On Thu, Oct 08, 2020 at 07:13:51PM +0200, Jann Horn wrote: > You may want to consider whether it would be better to store > information about free memory per subtree in the VMA tree, together > with the maximum gap size that is already stored in each node, and > then walk down the tree randomly, with the randomness weighted by free > memory in the subtrees, but ignoring subtrees whose gaps are too > small.
Please, no. We're trying to get rid of the rbtree, not enhance it further. The new data structure is a B-tree and we'd rather not burden it with extra per-node information (... although if we have to, we could) > And for expanding stacks, it might be a good idea for other > reasons as well (locking consistency) to refactor them such that the > size in the VMA tree corresponds to the maximum expansion of the stack > (and if an allocation is about to fail, shrink such stack mappings). We're doing that as part of the B-tree ;-) Although not the shrink stack mappings part ...
