Re: [PATCH] binder: fix descriptor lookup for context manager

[Todd Kjos]

On Mon, Jul 15, 2024 at 9:29 PM Carlos Llamas <cmllamas@xxxxxxxxxx> wrote:
>
> In commit 15d9da3f818c ("binder: use bitmap for faster descriptor
> lookup"), it was incorrectly assumed that references to the context
> manager node should always get descriptor zero assigned to them.
>
> However, if the context manager dies and a new process takes its place,
> then assigning descriptor zero to the new context manager might lead to
> collisions, as there could still be references to the older node. This
> issue was reported by syzbot with the following trace:
>
>   kernel BUG at drivers/android/binder.c:1173!
>   Internal error: Oops - BUG: 00000000f2000800 [#1] PREEMPT SMP
>   Modules linked in:
>   CPU: 1 PID: 447 Comm: binder-util Not tainted 6.10.0-rc6-00348-g31643d84b8c3 #10
>   Hardware name: linux,dummy-virt (DT)
>   pstate: 60000005 (nZCv daif -PAN -UAO -TCO -DIT -SSBS BTYPE=--)
>   pc : binder_inc_ref_for_node+0x500/0x544
>   lr : binder_inc_ref_for_node+0x1e4/0x544
>   sp : ffff80008112b940
>   x29: ffff80008112b940 x28: ffff0e0e40310780 x27: 0000000000000000
>   x26: 0000000000000001 x25: ffff0e0e40310738 x24: ffff0e0e4089ba34
>   x23: ffff0e0e40310b00 x22: ffff80008112bb50 x21: ffffaf7b8f246970
>   x20: ffffaf7b8f773f08 x19: ffff0e0e4089b800 x18: 0000000000000000
>   x17: 0000000000000000 x16: 0000000000000000 x15: 000000002de4aa60
>   x14: 0000000000000000 x13: 2de4acf000000000 x12: 0000000000000020
>   x11: 0000000000000018 x10: 0000000000000020 x9 : ffffaf7b90601000
>   x8 : ffff0e0e48739140 x7 : 0000000000000000 x6 : 000000000000003f
>   x5 : ffff0e0e40310b28 x4 : 0000000000000000 x3 : ffff0e0e40310720
>   x2 : ffff0e0e40310728 x1 : 0000000000000000 x0 : ffff0e0e40310710
>   Call trace:
>    binder_inc_ref_for_node+0x500/0x544
>    binder_transaction+0xf68/0x2620
>    binder_thread_write+0x5bc/0x139c
>    binder_ioctl+0xef4/0x10c8
>   [...]
>
> This patch adds back the previous behavior of assigning the next
> non-zero descriptor if references to previous context managers still
> exist. It amends both strategies, the newer dbitmap code and also the
> legacy slow_desc_lookup_olocked(), by allowing them to start looking
> for available descriptors at a given offset.
>
> Fixes: 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
> Cc: stable@xxxxxxxxxxxxxxx
> Reported-and-tested-by: syzbot+3dae065ca76952a67257@xxxxxxxxxxxxxxxxxxxxxxxxx
> Closes: https://lore.kernel.org/all/000000000000c1c0a0061d1e6979@xxxxxxxxxx/
> Signed-off-by: Carlos Llamas <cmllamas@xxxxxxxxxx>
> ---
>  drivers/android/binder.c  | 15 ++++++---------
>  drivers/android/dbitmap.h | 16 ++++++----------
>  2 files changed, 12 insertions(+), 19 deletions(-)
>
> diff --git a/drivers/android/binder.c b/drivers/android/binder.c
> index f26286e3713e..905290c98c3c 100644
> --- a/drivers/android/binder.c
> +++ b/drivers/android/binder.c
> @@ -1044,13 +1044,13 @@ static struct binder_ref *binder_get_ref_olocked(struct binder_proc *proc,
>  }
>
>  /* Find the smallest unused descriptor the "slow way" */
> -static u32 slow_desc_lookup_olocked(struct binder_proc *proc)
> +static u32 slow_desc_lookup_olocked(struct binder_proc *proc, u32 offset)
>  {
>         struct binder_ref *ref;
>         struct rb_node *n;
>         u32 desc;
>
> -       desc = 1;
> +       desc = offset;
>         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)
> @@ -1071,21 +1071,18 @@ static int get_ref_desc_olocked(struct binder_proc *proc,
>                                 u32 *desc)
>  {
>         struct dbitmap *dmap = &proc->dmap;
> +       unsigned int nbits, offset;
>         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;
> -       }
> +       offset = (node == proc->context->binder_context_mgr_node) ? 0 : 1;

If context manager doesn't need to be bit 0 anymore, then why do we
bother to prefer bit 0? Does it matter?

It would simplify the code below if the offset is always 0 since you
wouldn't need an offset at all.

>
>         if (!dbitmap_enabled(dmap)) {
> -               *desc = slow_desc_lookup_olocked(proc);
> +               *desc = slow_desc_lookup_olocked(proc, offset);
>                 return 0;
>         }
>
> -       if (dbitmap_acquire_first_zero_bit(dmap, &bit) == 0) {
> +       if (dbitmap_acquire_next_zero_bit(dmap, offset, &bit) == 0) {
>                 *desc = bit;
>                 return 0;
>         }
> diff --git a/drivers/android/dbitmap.h b/drivers/android/dbitmap.h
> index b8ac7b4764fd..1d58c2e7abd6 100644
> --- a/drivers/android/dbitmap.h
> +++ b/drivers/android/dbitmap.h
> @@ -6,8 +6,7 @@
>   *
>   * Used by the binder driver to optimize the allocation of the smallest
>   * available descriptor ID. Each bit in the bitmap represents the state
> - * of an ID, with the exception of BIT(0) which is used exclusively to
> - * reference binder's context manager.
> + * of an ID.
>   *
>   * A dbitmap can grow or shrink as needed. This part has been designed
>   * considering that users might need to briefly release their locks in
> @@ -132,16 +131,17 @@ dbitmap_grow(struct dbitmap *dmap, unsigned long *new, unsigned int nbits)
>  }
>
>  /*
> - * Finds and sets the first zero bit in the bitmap. Upon success @bit
> + * Finds and sets the next zero bit in the bitmap. Upon success @bit
>   * is populated with the index and 0 is returned. Otherwise, -ENOSPC
>   * is returned to indicate that a dbitmap_grow() is needed.
>   */
>  static inline int
> -dbitmap_acquire_first_zero_bit(struct dbitmap *dmap, unsigned long *bit)
> +dbitmap_acquire_next_zero_bit(struct dbitmap *dmap, unsigned long offset,
> +                             unsigned long *bit)
>  {
>         unsigned long n;
>
> -       n = find_first_zero_bit(dmap->map, dmap->nbits);
> +       n = find_next_zero_bit(dmap->map, dmap->nbits, offset);
>         if (n == dmap->nbits)
>                 return -ENOSPC;
>
> @@ -154,9 +154,7 @@ dbitmap_acquire_first_zero_bit(struct dbitmap *dmap, unsigned long *bit)
>  static inline void
>  dbitmap_clear_bit(struct dbitmap *dmap, unsigned long bit)
>  {
> -       /* BIT(0) should always set for the context manager */
> -       if (bit)
> -               clear_bit(bit, dmap->map);
> +       clear_bit(bit, dmap->map);
>  }
>
>  static inline int dbitmap_init(struct dbitmap *dmap)
> @@ -168,8 +166,6 @@ static inline int dbitmap_init(struct dbitmap *dmap)
>         }
>
>         dmap->nbits = NBITS_MIN;
> -       /* BIT(0) is reserved for the context manager */
> -       set_bit(0, dmap->map);
>
>         return 0;
>  }
> --
> 2.45.2.993.g49e7a77208-goog
>