Section 2: Internal metadata

Every allocator must keep metadata: information about the size of every allocation and the location and size of remaining free space. An allocator using internal metadata stores allocation metadata inside the allocation buffer itself, rather than in separate data structures like maps.

Question for the section: What are some advantages and disadvantages of internal metadata?

  • (+) Internal metadata likely has benefits in terms of memory cache performance. Applications usually free data recently after using it, so when metadata is kept in memory close to the allocated data, the metadata will already be in the cache at free time.

  • (+) An allocator that detects wild writes on free must allocate some extra space devoted to that purpose, so that space might as well be used for metadata storage too.

  • (-) Internal metadata is slightly more difficult to program.

  • (-) Internal metadata is more vulnerable to accidental corruption from wild writes.

  • (invalid -) Internal metadata takes up space that would otherwise be devoted to application data. (Metadata always takes up space, whether or not it’s internal!)

Group work (5m)

Design an internal metadata layout that supports wild write detection and allocation size tracking. Write this metadata layout as one or more structure definitions, and say how the structures are placed relative to user allocations.

Discussion

Solicit designs from the students.

Some points to highlight:

  1. The metadata containing the size of an allocation must be located in the buffer immediately before the allocation, at a known offset. This is because if it weren’t, you would need to know the size to find the size.

  2. The metadata that detects wild writes after an allocation should likely have 1-byte alignment, because allocations can have any size.

  3. It’s useful to have a magic number to detect invalid frees.

Group work (5m)

Assuming that header metadata (that is, the metadata stored in the buffer immediately before the allocation) is stored in a structure called m61_header, write code for the following functions:

void* m61_h2u(m61_header* hdr) {
    // Given a pointer to header metadata for an allocation, return
    // the address of the **user** allocation.
}

m61_header* m61_u2h(void* ptr) {
    // Given the address of a user allocation, return the address of the
    // corresponding header metadata.
}

// (optional)
m61_trailer* m61_h2t(m61_header* hdr) {
    // Given a pointer to header metadata, return a pointer to the
    // corresponding trailer metadata.
}

There are many valid ways to write these functions. Here are a few:

void* m61_h2u(m61_header* hdr) {
    return hdr + 1;
    return reinterpret_cast<char*>(hdr) + sizeof(*hdr);
    return (void*) ((uintptr_t) hdr + sizeof(m61_header));
}

m61_header* m61_u2h(void* ptr) {
    return reinterpret_cast<m61_header*>(ptr) - 1;
    return (m61_header*) ((uintptr_t) ptr - sizeof(m61_header));
}

m61_trailer* m61_h2t(m61_header* hdr) {
    return reinterpret_cast<m61_trailer*>(
        reinterpret_cast<char*>(hdr + 1) + hdr->size /* where `size` is the user’s size
    );

    uintptr_t user_addr = (uintptr_t) (hdr + 1);
    uintptr_t end_allocation = user_addr + hdr->size;
    return reinterpret_cast<m61_trailer*>(end_allocation);
}

Discussion

Make sure that the students understand why the + 1/- 1 variants work, and where the casts need to be.

Group work (5m)

Users can provide bad pointers to m61_free, and ideally m61_free will detect problems with those pointers before causing undefined behavior itself. A robust m61_u2h would detect bad pointers and return nullptr, rather than a pointer to random garbage, if ptr was an invalid free. Describe ways to make m61_u2h as robust as possible.

  1. Check the alignment of ptr.
  2. Check that ptr is within the allocation buffer: (char*) ptr >= buffer + sizeof(m61_header) && (char*) ptr < end_buffer.
  3. After those two checks, check that the purported hdr pointer has the right magic number.
  4. Check that the purported size in m61_u2h doesn’t go beyond the buffer. (This requires overflow reasoning!)

Many other checks are possible, though the first 3 are the most important. Discuss what the class comes up with. Make sure they understand why 1 and 2 must come first—why checking the magic number before checking alignment might cause undefined behavior in the allocator.

A challenging attack

This test program performs an invalid free that’s challenging for internal metadata allocators to detect. How does the attack work?

int main() {
    char* stash = m61_malloc(1000);
    char* victim = m61_malloc(10);
    char* post_stash = m61_malloc(1000);
    memcpy(stash, victim - 100, 300);
    m61_free(victim);
    memcpy(victim - 100, stash, 300);
    m61_free(victim); // should be detected as a double free!
}

The user is copying a region around the victim allocation, likely including its internal metadata, into a separate area, then copies that area back after freeing the victim. That means the data around victim looks exactly like it did before the free!

Group work (10m)

Can you design an internal metadata format that can detect this kind of attack? Ideally your format will take $$O(1)$$ work per free.

One $$O(N)$$ solution would be to recompute the active_bytes on every m61_free by walking over every allocation in the buffer, and compare that number with the cached active_bytes. Similarly, you could walk over the allocations and see whether the freed pointer occurs in the list. An $$O(1)$$ solution, though, is to store information in neighboring allocations. For instance, it would be enough to store in each m61_header whether the next block is allocated or free. The initial m61_free on line 6 will set stash’s header to “next block free”, which can be detected as a contradiction when the double free is attempted on line 8.