[PATCH 09/26] drm/radeon: add biggest hole tracking and wakequeue to the sa v3

[Christian König]

On 30.04.2012 17:45, Jerome Glisse wrote:
> On Mon, Apr 30, 2012 at 10:50 AM, Christian König
> <deathsimple at vodafone.de>  wrote:
>> With that in place clients are automatically blocking
>> until their memory request can be handled.
>>
>> v2: block only if the memory request can't be satisfied
>>     in the first try, the first version actually lacked
>>     a night of sleep.
>>
>> v3: make blocking optional, update comments and fix
>>     another bug with biggest hole tracking.
>>
>> Signed-off-by: Christian König<deathsimple at vodafone.de>
> I would say NAK, the idea of SA allocator is to be like ring buffer, a
> ring allocation. All the allocation made through SA are made for
> object that life are ring related, ie once allocated the object is
> scheduled through one of the ring and once the ring is done consuming
> it the object is free. So the idea behind the SA allocator is to make
> it simple we keep track of the highest offset used and the lowest one
> free, we try to find room above the highest and if we don't have
> enough room we try at the begining of the ring (wrap over), idea is
> that in most scenario we don't have to wait because SA is big enough
> and if we have to wait well it's because GPU is full of things to do
> so waiting a bit won't starve the GPU.
Take a closer look, that's exactly what the new code intends to do.

The biggest_hole is tracking the bottom of the ring allocation algorithm:

In (roughly estimated) 97% of all cases it is pointing after the last 
allocation, so new allocations can be directly served.

In 1% of the cases it is pointing to a free block at the end of the 
buffer that isn't big enough to serve the next allocation, in that case 
we just need to make one step to the beginning of the buffer and 
(assuming that allocations are ring like) there should be enough space 
gathered to serve the allocation.

In 1% of the cases a left over allocation will prevent a new 
biggest_hole to gather together at the beginning of the buffer, but that 
is actually unproblematic, cause all that needs to be done is stepping 
over that unreleased chunk of memory.

And well every algorithm has a worst case and here it happens when there 
isn't enough room to server the allocation, in this case we need to do a 
full cycle around all allocations and then optionally wait for the 
biggest_hole to increase in size.

> That being said current code doesn't exactly reflect that, i can't
> remember why. Anyway i would rather make current looks like intented
> as i believe it make allocation easy and fast in usual case. There is
> also a reason why i intended to have several sa manager. Idea is to
> have one SA manager for the VM (because VM might last longer) and one
> for all the ring object (semaphore, ib, ...) because usual case is
> that all ring sync from time to time and the all progress in //.
Yeah, even with your good intentions the current code just turned out to 
be a linear search over all the allocations and that seemed to be not so 
efficient. Also making the code look like it should from the comments 
description was also part of my intentions.

Anyway, I think it's definitely an improvement, but there obviously is 
also still room for new ideas, e.g. we could track how trustworthy the 
biggest_hole is and then early abort allocations that can never succeed. 
Or we could also keep track of the last allocation and on new 
allocations try once to place them directly behind the last allocation 
first, that would give the whole allocator a even more ring like fashion.

And by the way: Having two allocators, one for VM and another for the 
ring like stuff sounds like the right thing to do, since their 
allocations seems to have different live cycles.

Christian.