From 6ff2d39b91aec3dcae951afa982059e3dd9b49dc Mon Sep 17 00:00:00 2001 From: Manfred Spraul Date: Mon, 1 Dec 2008 13:14:02 -0800 Subject: lib/idr.c: fix rcu related race with idr_find 2nd part of the fixes needed for http://bugzilla.kernel.org/show_bug.cgi?id=11796. When the idr tree is either grown or shrunk, then the update to the number of layers and the top pointer were not atomic. This race caused crashes. The attached patch fixes that by replicating the layers counter in each layer, thus idr_find doesn't need idp->layers anymore. Signed-off-by: Manfred Spraul Cc: Clement Calmels Cc: Nadia Derbey Cc: Pierre Peiffer Cc: Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 14 ++++++++++++-- 1 file changed, 12 insertions(+), 2 deletions(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index e728c7fccc4d..7a785a0c2ea0 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -185,6 +185,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; + new->layer = l-1; rcu_assign_pointer(p->ary[m], new); p->count++; } @@ -210,6 +211,7 @@ build_up: if (unlikely(!p)) { if (!(p = get_from_free_list(idp))) return -1; + p->layer = 0; layers = 1; } /* @@ -237,6 +239,7 @@ build_up: } new->ary[0] = p; new->count = 1; + new->layer = layers-1; if (p->bitmap == IDR_FULL) __set_bit(0, &new->bitmap); p = new; @@ -493,17 +496,21 @@ void *idr_find(struct idr *idp, int id) int n; struct idr_layer *p; - n = idp->layers * IDR_BITS; p = rcu_dereference(idp->top); + if (!p) + return NULL; + n = (p->layer+1) * IDR_BITS; /* Mask off upper bits we don't use for the search. */ id &= MAX_ID_MASK; if (id >= (1 << n)) return NULL; + BUG_ON(n == 0); while (n > 0 && p) { n -= IDR_BITS; + BUG_ON(n != p->layer*IDR_BITS); p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]); } return((void *)p); @@ -582,8 +589,11 @@ void *idr_replace(struct idr *idp, void *ptr, int id) int n; struct idr_layer *p, *old_p; - n = idp->layers * IDR_BITS; p = idp->top; + if (!p) + return ERR_PTR(-EINVAL); + + n = (p->layer+1) * IDR_BITS; id &= MAX_ID_MASK; -- cgit v1.2.3 From 711a49a07f84f914aac26a52143f6e7526571143 Mon Sep 17 00:00:00 2001 From: Manfred Spraul Date: Wed, 10 Dec 2008 18:17:06 +0100 Subject: lib/idr.c: Fix bug introduced by RCU fix The last patch to lib/idr.c caused a bug if idr_get_new_above() was called on an empty idr. Usually, nodes stay on the same layer. New layers are added to the top of the tree. The exception is idr_get_new_above() on an empty tree: In this case, the new root node is first added on layer 0, then moved upwards. p->layer was not updated. As usual: You shall never rely on the source code comments, they will only mislead you. Signed-off-by: Manfred Spraul Signed-off-by: Linus Torvalds --- lib/idr.c | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index 7a785a0c2ea0..1c4f9281f412 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -220,8 +220,14 @@ build_up: */ while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) { layers++; - if (!p->count) + if (!p->count) { + /* special case: if the tree is currently empty, + * then we grow the tree by moving the top node + * upwards. + */ + p->layer++; continue; + } if (!(new = get_from_free_list(idp))) { /* * The allocation failed. If we built part of -- cgit v1.2.3