内存对齐

在最近的项目中，我们涉及到了“内存对齐”技术。对于大部分程序员来说，“内存对齐”对他们来说都应该是“透明 的”。“内存对齐”应该是编译器的“管辖范围”。编译器为程序中的每个“数据单元”安排在适当的位置上。但是C语言的一个特点就是太灵活，太强大，它允许 你干预“内存对齐”。如果你想了解更加底层的秘密，“内存对齐”对你就不应该再透明了。

一、内存对齐的原因
大部分的参考资料都是如是说的：
1、平台原因(移植原因)：不是所有的硬件平台都能访问任意地址上的任意数据的；某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。
2、性能原因：数据结构(尤其是栈)应该尽可能地在自然边界上对齐。原因在于，为了访问未对齐的内存，处理器需要作两次内存访问；而对齐的内存访问仅需要一次访问。

二、对齐规则
每个特定平台上的编译器都有自己的默认“对齐系数”(也叫对齐模数)。程序员可以通过预编译命令#pragma pack(n)，n=1,2,4,8,16来改变这一系数，其中的n就是你要指定的“对齐系数”。

规则：
1、数据成员对齐规则：结构(struct)(或联合(union))的数据成员，第一个数据成员放在offset为0的地方，以后每个数据成员的对齐按照#pragma pack指定的数值和这个数据成员自身长度中，比较小的那个进行。
2、结构(或联合)的整体对齐规则：在数据成员完成各自对齐之后，结构(或联合)本身也要进行对齐，对齐将按照#pragma pack指定的数值和结构(或联合)最大数据成员长度中，比较小的那个进行。
3、结合1、2颗推断：当#pragma pack的n值等于或超过所有数据成员长度的时候，这个n值的大小将不产生任何效果。

三、试验
我们通过一系列例子的详细说明来证明这个规则吧!
我试验用的编译器包括GCC 3.4.2和VC6.0的C编译器，平台为Windows XP + Sp2。

我们将用典型的struct对齐来说明。首先我们定义一个struct：
#pragma pack(n) /* n = 1, 2, 4, 8, 16 */
struct test_t {
int a;
char b;
short c;
char d;
};
#pragma pack(n)
首先我们首先确认在试验平台上的各个类型的size，经验证两个编译器的输出均为：
sizeof(char) = 1
sizeof(short) = 2
sizeof(int) = 4

我们的试验过程如下：通过#pragma pack(n)改变“对齐系数”，然后察看sizeof(struct test_t)的值。

1、1字节对齐(#pragma pack(1))
输出结果：sizeof(struct test_t) = 8 [两个编译器输出一致]
分析过程：
1) 成员数据对齐
#pragma pack(1)
struct test_t {
int a;   /* 长度4 < 1 按1对齐；起始offset=0 0%1=0；存放位置区间[0,3] */
char b;   /* 长度1 = 1 按1对齐；起始offset=4 4%1=0；存放位置区间[4] */
short c; /* 长度2 > 1 按1对齐；起始offset=5 5%1=0；存放位置区间[5,6] */
char d;   /* 长度1 = 1 按1对齐；起始offset=7 7%1=0；存放位置区间[7] */
};
#pragma pack()
成员总大小=8

2) 整体对齐
整体对齐系数 = min((max(int,short,char), 1) = 1
整体大小(size)=$(成员总大小) 按 $(整体对齐系数) 圆整 = 8 /* 8%1=0 */ [注1]

2、2字节对齐(#pragma pack(2))
输出结果：sizeof(struct test_t) = 10 [两个编译器输出一致]
分析过程：
1) 成员数据对齐
#pragma pack(2)
struct test_t {
int a;   /* 长度4 > 2 按2对齐；起始offset=0 0%2=0；存放位置区间[0,3] */
char b;   /* 长度1 < 2 按1对齐；起始offset=4 4%1=0；存放位置区间[4] */
short c; /* 长度2 = 2 按2对齐；起始offset=6 6%2=0；存放位置区间[6,7] */
char d;   /* 长度1 < 2 按1对齐；起始offset=8 8%1=0；存放位置区间[8] */
};
#pragma pack()
成员总大小=9

2) 整体对齐
整体对齐系数 = min((max(int,short,char), 2) = 2
整体大小(size)=$(成员总大小) 按 $(整体对齐系数) 圆整 = 10 /* 10%2=0 */

3、4字节对齐(#pragma pack(4))
输出结果：sizeof(struct test_t) = 12 [两个编译器输出一致]
分析过程：
1) 成员数据对齐
#pragma pack(4)
struct test_t {
int a;   /* 长度4 = 4 按4对齐；起始offset=0 0%4=0；存放位置区间[0,3] */
char b;   /* 长度1 < 4 按1对齐；起始offset=4 4%1=0；存放位置区间[4] */
short c; /* 长度2 < 4 按2对齐；起始offset=6 6%2=0；存放位置区间[6,7] */
char d;   /* 长度1 < 4 按1对齐；起始offset=8 8%1=0；存放位置区间[8] */
};
#pragma pack()
成员总大小=9

2) 整体对齐
整体对齐系数 = min((max(int,short,char), 4) = 4
整体大小(size)=$(成员总大小) 按 $(整体对齐系数) 圆整 = 12 /* 12%4=0 */

4、8字节对齐(#pragma pack(8))
输出结果：sizeof(struct test_t) = 12 [两个编译器输出一致]
分析过程：
1) 成员数据对齐
#pragma pack(8)
struct test_t {
int a;   /* 长度4 < 8 按4对齐；起始offset=0 0%4=0；存放位置区间[0,3] */
char b;   /* 长度1 < 8 按1对齐；起始offset=4 4%1=0；存放位置区间[4] */
short c; /* 长度2 < 8 按2对齐；起始offset=6 6%2=0；存放位置区间[6,7] */
char d;   /* 长度1 < 8 按1对齐；起始offset=8 8%1=0；存放位置区间[8] */
};
#pragma pack()
成员总大小=9

2) 整体对齐
整体对齐系数 = min((max(int,short,char), 8) = 4
整体大小(size)=$(成员总大小) 按 $(整体对齐系数) 圆整 = 12 /* 12%4=0 */

5、16字节对齐(#pragma pack(16))
输出结果：sizeof(struct test_t) = 12 [两个编译器输出一致]
分析过程：
1) 成员数据对齐
#pragma pack(16)
struct test_t {
int a;   /* 长度4 < 16 按4对齐；起始offset=0 0%4=0；存放位置区间[0,3] */
char b;   /* 长度1 < 16 按1对齐；起始offset=4 4%1=0；存放位置区间[4] */
short c; /* 长度2 < 16 按2对齐；起始offset=6 6%2=0；存放位置区间[6,7] */
char d;   /* 长度1 < 16 按1对齐；起始offset=8 8%1=0；存放位置区间[8] */
};
#pragma pack()
成员总大小=9

2) 整体对齐
整体对齐系数 = min((max(int,short,char), 16) = 4
整体大小(size)=$(成员总大小) 按 $(整体对齐系数) 圆整 = 12 /* 12%4=0 */

四、结论
8字节和16字节对齐试验证明了“规则”的第3点：“当#pragma pack的n值等于或超过所有数据成员长度的时候，这个n值的大小将不产生任何效果”。另外内存对齐是个很复杂的东西，上面所说的在有些时候也可能不正确。呵呵^_^

[注1]
什么是“圆整”？
举例说明：如上面的8字节对齐中的“整体对齐”，整体大小=9 按 4 圆整 = 12
圆整的过程：从9开始每次加一，看是否能被4整除，这里9，10，11均不能被4整除，到12时可以，则圆整结束。
http://bigwhite.blogbus.com/logs/1347304.html

关于内存对齐的话题，始终是敏感的。稍有不慎，必将闯下大祸！最近项目稍显轻闲，自己给自己安排一天反思和总结一下，突然想到以前写过的一篇'也谈内存对齐'，那篇文章谈的是内存对齐的基本知识以及一些实验的数据，想必很多人看完后，会收获一些东西，但是对内存对齐的应用还是处于懵懂状态，其实大部分时间我们是不会显式的用到'内存对齐的'，但是有些时候我们需要这样做。这里做了一个小例子，希望能给大家以启发。

例子是这样的：我们有一种二进制文件，其中存储了多条经过特定对齐的某种记录格式的数据，我们的任务就是解析出来这些数据，但是我们不知道也没有这 种数据的记录格式结构的定义，但我们不是一无所有，我们有一个表，这个表描述了这个记录格式中有哪些域以及这些域的类型信息，我们还知道的是源数据的对齐 系数。

叙述完问题后，我们来给出一些具体的东西：

二进制文件生成程序：
#pragma pack(1)
struct foo_t {
         int      a;
         char     b[25];
         int      c;
};
#pragma pack()

int main() {
         FILE             *fp      = NULL;
         struct foo_t     foo1     = {12457, "test foo1", 75421};
         struct foo_t     foo2     = {36098, "test foo2", 89063};

         fp = fopen("foo.dat", "wb+");
         if (fp == NULL) {
                 printf("error in open foo.dat!\n");
         }

         fwrite(&foo1, sizeof(foo1), 1, fp);
         fwrite(&foo2, sizeof(foo2), 1, fp);

         fclose(fp);

         return 0;
}

生成的待解析文件：foo.dat，其中有两条记录。

好了，我们的任务已经很明确了，就是正确解析出这两条记录。如果解析程序知道有下面这样的结构体定义：
#pragma pack(1)
struct foo_t {
         int      a;
         char     b[25];
         int      c;
};
#pragma pack()
那这里也就不用说废话了，我们不知道这个结构定义，不过我们通过知道的一些信息可以整理出一个描述该结构定义的一个表：

#define X_CHAR           1
#define X_STRING         2
#define X_INT            3

typedef struct x_fld_info_t {
         char     name[MAX_FIELD_NAME_LEN];
         int      type;
         int      nitems;
         int      offset;
} x_fld_info_t;

x_fld_info_t     cpi_type_info_tab[3] = { /* cpi - composite */
         {"a", X_INT, 1, -1},
         {"b", X_STRING, 25, -1},
         {"c", X_INT, 1, -1}
};

想一想，我们能从文件foo.dat中读出来什么？仅仅是一块数据，每次读多大一块？如何在这块数据中找到相应的域呢？没错，我们需要通过 cpi_type_info_tab这个表信息得出每条foo_t记录的大小，还要得到foo_t中每个域在这块数据中的偏移量，然后根据偏移量和域自身 大小准确获取其内容。

好了终于要用到内存对齐的知识了，其实想想也知道foo.dat的文件生成程序和我们的解析程序可能不在一台机器上，而且完全可能在体系结构不同的 机器上，这样不同体系结构的机器他们的默认对齐系数、字节序都可能不同(这里我们暂不考虑字节序的问题)，我们在文件生成程序那边强制指定对齐系数有利于 解析程序这边的解析。我们要做的就是根据已知的对齐系数和cpi_type_info_tab表中的信息计算出来该结构体在特定对齐系数下的总大小以及其 各个域的偏移量。下面的宏X_ROUND_UP和函数align_cpi_type配合完成了这一工作：

int x_atom_type_size[4] = {
         -1,
         sizeof(char),
         sizeof(char),
         sizeof(int)
};

static int lg2(int k) { /* 这里假设k一定为2的次方^_^ */
         int      i = 0;

         while ((k /= 2) != 0) {
                 i++;
         }
         return i;
}

#define X_ROUND_UP(x, k, rv) do { \
                 unsigned int t = (-1 << k); \
                 (rv) = ((x - t - 1) & t); \
         } while(0)

static void align_cpi_type(x_fld_info_t *tab, int fld_cnt, int force_align_mod, int *size) {
         int      i        = 0;
         int      cur      = 0;
         int      rv       = 0;
         int      max_sz   = 0; /* 复合类型各个域中的最大原子类型的长度, 用于对齐整个结构 */
         int      atom_sz = 0; /* 域的原子类型 */
         int      ali_mod = 0; /* alignment modules */

         /*
          * 对齐各个域
          */
         for (i = 0; i < fld_cnt; i++) {
                 atom_sz = x_atom_type_size[tab[i].type];
                 if (max_sz < atom_sz) {
                         max_sz = atom_sz;
                 }

                 if (atom_sz < modules) {
                         ali_mod = atom_sz;
                 } else {
                         ali_mod = force_align_mod;
                 }

                 X_ROUND_UP(cur, lg2(ali_mod), rv);
                 tab[i].offset = rv;
                 cur += (atom_sz * (tab[i].nitems));
         }

         /*
          * 对齐整个复合类型
          */
         if (max_sz < force_align_mod) {
                 ali_mod = max_sz;
         } else {
                 ali_mod = force_align_mod;
         }

         X_ROUND_UP(cur, lg2(ali_mod), rv);
         (*size) = rv;
}

如果对内存对齐还有疑惑的，可以去看看我的那篇'也谈内存对齐'，再回到这来看align_cpi_type的实现，这里的X_ROUND_UP的算法借自于'' 一书，很好的一本讨论'Computer Arithmetic'的书，里面的很多Knowledge & Tip很有价值。通过align_cpi_type函数我们既得到了结构的大小也得到了结构中各个域的偏移量。根据这些信息我们就可以输出文件 foo.dat中的数据了。

static void output_cpi_mem(x_fld_info_t *tab, int fld_cnt, char *buf)
{
         int      i = 0;
         int      int_tmp = 0;
         char     str_tmp[50]; /* 这里仅是举例, 所以使用了一个固定大小的缓冲区, 实际上需要做一个可动态扩展的缓冲区 */

         for (i = 0; i < fld_cnt; i++) {
                 if (tab[i].type == X_STRING) {
                         memset(str_tmp, 0, sizeof(str_tmp));
                         memcpy(str_tmp, (char*)(buf+(tab[i].offset)), x_atom_type_size[tab[i].type] * (tab[i].nitems));
                         printf("the value of field '%s' is [%s]\n", tab[i].name, str_tmp);
                 } else if (tab[i].type == X_INT) {
                         memcpy(&int_tmp, (char*)(buf+(tab[i].offset)), x_atom_type_size[tab[i].type] * (tab[i].nitems));
                         printf("the value of field '%s' is [%d]\n", tab[i].name, int_tmp);
                 }
         }
}

int main() {
         x_fld_info_t     cpi_type_info_tab[3] = { /* cpi - composite */
                 {"a", X_INT, 1, -1},
                 {"b", X_STRING, 25, -1},
                 {"c", X_INT, 1, -1}
         };

         int      size = 0;
         int      i     = 0;

         align_cpi_type(cpi_type_info_tab, sizeof(cpi_type_info_tab)/sizeof(cpi_type_info_tab[0]), modules, &size);

         /*
          * 从文件foo.dat中读出所有记录
          * 并打印出来
          */
         FILE     *fp      = NULL;
         char     buf[50];

         fp = fopen("foo.dat", "r");
         if (fp == NULL) {
                 printf("error in fopen!\n");
         }

         for (i = 0; i < 2; i++) { /* 这里偷了个懒儿，直接用2这个记录的个数了 */
                 memset(buf, 0, sizeof(buf));
                 fread(buf, size, 1, fp);

                 /*
                  * 通过cpi_type_info_tab中的信息打印出
                  * 各个字段的值
                  */
                 output_cpi_mem(cpi_type_info_tab, 3, buf);
         }

         fclose(fp);

         return 0;
}

执行输出：
the value of field 'a' is [12457]
the value of field 'b' is [test foo1]
the value of field 'c' is [75421]
the value of field 'a' is [36098]
the value of field 'b' is [test foo2]
the value of field 'c' is [89063]

看到这有些人可能还是很糊涂，到底为什么要这么做呢？提示一下：现在我们要解析一存储未知类型数据的文件的记录时，我们只需要这个纪录的一些描述信息即可了，而无需知道那个foo_t的具体定义了。能不能理解就看你自己了。

http://bigwhite.blogbus.com/logs/2006/06/2661330.html