Ready, Set, Allocate! (Part 4)

Original Author: Paul Laska

Links to other parts:

In this part the free method is covered.

 The system used for development and testing is an old laptop running Windows XP Pro Service Pack 3, with a Pentium-M 1.6GHz 32-bit processor, 400MHz FSB, and 512MB of RAM.

 To release memory back to the allocation system, the following steps will be taken:

  1. Retrieve the allocation header.
  2. Determine the pages used to track the memory.
  3. Release the pages back into the memory heap.

 The free function signature looks like so:

void my_free (void* pMem)

pMem is the memory to be released back to the allocation system. The free function can be redirected similarly to malloc, using a define.

#define MYFREE( pMem )	my_free( pMem )

1. Retrieve the allocation header.

Recall, the allocation header was placed just prior to the address returned from malloc.  So to retrieve the allocation size and alignment information, the address pointed to by pMem is decremented by the size of an allocation header; this makes the address pointed to the beginning of the allocation header, so a quick cast and the allocation header members can be retrieved.

       // The tracking header exists just prior to the pMem pointer, step backwards the size of an allocation header to get it.
 
        u32 uSize = ((TALLOCATION_HEADER*)((u32)(pMem) - sizeof(TALLOCATION_HEADER)))->uSize;
 
        u32 uAlignment = ((TALLOCATION_HEADER*)((u32)(pMem) - sizeof(TALLOCATION_HEADER)))->uAlignment;

The amount of padding used before the header, to keep the memory aligned is determined, and used to move the pMem pointer back, so that when the memory is released, all the memory added for the allocation header is released as well.

      u32 uAllocationHeaderPaddingSize = ((sizeof(TALLOCATION_HEADER) % uAlignment) > 0) ? uAlignment - sizeof(TALLOCATION_HEADER) % uAlignment : 0;
 
        // Align the header, so the beginning address of the memory will be aligned.
 
        u32 uAllocationHeaderSize = sizeof( TALLOCATION_HEADER ) + uAllocationHeaderPaddingSize;
 
        // Move the pointer backwards to include the allocation header.
 
        pMem = (void*)( (u32)( pMem ) - uAllocationHeaderSize );

2. Determine the pages used to track the memory.

The first thing to do here is to figure out the “address”, or offset from the beginning of the memory being tracked.  Then the tracking unit where the allocation was started can be determined using the address.  Also the offset for the beginning bit/page within the first tracking unit is calculated using the address.

      u32 uAddress = (u32)(pMem) - (u32)(const_cast(kpMemory));
 
        u32 uBeginningTrackingUnit = uAddress / kMemPageSize / kMemNumPagesPerUnit;
 
        u32 uPreOffset = uAddress / kMemPageSize % kMemNumPagesPerUnit;

The size information obtained from the allocation header allows the number of pages used to track the allocation to also be calculated.

      u32 uNumPagesUsed = uSize / kMemPageSize + ((uSize % kMemPageSize)? 1 : 0);

3. Release the pages back into the memory heap.

Clearing pages for each tracking unit follows the same basic pattern, a bitmask of the pages used is built, then bitwise inverted and logically AND’ed to the tracking unit, with results stored back into the same tracking unit.

If the entire allocation is contained within one tracking unit, then it is cleared and the function returns.

      // Check if the used pages are contained within one tracking unit.
 
        if(uNumPagesUsed < (kMemNumPagesPerUnit - uPreOffset))
 
        {
 
              // The entire allocation is contained in the one Tracking Unit, build a bit mask and clear the pages all at once.
 
              aMemPageTrackingBits[uBeginningTrackingUnit] &=  ~((kMemTrackingUnitAllPagesInUse << (kMemNumPagesPerUnit - uNumPagesUsed)) >> uPreOffset);
 
              return;
 
        }

Otherwise, the free operation is broken down into three parts:

  1. Free the partially used tracking unit for the beginning of the allocation.
  2. Free any whole tracking units used for the allocation.
  3. Free a partially used tracking unit, if used, for the end of the allocation.
      // All pages from the PreOffset to the end of the first Tracking Unit are used, clear them.
 
        aMemPageTrackingBits[uBeginningTrackingUnit] &= ~(kMemTrackingUnitAllPagesInUse >> uPreOffset);
 
   
 
        // Determine how many pages are left to clear.
 
        uNumPagesUsed -= (kMemNumPagesPerUnit - uPreOffset);
 
   
 
        // Clear whole tracking units.
 
        u32 uNextUnitToClear = (uBeginningTrackingUnit + 1);
 
        for( ; uNextUnitToClear <= (uBeginningTrackingUnit + (uNumPagesUsed / kMemNumPagesPerUnit)); ++uNextUnitToClear)
 
        {
 
              aMemPageTrackingBits[uNextUnitToClear] &= ~kMemTrackingUnitAllPagesInUse;
 
        }
 
   
 
        // Determine how many pages are left to clear.
 
        uNumPagesUsed -= ((uNextUnitToClear - (uBeginningTrackingUnit + 1)) * kMemNumPagesPerUnit);
 
   
 
        // Terminate if done, also protects from going past the end of the aMemPageTrackingBits array.
 
        if(uNumPagesUsed == 0 || (uNextUnitToClear >= kMemNumTrackingUnits))
 
        {
 
              // If this assertion fails, then something is messed up with the tracking information,
 
              // because it was believed that pages were still in use that must exist past the array
 
              // of tracking bits.
 
              assert(uNumPagesUsed == 0);
 
              return;
 
        }
 
   
 
        // Clear the remaining pages.
 
        aMemPageTrackingBits[uNextUnitToClear] &= ~(kMemTrackingUnitAllPagesInUse << (kMemNumPagesPerUnit - uNumPagesUsed));

And that’s it, the free method is done.  Next time I’ll cover the simple high performance timer used for testing.