Anatomy of a Heap Chunk

The HeapLesson 2 of 660 minutesLessonNo lab next

Somebody else’s data structure

The arrays and records in the last section gave you a useful starting point: you could read their declarations and then inspect how the compiler had laid them out. A program that calls malloc doesn’t tell you nearly as much. You know how many bytes it asked for, but that doesn’t tell you where the allocation will land or what will be sitting next to it.

Somebody still has to keep track of that memory. The allocator needs to know which regions are available and how large they are, and on glibc some of that bookkeeping sits right beside the bytes your program uses. glibc calls one of these internal blocks a chunk: it includes the allocation’s bookkeeping and the usable region returned to the program. Before we write past an allocation, let’s find out what we’d be writing into.

Safety note

This section is about one allocator

Use the supplied programs only in the isolated x86-64 Ubuntu course VM, with address randomization left enabled. The recorded layout is from glibc 2.39; a different allocator or configuration can change both the layout and the reuse policy. These are glibc inspection programs, not portable C examples to run unchanged on Windows or macOS.

Check ldd --version before comparing measurements. We’ll use the plain builds for allocator layout; AddressSanitizer and Valgrind replace allocation machinery, so their layouts answer a different question.

Learning objectives

By the end of this lesson

• Predict how many bytes malloc will actually give you for a request, and check it.
• Read the header that sits in front of an allocation and say what each field means.
• Work out where a neighbouring allocation’s header sits relative to your own pointer.
• Identify a separately mapped allocation from its flags, and measure when this run starts using one.

We aren’t overflowing anything yet. The inspection code deliberately reads outside the C allocation to examine glibc’s bookkeeping, so keep it in this unoptimized experiment rather than copying it into ordinary application code.

A stores counter

Create the working directory, then save the following program as stores.c there:

mkdir -p ~/underdunn-course/heap ~/underdunn-course/notes
cd ~/underdunn-course/heap
ldd --version

Use the nonnegative slot numbers and small successful allocations shown in the commands. The small command parser is an inspection aid, not a validated interface for arbitrary input.

/*
 * Stores counter. Issues crates of whatever size you ask for, hands them
 * back, and prints what the allocator actually did.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define CRATES 16

static void  *crate[CRATES];
static size_t asked[CRATES];

static void issue(int n, size_t bytes)
{
    crate[n] = malloc(bytes);
    asked[n] = bytes;
    printf("  crate %d: asked %zu, got %p, usable %zu\n",
           n, bytes, crate[n], malloc_usable_size(crate[n]));
}

static void header(int n)
{
    size_t *p = crate[n];

    if (!p) {
        puts("  no such crate");
        return;
    }
    printf("  crate %d at %p\n", n, (void *)p);
    printf("    p-0x10 = 0x%016zx\n", p[-2]);
    printf("    p-0x08 = 0x%016zx   size 0x%zx, flags%s%s%s\n",
           p[-1], p[-1] & ~(size_t)7,
           (p[-1] & 1) ? " PREV_INUSE" : "",
           (p[-1] & 2) ? " IS_MMAPPED" : "",
           (p[-1] & 4) ? " NON_MAIN_ARENA" : "");
}

static void gap(int a, int b)
{
    if (!crate[a] || !crate[b]) {
        puts("  no such crate");
        return;
    }
    printf("  crate %d is at %p, crate %d is at %p\n", a, crate[a], b, crate[b]);
    printf("  distance = %ld bytes\n",
           (long)((char *)crate[b] - (char *)crate[a]));
}

static void back(int n)
{
    free(crate[n]);
    crate[n] = NULL;
    printf("  crate %d returned\n", n);
}

static void sweep(void)
{
    size_t r[] = { 0, 1, 8, 16, 24, 25, 32, 40, 48, 56, 57, 88, 120, 1000 };
    size_t i;

    printf("  %-8s %-8s %s\n", "asked", "usable", "size field");
    for (i = 0; i < sizeof r / sizeof r[0]; i++) {
        void *p = malloc(r[i]);
        printf("  %-8zu %-8zu 0x%zx\n", r[i], malloc_usable_size(p),
               ((size_t *)p)[-1]);
        free(p);
    }
}

int main(void)
{
    char line[256];

    setvbuf(stdout, NULL, _IONBF, 0);
    puts("Stores counter.");
    puts("Commands: issue <n> <bytes>, header <n>, gap <a> <b>, back <n>, sweep, quit");

    memset(line, 0, sizeof line);
    while (fgets(line, sizeof line, stdin)) {
        line[strcspn(line, "\n")] = '\0';
        if (strncmp(line, "issue ", 6) == 0) {
            int n = atoi(line + 6);
            const char *sp = strchr(line + 6, ' ');
            issue(n % CRATES, sp ? (size_t)atol(sp + 1) : 0);
        } else if (strncmp(line, "header ", 7) == 0) {
            header(atoi(line + 7) % CRATES);
        } else if (strncmp(line, "gap ", 4) == 0) {
            int a = atoi(line + 4);
            const char *sp = strchr(line + 4, ' ');
            gap(a % CRATES, sp ? atoi(sp + 1) % CRATES : 0);
        } else if (strncmp(line, "back ", 5) == 0) {
            back(atoi(line + 5) % CRATES);
        } else if (strcmp(line, "sweep") == 0) {
            sweep();
        } else if (strcmp(line, "quit") == 0) {
            break;
        } else if (line[0] != '\0') {
            puts("  unknown command");
        }
        memset(line, 0, sizeof line);
    }
    return 0;
}

The only unusual thing here is p[-1], which reads the eight bytes immediately before your allocation. In ordinary code that is an out-of-bounds read and a bug. On this page it is the measurement.

gcc -g -O0 -fno-omit-frame-pointer -Wall -Wextra stores.c -o stores

No warnings.

What you asked for and what you got

Before you run anything, work out how many usable bytes you expect from malloc(1).

Run ./stores and enter:

sweep
quit

  asked    usable   size field
  0        24       0x21
  1        24       0x21
  8        24       0x21
  16       24       0x21
  24       24       0x21
  25       40       0x31
  32       40       0x31
  40       40       0x31
  48       56       0x41
  56       56       0x41
  57       72       0x51
  88       88       0x61
  120      120      0x81
  1000     1000     0x3f1

Three things in that table are worth stopping on:

• malloc(0) returns twenty-four usable bytes in this run. It does not return nothing and it does not return a null pointer. There is a smallest thing this allocator knows how to make, and you got one.

• The usable size moves in steps of sixteen. Requests of 16 and 24 share an allocation size, as do 32 and 40, and 48 and 56. The allocator rounds each request into a size it already works in.

• The size field is the usable size plus eight, with a bit set. Take 24, add 8, and you have 32, which is 0x20. The field reads 0x21. Strip the low bit and the sizes line up all the way down the table: 0x30 and 40, 0x40 and 56, 0x3f0 and 1000.

malloc_usable_size produced the middle column. It is a glibc inspection function that reports how many usable bytes this allocator placed behind a returned pointer. It helps us measure this layout, but it is not a portable replacement for the bound the application requested.

That last observation tells us that the number in front of the allocation describes the whole chunk, rather than just the part the program was given.

An arena is an allocator-managed pool from which glibc serves chunks. For the small allocations coming from this arena, add eight to the request, round up to a multiple of sixteen, and use a minimum chunk size of 32. Requests from 25 through 40 therefore all need a 48-byte chunk.

The glibc size calculation is named request2size if you want to compare the arithmetic with the implementation.

The two header words

Run ./stores and enter:

issue 0 24
header 0
quit

  crate 0: asked 24, got 0x5572429a72b0, usable 24
  crate 0 at 0x5572429a72b0
    p-0x10 = 0x0000000000000000
    p-0x08 = 0x0000000000000021   size 0x20, flags PREV_INUSE

Two words sit in front of the pointer you were handed:

• At p-0x08 is the size field. It holds this chunk’s size, with the bottom three bits used as flags. A size that is always a multiple of sixteen doesn’t need those bits.
• At p-0x10 is the previous chunk’s size, but only when the PREV_INUSE flag is clear. With that flag set, we can’t use this word to find the preceding chunk.

There are three flags to distinguish:

• PREV_INUSE tells the allocator not to consolidate backward into the previous chunk. A live preceding allocation has this bit set, but a chunk held in a tcache or fastbin can keep it set after free too. Those are caches for small freed chunks; the next lesson introduces the tcache by watching its reuse order.
• IS_MMAPPED marks a separate mapping. We’ll see one in the large-allocation comparison below.
• NON_MAIN_ARENA marks an allocation from another arena.

Here, PREV_INUSE is set, so the zero in the previous-size slot isn’t a usable size. That slot can even overlap another allocation’s usable data, as the next pair of allocations shows.

Two crates in a row

Run ./stores and enter:

issue 0 24
issue 1 24
issue 2 24
gap 0 1
gap 1 2
quit

  crate 0 is at 0x63820ed4c2b0, crate 1 is at 0x63820ed4c2d0
  distance = 32 bytes
  crate 1 is at 0x63820ed4c2d0, crate 2 is at 0x63820ed4c2f0
  distance = 32 bytes

Thirty-two, which is the chunk size rather than the twenty-four you were given. The allocations are laid end to end in this run, and each size field sits eight bytes before its returned pointer.

Look at the same memory through the debugger, which shows the whole run of it at once:

printf 'issue 0 24\nissue 1 24\ngap 0 1\nquit\n' > in.txt
gdb -q -batch -ex 'break gap' -ex 'run < in.txt' \
    -ex 'printf "crate 0 is at %p\n", crate[0]' \
    -ex 'x/6gx (char*)crate[0] - 16' ./stores

crate 0 is at 0x55555555a2b0
0x55555555a2a0:  0x0000000000000000  0x0000000000000021
0x55555555a2b0:  0x0000000000000000  0x0000000000000000
0x55555555a2c0:  0x0000000000000000  0x0000000000000021

Read that as six words:

• The first two are crate 0’s header.
• The next three are crate 0’s twenty-four usable bytes, running from 0x2b0 to 0x2c7.
• The last one, at 0x2c8, is crate 1’s size field, reading 0x21 again.

So crate 1’s size field begins 0x18 past crate 0’s pointer, and crate 1’s data begins 0x20 past it. Its two-word header starts earlier, at +0x10, which seems to overlap crate 0’s data. It does.

There is a detail hiding in the arithmetic. Crate 0 was given twenty-four usable bytes, ending at 0x2c7, and crate 1’s size field starts at 0x2c8. The word at 0x2c0, which is crate 1’s prev_size slot, is inside crate 0’s usable area.

The allocator lends that word to the previous chunk while the previous chunk is in use, which is exactly why a chunk of 32 bytes can give you 24 rather than 16.

Large allocations can get their own mapping

Large requests can be served by a separate mapping. Start a fresh process for this comparison and inspect the flags rather than relying on how far apart the addresses look.

Run ./stores and enter:

issue 0 131048
header 0
issue 1 131049
header 1
issue 2 262144
header 2
quit

  crate 0: asked 131048, got 0x58b6e99932b0, usable 131048
    p-0x08 = 0x000000000001fff1   size 0x1fff0, flags PREV_INUSE
  crate 1: asked 131049, got 0x58b6e99b32a0, usable 131064
    p-0x08 = 0x0000000000020001   size 0x20000, flags PREV_INUSE
  crate 2: asked 262144, got 0x7bc3509a9010, usable 266224
    p-0x08 = 0x0000000000041002   size 0x41000, flags IS_MMAPPED

The first two requests differ by one byte and cross a chunk-size boundary, but both still came from the arena in this run. The 256 KiB request carries IS_MMAPPED instead: glibc obtained a separate mapping, with a page-rounded size and room for its header.

The default mmap threshold starts at 128 KiB, but it isn’t a permanent boundary between two kinds of request. glibc can serve a large request from existing arena space, and freeing a separately mapped chunk can raise the threshold.

IS_MMAPPED tells us that the third allocation actually took that route, rather than the request crossing a magic number. If your flags differ, check the allocator version and its tunables, the configuration settings that can change allocation policy, before comparing the runs.

That mapping is released on free, rather than being put in the small-chunk cache we’ll examine next. Keep using the small requests for those experiments, where we’re interested in how an arena allocation is handed from one object to another.

Check the layout with a different request

Change both requests to 40 bytes. Before running them, work out:

• the chunk size;
• the distance between adjacent returned pointers;
• the offset from crate 0 to crate 1’s size field.

Then check your calculation. Run ./stores and enter:

issue 0 40
issue 1 40
gap 0 1
header 1
quit

Compare the offsets

Adding eight gives 48, already a multiple of sixteen, so each chunk is 0x30 bytes. If these two chunks are adjacent, the pointers are 48 bytes apart and the second size field is at offset 40 (0x28). Its value is 0x31 when PREV_INUSE is the only flag set. If you predicted 32, you’ve carried over the previous example’s chunk size rather than calculating the new one.

Knowledge check

Question 1 of 3

malloc(16) and malloc(24) both report 24 usable bytes. What does that tell you?

malloc_usable_size is reporting the request rounded to the nearest multiple of 8Both requests fall in the same rounded chunk-size classThe second allocation reused the first one's chunk

Check answer

When the results don’t match

• If your addresses differ from the transcripts, that is expected and nothing depends on it. Address randomization is on, and every claim on this page is about distances rather than locations.
• If the size fields differ, check ldd --version and use your own numbers. The arithmetic is what matters, not the constants.
• If gap 0 1 reports something other than 32, check that both issue commands asked for the same request of 24 bytes, and repeat in a fresh plain process. Matching sizes don’t guarantee adjacency in an arbitrary allocation history; gap is the check, not an assumption to work around.
• If header prints no such crate, the crate was returned or never issued. The program sets the pointer to NULL on back, so that slot no longer names an allocation.

To recover a known state, quit and start the program again. The stores counter keeps nothing between runs.

Check your understanding

Explain how a sequential write starting in crate 0 could reach crate 1’s size field in the measured layout.

Compare your reasoning

It has to write past the end of an allocation, because the next chunk’s size field is the first thing past it. There is no gap to absorb the mistake and no separate metadata region to keep the two apart. The header of the next allocation is in the direct path of any overflow from this one, which is the subject of Lesson 5.

That tells us where the metadata lives, but not whether the allocator checks it. We’ll examine those checks later in the section.

After the allocation is freed

The header tells us how much space a chunk occupies while the program is using it. Calling free doesn’t necessarily remove that memory from the process, though: the allocator may keep it ready for another request. Next we’ll return some chunks and find out which addresses come back.