---

ToyMemHeap.c

/***************************************************************************
                          ToyMemHeap.c  -  Heap allocation code for the
    toy memory manager
                             -------------------
    begin                : Mon Feb 3 2003
    copyright            : (C) 2003 by Tyler Montbriand
    student #            : 200200370
    class                : CS330
    email                : monttyle@heavyspace.ca
***************************************************************************/

#include <malloc.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#include "ToySegment.h"
#include "ToySegmentList.h"
#include "ToyProcess.h"
#include "ToyMemType.h"
#include "ToyMem.h"
#include "ToyMem_Internal.h"
#include "ToyLoad.h"
#include "ToyVirtualMem.h"

#define MIN_SIZE 1

#define WRAP_LEN strlen("-> [140 9] -> [149 0 (1)] -> [154 2] -> [156 9] -> ")

/*  Glue functions */

/* Inserts a space hole into the process' free list */
SegList *TMM_InsertSpaceHole(Process *proc, SegList *hole);
/*  Lie ptr=ptr->next, except rewinds to head when it hits the end  */
SegList *TMM_CircularNext(Process *proc);
/*  Deletes a space hole from the list, ensuring proc->ptr is still valid */
SegList *TMM_DeleteSpaceHole(Process *proc, SegList *hole);
/*  Attempts to find a block of 'size' length in the process' free list */
SegList *TMM_FindInFreeList(ToyMM *tmm, Process *proc, int size);
/*  Attempts to find a segment beginning at 'address' in the list */
SegList *TMM_FindAddressInList(SegList *list, int address);
/*  Merges segment with segment below, ensuring proc->ptr is still valid  */
void TMM_MergeAt(Process *proc, SegList *list);
/*  Prints a properly formatted and linewrapped list of segments  */
int PrintSegList(SegList *list, const char *title, char *prefix);
int PrintFreeHeap(Process *proc);
int TMM_FindProcess(ToyMM *tmm, Process *proc);
int TMM_MinSize(int size);
SegList *TMM_EnlargeHeap(ToyMM *tmm, int process, int size);



ErrMessage_t TMM_StoreHeapString(ToyMM *tm, int process, int addr, const char *str)
{
  SegList *list=NULL;
  Process *proc=NULL;
  int raddr=-1;
  if(tm==NULL)  return(ERR_UNKNOWN);
  if((process<0)||(process>=MAX_PROCESSES)) return(ERR_UNKNOWN);

  /*  Get our process */
  proc=tm->processList[process];
  if(proc==NULL)  return(ERR_NOPROCESS);

  list=proc->usedheap;

  while(list!=NULL)
  {
    if((list->seg.pos<=addr)&&(list->seg.pos+list->seg.len>addr))
    {
      raddr=TMM_GetRealAddress(tm,process,addr);
      if(raddr<0)
      {
        printf("wtf!?\n");
        return(ERR_UNKNOWN);
      }
      
      tm->mem[raddr].type=DATA_STRING;
      strcpy(tm->mem[raddr].string.value,str);
      return(ERR_NONE);
    }
    list=list->next;
  }

  return(ERR_INVALIDADDRESS);
}

ErrMessage_t TMM_StoreHeapInteger(ToyMM *tm, int process, int addr, int value)
{
  SegList *list=NULL;
  Process *proc=NULL;
  int raddr=-1;
  if(tm==NULL)  return(ERR_UNKNOWN);
  if((process<0)||(process>=MAX_PROCESSES)) return(ERR_UNKNOWN);

  /*  Get our process */
  proc=tm->processList[process];
  if(proc==NULL)  return(ERR_NOPROCESS);

  list=proc->usedheap;

  while(list!=NULL)
  {
    if((list->seg.pos<=addr)&&(list->seg.pos+list->seg.len>addr))
    {
      raddr=TMM_GetRealAddress(tm,process,addr);
      if(raddr<0)
      {
        printf("wtf!?\n");
        return(ERR_UNKNOWN);
      }
      
      tm->mem[raddr].type=DATA_INTEGER;
      tm->mem[raddr].integer.value=value;
      return(ERR_NONE);
    }
    list=list->next;
  }

  return(ERR_INVALIDADDRESS);
}

ErrMessage_t TMM_AllocateHeap(ToyMM *tm, int process, int size)
{
  SegList *memblock=NULL;
  SegList *newblock=NULL;
  Process *proc=NULL;

  if(tm==NULL)  return(ERR_UNKNOWN);
  if((process<0)||(process>=MAX_PROCESSES)) return(ERR_UNKNOWN);

  /*  Get our process */
  proc=tm->processList[process];
  if(proc==NULL)  return(ERR_NOPROCESS);

  /*  Find an appropriate memory block in free list  */
  memblock=TMM_FindInFreeList(tm,proc,size);
  /*  Couldn't find one?  We're out of memory  */
  if(memblock==NULL)  return(ERR_HEAPFULL);

  /*  Create new node to represent this */
  newblock=TMM_CreateSegList(memblock->seg.pos,size,NULL,NULL);
  /*  Insert it into the used heap list */
  proc->usedheap=TMM_OrderedInsert(proc->usedheap,newblock);

  if(size==0) size=1;

  /*  Two cases.  If the sizes are exactly the same,
      we have to delete the block.  But if they're not,
      we can just shrink and move the free block.       */
  if(memblock->seg.len==size)
  {
    /*  Delete the space hole entirely.  */
    TMM_DeleteSpaceHole(proc,memblock);
  }
  else
  {
    /*  Move the block down 'size' units, and shrink it
        'size' units - effectively chopping a portion
        off the top.                                    */
    memblock->seg.pos+=size;
    memblock->seg.len-=size;
  }

  /* Force the occupied page to get swapped in */
  TMM_GetRealAddress(tm,process,newblock->seg.pos);

  return(ERR_NONE);
}


ErrMessage_t TMM_FreeHeap(ToyMM *tm, int process, int addr)
{
  SegList *memblock;
  Process *proc;

  if(tm==NULL)  return(ERR_UNKNOWN);
  if((process<0)||(process>=MAX_PROCESSES)) return(ERR_UNKNOWN);

  /*  Get our process */
  proc=tm->processList[process];
  if(proc==NULL)  return(ERR_NOPROCESS);

  /*  Find pointer in used list */
  memblock=TMM_FindAddressInList(proc->usedheap,addr);
  /*  Didn't find it? */
  if(memblock==NULL)  return(ERR_BADFREEHEAPADDRESS);

  /*  If it's the head of the list, proceed to next
      If there IS no next, the list will become NULL,
      meaning empty.                                  */
  if(memblock==proc->usedheap)
  {
    proc->usedheap=proc->usedheap->next;
  }

  /*  Remove it from used list.  Not deallocating it,
      just unlinking it.                              */
  TMM_RemoveFromList(memblock);

  /* Segments of 0 size still take up 1 size */
  memblock->seg.len=TMM_MinSize(memblock->seg.len);

  /* Mark now-empty space as empty */
  TMM_MarkMemEmpty(tm,memblock->seg.pos,memblock->seg.len);

  /*  Add to list of free space */
  TMM_InsertSpaceHole(proc,memblock);

  /*  Combine segments together if any  */
  TMM_MergeAt(proc,memblock);
  TMM_MergeAt(proc,memblock->prev);

  return(ERR_NONE);
}

ErrMessage_t TMM_ReallocateHeap(ToyMM *tm, int process, int addr, int size)
{
  SegList *memblock=NULL;
  SegList *freeblock=NULL;

  Process *proc;
  int pos=0;
  int dsize=0;  /* change in size */

  if(tm==NULL)  return(ERR_UNKNOWN);
  if((process<0)||(process>=MAX_PROCESSES)) return(ERR_UNKNOWN);

  /*  Get our process */
  proc=tm->processList[process];
  if(proc==NULL)  return(ERR_NOPROCESS);

  /*  Find the allocated block associated with this address */
  memblock=TMM_FindAddressInList(proc->usedheap,addr);
  /*  Didn't find it, return error  */
  if(memblock==NULL)  return(ERR_BADREALLOCADDRESS);

  /*  Calculate the change in size - larger is positive,
      smaller is negative                                 */
  dsize=size-TMM_MinSize(memblock->seg.len);

  /* Calculate current last address of segment to be reallocated */
  pos=memblock->seg.pos+TMM_MinSize(memblock->seg.len);

  freeblock=TMM_FindAddressInList(proc->freeheap,pos);
  if(dsize==0)    /*  Same size - no problem  */
  {
    return(ERR_NONE);
  }
  else if(dsize>0)  /*  memory grows  */
  {
    if(freeblock!=NULL)  /*  memory available below? */
    if(freeblock->seg.len>=dsize)
    {
      /*  Yet again the obnoxious 0 size is 1 size problem. */
      memblock->seg.len=TMM_MinSize(memblock->seg.len);
      memblock->seg.len+=dsize;
      freeblock->seg.pos+=dsize;
      freeblock->seg.len-=dsize;
      if(memblock->seg.len==0)
      {
        TMM_DeleteSpaceHole(proc,freeblock);
      }
      return(ERR_NONE);
    }
    /*  Space NOT available below - search elsewhere */
    {
      SegList *newmem;
      /*  Find free space */
      freeblock=TMM_FindInFreeList(tm,proc,size);
      /*  Didn't find space - out of memory. */
      if(freeblock==NULL)  return(ERR_HEAPFULL);

      /*  Create new node for used list */
      newmem=TMM_CreateSegList(freeblock->seg.pos,size,NULL,NULL);

      /*  Copy memory into new seg  */
      TMM_CopyMem(tm,newmem->seg.pos,memblock->seg.pos,memblock->seg.len);
      TMM_MarkMemEmpty(tm,memblock->seg.pos,memblock->seg.len);

      /*  Move and resize memory hole  */
      freeblock->seg.pos+=size;
      freeblock->seg.len-=size;
      /*  If the hole is empty, delete it */
      if(freeblock->seg.len==0)
      {
        TMM_DeleteSpaceHole(proc,freeblock);
      }

      /*  Add new memory to used list */
      proc->usedheap=TMM_OrderedInsert(proc->usedheap,newmem);

      /* Remove old memory from used list */
      TMM_RemoveFromList(memblock);
      /*  Add memory hole to free list  */
      proc->freeheap=TMM_OrderedInsert(proc->freeheap,memblock);
      /*  Merge space holes */

      TMM_MergeAt(proc,memblock);
      TMM_MergeAt(proc,memblock->prev);

      return(ERR_NONE);
    }

  }
  else  /*  dsize < 0: shrink */
  {
    SegList *newhole=NULL;

    dsize=-dsize; /*  make non-negative for more obvious calculations */

    /* Should not happen unless a negative gets entered
        somehow.  But just in case...                   */
    if(memblock->seg.len<dsize)
    {
      return(ERR_UNKNOWN);
    }
    else if(memblock->seg.len==dsize)  /*  collapse to 0 size  */
    {
      /*  Create hole ONE smaller than 'zero'-size block, and one below */
      newhole=TMM_CreateSegList(memblock->seg.pos+1,memblock->seg.len-1,NULL,NULL);
      /*  Set seg size to zero  */
      memblock->seg.len=0;
    }
    else
    {
      /*  Create new memory hole  */
      newhole=TMM_CreateSegList(memblock->seg.pos+memblock->seg.len-dsize,
                                dsize,NULL,NULL);
      /*  Shrink the segment  */

      memblock->seg.len-=dsize;
    }
    /*  Insert new hole into free list  */
    proc->freeheap=TMM_OrderedInsert(proc->freeheap,newhole);
    /*  Merge end-to-end segments */
    TMM_MergeAt(proc,newhole);
    TMM_MergeAt(proc,newhole->prev);
    return(ERR_NONE);
  }
}

ErrMessage_t TMM_PrintHeap(ToyMM *tm, int process)
{
  char str[]="*\0\0";
  int totalsize=0;
  int freesize=0;
  int usedsize=0;

  float freepercent;

  if((process<0)||(process>=MAX_PROCESSES)) return(ERR_UNKNOWN);
  if(tm->processList[process]==NULL)        return(ERR_NOPROCESS);

  printf(LINE_RULE);
  printf(LINE_PREFIX"Heap for Process P%01d:\n",process);

  totalsize+=PrintFreeHeap(tm->processList[process]);
  str[0]='\0';
  usedsize+=PrintSegList(tm->processList[process]->usedheap,"Used",str);
  totalsize+=usedsize;

  freesize=totalsize-usedsize;

  if(totalsize!=0)
  {
    freepercent=(freesize*100.0f)/totalsize;
  }
  else
  {
    freepercent=0.0f;
  }

  printf(LINE_PREFIX" Free: %d / %d = %.0f%%\n",freesize,totalsize,freepercent);

  printf(LINE_RULE);

  return(ERR_NONE);
}

int PrintFreeHeap(Process *proc)
{
  SegList *list=NULL;
  char starstr[]="*\0\0";  
  int size=0;
  unsigned int charprinted=0;
  
  if(proc==NULL)  return(0);
  
  list=proc->freeheap;
  
  printf(LINE_PREFIX" Free");

  while(list!=NULL)
  {
    if(charprinted>=WRAP_LEN)
    {
      printf("\n"LINE_PREFIX"     ");
      charprinted=0;
    }

    if(list==proc->ptr) starstr[0]='*';
    else                starstr[0]='\0';
        
    charprinted+=printf(" -> %s[%d %d]",starstr,list->seg.pos,list->seg.len);
    starstr[0]='\0';
    size+=list->seg.len;
    list=list->next;    
  }

  if(charprinted>=WRAP_LEN)
  {
    printf("\n"LINE_PREFIX);
    charprinted=0;
  }
  printf(" -> %s[]\n",starstr);
  return(size);
}

int PrintSegList(SegList *list, const char *title, char *prefix)
{
  int size=0;
  int charprinted=0;
  char startStr[20];

  strcpy(startStr,prefix);
  printf(LINE_PREFIX" %4s",title);

  while(list!=NULL)
  {
    /*  Handle linewrapping - if we've printed this much, go to a new line. */
    if(charprinted>=WRAP_LEN)
    {
      charprinted=0;
      printf("\n"LINE_PREFIX"     ");
    }

    size+=list->seg.len;
    if(list->seg.len==0)  size++;
                                           /*  Print the next seg, keeping track of how much we've printed */
    if(list->seg.len==0)
    {
      charprinted+=printf(" -> %s[%d 0 (1)]",startStr,list->seg.pos);
    }
    else
    {
      charprinted+=printf(" -> %s[%d %d]",startStr,list->seg.pos,list->seg.len);
    }

    /*  Forward to the next segment */
    list=list->next;

    /* Turn the "*" into a "" */
    startStr[0]='\0';

  } while(list!=NULL);

  /*  Handle linewrapping - if we've printed this much, go to a new line. */
  if(charprinted>=WRAP_LEN)
  {
    charprinted=0;
    printf("\n"LINE_PREFIX"     ");
  }
  printf(" -> %s[]\n",startStr);

  return(size);
}

/******************************************************************************
  Glue functions
 ******************************************************************************/

SegList *TMM_InsertSpaceHole(Process *proc, SegList *hole)
{
  if(proc==NULL)  return(NULL);
  if(hole==NULL)  return(proc->freeheap);

  proc->freeheap=TMM_OrderedInsert(proc->freeheap,hole);
  if(proc->ptr==NULL) proc->ptr=proc->freeheap;

  return(proc->freeheap);
}

SegList *TMM_CircularNext(Process *proc)
{
  if(proc==NULL)            return(NULL);
  if(proc->freeheap==NULL)  return(NULL);

  if(proc->ptr==NULL)
  {
    proc->ptr=proc->freeheap;
    return(proc->ptr);
  }

  /*  Advance the pointer */
  proc->ptr=proc->ptr->next;
  /*  If we've reached the end, loop to the beginning */
  if(proc->ptr==NULL) proc->ptr=proc->freeheap;
  return(proc->ptr);
}

SegList *TMM_DeleteSpaceHole(Process *proc, SegList *hole)
{
  /*  Special case - this hole is the ONLY hole in the list.
      Need to set heap and ptr to NULL to denote empty.     */
  int size=TMM_SegListSize(proc->freeheap);
  if(size==0)
  {
    return(NULL);
  }
  else if(size==1)
  {
    if(hole!=proc->freeheap)
    {
      /*  Should NOT happen */
      printf("wtf?\n");
      abort();
    }

    proc->ptr=NULL;
    proc->freeheap=NULL;
    free(hole);
    return(NULL);
  }
  else
  {
    /*  If we're pointing to the hole, have to seek to the next */    
    if(proc->ptr==hole) TMM_CircularNext(proc);

    /*  If it's the head, better move the head ptr */
    if(proc->freeheap==hole)
    {
      proc->freeheap=proc->freeheap->next;
    }

    TMM_RemoveFromList(hole);
    free(hole);
    return(proc->freeheap);
  }
}

SegList *TMM_FindInFreeList(ToyMM *tmm,Process *proc, int size)
{
  SegList *list=proc->ptr;
  SegList *startpoint=list;

  /*  Set to minimum size */
  size=TMM_MinSize(size);

  /* Search through free list for suitable seg */  
  if(list!=NULL)
  {
    do
    {
      if(list->seg.len>=size) return(list);

      list=TMM_CircularNext(proc);
    }while(list!=startpoint);
  }

  /* Can't add pages to heap segment in legacy mode. */
  if(TMM_PagingEnabled(tmm)<0)
  {
    return(NULL);
  }
  else
  { /* Attempt to enlarge the heap */
    return(TMM_EnlargeHeap(tmm,TMM_FindProcess(tmm,proc),size));
  }
}

SegList *TMM_FindAddressInList(SegList *node, int address)
{
  while(node!=NULL) /*  Loop through every node in used list  */
  {
    /*  If the address matches, we've found it. */
    if(node->seg.pos==address) return(node);
    node=node->next;
  }

  /*  Didn't find it. */
  return(NULL);
}

void TMM_MergeAt(Process *proc, SegList *list)
{
  if(list==NULL)              return;
  else if (list->next==NULL)  return;  
  
  if(SegEnd(&(list->seg))==list->next->seg.pos)
  {
    if(list->next==proc->ptr)
    {
      proc->ptr=list;
    }

    list->seg.len+=list->next->seg.len;
    TMM_DeleteSpaceHole(proc,list->next);
  }
}


int TMM_FindProcess(ToyMM *tmm, Process *proc)
{
  int n;
  if(tmm==NULL) return(-1);

  for(n=0; n<MAX_PROCESSES; n++)
  {
    if(tmm->processList[n]==proc) return(n);
  }

  return(-1);
}

int TMM_MinSize(int size)
{
  if(size<MIN_SIZE) return(MIN_SIZE);
  else              return(size);
}

/* Enlarges the heap until 'pages' continuous pages exist in the free list.  Returns the hole or NULL. */
SegList *TMM_EnlargeHeap(ToyMM *tmm, int process, int size)
{
  SegList *lasthole=NULL;
  SegList *lastsegpos=NULL;
  int vaddr=-1;
  Process *proc=tmm->processList[process];

  lasthole=TMM_SeekSegListEnd(proc->freeheap);
  lastsegpos=TMM_GetSegmentNode(tmm, process, SEG_HEAP);

  vaddr=(lastsegpos->seg.pos+lastsegpos->seg.len);

  if(lastsegpos==NULL)
  {
    return(NULL);
  }

  if(lasthole==NULL)  /* Totally empty free list */
  {
    int frame=-1;
    int page=-1;
    int pages=TMM_GetNumFrames(tmm,size);
/*    printf("Allocating memory in totally empty free list\n"); */

    /* Not enough available pages, return error */
    if(pages>TMM_CountFreePages(tmm,process)) return(NULL);

    /* Create new space hole */
    lasthole=TMM_CreateSegList(vaddr,0,NULL,NULL);
    proc->freeheap=TMM_AppendSegList(proc->freeheap,lasthole);

    page=vaddr/tmm->pageSize;

    /* Find free frames */
    while(pages>0)
    {
      frame=TMM_FindFreeFrame(tmm);
      if(frame<0) break;
      
      /* Assign found frame to process */
      TMM_AssignFrame(tmm,process,frame,page);

      /* Increase the virtual address(page) */
      page++;
      /* Decrease # of needed pages */
      pages--;

      /* Increase segment sizes */
      lastsegpos->seg.len+=tmm->pageSize;
      lasthole->seg.len+=tmm->pageSize;
    }

    if(pages>0)
    {
      printf("Page allocation error\n");
      abort();
    }    

    proc->ptr=lasthole;
    return(lasthole);
  }
  else if(lasthole->seg.pos+lasthole->seg.len==lastsegpos->seg.pos+lastsegpos->seg.len)
  {
    int frame=-1;
    int page=-1;
    int pages=TMM_GetNumFrames(tmm,size-lasthole->seg.len);


    /* Not enough available pages, return error */
    if(TMM_CountFreePages(tmm,process)<pages) return(NULL);    


    page=vaddr/tmm->pageSize;

    /* Find free frames */
    while(pages>0)
    {
      frame=TMM_FindFreeFrame(tmm);
      if(frame<0) break;
      
      /* Assign found frame to process */
      TMM_AssignFrame(tmm,process,frame,page);

      /* Increase the virtual address(page) */
      page++;
      /* Decrease # of needed pages */
      pages--;

      /* Increase segment sizes */
      lastsegpos->seg.len+=tmm->pageSize;
      lasthole->seg.len+=tmm->pageSize;
    }

    if(pages>0)
    {
      printf("Page allocation error\n");
      abort();
    }

    proc->ptr=lasthole;
    return(lasthole);
  }
  else
  {
    int frame=-1;
    int page=-1;
    int pages=TMM_GetNumFrames(tmm,size);

    /* Not enough available pages, return error */
    if(TMM_CountFreePages(tmm,process)<pages) return(NULL);

    /* Create new space hole */
    lasthole=TMM_CreateSegList(vaddr,0,NULL,NULL);

    proc->freeheap=TMM_AppendSegList(proc->freeheap,lasthole);

    page=vaddr/tmm->pageSize;

    /* Find free frames */
    while(pages>0)
    {
      frame=TMM_FindFreeFrame(tmm);
      if(frame==-1)      
      {
        printf("Page allocation error -Email me at monttyle@heavyspace.ca and tell me how you did this.\n");
        abort();
      }
      /* Assign found frame to process */
      TMM_AssignFrame(tmm,process,frame,page);

      /* Increase the virtual address(page) */
      page++;
      /* Decrease # of needed pages */
      pages--;

      /* Increase segment sizes */
      lastsegpos->seg.len+=tmm->pageSize;
      lasthole->seg.len+=tmm->pageSize;
    }

    proc->ptr=lasthole;
    return(lasthole);
  }
}

---