之前一直是做的嵌入式音视频方向,对于驱动方向也是小白一个,希望能通过这本书对驱动和内核有更加深入的了解。
这里记录一些看书过程中遇到的一些比较重要的地方,如果写的有问题请指正。
slab分配器:实际上是建立在伙伴系统之上,slab使用的内存空间是通过伙伴算法进行分配的,slab通过自己的算法堆小块内存进行了管理
伙伴算法:把所有的空闲页框分组为 11 块链表,每一块链表分别包含大小为1,2,4,8,16,32,64,128,256,512 和 1024 个连续的页框。对1024 个页框的最大请求对应着 4MB 大小的连续RAM 块。每一块的第一个页框的物理地址是该块大小的整数倍。例如,大小为 16个页框的块,其起始地址是 16 * 2^12 (2^12 = 4096,这是一个常规页的大小)的倍数。
BSD进程记账:开启后,内核每次在一个进程终止时写一个记帐记录。这些记帐记录一般是命令名的少量二进制数据、使用 的CPU时间量、用户ID和组ID、开始时间,等等
SMP系统:多处理器系统
进程中住相关信息保存在task_struct这个结构体中,结构体定义在sched.h中。
Linux中可以用ps命令查看所有进程的信息:
ps -eo pid,tid,ppid,comm
Linux中创建进程与其他系统有个主要区别,Linux中创建进程分2步:fork()和exec()。
fork: 通过拷贝当前进程创建一个子进程
exec: 读取可执行文件,将其载入到内存中运行
调度我认为最主要是为了让客户有更好的使用体验,为加快进程的执行效率而生。
调度是一个平衡的过程。一方面,它要保证各个运行的进程能够最大限度的使用CPU(即尽量少的切换进程,进程切换过多,CPU的时间会浪费在切换上);另一方面,保证各个进程能公平的使用CPU(即防止一个进程长时间独占CPU的情况)
进程被分为I/O消耗型 和cpu消耗型,这种分类也并非绝对,有些进程可以两者兼备
I/O消耗型:只运行短短一会儿,随后会开始等待那些可阻塞资源,如键盘鼠标…………,调度策略应该为增加调度频率减少运行时间。
cpu消耗型:大部分时间花在cpu处理中(执行代码),对于这种类型进程,调度策略应该为降低调度频率增加运行时间。
通过以下指令可以查看,所有进程的相关信息
ps -eo state,uid,pid,ppid,rtprio,ni,time,comm
现代进程调度策略:进程调度由优先级和时间片来决定,优先级一个是nice值-20~+19,越大优先级越低,一个是实时优先级0~99,越大优先级越高。
现代进程调度策略的问题:
1、nice值到时间片需要将nice值对应到处理器的绝对时间,优先级低的处理时间少,多个低优先级进程会导致进程切换频繁。
2、相对的nice,高优先级级下问题不大,当低优先级时时间片差的必定较多,比如一个优先级差5ms,高优先级0为100ms,1为95ms问题不大,但是当低优先级18 10ms,19为5ms,前者处理时间为后者2倍。
3、时间片需要时节拍器的整数倍
4、存在某些睡眠/唤醒一个进程的后门,打破公平原则
CFS(完全公平调度算法):CFS的抢占时机取决于新的可运行程序消耗了多少处理器使用比,从而完全摈弃了时间片。CFS确保每个进程使用公平的处理器使用比,主要通过不同的权重因子来分配时间,消耗的使用比比当前进程小,则新进程立刻投入运行,抢占当前进程。2.6.23内核版本之后
cfs 中的选择下一个运行的程序的规则为选择vruntime最小的进程,其中使用红黑树(rbtree)储存每个进程的vruntime时间。
实现一个系统调用需要注意
参数检查
传输到内核的指针必须保证1、指针指向的区域为内核区域 2、指针指向的内存区域在进程的地址空间里3、进程调用系统调用不能绕过内存访问限制
注意:内核不论何时都不能轻率的接受来自用户空间的指针
内核与用户空间数据拷贝 copy_to_user() copy_from_user()
链表
内核链表特点是将链表结构体保存在用户数据结构体中,这样可以保证链表独立于用户数据之外,方便用户数据的单独操作
我们在通过链表中的pre/next进入到链表的上一个/下一个节点时,此时我们只能获得链表的数据结构,如果想要获得用户数据的数据结构,需要使用到下面这个接口
#define list_entry(ptr, type, member) \ container_of(ptr, type, member)
container_of 的定义如下
#define container_of(ptr, type, member) ({ \ const typeof(((type *)0)->member)*__mptr = (ptr); \ (type *)((char *)__mptr - offsetof(type, member)); })
第一个参数ptr代表链表指针
第二个参数type代表数据结构体的类型
第三个参数member代表type中定义的这个链表的名字
struct student { int id; char* name; struct list_head list; };
以student为例。type是struct student,ptr是指向stuct list的指针,也就是指向member类型的指针,member就是 list
typeof(x)的作用就是提取x的类型
typeof(((type *)0)->member)的意思就是提取链表结构体的l类型
offsetof的定义如下,用于计算从结构体头到mem的中间的偏移量
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
链表结构体地址减去这个偏移量就是数据结构体的头地址
剩下的链表的操作均比较常规
队列(FIFO)
内核中的队列是以字节形式保存数据的,所以获取数据的时候,需要知道数据的大小。
如果从队列中取得数据时指定的大小不对的话,取得数据会不完整或过大。
内核中关于队列定义的头文件位于:<linux/kfifo.h> include/linux/kfifo.h
头文件中定义的函数的实现位于:kernel/kfifo.c
内核队列编程需要注意的是:
映射
每个唯一的id对应一个自定义的数据结构。
映射的使用需要注意的是,给自定义的数据结构申请一个id的时候,不能直接申请id,先要分配id(函数idr_pre_get),分配成功后,在获取一个id(函数idr_get_new)。
参考查看:idr机制(32叉树)_paomadi的专栏-CSDN博客
二叉树(具体实现)
内核中用到的比较多的是红黑树,他是一种自平衡二叉搜索树,搜索的时间复杂度为logn,自平衡二叉搜索树的特点是所有叶子节点之间的深度差不超过1的二叉搜索树。
红黑树的特性如下
红黑树中最长的路径就是红黑交替的路径,最短的路径是全黑节点的路径,再加上根节点和叶子节点都是黑色,从而可以保证红黑树中最长路径的长度不会超过最短路径的2倍。
内核中关于红黑树定义的头文件位于:<linux/rbtree.h> include/linux/rbtree.h
头文件中定义的函数的实现位于:lib/rbtree.c
struct rb_node { unsigned long rb_parent_color; #define RB_RED 0 #define RB_BLACK 1 struct rb_node *rb_right; struct rb_node *rb_left; } __attribute__((aligned(sizeof(long))));
__attribute__((aligned(sizeof(long))));代表的是long的大小对齐,long在32位里面是4字节,64位里面是8字节。这表示在指向这个结构体的指针的最后两位必定是0,比如0xAB00,红黑树的颜色存储在最后一位中如0xAB01就代表的是黑色,0xAB00代表的就是红色。
为了提高cou与外设间协通工作的性能,引入了中断机制
如果没有中断,则使用轮询机制,这个机制很多时候cpu询问的时候并没有出现中断导致出现无用功。
中断机制是硬件在需要的时候向CPU发出信号,CPU暂时停止正在进行的工作,来处理硬件请求的一种机制。
这里说的的中断一般称为异步中断,同步中断一般又叫做异常,
同步中断是在cpu处理完中断请求的所有工作之后才做出反馈,在处理器执行到由于编程实物导致的错误指令是,或者出现缺页异常等情况,就会通过内核来处理,处理器就会产生一个异常。他的产生式必须考虑与处理器时钟同步。
异步中断是CPU处理中断的时间过长,所以先将硬件复位,使硬件可以继续自己的工作,然后在适当时候处理中断请求中耗时的部分。
异步中断举个例子:网卡的工作原理
注册中断的函数位置:<linux/interrupt.h> include/linux/interrupt.h
/* * irg - 表示要分配的中断号 * handler - 实际的中断处理程序 * flags - 标志位,表示此中断的具有特性 * name - 中断设备名称的ASCII 表示,这些会被/proc/irq和/proc/interrupts文件使用 * dev - 用于共享中断线,多个中断程序共享一个中断线时(共用一个中断号),依靠dev来区别各个中断程序 * 返回值: * 执行成功:0 * 执行失败:非0 */ int request_irq(unsigned int irq, irq_handler_t handler, unsigned long flags, const char* name, void *dev)
中断处理程序标志位
IRQF_DISABLED :该标志位被设置,意味着内核在处理中断处理程序本身期间,禁止其他所有中断。多数中断处理程序不会去设置这位,这种用法留给希望快速执行的轻量级中断
IRQF_SAMPLE_RANDOM:这个标志位设置,表示这个中断对内核熵池有贡献,内核熵池负责给各种随机时间提供随机数,如果有些硬件中断没有规律性,那么是很好的熵源
IRQF_TIMER:系统定时器的中断
IRQF_SHARED:此标志表明可以在多个中断处理程序中共享中断线,在同一个中断线上每个中断处理程序必须设置此标志。
共享的中断处理程序
共享与非共享的处理程序的差异主要有三处:
1、request_irq中的flag参数需要设置成IRQF_SHARED
2、request_irq中的dev参数必须唯一,要能通过dec来区分是哪个中断程序,设备指针的参数就可以满足这个要求,不能传递null值。
3、中断处理程序必须能够区分它的设备是否真的产生了中断
中断上下文
·中断处理程序打断了其他的代码,所有中断处理程序必须尽可能的迅速简洁。其他一些不是需要非常实时的工作放在下部分来执行。
中断处理机制
中断控制方法
常用的中断控制方法见下表:
函数 | 说明 |
local_irq_disable() | 禁止本地中断传递 |
local_irq_enable() | 激活本地中断传递 |
local_irq_save() | 保存本地中断传递的当前状态,然后禁止本地中断传递 |
local_irq_restore() | 恢复本地中断传递到给定的状态 |
disable_irq() | 禁止给定中断线,并确保该函数返回之前在该中断线上没有处理程序在运行 |
disable_irq_nosync() | 禁止给定中断线 |
enable_irq() | 激活给定中断线 |
irqs_disabled() | 如果本地中断传递被禁止,则返回非0;否则返回0 |
in_interrupt() | 如果在中断上下文中,则返回非0;如果在进程上下文中,则返回0 |
in_irq() | 如果当前正在执行中断处理程序,则返回非0;否则返回0 |
哪些工作必须放在上半部执行
1、如果一个任务对时间是否敏感,将其放在上半部
2、如果一个任务和硬件有关,将其放在上半部
3、如果一个任务要保证不被其他中断打断,将其放在上半部
除此之外其他所有任务可以考虑放在下半部
实现中断下半部的机制主要有一下几种:
1、软中断
2、tasklet
3、工作队列
软中断
https://www.cnblogs.com/wang_yb/archive/2013/04/23/3037268.html
软中断的代码定义在<linux/interrupt.h>
软中断是在编译期间静态分配的,不能动态的注册与注销
软中断的流程图如下所示:
一个软中断只有被触发之后才有可能执行
在下列地方,待处理的软中断会被检查和执行:
1、从一个硬件中断代码处返回时
2、在ksoftirqd内核线程中
3、在哪些显示检查和执行待处理的软中断的代码中,如网络子系统
软中断的描述符
新增加的中断类型,需要根据希望赋予他的优先级来决定加入的位置
enum { HI_SOFTIRQ=0,\\优先级高的tasklets TIMER_SOFTIRQ,\\定时器的下半部 NET_TX_SOFTIRQ,\\发送网络数据包 NET_RX_SOFTIRQ,\\接受网络数据包 BLOCK_SOFTIRQ,\\BLOCK装置 BLOCK_IOPOLL_SOFTIRQ, TASKLET_SOFTIRQ,\\正常优先权的tasklets SCHED_SOFTIRQ,\\调度程度 HRTIMER_SOFTIRQ,\\高分辨率定时器 RCU_SOFTIRQ, \\RCU锁定 /* Preferable RCU should always be the last softirq */ NR_SOFTIRQS };
linux中,执行软中断有专门的内核线程,每个处理器对应一个线程,名称ksoftirqd/n (n对应处理器号)
通过top命令查看我的单核虚拟机,CentOS系统中的ksoftirqd线程如下:
[root@vbox ~]# top | grep ksoftirq 4 root 20 0 0 0 0 S 0.0 0.0 0:00.02 ksoftirqd/0
tasklet
tasklet也是利用软中断来实现的,但是它提供了比软中断更好用的接口(其实就是基于软中断又封装了一下),
所以除了对性能要求特别高的情况,一般建议使用tasklet来实现自己的中断。
tasklet与软中断中间的差别是,在不同的处理器上面可以运行相同类型的软中断,而类型相同的tasklet不能同时执行
tasklet对应的结构体在 <linux/interrupt.h> 中
struct tasklet_struct { struct tasklet_struct *next; /* 链表中的下一个tasklet */ unsigned long state; /* tasklet状态 */ atomic_t count; /* 引用计数器 */ void (*func)(unsigned long); /* tasklet处理函数 */ unsigned long data; /* tasklet处理函数的参数 */ };
tasklet状态只有3种值:
引用计数器count 的值不为0,表示该tasklet被禁止。
tasklet支持动态声明和静态声明。
工作队列
工作队列是创建一个内核线程去执行下半部分的工作,如果推后执行的任务需要睡眠,那么久选择工作队列,如果不需要就先软中断、tasklet。
工作队列子系统是一个用于创建内核线程的接口,通过它可以创建一个工作者线程来专门处理中断的下半部工作。
工作者线程的结构体为workqueue_struct,不同类型的工作者线程对应着一个workqueue_struct,里面包含一个cpu_workqueue_struct的数组,它定义在kernel/workqueue.c中,表示每个处理器对应着一个cpu_workqueue_struct。
工作相关结构体work_struct放在<linux/workqueue.h>中,其中包含希望执行的func。
缺省的工作者线程名称是 events/n (n对应处理器号),大部分情况下使用默认工作者线程就行,有些情况下比如说XFS文件系统就需要为自己创建新的工作者线程。
通过top命令查看我的单核虚拟机,CentOS系统中的events线程如下:
[root@vbox ~]# top | grep event 7 root 20 0 0 0 0 S 0.0 0.0 0:03.71 events/0
使用工作队列的方法如下
创建推后的工作,可以是静态的也可以是动态的,DECLARE_WORK是静态的,INIT_WORK是动态的。
工作队列处理函数
typedef void (*work_func_t)(struct work_struct *work);
操作处理函数运行在进程上下文中运行,但是不能访问用户空间,因为内核中没有相关映射。
工作被创建之后就可以直接被调度schedule_work(struct work_struct *work);
刷新现有的工作,这个步骤不是必须的 刷新现有工作的意思就是在追加新的工作之前,保证队列中的已有工作已经执行完了。
下半部机制 | 上下文 | 复杂度 | 执行性能 | 顺序执行保障 |
软中断 | 中断 | 高 (需要自己确保软中断的执行顺序及锁机制) | 好 (全部自己实现,便于调优) | 没有 |
tasklet | 中断 | 中 (提供了简单的接口来使用软中断) | 中 | 同类型不能同时执行 |
工作队列 | 进程 | 低 (在进程上下文中运行,与写用户程序差不多) | 差 |
临界区:访问和操作共享数据的代码段
竞争条件:如果两个执行线程有可能处于同一个临界区中同时执行,我们称他为竞争条件
同步的作用其实是防止在临界区中形成竞争条件。
如果临界区里是原子操作(即整个操作完成前不会被打断),那么自然就不会出竞争条件。
但在实际应用中,临界区中的代码往往不会那么简单,所以为了保持同步,引入了锁机制。
内核中造成竞争条件的原因:
竞争原因 | 说明 |
中断 | 中断随时会发生,也就会随时打断当前执行的代码。如果中断和被打断的代码在相同的临界区,就产生了竞争条件 |
软中断和tasklet | 软中断和tasklet也会随时被内核唤醒执行,也会像中断一样打断正在执行的代码 |
内核抢占 | 内核具有抢占性,发生抢占时,如果抢占的线程和被抢占的线程在相同的临界区,就产生了竞争条件 |
睡眠及用户空间的同步 | 用户进程睡眠后,调度程序会唤醒一个新的用户进程,新的用户进程和睡眠的进程可能在同一个临界区中 |
对称多处理 | 2个或多个处理器可以同时执行相同的代码 |
编写代码之前就要考虑好临界区在哪,以及怎么加锁,难的不是怎么加锁,难的是提前确认哪些地方需要加锁,以及锁的粒度
编写内核代码时,时时记着下面这些问题:
死锁
死锁就是所有线程都在相互等待释放资源,导致谁也无法继续执行下去。
下面一些简单的规则可以帮助我们避免死锁:
锁的粒度
锁的粒度太粗,扩展性越不好,扩展性是对系统可扩展程度的一个量度。(我的理解是,锁的范围越大,整体程序扩展起来越麻烦,因为要保护的东西非常多,需要考虑的也会较多)
锁的粒度越细,系统开销越大,程序也越复杂,所以对于争用不是很频繁的锁,就没有必要细化了。
原子操作
原子操作是由编译器来保证的,保证一个线程对数据的操作不会被其他线程打断。
原子操作有2类:
自旋锁
自旋锁的特点就是当一个线程获取了锁之后,其他试图获取这个锁的线程一直在循环等待获取这个锁,直至锁重新可用。
由于线程实在一直循环的获取这个锁,所以会造成CPU处理时间的浪费,因此最好将自旋锁用于能很快处理完的临界区。
自旋锁使用时有2点需要注意:
中断处理下半部的操作中使用自旋锁尤其需要小心:
读写自旋锁
读写自旋锁除了和普通自旋锁一样有自旋特性以外,还有以下特点:
1、读锁之间是共享的
2、写锁之间是互斥的
3、读写锁之间是互斥的
当读锁被获取时写锁会一直等待,如果读写不能清晰的分开,建议使用一般的自旋锁即可。
信号量
信号量也是一种锁,和自旋锁不同的是,线程获取不到信号量的时候,不会像自旋锁一样循环的去试图获取锁,
而是进入睡眠,直至有信号量释放出来时,才会唤醒睡眠的线程,进入临界区执行。
由于使用信号量时,线程会睡眠,所以等待的过程不会占用CPU时间。所以信号量适用于等待时间较长的临界区。
信号量消耗的CPU时间的地方在于使线程睡眠和唤醒线程,
如果 (使线程睡眠 + 唤醒线程)的CPU时间 > 线程自旋等待的CPU时间,那么可以考虑使用自旋锁。
down()表示获取信号量,如果信号量值<0,则线程进入睡眠,up()表示释放信号量
一般用的比较多的是down_interruptible()方法,因为以 TASK_UNINTERRUPTIBLE 方式睡眠无法被信号唤醒。
对于 TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE 补充说明一下:
信号量结构体具体如下:
/* Please don't access any members of this structure directly */ struct semaphore { spinlock_t lock; unsigned int count; struct list_head wait_list; };
可以发现信号量结构体中有个自旋锁,这个自旋锁的作用是保证信号量的down和up等操作不会被中断处理程序打断。
读写信号量
读写信号量和信号量之间的关系 与 读写自旋锁和普通自旋锁之间的关系 差不多。
读写信号量都是二值信号量,即计数值最大为1,增加读者时,计数器不变,增加写者,计数器才减一。
也就是说读写信号量保护的临界区,最多只有一个写者,但可以有多个读者。
互斥体
互斥体也是一种可以睡眠的锁,相当于二值信号量,只是提供的API更加简单,使用的场景也更严格一些,如下所示:
完成变量
完成变量的机制类似于信号量,
比如一个线程A进入临界区之后,另一个线程B会在完成变量上等待,线程A完成了任务出了临界区之后,使用完成变量来唤醒线程B。
完成变量的API也很简单:
方法 | 描述 |
init_completion(struct completion *) | 初始化指定的动态创建的完成变量 |
wait_for_completion(struct completion *) | 等待指定的完成变量接受信号 |
complete(struct completion *) | 发信号唤醒任何等待任务 |
使用完成变量的例子可以参考:kernel/sched.c 和 kernel/fork.c
一般在2个任务需要简单同步的情况下,可以考虑使用完成变量。
顺序锁
顺序锁为读写共享数据提供了一种简单的实现机制。
之前提到的读写自旋锁和读写信号量,在读锁被获取之后,写锁是不能再被获取的,
也就是说,必须等所有的读锁释放后,才能对临界区进行写入操作。
顺序锁则与之不同,读锁被获取的情况下,写锁仍然可以被获取。
使用顺序锁的读操作在读之前和读之后都会检查顺序锁的序列值,如果前后值不符,则说明在读的过程中有写的操作发生,
那么读操作会重新执行一次,直至读前后的序列值是一样的。
顺序锁优先保证写锁的可用,所以适用于那些读者很多,写者很少,且写优于读的场景。
顺序锁的使用例子可以参考:kernel/timer.c和kernel/time/tick-common.c文件
禁止抢占
其实使用自旋锁已经可以防止内核抢占了,但是有时候仅仅需要禁止内核抢占,不需要像自旋锁那样连中断都屏蔽掉。,比如说一个任务a在操作参数foo是被抢占,此时b又去操作了foo,导致出现了伪并发的情况,如果不想出现这种情况,这时候就需要使用禁止内核抢占的方法了:
方法 | 描述 |
preempt_disable() | 增加抢占计数值,从而禁止内核抢占 |
preempt_enable() | 减少抢占计算,并当该值降为0时检查和执行被挂起的需调度的任务 |
preempt_enable_no_resched() | 激活内核抢占但不再检查任何被挂起的需调度的任务 |
preempt_count() | 返回抢占计数 |
这里的preempt_disable()和preempt_enable()是可以嵌套调用的,disable和enable的次数最终应该是一样的。
禁止抢占的头文件参见:<linux/preempt.h>
顺序和屏障
对于一段代码,编译器或者处理器在编译和执行时可能会对执行顺序进行一些优化,从而使得代码的执行顺序和我们写的代码有些区别。
一般情况下,这没有什么问题,但是在并发条件下,可能会出现取得的值与预期不一致的情况
比如下面的代码:
/* * 线程A和线程B共享的变量 a和b * 初始值 a=1, b=2 */ int a = 1, b = 2; /* * 假设线程A 中对 a和b的操作 */ void Thread_A() { a = 5; b = 4; } /* * 假设线程B 中对 a和b的操作 */ void Thread_B() { if (b == 4) printf("a = %d\n", a); }
由于编译器或者处理器的优化,线程A中的赋值顺序可能是b先赋值后,a才被赋值。
所以如果线程A中 b=4; 执行完,a=5; 还没有执行的时候,线程B开始执行,那么线程B打印的是a的初始值1。
这就与我们预期的不一致了,我们预期的是a在b之前赋值,所以线程B要么不打印内容,如果打印的话,a的值应该是5。