我刚刚完成了作为工作面试一部分的测试,一个问题难倒了我,甚至使用谷歌作为参考。我想看看 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 目的充分对齐的指针。但是,“any”的含义主要用于基本类型之类的东西 - long
、{3 }、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 Programmer 指出您不能对指针执行位掩码操作,事实上,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 评论:也许我今天早上有 [a] 阅读理解问题,但如果面试问题明确说:“你将如何分配 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
POSIX 定义了 posix_memalign()
:
#include
现在可以使用其中一个或两个来回答这个问题,但是当最初回答这个问题时,只有 POSIX 函数是一个选项。
在幕后,新的对齐内存功能与问题中概述的工作大致相同,除了它们能够更轻松地强制对齐,并在内部跟踪对齐内存的开始,这样代码就不会必须特别处理——它只是释放所使用的分配函数返回的内存。
根据您对问题的看法,三个略有不同的答案:
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;
乙:
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;
乙:
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 位整数类型)。该联合的对齐要求可以通过将其嵌入到具有单个字符后跟联合的结构中来确定:
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
。
ASSERT(mem);
检查分配结果; assert
用于捕获编程错误而不是缺少运行时资源。
char *
和 size_t
将导致错误。您必须使用 uintptr_t
之类的东西。
您也可以尝试 posix_memalign()
(当然在 POSIX 平台上)。
这是“汇总”部分的另一种方法。不是最出色的编码解决方案,但它完成了工作,并且这种类型的语法更容易记住(另外适用于不是 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 中,似乎很难以一种可以在任何符合 C99 的 C 实现中移植的方式保证任何类型的对齐。为什么?因为不能保证指针是“字节地址”,所以人们可能会在平面内存模型中想象。 uintptr_t 的表示也没有得到保证,它本身就是一个可选类型。
我们可能知道一些使用 void * 表示的实现(根据定义,还有 char *),它是一个简单的字节地址,但在 C99 中它对我们程序员来说是不透明的。一个实现可以用一个集合 {segment, offset} 来表示一个指针,其中 offset 可以“在现实中”有谁知道什么对齐。为什么,指针甚至可以是某种形式的哈希表查找值,甚至是链表查找值。它可以编码边界信息。
在最近的 C 标准 C1X 草案中,我们看到了 _Alignas 关键字。这可能有点帮助。
C99 给我们的唯一保证是内存分配函数将返回一个适合分配给指向任何对象类型的指针的指针。由于我们无法指定对象的对齐方式,因此我们无法实现自己的分配函数,负责以明确定义、可移植的方式对齐。
如果这个说法是错误的,那就太好了。
aligned_alloc()
。 (C++11 / 14 / 1z 还没有)。 _Alignas()
和 C++ alignas()
对动态分配不做任何事情,只对自动和静态存储(或结构布局)做任何事情。
在 16 与 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)
也许他们会对memalign的知识感到满意?正如 Jonathan Leffler 指出的那样,有两个更新的首选函数需要了解。
哎呀,弗洛林打败了我。但是,如果您阅读我链接到的手册页,您很可能会理解早期海报提供的示例。
memalign
函数已过时,应改用 aligned_alloc
或 posix_memalign
”。我不知道它在 2008 年 10 月说了什么——但它可能没有提到 aligned_alloc()
,因为它已添加到 C11。
我们一直在为 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 故障。
Cheesy:打开保护 malloc 或类似的。像这个这样大小为 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 进行与运算(例如,对齐= 16 的0xfff...ff0)将其返回到对齐的地址。
正如其他帖子所描述的,在其他没有 16 字节对齐保证的操作系统上,您可以调用具有更大大小的 malloc,稍后为 free() 预留指针,然后按照上面描述的方式对齐并使用对齐的指针,就像描述了我们的临时缓冲区案例。
至于aligned_memset,这是相当愚蠢的。您只需循环最多 15 个字节即可到达对齐的地址,然后在最后使用一些可能的清理代码继续对齐存储。您甚至可以在向量代码中进行清理位,或者作为与对齐区域重叠的未对齐存储(假设长度至少是向量的长度)或使用类似 movmaskdqu 的东西。有人只是懒惰。但是,如果面试官想知道您是否对 stdint.h、位运算符和内存基础知识感到满意,这可能是一个合理的面试问题,因此可以原谅人为设计的示例。
我很惊讶没有人投票赞成 Shao 的 answer,据我所知,不可能按照标准 C99 的要求去做,因为将指针正式转换为整数类型是未定义的行为。 (除了允许转换 uintptr_t
<-> void*
的标准外,该标准似乎不允许对 uintptr_t
值进行任何操作然后将其转换回来。)
unsigned char* myptr
;然后计算`mptr += (16-(uintptr_t)my_ptr) & 0x0F,将在定义 my_ptr 的所有实现上定义行为,但结果指针是否对齐将取决于 uintptr_t 位和地址之间的映射。
使用 memalign,Aligned-Memory-Blocks 可能是解决问题的好方法。
memalign
函数已过时,应改用 aligned_alloc
或 posix_memalign
”。我不知道它在 2010 年 10 月是怎么说的。
阅读这个问题时,我首先想到的是定义一个对齐的结构,实例化它,然后指向它。
由于没有其他人建议,我是否有一个根本原因失踪?
作为旁注,由于我使用了一个 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;
}
MacOS X 特定:
所有用 malloc 分配的指针都是 16 字节对齐的。支持 C11,因此您只需调用 aligned_malloc (16, size)。 MacOS X 在启动时为 memset、memcpy 和 memmove 选择针对单个处理器进行优化的代码,并且该代码使用您从未听说过的技巧来加快速度。 memset 有 99% 的几率比任何手写的 memset16 运行得更快,这使得整个问题毫无意义。
如果你想要一个 100% 便携的解决方案,在 C11 之前没有。因为没有可移植的方法来测试指针的对齐方式。如果它不必是 100% 便携的,你可以使用
char* p = malloc (size + 15);
p += (- (unsigned int) p) % 16;
这假设在将指针转换为无符号整数时,指针的对齐方式存储在最低位中。转换为 unsigned int 会丢失信息并且是实现定义的,但这并不重要,因为我们不会将结果转换回指针。
可怕的部分当然是原始指针必须保存在某个地方才能用它调用 free() 。所以总而言之,我真的怀疑这种设计的智慧。
aligned_malloc
?我使用的是 Xcode 6.1,它没有在 iOS SDK 的任何地方定义,也没有在 /usr/include/*
的任何地方声明。
aligned_alloc()
,但它也没有被声明。从 GCC 5.3.0,我得到了有趣的消息 alig.c:7:15: error: incompatible implicit declaration of built-in function ‘aligned_alloc’ [-Werror]
和 alig.c:7:15: note: include ‘<stdlib.h>’ or provide a declaration of ‘aligned_alloc’
。该代码确实包含 <stdlib.h>
,但 -std=c11
和 -std=gnu11
都没有更改错误消息。
您还可以添加一些 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);
}
如果有限制,你不能浪费一个字节,那么这个解决方案有效:注意:有一种情况可以无限执行:D
void *mem;
void *ptr;
try:
mem = malloc(1024);
if (mem % 16 != 0) {
free(mem);
goto try;
}
ptr = mem;
memset_16aligned(ptr, 0, 1024);
void*
定义了 %
运算符吗?
对于解决方案,我使用了填充的概念,它对齐内存并且不浪费单个字节的内存。
如果有限制,你不能浪费一个字节。所有用 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);
malloc()
返回的指针确实在 16 字节边界上对齐,但任何标准都不能保证——它会简单地为任何用途以及在许多 32 位系统上充分对齐在 8 字节边界上对齐就足够了,对于某些人来说,4 字节边界就足够了。
size =1024;
alignment = 16;
aligned_size = size +(alignment -(size % alignment));
mem = malloc(aligned_size);
memset_16aligned(mem, 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);
add += 16 - (add % 16)
。 (2 - (2 % 16)) == 0
。
不定期副业成功案例分享
<inttypes.h>
可用,则原始代码是正确的(至少对于格式字符串 - 可以说,值应该使用强制转换传递:(uintptr_t)mem, (uintptr_t)ptr
)。格式字符串依赖于字符串连接,PRIXPTR 宏是正确的printf()
长度和类型说明符,用于uintptr_t
值的十六进制输出。另一种方法是使用%p
,但其输出因平台而异(有些添加前导0x
,大多数不添加)并且通常用小写十六进制数字编写,我不喜欢;我写的跨平台是统一的。