[PATCH v2 2/8] drm: improve drm_buddy_alloc function

[Arunpravin]

Hi Matthew,
I am preparing version3 of the buddy allocator,
Please find the updated comments.

SNIP

>>> -int drm_buddy_alloc_range(struct drm_buddy_mm *mm,
>>> -			  struct list_head *blocks,
>>> -			  u64 start, u64 size)
>>> +static struct drm_buddy_block *
>>> +alloc_range(struct drm_buddy_mm *mm,
>>> +	    u64 start, u64 end,
>>> +	    unsigned int order)
>>>   {
>>>   	struct drm_buddy_block *block;
>>>   	struct drm_buddy_block *buddy;
>>> -	LIST_HEAD(allocated);
>>>   	LIST_HEAD(dfs);
>>> -	u64 end;
>>>   	int err;
>>>   	int i;
>>>   
>>
>>>   		if (!block)
>>>   			break;
>>>   
>>>   		list_del(&block->tmp_link);
>>>   
>>> +		if (drm_buddy_block_order(block) < order)
>>> +			continue;
>>> +
>>>   		block_start = drm_buddy_block_offset(block);
>>>   		block_end = block_start + drm_buddy_block_size(mm, block) - 1;
>>>   
>>>   		if (!overlaps(start, end, block_start, block_end))
>>>   			continue;
>>>   
>>> -		if (drm_buddy_block_is_allocated(block)) {
>>> -			err = -ENOSPC;
>>> -			goto err_free;
>>> -		}
>>> +		if (drm_buddy_block_is_allocated(block))
>>> +			continue;
>>>   
>>> -		if (contains(start, end, block_start, block_end)) {
>>> -			if (!drm_buddy_block_is_free(block)) {
>>> -				err = -ENOSPC;
>>> -				goto err_free;
>>> -			}
>>> +		if (contains(start, end, block_start, block_end)
>>> +				&& order == drm_buddy_block_order(block)) {
>>
>> Alignment looks off, also && should be on the line above.
> 
> [Arun] ok
>>
>>> +			/*
>>> +			 * Find the free block within the range.
>>> +			 */
>>> +			if (drm_buddy_block_is_free(block))
>>> +				return block;
>>
>> Would it make sense to keep searching here, rather than restarting the 
>> search from scratch every time? Would it work if we pass in the total 
>> size and min order?
> [Arun] yes, I will rewrite this function

I tried to rewrite the function, AFAIK, in case of end bias allocation,
we have to restart the search on every new order computed value from the
requested total size since we have to find a free node in the required
order level traversing from left to right, here continuing the search
for the subsequent order value would skip the free nodes present in the
beginning of the tree.

In case of actual range allocation, as handled at
i915_buddy_alloc_range, we can continue the search from where the
previous allocation happened since we allocate all the blocks
progressively within the start and end address values.

alloc_range() handles both the cases, having a penalty of restarting the
search in case of actual range allocation. Please let me know if any
suggestions?

>>> +int drm_buddy_alloc(struct drm_buddy_mm *mm,
>>> +		    u64 start, u64 end, u64 size,
>>> +		    u64 min_page_size,
>>> +		    struct list_head *blocks,
>>> +		    unsigned long flags)
>>
>> Do we need to validate the flags somewhere?
> [Arun] I will move 'unsigned long flags' to enum type declaration
I tried to move 'unsigned long flags' to enum type declaration, it
creates an ambiguity in i915 driver as both DRM_BUDDY_ALLOC_TOPDOWN and
DRM_BUDDY_ALLOC_RANGE are mutually non-exclusive. So I think its better
to have 'unsigned long flags'.

AFAIK, we don't need to validate the flags since we check flags using
'flags & DRM_BUDDY_RANGE_ALLOCATION'

>>
>>> +		BUG_ON(order > mm->max_order);
>>> +		BUG_ON(order < min_order);
>>> +
>>> +		do {
>>> +			if (flags & DRM_BUDDY_RANGE_ALLOCATION)
>>> +				/* Allocate traversing within the range */
>>> +				block = alloc_range(mm, start, end, order);
>>
>> Ok, so blocks might be in a random order, which is a slight concern for 
>> actual range allocations(not the bias thing). Can we somehow make 
>> alloc_range just do the old behaviour when end - start == size? Not the 
>> end of the world though if not.
> [Arun] I will change the alloc_range() block allocations to bottom-up,
> so both actual range allocation and end bias allocation blocks will
> start from lowest address. And, since we are traversing the tree from
> left to right, blocks will be in order.
> 
> And, alloc_range() handles actual range allocation demands the same way
> as in the old i915_buddy_alloc_range() function except alloc_range()
> make use of order value to find the blocks within the actual range
> allocation.

Correction - I will change alloc_range() block allocations to bottom-up,
so actual range allocation blocks will start from lowest address (not
the bias thing), and since we are traversing the tree from left to right
progressively within the required range, blocks will be in order (not
the bias thing)

alloc_range() handles actual range allocation demands the same way as in
the old i915_buddy_alloc_range() function except it restarts the search
(since we are handling both end bias and actual range allocations in the
same function) and make use of order value to find the blocks within
start and end value.

Regards,
Arun