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

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

"memset_16aligned"函数需要传递给它的16byte对齐指针,否则它将崩溃.

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

{    
   void *mem;
   void *ptr;

   // answer a) here

   memset_16aligned(ptr, 0, 1024);

   // answer b) here    
}

Jonathan Lef.. 570

原始答案

{
    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()应该返回已充分为对齐的指针任何目的然而,"任何"主要的东西基本一样类型的含义- ,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()是很容易:你一定要只,返回free()的值之一malloc(),calloc()或realloc()退还给你-还有什么别的是一场灾难.你正确地提供mem了保持这个价值 - 谢谢你.免费发布它.

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

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

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

修订

Windows程序员指出你不能对指针进行位掩码操作,事实上,GCC(经过测试的3.4.6和4.3.1)就是这样抱怨的.因此,基本代码的修改版本 - 转换为主程序,如下.我已经冒昧地增加了15而不是16,正如已经指出的那样.我正在使用,uintptr_t因为C99已经存在很长时间,可以在大多数平台上访问.如果不是PRIXPTR在printf()陈述中使用,那么#include 代替使用就足够了#include .[这段代码包括CR指出的修正案,它重申了Bill K多年前首次提出的一个观点,直到现在我都忽略了这一点.

#include 
#include 
#include 
#include 
#include 

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 
#include 
#include 
#include 
#include 

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 
void *aligned_alloc(size_t alignment, size_t size);

说明
该aligned_alloc函数为对象指定的对象分配空间,对象的alignment大小由指定size,并且其值是不确定的.值alignment应为实现支持的有效对齐,其值size应为.的整数倍alignment.

返回
该aligned_alloc函数返回空指针或指向已分配空间的指针.

而POSIX定义posix_memalign():

#include 

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

描述

该posix_memalign()函数应分配size在指定边界上对齐的字节alignment,并应返回指向已分配内存的指针memptr.值alignment应为两倍的幂sizeof(void *).

成功完成后,指向的值memptr应为.的倍数alignment.

如果请求的空间大小为0,则行为是实现定义的; 返回的值memptr应为空指针或唯一指针.

该free()函数应释放先前已分配的内存posix_memalign().

返回值

成功完成后,posix_memalign()应归零; 否则,应返回错误编号以指示错误.

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

在幕后,新的对齐记忆功能完成了与问题中概述的大致相同的工作,除了它们能够更容易地强制对齐,并在内部跟踪对齐的内存的开始,以便代码不会必须专门处理 - 它只是释放由使用的分配函数返回的内存.

原始答案

{
    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()应该返回已充分为对齐的指针任何目的然而,"任何"主要的东西基本一样类型的含义- ,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()是很容易:你一定要只,返回free()的值之一malloc(),calloc()或realloc()退还给你-还有什么别的是一场灾难.你正确地提供mem了保持这个价值 - 谢谢你.免费发布它.

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

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

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

修订

Windows程序员指出你不能对指针进行位掩码操作,事实上,GCC(经过测试的3.4.6和4.3.1)就是这样抱怨的.因此,基本代码的修改版本 - 转换为主程序,如下.我已经冒昧地增加了15而不是16,正如已经指出的那样.我正在使用,uintptr_t因为C99已经存在很长时间,可以在大多数平台上访问.如果不是PRIXPTR在printf()陈述中使用,那么#include 代替使用就足够了#include .[这段代码包括CR指出的修正案,它重申了Bill K多年前首次提出的一个观点,直到现在我都忽略了这一点.

#include 
#include 
#include 
#include 
#include 

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 
#include 
#include 
#include 
#include 

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 
void *aligned_alloc(size_t alignment, size_t size);

说明
该aligned_alloc函数为对象指定的对象分配空间,对象的alignment大小由指定size,并且其值是不确定的.值alignment应为实现支持的有效对齐,其值size应为.的整数倍alignment.

返回
该aligned_alloc函数返回空指针或指向已分配空间的指针.

而POSIX定义posix_memalign():

#include 

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

描述

该posix_memalign()函数应分配size在指定边界上对齐的字节alignment,并应返回指向已分配内存的指针memptr.值alignment应为两倍的幂sizeof(void *).

成功完成后,指向的值memptr应为.的倍数alignment.

如果请求的空间大小为0,则行为是实现定义的; 返回的值memptr应为空指针或唯一指针.

该free()函数应释放先前已分配的内存posix_memalign().

返回值

成功完成后,posix_memalign()应归零; 否则,应返回错误编号以指示错误.

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

在幕后,新的对齐记忆功能完成了与问题中概述的大致相同的工作,除了它们能够更容易地强制对齐,并在内部跟踪对齐的内存的开始,以便代码不会必须专门处理 - 它只是释放由使用的分配函数返回的内存.

/* 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;

free(mem);

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;

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

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;

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

#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)

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

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

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