本文同步自（如浏览不正常请点击跳转）：https://zohead.com/archives/linux-kernel-learning-block-layer/ Linux 内核中的 block I/O 层又是非常重要的一个概念，它相对字符设备的实现来说复杂很多，而且在现今应用中，block 层可以说是随处可见，下面分别介绍 kernel block I/O 层的一些知识，你需要对块设备、字符设备的区别清楚，而且对 kernel 基础有一些了解哦。 1、buffer_head 的概念： buffer_head 是 block 层中一个常见的数据结构（当然和下面的 bio 之类的结构相比就差多了哦，HOHO）。 当块设备中的一个块（一般为扇区大小的整数倍，并不超过一个内存 page 的大小）通过读写等方式存放在内存中，一般被称为存在 buffer 中，每个 buffer 和一个块相关联，它就表示在内存中的磁盘块。kernel 因此需要有相关的控制信息来表示块数据，每个块与一个描述符相关联，这个描述符就被称为 buffer head，并用 struct buffer_head 来表示，其定义在 <linux/buffer_head.h> 头文件中。 b_state 字段说明这段 buffer 的状态，它可以是 bh_state_bits 联合（也在上面的代码中，注释说明状态，应该比较好明白哦）中的一个或多个与值。b_count 为 buffer 的引用计数，它通过 get_bh、put_bh 函数进行原子性的增加和减小，需要操作 buffer_head 时调用 get_bh，完成之后调用 put_bh。b_bdev 表示关联的块设备，下面会单独介绍 block_device 结构，b_blocknr 表示在 b_bdev 块设备上 buffer 所关联的块的起始地址。b_page 指向的内存页即为 buffer 所映射的页。b_data 为指向块的指针（在 b_page 中），并且长度为 b_size。 在 Linux 2.6 版本以前，buffer_head 是 kernel 中非常重要的数据结构，它曾经是 kernel 中 I/O 的基本单位（现在已经是 bio 结构），它曾被用于为一个块映射一个页，它被用于描述磁盘块到物理页的映射关系，所有的 block I/O 操作也包含在 buffer_head 中。但是这样也会引起比较大的问题：buffer_head 结构过大（现在已经缩减了很多），用 buffer head 来操作 I/O 数据太复杂，kernel 更喜欢根据 page 来工作（这样性能也更好）；另一个问题是一个大的 buffer_head 常被用来描述单独的 buffer，而且 buffer 还很可能比一个页还小，这样就会造成效率低下；第三个问题是 buffer_head 只能描述一个 buffer，这样大块的 I/O 操作常被分散为很多个 buffer_head，这样会增加额外占用的空间。因此 2.6 开始的 kernel （实际 2.5 测试版的 kernel 中已经开始引入）使用 bio 结构直接处理 page 和地址空间，而不是 buffer。 2、bio： 说了一堆 buffer_head 的坏话，现在来看看它的替代者：bio，它倾向于为 I/O 请求提供一个轻量级的表示方法，它定义在 <linux/bio.h> 头文件中。 该定义中已经有详细的注释了哦。bi_sector 为以 512 字节为单位的扇区地址（即使物理设备的扇区大小不是 512 字节，bi_sector 也以 512 字节为单位）。bi_bdev 为关联的块设备。bi_rw 表示为读请求还是写请求。bi_cnt 为引用计数，通过 bio_get、bio_put 宏可以对 bi_cnt 进行增加和减小操作。当 bi_cnt 值为 0 时，bio 结构就被销毁并且后端的内存也被释放。 I/O 向量： bio 结构中最重要的是 bi_vcnt、bi_idx、bi_io_vec 等成员，bi_vcnt 为 bi_io_vec 所指向的 bio_vec 类型列表个数，bi_io_vec 表示指定的 block I/O 操作中的单独的段（如果你用过 readv 和 writev 函数那应该对这个比较熟悉），bi_idx 为当前在 bi_io_vec 数组中的索引，随着 block I/O 操作的进行，bi_idx 值被不断更新，kernel 提供 bio_for_each_segment 宏用于遍历 bio 中的 bio_vec。另外 kernel 中的 MD 软件 RAID 驱动也会使用 bi_idx 值来将一个 bio 请求分发到不同的磁盘设备上进行处理。 bio_vec 的定义也在上面的代码中，同样在 <linux/bio.h> 头文件中，每个 bio_vec 类型指向对应的 page，bv_page 表示它所在的页，bv_offset 为块相对于 page 的偏移量，bv_len 即为块的长度。 buffer_head 和 bio 总结： 因此也可以看出 block I/O 请求是以 I/O 向量的形式进行提交和处理的。 bio 相对 buffer_head 的好处有：bio 可以更方便的使用高端内存，因为它只与 page 打交道，并不直接使用地址。bio 可以表示 direct I/O（不经过 page cache，后面再详细描述）。对向量形式的 I/O（包括 sg I/O） 支持更好，防止 I/O 被打散。但是 buffer_head 还是需要的，它用于映射磁盘块到内存，因为 bio 中并没有包含 kernel 需要的 buffer 状态的成员以及一些其它信息。 3、请求队列： 块设备使用请求队列来保存等待中的 block I/O 请求，其使用 request_queue 结构来表示，定义在 <linux/blkdev.h> 头文件中，此头文件中还包含了非常重要的 request 结构： request_queue 中的很多成员和 I/O 调度器、request、bio 等息息相关。request_queue 中的 queue_head 成员为请求的双向链表。nr_requests 为请求的数量。I/O 请求被文件系统等上层的代码加入到队列中（需要经过 I/O 调度器，下面会介绍），只要队列不为空，block 设备驱动程序就需要从队列中抓取请求并提交到对应的块设备中。这个队列中的就是单独的请求，以 request 结构来表示。 每个 request 结构又可以由多个 bio 组成，一个 request 中放着顺序排列的 bio（请求在多个连续的磁盘块上）。 实际上在 request_queue 中，只有当请求队列有一定数目的请求时，I/O 调度算法才能发挥作用，否则极端情况下它将退化成 “先来先服务算法”，这就悲催了。通过对 request_queue 进行 plug 操作相当于停用，unplug 相当于恢复。请求少时将request_queue 停用，当请求达到一定数目，或者 request_queue 里最 “老” 的请求已经等待一段时间了才将 request_queue 恢复，这些见 request_queue 中的 unplug_fn、unplug_timer、unplug_thresh、unplug_delay 等成员。 4、I/O 调度器： I/O 调度器也是 block 层的大头，它肩负着非常重要的使命。由于现在的机械硬盘设备的寻道是非常慢的（常常是毫秒级），因此尽可能的减少寻道操作是提高性能的关键所在。一般 I/O 调度器要做的事情就是在完成现有请求的前提下，让磁头尽可能少移动，从而提高磁盘的读写效率。最有名的就是 “电梯算法” 了。 […]
Category: kernel
Linux kernel学习-内存管理
本文同步自（如浏览不正常请点击跳转）：https://zohead.com/archives/linux-kernel-learning-memory-management/ 接着之前的 Linux kernel 学习步伐，来到极其重要的内存管理部分，继续本文内容，需要先了解内存寻址的基础知识，见之前的 [内存寻址] 博文。 1、内存页及内存区域： 正如之前所说，Linux kernel 使用物理页作为内存管理的基本单位，其中重要的线程地址和物理地址的转换操作由页单元 MMU 来完成，系统的页表也由 MMU 来维护。kernel 使用 struct page 来表示一个物理页，它的定义在 include/linux/mm_types.h 头文件中： 其中的 flags 用于表示页的状态（是否为脏或者被锁定等），_count 即为页的引用计数，kernel 一般使用 page_count 宏调用 atomic_read 函数原子的读取此值，page_count 返回 0 表示此页可用。如果一个页被作为 page cache 使用，则 page 的 mapping 字段指向映射的 inode 的 address_space 对象，如果页被作为私有数据（作为 buffer_heads 缓冲、buddy 系统等），则 private 常包含对应的信息。注意其中的 virtual 字段为页的虚拟地址，结合之前的知识，对于高端内存来说，其并没有被固定映射到 kernel 地址空间中，因此如果 virtual 字段为 NULL，则表示此页必须被动态映射。 kernel 使用 page 结构记录系统中的所有页，因此 struct page 的大小应该要尽量小以减少内存占用，另外 kernel 必须知道页是否空闲，如果不空闲则拥有者是谁。 由于实际硬件限制，Linux kernel 不可能使用全部的物理内存，kernel 为此将内存划分为不同的区域，一个区域中的内存属性应该也相同。kernel 中常见的内存区域有 ZONE_DMA（可用于 DMA 的页）、ZONE_DMA32（与 ZONE_DMA 类似，但只对 32 位设备可用）、ZONE_NORMAL、ZONE_HIGHMEM（并没有被固定映射的高端内存区域），这些内存区域一般都是硬件相关的，例如在 x86 架构下，ZONE_DMA 的范围为 0MB - 16MB，ZONE_HIGHMEM 为高于 896MB 的物理内存，而在 x86_64 架构下 ZONE_HIGHMEM 则为空。需要注意的是内存的分配不会跨域这些不同的内存区域。内存区域在 kernel 中由 struct zone 结构来表示，其中的 name 字段即为内存区域名称。 2、获取页： 分配和释放内存是 Linux kernel 中极其重要又用的极多的接口。先看看 kernel 提供的直接获取以内存页面为单位的 alloc_pages 函数： struct page * alloc_pages(gfp_t gfp_mask, unsigned int order) 此函数是最基本的用于分配大小为 2^order 并且连续的物理页的函数，其返回分配到的第一个页面的 page 指针。 来看看比较重要的 gfp_t 类型的 gfp_mask 值： gfp_t 实际上就是 unsigned int 类型，gfp_mask 常用于指定行为方式、区域方式、类型等信息。常见的行为方式标志有：__GFP_WAIT（标志分配器可以睡眠，明显不适用于中断上下文中）、__GFP_IO（分配器可以启动磁盘 I/O）等。区域方式指定内存从哪里分配，对应的就有：__GFP_DMA、__GFP_DMA32、__GFP_HIGHMEM（从高端内存或普通内存中分配）。类型标志则用于简化分配时的指定操作，常见的有：GFP_ATOMIC（高优先级并不可睡眠，常用于中断、中断下半部、持有自旋锁等环境中）、GFP_NOIO（表示分配可中断但不可以发起 I/O 操作）、GFP_NOFS（分配时不可发起文件 I/O 操作）、GFP_KERNEL（最常见的分配标志，常用于可以睡眠的进程上下文中）、GFP_USER（用于分配内存给用户进程）、GFP_DMA 等。 需要注意的是对 __get_free_pages 和 kmalloc 函数（下面会分别说明）不能指定 __GFP_HIGHMEM 标志，因为它们都是直接返回的虚拟地址，而非 page 结构指针，如果指定了 __GFP_HIGHMEM，则他们可能分配到的内存并没有被映射到 kernel 地址空间，因此这样得不到虚拟地址。只有 alloc_page 函数可以分配高端内存，这个限制在下面的 __get_free_pages 函数的实现中可以看到。 使用 page_address 函数可以将 page 指针转换为虚拟地址（非物理地址）。实际使用中经常会用到 __get_free_pages 函数直接在分配页时直接得到虚拟地址，其参数为 alloc_pages 完全一样，看看它的实现就一目了然了： 另外 kernel 还 “好心” 的提供了两个只分配一个页的函数：alloc_page 和 __get_free_page，可以想象只是把 order 参数设为 0 而已。你可以使用 get_zeroed_page 函数分配一个页并自动清零（gfp_mask 指定 __GFP_ZERO）。 对应的释放页可以用 __free_pages（page 指针为参数）、free_pages（虚拟地址为参数）、free_page（只释放一个页）这些函数。 下面是常用的分配非整数倍页大小的内存的函数。首先是最常用的 kmalloc 函数： void *kmalloc(size_t size, gfp_t flags) kmalloc 用于分配最少指定的 size 字节大小的内存（实际分配的可能比 size 多），这与用户空间的 malloc 函数很相似，但需要注意的是 kmalloc 分配的内存物理地址是连续的，这非常重要。 相应的释放内存函数是 kfree： void kfree(const void *objp) kfree 用于释放 kmalloc 分配的内存，注意如果使用 kfree 在不是的 kmalloc 分配的内存地址或者已经 kfree 过的地址上，都可能导致 kernel 出错。 紧接着就是大名鼎鼎的 vmalloc 函数了。它与 kmalloc 类似，但它分配的内存只是虚拟连续的而物理地址却不一定连续，这也类似于用户空间的 malloc 函数的效果。vmalloc 由于需要做页表转换之类的操作，性能比 kmalloc 差，而且 vmalloc 得到的页还必须由单独的页来做映射，对 TLB 缓存的效率也会有影响（有关 TLB 缓存参考之前的文章 [内存寻址]），由于这些原因，vmalloc 在 kernel 中用到的机会并不是很多，其常用于分配大量的内存，常见的一个例子就是内核模块的代码就是通过 vmalloc 加载到 kernel 中的。vmalloc 的原型为： void * vmalloc(unsigned long size) 与之对应的，使用 vfree 释放分配的内存。另外 vmalloc 和 vfree 都是可以睡眠的，因此它们对中断上下文是不适用的。 3、Slab分配器： Slab 也是 Linux kernel 中非常重要的组成部分，它用于简化内存的分配和释放，它相当于一个可用内存列表，里面包含一堆已经分配好的数据结构，当 kernel 需要分配一个数据结构时，可以直接从这个可用内存列表中取出而节省分配的时间，不需要的时候又可以还给这个列表而不需要释放，因此这个列表用于缓存经常访问的某种类型的数据。为了统一管理和释放，Linux kernel 引入 Slab 分配器作为通用的数据结构缓存层给经常访问的数据结构使用。需要说明的是 kmalloc 就是在 Slab 分配器基础上实现的。 这里简单对 Slab 分配器做个介绍，有关其细节请参考这篇 PDF 文档： The Slab Allocator: An Object-Caching Kernel Memory Allocator Slab 层将不同的对象划分到名为 cache 的不同组中，每个组存储不同类型的数据，也就是每种数据类型都有一个 cache。每个 cache 然后被划分为多个 slab，slab 由一个或多个连续的物理页组成（通常只有一个页），每个 slab 又包含一些数量的对象，也就是实际缓存的数据。每个 slab 的状态可以是这三个中的一个：满、部分满、空。当 kernel 请求一个新对象时，优先从状态为 部分满 的 slab 中取，如果没有则从状态为 […]
Linux kernel percpu变量解析
本文同步自（如浏览不正常请点击跳转）：https://zohead.com/archives/linux-kernel-percpu-variable/ Linux 2.6 kernel 中的 percpu 变量是经常用到的东西，因为现在很多计算机都已经支持多处理器了，而且 kernel 默认都会被编译成 SMP 的，相对于原来多个处理器共享数据并进行处理的方式，用 percpu 变量在 SMP、NUMA 等架构下可以提高性能，而且很多情况下必须用 percpu 来对不同的处理器做出数据区分。 本文以 kernel 中的 softirq 为例简单说下 percpu 变量，我们先来看看 kernel 中唤醒 ksoftirqd 的实现，ksoftirqd 在 ps 命令看到的进程列表中很容易找到，是每个处理器都有一个（如果有 4 个处理器，则有 4 个 kernel 线程名称分别从 ksoftirqd/0 到 ksoftirqd/3），关于 softirq 本身的实现不在本文讨论范围内，唤醒 ksoftirqd 的实现在 kernel/softirq.c 文件中： 这里就用到了 percpu 变量 ksoftirqd，它是通过 DEFINE_PER_CPU 宏来进程定义的 percpu task_struct 列表，通过 __get_cpu_var 宏来得到相应处理器的 ksoftirqd/n 的 task_struct，然后调用 wake_up_process 函数唤醒进程（也就是 ksoftirqd/n kernel 线程），关于 wake_up_process 等进程调度的相关实现在之前的日志中有介绍的，请参考 [这里]。 __get_cpu_var、DEFINE_PER_CPU 等 percpu 宏的实现在 include/linux/percpu.h、include/asm-generic/percpu.h 等头文件中。先看看 include/asm-generic/percpu.h 中的一些定义： 通常所有的 percpu 变量是一起存放在特定的 section 里的，像上面头文件中的 .data.percpu 基础 section（ 当然非 SMP 系统下就是 .data 了）、.shared_aligned、.first section。使用 objdump 可以看到编译 kernel 时的 vmlinux 文件的 section（结果没有完全显示）： 可以看到 vmlinux 文件中的 .data 和 .data.percpu section。 percpu 变量的地址实际上就是其在上面说到的 section 里的偏移量，这个偏移量还要加上特定处理器的偏移量（也就是上面头文件中的 per_cpu_offset、my_cpu_offset 等）得到最终的变量地址，并最终以指针引用的方式得到值，这样访问的效果就有点类似于访问全局变量了。percpu 变量通常用于更新非常频繁而访问机会又相对比较少的场合，这样的处理方式可以避免多处理器环境下的频繁加锁等操作。 从上面的注释也可以看到 per_cpu_offset 是在一个 percpu 变量上增加的偏移量，大多数系统架构下使用 __per_cpu_offset 数组来作为偏移量，而 x86_64 等架构下处理方式则不同。my_cpu_offset 是在调用 per_cpu_offset 时使用 smp_processor_id() 得到当前处理器 ID 作为参数，__my_cpu_offset 则是用 raw_smp_processor_id() 的值作为 per_cpu_offset 的参数（smp_processor_id() 在抢占被关闭时是安全的）。SHIFT_PERCPU_PTR 宏用于给指针增加偏移量，它使用的 RELOC_HIDE 宏在不同的编译器下实现不同，在 include/linux/compiler.h 头文件中，看看 gcc 编译下的处理： 可以看到 gcc 中使用内嵌汇编先将 ptr 值赋给 __ptr（unsigned long 类型），然后在 __ptr 基础上增加偏移量，这样可以避免编译报错，ptr 值不变而且最终以 ptr 指定的类型来返回。 include/asm-generic/percpu.h 头文件中定义了 per_cpu、__get_cpu_var、__raw_get_cpu_var、this_cpu_ptr、__this_cpu_ptr 等几个常用的宏。per_cpu 就用于得到某个指定处理器的变量，__get_cpu_var 用于得到当前处理器的 percpu 变量值。 再来看看 DEFINE_PER_CPU 的实现，它在 include/linux/percpu-defs.h 头文件中： 使用 DEFINE_PER_CPU 宏可以静态的定义 percpu 变量。__PCPU_ATTRS 指定输入的 section 类型，DEFINE_PER_CPU_SECTION 用于在特定的 section 上定义特定类型的变量。__typeof__ 和 上面见到的 typeof 是一样的，都用于获取 type 的数据类型。__attribute__((section(xxx))) 表示把定义的变量存储在指定的 section 上。DEFINE_PER_CPU 就用于定义在 PER_CPU_BASE_SECTION section 上（从最开始的代码中也可以看出非 SMP 时用 .data 段，SMP 时用 .data.percpu 段）。 然后是 get_cpu_var 宏的实现，它在 include/linux/percpu.h 头文件中： get_cpu_var 会先禁止抢占然后调用 __get_cpu_var 得到 percpu 变量值。put_cpu_var 则重新启用抢占。 另外在 include/linux/percpu.h 等文件中还定义了 alloc_percpu 和 free_percpu 宏来动态定义和释放 percpu 变量，他们都是通过 percpu memory allocator 来实现的，在 mm/percpu.c 中，动态分配的 percpu 变量可以通过 per_cpu_ptr 宏来得到，为此 kernel 还引入了 this_cpu_ptr、this_cpu_read 等一系列相关机制用寄存器替代内存提高对 percpu 变量的访问速度，关于 percpu memory allocator 等信息以后再来详细分析了。 以上为个人分析结果，有任何问题欢迎指正咯 ^_^
Linux kernel kfifo分析
本文同步自（如浏览不正常请点击跳转）：https://zohead.com/archives/linux-kernel-kfifo/ kfifo 是 Linux kernel 中的一个通用队列实现，对于 kernel 中常见的 FIFO 队列应用还是很有用的，本文主要简单介绍分析下 Linux kernel kfifo。实际上 ChinaUnix 上有个 kfifo 的分析文章，但已经比较老（基于 Linux 2.6.10），而且我现在用的 2.6.34 版本 kernel 中 kfifo 实现有很多改动，故自己简单写下，ChinaUnix 上的 kfifo 介绍帖子在这里： http://bbs.chinaunix.net/thread-1994832-1-1.html kfifo 定义在 include/linux/kfifo.h 头文件中，我们经常使用的就是 kfifo 结构，看看它的定义： kfifo 也像其它队列那样提供了两个主要操作：入队列（in） 和 出队列（out），对应于上面结构中的 in 和 out 两个偏移量，in 偏移量为下次入队列的位置，out 为下次出队列的位置，很容易也能想到 out 值必须小于等于 in 值，当 out 值等于 in 值时表示队列为空，kfifo 中 buffer 为队列的空间，size 为空间大小，必须为 2 的 k 次幂值（原因在下面说明）。当然如果 in 值等于队列长度了，就表示队列已经满了。 先看看 kfifo 最简单的一些操作实现，在 kernel/kfifo.c 文件中： 调用 kfifo_alloc 可以自动分配空间并初始化，你也可以调用 kfifo_init 函数使用自己的空间来初始化队列，可以看到这两个函数中都用 is_power_of_2 做了检查队列空间的操作。kfifo_free 释放队列，它会调用 _kfifo_init 函数（参数为 NULL 和 0 清空队列），调用 kfifo_reset 可以重置队列（将 in 和 out 都设为 0）。你也可以用 DECLARE_KFIFO 和 INIT_KFIFO 静态定义一个 kfifo 队列，尽管这不太会被用到。 调用 kfifo_in 函数将数据加入队列，kfifo_out 将数据从队列中取出并从队列中删除（增加 out 值），Linux 还提供了 kfifo_out_peek 函数从队列中取数据但并不删除（不增加 out 值）。kfifo_in 中会先调用 __kfifo_in_data 将输入加入队列，然后调用 __kfifo_add_in 增加 in 的值，kfifo_out 相反则调用 __kfifo_out_data 和 __kfifo_add_out 函数取出数据并删除。 kfifo 中同时提供了 kfifo_from_user 函数用户将用户空间的数据加入到队列中，它会先调用 __kfifo_from_user_data 将用户空间的数据加入队列，再调用 __kfifo_add_in 增加 in 的值。看看 __kfifo_from_user_data 的实现： 可以看到 __kfifo_from_user_data 中是直接调用 copy_from_user 将用户空间的数据拷贝到 kfifo 队列的空间中。相应的也有 kfifo_to_user 函数将队列中的数据取出到用户空间的地址，他就调用 copy_to_user 将队列中数据拷贝到用户空间。 需要注意的是 __kfifo_from_user_data 中用到的 __kfifo_off 函数： __kfifo_off 是根据指定的偏移量得到索引值，由这里也可以看出为什么队列的大小为什么必须是 2 的 k 次幂值，否则无法得到正确的值。而且从代码中可以看到 __kfifo_from_user_data、__kfifo_in_n、__kfifo_in_rec 等函数中都用到了 __kfifo_off 函数指定加入队列时的偏移量。 另外从 include/linux/kfifo.h 中你也可以看到新的 kfifo 实现中默认 EXPORT 了非常多的 API 函数给 kernel 开发者使用。 以上为个人分析结果，有任何问题欢迎指正哦 ^_^
Linux kernel学习-进程调度
本文同步自（如浏览不正常请点击跳转）：https://zohead.com/archives/linux-kernel-learning-process-scheduling/ 接着上面进程基本概念的文章，进程调度器决定系统中什么进程需要运行，运行多长时间。Linux kernel 实现的是抢占式的时间片调度方式，而不是进程主动让出时间片的方式。 Linux 从 2.5 开始使用名为 O(1) 的调度器，它解决了 2.4 及之前早期的调度器中很多设计上就存在的问题，O(1) 就表示该算法可以在常数时间内完成工作。在 ULK3 对应的 2.6.11 内核中仍然在使用此调度器，它对于很大的服务器负载的情况是很理想的，但由于 O(1) 调度器对于延迟敏感的程序（被称为交互式进程）而言却有缺陷，因此从 2.6.23 内核开始 Linux 引入一种调度器类的框架，并且默认使用一种新的调度器：Completely Fair Scheduler（CFS）完全公平调度器，鉴于历史的车轮在前进着，本文就主要讨论 CFS 调度器了。 进程通常可以分为两类：I/O密集型 和 计算密集型。I/O密集型进程花费更多的时间在等待 I/O 请求上（不一定是磁盘I/O，也可以是键盘、网络 I/O 等），大多数的 GUI 程序都是 I/O密集型进程。计算密集型的进程则要求运行频率小些但运行时间更多，像各种加解密程序和 MATLAB 这种就是典型的计算密集型进程。一个好的调度策略应该能同时满足低延迟和高吞吐量，Linux 调度器会采取偏向I/O密集型进程的策略。 Linux kernel 实现了两种独立的进程优先级：一种是 nice 值，从 -20 到 +19，默认值为 0，越大的值表示优先级越低（表示你对其它进程更加 “nice”，哈哈），nice 值在所有 Unix 系统中是一个通用的进程优先级范围，运行 ps -el 可以看到进程的 nice 值；第二种是可配置的实时优先级，范围从 0 到 99，越大的值表示优先级越高，实时进程比普通进程的优先级高，Linux 根据 POSIX.1b Unix 标准实现了实现了实时优先级，运行 ps 时增加 rtprio 参数可以在 RTPRIO 栏中看到实时优先级（如果值为 - 表示不是实时进程）。 Linux 2.6.34 默认的 CFS 完全公平调度器并不像传统调度器那样，根据 nice 绝对值为相应的进程分配固定的时间片，它没有明确的时间片概念，而是根据每个进程的 nice 相对差异值作为权重得到进程可以运行的时间在处理器时间中的比例。CFS 设置了一个预定的 targeted latency 值作为调度持续时间来根据比例计算时间片，当然此值越小越接近完全公平。假设 targeted latency 值为 20 毫秒，系统中有两个进程 nice 值分别为 0 和 5，根据权重计算出来的时间片分别为 15 和 5 毫秒，当两个进程为 10 和 15 时，计算出来的仍然为 15 和 5 毫秒，因为 nice 值的相对差异值并没有变。在系统中进程不是特别多时，CFS 调度器可以做到接近完全公平，而进程数量特别多甚至接近无限时，每个进程获得的时间片将非常小，为了避免进程切换导致的开销，CFS 又规定了一个 minimum granularity 值作为每个进程最小的时间片，默认为 1 毫秒，也即即使进程无限，每个进程也最少能运行 1 毫秒的时间，因此进程特别多时 CFS 就不会那么公平了。 1、CFS调度器： CFS 调度器实现在 kernel/sched_fair.c 文件中，这在上面一篇博文：进程基本 中有简单的介绍的。CFS 使用 sched_entity 调度实体结构，task_struct 中就有这个成员，看看 sched_entity 的定义，它定义在 include/linux/sched.h 头文件中： 可以看到此结构中下面很大一部分是开启了 CONFIG_SCHEDSTATS 之后才有用的。其中 vruntime 为进程的虚拟运行时间（实际运行时间经可运行的进程个数进行权重计算后的结果），在理想的 CFS 环境中，处理器都处于理想状态，所有同级别的进程的 vruntime 值应该都相同。但实际上多处理器不能做到完美多任务，CFS 调度器就用 vruntime 记录进程的运行时间并得到它应当还要运行多长时间。 再看到下面会用到的 cfs_rq 运行队列属性的定义，在 kernel/sched.c 中定义： cfs_rq 中的 curr 字段即指向当前队列上正在运行的实体（如果没有则为 NULL 了），rq 字段即为 CPU 运行队列。 来看看 sched_entity 的 vruntime 是如何在 update_curr 函数中更新的： update_curr 会被系统定时器周期性的调用，进程转变为可运行或不可运行状态时都会被调用，而 update_curr 本身则调用 __update_curr 增加实际运行时间和 vruntime 虚拟运行时间。 由于实际情况下，每个进程的 vruntime 并不会像理想状况那样完全一样，CFS 调度器在需要调度时从运行队列里中取 vruntime 最小的那个进程来运行。CFS 调度器使用一个红黑树来管理可运行进程的列表，并用于快速查找最小的 vruntime 进程。 红黑树在 Linux 中被称为 rbtree，可以用于存储任意数据的节点，由特定的关键字来标识。sched_entity 调度实体中的 run_node 就是一个红黑树节点，cfs_rq 中的 rb_leftmost 即是红黑树最左边的节点（缓存在 cfs_rq 结构中以加快访问速度，这样可以避免遍历红黑树），最小的 vruntime 进程就在此节点上，如果找不到此进程（返回 NULL），CFS 唤醒 idle 任务。 看看将进程加到红黑树的实现： enqueue_entity 中更新了当前进程的 vruntime，并最终调用 __enqueue_entity 将进程加到红黑树中。__enqueue_entity 中先通过遍历找到正确位置，遍历过程中就能确定红黑树中最左边的节点是什么，然后设置红黑树中节点左右信息，调用 rb_link_node 添加节点，必要时更新 cfs_rq 中保存的最左边的节点缓存。 好吧，看了添加过程再看从红黑树中删除进程： 同样 dequeue_entity 先调用 update_curr 更新当前进程的 vruntime，删除的实际操作由 __dequeue_entity 来完成。__dequeue_entity 中判断如果最左边节点正是要删除的进程，必须更新最左边的节点缓存，然后调用 rb_erase 删除节点。 Linux 中进程调度入口是 schedule() 函数，定义在 kernel/sched.c 中。对于一个进程，schedule() 会先查找最高优先级的调度器类并调用此调度器类中的函数进行调度。看看 pick_next_task 的实现： 首先由于 Linux 普通进程默认使用 CFS 调度器，pick_next_task 先判断是不是所有进程都在 CFS 调度器中，如果是就直接调用 CFS 的 pick_next_task 函数节省遍历时间。sched_class_highest 的定义在上面也可以看到，就是 RT 调度器类，for_each_class 用于遍历调度器类。而其它类中找不到时，idle 调度器类的 pick_next_task 就返回一个有效 task_struct。在 CFS 调度器中 pick_next_task 会调用 pick_next_entity 函数选择下一个运行的进程。 2、睡眠与唤醒： 进程需要睡眠时，kernel 的处理大体如下：进程将自己标记为睡眠状态，将自己加到等待队列，从记录可运行进程的红黑树上删除自己，调用 schedule() 选择新进程来运行，schedule() 会调用 deactivate_task() 函数将进程从运行队列中移除。唤醒的过程则相反：进程被设置为可运行，从等待队列删除，重新加回到红黑树中。 等待队列在 kernel 中以 wait_queue_head_t 表示，定义在 include/linux/wait.h 头文件中，它其实是一个 __wait_queue_head 结构，下面的头文件中有一些经常用到的声明： 需要注意的是每个等待队列都需要可以在中断时被修改，因此操作等待队列之前必须获得一个自旋锁。而在实际使用中等待时需要处理竟态条件，为此 kernel 定义了几个很好用的等待条件的宏，为调用者减少操作，这些宏也是定义在上面的文件中。常用的有 wait_event 根据条件在队列上无限等待，wait_event_timeout 相对加了超时处理，它是调用 schedule_timeout 进行调度，wait_event_interruptible 即在等待时进程是可以响应信号之类的唤醒。 内核中的 completion 完成量机制也是基于等待队列的，用于等待某一操作结束。__wait_queue 结构的 task_list 成员通过双链表链接到 __wait_queue_head 中，__wait_queue 中的 private 成员指向等待进程的 task_struct。__wait_queue 中 […]
Linux kernel学习-进程基本
本文同步自（如浏览不正常请点击跳转）：https://zohead.com/archives/linux-kernel-learning-process/ Linux 中进程通过 fork() 被创建时，它差不多是和父进程一样的，它得到父进程的地址空间拷贝，运行和父进程一样的代码，从 fork() 的后面开始执行，父进程和子进程共享代码页，但子进程的 data 页是独立的（包括 stack 和 heap）。 早期的 Linux kernel 并不支持多线程的程序，从 kernel 来看，一个多线程的程序只是一个普通的进程，它的多个执行流应该完全在 user mode 来完成创建、处理、调度等操作，例如使用 POSIX pthread 库。当然这样的实现是无法让人满意的，Linux 为此使用轻量级进程为多线程程序提供更好的支持，两个轻量级进程可以共享资源（例如：地址空间、打开的文件等等），一个比较简单的方法是将为每个线程关联一个轻量级进程，这样每个线程可以被 kernel 单独调度，使用 Linux 轻量级进程的库有：LinuxThreads、NPTL、NGPT 等。Linux kernel 同时也支持线程组（可以理解为轻量级进程组）的概念。 1、进程描述符： 进程描述符由 task_struct 结构来表示，一般来说，每个可以被独立调度的执行上下文都必须有自己的进程描述符，因此尽管轻量级进程共享了很大一部分 kernel 数据结构，它也必须有自己的 task_struct。task_struct 中包含关于一个进程的差不多所有信息，它定义在 include/linux/sched.h 文件中，你会看到这是非常大的结构，其中还包含指向其它结构的指针。访问进程自身的 task_struct 结构，使用宏操作 current。 task_struct 中的 struct mm_struct *mm 即指向进程的地址空间。task_struct 的 state 字段表示进程的运行状态，取值有 TASK_RUNNING（正在运行或正在队列中等待运行，进程如果在用户空间只能为此状态）、TASK_INTERRUPTIBLE（可响应信号）、TASK_UNINTERRUPTIBLE（不响应信号）、TASK_STOPED 等，另外 state 还有特殊的两个值是 EXIT_ZOMBIE（僵尸进程） 和 EXIT_DEAD（进程将被系统移除）。kernel 提供 set_task_state 宏修改进程状态，set_task_state 最终调用 set_mb，set_current_state 用于当前进程的状态。task_struct 的 pid 字段就是咱们喜闻乐见的进程 ID 了。 这是一个典型的 Linux 进程状态机图： POSIX 1003.1c 标准规定一个多线程程序的每个线程都应该有相同的 PID，这样的好处是例如发一个信号给一个 PID，一个线程组里的所有线程都能收到。同一线程组中的线程有相同的线程组号（Thread Group ID），线程组组号放在 task_struct 的 tgid 成员变量中，一般是线程组里的第一个轻量级进程的 PID。特别需要注意 getpid() 系统调用返回的就是 tgid 的值，而不是 pid 值，这样一个多线程程序的所有线程可以共享一个 PID。 对每个进程，kernel 在通过 slab 分配器分配 task_struct 时，通常是实际分配了两个连续的物理页面（8KB），以 thread_union 联合表示，其中包括一个 thread_info 结构（其 task 成员是指向 task_struct 的指针）以及 kernel 模式的进程堆栈。esp CPU 堆栈指针即表示此进程堆栈的栈顶地址，进程从用户模式切换到 kernel 模式时，kernel 堆栈会被清空。为了效率考虑，kernel 会将这两个连续的物理页面的第一个页面按 2^13（也就是 8KB） 对齐，为了避免内存较少时产生问题，kernel 提供配置选项（就是下面的 THREAD_SIZE 了）可以将 thread_info 和堆栈包含在一个页面也就是 4KB 的内存区域里。一般来说，8KB 的堆栈对于内核程序已经够用。 看看 Linux 2.6.34 中 thread_union 的定义： 由于 thread_info 和内核堆栈是合并在连续的页面里的，kernel 就可以从 esp 指针得到 thread_info 结构地址，这是通过 current_thread_info 函数来实现的。 假设 thread_union 是 8KB 大小，也即 2^13，将 esp 的最低 13 位屏蔽掉即可得到 thread_info 的地址，如果是 4KB 的栈大小，屏蔽掉最低 12 位即可（和上面的代码一致），这样通过 current_thread_info()->task 就能得到当前的 task_struct，这就是 current 宏的实现了。 系统中进程的列表保存在 init_task 所在的双向链表中，task_struct 的 tasks 字段就是 list_head，init_task 表示的就是 PID 为 0 的 swapper 进程（或者叫 idle 进程），其 tasks 会依次指向下一个 task_struct，PID 为 1 的进程就是 init 进程，这两个进程都由 kernel 来创建。 而关于可以运行的进程的调度，Linux 2.6.34 和 ULK 上说的已经有很大的不同了。2.6.34 上加上了 struct sched_class 结构体表示不同类型的调度算法类，目前 2.6.34 上实现了三种：Completely Fair Scheduling (CFS) Class（完全公平算法，见 kernel/sched_fair.c）、Real-Time Scheduling Class（实时算法，见 kernel/sched_rt.c）和 idle-task scheduling class（见 kernel/sched_idletask.c），这三个源文件都被 include 在 kernel/sched.c 中进行编译了。CFS Class 使用 sched_entity 结构作为调度实体，其中包含权重、运行时间等信息，比 RT Class 复杂，其中还有专门的红黑树。RT Class 使用 sched_rt_entity 作为调度实体。 每个 task_struct 中都包含了 sched_entity 和 sched_rt_entity 这两个字段，sched_class 中则有 enqueue_task、dequeue_task 等函数指针指向对应调度算法中的实现函数，enqueue_task 将进程加入运行队列，dequeue_task 将进程从队列中移除，由于这段变化较大而且比较复杂，有关这三种调度算法的具体实现以后再来介绍了。 task_struct 的 real_parent 字段指向创建该进程的进程（如果父进程已不存在则为 init 进程），parent 指向当前进程的父进程，children 为该进程子进程列表，sibling 为该进程的兄弟进程列表，group_leader 字段指向该进程的线程组长。与 ULK 不同的是，ULK 中 ptrace_children 为被调试器 trace 的该进程的子进程列表，2.6.34 中 ptraced 字段包含该进程原本的子进程和 ptrace attach 的目标进程，ptrace_list 改为 ptrace_entry。另外 2.6.34 kernel 中已经引入 namespace 的概念，获得进程组 ID 和会话期 ID 的方式也于 ULK 中的有不少区别。 kernel 中进程的 PID 散列表存在 pid_hash 中以加快根据 PID 搜索 task_struct 的速度，pidhash_init 函数初始化此 PID 散列表，由于 2.6.34 中已有 namespace，pid_hashfn 也由原来的一个参数变为两个参数（增加一个 ns 参数表示哪个 namespace）。Linux kernel 也增加了 pid 和 […]
Linux kernel学习-内存寻址
本文同步自（如浏览不正常请点击跳转）：https://zohead.com/archives/linux-kernel-learning-memory-addressing/ 近日在看 Understanding the Linux kernel（慢慢啃E文原版，以下简称 ULK），这本书虽然已经是第三版了，但它基于的 Linux kernel 版本却不是很新，现在 Linux kernel 都已经出到 3.4 版本了，这本书还是基于 2.6.11 的 kernel，不得不说 Linux kernel 的更迭速度太快了。 下面准备以我正在用的 2.6.34 版本的 kernel 为基础进行学习，这本书中不对应的地方我会尽量找到新 kernel 中的实现，并尽量自己做个了解，日后的相同日志如无意外也基于 2.6.34 版本 Linux kernel。 首先已完成第一章：Introduction（这一章没有 Linux kernel 代码），来到第二章 Memory Addressing，开始是介绍逻辑地址、线性地址、物理地址的对应关系，虽然之前用汇编写过 Linux 的 bootloader，用到过实模式和保护模式，但对 GDT、LDT 的概念并没有深入了解过。这一章开篇就介绍了 Intel 80X86 硬件上内存分段的实现，包括段选择子，段寄存器，段描述符。 1、段式内存管理： 每个内存段由 8 个字节的段描述符来表示段的特征。段描述符被存储在 GDT 或者 LDT 中。内存中 GDT 的地址和大小包含在 gdtr 控制寄存器中，LDT 的地址和大小包含在 ldtr 控制寄存器中。段寄存器的高 13 位为段描述符在 GDT 或者 LDT 中的索引，GDT 或者 LDT 结构中包含基地址、段长度等信息。通过检查指令地址和段长度并确定没有越界以及权限是否正确之后，由于 线性地址 = 段基指 + 偏移地址，GDT 或者 LDT 中的基地址加上指令中的偏移量就可以得到需要的线性地址。 备注：由于每个进程都可以有 LDT，而 GDT 只有一个，为满足需求 Intel 的做法是将 LDT 嵌套在 GDT 表中。 Linux kernel 中的内存分段： Linux中所有进程使用相同的段寄存器值，因此它们的线性地址集也是相同的，不管在用户模式还是内核模式，都可以使用相同的逻辑地址，32位 kernel下为 4G 的地址空间。 ULK 中介绍的 user code、user data、kernel code、kernel data 这四个段对应的段选择子的宏为：__USER_CS、__USER_DS、__KERNEL_CS、__KERNEL_DS，2.6.11 中这4个宏定义在 include/asm-i386/segment.h 头文件中，2.6.34 中已经挪到 arch/x86/include/asm/segment.h 里，因为 2.6.34 中 i386 和 x86_64 的代码已经尽可能的合并到 x86 目录中，而不像老版本的代码那样弄成两个目录。定义如下： 下面是 Linux kernel GDT 的实现： 由于 kernel 中每个内核需要有一个 GDT，因此就有一个 GDT table，ULK 中说的是存在 cpu_gdt_table 中，GDT 的地址和大小存在 cpu_gdt_descr 中，2.6.11 kernel 里都是放在 arch/i386/kernel/head.S，使用的地方： 到了 2.6.34 中已经改为： 可以看到 2.6.34 中去掉了原来的 cpu_gdt_table 变量（详见 kernel commit bf50467204b435421d8de33ad080fa46c6f3d50b），新增了一个 gdt_page 结构存放 GDT table，而且提供 get_cpu_gdt_table 函数取得某个 CPU 的 GDT。cpu_gdt_descr 也已去掉，新增了 desc_ptr 结构存放每个 CPU 的 GDT 信息，cpu_gdt_descr 也改为 early_gdt_descr。 看下简单看下新的切换 GDT 的实现： load_gdt 最终调用 lgdt 汇编指令。 2、页式内存管理： Intel 从 80386 开始支持页式内存管理，页单元将线性地址翻译为物理地址。当 CR0 控制寄存器中的 PG 位置为 1 时，启动分页管理功能，为 0 时，禁止分页管理功能，并且把线性地址作物理地址使用。 32 位线性地址的高 10 位为页表目录的下标（指向页表），中间 10 位为页表的下标（指向页面），低 12 位为该地址在页面（通常大小为 4 KB）中的偏移量，这样的二层寻址设计主要为了减少页表本身所占用的内存，由于页表目录和页表都为 10 位，因此都最多包含 1024 个项。正在使用的页表目录的物理地址存在 cr3 控制寄存器中。 在 32 位大小的页表目录（页表）的结构中，其高 20 位为页表（页面）基地址的高 20 位，其它的 flag 中包含一个 Present 标志，如果该值为 1，表示指向的页面或者页表在内存中，如果为 0，页单元会将线性地址存在 cr2 控制寄存器中，并产生异常号 14： page fault。 页表目录结构中另外有一个 Page Size 标志（页表结构没有此标志），如果设为 1，则页面大小可以为 2MB 或者 4MB，这样可以跳过页表转换，将 cr4 寄存器的 PSE 标志启用即可启用大页面支持，此时 32 位线程地址由高 10 位页表目录下标和低 22 位的偏移量。 为满足寻址超过 4GB 的需求，Intel 从 Pentium Pro 处理器开始，将处理器的地址引脚数量由原来的 32 个提升为 36 个，处理器的寻址空间也从 4GB 增到 64GB，并增加 PAE 页面机制（设置 cr4 寄存器的 PAE 标志启用）：64G内存可以划分为 2^24 个页面，页表中的基地址由 20 位增为 24 位，页表结构的大小由 32 位增为 64 位，增加 PDDT 表从而使用三层寻址设计来解释 32 位的线性地址等等。PAE 机制稍显复杂，而且由于仍然使用 32 位线性地址，因此对于应用程序来说，仍然无法使用超过 4GB 的地址空间，64GB 只是对于 kernel 而言的。 顺带说下不同的 64 位架构下的页面寻址级别，见下表，可以看到常用的 x86_64 架构只用了 48 位的线性地址空间，但也达到了 256TB 咯 ^_^ 3、硬件cache： 由于现在 CPU 速度太快，频率已经动辄多少 GHz，而相对的 DRAM 内存频率就慢很多，而且 DRAM 由于设计上电容存在不可避免的漏电原因，DRAM 的数据只能保持很短的时间，必须隔一段时间就刷新一次，不刷新的话会造成存储的信息丢失；而 […]