[PATCH 08/10] This patch introduces the ridr_remove() routine. Signed-off-by: Nadia Derbey --- 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(-) Index: linux-2.6.25-mm1/include/linux/ridr.h =================================================================== --- linux-2.6.25-mm1.orig/include/linux/ridr.h 2008-04-29 14:31:43.000000000 +0200 +++ linux-2.6.25-mm1/include/linux/ridr.h 2008-04-29 14:34:53.000000000 +0200 @@ -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 *); Index: linux-2.6.25-mm1/include/linux/idr.h =================================================================== --- linux-2.6.25-mm1.orig/include/linux/idr.h 2008-04-29 14:08:47.000000000 +0200 +++ linux-2.6.25-mm1/include/linux/idr.h 2008-04-29 14:35:37.000000000 +0200 @@ -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. Index: linux-2.6.25-mm1/lib/idr.c =================================================================== --- linux-2.6.25-mm1.orig/lib/idr.c 2008-04-29 14:06:20.000000000 +0200 +++ linux-2.6.25-mm1/lib/idr.c 2008-04-29 14:40:12.000000000 +0200 @@ -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); } /** Index: linux-2.6.25-mm1/lib/ridr.c =================================================================== --- linux-2.6.25-mm1.orig/lib/ridr.c 2008-04-29 14:32:26.000000000 +0200 +++ linux-2.6.25-mm1/lib/ridr.c 2008-04-29 14:41:57.000000000 +0200 @@ -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 -- -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/