公告
页次： 1
#1 2022-10-08 12:21:09
linux源码解读（二）：文件系统——高速缓存区
用户的应用程序会经常读写磁盘文件的数据到内存，但是内存的速度和磁盘的速度理论上差了好几个数量级；为了更高效地解决内存和磁盘的速度差，linux也在内存使用了缓存区（作用类似于cpu内部为了解决寄存器和内存速度差异的的L1、L2、L3 cache）：如果数据要写入磁盘文件，先放在缓存区，等凑够了一定数量后再批量写入磁盘文件，借此减少磁盘寻址的次数，来提升写入效率（这里多说几句：比如U盘插上电脑后，如果要拔出，建议先卸载再拔出，而不是直接拔出，为啥了？U盘的数据也是先放入缓冲区的，缓冲区有自己的管理机制，很久没有使用的块可以给其他进程使用，如果是脏块则要进行写盘。缓冲在某些情况下才会有写盘操作，所以要拔出U盘时，应该先进行卸载，这样才会写盘，否则数据可能丢失，文件系统可能损坏。）；如果从磁盘读数据，也会先放入缓存区暂存，一旦有其他进程或线程读取同样的磁盘文件，这是就可以先从内存的缓存区取数据了，没必要重新从磁盘读取，也提升了效率！linux 0.11的缓冲区是怎么工作的了？
在main.c的main函数中，有设置缓存区的大小，代码如下：内存不同，缓存区的大小也不同，linux是怎么管理和使用这些缓存区了的？
void main(void) /* This really IS void, no error here. */
{ /* The startup routine assumes (well, ...) this */
/*
* Interrupts are still disabled. Do necessary setups, then
* enable them
*/
//前面这里做的所有事情都是在对内存进行拷贝
ROOT_DEV = ORIG_ROOT_DEV;//设置操作系统的根文件
drive_info = DRIVE_INFO;//设置操作系统驱动参数
//解析setup.s代码后获取系统内存参数
memory_end = (1<<20) + (EXT_MEM_K<<10);
//取整4k的内存大小
memory_end &= 0xfffff000;
if (memory_end > 16*1024*1024)//控制操作系统的最大内存为16M
memory_end = 16*1024*1024;
if (memory_end > 12*1024*1024)
buffer_memory_end = 4*1024*1024;//设置高速缓冲区的大小，跟块设备有关，跟设备交互的时候，充当缓冲区，写入到块设备中的数据先放在缓冲区里，只有执行sync时才真正写入；这也是为什么要区分块设备驱动和字符设备驱动；块设备写入需要缓冲区，字符设备不需要是直接写入的
else if (memory_end > 6*1024*1024)
buffer_memory_end = 2*1024*1024;
else
buffer_memory_end = 1*1024*1024;
main_memory_start = buffer_memory_end;1、cpu有分页机制，硬件上以4KB为单位把内存分割成小块供程序使用；这个颗粒度是比较大的，有些时候可能会浪费比较多的内存，所以linux缓存区采用了1KB的大小来分割整个缓存区；假设缓存区有2MB，那么一共被分割成了2000个小块，这么多的缓存区该怎么管理了？
每个缓存都有各自的属性，比如是否使用、数据是否更新、缓存数据在磁盘的位置、缓存的起始地址等，要想统一管理这么多的属性，最好的办法自然是构建结构体了；一个结构体管理1块（也就是1KB）的缓存区；假设这里有2000个缓存区，就需要2000个结构体，那么问题又来了：这个多的结构体，又该怎么去管理了？
参考前面的进程task结构体管理方式：用task数组来管理所有的进程task结构体，最大限制为64个进程，但是放在这里显然不适用：不同机器的物理内存大小是不同的，导致缓存区的block数量是不同的，但数组最大的缺点就是定长，无法适应不同的物理内存，那么这里最适合的只剩链表了，所以linux 0.11版本使用的结构体如下：
struct buffer_head {
char * b_data; /* pointer to data block (1024 bytes):单个数据块大小1KB */
unsigned long b_blocknr; /* block number */
unsigned short b_dev; /* device (0 = free) */
unsigned char b_uptodate; /*数据是否更新*/
unsigned char b_dirt; /* 0-clean空现,1-dirty已被占用*/
unsigned char b_count; /* users using this block */
/*如果缓冲区的某个block被锁，上层应用是没法从这个block对应的磁盘空间读数据的，这里有个漏洞：
A进程锁定了某block，B进程想办法解锁，然后就能监听A进程从磁盘读写了哪些数据
*/
unsigned char b_lock; /* 0 - ok, 1 -locked:锁用于多进程/多线程之间同步，避免数据出错*/
struct task_struct * b_wait;/*A正在使用这个缓存，并已经锁定；B也想用，就用这个字段记录；等A用完后从这里找到B再给B用*/
struct buffer_head * b_prev;
struct buffer_head * b_next;
struct buffer_head * b_prev_free;
struct buffer_head * b_next_free;
};每个字段的含义都在注释了，这里不再赘述；既然采用了链表，解决了数组只能定长的缺点，但是链表本身也有缺点：无法直接找到目标实例，需要挨个遍历链表上的每个节点；还是假设有2000个块，好巧的不巧的是程序所需的block刚好在最后一个节点，那么需要遍历1999个节点才能到达，效率非常低，这又该怎么解决了？刚好这种快速寻址（时间复杂度O(1)）是数组的优势，怎么解决数组和链表各自的优势了？-----hash表！
linux 0.11版本采用hash表的方式快速寻址，hash映射算法如下：
// hash表的主要作用是减少查找比较元素所花费的时间。通过在元素的存储位置与关
// 键字之间建立一个对应关系(hash函数)，我们就可以直接通过函数计算立刻查询到指定
// 的元素。建立hash函数的指导条件主要是尽量确保散列在任何数组项的概率基本相等。
// 建立函数的方法有多种，这里Linux-0.11主要采用了关键字除留余数法。因为我们
// 寻找的缓冲块有两个条件，即设备号dev和缓冲块号block，因此设计的hash函数肯定
// 需要包含这两个关键值。这两个关键字的异或操作只是计算关键值的一种方法。再对
// 关键值进行MOD运算就可以保证函数所计算得到的值都处于函数数组项范围内。
#define _hashfn(dev,block) (((unsigned)(dev^block))%NR_HASH)
#define hash(dev,block) hash_table[_hashfn(dev,block)]映射的算法也很简单：每个buffer_head结构体都有dev和block两个字段，这两个字段组合起来本身是不会重复的，所以把这两个字段异或后模上hash表的长度，就得到了hash数组的偏移；现在问题又来了：这个版本的hash_table数组长度设定为NR_HASH=307，远不如buffer_head的实例个数，肯定会发生hash冲突，这个该怎么解决了？--这里就要用上链表变长的优点了：把发生hash冲突的bufer_head实例首位相接不久得了么？最终的hash_table示意图如下：hash表本身用数组，存储buffer_head实例的地址；如果发生hash冲突，相同hash偏移的实例通过b_next和b_prev链表首尾连接！
当这个一整套存储机制建立后，怎么检索了？linux的检索方式如下：先通过dev和block号定位到hash表的偏移，再遍历该偏移处的所有节点，通过比对dev和block号找到目标buffer_head实例！
//// 利用hash表在高速缓冲区中寻找给定设备和指定块号的缓冲区块。
// 如果找到则返回缓冲区块的指针，否则返回NULL。
static struct buffer_head * find_buffer(int dev, int block)
{
struct buffer_head * tmp;
// 搜索hash表，寻找指定设备号和块号的缓冲块。
for (tmp = hash(dev,block) ; tmp != NULL ; tmp = tmp->b_next)
if (tmp->b_dev==dev && tmp->b_blocknr==block)
return tmp;
return NULL;
}根据dev和block号找到缓存区的buffer_head并不代表万事大吉，因为该缓存区可能已经被其他进程/线程占用，当前线程如果一定要用这个缓存区，只能等了，所以最终查找缓存区的代码如下：这里增加了wait_on_buffer函数：
//// 利用hash表在高速缓冲区中寻找指定的缓冲块。若找到则对该缓冲块上锁
// 返回块头指针。
struct buffer_head * get_hash_table(int dev, int block)
{
struct buffer_head * bh;
for (;;) {
// 在高速缓冲中寻找给定设备和指定块的缓冲区块，如果没有找到则返回NULL。
if (!(bh=find_buffer(dev,block)))
return NULL;
// 对该缓冲块增加引用计数，并等待该缓冲块解锁。由于经过了睡眠状态，其他任务可能会更改这个缓存区对应的dev和block号
// 因此有必要在验证该缓冲块的正确性，并返回缓冲块头指针。
bh->b_count++;
wait_on_buffer(bh);
if (bh->b_dev == dev && bh->b_blocknr == block)
return bh;
// 如果在睡眠时该缓冲块所属的设备号或块设备号发生了改变，则撤消对它的
// 引用计数，重新寻找。
bh->b_count--;
}
}wait_on_buffer函数实现：如果发现该缓存区已经上锁，那么调用sleep_on函数让出cpu，阻塞在这里等待；这个sleep_on函数传入的参数是二级指针，并且内部用了tmp变量保存临时变量；由于二级指针是全局的，所以如果有多个task等待同一个缓存区，sleep_on函数是通过先进后出的栈的形式唤醒等待任务的；参考1有详细的说明，感兴趣的小伙伴建议好好看看！
//// 等待指定缓冲块解锁
// 如果指定的缓冲块bh已经上锁就让进程不可中断地睡眠在该缓冲块的等待队列b_wait中。
// 在缓冲块解锁时，其等待队列上的所有进程将被唤醒。虽然是在关闭中断(cli)之后
// 去睡眠的，但这样做并不会影响在其他进程上下文中影响中断。因为每个进程都在自己的
// TSS段中保存了标志寄存器EFLAGS的值，所以在进程切换时CPU中当前EFLAGS的值也随之
// 改变。使用sleep_on进入睡眠状态的进程需要用wake_up明确地唤醒。
static inline void wait_on_buffer(struct buffer_head * bh)
{
cli(); // 关中断
while (bh->b_lock) // 如果已被上锁则进程进入睡眠，等待其解锁
sleep_on(&bh->b_wait);
sti(); // 开中断
} 先进后出的栈形式唤醒等待任务：
接下来可能就是buffer.c中最重要的函数之一了：struct buffer_head * getblk(int dev,int block)，根据设备号和块号得到buffer_head的实例，便于后续使用对应的缓存区；
//// 取高速缓冲中指定的缓冲块
// 检查指定（设备号和块号）的缓冲区是否已经在高速缓冲中。如果指定块已经在
// 高速缓冲中，则返回对应缓冲区头指针退出；如果不在，就需要在高速缓冲中设置一个
// 对应设备号和块好的新项。返回相应的缓冲区头指针。
struct buffer_head * getblk(int dev,int block)
{
struct buffer_head * tmp, * bh;
repeat:
// 搜索hash表，如果指定块已经在高速缓冲中，则返回对应缓冲区头指针，退出。
if ((bh = get_hash_table(dev,block)))
return bh;
// 扫描空闲数据块链表，寻找空闲缓冲区。
// 首先让tmp指向空闲链表的第一个空闲缓冲区头
tmp = free_list;
do {
// 如果该缓冲区正被使用（引用计数不等于0），则继续扫描下一项。对于
// b_count = 0的块，即高速缓冲中当前没有引用的块不一定就是干净的
// (b_dirt=0)或没有锁定的(b_lock=0)。因此，我们还是需要继续下面的判断
// 和选择。例如当一个任务该写过一块内容后就释放了，于是该块b_count()=0
// 但b_lock不等于0；当一个任务执行breada()预读几个块时，只要ll_rw_block()
// 命令发出后，它就会递减b_count; 但此时实际上硬盘访问操作可能还在进行，
// 因此此时b_lock=1, 但b_count=0.
if (tmp->b_count)
continue;
// 如果缓冲头指针bh为空，或者tmp所指缓冲头的标志(修改、锁定)权重小于bh
// 头标志的权重，则让bh指向tmp缓冲块头。如果该tmp缓冲块头表明缓冲块既
// 没有修改也没有锁定标志置位，则说明已为指定设备上的块取得对应的高速
// 缓冲块，则退出循环。否则我们就继续执行本循环，看看能否找到一个BANDNESS()
// 最小的缓冲块。BADNESS等于0意味着b_block和b_dirt都是0，这块缓存区还没被使用，目标缓存区已经找到，可以跳出循环了
if (!bh || BADNESS(tmp)<BADNESS(bh)) {
bh = tmp;
if (!BADNESS(tmp))
break;
}
/* and repeat until we find something good */
} while ((tmp = tmp->b_next_free) != free_list);
// 如果循环检查发现所有缓冲块都正在被使用(所有缓冲块的头部引用计数都>0)中，
// 则睡眠等待有空闲缓冲块可用。当有空闲缓冲块可用时本进程会呗明确的唤醒。
// 然后我们跳转到函数开始处重新查找空闲缓冲块。
if (!bh) {
sleep_on(&buffer_wait);
goto repeat;
}
// 执行到这里，说明我们已经找到了一个比较合适的空闲缓冲块了。于是先等待该缓冲区
// 解锁（多任务同时运行，刚找到的缓存块可能已经被其他任务抢先一步找到并使用了，所以要再次检查）。如果在我们睡眠阶段该缓冲区又被其他任务使用的话，只好重复上述寻找过程。
wait_on_buffer(bh);
if (bh->b_count)
goto repeat;
// 如果该缓冲区已被修改，则将数据写盘，并再次等待缓冲区解锁。同样地，若该缓冲区
// 又被其他任务使用的话，只好再重复上述寻找过程。
while (bh->b_dirt) {
sync_dev(bh->b_dev);
wait_on_buffer(bh);
if (bh->b_count)
goto repeat;
}
/* NOTE!! While we slept waiting for this block, somebody else might */
/* already have added "this" block to the cache. check it */
// 在高速缓冲hash表中检查指定设备和块的缓冲块是否乘我们睡眠之际已经被加入
// 进去(毕竟是多任务系统，有可能被其他任务抢先使用并放入has表)。如果是的话，就再次重复上述寻找过程。
if (find_buffer(dev,block))
goto repeat;
/* OK, FINALLY we know that this buffer is the only one of it's kind, */
/* and that it's unused (b_count=0), unlocked (b_lock=0), and clean */
// 于是让我们占用此缓冲块。置引用计数为1，复位修改标志和有效(更新)标志。
bh->b_count=1;
bh->b_dirt=0;
bh->b_uptodate=0;
// 从hash队列和空闲队列块链表中移出该缓冲区头，让该缓冲区用于指定设备和
// 其上的指定块。然后根据此新的设备号和块号重新插入空闲链表和hash队列新
// 位置处。并最终返回缓冲头指针。
remove_from_queues(bh);
bh->b_dev=dev;
bh->b_blocknr=block;
insert_into_queues(bh);
return bh;
}代码的整体逻辑并不复杂，但是有些细节想展开说说：
BADNESS(bh)：从表达式看，b_dirt左移1位后再和b_lock相加，明显b_dirt的权重乘以了2，说明作者认为缓存区是否被使用的权重应该大于是否被锁！但是实际使用的时候，会一直循环查找BADNESS小的缓存区，说明作者认为b_block比b_dirt更重要，也就是缓存区是否上锁比是否被使用了更重要，这个也符合业务逻辑！
// 下面宏用于同时判断缓冲区的修改标志和锁定标志，并且定义修改标志的权重要比锁定标志大。
// b_dirt左移1位，权重比b_block高
#define BADNESS(bh) (((bh)->b_dirt<<1)+(bh)->b_lock)
循环停止的条件如下：tmp初始值就是free_list，这里的停止的条件也是tmp == free_list，说明free_list是个环形循环链表；所以整个do while循环本质上就是在free_list中找BADNESS值最小的buffer_head；如果找到BADNESS等于0（意味着b_block和b_dirt都为0，该缓存区还没被使用）的buffer_head，直接跳出循环！
while ((tmp = tmp->b_next_free) != free_list);
函数结尾处: 再次检查dev+block是否已经在缓存区了，如果在，说明其他任务捷足先登，已经使用了该缓存区，本任务只能重新走查找的流程；如果该缓存块还没被使用，先设置一些标志/属性位，再把该buffer_head节点从旧hash表和free_list队列溢出，再重新加入hash_table和free_list队列，作者是咋想的？为啥要重复干这种事了？
/* already have added "this" block to the cache. check it */
// 在高速缓冲hash表中检查指定设备和块的缓冲块是否乘我们睡眠之际已经被加入
// 进去（毕竟是多任务，期间可能会被其他任务抢先使用并放入hash表）。如果是的话，就再次重复上述寻找过程。
if (find_buffer(dev,block))
goto repeat;
/* OK, FINALLY we know that this buffer is the only one of it's kind, */
/* and that it's unused (b_count=0), unlocked (b_lock=0), and clean */
// 于是让我们占用此缓冲块。置引用计数为1，复位修改标志和有效(更新)标志。
bh->b_count=1;
bh->b_dirt=0;
bh->b_uptodate=0;
// 从hash队列和空闲队列块链表中移出该缓冲区头，让该缓冲区用于指定设备和
// 其上的指定块。然后根据此新的设备号和块号重新插入空闲链表和hash队列新
// 位置处。并最终返回缓冲头指针。
/*将缓冲块从旧的队列移出，添加到新的队列中，即哈希表的头，空闲表的尾，这样能够迅速找到该存在的块，而该缓冲块存在的时间最长*/
remove_from_queues(bh);
bh->b_dev=dev;
bh->b_blocknr=block;
insert_into_queues(bh);
return bh;先来看看remove_from_queues和insert_into_queu函数代码：remove_from_queues没啥好说的，就是简单粗暴的从hash表和free_list删除，也是常规的链表操作，重点在insert_into_queu函数：
bh节点加入了free_list链表的末尾，直接减少了后续查询遍历链表的时间，这不就直接提升了查询效率么？
bh节点加入hash表某个偏移的表头，后续通过hash偏移不就能第一个找到该节点了么？又省了遍历链表的操作！
//// 从hash队列和空闲缓冲区队列中移走缓冲块。
// hash队列是双向链表结构，空闲缓冲块队列是双向循环链表结构。
static inline void remove_from_queues(struct buffer_head * bh)
{
/* remove from hash-queue */
if (bh->b_next)
bh->b_next->b_prev = bh->b_prev;
if (bh->b_prev)
bh->b_prev->b_next = bh->b_next;
// 如果该缓冲区是该队列的头一个块（每个hash偏移的头），则让hash表的对应项指向本队列中的下一个
// 缓冲区。
if (hash(bh->b_dev,bh->b_blocknr) == bh)
hash(bh->b_dev,bh->b_blocknr) = bh->b_next;
/* remove from free list */
if (!(bh->b_prev_free) || !(bh->b_next_free))
panic("Free block list corrupted");
bh->b_prev_free->b_next_free = bh->b_next_free;
bh->b_next_free->b_prev_free = bh->b_prev_free;
// 如果空闲链表头指向本缓冲区，则让其指向下一缓冲区。
if (free_list == bh)
free_list = bh->b_next_free;
}
//// 将缓冲块插入空闲链表尾部，同时放入hash队列中。
static inline void insert_into_queues(struct buffer_head * bh)
{
/* put at end of free list */
bh->b_next_free = free_list;
bh->b_prev_free = free_list->b_prev_free;
free_list->b_prev_free->b_next_free = bh;
free_list->b_prev_free = bh;
/* put the buffer in new hash-queue if it has a device */
// 请注意当hash表某项第1次插入项时，hash()计算值肯定为Null，因此此时得到
// 的bh->b_next肯定是NULL，所以应该在bh->b_next不为NULL时才能给b_prev赋
// bh值。
bh->b_prev = NULL;
bh->b_next = NULL;
if (!bh->b_dev)
return;
bh->b_next = hash(bh->b_dev,bh->b_blocknr);
hash(bh->b_dev,bh->b_blocknr) = bh;
bh->b_next->b_prev = bh; // 此句前应添加"if (bh->b_next)"判断
}当一个block使用完后就要释放了，避免“占着茅坑不拉屎”；释放的逻辑也简单，如下：引用计数count--，并且唤醒正在等待该缓存区的其他任务；
// 释放指定缓冲块。
// 等待该缓冲块解锁。然后引用计数递减1，并明确地唤醒等待空闲缓冲块的进程。
void brelse(struct buffer_head * buf)
{
if (!buf)
return;
wait_on_buffer(buf);
if (!(buf->b_count--))
panic("Trying to free free buffer");
wake_up(&buffer_wait);
}前面很多的操作，尤其是节点的增删改查都涉及到了hash表和链表，那么hash表和链表都是怎么建立的了？这里用的是buffer_init函数：hash表初始化时所有的偏移都指向null；
// 缓冲区初始化函数
// 参数buffer_end是缓冲区内存末端。对于具有16MB内存的系统，缓冲区末端被设置为4MB.
// 对于有8MB内存的系统，缓冲区末端被设置为2MB。该函数从缓冲区开始位置start_buffer
// 处和缓冲区末端buffer_end处分别同时设置(初始化)缓冲块头结构和对应的数据块。直到
// 缓冲区中所有内存被分配完毕。
void buffer_init(long buffer_end)
{
struct buffer_head * h = start_buffer;
void * b;
int i;
// 首先根据参数提供的缓冲区高端位置确定实际缓冲区高端位置b。如果缓冲区高端等于1Mb，
// 则因为从640KB - 1MB被显示内存和BIOS占用，所以实际可用缓冲区内存高端位置应该是
// 640KB。否则缓冲区内存高端一定大于1MB。
if (buffer_end == 1<<20)
b = (void *) (640*1024);
else
b = (void *) buffer_end;
// 这段代码用于初始化缓冲区，建立空闲缓冲区块循环链表，并获取系统中缓冲块数目。
// 操作的过程是从缓冲区高端开始划分1KB大小的缓冲块，与此同时在缓冲区低端建立
// 描述该缓冲区块的结构buffer_head,并将这些buffer_head组成双向链表。
// h是指向缓冲头结构的指针，而h+1是指向内存地址连续的下一个缓冲头地址，也可以说
// 是指向h缓冲头的末端外。为了保证有足够长度的内存来存储一个缓冲头结构，需要b所
// 指向的内存块地址 >= h 缓冲头的末端，即要求 >= h+1.
while ( (b -= BLOCK_SIZE) >= ((void *) (h+1)) ) {
h->b_dev = 0; // 使用该缓冲块的设备号
h->b_dirt = 0; // 脏标志，即缓冲块修改标志
h->b_count = 0; // 缓冲块引用计数
h->b_lock = 0; // 缓冲块锁定标志
h->b_uptodate = 0; // 缓冲块更新标志(或称数据有效标志)
h->b_wait = NULL; // 指向等待该缓冲块解锁的进程
h->b_next = NULL; // 指向具有相同hash值的下一个缓冲头
h->b_prev = NULL; // 指向具有相同hash值的前一个缓冲头
h->b_data = (char *) b; // 指向对应缓冲块数据块（1024字节）
h->b_prev_free = h-1; // 指向链表中前一项
h->b_next_free = h+1; // 指向连表中后一项
h++; // h指向下一新缓冲头位置
NR_BUFFERS++; // 缓冲区块数累加
if (b == (void *) 0x100000) // 若b递减到等于1MB，则跳过384KB
b = (void *) 0xA0000; // 让b指向地址0xA0000(640KB)处
}
h--; // 让h指向最后一个有效缓冲块头
free_list = start_buffer; // 让空闲链表头指向头一个缓冲快
free_list->b_prev_free = h; // 链表头的b_prev_free指向前一项(即最后一项)。
h->b_next_free = free_list; // h的下一项指针指向第一项，形成一个环链
// 最后初始化hash表，置表中所有指针为NULL。
for (i=0;i<NR_HASH;i++)
hash_table[i]=NULL;
}截至目前，前面围绕缓存区做了大量的铺垫，最终的目的就是和磁盘之间读写数据，那么linux又是怎么利用缓存区从磁盘读数据的了？bread函数代码如下：整个逻辑也很简单，先申请缓存区，如果已经更新就直接返回；否则调用ll_rw_block读磁盘数据；读数据是要花时间的，这段时间cpu没必要闲着，可以跳转到其他进程继续执行；等数据读完后唤醒当前进程，检查buffer是否被锁、是否被更新；如果都没有，就可以安心释放了！
//// 从设备上读取数据块。
// 该函数根据指定的设备号 dev 和数据块号 block，首先在高速缓冲区中申请一块
// 缓冲块。如果该缓冲块中已经包含有有效的数据就直接返回该缓冲块指针，否则
// 就从设备中读取指定的数据块到该缓冲块中并返回缓冲块指针。
struct buffer_head * bread(int dev,int block)
{
struct buffer_head * bh;
// 在高速缓冲区中申请一块缓冲块。如果返回值是NULL，则表示内核出错，停机。
// 然后我们判断其中说是否已有可用数据。如果该缓冲块中数据是有效的（已更新）
// 可以直接使用，则返回。
if (!(bh=getblk(dev,block)))
panic("bread: getblk returned NULL\n");
if (bh->b_uptodate)
return bh;
// 否则我们就调用底层快设备读写ll_rw_block函数，产生读设备块请求。然后
// 等待指定数据块被读入，并等待缓冲区解锁。在睡眠醒来之后，如果该缓冲区已
// 更新，则返回缓冲区头指针，退出。否则表明读设备操作失败，于是释放该缓
// 冲区，返回NULL，退出。
ll_rw_block(READ,bh);
wait_on_buffer(bh);
if (bh->b_uptodate)
return bh;
brelse(bh);
return NULL;
}ll_rw_block：ll全称应该是lowlevel的意思；rw表示读或者写请求，bh用来传递数据或保存数据。先通过主设备号判断是否为有效的设备，同时请求函数是否存在。如果是有效的设备且函数存在，即有驱动，则添加请求到相关链表中；
对于一个当前空闲的块设备，当 ll_rw_block()函数为其建立第一个请求项时，会让该设备的当前请求项指针current_request直接指向刚建立的请求项，并且立刻调用对应设备的请求项操作函数开始执行块设备读写操作。当一个块设备已经有几个请求项组成的链表存在，ll_rw_block()就会利用电梯算法，根据磁头移动距离最小原则，把新建的请求项插入到链表适当的位置处；
void ll_rw_block(int rw, struct buffer_head * bh)
{
unsigned int major;
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(major,rw,bh);
}该函数内部继续调用make_request生成request：函数首先判断是否为提前读或者提前写，如果是则要看bh是否上了锁。上了锁则直接返回，因为提前操作是不必要的，否则转化为可以识别的读或者写，然后锁住缓冲区；数据处理结束后在中断处理函数中解锁；如果是写操作但是缓冲区不脏，或者读操作但是缓冲区已经更新，则直接返回；最后构造request实例，调用add_request函数把实例添加到链表！
add_request函数用了电梯调度算法，主要是考虑到早期机械磁盘的移臂的时间消耗较大，要么从里到外，要么从外到里，顺着某个方向多处理请求。如果req刚好在磁头移动的方向上，那么可以先处理，这样能节省IO(本质是寻址)的时间；
/*
* add-request adds a request to the linked list.
* It disables interrupts so that it can muck with the
* request-lists in peace.
*/
static void add_request(struct blk_dev_struct * dev, struct request * req)
{
struct request * tmp;
req->next = NULL;
cli();
if (req->bh)
req->bh->b_dirt = 0;
if (!(tmp = dev->current_request)) {
dev->current_request = req;
sti();
(dev->request_fn)();
return;
}
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;
sti();
}
static void make_request(int major,int rw, struct buffer_head * bh)
{
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;
else
rw = WRITE;
}
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;
}
repeat:
/* we don't allow the write-requests to fill up the queue completely:
* we want some room for reads: they take precedence. The last third
* of the requests are only for reads.
*/
if (rw == READ)
req = request+NR_REQUEST;
else
req = 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;
}
/* 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);
}add_request中定义了宏IN_ORDER，真正的电梯调度算法体现在这里了：read请求排在写请求前面，先处理读请求，再处理写请求；同一读或写请求先处理设备号小的设备请求，再处理设备号大的设备请求；同一读或写请求，同一设备，按先里面的扇区再到外面的扇区的顺序处理。
/*
* This is used in the elevator algorithm: Note that
* reads always go before writes. This is natural: reads
* are much more time-critical than writes.
*/
#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))))参考：
1、https://blog.csdn.net/jmh1996/article/details/90139485 linux-0.12源码分析——缓冲区等待队列（栈）sleep_on+wake_up分析2
2、https://blog.csdn.net/ac_dao_di/article/details/54615951 linux 0.11 块设备文件的使用
3、https://cloud.tencent.com/developer/article/1749826 Linux文件系统之 — 通用块处理层
离线
页次： 1