diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Kconfig.debug | 18 | ||||
| -rw-r--r-- | lib/radix-tree.c | 132 |
2 files changed, 118 insertions, 32 deletions
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 396c38b3cb69..7d16e6433302 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -413,6 +413,24 @@ config FORCED_INLINING become the default in the future, until then this option is there to test gcc for this. +config BOOT_PRINTK_DELAY + bool "Delay each boot printk message by N milliseconds" + depends on DEBUG_KERNEL && PRINTK && GENERIC_CALIBRATE_DELAY + help + This build option allows you to read kernel boot messages + by inserting a short delay after each one. The delay is + specified in milliseconds on the kernel command line, + using "boot_delay=N". + + It is likely that you would also need to use "lpj=M" to preset + the "loops per jiffie" value. + See a previous boot log for the "lpj" value to use for your + system, and then set "lpj=M" before setting "boot_delay=N". + NOTE: Using this option may adversely affect SMP systems. + I.e., processors other than the first one may not boot up. + BOOT_PRINTK_DELAY also may cause DETECT_SOFTLOCKUP to detect + what it believes to be lockup conditions. + config RCU_TORTURE_TEST tristate "torture tests for RCU" depends on DEBUG_KERNEL diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 514efb200be6..6b26f9d39800 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -60,9 +60,14 @@ struct radix_tree_path { }; #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) -#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2) +#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \ + RADIX_TREE_MAP_SHIFT)) -static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly; +/* + * The height_to_maxindex array needs to be one deeper than the maximum + * path as height 0 holds only 1 entry. + */ +static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly; /* * Radix tree node cache. @@ -93,7 +98,8 @@ radix_tree_node_alloc(struct radix_tree_root *root) struct radix_tree_node *ret; gfp_t gfp_mask = root_gfp_mask(root); - ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); + ret = kmem_cache_alloc(radix_tree_node_cachep, + set_migrateflags(gfp_mask, __GFP_RECLAIMABLE)); if (ret == NULL && !(gfp_mask & __GFP_WAIT)) { struct radix_tree_preload *rtp; @@ -104,7 +110,7 @@ radix_tree_node_alloc(struct radix_tree_root *root) rtp->nr--; } } - BUG_ON(radix_tree_is_direct_ptr(ret)); + BUG_ON(radix_tree_is_indirect_ptr(ret)); return ret; } @@ -137,7 +143,8 @@ int radix_tree_preload(gfp_t gfp_mask) rtp = &__get_cpu_var(radix_tree_preloads); while (rtp->nr < ARRAY_SIZE(rtp->nodes)) { preempt_enable(); - node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); + node = kmem_cache_alloc(radix_tree_node_cachep, + set_migrateflags(gfp_mask, __GFP_RECLAIMABLE)); if (node == NULL) goto out; preempt_disable(); @@ -240,7 +247,7 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) return -ENOMEM; /* Increase the height. */ - node->slots[0] = radix_tree_direct_to_ptr(root->rnode); + node->slots[0] = radix_tree_indirect_to_ptr(root->rnode); /* Propagate the aggregated tag info into the new root */ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { @@ -251,6 +258,7 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) newheight = root->height+1; node->height = newheight; node->count = 1; + node = radix_tree_ptr_to_indirect(node); rcu_assign_pointer(root->rnode, node); root->height = newheight; } while (height > root->height); @@ -274,7 +282,7 @@ int radix_tree_insert(struct radix_tree_root *root, int offset; int error; - BUG_ON(radix_tree_is_direct_ptr(item)); + BUG_ON(radix_tree_is_indirect_ptr(item)); /* Make sure the tree is high enough. */ if (index > radix_tree_maxindex(root->height)) { @@ -283,7 +291,8 @@ int radix_tree_insert(struct radix_tree_root *root, return error; } - slot = root->rnode; + slot = radix_tree_indirect_to_ptr(root->rnode); + height = root->height; shift = (height-1) * RADIX_TREE_MAP_SHIFT; @@ -298,7 +307,8 @@ int radix_tree_insert(struct radix_tree_root *root, rcu_assign_pointer(node->slots[offset], slot); node->count++; } else - rcu_assign_pointer(root->rnode, slot); + rcu_assign_pointer(root->rnode, + radix_tree_ptr_to_indirect(slot)); } /* Go a level down */ @@ -318,7 +328,7 @@ int radix_tree_insert(struct radix_tree_root *root, BUG_ON(tag_get(node, 0, offset)); BUG_ON(tag_get(node, 1, offset)); } else { - rcu_assign_pointer(root->rnode, radix_tree_ptr_to_direct(item)); + rcu_assign_pointer(root->rnode, item); BUG_ON(root_tag_get(root, 0)); BUG_ON(root_tag_get(root, 1)); } @@ -350,11 +360,12 @@ void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) if (node == NULL) return NULL; - if (radix_tree_is_direct_ptr(node)) { + if (!radix_tree_is_indirect_ptr(node)) { if (index > 0) return NULL; return (void **)&root->rnode; } + node = radix_tree_indirect_to_ptr(node); height = node->height; if (index > radix_tree_maxindex(height)) @@ -398,11 +409,12 @@ void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) if (node == NULL) return NULL; - if (radix_tree_is_direct_ptr(node)) { + if (!radix_tree_is_indirect_ptr(node)) { if (index > 0) return NULL; - return radix_tree_direct_to_ptr(node); + return node; } + node = radix_tree_indirect_to_ptr(node); height = node->height; if (index > radix_tree_maxindex(height)) @@ -447,7 +459,7 @@ void *radix_tree_tag_set(struct radix_tree_root *root, height = root->height; BUG_ON(index > radix_tree_maxindex(height)); - slot = root->rnode; + slot = radix_tree_indirect_to_ptr(root->rnode); shift = (height - 1) * RADIX_TREE_MAP_SHIFT; while (height > 0) { @@ -487,7 +499,11 @@ EXPORT_SYMBOL(radix_tree_tag_set); void *radix_tree_tag_clear(struct radix_tree_root *root, unsigned long index, unsigned int tag) { - struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; + /* + * The radix tree path needs to be one longer than the maximum path + * since the "list" is null terminated. + */ + struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path; struct radix_tree_node *slot = NULL; unsigned int height, shift; @@ -497,7 +513,7 @@ void *radix_tree_tag_clear(struct radix_tree_root *root, shift = (height - 1) * RADIX_TREE_MAP_SHIFT; pathp->node = NULL; - slot = root->rnode; + slot = radix_tree_indirect_to_ptr(root->rnode); while (height > 0) { int offset; @@ -562,8 +578,9 @@ int radix_tree_tag_get(struct radix_tree_root *root, if (node == NULL) return 0; - if (radix_tree_is_direct_ptr(node)) + if (!radix_tree_is_indirect_ptr(node)) return (index == 0); + node = radix_tree_indirect_to_ptr(node); height = node->height; if (index > radix_tree_maxindex(height)) @@ -599,6 +616,42 @@ int radix_tree_tag_get(struct radix_tree_root *root, EXPORT_SYMBOL(radix_tree_tag_get); #endif +/** + * radix_tree_next_hole - find the next hole (not-present entry) + * @root: tree root + * @index: index key + * @max_scan: maximum range to search + * + * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest + * indexed hole. + * + * Returns: the index of the hole if found, otherwise returns an index + * outside of the set specified (in which case 'return - index >= max_scan' + * will be true). + * + * radix_tree_next_hole may be called under rcu_read_lock. However, like + * radix_tree_gang_lookup, this will not atomically search a snapshot of the + * tree at a single point in time. For example, if a hole is created at index + * 5, then subsequently a hole is created at index 10, radix_tree_next_hole + * covering both indexes may return 10 if called under rcu_read_lock. + */ +unsigned long radix_tree_next_hole(struct radix_tree_root *root, + unsigned long index, unsigned long max_scan) +{ + unsigned long i; + + for (i = 0; i < max_scan; i++) { + if (!radix_tree_lookup(root, index)) + break; + index++; + if (index == 0) + break; + } + + return index; +} +EXPORT_SYMBOL(radix_tree_next_hole); + static unsigned int __lookup(struct radix_tree_node *slot, void **results, unsigned long index, unsigned int max_items, unsigned long *next_index) @@ -680,13 +733,13 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results, if (!node) return 0; - if (radix_tree_is_direct_ptr(node)) { + if (!radix_tree_is_indirect_ptr(node)) { if (first_index > 0) return 0; - node = radix_tree_direct_to_ptr(node); - results[0] = rcu_dereference(node); + results[0] = node; return 1; } + node = radix_tree_indirect_to_ptr(node); max_index = radix_tree_maxindex(node->height); @@ -808,13 +861,13 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, if (!node) return 0; - if (radix_tree_is_direct_ptr(node)) { + if (!radix_tree_is_indirect_ptr(node)) { if (first_index > 0) return 0; - node = radix_tree_direct_to_ptr(node); - results[0] = rcu_dereference(node); + results[0] = node; return 1; } + node = radix_tree_indirect_to_ptr(node); max_index = radix_tree_maxindex(node->height); @@ -844,12 +897,22 @@ EXPORT_SYMBOL(radix_tree_gang_lookup_tag); static inline void radix_tree_shrink(struct radix_tree_root *root) { /* try to shrink tree height */ - while (root->height > 0 && - root->rnode->count == 1 && - root->rnode->slots[0]) { + while (root->height > 0) { struct radix_tree_node *to_free = root->rnode; void *newptr; + BUG_ON(!radix_tree_is_indirect_ptr(to_free)); + to_free = radix_tree_indirect_to_ptr(to_free); + + /* + * The candidate node has more than one child, or its child + * is not at the leftmost slot, we cannot shrink. + */ + if (to_free->count != 1) + break; + if (!to_free->slots[0]) + break; + /* * We don't need rcu_assign_pointer(), since we are simply * moving the node from one part of the tree to another. If @@ -858,8 +921,8 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) * one (root->rnode). */ newptr = to_free->slots[0]; - if (root->height == 1) - newptr = radix_tree_ptr_to_direct(newptr); + if (root->height > 1) + newptr = radix_tree_ptr_to_indirect(newptr); root->rnode = newptr; root->height--; /* must only free zeroed nodes into the slab */ @@ -882,7 +945,11 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) */ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) { - struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; + /* + * The radix tree path needs to be one longer than the maximum path + * since the "list" is null terminated. + */ + struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path; struct radix_tree_node *slot = NULL; struct radix_tree_node *to_free; unsigned int height, shift; @@ -894,12 +961,12 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) goto out; slot = root->rnode; - if (height == 0 && root->rnode) { - slot = radix_tree_direct_to_ptr(slot); + if (height == 0) { root_tag_clear_all(root); root->rnode = NULL; goto out; } + slot = radix_tree_indirect_to_ptr(slot); shift = (height - 1) * RADIX_TREE_MAP_SHIFT; pathp->node = NULL; @@ -941,7 +1008,8 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) radix_tree_node_free(to_free); if (pathp->node->count) { - if (pathp->node == root->rnode) + if (pathp->node == + radix_tree_indirect_to_ptr(root->rnode)) radix_tree_shrink(root); goto out; } |