aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorHugh Dickins <hughd@google.com>2011-08-03 19:21:18 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2011-08-03 20:25:22 -0400
commit6328650bb4d854a7dc1498d1c0048b838b0d340c (patch)
tree0e265dc86f7c4451647c1e227843cdd1530f9651 /lib
parent70d327198a434edb95b3d858bc8010b8add28e3e (diff)
radix_tree: exceptional entries and indices
A patchset to extend tmpfs to MAX_LFS_FILESIZE by abandoning its peculiar swap vector, instead keeping a file's swap entries in the same radix tree as its struct page pointers: thus saving memory, and simplifying its code and locking. This patch: The radix_tree is used by several subsystems for different purposes. A major use is to store the struct page pointers of a file's pagecache for memory management. But what if mm wanted to store something other than page pointers there too? The low bit of a radix_tree entry is already used to denote an indirect pointer, for internal use, and the unlikely radix_tree_deref_retry() case. Define the next bit as denoting an exceptional entry, and supply inline functions radix_tree_exception() to return non-0 in either unlikely case, and radix_tree_exceptional_entry() to return non-0 in the second case. If a subsystem already uses radix_tree with that bit set, no problem: it does not affect internal workings at all, but is defined for the convenience of those storing well-aligned pointers in the radix_tree. The radix_tree_gang_lookups have an implicit assumption that the caller can deduce the offset of each entry returned e.g. by the page->index of a struct page. But that may not be feasible for some kinds of item to be stored there. radix_tree_gang_lookup_slot() allow for an optional indices argument, output array in which to return those offsets. The same could be added to other radix_tree_gang_lookups, but for now keep it to the only one for which we need it. Signed-off-by: Hugh Dickins <hughd@google.com> Acked-by: Rik van Riel <riel@redhat.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib')
-rw-r--r--lib/radix-tree.c29
1 files changed, 19 insertions, 10 deletions
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,
823EXPORT_SYMBOL(radix_tree_prev_hole); 823EXPORT_SYMBOL(radix_tree_prev_hole);
824 824
825static unsigned int 825static unsigned int
826__lookup(struct radix_tree_node *slot, void ***results, unsigned long index, 826__lookup(struct radix_tree_node *slot, void ***results, unsigned long *indices,
827 unsigned int max_items, unsigned long *next_index) 827 unsigned long index, unsigned int max_items, unsigned long *next_index)
828{ 828{
829 unsigned int nr_found = 0; 829 unsigned int nr_found = 0;
830 unsigned int shift, height; 830 unsigned int shift, height;
@@ -857,12 +857,16 @@ __lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
857 857
858 /* Bottom level: grab some items */ 858 /* Bottom level: grab some items */
859 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) { 859 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
860 index++;
861 if (slot->slots[i]) { 860 if (slot->slots[i]) {
862 results[nr_found++] = &(slot->slots[i]); 861 results[nr_found] = &(slot->slots[i]);
863 if (nr_found == max_items) 862 if (indices)
863 indices[nr_found] = index;
864 if (++nr_found == max_items) {
865 index++;
864 goto out; 866 goto out;
867 }
865 } 868 }
869 index++;
866 } 870 }
867out: 871out:
868 *next_index = index; 872 *next_index = index;
@@ -918,8 +922,8 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
918 922
919 if (cur_index > max_index) 923 if (cur_index > max_index)
920 break; 924 break;
921 slots_found = __lookup(node, (void ***)results + ret, cur_index, 925 slots_found = __lookup(node, (void ***)results + ret, NULL,
922 max_items - ret, &next_index); 926 cur_index, max_items - ret, &next_index);
923 nr_found = 0; 927 nr_found = 0;
924 for (i = 0; i < slots_found; i++) { 928 for (i = 0; i < slots_found; i++) {
925 struct radix_tree_node *slot; 929 struct radix_tree_node *slot;
@@ -944,6 +948,7 @@ EXPORT_SYMBOL(radix_tree_gang_lookup);
944 * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree 948 * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
945 * @root: radix tree root 949 * @root: radix tree root
946 * @results: where the results of the lookup are placed 950 * @results: where the results of the lookup are placed
951 * @indices: where their indices should be placed (but usually NULL)
947 * @first_index: start the lookup from this key 952 * @first_index: start the lookup from this key
948 * @max_items: place up to this many items at *results 953 * @max_items: place up to this many items at *results
949 * 954 *
@@ -958,7 +963,8 @@ EXPORT_SYMBOL(radix_tree_gang_lookup);
958 * protection, radix_tree_deref_slot may fail requiring a retry. 963 * protection, radix_tree_deref_slot may fail requiring a retry.
959 */ 964 */
960unsigned int 965unsigned int
961radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results, 966radix_tree_gang_lookup_slot(struct radix_tree_root *root,
967 void ***results, unsigned long *indices,
962 unsigned long first_index, unsigned int max_items) 968 unsigned long first_index, unsigned int max_items)
963{ 969{
964 unsigned long max_index; 970 unsigned long max_index;
@@ -974,6 +980,8 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
974 if (first_index > 0) 980 if (first_index > 0)
975 return 0; 981 return 0;
976 results[0] = (void **)&root->rnode; 982 results[0] = (void **)&root->rnode;
983 if (indices)
984 indices[0] = 0;
977 return 1; 985 return 1;
978 } 986 }
979 node = indirect_to_ptr(node); 987 node = indirect_to_ptr(node);
@@ -987,8 +995,9 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
987 995
988 if (cur_index > max_index) 996 if (cur_index > max_index)
989 break; 997 break;
990 slots_found = __lookup(node, results + ret, cur_index, 998 slots_found = __lookup(node, results + ret,
991 max_items - ret, &next_index); 999 indices ? indices + ret : NULL,
1000 cur_index, max_items - ret, &next_index);
992 ret += slots_found; 1001 ret += slots_found;
993 if (next_index == 0) 1002 if (next_index == 0)
994 break; 1003 break;