[PATCH 01/13] duplicate idr code

From: Nadia . Derbey
Date: Fri Apr 11 2008 - 12:20:46 EST


[PATCH 01/13]

This patch duplicates idr.c and idr.h, only changing the routines and
structures names where needed.

Signed-off-by: Nadia Derbey <Nadia.Derbey@xxxxxxxx>

---
include/linux/ridr.h | 58 +++++++
lib/ridr.c | 386 +++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 444 insertions(+)

Index: linux-2.6.25-rc8-mm1/include/linux/ridr.h
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6.25-rc8-mm1/include/linux/ridr.h 2008-04-11 17:17:41.000000000 +0200
@@ -0,0 +1,58 @@
+/*
+ * include/linux/ridr.h
+ *
+ * Small id to pointer translation service avoiding fixed sized
+ * tables. RCU-based implmentation of IDRs.
+ */
+
+#ifndef _RIDR_H_
+#define _RIDR_H_
+
+#include <linux/idr.h>
+
+struct ridr_layer {
+ unsigned long bitmap; /* A zero bit means "space here" */
+ struct ridr_layer *ary[1<<IDR_BITS];
+ int count; /* When zero, we can release it */
+};
+
+struct ridr {
+ struct ridr_layer *top;
+ struct ridr_layer *id_free;
+ int layers;
+ int id_free_cnt;
+ spinlock_t lock;
+};
+
+#define RIDR_INIT(name) \
+{ \
+ .top = NULL, \
+ .id_free = NULL, \
+ .layers = 0, \
+ .id_free_cnt = 0, \
+ .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
+}
+#define DEFINE_RIDR(name) struct ridr name = RIDR_INIT(name)
+
+#define INIT_RIDR(name) \
+do { \
+ (name)->top = NULL; \
+ (name)->id_free = NULL; \
+ (name)->layers = 0; \
+ (name)->id_free_cnt = 0; \
+ (name)->lock = __SPIN_LOCK_UNLOCKED(name.lock); \
+} while (0)
+
+
+/*
+ * This is what we export.
+ */
+
+void *ridr_find(struct ridr *idp, int id);
+int ridr_pre_get(struct ridr *idp, gfp_t gfp_mask);
+int ridr_get_new(struct ridr *idp, void *ptr, int *id);
+void ridr_remove(struct ridr *idp, int id);
+
+void __init ridr_init_cache(void);
+
+#endif /* _RIDR_H_ */
Index: linux-2.6.25-rc8-mm1/lib/ridr.c
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6.25-rc8-mm1/lib/ridr.c 2008-04-11 17:30:28.000000000 +0200
@@ -0,0 +1,386 @@
+/*
+ * RCU-based idr API
+ */
+
+#ifndef TEST /* to test in user space... */
+#include <linux/slab.h>
+#include <linux/init.h>
+#include <linux/module.h>
+#endif
+#include <linux/err.h>
+#include <linux/string.h>
+#include <linux/ridr.h>
+
+static struct kmem_cache *ridr_layer_cache;
+
+static struct ridr_layer *alloc_layer(struct ridr *idp)
+{
+ struct ridr_layer *p;
+ unsigned long flags;
+
+ spin_lock_irqsave(&idp->lock, flags);
+ p = idp->id_free;
+ if (p) {
+ idp->id_free = p->ary[0];
+ idp->id_free_cnt--;
+ p->ary[0] = NULL;
+ }
+ spin_unlock_irqrestore(&idp->lock, flags);
+ return(p);
+}
+
+/* only called when idp->lock is held */
+static void __free_layer(struct ridr *idp, struct ridr_layer *p)
+{
+ p->ary[0] = idp->id_free;
+ idp->id_free = p;
+ idp->id_free_cnt++;
+}
+
+static void free_layer(struct ridr *idp, struct ridr_layer *p)
+{
+ unsigned long flags;
+
+ /*
+ * Depends on the return element being zeroed.
+ */
+ spin_lock_irqsave(&idp->lock, flags);
+ __free_layer(idp, p);
+ spin_unlock_irqrestore(&idp->lock, flags);
+}
+
+static void ridr_mark_full(struct ridr_layer **pa, int id)
+{
+ struct ridr_layer *p = pa[0];
+ int l = 0;
+
+ __set_bit(id & IDR_MASK, &p->bitmap);
+ /*
+ * If this layer is full mark the bit in the layer above to
+ * show that this part of the radix tree is full. This may
+ * complete the layer above and require walking up the radix
+ * tree.
+ */
+ while (p->bitmap == IDR_FULL) {
+ p = pa[++l];
+ if (!p)
+ break;
+ id = id >> IDR_BITS;
+ __set_bit((id & IDR_MASK), &p->bitmap);
+ }
+}
+
+/**
+ * ridr_pre_get - reserver resources for ridr allocation
+ * @idp: ridr handle
+ * @gfp_mask: memory allocation flags
+ *
+ * This function should be called prior to locking and calling the
+ * following function. It preallocates enough memory to satisfy
+ * the worst possible allocation.
+ *
+ * If the system is REALLY out of memory this function returns 0,
+ * otherwise 1.
+ */
+int ridr_pre_get(struct ridr *idp, gfp_t gfp_mask)
+{
+ while (idp->id_free_cnt < IDR_FREE_MAX) {
+ struct ridr_layer *new;
+ new = kmem_cache_alloc(ridr_layer_cache, gfp_mask);
+ if (new == NULL)
+ return (0);
+ free_layer(idp, new);
+ }
+ return 1;
+}
+EXPORT_SYMBOL(ridr_pre_get);
+
+static int sub_alloc(struct ridr *idp, int *starting_id,
+ struct ridr_layer **pa)
+{
+ int n, m, sh;
+ struct ridr_layer *p, *new;
+ int l, id, oid;
+ unsigned long bm;
+
+ id = *starting_id;
+ restart:
+ p = idp->top;
+ l = idp->layers;
+ pa[l--] = NULL;
+ while (1) {
+ /*
+ * We run around this while until we reach the leaf node...
+ */
+ n = (id >> (IDR_BITS*l)) & IDR_MASK;
+ bm = ~p->bitmap;
+ m = find_next_bit(&bm, IDR_SIZE, n);
+ if (m == IDR_SIZE) {
+ /* no space available go back to previous layer. */
+ l++;
+ oid = id;
+ id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
+
+ /* if already at the top layer, we need to grow */
+ p = pa[l];
+ if (!p) {
+ *starting_id = id;
+ return -2;
+ }
+
+ /* If we need to go up one layer, continue the
+ * loop; otherwise, restart from the top.
+ */
+ sh = IDR_BITS * (l + 1);
+ if (oid >> sh == id >> sh)
+ continue;
+ else
+ goto restart;
+ }
+ if (m != n) {
+ sh = IDR_BITS*l;
+ id = ((id >> sh) ^ n ^ m) << sh;
+ }
+ if ((id >= MAX_ID_BIT) || (id < 0))
+ return -3;
+ if (l == 0)
+ break;
+ /*
+ * Create the layer below if it is missing.
+ */
+ if (!p->ary[m]) {
+ new = alloc_layer(idp);
+ if (!new)
+ return -1;
+ p->ary[m] = new;
+ p->count++;
+ }
+ pa[l--] = p;
+ p = p->ary[m];
+ }
+
+ pa[l] = p;
+ return id;
+}
+
+static int ridr_get_empty_slot(struct ridr *idp, int starting_id,
+ struct ridr_layer **pa)
+{
+ struct ridr_layer *p, *new;
+ int layers, v, id;
+ unsigned long flags;
+
+ id = starting_id;
+build_up:
+ p = idp->top;
+ layers = idp->layers;
+ if (unlikely(!p)) {
+ p = alloc_layer(idp);
+ if (!p)
+ return -1;
+ layers = 1;
+ }
+ /*
+ * Add a new layer to the top of the tree if the requested
+ * id is larger than the currently allocated space.
+ */
+ while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
+ layers++;
+ if (!p->count)
+ continue;
+ new = alloc_layer(idp);
+ if (!new) {
+ /*
+ * The allocation failed. If we built part of
+ * the structure tear it down.
+ */
+ spin_lock_irqsave(&idp->lock, flags);
+ for (new = p; p && p != idp->top; new = p) {
+ p = p->ary[0];
+ new->ary[0] = NULL;
+ new->bitmap = new->count = 0;
+ __free_layer(idp, new);
+ }
+ spin_unlock_irqrestore(&idp->lock, flags);
+ return -1;
+ }
+ new->ary[0] = p;
+ new->count = 1;
+ if (p->bitmap == IDR_FULL)
+ __set_bit(0, &new->bitmap);
+ p = new;
+ }
+ idp->top = p;
+ idp->layers = layers;
+ v = sub_alloc(idp, &id, pa);
+ if (v == -2)
+ goto build_up;
+ return(v);
+}
+
+static int ridr_get_new_above_int(struct ridr *idp, void *ptr, int starting_id)
+{
+ struct ridr_layer *pa[MAX_LEVEL];
+ int id;
+
+ id = ridr_get_empty_slot(idp, starting_id, pa);
+ if (id >= 0) {
+ /*
+ * Successfully found an empty slot. Install the user
+ * pointer and mark the slot full.
+ */
+ pa[0]->ary[id & IDR_MASK] = (struct ridr_layer *)ptr;
+ pa[0]->count++;
+ ridr_mark_full(pa, id);
+ }
+
+ return id;
+}
+
+/**
+ * ridr_get_new - allocate new ridr entry
+ * @idp: ridr handle
+ * @ptr: pointer you want associated with the ide
+ * @id: pointer to the allocated handle
+ *
+ * This is the allocate id function. It should be called with any
+ * required locks.
+ *
+ * If memory is required, it will return -EAGAIN, you should unlock
+ * and go back to the ridr_pre_get() call. If the ridr is full, it will
+ * return -ENOSPC.
+ *
+ * @id returns a value in the range 0 ... 0x7fffffff
+ */
+int ridr_get_new(struct ridr *idp, void *ptr, int *id)
+{
+ int rv;
+
+ rv = ridr_get_new_above_int(idp, ptr, 0);
+ /*
+ * This is a cheap hack until the IDR code can be fixed to
+ * return proper error values.
+ */
+ if (rv < 0) {
+ if (rv == -1)
+ return -EAGAIN;
+ else /* Will be -3 */
+ return -ENOSPC;
+ }
+ *id = rv;
+ return 0;
+}
+EXPORT_SYMBOL(ridr_get_new);
+
+static void ridr_remove_warning(int id)
+{
+ printk("ridr_remove called for id=%d which is not allocated.\n", id);
+ dump_stack();
+}
+
+static void sub_remove(struct ridr *idp, int shift, int id)
+{
+ struct ridr_layer *p = idp->top;
+ struct ridr_layer **pa[MAX_LEVEL];
+ struct ridr_layer ***paa = &pa[0];
+ int n;
+
+ *paa = NULL;
+ *++paa = &idp->top;
+
+ while ((shift > 0) && p) {
+ n = (id >> shift) & IDR_MASK;
+ __clear_bit(n, &p->bitmap);
+ *++paa = &p->ary[n];
+ p = p->ary[n];
+ shift -= IDR_BITS;
+ }
+ n = id & IDR_MASK;
+ if (likely(p != NULL && test_bit(n, &p->bitmap))) {
+ __clear_bit(n, &p->bitmap);
+ p->ary[n] = NULL;
+ while (*paa && !--((**paa)->count)) {
+ free_layer(idp, **paa);
+ **paa-- = NULL;
+ }
+ if (!*paa)
+ idp->layers = 0;
+ } else
+ ridr_remove_warning(id);
+}
+
+/**
+ * ridr_remove - remove the given id and free it's slot
+ * @idp: ridr handle
+ * @id: unique key
+ */
+void ridr_remove(struct ridr *idp, int id)
+{
+ struct ridr_layer *p;
+
+ /* Mask off upper bits we don't use for the search. */
+ id &= MAX_ID_MASK;
+
+ sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
+ if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
+ idp->top->ary[0]) { /* We can drop a layer */
+
+ p = idp->top->ary[0];
+ idp->top->bitmap = idp->top->count = 0;
+ free_layer(idp, idp->top);
+ idp->top = p;
+ --idp->layers;
+ }
+ while (idp->id_free_cnt >= IDR_FREE_MAX) {
+ p = alloc_layer(idp);
+ kmem_cache_free(ridr_layer_cache, p);
+ return;
+ }
+}
+EXPORT_SYMBOL(ridr_remove);
+
+/**
+ * ridr_find - return pointer for given id
+ * @idp: ridr handle
+ * @id: lookup key
+ *
+ * Return the pointer given the id it has been registered with. A %NULL
+ * return indicates that @id is not valid or you passed %NULL in
+ * ridr_get_new().
+ *
+ * The caller must serialize ridr_find() vs ridr_get_new() and ridr_remove().
+ */
+void *ridr_find(struct ridr *idp, int id)
+{
+ int n;
+ struct ridr_layer *p;
+
+ n = idp->layers * IDR_BITS;
+ p = idp->top;
+
+ /* Mask off upper bits we don't use for the search. */
+ id &= MAX_ID_MASK;
+
+ if (id >= (1 << n))
+ return NULL;
+
+ while (n > 0 && p) {
+ n -= IDR_BITS;
+ p = p->ary[(id >> n) & IDR_MASK];
+ }
+ return((void *)p);
+}
+EXPORT_SYMBOL(ridr_find);
+
+static void ridr_cache_ctor(struct kmem_cache *ridr_layer_cache,
+ void *ridr_layer)
+{
+ memset(ridr_layer, 0, sizeof(struct ridr_layer));
+}
+
+void __init ridr_init_cache(void)
+{
+ ridr_layer_cache = kmem_cache_create("ridr_layer_cache",
+ sizeof(struct ridr_layer), 0, SLAB_PANIC,
+ ridr_cache_ctor);
+}

--
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/