On 30.04.2012 17:45, Jerome Glisse wrote:
On Mon, Apr 30, 2012 at 10:50 AM, Christian König deathsimple@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önigdeathsimple@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.