这一节我们讲队列.
从前在乡下的时候是不用排队的,村里的人们都很谦让,而且人本来又不多.后来到了县城里,县城里不大,大家去走亲戚去串门去逛街不用坐车不用排队,除了街上的游戏厅人多一点以外,别的地方人都不是很多,陪妈妈去菜市场买菜也不用排队.后来到了上海,发现去食堂吃饭要排队,开学报道要排队,在人民广场等回复旦的123路公共汽车要排队,考试成绩不好去教务处交重修费要排队,甚至连追求一个女孩子也要排队.每次看见人群排成一条长龙时,才真正意识到自己是龙的传人.
随着子进程进入了我们的视野,我们来看其入口函数,hub_thread().这是一个令你大跌隐形眼镜的函数.
2817 static int hub_thread(void *__unused)
2818 {
2819 do {
2820 hub_events();
2821 wait_event_interruptible(khubd_wait,
2822 !list_empty(&hub_event_list) ||
2823 kthread_should_stop());
2824 try_to_freeze();
2825 } while (!kthread_should_stop() || !list_empty(&hub_event_list));
2826
2827 pr_debug("%s: khubd exiting/n", usbcore_name);
2828 return 0;
2829 }
这就是hub驱动中最精华的代码.这几乎是一个死循环,但是关于hub的所有故事都发生在这里,没错,就在这短短几行代码中.
而这其中,最核心的函数自然是hub_events().我们先不看hub_events,先把外面这几个函数看明白了,kthread_should_stop()的意思很明显,就是字面意思,是不是该停掉,如果是,那么这里循环就结束了,hub_thread()返回0,而要让kthread_should_stop()为真,就是当我们调用kthread_stop()的时候.这种情况,这个进程就该结束了.
再看hub_event_list,同样来自drivers/usb/core/hub.c:
83 static LIST_HEAD(hub_event_list); /* List of hubs needing servicing */
我们来看一下LIST_HEAD吧,当你越接近那些核心的代码,你就会发现关于链表的定义会越多.其实在usb-storage里面,我们也提到过一些链表,但却并没有自己用LIST_HEAD来定义过链表,因为我们用不着.可是hub这边就有用了,当然host controller的驱动程序里也会有,使用链表的目的很明确,因为有很多事情要做,于是就把它放进链表里,一件事一件事的处理,还记得我们当初在usb-storage里面提交urb request了吗?你U盘不停的提交urb request,他usb键盘也提交,我usb鼠标也提交,那usb host controller咋应付得过来呢?很简单,建一个队列,然后你每次提交就是往一个队列里边插入,然后usb host controller再统一去调度,一个一个来执行.那么这里hub,它有什么事件?比如探测到一个设备连进来了,于是就会执行一些代码去初始化设备,所以就建一个队列.所以,再一次证明了,谭浩强大哥的C程序设计是我们学习Linux的有力武器,书中对链表的介绍无疑是英明的,谭大哥,您不是一个人在战斗!关于Linux内核中的链表,可以专门写一篇文章了,我们简单介绍一下,来看include/linux/list.h,
21 struct list_head {
22 struct list_head *next, *prev;
23 };
24
25 #define LIST_HEAD_INIT(name) { &(name), &(name) }
26
27 #define LIST_HEAD(name) /
28 struct list_head name = LIST_HEAD_INIT(name)
可以看出,我们无非就是定义了一个struct list_head的结构体,hub_event_list,而且其两个指针next和prev分别是指向自己,换言之,我们建立了一个链表,而且是双向链表,并且做了初始化,初始化成一个空队列.而对于这个队列的操作,内核提供了很多函数可以使用,不过在usb hub中,我们将会用到这么几个函数,它们是,
294 /**
295 * list_empty - tests whether a list is empty
296 * @head: the list to test.
297 */
298 static inline int list_empty(const struct list_head *head)
299 {
300 return head->next == head;
301 }
不言自明,判断队列是否为空,我们说了,初始化的时候这个hub_event_list()队列是空的.
有了队列,自然就要操作队列,要往队列里加东西,减东西,就像我们每个人每天都在不停的走进去,又走出来,似是梦境又不是梦境.一切都是不经意的.走进去是一年四季,走出来是春夏秋冬.来看第二个函数,list_add_tail(),这就是往队列里加东西.
76 /**
77 * list_add_tail - add a new entry
78 * @new: new entry to be added
79 * @head: list head to add it before
80 *
81 * Insert a new entry before the specified head.
82 * This is useful for implementing queues.
83 */
84 static inline void list_add_tail(struct list_head *new, struct list_head *head)
85 {
86 __list_add(new, head->prev, head);
87 }
继续跟着__list_add()看就会发现其实就是往队列的末尾加一个元素.
43 static inline void __list_add(struct list_head *new,
44 struct list_head *prev,
45 struct list_head *next)
46 {
47 next->prev = new;
48 new->next = next;
49 new->prev = prev;
50 prev->next = new;
51 }
搞懂谭浩强那本书之后看这些链表的代码那就是小菜一碟.再来看下一个,list_del_init(),队列里的元素不能只加不减,没用了的元素就该删除掉,把空间腾出来给别人.郭敬明说过,我生命里的温暖就那么多,我全部给了你,但是你离开了我,你叫我以后怎么再对别人笑…
250 /**
251 * list_del_init - deletes entry from list and reinitialize it.
252 * @entry: the element to delete from the list.
253 */
254 static inline void list_del_init(struct list_head *entry)
255 {
256 __list_del(entry->prev, entry->next);
257 INIT_LIST_HEAD(entry);
258 }
从队列里删除一个元素,并且将该元素做初始化,首先看__list_del(),
148 /*
149 * Delete a list entry by making the prev/next entries
150 * point to each other.
151 *
152 * This is only for internal list manipulation where we know
153 * the prev/next entries already!
154 */
155 static inline void __list_del(struct list_head * prev, struct list_head * next)
156 {
157 next->prev = prev;
158 prev->next = next;
159 }
INIT_LIST_HEAD()其实就是初始化为最初的状态,即一个空链表.如下:
30 static inline void INIT_LIST_HEAD(struct list_head *list)
31 {
32 list->next = list;
33 list->prev = list;
34 }
当然了,还有超级经典的一个,list_entry(),和以上所有list方面的宏一样,也是来自include/linux/list.h:
419 /**
420 * list_entry - get the struct for this entry
421 * @ptr: the &struct list_head pointer.
422 * @type: the type of the struct this is embedded in.
423 * @member: the name of the list_struct within the struct.
424 */
425 #define list_entry(ptr, type, member) /
426 container_of(ptr, type, member)
我相信,list_entry()这个宏在Linux内核代码中的地位,就相当于广告词中的任静付笛生的洗洗更健康,相当于大美女关之琳的一分钟轻松做女人,这都是耳熟能详妇孺皆知的,是经典中的经典.如果你说你不知道list_entry(),那你千万别跟人说你懂Linux内核,就好比你不知道陈文登不知道任汝芬你就根本不好意思跟人说你考过研,要知道每个考研人都是左手一本陈文登右手一本任汝芬.
可惜,关于list_entry,这个谭浩强老师的书里就没有了,当然你不能指责谭浩强的书不行,再好的书也不可能包罗万象.这个宏应该说还是有一定技术含量的.我印象中外企面试笔试中,有三次比较经典的链表考题,其中对list_entry的解释就是其中一次,威盛的笔试,而另外两次是摩托罗拉中国研发中心和IBM.摩托罗拉那次是在中信泰富广场,问了我一道骨灰级的问题,给定一个链表,如何判断链表中是否有环,而IBM那次也是问的一道化石级的问题,说给定一个单向链表,请设计一个比较快的算法来找到该链表中的倒数第m个元素.像我这种低智商+不学无术的人怎么可能回答得出这样的问题.也许只有错过IBM这个我当时最心仪的公司才能给我留下刻骨铭心的伤痛吧.每一段文字都有一段刻骨铭心的经历,人们能看见我在屏幕上打的字,却看不见我流在键盘上的泪.我记得当年有一个房地产公司来我们学校招聘,是瑞安房地产,当时我一边投简历一边对同学说,要就别让我就了瑞安,进了瑞安我第一件事就是把IBM赶出瑞安广场,哼.算了,有些东西,注定和我们无缘,以前是,现在是,将来也是.
关于list_entry(),让我们结合实例来看,我们在hub的故事里会接触到的一个重要的数据结构就是struct usb_hub,来自drivers/usb/core/hub.c
34 struct usb_hub {
35 struct device *intfdev; /* the "interface" device */