linux0.11缓冲区设计解读

发表于 更新于 分类于 ， 阅读次数： 本文字数： 9.8k 阅读时长 ≈ 9 分钟

linux0.11缓冲区设计解读

在之前的笔记中，我们已经零散的介绍了缓冲区的相关设计。这里我们系统的总结linux0.11关于缓冲区的相关设计

缓冲区：高速缓冲区位于内核代码块和主内存区之间

高速缓存

缓冲区的作用与设计原则

首先，我们需要考虑，我们为什么需要缓冲区，在什么情况下缓冲区可以没有。

缓冲区：开一块内存，磁盘内容先读到缓冲区，在缓冲区读到内存

缓冲区示意图

缓冲区的优势：

1.块设备的统一集散地，使得操作系统设计更方便，更灵活

2.对块设备的文件操作运行效率更高

前提：从内存读比从磁盘读快200倍

image-20231115093737912

怎么设计缓冲区才能重复使用。

为啥使用缓冲区快：存在重复读写的时候变快，有点像catche

怎么设计缓冲区才能满足重复使用，使得读写变快？

思路：缓冲区的数据一旦进了缓冲区就尽可能呆在缓冲区时间长：怎么设计

如果counter=0且没有新的请求或者缓冲区没满，那么这个conuter的buffer head还得在缓冲区里面放着，满足在缓冲区时间长

如果缓冲区满了，有新的请求，则把counter=0的挪出去，把新的加进来

如果缓冲区满了，没有counter=0的，有新的请求，则新的请求等待。

缓冲区数据结构

缓冲区涉及的操作主要是buffer head和request，也就是缓冲区部分和块设备部分

主要操作

缓冲区双向环链表和hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct buffer_head {
	char * b_data;	// 指向数据块的指针（数据块为 1024 字节）	/* pointer to data block (1024 bytes) */
	unsigned long b_blocknr;	// 块号//块号/* block number */
	unsigned short b_dev;	// 数据源的设备号（0 表示未用）。	/* device (0 = free) */
	unsigned char b_uptodate; // 更新标志：表示数据是否已更新。
	unsigned char b_dirt;	// 修改标志：0-未修改，1-已修改。	/* 0-clean,1-dirty */
	unsigned char b_count;		// 使用该数据块的用户数。 /* users using this block */
	unsigned char b_lock;	// 缓冲区是否被锁定，0-未锁；1-已锁定。	/* 0 - ok, 1 -locked */
	struct task_struct * b_wait;// 指向等待该缓冲区解锁的任务。 
	struct buffer_head * b_prev; // 前一块（这四个指针用于缓冲区的管理）。 
	struct buffer_head * b_next;  // 下一块。
	struct buffer_head * b_prev_free; // 前一空闲块。 
	struct buffer_head * b_next_free; // 下一空闲块。
};

其中 ==b_blocknr== ==unsigned short b_dev==，是缓冲区接受多进程文件和设计的基础

如何保证缓冲块的唯一性：、

每个缓冲块有唯一的bufffer_head,内核通过b_dev和b_blocknr设备号块号把缓冲块和磁盘数据块绑定保证了关系的唯一性

buffer_head 被链接成一个空闲缓冲块双向链表结构。

双向环链表

为了能够快速地在缓冲区中寻找请求的数据块是否已经被读入到缓冲区中，buffer.c 程序使用了具有307 个 buffer_head 指针项的==hash 表结构==。上图中 buffer_head 结构的指针 b_prev、b_next 就是用于 hash表中散列在同一项上多个缓冲块之间的双向连接。Hash 表所使用的散列函数由==设备号和逻辑块号组合而成==。程序中使用的具体函数是：==(设备号^逻辑块号) Mod 307==。

hash结构

image-20231115104420577

request 数据结构

1
2
3
4
5
6
7
8
9
10
11
12
struct 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;//指向下一个请求项
};

request是一个数组，被用到的request挂载dev_hd这个数组结构下面形成一条链表

缓冲绘图

linux0.11做的缓冲区相关初始化操作

进程与缓冲区交互以块为单位，内核支持缓冲区与磁盘交互通过request交互。块是操作系统的概念，磁盘只有扇区的概念。（request相当于一个翻译官）

buffer

buffer_init(buffer_memory_end);

struct buffer_head * start_buffer = (struct buffer_head *) &end;

这里的end就是内核代码末端的地址，设计者较难事先预估在内核模块链接期间设置end值，在这里使用

buffer.c里面的buffer_init:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void buffer_init(long buffer_end)
{
	struct buffer_head * h = start_buffer;
	void * b;
	int i;
 // 如果缓冲区高端等于 1Mb，则由于从 640KB-1MB 被显示内存和 BIOS 占用，因此实际可用缓冲区内存 
 // 高端应该是 640KB。否则内存高端一定大于 1MB。 
	if (buffer_end == 1<<20)
		b = (void *) (640*1024);
	else
		b = (void *) buffer_end;
// 这段代码用于初始化缓冲区，建立空闲缓冲区环链表，并获取系统中缓冲块的数目。 
 // 操作的过程是从缓冲区高端开始划分 1K 大小的缓冲块，与此同时在缓冲区低端建立描述该缓冲块 
 // 的结构 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;
}

缓冲初始化

blk_dev

blk.h：

\#define NR_BLK_DEV 7

系统管理外设的重要数据结构：对于各种块设备，内核使用了一张块设备表 blk_dev[]来进行管理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct blk_dev_struct { 
 void (*request_fn)(void); // 请求项操作的函数指针。 
 struct request * current_request; // 当前请求项指针。 
};

struct blk_dev_struct blk_dev[NR_BLK_DEV] = {
	{ NULL, NULL },		/* no_dev */
	{ NULL, NULL },		/* dev mem */
	{ NULL, NULL },		/* dev fd */
	{ NULL, NULL },		/* dev hd */
	{ NULL, NULL },		/* dev ttyx */
	{ NULL, NULL },		/* dev tty */
	{ NULL, NULL }		/* dev lp */
};
主设备号

blk_dev[major].request 在hd_init里面做了初始化，挂载了请求项函数：do_hd_request， current_request指向null

1
2
3
4
5
6
7
8
#define DEVICE_REQUEST do_hd_request


void hd_init(void)
{
	blk_dev[MAJOR_NR].request_fn = DEVICE_REQUEST;
    ...
}
blk_dev

request

struct request request[NR_REQUEST];//32

1
2
3
4
5
6
7
8
9
void blk_dev_init(void)
{
	int i;
    //NR_REQUEST是请求项的数量=32
	for (i=0 ; i<NR_REQUEST ; i++) {
		request[i].dev = -1;//设为空闲，说明这个请求项还没有聚体对应那个设备，用于判断请求项当前设备是否空闲
		request[i].next = NULL;//互不挂接，说明还没形成请求队列
	}
}

一个是七个blk_dev的一个是32个的request(是一个数组链表)

request

获取缓冲块，缓冲块与进程，磁盘设备绑定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct buffer_head * bread(int dev,int block)//读指定的dev，block，第一块dev是0x300   block：0
{
	struct buffer_head * bh;
    //先到缓冲区里面找有没有相同的块
	//dev设备号block 块号
	if (!(bh=getblk(dev,block))) //在缓冲区找与dev，block相符合的缓冲块
		panic("bread: getblk returned NULL\n"); //因为现在是进程一第一次使用缓冲区不可能没有空闲块
    /*找到缓冲块与请求项挂载*/
	if (bh->b_uptodate) //如果在缓冲区找到了相符合的块，如果该缓冲区中的数据是有效的（已更新的），否则可能内存还没向缓冲区完成写
		return bh;   //返回块
	// 否则调用 ll_rw_block()函数，产生读设备块请求。并等待缓冲区解锁。
	ll_rw_block(READ,bh); 
	wait_on_buffer(bh);//之前调用了读盘的操作，数据还没用从硬盘中读完，因此等待
	// 如果该缓冲区已更新，则返回缓冲区头指针，退出。
	if (bh->b_uptodate)
		return bh;
	// 否则表明读设备操作失败，释放该缓冲区，返回 NULL 指针，退出。 
	brelse(bh);
	return NULL;
}

get_hash_table

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct buffer_head * get_hash_table(int dev, int block)
{
	struct buffer_head * bh;

	for (;;) {
		if (!(bh=find_buffer(dev,block)))//在hash的链表中找相同设备号块号的缓冲区
			return NULL;
		bh->b_count++;//增加缓冲块的引用计数
		wait_on_buffer(bh);//等待缓冲块，因为之前的进程不一定用完了，如果是lock的该进程sleep
		if (bh->b_dev == dev && bh->b_blocknr == block)
			return bh;
		bh->b_count--;
	}
}
gethashtable

find_buffer

1
2
3
4
5
6
7
8
9
10
11
#define hash(dev,block) hash_table[_hashfn(dev,block)]

static struct buffer_head * find_buffer(int dev, int block)
{		
	struct buffer_head * tmp;

	for (tmp = hash(dev,block) ; tmp != NULL ; tmp = tmp->b_next)
		if (tmp->b_dev==dev && tmp->b_blocknr==block)
			return tmp;
	return NULL;
}
find—buffer

getblk

缓冲块搜索函数 getblk()，以获取适合的缓冲块。该函数首先 调用 get_hash_table()函数，在 hash 表队列中搜索指定设备号和逻辑块号的缓冲块是否已经存在。如果存在就立刻返回对应缓冲头结构的指针；

1
2
3
4
5
6
7
8
9
struct buffer_head * getblk(int dev,int block)
{
	struct buffer_head * tmp, * bh;

repeat:
	if (bh = get_hash_table(dev,block))
		return bh;
    ...
}

如果不存在现成的，则从空闲链表头开始，对空闲链表进行扫描，寻找 一个空闲缓冲块。在寻找过程中还要对找到的空闲缓冲块作比较，根据赋予修改标志和锁定标志组合而成的权值，比较哪个空闲块最适合。若找到的空闲块既没有被修改也没有被锁定，就不用继续寻找了。

这里的dirt指的是进程方向的，dirt=1指的是进程修改了缓冲块，还没有写到硬盘中，而update是硬盘方向的，update=1指的是硬盘刷新过的缓冲块，数据已经读入内存。dirt和lock的区别体现在，lock是指缓冲块正在同步（正在写入硬盘），而dirt还不知道什么时候写，所以相比之下，dirt位比lock位更加的不好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#define BADNESS(bh) (((bh)->b_dirt<<1)+(bh)->b_lock)
static struct buffer_head * free_list;

struct buffer_head * getblk(int dev,int block)
{
    ...
	tmp = free_list;
	do {
		//如果被人用了就接着往下遍历
		if (tmp->b_count)
			continue;
			//BADNESS：dirt<<2+lock
			//一读一写才有竞争，生产者消费者模型，谁是自动化的，谁是主动的进程可以干预的，所以要锁住内存到缓冲区的路径
			//因此一加锁说明缓冲区到磁盘正在自动化操作
			//dirt说明缓冲区被进程写过，还没开始自动化的过程
			//因此dirt和lock选一个，选lock，因为lock干的时间短
			//dirt左移说明加了权重了
			//要从11 10 01 00 里面找最小的一个
		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);
        
	if (!bh) {
		sleep_on(&buffer_wait);
		goto repeat;
	}
        ...
    }
getblk1

若没有找到空闲块，则让当前进程进入睡眠状态，待继续执行时再次寻找。若该空闲块被锁定，则进程也需进入睡眠，等待其它进程解锁。若在睡眠等待的过程中，该缓冲块又被其它进程占用，那么只要再 重头开始搜索缓冲块。

1
2
3
wait_on_buffer(bh);//等待写完缓冲区
	if (bh->b_count)//不空闲则重复上面的操作//在buffer_init里面初始化的时候设置成0
		goto repeat;

否则判断该缓冲块是否已被修改过，若是，则将该块写盘，并等待该块解锁。此 时如果该缓冲块又被别的进程占用，那么又一次全功尽弃，只好再重头开始执行 getblk()。

1
2
3
4
5
6
7
//脏位置一，说明缓冲块被写了，当前正等待用户写
	while (bh->b_dirt) {
		sync_dev(bh->b_dev);
		wait_on_buffer(bh);
		if (bh->b_count)
			goto repeat;//又被其它进程小贼抢占了，只能继续从头再来
	}

在经历了以上 折腾后，此时有可能出现另外一个意外情况，也就是在我们睡眠时，可能其它进程已经将我们所需要的 缓冲块加进了 hash 队列中，因此这里需要最后一次搜索一下 hash 队列。如果真的在 hash 队列中找到了 我们所需要的缓冲块，那么我们又得对找到的缓冲块进行以上判断处理，因此，又一次需要重头开始执 行 getblk()。最后，我们才算找到了一块没有被进程使用、没有被上锁，而且是干净（修改标志未置位） 的空闲缓冲块。于是我们就将该块的引用次数置 1，并复位其它几个标志，然后从空闲表中移出该块的 缓冲头结构。在设置了该缓冲块所属的设备号和相应的逻辑号后，在将其放入 hash 表对应表项的第一个 和空闲队列的末尾处。最终，返回该缓冲块头的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct buffer_head * getblk(int dev,int block)
{
    ...
 //终于申请到能用的缓冲块了，发现有好兄弟进程先自己一步找到了缓冲块并且加入了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 */
	bh->b_count=1;//占用该缓冲块
	bh->b_dirt=0;//还没有读盘dirt不置1
	bh->b_uptodate=0;
	remove_from_queues(bh);//假设都满了就会在叉子上面摘下来，放到其他的设备号块号上面
	bh->b_dev=dev;//更换设备号块号
	bh->b_blocknr=block;
	//要把缓冲块叉在hash上面才算纳入了缓冲区的管理范围
	insert_into_queues(bh);//重新插到合适的位置
	return bh;
}

占用缓冲块：

getblk2

remove_from_queues

image-20231115104420577

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 从 hash 队列中移除缓冲块 */ 
static inline void remove_from_queues(struct buffer_head * bh)
{
/* remove from hash-queue */
//hash队列链表上删除结点，但是始终都在双向环链表上面
	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 表的对应项指向本队列中的下一个缓冲区。
	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;
}

insert_into_queues

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//// 将指定缓冲区插入空闲链表尾并放入 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 队列中，头插入 */
	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;
}

bread

进程与缓冲块

内核通过文件操作指针计算出文件数据所在的设备号块号，进程方面延申到缓冲块位置，执行bread后就不在与硬盘数据块直接打交道了

写文件同样延申到bread为止