On Mon, 2024-11-04 at 15:07 -0800, Matthew Brost wrote: > > We > > have > > https://elixir.bootlin.com/linux/v6.12-rc6/source/include/linux/int > > erval_tree_generic.h#L24 > > > > to relate to. Now GPUVM can't use the generic version since it > > needs > > u64 intervals. These trees need unsigned long only so it should be > > ok. > > And safe removal, isn't that possible to implement without the > > list? > > Then it's really only the linked list as a perf optimization I > > guess, > > but we have a lot of those pending... > > > > See my other comments. Let me just follow on using a maple tree and > perhaps a > list isn't required if we use that. Will have definite answer in my > next rev. Note, though, that IIRC maple trees do not allow overlapping ranges, and If we need to support multiple svm VMAs with different offsets, like Christian suggests, we will likely have overlapping ranges for the range tree but not for the notifier tree. Thinking a bit more about this, my concern is mostly around needlessly instantiating new interval trees instead of using the generic instantiation, because that is clearly against recommended practice. But the list could probably be added anyway if needed, and it does indeed AFAICT reduce the traversal complexity from O(N ln N) to O(N). /Thomas
