custom memory allocator

I wrote a custom memory allocator. It has 2 restrictions that I want to remove so it works like malloc/free.

1.) The mem_free call requires a cast to an unsigned char * for its input parameter. I would like it to take a pointer of any type. How can this be done?

2.) The memory allocator I wrote allocates a block of memory to the front of the buffer and it also writes its size. The free function removes the last block of allocated memory in the buffer. So the order of the malloc/free calls matter or it will not work. How can I remove t开发者_高级运维his restriction?

want to be able to do this:

char* ptr1 = mem_alloc(10);
char* ptr2 = mem_alloc(4);

mem_free(ptr1);
mem_free(ptr2);

have to do this now:

char* ptr1 = mem_alloc(10);
char* ptr2 = mem_alloc(4);

mem_free(ptr2);
mem_free(ptr1);

code:

unsigned char* mem_alloc(unsigned int size) {
    unsigned int s;
    if( (size + MEM_HEADER_SIZE)  > (MEM_MAX_SIZE - mem_current_size_bytes) ) {
        return NULL;
    }
    if(is_big_endian() == 0) {
        s = (mem_buff[3] << 24) + (mem_buff[2] << 16) + (mem_buff[1] << 8) + mem_buff[0];
    } else {
        s = (mem_buff[0] << 24) + (mem_buff[1] << 16) + (mem_buff[2] << 8) + mem_buff[3];
    }
    memcpy(mem_buff + mem_current_size_bytes, &size, sizeof(unsigned int));
    unsigned char* result = mem_buff + (mem_current_size_bytes + MEM_HEADER_SIZE);
    mem_current_size_bytes += MEM_HEADER_SIZE + size;
    return result;
}

void mem_free(unsigned char* ptr) {
    unsigned int i,s;
    for(i=0; i<mem_current_size_bytes; i++) {
        if( (char*)ptr == (char*)(mem_buff + i) ) {
            if(is_big_endian() == 0) {
                s = (*(ptr - 1) << 24) + (*(ptr - 2) << 16) + (*(ptr - 3) << 8) + *(ptr - 4);
            } else {
                s = (*(ptr - 4) << 24) + (*(ptr - 3) << 16) + (*(ptr - 2) << 8) + *(ptr - 1);
            }
            mem_current_size_bytes-=s;
            mem_current_size_bytes-=MEM_HEADER_SIZE;
            break;
        }
    }
}

1) Use a void* instead.
2) Store a map of addresses to allocated blocks and a seperate map of unallocated blocks. You can then look up which block is being freed in the allocated map, remove it and then add the block to the unallocated map (making sure to merge it with any free blocks either side of it). Of course, this can and does lead to memory fragmentation but that is rather unavoidable really.

You wrote you are looking for ideas, so I am attaching one of my projects I've done at university, in which we should implement malloc() and free()... You can see how I've done this and perhaps get an inspiration or use it all if you want. It sure isn't the fastest implementation possible, but is rather easy and should be bug free ;-)

(note if someone from the same course happen to came across this - pls don't use this and rather make your own one - hence the license ;-)

/*
 * The 1st project for Data Structures and Algorithms course of 2010
 *
 * The Faculty of Informatics and Information Technologies at
 * The Slovak University of Technology, Bratislava, Slovakia
 *
 *
 * Own implementation of stdlib's malloc() and free() functions
 *
 * Author: mnicky
 *
 *
 * License: modified MIT License - see the section b) below
 *
 * Copyright (C) 2010 by mnicky
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * a) The above copyright notice and this permission notice - including the
 *    section b) - shall be included in all copies or substantial portions
 *    of the Software.
 *
 * b) the Software WILL NOT BE USED IN ANY WORK DIRECTLY OR INDIRECTLY
 *    CONNECTED WITH The Faculty of Informatics and Information Technologies at
 *    The Slovak University of Technology, Bratislava, Slovakia
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 *
 */

#include <stdio.h>

typedef unsigned int MEMTYPE;

MEMTYPE *mem;
MEMTYPE memSize;
MEMTYPE avail;  //1st index of the 1st free range

//return size of block
MEMTYPE blockSize(MEMTYPE x) {
  return mem[x];
}

//return next free block
MEMTYPE next(MEMTYPE x) {
  return mem[x + mem[x]];
}

//return index of pointer to next free block
MEMTYPE linkToNext(MEMTYPE x) {
  return x + mem[x];
}

//initialize memory
void my_init(void *ptr, unsigned size) {

  mem = (MEMTYPE *) ptr;
  memSize = size / sizeof(MEMTYPE);
  mem[0] = memSize - 1;
  mem[memSize - 1] = memSize;
  avail = 0;
}

//allocate memory
void *my_alloc(unsigned size) {

  if (size == 0) {  //return NULL pointer after attempt to allocate 0-length memory
    return NULL;
  }

  MEMTYPE num = size / sizeof(MEMTYPE);
  if (size % sizeof(MEMTYPE) > 0) num++;
  MEMTYPE cur, prev;  //pointer to (actually index of) current block, previous block
  MEMTYPE isFirstFreeBeingAllocated = 1;  //whether the first free block is being allocated

  prev = cur = avail;

  //testing, whether we have enough free space for allocation
  test:

  if (avail == memSize) {  //if we are on the end of the memory
    return NULL;
  }

  if (blockSize(cur) < num) {  //if the size of free block is lower than requested
    isFirstFreeBeingAllocated = 0;
    prev = cur;

    if (next(cur) == memSize) {  //if not enough memory
      return NULL;
    }
    else
      cur = next(cur);
    goto test;
  }

  if (blockSize(cur) == num) {  //if the size of free block is equal to requested

    if (isFirstFreeBeingAllocated)
      avail = next(cur);
    else
      mem[linkToNext(prev)] = next(cur);
  }

  else {  //if the size of free block is greater than requested

    if (isFirstFreeBeingAllocated) {
      if ((blockSize(cur) - num) == 1)  //if there is only 1 free item left from this (previously) free block
        avail = next(cur);
      else
        avail = cur + num + 1;
    }
    else {
      if ((blockSize(cur) - num) == 1)  //if there is only 1 free item left from this (previously) free block
        mem[linkToNext(prev)] = next(cur);
      else
        mem[linkToNext(prev)] = cur + num + 1;
    }

    if ((blockSize(cur) - num) == 1)  //if there is only 1 free item left from this (previously) free block
      mem[cur] = num + 1;
    else {
      mem[cur + num + 1] = blockSize(cur) - num - 1;
      mem[cur] = num;
    }
  }

  return (void *) &(mem[cur+1]);
}

//free memory
void my_free(void *ptr) {

  MEMTYPE toFree;  //pointer to block (to free)
  MEMTYPE cur, prev;

  toFree = ((MEMTYPE *)ptr - (mem + 1));


  if (toFree < avail) {  //if block, that is being freed is before the first free block

    if (((linkToNext(toFree) + 1) == avail) && avail < memSize)  //if next free block is immediately after block that is being freed
      mem[toFree] += (mem[avail] + 1);  //defragmentation of free space
    else
      mem[linkToNext(toFree)] = avail;

    avail = toFree;
  }

  else {  //if block, that is being freed isn't before the first free block

    prev = cur = avail;

    while (cur < toFree) {
      prev = cur;
      cur = next(cur);
    }

    if ((linkToNext(prev) + 1) == toFree) { //if previous free block is immediately before block that is being freed

      mem[prev] += (mem[toFree] + 1);  //defragmentation of free space

      if (((linkToNext(toFree) + 1) == cur) && cur < memSize)  //if next free block is immediately after block that is being freed
        mem[prev] += (mem[cur] + 1);  //defragmentation of free space
      else
        mem[linkToNext(toFree)] = cur;
    }
    else {
      mem[linkToNext(prev)] = toFree;
      mem[linkToNext(toFree)] = cur;
    }

  }
}

It was done to use as small amount of space for metainformation as possible, so the allocated space is marked by the number in 1st node of allocated range, indicating the number of allocated nodes following.

Amount of free space in the free range is marked by a number indicating the number of free nodes following (including that node) and last node of the free range contains number of 1st index of the next following free range - sth like this (the red space is allocated, the white is free):

And it can be used like this:

char region[30000000];  //space for memory allocation
my_init(region, 30000000);  //memory initialization

var = (TYPE *) my_alloc(sizeof(TYPE));  //memory allocation
my_free((void *) var);  //freeing the memory

Just use a void* pointer instead of char* in the argument of mem_free.

For making the memory allocator work with any memory location, you need to add much more complexity...i'd recommend researching how memory heaps are managed and you will find some basic schemes to try out.

1. You have to rewrite the whole code. Memory allocators usually use a linked list for storing used and unused chunks of memory, you can put the this link in the header of the chunk before size. I advise you to search for some articles about how memory allocators work. Writing a well performing memory allocator is a hard task.