Memory allocation in C

Question

the following is a very very simple version of malloc() and seems to allocate some space to me, but apart from the fact that there is no free() and I don't check if I've overrun the allocated space, how can I check that the code is correct?

Any obvious blunders that "C" experts would slap me for?

#include <stdio.h>
#include <unistd.h>

#define MAX_MEMORY 1024 * 1024 * 2 /* 2MB of memory */

void *stack = NULL; /* pointer to available stack */
void * memoryAlloc(size) {
    if (stack == NULL)
        stack = sbrk(MAX_MEMORY); /* give us system memory */

    void *pointer;
    pointer = (void *)stack + size; /* we always have space :) */
    stack += size; /* move in stack forward as space allocated */
    return pointer;
}

Derbyshire

I wouldn't call the arena of memory "stack". Your current implementation is like a stack, yes, but if you intend this to work like malloc does, with free, then it is a heap. – Adamandeve

Thanks a lot guys for all your comments! – Derbyshire

This allocator is the beginning of something called a 'pool allocator' - allocations happen like the above, then the whole block is freed back to the system at once when the work unit using the pool is completed. It helps deal with leaks caused by having to manage each little allocation separately. Apache uses pools - an HTTP request comes in, a pool is setup for the request, when the request is complete the pool is freed. Nothing else working on the request needs to worry about freeing dynamically allocated objects. – Whistler

Answer 1

In addition to the basic problems Ned Batchelder pointed out, a much more subtle problem is that an allocator has to return an address that's properly aligned for whatever object is being allocated. On some platforms (x86) this may not matter except for performance issues, but on many platforms it's a complete deal breaker.

I also had to perform a (char*) cast to perform the stack pointer arithmetic (you can't do pointer arithmetic on void* types).

And you should put parens around the expression in the MAX_MEMORY macro. I don't think there are any precedence problems you'd get into without them, as all the high precedence operators than multiplication wouldn't be correct syntax anyway. With macros, it's always better safe than sorry. (There's at least one exception where the [] operator could bind only to the 2 and not the whole MAX_MEMORY expression, but it would be a very weird situation to see MAX_MEMORY[arrayname], even if it's syntactically valid).

As a matter of fact, I would have made it an enum.

You can probably keep the allocator simple by returning a block of memory that's properly aligned for any basic data type on the system (maybe an 8 byte alignment):

/* Note: the following is untested                   */
/*       it includes changes suggested by Batchelder */

#include <stdio.h>
#include <unistd.h>

enum {
    kMaxMemory = 1024 * 1024 * 2, /* 2MB of memory */
    kAlignment = 8
};

void *stack = NULL; /* pointer to available stack */
void * memoryAlloc( size_t size) {
    void *pointer;

    size = (size + kAlignment - 1) & ~(kAlignment - 1);   /* round size up so allocations stay aligned */

    if (stack == NULL)
    stack = sbrk(kMaxMemory); /* give us system memory */

    pointer = stack; /* we always have space :) */
    stack = (char*) stack + size;   /* move in stack forward as space allocated */
    return pointer;
}

Whistler

Answer 2

There are a few problems:

1. You declare pointer in the middle of the function, which isn't allowed in C.

2. You set pointer to stack+size, but you want it to be just stack. Otherwise, you're returning a pointer to the end of the block of memory you're allocating. As a result, if your caller uses all size bytes at that pointer, he'll be overlapping with another block of memory. If you get different sized blocks at different times, you'll have two callers trying to use the same bytes of memory.

3. When you do stack += size, you're incrementing stack not by size bytes but by size void*'s, which is almost always larger.

Headlock

Declarations in the middle of a function has been allowed since C99. – Adamandeve

The point about pointer increment is incorrect. When you are incrementing a void * pointer, you are incrementing not by size of void *, but by size of void, of course. void has no size, so the increment is illegal (in both C89/90 and C99). Some compilers allow this as an extension, treating void * as char * in pointer arithmetic (so the increment is correct as written above), but in any case it is an extension, not a standard C. – Aiguille

Answer 3

Firstly, as other have already noted, you are declaring variables in the middle of the block, which is only allowed in C99, but not in C89/90. I.e. we have to conclude that you are using C99.

Secondly, you are defining your function in K&R-style (no parameter type), but at the same time not declaring the parameter type later. That way you are relying on the "implicit int" rule, which is outlawed in C99. I.e. we have to conclude that your are not using C99. This is already a contradiction with the "firstly" part. (Additionally, it is customary to use unsigned types to represent the concept of "object size". size_t is a dedicated type normally used for that purpose).

Thirdly, you are using pointer arithmetic on a void * pointer, which is always illegal in both C89/90 and C99. I don't even know what we can conclude from that :)

Please, decide what language you are trying to use, and we will go from there.

Aiguille

I missed the implicit declaration of size. – Whistler

Thanks AndreyT, I am going to use C89 and you can conclude that I am a newbie but with a lot of helpful input now :). – Derbyshire