结构体内存对齐

1. 结构体对齐是为了提高CPU读取内存效率，防止一个数据放在两个8自己内存块中。无论是否对齐，x86-64都能正确工作。对齐的基本原则是K字节类型对象的对象起始地址必须是K的倍数：
   

2. 编译器需要在结构体中插入一些空隙来保证对齐，考虑下面的结构体:

   struct s1 {
    int i;
    char c;
    int j;
    };
   
    struct s1 a;
    struct s1* p = &a;
   

   假设p的地址为$x_p$:

   • &p->i等于结构体的地址，i为int类型它的$K$等于4，所以编译器必须保证$x_p$是4的倍数
   • &p->c的地址等于$x_p+4$， 它的K等于1，地址肯定是1的倍数，所以不用对齐
   • &p->j的地址等于$x_p+5$, 它的$K$是4, 地址不是4的倍数，所以需要对齐，需要补齐3个字节, 地址变为$x_p+8$, 地址是4的倍数
   • 所以对齐后整个结构体的大小sizeof(s1)变成了12个字节

3. 结构体的尾末也需要对齐。考虑下面的结构体：

   struct s2 {
   int i;
   int j;
   char c;
   };
   
   struct s2 a;
   struct s2* p = &;
   

   struct s2和struct s1相比，调换了成员c和j的顺序。假设p的地址为$x_p$, 如果按照之前的思路计算:

   • &p->i等于结构体的地址，p->i的$K$等于4，所以编译器必须保证$x_p$是4的倍数。
   • &p->j的地址等于$x_p$+4，它的$K$等于4，$x_p+4$肯定也是4的倍数，所以也不用对齐。
   • &p->c的地址等于$x_p+8$，它的$K$等于1，地址肯定是1的倍数，所以不用对齐。
   • 那么sizeof(s2) = 9
     但是测试sizeof(s2)依然是12个字节，这是为什么呢？对于单个结构体9个字节以及能够满足对齐了，但是如果是结构体数组呢，考虑如下定义：

   struct s2 d[4];
   

   如果不对结构体末尾进行对齐，假设d的地址位$x_d$，首先$x_d$肯定是4的倍数，那么d[1]的地址就是$x_d$ + sizeof(s2) = $x_d + 9$，那么肯定不满足d[i]->i的对齐规则，因为它的$K$是4，而$x_d$不是4的倍数。所以sizeof(s2)就必须是12个字节，也就是需要在末尾补齐3个字节

4. 可以看出来要满足元素开头地址是其$K$的整数倍。不仅需要填充字节还需要保证结构体的首字节地址也必须满足某些规则，也就是不单需要考虑单个结构体的情况，还需要考虑连续多个结构体的情况。为了得到更通用的规则，我们定义一个通用模型（先假设结构体元素都是简单元素）：

   // T1, T2, ..., Tk都是简单类型，非数组和结构体的复合类型
   struct sc {
       T1 x1;
       T2 x2;
       ...
       Tn xn;
       ...
   }
   
   struct sc c;
   struct sc ac[N];
   

   假struct sc c的地址位$x_c$，任意成员xn相对于$x_c$的偏移位$N$，Tn类型的$K$值为$K_n$, 结构体的大小为$SizeC$, 结构体已经对齐，那么：

   • 先考虑单个结构体的情况，对于任意成员xn，有&c.xn = $x_c + N$, 那么$x_c + N$一定是$K_n$的n整数倍。当$N$是0的时候，表示第一个元素的地址，也意味着$x_c$一定是是第一个元素$K$值的整数倍
   • 在考虑结构体数组，对于索引为i的结构体ac[i]，其任意成员xn，有&ac[i].xn = $x_c + i*Sizec + N$, 因为$x_c + N$一定是$K_n$的整数倍，所以$i*sizec$也一定是$K_n$的整数倍意味者$Sizec$也必须是$K_n$的整数倍(i=1时)。因为$K_n$可以结构体的任意元素，所以$Sizec$必须是所有元素$K$值的整数倍。而$K_n$的取值范围是{1, 2, 4, 8}，当xn是struct sc中最大的成员时，$K_n$也是最大的$K$值，$Sizec$是$K_n$的整数倍，也就意味着$ Sizec$一定是其他元素的整数倍

5. 还有一个很有意思的事情。假设下面一个结构体：

   struct St{
       char a;
       int b;
   } s;
   

   假设结构体s的其实地址为$X_S$如果让画出内存布局，我相信第一反应(包括很多网上的文章)都是像下面那样：

   

   但是上述布局都是默认内存的起始地址是0或者4的倍数。但是按照我们之前的推到，只是要求$X_S$是第一个成员$K$的整数倍（第一个元素位char，K值为1），或者$X_S+N$是第n个成员xn的$K_n$的整数倍即可，没有要求$X_S$是$K_n$的整数倍，如果起始地址是3呢？那么内存布局是怎么样了，按照前面的规则，&s.b的地址刚好是4，所以不用补齐，此时结构体的大小是5，但是还必须是成员的最大$K$值(对于struct St为4)的整数倍,所以结构体大小必须为8， 也就是需要早尾部填充3个字节，按照这个推出内存布局如下：

这种布局一样满足所有的规则。但是经过实际的测试发现编译器位结构体首地址分配的是结构体最大$K$值的整数倍（比结构体struct St的首地址就是4的倍数），也就是实际上确实第一种内存布局方式（但是暂时还不清楚原因是什么，也没有google到)。

当起始地址为1的时候也是同理，就不推导了:

当起始地址为2的时候：

可以看到如果任由起始地址任意的话，可以看到有4种可能，如果把$int$替换成$long$就会有8种情况，所以可能是为了统一，才规定首地址必须是最大成员$K$值的倍数把。

1. 对于结构体嵌套来说，内部结构体的成员是由他自己的保证对齐的，父结构体唯一需要保证的就是结构体的起始地址是子结构体里最大$K$值的整数倍，这样它内部的成员也肯定是对齐的。也可以理解为结构体的$K$值，就是其内部最大成员的$K$值

2. 对于结构体元素是数组来说。起始数组也可以看做一个所有成员类型都相同的结构体，其$K$值就是成员类型的K值。所以只要保证数组首地址是其$K$值整数倍就行

3. 还有最后一条规则，系统可以通过指令

   #pragma pack(N)
   

   指定系统对齐的字节（最大$K$值）位$N$, 如果指定了，那么一个元素的$K$值就变成了：

   K=min(K, N)=\left\{ K, \quad K \le N \\ \end{aligned} struct S { long b; } - 结构体首地址必须$min(N, Kmax)$的整数倍 - 数组的$K$值就是其成员类型的$K$值(用于结构体成员是数组) struct p1 { char c; // 1个字节 int j; // 4个字节 // Kmax=4, 为了保证结构体大小是Kmax的倍数，需要补3个字节 short i; // 2个字节 long j; // 8个字节 // Kmax=8, 为了保证结构体大小是Kmax的倍数，需要补7个字节 short w[3]; // 6个字节 // kmax=2, 为了保证结构体大小是2的倍数，需要补1个字节 struct p3 a[2]; // 20个字节，K=2 struct p2 t; // 自身24个字节, K=8 }; // 20+4+24=48字节 struct p5 { // Kb=8, 补齐6字节 int c; // 4个字节 }; // 2+6+8+4+4=24个字节 #pragma pack(4) // 从这儿开始设置系统对齐位4字节 short a; // 2个字节, K=2 long b; // 8个字节, K=min(8, 4)=4 // Kmax=4 不用补齐