BCache源码浅析之二数据结构与操作

ZZ: http://blog.csdn.net/wanthelping/article/details/50448975

2.主流程与数据结构

2.1 bcache初始化

(1) register_bcache

         首先read_super得到超级快的信息，根据该信息能的知道是主设备还是cache设备

(2) register_bdev 主设备注册：

   cached_dev_init : 初始化struct cached_dev中的先关结构

       disk包含了gendisk和

              cache_accounting包含了统计信息

              sb_* 用于管理super block io

          running表明了主设备的状态

              io* 用于记录顺序读写信息

   cached_dev_init ==>  bcache_device_init 会注册request queue, 并初始化gendisk

   cached_dev_init ==>bch_cached_dev_request_init注册request queue的回调

cached_dev_init==>bch_cached_dev_writeback_init 初始化writeback模块

 

（3） register_cache ==》 register_cache_set

       struct cache :

   每个cache设备与一个bch_allocator_thread关联，用于bucket的分配

       sb* : 用于访问cache设备的超级块

   cache_set: 一个cache set中可以有一个或多个cache 设备， bch_cache_set_alloc用于分配一个cache-set; bch_cache_sets是全局cache_set的list.

DECLARE_FIFO(long,free)[RESERVE_NR];用于记录可用的bucket, bcache用bucket来管理磁盘空间。

    最后会关联cache与cache_set

       ca->set = c; //ca为cache,c为cache_set

       ca->set->cache[ca->sb.nr_this_dev]= ca;

       c->cache_by_alloc[c->caches_loaded++]= ca;

 

(4）bch_cache_set_alloc

  首先从super block中获取bucket size, block_size等参数， 然后依次调用如下初始化函数：

              c->bio_split = bioset_create

              c->uuids = alloc_bucket_pages

       c-->moving_gc_wq =create_workqueue("bcache_gc")

              bch_journal_alloc(c) ；//journal 初始化

          bch_btree_cache_alloc(c) ；//建立btree node的分配缓存管理结构

          bch_open_buckets_alloc(c) ；//初始化c->data_buckets 一共为6个

          bch_bset_sort_state_init；//用于bset中的sort操作

 

（5） 关联主设备与cache设备bch_cached_dev_attach

   a. 主设别状态检察

   b. uuid检察，若uuid未分配则写分配uuid并写入bch_uuid_write

   c. bcache_device_attach关联cache 与主设备

   d. bch_cached_dev_run运行主设备

   e. 建立link文件bcache_device_link

 

bch_cached_dev_run

       a. add_disk(d->disk); 这样block层会知道有block设备增加了

    b. kobject_uevent_env 发送uevent

    c. 建立dev 与bcache链接文件

 

 

2.2 btree的基本数据结构

（1） bucket

  缓存设备会按照bucket大小划分成很多bucket，bucket的大小最好是设置成与缓存设备ssd的擦除大小一致，一般建议128k~2M+，默认是512k。bucket内空间是追加分配的，只记录当前分配到哪个偏移了，下一次分配的时候从当前记录位置往后分配。另外在选择bucket来缓存数据时有两个优先原则：1）优先考虑io连续性，即使io可能来自于不同的生产者；2）其次考虑相关性，同一个进程产生的数据尽量缓存到相同的bucket里

struct bucket {

       atomic_t       pin;

       uint16_t prio;/*每次hit都会增加，然后所有的bucket的优先级编号都会周期性地减少，不常用的会被回收，这个优先级编号主要是用来实现lru替换的*/

       uint8_t          gen;//generation，用来invalidate bucket用的。

 

       uint8_t          last_gc;/* Most out of date gen in the btree */

       uint16_t gc_mark;/* Bitfield used by GC. See below for field */

};

 

(2) bkey

bcache使用了b+tree, b+tree的node和叶节点指向的数据，最终存到bucket对应的cache disk中的位置。b+树节点中的关键结构就是bkey，bkey就是记录缓存设备缓存数据和后端设备数据的映射关系的，其结构如下。

struct bkey {

       __u64    high;

       __u64    low;

       __u64    ptr[];

};

/*

KEY_INODE:表示一个后端设备的id编号（后端设备在cache set中一般以bdev0，bdev1这种方式出现）

KEY_SIZE：表示该bkey所对应缓存数据的大小

KEY_DIRTY：表示该块缓存数据是否是脏数据

KEY_PTRS：表示cache设备的个数（多个ptr是用来支持多个cache设备的，多个cache设备只对脏数据和元数据做镜像）

KEY_OFFSET：bkey所缓存的hdd上的那段数据区域的结束地址

PTR_DEV：cache设备

PTR_OFFSET：在缓存设备中缓存的数据的起始地址

PTR_GEN：对应cache的bucket的迭代数（版本）

*/

由于key中记录了PTR_OFFSET，因此根据该信息能够得到bucket

static inlinesize_t PTR_BUCKET_NR(struct cache_set *c,

                               const struct bkey *k,

                               unsigned ptr) {

       return sector_to_bucket(c, PTR_OFFSET(k,ptr));

}

BEKY 的比较函数如下：

static__always_inline int64_t bkey_cmp(const struct bkey *l,

                                   const structbkey *r) {

       return unlikely(KEY_INODE(l) !=KEY_INODE(r))

              ? (int64_t) KEY_INODE(l) -(int64_t) KEY_INODE(r)

              : (int64_t) KEY_OFFSET(l) -(int64_t) KEY_OFFSET(r);

}

 

（3）  bset

一个bset是一个bkey的数组，在内存中的bset是一段连续的内存，并且以bkey排序的，内存中一个btree node只有4个bset。

struct btree {

       。。。。。。

       struct btree_keys       keys;

       。。。。。。。

}

struct btree_keys{

       。。。。。。

       /*

        *Sets of sorted keys - the real btree node - plus a binary search tree

        *

        *set[0] is special; set[0]->tree, set[0]->prev and set[0]->data point

        *to the memory we have allocated for this btree node. Additionally,

        *set[0]->data points to the entire btree node as it exists on disk.

        */

       struct bset_tree  set[MAX_BSETS]; //MAX_BESTS = 4

};

 

struct bset_tree {

       .......

       struct bset           *data;

}

struct bset {

       __u64                  csum;

       __u64                  magic;

       __u64                  seq;

       __u32                  version;

       __u32                  keys;

 

       union {

              struct bkey    start[0];

              __u64           d[0];

       };

};

 

(4) B+ Tree

 

bcache中以b+tree来维护索引，一个btree node里包含4个bset，每个bset中是排序的bkey。每个btree node以一个bkey来标识，该bkey是其子节点中所有bkey中的最大值，不同于标准的b+树那(父节点存放子节点的地址指针); bcache中的b+树中非叶子节点中存放的bkey用于查找其子节点（并不是存的地址指针），而是根据bkey计算hash，再到hash表中取查找btree node（mca_find函数实现）。叶子节点中的bkey存放的就是实际的映射了（根据这些key可以找到缓存数据以及在hdd上的位置）。

 

btree 叶节点的遍历： bch_btree_map_keys ==》

intbch_btree_map_keys(struct btree_op *op, struct cache_set *c,

                     struct bkey *from, btree_map_keys_fn*fn, int flags)

{

       return btree_root(map_keys_recurse, c, op, from, fn, flags); //遍历btree+进行查找

}

 

#definebtree_root(fn, c, op, ...)                                 \

({                                                             \

       int _r = -EINTR;                                      \

       do {                                                  \

              struct btree *_b = (c)->root;                         \

              bool _w = insert_lock(op, _b);                      \

              rw_lock(_w, _b, _b->level);                          \

              if (_b == (c)->root &&                                   \

                 _w == insert_lock(op, _b)) {                  \

                     _b->parent = NULL;                         \

                     _r = bch_btree_ ## fn(_b, op, ##__VA_ARGS__);     \

              }                                                \

              rw_unlock(_w, _b);                                \

              bch_cannibalize_unlock(c);                          \

              if (_r == -EINTR)                              \

                     schedule();                               \

       } while (_r == -EINTR);                                         \

                                                               \

       finish_wait(&(c)->btree_cache_wait,&(op)->wait);         \

       _r;                                                    \

})

 

static intbch_btree_map_keys_recurse(struct btree *b, struct btree_op *op,

                                  struct bkey *from, btree_map_keys_fn *fn,

                                  int flags) {

       。。。。。

       bch_btree_iter_init(&b->keys,&iter, from);

 

       while ((k =bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) {

              ret = !b->level

                     ? fn(op, b, k) //已经到页节点了

                     : btree(map_keys_recurse,k, b, op, from, fn, flags); //非页节点

              from = NULL;

 

              if (ret != MAP_CONTINUE)

                     return ret;

       }

 

       if (!b->level && (flags &MAP_END_KEY))

              ret = fn(op, b,&KEY(KEY_INODE(&b->key),

                                 KEY_OFFSET(&b->key), 0));

 

       return ret;

}

 

#define btree(fn,key, b, op, ...)                                  \

({                                                             \

       int _r, l = (b)->level - 1;                                 \

       bool _w = l <= (op)->lock;                             \

       struct btree *_child =bch_btree_node_get((b)->c, op, key, l, _w);\

       if (!IS_ERR(_child)) {                                     \

              _child->parent = (b);                              \

              _r = bch_btree_ ## fn(_child, op, ##__VA_ARGS__);      \

              rw_unlock(_w, _child);                                  \

       } else                                                      \

              _r = PTR_ERR(_child);                                   \

       _r;                                                    \

})

 

struct btree*bch_btree_node_get(struct cache_set *c, struct btree_op *op,

                             struct bkey *k, int level, bool write) {

。。。。。。

retry:

       b = mca_find(c, k);

 

       if (!b) { //若key 对应的btree不存在，则先申请分配一个bucket,并

              mutex_lock(&c->bucket_lock);

              b = mca_alloc(c, op, k, level);

              mutex_unlock(&c->bucket_lock);

              。。。。。。

              bch_btree_node_read(b);

 

       } else {

              rw_lock(write, b, level);

              if (PTR_HASH(c, &b->key) !=PTR_HASH(c, k)) {

                     rw_unlock(write, b);

                     goto retry;

              }

       }

       。。。。。。

       return b;

}

 

static structbtree *mca_find(struct cache_set *c, struct bkey *k)

{

       struct btree *b;

 

       rcu_read_lock();

       hlist_for_each_entry_rcu(b, mca_hash(c,k), hash) //根据key的hash从hlist中取出下一个btree节点

              if (PTR_HASH(c, &b->key) ==PTR_HASH(c, k))

                     goto out;

       b = NULL;

out:

       rcu_read_unlock();

       return b;

}

为了提高性能， 使用了cache_set中有btree的缓存

       struct list_head   btree_cache;

       struct list_head   btree_cache_freeable;

       struct list_head   btree_cache_freed;

如果btree不存在时，先从cache_set中的btree_cache中分配，失败则最终从kzalloc中分配。（相关机制较简单， 不在详细分析 mca_bucket_alloc, mca_data_alloc, mca_reap）

 

bch_btree_iter_init和bch_btree_iter_next_filter为btree的访问迭代器，其基本工作原理就是

（1）bch_btree_iter_init 根据要search的bkeys,遍历btree中的bset, bset中的bkey.然后将满足条件的bkey集合以{bkey_start, bkey_end}元素形式添加到heap中。 heap的排序比较函数为：btree_iter_cmp

static inline boolbtree_iter_cmp(struct btree_iter_set l, struct btree_iter_set r) {

       return bkey_cmp(l.k, r.k) > 0;

}

bch_btree_iter_init==> __bch_btree_iter_init  {

       for (; start <= bset_tree_last(b);start++) {

              ret = bch_bset_search(b, start,search);

              bch_btree_iter_push(iter, ret,bset_bkey_last(start->data));

       }

}

 

(2) bch_btree_iter_next_filter则根据heap中的bkey范围，每次返回一个bkey.

 

 

3.底层IO

3.1 Closure

bcache里的closure就是一个引用计数来管理回调或对象析构的机制

structclosure {

         union {

                   struct {

                            structworkqueue_struct *wq;

                            struct task_struct   *task;

                            struct llist_node       list;

                            closure_fn                  *fn;

                   };

                   struct work_struct  work;

         };

 

         struct closure           *parent; //父closure对象

         atomic_t           remaining;

};

当调用closure_get后，需要调用closure_put来减少引用计数。 closure_init后引用计数被设为1； closuer实现较为简单，下面只分析几种常用的使用方法.

(1) Basicusage

 foo_endio(struct bio *bio, int error)  {

        closure_put(cl);

  }

 

  closure_init(cl); // ref to 1

 

  do_stuff();

  closure_get(cl); //ref to 2

  bio1->bi_endio = foo_endio;

  do_more_stuff();

  closure_get(cl); ref to 3

  bio2->bi_endio = foo_endio;

 

  bio_submit(bio1);

  bio_submit(bio2); //当bio1 bio2完成后ref set to 1

 

  continue_at(cl, complete_some_read,system_wq); ref--, 如果ref == 0则complete_some_read在system_wq中执行。

 

continue_at如果wq参数为0，则同步执行。

 

上面的例子是异步执行方法，它还支持同步应用: A __closure_wait(ref++), B closure_sync会使调用task让出cpu,; C __closure_wake_up(ref--)能唤醒等待的task

 

最后closure还支持parent机制， closure_init， 如果parent不为NULL, 会closure_get(parent)

closure_put_after_sub时， 如果当前ref==0, 则closure_put(parent)

3.2 基本io.c

bch_bio_max_sectors: 合并bio中的请求，并返回一次最大传输长度

bch_generic_make_request:根据设备能支持一次最大传输长度， 拆分传输。

bch_bbio_alloc： 分配一个对cache设备的bio,

                   其中bio->bi_bdev            = PTR_CACHE(c, &b->key,0)->bdev;

bch_submit_bbio提交对cache设备的io

bch_bbio_endio对cache设备的io的回调

bch_bio_map： 对bio中的bio_vec分配物理地址， 当base参数不为0时执行如下代码：

                   bv->bv_page =is_vmalloc_addr(base)

                                              ? vmalloc_to_page(base)

                                              : virt_to_page(base);

 

 

下面时对block层bio操作的小结：

1. bio_alloc_pages:为bio中的每个bio_vec分配物理内存页

2. bio_initbio初始化； bio_reset reinit bio

3.bio_sumit异步提交bio；submit_bio_wait同步提交

4.拆分bio: bio_next_split

5. bioset_create:create bioset, bio_alloc_bioset: allocate a bio for I/O according to bioset