The Heap

Every variable you have declared so far lives on the stack^[1] — the region of memory managed automatically by the function call mechanism. When a function is called, the stack grows to hold its local variables. When the function returns, the stack shrinks and those variables are gone. You cannot return a pointer to a local variable because the storage it pointed at no longer exists.

char    *bad_function(void)
{
    char  buf[16];
 
    tci_strcpy(buf, "hello");
    return (buf); /* bug: buf disappears when the function returns */
}

When you need storage that outlives the function that creates it — a string you allocate in one function and use in another, a list node that persists until you explicitly free it — you need the heap^[2].

malloc

malloc asks the operating system for n bytes of heap memory and returns a pointer to the start of it. You must #include <stdlib.h> to use it.

On bare metal there is no operating system to ask. The r-tier console targets — Mega Drive, PS1, Dreamcast — each come with an SDK that provides its own heap allocator in place of the standard one.

The interface is similar, but memory is scarce and fragmentation is a real concern: a Mega Drive has 64 KB of RAM, a PS1 has 2 MB. Each r-tier chapter introduces the allocator its SDK provides and the memory budget you are working within.

#include <stdlib.h>
 
char  *s;
 
s = malloc(6); /* room for "hello" and its null terminator */

s now points at 6 bytes of heap memory. Those bytes are uninitialized — they contain whatever was in memory before. Use tci_memset or tci_bzero to clear them, or write to them before reading from them.

malloc can fail. If the operating system has no memory left, it returns NULL. You must check before dereferencing the pointer:

s = malloc(10);
if (!s)
    return (NULL); /* or handle the error */

!s is shorthand for s == NULL. If malloc returned NULL and you dereference it anyway, the program crashes.

Run man 3 malloc — the manual specifies that the returned memory is uninitialized; reading it before writing produces undefined behaviour.

free

free returns the memory back to the heap:

free(s);

After this call, the memory s pointed at is no longer yours. Using it — reading from it, writing to it, passing it to another function — is undefined behaviour. The program may crash, silently corrupt data, or appear to work. Accessing freed memory is one of the hardest bugs to diagnose because the symptom often appears far from the cause.

A common defensive practice is to set the pointer to NULL after freeing it:

free(s);
s = NULL;

Dereferencing NULL crashes immediately with a clear error, which is easier to debug than a later corruption.

Run man 3 free — the manual specifies that passing NULL to free is a no-op, which is why the s = NULL pattern is safe.

The discipline of freeing in the right order becomes important when allocations nest. A linked-list node holds a pointer to the next node; to free the list correctly you must free every node before discarding the pointer to it — walking from the first node to the last, inner before outer.

Right now we would do that with a loop. In c05, when we build the linked-list API, a function will handle this by calling itself: free the rest of the list, then free this node. Each call solves a smaller version of the same problem. That pattern is recursion — the call stack takes over the job of remembering what is still left to free.

tci_calloc

tci_calloc allocates memory for an array of count elements each of size bytes and returns a pointer to the zeroed block. It is equivalent to malloc(count * size) followed by tci_bzero, but with one critical addition: it guards against the multiplication overflowing size_t. Requesting 2,000,000,000 elements of 4 bytes each produces count * size = 8,000,000,000 — which exceeds the 32-bit maximum and wraps to a small number, causing malloc to allocate far less memory than requested. tci_calloc detects the overflow and returns NULL instead of a dangerously undersized allocation.

The caller owns the allocation and must free it.

Create tci_calloc.c:

#include "libtci.h"
#include <stdlib.h>
 
void    *tci_calloc(size_t count, size_t size)
{
    void    *ptr;
    size_t  total;
 
    if (count == 0 || size == 0)    /* zero-element or zero-size array: nothing to allocate */
        return (NULL);
    total = count * size;
    if (total / count != size)      /* overflow check: wrapped multiplication won't round-trip */
        return (NULL);              /* don't allocate a dangerously undersized block */
    ptr = malloc(total);
    if (!ptr)                       /* allocation failed: propagate NULL to caller */
        return (NULL);
    tci_bzero(ptr, total);           /* zero every byte: this is what distinguishes calloc from malloc */
    return (ptr);
}

total / count != size is the overflow check. If count * size wrapped around, dividing the result back by count will not recover size — the division catches the inconsistency and returns NULL before any allocation happens.

Run man 3 calloc — the standard specifies that calloc returns zeroed memory; the tci_bzero call is what makes this true in our implementation.

Add tci_calloc.c to SRCS and its declaration to libtci.h:

void    *tci_calloc(size_t count, size_t size);

Memory leaks

A leak occurs when you allocate memory and never free it. The memory stays reserved until the process exits. A small leak in a short-lived program is harmless. A leak in a function called a thousand times per second will exhaust memory.

valgrind finds leaks. The command you used in f05/04 applies directly:

valgrind --leak-check=full ./your_program

If libtci allocates memory and your test program never frees it, valgrind will name the allocation site. The tester for this chapter runs valgrind on every test case.

tci_strdup

tci_strdup is the libc function strdup — same name, same behaviour, POSIX-standard. It duplicates a string: allocates a fresh copy on the heap and returns a pointer to it.

The need arises in two common situations. The first is ownership: a function that builds a string internally and needs to return it to the caller must allocate on the heap, because local buffers disappear when the function returns. The second is mutability: a string literal like "hello" lives in read-only memory — writing to it is undefined behaviour. Passing it through tci_strdup gives you a heap-allocated copy you can freely modify.

The caller owns the allocation. Every string returned by tci_strdup must eventually be passed to free.

This is the function that makes the + 1 rule visible. tci_strlen returns the number of characters before \0. The allocation needs room for the characters plus the \0 itself:

Create tci_strdup.c:

#include "libtci.h"
#include <stdlib.h>
 
char    *tci_strdup(const char *s)
{
    char    *copy;
    size_t  len;
 
    len = tci_strlen(s);              /* measure once; needed for both malloc and memcpy */
    copy = malloc(len + 1);          /* +1 reserves the byte for '\0' */
    if (!copy)                       /* allocation failed: propagate NULL to caller */
        return (NULL);
    tci_memcpy(copy, s, len + 1);     /* copy characters and the '\0' in one pass */
    return (copy);                   /* caller owns this allocation and must free it */
}

tci_memcpy(copy, s, len + 1) copies len characters plus the null terminator in one operation. The + 1 appears in both the malloc call and the memcpy call: one to reserve the byte, one to copy it.

Writing malloc(len) and tci_memcpy(copy, s, len) is the classic mistake. The string appears correct in many tests — the byte after the allocation often happens to be zero — until it is not, and then you get a string function that runs past the end and reads garbage. valgrind and AddressSanitizer both catch this.

Run man 3 strdup — strdup is POSIX; it allocates strlen(s) + 1 bytes and copies the string, which is exactly what our implementation does.

Add tci_strdup.c to SRCS and its declaration:

char    *tci_strdup(const char *s);

Testing tci_strdup

Write a quick manual test before continuing. Create test_strdup.c in your working directory — not as part of the library, just as a throwaway check:

#include "libtci.h"
#include <stdlib.h>
#include <stdio.h>
 
int main(void)
{
    char  *s;
 
    s = tci_strdup("hello");
    if (!s)
        return (1);
    printf("%s\n", s);
    free(s);
    return (0);
}

Compile and link against the library:

gcc -Wall -Wextra -g -std=c99 test_strdup.c -L. -ltci -I. -o test_strdup

-L. tells the linker to look for libraries in the current directory. -ltci tells it to link libtci.a (the lib prefix and .a suffix are stripped; you name the library by its middle part). -I. tells the compiler to look in the current directory for header files, so #include "libtci.h" resolves correctly.

Run it under valgrind:

valgrind --leak-check=full ./test_strdup

You should see hello printed and zero leaks reported. The free(s) in main is what keeps the leak count at zero. Remove it, rerun valgrind, and see what it reports.

Delete test_strdup.c and test_strdup when you are done. The tester covers tci_strdup more thoroughly than a manual test can.

tci_strndup

tci_strndup is the length-limited variant of tci_strdup. Where tci_strdup copies an entire string, tci_strndup copies at most n characters. The result is always null-terminated, even if the source string is longer than n. It is the n-variant companion to tci_strdup, just as tci_strncmp is to tci_strcmp.

Create tci_strndup.c:

#include "libtci.h"
#include <stddef.h>  /* size_t */
 
char    *tci_strndup(const char *s, size_t n)
{
    char    *copy;
    size_t  i;
 
    copy = tci_calloc(n + 1, 1);      /* +1 for null terminator */
    if (!copy)
        return (NULL);
    i = 0;
    while (i < n && s[i]) {          /* stop at n or at '\0', whichever comes first */
        copy[i] = s[i];
        i++;
    }
    return (copy);                   /* caller owns this allocation */
}

tci_calloc zero-initialises the buffer, so the null terminator at position i is already there when the loop exits — no explicit copy[i] = '\0' is needed.

Add tci_strndup.c to SRCS and its declaration to libtci.h:

char    *tci_strndup(const char *s, size_t n);

Run man 3 strndup — strndup is POSIX.1-2008 and available on Linux and BSD. This is the libtci version.

The rule

Every string that malloc allocates needs tci_strlen(s) + 1 bytes. Every time. The only exception is if you are storing a fixed-size buffer and you know at compile time exactly how many bytes it needs. For every dynamic string function on this page — and any you write that allocates space for a string — len + 1 is the rule.

The library now has twenty-nine functions. The next page covers building and linking the complete library: what libtci.a actually is, how to link against it from another program, and what the build produces.