`realloc` size in `BlockHeader` incorrect causing `_find_fit` negative sizes

[EngineersBox]

Hi all,

I'm back again with another allocator bug (I think 🤣).

Background

With calls to _find_fit(BlockHeader* head, size_t size), blocks are traversed to check free space between each relative to the input parameter size. The nature of the implementation expects that the offset calculated from an allocated block to a candidate free address block is always before/smaller than the base address of the next allocated block.

uintptr_t next_bot = (uintptr_t) prev->next;
next_bot          -= (uintptr_t) prev->ptr + prev->size;
//                   |_________________________________|
//                       This should be <= prev->next

So, we should expect that (prev->ptr + prev->size) <= prev->next, however this is ONLY the case when two conditions are met universally within the allocator:

1. The BlockHeader.size parameter represents the 8-byte aligned requested size (not including sizeof(BlockHeader)).
2. The size parameter given to _find_fit(...) is the requested size + sizeof(BlockHeader) aligned to 8 bytes.

Implementation Issue

Within the malloc(size_t size) implementation, we can see that the second condition is correctly met:

// ... snip from alloc ...
size_t _size = _align(size + sizeof(BlockHeader), 8);
// ... snip ...
BlockHeader *prev = _find_fit(_alloc_head, _size);
// ... snip ...

In the implementation of realloc(...) however, the first condition is not met. All of the instances where the BlockHeader.size field is set, the value is the 8-byte aligned value of size + sizeof(BlockHeader). This is also present in the free(...) implementation (not shown here, see the PR linked at the bottom of this issue description).

// malloc.c
// ... snip from realloc ...
// New memory block shorter?
if (prev->size >= _size) {
    TrackHeapUsage(size - prev->size);
    prev->size = _size; // <-- HERE

    if (!prev->next)
        sbrk((ptr - sbrk(0)) + _size);

    return ptr;
}

// New memory block larger; is it the last one?
if (!prev->next) {
    void *new = sbrk(_size - prev->size);
    if (!new)
        return 0;

    TrackHeapUsage(size - prev->size);
    prev->size = _size; // <-- HERE
    return ptr;
}

// Do we have free memory after it?
if (((prev->next)->ptr - ptr) > _size) {
    TrackHeapUsage(size - prev->size);
    prev->size = _size; // <-- HERE
    return ptr;
}
// ... snip ...

The result of this, we can get integer underflow occurring with the offset to the free block in _find_fit(...) when two blocks of memory are sequentially allocated and reallocated several times.

Specifically, rev->ptr + prev->size exceeds the actual free space, since size should represent free space, but can have up to an additional sizeof(BlockHeader) (aligned) space which causes next_bot to underflow on the subtraction and then exceed prev->next, thus the following check (next in the _find_fit implementation) will be true:

if (next-bot >= size) {
    return prev;
}

As a result, with sequentially allocated and re-sized blocks this can cause the header of the reallocated error to be placed within the header or allocated space of the next block. This thus causes invalid read/write to addresses that are invalid or potentially non-existent (from userspace) depending on where exactly the reallocated header is placed within the next block and what the existing data in that block was.

Example and Memory Layout

Using a minimal example (with the help of a library cvector) and adding some logs to both the malloc.c implementation in PSn00bSDK and the cvector library, we can see the issue itself. A buildable/complete example can be found in my current project https://github.com/EngineersBox/PSX-Minecraft/tree/ab1052d1f9a062b33040847bf7adb13d53d61691 at commit ab1052d1f9a062b33040847bf7adb13d53d61691 (That link goes directly to the repo at that commit).

The code is as follows:

#include <stdint.h>
#include <stdio.h>
#include <psxgte.h>
#include <cvector.h>

#include "core/display.h"

typedef struct {
    SMD smd;
    cvector(SVECTOR) vec1;
    cvector(SVECTOR) vec2;
} TestMinRep;

void __destruct(void *elem) {
}

void initRep(TestMinRep *rep) {
    rep->vec1 = NULL;
    rep->vec2 = NULL;
    cvector_init(rep->vec1, 1, __destruct);
    cvector_init(rep->vec2, 1, __destruct);
}

int main() {
    init(); // Some basic init stuff
    TestMinRep obj;
    initRep(&obj);
    uint32_t i1 = 0;
    uint32_t i2 = 0;
    int should_break = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            printf("VERTEX %d: %p\n", j, obj.vec1);
            cvector_metadata_t *meta = cvector_vec_to_base(obj.vec1);
            printf("  [BEFORE] Size: %d, Cap: %d, Dest: %p\n", meta->size, meta->capacity, meta->elem_destructor);
            cvector_metadata_t *meta2 = cvector_vec_to_base(obj.vec2);
            printf("  [Normal: %p] [BEFORE] Size: %d, Cap: %d, Dest: %p\n", obj.vec2, meta2->size, meta2->capacity,
                   meta2->elem_destructor);
            cvector_push_back(obj.vec1, (SVECTOR){});
            meta = cvector_vec_to_base(obj.vec1);
            printf("  [AFTER] Size: %d, Cap: %d, Dest: %p\n", meta->size, meta->capacity, meta->elem_destructor);
            meta2 = cvector_vec_to_base(obj.vec2);
            printf("  [Normal: %p] [AFTER] Size: %d, Cap: %d, Dest: %p\n", obj.vec2, meta2->size, meta2->capacity,
                   meta2->elem_destructor);
            SVECTOR *curr = &obj.vec1[i1];
            curr->vx = i;
            curr->vy = j;
            curr->vz = i1;
            i1++;
            // This stops the loop at exactly the right spot
            // comment this out to let it run in full (lots of corruption)
            if (i == 2 && j == 1) {
                should_break = 1;
                break;
            }
        }
        // This stops the loop at exactly the right spot
        // comment this out to let it run in full (lots of corruption)
        if (should_break) {
            break;
        }
        printf("NORMAL: %p\n", obj.vec2);
        cvector_metadata_t *meta2 = cvector_vec_to_base(obj.vec2);
        printf("  [BEFORE] Size: %d, Cap: %d, Dest: %p\n", meta2->size, meta2->capacity, meta2->elem_destructor);
        cvector_push_back(obj.vec2, (SVECTOR){});
        meta2 = cvector_vec_to_base(obj.vec2);
        printf("  [AFTER] Size: %d, Cap: %d, Dest: %p\n", meta2->size, meta2->capacity, meta2->elem_destructor);
        SVECTOR *curr1 = &obj.vec2[i2];
        curr1->vx = i;
        curr1->vx = i2;
        curr1->vz = rand();
        i2++;
    }
    while (1) {
        display(&dctx); // Swap buffers, etc
    }
    return 0;
}

Running this example, opening logs and dumping the memory layout we can see the following.

The left side memory editor (Memory Editor #1) shows the spot where the size of the normals cvector instance was held previously (just ahead of the BlockHeader), the top-right memory editor showcases the previous location of vertices cvector instance, the bottom left has the new location of the vertices cvector instance.

In the logs on the right side, we can see the integer underflow occur on the third iteration within the _find_fit(...) call when resizing the vertices cvector memory. Here lies the issue, since the if statement is true with the effectively negative (converted to uintptr_t) size becoming very large, thus matching the condition for next_bot >= size is met. The address that is returned here is partially within the BlockHeader of the next memory block, which is sequentially allocated in a struct and thus corresponds to the normals cvector instance.

Applying the fix to the realloc(BlockHeader* head, size_t size) implementation, we can see that these issues are now resolved.

Changes

I've submitted a pull request to fix these issues, and as per the last issue I raised, it's probably a good idea to forward these fixes onto the original implementation used in the PCSX-Redux emulator (I think that's what it was).

PR link is here: https://github.com/Lameguy64/PSn00bSDK/pull/81