Skip to contentSkip to conversation

radix-tree: iterating general cleanup

PATCH In review Konstantin Khlebnikov 6 participants 15 messages Feb 7, 2012 – Mar 15, 2012

Subsystems (7)
lore
Share & tools
lore
#0 lore raw

cover radix-tree: iterating general cleanup

This patchset implements common radix-tree iteration routine and reworks page-cache lookup functions with using it.

radix_tree_gang_lookup_*slot() now mostly unused (the last user somethere in drivers/sh/intc/virq.c), but they are exported, we cannot remove them for now.

Also there some shmem-related radix-tree hacks can be reworked, radix_tree_locate_item() can be removed. I already have a few extra patches.

And as usual my lovely bloat-o-meter:

add/remove: 4/3 grow/shrink: 4/4 up/down: 1232/-964 (268)

function                                     old     new   delta
radix_tree_next_chunk                          -     499    +499
static.shmem_find_get_pages_and_swap           -     404    +404
find_get_pages_tag                           354     488    +134
find_get_pages                               362     438     +76
find_get_pages_contig                        345     407     +62
__kstrtab_radix_tree_next_chunk                -      22     +22
shmem_truncate_range                        1633    1652     +19
__ksymtab_radix_tree_next_chunk                -      16     +16
radix_tree_gang_lookup_tag_slot              208     180     -28
radix_tree_gang_lookup_tag                   247     207     -40
radix_tree_gang_lookup_slot                  204     162     -42
radix_tree_gang_lookup                       231     160     -71
__lookup                                     217       -    -217
__lookup_tag                                 242       -    -242
shmem_find_get_pages_and_swap                324       -    -324

---

Konstantin Khlebnikov (4):
bitops: implement "optimized" __find_next_bit()
radix-tree: introduce bit-optimized iterator
radix-tree: rewrite gang lookup with using iterator
radix-tree: use iterators in find_get_pages* functions

 include/asm-generic/bitops/find.h |   36 +++
 include/linux/radix-tree.h        |  129 +++++++++++
 lib/radix-tree.c                  |  422 +++++++++++++------------------------
 mm/filemap.c                      |   75 ++++---
 mm/shmem.c                        |   23 +-
 5 files changed, 375 insertions(+), 310 deletions(-)
Signature · 8 lines
Signature

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#1 lore raw

PATCH 1/4 bitops: implement "optimized" __find_next_bit()

This patch adds __find_next_bit() -- static-inline variant of find_next_bit() optimized for small constant size arrays, because find_next_bit() is too heavy for searching in an array with one/two long elements.
And unlike to find_next_bit() it does not mask tail bits.

---
 include/asm-generic/bitops/find.h |   36 ++++++++++++++++++++++++++++++++++++
 1 files changed, 36 insertions(+), 0 deletions(-)
include/asm-generic/bitops/find.h +36 -0
index 71c7780..1dd2495 100644
@@ -12,6 +12,42 @@ extern unsigned long find_next_bit(const unsigned long *addr, unsigned long
 		size, unsigned long offset);
 #endif
 
+#ifndef __find_next_bit
+/**
+ * __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 inline unsigned long __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;
+}
+#endif
+
 #ifndef find_next_zero_bit
 /**
  * find_next_zero_bit - find the next cleared bit in a memory region

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#2 lore raw

Re: [PATCH 1/4] bitops: implement "optimized" __find_next_bit()

Quoted 4 lines · Konstantin Khlebnikov

This patch adds  __find_next_bit() -- static-inline variant of find_next_bit() optimized for small constant size arrays, because find_next_bit() is too heavy for searching in an array with one/two long elements.
And unlike to find_next_bit() it does not mask tail bits.

Does anybody else really want this? My gut feel is that this shouldn't be inline at all (the same is largely true of the existing ones), and that nobody else really wants this. Nor do we want to introduce yet another helper function that has very subtly different semantics that will just confuse people.

So I suspect this should be instead a function that is internal to the iterator code.

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#3 lore raw

PATCH 2/4 radix-tree: introduce bit-optimized iterator

In reply to Konstantin Khlebnikov

This patch implements clean, simple and effective radix-tree iteration routine. Iterating is divided into two loops: the outer loop iterates though radix tree chunks on leaf nodes, the nested loop iterates through slots in one 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. Thus nested-loop has enough information for iteration.

---
 include/linux/radix-tree.h |  129 ++++++++++++++++++++++++++++++++++++++++++++
 lib/radix-tree.c           |  107 ++++++++++++++++++++++++++++++++++++
 2 files changed, 236 insertions(+), 0 deletions(-)
include/linux/radix-tree.h +129 -0
index 07e360b..c31b895 100644
@@ -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
@@ -256,4 +257,132 @@ static inline void radix_tree_preload_end(void)
 	preempt_enable();
 }
 
+struct radix_tree_iter {
+	unsigned long		index;		/* current slot index */
+	unsigned long		next_index;	/* next chunk first index */
+	unsigned long		tags;		/* bitmask for tag-iterating */
+};
+
+static inline void radix_tree_iter_start(struct radix_tree_iter *iter,
+					 unsigned long start)
+{
+	iter->index = start;
+	iter->next_index = 1; /* any non-zero */
+}
+
+#define RADIX_TREE_ITER_TAG_MASK	0x00FF
+#define RADIX_TREE_ITER_TAGGED		0x0100	/* search tagged */
+#define RADIX_TREE_ITER_CONTIG		0x0200	/* stop at first hole  */
+
+void **radix_tree_next_chunk(struct radix_tree_root *root,
+			     struct radix_tree_iter *iter, unsigned flags);
+
+/**
+ * radix_tree_next_tag - find next tagged slot in chunk
+ *
+ * @slot	pointer to slot pointer
+ * @iter	iterator state
+ *
+ * Eats iter->tags and bumps *slot and iter->index to next tagged slot
+ * Returns true if something found, and false otherwise
+ */
+static inline bool radix_tree_next_tag(void ***slot,
+				       struct radix_tree_iter *iter)
+{
+	unsigned long offset;
+
+	if (likely(iter->tags & 1ul))
+		return true;
+	if (unlikely(!iter->tags)) {
+		iter->index = iter->next_index;
+		return false;
+	}
+	offset = __ffs(iter->tags);
+	iter->tags >>= offset;
+	iter->index += offset;
+	*slot += offset;
+	return true;
+}
+
+/**
+ * radix_tree_for_each_chunk - iterate over all slot chunks
+ *
+ * @slot:	the void** for pointer to first slot
+ * @root	the struct radix_tree_root pointer
+ * @iter	the struct radix_tree_iter pointer
+ * @start	starting index
+ * @flags	RADIX_TREE_ITER_* and tag index
+ */
+#define radix_tree_for_each_chunk(slot, root, iter, start, flags)	\
+	for ( radix_tree_iter_start(iter, start) ;			\
+	      (slot = radix_tree_next_chunk(root, iter, flags)) ; )
+
+/**
+ * radix_tree_for_each_chunk_slot - iterate over all slots in one chunk
+ *
+ * @slot:	the void** for pointer to slot
+ * @iter	the struct radix_tree_iter pointer
+ */
+#define radix_tree_for_each_chunk_slot(slot, iter)	\
+	for ( ; (iter)->index != (iter)->next_index ;	\
+		(iter)->index++, slot++ )
+
+/**
+ * radix_tree_for_each_chunk_tagged_slot - iterate over all tagged slots
+ *					   in one chunk
+ *
+ * @slot:	the void** for pointer to slot
+ * @iter	the struct radix_tree_iter pointer
+ */
+#define radix_tree_for_each_chunk_tagged_slot(slot, iter)	\
+	for ( ; radix_tree_next_tag(&slot, iter) ;		\
+		(iter)->tags >>= 1, (iter)->index++, slot++ )
+
+/**
+ * radix_tree_for_each_slot - iterate over all non-empty slots
+ *
+ * @slot:	the void** for pointer to slot
+ * @root	the struct radix_tree_root pointer
+ * @iter	the struct radix_tree_iter pointer
+ * @start	starting index
+ *
+ * This is double-loop, break does not work.
+ */
+#define radix_tree_for_each_slot(slot, root, iter, start)	\
+	radix_tree_for_each_chunk(slot, root, iter, start, 0)	\
+		radix_tree_for_each_chunk_slot(slot, iter)	\
+			if (!*slot) { continue; } else
+
+/**
+ * radix_tree_for_each_contig - iterate over all contiguous non-empty slots
+ *
+ * @slot:	the void** for pointer to slot
+ * @root	the struct radix_tree_root pointer
+ * @iter	the struct radix_tree_iter pointer
+ * @start	starting index
+ *
+ * This is double-loop, break does not work.
+ */
+#define radix_tree_for_each_contig(slot, root, iter, start)	\
+	radix_tree_for_each_chunk(slot, root, iter, start,	\
+					RADIX_TREE_ITER_CONTIG)	\
+		radix_tree_for_each_chunk_slot(slot, iter)	\
+			if (!*slot) { (iter)->next_index = 0; break; } else
+
+/**
+ * radix_tree_for_each_tagged - iterate over all tagged slots
+ *
+ * @slot:	the void** for pointer to slot
+ * @root	the struct radix_tree_root pointer
+ * @iter	the struct radix_tree_iter pointer
+ * @start	starting index
+ * @tag		tag index
+ *
+ * This is double-loop, break does not work.
+ */
+#define radix_tree_for_each_tagged(slot, root, iter, start, tag)\
+	radix_tree_for_each_chunk(slot, root, iter, start,	\
+				RADIX_TREE_ITER_TAGGED | tag)	\
+		radix_tree_for_each_chunk_tagged_slot(slot, iter)
+
 #endif /* _LINUX_RADIX_TREE_H */
lib/radix-tree.c +107 -0

119 lines not on this page · raw message

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#4 lore raw

PATCH 3/4 radix-tree: rewrite gang lookup with using iterator

In reply to Konstantin Khlebnikov

Rewrite radix_tree_gang_lookup_* functions with using radix-tree iterator.

---
 lib/radix-tree.c |  315 ++++++++----------------------------------------------
 1 files changed, 45 insertions(+), 270 deletions(-)
lib/radix-tree.c +45 -270
index 32e2bfa..57a93e7 100644
@@ -924,57 +924,6 @@ 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 *indices,
-	unsigned long index, unsigned int max_items, unsigned long *next_index)
-{
-	unsigned int nr_found = 0;
-	unsigned int shift, height;
-	unsigned long i;
-
-	height = slot->height;
-	if (height == 0)
-		goto out;
-	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: grab some items */
-	for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
-		if (slot->slots[i]) {
-			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;
-	return nr_found;
-}
-
 /**
  *	radix_tree_gang_lookup - perform multiple lookup on a radix tree
  *	@root:		radix tree root
@@ -998,50 +947,21 @@ unsigned int
 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
 			unsigned long first_index, unsigned int max_items)
 {
-	unsigned long max_index;
-	struct radix_tree_node *node;
-	unsigned long cur_index = first_index;
-	unsigned int ret;
-
-	node = rcu_dereference_raw(root->rnode);
-	if (!node)
-		return 0;
+	struct radix_tree_iter iter;
+	void **slot;
+	unsigned int ret = 0;
 
-	if (!radix_tree_is_indirect_ptr(node)) {
-		if (first_index > 0)
-			return 0;
-		results[0] = node;
-		return 1;
-	}
-	node = indirect_to_ptr(node);
-
-	max_index = radix_tree_maxindex(node->height);
-
-	ret = 0;
-	while (ret < max_items) {
-		unsigned int nr_found, slots_found, i;
-		unsigned long next_index;	/* Index of next search */
+	if (!max_items)
+		goto out;
 
-		if (cur_index > max_index)
-			break;
-		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;
-			slot = *(((void ***)results)[ret + i]);
-			if (!slot)
-				continue;
-			results[ret + nr_found] =
-				indirect_to_ptr(rcu_dereference_raw(slot));
-			nr_found++;
-		}
-		ret += nr_found;
-		if (next_index == 0)
-			break;
-		cur_index = next_index;
+	radix_tree_for_each_slot(slot, root, &iter, first_index) {
+		results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot));
+		if (!results[ret])
+			continue;
+		if (++ret == max_items)
+			goto out;
 	}
-
+out:
 	return ret;
 }
 EXPORT_SYMBOL(radix_tree_gang_lookup);
@@ -1069,112 +989,25 @@ 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;
-	struct radix_tree_node *node;
-	unsigned long cur_index = first_index;
-	unsigned int ret;
+	struct radix_tree_iter iter;
+	void **slot;
+	unsigned int ret = 0;
 
-	node = rcu_dereference_raw(root->rnode);
-	if (!node)
-		return 0;
+	if (!max_items)
+		goto out;
 
-	if (!radix_tree_is_indirect_ptr(node)) {
-		if (first_index > 0)
-			return 0;
-		results[0] = (void **)&root->rnode;
+	radix_tree_for_each_slot(slot, root, &iter, first_index) {
+		results[ret] = slot;
 		if (indices)
-			indices[0] = 0;
-		return 1;
-	}
-	node = indirect_to_ptr(node);
-
-	max_index = radix_tree_maxindex(node->height);
-
-	ret = 0;
-	while (ret < max_items) {
-		unsigned int slots_found;
-		unsigned long next_index;	/* Index of next search */
-
-		if (cur_index > max_index)
-			break;
-		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;
-		cur_index = next_index;
+			indices[ret] = iter.index;
+		if (++ret == max_items)
+			goto out;
 	}
-
+out:
 	return ret;
 }
 EXPORT_SYMBOL(radix_tree_gang_lookup_slot);
 
-/*
- * FIXME: the two tag_get()s here should use find_next_bit() instead of
- * open-coding the search.
- */
-static unsigned int
-__lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index,
-	unsigned int max_items, unsigned long *next_index, unsigned int tag)
-{
-	unsigned int nr_found = 0;
-	unsigned int shift, height;
-
-	height = slot->height;
-	if (height == 0)
-		goto out;
-	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
-
-	while (height > 0) {
-		unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ;
-
-		for (;;) {
-			if (tag_get(slot, tag, i))
-				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;
-		}
-		height--;
-		if (height == 0) {	/* Bottom level: grab some items */
-			unsigned long j = index & RADIX_TREE_MAP_MASK;
-
-			for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
-				index++;
-				if (!tag_get(slot, tag, j))
-					continue;
-				/*
-				 * Even though the tag was found set, we need to
-				 * recheck that we have a non-NULL node, because
-				 * if this lookup is lockless, it may have been
-				 * subsequently deleted.
-				 *
-				 * Similar care must be taken in any place that
-				 * lookup ->slots[x] without a lock (ie. can't
-				 * rely on its value remaining the same).
-				 */
-				if (slot->slots[j]) {
-					results[nr_found++] = &(slot->slots[j]);
-					if (nr_found == max_items)
-						goto out;
-				}
-			}
-		}
-		shift -= RADIX_TREE_MAP_SHIFT;
-		slot = rcu_dereference_raw(slot->slots[i]);
-		if (slot == NULL)
-			break;
-	}
-out:
-	*next_index = index;
-	return nr_found;
-}
-
 /**
  *	radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
  *	                             based on a tag
@@ -1193,54 +1026,21 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
 		unsigned long first_index, unsigned int max_items,
 		unsigned int tag)
 {
-	struct radix_tree_node *node;
-	unsigned long max_index;
-	unsigned long cur_index = first_index;
-	unsigned int ret;
-
-	/* check the root's tag bit */
-	if (!root_tag_get(root, tag))
-		return 0;
+	struct radix_tree_iter iter;
+	void **slot;
+	unsigned int ret = 0;
 
-	node = rcu_dereference_raw(root->rnode);
-	if (!node)
-		return 0;
-
-	if (!radix_tree_is_indirect_ptr(node)) {
-		if (first_index > 0)
-			return 0;
-		results[0] = node;
-		return 1;
-	}
-	node = indirect_to_ptr(node);
-
-	max_index = radix_tree_maxindex(node->height);
-
-	ret = 0;
-	while (ret < max_items) {
-		unsigned int nr_found, slots_found, i;
-		unsigned long next_index;	/* Index of next search */
+	if (!max_items)
+		goto out;
 
-		if (cur_index > max_index)
-			break;
-		slots_found = __lookup_tag(node, (void ***)results + ret,
-				cur_index, max_items - ret, &next_index, tag);
-		nr_found = 0;
-		for (i = 0; i < slots_found; i++) {
-			struct radix_tree_node *slot;
-			slot = *(((void ***)results)[ret + i]);
-			if (!slot)
-				continue;
-			results[ret + nr_found] =
-				indirect_to_ptr(rcu_dereference_raw(slot));
-			nr_found++;
-		}
-		ret += nr_found;
-		if (next_index == 0)
-			break;
-		cur_index = next_index;
+	radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
+		results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot));
+		if (!results[ret])
+			continue;
+		if (++ret == max_items)
+			goto out;
 	}
-
+out:
 	return ret;
 }
 EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
@@ -1263,44 +1063,19 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
 		unsigned long first_index, unsigned int max_items,
 		unsigned int tag)
 {
-	struct radix_tree_node *node;
-	unsigned long max_index;
-	unsigned long cur_index = first_index;
-	unsigned int ret;
+	struct radix_tree_iter iter;
+	void **slot;
+	unsigned int ret = 0;
 
-	/* check the root's tag bit */
-	if (!root_tag_get(root, tag))
-		return 0;
-
-	node = rcu_dereference_raw(root->rnode);
-	if (!node)
-		return 0;
-
-	if (!radix_tree_is_indirect_ptr(node)) {
-		if (first_index > 0)
-			return 0;
-		results[0] = (void **)&root->rnode;
-		return 1;
-	}
-	node = indirect_to_ptr(node);
-
-	max_index = radix_tree_maxindex(node->height);
-
-	ret = 0;
-	while (ret < max_items) {
-		unsigned int slots_found;
-		unsigned long next_index;	/* Index of next search */
+	if (!max_items)
+		goto out;
 
-		if (cur_index > max_index)
-			break;
-		slots_found = __lookup_tag(node, results + ret,
-				cur_index, max_items - ret, &next_index, tag);
-		ret += slots_found;
-		if (next_index == 0)
-			break;
-		cur_index = next_index;
+	radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
+		results[ret] = slot;
+		if (++ret == max_items)
+			goto out;
 	}
-
+out:
 	return ret;
 }
 EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#5 lore raw

PATCH 4/4 radix-tree: use iterators in find_get_pages* functions

In reply to Konstantin Khlebnikov

This patch replaces radix_tree_gang_lookup_slot() and radix_tree_gang_lookup_tag_slot() in page-cache lookup functions with brand-new radix-tree direct iterating. This avoids the double-scanning and pointers copying.

---
 mm/filemap.c |   75 ++++++++++++++++++++++++++++++++++------------------------
 mm/shmem.c   |   23 +++++++++++-------
 2 files changed, 58 insertions(+), 40 deletions(-)
mm/filemap.c +44 -31
index b662757..518223b 100644
@@ -811,23 +811,25 @@ EXPORT_SYMBOL(find_or_create_page);
 unsigned find_get_pages(struct address_space *mapping, pgoff_t start,
 			    unsigned int nr_pages, struct page **pages)
 {
-	unsigned int i;
 	unsigned int ret;
 	unsigned int nr_found, nr_skip;
+	struct radix_tree_iter iter;
+	void **slot;
+
+	if (!nr_pages)
+		return 0;
 
 	rcu_read_lock();
 restart:
-	nr_found = radix_tree_gang_lookup_slot(&mapping->page_tree,
-				(void ***)pages, NULL, start, nr_pages);
-	ret = 0;
-	nr_skip = 0;
-	for (i = 0; i < nr_found; i++) {
+	nr_found = nr_skip = ret = 0;
+	radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start) {
 		struct page *page;
 repeat:
-		page = radix_tree_deref_slot((void **)pages[i]);
+		page = radix_tree_deref_slot(slot);
 		if (unlikely(!page))
 			continue;
 
+		nr_found++;
 		if (radix_tree_exception(page)) {
 			if (radix_tree_deref_retry(page)) {
 				/*
@@ -835,7 +837,7 @@ repeat:
 				 * when entry at index 0 moves out of or back
 				 * to root: none yet gotten, safe to restart.
 				 */
-				WARN_ON(start | i);
+				WARN_ON(iter.index);
 				goto restart;
 			}
 			/*
@@ -851,13 +853,14 @@ repeat:
 			goto repeat;
 
 		/* Has the page moved? */
-		if (unlikely(page != *((void **)pages[i]))) {
+		if (unlikely(page != *slot)) {
 			page_cache_release(page);
 			goto repeat;
 		}
 
 		pages[ret] = page;
-		ret++;
+		if (++ret == nr_pages)
+			goto out;
 	}
 
 	/*
@@ -866,6 +869,7 @@ repeat:
 	 */
 	if (unlikely(!ret && nr_found > nr_skip))
 		goto restart;
+out:
 	rcu_read_unlock();
 	return ret;
 }
@@ -885,21 +889,23 @@ repeat:
 unsigned find_get_pages_contig(struct address_space *mapping, pgoff_t index,
 			       unsigned int nr_pages, struct page **pages)
 {
-	unsigned int i;
+	struct radix_tree_iter iter;
 	unsigned int ret;
-	unsigned int nr_found;
+	void **slot;
+
+	if (!nr_pages)
+		return 0;
 
 	rcu_read_lock();
 restart:
-	nr_found = radix_tree_gang_lookup_slot(&mapping->page_tree,
-				(void ***)pages, NULL, index, nr_pages);
 	ret = 0;
-	for (i = 0; i < nr_found; i++) {
+	radix_tree_for_each_contig(slot, &mapping->page_tree, &iter, index) {
 		struct page *page;
 repeat:
-		page = radix_tree_deref_slot((void **)pages[i]);
+		page = radix_tree_deref_slot(slot);
+		/* The hole, there no reason to continue */
 		if (unlikely(!page))
-			continue;
+			goto out;
 
 		if (radix_tree_exception(page)) {
 			if (radix_tree_deref_retry(page)) {
@@ -915,14 +921,14 @@ repeat:
 			 * here as an exceptional entry: so stop looking for
 			 * contiguous pages.
 			 */
-			break;
+			goto out;
 		}
 
 		if (!page_cache_get_speculative(page))
 			goto repeat;
 
 		/* Has the page moved? */
-		if (unlikely(page != *((void **)pages[i]))) {
+		if (unlikely(page != *slot)) {
 			page_cache_release(page);
 			goto repeat;
 		}
@@ -932,15 +938,16 @@ repeat:
 		 * otherwise we can get both false positives and false
 		 * negatives, which is just confusing to the caller.
 		 */
-		if (page->mapping == NULL || page->index != index) {
+		if (page->mapping == NULL || page->index != iter.index) {
 			page_cache_release(page);
-			break;
+			goto out;
 		}
 
 		pages[ret] = page;
-		ret++;
-		index++;
+		if (++ret == nr_pages)
+			goto out;
 	}
+out:
 	rcu_read_unlock();
 	return ret;
 }
@@ -960,22 +967,26 @@ EXPORT_SYMBOL(find_get_pages_contig);
 unsigned find_get_pages_tag(struct address_space *mapping, pgoff_t *index,
 			int tag, unsigned int nr_pages, struct page **pages)
 {
-	unsigned int i;
 	unsigned int ret;
 	unsigned int nr_found;
+	struct radix_tree_iter iter;
+	void **slot;
+
+	if (!nr_pages)
+		return 0;
 
 	rcu_read_lock();
 restart:
-	nr_found = radix_tree_gang_lookup_tag_slot(&mapping->page_tree,
-				(void ***)pages, *index, nr_pages, tag);
-	ret = 0;
-	for (i = 0; i < nr_found; i++) {
+	nr_found = ret = 0;
+	radix_tree_for_each_tagged(slot, &mapping->page_tree,
+				   &iter, *index, tag) {
 		struct page *page;
 repeat:
-		page = radix_tree_deref_slot((void **)pages[i]);
+		page = radix_tree_deref_slot(slot);
 		if (unlikely(!page))
 			continue;
 
+		nr_found++;
 		if (radix_tree_exception(page)) {
 			if (radix_tree_deref_retry(page)) {
 				/*
@@ -996,13 +1007,14 @@ repeat:
 			goto repeat;
 
 		/* Has the page moved? */
-		if (unlikely(page != *((void **)pages[i]))) {
+		if (unlikely(page != *slot)) {
 			page_cache_release(page);
 			goto repeat;
 		}
 
 		pages[ret] = page;
-		ret++;
+		if (++ret == nr_pages)
+			goto out;
 	}
 
 	/*
@@ -1011,6 +1023,7 @@ repeat:
 	 */
 	if (unlikely(!ret && nr_found))
 		goto restart;
+out:
 	rcu_read_unlock();
 
 	if (ret)
mm/shmem.c +14 -9
index 269d049..5033319 100644
@@ -316,21 +316,24 @@ static unsigned shmem_find_get_pages_and_swap(struct address_space *mapping,
 					pgoff_t start, unsigned int nr_pages,
 					struct page **pages, pgoff_t *indices)
 {
-	unsigned int i;
 	unsigned int ret;
 	unsigned int nr_found;
+	struct radix_tree_iter iter;
+	void **slot;
+
+	if (!nr_pages)
+		return 0;
 
 	rcu_read_lock();
 restart:
-	nr_found = radix_tree_gang_lookup_slot(&mapping->page_tree,
-				(void ***)pages, indices, start, nr_pages);
-	ret = 0;
-	for (i = 0; i < nr_found; i++) {
+	nr_found = ret = 0;
+	radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start) {
 		struct page *page;
 repeat:
-		page = radix_tree_deref_slot((void **)pages[i]);
+		page = radix_tree_deref_slot(slot);
 		if (unlikely(!page))
 			continue;
+		nr_found++;
 		if (radix_tree_exception(page)) {
 			if (radix_tree_deref_retry(page))
 				goto restart;
@@ -345,17 +348,19 @@ repeat:
 			goto repeat;
 
 		/* Has the page moved? */
-		if (unlikely(page != *((void **)pages[i]))) {
+		if (unlikely(page != *slot)) {
 			page_cache_release(page);
 			goto repeat;
 		}
 export:
-		indices[ret] = indices[i];
+		indices[ret] = iter.index;
 		pages[ret] = page;
-		ret++;
+		if (++ret == nr_pages)
+			goto out;
 	}
 	if (unlikely(!ret && nr_found))
 		goto restart;
+out:
 	rcu_read_unlock();
 	return ret;
 }

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#6 lore raw
In reply to Konstantin Khlebnikov
Quoted 2 lines · Konstantin Khlebnikov

This patchset implements common radix-tree iteration routine and reworks page-cache lookup functions with using it.

So what's the advantage? Both the line counts and the bloat-o-meter seems to imply this is all just bad.

I assume there is some upside to it, but you really don't make that obvious, so why should anybody ever waste even a second of time looking at this?

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#7 lore raw
Quoted 7 lines · Linus Torvalds
Quoted 2 lines · Konstantin Khlebnikov

This patchset implements common radix-tree iteration routine and reworks page-cache lookup functions with using it.

So what's the advantage? Both the line counts and the bloat-o-meter seems to imply this is all just bad.

If do not count comments here actually is negative line count change. And if drop (almost) unused radix_tree_gang_lookup_tag_slot() and radix_tree_gang_lookup_slot() total bloat-o-meter score becomes negative too. There also some shrinkable stuff in shmem code.
So, if this is really a problem it is fixable. I just didn't want to bloat patchset.

Quoted 4 lines

I assume there is some upside to it, but you really don't make that obvious, so why should anybody ever waste even a second of time looking at this?

Hmm, from my point of view, this unified iterator code looks cleaner than current duplicated radix-tree code. That's why I was titled it "cleanup".

There also some simple bit-hacks: find-next-bit instead of dumb loops in tagged-lookup.

Here some benchmark results: there is radix-tree with 1024 slots, I fill and tag every <step> slot, and run lookup for all slots with radix_tree_gang_lookup() and radix_tree_gang_lookup_tag() in the loop. old/new rows -- nsec per iteration over whole tree.

tagged-lookup
step 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
old 7035 5248 4742 4308 4217 4133 4030 3920 4038 3933 3914 3796 3851 3755 3819 3582
new 3578 2617 1899 1426 1220 1058 936 822 845 749 695 679 648 575 591 509

so, new tagged-lookup always faster, especially for sparse trees.

normal-lookup
step 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
old 4156 2641 2068 1837 1630 1531 1467 1415 1373 1398 1333 1323 1308 1280 1236 1249
new 3048 2520 2429 2280 2266 2296 2215 2219 2188 2170 2218 2332 2166 2096 2100 2058

New normal lookup works faster for dense trees, on sparse trees it slower. Looks like it caused by struct radix_tree_iter aliasing,
gcc cannot effectively use its field as loop counter in nested-loop. But how important is this? Anyway, I'll think how to fix this misfortune.

Quoted 2 lines

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#8 lore raw
Quoted 2 lines · Konstantin Khlebnikov

If do not count comments here actually is negative line count change.

Ok, fair enough.

Quoted 3 lines

And if drop (almost) unused radix_tree_gang_lookup_tag_slot() and radix_tree_gang_lookup_slot() total bloat-o-meter score becomes negative too.

Good.

Quoted 9 lines

There also some simple bit-hacks: find-next-bit instead of dumb loops in tagged-lookup.

Here some benchmark results: there is radix-tree with 1024 slots, I fill and tag every <step> slot,
and run lookup for all slots with radix_tree_gang_lookup() and radix_tree_gang_lookup_tag() in the loop.
old/new rows -- nsec per iteration over whole tree.

Quoted 6 lines

tagged-lookup
step    1       2       3       4       5       6       7       8       9       10      11      12      13      14      15      16 old     7035    5248    4742    4308    4217    4133    4030    3920    4038    3933    3914    3796    3851    3755    3819    3582 new     3578    2617    1899    1426    1220    1058    936     822     845     749     695     679     648     575     591     509

so, new tagged-lookup always faster, especially for sparse trees.

Do you have any benchmarks when it's actually used by higher levels, though? I guess that will involve find_get_pages(), and we don't have all that any of them, but it would be lovely to see some real load (even if it is limited to one of the filesystems that uses this) numbers too..

Quoted 1 line

New normal lookup works faster for dense trees, on sparse trees it slower.

I think that should be the common case, so that may be fine. Again, it would be nice to see numbers that are for something else than just the lookup - an actual use of it in some real context.

Anyway, the patches themselves looked fine to me, modulo the fact that I wasn't all that happy with the new __find_next_bit, and I think it's better to not expose it in a generic header file. But I would really like to see more "real" numbers for the series

Thanks,

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#9 lore raw
Quoted 27 lines · Linus Torvalds
Quoted 2 lines · Konstantin Khlebnikov

If do not count comments here actually is negative line count change.

Ok, fair enough.

Quoted 3 lines

And if drop (almost) unused radix_tree_gang_lookup_tag_slot() and radix_tree_gang_lookup_slot() total bloat-o-meter score becomes negative too.

Good.

Quoted 14 lines

There also some simple bit-hacks: find-next-bit instead of dumb loops in tagged-lookup.

Here some benchmark results: there is radix-tree with 1024 slots, I fill and tag every <step> slot,
and run lookup for all slots with radix_tree_gang_lookup() and radix_tree_gang_lookup_tag() in the loop.
old/new rows -- nsec per iteration over whole tree.

tagged-lookup
step 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

old   7035  5248  4742  4308  4217  4133  4030  3920  4038  3933  3914  3796  3851  3755  3819  3582
new   3578  2617  1899  1426  1220  1058  936   822   845   749   695   679   648   575   591   509
Quoted 7 lines
Quoted 1 line

so, new tagged-lookup always faster, especially for sparse trees.

Do you have any benchmarks when it's actually used by higher levels, though? I guess that will involve find_get_pages(), and we don't have all that any of them, but it would be lovely to see some real load (even if it is limited to one of the filesystems that uses this) numbers too..

It's also a very small tree size to test - 1024 slots is only 4MB of page cache data, but we regularly cache GBs of pages in a single tree.

Quoted 1 line
Quoted 1 line

New normal lookup works faster for dense trees, on sparse trees it slower.

Testing large trees (in the millions of entries) might show different results - I'd be interested to see the difference there given that iterating large trees is very common (e.g. in the writeback code)....

Quoted 3 lines

I think that should be the common case, so that may be fine. Again, it would be nice to see numbers that are for something else than just the lookup - an actual use of it in some real context.

XFS also uses radix trees for it's inode caches and AG indexes. We iterate those trees by both normal and tagged lookups in different contexts, but it is extremely difficult to isolate the tree traversal from everything else that is going on around them, so I can't really help with a microbenchmark there...

Cheers,

Dave.

Signature · 9 lines
Dave Chinner
[email protected]

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#10 lore raw
In reply to Konstantin Khlebnikov

Any updates on this series?

Quoted 38 lines · Konstantin Khlebnikov

This patchset implements common radix-tree iteration routine and reworks page-cache lookup functions with using it.

radix_tree_gang_lookup_*slot() now mostly unused (the last user somethere in drivers/sh/intc/virq.c), but they are exported, we cannot remove them for now.

Also there some shmem-related radix-tree hacks can be reworked, radix_tree_locate_item() can be removed. I already have a few extra patches.

And as usual my lovely bloat-o-meter:

add/remove: 4/3 grow/shrink: 4/4 up/down: 1232/-964 (268)

function                                     old     new   delta
radix_tree_next_chunk                          -     499    +499
static.shmem_find_get_pages_and_swap           -     404    +404
find_get_pages_tag                           354     488    +134
find_get_pages                               362     438     +76
find_get_pages_contig                        345     407     +62
__kstrtab_radix_tree_next_chunk                -      22     +22
shmem_truncate_range                        1633    1652     +19
__ksymtab_radix_tree_next_chunk                -      16     +16
radix_tree_gang_lookup_tag_slot              208     180     -28
radix_tree_gang_lookup_tag                   247     207     -40
radix_tree_gang_lookup_slot                  204     162     -42
radix_tree_gang_lookup                       231     160     -71
__lookup                                     217       -    -217
__lookup_tag                                 242       -    -242
shmem_find_get_pages_and_swap                324       -    -324

---

Konstantin Khlebnikov (4):
bitops: implement "optimized" __find_next_bit()
radix-tree: introduce bit-optimized iterator
radix-tree: rewrite gang lookup with using iterator
radix-tree: use iterators in find_get_pages* functions

Quoted 16 lines
 include/asm-generic/bitops/find.h |   36 +++
 include/linux/radix-tree.h        |  129 +++++++++++
 lib/radix-tree.c                  |  422 +++++++++++++------------------------
 mm/filemap.c                      |   75 ++++---
 mm/shmem.c                        |   23 +-
 5 files changed, 375 insertions(+), 310 deletions(-)
Signature · 8 lines
Signature

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

---end quoted text---

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#11 lore raw
Quoted 1 line · Christoph Hellwig

Any updates on this series?

I had sent "[PATCH v2 0/3] radix-tree: general iterator" February 10, there is no more updates after that. I just checked v2 on top "next-20120314" -- looks like all ok.

Quoted 50 lines · Konstantin Khlebnikov
Quoted 48 lines

This patchset implements common radix-tree iteration routine and reworks page-cache lookup functions with using it.

radix_tree_gang_lookup_*slot() now mostly unused (the last user somethere in drivers/sh/intc/virq.c), but they are exported, we cannot remove them for now.

Also there some shmem-related radix-tree hacks can be reworked, radix_tree_locate_item() can be removed. I already have a few extra patches.

And as usual my lovely bloat-o-meter:

add/remove: 4/3 grow/shrink: 4/4 up/down: 1232/-964 (268)

function                                     old     new   delta
radix_tree_next_chunk                          -     499    +499
static.shmem_find_get_pages_and_swap           -     404    +404
find_get_pages_tag                           354     488    +134
find_get_pages                               362     438     +76
find_get_pages_contig                        345     407     +62
__kstrtab_radix_tree_next_chunk                -      22     +22
shmem_truncate_range                        1633    1652     +19
__ksymtab_radix_tree_next_chunk                -      16     +16
radix_tree_gang_lookup_tag_slot              208     180     -28
radix_tree_gang_lookup_tag                   247     207     -40
radix_tree_gang_lookup_slot                  204     162     -42
radix_tree_gang_lookup                       231     160     -71
__lookup                                     217       -    -217
__lookup_tag                                 242       -    -242
shmem_find_get_pages_and_swap                324       -    -324

---

Konstantin Khlebnikov (4):
bitops: implement "optimized" __find_next_bit()
radix-tree: introduce bit-optimized iterator
radix-tree: rewrite gang lookup with using iterator
radix-tree: use iterators in find_get_pages* functions

  include/asm-generic/bitops/find.h |   36 +++
  include/linux/radix-tree.h        |  129 +++++++++++
  lib/radix-tree.c                  |  422 +++++++++++++------------------------
  mm/filemap.c                      |   75 ++++---
  mm/shmem.c                        |   23 +-
  5 files changed, 375 insertions(+), 310 deletions(-)

--
Signature

Quoted 7 lines
Quoted 6 lines

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email:<a href=mailto:"[email protected]"> [email protected]</a>

---end quoted text---

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#12 lore raw
Quoted 5 lines · Konstantin Khlebnikov
Quoted 1 line · Christoph Hellwig

Any updates on this series?

I had sent "[PATCH v2 0/3] radix-tree: general iterator" February 10, there is no more updates after that. I just checked v2 on top "next-20120314" -- looks like all ok.

this was more a question to the MM maintainers if this is getting merged or if there were any further comments.

We'd really like to have this interface to simplify some code in XFS.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

maintainer
#13 lore raw
Quoted 9 lines · Christoph Hellwig
Quoted 5 lines · Konstantin Khlebnikov
Quoted 1 line · Christoph Hellwig

Any updates on this series?

I had sent "[PATCH v2 0/3] radix-tree: general iterator" February 10, there is no more updates after that. I just checked v2 on top "next-20120314" -- looks like all ok.

this was more a question to the MM maintainers if this is getting merged or if there were any further comments.

I haven't studied the code at all - I'm afraid Konstantin is rather more productive than I can keep up with, and other bugs and patches appeared to be more urgent and important.

But I have included that work in most of my testing for four weeks now, and observed no problems whatever from it. And I made a patch for the radix-tree test harness which akpm curates, to update its radix-tree.c to Konstantin's: those tests ran perfectly on 64-bit and on 32-bit. That patch to rtth appended below.

(I do have, or expect to have once I study them, reservations about his subsequent changes to radix-tree usage in mm/shmem.c; and even if I end up agreeing with his changes, would prefer to hold them off until after the tmpfs fallocation mods are in - other work which had to yield to higher priorities, ready but not yet commented.)

Quoted 2 lines

We'd really like to have this interface to simplify some code in XFS.

That's useful info: let's raise its priority, and hope that someone faster than me (not a narrow category...) gets to review it.

Hugh

[PATCH] rtth: update to KK's radix-tree iterator

Makefile renamed from Makefile.0 +2 -1
@@ -2,7 +2,8 @@
 CFLAGS += -I. -g -Wall -D_LGPL_SOURCE
 LDFLAGS += -lpthread -lurcu
 TARGETS = main
-OFILES = main.o radix-tree.o linux.o test.o tag_check.o regression1.o regression2.o
+OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_next_bit.o \
+	 regression1.o regression2.o
 
 targets: $(TARGETS)
 
find_next_bit.c renamed from find_next_bit.c.0 +57 -0

57 lines not on this page · raw message

linux/bitops.h renamed from linux/bitops.h.0 +39 -0
@@ -108,4 +108,43 @@ static inline int test_bit(int nr, const
 	return 1UL & (addr[BITOP_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
 }
 
+/**
+ * __ffs - find first bit in word.
+ * @word: The word to search
+ *
+ * Undefined if no bit exists, so code should check against 0 first.
+ */
+static inline unsigned long __ffs(unsigned long word)
+{
+	int num = 0;
+
+	if ((word & 0xffffffff) == 0) {
+		num += 32;
+		word >>= 32;
+	}
+	if ((word & 0xffff) == 0) {
+		num += 16;
+		word >>= 16;
+	}
+	if ((word & 0xff) == 0) {
+		num += 8;
+		word >>= 8;
+	}
+	if ((word & 0xf) == 0) {
+		num += 4;
+		word >>= 4;
+	}
+	if ((word & 0x3) == 0) {
+		num += 2;
+		word >>= 2;
+	}
+	if ((word & 0x1) == 0)
+		num += 1;
+	return num;
+}
+
+unsigned long find_next_bit(const unsigned long *addr,
+			    unsigned long size,
+			    unsigned long offset);
+
 #endif /* _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ */
linux/kernel.h renamed from linux/kernel.h.0 +1 -0
@@ -14,6 +14,7 @@
 #define panic(expr)
 #define printk printf
 #define __force
+#define likely(c) (c)
 #define unlikely(c) (c)
 #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
 
linux/radix-tree.h renamed from linux/radix-tree.h.0 +140 -0

156 lines not on this page · raw message

radix-tree.c renamed from radix-tree.c.0 +180 -258

509 lines not on this page · raw message

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

maintainer
#14 lore raw
Quoted 4 lines · On Wed, 14 Mar 2012 12:36:11 -0700 (PDT) Hugh Dickins <[email protected]> wrote:
Quoted 3 lines · Christoph Hellwig
Quoted 2 lines · Konstantin Khlebnikov
Quoted 1 line · Christoph Hellwig

Any updates on this series?

Linus took an interest, so I went to sleep. It seems that a role reversal is in order ;)

Quoted 9 lines
Quoted 5 lines
Quoted 2 lines

I had sent "[PATCH v2 0/3] radix-tree: general iterator" February 10, there is no more updates after that. I just checked v2 on top "next-20120314" -- looks like all ok.

this was more a question to the MM maintainers if this is getting merged or if there were any further comments.

I haven't studied the code at all - I'm afraid Konstantin is rather more productive than I can keep up with, and other bugs and patches appeared to be more urgent and important.

I'll take a look.

Quoted 4 lines

And I made a patch for the
radix-tree test harness which akpm curates, to update its radix-tree.c to Konstantin's: those tests ran perfectly on 64-bit and on 32-bit. That patch to rtth appended below.

Thanks.

Quoted 5 lines

(I do have, or expect to have once I study them, reservations about his subsequent changes to radix-tree usage in mm/shmem.c; and even if I end up agreeing with his changes, would prefer to hold them off until after the tmpfs fallocation mods are in - other work which had to yield to higher priorities, ready but not yet commented.)

OK, I shall forget all about that followup series this time around.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>