Storage functionality

storage
files & directories access
Virtual File System
page cache
logical file systems
block devices
storage drivers

Storage functionality provides access to various storage devices via files and directories of files. Most of the storage is persistent as flash memory, SSD and legacy hard disks. Another kind of storage is temporary. The file system provides an abstraction to organize the information into separate pieces of data (called files) identified by a unique name. Each file system type defines their own structures and logic rules used to manage these groups of information and their names. Linux supports a plethora or different file system types, local and remote, native and from other operating systems. To accommodate such disparity the kernel defines a common top layer, the virtual file system (VFS) layer.

Summary of the Linux kernel's storage stack

Files and directories

Four basic files access system calls:

man 2 open ↪ do_sys_open _id - opens a file by name and returns a file descriptor (fd). Below functions operates on a fd.

man 2 close ↪ close_fd _id

man 2 read ↪ ksys_read _id

man 2 write ↪ ksys_write _id

File in Linux and UNIX is not only physical file on persistent storage. File interface is used to access pipes, sockets and other pseudo-files.

🔧 TODO

man 2 readlink , man 2 symlink , man 2 link

man 3 readdir ⇾ man 2 getdents

man 7 path_resolution

man 2 fcntl – manipulate file descriptor

⚙️ Files and directories internals

linux/fs.h _inc

fs/open.c _src

fs/namei.c _src

fs/read_write.c _src

📚 Files and directories references

Input/Output, The GNU C Library

VFS in Linux Kernel 2.4 Internals

Unix file types

File locks

File locks are mechanisms that allow processes to coordinate access to shared files. These locks help prevent conflicts when multiple processes or threads attempt to access the same file simultaneously.

💾 Historical: Mandatory locking feature is no longer supported at all in Linux 5.15 and above because the implementation is unreliable.

⚲ API

man 8 lslocks – list local system locks

man 3 lockf – apply, test or remove a POSIX lock on an open file

man 2 flock – apply or remove an advisory BSD lock on an open file

man 2 fcntl – manipulate file descriptor

F_SETLK _id – advisory record lock

F_OFD_SETLK _id – Open File Description Lock

flock _id – lock parameters

⚙️ Internals

linux/filelock.h _inc

fs/locks.c _src

trace/events/filelock.h _inc

Asynchronous I/O

🚀 advanced features

AIO

https://lwn.net/Kernel/Index/#Asynchronous_IO

man 2 io_submit man 2 io_setup man 2 io_cancel man 2 io_destroy man 2 io_getevents

uapi/linux/aio_abi.h _inc

fs/aio.c _src

io/aio _ltp

io_uring

🌱 New since release 5.1 in May 2019

https://blogs.oracle.com/linux/an-introduction-to-the-io_uring-asynchronous-io-framework

https://thenewstack.io/how-io_uring-and-ebpf-will-revolutionize-programming-in-linux/

io_uring_enter _id io_uring_setup _id io_uring_register _id

linux/io_uring.h _inc

uapi/linux/io_uring.h _inc

fs/.c _src

https://lwn.net/Kernel/Index/#io_uring

io_uring, SCM_RIGHTS, and reference-count cycles

The rapid growth of io_uring

Automatic buffer selection for io_uring

Operations restrictions for io_uring

io_uring, SCM_RIGHTS, and reference-count cycles

Redesigned workqueues for io_uring

io_uring _ltp

Non-blocking I/O

Allow non-blocking access to multiple file descriptors.

Efficient event polling epoll

⚲ API:

uapi/linux/eventpoll.h _inc

man 7 epoll

man 2 epoll_create ↪ do_epoll_create _id

man 2 epoll_ctl ↪ do_epoll_ctl _id

man 2 epoll_wait ↪ do_epoll_wait _id

⚙️ Internals:

fs/eventpoll.c _src

select and poll

💾 Historical: Select and poll system calls are derived from UNIX

⚲ API:

man 2 poll ↪ do_sys_poll _id

man 2 select ↪ kern_select _id

⚙️ Internals:

fs/select.c _src

Vectored I/O

🚀 advanced feature

Vectored I/O, also known as scatter/gather I/O, is a method of input and output by which a single procedure call sequentially reads data from multiple buffers and writes it to a single data stream, or reads data from a data stream and writes it to multiple buffers, as defined in a vector of buffers. Scatter/gather refers to the process of gathering data from, or scattering data into, the given set of buffers. Vectored I/O can operate synchronously or asynchronously. The main reasons for using vectored I/O are efficiency and convenience.

⚲ API:

uapi/linux/uio.h _inc

linux/uio.h _inc

iovec _id

man 2 readv ↪ do_readv _id

man 2 writev ↪ do_writev _id

⚙️ Internals:

iov_iter _id

do_readv _id ↯ call hierarchy:

vfs_readv _id

import_iovec _id

ext4_file_read_iter _id

lib/iov_iter.c _src

📚 References

Fast Scatter-Gather I/O, The GNU C Library

https://lwn.net/Kernel/Index/#Vectored_IO

https://lwn.net/Kernel/Index/#Scattergather_chaining

Virtual File System

The virtual file system (VFS) is an abstract layer on top of a concrete logical file system. The purpose of a VFS is to allow client applications to access different types of logical file systems in a uniform way. A VFS can, for example, be used to access local and network storage devices transparently without the client application noticing the difference. It can be used to bridge the differences in Windows, classic Mac OS/macOS and Unix filesystems, so that applications can access files on local file systems of those types without having to know what type of file system they are accessing. A VFS specifies an interface (or a "contract") between the kernel and a logical file system. Therefore, it is easy to add support for new file system types to the kernel simply by fulfilling the contract.

🔧 TODO: vfsmount _id, vfs_create _id, vfs_read _id, vfs_write _id

📚 VFS References

VFS _doc

VFS in Linux Kernel 2.4 Internals

Logical file systems

A file system (or filesystem) is used to control how data is stored and retrieved. Without a file system, information placed in a storage area would be one large body of data with no way to tell where one piece of information stops and the next begins. By separating the data into individual pieces, and giving each piece a name, the information is easily separated and identified. Each group of data is called a "file". The structure and logic rules used to manage the groups of information and their names is called a "file system".

There are many different kinds of file systems. Each one has different structure and logic, properties of speed, flexibility, security, size and more. Some file systems have been designed to be used for specific applications. For example, the ISO 9660 file system is designed specifically for optical discs.

File systems can be used on many different kinds of storage devices. Each storage device uses a different kind of media. The most common storage device in use today is a SSD. Other media that was used are hard disk, magnetic tape, optical disc, and . In some cases, the computer's main memory (RAM) is used to create a temporary file system for short-term use. Raw storage is called a block device.

Linux supports many different file systems, but common choices for the system disk on a block device include the ext* family (such as ext2, ext3 and ext4), XFS, ReiserFS and btrfs. For raw Flash without a flash translation layer (FTL) or Memory Technology Device (MTD), there is UBIFS, JFFS2, and YAFFS, among others. SquashFS is a common compressed read-only file system. NFS and another network FS are described further in paragraph Network storage.

⚲ Shell interfaces:

cat /proc/filesystems

ls /sys/fs/

man 8 mount

man 8 umount

man 8 findmnt

man 1 mountpoint

man 1 df

Infrastructure ⚲ API function register_filesystem _id registers structs file_system_type _id and stores them in linked list ⚙️ file_systems _id. Function ext4_init_fs _id registers ext4_fs_type _id. Operation of file system opening is called mounting: ext4_mount _id

⚙️ Internals:

fs/namespace.c _src

man 2 mount

do_mount _id

linux/buffer_head.h _inc

super_block _id

sb_bread _id

fs _src

fs/ext4/ext4.h _src

ext4_sb_bread _id

📚 References:

filesystems _doc

Kernel wikis: EXT4, btrfs, Reiser4, RAID, XFS

Page cache

A page cache or disk cache is a transparent cache for the memory pages originating from a secondary storage device such as a hard disk drive. The operating system keeps a page cache in otherwise unused portions of the main memory, resulting in quicker access to the contents of cached pages and overall performance improvements. The page cache is implemented by the kernel, and is mostly transparent to applications.

Usually, all physical memory not directly allocated to applications is used by the operating system for the page cache. Since the memory would otherwise be idle and is easily reclaimed when applications request it, there is generally no associated performance penalty and the operating system might even report such memory as "free" or "available". The page cache also aids in writing to a disk. Pages in the main memory that have been modified during writing data to disk are marked as "dirty" and have to be flushed to disk before they can be freed. When a file write occurs, the page backing the particular block is looked up. If it is already found in the page cache, the write is done to that page in the main memory. Otherwise, when the write perfectly falls on page size boundaries, the page is not even read from disk, but allocated and immediately marked dirty. Otherwise, the page(s) are fetched from disk and requested modifications are done.

Not all cached pages can be written to as program code is often mapped as read-only or copy-on-write; in the latter case, modifications to code will only be visible to the process itself and will not be written to disk.

⚲ API:

man 2 fsync ↪ do_fsync _id

man 2 sync_file_range ↪ ksys_sync_file_range _id

man 2 syncfs ↪ sync_filesystem _id

📚 References

wb_workfn _id

address_space _id

do_writepages _id

linux/writeback.h _inc

mm/page-writeback.c _src

Page cache

More

The future of DAX - direct access bypassing the cache

Linux Page Cache in Linux Kernel 2.4 Internals

Zero-copy

🚀 advanced features

Writing data to storage and reading are very resource consuming operations. Copying memory is time and CPU consuming operation too. Set of methods to avoid copying operations is called zero-copy. The goal of zero-copy methods is a fast and efficient data transfer within the system.

The first and simplest method is Pipeline, invoked by operator "|" in shells. Instead of writing data into temporary file and reading, the data is passed efficiently via a pipe bypassing a storage. The second method is tee.

⚲ Syscalls:

man 2 pipe2

man 2 tee, man 1 tee

man 2 sendfile

man 2 copy_file_range

man 2 splice

man 2 vmsplice

⚲ API and ⚙️ Internals:

man 2 pipe2 ↪ do_pipe2 _id - creates pipe

uses pipe_fs_type _id, pipefifo_fops _id

man 2 tee ↪ do_tee _id- duplicates pipe content

calls link_pipe _id

man 2 sendfile ↪ do_sendfile _id - transfers data between file descriptors, the output can be a socket. Used in network storage and servers.

Calls: do_splice_direct _id, splice_direct_to_actor _id

man 2 copy_file_range ↪ vfs_copy_file_range _id - transfers data between files

calls custom remap_file_range _id like nfs42_remap_file_range _id

or custom copy_file_range _id like fuse_copy_file_range _id

or do_splice_direct _id

man 2 splice ↪ do_splice _id - splices data to/from a pipe.

There are three cases regarding which end being a pipe:

1. do_splice_from _id - only input is a pipe

   Calls iter_file_splice_write _id or custom splice_write _id

   or default_file_splice_write _id: write_pipe_buf _id, splice_from_pipe _id, __splice_from_pipe _id

2. do_splice_to _id - only output is a pipe.

   Calls generic_file_splice_read _id or custom splice_read _id

   or default_file_splice_read _id: kernel_readv _id

3. splice_pipe_to_pipe _id - both are pipes

man 2 vmsplice ↪

vmsplice_to_pipe _id – splices user pages to a pipe

vmsplice_to_user _id – splices a pipe to user pages

⚲ API

linux/splice.h _inc

⚙️ Internals:

fs/pipe.c _src

fs/splice.c _src

🔧 TODO: zerocopy_sg_from_iter _id builds a zerocopy skb datagram from an iov_iter. Used in tap_get_user _id and tun_get_user _id.

skb_zerocopy _id

skb_zerocopy_iter_dgram _id

📚 References

man 7 pipe

man 7 fifo

splice and pipes _doc

Pipes API _doc

splice (system call)

LTP: pipe _ltp, pipe2 _ltp, tee _ltp, sendfile _ltp, copy_file_range _ltp, splice _ltp, vmsplice _ltp

Block device layer

Linux storage is based on block devices.

Block devices provide buffered access to the hardware, always allowing to read or write any sized block (including single characters/bytes) and are not subject to alignment restrictions. They are commonly used to represent hardware like hard disks.

⚲ Interfaces:

linux/genhd.h _inc

linux/blk_types.h _inc

block_device _id

alloc_disk_node _id allocates gendisk _id

add_disk _id

device_add_disk _id

block_device_operations _id

register_blkdev _id

bio _id - main unit of I/O for the block layer and lower layers (ie drivers and stacking drivers)

request _id

request_queue _id

⚙️ Internals.

block _src

block_class _id

👁 Examples:

drivers/block/brd.c _src - small RAM backed block device driver

drivers/block/null_blk _src

📚 References

Block devices _doc

Switching Scheduler _doc

BFQ - Budget Fair Queueing _doc

Deadline IO scheduler tunables _doc

Kyber I/O scheduler tunables _doc

Multi-Queue Block IO Queueing Mechanism (blk-mq) _doc

https://lwn.net/Kernel/Index/#Block_layer

LDD3:Block Drivers

LDD1:Loading Block Drivers

ULK3 Chapter 14. Block Device Drivers

Device mapper

The device mapper is a framework provided by the kernel for mapping physical block devices onto higher-level "virtual block devices". It forms the foundation of LVM2, software RAIDs and dm-crypt disk encryption, and offers additional features such as file system snapshots.

Device mapper works by passing data from a virtual block device, which is provided by the device mapper itself, to another block device. Data can be also modified in transition, which is performed, for example, in the case of device mapper providing disk encryption.

User space applications that need to create new mapped devices talk to the device mapper via the libdevmapper.so shared library, which in turn issues ioctls to the /dev/mapper/control device node.

Functions provided by the device mapper include linear, striped and error mappings, as well as crypt and multipath targets. For example, two disks may be concatenated into one logical volume with a pair of linear mappings, one for each disk. As another example, crypt target encrypts the data passing through the specified device, by using the Linux kernel's Crypto API.

The following mapping targets are available:

cache - allows the creation of hybrid volumes, by using solid-state drives (SSDs) as caches for hard disk drives (HDDs)

crypt - provides data encryption, by using the Linux kernel's Crypto API

delay - delays reads and/or writes to different devices (used for testing)

era - behaves in a way similar to the linear target, while it keeps track of blocks that were written to within a user-defined period of time

error - simulates I/O errors for all mapped blocks (used for testing)

flakey - simulates periodic unreliable behaviour (used for testing)

linear - maps a continuous range of blocks onto another block device

mirror - maps a mirrored logical device, while providing data redundancy

multipath - supports the mapping of multipathed devices, through usage of their path groups

raid - offers an interface to the Linux kernel's software RAID driver (md)

snapshot and snapshot-origin - used for creation of LVM snapshots, as part of the underlining copy-on-write scheme

striped - strips the data across physical devices, with the number of stripes and the striping chunk size as parameters

zero - an equivalent of /dev/zero, all reads return blocks of zeros, and writes are discarded

📚 References

Device mapper

Device mapper _doc

linux/device-mapper.h _inc

drivers/md _src

https://lwn.net/Kernel/Index/#Device_mapper

I/O scheduler

I/O scheduling (or disk scheduling) is the method chosen by the kernel to decide in which order the block I/O operations will be submitted to the storage volumes. I/O scheduling usually has to work with hard disk drives that have long access times for requests placed far away from the current position of the disk head (this operation is called a seek). To minimize the effect this has on system performance, most I/O schedulers implement a variant of the elevator algorithm that reorders the incoming randomly ordered requests so the associated data would be accessed with minimal arm/head movement.

The particular I/O scheduler used with certain block device can be switched at run time by modifying the corresponding /sys/block/<block_device>/queue/scheduler file in the sysfs filesystem. Some I/O schedulers also have tunable parameters that can be set through files in /sys/block/<block_device>/queue/iosched/.

⚲ Interfaces:

linux/elevator.h _inc

Function elv_register _id registers struct elevator_type _id.

elevator_queue _id

⚙️ Internals:

block/elevator.c _src

block/Kconfig.iosched _src

block/bfq-iosched.c _src

block/kyber-iosched.c _src

block/mq-deadline.c _src

include/trace/events/block.h _inc

📚 References:

I/O scheduling

Elevator algorithm

Switching Scheduler _doc

BFQ - Budget Fair Queueing _doc

Deadline IO scheduler tunables _doc

https://www.cloudbees.com/blog/linux-io-scheduler-tuning/

https://wiki.ubuntu.com/Kernel/Reference/IOSchedulers

Storage drivers

🔧 TODO

⚙️ Internals

drivers/scsi _src - Small Computer System Interface

drivers/virtio _src

drivers/sdio _src - Secure Digital Input Output

drivers/nvmem _src - Non Volatile Memory devices like EEPROM, Efuse

drivers/mtd _src - Memory Technology Device for 🤖 embedded devices

NVMe

NVM Express drivers provide accesses a computer's non-volatile storage. Local storage is attached via PCI Express bus. PCI NVMe device driver entry point is nvme_init _id. Remote storage driver is called target and local proxy driver is called host. Fabrics connect remote targets with local host. A fabric can be based on RDMA, TCP or Fibre Channel protocols.

⚲ API:

nvme-cli

uapi/linux/nvme_ioctl.h _inc

linux/nvme.h _inc

⚙️ Internals:

drivers/nvme _src

Host drivers/nvme/host _src:

⚲ Interfaces:

drivers/nvme/host/nvme.h _src

nvme_init_ctrl _id initializes a NVMe controller structures nvme_ctrl _id with operations nvme_ctrl_ops _id

a subroutine of nvme_scan_work _id adds a new disk with device_add_disk _id

nvme_init _id - local PCI nvme module init

nvme_probe _id

nvme_init_ctrl _id ...

nvme_pci_ctrl_ops _id

nvme_core_init _id - module init

Fabrics

⚲ interfaces:

drivers/nvme/host/fabrics.h _src

nvmf_register_transport _id resisters nvmf_transport_ops _id

nvmf_init _id - fabrics module init

⚙️ internals:

nvmf_init _id - fabrics module init

nvmf_misc _id

nvmf_dev_fops _id

nvmf_dev_write _id

nvmf_create_ctrl _id binds nvmf_transport_ops _id

Target drivers/nvme/target _src:

⚲ Interfaces: drivers/nvme/target/nvmet.h _src

nvmet_register_transport _id registers nvmet_fabrics_ops _id

nvmet_init _id - module init

fcloop_init _id - loopback test module init which can be useful to test NVMe-FC transport interfaces.

	NVMe over Fabrics
Layers	TCP	RDMA	Fibre Channel
Host modules	nvme_tcp_init_module id	nvme_rdma_init_module id	nvme_fc_init_module id
Fabrics protocols	linux/nvme-tcp.h inc	linux/nvme-rdma.h inc	linux/nvme-fc.h inc linux/nvme-fc-driver.h inc
Target modules	nvmet_tcp_init id	nvmet_rdma_init id	nvmet_fc_init_module id

👁 Example: nvme_loop_init_module _id nvme loopback

nvme_loop_transport _id - fabrics operations

nvme_loop_create_ctrl _id

nvme_loop_create_io_queues _id

nvme_loop_ops _id - target operation

nvme_loop_add_port _id

nvme_loop_queue_response _id

Appendices

🚀 Advanced

man 1 pidstat – reports task statistics

/proc/self/io – I/O statistics for the process (see man 5 proc)

💾 Historical storage drivers

drivers/ata _src - Parallel ATA

📖 Further reading about storage

bcc/ebpf storage and filesystems tools