linux 内核设计与实现阅读

linux 内核设计与实现（原书第 3 版）, Robert Love

• 一个内核由：负责响应中断的中断服务程序，负责多个程序分享处理器时间的进程调度程序，负责管理进程地址空间的内存管理程序和网络、进程间通信等系统服务程序组成。

• 应用程序通过系统调用访问内核，内核运行于进程上下文中。（不同进程运行同样的内核代码，上下文不同，因此有不同效果）

  • 对于中断来说，内核运行于中断上下文

• 单内核和微内核。linux 汲取了微内核的优点：linux 是模块化的，多线程的以及内核本身可调度的。

• inline 函数必须用 static 修饰，涉及到编译，因为 inline 的含义有点像宏。而如果不用 static 修饰，那么其他文件的函数也可以调用它，那么就会导致不得不建立一个符号表项。因此声明为 static 实现起来更简单。

• 内核使用的 C 语言用到了 ISO99 和 GUN C 扩展特性，其中几个用的比较广的 GUN C 扩展特性
  • 内联函数
  • 内联汇编

进程调度

• 每个 CPU 都有单独的运行队列 runqueue，每个 runqueue 实际包含两个 prio_array 结构的数据 active, expire。active 记录时间片还没有运行完的进程，expire 则是运行完的。prio_array 包含一个 bitmap 和实际的对应不同优先级的进程链表 struct list_head queue（queue[MAX_PRIO]），调度时 schedule():/kernel/sched.c 更具 bitmap 找到非空的最高优先级的链表的第一个进程作为全局优先级最高的进程。

• 重新分配时间片，task_timeslice() 根据任务的静态优先级（用户指定的 nice 值）分配时间片。默认 nice 为 0 为 100ms。

• 降低交互进程响应时间：每个定时器中断会调用 scheduler_tick()，该函数减少任务的时间片，如果减为 0 了，则判断该进程是否为交互性进程，如果不是，则添加到 expired 队列中，如果是且没有发生 expired 队列饥饿时，继续添加到 active 队列

• schedule 选择了下一个进程后，便通过 contex_switch 完成上下文交换。该函数通过则进一步通过以下两个函数实现

  • asm/mmu_contex.h:switch_mm：切换虚拟内存
  • asm/system.h:switch_to：实现处理器状态切换

• 什么时候调用 sechdule

  • 内核通过 need_resched 标志来表明是否需要重新执行一次调度。
    • 当时间片耗尽时 scheduler_tick 设置
    • 当更高优先级的进程进入可执行状态时，try_to_wake_up 设置

  • 用户抢占

    当内核即将返回到用户空间时，如果 need_resched 被设置，那么就会调用 schedule，从而发生用户抢占

  • 内核抢占

    linux 实现了内核抢占。在不支持内核抢占的系统中，内核代码可以一直执行。

  • 实时

    linux 支持 SCHED_FIFO 和 SCHED_RR 两种试试调度策略。FIFO 不适用时间片，会比任何 SCHED_NORMAL 的进程都先得到调度。一旦一个 SCHED_FIFO 处于执行状态就会一直执行，直到显示释放处理器为止。

系统调用

• 系统调用应该提供机制 (mechanism)（需要提供什么功能）而不是策略 (policy)（怎么使用这些功能）（驱动设计也应该这样）
• 系统调用内核实现，需要在函数前添加 asmlinkage 限定词，告诉编译器仅从栈中提取该函数的参数。
  • 在内陷到内核空间之前，需要将系统调用号和参数都放到寄存器里（多于 5 个则传递一个用户空间指针），然后触发软中断 (int $0x80)，执行 128 号异常处理程序。该程序对应系统调用处理程序 system_call，在 entry.S 中用汇编实现。system_call 再将参数（从寄存器中获得）传递给真正的系统调用函数 sys_xxx。
  • 在看过的 mips ucore 中实现中，system_call 不是用汇编实现的，已经是 C 了。参数之类的都放在中断帧（内核栈中一个数据结构）里（包含各种寄存器）
  • x86-64 中添加了 sysenter 的指令
• copy_to_user 和 copy_from_user
• 即使添加了自己的系统调用，由于 libc 库没有进行 wrap，因此用户程序需要通过汇编进行系统调用。linux 提供了相关宏——_syscalln，简化了该步骤

中断处理程序

• 中断上下文：

  当执行系统调用或运行内核线程时，内核处于进程上下文。而当内核执行中断处理程序时，内核处于中断上下文。

  中断栈：曾今，中断处理程序共享被中断进程的内核栈。2.6 版本后，中断处理程序有了自己的栈，大小为 1 个页，即 4KB。

• 中断处理程序不再进程上下文中运行，因此不能阻塞

• 过程

  • 注册中断

    int request_irq(unsigned int irq,
        irqreturn_t (*handler)(int, void *, struct pt_regs *)),
        unsigned long irqflags,
        const char *devname,
        void *dev_id)
    

    • irq 为要分配的中断号，对于传统 PC 设备，该值通常是预先定义的
    • handler 为中断处理程序
    • irqflags
      • SA_INTERRUPT：快速中断，在禁止本地 CPU 上的所有中断情况下运行。
      • SA_SHIRQ：共享中断线

  • 处理器某管脚接收到设备中断信号，关闭中断系统，跳转到中断程序入口点开始执行

    注：x86 中，对于每个中断号都会跳转到不同入口点

  • 入口点代码将中断号压栈，存放寄存器，然后调用 do_IRQ()

    unsigned int do_IRQ(struct pt_regs regs)
    

  • do_IRQ 判断中断线上是否有注册的中断处理程序，并调用 handle_IRQ_event 进行处理。

    注 1：前面说到，CPU 接收到中断后，关闭了中断系统。在这里，如果 IRQ 类型不是 SA_INTERRUPT，则会重新打开中断。

    注 2：共享中断线的中断处理程序：依次调用在该中断线上注册的每一个程序。中断处理程序需要判断是否自己注册的设备产生了中断（通过检查硬件状态寄存器）

  • 没有或者处理完后，则调用 ret_from_intr() 进行中断返回。

下半部

• 上半部和下半部

  • 一个中断处理程序正在执行时，同一个中断线在所有处理器上都会被频闭掉。
  • 因此同一个中断程序不会被嵌套调用，从而简化了中断处理程序的编写。
  • 对于 SA_INTERRUPT 类型中断，本地处理器的所有中断被禁用
  • 缩短中断被屏蔽时间对系统响应时间和性能很重要

• 中断处理程序必须尽可能快速的完成，因此整个中断处理流程被分为了上下两部分。应尽可能将任务放到下半部执行，除了以下情况：

  • 对时间非常敏感
  • 和硬件相关
  • 要保证不被其他中断打断

• 内核实现下半部的方式：

  • 软中断 (2.3)
  • tasklet(2.3)
  • workqueue(2.5)

• 软中断

  • 一个 32 个表项数组用于注册软中断。
  • do_softirq()
  • 什么时候触发软中断
    • 中断处理程序退出前
    • 在 ksoftirq/n 内核线程中
  • 避免加锁来提高性能
  • 相同类别的软中断可能在不同处理器上同时执行

• tasklet

  • 基于软中断实现
  • 不同类型的 tasklet：HI_SOFTIRQ, TASKLET_SOFTIRQ。
  • 相同类别的 tasklet 不能同时执行，不同类型 tasklet 可以同时执行
  • 避免软中断处理函数有触发软中断，导致用户空间进程饥饿。引入 ksoftirq，当大量软中断出现时，内核唤醒一组内核线程来处理这些负载，运行在最低优先级（nice 值为 19），保证最终肯定会被执行。

• workqueue

  • 可以阻塞
  • 由内核线程代为执行（一般使用默认的，也可以自己创建），可以调度

内核同步介绍

• 用户程序并发执行情形
  • 伪并发：进程被抢占，并重新调度。在被抢占期间，另一个进程可能访问临界区
  • 多核处理器，进程并行执行（真并发）

• 内核并发执行情形
  • 内核也支持抢占调度（换句话说，如果内核不支持抢占，那么单核情况，内核正常情况就不会遇到并发问题）
  • 中断
  • SMP

• 在写代码时就需要考虑加锁，而不是写完了之后再加锁
• 中断安全代码
• SMP 安全代码
• 抢占安全代码
• 刚开始锁的粒度都很粗，但是当锁的竞争变得严重时，设计就向更精细的加锁方向进化

内核同步实现

• 原子操作

  • 原子操作，比如 atomic_inc() 需要将内存中一个变量加 1。原子操作需要硬件支持
  • 原子性和顺序性：原子性表示操作是不可分割的，要么执行完要么不执行。而同步性表示多条指令即使执行在多个核上，他们间的顺序也依然要保持。通过屏障 (barrier) 实现

• 锁

  • 临界区要进行的操作可能非常复杂，因此无法仅使用简单的原子操作。此时便需要引入锁的机制。

  • 自旋锁 spinlock：

    • 自旋锁最多只能被一个线程持有
    • 当一个线程试图获得一个已经被持有的锁时，就会进入循环忙等待，直到锁被释放。
    • 适用于小的临界区
    • 可以在中断处理程序中使用（不会进入睡眠）

    • 中断处理程序获取自旋锁之前，需要禁止本地中断。否则，其它中断处理程序可能打断当前代码，并试图去获得已经被持有的锁，造成死锁。

      • spin_lock_irqsave(&mr_lock, flags) ...//临界区 spin_unlock_irqrestore(&mr_lock, flags)

    • 读/共享/S 锁，写/排它/X 锁

      当有大量读锁被占有时，可能导致写者饥饿

  • 信号量

    • 一个任务试图获得一个被占用的信号量时，信号量将其推进一个等待队列，然后让其睡眠。当持有信号量的进程将信号量释放后，将等待队列中的任务唤醒，并获得该信号量
    • 信号量支持多个进程持有同一个信号量，在声明信号量时指定，称为使用者数量。为 1 时则是二值信号量
    • 信号量支持两个原子操作，P(), V()，来自荷兰语 Proberen(探查), Vershogen(增加)。linux 中叫做 down() 和 up()。

  • seq 锁：读之前保存一个序列值，读操作之后再检查以下序列值是否变化。没变化则说明临界区时没有写操作发生，否则循环重新读取。对写者有利。

    • ```c write_seqlock(&sl) ... write_sequnlock(&sl)

      do{ seq = read_seqbegin(&sl) ... }while(read_seqretry(&sl, seq)) ```

    • 代码位于 include/linux/seqlock.h
    • write_seqlock 和 write_sequnlock 都会将 sl 内部的 seq 增加 1
    • 对于写者来说，可以直接进入临界区
    • 对于读者来说，如果第一次读取到的 seq 是奇数，则说明有写者进入了临界区，需要重新读。或者第一次读取到的 seq 和第二次读取到的不一致，说明。在读者进入临界区后，有写者进入了临界区，也需要重新读。
    • 为了防止有多个写者进入临界区，write_seqlock 中也使用了自选锁实现。

• 代码：

  • 原子整数操作：arch/*/include/atomic.h
  • 自旋锁：spinlock.h
  • 信号量：semaphore.h，rwsem.h

定时器和时间管理

• 系统定时器：为内核提供一个周期性的时钟中断，节拍可以设置
  • 节拍(tick)，节拍率 (tick rate) 也叫 HZ
  • 节拍率一般为 1000（早期为 100），不同体系结构也不一样
  • 节拍率更高可以提高时间驱动事件的解析度 resultion（感觉可以理解为粒度），单也会导致时钟中断负载变大。
  • 不使用周期时钟？有人尝试使用动态编程定时器来驱动一些事件（设定多少时间后触发中断）

• RTC 实时时钟：记录墙上时间，用于系统启动时初始化 xtime 变量

  • 当前实际时间（墙上时间）存储在 xtime 变量中，定义于 kernel/timer.c。timespec 定义在中

    struct timespec xtime
    struct timepsec{
     time_t tv_sec;
     long tv_nsec;
    }
    

• 时钟中断处理程序

  • 分为体系结构相关部分和无关部分 (do_timer) 两部分
  • do_timer 需要
    • 对 jiffies_64 加 1
    • 执行到期的动态定时器
    • scheduler_tick()
  • 根据中断发生在用户空间还是内核空间，将任务的用户时间和系统时间增加 1。然而由于在一个节拍期间可能多次进入和退出内核，因此实际上并不足够精确。

• 通过 sys_gettimeofday 系统调用获得墙上时间

• 定时器（内核定时器）(kernel/timer.c)

  • ```c struct timer_list my_timer;

    init_timer(&my_timer);

    my_timer.expires = jiffies + delay; my_timer.data = 0; my_timer.function = my_function;

    add_timer(&my_timer);

    mod_timer(&my_timer, jiffies+new_delay); del_timer(&my_timer);

    ```

  • 实现

    • 时钟中断处理程序执行 update_process_timers()，该函数调用 run_local_timers()

      void run_local_timers(){
       raise_softirq(TIMER_SOFTIRQ);
      }
      

    • 即定时器作为软中断在下半部中执行
  • 不能使用定时器来实现硬实时任务

• 实现延迟执行

  • 忙等待

    • 下面的代码延迟两秒

      unsigned long delay = jiffies + 2*HZ;
      while(time_before(jiffies, delay))
       ;
      

    • C 编译器通常只会将变量 load 一次，这样的话上面的代码使用的 jiffies 就不对（jiffies 在后台随时钟中断不断被更新）。因此需要使用 volatile，关键字 volatile 指示编译器在每次访问变量时都重新重内存中读取。

  • 短延迟

    • 如果需要延迟的时间短于一个节拍
    • 内核中提供延迟微秒和毫秒的函数 udelay 和 mdelay（linux/delay.h）
    • udelay 通过执行数次循环实现，而不是 jiffies

    • BogoMIPS

      • 内核在启动时利用 calibrate_delay 计算 loops_per_jiffy，位于 init/main.c

      • BogoMIPS 表示处理器执行空循环时，执行指令的速度（相当于 CPU 频率），单位：百万/s

        因此：BogoMIPS = loops_per_jiffy * HZ / 500000。因为一个 loop 需要两条指令。

    • 现在一般使用硬件定时器实现，更加精确。（CPU 频率会变化）

内存管理

• struct page:

  内核给每个物理页都分配一个 page 结构体。虽然看上去很消耗内存，但是实际上不到 1/100，并且是值得的。

• struct zone:

  • 不同体系结构 zone 的划分不一样
  • ZONE_NORMAL
  • ZONE_DMA：DMA 可以使用的
  • ZONE_HIGHMEM：无法永久映射到内核地址空间

• 内核启动时初始化：mm/page_alloc.c

• 请求内存的底层机制，以页为单位请求内存：

  分配 2^order 个连续的物理页，并返回第一个页对应 page 指针

  struct page * alloc_pages(unsigned int gfp_mask, unsigned int order)
  

  把给定的页转换成逻辑地址

  void *page_address(struct page *page)
  

  直接返回请求的第一个页的逻辑地址

  unsigned long __get_free_pages(unsigned int gfp_mask, unsigned int order)
  

  获得一个页

  struct page*alloc_page(unsigned int gfp_mask)
  

  释放

  void __free_pages(struct page *page, unsigned int order)
  void free_pages(unsigned long addr, unsigned int order)
  void free_page(unsigned long addr)
  

• kmalloc：

  • c void *kmallock(size_t size, int flags)
  • 获得以字节为单位的一块连续的内核内存

  • flag

    • 行为修饰符：如不能睡眠
    • 区修饰符
  • kfree：释放不是 kmalloc 分配的或则已经被释放的内存可能导致严重的后果

• vmalloc

  • 虚拟地址是连续的，而物理地址无需连续。
  • vmalloc 一般在获得大块内存时使用：需要建立页表项，性能低

• slab 分配器

  • 作用：避免频繁分配和释放页。

    • slab 负责底层的对齐、着色、分配、释放等等
    • 如果需要频繁创建很多相同类型的对象，应该使用 slab，而不是自己创建空闲链表。

  • 比较特殊的几点

    • 让部分缓存专属于单个处理器，那么分配和释放就可以在不加 SMP 锁的情况下进行
    • 对存放的对象进行着色 (colored)，可以防止多个对象映射到相同的 cache line

  • 原理：

    • 频繁使用的数据结构会被频繁分配和释放，因此需要缓存它们。
    • 使用不同的 cache 来缓存不同的对象，如用于存放进程描述符，索引节点的对象
    • cache 由若干个 slab 组成，一个 slab 包含若干个连续的物理页
    • slab 可能为处于：满，部分满，空三种状态之一。优先在部分满的 slab 中分配对象。

  • 接口

    • 创建一个 cache

      kmem_cache_t *kmem_cache_create(const char *name, size_t size,
                                      size_t align, unsigned long flags,
                                      void (*ctor)(void *, kmem_cache_t *, unsigned long),
                                      void (*ctor)(void *, kmem_cache_t *, unsigned long))
      

      • size 为对象的大小
      • align 为第一个对象的偏移，通常为 0

      • flags

        • SLAB_HWCACHE_ALGIN：命令 slab 层把每一个对象按 cache line 对齐，防止两个对象地址不同但映射到相同的 cache line

          注：不太明白，cache line 大小对齐不仍然会映射冲突吗？

        • SLAB_POISON：使用已知的值填充 slab
        • SLAB_PANIC：分配失败时体形 slab 层。在要求分配必须成功时有用，比如系统启动时分配 VMA 结构的 cache。

    • 创建 cache 后，获得一个对象

      void *kmem_cache_alloc(kmem_cache_t *cachep, int flags)
      

      如果 cache 中所有 slab 都没有空闲的对象，则通过 kmem_getpages 获取新的页。

      void *kmem_cache_alloc(kmem_cache_t *cachep, void *objp)
      

  • 内核栈

    • 不像用户进程，栈的大小可以动态增长，内核栈的大小是固定的。
    • 每个进程都有一个内核栈（内核运行在进程上下文），内核栈的大小一般是两个页。（可以编译时配置为 1 个页）
    • 在过去，中断处理程序和被中断进程共享内核栈，之后引入了中断栈，每个进程有一个中断栈

虚拟文件系统

• 复习
  • 磁盘结构
    • CHS geometry
    • Logic Block Address
  • 分区格式：MBR, GPT
    • MBR 分区格式在 fdisk, parted 等工具中一般标记为 dos 格式
    • MBR(Master boot record) 位于第一个扇区，因此分区表不能太大，最多支持 4 个 primary 分区，如果需要多于 4 个分区，则需要使用 extend 分区+logic 分区的方式。
    • MBR 也限制了最大只能支持 2TB 的磁盘
  • 文件系统

• VFS 作用：提供统一接口，支持不同文件系统

• Unix 文件系统采用了面向对象设计风格，使用了 4 中不同数据结构：超级块、索引节点、目录项、文件对象，每种数据结构都包含对其进行操作的函数

  • 其中超级块、索引节点在 Unix 风格的文件系统中有对应的磁盘数据结构
  • 如果要支持非 Unix 风格的文件系统，则仍然需要在内存中构造响应数据结构
  • 内存中的数据结构相比磁盘中的会多一些控制信息

• 超级块：包含文件系统的控制信息。也叫文件系统控制块。

  • 当一个文件系统被挂载到一个目录时，内核通过 alloc_super 创建超级块，并填充相关数据（从磁盘读取）

• 索引节点 inode

  • 索引节点存储文件的元数据（如控制权限，大小，拥有者，创建时间）

    • Unix 将文件信息和文件本身分别存储

  • Unix 风格的文件系统中，索引节点存储在磁盘单独的块中

    • 没有索引节点的文件系统通常将信息作为文件的一部分存储起来
  • 目录被当作一种特殊的文件，可以像文件一样进行操作

  • 查找文件

    It starts at the beginning of the path name and looks up the inode of the first directory in the path. Then it uses that inode to look up the next directory in the path. When it reachs the end, it has found the inode of the file or directory it is trying to look up. But since it needs an inode to get started, how does it get started with the first lookup? There is an inode pointer kept in the superblock called s_mounted which points at an inode structure for the filesystem. T

• 目录项 dentry

  • 指向一个 inode

• 目录项缓存 dcache

  • 用于快速路径解析

• 文件对象

  • 进程打开一个文件时创建，包含文件当前位置、访问模式等信息。
  • 现在还不清楚，文件对象是不是每个进程私有的。
  • 实现文件共享：不同进程的文件对象可以指向相同的 dentry 和 inode

块 I/O 层

• 字符设备太简单，因此没有子系统。而块设备有
• 扇区是块设备的最小寻址单元，通常为 512 字节。
  • 可以叫做：设备块
• 块是文件系统的最小寻址单元，通常为 512B, 1KB 或 4KB。
  • 可以叫做：文件块，I/O 块

进程地址空间

Linux 内核完全注释 -0.12-v5.0-赵炯

• 汇编中任何一个地址引用都可表示为该文件中{区地址 + 偏移}或者绝对地址。前一种有利于链接时的重定位

• 程序员使用符号来命名对象，链接器使用符号进行链接操作，而调试器利用符号进行调试