[PATCH v2 39/40] drm: Improve drm_mm search (and fix topdown allocation) with rbtrees

[Chris Wilson]

On Fri, Dec 16, 2016 at 03:46:18PM +0200, Joonas Lahtinen wrote:
> On pe, 2016-12-16 at 07:47 +0000, Chris Wilson wrote:
> > The drm_mm range manager claimed to support top-down insertion, but it
> > was neither searching for the top-most hole that could fit the
> > allocation request nor fitting the request to the hole correctly.
> > 
> > In order to search the range efficiently, we create a secondary index
> > for the holes using either their size or their address. This index
> > allows us to find the smallest hole or the hole at the bottom or top of
> > the range efficiently, whilst keeping the hole stack to rapidly service
> > evictions.
> > 
> > v2: Search for holes both high and low. Rename flags to mode.
> > 
> > Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
> 
> <SNIP>
> 
> > +static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size)
> > +{
> > +	struct rb_node *best = NULL;
> > +	struct rb_node **link = &mm->holes_size.rb_node;
> > +	while (*link) {
> > +		struct rb_node *rb = *link;
> > +		if (size <= rb_hole_size(rb))
> > +			link = &rb->rb_left, best = rb;
> 
> Missed this split.

You must own shares in a company selling braces! :-p
-Chris

-- 
Chris Wilson, Intel Open Source Technology Centre