path: root/mm.c

/* Autor: Franciszek Malinka
 * Indeks: 316093
 * Oświadczam, że niniejszy kod jest dziełem mojego autorstwa. W swojej pracy
 * wzorowałem się na kodzie dostarczonym przez wykładowcę oraz przez kod
 * drzew rozchylanych autorstwa Daniela Sleatora.
 *
 * TL;DR: optimised boundary tags and splay tree of free blocks with eager
 * coalescing.
 *
 * --=[ APPROACH TO THE PROBLEM ]=--
 * 
 * This is the list of steps I did in order to implement this solution:
 * 1. Implemented implicit list of free and used blocks, made it work with
 *    simple first-fit policy.
 * 2. Implemented doubly linked list and many policies of inserting and 
 *    searching for the block.
 * 3. Debuged allocator functions, optimised realloc.
 * 4. Abstracted functions related to free block management.
 * 5. Now, when I had a working allocator code I could just implement the 
 *    interface for free block management with splay trees. It worked almost
 *    instantly after implementing. It made the code work 10 times faster.
 * 6. Further micro optimisations.
 * 
 * Along the way I've implement a lot of auxilary debug functions. I tried my
 * best to keep the code as clean as possible.
 * 
 * --=[ MANAGING USED AND FREE BLOCK ]=--
 *
 * Used blocks structure:
 * +-------------+
 * | Header      |
 * +-------------+
 * |             |
 * | Payload     |
 * .             .
 * .             .
 * |             |
 * +-------------+
 *
 * Free blocks structure:
 * +-------------+
 * | Header      |
 * +-------------+
 * | Ptr1        |
 * +-------------+
 * | Ptr2        |
 * +-------------+
 * |             |
 * | Free space  |
 * .             .
 * .             .
 * |             |
 * +-------------+
 * | Footer      |
 * +-------------+
 *
 * Header, ptr1, ptr2 and footer are all 4-bytes words (word_t). ptr1, ptr2
 * aren't acutal pointers -- they're offsets from the address of the free block
 * to some other free block (what are those blocks logicly depends ond the
 * data structure used).
 *
 * Header is a boundary tag consisting of the size of the block and possible 2
 * bits. Size is given in number of 4-byte words.
 * LSB of header indicates if block is used or free. The second least
 * significant bit indicates if phisically previous block is free
 * (prevfree bit). The prevfree bit should only be set in used blocks.
 * Footer is similar, but it has only size set (we don't need the bit nor
 * the prevfree bit set, so I didn't care about setting it in the
 * implementation).
 *
 * This implementation provides two data structures for managing free blocks:
 * - doubly linked list,
 * - splay tree.
 *
 * Both data structures implement a simple interface for the allocator:
 * - void init_data_structure(void *params) -- initialize data structure (DS).
 * - void insert_fb(free_block_t *block) -- insert free block to the DS.
 * - void erase_fb(free_block_t *block) -- erase block from the DS. It assumes
 *                                         the block is in the DS.
 * - free_block_t *find_fit(size_t reqsz) -- find a free block of size at least
 *                                           reqsz.
 *
 * Thanks to this abstraction the implementation of allocator functions are
 * (almost) independent from the implementation of the DS.
 *
 * To enable DS comment or uncomment defines LIST_IMP or SPLAY_IMP (only one
 * define should be enabled at a time). If you choose LIST_IMP then you can
 * also choose policies for inserting and searching the list.
 *
 * Both DS use sentiel block as a auxilary blocks. For list it serves as the end
 * and beggining of the list. For splay tree it serves as a NULL -- we remember
 * offsets other blocks, so we cannot store offset to 'true' NULL, that's why
 * we use the beggining of the heap.
 *
 * --=[ SPLAY TREES ]=--
 *
 * Here I discuss details behind the implementation of splay trees.
 *
 * Splay trees can store only nodes with distinct values. That's why we sort the
 * blocks not only by their size, but also by their addres. Nodes comparing is
 * done using the is_lesser and is_greater functions.
 *
 * The implementation is based on the Daniel Sleator's splay trees. What it lack
 * was the method for searching for the upperbound of some value. That's why
 * I implemented my own method. It simply searches the tree and stores the
 * lowest node that is greater or equal to the static mock block. We use the
 * mock block as a block that we can set the size to whatever we want, just for
 * sake of the upperbound functions. We also store the result of this function
 * in a static node pointer ub.
 *
 * --=[ ALLOCATOR FUNCTIONS ]=--
 *
 * There's three main functions for memory management: malloc, free and realloc.
 * Here's a detailed description of how those function work.
 *
 * If you look on the implementation of free and malloc then you'd recognize
 * that they're quite short. That is all is happening in those functions
 * is calculating of the size of word_t's that we want to actually allocate.
 * Functions that actualy do important stuff are allocate_block and free_block.
 * Those functions manage free block data structure.
 *
 * Realloc is more complicated due to optimisations:
 * - if there's a free block to the left of reallocated block and its size
 *   is sufficient to extend the block, then we do it,
 * - if the reallocated block is the last block, then we just get more heap
 *   and extend the block
 * - otherwise we run allocate_block and move the block.
 *
 * I call sbrk every time I need more memory and allocate exactly the amount
 * I need. I tried to allocate more memory, so we limit system calls, but
 * it turned out that when using the splay trees as DS number of instructions
 * drastically rose, so I left it as is.
 *
 * --=[ DEBUGGING ]=--
 *
 * I didn't implement mm_checkheap. It was more convinient for me to implement
 * separate functions for printing and checking integrity of the heap and data
 * structures. All those functions are run only if the DEBUG flags is defined,
 * otherwise their body is empty. I also used sanitzer. What I checked in those
 * debug functions:
 *
 * - Integrity of the heap, i.e. check if there are no adjacent free blocks,
 *   check if prevfree bits are set correctly, check if last block is actually
 *   the last block, check if last block ends with the heap.
 * - Integrity of the free block list, if the size in both boundary tags are
 *   equal, if none of them has the prevfree block set
 */

#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stddef.h>
#include <unistd.h>
#include <stdbool.h>

#include "mm.h"
#include "memlib.h"

/* If you want debugging output, use the following macro.
 * When you hand in, remove the #define DEBUG line. */
// #define DEBUG
#ifdef DEBUG
#define debug(fmt, ...) printf("%s: " fmt "\n", __func__, __VA_ARGS__)
#define msg(...) printf(__VA_ARGS__)
#else
#define debug(fmt, ...)
#define msg(...)
#endif

#define __unused __attribute__((unused))

/* do not change the following! */
#ifdef DRIVER
/* create aliases for driver tests */
#define malloc mm_malloc
#define free mm_free
#define realloc mm_realloc
#define calloc mm_calloc
#endif /* !DRIVER */

typedef int32_t word_t; /* Heap is bascially an array of 4-byte words. */

typedef enum {
  FREE = 0,     /* Block is free */
  USED = 1,     /* Block is used */
  PREVFREE = 2, /* Previous block is free (optimized boundary tags) */
} bt_flags;

typedef struct {
  word_t header;
  word_t left;
  word_t right;
  word_t _offset; /* needed so the sizeof(free_block_t) includes the footer */
  word_t payload[];
} free_block_t;

typedef struct {
  word_t header;
  word_t payload[];
} used_block_t;

static word_t *heap_start;    /* First byte of the logical heap */
static word_t *heap_end;      /* First byte past the heap */
static void *last;            /* Pointer to the phisically last block */
static free_block_t *sentiel; /* Address of sentiel */
static size_t hwm;
static size_t chs;

/* --=[ miscellanous procedures ]=------------------------------------------ */

/* Extend the heap by sz bytes. */
static void *morecore(size_t sz) {
  void *ptr = mem_sbrk(sz);
  if (ptr == (void *)-1) {
    assert(false);
    return NULL;
  }
  return ptr;
}

/* Round up sz to ALIGNMENT. */
static inline size_t round_up(size_t sz) {
  return (sz + ALIGNMENT - 1) & -ALIGNMENT;
}

/* Get number of words to allocate for a sz bytes block */
static inline size_t btw_size(size_t sz) {
  return round_up(sz) / sizeof(word_t);
}

/* Get number of bytes of block of sz word_t's size */
static inline size_t wtb_size(size_t sz) {
  return sz * sizeof(word_t);
}

static inline size_t min(size_t a, size_t b) {
  return (a < b ? a : b);
}

/* --=[ boundary tag handling ]=-------------------------------------------- */

/* Creates boundary tag with size and flags. */
static inline void make_bt(word_t *bt, size_t sz, bt_flags flags) {
  *bt = sz | flags;
}

/* Gets size from boundary tag bt. */
static inline size_t get_size(void *bt) {
  return *(word_t *)bt & ~(USED | PREVFREE);
}

/* Checks if block is used. */
static inline word_t is_used(void *bt) {
  return *(word_t *)bt & USED;
}

/* Checks if block is free. */
static inline word_t is_free(void *bt) {
  return !(*(word_t *)bt & USED);
}

/* Sets block to a free block. */
static inline void set_free(void *bt) {
  *(word_t *)bt &= ~USED;
}

/* Get the footer address having the header address. */
static inline word_t *get_footer(free_block_t *bt) {
  return (word_t *)bt + get_size(bt) - 1;
}

/* The name says it all. */
static inline word_t *get_header_from_footer(word_t *footer) {
  return footer - get_size(footer) + 1;
}

/* Gets payload address from used block. */
static inline void *get_payload(used_block_t *block) {
  return block + 1;
}

/* Gets payload size from used block. */
static inline size_t get_payload_size(used_block_t *block) {
  return (get_size(block) - 1) * sizeof(word_t);
}

/* Gets block address from pointer address. */
static inline used_block_t *block_fromptr(void *ptr) {
  return (used_block_t *)ptr - 1;
}

/* Gets next phisical block. */
static inline void *next_block(void *bt) {
  return (word_t *)bt + get_size(bt);
}

/* Check if next phisical block is free. */
static inline word_t is_next_free(void *bt) {
  return last != bt && is_free(next_block(bt));
}

/* Checks if previous block is free (works only for headers). */
static inline bt_flags is_prevfree(void *bt) {
  return *(word_t *)bt & PREVFREE;
}

/* Assumes that is_prevfree(bt) == true */
static inline void *prev_block(void *bt) {
  return get_header_from_footer((word_t *)bt - 1);
}

/* Clears prevfree bit. */
static inline void clr_prevfree(void *bt) {
  *(word_t *)bt &= ~PREVFREE;
}

/* Sets prevfree bit. */
static inline void set_prevfree(void *bt) {
  *(word_t *)bt |= PREVFREE;
}

/* Clear next block's prevfree bit if the block exists present */
static void maybe_clr_next_prevfree(void *block) {
  word_t *next = next_block(block);
  if (next < heap_end) {
    clr_prevfree(next);
  }
}

/* Set next block's prevfree bit if the block exists present */
static void maybe_set_next_prevfree(free_block_t *block) {
  word_t *next = next_block(&block->header);
  if (next < heap_end) {
    set_prevfree(next);
  }
}

/* --=[ block creation ]=--------------------------------------------------- */

/* Make header and footer with size sz and FREE bit unset.
   Size has to be of size at least sizeof(free_block_t) */
static void make_free(void *block, size_t sz, int prev_free) {
#ifdef DEBUG
  assert(sz * sizeof(word_t) >= sizeof(free_block_t));
#endif

  make_bt(block, sz, FREE | prev_free);
  make_bt(get_footer(block), sz, FREE | prev_free);
}

/* Make header for the block with USED bit set. */
static inline void make_used(void *block, size_t sz, int prev_free) {
  make_bt(block, sz, USED | prev_free);
}

/* --=[ Free block data structure iterface ]=------------------------------- */

/* Initialize data structure */
static void init_data_structure(void *params);

/* Insert free block to the data structure */
static void insert_fb(free_block_t *block);

/* Erase free block from the data structure */
static void erase_fb(free_block_t *block);

/* Find free block of reqsz word_t's size. Return NULL if no block availabe. */
static free_block_t *find_fit(size_t reqsz);

/* --=[ Splay functions ]=-------------------------------------------------- */

typedef free_block_t node_t;
static node_t *mock; /* One mock block used for upperbound method. */

/* Get offset from 'from' pointer to 'to' pointer. */
static inline word_t sget_offset(node_t *from, node_t *to) {
  return (word_t)((void *)to - (void *)from);
}

/* Set left child of node par to child. */
static inline void sset_left(node_t *par, node_t *child) {
  par->left = sget_offset(par, child);
}

/* Set right child of node par to child. */
static inline void sset_right(node_t *par, node_t *child) {
  par->right = sget_offset(par, child);
}

/* Get left child of node par. */
static inline node_t *sleft(node_t *node) {
  return (void *)node + node->left;
}

/* Get right child of node par. */
static inline node_t *sright(node_t *node) {
  return (void *)node + node->right;
}

/* Check if left child is sentiel. */
static inline bool is_left_sentiel(node_t *node) {
  return sleft(node) == sentiel;
}

/* Check if right child is sentiel. */
static inline bool is_right_sentiel(node_t *node) {
  return sright(node) == sentiel;
}

/* Check if node is sentiel. */
static inline bool is_sentiel(node_t *node) {
  return node == sentiel;
}

/* Checks if node a is greater than node b. */
static inline bool is_greater(node_t *a, node_t *b) {
  size_t as = get_size(a), bs = get_size(b);
  return (as > bs || (as == bs && a > b));
}

/* Cheks if node a is lesser than node b. */
static inline bool is_lesser(node_t *a, node_t *b) {
  size_t as = get_size(a), bs = get_size(b);
  return (as < bs || (as == bs && a < b));
}

/* Get the lowest node greater or equal to the mock node. Store it in ub */
static node_t *ub;
static void upperbound(node_t *t) {
  if (t == sentiel)
    return;
  if (is_lesser(mock, t)) {
    ub = t;
    upperbound(sleft(t));
  } else if (t == mock) {
    ub = t;
    return;
  } else {
    upperbound(sright(t));
  }
}

/* Splay node in the tree t. Based on Daniel's splay. */
static node_t *splay(node_t *node, node_t *t) {
  node_t N, *l, *r, *y;
  if (t == sentiel)
    return t;
  sset_left(&N, sentiel);
  sset_right(&N, sentiel);
  l = r = &N;

  for (;;) {
    if (is_lesser(node, t)) {
      if (is_left_sentiel(t))
        break;
      if (is_lesser(node, sleft(t))) {
        y = sleft(t);
        sset_left(t, sright(y));
        sset_right(y, t);
        t = y;
        if (is_left_sentiel(t))
          break;
      }
      sset_left(r, t);
      r = t;
      t = sleft(t);
    } else if (is_greater(node, t)) {
      if (is_right_sentiel(t))
        break;
      if (is_greater(node, sright(t))) {
        y = sright(t);
        sset_right(t, sleft(y));
        sset_left(y, t);
        t = y;
        if (is_right_sentiel(t))
          break;
      }
      sset_right(l, t);
      l = t;
      t = sright(t);
    } else {
      break;
    }
  }
  sset_right(l, sleft(t));
  sset_left(r, sright(t));
  sset_left(t, sright(&N));
  sset_right(t, sleft(&N));
  return t;
}

/* Insert node to tree t. Based on Daiel's splay. */
static node_t *sinsert(node_t *node, node_t *t) {
  if (is_sentiel(t)) {
    sset_left(node, sentiel);
    sset_right(node, sentiel);
    return node;
  }
  t = splay(node, t);
  if (is_lesser(node, t)) {
    sset_left(node, sleft(t));
    sset_right(node, t);
    sset_left(t, sentiel);
    return node;
  } else if (is_greater(node, t)) {
    sset_right(node, sright(t));
    sset_left(node, t);
    sset_right(t, sentiel);
    return node;
  } else {
    return t;
  }
}

/* Removes node from tree. Assumes that node is in the tree t.
   Base on Daniel's splay. */
static node_t *sremove(node_t *node, node_t *t) {
  node_t *x;
  t = splay(node, t);
  if (is_left_sentiel(t)) {
    x = sright(t);
  } else {
    x = splay(node, sleft(t));
    sset_right(x, sright(t));
  }
  return x;
}

/* --=[ Interface implemenetation ]=---------------------------------------- */

static node_t *root;

/* Initialize the splay tree. */
static void init_data_structure(void *params) {
  sentiel = params;
  mock = params + ALIGNMENT;
  make_free(sentiel, sizeof(free_block_t), USED);
  sset_right(sentiel, sentiel);
  sset_left(sentiel, sentiel);
  root = sentiel;
}

/* Insert free block to the data structure */
static void insert_fb(free_block_t *block) {
  root = sinsert(block, root);
}

/* Erase free block from the data structure */
static void erase_fb(free_block_t *block) {
  root = sremove(block, root);
}

/* Find free block of reqsz word_t's size. Return NULL if no block availabe. */
static free_block_t *find_fit(size_t reqsz) {
  /* This mock block is used just for upperbound. */
  make_bt(&mock->header, reqsz, USED);

  ub = NULL;
  upperbound(root);
  if (ub) {
    /* This commented lines should be run, but this is slower on the tests. */
    // root = splay(ub, root);
    // return root;
    return ub;
  }
  root = splay(mock, root);
  if (is_sentiel(root) || get_size(root) < reqsz)
    return NULL;
  return root;
}

/* --=[ mm_init ]=---------------------------------------------------------- */

int mm_init(void) {
  /* Place for sentiel, offset so that
   * a new block starts just before aligned byte */
  void *ptr = morecore(3 * ALIGNMENT - sizeof(word_t));
  if (!ptr)
    return -1;
  init_data_structure(ptr);
  heap_start = morecore(0);
  heap_end = heap_start;
  chs = 0;
  hwm = 0;
  last = (word_t *)sentiel; /* Sentiel is the first block */
  return 0;
}

/* --=[ malloc ]=----------------------------------------------------------- */

/* Size is number of requested word_t's */
static void *get_memory_words(size_t sz) {
  void *ptr = morecore(wtb_size(sz));
  heap_end = morecore(0);
  return ptr;
}

/* Allocate additional memory on heap and return (phisicaly) last free block.*/
static used_block_t *allocate_new(size_t sz) {
  int is_last_free = is_free(last) ? PREVFREE : 0;
  size_t alloc_size = sz;
  used_block_t *block;
  if (is_last_free) {
    alloc_size -= get_size(last);
  }
  block = get_memory_words(alloc_size);
  if (is_last_free) {
    block = last;
    erase_fb(last);
  }
  last = block;
  make_used(block, sz, 0);
  return block;
}

/* Block is a free block that has sufficient size to allocate sz words. */
static used_block_t *allocate_existing_block(used_block_t *block, size_t sz) {
  erase_fb((free_block_t *)block);
  size_t prev_sz = get_size(block);
  make_used(block, sz, 0);
  if (prev_sz > sz) {
    free_block_t *next = next_block(block);
    /* Previous block isn't free, otherwise it would be coalessed */
    make_free(next, prev_sz - sz, 0);
    insert_fb(next);
    if (block == last)
      last = next;
  } else {
    maybe_clr_next_prevfree(block);
  }
  return block;
}

/* Allocate a block of sz words size */
static used_block_t *allocate_block(size_t size) {
  used_block_t *block = (used_block_t *)find_fit(size);
  if (!block) {
    block = allocate_new(size);
  } else {
    block = allocate_existing_block(block, size);
  }
  return block;
}

/* Malloc size bytes */
void *malloc(size_t size) {
  if (size == 0)
    return NULL;
  size = btw_size(size + sizeof(used_block_t));
  return get_payload(allocate_block(size));
}

/* --=[ free ]=------------------------------------------------------------- */

/* Try coalescing with previous block. Return pointer to coalesed blocks. */
static free_block_t *coalesce_prev(free_block_t *block) {
  if (is_prevfree(block)) {
    free_block_t *prev = prev_block(block);
    erase_fb(prev);
    size_t new_sz = get_size(prev) + get_size(block);
    make_free(prev, new_sz, 0);
    if (block == last) {
      last = prev;
    }
    block = prev;
  }
  return block;
}

/* Try coalescing with the next block.
   Does not return, because pointer stays the same. */
static void coalesce_next(free_block_t *block) {
  if (is_next_free(block)) {
    free_block_t *next = next_block(block);
    erase_fb(next);
    if (next == last)
      last = block;
    /* Can set PREVFREE to 0, because we coalesed with previous already */
    make_free(block, get_size(block) + get_size(next), 0);
  }
}

/* Coalesce with adjacent free blocks. */
static void coalesce(free_block_t *block) {
  block = coalesce_prev(block);
  coalesce_next(block);
  insert_fb(block);
  maybe_set_next_prevfree(block);
}

/* Free block. */
static void free_block(used_block_t *block) {
  make_free(block, get_size(block), is_prevfree(block));
  coalesce((free_block_t *)block);
}

/* Free malloced memory under ptr. */
void free(void *ptr) {
  if (ptr == NULL)
    return;
  used_block_t *block = block_fromptr(ptr);
  free_block(block);
}

/* --=[ realloc ]=---------------------------------------------------------- */

/* Copies payload from src to dest's payload. */
static void copy_block_payload(used_block_t *dest, used_block_t *src) {
  // msg("Coping from %p to %p, %ld\n", src, dest, size);
  void *dest_payload = get_payload(dest);
  void *src_payload = get_payload(src);
  size_t size = min(get_payload_size(dest), get_payload_size(src));
  memmove(dest_payload, src_payload, size);
}

/* Try extending the old_block without replacing it. */
static int maybe_realloc_inplace(used_block_t *old_block, size_t size) {
  msg("Maybe maybe?\n");
  size_t cur_size = get_size(old_block);
  if (cur_size == size) {
    return 1;
  }
  if (cur_size > size) {
    make_used(old_block, size, is_prevfree(old_block));
    free_block_t *next = next_block(old_block);
    make_free(next, cur_size - size, 0);
    insert_fb(next);
    maybe_set_next_prevfree(next);
    if (last == old_block)
      last = next;
    return 1;
  }
  if (is_next_free(old_block)) {
    free_block_t *next = next_block(old_block);
    size_t size_together = cur_size + get_size(next);
    if (size_together >= size) {
      erase_fb(next);
      make_used(old_block, size, is_prevfree(old_block));
      if (size_together == size) {
        maybe_clr_next_prevfree(old_block);
        if (next == last)
          last = old_block;
      } else {
        free_block_t *new_next = (free_block_t *)next_block(old_block);
        make_free(new_next, size_together - size, 0);
        insert_fb(new_next);
        if (last == next)
          last = new_next;
      }
      return 1;
    }
  }

  return 0;
}

/* Reallocate memory under old_ptr so it has size bytes. */
void *realloc(void *old_ptr, size_t size) {
  if (old_ptr == NULL) {
    return malloc(size);
  }
  if (size == 0) {
    free(old_ptr);
    return NULL;
  }
  size = btw_size(size + sizeof(used_block_t));
  used_block_t *old_block = block_fromptr(old_ptr);
  if (maybe_realloc_inplace(old_block, size)) {
    return get_payload(old_block);
  }
  if (old_block == last) {
    get_memory_words(size - get_size(old_block));
    make_used(old_block, size, is_prevfree(old_block));
    return get_payload(old_block);
  }

  used_block_t *new_block = allocate_block(size);
  copy_block_payload(new_block, old_block);
  free_block(old_block);

  return get_payload(new_block);
}

/* --=[ calloc ]=----------------------------------------------------------- */

/* Allocate and initialize nmemb * size bytes of memory. */
void *calloc(size_t nmemb, size_t size) {
  size_t bytes = nmemb * size;
  void *new_ptr = malloc(bytes);
  if (new_ptr)
    memset(new_ptr, 0, bytes);
  return new_ptr;
}

/* --=[ mm_checkheap ]=----------------------------------------------------- */

void mm_checkheap(int verbose) {
}