10_speicherverwaltung

linked_list_management.c

#include "linked_list_management.h"


void add_page_to_pool_free_list(mem_pool *pool, mem_page *new_page) {
  mem_page *current_page = pool->free_pages;
  if (current_page == NULL) {
    pool->free_pages = new_page;
    return;
  }

  while(current_page->next != NULL) {
    current_page = current_page->next;
  }

  current_page->next = new_page;
  new_page->previous = current_page;
}

void add_page_to_pool_full_list(mem_pool *pool, mem_page *page) {
  page->previous = NULL;
  if ((page->next = pool->full_pages) != NULL) {
    page->next->previous = page;
  }

  pool->full_pages = page;
}

void remove_page_from_pool_free_list(mem_pool *pool, mem_page *page) {
  if ((pool->free_pages = page->next) != NULL) {
    pool->free_pages->previous = NULL;
  }

  page->previous = NULL;
}

/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

void remove_chunk_from_bin_free_list(mem_bin *bin, mem_chunk *chunk) { 
  if ((bin->free = chunk->next) != NULL) {
    bin->free->previous = NULL;
  }

  chunk->previous = NULL;
}

void add_chunk_to_bin_used_list(mem_bin *bin, mem_chunk *chunk) {
  if ((chunk->next = bin->in_use) != NULL) {
    chunk->next->previous = chunk;
  }

  bin->in_use = chunk;
}

void add_chunk_to_bin_free_list(mem_bin *bin, mem_chunk *chunk) {
  chunk->previous = NULL;
  if ((chunk->next = bin->free) != NULL) {
    chunk->next->previous = chunk;
  }
  bin->free = chunk;
}

void remove_chunk_from_bin_in_use_list(mem_bin *bin, mem_chunk *chunk) {
  if (chunk->next != NULL) {
    chunk->next->previous = chunk->previous;
  }
  if (chunk->previous != NULL) {
    chunk->previous->next = chunk->next;
  } else {
    bin->in_use = chunk->next;
  }
}

linked_list_management.h

#ifndef LINKED_LIST_MANAGEMENT_H
#define LINKED_LIST_MANAGEMENT_H

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "my_alloc.h"

void remove_page_from_pool_free_list(mem_pool *pool, mem_page *page);
void add_page_to_pool_free_list(mem_pool *pool, mem_page *page);
void add_page_to_pool_full_list(mem_pool *pool, mem_page *page);

void remove_chunk_from_bin_free_list(mem_bin *bin, mem_chunk *chunk);
void remove_chunk_from_bin_in_use_list(mem_bin *bin, mem_chunk *chunk);
void add_chunk_to_bin_used_list(mem_bin *bin, mem_chunk *chunk);
void add_chunk_to_bin_free_list(mem_bin *bin, mem_chunk *chunk);

#endif

my_alloc.c

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "my_alloc.h"
#include "my_system.h"
#include "linked_list_management.h"


mem_page *alloc_new_page_from_system() {
  mem_page *page = (mem_page *)get_block_from_system();
  assert(page != NULL);

  memset(page, 0, BLOCKSIZE);
  page->total_size = BLOCKSIZE - sizeof(struct _mem_page);
  page->free_size = page->total_size;

  return page;
}

mem_page *pull_page_from_pool_or_system(size_t alloc_size) {
  for(mem_page *current_page = pool.free_pages; current_page != NULL; current_page = current_page->next) {
    if (current_page->free_size >= alloc_size)
      return current_page;
  }

  // else
  mem_page *new_page = alloc_new_page_from_system();
  add_page_to_pool_free_list(&pool, new_page);

  return new_page;
}

void relocate_page_in_pool_lists_if_necessary(mem_page *page) {
  assert(page != NULL);

  if (page->free_size >= 8) 
    return;

  remove_page_from_pool_free_list(&pool, page);
  add_page_to_pool_full_list(&pool, page);
}

mem_chunk *alloc_new_chunk_from_page(mem_bin *bin) {
  assert(bin != NULL);

  size_t alloc_size = bin->alloc_size  + sizeof(struct _mem_chunk);
  
  mem_page *page = pull_page_from_pool_or_system(alloc_size);
  assert(page != NULL);

  mem_chunk *chunk = (mem_chunk *)(page->suffix + (page->total_size - page->free_size));
  memset(chunk, 0, alloc_size);
 
  page->free_size -= alloc_size;
 
  relocate_page_in_pool_lists_if_necessary(page);

  return chunk;
}

void init_mem_bin(mem_bin *bin, int alloc_size, const char *name) {
  assert(bin != NULL);

  memset(bin, 0, sizeof(mem_bin));

  bin->alloc_size = alloc_size;
  bin->name = strdup(name);
}

void init_my_alloc() {
  pool.free_pages = alloc_new_page_from_system();

  init_mem_bin(&pool.bins.b8,     8, "bin008");
  init_mem_bin(&pool.bins.b16,   16, "bin016");
  init_mem_bin(&pool.bins.b32,   32, "bin032");
  init_mem_bin(&pool.bins.b48,   48, "bin048");
  init_mem_bin(&pool.bins.b64,   64, "bin064");
  init_mem_bin(&pool.bins.b80,   80, "bin080");
  init_mem_bin(&pool.bins.b96,   96, "bin096");
  init_mem_bin(&pool.bins.b112, 112, "bin112");  
  init_mem_bin(&pool.bins.b128, 128, "bin128");
  init_mem_bin(&pool.bins.b144, 144, "bin144");
  init_mem_bin(&pool.bins.b160, 160, "bin160");
  init_mem_bin(&pool.bins.b176, 176, "bin176");
  init_mem_bin(&pool.bins.b192, 192, "bin192");
  init_mem_bin(&pool.bins.b208, 208, "bin208");
  init_mem_bin(&pool.bins.b224, 224, "bin224");
  init_mem_bin(&pool.bins.b240, 240, "bin240");
  init_mem_bin(&pool.bins.b256, 256, "bin256");
}

mem_chunk *pull_free_chunk_from_bin(mem_bin *bin, size_t req_size) {
  mem_chunk *chunk = bin->free;
   
  remove_chunk_from_bin_free_list(bin, chunk);
  add_chunk_to_bin_used_list(bin, chunk);

  chunk->size = req_size;
  chunk->flags |= CHUNK_FLAG_INUSE;

  return chunk;
}

mem_chunk *pull_new_chunk_from_current_page(mem_bin *bin, size_t req_size) {
  assert(bin != NULL);
  mem_chunk *chunk = alloc_new_chunk_from_page(bin);

  if (chunk == NULL)
    return NULL;
    
  chunk->bin = bin;
  chunk->flags |= CHUNK_FLAG_INUSE;
  chunk->alloc_size = bin->alloc_size;
  chunk->size = req_size;

  chunk->suffix[0] = 0;
  chunk->suffix[1] = 0;
  chunk->suffix[2] = 0;
  chunk->suffix[3] = 0;
    
  chunk->previous = NULL;
  add_chunk_to_bin_used_list(bin, chunk);

  return chunk;
}

mem_chunk *pull_free_chunk(mem_bin *bin, size_t req_size) {
#ifdef BIN_STATS
  bin->stats.pitches++;
#endif
  mem_chunk *chunk = NULL;

  if (bin->free != NULL) {
    chunk = pull_free_chunk_from_bin(bin, req_size);
  } else {
#ifdef BIN_STATS
    bin->stats.strikes++;
#endif
    chunk = pull_new_chunk_from_current_page(bin, req_size);    
  }

  return chunk;
}

void *my_alloc (int size) {
  mem_chunk *chunk;

  if (size <= 8) {
    chunk = pull_free_chunk(&pool.bins.b8, size);
  } else if (size <=  16) {
    chunk = pull_free_chunk(&pool.bins.b16, size);
  } else if (size <=  32) {
    chunk = pull_free_chunk(&pool.bins.b32, size);
  } else if (size <=  48) {
    chunk = pull_free_chunk(&pool.bins.b48, size);
  } else if (size <=  64) {
    chunk = pull_free_chunk(&pool.bins.b64, size);
  } else if (size <=  80) {
    chunk = pull_free_chunk(&pool.bins.b80, size);
  } else if (size <=  96) {
    chunk = pull_free_chunk(&pool.bins.b96, size);
  } else if (size <= 112) {
    chunk = pull_free_chunk(&pool.bins.b112, size);
  } else if (size <= 128) {
    chunk = pull_free_chunk(&pool.bins.b128, size);
  } else if (size <= 144) {
    chunk = pull_free_chunk(&pool.bins.b144, size);
  } else if (size <= 160) {
    chunk = pull_free_chunk(&pool.bins.b160, size);
  } else if (size <= 176) {
    chunk = pull_free_chunk(&pool.bins.b176, size);
  } else if (size <= 192) {
    chunk = pull_free_chunk(&pool.bins.b192, size);
  } else if (size <= 208) {
    chunk = pull_free_chunk(&pool.bins.b208, size);
  } else if (size <= 224) {
    chunk = pull_free_chunk(&pool.bins.b224, size);
  } else if (size <= 240) {
    chunk = pull_free_chunk(&pool.bins.b240, size);
  } else if (size <= 256) {
    chunk = pull_free_chunk(&pool.bins.b256, size);
  } 

  if (chunk != NULL)
    return chunk->suffix; // return actual payload of chunk

  return NULL;
}

void push_free_chunk(mem_bin *bin, mem_chunk *chunk) {
  chunk->flags &= ~CHUNK_FLAG_INUSE;
  
  remove_chunk_from_bin_in_use_list(bin, chunk);
  add_chunk_to_bin_free_list(bin, chunk);
}

void my_free (void * ptr) {
  if (ptr == NULL)
    return;

  mem_chunk *chunk = (mem_chunk *)((unsigned char *)ptr - SUFFIX_OFFSET);
  if (! (chunk->flags & CHUNK_FLAG_INUSE)) {
    fprintf(stderr, "**Warning** trying to free an unused memory chunk\n");
    return;
  }

  push_free_chunk(chunk->bin, chunk);
}

void print_bin_stat(mem_bin *bin) {
  assert(bin != NULL);

  printf("\t%6s: Pitches %5ld, Strikes %5ld, Ratio %3.2f\n", 
      bin->name, 
      bin->stats.pitches, bin->stats.strikes,
      (double)bin->stats.strikes / (double)bin->stats.pitches); 
}

void print_page_stat(mem_page *page) {
  assert(page != NULL);

  printf("\tTotal Size: %5ld, Free Size: %5ld, Fill Ratio: %3.2f\n",
      page->total_size, page->free_size,
      (double)(page->total_size - page->free_size) / (double)page->total_size);
}

void print_pool_stats() {
  
  printf("\n##################################################\n\n");
  /*
  printf("Total Requested Size: %5ld, Total Allocated Size: %5ld\n",
        pool.req_total_size, pool.alloc_total_size);
  */
  /*
  printf("Bins: \n");
  print_bin_stat(&pool.bins.b8);
  print_bin_stat(&pool.bins.b16);
  print_bin_stat(&pool.bins.b32);
  print_bin_stat(&pool.bins.b48);
  print_bin_stat(&pool.bins.b64);
  print_bin_stat(&pool.bins.b80);
  print_bin_stat(&pool.bins.b96);
  print_bin_stat(&pool.bins.b112);  
  print_bin_stat(&pool.bins.b128);
  print_bin_stat(&pool.bins.b144);
  print_bin_stat(&pool.bins.b160);
  print_bin_stat(&pool.bins.b176);
  print_bin_stat(&pool.bins.b192);
  print_bin_stat(&pool.bins.b208);
  print_bin_stat(&pool.bins.b224);
  print_bin_stat(&pool.bins.b240);
  print_bin_stat(&pool.bins.b256);
  */

  printf("\nFree Pages: \n");
  for(mem_page *page = pool.free_pages; page != NULL; page = page->next)
    print_page_stat(page);
  
  printf("\nFull Pages: \n");
  for(mem_page *page = pool.full_pages; page != NULL; page = page->next)
    print_page_stat(page);
}

my_alloc.h

#ifndef MY_ALLOC_H
#define MY_ALLOC_H

#if !defined(offsetof)
#define offsetof(s, m)             ((size_t)&(((s *)0)->m))
#endif

#define BIN_STATS

#define SUFFIX_OFFSET              offsetof(mem_chunk, suffix)

#define CHUNK_FLAG_INUSE           (1 << 3)

typedef struct _mem_chunk {
  struct _mem_chunk *next;         /* Next pooled entry */
  struct _mem_chunk *previous;     /* Previous pooled entry */

  struct _mem_bin *bin;            /* Owned by bin */

  unsigned long flags;             /* Pooled entry flags */
  unsigned long alloc_size;        /* Actually allocated size */
  unsigned long size;              /* Size requested by caller */

  unsigned char suffix[4];         /* Base pointer for allocations */
} mem_chunk;

typedef struct _mem_bin {
  struct _mem_chunk *free;        /* List available pooled entries */
  struct _mem_chunk *in_use;      /* Head of the pools in use list */

  size_t alloc_size;              /* Pool allocation size (0 for the extreme pool) */

  const char *name;               /* Name, for debug purpose */

#ifdef BIN_STATS
  struct {
    unsigned long pitches;        /* Requests to pull from the pool */
    unsigned long strikes;        /* Failed attempts to pull from the pool */
  } stats;
#endif

} mem_bin;

typedef struct _mem_page {
  struct _mem_page *next;         /* Next page entry */
  struct _mem_page *previous;     /* Previous page entry */

  size_t total_size;              /* Total usable size of page */
  size_t free_size;               /* Free size in page */

  unsigned char suffix[4];        /* Base pointer for allocations */
} mem_page;

typedef struct {

   struct {
        mem_bin b8;
        mem_bin b16;
        mem_bin b32;
        mem_bin b48;
        mem_bin b64;
        mem_bin b80;
        mem_bin b96;
        mem_bin b112;
        mem_bin b128;
        mem_bin b144;
        mem_bin b160;
        mem_bin b176; 
        mem_bin b192;
        mem_bin b208;
        mem_bin b224;
        mem_bin b240;
        mem_bin b256;
    } bins;

    struct _mem_page *full_pages;
    struct _mem_page *free_pages;

} mem_pool;

mem_pool pool;

/* This function is called exactly once before the first call to
 * my_alloc or my_free.
 */
void init_my_alloc ();

/* Return a pointer to size bytes of memory. Size will be a multiple of
 * 8 Bytes. The return value must be aligned to 8 bytes.
 */
void * my_alloc (int size);

/* This function is used to free a block of memory that was previously
 * allocated by my_alloc. ptr will always be a pointer that has been
 * returned by my_alloc.
 */
void my_free (void * ptr);


void print_pool_stats();

#endif // MY_ALLOC_H