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