填充与对齐——指定变量的地址偏移【转】

转自 http://hi.baidu.com/bai_yechuang/item/34bff9ba6dff3cdf84dd79c0

 

前言
    由于填充与对齐与硬件架构有很大关系，所以填充与对齐在一般的编程工作中很少涉及，但网站还是有不少关于对齐的技术文章。坦白的说，我并不认为这些文章抓住了要点，或者说，即使那些作者自己抓住了要点但并没有描述清楚。也许我看的这方面文章不多，但我想就这个问题写一篇清晰而简单的文章，结合我的理解和经验，用逻辑的思路描述出来。
    大家看到我的标题是“填充与对齐”，我就是想明确一个观点，即使它们二者充满了联系，但填充与对齐是不同的。这时候有些人可能也觉得填充与对齐不同，但当自己讲到对齐问题，就又和填充混到一起了。
    填充和对齐存在的根本原因是硬件架构的要求，让我们先从硬件架构的要求说起。
    计算机主要的架构就分为两类，复杂指令集计算机（CISC）和精简指令集计算机（RISC）。CISC最有代表性的架构就是x86，RISC最有代表性的架构就是ARM。不管是什么架构，对要访问的一定长度的数据的地址是有要求的，比如要访问一个32位的整数，那么这个数据必须（最好）存储在以4字节（32/8=4）对齐的地方。一般来说，RISC对对齐要求的更严格些，非对齐访问可能会带来性能上的损失。这对程序在不同架构间移植非常重要，因为它极有可能导致你的程序崩溃。
    不要问我为什么硬件要这么要求，你可以询问专业的硬件工程师，但是现在记住：我们必须对齐！

什么是对齐
    如果一段长度为n字节的数据d所存放的地址m能被n整除，那么d就是对齐的。可见，数据的对齐和自身长度和地址有关。在32位机器上，对于short类型的数据来说，将他们存放在偶数地址上，都是对齐的，否则奇数地址都是非对齐；对于int类型的数据来说，要将他们存放在能被4整除的地址上，才是对齐的。

非对齐访问的程序表现
    程序上怎么描述非对齐访问？让我们看看下面小段程序：

int *p;
//do some pointer offset
//…
int i = *p; //access

    *p就是访问数据，我们知道*p就是要通过指向int型数据的指针p获取数据，p中存的是数据的地址，如果p本身的值不是能被4整除的，那么用*p来访问int型数据就是非法的。具体操作系统的表现因机而异。

结构的填充
    一般来说，我们现在的程序上对齐都由编译器来完成，因为我们根本无法确保数据放在什么地方。因为我们都运作在虚拟地址空间上。对于普通的基本数据类型，实现这点不是很难。对于复合结构呢？我们需要给结构设计一个结构。
    当我们定义结构时，实际我们并没有给结构指定存储，我们只是在设计一个模板，一个存储的模板，让编译器帮助我们当我们需要结构变量时，编译器会自动按照我们设计好的存储模板放置结构的成员。
    按照前面说的对齐的定义，要使*p(p指向结构变量)不出错，p的值必须是结构大小的整数倍。由于p本身的值由编译器指定，那么焦点就落在了结构的大小上了。由于我们定义结构时只是在定义一个模板而真正结构变量的地址由编译器保证，那么我们只需考虑结构成员相对偏移是符合对齐标准就行了。

struct _Struct
…{
int i;
char c;
short s;
char c2;
};

    我们先来看第一个结构成员i，它在结构模板中相对偏移是0，也就是说只要结构对齐了（结构对齐的值肯定大于int）那么i肯定是对齐的。这里补说一个概念——自对齐，每个类型都有它的自对齐，对于char它的自对齐就是1，对于int它的自对齐就是4，依次推理。只要数据所在地址是该数据自对齐的整数倍，那该数据肯定是对齐的。结构也是有自对齐的，至于如何计算，我们后面再讲。我们接着偏移往后讲。
    由于存在访问结构成员的可能性，所以结构的成员也必须是对齐的。这个对齐很容易做到，因为结构内的成员都是根据相对偏移来做的，以0为基准。我们继续看前面定义的结构。i必然是对齐的，它开始存放的地址偏移为0，然后它占用了4个字节的自身长度的存储。c好养活，任何地址它都可以对齐，它也只占用了一个字节的存储，挨着i放。s怎么放呢？它为了对齐不能紧挨着c放，因为紧挨着c的地址偏移是5，显然不能被short类型的自对齐长度2整除，所以没办法，s需要向后挪一个字节开始存放，并从此向后占用2个字节的存储。问题出来了，s向后挪了一个字节，它与c之间没有存储任何有效数据的地方怎么办呢？这个地方会在生成结构变量时由编译器随机生成数据填补空间。我们把这样的方式叫做结构填充(pad)，把填充的数据叫做填充数据(pading data)。接下来，数据c2也挨着s放，c2本身占用1个字节的存储。问题又出现了，c2后面还需要填充吗？填充多少?这两个问题非常关键，因为他们决定了结构的大小，这两个问题确定不下来，编译器就无法为我们生成结构变量。编译器很生气，后果很严重。

结构的自对齐
    根据我们解决基本数据类型的经验，我们只需要给结构规定一个自对齐就可以解决问题，它该填充多少就填充多少。那么结构的自对齐是如何确定的呢？结构的自对齐其实完全取决于它的成员。结构的自对齐取决于其成员的自对齐，结构的自对齐值等于其成员的自对齐的最大值。比如，前面定义的结构，结构成员自对齐最大的就是int了（等于4），那么结构的自对齐就是4。假如结构中有一double变量（长度和自对齐为8），那结构的自对齐就是8。前面的最后一个问题终于得到了解决，根据自对齐理论，前面的结构需要根据自身的自对齐进行补齐，所以后面还需要部3字节。这样整个结构的大小就确定了下来，回想一下前面说的，我们做个简单的加法：4+1+1+2+1+3=12（我为什么这么写？这些数字分别代表了什么意思？）。

结构的最大对齐及其控制
    结构本身的大小我们已经通过规范能够确定下来，当我们定义结构变量时，编译器就会根据其大小自动帮助我们将结构放置在对齐的合适的位置。是不是每个结构变量我们都需要按照结构的自对齐补齐呢？
    有时候我们需要生成一些紧凑的结构（compact structure），这种情况在写底层程序时比较常见，比如我们通过定义一个与硬件数据相符的程序结构，方便与硬件交换信息。那么这个时候结构本身的定义重点是在与硬件规范相符，而不是由编译器损益分配。这点和结构变量的对齐没关系，我们是说通过把结构内部变量紧缩排列，以达到符合硬件规范或缩减存储占用的目的，这个确实和结构的对齐没关系。
    VC（不是指风投也不是指维生素）为我们提供了一个机制让我们可以控制结构的内部排列——那就是结构最大对齐，也叫结构成员对齐，我个人更倾向于前者的叫法。结构最大对齐和结构自对齐是与结构对齐有关的最重要的两个属性。通过调整结构最大对齐可以调用结构最后的补齐甚至成员的排列。
    调整结构最大对齐有两种方式：一种是静态的；一种是动态的。静态就是（VC6环境下）Alt+F7调出工程设置C/C++选项卡，Code Generation类别，Structure member alignment选项；动态就是利用编译器指令#pragma pack(n)在程序中动态设置，n就是结构最大对齐。
    当然还有堆栈式用法，请参考MSDN。
不光最后的补齐受制于结构最大对齐，中间结构成员间的填充也受制于它。比如：
struct _Struct
…{
char c;
int i;
char c2;
};
    按照我们前面的里面这个结构的大小sizeof(_Struct)等于12。但我们这里动态给它设置结构最大对齐（和静态方式效果是一样的），代码如下：
#pragma pack(2)
struct _Struct
…{
char c;
int i;
char c2;
};
    大家猜猜该结构大小是多少？本来结构的自对齐是4（等于i的自对齐），但现在的结构最大对齐才是2，c与i之间还会按照以前的规则来填充吗？c2后面还会按照结构自对齐来补齐吗？答案就像结构最大对齐的名字一样，它是一种限制，只要能限制得了你（小于结构自对齐），它还真要亮亮它的剑。比如这个结构，c与i之间本来是应该编译器帮我们自动填充3个字节的，现在不行了，人家结构最大对齐发话了，最大按2对齐，这样c与i之间就只能填充1个字节，同理，c2后面也只能补一个字节。最终结构的大小为：1+1+4+1+1=8个字节。这个“万恶”的结构最大对齐。

结构的对齐
    就像文章开始时说的，对齐和填充最容易混淆，主要是术语上的含糊导致理解上的模糊。经过前面一大段的说明，你是否对对齐有点模糊了呢？我现在就把它提出来说。
    其实，我们前面就几乎没说对齐的问题，说的都是填充！你还记得前面我说过一句话，对齐默认情况下是由编译器保证的，包括基本变量、结构变量等。这样的话，我们说的自对齐、最大对齐实际上都是填充的概念。真正的对齐是什么概念？结合最初我们对对齐的定义，我们不难得出，真正的对齐就是要我们有控制编译器放置变量位置的能力。
    VC（2005）为我们提供了这样一个机制，一个编译器指令让我们控制变量的对齐：__declspec(align(n))
    在具体解释这个指令如何使用前，我希望先说一下，为什么对齐会影响填充。其实前面的解释也已经有了隐隐约约的印象。对于基本类型变量，指定了对齐，“根本”就没有填充的问题，它只占用自己的自然长度，而对于结构这样的复合类型，就有问题了。我们用归谬法来说明问题。假设指定对齐只管存放结构变量的首地址，而不管其填充，尤其是补齐时填充，那么当你要生成结构数组时，编译器就会毫无办法，因为它不知道结构的大小。不管什么情况，即使有多种约束，但编译时，结构的大小必须是确定的。
    让我们看看对齐指令（__declspec(align(n))）对结构大小的影响。如：
struct __declspec(align(16)) _Struct
…{
int a;
};
    这里没有动态利用pragma指令设置结构最大对齐，那么就是说结构的最大对齐采用的是默认的静态配置的8字节。结构定义时，我们通过对齐指令定义了其对齐为16字节，也就是说它的放置地址肯定是能被16整除的，再加上要解决其他问题（数组排列）还需要对结构进行补齐填充。到底填多少呢？我们可以这么理解，开始阶段结构最大对齐和结构自对齐他们经过商量，达成协议根据4字节对结构进行填充，对齐指令来了后，发现结构的对齐不符合自己的要求，就按照自己的设置16字节对结构进行补齐填充，最终结构末端被填充了16-4=12字节。可以说，结构填充是个软蛋，谁都可以欺负它，当然最终还是按照实力强（对齐数值大）的规矩办。所以最终上面结构的大小是16字节。
    那对齐指令对结构成员有什么影响呢？让我们看看下面这个例子：
struct _Struct
…{
char c;
int __declspec(align(8)) i;
short s;
};
    我们知道结构的自对齐和基本类型的自对齐是对应的，那这里对基本类型的对齐进行设置和前面对结构对齐进行设置有什么联系呢？其实是一回事。对于基本类型，不管是全局的，还是结构成员，还是将其自对齐和对齐指令设置的对齐进行比较，最终将数据挪到符合要求的地方。所以像结构中成员i的偏移地址就是8而非原来的自对齐4。对齐指令还是厉害啊。
    对于这个结构的大小，就需要结合我们开始讲的原理了，既然成员i的对齐已经成了8，那么它最终必将影响结构的自对齐，也就是说最终结构的自对齐就等于结构中成员的最大对齐即8。所以最终结构补齐填充还是要按照结构的自对齐来办，所以这个结构的最终大小为1+7+4+2+2=16（我怎么计算的？）。有兴趣的可以试试在全局定义一个变量，如：
char __declspec(align(16)) global_c;
printf(“%08X “, &global_c);
    看看16进制的地址最后一位是不是为0。

总结
    本文旨在通过从原理上和逻辑上的描述，帮助理解，加深记忆。当然为了我叙述的准确我还是做了试验的，一些显而易见的我就偷了懒。各位可以对上面的原理进行测试验证，欢迎批评指正。有兴趣的，也可以参考其他有关填充与对齐的文章，但我觉得还是我描述的最清晰了，如果有不清晰的，那就请告诉我，我会使它更清晰。

==================================================================================================

编译器默认按处理器字长对齐.否则使用紧缩.但很多处理器上使用紧缩方式将导致core error!X86是少数支持直接读取非对齐数据的处理器之一.

"对齐"是RISC计算机的"通病".所谓对齐,就是一个变量不会跨越2个字.为啥?这跟RISC的取指方式有关,RISC每次读取存储器,都是一个完整的字长,换个说法就是,每次取数据的首地址必为4的倍数,一次取4个字节.如果变量未对齐,则该变量会分散在两个字中,取数时势必只能取回该变量的一部分,于是出错.X86由于设计特殊,可以从任意地址开始读取一个字长宽度而不必非得从4的倍数地址开始,所以无需对齐.

对齐原则为:
单字节变量无需对齐,可放在任何地址
双字节变量起始地址为2的倍数
4字节变量首地址为4的倍数

struct {
u8    偏移量:0
u8    偏移量:1 ---- 单字节变量的首地址可以为任意位置
}

struct {
u8    偏移量:0
u16   偏移量:2 ---- 双字节变量的首地址必须为2的倍数,所以该成员之前空出一字节,偏移量1的单元被浪费了.
}

struct {
u8    偏移量:0
u32   偏移量:4 ---- 4字节变量的首地址必须为4的倍数,所以该成员之前空出3字节,偏移量1~3的单元都被浪费了.
}