提问



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


memset_16aligned函数需要传递给它的16字节对齐指针,否则会崩溃。


a)如何分配1024字节的内存,并将其与16字节边界对齐?

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字节对齐的(意味着前导字节地址需要是16的倍数),因此添加16个额外字节可确保我们有足够的空间。在前16个字节的某处,有一个16字节对齐的指针。 (注意malloc()应该返回一个与任何目的足够对齐的指针。但是,any的含义主要用于基本类型之类的东西 - long]],doublelong doublelong 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已经存在足够长的时间,可以在大多数平台上访问。如果不是printf()语句中使用PRIXPTR,那就足够了至#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():[91]



#include 

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

??
??描述

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

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

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

??
??free()函数应解除先前由posix_memalign()分配的内存。

??
??返回值

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



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


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

其它参考1


根据您对问题的看法,三个略有不同的答案:


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字节缓冲区,并假设你看到的最差对齐是保证对齐。如果你错了,你会浪费记忆。任何有更好主意的人,请说出来......


[[:
标准技巧是创建可能是最大对齐类型的联合以确定必要的对齐。最大对齐类型可能是(在C99中)long longlong doublevoid *void (*)(void);如果你包括,你可能会使用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_memalign用于POSIX,_aligned_malloc在Windows上。


4)如果你使用C11,那么最干净 - 便携和简洁 - 选项是使用在此版本的语言规范中引入的标准库函数aligned_alloc[92]

其它参考2


您也可以尝试posix_memalign()(当然在POSIX平台上)。[93]

其它参考3


这是向上舍入部分的另一种方法。不是最精彩编码的解决方案,但它完成了工作,这种类型的语法更容易记住(加上对于不是功率的对齐值2)。 uintptr_t演员阵容是安抚编译器的必要条件;指针运算不是非常喜欢除法或乘法。


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

其它参考4


不幸的是,在C99中,似乎很难保证任何类型的对齐方式,这种方式可以在符合C99的任何C实现中移植。为什么?因为不能保证指针是字节地址,可以想象使用平坦的内存模型。也没有保证 uintptr_t 的表示,无论如何它本身都是可选类型。


我们可能知道一些实现使用 void * (并且根据定义,也是 char * )的表示,这是一个简单的字节地址,但是通过C99它是不透明的我们,程序员。实现可能表示集合{段,偏移}的指针,其中 offset 可能具有谁知道什么是实际对齐。为什么,指针甚至可以是某种形式的哈希表查找值,甚至是链表查找值。它可以编码边界信息。


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


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


这种说法是错误的。

其它参考5


在16 vs 15字节数的填充前面,为了获得N的对齐而需要添加的实际数字是 max(0,NM)其中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)

其它参考6


也许他们会对memalign的知识感到满意?正如Jonathan Leffler所指出的那样,有两个更新的优选函数需要了解。[94]


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

其它参考7


我们一直在为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 
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,按位运算符和记忆基础知识感到满意,这可能是一个合理的面试问题,所以人为的例子可以被宽恕。

其它参考8


我很惊讶没有人投票支持Shao的答案,正如我所理解的那样,不可能按照标准C99的要求去做,因为正式将指针转换为整数类型是不明确的行为。 (除了允许转换uintptr_t< - > void*的标准外,该标准似乎不允许对uintptr_t值进行任何操作然后将其转换回来。)[[

其它参考9


使用memalign,Aligned-Memory-Blocks可能是解决问题的好方法。[97]

其它参考10


在阅读这个问题时,我首先想到的是定义一个对齐的结构,实例化它,然后指向它。


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


作为旁注,因为我使用了一个char数组(假设系统的char是8位(即1个字节)),我不认为需要属性((打包))必须(如果我错了,请纠正我),但无论如何我都把它放进去。


这适用于我尝试过的两个系统,但是有可能存在编译器优化,我不知道在代码的功效方面给出了误报。我在OSX上使用了gcc 4.9.2,在Ubuntu上使用了gcc 5.2.1。


#include 
#include 

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;
}

其它参考11


特定于MacOS X:



  1. 使用malloc分配的所有指针都是16字节对齐的。

  2. 支持C11,因此您只需调用aligned_malloc(16,size)即可。

  3. MacOS X选择在启动时针对各个处理器优化的代码,用于memset,memcpy和memmove,并且该代码使用您从未听说过的技巧来快速实现。将memset运行速度提高99%的几率 - 写的memset16使整个问题毫无意义。



如果您想要100%便携式解决方案,那么在C11之前就没有了。因为没有可移植的方法来测试指针的对齐方式。如果它不是100%便携式,你可以使用


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


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


可怕的部分当然是原始指针必须保存在某处以调用free()机智它。总而言之,我真的怀疑这种设计的智慧。

其它参考12


只是使用memalign? http://linux.die.net/man/3/memalign[98]

其它参考13


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

其它参考14


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


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

其它参考15


对于解决方案,我使用了填充的概念,它对齐内存并且不浪费
????单个字节的内存。


如果存在约束,则不能浪费单个字节。
使用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);

其它参考16


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