Zyphicx Zyphicx - 1 month ago 13
C Question

How does this memory allocator work?

So, I just sat down and decided to write a memory allocator. I was tired, so I just threw something together. What I ended up with was this:

#include <stdio.h>
#include <stdlib.h>

#define BUFSIZE 1024

char buffer[BUFSIZE];
char *next = buffer;

void *alloc(int n){
if(next + n <= buffer + BUFSIZE){
next += n;
return (void *)(next - n);
}else{
return NULL;
}
}

void afree(void *c){
next = (char *)c;
}

int main(){
int *num = alloc(sizeof(int));
*num = 5643;
printf("%d: %d", *num, sizeof(int));
afree(num);
}


For some reason, this works. But I can not explain why it works. It may have to do with the fact that I am tired, but I really can not see why it works. So, this is what it should be doing, logically, and as I understand it:


  1. It creates a char array with a pointer which points to the first element of the array.

  2. When I call alloc with a value of 4 (which is the size of an int, as I have tested down below), it should set next to point to the fourth element of the array. It should then return a char pointer to the first 4 bytes of the array casted to a void pointer.

  3. I then set that value to something greater than the max value of a char. C should realise that that isn't possible and should then truncate it to *num % sizeof(char).



I have one guess as to why this works: When the char pointer is casted to a void pointer and then gets turned into an integer it somehow changes the size of the pointer so that it is able to point to an integer. (I haven't only tried this memory allocator with integers, but with structures as well, and it seems to work with them as well).

Is this guess correct, or am I too tired to think?

EDIT:
This is what it looks like in my mind

EDIT 2: I think I've understood it. I realised that my phrasing from yesterday was quite bad. The thing which threw me off was the fact that the returned pointer actually points to a char, but I am still somehow able to store an integer value.

Answer

The allocator posted implements a mark and release allocation scheme:

  • alloc(size) returns a valid pointer if there is at least size unallocated bytes available in the arena. The available size is reduced accordingly. Note that this pointer can only be used to store bytes, as it is not properly aligned for anything else. Furthermore, from a strict interpretation of the C Standard, even if the pointer is properly aligned, using it as a pointer to any other type would violate the strict aliasing rule.

  • afree(ptr) resets the arena to the state is was before alloc() returned ptr. It would be a useful extension to make afree(NULL) reset the arena to its initial state.

Note that the main() function attempts to use the pointer returned by alloc(sizeof(int)) as a pointer to int. This invokes undefined behavior because there is no guarantee that buffer is properly aligned for this, and because of the violation of the strict aliasing rule.

Note also that the printf format printf("%d: %d", *num, sizeof(int)); is incorrect for the second argument. It should be printf("%d: %zd", *num, sizeof(int)); or printf("%d: %d", *num, (int)sizeof(int)); if the C runtime library is too old to support %zd.