minimize byte wasted to align data between 2 headers (custom allocator)

Viewed 175

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)

Question

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){
    //???
}

My progress

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.

My current workarounds

If I am very desperate, I can :-

  1. query a lot more than need e.g. return ceil((SIZE+max(4,ALIGN)-1)/ALIGN)*ALIGN
  2. brute force every possible combination (e.g. loop by 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 :-

enter image description here enter image description here

1 Answers
Related