3
\$\begingroup\$

I took on a for-fun task of creating a memory allocator which uses process memory rather than making a bunch of system calls to the operating system. The task was: implement my own malloc() and free() functions which are limited to a pool (stack array) of 20000 bytes. I already had my own malloc and free implementations which used the sbrk() in unistd.h, but I realized the difference here would be that I need to re-create an sbrk that instead of getting memory from the OS, gets memory from my array. I had no experience doing this and was quite frankly pretty unfamiliar with how sbrk() worked internally. Even more, I still don't fully understand unistd's sbrk() integer pointer param. Nevertheless, I came up with a way to imitate the functionality below:

#define MEMORY_CAPACITY 20000
//NOTE: These are GLOBAL variables below
char global_mem[MEMORY_CAPACITY] = {0};
void *p_break = &global_mem;
void* mov_sbrk(int increment)
{
    void *final_address = (char*) global_mem + (MEMORY_CAPACITY-1);
    void *original = p_break;
    if(increment == 0)
    {
        return p_break;
    }
    if(((char*)p_break + increment) < (char*)global_mem)
    {
        ERR("mov_sbrk: Cannot move to address prior to start of memory.");
        return (void*) -1;
    }
    if(((char*)p_break + increment) > (char*)final_address)
    {
        ERR("You've run out of memory!");
        return (void*) -1;
    }
    p_break = (void*) ((char*)p_break + increment);
    return original;

}

Note that ERR is just a macro for fprintf(stderr, msg). Please critique this implementation and let me know if I am missing anything. I've performed some tests with my allocator and so far, it performs as expected. The difference though is that I used a int because a int ptr like the "official" sbrk() uses as a parameter didn't make sense to me since it would force increments of the architecture's integer size rather than byte-by-byte.

\$\endgroup\$
  • 2
    \$\begingroup\$ Instead of explaining ERR, you should just include its definition in your program. Note that it then requires <stdio.h>, too, to declare fprintf(). \$\endgroup\$ – Toby Speight Aug 16 at 8:28
  • \$\begingroup\$ There's a lot of casts there. Not a good sign \$\endgroup\$ – Cacahuete Frito Aug 16 at 12:59
2
\$\begingroup\$

Interface: consider accepting larger types than int. The Linux man page says:

Various systems use various types for the argument of sbrk(). Common are int, ssize_t, ptrdiff_t, intptr_t.

ptrdiff_t seems like the most appropriate choice. Of course, it doesn't really matter with this implementation, as the capacity is less than 32768, and so even a minimal INT_MAX allocation will fail.


if(((char*)p_break + increment) < (char*)global_mem)

Since we have no guarantee that p_break + increment won't overflow, we should re-write that as:

if (increment < global_mem - (char*)p_break)

We know that global_mem - p_break can't overflow, as they are pointers into the same object.

Similarly,

if(((char*)p_break + increment) > (char*)final_address)

should be rewritten as

if (increment > (char*)final_address - (char*)p_break)

We can avoid all the casts here by using char* pointers rather than void* - only the public interface needs the void*.


I hope the ERR macro is compiled out in non-debug builds - users certainly won't want or expect output from sbrk.

The error paths should set errno to ENOMEM.


Modified code

#include <errno.h>

#define MEMORY_CAPACITY 20000

void *mov_sbrk(int increment)
{
    static char global_mem[MEMORY_CAPACITY] = {0};
    static char *p_break = global_mem;

    char *const limit = global_mem + MEMORY_CAPACITY;
    char *const original = p_break;

    if (increment < global_mem - p_break  ||  increment >= limit - p_break)
    {
        errno = ENOMEM;
        return (void*)-1;
    }
    p_break += increment;

    return original;
}

(I moved the global variables into the function to reduce their scope; that might not be appropriate if you also want to implement brk(), but I'm only reviewing the code I see!)

\$\endgroup\$
  • \$\begingroup\$ Question - Could there be any resulting bad effects of those 2 overflows occurring that you mentioned? As far as I knew, say that the math ends up overflowing, I'm never actually storing or accessing that overflowed address so was just curious if there was some other bad side effect of overflowing in the math even without an access or storage of the overflowed memory address? Thank you for your thorough and helpful answer \$\endgroup\$ – the_endian Aug 16 at 16:51
  • 2
    \$\begingroup\$ @the_endian The code inside the ifs might or might not get executed when it shouldn't/should. \$\endgroup\$ – Cacahuete Frito Aug 16 at 20:34
  • \$\begingroup\$ Pointer arithmetic overflow results in Undefined Behaviour, so absolutely anything is a possible outcome. Following the wrong branch of the conditional is the least bad outcome! \$\endgroup\$ – Toby Speight Aug 19 at 8:24

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.