Questions regarding specialized malloc()/free() replacements

[Stephan Beal]

Hello, all!

i'm working on an embedded filesystem library for C (http://
fossil.wanderinghorse.net/repos/whefs/) where one of the priorities is
keeping the memory costs and number of calls to malloc() at an
absolute minimum (i'd like to target very small devices some day). By
using custom routines for alloc/free, i've been able to get a virtual
filesystem running with only a single call to malloc() (which happens
deep inside fopen(), so i can't avoid that one).

My question is regarding the technique i'm using (the code is shown
below), and:

a) Is the implementation halfway sane?

b) Is there a comparable, but more canon approach to achieve this?

c) Are there any glaring problems which i've overlooked? (Aside from
the inherent non-threadsafeness of the alloc routine, of which i'm
aware but can live with for the current use case.)

i'm satisfied with the results so far, but i also know that i'm no C
guru and i'm concerned that i may inadvertently be leading down a Dark
Path (and would very much like to avoid doing so).

In short, the allocator works like this:

- Pre-allocate N objects of type T via static initialization.
- Client calls T_create() to create the objects.
- T_create() (shown below) checks the pre-allocated list of objects.
If it finds an unused one, mark it used and return it. (This has an
inherent race condition, i'm aware of that.) If it doesn't find a free
slot, fall back to malloc().

The deallocator (T_free()) simply marks the object as free (if it
comes from our static pool) or falls back to free() if needed. (The
deallocator is, IMO, more interesting than the allocator because it is
O(1) and, as far as i can tell, is inherently thread-safe even though
it mucks with static data.)

The implementation (created via a shell script) is:

stephan@jareth:~/cvs/fossil/whefs$ ./makeStaticAlloc.sh MyType

/**
Works like malloc(), but beware...

Creates an empty, non-functional MyType object and returns it.
The object must be populated by the caller and must eventually
be destroyed by calling MyType_free() AFTER the private parts
of the object are cleaned up (see MyType_free() for details).

Clients of MyType objects SHOULD NOT use this routine - it is
intended for use by MyType factory/initialization routines for
reasons explained below.

This function is not required to be thread safe nor reentrant, and
a given implementation may use static data if needed. If it
dynamically allocates memory for its internal use then it "should"
clean up that memory via an atexit() handler or custom cleanup
mechanism beyond the scope of this interface.

A side effect of the undefined allocation rules is that objects
returned from this function may not be valid if used after main()
exits (e.g. via an atexit() handler) because the underlying
allocation mechanism might have been cleaned up already.

@see MyType_free()
*/
MyType * MyType_alloc();

/**
Deallocates MyType objects, but...

BIG FAT HAIRY WARNING:

- This function DOES NOT do any type-specific cleanup.
Instead, this function is intended to be called from
type-specific cleanup routines after any private data has
been freed.

This function effectively passes the given object to free(), but
the implementation is free to use a different alloc/dealloc
method. In any case, clients should treat obj as invalid after this
call.

@see MyType_alloc()
*/
void MyType_free( MyType * obj );

#if !defined(MYTYPE_ALLOC_USE_STATIC)
/**
If MYTYPE_ALLOC_USE_STATIC is true then we statically allocate
MyType_alloc_count MyType objects to dole out via
MyType_alloc(), falling back to malloc() if the list is full.

Depending on sizeof(MyType), we may not actually save much
dynamic memory, but we potentially save many calls to malloc().
That depends on the application, of course, but this idea
was implemented for a library where saving calls to malloc()
was a high-priority goal.
*/
#define MYTYPE_ALLOC_USE_STATIC 1
#endif


#if MYTYPE_ALLOC_USE_STATIC
enum {
/**
The number of elements to statically allocate
in the MyType_alloc_slots object.
*/
MyType_alloc_count = 10
};
#define MyType_alloc_slots_MyType_INIT {0 /* FILL THIS OUT FOR MyType
OBJECTS! */}
static struct
{
MyType objs[MyType_alloc_count];
char used[MyType_alloc_count];
} MyType_alloc_slots = { { MyType_alloc_slots_MyType_INIT }, {0} };
static const MyType MyType_alloc_prototype =
MyType_alloc_slots_MyType_INIT;
#undef MyType_alloc_slots_MyType_INIT
#endif

MyType * MyType_alloc()
{
MyType * obj = 0;
#if MYTYPE_ALLOC_USE_STATIC
size_t i = 0;
for( ; i < MyType_alloc_count; ++i )
{
if( MyType_alloc_slots.used ) continue;
MyType_alloc_slots.used = 1;
MyType_alloc_slots.objs = MyType_alloc_prototype;
obj = &MyType_alloc_slots.objs;
break;
}
#endif /* MYTYPE_ALLOC_USE_STATIC */
if( ! obj ) obj = (MyType *) malloc( sizeof(MyType) );
return obj;
}

void MyType_free( MyType * obj )
{
#if MYTYPE_ALLOC_USE_STATIC
if( (obj < &MyType_alloc_slots.objs[0]) ||
(obj > &MyType_alloc_slots.objs[MyType_alloc_count-1]) )
{ /* it does not belong to us */
free(obj);
return;
}
else
{
const size_t ndx = (obj - &MyType_alloc_slots.objs[0]);
MyType_alloc_slots.objs[ndx] = MyType_alloc_prototype;
MyType_alloc_slots.used[ndx] = 0;
return;
}
#else
free(obj);
#endif /* MYTYPE_ALLOC_USE_STATIC */
}

/* end code */

Many thanks in advance for your time and insights .

 

[Stephan Beal]

Why not use a linked list for free blocks? Then allocation and
deallocation are constant-time operations (unless you have to fall back on
malloc/free).

Good idea.

And remember that any custom allocator will not be as good
for finding usage bugs than malloc/free, which can benefit from tools like
valgrind.

That's how i've been testing whether my static allocs work - by
comparing valgrind results with and without static allocs turned on.

void MyType_init()
{
    int i;
    for ( i = 0; i < max_blocks - 1; ++i )
        blocks .next = &blocks [i + 1];
    blocks [max_blocks - 1].next = NULL;
    avail = blocks;

}

i was hoping to avoid something like this, but if it'll get me O(1)
alloc then it'd be worth it. In C++ it could be called automatically
with:

static const int foo = (MyType_init(),1);

but C won't allow that, so i'd have to call the init routine from
somewhere (maybe on the first call to the allocator).

void MyType_free( MyType* p )
{
    /* This might be technically non-portable, though portable in practice */
    if ( p != NULL && (void*) p >= blocks && (void*) p < blocks + max_blocks )

Why shouldn't this be portable? An array must, by definition, be a
contiguous range of memory, which means that any memory from outside
that range *must* compare not-equal. Or am i missing some voodoo
there? Are there platforms where arrays needn't be physically
contiguous (as long as they act like they are)?

    {
        Block* b = (Block*) p;
        b->next = avail;
        avail = b;
    }

Excellent! Thank you for that tip! Now time to go refactor...

 

[Stephan Beal]

Why shouldn't this be portable? An array must, by definition, be a
contiguous range of memory, which means that any memory from outside

Sorry, i missed the following lines:

/* This might be technically non-portable, though portable in
practice */
if ( p != NULL && (void*) p >= blocks && (void*) p < blocks +
max_blocks )
{
---> Block* b = (Block*) p;
b->next = avail;
avail = b;
}

now [i think] it's clear why it may not be portable.

 

[Barry Schwarz]

On Sun, 4 Jan 2009 02:28:36 -0800 (PST), Stephan Beal

snip

void MyType_free( MyType * obj );

#if !defined(MYTYPE_ALLOC_USE_STATIC)
/**
If MYTYPE_ALLOC_USE_STATIC is true then we statically allocate
MyType_alloc_count MyType objects to dole out via
MyType_alloc(), falling back to malloc() if the list is full.

Depending on sizeof(MyType), we may not actually save much
dynamic memory, but we potentially save many calls to malloc().
That depends on the application, of course, but this idea
was implemented for a library where saving calls to malloc()
was a high-priority goal.
*/
#define MYTYPE_ALLOC_USE_STATIC 1
#endif


#if MYTYPE_ALLOC_USE_STATIC
enum {
/**
The number of elements to statically allocate
in the MyType_alloc_slots object.
*/
MyType_alloc_count = 10
};
#define MyType_alloc_slots_MyType_INIT {0 /* FILL THIS OUT FOR MyType
OBJECTS! */}
static struct
{
MyType objs[MyType_alloc_count];
char used[MyType_alloc_count];
} MyType_alloc_slots = { { MyType_alloc_slots_MyType_INIT }, {0} };

Based on the code in your allocation function, the initialization for
the objs[0] is not needed. The initialization for used is superfluous
since any uninitialized static object will default to 0.

static const MyType MyType_alloc_prototype =
MyType_alloc_slots_MyType_INIT;
#undef MyType_alloc_slots_MyType_INIT

Just curious why you undef this macro.

#endif

MyType * MyType_alloc()
{
MyType * obj = 0;
#if MYTYPE_ALLOC_USE_STATIC
size_t i = 0;
for( ; i < MyType_alloc_count; ++i )
{
if( MyType_alloc_slots.used ) continue;
MyType_alloc_slots.used = 1;
MyType_alloc_slots.objs = MyType_alloc_prototype;

This is why the initialization above is not needed.

obj = &MyType_alloc_slots.objs;
break;
}
#endif /* MYTYPE_ALLOC_USE_STATIC */
if( ! obj ) obj = (MyType *) malloc( sizeof(MyType) );

Lose the cast. The only thing it does is prevent the compiler from
warning you about undefined behavior if there is not a proper
prototype for malloc in scope.

Why do you assign a value to a static *obj but not to an allocated
one? Surely the calling function should not care how you are
performing the allocation and should see the same result regardless.

return obj;
}

void MyType_free( MyType * obj )
{
#if MYTYPE_ALLOC_USE_STATIC
if( (obj < &MyType_alloc_slots.objs[0]) ||
(obj > &MyType_alloc_slots.objs[MyType_alloc_count-1]) )
{ /* it does not belong to us */
free(obj);
return;
}
else
{
const size_t ndx = (obj - &MyType_alloc_slots.objs[0]);
MyType_alloc_slots.objs[ndx] = MyType_alloc_prototype;

This assignment is also unnecessary.

MyType_alloc_slots.used[ndx] = 0;
return;
}
#else
free(obj);
#endif /* MYTYPE_ALLOC_USE_STATIC */
}