Fixed memory manager in C

Question

I decided to not use heap in my program and create a custom memory manager to retrieve memory chunks from a big global array of uint8_t(u8). I chose u8 since 8 bits is a byte. The very big MEMORY_BLOCK_SIZE is not a problem since in Release builds the compiler will remove the unused bytes. I keep track of free memory chunks with something i call "lookups".

#include <assert.h>

// NOTE: null is a redefinition of NULL
// NOTE: u8 = uint8_t
// NOTE: u64 = uint64_t

#define MEMORY_BLOCK_SIZE 8388608
#define MEMORY_LOOKUPS 8

static u8 memoryBlock[ MEMORY_BLOCK_SIZE ];
static u8* memoryLookups[ MEMORY_LOOKUPS ];
static u64 memoryLookupsSizes[ MEMORY_LOOKUPS ];

void memoryInit( void )
{
     memoryLookups[ 0 ] = memoryBlock;
     memoryLookupsSizes[ 0 ] = MEMORY_BLOCK_SIZE;
}

u8* requestMemoryChunk( u64 size )
{
     assert( size );

     u8* usablePtr = null;
     u64 ptrPosition;

     for( u64 i = MEMORY_LOOKUPS; i >= 0; --i )
     {
          if( ( !( memoryLookups[ i ] ) ) &&
                ( memoryLookupsSizes[ i ] >= size ) )
          {
                usablePtr = memoryLookups[ i ];
                ptrPosition = i;
                break;
          }
     }

     assert( usablePtr );

     u8* block = usablePtr;
     
     memoryLookupsSizes[ ptrPosition ] -= size;

     if( !( memoryLookupsSizes[ ptrPosition ] ) )
          memoryLookups[ ptrPosition ] = null;
     else 
          memoryLookups[ ptrPosition ] = usablePtr + size;

     return block;
}

void freeMemoryChunk( u64 size, u8* block )
{
     assert( block && size );

     for( u64 i = 0; i < MEMORY_LOOKUPS; ++i )
     {
          if( ! ( memoryLookups[ i ] ) )
          {
                memoryLookups[ i ] = block;
                memoryLookupsSizes[ i ] = size;
                
                break;
          }
     }
}
```

in the request function, shouldn't it be if(lookups && sizes) rather than if(!lookups && sizes) — Hannah W.
– Hannah W., Commented May 3, 2021 at 21:55
for( u64 i = MEMORY_LOOKUPS; i >= 0; --i ) will never stop, i will wrap around to the maximum value of uint64_t. — Rish
– Rish, Commented May 4, 2021 at 11:16

Lundin · Accepted Answer · 2021-05-05 11:51:23Z

You can't really implement a memory manager system like this in standard C. It would have to rely on standard extensions and specific compiler options. The main reason for this is "the strict aliasing rule"... (What is the strict aliasing rule?)
...but also alignment, you shouldn't write a library that hands out misaligned chunks of memory. If you look at malloc & friends they only work since they have a requirement (from the C standard 7.22.3):

The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object with a fundamental alignment requirement and then used to access such an object or an array of such objects in the space allocated (until the space is explicitly deallocated).
As noted in another review, you shouldn't come up with home-brewed, secret aliases for standardized terms. Use stdint.h with uint8_t etc. Use NULL. In particular, don't re-define NULL to something custom since that can cause all manner of subtle bugs. See What's the difference between null pointers and NULL? for details.
Bug here: for( u64 i = MEMORY_LOOKUPS; i >= 0; --i ) An u64 is always >= 0. Decent compilers ought to warn you here. In general, bugs like this can be avoided by always iterating from 0 and upwards, then change the indexing instead: arr[MAX - i] etc.
Generally, library quality code does not check if parameters passed are NULL, 0 etc. Such things are handled by documentation and making it the caller's responsibility to not pass on trash parameters.
Your routines ought to keep track of the last used memory location instead of searching for it in run-time. I take it that some of these might be freed so you'd get gaps in the look-up table, but then you should ask yourself if an array is really the right container class to use. You could for example use a BST instead, sorted after memory address.
Your code doesn't seem to address fragmentation at all.
The very big MEMORY_BLOCK_SIZE is not a problem since in Release builds the compiler will remove the unused bytes.

I wouldn't be so sure about that, it depends a lot on system and context.

Hannah W. · Accepted Answer · 2021-05-03 22:16:22Z

Please, please, don't rename NULL, uint8_t and uint64_t. It makes your code super hard to read. If you really don't want to type all that out then do a find replace after you're done coding.

Well aware that checking if(!x) is the same as if(x == NULL) and if(x == 0). But ultimately, I have to favor the explicit versions for readability.

Also

for(int x=0; x< MEMORY_LOOKUPS; x++) {
    uint8_t* x = requestMemoryChunk(MEMORY_BLOCK_SIZE - 1 - x);
    freeMemoryChunk(x, MEMORY_BLOCK_SIZE - 1 - x);
}
uint8_t* y = requestMemoryChunk(2);
// you just lost 99.99% of your memory

If this example is too extreme, consider

for(int x=0; x< MEMORY_LOOKUPS; x++) {
    uint8_t* x = requestMemoryChunk(10000 - x);
    freeMemoryChunk(x, 10000 - x);
}
uint8_t* y = requestMemoryChunk(2);
// you just lost ~10000 bytes of memory

Consider snapping the requests to block sizes (eg powers of 2) to avoid these kinds of pathological requests. Further consider keeping the lookups sorted by size.

Stylistically things are ok. There are some unnecessary parentheses in the if conditions but (... y'know lisp exists)

Ultimately, people code in c for efficiency and control. One expects to lose some readability doing clever things. But there's no reason to not explain the clever stuff in comments.

Thanks for the review, I agree to all the points you mentioned. I tought u64/u8/null wasn't hard to read since it is a c programming practice quite diffused. To solve the memory waste problem you should modify the MEMORY_LOOKUPS to suit your program needs. (same as MEMORY_BLOCK_SIZE). I try to keep this as low as possible because the more lookups the program checks for the more iterations it has to do. — cynnad
– cynnad, Commented May 4, 2021 at 16:27

Stack Exchange Network

Fixed memory manager in C

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Fixed memory manager in C

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions