Added comments

1 files changed, 110 insertions, 43 deletions

diff --git a/mm.c b/mm.c
index 6fb9b4d..a4f0ef0 100644
--- a/mm.c
+++ b/mm.c
@@ -1,3 +1,78 @@
+/* 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.
+ *
+ * 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.
+ * 
+ * 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.
+ */
+
 #include <assert.h>
 #include <limits.h>
 #include <stdio.h>
@@ -11,17 +86,22 @@
 #include "mm.h"
 #include "memlib.h"
 
+// #define LIST_IMP
+#define SPLAY_IMP
+
+#ifdef LIST_IMP
+
+/* Insertion policy */
 // #define LIFO
 // #define FIFO
-#define SORT
-// #define SORT_ADDR
+#define SORT            /* Keep the list sorted by block size */
+// #define SORT_ADDR       /* Keep the list sorted by block address */
 
+/* Find-fit policy */
 #define FIRSTFIT
-// #define NEXTFIT
 // #define BESTFIT
 
-// #define LIST_IMP
-#define SPLAY_IMP
+#endif /* LIST_IMP */
 
 /* If you want debugging output, use the following macro.
  * When you hand in, remove the #define DEBUG line. */
@@ -75,7 +155,6 @@ 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 free_block_t *mock;    /* One mock block (splay) */
 static size_t hwm;
 static size_t chs;
 
@@ -111,8 +190,8 @@ static inline size_t min(size_t a, size_t b) {
 /* --=[ boundary tag handling ]=-------------------------------------------- */
 
 /* Creates boundary tag with size and flags. */
-static inline void make_bt(word_t *bt, size_t size, bt_flags flags) {
-  *bt = size | flags;
+static inline void make_bt(word_t *bt, size_t sz, bt_flags flags) {
+  *bt = sz | flags;
 }
 
 /* Gets size from boundary tag bt. */
@@ -249,6 +328,8 @@ 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 inline word_t sget_offset(node_t *from, node_t *to) {
@@ -309,8 +390,8 @@ static void print_splay(node_t *node, int ind) {
   print_splay(sleft(node), ind + 2);
   print_splay(sright(node), ind + 2);
 }
-#endif
-#endif
+#endif /* SPLAY_IMP */
+#endif /* DEBUG */
 
 static node_t *ub;
 static void upperbound(node_t *node, node_t *t) {
@@ -318,10 +399,8 @@ static void upperbound(node_t *node, node_t *t) {
     return;
   if (is_lesser(node, t)) {
     ub = t;
-    msg("is_lesser(%p, %p)\n", node, t);
     upperbound(node, sleft(t));
   } else if (t == node) {
-    msg("%p == %p\n", node, t);
     ub = t;
     return;
   } else {
@@ -417,6 +496,8 @@ static node_t *sremove(node_t *node, node_t *t) {
   return x;
 }
 
+/* --=[ Interface implemenetation ]=---------------------------------------- */
+
 static node_t *root;
 
 static void init_data_structure(void *params) {
@@ -440,28 +521,21 @@ 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 is tricky - we use sentiel as a query node, because it has to lowest
-   * possible address. We will find the lowest node with size at least reqsz. */
-  msg("Splayed for %ld:\n", reqsz);
   make_bt(&mock->header, reqsz, USED);
-
   ub = NULL;
   upperbound(mock, root);
   if (ub) {
-    // msg("ub: %p, %ld\n", ub, reqsz);
-    // root = splay(ub, root);
-    // return root;
-    return ub;
+    root = splay(ub, root);
+    return root;
+    // return ub;
   }
-  // print_splay(root, 0);
   root = splay(mock, root);
-  // print_splay(root, 0);
   if (is_sentiel(root) || get_size(root) < reqsz)
     return NULL;
   return root;
 }
 
-#endif
+#endif /* SPLAY_IMP */
 
 /* --=[ list functions ]=--------------------------------------------------- */
 
@@ -542,10 +616,8 @@ static void linsert(free_block_t *block) {
   ladd_after(block, lprev(crawl));
 }
 #else
-static void linsert(free_block_t *block) {
-  assert(false);
-}
-#endif
+#error "No linsert implementation."
+#endif /* Insertion policy */
 
 static void insert_fb(free_block_t *block) {
   linsert(block);
@@ -589,12 +661,9 @@ static free_block_t *find_fit(size_t reqsz) {
 static free_block_t *find_fit(size_t reqsz) {
 }
 #else
-static free_block_t *find_fit(size_t reqsz) {
-  assert(false);
-}
-#endif
-
-#endif
+#error "No find-fit implementation"
+#endif /* Find-fit policy */
+#endif /* LIST_IMP */
 
 /* --=[ list debug ]=-------------------------------------------------------- */
 
@@ -625,8 +694,8 @@ static void print_data_structure() {
   print_splay(root, 0);
   msg("------------=[ SPLAY END ]=-------------\n\n");
 
-#endif
-#endif
+#endif /* LIST_IMP */
+#endif /* DEBUG */
 }
 
 /* --=[ general debug ]=----------------------------------------------------- */
@@ -662,11 +731,9 @@ static void print_heap() {
         assert((uint64_t)lprev((free_block_t *)crawl) % 4 == 0);
         assert(!is_free(next));
       }
-#endif
+#endif /* LIST_IMP */
     }
     if (next == heap_end) {
-      // msg("%p [%ld] %s, %s\n", crawl, get_size(crawl), (is_free(crawl) ?
-      // "FREE" : "USED"), (is_prevfree(crawl) ? "pf" : "-"));
       assert(last == crawl);
     }
     crawl = next;
@@ -684,7 +751,7 @@ static void print_heap() {
   msg("HWM: %ld, CHS: %ld\n", hwm, chs);
   msg("Util: %f%%\n", (float)hwm / (float)(heap_size / sizeof(word_t)) * 100.0);
   msg("-------=[  HEAP STATS END ]=--------\n\n");
-#endif
+#endif /* DEBUG */
 }
 
 /* --=[ mm_init ]=---------------------------------------------------------- */
@@ -698,7 +765,7 @@ static void init_data_structure(void *params) {
   lset_next(sentiel, sentiel);
   lset_prev(sentiel, sentiel);
 }
-#endif
+#endif /* LIST_IMP */
 
 int mm_init(void) {
   /* Place for sentiel, offset so that
@@ -728,12 +795,10 @@ static void *get_memory_words(size_t sz) {
   return ptr;
 }
 
-/* Allocate additional memory on heap and return (phisically) last free block.
- */
+/* Allocate additional memory on heap and return (phisicaly) last free block.*/
 static used_block_t *allocate_new(size_t sz) {
   msg("Allocating new.\n");
   int is_last_free = is_free(last) ? PREVFREE : 0;
-  // msg("last: %p\n", last);
   size_t alloc_size = sz;
   used_block_t *block;
   if (is_last_free) {
@@ -906,6 +971,7 @@ static int maybe_realloc_inplace(used_block_t *old_block, size_t size) {
   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);
@@ -939,6 +1005,7 @@ void *realloc(void *old_ptr, size_t size) {
 
 /* --=[ 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);