4
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Is this a pool allocator for generic types? Or for char objects? If it is used for strings then potentially OK. But objects of type T have both space and alignment characteristics. You may be using size but have not considered alignment. Once memory is allocated you can't count on it having and particular value. So scanning for '\0' will not work in the general case. \$\endgroup\$ – Martin York Mar 4 '16 at 18:32
  • \$\begingroup\$ A memory Pool usually has two things. 1) An array of memory. 2) A free list (a list of blocks that are free). When the pool is initialized the free list contains one item (the whole pool). When allocating from the pool you scan the free list for a chunk of memory the correct size. If you can find one you take a larger free block and split it into two parts. The free list can be a separate structure but an optimization is to build it inside your pool in the unused blocks themselves. \$\endgroup\$ – Martin York Mar 4 '16 at 18:38
  • \$\begingroup\$ This should be used for generic types. I actually ran into that issue on an earlier attempt when I tried just adding a beginning and ending null character '\0' and a string was added, since they end in a null character for parsing. I would have liked to add a separate list, however I wasn't allowed to create any more global variables for this assignment. What would be the best method for defining the free list within the pool itself? Simply breaking into block sizes; ex : a variable is inserted at 80-100 for pool size 300, so you put 2 values [79, 101]? Or is there a better way? \$\endgroup\$ – Ray McClain Mar 5 '16 at 1:39
  • \$\begingroup\$ If you can't add an extra variable. Then make the first element of the free list at pool[0] \$\endgroup\$ – Martin York Mar 5 '16 at 10:14
  • \$\begingroup\$ If you can add an extra variable. Then use a static member variable inside the function. \$\endgroup\$ – Martin York Mar 5 '16 at 18:35
3
\$\begingroup\$

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).

\$\endgroup\$
1
\$\begingroup\$
  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.
\$\endgroup\$
  • \$\begingroup\$ For this specific assignment, I believe speed is ideal. Unfortunately I couldn't use structs in the assignment. I will take a look at those optimizations you pointed out and correct the areas that have multiple casts. \$\endgroup\$ – Ray McClain Mar 5 '16 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.