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

[Joonas Lahtinen]

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.

With that addressed, this is;

Reviewed-by: Joonas Lahtinen <joonas.lahtinen at linux.intel.com>

Regards, Joonas
-- 
Joonas Lahtinen
Open Source Technology Center
Intel Corporation