OSDev.org

void *a = palloc(64kB);
void *b = palloc(4kB);
free(a);
void *c = palloc(4kB);
a = palloc(64kB);

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#define MAXSTACKITEMS ((4096-2-4-4)/4)
struct sStack{
   uintptr_t    addr[MAXSTACKITEMS];
   uint16_t   index;
   struct sStack   *next, *prev;
};
struct sGroup{
   uint32_t   freeCount;
   struct sStack *free;
   struct sStack *used;
};
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#define REDZONE_CLUSTERCOUNT 5
#define YELLOWZONE_CLUSTERCOUNT 10
#define GREENZONE_CLUSTERCOUNT 20
#define MAXPAGECLUSTERSIZE 7
static struct sGroup group[MAXPAGECLUSTERSIZE];
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/// The functions (private and public).
static void fill(uint8_t groupIndex);
static void push(uint8_t groupIndex, uintptr_t address);
static uintptr_t pop(uint8_t groupIndex);
void *valloc(uint32_t pageCount);
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/// Brings a group that is below the GREENZONE in cluster count into the GREENZONE.
static void fill(uint8_t groupIndex)
{
   uint32_t needed;
   /// take a cluster from a higher level and fill this level with it.
   if((groupIndex+1) > MAXPAGECLUSTERSIZE){
      /// we are out of memory?
      PROBLEM;
      for(;;);
   }
   if(group[groupIndex].freeCount > GREENZONE_CLUSTERCOUNT){
      // ignore it?
      return;
   }
   for(needed = (GREENZONE_CLUSTERCOUNT - group[groupIndex].freeCount) / 2; needed > 0; --needed){
                /// this is the splitting for the lower half of the cluster.
      push(groupIndex, pop(groupIndex+1));
                /// this is the splitting for the upper half of the cluster.
                push(groupIndex, pop(groupIndex+1) + (groupIndex * 4096));
   }
   return;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/// Pushes a cluster specified at 'address' into the group specified by 'groupIndex'.
static void push(uint8_t groupIndex, uintptr_t address)
{
   struct sStack *nstack;
   if(group[groupIndex].free->index == MAXSTACKITEMS){
      // create a new array for the list.
      nstack = (struct sStack*)pop(1);
      nstack->prev = group[groupIndex].free;
      group[groupIndex].free->next = nstack;
      nstack->next = 0;
      nstack->index = 0;
      group[groupIndex].free = nstack;
   }
   ++group[groupIndex].freeCount;
   group[groupIndex].free->addr[(group[groupIndex].free->index)++] = address;
   return;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/// Pops a cluster from the group specified with 'groupIndex'.
static uintptr_t pop(uint8_t groupIndex)
{
   struct sStack *tmp;
   if(group[groupIndex].free->index == 0){
      tmp = group[groupIndex].free;
      group[groupIndex].free = group[groupIndex].free->prev;
      group[groupIndex].free->next = 0;
      push(1, (uintptr_t)tmp);
      if(group[groupIndex].freeCount < REDZONE_MINCLUSTERCOUNT){
         /// schedule a replenishment or immediately replenish.
         fill(groupIndex);
      }
      // if(grou[groupIndex].freeCount < YELLOWZONE_MINCLUSTERCOUNT){
                // .... something here.. maybe a scheduler and not right now.
   }
   --group[groupIndex].freeCount;
   return group[pageCount].free->addr[--(group[groupIndex].free->index)];
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/// Almost a plain shadow of pop(). Missing error handling and such other things.
void *valloc(uint32_t pageCount)
{
   return (void*)pop(pageCount);
}