对于串行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
输入：系统中允许的最大缓冲区数目
输出：无
描述：初始化高速缓冲管理所需的数据结构（注：初始化空闲缓冲区只是初始化散列表，不包含申请内存。 申请内存只是在‘分配缓冲区’中才可能需要）
2.分配缓冲区
get_block
输入：设备号，块号
输出：指向能被使用的缓冲区的指针，如果没有的话，返回NULL
描述：按前文所述，从高速缓冲中分配一个缓冲区
3.释放缓冲区
put_block
输入：被释放的缓冲区指针
输出：无
描述：按前文所述，将一个缓冲区释放回高速缓冲的空闲表中去。
注：这3个函数必须存在，可以根据需要添加其他的辅助函数
?
附：典型情况举例
(1) 当前情况如下图所示
(2) 调用者申请一个缓冲区，
???可分为3种情况：
a)所要的块在HASH表中找不到，假设是目标块是D，且缓冲数量未达到上限。此时直接从系统内存中申请新的数据库即可。
b)所要的块在HASH表中找不到，假设是目标块是D，且缓冲数量已经达到上限。此时要从空闲表中分配，因为A是LRU表的首个元素，则将A分配给D。具体步骤为将A从LRU表、HASH表中摘除，将它初始化为D，插入新的HASH表中
c)所要的块在HASH表可以找到，假设是B，则将B直接从LRU中摘除
(3) 调用者释放一个缓冲区E
???????将E加放LRU中即可。?
验收方法：
l需要可以进行验收和测试，比如可以创建2个任务来分别模拟get block和put block操作来验证（验证逻辑自己考虑，不作为考查的重点）。
l要求支持查看当前空闲链上区块个数和表项，支持显示挂接在散列表上第num个链表上的区块个数和各个表项，支持显示所有区块。具体命令格式不做要求。
l所有的接口通过放在一个.h和.c中（buf_interface.c buf_interface.h），验收和测试的界面放在另外一个文件中。
根据前文要求，至少有如下3个接口
void init_blk_pool(int);
nand_block_head_t *get_block(int,int);
void put_block(nand_block_head_t *);
l代码要有注释，符合编程规范。
l使用list_head 相关的链表操作接口。
l自己构造hash算法。
2.代码
算buf_interface.h
#ifndef BUF_INTERFACE_H_INCLUDED
#define BUF_INTERFACE_H_INCLUDED
#define BLK_SIZE 512 /* the chip block size */
#define HASH_BITS 6
#define HASH_SIZE (1UL << HASH_BITS)
#define HASH_MASK (HASH_SIZE-1)
#define DATA_VALID 1/* If data is valid,used in the struct of nand_block_head_t */
typedef struct list_head {
struct list_head *next,*prev;
}list_head_t;
typedef struct nand_block_head_s {
struct list_head hash;
struct list_head lru;
int dev; /* device number */
int blk_nr; /* block number */
int flags; /* whether data is valid */
unsigned char blk_data[0];/* area of storing data */
} nand_block_head_t;
#define LIST_HEAD_INIT(name) { &(name),&(name) }
#define LIST_HEAD(name) list_head_t name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do{
(ptr)->next = ptr;(ptr)->prev = ptr;
}while(0)
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr,type,member)
( (type *)( (char *)(ptr) - (unsigned long)(&((type *)0)->member) ) )
/**
* _list_add - Insert a new entry between two known consecutive entries.
* @entry: new entry
* @prev: previous node
* @next: next node
*/
static inline void _list_add(list_head_t *entry,list_head_t *prev,list_head_t *next)
{
next->prev = entry;
entry->next = next;
entry->prev = prev;
prev->next = entry;
}
/**
* list_add - Insert a new entry after the specified head
* @entry: new entry to be added
* @head: list head to add it after
*/
static inline void list_add(list_head_t *entry,list_head_t *head)
{
_list_add(entry,head,head->next);
}
/**
* list_add_tail - Insert a new entry before the specified head.
* @entry: new entry to be added
* @head: list head to add it before
*/
static inline void list_add_tail(list_head_t * entry,head->prev,head);
}
/**
* __list_del - Delete a list entry by making the prev/next entries point to each other.
* @prev: previous node
* @next: next node
*/
static inline void _list_del(list_head_t * prev,list_head_t * next)
{
next->prev = prev;
prev->next = next;
}
/**
* list_del - deletes entry from list and reinitialize it.
* @entry: the element to delete from the list.
*/
static inline void list_del_init(list_head_t *entry)
{
_list_del(entry->prev,entry->next);
INIT_LIST_HEAD(entry);
}
/**
* list_empty - tests whether a list is empty
* @head: the list to test.
*/
static inline int list_empty(list_head_t * head)
{
return (head->next == head);
}
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop counter.
* @head: the head for your list.
*/
#define _list_for_each(pos,head)
for (pos = (head)->next; pos != (head); pos = pos->next)
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop counter.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define _list_for_each_safe(pos,n,head)
for (pos = (head)->next,n = pos->next; pos != (head);
pos = n,n = pos->next)
/* function declaration */
void init_blk_pool();
nand_block_head_t *get_block(int,int);
void put_block(nand_block_head_t *);
#endif // BUF_INTERFACE_H_INCLUDED
buf_interface.c
#include "buf_interface.h"
static struct list_head blk_head_hashtable[HASH_SIZE];
static LIST_HEAD(blk_head_lru);
static int max_cache_size;
static int produce_key(int dev,int blk_nr)
{
return (dev+blk_nr)&HASH_MASK;
}
/*1.初始化空闲缓冲区
init_blk_pool
输入：系统中允许的最大缓冲区数目
输出：无
描述：初始化高速缓冲管理所需的数据结构（注：初始化空闲缓冲区只是初始化散列表，不包含申请内存。
申请内存只是在‘分配缓冲区’中才可能需要）*/
void init_blk_pool(int maxsize)
{
//init hash_table
int i;
for(i=0;i<HASH_SIZE;i++)
{
INIT_LIST_HEAD(&blk_head_hashtable[i]);
}
max_cache_size=maxsize;
INIT_LIST_HEAD(&blk_head_lru);
}
/*2.分配缓冲区
get_block
输入：设备号，块号
输出：指向能被使用的缓冲区的指针，如果没有的话，返回NULL
描述：按前文所述，从高速缓冲中分配一个缓冲区*/
nand_block_head_t *get_block(int dev,int blk_nr)
{
int pool_count=0;
int key=produce_key(dev,blk_nr);
nand_block_head_t *temp_buffer;//用来保存找到的缓冲区
list_head_t* temp_hash_node=&blk_head_hashtable[key];
list_head_t* pos;
//情况一，缓冲区数未达到最大值
_list_for_each(pos,temp_hash_node)
{
temp_buffer=list_entry(pos,nand_block_head_t,hash);
if(temp_buffer->dev==dev&&temp_buffer->blk_nr==blk_nr&&temp_buffer->flags==0)
{
//1.在hash表中找到了相应缓冲区，且缓冲区里面flag为0，则直接从LRU中提出来
list_del_init(pos);
temp_buffer->flags=1;
return temp_buffer;
}
//else {continue;}
pool_count++;
}
//2。缓冲区未达到最大值且在hash表中未直接找到对应缓冲区，则直接从系统内存中申请
if(pool_count<max_cache_size)
{
temp_buffer=(nand_block_head_t*)malloc(sizeof(nand_block_head_t)+BLK_SIZE*sizeof(char));
memset(temp_buffer->blk_data,BLK_SIZE);
temp_buffer->flags=1;
temp_buffer->dev=dev;
temp_buffer->blk_nr=blk_nr;
list_add(&temp_buffer->hash,&blk_head_hashtable[key]);
return temp_buffer;
}
//二.缓冲区数目已经达到最大值
else
{
//list_head_t=blk_head_lru->next;
//1.lru中有空余的缓冲区，则直接去除，给申请者使用
if(blk_head_lru.next!=&blk_head_lru)
{
temp_buffer=list_entry(blk_head_lru.next,hash);
list_del_init(blk_head_lru.next);
list_del_init(&(temp_buffer->hash));
int key=produce_key(dev,blk_nr);
list_add(&temp_buffer->hash,&blk_head_hashtable[key]);
temp_buffer->flags=1;
temp_buffer->dev=dev;
temp_buffer->blk_nr=blk_nr;
memset(temp_buffer->blk_data,BLK_SIZE);
return temp_buffer;
}
return 0;
}
}
/*3.释放缓冲区
put_block
输入：被释放的缓冲区指针
输出：无
描述：按前文所述，将一个缓冲区释放回高速缓冲的空闲表中去*/
void put_block(nand_block_head_t * node_to_del)
{
if(node_to_del==0)
{
printf("not exist this kind of buffer block");
return;
}
else if(node_to_del->flags==0)
{
printf("this kind of buffer block have in free list");
return;
}
node_to_del->flags=0;
list_add_tail(&node_to_del->lru,&blk_head_lru);
memset(node_to_del->blk_data,BLK_SIZE);
/* check whether the block added to the list but now */
/* if added successfully,the prev of head point to it */
if(blk_head_lru.prev == &(node_to_del->lru)){
printf("block has added to the free listnndevice = %dnblock = %dn",node_to_del->dev,node_to_del->blk_nr);
}
}
//显示节点
void show_node_info()
{
nand_block_head_t *temp_buffer;//用来保存找到的缓冲区
list_head_t* temp_hash_node;
list_head_t* pos;
int i;
for(i=0;i<HASH_SIZE;i++)
{
temp_hash_node=&blk_head_hashtable[i];
_list_for_each(pos,temp_hash_node)
{
temp_buffer=list_entry(pos,hash);
printf("缓存池中的节点为key=%d,dev=%d,blk_nr=%d,flags=%dtn",i,
temp_buffer->dev,temp_buffer->blk_nr,temp_buffer->flags);
}
}
}
void show_lru_info()
{
nand_block_head_t *temp_buffer;//用来保存找到的缓冲区
list_head_t* pos;
_list_for_each(pos,&blk_head_lru)
{
temp_buffer=list_entry(pos,lru);
printf("lru中的节点为dev=%d,
temp_buffer->dev,temp_buffer->flags);
}
}
main.c 仅仅是测试<pre name="code" class="cpp">#include <stdio.h>
#include <stdlib.h>
#include "buf_interface.h"
int main()
{
init_blk_pool(100);
nand_block_head_t* temp=get_block(1,1);
put_block(temp);
temp=get_block(1,2);
put_block(temp);
show_node_info();
show_lru_info();
printf("nihaon");
show_node_info();
show_lru_info();
return 0;
}
