Un-inline the core-dump helper functions

[pandora-kernel.git] / lib / radix-tree.c

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index e907858..efd16fa 100644 (file)
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -174,14 +174,16 @@ static void radix_tree_node_rcu_free(struct rcu_head *head)
 {
        struct radix_tree_node *node =
                        container_of(head, struct radix_tree_node, rcu_head);
+       int i;
 
        /*
         * must only free zeroed nodes into the slab. radix_tree_shrink
         * can leave us with a non-NULL entry in the first slot, so clear
         * that here to make sure.
         */
-       tag_clear(node, 0, 0);
-       tag_clear(node, 1, 0);
+       for (i = 0; i < RADIX_TREE_MAX_TAGS; i++)
+               tag_clear(node, i, 0);
+
        node->slots[0] = NULL;
        node->count = 0;
 
@@ -623,17 +625,30 @@ EXPORT_SYMBOL(radix_tree_tag_get);
  * also settag. The function stops either after tagging nr_to_tag items or
  * after reaching last_index.
  *
+ * The tags must be set from the leaf level only and propagated back up the
+ * path to the root. We must do this so that we resolve the full path before
+ * setting any tags on intermediate nodes. If we set tags as we descend, then
+ * we can get to the leaf node and find that the index that has the iftag
+ * set is outside the range we are scanning. This reults in dangling tags and
+ * can lead to problems with later tag operations (e.g. livelocks on lookups).
+ *
  * The function returns number of leaves where the tag was set and sets
  * *first_indexp to the first unscanned index.
+ * WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must
+ * be prepared to handle that.
  */
 unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
                unsigned long *first_indexp, unsigned long last_index,
                unsigned long nr_to_tag,
                unsigned int iftag, unsigned int settag)
 {
-       unsigned int height = root->height, shift;
-       unsigned long tagged = 0, index = *first_indexp;
-       struct radix_tree_node *open_slots[height], *slot;
+       unsigned int height = root->height;
+       struct radix_tree_path path[height];
+       struct radix_tree_path *pathp = path;
+       struct radix_tree_node *slot;
+       unsigned int shift;
+       unsigned long tagged = 0;
+       unsigned long index = *first_indexp;
 
        last_index = min(last_index, radix_tree_maxindex(height));
        if (index > last_index)
@@ -653,6 +668,13 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
        shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
        slot = radix_tree_indirect_to_ptr(root->rnode);
 
+       /*
+        * we fill the path from (root->height - 2) to 0, leaving the index at
+        * (root->height - 1) as a terminator. Zero the node in the terminator
+        * so that we can use this to end walk loops back up the path.
+        */
+       path[height - 1].node = NULL;
+
        for (;;) {
                int offset;
 
@@ -661,21 +683,35 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
                        goto next;
                if (!tag_get(slot, iftag, offset))
                        goto next;
+               if (height > 1) {
+                       /* Go down one level */
+                       height--;
+                       shift -= RADIX_TREE_MAP_SHIFT;
+                       path[height - 1].node = slot;
+                       path[height - 1].offset = offset;
+                       slot = slot->slots[offset];
+                       continue;
+               }
+
+               /* tag the leaf */
+               tagged++;
                tag_set(slot, settag, offset);
-               if (height == 1) {
-                       tagged++;
-                       goto next;
+
+               /* walk back up the path tagging interior nodes */
+               pathp = &path[0];
+               while (pathp->node) {
+                       /* stop if we find a node with the tag already set */
+                       if (tag_get(pathp->node, settag, pathp->offset))
+                               break;
+                       tag_set(pathp->node, settag, pathp->offset);
+                       pathp++;
                }
-               /* Go down one level */
-               height--;
-               shift -= RADIX_TREE_MAP_SHIFT;
-               open_slots[height] = slot;
-               slot = slot->slots[offset];
-               continue;
+
 next:
                /* Go to next item at level determined by 'shift' */
                index = ((index >> shift) + 1) << shift;
-               if (index > last_index)
+               /* Overflow can happen when last_index is ~0UL... */
+               if (index > last_index || !index)
                        break;
                if (tagged >= nr_to_tag)
                        break;
@@ -685,7 +721,7 @@ next:
                         * last_index is guaranteed to be in the tree, what
                         * we do below cannot wander astray.
                         */
-                       slot = open_slots[height];
+                       slot = path[height - 1].node;
                        height++;
                        shift += RADIX_TREE_MAP_SHIFT;
                }