_GARBAGE COLLECTION FOR C PROGRAMS_
by Giuliano Carlini and Susan Rendina

[LISTING ONE]

/* Garbage Collector - Free memory blocks that aren't referenced. A garbage 
collector deduces which memory blocks are in use. When memory runs low, it 
reclaims those blocks which are no longer used. That memory can then be reused 
to satisfy further requests for memory. */

#ifndef GC_Defn
#define GC_Defn

void GcPickUp( void );
/* Reclaim blocks of unused memory from the segments being watched. */

#endif


[LISTING TWO]

/* GC - Garbage Collector */

#include "aseg.h"
#include "array.h"
#include "bool.h"
#include "gc.h"

#ifndef BitsPerByte
#define BitsPerByte 8
#endif

void GcMark(
    unsigned*   Block,
    unsigned    Length
) {
    unsigned    Bit;
    unsigned    Idx;
    unsigned*   Last;
    unsigned*   Next;
    unsigned    Value;
    Last = (unsigned*)((char*)Block + Length ) - 1;
    for ( Next = Block; Next <= Last; Next = (unsigned*)((char*)Next+1) ) {
        Value  = *Next;
        Length = ASegMarkValue(
            0,
            (unsigned*)Value
        );
        if ( Length != 0 ) {
            GcMark( (unsigned*)Value, Length );
        }
    }
}
void GcPickUp()
{
    extern unsigned end;
    AllocSeg    Seg;
    /* Algorithm: Clear the mark bits; mark blocks reachable from roots 
        (the stack and global data); Sweep all watched segments. */
    Seg = 0;
    ASegClearMarks(Seg);
    GcMark( 0, end );
    GcMark(
        (unsigned*)&Seg,
        (unsigned)&Seg - (unsigned)Seg->FirstFreeOfSize[0]
    );
    ASegSweep(Seg);
}


[LISTING THREE]

/* AllocSeg - Segments used for memory allocation. Allocation segments are 
80x86 segments used for memory allocation. Clients may request or return 
pointers to blocks of memory.  */
#ifndef ASeg_Defn
#define ASeg_Defn
#include "stdio.h"
typedef struct AllocSegTg*  AllocSeg;
void* ASegAllocBlock(
    AllocSeg    Seg,
    unsigned    Size
);
/* Returns block of <Length> bytes from <Seg>. Returns NULL if no block. */
void ASegDumpSeg(
    AllocSeg    Seg,
    FILE*       F
);
/* Write a debugging dump of <Seg> to <F>. */
void ASegInitSeg(
    AllocSeg    Seg
);
/* Initialize <Seg> for use. */
/* GARBAGE COLLECTOR INTERFACE: Only a garbage collector should use this. */
void ASegClearMarks(
    AllocSeg    Seg
); 
/* Clear all marks from <Seg>. */
unsigned ASegMarkValue(
    AllocSeg    Seg,
    void*       Value
);
/* If <Value> corresponds to a block allocated from <Seg> mark it as being in 
use. Return the size of the block (not the actual size, but the size requested 
by creator). Returns 0 if Value isn't valid, or if block was already marked. */
void ASegSweep(
    AllocSeg    Seg
);
/* Sweep all unmarked blocks in <Seg> into <Seg's> free lists. */
/* INTERNALS: An Allocation Segment is an 80x86 segment. The programs global 
data and its stack are at the start. The middle is used for client memory
requests. It's tail is used for bookkeeping. A client may request a block of 
any size. Internally however, all blocks lengths are a power of two between 8 
bytes and 32K bytes. Block lengths are represented by their Log base 2, which 
is the number of 0 bits to the right of the 1 bit in the length.  */
typedef unsigned            UnsignedLog2;
   /* UnsignedLog2 - An unsigned power of 2 represented by it's Log base 2. */
#define BitsPerByte     8
#define SegSize         0x10000L  /* 64K byte segments */
#define UnitSize        8    /* Allocations are in units of 8 bytes */
#define UnitMask        0xFFF8
#define UnitsPerSeg     (SegSize/UnitSize) /* Nbr of Units/segment */
#define FlagsPerUnit        2 /* 2 flags for each unit */
    #define UnitAlloc   1  /* Unit is the start of an alloc'd block */
    #define UnitMark    2  /* Mark bit for garbage collection */
#define FlagBytesPerSeg     (UnitsPerSeg * FlagsPerUnit / BitsPerByte)
#define ASegOverhead FlagBytesPerSeg
#define UnitsPerFlagByte ( BitsPerByte / FlagsPerUnit )
#define BFUnused     (FlagBytesPerSeg / UnitSize * FlagsPerUnit / BitsPerByte)
  /* Flag bytes are at tail of the segment; will never be allocated. Flags that
  represent flag bytes are needed. Calculate how much of the tail isn't needed
  for flag bytes. UnitsInFlagBytes = FlagBytesPerSeg/UnitSize = 512; 
  BFUnused = UnitsInFlagBytes * FlagsPerUnit/BitsPerByte */
typedef unsigned    BlockFlags[ (ASegOverhead - BFUnused) / sizeof(int) ];
#define NbrOfBlockSizes 15
   /* Number of block lengths supported. */
#define ASegPadSize  ( BFUnused - NbrOfBlockSizes * sizeof(FreePtr) - 2 )
   /* Number of bytes to pad segment structure to 2 bytes less than 64K. */
typedef struct FreeBlockTg* FreePtr;
    /* Pointer to a free block */
/* Representation of an AllocSeg */
typedef struct AllocSegTg {
    int         Well[ (SegSize - ASegOverhead) / sizeof(int) ];
    BlockFlags  Flags;
                #define ASegFlagIdx(S, P) ( (unsigned)P / ( UnitSize * 
                           BitsPerByte * sizeof(S->Flags[0]) / FlagsPerUnit ) )
        #define ASegFlagAddr(S, P) ((unsigned*)&S->
                                                    Flags[ ASegFlagIdx(S, P) ])
        #define ASegFlagShift(S, P) ( ( (unsigned)P / UnitSize ) % 
                     ( UnitsPerFlagByte * sizeof(S->Flags[0]) ) * FlagsPerUnit)
        #define ASegFlagAllocBits 0x5555
        #define ASegFlagMarkBits 0xAAAA
        #define ASegAllocClr(S, P) \
           *ASegFlagAddr(S, P) &= ~( UnitAlloc << ASegFlagShift(S, P) )
        #define ASegAllocSet(S, P) \
           *ASegFlagAddr(S, P) |=  ( UnitAlloc << ASegFlagShift(S, P) )
        #define ASegIsAllocSet(S, P) \
         ( *ASegFlagAddr(S, P) & ( UnitAlloc << ASegFlagShift(S, P) ) )
        #define ASegMarkClr(S, P) \
            *ASegFlagAddr(S, P) &= ~( UnitMark << ASegFlagShift(S, P) )
        #define ASegMarkSet(S, P) \
            *ASegFlagAddr(S, P) |=  ( UnitMark << ASegFlagShift(S, P) )
        #define ASegIsMarkSet(S, P) \
          ( *ASegFlagAddr(S, P) & ( UnitMark << ASegFlagShift(S, P) ) )
    FreePtr     FirstFreeOfSize[ NbrOfBlockSizes ];
    char        Pad[ ASegPadSize - 1 ];
};
/* FirstFreeOfSize[0] is not used. */
/* Representation of an allocated block */
typedef struct BlockTg* BlockPtr;
typedef struct BlockTg {
    UnsignedLog2    Size;   /* The actual size */
    unsigned        Used;   /* The size requested */
} AllocBlock;
/* Note: Block returned by ASegAllocBlock must have struct BlockTg. */
/* Representation of a free block */
typedef struct FreeBlockTg {
    UnsignedLog2        Size;
    FreePtr             Next;
};
#endif


[LISTING FOUR]

/* AllocSeg -- Allocation Segment -- ALGORITHM & DATA STRUCTURES: This is a 
buddy system allocator; see KNUTH, Vol 1, pg 442. */

unsigned Junk;

#include "array.h"
#include "aseg.h"
#include "bool.h"
#include "power2.h"
#include "stdio.h"

#ifndef NULL
#define NULL 0
#endif

#define NULL_OFS 0xFFFF
void* ASegAllocBlock(
    AllocSeg        Seg,
    unsigned        Size
) {
    BlockPtr        Block;
    UnsignedLog2    BlockSize;
    FreePtr         Buddy;
    FreePtr         Free;
    UnsignedLog2    FreeSize;
    unsigned long*  ZeroPtr;
    Size += 4;
        /* Add in the space for the block header */
    /* Set BlockSize to the first power of 2 equal or larger to Size */
    if ( Size < 256 ) {
        BlockSize = Log2[ BumpUp[Size] ];
    } else {
        BlockSize = (Size + 255) >> 8;
        BlockSize = Log2[ BumpUp[BlockSize] ] + 8;
    }
    /* Set Free to the first free block of length >= Size */
    /* If there is no such block return NULL */
    Free = NULL;
    FreeSize = BlockSize;
    while (True) {
        if (NbrOfBlockSizes < FreeSize) {
            return NULL;
        }
        Free = Seg->FirstFreeOfSize[FreeSize];
        if (Free != NULL) break;
        FreeSize++;
    }
    Block = (BlockPtr)Free;
         /* Returned block will be split from Free. */
     /* Unlink Free from its list */
    Seg->FirstFreeOfSize[FreeSize] = Free->Next;
    /* Split Free until it is of the requested size. */
    while (FreeSize != BlockSize) {
        FreeSize--;
        Buddy = (FreePtr)( (char*)Free + (1 << FreeSize) );
        Buddy->Size = FreeSize;
        Buddy->Next = Seg->FirstFreeOfSize[FreeSize];
        Seg->FirstFreeOfSize[FreeSize] = Buddy;
    }
    Free->Size = BlockSize;
    ASegAllocSet(Seg, Block);
    Block->Used = Size - 4; /* Subtract off header length that we added */
    /* Zero out memory before returning it */
    for (
        ZeroPtr = (unsigned long*)(Block + 1);
        ZeroPtr < (unsigned long*)( (char*)Block + (1 << BlockSize) );
        ZeroPtr++
    ) {
        *ZeroPtr = 0L;
    }
    return Block + 1;
}
void ASegVegamatic(
    AllocSeg        Seg,
    FreePtr         First,
    FreePtr         End 
) {
    FreePtr         Free;
    unsigned        FreeSize;
    unsigned        Size;
    UnsignedLog2    SizeLog2;
    for (
        Free = First;
        Free < End;
        Free = (FreePtr)( (char*)Free + Size )
    ) {
   /* Calculate size for block. */
        FreeSize = (char*)End - (char*)Free;
        Size = MaxPwr2Div((unsigned)Free);
        if ( (unsigned)Free & 0xFF ) {
            SizeLog2 = Log2[Size];
        } else {
            SizeLog2 = Log2[Size>>8];
            SizeLog2 += 8;
        }
        while ( FreeSize < Size ) {
            Size >>= 1;
            SizeLog2--;
        }
        Free->Size = SizeLog2;
        /* Link Free into the free list for blocks of Size */
        Free->Next = Seg->FirstFreeOfSize[SizeLog2];
        Seg->FirstFreeOfSize[SizeLog2] = Free;
    }
}
void ASegInitSeg(
    AllocSeg        Seg
) {
    extern unsigned _atopsp;    /* Start of heap and stack */
    UnsignedLog2    BlockSize;  /* The size of Free */
    FreePtr         Free;   /* A free block */
    unsigned        Idx;
    /* Notes: atopsp is set by C startup to start of stack. The stack 
        grows down from there, and the heap (that's us) up. */
    _atopsp = (_atopsp + UnitSize - 1) & UnitMask;
    Seg->FirstFreeOfSize[0] = (FreePtr)_atopsp;
    for (Idx = 1; Idx < ArrayLength(Seg->FirstFreeOfSize); Idx++) {
        Seg->FirstFreeOfSize[Idx] = 0;
    }
    for (Idx = 0; Idx < ArrayLength(Seg->Flags); Idx++) {
        Seg->Flags[Idx] = 0;
    }
    ASegVegamatic( Seg, (FreePtr)_atopsp, (FreePtr)(Seg->Flags) );
}
/* GARBAGE COLLECTING OPERATIONS */
void ASegClearMarks(
    AllocSeg    Seg
) {
    int         Pos;
   /* Notes: This is faster than traversing chain of blocks in segment, and 
   then computing the bit to clear. This executes loop about 2K times; block-
   by-block could take 8K times. */
    for (Pos = 0; Pos <= ArrayLast(Seg->Flags); Pos++) {
        Seg->Flags[Pos] &= ~ASegFlagMarkBits;
    }
}
unsigned ASegMarkValue(
    AllocSeg    Seg,
    void*       Value
) {
    unsigned*   FlagPtr;
    unsigned    Shift;
    unsigned*   SizePtr;
    if ( (FreePtr)Value < Seg->FirstFreeOfSize[0] ) return 0;
      /* Value represents an address in the global data or stack, and 
          couldn't have been returned by the allocator. */
    if ( (unsigned)Value % UnitSize != 4 ) return 0;
      /* Allocator always returns address 4 bytes after unit which starts
          block. If value doesn't start 4 bytes after a Unit, it can't have 
          been returned from allocator. */
    FlagPtr = ASegFlagAddr(Seg, Value);
    Shift   = ASegFlagShift(Seg, Value);
    if (
         (
            ( (*FlagPtr) >> Shift ) & (UnitAlloc|UnitMark)
         ) != UnitAlloc
    ) {
        /* Unit is Unallocated or already marked */
        return 0;
    }
    *FlagPtr |= UnitMark << Shift;
    /* HACK: Assumption that requested size is 1 word before the value. */
    SizePtr = (unsigned*)Value - 1;
}
    return *SizePtr;
}
void ASegSweep(
    AllocSeg        Seg
) {
    FreePtr         End;
    FreePtr         First;
    UnsignedLog2    SizeLog2;
    FreePtr         WellWall;
    WellWall = (FreePtr)&Seg->Well[ ArrayLength(Seg->Well) ];
    /* Zap the free list headers */
    for ( SizeLog2 = 1; SizeLog2 <= NbrOfBlockSizes; SizeLog2++) {
        Seg->FirstFreeOfSize[ SizeLog2 ] = NULL;
    }
    First = (FreePtr)Seg->FirstFreeOfSize[0];
    while ( True ) {
        /* Find the start of a free region */
        while (
            First < WellWall
          /* end the loop when we get past the segments memory well */
            && ASegIsMarkSet(Seg, First)
                /* or when we find an unreferenced block */
        ) {
            SizeLog2 = First->Size;
            First = (FreePtr)( (char*)First + ( 1 << SizeLog2 ) );
        }
        if ( WellWall <= First ) break;
           /* end the loop when we get past the segments memory well */
        ASegAllocClr(Seg, First);
           /* First is unreferenced, but may be allocated.  It's about
           to be swept into the free list, so clear it's alloc flag. */
        /* Find the end of the free region */
        SizeLog2 = First->Size;
        End = (FreePtr)( (char*)First + ( 1 << SizeLog2 ) );
        while (
            End < WellWall
           /* end the loop when we get past the segments memory well */
            && ! ASegIsMarkSet(Seg, End)
                /* or when we find a referenced block */
        ) {
            ASegAllocClr(Seg, End);
                /* About to be swept up.  Clear alloc flag */
            SizeLog2 = End->Size;
            End = (FreePtr)( (char*)End + ( 1 << SizeLog2 ) );
        }
        ASegVegamatic( Seg, First, End );
           /* Split free region into free blocks and put into free lists */
        First = End;
        /* Set First to End rather than block following End. */
    }
}


[LISTING FIVE]

/* Alloc -- A garbage collecting memory allocator. */
#include "stdio.h"

#include "array.h"
#include "aseg.h"
#include "alloc.h"
#include "gc.h"

void free(
    void*    Ptr
) {
    return;
}
void* malloc(
    unsigned    Length
) {
    void*   Result;
    Result = ASegAllocBlock( 0, Length );
    if ( Result == NULL ) {
        GcPickUp();
        Result = ASegAllocBlock( 0, Length );
    }
    return Result;
}