Received-SPF: pass (google.com: domain of linux-kernel+bounces-181715-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) client-ip=147.75.80.249;
Date: Fri, 17 May 2024 03:24:13 +0000
From: Carlos Llamas <cmllamas@google.com>
To: Alice Ryhl <aliceryhl@google.com>
Cc: Christophe JAILLET <christophe.jaillet@wanadoo.fr>,
	Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
	Arve =?iso-8859-1?B?SGr4bm5lduVn?= <arve@android.com>,
	Todd Kjos <tkjos@android.com>, Martijn Coenen <maco@android.com>,
	Joel Fernandes <joel@joelfernandes.org>,
	Christian Brauner <brauner@kernel.org>,
	Suren Baghdasaryan <surenb@google.com>,
	linux-kernel@vger.kernel.org, kernel-team@android.com,
	Tim Murray <timmurray@google.com>, John Stultz <jstultz@google.com>,
	Steven Moreland <smoreland@google.com>,
	Nick Chen <chenjia3@oppo.com>
Subject: Re: [PATCH v3] binder: use bitmap for faster descriptor lookup
Message-ID: <ZkbN3f8cGu4QPknY@google.com>
References: <20240516133952.4072309-1-cmllamas@google.com>
 <CAH5fLgjP8eozdA3wSari2LHyVUzaOMNTU12JWb2rzGgy9RRpsg@mail.gmail.com>
Precedence: bulk
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <CAH5fLgjP8eozdA3wSari2LHyVUzaOMNTU12JWb2rzGgy9RRpsg@mail.gmail.com>

On Thu, May 16, 2024 at 04:10:40PM +0200, Alice Ryhl wrote:
> On Thu, May 16, 2024 at 3:39 PM Carlos Llamas <cmllamas@google.com> wrote:
> >
> > 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.
> >
> > Link: https://lore.kernel.org/all/20240417191418.1341988-1-cmllamas@google.com/ [1]
> > Cc: Tim Murray <timmurray@google.com>
> > Cc: Arve Hjønnevåg <arve@android.com>
> > Cc: Alice Ryhl <aliceryhl@google.com>
> > Cc: Martijn Coenen <maco@android.com>
> > Cc: Todd Kjos <tkjos@android.com>
> > Cc: John Stultz <jstultz@google.com>
> > Cc: Steven Moreland <smoreland@google.com>
> > Suggested-by: Nick Chen <chenjia3@oppo.com>
> > Signed-off-by: Carlos Llamas <cmllamas@google.com>
> 
> LGTM. One nit below, but it's not a correctness issue.
> 
> Reviewed-by: Alice Ryhl <aliceryhl@google.com>
> 
> > +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
> `<=`.

True, the range goes [0...n-1] so it should be "bit < n". Let me fix
that. Thanks.

> 
> Alice