Btrfs Code documentation
Kernel and Utilities
尽最大的可能在内核和应用程序之间共享代码。他们代码主要的不同在于启动和跟踪IO的代码。Btrfs内的任何一个项目都应该试着来保持内核和应用程序的更新，并且保持他们之间的代码通用。
对于Btrfs理解的重要部分便是理解keys和items是如何交互的，和各个类型的item的数据是如何编排格式的。Btrfs-debug-tree命令可以被用来打印ascii格式的btree结构，如果想要查看数据是如何在磁盘上排列的，这可能会非常有帮助。
- Btree
所有的元数据都被存放在磁盘上的一个btree中。Btrees存储key/item对。尽管使用了相同的代码来实现所有的btrees，但仍有一些不同种类的btree。可以参考 Btrees。
- Key
一个用来为一棵Btree的item提供标识和分类的固定大小的元组。key被分成3各部分：objectid, type, 和 offset。type字段显示另外两个字段应该被使用的方式和在item中找到的信息类型。可以参考Btree Keys。
- Item
存储在btree叶子中的可变大小的结构。根据key类型的不同，item含有不同类型的数据。可以参考Btree Items。
- Subvolume
一个含有文件和目录的命名树。每一个快照是一个subvolume，但并不是每一个subvolume都是一个快照。
- Snapshot
通过引用另一个subvolume的根来创建一个subvolume。快照是可写的，但是对于快照的任何修改都不会出现在它的父subvolume中。
- Extent buffer
一个允许访问大于一个页大小的btree块的抽象。
- ctree.c 核心的btree管理代码
- ctree.h 定义了keys和大多数元数据使用的数据结构
- dir-item.c 创建和使用目录items的辅助函数
- disk-io.c 元数据IO操作和FS open/close 例程
- extent-tree.c btree块和文件数据extents使用的tracks and space
- extent_io.c 跟踪状态（locked, writeback 等）和实现extent_buffers
- extent_map.c 映射一个文件的逻辑偏移到磁盘上的逻辑块地址
- file-item.c 插入和移除文件extents 和数据校验和的辅助函数
- file.c 文件写例程(kernel only)
- inode-item.c 在btree中分配inode结构的辅助函数
- inode.c kernel使用的大部分文件和目录操作
- ordered-data.c 为data=ordered 维护inodes链表
- print-tree.c 查找一棵btree并打印它找到的items
- root-tree.c 管理tree roots的tree中的items的辅助函数
- struct-funcs.c 例示所有的元数据的set/get 函数的宏
- super.c 内核超级块及相关函数
- transaction.c 处理事件的提交
- volumes.c 所有的多设备有关代码
- tree-log.c 为快速fsync 处理树items的日志
- compression.c zlib压缩支持例程
Using Extent Buffers
Extent缓冲是提供了对于跨越多个页的内存区域的读/写方法的容器。他们使btrfs可以具有大于单个页的树块，并且抽象出kmap调用以使元数据可以位于高端内存。
为了维护代码中的类型安全，Btrfs提供了一些宏可以将extent buffer内的偏移转换为一个特定的类型，还有一些宏来为数据结构中各个字段执行set/get操作。These macros including caching to lower then number of times kmap must be called while looping.
宏在ctree.h声明(查找BTRFS_SETGET_FUNCS)，但是由于他们相当大，在文件struct-funcs.c有他们的例示。用法的例子可以在下面的算法部分找到。
Tree Searching
我们希望通过对于树查找过程的研究，来了解B+树在btrfs中的应用。
int btrfs_search_slot(struct btrfs_trans_handle *trans,
struct btrfs_root *root, struct btrfs_key *key,
struct btrfs_path *p, int ins_len, int cow);
书查找是基于关键字的，查找结果保存在一个btrfs_path结构中，路径给了你从跟向下到页的所有的树块。
---------------------------------------------------------------------
fs/btrfs/ctree.h
430 struct btrfs_path {
431 struct extent_buffer *nodes[BTRFS_MAX_LEVEL];
432 int slots[BTRFS_MAX_LEVEL];
433 /* if there is real range locking, this locks field will change */
434 int locks[BTRFS_MAX_LEVEL];
435 int reada;
436 /* keep some upper locks as we walk down */
437 int lowest_level;
438
439 /*
440 * set by btrfs_split_item, tells search_slot to keep all locks
441 * and to force calls to keep space in the nodes
442 */
443 unsigned int search_for_split:1;
444 unsigned int keep_locks:1;
445 unsigned int skip_locking:1;
446 unsigned int leave_spinning:1;
447 unsigned int search_commit_root:1;
448 };
---------------------------------------------------------------------
上面的BTRFS_MAX_LEVEL定义为8。
path->nodes[0]总是叶子节点，path->nodes[1]为指向叶子节点的btree节点。slots数组指示使用的是btree块中的哪一个key或item。path->slots[1]告诉我们使用path->nodes[1]中的哪一个块指针来查找叶子节点。path->slots[0]告诉我们找到的是path->nodes[0]中的哪个item。
ins_len参数告诉btrfs_search_slot()来准备树以在树中中插入一个item(ins_len > 0)或移除一个item(ins_len < 0)。在插入的情形下，btrfs_search_slot()确保叶子节点有可以插入一个大小为ins_len的item的空间。对于移除items，btrfs_search_slot()确保高层节点被适当的拆分。
cow参数告诉btrfs_search_slot()你打算改变路径中的一个或多个buffers。这种情况下，它在从根到页的所有的buffers上执行适当的cow操作。
btrfs_search_slot()出错时返回 < 0，如果找到要查找的关键字则返回0，如果没找到，则返回1。如果没找到关键字，则路径指向关键字应该被插入的位置（即使ins_len为0）。这使你可以容易的查看接近于某个给定关键字的items。
查找关键字(0, 0, 0)将使路径指向数的第一个item。查找关键字将使返回值为1，并且路径指向树的最后一个item（假设那个关键字还没有出现，它也本不应该出现）。
btrfs_previous_item()可以被用以基于一个路径的查找给定类型的前一个item。
btrfs_next_leaf()可以被用以基于一个路径的查找给定类型的下一个item。
btrfs_prev_leaf()可以被用以基于一个路径的查找给定类型的前一个叶子节点。
Sample Search Code
volumes.c:find_next_chunk()是一个非常简单的为一个新的逻辑磁盘chunk查找起始点的例程。它查找chunk btree的最高的关键字，并返回一个更大的值。chunk树中的关键字具有如下的形式：
---------------------------------------------------------------------
key.objectid = logical byte offset
key.type = BTRFS_CHUNK_ITEM_KEY
key.offset = number of bytes in this chunk
---------------------------------------------------------------------
---------------------------------------------------------------------
947 static noinline int find_next_chunk(struct btrfs_root *root,
948 u64 objectid, u64 *offset)
949 {
950 struct btrfs_path *path;
951 int ret;
952 struct btrfs_key key;
953 struct btrfs_chunk *chunk;
954 struct btrfs_key found_key;
955
956 path = btrfs_alloc_path();
957 BUG_ON(!path);
958
959 key.objectid = objectid;
960 key.offset = (u64)-1;
961 key.type = BTRFS_CHUNK_ITEM_KEY;
962
963 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
---------------------------------------------------------------------
树搜索是一个只读的操作，所以btrfs_search_slot()不需要一个“事件处理”，并且ins_len和cow参数也为0。分配了一个path以用于记录搜索的结构，关键字被设置来搜索树中最高的可能的BTRFS_CHUNK_ITEM_KEY
---------------------------------------------------------------------
964 if (ret < 0)
965 goto error;
966
967 BUG_ON(ret == 0);
968
---------------------------------------------------------------------
我们期望搜索返回1，它不应该可能会有一个chunk以逻辑偏移2^64处为起始。
---------------------------------------------------------------------
969 ret = btrfs_previous_item(root, path, 0, BTRFS_CHUNK_ITEM_KEY);
---------------------------------------------------------------------
btrfs_previous_item() 被用来在树中向后查找，直到找到一个具有类型BTRFS_CHUNK_ITEM_KEY的关键字。如果他返回非零，那么它没有找到任何东西。如果需要，btrfs_previous_item() 可能会执行IO来读取通过查找父指针而找到的树中的前一个页子节点。
---------------------------------------------------------------------
970 if (ret) {
971 *offset = 0;
972 } else {
973 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
974 path->slots[0]);
975 if (found_key.objectid != objectid)
976 *offset = 0;
977 else {
978 chunk = btrfs_item_ptr(path->nodes[0], path->slots[0],
979 struct btrfs_chunk);
980 *offset = found_key.offset +
981 btrfs_chunk_length(path->nodes[0], chunk);
982 }
983 }
---------------------------------------------------------------------
btrfs_previous_item() 执行之后，path指向树中type == BTRFS_CHUNK_ITEM_KEY的最后一个item。btrfs_item_key_to_cpu() 从extent_buffer中拷贝出关键字，并执行尾端转换来把它变为CPU字节序，将结果保存在found_key 中。我们用*objectid返回新的chunk的起始字节。
---------------------------------------------------------------------
984 ret = 0;
985 error:
986 btrfs_free_path(path);
987 return ret;
988 }
---------------------------------------------------------------------
最后的步骤是释放path并返回。
Sample Item Insertion
在内部，item插入仅仅是一次搜索，然后在叶子节点中腾出空间，接着把item复制到适当的地方而已。下面的例子来自volumes.c:btrfs_add_device()。它在chunk树中添加包括每一个设备的总大小、设备类型、已使用的字节、最优的IO参数的信息。
设备item具有如下形式的关键字：
---------------------------------------------------------------------
key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
key.type = BTRFS_DEV_ITEM_KEY;
key.offset = device id
---------------------------------------------------------------------
设备items共享同一课完成逻辑->物理设备映射的树。他们的关键字具有相同的objectid和type字段，只有offset用来区分两个不同的设备item。传递给函数btrfs_add_device()的device 具有所有用来填充磁盘上元数据的数据。
---------------------------------------------------------------------
1032 int btrfs_add_device(struct btrfs_trans_handle *trans,
1033 struct btrfs_root *root,
1034 struct btrfs_device *device)
1035 {
1036 int ret;
1037 struct btrfs_path *path;
1038 struct btrfs_dev_item *dev_item;
1039 struct extent_buffer *leaf;
1040 struct btrfs_key key;
1041 unsigned long ptr;
1042
1043 root = root->fs_info->chunk_root;
1044
1045 path = btrfs_alloc_path();
1046 if (!path)
1047 return -ENOMEM;
1048
1049 key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1050 key.type = BTRFS_DEV_ITEM_KEY;
1051 key.offset = device->devid;
1052
1053 ret = btrfs_insert_empty_item(trans, root, path, &key,
1054 sizeof(*dev_item));
1055 if (ret)
1056 goto out;
---------------------------------------------------------------------
btrfs_insert_empty_item() 完成所有需要的在树中为新的item腾出空间的COW和btree 工作。如果返回0，则path 可以被用来填充数据。
---------------------------------------------------------------------
1058 leaf = path->nodes[0];
1059 dev_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dev_item);
1060
---------------------------------------------------------------------
btrfs_item_ptr() 把extent buffer leaf 中的一个偏移转换为一个struct btrfs_dev_item。树的叶子节点和slot的信息来自于path。 下面的代码使用set/get函数来填充元数据。
---------------------------------------------------------------------
1061 btrfs_set_device_id(leaf, dev_item, device->devid);
1062 btrfs_set_device_generation(leaf, dev_item, 0);
1063 btrfs_set_device_type(leaf, dev_item, device->type);
1064 btrfs_set_device_io_align(leaf, dev_item, device->io_align);
1065 btrfs_set_device_io_width(leaf, dev_item, device->io_width);
1066 btrfs_set_device_sector_size(leaf, dev_item, device->sector_size);
1067 btrfs_set_device_total_bytes(leaf, dev_item, device->total_bytes);
1068 btrfs_set_device_bytes_used(leaf, dev_item, device->bytes_used);
1069 btrfs_set_device_group(leaf, dev_item, 0);
1070 btrfs_set_device_seek_speed(leaf, dev_item, 0);
1071 btrfs_set_device_bandwidth(leaf, dev_item, 0);
1072 btrfs_set_device_start_offset(leaf, dev_item, 0);
1073
1074 ptr = (unsigned long)btrfs_device_uuid(dev_item);
1075 write_extent_buffer(leaf, device->uuid, ptr, BTRFS_UUID_SIZE);
---------------------------------------------------------------------
btrfs_device_uuid()用来查找设备item的uuid字段的偏移。write_extent_buffer() 使用这个字段作为一个到叶子节点页的memcpy操作的目的地址。
---------------------------------------------------------------------
1076 ptr = (unsigned long)btrfs_device_fsid(dev_item);
1077 write_extent_buffer(leaf, root->fs_info->fsid, ptr, BTRFS_UUID_SIZE);
1078 btrfs_mark_buffer_dirty(leaf);
1079
1080 ret = 0;
1081 out:
1082 btrfs_free_path(path);
1083 return ret;
1084 }
---------------------------------------------------------------------
最后的步骤是标记buffer为“脏”以使它被pdflush或transaction commit写回磁盘，然后释放path。
Sample Item Removal
移除items通过查找item，然后调用btrfs_del_item()来完成。下面的代码来自xattr.c:btrfs_delete_xattrs()，它删除一个给定inode的所有的xattrs。在inode.c:btrfs_truncate_inode_items()中可以找到一个这种循环的更高效的版本。基本的结构是循环搜索最后的类型为BTRFS_XATTR_ITEM_KEY的item并删除它。循环在你发现一些不是一个BTRFS_XATTR_ITEM_KEY的item的时候或者一些属于不同的objectid的item的时候终止。
xattr关键字具有如下的形式：
---------------------------------------------------------------------
key.objectid = objectid of the inode owning the xattr
key.type = BTRFS_XATTR_ITEM_KEY
key.offset = hash of xattr name
---------------------------------------------------------------------
---------------------------------------------------------------------
int btrfs_delete_xattrs(struct btrfs_trans_handle *trans,
struct btrfs_root *root, struct inode *inode)
{
struct btrfs_path *path;
struct btrfs_key key, found_key;
struct extent_buffer *leaf;
int ret;
path = btrfs_alloc_path();
if (!path)
return -ENOMEM;
path->reada = -1;
---------------------------------------------------------------------
path->reada = -1告诉预读代码你正在向后查找树。
---------------------------------------------------------------------
key.objectid = inode->i_ino;
btrfs_set_key_type(&key, BTRFS_XATTR_ITEM_KEY);
key.offset = (u64)-1;
while(1) {
/* look for our next xattr */
ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
---------------------------------------------------------------------
btrfs_search_slot()的ins_len为-1，由于我们在删除一个item。COW是1是因为树将会被修改。我们希望搜索的返回值为1，并且在搜索之后，path指向树中适于出入关键字的位置。如果我们从那个位置向前一个slot，我们将会找到这个inode的上一个xattr item或一个具有完全不同的类型或objectid的item。
---------------------------------------------------------------------
if (ret < 0)
goto out;
BUG_ON(ret == 0);
if (path->slots[0] == 0)
break;
path->slots[0]--;
leaf = path->nodes[0];
btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
if (found_key.objectid != key.objectid)
break;
if (btrfs_key_type(&found_key) != BTRFS_XATTR_ITEM_KEY)
break;
ret = btrfs_del_item(trans, root, path);
BUG_ON(ret);
btrfs_release_path(root, path);
---------------------------------------------------------------------
在确认了item具有我们查找的类型和objectid后，调用btrfs_del_item()来讲那个item从btree中删除。btrfs_release_path()减少path中所有的extent_buffers的引用计数，以使btrfs_search_slot()可以被再次调用。while循环终止后的最后的步骤便是释放path和返回了。 }
---------------------------------------------------------------------
ret = 0;
out:
btrfs_free_path(path);
return ret;
}
---------------------------------------------------------------------
Retrieved from "https://btrfs.wiki.kernel.org/index.php/Code_documentation"