Questions on prio_tree
A message that is not in the archive (sent off-list or not yet received): [email protected]
Hi Rajesh,
I've been reading through your recently posted prio tree code. There are a couple of things in the code that I do not understand, and I am concerned that they may be bugs or omissions. Hopefully, you'll be just able to clarify the code for me. :-)
1 - Why does prio_tree_expand use the max_heap_index to determine the height of the radix tree? The bits of the radix_index is only ever used (never the bits in the heap_index), so shouldn't max_radix_index be used? I understand that using the max_heap_index isn't necessary broken (it is guaranteed to be greater than or equal to the max_radix_index), but it seems inefficient. As an example, consider the case where 100 vmas are created all starting at address 0 and ending at addresses 0 through 100. The current code will force the address part of the tree to a height of 7, but since there is only one start address (0) the tree really could have a height of just 1.
2 - When traversing the tree, after the first root->index_bits levels of the tree have been walked, the code starts inspecting the "size" portion of the radix key. Why does the code set the start bit for the size portion to root->index_bits? Shouldn't the code set the start bit to (BITS_PER_LONG - PAGE_SHIFT)?
Consider the case where 100 vmas are created all starting at address 0 and ending at addresses 0 through 100, followed by the creation of a vma from address 100,000 - 100,001. After the first 100 vmas, the tree will have a height of 7 (reasons sited above) for the start address and an additional height of 7 for the size portion of the index. This will cause the tree to have 7 records in the start_address portion of the tree, and the remaining 93 will be distributed pretty evenly in the size portion of the radix tree that hangs off the zero address. When the 101st vma is added, the start address portion of the tree will be expanded to a height of 17. The current code will expand the tree to contain 17 records in the size portion of the radix tree and leave the remaining 84 records in the size portion of the tree hanging off the zero address.
The problem, as I see it, is that new inserts into the tree that start at address zero will not be inspecting the same bits that were used when the first 100 were inserted. (When the first 100 were inserted, bits 1-7 were used to branch in the size portion of the tree, but inserts 102 and on will use bits 1-17.) I don't think this can cause a "crash", but I think it skews the tree ordering and could disturb the O(log n + m) behavior of the algorithm.
Did I miss something?
-Kevin
Signature · 4 lines
--------------------------------------------------------------------- | Kevin O'Connor "BTW, IMHO we need a FAQ for | | [email protected] 'IMHO', 'FAQ', 'BTW', etc. !" | ---------------------------------------------------------------------
Hi Kevin,
Thanks for you analysis and comments.
Quoted 3 lines
1 - Why does
prio_tree_expanduse themax_heap_indexto determine the height of the radix tree? The bits of theradix_indexis only ever used (never the bits in theheap_index), so shouldn'tmax_radix_indexbe used?
In some cases heap_index is also used. As you noted below sometimes size = heap_index - radix_index is used for indexing the tree. If you consider radix_index = 0UL, then size == heap_index.
Quoted 7 lines
I understand that using the
max_heap_indexisn't necessary broken (it is guaranteed to be greater than or equal to themax_radix_index), but it seems inefficient. As an example, consider the case where 100 vmas are created all starting at address 0 and ending at addresses 0 through 100. The current code will force the address part of the tree to a height of 7, but since there is only one start address (0) the tree really could have a height of just 1.
Good example. Actually, your example is the exact reason why we use max_heap_index rather than max_radix_index.
It is clear that we cannot store 101 vmas if the height of the tree is just 1. We need at least 7 levels to store 101 vmas. Yes. The first 7 levels of the tree will be skewed because radix_index (all 0) is used for indexing first 7 (root->index_bits) levels. From level 8 to 14 the size (== heap_index because radix_index is always 0) is used for indexing the tree. So from level 8 to 14 it will be a fully packed (dense) radix tree where size (== heap_index) is used as the index.
Yes. This is bit inefficient. But, it provides a clean solution for a corner case where all vmas start from the same pgoff (radix_index) with different end addresses. This is a rare corner case, so we don't have to worry much about the performance here.
Quoted 11 lines
2 - When traversing the tree, after the first
root->index_bitslevels of the tree have been walked, the code starts inspecting the "size" portion of the radix key. Why does the code set the start bit for the size portion toroot->index_bits? Shouldn't the code set the start bit to (BITS_PER_LONG-PAGE_SHIFT)?Consider the case where 100 vmas are created all starting at address 0 and ending at addresses 0 through 100, followed by the creation of a vma from address 100,000 - 100,001. After the first 100 vmas, the tree will have a height of 7 (reasons sited above) for the start address and an additional height of 7 for the size portion of the index.
Yeah.
Quoted 4 lines
This will cause the tree to
have 7 records in thestart_addressportion of the tree, and the remaining 93 will be distributed pretty evenly in the size portion of the radix tree that hangs off the zero address.
Agreed.
Quoted 3 lines
When the 101st vma is added, the start
address portion of the tree will be expanded to a height of 17. The current code will expand the tree to contain 17 records in the size portion
^^^^
I think it is typo: 17 records in the start_address portion
Quoted 2 lines
of the radix tree and leave the remaining 84 records in the size portion of the tree hanging off the zero address.
Right.
Quoted 5 lines
The problem, as I see it, is that new inserts into the tree that start at address zero will not be inspecting the same bits that were used when the first 100 were inserted. (When the first 100 were inserted, bits 1-7 were used to branch in the size portion of the tree, but inserts 102 and on will use bits 1-17.)
Thanks for your analysis. This is the reason why the expand algorithm is O((log n)^2) algorithm.
Check the prio_tree_remove in prio_tree_expand. If the tree is expanded more than 1 index_bit, then we start removing nodes from the current tree and form a new skewed tree.
In your example, the index_bits changes from 7 to 17. So, (17 - 7) - 1 = 9 nodes will be removed from the current tree before adding the 101st vma. So, at the end of the removal of 9 nodes from the current tree, there are 91 vmas (7 in the skewed start_address portion and the remaining 84 in the size portion that hangs of the radix_index zero). Now, the 9 removed vmas and the newly added vma forms a skewed tree of height 10. The current tree with 91 vmas is appened at the end of this 10 vma skewed tree forming a 17 vma skewed tree in the start_address portion and 84 vma dense tree in the size portion.
Quoted 3 lines
I don't think this can cause a "crash", but I think it
skews the tree ordering and could disturb the O(log n + m) behavior of the algorithm.
Even when the tree is skewed we guarantee O(log n + m). Yeah, we hide the multiplicative constant (2). But then, that is the beauty of big-O notation, right? Hiding the practical performance issues.
The tree gets skewed only in very rare corner cases. So the performance issues should not matter much, IMHO.
Thanks,
Rajesh