最小化字节浪费以对齐 2 headers 之间的数据（自定义分配器）

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) 始终正确对齐的最小字节数？

我需要函数 (A+content+B) 的结果作为参数来从自定义堆分配器查询内存块。

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

我的进步

如果我更深入地处理问题 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

我会得到一个不等式系统:-

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

但是，以我有限的数学背景，我不知道如何解决它。

主要难点是事先不知道K1

我会知道 K1 只有在 我得到那块内存之后。 :(

因此，函数的结果可能会有点sub-optimal（为了安全在worst-case），但我认为是可以接受的。

我目前的解决方法

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

查询比需要的多得多，例如returnceil((SIZE+max(4,ALIGN)-1)/ALIGN)*ALIGN
暴力破解每个可能的组合（例如通过 SIZE 和 ALIGN 循环）或预先计算每个案例然后将其缓存在文本文件中。

但这是可耻的......我相信这个问题有一个明确的公式。（不是吗？）

我想要一个展示概念和想法（展示如何思考）的答案。
代码不是必需的，但我不介意。

3年后，路人的回答对我还是有用的。所以，我将在这里粘贴我的解释：-

Answer 1

让我们首先假设 ALIGN 是 power of 2。

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

如果 ALIGN <= 4，则 content 总是与 A == 0 对齐，如果 Header 是。剩下的就是填充 B，直到下一个 header 位于 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，因此 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 是 而不是 静态的。

最小化字节浪费以对齐 2 headers 之间的数据（自定义分配器）

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

c++

math

memory-alignment

allocator

问题

我的进步

我目前的解决方法