Replace critnib with a RAVL tree to track allocations in providers

[lplewa]

This is a rough idea - I'm not 100% sure that this solution will not have any disadvantages.

Currently, on every split or merge, we add and remove entries from critnib structures to track allocations at various levels. This proposal suggests replacing those structures with a RAVL tree instead.

A key advantage of using a RAVL tree is the ability to search for a key that is equal to or lower than a specified value. After a split, this feature allows reusing the original entry in the tree, eliminating the need to update it. As a result, overall performance is improved by reducing the overhead of frequent insertions and deletions. In addition, a RAVL tree will be smaller, which further enhances search times.

[igchor]

I believe that currently, we do update + insert in the split and only update in merge (see https://github.com/oneapi-src/unified-memory-framework/blob/main/src/provider/provider_tracking.c#L318C30-L318C66). How would using RAVL improve this?

Critnib also allows you to search for key that is equal or lower: https://github.com/oneapi-src/unified-memory-framework/blob/main/src/critnib/critnib.h#L36

Also, I'm not sure if RAVL would be smaller - it's a binary tree and critnib has a branching factor of 16 (although the number of level for critnib will depend on how similar are the keys).

[lplewa]

The idea is that we do not do any inserts on split. We do not need two separates entries in tracker after split. Only in case of free we remove entry in tree, and optionally add a new one(s), if needed.

We have to assume that user provides "correct" ptrs, and if it doesn't it is undefined behavior. But this assumption should be "fine".

[igchor]

I see, so you suggest to do nothing on split/merge, and only remove (potentially partial) range on free? One potential problem would be that the information we report to the user through #686 (once/when we implement it) is not exactly correct. I don't know if that's a problem for any providers that we have right now though. I don't think there is any observable difference from the user perspective.

Regarding RAVL vs critnib - I still don't see a clear advantage of RAVL, as I mentioned critnib also support searching for LE keys.

[vinser52]

The idea is that we do not do any inserts on split. We do not need two separates entries in tracker after split. Only in case of free we remove entry in tree, and optionally add a new one(s), if needed.

It is error-prone. For example, IPC functionality might be impacted. Memory tracker should contain "true" information. If there are two memory blocks after split tracker should be able to tell that.

[vinser52]

A key advantage of using a RAVL tree is the ability to search for a key that is equal to or lower than a specified value.

I thought the critnib also supports lower_bound search. Otherwise, umfPoolByPtr wouldn't work.