Here is a memory layout within a custom allocator :-
^ toward less address
....
Header [size=16 alignment=4 ] ....(1)
some waste space A [size=A (unknown) ]
content [size="SIZE" alignment="ALIGN"] ....(2)
some waste space B [size=B (unknown) ]
Header [size=16 alignment=4 ] ....(3)
....
v toward more address
The exact address of Header
is not known beforehand.
However, I know that :-
every Header address % 4 == 0 from (1,3)
"content"%ALIGN == 0 from (2)
How to determine minimum amount of byte for A+content+B
that make everything (1&2&3) always align appropriately?
I need the result of the function (A+content+B
) as a parameter to query a memory block from the custom heap allocator.
//return maximum size of A+content+B that make the allocation always safe
int wasteA_content_wasteB(int SIZE,int ALIGN){
//???
}
If I approach the problem in a more Mathematic-way :-
Header start at K1*4
some waste space A
content start at K2*ALIGN
some waste space B
Header start at K3*4
//K1 and K2 and K3 are unknown positive integer
I will get an inequality system :-
K1*4 + 16 <= K2*ALIGN
K2*ALIGN+SIZE <= K3*4
However, with my limited Math background, I don't know how to solve it.
The main difficulty is that I don't know K1
in advance.
I will know K1
only after I get that block of memory. :(
Therefore, the result of function may be a little sub-optimal (for safety at the worst-case), but I think it is acceptable.
If I am very desperate, I can :-
ceil((SIZE+max(4,ALIGN)-1)/ALIGN)*ALIGN
SIZE
and ALIGN
) or calculate every case beforehand then cache it inside a text file.But it is disgraceful ... I believe there is an explicit formula for this problem. (no?)
I would like an answer that shows concept & idea (show how to think).
Code is not required, but I don't mind.
3 years later, Passer By's answer is still useful for me. So, I will paste my interpretation here :-
Let us first assume ALIGN
is a power of 2.
There are two cases, one is ALIGN <= 4
and other is ALIGN > 4
.
If ALIGN <= 4
, then content
is always aligned with A == 0
if Header
is. All that is left is to pad B
until the next header is at alignment == 4
. So, A + content + B == ceil(content/4)*4
.
If ALIGN > 4
, we would need to find consecutive bytes where content
can fit in there with alignment of ALIGN
.
In the worst case, Header
can be located at position k*ALIGN - 12
, and hence A
would start at k*ALIGN + 4
. To find an alignment of ALIGN
, you would need A == ALIGN - 4
, so A + content == ALIGN + content - 4
.
What is left is to pad for the next Header
. B
starts at k'*ALIGN + content
and hence we would require B == 4 - (content%4)
since we assumed ALIGN
is a power of 2 greater than 4. Thus A + content + B == ALIGN + content + (content%4)
or ALIGN + ceil(content/4)*4
.
Note that in this solution, the position of content
is not static relative to Header
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With