What's the purpose of a footer on each block when implementing malloc() in C?

user_1020173 0
Viewed 498

I can kind of understand the purpose of having just a header on each block but I can't understand the purpose of having both a header and a footer. According to http://www.cs.cornell.edu/courses/cs3410/2016fa/slides/15-allocation.pdf, slide 25, the footer enables traversing the list, also, backwards. What's the purpose of traversing the list both forward and backward?

c
1 Answers

I have implemented quite a few implementations of malloc(). The reason you want to traverse backwards is to attach the block onto the previous block on free(). But I can't imagine using a footer. I just use a header that looks like this.

struct block {
    struct block *next;
    struct block *prev;
    uintptr_t size;
    uintptr_t blocksize;
};

I could use size_t for size but on platforms where they differ, uintptr_t is more likely to work correctly, so I'm less apt to have to fix something. I keep track of the size that was allocated as well as the size of the block to speed up realloc().

If we mutated away the need to traverse backwards on free() somehow, we could reduce the header to two elements.

struct block {
    struct block *next;
    uintptr_t size;
};

The low bit of size is free on any reasonable platform, so you can stick an is_allocated flag there.

user_147680
Related