linux内核基础层的学习（1）

一：内核基础层数据结构
1：双向链表list
a）：链表的定义

struct list_head{
 struct list_head *next,*pre;
 }

b）：container对象和list_entry

#define container_of(ptr,type,member){  \
    const typeof(((type *)0->member) *_mptr = (ptr);     (type*)((char*)_mptr-offset(type,member));})

#define list_entry(ptr,type,member) \
    container_of(ptr,type,member)

对双向链表的详细介绍请参考我的博客：

linux内核list.h的学习

2：hash链表
a）：定义

struct hlist_head{
    struct hlist_head *first;
}

b）:hash链表库
与list相同

请参考下面文章的后面部分就是hash链表的内容：

linux内核list.h的学习

3：红黑树

a）：实质上是自平衡二叉树
b）：定义在rbtree.c文件中（静待博客更新，对rbtree的介绍）
c）：应用场景
主要用在内存管理，IO调度算法等实现了红黑树

4：radix输–基树

a）：定义在/lib/radix_tree.c中
b）：radix树是一种空间换时间的数据结构，通过空间的冗余减少了时间上的消耗
（静待博客更新，对radix_tree的介绍）
c）：page cache的管理使用了radix tree

二：内核基础层的同步机制
1：自旋锁
a）：作用
（1）：如果数据未锁，那么就获取锁并运行，如果数据已锁，那么就一定旋转（其实是反复执行一条指令）
（2）：单处理器环境（非抢占式内核）下，自旋锁其实不起作用
（3）：单处理器，抢占式内核环境下，自旋锁起的作用就是禁止抢占
b）：自旋锁的调用
（1）：spin_lock
（2）：spin_unlock

2：内核信号量

a）：定义在文件semaphore.h文件里
b)：semaphore和mutex
（1）：sema_init：计数可以为多
（2）：init_mutex：计数为1的信号量
c）：信号量的操作
（1）：up：释放信号量
（2）：down：获取信号量，如果不能获取，则进入睡眠状态
（3）：down_trylock：获取信号量，如果不能获取则立即返回，进程不进入睡眠状态

注意：
自旋锁和信号量的区别
1：自旋锁可以用在中断处理函数和tasklet等不可睡眠的场景，而信号量不行
2：可睡眠的场景既可以使用信号量，也可以使用自旋锁，自旋锁通常用在轻量级场景

3：同步机制–原子变量
a）：原子变量提供了一种原子的数据结构，对这种数据结构的读写不可被细分和打断
b）：原子变量提供的调用
（1）：atomic_add：加一个整数到原子变量
（2）：automic_sub：从原子变量减去一个整数
（3）：automic_set：设置原子变量的数值
（4）：automic_read：读取原子变量的数值
4：同步机制–completion
a）：completion提供了一种等待完成的机制
b）：提供的调用
（1）：wait_for_completion：等待操作完成
（2）：complete：完成的信号
5：其他内核同步机制
a）：CPU变量 DEFINE_PER_CPU
b）：RCU锁
c）：顺序锁