Kernel中的红黑树
红黑树是一种平衡二叉树。
基于5.16内核。
头文件定义：include/linux/rbtree.h、include/linux/rbtree_types.h
结构定义12345678910struct rb_node { unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left;} __attribute__((aligned(sizeof(long))));/* The alignment might seem pointless, but allegedly CRIS needs it */struct rb_root { struct rb_node *rb_node;};
其中rb_node是节点类型，rb_root表示根节点。
rb_node中__rb_parent_color同时定义了父节点和颜色值。由于该该结构体需要大小为sizeof(long)对齐，不管是在32位还是64位上，其地址的最后两个bit永远是0，因此就可 ...
Kernel中的地址转换
在Linux中的地址转换如下图所示，逻辑地址通过段选择子查询GDT得到段描述，然后加上偏移得到线性地址（虚拟地址），而在Linux中并没有完整的使用分段机制，它让所有的段都指向相同的地址范围，段的基地址都为0，也就是说逻辑地址和线性地址在数值上就相同了。在由分页机制将线性地址转换为物理地址
在Linux系统中，为了兼容32位和64位，它需要一个统一的页面地址模型，目前常用的是4级页表模型。包括PGD页全局目录、PUD页上级目录、PMD页中级目的、PTE页表。根据情况某些页表不会被使用，每个页表项的大小会根据计算机体系结构的不同做相应的改变。例如没有启用物理地址扩展的32位系统来说，两级页表页表就够了，那么Linux会在线性地址中，会让PUD和PMD索引置为0，从根本上取消了这两个字段，但是这两个页目录在指针序列中的位置仍然被保留下来，也就是说在寻址过程中不能通过PUD和PMD直接都页表，内核会将这两个页目录表项都置为1。
由于64位系统硬件限制，实际的地址线有48条，所以线性地址实际使用也只有48位。在64位Linux中使用了4级页表结构。线性地址划分如下：
PGD、PUD、PM ...
操作系统之段页式内存管理
分段分段可以说是Intel的CPU一直保持着的一种机制，而分页只是保护模式下的一种内存管理策略。不过想开启分页机制，CPU就必须工作在保护模式，而工作在保护模式时候可以不开启分页。
首先是全局段描述符表：
结构体后的__attribute__((packed))是GCC的扩展，用来设置该结构体不进行字节对齐。
段描述符表定义：
GDTR定义：
段描述符表的部分以二进制位来表示的设置信息合并到了相应的字节里，这里按照位域去定义不是不可以，但是太过于臃肿了。
全局描述符表的定义以及设置一项描述符的函数实现：
初始化函数：
最后有一个加载全局描述附表的函数，这个函数用汇编来实现了。代码如下：
CPU在保护模式下分页未开启和分页开启的不同状态时，MMU组件处理地址的流程。
如果没有开启分页：
逻辑地址->段机制处理->线性地址=物理地址
如果开启分页：
逻辑地址->段机制处理->线性地址->页机制处理->物理地址
因为我们采用了平坦模式，所以给出的访问地址实际上已经是线性地址了(段基址为0)，那么剩下的问题就是所谓的页机制处理 ...
操作系统之中断和异常处理
中断和异常的作用是指示系统中的某个地方发生一些事件, 需要引起处理器(包括正在执行中的程序和任务)的注意. 当中断和异常发生时, 典型的结果是迫使处理器将控制从当前正在执行的程序或任务转移到另一个历程或任务中去. 该例程叫做中断处理程序, 或者异常处理程序. 如果是一个任务, 则发生任务切换.
中断包括硬件中断和软中断.
硬件中断是由外围硬件设备发出的中断信号引发的, 以请求处理器提供服务. 当I/O接口发出中断请求时, 会被像8259A和I/O APIC这样的中断控制器收集, 并发送到处理器. 硬件中断完全是随机产生的, 与处理器的执行并不同步. 当中断发生时, 处理器要先执行完当前的指令, 然后才对中断进行处理。
软中断是由 int n 指令引发的中断处理, n是中断号或者叫类型码.
中断处理程序是运行在ring0层的，这就意味着中断处理程序拥有着系统的全部权限。Intel设置了一个叫做中断描述符表（IDT, Interrupt Descriptor Table）的东西，和段描述符表一样放置在主存中，类似地，也有一个中断描述符表寄存器（IDTR）记录这个表的起始 ...
操作系统之保护模式
实模式（Real Mode)：又名 Real Address Mode，在此模式下地址访问的是真实地内存地址所在位置。在此模式下，可以使用20位（1MB）的地址空间，软件可以不受限制的操作所有地址的空间和IO设备。
保护模式（Protected Mode)：又名 Protected Virtual Address Mode，采用虚拟内存、页等机制对内存进行了保护，比起实模式更为安全可靠，同时也增加了灵活性和扩展性。
现在的64位处理器，拥有三种基本模式（保护模式、实模式、系统管理模式）和一种扩展模式（IA-32e模式（又分兼容模式和64位模式
在8086中，实模式采取内存段来管理 0 - 0xFFFFF的这1M内存空间，但是由于只有16位寄存器，所以最大地址只能表示为0xFFFFF（64KB)，因此不得不采取将内存按段划分为64KB的方式来充分利用1M空间。也就是上所示的，采取段选择子 + 偏移量的表示法，直接输出的就是物理地址，CPU 可以直接用此地址访问内存 ，计算如下：
1PhysicalAddress = Segment Selector * 16 + Offset
...
Kernel中的哈希表
哈表表的定义哈希表，是根据键值（key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中的一个位置来访问记录，加快了查找速度。这个映射函数就叫做散列函数，存放记录的数组称作散列列表。
12345678// 哈希头struct hlist_head { struct hlist_node *first;};// 哈希节点struct hlist_node { struct hlist_node *next, **pprev;};
哈希表包含两个数据结构，一个是哈希链表节点hlist_node，另一个是哈希表头hlist_head。可以看到哈希节点hlist_node和内核普通双向链表的节点唯一的区别就在于，前向节点pprev是个两级指针。同时并没有使用hlist_node作为哈希表头，而是重新定义了hlist_head结构体，这是因为哈希链表并不需要双向循环，为了节省空间使用一个指针first指向该哈希表的第一个节点就可以了。整个哈希表结构如下图所示，其中ppre是个二级指针，它指向前一个节点 ...
遍历kernel进程链表
linux内核中使用task_struct结构来描述一个PCB（linux/kernel/sched.c）。多个进程则常常使用双链表等来进行组织。比如可运行状态的进程组成可运行队列，等待状态的进程组成等待队列等。
list.h的遍历宏：
1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */#define container_of(ptr, type, member) ({ \ void *__mptr ...
Kernel链表list.h分析
Kernel中链表的声明和初始化list.h定义在include/linux/list.h中
Kernel中的链表定义如下：
123struct list_head { struct list_head *next, *prev;};
仅仅只有两个指针没有数据的双向循环链表。因此，如果需要定义一个能存储链表的结构，如下：
1234struct data_list { int data; struct list_head list;}
链表初始化：
1234#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name)
此处初始化声明了一个首尾都是指向自己的链表。在list.h中，除了初始化链表宏，还有初始化函数：
1234567891011121314151617181920212223#define __WRITE_ONCE(x, ...
运行扇区外的程序
运行扇区外的程序目标：使启动扇区的BootLoader程序可以启动普通扇区内的程序
BootLoader启动扇区
所以程序需要准备一份“简历”，告诉BootLoader，BootLoader才能正确读取、加载并运行程序。这段程序要放到最前面，好让BootLoader读取第一个扇区后，就能获知所有的信息
而对于BootLoader，结构为：
CodeProgram.asm
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109HDDPORT equ 0x1f0section code align=16 vstart=0x7c00 mov si, [READSTART] mov cx, [READSTA ...
QEMU启动hda文件系统
QEMU启动hda文件系统创建文件系统，大小为16M
1dd if=/dev/zero of=./rootfs.img bs=1M count=16
格式化
1mkfs.ext3 rootfs.ext3
挂载文件系统
1mount -o loop rootfs.img ./fs
此时在/dev下有个loop0的设备
写入磁盘引导和数据
12dd if=./readhdd.bin of=/dev/loop0 bs=512 count=1dd if=./data of=/dev/loop0 seek=10 bs=512 count=1
卸载硬盘
1umount /dev/loop0
qemu虚拟机启动
1qemu-system-x86_64 -hda rootfs.img
或者写入时：
1dd if=./readhdd.bin of=/dev/loop0 bs=512 count=1 conv=notrunc
notrunc规定在写入数据后不截断
