This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

| Dynamic Memory Allocator Submitted by

Editor's Note: The description can be found in the comments at the top of the code listing.

Download Associated File: memory.c (14,429 bytes)

    /***********************************************************************
     *  Memory.c:
     *  Copyright (c) 2001, Eidatsu Interactive, Inc.
     *                      All Rights Reserved
     *  Version: 0.0.0-1
     *
     *  Revision History:
     *   *
     *
     *  Notes:
     *   * This is a total rewrite of the previous memory manager featured
     *     on flipcode's COTD.  The previous memory manager had a few
     *     dormant bugs that would cause corruption of the memory heap,
     *     and, only in some *rare* cases, a crash.  Obviously, these bugs
     *     were hard to track down.  Other than bug fixes, this total
     *     rewrite features MUCH MUCH MUCH cleaner and more easy-to-read
     *     code.  Yay!
     *
     *   * This code contains calls to functions and macros in our run-time
     *     library.  These functions are not included, but their purpose
     *     should be pretty clear, and not need any further documentation.
     *
     *   * Oh, and unlike the previous version, this version of the dyn
     *     memory allocator is now thread-safe.
     *
     *   * ALL of the following functions are heavily dependant on machine
     *     size and architecture.  Word-size is expected to be 32 bits.
     **********************************************************************/

    /***********************************************************************
     *  Function Declarations
     **********************************************************************/

    private void* _Alloc         ( uword );
    private void  _Free          ( void* );

    export  void* MemAlloc       ( uword );
    export  void* MemReAlloc     ( void*, uword );
    export  void  MemFree        ( void* );

    public  word  _MemInitialize ( void );
    public  void  _MemShutdown   ( void );

    /* Not included. */
    export  void  MemCopy        ( void*, const void*, uword );
    export  void  MemMove        ( void*, const void*, uword );
    export  void  MemFill        ( void*, uword, uint8 );

    /***********************************************************************
     *  Global Variables
     **********************************************************************/

    private Mutex_t  gMemMutex;

    private DWORD    gPageSize;

    private uword   *gFirstSuperBlock;
    private uword   *gEndOfLastSuperBlock;
    private uword   *gLastUsedBlock;

    /***********************************************************************
     *  Function Macros
     **********************************************************************/

    #define MemArrayAlloc( size, count ) \
              MemAlloc( (size) * (count) )

    #define MemArrayReAlloc( ptr, size, count ) \
              MemReAlloc( ptr, (size) * (count) )

    #define MemZero( ptr, count ) \
              MemFill( ptr, count, 0x00 )

    /***********************************************************************
     *  Functions
     **********************************************************************/

    /*  Block Header:
     *    ----------------
     *   | Block Size |E|F|
     *    ----------------
     *
     *    Block Size:  The offset to the next block header.
     *    E:           Flag is set if this is the last block.
     *    F:           Flag is set if this block is full (allocated).
     *
     *  Superblock:
     *    --------------
     *   | Prev Pointer |
     *    --------------
     *   | Block Header | ---> E=0     F=1
     *    --------------
     *   |     DATA     |
     *    --------------
     *   |     ....     |
     *    --------------
     *   |     DATA     |
     *    --------------
     *   | Block Header | ---> E=1     F=0
     *    --------------
     *   |    EMPTY     |
     *    --------------
     *   |     ....     |
     *    --------------
     *   |    EMPTY     |
     *    --------------
     *   | Next Pointer |
     *    --------------
     *
     *    Prev Pointer:  Pointer to the previous superblock.
     *    Next Pointer:  Pointer to the next superblock.
     *
     *       The superblocks are kept in a circular linked list.  If
     *    there is only one superblock, then both it's "next" and "prev"
     *    pointers point to the first byte in the superblock (which,
     *    coincidentally, is the "prev" pointer).
     */
    private
    void*
    _Alloc
      ( uword Size )
    {
      uword *tmpblk;
      uword  NewSupBlockSize, tmpi;

      /* We round the requested size up to the nearest multiple of eight
       * bytes, and then add a four byte buffer.  We also set tmpblk to
       * gLastUsedBlock, as is required for the next block of code. */
      Size   = ((Size + 7) & 0xFFFFFFF8) + 4;
      tmpblk = gLastUsedBlock;

      /* We now do a search through the entire heap to see if there is
       * a block of the right size available. */
        do
      {
        /* If we find an unused block of the appropriate size, then
         * we break out of this loop to the BlockFound label below. */
        if ( (*tmpblk & 0x1) == 0 )
          if ( (((*tmpblk >> 2) - 1) << 2) > Size )
            goto BlockFound;

        /* Otherwise we advance to the next block header.  If the
         * block we are currently looking at is the last in the
         * superblock (the end bit is set), then we must advance
         * one more time to the first block in the next
         * superblock. */
        tmpi   = *tmpblk;
        tmpblk =  tmpblk + (tmpi >> 2);
        if ( (tmpi & 0x2) != 0 )
          tmpblk = (uword*)( *tmpblk + sizeof(uword) );
      }
        while ( tmpblk != gLastUsedBlock );

      /* A block of the appropriate size was not found.  We must
       * therefore request another chunk of memory from the
       * operating system.  The new chunk of memory must be large
       * enough to hold the requested memory, two pointers, and
       * a block header, and must be a multiple of gPageSize.
       *
       * In the following calculation we assume that gPageSize is
       * a power of 2. */
      NewSupBlockSize = (Size + 3 * sizeof(uword) + gPageSize - 1) &
                         ~(gPageSize - 1);

      tmpblk = VirtualAlloc( NULL, NewSupBlockSize,
                             MEM_RESERVE | MEM_COMMIT,
                             PAGE_READWRITE );

      if ( tmpblk == NULL )
        return NULL;

      /* Set the Prev pointer. */
      *tmpblk = *gFirstSuperBlock;

      /* Insert this new superblock into the heap as the last
       * superblock. */
      *gFirstSuperBlock     = (uword)  tmpblk;
      *gEndOfLastSuperBlock = (uword)  tmpblk;
       gEndOfLastSuperBlock = tmpblk + (NewSupBlockSize >> 2) - 1;

      /* Now set the Next pointer, which gEndOfLastSuperBlock
       * now points to. */
      *gEndOfLastSuperBlock = (uword) gFirstSuperBlock;

      /* Before we move on to allocate the new block, we set up
       * a default block the size of the newly allocated space,
       * and set tmpblk equal to it's header. */
      ++tmpblk;
       *tmpblk = (NewSupBlockSize - 2 * sizeof(uword)) | 0x2;

    BlockFound:

      /* If the block we found is too big, we split it.  The cut-off
       * limit of 24 is arbitrary.  I have absolutly no idea what an
       * optimal cut-off limit in real life situations would be.  24
       * just sounded good.
       *
       * If we split, then we set gLastUsedBlock to the value of the
       * second (free) block, otherwise we set it to the value of the
       * block being used. */
      if
        ( ((*tmpblk & 0xFFFFFFFC) - sizeof(uword) - Size) > 24 )
      {
         gLastUsedBlock = tmpblk + 1 + (Size >> 2);
        *gLastUsedBlock = *tmpblk - Size - sizeof(uword);
        *tmpblk         = (Size + sizeof(uword)) | 0x1;
      }
        else
      {
        *tmpblk         = *tmpblk | 0x1;
         gLastUsedBlock = tmpblk;
      }

      return tmpblk + 1;
    }

    private
    void
    _Free
      ( void *Ptr )
    {
      uword *BlockToBeFreed, *BlockItr, *SupBlockFreedFrom;
      uword  tmpi;

      /* The value passed to this function should be a pointer
       * to the first byte of memory that was allocated - the
       * same value that was returned from _Alloc().  To get
       * the header of the block we're freeing, we simply move
       * back one uword. */
      BlockToBeFreed = ((uword*) Ptr) - 1;

      /* We clear the "full" bit in the block header. */
      *BlockToBeFreed = *BlockToBeFreed ^ 0x1;

      /* Finding the next block after the one being freed is
       * easy. */
      if
        ( (*BlockToBeFreed & 0x2) != 0 )
      {
        /* We use BlockItr as a temporary. */
        BlockItr = BlockToBeFreed + (*BlockToBeFreed >> 2);

        /* If the next block is empty, we merge it and the
         * block now being freed. */
        if ( (*BlockItr & 0x1) == 0 )
          *BlockToBeFreed += *BlockItr;
      }

      /* Now we find the previous block to the one being freed.
       * This is a little more time consuming, as we need to
       * advance all the way to the next superblock, use the
       * Prev pointer to get back to the beginning of the
       * superblock we're in, and then advance to the block
       * right before the block we're freeing. */
      BlockItr = BlockToBeFreed;

        do
      {
        tmpi      = *BlockItr;
        BlockItr += tmpi >> 2;
      }
        while ( (tmpi & 0x2) != 0 );

      SupBlockFreedFrom = **((uword***) BlockItr);
      BlockItr          = SupBlockFreedFrom + 1;

      if
        ( BlockItr != BlockToBeFreed )
      {
        while ( BlockItr + (*BlockItr >> 2) != BlockToBeFreed )
          BlockItr += (*BlockItr >> 2);

        /* If the previous block is empty, we merge it and the
         * block being freed. */
        if
          ( (*BlockItr & 0x1) == 0 )
        {
          *BlockItr       += *BlockToBeFreed;
           BlockToBeFreed  =  BlockItr;
        }
      }

      /* We set gLastBlockUsed to the value of BlockToBeFreed.
       * That way the next call to _Alloc() will begin its search
       * for free memory with an empty block, hopefully saving
       * time in the long run. */
      gLastUsedBlock = BlockToBeFreed;

      /* Now we test to see if the superblock is empty, and if
       * it is, then we request the operating system to free
       * it. */
      if
        ( (*(SupBlockFreedFrom + 1) & 0x2) != 0 )
      {
        /* We do not deallocate the superblock if it is the
         * superblock pointed to by gFirstSuperBlock - that way
         * we can be assured that there will always be at least
         * one superblock in memory. */
        if
          ( SupBlockFreedFrom != gFirstSuperBlock )
        {
          /* Before we free the superblock we must first remove it
           * from the global list of superblocks. */

          /* First we advance BlockItr to the Prev pointer in the
           * next superblock, taking advantage of the fact that we
           * know this superblock to contain only one unused block. */
          BlockItr  = SupBlockFreedFrom + 1;
          BlockItr += *BlockItr >> 2;
          BlockItr  = *((uword**) BlockItr);

          /* And then set this Prev pointer to the value of the Prev
           * pointer in the superblock being freed. */
          *BlockItr = *SupBlockFreedFrom;

          /* In order to save on the number of variables we have,
           * we use BlockToBeFreed as a temporary. */
          BlockToBeFreed = BlockItr;

          /* Now we set BlockItr to the beginning of the previous
           * superblock, and advance until we reach the Next pointer
           * at the end of the superblock. */
          BlockItr = *((uword**) SupBlockFreedFrom) + 1;

            do
          {
            tmpi      = *BlockItr;
            BlockItr += tmpi >> 2;
          }
            while ( (tmpi & 0x2) == 0 );

          /* Now we set the Next pointer in the previous superblock to
           * the address of the superblock after the one being freed.
           * BlockToBeFreed, in this case, is just a temporary
           * containing a pointer to the next superblock. */
          *BlockItr = (uword) BlockToBeFreed;

          VirtualFree( SupBlockFreedFrom, 0, MEM_DECOMMIT | MEM_RELEASE );

          /* Finally, we must choose another value for gLastBlockUsed,
           * since we just deallocated the memory it pointed to.  We
           * simply play it safe and point it at the only block we
           * know to be in existance - the first one. */
          gLastUsedBlock = gFirstSuperBlock + 1;
        }
      }

      return;
    }

    export
    void*
    MemAlloc
      ( uword Size )
    {
      void *Mem;

      MutexLock( &gMemMutex );

      Mem = _Alloc( Size );

      MutexUnLock( &gMemMutex );

      return Mem;
    }

    export
    void*
    MemReAlloc
      ( void *OldMemory, uword NewSize )
    {
      void  *NewMemory;
      uword  OldSize;

      MutexLock( &gMemMutex );

        do
      {
        if
          ( NULL == OldMemory )
        {
          /* If OldMemory is NULL, then the user is simply requesting
           * that NewSize bytes be allocated. */
          NewMemory = _Alloc( NewSize );
          break;
        }
          else if ( NewSize == 0 )
        {
          /* If NewSize is zero, then the user is requesting that
           * OldMemory be freed. */
          _Free( OldMemory );
          break;
        }
          else
        {
          /* Otherwise the user is requesting that the memory block
           * pointed to by OldMemory be either increased or decreased
           * to NewSize bytes. */
          OldSize = ((*(((uword*) OldMemory) - 1) >> 2) + 1) << 2;

          if
            ( NewSize > OldSize )
          {
            NewMemory = _Alloc( NewSize );

            if ( NewMemory == NULL )
              break;

            MemCopy( NewMemory, OldMemory, OldSize );
            MemFree( OldMemory );

            break;
          }
        }
      }
        while ( 0 );

      MutexUnLock( &gMemMutex );

      return NewMemory;
    }

    export
    void
    MemFree
      ( void *Ptr )
    {
      MutexLock( &gMemMutex );

      _Free( Ptr );

      MutexUnLock( &gMemMutex );

      return;
    }

    public
    word
    _MemInitialize
      ( void )
    {
      SYSTEM_INFO SystInfo;

      MutexCreate( &gMemMutex );

      GetSystemInfo( &SystInfo );

      gPageSize = SystInfo.dwPageSize;

      if ( gPageSize <= 0 )
        return -1; /* FIXME: need error code */

      gFirstSuperBlock = VirtualAlloc( NULL, gPageSize,
                                       MEM_COMMIT | MEM_RESERVE,
                                       PAGE_READWRITE );

      if ( gFirstSuperBlock == NULL )
        return -1; /* FIXME: need error code */

      gLastUsedBlock        = gFirstSuperBlock + 1;
      gEndOfLastSuperBlock  = (uword*)(((byte*) gFirstSuperBlock) +
                               gPageSize - sizeof(uword));
      *gFirstSuperBlock     = (uword) gFirstSuperBlock;
      *gEndOfLastSuperBlock = (uword) gFirstSuperBlock;
      *gLastUsedBlock       = (gPageSize - sizeof(uword) * 2) | 0x2;

      return 0;
    }

    public
    void
    _MemShutdown
      ( void )
    {
      /* No heap cleanup routines provided, as they are usually not
       * needed (the operating system deallocates all memory when
       * the application exits).  This would, however, be a good
       * place to call routines that browse the heap and print
       * memory information to a log file, as any allocated
       * memory present when this function is called may safely
       * be considered a memory leak. */

      MutexDestroy( &gMemMutex );

      return;
    }

    /***********************************************************************
     *  The End
     **********************************************************************/

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.