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;
                 }