From File to Device: VFS, Page Cache, Queues, and DMA
VFS is not a filesystem but it's part of the kernel that live in kernel/vfs/.
moving to btrfs, but first in order to realy understand btrfs, vfs is a prerequisite that why we'll understand VFS, then btrfs . VFS is not a filesystem but it's part of the kernel that live in kernel/vfs/, an intermediate between the kernel and the filesystem, example multiple filesystem mounted on the same directory "/", not that the directory is mounted in two filesystems, but /dev/sda is XFS mounted, /dev/sdb is ext4 mounted, and the interaction with those two is different, in order for the kernel to not for each filesystem use a different approach and differente code, the VFS handle this, when the kernel want to write, it make the same function to VFS write(), then the VFS identifie which filesystem is this, and use it's needed code and method or implementation. and it's part of the kernel not the filesystem. and it handle this with structure: struct super_block, struct inode ..., and for each filesystem there is structures that match the filesystem structure, the question here is how it identifie which filesystem is this ? we already know, it's the magic number, each filesystem has a magic number shared universally in all same filesystems. for the VFS perspective all inodes are the same across al filesystem because in the end it stores the file's metadata, however in filesystem each filesystem has it s own inode structure. so VFS stores whatever's filesystem in the same structure but retrieve the inode with different methods depending on the structure. update: i did a misake i moved directly to the implementation which made things ambigious, however i ll understand the flow then connec this, architecture, flow, implementaiton so the questions now are :
how a vfs map a path to a mounted filesystem ? more how does it know that /dev/sda is a mounting point ?
when accessing a file for first time with open() it creats a struct dentry a struct that tells if this is a mounting point if yes what is the root inode is it pointing at, and which filesystem is mounted . the specifique structure of a dentry is but before a dentry is cashed till the shutdown errasing memory, open() does not just create a dentry but it opens the file descriptor of that file, and the open() returns an integer along with other metadata, that integer is the index of the fd in the file descriptor table, and the file descriptor is a buffer, like stdout -> 2 stdin -> 1, that file will have an index in the fd table. so close() does not delete or free the struct dentry instead it close the fd . the correct structure of a dentry.
but first the filemeta data are stored depending on the kernel version kernel version means vfs version, old kernels store is like this
struct dentry {
...
unsigned int d_hash;
char* d_name;
unsigned int len;
...
}while modern kernel has qstr :
struct dentry {
// name, hash and length
struct qstr d_name; // filename "report.txt" along with some metadata
struct inode *d_inode; // pointer to the inode
// parent and siblings
struct dentry d_parent; // parent directory of this file
struct list_head d_child; // siblings dentrys in the same directory
struct list_head d_subdirs // child or sub dentrys
// mount
struct mount *d_mnt; // if a filesystem is mounted in this dentry point here
// reference countring
atomic_t d_count; // usage counter
// status flags
unsigned int d_flags; // DCACHE_VALID, DCACHE_NEGATIVE, etc
// operations
struct dentry_operations *d_op; // depens on the filesystem
// caching
struct hlist_node d_hash; // hash tbale link
...
}and the sqtr structure is but first what qstr stand for ? stand for quick string because for a simple name, the kernel should first calculate the length then the hash then strcmp of the name your looking for and the name it found qstr make this faster by storing those metadata :
struct qstr {
u32 hash;
u32 len;
const unsigned char *name;
}there are some fields that needs attention first one is :struct mount *d_mnt; // if a filesystem is mounted in this dentry point here
what the struct mount that d_mnt point to contain ? so the actual structure is too large and i ll stick with the important fields because i m not planning to because a vfs developper, so this is it :
struct mount {
struct mount *mnt_parent; // parent mount
struct dentry *mnt_mountpoint; // where this mount is attached
struct vfsmount mnt; // the vfs visible mount
...
}so struct mount *mnt_parent, this field contain a pointer to another same mount structure . needed for cases like :
mnt /dev/sda1 /data -t ext4 # creates mount a
mnt /dev/sdb /data/document -t xfs # creates mount bso struct mount *mnt_parent; of the mounting point b, contain the struct mount of the mounting a.
even if the fs mounted is differente, we already mentionned that it's normal for vfs to handle multiple fs .
walking to /data/docs, for each opened file by file we also mean directory, a dentry structure is created that live the entire session till the ram is errased (shutdown), the dentry stores the qstr structure that stores filename, hash, length , inode information , other fields… and the mount structure, outside of the dentry a another structure struct path, which is a nested structure, that stores current dentry & current mount, so walking to /data, create dentry the cfs perform a lookup_mount(), search in the vfs mounting table, the mounting table stores key value paires conceptualy
{
hash [(mounting point parent, '/data'dentry)] = mounting point (structure) child
}parent or root mointing point is stored inside all dentrys, the vfs first create or walk to the dentry, then perform the lookup_mount(current_dentry, vfs_mounting_table), current dentry is /data dentry
containing root or parent mounting point and it's own metadata, compare hashs, returns the the mount structure, now /data is a mounting point, walking to /data/docs, current dentry setted to docs dentry, perform lookup_mount(), case 1: /docs is a mounting point, current mount setted to /docs
mount structure, if it's different fs treated differently . case 2: is not a mounting point, current mount is /data mount structure . visualization :
walking /data/docs
1: create "/data" dentry, found in "/" dentry, root dentry
2: check "/data" is a mounting point ?
lookup_mount(...) -> yes, returns "/data" mount a
3: replace
current dentry = "/data" dentry
current mount = mount a
4: find "/data/docs" dentry inside "/data" dentry
5: check "/data/docs" is a mounting point
lookup_mount(...) -> no, NULL
6: replace
current directory = "/data/docs"
current mount = mount anote: check mount is after assigning current dentry. not before . things are too simple .
when read() is called, what is the chain reaction the sequence of functions ?
where does the inode come from ? how the vfs find it and how the filesystem send it or load it ?
and this universal structure is embeeded inside the filesystem custom structures. based on the filesystem details attached to the structure. called i_private (inode_private), example :
struct ext4_inode_info {
[ext4 specifique fields];
struct inode vfs_inode;
}the specifique vfs shared inode struct :
struct inode {
// file indentification
unsigned long i_inode; // inode number unique in a fileystem
// file metadata
loff_t i_size; // file size in bytes not blocks
kuid_t i_uid; // owner
kguid_t i_gid; // owner group
umode_t i_mode; // permession (rwx) and file type
struct timespec64 i_atime; // last access time, last time the file was open
struct timespec64 i_mtime; // last modification time
struct timespec64 i_ctime; // last change time; change != modif we already understand it
// linking infos
unsigned int i_nlink; // number of hard links
blkcount_t i_blocks; // number of block used by inode not just data blocks but also metadata, indirect pointers ...
struct inode_operations *i_op; // inode operation, this field is setted by the fs (mkdir, chmod ...)
struct file_operations *i_fop; // file operation, this field is setted by the fs (read, write ...)
// filesystem references
struct super_block *i_sb; // pointer to super block (the owner of the structure)
}the structure here is very clear, simple and logical .
question here is when the i_op and i_fop are setted ? in mounting operation, fields in inode are the inode common metadata shared across all the filesystems …
for xfs structure, we should first remember and understand some topics . mounting is when plugging linking the filesystem (hard drive), the kernel should interact with the filesystem somewhere, like /mnt/data, but not explicitly /mnt you can point in whatever point . quota we alreadt understand it, it's the limit or the maximum size that a user / group can have. i_imap is the physical adress where the inode is stored. copy on write is for optimization copying a file is creating a hard link, preventing redunduncy, for btrfs is the default behaviour unless specified to copy the actual inode and data, while for xfs nomal copy is the default, for copy on write it should be specified. fork is simple instead of storing all the inode metadata in one field, but store the content metadata like the blocks or the extents where the data are located or stores the actual tree b-tree not normal data or extents in an array, then stores the copy on write metadata like the blocks shared between more than one inode. and attribute fork we already understanded attributes that stores the file's metadata, owner, group, comment …
struct xfs_inode {
// inode linking and identification
struct xfs_mount *i_mount; // mounting point
struct xfs_dquot *i_udquot; // user disk quota
struct xfs_dquot *i_gdquot; // group disk quota
struct xfs_dquot *i_pdquot; // project disk quota
// inode location
xfs_ino_t i_ino; // inode number
struct xfs_imap i_imap; // location on disk for lookup
// extents informations
struct xfs_ifork *i_cowfp; // copy on write extents
struct xfs_ifork i_df; // data fork (b-tree or extents)
struct xfs_ifork i_af; // attributefork
// transaction & locking
struct xfs_inode_log_item *i_item; // logging information
struct rw_semaphore i_lock; // inode lock
atomic_t i_pincount; // pin count for I/O
}for the last three fields, *i_item when writting data or updating a file, first the kernel take the whole file content and put it into memory (ram), then write the modification into the file's ram content, when saving, (after delayallocation … already talk about this), it write the whole file content in the content space in disk, but the fields *i_item is for metadata a pointer to another structure, this structure that contain the fields which fields did changed in the metadata, to log into journal, content is optimized with delayed allocation, while metadata is optimized to not write the whole metadata but only the fields that *i_item track .
second i_lock, when a process, thread, core, a second cpu, wants to access data, first it check it's lock. if it's locked then it unlock it use it, lock it and leave. if another process try to access the data check the lock find it unlocked then it will wait till the first process finished, lock the data then process 2 is called, unlock, use, lock .semaphore is the lock. why not accessing simultaniously ? because if process 1 try to read it, and process 2 modified it, then process 1 wil lread modified data, or the data can be corrupted or ..., then the pin the pin is an important feature attomic number that can be incremented and decremented safly, giving three process 1 2 3, process one arrived pin is 0, process 2 arrived pin is incremented 1, process 3 arrived pin is incremented 2, process one unlock, read, lock, decrement pin = 1, process 2 unlock, try to free check pin != 0, another process is waiting for this data should wait till pin is 0 then free, unlock. process 3 arrived unlock write lock decrement pin = 0, process 2 is called pin is 0, safe free . if process 3 try to write or read a freed data, will lead to unknown behaviour . the question here is what if two processes try to free ? is it a deadlock ? so there is a background logworker process that checks pinning for deadlocks, if deadlock is deteted, force unpinning. now that we coverd vfs layer, we'll jump to page cache and block layer (blk-mq), understand page cache | I/O queue | I/O schedular | vfs operations .
introduction to the fourth topics, so page cache is the buffer that stores files data, obviously, each file has it page cache buffer, I/O queue is the operations queue, submiting whatever operation, the operation is first queued, sorted sometimes merged with I/O schedular algortihms by the vfs, and all those operations are vfs operations .
the four stacks are highly related, when the vfs perform a read(), the request do not goes directly to disk, it will be extremly slow to perform all operations interacting with disk, instead when opening a file, the file content and metadata ..., goes into page cache, a section at an offset, that stores the file, after this all the operations are performed on ram . this makes it faster, when performing an operation that change data or metadata, the data stores in ram are considred dirty, means that it is modified only on ram, not on disk .when vfs perform an operation on a file, first the kernel checks the page cache, is inode N at offset X present, if yes -> perform the operation on it, if no -> generate an exception
page fault, the question here is how does it know that inode is in offset x ? the response is the vma (virtual memory area) . the page fault is handled by the kernel, thats when it reads from disk
a process opens file.txt, note: open not read, because open does not load the file content, it set the metadata needed to interact with the file . open file.txt, file descriptor created already mentionned allow interaction with the file.
so when open file.txt READ a file descriptor is created that belongs to the file along with struct file and struct inode how ? the kernel gives the vfs the metadata stored in the parent directory that maps each filename to it's inode, and struct file that i don't know yet what it's role update : the structure file stores like the session like the content file offset; example the cursor is on line 75 char 30 but as a ram offset like 1126 byte after the first file content adress along the the fd index. what is the role of fd ? the integer is the index in fd table that maps the integer to struct file, then mmap allocate the buffer or space needed for that file with permission on that buffer and create the vma. then performing read file.txt an operation with low or same permission as open, like open write, while open read, kernel can't mmap write, on the page cache, kernel checks page cache, if present execute the operation, if not call vfs with metadata; inode number ..., vfs reads from disk return data, kernel stores to page cache, execute the operation . the vma is the structure that has metadata about that page cache, before performing an operation about that buffer we should know why where and what . this is why struct vma. question here is why there is two cases : page cache present | page cache absent . so we already mentionned that when interacting with a file, metadata along with content is kept temporary in ram . so when performing another operation it may find it or not . data are the same processes are different .
so when opening a file, open create a filedescriptor, that file descriptor in the fd table points to struct file, which is also created in open that struct contain the inode struct, and struct file has al lthe metadata about that file such as inode number, that it s taken from the parent directory of that file, and then mmap allocate the buffer page cache or space needed on the virtual memory for that file along with permission on that page cache that should be either low or same as open permissions and set the pointer of that page cache to the struct file, then creates the vma which stores metadata about that buffer such as which file back the buffer, the offset … so when performing an operation on that page cache the kernel should know on what the operation is executing, then the operation example read the page cache kernel checks if that buffer which the struct file is pointing at is already loaded, if yes execute the operation if no call the vfs to read the disk inode number is known, an returns data. then execute the operation .open file.txt READ, the open function return an integer, that integer is the index of file descritor in the fd table, that maps the file to it's struct file, that contain struct inode both are created on open, we already mentionned that the parent directory map each file to it's inode number, so inode number is taken from the parent directory, then mmap which is the function that setts the mapping of the buffer or space or page cache in memory that the will handle the file, and creates the struct vma that contain metadata about that page cache such as the file backing the page cache, the permissions on that page cache that should be low or same as the open permissions and maps the file to it's virtal memory adress. i think that i should make a topic on the virtual memory and physical memory, then an operation like read, that is performed on the file page cache specifiquely on the virtual ram adress, here there are two cases, first is that the virtual ram adress is not assigned to a physical adress, thats when the kernel raise a page fault captured then linked to a physical adress, or the page is already loaded by another prosses already mentionned that the file stay in ram for sometime, to minimize disk operations, then the operation occures with no exception . we'll see the implementation later
jumping to block layer, starting by I/O queue. so early hard drive could make on I/O op at a time, hardware had evolved, with ability to do operations in parralele. and machine support multiple cpus, multiple processes do I/O operations. the kernel should support this advantage, so it should request multiple I/O at a time. that why there are two queues software queue and hardware queue, and both are before the driver with hardware queue as the very last step before the driver .
difference is that software queue is the cpu queue, requests queue while hardware queue is the hard drive's queue, the gate queue . based on what software queue is created ? for each cpu or cpu group a software queue is created. all the I/O ops of that process queued in it's own update: the processes I/O ops are queued in it's executing cpu in the cpu's softawre queue, while hardware queue it depens on the device, if it support 5 ops at a time, 5 hardware queues are created . and the kernel maps one or more software queue to one or more hardware queue in three cases :
software queue 0 --> hardware queue 0
software queue 1 --> hardware queue 1
software queue 2 --> hardware queue 2or
software queue 0 --|
software queue 1 --| -> hardware queue 0
software queue 2 __| or
|---hardware queue 0
software queue 1 --|---hardware queue 0
|---hardware queue 2 I/O scheduling increase fetching data performance and scale, part of block layer sitting between the fs and the block device driver
software queue -> I/O schedul -> hardware queue -> device driver -> storage hardware, why requests should be scheduled ? if there are no scheduling the requests will be FIFO, whatever request came first will be treated till it ends, this makes things unefficient, a process may wait forever or minutes, instead algorithms are used to re order the queue, not just reorder sometimes merge or batch the request, and scheduling depens on hardware storing device, because each one has it's own hardware queuing approch, there main algorithms mq-deadline, BFQ and kyber or no scheduling, mq-deadline order the queue (software queue) incremently, example giving three requests A B C:
request A -> block 402
request B -> block 386
request C -> block 512
mq-deadline ordering
request B -> block 386
request A -> block 402
request C -> block 512why incremently ? because in order to travel to block 512 we pass by block 386 and block 402, so the three requests will be merged in one retrieving the data needed .
second is BFQ which is a round robin algorithm that assigns sector budget instead of time slices we queue is FIFO order but each request get a sector limit, example 500 sector, if a request need to fetch 600 sector it will complete it in two cycle, first 500 sector second 100. making it as a circular chain .
third is a new efficient for fast storage device algorithm that works with token, new requests consume token, completed request returns token, and there is a token limit, a visualized example :
max tokens = 300
current requests = 201
available tokens = 101current requests are consuming 300 - 101 = 199 token, new token can be treated in limit to consume ≠ or < than the available tokens, so it's not about requests instead there is a token rate limit .
or no scheduling used in newer devices that has it's own internal scheduling process, so scheduling in the software level will be a wasted compution a cpu overheading .
after this the device driver takes control, receive the request return another one that says read sector 8000, length 8 sectors, put data in DMA 0x50000000 then raise an interrupt that ends the operation process, here is the twist, the kernel does not receive a response then write it to the memory, instead it receive only interruption to kill the process and it's the device driver that write to memory, and the reason is involve the kernel makes it slower, so how does it do that ? and how does it know the destination adress ? the ram adress is passed with the request but not as a fields, a structure and a function are involved in this, first is scatter-gather struct scatterlist[] which contain multiple scatter-gather , second is dma_map_sg() direct memory adress map scatter-gather, the device driver cannot use the virtual adress because it belongs to the kernel, it uses the physical ram adress, but scatter struct provide only the ram page and the offset, that when the dma_map_sg(), maps the page and offset to a physical ram adress, cpu is not involved in the whole operation it's the mmu ship that does this and the writing to physical ram. not the struct scatterlist[] contain all the page invloved with DMA operations .
struct scatterlist[N] {
{
.page = &page_cache_page; // ram page
.offset = x; // offset after the page adress
.length = 4096; // data that need to be writen length
.dma_adress = 'unknown'
},
};this is passed with the request. then driver call dma_map_sg()
int dma_map_sg(
struct device *dev;
struct scatterlist *sg; // the scatterlist elemnt
int nents; // is how many element in scatterlist
enum dma_data_direction direction; // direction
);each device is represented, the kernel represent it with a struct device, because each one is treated differently, and have it s own limits, permission ..., *sg is the pointer to the scatter-gather element in scatterlist, nents is not how many element the scatter list can have, not the size of that list, but how many element is present, example the list can support up to 1000 element but only 10 are there, so nents is 10, direction can be three cases.
RAM -> device enum DMA to device
device -> ram enum DMA from device
bidirectional enum DMA_BIDIRECTIONALand then the function returns the new scatter-gather number; that need to be = || < than nents . why is that ? because if it find two or more scatter-gather that are sequential, it merge it into one scatterlist entry . example :
entry 0
page 100
length 4096 bytes
entry 3
page 101
length 4096 bytesthose are scatterlist entries, merge it into one entry .
entry 0
page 100
length 8196 bytesthen the dma_map_sg that takes the scatter-gather along with other data, write the physical adress to the structure . and this is how the device write to the ram . then programming the device :
nvme_device->lba = 8192; // sector to read
nvme_device->dma_addr = 0x5000000; // put data location
nvme_device->length = 4096; // data length
nvme_device->start() // trigger the operation