前段时间写了篇文章《深入浅出linux内核源代码之双向链表list_head 》，收到一位读者的email，这封email的有个附件，是关于用list_head来实现一个数据缓冲区的程序设计，我把这个附件的内容写上，如下：

 

串行FLASH数据缓冲区的管理

对于串行FLASH芯片的存取操作，内核能够通过直接对芯片的读写来实现，但是较慢的芯片响应速度会使用读写响应时间加长，吞吐率降低。因此，内核通过保持一个称为数据缓冲区高速缓冲的内部数据缓冲区来减小对芯片的存取频度。高速缓冲含有最近被使用过的串行Flash的数据。

当从芯片中读数据的时候，内核试图先从高速缓冲中读取。如果数据已经在该高速缓冲中，则内核可以不必从芯片中读取数据。如果数据不在该高速缓冲中，则内核从芯片上读数据，并将其缓冲起来，这样下次使用时就不需要再从芯片中读取了。
但是，由于串行Flash的容量都比较大，将Flash的所有内容都缓冲在内存中是不可行的，只能将部分Flash的内容缓冲起来。所使用的算法试图把尽可能多的有效数据保存在高速缓冲中。

以下的算法描述的就是数据缓冲区的管理。

 

数据缓冲区的结构
缓冲区由两部分组成：一个用于存储数据块的数组及一个用来标识该缓冲区的缓冲头部，两者是一到一的映射关系。
缓冲区头部含一个设备号字段与一个块号字段，这两个字段唯一地标识了该缓冲区。这两个字段都是16-bit的。
缓冲区头部含有一个标志，用于标识存储数据块的数据是否含有有效的数据。显然，当缓冲区刚分配时，它其中没有有效的数据，当驱动程序从芯片中数据读出后，数据块中含有有效的数据。

缓冲池的结构
数据块以最近最少使用算法（LRU，least recently used）缓冲于缓冲池中：当一个缓冲区使用之后，只要不是所有其他缓冲区都在更近的时间内被使用过了，它就不能让其他使用者使用该缓冲区。

系统中维护一个缓冲区的空闲表，它按被最近使用的次序保存块的缓冲。空闲表是缓冲区的双向循环表，具有一个哑缓冲区头，以标志缓冲区空闲表的开始和结束。当内核想要一个空闲缓冲区的话，它可以从空闲表的头部取出一个缓冲区。但是，如果它可以标识出缓冲池中一个特定的块的话，它会从空闲表的中间取出这个特定的缓冲区。在这两种情况下，它都从空闲表中摘下缓冲区。当内核把一个缓冲区归还缓冲池时，它把该缓冲区附到空闲表的尾部。当内核从空闲表上不断地摘下缓冲区时，装有有效数据的缓冲区会越来越近地移动到空闲表的头部。因此，离空闲表的头部近的缓冲区比离空闲表的头部远的缓冲区是最近最少使用的。

当内核申请一个数据块时，它使用对应的设备号和块号的组合去找相应的缓冲区。它并不是去搜索整个缓冲区池。缓冲区组织成一个个队列，这些队列是以设备号和块号来散列的。内核把一个散列队列上的缓冲区链接成一个类似于空闲表结构的双向链接循环表。一个散列队列上的缓冲区数目在系统生存期间是变化的。内核必须使用一个散列函数，该散列函把诸缓冲均匀分布在一组散列队列中。散列函数也必须简单，以便使性能不受损失。

每个缓冲区总在存在于一个散列队列中，然而它位于队列上的什么位置是不重要的。一个缓冲区可以同时既存在于一个散列队列中又存在于一个空闲队列中，所以内核在两个方法可以找到它：如果它要寻找一个特定的缓冲，则它搜索散列队列；如果它要寻找任何一个空闲缓冲区，则它从空闲表中摘下一个缓冲区。概括的说，一个缓冲区总是在某个散列队列上，但是它可以在或不在空闲表中。

最初空闲表中空的，所需要的块是从系统内存中分配的。申请块缓冲时，在整个数据块已经申请的缓冲数量未达到上限以前，从系统中申请新的数据块，否则，从空闲表中分配，如果空闲表也没有数据块，则返回失败。

数据结构：

#define BLK_SIZE 512 /* the chip block size */ #define HASH_BITS 6 #define HASH_SIZE (1UL << HASH_BITS) #define HASH_MASK (HASH_SIZE-1) typedef struct nand_block_head_s { struct list_head hash; struct list_head lru; int dev; int blk_nr; int flags; /* see below */ unsigned char blk_data[0]; } nand_block_head_t; #define DATA_VALID 1 /* If data is valid */ static struct list_head blk_head_hashtable[HASH_SIZE]; static LIST_HEAD(blk_head_lru);

 

提示：HASH_BITS 的值可根据实际情况修改；

不考虑调用者重复申请同一个缓冲区的情况

算法 :

1. 初始化空闲缓冲区

init_blk_pool

输入：系统中允许的最大缓冲区数目

输出：无

描述：初始化高速缓冲管理所需的数据结构

1. 分配缓冲区

get_block

输入：设备号，块号

输出：指向能被使用的缓冲区的指针，如果没有的话，返回NULL

描述：按前文所述，从高速缓冲中分配一个缓冲区

1. 释放缓冲区

put_block

输入：被释放的缓冲区指针

输出：无

描述：按前文所述，将一个缓冲区释放回高速缓冲的空闲表中去。

 

附：典型情况举例

(1) 当前情况如下图所示

(2) 调用者申请一个缓冲区，

可分为两种情况：

1. 所要的块在HASH 表中找不到，假设是D ，则将A 分配给D ；

a、需要将A 从LRU 表、HASH 表中摘除，将它初始化为D ，插入新的HASH 表中

 

            b、所要的块在HASH 表可以找到，假设是B ，则将B 直接从LRU 中摘除

(2) 调用者释放一个缓冲区E

将E 加放LRU 中即可。

 

验收方法：

1. 有可以进行验收和测试的界面，要求对每个接口都提供提供测试界面（界面风格不做要求，不作为考核的重点）

2. 所有的接口通过放在一个.h 和.c 中（buf_interface.c buf_interface.h ），验收和测试的界面放在另外一个文件中。这样，测试人员就可以用这个文件的.o 进行测试。

3. 代码要有注释，符合编程规范。

4. 不能使用vc, 直接进行cygwin+gcc 的编译。

5. 使用list_head 相关的链表操作接口，list_head 自己上网找，linux 到处都是，自己移植过来。

6. 要使用hash 查找，自己构造hash 算法。

 

 

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

下面是我针对这篇文章的一点理解，首先， 设备号字段与块号字段是16位的，但上面给的结构的dev和blk_nr是int（现在大多数计算机的int都是32位的），除非这两个字段不是设备号字段与块号字段，不然也在结构中找不到其它可以表示设备号字段与块号字段了，所以我把这个结构的这两个成员改成short型的了。

 

下面使我对这个文档的理解的一个程序实现：

buf_interface.h

 

#ifndef LIST_CACHE_H #define LIST_CACHE_H #include "list.h" #define BLK_SIZE 512 /* the chip block size */ #define HASH_BITS 6 #define HASH_SIZE (1UL << HASH_BITS) #define HASH_MASK (HASH_SIZE-1) typedef struct nand_block_head_s { struct list_head hash; struct list_head lru; short dev; short blk_nr; int flags; /* see below */ unsigned char blk_data[0]; } nand_block_head_t; #define DATA_VALID 1 /* If data is valid */ void init_blk_pool(unsigned long max_cache); nand_block_head_t * get_block(short dev, short blk_nr); void put_block(nand_block_head_t *tmp); // test functions nand_block_head_t* get_from_hash(short dev, short blk_nr); int set_block(nand_block_head_t* node, const char* data); void clear_all(); static struct list_head blk_head_hashtable[HASH_SIZE]; static LIST_HEAD(blk_head_lru); #endif

buf_interface.c

 

#include "buf_interface.h" #include <stdio.h> #include <string.h> #include <stdlib.h> int key(short dev, short blk_nr) { int key = ((dev<<16) | (blk_nr)); return key%BLK_SIZE; } void init_blk_pool(unsigned long max_cache) { nand_block_head_t *tmp_block_head = NULL; unsigned long i = 0; for(i = 0; i < HASH_SIZE; i++) INIT_LIST_HEAD(&blk_head_hashtable[i]); for(i = 0; i < max_cache; i++) { tmp_block_head = (nand_block_head_t*)malloc(sizeof(nand_block_head_t) + BLK_SIZE*sizeof(char)); //这里不分配芯片的缓冲区，只在需要时再分配，这样可以节省内存空间,但需要一个变量来说明是否已经分配过空间 //tmp_block_head = (nand_block_head_t*)malloc(sizeof(nand_block_head_t)); /* test if malloc success*/ /*if (!tmp_block_head)*/ tmp_block_head->flags = -1; tmp_block_head->dev = i>>16; tmp_block_head->blk_nr = i & 0xffff; /* add to free list*/ list_add(&(tmp_block_head->lru), &blk_head_lru); /*add to hash */ int no = i % HASH_SIZE; list_add(&(tmp_block_head->hash), &blk_head_hashtable[no]); } } nand_block_head_t * get_block(short dev, short blk_nr) { if (list_empty(&blk_head_lru)) return NULL; nand_block_head_t *tmp_block_head = NULL; /* get the nearest head from lru */ struct list_head* pos = blk_head_lru.next; tmp_block_head = list_entry(pos, nand_block_head_t, lru); /*delete it from lru */ list_del_init(pos); list_del_init(&(tmp_block_head->hash)); int no = key(dev, blk_nr); list_add(&(tmp_block_head->hash), &blk_head_hashtable[no]); if(tmp_block_head) { tmp_block_head->dev = dev; tmp_block_head->blk_nr = blk_nr; } return tmp_block_head; } void put_block(nand_block_head_t *tmp) { tmp->flags = -1; list_add_tail(&(tmp->lru), &blk_head_lru); } nand_block_head_t* get_from_hash(short dev, short blk_nr) { int no = key(dev, blk_nr); nand_block_head_t *node = NULL; // find from hash if (!list_empty(&blk_head_hashtable[no])) { struct list_head *pos; list_for_each(pos, &blk_head_hashtable[no]) { nand_block_head_t *tmp = list_entry(pos, nand_block_head_t, hash); if (tmp->flags != -1 && tmp->dev == dev && tmp->blk_nr == blk_nr) { node = tmp; break; } } } return node; } //在获得一个节点后，我们可以给这个节点分配芯片内存并让它存储数据 int set_block(nand_block_head_t* node, const char* data) { // get it from free list if (node) { node->flags = 1; //我们这里检测这个节点是否已经分配过芯片缓冲区 //if () //{//如果没有，就分配 //分配芯片的块大小的缓冲区 // node = realloc(node, sizeof(nand_block_head_t) + BLK_SIZE*sizeof(char)); //} //已经分配过了就直接使用 memcpy(node->blk_data, data, strlen(data)); return 0; } else // no empty cache { fprintf(stderr, "invalide param!/n"); return -1; } } //清除在初始化时分配的所有内存 void clear_all() { struct list_head *pos, *n; nand_block_head_t *tmp; int i; for(i = 0; i<HASH_SIZE; i++) { if (!list_empty(&blk_head_hashtable[i])) { list_for_each_safe(pos, n, &blk_head_hashtable[i]) { tmp = list_entry(pos, nand_block_head_t, hash); list_del_init(pos); free(tmp); tmp = NULL; } } } }

 

这里的

// test functions
       nand_block_head_t* get_from_hash(short dev, short blk_nr);
       int set_block(nand_block_head_t* node, const char* data);
       void clear_all();

是我的测试函数。

下面是main.c

#include "buf_interface.h" #include <stdio.h> #include <string.h> #define MAX_CACHE 10000 int main(int argc, const char *argv[]) { init_blk_pool(MAX_CACHE); short dev = 10, blk_nr = 20; /* get a block */ printf("/n=============================================/n/n"); fprintf(stdout, "从hash表中获取dev=%d, blk_nr=%d的节点/n", dev, blk_nr); nand_block_head_t *tmp = get_from_hash(dev, blk_nr); if(tmp) { fprintf(stdout, " 已经从hash表中得到这个节点:/n"); fprintf(stdout, " dev: %d, blk_nr: %d/n", tmp->dev, tmp->blk_nr); fprintf(stdout, " data: %s/n", tmp->blk_data); } else { fprintf(stdout, "/nhash表中没有dev=%d, blk_nr=%d的节点/n", dev, blk_nr); fprintf(stdout, "这将从空余链表中分配一个空余的节点!/n"); tmp = get_block(dev, blk_nr); if (tmp) { fprintf(stdout, "/n已经从空余链表中分配到了一个节点给它！/n"); fprintf(stdout, "给这个节点分配数据 －－－ first used!/n"); set_block(tmp, "first used!"); } else { fprintf(stderr, "error: 空余链表中没有了空余节点了！/n"); clear_all(); return -1; } } fprintf(stdout, "/n我们再次从hash表中获取dev=%d, blk_nr=%d的节点/n", dev, blk_nr); // test: get it again and find if it in hash table now tmp = get_from_hash(dev, blk_nr); if(tmp) { fprintf(stdout, " 已经从hash表中得到这个节点:/n"); fprintf(stdout, " dev: %d, blk_nr: %d/n", tmp->dev, tmp->blk_nr); fprintf(stdout, " data: %s/n", tmp->blk_data); } else { fprintf(stderr, "error!/n"); } //这里测试节点之前已经分配过内存的情况 fprintf(stdout, "/n我们再次给这个节点分配数据 －－－ second used!/n"); set_block(tmp, "second used!"); if (tmp) { fprintf(stdout, " 再次分配数据的节点的信息为：/n"); fprintf(stdout, " dev: %d, blk_nr: %d/n", tmp->dev, tmp->blk_nr); fprintf(stdout, " data: %s/n", tmp->blk_data); } printf("/n================= test end ======================/n/n"); clear_all(); return 0; }

 

Makefile:

test: main.c buf_interface.c
               gcc -g -Wall main.c buf_interface.c buf_interface.h -o test

关于测试，说一下：

首先，我是想从hash表中用 get_from_hash（dev, blk_nr）函数获得    short dev = 10, blk_nr = 20的节点，但一开始，肯定不可能获得这个节点，因为还没有使用过这个hash表，所以在从hash表中查找的话返回一个NULL，在找不到时，就从空闲链表中分配一个空闲的节点get_block(dev, blk_nr)，然后我们用set_block(tmp, "first used!")函数来使用这个节点，这个使用就是给这个节点的数据内容分配“first used!"这个字符串而已。再一次，我用 get_from_hash(dev, blk_nr)从hash表中再获取这个节点，由于我们已经使用过这个节点，因此它就存在于缓冲区中，所以我们就可以获得，并打印出它的内容，并用set_block(tmp, "second used!")再使用它的缓冲，并付给不同的内容"second used!"，然后再打印这个节点的内容。

在这里有一点想说的是，我们看到结构是数据内容是一个零长度数组，我们知道零长度数组只是一个占位符，所以你看到我在初始化结构链表时，就给每个节点分配缓冲区了，这样的一个好处是只分配一次，不好的地方是一下子就全部分配，而不是在使用的时候才分配。

所以你做法是你初始化hash表时，只分配节点，在获得和使用节点时才给节点分配数据区，在收回节点时再销毁节点的数据区，这有个不好的是要平凡的分配和销毁节点的数据区。

程序最后用

void clear_all();

函数来销毁之前初始化的每个节点，这些对list_head的使用已经在我之前的文章《深入浅出linux内核源代码之双向链表list_head 》已经说得很详细了，如果你不了解list_head的使用，你可以参考这篇文章。

程序的输出如下：

 

=============================================

从hash表中获取dev=10, blk_nr=20的节点

hash表中没有dev=10, blk_nr=20的节点
这将从空余链表中分配一个空余的节点!

已经从空余链表中分配到了一个节点给它！
给这个节点分配数据 －－－ first used!

我们再次从hash表中获取dev=10, blk_nr=20的节点
        已经从hash表中得到这个节点:
        dev: 10, blk_nr: 20
        data: first used!

我们再次给这个节点分配数据 －－－ second used!
        再次分配数据的节点的信息为：
        dev: 10, blk_nr: 20
        data: second used!

================= test end ======================

 

如对程序有任何问题，欢迎提出探讨！

代码大包下载:

串行FLASH数据缓冲区的管理(程序）