如何仅使用标准库分配对齐的内存？-Java 学习之路

381

我刚刚完成了一次测试，作为求职面试的一部分，一个问题让我感到难过 - 甚至使用谷歌作为参考 . 我想看看stackoverflow工作人员可以用它做什么：

The “memset_16aligned” function requires a 16byte aligned pointer passed to it, or it will crash.

a）如何分配1024字节的内存，并将其与16字节边界对齐？
b）执行memset_16aligned后释放内存 .

{

   void *mem;

   void *ptr;

   // answer a) here

   memset_16aligned(ptr, 0, 1024);

   // answer b) here

}

17 回答

1

你也可以试试posix_memalign()（当然是在POSIX平台上） .

回复于 2024-04-30T20:00:05+08:00
55
原始答案
```
{
    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 来保持这个 Value - 谢谢 . 免费发布它 .

最后，如果您了解系统的 malloc 包的内部结构，您可能会猜测它可能会返回16字节对齐的数据（或者它可能是8字节对齐的） . 如果它是16字节对齐的，那么你不需要对这些值进行调整 . 然而，这是狡猾和不可移植 - 其他 malloc 包具有不同的最小对齐，因此假设有一件事情，当它做不同的事情会导致核心转储 . 在宽范围内，此解决方案是便携式的 .

有人提到 posix_memalign() 作为获得对齐内存的另一种方式;这在任何地方都不可用，但通常可以使用此作为基础来实现 . 注意，对齐方便是2的幂;其他路线比较混乱 .

还有一条评论 - 此代码不会检查分配是否成功 .

修正案

Windows Programmer指出你也可以自由地增加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评论：也许我今天早上有[a]阅读理解问题，但如果面试问题具体说："How would you allocate 1024 bytes of memory"并且你明确分配的不仅仅是这个问题 . 这不是面试官的自动失败吗？

我的回答不符合300个字符的评论......

我想这取决于它 . 我想大多数人（包括我）都提出这样的问题：“你将如何分配一个可以存储1024字节数据的空间，以及基址是16字节的倍数” . 如果面试官真的意味着你如何分配1024字节（仅）并使其16字节对齐，那么选项更有限 .
- 显然，一种可能性是分配1024个字节，然后给该地址'alignment treatment';该方法的问题在于实际可用空间没有正确确定（可用空间在1008到1024字节之间，但没有可用于指定哪个大小的机制），这使得它不太有用 .
- 另一个可能性是您需要编写一个完整的内存分配器，并确保返回的1024字节块已正确对齐 . 如果是这种情况，您可能最终执行的操作与提议的解决方案完全相似，但您将其隐藏在分配器中 .
但是，如果面试官期望这些回答中的任何一个，我希望他们认识到这个解决方案回答了一个密切相关的问题，然后重新构思他们的问题，以便将对话指向正确的方向 . （此外，如果面试官变得非常粗犷，那么我就不会想要这份工作;如果对不完全精确的要求的答案在没有纠正的情况下被火上浇油，那么面试官就不是一个可以安全工作的人 . ）

世界继续前进

问题的 Headers 最近有所改变 . 这是解决C采访问题中的记忆对齐困扰我 . 修订后的 Headers （如何仅使用标准库分配对齐的内存？）需要稍加修改的答案 - 本附录提供了它 .

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指定，其值不确定 . 对齐的值应该是实现支持的有效对齐，并且size的值应该是对齐的整数倍 . 返回aligned_alloc函数返回空指针或指向已分配空间的指针 .

POSIX定义posix_memalign()：

#include <stdlib.h>

int posix_memalign（void ** memptr，size_t alignment，size_t size）;
描述posix_memalign（）函数应分配在由alignment指定的边界上对齐的大小字节，并且应在memptr中返回指向已分配内存的指针 . 对齐的值应为sizeof（void *）的两倍的幂 . 成功完成后，memptr指向的值应为对齐的倍数 . 如果请求的空间大小为0，则行为是实现定义的; memptr中返回的值应为空指针或唯一指针 . free（）函数应解除先前由posix_memalign（）分配的内存 . 返回值成功完成后，posix_memalign（）将返回零;否则，应返回错误编号以指示错误 .

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

在幕后，新的对齐记忆功能完成了与问题中概述的大致相同的工作，除了它们能够更容易地强制对齐，并在内部跟踪对齐的内存的开始，以便代码不会必须专门处理 - 它只是释放由使用的分配函数返回的内存 .
回复于 2024-04-30T20:00:05+08:00
547
我们一直在为Accelerate.framework做一件事，这是一个高度向量化的OS X / iOS库，我们必须始终注意对齐 . 有很多选择，其中一个或两个我没有看到上面提到的 .

像这样的小阵列最快的方法就是将它粘在堆栈上 . GCC / clang：
```
void my_func( void )
 {
     uint8_t array[1024] __attribute__ ((aligned(16)));
     ...
 }
```
不需要free（） . 这通常是两条指令：从堆栈指针中减去1024，然后使用-alignment与堆栈指针相比较 . 据推测，请求者需要堆上的数据，因为它的生命周期超出了堆栈或递归正在工作或堆栈空间非常重要 .

在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故障 .

俗气：打开警卫摩托车或类似物 . 大小为n * 16字节的缓冲区（例如此缓冲区）将对齐n * 16字节，因为VM用于捕获溢出，其边界位于页边界 .

一些Accelerate.framework函数接受用户提供的临时缓冲区作为临时空间 . 在这里，我们必须假设传递给我们的缓冲区严重错位，并且用户正在积极地努力使我们的生活变得困难 . （我们的测试用例在临时缓冲区之前和之后粘贴一个保护页面以强调恶意 . ）在这里，我们返回最小尺寸我们需要在其中的某处保证16字节对齐的段，然后手动对齐缓冲区 . 这个大小是desired_size alignment - 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));
    ...
}
```
添加alignment-1将使指针移过第一个对齐的地址，然后使用-alignment进行AND运算（例如0xfff ... ff0 for alignment = 16）将其返回到对齐的地址 .

正如其他帖子所述，在没有16字节对齐保证的其他操作系统上，你可以调用较大的malloc，稍后将指针放在free（）之后，然后如上所述对齐并使用对齐的指针，就像为我们的临时缓冲区描述 .

至于aligned_memset，这是相当愚蠢的 . 您只需循环最多15个字节即可到达对齐的地址，然后在此之后继续使用对齐的存储，并在最后使用一些可能的清理代码 . 您甚至可以在向量代码中执行清理位，作为与对齐区域重叠的未对齐存储（提供长度至少是向量的长度）或使用类似movmaskdqu的内容 . 有人只是懒惰 . 然而，如果面试官想知道你是否对stdint.h，按位运算符和记忆基础知识感到满意，这可能是一个合理的面试问题，所以人为的例子可以被宽恕 .
回复于 2024-04-30T20:00:05+08:00
5
对于解决方案，我使用了填充的概念，它对齐内存并且不会浪费单个字节的内存 .

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

支持C11，因此您只需调用aligned_malloc（16，size） .
```
void *mem = malloc(1024+16);
void *ptr = ((char *)mem+16) & ~ 0x0F;
memset_16aligned(ptr, 0, 1024);
free(mem);
```
回复于 2024-04-30T20:00:05+08:00
15

不幸的是，在C99中，似乎很难保证任何类型的对齐方式，这种方式可以在符合C99的任何C实现中移植 . 为什么？因为指针不能保证是"byte address"，可以想象使用平坦的内存模型 . uintptr_t 的表示也没有得到保证，无论如何它本身都是一个可选类型 .

我们可能知道一些使用 **void *** （并且根据定义，也是 **char *** ）的表示的实现，这是一个简单的字节地址，但是对于我们程序员来说，它对C99来说是不透明的 . 一个实现可能表示一个集合{segment，offset}的指针，其中offset可能有谁知道什么是对齐"in reality."为什么，指针甚至可以是某种形式的哈希表查找值，甚至是链表查找值 . 它可以编码边界信息 .

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

C99给我们的唯一保证是内存分配函数将返回一个指针，该指针适合分配给指向任何对象类型的指针 . 由于我们无法指定对象的对齐方式，因此我们无法以明确定义的可移植方式实现自己的分配函数 .

这种说法是错误的 .

回复于 2024-04-30T20:00:05+08:00
37
根据您对问题的看法，三个略有不同的答案：

1）对于Jonathan Leffler的解决方案提出的确切问题已经足够了，除了要将16位对齐，你只需要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）对于更通用的内存分配函数，调用者不希望必须跟踪两个指针（一个使用，一个指向空闲） . 因此，您将指针存储到对齐缓冲区下方的“实际”缓冲区 .

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字节对齐，这个代码实际上可以减少对齐（不太可能，但理论上C实现可能有32字节）对齐型） . 如果您所做的只是调用memset_16aligned，那么无关紧要，但是如果您将内存用于结构，那么它可能很重要 .

我不确定这是一个很好的解决方案（除了警告用户返回的缓冲区不一定适合任意结构），因为没有办法以编程方式确定特定于实现的对齐保证是什么 . 我想在启动时你可以分配两个或更多的1字节缓冲区，并假设你看到的最差对齐是保证对齐 . 如果你错了，你会浪费记忆力 . 任何有更好主意的人，请说出来......

[补充：'standard'技巧是创建'likely to be maximally aligned types'的并集以确定必要的对齐方式 . 最大对齐类型可能是（在C99中）' long long ', ' long double ', ' void * ', or ' 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;
```
然后，您将使用较大的请求对齐（in示例，16）和上面计算的 align 值 .

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

在实践中，对齐的分配器通常采用对齐的参数而不是硬连线 . 因此，用户将传递他们关心的结构的大小（或者大于或等于2的最小功率）并且一切都会很好 .

3）使用您的平台提供的内容： posix_memalign for POSIX， _aligned_malloc 在Windows上 .

4）如果你使用C11，那么最干净 - 可移植和简洁 - 选项是使用此版本的语言规范中引入的标准库函数aligned_alloc .
回复于 2024-04-30T20:00:05+08:00
-2

使用memalign，Aligned-Memory-Blocks可能是解决问题的好方法 .

回复于 2024-04-30T20:00:05+08:00

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

回复于 2024-04-30T20:00:05+08:00

您还可以添加大约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);
}

回复于 2024-04-30T20:00:05+08:00

0
特定于MacOS X：
- 用malloc分配的所有指针都是16字节对齐的 .
  支持
- C11，因此您只需调用aligned_malloc（16，size）即可 .
- MacOS X选择在启动时为各个处理器优化的代码，用于memset，memcpy和memmove，并且该代码使用您从未听说过的技巧来快速实现 . memset运行速度比任何手写memset16快99％，这使得整个问题毫无意义 .
如果您想要100％便携式解决方案，那么在C11之前就没有了 . 因为没有可移植的方法来测试指针的对齐方式 . 如果它不必100％便携，您可以使用
```
char* p = malloc (size + 15);
p += (- (unsigned int) p) % 16;
```
这假设在将指针转换为unsigned int时，指针的对齐存储在最低位中 . 转换为unsigned int会丢失信息并且是实现定义的，但这并不重要，因为我们不会将结果转换回指针 .

可怕的部分当然是原始指针必须保存在某个地方用它来调用free（） . 总而言之，我真的怀疑这种设计的智慧 .
回复于 2024-04-30T20:00:05+08:00
8
这里's an alternate approach to the '向上舍入' part. Not the most brilliantly coded solution but it gets the job done, and this type of syntax is a bit easier to remember (plus would work for alignment values that aren' t为2的幂 . uintptr_t 演员是安抚编译器的必要条件;指针运算不是很喜欢除法或乘法 .
```
void *mem = malloc(1024 + 15);
void *ptr = (void*) ((uintptr_t) mem + 15) / 16 * 16;
memset_16aligned(ptr, 0, 1024);
free(mem);
```
回复于 2024-04-30T20:00:05+08:00
3

也许他们会对memalign的知识感到满意？正如Jonathan Leffler指出的那样，有两个更新的优选功能需要了解 .

哎呀，弗罗林打败了我 . 但是，如果您阅读我链接的手册页，您很可能会理解早期海报提供的示例 .

回复于 2024-04-30T20:00:05+08:00
18
在阅读这个问题时，我首先想到的是定义一个对齐的结构，实例化它，然后指向它 .

有没有一个根本原因我失踪，因为没有人建议这个？

作为旁注，因为我使用了一个char数组（假设系统's char is 8 bits (i.e. 1 byte)), I don't必须看到 attribute （（打包））的必要性（如果我错了就纠正我），但无论如何我都把它放进去了 .

这适用于我尝试过的两个系统，但是有可能存在编译器优化，我不知道在代码的功效方面给出了误报 . 我在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;
}
```
回复于 2024-04-30T20:00:05+08:00
3

只是使用memalign？ http://linux.die.net/man/3/memalign

回复于 2024-04-30T20:00:05+08:00
0
在16 vs 15字节数的填充前面，你需要添加以获得N对齐的实际数字是 max(0,N-M) ，其中M是内存分配器的自然对齐（两者都是2的幂） .

由于任何分配器的最小内存对齐是1个字节，因此15 = max（0,16-1）是保守的答案 . 但是，如果您知道您的内存分配器将为您提供32位int对齐的地址（这是相当常见的），您可以使用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)
```
回复于 2024-04-30T20:00:05+08:00
0

我'm surprised noone'投了Shao的answer，根据我的理解，它不可能做标准C99中的问题，因为正式将指针转换为整数类型是未定义的行为 . （除了允许转换 uintptr_t < - > void* 的标准外，标准似乎不允许对 uintptr_t 值进行任何操作然后将其转换回来 . ）

回复于 2024-04-30T20:00:05+08:00

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

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

回复于 2024-04-30T20:00:05+08:00

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

17 回答

原始答案

修正了答案

按要求说明

修正案

采访者的问题

世界继续前进

相关问题