[RFC 04/10] lib/tida.c: a very simple integer id allocator

[Rasmus Villemoes <linux@rasmusvillemoes.dk>]

The idr-based id allocator ida has a rather large memory footprint
(despite claims to the contrary). For example, on my laptop, each of
the six idas associated to the workqueues uses more than 16 KB of
memory (most of which sits unused in the embedded idr structure), even
though _combined_ they have only handed out a little over 100 ids in
their lifetime. That's about 1KB of overhead per id, which is rather
far from "each id only occupies a bit".

This introduces tida (t for tiny, trivial, whatever). Initially we
only support allocating the smallest available id, but this can
already replace many uses of ida throughout the tree.

It shouldn't be that hard to implement e.g. tida_get_min() or
tida_get_exact() which might make this capable of replacing more ida
instances.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 include/linux/tida.h |  26 +++++++++++++
 lib/Makefile         |   2 +-
 lib/tida.c           | 103 +++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 130 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/tida.h
 create mode 100644 lib/tida.c

diff --git a/include/linux/tida.h b/include/linux/tida.h
new file mode 100644
index 000000000000..9aa3ad96a632
--- /dev/null
+++ b/include/linux/tida.h
@@ -0,0 +1,26 @@
+#ifndef __LINUX_TIDA_H__
+#define __LINUX_TIDA_H__
+
+#include <linux/types.h>
+#include <linux/spinlock.h>
+
+struct tida {
+	unsigned long	*bits;
+	unsigned long	alloc;
+	spinlock_t	lock;
+	int		hint;
+};
+
+#define TIDA_INIT(name)				\
+	{ .lock = __SPIN_LOCK_UNLOCKED(name.lock), }
+
+#define DEFINE_TIDA(name) struct tida name = TIDA_INIT(name)
+
+void tida_init(struct tida *tida);
+void tida_destroy(struct tida *tida);
+
+int tida_get(struct tida *tida, gfp_t gfp);
+void tida_put(struct tida *tida, int id);
+
+
+#endif /* __LINUX_TIDA_H__ */
diff --git a/lib/Makefile b/lib/Makefile
index 50144a3aeebd..e6f5b9896bbd 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -18,7 +18,7 @@ KCOV_INSTRUMENT_dynamic_debug.o := n
 
 lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 rbtree.o radix-tree.o dump_stack.o timerqueue.o\
-	 idr.o int_sqrt.o extable.o \
+	 idr.o int_sqrt.o extable.o tida.o \
 	 sha1.o chacha20.o md5.o irq_regs.o argv_split.o \
 	 flex_proportions.o ratelimit.o show_mem.o \
 	 is_single_threaded.o plist.o decompress.o kobject_uevent.o \
diff --git a/lib/tida.c b/lib/tida.c
new file mode 100644
index 000000000000..1ea0deb6fa64
--- /dev/null
+++ b/lib/tida.c
@@ -0,0 +1,103 @@
+#include <linux/bitmap.h>
+#include <linux/bitops.h>
+#include <linux/export.h>
+#include <linux/kernel.h>
+#include <linux/slab.h>
+#include <linux/string.h>
+#include <linux/tida.h>
+
+/*
+ * An extremely simple integer id allocator with small memory
+ * footprint, mostly useful for cases where up to a few hundred ids
+ * get allocated.
+ *
+ * Note that the backing bitmap is never shrunk.
+ */
+
+/*
+ * Invariant:
+ *
+ *   0 <= tida->hint
+ *     <= find_next_zero_bit(tida->bits, tida->alloc, 0)
+ *     <= tida->alloc.
+ */
+
+static int
+tida_expand(struct tida *tida, gfp_t gfp, unsigned long *flags)
+	__releases(tida->lock)
+	__acquires(tida->lock)
+{
+	unsigned long newalloc, oldalloc = tida->alloc;
+	unsigned long *bits;
+
+	newalloc = oldalloc ? 2 * oldalloc : BITS_PER_LONG;
+
+	spin_unlock_irqrestore(&tida->lock, *flags);
+	bits = kcalloc(BITS_TO_LONGS(newalloc), sizeof(*bits), gfp);
+	spin_lock_irqsave(&tida->lock, *flags);
+
+	if (!bits)
+		return -ENOMEM;
+
+	if (tida->alloc < newalloc) {
+		memcpy(bits, tida->bits, tida->alloc/8);
+		tida->alloc = newalloc;
+		swap(tida->bits, bits);
+	}
+	kfree(bits);
+
+	return 0;
+}
+
+int
+tida_get(struct tida *tida, gfp_t gfp)
+{
+	unsigned long flags;
+	int ret;
+
+	spin_lock_irqsave(&tida->lock, flags);
+	while (1) {
+		/* find_next_zero_bit is fine with a NULL bitmap as long as size is 0 */
+		ret = find_next_zero_bit(tida->bits, tida->alloc, tida->hint);
+		if (ret < tida->alloc)
+			break;
+		ret = tida_expand(tida, gfp, &flags);
+		if (ret < 0)
+			goto out;
+	}
+
+	__set_bit(ret, tida->bits);
+	tida->hint = ret+1;
+out:
+	spin_unlock_irqrestore(&tida->lock, flags);
+	return ret;
+}
+EXPORT_SYMBOL_GPL(tida_get);
+
+void
+tida_put(struct tida *tida, int id)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&tida->lock, flags);
+	__clear_bit(id, tida->bits);
+	if (id < tida->hint)
+		tida->hint = id;
+	spin_unlock_irqrestore(&tida->lock, flags);
+}
+EXPORT_SYMBOL_GPL(tida_put);
+
+void
+tida_init(struct tida *tida)
+{
+	memset(tida, 0, sizeof(*tida));
+	spin_lock_init(&tida->lock);
+}
+EXPORT_SYMBOL_GPL(tida_init);
+
+void
+tida_destroy(struct tida *tida)
+{
+	kfree(tida->bits);
+}
+EXPORT_SYMBOL_GPL(tida_destroy);
-- 
2.1.4