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.