Memory Management Code

Question

For a project I had to do a memory management problem without creating any custom classes or templates using the provided pool array and poolSize.

I implemented all functions and created two extra, SizeConversion and GetSize. My main question is this: is there a better way to implement this and is the code that I have clean and efficient?

const int poolSize = 65536;
char pool[poolSize];

int SizeConversion(int);
int GetSize(int, int);

// Initialize set up any data needed to manage the memory pool
void initializeMemoryManager(void)
{
    //Verify that the pool is preset to null
    for (int x = 0; x < poolSize; x++) {
        pool[x] = '\0';
    }
}

// return a pointer inside the memory pool
// If no chunk can accommodate aSize call onOutOfMemory()
void* allocate(int aSize)
{
    //Check if the allocation size requires more than 2 bytes to determine length
    if (aSize >= (256 * 256)) {
        onIllegalOperation("Allocation Size too Large");
        return nullptr;
    }
    else {
        int first = 0;
        int cur = 0;
        //Find the first location the data can be stored
        for (int x = 0; x < poolSize; x++) {
            //Save first location if not set, otherwise increment cur
            if (pool[x] == '\0') {
                if (cur == 0)
                    first = x;
                cur++;
            }
            else {
                cur = 0;
                //Get the integer value of the two size bytes
                int sr = (int)pool[x];
                int sl = (int)pool[x + 1];
                //Jump from current index to end of allocation then continue
                x = x + 1 + GetSize(sl, sr);
            }
            //If cur is larger than the necessary size, use 
            if (cur >= aSize + 2) {
                break;
            }
        }
        //Define the allocated data for display purposes to 'A'
        for (int x = first + 2; x < first + 2 + aSize; x++) {
            pool[x] = 'A';
        }
        //Define the size of the data from range of 1-255
        pool[first] = (char)((int)((aSize+1) / 256) + 1);
        pool[first + 1] = (char)((aSize - ((int)pool[first] - 1) * 256) + 1);
        //Return a pointer to the first value index of allocation
        return ((void*)(pool + first + 2));
    }
}

//Since characters are signed, if they are below zero then continue normal ordering
int SizeConversion(int x) {
    if (x < 0) {
        x = 256 + x;
    }
    return x;
}

//Get the total size of a single allocation
int GetSize(int right, int left) {
    //Convert characters to correct integer values
    right = SizeConversion(right);
    left = SizeConversion(left);
    //Get the total allocation size of entry
    int r = (right - 1) + (left - 1) * 256;
    return r;
}

// Free up a chunk previously allocated
void deallocate(void* aPointer)
{
    if (aPointer == nullptr)
        onIllegalOperation("Cannot Deallocate Pointer Without Address");
    else {
        //Convert Characters to integers for sizing
        int x1 = (int)(*((char*)aPointer - 1));
        int x2 = ((int)(*((char*)aPointer - 2)));
        //Get the total allocation size of entry
        int x = GetSize(x1, x2);
        int i = 0;
        //Deallocate values
        while (x > i) {
            *((char*)aPointer + i) = '\0';
            i++;
        }
        //Deallocated Allocation size parameters
        *((char*)aPointer - 1) = '\0';
        *((char*)aPointer - 2) = '\0';
    }
}

// Will scan the memory pool and return the total free space remaining
int freeRemaining(void)
{
    int remaining = 0;
    for (int x = 0; x < poolSize; x++) {
        //Increase remaining if location is null
        if (pool[x] == '\0') {
            remaining++;
        }
        else {
            //Get the integer value of the two size bytes
            int sr = (int)pool[x];
            int sl = (int)pool[x + 1];
            //Jump from current index to end of allocation then continue
            x = x + 1 + GetSize(sl, sr);
        }
    }

    return remaining;
}

//Scans the memory pool and return the largest free space remaining
int largestFree(void)
{
    int largest = 0;
    int cur = 0;
    for (int x = 0; x < poolSize; x++) {
        //Increase cur if index value is null and set largest if cur is bigger
        if (pool[x] == '\0') {
            cur++;
            if (cur > largest)
                largest = cur;
        }
        else {
            cur = 0;
            //Get the integer value of the two size bytes
            int sr = (int)pool[x];
            int sl = (int)pool[x + 1];
            //Jump from current index to end of allocation then continue
            x = x + 1 + GetSize(sl, sr);
        }
    }
    return largest;
}

//Scans the memory pool and return the smallest free space remaining
int smallestFree(void)
{
    int smallest = poolSize;
    int cur = 0;
    for (int x = 0; x < poolSize; x++) {
        if (pool[x] == '\0') {
            cur++;
            if (cur < smallest)
                smallest = cur;
        }
        else {
            cur = 0;
            //Get the integer value of the two size bytes
            int sr = (int)pool[x];
            int sl = (int)pool[x + 1];
            //Jump from current index to end of allocation then continue
            x = x + 1 + GetSize(sl, sr);
        }
    }
    return smallest;
}

Answer 1

You have a pool:

const int poolSize = 65536;
char pool[poolSize];

The problem with allocating pools like this (via char array). Is that the language gives you no guarantees about the alignment of pool. If on the other hand you used a std::vector<char> pool(poolSize); then the language guarantees that the &pool[0] is aligned for all types of size poolSize or smaller (see requirements for dynamically allocated memory).

The maximum size of the pool is 65536 so this can be represented by 2 bytes. So every block will keep a two byte prefix of its length so that when we de-allocate it we know how many bytes have been added back into the system.

Note: We need this prefix size even when the block is allocated. Also this means there is a two byte additional overhead when allocating blocks.

Also each free block has to know the next block. Again the next free block has a number of in the range [0-65535] so it can be represented as two bytes.

Note: This data is only used when the object has been freed. So it can be used by the application as part of the data space. But it means that that the minimum block size that will be allocated is 2 (so 0/1 sized blocks will not be optimal).

Answer 2

1. As far as efficiency goes, what are you trying to optimize, speed or size? Loki Astari has a valid point about alignment, and also about a free list. A free list would speed up a couple of your functions (largestFree(), smallestFree(), freeRemaining()), but would use more memory. Using largestFree() and smallestFree() might improve the performance of your allocate() function.
2. To optimize speed you might want to look at using memset (http://en.cppreference.com/w/cpp/string/byte/memset).
3. You use a number of C style casts, for C++ it is better to use static_cast or dynamic_cast. Both static_cast and dynamic_cast are more type safe, static_cast does compile time checking and dynamic_cast does runtime checking.
4. Was it specified that you couldn't use structs? The free list could be implemented with either an array of structs or 2 arrays, one of addresses of free blocks and the other of sizes of the free blocks using the same index into the array.