summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig.debug18
-rw-r--r--lib/radix-tree.c132
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;
}
generated by cgit v1.2.3 (git 2.0.4) at 2024-11-14 14:59:14 +0000