git clone https://evilpiepirate.org/git/bcachefs-tools.git

git clone https://evilpiepirate.org/git/bcachefs.git

struct btree_node {           | struct btree_node_entry {
  struct bch_sum     csum;    |   struct bch_csum csum;
  __le64             magic;   |
  __le64             flags;   |
                              |
  struct bpos        min_key; |
  struct bpos        max_key; |
                              |
  /* NOT USED ANYTMORE */     |
  struct bch_extent_ptr _ptr; |
                              |
  struct bkey_format format;  |
                              |
  union {                     |   union {
  struct bset keys;           |   struct bset keys;
  struct {                    |   struct {
    __u8   pad[22];           |     __u8   pad[22];
    __le16 u64s;              |     __le16 u64s;
    __u64  _data[0];          |     __u64  _data[0];
  };                          |   };
  };                          |   };
} __packed __aligned(8);      | } __packed __aligned(8);

struct bpos { __u64 inode; __u64 offset; __u32 snapshot; }

struct bkey { __u8 u64s; __u8 format:7, needs_whiteout:1;
              __u8 type  __u8 pad[1];   struct bversion version;
              __u32 size;               struct bpos p;
                                     // ^^^^^^^^^^^^^
} __packed __aligned(8);

<---------- 256KB ----------->
------------------------------
||||||||||||****           ***
------------------------------
           ^               ^
           |               b->whiteout_u64s
           b->written

// btree_update_interior.h

static inline void push_whiteout(struct bch_fs *c, struct btree *b,
                                 struct bpos pos) {
                               //            ^^^
  // 依据 bpos 构造一个 bkey_packed，变量名叫 k
  // k.type = KEY_TYPE_deleted;
  // k.p = pos;
  // k.needs_whiteout = true;
  ...

  b->whiteout_u64s = k.u64s;

  bkey_copy( ((u64 *)((void *)b->data + 256 * 1024)) - b->whiteout_u64s,
             &k );
}

void __bch2_btree_node_write(struct bch_fs *c, struct btree *b, unsigned flags) {
  struct bset_tree *t;
  struct sort_iter sort_iter;

  unsigned bytes = !b->written ? sizeof(struct btree_node)
                    : sizeof(struct btree_node_entry);

  for (t = b->set; t < b->set + b->nsets; t++) {
    struct bset *i = (u64 *) b->data + 1 + t->data_offset;

    if ((void *) i < (void *) b->data + (b->written * 512))
      continue; // 已写入磁盘，跳过

    bytes += le16_to_cpu(i->u64s) * sizeof(u64);

    // bset 内的 bkey 本身是排序
    // 几个 bset 的 bkey 统一排序，需通过 sort_iter 的移动
    // 此处：先加入到 sort_iter 中
    sort_iter_add(&sort_iter,
                  i->start, // 当前 bset 所指向的第一个 bkey
                  (u64 *) i->start + i->u64s);
  }

  // bch2_varint_decode may read up to 7 bytes past the end of the buffer:
  bytes += 8

  bch2_sort_whiteouts(c, b); // 对 “被 whiteout 掉 bkeys” 进行排序
  sort_iter_add(&sort_iter,
                (u64 *)((void *) b->data + 256 * 1024) - b->whiteout_u64s,
                (void *) b->data + 256 * 1024);

  bytes += b->whiteout_u64s * sizeof(u64);
  bytes = round_up(bytes, block_bytes(c) /* 磁盘的 block size */);

  data = btree_bounce_alloc(..., bytes, ...);

  // 接续上文
  struct btree_node_entry *bne = data;
  struct bset *i = &bne->keys;

  // 初始化 bset 头信息，例如：
  //   bne->keys = b->data->keys;
  //   i->journal_seq = cpu_to_le64(seq);
  //   i->u64s = 0;

  // 通过 sort_iter 进行排序，并将排序结果写入到 i->start（实际上就是前述
  // data 指向的新分配空间中）

  // 排序中，使用了 sort_keys_cmp 这个函数来定义排序规则
  unsigned u64s = bch2_sort_keys(i->start, &sort_iter, false);
  i->u64s += u64s;

  // 排序后，多个相同键值的 bkey 将被排序靠后的 bkey 合并
  //  特别指出的是：deleted key 排序靠后

  // 续接上文
  unsigned bytes_to_write = (void *) ((u64 *) i->start + i->u64s) - data;
  unsigned sectors_to_write = round_up(bytes_to_write,
                                       block_bytes(c) /* 磁盘的 block size */)
  sectors_to_write /= 512;

  struct bio *bio = bio_alloc_bioset(NULL,
                        buf_pages(data, sectors_to_write * 512),
                        REQ_OP_WRITE|REQ_META,
                        GFP_NIO, &c->btree_bio);

  struct btree_write_bio *wbio = container_of(bio, struct btree_write_bio, wbio.bio);

  // 在下面函数中，bio->bi_iter.bi_size = sectors_to_write * 512;
  bch2_bio_map(bio, data, sectors_to_write * 512);

  wbio->sector_offset = b->written;

  bkey_copy(&wbio->key, bkey);
  
  b->written += sectors_to_write;
  if (wbio->key.k.type == KEY_TYPE_btree_ptr_v2)
    bkey_i_to_btree_ptr_v2(&wbio->key)->v.sectors_written = cpu_to_le16(b->written);

  INIT_WORK(&wbio->work, btree_write_submit);
  queue_work(c->io_complete_wq, &wbio->work);

void btree_write_submit(struct work_struct *work) {
  struct btree_write_bio *wbio = container_of(work, struct btree_write_bio, work);

  struct bch_extent_ptr *ptr;
  bkey_copy(&tmp.k, &wbio->key); // 拷贝出一个 tmp 的 key

  bkey_for_each_prt(bch2_bkey_ptrs(bkey_i_to_s(&tmp.k)), ptr)
    ptr->offset += wbio->sector_offset;
  //^^^^^^^^^^^

  bch2_submit_wbio_replicas(&wbio->wbio, ..., &tmp.k, false);
}

void bch2_btree_node_read(struct bch_fs *c, struct btree *b, bool sync) {
  struct extent_ptr_decoded pick;

  // 对 b->key 的 value 进行解析，解析结果保存在类型为 struct extent_ptr_decoded
  // 的变量中


  // value 可能包含多个 struct bch_extent_ptr，对应不同磁盘上的副本
  // 筛选出一个较佳的磁盘，随后访问该磁盘上的副本
  int ret = bch2_bkey_pick_read_device(c, bkey_i_to_s_c(&b->key),
                                       NULL, &pick);

  // 续接上文
  struct bio *bio = bio_alloc_bioset(NULL,
                        buf_pages(b->data, 256 * 1024),
                        REQ_OP_READ|REQ_SYNC|REQ_META,
                        GFP_NOIO,
                        &c->btree_io);
  struct btree_read_bio *rb = container_of(bio, struct btree_read_bio, bio);
  INIT_WORK(&rb->work, btree_node_read_work);

  bio->bi_iter.bi_sector = pick.ptr.offset; // bch_extent_ptr::offset
  bio->bi_end_io = btree_node_read_endio;
  bch2_bio_map(bio, b->data, 256 * 1024); // bio->bi_iter.bi_size = 256 * 1024;

  submit_bio(bio);
}

void btree_node_read_endio(struct bio *bio) {
  struct btree_read_bio *rb = container_of(bio, struct btree_read_bio, bio);
  ...
  queue_work(c->io_complete_wq, &rb->work);
}

int bch2_btree_node_read_done(struct bch_fs *c, struct bch_dev *ca, struct btree *b,
                              bool have_retry, bool *saw_error) {

  // 参见 super.c：bch2_fs_alloc() 函数，关于 fill_iter 这个 mempool_t
  // 分配的 iter 大小为 sizeof(struct sort_iter) 
  //                    + (256 * 1024 / block_bytes(c) + 1) * 2 * sizeof(struct sort_iter_set)
  struct sort_iter *iter = mempool_alloc(&c->fill_iter, GFP_NOIO);

  sort_iter_init(iter, b);
  iter->size = (256 * 1024 / block_bytes(c) + 1) * 2;

  // 即 bch_btree_ptr_v2::sectors_written
  unsigned ptr_written = btree_ptr_sectors_written(&b->key);

  b->written = 0;
  while (b->written < ptr_written) {
    struct bset *i;
    unsigned sectors;

    bool first = !b->written;

    // 读取 bset
    if (first) {
      i = &b->data->keys;

      sectors = /* 包括 btree_node 头、bset 头
                 * 以及 bset::u64s，向上对齐到磁盘的 block size */ ;
    } else {
      struct btree_node_entry *bne = (void *) b->data + b->written * 512;
      i = &bne->keys;

      sectors = /* 包括 btree_node 头、bset 头
                 * 以及 bset::u64s，向上对齐到磁盘的 block size */ ;
    }

    b->written += sectors;

    sort_iter_add(iter, i->start, (u64 *) i->start + i->u64s);
  }

  // 续接上文
  struct btree_node *sorted = btree_bounce_alloc(c, 256 * 1024, ...);
  sorted->keys.u64s = 0;

  // 将全部磁盘上读取的 bset，其 bkey 进行排序
  // 留意，排序中，使用了 key_sort_fix_overlapping_cmp 这个函数来定义排序规则
  // - 对于 key 值相同的，序列化中偏移大的，序号大
  // - 实际上是写磁盘晚的，序号大，最终生效
  //
  // 并将排序结果存到 sorted->keys
  b->nr = bch2_key_sort_fix_overlapping(c, &sorted->keys, iter);
  
  unsigned u64s = le16_to_cpu(sorted->keys.u64s);
  *sorted = *b->data;
  sorted->keys.u64s = u64s;
  // sorted 指向内存区域，成为 b->data 所指向
  swap(sorted, b->data);

  b->set[0].data_offset = (u64 *) i - 1 - (u64 *) b->data;
  b->set[0].end_offset = (u64 *) i->start + i->u64s;

  // 反序列化后，多个 bsets 合并成在内存中的一个 bset
  b->nsets = 1;  

  // 在内存中，建立二叉搜索树
  bch2_bset_build_aux_btree(b, &b->set[0], false);
}