当前位置: 首页 > 工具软件 > Btrfs > 使用案例 >

Btrfs Code documentation

司空玮
2023-12-01
Btrfs Code documentation (2010-08-15 23:28) 转载

Kernel and Utilities

尽最大的可能在内核和应用程序之间共享代码。他们代码主要的不同在于启动和跟踪IO的代码。Btrfs内的任何一个项目都应该试着来保持内核和应用程序的更新,并且保持他们之间的代码通用。

对于Btrfs理解的重要部分便是理解keys和items是如何交互的,和各个类型的item的数据是如何编排格式的。Btrfs-debug-tree命令可以被用来打印ascii格式的btree结构,如果想要查看数据是如何在磁盘上排列的,这可能会非常有帮助。

Btrfs Terms

  • Btree

所有的元数据都被存放在磁盘上的一个btree中。Btrees存储key/item对。尽管使用了相同的代码来实现所有的btrees,但仍有一些不同种类的btree。可以参考 Btrees

  • Key

一个用来为一棵Btree的item提供标识和分类的固定大小的元组。key被分成3各部分:objectid, type, 和 offsettype字段显示另外两个字段应该被使用的方式和在item中找到的信息类型。可以参考Btree Keys

  • Item

存储在btree叶子中的可变大小的结构。根据key类型的不同,item含有不同类型的数据。可以参考Btree Items

  • Subvolume

一个含有文件和目录的命名树。每一个快照是一个subvolume,但并不是每一个subvolume都是一个快照。

  • Snapshot

通过引用另一个subvolume的根来创建一个subvolume。快照是可写的,但是对于快照的任何修改都不会出现在它的父subvolume中。

  • Extent buffer

一个允许访问大于一个页大小的btree块的抽象。

Main Source Files

  • 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"

Categories: Code | Documentation

 类似资料:

相关阅读

相关文章

相关问答