§ 33 — select / poll Internals: 5 I/O Models · fd_set · do_select() · Kernel Wait Queues · O(n) Cost

1. Full Packet Path — NIC to Application (7 Layers of Kernel)

Before diving into select() mechanics, you must understand the complete path a packet takes from the NIC to your application. This is what actually triggers select() to return — and why it matters for performance.

Interactive: Step Through the Packet Journey

Click through each step to see exactly what happens in the kernel when a packet arrives and a process sleeping in select() wakes up.

Interrupt → SoftIRQ: Why Two Levels?

How the Socket is Found: inet_lookup_established()

When tcp_v4_rcv() receives an IP packet, it needs to find the right struct sock to deliver it to. This is a hash table lookup — not a linear scan.

2. § 33.1 — Five Stevens I/O Models

Richard Stevens (UNIX Network Programming §6.2) defined 5 I/O models. The critical difference is when the application blocks and who does the data copy. Only async I/O avoids both blocking and doing the copy.

Multiplexing vs Async: The Critical Distinction

I/O multiplexing (select/poll/epoll) is not async. It is readiness notification — the kernel tells you which fd is ready, then you call read() to fetch the data. Two syscalls, two phases. Async I/O (io_uring) submits the read and the kernel delivers the data directly — one operation, zero blocking.

Interactive: I/O Model Comparison

3. § 33.2 — select() Deep Dive: fd_set Bitmap & do_select()

The fd_set Bitmap

fd_set is a fixed-size bitmap of 1024 bits (128 bytes). Each bit represents one file descriptor. Bit n is set if fd n should be monitored.

Interactive: fd_set Bitmap Visualizer

Click fds to toggle them into the monitored set. Set which fd is "ready" and run the scan to see exactly how do_select() processes the bitmap — every bit, every fd.

do_select() Kernel Flow

The actual kernel implementation in fs/select.c:do_select() does exactly what you expect: iterate every fd bit, call vfs_poll() for each set bit, and sleep if nothing is ready.

The poll_table and __pollwait

The poll_table passed to vfs_poll() has a function pointer _qproc = __pollwait. Each socket's tcp_poll() calls sock_poll_wait(file, sock, poll_table) which calls __pollwait() to add the process to the socket's wait queue. This is how the process gets notified when data arrives.

Interactive: select() O(n) Scan Simulator

4. § 33.3 — poll() Deep Dive: pollfd Array & do_poll()

The pollfd Struct

poll() replaces the bitmap with an explicit array of struct pollfd. Each entry names an fd and the events to watch. The kernel fills revents on return.

do_poll() Flow

poll() Advantages Over select()

Interactive: poll() vs select() Comparison

5. § 33.4 — Kernel Wait Queues: The Blocking/Wakeup Engine

This is the most important section for understanding IO multiplexing at the kernel level. The wait queue is the mechanism by which a process gives up the CPU when nothing is ready, and gets it back when data arrives. This is how select() can monitor thousands of fds efficiently — it does not poll in userspace; the kernel wakes it up.

Wait Queue Data Structures

Full Wakeup Sequence (from Interrupt to do_select() returning)

How a Process Goes from SLEEPING to RUNNING

The state transition happens in try_to_wake_up() in kernel/sched/core.c:

Interactive: Thundering Herd — Wait Queue Simulator

Simulate three processes all sleeping in select() on the same socket. When data arrives, watch how all three wake up and only one gets the data.

The Thundering Herd Problem

When multiple processes call select() on the same socket, all of them register a wait_queue_entry in the socket's wait queue. When data arrives, wake_up_interruptible_all() wakes all of them. Each wastes a context switch and O(n) fd scan, but only one gets the data.

epoll solves this with EPOLLEXCLUSIVE (Linux 4.5): marks the wait queue entry as exclusive (WQ_FLAG_EXCLUSIVE), so only one process is woken per event. SO_REUSEPORT is an alternative: each process gets its own socket; the kernel load-balances new connections.

Wait Queue Cleanup on Wakeup

6. § 33.5 — FD_SETSIZE Limit & O(n) Cost Analysis

Why FD_SETSIZE = 1024 Is a Hard Limit

FD_SETSIZE is defined in <sys/select.h> as 1024. The fd_set struct is statically sized: 128 bytes (1024 bits). You cannot pass nfds=2000 to select() without allocating a custom oversized fd_set — and even then, glibc macros will overflow.

Per-Call Cost Breakdown at N=10,000 Connections

The C10K Problem

Dan Kegel's 1999 “C10K problem” identified that with 10,000 concurrent connections and 100 events/second:

• Blocking model: 10,000 threads × ~8 MB stack = 80 GB RAM. OS limit ~few thousand threads.
• select(): 10,000 fd scans × 100 events/sec = 1,000,000 vfs_poll() calls/sec. 99.99% wasted. Plus fd_set copy overhead. Plus hit FD_SETSIZE=1024 anyway.
• poll(): Same O(n) scan; no fd limit. But 10K × 8 bytes = 80KB copied kernel↔user per call × 100/sec = 8MB/sec of pointless kernel↔user copies.
• epoll: Only ready fds are ever touched. Cost is O(k) where k is the number of active connections. 10,000 idle connections cost exactly 0. This is the fix.

When select() / poll() Are Acceptable

• N < 50–100 fds: O(n) cost is negligible; code simplicity wins
• Short-lived connections: setup overhead matters less than at steady-state
• Portability: select() works everywhere; epoll is Linux-only
• stdin + a few network fds: typical CLI tool use case
• But: never use select() if any fd might be > 1023 (file descriptors from daemon code commonly exceed this)

7. Interview Prep — Questions This Page Answers