深入分析 Linux 内核链表

Linux内核：RCU机制与使⽤Linux 内核：RCU机制与使⽤背景学习Linux源码的时候，发现很多熟悉的数据结构多了__rcu后缀，因此了解了⼀下这些内容。

介绍RCU（Read-Copy Update）是数据同步的⼀种⽅式，在当前的Linux内核中发挥着重要的作⽤。

RCU主要针对的数据对象是链表，⽬的是提⾼遍历读取数据的效率，为了达到⽬的使⽤RCU机制读取数据的时候不对链表进⾏耗时的加锁操作。

这样在同⼀时间可以有多个线程同时读取该链表，并且允许⼀个线程对链表进⾏修改（修改的时候，需要加锁）。

RCU适⽤于需要频繁的读取数据，⽽相应修改数据并不多的情景，例如在⽂件系统中，经常需要查找定位⽬录，⽽对⽬录的修改相对来说并不多，这就是RCU发挥作⽤的最佳场景。

RCU(Read-Copy Update)，是 Linux 中⽐较重要的⼀种同步机制。

顾名思义就是“读，拷贝更新”，再直⽩点是“随意读，但更新数据的时候，需要先复制⼀份副本，在副本上完成修改，再⼀次性地替换旧数据”。

这是 Linux 内核实现的⼀种针对“读多写少”的共享数据的同步机制。

RCU机制解决了什么在RCU的实现过程中，我们主要解决以下问题：1、在读取过程中，另外⼀个线程删除了⼀个节点。

删除线程可以把这个节点从链表中移除，但它不能直接销毁这个节点，必须等到所有的读取线程读取完成以后，才进⾏销毁操作。

RCU中把这个过程称为宽限期（Grace period）。

2、在读取过程中，另外⼀个线程插⼊了⼀个新节点，⽽读线程读到了这个节点，那么需要保证读到的这个节点是完整的。

这⾥涉及到了发布-订阅机制（Publish-Subscribe Mechanism）。

3、保证读取链表的完整性。

新增或者删除⼀个节点，不⾄于导致遍历⼀个链表从中间断开。

但是RCU并不保证⼀定能读到新增的节点或者不读到要被删除的节点。

RCU(Read-Copy Update)，顾名思义就是读-拷贝修改，它是基于其原理命名的。

Linux 内核启动分析1. 内核启动地址1.1. 名词解释ZTEXTADDR解压代码运行的开始地址。

没有物理地址和虚拟地址之分，因为此时MMU处于关闭状态。

这个地址不一定时RAM的地址，可以是支持读写寻址的flash等存储中介。

Start address of decompressor. here's no point in talking about virtual or physical addresses here, since the MMU will be off at the time when you call the decompressor code. Y ou normally call the kernel at this address to start it booting. This doesn't have to be located in RAM, it can be in flash or other read-only or read-write addressable medium.ZRELADDR内核启动在RAM中的地址。

压缩的内核映像被解压到这个地址，然后执行。

This is the address where the decompressed kernel will be written, and eventually executed. The following constraint must be valid:__virt_to_phys(TEXTADDR) == ZRELADDRThe initial part of the kernel is carefully coded to be position independent.TEXTADDR内核启动的虚拟地址，与ZRELADDR相对应。

一般内核启动的虚拟地址为RAM的第一个bank地址加上0x8000。

linux内核源码分析-nvme设备的初始化本⽂基于3.18.3内核的分析,nvme设备为pcie接⼝的ssd,其驱动名称为nvme.ko,驱动代码在drivers/block/nvme-core.c.驱动的加载 驱动加载实际就是module的加载,⽽module加载时会对整个module进⾏初始化,nvme驱动的module初始化函数为nvme_init(),如下:static struct pci_driver nvme_driver = {.name = "nvme",.id_table = nvme_id_table,.probe = nvme_probe,.remove = nvme_remove,.shutdown = nvme_shutdown,.driver = {.pm = &nvme_dev_pm_ops,},.err_handler = &nvme_err_handler,};static int __init nvme_init(void){int result;/* 初始化等待队列nvme_kthread_wait,此等待队列⽤于创建nvme_kthread(只允许单进程创建nvme_kthread) */init_waitqueue_head(&nvme_kthread_wait);/* 创建⼀个workqueue叫nvme */nvme_workq = create_singlethread_workqueue("nvme");if (!nvme_workq)return -ENOMEM;/* 在内核中注册新的⼀类块设备驱动,名字叫nvme,注意这⾥只是注册,表⽰kernel⽀持了nvme类的块设备,返回⼀个major,之后所有的nvme设备的major都是此值 */result = register_blkdev(nvme_major, "nvme");if (result < 0)goto kill_workq;else if (result > 0)nvme_major = result;/* 注册⼀些通知信息 */nvme_nb.notifier_call = &nvme_cpu_notify;result = register_hotcpu_notifier(&nvme_nb);if (result)goto unregister_blkdev;/* 注册pci nvme驱动 */result = pci_register_driver(&nvme_driver);if (result)goto unregister_hotcpu;return0;unregister_hotcpu:unregister_hotcpu_notifier(&nvme_nb);unregister_blkdev:unregister_blkdev(nvme_major, "nvme");kill_workq:destroy_workqueue(nvme_workq);return result;} 这⾥⾯其实最重要的就是做了两件事,⼀件事是register_blkdev,注册nvme这类块设备,返回⼀个major,另⼀件事是注册了nvme_driver,注册了nvme_driver后,当有nvme设备插⼊后系统后,系统会⾃动调⽤nvme_driver->nvme_probe去初始化这个nvme设备.这时候可能会有疑问,系统是如何知道插⼊的设备是nvme设备的呢,注意看struct pci_driver nvme_driver这个结构体,⾥⾯有⼀个nvme_id_table,其内容如下:/* Move to pci_ids.h later */#define PCI_CLASS_STORAGE_EXPRESS 0x010802static const struct pci_device_id nvme_id_table[] = {{ PCI_DEVICE_CLASS(PCI_CLASS_STORAGE_EXPRESS, 0xffffff) },{ 0, }};再看看PCI_DEVICE_CLASS宏是如何定义的#define PCI_DEVICE_CLASS(dev_class,dev_class_mask) \.class = (dev_class), .class_mask = (dev_class_mask), \.vendor = PCI_ANY_ID, .device = PCI_ANY_ID, \.subvendor = PCI_ANY_ID, .subdevice = PCI_ANY_ID也就是当pci class为PCI_CLASS_STORAGE_EXPRESS时,就表⽰是nvme设备,并且这个是写在设备⾥的,当设备插⼊host时,pci driver(并不是nvme driver)回去读取这个值,然后判断它需要哪个驱动去做处理.nvme数据结构 现在假设nvme.ko已经加载完了(注册了nvme类块设备,并且注册了nvme driver),这时候如果有nvme盘插⼊pcie插槽,pci会⾃动识别到,并交给nvme driver去处理,⽽nvme driver就是调⽤nvme_probe去处理这个新加⼊的设备. 在说nvme_probe之前,先说⼀下nvme设备的数据结构,⾸先,内核使⽤⼀个nvme_dev结构体来描述⼀个nvme设备, ⼀个nvme设备对应⼀个nvme_dev,nvme_dev如下:/* nvme设备描述符,描述⼀个nvme设备 */struct nvme_dev {struct list_head node;/* 设备的queue,⼀个nvme设备⾄少有2个queue,⼀个admin queue,⼀个io queue,实际情况⼀般都是⼀个admin queue,多个io queue,并且io queue会与CPU做绑定 */ struct nvme_queue __rcu **queues;/* unsigned short的数组，每个CPU占⼀个,主要⽤于存放CPU上绑定的io queue的qid,⼀个CPU绑定⼀个queues,⼀个queues绑定到1到多个CPU上 */unsigned short __percpu *io_queue;/* ((void __iomem *)dev->bar) + 4096 */u32 __iomem *dbs;/* 此nvme设备对应的pci dev */struct pci_dev *pci_dev;/* dma池,主要是以4k为⼤⼩的dma块,⽤于dma分配 */struct dma_pool *prp_page_pool;/* 也是dma池,但是不是以4k为⼤⼩的,是⼩于4k时使⽤ */struct dma_pool *prp_small_pool;/* 实例的id,第⼀个加⼊的nvme dev,它的instance为0,第⼆个加⼊的nvme,instance为1,也⽤于做/dev/nvme%d的显⽰,%d实际就是instance的数值 */int instance;/* queue的数量, 等于admin queue + io queue */unsigned queue_count;/* 在线可以使⽤的queue数量,跟online cpu有关 */unsigned online_queues;/* 最⼤的queue id */unsigned max_qid;/* nvme queue⽀持的最⼤cmd数量，为((bar->cap) & 0xffff)或者1024的最⼩值 */int q_depth;/* 1 << (((bar->cap) >> 32) & 0xf)，应该是每个io queue占⽤的bar空间 */u32 db_stride;/* 初始化设置的值* dev->ctrl_config = NVME_CC_ENABLE | NVME_CC_CSS_NVM;* dev->ctrl_config |= (PAGE_SHIFT - 12) << NVME_CC_MPS_SHIFT;* dev->ctrl_config |= NVME_CC_ARB_RR | NVME_CC_SHN_NONE;* dev->ctrl_config |= NVME_CC_IOSQES | NVME_CC_IOCQES;*/u32 ctrl_config;/* msix中断所使⽤的entry,指针表⽰会使⽤多个msix中断,使⽤的中断的个数与io queue对等,多少个io queue就会申请多少个中断* 并且让每个io queue的中断尽量分到不同的CPU上运⾏*/struct msix_entry *entry;/* bar的映射地址，默认是映射8192，当io queue过多时，有可能会⼤于8192 */struct nvme_bar __iomem *bar;/* 其实就是块设备,⼀张nvme卡有可能会有多个块设备 */struct list_head namespaces;/* 对应的在/sys下的结构 */struct kref kref;/* 对应的字符设备,⽤于ioctl操作 */struct miscdevice miscdev;/* 2个work,暂时还不知道什么⽤ */work_func_t reset_workfn;struct work_struct reset_work;struct work_struct cpu_work;/* 这个nvme设备的名字,为nvme%d */char name[12];/* SN号 */char serial[20];char model[40];char firmware_rev[8];/* 这些值都是从nvme盘上获取 */u32 max_hw_sectors;u32 stripe_size;u16 oncs;u16 abort_limit;u8 vwc;u8 initialized;}; 在nvme_dev结构中,最最重要的数据就是nvme_queue,struct nvme_queue⽤来表⽰⼀个nvme的queue,每⼀个nvme_queue会申请⾃⼰的中断,也有⾃⼰的中断处理函数,也就是每个nvme_queue在驱动层⾯是完全独⽴的.nvme_queue有两种,⼀种是admin queue,⼀种是io queue,这两种queue都⽤struct nvme_queue来描述,⽽这两种queue的区别如下:admin queue: ⽤于发送控制命令的queue,所有⾮io命令都会通过此queue发送给nvme设备,⼀个nvme设备只有⼀个admin queue,在nvme_dev中,使⽤queues[0]来描述.io queue: ⽤于发送io命令的queue,所有io命令都是通过此queue发送给nvme设备,简单来说读/写操作都是通过io queue发送给nvme设备的,⼀个nvme设备有⼀个或多个io queue,每个io queue的中断会绑定到不同的⼀个或多个CPU上.在nvme_dev中,使⽤queues[1~N]来描述. 以上说的io命令和⾮io命令都是nvme命令,⽐如快层下发⼀个写request,nvme驱动就会根据此request构造出⼀个写命令,将这个写命令放⼊某个io queue中,当controller完成了这个写命令后,会通过此io queue的中断返回完成信息,驱动再将此完成信息返回给块层.明⽩了两种队列的作⽤,我们看看具体的数据结构struct nvme_queue/* nvme的命令队列，其中包括sq和cq。

深入分析request_irq的dev_id参数作用上一篇/ 下一篇 2010-07-21 22:06:44 / 个人分类：Linux移植查看( 358 ) / 评论( 0 ) / 评分( 0 / 0 )注：若对kernel中断处理模型不是很清楚的话(如:irqaction的作用)可以先参考一下这篇文档：/u2/60011/showart.php?id=1079281这里主要讲request_irq的参数dev_id的作用，内容会涉及到少许上面文档提到的内容。

Request_irq的作用是申请使用IRQ并注册中断处理程序。

request_irq（）函数的原型如下：我们知道，当使用内核共享中断时，request_irq必须要提供dev_id参数，并且dev_id的值必须唯一。

那么这里提供唯一的dev_id值的究竟是做什么用的？起先我以为dev_id的值是提供给kernel进行判断共享中断线上的哪一个设备产生了中断（即哪个irqaction 产生中断）,然后执行相应的中断处理函数(irqaction->handler)。

实际上不是的，我们来看看《Linux Kernel Development – Second Edition》第六章中Shared Handlers这一节,其中有段总结性的文字如下：When the kernel receives an interrupt, it invokes sequentially each registered handler on the line. Therefore, it is important that the handler be capable of distinguishing whether it generated a giveninterrupt. The handler must quickly exit if its associated device did not generate the interrupt. This requires the hardware device to have a status register (or similar mechanism) that the handler can check. Most hardware does indeed have such a feature.这段话的大概意思是，发生中断时，内核并不判断究竟是共享中断线上的哪个设备产生了中断，它会循环执行所有该中断线上注册的中断处理函数（即irqaction->handler函数）。

142/**143*klist_add_after-Init a klist_node and add it after an existing node 144*@n:node we're adding.145*@pos:node to put@n after146*//*在节点pos后面插入节点n*/147void klist_add_after(struct klist_node*n,struct klist_node*pos)148{149struct klist*k=knode_klist(pos);150151klist_node_init(k,n);152spin_lock(&k->k_lock);153list_add(&n->n_node,&pos->n_node);154spin_unlock(&k->k_lock);155}156EXPORT_SYMBOL_GPL(klist_add_after);157158/**159*klist_add_before-Init a klist_node and add it before an existing node 160*@n:node we're adding.161*@pos:node to put@n after162*//*在节点pos前面插入节点n*/163void klist_add_before(struct klist_node*n,struct klist_node*pos)164{165struct klist*k=knode_klist(pos);166167klist_node_init(k,n);168spin_lock(&k->k_lock);169list_add_tail(&n->n_node,&pos->n_node);170spin_unlock(&k->k_lock);171}172EXPORT_SYMBOL_GPL(klist_add_before);173/*等待者结构体，用于删除节点，删除完成唤醒进程*/174struct klist_waiter{175struct list_head list;176struct klist_node*node;177struct task_struct*process;178int woken;179};180/*定义并初始化klist节点移除自旋锁*/181static DEFINE_SPINLOCK(klist_remove_lock);/*定义一个等待器的链表*/182static LIST_HEAD(klist_remove_waiters);183184static void klist_release(struct kref*kref)185{186struct klist_waiter*waiter,*tmp;187struct klist_node*n=container_of(kref,struct klist_node,n_ref);188189WARN_ON(!knode_dead(n));/*删除链表中的节点入口*/190list_del(&n->n_node);191spin_lock(&klist_remove_lock);/*内核链表操作宏include/linux/list.h，遍历klist节点移除等待链表*/192list_for_each_entry_safe(waiter,tmp,&klist_remove_waiters,list){/*是要删除链表节点的等待器*/193if(waiter->node!=n)194continue;195/*等待者唤醒标志*/196waiter->woken=1;197mb();/*唤醒等待进程*/198wake_up_process(waiter->process);/*删除链表入口*/199list_del(&waiter->list);200}201spin_unlock(&klist_remove_lock);/*设置节点n指向的klist为空*/202knode_set_klist(n,NULL);203}204/*减引用次数并删除节点*/205static int klist_dec_and_del(struct klist_node*n)206{/*n->nref减引用次数，若引用次数减完不为0，调用klist_release清除节点对象，返回1；为0，则返回0*/207return kref_put(&n->n_ref,klist_release);208}209/*带锁操作的节点删除，不判断是否成功，减引用次数*/210static void klist_put(struct klist_node*n,bool kill)211{/*获取节点的put方法*/212struct klist*k=knode_klist(n);213void(*put)(struct klist_node*)=k->put;214215spin_lock(&k->k_lock);/*“需要杀死节点”==*/216if(kill)217knode_kill(n);/*节点对象引用次数为0了，则不需要调用put方法*/218if(!klist_dec_and_del(n))219put=NULL;220spin_unlock(&k->k_lock);/*调用put方法*/221if(put)222put(n);223}224225/**226*klist_del-Decrement the reference count of node and try to remove. 227*@n:node we're deleting.228*//*删除节点“杀死死节点*/229void klist_del(struct klist_node*n)230{231klist_put(n,true);232}233EXPORT_SYMBOL_GPL(klist_del);234235/**236*klist_remove-Decrement the refcount of node and wait for it to go away. 237*@n:node we're removing.238*/239void klist_remove(struct klist_node*n)240{/*定义一个等待者，并加入等待者加入移除等待者链表*/241struct klist_waiter waiter;242243waiter.node=n;244waiter.process=current;245waiter.woken=0;246spin_lock(&klist_remove_lock);247list_add(&waiter.list,&klist_remove_waiters);248spin_unlock(&klist_remove_lock);249/*清除节点，并设置等待者*/330*First grab list lock.Decrement the reference count of the previous 331*node,if there was one.Grab the next node,increment its reference 332*count,drop the lock,and return that next node.333*//*“预下”链表中下一节点*/334struct klist_node*klist_next(struct klist_iter*i)335{336void(*put)(struct klist_node*)=i->i_klist->put;337struct klist_node*last=i->i_cur;338struct klist_node*next;339/*抢占锁*/340spin_lock(&i->i_klist->k_lock);341/*获取下一节点*/342if(last){343next=to_klist_node(last->n_node.next);/*减上一节点引用次数*/344if(!klist_dec_and_del(last))345put=NULL;346}else347next=to_klist_node(i->i_klist->k_list.next);348349i->i_cur=NULL;/*链表中有节点“没死”，增加引用次数*/350while(next!=to_klist_node(&i->i_klist->k_list)){351if(likely(!knode_dead(next))){352kref_get(&next->n_ref);353i->i_cur=next;354break;355}356next=to_klist_node(next->n_node.next);357}358/*丢弃锁*/359spin_unlock(&i->i_klist->k_lock);360361if(put&&last)362put(last);363return i->i_cur;364}365EXPORT_SYMBOL_GPL(klist_next);366----------------------/*使用迭代查找下一链表节点*/1124struct klist_node*n=klist_next(i);1125struct device*dev=NULL;1126struct device_private*p;11271128if(n){/*根据节点入口获取该节点上的设备*/1129p=to_device_private_parent(n);1130dev=p->device;1131}1132return dev;1133}/*-------------------------------------------------------------------------------*//*其中device_private是设备私有数据结构，一下代码不难看出*想要由链表节点迭代查找设备非常容易*/66/**67*struct device_private-structure to hold the private to the driver core portions of the device structure.68*69*@klist_children-klist containing all children of this device70*@knode_parent-node in sibling list71*@knode_driver-node in driver list72*@knode_bus-node in bus list73*@driver_data-private pointer for driver specific info.Will turn into a74*list soon.75*@device-pointer back to the struct class that this structure is76*associated with.77*78*Nothing outside of the driver core should ever touch these fields.79*/80struct device_private{81struct klist klist_children;82struct klist_node knode_parent;83struct klist_node knode_driver;84struct klist_node knode_bus;85void*driver_data;86struct device*device;87};88#define to_device_private_parent(obj)\89container_of(obj,struct device_private,knode_parent)90#define to_device_private_driver(obj)\91container_of(obj,struct device_private,knode_driver)92#define to_device_private_bus(obj)\93container_of(obj,struct device_private,knode_bus) 94driver_attach()函数driver_attach()函数2009-04-2114:39:03|分类：linux kernel|字号订阅最近在看一个mpc8315CPU上的驱动程序发现在使用spi_register注册完成后没有调用到相应的probe函数，分析后发现在driver_attach()函数执行时没有找到匹配的device，在网上狗狗后找到关于这部分的分析，引用如下：个浅析linux2.6.23驱动自动匹配设备driver_attach()函数文章来源:int driver_attach(struct device_driver*drv){return bus_for_each_dev(drv->bus,NULL,drv,__driver_attach);}调用该函数,那么drv驱动程式会和drv所在总线上连接了的物理设备进行一一匹配,再来看看下面:int bus_for_each_dev(struct bus_type*bus,struct device*start,void*data,int(*fn)(struct device*,void*)){struct klist_iter i;//专门用于遍历的链表结构体,其中i_cur是遍历移动的关键struct device*dev;int error=0;if(!bus)return-EINVAL;klist_iter_init_node(&bus->klist_devices,&i,(start?&start->knode_bus:NULL));//i->i_klist=&bus->klist_devices;//i->i_head=&bus->klist_devices.k_list;//i->i_cur=NULL;//表示从最前端开始遍历挂接到bus总线上的整个设备链条.while((dev=next_device(&i))&&!error)//dev为该bus总线链表上的一个设备,[就像一根藤条上的一朵小花gliethttp_20071025] //这些device设备把自己的&device->knode_bus链表单元链接到了bus->klist_devices 上//这也说明名字为knode_bus的list单元将是要被挂接到bus->klist_devices的链表上//同理&device->knode_driver将是这个device设备链接到drivers驱动上的list节点识别单元//见driver_bound()->klist_add_tail(&dev->knode_driver,&dev->driver->klist_devices);error=fn(dev,data);//调用__driver_attach函数,进行匹配运算klist_iter_exit(&i);return error;//成功匹配返回0}struct klist_iter{struct klist*i_klist;struct list_head*i_head;struct klist_node*i_cur;};void klist_iter_init_node(struct klist*k,struct klist_iter*i,struct klist_node*n){i->i_klist=k;//需要被遍历的klisti->i_head=&k->k_list;//开始的链表头i->i_cur=n;//当前位置对应的klist_node节点,next_device()会从当前n 开始一直搜索到//链表的结尾,也就是i_head->prev处停止if(n)kref_get(&n->n_ref);//引用计数加1}static struct device*next_device(struct klist_iter*i){struct klist_node*n=klist_next(i);return n?container_of(n,struct device,knode_bus):NULL;//因为n是device->knode_bus的指针,所以container_of将返回device的指针}struct klist_node*klist_next(struct klist_iter*i){struct list_head*next;struct klist_node*lnode=i->i_cur;struct klist_node*knode=NULL;//赋0,当next==i->i_head时用于退出void(*put)(struct klist_node*)=i->i_klist->put;spin_lock(&i->i_klist->k_lock);if(lnode){next=lnode->n_node.next;if(!klist_dec_and_del(lnode))//释放前一个i_cur对象的引用计数put=NULL;//klist_dec_and_del成功的对引用计数做了减1操作,那么失效用户定义put}elsenext=i->i_head->next;//如果lnode=0,那么从链表头开始,所以head->next指向第1个实际对象if(next!=i->i_head){//head并不链接设备,所以head无效//当next==i->i_head时,说明已遍历到了head牵头的链表的末尾,回环到了head, //所以knode将不会进行赋值,这时knode=0,while((dev=next_device(&i))&&!error)因为0而退出knode=to_klist_node(next);//调用container_of()获取klist_node->n_node中klist_node地址kref_get(&knode->n_ref);//对该node的引用计数加1}i->i_cur=knode;//记住当前遍历到的对象,当next==i->i_head时,knode=0spin_unlock(&i->i_klist->k_lock);if(put&&lnode)put(lnode);return knode;}static int klist_dec_and_del(struct klist_node*n){return kref_put(&n->n_ref,klist_release);//对该node的引用计数减1,如果引用计数到达0,那么调用klist_release}static void klist_release(struct kref*kref){struct klist_node*n=container_of(kref,struct klist_node,n_ref);list_del(&n->n_node);//从节点链表上摘掉该node节点complete(&n->n_removed);//n->n_klist=NULL;}void fastcall complete(struct completion*x){unsigned long flags;spin_lock_irqsave(&x->wait.lock,flags);//关闭中断,防止并发x->done++;//唤醒因为某些原因悬停在klist_node->n_removed等待队列上的task们//这种现象之一是:__device_release_driver()删除挂接在设备上的driver时,会出现//删除task小憩在node的wait上__wake_up_common(&x->wait,TASK_UNINTERRUPTIBLE|TASK_INTERRUPTIBLE,1,0,NULL);spin_unlock_irqrestore(&x->wait.lock,flags);//恢复中断}static void__wake_up_common(wait_queue_head_t*q,unsigned int mode,int nr_exclusive,int sync,void*key){struct list_head*tmp,*next;list_for_each_safe(tmp,next,&q->task_list){//遍历以head牵头的链表上的task们wait_queue_t*curr=list_entry(tmp,wait_queue_t,task_list);unsigned flags=curr->flags;if(curr->func(curr,mode,sync,key)&&//调用wait上准备好了的回调函数func (flags&WQ_FLAG_EXCLUSIVE)&&!--nr_exclusive)break;}}//抛开链表上的head,当最后一个post==head时,说明链表已遍历结束(gliethttp_20071025) #define list_for_each_safe(pos,n,head)＼for(pos=(head)->next,n=pos->next;pos!=(head);＼pos=n,n=pos->next)void klist_iter_exit(struct klist_iter*i){if(i->i_cur){//对于正常遍历的退出,i->i_cur会等于0,如果找到了匹配对象,提前退出了,那么就会在这里对引用进行释放klist_del(i->i_cur);i->i_cur=NULL;}}static int__driver_attach(struct device*dev,void*data){struct device_driver*drv=data;//data就是打算把自己匹配到bus上挂接的合适设备上的driver驱动if(dev->parent)down(&dev->parent->sem);//使用信号量保护下面的操作down(&dev->sem);if(!dev->driver)//如果当前这个dev设备还没有挂接一个driver驱动driver_probe_device(drv,dev);//那么尝试该dev是否适合被该drv驱动管理up(&dev->sem);if(dev->parent)up(&dev->parent->sem);return0;}int driver_probe_device(struct device_driver*drv,struct device*dev){int ret=0;if(!device_is_registered(dev))//设备是否已被bus总线认可return-ENODEV;if(drv->bus->match&&!drv->bus->match(dev,drv))//调用该driver驱动自定义的match函数,如:usb_device_match(),查看//这个设备是否符合自己,drv->bus->match()返回1,表示本drv认可该设备//否则,goto done,继续检测下一个device设备是否和本drv匹配goto done;pr_debug("%s:Matched Device%s with Driver%s＼n",drv->bus->name,dev->bus_id,drv->name);//这下来真的了,ret=really_probe(dev,drv);done:return ret;}static inline int device_is_registered(struct device*dev){return dev->is_registered;//当调用bus_attach_device()之后,is_registered=1}static int really_probe(struct device*dev,struct device_driver*drv){int ret=0;atomic_inc(&probe_count);pr_debug("%s:Probing driver%s with device%s＼n",drv->bus->name,drv->name,dev->bus_id);WARN_ON(!list_empty(&dev->devres_head));dev->driver=drv;//管理本dev的驱动指针指向drvif(driver_sysfs_add(dev)){//将driver和dev使用link,链接到一起,使他们真正相关printk(KERN_ERR"%s:driver_sysfs_add(%s)failed＼n",__FUNCTION__,dev->bus_id);goto probe_failed;}if(dev->bus->probe){//总线提供了设备探测函数ret=dev->bus->probe(dev);if(ret)goto probe_failed;}else if(drv->probe){//驱动自己提供了设备探测函数//因为drv驱动自己也不想管理那些意外的非法设备//所以一般drv都会提供这个功能,相反//比如:usb_bus_type没有提供probe,而usb驱动提供了usb_probe_interface//来确认我这个driver软件真的能够管理这个device设备ret=drv->probe(dev);if(ret)goto probe_failed;}driver_bound(dev);ret=1;pr_debug("%s:Bound Device%s to Driver%s＼n",drv->bus->name,dev->bus_id,drv->name);goto done;probe_failed:devres_release_all(dev);driver_sysfs_remove(dev);dev->driver=NULL;if(ret!=-ENODEV&&ret!=-ENXIO){printk(KERN_WARNING"%s:probe of%s failed with error%d＼n",drv->name,dev->bus_id,ret);}ret=0;done:atomic_dec(&probe_count);wake_up(&probe_waitqueue);return ret;}static void driver_bound(struct device*dev){if(klist_node_attached(&dev->knode_driver)){//本dev已挂到了某个driver驱动的klist_devices链条上了//感觉不应该发生printk(KERN_WARNING"%s:device%s already bound＼n",__FUNCTION__,kobject_name(&dev->kobj));return;}pr_debug("bound device’%s’to driver’%s’＼n",dev->bus_id,dev->driver->name);if(dev->bus)blocking_notifier_call_chain(&dev->bus->bus_notifier,BUS_NOTIFY_BOUND_DRIVER,dev);//将本dev的knode_driver链表结构体节点挂接到该driver->klist_devices上//这样driver所管理的device设备又多了1个,//也能说又多了1个device设备使用本driver驱动管理他自己(gilethttp_20071025).klist_add_tail(&dev->knode_driver,&dev->driver->klist_devices);}Linux内核中的klist分析分析的内核版本照样是2.6.38.5。

深⼊解读Linux进程调度Schedule【转】调度系统是现代操作系统⾮常核⼼的基础⼦系统之⼀，尤其在多任务并⾏操作系统（Multitasking OS）上，系统可能运⾏于单核或者多核CPU上，进程可能处于运⾏状态或者在内存中可运⾏等待状态。

如何实现多任务同时使⽤资源并且提供给⽤户及时的响应实现实时交互以及提供⾼流量并发等对现代操作系统的设计实现带来了巨⼤挑战，⽽Linux调度⼦系统的设计同样需要实现这些看似⽭盾的要求，适应不同的使⽤场景。

我们看到Linux是⼀个复杂的现在操作系统，各个⼦系统之间相互合作才能完成⾼效的任务。

本⽂从围绕调度⼦系统，介绍了调度⼦系统核⼼的概念，并且将其与Linux各个相关组件的关系进⾏探讨，尤其是与调度⼦系统息息相关的中断（softirq和irq）⼦系统以及定时器Timer，深⼊⽽全⾯地展⽰了调度相关的各个概念以及相互联系。

由于笔者最近在调试PowerPC相关的芯⽚，因此相关的介绍会以此为例提取相关的内核源代码进⾏解读展⽰。

涉及的代码为Linux-4.4稳定发布版本，读者可以查看源码进⾏对照。

1. 相关概念要理解调度⼦系统，⾸先需要总体介绍调度的流程，对系统有⼀个⾼屋建瓴的认识之后，再在整体流程中对各个节点分别深⼊分析，从⽽掌握丰富⽽饱满的细节。

在系统启动早期，会注册硬件中断，时钟中断是硬件中断中⾮常重要的⼀种，调度过程中需要不断地刷新进程的状态以及设置调度标志已决定是否抢占进程的执⾏进⾏调度。

时钟中断就是周期性地完成此项⼯作。

这⾥⼜引出另外⼀个现代OS的调度设计思想即抢占（preempt），⽽与其对应的概念则为⾮抢占或者合作（cooperate），后⾯会给出两者的详细区别。

时钟中断属于硬件中断，Linux系统不⽀持中断嵌套，所以在中断发⽣时⼜会禁⽌本地中断（local_irq_disable），⽽为了尽快相应其他可能的硬件事件，必须要尽快完成处理并开启中断，因此引出了中断下半部，也就是softirq的概念。

Linux内存管理分析与研究随着计算机技术的不断发展，操作系统在计算机系统中扮演着越来越重要的角色。

作为开源操作系统领域的佼佼者，Linux被广泛用于各种应用场景，包括服务器、桌面、嵌入式系统等。

内存管理是操作系统核心功能之一，对于系统性能和稳定性具有重要影响。

本文将对Linux内存管理进行深入分析，并探讨其存在的问题与解决方案。

Linux内存管理采用分页和分段技术，将物理内存划分为大小不同的页框或段框，以便更有效地利用和管理内存资源。

Linux通过将内存分为内核空间和用户空间，实现了内存的隔离和保护，同时允许用户进程使用不同的内存空间。

Linux内存管理存在的一个主要问题是内存分配不均。

由于内存分配是基于页框或段框的，当某些进程需要更多内存时，操作系统会从空闲的内存页框中分配内存。

然而，在实际情况中，由于页框大小固定，当需要分配大量内存时，可能会造成内存分配不均的情况。

另一个问题是浪费空间。

Linux为了提高内存利用率，采用了一种称为内存分页的技术。

然而，在某些情况下，当进程不再需要使用内存时，操作系统并不会立即将内存页框回收，而是保留在内存中以备将来使用，这可能会导致内存空间的浪费。

针对内存分配不均的问题，可以采取交换技术。

交换技术是一种将进程使用的内存部分移至磁盘上，以腾出更多内存供其他进程使用的方法。

在Linux中，可以使用瑞士文件系统（Swiss File System，SFS）作为交换设备，将不常用的内存页框交换到磁盘上，以便在需要时重新加载。

为了解决内存浪费问题，可以优化内存分配算法。

Linux中使用的内存分配算法是基于伙伴系统的，该算法会跟踪每个内存块的空闲状态。

当需要分配内存时，伙伴系统会选择一个适当大小的空闲块，并将其划分为所需的内存大小。

为了避免内存浪费，可以采取以下措施：增加空闲内存块的大小，以便更好地适应大内存需求；引入动态内存分配机制，使操作系统能够在需要时分配和回收内存；定期清理不再使用的内存块，以便及时回收内存空间。

需要了解Linux内核通知链机制的原理及实现一、概念：大多数内核子系统都是相互独立的，因此某个子系统可能对其它子系统产生的事件感兴趣。

为了满足这个需求，也即是让某个子系统在发生某个事件时通知其它的子系统，Linux 内核提供了通知链的机制。

通知链表只能够在内核的子系统之间使用，而不能够在内核与用户空间之间进行事件的通知。

通知链表是一个函数链表，链表上的每一个节点都注册了一个函数。

当某个事情发生时，链表上所有节点对应的函数就会被执行。

所以对于通知链表来说有一个通知方与一个接收方。

在通知这个事件时所运行的函数由被通知方决定，实际上也即是被通知方注册了某个函数，在发生某个事件时这些函数就得到执行。

其实和系统调用signal的思想差不多。

二、数据结构：通知链有四种类型：原子通知链（ Atomic notifier chains ）：通知链元素的回调函数（当事件发生时要执行的函数）只能在中断上下文中运行，不允许阻塞。

对应的链表头结构：struct atomic_noTIfier_head{ spinlock_t lock; struct noTIfier_block *head;};可阻塞通知链（ Blocking noTIfier chains ）：通知链元素的回调函数在进程上下文中运行，允许阻塞。

对应的链表头：struct blocking_noTIfier_head{ struct rw_semaphore rwsem; struct notifier_block *head;}; 原始通知链（ Raw notifier chains ）：对通知链元素的回调函数没有任何限制，所有锁和保护机制都由调用者维护。

对应的链表头：struct raw_notifier_head{ struct notifier_block *head;};SRCU 通知链（ SRCU notifier chains ）：可阻塞通知链的一种变体。

其中基于sparc64平台的Linux用户空间可以运行32位代码，用户空间指针是32位宽的，但内核空间是64位的。

内核中的地址是unsigned long类型，指针大小和long类型相同。

内核提供下列数据类型。

所有类型在头文件<asm/types.h>中声明，这个文件又被头文件<Linux/types.h>所包含。

下面是include/asm/types.h文件。

#ifndef _I386_TYPES_H#define _I386_TYPES_H#ifndef __ASSEMBLY__typedef unsigned short umode_t;// 下面__xx类型不会损害POSIX 名字空间，在头文件使用它们，可以输出给用户空间typedef __signed__ char __s8;typedef unsigned char __u8;typedef __signed__ short __s16;typedef unsigned short __u16;typedef __signed__ int __s32;typedef unsigned int __u32;#if defined(__GNUC__) && !defined(__STRICT_ANSI__)typedef __signed__ long long __s64;typedef unsigned long long __u64;#endif#endif /* __ASSEMBLY__ *///下面的类型只用在内核中，否则会产生名字空间崩溃#ifdef __KERNEL__#define BITS_PER_LONG 32#ifndef __ASSEMBLY__#include <Linux/config.h>typedef signed char s8;typedef unsigned char u8;typedef signed short s16;typedef unsigned short u16;typedef signed int s32;typedef unsigned int u32;typedef signed long long s64;typedef unsigned long long u64;/* DMA addresses come in generic and 64-bit flavours. */ #ifdef CONFIG_HIGHMEM64Gtypedef u64 dma_addr_t;#elsetypedef u32 dma_addr_t;#endiftypedef u64 dma64_addr_t;#ifdef CONFIG_LBDtypedef u64 sector_t;#define HAVE_SECTOR_T#endiftypedef unsigned short kmem_bufctl_t;#endif /* __ASSEMBLY__ */#endif /* __KERNEL__ */#endif下面是Linux/types.h的部分定义。