Conversation
@ljs I'd need a generic structure that gets built up from intervals, potentially overlapping. after that enumerate the intervals. the tricky part is the merging, I had similar sketches for the cases as you on the whiteboard for my (unfinished) prototype. the maple tree has a single value key, so the merging is still left as an exercise. The linux.git/include/interval_tree.h is close but IIRC not doing what I wanted.
1
0
0
@kdave it's not a property of the data structure in the kernel but rather a separate mechanism triggered before an operation which adds a new VMA or modifies an existing one.
The maple tree is the data structure used for all VMA operations so it's not so much an exercise but rather just implemented elsewhere.
I refactored the vma merge mechanism into two cases - existing VMAs being modified - https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/mm/vma.c#n659
And a new VMA being inserted - https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/mm/vma.c#n911
The power of the maple tree is precisely in representing ranges (and being able to find gaps) in a way that's cache-friendly.
The maple tree is the data structure used for all VMA operations so it's not so much an exercise but rather just implemented elsewhere.
I refactored the vma merge mechanism into two cases - existing VMAs being modified - https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/mm/vma.c#n659
And a new VMA being inserted - https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/mm/vma.c#n911
The power of the maple tree is precisely in representing ranges (and being able to find gaps) in a way that's cache-friendly.
2
0
0
@kdave Something generic though would probably want to put some of this logic explicitly in the library itself obviously, but then depending on how custom the 'are these the same?' criteria you have are you would need hooks etc.
You could implement something that wraps the maple tree also...
You could implement something that wraps the maple tree also...
0
0
0
@ljs I've implemented all that in user space for https://github.com/enarx/enarx :-) It perfectly highlights the SGX issue (which might be unsolvable by kernel). Easy to recall because I draw almost the same picture to my notebook when I did it: https://github.com/enarx/mmledger/blob/main/src/lib.rs
Not proud of it all., On the contrary this exactly the code that I'd like to see some day deleted. Since SGX is the lowest common denominator we also need to use it with AMD SNP, Intel TDX and ARM CCA if gets ever supported. Not sure if it is possible but would be nice to delegate merging of VMAs back to the kernel (which is not possible as of today).
I'm sure whatever merge code is kernel is factors more mature and better but this is unfortunately as of today only piece of code that works :-)
Not proud of it all., On the contrary this exactly the code that I'd like to see some day deleted. Since SGX is the lowest common denominator we also need to use it with AMD SNP, Intel TDX and ARM CCA if gets ever supported. Not sure if it is possible but would be nice to delegate merging of VMAs back to the kernel (which is not possible as of today).
I'm sure whatever merge code is kernel is factors more mature and better but this is unfortunately as of today only piece of code that works :-)
0
0
0
@ljs Thanks for the pointers, by a quick look this is what I'd need, but yes it's vma-specific. I'm namely interested in the logic, that can be copied and adapted for data structure I need it for. We have range trees for extent state tracking but it's a bit heavy for the purpose. A generic way would be better so I can rely on tested code (the same way I don't want to reimplement rb-tree balancing). Alternatively, implementing that on a linked list is maybe the easiest way with obvious performance limitations (with bonus of iterator friendly changes to the whole data structure), but I can start writing the actual thing built on the range trees.
0
0
1