c语言 - 为什么我们在实现对齐的malloc时使用按位运算符&和~而不是数学运算符%？

Question

在研究Linux操作系统的内存管理时，我看到实现对齐malloc函数的一般解决方案是以下代码：

void *aligned_malloc(size_t required_bytes, size_t alignment) {
void *p1; // original block
void **p2; // aligned block
int offset = alignment - 1 + sizeof(void *);
if ((p1 = (void *)malloc(required_bytes + offset)) == NULL) {
return NULL;
}
p2 = (void **)(((size_t)(p1) + offset) & ~(alignment - 1));
p2[-1] = p1;
return p2;
}

该解决方案存在一个问题，即由于& ~(alignment - 1)，只有当alignment为2的幂时，它才能正常工作。此外，alignment必须是size_t数据类型，以便适合指针p1的数据类型。 由于这些限制，我想到了另一种解决方案，即：

void *aligned_malloc(size_t required_bytes, size_t alignment) {
void *p1; // original block
void **p2; // aligned block
int offset = alignment - 1 + sizeof(void *);
if ((p1 = (void*)malloc(required_bytes + offset)) == NULL) {
return NULL;
}
offset = (size_t)(p1) % alignment; // offset is used so that I don't have to declare another variable
p2 = (void **)((size_t)(p1) + (alignment - offset));
p2[-1] = p1;
return p2;
}

此解决方案解决了这两个问题，即alignment不必既不是 2 的幂，也不必是数据类型size_t。我的问题是，为什么不使用这种实现对齐 malloc 的方式？它的缺点是什么，使人们选择按位运算符的解决方案&和~？

任何帮助真的非常感谢。谢谢。

Answer 1

我同意你的观点，经典代码有问题，但不完全是提到的那些：

• alignment确实必须是 2 的幂，这是 POSIX 标准函数aligned_alloc的约束。事实上，alignment必须是大于或等于sizeof(size_t)的 2 的幂，并且在此标准下，大小参数应该是alignment的倍数。

• alignment是用类型size_t定义的，但这与指针p1的数据类型无关。事实上，size_t和void *的大小可能与 16 位 MSDOS/Windows 中大型模型体系结构不同。

  因此，代码p2 = (void **)(((size_t)(p1) + offset) & ~(alignment - 1));并不严格符合。要解决此问题，可以使用<stdint.h>中定义的uintptr_t，该被指定为具有与void *相同的大小：

  p2 = (void **)(void *)(((uintptr_t)(p1) + offset) & ~(alignment - 1));
  

• 发布的代码中还有另一个问题：如果alignment小于sizeof(void *)，则p2可能未对齐以写入void *值p1。需要额外的代码来确保alignment至少与sizeof(void *)一样大。在实际系统中，这不是问题，因为malloc()必须返回针对所有基本类型(包括void *)正确对齐的指针。

首选按位&和~运算符的原因是效率之一：对于x无符号整数和alignment2x & (alignment - 1)的幂等同于x % alignment，但对于大多数 CPU 来说，使用按位掩码计算比使用除法计算要快得多，并且编译器无法假设alignment是 2 的幂，因此它会使用慢得多的整数除法指令。

此外，您的计算不正确：如果p1未对齐，则offset(计算为(size_t)(p1) % alignment)可以大到alignment - 1，因此p2可以接近p1个字节，因此p2[-1] = p1;会在分配的空间开始之前写入。

这是一个修改版本：

#include <stdint.h>
#include <stdlib.h>
void *aligned_malloc(size_t size, size_t alignment) {
// alignment must be a power of 2
//assert(alignment != 0 && (alignment & (alignment - 1)) == 0);
void *p1;     // allocated block
void **p2;    // aligned block
size_t slack; // amount of extra memory to allocate to ensure proper alignment
// and space to save the original pointer returned by malloc.
//compute max(alignment - 1, sizeof(void*) - 1) without testing:
size_t alignment_mask = (alignment - 1) | (sizeof(void *) - 1);
slack = alignment_mask + sizeof(void *);
if ((p1 = malloc(size + slack)) == NULL)
return NULL;
p2 = (void **)(void *)(((uintptr_t)p1 + slack) & ~alignment_mask);
p2[-1] = p1;
return p2;
}

Answer 2

可能是因为alignment是一个具有(对于编译器)未知值的变量，这意味着编译器不能轻松地将其作为更简单的操作。

按位运算比%运算符所需的算术(尤其是除法)更简单、更高效。