Growing Buffers with realloc

The Block You Already Have

Last lesson ended with a program that could keep a line and could not enlarge one. Every keeper was a fresh malloc, a strcpy into it, and a free of the copy it replaced, which is exactly right when the new string has nothing to do with the old one and is the wrong shape entirely when what you want is the old string with more added to the end. realloc is the third function of the allocation trio and it exists for that case. realloc(pointer, new_size) takes a block you already own and a size you now want, and returns a pointer to a block of the new size holding the old contents, up to the smaller of the two sizes, so growing preserves everything you had written and shrinking keeps as much of it as still fits. On failure it returns NULL, and what that means for the block you handed it is the subject of the next section. One more fact belongs in the definition rather than in a footnote: realloc(NULL, size) does exactly what malloc(size) does, which is what lets a growth loop start from an empty buffer with no special case.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    char *text = malloc(8);

    if (text == NULL)
    {
        printf("could not allocate\n");
        return 0;
    }

    strcpy(text, "seven");

    char *grown = realloc(text, 32);

    if (grown == NULL)
    {
        free(text);
        printf("could not grow\n");
        return 0;
    }

    text = grown;
    strcpy(text + strlen(text), " and then some");
    printf("[%s] %zu characters in 32 bytes\n", text, strlen(text));
    free(text);

    return 0;
}

That prints [seven and then some] 19 characters in 32 bytes. Three lines carry the whole pattern and they happen in a fixed order: grown asks, if (grown == NULL) checks, text = grown accepts. Notice that only one free appears on the success path, because the block text used to name is not something you free after a successful realloc; whatever happened to it, it is no longer yours. And what happened to it is the part people find surprising. A successful realloc may or may not have moved your block, and you do not get to know which. The allocator may find the neighbouring bytes unclaimed and simply extend the block where it lies, returning the same address you gave it, or it may allocate a fresh block elsewhere, copy your contents across, release the old one, and hand you a different address. Both outcomes are successes, both preserve your string, and only one of them leaves the old pointer meaning anything. So treat the old pointer as stale the instant realloc returns: reading or writing through text after a realloc that moved it touches memory that has already been released, which is chapter 4's heap-use-after-free and undefined behaviour, reached without a single free call in your source. There is no run to show you here, because whether a block moves depends on the allocator's private bookkeeping and cannot be forced from your program. That is the reason the rule is unconditional rather than situational: overwrite the old pointer with the returned one and never mention the old one again.

The Assignment That Leaks

Now look at the shape the program above went to that trouble to avoid, because the short version is the one that gets written. The next program is wrong on purpose, and the mistake is that it is shorter. Since no allocator can be talked into failing on demand, the failure below is simulated: realloc_that_always_fails is a stand-in that keeps the one part of realloc's contract that matters right now, returning NULL without touching the block it was given. Everything else is the shape you would write with the real function.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *realloc_that_always_fails(char *block, size_t new_size)
{
    (void) block;
    (void) new_size;
    return NULL;
}

int main(void)
{
    char *text = malloc(8);

    if (text == NULL)
    {
        printf("could not allocate\n");
        return 0;
    }

    strcpy(text, "seven");
    printf("holding [%s]\n", text);

    text = realloc_that_always_fails(text, 32);

    if (text == NULL)
    {
        printf("could not grow\n");
        return 0;
    }

    printf("[%s]\n", text);
    free(text);

    return 0;
}

It prints holding [seven] and then could not grow, handles the failure it was told about, and exits 0. Afterwards this arrives on standard error:

==12==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 8 byte(s) in 1 object(s) allocated from:
    #0 0xffffbee64488 in malloc (/usr/local/lib64/libasan.so.8+0xd4488)
    #1 0x00000040082c in main /tmp/e.c:14

SUMMARY: AddressSanitizer: 8 byte(s) leaked in 1 allocation(s).

Eight bytes in one object, allocated at the malloc on line 14, which is the original buffer. Here is why it is still on the heap to be reported: realloc returning NULL frees nothing. Failure leaves the original block allocated, unchanged, and still yours, which is a generous contract and completely useless if you have thrown away its address. That is what the assignment did. text = realloc(text, ...) overwrote the only pointer to a live block with the NULL that reported the failure, so by the time the if runs there is nothing left to name in a free, and chapter 4's first leak shape is complete: a live block with no owner left. The printf before it exists only to keep gcc from deleting an allocation nothing ever reads, since this platform compiles at -O2; the leak is in the language either way. What makes this trap worse than the one you met in chapter 4 is that there you could see both blocks in your own source, while here the API springs it, because the expression that reports the failure is the expression that destroys the evidence. Every run with memory to spare looks perfect. The bad run happens on the day the machine is short of memory, which is the day you least want a second bug. So: assign a realloc to a temporary, check the temporary, and only then overwrite your pointer, with the failure branch freeing the original, which is still there waiting for you.

Capacity and Length

A buffer that grows needs two numbers where a fixed array needed none. Capacity is how many bytes you asked the allocator for. Length is how many characters you have actually written, terminator not counted, exactly as strlen counts. They are two different numbers with no reason to agree, and each has one job: capacity is the number you compare against before writing, and length is where the next write starts, which as a pointer is text + length. Keeping them in one variable is how buffers overrun, because the question "will this fit" and the question "where does it go" have different answers. This is the pair that replaces chapter 4's single element count once the size can change under you.

How much to grow by is the other decision, and everyone converges on the same answer. Growing by exactly what you need each time makes n characters cost about n calls to realloc, and every one of those calls may have to copy everything written so far, so the work grows with the square of the input. Doubling the capacity instead, 8 then 16 then 32 then 64, reaches n bytes in about log2(n) calls: a hundred thousand characters cost seventeen reallocations rather than a hundred thousand. The price is that the buffer can be almost twice the size of what it holds, which is memory you have asked for and are not using. Trading a bounded amount of unused memory for a logarithmic instead of linear number of copies is a bargain nearly every growable buffer takes, in C and in the standard containers of every language built on top of it.

Reading Input Nobody Measured

Here is the program the chapter has been walking towards: it reads everything on standard input, however much that turns out to be, into one heap buffer that grows to fit, and then hands it back with a count. The buffer starts at eight bytes on purpose, so that even a few lines of ordinary text force it to grow several times.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    size_t capacity = 8;
    size_t length = 0;
    char chunk[64];
    char *text = malloc(capacity);

    if (text == NULL)
    {
        printf("could not allocate\n");
        return 0;
    }

    text[0] = '\0';

    while (fgets(chunk, sizeof(chunk), stdin) != NULL)
    {
        size_t chunk_length = strlen(chunk);

        while (length + chunk_length + 1 > capacity)
        {
            char *grown = realloc(text, capacity * 2);

            if (grown == NULL)
            {
                free(text);
                printf("could not grow\n");
                return 0;
            }

            text = grown;
            capacity *= 2;
        }

        strcpy(text + length, chunk);
        length += chunk_length;
    }

    printf("%s", text);
    printf("%zu characters in a %zu byte buffer\n", length, capacity);
    free(text);

    return 0;
}

Piped three lines of prose, it echoes them and reports 86 characters in a 128 byte buffer: eight bytes doubled four times, 8 to 16 to 32 to 64 to 128, arriving at a size nothing in the program ever predicted. Four details are load bearing. The growth test is a while and not an if, because one 64-byte chunk arriving into a small buffer can need several doublings and a single one may still leave it short. The + 1 in length + chunk_length + 1 > capacity is this chapter's opening rule, still on duty: the characters need their bytes and the terminator needs one more. text[0] = '\0' before the loop matters for input that never arrives, since malloc does not initialize and printing a buffer with no terminator in it would be undefined behaviour rather than an empty line. And the growth failure path frees text before returning, which it can only do because grown took the NULL and left text pointing at the block that is still there. Two variables, one buffer, and a program whose memory use is decided entirely by its input.

Key Takeaways

• realloc(pointer, new_size) resizes a block you already own and preserves its contents up to the smaller of the old and new sizes. realloc(NULL, size) is malloc(size), which removes the special case at the start of a growth loop.
• A successful realloc may have moved the block. The old pointer is stale from that moment, and using it is heap-use-after-free with no free in sight. Take the returned pointer as the only address, and do not free the old one.
• realloc returning NULL frees nothing, so the original block is still allocated and still yours, which is why p = realloc(p, n); must never be written: on failure it overwrites the only pointer to a live block with NULL and leaks it, on the one run where memory ran short. Always char *grown = realloc(p, n); then check grown, then p = grown;.
• A growable buffer tracks capacity and length separately: capacity is what you compare against before writing, length is where the next write goes, at text + length.
• Grow by doubling. Reaching n bytes takes about log2(n) reallocations instead of n, at the cost of a buffer that may be up to twice the size of its contents.