如何仅使用标准库分配对齐的内存?
作为面试的一部分,我刚刚完成了一项测试,其中一个问题难倒我 - 甚至使用谷歌作为参考。 我想看看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
}
原始答案
{
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()
的最后一步很简单:你总是只返回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 <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个字节对齐,那么这些选项会受到更多限制。
但是,如果面试官希望得到这些答复,我希望他们认识到,这个解决方案回答了一个密切相关的问题,然后重新构思他们的问题,指出正确的方向。 (另外,如果面试官真的很慌张,那么我就不想要这份工作;如果对不够精确的要求的答案在没有更正的情况下被扑灭,那么面试官不是一个可以安全工作的人。)
世界继续前进
问题的标题最近已经改变。 这是在C面试问题中解决内存对齐难题的难题。 修订后的标题(如何仅使用标准库分配对齐的内存?)需要稍微修改一下的答案 - 本附录提供了它。
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
指定,其值不确定。 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
指定的边界上对齐的size
字节,并且应该返回一个指向memptr
分配的内存的memptr
。 alignment
的值应是sizeof(void *)
的两倍的幂。
成功完成后, memptr
指向的值应为多重alignment
。
如果请求的空间大小为0,则行为是实现定义的; memptr
返回的值应该是空指针或唯一指针。
free()
函数将释放之前由posix_memalign()
分配的内存。
返回值
成功完成后, posix_memalign()
将返回零; 否则,应返回一个错误编号以指示错误。
其中之一或两者都可以用来回答现在的问题,但只有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;
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)不同(1),其中只有15个字节被添加到mem中,如果您的实现恰好保证了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的posix_memalign
,Windows的_aligned_malloc
。
4)如果你使用C11,那么最简洁 - 便携和简洁的选项就是使用在这个版本的语言规范中引入的标准库函数aligned_alloc
。
你也可以尝试posix_memalign()
(当然是在POSIX平台上)。
上一篇: How to allocate aligned memory only using the standard library?