1.每日自省; 2.享受人生; 3.尽力而为; 4.坚持不懈; 5.切莫急躁; 6.慎言敏行; 7.动心忍性; 8.上善若水。
全部博文(134)
分类: 嵌入式
2013-12-25 11:25:07
u16; /* 无符号字(16位) */
u32; /* 无符号32位 */
u64; /* 无符号64位 */
可用如sizeof(char)和sizeof(char*)等得出占有多少位。
32位编译器
char :1个字节
char*(即指针变量): 4个字节(32位的寻址空间是2^32, 即32个bit,也就是4个字节。同理64位编译器)
short int : 2个字节
int: 4个字节
unsigned int : 4个字节
float: 4个字节
double: 8个字节
long: 4个字节
long long: 8个字节
unsigned long: 4个字节
64位编译器
char :1个字节
char*(即指针变量): 8个字节
short int : 2个字节
int: 4个字节
unsigned int : 4个字节
float: 4个字节
double: 8个字节
long: 8个字节
long long: 8个字节
unsigned long: 8个字节
二、其他有关移植性的问题
2.1、时间间隔
使用jiffies计算时间间隔时,应该用HZ(每秒定时器中断的次数)来衡量。例如:半秒:HZ/2;
msec毫秒对应的jiffies数目:msec * HZ / 1000;
2.2、页大小
使用内存时,记住内存页的大小为PAGE_SIZE字节,而不是4KB。
三、链表
3.1、 链表数据结构简介
链表是一种常用的组织有序数据的数据结构,它通过指针将一系列数据节点连接成一条数据链,是线性表的一种重要实现方式。相对
于数组,链表具有更好的动态性,建立链表时无需预先知道数据总量,可以随机分配空间,可以高效地在链表中的任意位置实时插入或删
除数据。链表的开销主要是访问的顺序性和组织链的空间损失。
通常链表数据结构至少应包含两个域:数据域和指针域,数据域用于存储数据,指针域用于建立与下一个节点的联系。按照指针域的
组织以及各个节点之间的联系形式,链表又可以分为单链表、双链表、循环链表等多种类型,下面分别给出这几类常见链表类型的示意图:
3.1.1、单链表
图1 单链表
单链表是最简单的一类链表,它的特点是仅有一个指针域指向后继节点(next),因此,对单链表的遍历只能从头至尾(通常是NULL
空指针)顺序进行。
3.1.2、双链表
图2 双链表
通过设计前驱和后继两个指针域,双链表可以从两个方向遍历,这是它区别于单链表的地方。如果打乱前驱、后继的依赖关系,就可以
构成"二叉树";如果再让首节点的前驱指向链表尾节点、尾节点的后继指向首节点(如图2中虚线部分),就构成了循环链表;如果设计更多
的指针域,就可以构成各种复杂的树状数据结构。
3.1.3、循环链表
循环链表的特点是尾节点的后继指向首节点。前面已经给出了双循环链表的示意图,它的特点是从任意一个节点出发,沿两个方向的任
何一个,都能找到链表中的任意一个数据。如果去掉前驱指针,就是单循环链表。
在Linux内核中使用了大量的链表结构来组织数据,包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在[include/linux
/list.h]
实现的一个相当精彩的链表数据结构。本文的后继部分就将通过示例详细介绍这一数据结构的组织和使用。
3.2、内核链表数据结构的实现
2.6版本内核扩充了两种链表数据结构:链表的读拷贝更新(rcu)和HASH链表(hlist)。这两种扩展都是基于最基本的list结构,因此,
本文主要介绍基本链表结构,然后再简要介绍一下rcu和
hlist。
链表数据结构的定义很简单(节选自
点击(此处)折叠或打开
和第一节介绍的双链表结构模型不同,这里的list_head没有数据域。在Linux内核链表中,不是在链表结构中包含数据,而是
在数据结构中包含链表节点。
在数据结构课本中,链表的经典定义方式通常是这样的(以单链表为例):
点击(此处)折叠或打开
在Linux内核链表中,需要用链表组织起来的数据通常会包含一个struct
list_head成员,例如在
个nf_sockopt_ops结构来描述
Netfilter为某一协议族准备的getsockopt/setsockopt接口,其中就有一个(struct list_head
list)成员,各
个协议族的nf_sockopt_ops结构都通过这个list成员组织在一个链表中,表头是定义在
从下图中我们可以看到,这种通用的链表结构避免了为每个数据项类型定义自己的链表的麻烦。
图3 nf_sockopts链表示意图
3.3、 链表操作接口
3.3.1、声明和初始化
实际上Linux只定义了链表节点,并没有专门定义链表头,那么一个链表结构是如何建立起来的呢?让我们来看看LIST_HEAD()这个宏:
点击(此处)折叠或打开
点击(此处)折叠或打开
点击(此处)折叠或打开
3.3.2、插入/删除/合并
1、插入
对链表的插入操作有两种:在表头插入和在表尾插入。Linux为此提供了两个接口:
点击(此处)折叠或打开
点击(此处)折叠或打开
假设有一个新nf_sockopt_ops结构变量new_sockopt需要添加到nf_sockopts链表头,我们应当这样操作:
点击(此处)折叠或打开
2、删除
点击(此处)折叠或打开
当我们需要删除nf_sockopts链表中添加的new_sockopt项时,我们这么操作:
点击(此处)折叠或打开
3、搬移
Linux提供了将原本属于一个链表的节点移动到另一个链表的操作,并根据插入到新链表的位置分为两类:
点击(此处)折叠或打开
4、合并
除了针对节点的插入、删除操作,Linux链表还提供了整个链表的插入功能:
点击(此处)折叠或打开
图4 链表合并list_splice(&list1,&list2)
当list1被挂接到list2之后,作为原表头指针的list1的next、prev仍然指向原来的节点,为了避免引起混乱,Linux提供了一个
list_splice_init()函数:
点击(此处)折叠或打开
3.3.3、遍历
遍历是链表最经常的操作之一,为了方便核心应用遍历链表,Linux链表将遍历操作抽象成几个宏。在介绍遍历宏之前,我们先
看看如何从链表中访问到我们真正需要的数据项。
1、由链表节点到数据项变量
我们知道,Linux链表中仅保存了数据项结构中list_head成员变量的地址,那么我们如何通过这个list_head成员访问到作为它
的所有者的节点数据呢?Linux为此提供了一个list_entry(ptr,type,member)宏,其中ptr是指向该数据中list_head成员的指针,也
就是存储在链表中的地址值,type是数据项的类型,member则是数据项类型定义中list_head成员的变量名,
例如,我们要访问nf_sockopts链表中首个nf_sockopt_ops变量,则如此调用:
点击(此处)折叠或打开
list_entry的使用相当简单,相比之下,它的实现则有一些难懂:
点击(此处)折叠或打开
这里使用的是一个利用编译器技术的小技巧,即先求得结构成员在与结构中的偏移量,然后根据成员变量的地址反过来得出属主结
构变量的地址。
container_of()和offsetof()并不仅用于链表操作,这里最有趣的地方是((type
*)0)->member,它将0地址强制"转换"为type结
构的指针,再访问到type结构中的member成员。在container_of
宏中,它用来给typeof()提供参数(typeof()是gcc的扩展,和
sizeof()类似),以获得member成员的数据类型;在
offsetof()中,这个member成员的地址实际上就是type数据结构中member
成员相对于结构变量的偏移量。
如果这么说还不好理解的话,不妨看看下面这张图:
图5 offsetof()宏的原理
对于给定一个结构,offsetof(type,member)是一个常量,list_entry()正是利用这个不变的偏移量来求得链表数据项的变量地址。
2、遍历宏
在
点击(此处)折叠或打开
点击(此处)折叠或打开
那么在nf_register_sockopt()中实际上就是遍历nf_sockopts链表。为什么能直接将获得的list_head成员变量地址当成struct nf_sockopt_ops
数据项变量的地址呢?我们注意到在struct
nf_sockopt_ops结构中,list是其中的第一项成员,因此,它的地址也就是结构变量的地址。
更规范的获得数据变量地址的用法应该是:
点击(此处)折叠或打开
点击(此处)折叠或打开
点击(此处)折叠或打开
某些应用需要反向遍历链表,Linux提供了list_for_each_prev()和list_for_each_entry_reverse()来完成这一操作,使用方法和上面介绍
的list_for_each()、list_for_each_entry()完全相同。
如果遍历不是从链表头开始,而是从已知的某个节点pos开始,则可以使用
list_for_each_entry_continue(pos,head,member)。有时还
会出现这种需求,即经过一系列计算后,如果pos
有值,则从pos开始遍历,如果没有,则从链表头开始,为此,Linux专门提供了一个
list_prepare_entry(pos,head,member)宏,将它的返回值作为
list_for_each_entry_continue()的pos参数,就可以满足这一要求。
3.3.4、安全性考虑
当使用这些链表接口时,应该始终牢记这些链表函数不进行任何锁定。如果你的驱动程序有可能试图对同一链表执行并发操作的话,则有责任
实现一个锁方案。否则崩溃的链表结构体、数据丢失、内核混乱等问题是很难诊断的。
在并发执行的环境下,链表操作通常都应该考虑同步安全性问题。为了方便,Linux将这一操作留给应用自己处理。Linux链表自己考虑的安
全性主要有两个方面:
1、list_empty()判断
基本的list_empty()仅以头指针的next是否指向自己来判断链表是否为空,如果双向链表head为空则返回真,否则为假。Linux
链表另行提
供了一个list_empty_careful()宏,它同时判断头指针的next和prev,仅当两者都指向自己时才返回真。这主要是为了应付另一个cpu正在处理同
一个链表而造成next、prev不一致的情况。但代码注释也承认,这一安全保障能力有限:除非其他cpu的链表操作只有
list_del_init(),否则仍然
不能保证安全,也就是说,还是需要加锁保护。
2、遍历时节点删除
前面介绍了用于链表遍历的几个宏,它们都是通过移动pos指针来达到遍历的目的。但如果遍历的操作中包含删除pos指针所指向的节点,pos
指针的移动就会被中断,因为list_del(pos)将把pos的next、prev置成LIST_POSITION2和LIST_POSITION1的特殊值。
当然,调用者完全可以自己缓存next指针使遍历操作能够连贯起来,但为了编程的一致性,Linux链表仍然提供了两个对应于基本遍历操作的
"_safe"接口:list_for_each_safe(pos, n,
head)、list_for_each_entry_safe(pos, n, head,
member),它们要求调用者另外提供一个与pos
同类型的指针n,在for循环中暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。 如果循环可能会删除链表中的项,就应该使用该版
本。它只是简单地在循环的开始处把链表中的下一项存储在next中,这样如果cursor所指的项被删除也不会造成混乱。
3.4、 扩展
3.4.1、hlist
图6 list和hlist
精益求精的Linux链表设计者(因为list.h没有署名,所以很可能就是Linus
Torvalds)认为双头(next、prev)的双链表对于HASH表来说
"过于浪费",因而另行设计了一套用于HASH表应用的hlist数据结构 --单指针表头双循环链表,从上图可以看出,hlist的表头仅有一个指向首节点
的指针,而没有指向尾节点的指针,这样在可能是海量的HASH表中存储的表头就能减少一半的空间消耗。
因为表头和节点的数据结构不同,插入操作如果发生在表头和首节点之间,以往的方法就行不通了:表头的first指针必须修改指向新插入的节
点,却不能使用类似list_add()这样统一的描述。为此,hlist节点的prev不再是指向前一个节点的指针,而是指向前一个节点(可能是表头)中的
next(对于表头则是first)指针(struct list_head
**pprev),从而在表头插入的操作可以通过一致的"*(node->pprev)"访问和修改前驱节点
的next(或first)指针。
3.4.2、read-copy update
在Linux链表功能接口中还有一系列以"_rcu"结尾的宏,与以上介绍的很多函数一一对应。RCU(Read-Copy Update)是内核中引入的新技
术,它通过延迟写操作来提高同步性能。
我们知道,系统中数据读取操作远多于写操作,而rwlock机制在smp环境下随着处理机增多性能会迅速下降。针对这一应用背景,IBM
Linux
技术中心的Paul E.
McKenney提出了"读拷贝更新"的技术,并将其应用于Linux内核中。RCU技术的核心是写操作分为写-更新两步,允许读操作在
任何时候无阻访问,当系统有写操作时,更新动作一直延迟到对该数据的所有读操作完成为止。对RCU链表的使用和基本链表的使用方法基本相同。
3.5、C语言书中的链表
本节所设计的链表,以一个经典的存储学生学号和成绩的结构体作为例子,具体的结构体如下:
点击(此处)折叠或打开
首先建立一个链表,具体函数如下:
点击(此处)折叠或打开
输出链表:
点击(此处)折叠或打开
删除链表:
点击(此处)折叠或打开
增加一个节点:
点击(此处)折叠或打开
将一个链表逆序:
点击(此处)折叠或打开