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

[Daniel Vetter]

On Fri, Oct 16, 2015 at 08:54:20AM +0000, Daniel, Thomas wrote:
> Hi,
> 
> > -----Original Message-----
> > From: Intel-gfx [mailto:intel-gfx-bounces at lists.freedesktop.org] On Behalf Of
> > David Herrmann
> > Sent: Wednesday, October 7, 2015 11:23 AM
> > To: Chris Wilson; Daniel Vetter; Intel Graphics Development; dri-
> > devel at lists.freedesktop.org
> > Subject: Re: [Intel-gfx] [PATCH 1/3] drm: Track drm_mm nodes with an interval
> > tree
> > 
> > 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
> 
> Is there a conclusion to this discussion?  I'm under increasing pressure to get the i915 soft-pinning merged and Chris's latest version depends on this interval tree.
> 
> I've been told to post a new rebase of the version which doesn't use the interval tree if not.

In my opiniong pushing the interval tree into drm_mm.c makes tons of
sense, so that we don't have to duplicate this between i915 and the vma
manager.
-Daniel
-- 
Daniel Vetter
Software Engineer, Intel Corporation
http://blog.ffwll.ch