The Mullocator - Part IV - Testing Boundaries

As we'll see soon, the complicated part of malloc isn't actually malloc, it's free. Let's look at the code from Part I again, for simplicity.

static inline void  *malloc( size_t size)
{
   extern long  memory[];
   extern long  *sentinel;
   extern long  *buf;
   void         *p;
   long         *q;
   
   /* assume the compiler does reduce that to shifting, it will... */
   q = &buf[ (size + sizeof( long) - 1) / sizeof( long)];  
   if( q > sentinel)
      return( NULL);

   p   = buf;
   buf = q;
   return( p);
}

We have a huge memory block, where we are cutting of pieces and returning them. There is ONE extremely easy free operation, and that is if the last recently allocated block of memory is returned. We could just bump the buf pointer down to it's previous value and that memory could be reused again. (It'd be easy if we would remember something about it...)

main()
{
    long   *p;

   p = malloc( 1848 * sizeof( long));
   free( p);
}

Before the malloc call, buf will be pointing at memory. Afterwards buf is now pointing to &memory[ 1848]. If the address of memory (now contained in p) gets freed, we could and would want to shrink buf back to memory.

void free( void *p)
{
   if( p == memory)
      buf = memory;
}

The problem is we can't do that. We do not know if p is the most recently allocated block, because we don't remember it. As a simple example like this shows:

main()
{
    long  *p, *q;

   p = malloc( 1 * sizeof( long));    // but now &memory[ 1]
   q = malloc( 1 * sizeof( long));    // but now &memory[ 2]
   free( p);                          // but now &memory[ 0] *BAD*
   p = malloc( 2 * sizeof( long));
   
   assert( p >= q);
   assert( &p[ 2] <= q);  // crash
}

Which leads to the conclusion that we need to store the size of a memory block if we want to be able to free it again. It doesn't matter if we save the end address or the length of the block, because we can compute either from the other.

The more interesting question is where do we save the length of the block ?

This open question concludes the first four parts. We now have a feeling for what would be the fastest malloc and free speed. What we don't really know is, what kind of real life stress malloc faces. That's for the next series, where we actually make some empirical testing and things become a little more interesting...

Hopefully :)