I/O Multiplexing in C: Select, Poll, and Epoll

I/O multiplexing allows a network server written in C to monitor multiple socket descriptors concurrently using a single thread, eliminating the need to allocate dedicated threads or processes per client connection. Operating systems provide system calls—primarily select, poll, and Linux-specific epoll—that notify an application when one or more sockets are ready for non-blocking read or write operations. While all three mechanisms solve the fundamental concurrency bottleneck of synchronous blocking I/O, they differ significantly in their internal kernel architecture, memory overhead, API ergonomics, and algorithmic scalability.

The Concept of I/O Multiplexing

In a traditional blocking network model, calling read() or recv() on a socket stalls thread execution until data arrives from the client. To serve thousands of concurrent clients, a server would need thousands of threads, incurring severe context-switching overhead and memory consumption.

I/O multiplexing resolves this by setting client sockets to non-blocking mode (O_NONBLOCK via fcntl) and registering their file descriptors with an OS-level polling mechanism. The application suspends execution on a single system call until the kernel signals that network activity has occurred on at least one registered descriptor.

1. select(): The Legacy Standard

Introduced in BSD Unix, select() is defined in <sys/select.h> and is the most portable I/O multiplexing call.

int select(int nfds, fd_set *readfds, fd_set *writefds, 
           fd_set *exceptfds, struct timeval *timeout);

Mechanics

• Bitmasks: Sockets are tracked using fixed-size bit arrays (fd_set). Macros like FD_SET(), FD_CLR(), and FD_ISSET() manipulate these masks.
• In-Place Modification: The kernel modifies the passed fd_set pointers in place to indicate readiness. Consequently, the application must re-populate the sets before every invocation of select().

Limitations

• Descriptor Limit: Sockets cannot exceed FD_SETSIZE (typically hardcoded to 1024 in glibc). Sockets with descriptor numbers \(\ge 1024\) cause undefined behavior or buffer overflows.
• Linear Complexity (\(O(N)\)): The kernel iterates through all bits up to nfds to determine readiness. Upon return, the user space must also iterate through all descriptors up to nfds with FD_ISSET() to find which sockets fired.
• Repeated Copying: The entire bitmask state must be copied from user space to kernel space and back on every call.

2. poll(): Overcoming Fixed Limits

Standardized by POSIX in <poll.h>, poll() improves upon select() by ditching bitmasks in favor of a dynamic array of structures.

struct pollfd {
    int   fd;       /* file descriptor */
    short events;   /* requested events (e.g., POLLIN, POLLOUT) */
    short revents;  /* returned events */
};

int poll(struct pollfd *fds, nfds_t nfds, int timeout);

Mechanics

• Separation of Input and Output: events defines what to listen for, while the kernel writes results exclusively to revents. This eliminates the need to rebuild the tracking structure before each loop iteration.
• No Hardcoded Limit: The fds array can be dynamically allocated to accommodate any number of file descriptors permitted by system resource limits (RLIMIT_NOFILE).

Limitations

• Linear Complexity (\(O(N)\)): Like select(), both the kernel and the user application must perform an \(O(N)\) scan across the entire array on each iteration to check for ready sockets.
• Memory Overhead: The entire array of struct pollfd instances must be copied between user space and kernel space on every call, generating substantial overhead under high connection counts.

3. epoll(): High-Performance Scalability for Linux

Introduced in Linux 2.6 and defined in <sys/epoll.h>, epoll solves the \(O(N)\) scaling bottlenecks of select() and poll() by decoupling event registration from event waiting.

Core API

1. epoll_create1(int flags): Allocates an epoll instance in the kernel and returns an epoll file descriptor.
2. epoll_ctl(int epfd, int op, int fd, struct epoll_event *event): Adds (EPOLL_CTL_ADD), modifies (EPOLL_CTL_MOD), or removes (EPOLL_CTL_DEL) specific file descriptors within the kernel's interest list.
3. epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout): Blocks until one or more registered descriptors become ready, writing only the active events into the user-provided events buffer.

Architectural Advantages

• Persistent State in Kernel Space: Monitored descriptors are organized inside the kernel using a red-black tree. Descriptors are registered once; the application does not re-pass lists on every wait call.
• Constant-Time Notification (\(O(1)\)): The kernel uses hardware interrupts and internal device callbacks to place ready descriptors directly into a ready list (a doubly linked list).
• Sparse Event Retrieval: epoll_wait() returns only the descriptors that actually have events pending (\(O(K)\), where \(K\) is the number of active sockets), completely eliminating the need for linear scans across inactive connections.

Triggering Modes

• Level-Triggered (LT): Default behavior. epoll_wait() continuously reports a descriptor as ready as long as its buffer contains data.
• Edge-Triggered (ET): Enabled via the EPOLLET flag. The kernel notifies the application only when a state change occurs (e.g., new data arrives). To avoid dropped packets or hung connections, sockets must be non-blocking, and loops must drain the socket using read() or write() until encountering an EAGAIN or EWOULDBLOCK error.

Technical Comparison

For modern high-load network daemons on Linux (such as Nginx or Redis), epoll is the industry standard because its performance remains steady regardless of the number of idle connections. For cross-platform tools where connection counts remain low or deterministic, select() and poll() continue to provide portable alternatives.