tail(1): Rebuilding tail from Scratch in C

The First Tool That Reads Backward

In the last two chapters we built cat and head. Both share a comfortable property: they move forward. cat reads until EOF. head reads until a limit. Both know where they're going from the moment they start.

tail breaks that. Its job is to show the last N lines of a file. To know what the last lines are, you need to know where the file ends, and to know where it ends, you have to reach it first.

That asymmetry is the whole problem. With head, we could stop early. With tail, we can't.

Errata: corrections to `head`

Before we build on the previous chapter, here is what it got wrong.

// errata 02: head

A single dash did not mean standard input. By long convention, - as a filename means "read stdin here", so head - should behave like head with no arguments. Ours printed nothing. The cause is in is_numeric(): given the empty string it returns true, because the loop that inspects the characters never runs. So head - parsed as the -NUMBER shorthand with a number of zero, and a limit of zero produces no output. A predicate that answers "yes" about an empty string is worth fixing wherever it appears.

Read errors were treated as end of input. Both streaming functions stopped on bytes_read <= 0, which collapses two different outcomes: zero means the input finished, negative means it failed. A file that becomes unreadable halfway through produced truncated output, silently, with a successful exit status. The previous chapter got this right and checked for -1 explicitly; this one lost it.

The write() return value was still ignored. Carried over from cat, and it will keep being carried until we build the shared library that does it properly in one place.

Rethinking tail

Most people think of tail as "head but from the other end." That's a reasonable starting point, but it misses the actual design challenge.

head gives you a prefix. Getting a prefix is easy: start reading and stop after N units. tail gives you a suffix. Getting a suffix is harder, because you can't know where it begins until you know where the data ends.

There's another complication: tail has to handle two fundamentally different kinds of input.

files vs streams: why tail has two modes

Regular files let you seek. Pipes and stdin don't. tail detects which situation it's in at runtime and picks the right strategy.

The C Concepts: Circular Buffer + lseek

Approach 1: Circular Buffer (works on anything)

The universal approach: read the entire input, keeping only the last N lines in memory at any time. When the input ends, print whatever we kept.

The data structure that makes this possible is a circular buffer: an array that wraps around. Imagine 10 slots. New lines fill slots 0 through 9. When slot 10 would be needed, we write to slot 0 instead, overwriting the oldest line. The "head" pointer always points to where the next write will go.

circular buffer: animated (N=6)

Each arriving line fills the next slot. When the buffer is full, new lines overwrite the oldest. The amber slot is where the next write goes: the "head" pointer.

// the key expression

head = (head + 1) % MAX_LINES. This one line is the entire circular buffer mechanism. The modulo operator wraps the index back to zero when it reaches the end of the array. That's it.

Approach 2: lseek (regular files only, much faster)

lseek() moves the read position of a file descriptor to any byte offset. For regular files, this is a kernel operation with no I/O; it just updates a number. For pipes and terminals, it fails with ESPIPE.

lseek signature

off_t lseek(int fd, off_t offset, int whence);

/* whence controls the reference point: */
SEEK_SET  /* offset from beginning of file */
SEEK_CUR  /* offset from current position  */
SEEK_END  /* offset from end of file        */

/* to get file size: */
off_t size = lseek(fd, 0, SEEK_END);

lseek: jumping backward to count newlines

tail -n 10 on a 2 GB file: reads the last few kilobytes, counts 10 newlines backward, seeks to that position, streams forward. Never touches the rest of the file.

The Build

Universal Version: Circular Buffer

tail.c: circular buffer (works on pipes too)

void    tail_lines_universal(int fd, int n)
{
    char    lines[MAX_LINES][MAX_LINE_LEN];
    char    buffer[BUFFER_SIZE];
    ssize_t bytes_read;
    int     head;
    int     total;
    int     line_pos;
    int     count;
    int     start;
    int     j;
    int     i;

    head     = 0;
    total    = 0;
    line_pos = 0;
    while ((bytes_read = read(fd, buffer, BUFFER_SIZE)) > 0)
    {
        i = 0;
        while (i < bytes_read)
        {
            lines[head % n][line_pos] = buffer[i];
            line_pos++;
            if (buffer[i] == '\n' || line_pos == MAX_LINE_LEN - 1)
            {
                lines[head % n][line_pos] = '\0';
                head++;
                total++;
                line_pos = 0;
            }
            i++;
        }
    }
    if (bytes_read < 0)
    {
        write(2, "tail: read error\n", 17);
        return;
    }
    if (line_pos > 0)
    {
        lines[head % n][line_pos] = '\0';
        head++;
        total++;
    }
    count = (total < n) ? total : n;
    start = (total < n) ? 0 : head - count;
    j = 0;
    while (j < count)
    {
        int idx;
        int k;

        idx = (start + j) % n;
        k   = 0;
        while (lines[idx][k])
            k++;
        write(1, lines[idx], k);
        j++;
    }
}

// known limitations of this version

The circular buffer carries two honest constraints. Each slot is a fixed MAX_LINE_LEN bytes, so a line longer than that gets split across two slots. And the number of slots is fixed when we compile. Both come from the same root cause: we are storing lines in a static array because we cannot yet allocate memory at runtime. The real tail uses dynamic allocation to handle lines and counts of any size. We reach for malloc for the first time in the sort episode. Until then, fixed buffers are a deliberate, documented trade.

Seekable Version: lseek for Regular Files

tail.c: seekable path (fast for large files)

void    tail_lines_seekable(int fd, int n)
{
    char    buffer[BUFFER_SIZE];
    ssize_t bytes_read;
    off_t   size;
    off_t   pos;
    int     lines_found;
    int     i;

    size = lseek(fd, 0, SEEK_END);
    if (size < 0)
    {
        write(2, "tail: cannot seek\n", 18);
        return;
    }
    if (size == 0)
        return;
    pos         = size;
    lines_found = 0;
    while (pos > 0 && lines_found <= n)
    {
        off_t chunk;

        chunk = (pos > BUFFER_SIZE) ? BUFFER_SIZE : pos;
        pos -= chunk;
        lseek(fd, pos, SEEK_SET);
        bytes_read = read(fd, buffer, chunk);
        if (bytes_read <= 0)
            break;
        i = bytes_read - 1;
        if (pos + bytes_read == size && buffer[i] == '\n')
            i--;
        while (i >= 0)
        {
            if (buffer[i] == '\n')
            {
                lines_found++;
                if (lines_found == n)
                {
                    lseek(fd, pos + i + 1, SEEK_SET);
                    while ((bytes_read = read(fd, buffer, BUFFER_SIZE)) > 0)
                        write(1, buffer, bytes_read);
                    return;
                }
            }
            i--;
        }
    }
    lseek(fd, 0, SEEK_SET);
    while ((bytes_read = read(fd, buffer, BUFFER_SIZE)) > 0)
        write(1, buffer, bytes_read);
}

/* detect which approach to use */
void    tail_lines(int fd, int n)
{
    off_t   probe;

    probe = lseek(fd, 0, SEEK_END);
    if (probe == -1)
        tail_lines_universal(fd, n);
    else
        tail_lines_seekable(fd, n);
}

The dispatch function is the design, not a workaround. Call lseek(). If it returns -1, the file descriptor is a stream, so we fall back to the circular buffer. If it succeeds, use the fast path. The program never has to ask the user which kind of input it's dealing with.

Walking the Backward Scan

The seekable line path is the subtle one, so let's trace it on a tiny file. Five lines, forty-nine bytes, and we want the last three:

tail -n 3: counting newlines from the end

file (49 bytes):
  line one\n      bytes  0..8     newline at 8
  line two\n      bytes  9..17    newline at 17
  line three\n    bytes 18..28    newline at 28
  line four\n     bytes 29..38    newline at 38
  line five\n     bytes 39..48    newline at 48  (the final one)

scan backward from the end, skip the trailing newline at 48:
  byte 38: '\n'  -> lines_found = 1
  byte 28: '\n'  -> lines_found = 2
  byte 17: '\n'  -> lines_found = 3 == n   STOP

the last 3 lines begin at byte 18.
seek there, stream forward:
  line three
  line four
  line five

The whole file was read once, and only the bytes from offset 18 onward were written out. Swap the forty-nine-byte file for a two-gigabyte log and the shape does not change. tail -n 10 reads the last few kilobytes, finds ten newlines, seeks once, and streams. It never touches the rest of the file. That is the entire reason the seekable path is worth the extra code.

Byte Mode: the Easy Twin

Everything so far counts lines. The -c flag counts bytes instead, and on a seekable file it is almost trivial. We know the file size and how many bytes we want, so we jump straight to size - n and stream to the end. No backward scan, no newline counting.

tail.c: byte mode, seekable

void    tail_bytes_seekable(int fd, int n)
{
    char    buffer[BUFFER_SIZE];
    ssize_t bytes_read;
    off_t   size;

    size = lseek(fd, 0, SEEK_END);
    if (size < 0)
    {
        write(2, "tail: cannot seek\n", 18);
        return;
    }
    if (n >= size)
        lseek(fd, 0, SEEK_SET);
    else
        lseek(fd, -n, SEEK_END);
    while ((bytes_read = read(fd, buffer, BUFFER_SIZE)) > 0)
        write(1, buffer, bytes_read);
}

For a stream, where we cannot seek, byte mode falls back to the same circular-buffer idea as lines, except the ring holds raw bytes instead of whole lines. The dispatch is identical: probe with lseek, and if it fails, keep the last N bytes in a ring as they flow past. One flag, two strategies, chosen by the same runtime probe we already wrote for lines.

The Comparison

criterion	circular buffer	lseek
works on pipes/stdin	yes	no
works on regular files	yes	yes
reads entire file	yes	no
fast on 2 GB file	slow	fast

What About `-f`?

The real tail has one more flag worth naming: -f, for "follow." tail -f logfile keeps running after it reaches the end of the file, printing new lines as they are appended. It is what you leave open in a terminal while watching a server log fill up.

With what we already know, a first version is short:

tail.c: a naive follow loop

void    tail_follow(int fd)
{
    char    buffer[BUFFER_SIZE];
    ssize_t bytes_read;

    while (1)
    {
        bytes_read = read(fd, buffer, BUFFER_SIZE);
        if (bytes_read > 0)
            write(1, buffer, bytes_read);
        else if (bytes_read == 0)
            sleep(1);
        else
        {
            write(2, "tail: read error\n", 17);
            break;
        }
    }
}

It works, but it polls once a second whether or not anything changed. The real tail -f on Linux uses inotify, a kernel facility that wakes a program the moment a file changes, so it reacts instantly and burns nothing in between. inotify deserves its own episode, and it will get one once we have the vocabulary for it. For now, notice the gap: the naive version sleeps when it should not, and that itch is exactly the motivation for a better mechanism.

The Test

bash: compile and compare

$ cc -Wall -Wextra -o mytail tail.c

# default: last 10 lines
$ diff <(tail tail.c) <(./mytail tail.c)

# explicit count
$ diff <(tail -n 3 tail.c) <(./mytail -n 3 tail.c)

# more lines than the file has
$ diff <(tail -n 1000 tail.c) <(./mytail -n 1000 tail.c)

# force the pipe path (circular buffer)
$ diff <(cat tail.c | tail -n 5) <(cat tail.c | ./mytail -n 5)

# large file: watch the speed difference
$ seq 1000000 > big.txt
$ time tail -n 10 big.txt
$ time ./mytail -n 10 big.txt

Run that last test on a file with a million lines. You should see a meaningful timing difference between the seekable path and what the circular buffer would need to do.

What We Actually Learned

tail forced us to face a problem the first two tools never had: you can't know where the end is until you've reached it. That constraint produced two legitimate solutions, each valid under different conditions.

The circular buffer is universal. It requires nothing from the OS beyond read(). It works on any input. Its only cost is reading everything, which matters a lot on large files.

The seekable path is efficient. It jumps directly to the data we care about. But it requires a regular file and the kernel's cooperation through lseek().

This is a pattern that comes up constantly in systems programming: not one best solution, but a set of approaches, each valid under different constraints, selected at runtime based on what the environment provides. The dispatch function is not an awkward compromise. It's exactly how real Unix utilities work.

Don't just read this one. Build it, then make it earn its design. Run it on a file with a million lines and time both paths. Feed it a pipe and confirm it falls back to the circular buffer. Then write the -f polling loop and watch it sleep when it should not. The frustration you feel at that one-second lag is the reason inotify exists, and you will appreciate it far more for having felt the gap first.

Next: lines, the first tool in this series that doesn't exist in Unix. We design it from scratch, which is harder than matching an existing spec.