分类： LINUX
2009-04-30 15:54:30
这一节我们讲队列.
从前在乡下的时候是不用排队的,村里的人们都很谦让,而且人本来又不多.后来到了县城里,县城里不大,大家去走亲戚去串门去逛街不用坐车不用排队,除了街上的游戏厅人多一点以外,别的地方人都不是很多,陪妈妈去菜市场买菜也不用排队.后来到了上海,发现去食堂吃饭要排队,开学报道要排队,在人民广场等回复旦的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 */
36 struct usb_device *hdev;
37 struct urb *urb; /* for interrupt polling pipe */
38
39 /* buffer for urb ... with extra space in case of babble */
40 char (*buffer)[8];
41 dma_addr_t buffer_dma; /* DMA address for buffer */
42 union {
43 struct usb_hub_status hub;
44 struct usb_port_status port;
45 } *status; /* buffer for status reports */
46 struct mutex status_mutex; /* for the status buffer */
47
48 int error; /* last reported error */
49 int nerrors; /* track consecutive errors */
50
51 struct list_head event_list; /* hubs w/data or errs ready */
52 unsigned long event_bits[1]; /* status change bitmask */
53 unsigned long change_bits[1]; /* ports with logical connect
54 status change */
55 unsigned long busy_bits[1]; /* ports being reset or
56 resumed */
57 #if USB_MAXCHILDREN > 31 /* 8*sizeof(unsigned long) - 1 */
58 #error event_bits[] is too short!
59 #endif
60
61 struct usb_hub_descriptor *descriptor; /* class descriptor */
62 struct usb_tt tt; /* Transaction Translator */
63
64 unsigned mA_per_port; /* current for each child */
65
66 unsigned limited_power:1;
67 unsigned quiescing:1;
68 unsigned activating:1;
69
70 unsigned has_indicators:1;
71 u8 indicator[USB_MAXCHILDREN];
72 struct delayed_work leds;
73 };
看到了吗,51行,struct list_head event_list,这个结构体变量将为我们组建一个队列,或者说组建一个链表.我们知道,一个struct usb_hub代表一个hub,每一个struct usb_hub有一个event_list,即每一个hub都有它自己的一个事件列表,要知道hub可以有一个或者有多个,而hub驱动只需要一个,或者说khubd这个精灵进程永远都只有一个,而我们的做法是,不管实际上有多少个hub,我们最终都会将其event_list挂入到全局链表hub_event_list中来统一处理(hub_event_list是对于整个usb系统来说是全局的,但对于整个内核来说当然是局部的,毕竟它前面有一个static).因为最终处理所有hub的事务的都是我们这一个精灵进程khubd,它只需要判断hub_event_list是否为空,不为空就去处理.或者说就去出发hub_events()函数,但当我们真的要处理hub的事件的时候,我们当然又要知道具体是哪个hub触发了这起事件.而list_entry的作用就是,从struct list_head event_list得到它所对应的struct usb_hub结构体变量.比如以下四行代码:
struct list_head *tmp;
struct usb_hub *hub;
tmp=hub_event_list.next;
hub=list_entry(tmp,struct usb_hub,event_list);
从全局链表hub_event_list中取出一个来,叫做tmp,然后通过tmp,获得它所对应的struct usb_hub.
最后,总结陈词,本方论点:中学我们学习写议论文的时候,老师教过有这样几种结构,总分总式结构,对照式结构,层进式结构,并列式结构.而总分总式就是先提出中心论点,然后围绕中心,以不同角度提出分论点,展开论述,最后进行总结.而总分总具体来说又有总分,分总,总分总三种形式.以前我以为Linus只是技术比我强,现在我算是看明白了,这家伙语文学得也比我好.看出来了么?这里采用的就是我们议论文中的总分总结构,先设置一个链表,hub_event_list,设置一个总的函数hub_events(),这是总,然后每一个hub都有一个event_list,每当有一个hub的event_list出现了变化,就把它的event_list插入到hub_event_list中来,这是分,然后触发总函数hub_events(),这又是总,然后在hub_events()里又根据event_list来确定是哪个struct usb_hub,或者说是哪个hub有事情,又针对该hub进行具体处理,这又是分.这就是Linux中hub驱动的中心思想.Linus,I服了U!从前我只佩服复旦大学中文系系主任陈思和,他早上8点的公选课学生7点去就没有了座位,堪称复旦的奇迹,而Linus你和你的那些伙伴们让我们知道了真正的文学泰斗是从来不写文学著作的!是从来不讲论语心得,从来不去品三国的!
最后的最后,提醒一下,struct usb_hub这里贴出来了,稍后讲到这个结构体的时候就不会再贴了.
