gistfile1.c

/***************************************************************************
 *  Title: Kernel Memory Allocator
 * -------------------------------------------------------------------------
 *    Purpose: Kernel memory allocator based on the buddy algorithm
 *    Author: Stefan Birrer
 *    Version: $Revision: 1.2 $
 *    Last Modification: $Date: 2009/10/31 21:28:52 $
 *    File: $RCSfile: kma_bud.c,v $
 *    Copyright: 2004 Northwestern University
 ***************************************************************************/
/***************************************************************************
 *  ChangeLog:
 * -------------------------------------------------------------------------
 *    $Log: kma_bud.c,v $
 *    Revision 1.2  2009/10/31 21:28:52  jot836
 *    This is the current version of KMA project 3.
 *    It includes:
 *    - the most up-to-date handout (F'09)
 *    - updated skeleton including
 *        file-driven test harness,
 *        trace generator script,
 *        support for evaluating efficiency of algorithm (wasted memory),
 *        gnuplot support for plotting allocation and waste,
 *        set of traces for all students to use (including a makefile and README of the settings),
 *    - different version of the testsuite for use on the submission site, including:
 *        scoreboard Python scripts, which posts the top 5 scores on the course webpage
 *
 *    Revision 1.1  2005/10/24 16:07:09  sbirrer
 *    - skeleton
 *
 *    Revision 1.2  2004/11/05 15:45:56  sbirrer
 *    - added size as a parameter to kma_free
 *
 *    Revision 1.1  2004/11/03 23:04:03  sbirrer
 *    - initial version for the kernel memory allocator project
 *
 ***************************************************************************/
#ifdef KMA_BUD
#define __KMA_IMPL__

/************System include***********************************************/
#include <assert.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

/************Private include**********************************************/
#include "kpage.h"
#include "kma.h"

/************Defines and Typedefs*****************************************/
/*  #defines and typedefs should have their names in all caps.
 *  Global variables begin with g. Global constants with k. Local
 *  variables should be in all lower case. When initializing
 *  structures and arrays, line everything up in neat columns.
 */
 // used for finding the free list for a size
 #define LOG2(X) (int)ceil(log2(X))
 #define LOG2_FLOOR(X) (int)floor(log2(X))
 #define MAXPOWER 14
 #define BLOCKHEADERSIZE sizeof(int)
 #define ISBLOCKNULL(X) (X->size == 0 && X->data == 0)
 #define ISBLOCKLNULL(X) (X->in_use == 0 && X->size == 0)

 typedef struct {
  int size;
  char data[];
 } block;

 // A block will be typecasted to this when checking if it is free
 // The first int bytes will be set to 0 when it is freed. These bytes are
 // occupied by block->size so they shouldn't ever be 0 when it has been malloc'd
 // NOTE: size needs to be checked while traversing a free list in malloc
 // because when a block gets coalesced, it just gets added to a new freelist
 // but never removed from the old one for efficiency
 // It also contains the size which will be used for coalescing
 // NOTE: the size is not in the first member of the struct so we can use the
 // property stated for the in_use member
 // Next points to the next free block in the freelist
 typedef struct _block_l{
  int in_use;
  int size;
  struct _block_l *next;
 } block_l;

/************Global Variables*********************************************/
 block_l *base = NULL;

/************Function Prototypes******************************************/
 void init();
 void restore(kpage_t *page, int size);
 block_l *fl_for_size(int size);
 void coalesce(block_l *node);
 void create_block(int size);
 void trim_fl(block_l *head, int expected_size);
 block_l *allocate_page();
 void reassign_block_l(block_l *a, block_l *b);


/************External Declaration*****************************************/

/**************Implementation***********************************************/

void init()
{
  int fl_size = sizeof(block_l *) * MAXPOWER;
  block_l ***head_p;
  block_l *head;
  kpage_t *page = get_page();
  base = (block_l *)page->ptr;
  memset(base, 0, fl_size);

  // add the remainder of base page the free lists to a new block
  head = fl_for_size(page->size - fl_size);
  head_p = &head;
  **head_p = (block_l *)((char *)base + sizeof(block_l *) * (MAXPOWER + 1));
  // head = *head_p;
  head->in_use = 0;
  head->size = ceil(pow(2,LOG2(page->size - fl_size)));
  head->next = NULL;
}

void* kma_malloc(kma_size_t size)
{
  block_l *head;
  block *tmp_block;
  if(base == NULL)
    init();
  // the size field of the block struct
  size += sizeof(int);
  size = ceil(pow(2, LOG2(size)));
  // find the free list we should allocate from
  head = fl_for_size(size);
  if(ISBLOCKLNULL(head))
  {
    create_block(size);
    // creating a block should have made a block in the free list
    assert(!ISBLOCKLNULL(head));
  }
  // when we coalesce blocks, we don't actually remove the original blocks
  // from their original free lists for speed reasons. To get around this, we
  // remove any invalid blocks before trying to allocate a block in the list.
  // NOTE: this also only removes invalid free blocks from the front of the list
  // so after calling this, there may still be invalid blocks but the first block
  // is guaranteed to be valid or NULL.
  trim_fl(head, size);
  tmp_block = (block *)head;
  head = (block_l *)(head->next);
  return (void *)tmp_block->data;
}

void  kma_free(void* ptr, kma_size_t size)
{
  return;
}

block_l *fl_for_size(int size)
{
  assert(size > 0);
  int power = LOG2(size);
  assert(power <= MAXPOWER);
  return (block_l *)((char *)base + sizeof(block_l *) * (LOG2(size)));
}

void create_block(int target_size)
{
  int size = target_size;
  block_l *head = fl_for_size(size);
  block_l **head_p;
  block_l *new_block_l;
  block_l *old_block_l;
  int max_size = pow(2, MAXPOWER);
  // find the smallest free list with an available block
  while(size <= max_size / 2)
  {
    size *= 2;
    head = fl_for_size(size);
    if(!ISBLOCKLNULL(head))
    {
      // remove any invalid blocks
      trim_fl(head, size);
      break;
    }
  }
  // compensate for the last size *= 2

  // if we are at the max size, allocate a new page
  if(size == max_size && ISBLOCKLNULL(head))
    head = allocate_page();

  // go back down from our current size to the target block and split blocks
  while(size > target_size)
  {
    // make a new block_l in the middle
    old_block_l = fl_for_size(size);
    new_block_l = (block_l *)(old_block_l + head->size / 2);

    // divide the size by 2 and get the new free list
    size /= 2;
    head = fl_for_size(size);

    // reassign the sizes to the new smaller one
    new_block_l->size = size;
    new_block_l->in_use = 5;
    old_block_l->size = size;

    // insert both new block in the front of the new linked list
    new_block_l->next = head;
    old_block_l->next = new_block_l;
    head_p = &head;
    *head_p = old_block_l;
  }
}

/*void reassign_block_l(block_l *a, block_l *b)
{
  // add the remainder of base page the free lists to a new block
  block_l **a_p;
  a_p = &a;
  **a = b;
  a = *a_p;
}*/

block_l *allocate_page()
{
  kpage_t *starting_page = get_page();
  kpage_t *temp_page;
  block_l *new_block_l;
  int size = ceil(pow(2, MAXPOWER));
  int num_pages = size / starting_page->size;
  int i;

  // num_page - 1 because 1 page has already been allocated
  for(i = 0; i < num_pages - 1; i++)
    temp_page = get_page();
  // make sure the pages are contiguous
  assert(temp_page - starting_page == 1);
  new_block_l = (block_l *)starting_page->ptr;
  new_block_l->in_use = 0;
  new_block_l->size = starting_page->size * num_pages;
  return new_block_l;
}

// remove all nodes at the front of the free list that have been coalesced
// and are no longer actually in this free list
// A node is invalid if it's size no longer matches its free list
void trim_fl(block_l *head, int expected_size)
{
  // convert the size to the next power of 2
  expected_size = pow(2,LOG2(expected_size));
  while(!ISBLOCKLNULL(head) && head->size != expected_size)
    head = head->next;
}

void coalesce(block_l *current_node)
{
  block_l *buddy_node;
  block_l *new_node;
  block_l *old_node;
  block_l *head;

  buddy_node = (block_l *)((long)current_node ^ (long)current_node->size);

  if(!buddy_node->in_use && current_node->size == buddy_node->size)
  {
    if(buddy_node < current_node)
    {
      new_node = buddy_node;
      old_node = current_node;
    }
    else
    {
      new_node = current_node;
      old_node = buddy_node;
    }
    // invalidate the old block
    old_node->size = -1;
    new_node->size *= 2;
    // insert the new block into the new free list
    head = fl_for_size(new_node->size);
    new_node->next = head;
    head = new_node;
    coalesce(new_node);
  }
}

#endif // KMA_BUD