精华内容
下载资源
问答
  • 该结构体在linux内核中被大量引用,几乎所有内核当中需要构成链表结构的地方都用到了这个结构体。例如内核的总线设备就用到了这个结构体。 2、头结点的创建及初始化 struct list_head head =...

    1、list_head结构原型

    struct  list_head{
        struct  list_head *next,*prev;
    };

    此结构体构成的链表为双向循环链表。该结构体在linux内核中被大量引用,几乎所有内核当中需要构成链表结构的地方都用到了这个结构体。例如内核的总线设备就用到了这个结构体。

    2、头结点的创建及初始化

    struct list_head head ={
        &(head),&(head)
    };

    链表初始化时,head结构体的成员指向自己。如下图所示:

     

    3、链表的添加过程

    list_add(struct list_head *_new, struct list_head *prev,
        struct list_head *next)
    {
    	next->prev = _new;  // 1
    	_new->next = next;  // 2
    	_new->prev = prev;  // 3
    	prev->next = _new;  // 4
    }

    其中_new为新添加的结点,prev和next为头结点的两个成员,进行如上四步操作完成链表的添加,如下图所示:

    4、链表的使用方法

            该结构体只有纯粹的链表指针成员,不能直接用来链接数据。所以需要在其它结构体中加入该链表结构体,才能发挥该链表的作用。该链表可作为各种不同数据结构体的成员,也就是说它能将多种数据结构链接在一起,使用非常灵活。

            那么如何通过链表指针来得到某个结点上的数据呢?

            它是通过container_of宏,获得所在结点的结构体指针,再通过结构体指针来访问对应结点的数据的。

    5、container_of 宏

    container_of宏的作用为:知道结构体变量中某一个变量,用来反推这个结构体变量的指针。

    其定义为:

    #define container_of(ptr, type, member)                                      \
    ({                                                                           \
        const typeof(((type *) NULL)->member) *__mptr = (ptr);              \
        (type *) ((char *) __mptr - offsetof(type, member));                \
    })

    其实现可分为两个部分:

    第一部分:   const  typeof(((type *) NULL)->member) * __mptr = (ptr); 

            通过typeof定义一个member指针类型的指针变量__mptr,(即__mptr是指向member类型的指针),并将__mptr赋值为ptr。

    第二部分:   (type *) ((char *) __mptr - offsetof(type, member));    

           通过offsetof宏计算出member在type中的偏移,然后用member的实际地址__mptr减去偏移量,即可得到type的起始地址,即指向type类型的指针。

    6、linux_list.h的使用

    如下头文件,包含了对链表的一些基本操作,都是通过内联函数或者宏来实现的,可直接包含后使用。

    #ifndef _LINUX_LIST_H_
    #define _LINUX_LIST_H_
    
    #include <stddef.h>
    #include <stdbool.h>
    
    #define	prefetch(x)
    
    #ifndef container_of
    #define container_of(ptr, type, member)					\
    	({								\
    		const typeof(((type *) NULL)->member) *__mptr = (ptr);	\
    		(type *) ((char *) __mptr - offsetof(type, member));	\
    	})
    #endif
    
    struct list_head {
    	struct list_head *next;
    	struct list_head *prev;
    };
    
    #define LIST_HEAD_INIT(name) { &(name), &(name) }
    #undef LIST_HEAD
    #define LIST_HEAD(name)	struct list_head name = LIST_HEAD_INIT(name)
    
    //头结点初始化
    static inline void
    INIT_LIST_HEAD(struct list_head *list)
    {
    	list->next = list->prev = list;
    }
    //判断这个链表是否为空
    static inline bool
    list_empty(const struct list_head *head)
    {
    	return (head->next == head);
    }
    //判断该结点是否为头结点
    static inline bool
    list_is_first(const struct list_head *list,
    	      const struct list_head *head)
    {
    	return list->prev == head;
    }
    //判断该结点是否为尾结点
    static inline bool
    list_is_last(const struct list_head *list,
    	     const struct list_head *head)
    {
    	return list->next == head;
    }
    
    static inline void
    _list_del(struct list_head *entry)
    {
    	entry->next->prev = entry->prev;
    	entry->prev->next = entry->next;
    }
    //删除结点
    static inline void
    list_del(struct list_head *entry)
    {
    	_list_del(entry);
    	entry->next = entry->prev = NULL;
    }
    //添加结点
    static inline void
    _list_add(struct list_head *_new, struct list_head *prev,
        struct list_head *next)
    {
    
    	next->prev = _new;
    	_new->next = next;
    	_new->prev = prev;
    	prev->next = _new;
    }
    //删除这个元素并且初始化
    static inline void
    list_del_init(struct list_head *entry)
    {
    	_list_del(entry);
    	INIT_LIST_HEAD(entry);
    }
    
    #define	list_entry(ptr, type, field)	container_of(ptr, type, field)
    #define	list_first_entry(ptr, type, field)	list_entry((ptr)->next, type, field)
    #define	list_last_entry(ptr, type, field)	list_entry((ptr)->prev, type, field)
    
    //从前到后遍历链表
    #define	list_for_each(p, head)						\
    	for (p = (head)->next; p != (head); p = p->next)
    //删除当前结点不会造成断链
    #define	list_for_each_safe(p, n, head)					\
    	for (p = (head)->next, n = p->next; p != (head); p = n, n = p->next)
    //遍历链表上的结构体
    #define list_for_each_entry(p, h, field)				\
    	for (p = list_first_entry(h, typeof(*p), field); &p->field != (h); \
    	    p = list_entry(p->field.next, typeof(*p), field))
    
    #define list_for_each_entry_safe(p, n, h, field)			\
    	for (p = list_first_entry(h, typeof(*p), field),		\
    	    n = list_entry(p->field.next, typeof(*p), field); &p->field != (h);\
    	    p = n, n = list_entry(n->field.next, typeof(*n), field))
    
    #define	list_for_each_entry_reverse(p, h, field)			\
    	for (p = list_last_entry(h, typeof(*p), field); &p->field != (h); \
    	    p = list_entry(p->field.prev, typeof(*p), field))
    
    #define	list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = p->prev)
    #define	list_for_each_prev_safe(p, n, h) for (p = (h)->prev, n = p->prev; p != (h); p = n, n = p->prev)
    
    static inline void
    list_add(struct list_head *_new, struct list_head *head)
    {
    	_list_add(_new, head, head->next);
    }
    
    static inline void
    list_add_tail(struct list_head *_new, struct list_head *head)
    {
    	_list_add(_new, head->prev, head);
    }
    
    static inline void
    list_move(struct list_head *list, struct list_head *head)
    {
    	_list_del(list);
    	list_add(list, head);
    }
    
    static inline void
    list_move_tail(struct list_head *entry, struct list_head *head)
    {
    	_list_del(entry);
    	list_add_tail(entry, head);
    }
    
    static inline void
    _list_splice(const struct list_head *list, struct list_head *prev,
        struct list_head *next)
    {
    	struct list_head *first;
    	struct list_head *last;
    
    	if (list_empty(list))
    		return;
    
    	first = list->next;
    	last = list->prev;
    	first->prev = prev;
    	prev->next = first;
    	last->next = next;
    	next->prev = last;
    }
    
    static inline void
    list_splice(const struct list_head *list, struct list_head *head)
    {
    	_list_splice(list, head, head->next);
    }
    
    static inline void
    list_splice_tail(struct list_head *list, struct list_head *head)
    {
    	_list_splice(list, head->prev, head);
    }
    
    static inline void
    list_splice_init(struct list_head *list, struct list_head *head)
    {
    	_list_splice(list, head, head->next);
    	INIT_LIST_HEAD(list);
    }
    
    static inline void
    list_splice_tail_init(struct list_head *list, struct list_head *head)
    {
    	_list_splice(list, head->prev, head);
    	INIT_LIST_HEAD(list);
    }
    
    #endif /* _LINUX_LIST_H_ */

     

    展开全文
  • 如果数据量小或者不太在乎时间,选择list_head。 如果数据量大且对查找性能要求很高,读多写少的情况下,选择hlist。 如果数据量大且对查找性能要求很高,写操作相对多的情况下,选择hlist_nulls。 在涉及并发操作...

    我们被灌输过各种高效复杂的数据结构,比如rb tree,skip list等等,但现实中,我们经常用各种List管理我们的数据,因为它的操作非常简单。

    • 如果数据量小或者不太在乎时间,选择list_head。
    • 如果数据量大且对查找性能要求很高,读多写少的情况下,选择hlist。
    • 如果数据量大且对查找性能要求很高,写操作相对多的情况下,选择hlist_nulls。

    在涉及并发操作的环境中,对list的add,delete肯定需要某种并发保护,因为:

    • 无论是add还是delete操作本身均不是原子操作。

    但在具体的使用中,很多人搞不清该使用哪种类型的锁,于是就出现了以下的范式:

    • 懒省事者,无论是add,delete还是list_for_each,均用一把spinlock搞定。
    • 想优化性能却不想做太多的,直接把spinlock换成rwlock,一切看起来OK。
    • 如果写操作非常多且不能忍受性能损失,rculock搞定,同时保留add,delete的spinlock。

    但是事情真的有这么复杂吗?我看未必。

    事实上, 只要我们自己控制好写并发,读写是可以无锁并行的,只要保证我们的读操作中遍历链表的顺序是从前到后即可。

    我们看看这是为什么,先看add list:
    在这里插入图片描述
    我们看到,之所以add操作对遍历不影响,是因为:

    • 第一,遍历是始终单向向前的。
    • 第二,先将新节点的next接入链表,使从new节点可继续遍历。
    • 第三,再将链表节点的next指向新节点,使new节点可被遍历到。

    同时,我们知道在x86_64体系,对齐的指针操作是原子操作,所以,上面第三步就是原子操作,这保证了链表add操作和遍历操作是无冲突的:

    1. 遍历进程要么到达new。
    2. 遍历进程要么越过到达N2。
    3. 不会存在除1和2之外的其它情况。

    然而,如何保证上图中的顺序不会被编译器或者CPU给reorder呢?这很容易保证:

    • 增加一个屏障即可!

    长话短说,几乎 可以认为,x86_64体系,只有write-read序列存在CPU乱序的情况,所以乱序的情况并不会发生在链表操作中, “几乎” 以外的情况,参见:
    https://blog.csdn.net/dog250/article/details/103911008

    在Linux内核的链表操作接口中,上述的顺序以及原子保证是通过 _rcu 后缀来修饰的接口保证的,比如:

    • list_add_rcu/list_del_rcu
    • hlist_add_after_rcu/hlist_del_rcu
    • hlist_nulls_add_head_rcu/hlist_nulls_del_rcu

    以上的这些接口可以同时和同版本的for_each遍历同时进行而不会出现并发问题!也就是说,在保证不会同时add和del的前提下,可以实现无锁遍历。

    有了上面的理解,我们再看看del操作的流程:
    在这里插入图片描述
    和add操作一样,这也是个实实在在的RCU操作,其核心在于 最后更新

    关于rcu,我们必须清楚一件事,那就是遍历操作本身要通过rcu readlock保护,保证delete的节点在rcu readlock释放后再回收。

    最后,我们看一个关于hlist_nulls的遍历算法和其Insert/add,Remove/delete算法,来自内核文档Documents/RCU/rculist_nulls.txt:

    • Lookup算法:
    1) Lookup algo
    --------------
    rcu_read_lock()
    begin:
    obj = lockless_lookup(key);
    if (obj) {
      if (!try_get_ref(obj)) // might fail for free objects
        goto begin;
      /*
       * Because a writer could delete object, and a writer could
       * reuse these object before the RCU grace period, we
       * must check key after getting the reference on object
       */
      if (obj->key != key) { // not the object we expected
         put_ref(obj);
         goto begin;
       }
    }
    rcu_read_unlock();
    
    • Insert/add算法:
    2) Insert algo :
    ----------------
    /*
     * Please note that new inserts are done at the head of list,
     * not in the middle or end.
     */
    obj = kmem_cache_alloc(...);
    lock_chain(); // typically a spin_lock()
    obj->key = key;
    /*
     * we need to make sure obj->key is updated before obj->next
     * or obj->refcnt
     */
    smp_wmb();
    atomic_set(&obj->refcnt, 1);
    hlist_add_head_rcu(&obj->obj_node, list);
    unlock_chain(); // typically a spin_unlock()
    
    • Remove/delete算法:
    3) Remove algo
    --------------
    
    if (put_last_reference_on(obj) {
       lock_chain(); // typically a spin_lock()
       hlist_del_init_rcu(&obj->obj_node);
       unlock_chain(); // typically a spin_unlock()
       kmem_cache_free(cachep, obj);
    }
    

    在Linux内核的socket系统中,我们可以看到上述算法的具体实现,这是一个标准的算法,但是在特殊的环境下真的有必要这么复杂吗?lock_chain真的有必要吗?

    以socket系统为例,我们知道,socket是可以在内核中的软中断上下文被创建和销毁的,这里就会存在并发问题,因此Insert/Insert,Remove/Remove,Insert/Remove之间就会存在并发,所以必须lock_chain。

    但是如果我们保证节点的Insert和Remove均是在进程上下文的受控环境中进行的,比方说配置下发,那么我们只需要控制下发过程本身的并发即可,我们只要保证不会同时有Insert/Insert,Remove/Remove,Insert/Remove之间的并发即可,而这可以通过mutex来实现:

    int write_config(...)
    {
    	mutext_lock(&global_mutex);
    	insert_or_remove_some_nodes(...);
    	mutex_unlock(&global_mutex);
    }
    

    这样我们就可以省掉更多的spin开销,而我们知道mutex是可以re-schedule的,这便节省了CPU资源。

    你也不要怼我说re-schedule切换进程也是有开销的,这个开销可能比spinlock的开销更大,我承认这个点,但是我并非站在这个谁的开销大的立场上说这件事的,我的立场是:

    • 受控的环境比争抢的环境更好,我一向崇尚仲裁。

    至于怎么定义 “好” ,这便是形而上学的范畴了。

    举个例子,Linux内核的路由rule就是这么实现的。


    浙江温州皮鞋湿,下雨进水不会胖。

    展开全文
  • linux 内核 链表 list_head 使用方法.pdf
  • linux内核链表list_head的原理与使用一般的链表Linux内核中的链表list_head主要的操作内核链表的使用Liunx内核链表的原理 一般的链表 一般的链表如下,它是将数据结构塞入链表,这样的话,每一种数据结构都需要重新...

    一般的链表

    一般的链表如下,它是将数据结构塞入链表,这样的话,每一种数据结构都需要重新定义。

    struct student_node {
    	char name[20];
    	int age;
    	struct student_node *next;
    	struct student_node *prev;
    }
    

    Linux内核中的链表

    内核版本:4.1.15, 在目录include/linux/types.h中定义了list_head结构:

    struct list_head {
    	struct list_head *next, *prev;
    };
    

    可以看到,很简单,Linux不是将数据结构塞入链表,而是将链表塞入数据结构。

    list_head主要的操作

    在目录include/linux/types.h中定义了list_head的操作函数:

    static inline void INIT_LIST_HEAD(struct list_head *list) //初始化一个链表头,
    {													      //将其中的next和prev都指向自己
    	list->next = list;
    	list->prev = list;
    }
    
    static inline void __list_add(struct list_head *_new,   
    			      struct list_head *prev,
    			      struct list_head *next)
    {
    	next->prev = _new;
    	_new->next = next;
    	_new->prev = prev;
    	prev->next = _new;
    }
    
    static inline void list_add(struct list_head *new, struct list_head *head)//在头部添加一个节点
    {
    	__list_add(new, head, head->next);
    }
    
    static inline void list_add_tail(struct list_head *_new, struct list_head *head)//在尾部添加一个节点
    {
    	__list_add(_new, head->prev, head);
    }
    
    #define container_of(ptr, type, member) ({                      \ 
    	const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    	(type *)( (char *)__mptr - offsetof(type,member) );})
    
    #define list_entry(ptr, type, member) \ 
    	container_of(ptr, type, member)
    
    #define list_for_each_entry(pos, head, member)				\     //遍历head
    	for (pos = list_entry((head)->next, typeof(*pos), member);	\
    	     &pos->member != (head); 	\
    	     pos = list_entry(pos->member.next, typeof(*pos), member))
    

    内核链表的使用

    struct student {
        char name[20];
        int age;
        struct list_head list;
    };
    
    int main()
    {
        //struct list_head stu_head = {&stu_head, &stu_head};
        struct list_head stu_head;
        INIT_LIST_HEAD(&stu_head);
    
        struct student *stu1;
        stu1 = malloc(sizeof(*stu1));
        strcpy(stu1->name, "jack");
        stu1->age = 20;
    
        struct student *stu2;
        stu2 = malloc(sizeof(*stu2));
        strcpy(stu2->name, "bob");
        stu2->age = 30;
    
        struct student *stu3;
        stu3 = malloc(sizeof(*stu3));
        strcpy(stu3->name, "bobc");
        stu3->age = 31;
    
        list_add(&stu1->list, &stu_head);
        list_add(&stu2->list, &stu_head);
        list_add(&stu3->list, &stu_head);
    
        struct student *stu;
        list_for_each_entry(stu, &stu_head, list) {
            printf("stu->name=%s\n",stu->name);
        }
    	return 0;
    }
    

    输出如下:

    stu->name=bobc
    stu->name=bob
    stu->name=jack
    

    可以看到,linux内核中链表操作的都是list_head结构,那么它是怎样通过list_head来访问对应的数据结构里的成员的呢?

    Liunx内核链表的原理

    从上面的代码可以知道,遍历是通过list_for_each_entry宏来实现的,该宏是一个for循环,可以使用gcc的预编译命令来查看list_for_each_entry展开后的代码:

    gcc -E -o main.i main.c
    

    查看main.i中宏的位置,展开后如下:

        struct student *stu;
        for (stu = ({ const typeof( ((typeof(*stu) *)0)->list ) *__mptr = ((&stu_head)->next); (typeof(*stu) *)( (char *)__mptr - ((size_t) &((typeof(*stu) *)0)->list) );}); &stu->list != (&stu_head); stu = ({ const typeof( ((typeof(*stu) *)0)->list ) *__mptr = (stu->list.next); (typeof(*stu) *)( (char *)__mptr - ((size_t) &((typeof(*stu) *)0)->list) );})) {
            printf("stu->name=%s\n",stu->name);
        }
    

    展开后分为for循环中的三个部分:

    stu = ({ const typeof( ((typeof(*stu) *)0)->list ) *__mptr = ((&stu_head)->next); (typeof(*stu) *)( (char *)__mptr - ((size_t) &((typeof(*stu) *)0)->list) );})
    &stu->list != (&stu_head);
    stu = ({ const typeof( ((typeof(*stu) *)0)->list ) *__mptr = (stu->list.next); (typeof(*stu) *)( (char *)__mptr - ((size_t) &((typeof(*stu) *)0)->list) );})
    

    分别对应for语句中的三份代码,可以看到,遍历的终止条件是&stu->list != (&stu_head),如果&stu->list = (&stu_head),说明遍历到头节点了,循环结束,下面简化一下第一份代码:

    const list_head *__mptr = ((&stu_head)->next);
    (struct student *)( (char *)__mptr - ((size_t) &((struct student *)0)->list);
    

    可以看到, 最终stu的值是:

    (struct student *)( (char *)__mptr - ((size_t) &((struct student *)0)->list);
    

    将第一步细化实现如下:

        /*手动实现从list_head访问student*/
        struct list_head *mptr = stu_head.next;
        unsigned long long offset = (unsigned long long)(&(((struct student *)0)->list));
        mptr = (unsigned long long)mptr - offset;
        stu = (struct student *)mptr;
    
        printf("stu = %s %p\n", stu->name, stu);
        printf("stu1 = %p\n", stu1);
        printf("stu2 = %p\n", stu2);
        printf("stu3 = %p\n", stu3);
    

    输出如下:

    stu = bobc 0x55d8023972c0
    stu1 = 0x55d802397260
    stu2 = 0x55d802397290
    stu3 = 0x55d8023972c0
    

    可以看到,stu最终等于stu3,因为stu3最后一个插入。画了一份草图便于理解:
    在这里插入图片描述
    可以看到,linux能够实现从list_head访问到student主要是使用了offset,offset是student结构体的起始地址到list_head的大小,再使用list_head的地址减去这段大小即可得到该结构体的起始地址,从而访问结构体成员。

    代码链接

    展开全文
  • 做内核驱动开发经常会使用linux内核最经典的双向链表 list_head, 以及它的拓展接口(或者宏定义): list_add , list_add_tail, list_del , list_entry ,list_for_each , list_for_each_entry ...... 每次看到这些...

    做内核驱动开发经常会使用linux内核最经典的双向链表 list_head, 以及它的拓展接口(或者宏定义): list_add , list_add_tail, list_del , list_entry ,list_for_each , list_for_each_entry ...... 

          每次看到这些接口,感觉都很像,今天专门研究了一下内核,对它们做一些总结,希望为后续开发提供方便。

    首先找到list_head 结构体定义,kernel/inclue/linux/types.h  如下:  

    struct list_head {
    	struct list_head *next, *prev;
    };

    然后就开始围绕这个结构开始构建链表,然后插入、删除节点 ,遍历整个链表等等,其实内核已经提供好了现成的接口,接下来就让我们进入 kernel/include/linux/list.h中:
     

    一. 创建链表

        内核提供了下面的这些接口来初始化链表:

    #define LIST_HEAD_INIT(name) { &(name), &(name) }
     
    #define LIST_HEAD(name) \
    	struct list_head name = LIST_HEAD_INIT(name)
     
    static inline void INIT_LIST_HEAD(struct list_head *list)
    {
    	WRITE_ONCE(list->next, list);
    	list->prev = list;
    }

    如:  可以通过 LIST_HEAD(mylist) 进行初始化一个链表,mylist的prev 和 next 指针都是指向自己。

    struct list_head mylist = {&mylist,  &mylist};   

           但是如果只是利用mylist这样的结构体实现链表就没有什么实际意义了,因为正常的链表都是为了遍历结构体中的其它有意义的字段而创建的,而我们mylist中只有 prev和next指针,却没有实际有意义的字段数据,所以毫无意义。

          综上,我们可以创建一个宿主结构,然后在此结构中再嵌套mylist字段,宿主结构又有其它的字段(进程描述符 task_struct,页面管理的page结构,等就是采用这种方法创建链表的)。为简便理解,定义如下:

    struct  my_task_list {
        int val ;
        struct list_head mylist;
    }

    创建第一个节点

    struct my_task_list first_task = 
    { 
        .val = 1,
        .mylist = LIST_HEAD_INIT(first_task.mylist)
    };

    这样mylist 就prev 和 next指针分别指向mylist自己了,如下图:

     

    二. 添加节点

    内核已经提供了添加节点的接口了

    1.  list_add 

        如下所示。 根据注释可知,是在链表头head后方插入一个新节点new。

        并且还说了一句:这个接口利用实现堆栈  (why? 稍后再做分析)

    /**
     * list_add - add a new entry
     * @new: new entry to be added
     * @head: list head to add it after
     *
     * Insert a new entry after the specified head.
     * This is good for implementing stacks.
     */
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head, head->next);
    }

    list_add再调用__list_add接口

    /*
     * Insert a new entry between two known consecutive entries.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_add(struct list_head *new,
    			      struct list_head *prev,
    			      struct list_head *next)
    {
    	if (!__list_add_valid(new, prev, next))
    		return;
     
    	next->prev = new;
    	new->next = next;
    	new->prev = prev;
    	WRITE_ONCE(prev->next, new);
    }

    其实就是在head 链表头后和链表头后第一个节点之间插入一个新节点。然后这个新的节点就变成了链表头后的第一个节点了。

    依然用上面的my_task_list结构体举例子

    首先我们创建一个链表头   header_task 

     LIST_HEAD(header_task);

       

    然后再创建实际的第一个节点

    struct my_task_list my_first_task = 
    { .val = 1,
      .mylist = LIST_HEAD_INIT(my_first_task.mylist)
    };

    接着把这个节点插入到header_task之后

    list_add(&my_first_task.mylist,  &header_task);

     

    然后在创建第二个节点,同样把它插入到header_task之后

    struct my_task_list my_second_task = 
    { .val = 2,
      .mylist = LIST_HEAD_INIT(my_second_task.mylist)
    };

    其实还可以用另外一个接口 INIT_LIST_HEAD 进行初始化(参数为指针变量), 如下:

    struct my_task_list my_second_task;
    my_second_task.val = 2;
    INIT_LIST_HEAD(&my_second_task.mylist);

     

    list_add(&my_second_task.mylist, &header_task)

    以此类推,每次插入一个新节点,都是紧靠着header节点,而之前插入的节点依次排序靠后,那最后一个节点则是第一次插入header后的那个节点。最终可得出:先来的节点靠后,而后来的节点靠前,“先进后出,后进先出”。所以此种结构类似于 stack“堆栈”, 而 header_task就类似于内核stack中的栈顶指针esp, 它都是紧靠着最后push到栈的元素。

    2. list_add_tail 接口 

    上面所讲的list_add接口是从链表头header后添加的节点。 同样,内核也提供了从链表尾处向前添加节点的接口list_add_tail. 让我们来看一下它的具体实现。

    /**
     * list_add_tail - add a new entry
     * @new: new entry to be added
     * @head: list head to add it before
     *
     * Insert a new entry before the specified head.
     * This is useful for implementing queues.
     */
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head->prev, head);
    }

    从注释可得出:(1)在一个特定的链表头前面插入一个节点

    (2)这个方法很适用于队列的实现 (why?)

    进一步把__list_add ()展开如下:

    /*
     * Insert a new entry between two known consecutive entries.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_add(struct list_head *new,
    			      struct list_head *prev,
    			      struct list_head *next)
    {
    	if (!__list_add_valid(new, prev, next))
    		return;
     
    	next->prev = new;
    	new->next = next;
    	new->prev = prev;
    	WRITE_ONCE(prev->next, new);
    }

        所以,很清楚明了, list_add_tail就相当于在链表头前方依次插入新的节点(也可理解为在链表尾部开始插入节点,此时,header节点既是为节点,保持不变)

        利用上面分析list_add接口的方法可画出数据结构图形如下。

    (1)创建一个 链表头(实际上应该是表尾), 同样可调用 LIST_HEAD(header_task);

        

     

    (2)插入第一个节点 my_first_task.mylist , 调用 list_add_tail(& my_first_task.mylist,  & header_task);

        

    (3) 插入第二个节点my_second_task.mylist,调用list_add_tail(& my_second_task.mylist,  &header_task);

     

    依此类推,每次插入的新节点都是紧挨着 header_task表尾,而插入的第一个节点my_first_task排在了第一位,my_second_task排在了第二位,可得出:先插入的节点排在前面,后插入的节点排在后面,“先进先出,后进后出”,这不正是队列的特点吗(First in First out)!

     

    三. 删除节点

          内核同样在list.h文件中提供了删除节点的接口 list_del(), 让我们看一下它的实现流程

    static inline void list_del(struct list_head *entry)
    {
    	__list_del_entry(entry);
    	entry->next = LIST_POISON1;
    	entry->prev = LIST_POISON2;
    }

     

    /*
     * 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;
    	WRITE_ONCE(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_entry(struct list_head *entry)
    {
    	if (!__list_del_entry_valid(entry))
    		return;
     
    	__list_del(entry->prev, entry->next);
    }

        利用list_del(struct list_head *entry) 接口就可以删除链表中的任意节点了,但需注意,前提条件是这个节点是已知的,既在链表中真实存在,切prev,next指针都不为NULL。

        

    四. 链表遍历

         内核是同过下面这个宏定义来完成对list_head链表进行遍历的,如下 :

    /**
     * list_for_each	-	iterate over a list
     * @pos:	the &struct list_head to use as a loop cursor.
     * @head:	the head for your list.
     */
    #define list_for_each(pos, head) \
    	for (pos = (head)->next; pos != (head); pos = pos->next)

    上面这种方式是从前向后遍历的,同样也可以使用下面的宏反向遍历​

    /**
     * list_for_each_prev	-	iterate over a list backwards
     * @pos:	the &struct list_head to use as a loop cursor.
     * @head:	the head for your list.
     */
    #define list_for_each_prev(pos, head) \
    	for (pos = (head)->prev; pos != (head); pos = pos->prev)

       而且,list.h 中也提供了list_replace( 节点替换)  list_move(节点移位)  ,翻转,查找等接口,这里就不在一一分析了。

     

    五. 宿主结构

    1.找出宿主结构  list_entry(ptr, type, member)

        上面的所有操作都是基于list_head这个链表进行的,涉及的结构体也都是:

    struct list_head {
    	struct list_head *next, *prev;
    };

            其实,正如文章一开始所说,我们真正更关心的是包含list_head这个结构体字段的宿主结构体,因为只有定位到了宿主结构体的起始地址,我们才能对对宿主结构体中的其它有意义的字段进行操作。

    struct  my_task_list {
        int val ;
        struct list_head mylist;
    }

    那我们如何根据mylist这个字段的地址而找到宿主结构my_task_list的位置呢???

          做linux驱动开发的同学是不是想到了LDD3这本书中经常使用的一个非常经典的宏定义呢!那就是:

    container_of(ptr, type, member)

        没错就是它,在LDD3这本书中的第三章字符设备驱动,以及第十四章驱动设备模型中多次提到,所以我觉得这个宏应该是内核最经典的宏之一。 那list.h中使用什么接口实现的这个转换功能呢?

    /**
     * list_entry - get the struct for this entry
     * @ptr:	the &struct list_head pointer.
     * @type:	the type of the struct this is embedded in.
     * @member:	the name of the list_head within the struct.
     */
    #define list_entry(ptr, type, member) \
    	container_of(ptr, type, member)

     list.h中提供了list_entry宏来实现对应地址的转换,但最终还是调用了container_of宏,所以container_of宏的伟大之处不言而喻。 那接下来让我们揭开她的面纱:

        此宏在内核代码 kernel/include/linux/kernel.h中定义(此处kernel版本为3.10;新版本4.13之后此宏定义改变,但实现思想保持一致)

    /** 
     * 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) ({          \  
        const typeof( ((type *)0)->member ) *__mptr = (ptr); \  
        (type *)( (char *)__mptr - offsetof(type,member) );})  

    而offsetof定义在 kernel/include/linux/stddef.h ,如下:

    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

    看下container_of宏的注释:

    (1)根据结构体重的一个成员变量地址导出包含这个成员变量mem的struct地址。

    (2)参数解释:

             ptr  : 成员变量mem的地址    

            type: 包含成员变量mem的宿主结构体的类型

            member: 在宿主结构中的mem成员变量的名称

            如果用我们之前定义的结构体struct my_task_list举例

    struct  my_task_list {
        int val ;
        struct list_head mylist;
    }
    struct my_task_list first_task = 
    { .val = 1,
      .mylist = LIST_HEAD_INIT(first_task.mylist)
    };

        ptr   :    &first_task.mylist

        type  :  struct my_task_list

        member :  mylist

    而container_of宏的功能就是根据 first_task.mylist字段的地址得出first_task结构的其实地址。

    把上面offsetof的宏定义代入container_of宏中,可得到下面定义:

    #define container_of(ptr, type, member) ({          \  
        const typeof( ((type *)0)->member ) *__mptr = (ptr); \  
        (type *)( (char *)__mptr - ((size_t) &((type *)0)->member) );})  

    再把宏中对应的参数替换成实参:

    const typeof( ((struct my_task_list *)0)->mylist ) *__mptr = (&first_task.mylist); \  
    (struct my_task_list *)( (char *)__mptr - ((size_t) &((struct my_task_list *)0)->mylist) );})  

    typeof 是 GNU对C新增的一个扩展关键字,用于获取一个对象的类型 ,比如这里((struct my_task_list *)0)->mylist 是把0地址强制转换成struct my_task_list 指针类型,然后取出mylist元素。 然后再对mylist元素做typeof操作,其实就是获取 my_task_list结构中mylist字段的数据类型struct list_head,所以这行语句最后转化为:

    const struct list_head *__mptr  = (&first_task.mylist);

    第二条语句中在用 __mptr这个指针 减去 mylist字段在 my_task_list中的偏移(把0地址强制转换成struct my_task_list指针类型,然后取出mylist的地址,此时mylist的地址也是相对于0地址的偏移,所以就是mylist字段相对于宿主结构类型struct my_task_list的偏移) 正好就是宿主结构的起始地址。C语言的灵活性得到了很好的展示!!!

     

    2. 宿主结构的遍历

            我们可以根据结构体中成员变量的地址找到宿主结构的地址, 并且我们可以对成员变量所建立的链表进行遍历,那我们是不是也可以通过某种方法对宿主结构进行遍历呢?    

            答案肯定是可以的,内核在list.h中提供了下面的宏:

    /**
     * list_for_each_entry	-	iterate over list of given type
     * @pos:	the type * to use as a loop cursor.
     * @head:	the head for your list.
     * @member:	the name of the list_head within the struct.
     */
    #define list_for_each_entry(pos, head, member)				\
    	for (pos = list_first_entry(head, typeof(*pos), member);	\
    	     &pos->member != (head);					\
    	     pos = list_next_entry(pos, member))

     其中,list_first_entry 和  list_next_entry宏都定义在list.h中,分别代表:获取第一个真正的宿主结构的地址; 获取下一个宿主结构的地址。它们的实现都是利用list_entry宏。

    /**
     * list_first_entry - get the first element from a list
     * @ptr:	the list head to take the element from.
     * @type:	the type of the struct this is embedded in.
     * @member:	the name of the list_head within the struct.
     *
     * Note, that list is expected to be not empty.
     */
    #define list_first_entry(ptr, type, member) \
    	list_entry((ptr)->next, type, member)
     
    /**
     * list_next_entry - get the next element in list
     * @pos:	the type * to cursor
     * @member:	the name of the list_head within the struct.
     */
    #define list_next_entry(pos, member) \
    	list_entry((pos)->member.next, typeof(*(pos)), member)

    最终实现了宿主结构的遍历

    #define list_for_each_entry(pos, head, member)				\
    	for (pos = list_first_entry(head, typeof(*pos), member);	\
    	     &pos->member != (head);					\
    	     pos = list_next_entry(pos, member))

     首先pos定位到第一个宿主结构地址,然后循环获取下一个宿主结构地址,如果查到宿主结构中的member成员变量(宿主结构中struct list_head定义的字段)地址为head,则退出,从而实现了宿主结构的遍历。如果要循环对宿主结构中的其它成员变量进行操作,这个遍历操作就显得特别有意义了。

            我们用上面的 my_task_list结构举个例子:

    struct my_task_list *pos_ptr = NULL ; 
    list_for_each_entry (pos_ptr, & header_task, mylist ) 
    { 
        printk ("val =  %d\n" , pos_ptr->val); 
    }

        

    参考文档:https://kernelnewbies.org/FAQ/LinkedLists

                    《Understanding linux kernel》

                    《Linux device drivers》

    展开全文
  • Linux内核链表list_head

    千次阅读 2014-08-10 10:53:07
    1、内核链表的定义在include/linux/list.h struct list_head {  struct list_head *next, *...2、Linux链表与普通链表区别 我们通常定义的链表是在链表节点中嵌入元素,比如 struct MyList {  int StudentID; 
  • 前言:一起分析内核最重要的链表list_head 一、链表结构 struct list_head { struct list_head *next, *prev; }; 二、链表初始化函数 list_head 链表的初始化只是把 *next, *prev连个指针指向链表头,形成双向循环...
  • 一、双链表list_head 1、基本概念 linux内核提供的标准链表可用于将任何类型的数据结构彼此链接起来。 不是数据内嵌到链表中,而是把链表内嵌到数据对象中。 即:加入链表的数据结构必须包含一个类型为list_head...
  • Linux内核中经典链表 list_head 常见使用方法解析

    万次阅读 多人点赞 2018-07-03 17:49:07
    做内核驱动开发经常会使用linux内核最经典的双向链表 list_head, 以及它的拓展接口(或者宏定义): list_add , list_add_tail, list_del , list_entry ,list_for_each , list_for_each_entry ...... 每次看到这些...
  • 深入浅出linux内核源代码之双向链表list_head,深入地讲解了list_head的结构和相关的函数,非常好,包会的。
  • 做内核驱动开发经常会使用linux内核最经典的双向链表 list_head, 以及它的拓展接口(或者宏定义): list_add , list_add_tail, list_del , list_entry ,list_for_each , list_for_each_entry ...... 每次看到这些...
  • 深入浅出linux内核源代码之双向链表list_head pdf文档和代码
  • Linux的双链表list_head

    千次阅读 2012-08-27 13:22:51
    链表在include/linux/types.h中...include/linux/list.h中定义了链表的操作。 这个结构经常作为成员与其他数据类型一起组成一个新的结构体(后文若无特别提示,“新结构体”均指类似下面举例的嵌套型结构体),比如:
  • linux内核源码“双向链表list_head
  • 双向链表 list_head

    2019-03-02 15:05:31
    struct list_head { ...linux/list.h&gt;中定义其相关的操作。 主要API简介: 函数 作用 INIT_LIST_HEAD() 初始化表头 list_add 在表头后增加一个元素 list_add_tail 在链...
  • linux内核源码“双向链表list_head”续
  • 1. linux 内核中循环链表 内核中的循环链表实现: struct list_head{ struct list_head *next, *prev; }; 平时我们用的循环链表实现: struct list{ struct list *next, *prev; int value; }; 两者区别在于,list_...
  • Linux 内核)双向循环链表list_head

    千次阅读 2017-08-17 15:48:01
    什么是双向循环链表就不说了,学习linux的应该都有C家族的基础。 struct list_head {  struct list_head *next, *prev; }; list_head不是拿来单独用的,它一般被嵌到其它结构中,如: struct str{  char c...
  • Linux内核中,提供了一个用来创建双向循环链表的结构 list_head。虽然linux内核是用C语言写的,但是list_head的引入,使得内核数据结构也可以拥有面向对象的特性,通过使用操作list_head 的通用接口很容易实现代码...
  • 深入浅出linux内核源代码之双向链表list_head(list.h).pdf
  • Linux内核链表list_head扩展---klist

    千次阅读 2011-03-08 01:15:00
    内核代码: include/linux/klist.h lib/klist.c ---------------------- 先要有一点点预备知识——list_head ---------------------- 先看看头文件如何定义klist,以及一些基本操作方法接口。 ---------------------...
  • 一 为什么要重构Linux中的双向循环链表? 第一,首先 Linux内核双向循环链表的实现依赖于GNU编译器,里面有一些语法是GUN编译器的语法,标准C编译器不能使用它。所以需要清除平台相关代码。 1 ({}) 2 typeof() 3 _...
  • 内核中的链表list_head

    2013-11-27 11:06:30
    linux内核中,链表的实现是通过把链表结点嵌入到数据... struct list_head list;  dma_addr_t dma_handle;  char *buf;  u32 bytesused;  u32 readpos; }; 链表结构体的定义在include\linux\types.h中: struc
  • 前言: 在linux 源代码中有个头文件为list.h 。很多linux 下的源代码都会使用这个头文件,它里面定义了一个结构, 以及定义了和其相关的一组函数,这个结构是这样的:   struct list_head{ struct list_head *...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,976
精华内容 12,390
关键字:

linux链表list_head

linux 订阅