需要用到的数据结构: 链表，基树。

　　

gearcache在qemu-kvm虚拟化平台下的实现主要有以下的步骤:

1.打开镜像文件的时候，为gearcache中的基数池(page_node_pool)和读写数据池(buf_pool)的存储创建相应的内存空间。

2.将qemu-kvm对于镜像文件的读写IO粒度控制在512字节。

3.对于所有的写请求进行拦截：

　-(1)先通过该写请求的offset在基数池当中查找，如果存在该offset，那么将这个写请求复写(overwirte)到基数当中，覆盖对应的数据块。

　-(2)如果该写请求的offset不存在基树池当中，那么就在buf_pool中分配512字节空间存储该数据，并在基数池(page_node_pool)中对应的offset的位置创立一个节点，保存该节点的信息，并将该节点插入(insert_this_write)到链表里面去，每个链表的节点都有一个指针指向对应的buf_pool的数据块中，并存储对应的offset。

　-(3)然后判断buf_pool是否被写满了，如果写满了，就顺着在(2)中所建立的链表的顺序，将每个链表节点所存储的512字节的数据通过pwrite写到镜像文件对应的offset的位置中去。每写完一个节点的数据，释该节点对应的buff_pool 和page_node_pool的空间。直到到达链表的尾部。

4.对所有的读请求进行拦截；

　-(1)通过该读请求的offset在基树池当中查找，如果存在该offset，那么将对应节点里所存储的512字节的数据返回便可。

　-(2)如果该读请求不存在基树池当中，那么就执行qemu原本的读请求的处理。

5.关闭镜像文件的时候:

　将每个链表节点所存储的512字节的数据通过pwrite写到镜像文件对应的offset的位置中去。每写完一个节点的数据，释该节点对应的buff_pool和page_node_pool的空间。直到到达链表的尾部。