Introdution
Hi, this is my analysis of a bug I found on the simplefs project. Here's the project link. This was my first time finding a bug and trying to figure out the cause. Although the core root cause was not found by me, I did play some role in pinpointing the cause. I hope anyone interested in filesystems, the linux kernel, and low level computing in general could find some use from this post.
The problem
When mounting a simplefs filesystem image, whether it be a file image freshly created one with files, locks up upon mounting or looking through its contents. The kernel watchdog soft lockup warning gives which function caused a soft lockup, which was __file_lookup(), a function wrapped around simplefs_lookup, which is one of inode operations. The system hanged during execution of ls or other commands/programs that uses inode lookup operation.
What happens inside __file_lookup
Simplefs has 3 main things to consider when looking for files and directories. The inode, extent block, and the actual data block. Inode contains all information about the file and directory, without the actual data. The inode number is found in directory entries, or in case of root, on the superblock. In case of simplefs, inode has the extent block number as a reference to its data. The extent block is a block which contains a list of block numbers that contain the data for file or dir(for file, the raw data and for directories, the dir entry). In dir entry lists, each dir entry(which is simplefs_file structure) has nr_blk, inode number and filename. The nr_blk variable contains a number that defines how much offset the index has to go to the next dir entry. For example, if nr_blk is 1, the next dir entry is 1 offset away from it, and if it is 4 the next dir entry is 4 offset away from it.
The __file_lookup function loops through the extent blockβs extent entries, dir entry blocks, and dir entries(3 for loops). In order to optimize the performance, the starting point of extent entries and dir entry blocks are determined by the hash of the target file the function is looking for. And for it to prevent the hash value from going over the actual length, it is divided by max blocks per extent value. And if the file is not found until the end, it goes to the start of the index and looks from there again. When looking through dir entries, nr_blk is added every iteration, which significantly reduces the number of iterations if there are long empty dir entries until the next valid dir entry.
The surface problem
https://github.com/sysprog21/simplefs/pull/88
The __file_lookup function would work on a valid filesystem, without any corruption or function with human error. In the most inner for loop(which iterates through dir entries), however, it assumes nr_blk to be a positive value, which should be in an error-free filesystem. However, if for some reason the value is 0(never negative because it is uint32_t), the for loop never advances and becomes stuck at the same dir entry over and over again, causing the for loop to spin endlessly, Causing GUI to become unresponsive in some systems, and triggering watchdog. This was the surface cause of filesystem image causing a lockup, because in the place where there would be dir entries were all null.
The root cause
https://github.com/sysprog21/simplefs/pull/90
The reason why there were null values in place of valid dir entry blocks was caused by a human error. In creation of the filesystem, all bytes on disk or image is null. Upon initialization of the extent block for dir, each nr_blk in entry should be set as SIMPLEFS_FILES_PER_BLOCK, and the rest should be initialized as defined in the function simplefs_get_new_ext(). However, the initialized dir entry blocks were never written to the filesystem, because the buffer was never marked dirty. As a result, the initialized value were persisted as 0, making nr_blk to be interpreted as 0, triggering the surface problem.
Meanwhile, creation of new entries to dir entries was written to block.
...
bi = hash_code % eblock->extents[avail].ee_len;
for (idx_bi = 0; idx_bi < eblock->extents[avail].ee_len; bi++, idx_bi++) {
CHECK_AND_SET_RING_INDEX(bi, eblock->extents[avail].ee_len);
bh2 = sb_bread(sb, eblock->extents[avail].ee_start + bi);
if (!bh2) {
ret = -EIO;
goto put_block;
}
dblock = (struct simplefs_dir_block *) bh2->b_data;
if (dblock->nr_files != SIMPLEFS_FILES_PER_BLOCK)
break;
else
RELEASE_BUFFER_HEAD(bh2);
}
...
eblock->extents[avail] values are valid, so ee_start + bi is correctly set as the first available extent block(ee_start of extents[avail]) + bi value(which stays in the range set by CHECK_AND_SET_RING_INDEX). At the first iteration, dblockβnr_file != SIMPLES_FILES_PER_BLOCK(since nr_file is 0, or it could be written correctly if the buffer_head is still in memory, which would correctly write to the position of extent block, since later in the creation process, as I will mention next, the block is marked dirty), and writes dir entry to that block with simplefs_set_file_into_dir, which is then marked dirty to be written to disk.
Fix
https://github.com/sysprog21/simplefs/pull/91
The proposed fix on PR #90 adds mark_buffer_dirty(bh) before brelse(), which fixes the root cause. In addition, the PR #91 adds a guard on __file_lookup function to check whether nr_blk is 0 and return -EUCLEAN if so, with unlikely() macro to inform that this is a rare case, since in the case of violation, __file_lookup becomes non-terminating, causing unbounded kernel loop(In userspace, the process using __file_lookup function hangs forever and become impossible to terminate, even at shutdown, making force shutdown necessary, or at worst case scenario, causes the user interface to become unresponsive). Returning -EUCLEAN reports that filesystem is corrupted in violation of nr_blk > 0 to userspace, and makes the rest of the system intact.
Conclusion
Although my proposed change was rejected by the maintainer(because it solves the surface problem, not the root cause, and the goal of the project is to edit codes before lookup to ensure that no such data is passed to it), I learned a lot during the process of solving this problem, and it was a valuable experience. I hope some of you watching would try to solve a small bug in a project and contribute to it, because it helps a lot about open source than writing personal hobby projects.
Top comments (0)