3 files changed, 54 insertions, 15 deletions

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 23241c2fecce..b7edf8251455 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -39,7 +39,15 @@
  * when it is shrunk, before we rcu free the node. See shrink code for
  * details.
  */
-#define RADIX_TREE_INDIRECT_PTR 1
+#define RADIX_TREE_INDIRECT_PTR         1
+/*
+ * A common use of the radix tree is to store pointers to struct pages;
+ * but shmem/tmpfs needs also to store swap entries in the same tree:
+ * those are marked as exceptional entries to distinguish them.
+ * EXCEPTIONAL_ENTRY tests the bit, EXCEPTIONAL_SHIFT shifts content past it.
+ */
+#define RADIX_TREE_EXCEPTIONAL_ENTRY    2
+#define RADIX_TREE_EXCEPTIONAL_SHIFT    2
 
 #define radix_tree_indirect_to_ptr(ptr) \
         radix_tree_indirect_to_ptr((void __force *)(ptr))
@@ -174,6 +182,28 @@ static inline int radix_tree_deref_retry(void *arg)
 }
 
 /**
+ * radix_tree_exceptional_entry - radix_tree_deref_slot gave exceptional entry?
+ * @arg:        value returned by radix_tree_deref_slot
+ * Returns:     0 if well-aligned pointer, non-0 if exceptional entry.
+ */
+static inline int radix_tree_exceptional_entry(void *arg)
+{
+        /* Not unlikely because radix_tree_exception often tested first */
+        return (unsigned long)arg & RADIX_TREE_EXCEPTIONAL_ENTRY;
+}
+
+/**
+ * radix_tree_exception - radix_tree_deref_slot returned either exception?
+ * @arg:        value returned by radix_tree_deref_slot
+ * Returns:     0 if well-aligned pointer, non-0 if either kind of exception.
+ */
+static inline int radix_tree_exception(void *arg)
+{
+        return unlikely((unsigned long)arg &
+                (RADIX_TREE_INDIRECT_PTR | RADIX_TREE_EXCEPTIONAL_ENTRY));
+}
+
+/**
  * radix_tree_replace_slot      - replace item in a slot
  * @pslot:      pointer to slot, returned by radix_tree_lookup_slot
  * @item:       new item to store in the slot.
@@ -194,8 +224,8 @@ void *radix_tree_delete(struct radix_tree_root *, unsigned long);
 unsigned int
 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
                         unsigned long first_index, unsigned int max_items);
-unsigned int
-radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
+unsigned int 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 radix_tree_next_hole(struct radix_tree_root *root,
                                 unsigned long index, unsigned long max_scan);
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 7ea2e033d715..348eaefbed74 100644
--- 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;
diff --git a/mm/filemap.c b/mm/filemap.c
index 867d40222ec7..b83aebfd0a00 100644
--- a/mm/filemap.c
+++ b/mm/filemap.c
@@ -840,7 +840,7 @@ unsigned find_get_pages(struct address_space *mapping, pgoff_t start,
         rcu_read_lock();
 restart:
         nr_found = radix_tree_gang_lookup_slot(&mapping->page_tree,
-                                (void ***)pages, start, nr_pages);
+                                (void ***)pages, NULL, start, nr_pages);
         ret = 0;
         for (i = 0; i < nr_found; i++) {
                 struct page *page;
@@ -903,7 +903,7 @@ unsigned find_get_pages_contig(struct address_space *mapping, pgoff_t index,
         rcu_read_lock();
 restart:
         nr_found = radix_tree_gang_lookup_slot(&mapping->page_tree,
-                                (void ***)pages, index, nr_pages);
+                                (void ***)pages, NULL, index, nr_pages);
         ret = 0;
         for (i = 0; i < nr_found; i++) {
                 struct page *page;