为什么会有这个疑问

之前看了本电子书《C标准库》,对其中的malloc/free的实现比较好奇,K&R中实现了一个简单的,但是在强烈的好奇心驱动下想看下真正的实现是怎样的,于是翻到13章,看到存储分配的那一小节,发现有一句定义:

#define CELL_OFF (sizeof(size_t) + _MEMBND & ~_MEMBND)

书上解释说_MEMBND是一个宏,对应于对齐的要求,是2^(n-1),其中n是对齐字节的阶数。 看到这句,演算了一下,百思不得其解。

后来我算是明白了,这是个印刷错误,_MEMBND应该是2^n-1,不然无法实现所需要对齐的功能。这一点也在linux的内核代码中得到验证:

#define DK_MEMBND 2U /* cts : 4 byte malloc boundaries (3 ==> 8 byte) */
#define M_MASK ((1 << DK_MEMBND) - 1) /* rounds all sizes */
#define CELL_OFF ((DKoffsetof(_Cell, _Next) + M_MASK) & ~M_MASK)

注意其中M_MASK即是上文的_MEMBND,先左移1位,再减1,这样就比较能理解了。

如何理解 n + x & ~x表达式

这是一个求对齐的式子,首先上实验结果: 代码如下:

#include <stdio.h>
#include <stdlib.h>
    
#define _MEMBND 3
     
int main()
{
    int i;
    for (i = 0; i < 100; i++)
    {
        printf("%d:%d\n", i, i + _MEMBND & ~_MEMBND);
    }
    return 0;
 }

结果如下:

0:0

1:4

2:4

3:4

4:4

5:8

6:8

7:8

8:8

9:12

10:12

11:12

12:12

13:16

14:16

15:16

16:16

17:20

18:20

4字节对齐,M_MASK的值是3,其二进制表示是0011,~M_MASK是1100, 也就是最后两位先加到欲求对齐的数字上,然后再舍去。加上0011会有什么结果呢?可能的数字变化(最后两位非00),倒数第三位及以后可能会发生变化, 而倒数第三位变化1位,即即意味着4个字节的变化。并且因为& ~M_MASK的操作,对后两个位的变化不关注,而能导致倒数第三位变化的倒数第一位和倒数第二位的条件是至少有一位为1,可能的组合是 11,10,01,分别是+3,+2,+1。所以对于一个齐整的已对齐的4字节而言,所有在其后+1,+2,+3的字节通过上述的操作都会被对齐到+4。

所以这个表达式的意义,对于4字节对齐而言,是关注欲对齐的数字n的后两位,若为非4的倍数,则会对齐到 (n//4 + 1) * 4的字节数。