[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <2024060442-fedora-maybe-e857@gregkh>
Date: Tue, 4 Jun 2024 16:06:16 +0200
From: Greg Kroah-Hartman <gregkh@...uxfoundation.org>
To: Carlos Llamas <cmllamas@...gle.com>
Cc: Alice Ryhl <aliceryhl@...gle.com>,
Arve Hjønnevåg <arve@...roid.com>,
Todd Kjos <tkjos@...roid.com>, Martijn Coenen <maco@...roid.com>,
Joel Fernandes <joel@...lfernandes.org>,
Christian Brauner <brauner@...nel.org>,
Suren Baghdasaryan <surenb@...gle.com>,
Christophe JAILLET <christophe.jaillet@...adoo.fr>,
linux-kernel@...r.kernel.org, kernel-team@...roid.com,
Tim Murray <timmurray@...gle.com>, John Stultz <jstultz@...gle.com>,
Steven Moreland <smoreland@...gle.com>,
Nick Chen <chenjia3@...o.com>
Subject: Re: [PATCH v4] binder: use bitmap for faster descriptor lookup
On Fri, May 17, 2024 at 03:28:27AM +0000, Carlos Llamas wrote:
> diff --git a/drivers/android/dbitmap.h b/drivers/android/dbitmap.h
> new file mode 100644
> index 000000000000..2cf470702bbb
> --- /dev/null
> +++ b/drivers/android/dbitmap.h
> @@ -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 :(
> +
> +#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?
> +
> +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?
> +}
> +
> +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;
And these unlikely() markings actually work better than not having them?
Please document that if so.
> +
> + 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;
> +}
> +
> +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.
> +
> + /*
> + * 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)
> +{
> + /*
> + * 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?
> + */
> + 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?
> + 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;
> + 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
Powered by blists - more mailing lists