Custom memory caching allocator in C

Question

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 < f->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 <= size) {
 i *= 2;
 iter ++;
 }
 struct Size s;
 s.size = i;
 s.alignment = iter - 1;
 return s;
}
struct FreeOnes** sizes; //holds a free ones data structure for all power of 2 sizes until 2^32
void* allocChunk(struct FreeOnes * f, size_t size, int alignment, int howMuch){ //chunk allocate memory,
//used by alloc and returns a pointer to the first element in the chunk
 void* pool = malloc(size * howMuch);
 void* at = pool;
 for (int i = 0; i < howMuch; i++){
 void* pointer = at;
 at += size;
 int* p = (int*) pointer;
 *p = alignment; //store the alignment meta-date
 append(f, pointer+ sizeof(int));
 }
 return pop(f);
}
void* alloc(struct Size s){ //allocate, memory for a size
 if (sizes[s.alignment]->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 vector
 int s = *((int*) (pointer - sizeof(int)));
 append(sizes[s], pointer);
}
void init(){ //initialize the program memory needed for alloc and dealloc
 sizes = (struct FreeOnes**) malloc(sizeof(struct FreeOnes*) * 32);
 for (int i = 0; i < 32; i++){
 sizes[i] = newFreeOnes(100);
 }
}

The allocator performs very well on this slightly biased benchmark:

struct LinkedListAlloc { //small linked list benchmark
 int x;
 struct LinkedListAlloc * next;
};
long benchmark1(){ //benchmark using alloc
 clock_t time1 = clock();
 struct Size size = find(sizeof(struct LinkedListAlloc)); //the size for the linked list, in the format for alloc
 for (int iter = 0; iter < 1000; iter++){
 //create the linked list
 struct LinkedListAlloc* root = alloc(size);
 root->x = 0;
 struct LinkedListAlloc* last = root;
 for (int i = 1; i < 1000; i++){
 struct LinkedListAlloc* tmp = alloc(size);
 tmp->x = i;
 last->next = tmp;
 last = tmp;
 }
 struct LinkedListAlloc* current = root;
 while (1) {
 if (current->x == 999){ dealloc(current); break; }
 struct LinkedListAlloc* tmp = current;
 current = current->next;
 dealloc(tmp);
 }
 }
 clock_t time2 = clock();
 return time2 - time1;
}
long benchmark2(){ //benchmark using malloc
 clock_t time1 = clock();
 size_t size = sizeof(struct LinkedListAlloc); //the size for the linked list
 for (int iter = 0; iter < 1000; iter++){
 //create the linked list
 struct LinkedListAlloc* root = malloc(size);
 root->x = 0;
 struct LinkedListAlloc* last = root;
 for (int i = 1; i < 1000; i++){
 struct LinkedListAlloc* tmp = malloc(size);
 tmp->x = i;
 last->next = tmp;
 last = tmp;
 }
 struct LinkedListAlloc* current = root;
 while (1) {
 if (current->x == 999){ free(current); break; }
 struct LinkedListAlloc* tmp = current;
 current = current->next;
 free(tmp);
 }
 }
 clock_t time2 = clock();
 return time2 - time1;
}
int main(){
 init();
 long took1 = benchmark1();
 long took2 = benchmark2();
 printf("alloc: %ld\n", took1);
 printf("malloc: %ld\n", took2);
 return 0;
}

The test using alloc and dealloc is ten times faster than the test using malloc and free.

What could I improve on for this allocator, eg. how to make it thread-safe?

Answer 1

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.

• Coder3000: how would it be possible to fix, the third bug.
• Coder3000: fixed all bugs!
• JS1: @Coder3000 You've already fixed the bugs, but in response to your question, you should probably steal a "maximum alignment" sized chunk off the front instead of an int. According to the GNU C library documentation, their malloc always aligns to a maximum of 8 on 32-bit systems and 16 on 64-bit systems. So if you steal 16 bytes off the front, you should be able to maintain alignment.