XFS FUSE Implementation (Week 4)
Leaf Directories
Once a Block Directory has filled the block, the directory data is changed into a new format. It still uses extents and the same basic structures, but the “data” and “leaf” are split up into their own extents. The “leaf” information only occupies one extent. As “leaf” information is more compact than “data” information, more than one “data” extent is common.
The leaf block has a logical offset that start at 32GB / block size.
The data block has the following structure:
typedef struct xfs_dir2_data {
xfs_dir2_data_hdr_t hdr;
xfs_dir2_data_union_t u[1];
} xfs_dir2_data_t;It contains only the header and data itself.
Another block is reserved for leaf and has the following structure
typedef struct xfs_dir2_leaf {
xfs_dir2_leaf_hdr_t hdr;
xfs_dir2_leaf_entry_t ents[1];
xfs_dir2_data_off_t bests[1];
xfs_dir2_leaf_tail_t tail;
} xfs_dir2_leaf_t;The bests and tail are almost unchanged from Block directories.
The hdr; however, has the following structure:
struct xfs_dir3_leaf_hdr {
struct xfs_da3_blkinfo info;
__uint16_t count;
__uint16_t stale;
__be32 pad;
};
Iteration
Iteration is the same as Block directories except that the first block is entirely reserved for the data, so we mark the end of the data when we exceed a block size of data.
Lookup
Lookup again is kind of simpler and similar to Block directories. Simpler because it's easier to seek to the start of the data.
Node Directories
When the “leaf” information fills a block, the extents undergo another separation. All “freeindex” information moves into its own extent. Like Leaf Directories, the “leaf” block maintained the best free space information for each “data” block. This is not possible with more than one leaf.
This is the first time we will need to use B+Trees.
Iteration
Iteration is; again, similar to Block directories except the we need to hop on to the next data block on the end of the current one. Also when passing the offset we need to mark the current block using the most significant bits.
Lookup
After searching for logical leaf offset we mark the first node, which is usually an internal B+Tree Node. The internal B+Tree Node has a btree array that has hashval/before pairs. The hashvals are; again, ordered so we can binary search them. The before in the pair points to the logical offset of the block carrying the lookup information. After we navigate there we can do as before with the lookup information.