[PATCH] binder: fix descriptor lookup for context manager

[PATCH] binder: fix descriptor lookup for context manager

[Carlos Llamas]

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@vger.kernel.org
Reported-and-tested-by: syzbot+3dae065ca76952a67257@syzkaller.appspotmail.com
Closes: https://lore.kernel.org/all/000000000000c1c0a0061d1e6979@google.com/
Signed-off-by: Carlos Llamas <cmllamas@google.com>
---
 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 (!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

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

[Todd Kjos]

On Mon, Jul 15, 2024 at 9:29 PM Carlos Llamas <cmllamas@google.com> 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@vger.kernel.org
> Reported-and-tested-by: syzbot+3dae065ca76952a67257@syzkaller.appspotmail.com
> Closes: https://lore.kernel.org/all/000000000000c1c0a0061d1e6979@google.com/
> Signed-off-by: Carlos Llamas <cmllamas@google.com>
> ---
>  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
>

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

[Carlos Llamas]

On Tue, Jul 16, 2024 at 10:40:20AM -0700, Todd Kjos wrote:
> 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.

Yes, it would make things simplier if references to the context manager
could get any descriptor id. However, there seems to be an expectation
from libbinder that this descriptor would be zero. At least according to
some folks more familiar with userspace binder than myself.

I think we can revisit this expectation though and also look closer at
the scenario of a context manager "swap". The procs can still reach the
new context manager using descriptor 0. However, this may cause some
issues with operations with refs such as BC_INCREFS/BC_DECREFS.

AFAICT, the context manager doesn't even need a reference. But while we
dig furhter into this I think the best option is to keep the behavior
the same for now: reserve descriptor zero for the context manager node
unless it's already taken. Changing this is non-trivial IMO.

--
Carlos Llamas

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

[Carlos Llamas]

On Tue, Jul 16, 2024 at 06:48:54PM +0000, Carlos Llamas wrote:
> On Tue, Jul 16, 2024 at 10:40:20AM -0700, Todd Kjos wrote:
> > 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.
> 
> Yes, it would make things simplier if references to the context manager
> could get any descriptor id. However, there seems to be an expectation
> from libbinder that this descriptor would be zero. At least according to
> some folks more familiar with userspace binder than myself.
> 
> I think we can revisit this expectation though and also look closer at
> the scenario of a context manager "swap". The procs can still reach the
> new context manager using descriptor 0. However, this may cause some
> issues with operations with refs such as BC_INCREFS/BC_DECREFS.
> 
> AFAICT, the context manager doesn't even need a reference. But while we
> dig furhter into this I think the best option is to keep the behavior
> the same for now: reserve descriptor zero for the context manager node
> unless it's already taken. Changing this is non-trivial IMO.
> 
> --
> Carlos Llamas

Also, we need to consider that references to regular nodes (not context
manager) cannot get descriptor zero assigned to them for obvious
reasons. So descriptor zero is always reserved for the context manager,
but there might be certain scenarios in which references to the context
manager get a non-zero descriptor.

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

[Alice Ryhl]

On Tue, Jul 16, 2024 at 7:40 PM Todd Kjos <tkjos@google.com> wrote:
>
> On Mon, Jul 15, 2024 at 9:29 PM Carlos Llamas <cmllamas@google.com> wrote:
> >         /* 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.

Userspace assumes that sending a message to handle 0 means that the
current context manager receives it. If we assign anything that is not
the context manager to bit 0, then libbinder will send ctxmgr messages
to random other processes. I don't think libbinder handles the case
where context manager is restarted well at all. Most likely, if we hit
this condition in real life, processes that had a non-zero refcount to
the context manager will lose the ability to interact with ctxmgr
until they are restarted.

I think this patch just needs to make sure that this scenario doesn't
lead to a UAF in the kernel. Ensuring that userspace handles it
gracefully is another matter.

Alice

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

[Carlos Llamas]

On Mon, Jul 22, 2024 at 12:57:31PM +0200, Alice Ryhl wrote:
> On Tue, Jul 16, 2024 at 7:40 PM Todd Kjos <tkjos@google.com> wrote:
> >
> > On Mon, Jul 15, 2024 at 9:29 PM Carlos Llamas <cmllamas@google.com> wrote:
> > >         /* 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.
> 
> Userspace assumes that sending a message to handle 0 means that the
> current context manager receives it. If we assign anything that is not
> the context manager to bit 0, then libbinder will send ctxmgr messages
> to random other processes. I don't think libbinder handles the case
> where context manager is restarted well at all. Most likely, if we hit
> this condition in real life, processes that had a non-zero refcount to
> the context manager will lose the ability to interact with ctxmgr
> until they are restarted.

Using handle 0 for transaction will always reach the current context
manager. This is hardcoded so it works regardless of the descriptor
assigned to any references.

Things get complicated when doing refcount operations though. It seems
that some commands will reach the new context manager and others will
reach the old dead node. Odd.

This needs to the fixed. I'll look into it.

> 
> I think this patch just needs to make sure that this scenario doesn't
> lead to a UAF in the kernel. Ensuring that userspace handles it
> gracefully is another matter.
> 

Right, the main concern in this patch is handling the BUG() assert.

Thanks,
--
Carlos Llamas

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

[Alice Ryhl]

On Tue, Jul 16, 2024 at 6:29 AM Carlos Llamas <cmllamas@google.com> 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@vger.kernel.org
> Reported-and-tested-by: syzbot+3dae065ca76952a67257@syzkaller.appspotmail.com
> Closes: https://lore.kernel.org/all/000000000000c1c0a0061d1e6979@google.com/
> Signed-off-by: Carlos Llamas <cmllamas@google.com>

You are changing dbitmap so that BIT(0) is no longer guaranteed to be
set, so you should update this comment:

         /*
          * Note that find_last_bit() returns dmap->nbits when no bits
          * are set. While this is technically not possible here since
          * BIT(0) is always set, this check is left for extra safety.
          */
         if (bit == dmap->nbits)
                  return NBITS_MIN;

Otherwise LGTM. With the above comment fixed:

Reviewed-by: Alice Ryhl <aliceryhl@google.com>

Alice

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

[Carlos Llamas]

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@vger.kernel.org
Reported-and-tested-by: syzbot+3dae065ca76952a67257@syzkaller.appspotmail.com
Closes: https://lore.kernel.org/all/000000000000c1c0a0061d1e6979@google.com/
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Signed-off-by: Carlos Llamas <cmllamas@google.com>
---
 drivers/android/binder.c  | 15 ++++++---------
 drivers/android/dbitmap.h | 22 +++++++---------------
 2 files changed, 13 insertions(+), 24 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 (!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..956f1bd087d1 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
@@ -58,11 +57,7 @@ static inline unsigned int dbitmap_shrink_nbits(struct dbitmap *dmap)
 	if (bit < (dmap->nbits >> 2))
 		return dmap->nbits >> 1;
 
-	/*
-	 * Note that find_last_bit() returns dmap->nbits when no bits
-	 * are set. While this is technically not possible here since
-	 * BIT(0) is always set, this check is left for extra safety.
-	 */
+	/* find_last_bit() returns dmap->nbits when no bits are set. */
 	if (bit == dmap->nbits)
 		return NBITS_MIN;
 
@@ -132,16 +127,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 +150,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 +162,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.1089.g2a221341d9-goog

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

[Carlos Llamas]

On Mon, Jul 22, 2024 at 03:05:11PM +0000, Carlos Llamas 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@vger.kernel.org
> Reported-and-tested-by: syzbot+3dae065ca76952a67257@syzkaller.appspotmail.com
> Closes: https://lore.kernel.org/all/000000000000c1c0a0061d1e6979@google.com/
> Reviewed-by: Alice Ryhl <aliceryhl@google.com>
> Signed-off-by: Carlos Llamas <cmllamas@google.com>
> ---

Sorry, I forgot to feed --notes to git send-email and the list of
changes in this v2 patch was missed. Here it is:

Notes:
    v2: updated comment about BIT(0) per Alice's feedback
        collect tags