Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

like image 274
cppBeginner Avatar asked Jul 09 '17 08:07

cppBeginner


1 Answers

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.

like image 120
Passer By Avatar answered Sep 23 '22 07:09

Passer By