[PATCH 33/34] drm: Fix drm_mm search and insertion

[Joonas Lahtinen]

On ma, 2016-12-12 at 11:53 +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.
> 
> Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>

<SNIP>

> +static void rm_hole(struct drm_mm_node *node)
> +{
> +	if (!node->hole_size)
> +		return;

I've actively tried to remove conditions that cause asymmetry between
add_/rm_, create_/destroy_ etc. So I think this should be
DRM_MM_BUG_ON() too.

> +static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size)
>  {
> -	struct drm_mm *mm = hole_node->mm;
> -	u64 hole_start = drm_mm_hole_node_start(hole_node);
> -	u64 hole_end = drm_mm_hole_node_end(hole_node);
> -	u64 adj_start = hole_start;
> -	u64 adj_end = hole_end;
> +	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;

Single assignment per line, by coding style. And
link = &(best = rb)->rb_left is not better :P

> -int drm_mm_insert_node_in_range_generic(struct drm_mm *mm, struct drm_mm_node *node,
> +int drm_mm_insert_node_in_range_generic(struct drm_mm * const mm,
> +					struct drm_mm_node * const node,

I really have no stance on the const's, I'll defer to higher powers on
this.

> +void drm_mm_remove_node(struct drm_mm_node *node)
>  {

<SNIP>

> -	return best;
> +	rm_hole(prev_node);
> +	add_hole(prev_node);

update_hole?
 
> @@ -799,7 +706,7 @@ bool drm_mm_scan_add_block(struct drm_mm_scan *scan,
>  	if (adj_end <= adj_start || adj_end - adj_start < scan->size)
>  		return false;
>  
> -	if (scan->flags == DRM_MM_CREATE_TOP)
> +	if (scan->flags == DRM_MM_INSERT_HIGH)

Flags are usually checked with & if somebody wants to add them later.
Otherwise you could call it "mode".

Somebody else could give this a glance too.

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