Writing a simulation of malloc [closed]

You are going to need to keep two lists, one for the free memory, one for the memory in use. You will initialize the free list so it initially contains all the memory in the array, and the in-use list so that it is empty.

When a block of memory is allocated, you'll need to search the free list to find a suitable chunk that is at least as big as the one requested. If there's no such chunk, you'll return an error. Assuming there is a chunk, then you'll record the chunk as allocated by modifying the free list to indicate that the space just allocated is no longer available and by adding the appropriate information to the in use list. Note that in a more general system, when there isn't any suitable space in the free list, the code will try to obtain more memory from the O/S, only failing if the O/S refuses to help. When you have a fixed size array supplying the memory, this is not an option, of course.

When a block of memory is freed, you'll be able to determine whether it is valid from the in-use list. If it is valid, you will remove the memory from the in-use list and move it into the free list, taking care to ensure that if it is contiguous with other blocks of memory in the list, then it is merged with the other blocks to make a larger block (there might be one or two adjacent blocks, and after the free, there could be one more block on the list, or the same number of blocks, or one less block on the list.

For a realloc, you need to look to see whether the request is for more or less memory. If less, then you can release the memory that's no longer required to the free list. If more, you need to see whether there is enough space after the current block. If so, you can extend the current allocation. If not, then you need to allocate the new larger block (failing if there isn't enough memory available), then copy the old block over the new, and finally release the old block.

You may well decide not to allocate fewer than, say, 8 bytes to any request, and to always allocate a multiple of 8 bytes. The use of an array as the source of space simplifies this allocator compared with one that must get memory from the operating system.

Production versions of malloc() often do not separate the control information as described here. There isn't always an explicit in-use list, but the memory pointer returned is typically a few bytes after some control information (which contains at least the size of the block of memory). The free list is often held in a linked list using the previously allocated space to hold pointers to the next and previous blocks in the free list. The advantage of the separate controls is that you can formally validate that the memory returned with free() is memory that was allocated. Without the separation, things go haywire if the control information for the memory returned was trampled by a bug in the program or if the pointer returned was not a pointer allocated, so there isn't any control information (but the memory manager assumes there is and gets misled). Of course, even with separation of control and data information, things can go haywire if the program is buggy; it is just less probable that a small defect (manipulating data just outside the range of allocated memory) will crash the memory management system. With a debugging memory allocator, you can put sentinel data outside the allocated space (so you over-allocate) and you can then test that the extra space was not modified. Etc.

There are many detailed systems for how to handle memory allocation with names such as 'first fit', 'best fit', 'worst fit', 'buddy allocation' and so on. Knuth's 'The Art of Computer Programming, Volume 1, Fundamental Algorithms' describes memory management algorithms. There are a myriad other sources of information on the web; it is a popular subject for discussion and experimentation.

When you allocate memory from your array, "allocate" the requested size plus the size of the node structure. Then you can use

/* "region_ptr" is the start of the region allocated */
struct node *node_ptr = (struct node *) region_ptr;
void *mem_ptr = ((char *) region_ptr) + sizeof(stuct node);

Now you have two pointers: node_ptr points to a node you can use; And mem_ptr points to the actual memory you return from your allocation routine.

As always @Jonathan Leffler explained it nicely. I sometime back saw an answer which might definitely help you implement this with a macro. I thought this extra information is useful. Please have a look at the solution provided for this question macro usage to detect memory usage