Building get_next_line: A 93-line function that explains file descriptors, buffers, and the system call boundary
1,000,000 read() calls of 1 byte cost 100 seconds of pure syscall latency. My implementation reads from BUFFER_SIZE 1 to 10,000,000 without leaking a byte. This is the story of how a single function forced me to understand file descriptors, kernel buffers, and the boundary between user space and the kernel.
The problem
Write a function that returns one line at a time from a file descriptor. Compile with -D BUFFER_SIZE=n, where n can be anything from 1 to 10,000,000. No leaks, no UB, no crash, at any buffer size. A line can be as short as "\n" or the entire file without a single newline.
The constraints are the point. You are not allowed to know the input ahead of time, and the caller does not free what you haven't allocated cleanly. This is streaming, in its rawest C form.
What read() actually costs
Before designing anything, I ran the numbers on the primitive. read() is a system call: the process stops, the CPU switches from ring 3 to ring 0, the kernel validates the fd, walks to the disk or page cache, and copies bytes back to user space. Each crossing costs hundreds to thousands of CPU cycles, a fixed toll, whether you request 1 byte or 4096.
If the disk has ~0.1ms latency (SSD) and you issue 1,000,000 reads of 1 byte, that's 100 seconds of pure syscall latency before a single byte is processed. Reading 4096 bytes at once costs almost the same as reading 1. This is why the libc buffers printf, 100 printf calls do not become 100 system calls. Every real system is full of buffers for exactly this reason.
Why BUFFER_SIZE is a request, not a line size
BUFFER_SIZE is how many bytes your program asks the kernel for per call. The kernel does not guarantee the amount. It returns what it read, and that return value is the only truth. The naivest design, char buffer[BUFFER_SIZE] on the stack, segfaults at 10,000,000: the Linux stack defaults to ~8MB. The fix is one word: heap. buffer = malloc(BUFFER_SIZE + 1) moves 10MB to where memory is just memory, and the +1 exists because C strings end at '\0', the invariant that separates a string from garbage.
The one state the function is allowed to keep
get_next_line(fd) has a fixed signature and globals are banned, yet it must remember bytes it already consumed from the kernel. The answer is static: a static local lives in .bss, zeroed by the OS before main, while its visibility stays inside the function. Same word, two meanings in C: storage duration vs linkage. A counter proves it: a local prints 1, 1, 1 across calls; a static prints 1, 2, 3.
The remainder exists because of a hard fact of file descriptors: the kernel keeps the read offset, and it only moves forward. If you read 42 bytes and the newline was at byte 5, the other 37 bytes are already consumed, there is no unread. The fd is an int that indexes the kernel's table of open files (which is why the first open() returns 3: 0, 1 and 2 are stdin, stdout, stderr). Your program never sees that state advance; the remainder is how you mirror it in user space.
The return value is part of the contract
read() returns ssize_t, not size_t, because it must fit both "bytes read" and -1 (error). With size_t, -1 becomes SIZE_MAX, about 18 quintillion on 64-bit, and a comparison bytes == -1 is never true. My internal read loop mirrors read() with a three-state protocol: -1 error, 0 EOF, 1 got a line. The type of a return value is part of the API.
Results
The implementation is 93 lines: read and accumulate until a newline or EOF, extract the line, keep the overflow. The buffer is heap-allocated with room for the terminator, and after every read the byte at index bytes is set to '\0', null-termination exactly one byte past the last valid datum. Tested across the full suite: 128 cases with BUFFER_SIZE 1, 42, 9999 and 10,000,000, zero failures, zero leaks. It reads from stdin and from files, returns the final line without a trailing newline at EOF, and returns NULL forever after (read() at EOF returns 0 instantly; no infinite loop).
Trade-offs
The honest part. Each read appends via strjoin, which copies the entire accumulated remainder, O(n²) on a pathological long line read through a tiny buffer. It passed every tester, and it is still quadratic where a tail-copy design would be linear. The single static variable also means one fd at a time: interleaving two fds corrupts both remainders (the 42 bonus, one static managing many fds via a linked list, exists precisely for this). And the caller owns every returned line: the function guarantees allocation and freeing of its internal state, and nothing more. Simple, correct, and knowingly suboptimal in the corners.
Lessons
- Performance in I/O is a story about the user/kernel boundary, not about clever code. Count the crossings, then buffer.
- Memory from malloc comes dirty. The
'\0'is a convention only the programmer restores. - The return type is a contract.
size_tturns -1 into 18 quintillion silent falsehoods. - Complexity hides inside API details: an O(n)
strjoininside a loop becomes O(n²) without changing a single line's shape. - Newline at EOF is not an error; the empty string is not EOF; NULL is not a line. Streaming is 90% conventions.
A note on tooling
read(2) and malloc(3) man pages; valgrind for the leak discipline; the 42 norm (25 lines per function, 80 columns) as a forcing function; and a 128-case tester with extreme buffer sizes as the only honest judge.