OuicheFS Extended

Project 2026 — Beyond the 4 MB Barrier

Author

Julien Sopena, Sorbonne University

In this project, you will have to implement new features on top of an existing file system, ouichefs, in the form of a kernel module for Linux 6.6.137.

As usual, you are strongly encouraged to use a cross-reference tool to navigate the Linux kernel source code, be it integrated in your development environment or online like Bootlin’s Elixir.

You are also strongly encouraged to read the documentation available in Documentation/filesystem/vfs.rst or online to better understand how the virtual file system (VFS) layer works and how a file system is implemented.

Objectives of the project

In this project, you will design and implement an extent-based block addressing scheme for OuicheFS, lifting its current hard limit of 4 MB per file.

In the current implementation, a file’s data blocks are referenced by an index block containing an array of 1024 block numbers (uint32_t). Since each block is 4 KB, this limits files to 1024 × 4 KB = 4 MB.

The core idea is to replace this flat list of block numbers with a list of extents. An extent is a pair (start, count) describing a run of count consecutive blocks beginning at block start. For example, the extent list [(127, 4), (512, 2)] encodes the six blocks 127, 128, 129, 130, 512, 513.

Since each extent occupies 8 bytes (two uint32_t), an index block can hold up to 512 extents. The maximum file size now depends on how contiguous the data is on disk:

Best case (one large contiguous run): a single extent can describe billions of blocks, effectively removing the size limit.
Worst case (fully fragmented): 512 extents × 1 block = 512 × 4 KB = 2 MB — worse than before.

This trade-off makes the block allocator a first-class concern: a good allocator that favours contiguous allocation directly improves the maximum file size. This approach is similar to the extent-based addressing used in production file systems such as ext4.

1 Project roadmap

The project is structured into a series of progressive steps, each focusing on a specific feature to implement. It is essential to complete these steps sequentially, as each builds upon the foundation laid by the previous one.

Important

Please read the assignment in its entirety before starting your implementation!!!

Having a clear understanding of all the requirements beforehand allows you to make more informed design decisions and ensures a smoother development process. Also keep in mind that testing is an important part of the evaluation!

1.1 Mounting and testing a vanilla OuicheFS

This project is based on the OuicheFS file system that you need to download from GitHub at the following address: https://github.com/rgouicem/ouichefs. Be careful to use the branch named v6.6.137!

Alongside the source code, you will find comprehensive documentation detailing the design of this simple file system, including the relationships between various kernel structures and their interactions. Feel free to explore the source code, which is well-documented, and experiment with the vanilla file system in your virtual machine. This hands-on approach will help you understand its functionality and identify its limitations.

After downloading the source and building the kernel module, you will need to format a partition with OuicheFS and mount it. You can then test the file system by creating files, writing data, and reading it back.

Pay particular attention to the structure of the index block (ouichefs_file_index_block) and how it is read and written in the file operations. Understanding this is essential before modifying anything.

1.2 Reimplementation of the read and the write functions

The first step of your project is to reimplement the read and the write functions of OuicheFS without changing their behavior. Currently, OuicheFS does not implement these functions and therefore uses the default implementation provided by the Linux kernel. Unfortunately, this default implementation relies on the page cache and abstracts away the mapping from logical block offsets to physical block numbers, which will need to be under your control at the end of the project.

To simplify this step, you will implement read and write functions that behave like the default implementation, but that will not use the page cache. To do this, you will need to use the sb_bread and brelse functions provided by the Linux kernel to read data directly from the disk. You will also need to use the mark_buffer_dirty and sync_dirty_buffer functions to write data to the disk.

The read function, whose prototype you can find in the documentation of the vfs referred to above, has the following semantic:

You must return the amount of bytes you copied to userspace. There are some cases when that quantity is 0.
Updating the offset given to you by the application is your responsibility.
Note that you do not have to return all the bytes that the application asked you for. The returned quantity and the offset update must only be consistent with what you copy. An application that wishes to read until the end of the file (like cat(1)) will attempt the read syscall again. However, note that returning 0 can be interpreted by the application that there will be no more bytes left to read, prompting them to give up.

The write function has the following semantic:

You must return the amount of bytes you have copied from userspace.
You must still update the offset.
You do not have to accept all the bytes the application sent you.
All the updates to the inode are your responsibility.
Note that writes done after the end of the file are valid. It is your responsibility to fill the possible blanks in the file.
If the file was opened with the O_APPEND flag (e.g. when using echo >> file), you must move the write offset to the end of the file before writing.

You are strongly advised to read the functions ouichefs_write_begin and ouichefs_write_end to see what checks and modifications are made. Your write function will be called instead of those!

Check that your implementation works correctly by repeating the file operations from Section 1.1 and measure the performance loss compared to the default implementation.

1.3 Extent-based index block

The goal of this step is to introduce the data structures required for extent-based addressing and to update the on-disk format accordingly.

1.3.1 Data structures

Define the following structure to represent a single extent:

struct ouichefs_extent {
    uint32_t start; /* first physical block number of the run */
    uint32_t count; /* number of consecutive blocks in the run */
};

Replace the ouichefs_file_index_block structure so that it stores an array of OUICHEFS_MAX_EXTENTS extents, where OUICHEFS_MAX_EXTENTS = OUICHEFS_BLOCK_SIZE / sizeof(struct ouichefs_extent).

Unallocated slots contain {0, 0}. Since block 0 is always the superblock and is never a valid data block, start == 0 is an impossible value for a real extent and is used to encode special cases (holes, see Section 1.9). Scanning the array stops at the first entry with count == 0.

Tip

The index block is zero-filled by the kernel when first allocated and by mkfs at format time. There is no need to write an explicit terminator: unwritten slots are already {0, 0} and will naturally stop any scan.

Tip

A good strategy is to patch all code assuming every extent has a size of 1 (i.e., count = 1 for every extent). Each extent then describes exactly one block, so the extent array is a direct one-to-one mapping with the old flat index, and you can reuse the same indexing logic. This limits file sizes to at most 2 MB and will be fixed in a later step.

1.3.2 Debugging ioctl

Implement an ioctl command OUICHEFS_IOC_GET_EXTENTS that, given an open file descriptor, reads its index block and prints the full extent list to the kernel log (dmesg), in the following format:

ouichefs: extents for inode <ino>: <n> extent(s)
  [0] start=127 count=4  (blocks 127–130)
  [1] start=512 count=2  (blocks 512–513)

Define the ioctl macro in a file called extent_ioctl.h. This command will be your primary debugging tool throughout the rest of the project.

1.4 Updating the read function

Now that the data structures are in place, update the read function you wrote in Section 1.2 to use extent-based addressing.

1.4.1 Logical-to-physical block translation

Write a helper function with the following signature:

static uint32_t ouichefs_extent_get_block(
        struct ouichefs_extent *extents, uint32_t logical_block);

This function takes the extent array and a logical block index (0 for the first block of the file, 1 for the second, etc.) and returns the corresponding physical block number, or 0 if the logical block is beyond the end of the extent list.

1.4.2 Integration

Replace the direct index-block lookup in your read function with a call to ouichefs_extent_get_block. Verify that reading still works correctly for files created with the updated mkfs.ouichefs.

Note

You do not need to modify the write function in this step. The sole objective here is to make the read path extent-aware, so that it will work correctly once the write function is updated in Section 1.5.

1.5 Updating the write function

Update the write function from Section 1.2 to build and maintain the extent list when allocating new blocks.

1.5.1 Extent-aware block allocation

When a write requires allocating a new block (beyond the current end of file), proceed as follows:

Allocate a free block using the existing allocator (ouichefs_alloc_block).
Check whether the newly allocated block is contiguous with the last extent, i.e., last.start + last.count == new_block. If so, increment last.count — no new entry is needed.
Otherwise, append a new extent {new_block, 1} in the next available slot (already {0, 0} from zero-initialisation — no explicit write needed).
If all 512 slots are already occupied, return -ENOSPC.

After every allocation, write the updated index block back to disk and mark it dirty.

1.5.2 Updating file deletion

Update ouichefs_evict_inode (or the equivalent truncation path) to free blocks extent by extent. For each valid extent {start, count}, free all blocks from start to start + count - 1.

1.5.3 Verification

Use the OUICHEFS_IOC_GET_EXTENTS ioctl from Section 1.3 to inspect the extent list of files written with your new function. Create a file slightly larger than 4 MB and verify it can be written and read back correctly.

Note

For this step, assume that all writes are sequential and append-only: the application writes from offset 0 and never seeks backward or past the end of file before writing. Support for sparse files (created by lseek + write past the end) will be added in Section 1.9.

Tip

At this point, the extent count for a typical file will equal the number of allocated blocks, because the existing allocator does not guarantee contiguous allocation. The next step addresses this.

1.6 Contiguous block allocator

The key insight of extent-based addressing is that the larger the extents, the fewer entries are consumed and the larger files can become. This step implements a contiguous block allocator to maximise extent sizes.

1.6.1 Implementation

Write the following function:

static uint32_t ouichefs_alloc_contiguous(struct super_block *sb,
                                          uint32_t requested,
                                          uint32_t *block);

requested must be non-zero. This function searches the free-block bitmap for the longest run of consecutive free blocks, up to requested. It marks all found blocks as allocated, writes the starting block number into *block, and returns the number of blocks actually allocated — which may be less than requested if no run that long exists. Returns 0 if the partition has no free blocks at all, in which case *block is left unchanged.

Tip

The return value is both the success indicator and the allocation count: 0 means failure, any positive value means success with that many blocks allocated. The caller should always check for 0 before using *block, and use the returned count (not requested) when building the new extent.

Tip

Iterate over the bitmap word by word and count consecutive zero bits to find a free run. A first-fit strategy stops at the first run large enough to satisfy the request. It is also possible to implement a best-fit strategy that scans the entire bitmap and picks the run that minimises fragmentation, though this is more open-ended. For a more advanced allocator design, see Section 1.11.

1.6.2 Integration

Update the write function from Section 1.5 to call ouichefs_alloc_contiguous instead of ouichefs_alloc_block. Pass as requested the number of blocks still needed to satisfy the current write call. When the allocator returns fewer blocks than requested, perform a partial write and let the caller retry.

Verify that writing a large file now produces significantly fewer extents than before, and measure the maximum file size achievable on a given partition.

1.7 Write-time block reservation

Allocating blocks one at a time during writes creates fragmentation even with the contiguous allocator of Section 1.6: two concurrent writers interleaved on the same partition will fragment each other’s files. This step introduces write-time reservation: when a file needs more space, it pre-reserves a contiguous window of blocks larger than immediately needed, guaranteeing future writes can extend the last extent without touching the bitmap.

1.7.1 In-memory reservation state

Add two fields to ouichefs_inode_info (the in-memory inode structure, not the on-disk one):

uint32_t i_reserved_start; /* first pre-reserved block          */
uint32_t i_reserved_count; /* number of pre-reserved blocks left */

Both fields are initialised to 0 when an inode is loaded and are never written to disk.

Define the reservation window size as a module parameter with a default value:

static uint32_t reservation_size = 8;
module_param(reservation_size, uint, 0644);

1.7.2 Allocation with reservation

When the write function needs to extend the file, check the reservation window first:

If the reservation is exhausted (i_reserved_count == 0), call ouichefs_alloc_contiguous(sb, reservation_size, &start) to obtain a new window. If it returns 0, trigger the GC (see below) and retry once. On success, store start in i_reserved_start and the returned count in i_reserved_count. The allocated blocks are immediately marked as used in the bitmap, preventing any concurrent writer from taking them. Consume the first block of the new window as described in step 1.
If i_reserved_count > 0, the next block to write is i_reserved_start. Increment the last extent’s count, decrement i_reserved_count, and advance i_reserved_start — no bitmap operation needed.
Handle the special case where the allocation request is greater than the reservation window size.

Tip

The reserved blocks are marked as allocated in the bitmap but do not appear in any extent yet. From the file system’s perspective they are “used but uncommitted”. This is exactly the invariant maintained by ext3/ext4 reservations.

1.7.3 Releasing unused reservations

Hook into the release file operation (called when the last file descriptor referencing an inode is closed). If i_reserved_count > 0, free the i_reserved_count blocks starting at i_reserved_start in the bitmap and reset both fields to 0.

Also release the reservation in evict_inode (file deletion), before freeing the blocks referenced by the extents.

1.7.4 Garbage collector

When ouichefs_alloc_contiguous returns 0 (no free blocks), do not immediately return -ENOSPC. Instead, trigger a GC pass:

Iterate over all inodes currently loaded in memory via sb->s_inodes.
For each inode with i_reserved_count > 0, free its reserved blocks and reset both reservation fields to 0.
Retry ouichefs_alloc_contiguous.
Only return -ENOSPC to the caller if the retry also fails.

Note

The GC reclaims space that was logically reserved but never written. It is a last-resort mechanism — a well-sized reservation_size should make it rare in practice. Track the number of GC runs with a counter in the superblock info for the sysfs step.

Warning

Iterating over sb->s_inodes and modifying per-inode reservation fields while other writers may be running concurrently raises data race issues. Be careful about concurrent accesses in your implementation.

Verify the reservation mechanism by writing to a file in small increments and checking with OUICHEFS_IOC_GET_EXTENTS that the number of extents grows slowly (one new extent per exhausted window, not one per write). Trigger the GC by filling the partition with several concurrent writers and verifying that space is correctly reclaimed.

1.8 Sysfs statistics

To monitor the state of the file system, implement a directory /sys/ouichefs/<partition>/ containing the following read-only files:

File	Content
`free_blocks`	Number of free blocks
`committed_blocks`	Number of blocks referenced by at least one extent (data effectively written)
`reserved_blocks`	Number of blocks marked in the bitmap but not yet in any extent
`files`	Number of regular files
`total_extents`	Total number of extents across all files
`avg_extent_size`	Average extent size in blocks × 100 (e.g. 250 means 2.50 blocks)
`max_file_size`	Size in bytes of the largest file on the partition
`fragmentation`	Average number of extents per file × 100 (e.g. 133 means 1.33 extents/file)
`reservation_size`	Current value of the reservation window (read-write)
`gc_runs`	Number of GC passes triggered since mount

The following invariant must hold at all times and can be used as a sanity check in your tests:

free_blocks + committed_blocks + reserved_blocks == total_blocks

committed_blocks and reserved_blocks are complementary: a block moves from reserved to committed when it is consumed by a write (i.e. when it is appended to the last extent). It moves back to free when the file is deleted or when unused reservations are released by the GC or at release time.

The fragmentation and avg_extent_size metrics are reported multiplied by 100 to preserve two decimal places without using floating-point arithmetic in the kernel. A perfectly packed file system would report fragmentation = 100 (one extent per file); a fully fragmented one would report one extent per block. These values can be divided by 100 in userspace for display.

The reservation_size file should be read-write: writing a new integer value to it updates the reservation_size module parameter at runtime, allowing experimentation without reloading the module.

Tip

Computing total_extents, avg_extent_size, and max_file_size requires scanning all on-disk inodes. reserved_blocks requires iterating over in-memory inodes (sb->s_inodes) and summing their i_reserved_count fields. For all these metrics, you may compute lazily (on each sysfs read) or maintain running counters updated on every allocation and release. Choose your approach based on the trade-offs between simplicity and overhead.

Verify your implementation by creating files of various sizes, reading the statistics, deleting files, and checking that the counters are updated correctly. This should work with multiple file systems mounted at the same time. For instance, /sys/ouichefs/vda/ and /sys/ouichefs/vdb/

1.9 Sparse files and holes

A sparse file is a file that contains holes: regions that have never been written but are within the logical file extent. They are created by seeking past the current end of file (lseek) and then writing, leaving an unwritten gap. On read, holes appear as sequences of zero bytes without consuming disk space.

1.9.1 Representing holes in the extent array

Since start == 0 is impossible for a real data extent (block 0 is always the superblock), it can encode a hole: an extent {0, N} with N > 0 represents a hole of N consecutive logical blocks. The three cases when scanning the array are:

`start`	`count`	Meaning
0	0	Unallocated slot — end of list
0	N > 0	Hole of N logical blocks
B > 0	N > 0	N real data blocks starting at block B

Note

In a first step, do not handle the case where a write targets a range that falls inside an existing hole. This is covered in Section 1.9.5.

1.9.2 Creating holes

Update the write function to handle the case where the write offset is strictly beyond the current inode->i_size. Before appending the new data extents, insert a hole extent {0, gap_in_blocks} to cover the gap. Convert the gap from bytes to blocks, rounding up.

Tip

If the last existing extent is also a hole {0, N}, simply increment its count rather than appending a new entry.

1.9.3 Reading holes

Update ouichefs_extent_get_block to distinguish holes from real blocks. When the logical block falls within a {0, N} extent, signal a hole to the caller (for example by returning a dedicated sentinel such as OUICHEFS_HOLE_BLOCK). Update the read function to memset the corresponding portion of the user buffer to zero instead of calling sb_bread.

1.9.4 Updating file deletion

Update ouichefs_evict_inode to skip hole extents {0, N} when freeing blocks: a hole occupies no disk space and has no blocks to release.

1.9.5 Writing into an existing hole

The most complex case occurs when a write targets a range that falls inside an existing hole extent {0, N}. The hole must be split into up to three pieces:

Write at the start of the hole: {0, N} → {real, written}, {0, N - written}
Write at the end of the hole: {0, N} → {0, N - written}, {real, written}
Write in the middle: {0, N} → {0, offset}, {real, written}, {0, N - offset - written} — this inserts two new entries and shifts all subsequent entries rightward.

Warning

Splitting a hole in the middle requires shifting all following entries in the array to make room for the extra entry. Verify that the table has enough free slots before performing the shift, and update the index block atomically.

1.10 File defragmentation

As the file system is used, external fragmentation will naturally occur: files will accumulate many small extents, consuming the extent table and limiting the maximum file size. To address this, implement a defragmentation mechanism.

1.10.1 Per-file defragmentation ioctl

Implement an ioctl command OUICHEFS_IOC_DEFRAG_FILE that defragments a single file identified by its file descriptor. Write your command in extent_ioctl.h. The algorithm is as follows:

Compute the total number of blocks used by the file.
Attempt to allocate that many contiguous blocks using ouichefs_alloc_contiguous(sb, total_blocks, &new_start).
Copy the file data block by block from the old locations to the new contiguous region.
Update the extent list to a single entry {new_start, total_blocks} and zero out the remaining slots.
Free the old blocks.

If a fully contiguous allocation is not available, the ioctl may return -ENOSPC or perform a partial defragmentation (reducing the number of extents without necessarily reaching one).

1.10.2 Automatic defragmentation

Trigger a full-partition defragmentation scan automatically when, at the end of a write operation, the fragmentation metric exceeds a configurable threshold (e.g., 400, meaning 4.00 extents per file on average). The scan iterates over all files and calls the per-file defragmentation on those with more than one extent.

You may also expose a threshold file in sysfs to allow runtime tuning of this parameter.

1.11 Bonus: advanced block allocator

Difficult question — only attempt if everything else works

This section has no single correct answer. It is open-ended and exploratory. Do not start it until all previous steps are fully functional and tested.

The contiguous allocator of Section 1.6 scans the bitmap linearly every time a new reservation is needed. As the partition fills up, contiguous free runs become scarce and the scan grows expensive. More importantly, small scattered free regions accumulate between reserved windows, a form of external fragmentation that the GC of Section 1.7 only partially addresses.

A well-known mechanism to counter this is the buddy allocator, used by the Linux kernel for physical memory. It maintains free blocks grouped by size class and merges adjacent free blocks systematically to reduce fragmentation.

Design and implement an analogous mechanism for block allocation in OuicheFS. This structure should live separately from the bitmap, but the bitmap must be kept consistent with it at all times.

2 Bug bounty

If you find any bug in ouichefs, do not hesitate to report it and fix it! If you manage to fix a bug, provide a patch and an explanation in your report. After the submission deadline, you can submit your fix through a pull request on GitHub (in exchange for a few bonus points of course…).

3 Submission

3.1 Process

You will submit your work via email as a set of patches (8-12 patches) directly applied to the ouichefs git repository, not to the Linux kernel sources.

The email subject format should be:

Subject: [PATCH 1/8] project: ......

This patchset needs to contain:

the modified sources of ouichefs,
a short pdf report (2–4 pages),
the tests you used as a single executable extent.sh script.

This report should contain explanations about your design choices (algorithms and data structures) and a status report with the following sections:

List of features implemented and functional
List of features implemented but not fully functional. In this case, explain the problems, why they occur, and potential fixes if you have any in mind.
List of features not implemented.
Tests used and instructions on how to run them.
Short conclusion based on your experimental results.

The project must be done in groups of three students. A Moodle grouptool can be used to register your groups, and you can use either the Moodle forum or the Matrix room to find group members.

The submission deadline is : July 30 at 14:00. After the deadline, you will also have to present your work, design and implementations choices, and make a short demonstration.

3.2 Grading

You will be evaluated on the following criteria:

Functionality: Does your code pass the functional tests?
Design: How elegant and optimized is your implementation?
Test: How relevant are the tests used?
Code Quality: Is your code readable and properly commented? (Ensure you use the scripts/checkpatch.pl script from the kernel sources and strictly respect the kernel coding style rules).

Please ensure your report is clear, concise, and spell-checked. While the report itself is not explicitly graded, a poorly written report makes it difficult for us to understand your design choices and award you appropriate points.