BCache源码浅析之三数据读写流程

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

4. 数据读写流程与B+Tree

cached_dev_make_request:

a. 如果device没有对应的缓存设备，则直接将向主设备提交bio,并返回.

b.如果有cache device 根据要传输的bio, 用search_alloc建立struct search s;

c. 调用check_should_bypass  check是否应该bypass这个bio,

d.根据读写分别调用cached_dev_read或cached_dev_write

 

4.1 bypass检查check_should_bypass

 (1) 若bio为discard 或gc 数量大于CUTOFF_CACHE_ADD，则bypass为true

 (2) 主设备设备禁用cache,  则bypass为true

 (3) 传输的sector 为按block对齐，则bypass为true

 (4) cache设备处于拥塞状态(bch_get_congested)，则bypass为true

 (5) 根据历史判断是否为sequence io, 且sectors >= dc->sequential_cutoff(default为4MB)则bypass为true

 

4.2数据读取流程cached_dev_read

staticvoid cached_dev_read(struct cached_dev *dc, struct search *s) {

         struct closure *cl = &s->cl;

 

         closure_call(&s->iop.cl,cache_lookup, NULL, cl);

         continue_at(cl,cached_dev_read_done_bh, NULL);

}

cache_lookup调用

ret = bch_btree_map_keys(&s->op,s->iop.c,

                                      &KEY(s->iop.inode,bio->bi_iter.bi_sector, 0),

                                      cache_lookup_fn, MAP_END_KEY);

来遍历b+tree叶子节点，来查找bkey: KEY(s->iop.inode,bio->bi_iter.bi_sector, 0); 当遍历到页节点时btree_map_keys_fn 函数会被调用， 这里为cache_lookup_fn.

 

cache_loopup_fn:

a. 若带搜索的key比当前key小，则返回MAP_CONTINUE让上层搜索下一个key.

b. 若key不在b+tree或key中的数据只有部分在b+tree则调用s->d->cache_miss(b, s, bio, sectors);

c. 如果数据已在缓存中(bkey在b+tree中，且key中的数据范围也完全在缓存中)了， 则直接从缓存disk读取， 命中后需将bucket的prio重新设为：PTR_BUCKET(b->c, k, ptr)->prio = INITIAL_PRIO（32768U）

 

caceh_miss== cached_dev_cache_miss

a. 当miss函数重入(s->cache_miss)或read bypass时， 直接从主设备读取

b. 当读取非元数据且预读机制未禁止时，计算能预读的sector数

c. s->iop.replace_key= KEY(s->iop.inode, //计算要向b+tree添加或替换的key

                                      bio->bi_iter.bi_sector + s->insert_bio_sectors,

                                      s->insert_bio_sectors);

         bch_btree_insert_check_key(b,&s->op, &s->iop.replace_key)//向b+tree提交key

d.从主设备读取数据，并将bio记录到iop.bio中以便上层cached_dev_read_done_bh 将数据加到缓存设备:          s->cache_miss          = miss;

                            s->iop.bio        = cache_bio;

 

cached_dev_read_done_bh:

a.cached_dev_read_done:

当s->iop.bio不为0时， 表明有新的数据要添加到管理缓存的b+tree中， 所以首先bio_copy_data(s->cache_miss,s->iop.bio) 将数据拷贝到cache_missbio中，然后调用bch_data_insert将数据更新到cache设备中

 

b. cached_dev_bio_complete:释放struct search

 

bch_data_insert: {

bch_keylist_init(&op->insert_keys);//初始化keylist, keylist是一种双端队列结构

         bio_get(op->bio);

         bch_data_insert_start(cl);

}

 

bch_data_insert_start：该函数要考虑cache disk存储区域的overlap,下面是overlap的case:

  当需要在cache disk中分配新的存储区域时需要调用bch_alloc_sectors， 从bucket中分配空间。 然后向cachedisk发起bio请求bch_submit_bbio(n, op->c, k, 0);。

  在添加数据与处理overlap时发现要改变现有b+tree的key结构，那么调用如下代码：

                   k = op->insert_keys.top; bkey_init(k);

                   SET_KEY_INODE(k,op->inode);

                   SET_KEY_OFFSET(k,bio->bi_iter.bi_sector);需要重新更新btree

                   if (op->writeback)

                            SET_KEY_DIRTY(k,true);

                   bch_keylist_push(&op->insert_keys);

最后bch_data_insert_start==> bch_data_insert_keys来将op->insert_key更新到b+tree

bch_data_insert_keys首先对插入的case 调用bch_journal来增加journal(第8节分析该流程).然后调用bch_btree_insert，遍历要插入了keylist, 对每项做：bch_btree_map_leaf_nodes(&op.op, c, &START_KEY(keys->keys),btree_insert_fn);

btree_insert_fn将调用bch_btree_insert_node来操作b+tree.

 

4.3数据写入流程cached_dev_write

cached_dev_write：

a. bch_keybuf_check_overlapping查看是否和已有要writeback的区域有重合，若有，取消当前区域的bypass

b.若bio为REQ_DISCARD，则采用bypass

c. should_writeback做writeback检测(第7节分析)

d. 下面分三种case处理：

         (1) bypass: 则直接s->iop.bio = s->orig_bio（赋值为原disk io)

    (2) 开启writeback, 则需要bch_writeback_add(dc);s->iop.bio = bio; 并不需要将数据立即写回主设备，

    (3) s->iop.bio = bio_clone_fast(bio,...);closure_bio_submit(bio, cl, s->d); 将数据写回主设备

d. closure_call(&s->iop.cl,bch_data_insert, NULL, cl); 向B+tree更新节点

 

4.4 B+Tree的Insert Node操作

  第4.2节中分析到了bch_btree_insert_check_key和bch_btree_insert_node函数，本节通过他们来分析B+Tree的Insert与Replace操作。

  bch_btree_insert_check_key 的关键代码如下：

                   bch_keylist_add(&insert,check_key);

                  ret= bch_btree_insert_node(b, op, &insert, NULL, NULL);

由此可见， 最重要的代码是bch_btree_insert_node。 下面时该函数的定义：

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

                                      struct keylist *insert_keys, 要插入的keylist

                                      atomic_t *journal_ref, //journal信息

                                      struct bkey *replace_key) //要replace的key {

                   .....

         if (bch_keylist_nkeys(insert_keys) >insert_u64s_remaining(b)) {

                   mutex_unlock(&b->write_lock);

                   goto split; //如果btree空间不够，则需要进行拆分操作

         }

                  if(bch_btree_insert_keys(b, op, insert_keys, replace_key)) {

                            if (!b->level) //对于页节点不立即更新，仅标记为dirty

                                     bch_btree_leaf_dirty(b, journal_ref);

                            else

                                     bch_btree_node_write(b, &cl); //对于非页节点，更新完后直接写入

         }

         closure_sync(&cl); //等待btree写入完成

         return 0;

split:

         int ret = btree_split(b, op,insert_keys, replace_key);

}

 对于页节点执行：

bch_btree_leaf_dirty：

a.若node未dirty 则延迟调用b->work;(INIT_DELAYED_WORK(&b->work, btree_node_write_work);)

b. 已dirty, 如果bset的大小已经很大则bch_btree_node_write(b,null);注意对于多数情况并不会立即更新node以提高性能。 这时就靠前面的bch_journal,来记录更新的日志来保证更改不会丢失了。

 

对于非页节点执行：

bch_btree_node_write ==> __bch_btree_node_write 清除dirty并调用do_btree_node_write，更新node

 

bch_btree_insert_keys：将分三种情况实际更新b+tree

         case 1: 要插入key < btree->key, 则直接调用btree_insert_key插入

         case 2: 和btree已有key部分重合,计算不重合部分插入

                                               bkey_copy(&temp.key,insert_keys->keys);

                                               bch_cut_back(&b->key,&temp.key);

                                     bch_cut_front(&b->key,insert_keys->keys);

                                     ret |= btree_insert_key(b,&temp.key, replace_key);

         case 3: 完全包含与btree->key则不插入

 

btree_insert_key==》  bch_btree_insert_key 该函数首先遍历检察btree中的bset是否已排序；若为排好序排序就调用bch_bkey_try_merge。 最后然后调用bch_bset_insert(b, m, k)执行b+tree添加或replace操作.

 

btree_split:

a. 复制一个btree node        n1= btree_node_alloc_replacement(b, op);//里面会从bucket分配

b.计算是否需要分裂split = set_blocks(btree_bset_first(n1),

                               block_bytes(n1->c)) > (btree_blocks(b)* 4) / 5;

下面时该函数split为true部分的流程及分析：

         n2 = bch_btree_node_alloc(b->c, op,b->level);

 

                   if (!b->parent) { //如果b已经是根节点，需要分配另一个节点作为新的根节点

                            n3 =bch_btree_node_alloc(b->c, op, b->level + 1);

                   }

                    //将要插入的key先插入到新建立的n1中

                   bch_btree_insert_keys(n1, op,insert_keys, replace_key);

      

                  建立bset的search  tree，这里代码未贴出来........

 

                   bkey_copy_key(&n2->key,&b->key);

        将n2的key 加入到parent_key keylist中以便后面添加里面的key

                   bch_keylist_add(&parent_keys,&n2->key);            bch_btree_node_write(n2,&cl);

接下来：

         bch_keylist_add(&parent_keys,&n1->key);

         bch_btree_node_write(n1, &cl);

         if (n3) { //若r3存在，将他设为新的root

                   bkey_copy_key(&n3->key,&MAX_KEY);

                   bch_btree_insert_keys(n3, op,&parent_keys, NULL); //将parent_keys提交的n3中

                   bch_btree_node_write(n3,&cl);

                   closure_sync(&cl);

                   bch_btree_set_root(n3);

         } else if (!b->parent) {

                   closure_sync(&cl);

                   bch_btree_set_root(n1);//root不需要split的情况，将n1设为root，

         } else {

                   closure_sync(&cl);

                   make_btree_freeing_key(b,parent_keys.top);

                   bch_keylist_push(&parent_keys);

                   //将parent_keys中的key提交到b->parent中

                   bch_btree_insert_node(b->parent,op, &parent_keys, NULL, NULL);

                   BUG_ON(!bch_keylist_empty(&parent_keys));

         }

 

         btree_node_free(b); //b无论走哪个分支，都不在需要所以释放， 对于上面的case2,bucket的prio由于重建，所以自动被更新了。