1.linux class概念
- 几乎所有的类都显示在/sys/class目录下，大多是链接 网络接口：/sys/class/net 输入设备：/sys/class/input 串行设备：/sys/class/tty 块设备：/sys/block
2.semaphore
-
sem_init val为赋予一个信号量的初始值
-
spinkock与semaphore区别
项目 spinlock semaphore mutex 使用步骤 1.定义自旋锁
spinklock_t lock;
2.初始化自旋锁
spin_lock_init(&lock);
3.获得自旋锁
spin_lock(&lock);
4.释放自旋锁
spin_unlock(&lock);线程A：
semaphore sem;
init_MUTEX_LOCKED(&sem)
down(&sem) —进入休眠，等待唤醒
被保护的代码A
线程B中：
被保护代码B
up(&sem)释放信号量 —可唤醒进程Astruct mutex mutex;
mutex_init(&mutex); /定义/
…
mutex_lock(&mutex); /获取互斥锁/
… /临界资源/
mutex_unlock(&mutex); /释放互斥锁/使用场景 忙等待,占用时间比较短时候使用，可保护中断的打断，防止多处理器并发访问临界区，可在中断中使用 休眠，需要上下文切换，耗时，占用时间比较长时候使用（不能在中断中使用），可用于进程间同步 休眠，需要上下文切换，耗时，占用时间比较长时候使用（不能在中断中使用），可用于进程间同步
3.init_completion, init_waitqueue_head
static inline void init_completion(struct completion *x)
{
x->done = 0;
init_waitqueue_head(&x->wait);
}
初始化等待队列头
void init_waitqueue_head(wait_queue_head_t *q) { spin_lock_init(&q->lock); INIT_LIST_HEAD(&q->task_list); }
static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; }
4.tasklet_init
驱动程序在初始化时，通过函数task_init建立一个tasklet，然后调用函数tasklet_schedule将这个tasklet 放在 tasklet_vec链表的头部，并唤醒后台线程ksoftirqd。当后台线程ksoftirqd运行调用__do_softirq时，会执行在中断 向量表softirq_vec里中断号TASKLET_SOFTIRQ对应的tasklet_action函数，然后tasklet_action遍历 tasklet_vec链表，调用每个tasklet的函数完成软中断操作。
5.idr
idr机制，该机制内部采用radix树实现，可以很方便地将整数和指针关联起来，并且具有很高的搜索效率
(1)获得idr 要在代码中使用idr，首先要包括<linux/idr.h>。接下来，我们要在代码中分配idr结构体，并初始化： void idr_init(struct idr *idp); 其中idr定义如下：
struct idr {
struct idr_layer *top;
struct idr_layer *id_free;
int layers;
int id_free_cnt;
spinlock_t lock;
};
/* idr是idr机制的核心结构体 何问起 hovertree.com */
(2)idr分配内存 int idr_pre_get(struct idr *idp, unsigned int gfp_mask); 每次通过idr获得ID号之前，需要先分配内存。 返回0表示错误，非零值代表正常
(3)分配ID号并将ID号和指针关联 int idr_get_new(struct idr *idp, void *ptr, int *id); int idr_get_new_above(struct idr *idp, void *ptr, int start_id, int *id); idp: 之前通过idr_init初始化的idr指针 id: 由内核自动分配的ID号 ptr: 和ID号相关联的指针 start_id: 起始ID号。内核在分配ID号时，会从start_id开始。
函数调用正常返回0，如果没有ID可以分配，则返回-ENOSPC
在实际中，上述函数常常采用如下方式使用：
again:
if (idr_pre_get(&my_idr, GFP_KERNEL) == 0) {
/* No memory, give up entirely */
}
spin_lock(&my_lock);
result = idr_get_new(&my_idr, &target, &id);
if (result == -EAGAIN) {
sigh();
spin_unlock(&my_lock);
goto again;
}
(4)通过ID号搜索对应的指针 void *idr_find(struct idr *idp, int id); 返回值是和给定id相关联的指针，如果没有，则返回NULL
(5)删除ID 要删除一个ID，使用： void idr_remove(struct idr *idp, int id);
6.netlink
- netlink具有以下特点：
① 支持全双工、异步通信(当然同步也支持)
② 用户空间可使用标准的BSD socket接口(但netlink并没有屏蔽掉协议包的构造与解析过程，推荐使用libnl等第三方库)
③ 在内核空间使用专用的内核API接口
④ 支持多播(因此支持“总线”式通信，可实现消息订阅)
⑤ 在内核端可用于进程上下文与中断上下文
内核使用与标准socket API类似的一套API完成通信过程。首先通过netlink_kernel_create()创建套接字，该函数的原型如下：
static inline struct sock * netlink_kernel_create(struct net \*net, int unit, struct netlink_kernel_cfg \*cfg)
/* net: net指向所在的网络命名空间, 一般默认传入的是&init_net(不需要定义); 定义在net_namespace.c(extern struct net init_net);
unit：netlink协议类型
cfg： cfg存放的是netlink内核配置参数（如下）
*/
/* optional Netlink kernel configurationparameters */
struct netlink_kernel_cfg {
unsigned int groups;
unsigned int flags;
void (*input)(struct sk_buff *skb); /* input 回调函数 */
struct mutex *cb_mutex;
void (*bind)(int group);
bool (*compare)(struct net *net, struct sock *sk);
};
其中net参数是网络设备命名空间指针.
然后用户空间进程使用标准Socket API来创建套接字，将进程ID发送至内核空间，用户空间创建使用socket()创建套接字，该函数的原型如下：
int socket(int domain, int type, int protocol);
其中domain值为PF_NETLINK，即Netlink使用协议族。protocol为Netlink提供的协议或者是用户自定义的协议，Netlink提供的协议包括NETLINK_ROUTE, NETLINK_FIREWALL, NETLINK_ARPD, NETLINK_ROUTE6和 NETLINK_IP6_FW。
接着使用bind函数绑定。Netlink的bind()函数把一个本地socket地址(源socket地址)与一个打开的socket进行关联。完成绑定，内核空间接收到用户进程ID之后便可以进行通讯。
用户空间进程发送数据使用标准socket API中sendmsg()函数完成，使用时需添加struct msghdr消息和nlmsghdr消息头。一个netlink消息体由nlmsghdr和消息的payload部分组成，输入消息后，内核会进入nlmsghdr指向的缓冲区。
内核空间发送数据使用独立创建的sk_buff缓冲区，Linux定义了如下宏方便对于缓冲区地址的设置，如下所示：
#define NETLINK_CB(skb) ((struct netlink_skb_parms)&((skb)->cb))
在对缓冲区设置完成消息地址之后，可以使用netlink_unicast()来发布单播消息，netlink_unicast()原型如下：
int netlink_unicast(struct sock *sk, struct sk_buff *skb, u32 pid, int nonblock);
参数sk为函数netlink_kernel_create()返回的socket，参数skb存放消息，它的data字段指向要发送的netlink消息结构，而skb的控制块保存了消息的地址信息，前面的宏NETLINK_CB(skb)就用于方便设置该控制块，参数pid为接收消息进程的pid，参数nonblock表示该函数是否为非阻塞，如果为1，该函数将在没有接收缓存可利用时立即返回，而如果为0，该函数在没有接收缓存可利用时睡眠。
内核模块或子系统也可以使用函数netlink_broadcast来发送广播消息：
void netlink_broadcast(struct sock *sk, struct sk_buff *skb, u32 pid, u32 group, int allocation);
前面的三个参数与netlink_unicast相同，参数group为接收消息的多播组，该参数的每一个代表一个多播组，因此如果发送给多个多播组，就把该参数设置为多个多播组组ID的位或。参数allocation为内核内存分配类型，一般地为GFP_ATOMIC或GFP_KERNEL，GFP_ATOMIC用于原子的上下文（即不可以睡眠），而GFP_KERNEL用于非原子上下文。
接收数据时程序需要申请足够大的空间来存储netlink消息头和消息的payload部分。然后使用标准函数接口recvmsg()来接收netlink消息
6.down_interruptible
这个函数的功能就是获得信号量，如果得不到信号量就睡眠，此时没有信号打断，那么进入睡眠。但是在睡眠过程中可能被信号打断，打断之后返回-EINTR。 使用可被中断的信号量版本的意思是，万一出现了semaphore的死锁，还有机会用ctrl+c发出软中断，让等待这个内核驱动返回的用户态进程退出。
7.container_of
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
- 作用： container_of（ptr, type,member）函数的实现包括两部分：
-
判断ptr 与 member 是否为同一类型
-
计算size大小，结构体的起始地址 = (type *)((char *)ptr - size) (注：强转为该结构体指针)
总结：container_of()的作用就是通过一个结构变量中一个成员的地址找到这个结构体变量的首地址。
8.device_create
内核中定义了struct class结构体，顾名思义，一个struct class结构体类型变量对应一个类，内核同时提供了class_create(…)函数，可以用它来创建一个类，这个类存放于sysfs下面，一旦创建好了这个类，再调用device_create(…)函数来在/dev目录下创建相应的设备节点。这样，加载模块的时候，用户空间中的udev会自动响应device_create(…)函数，去/sysfs下寻找对应的类从而创建设备节点。
struct device *device_create(struct class *class, struct device *parent,
dev_t devt, const char *fmt, ...)
{
va_list vargs;
struct device *dev;
va_start(vargs, fmt);
dev = device_create_vargs(class, parent, devt, NULL, fmt, vargs);
va_end(vargs);
return dev;
}
第一个参数指定所要创建的设备所从属的类，第二个参数是这个设备的父设备，如果没有就指定为NULL，第三个参数是设备号，第四个参数是设备名称，第五个参数是从设备号。
9.mmap在驱动中的实现
在驱动中的mmap实现主要是完成一件事，就是实际物理设备的操作区域到进程虚拟空间地址的映射过程。同时也需要保证这段映射的虚拟存储器区域不会被进程当做一般的空间使用，因此需要添加一系列的保护方式。
具体的实现过程如下：
/*主要是建立虚拟地址到物理地址的页表关系，其他的过程由内核自己完成*/
static int mem_mmap(struct file* filp,struct vm_area_struct *vma)
{
/*间接的控制设备*/
struct mem_dev *dev = filp->private_data;
/*标记这段虚拟内存映射为IO区域，并阻止系统将该区域包含在进程的存放转存中*/
vma->vm_flags |= VM_IO;
/*标记这段区域不能被换出*/
vma->vm_flags |= VM_RESERVED;
/**/
if(remap_pfn_range(vma,/*虚拟内存区域*/
vma->vm_start, /*虚拟地址的起始地址*/
virt_to_phys(dev->data)>>PAGE_SHIFT, /*物理存储区的物理页号*/
dev->size, /*映射区域大小*/
vma->vm_page_prot /*虚拟区域保护属性*/
))
return -EAGAIN;
return 0;
}
采用函数remap_pfn_range()建立物理页与虚拟页之间的关系, 具体的参数如下：
int remap_pfn_range(structvm_area_struct *vma, unsigned long addr,unsigned long pfn, unsigned long size, pgprot_t prot)
1、struct vm_area_struct是一个虚拟内存区域结构体，表示虚拟存储器中的一个内存区域。其中的元素vm_start是指虚拟存储器中的起始地址。
2、addr也就是虚拟存储器中的起始地址，通常可以选择addr = vma->vm_start。
3、pfn是指物理存储器的具体页号，通常通过物理地址得到对应的物理页号，具体采用virt_to_phys(dev->data)»PAGE_SHIFT.首先将虚拟内存转换到物理内存，然后得到页号。»PAGE_SHIFT通常为12，这是因为每一页的大小刚好是4K,这样右移12相当于除以4096，得到页号。
4、size区域大小
5、区域保护机制。
返回值，如果成功返回0，否则正数。
10.红黑树（R-B Tree）
红黑树的特性: （1）每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 （3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！] （4）如果一个节点是红色的，则它的子节点必须是黑色的。 （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
红黑树是一种二叉查找树，但在每个结点上增加了一个存储位表示结点的颜色，可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。 当二叉查找树的高度较低时，这些操作执行的比较快，但是当树的高度较高时，这些操作的性能可能不比用链表好。红黑树（red-black tree）是一种平衡的二叉查找树，它能保证在最坏情况下，基本的动态操作集合运行时间为 O(lgn)。 在实际场景中，linux进程调度， Java的HashMap，Mysql的Innodb都是使用了红黑树进行数据的存储的。
linux进程调度：
任务存储在以时间为顺序的红黑树中（由 sched_entity 对象表示），对处理器需求最多的任务 （最低虚拟执行时vruntime）存储在树的左側，处理器需求最少的任务（最高虚拟执行时）存储在树的右側。 为了公平。调度器然后选取红黑树最左端的节点调度为下一个以便保持公平性。
任务通过将其执行时间加入到虚拟执行时， 说明其占用 CPU 的时间，然后假设可执行。再插回到树中。这样，树左側的任务就被给予时间执行了，树的内容从右側迁移到左側以保持公平。