Btrfs之NV（一）：COW_lookup_extent_backref

Btrfs采用了两种方法：COW和log_root，保证磁盘能够在断电之后保证数据的一致性，以防止super或者meta_data数据被破环而导致整个文件系统的崩溃。

COW是Btrfs Non-volatile(NV)的主要方式,其主要思路是：多个线程可以在一个trans内并发地对整个Btrfs进行如下图所示的COW修改；当所有的线程都退出trans时，通过btrfs_commit_transaction将所有线程cow block落盘，落盘完成后将管理root的super落盘(super的落盘也是NV，btrfs_commit_transaction中会讲解)。就这样将big_size data/meta_data NV转换为small_size super的NV,从而完成了整个Btrfs NV。

Copy on Write

当线程对btrfs的结构有所修改时，在btrfs_search_slot时会将cow标志置上，线程在搜索要修改的结构时就会将整个path COW，然后在cow block上进行修改而不改变原始的block，保证原始block数据的一致性。

static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
			     struct btrfs_root *root,
			     struct extent_buffer *buf,
			     struct extent_buffer *parent, int parent_slot,
			     struct extent_buffer **cow_ret,
			     u64 search_start, u64 empty_size)
{
	... ...
	/*
	功能分析：为buf申请新的eb(cow)，并初始化cow(复制buf，并更新gen)。具体申请eb参考《Btrfs之RAID(一)：Chunk抽象和使用》，会增加root/parent对eb的引用
	*/
	cow = btrfs_alloc_tree_block(trans, root, parent_start,
			root->root_key.objectid, &disk_key, level,
			search_start, empty_size);
	... ...
	copy_extent_buffer(cow, buf, 0, 0, cow->len);
	btrfs_set_header_bytenr(cow, cow->start);
	btrfs_set_header_generation(cow, trans->transid);
	btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
	... ...
	/*
	功能分析：更新cow，buf对child的引用
	函数分析：
	1.btrfs_lookup_extent_info会查看对extent_item总ref数量(ref和delay_ref)，和其索引的flag(是否是full_ref,其root相对于源root发生改变)
	2.索引更新
		1.如果源buf有多个ref，不需要释放buf对其child的引用，只需要增加cow对其child的索引
			-如果cow继承buf的owner，cow继承buf中root对child的引用(递增buf的full_ref)
			-如果cow没继承buf的onwer，cow现在单独被root引用(cow只复制一条路径,cow的onwer将不同于buf，在__btrfs_cow_block会重新被设置，)，所以会递增对child的root引用
		2.如果源buf是由一个ref
			1.如果是full_ref，需要删除buf对child的索引，但是递增cow对child的索引
			2.如果不是full_ref，是root对child进行索引,不区分是buf还是cow，所以不做处理
		3.如果cow的root是relocate_root,都会将cow child的引用转换成full_ref
	3.btrfs_inc_ref：增加对其child的索引，如果最后一个参数置0，表示增加root索引；如果是1表示增加parent对child索引。btrfs_dec_ref则是相应递减其索引，两者都是调用__btrfs_mod_ref
	4，__btrfs_mod_ref不仅会更新对child tree_block的索引，还会更新对child extent_data的索引
	*/
	ret = update_ref_for_cow(trans, root, buf, cow, &last_ref);
	... ...
	/*
	功能分析：参考《Btrfs之RAID（三）：RAID应用》中的do_relocation。
	函数分析：
	1.更新node.eb，防止在do_relocation时被多个root引用的eb被重复cow
	2.设置node.pending，表示需要向上遍历其所有的parent并更新索引
	3.对于level 0,在UPDATE_DATA_PTRS时会通过replace_file_extents
		-get_new_location获取extent_data relocate的段(记录在rc.data_inode中，offset为在blockgroup中的偏移，指向新relocate的extent_data)
		-更新dist_bytenr(new_bytenr)，并增加对new_bytenr的索引，递减对bytenr的索引
	*/
	if (test_bit(BTRFS_ROOT_REF_COWS, &root->state)) {
		ret = btrfs_reloc_cow_block(trans, root, buf, cow);
	... ...
	}
	... ...
	/*
	功能分析：更新cow在parent中的索引(parent已经在buf之前进行了cow)
	*/
	if (buf == root->node) {
		... ...
		rcu_assign_pointer(root->node, cow);

		btrfs_free_tree_block(trans, root, buf, parent_start,
				      last_ref);
		free_extent_buffer(buf);
		... ...
	}
	} else {
		... ...
		btrfs_set_node_blockptr(parent, parent_slot,
					cow->start);
		btrfs_set_node_ptr_generation(parent, parent_slot,
					      trans->transid);
		... ...
		btrfs_free_tree_block(trans, root, buf, parent_start,
				      last_ref);
	}
	... ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

btrfs_commit_transaction

多个线程在一个trans中对Btrfs进行更新时，更改的是cow block，而且对于cow block的索引都是以delayed_ref形式存在，所以此时磁盘上的内容还是原有block和对原有block的ref。当所有的线程都退出trans时，btrfs_commit_transaction会将cow block和其delayed_ref落盘，并且管理root的super也进行NV落盘，实现整个Btrfs NV。

int btrfs_commit_transaction(struct btrfs_trans_handle *trans,
			     struct btrfs_root *root)
{
	/*
	功能分析：将root下所有的delayed_ref落盘
	函数分析：
	1.__btrfs_run_delayed_refs会将每个extent对应的delayed_ref进行合并，并通过run_one_delayed_ref将tree_block和extent_data的ref落盘
	2.随后遍历delayed_refs，将所有head删掉
	*/
	ret = btrfs_run_delayed_refs(trans, root, 0);
	... ...
	/*
	功能分析：如果之前btrfs_alloc_chunk向dev申请chunk，并通过block_group管理，这里会将block_group，dev_extent,chunk信息落盘
	*/
	if (!list_empty(&trans->new_bgs))
		btrfs_create_pending_block_groups(trans, root);
	ret = btrfs_run_delayed_refs(trans, root, 0);
	... ...
	/*
	功能分析：如果没有dirty_bg在刷写，通过btrfs_start_dirty_block_groups将dirty_bg刷写到磁盘上
	函数分析：btrfs_start_dirty_block_groups
	1.btrfs_create_pending_block_groups刷写btrfs_alloc_chunk添加的new_bgs
	2.遍历dirty_bgs，
		- btrfs_wait_cache_io将等待之前刷写的block_group free_space信息落盘
		
		- cache_save_setup会将整个inode清空(并没有落盘，清空的是inode内存结构和添加extent_data delayed_ref),并通过btrfs_prealloc_file_range_trans为inode申请要写的extent
		
		- btrfs_run_delayed_refs将delayed_ref落盘
		注：这里的delayed_ref落盘也是cow，只要super不落盘，还是索引原有的root，这个ref不会生效
		
		- btrfs_write_out_cache delalloc free_space和bitmap信息，并通过btrfs_fdatawrite_range落盘到inode中
		
		- write_one_cache_group对block_gruop信息cow，并标记dirty
		注：在alloc_extent_buffer中eb.page是属于fs_info.btree_inode.i_mapping，所有的meta_data都是属于btree_inode，最后meta_data通过btree_inode统一落盘
		
		- btrfs_wait_cache_io等待所有的free_space信息落盘完成
	*/
	if (!test_bit(BTRFS_TRANS_DIRTY_BG_RUN, &cur_trans->flags)) {
		if (!test_and_set_bit(BTRFS_TRANS_DIRTY_BG_RUN,
				      &cur_trans->flags))
			run_it = 1;
		... ...
		if (run_it)
			ret = btrfs_start_dirty_block_groups(trans, root);
	}
	... ...
	/*
	1.如果trans在TRANS_STATE_COMMIT_START状态(**刷写delalloc inode数据,ordered inode数据**)，其他线程不能commit，只能等待commit完成
	2.btrfs_start_delalloc_flush触发异步刷写所有的fs_info.delalloc_roots.delalloc_inodes，并等待
                注：1.这里主要是刷写data(btrfs_run_delalloc_work)
                 	2.刷写的是设置为EXTENT_DELALLOC page,也会在mapping_tree中set_page_dirty
                  	3.用户在写数据时，如果不是direct_io或者sync(log_root)，会通过__btrfs_buffered_write暂时将数据复制到mapping_tree，并通过btrfs_dirty_pages设置为delalloc，并在btrfs_set_bit_hook中加入到root.delalloc_inodes中。
	3.btrfs_run_delayed_items将delayed_root中记录inode数据结构的修改在内存中实现，并btrfs_mark_buffer_dirty，之后通过btree_inode落盘meta_data
	4.btrfs_wait_delalloc_flush等待所有ordered_extent落盘(用户对磁盘的写请求都会通过btrfs_add_ordered_extent链接到root中，在submit_one_bio返回后，通过btrfs_finish_ordered_io将ordered_extent删除)
	
	
	5.trans状态变换为TRANS_STATE_COMMIT_DOING(**更新root，再向上依次更新tree_root chunk_root**)
	6.create_pending_snapshots遍历btrfs_ioctl_snap_create中创建的pending_snapshots链表，通过btrfs_copy_root创建snapshot，并插入到指定的dir中
	7.commit_fs_roots更新fs_roots_radix上标记为BTRFS_ROOT_TRANS_TAG的root。
	  - 释放log_root,更新relocate_root,更新orphan，更新root
	  - btrfs_save_ino_cache将root的objectid free_space写入磁盘
	  注：block_group的free_space信息存储在tree_root.free_ino_ctl中，每个单独的root.free_ino_ctl存储的是objectid
	8.btrfs_free_log_root_tree释放log_root_tree上所有的block，后续会清空super_copy中的log_root
	9.commit_cowonly_roots处理tree_root
		-btrfs_setup_space_cache储存tree_root中的block_group free_space信息
		-刷新dirty_cowonly_roots上的root和新的tree_root链接，并等待所有的block_gruop刷写完成
	10.switch_commit_roots更新root.commit_root
	
	
	11.trans状态变换为TRANS_STATE_UNBLOCKED(**落盘meta_data/eb/tree_block，最后落盘super**)，此时其他线程无法加入trans
	12.btrfs_write_and_wait_transaction将btree_inode中标记为dirty的page(dirty eb,也在cow时链接到trans.dirty_pages树中)刷写到磁盘,并等待刷写完成
	13.write_ctree_super会让第一个supper mirror以FUA(force unit access，不落盘不返回)，其他mirror以lazy mode方式落盘。这样supper mirror的顺序写保证了super NV(如果第一个mirror写过程中掉电导致数据不一致，还有其他两个mirror；如果其他两个mirror写的时候掉电导致数据不一致，还有第一个mirror)
	14.更新root->fs_info->last_trans_committed 
	*/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

Dirty数据落盘

tree_block在cow时在fs_info.btree_inode.mapping中标记为dirty，而data在用户通过__btrfs_buffered_write写数据时在对应的inode.mapping中标记dirty。在btrfs_commit_transaction时会将dirty tree_block和data通过do_writepages落盘。

对于tree_block，只需要通过btree_write_cache_pages直接提交bio；但是对于普通data，需要保证数据的一致性，extent_write_cache_pages提供了inode数据的cow落盘。

static int extent_write_cache_pages(struct extent_io_tree *tree,
			     struct address_space *mapping,
			     struct writeback_control *wbc,
			     writepage_t writepage, void *data,
			     void (*flush_fn)(void *))
{
    ... ...
     /*pagevec_lookup_tag查找inode.mapping中规定段内被标记为tag(dirty)的pages*/
    while (!done && !nr_to_write_done && (index <= end) &&
	       (nr_pages = pagevec_lookup_tag(&pvec, mapping, &index, tag,
			min(end - index, (pgoff_t)PAGEVEC_SIZE-1) + 1))) {
        
        		/*clear_page_dirty_for_io会清掉inode.mapping中对应page dirty的标志*/
        		if (PageWriteback(page) ||
			    !clear_page_dirty_for_io(page)) {
				unlock_page(page);
				continue;
			}
			/*
			功能分析：__extent_writepage会将需要保护的inode数据cow并提交bio，bio完成之后会为数据添加inode的extent_data_item
			函数分析：
			1.writepage_delalloc在inode.io_tree中查找在page内delalloc的段(btrfs_dirty_pages设置为delalloc),并通过run_delalloc_range对数据cow，并添加ordered到root.ordered_extents。
			2.__extent_writepage_io将page通过submit_one_bio提交，bio完成后会异步激活btrfs_finish_ordered_io为inode数据添加extent_data并移除ordered
			*/
			ret = (*writepage)(page, wbc, data);
        		... ...
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

fsck

Btrfs的root是存储在super_copy中，在btrfs_commit_transaction中可以看到super是在其他dirty data都落盘之后才会落盘。在super落盘之前如果断电，因为采用的cow所以super所在的树并没有发生任何的改变(包括dev_extent，chunk，block_group，free_space信息)，而新写的数据因为其不在原super下，所以其磁盘信息和数据所在的磁盘空间将会作为空闲磁盘空间使用.

如果在super落盘过程中断电，super的数据可能会出现不一致，所以在btrfs_mount(如果是自动挂载，信息会存储在/etc/fstab中)时会通过__btrfs_open_devices检查super有效性。

static int __btrfs_open_devices(struct btrfs_fs_devices *fs_devices,
				fmode_t flags, void *holder)
{
    ... ...
    /*遍历fs_devices->devices上所有的device*/
    list_for_each_entry(device, head, dev_list) {
     ... ...
   	   /*通过btrfs_get_bdev_and_sb获取每个device上的super，如果因为断电导致super不一致将会返回错误，不做处理。*/
         if (btrfs_get_bdev_and_sb(device->name->str, flags, holder, 1,
					    &bdev, &bh))
			continue;
    ... ...
        /*获取super gen最新的device*/
        if (!latest_dev ||
		 device->generation > latest_dev->generation)
			latest_dev = device;
    }
    /*存储最新super的device，之后会再次通过btrfs_read_dev_super将super赋值给fs_info.super_copy*/
    fs_devices->latest_bdev = latest_dev->bdev;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

因为在btrfs_commit_transaction时会保证第一个mirror落盘之后，才会落盘其他两个mirror。所以如果在第一个mirror落盘过程中断电，这个mirror在btrfs_mount中读取super时会出错，而读取其他两个mirror(其root是原root，所有数据将会使用源root中的数据)；如果在第一个mirror落盘完成之后断电，重启之后读取第一个mirror读取总会成功(并且因为其gen最新所以会作为latest_dev)，这时将会用最新的root以及数据。