发表于 | 分类于 ，

现实世界中存在着大量的设备，这些设备在电气特性和I/O方式上都各不相同。为了简化设备驱动程序员的工作，linux系统从这些各异的设备中抽象出共性的特征，将其划分为三大类：字符设备、块设备和网络设备。内核针对每一类设备都提供了对应的驱动模型框架，包括基本的内核设施和文件系统接口。这样，设备驱动程序员在编写某类设备驱动程序时，就有一套完整的驱动模型框架可以使用，从而可以将大量的精力放在设备本身的操作上。下图2-1展示了一个粗略的linux设备驱动程序结构图：

device_driver_framework.png
阅读全文 »

发表于 | 分类于 ，

klist是list的线程安全版本，它提供了整个链表的自旋锁，查找链表节点，对链表节点的插入和删除操作都要获得这个自旋锁。klist的节点数据结构是klist_node，klist_node引入引用计数，只有当引用计数减到0时才允许该node从链表中移除。当一个内核线程要移除一个node，必须要等待到node的引用计数释放，在此期间线程处于休眠状态。为了方便线程等待，klist引入等待移除节点者结构体klist_waiter，klist_waiter组成klist_remove_waiters（内核全局变量）链表，为保护klist_remove_waiters线程安全，引入klist_remove_lock（内核全局变量）自旋锁。为方便遍历klist，引入了迭代器klist_iter。

阅读全文 »

发表于 | 分类于 ，

在Linux内核中，hlist（哈希链表）使用非常广泛，本文将对其数据结构和核心函数进行分析。

和hlist相关的数据结构有两个

  1. hlist_head
  2. hlist_node
    1
    2
    3
    4
    5
    6
    7
    struct hlist_head {
            struct hlist_node *first;
    };
    struct hlist_node {
            struct hlist_node *next, **pprev;
    };

顾名思义，hlist_head表示哈希表的头结点。哈希表中每一个 entry (hlist_head) 所对应的都是一个链表（hlist)，该链表的结点由hlist_node表示。
hlist.jpg
hlist_head 结构体只有一个域，即first。first指针指向该 hlist 链表的第一个节点。

hlist_node结构体有两个域，next和pprev。 next指针很容易理解，它指向下个hlist_node结点，倘若该节点是链表的最后一个节点，next指向NULL。

pprev是一个二级指针，为什么我们需要这样一个指针呢？它的好处是什么？

阅读全文 »

发表于 | 分类于 ，

在linux内核中，有一种通用的双向循环链表，构成了各种队列的基础。链表的结构定义和相关函数均在include/linux/list.h中。

在阅读list.h文件之前，有一点必须注意：linux内核中的链表使用方法和一般数据结构中定义的链表是有所不同的。

一般的双向链表一般是如下的结构，

  • 有个单独的头结点(head)
  • 每个节点(node)除了包含必要的数据之外，还有2个指针(pre,next)
  • pre指针指向前一个节点(node)，next指针指向后一个节点(node)
  • 头结点(head)的pre指针指向链表的最后一个节点
  • 最后一个节点的next指针指向头结点(head)

具体见下图：
dlist.png

阅读全文 »

发表于 | 分类于 ，

参考原文链接：linux内核部件分析（三）——记录生命周期的kref
另外关于kref的使用可参考：
Linux内核里的“智能指针”
Linux内核里的“智能指针” (续)

kref是一个引用计数器，它被嵌套进其它的结构中，记录所嵌套结构的引用计数，并在计数为0时调用相应的清理函数。kref的原理和实现都非常简单，但要想用好却不容易，或者说kref被创建就是为了跟踪复杂情况下结构的引用和销毁。所以这里先介绍kref的实现，再介绍其使用规则。

阅读全文 »