Li-Ta Lo ollie@lanl.gov writes:
On Mon, 2004-03-01 at 14:06, Eric W. Biederman wrote:
There are many was to assign resources on a bus. After some experiences with tight memory situations I implemented a near optimal solution. The solution is optimal if all of your resources are a power of 2 in size.
Basically the code is a loop. For each iteration the code finds the largest unassigned resource. Then the resource constraints of that resource are considered and padding between the previous resources and the current resources are inserted if necessary. Then we get into the next iteration.
I still don't understand this. Do you mean that now the resource allocation is not sequential (in the order of devices been enumerated) and not continuous (there are gaps in allocated address) ?
Correct.
The reason the allocation is not sequential (in the order of devices been enumerated) is to reduce the number of gaps in the allocated addresses.
So a thought problem to help put this in perspective.
First all resources are a power of 2 in size must be that same power of 2 aligned.
So if I have 3 resources A,B,C with the following sizes:
A: 8K B: 256M C: 4K
Allocating them sequentially would use 756M of address space. After allocating A you need nearly 256M of padding to get B 256M aligned. C takes nearly 256M due to padding.
Allocating them largest to smallest (B,A,C) uses just 512M of address space. Because the alignment necessary for A is present at the end of B, and the alignment necessary for A is present at the end of C.
Eric
The reason this is optimal if all of your resources are a power of two in size is because if your previous resource is a larger or equal power of two no padding will be needed for the current resource.