dtfs Design Issues -- Block Addressing and Layout

In-Memory Block Addressing Scheme, Partial Segment Layout

Addressing blocks in the dtfs kernel module

Conclusion: Tested in mkdtfs implementation, depreciated.

At first I assumed that it would be a good idea to have a "logical block address space" in which all blocks are mapped. The physical block addresses of the underlying device would be part of that logical block address space. Furthermore, a distinct area of the logical address space would be reserved for various kinds of indirect blocks and for inode blocks.

However, on a second thought it turns out that this approach has some severe drawbacks:

• A block that is read in from the disk and gets dirty changes its logical address.

• Writing out a partial segment by sorting the blocks by their logical block number is fine for sorting out dependencies. However, in this situation writing the ifile gets a problem: Since the ifile data blocks would get written out before the inodes block are written, fixing up the block numbers on writing the ifile blocks out becomes a problem. (And reserving address space for ifile data blocks would be possible but is not a very good solution IMHO)

• Furhtermore sync calls might force a file A that was originally scheduled for a write after the blocks of file B have been written out to be written before B. This results in the necessity to re-order blocks in a partial segment adding even more complexity.

A better way to address blocks.

Conclusion: Implementaion planned in dtfs kernel module.

Having a different block address space for each file seems to be a more viable approach: Every data block in the file system is uniquely identified by the inode number of the file and the index of the data block within that file.

Indirect blocks could be assigned very high block numbers (which would also cause them to be placed after all data blocks automatically thus easing the address fixup necessary when writing them out to the device.)

Placing data blocks before indirect blocks.

Conclusion: Implemented in mkdtfs, planned for dtfs kernel module implementation.

dtfs places data blocks in a partial segment before the indirect blocks referencing them. This eases the address fixup necessary when writing out the indirect blocks. The drawback of this decision is that read-aheads when accessing indirect blocks (that could pick up some useful data blocks of the file) are not possible since the indirect blocks follow the data blocks.

However, such read-aheads would probably not buy us too much, since

• dtfs assumes that the system has large in-memory caches that can satisfy many read requests without actual disk access anyway.

• The read-ahead would probably not return useful data since indirect blocks are needed for large files only. When the indirect blocks were placed before the data blocks they reference a read-ahead would only read in some data blocks at the beginning of the file. However, when an indirect block is accessed we are not interested in data blocks at the beginning of the file, rather on data blocks somehwere in the middle of the file or at the end of the file. (Otherwise we would not be accessing an indirect block in the first place.)

Placing inode blocks (almost) last in a partial segment.

Conclusion: Implemented in mkdtfs, planned for dtfs kernel module implementation.

Inodes blocks are placed (almost) last in a partial segment to ensure that all blocks that they reference have already got a valid physical address so that performing the address fixup when writing them to disk should be rather simple.

Block ordering in a checkpoint.

Conclusion: Implemented in mkdtfs, planned for dtfs kernel module implementation.

The general idea behind the strategy of placing blocks in a partial segment in that special way they are is to avoid that a block A that contains a reference to block B is written out before B. Therefore we get the following block ordering (from low physical block address to high physical block address) within a partial segment:

• data blocks of file A (sorted)
• single indir. blocks of file A (sorted)
• double indir. blocks of file A (sorted)
• triple indir. blocks of file A (sorted)

  repeated for each file in the partial segment

• inode blocks (sorted)
• data blocks of the ifile
• indir. blocks of the ifile (same as the indir. block scheme for ordinary files)
• A special checkpoint block that contains the inode of the ifile. (This block is not absolutely necessary, but without this block such a linear block dependency would not be possible.
• The partial segment header.

Placing the ifile inode directly into the checkpoint header.

Conclusion: Depreciated.

This solution would avoid the necessity of having an addational block for the ifile inode while still maintaining the linear block dependency. The problem with this approach is that the detailed structure of an inode is dependend on the tradfs used. Thus placing the inode directly in the checkpoint header would introduce a tradfs--dependent information in a dtfs data structure.

The fact that future versions of dtfs might support having more than one file system that might even use different traditional file system implementations within one dtfs partition makes this approach even more impracticable.

Christian Czezatke, email: e9025461@student.tuwien.ac.at