Custom memory caching allocator in C

Over the weekend I built a fairly simple allocator:

```
struct FreeOnes { //data structure holding the pointers to free blocks
int len;
void** array;
int capacity;
};

void append(struct FreeOnes f, void what){ //add a free block to FreeOnes
if (f->len capacity){
f->array[f->len++] = what;
} else {
f->capacity *= 2;
f->array = realloc(f->array, sizeof(void) f->capacity);
f->array[f->len++] = what;
}
}

void pop(struct FreeOnes f){
return f->array[--f->len];
}

struct FreeOnes* newFreeOnes(int capacity){ //create a new FreeOnes datastructure
struct FreeOnes* f = malloc(sizeof(struct FreeOnes));

f->len = 0;
f->capacity = capacity;
f->array = malloc(sizeof(void) capacity);

return f;
}

struct Size { //the information neccessary to allocate a block
int size; //the byte size
int alignment; //the alignment to the memory-array
};

struct Size find(int size){ //find at wich alignment the size fits inside
int i = 2;
int iter = 0;
while (i len > 0){ //if already allocated memory, just this instead
void* pointer = pop(sizes[s.alignment]);
return pointer;
} else if (s.alignment < 6){ //allocate chunk and use the first element
return allocChunk(sizes[s.alignment], s.size, s.alignment, 100);
} else if (s.alignment < 12){ //allocate chunk and use the first element
return allocChunk(sizes[s.alignment], s.size, s.alignment, 20);
} else if (s.alignment < 24){ //allocate chunk and use the first element
return allocChunk(sizes[s.alignment], s.size, s.alignment, 5);
} else { //so big not worth allocating chunk for, simply return pointer to malloc initialized memory
void* pointer = malloc(s.size);
int p = (int) pointer;
*p = s.alignment; //store the alignment meta-date
return pointer+ sizeof(int);
}
}

void dealloc(void* pointer){ //free the pointer, and return it to the freeOnes vect

Bug 1

Here is a program that crashes when using your allocator:

int main(void)
{
    init();

    struct Size s = find(sizeof(short));

    short *pShort1 = alloc(s);
    short *pShort2 = alloc(s);
    *pShort2 = 0xffff;
    dealloc(pShort1);

    return 0;
}

The reason for the crash is that the allocator rounds up each size requested to the next power of 2, but then it steals 4 bytes to store some metadata. When the size requested is 2 bytes, as in the example above, the allocator rounds up the size to 4, and then steals all 4 bytes to store the metadata, leaving no memory for the actual allocation. What ends up happening is that the pointer returned is pointing at the metadata for another allocation. Writing 0xffff to that pointer clobbers the metadata for the other allocation and results in a crash when that allocation is deallocated.

This bug can happen whenever the size requested is 1 to sizeof(int)-1 bytes less than a power of 2. So for example, if an int is 4 bytes, then using sizes 1, 2, 3, 5, 6, 7, 13, 14, 15, etc. are all unsafe.

Bug 2

If you allocate something bigger than \$2^{24}\$ bytes, you will get a pointer back that is 4 bytes smaller than what you requested. The problem is with this code:

} else { //so big not worth allocating chunk for, simply return pointer to malloc initialized memory
    void* pointer = malloc(s.size);
    int* p = (int*) pointer;
    *p = s.alignment; //store the alignment meta-date
    return pointer+ sizeof(int);
}

As you can see, you call malloc(s.size), but then steal one int from the front. You then return a pointer to something which has only s.size - sizeof(int) bytes allocated.

Bug 3

The regular malloc() always returns a pointer aligned to the maximum required alignment for the system. So for example, on some system let's suppose it always returns an 8-byte aligned pointer because a double on that system must be 8-byte aligned.

With your allocator, you always return something that is off alignment by sizeof(int) bytes because you put the int sized metadata right before the actual pointer returned. So if someone tried to use your allocator to allocate space for a double, and sizeof(int) is 4, then the pointer returned would be misaligned by 4 bytes and not be suitable for use as a double pointer.

StackExchange Code Review Q#120612, answer score: 7