Linux Kernel Development 读书笔记

发表于 | 分类于 | 阅读次数

调度

  • Linux 的进程调度是基于 “处理器比重” 策略，具体实现通过 vruntime 成员。所有进程以各自的 vruntime 作为 Key，链接成为一个 RBTree。调度核心通过查找最小的 vruntime 对应的进程，作为下一刻需要运行的进程。vruntime 作为进程调度的核心，那它的计算方法是什么？

  • 应用程序进行系统调用(system call)时，通过 软中断(soft irq) 陷入内核态，将 系统调用号 以及 参数指针 通过 CPU 通用寄存器 传入(exp. eax, ebx…)，由内核代表应用程序在 内核空间 执行系统调用。

  • Linux 内核常用的 内建数据结构 ： 链表 list， 队列 kfifo， 映射 idr， 二叉树 rbtree

中断

  • Linux 中断实现机制怎样？ 中断发生时，通过 中断向量表 跳转到预定义入口点。初始入口点将 中断号保存在栈中，然后跳转调用 unsigned int do_IRQ(struct pt_regs regs) 进行处理。因为 C 的调用惯例是要把函数参数放在 栈的顶部，因此可以从 pt_regs 结构中提取出中断号 进行进一步处理。

  • 什么是中断上下文？当执行一个中断处理程序时，内核即处于中断上下文 (interrupt context) 中。

  • 为什么中断里面不能休眠？ 因为没有后备进程，所以中断上下文不可以休眠，否则又怎能对它重新调度呢？ 这段话中的，后备进程 要怎么理解？ 中断栈又是什么鬼？

  • 为什么中断处理需要分成 上半部 和 下半部 ？ 上半部分 简单快速，执行的时候禁止一些或者全部中断。 下半部分 稍后执行，而且执行期间可以相应所有的中断。这种设计可使系统处于中断屏蔽状态的时间尽可能的短，以此来提高系统的相应能力。

  • softirq 和 sys_call 中的软中断意义是否一致？ 答案是：不一致！sys_call 中的软中断指的是 体系结构 预留的软中断，有固定的中断号，触发后 立即 经由中断向量表进行映射跳转；softirq 中的软中断仅仅是一种 软件机制，维护一组静态注册的回调函数列表，触发后 无法立即 回调处理函数，需等待时机 (硬中断代码返回、ksoftirqd 内核线程中、do_softirq 显示调用刷新)

  • softirq 中为什么不能休眠？ 难道是 softirq 是处于中断上下文 interrupt context？

  • tasklet 和 工作队列 的主要区别？ tasklet 是 基于 softirq 实现，调用者将目标 tasklet 注册到 __this_cpu（更好利用处理器的高速缓存）的 tasklet list 中，然后触发软中断等待执行，回调处理中 不允许休眠； 工作队列 是 基于 内核线程kthread 和 等待队列 waitqueue 实现，硬中断函数中唤醒对应内核线程，在线程函数中检查并遍历执行 worklist，回调处理中 允许调度及休眠 。

同步

  • 为什么全局变量自加操作，在多线程中是不安全的？ 请看以下例子：
线程 1 线程 2 线程 1 线程 2
获得 i (7) —— 获得 i (7) 获得 i (7)
增加 i (7->8) —— 增加 i (7->8) ——
写回 i (8) —— ——- 增加 i (7->8)
—— 获得 i (8) 写回 i (8) ——
—— 增加 i (8->9) —— 写回 i (8)
—— 写回 i (9)
  • 造成并发执行的原因？为什么数据需要同步？
    • Userspace： 用户程序在任何时刻都可能 被调度程序抢占和重新调度；
    • Userspace： 异步发生的 信号 处理（什么信号？）
    • Kernel： 中断 — 几乎可以任何时刻异步发生
    • Kernel： 软中断和 tasklet — 内核能在 任何时刻 唤醒或调度 软中断 和 tasklet ( 怎么理解这里的任何时刻？具体是什么 Case 下？ )
    • Kernel： 内核抢占 — 内核具有抢占性，内核中的任务可能会被另一任务抢占
    • Kernel： 睡眠及用户空间的同步 — 内核执行的进程可能会睡眠，这就会 唤醒调度程序，从而导致调度一个新的用户进程执行
    • Kernel： 对称多处理器 SMP — 两个或多个处理器可以同时执行代码
  • 在编写内核代码时，你要问自己下面这些问题：
    • 这个数据是不是全局的？除了当前线程外，其他线程能不能访问它？
    • 这个数据会不会在 进程上下文 和 中断上下文 中共享？它是不是要在两个不同的中断处理程序中共享？
    • 进程在访问数据时可不可能被抢占？被调度的新程序会不会访问同一数据？
    • 当前进程是不是会休眠（阻塞）在某些资源上，如果是，它会让共享数据处于何种状态？
    • 怎样防止数据失控？
    • 如果这个函数又在另一个处理器上被调度将会发生什么呢？
    • 如何确保代码远离并发威胁呢？

  • 常用的内核同步手段有哪些？简单介绍实现机制

    • atomic_t 原子操作：由 体系结构 提供的原子操作简单算术指令实现（经典用途：计数器）

    • spinlock 自旋锁：忙循环 - 旋转 - 等待，自旋锁不应被长时间持有。( rwlock 读写自旋锁 )

      由于下半部可以抢占进程上下文中的代码，所以当下半部和进程上下文共享数据时，必须对进程上下文中的共享数据进行保护，所以需要加锁的同时还要 禁止下半部执行 spin_lock_bh().

      同样，由于中断处理程序可以抢占下半部，所以如果中断处理程序和下半部共享数据的话，那么就必须在获取恰当的锁的同时还要 禁止中断 spin_lock_irqsave().

    • semaphone 信号量：基于等待队列实现的睡眠锁，适用于长时间持有的情况。( rwsem 读写信号量 & mutex 互斥信号量)

      函数 down_interruptible() 试图获取制定的信号量，如果信号量不可用，将把进程设置为 TASK_INTERRUPTIBLE 状态。而函数 down() 则会让进程在 TASK_UNINTERRUPTIBLE 状态下休眠，此状态无法响应其他信号了。所以 使用 down_interruptible() 比使用 down() 更为普遍（也更正确）

    • completion 完成变量：用于一个任务发出信号通知另一个任务发生了特定事件，实现思想和信号量一致。

    • seqlock 顺序锁：基于一个序列计数器实现，经典应用例程 jiffies。

    • preempt 禁止抢占：preempt_enable() or preempt_disable()

    • 顺序和屏障：处理多处理器和硬件设备之间的同步问题，确保跨越屏障的读／写不发生重排序，rmb(), wmb(), mb(), read_barrier_depends()

定时器

  • 内核中的 HZ 代表什么？ 赫兹 HZ 代表每秒钟 pre-second 时钟中断发生的次数，也代表定时器精度，是通过静态预处理定义的。

  • 内核中的 jeffies 怎么来的？ 全局变量 jeffies 用于记录自系统启动以来产生的节拍的总数 unsigned long volatile jeffies

    由于 jeffies 在 32-bit 机器上，字节数为 4 byte，存在 溢出后回绕 为 0 的问题。如果用户采用直接比较 jeffies 来判断时序，则有可能导致逻辑错误。因此内核提供了以下四个宏帮助比较节拍计数，正确处理节拍计数回绕问题：

    1
    2
    3
    4
    #define time_after(unknow, know)      ((long)(know) - (long)(unknow) < 0)
    #define time_before(unknow, know)     ((long)(unknow) - (long)(know) < 0)
    #define time_after_eq(unknow, know)   ((long)(unknow) - (long)(know) >= 0)
    #define time_before_eq(unknow, know)  ((long)(know) - (long)(unknow) >= 0)

  • 内核中的 xtime 全局变量用途？ xtime 是用来代表 wall time (实际时间)，RTC 模块主要在启动时协助初始化 xtime 变量。(xtime 全局变量的同步方式和 jeffies 一样，采用 seqlock 顺序锁同步)

    用户空间可以通过 gettimeofday() 系统调用来获取 wall time，内核也可以通过 do_gettimeofday() 来获取。

    1
    2
    3
    4
    struct timespec {
      _kernel_time_t tv_sec; /* second */
      long tv_nsec; /* ns */
    } xtime;

  • 可用的延时执行机制？说明简单实现

    • jeffies 忙等待：通过对 jeffies 进行判断，加上一定的空闲调度 cond_resched()；
    • udelay 短延时：依靠执行数次循环达到延时效果，循环次数是根据 BogoMIPS 参数进行比例换算；
    • schedule_timeout：结合 timer 和 schedule 实现；

      如果任务既要等待一个特定事件到来，又在等待一个特定时间到期，这时可以简单使用 schedule_timeout() 代替 schedule() + wait_queue；

内存管理与地址空间

  • 基本术语概念：页、区
    • Page 页：内存管理单元 (MMU，管理内存并把虚拟地址转换为物理地址的 硬件) 通常以页为单位进行处理，尽管处理器的 最小可寻址单位 通常是字（Or 字节）。大多数 32 位体系结构支持 4KB 的页，而 64 位体系结构一般会支持 8KB 的页
    • Zone 区：由于硬件存在缺陷而引起的内存寻址问题，内核并不能对所有页一视同仁，所以分成四种区：ZONE_DMA, ZONE_DMA32, ZONE_NORMAL, ZONE_HIGHMEM
      • 一些硬件只能用于某些特定的内存地址来执行 DMA.
      • 一些结构的内存的物理寻址范围比虚拟寻址范围大的多。这样，就有一些内存不能永久地映射到内核空间上
  • gfp_mask 分配器标志可分成三类：行为修饰符、区修饰符及类型。
    • 行为修饰符：标志内核应该如何分配所需的内存。（__GFP_WAIT 分配器可以休眠）
    • 区修饰符：表示内存区应当从何处分配。（默认从 ZONE_NORMAL 分配）
    • 类型标志：行为修饰符和区修饰符的指定组合。（GFP_KERNEL 常规分配可能会阻塞， GFP_ATOMIC 用在不能睡眠的上下文中）
  • Slab 分配器（Linux 通用数据结构缓存层）的 设计准则：
    • 频繁使用的数据结构也会频繁分配和释放，因此应当缓存它们；
    • 频繁分配和回收必然会导致内存碎片，难以找到大块连续的可用内存。为了避免这种现象，应采用空闲链表的来缓存存放；
    • 回收的对象可以立即投入下一次分配，因此对于频繁的分配和释放，空闲链表能够提高决策；
    • 如果分配器知道对象大小、页大小和总的高速缓存的大小，它会做出更正确的决策；
    • 如果让部分缓存专属于单个处理器，那么分配和释放就可以不加 SMP 锁；
    • ？如果分配器是与 NUMA 相关的，它就可以从相同的内存节点为请求者进行分配；
    • ？对存放的对象进行着色，以防止多个对象映射到相关的高速缓存行 (cache line)

  • Slab 对象管理模型：基于 动态增长 的高速缓存 cachep，将其分成两级 Slab 与 对象 进行管理。高速缓存以页为单位，划分成为多个 Slab（一般 Slab 暂用一页）。然后 Slab 再以对象大小为单位，管理多个对象的申请与释放。
    高速缓存、Slab 及对象之间的关系图

  • 如何理解：进程栈、内核栈、中断栈三者的关系？以及分别有何种用途？ 内核栈和中断栈分别独立占用一个页，其空间全部来至于进程栈。

  • precpu 每个 CPU 私有化数据资源的好处 ： 减少了 SMP 数据锁（需要禁止内核抢占）； 大大减少缓存失效；

  • mem_struct 与内核线程？ 内核线程没有进程地址空间，也没有相关的内存描述符。所以内核线程对应的进程描述符中 mm 域为空。事实上，这也正是内核线程的真实含义 - 它们没有用户上下文。当一个内核线程被调度时，内核发现它的 mm 域为 NULL，就会保留前一个进程的地址空间，随后内核更新内核线程对应的进程描述符中的 active_mm 域，使其指向前一个进程的内存描述符。因为内核线程不访问用户空间的内存，它们仅仅使用地址空间中和内核内存相关的信息。

  • 虚拟内存域 vm_area_struct 和 内存描述符 mm_struct 的关系？ mm_struct 描述整个进程的内存空间对象，vm_area_struct 是对进程内存空间进行区域划分，vm_area_struct 从属于 mm_struct。

    • 每个 VMA 对其相关的 mm_struct 结构体来说都是唯一的；所以即使两个独立的进程将同一个文件映射到各自的地址空间，它们分别都会有一个 vm_area_struct 结构体来标志自己的内存区域；
    • 同一个进程地址空间内的不同内存区域不能重叠；
    • Note: 可用使用 pmap $PID 来查看对应进程的虚拟内存域组织情况；

  • 页表：虽然应用程序操作的对象是映射到物理内存之上的虚拟内存，但是处理器直接操作的确实物理内存。所以当应用程序访问一个虚拟地址时，首先必须将虚拟地址转化为物理地址，然胡处理器才能解析地址访问的请求，而地址转化的过程就是页表查询的过程。

    地址转化需要将虚拟地址分段，使每段虚拟地址都作为一个索引指向页表，而页表项则指向下一级别的页表或者指向最终的物理页面。Linux 采用三级页表完成地址转化，三级页表名称分别为：PGD, PMD, PTE。
    虚拟地址通过页表找到物理地址的过程.png
    页表空间大小解析.png

    • TLB 翻译后缓冲器：由于几乎每次对虚拟内存中的页面访问都必须先解析它，从而得到物理内存中的对应地址，所以页表操作的性能非常关键。TLB 是一个将虚拟地址映射到物理地址的硬件缓存，当请求访问一个虚拟地址时，处理器将首先检查 TLB 中是否缓存了改虚拟地址到物理地址的映射，如果缓存命中，就不需要通过页表搜索对应的物理地址了。

转载请注明出处： http://kyang.cc/