radix_tree_next_chunk: redundant search for next slot in hole
Hi, I am running Phoronix-fio benchmark on Linux kernel 4.18.0-rc5. I observe that radix_tree_next_chunk search shows some form of a redundant walk while called from radix_tree_for_each_slot iterator. While searching for next slot in a hole, it walks through the same slots over n over. void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root, struct radix_tree_iter *iter, unsigned flags) { ... if ((flags & RADIX_TREE_ITER_TAGGED) ? !tag_get(node, tag, offset) : !child) { ... while (++offset < RADIX_TREE_MAP_SIZE) { void *slot = rcu_dereference_raw( /* redundant slot walk */ node->slots[offset]); if (slot) break; } } ... } Can you please explain such behavior? Any feedback/recommendation about this case is very welcome. -- Probir Roy
On Fri, 03 May 2019 16:03:46 -0500, Probir Roy said:
While searching for next slot in a hole, it walks through the same slots over n over.
How did you determine this?
while (++offset < RADIX_TREE_MAP_SIZE) { void *slot = rcu_dereference_raw( /* redundant slot walk */ node->slots[offset]); if (slot) break; }
Looks to me like the ++offset will walk through each potential slot once, and break out if it finds one. I haven't looked at the code closely, perhaps what you're seeing is repeated scan/merge/rescan behavior? Often, compacting a data structure requires multiple passes.
While searching for next slot in a hole, it walks through the same slots over n over.
How did you determine this?
I am working on a tool that identifies repeated load of an address. Often these repeated loads are redundant and can be avoided with data structure modification. The tool points me to this line.
Looks to me like the ++offset will walk through each potential slot once, and break out if it finds one.
This function is being called by the radix_tree_for_each_slot iterator, defined as follows: #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)) Here is the calling context I get: |_ depth: 1 :0, method: ext4_block_write_begin+0x335/0x4f0(), |_ depth: 2 :0, method: alloc_buffer_head+0x21/0x60(), |_ depth: 3 :0, method: ext4_da_get_block_prep+0x1a6/0x490(), |_ depth: 4 :0, method: clean_bdev_aliases+0x9a/0x210(), |_ depth: 5 :0, method: pagevec_lookup_range+0x24/0x30(), |_ depth: 6 :0, method: find_get_pages_range+0x151/0x2d0(), |_ depth: 7 :0, method: radix_tree_next_chunk+0x10f/0x360() Does it explain the case?
I haven't looked at the code closely, perhaps what you're seeing is repeated scan/merge/rescan behavior? Often, compacting a data structure requires multiple passes.
If that's the case, can this repeated search for the next valid slot be avoided by caching/storing the next valid slot? -- Probir Roy
On Fri, 03 May 2019 19:00:26 -0500, Probir Roy said:
While searching for next slot in a hole, it walks through the same slots over n over.
How did you determine this?
I am working on a tool that identifies repeated load of an address. Often these repeated loads are redundant and can be avoided with data structure modification. The tool points me to this line.
Is this doing static analysis, or actually doing run-time tracing?
Looks to me like the ++offset will walk through each potential slot once, and break out if it finds one.
This function is being called by the radix_tree_for_each_slot iterator, defined as follows:
#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))
Here is the calling context I get: |_ depth: 1 :0, method: ext4_block_write_begin+0x335/0x4f0(), |_ depth: 2 :0, method: alloc_buffer_head+0x21/0x60(), |_ depth: 3 :0, method: ext4_da_get_block_prep+0x1a6/0x490(), |_ depth: 4 :0, method: clean_bdev_aliases+0x9a/0x210(), |_ depth: 5 :0, method: pagevec_lookup_range+0x24/0x30(), |_ depth: 6 :0, method: find_get_pages_range+0x151/0x2d0(), |_ depth: 7 :0, method: radix_tree_next_chunk+0x10f/0x360()
Does it explain the case?
Actually, that calling context doesn't tell us much of anything till depth 7. Yes, next_chunk() and next_slot() can get called repeatedly, especially if it's a large radix tree. The important question is: Is it being called with the *same value* of 'slot' repeatedly? Looking at the code, it's pretty obvious that 'slot' will be updated at least once through every pass through the for_each_slot(), unless the radix tree is corrupted. If you're trying to do static analysis, your code may be confused by either the 'slot || next_chunk()' iterator, or the fact that 'slot' is assigned both in the for loops iterator and in the body of the loop, and thus failing to detect that slot is updated.
participants (2)
-
Probir Roy -
Valdis Klētnieks