思享工具箱

《内核源码情景分析》（浙大）笔记

摘要：
内核源码情景分析笔记背景1.1x86寻址1.2CinLinux1.3AssemblyinLinux为什么要汇编GNU386汇编存储管理2.1内存管理基本框架2.2地址映射全过程2.3常见数据结构2.4越界访问2.5用户堆栈的扩展2.6物理页的使用和周转2.7物理页面分配2.8页面的定期换出2.9页面的换入2.10内核缓冲区的管理2.10.1专用缓冲区的建立2.10.2缓冲区的分配和释放2.11外部
内核源码情景分析笔记

背景

1.1 x86寻址

8086, 8088, 80186, 80286, 80386, 80486,

  • 实地址模式

8086

段寄存器 CS, DS, SS 和 ES 为16bit
实际地址(20bit) = 内部地址(16bit) + 段寄存器值(16bit) << 4　

  • 保护模式 (段式内存管理)

80386

设计思路: 在保护模式下改变段寄存器的功能, 使其从单纯的基地址变成指向这样的一个数据结构的指针.
涉及的新增寄存器:

  • GDTR (Global Description Table Register)
  • LDTR (Local Description Table Register)

段寄存器的定义也有所变化, 其中高13位为描述表的index,低2位表示特权级别, 第2位(从0开始)表示选用GDTR还是LDTR.
所以具体 段描述地址 = index + GDTR/LDTR指向的基地址

定位段描述地址可获得段描述项(8 byte), 其中定义了基地址(32 bit),段长度(20 bit)以及权限信息.
段单元大小 0 代表1B , 1 代表 4KB.
最大段 (4GB = 4KB * 2^{20}), 所有段寄存器都指向同一个描述项目, 且该项的基地址为零, 使用最长段长,
这时候物理地址和逻辑地址是相同的. 这被成为平坦模式.Flat Mode.

  • 页式管理

在段式内存管理的基础上分页管理, 在段式管理处理后可得线性地址, 80386在把线性地址空间划分为4KB的页面,
每个页面映射到物理空间任意一块4KB区间.
线性地址结构:页目录 10bit + 页面表 10bit + 页内偏移12bit

其中CR3寄存器指向当前页面目录.
从线性地址到物理地址:

  1. 从CR3获取页面目录的基地址
  2. 以线性地址的目录录位段为下标,在目录中取得相应页面表的基地址.
  3. 以线性地址的页面表位段为下标,在所得的页面表取得相应的页面描述项.
  4. 将页面描述项的页面基地址与页内偏移相加得到物理地址.

目录项含有指向页面表的指针4B, 页面表项中则含有一个指向页面起始地址的指针4B.

一个页面可以存储1024个表项 (4KB=1024*4B), 这就是4KB的由来.

由于页面表和页面的起始地址都需要4K边界对齐, 所以这些指针的低12位永为0, 那么余下的12位可以用来放控制信息

PSE(page size extension)机制: 页目录项中的ps位为0代表4KB默认大小, 为1则页面大小为4M那么,
取消页面表, 线性地址的低22位全部用来4M页面内的偏移.

CR0寄存器的最高位PG是页式映射机制的总开关.

PAE(Physical Address Extension)机制, 在CR4寄存器中将PAE位置为1则地址总线的宽度为36位.

1.2 C in Linux

Linux由GNU的C语言编写而成, 所以这里介绍内核中 用到的一些ANSI C技巧.

  • inline and const 从C++借鉴, 其中inline函数相对于宏而言更便于调试,
    在未开启编译优化时inline函数与普通函数一致, 在调试成功后开启优化提高运行效率.

  • 属性描述符 attribute 如 aligned 和 packed等.

    为防止与变量冲突引入等价关键字 __aligin__ , __packed__, __asm__, __volatile__.

  • 一些奇怪的Macro定义:

    • 空定义
      /* include/asm-i386/system.h:14 */
#define prepare_to_switch() do { } while(0)

      为了不同架构有不同实现

    • 执行一次定义
      /* fs/proc/kcore.c:163 */
#define DUMP_WRITE(addr, nr) do {memcpy(bufp, addr, nr); bufp += nr;} while(0)

      为了在没有花括号的if-else语句内正确执行

  • 抽象数据结构类型

    /* include/linux/list.h:16 */
struct lsit_head {
    struct list_head *next, *prev;
 }

实现双向链表

  • 反解析宿主地址
```c
/* mm/page_alloc.c 188*/
page = memlist_entry(cur, struct page, list);
```
```c
/* include/linux/mm.h */
typedef struct page {
	struct list_head list;
	...
}

从cur一个list__head指针换算出page结构的地址

实际实现:

 page = ((struct page*))(cahr*)(curr) - (unsigned long)(&(struct page*)0)->list)));

curr是page结构内部成分list的地址, 思路是通过curr去减去list在page内的偏移量.

1.3 Assembly in Linux

为什么要汇编

  1. 硬件专用指令如inb, outb无法在C中找到对应语句
  2. CPU中的特殊指令如开闭中断,还有后代CPU的扩展指令
  3. 内核中要求效率的操作
  4. 空间有限, 如对于引导程序而言.

GNU 386汇编

Unix 采用的是AT&T格式的指令, 而非Intel定义的x86指令.

Unix早期实在PDP-11机器上开发完成, 后一直到VAX和68000系列.

那么GNU自然继承了AT&T的386汇编语言格式.

异同点:

  1. 一般Intel大写, AT&T小写
  2. AT&T的寄存器需要%前缀
  3. AT&T 的源操作数在前,目标操作在后, 而Intel相反.
  4. AT&T格式中,访问指令的操作数宽度由操作码后缀决定:
    如 b(8), w(16), l(32)
    Intel格式中需要在内存单元的操作数前加上BYTE PTR
    WORD PTR 或DWORD PTR.
  5. AT&T 直接操作书需要加上$作为前缀, 而Intel不需要
  6. AT&T格式中jmp/call指令的操作数需要加上*作为前缀
  7. AT&T的长跳转和调用为ljmp和lcall,Intel为JMP FAR
    和CALL FAR.如下
; Intel
CALL FAR SECTION:OFFSET
JMP FAR SECTION:OFFSET

;AT&T

lcall $section, $offset
ljmp $section, $offset
  1. 间接寻址
SECTION:[BASE+INDEX*SCALE+DISP] ;Intel
section:disp(base,index,scale) ;AT&T

C代码插入汇编是以汇编片段的形式,如

/* include/asm-i386/atomic.h */
 static __inline__ void atomic_add(int i, atomic_t *v)
 {
 __asm__ __volatile__(
 LOCK "addl %1,%0"
 :"=m" (v->counter)
 :"ir" (i), "m" (v->counter));
 }

LOCK表示在执行addl时候将总线锁住, 保证操作原子性.

汇编片段形式如下:

指令部分: 输出部分 : 输入部分 : 损坏部分

  • 指令部分: 这部分和纯粹的汇编大致相同但是由于涉及到和C变量结合,那么对于数字加上%前缀表示
    需要使用寄存器的样板操作数. 指令部分中用到多少操作数代表有多少变量需要和寄存器结合, 由gcc和
    gas在编译和汇编时根据后面提供的约束条件给出. 为了避免和样板操作数混淆,具体指定寄存器需要使用%%前缀.

    在指令部分对操作数的引用总是将其当成32bits 的长字, 也可以显式的声明对于那个字节的操作, 如在%与序号间插入
    b 表示最低字节, 插入一个h表示次低字节.

  • 输出部分: 这部分是对于目标操作数如何结合的约束条件, 每个条件称为一个约束(constraint), 每个输出约束以=开头
    ,然后是一个字母表示对操作数类型的说明, 之后是关于变量结合的约束.

    :"=m" (v->counter) 就表示目标操作数(指令部分的%0)是一个内存单元 v->counter

    凡是与输出部中说明的操作数相结合的寄存器或操作数本身,在执行嵌入的汇编代码以后均不保留执行前的内容

  • 输入部分: 与输出约束类似但是不带=号.

    :"ir" (i), "m" (v->counter));中有两个输入约束, "ir"(i)表示指令中的%可以是一个在寄存器中的直接操作数
    ,并且该操作数来自C代码的变量i.

    第二个约束为"m"(v->counter) 意思为为操作数(%0)分配一个内存单元.

  • 损坏部分: 对于明示使用的寄存器gcc会对其作pushl和popl操作来保护原有内容.但是对于中间操作使用的寄存器没法
    保证, 所以要在损坏部分对操作的副作用进行说明.

操作数的编号从输出部得第一个约束开始, 顺序数下来,每个约束计数一次.

约束条件:

条件说明
mvoMemory
rAny Register
qAnyone in eax, ebx, ecx, edx
ihDirect operation
EFFloat
gAny
abcdeax, ebx, ecx, edx
SDesi edi
Iconstant(0-31)

__memcpy() 的实现:

/* include/asm-i386/string.h 199 */

static inine void * __memcpy(void * to, const void * from, size_t n){
	int d0, d1, d2;
	__asm__ __volatile__(
		"rep ; movsl 
	"
		"testb $2, %b4
	"
		"je 1f
	"
		"1:	testb $1,%b4
	"
		"je 2f
	"
		"movsb
"
		"2:"
		: "=&c" (d0), "=&D" (d1), "=&S" (d2)
		: "0" (n/4), "q" (n), "1" ((long) to), "2" ((long) from)
		: "memory"
			);
	return (to);                    
}

解析:

  • 对于输出部: 有三条约束,分别定义了变量d0对应%0操作数必须放在ecx中,
    变量d1对应操作数%1必须存在edi中, 变量d2对应操作数%2必须放在esi中.

  • 对于输入部: 有四条约束, 分别规定了%3和%0使用相同的寄存器即ecx, 并且要求gcc自动插入必要指令
    事先将其设置c为n/4(实际上是由字节数n换算成长字(DWORD)个数n/4),对于n自身由gcc自动分配寄存器;

    %5和%6即参数to和from, 分别与%1,%2使用相同的寄存器,所以为edi和esi

  • 对于指令部: 第一条为rep, 表示下一条指令将重复执行, 每重复一次ecx自减,直至为零.

    movsl 默认将esi所指的内容复制一个长字到edi所指位置,然后将esi和edi分别加4.

    拷贝完长字部分还需判断有无剩余, 这里测试n的最低字节中的bit2, 若为1表示至少还有两个字节
    然后使用movsw来拷贝.

    再通过测试n的最低字节中的bit1, 若为1则表示还有一个字节未拷贝, 通过movsb解决.

** strncmp() **实现:

/* include/asm-i386/string.h 127 */
static inline int strncmp(const char * cs,const char * ct,size_t count)
{
register int __res;
int d0, d1, d2;
__asm__ __volatile__(
	"1:	decl %3
	"
	"js 2f
	"
	"lodsb
	"
	"scasb
	"
	"jne 3f
	"
	"testb %%al,%%al
	"
	"jne 1b
"
	"2:	xorl %%eax,%%eax
	"
	"jmp 4f
"
	"3:	sbbl %%eax,%%eax
	"
	"orb $1,%%al
"
	"4:"
		     :"=a" (__res), "=&S" (d0), "=&D" (d1), "=&c" (d2)
		     :"1" (cs),"2" (ct),"3" (count));
return __res;
}

解析:

  1. 输出部: 定义了 %0 即 __res 必须与eax绑定, %1 即 d0 与esi绑定,
    %2即d1与edi绑定, %3 即 d2 与 ecx绑定.

  2. 输入部: 定义了 %4 即 cs 与%1使用相同的寄存器, %5即ct 与 %2使用相同寄存器. %6即count与%3使用相同寄存器.

  3. 指令部
    指令参考

    OPExplanation
    decl自减
    js前面运算完符号位SF为1时候跳转
    lodsb将DS:ESI指向的源串元素装入AL中
    scasb将AL的内容减去DS:EDI指向元素
    sbbl带借位的减操作 并写入
    orb字节逻辑或操作 并写入
    testb字节与测试

    先对ecx即count自减 如果结果为负直接跳出并返回0, 若为正数则开始比较, 首先通过lodsb指令
    装入AL寄存器, 再通过串扫描比较EDI执行与AL的内容, 如不等直接返回1; 相等之后判断当前是否到达串尾(al=0)
    未到达则返回开始处循环比较.

存储管理

2.1 内存管理基本框架

Linux考虑到64bit系统, 将内核的映射机制设计成三层,在页目录和页面表的中间增设"中间目录"概念.

  • 页面目录 PGD(Page Global Directory)
  • 中间目录 PMD(Page Middle Directory)
  • 页面表 PT (Page Table)
  • 表项 PTE (Page Table Entry)

线性地址到物理地址的映射过程: PGD+PMD+PT+OFFSET

内核将内存划分为1G内核空间和3G用户空间
其中0xC0000000-0xFFFFFFFF为内核空间, 线性映射所有内核进程共享该空间:

/* include/asm-i386/page.h 68 */
/*
 * This handles the memory map.. We could make this a config
 * option, but too many people screw it up, and too few need
 * it.
 *
 * A __PAGE_OFFSET of 0xC0000000 means that the kernel has
 * a virtual address space of one gigabyte, which limits the
 * amount of physical memory you can use to about 950MB. 
 *
 * If you want more physical memory than this then see the CONFIG_HIGHMEM4G
 * and CONFIG_HIGHMEM64G options in the kernel configuration.
 */

#define __PAGE_OFFSET		(0xC0000000)


#define PAGE_OFFSET		((unsigned long)__PAGE_OFFSET)
#define __pa(x)			((unsigned long)(x)-PAGE_OFFSET)
#define __va(x)			((void *)((unsigned long)(x)+PAGE_OFFSET))

注意:这里物理内存是从0开始映射的,也就是物理内存0-1G范围内被映射到内核
实际的映射由MMU完成这里是方便内核取得物理地址, 如在进程切换的时候CR3要做相应切换,
其指向的PGD应为物理地址, 而该目录的起始地址在内核中式以虚地址形式存在的,所以用到了
这里的__pa()函数转换. 代码如下:

/* include/asm-i386/mmu_context.h 43 */

/* Re-laod page tables */
 
asm volatile("movl %0, %%cr3": : "r" (__pa(next->pgd)));

TIPs: 如何计算系统最大进程数
由于全局段描述表GDT中要保存每个进程的局部描述表LDT同时要保存TSS(Task State Struct), 除去保留项
GDT(13bit宽度)可用8180,所以理论上最大进程数为4090.

2.2 地址映射全过程

Linux 采用先分段再分页是对Intel CPU的妥协, 其实在 M68K, PowerPC上是不存在段式映射的.
比如在可执行程序ELF通过objdump解析后得出如下:

0804119d <greeting>:
 804119d:	55                   	push   %ebp
 804119e:	89 e5                	mov    %esp,%ebp
 80411a0:	53                   	push   %ebx
 80411a1:	83 ec 04             	sub    $0x4,%esp
 80411a4:	e8 3b 00 00 00       	call   11e4 <__x86.get_pc_thunk.ax>
 80411a9:	05 57 2e 00 00       	add    $0x2e57,%eax
 80411ae:	83 ec 0c             	sub    $0xc,%esp
 80411b1:	8d 90 08 e0 ff ff    	lea    -0x1ff8(%eax),%edx
 80411b7:	52                   	push   %edx
 80411b8:	89 c3                	mov    %eax,%ebx
 80411ba:	e8 81 fe ff ff       	call   1040 <puts@plt>
 80411bf:	83 c4 10             	add    $0x10,%esp
 80411c2:	90                   	nop
 80411c3:	8b 5d fc             	mov    -0x4(%ebp),%ebx
 80411c6:	c9                   	leave  
 80411c7:	c3                   	ret

从上述结果可以看出ld为greeting()分配了地址0x08048386.
那么如何解析需要从

  1. 段式映射阶段: 由于当前执行过程中是由CPU中的EIP指定,在代码段中, 所以段选择index存于代码段寄存器CS
    中, CS内容由内核建立进程时设置, regs->xcs = __USER_CS. 其中 __USER_CS 被定义为 0x23.

    /* include/asm-i386/processor.h 408 */
#define start_thread(regs, new_eip, new_esp) do {		
	__asm__("movl %0,%%fs ; movl %0,%%gs": :"r" (0));	
	set_fs(USER_DS);					
	regs->xds = __USER_DS;					
	regs->xes = __USER_DS;					
	regs->xss = __USER_DS;					
	regs->xcs = __USER_CS;					
	regs->eip = new_eip;					
	regs->esp = new_esp;					
} while (0)

/* include/asm-i386/segment.h 4 */

#define __KERNEL_CS 0x10
#define __KERNEL_DS 0x18
#define __USER_CS   0x23
#define __USER_DS   0x2B

段寄存器值对照表如下

NameValueindexTIRPL
__KERNEL_CS0x100000 0000 0001 0000
__KERNEL_DS0x180000 0000 0001 1000
__USER_CS0x230000 0000 0010 0011
__USER_DS0x2B0000 0000 0010 1011

可以看出所有的TI都是0 代表只使用GDT(LDT只有在VM86模式中运行wine以及模拟Windows环境才会用到)

RPL只用到了 0 内核 和 3 用户.

下面在GDT中找到index = 4 的描述项(从0开始的)

/* arch/i386/kernel/head.S 444 */
/*
 * This contains typically 140 quadwords, depending on NR_CPUS.
 *
 * NOTE! Make sure the gdt descriptor in head.S matches this if you
 * change anything.
 */
ENTRY(gdt_table)
	.quad 0x0000000000000000	/* NULL descriptor */
	.quad 0x0000000000000000	/* not used */
	.quad 0x00cf9a000000ffff	/* 0x10 kernel 4GB code at 0x00000000 */
	.quad 0x00cf92000000ffff	/* 0x18 kernel 4GB data at 0x00000000 */
	.quad 0x00cffa000000ffff	/* 0x23 user   4GB code at 0x00000000 */
	.quad 0x00cff2000000ffff	/* 0x2b user   4GB data at 0x00000000 */
	.quad 0x0000000000000000	/* not used */
	.quad 0x0000000000000000	/* not used */
	/*
	 * The APM segments have byte granularity and their bases
	 * and limits are set at run time.
	 */
	.quad 0x0040920000000000	/* 0x40 APM set up for bad BIOS's */
	.quad 0x00409a0000000000	/* 0x48 APM CS    code */
	.quad 0x00009a0000000000	/* 0x50 APM CS 16 code (16 bit) */
	.quad 0x0040920000000000	/* 0x58 APM DS    data */
	.fill NR_CPUS*4,8,0		/* space for TSS's and LDT's */

GDT第一项和第二项不使用, 可以解析得到如下结论:
除了DPL权限和type字段表示代码和数据段不同外, 其余都完全相同.

每个段都是从0地址开始的整个4GB的虚拟空间, 虚地址到线性地址的映射保持原值不变.(段映射机制形同虚设, 虚拟地址到线性地址是完全相同的)

  1. 页映射阶段
    与段式映射过程中所有进程共用GDT不同, 每个进程的PGD是不通的, 由每个进程的mm_struct数据结构保存.
    进程切换需要将CR3设置为新的PGD物理地址, MMU硬件直接从CR3中取得指向当前页面的物理地址.

    将0x0804119d二进制展开:$$0000, 1000, 0000, 0100, 0001, 0001, 1001, 1010$$
    解析如下

    namevalue
    页面目录项0000100000
    页面表项1000010001
    offset000110011010

总结: 页面映射需要访存三次, 第一次是页面目录, 第二次是页面表, 第三次是访问的真正目标.

2.3 常见数据结构


/* include/asm-i386/page.h 36 */
/*
 * These are used to make use of C type-checking..
 */
#if CONFIG_X86_PAE
typedef struct { unsigned long pte_low, pte_high; } pte_t;
typedef struct { unsigned long long pmd; } pmd_t;
typedef struct { unsigned long long pgd; } pgd_t;
#define pte_val(x)	((x).pte_low | ((unsigned long long)(x).pte_high << 32))
#else
typedef struct { unsigned long pte_low; } pte_t;
typedef struct { unsigned long pmd; } pmd_t;
typedef struct { unsigned long pgd; } pgd_t;
#define pte_val(x)	((x).pte_low)
#endif

pgd_t, pmd_t and pte_t are all long integer, when it comes with PAE enable, they are
defined to long long integer.

值得注意的是: pte_t只有前20bit是基地址(页面大小是4KB), 所以余下的12bit作为页面的状态信息和访问权限.

内核代码中页面项的生成方式如下:

页面序号左移12位,与页面控制/状态位段相或,得到表项值.

/* include/asm-i386/pgtable-2level.h 61 */

#define __mk_pte(page_nr, pgprot) __pte(((page_nr) << PAGE_SHIFT) |  pgprot_val(pgprot))

/* include/asm-i386/page.h */
#define pgprot_val(x) ((x).pgprot)
#define __pte(x) ((pte_t) {(x)})

/* include/asm-i386/pgtable.h 162 */

#define _PAGE_PRESENT	0x001
#define _PAGE_RW	0x002
#define _PAGE_USER	0x004
#define _PAGE_PWT	0x008
#define _PAGE_PCD	0x010
#define _PAGE_ACCESSED	0x020
#define _PAGE_DIRTY	0x040
#define _PAGE_PSE	0x080	/* 4 MB (or 2MB) page, Pentium+, if present.. */
#define _PAGE_GLOBAL	0x100	/* Global TLB entry PPro+ */

#define _PAGE_PROTNONE	0x080	/* If not present */

内核中有全局变量mem_map, 是一个指向page的数组, 每个page代表一个物理页面.

/* include/linux/mm.h 126 */

/*
 * Try to keep the most commonly accessed fields in single cache lines
 * here (16 bytes or greater).  This ordering should be particularly
 * beneficial on 32-bit processors.
 *
 * The first line is data used in page cache lookup, the second line
 * is used for linear searches (eg. clock algorithm scans). 
 */
typedef struct page {
	struct list_head list;
	struct address_space *mapping;
	unsigned long index;
	struct page *next_hash;
	atomic_t count;
	unsigned long flags;	/* atomic flags, some possibly updated asynchronously */
	struct list_head lru;
	unsigned long age;
	wait_queue_head_t wait;
	struct page **pprev_hash;
	struct buffer_head * buffers;
	void *virtual; /* non-NULL if kmapped */
	struct zone_struct *zone;
} mem_map_t;

当页面内容来自文件,index代表页面在文件中的序号;

当页面内容被swap, 但是内容还作为缓冲时,怎index指明了页面的去向.

系统中的每个物理页面都有一个page结构,系统在初始化时根据物理内存的大小建立其一个page结构数组
mem_map.每个物理页面的page结构在这个数组里的下标就是该物理页面的序号.
物理页面被分为ZONE_DMA 和ZONE_NORMAL(以及物理内存超过1GB时的ZONE_HIGHMEM)

ZONE_DMA的理由:

  1. 预留空间给磁盘I/O
  2. DMA由于不经过MMU提供地址映射,所以需要直接访问物理地址.
  3. 使用DMA缓冲很大所以需要的物理页要连续, 不能被分页机制破环地址的连续性.
/* include/linux/mmzone.h 11 */

/*
 * Free memory management - zoned buddy allocator.
 */

#define MAX_ORDER 10

typedef struct free_area_struct {
	struct list_head	free_list;
	unsigned int		*map;
} free_area_t;

struct pglist_data;

typedef struct zone_struct {
	/*
	 * Commonly accessed fields:
	 */
	spinlock_t		lock;
	unsigned long		offset;
	unsigned long		free_pages;
	unsigned long		inactive_clean_pages;
	unsigned long		inactive_dirty_pages;
	unsigned long		pages_min, pages_low, pages_high;

	/*
	 * free areas of different sizes
	 */
	struct list_head	inactive_clean_list;
	free_area_t		free_area[MAX_ORDER];

	/*
	 * rarely used fields:
	 */
	char			*name;
	unsigned long		size;
	/*
	 * Discontig memory support fields.
	 */
	struct pglist_data	*zone_pgdat;
	unsigned long		zone_start_paddr;
	unsigned long		zone_start_mapnr;
	struct page		*zone_mem_map;
} zone_t;

#define ZONE_DMA		0
#define ZONE_NORMAL		1
#define ZONE_HIGHMEM		2
#define MAX_NR_ZONES		3

其中offset代表该分区在mem_map中的起始页面号, 管理区的建立每个物理页面便永久属于该管理区.

理想环境下, 物理空间均匀一致, CPU访问内存中的任意地址时间相同,称之为均质存储结构(Uniform Memory Architecture)

但实际情况下都是NUMA结构, 所以上述的物理页面管理机制要修改, 管理区不再是最高层机构, 而时在每个存储节点都需要至少两个管理区. 而且page结构数组页不在时全局性的, 而数丛书与具体的节点. 在zone_struct之上又有了一层代表着存储节点的pglist_data数据结构.

/* include/linux/mmzone.h */

typedef struct pglist_data {
	zone_t node_zones[MAX_NR_ZONES];
	zonelist_t node_zonelists[NR_GFPINDEX];
	struct page *node_mem_map;
	unsigned long *valid_addr_bitmap;
	struct bootmem_data *bdata;
	unsigned long node_start_paddr;
	unsigned long node_start_mapnr;
	unsigned long node_size;
	int node_id;
	struct pglist_data *node_next;
} pg_data_t;

pglist_data可以通过node_next形成一个单链队列.
每个结构中的指针node_mem_map指向具体节点的page结构数组.
node_zone[] 代表该节点的最多三个页面管理区, 同时zone_struct结构中也有指向pglist_data的指针.

node_zonelists链是用来进行页面分配指定页面管理区的分配顺序的.

同时相对于物理内存的管理, 虚拟内存同样也有虚存空间的概念.
对其的抽象就是vm_area_struct数据结构. 虚存空间由[vm_start, vm_end) 左闭右开.
权限由vm_page_prot和vm_flags 控制.
通过vm_next 进行遍历, 同时为了加快查找速度建立了AVL(Adelson-Velskii and Landis)树结构.


/* include/linux/mm.h */

/*
 * This struct defines a memory VMM memory area. There is one of these
 * per VM-area/task.  A VM area is any part of the process virtual memory
 * space that has a special rule for the page-fault handlers (ie a shared
 * library, the executable area etc).
 */
struct vm_area_struct {
	struct mm_struct * vm_mm;	/* VM area parameters */
	unsigned long vm_start;
	unsigned long vm_end;

	/* linked list of VM areas per task, sorted by address */
	struct vm_area_struct *vm_next;

	pgprot_t vm_page_prot;
	unsigned long vm_flags;

	/* AVL tree of VM areas per task, sorted by address */
	short vm_avl_height;
	struct vm_area_struct * vm_avl_left;
	struct vm_area_struct * vm_avl_right;

	/* For areas with an address space and backing store,
	 * one of the address_space->i_mmap{,shared} lists,
	 * for shm areas, the list of attaches, otherwise unused.
	 */
	struct vm_area_struct *vm_next_share;
	struct vm_area_struct **vm_pprev_share;

	struct vm_operations_struct * vm_ops;
	unsigned long vm_pgoff;		/* offset in PAGE_SIZE units, *not* PAGE_CACHE_SIZE */
	struct file * vm_file;
	unsigned long vm_raend;
	void * vm_private_data;		/* was vm_pte (shared mem) */
};

在两种情况下虚存页面会与磁盘文件发生交互：

  1. 盘区交换swap
  2. mmap系统调用， 将已打开文件映射到用户空间，通访存的方式来访问文件。

虚拟区间操作函数：

/* include/linux/mm.h:115 */
/*
 * These are the virtual MM functions - opening of an area, closing and
 * unmapping it (needed to keep files on disk up-to-date etc), pointer
 * to the functions called when a no-page or a wp-page exception occurs. 
 */
struct vm_operations_struct {
	void (*open)(struct vm_area_struct * area);
	void (*close)(struct vm_area_struct * area);
	struct page * (*nopage)(struct vm_area_struct * area, unsigned long address, int write_access);
};

open和close 负责虚存空间的打开和关闭， nopage 为出现page fault时调用函数。

最后vm_area_struct中还有一个指针vm_mm, 该指针指向一个mm_struct数据结构。
事实上这个是更高层次的数据结构， 每个进程只有一个mm_struct ， 可以看作整个用户空间的抽象。
mm_struct被task_struct 的mm指针指向。当进程传见子进程时会共享该结构。
《内核源码情景分析》（浙大）笔记第1张

在某进程空间内找到给定虚拟地址的所属的区间的vm_area_struct, 有find_vma()函数实现：

/* mm/mmap.c 404 */

/* Look up the first VMA which satisfies  addr < vm_end,  NULL if none. */
struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long addr)
{
	struct vm_area_struct *vma = NULL;

	if (mm) {
		/* Check the cache first. */
		/* (Cache hit rate is typically around 35%.) */
		vma = mm->mmap_cache;
		if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
			if (!mm->mmap_avl) {
				/* Go through the linear list. */
				vma = mm->mmap;
				while (vma && vma->vm_end <= addr)
					vma = vma->vm_next;
			} else {
				/* Then go through the AVL tree quickly. */
				struct vm_area_struct * tree = mm->mmap_avl;
				vma = NULL;
				for (;;) {
					if (tree == vm_avl_empty)
						break;
					if (tree->vm_end > addr) {
						vma = tree;
						if (tree->vm_start <= addr)
							break;
						tree = tree->vm_avl_left;
					} else
						tree = tree->vm_avl_right;
				}
			}
			if (vma)
				mm->mmap_cache = vma;
		}
	}
	return vma;
}

可以看出先对缓存mmap_cache进行判断，然后通过AVL/线性查找方式去定位vma.

2.4 越界访问

  1. 访问失败
  • 对应页面目录，页面表项为空。
  • 物理页不在内存中
  • 访问权限不匹配
  1. 页错误处理
    上述将会引发Page Fault异常， do_page_fault：
/* arch/i386/mm/fault.c 106 */

/*
 * This routine handles page faults.  It determines the address,
 * and the problem, and then passes it off to one of the appropriate
 * routines.
 *
 * error_code:
 *	bit 0 == 0 means no page found, 1 means protection fault
 *	bit 1 == 0 means read, 1 means write
 *	bit 2 == 0 means kernel, 1 means user-mode
 */
asmlinkage void do_page_fault(struct pt_regs *regs, unsigned long error_code)
{
	struct task_struct *tsk;
	struct mm_struct *mm;
	struct vm_area_struct * vma;
	unsigned long address;
	unsigned long page;
	unsigned long fixup;
	int write;
	siginfo_t info;

	/* get the address */
	__asm__("movl %%cr2,%0":"=r" (address));

	tsk = current;

	/*
	 * We fault-in kernel-space virtual memory on-demand. The
	 * 'reference' page table is init_mm.pgd.
	 *
	 * NOTE! We MUST NOT take any locks for this case. We may
	 * be in an interrupt or a critical region, and should
	 * only copy the information from the master page table,
	 * nothing more.
	 */
	if (address >= TASK_SIZE)
		goto vmalloc_fault;

	mm = tsk->mm;
	info.si_code = SEGV_MAPERR;

	/*
	 * If we're in an interrupt or have no user
	 * context, we must not take the fault..
	 */
	if (in_interrupt() || !mm)
		goto no_context;

	down(&mm->mmap_sem);

	vma = find_vma(mm, address);
	if (!vma)
		goto bad_area;
	if (vma->vm_start <= address)
		goto good_area;
	if (!(vma->vm_flags & VM_GROWSDOWN))
		goto bad_area;
	if (error_code & 4) {
		/*
		 * accessing the stack below %esp is always a bug.
		 * The "+ 32" is there due to some instructions (like
		 * pusha) doing post-decrement on the stack and that
		 * doesn't show up until later..
		 */
		if (address + 32 < regs->esp)
			goto bad_area;
	}
	if (expand_stack(vma, address))
		goto bad_area;
/*
 * Ok, we have a good vm_area for this memory access, so
 * we can handle it..
 */
good_area:
	info.si_code = SEGV_ACCERR;
	write = 0;
	switch (error_code & 3) {
		default:	/* 3: write, present */
#ifdef TEST_VERIFY_AREA
			if (regs->cs == KERNEL_CS)
				printk("WP fault at %08lx
", regs->eip);
#endif
			/* fall through */
		case 2:		/* write, not present */
			if (!(vma->vm_flags & VM_WRITE))
				goto bad_area;
			write++;
			break;
		case 1:		/* read, present */
			goto bad_area;
		case 0:		/* read, not present */
			if (!(vma->vm_flags & (VM_READ | VM_EXEC)))
				goto bad_area;
	}

	/*
	 * If for any reason at all we couldn't handle the fault,
	 * make sure we exit gracefully rather than endlessly redo
	 * the fault.
	 */
	switch (handle_mm_fault(mm, vma, address, write)) {
	case 1:
		tsk->min_flt++;
		break;
	case 2:
		tsk->maj_flt++;
		break;
	case 0:
		goto do_sigbus;
	default:
		goto out_of_memory;
	}

	/*
	 * Did it hit the DOS screen memory VA from vm86 mode?
	 */
	if (regs->eflags & VM_MASK) {
		unsigned long bit = (address - 0xA0000) >> PAGE_SHIFT;
		if (bit < 32)
			tsk->thread.screen_bitmap |= 1 << bit;
	}
	up(&mm->mmap_sem);
	return;

/*
 * Something tried to access memory that isn't in our memory map..
 * Fix it, but check if it's kernel or user first..
 */
bad_area:
	up(&mm->mmap_sem);

bad_area_nosemaphore:
	/* User mode accesses just cause a SIGSEGV */
	if (error_code & 4) {
		tsk->thread.cr2 = address;
		tsk->thread.error_code = error_code;
		tsk->thread.trap_no = 14;
		info.si_signo = SIGSEGV;
		info.si_errno = 0;
		/* info.si_code has been set above */
		info.si_addr = (void *)address;
		force_sig_info(SIGSEGV, &info, tsk);
		return;
	}

	/*
	 * Pentium F0 0F C7 C8 bug workaround.
	 */
	if (boot_cpu_data.f00f_bug) {
		unsigned long nr;
		
		nr = (address - idt) >> 3;

		if (nr == 6) {
			do_invalid_op(regs, 0);
			return;
		}
	}

no_context:
	/* Are we prepared to handle this kernel fault?  */
	if ((fixup = search_exception_table(regs->eip)) != 0) {
		regs->eip = fixup;
		return;
	}

/*
 * Oops. The kernel tried to access some bad page. We'll have to
 * terminate things with extreme prejudice.
 */

	bust_spinlocks();

	if (address < PAGE_SIZE)
		printk(KERN_ALERT "Unable to handle kernel NULL pointer dereference");
	else
		printk(KERN_ALERT "Unable to handle kernel paging request");
	printk(" at virtual address %08lx
",address);
	printk(" printing eip:
");
	printk("%08lx
", regs->eip);
	asm("movl %%cr3,%0":"=r" (page));
	page = ((unsigned long *) __va(page))[address >> 22];
	printk(KERN_ALERT "*pde = %08lx
", page);
	if (page & 1) {
		page &= PAGE_MASK;
		address &= 0x003ff000;
		page = ((unsigned long *) __va(page))[address >> PAGE_SHIFT];
		printk(KERN_ALERT "*pte = %08lx
", page);
	}
	die("Oops", regs, error_code);
	do_exit(SIGKILL);

/*
 * We ran out of memory, or some other thing happened to us that made
 * us unable to handle the page fault gracefully.
 */
out_of_memory:
	up(&mm->mmap_sem);
	printk("VM: killing process %s
", tsk->comm);
	if (error_code & 4)
		do_exit(SIGKILL);
	goto no_context;

do_sigbus:
	up(&mm->mmap_sem);

	/*
	 * Send a sigbus, regardless of whether we were in kernel
	 * or user mode.
	 */
	tsk->thread.cr2 = address;
	tsk->thread.error_code = error_code;
	tsk->thread.trap_no = 14;
	info.si_code = SIGBUS;
	info.si_errno = 0;
	info.si_code = BUS_ADRERR;
	info.si_addr = (void *)address;
	force_sig_info(SIGBUS, &info, tsk);

	/* Kernel mode? Handle exceptions or die */
	if (!(error_code & 4))
		goto no_context;
	return;

vmalloc_fault:
	{
		/*
		 * Synchronize this task's top level page-table
		 * with the 'reference' page table.
		 */
		int offset = __pgd_offset(address);
		pgd_t *pgd, *pgd_k;
		pmd_t *pmd, *pmd_k;

		pgd = tsk->active_mm->pgd + offset;
		pgd_k = init_mm.pgd + offset;

		if (!pgd_present(*pgd)) {
			if (!pgd_present(*pgd_k))
				goto bad_area_nosemaphore;
			set_pgd(pgd, *pgd_k);
			return;
		}

		pmd = pmd_offset(pgd, address);
		pmd_k = pmd_offset(pgd_k, address);

		if (pmd_present(*pmd) || !pmd_present(*pmd_k))
			goto bad_area_nosemaphore;
		set_pmd(pmd, *pmd_k);
		return;
	}
}

解析：

  1. 首先定义了三个error_code：
error_code bit01
bit0no page foundprotection fault
bit1readwrite
bit2kerneluser-mode
  1. 由于page fault发生时, CPU会将失败地址放入CR2寄存器中, 所以通过汇编将其放入address.
    同时异常还发送了当时的reg以及error_code, 用与确定当时的现场以及失败的原因.
  2. 之后是对当前进程task_struct的获取(通过current宏实现)
  3. 接下来针对page_fault的发生是是在中断还是异常,即进程有关和无关问题. 特别地, 中断表示
    内存映射失败发生在某个中断服务程序中,而与进程无关, 还有一种情形是映射mm指针为空, 说明进程的映射尚未建立, 也与当前进程无关.这种情况交由no_cotext处理.
  4. 接下来需要对操作进行互斥访问, 对mm_struct设置了信号量mmap_sem.由down/up操作进行P/V.
  5. 确定完失败地址和进程以后需要对地址映射的区间定位, 这里用到了find_vma(), 如果找不到说明访问越界,继而转向bad_area. 如果找到了则说明映射已经建立了, 转向good_area.
  6. 如果给定地址落在空洞区(被撤销或者未建立), 未建立的空洞只有一种情形, 那就是堆栈区以下的空洞.
    如何确定? 通过vm_area_struct的vm_flags中的标志位VM_GROWSDOWN, 该标志位为0时代表空洞上方非堆栈区,那么就是撤销的种情形, 反之就是堆栈下的空洞.
  7. 确定地址位于被撤销的空洞则转向bad_area, 由于这里不需要对mm_struct进行操作, 先通过up()释放mmap_sem信号, 之后判断error_code的bit2为1时, 表示失败是由CPU处于用户模式那么进行一些task设置后发出SIGSEGV信号退出.

2.5 用户堆栈的扩展

   ┏━━━━━━━━━━━━┓-----------------
   ┃ / / / / / /┃ 
   ┃/ / / / / / ┃ ←---系统空间
   ┣━━━━━━━━━━━━┫ 0xC0000000 ----
   ┃            ┃
   ┃  堆 栈 区  ┃
   ┃            ┃
   ┣━━━━━━━━━━━━┫
   ┃  空  洞    ┃
   ┃            ┃
   ┣━━━━━━━━━━━━┫ ←---用户空间
   ┃ 数据       ┃
   ┃ 代码区     ┃
   ┗━━━━━━━━━━━━┛-----------------

对于堆栈区下方的空洞, 需要检查其异常地址是否紧挨着堆栈指针所指空间, 如果地址在%esp-4.
i386 CPU的pusha 将会使%esp-32, 超出该范围一定是错的, 转向bad_area.

如果是正常的堆栈扩展要求, 那么应该从空洞顶部开始分配若干页面建立映射.
调用expand_stack()

/* inlcude/linux/mm.h  487 */

/* vma is the first one with  address < vma->vm_end,
 * and even  address < vma->vm_start. Have to extend vma. */
static inline int expand_stack(struct vm_area_struct * vma, unsigned long address)
{
	unsigned long grow;

	address &= PAGE_MASK;
	grow = (vma->vm_start - address) >> PAGE_SHIFT;
	if (vma->vm_end - address > current->rlim[RLIMIT_STACK].rlim_cur ||
	    ((vma->vm_mm->total_vm + grow) << PAGE_SHIFT) > current->rlim[RLIMIT_AS].rlim_cur)
		return -ENOMEM;
	vma->vm_start = address;
	vma->vm_pgoff -= grow;
	vma->vm_mm->total_vm += grow;
	if (vma->vm_flags & VM_LOCKED)
		vma->vm_mm->locked_vm += grow;
	return 0;
}

解析:
vma 代表用户空间堆栈所在区间, 确定页号偏移量, 分配空间(注意栈大小不可大于RLIMIT_STACK).
此外此函数只改变了堆栈区vma的结构, 并未建立物理内存的映射.

接下来由good_area完成, 首先对error_code判断并分配对策, 对于上述情形, 可以执行handle_mm_fault().

/* mm/memory.c 1189 */

/*
 * By the time we get here, we already hold the mm semaphore
 */
int handle_mm_fault(struct mm_struct *mm, struct vm_area_struct * vma,
	unsigned long address, int write_access)
{
	int ret = -1;
	pgd_t *pgd;
	pmd_t *pmd;

	pgd = pgd_offset(mm, address);
	pmd = pmd_alloc(pgd, address);

	if (pmd) {
		pte_t * pte = pte_alloc(pmd, address);
		if (pte)
			ret = handle_pte_fault(mm, vma, address, write_access, pte);
	}
	return ret;
}
  1. pdg_offset()宏操作计算指向该地址所属页面目录项的指针.
#define pdg_index(address) ((address >> PGDIR_SHIFT) & (PTRS_PER_PGD - 1))
#deinfe pdg_offset(mm, address) ((mm)->pdg + pgd_index(address))
  1. 对于pmg_alloc分配中间页目录项, 由于i386只用了两层映射, 所以被定义为return (pmd_t *)pgd;.
  2. 接下来分配页面表的页面pte_alloc(), 先将给定地址转换成所属页面表的下表, 加入目录项为空, 那么需要get_new()来生成页面表. (当释放页面表时, 内核将释放的页面表先保存在缓冲池中, 而不先将物理内存页面释放, 只有当池满的情况才会将页面表所占的物理内存页面释放.)
  3. 在缓冲池内的页面表可以通过get_pte_fast获取, 若不存在则使用get_pte_slow获取.
  4. 有了页目录表, 中间目录表,页面表以后接下来需要对物理内存页面进行映射, 由handle_pte_fault()完成.
/* mm/memory.c 1135 */

/*
 * These routines also need to handle stuff like marking pages dirty
 * and/or accessed for architectures that don't do it in hardware (most
 * RISC architectures).  The early dirtying is also good on the i386.
 *
 * There is also a hook called "update_mmu_cache()" that architectures
 * with external mmu caches can use to update those (ie the Sparc or
 * PowerPC hashed page tables that act as extended TLBs).
 *
 * Note the "page_table_lock". It is to protect against kswapd removing
 * pages from under us. Note that kswapd only ever _removes_ pages, never
 * adds them. As such, once we have noticed that the page is not present,
 * we can drop the lock early.
 *
 * The adding of pages is protected by the MM semaphore (which we hold),
 * so we don't need to worry about a page being suddenly been added into
 * our VM.
 */
static inline int handle_pte_fault(struct mm_struct *mm,
	struct vm_area_struct * vma, unsigned long address,
	int write_access, pte_t * pte)
{
	pte_t entry;

	/*
	 * We need the page table lock to synchronize with kswapd
	 * and the SMP-safe atomic PTE updates.
	 */
	spin_lock(&mm->page_table_lock);
	entry = *pte;
	if (!pte_present(entry)) {
		/*
		 * If it truly wasn't present, we know that kswapd
		 * and the PTE updates will not touch it later. So
		 * drop the lock.
		 */
		spin_unlock(&mm->page_table_lock);
		if (pte_none(entry))
			return do_no_page(mm, vma, address, write_access, pte);
		return do_swap_page(mm, vma, address, pte, pte_to_swp_entry(entry), write_access);
	}

	if (write_access) {
		if (!pte_write(entry))
			return do_wp_page(mm, vma, address, pte, entry);

		entry = pte_mkdirty(entry);
	}
	entry = pte_mkyoung(entry);
	establish_pte(vma, address, pte, entry);
	spin_unlock(&mm->page_table_lock);
	return 1;
}

当pte为空那么进入do_no_page() 否则do_swap_page().

COW(Copy On Write):

读共享,写时复制.

do_no_page由do_anonymous_page实现:

  1. ptre_wrprotect() 修复读操作异常, 将_PAGE_RW设为0, 表示页面只读.
  2. pte_mkwrite() 修复写操作异常, 将_PAGE_RW设为1, 但是所映射的页面都是ZERO_PAGE. 就是说凡是
    写保护的页面, 开始一律映射到物理内存页面empty_zero_page, 而不管其虚拟地址是什么. 实际上, 这个页面的内容为全0, 所以映射之初若从该页面读出就读得0.
    只有科协页面才通过alloc_page()为其分配独立的物理内存.
  3. 这里页面位于堆栈区, 首先通过alloc_page()分配物理内存页面, 然后设置状态和标志位,并通过set_pte设置进指针page_table所指的页面表项. 注意i386的MMU实现是在CPU内部,所以这里的update_mmu_cache是个空函数.

最后, 经历层层返回控制流到do_page_fault,然后交由用户空间, 重新执行失败的指令.(这是与普通中断所不同的)

2.6 物理页的使用和周转

在系统初始化阶段, 系统检测全部物理内存, 并为每个物理页分配page结构, 形成全局数组, 由mem_map指向.
同时又将这些页面合成物理地址连续的许多内存页面块, 在根据块的大小建立其若干zone, 在每个zone内设置一个空闲块队列组. 类似的, 交换设备的每个物理页面也要在内存有相应的数据结构,swap_info_struct.
这里定义了计数器表示页面是否被分配使用, 以及多少用户在共享页面. swap_map指向一个数组, 数组内的元书是盘上的物理页面, 下标表示盘上位置.数组大小取决于pages, 表示页面交换设备大小.

内核还允许多个页面交换设备建立一个swap_info_struct的数组swap_info.

同时还设立了一个队列swap_list定义优先级.

就像通过pte_t结构建立其物理内存页面和虚存页面联系一样, 盘上页面也有swp_entry_t数据结构.
其为32位无符号整数, sw怕_entry_t = offset(24bbit) + type(7bit) + 0(1bit)
offset是文件的逻辑页面号, type是设备号.
其实从

#define pte_to_swp_entry(pte)  ((swp_entry_t) {(pte).pte_low})
#define swp_entry_to_pte(x) ((pte_t) {(x).val })

可以看出两者是可以互相转换的, 其实不同点在与type处的P值, 若该值为1表示其位于内存中,那么就可以当其为pte, 否则变成一个swp_entry_t.
注意: 盘上页面的释放不需要擦除数据, 只需要在内存中消除相应记录即可.

所谓内存页面的周转分为

  1. 页面的分配, 使用和回收
  2. 盘区交换, 交换的终极目的也是页面的回收. 也并非所有页面都可以被交换: 只有映射到用户内存空间的页面才会被换出 (实际上内核区有一部分是物理内存的完全映射ps:4G以内)

内存分类:

  1. 内核代码和内核全局变量所占内存页面是静态的, 不会被分配以及换出.

  2. 除上内核使用的页面还是需要动态分配, 但是不会被交换.

    • "阅后即焚" 空闲-> 分配 -> 使用 -> 释放 -> 空闲
    • 具有缓存价值: 放入LRU

  3. 进程的代码段和全局变量都在用户空间, 所占的内存页面都是动态的.

页面交换:

为了防止抖动发生, 需要做些调整:

  1. 空闲 页面的page数据结构通过队列头结构list链入某个页面管理区zone的空闲区队列free_area/ 页面的技术count=0.

  2. 分配 通过函数__alloc_pages()或_get_free_page() 从某个空闲队列中分配内存页面, 并将分配的使用计数count=1, 其page数据结构的队列头list结构变为空闲.

  3. 活跃状态 页面的page数据结构通过其队列头结构lru链入活跃页面队列active_list, 并且至少有一个进程空间页面表项指向该页面. 每当为页面建立或恢复映射时, 都是页面的使用计数count加一.

  4. 不活跃状态 脏页 页面的page结构通过其队列头结构lru链入不活跃脏页队列inactive_dirty_list, 但是原则上不再有任何进程的页面表项指向该页面. 每当断开页面映射时都使页面的使用计数count减1.
    将不活跃的脏页写入将换设备, 并将页面的page数据结构从不活跃脏页面队列inactive_dirty_list转移到某个不活跃干净页面队列中.

  5. 不活跃状态 干净 页面的page数据结构通过其队列头结构lru链入某个不活跃页面队列 inactive_clean_list.

  6. 如果在转入不活跃状态后页面被访问, 则转入活跃状态并恢复映射.

  7. 如有需要, 就从干净页面队列回收页面, 或退回空闲队列, 或直接另行分配.

注意: 内核设置了全局性的active_list和inactive_dirty_list两个LRU队列, 还在每个页面管理区
zone设置了一个inactive_clean_list.
为了回收页面提供参考, 同时通过一个全局address_space数据结构swapper_space, 把所有的可交换的内存页面管理起来, 每个可交换内存页面的page数据结构都是通过其队列头结构list链入其中的一个队列.此外, 为了加快在暂存队列中的搜索, 又设置了一个page_hash_table

内核分配空闲内存页面以后, 通过add_to_swap_cache()将其page结构链入相应的队列.

2.7 物理页面分配

当一个进程需要分配若干连续的物理页面时, 可以通过alloc_pages()实现.

Linux 2.4.0有两种实现分别位于mm/numa.c和mm/page_alloc.c中.

/* mm/numa.c  91 */

/*
 * This can be refined. Currently, tries to do round robin, instead
 * should do concentratic circle search, starting from current node.
 */
struct page * alloc_pages(int gfp_mask, unsigned long order)
{
	struct page *ret = 0;
	pg_data_t *start, *temp;
#ifndef CONFIG_NUMA
	unsigned long flags;
	static pg_data_t *next = 0;
#endif

	if (order >= MAX_ORDER)
		return NULL;
#ifdef CONFIG_NUMA
	temp = NODE_DATA(numa_node_id());
#else
	spin_lock_irqsave(&node_lock, flags);
	if (!next) next = pgdat_list;
	temp = next;
	next = next->node_next;
	spin_unlock_irqrestore(&node_lock, flags);
#endif
	start = temp;
	while (temp) {
		if ((ret = alloc_pages_pgdat(temp, gfp_mask, order)))
			return(ret);
		temp = temp->node_next;
	}
	temp = pgdat_list;
	while (temp != start) {
		if ((ret = alloc_pages_pgdat(temp, gfp_mask, order)))
			return(ret);
		temp = temp->node_next;
	}
	return(0);
}

解析:

  1. 首先通过NODE_DATA宏和numa_node_id()取到CPU所在节点的pg_data_t队列到temp.
  2. 两个while循环, 第一次从temp到队尾查找分配符合节点, 第二次从头节点到temp节点查找合适节点.

TODO: page 86

2.8 页面的定期换出

kswapd是一个由内核调度的线程, 专门负责页面换出.

kswapd 通过在系统初始化进行kswapd_init()

  1. swap_setup根据物理内存大小设定一个全局量page_cluster 该参数是用于读磁盘预读数目指示.
  2. 创建现场kswapd和kreclaimd
    初始化之后, 程序进入无线循环, 每次循环的末尾调用interruptible_sleep_on_timeout() 进入睡眠, 让内核自由调度. 一定时间后又会被唤醒, 继续执行. 本版本定义了经历HZ次时钟中断后重新唤醒, 而HZ代表每秒钟始终中断次数, 即1s钟重新调度.

kswapd 在例程中会有两部分:

  1. 物理页短缺的情况下, 找到可交换页面, 断开映射, 并设置其状态为不活跃.
  2. 不活跃脏页写回交换设备, 使其成为不活跃干净页面继续缓冲, 或者回收.

2.9 页面的换入

当寻址过程中发现地址映射存在, 但是对应的P位为0, 即不在内存中.
需要由交换区换入内存.

2.10 内核缓冲区的管理

早在Solaris 2.4(Unix变种)就提出了slab的缓冲区分配和管理办法.
在slab管理方法中, 每种重要数据都有自己专用的缓冲区队列, 每种数据都有相应的constructor 和destructor函数. 同时将结构称为对象, 每个对象的缓冲区队列并非由各个对象直接构成, 而是由一大连串的slab构成. 对象分为大对象和小对象.小对象是指小于页面大小.

  • slab可能由(1,2,4,8,16,32)个连续的物理页面构成.

  • 每个slab的前端是slab描述结构slab_t, 用同一种对象的多个slab通过描述结构的队列头形成一条双向队列. 每个slab的双向队列在逻辑上分为三段:

    • 各个已经分配使用的对象
    • 部分已经分配使用的对象
    • 空闲状态的对象

  • 每个slab都有一个对象区, 这个是对象数据结构的数组, 以对象的序号为下标就可以得到具体的对象的起始地址.

  • 每个slab上还有个对象链接数组, 用来实现一个空闲对象链.

  • 每个slab上都有一个字段指向了slab上的第一个空闲对象.

  • 在slab的描述结构中还有一个已经分配使用的对象的计数器, 当一个空闲的对象分配使用时, 就将slab的控制结构中的计数器加1.

  • 当时释放一个对象时, 只需要调整链接数组中的相应元素以及slab描述结构中的计数器,并且更具该slab的使用情况而调整其在slab队列中的位置.

  • 每个slab的头部都一部分区域不使用, 称之为着色区.
    着色区的大小使slab中的每个对象的起始地址都按高速缓存中的缓冲行大小对齐.(80386的一级高速缓存中缓存行大小为16B)

  • 每个slab上最后一个对象之后也有一个小小的废料区是不用的, 这是对着色区大小的补偿, 其大小取决与着色区的大小以及slab与其对象相对的大小.

  • 每个对象的大小基本是所需数据结构的大小. 只有当数据结构的大小不与告诉缓存中的缓存行对齐才增加若干字节使其对齐. 所以, 一个slab上的所有对象的起始地址一定是对其的.

    /* mm/slab.c 138 */
/*
 * slab_t
 *
 * Manages the objs in a slab. Placed either at the beginning of mem allocated
 * for a slab, or allocated from an general cache.
 * Slabs are chained into one ordered list: fully used, partial, then fully
 * free slabs.
 */
typedef struct slab_s {
	struct list_head	list;
	unsigned long		colouroff;
	void			    *s_mem;		/* including colour offset */
	unsigned int		inuse;		/* num of objs active in slab */
	kmem_bufctl_t		free;
} slab_t;

解析:

  1. list 用来将一块slab链入一个专用缓冲区队列
  2. colouroff 为本slab上着色区大小
  3. s_mem指向对象区的起点
  4. inuse是已分配对象的计数器
  5. free指向空闲对象链中的第一个对象.

Cache形成层次式树形结构:

  • 总根cache_cache是一个kmem_cache_t 结构, 用来维持第一层slab队列, slab对象都是kmem_cache_t.
  • 每个第一层上的kmem_cache_t都是队列头, 维护第二次队列.
  • 第二层为某种对象, 数据结构专用, slab上都维护一个空闲队列.

《内核源码情景分析》（浙大）笔记第2张

分配一个数据的缓存时, 只需指明队列不需要说明大小.

void *kmem_cache_alloc(kmem_cache_t *cachep, int flags);
void *kmem_cache_free(kmem_cache_t *cachep, void *objp);

对于非专用的缓冲区队列, 由通用的缓冲区分配机制. 类似物理页面中分配按大小分区, 又采用slab方式管理的通用缓冲池,
称为slab cache. 其顶层时一个结构数组(静态). slab对象大小从32,64到128K.分配释放函数为:

void *kmalloc(size_t size, int flags);
void free(const void *objp);

分配策略: 对于专用的数据结构使用kmem_cache_alloc 分配, 对于非专用使用kmalloc, 对于数据结构很大接近一个页面的使用alloc_pages分配.

内存还有一组用于分配的函数:
vmalloc()和vfree()

void *vmalloc(unsigned long size);
void vfree(void *addr);

vmalloc() 从内核的虚存空间分配虚存以及相应的物理地址, 类似于系统调用brk(), 而brk()时用户空间使用的, vmalloc()则在系统空间. vmalloc 不会被kswapd换出, 因为kswapd只能扫描用户进程空间.

2.10.1 专用缓冲区的建立

/* net/core/skbuff.c 473 */
void __init skb_init(void)
{
	int i;

	skbuff_head_cache = kmem_cache_create("skbuff_head_cache",
					      sizeof(struct sk_buff),
					      0,
					      SLAB_HWCACHE_ALIGN,
					      skb_headerinit, NULL);
	if (!skbuff_head_cache)
		panic("cannot create skbuff cache");

	for (i=0; i<NR_CPUS; i++)
		skb_queue_head_init(&skb_head_pool[i].list);
}

可以看到skb_init建立了一个sk_buff数据结构的专用缓冲区队列, 名为skbuff_head_cache, 每个缓冲区大小为sizeof(struct sk_buff), slab中位移为offset=0, flags为SLAB_HWCACHE_ALIGN 表示要与高速缓存中的缓冲行边界(16B或32B)对齐. 对象构造函数为skb_headerinit(), destructor为NULL.

2.10.2 缓冲区的分配和释放

在建立了一种缓冲区的专用队列后, 可以用kmem_cache_alloc()进行分配:

  1. 无空闲slab对象 需要重新分配 kmem_chache_grow()
  2. 有空闲slab对象 kmem_alloc_one_tail()
  3. kmem_cache_reap()被定时调用来释放完全空闲的slab.

专用缓冲区的释放是由kmem_cache_free 完成的.

  1. 操作的主体是__kmem_cache_free(), 需要关中断.
  2. 根据待释放对象的地址可以算出其所在页面的, 进一步, 页面的page结构中链头list内,原本用于队列链接的指针prev指向了找到对象所在的
    slab, 所以通过GET_PAGE_SLAB可以得到slab的指针.

注意: 缓冲区的释放不等同slab的释放, slab的释放是由kswapd等内核线程调用kmem_cache_reap()完成的.

通用缓冲区队列的分配的关键是通用缓冲区的cache_size, 里面根据缓冲区的大小而分成若干队列.
如kmalloc():

/* mm/slab.c  1511*/
/**
 * kmalloc - allocate memory
 * @size: how many bytes of memory are required.
 * @flags: the type of memory to allocate.
 *
 * kmalloc is the normal method of allocating memory
 * in the kernel.  The @flags argument may be one of:
 *
 * %GFP_BUFFER - XXX
 *
 * %GFP_ATOMIC - allocation will not sleep.  Use inside interrupt handlers.
 *
 * %GFP_USER - allocate memory on behalf of user.  May sleep.
 *
 * %GFP_KERNEL - allocate normal kernel ram.  May sleep.
 *
 * %GFP_NFS - has a slightly lower probability of sleeping than %GFP_KERNEL.
 * Don't use unless you're in the NFS code.
 *
 * %GFP_KSWAPD - Don't use unless you're modifying kswapd.
 */
void * kmalloc (size_t size, int flags)
{
	cache_sizes_t *csizep = cache_sizes;

	for (; csizep->cs_size; csizep++) {
		if (size > csizep->cs_size)
			continue;
		return __kmem_cache_alloc(flags & GFP_DMA ?
			 csizep->cs_dmacachep : csizep->cs_cachep, flags);
	}
	BUG(); // too big size
	return NULL;
}

释放是由kmem_cache_reap()的调用, 其扫描cache_sizes,从clock_searchp开始, 每次保持回收80%.调用kmem_slab_destroy.

2.11 外部设备存储空间的地址映射

对外部设备的访问有两种形式:

  • 内存映射式

    设备的存储单元映射到内核, 直接访问内存单元.

  • I/O映射式

    内核通过IN/OUT这种专门的外设I/O指令.(外部设备的存储单元和内存分属两个不同的体系)

2.11.1 内存映射

Linux 的虚存映射是通过ioremap()建立的, 通常内存映射是由缺页异常引起的被动建立, 但是ioremap()则是
先准备一个物理存储区间, 地址为外设在总线的存储器地址.(注意这里并非一定是存储单元在外设卡上的物理地址,这里隐含了一层地址映射).

┌─────────────────────────────────┐
│                                 │ 
│                                 │ 
│       0x0000f00000000000        │  ---> PCI: 0
├─────────────────────────────────┤
│                                 │
│                                 │
│                                 │
│                                 │
│                                 │
│                                 │
│                                 │
│                                 │
└─────────────────────────────────┘

比如这里PCI总线上的图形卡上的存储器是从地址0开始, 装载到总线上的物理地址可能是从0x0000f00000000000开始.
但是这里仅仅是总线地址, 而非虚拟地址, 所以需要建立映射, 这个函数原名是vremap()后称为irremap()(这里是从物理地址到虚拟内存的反向映射)

由__ioremap()实现:

/* arch/i386/mm/ioremap.c 92*/

/*
 * Remap an arbitrary physical address space into the kernel virtual
 * address space. Needed when the kernel wants to access high addresses
 * directly.
 *
 * NOTE! We need to allow non-page-aligned mappings too: we will obviously
 * have to convert them into an offset in a page-aligned mapping, but the
 * caller shouldn't need to know that small detail.
 */
void * __ioremap(unsigned long phys_addr, unsigned long size, unsigned long flags)
{
	void * addr;
	struct vm_struct * area;
	unsigned long offset, last_addr;

	/* Don't allow wraparound or zero size */
	last_addr = phys_addr + size - 1;
	if (!size || last_addr < phys_addr)
		return NULL;

	/*
	 * Don't remap the low PCI/ISA area, it's always mapped..
	 */
	if (phys_addr >= 0xA0000 && last_addr < 0x100000)
		return phys_to_virt(phys_addr);

	/*
	 * Don't allow anybody to remap normal RAM that we're using..
	 */
	if (phys_addr < virt_to_phys(high_memory)) {
		char *t_addr, *t_end;
		struct page *page;

		t_addr = __va(phys_addr);
		t_end = t_addr + (size - 1);
	   
		for(page = virt_to_page(t_addr); page <= virt_to_page(t_end); page++)
			if(!PageReserved(page))
				return NULL;
	}

	/*
	 * Mappings have to be page-aligned
	 */
	offset = phys_addr & ~PAGE_MASK;
	phys_addr &= PAGE_MASK;
	size = PAGE_ALIGN(last_addr) - phys_addr;

	/*
	 * Ok, go for it..
	 */
	area = get_vm_area(size, VM_IOREMAP);
	if (!area)
		return NULL;
	addr = area->addr;
	if (remap_area_pages(VMALLOC_VMADDR(addr), phys_addr, size, flags)) {
		vfree(addr);
		return NULL;
	}
	return (void *) (offset + (char *)addr);
}

解析:

  1. 首先进行sanity check, 判断地址不越出, 大小不为0, 没有覆盖VGA,BIOS的映射区, 不低于物理内存直接映射的地址上限(high_memory是全局变量.) 还需要保证物理地址是按页面4K对其.
  2. 通过get_vm_area来找到一片虚存地址空间来存放映射, 这段空间属于内核不属于任何特定进程.
    • 通过内核的虚存队列vmlist获取.
    • 内核委会一个内核专用的mm_struct为init_mm.

2.12 系统调用brk()

用户通过brk()向内核申请空间. (实际上用户使用库函数malloc()来调用系统调用brk())

┌───────────────┐
│               │ 
│    Kernel     │ 
│               │             
├───────────────┤
│    User       │
│    Heap       │
│    Stack      │
├───────────────┤
│               │
│  Free Space   │
├───────────────┤
│     .bss      │
├───────────────┤
│     .data     │
├───────────────┤
│     .text     │
└───────────────┘

从data段往上开始分配, 并记录边界, 内核记录在进程的mm_struct->brk里, 进程由库函数管理.
brk()由sys_brk()实现:

/* mm/mmap.c 113 */

/*
 *  sys_brk() for the most part doesn't need the global kernel
 *  lock, except when an application is doing something nasty
 *  like trying to un-brk an area that has already been mapped
 *  to a regular file.  in this case, the unmapping will need
 *  to invoke file system routines that need the global lock.
 */
asmlinkage unsigned long sys_brk(unsigned long brk)
{
	unsigned long rlim, retval;
	unsigned long newbrk, oldbrk;
	struct mm_struct *mm = current->mm;

	down(&mm->mmap_sem);

	if (brk < mm->end_code)
		goto out;
	newbrk = PAGE_ALIGN(brk);
	oldbrk = PAGE_ALIGN(mm->brk);
	if (oldbrk == newbrk)
		goto set_brk;

	/* Always allow shrinking brk. */
	if (brk <= mm->brk) {
		if (!do_munmap(mm, newbrk, oldbrk-newbrk))
			goto set_brk;
		goto out;
	}

	/* Check against rlimit.. */
	rlim = current->rlim[RLIMIT_DATA].rlim_cur;
	if (rlim < RLIM_INFINITY && brk - mm->start_data > rlim)
		goto out;

	/* Check against existing mmap mappings. */
	if (find_vma_intersection(mm, oldbrk, newbrk+PAGE_SIZE))
		goto out;

	/* Check if we have enough memory.. */
	if (!vm_enough_memory((newbrk-oldbrk) >> PAGE_SHIFT))
		goto out;

	/* Ok, looks good - let it rip. */
	if (do_brk(oldbrk, newbrk-oldbrk) != oldbrk)
		goto out;
set_brk:
	mm->brk = brk;
out:
	retval = mm->brk;
	up(&mm->mmap_sem);
	return retval;
}

解析:

  1. 通过brk参数判断新边界和旧边界之间的关系, 如果新边界要高于旧边界则说明是在申请分配空间, 反之释放.
  2. 释放使用do_mumap()函数解除物理映射关系.
  3. find_vma_prev()找到结束地址高于addr的第一个区间, 如找到返回vm_area_struct结构指针. 不同的是它还通过参数返回其前一区间结构的指针.
    TODO: 166

2.13 系统调用mmap()

一个进程可以通过mmap()将一个已经打开文件的内容映射到它的用户空间

mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);

参数fd 代表打开的文件, offset为文件的起点, 而start为映射到用户空间中的起始地址, length是长度, prot为访问模式(读写执行), flags为控制目的.

在2.4.0版本的内核中实现这个调用的函数为sys_mmap2(), 但是在老一些版本中使用的是old_mmap(), 他们的系统调用号不同, 所以还共存.

/* arch/i386/kernel/sys_i386.c 68 */
asmlinkage long sys_mmap2(unsigned long addr, unsigned long len,
   unsigned long prot, unsigned long flags,
   unsigned long fd, unsigned long pgoff)
{
   return do_mmap2(addr, len, prot, flags, fd, pgoff);
}

/* arch/i386/kernel/sys_i386.c 91 */

asmlinkage int old_mmap(struct mmap_arg_struct *arg)
{
   struct mmap_arg_struct a;
   int err = -EFAULT;

   if (copy_from_user(&a, arg, sizeof(a)))
   	goto out;

   err = -EINVAL;
   if (a.offset & ~PAGE_MASK)
   	goto out;

   err = do_mmap2(a.addr, a.len, a.prot, a.flags, a.fd, a.offset >> PAGE_SHIFT);
out:
   return err;
}

二者的区别在与传参, 主体实现都是do_mmap2(),


/* arch/i386/kernel/sys_i386.c 42 */
/* common code for old and new mmaps */
static inline long do_mmap2(
  unsigned long addr, unsigned long len,
  unsigned long prot, unsigned long flags,
  unsigned long fd, unsigned long pgoff)
{
  int error = -EBADF;
  struct file * file = NULL;

  flags &= ~(MAP_EXECUTABLE | MAP_DENYWRITE);
  if (!(flags & MAP_ANONYMOUS)) {
  	file = fget(fd);
  	if (!file)
  		goto out;
  }

  down(&current->mm->mmap_sem);
  error = do_mmap_pgoff(file, addr, len, prot, flags, pgoff);
  up(&current->mm->mmap_sem);

  if (file)
  	fput(file);
out:
  return error;
}

sys_execve(), 在load_auto_binary中可以看出通过do_mmap()将可执行程序映射到当前进程的用户空间.
此外do_mmap()还会创建进程间通信的共享内存区.

TODO: 185-192

中断, 异常和系统调用

TODO: 194-266

进程与进程调度

标签：#地址#系统调用 | 浏览：275 | 发布日期：

免责声明：文章转载自《《内核源码情景分析》（浙大）笔记》仅用于学习参考。如对内容有疑问，请及时联系本站处理。

上篇SAMBA服务器图像相关下篇

宿迁高防，2C2G15M，22元/月；香港BGP，2C5G5M，25元/月 雨云优惠码：MjYwNzM=

相关文章

2016.7.7 计算机网络复习要点第四章之网际协议IP

1.与IP协议配套使用的还有三个协议： **地址解析协议ARP； **网际控制报文协议ICMP； **网际组管理协议IGMP； 2.虚拟互连网络： **没有一种单一的网络能够适应所有用户的需求； **将网络互连起来要使用一些中间设备： （1）物理层使用的中间设备叫做转发器； （2）数据链路层使用的中间设备叫做网桥或者桥接器； （3）网络层使用的中间设备叫做...

Java判断IP地址类型(第二版)

1 import java.net.Inet4Address; 2 import java.net.Inet6Address; 3 import java.net.InetAddress; 4 import java.net.UnknownHostException; 5 6 /* 7 * 第一版判断Ipv4或者Ipv6是通过是通过长度来...

交换机安全学习笔记 第二章 MAC地址泛洪攻击

本文为书中相关知识的摘要，由于书中以思科设备为配置依据，所以笔记中补充了华为、H3C设备的相关配置。华为设备配置参考华为S2352EI 产品版本：V100R005C01文档版本：02。  H3C配置参考S7600系列文档（资料版本：6W102-20130226 产品版本：S7600系列—Release 6701及以上版本  S7600-X系列 —Relea...

火狐浏览器所有的快捷键

http://zhidao.baidu.com/link?url=-fpx6gbr3jdwvlTvDrGqBvTu-CHVmLFKLAqm5dSL8DaXYYFVtEt4fD1KsFvcQ_5u-Mn9geEjBv-7LWPwpiDWjKfirefox快捷键搜索类：本页查找： Ctrl+F再次查找： F3输入查找链接： '输入查找文本： /查找： Shif...

17.U-boot的工作流程分析-6410

17.U-boot的工作流程分析-6410 6410开发板： 1.uboot的入口： 要看uboot工程的入口，首先打开顶层目录的Makefile： Uboot所支持的开发板，在顶层的Makefile中都会有一个配置选项。比如6410，在Makefile中的配置选项是make forlinx_nand_ram256_config:在vim的命令模式按...

嵌入式 Linux下修改MAC地址

Linux下修改MAC地址 方法一： 1.关闭网卡设备ifconfig eth0 down2.修改MAC地址ifconfig eth0 hw ether MAC地址3.重启网卡ifconfig eth0 up 方法二：以上方法一修改后linux重启后MAC又恢复为原来的，为了下次启动时修改后的MAC仍有效，我们可以修改文件file:/etc/rc.d /...

最新文章

随机推荐

思享工具箱导航