CatBro's Blog

Volar con el viento

Linux内核中隐藏的兵法—以逸待劳

发表于 更新于 分类于 阅读次数： 评论数：
繁/简： 繁體
本文字数： 11k 阅读时长 ≈ 10 分钟

在本系列之前的两篇文章无中生有与移花接木中，我们探究了Linux中的进程创建，它可以说是进程管理中最重要的内容之一（另一个是进程调度）。本文我们将介绍的内容则更多地属于是内存管理范畴。（当然这也是相对而言的，作为Linux内核中最核心的部分，进程管理、内存管理、中断管理相互之间都是紧密联系的。）

也许你已经注意到了，无论是fork还是execve都没有主动去分配内存执行拷贝或读取的动作。fork时只是拷贝了页表并设置为用户只读，而execve时则只是准备了新的LDT局部表以及堆栈中的参数和环境表，而并没有实际读程序到内存中。

这就是本文将讨论的页异常中断：写保护异常/写时复制机制和缺页异常。

后面的代码基于Linux 0.11

分页机制

为了更好地理解后面的内容，我们先简单介绍下分页机制。

地址转换

线性地址转换成物理地址的步骤如下：

  1. 首先从cr3寄存器中获取到页目录的地址
  2. 从线性地址的前10位获取到页目录项，页目录项中保存着对应页表的地址
  3. 从线性地址中间10位获取到页表项，页表项中保存着对应页框的地址
  4. 线性地址的最后12位即表示在页内的偏移值。
1
2
         31     22 21     12 11      0
线性地址: | 页目录项 |  页表项 | 页内偏移 |

页目录和页表

页目录和页表的表项结构如下：

1
2
 31             12 11   9    6 5   3   2   1  0
|页框地址           |AVAIL|0 0|D|A|0 0|U/S|R/W|P|

如前所述，页目录项的高20位保存对应页表的地址，页表项的高20位则保存对应物理页框的地址。因为页地址总是4KB对齐的，所以表项的低位12位可作他用。这里保存了一些标志位：

  • 其中最低位P表示该表项是否有效，如果P=1表示表项有效，P=1则表示该表项无效，不能用于地址转换。在地址转换过程中如果遇到表项无效，会引发缺页异常，尝试共享页面或者分配新页。
  • R/W是读写位，为0时表示只读，为1时表示可读写，该位只限制用户态，对内核态不起作用。页目录项中的R/W位对其所映射的所有页面起作用。如果碰到用户往只读的页面写数据，会引发写保护的页异常，尝试为进程分配新的空闲页。
  • U/S是用户/超级用户标志，如果为1那么所有特权级都能访问，如果为0则只有内核态可以访问。同样地，页目录项中的U/S位对其所映射的所有页面起作用。
  • A位是已访问标志，当处理器访问页表项映射的页面时，页表表项的这个标志就会被置为1。当处理器访问页目录表项映射的任何页面时，页目录表项中这个标志就会被置为1。处理器只负责设置该标志，操作系统可通过定期地复位该标志来统计页面的使用情况。
  • D位是已修改标志，当处理器对一个页面执行写操作时，就会设置对应页表表项的D标志。

写时复制机制/写保护页异常

延迟页面拷贝

之前介绍fork的核心参数copy_process时，我们提到了其中的copy_mem在拷贝内存时是写时复制，但是并没有详细展开。我们先来看copy_mem()函数的实现：

1
2
3
4
5
6
7
8
9
int copy_mem(int nr,struct task_struct * p)
{
    unsigned long old_data_base,new_data_base,data_limit;
    unsigned long old_code_base,new_code_base,code_limit;

    code_limit=get_limit(0x0f);
    data_limit=get_limit(0x17);
    old_code_base = get_base(current->ldt[1]);
    old_data_base = get_base(current->ldt[2]);

首先是获取代码段的限长和基址

1
2
3
4
if (old_data_base != old_code_base)
    panic("We don't support separate I&D");
if (data_limit < code_limit)
    panic("Bad data_limit");

做些检查，Linux 0.11中代码段与数据段的基址是相同的，且数据段限长大于代码段。

1
2
3
4
new_data_base = new_code_base = nr * 0x4000000;
p->start_code = new_code_base;
set_base(p->ldt[1],new_code_base);
set_base(p->ldt[2],new_data_base);

设置新的代码段和数据段基址到LDT中

1
2
3
4
5
6
7
    if (copy_page_tables(old_data_base,new_data_base,data_limit)) {
        printk("free_page_tables: from copy_mem\n");
        free_page_tables(new_data_base,data_limit);
        return -ENOMEM;
    }
    return 0;
}

最后调用copy_page_tables对页表进行拷贝。可以看到这里只复制了数据段的页表。（因为Linux 0.11所有进程是共享页目录的，且Linux 0.11中代码段和数据段的基址是相同的，数据段长度不小于代码段，所以这里只需要复制数据段即可。）

（Linux 0.11中最多支持同时64个进程，每个进程的线性基址根据其进程编号*64MB得到，即上面代码中的nr * 0x4000000。）

既然只是复制了页表，页面的复制推迟到某一方进行写操作时，那么推迟复制这个动作是怎么实现的呢？这就需要跟到copy_page_tables()里面一探虚实了：

1
2
3
4
5
6
7
8
9
10
11
12
int copy_page_tables(unsigned long from,unsigned long to,long size)
{
    unsigned long * from_page_table;
    unsigned long * to_page_table;
    unsigned long this_page;
    unsigned long * from_dir, * to_dir;
    unsigned long nr;

    if ((from&0x3fffff) || (to&0x3fffff))
        panic("copy_page_tables called with wrong alignment");
    from_dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */
    to_dir = (unsigned long *) ((to>>20) & 0xffc);

from_dir和to_dir是根据源段和目的段线性基址获取其在页目录中的目录项指针。结合前面分页机制中地址转换的介绍，可以知道((from>>20) & 0xffc)其实就是线性地址前10位的值*4，因为每个页目录项是4个字节所以乘以4转换成了页目录项指针。所以from_dir和to_dir分别是源进程和目的进程的页目录项指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
size = ((unsigned) (size+0x3fffff)) >> 22;
for( ; size-->0 ; from_dir++,to_dir++) {
    if (1 & *to_dir)
        panic("copy_page_tables: already exist");
    if (!(1 & *from_dir))   // 源目录项未被使用，跳过
        continue;
    from_page_table = (unsigned long *) (0xfffff000 & *from_dir);
    if (!(to_page_table = (unsigned long *) get_free_page()))
        return -1;  /* Out of memory, see freeing */
    *to_dir = ((unsigned long) to_page_table) | 7; // User, R/W, Present
    nr = (from==0)?0xA0:1024;
    for ( ; nr-- > 0 ; from_page_table++,to_page_table++) {
        this_page = *from_page_table;
        if (!(1 & this_page)) // 源页表项未被使用，跳过
            continue;
        this_page &= ~2;     // 目的页表项的R/W位置0，表示用户只读
        *to_page_table = this_page;
        if (this_page > LOW_MEM) {
            *from_page_table = this_page;  // 不是LOW_MEM，源页表项所指内存页也只读
            this_page -= LOW_MEM;
            this_page >>= 12;
            mem_map[this_page]++;
        }
    }
}
invalidate();  // 刷新TLB地址变换高速缓存
return 0;

接下来就是两层循环对页目录项、页表项进行循环拷贝操作了。注意如果页目录项或页表项的最后1位为0（P位为0表示没有使用），则跳过。

注意这一行this_page &= ~2，这里将页表项的R/W位置0，表示目的页对用户只读。最后如果源页面不是LOW_MEM，那么源页表项的R/W位置也置0，同时增加了该页面的引用计数。正是通过这一动作，实现了推迟复制。

但是这里将LOW_MEM排除了，所以在进程0第一次fork进程1的时候，进程0对其内存页仍然是可写的，并没有写时复制。所以进程0在main函数中的fork和pause才需要使用内嵌函数的形式，避免使用堆栈。如果进程0先将堆栈改了，然后进程1后面要写栈时复制的栈就是坏的。

这还只是实现了写时复制机制（copy-on-write）的其中一半，这里只是将页面复制推迟了。写时复制机制（copy-on-write）的另外一半发生在写保护的页异常时。

写保护的页异常

前面在拷贝页表项时已经将其R/W位置0，当后面用户往这个只读的页面写数据时，会引发写保护的页异常，尝试为进程分配新的空闲页。具体代码如下：

1
2
3
4
5
void un_wp_page(unsigned long * table_entry)
{
    unsigned long old_page,new_page;

    old_page = 0xfffff000 & *table_entry;

参数table_entry是造成页异常的线性地址对应的页表项指针，old_page就是对应的物理页面地址。

1
2
3
4
5
if (old_page >= LOW_MEM && mem_map[MAP_NR(old_page)]==1) {
    *table_entry |= 2;
    invalidate();
    return;
}

如果不是低端内存且引用数为1，说明并没有被共享，直接将对应页表项的R/W置1即可。

1
2
if (!(new_page=get_free_page()))
    oom();

对于其他情况，则都需要分配一个新页

1
2
3
4
5
6
    if (old_page >= LOW_MEM)
        mem_map[MAP_NR(old_page)]--;
    *table_entry = new_page | 7;  // User, R/W, Present
    invalidate();
    copy_page(old_page,new_page);
}

然后将对应的页表项设置为新分配页的物理地址并设置最后3位标志。

注意：这里只修改了当前进程的页表项，所以其他共享这个页面的进程的页表项中仍然还是只读的状态，当它们试图执行写操作时也同样会引发写保护异常。

至此，写时复制机制的实现逻辑就完整了。

最后提一下invalidate()函数，因为之前修改了页表，所以需要刷新TLB地址变换高速缓冲。这里是通过重置cr3寄存器来实现的。

页异常中断

中断产生

那么页异常中断是如何产生的呢？

CPU在寻址的过程中如果碰到了页面不存在或者是写保护的（根据页表项的中标志位判断），就会引发页异常中断。我们接下来就来完整地看下页异常中断的处理过程：

1
2
page_fault:
    xchgl %eax,(%esp)	# 栈顶错误码与eax交换

这部分的代码跟之前在介绍系统调用时有些类似。首先刚进入中断处理程序时栈指针位于下图esp0的位置，中断过程已自动将用户态原堆栈段ss、原用户态堆栈指针esp、状态寄存器eflags、原用户代码段cs、原用户代码eip入栈。对于页异常中断，CPU还会自动将一个错误码压栈，这个错误码用于说明导致异常发生的原因及状态，只用了最后3位。

  • 位0（P）：0表示页不存在，1表示页级保护
  • 位1（W/R）：0表示是读操作，1表示是写操作
  • 位2（U/S）：0表示在超级用户下执行，1表示在用户模式下执行

可以看到，这几位的意思跟页表项中最后3位的意思基本是一致的。

中断处理程序中第一件事就是将当前栈顶的值（即错误码）换到eax寄存器中。

1
2
3
4
5
6
7
8
9
pushl %ecx
pushl %edx
push %ds
push %es
push %fs
movl $0x10,%edx		# 内核数据段选择符
mov %dx,%ds
mov %dx,%es
mov %dx,%fs

接着将一些用到的寄存器压栈，然后将ds、es、fs都设置为了内核数据段选择符。

1
2
3
4
5
6
7
8
9
    movl %cr2,%edx      # cr2是导致异常的线性地址
    pushl %edx
    pushl %eax
    testl $1,%eax       # 测试错误码的P位
    jne 1f
    call do_no_page
    jmp 2f
1:  call do_wp_page
2:  addl $8,%esp

随后从cr2寄存器中获取到导致异常的线性地址，将线性地址和错误码分别压栈，作为后面调用的C函数的参数。然后根据错误码的最低位P位决定调用缺页处理函数还是写保护处理函数。

内核堆栈情况

依旧来看下内核堆栈的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
HIGH  +----------------------+
      |          |  prev ss  |
      +----------------------+
      |       prev esp       |
      +----------------------+
      |        eflags        |
      +----------------------+
      |          |  prev cs  |
      +----------------------+
      |       prev eip       |
      +----------------------+
      |         eax          |<-- esp0
      +----------------------+
      |         ecx          |
      +----------------------+
      |         edx          |  
      +----------------------+
      |          |     ds    |
      +----------------------+
      |          |     es    |
      +----------------------+
      |          |     fs    |
      +----------------------+
      |         cr2          |
      +----------------------+
      |      error_code      |
      +----------------------+
      |         eip          |<-- esp1
LOW   +----------------------+

刚进入中断处理程序时栈指针位于esp0的位置，接着将用到的寄存器ecx、edx、ds、es、fs分别压栈，然后将cr2和错误码压栈，作为调用的处理函数的参数。进入具体的处理函数之后，堆栈指针位于esp1位置。

因为写保护的页异常处理函数我们前面已经看过了，接下来就来看下缺页处理函数。

缺页异常

处理函数

1
2
3
4
5
6
7
8
9
void do_no_page(unsigned long error_code,unsigned long address)
{
    int nr[4];
    unsigned long tmp;
    unsigned long page;
    int block,i;

    address &= 0xfffff000;
    tmp = address - current->start_code;

首先将线性地址页对齐，然后计算其相对进程代码段起始地址的偏移。

1
2
3
4
if (!current->executable || tmp >= current->end_data) {
    get_empty_page(address);
    return;
}

紧接着如果当前进程没有对应的可执行程序，或者线性地址已经超出了数据段末尾，那就不是代码或数据段的页面，也就不可能共享其他进程的页面，也不需要额外的初始化操作，所以直接申请新的物理页面返回即可。

1
2
3
4
if (share_page(tmp))
    return;
if (!(page = get_free_page()))
    oom();

否则，就调用share_page()尝试共享页面，如果共享成功了就直接返回，否则就只能老老实实分配新的物理页面了并初始化了。共享页面的部分我们稍后再看，先继续看缺页处理函数的剩余部分。

1
2
3
4
block = 1 + tmp/BLOCK_SIZE;
for (i=0 ; i<4 ; block++,i++)
    nr[i] = bmap(current->executable,block);
bread_page(page,current->executable->i_dev,nr);

如果没找到共享页面，那么就只能自己从磁盘中读取。从偏移地址tmp计算出缺页所在的数据块项，获取其在设备上对应的逻辑块号。因为Linux 0.11是使用的MINIX 1.0文件系统，将两个扇区作为一个数据块来处理，称之为磁盘块或盘块，所以1页是4个磁盘块。

1
2
3
4
5
6
i = tmp + 4096 - current->end_data;
tmp = page + 4096;
while (i-- > 0) {
    tmp--;
    *(char *)tmp = 0;
}

如果新增的这个页面正好是数据段的最后一页，那么该页其中一部分可能会超出end_data，需要对这部分内存进行清零操作。

1
2
3
4
5
    if (put_page(page,address))
        return;
    free_page(page);
    oom();
}

最后就是将物理页面映射到线性地址，即修改对应页表项。成功了直接返回，失败了说明内存不够了，释放新的那个页面之后oom()。

共享页面

share_page()函数也有点意思，它尝试找到一个进程可以和当前进程共享页面。我们来详细看一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static int share_page(unsigned long address)
{
    struct task_struct ** p;

    if (!current->executable)
        return 0;
    if (current->executable->i_count < 2)
        return 0;
    for (p = &LAST_TASK ; p > &FIRST_TASK ; --p) {
        if (!*p)
            continue;
        if (current == *p)
            continue;
        if ((*p)->executable != current->executable)
            continue;
        if (try_to_share(address,*p))
            return 1;
    }
    return 0;
}

函数主体是遍历进程数组，尝试共享页面，不过首先要确保当前进程和被共享的进程是相同的可执行程序。核心函数是try_to_share()，我们来看下它的实现：

1
2
3
4
5
6
7
8
9
10
11
static int try_to_share(unsigned long address, struct task_struct * p)
{
    unsigned long from;
    unsigned long to;
    unsigned long from_page;
    unsigned long to_page;
    unsigned long phys_addr;

    from_page = to_page = ((address>>20) & 0xffc);
    from_page += ((p->start_code>>20) & 0xffc);
    to_page += ((current->start_code>>20) & 0xffc);

最前面部分是计算页目录的位置，跟之前在copy_page_tables()中看到的类似。因为参数address传的是一个相对偏移，所以需要加上进程的代码段起始地址。

1
2
3
4
5
6
from = *(unsigned long *) from_page;
if (!(from & 1))
    return 0;
from &= 0xfffff000;
from_page = from + ((address>>10) & 0xffc);
phys_addr = *(unsigned long *) from_page;

接下来就检查页目录项最后1位，即确认是否存在相应的页表，如果不存在直接返回0，否则从页目录项中获取页表基址，加上线性地址中表示页表项的部分，获取到相应页表项。

1
2
if ((phys_addr & 0x41) != 0x01)
    return 0;

然后检查页表项，如果页面不存在或者是脏的，直接返回0。

1
2
3
phys_addr &= 0xfffff000;
if (phys_addr >= HIGH_MEMORY || phys_addr < LOW_MEM)
    return 0;

如果物理地址超出了系统最大支持的范围，或者属于内核空间，直接返回0。

1
2
3
4
5
6
7
to = *(unsigned long *) to_page;
if (!(to & 1)) {
    if ((to = get_free_page()))
        *(unsigned long *) to_page = to | 7;
    else
        oom();
}

走到这里说明已经找到可以共享的页面了，from的部分搞定了。接下来就是修改to的部分，首先检查目的页目录项，如果相应的页表不存在，需要分配。

1
2
3
4
to &= 0xfffff000;
to_page = to + ((address>>10) & 0xffc);
if (1 & *(unsigned long *) to_page)
    panic("try_to_share: to_page already exists");

然后获取到页表项，如果目的页面已经存在说明出现bug了，直接panic。

1
2
3
4
5
6
7
8
    *(unsigned long *) from_page &= ~2;
    *(unsigned long *) to_page = *(unsigned long *) from_page;
    invalidate();
    phys_addr -= LOW_MEM;
    phys_addr >>= 12;
    mem_map[phys_addr]++;
    return 1;
}

最后就是进行共享操作了，将源和目的的页表项的R/W位都设成只读，刷新TLB地址变换高速缓存，并增加对应物理页面的引用计算。这段代码是不是有点似曾相识，在fork中进行页表的拷贝时也有类似的操作。被共享的页面，如果后面碰到了写操作，同样会引发页写保护异常。

malloc测试

用户分配内存其实只是分配了虚拟内存，真正分配物理内存要推迟到用户对内存进行访问时。我们可以尝试malloc一个非常大的内存试试，下面的测试代码malloc了100G的内存，然后分别在第1个字节和最后一个字节进行写操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>

int main()
{
        char *p = malloc(107374182400); /* 100G */
        printf("p: %p\n", p);
        p[0] = 1;
        printf("p[0] = 1 ok\n");
        p[107374182399] = 1;
        printf("p[107374182399] = 1 ok\n");
        sleep(30);
}

我们来实际测试下，可以看到这些操作都成功了。

1
2
3
4
5
6
# echo 1 > /proc/sys/vm/overcommit_memory
# gcc test.c
# ./a.out
p: 0x7faeb88cc010
p[0] = 1 ok
p[107374182399] = 1 ok

观察进程内存的占用情况，可以看到虚拟内存占用到了100G，但是实际使用的物理内存只有700多K。

1
2
3
4
5
6
7
# cat /proc/`pgrep a.out`/status
Name:	a.out
...
VmSize:	104862108 kB
...
VmRSS:	     760 kB
...

总结

到这里我们以逸待劳（貌似用它来形容并不是完全确切，但我暂时想不到更好的词了🤷‍♂️）的部分也结束了，这应该算是内核内存管理中最核心的部分了。

无论是缺页异常还是写保护页异常，其背后的基本思想是一致的，也就是实际物理内存的分配能推迟就推迟。毕竟内存是稀缺资源，分页机制本身引入的目的也是为了对内存的管理和使用更加精细。

其实，该思想在其他很多地方也都有类似的应用。例如图片的懒加载，重定位的延迟绑定等。前者只有当网页需要显示该图片时才加载，后者则当第一次加载外部符号时才进行绑定。它们都可以缩短主体操作的时间，以及避免不必要的开销。

相关文章推荐
-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道