Month: April 2018

严格意义上讲，Linux并不严格区分进程和线程，众所周知，进程是资源分配的基本单位而线程是系统调度的基本单位，但是在Linux中，task_struct作为内核调度的实体，即一个线程，如果其使用的资源完全独立于其他task_struct，那就可以看作一个”进程”，如果其使用的资源完全是另一个task_struct，那就可以看作一个”线程”，如果其使用的资源部分是自己的，部分是其他task_struct的，那就可以看作一个”X程”，扯远了，下图中的task_struct表示一个进程。

当我们malloc一块内存的时候，本质上是调用brk()移动当前进程的堆指针，在内核中的表现为构建相应的虚拟内存结构vm_area_struct，这个vm_area_struct描述了一块虚拟地址空间，其中还保存着相应的权限信息，这些结构构建好之后变使malloc()返回，当用户去写这块分配出来的内存的时候，MMU会发现进程的PT并没有相应的映射表项，进而触发PageFault，内核的PageFault核心处理函数是do_page_fault()，这个函数会检查相应的vm_area_struct权限是否正确，如果检查通过，就会通过buddy分配器(注意不是slab，slab只给内核用)分配相应的内存并修改PT，如此这块虚拟地址空间才真正可用。

根据Memory Hierarchy，系统总是希望将活跃的数据放在更快(通常也更小)的存储介质中来提升系统IO性能，在当代计算机体系中，位于Memory Hierarchy顶端的就是CPU中、负责缓存主存数据的cache，其缓存算法由硬件实现，OS无法插手，但OS可以管理自主存开始剩下的所有的存储介质，基于同样的思想，OS也希望将活跃的数据放在所能控制的最快介质——主存中，将数据从慢介质移动到快介质的Cache replacement policy有很多种，Linux通常使用LRU作为指导思想进行设计，即假设”当前正在使用的有很大可能将来也能用到，而许久不用的将来被用到的可能性很低“。基于这样的思想，Linux中使用Page Fault机制将活跃的数据从Backing Device中缓存到更快的主存中。同样，基于LRU，Linux仍需要将不活跃的数据移出主存，这就是Memory Reclaim——内存回收。

• 

Mapped Page/Anonymous Page

在Linux中，按照Page的background不同将内存页分为两类: Mapped Page和Anonymous Page。Mapped Page即映射页，也可以称之为File Cache、Page Cache，其实质是File-backed Page，file即文件系统中的”file”，比如执行a.out，每个ELF文件的格式头都会记录代码段的位置，内核将代码段映射到(可以理解为mmap)到page中，并赋予其R-X权限，这种Page以File为background，Dirty Flush或Swap Out时就以该位于Backing Device上的File为目标操作，可以看出，对于内核来说，文件就是一块内存。老版本的内核还将Mapped Page区分为两种形式：buffers用于缓存裸设备的数据、cached用于缓存文件系统下文件的数据，不过新版本已经不做区分。Anonymous Page即匿名页，指那些没有明确”文件背景”的page，比如一个进程的Stack、Heap以及COW生成的数据段，这些页在swap out的时候没有一个backed-file供其写入，需要写入swap分区/文件。如果从空间维度考察Swap，Mapped Page和Anonymous Page都是Swap回收的范围

DRAM作为Memory Hierarchy 中除CPU内Cache外最快的一级，对于内核性能来说是稀缺资源，所以Linux内核对于物理内存相关的数据结构设计地十分精巧，比如常见的用于分配内存的buddy、Slab分配器、用于规整内存的KSM、用于快速回收内存的RMAP等等，无论哪种精巧的技术，都离不开本文需要讨论的几个与物理内存管理的基础类：node、zone和page。

• 

node

多CPU的硬件架构可以分为两种：UMA和NUMA，前者由多个CPU共享一个内存控制器，这样主板上的所有内存对于所有的CPU都是一样的，缺点是内存控制器容易称为系统瓶颈。NUMA架构中每个CPU使用自己的DRAM Controller，即每个CPU都有接在自己本地的内存控制下的LOCAL内存区间和接在其他CPU内存控制器下的REMOTE内存，显然，对于任何一个CPU而言，访问LOCAL内核要比访问REMOTE的内存要快很多，这样的设计就造成了地址空间中一个物理地址使用不同的CPU的访问不同，即物理地址空间的不均匀，NUMA架构通常可以更好的发挥硬件性能，是当下服务器的主流架构，缺点是系统对内核的内存管理提出了新的挑战。

Continue reading →

本文主要讨论Linux对物理地址空间的分页机制的实现。

• 

分页机制说来也简单，借助MMU来实现进程虚拟地址空间到物理地址空间的映射，在x86平台中，PGD的基地址存放在CR3寄存器，对于ARM平台，在TIBRx寄存器，每当切换进程上下文的时候，Linux都会将本进程的PGD基地址写入相应的寄存器，如此便更换了虚拟地址到物理地址的映射关系，其产生的结果的就是不同进程中的同一个虚拟地址，经过PageGlobleDentry->PageUpperDentry->PageMiddleDentry->PageTableEntry的映射，找到的是不同的物理页框pfn，也就找到了不同的物理地址。

上图是比较典型的32bit CPU中3级页表模型，在64bit视物理地址总线宽度的不同(eg ARM64采用48bit寻址)可能会采用更多级的页表，但其基本原来都是一样的。

MMU除了要完成相应地址的映射，还要进行权限检查，由于地址映射都是以页为单位的，所以权限检查也是以页为单位的。具体地，每种CPU的MMU支持的权限标志位可能都不一样，以ARM Linux为例，其使用在权限定义在arch/arm/include/asm/pgtable*.h中，包括标记页面是否在主存中的L_PTE_PRESENT、标记页面是否是脏页的L_PTE_DIRTY、以及页面是否可执行的PAGE_SHARED_EXEC等。当Linux触发Page Fault时，就会准备好平台相关的MMU表项结构：映射关系和权限，放在相应的页目录中以供MMU使用。

PHYS_OFFSET，PAGE_OFFSET

这两个宏是系统对于物理地址空间划分很常用的两个宏，由于内核的虚拟地址空间和物理地址空间存在线性映射的关系，通过这两个宏，就可以很快地完成转换

Macro	含义	备注
PHYS_OFFSET	RAM偏移	物理地址空间RAM的起始地址
PAGE_OFFSET	kernel space偏移	虚拟地址空间中内核地址空间的起始地址

pgd_t, pud_t, pmd_t

这几个变量的类型分别是PGD，PUD，PMD的基地址，主要注意的是，作为物理地址，它们的本质是unsigned long, 而不是指针。

*_SHIFT, *_MASK

这两类宏在内存管理也很常见，前者是用于计算相应空间的大小的对数，比如，对于页来说

#define PAGE_SHIFT 12
#define PAGE_SIZE (1<<PAGE_SHIFT)

类似的还有PMD_SHIFT，PUD_SHIFT，PGDIR_SHIFT等。

后者用于计算屏蔽低位的掩码。

#define PAGE_MASK   (~(PAGE_SIZE-1))

ALIGN()

要解释这个宏，就需要看看x&~(2^n -1 )的计算结果。对于一个2的指数，其二进制假设为0x10000，则0x10000 – 1 = 0x01111, ~0x01111 = 0x1111111…0000，可见任何一个数x与该数做”与”运算，低位都会被掩掉，也就是向下对齐的效果，即

#define ALIGN(x,a) (x&~(a-1))

同理，对于向上对齐，我们只需要的使用(x+(a-1))&~(a-1)即可，这就是ALIGN。

ALLIGN(x,a)用于x以a为标准向上对齐的值，a必须是2的次方，定义如下：

#define ALIGN(x,a)              __ALIGN_MASK(x,(typeof(x))(a)-1)
#define __ALIGN_MASK(x,mask)    (((x)+(mask))&~(mask))

CPU的内存空间指由CPU地址总线张成的地址空间，即物理地址空间。这个空间中，借助地址总线，CPU可以进行”字节级”的寻址。

• 

上图是一个主板硬件拓扑的例子(实际开发中用的可能完全不是这个样子，比如全闪主板通常直接从CPU中出SSD控制器)，我们以该图为例说明内存管理的基本概念。

视不同架构的CPU，接入物理地址空间的硬件有所不同。对于ARM等RISC处理器，通常将内存条(物理内存)，和设备、外设控制器一并接入物理地址空间。这样可以令CPU使用统一的方式访问物理内存和设备IO，这种设备IO方式称之为映射IO，此时，物理地址空间可以被看作分成两部分: 物理内存区间和设备IO区间。而在x86体系中，设备IO不占用物理地址空间，intel的CPU为设备单独开辟了16bit的IO空间，在硬件上通过拉低/拉高作为flag的某个引脚或寄存器来区分一个地址是位于内存空间还是IO空间，表现在软件上就是在内核态中使用不同接口函数来操作不同的空间。

对映射IO来说，本质上是CPU将需要访问的地址发给北桥，由北桥决定这个地址是发给DRAM控制器来访问内存，还是将相应的指令发给某个设备。总之，CPU的物理地址空间布局和与之相应的操作方法是BSP级的。

在内核通过启动参数解析了BSP信息之后，CPU看到的就只是一个unified的地址空间，在开启了MMU的情况下，这个地址空间就是虚拟地址空间，否则就是物理地址空间。此外，需要注意的是，低端的DMA引擎通常不能实现对整个DRAM的寻址，这也就是内核将低端内存设置为ZONE_DMA的原因，此外，没有IOMMU的DMA引擎接收一次指令只能将一块连续的内存传递到二级存储介质，而配备了IOMMU的DMA引擎可以实现Scatter/Gatter，即IOMMU负责将DRAM中离散的地址区间映射为DMA引擎中的连续的地址。

• 

其中，CPU与DRAM之间通过MMU连接进而实现虚拟地址到物理地址的转换，而设备通过IOMMU和DRAM连接进而实现IO总线地址到物理地址的转换。