Patterns from Linux Kernel
The Linux kernel has been refined over 30+ years. These patterns have survived decades of real-world use across millions of devices.
| Pattern | Where in Linux | What It Does |
|---|---|---|
| Bitmask | include/uapi/linux/stat.h | File permission bits (rwxrwxrwx) |
| Min Heap | kernel/sched/fair.c (CFS) | Completely Fair Scheduler — pick task with lowest vruntime |
| Ring Buffer | include/linux/ring_buffer.h | ftrace event logging, per-CPU lock-free buffers |
| State Machine | net/ipv4/tcp_input.c | TCP connection state machine (SYN_SENT → ESTABLISHED → FIN_WAIT) |
| Semaphore | include/linux/semaphore.h | Kernel counting semaphore with down()/up() |
| Backpressure | net/ipv4/tcp_output.c | TCP congestion window (cwnd) — flow control backpressure |
| Free List | mm/slub.c | SLUB slab allocator — intrusive free list with XOR-hardened pointers |
| Trie | net/ipv4/fib_trie.c | IP routing table as a compressed trie (LC-trie) |
| Vtable | include/linux/fs.h | file_operations struct — function pointer vtable for VFS dispatch (.read, .write, .open) |
| Batch Processing | block/blk-merge.c | Block layer merges adjacent I/O requests to amortize seek time |
| Rate Limiter | net/sched/sch_tbf.c | Token bucket filter for kernel traffic control |
| Reference Counting | lib/kobject.c | kref provides reference counting for kernel objects |
How They Compose: Reading a File
When a process calls read(), multiple patterns activate in a single syscall:
read(fd, buf, count)▼The VFS layer looks up the file's file_operations struct and calls .read(). ext4, NFS, procfs each provide their own implementation behind the same interface.
The kernel checks file permission bits (rwxrwxrwx) against the process's UID/GID. A single AND operation decides access.
Opening the file incremented its inode refcount. The kernel won't free the inode while any fd references it.
If the read triggers disk I/O, the block layer merges adjacent requests to minimize seek time before dispatching.
ftrace logs the syscall entry/exit into a per-CPU ring buffer for tracing.
The "everything is a file" abstraction works because vtable dispatch lets the kernel treat ext4 files, network sockets, and /proc entries identically. The bitmask permission check happens once regardless of filesystem type. And reference counting ensures no resource is freed while in use — even if another process deletes the file.