Chunk Reuse and the tcache

The HeapLesson 3 of 660 minutesLessonNo lab next

The question a stale pointer depends on

Suppose a program frees a record but keeps a pointer to it. The address hasn’t changed, but the program no longer owns the allocation at that address. If another record lands there, using the old pointer may read or change the new record instead. That’s a rather different problem from simply reading some leftover bytes.

To arrange that replacement, we need to know which freed chunk a new request will receive. We’ll start with three allocations and watch their addresses, then change the number and size of the requests to see where the pattern stops holding.

Learning objectives

By the end of this lesson

• Predict which allocation a malloc will return after several have been freed, and check it.
• Explain the size-class and cache-state conditions behind the observed reuse order.
• Show how the tcache affects that order by turning it off for one process.
• Say what breaks the correspondence between what you freed and what you get.

Use the isolated x86-64 Ubuntu course VM with ASLR enabled and the plain build shown below. The recorded allocator is glibc 2.39. We retain old address values to identify reused storage, but aren’t using those old pointers to access an object here.

A returns desk

Create the working directory if needed and enter it in the Ubuntu terminal:

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

Keep that glibc version with your results. Save the complete program below as returns.c; it doesn’t extend another source file. Use counts from 1 to 32 and the sizes shown below, with a fresh process for each experiment; the command parser doesn’t validate arbitrary inputs.

/*
 * Returns desk. Fills a rack with crates, empties it, and fills it again,
 * reporting which of the original crates each new one turned out to be.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define RACK 32

static void  *held[RACK];
static int    held_count;
static void  *mark[RACK];
static int    mark_count;

static void fill(int count, size_t bytes)
{
    int i;

    if (count > RACK) count = RACK;
    for (i = 0; i < count; i++) {
        held[i] = malloc(bytes);
        mark[i] = held[i];
    }
    held_count = mark_count = count;
    printf("  filled %d crates of %zu (chunk 0x%zx)\n", count, bytes,
           ((size_t *)held[0])[-1] & ~(size_t)7);
    for (i = 0; i < count; i++)
        printf("    crate %2d at %p\n", i, held[i]);
}

static void empty(void)
{
    int i;

    for (i = 0; i < held_count; i++) {
        free(held[i]);
        held[i] = NULL;
    }
    printf("  returned %d crates, lowest index first\n", held_count);
    held_count = 0;
}

static void refill(int count, size_t bytes)
{
    int i, j;

    if (count > RACK) count = RACK;
    printf("  asking for %d crates of %zu again\n", count, bytes);
    for (i = 0; i < count; i++) {
        void *p = malloc(bytes);
        int was = -1;
        for (j = 0; j < mark_count; j++)
            if (p == mark[j]) was = j;
        held[i] = p;
        if (was >= 0)
            printf("    request %2d -> %p, which was crate %d\n", i, p, was);
        else
            printf("    request %2d -> %p, which is new ground\n", i, p);
    }
    held_count = count;
}

static void order(int count, size_t bytes)
{
    int i, j;

    if (count > RACK) count = RACK;
    fill(count, bytes);
    empty();
    printf("  reuse order: ");
    for (i = 0; i < count; i++) {
        void *p = malloc(bytes);
        int was = -1;
        for (j = 0; j < mark_count; j++)
            if (p == mark[j]) was = j;
        held[i] = p;
        printf("%d ", was);
    }
    held_count = count;
    printf("\n");
}

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

    setvbuf(stdout, NULL, _IONBF, 0);
    puts("Returns desk.");
    puts("Commands: fill <count> <bytes>, empty, refill <count> <bytes>,");
    puts("          order <count> <bytes>, quit");

    memset(line, 0, sizeof line);
    while (fgets(line, sizeof line, stdin)) {
        line[strcspn(line, "\n")] = '\0';
        if (strncmp(line, "fill ", 5) == 0) {
            int n = atoi(line + 5);
            const char *sp = strchr(line + 5, ' ');
            fill(n, sp ? (size_t)atol(sp + 1) : 24);
        } else if (strncmp(line, "refill ", 7) == 0) {
            int n = atoi(line + 7);
            const char *sp = strchr(line + 7, ' ');
            refill(n, sp ? (size_t)atol(sp + 1) : 24);
        } else if (strncmp(line, "order ", 6) == 0) {
            int n = atoi(line + 6);
            const char *sp = strchr(line + 6, ' ');
            order(n, sp ? (size_t)atol(sp + 1) : 24);
        } else if (strcmp(line, "empty") == 0) {
            empty();
        } else if (strcmp(line, "quit") == 0) {
            break;
        } else if (line[0] != '\0') {
            puts("  unknown command");
        }
        memset(line, 0, sizeof line);
    }
    return 0;
}

Two commands let us compare old and new allocations:

• refill reports which of the remembered addresses each new allocation matches.
• order runs a fill, an empty and a refill in one go. It prints only the mapping, for when you want the order rather than the addresses.

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

No warnings.

Out and back

Three crates, returned lowest index first, then asked for again. Work out which address you expect the first new request to return.

Run ./returns and enter:

fill 3 48
empty
refill 3 48
quit

  filled 3 crates of 48 (chunk 0x40)
    crate  0 at 0x62febe0072b0
    crate  1 at 0x62febe0072f0
    crate  2 at 0x62febe007330
  returned 3 crates, lowest index first
  asking for 3 crates of 48 again
    request  0 -> 0x62febe007330, which was crate 2
    request  1 -> 0x62febe0072f0, which was crate 1
    request  2 -> 0x62febe0072b0, which was crate 0

The address matches are our evidence of reuse. The same three addresses came back, but in reverse order: last in, first out.

Here, the allocator took the most recently returned chunk first. If a program retains a pointer to crate 2, that pointer now reaches the storage used by request 0. We didn’t have to guess an address or turn off randomization: the allocation sequence brought the address back to us.

The eighth crate

Try twelve this time. If the same rule held for every returned chunk, which index would appear first? Compare that prediction with the output and find where the simple reverse-order model fails.

Run ./returns and enter:

order 12 48
quit

  reuse order: 6 5 4 3 2 1 0 11 7 8 9 10

The first seven are clean: crates 6 down to 0, exactly the last-in-first-out behaviour from the three-crate run. Then it stops. Crate 11 arrives out of turn, and 7 through 10 follow in the order they were freed rather than the reverse.

Every original address still came back in this run, but one reverse-order list cannot explain the sequence. The allocator has more than one place to put a returned chunk, and the first one filled up before all twelve were freed.

Turning off the tcache

The tcache is a small per-thread cache with a separate list, or bin, for each eligible chunk size. A free pushes a chunk onto the front of its list, and a matching allocation takes the front one off.

With an initially empty bin and the default capacity of seven, freeing crates 0 through 6 therefore leaves crate 6 at the front. Crates 7 through 11 don’t fit and take another route.

We can check the cache’s role by turning it off for one process:

GLIBC_TUNABLES=glibc.malloc.tcache_count=0 ./returns

GLIBC_TUNABLES is an environment variable glibc reads for per-process configuration. Here it sets the tcache entry limit to zero before returns starts, disabling that cache for this experiment.

Give it the same order 12 48:

  reuse order: 11 10 9 8 7 6 5 4 3 2 1 0

Now all twelve come back in last-in-first-out order, with no hiccup after the seventh. Turning off the cache removed the split in the sequence. These chunks went to the older structure underneath it, which returned them in a simple stack order.

Exit that process before continuing. Because the variable appears directly before the command, the GLIBC_TUNABLES setting applies only to that run, so starting ./returns normally restores the default cache for the next comparison.

Bigger chunks take a different route

The 48 in those commands isn’t incidental. Let’s change the request size and see whether the chunks outside the cache still follow the same route.

Run ./returns and enter:

order 12 200
quit

  filled 12 crates of 200 (chunk 0xd0)
  reuse order: 6 5 4 3 2 1 0 7 8 9 10 11

The first seven are identical because both tested sizes have eligible tcache bins. The remaining five now arrive in the order they were freed, with no crate 11 jumping the queue.

The difference is what happens to the chunks that don’t fit in the cache:

• The 0x40 chunks enter a fastbin, another list for small chunks. On the next allocation after the tcache empties, glibc returns one fastbin chunk and moves others into the cache, accounting for the change in order.
• The 0xd0 chunks are too large for that route and can instead be merged with adjacent free space.

Seven is the default bin capacity, but that doesn’t mean any seven frees will follow this pattern:

• A bin that already contains chunks has fewer spaces left.
• A different thread has a different cache.
• Requests beyond the cache’s supported sizes don’t use it.

The glibc implementation checks those conditions before tcache_put adds an entry. That’s why these comparisons start in a fresh process with an initially empty bin.

Asking for something else

Everything so far repeated the original request size. What matters to the cache, though, is the rounded chunk size from the previous lesson. Requests of 25 and 40 bytes share a size class, but 200 and 100 do not.

Start with that larger change. Run ./returns and enter:

fill 12 200
empty
refill 12 100
quit

    request  0 -> 0x645fe2a05860, which was crate 7
    request  1 -> 0x645fe2a058d0, which is new ground
    request  2 -> 0x645fe2a05940, which is new ground
    request  3 -> 0x645fe2a059b0, which is new ground

One match, and then nothing. Twelve crates were returned and a differently sized request found almost none of them.

Two separate things are happening:

• Crates 0 to 6 are still in the tcache. They’re parked in the bin for their size, and a request for another size does not look there.
• The remaining chunks were merged into one larger free region. The new smaller requests are being carved off its front. The first landed exactly where crate 7 used to be, while the others landed at offsets that never were a crate boundary.

The smaller case is starker. Run ./returns and enter:

fill 2 200
empty
refill 1 450
quit

    request  0 -> 0x61fd3fd77450, which is new ground

Two crates freed, one bigger crate requested, and none of that memory was used. Both returned chunks are sitting in a tcache bin, held out of circulation for any size but their own, so the allocator went and took fresh ground instead.

Different requests, the same bin

Predict whether a 40-byte request will reuse a freed 25-byte allocation, then test in a fresh process. Run ./returns and enter:

fill 1 25
empty
refill 1 40
quit

Repeat with a refill size of 41. Check the rounded chunk sizes as well as the address matches so you can explain the difference without relying on the original request numbers being equal.

Compare the two requests

Both 25 and 40 need a 0x30 chunk, so the first run returns crate 0 from the same bin. A request of 41 needs a 0x40 chunk and cannot take that entry. If you expected both requests to miss, revisit the rounding calculation: the cache selects by chunk size, not the exact number passed to malloc.

In a real program, that means following the intervening allocations as well as finding the free. A matching request might consume your chunk before the object you wanted is created. A variable-length string might sometimes enter the right size class and sometimes miss it. The allocator’s policy explains the possibilities, but the program’s request sequence determines which one you get.

Knowledge check

Question 1 of 3

In the fresh-process example, one 48-byte record enters the tcache and the same thread immediately requests another. What happens?

The new allocation receives the address of the freed recordThe new record is placed after the old one, since the allocator avoids reusing memory immediatelyThe result is unpredictable, because reuse depends on the order of unrelated allocations

Check answer

When the results don’t match

• If your reuse order differs past the seventh entry, use your observed order and carry on. The first seven are the expected prefix for this fresh-process configuration. If the prefix differs too, check the libc version and printenv GLIBC_TUNABLES, then repeat without a persistent cache override.
• If order 12 48 shows -1 anywhere, something else in the process allocated during the run. Start a fresh process and run the single command rather than adding it to a session you have already used.
• If the tunable appears to do nothing, check you exported it for the right process. Running GLIBC_TUNABLES=... ./returns sets it for that program only, and setting it after the program has started has no effect.
• If every request reports new ground, calculate the chunk size for both fill and refill. Different requested sizes can share a bin, but crossing a size-class boundary prevents this cache match.

To recover a known state, quit and start the program again. The returns desk keeps nothing between runs, and a fresh process is the only reliable way to repeat a measurement here.

Check your understanding

Consider a program that frees a record and keeps the pointer. What would you need to know about the program, rather than about the allocator, before you could say whether that is exploitable?

Compare your reasoning

Follow the allocations between the free and the stale use, including their size classes and thread. If the freed chunk enters the tcache, a matching request in that thread can take it, but an earlier matching request might consume it first. Then ask whether you control any of the replacement’s data and whether the stale pointer is used to read, write, or call something through it.

Here, “timing” means the order of the calls within one thread. We can follow that order through the code instead of treating reuse as a race between threads.

When the old address still works

Reuse can put a new object at an old address. If a program kept a pointer to the previous object, that pointer still leads to the same bytes even though they now belong to something else. Next we’ll keep one of those stale pointers and find out what it can read and change before and after reuse.