Andrew Morton wrote:
On Fri, 10 Feb 2012 23:25:42 +0400
Konstantin Khlebnikov<khlebnikov@xxxxxxxxxx> wrote:
This patch implements 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 patch 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.
...
+
+static inline
+void **radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
Nit: if we're going to line break a function definition/declaration
line like this then the usual way is to split it before the function
name, so
static inline void **
radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
Old-school people did this so they could find the function with
/^radix_tree_iter_init in vi ;)
Thanks for watching! I'll try to fix all style problems.
+{
+ iter->index = 0; /* to bypass next_index overflow protection */
+ iter->next_index = start;
+ return NULL;
+}
Why didn't it initialize .tags?
In fact .tags only ever gets initialized deep inside
radix_tree_next_chunk(), if !radix_tree_is_indirect_ptr(). Is this
correct?
Yes, it correct.
.tags can be used only after success radix_tree_next_chunk() calling with RADIX_TREE_ITER_TAGGED
It initialized in two places: one for trivial single-entry tree and one at the end for normal chunk.
...
+/**
+ * radix_tree_next_slot - find next slot in chunk
+ *
+ * @slot pointer to slot
+ * @iter iterator state
+ * @flags RADIX_TREE_ITER_*
+ *
+ * Returns pointer to next slot, or NULL if no more left.
+ */
+static __always_inline
+void **radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
+ unsigned flags)
+{
+ unsigned size, offset;
'offset' could be made local to the single code block which uses it.
personally I find that this leads to clearer code.
+ size = radix_tree_chunk_size(iter) - 1;
radix_tree_chunk_size() returns unsigned long, and we just threw away
the upper 32 bits. I'm unsure if that's a bug, but it's messy and
possibly inefficient.
Would it be better to convert all to unsigned long?
As I remember, I was played there a lot trying to shrink code size for x86_64.
This function is really hot, so it should be carefully optimized.
+ 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)&& size)
+ return NULL;
+ if (likely(iter->tags)) {
+ offset = __ffs(iter->tags);
+ iter->tags>>= offset;
+ iter->index += offset + 1;
+ return slot + offset + 1;
+ }
+ } else {
+ while (size--) {
+ slot++;
+ iter->index++;
+ if (likely(*slot))
+ return slot;
+ if (flags& RADIX_TREE_ITER_CONTIG)
+ return NULL;
+ }
+ }
+ return NULL;
+}
This is a whopping big function. Why was it inlined? Are you sure
that was a correct decision?
Ok, I'll split it in two: for cases with/without RADIX_TREE_ITER_TAGGED,
and split radix_tree_for_each_chunk_slot() macro in two: tagged and non-tagged.
+/**
+ * radix_tree_for_each_chunk - iterate over chunks
+ *
+ * @slot: the void** for pointer to chunk 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
Some of the arguments have a colon, others don't.
+ * Locks can be released and reasquired between iterations.
"reacquired"
+ */
+#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)) ; )
I don't think I understand this whole interface :(
The term "chunk" has not been defined anywhere in the code, which
doesn't help.
Ok, description must be fixed.
"chunk" is array of slot-pointers from radix tree leaf node.
radix_tree_for_each_chunk() iterates through radix-tree with with long steps.
Iterator body can work with chunk as with array: slot[0..radix_tree_chunk_size(iter)-1]
or iterate through it with help radix_tree_for_each_chunk_slot()
Neither radix_tree_for_each_chunk() nor
radix_tree_for_each_chunk_slot() get used anywhere in this patchset so
one can't go look at call sites to work out what they're for.
It was used it in "[PATCH 3/4] shmem: use radix-tree iterator in shmem_unuse_inode()" from
"[PATCH 0/4] shmem: radix-tree cleanups and swapoff optimizations"
It's a strange iterator - it never terminates. It requires that the
caller have an open-coded `break' in the search loop.
It terminates if radix_tree_next_chunk() returns NULL.
A bit more description and perhaps a usage example would help.
+/**
+ * radix_tree_for_each_chunk_slot - iterate over slots in one chunk
+ *
+ * @slot: the void** for pointer to slot
+ * @iter the struct radix_tree_iter pointer
+ * @flags RADIX_TREE_ITER_*
+ */
+#define radix_tree_for_each_chunk_slot(slot, iter, flags) \
+ for ( ; slot ; slot = radix_tree_next_slot(slot, iter, flags) )
Similar observations here.
+/**
+ * radix_tree_for_each_slot - iterate over all 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
+ */
+#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) )
All of these macros reference some of their arguments more than once.
So wierd and wrong things will happen if they are invoked with an
expression-with-side-effects. Also they lack parenthesisation, so
radix_tree_for_each_slot(myslot + 1, ...)
slot must be lvalue, like "pos" in list_for_each_entry()
Description not explains arguments' roles...
won't compile. The first problem is more serious than the second.
This is always a pain with complex macros and fixing it here would
deeply uglify the code. It's unlikely that anyone will be invoking
these with expression-with-side-effects so I'd be inclined to just live
with the dangers.
otoh, someone *might* do
radix_tree_for_each_slot(slot,
expensive_function_which_returns_a_root(),
iter, start);
and we'd call expensive_function_which_returns_a_root() each time
around the loop. But I don't think this is fixable.
Anyway, have a think about it all.
list_for_each_entry() do the same for "head" argument, I think this is ok.
+/**
+ * radix_tree_for_each_contig - iterate over all contiguous slots
Now what does this mean? Given a slot, iterate over that slot and all
contiguous successor slots until we encounter a hole?
It start from "start" index and iterate till first empty slot.
Maybe. Again, better interface descriptions are needed, please.
+ * @slot: the void** for pointer to slot
+ * @root the struct radix_tree_root pointer
+ * @iter the struct radix_tree_iter pointer
+ * @start starting 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 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
+ */
+#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 */
...
+static 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;
+}
Beware that gcc will freely ignore your "inline" directive.
When I compiled it, gcc did appear to inline it. Then I added
__always_inline and it was still inlined, but the text section in the
.o file got 20 bytes larger. Odd.
/*
* 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 +649,117 @@ 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 first slots in chunk, or NULL if there no more left
+ */
+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 i, index;
When a c programmer sees a variable called "i", he solidly expects it
to have type "int". Please choose a better name for this guy!
Perferably something which helps the reader understand what the
variable's role is.
=) Ok, I can make it "int"
+ if ((flags& RADIX_TREE_ITER_TAGGED)&& !root_tag_get(root, tag))
+ return NULL;
+
+ /*
+ * Catch next_index overflow after ~0UL.
+ * iter->index can be zero only at the beginning.
+ * Because RADIX_TREE_MAP_SHIFT< BITS_PER_LONG we cannot
+ * oveflow iter->next_index in single step.
+ */
+ 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;
+ i = index>> shift;
+
+ /* Index ouside of the tree */
+ if (i>= RADIX_TREE_MAP_SIZE)
+ return NULL;
+
+ node = rnode;
+ while (1) {
+ if ((flags& RADIX_TREE_ITER_TAGGED) ?
+ !test_bit(i, node->tags[tag]) :
+ !node->slots[i]) {
+ /* Hole detected */
+ if (flags& RADIX_TREE_ITER_CONTIG)
+ return NULL;
+
+ if (flags& RADIX_TREE_ITER_TAGGED)
+ i = radix_tree_find_next_bit(node->tags[tag],
+ RADIX_TREE_MAP_SIZE, i + 1);
+ else
+ while (++i< RADIX_TREE_MAP_SIZE&&
+ !node->slots[i]);
+
+ index&= ~((RADIX_TREE_MAP_SIZE<< shift) - 1);
+ index += i<< shift;
+ /* Overflow after ~0UL */
+ if (!index)
+ return NULL;
+ if (i == RADIX_TREE_MAP_SIZE)
+ goto restart;
+ }
+
+ /* This is leaf-node */
+ if (!shift)
+ break;
+
+ node = rcu_dereference_raw(node->slots[i]);
+ if (node == NULL)
+ goto restart;
+ shift -= RADIX_TREE_MAP_SHIFT;
+ i = (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 bitmask from node->tags[tag] array */
+ if (flags& RADIX_TREE_ITER_TAGGED) {
+ unsigned tag_long, tag_bit;
+
+ tag_long = i / BITS_PER_LONG;
+ tag_bit = i % 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 + i;
+}
+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
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxx. 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:"dont@xxxxxxxxx";> email@xxxxxxxxx</a>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxx. 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:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>