binder: use bitmap for faster descriptor lookup
Carlos Llamas
maintainerPATCH v3 1/1 binder: use bitmap for faster descriptor lookup
When creating new binder references, the driver assigns a descriptor id that is shared with userspace. Regrettably, the driver needs to keep the descriptors small enough to accommodate userspace potentially using them as Vector indexes. Currently, the driver performs a linear search on the rb-tree of references to find the smallest available descriptor id. This approach, however, scales poorly as the number of references grows.
This patch introduces the usage of bitmaps to boost the performance of descriptor assignments. This optimization results in notable performance gains, particularly in processes with a large number of references. The following benchmark with 100,000 references showcases the difference in latency between the dbitmap implementation and the legacy approach:
[ 587.145098] get_ref_desc_olocked: 15us (dbitmap on) [ 602.788623] get_ref_desc_olocked: 47343us (dbitmap off)
Note the bitmap size is dynamically adjusted in line with the number of references, ensuring efficient memory usage. In cases where growing the bitmap is not possible, the driver falls back to the slow legacy method.
A previous attempt to solve this issue was proposed in [1]. However, such method involved adding new ioctls which isn't great, plus older userspace code would not have benefited from the optimizations either.
---
Notes:
v1: first solution using a new "flags" ioctl:
https://lore.kernel.org/all/[email protected]/
v2: switched to different implementation using bitmaps.
v3: dropped __GFP_ZERO when using zalloc().
renamed ...get_first_zero_bit() to ...acquire_first_zero_bit()
drivers/android/binder.c | 113 +++++++++++++++++++++--- drivers/android/binder_internal.h | 5 +- drivers/android/dbitmap.h | 139 ++++++++++++++++++++++++++++++ 3 files changed, 243 insertions(+), 14 deletions(-) create mode 100644 drivers/android/dbitmap.h
drivers/android/binder.c +100 -13
@@ -1045,6 +1045,67 @@ static struct binder_ref *binder_get_ref_olocked(struct binder_proc *proc,return NULL ; } +/* find first non-zero available descriptor the "slow way" */ +static u32 slow_desc_lookup_olocked (struct binder_proc *proc) +{ +struct binder_ref *ref; +struct rb_node *n; +u32 desc; + + desc =1 ; +for (n =rb_first (&proc->refs_by_desc); n; n =rb_next (n)) { + ref = rb_entry(n, struct binder_ref, rb_node_desc); +if (ref->data.desc > desc) +break ; + desc = ref->data.desc +1 ; + } + +return desc; +} + +/* +* Find an available reference descriptor. Note that the proc->outer_lock +* might be released in the process. In such case, -EAGAIN is returned and +* the provided descriptor is invalid. +*/ +static int get_ref_desc_olocked (struct binder_proc *proc, +struct binder_node *node, +u32 *desc) +{ +struct dbitmap *dmap = &proc->dmap; +unsigned long *new, bit; +unsigned int nbits; + +/* 0 is reserved for the context manager */ +if (node == proc->context->binder_context_mgr_node) { + *desc =0 ; +return 0 ; + } + +if (unlikely (!dbitmap_enabled (dmap))) { + *desc =slow_desc_lookup_olocked (proc); +return 0 ; + } + +if (dbitmap_acquire_first_zero_bit (dmap, &bit) ==0 ) { + *desc = bit; +return 0 ; + } + +/* +* The descriptors bitmap is full and needs to be expanded. +* The proc->outer_lock is briefly released to allocate the +* new bitmap safely. +*/ + nbits =dbitmap_expand_nbits (dmap); +binder_proc_unlock (proc); + new =bitmap_zalloc (nbits,GFP_KERNEL ); +binder_proc_lock (proc); +dbitmap_expand (dmap, new, nbits); + +return -EAGAIN ; +} +/** * binder_get_ref_for_node_olocked() - get the ref associated with given node * @proc: binder_proc that owns the ref
@@ -1068,12 +1129,14 @@ static struct binder_ref *binder_get_ref_for_node_olocked(struct binder_node *node, struct binder_ref *new_ref) { - struct binder_context *context = proc->context; -struct rb_node **p = &proc->refs_by_node.rb_node; -struct rb_node *parent =NULL ; struct binder_ref *ref; -struct rb_node *n; +struct rb_node *parent; +struct rb_node **p; +u32 desc; +retry: + p = &proc->refs_by_node.rb_node; + parent =NULL ;while (*p) { parent = *p; ref = rb_entry(parent, struct binder_ref, rb_node_node);
@@ -1088,6 +1151,10 @@ static struct binder_ref *binder_get_ref_for_node_olocked(if (!new_ref)return NULL ; +/* might release the proc->outer_lock */ +if (get_ref_desc_olocked (proc, node, &desc) == -EAGAIN ) + goto retry; +binder_stats_created (BINDER_STAT_REF ); new_ref->data.debug_id =atomic_inc_return (&binder_last_id); new_ref->proc = proc;
@@ -1095,14 +1162,7 @@ static struct binder_ref *binder_get_ref_for_node_olocked(rb_link_node (&new_ref->rb_node_node, parent, p);rb_insert_color (&new_ref->rb_node_node, &proc->refs_by_node); - new_ref->data.desc = (node == context->binder_context_mgr_node) ?0 :1 ; -for (n =rb_first (&proc->refs_by_desc); n !=NULL ; n =rb_next (n)) { - ref = rb_entry(n, struct binder_ref, rb_node_desc); -if (ref->data.desc > new_ref->data.desc) -break ; - new_ref->data.desc = ref->data.desc +1 ; - } - + new_ref->data.desc = desc; p = &proc->refs_by_desc.rb_node;while (*p) { parent = *p;
@@ -1131,6 +1191,7 @@ static struct binder_ref *binder_get_ref_for_node_olocked(static void binder_cleanup_ref_olocked (struct binder_ref *ref) { +struct dbitmap *dmap = &ref->proc->dmap;bool delete_node = false; binder_debug(BINDER_DEBUG_INTERNAL_REFS,
@@ -1138,6 +1199,8 @@ static void binder_cleanup_ref_olocked(struct binder_ref *ref) ref->proc->pid, ref->data.debug_id, ref->data.desc, ref->node->debug_id); +if (dbitmap_enabled (dmap)) +dbitmap_clear_bit (dmap, ref->data.desc);rb_erase (&ref->rb_node_desc, &ref->proc->refs_by_desc);rb_erase (&ref->rb_node_node, &ref->proc->refs_by_node);
@@ -1298,6 +1361,25 @@ static void binder_free_ref(struct binder_ref *ref)kfree (ref); } +/* shrink descriptor bitmap if needed */ +static void try_shrink_dmap (struct binder_proc *proc) +{ +unsigned long *new; +int nbits; + +binder_proc_lock (proc); + nbits =dbitmap_shrink_nbits (&proc->dmap); +binder_proc_unlock (proc); + +if (!nbits) +return ; + + new =bitmap_zalloc (nbits,GFP_KERNEL ); +binder_proc_lock (proc); +dbitmap_shrink (&proc->dmap, new, nbits); +binder_proc_unlock (proc); +} +/** * binder_update_ref_for_handle() - inc/dec the ref for given handle * @proc: proc containing the ref
@@ -1334,8 +1416,10 @@ static int binder_update_ref_for_handle(struct binder_proc *proc, *rdata = ref->data;binder_proc_unlock (proc); -if (delete_ref) +if (delete_ref) {binder_free_ref (ref); +try_shrink_dmap (proc); + }return ret; err_no_ref:
@@ -4931,6 +5015,7 @@ static void binder_free_proc(struct binder_proc *proc)put_task_struct (proc->tsk);put_cred (proc->cred);binder_stats_deleted (BINDER_STAT_PROC ); +dbitmap_free (&proc->dmap);kfree (proc); }
@@ -5634,6 +5719,8 @@ static int binder_open(struct inode *nodp, struct file *filp) proc =kzalloc (sizeof (*proc),GFP_KERNEL );if (proc ==NULL )return -ENOMEM ; + +dbitmap_init (&proc->dmap);spin_lock_init (&proc->inner_lock);spin_lock_init (&proc->outer_lock);get_task_struct (current->group_leader);
drivers/android/binder_internal.h +4 -1
@@ -14,6 +14,7 @@#include <linux/uidgid.h> #include <uapi/linux/android/binderfs.h> #include "binder_alloc.h" +#include "dbitmap.h" struct binder_context {struct binder_node *binder_context_mgr_node;
@@ -368,6 +369,8 @@ struct binder_ref {* @freeze_wait: waitqueue of processes waiting for all outstanding * transactions to be processed * (protected by @inner_lock) +* @dmap bitmap to manage available reference descriptors +* (protected by @outer_lock) * @todo: list of work for this process * (protected by @inner_lock) * @stats: per-process binder statistics
@@ -417,7 +420,7 @@ struct binder_proc {bool sync_recv;bool async_recv;wait_queue_head_t freeze_wait; - +struct dbitmap dmap;struct list_head todo;struct binder_stats stats;struct list_head delivered_death;
drivers/android/dbitmap.h new file +139 -0
139 lines not on this page · raw message
Signature · 1 line
2.45.0.rc1.225.g2a3ae87e7f-goog
Quoted 25 lines · Carlos Llamas
When creating new binder references, the driver assigns a descriptor id that is shared with userspace. Regrettably, the driver needs to keep the descriptors small enough to accommodate userspace potentially using them as Vector indexes. Currently, the driver performs a linear search on the rb-tree of references to find the smallest available descriptor id. This approach, however, scales poorly as the number of references grows.
This patch introduces the usage of bitmaps to boost the performance of descriptor assignments. This optimization results in notable performance gains, particularly in processes with a large number of references. The following benchmark with 100,000 references showcases the difference in latency between the dbitmap implementation and the legacy approach:
[ 587.145098] get_ref_desc_olocked: 15us (dbitmap on) [ 602.788623] get_ref_desc_olocked: 47343us (dbitmap off)Note the bitmap size is dynamically adjusted in line with the number of references, ensuring efficient memory usage. In cases where growing the bitmap is not possible, the driver falls back to the slow legacy method.
A previous attempt to solve this issue was proposed in [1]. However, such method involved adding new ioctls which isn't great, plus older userspace code would not have benefited from the optimizations either.
Quoted 10 lines
Cc Tim Murray <[email protected]>Cc Arve Hjønnevåg <[email protected]>Cc Alice Ryhl <[email protected]>Cc Martijn Coenen <[email protected]>Cc Todd Kjos <[email protected]>Cc John Stultz <[email protected]>Cc Steven Moreland <[email protected]>Suggested-by Nick Chen <[email protected]>Signed-off-by Carlos Llamas <[email protected]>
LGTM. One nit below, but it's not a correctness issue.
drivers/android/dbitmap.h line 37
Quoted 13 lines
drivers/android/dbitmap.h new file +13
-0+static inline unsigned int dbitmap_shrink_nbits (struct dbitmap *dmap) +{ +unsigned int bit; + +if (dmap->nbits <=NBITS_MIN ) +return 0 ; + + bit =find_last_bit (dmap->map, dmap->nbits); +if (unlikely (bit == dmap->nbits)) +return NBITS_MIN ; + +if (unlikely (bit <= (dmap->nbits >>2 ))) +return dmap->nbits >>1 ;
I think this is intended to say that we only shrink if only the lower fourth of the bits have any bits set, but for the condition to actually be that, you need bit < (map->nbits >> 2) here instead of <=.
Alice
Carlos Llamas
maintainerQuoted 51 lines · Alice Ryhl
Quoted 25 lines · Carlos Llamas
When creating new binder references, the driver assigns a descriptor id that is shared with userspace. Regrettably, the driver needs to keep the descriptors small enough to accommodate userspace potentially using them as Vector indexes. Currently, the driver performs a linear search on the rb-tree of references to find the smallest available descriptor id. This approach, however, scales poorly as the number of references grows.
This patch introduces the usage of bitmaps to boost the performance of descriptor assignments. This optimization results in notable performance gains, particularly in processes with a large number of references. The following benchmark with 100,000 references showcases the difference in latency between the dbitmap implementation and the legacy approach:
[ 587.145098] get_ref_desc_olocked: 15us (dbitmap on) [ 602.788623] get_ref_desc_olocked: 47343us (dbitmap off)Note the bitmap size is dynamically adjusted in line with the number of references, ensuring efficient memory usage. In cases where growing the bitmap is not possible, the driver falls back to the slow legacy method.
A previous attempt to solve this issue was proposed in [1]. However, such method involved adding new ioctls which isn't great, plus older userspace code would not have benefited from the optimizations either.
Quoted 10 lines
Cc Tim Murray <[email protected]>Cc Arve Hjønnevåg <[email protected]>Cc Alice Ryhl <[email protected]>Cc Martijn Coenen <[email protected]>Cc Todd Kjos <[email protected]>Cc John Stultz <[email protected]>Cc Steven Moreland <[email protected]>Suggested-by Nick Chen <[email protected]>Signed-off-by Carlos Llamas <[email protected]>LGTM. One nit below, but it's not a correctness issue.
Reviewed-by Alice Ryhl <[email protected]>Quoted 10 lines
drivers/android/dbitmap.h new file +10
-0+static inline unsigned int dbitmap_shrink_nbits (struct dbitmap *dmap) +{ +unsigned int bit; + +if (dmap->nbits <=NBITS_MIN ) +return 0 ; + + bit =find_last_bit (dmap->map, dmap->nbits); +if (unlikely (bit == dmap->nbits)) +return NBITS_MIN ;
Quoted 8 lines
drivers/android/dbitmap.h line 37
Quoted 3 lines
drivers/android/dbitmap.h new file +3
-0+ +if (unlikely (bit <= (dmap->nbits >>2 ))) +return dmap->nbits >>1 ;I think this is intended to say that we only shrink if only the lower fourth of the bits have any bits set, but for the condition to actually be that, you need
bit < (map->nbits >> 2)here instead of<=.
True, the range goes [0...n-1] so it should be "bit < n". Let me fix that. Thanks.
Quoted 2 lines
Alice
Carlos Llamas
maintainerPATCH v4 1/1 binder: use bitmap for faster descriptor lookup
In reply to Alice RyhlWhen creating new binder references, the driver assigns a descriptor id that is shared with userspace. Regrettably, the driver needs to keep the descriptors small enough to accommodate userspace potentially using them as Vector indexes. Currently, the driver performs a linear search on the rb-tree of references to find the smallest available descriptor id. This approach, however, scales poorly as the number of references grows.
This patch introduces the usage of bitmaps to boost the performance of descriptor assignments. This optimization results in notable performance gains, particularly in processes with a large number of references. The following benchmark with 100,000 references showcases the difference in latency between the dbitmap implementation and the legacy approach:
[ 587.145098] get_ref_desc_olocked: 15us (dbitmap on) [ 602.788623] get_ref_desc_olocked: 47343us (dbitmap off)
Note the bitmap size is dynamically adjusted in line with the number of references, ensuring efficient memory usage. In cases where growing the bitmap is not possible, the driver falls back to the slow legacy method.
A previous attempt to solve this issue was proposed in [1]. However, such method involved adding new ioctls which isn't great, plus older userspace code would not have benefited from the optimizations either.
---
Notes:
v1: first solution using a new "flags" ioctl:
https://lore.kernel.org/all/[email protected]/
v2: switched to different implementation using bitmaps.
v3: dropped __GFP_ZERO when using zalloc().
renamed ...get_first_zero_bit() to ...acquire_first_zero_bit()
v4: fix bit range check for 25% bitmap capacity.
drivers/android/binder.c | 113 +++++++++++++++++++++--- drivers/android/binder_internal.h | 5 +- drivers/android/dbitmap.h | 139 ++++++++++++++++++++++++++++++ 3 files changed, 243 insertions(+), 14 deletions(-) create mode 100644 drivers/android/dbitmap.h
drivers/android/binder.c +100 -13
@@ -1045,6 +1045,67 @@ static struct binder_ref *binder_get_ref_olocked(struct binder_proc *proc,return NULL ; } +/* find first non-zero available descriptor the "slow way" */ +static u32 slow_desc_lookup_olocked (struct binder_proc *proc) +{ +struct binder_ref *ref; +struct rb_node *n; +u32 desc; + + desc =1 ; +for (n =rb_first (&proc->refs_by_desc); n; n =rb_next (n)) { + ref = rb_entry(n, struct binder_ref, rb_node_desc); +if (ref->data.desc > desc) +break ; + desc = ref->data.desc +1 ; + } + +return desc; +} + +/* +* Find an available reference descriptor. Note that the proc->outer_lock +* might be released in the process. In such case, -EAGAIN is returned and +* the provided descriptor is invalid. +*/ +static int get_ref_desc_olocked (struct binder_proc *proc, +struct binder_node *node, +u32 *desc) +{ +struct dbitmap *dmap = &proc->dmap; +unsigned long *new, bit; +unsigned int nbits; + +/* 0 is reserved for the context manager */ +if (node == proc->context->binder_context_mgr_node) { + *desc =0 ; +return 0 ; + } + +if (unlikely (!dbitmap_enabled (dmap))) { + *desc =slow_desc_lookup_olocked (proc); +return 0 ; + } + +if (dbitmap_acquire_first_zero_bit (dmap, &bit) ==0 ) { + *desc = bit; +return 0 ; + } + +/* +* The descriptors bitmap is full and needs to be expanded. +* The proc->outer_lock is briefly released to allocate the +* new bitmap safely. +*/ + nbits =dbitmap_expand_nbits (dmap); +binder_proc_unlock (proc); + new =bitmap_zalloc (nbits,GFP_KERNEL ); +binder_proc_lock (proc); +dbitmap_expand (dmap, new, nbits); + +return -EAGAIN ; +} +/** * binder_get_ref_for_node_olocked() - get the ref associated with given node * @proc: binder_proc that owns the ref
@@ -1068,12 +1129,14 @@ static struct binder_ref *binder_get_ref_for_node_olocked(struct binder_node *node, struct binder_ref *new_ref) { - struct binder_context *context = proc->context; -struct rb_node **p = &proc->refs_by_node.rb_node; -struct rb_node *parent =NULL ; struct binder_ref *ref; -struct rb_node *n; +struct rb_node *parent; +struct rb_node **p; +u32 desc; +retry: + p = &proc->refs_by_node.rb_node; + parent =NULL ;while (*p) { parent = *p; ref = rb_entry(parent, struct binder_ref, rb_node_node);
@@ -1088,6 +1151,10 @@ static struct binder_ref *binder_get_ref_for_node_olocked(if (!new_ref)return NULL ; +/* might release the proc->outer_lock */ +if (get_ref_desc_olocked (proc, node, &desc) == -EAGAIN ) + goto retry; +binder_stats_created (BINDER_STAT_REF ); new_ref->data.debug_id =atomic_inc_return (&binder_last_id); new_ref->proc = proc;
@@ -1095,14 +1162,7 @@ static struct binder_ref *binder_get_ref_for_node_olocked(rb_link_node (&new_ref->rb_node_node, parent, p);rb_insert_color (&new_ref->rb_node_node, &proc->refs_by_node); - new_ref->data.desc = (node == context->binder_context_mgr_node) ?0 :1 ; -for (n =rb_first (&proc->refs_by_desc); n !=NULL ; n =rb_next (n)) { - ref = rb_entry(n, struct binder_ref, rb_node_desc); -if (ref->data.desc > new_ref->data.desc) -break ; - new_ref->data.desc = ref->data.desc +1 ; - } - + new_ref->data.desc = desc; p = &proc->refs_by_desc.rb_node;while (*p) { parent = *p;
@@ -1131,6 +1191,7 @@ static struct binder_ref *binder_get_ref_for_node_olocked(static void binder_cleanup_ref_olocked (struct binder_ref *ref) { +struct dbitmap *dmap = &ref->proc->dmap;bool delete_node = false; binder_debug(BINDER_DEBUG_INTERNAL_REFS,
@@ -1138,6 +1199,8 @@ static void binder_cleanup_ref_olocked(struct binder_ref *ref) ref->proc->pid, ref->data.debug_id, ref->data.desc, ref->node->debug_id); +if (dbitmap_enabled (dmap)) +dbitmap_clear_bit (dmap, ref->data.desc);rb_erase (&ref->rb_node_desc, &ref->proc->refs_by_desc);rb_erase (&ref->rb_node_node, &ref->proc->refs_by_node);
@@ -1298,6 +1361,25 @@ static void binder_free_ref(struct binder_ref *ref)kfree (ref); } +/* shrink descriptor bitmap if needed */ +static void try_shrink_dmap (struct binder_proc *proc) +{ +unsigned long *new; +int nbits; + +binder_proc_lock (proc); + nbits =dbitmap_shrink_nbits (&proc->dmap); +binder_proc_unlock (proc); + +if (!nbits) +return ; + + new =bitmap_zalloc (nbits,GFP_KERNEL ); +binder_proc_lock (proc); +dbitmap_shrink (&proc->dmap, new, nbits); +binder_proc_unlock (proc); +} +/** * binder_update_ref_for_handle() - inc/dec the ref for given handle * @proc: proc containing the ref
@@ -1334,8 +1416,10 @@ static int binder_update_ref_for_handle(struct binder_proc *proc, *rdata = ref->data;binder_proc_unlock (proc); -if (delete_ref) +if (delete_ref) {binder_free_ref (ref); +try_shrink_dmap (proc); + }return ret; err_no_ref:
@@ -4931,6 +5015,7 @@ static void binder_free_proc(struct binder_proc *proc)put_task_struct (proc->tsk);put_cred (proc->cred);binder_stats_deleted (BINDER_STAT_PROC ); +dbitmap_free (&proc->dmap);kfree (proc); }
@@ -5634,6 +5719,8 @@ static int binder_open(struct inode *nodp, struct file *filp) proc =kzalloc (sizeof (*proc),GFP_KERNEL );if (proc ==NULL )return -ENOMEM ; + +dbitmap_init (&proc->dmap);spin_lock_init (&proc->inner_lock);spin_lock_init (&proc->outer_lock);get_task_struct (current->group_leader);
drivers/android/binder_internal.h +4 -1
@@ -14,6 +14,7 @@#include <linux/uidgid.h> #include <uapi/linux/android/binderfs.h> #include "binder_alloc.h" +#include "dbitmap.h" struct binder_context {struct binder_node *binder_context_mgr_node;
@@ -368,6 +369,8 @@ struct binder_ref {* @freeze_wait: waitqueue of processes waiting for all outstanding * transactions to be processed * (protected by @inner_lock) +* @dmap bitmap to manage available reference descriptors +* (protected by @outer_lock) * @todo: list of work for this process * (protected by @inner_lock) * @stats: per-process binder statistics
@@ -417,7 +420,7 @@ struct binder_proc {bool sync_recv;bool async_recv;wait_queue_head_t freeze_wait; - +struct dbitmap dmap;struct list_head todo;struct binder_stats stats;struct list_head delivered_death;
drivers/android/dbitmap.h new file +139 -0
139 lines not on this page · raw message
Signature · 1 line
2.45.0.rc1.225.g2a3ae87e7f-goog
Greg Kroah-Hartman
maintainerdrivers/android/dbitmap.h line 4
Quoted 10 lines · Carlos Llamas
drivers/android/dbitmap.h new file +4
-0@@ -0,0 +1,139 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef _LINUX_DBITMAP_H +#define _LINUX_DBITMAP_H +#include <linux/bitmap.h>
No copyright line for a new file? Somehow I doubt that's what your corporate policy is :(
drivers/android/dbitmap.h line 11
Quoted 7 lines
drivers/android/dbitmap.h new file +7
-0+ +#define NBITS_MIN BITS_PER_TYPE(unsigned long) + +struct dbitmap { +unsigned int nbits; +unsigned long *map; +};
Some documentation about how this all works would be nice so we can verify / validate it is doing what it should be doing.
And maybe a test?
drivers/android/dbitmap.h line 22
Quoted 11 lines
drivers/android/dbitmap.h new file +11
-0+ +static inline int dbitmap_enabled (struct dbitmap *dmap) +{ +return dmap->map !=NULL ; +} + +static inline void dbitmap_free (struct dbitmap *dmap) +{ + dmap->nbits =0 ; +kfree (dmap->map); + dmap->map =NULL ;
Why are you setting this to NULL after freeing it? What does that signal?
Quoted 5 lines
drivers/android/dbitmap.h new file +5
-0+} + +static inline unsigned int dbitmap_shrink_nbits (struct dbitmap *dmap) +{ +unsigned int bit;
drivers/android/dbitmap.h line 37
Quoted 10 lines
drivers/android/dbitmap.h new file +10
-0+ +if (dmap->nbits <=NBITS_MIN ) +return 0 ; + + bit =find_last_bit (dmap->map, dmap->nbits); +if (unlikely (bit == dmap->nbits)) +return NBITS_MIN ; + +if (unlikely (bit < (dmap->nbits >>2 ))) +return dmap->nbits >>1 ;
And these unlikely() markings actually work better than not having them? Please document that if so.
Quoted 8 lines
drivers/android/dbitmap.h new file +8
-0+ +return 0 ; +} + +static inline void +dbitmap_replace (struct dbitmap *dmap,unsigned long *new,unsigned int nbits) +{ +bitmap_copy (new, dmap->map,min (dmap->nbits, nbits));
drivers/android/dbitmap.h line 55
Quoted 10 lines
drivers/android/dbitmap.h new file +10
-0+kfree (dmap->map); + dmap->map = new; + dmap->nbits = nbits; +} + +static inline void +dbitmap_shrink (struct dbitmap *dmap,unsigned long *new,unsigned int nbits) +{ +if (unlikely (!new)) +return ;
All unlikely/likely needs to be "proven" to be needed, otherwise the compiler and cpu almost always does a better job over time.
Quoted 19 lines
drivers/android/dbitmap.h new file +19
-0+ +/* +* Make sure we can still shrink to the requested nbits as +* this call might have raced with another shrink or more +* bits have been assigned. In such case, release the @new +* bitmap and move on. +*/ +if (unlikely (!dbitmap_enabled (dmap) || +dbitmap_shrink_nbits (dmap) != nbits)) { +kfree (new); +return ; + } + +dbitmap_replace (dmap, new, nbits); +} + +static inline unsigned int +dbitmap_expand_nbits (struct dbitmap *dmap) +{
drivers/android/dbitmap.h line 84
Quoted 10 lines
drivers/android/dbitmap.h new file +10
-0+return dmap->nbits <<1 ; +} + +static inline void +dbitmap_expand (struct dbitmap *dmap,unsigned long *new,unsigned int nbits) +{ +/* +* Determine if the expand is still valid as it might have +* raced with another expand or free. In such case, release +* the @new bitmap and move on.
Shouldn't locks protect any race? otherwise what happens if it changes right after you check for this?
drivers/android/dbitmap.h line 96
Quoted 12 lines
drivers/android/dbitmap.h new file +12
-0+*/ +if (unlikely (!dbitmap_enabled (dmap) || nbits <= dmap->nbits)) { +kfree (new); +return ; + } + +/* +* ENOMEM is checked here as we can now discard a potential +* race with another successful expand. In such case, disable +* the dbitmap and fallback to slow_desc_lookup_olocked(). +*/ +if (unlikely (!new)) {
As you control the callers, how can this happen?
Quoted 29 lines
drivers/android/dbitmap.h new file +29
-0+dbitmap_free (dmap); +return ; + } + +dbitmap_replace (dmap, new, nbits); +} + +static inline int +dbitmap_acquire_first_zero_bit (struct dbitmap *dmap,unsigned long *bit) +{ +unsigned long n; + + n =find_first_zero_bit (dmap->map, dmap->nbits); +if (unlikely (n == dmap->nbits)) +return -ENOSPC ; + + *bit = n; +set_bit (n, dmap->map); + +return 0 ; +} + +static inline void +dbitmap_clear_bit (struct dbitmap *dmap,unsigned long bit) +{ +clear_bit (bit, dmap->map); +} + +static inline int dbitmap_init (struct dbitmap *dmap)
drivers/android/dbitmap.h line 135
Quoted 10 lines
drivers/android/dbitmap.h new file +10
-0+{ + dmap->map =bitmap_zalloc (NBITS_MIN ,GFP_KERNEL ); +if (!dmap->map) { + dmap->nbits =0 ; +return -ENOMEM ; + } + + dmap->nbits =NBITS_MIN ; +/* 0 is reserved for the context manager */ +set_bit (0 , dmap->map);
Yeah, this all needs to be documented somewhere please :)
thanks,
greg k-h
Carlos Llamas
maintainerQuoted 14 lines · Greg Kroah-Hartman
drivers/android/dbitmap.h line 4
Quoted 10 lines · Carlos Llamas
drivers/android/dbitmap.h new file +4
-0@@ -0,0 +1,139 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef _LINUX_DBITMAP_H +#define _LINUX_DBITMAP_H +#include <linux/bitmap.h> No copyright line for a new file? Somehow I doubt that's what your corporate policy is :(
It is not, sorry I'll fix it.
Quoted 15 lines
drivers/android/dbitmap.h line 11
Quoted 9 lines
drivers/android/dbitmap.h new file +7
-0+ +#define NBITS_MIN BITS_PER_TYPE(unsigned long) + +struct dbitmap { +unsigned int nbits; +unsigned long *map; +};Some documentation about how this all works would be nice so we can verify / validate it is doing what it should be doing.
And maybe a test?
Quoted 14 lines
drivers/android/dbitmap.h line 22
Quoted 11 lines
drivers/android/dbitmap.h new file +11
-0+ +static inline int dbitmap_enabled (struct dbitmap *dmap) +{ +return dmap->map !=NULL ; +} + +static inline void dbitmap_free (struct dbitmap *dmap) +{ + dmap->nbits =0 ; +kfree (dmap->map); + dmap->map =NULL ;Why are you setting this to NULL after freeing it? What does that signal?
The signal is on dbitmap_enabled(). I'll either add a comment to this or create a dbitmap_disable() to pair with it in the next version.
Quoted 34 lines
Quoted 6 lines
drivers/android/dbitmap.h new file +5
-0+} + +static inline unsigned int dbitmap_shrink_nbits (struct dbitmap *dmap) +{ +unsigned int bit;drivers/android/dbitmap.h line 37
Quoted 10 lines
drivers/android/dbitmap.h new file +10
-0+ +if (dmap->nbits <=NBITS_MIN ) +return 0 ; + + bit =find_last_bit (dmap->map, dmap->nbits); +if (unlikely (bit == dmap->nbits)) +return NBITS_MIN ; + +if (unlikely (bit < (dmap->nbits >>2 ))) +return dmap->nbits >>1 ;And these
unlikely()markings actually work better than not having them? Please document that if so.Quoted 13 lines
drivers/android/dbitmap.h new file +13
-0+ +return 0 ; +} + +static inline void +dbitmap_replace (struct dbitmap *dmap,unsigned long *new,unsigned int nbits) +{ +bitmap_copy (new, dmap->map,min (dmap->nbits, nbits)); +kfree (dmap->map); + dmap->map = new; + dmap->nbits = nbits; +} +
Quoted 8 lines
drivers/android/dbitmap.h line 55
Quoted 5 lines
drivers/android/dbitmap.h new file +5
-0+static inline void +dbitmap_shrink (struct dbitmap *dmap,unsigned long *new,unsigned int nbits) +{ +if (unlikely (!new)) +return ;All unlikely/likely needs to be "proven" to be needed, otherwise the compiler and cpu almost always does a better job over time.
Ok, I'll drop all these unlikely/likely and let the compiler and cpu do their thing.
Quoted 25 lines
Quoted 25 lines
drivers/android/dbitmap.h new file +24
-0+ +/* +* Make sure we can still shrink to the requested nbits as +* this call might have raced with another shrink or more +* bits have been assigned. In such case, release the @new +* bitmap and move on. +*/ +if (unlikely (!dbitmap_enabled (dmap) || +dbitmap_shrink_nbits (dmap) != nbits)) { +kfree (new); +return ; + } + +dbitmap_replace (dmap, new, nbits); +} + +static inline unsigned int +dbitmap_expand_nbits (struct dbitmap *dmap) +{ +return dmap->nbits <<1 ; +} + +static inline void +dbitmap_expand (struct dbitmap *dmap,unsigned long *new,unsigned int nbits)
Quoted 8 lines
drivers/android/dbitmap.h line 84
Quoted 5 lines
drivers/android/dbitmap.h new file +5
-0+{ +/* +* Determine if the expand is still valid as it might have +* raced with another expand or free. In such case, release +* the @new bitmap and move on. Shouldn't locks protect any race? otherwise what happens if it changes right after you check for this?
Yes, there are locks protecting this call. However, these are spinlocks so the bitmap gets alloc'ed outside of them. e.g.
nbits = dbitmap_expand_nbits(dmap); spin_unlock(&proc->lock); new = bimap_zalloc(nbits, GFP_KERNEL); spin_lock(&proc->lock); dbitmap_expand(dmap, new, nbits);
Thus why we need to check if other task beat us to the expand. Sorry, I now realize this needs to be documented.
Quoted 16 lines
Quoted 4 lines
drivers/android/dbitmap.h new file +2
-0+*/ +if (unlikely (!dbitmap_enabled (dmap) || nbits <= dmap->nbits)) {drivers/android/dbitmap.h line 96
Quoted 10 lines
drivers/android/dbitmap.h new file +10
-0+kfree (new); +return ; + } + +/* +* ENOMEM is checked here as we can now discard a potential +* race with another successful expand. In such case, disable +* the dbitmap and fallback to slow_desc_lookup_olocked(). +*/ +if (unlikely (!new)) {As you control the callers, how can this happen?
Delaying this check has the advantage that we can rely on another successful expand call. So in this case the "race" is good. The comment above the check has these details.
Quoted 34 lines
Quoted 34 lines
drivers/android/dbitmap.h new file +33
-0+dbitmap_free (dmap); +return ; + } + +dbitmap_replace (dmap, new, nbits); +} + +static inline int +dbitmap_acquire_first_zero_bit (struct dbitmap *dmap,unsigned long *bit) +{ +unsigned long n; + + n =find_first_zero_bit (dmap->map, dmap->nbits); +if (unlikely (n == dmap->nbits)) +return -ENOSPC ; + + *bit = n; +set_bit (n, dmap->map); + +return 0 ; +} + +static inline void +dbitmap_clear_bit (struct dbitmap *dmap,unsigned long bit) +{ +clear_bit (bit, dmap->map); +} + +static inline int dbitmap_init (struct dbitmap *dmap) +{ + dmap->map =bitmap_zalloc (NBITS_MIN ,GFP_KERNEL ); +if (!dmap->map) { + dmap->nbits =0 ;
Quoted 8 lines
drivers/android/dbitmap.h line 135
Quoted 6 lines
drivers/android/dbitmap.h new file +6
-0+return -ENOMEM ; + } + + dmap->nbits =NBITS_MIN ; +/* 0 is reserved for the context manager */ +set_bit (0 , dmap->map);Yeah, this all needs to be documented somewhere please :)
Yeah ok, I'll add the documentation.
Quoted 4 lines
thanks,
greg k-h
Thanks,
Carlos Llamas
Carlos Llamas
maintainerPATCH v5 1/1 binder: use bitmap for faster descriptor lookup
In reply to Greg Kroah-HartmanWhen creating new binder references, the driver assigns a descriptor id that is shared with userspace. Regrettably, the driver needs to keep the descriptors small enough to accommodate userspace potentially using them as Vector indexes. Currently, the driver performs a linear search on the rb-tree of references to find the smallest available descriptor id. This approach, however, scales poorly as the number of references grows.
This patch introduces the usage of bitmaps to boost the performance of descriptor assignments. This optimization results in notable performance gains, particularly in processes with a large number of references. The following benchmark with 100,000 references showcases the difference in latency between the dbitmap implementation and the legacy approach:
[ 587.145098] get_ref_desc_olocked: 15us (dbitmap on) [ 602.788623] get_ref_desc_olocked: 47343us (dbitmap off)
Note the bitmap size is dynamically adjusted in line with the number of references, ensuring efficient memory usage. In cases where growing the bitmap is not possible, the driver falls back to the slow legacy method.
A previous attempt to solve this issue was proposed in [1]. However, such method involved adding new ioctls which isn't great, plus older userspace code would not have benefited from the optimizations either.
---
Notes:
v1: first solution using a new "flags" ioctl:
https://lore.kernel.org/all/[email protected]/
v2: switched to different implementation using bitmaps.
v3: dropped __GFP_ZERO when using zalloc().
renamed ...get_first_zero_bit() to ...acquire_first_zero_bit()
v4: fix bit range check for 25% bitmap capacity.
v5: Per gregkh's feedback:
- fix new file copyright line according to Google's policy
- add plenty of comments documenting dbitmap's behavior
- drop (un)likely() and let compiler/cpu do a better job
- use dmap->nbits to determine if dbitmap is disabled Also:
- make sure dbitmap can't clear BIT(0)
- rename "_expand()" to "_grow()"
drivers/android/binder.c | 112 ++++++++++++++++--- drivers/android/binder_internal.h | 5 +- drivers/android/dbitmap.h | 176 ++++++++++++++++++++++++++++++ 3 files changed, 279 insertions(+), 14 deletions(-) create mode 100644 drivers/android/dbitmap.h
drivers/android/binder.c +99 -13
@@ -1045,6 +1045,66 @@ static struct binder_ref *binder_get_ref_olocked(struct binder_proc *proc,return NULL ; } +/* Find the smallest unused descriptor the "slow way" */ +static u32 slow_desc_lookup_olocked (struct binder_proc *proc) +{ +struct binder_ref *ref; +struct rb_node *n; +u32 desc; + + desc =1 ; +for (n =rb_first (&proc->refs_by_desc); n; n =rb_next (n)) { + ref = rb_entry(n, struct binder_ref, rb_node_desc); +if (ref->data.desc > desc) +break ; + desc = ref->data.desc +1 ; + } + +return desc; +} + +/* +* Find an available reference descriptor ID. The proc->outer_lock might +* be released in the process, in which case -EAGAIN is returned and the +* @desc should be considered invalid. +*/ +static int get_ref_desc_olocked (struct binder_proc *proc, +struct binder_node *node, +u32 *desc) +{ +struct dbitmap *dmap = &proc->dmap; +unsigned long *new, bit; +unsigned int nbits; + +/* 0 is reserved for the context manager */ +if (node == proc->context->binder_context_mgr_node) { + *desc =0 ; +return 0 ; + } + +if (!dbitmap_enabled (dmap)) { + *desc =slow_desc_lookup_olocked (proc); +return 0 ; + } + +if (dbitmap_acquire_first_zero_bit (dmap, &bit) ==0 ) { + *desc = bit; +return 0 ; + } + +/* +* The dbitmap is full and needs to grow. The proc->outer_lock +* is briefly released to allocate the new bitmap safely. +*/ + nbits =dbitmap_grow_nbits (dmap); +binder_proc_unlock (proc); + new =bitmap_zalloc (nbits,GFP_KERNEL ); +binder_proc_lock (proc); +dbitmap_grow (dmap, new, nbits); + +return -EAGAIN ; +} +/** * binder_get_ref_for_node_olocked() - get the ref associated with given node * @proc: binder_proc that owns the ref
@@ -1068,12 +1128,14 @@ static struct binder_ref *binder_get_ref_for_node_olocked(struct binder_node *node, struct binder_ref *new_ref) { - struct binder_context *context = proc->context; -struct rb_node **p = &proc->refs_by_node.rb_node; -struct rb_node *parent =NULL ; struct binder_ref *ref; -struct rb_node *n; +struct rb_node *parent; +struct rb_node **p; +u32 desc; +retry: + p = &proc->refs_by_node.rb_node; + parent =NULL ;while (*p) { parent = *p; ref = rb_entry(parent, struct binder_ref, rb_node_node);
@@ -1088,6 +1150,10 @@ static struct binder_ref *binder_get_ref_for_node_olocked(if (!new_ref)return NULL ; +/* might release the proc->outer_lock */ +if (get_ref_desc_olocked (proc, node, &desc) == -EAGAIN ) + goto retry; +binder_stats_created (BINDER_STAT_REF ); new_ref->data.debug_id =atomic_inc_return (&binder_last_id); new_ref->proc = proc;
@@ -1095,14 +1161,7 @@ static struct binder_ref *binder_get_ref_for_node_olocked(rb_link_node (&new_ref->rb_node_node, parent, p);rb_insert_color (&new_ref->rb_node_node, &proc->refs_by_node); - new_ref->data.desc = (node == context->binder_context_mgr_node) ?0 :1 ; -for (n =rb_first (&proc->refs_by_desc); n !=NULL ; n =rb_next (n)) { - ref = rb_entry(n, struct binder_ref, rb_node_desc); -if (ref->data.desc > new_ref->data.desc) -break ; - new_ref->data.desc = ref->data.desc +1 ; - } - + new_ref->data.desc = desc; p = &proc->refs_by_desc.rb_node;while (*p) { parent = *p;
@@ -1131,6 +1190,7 @@ static struct binder_ref *binder_get_ref_for_node_olocked(static void binder_cleanup_ref_olocked (struct binder_ref *ref) { +struct dbitmap *dmap = &ref->proc->dmap;bool delete_node = false; binder_debug(BINDER_DEBUG_INTERNAL_REFS,
@@ -1138,6 +1198,8 @@ static void binder_cleanup_ref_olocked(struct binder_ref *ref) ref->proc->pid, ref->data.debug_id, ref->data.desc, ref->node->debug_id); +if (dbitmap_enabled (dmap)) +dbitmap_clear_bit (dmap, ref->data.desc);rb_erase (&ref->rb_node_desc, &ref->proc->refs_by_desc);rb_erase (&ref->rb_node_node, &ref->proc->refs_by_node);
@@ -1298,6 +1360,25 @@ static void binder_free_ref(struct binder_ref *ref)kfree (ref); } +/* shrink descriptor bitmap if needed */ +static void try_shrink_dmap (struct binder_proc *proc) +{ +unsigned long *new; +int nbits; + +binder_proc_lock (proc); + nbits =dbitmap_shrink_nbits (&proc->dmap); +binder_proc_unlock (proc); + +if (!nbits) +return ; + + new =bitmap_zalloc (nbits,GFP_KERNEL ); +binder_proc_lock (proc); +dbitmap_shrink (&proc->dmap, new, nbits); +binder_proc_unlock (proc); +} +/** * binder_update_ref_for_handle() - inc/dec the ref for given handle * @proc: proc containing the ref
@@ -1334,8 +1415,10 @@ static int binder_update_ref_for_handle(struct binder_proc *proc, *rdata = ref->data;binder_proc_unlock (proc); -if (delete_ref) +if (delete_ref) {binder_free_ref (ref); +try_shrink_dmap (proc); + }return ret; err_no_ref:
@@ -4931,6 +5014,7 @@ static void binder_free_proc(struct binder_proc *proc)put_task_struct (proc->tsk);put_cred (proc->cred);binder_stats_deleted (BINDER_STAT_PROC ); +dbitmap_free (&proc->dmap);kfree (proc); }
@@ -5634,6 +5718,8 @@ static int binder_open(struct inode *nodp, struct file *filp) proc =kzalloc (sizeof (*proc),GFP_KERNEL );if (proc ==NULL )return -ENOMEM ; + +dbitmap_init (&proc->dmap);spin_lock_init (&proc->inner_lock);spin_lock_init (&proc->outer_lock);get_task_struct (current->group_leader);
drivers/android/binder_internal.h +4 -1
@@ -14,6 +14,7 @@#include <linux/uidgid.h> #include <uapi/linux/android/binderfs.h> #include "binder_alloc.h" +#include "dbitmap.h" struct binder_context {struct binder_node *binder_context_mgr_node;
@@ -368,6 +369,8 @@ struct binder_ref {* @freeze_wait: waitqueue of processes waiting for all outstanding * transactions to be processed * (protected by @inner_lock) +* @dmap dbitmap to manage available reference descriptors +* (protected by @outer_lock) * @todo: list of work for this process * (protected by @inner_lock) * @stats: per-process binder statistics
@@ -417,7 +420,7 @@ struct binder_proc {bool sync_recv;bool async_recv;wait_queue_head_t freeze_wait; - +struct dbitmap dmap;struct list_head todo;struct binder_stats stats;struct list_head delivered_death;
drivers/android/dbitmap.h new file +176 -0
176 lines not on this page · raw message
Signature · 1 line
2.45.2.505.gda0bf45e8d-goog
…
Quoted 1 line
+++
b/drivers/android/binder.c
…
Quoted 2 lines
drivers/android/binder.c +2
-0+static void try_shrink_dmap (struct binder_proc *proc) +{
…
Quoted 3 lines
drivers/android/binder.c +3
-0+binder_proc_lock (proc); + nbits =dbitmap_shrink_nbits (&proc->dmap); +binder_proc_unlock (proc);
…
drivers/android/binder.c static void binder_free_ref(struct binder_ref *ref) · line 1380
Quoted 5 lines
drivers/android/binder.c +5
-0+ new =bitmap_zalloc (nbits,GFP_KERNEL ); +binder_proc_lock (proc); +dbitmap_shrink (&proc->dmap, new, nbits); +binder_proc_unlock (proc); +}
…
Would you become interested to apply lock guards?
https://elixir.bootlin.com/linux/v6.10-rc3/source/include/linux/cleanup.h#L124
Regards,
Markus
Greg Kroah-Hartman
maintainerQuoted 17 lines · Markus Elfring
…
Quoted 1 line
+++
b/drivers/android/binder.c…
Quoted 2 lines
drivers/android/binder.c +2
-0+static void try_shrink_dmap (struct binder_proc *proc) +{…
Quoted 3 lines
drivers/android/binder.c +3
-0+binder_proc_lock (proc); + nbits =dbitmap_shrink_nbits (&proc->dmap); +binder_proc_unlock (proc);…
Quoted 5 lines
drivers/android/binder.c +5
-0+ new =bitmap_zalloc (nbits,GFP_KERNEL ); +binder_proc_lock (proc); +dbitmap_shrink (&proc->dmap, new, nbits); +binder_proc_unlock (proc); +}…
Quoted 2 lines
Would you become interested to apply lock guards?
https://elixir.bootlin.com/linux/v6.10-rc3/source/include/linux/cleanup.h#L124
Hi,
This is the semi-friendly patch-bot of Greg Kroah-Hartman.
Markus, you seem to have sent a nonsensical or otherwise pointless review comment to a patch submission on a Linux kernel developer mailing list. I strongly suggest that you not do this anymore. Please do not bother developers who are actively working to produce patches and features with comments that, in the end, are a waste of time.
Patch submitter, please ignore Markus's suggestion; you do not need to follow it at all. The person/bot/AI that sent it is being ignored by almost all Linux kernel maintainers for having a persistent pattern of behavior of producing distracting and pointless commentary, and inability to adapt to feedback. Please feel free to also ignore emails from them.
thanks,
greg k-h's patch email bot