Linux kernel学习-内存寻址

近日在看 Understanding the Linux kernel(慢慢啃E文原版,以下简称 ULK),这本书虽然已经是第三版了,但它基于的 Linux kernel 版本却不是很新,现在 Linux kernel 都已经出到 3.4 版本了,这本书还是基于 2.6.11 的 kernel,不得不说 Linux kernel 的更迭速度太快了。

下面准备以我正在用的 2.6.34 版本的 kernel 为基础进行学习,这本书中不对应的地方我会尽量找到新 kernel 中的实现,并尽量自己做个了解,日后的相同日志如无意外也基于 2.6.34 版本 Linux kernel。

首先已完成第一章:Introduction(这一章没有 Linux kernel 代码),来到第二章 Memory Addressing,开始是介绍逻辑地址、线性地址、物理地址的对应关系,虽然之前用汇编写过 Linux 的 bootloader,用到过实模式和保护模式,但对 GDT、LDT 的概念并没有深入了解过。这一章开篇就介绍了 Intel 80X86 硬件上内存分段的实现,包括段选择子,段寄存器,段描述符。

段式内存管理

每个内存段由 8 个字节的段描述符来表示段的特征。段描述符被存储在 GDT 或者 LDT 中。内存中 GDT 的地址和大小包含在 gdtr 控制寄存器中,LDT 的地址和大小包含在 ldtr 控制寄存器中。段寄存器的高 13 位为段描述符在 GDT 或者 LDT 中的索引,GDT 或者 LDT 结构中包含基地址、段长度等信息。通过检查指令地址和段长度并确定没有越界以及权限是否正确之后,由于 线性地址 = 段基指 + 偏移地址,GDT 或者 LDT 中的基地址加上指令中的偏移量就可以得到需要的线性地址。

备注:由于每个进程都可以有 LDT,而 GDT 只有一个,为满足需求 Intel 的做法是将 LDT 嵌套在 GDT 表中。

Linux kernel 中的内存分段

Linux中所有进程使用相同的段寄存器值,因此它们的线性地址集也是相同的,不管在用户模式还是内核模式,都可以使用相同的逻辑地址,32位 kernel下为 4G 的地址空间。

ULK 中介绍的 user code、user data、kernel code、kernel data 这四个段对应的段选择子的宏为:__USER_CS、__USER_DS、__KERNEL_CS、__KERNEL_DS,2.6.11 中这4个宏定义在 include/asm-i386/segment.h 头文件中,2.6.34 中已经挪到 arch/x86/include/asm/segment.h 里,因为 2.6.34 中 i386 和 x86_64 的代码已经尽可能的合并到 x86 目录中,而不像老版本的代码那样弄成两个目录。定义如下:

#define __KERNEL_CS	(GDT_ENTRY_KERNEL_CS*8)
#define __KERNEL_DS	(GDT_ENTRY_KERNEL_DS*8)
#define __USER_DS	(GDT_ENTRY_DEFAULT_USER_DS*8+3)
#define __USER_CS	(GDT_ENTRY_DEFAULT_USER_CS*8+3)

下面是 Linux kernel GDT 的实现:

由于 kernel 中每个内核需要有一个 GDT,因此就有一个 GDT table,ULK 中说的是存在 cpu_gdt_table 中,GDT 的地址和大小存在 cpu_gdt_descr 中,2.6.11 kernel 里都是放在 arch/i386/kernel/head.S,使用的地方:

extern struct desc_struct cpu_gdt_table[GDT_ENTRIES];
DECLARE_PER_CPU(struct desc_struct, cpu_gdt_table[GDT_ENTRIES]);

struct Xgt_desc_struct {
	unsigned short size;
	unsigned long address __attribute__((packed));
	unsigned short pad;
} __attribute__ ((packed));

extern struct Xgt_desc_struct idt_descr, cpu_gdt_descr[NR_CPUS];

到了 2.6.34 中已经改为:

struct gdt_page {
	struct desc_struct gdt[GDT_ENTRIES];
} __attribute__((aligned(PAGE_SIZE)));
DECLARE_PER_CPU_PAGE_ALIGNED(struct gdt_page, gdt_page);

static inline struct desc_struct *get_cpu_gdt_table(unsigned int cpu)
{
	return per_cpu(gdt_page, cpu).gdt;
}

可以看到 2.6.34 中去掉了原来的 cpu_gdt_table 变量(详见 kernel commit bf50467204b435421d8de33ad080fa46c6f3d50b),新增了一个 gdt_page 结构存放 GDT table,而且提供 get_cpu_gdt_table 函数取得某个 CPU 的 GDT。cpu_gdt_descr 也已去掉,新增了 desc_ptr 结构存放每个 CPU 的 GDT 信息,cpu_gdt_descr 也改为 early_gdt_descr。

struct desc_ptr {
	unsigned short size;
	unsigned long address;
} __attribute__((packed)) ;

看下简单看下新的切换 GDT 的实现:

/*
 * Current gdt points %fs at the "master" per-cpu area: after this,
 * it's on the real one.
 */
void switch_to_new_gdt(int cpu)
{
	struct desc_ptr gdt_descr;

	gdt_descr.address = (long)get_cpu_gdt_table(cpu);
	gdt_descr.size = GDT_SIZE - 1;
	load_gdt(&gdt_descr);
	/* Reload the per-cpu base */

	load_percpu_segment(cpu);
}

load_gdt 最终调用 lgdt 汇编指令。

页式内存管理

Intel 从 80386 开始支持页式内存管理,页单元将线性地址翻译为物理地址。当 CR0 控制寄存器中的 PG 位置为 1 时,启动分页管理功能,为 0 时,禁止分页管理功能,并且把线性地址作物理地址使用。

32 位线性地址的高 10 位为页表目录的下标(指向页表),中间 10 位为页表的下标(指向页面),低 12 位为该地址在页面(通常大小为 4 KB)中的偏移量,这样的二层寻址设计主要为了减少页表本身所占用的内存,由于页表目录和页表都为 10 位,因此都最多包含 1024 个项。正在使用的页表目录的物理地址存在 cr3 控制寄存器中。

在 32 位大小的页表目录(页表)的结构中,其高 20 位为页表(页面)基地址的高 20 位,其它的 flag 中包含一个 Present 标志,如果该值为 1,表示指向的页面或者页表在内存中,如果为 0,页单元会将线性地址存在 cr2 控制寄存器中,并产生异常号 14: page fault。

页表目录结构中另外有一个 Page Size 标志(页表结构没有此标志),如果设为 1,则页面大小可以为 2MB 或者 4MB,这样可以跳过页表转换,将 cr4 寄存器的 PSE 标志启用即可启用大页面支持,此时 32 位线程地址由高 10 位页表目录下标和低 22 位的偏移量。

为满足寻址超过 4GB 的需求,Intel 从 Pentium Pro 处理器开始,将处理器的地址引脚数量由原来的 32 个提升为 36 个,处理器的寻址空间也从 4GB 增到 64GB,并增加 PAE 页面机制(设置 cr4 寄存器的 PAE 标志启用):64G内存可以划分为 2^24 个页面,页表中的基地址由 20 位增为 24 位,页表结构的大小由 32 位增为 64 位,增加 PDDT 表从而使用三层寻址设计来解释 32 位的线性地址等等。PAE 机制稍显复杂,而且由于仍然使用 32 位线性地址,因此对于应用程序来说,仍然无法使用超过 4GB 的地址空间,64GB 只是对于 kernel 而言的。

顺带说下不同的 64 位架构下的页面寻址级别,见下表,可以看到常用的 x86_64 架构只用了 48 位的线性地址空间,但也达到了 256TB 咯 ^_^

64位架构的页面级别

硬件 cache

由于现在 CPU 速度太快,频率已经动辄多少 GHz,而相对的 DRAM 内存频率就慢很多,而且 DRAM 由于设计上电容存在不可避免的漏电原因,DRAM 的数据只能保持很短的时间,必须隔一段时间就刷新一次,不刷新的话会造成存储的信息丢失;而 SRAM 在加电之后不需要刷新,数据也不会丢失,由于 SRAM 的内部结构明显比 DRAM 复杂,而且由于价格原因不能将容量做的很大,DRAM 常用于 PC 机的内存,而 SRAM 常用于 CPU 的 L1 和 L2、L3 缓存,这时位于 SRAM 和 DRAM 之间的处理器 cache 控制器就应运而生了。

首先 CPU 从 cache 里读取的数据是以数据总线宽度为单位的,而新引入的 cache line 则是cache 和 memory 之间数据传输的最小单元,一般的 cache line size 有 32个字节、64个字节等。cache memory 的大小一般以 cache line size 为单位,可以包含多个 cache line,假设 cache line size 是 32 字节,数据总线宽度是 128 位,一个 cache line 就需要多次的总线操作,为此 x86 可以使用锁总线来保证一个操作序列是原子的。

CPU 访问 RAM 地址时,首先会根据地址判断是否在 cache 中,假设 cache 命中,如果是读操作,cache 控制器从 cache memory 中取得数据传给 CPU 寄存器,RAM 就不被访问以提高性能,如果是写操作,cache 控制器一般都需要实现 write-through 和 write-back 两种缓存策略。对于 L1 cache,大多是 write-through 的(同时写 RAM 和 cache line);L2 cache 则是 write-back 的,只更新 cache line,不会立即写回 memory,只在需要时再更新,而且 cache 控制器一般只在 CPU 得到需要刷新 cache line 的指令时才刷新。反之 cache 未命中时,cache line 中的数据需要写回 memory,如果需要的话,将正确的 cache line 的数据从 RAM 中取出并更新。

如果能提高 CPU 的 cache 命中率,减少 cache 和 memory 之间的数据传输,将会提高系统的性能。

在多处理器环境中,每个处理器都有独立的硬件 cache。因此存在 cache 一致性问题,需要额外的硬件电路同步 cache 内容。

Linux kernel 中默认对所有页面启用 cache,并且都使用 write-back 策略。

TLB(Translation Lookaside Buffers)的作用:

除了通用的硬件 cache 之外,80X86 处理器包含 TLB(Translation Lookaside Buffers)cache 用于提高线性地址转换的速度。某个地址第一次使用时,MMU 将它对应的物理地址填入 TLB 中,下次使用同一地址时就可以从 TLB cache 里取出。TLB 中的内容需要保持与页表的一致,页面目录的物理地址变化时(更新 cr3 寄存器的值),TLB 中的所有内容也会被更新。

另外在多处理器环境中,每个处理器都有自己的 TLB,不过多处理器下的 TLB 是不需要像 CPU cache 那样做同步,因为某个进程对于不同的处理器的线性地址是相同的。

Linux 内存分页管理

2.6.11 之后的新 Linux kernel 中为了兼容 x86_64 等硬件架构已经将原先的两层页结构改为四层页结构:页全局目录(PGD)、页上级目录(PUD)、页中间目录(PMD)、页表(PT)。这样一个线性地址就被分成了 5 个部分,为了适应不同架构的考虑,这 5 个部分的位长度并没有固定,有的 64 位硬件架构只使用了三层页结构。

对于 32 位又没有 PAE 的架构,两层页结构就已经够了,此时 Linux 将的 PUD、PMD 的长度设为 0 位,为了使同样的代码既可以在 32 位又能在 64 位上运行,Linux 会将 PUD、PMD 的条目数设为 1,并将 PUD、PMD 映射放到 PGD 的合适条目上,PUD 的惟一的条目指向下一级的 PMD,PMD 的惟一的条目指向下一级的 PT,这样可以做到对于 OS 来说还是使用四层页结构。对于 32 位并启用了 PAE 的架构,PGD 对应于原来的 PDPT,PUD 被移除(长度为 0 位),PMD 对应于原来的 页目录,PT 还是对应于原来的页表。

下面这张摘来的图很好的说明了 段式内存管理 和 页式内存管理 的关系(还算简单,没有画出 PGD、PUD、PMD 这种东西):

段式与页式内存管理

每个进程有自己的 PGD 和 页表,当进程发生切换时,当前进程的描述符中就保存了 cr3 寄存器的值。

页表、PMD、PUD、PGD 在 Linux kernel 中分别用 pte_t、pmd_t、pud_t 和 pgd_t 来表示,PAE 启用时这些值为 64 位,否则为 32 位。Linux kernel 提供 pte_clear、set_pte、pte_none、pte_same 等宏(函数)来操作或判断页表的值。

pmd_present 宏根据指定的页或页表是否在内存中而返回 1 或 0。而 pud_present、pgd_present 始终返回 1。需要注意的是 pte_present 宏,当页表结构中 Present 或者 Page Size 标志位为 1 时,pte_present 都返回 1,否则返回 0。由于 Page Size 标志位对于页表没有意义,因此对于一些虽然在内存中但并没有 读/写/执行 权限的 page,kernel 会将其 Present 标志位置为 0 及 Page Size 标志位置为 1,由于 Present 被置为 0,访问这些 page 时将触发 page fault 异常,但这时 kernel 就会根据 Page Size 为 1 而判断出这个异常不是真的由缺页引起的。

pgd_index、pmd_index、pte_index 分别返回指定的线性地址在 PGD、PMD、PT 中映射该线性地址所在项的索引,其它还有一些例如 pte_page、pmd_page、pud_page、pgd_page 这种操作不同种类的 page descriptor 的函数(宏)。

Linux kernel 内存布局

现在的 2.6 bzImage kernel 在启动时一般装载在 0x100000 即 1MB 的内存地址上(2.4 zImage 默认装载在 0x10000 内存地址上,具体请参考 Linux boot protocol - Documentation/x86/boot.txt),因为 1MB 之前的内存被 BIOS 和一些设备使用,这些可以找 BIOS 内存图来参考学习。

kernel 中有 min_low_pfn 变量表示在内存中 kernel 映像之后第一个可用页框的页号,max_pfn 表示最后一个可用页框的页号,max_low_pfn 表示最后一个由 kernel 直接映射的页框的页号(low memory),totalhigh_pages 表示 kernel 不能直接映射的页框数(high memory),highstart_pfn 和 highend_pfn 就比较好理解了。

在 32 位 Linux 中地址空间为4G,0~3G 为用户空间,物理地址的 0~896M 是直接写死的内核空间(即 low memory),大于 896M 的物理地址必须建立映射才能访问,可以通过 alloc_page() 等函数获得对应的 page,大于 896M 的就称为高端内存(high memory),另外剩下 896M~1G 的 128M 空间就用来映射 high memory 的,这段空间包括:

  1. noncontiguous memory area 映射

    从 VMALLOC_OFFSET 到 VMALLOC_END,其中 VMALLOC_OFFSET 距 high memory 8MB,每个被映射的 noncontiguous memory area 中间还要间隔一个页面(4KB);

  2. 映射 persistent kernel mapping

    从 PKMAP_BASE 开始;

  3. 最后用于 fix-mapped linear address

    见下面的固定映射的说明。

所有进程从 3GB 到 4GB 的虚拟空间都是一样的,Linux 以此方式让内核态进程共享代码段和数据段。

3GB(0xC0000000)就是物理地址与虚拟地址之间的位移量,在 Linux kernel 代码中就叫做 PAGE_OFFSET。Linux kernel 提供 __pa 宏将从 PAGE_OFFSET 开始的线性地址转换为对应的物理地址,__va 则做相反的操作。

备注:Linux kernel 中有配置选项可以将 用户/内核 空间划分为分别 2G,64位 Linux 由于不存在 4G 地址空间限制不存在高端内存。

下面以一个编译 32 位 Linux kernel 时产生的 System.map 符号表文件说明下 kernel 在内存中的使用情况,在  System.map 里可以看到下面几个符号:

c1000000 T _text
c131bab6 T _etext
c131d000 R __start_rodata
c143c000 R __end_rodata
c143c000 D _sdata
c1469f40 D _edata
c151a000 B __bss_start
c1585154 B __bss_stop
c16ab000 A _end

_text 表示 kernel code 开始处,这个在符号表就被链接到 0xc0000000 + 0x100000,这样所有的符号地址 = 0xC0000000 + 符号,_etext 表示 kernel code 结束处,之后是 rodata 只读数据段的开始 __start_rodata 和结束位置 __end_rodata;已初始化的 kernel data 在 _sdata 开始并结束于 _edata 位置,紧接着是未初始化的 kernel data(BSS),开始于 __bss_start 结束于 __bss_stop,通常 System.map 的最后都是 _end。(注意:这里看到的 kernel ELF 段分布和 ULK 说的并不完全一样,ULK 说的相对比较笼统)

Linux kernel 内存映射

PGD 被分成了两部分,第一部分表项映射的线性地址小于 0xc0000000 (PGD 共 1024 项,在 PAE 未启用时是前 768 项,PAE 启用时是前 3 项),具体大小依赖特定进程。相反,剩余的表项对所有进程来说都应该是相同的,它们等于 master kernel PGD 的相应表项。

系统在初始化时,kernel 会维护一个 master kernel PGD,初始化之后,这个 master kernel PGD 将不会再被任何进程或者 kernel 线程直接使用,而对于系统中的常规进程的 PGD,最开始的一些 PGD 条目(PAE 禁用时为最开始 768 条,启用时为最开始 3 条)是进程相关的,其它的 PGD 条目则和其它进程一样统一指向对应的 master kernel PGD 中的最高的一些 PGD 条目,master kernel PGD 只相当于参考模型。

kernel 刚被装载到内存时,CPU 还处于实模式,分页功能还未启用,首先 kernel 会创建一个有限的 kernel code 和 data 地址空间、初始页表、以及一些动态数据;然后 kernel 利用这个最小的地址空间完成使用所有 RAM 并正确设置页表。

看看 arch/x86/kernel/head_32.S 中 kernel 临时页表的 AT&T 汇编代码:

page_pde_offset = (__PAGE_OFFSET >> 20);

	movl $pa(__brk_base), %edi
	movl $pa(swapper_pg_dir), %edx
	movl $PTE_IDENT_ATTR, %eax
10:
	leal PDE_IDENT_ATTR(%edi),%ecx		/* Create PDE entry */
	movl %ecx,(%edx)			/* Store identity PDE entry */
	movl %ecx,page_pde_offset(%edx)		/* Store kernel PDE entry */
	addl $4,%edx
	movl $1024, %ecx
11:
	stosl
	addl $0x1000,%eax
	loop 11b
	/*
	 * End condition: we must map up to the end + MAPPING_BEYOND_END.
	 */
	movl $pa(_end) + MAPPING_BEYOND_END + PTE_IDENT_ATTR, %ebp
	cmpl %ebp,%eax
	jb 10b
	addl $__PAGE_OFFSET, %edi
	movl %edi, pa(_brk_end)
	shrl $12, %eax
	movl %eax, pa(max_pfn_mapped)

	/* Do early initialization of the fixmap area */
	movl $pa(swapper_pg_fixmap)+PDE_IDENT_ATTR,%eax
	movl %eax,pa(swapper_pg_dir+0xffc)

// ... 中间代码省略 ... //

/*
 * Enable paging
 */
	movl $pa(swapper_pg_dir),%eax
	movl %eax,%cr3		/* set the page table pointer.. */
	movl %cr0,%eax
	orl  $X86_CR0_PG,%eax
	movl %eax,%cr0		/* ..and set paging (PG) bit */
	ljmp $__BOOT_CS,$1f	/* Clear prefetch and normalize %eip */
1:
	/* Set up the stack pointer */
	lss stack_start,%esp

kernel 临时页表就包含在 swapper_pg_dir 中,最后通过设置 cr3 寄存器启用内存分页管理。master kernel PGD 在 paging_init 中初始化,其中调用 pagetable_init:

#ifdef CONFIG_HIGHMEM
static void __init permanent_kmaps_init(pgd_t *pgd_base)
{
	unsigned long vaddr;
	pgd_t *pgd;
	pud_t *pud;
	pmd_t *pmd;
	pte_t *pte;

	vaddr = PKMAP_BASE;
	page_table_range_init(vaddr, vaddr + PAGE_SIZE*LAST_PKMAP, pgd_base);

	pgd = swapper_pg_dir + pgd_index(vaddr);
	pud = pud_offset(pgd, vaddr);
	pmd = pmd_offset(pud, vaddr);
	pte = pte_offset_kernel(pmd, vaddr);
	pkmap_page_table = pte;
}

#else
static inline void permanent_kmaps_init(pgd_t *pgd_base)
{
}
#endif /* CONFIG_HIGHMEM */

static void __init pagetable_init(void)
{
	pgd_t *pgd_base = swapper_pg_dir;

	permanent_kmaps_init(pgd_base);
}

/*
 * paging_init() sets up the page tables - note that the first 8MB are
 * already mapped by head.S.
 *
 * This routines also unmaps the page at virtual kernel address 0, so
 * that we can trap those pesky NULL-reference errors in the kernel.
 */
void __init paging_init(void)
{
	pagetable_init();

	__flush_tlb_all();

	kmap_init();

	/*
	 * NOTE: at this point the bootmem allocator is fully available.
	 */
	sparse_init();
	zone_sizes_init();
}

如果计算机内存少于 896M,32 位地址就已经足够寻址所有 RAM,就不必要开启 PAE 了。如果内存多于 4GB 且 CPU 支持 PAE,kernel 也已经启用 PAE,则使用三层页结构,并使用大页面以减少页表数。

有关固定映射

kernel 线性地址的 896M 映射系统物理内存,然而至少 128MB 的线性地址总是留作他用,因为内核使用这些线性地址实现 非连续内存分配 和 固定映射的线性地址。

Linux 内核中提供了一段虚拟地址用于固定映射,也就是 fixmap。fixmap 是这样一种机制:提供一些线性地址,在编译时就确定下来,等到 Linux 引导时再为之建立起和物理地址的映射(用 set_fixmap(idx, phys)、set_fixmap_nocache 函数)。fixmap 地址比指针更加好用,dereference 也比普通的指针速度要快,因为普通的指针 dereference 时比 fixmap 地址多一个内存访问,而且 fixmap 在 dereference 时也不需要做检查是否有效的操作。fixmap 地址可以在编译时作为一个常量,只是这个常量在 kernel 启动时被映射。

kernel 能确保在发生上下文切换时 fixmap 的页表项不会从 TLB 中被 flush,这样对它的访问可以始终通过高速缓存。

固定映射的线性地址(fix-mapped linear address)是一个固定的线性地址,它所对应的物理地址不是通过简单的线性转换得到的,而是人为强制指定的。每个固定的线性地址都映射到一块物理内存页。固定映射线性地址能够映射到任何一页物理内存。固定映射线性地址

固定映射线性地址是从整个线性地址空间的最后 4KB 即线性地址 0xfffff000 向低地址进行分配的。在最后 4KB 空间与固定映射线性地址空间的顶端空留一页(未知原因),固定映射线性地址空间前面的地址空间就是 vmalloc 分配的区域,他们之间也空有一页。

固定映射的线性地址基本上是一种类似于 0xffffc000 这样的常量线性地址,其对应的物理地址不必等于线性地址减去 0xc000000,而是通过页表以任意方式建立。因此每个固定映射的线性地址都映射一个物理内存的页框。

每个 fixmap 地址在 kernel 里是放在 enum fixed_addresses 数据结构中的,fix_to_virt 函数用于将 fixmap 在 fixed_addresses 中的索引转换为虚拟地址。fix_to_virt 还是一个 inline 函数,编译时不会产生函数调用代码。

处理硬件 cache 和 TLB

以下措施用于优化硬件cache(L1、L2 cache 等)的命中率:

1) 一个数据结构中使用最频繁的字段被放在数据结构的低偏移量,这样可以在同一个 cache line 里被缓存;
2) 分配很多块数据结构时,kernel 会尝试将它们分别存在 memory 中以使所有 cache line 都能被均匀使用。

80x86 处理器会自动处理 cache 同步,Linux kernel 只对其它没有同步 cache 操作的处理器单独做 cache flushing。

Linux 提供了一些在页表变化时 flush TLB 的函数,例如 flush_tlb(常用于进程切换时)、flush_tlb_all(常用于更新 kernel 页表项时) 等。

到此 ULK 的内存寻址部分结束,本文只是我个人看 ULK 时的认识和查找到的一些总结,这算是我所写的日志里花的时间最长的一篇(从 5月22日 写到 5月26日),花的心思也很多。本文基于 32 位 Linux kernel 而言,主要着重于 Linux 中最重要的部分之一:内存管理,本文中像 CPU L1、L2 cache 之类的一些信息都是笔者在看 ULK 不太了解时通过在网上查其它的文章而记录下的,因此里面有任何不正确之处欢迎指正 ^_^

发表评论

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

*