共享 Linux 内核链表分析
有人写的内核链表分析,先放这儿漫漫看
发信人: jeffshia (小豆芽@_@冠玉^_^变成胡萝卜), 信区: KernelTech 标 题: linux-2.6.14之链表分析 发信站: 水木社区 (Sat Apr 1 11:05:39 2006), 转信 from:http://www.linuxforum.net/ Linux内核源码分析-链表代码分析 分析人:余旭 背景:开始在http://www.linuxforum.net/ Linux内核技术论坛上面发贴,在网友的帮忙 版权声明:版权保留。本文用作其他用途当经作者本人同意,转载请注明作者姓名 ************************************************** 如果想对某种类型创建链表,就把一个list_head类型的变量嵌入到该类型中,用list_head -------------防止重复包含同一个头文件--------------- -----------struct list_head{}及初始化宏--------- --LIST_HEAD_INIT()--LIST_HEAD()--INIT_LIST_HEAD()------ #define INIT_LIST_HEAD(ptr) do { / ------------__list_add()---list_add()------------- static inline void list_add(struct list_head *new, struct list_head *head -------------list_add_tail()------------------- -----------__list_del()---list_del()-------------- static inline void list_del(struct list_head *entry) ---------------list_del_init()-------------------- -----------list_move()--list_move_tail()---------- static inline void list_move_tail(struct list_head *list, struct list_head ---------------------list_empty()------------- --------------------list_empty_careful()--------- { ---------------__list_splice()------------------ first->prev = head; last->next = at; --------------------list_splice()---------------- ====>此处作者画了图,可显示不出来,郁闷!!! ========》待作者上传一个word文档,图在里面。 这种情况会丢弃list所指向的结点,这是特意设计的,因为两个链表有两个头结点, ------------------------------------------------------------------------- 特殊情况1: ------------------------------------------------------------------------ 特殊情况2: --------------------list_splice_init()----------------------------------- /** --------------------/asm-i386/posix_types.h------- ------/linux/types.h---------size_t--------------- 自己分析:即:__builtin_offsetof(a,b)就是#define offsetof(TYPE, MEMBER) ( 2.对offsetof()宏的分析:(以下引用论坛)---曾经的腾讯QQ的笔试题。 一共4步 2. ((TYPE *)0)->MEMBER 访问结构中的数据成员; ---------------------typeof()-------------------- ------------------------ ---------------container_of()-------------------- #define container_of(ptr, type, member) ({ / 2.typeof( ( (type *)0)->member )为取出member成员的变量类型。用其定义__mptr 3.(char *)__mptr转换为字节型指针。(char *)__mptr - offsetof(type,member) -----------茶余饭后一点小资料---------------------- --------------arch-v32/cache.h------------------ /* A cache-line is 32 bytes. */ #endif /* _ASM_CRIS_ARCH_CACHE_H */ -------------asm-i386/cache.h-------------------- #ifndef __ARCH_I386_CACHE_H /* L1 cache line size */ //largest L1 which this arch supports #endif |
----------/linux/prefetch.h--------------------
这里是内核中的解释:(含有自己的分析)
/*
prefetch(x) attempts to pre-emptively get the memory pointed to
by address "x" into the CPU L1 cache.
prefetch(x) should not cause any kind of exception, prefetch(0) is
specifically ok.
prefetch() should be defined by the architecture, if not, the
#define below provides a no-op define.
prefetch()当由体系结构来决定,否则就定义为空宏
有3类prefetch()宏:
There are 3 prefetch() macros:
prefetch(x) - prefetches the cacheline at "x" for read-->预取读
prefetchw(x) - prefetches the cacheline at "x" for write-->预取写
spin_lock_prefetch(x) - prefectches the spinlock *x for taking
there is also PREFETCH_STRIDE which is the architecure-prefered
"lookahead" size for prefetching streamed operations.
PREFETCH_STRIDE用于预取操作流。
These cannot be do{}while(0) macros.
*/
#define _LINUX_PREFETCH_H
#ifndef ARCH_HAS_PREFETCH
static inline void prefetch(const void *x) {;}
#endif
#ifndef ARCH_HAS_PREFETCHW
static inline void prefetchw(const void *x) {;}
#endif
#ifndef ARCH_HAS_SPINLOCK_PREFETCH
#define spin_lock_prefetch(x) prefetchw(x)
#endif
#ifndef PREFETCH_STRIDE
#define PREFETCH_STRIDE (4*L1_CACHE_BYTES)
#endif //PREFETCH_STRIDE
static inline void prefetch_range(void *addr, size_t len)
{
#ifdef ARCH_HAS_PREFETCH
char *cp;
char *end = addr + len;
for (cp = addr; cp < end; cp += PREFETCH_STRIDE)
prefetch(cp);
#endif //ARCH_HAS_PREFETCH
}
#endif //_LINUX_PREFETCH_H
-----asm-x86_64/processor.h---prefetch()---------
static inline void prefetch(void *x)
{
asm volatile("prefetcht0 %0" :: "m" (*(unsigned long *)x));
}
分析:
将x指针作强制类型转换为unsigned long *型,然后取出该内存操作数,送入高速缓
存。
----------------list_for_each()------------------
#define list_for_each(pos, head) /
for (pos = (head)->next; prefetch(pos->next), pos != (head); /
pos = pos->next)
----------------__list_for_each()-----------------
Linux Kernel 2.6.14中的解释中的精华部分:
/**
* This variant differs from list_for_each() in that it's the simplest possible
list iteration code, no prefetching is done.Use this for code that knows
the list to be very short (empty or 1 entry) most of the time.
*/
#define __list_for_each(pos, head) /
for (pos = (head)->next; pos != (head); pos = pos->next)
list_for_each()有prefetch()用于复杂的表的遍历,而__list_for_each()无prefetch
()用于简单的表的遍历.
注意:head在宏定义中用了括号将其括起来.
----------------list_for_each_prev()-------------
#define list_for_each_prev(pos, head) /
for (pos = (head)->prev; prefetch(pos->prev), pos != (head); /
pos = pos->prev)
解释类似上面的list_for_each()。
----------------list_for_each_safe()--------------
内核中解释的精华部分:
/*
* list_for_each_safe - iterate over a list safe against removal of list entry
*/
#define list_for_each_safe(pos, n, head) /
for (pos = (head)->next, n = pos->next; pos != (head); /
pos = n, n = pos->next)
这是说你可以边遍历边删除,这就叫safe。十分精彩。刚开始时,我也一直不理解safe
的意思,后来在http://www.linuxforum.net/论坛上搜索list_for_each_safe找到了解答。
----------------list_entry()--------------------
#define list_entry(ptr, type, member) /
container_of(ptr, type, member)
分析:
list_entry()函数用于将指向某链表结点成员的指针调整到该链表的开始处,并指针
转换为该链表结点的类型。
-------------list_for_each_entry()---------------
#define list_for_each_entry(pos, head, member) /
for (pos = list_entry((head)->next, t ypeof(*pos), member); /
prefetch(pos->member.next), &pos->member != (head); /
pos = list_entry(pos->member.next, typeof(*pos), member))
分析:
1.杨沙洲--国防科技大学计算机学院--2004年8月指出:
大多数情况下,遍历链表的时候都需要获得链表节点数据项,也就是说list_for_each
()和list_entry()总是同时使用。对此Linux给出了一个list_for_each_entry()宏。
2.这是用于嵌套的结构体中的宏:(这个程序例子来自:《Linux内核分析及编程》
作者:倪继利 电子工业出版社)
struct example_struct
{
struct list_head list;
int priority;
... //其他结构体成员
};
struct example_struct *node = list_entry(ptr,struct example_struct,list);
自己分析:对比list_entry(ptr,type,member)可知有以下结果:
其中list相当于member成员,struct example_struct相当于type成员,ptr相当于ptr
成员。而list{}成员嵌套于example_struct{}里面。ptr指向example_struct{}中的
list成员变量的。在list_entry()作用下,将ptr指针回转指向struct example_struct
{}结构体的开始处。
3.pos当指向外层结构体,比如指向struct example_struct{}的结点,最开始时候,
pos当指向第一个结点。而head开始时候也是指向第一个外层结点的里面的这个内嵌
的链表结构体struct list_head{},(head)->next则指向后继的一个外层结点的内嵌
的链表结点struct list_head{} list。member即是指出该list为其内嵌的结点。
思路:用pos指向外层结构体的结点,用head指向内层嵌入的结构体的结点。用(head
)->next,pos->member.next(即:ptr->list.next)来在内嵌的结构体结点链表中遍历
。每遍历一个结点,就用list_entry()将内嵌的pos->member.next指针回转为指向该
结点外层结构体起始处的指针,并将指针进行指针类型转换为外层结构体型pos。&pos
->member! = (head)用pos外层指针引用member即:list成员,与内层嵌入的链表之
头结点比较来为循环结束条件。
-------------list_for_each_entry_reverse()-------
#define list_for_each_entry_reverse(pos, head, member) /
for (pos = list_entry((head)->prev, typeof(*pos), m+ember); /
prefetch(pos->member.prev), &pos->member != (head); /
pos = list_entry(pos->member.prev, typeof(*pos), member))
分析类似上面。
---------------list_prepare_entry()---------------
1.函数背景:来自杨沙洲.国防科技大学计算机学院.2004年8月.http://www.linuxforum.net/
Linux 内核技术论坛:
杨在贴子中指出:如果遍历不是从链表头开始,而是从已知的某个pos结点开始,则
可以使用list_for_each_entry_continue(pos,head,member)。有时还会出现这种需
求,即经过一系列计算后,如果pos有值,则从pos开始遍历,如果没有,则从链表头
开始,为此,Linux专门提供了一个list_prepare_entry(pos,head,member)宏,将它
的返回值作为list_for_each_entry_continue()的pos参数,就可以满足这一要求。
2.内核中的list_prepare_entry()的注释及代码:
/**
* list_prepare_entry - prepare a pos entry for use as a start point in
* @pos: the type * to use as a start point
* @head: the head of the list
* @member: the name of the list_struct within the struct.
*/
内核源代码:
#define list_prepare_entry(pos, head, member) /
((pos) ? : list_entry(head, typeof(*pos), member))
分析:
:前面是个空值,即:若pos不为空,则pos为其自身。等效于:
(pos)? (pos): list_entry(head,typeof(*pos),member)
注意内核格式::前后都加了空格。
------------list_for_each_entry_continue()--------
3.内核中的list_for_each_entry_continue()的注释及代码:
/**
* list_for_each_entry_continue - iterate over list of given type
*continuing after existing point
* @pos: the type * to use as a loop counter.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
内核源代码:
#define list_for_each_entry_continue(pos, head, member) /
for (pos = list_entry(pos->member.next, typeof(*pos), member); /
prefetch(pos->member.next), &pos->member != (head); /
pos = list_entry(pos->member.next, typeof(*pos), member))
分析见list_prepare_entry()中的函数背景。
-------------list_for_each_entry_safe()-----------
1.函数背景:来自杨沙洲.国防科技大学计算机学院.2004年8月.http://www.linuxforum.net/
Linux 内核技术论坛:
杨在贴子中指出:list_for_each_entry_safe(pos, n, head,member),它们要求调
用者另外提供一个与pos同类型的指针n,在for循环中暂存pos下一个节点的地址,避
免因pos节点被释放而造成的断链。
2.内核中的注释与源代码:
/**
* list_for_each_entry_safe - iterate over list of given type safe against
removal of list entry
* @pos: the type * to use as a loop counter.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry_safe(pos, n, head, member) /
for (pos = list_entry((head)->next, typeof(*pos), member), /
n = list_entry(pos->member.next, typeof(*pos), member); /
&pos->member != (head); /
pos = n, n = list_entry(n->member.next, typeof(*n), member))
分析类似上面。容易明白。
--------list_for_each_entry_safe_continue()-------
#define list_for_each_entry_safe_continue(pos, n, head, member) /
for (pos = list_entry(pos->member.next, typeof(*pos), member), /
n = list_entry(pos->member.next, typeof(*pos), member); /
&pos->member != (head); /
pos = n, n = list_entry(n->member.next, typeof(*n), member))