Added full description of the program and some comments

1 files changed, 95 insertions, 20 deletions

diff --git a/mm.c b/mm.c
index a4f0ef0..161b304 100644
--- a/mm.c
+++ b/mm.c
@@ -7,6 +7,8 @@
  * TL;DR: optimised boundary tags and splay tree of free blocks with eager
  * coalescing.
  *
+ * --=[ MANAGING USED AND FREE BLOCK ]=--
+ *
  * Used blocks structure:
  * +-------------+
  * | Header      |
@@ -67,10 +69,64 @@
  * 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.
+ * 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>
@@ -94,7 +150,7 @@
 /* Insertion policy */
 // #define LIFO
 // #define FIFO
-#define SORT            /* Keep the list sorted by block size */
+#define SORT /* Keep the list sorted by block size */
 // #define SORT_ADDR       /* Keep the list sorted by block address */
 
 /* Find-fit policy */
@@ -160,6 +216,7 @@ 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) {
@@ -169,6 +226,7 @@ static void *morecore(size_t sz) {
   return ptr;
 }
 
+/* Round up sz to ALIGNMENT. */
 static inline size_t round_up(size_t sz) {
   return (sz + ALIGNMENT - 1) & -ALIGNMENT;
 }
@@ -296,7 +354,8 @@ static void maybe_set_next_prevfree(free_block_t *block) {
 
 /* --=[ block creation ]=--------------------------------------------------- */
 
-/* Size has to be of size at least sizeof(free_block_t) */
+/* 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));
@@ -306,6 +365,7 @@ static void make_free(void *block, size_t sz, int 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);
 }
@@ -328,54 +388,63 @@ static free_block_t *find_fit(size_t reqsz);
 
 #ifdef SPLAY_IMP
 
-static free_block_t *mock; /* One mock block (splay) */
-
 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));
 }
 
 #ifdef DEBUG
-#ifdef SPLAY_IMP
+/* Prints the splay tree. */
 static void print_splay(node_t *node, int ind) {
   if (is_sentiel(node))
     return;
@@ -390,24 +459,25 @@ static void print_splay(node_t *node, int ind) {
   print_splay(sleft(node), ind + 2);
   print_splay(sright(node), ind + 2);
 }
-#endif /* SPLAY_IMP */
 #endif /* DEBUG */
 
+/* Get the lowest node greater or equal to the mock node. Store it in ub */
 static node_t *ub;
-static void upperbound(node_t *node, node_t *t) {
+static void upperbound(node_t *t) {
   if (t == sentiel)
     return;
-  if (is_lesser(node, t)) {
+  if (is_lesser(mock, t)) {
     ub = t;
-    upperbound(node, sleft(t));
-  } else if (t == node) {
+    upperbound(sleft(t));
+  } else if (t == mock) {
     ub = t;
     return;
   } else {
-    upperbound(node, sright(t));
+    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)
@@ -456,7 +526,7 @@ static node_t *splay(node_t *node, node_t *t) {
   return t;
 }
 
-/* insert node to tree 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);
@@ -479,7 +549,8 @@ static node_t *sinsert(node_t *node, node_t *t) {
   }
 }
 
-/* Removes node from tree. Assumes that node is in the tree 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;
   msg("removing %p\n", node);
@@ -500,6 +571,7 @@ static node_t *sremove(node_t *node, node_t *t) {
 
 static node_t *root;
 
+/* Initialize the splay tree. */
 static void init_data_structure(void *params) {
   sentiel = params;
   mock = params + ALIGNMENT;
@@ -521,13 +593,16 @@ 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) {
+  /* This mock block is used just for upperbound. */
   make_bt(&mock->header, reqsz, USED);
+
   ub = NULL;
-  upperbound(mock, root);
+  upperbound(root);
   if (ub) {
-    root = splay(ub, root);
-    return root;
-    // return 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)
@@ -693,13 +768,13 @@ static void print_data_structure() {
   msg("------------=[ SPLAY BEG ]=-------------\n");
   print_splay(root, 0);
   msg("------------=[ SPLAY END ]=-------------\n\n");
-
 #endif /* LIST_IMP */
 #endif /* DEBUG */
 }
 
 /* --=[ general debug ]=----------------------------------------------------- */
 
+/* Print the heap and check its integrity. */
 static void print_heap() {
 #ifdef DEBUG
   msg("-------=[ HEAP BEGIN ]=--------\n");