aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig.debug1
-rw-r--r--lib/Makefile2
-rw-r--r--lib/cmdline.c35
-rw-r--r--lib/idr.c4
-rw-r--r--lib/kobject.c3
-rw-r--r--lib/list_debug.c10
-rw-r--r--lib/locking-selftest.c2
-rw-r--r--lib/radix-tree.c333
8 files changed, 276 insertions, 114 deletions
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index d3679103a8e4..b75fed737f25 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1,6 +1,7 @@
1 1
2config PRINTK_TIME 2config PRINTK_TIME
3 bool "Show timing information on printks" 3 bool "Show timing information on printks"
4 depends on PRINTK
4 help 5 help
5 Selecting this option causes timing information to be 6 Selecting this option causes timing information to be
6 included in printk output. This allows you to measure 7 included in printk output. This allows you to measure
diff --git a/lib/Makefile b/lib/Makefile
index cf98fabaa549..fea8f9035f07 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -25,7 +25,7 @@ lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
25lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o 25lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
26lib-$(CONFIG_SEMAPHORE_SLEEPERS) += semaphore-sleepers.o 26lib-$(CONFIG_SEMAPHORE_SLEEPERS) += semaphore-sleepers.o
27lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o 27lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o
28lib-$(CONFIG_GENERIC_HWEIGHT) += hweight.o 28obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o
29obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o 29obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o
30obj-$(CONFIG_PLIST) += plist.o 30obj-$(CONFIG_PLIST) += plist.o
31obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o 31obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o
diff --git a/lib/cmdline.c b/lib/cmdline.c
index 0331ed825ea7..8a5b5303bd4f 100644
--- a/lib/cmdline.c
+++ b/lib/cmdline.c
@@ -16,6 +16,23 @@
16#include <linux/kernel.h> 16#include <linux/kernel.h>
17#include <linux/string.h> 17#include <linux/string.h>
18 18
19/*
20 * If a hyphen was found in get_option, this will handle the
21 * range of numbers, M-N. This will expand the range and insert
22 * the values[M, M+1, ..., N] into the ints array in get_options.
23 */
24
25static int get_range(char **str, int *pint)
26{
27 int x, inc_counter, upper_range;
28
29 (*str)++;
30 upper_range = simple_strtol((*str), NULL, 0);
31 inc_counter = upper_range - *pint;
32 for (x = *pint; x < upper_range; x++)
33 *pint++ = x;
34 return inc_counter;
35}
19 36
20/** 37/**
21 * get_option - Parse integer from an option string 38 * get_option - Parse integer from an option string
@@ -29,6 +46,7 @@
29 * 0 : no int in string 46 * 0 : no int in string
30 * 1 : int found, no subsequent comma 47 * 1 : int found, no subsequent comma
31 * 2 : int found including a subsequent comma 48 * 2 : int found including a subsequent comma
49 * 3 : hyphen found to denote a range
32 */ 50 */
33 51
34int get_option (char **str, int *pint) 52int get_option (char **str, int *pint)
@@ -44,6 +62,8 @@ int get_option (char **str, int *pint)
44 (*str)++; 62 (*str)++;
45 return 2; 63 return 2;
46 } 64 }
65 if (**str == '-')
66 return 3;
47 67
48 return 1; 68 return 1;
49} 69}
@@ -55,7 +75,8 @@ int get_option (char **str, int *pint)
55 * @ints: integer array 75 * @ints: integer array
56 * 76 *
57 * This function parses a string containing a comma-separated 77 * This function parses a string containing a comma-separated
58 * list of integers. The parse halts when the array is 78 * list of integers, a hyphen-separated range of _positive_ integers,
79 * or a combination of both. The parse halts when the array is
59 * full, or when no more numbers can be retrieved from the 80 * full, or when no more numbers can be retrieved from the
60 * string. 81 * string.
61 * 82 *
@@ -72,6 +93,18 @@ char *get_options(const char *str, int nints, int *ints)
72 res = get_option ((char **)&str, ints + i); 93 res = get_option ((char **)&str, ints + i);
73 if (res == 0) 94 if (res == 0)
74 break; 95 break;
96 if (res == 3) {
97 int range_nums;
98 range_nums = get_range((char **)&str, ints + i);
99 if (range_nums < 0)
100 break;
101 /*
102 * Decrement the result by one to leave out the
103 * last number in the range. The next iteration
104 * will handle the upper number in the range
105 */
106 i += (range_nums - 1);
107 }
75 i++; 108 i++;
76 if (res == 1) 109 if (res == 1)
77 break; 110 break;
diff --git a/lib/idr.c b/lib/idr.c
index 16d2143fea48..71853531d3b0 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -33,7 +33,7 @@
33#include <linux/string.h> 33#include <linux/string.h>
34#include <linux/idr.h> 34#include <linux/idr.h>
35 35
36static kmem_cache_t *idr_layer_cache; 36static struct kmem_cache *idr_layer_cache;
37 37
38static struct idr_layer *alloc_layer(struct idr *idp) 38static struct idr_layer *alloc_layer(struct idr *idp)
39{ 39{
@@ -445,7 +445,7 @@ void *idr_replace(struct idr *idp, void *ptr, int id)
445} 445}
446EXPORT_SYMBOL(idr_replace); 446EXPORT_SYMBOL(idr_replace);
447 447
448static void idr_cache_ctor(void * idr_layer, kmem_cache_t *idr_layer_cache, 448static void idr_cache_ctor(void * idr_layer, struct kmem_cache *idr_layer_cache,
449 unsigned long flags) 449 unsigned long flags)
450{ 450{
451 memset(idr_layer, 0, sizeof(struct idr_layer)); 451 memset(idr_layer, 0, sizeof(struct idr_layer));
diff --git a/lib/kobject.c b/lib/kobject.c
index 744a4b102c7f..7ce6dc138e90 100644
--- a/lib/kobject.c
+++ b/lib/kobject.c
@@ -111,10 +111,9 @@ char *kobject_get_path(struct kobject *kobj, gfp_t gfp_mask)
111 len = get_kobj_path_length(kobj); 111 len = get_kobj_path_length(kobj);
112 if (len == 0) 112 if (len == 0)
113 return NULL; 113 return NULL;
114 path = kmalloc(len, gfp_mask); 114 path = kzalloc(len, gfp_mask);
115 if (!path) 115 if (!path)
116 return NULL; 116 return NULL;
117 memset(path, 0x00, len);
118 fill_kobj_path(kobj, path, len); 117 fill_kobj_path(kobj, path, len);
119 118
120 return path; 119 return path;
diff --git a/lib/list_debug.c b/lib/list_debug.c
index 7ba9d823d388..4350ba9655bd 100644
--- a/lib/list_debug.c
+++ b/lib/list_debug.c
@@ -21,13 +21,15 @@ void __list_add(struct list_head *new,
21 struct list_head *next) 21 struct list_head *next)
22{ 22{
23 if (unlikely(next->prev != prev)) { 23 if (unlikely(next->prev != prev)) {
24 printk(KERN_ERR "list_add corruption. next->prev should be %p, but was %p\n", 24 printk(KERN_ERR "list_add corruption. next->prev should be "
25 prev, next->prev); 25 "prev (%p), but was %p. (next=%p).\n",
26 prev, next->prev, next);
26 BUG(); 27 BUG();
27 } 28 }
28 if (unlikely(prev->next != next)) { 29 if (unlikely(prev->next != next)) {
29 printk(KERN_ERR "list_add corruption. prev->next should be %p, but was %p\n", 30 printk(KERN_ERR "list_add corruption. prev->next should be "
30 next, prev->next); 31 "next (%p), but was %p. (prev=%p).\n",
32 next, prev->next, prev);
31 BUG(); 33 BUG();
32 } 34 }
33 next->prev = new; 35 next->prev = new;
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index 7945787f439a..280332c1827c 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -963,7 +963,9 @@ static void dotest(void (*testcase_fn)(void), int expected, int lockclass_mask)
963 printk("failed|"); 963 printk("failed|");
964 } else { 964 } else {
965 unexpected_testcase_failures++; 965 unexpected_testcase_failures++;
966
966 printk("FAILED|"); 967 printk("FAILED|");
968 dump_stack();
967 } 969 }
968 } else { 970 } else {
969 testcase_successes++; 971 testcase_successes++;
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index aa9bfd0bdbd1..d69ddbe43865 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -2,6 +2,7 @@
2 * Copyright (C) 2001 Momchil Velikov 2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig 3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com> 4 * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com>
5 * Copyright (C) 2006 Nick Piggin
5 * 6 *
6 * This program is free software; you can redistribute it and/or 7 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License as 8 * modify it under the terms of the GNU General Public License as
@@ -30,6 +31,7 @@
30#include <linux/gfp.h> 31#include <linux/gfp.h>
31#include <linux/string.h> 32#include <linux/string.h>
32#include <linux/bitops.h> 33#include <linux/bitops.h>
34#include <linux/rcupdate.h>
33 35
34 36
35#ifdef __KERNEL__ 37#ifdef __KERNEL__
@@ -45,7 +47,9 @@
45 ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG) 47 ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
46 48
47struct radix_tree_node { 49struct radix_tree_node {
50 unsigned int height; /* Height from the bottom */
48 unsigned int count; 51 unsigned int count;
52 struct rcu_head rcu_head;
49 void *slots[RADIX_TREE_MAP_SIZE]; 53 void *slots[RADIX_TREE_MAP_SIZE];
50 unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; 54 unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
51}; 55};
@@ -63,7 +67,7 @@ static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly;
63/* 67/*
64 * Radix tree node cache. 68 * Radix tree node cache.
65 */ 69 */
66static kmem_cache_t *radix_tree_node_cachep; 70static struct kmem_cache *radix_tree_node_cachep;
67 71
68/* 72/*
69 * Per-cpu pool of preloaded nodes 73 * Per-cpu pool of preloaded nodes
@@ -100,13 +104,21 @@ radix_tree_node_alloc(struct radix_tree_root *root)
100 rtp->nr--; 104 rtp->nr--;
101 } 105 }
102 } 106 }
107 BUG_ON(radix_tree_is_direct_ptr(ret));
103 return ret; 108 return ret;
104} 109}
105 110
111static void radix_tree_node_rcu_free(struct rcu_head *head)
112{
113 struct radix_tree_node *node =
114 container_of(head, struct radix_tree_node, rcu_head);
115 kmem_cache_free(radix_tree_node_cachep, node);
116}
117
106static inline void 118static inline void
107radix_tree_node_free(struct radix_tree_node *node) 119radix_tree_node_free(struct radix_tree_node *node)
108{ 120{
109 kmem_cache_free(radix_tree_node_cachep, node); 121 call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
110} 122}
111 123
112/* 124/*
@@ -222,11 +234,12 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
222 } 234 }
223 235
224 do { 236 do {
237 unsigned int newheight;
225 if (!(node = radix_tree_node_alloc(root))) 238 if (!(node = radix_tree_node_alloc(root)))
226 return -ENOMEM; 239 return -ENOMEM;
227 240
228 /* Increase the height. */ 241 /* Increase the height. */
229 node->slots[0] = root->rnode; 242 node->slots[0] = radix_tree_direct_to_ptr(root->rnode);
230 243
231 /* Propagate the aggregated tag info into the new root */ 244 /* Propagate the aggregated tag info into the new root */
232 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { 245 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
@@ -234,9 +247,11 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
234 tag_set(node, tag, 0); 247 tag_set(node, tag, 0);
235 } 248 }
236 249
250 newheight = root->height+1;
251 node->height = newheight;
237 node->count = 1; 252 node->count = 1;
238 root->rnode = node; 253 rcu_assign_pointer(root->rnode, node);
239 root->height++; 254 root->height = newheight;
240 } while (height > root->height); 255 } while (height > root->height);
241out: 256out:
242 return 0; 257 return 0;
@@ -258,6 +273,8 @@ int radix_tree_insert(struct radix_tree_root *root,
258 int offset; 273 int offset;
259 int error; 274 int error;
260 275
276 BUG_ON(radix_tree_is_direct_ptr(item));
277
261 /* Make sure the tree is high enough. */ 278 /* Make sure the tree is high enough. */
262 if (index > radix_tree_maxindex(root->height)) { 279 if (index > radix_tree_maxindex(root->height)) {
263 error = radix_tree_extend(root, index); 280 error = radix_tree_extend(root, index);
@@ -275,11 +292,12 @@ int radix_tree_insert(struct radix_tree_root *root,
275 /* Have to add a child node. */ 292 /* Have to add a child node. */
276 if (!(slot = radix_tree_node_alloc(root))) 293 if (!(slot = radix_tree_node_alloc(root)))
277 return -ENOMEM; 294 return -ENOMEM;
295 slot->height = height;
278 if (node) { 296 if (node) {
279 node->slots[offset] = slot; 297 rcu_assign_pointer(node->slots[offset], slot);
280 node->count++; 298 node->count++;
281 } else 299 } else
282 root->rnode = slot; 300 rcu_assign_pointer(root->rnode, slot);
283 } 301 }
284 302
285 /* Go a level down */ 303 /* Go a level down */
@@ -295,11 +313,11 @@ int radix_tree_insert(struct radix_tree_root *root,
295 313
296 if (node) { 314 if (node) {
297 node->count++; 315 node->count++;
298 node->slots[offset] = item; 316 rcu_assign_pointer(node->slots[offset], item);
299 BUG_ON(tag_get(node, 0, offset)); 317 BUG_ON(tag_get(node, 0, offset));
300 BUG_ON(tag_get(node, 1, offset)); 318 BUG_ON(tag_get(node, 1, offset));
301 } else { 319 } else {
302 root->rnode = item; 320 rcu_assign_pointer(root->rnode, radix_tree_ptr_to_direct(item));
303 BUG_ON(root_tag_get(root, 0)); 321 BUG_ON(root_tag_get(root, 0));
304 BUG_ON(root_tag_get(root, 1)); 322 BUG_ON(root_tag_get(root, 1));
305 } 323 }
@@ -308,49 +326,54 @@ int radix_tree_insert(struct radix_tree_root *root,
308} 326}
309EXPORT_SYMBOL(radix_tree_insert); 327EXPORT_SYMBOL(radix_tree_insert);
310 328
311static inline void **__lookup_slot(struct radix_tree_root *root, 329/**
312 unsigned long index) 330 * radix_tree_lookup_slot - lookup a slot in a radix tree
331 * @root: radix tree root
332 * @index: index key
333 *
334 * Returns: the slot corresponding to the position @index in the
335 * radix tree @root. This is useful for update-if-exists operations.
336 *
337 * This function cannot be called under rcu_read_lock, it must be
338 * excluded from writers, as must the returned slot for subsequent
339 * use by radix_tree_deref_slot() and radix_tree_replace slot.
340 * Caller must hold tree write locked across slot lookup and
341 * replace.
342 */
343void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
313{ 344{
314 unsigned int height, shift; 345 unsigned int height, shift;
315 struct radix_tree_node **slot; 346 struct radix_tree_node *node, **slot;
316
317 height = root->height;
318 347
319 if (index > radix_tree_maxindex(height)) 348 node = root->rnode;
349 if (node == NULL)
320 return NULL; 350 return NULL;
321 351
322 if (height == 0 && root->rnode) 352 if (radix_tree_is_direct_ptr(node)) {
353 if (index > 0)
354 return NULL;
323 return (void **)&root->rnode; 355 return (void **)&root->rnode;
356 }
357
358 height = node->height;
359 if (index > radix_tree_maxindex(height))
360 return NULL;
324 361
325 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 362 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
326 slot = &root->rnode;
327 363
328 while (height > 0) { 364 do {
329 if (*slot == NULL) 365 slot = (struct radix_tree_node **)
366 (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
367 node = *slot;
368 if (node == NULL)
330 return NULL; 369 return NULL;
331 370
332 slot = (struct radix_tree_node **)
333 ((*slot)->slots +
334 ((index >> shift) & RADIX_TREE_MAP_MASK));
335 shift -= RADIX_TREE_MAP_SHIFT; 371 shift -= RADIX_TREE_MAP_SHIFT;
336 height--; 372 height--;
337 } 373 } while (height > 0);
338 374
339 return (void **)slot; 375 return (void **)slot;
340} 376}
341
342/**
343 * radix_tree_lookup_slot - lookup a slot in a radix tree
344 * @root: radix tree root
345 * @index: index key
346 *
347 * Lookup the slot corresponding to the position @index in the radix tree
348 * @root. This is useful for update-if-exists operations.
349 */
350void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
351{
352 return __lookup_slot(root, index);
353}
354EXPORT_SYMBOL(radix_tree_lookup_slot); 377EXPORT_SYMBOL(radix_tree_lookup_slot);
355 378
356/** 379/**
@@ -359,13 +382,45 @@ EXPORT_SYMBOL(radix_tree_lookup_slot);
359 * @index: index key 382 * @index: index key
360 * 383 *
361 * Lookup the item at the position @index in the radix tree @root. 384 * Lookup the item at the position @index in the radix tree @root.
385 *
386 * This function can be called under rcu_read_lock, however the caller
387 * must manage lifetimes of leaf nodes (eg. RCU may also be used to free
388 * them safely). No RCU barriers are required to access or modify the
389 * returned item, however.
362 */ 390 */
363void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) 391void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
364{ 392{
365 void **slot; 393 unsigned int height, shift;
394 struct radix_tree_node *node, **slot;
395
396 node = rcu_dereference(root->rnode);
397 if (node == NULL)
398 return NULL;
399
400 if (radix_tree_is_direct_ptr(node)) {
401 if (index > 0)
402 return NULL;
403 return radix_tree_direct_to_ptr(node);
404 }
405
406 height = node->height;
407 if (index > radix_tree_maxindex(height))
408 return NULL;
409
410 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
366 411
367 slot = __lookup_slot(root, index); 412 do {
368 return slot != NULL ? *slot : NULL; 413 slot = (struct radix_tree_node **)
414 (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
415 node = rcu_dereference(*slot);
416 if (node == NULL)
417 return NULL;
418
419 shift -= RADIX_TREE_MAP_SHIFT;
420 height--;
421 } while (height > 0);
422
423 return node;
369} 424}
370EXPORT_SYMBOL(radix_tree_lookup); 425EXPORT_SYMBOL(radix_tree_lookup);
371 426
@@ -495,27 +550,30 @@ int radix_tree_tag_get(struct radix_tree_root *root,
495 unsigned long index, unsigned int tag) 550 unsigned long index, unsigned int tag)
496{ 551{
497 unsigned int height, shift; 552 unsigned int height, shift;
498 struct radix_tree_node *slot; 553 struct radix_tree_node *node;
499 int saw_unset_tag = 0; 554 int saw_unset_tag = 0;
500 555
501 height = root->height;
502 if (index > radix_tree_maxindex(height))
503 return 0;
504
505 /* check the root's tag bit */ 556 /* check the root's tag bit */
506 if (!root_tag_get(root, tag)) 557 if (!root_tag_get(root, tag))
507 return 0; 558 return 0;
508 559
509 if (height == 0) 560 node = rcu_dereference(root->rnode);
510 return 1; 561 if (node == NULL)
562 return 0;
563
564 if (radix_tree_is_direct_ptr(node))
565 return (index == 0);
566
567 height = node->height;
568 if (index > radix_tree_maxindex(height))
569 return 0;
511 570
512 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 571 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
513 slot = root->rnode;
514 572
515 for ( ; ; ) { 573 for ( ; ; ) {
516 int offset; 574 int offset;
517 575
518 if (slot == NULL) 576 if (node == NULL)
519 return 0; 577 return 0;
520 578
521 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 579 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
@@ -524,15 +582,15 @@ int radix_tree_tag_get(struct radix_tree_root *root,
524 * This is just a debug check. Later, we can bale as soon as 582 * This is just a debug check. Later, we can bale as soon as
525 * we see an unset tag. 583 * we see an unset tag.
526 */ 584 */
527 if (!tag_get(slot, tag, offset)) 585 if (!tag_get(node, tag, offset))
528 saw_unset_tag = 1; 586 saw_unset_tag = 1;
529 if (height == 1) { 587 if (height == 1) {
530 int ret = tag_get(slot, tag, offset); 588 int ret = tag_get(node, tag, offset);
531 589
532 BUG_ON(ret && saw_unset_tag); 590 BUG_ON(ret && saw_unset_tag);
533 return !!ret; 591 return !!ret;
534 } 592 }
535 slot = slot->slots[offset]; 593 node = rcu_dereference(node->slots[offset]);
536 shift -= RADIX_TREE_MAP_SHIFT; 594 shift -= RADIX_TREE_MAP_SHIFT;
537 height--; 595 height--;
538 } 596 }
@@ -541,47 +599,45 @@ EXPORT_SYMBOL(radix_tree_tag_get);
541#endif 599#endif
542 600
543static unsigned int 601static unsigned int
544__lookup(struct radix_tree_root *root, void **results, unsigned long index, 602__lookup(struct radix_tree_node *slot, void **results, unsigned long index,
545 unsigned int max_items, unsigned long *next_index) 603 unsigned int max_items, unsigned long *next_index)
546{ 604{
547 unsigned int nr_found = 0; 605 unsigned int nr_found = 0;
548 unsigned int shift, height; 606 unsigned int shift, height;
549 struct radix_tree_node *slot;
550 unsigned long i; 607 unsigned long i;
551 608
552 height = root->height; 609 height = slot->height;
553 if (height == 0) { 610 if (height == 0)
554 if (root->rnode && index == 0)
555 results[nr_found++] = root->rnode;
556 goto out; 611 goto out;
557 }
558
559 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 612 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
560 slot = root->rnode;
561 613
562 for ( ; height > 1; height--) { 614 for ( ; height > 1; height--) {
563 615 i = (index >> shift) & RADIX_TREE_MAP_MASK;
564 for (i = (index >> shift) & RADIX_TREE_MAP_MASK ; 616 for (;;) {
565 i < RADIX_TREE_MAP_SIZE; i++) {
566 if (slot->slots[i] != NULL) 617 if (slot->slots[i] != NULL)
567 break; 618 break;
568 index &= ~((1UL << shift) - 1); 619 index &= ~((1UL << shift) - 1);
569 index += 1UL << shift; 620 index += 1UL << shift;
570 if (index == 0) 621 if (index == 0)
571 goto out; /* 32-bit wraparound */ 622 goto out; /* 32-bit wraparound */
623 i++;
624 if (i == RADIX_TREE_MAP_SIZE)
625 goto out;
572 } 626 }
573 if (i == RADIX_TREE_MAP_SIZE)
574 goto out;
575 627
576 shift -= RADIX_TREE_MAP_SHIFT; 628 shift -= RADIX_TREE_MAP_SHIFT;
577 slot = slot->slots[i]; 629 slot = rcu_dereference(slot->slots[i]);
630 if (slot == NULL)
631 goto out;
578 } 632 }
579 633
580 /* Bottom level: grab some items */ 634 /* Bottom level: grab some items */
581 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) { 635 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
636 struct radix_tree_node *node;
582 index++; 637 index++;
583 if (slot->slots[i]) { 638 node = slot->slots[i];
584 results[nr_found++] = slot->slots[i]; 639 if (node) {
640 results[nr_found++] = rcu_dereference(node);
585 if (nr_found == max_items) 641 if (nr_found == max_items)
586 goto out; 642 goto out;
587 } 643 }
@@ -603,28 +659,51 @@ out:
603 * *@results. 659 * *@results.
604 * 660 *
605 * The implementation is naive. 661 * The implementation is naive.
662 *
663 * Like radix_tree_lookup, radix_tree_gang_lookup may be called under
664 * rcu_read_lock. In this case, rather than the returned results being
665 * an atomic snapshot of the tree at a single point in time, the semantics
666 * of an RCU protected gang lookup are as though multiple radix_tree_lookups
667 * have been issued in individual locks, and results stored in 'results'.
606 */ 668 */
607unsigned int 669unsigned int
608radix_tree_gang_lookup(struct radix_tree_root *root, void **results, 670radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
609 unsigned long first_index, unsigned int max_items) 671 unsigned long first_index, unsigned int max_items)
610{ 672{
611 const unsigned long max_index = radix_tree_maxindex(root->height); 673 unsigned long max_index;
674 struct radix_tree_node *node;
612 unsigned long cur_index = first_index; 675 unsigned long cur_index = first_index;
613 unsigned int ret = 0; 676 unsigned int ret;
677
678 node = rcu_dereference(root->rnode);
679 if (!node)
680 return 0;
614 681
682 if (radix_tree_is_direct_ptr(node)) {
683 if (first_index > 0)
684 return 0;
685 node = radix_tree_direct_to_ptr(node);
686 results[0] = rcu_dereference(node);
687 return 1;
688 }
689
690 max_index = radix_tree_maxindex(node->height);
691
692 ret = 0;
615 while (ret < max_items) { 693 while (ret < max_items) {
616 unsigned int nr_found; 694 unsigned int nr_found;
617 unsigned long next_index; /* Index of next search */ 695 unsigned long next_index; /* Index of next search */
618 696
619 if (cur_index > max_index) 697 if (cur_index > max_index)
620 break; 698 break;
621 nr_found = __lookup(root, results + ret, cur_index, 699 nr_found = __lookup(node, results + ret, cur_index,
622 max_items - ret, &next_index); 700 max_items - ret, &next_index);
623 ret += nr_found; 701 ret += nr_found;
624 if (next_index == 0) 702 if (next_index == 0)
625 break; 703 break;
626 cur_index = next_index; 704 cur_index = next_index;
627 } 705 }
706
628 return ret; 707 return ret;
629} 708}
630EXPORT_SYMBOL(radix_tree_gang_lookup); 709EXPORT_SYMBOL(radix_tree_gang_lookup);
@@ -634,55 +713,64 @@ EXPORT_SYMBOL(radix_tree_gang_lookup);
634 * open-coding the search. 713 * open-coding the search.
635 */ 714 */
636static unsigned int 715static unsigned int
637__lookup_tag(struct radix_tree_root *root, void **results, unsigned long index, 716__lookup_tag(struct radix_tree_node *slot, void **results, unsigned long index,
638 unsigned int max_items, unsigned long *next_index, unsigned int tag) 717 unsigned int max_items, unsigned long *next_index, unsigned int tag)
639{ 718{
640 unsigned int nr_found = 0; 719 unsigned int nr_found = 0;
641 unsigned int shift; 720 unsigned int shift, height;
642 unsigned int height = root->height;
643 struct radix_tree_node *slot;
644 721
645 if (height == 0) { 722 height = slot->height;
646 if (root->rnode && index == 0) 723 if (height == 0)
647 results[nr_found++] = root->rnode;
648 goto out; 724 goto out;
649 } 725 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
650
651 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
652 slot = root->rnode;
653 726
654 do { 727 while (height > 0) {
655 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK; 728 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ;
656 729
657 for ( ; i < RADIX_TREE_MAP_SIZE; i++) { 730 for (;;) {
658 if (tag_get(slot, tag, i)) { 731 if (tag_get(slot, tag, i))
659 BUG_ON(slot->slots[i] == NULL);
660 break; 732 break;
661 }
662 index &= ~((1UL << shift) - 1); 733 index &= ~((1UL << shift) - 1);
663 index += 1UL << shift; 734 index += 1UL << shift;
664 if (index == 0) 735 if (index == 0)
665 goto out; /* 32-bit wraparound */ 736 goto out; /* 32-bit wraparound */
737 i++;
738 if (i == RADIX_TREE_MAP_SIZE)
739 goto out;
666 } 740 }
667 if (i == RADIX_TREE_MAP_SIZE)
668 goto out;
669 height--; 741 height--;
670 if (height == 0) { /* Bottom level: grab some items */ 742 if (height == 0) { /* Bottom level: grab some items */
671 unsigned long j = index & RADIX_TREE_MAP_MASK; 743 unsigned long j = index & RADIX_TREE_MAP_MASK;
672 744
673 for ( ; j < RADIX_TREE_MAP_SIZE; j++) { 745 for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
746 struct radix_tree_node *node;
674 index++; 747 index++;
675 if (tag_get(slot, tag, j)) { 748 if (!tag_get(slot, tag, j))
676 BUG_ON(slot->slots[j] == NULL); 749 continue;
677 results[nr_found++] = slot->slots[j]; 750 node = slot->slots[j];
751 /*
752 * Even though the tag was found set, we need to
753 * recheck that we have a non-NULL node, because
754 * if this lookup is lockless, it may have been
755 * subsequently deleted.
756 *
757 * Similar care must be taken in any place that
758 * lookup ->slots[x] without a lock (ie. can't
759 * rely on its value remaining the same).
760 */
761 if (node) {
762 node = rcu_dereference(node);
763 results[nr_found++] = node;
678 if (nr_found == max_items) 764 if (nr_found == max_items)
679 goto out; 765 goto out;
680 } 766 }
681 } 767 }
682 } 768 }
683 shift -= RADIX_TREE_MAP_SHIFT; 769 shift -= RADIX_TREE_MAP_SHIFT;
684 slot = slot->slots[i]; 770 slot = rcu_dereference(slot->slots[i]);
685 } while (height > 0); 771 if (slot == NULL)
772 break;
773 }
686out: 774out:
687 *next_index = index; 775 *next_index = index;
688 return nr_found; 776 return nr_found;
@@ -706,27 +794,44 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
706 unsigned long first_index, unsigned int max_items, 794 unsigned long first_index, unsigned int max_items,
707 unsigned int tag) 795 unsigned int tag)
708{ 796{
709 const unsigned long max_index = radix_tree_maxindex(root->height); 797 struct radix_tree_node *node;
798 unsigned long max_index;
710 unsigned long cur_index = first_index; 799 unsigned long cur_index = first_index;
711 unsigned int ret = 0; 800 unsigned int ret;
712 801
713 /* check the root's tag bit */ 802 /* check the root's tag bit */
714 if (!root_tag_get(root, tag)) 803 if (!root_tag_get(root, tag))
715 return 0; 804 return 0;
716 805
806 node = rcu_dereference(root->rnode);
807 if (!node)
808 return 0;
809
810 if (radix_tree_is_direct_ptr(node)) {
811 if (first_index > 0)
812 return 0;
813 node = radix_tree_direct_to_ptr(node);
814 results[0] = rcu_dereference(node);
815 return 1;
816 }
817
818 max_index = radix_tree_maxindex(node->height);
819
820 ret = 0;
717 while (ret < max_items) { 821 while (ret < max_items) {
718 unsigned int nr_found; 822 unsigned int nr_found;
719 unsigned long next_index; /* Index of next search */ 823 unsigned long next_index; /* Index of next search */
720 824
721 if (cur_index > max_index) 825 if (cur_index > max_index)
722 break; 826 break;
723 nr_found = __lookup_tag(root, results + ret, cur_index, 827 nr_found = __lookup_tag(node, results + ret, cur_index,
724 max_items - ret, &next_index, tag); 828 max_items - ret, &next_index, tag);
725 ret += nr_found; 829 ret += nr_found;
726 if (next_index == 0) 830 if (next_index == 0)
727 break; 831 break;
728 cur_index = next_index; 832 cur_index = next_index;
729 } 833 }
834
730 return ret; 835 return ret;
731} 836}
732EXPORT_SYMBOL(radix_tree_gang_lookup_tag); 837EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
@@ -742,8 +847,19 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
742 root->rnode->count == 1 && 847 root->rnode->count == 1 &&
743 root->rnode->slots[0]) { 848 root->rnode->slots[0]) {
744 struct radix_tree_node *to_free = root->rnode; 849 struct radix_tree_node *to_free = root->rnode;
850 void *newptr;
745 851
746 root->rnode = to_free->slots[0]; 852 /*
853 * We don't need rcu_assign_pointer(), since we are simply
854 * moving the node from one part of the tree to another. If
855 * it was safe to dereference the old pointer to it
856 * (to_free->slots[0]), it will be safe to dereference the new
857 * one (root->rnode).
858 */
859 newptr = to_free->slots[0];
860 if (root->height == 1)
861 newptr = radix_tree_ptr_to_direct(newptr);
862 root->rnode = newptr;
747 root->height--; 863 root->height--;
748 /* must only free zeroed nodes into the slab */ 864 /* must only free zeroed nodes into the slab */
749 tag_clear(to_free, 0, 0); 865 tag_clear(to_free, 0, 0);
@@ -767,6 +883,7 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
767{ 883{
768 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; 884 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
769 struct radix_tree_node *slot = NULL; 885 struct radix_tree_node *slot = NULL;
886 struct radix_tree_node *to_free;
770 unsigned int height, shift; 887 unsigned int height, shift;
771 int tag; 888 int tag;
772 int offset; 889 int offset;
@@ -777,6 +894,7 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
777 894
778 slot = root->rnode; 895 slot = root->rnode;
779 if (height == 0 && root->rnode) { 896 if (height == 0 && root->rnode) {
897 slot = radix_tree_direct_to_ptr(slot);
780 root_tag_clear_all(root); 898 root_tag_clear_all(root);
781 root->rnode = NULL; 899 root->rnode = NULL;
782 goto out; 900 goto out;
@@ -809,10 +927,17 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
809 radix_tree_tag_clear(root, index, tag); 927 radix_tree_tag_clear(root, index, tag);
810 } 928 }
811 929
930 to_free = NULL;
812 /* Now free the nodes we do not need anymore */ 931 /* Now free the nodes we do not need anymore */
813 while (pathp->node) { 932 while (pathp->node) {
814 pathp->node->slots[pathp->offset] = NULL; 933 pathp->node->slots[pathp->offset] = NULL;
815 pathp->node->count--; 934 pathp->node->count--;
935 /*
936 * Queue the node for deferred freeing after the
937 * last reference to it disappears (set NULL, above).
938 */
939 if (to_free)
940 radix_tree_node_free(to_free);
816 941
817 if (pathp->node->count) { 942 if (pathp->node->count) {
818 if (pathp->node == root->rnode) 943 if (pathp->node == root->rnode)
@@ -821,13 +946,15 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
821 } 946 }
822 947
823 /* Node with zero slots in use so free it */ 948 /* Node with zero slots in use so free it */
824 radix_tree_node_free(pathp->node); 949 to_free = pathp->node;
825
826 pathp--; 950 pathp--;
951
827 } 952 }
828 root_tag_clear_all(root); 953 root_tag_clear_all(root);
829 root->height = 0; 954 root->height = 0;
830 root->rnode = NULL; 955 root->rnode = NULL;
956 if (to_free)
957 radix_tree_node_free(to_free);
831 958
832out: 959out:
833 return slot; 960 return slot;
@@ -846,7 +973,7 @@ int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
846EXPORT_SYMBOL(radix_tree_tagged); 973EXPORT_SYMBOL(radix_tree_tagged);
847 974
848static void 975static void
849radix_tree_node_ctor(void *node, kmem_cache_t *cachep, unsigned long flags) 976radix_tree_node_ctor(void *node, struct kmem_cache *cachep, unsigned long flags)
850{ 977{
851 memset(node, 0, sizeof(struct radix_tree_node)); 978 memset(node, 0, sizeof(struct radix_tree_node));
852} 979}
@@ -869,7 +996,6 @@ static __init void radix_tree_init_maxindex(void)
869 height_to_maxindex[i] = __maxindex(i); 996 height_to_maxindex[i] = __maxindex(i);
870} 997}
871 998
872#ifdef CONFIG_HOTPLUG_CPU
873static int radix_tree_callback(struct notifier_block *nfb, 999static int radix_tree_callback(struct notifier_block *nfb,
874 unsigned long action, 1000 unsigned long action,
875 void *hcpu) 1001 void *hcpu)
@@ -889,7 +1015,6 @@ static int radix_tree_callback(struct notifier_block *nfb,
889 } 1015 }
890 return NOTIFY_OK; 1016 return NOTIFY_OK;
891} 1017}
892#endif /* CONFIG_HOTPLUG_CPU */
893 1018
894void __init radix_tree_init(void) 1019void __init radix_tree_init(void)
895{ 1020{