mmanager_model.c

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

#include "mmanager.h"

int runModel(FILE *outputfp, FILE *inputfp, long totalMemorySize,
             int fitStrategy, int verbosity) {
  char *memoryBlock = NULL;
  int nSuccessfulActions = 0;
  mmgr_action action;

  fprintf(outputfp, "Running a %s-fit model in %ld (0x%lx) bytes of memory.\n",
          (fitStrategy == STRAT_FIRST   ? "first"
           : fitStrategy == STRAT_BEST  ? "best"
           : fitStrategy == STRAT_WORST ? "worst"
                                        : "unknown"),
          totalMemorySize, totalMemorySize);

  /**
   * this is the only allocation you should need -- all requests
   * from your model should come from this allocated block
   */
  memoryBlock = (char *)malloc(totalMemorySize);
  if (memoryBlock == NULL) {
    perror("allocation failed!");
    return -1;
  }

  /**
   *	+++ Set up anything else you will need for your memory management
   */
  // internal strucutre to track the memory chunks
  // this struct itself needs 24 bytes
  typedef struct Chunk {
    int id;             // id of the allocation chunk
    int size;           // size of the chunk
    int isFree;         // 1-> free, 0 -> allocated
    struct Chunk *next; // next chunk pointer
  } Chunk;
  // counting the number of allocations
  int numAlocations = 1;
  // track number of bytes allocated
  int allocated = 0;

  Chunk *head = (Chunk *)memoryBlock;
  // printf("%p", head);
  head->size = totalMemorySize - sizeof(Chunk);
  head->isFree = 1;
  head->next = NULL;

  while (getAction(&action, inputfp, outputfp, verbosity) > 0) {
    if (action.type == ACTION_ALLOCATE) {
      /* +++ do an allocation */
      Chunk *current = head;
      // iterate through the linked list to find suitable chunk
      while (current != NULL) {
        // for 1st starategy
        if (fitStrategy == STRAT_FIRST) {
          // is current chunk free and large enough for the request
          if (current->isFree && current->size >= action.size) {
            // allocate memory in the current chunk
            int requested = action.size;
            // calculating relative location
            int offset = (int)((char *)current - memoryBlock);

            // divide the chunk if there's enough space for another chunk
            if ((current->size - requested) >= sizeof(Chunk)) {
              // calcuting the address and size of the chunk that will be marked
              // as free
              Chunk *next =
                  (Chunk *)((char *)current + sizeof(Chunk) + requested);
              next->size = current->size - requested - sizeof(Chunk);
              next->isFree = 1;
              next->next = current->next;
              current->next = next;
              // increment the allocation tracker
              numAlocations++;
            }

            // update current chunk
            current->size = requested;
            current->isFree = 0;
            current->id = action.id;
            // track allocated memory
            allocated += action.size;
            // paint the memory with paint character
            memset((char *)current + sizeof(Chunk), action.paint, requested);

            // output message
            fprintf(outputfp, "alloc %d bytes : SUCCESS - return location %d\n",
                    requested, offset);
            break;
          }
        }
        // best strategy
        if (fitStrategy == STRAT_BEST) {
          // pointer to find the best fit chunk for request
          Chunk *ptr = head;
          Chunk *bestFit = NULL;
          int min = totalMemorySize;
          // traverse the linked list
          while (ptr != NULL) {
            // current chunk is free, large enough size and has less useless
            // space
            if (ptr->size - action.size < min && ptr->isFree &&
                ptr->size >= action.size) {
              // store current chunk into pointer
              min = ptr->size;
              bestFit = ptr;
            }
            ptr = ptr->next;
          }
          // allocate if a suitable chunk was found
          if (bestFit != NULL) {
            int requested = action.size;
            // calculate relative location
            int offset = (int)((char *)bestFit - memoryBlock);
            // need memory for the tracking strut as well so check if left over
            // space is enough
            if ((bestFit->size - requested) >= sizeof(Chunk)) {
              // calcuting the address and size of the chunk that will be marked
              // as free
              Chunk *next =
                  (Chunk *)((char *)bestFit + sizeof(Chunk) + requested);
              next->size = bestFit->size - requested - sizeof(Chunk);
              next->isFree = 1;
              next->next = bestFit->next;
              bestFit->next = next;
              // increment the allocation tracker
              numAlocations++;
            }
            // update the best fit chunk
            bestFit->size = requested;
            bestFit->isFree = 0;
            bestFit->id = action.id;
            // tracking the memory allocated
            allocated += action.size;
            // paint the memory with paint character
            memset((char *)bestFit + sizeof(Chunk), action.paint, requested);

            // output message
            fprintf(outputfp, "alloc %d bytes : SUCCESS - return location %d\n",
                    requested, offset);
          } else {
            fprintf(outputfp, "alloc %d bytes : FAIL\n", action.size);
          }
          break;
        }
        if (fitStrategy == STRAT_WORST) {
          Chunk *ptr = head;
          Chunk *worstFit = NULL;
          int max = 0;
          while (ptr != NULL) {
            if (ptr->size - action.size > max && ptr->isFree &&
                ptr->size >= action.size) {
              max = ptr->size;
              worstFit = ptr;
            }
            ptr = ptr->next;
          }
          if (worstFit != NULL) {
            int requested = action.size;
            // calculate relative location
            int offset = (int)((char *)worstFit - memoryBlock);

            // need memory for the tracking strut as well so check if left over
            // space is enough
            if ((worstFit->size - requested) >= sizeof(Chunk)) {
              // calcuting the address and size of the chunk that will be marked
              // as free
              Chunk *next =
                  (Chunk *)((char *)worstFit + sizeof(Chunk) + requested);
              next->size = worstFit->size - requested - sizeof(Chunk);
              next->isFree = 1;
              next->next = worstFit->next;
              worstFit->next = next;
              // increment the allocation tracker
              numAlocations++;
            }
            // update the best fit chunk
            worstFit->size = requested;
            worstFit->isFree = 0;
            worstFit->id = action.id;
            // tracking the memory allocated
            allocated += action.size;
            // paint the memory with paint character
            memset((char *)worstFit + sizeof(Chunk), action.paint, requested);

            // output message
            fprintf(outputfp, "alloc %d bytes : SUCCESS - return location %d\n",
                    requested, offset);
          } else {
            fprintf(outputfp, "alloc %d bytes : FAIL\n", action.size);
          }
          break;
        }
        current = current->next;
      }
      // no allocation done, error message printout
      if (current == NULL) {
        fprintf(outputfp, "alloc %d bytes : FAIL\n", action.size);
      }
    } else {
      /* +++ do a release */
      Chunk *current = head;
      // traverse the linked list, looking for id
      while (current != NULL) {
        if (action.id == current->id) {
          // mark it as free
          current->isFree = 1;
          allocated -= current->size;
          // output message with relative addressing
          fprintf(outputfp, "free location %ld\n",
                  (char *)current - (char *)memoryBlock);
          break;
        }
        current = current->next;
      }
      // merging adjacent free blocks
      Chunk *ptr = head;
      while (ptr != NULL && ptr->next != NULL) {
        if (ptr->isFree && ptr->next->isFree) {
          // merge the current and next chunks
          ptr->size += ptr->next->size + sizeof(Chunk);
          // skip the next chunk
          ptr->next = ptr->next->next;
          numAlocations--;
        } else {
          ptr = ptr->next;
        }
      }
    }

    /** increment our count of work we did */
    nSuccessfulActions++;
  }

  /** +++ Clean up your memory management */

  fprintf(outputfp, "SUMMARY:\n");
  fprintf(outputfp, "%d bytes allocated\n", allocated);
  fprintf(outputfp, "%ld bytes free\n", totalMemorySize - allocated);
  fprintf(outputfp, "%d allocation chunks:\n", numAlocations);
  Chunk *ptr = head;
  int i = 0;
  while (ptr != NULL) {
    fprintf(outputfp, "chunk %d location %ld:%d bytes - ", i,
            (char *)ptr - (char *)memoryBlock, ptr->size);
    if (ptr->isFree) {
      fprintf(outputfp, "free");
    } else {
      fprintf(outputfp, "allocated");
    }
    fprintf(outputfp, "\n");
    ptr = ptr->next;
    i++;
  }

  free(memoryBlock);

  return nSuccessfulActions;
}