[PATCH 3/8] drm: implement top-down allocation method

[Matthew Auld]

On 25/10/2021 14:00, Arunpravin wrote:
> Implemented a function which walk through the order list,
> compares the offset and returns the maximum offset block,
> this method is unpredictable in obtaining the high range
> address blocks which depends on allocation and deallocation.
> for instance, if driver requests address at a low specific
> range, allocator traverses from the root block and splits
> the larger blocks until it reaches the specific block and
> in the process of splitting, lower orders in the freelist
> are occupied with low range address blocks and for the
> subsequent TOPDOWN memory request we may return the low
> range blocks.To overcome this issue, we may go with the
> below approach.
> 
> The other approach, sorting each order list entries in
> ascending order and compares the last entry of each
> order list in the freelist and return the max block.
> This creates sorting overhead on every drm_buddy_free()
> request and split up of larger blocks for a single page
> request.
> 
> Signed-off-by: Arunpravin <Arunpravin.PaneerSelvam at amd.com>
> ---
>   drivers/gpu/drm/drm_buddy.c | 42 +++++++++++++++++++++++++++++++------
>   include/drm/drm_buddy.h     |  1 +
>   2 files changed, 37 insertions(+), 6 deletions(-)
> 
> diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
> index 406e3d521903..9d3547bcc5da 100644
> --- a/drivers/gpu/drm/drm_buddy.c
> +++ b/drivers/gpu/drm/drm_buddy.c
> @@ -362,6 +362,27 @@ alloc_range(struct drm_buddy_mm *mm,
>   	return ERR_PTR(err);
>   }
>   
> +static struct drm_buddy_block *
> +get_maxblock(struct list_head *head)
> +{
> +	struct drm_buddy_block *max_block = NULL, *node;
> +
> +	max_block = list_first_entry_or_null(head,
> +					     struct drm_buddy_block,
> +					     link);
> +
> +	if (!max_block)
> +		return NULL;
> +
> +	list_for_each_entry(node, head, link) {
> +		if (drm_buddy_block_offset(node) >
> +				drm_buddy_block_offset(max_block))

Alignment.

> +			max_block = node;
> +	}

I suppose there will be pathological cases where this will unnecessarily 
steal the mappable portion? But in practice maybe this is good enough?

> +
> +	return max_block;
> +}
> +
>   static struct drm_buddy_block *
>   alloc_from_freelist(struct drm_buddy_mm *mm,
>   		    unsigned int order,
> @@ -372,13 +393,22 @@ alloc_from_freelist(struct drm_buddy_mm *mm,
>   	int err;
>   
>   	for (i = order; i <= mm->max_order; ++i) {
> -		if (!list_empty(&mm->free_list[i])) {
> -			block = list_first_entry_or_null(&mm->free_list[i],
> -							 struct drm_buddy_block,
> -							 link);
> +		if (flags & DRM_BUDDY_TOPDOWN_ALLOCATION) {
> +			if (!list_empty(&mm->free_list[i])) {

AFAIK no need to keep checking list_empty(), below also.

> +				block = get_maxblock(&mm->free_list[i]);
>   
> -			if (block)
> -				break;
> +				if (block)
> +					break;
> +			}
> +		} else {
> +			if (!list_empty(&mm->free_list[i])) {
> +				block = list_first_entry_or_null(&mm->free_list[i],
> +								 struct drm_buddy_block,
> +								 link);
> +
> +				if (block)
> +					break;
> +			}
>   		}
>   	}
>   
> diff --git a/include/drm/drm_buddy.h b/include/drm/drm_buddy.h
> index c7bb5509a7ad..cd8021d2d6e7 100644
> --- a/include/drm/drm_buddy.h
> +++ b/include/drm/drm_buddy.h
> @@ -28,6 +28,7 @@
>   })
>   
>   #define DRM_BUDDY_RANGE_ALLOCATION (1 << 0)
> +#define DRM_BUDDY_TOPDOWN_ALLOCATION (1 << 1)
>   
>   struct drm_buddy_block {
>   #define DRM_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)
>