[PROJECT] Is combining allocation and lookup a good idea?

[Peng Zhang]

在 2023/11/15 01:57, Matthew Wilcox 写道:
> The rbtree combined allocation and lookup.  We followed that lead with
> the maple tree and have "allocating nodes" which contain 10 slots. 10
> gaps and 9 pivots.  Now I'm wondering if we made the right decision.
> 
> If we split "find a free range of address space" into a separate data
> structure, we get 16 slots and 15 pivots.  Assuming that a tree node
> is 70% full, an allocating tree can store 7 * 7 * 11 = 539 VMAs in a
> height-3 tree.  If we have a tree of regular nodes, we can store 1331
> in a height-3 tree -- over twice as many!
I have thought about this before. I have a question: do we really need
to store the gap of each subtree in non-leaf nodes? Perhaps we don't need
this gap information in non-leaf nodes. Instead, we can simply store the
maximum gap in the metadata, and when we need the specific maximum gap of
a particular subtree, we can enter that child node and retrieve its metadata.
I'm not sure if I'm missing something.
> 
> We should definitely be optimising for lookup, not allocation, so keeping
> the allocation information in the tree alongside the lookup information
> is probably a really bad idea.  I have lots of bad ideas.
> 
> We'd obviously want to keep the two data structures under the same lock,
> but they needn't both be a maple tree.  There are definitely downsides
> to the current scheme; for example , if you mmap() all of memory, then
> munmap() alternate 64MB chunks, mmap() specifying a size of 64M and
> alignment of 64M will not find any of the open spaces because we look
> for a 128MB gap so that we can guarantee alignment.
I have an idea: perhaps the gap in the maple tree could be represented
by a 64-bit bitmap, where each bit indicates the power of 2 that the
subtree can allocate as a range. This can address the issue you mentioned.
When I started working a year ago, I implemented a version of IOVA
allocation using a red-black tree, as referenced in patch [1]. It addressed
the address alignment issue. Unfortunately, it didn't receive support from
the IOVA maintainer, but I believe it was a good solution for addressing
address alignment.

[1] https://lore.kernel.org/lkml/20220818121703.20977-1-zhangpeng.00@bytedance.com/
> 
> I suspect the obvious first place to start is a second maple tree
> which contains (start, length) descriptions of the gaps, but honestly
> designing the right data structure for this could be a project in itself.
> Just separating the allocation from the lookup is a big enough project,
> I think.
>