内存访问为什么需要地址对齐

1、何为内存对齐

一般对内存对齐的理解为,如果要访问的内存起始地址address,对数据类型的长度进行求模运算,如果结果为0,则本次访问是内存地址对齐的,即:

例如,当CPU需要获取4个连续的整数(int)字节时,如果要获取的数据的起始地址可以被sizeof(int)整除,那么我们称本次访问是内存对齐的访问,反之就是没有内存对齐的访问。
比如,从地址0xf1取4个字节整数,就是非内存(地址)对齐的访问。

2、数据需要对齐到多少字节

内存与CPU之间的数据传输需要经过cache,当前Intel的通用CPU基本全部是64位,每个cacheline大小为64字节,因此一次内存访问至少可以获取64字节的数据到cache。

那么按照以下针对不同类型的数据的对齐规则进行对齐的话,就可以保证内存的一次访问都在64字节的 cacheline 宽度范围之内:
(1)1字节数据可以在任何位置开始访问(对齐在任何地址)
(2)2字节数据的开始地址是2的倍数,(按2字节对齐)
(3)3-4字节数据的开始地址是4的倍数,(按4字节对齐)
(4)5-8字节数据的开始地址是8的倍数,(按8字节对齐)
(5)9-16字节数据的开始地址是16的倍数,(按16字节对齐)

一个64字节或更大的数据结构或数组的开始地址应该按照64字节边界对齐。

3、为什么需要内存对齐

简单的看来,对于一个64位的CPU,其数据总线宽度为64位,一次拥有取出8个字节数据的能力,理论上cpu应该是可以从任意的内存地址取8个连续字节的,而且是否对齐硬件的设计是相同的(如果内存和CPU都是字节组织的话,那么内存应当可以返回任意地址开始连续的四字节,CPU处理起来也没有任何差异)。
然而,很多cpu并不支持非对齐的内存访问,甚至在访问的时候会发生例外(例如arm架构的某些CPU)。而某些复杂指令集的cpu(比如x86架构),可以完成非对齐的内存访问,然而CPU也不是一次性读出四个字节,而是采取多次读取对齐的内存,然后进行数据拼接,从而实现非对齐数据访问的。如下图:

如果我们的数据存于内存的2-5中,在读取时实际上是先读取0-3,再读取4-7字节,再分别将2-3字节和4-5字节合并,最后得到所需的四字节数据。
那么为什么CPU不直接读取2-5,而是要么不提供支持,要么甚至不惜花大力气执行多次访问再拼接访问非对齐的内存呢(这么做一是增加了访问时间,二是增加了电路的复杂性)?

实际上,访问非对齐内存并没有我们想象的那么“简单”,例如,在一个常见的pc上,内存实际上是有多个内存芯片共同组成的(也就是内存条上那些黑色的内存颗粒)。
为了提高访存的带宽,通常的做法是将数据分开存储,放到不同的芯片上,比如,第0-7bit(第0字节)在芯片0上储存,8-15bit(第1字节)在芯片1上存储,16-23bit(第2字节)在芯片2存储,24-31bit(第3字节)在芯片3上存储,以此类推,如下图:

如果要获取对齐的内存地址0x00处的 4个字节,显然这个时候这四个字节分别存储在4个芯片中,而且都有同样的offset 为0,因此一次就可以获取到的需要的数据。
但如果获取非对齐的内存地址 0x01 处的4个字节,这个时候,前三个字节存储在offset 为0的三个芯片中,第四个字节存储在offset为1的芯片中。在对内存进行访问时,CPU每次只能给出一个offset,也就是说一次访问内存无法取出保存在两个偏移量中的数据,因此需要两次访问内存。

4、CPU的缓存结构

4.1 N-Way Set-Associative

目前常用的64位Intel CPU的缓存cacheline宽度是64字节,也就是说一个cacheline一次可以访问(load/store)64字节的内存单元,这是CPU从内存获取数据的最小数据单元。
为了便于数据查找,一般规定内存数据只能置于缓存的特定区域,Cache的数据放置策略决定了内存中的数据块会拷贝到CPU Cache中的哪个位置上,因为Cache的大小远远小于内存,所以,需要有一种地址关联的算法,能够让内存中的数据可以被映射到Cache中来。当前用的方法叫做N路组相联,英文名是N-Way Set-Associative,采用这种方式时,cacheline被分成 S 个sets,每个set包含N个Way,就是把连续的多个cacheline组成一组,将内存中的数据加载到缓存时,需要先找到对应的组,再在这个组内找到对应的cacheline。
cache的总容量即为 S * N。
根据N值 和S值的不同,可以分为Full-Associative、N-Way Set-Associative或者Direct Mapped。当N为1时,即为Direct Mapped;当S为1时,即为Full-Associative;当二者均不为1时,即为N-Way Set-Associative方式。

通过Linux命令行工具dmidecode –t cache 命令可以看到CPU的各级缓存支持几路组相联,通过lscpu命令可以看到各级缓存大小。cacheline的大小可以通过以下命令得到:

其中indexX表示哪一级缓存,index0表示L1数据缓存,index1表示L1指令缓存,index2表示L2缓存,index3表示L3缓存。

4.2 缓存结构

举例说明,目前Intel通用CPU的L1 Cache基本都是32KB,8-Way Set-associative,cacheline是64B,即:

  • 这32KB被分成 32KB / 64B = 512条 cacheline;
  • 由于是8-way,因此sets的数量为 512 / 8 = 64个;

为了方便对内存地址进行索引,将64位的内存地址分为以下三个区间:

  • offset表示数据在cacheline缓存中的位置。由于cacheline是64位,2 ^ 6 = 64,因此offset占用6位;
  • index表示数据在哪个sets的cacheline中,前面已经计算得到包含64个sets,2 ^ 6 = 64,因此index占用6位;
  • tag表示地址的最高有效位,将对照当前set的所有cacheline(具体是哪个set已经通过index得到)检查在该set中是否包含请求的内存地址,如果包含,表示缓存命名,如果不包含,则表示没命中。tag的长度 = 内存地址的长度 – index的长度 – offset的长度,即64 – 6 – 6 = 52位;

一个cacheline的结构如下:

  • flag bits 表示一些在操作过程中涉及到的标志位;
  • data block存放的就是从内存中获取过来的数据,其大小就是一般常说的cacheline大小,如64B;flag bits和tag占用的空间是不算在64B大小之中的;
  • tag 表示数据块在内存中的地址,但并不是完整地址,而是与上文中的tag对应。

关于flag bits,对于指令缓存来说,只需要一个标志位,即有效标志位(valid bit),表示缓存data block中的数据是否有效;
数据缓存通常要求每个cacheline包含两个标志位,一个有效位(valid bit)和一个脏位(dirty bit)。如果设置了dirty bit,表示关联的cacheline自从内存读取之后已经被更改(“脏”了),也就意味着处理器已经把数据写入该行,且新值还没有写回到内存。
通电时,硬件会将所有缓存中的所有有效位设置为“无效”。有些系统还会在其他时间将有效位设置为“无效”,例如当一个处理器的高速缓存中的多主总线侦听硬件听到来自其他处理器的地址广播时,并意识到本地高速缓存中的某些数据块现在已过时,应将其标记为无效。

5、缓存的匹配

当拿到一个内存地址的时候,先拿出中间的set index中的6bit,打到其属于哪组set。

之后,在该组的8个cacheline中,进行时间复杂度为O(8)的遍历,主要是匹配tag字段。如果匹配上了,表示命中;如果没有匹配到,就是cache miss。
L2 Cache与L3 Cache的算法相同。

6、分配地址对齐的内存

6.1 Cache层级结构

6.2 Cache一致性与伪共享问题

Cache Line 是 CPU 和主存之间数据传输的最小单位。
因此,同一个变量,或者同一行 cacheline,有在多个处理器的本地 Cache 里存在多份拷贝的可能性,因此就存在数据一致性问题。
假设两个处理器 A 和 B,都在各自本地 cacheline 里有同一个变量的拷贝时,此时该 cache line 处于 Shared 状态。当处理器 A 在本地修改了变量,除去把本地变量所属的 cacheline 置为 Modified 状态以外,还必须在另一个处理器 B 读同一个变量前,对该变量所在的 B 处理器本地 Cache Line 发起 Invaidate 操作,标记 B 处理器的那条 Cache Line 为 Invalidate 状态。随后,若处理器 B 在对变量做读写操作时,如果遇到这个标记为 Invalidate 的状态的 cacheline,即会引发 Cache Miss,从而将内存中最新的数据拷贝到 cacheline 里,然后处理器 B 再对此 cacheline 对变量做读写操作。
cacheline 伪共享问题,就是由多个 CPU 上的多个线程同时修改自己的变量引发的。这些变量表面上是不同的变量,但是实际上却存储在同一条 cacheline 里。在这种情况下,由于 Cache 一致性协议,两个处理器都存储有相同的 cacheline 拷贝的前提下,本地 CPU 变量的修改会导致本地 cacheline 变成 Modified 状态,然后在其它共享此 cacheline 的 CPU 上,引发 Cache Line 的 Invaidate 操作,导致 cacheline 变为 Invalidate 状态,从而使 cacheline 再次被访问时,发生本地 Cache Miss,从而伤害到应用的性能。在这种情况下,多个线程在不同的 CPU 上高频反复访问这种 cacheline 伪共享的变量,导致产生大量Cache Miss,从而对性能产生影响。

6.3 获取当前系统的cacheline大小

6.3.1 在命令行获取

(1)

(2)

6.3.2 用C语言实现

6.4 堆内存

Intel 提供了SSE指令用来分配地址对齐的malloc 函数:

这两个函数定义在SSE中。

6.5 栈内存

6.5.1 声明地址对齐的变量

#define CACHELINE 64
#define ____cacheline_aligned __attribute__((__aligned__(CACHELINE)))
该宏是gcc属性,对定义的数据结构做空间对齐,使之起始位置对齐cacheline。

6.5.2 数据结构的两种对齐方式

(1)

这种定义将要求编译器(在内核的SMP配置中)在每个cpu的结构从缓存行边界开始。
编译器会在每一个cpu的struct之后隐含地分配额外的空间,这样下一个cpu的struct也会从缓存行边界开始。

(2)

这种方法是在数据结构中垫上一个缓存行的大小的未使用字节。

6.5.3 示例代码

编译并运行,得到如下结果:

参考

【1】https://blog.csdn.net/ropyn/article/details/6568780
【2】https://stackoverflow.com/questions/3903164/why-misaligned-address-access-incur-2-or-more-accesses
【3】https://coolshell.cn/articles/20793.html
【4】https://yangwang.hk/?p=773
【5】https://en.wikipedia.org/wiki/CPU_cache
【6】https://www.cnblogs.com/diegodu/p/9340243.html

————————————————————

原创文章,转载请注明: 转载自孙希栋的博客

本文链接地址: 《内存访问为什么需要地址对齐》

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Scroll Up