avatar

Catalog
《Linux内核源代码情景分析》笔记

前言

原计划在7月份写一些与Linux内核相关的博客,6月份就都在看这方面的书了,问轩辕大哥要了份资源,其中一本就是毛德操老师的《Linux内核源代码情景分析》,在学习 Windows 内核时就曾久仰毛德操老师的大名,这本书确实不错,但在读完存储管理这一章后,我就放弃了,内容非常深入,但不结合代码一点点看,显然是读不明白的,另一方面,鉴于这是2001年就出版的基于2.4版本的 Linux 内核的书,属实有些旧了。同样经典的 ULK,LDD 以及红宝书,均是基于2.6版本 Linux 内核。

经过一个周末的筛选,接下来会选择红宝书(3本书中翻译的较为好的一本,另外2本不想去看英文原版)作为主要资料进行学习。并会从7月初开始,根据所学进度逐步更新 Linux 内核知识点。

本篇主要是先前阅读《Linux内核源代码情景分析》时记录下的我认为比较重要或者构思巧妙的点(主要是存储管理这一章节的内容)。

笔记

耐人寻味的do-while

参考P17~18,这个宏操作为什么要通过一个do-while循环来定义呢?

#define DUMP_WRITE(addr,nr) do { memcpy(bufp,addr,nr); bufp += nr; } while(0)

绕人的宿主结构体

参考P21中rmqueue()的例子,如何通过结构体中的字段,算出宿主结构体的地址。

((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

Ubuntu的常规工具

  • gcc:编译
  • objdump:反汇编

LDT的设计初衷

参考P37,Intel的设计意图是内核用GDT而各个进程都用其自己的LDT。但实际上,不光Windows内核不用LDT,Linux内核也不怎么用(除了运行wine或其它模拟运行Windows软件时才使用)。

Linux中的段寄存器

参考P38,虽然Intel的意图是将一个进程的映像分成代码段、数据段和堆栈段,Linux内核却并不买这个帐。在Linux内核中堆栈段和数据段是不分的。

卑微的段式保护机制

参考P40,要不是 i386 CPU中的 MMU 规定先作段式映射,然后才可以作页式映射,那就根本不需要段描述符和段寄存器了。所以,这里 Linux 内核只不过是装模做样地糊弄 i386 CPU,对付其检查比对而已。

段式存储管理的特殊系统调用

参考P43,modify_ldt(int func, void \*ptr, unsigned bytecount),用来实现WINE(WINdows Emulation)的系统调用,可以改变当前进程的局部段描述符表,也就有办法侵犯到其它进程或内核的空间中去。一方面它确实是在内存管理机制上开了一个小小的缺口,但另一方面它的背后仍然是 Linux 内核的页式存储管理,只要不让用户进程掌握修改页面目录和页面表的手段,系统就还是安全的。

Linux中对页的管理

参考P45~49,内核中有个全局变量 mem_map,是一个指针,指向一个 page 数据结构的数组(物理页面的仓库),每个 page 数据结构代表着一个物理页面,整个数组就代表着系统中的全部物理页面。这个 mem_map 相当于 Windows 系统中一个记录所有物理页信息的全局数组的指针 MmPfnDatabase

”仓库“中有管理区(常规的2个管理区:ZONE_DMA, ZONE_NORAML;用于物理地址超过 1GB 存储空间的管理区:ZONE_HIGHMEM)的概念,不同于 Windows 中的空闲页与活动状态页。

物理空间的均匀性

参考P49,均质存储结构(Uniform Memory Architecture),是一种理想化的物理空间结构,即CPU访问这个空间中的任何一个地址所需的时间都相同。随着非均质存储结构的引入(Non-Uniform Memory Architecture)物理页面管理机制也作了相应的修正。管理区不再是属于最高层的机构,而是在每个存储节点中都有至少两个管理区。而且 page 结构数组(mem_map)也不再是全局性的,而是从属于具体的节点了。从而,在 zone_struct 结构(以及 page 结构数组)之上又有了另一层代表着存储节点的 pglist_data 数据结构。

Linux中的映射内存

参考P52,有两种情况下虚存页面会跟磁盘文件发生关系。一种是盘区交换(swap),参考缺页异常的处理流程。另一种情况则是将一个磁盘文件映射到一个进程的用户空间中。Linux 提供了一个系统调用 mmap(),使一个进程可以将一个已经打开的文件映射到其用户空间中,此后就可以像访问内存中一个字符数组那样来访问这个文件的内容,而不必通过 leek()、read() 或 write() 等进行文件操作。这部分内容类似 Windows 中的映射内存

Linux虚拟内存管理中数据结构间的联系

参考2.3 几个重要的数据结构和函数。这一节介绍了多个数据结构,mm_struct 和 vm_area_struct 说明了(进程)对页面的需求;page、zone_struct 等结构则说明了(物理内存)对页面的供应;而页面目录、中间目录以及页面表则是二者中间的桥梁。其关系如下所示:

页式存储管理机制下的越界访问

参考2.4节 越界访问P57~P60,这一节简略的分析了 Linux 系统中对缺页异常的处理函数 do_page_fault 的执行流程,里面提到了一个 task_struct 结构,它是描述进程的数据结构,从它可以修改线程的 Cr2 的值来看,task_struct 结构有点类似 Windows 内核中的 EProcess 或 KProcess 结构体。

P59,提到关于 Linux 中越界的一个定义:回忆一下内核对用户虚存空间的使用,堆栈在用户区的顶部,从上向下伸展,而进程的代码和数据都是自底向上分配空间。如果没有一个区间的结束地址高于给定的地址,那就是说明这个地址是在堆栈之上,也就是 3G 字节以上。要从用户空间访问属于系统的空间,那当然是越界了。

同样是P59,关于空洞。在用户虚存空间中,可能有两种不同的空洞。第一种是堆栈区以下的那个大空洞,它代表着供动态分配(通过系统调用 brk() )而仍未分配出去的空间;第二种我的理解就是缺页异常时,页内容被换出去,P=0,但PTE不为空的那种情况。在2.5节 用户堆栈的扩展这一节中,有对第一种情况异常处理的分析。

页面增长量计算

参考P62,当发生缺页异常,原因是进程堆栈空间不足时(属于正常的堆栈扩展要求情况下),需要扩充堆栈。首先将地址按页面边界对齐,并计算需要增长几个页面才能把给定的地址包括进去(通常是一个)。这里的代码逻辑我很喜欢,特此记录下来:

grow = (vma->vm_start - address) >> PAGE_SHIFT;

文件操作函数表中的内存分配函数

参考P66,在虚存区间结构 vm_area_struct 中有个指针 vm_ops,指向一个 vm_operations_struct 数据结构。这个数据结构实际上是一个函数跳转表,结构中通常是一些与文件操作有关的函数指针。其中有一个函数指针就是用于物理内存页面的分配。在这一节中,还涉及到对写保护部分代码实现的分析。

中断与异常的返回

参考P69,中断返回后,会从下一条指令开始执行;异常返回后,会重新执行导致异常的那条指令。

2.1~2.5小结

参考P70,在系统的初始化阶段,内核根据检测到的物理内存的大小,为每一个页面都建立一个 page 结构,形成一个 page 结构的数组,并使一个全局变量 mem_map 指向这个数组。同时,又按需要将这些页面拼合成物理地址连续的许多内存页面”块“,再根据块的大小建立起若干”管理区“(zone),而在每个管理区中则设置一个空闲块队列,以便物理内存页面的分配使用。

Linux内核对内存页面和盘上页面的管理

参考P70~73:

  • swap_info_struct:内核中定义的数据结构,用以描述和管理用于页面交换的文件或设备。

    • swap_map:指针,指向一个无符号短型数组;值代表盘上(或普通文件中)的一个物理页面,下标决定了该页面在盘上或文件中的位置。
      • swap_map[0]:所代表的页面不用于页面交换,它包含了该设备或文件自身的一些信息以及一个表明哪些页面可供使用的位图。
    • lowest_bit&highest_bit:供页面交换使用的范围区间。
    • max:该设备或文件中最大的页面号,即物理大小。
  • swap_info:swap_info_struct 结构的数组。

  • swap_list:将各个可以分配物理页面的磁盘设备或文件的 swap_info_struct 结构按优先级高低链接在一起。

  • swp_entry_t:类似 pte_t

    • offset:表示在一个磁盘设备或文件中的位置

    • type:指该页面在哪一个文件中,是个序号

    • 0:相当于 pte_t 的最低位 P 标志。指明页面不在内存,在磁盘上。

内存页面的周转

参考P74,并非所有的内存页面都是可以交换出去的。事实上,只有映射到用户空间的页面才会被换出,而内核,即系统空间的页面则不在此列。

物理内存页面换入/换出的周转要点

参考P76:

  1. 空闲。页面的 page 数据结构通过其队列头结构 list 链入某个页面管理区(zone)的空闲区队列 free_area。页面的使用计数 count 为0
  2. 分配。通过函数 _alloc_page() 或 __get_free_page() 从某个空闲队列中分配内存页面,并将所分配页面的使用计数 count 置成1,其 page 数据结构的队列头 list 结构则变成空闲。
  3. 活跃状态。页面的 page 数据结构通过其队列头结构 LRU 链入活跃页面队列 active_list,并且至少有一个进程的(用户空间)页面表项指向该页面。每当为页面建立或恢复映射时,都使页面的使用计数 count 加1。
  4. 不活跃状态(脏)。页面的 page 数据结构通过其队列头结构 LRU 链入不活跃 ”脏“ 页面队列 inactive_dirty_list,但是原则上不再有任何进程的页面表项指向该页面。每当断开页面的映射时都使页面的使用计数 count 减1。
  5. 将不活跃 ”脏“ 页面的内容写入交换设备,并将页面的 page 数据结构从不活跃 “脏” 页面队列 inactive_dirty_list 转移到某个不活跃 “干净” 页面队列中。
  6. 不活跃状态(干净)。页面的 page 数据结构通过其队列头结构 LRU 链入某个不活跃 “干净” 页面队列,每个页面管理区都有一个不活跃 “干净” 页面队列 inactive_clean_list。
  7. 如果在转入不活跃状态以后的一段时间内页面受到访问,则又转入活跃状态并恢复映射。
  8. 当有需要时,就从 “干净” 页面队列中回收页面,或退回到空闲队列中,或直接另行分配。

物理内存页面换入/换出的周转实现

参考P77,为了实现这种策略,在 page 数据结构中设置了所需的各种成分,并在内核中设置了全局性的 active_list 和 inactive_dirty_list 两个 LRU 队列,还在每个页面管理区中设置了一个 inactive_clean_list。根据页面的 page 结构在这些 LRU 队列中的位置,就可以知道这个页面转入不活跃状态后时间的长短,为回收页面提供参考。同时,还通过一个全局的 address_space 数据结构 swapper_space,把所有可交换内存页面管理起来,每个可交换内存页面的 page 数据结构都通过其队列列头结构 list 链入其中的一个队列。此外,为加快在暂存队列中的搜索,又设置了一个哈希表 page_hash_table。

P78~80,通过分析 add_to_swap_cache() 的执行流程,介绍了内核是如何将一个内存页面链入上述队列的。不过该函数具体实现,还是和上述描述有些差别。

多重身份的address_sapce

参考P79,通常来自同一个文件的页面就通过一个 address_space 数据结构来管理,而代表着一个文件的 inode 数据结构中有个成分 i_data,那就是一个 address_space 数据结构。从这个意义上说,用来管理可交换页面的 address_space 数据结构 swapper_space 只是个特例。

连续空间与不连续空间的alloc_pages()

参考P82。可见,参数 gfp_mask 在这里用作给定节点中数组 node_zonelists[]的下标,决定具体的分配策略。在连续空间 UMA 结构中只有一个节点 contig_pape_data,而在 NUMA 结构或不连续空间 UMA 结构中则有多个。

kswapd

参考P93,Linux 内核中设置了一个专司定期将页面换出的 “守护神” kswapd。从原理上说,kswapd 相当于一个进程,有其自身的进程控制块 task_struct 结构,跟其它进程一样受内核的调度。而正因为内核将它按进程来调度,就可以让它在系统相对空闲的时候来运行。不过,与普通的进程相比,kswapd 还是有其特殊性。首先,它没有自己独立的地址空间,所以在近代操作系统理论中称为 “线程” (thread)以示区别。那么,kswapd 使用谁的地址空间呢?它使用的是内核的空间。在这一点上,它与中断服务程序相似。其次,它的代码是静态地连接在内核中的,可以直接调用内核中的各种子程序,而不像普通的进程那样只能通过系统调用,使用预先定义好的一组功能。

kernel_thread()

参考P94,kernel_thread() 用来创建线程,例如 kswapd 和 kreclaimd 这两个线程:

c
1
2
kernel_thread(kswapd, NULL, CLONE_FS | CLONE_FILES | CLONE_SIGNAL);
kernel_thread(kreclaimd, NULL, CLONE_FS | CLONE_FILES | CLONE_SIGNAL);

kswapd() 每秒一次的例行路线会做些什么?

参考P97:

  • 预先找出若干页面,且将这些页面的映射断开,使这些物理页面从活跃状态转入不活跃状态,为页面的换出作好准备。该功能只有在发现物理页面出现短缺时才会执行。
  • 把已经处于不活跃状态的 “脏” 页面写入交换设备,使它们成为不活跃 “干净” 页面继续缓冲,或进一步回收一些这样的页面成为空闲页面。这个功能每次都会执行。

系统可供分配或周转的物理页面检查

参考P97,系统中应该维持的物理页面供应量由两个全局变量确定,freepages.high 和 inactive_target,分别为空闲页面的数量和不活跃页面的数量,二者之和为正常情况下潜在的供应链。这些内存页面的来源有3个方面:

  • nr_fress_pages() 统计的空闲页面,分散在各个页面管理区中,合并成地址连续的页面块形式存在。
  • nr_inactive_clean_pages() 统计的不活跃 “干净” 页面,也分散在各个页面管理区中,但不合并成块。
  • 由内核中的一个全局变量队列 nr_inactive_dirty_pages 统计的不活跃的 “脏” 页面,使用前要先将内容写入交换设备。

内核对进程虚存空间的管理

参考P164,那么,内核怎样管理每个进程的 3G 字节虚存空间呢?粗略的说,用户程序经过编译、连接形成的映像文件中有一个代码段和一个数据段(包括 data 段和 bss 段),其中代码段在下,数据段在上。数据段中包含了所有静态分配的数据空间,包括全局变量和说明为 static 的局部变量。这些空间是进程所必须的基本要求,所以内核在建立一个进程的运行映像时就分配好这些空间,包括虚存地址空间和物理页面,并建立好二者间的映射。除此之外,堆栈使用的空间也属于基本要求,所以也是在建立进程时就分配好的(但可以扩充)。所不同的是,堆栈空间安置在虚存空间的顶部,运行时由顶向下延申;代码段和数据段则在底部,在运行时并不向上伸展。而从数据段的顶部 end_data 到堆栈段地址的下沿这个中间区域则是一个巨大的空洞,这就是可以在运行时动态分配的空间。最初,这个动态分配空间是从进程的 end_data 开始的,这个地址为内核和进程所共知。以后,每次动态分配一块 “内存”,这个边界就往上推进一段距离,同时内核和进程都要记下当前的边界在哪里。在进程这一边由 malloc() 或类似的库函数管理,而在内核中则将当前的边界记录在进程的 mm_struct 结构中。具体地说,mm_struct 结构中有一个成分 brk,表示动态分配区当前的底部。当一个进程需要分配内存时,将要求的大小与其当前的动态分配区底部边界相加,所得的就是所要求的新边界,也就是 brk() 调用时的参数 brk。当内核能满足要求时,系统调用 brk() 返回0,此后新旧两个边界之间的虚存地址就都可以使用了。当内核发现无法满足要求(例如物理空间已经分配完),或者发现新的边界已经过于逼近设于顶部的堆栈时,就拒绝分配而返回-1。

系统调用 brk() 在内核中的实现为 sys_brk()。这个函数既可以用来分配空间,即把动态分配区底部的边界往上推;也可以用来释放,即归还空间。

系统调用 mmap()

参考P181,一个进程可以通过系统调用 mmap(), 将一个已打开文件的内容映射到它的用户空间,有点类似 Windows 上的 CreateFileMapping + MapViewOfFile 实现映射内存的过程。

参考资料

Author: cataLoc
Link: http://cataloc.gitee.io/blog/2021/07/02/Linux%E5%86%85%E6%A0%B8%E6%BA%90%E4%BB%A3%E7%A0%81%E6%83%85%E6%99%AF%E5%88%86%E6%9E%90%E8%AF%BB%E4%B9%A6%E7%AC%94%E8%AE%B0/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
    微信
  • 支付寶
    支付寶