最小化字节浪费以对齐2个头之间的数据(自定义分配器)

Question

这是自定义分配器中的内存布局: -

^ 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

Header事先并不知道确切的地址.
但是,我知道: -

every Header address % 4 == 0      from (1,3)
"content"%ALIGN          == 0      from (2)

题

如何确定最小字节数A+content+B使得所有内容(1和2和3)始终正确对齐？

//return maximum size of A+content+B that make the allocation always safe
int wasteA_content_wasteB(int SIZE,int ALIGN){
    //???
}

我的进步

如果我以更加数学的方式解决问题: -

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

我将得到一个不平等系统: -

K1*4 + 16     <= K2*ALIGN
K2*ALIGN+SIZE <= K3*4

但是,由于我有限的数学背景,我不知道如何解决它.

主要困难是我K1事先不知道,我必须使用function(A+content+B)的结果作为参数从自定义堆分配器查询内存块.

我得到那个记忆K1 后我会知道的. :(

因此,功能的结果可能有点次优(为了最坏情况下的安全性),但我认为这是可以接受的.

我目前的解决方法

如果我非常绝望,我可以: -

1. 查询比需要更多,例如返回 ceil((SIZE+max(4,ALIGN)-1)/ALIGN)*ALIGN
2. 蛮力强制每个可能的组合(例如循环SIZE和ALIGN)或预先计算每个案例然后将其缓存在文本文件中.

但这是可耻的......我相信这个问题有一个明确的公式.(没有？)

我想要一个显示概念和想法的答案(展示如何思考).
代码不是必需的,但我不介意.

Answer 1

让我们首先假设ALIGN是2 的幂。

有两种情况，一种是ALIGN <= 4，另一种是ALIGN > 4。

如果ALIGN <= 4, thencontent总是与A == 0if Headeris 对齐。剩下的就是填充B直到下一个标头位于 处alignment == 4。所以，A + content + B == ceil(content/4)*4。

如果ALIGN > 4，我们需要找到content可以放入其中且对齐的连续字节ALIGN。

在最坏的情况下，Header可以位于位置k*ALIGN - 12，因此A将从 开始k*ALIGN + 4。要找到 的对齐方式ALIGN，您需要A == ALIGN - 4, so A + content == ALIGN + content - 4。

剩下的就是为下一步做准备了Header。B开始于k'*ALIGN + content，因此我们需要B == 4 - (content%4)，因为我们假设ALIGN是大于 4 的 2 的幂。因此A + content + B == ALIGN + content + (content%4)或ALIGN + ceil(content/4)*4。

请注意，在此解决方案中， 的位置相对于 而言content不是静态的Header。