如何仅使用标准库分配alignment的内存？
作为面试的一部分，我刚刚完成了一个testing，有一个问题难倒我 – 甚至使用谷歌作为参考。 我想看看stackoverflow的工作人员可以用它做些什么：
“memset_16aligned”函数需要一个16bytealignment的指针传递给它，否则会崩溃。
a）如何分配1024字节的内存，并将其与16字节的边界alignment？
b）在执行memset_16aligned之后释放内存。
{ void *mem; void *ptr; // answer a) here memset_16aligned(ptr, 0, 1024); // answer b) here } 原始答案
{ 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字节alignment的（意思是前面的字节地址需要是16的倍数），所以增加16个额外的字节保证了我们有足够的空间。 在前16个字节的某处，有一个16字节alignment的指针。 （注意， malloc()应该返回一个指针，这个指针对任何目的来说都是非常好的，但是any的含义主要是基本types – long ， double ， long double ， long long和指向对象和指向函数的指针，当你在做更多特殊的事情时，比如使用graphics系统，他们可能需要比系统其他部分更严格的alignment，因此问题和答案是这样的。
下一步是将void指针转换为char指针; 尽pipeGCC，你不应该做空指针的指针算术（GCC有警告选项告诉你，当你滥用它）。 然后将16添加到开始指针。 假设malloc()返回了一个不可能的严格alignment的指针：0x800001。 添加16给0x800011。 现在我要回到16字节的边界 – 所以我想把最后4位复位为0. 0x0F的最后4位设置为1; 因此，除了最后四位之外， ~0x0F所有位都被设置为1。 用0x800011给出0x800010。 您可以迭代其他偏移量，并看到相同的algorithm。
free()的最后一个步骤很简单：只要返回free() ， malloc() ， calloc()或realloc()返回给你的值，任何事情都是一场灾难。 你正确地提供了mem来保存这个值 – 谢谢。 免费发布它。
最后，如果你知道你的系统的malloc包的内部，你可以猜测它可能会返回16字节alignment的数据（或者可能是8字节alignment）。 如果它是16字节alignment的，那么你就不需要使用这些值。 然而，这是不可靠和不可移植的 – 其他malloc包具有不同的最小alignment，因此假设一件事情做不同的事情会导致核心转储。 在广泛的范围内，这个解决scheme是便携式
其他人提到posix_memalign()作为获得alignment内存的另一种方式; 这在任何地方都无法实现，但通常可以以此为基础来实施。 请注意，alignment是2的幂是方便的; 其他路线更混乱。
还有一点评论 – 这段代码不检查分配是否成功。
修订
Windows程序员指出，你不能对指针进行位掩码操作，实际上，GCC（3.4.6和4.3.1testing）确实抱怨。 所以，基本代码的修改版本 – 转换为主程序，如下所示。 正如已经指出的那样，我也冒昧地把15个而不是16个。 我正在使用uintptr_t因为C99已经足够长，可以在大多数平台上访问。 如果不是在printf()语句中使用PRIXPTR ，那么#include <stdint.h>而不是使用#include <inttypes.h>就足够了。 [这段代码包括了CR所指出的修正，这是几年前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个字节alignment，那么选项更加有限。
- 显然，一种可能性是分配1024个字节，然后给这个地址“alignment处理”。 这种方法的问题是实际的可用空间不是正确的（可用空间在1008和1024字节之间，但是没有可用的机制来指定哪个大小），这使得它不太有用。
- 另一种可能性是，您需要编写一个完整的内存分配器，并确保您返回的1024字节块被适当alignment。 如果是这样的话，你最终可能会做一个与build议的解决scheme非常类似的操作，但是你将其隐藏在分配器中。
但是，如果面试官希望得到这些答复，我希望他们认识到，这个解决scheme回答了一个密切相关的问题，然后重新构思他们的问题，指出正确的方向。 （进一步说，如果面试官真的很乱，那么我就不要这份工作;如果对不够精确的要求的答复在没有更正的情况下被扑灭，那么面试官就不是一个安全的工作）。
世界继续前进
这个问题的标题最近已经改变了。 在C面试问题中解决了内存alignment困扰了我 。 修订后的标题（ 如何仅使用标准库分配alignment的内存？ ）需要稍微修改一下的答案 – 本附录提供了它。
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方式指定alignment的对象分配空间，其大小由size指定，其值不确定。alignment的值应该是由实现支持的有效alignment，并且size的值应该是alignment的整数倍。返回
aligned_alloc函数返回空指针或指向已分配空间的指针。
POSIX定义了posix_memalign() ：
#include <stdlib.h> int posix_memalign(void **memptr, size_t alignment, size_t size);描述
posix_memalign()函数应该分配在由alignment指定的边界上alignment的size字节，并且应该返回一个指向memptr分配的内存的memptr。alignment的值应是sizeof(void *)的两倍的幂。成功完成后，
memptr指向的值应该是一致的倍数。如果请求空间的大小为0，则行为是实现定义的; 在
memptr返回的值应该是空指针或唯一指针。
free()函数将释放之前由posix_memalign()分配的内存。返回值
成功完成后，
posix_memalign()将返回零; 否则，应返回一个错误号码来表示错误。
这两者中的任何一个或两个都可以用来回答现在的问题，但是当问题最初得到回答时，只有POSIX函数是一个选项。
在幕后，新的alignment的内存函数完成与问题中概述的大致相同的工作，除了它们能够更容易地强制alignment，并在内部跟踪alignment的内存的开始，使得代码不会必须特别处理 – 它只是释放所使用的分配函数返回的内存。
三个略有不同的答案取决于你如何看待这个问题：
1）对于Jonathan Leffler的解决scheme，确切的问题已经足够了，除了16位alignment之外，你只需要15个额外的字节，而不是16位。
A：
/* 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）对于更通用的内存分配函数，调用者不需要跟踪两个指针（一个使用，一个释放）。 所以你在alignment的缓冲区下面存储一个指向“真实”缓冲区的指针。
A：
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）那样，只有15个字节被添加到mem中，如果您的实现恰好保证了malloc的32字节alignment，这个代码实际上可以减lessalignment（不太可能，但理论上C实现可能有一个32字节alignmenttypes）。 这并不重要，如果你只是调用memset_16aligned，但如果你使用内存的结构，那么它可能很重要。
我不确定这是一个很好的解决办法（除了警告用户返回的缓冲区不一定适合任意的结构），因为没有办法从编程上确定实现特定的alignment保证是什么。 我想在启动时你可以分配两个或更多的1字节缓冲区，并假设你看到的最坏的alignment方式是保证alignment。 如果你错了，你会浪费记忆。 任何人有更好的主意，请说出来…
[ 补充 ：'标准'技巧是创build'可能是最大alignmenttypes'的联合来确定必要的alignment。 long longalignment的types可能是（在C99中）“ long long ”，“ long double ”，“ void * ”或“ void (*)(void) ”; 如果包含<stdint.h> ，则可能会使用' intmax_t '来代替long long （并且在Power 6（AIX）机器上， intmax_t将为您提供128位整数types）。 该联合的alignment要求可以通过将其embedded到具有单个字符的结构中，然后使用联合来确定：
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;
然后，您将使用所请求alignment的较大值（在本例中为16）和上面计算的align值。
在（64位）Solaris 10上，似乎malloc()的结果的基本alignment方式是32字节的倍数。
]
在实践中，alignment的分配器通常需要一个参数来进行alignment，而不是硬连线。 所以用户会传递他们关心的结构的大小（或者大于或等于2的最小次幂），一切都会好的。
3）使用你的平台提供的：POSIX的posix_memalign ，Windows的_aligned_malloc 。
4）如果你使用C11，那么最简洁便携的简洁选项就是使用这个语言规范版本中引入的标准库函数aligned_alloc 。
你也可以尝试posix_memalign() （当然在POSIX平台上）。
这是“整合”部分的另一种方法。 不是最精彩的编码解决scheme，但它完成了工作，这种types的语法有点容易记住（加上会alignment的值不是2的幂）。 uintptr_t是安抚编译器所必需的。 指针运算不是很喜欢分割或乘法运算。
void *mem = malloc(1024 + 15); void *ptr = (void*) ((uintptr_t) mem + 15) / 16 * 16; memset_16aligned(ptr, 0, 1024); free(mem);
不幸的是，在C99中，保证任何types的alignment都是非常困难的，这种方式可以通过符合C99的任何C实现进行移植。 为什么？ 因为指针不能保证是平面内存模型的“字节地址”。 uintptr_t也没有这样的保证，它本身是一个可选的types。
我们可能知道一些使用void *表示的实现（以及定义，也是char * ），这是一个简单的字节地址，但是对C99来说，程序员是不透明的。 一个实现可以通过集合{ segment ， offset }来表示一个指针，其中偏移量可以有谁知道什么alignment“实际上”。 为什么，一个指针甚至可能是某种forms的哈希表查找值，甚至是链表查找值。 它可以编码边界信息。
在最近的C标准草案中，我们看到了_Alignas关键字。 这可能会有所帮助。
C99给我们的唯一保证是内存分配函数将返回一个适合指向任何对象types的指针的指针。 由于我们无法指定对象的alignment方式，因此我们无法以定义明确的便携方式实现自己的alignmentfunction。
这个说法是错误的。
在16和15字节数填充前面，为了得到N的alignment，你需要添加的实际数量是max（0，NM） ，其中M是内存分配器的自然alignment（两者都是2的幂）。
由于任何分配器的最小内存alignment是1个字节，所以15 = max（0,16-1）是一个保守的答案。 但是，如果你知道你的内存分配器会给你32位intalignment的地址（这很常见），你可以用12作为一个pad。
这个例子对于这个例子来说并不重要，但是在一个12K的RAM的embedded式系统中，保存每一个int值都是非常重要的。
如果你真的要保存每一个可能的字节，实现它的最好方法是作为一个macros，所以你可以喂它你的本地内存alignment。 同样，这可能仅适用于需要保存每个字节的embedded式系统。
在下面的例子中，在大多数系统中，对于MEMORY_ALLOCATOR_NATIVE_ALIGNMENT ，值1是MEMORY_ALLOCATOR_NATIVE_ALIGNMENT ，但是对于我们的32位alignment分配的理论embedded式系统来说，下面可以节省一点宝贵的内存：
#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)
也许他们对memalign的知识会满意吗？ 正如乔纳森·莱弗勒（Jonathan Leffler）指出的那样，有两个更新的更好的function可以被了解。
哎呀，弗洛林打败了我。 但是，如果您阅读了我链接的手册页，则很可能会理解以前的海报提供的示例。
Accelerate.framework是一个高度vector化的OS X / iOS库，我们一直都在做这类事情，我们必须始终注意alignment。 有很多select，其中一个或两个我没有看到上面提到的。
像这样的小数组最快的方法就是把它粘在栈上。 用GCC / clang：
void my_func( void ) { uint8_t array[1024] __attribute__ ((aligned(16))); ... }
没有免费（）需要。 这通常是两条指令：从堆栈指针中减去1024，然后用-alignment和堆栈指针。 据推测，请求者需要在堆上的数据，因为它的数组寿命超过堆栈或recursion正在工作或堆栈空间是一个严重的溢价。
在OS X / iOS上，所有调用malloc / calloc / etc。 总是16个字节alignment。 例如，如果你需要32个字节对齐AVX，那么你可以使用posix_memalign：
void *buf = NULL; int err = posix_memalign( &buf, 32 /*alignment*/, 1024 /*size*/); if( err ) RunInCirclesWaivingArmsWildly(); ... free(buf);
有些人提到了类似的C ++接口。
不应该忘记页面alignment到2的大幂，所以页面alignment的缓冲区也是16字节alignment的。 因此，mmap（）和valloc（）以及其他类似的接口也是选项。 mmap（）的优点是，如果你愿意的话，缓冲区可以被初始化为非零的东西。 由于页面alignment的大小，您将不会从这些页面获得最小的分配，并且在您第一次触摸时可能会遇到虚拟机故障。
俗气：打开警卫malloc或类似的。 大小为n * 16个字节的缓冲区（例如这个缓冲区）将是n * 16个字节alignment的，因为VM用于捕捉超限并且其边界在页边界处。
某些Accelerate.framework函数将用户提供的临时缓冲区用作临时空间。 在这里，我们必须假设传递给我们的缓冲区是非常不协调的，用户正在积极努力地使我们的生活变得不合时宜。 （我们的testing用例在临时缓冲区之前和之后都粘贴了一个保护页面，以强调这一点）。在这里，我们返回保证16字节alignment的区段的最小尺寸，然后手动alignment缓冲区。 这个尺寸是所希望的尺寸+alignment方式-1。所以，在这种情况下，这是1024 + 16-1 = 1039字节。 然后alignment如下：
#include <stdint.h> void My_func( uint8_t *tempBuf, ... ) { uint8_t *alignedBuf = (uint8_t*) (((uintptr_t) tempBuf + ((uintptr_t)alignment-1)) & -((uintptr_t) alignment)); ... }
添加alignment方式1将把指针移过第一个alignment的地址，然后用alignment方式（例如0xfff … ff0alignment= 16）将其带回alignment的地址。
正如其他post所描述的那样，在没有16字节alignment保证的其他操作系统上，您可以调用malloc的大小，稍后将指针放在free（）处，然后如上所述alignment，然后使用alignment的指针，就像描述为我们的临时缓冲区情况。
至于aligned_memset，这是相当愚蠢的。 你只需要循环多达15个字节到达一个alignment的地址，然后进行alignment的存储，然后在最后使用一些可能的清理代码。 您甚至可以在向量代码中执行清理位，或者作为与alignment的区域重叠的未alignment的存储区（提供的长度至less是向量的长度），或者使用像movmaskdqu之类的东西。 有人正在懒惰。 不过，如果面试官想知道你是否适合stdint.h，按位运算符和内存基本原则，这可能是一个合理的面试问题，所以这个人为的例子是可以原谅的。
我很惊讶没有人投票支持邵的回答 ，据我所知，不可能做标准C99所要求的，因为正式地将指针转换为整数types是不确定的行为。 （除了允许uintptr_t < – > void*转换的标准之外，标准似乎不允许对uintptr_t值进行任何操作，然后将其转换回来。）
使用memalign， Aligned-Memory-Blocks可能是解决这个问题的好办法。
在阅读这个问题的时候，第一件事就是定义一个alignment的结构，实例化它，然后指向它。
有没有一个根本的原因，我失踪，因为没有人提出这个？
作为一个旁注，因为我使用了一个字符数组（假设系统的字符是8位（即1字节）），我没有看到需要的属性 （（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; }
MacOS X具体：
- 所有分配malloc的指针都是16个字节alignment的。
-
C11被支持，所以你可以调用aligned_malloc（16，size）。
-
MacOS Xselect在启动时针对memset，memcpy和memmove针对单个处理器进行了优化的代码，并且该代码使用您从来没有听说过的技巧来使其更快。 memset比任何手写的memset16运行速度快99％，这使得整个问题变得毫无意义。
如果你想要一个100％的便携式解决scheme，在C11之前是没有的。 因为没有可移植的方式来testing指针的alignment方式。 如果它不必是100％的便携式，你可以使用
char* p = malloc (size + 15); p += (- (unsigned int) p) % 16;
这假定当将指针转换为无符号整型时，指针的alignment被存储在最低位中。 转换为无符号的int会丢失信息，并且是实现定义的，但这并不重要，因为我们不会将结果转换回指针。
可怕的部分当然是，原来的指针必须保存在某个地方，用它来调用free（）。 总而言之，我真的怀疑这个devise的智慧。
只用memalign？ http://linux.die.net/man/3/memalign
你也可以添加一些16字节，然后把原来的ptr加到16位，方法是在指针下面加上（16-mod）
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); }
If there are constraints that, you cannot waste a single byte, then this solution works: Note: There is a case where this may be executed infinitely 😀
void *mem; void *ptr; try: mem = malloc(1024); if (mem % 16 != 0) { free(mem); goto try; } ptr = mem; memset_16aligned(ptr, 0, 1024);
For the solution i used a concept of padding which aligns the memory and do not waste the memory of a single byte .
If there are constraints that, you cannot waste a single byte. All pointers allocated with malloc are 16 bytes aligned.
C11 is supported, so you can just call aligned_malloc (16, size).
void *mem = malloc(1024+16); void *ptr = ((char *)mem+16) & ~ 0x0F; memset_16aligned(ptr, 0, 1024); free(mem);
long add; mem = (void*)malloc(1024 +15); add = (long)mem; add = add - (add % 16);//align to 16 byte boundary ptr = (whatever*)(add);
