XFS FUSE Implementation (Week 3)

Data Extents

XFS uses Data Extents to manage space. Data Extents are defined by their starting location and length. As you can imagine this can save quite a lot of space by allocating chunks of contiguous blocks. It's; however, useless if free block are sparse and spread everywhere. Extents are 128-bits in length with the first bit containing a flag determining whether this extent is invalid; as in, it was in the process of being written but a failure has occurred. Then, it's followed by 54-bits which determine logical file block offset. After that, 52-bits for the absolute block number. And finally, 21-bits for the number of blocks.

Logical Blocks: are imaginary block numbers that act as a logical sequential id.

Data Extents don't usually exist on their own in the wild. They are part of an Extent List or a B+Tree Extent List. We will deal with Extent Lists for a while.

Block Directories

When the Shortform directory space exceeds the space in an inode, the directory data is moved into a new single directory block outside the inode. Everything is stored in this block. This includes the directory data itself in addition to the lookup data; sometimes named as leaf data, and the freespace index data. Here we are not interested in the freespace index data because we are doing a read-only implementation.

The block has the following structure:

#define XFS_DIR2_DATA_FD_COUNT 3
typedef struct xfs_dir2_block {
  xfs_dir2_data_hdr_t hdr;
  xfs_dir2_data_union_t u[1];
  xfs_dir2_leaf_entry_t leaf[1];
  xfs_dir2_block_tail_t tail;
} xfs_dir2_block_t;

Where:

  1. hdr: Is the directory block header.
  2. u: Contains either an entry or defines an unused area.
  3. leaf: Contains lookup data.
  4. tail: Contains freespace index data.

The header has the following structure

struct xfs_dir3_data_hdr {
  struct xfs_dir3_blk_hdr hdr;
  xfs_dir2_data_free_t best_free[XFS_DIR2_DATA_FD_COUNT];
  __be32 pad;
};

Where:

  1. hdr: Is the directory/attribute header.
  2. best_free: An array pointing to free regions in the directory block.

The directory/attribute has the following structure:

struct xfs_dir3_blk_hdr {
  __be32 magic;
  __be32 crc;
  __be64 blkno;
  __be64 lsn;
  uuid_t uuid;
  __be64 owner;
};

These fields are important for integrity checks. We will talk about them later.

Entries have the following structure:

typedef struct xfs_dir2_data_entry {
  xfs_ino_t inumber;
  __uint8_t namelen;
  __uint8_t name[1];
  __uint8_t ftype;
  xfs_dir2_data_off_t tag;
} xfs_dir2_data_entry_t;

Where:

  1. inumber: The inode number that this entry points to.
  2. namelen: Length of the name, in bytes.
  3. name: The name associated with this entry.
  4. ftype: The type of the inode. This is used to avoid reading the inode while iterating a directory. The XFS_SB_VERSION2_FTYPE feature must be set, or this field will not be present.
  5. tag: Starting offset of the entry, in bytes. This is used for directory iteration.

If there is no data in this location, it will contain a the following structure:

typedef struct xfs_dir2_data_unused {
  __uint16_t freetag; /* 0xffff */
  xfs_dir2_data_off_t length;
  xfs_dir2_data_off_t tag;
} xfs_dir2_data_unused_t;

Iteration

Iteration here is simple, each entry contains a tag that is the offset of the entry's address from the beginning of the block. The inode contains only one extent. So, we read the extent and seek to the block, we then skip the header's size. Finally we start reading the first 2 bytes if they are euqal to 0xFFFF then it's the freetag and this is an unused space we skip by length of such space and read the next entry until we have read the number of entries in this block. If we start from an offset we repeate the previous cycle of checking for the free tag.

Lookup

We can skip to the leaf structure which contains a hashval/address, hasvals are ordered so we can do binary search and seek to the address.


CategoryGsoc

SummerOfCode2021Projects/XFSFUSEImplementation/Week3 (last edited 2021-08-22T15:40:01+0000 by KhaledEmaraDev)