深入浅出Linux之内核数据结构

内核使用的数据结构有双向链表，单向链表和hash链表。另外，基树和红黑树也是内核使用的数据结构。实际上，这也是程序代码中通常使用的数据结构，一些偏僻难的数据结构并不常见。1. container container是linux很重要的一个概念。有了container方法，才能实现对对象的封装。分析一下container方法。======================================================================#define container_of（ptr, type, member）（{ const typeof（（（type *）0）->member ） *__mptr = （ptr）; （type *）（（char *）__mptr - offsetof（type,member））;}）这个方法巧妙的实现了通过结构的一个成员找到整个结构的地址。有了container方法，list才成为了一个通用的数据结构，通过container方法，还可以实现内核的封装，程序之间不暴露内部的数据。 2. 双向链表list List定义在/include/linux目录下。首先看看list的结构定义： struct list_head { struct list_head *next, *prev; }; List是双向链表的一个抽象，list库提供了list_entry，使用了container方法，通过container 可以从list找到整个数据对象，这样list就成为了一种通用的数据结构。======================================================================#define list_entry（ptr, type, member） container_of（ptr, type, member）内核定义了很多对list结构操作的内联函数和宏，计有：

LIST_HEAD：定义并初始化一个list链表
list_add_tail：加一个成员到链表尾
list_del：删除一个list成员
list_empty：检查链表是否为空
list_for_each：遍历链表。得到链表指针。
list_for_each_safe：遍历链表。和list_for_each区别是可以删除遍历的成员
list_for_each_entry：遍历链表，通过container方法返回结构指针。

3. hash list Hash list和双向链表list很相似，它适用于hash表。看一下hash list的head定义： struct hlist_head { struct hlist_node *first;}; 和通常的list比较，hlist头只有一个指针，这样就节省了一个指针的内存。如果hash表非常庞大，那么每个hash 表头节省一个指针，整个hash表节省的内存就很可观了。这就是内核中专门定义hash list的原因。 Hash list库提供的函数和list很相似，计有：l HLIST_HEAD：定义并初始化一个hash list链表头l hlist_add_head：加一个成员到hash链表头l hlist_del：删除一个hash list成员l hlist_empty：检查hash 链表是否为空l hlist_for_each：遍历hash 链表。l hlist_for_each_safe：遍历链表。和hlist_for_each区别是可以删除遍历的成员l hlist_for_each_entry：遍历hash 链表，通过container方法返回结构指针 4. 单向链表内核中，没有提供单向链表的定义。但实际上，有多处使用了单向链表的概念。====================================================================== for （i = 0, p -= n; i < n; i++, p++, index++） { struct probe **s = &domain->probes[index % 255]; while （*s && （*s）->range < range） s = &（*s）->next; p->next = *s; *s = p; } 上面的例子是加入一个新的字符设备到系统的表里面。在系统的字符设备表里，probe结构其实就是单向链表。这种结构在内核中应用很广泛。 5. red-black tree 红黑树位于/lib/rbtree.c文件。红黑树是一种自平衡的二叉树。实际上，红黑树可以看做是折半查找。我们知道，排序的快速做法是取队列的中间值比较，然后在剩下的队列中再次取中间值比较，迭代进行直到找到最合适的位置。红黑树实际就是实现了这种算法。那么红黑树里面的“红黑”代表什么意思？红黑的颜色处理是避免树的不平衡。举个例子，如果1，2，3，4，5五个数字依次插入一颗红黑树，那么五个值都落在了树的右侧，如果6再插入这颗红黑树，那么需要比较五次。“红黑规则”就要将树旋转，树的根部要落在3这个节点，只需要比较两次，这样就避免了树的不平衡导致的问题。内核中的io调度算法和内存管理中都使用了红黑树。红黑树有很多介绍的文章，读者可以结合代码分析一下。 6. radix tree 内核提供了一个基树库，代码在/lib/radix-tree.c文件。基树是一种空间换时间的数据结构，通过空间的冗余减少了时间上的消耗。用一张图来分析：图中显示，元素空间总共为256，但元素个数不固定。那么如果用数组存储，好处是插入查找只用一次操作，但是存储空间需要256，这是不可思议的。如果用链表存储，存储空间节省了，但是极限情况下查找操作次数等于元素的个数。而采用一颗高度为2的基树，第一级最多16个冗余结构，代表元素前四位的索引。第二级代表元素后四位的索引。那么只要两级查找就可以找到特定的元素，而且只有少量的冗余数据。图中假设只有一个元素10001000，那么只有树的第一级有元素，而且树的第二级只有1000这个节点有子节点，其它节点都不必分配空间。这样既可以快速定位查找，也减少了冗余数据。基树很适合存储稀疏的数据，内核中文件的页cache就采用了基树。关于基树的文章很多，读者可以结合代码分析一下。Gnome Shell 下特效扩展：Focus-effects & Coverflow Alt-Tab深入浅出Linux之内核基础层相关资讯 Linux内核

IT人员必须了解的六项Linux内核变（今 12:05）
Linux 内核更新：3.10.98、3.14.62 （02月26日）
Linux：让手机运行主线内核（11/26/2015 22:16:17）

Linux内核自防护项目（05月24日）
Linux 内核架构的理解（12/09/2015 09:01:01）
Linux内核被指缺乏安全性（11/07/2015 08:28:47）

本文评论查看全部评论（0）