[Intel-gfx] [PATCH 1/3] drm: Track drm_mm nodes with an interval tree

[David Herrmann]

Hi

On Tue, Oct 6, 2015 at 1:19 PM, Chris Wilson <chris at chris-wilson.co.uk> wrote:
> On Tue, Oct 06, 2015 at 01:11:56PM +0200, Daniel Vetter wrote:
>> On Tue, Oct 06, 2015 at 11:53:09AM +0100, Chris Wilson wrote:
>> > In addition to the last-in/first-out stack for accessing drm_mm nodes,
>> > we occasionally and in the future often want to find a drm_mm_node by an
>> > address. To do so efficiently we need to track the nodes in an interval
>> > tree - lookups for a particular address will then be O(lg(N)), where N
>> > is the number of nodes in the range manager as opposed to O(N).
>> > Insertion however gains an extra O(lg(N)) step for all nodes
>> > irrespective of whether the interval tree is in use. For future i915
>> > patches, eliminating the linear walk is a significant improvement.
>> >
>> > Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
>> > Cc: dri-devel at lists.freedesktop.org
>>
>> For the vma manager David Herrman put the interval tree outside of drm_mm.
>> Whichever way we pick, but I think we should be consistent about this.
>
> Given that the basis of this patch is that functionality exposed by
> drm_mm (i.e. drm_mm_reserve_node) is too slow for our use case (i.e.
> there is a measurable perf degradation if we switch over from the mru
> stack to using fixed addresses) it makes sense to improve that
> functionality. The question is then why the drm_vma_manager didn't use
> and improve the existing functionality...

I didn't want to slow down drm_mm operations, so I kept it separate. I
don't mind if it is merged into drm_mm. It'd be trivial to make the
vma-manager use it (only on the top-level, though).

Thanks
David