Strings on the Heap

The Byte You Have to Add Yourself

Chapter 4 gave you memory whose size is decided while the program runs. This chapter opened with the rule that a string of n characters needs n + 1 bytes. A heap string is both facts at once, and they meet in exactly one place: the number you hand to malloc. strlen(source) is the first half of that number, the characters you are about to copy, and it is the whole of what a careless request asks for. The terminator is the byte nobody asks for, because nobody types it, and on the heap there is no sizeof standing by to include it on your behalf. The next program is wrong on purpose, and the mistake is one absent token.

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

int main(void)
{
    const char *source = "borrowed";
    char *copy = malloc(strlen(source));

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

    strcpy(copy, source);
    printf("copied %s\n", copy);
    free(copy);

    return 0;
}

Everything else about it is right. The allocation is checked against NULL, nothing casts the malloc, the block is freed on the path that has one to free, and strcpy is copying eight characters into a block that strlen measured for those eight characters one line above. What the block has no room for is the ninth byte, and here gcc can see that:

warning: '__builtin_memcpy' writing 9 bytes into a region of size 8 [-Wstringop-overflow=]
   16 |     strcpy(copy, source);
note: destination object of size 8 allocated by 'malloc'

That is an unusually direct diagnostic and worth having, but take it as a gift rather than a guarantee, exactly as with last lesson's -Wstringop-overflow=. It exists because the compiler could follow both the strlen and the malloc back to the same literal. A source whose length arrives from fgets still draws a version of it, reading writing one too many bytes into a region of a size that depends on 'strlen', which is about as helpful as a compiler gets; put the allocation and the copy in different files, though, and there is nothing left for it to follow. What does not depend on the compiler's reach is the run:

==12==ERROR: AddressSanitizer: heap-buffer-overflow on address 0xfc1f8e5e0018
WRITE of size 9 at 0xfc1f8e5e0018 thread T0
    #0 0xffff8f9b27b8 in memcpy (/usr/local/lib64/libasan.so.8+0xd27b8)
    #1 0x0000004008cc in main /tmp/e.c:16
0xfc1f8e5e0018 is located 0 bytes after 8-byte region [0xfc1f8e5e0010,0xfc1f8e5e0018)
allocated by thread T0 here:
    #1 0x0000004008ac in main /tmp/e.c:8
SUMMARY: AddressSanitizer: heap-buffer-overflow /tmp/e.c:16 in main

Take chapter 4's four fields in order. Which kind: heap-buffer-overflow, so a heap block was touched outside itself. What was it doing: a WRITE of 9 bytes, the eight characters and the terminator together, which says strcpy never intended to stop at 8. Which line: the first frame in your own file, /tmp/e.c:16, the strcpy. The memory's story: the address is 0 bytes after 8-byte region, the very first byte past the end, and allocated by points at line 8. Nine bytes of string into an eight-byte block, and it is the last byte that falls off, which is the shape every missing + 1 has. Notice what the stack version of this bug had and this one does not. char destination[8]; carries its size in its declaration, so sizeof(destination) is there to check against and gcc knows the number at every call. Here the size was computed, so there is no declaration to consult and no sizeof to reach for. The only record of how big the block is is the arithmetic you wrote, and arithmetic that is short by one makes everything downstream confidently short by one. So write the rule into the arithmetic: malloc(strlen(source) + 1), every time, and never the bare strlen form at all.

make_copy, and Who Frees It

A copy is worth a function, because the two lines that make one belong together and because the ownership question then has a single place to be answered. char *make_copy(const char *source) takes a string it promises not to modify and returns a block the caller must free, which is chapter 4's make_ convention doing the job it was introduced for. Here it is inside the program that motivates heap strings in the first place.

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

char *make_copy(const char *source)
{
    char *copy = malloc(strlen(source) + 1);

    if (copy == NULL)
    {
        return NULL;
    }

    strcpy(copy, source);

    return copy;
}

int main(void)
{
    char line[64];
    char *longest = NULL;

    while (fgets(line, sizeof(line), stdin) != NULL)
    {
        size_t length = strlen(line);

        if (length > 0 && line[length - 1] == '\n')
        {
            line[length - 1] = '\0';
        }

        if (longest == NULL || strlen(line) > strlen(longest))
        {
            char *kept = make_copy(line);

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

            free(longest);
            longest = kept;
        }
    }

    if (longest == NULL)
    {
        printf("no lines\n");
        return 0;
    }

    printf("longest: %s\n", longest);
    free(longest);

    return 0;
}

Given the three lines one, four four and two it prints longest: four four, and given no input at all it prints no lines. Read make_copy first. malloc(strlen(source) + 1) is the last section's rule written once, in the one place it matters. Chapter 4's sizing idiom was count * sizeof *p, and it has not been abandoned here, it has collapsed: sizeof *copy is sizeof(char), which the standard defines to be 1, so (strlen(source) + 1) * 1 is the same number with more typing. char is the one type whose element size may be left out of the request, and it is left out because writing it changes nothing, not because the rule stopped applying. The NULL check is not decoration either, and what it does deliberately is report failure upward, since make_copy is not the function that knows what the program should do about it.

Then the strcpy, which last lesson told you never to write without a length check above it. There is no check above it and the call is still correct, and the reason is the line before: the destination's size was computed from this very source one line earlier, so the check would compare a number against itself. strlen(source) < strlen(source) + 1 is true for every source that exists, and a condition that cannot be false is not a safety check, it is noise. That is worth more than the one call it saves. The rule exists because a destination's capacity and a source's length are normally two independent facts; when you have just derived one from the other, the rule is discharged. Knowing why a rule is there is what tells you when it has been satisfied by construction rather than by an if. What comes back from make_copy is a pointer and an obligation. From the return onwards the block belongs to the caller: nothing in the type char * says so, the name and this sentence are the entire mechanism, and if main never frees it nobody will. That is chapter 4's ownership rule with a string in it instead of an int block, unchanged in every detail. One honest note before you write those three lines for the tenth time. POSIX has shipped a function that does exactly this for decades, strdup(source), it is available on essentially every system you will meet, and C23 finally brought it into the standard. This course targets C17 and writes its own, partly because make_copy is three lines you should be able to derive from the rule rather than recall from a manual, and partly because it changes nothing that matters: whatever allocated the block, somebody still has to free it.

The Buffer Is Reused, So Keep a Copy

Now the loop, and the reason any of this exists. char line[64] is one buffer, and fgets writes over it on every iteration, so the text of the first line survives only until the second line arrives. A program that wants to remember a line after reading the next one has to move it somewhere that is not line, and somewhere sized to fit, decided while the program runs, is the heap. That is the motivation in one sentence: the stack buffer is where lines arrive, and the heap is where the ones you keep go. free(longest); longest = kept; is the pair that matters, in that order. Assigning first would overwrite the only pointer to the old copy and orphan it, which is chapter 4's first leak shape exactly, arriving here once per improvement rather than once per program. So free before you replace. The first time round longest is still NULL and free(NULL) is a defined no-op, which is what lets the same two lines serve the first keep and every later one, and the allocation-failure path frees longest for the same reason a chapter 4 error path did: a program that gives up still owns whatever it was holding. What this program cannot do is enlarge a block it already has. Every keeper is a fresh allocation and a discarded old one, and resizing a block in place is the next lesson.

Sizes You Compute

Copying is the simplest computed size. Building a string from pieces is the general case, and the arithmetic is yours to get right, terminator included on purpose.

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

int main(void)
{
    const char *first = "hello";
    const char *second = "world";
    size_t size = strlen(first) + strlen(second) + 2;
    char *joined = malloc(size);

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

    snprintf(joined, size, "%s %s", first, second);
    printf("[%s] %zu bytes for %zu characters\n", joined, size, strlen(joined));
    free(joined);

    return 0;
}

That prints [hello world] 12 bytes for 11 characters. The 2 in strlen(first) + strlen(second) + 2 is two separate bytes with two separate reasons: one for the space going between the pieces, and one for the terminator going after them. Count the characters the result will contain, add a byte for every separator you are inserting, add one for the terminator, and that is your size. Then hand the writing to snprintf with the same size you just computed, because it always terminates and never writes past the size it is given, so an arithmetic slip becomes a truncated string instead of the report at the top of this lesson. Twelve bytes holding eleven characters is the n + 1 rule reporting for duty one last time.

Key Takeaways

• A heap string buffer is malloc(strlen(source) + 1). The + 1 is the terminator, and on the heap nothing supplies it for you, because the size is computed rather than declared and there is no sizeof to consult. Omit it and AddressSanitizer reports a heap-buffer-overflow with a WRITE landing 0 bytes after the region.
• Chapter 4's count * sizeof *p collapses for char, since sizeof(char) is defined to be 1, so malloc(length + 1) is the whole request. Check it against NULL every time, and never cast it.
• strcpy into a block sized from that same source needs no separate length check, because the check would compare strlen(source) against strlen(source) + 1. The rule is discharged by construction, not ignored.
• char *make_copy(const char *source) returns a block the caller must free. Ownership travels with the pointer exactly as chapter 4 described, carried by the make_ prefix and by what you wrote down, since char * says nothing. POSIX strdup does the same job and was standardised in C23; this course is C17 and writes its own.
• A line read by fgets lives only until the next call, because the buffer is reused, so keeping one means copying it to the heap. When you replace a kept string, free the old one before overwriting the pointer, or the copy is leaked; free(NULL) makes the first replacement safe with no special case.
• When you build a string, count every byte you are about to write. malloc(strlen(a) + strlen(b) + 2) is one byte for the separator and one for the terminator, and snprintf is the safe way to fill it.