Linux内核学习小结

网上学习总结的一些资料，加上个人的一些总结。

1. Linux内核可以分成基础层和应用层。
   基础层包括数据结构，内核同步机制，内存管理，任务调度。
   应用层包括文件系统，设备和驱动，网络，虚拟化等。文件系统是应用层的基础。

2. 内核基础层-数据结构
   双向链表
   hash链表
   红黑树: deadline调度算法 deadline-iosched.c 用到了红黑树。
   radix树：以空间冗余换时间消耗，代码见 /lib/radix-tree.c。Page cache的管理用到了radix tree。

3. 内核基础层-内存管理
   主要有伙伴系统内存管理和Slab内存管理两种。
   3.1 伙伴系统内存管理

   • 基于页面的内存管理 (1页=4096字节，每个页面地址上连续)。分配内存以页为单位。
   • 自动完成页面的分割与合并
   • alloc_pages(): 从伙伴系统申请内存。申请得到的是页面结构的指针，如果要得到内存地址，需要调用page_address()。_get_free_pages()可以直接得到内存地址。
     3.2 Slab系统内存管理
   • 基于对象的内存管理 (建立在伙伴系统之上)。分配内存不以页为单位。
   • 提供内存的构造函数和析构函数
   • kmem_cache_create: 创建Slab对象
   • kmem_cache_alloc: 申请内存
   • kmem_cache_free: 释放内存

4. 内核基础层-同步机制主要有自旋锁和信号量两种。
   4.1自旋锁 spin-lock
   我的理解是spin-lock主要是给多核同步用。如果是单核非抢占式，那么spin-lock没有什么作用。如果是单核抢占式，那么spin-lock起的作用是禁止抢占?。
   spin-lock如果没有抢到就busy-waiting，不会sleep。
   spin-lock可以用在interrupt-handler中，因为interrupt-handler不允许在里面sleep，spin-lock没抢到也不会sleep。
   4.2 信号量semaphore and mutex
   Semaphore计数可以多个，mutex计数只有一个。
   up: 释放信号量
   down: 获取信号量。如果没获取到就sleep
   down_trylock: 获取信号量。如果没获取到就立刻返回，不会进入sleep
   semaphore不可以用在interrupt-handler和tasklet等不能sleep的场景，因为Semaphore没抢到的话会sleep。
   对于可以sleep的场景，那就semaphore和spin-lock都可以用。spin-lock多用在轻量级场景。
   4.3 原子变量 - 读写不会被打断。用在简单的数据的读写上，比如多个进程读写一个公共int变量。
   atmoic_add - 加一个整数到原子变量
   atomic_sub - 减一个整数到原子变量
   atomic_set - 设置原子变量的数值
   atomic_read - 读取原子变量的数值
   4.4 completion - 提供一种等待完成的机制。类似信号量。
   wait_for_completion - 等待操作完成
   complete - 完成的信号
   4.5 CPU变量 - 每个CPU都有一个变量的备份
   DEFINE_PER_CPU
   4.6 RCU锁 - 免锁机制
   call_rcu
   rcu_read_lock
   4.7 顺序锁 - 适用于读多写少的场合
   read_seqbegin
   write_seqlock