8
\$\begingroup\$

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?

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ how would it be possible to fix, the third bug. \$\endgroup\$ – Coder3000 Feb 21 '16 at 9:27
  • \$\begingroup\$ fixed all bugs! \$\endgroup\$ – Coder3000 Feb 21 '16 at 17:00
  • \$\begingroup\$ @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. \$\endgroup\$ – JS1 Feb 21 '16 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.