Chapter 3
Memory Management

The following declarations span the entire module. There is the CPU page size, the public basic elements kBlock and kPointer, and also the private structure kBlockStruct. Please note that thread safety has not been tested yet.

#ifdef kCPUIntel
#define kCPUPageSize 4096
#endif

typedef kNatural kBlock;

typedef kByte* kPointer;

typedef struct SBlockStruct
{
  kPointer sReserved1;
  kFlags sFlags;
  kSize sSize;
  kNatural sRefs;
  kNatural sReserved2;
  kBlock sBlock;
  struct SBlockStruct* sPrev;
  struct SBlockStruct* sNext;
} kBlockStruct;

See below for flags. The size of a memory block is always a multiple of 16 and is aligned too. sRefs is used for manual reference counting. The block number comes next, folowed by the links to previous and following blocks in the heap.

Segments

The items in this section are private. There are two segments per application: the heap and the pile. The heap is your normal heap segment. It is composed as a sequence of kBlockStruct, each followed by user data of size sSize (aligned to 16 bytes). At first there are just two structs, one that spans almost all of the entire heap and that reecords the initial free space in the heap, followed by a dummy struct of block sSize equal to zero used to signal the end of the heap. The structs point to their previous and next siblings. The pile is just an array of master pointers, or handles, each pointing to a kBlockStruct. The pile grows as needed to accomodate more handles.

kPointer kSegmentPile;
kNatural kSegmentPileMax;
kNatural kSegmentPileNextFree;

kPointer kSegmentHeap;

kByte kSegmentHeapLockFlag;

kSegmentSetSize sets or resets the size of a segment. If aNewSize is not zero, it preserves the previous contents of a segment, by truncation or padding the remaining space with zeros.

kVoid kSegmentSetSize(kPointer *aSegment, kSize aOldSize, kSize aNewSize)
{
  if(aNewSize == 0)
  {
    if(*aSegment)
    {
      #ifdef kOSWindows
      HeapFree(GetProcessHeap(), 0, *aSegment);
      #endif
      *aSegment = kNil;
    }
  }

  kSize i = 0;
  #ifdef kOSWindows
  kPointer vArray = (kPointer)HeapAlloc(GetProcessHeap(), 0, aNewSize);
  #endif
  kNatural vMinSize = kNaturalMin(aNewSize, aOldSize);

  if(*aSegment)
    for(; i < vMinSize; i++)
      vArray[i] = (*aSegment)[i];
  for(; i < aNewSize; i++)
    vArray[i] = 0;

  if(*aSegment)
    #ifdef kOSWindows
    HeapFree(GetProcessHeap(), 0, *aSegment);
    #endif

  *aSegment = vArray;
}

We need to initialize the pile. We also record its size, and the next free entry.

kVoid kSegmentPileInit(kVoid)
{
  kSegmentPileMax = kCPUPageSize / sizeof(kBlockStruct*);
  kSegmentPileNextFree = 1;
  kSegmentSetSize(&kSegmentPile, 0, kSegmentPileMax * sizeof(kBlockStruct*));
}

At the end of the program, we call the following function.

kVoid kSegmentPileDone(kVoid)
{
  kSegmentSetSize(&kSegmentPile, kSegmentPileMax * sizeof(kBlockStruct*), 0);
  kSegmentPileMax = 0;
  kSegmentPileNextFree = 0;
}

Whenever we need more master pointers, or handles, we call the following function. Note that the pile never shrinks.

kVoid kSegmentPileGrow(kVoid)
{
  kNatural vSegmentPileOldMax = kSegmentPileMax;

  kSegmentPileMax += kCPUPageSize / sizeof(kBlockStruct*);
  kSegmentSetSize(&kSegmentPile, vSegmentPileOldMax * sizeof(kBlockStruct*),
    kSegmentPileMax * sizeof(kBlockStruct*));
}

The following two functions retrieve the block in the heap or set a block in the heap given the master pointer, or block index, in the pile.

kBlockStruct* kSegmentPileGetBlockStruct(kNatural aIndex)
{
  if(aIndex < kSegmentPileMax)
    return ((kBlockStruct**)kSegmentPile)[aIndex];
  else
    return kNil;
}

kVoid kSegmentPileSetBlockStruct(kNatural aIndex, kBlockStruct* aBlockStruct)
{
  if(aIndex < kSegmentPileMax)
    ((kBlockStruct**)kSegmentPile)[aIndex] = aBlockStruct;
}

We maintain an index to the pile array, called kSegmentPileNextFree, to record the next available entry in it. The function that follows does part of the relevant housekeeping.

kNatural kSegmentPileGetNextFree(kVoid)
{
  if((kSegmentPileNextFree < kSegmentPileMax) && !kSegmentPileGetBlockStruct(kSegmentPileNextFree))
    return kSegmentPileNextFree++;
  else
  {
    while((kSegmentPileNextFree < kSegmentPileMax) && kSegmentPileGetBlockStruct(kSegmentPileNextFree))
      kSegmentPileNextFree++;
    if(kSegmentPileNextFree == kSegmentPileMax)
      kSegmentPileGrow();

    return kSegmentPileNextFree;
  }
}

Next come the heap functions, one to initialize it, at the start of the program, and one to finalize it, at the end of the program.

kVoid kSegmentHeapInit(kSize aSize)
{
  kBlockStruct* vBlock;

  kSegmentSetSize(&kSegmentHeap, 0, aSize);

  vBlock = (kBlockStruct*)kSegmentHeap; // First kBlockStruct
  vBlock->sCheck = kNil;
  vBlock->sFlags = 0;
  vBlock->sSize = aSize - 2 * sizeof(kBlockStruct);
  vBlock->sRefs = 0;
  vBlock->sLocker = 0;
  vBlock->sBlock = 0;
  vBlock->sPrev = kNil;
  vBlock->sNext = (kBlockStruct*)(kSegmentHeap + aSize - sizeof(kBlockStruct));

  vBlock = (kBlockStruct*)(kSegmentHeap + aSize - sizeof(kBlockStruct)); // Dummy Final kBlockStruct
  vBlock->sCheck = kNil;
  vBlock->sFlags = 0;
  vBlock->sSize = 0;
  vBlock->sRefs = 0;
  vBlock->sLocker = 0;
  vBlock->sBlock = 0;
  vBlock->sPrev = (kBlockStruct*)kSegmentHeap;
  vBlock->sNext = kNil;
}

kVoid kSegmentHeapDone(kVoid)
{
  kSegmentSetSize(&kSegmentHeap, 0, 0);
}

I need to think about the following function first :).

kVoid kSegmentHeapCompact(kVoid)
{
  // Later!
}

The next two functions are used in multithreaded programs, and have not yet been tested. They prevent racing situations when more that one thread is trying to access the heap.

kVoid kSegmentHeapLock(kVoid)
{
  volatile kByte vZeroFlag = 0;

  do
  {
    #ifdef kCPUIntel
    __asm__
    (
      "xor %%al, %%al;\
      mov $0x01, %%bl;\
      lock cmpxchg %%bl, %[kSegmentHeapLockFlag];\
      setz %[vZeroFlag];"
      : [vZeroFlag] "=mr" (vZeroFlag), [kSegmentHeapLockFlag] "=m" (kSegmentHeapLockFlag)
      : "m" (vZeroFlag), "r" (kSegmentHeapLockFlag)
      : "%al", "%bl"
    );
    #endif
  }
  while(vZeroFlag);
}

kVoid kSegmentHeapUnlock(kVoid)
{
  kSegmentHeapLockFlag = 0;
}

Blocks

These are the public bits of the memory management module. We start with the errors.

typedef enum
{
  kBlockErrorOk,
  kBlockErrorHeapFull,
  kBlockErrorLocked,
  kBlockErrorUnlocked,
  kBlockErrorBadArgument,
  kBlockErrorUnknown
} kBlockErrorKind;

There follows a couple of private flags, useful to say when a block is being used and when it is locked.

#define kBlockFlagIsInUse  1
#define kBlockFlagIsLocked 2

The following two functions are also private. The first splits a block in two, useful when we need a new used block of size aSize, followed by a free block. The second merges a newly free block with the following block if it's free too, and with the previous block if it also is free.

kVoid kBlockSplitStruct(kBlockStruct* aBlockStruct, kSize aSize)
{
  kBlockStruct* vBlockStruct;

  if(aBlockStruct->sSize > aSize + sizeof(kBlockStruct))
  {
    vBlockStruct = (kBlockStruct*)((kPointer)aBlockStruct + sizeof(kBlockStruct) + aSize);
    vBlockStruct->sFlags = 0;
    vBlockStruct->sSize = (aBlockStruct->sSize - aSize) - sizeof(kBlockStruct);
    vBlockStruct->sPrev = aBlockStruct;
    vBlockStruct->sNext = aBlockStruct->sNext;

    aBlockStruct->sSize = aSize;
    aBlockStruct->sNext = vBlockStruct;
  }
}

kVoid kBlockMergeStruct(kBlockStruct* aBlockStruct)
{
  kBlockStruct* vBlockStruct = aBlockStruct->sNext;

  if(vBlockStruct->sSize)
  {
    vBlockStruct->sNext->sPrev = aBlockStruct;

    aBlockStruct->sFlags = 0;
    aBlockStruct->sSize = aBlockStruct->sSize + vBlockStruct->sSize + sizeof(kBlockStruct);
    aBlockStruct->sNext = vBlockStruct->sNext;
  }
}

Next comes the kBlockInit function.

kBlock kBlockInit(kSize aSize)
{
  if(aSize == 0)
  {
    kError = kBlockErrorBadArgument;

    return 0;
  }

  if(aSize & 0xF)
    aSize = (aSize & ~0xF) + 0x10; // Align to 16 bytes

  kSegmentHeapLock();

  kBlock vBlock = kSegmentPileGetNextFree();
  kBlockStruct* vBlockStruct = (kBlockStruct*)kSegmentHeap;

  if(vBlockStruct == kNil)
  {
    kError = kBlockErrorUnknown;

    kSegmentHeapUnlock();

    return 0;
  }
  else
  {
label1111:
    while((vBlockStruct->sSize < aSize + sizeof(kBlockStruct)) && vBlockStruct->sSize)
      vBlockStruct = vBlockStruct->sNext;
    if(vBlockStruct->sFlags & kBlockFlagIsInUse)
    {
      vBlockStruct = vBlockStruct->sNext;
      goto label1111;
    }

    if(vBlockStruct->sSize == 0)
    {
      kSegmentHeapCompact();

      // retry once;
      // kError = ;

      kSegmentHeapUnlock();

      return 0;
    }
    else if(vBlockStruct->sSize > aSize + sizeof(kBlockStruct))
    {
      kBlockSplitStruct(vBlockStruct, aSize);
      vBlockStruct->sFlags = kBlockFlagIsInUse;
      vBlockStruct->sRefs = 1;
      vBlockStruct->sBlock = vBlock;
      kSegmentPileSetBlockStruct(vBlock, vBlockStruct);

      for(kSize i = 0; i < aSize; i++)
        *((kByte*)vBlockStruct + sizeof(kBlockStruct) + i) = 0;

      kError = kBlockErrorOk;

      kSegmentHeapUnlock();

      return vBlock;
    }
    else
    {
      kError = kBlockErrorHeapFull;

      kSegmentHeapUnlock();

      return 0;
    }
  }
}

And then there is the kBlockDone function.

kVoid kBlockDone(kBlock aBlock)
{
  kBlockStruct *vCurrBlockStruct, *vPrevBlockStruct, *vNextBlockStruct;

  kSegmentHeapLock();

  vCurrBlockStruct = kSegmentPileGetBlockStruct(aBlock);

  if(vCurrBlockStruct)
  {
    vPrevBlockStruct = vCurrBlockStruct->sPrev;
    vNextBlockStruct = vCurrBlockStruct->sNext;

    vCurrBlockStruct->sFlags = 0;

    if(vNextBlockStruct->sSize && ((vNextBlockStruct->sFlags & kBlockFlagIsInUse) == 0))
      kBlockMergeStruct(vCurrBlockStruct);
    if(vPrevBlockStruct && ((vPrevBlockStruct->sFlags & kBlockFlagIsInUse) == 0))
      kBlockMergeStruct(vPrevBlockStruct);

    kSegmentPileSetBlockStruct(aBlock, kNil);

    if(aBlock < kSegmentPileNextFree)
      kSegmentPileNextFree = aBlock;

    kError = kBlockErrorOk;
  }
  else
    kError = kBlockErrorUnknown;

  kSegmentHeapUnlock();
}

Whenever we need to access the contents of a block, through the use of a pointer, we first must lock it, and then unlock it when we are through with it. The two functions that follow allow us to do that.

kPointer kBlockLock(kBlock aBlock)
{
  kSegmentHeapLock();

  kBlockStruct* vBlockStruct = kSegmentPileGetBlockStruct(aBlock);

  if(!vBlockStruct)
  {
    kError = kBlockErrorUnknown;

    kSegmentHeapUnlock();

    return kNil;
  }

  if((vBlockStruct->sFlags & kBlockFlagIsLocked) == 0)
  {
    vBlockStruct->sFlags |= kBlockFlagIsLocked;
    kError = kBlockErrorOk;

    kSegmentHeapUnlock();

    return (kPointer)vBlockStruct + sizeof(kBlockStruct);
  }
  else
  {
    kError = kBlockErrorLocked;

    kSegmentHeapUnlock();

    return kNil;
  }
}

kBlock kBlockUnlock(kPointer aPointer)
{
  kSegmentHeapLock();

  kBlockStruct* vBlockStruct = (kBlockStruct*)(aPointer - sizeof(kBlockStruct));

  if(vBlockStruct->sFlags & kBlockFlagIsLocked)
  {
    vBlockStruct->sFlags &= ~kBlockFlagIsLocked;
    kError = kBlockErrorOk;

    kSegmentHeapUnlock();

    return vBlockStruct->sBlock;
  }
  else
  {
    kError = kBlockErrorUnlocked;

    kSegmentHeapUnlock();

    return 0;
  }
}

The following function returns the size of a block.

kSize kBlockGetSize(kBlock aBlock)
{
  kSegmentHeapLock();

  kBlockStruct* vBlockStruct = kSegmentPileGetBlockStruct(aBlock);

  if(vBlockStruct)
  {
    kError = kBlockErrorOk;

    kSegmentHeapUnlock();

    return vBlockStruct->sSize;
  }
  else
  {
    kError = kBlockErrorUnknown;

    kSegmentHeapUnlock();

    return 0;
  }
}

Finally, come three functions that deal with reference counting.

kNatural kBlockGetRefs(kBlock aBlock)
{
  kSegmentHeapLock();

  kBlockStruct* vBlockStruct = kSegmentPileGetBlockStruct(aBlock);

  if(vBlockStruct)
  {
    kError = kBlockErrorOk;

    kSegmentHeapUnlock();

    return vBlockStruct->sRefs;
  }
  else
  {
    kError = kBlockErrorUnknown;

    kSegmentHeapUnlock();

    return 0;
  }
}

kVoid kBlockDecRefs(kBlock aBlock)
{
  kSegmentHeapLock();

  kBlockStruct* vBlockStruct = kSegmentPileGetBlockStruct(aBlock);

  if(vBlockStruct)
  {
    kError = kBlockErrorOk;
    vBlockStruct->sRefs--;

    if(!vBlockStruct->sRefs)
      kBlockDone(aBlock);
  }
  else
    kError = kBlockErrorUnknown;

  kSegmentHeapUnlock();
}

kVoid kBlockIncRefs(kBlock aBlock)
{
  kSegmentHeapLock();

  kBlockStruct* vBlockStruct = kSegmentPileGetBlockStruct(aBlock);

  if(vBlockStruct)
  {
    kError = kBlockErrorOk;
    vBlockStruct->sRefs++;
  }
  else
    kError = kBlockErrorUnknown;

  kSegmentHeapUnlock();
}

Pointers

If we don't need blocks, but wish to work directly with pointers, the following functions allow us to do so. They are similar to the ones that work with blocks. Please note that if we only work with pointers, the heap cannot be compacted, so it's best if we use memory through block functions.

kPointer kPointerInit(kSize aSize)
{
  return kBlockLock(kBlockInit(aSize));
}

kVoid kPointerDone(kPointer aPointer)
{
  kBlockDone(kBlockUnlock(aPointer));
}

kSize kPointerGetSize(kPointer aPointer)
{
  return ((kBlockStruct*)(aPointer - sizeof(kBlockStruct)))->sSize;
}

kNatural kPointerGetRefs(kPointer aPointer)
{
  return ((kBlockStruct*)(aPointer - sizeof(kBlockStruct)))->sRefs;
}

kVoid kPointerDecRefs(kPointer aPointer)
{
  ((kBlockStruct*)(aPointer - sizeof(kBlockStruct)))->sRefs--;
}

kVoid kPointerIncRefs(kPointer aPointer)
{
  ((kBlockStruct*)(aPointer - sizeof(kBlockStruct)))->sRefs++;
}

Copyright © 2025 Rui Cuco. All rights reserved.