radix-tree: introduce bit-optimized iterator

A series of radix tree cleanups, and usage of them in the core pagecache code. Micro-benchmark: lookup 14 slots (typical page-vector size) in radix-tree there earch <step> slot filled and tagged before/after - nsec per full scan through tree * Intel Sandy Bridge i7-2620M 4Mb L3 New code always faster * AMD Athlon 6000+ 2x1Mb L2, without L3 New code generally faster, Minor degradation (marked with "*") for huge sparse trees * i386 on Sandy Bridge New code faster for common cases: tagged and dense trees. Some degradations for non-tagged lookup on sparse trees. Ideally, there might help __ffs() analog for searching first non-zero long element in array, gcc sometimes cannot optimize this loop corretly. Numbers: CPU: Intel Sandy Bridge i7-2620M 4Mb L3 radix-tree with 1024 slots: tagged lookup step 1 before 7156 after 3613 step 2 before 5399 after 2696 step 3 before 4779 after 1928 step 4 before 4456 after 1429 step 5 before 4292 after 1213 step 6 before 4183 after 1052 step 7 before 4157 after 951 step 8 before 4016 after 812 step 9 before 3952 after 851 step 10 before 3937 after 732 step 11 before 4023 after 709 step 12 before 3872 after 657 step 13 before 3892 after 633 step 14 before 3720 after 591 step 15 before 3879 after 578 step 16 before 3561 after 513 normal lookup step 1 before 4266 after 3301 step 2 before 2695 after 2129 step 3 before 2083 after 1712 step 4 before 1801 after 1534 step 5 before 1628 after 1313 step 6 before 1551 after 1263 step 7 before 1475 after 1185 step 8 before 1432 after 1167 step 9 before 1373 after 1092 step 10 before 1339 after 1134 step 11 before 1292 after 1056 step 12 before 1319 after 1030 step 13 before 1276 after 1004 step 14 before 1256 after 987 step 15 before 1228 after 992 step 16 before 1247 after 999 radix-tree with 1024*1024*128 slots: tagged lookup step 1 before 1086102841 after 674196409 step 2 before 816839155 after 498138306 step 7 before 599728907 after 240676762 step 15 before 555729253 after 185219677 step 63 before 606637748 after 128585664 step 64 before 608384432 after 102945089 step 65 before 596987114 after 123996019 step 128 before 304459225 after 56783056 step 256 before 158846855 after 31232481 step 512 before 86085652 after 18950595 step 12345 before 6517189 after 1674057 normal lookup step 1 before 626064869 after 544418266 step 2 before 418809975 after 336321473 step 7 before 242303598 after 207755560 step 15 before 208380563 after 176496355 step 63 before 186854206 after 167283638 step 64 before 176188060 after 170143976 step 65 before 185139608 after 167487116 step 128 before 88181865 after 86913490 step 256 before 45733628 after 45143534 step 512 before 24506038 after 23859036 step 12345 before 2177425 after 2018662 * AMD Athlon 6000+ 2x1Mb L2, without L3 radix-tree with 1024 slots: tag-lookup step 1 before 8164 after 5379 step 2 before 5818 after 5581 step 3 before 4959 after 4213 step 4 before 4371 after 3386 step 5 before 4204 after 2997 step 6 before 4950 after 2744 step 7 before 4598 after 2480 step 8 before 4251 after 2288 step 9 before 4262 after 2243 step 10 before 4175 after 2131 step 11 before 3999 after 2024 step 12 before 3979 after 1994 step 13 before 3842 after 1929 step 14 before 3750 after 1810 step 15 before 3735 after 1810 step 16 before 3532 after 1660 normal-lookup step 1 before 7875 after 5847 step 2 before 4808 after 4071 step 3 before 4073 after 3462 step 4 before 3677 after 3074 step 5 before 4308 after 2978 step 6 before 3911 after 3807 step 7 before 3635 after 3522 step 8 before 3313 after 3202 step 9 before 3280 after 3257 step 10 before 3166 after 3083 step 11 before 3066 after 3026 step 12 before 2985 after 2982 step 13 before 2925 after 2924 step 14 before 2834 after 2808 step 15 before 2805 after 2803 step 16 before 2647 after 2622 radix-tree with 1024*1024*128 slots: tag-lookup step 1 before 1288059720 after 951736580 step 2 before 961292300 after 884212140 step 7 before 768905140 after 547267580 step 15 before 771319480 after 456550640 step 63 before 504847640 after 242704304 step 64 before 392484800 after 177920786 step 65 before 491162160 after 246895264 step 128 before 208084064 after 97348392 step 256 before 112401035 after 51408126 step 512 before 75825834 after 29145070 step 12345 before 5603166 after 2847330 normal-lookup step 1 before 1025677120 after 861375100 step 2 before 647220080 after 572258540 step 7 before 505518960 after 484041813 step 15 before 430483053 after 444815320 * step 63 before 388113453 after 404250546 * step 64 before 374154666 after 396027440 * step 65 before 381423973 after 396704853 * step 128 before 190078700 after 202619384 * step 256 before 100886756 after 102829108 * step 512 before 64074505 after 56158720 step 12345 before 4237289 after 4422299 * * i686 on Sandy bridge radix-tree with 1024 slots: tagged lookup step 1 before 7990 after 4019 step 2 before 5698 after 2897 step 3 before 5013 after 2475 step 4 before 4630 after 1721 step 5 before 4346 after 1759 step 6 before 4299 after 1556 step 7 before 4098 after 1513 step 8 before 4115 after 1222 step 9 before 3983 after 1390 step 10 before 4077 after 1207 step 11 before 3921 after 1231 step 12 before 3894 after 1116 step 13 before 3840 after 1147 step 14 before 3799 after 1090 step 15 before 3797 after 1059 step 16 before 3783 after 745 normal lookup step 1 before 5103 after 3499 step 2 before 3299 after 2550 step 3 before 2489 after 2370 step 4 before 2034 after 2302 * step 5 before 1846 after 2268 * step 6 before 1752 after 2249 * step 7 before 1679 after 2164 * step 8 before 1627 after 2153 * step 9 before 1542 after 2095 * step 10 before 1479 after 2109 * step 11 before 1469 after 2009 * step 12 before 1445 after 2039 * step 13 before 1411 after 2013 * step 14 before 1374 after 2046 * step 15 before 1340 after 1975 * step 16 before 1331 after 2000 * radix-tree with 1024*1024*128 slots: tagged lookup step 1 before 1225865377 after 667153553 step 2 before 842427423 after 471533007 step 7 before 609296153 after 276260116 step 15 before 544232060 after 226859105 step 63 before 519209199 after 141343043 step 64 before 588980279 after 141951339 step 65 before 521099710 after 138282060 step 128 before 298476778 after 83390628 step 256 before 149358342 after 43602609 step 512 before 76994713 after 22911077 step 12345 before 5328666 after 1472111 normal lookup step 1 before 819284564 after 533635310 step 2 before 512421605 after 364956155 step 7 before 271443305 after 305721345 * step 15 before 223591630 after 273960216 * step 63 before 190320247 after 217770207 * step 64 before 178538168 after 267411372 * step 65 before 186400423 after 215347937 * step 128 before 88106045 after 140540612 * step 256 before 44812420 after 70660377 * step 512 before 24435438 after 36328275 * step 12345 before 2123924 after 2148062 * bloat-o-meter delta for this patchset + patchset with related shmem cleanups bloat-o-meter: x86_64 add/remove: 4/3 grow/shrink: 5/6 up/down: 928/-939 (-11) function old new delta radix_tree_next_chunk - 499 +499 shmem_unuse 428 554 +126 shmem_radix_tree_replace 131 227 +96 find_get_pages_tag 354 419 +65 find_get_pages_contig 345 407 +62 find_get_pages 362 396 +34 __kstrtab_radix_tree_next_chunk - 22 +22 __ksymtab_radix_tree_next_chunk - 16 +16 __kcrctab_radix_tree_next_chunk - 8 +8 radix_tree_gang_lookup_slot 204 203 -1 static.shmem_xattr_set 384 381 -3 radix_tree_gang_lookup_tag_slot 208 191 -17 radix_tree_gang_lookup 231 187 -44 radix_tree_gang_lookup_tag 247 199 -48 shmem_unlock_mapping 278 190 -88 __lookup 217 - -217 __lookup_tag 242 - -242 radix_tree_locate_item 279 - -279 bloat-o-meter: i386 add/remove: 3/3 grow/shrink: 8/9 up/down: 1075/-1275 (-200) function old new delta radix_tree_next_chunk - 757 +757 shmem_unuse 352 449 +97 find_get_pages_contig 269 322 +53 shmem_radix_tree_replace 113 154 +41 find_get_pages_tag 277 318 +41 dcache_dir_lseek 426 458 +32 __kstrtab_radix_tree_next_chunk - 22 +22 vc_do_resize 968 977 +9 snd_pcm_lib_read1 725 733 +8 __ksymtab_radix_tree_next_chunk - 8 +8 netlbl_cipsov4_list 1120 1127 +7 find_get_pages 293 291 -2 new_slab 467 459 -8 bitfill_unaligned_rev 425 417 -8 radix_tree_gang_lookup_tag_slot 177 146 -31 blk_dump_cmd 267 229 -38 radix_tree_gang_lookup_slot 212 134 -78 shmem_unlock_mapping 221 128 -93 radix_tree_gang_lookup_tag 275 162 -113 radix_tree_gang_lookup 255 126 -129 __lookup 227 - -227 __lookup_tag 271 - -271 radix_tree_locate_item 277 - -277 This patch: Implement a clean, simple and effective radix-tree iteration routine. Iterating divided into two phases: * lookup next chunk in radix-tree leaf node * iterating through slots in this chunk Main iterator function radix_tree_next_chunk() returns pointer to first slot, and stores in the struct radix_tree_iter index of next-to-last slot. For tagged-iterating it also constuct bitmask of tags for retunted chunk. All additional logic implemented as static-inline functions and macroses. Also adds radix_tree_find_next_bit() static-inline variant of find_next_bit() optimized for small constant size arrays, because find_next_bit() too heavy for searching in an array with one/two long elements. [akpm@linux-foundation.org: rework comments a bit] Signed-off-by: Konstantin Khlebnikov <khlebnikov@openvz.org> Tested-by: Hugh Dickins <hughd@google.com> Cc: Christoph Hellwig <hch@lst.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
author: Konstantin Khlebnikov <khlebnikov@openvz.org> 2012-03-28 17:42:53 -0400
committer: Linus Torvalds <torvalds@linux-foundation.org> 2012-03-28 20:14:37 -0400
commit: 78c1d78488a3c45685d993130c9f17102dc79a54 (patch)
tree: b9fd6e6b53b5b161836bea39811f16deb0ad88ff
parent: 4c619aa0ba171c092a0ae5d969364deb82dbe371 (diff)
2 files changed, 347 insertions, 0 deletions
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index e9a48234e693..0d04cd69ab9b 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -2,6 +2,7 @@
 * Copyright (C) 2001 Momchil Velikov
 * Portions Copyright (C) 2001 Christoph Hellwig
 * Copyright (C) 2006 Nick Piggin
+ * Copyright (C) 2012 Konstantin Khlebnikov
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
@@ -257,4 +258,199 @@ static inline void radix_tree_preload_end(void)
        preempt_enable();
 }
+/**
+ * struct radix_tree_iter - radix tree iterator state
+ *
+ * @index:      index of current slot
+ * @next_index: next-to-last index for this chunk
+ * @tags:       bit-mask for tag-iterating
+ *
+ * This radix tree iterator works in terms of "chunks" of slots.  A chunk is a
+ * subinterval of slots contained within one radix tree leaf node.  It is
+ * described by a pointer to its first slot and a struct radix_tree_iter
+ * which holds the chunk's position in the tree and its size.  For tagged
+ * iteration radix_tree_iter also holds the slots' bit-mask for one chosen
+ * radix tree tag.
+ */
+struct radix_tree_iter {
+        unsigned long   index;
+        unsigned long   next_index;
+        unsigned long   tags;
+};
+#define RADIX_TREE_ITER_TAG_MASK        0x00FF  /* tag index in lower byte */
+#define RADIX_TREE_ITER_TAGGED          0x0100  /* lookup tagged slots */
+#define RADIX_TREE_ITER_CONTIG          0x0200  /* stop at first hole */
+/**
+ * radix_tree_iter_init - initialize radix tree iterator
+ *
+ * @iter:       pointer to iterator state
+ * @start:      iteration starting index
+ * Returns:     NULL
+ */
+static __always_inline void **
+radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
+{
+        /*
+         * Leave iter->tags uninitialized. radix_tree_next_chunk() will fill it
+         * in the case of a successful tagged chunk lookup.  If the lookup was
+         * unsuccessful or non-tagged then nobody cares about ->tags.
+         *
+         * Set index to zero to bypass next_index overflow protection.
+         * See the comment in radix_tree_next_chunk() for details.
+         */
+        iter->index = 0;
+        iter->next_index = start;
+        return NULL;
+}
+/**
+ * radix_tree_next_chunk - find next chunk of slots for iteration
+ *
+ * @root:       radix tree root
+ * @iter:       iterator state
+ * @flags:      RADIX_TREE_ITER_* flags and tag index
+ * Returns:     pointer to chunk first slot, or NULL if there no more left
+ *
+ * This function looks up the next chunk in the radix tree starting from
+ * @iter->next_index.  It returns a pointer to the chunk's first slot.
+ * Also it fills @iter with data about chunk: position in the tree (index),
+ * its end (next_index), and constructs a bit mask for tagged iterating (tags).
+ */
+void **radix_tree_next_chunk(struct radix_tree_root *root,
+                             struct radix_tree_iter *iter, unsigned flags);
+/**
+ * radix_tree_chunk_size - get current chunk size
+ *
+ * @iter:       pointer to radix tree iterator
+ * Returns:     current chunk size
+ */
+static __always_inline unsigned
+radix_tree_chunk_size(struct radix_tree_iter *iter)
+{
+        return iter->next_index - iter->index;
+}
+/**
+ * radix_tree_next_slot - find next slot in chunk
+ *
+ * @slot:       pointer to current slot
+ * @iter:       pointer to interator state
+ * @flags:      RADIX_TREE_ITER_*, should be constant
+ * Returns:     pointer to next slot, or NULL if there no more left
+ *
+ * This function updates @iter->index in the case of a successful lookup.
+ * For tagged lookup it also eats @iter->tags.
+ */
+static __always_inline void **
+radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
+{
+        if (flags & RADIX_TREE_ITER_TAGGED) {
+                iter->tags >>= 1;
+                if (likely(iter->tags & 1ul)) {
+                        iter->index++;
+                        return slot + 1;
+                }
+                if (!(flags & RADIX_TREE_ITER_CONTIG) && likely(iter->tags)) {
+                        unsigned offset = __ffs(iter->tags);
+                        iter->tags >>= offset;
+                        iter->index += offset + 1;
+                        return slot + offset + 1;
+                }
+        } else {
+                unsigned size = radix_tree_chunk_size(iter) - 1;
+                while (size--) {
+                        slot++;
+                        iter->index++;
+                        if (likely(*slot))
+                                return slot;
+                        if (flags & RADIX_TREE_ITER_CONTIG)
+                                break;
+                }
+        }
+        return NULL;
+}
+/**
+ * radix_tree_for_each_chunk - iterate over chunks
+ *
+ * @slot:       the void** variable for pointer to chunk first slot
+ * @root:       the struct radix_tree_root pointer
+ * @iter:       the struct radix_tree_iter pointer
+ * @start:      iteration starting index
+ * @flags:      RADIX_TREE_ITER_* and tag index
+ *
+ * Locks can be released and reacquired between iterations.
+ */
+#define radix_tree_for_each_chunk(slot, root, iter, start, flags)       \
+        for (slot = radix_tree_iter_init(iter, start) ;                 \
+              (slot = radix_tree_next_chunk(root, iter, flags)) ;)
+/**
+ * radix_tree_for_each_chunk_slot - iterate over slots in one chunk
+ *
+ * @slot:       the void** variable, at the beginning points to chunk first slot
+ * @iter:       the struct radix_tree_iter pointer
+ * @flags:      RADIX_TREE_ITER_*, should be constant
+ *
+ * This macro is designed to be nested inside radix_tree_for_each_chunk().
+ * @slot points to the radix tree slot, @iter->index contains its index.
+ */
+#define radix_tree_for_each_chunk_slot(slot, iter, flags)               \
+        for (; slot ; slot = radix_tree_next_slot(slot, iter, flags))
+/**
+ * radix_tree_for_each_slot - iterate over non-empty slots
+ *
+ * @slot:       the void** variable for pointer to slot
+ * @root:       the struct radix_tree_root pointer
+ * @iter:       the struct radix_tree_iter pointer
+ * @start:      iteration starting index
+ *
+ * @slot points to radix tree slot, @iter->index contains its index.
+ */
+#define radix_tree_for_each_slot(slot, root, iter, start)               \
+        for (slot = radix_tree_iter_init(iter, start) ;                 \
+             slot || (slot = radix_tree_next_chunk(root, iter, 0)) ;    \
+             slot = radix_tree_next_slot(slot, iter, 0))
+/**
+ * radix_tree_for_each_contig - iterate over contiguous slots
+ *
+ * @slot:       the void** variable for pointer to slot
+ * @root:       the struct radix_tree_root pointer
+ * @iter:       the struct radix_tree_iter pointer
+ * @start:      iteration starting index
+ *
+ * @slot points to radix tree slot, @iter->index contains its index.
+ */
+#define radix_tree_for_each_contig(slot, root, iter, start)             \
+        for (slot = radix_tree_iter_init(iter, start) ;                 \
+             slot || (slot = radix_tree_next_chunk(root, iter,          \
+                                RADIX_TREE_ITER_CONTIG)) ;              \
+             slot = radix_tree_next_slot(slot, iter,                    \
+                                RADIX_TREE_ITER_CONTIG))
+/**
+ * radix_tree_for_each_tagged - iterate over tagged slots
+ *
+ * @slot:       the void** variable for pointer to slot
+ * @root:       the struct radix_tree_root pointer
+ * @iter:       the struct radix_tree_iter pointer
+ * @start:      iteration starting index
+ * @tag:        tag index
+ *
+ * @slot points to radix tree slot, @iter->index contains its index.
+ */
+#define radix_tree_for_each_tagged(slot, root, iter, start, tag)        \
+        for (slot = radix_tree_iter_init(iter, start) ;                 \
+             slot || (slot = radix_tree_next_chunk(root, iter,          \
+                              RADIX_TREE_ITER_TAGGED | tag)) ;          \
+             slot = radix_tree_next_slot(slot, iter,                    \
+                                RADIX_TREE_ITER_TAGGED))
 #endif /* _LINUX_RADIX_TREE_H */
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 3e69c2b66c94..fefa76e6ff96 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -3,6 +3,7 @@
 * Portions Copyright (C) 2001 Christoph Hellwig
 * Copyright (C) 2005 SGI, Christoph Lameter
 * Copyright (C) 2006 Nick Piggin
+ * Copyright (C) 2012 Konstantin Khlebnikov
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
@@ -146,6 +147,43 @@ static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
        }
        return 0;
 }
+/**
+ * radix_tree_find_next_bit - find the next set bit in a memory region
+ *
+ * @addr: The address to base the search on
+ * @size: The bitmap size in bits
+ * @offset: The bitnumber to start searching at
+ *
+ * Unrollable variant of find_next_bit() for constant size arrays.
+ * Tail bits starting from size to roundup(size, BITS_PER_LONG) must be zero.
+ * Returns next bit offset, or size if nothing found.
+ */
+static __always_inline unsigned long
+radix_tree_find_next_bit(const unsigned long *addr,
+                         unsigned long size, unsigned long offset)
+{
+        if (!__builtin_constant_p(size))
+                return find_next_bit(addr, size, offset);
+        if (offset < size) {
+                unsigned long tmp;
+                addr += offset / BITS_PER_LONG;
+                tmp = *addr >> (offset % BITS_PER_LONG);
+                if (tmp)
+                        return __ffs(tmp) + offset;
+                offset = (offset + BITS_PER_LONG) & ~(BITS_PER_LONG - 1);
+                while (offset < size) {
+                        tmp = *++addr;
+                        if (tmp)
+                                return __ffs(tmp) + offset;
+                        offset += BITS_PER_LONG;
+                }
+        }
+        return size;
+}
 /*
 * This assumes that the caller has performed appropriate preallocation, and
 * that the caller has pinned this thread of control to the current CPU.
@@ -613,6 +651,119 @@ int radix_tree_tag_get(struct radix_tree_root *root,
 EXPORT_SYMBOL(radix_tree_tag_get);
 /**
+ * radix_tree_next_chunk - find next chunk of slots for iteration
+ *
+ * @root:       radix tree root
+ * @iter:       iterator state
+ * @flags:      RADIX_TREE_ITER_* flags and tag index
+ * Returns:     pointer to chunk first slot, or NULL if iteration is over
+ */
+void **radix_tree_next_chunk(struct radix_tree_root *root,
+                             struct radix_tree_iter *iter, unsigned flags)
+{
+        unsigned shift, tag = flags & RADIX_TREE_ITER_TAG_MASK;
+        struct radix_tree_node *rnode, *node;
+        unsigned long index, offset;
+        if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
+                return NULL;
+        /*
+         * Catch next_index overflow after ~0UL. iter->index never overflows
+         * during iterating; it can be zero only at the beginning.
+         * And we cannot overflow iter->next_index in a single step,
+         * because RADIX_TREE_MAP_SHIFT < BITS_PER_LONG.
+         */
+        index = iter->next_index;
+        if (!index && iter->index)
+                return NULL;
+        rnode = rcu_dereference_raw(root->rnode);
+        if (radix_tree_is_indirect_ptr(rnode)) {
+                rnode = indirect_to_ptr(rnode);
+        } else if (rnode && !index) {
+                /* Single-slot tree */
+                iter->index = 0;
+                iter->next_index = 1;
+                iter->tags = 1;
+                return (void **)&root->rnode;
+        } else
+                return NULL;
+restart:
+        shift = (rnode->height - 1) * RADIX_TREE_MAP_SHIFT;
+        offset = index >> shift;
+        /* Index outside of the tree */
+        if (offset >= RADIX_TREE_MAP_SIZE)
+                return NULL;
+        node = rnode;
+        while (1) {
+                if ((flags & RADIX_TREE_ITER_TAGGED) ?
+                                !test_bit(offset, node->tags[tag]) :
+                                !node->slots[offset]) {
+                        /* Hole detected */
+                        if (flags & RADIX_TREE_ITER_CONTIG)
+                                return NULL;
+                        if (flags & RADIX_TREE_ITER_TAGGED)
+                                offset = radix_tree_find_next_bit(
+                                                node->tags[tag],
+                                                RADIX_TREE_MAP_SIZE,
+                                                offset + 1);
+                        else
+                                while (++offset < RADIX_TREE_MAP_SIZE) {
+                                        if (node->slots[offset])
+                                                break;
+                                }
+                        index &= ~((RADIX_TREE_MAP_SIZE << shift) - 1);
+                        index += offset << shift;
+                        /* Overflow after ~0UL */
+                        if (!index)
+                                return NULL;
+                        if (offset == RADIX_TREE_MAP_SIZE)
+                                goto restart;
+                }
+                /* This is leaf-node */
+                if (!shift)
+                        break;
+                node = rcu_dereference_raw(node->slots[offset]);
+                if (node == NULL)
+                        goto restart;
+                shift -= RADIX_TREE_MAP_SHIFT;
+                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+        }
+        /* Update the iterator state */
+        iter->index = index;
+        iter->next_index = (index | RADIX_TREE_MAP_MASK) + 1;
+        /* Construct iter->tags bit-mask from node->tags[tag] array */
+        if (flags & RADIX_TREE_ITER_TAGGED) {
+                unsigned tag_long, tag_bit;
+                tag_long = offset / BITS_PER_LONG;
+                tag_bit  = offset % BITS_PER_LONG;
+                iter->tags = node->tags[tag][tag_long] >> tag_bit;
+                /* This never happens if RADIX_TREE_TAG_LONGS == 1 */
+                if (tag_long < RADIX_TREE_TAG_LONGS - 1) {
+                        /* Pick tags from next element */
+                        if (tag_bit)
+                                iter->tags |= node->tags[tag][tag_long + 1] <<
+                                                (BITS_PER_LONG - tag_bit);
+                        /* Clip chunk size, here only BITS_PER_LONG tags */
+                        iter->next_index = index + BITS_PER_LONG;
+                }
+        }
+        return node->slots + offset;
+}
+EXPORT_SYMBOL(radix_tree_next_chunk);
+/**
 * radix_tree_range_tag_if_tagged - for each item in given range set given
 *                                 tag if item has another tag set
 * @root:               radix tree root
author	Konstantin Khlebnikov <khlebnikov@openvz.org>	2012-03-28 17:42:53 -0400
committer	Linus Torvalds <torvalds@linux-foundation.org>	2012-03-28 20:14:37 -0400
commit	78c1d78488a3c45685d993130c9f17102dc79a54 (patch)
tree	b9fd6e6b53b5b161836bea39811f16deb0ad88ff
parent	4c619aa0ba171c092a0ae5d969364deb82dbe371 (diff)

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index e9a48234e693..0d04cd69ab9b 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h
@@ -2,6 +2,7 @@
2	* Copyright (C) 2001 Momchil Velikov	2	* Copyright (C) 2001 Momchil Velikov
3	* Portions Copyright (C) 2001 Christoph Hellwig	3	* Portions Copyright (C) 2001 Christoph Hellwig
4	* Copyright (C) 2006 Nick Piggin	4	* Copyright (C) 2006 Nick Piggin
		5	* Copyright (C) 2012 Konstantin Khlebnikov
5	*	6	*
6	* This program is free software; you can redistribute it and/or	7	* This program is free software; you can redistribute it and/or
7	* modify it under the terms of the GNU General Public License as	8	* modify it under the terms of the GNU General Public License as
@@ -257,4 +258,199 @@ static inline void radix_tree_preload_end(void)
257	preempt_enable();	258	preempt_enable();
258	}	259	}
259		260
		261	/**
		262	* struct radix_tree_iter - radix tree iterator state
		263	*
		264	* @index: index of current slot
		265	* @next_index: next-to-last index for this chunk
		266	* @tags: bit-mask for tag-iterating
		267	*
		268	* This radix tree iterator works in terms of "chunks" of slots. A chunk is a
		269	* subinterval of slots contained within one radix tree leaf node. It is
		270	* described by a pointer to its first slot and a struct radix_tree_iter
		271	* which holds the chunk's position in the tree and its size. For tagged
		272	* iteration radix_tree_iter also holds the slots' bit-mask for one chosen
		273	* radix tree tag.
		274	*/
		275	struct radix_tree_iter {
		276	unsigned long index;
		277	unsigned long next_index;
		278	unsigned long tags;
		279	};
		280
		281	#define RADIX_TREE_ITER_TAG_MASK 0x00FF /* tag index in lower byte */
		282	#define RADIX_TREE_ITER_TAGGED 0x0100 /* lookup tagged slots */
		283	#define RADIX_TREE_ITER_CONTIG 0x0200 /* stop at first hole */
		284
		285	/**
		286	* radix_tree_iter_init - initialize radix tree iterator
		287	*
		288	* @iter: pointer to iterator state
		289	* @start: iteration starting index
		290	* Returns: NULL
		291	*/
		292	static __always_inline void **
		293	radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
		294	{
		295	/*
		296	* Leave iter->tags uninitialized. radix_tree_next_chunk() will fill it
		297	* in the case of a successful tagged chunk lookup. If the lookup was
		298	* unsuccessful or non-tagged then nobody cares about ->tags.
		299	*
		300	* Set index to zero to bypass next_index overflow protection.
		301	* See the comment in radix_tree_next_chunk() for details.
		302	*/
		303	iter->index = 0;
		304	iter->next_index = start;
		305	return NULL;
		306	}
		307
		308	/**
		309	* radix_tree_next_chunk - find next chunk of slots for iteration
		310	*
		311	* @root: radix tree root
		312	* @iter: iterator state
		313	* @flags: RADIX_TREE_ITER_* flags and tag index
		314	* Returns: pointer to chunk first slot, or NULL if there no more left
		315	*
		316	* This function looks up the next chunk in the radix tree starting from
		317	* @iter->next_index. It returns a pointer to the chunk's first slot.
		318	* Also it fills @iter with data about chunk: position in the tree (index),
		319	* its end (next_index), and constructs a bit mask for tagged iterating (tags).
		320	*/
		321	void *radix_tree_next_chunk(struct radix_tree_root root,
		322	struct radix_tree_iter *iter, unsigned flags);
		323
		324	/**
		325	* radix_tree_chunk_size - get current chunk size
		326	*
		327	* @iter: pointer to radix tree iterator
		328	* Returns: current chunk size
		329	*/
		330	static __always_inline unsigned
		331	radix_tree_chunk_size(struct radix_tree_iter *iter)
		332	{
		333	return iter->next_index - iter->index;
		334	}
		335
		336	/**
		337	* radix_tree_next_slot - find next slot in chunk
		338	*
		339	* @slot: pointer to current slot
		340	* @iter: pointer to interator state
		341	* @flags: RADIX_TREE_ITER_*, should be constant
		342	* Returns: pointer to next slot, or NULL if there no more left
		343	*
		344	* This function updates @iter->index in the case of a successful lookup.
		345	* For tagged lookup it also eats @iter->tags.
		346	*/
		347	static __always_inline void **
		348	radix_tree_next_slot(void *slot, struct radix_tree_iter iter, unsigned flags)
		349	{
		350	if (flags & RADIX_TREE_ITER_TAGGED) {
		351	iter->tags >>= 1;
		352	if (likely(iter->tags & 1ul)) {
		353	iter->index++;
		354	return slot + 1;
		355	}
		356	if (!(flags & RADIX_TREE_ITER_CONTIG) && likely(iter->tags)) {
		357	unsigned offset = __ffs(iter->tags);
		358
		359	iter->tags >>= offset;
		360	iter->index += offset + 1;
		361	return slot + offset + 1;
		362	}
		363	} else {
		364	unsigned size = radix_tree_chunk_size(iter) - 1;
		365
		366	while (size--) {
		367	slot++;
		368	iter->index++;
		369	if (likely(*slot))
		370	return slot;
		371	if (flags & RADIX_TREE_ITER_CONTIG)
		372	break;
		373	}
		374	}
		375	return NULL;
		376	}
		377
		378	/**
		379	* radix_tree_for_each_chunk - iterate over chunks
		380	*
		381	* @slot: the void** variable for pointer to chunk first slot
		382	* @root: the struct radix_tree_root pointer
		383	* @iter: the struct radix_tree_iter pointer
		384	* @start: iteration starting index
		385	* @flags: RADIX_TREE_ITER_* and tag index
		386	*
		387	* Locks can be released and reacquired between iterations.
		388	*/
		389	#define radix_tree_for_each_chunk(slot, root, iter, start, flags) \
		390	for (slot = radix_tree_iter_init(iter, start) ; \
		391	(slot = radix_tree_next_chunk(root, iter, flags)) ;)
		392
		393	/**
		394	* radix_tree_for_each_chunk_slot - iterate over slots in one chunk
		395	*
		396	* @slot: the void** variable, at the beginning points to chunk first slot
		397	* @iter: the struct radix_tree_iter pointer
		398	* @flags: RADIX_TREE_ITER_*, should be constant
		399	*
		400	* This macro is designed to be nested inside radix_tree_for_each_chunk().
		401	* @slot points to the radix tree slot, @iter->index contains its index.
		402	*/
		403	#define radix_tree_for_each_chunk_slot(slot, iter, flags) \
		404	for (; slot ; slot = radix_tree_next_slot(slot, iter, flags))
		405
		406	/**
		407	* radix_tree_for_each_slot - iterate over non-empty slots
		408	*
		409	* @slot: the void** variable for pointer to slot
		410	* @root: the struct radix_tree_root pointer
		411	* @iter: the struct radix_tree_iter pointer
		412	* @start: iteration starting index
		413	*
		414	* @slot points to radix tree slot, @iter->index contains its index.
		415	*/
		416	#define radix_tree_for_each_slot(slot, root, iter, start) \
		417	for (slot = radix_tree_iter_init(iter, start) ; \
		418	slot \|\| (slot = radix_tree_next_chunk(root, iter, 0)) ; \
		419	slot = radix_tree_next_slot(slot, iter, 0))
		420
		421	/**
		422	* radix_tree_for_each_contig - iterate over contiguous slots
		423	*
		424	* @slot: the void** variable for pointer to slot
		425	* @root: the struct radix_tree_root pointer
		426	* @iter: the struct radix_tree_iter pointer
		427	* @start: iteration starting index
		428	*
		429	* @slot points to radix tree slot, @iter->index contains its index.
		430	*/
		431	#define radix_tree_for_each_contig(slot, root, iter, start) \
		432	for (slot = radix_tree_iter_init(iter, start) ; \
		433	slot \|\| (slot = radix_tree_next_chunk(root, iter, \
		434	RADIX_TREE_ITER_CONTIG)) ; \
		435	slot = radix_tree_next_slot(slot, iter, \
		436	RADIX_TREE_ITER_CONTIG))
		437
		438	/**
		439	* radix_tree_for_each_tagged - iterate over tagged slots
		440	*
		441	* @slot: the void** variable for pointer to slot
		442	* @root: the struct radix_tree_root pointer
		443	* @iter: the struct radix_tree_iter pointer
		444	* @start: iteration starting index
		445	* @tag: tag index
		446	*
		447	* @slot points to radix tree slot, @iter->index contains its index.
		448	*/
		449	#define radix_tree_for_each_tagged(slot, root, iter, start, tag) \
		450	for (slot = radix_tree_iter_init(iter, start) ; \
		451	slot \|\| (slot = radix_tree_next_chunk(root, iter, \
		452	RADIX_TREE_ITER_TAGGED \| tag)) ; \
		453	slot = radix_tree_next_slot(slot, iter, \
		454	RADIX_TREE_ITER_TAGGED))
		455
260	#endif /* _LINUX_RADIX_TREE_H */	456	#endif /* _LINUX_RADIX_TREE_H */


diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 3e69c2b66c94..fefa76e6ff96 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c
@@ -3,6 +3,7 @@
3	* Portions Copyright (C) 2001 Christoph Hellwig	3	* Portions Copyright (C) 2001 Christoph Hellwig
4	* Copyright (C) 2005 SGI, Christoph Lameter	4	* Copyright (C) 2005 SGI, Christoph Lameter
5	* Copyright (C) 2006 Nick Piggin	5	* Copyright (C) 2006 Nick Piggin
		6	* Copyright (C) 2012 Konstantin Khlebnikov
6	*	7	*
7	* This program is free software; you can redistribute it and/or	8	* This program is free software; you can redistribute it and/or
8	* modify it under the terms of the GNU General Public License as	9	* modify it under the terms of the GNU General Public License as
@@ -146,6 +147,43 @@ static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
146	}	147	}
147	return 0;	148	return 0;
148	}	149	}
		150
		151	/**
		152	* radix_tree_find_next_bit - find the next set bit in a memory region
		153	*
		154	* @addr: The address to base the search on
		155	* @size: The bitmap size in bits
		156	* @offset: The bitnumber to start searching at
		157	*
		158	* Unrollable variant of find_next_bit() for constant size arrays.
		159	* Tail bits starting from size to roundup(size, BITS_PER_LONG) must be zero.
		160	* Returns next bit offset, or size if nothing found.
		161	*/
		162	static __always_inline unsigned long
		163	radix_tree_find_next_bit(const unsigned long *addr,
		164	unsigned long size, unsigned long offset)
		165	{
		166	if (!__builtin_constant_p(size))
		167	return find_next_bit(addr, size, offset);
		168
		169	if (offset < size) {
		170	unsigned long tmp;
		171
		172	addr += offset / BITS_PER_LONG;
		173	tmp = *addr >> (offset % BITS_PER_LONG);
		174	if (tmp)
		175	return __ffs(tmp) + offset;
		176	offset = (offset + BITS_PER_LONG) & ~(BITS_PER_LONG - 1);
		177	while (offset < size) {
		178	tmp = *++addr;
		179	if (tmp)
		180	return __ffs(tmp) + offset;
		181	offset += BITS_PER_LONG;
		182	}
		183	}
		184	return size;
		185	}
		186
149	/*	187	/*
150	* This assumes that the caller has performed appropriate preallocation, and	188	* This assumes that the caller has performed appropriate preallocation, and
151	* that the caller has pinned this thread of control to the current CPU.	189	* that the caller has pinned this thread of control to the current CPU.
@@ -613,6 +651,119 @@ int radix_tree_tag_get(struct radix_tree_root *root,
613	EXPORT_SYMBOL(radix_tree_tag_get);	651	EXPORT_SYMBOL(radix_tree_tag_get);
614		652
615	/**	653	/**
		654	* radix_tree_next_chunk - find next chunk of slots for iteration
		655	*
		656	* @root: radix tree root
		657	* @iter: iterator state
		658	* @flags: RADIX_TREE_ITER_* flags and tag index
		659	* Returns: pointer to chunk first slot, or NULL if iteration is over
		660	*/
		661	void *radix_tree_next_chunk(struct radix_tree_root root,
		662	struct radix_tree_iter *iter, unsigned flags)
		663	{
		664	unsigned shift, tag = flags & RADIX_TREE_ITER_TAG_MASK;
		665	struct radix_tree_node rnode, node;
		666	unsigned long index, offset;
		667
		668	if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
		669	return NULL;
		670
		671	/*
		672	* Catch next_index overflow after ~0UL. iter->index never overflows
		673	* during iterating; it can be zero only at the beginning.
		674	* And we cannot overflow iter->next_index in a single step,
		675	* because RADIX_TREE_MAP_SHIFT < BITS_PER_LONG.
		676	*/
		677	index = iter->next_index;
		678	if (!index && iter->index)
		679	return NULL;
		680
		681	rnode = rcu_dereference_raw(root->rnode);
		682	if (radix_tree_is_indirect_ptr(rnode)) {
		683	rnode = indirect_to_ptr(rnode);
		684	} else if (rnode && !index) {
		685	/* Single-slot tree */
		686	iter->index = 0;
		687	iter->next_index = 1;
		688	iter->tags = 1;
		689	return (void **)&root->rnode;
		690	} else
		691	return NULL;
		692
		693	restart:
		694	shift = (rnode->height - 1) * RADIX_TREE_MAP_SHIFT;
		695	offset = index >> shift;
		696
		697	/* Index outside of the tree */
		698	if (offset >= RADIX_TREE_MAP_SIZE)
		699	return NULL;
		700
		701	node = rnode;
		702	while (1) {
		703	if ((flags & RADIX_TREE_ITER_TAGGED) ?
		704	!test_bit(offset, node->tags[tag]) :
		705	!node->slots[offset]) {
		706	/* Hole detected */
		707	if (flags & RADIX_TREE_ITER_CONTIG)
		708	return NULL;
		709
		710	if (flags & RADIX_TREE_ITER_TAGGED)
		711	offset = radix_tree_find_next_bit(
		712	node->tags[tag],
		713	RADIX_TREE_MAP_SIZE,
		714	offset + 1);
		715	else
		716	while (++offset < RADIX_TREE_MAP_SIZE) {
		717	if (node->slots[offset])
		718	break;
		719	}
		720	index &= ~((RADIX_TREE_MAP_SIZE << shift) - 1);
		721	index += offset << shift;
		722	/* Overflow after ~0UL */
		723	if (!index)
		724	return NULL;
		725	if (offset == RADIX_TREE_MAP_SIZE)
		726	goto restart;
		727	}
		728
		729	/* This is leaf-node */
		730	if (!shift)
		731	break;
		732
		733	node = rcu_dereference_raw(node->slots[offset]);
		734	if (node == NULL)
		735	goto restart;
		736	shift -= RADIX_TREE_MAP_SHIFT;
		737	offset = (index >> shift) & RADIX_TREE_MAP_MASK;
		738	}
		739
		740	/* Update the iterator state */
		741	iter->index = index;
		742	iter->next_index = (index \| RADIX_TREE_MAP_MASK) + 1;
		743
		744	/* Construct iter->tags bit-mask from node->tags[tag] array */
		745	if (flags & RADIX_TREE_ITER_TAGGED) {
		746	unsigned tag_long, tag_bit;
		747
		748	tag_long = offset / BITS_PER_LONG;
		749	tag_bit = offset % BITS_PER_LONG;
		750	iter->tags = node->tags[tag][tag_long] >> tag_bit;
		751	/* This never happens if RADIX_TREE_TAG_LONGS == 1 */
		752	if (tag_long < RADIX_TREE_TAG_LONGS - 1) {
		753	/* Pick tags from next element */
		754	if (tag_bit)
		755	iter->tags \|= node->tags[tag][tag_long + 1] <<
		756	(BITS_PER_LONG - tag_bit);
		757	/* Clip chunk size, here only BITS_PER_LONG tags */
		758	iter->next_index = index + BITS_PER_LONG;
		759	}
		760	}
		761
		762	return node->slots + offset;
		763	}
		764	EXPORT_SYMBOL(radix_tree_next_chunk);
		765
		766	/**
616	* radix_tree_range_tag_if_tagged - for each item in given range set given	767	* radix_tree_range_tag_if_tagged - for each item in given range set given
617	* tag if item has another tag set	768	* tag if item has another tag set
618	* @root: radix tree root	769	* @root: radix tree root