如何仅使用标准库分配对齐内存?

小开

最佳答案

原来的答案

{
void *mem = malloc(1024+16);
void *ptr = ((char *)mem+16) & ~ 0x0F;
memset_16aligned(ptr, 0, 1024);
free(mem);
}

固定的答案

{
void *mem = malloc(1024+15);
void *ptr = ((uintptr_t)mem+15) & ~ (uintptr_t)0x0F;
memset_16aligned(ptr, 0, 1024);
free(mem);
}

按要求解释

第一步是分配足够的空闲空间，以防万一。由于内存必须是16字节对齐的(这意味着前导字节地址需要是16的倍数)，因此增加16个额外字节可以保证有足够的空间。在前16个字节的某处，有一个16字节的对齐指针。(请注意，malloc()应该返回一个指针，该指针已经足够对准任何的目的。然而，'any'的意思主要是指基本类型——long， double， long double， long long，以及指向对象的指针和指向函数的指针。当你在做更专业的事情时，比如处理图形系统，它们可能比系统的其他部分需要更严格的对齐——因此会出现这样的问题和回答。)

下一步是将void指针转换为char指针;尽管在GCC中，您不应该在void指针上执行指针算术(并且GCC有警告选项，当您滥用它时告诉您)。然后在开始指针上加上16。假设malloc()返回一个极其糟糕的指针:0x800001。加上16得到0x800011。现在我想四舍五入到16字节的边界-所以我想把最后4位重置为0。0x0F将最后4位设置为1;因此，~0x0F的所有位都设置为1，除了最后四位。与0x800011相加得到0x800010。您可以遍历其他偏移量，并查看相同的算法是否有效。

最后一步，free()，很简单:你总是且只返回一个malloc()， calloc()或realloc()返回给你的值给free()——任何其他的都是灾难。你正确地提供了mem来保存该值-谢谢。自由释放它。

最后，如果你知道你的系统的malloc包的内部结构，你可以猜测它很可能返回16字节对齐的数据(或者它可能是8字节对齐的)。如果它是16字节对齐的，那么您就不需要对值进行丁克。然而，这是狡猾的和不可移植的-其他malloc包有不同的最小对齐，因此假设一件事当它做不同的事情会导致核心转储。在广泛的范围内，这个解决方案是可移植的。

还有人提到posix_memalign()是另一种获得对齐内存的方法;并不是所有地方都可以使用它，但通常可以使用它作为基础来实现。注意，对齐是2的幂，这很方便;其他的结盟则更为混乱。

还有一条注释——这段代码不会检查分配是否成功。

修正案

Windows程序员指出你不能对指针做位掩码操作，事实上，GCC(3.4.6和4.3.1测试)确实抱怨这样。因此，一个基本代码的修正版本-转换成一个主程序，如下。我还擅自加了15而不是16，就像已经指出的那样。我使用uintptr_t，因为C99已经存在了足够长的时间，可以在大多数平台上访问。如果不是为了在printf()语句中使用PRIXPTR，那么使用#include <stdint.h>而不是#include <inttypes.h>就足够了。[此代码包括由C.R.指出的修复，这是重申了Bill K几年前提出的观点，直到现在我都忽略了这一点。]

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


static void memset_16aligned(void *space, char byte, size_t nbytes)
{
assert((nbytes & 0x0F) == 0);
assert(((uintptr_t)space & 0x0F) == 0);
memset(space, byte, nbytes);  // Not a custom implementation of memset()
}


int main(void)
{
void *mem = malloc(1024+15);
void *ptr = (void *)(((uintptr_t)mem+15) & ~ (uintptr_t)0x0F);
printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr);
memset_16aligned(ptr, 0, 1024);
free(mem);
return(0);
}

这里是一个稍微一般化的版本，它适用于2的幂的大小:

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


static void memset_16aligned(void *space, char byte, size_t nbytes)
{
assert((nbytes & 0x0F) == 0);
assert(((uintptr_t)space & 0x0F) == 0);
memset(space, byte, nbytes);  // Not a custom implementation of memset()
}


static void test_mask(size_t align)
{
uintptr_t mask = ~(uintptr_t)(align - 1);
void *mem = malloc(1024+align-1);
void *ptr = (void *)(((uintptr_t)mem+align-1) & mask);
assert((align & (align - 1)) == 0);
printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr);
memset_16aligned(ptr, 0, 1024);
free(mem);
}


int main(void)
{
test_mask(16);
test_mask(32);
test_mask(64);
test_mask(128);
return(0);
}

要将test_mask()转换为通用分配函数，分配器的单个返回值必须对发布地址进行编码，正如一些人在他们的回答中所指出的那样。

与面试官的问题

Uri评论:也许我今天早上有阅读理解问题，但如果面试问题明确地说:“你如何分配1024字节的内存”，而你分配的内存显然不止这个数。这难道不是面试官的自动失败吗?

我的回答写不进300字的评论……

我想这要看情况。我想大多数人(包括我)认为这个问题的意思是“你将如何分配一个可以存储1024字节数据的空间，其中基址是16字节的倍数”。如果面试官真正的意思是如何分配1024字节(仅)并将其对齐为16字节，那么选择就更有限了。

显然，一种可能是分配1024字节，然后给该地址'对齐处理';这种方法的问题是，实际可用空间不能正确确定(可用空间在1008和1024字节之间，但没有一种机制可以指定大小)，这使得它没有多大用处。
另一种可能是，您希望编写一个全内存分配器，并确保返回的1024字节块是适当对齐的。如果是这种情况，您最终可能会执行与建议的解决方案相当类似的操作，但您将其隐藏在分配器中。

然而，如果面试官期待这两种回答中的任何一种，我希望他们能意识到这个答案回答了一个密切相关的问题，然后重新组织他们的问题，把谈话引向正确的方向。(此外，如果面试官真的很暴躁，那么我就不会想要这份工作;如果对一个不够精确的要求的回答没有得到纠正就被猛烈抨击，那么这个面试官就不是一个安全的雇主。)

世界在前进

问题的题目最近变了。它是解决C语言面试中困扰我的记忆对齐问题。修改后的标题(如何仅使用标准库分配对齐内存?)需要稍微修改的答案-这个附录提供了它。

C11 (ISO/IEC 9899:2011)添加函数aligned_alloc():

7.22.3.1 aligned_alloc函数

剧情简介
#include <stdlib.h>
void *aligned_alloc(size_t alignment, size_t size);
 描述 aligned_alloc函数的作用是:为对象的对齐方式为由alignment指定，其大小由size指定，其值为不确定的。alignment的值必须是实现支持的有效对齐方式，而size的值必须是alignment的整数倍 返回 aligned_alloc函数返回一个空指针或指向已分配空间的指针

POSIX定义了posix_memalign():

#include <stdlib.h>


int posix_memalign(void **memptr, size_t alignment, size_t size);
描述

posix_memalign()函数将分配size字节，对齐于alignment指定的边界，并将返回指向memptr中已分配内存的指针。alignment的值应该是sizeof(void *)的2倍幂。

成功完成后，memptr所指向的值将是alignment的倍数。

如果请求的空间大小为0，则行为是由实现定义的;memptr返回的值必须是空指针或唯一指针。

free()函数将释放先前由posix_memalign()分配的内存。

返回值

成功完成后，posix_memalign()将返回零;否则，将返回一个错误编号来表示错误。

现在可以使用其中一个或两个函数来回答问题，但在最初回答问题时，只有POSIX函数是一个选项。

在幕后，新的对齐内存函数所做的工作与问题中概述的基本相同，只是它们能够更容易地强制对齐，并在内部跟踪对齐内存的开始，这样代码就不必特别处理—它只是释放使用的分配函数返回的内存。

小开

你也可以尝试posix_memalign()(当然是在POSIX平台上)。

小开

也许他们会满足于memalign的知识?正如乔纳森·莱弗勒(Jonathan Leffler)指出的，有两个更新的更可取的函数需要了解。

哦，弗罗林先我一步。但是，如果您阅读了我链接到的手册页，您很可能会理解前面的帖子提供的示例。

小开

三个稍微不同的答案取决于你如何看待这个问题:

1) Jonathan Leffler的解决方案很好地回答了这个问题，除了要四舍五入到16对齐，你只需要额外的15个字节，而不是16个。

答:

/* allocate a buffer with room to add 0-15 bytes to ensure 16-alignment */
void *mem = malloc(1024+15);
ASSERT(mem); // some kind of error-handling code
/* round up to multiple of 16: add 15 and then round down by masking */
void *ptr = ((char*)mem+15) & ~ (size_t)0x0F;

B:

free(mem);

2)对于一个更通用的内存分配函数，调用者不需要跟踪两个指针(一个使用，一个释放)。因此，在对齐的缓冲区下面存储一个指向“真实”缓冲区的指针。

答:

void *mem = malloc(1024+15+sizeof(void*));
if (!mem) return mem;
void *ptr = ((char*)mem+sizeof(void*)+15) & ~ (size_t)0x0F;
((void**)ptr)[-1] = mem;
return ptr;

B:

if (ptr) free(((void**)ptr)[-1]);

注意，与(1)中只向mem添加了15个字节不同，如果你的实现恰好保证了malloc的32字节对齐(不太可能，但理论上C实现可以有32字节对齐类型)，这段代码实际上可以减少对齐。如果您所做的只是调用memset_16aligned，那么这并不重要，但如果您为结构体使用内存，那么这可能很重要。

我不确定一个好的修复是什么(除了警告用户返回的缓冲区不一定适合任意结构)，因为没有办法通过编程确定特定于实现的对齐保证是什么。我猜在启动时，您可以分配两个或更多的1字节缓冲区，并假设您看到的最糟糕的对齐方式是保证对齐方式。如果你错了，你就浪费了记忆。谁有更好的主意，请说出来…

[添加: “标准”技巧是创建一个“可能是最大对齐类型”的联合，以确定必要的对齐方式。最大对齐类型可能是(在C99中)'long long'， 'long double'， 'void *'，或'void (*)(void)';如果你包含<stdint.h>，你可能会使用'intmax_t'来代替long long(并且，在Power 6 (AIX)机器上，intmax_t会给你一个128位整数类型)。该联合的对齐要求可以通过将其嵌入到一个带有单个char字符的结构体中来确定:

struct alignment
{
char     c;
union
{
intmax_t      imax;
long double   ldbl;
void         *vptr;
void        (*fptr)(void);
}        u;
} align_data;
size_t align = (char *)&align_data.u.imax - &align_data.c;

然后你可以使用请求对齐中较大的一个(在例子中是16)和上面计算的align值。

在(64位)Solaris 10上，malloc()的结果的基本对齐似乎是32字节的倍数。
)

在实践中，对齐分配器通常采用一个参数进行对齐，而不是硬连接。因此，用户将传递他们所关心的结构体的大小(或大于或等于2的最小次幂)，一切都将正常。

3)使用你的平台提供的:POSIX上的posix_memalign, Windows上的_aligned_malloc。

4)如果你使用C11，那么最干净——可移植和简洁——的选项是使用标准库函数aligned_alloc，它是在语言规范的这个版本中引入的。

小开

这里有一个“四舍五入”部分的替代方法。不是最出色的编码解决方案，但它完成了工作，而且这种类型的语法更容易记住(plus适用于不是2的幂的对齐值)。uintptr_t强制转换是必要的，以安抚编译器;指针算术不太喜欢除法或乘法。

void *mem = malloc(1024 + 15);
void *ptr = (void*) ((uintptr_t) mem + 15) / 16 * 16;
memset_16aligned(ptr, 0, 1024);
free(mem);

小开

在16字节计数vs 15字节计数的填充前面，您需要添加的实际数字以获得N的对齐是max (0, n - m)，其中M是内存分配器的自然对齐(两者都是2的幂)。

由于任何分配器的最小内存对齐都是1字节，因此15=max(0,16-1)是一个保守的答案。然而，如果你知道你的内存分配器将给你32位整型对齐的地址(这是相当常见的)，你可以使用12作为一个垫。

这对于本例来说并不重要，但对于具有12K RAM的嵌入式系统来说可能很重要，因为其中保存的每个int都很重要。

实现它的最好方法是，如果你真的想保存每一个字节，那么你可以把它作为宏，这样你就可以给它你的本机内存对齐。同样，这可能只对需要保存每个字节的嵌入式系统有用。

在下面的例子中，在大多数系统上，值1对于MEMORY_ALLOCATOR_NATIVE_ALIGNMENT来说是很好的，但是对于我们的32位对齐分配的理论嵌入式系统，下面的代码可以节省一小部分宝贵的内存:

#define MEMORY_ALLOCATOR_NATIVE_ALIGNMENT    4
#define ALIGN_PAD2(N,M) (((N)>(M)) ? ((N)-(M)) : 0)
#define ALIGN_PAD(N) ALIGN_PAD2((N), MEMORY_ALLOCATOR_NATIVE_ALIGNMENT)

小开

不幸的是，在C99中，似乎很难保证在任何符合C99的C实现之间都是可移植的。为什么?因为指针不能保证是平面内存模型中想象的“字节地址”。uintptr_t的表示也不是那么有保证，它本身是一个可选类型。

我们可能知道一些实现使用了void *(根据定义，也有char *)的表示，这是一个简单的字节地址，但对于我们程序员来说，C99是不透明的。实现可以用集合{段，抵消}表示指针，其中抵消“在现实中”可能有谁知道的对齐方式。为什么，指针甚至可以是某种形式的哈希表查找值，甚至是链表查找值。它可以编码边界信息。

在最近的C标准C1X草案中，我们看到了_Alignas关键字。这可能会有所帮助。

C99给我们的唯一保证是内存分配函数将返回一个适合赋值给指向任何对象类型的指针的指针。因为我们不能指定对象的对齐方式，所以我们不能以定义良好的、可移植的方式实现我们自己的分配函数来负责对齐。

如果这种说法是错误的，那就好了。

小开

使用memalign， Aligned-Memory-Blocks可能是这个问题的一个很好的解决方案。

小开

我很惊讶没有人投票给邵的回答，根据我的理解，它不可能做标准C99中要求的事情，因为将指针转换为整型形式是未定义的行为。(除了标准允许转换uintptr_t <-> void*，但标准似乎不允许对uintptr_t值进行任何操作，然后再将其转换回来。)

小开

long add;
mem = (void*)malloc(1024 +15);
add = (long)mem;
add = add - (add % 16);//align to 16 byte boundary
ptr = (whatever*)(add);

小开

你也可以添加一些16字节，然后通过添加指针下面的(16-mod)将原始ptr推到16位对齐:

main(){
void *mem1 = malloc(1024+16);
void *mem = ((char*)mem1)+1; // force misalign ( my computer always aligns)
printf ( " ptr = %p \n ", mem );
void *ptr = ((long)mem+16) & ~ 0x0F;
printf ( " aligned ptr = %p \n ", ptr );


printf (" ptr after adding diff mod %p (same as above ) ", (long)mem1 + (16 -((long)mem1%16)) );




free(mem1);
}

小开

MacOS X专用:

所有用malloc分配的指针都是16字节对齐的。
C11是支持的，所以你可以调用aligned_malloc (16, size)。

MacOS X在启动时为memset、memcpy和memmove的各个处理器选择了优化的代码，这些代码使用了你从未听说过的技巧来提高速度。99%的概率memset比任何手写的memset16运行得更快，这使得整个问题毫无意义。

如果你想要一个100%可移植的解决方案，在C11之前没有。因为没有可移植的方法来测试指针的对齐方式。如果它不需要100%便携，你可以使用

char* p = malloc (size + 15);
p += (- (unsigned int) p) % 16;

这假设将指针转换为unsigned int时，指针的对齐方式存储在最低位。转换为unsigned int会丢失信息，并且是实现定义的，但这并不重要，因为我们没有将结果转换回指针。

最可怕的部分当然是原始指针必须保存在某个地方，以便用它调用free()。所以总的来说，我真的怀疑这个设计是否明智。

小开

如果有限制，你不能浪费一个字节，那么这个解决方案是有效的: 注意:有一种情况可以无限执行:D

   void *mem;
void *ptr;
try:
mem =  malloc(1024);
if (mem % 16 != 0) {
free(mem);
goto try;
}
ptr = mem;
memset_16aligned(ptr, 0, 1024);

小开

对于解决方案，我使用了一个填充的概念，对齐内存和不浪费单个字节的内存

如果存在限制，则不能浪费单个字节。所有使用malloc分配的指针都是16字节对齐的

C11是支持的，所以你可以直接调用aligned_alloc (16, size)。

void *mem = malloc(1024+16);
void *ptr = ((char *)mem+16) & ~ 0x0F;
memset_16aligned(ptr, 0, 1024);
free(mem);

小开

我们一直在为accelerator .framework做这样的事情，这是一个高度向量化的OS X / iOS库，在那里我们必须一直注意对齐。有很多选择，其中一两个我在上面没有提到。

对于这样的小数组，最快的方法就是把它放在堆栈上。GCC / clang:

 void my_func( void )
{
uint8_t array[1024] __attribute__ ((aligned(16)));
...
}

不需要free()。这通常是两条指令:从堆栈指针减去1024，然后用-align对堆栈指针进行AND运算。假设请求者需要堆上的数据，因为数组的生命周期超过了堆栈，或者递归在工作，或者堆栈空间非常宝贵。

在OS X / iOS上，所有调用malloc/calloc/etc。总是16字节对齐。例如，如果你需要为AVX对齐32字节，那么你可以使用posix_memalign:

void *buf = NULL;
int err = posix_memalign( &buf, 32 /*alignment*/, 1024 /*size*/);
if( err )
RunInCirclesWaivingArmsWildly();
...
free(buf);

有些人提到c++接口的工作原理与此类似。

不要忘记页是按2的大幂进行对齐的，因此页对齐的缓冲区也是16字节对齐的。因此，mmap()和valloc()以及其他类似的接口也是选项。Mmap()的优点是，如果您愿意，可以在缓冲区中预先初始化一些非零的东西。由于它们具有页面对齐的大小，因此您将无法从中获得最小分配，并且在第一次接触它时可能会出现VM故障。

Cheesy:打开守卫malloc或类似的。像这样大小为n*16字节的缓冲区将对齐为n*16字节，因为VM用于捕获溢出，并且其边界位于页面边界。

一些Accelerate.framework函数使用用户提供的临时缓冲区作为临时空间。在这里，我们必须假设传递给我们的缓冲区严重错位，用户正积极地试图让我们的生活变得艰难。(我们的测试用例在临时缓冲区前后粘贴了一个保护页面，以强调恶意。)在这里，我们返回确保其中某个地方有16字节对齐段所需的最小大小，然后手动对齐缓冲区。这个大小是需要的大小+对齐- 1。因此，在这种情况下，这是1024 + 16 - 1 = 1039字节。然后排列如下:

#include <stdint.h>
void My_func( uint8_t *tempBuf, ... )
{
uint8_t *alignedBuf = (uint8_t*)
(((uintptr_t) tempBuf + ((uintptr_t)alignment-1))
& -((uintptr_t) alignment));
...
}

添加align -1会将指针移动到第一个对齐地址之前，然后使用-align进行and(例如0xfff…)Ff0 for alignment=16)将它带回对齐的地址。

正如其他文章所描述的，在其他没有16字节对齐保证的操作系统上，您可以调用更大的malloc，稍后将指针预留给free()，然后按照上面所述进行对齐并使用对齐的指针，这与我们的临时缓冲区的情况非常相似。

至于aligned_memset，这是相当愚蠢的。您只需要循环最多15个字节来到达一个对齐的地址，然后在那之后继续进行对齐的存储，并在最后进行一些可能的清理代码。您甚至可以在向量代码中进行清理位，或者作为重叠对齐区域的未对齐存储(提供长度至少是向量的长度)，或者使用像movmaskdqu这样的东西。有人只是偷懒了。然而，如果面试官想知道你是否熟悉stdint.h、位运算符和内存基本原理，这可能是一个合理的面试问题，所以这个人为的例子可以原谅。

小开

读到这个问题时，我脑子里冒出的第一件事是定义一个对齐的结构，实例化它，然后指向它。

有没有什么根本的原因，因为没有人建议我这么做?

作为旁注，由于我使用了一个char数组(假设系统的char是8位(即1字节))，我认为不一定需要__attribute__((packed))(如果我错了请纠正我)，但我还是把它放了进去。

这在我尝试的两个系统上都有效，但有可能是我不知道的编译器优化给了我关于代码有效性的误报。我在OSX上使用gcc 4.9.2，在Ubuntu上使用gcc 5.2.1。

#include <stdio.h>
#include <stdlib.h>


int main ()
{


void *mem;


void *ptr;


// answer a) here
struct __attribute__((packed)) s_CozyMem {
char acSpace[16];
};


mem = malloc(sizeof(struct s_CozyMem));
ptr = mem;


// memset_16aligned(ptr, 0, 1024);


// Check if it's aligned
if(((unsigned long)ptr & 15) == 0) printf("Aligned to 16 bytes.\n");
else printf("Rubbish.\n");


// answer b) here
free(mem);


return 1;
}

小开

size =1024;
alignment = 16;
aligned_size = size +(alignment -(size %  alignment));
mem = malloc(aligned_size);
memset_16aligned(mem, 0, 1024);
free(mem);

希望这是一个最简单的实现，让我知道你的意见。