NFSd: call svc rpcbind cleanup explicitly

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

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 7ea2e03..a2f9da5 100644 (file)
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -823,8 +823,8 @@ unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
 EXPORT_SYMBOL(radix_tree_prev_hole);
 
 static unsigned int
-__lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
-       unsigned int max_items, unsigned long *next_index)
+__lookup(struct radix_tree_node *slot, void ***results, unsigned long *indices,
+       unsigned long index, unsigned int max_items, unsigned long *next_index)
 {
        unsigned int nr_found = 0;
        unsigned int shift, height;
@@ -857,12 +857,16 @@ __lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
 
        /* Bottom level: grab some items */
        for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
-               index++;
                if (slot->slots[i]) {
-                       results[nr_found++] = &(slot->slots[i]);
-                       if (nr_found == max_items)
+                       results[nr_found] = &(slot->slots[i]);
+                       if (indices)
+                               indices[nr_found] = index;
+                       if (++nr_found == max_items) {
+                               index++;
                                goto out;
+                       }
                }
+               index++;
        }
 out:
        *next_index = index;
@@ -918,8 +922,8 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
 
                if (cur_index > max_index)
                        break;
-               slots_found = __lookup(node, (void ***)results + ret, cur_index,
-                                       max_items - ret, &next_index);
+               slots_found = __lookup(node, (void ***)results + ret, NULL,
+                               cur_index, max_items - ret, &next_index);
                nr_found = 0;
                for (i = 0; i < slots_found; i++) {
                        struct radix_tree_node *slot;
@@ -944,6 +948,7 @@ EXPORT_SYMBOL(radix_tree_gang_lookup);
  *     radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
  *     @root:          radix tree root
  *     @results:       where the results of the lookup are placed
+ *     @indices:       where their indices should be placed (but usually NULL)
  *     @first_index:   start the lookup from this key
  *     @max_items:     place up to this many items at *results
  *
@@ -958,7 +963,8 @@ EXPORT_SYMBOL(radix_tree_gang_lookup);
  *     protection, radix_tree_deref_slot may fail requiring a retry.
  */
 unsigned int
-radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
+radix_tree_gang_lookup_slot(struct radix_tree_root *root,
+                       void ***results, unsigned long *indices,
                        unsigned long first_index, unsigned int max_items)
 {
        unsigned long max_index;
@@ -974,6 +980,8 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
                if (first_index > 0)
                        return 0;
                results[0] = (void **)&root->rnode;
+               if (indices)
+                       indices[0] = 0;
                return 1;
        }
        node = indirect_to_ptr(node);
@@ -987,8 +995,9 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
 
                if (cur_index > max_index)
                        break;
-               slots_found = __lookup(node, results + ret, cur_index,
-                                       max_items - ret, &next_index);
+               slots_found = __lookup(node, results + ret,
+                               indices ? indices + ret : NULL,
+                               cur_index, max_items - ret, &next_index);
                ret += slots_found;
                if (next_index == 0)
                        break;
@@ -1194,6 +1203,98 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
 }
 EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
 
+#if defined(CONFIG_SHMEM) && defined(CONFIG_SWAP)
+#include <linux/sched.h> /* for cond_resched() */
+
+/*
+ * This linear search is at present only useful to shmem_unuse_inode().
+ */
+static unsigned long __locate(struct radix_tree_node *slot, void *item,
+                             unsigned long index, unsigned long *found_index)
+{
+       unsigned int shift, height;
+       unsigned long i;
+
+       height = slot->height;
+       shift = (height-1) * RADIX_TREE_MAP_SHIFT;
+
+       for ( ; height > 1; height--) {
+               i = (index >> shift) & RADIX_TREE_MAP_MASK;
+               for (;;) {
+                       if (slot->slots[i] != NULL)
+                               break;
+                       index &= ~((1UL << shift) - 1);
+                       index += 1UL << shift;
+                       if (index == 0)
+                               goto out;       /* 32-bit wraparound */
+                       i++;
+                       if (i == RADIX_TREE_MAP_SIZE)
+                               goto out;
+               }
+
+               shift -= RADIX_TREE_MAP_SHIFT;
+               slot = rcu_dereference_raw(slot->slots[i]);
+               if (slot == NULL)
+                       goto out;
+       }
+
+       /* Bottom level: check items */
+       for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
+               if (slot->slots[i] == item) {
+                       *found_index = index + i;
+                       index = 0;
+                       goto out;
+               }
+       }
+       index += RADIX_TREE_MAP_SIZE;
+out:
+       return index;
+}
+
+/**
+ *     radix_tree_locate_item - search through radix tree for item
+ *     @root:          radix tree root
+ *     @item:          item to be found
+ *
+ *     Returns index where item was found, or -1 if not found.
+ *     Caller must hold no lock (since this time-consuming function needs
+ *     to be preemptible), and must check afterwards if item is still there.
+ */
+unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
+{
+       struct radix_tree_node *node;
+       unsigned long max_index;
+       unsigned long cur_index = 0;
+       unsigned long found_index = -1;
+
+       do {
+               rcu_read_lock();
+               node = rcu_dereference_raw(root->rnode);
+               if (!radix_tree_is_indirect_ptr(node)) {
+                       rcu_read_unlock();
+                       if (node == item)
+                               found_index = 0;
+                       break;
+               }
+
+               node = indirect_to_ptr(node);
+               max_index = radix_tree_maxindex(node->height);
+               if (cur_index > max_index)
+                       break;
+
+               cur_index = __locate(node, item, cur_index, &found_index);
+               rcu_read_unlock();
+               cond_resched();
+       } while (cur_index != 0 && cur_index <= max_index);
+
+       return found_index;
+}
+#else
+unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
+{
+       return -1;
+}
+#endif /* CONFIG_SHMEM && CONFIG_SWAP */
 
 /**
  *     radix_tree_shrink    -    shrink height of a radix tree to minimal