Linux-0.11 kernel目录ll_rw_blk.c详解

该模块的作用是处理块设备的读写，其中最重要的函数就是电梯算法add_request函数和ll_rw_block函数。

add_request

static void add_request(struct blk_dev_struct * dev, struct request * req)

该函数的作用是将块设备读写请求插入到电梯队列中。

首先将数据的脏数据标志置为0。

if (req->bh)req->bh->b_dirt = 0;

如果当前设备的请求为空，就将入参中的请求作为设备电梯队列的头节点。并且立即调用request_fn。request_fn对于不同的设备对应不同的回调函数，对于硬盘设备而言，request_fn指的是do_hd_request，关于do_hd_request,将在hd.c中进行讲解。

if (!(tmp = dev->current_request)) {dev->current_request = req;sti();(dev->request_fn)();return;
}

上面的部分处理了请求队列只有一个请求的场景，接下来便是当请求队列有多个请求时，如何处理优先级顺序的逻辑，也就是电梯算法部分，其中最难理解的便是宏定义IN_ORDER。IN_ORDER的定义如下所示。

#define IN_ORDER(s1,s2) \
((s1)->cmd<(s2)->cmd || ((s1)->cmd==(s2)->cmd && \
((s1)->dev < (s2)->dev || ((s1)->dev == (s2)->dev && \
(s1)->sector < (s2)->sector))))

上述代码是比较难懂的，可以使用if-else来帮助理解

bool inorder(request &s1, request &s2)
{if(s1.cmd < s2.cmd>){return true;}else if(s1.cmd == s2.cmd){if(s1.dev < s2.dev){return true;}else if(s1.dev == s2.dev){if(s1.sector < s2.sector){return true;}return false;//s1.sector > s2.sector}return false;//s1.dev > s2.dev}return false;//s1.cmd > s2.cmd
}

展开上面的if-else结构逻辑就清晰了很多，IN_ORDER实际上就是依次对操作类型，设备号， 扇区号作比较，并且操作类型优先级大于设备号，设备号优先级大于扇区号。

对于操作类型而言，读操作优先级大于写操作。对于设备号而言，设备号小的设备优先级大于设备号大的设备的优先级。对于扇区而言，扇区序号小的扇区优先级高于扇区序号大的扇区。

有了这个认识之后，再看下面的语句，就会简单很多，实际上就是根据优先级找到合适的位置插入数据。

for ( ; tmp->next ; tmp=tmp->next)if ((IN_ORDER(tmp,req) || !IN_ORDER(tmp,tmp->next)) &&IN_ORDER(req,tmp->next))break;
req->next=tmp->next;
tmp->next=req;

下面的这一段代码可以用两个if语句进行替代，即定向扫描和折返扫描两个场景。

if ((IN_ORDER(tmp,req) || !IN_ORDER(tmp,tmp->next)) &&IN_ORDER(req,tmp->next))

条件1：定向扫描， req在当前扫描的方向上

if(tmp > req && req > tmp->next)
{req->next=tmp->next;tmp->next=req;	
}

条件2: 折返扫描，req在下一轮扫描的方向上

if(tmp < tmp->next && req > tmp->next)
{req->next=tmp->next;tmp->next=req;	
}

这里需要阐明的是，Linux-0.11实际使用的磁盘扫描算法是C-SCAN算法，也是电梯算法（可戏称为跳楼机）。

其思路就是只单向寻道，到头后直接复位再次沿同方向寻道，这样对于所有磁盘位置的请求都是公平的。

我们通过下面的代码实际感受一下这个过程，我们固定cmd和dev， 只让sector号有区别，依次插入50， 80， 60， 30， 20 ，看看最后的结果如何。

#include 
#include #define READ 0
#define WRITE 1struct request {int dev;		/* -1 if no request */int cmd;		/* READ or WRITE */int errors;unsigned long sector;unsigned long nr_sectors;char * buffer;//struct task_struct * waiting;//struct buffer_head * bh;struct request * next;
};#define IN_ORDER(s1,s2) \((s1)->cmd<(s2)->cmd || (s1)->cmd==(s2)->cmd && \((s1)->dev < (s2)->dev || ((s1)->dev == (s2)->dev && \(s1)->sector < (s2)->sector)))// 作为解析，以明白的分支结构重写一个内容一样的inorder函数
bool inorder(struct request *s1,struct request *s2)
{if (s1->cmdcmd){return true;//only when s1->cmd = READ; s2->cmd = WRITE;}else if ( s1->cmd == s2->cmd ){if (s1->dev < s2->dev){return true;// when (s1->cmd==s2->cmd) && (s1->devdev)}else if ( s1->dev == s2->dev ){if (s1->sectorsector){return true;// when when (s1->cmd==s2->cmd) && (s1->sectorsector)}return false;// when when (s1->cmd==s2->cmd) && (s1->sector>=s1->sector)}return false;// when (s1->cmd==s2->cmd) && (s1->dev>s2->dev)}return false;// when s1->cmd>s2->cmd
}void AddRequest(struct request * &head,struct request *req)
{if (!head){head = req;head->next = 0;return ;}struct request * tmp = head;for (;tmp->next;tmp = tmp->next){if ( ( IN_ORDER(tmp,req)||!IN_ORDER(tmp,tmp->next)) &&IN_ORDER(req,tmp->next)){break;}}req->next = tmp->next;tmp->next = req;return;
}void PrintQueen(struct request * n)
{while (n){printf("(%d,%d,%d),",n->cmd,n->dev,n->sector);n = n->next;}printf("\n");
}
int main(int argc,char ** argv)
{struct request s1;struct request * pHead = 0;struct request *req = new struct request;req->cmd = 0;req->dev =  0;req->sector =  50;AddRequest(pHead,req);PrintQueen(pHead);   struct request *req3 = new struct request;req3->cmd = 0;req3->dev =  0;req3->sector =  80;AddRequest(pHead,req3);PrintQueen(pHead);  struct request *req2 = new struct request;req2->cmd = 0;req2->dev =  0;req2->sector =  60;AddRequest(pHead,req2);PrintQueen(pHead);  struct request *req5 = new struct request;req5->cmd = 0;req5->dev =  0;req5->sector =  30;AddRequest(pHead,req5);PrintQueen(pHead);  struct request *req4 = new struct request;req4->cmd = 0;req4->dev =  0;req4->sector =  20;AddRequest(pHead,req4);PrintQueen(pHead);  return 0;
}

上述代码的执行结果如下所示:

(0,0,50),
(0,0,50),(0,0,80),
(0,0,50),(0,0,60),(0,0,80),
(0,0,50),(0,0,60),(0,0,80),(0,0,30),
(0,0,50),(0,0,60),(0,0,80),(0,0,20),(0,0,30),

可以看出最后的顺序是50->60->80->20->30， 实际上效果就是单方向移动到最后一个位置，再复位进行扫描，再次沿同方向扫描。

make_request

static void make_request(int major,int rw, struct buffer_head * bh)

该函数的作用是创建请求项并插入请求队列中。

首先判断命令是否READA或者是WRITEA。READA代表预读取，WRITEA代表预写入。所以当命令是预读取或者是预写入，如果bh块被锁，那么就放弃，直接返回。如果bh块没有被锁，那么就当作普通的READ和WRITE。

	struct request * req;int rw_ahead;/* WRITEA/READA is special case - it is not really needed, so if the */
/* buffer is locked, we just forget about it, else it's a normal read */if ((rw_ahead = (rw == READA || rw == WRITEA))) {if (bh->b_lock)return;if (rw == READA)rw = READ;elserw = WRITE;}

如果命令不是读或者写，那么就是一个致命错误，直接通过panic抛出错误。对命令校验之后，就去锁定该数据块。如果命令是写操作，但是该数据块并没有脏数据，则没有必要去写块设备，就可以对bh块进行解锁。除此以外，如果命令是读操作，但是该bh块中的内容已经是最新的，也没有必要去读块设备，就可以对bh块进行解锁。

if (rw!=READ && rw!=WRITE)panic("Bad block dev command, must be R/W/RA/WA");
lock_buffer(bh);
if ((rw == WRITE && !bh->b_dirt) || (rw == READ && bh->b_uptodate)) {unlock_buffer(bh);return;
}

下面需要从request数组中寻找一个位置来创建该请求。对于读请求而言，将会从数组的尾部开始搜索。对于写请求而言，将会从数组的2/3处开始搜索。 如果找到了位置，那么就开始进行创建，如果没有找到位置，就sleep_on进行等待。

	if (rw == READ)req = request+NR_REQUEST;elsereq = request+((NR_REQUEST*2)/3);
/* find an empty request */while (--req >= request)if (req->dev<0)break;
/* if none found, sleep on new requests: check for rw_ahead */if (req < request) {if (rw_ahead) {unlock_buffer(bh);return;}sleep_on(&wait_for_request);goto repeat;}

当找到该位置时，就在该位置上进行构建请求。构建完之后，调用add_request插入到电梯队列中。

/* fill up the request-info, and add it to the queue */req->dev = bh->b_dev;req->cmd = rw;req->errors=0;req->sector = bh->b_blocknr<<1;req->nr_sectors = 2;req->buffer = bh->b_data;req->waiting = NULL;req->bh = bh;req->next = NULL;add_request(major+blk_dev,req);

ll_rw_block

void ll_rw_block(int rw, struct buffer_head * bh)

该函数的作用就是读写数据块。

下面一段代码用于对bh块对应的设备做相应的校验。如果主设备号不存在，或者该设备对应的请求操作函数不存在，就显示出错信息。

if ((major=MAJOR(bh->b_dev)) >= NR_BLK_DEV ||
!(blk_dev[major].request_fn)) {printk("Trying to read nonexistent block-device\n\r");return;
}

如果校验没有问题就调用make_request建立块设备读写请求。

make_request(major,rw,bh);

blk_dev_init

void blk_dev_init(void)

该函数的作用是初始化块设备。

遍历request数组，对request数组中每一项的dev设置为-1， 对next指针设置为NULL。

for (i=0 ; irequest[i].dev = -1;request[i].next = NULL;
}

lock_buffer

static inline void lock_buffer(struct buffer_head * bh)

该函数的作用是锁定指定的缓冲块。

cli();//关中断
while (bh->b_lock)//如果缓冲区已被锁定就睡眠，一直到缓冲区解锁sleep_on(&bh->b_wait);
bh->b_lock=1;//立即锁定缓冲区
sti();//开中断

unlock_buffer

static inline void unlock_buffer(struct buffer_head * bh)

该函数的作用是解锁指定的缓冲块。

if (!bh->b_lock)//如果该缓冲区没有加锁，则打印出错信息printk("ll_rw_block.c: buffer not locked\n\r");
bh->b_lock = 0;//对缓冲区解锁
wake_up(&bh->b_wait);//唤醒等待该缓冲区的任务。