Specialized memory allocator

Question

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

1.) Calling mem_free requires an unsigned cast of char * for its input parameter. I would like it to use a pointer of any type. How can I do that?

2.) The memory allocator that I wrote allocates a block of memory in front of the front of the buffer and also writes its size. A free function deletes the last block of allocated memory in the buffer. Thus, the order of malloc / free calls matters or it will not work. How can I remove this restriction?

I want to be able to do this:

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

should do it 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; } } } 

Answer 1

1) Use void * instead. 2) Store the address map in the allocated blocks and a separate map of unallocated blocks. Then you can see which block is freed in the allocated card, delete it, and then add the block to the unallocated card (make sure that it will combine it with any free blocks on each side). Of course, this can and can lead to memory fragmentation, but it is really inevitable.

Answer 2

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

In order for the memory allocator to work with any memory cell, you need to add much more complexity ... I would recommend exploring how memory heaps are managed, and you will find some basic schemes for testing.

Answer 3

You wrote that you are looking for ideas, so I am attaching one of my projects that I did at the university, in which we must implement malloc () and free () ... You can see how I did it, and maybe get inspiration or use it all if you want. He is sure that this is not the fastest implementation, but rather simple and should be error-free; -)

(note if someone from the same course happens to this - pls do not use it and rather make their own - 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 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; } } } 

This was done in order to use as little space as possible for meta-information, so the allocated space is marked with the number in the 1st node of the allocated range, indicating the number of subsequent allocated nodes.

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

And it can be used as follows:

 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 

Answer 4

• You must rewrite all the code. Memory allocators usually use a linked list to store used and unused pieces of memory, you can put this link in the block header to size. I advise you to find some articles on how memory allocators work. Writing a well-functioning memory allocator is a difficult task.