The patch titled
idr: introduce ridr_remove()
has been removed from the -mm tree. Its filename was
idr-introduce-ridr_remove.patch
This patch was dropped because an updated version will be merged
The current -mm tree may be found at http://userweb.kernel.org/~akpm/mmotm/
------------------------------------------------------
Subject: idr: introduce ridr_remove()
From: Nadia Derbey <Nadia.Derbey@xxxxxxxx>
Introduce the ridr_remove() routine.
Signed-off-by: Nadia Derbey <Nadia.Derbey@xxxxxxxx>
Cc: Jim Houston <jim.houston@xxxxxxxxxxx>
Cc: Manfred Spraul <manfred@xxxxxxxxxxxxxxxx>
Cc: "Paul E. McKenney" <paulmck@xxxxxxxxxx>
Cc: Nick Piggin <nickpiggin@xxxxxxxxxxxx>
Cc: Pierre Peiffer <peifferp@xxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
include/linux/idr.h | 1
include/linux/ridr.h | 1
lib/idr.c | 7 +--
lib/ridr.c | 83 +++++++++++++++++++++++++++++++++++++++++
4 files changed, 89 insertions(+), 3 deletions(-)
diff -puN include/linux/idr.h~idr-introduce-ridr_remove include/linux/idr.h
--- a/include/linux/idr.h~idr-introduce-ridr_remove
+++ a/include/linux/idr.h
@@ -91,6 +91,7 @@ static inline void _idr_set_new_slot(str
void _idr_mark_full(struct idr_layer **, int);
int _idr_sub_alloc(int *, int *, struct idr_layer **, struct idr_layer **);
+void _idr_remove_warning(const char *, int);
/*
* This is what we export.
diff -puN include/linux/ridr.h~idr-introduce-ridr_remove include/linux/ridr.h
--- a/include/linux/ridr.h~idr-introduce-ridr_remove
+++ a/include/linux/ridr.h
@@ -63,6 +63,7 @@ void *ridr_find(struct ridr *, int);
int ridr_pre_get(struct ridr *, gfp_t);
int ridr_get_new(struct ridr *, void *, int *);
int ridr_get_new_above(struct ridr *, void *, int, int *);
+void ridr_remove(struct ridr *, int);
void ridr_init(struct ridr *);
diff -puN lib/idr.c~idr-introduce-ridr_remove lib/idr.c
--- a/lib/idr.c~idr-introduce-ridr_remove
+++ a/lib/idr.c
@@ -356,9 +356,10 @@ int idr_get_new(struct idr *idp, void *p
}
EXPORT_SYMBOL(idr_get_new);
-static void idr_remove_warning(int id)
+void _idr_remove_warning(const char *caller, int id)
{
- printk("idr_remove called for id=%d which is not allocated.\n", id);
+ printk(KERN_INFO "%s called for id=%d which is not allocated.\n",
+ caller, id);
dump_stack();
}
@@ -390,7 +391,7 @@ static void sub_remove(struct idr *idp,
if (!*paa)
idp->layers = 0;
} else
- idr_remove_warning(id);
+ _idr_remove_warning("idr_remove", id);
}
/**
diff -puN lib/ridr.c~idr-introduce-ridr_remove lib/ridr.c
--- a/lib/ridr.c~idr-introduce-ridr_remove
+++ a/lib/ridr.c
@@ -28,6 +28,19 @@ static struct ridr_layer *get_from_free_
return(q);
}
+static void ridr_layer_rcu_free(struct rcu_head *head)
+{
+ struct ridr_layer *layer;
+
+ layer = container_of(head, struct ridr_layer, rcu_head);
+ kmem_cache_free(ridr_layer_cache, layer);
+}
+
+static inline void free_layer(struct ridr_layer *p)
+{
+ call_rcu(&p->rcu_head, ridr_layer_rcu_free);
+}
+
/* only called when idp->lock is held */
/* moves an ridr_layer to the free list */
static void __move_to_free_list(struct ridr *idp, struct ridr_layer *p)
@@ -259,6 +272,76 @@ int ridr_get_new(struct ridr *idp, void
}
EXPORT_SYMBOL(ridr_get_new);
+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];
+ struct ridr_layer *to_free;
+ int n;
+
+ *paa = NULL;
+ *++paa = &idp->top;
+
+ while ((shift > 0) && p) {
+ n = (id >> shift) & IDR_MASK;
+ __clear_bit(n, &p->idr.bitmap);
+ *++paa = (struct ridr_layer **) &(p->idr.ary[n]);
+ p = p->idr.ary[n];
+ shift -= IDR_BITS;
+ }
+ n = id & IDR_MASK;
+ if (likely(p != NULL && test_bit(n, &p->idr.bitmap))) {
+ __clear_bit(n, &p->idr.bitmap);
+ rcu_assign_pointer(p->idr.ary[n], NULL);
+ to_free = NULL;
+ while (*paa && !--((**paa)->idr.count)) {
+ if (to_free)
+ free_layer(to_free);
+ to_free = **paa;
+ **paa-- = NULL;
+ }
+ if (!*paa)
+ idp->layers = 0;
+ if (to_free)
+ free_layer(to_free);
+ } else
+ _idr_remove_warning("ridr_remove", 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;
+ struct ridr_layer *to_free;
+
+ /* 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->idr.count == 1 && (idp->layers > 1) &&
+ idp->top->idr.ary[0]) {
+ /*
+ * Single child at leftmost slot: we can shrink the tree.
+ * This level is not needed anymore since when layers are
+ * inserted, they are inserted at the top of the existing
+ * tree.
+ */
+ to_free = idp->top;
+ p = idp->top->idr.ary[0];
+ rcu_assign_pointer(idp->top, p);
+ --idp->layers;
+ to_free->idr.bitmap = to_free->idr.count = 0;
+ to_free->idr.ary[0] = NULL;
+ free_layer(to_free);
+ }
+ return;
+}
+EXPORT_SYMBOL(ridr_remove);
+
/**
* ridr_find - return pointer for given id
* @idp: ridr handle
_
Patches currently in -mm which might be from Nadia.Derbey@xxxxxxxx are
origin.patch
idr-introduce-ridr_remove.patch
ipc-integrate-the-ridr-code-into-ipc-code.patch
ipc-get-rid-of-ipc_lock_down.patch
--
To unsubscribe from this list: send the line "unsubscribe mm-commits" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
