Re: [PATCH v4] binder: use bitmap for faster descriptor lookup

[Greg Kroah-Hartman <gregkh@linuxfoundation.org>]

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