From 4ae537892ab9858f71c78701f4651ad1ca531a1b Mon Sep 17 00:00:00 2001 From: Nadia Derbey Date: Fri, 25 Jul 2008 01:47:58 -0700 Subject: idr: rename some of the idr APIs internal routines This is a trivial patch that renames: . alloc_layer to get_from_free_list since it idr_pre_get that actually allocates memory. . free_layer to move_to_free_list since memory is not actually freed there. This makes things more clear for the next patches. Signed-off-by: Nadia Derbey Reviewed-by: "Paul E. McKenney" Cc: Manfred Spraul Cc: Jim Houston Cc: Pierre Peiffer Acked-by: Rik van Riel Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 31 ++++++++++++++++--------------- 1 file changed, 16 insertions(+), 15 deletions(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index 7a02e173f027..8170ace154fb 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -35,7 +35,7 @@ static struct kmem_cache *idr_layer_cache; -static struct idr_layer *alloc_layer(struct idr *idp) +static struct idr_layer *get_from_free_list(struct idr *idp) { struct idr_layer *p; unsigned long flags; @@ -51,14 +51,14 @@ static struct idr_layer *alloc_layer(struct idr *idp) } /* only called when idp->lock is held */ -static void __free_layer(struct idr *idp, struct idr_layer *p) +static void __move_to_free_list(struct idr *idp, struct idr_layer *p) { p->ary[0] = idp->id_free; idp->id_free = p; idp->id_free_cnt++; } -static void free_layer(struct idr *idp, struct idr_layer *p) +static void move_to_free_list(struct idr *idp, struct idr_layer *p) { unsigned long flags; @@ -66,7 +66,7 @@ static void free_layer(struct idr *idp, struct idr_layer *p) * Depends on the return element being zeroed. */ spin_lock_irqsave(&idp->lock, flags); - __free_layer(idp, p); + __move_to_free_list(idp, p); spin_unlock_irqrestore(&idp->lock, flags); } @@ -109,7 +109,7 @@ int idr_pre_get(struct idr *idp, gfp_t gfp_mask) new = kmem_cache_alloc(idr_layer_cache, gfp_mask); if (new == NULL) return (0); - free_layer(idp, new); + move_to_free_list(idp, new); } return 1; } @@ -167,7 +167,8 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) * Create the layer below if it is missing. */ if (!p->ary[m]) { - if (!(new = alloc_layer(idp))) + new = get_from_free_list(idp); + if (!new) return -1; p->ary[m] = new; p->count++; @@ -192,7 +193,7 @@ build_up: p = idp->top; layers = idp->layers; if (unlikely(!p)) { - if (!(p = alloc_layer(idp))) + if (!(p = get_from_free_list(idp))) return -1; layers = 1; } @@ -204,7 +205,7 @@ build_up: layers++; if (!p->count) continue; - if (!(new = alloc_layer(idp))) { + if (!(new = get_from_free_list(idp))) { /* * The allocation failed. If we built part of * the structure tear it down. @@ -214,7 +215,7 @@ build_up: p = p->ary[0]; new->ary[0] = NULL; new->bitmap = new->count = 0; - __free_layer(idp, new); + __move_to_free_list(idp, new); } spin_unlock_irqrestore(&idp->lock, flags); return -1; @@ -351,7 +352,7 @@ static void sub_remove(struct idr *idp, int shift, int id) __clear_bit(n, &p->bitmap); p->ary[n] = NULL; while(*paa && ! --((**paa)->count)){ - free_layer(idp, **paa); + move_to_free_list(idp, **paa); **paa-- = NULL; } if (!*paa) @@ -378,12 +379,12 @@ void idr_remove(struct idr *idp, int id) p = idp->top->ary[0]; idp->top->bitmap = idp->top->count = 0; - free_layer(idp, idp->top); + move_to_free_list(idp, idp->top); idp->top = p; --idp->layers; } while (idp->id_free_cnt >= IDR_FREE_MAX) { - p = alloc_layer(idp); + p = get_from_free_list(idp); kmem_cache_free(idr_layer_cache, p); } return; @@ -426,7 +427,7 @@ void idr_remove_all(struct idr *idp) while (n < fls(id)) { if (p) { memset(p, 0, sizeof *p); - free_layer(idp, p); + move_to_free_list(idp, p); } n += IDR_BITS; p = *--paa; @@ -444,7 +445,7 @@ EXPORT_SYMBOL(idr_remove_all); void idr_destroy(struct idr *idp) { while (idp->id_free_cnt) { - struct idr_layer *p = alloc_layer(idp); + struct idr_layer *p = get_from_free_list(idp); kmem_cache_free(idr_layer_cache, p); } } @@ -749,7 +750,7 @@ int ida_get_new_above(struct ida *ida, int starting_id, int *p_id) * allocation. */ if (ida->idr.id_free_cnt || ida->free_bitmap) { - struct idr_layer *p = alloc_layer(&ida->idr); + struct idr_layer *p = get_from_free_list(&ida->idr); if (p) kmem_cache_free(idr_layer_cache, p); } -- cgit v1.2.2 From f098ad655f4dd8e3da98ffbeda9cedcc4459c01a Mon Sep 17 00:00:00 2001 From: Nadia Derbey Date: Fri, 25 Jul 2008 01:47:59 -0700 Subject: idr: fix a printk call Fix the incomplete printk call. Signed-off-by: Nadia Derbey Reviewed-by: "Paul E. McKenney" Cc: Manfred Spraul Cc: Jim Houston Cc: Pierre Peiffer Acked-by: Rik van Riel Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index 8170ace154fb..9d905b131ecb 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -326,7 +326,8 @@ EXPORT_SYMBOL(idr_get_new); static void idr_remove_warning(int id) { - printk("idr_remove called for id=%d which is not allocated.\n", id); + printk(KERN_WARNING + "idr_remove called for id=%d which is not allocated.\n", id); dump_stack(); } -- cgit v1.2.2 From 944ca05c7b4972f2ebf37262e0f4933d178ad6db Mon Sep 17 00:00:00 2001 From: Nadia Derbey Date: Fri, 25 Jul 2008 01:47:59 -0700 Subject: idr: error checking factorization Do some code factorization in the return code analysis. Signed-off-by: Nadia Derbey Cc: "Paul E. McKenney" Cc: Manfred Spraul Cc: Jim Houston Cc: Pierre Peiffer Acked-by: Rik van Riel Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 30 +++++++++--------------------- 1 file changed, 9 insertions(+), 21 deletions(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index 9d905b131ecb..80ba06f29d36 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -143,7 +143,7 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) /* if already at the top layer, we need to grow */ if (!(p = pa[l])) { *starting_id = id; - return -2; + return IDR_NEED_TO_GROW; } /* If we need to go up one layer, continue the @@ -160,7 +160,7 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) id = ((id >> sh) ^ n ^ m) << sh; } if ((id >= MAX_ID_BIT) || (id < 0)) - return -3; + return IDR_NOMORE_SPACE; if (l == 0) break; /* @@ -229,7 +229,7 @@ build_up: idp->top = p; idp->layers = layers; v = sub_alloc(idp, &id, pa); - if (v == -2) + if (v == IDR_NEED_TO_GROW) goto build_up; return(v); } @@ -278,12 +278,8 @@ int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id) * 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; - } + if (rv < 0) + return _idr_rc_to_errno(rv); *id = rv; return 0; } @@ -313,12 +309,8 @@ int idr_get_new(struct idr *idp, void *ptr, int *id) * 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; - } + if (rv < 0) + return _idr_rc_to_errno(rv); *id = rv; return 0; } @@ -696,12 +688,8 @@ int ida_get_new_above(struct ida *ida, int starting_id, int *p_id) restart: /* get vacant slot */ t = idr_get_empty_slot(&ida->idr, idr_id, pa); - if (t < 0) { - if (t == -1) - return -EAGAIN; - else /* will be -3 */ - return -ENOSPC; - } + if (t < 0) + return _idr_rc_to_errno(t); if (t * IDA_BITMAP_BITS >= MAX_ID_BIT) return -ENOSPC; -- cgit v1.2.2 From 3219b3b7456d5cf15ba7b1fe7b1bcf15ce8840e2 Mon Sep 17 00:00:00 2001 From: Nadia Derbey Date: Fri, 25 Jul 2008 01:48:00 -0700 Subject: idr: make idr_get_new* rcu-safe Make the idr_get_new* routines rcu-safe. Signed-off-by: Nadia Derbey Reviewed-by: "Paul E. McKenney" Cc: Manfred Spraul Cc: Jim Houston Cc: Pierre Peiffer Acked-by: Rik van Riel Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 14 +++++++++----- 1 file changed, 9 insertions(+), 5 deletions(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index 80ba06f29d36..44ab3b2a4eba 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -6,6 +6,8 @@ * Modified by George Anzinger to reuse immediately and to use * find bit instructions. Also removed _irq on spinlocks. * + * Modified by Nadia Derbey to make it RCU safe. + * * Small id to pointer translation service. * * It uses a radix tree like structure as a sparse array indexed @@ -96,7 +98,7 @@ static void idr_mark_full(struct idr_layer **pa, int id) * @gfp_mask: memory allocation flags * * This function should be called prior to locking and calling the - * following function. It preallocates enough memory to satisfy + * idr_get_new* functions. It preallocates enough memory to satisfy * the worst possible allocation. * * If the system is REALLY out of memory this function returns 0, @@ -170,7 +172,7 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) new = get_from_free_list(idp); if (!new) return -1; - p->ary[m] = new; + rcu_assign_pointer(p->ary[m], new); p->count++; } pa[l--] = p; @@ -226,7 +228,7 @@ build_up: __set_bit(0, &new->bitmap); p = new; } - idp->top = p; + rcu_assign_pointer(idp->top, p); idp->layers = layers; v = sub_alloc(idp, &id, pa); if (v == IDR_NEED_TO_GROW) @@ -245,7 +247,8 @@ static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id) * Successfully found an empty slot. Install the user * pointer and mark the slot full. */ - pa[0]->ary[id & IDR_MASK] = (struct idr_layer *)ptr; + rcu_assign_pointer(pa[0]->ary[id & IDR_MASK], + (struct idr_layer *)ptr); pa[0]->count++; idr_mark_full(pa, id); } @@ -710,7 +713,8 @@ int ida_get_new_above(struct ida *ida, int starting_id, int *p_id) return -EAGAIN; memset(bitmap, 0, sizeof(struct ida_bitmap)); - pa[0]->ary[idr_id & IDR_MASK] = (void *)bitmap; + rcu_assign_pointer(pa[0]->ary[idr_id & IDR_MASK], + (void *)bitmap); pa[0]->count++; } -- cgit v1.2.2 From f9c46d6ea5ce138a886c3a0f10a46130afab75f5 Mon Sep 17 00:00:00 2001 From: Nadia Derbey Date: Fri, 25 Jul 2008 01:48:01 -0700 Subject: idr: make idr_find rcu-safe Make idr_find rcu-safe: it can now be called inside an rcu_read critical section. Signed-off-by: Nadia Derbey Reviewed-by: "Paul E. McKenney" Cc: Manfred Spraul Cc: Jim Houston Cc: Pierre Peiffer Acked-by: Rik van Riel Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index 44ab3b2a4eba..21e12af1f231 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -456,7 +456,8 @@ EXPORT_SYMBOL(idr_destroy); * return indicates that @id is not valid or you passed %NULL in * idr_get_new(). * - * The caller must serialize idr_find() vs idr_get_new() and idr_remove(). + * This function can be called under rcu_read_lock(), given that the leaf + * pointers lifetimes are correctly managed. */ void *idr_find(struct idr *idp, int id) { @@ -464,7 +465,7 @@ void *idr_find(struct idr *idp, int id) struct idr_layer *p; n = idp->layers * IDR_BITS; - p = idp->top; + p = rcu_dereference(idp->top); /* Mask off upper bits we don't use for the search. */ id &= MAX_ID_MASK; @@ -474,7 +475,7 @@ void *idr_find(struct idr *idp, int id) while (n > 0 && p) { n -= IDR_BITS; - p = p->ary[(id >> n) & IDR_MASK]; + p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]); } return((void *)p); } @@ -507,7 +508,7 @@ int idr_for_each(struct idr *idp, struct idr_layer **paa = &pa[0]; n = idp->layers * IDR_BITS; - p = idp->top; + p = rcu_dereference(idp->top); max = 1 << n; id = 0; @@ -515,7 +516,7 @@ int idr_for_each(struct idr *idp, while (n > 0 && p) { n -= IDR_BITS; *paa++ = p; - p = p->ary[(id >> n) & IDR_MASK]; + p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]); } if (p) { -- cgit v1.2.2 From cf481c20c476ad2c0febdace9ce23f5a4db19582 Mon Sep 17 00:00:00 2001 From: Nadia Derbey Date: Fri, 25 Jul 2008 01:48:02 -0700 Subject: idr: make idr_remove rcu-safe Introduce the free_layer() routine: it is the one that actually frees memory after a grace period has elapsed. Signed-off-by: Nadia Derbey Reviewed-by: "Paul E. McKenney" Cc: Manfred Spraul Cc: Jim Houston Cc: Pierre Peiffer Acked-by: Rik van Riel Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 57 +++++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 43 insertions(+), 14 deletions(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index 21e12af1f231..3476f8203e97 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -52,6 +52,19 @@ static struct idr_layer *get_from_free_list(struct idr *idp) return(p); } +static void idr_layer_rcu_free(struct rcu_head *head) +{ + struct idr_layer *layer; + + layer = container_of(head, struct idr_layer, rcu_head); + kmem_cache_free(idr_layer_cache, layer); +} + +static inline void free_layer(struct idr_layer *p) +{ + call_rcu(&p->rcu_head, idr_layer_rcu_free); +} + /* only called when idp->lock is held */ static void __move_to_free_list(struct idr *idp, struct idr_layer *p) { @@ -331,6 +344,7 @@ static void sub_remove(struct idr *idp, int shift, int id) struct idr_layer *p = idp->top; struct idr_layer **pa[MAX_LEVEL]; struct idr_layer ***paa = &pa[0]; + struct idr_layer *to_free; int n; *paa = NULL; @@ -346,13 +360,18 @@ static void sub_remove(struct idr *idp, int shift, int id) n = id & IDR_MASK; if (likely(p != NULL && test_bit(n, &p->bitmap))){ __clear_bit(n, &p->bitmap); - p->ary[n] = NULL; + rcu_assign_pointer(p->ary[n], NULL); + to_free = NULL; while(*paa && ! --((**paa)->count)){ - move_to_free_list(idp, **paa); + 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(id); } @@ -365,22 +384,34 @@ static void sub_remove(struct idr *idp, int shift, int id) void idr_remove(struct idr *idp, int id) { struct idr_layer *p; + struct idr_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->count == 1 && (idp->layers > 1) && - idp->top->ary[0]) { // We can drop a layer - + idp->top->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->ary[0]; - idp->top->bitmap = idp->top->count = 0; - move_to_free_list(idp, idp->top); - idp->top = p; + rcu_assign_pointer(idp->top, p); --idp->layers; + to_free->bitmap = to_free->count = 0; + free_layer(to_free); } while (idp->id_free_cnt >= IDR_FREE_MAX) { p = get_from_free_list(idp); + /* + * Note: we don't call the rcu callback here, since the only + * layers that fall into the freelist are those that have been + * preallocated. + */ kmem_cache_free(idr_layer_cache, p); } return; @@ -421,15 +452,13 @@ void idr_remove_all(struct idr *idp) id += 1 << n; while (n < fls(id)) { - if (p) { - memset(p, 0, sizeof *p); - move_to_free_list(idp, p); - } + if (p) + free_layer(p); n += IDR_BITS; p = *--paa; } } - idp->top = NULL; + rcu_assign_pointer(idp->top, NULL); idp->layers = 0; } EXPORT_SYMBOL(idr_remove_all); @@ -546,7 +575,7 @@ EXPORT_SYMBOL(idr_for_each); * A -ENOENT return indicates that @id was not found. * A -EINVAL return indicates that @id was not within valid constraints. * - * The caller must serialize vs idr_find(), idr_get_new(), and idr_remove(). + * The caller must serialize with writers. */ void *idr_replace(struct idr *idp, void *ptr, int id) { @@ -572,7 +601,7 @@ void *idr_replace(struct idr *idp, void *ptr, int id) return ERR_PTR(-ENOENT); old_p = p->ary[n]; - p->ary[n] = ptr; + rcu_assign_pointer(p->ary[n], ptr); return old_p; } -- cgit v1.2.2 From 51cc50685a4275c6a02653670af9f108a64e01cf Mon Sep 17 00:00:00 2001 From: Alexey Dobriyan Date: Fri, 25 Jul 2008 19:45:34 -0700 Subject: SL*B: drop kmem cache argument from constructor Kmem cache passed to constructor is only needed for constructors that are themselves multiplexeres. Nobody uses this "feature", nor does anybody uses passed kmem cache in non-trivial way, so pass only pointer to object. Non-trivial places are: arch/powerpc/mm/init_64.c arch/powerpc/mm/hugetlbpage.c This is flag day, yes. Signed-off-by: Alexey Dobriyan Acked-by: Pekka Enberg Acked-by: Christoph Lameter Cc: Jon Tollefson Cc: Nick Piggin Cc: Matt Mackall [akpm@linux-foundation.org: fix arch/powerpc/mm/hugetlbpage.c] [akpm@linux-foundation.org: fix mm/slab.c] [akpm@linux-foundation.org: fix ubifs] Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index 3476f8203e97..e728c7fccc4d 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -607,7 +607,7 @@ void *idr_replace(struct idr *idp, void *ptr, int id) } EXPORT_SYMBOL(idr_replace); -static void idr_cache_ctor(struct kmem_cache *idr_layer_cache, void *idr_layer) +static void idr_cache_ctor(void *idr_layer) { memset(idr_layer, 0, sizeof(struct idr_layer)); } -- cgit v1.2.2