radix-tree: fix contiguous iterator
Konstantin Khlebnikov [Tue, 5 Jun 2012 17:36:33 +0000 (21:36 +0400)]
commit fffaee365fded09f9ebf2db19066065fa54323c3 upstream.

This patch fixes bug in macro radix_tree_for_each_contig().

If radix_tree_next_slot() sees NULL in next slot it returns NULL, but following
radix_tree_next_chunk() switches iterating into next chunk. As result iterating
becomes non-contiguous and breaks vfs "splice" and all its users.

Signed-off-by: Konstantin Khlebnikov <khlebnikov@openvz.org>
Reported-and-bisected-by: Hans de Bruin <jmdebruin@xmsnet.nl>
Reported-and-bisected-by: Ondrej Zary <linux@rainbow-software.org>
Reported-bisected-and-tested-by: Toralf Förster <toralf.foerster@gmx.de>
Link: https://lkml.org/lkml/2012/6/5/64
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>

include/linux/radix-tree.h
lib/radix-tree.c

index 0d04cd6..ffc444c 100644 (file)
@@ -368,8 +368,11 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
                        iter->index++;
                        if (likely(*slot))
                                return slot;
-                       if (flags & RADIX_TREE_ITER_CONTIG)
+                       if (flags & RADIX_TREE_ITER_CONTIG) {
+                               /* forbid switching to the next chunk */
+                               iter->next_index = 0;
                                break;
+                       }
                }
        }
        return NULL;
index 86516f5..3ac50dc 100644 (file)
@@ -673,6 +673,9 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
         * 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.
+        *
+        * This condition also used by radix_tree_next_slot() to stop
+        * contiguous iterating, and forbid swithing to the next chunk.
         */
        index = iter->next_index;
        if (!index && iter->index)