Re: [PATCH 1/2] [RFC] Range tree implementation

[John Stultz <john.stultz@linaro.org>]

On 04/07/2012 10:36 AM, Sasha Levin wrote:
> On Sat, Apr 7, 2012 at 2:08 AM, John Stultz<john.stultz@linaro.org>  wrote:
>> After Andrew suggested something like his mumbletree idea
>> to better store a list of ranges, I worked on a few different
>> approaches, and this is what I've finally managed to get working.
>>
>> I suspect range-tree isn't a totally accurate name, but I
>> couldn't quite make out the difference between range trees
>> and interval trees, so I just picked one to call it. Do
>> let me know if you have a better name.
>>
>> The idea of storing ranges in a tree is nice, but has a number
>> of complications. When adding a range, its possible that a
>> large range will consume and merge a number of smaller ranges.
>> When removing a range, its possible you may end up splitting an
>> existing range, causing one range to become two. This makes it
>> very difficult to provide generic list_head like behavior, as
>> the parent structures would need to be duplicated and removed,
>> and that has lots of memory ownership issues.
>>
>> So, this is a much simplified and more list_head like
>> implementation. You can add a node to a tree, or remove a node
>> to a tree, but the generic implementation doesn't do the
>> merging or splitting for you. But it does provide helpers to
>> find overlapping and adjacent ranges.
>>
>> Andrew also really wanted this range-tree implementation to be
>> resuable so we don't duplicate the file locking logic. I'm not
>> totally convinced that the requirements between the volatile
>> ranges and file locking are really equivelent, but this reduced
>> impelementation may make it possible.
>>
>> Do let me know what you think or if you have other ideas for
>> better ways to do the same.
> Hi John,
>
> I have implemented an interval lookup tree using the augmented
> features of the in-kernel rbtree for the KVM tools project. We
> currently use it for several things as a framework code such as MMIO
> memory mapping.
>
>  From what I see in the patch, you haven't fully implemented the
> interval structure (it needs to keep track of additional parameters
> when building it, and the search is a bit different and is based on
> those parameters).
Any more details on whats missing/different? Or the pros/cons of the 
different approaches?

> I could send that code as a patch against the kernel tree if something
> like that is actually required for the kernel at this point.
>
Sure.  I'm not married to this implementation (its just the only one so 
far that solves my needs - Dmitry already pointed out that the priotree 
might be close to sufficient, but I've not yet tried to adapt it), and 
whatever goes upstream needs to be generic enough to solve the related 
problems that a number of folks are all working on solving.  So seeing 
your approach might be good too.

thanks
-john