Linux 内核代码赏析与应用(三)-链表API之应用

如前文所述,Linux内核中的代码,经过稍加改造后,可以在用户态下使用。
linclude/linux/list.h 中的函数和宏,是一组精心设计的API,有比较完整的注释和清晰的思路。在用户态下使用list.h,查看改造后的list.h
1. 举例
下面是用户态下的例子,用以创建、增加、删除和遍历一个双向链表。

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct kool_list{
	int to;
	struct list_head list;
	int from;
	};

int main(int argc, char **argv){

	struct kool_list *tmp;
	struct list_head *pos, *q;
	unsigned int i;

	struct kool_list mylist;
	INIT_LIST_HEAD(&mylist.list); /*初始化链表头*/

	/* 给mylist增加元素 */
	for(i=5; i!=0; --i){
	tmp= (struct kool_list *)malloc(sizeof(struct kool_list));

	/* 或者INIT_LIST_HEAD(&tmp->list); */
	printf("enter to and from:");
	scanf("%d %d", &tmp->to, &tmp->from);

	list_add(&(tmp->list), &(mylist.list));
	/* 也可以用list_add_tail() 在表尾增加元素*/
	}
	printf("\n");

	printf("traversing the list using list_for_each()\n");
	list_for_each(pos, &mylist.list){

	/* 在这里 pos->next 指向next 节点, pos->prev指向前一个节点.这里的节点是
        struct kool_list类型. 但是,我们需要访问节点本身,
        而不是节点中的list字段,宏list_entry()正是为此目的。*/
	tmp= list_entry(pos, struct kool_list, list);

	printf("to= %d from= %d\n", tmp->to, tmp->from);

	}
	printf("\n");
	/* 因为这是循环链表,也可以以相反的顺序遍历它,
	*为此,只需要用'list_for_each_prev'代替'list_for_each',
	* 也可以调用list_for_each_entry() 对给定类型的节点进行遍历。
	* 例如:
	*/
	printf("traversing the list using list_for_each_entry()\n");
	list_for_each_entry(tmp, &mylist.list, list)
	printf("to= %d from= %d\n", tmp->to, tmp->from);
	printf("\n");

	/*现在,我们可以释放 kool_list节点了.我们本可以调用 list_del()删除节点元素,
	* 但为了避免遍历链表的过程中删除元素出错,因此调用另一个更加安全的宏 list_for_each_safe(),
	* 具体原因见后面的分析*/

	printf("deleting the list using list_for_each_safe()\n");
	list_for_each_safe(pos, q, &mylist.list){
	tmp= list_entry(pos, struct kool_list, list);
	printf("freeing item to= %d from= %d\n", tmp->to, tmp->from);
	list_del(pos);
	free(tmp);
	}

	return 0;
}

2. 关于删除元素的不安全性
为什么说调用list_del()删除元素有安全隐患?具体看源代码:
/*
* Delete a list entry by making the prev/next entries
* point to each other.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
/**
* list_del – deletes entry from list.
* @entry: the element to delete from the list.
* Note: list_empty on entry does not return true after this, the entry is
* in an undefined state.
*/
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
可以看出,当执行删除操作的时候, 被删除的节点的两个指针被指向一个固定的位置(entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;)。而list_for_each(pos, head)中的pos指针在遍历过程中向后移动,即pos = pos->next,如果执行了list_del()操作,pos将指向这个固定位置的next, prev,而此时的next, prev没有任何意义,别无选择,出错。
而list_for_each_safe(p, n, head) 宏解决了上面的问题:
/**
* list_for_each_safe    –    iterate over a list safe against removal of list entry
* @pos:    the &struct list_head to use as a loop counter.
* @n:        another &struct list_head to use as temporary storage
* @head:    the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
它采用了一个同pos同样类型的指针n 来暂存将要被删除的节点指针pos,从而使得删除操作不影响pos指针!

实际上,list.h的设计可谓精益求精,煞费苦心,用简洁的代码突破计算机科学中传统的链表实际机制,不仅考虑了单处理机,还利用了Paul E. McKenney提出的RCU(读拷贝更新)的技术,从而提高了多处理机环境下的性能。关于RCU,请看http://www.rdrop.com/users/paulmck/rclock/

后记:
链表,是一个古老而没有新意的话题,关于其分析的文章,也随处可见。之所以重提旧话题,是因为在讲课的过程中,每当我对那些复杂的事物进行剖析 时,剥去一层层外衣,发现,最终的实现都掉落在计算机科学最根本的问题上,比如各种最基本的数据结构,可这些,往往又是学生们不屑一顾的。在此,把链表那拿出来分析,是希冀学子们有时间关注计算机科学的根本问题。
.

发表评论

电子邮件地址不会被公开。 必填项已用*标注