Controlling a continuous chunk of memory without Malloc / New or Free / Delete

Question

How can I create my own memory manager to manage this continuous piece of memory without the help of other memory managers (such as Malloc / New) in C ++?

Here is another context:

MemManager::MemManager(void* memory, unsigned char totalsize) { Memory = memory; MemSize = totalsize; } 

I need to be able to allocate and free blocks of this contiguous memory using MemManager. The constructor gets the total size of the chunk in bytes.

The Allocate function should take the amount of memory needed in bytes and return a pointer to the beginning of this memory block. If there is no memory left, a NULL pointer is returned.

The Deallocate function must take a pointer to a block of memory to be freed and return it to MemManager for future use.

Please note the following restrictions:

- In addition to the memory provided to him, MemManager cannot use ANY dynamic memory

- As originally stated, MemManager CANNOT use other memory managers to perform its functions, including the new / malloc and delete / free

I already got this question at several interviews, but even hours of research on the Internet did not help me, and I failed every time. I found similar implementations, but they all either used malloc / new, or were intended for general purpose and requested memory from the OS, which I am not allowed to do.

Please note that it is convenient for me to use malloc / new and free / delete and work with them with minor problems.

I tried implementations that use node objects in the LinkedList method, which point to a allocated block of memory and determine how many bytes were used. However, with these implementations, I always had to create new nodes on the stack and insert them into the list, but as soon as they went out of scope, the whole program broke down, because addresses and memory sizes were lost.

If anyone has an idea on how to implement something like this, I would really appreciate it. Thanks in advance!

EDIT: I forgot to explicitly indicate this in my original post, but the objects selected by this MemManager can be of different sizes.

EDIT 2: I ended up using homogeneous memory blocks, which was actually very easy to implement thanks to the information provided below. Exact rules regarding the implementation itself were not specified, so I divided each block into 8 bytes. If the user requested more than 8 bytes, I would not be able to provide it, but if the user requested less than 8 bytes (but> 0), I would give additional memory. If the amount of memory transferred inside is not divisible by 8, then in the end memory will be lost, which, I believe, is much better than using more memory than you.

Answer 1

I tried implementations that use node objects in a LinkedList mod that points to a allocated block of memory, and specify how many bytes. However, with these implementations, I was always forced to create new nodes on the stack and insert them into the list, but as soon as they went out of scope, the whole program broke down because the addresses and memory sizes were lost.

You are on the right way. You can insert the LinkedList node into the memory block that you specified with reinterpret_cast <>. Since you are allowed to store variables in the memory manager until you dynamically allocate memory, you can track the list header with a member variable. You may need to pay particular attention to the size of the object (are all objects the same size? Is the size of the object larger than the size of the linked list node?)

Assuming the answers to the previous questions are correct, you can process the memory block and divide it into smaller pieces the size of an object using the list associated with the helper, which tracks free nodes. Your loose node structure will be something like

 struct FreeListNode { FreeListNode* Next; }; 

When distributing everything, you remove the node head from the free list and return it. Releasing is simply inserting a freed block of memory into a free list. Dividing a memory block up is just a loop:

 // static_cast only needed if constructor takes a void pointer; can't perform pointer arithmetic on void* char* memoryEnd = static_cast<char*>(memory) + totalSize; for (char* blockStart = block; blockStart < memoryEnd; blockStart += objectSize) { FreeListNode* freeNode = reinterpret_cast<FreeListNode*>(blockStart); freeNode->Next = freeListHead; freeListHead = freeNode; } 

As you mentioned, the Allocate function takes the size of the object, in order to save metadata it will be necessary to change this above. You can do this by including the size of the free block in the free list of node data. This eliminates the need to separate the start block, but introduces complexity in Allocate () and Deallocate (). You will also need to worry about memory fragmentation, because if you do not have a free block with enough memory to store the requested amount, then nothing you can do, in addition to not performing the allocation, does not exist. A pair of Allocate () algorithms could be:

1) Just return the first available block large enough to hold the request, updating the free block if necessary. This is O (n) in terms of searching in a free list, but it may not be necessary to search for a large number of free blocks and may lead to fragmentation problems in the future.

2) Find a free list for a block that has a minimum amount of free space for memory storage. This is still O (n) in terms of finding a free list, because you have to look at each node to find the least wasteful, but can help delay fragmentation issues.

In any case, with a variable size, you should also store metadata for distributions. If you cannot dynamically allocate at all, the best place is before or after the block requested by the user; you can add functions to detect buffer overflows / overflows during Deallocate () if you want to add a registration that is initialized with a known value, and check the addition for the difference. You can also add a compact step, as indicated in another answer, if you want to handle it.

One final note: you need to be careful when adding metadata to the FreeListNode helper structure, since the minimum free block size is sizeof (FreeListNode). This is because you store metadata in the freest block of memory. The more metadata you need to store for your internal purposes, the more wasteful your memory manager will be.

Answer 2

When you manage memory, you usually want to use the memory in which you want to store any metadata that you need. If you look at any of the malloc implementations (ptmalloc, phkmalloc, tcmalloc, etc.), you will see how they are implemented (neglecting any static data, of course). The algorithms and structures are very different, for various reasons, but I will try to give a little idea of ​​what is happening with general memory management.

Managing homogeneous chunks of memory is different than managing heterogeneous chunks, and this can be much simpler. Example...

 MemoryManager::MemoryManager() { this->map = std::bitset<count>(); this->mem = malloc(size * count); for (int i = 0; i < count; i++) this->map.set(i); } 

Isolation is a matter of finding the next bit in std::bitset (the compiler can optimize), marking the piece as selected and returning it. De-distribution simply requires the calculation of the index and labeling as unallocated. A free list is another way (as described here ), but it is a bit less efficient memory and may not use the CPU cache.

A free list can be the basis for managing heterogeneous pieces of memory. In this case, you need to save the size of the pieces in addition to the next pointer in the piece of memory. Size allows you to divide large pieces into smaller pieces. This usually leads to fragmentation, since the merging of pieces is nontrivial. This is why most data structures contain lists with the same size and try to match queries as accurately as possible.