Merge tag 'char-misc-6.11-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/char-misc

Pull char / misc and other driver updates from Greg KH:
 "Here is the "big" set of char/misc and other driver subsystem changes
  for 6.11-rc1. Nothing major in here, just loads of new drivers and
  updates. Included in here are:

   - IIO api updates and new drivers added

   - wait_interruptable_timeout() api cleanups for some drivers

   - MODULE_DESCRIPTION() additions for loads of drivers

   - parport out-of-bounds fix

   - interconnect driver updates and additions

   - mhi driver updates and additions

   - w1 driver fixes

   - binder speedups and fixes

   - eeprom driver updates

   - coresight driver updates

   - counter driver update

   - new misc driver additions

   - other minor api updates

  All of these, EXCEPT for the final Kconfig build fix for 32bit
  systems, have been in linux-next for a while with no reported issues.
  The Kconfig fixup went in 29 hours ago, so might have missed the
  latest linux-next, but was acked by everyone involved"

* tag 'char-misc-6.11-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/char-misc: (330 commits)
  misc: Kconfig: exclude mrvl-cn10k-dpi compilation for 32-bit systems
  misc: delete Makefile.rej
  binder: fix hang of unregistered readers
  misc: Kconfig: add a new dependency for MARVELL_CN10K_DPI
  virtio: add missing MODULE_DESCRIPTION() macro
  agp: uninorth: add missing MODULE_DESCRIPTION() macro
  spmi: add missing MODULE_DESCRIPTION() macros
  dev/parport: fix the array out-of-bounds risk
  samples: configfs: add missing MODULE_DESCRIPTION() macro
  misc: mrvl-cn10k-dpi: add Octeon CN10K DPI administrative driver
  misc: keba: Fix missing AUXILIARY_BUS dependency
  slimbus: Fix struct and documentation alignment in stream.c
  MAINTAINERS: CC dri-devel list on Qualcomm FastRPC patches
  misc: fastrpc: use coherent pool for untranslated Compute Banks
  misc: fastrpc: support complete DMA pool access to the DSP
  misc: fastrpc: add missing MODULE_DESCRIPTION() macro
  misc: fastrpc: Add missing dev_err newlines
  misc: fastrpc: Use memdup_user()
  nvmem: core: Implement force_ro sysfs attribute
  nvmem: Use sysfs_emit() for type attribute
  ...

1 files changed, 176 insertions, 0 deletions

diff --git a/drivers/android/dbitmap.h b/drivers/android/dbitmap.h
new file mode 100644
index 000000000000..b8ac7b4764fd
--- /dev/null
+++ b/drivers/android/dbitmap.h
@@ -0,0 +1,176 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+/*
+ * Copyright 2024 Google LLC
+ *
+ * dbitmap - dynamically sized bitmap library.
+ *
+ * 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.
+ *
+ * A dbitmap can grow or shrink as needed. This part has been designed
+ * considering that users might need to briefly release their locks in
+ * order to allocate memory for the new bitmap. These operations then,
+ * are verified to determine if the grow or shrink is sill valid.
+ *
+ * This library does not provide protection against concurrent access
+ * by itself. Binder uses the proc->outer_lock for this purpose.
+ */
+
+#ifndef _LINUX_DBITMAP_H
+#define _LINUX_DBITMAP_H
+#include <linux/bitmap.h>
+
+#define NBITS_MIN	BITS_PER_TYPE(unsigned long)
+
+struct dbitmap {
+	unsigned int nbits;
+	unsigned long *map;
+};
+
+static inline int dbitmap_enabled(struct dbitmap *dmap)
+{
+	return !!dmap->nbits;
+}
+
+static inline void dbitmap_free(struct dbitmap *dmap)
+{
+	dmap->nbits = 0;
+	kfree(dmap->map);
+}
+
+/* Returns the nbits that a dbitmap can shrink to, 0 if not possible. */
+static inline unsigned int dbitmap_shrink_nbits(struct dbitmap *dmap)
+{
+	unsigned int bit;
+
+	if (dmap->nbits <= NBITS_MIN)
+		return 0;
+
+	/*
+	 * Determine if the bitmap can shrink based on the position of
+	 * its last set bit. If the bit is within the first quarter of
+	 * the bitmap then shrinking is possible. In this case, the
+	 * bitmap should shrink to half its current size.
+	 */
+	bit = find_last_bit(dmap->map, dmap->nbits);
+	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.
+	 */
+	if (bit == dmap->nbits)
+		return NBITS_MIN;
+
+	return 0;
+}
+
+/* Replace the internal bitmap with a new one of different size */
+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 (!new)
+		return;
+
+	/*
+	 * Verify that shrinking to @nbits is still possible. The @new
+	 * bitmap might have been allocated without locks, so this call
+	 * could now be outdated. In this case, free @new and move on.
+	 */
+	if (!dbitmap_enabled(dmap) || dbitmap_shrink_nbits(dmap) != nbits) {
+		kfree(new);
+		return;
+	}
+
+	dbitmap_replace(dmap, new, nbits);
+}
+
+/* Returns the nbits that a dbitmap can grow to. */
+static inline unsigned int dbitmap_grow_nbits(struct dbitmap *dmap)
+{
+	return dmap->nbits << 1;
+}
+
+static inline void
+dbitmap_grow(struct dbitmap *dmap, unsigned long *new, unsigned int nbits)
+{
+	/*
+	 * Verify that growing to @nbits is still possible. The @new
+	 * bitmap might have been allocated without locks, so this call
+	 * could now be outdated. In this case, free @new and move on.
+	 */
+	if (!dbitmap_enabled(dmap) || nbits <= dmap->nbits) {
+		kfree(new);
+		return;
+	}
+
+	/*
+	 * Check for ENOMEM after confirming the grow operation is still
+	 * required. This ensures we only disable the dbitmap when it's
+	 * necessary. Once the dbitmap is disabled, binder will fallback
+	 * to slow_desc_lookup_olocked().
+	 */
+	if (!new) {
+		dbitmap_free(dmap);
+		return;
+	}
+
+	dbitmap_replace(dmap, new, nbits);
+}
+
+/*
+ * Finds and sets the first 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)
+{
+	unsigned long n;
+
+	n = find_first_zero_bit(dmap->map, dmap->nbits);
+	if (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)
+{
+	/* BIT(0) should always set for the context manager */
+	if (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;
+	/* BIT(0) is reserved for the context manager */
+	set_bit(0, dmap->map);
+
+	return 0;
+}
+#endif