Added asserts back with additional flag DASSERT

1 files changed, 155 insertions, 84 deletions

diff --git a/mm.c b/mm.c
index ca2c406..1237441 100644
--- a/mm.c
+++ b/mm.c
@@ -69,7 +69,8 @@
  * implementation).
  *
  * This implementation provides two data structures for managing free blocks:
- * - doubly linked list,
+ * - doubly linked list (EDIT: I removed the list implementation, it's in
+ *   previous commits),
  * - splay tree.
  *
  * Both data structures implement a simple interface for the allocator:
@@ -83,6 +84,9 @@
  * Thanks to this abstraction the implementation of allocator functions are
  * (almost) independent from the implementation of the DS.
  *
+ *
+ * EDIT: I removed it, you can see it in the previous commits. There's
+ * only splay implementation.
  * 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.
@@ -164,12 +168,19 @@
 // #define DEBUG
 #ifdef DEBUG
 #define debug(fmt, ...) printf("%s: " fmt "\n", __func__, __VA_ARGS__)
-#define msg(...) printf(__VA_ARGS__)
+#define msg(...) fprintf(stderr, __VA_ARGS__)
 #else
 #define debug(fmt, ...)
 #define msg(...)
 #endif
 
+// #define DASSERT
+#ifdef DASSERT
+#define dassert(x) assert(x)
+#else
+#define dassert(x)
+#endif
+
 #define __unused __attribute__((unused))
 
 /* do not change the following! */
@@ -279,11 +290,13 @@ static inline word_t *get_header_from_footer(word_t *footer) {
 
 /* Gets payload address from used block. */
 static inline void *get_payload(used_block_t *block) {
+  dassert(is_used(block));
   return block + 1;
 }
 
 /* Gets payload size from used block. */
 static inline size_t get_payload_size(used_block_t *block) {
+  dassert(is_used(block));
   return (get_size(block) - 1) * sizeof(word_t);
 }
 
@@ -309,6 +322,7 @@ static inline bt_flags is_prevfree(void *bt) {
 
 /* Assumes that is_prevfree(bt) == true */
 static inline void *prev_block(void *bt) {
+  dassert(is_prevfree(bt));
   return get_header_from_footer((word_t *)bt - 1);
 }
 
@@ -343,9 +357,7 @@ static void maybe_set_next_prevfree(free_block_t *block) {
 /* 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
+  dassert(sz * sizeof(word_t) >= sizeof(free_block_t));
 
   make_bt(block, sz, FREE | prev_free);
   make_bt(get_footer(block), sz, FREE | prev_free);
@@ -520,6 +532,10 @@ static node_t *sinsert(node_t *node, node_t *t) {
 static node_t *sremove(node_t *node, node_t *t) {
   node_t *x;
   t = splay(node, t);
+
+  /* Node should be in tree. */
+  dassert(node == t);
+
   if (is_left_sentiel(t)) {
     x = sright(t);
   } else {
@@ -529,53 +545,6 @@ static node_t *sremove(node_t *node, node_t *t) {
   return x;
 }
 
-static void print_heap() {
-#ifdef DEBUG
-  msg("-------=[ HEAP BEGIN ]=--------\n");
-  word_t *crawl = heap_start;
-  int blocks_cnt = 0;
-  int used_cnt = 0;
-  chs = 0;
-  while (crawl < heap_end) {
-    // if (cnt < 5) {
-    msg("%p [%ld] %s, %s\n", crawl, get_size(crawl),
-        (is_free(crawl) ? "FREE" : "USED"), (is_prevfree(crawl) ? "pf" : "-"));
-    // }
-    // else if (cnt == 5) {
-    //   msg(".\n.\n.\n");
-    // }
-    blocks_cnt++;
-    if (is_used(crawl)) {
-      chs += get_size(crawl);
-      used_cnt++;
-    }
-    word_t *next = next_block(crawl);
-    if (next < heap_end) {
-      // assert(prev_block())
-      // assert(is_used(crawl));
-      assert(is_used(crawl) || is_prevfree(next));
-    }
-    if (next == heap_end) {
-      assert(last == crawl);
-    }
-    crawl = next;
-  }
-  if (chs > hwm) {
-    hwm = chs;
-  }
-  msg("-------=[  HEAP END  ]=--------\n\n");
-  msg("-------=[  HEAP STATS BEG ]=--------\n");
-  msg("Blocks cnt: [all] %d, [free] %d, [used] %d\n", blocks_cnt,
-      blocks_cnt - used_cnt, used_cnt);
-  msg("last: %p, sentiel: %p\n", last, sentiel);
-  size_t heap_size = (size_t)((void *)heap_end - (void *)heap_start);
-  msg("heap size: %ldB, %ld words\n", heap_size, heap_size / sizeof(word_t));
-  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 /* DEBUG */
-}
-
 /* --=[ Interface implemenetation ]=---------------------------------------- */
 
 static node_t *root;
@@ -597,6 +566,7 @@ static void insert_fb(free_block_t *block) {
 
 /* Erase free block from the data structure */
 static void erase_fb(free_block_t *block) {
+  dassert(is_free(block));
   root = sremove(block, root);
 }
 
@@ -619,6 +589,69 @@ static free_block_t *find_fit(size_t reqsz) {
   return root;
 }
 
+#ifdef DASSERT
+static void print_splay(node_t *node, int ind) {
+  if (is_sentiel(node))
+    return;
+  for (int i = 0; i < ind; i++)
+    msg(" ");
+  msg("[%p], size %ld, left %p, right %p\n", node, get_size(node), sleft(node),
+      sright(node));
+  if (!is_left_sentiel(node))
+    dassert(is_lesser(sleft(node), node));
+  if (!is_right_sentiel(node))
+    dassert(is_greater(sright(node), node));
+  print_splay(sleft(node), ind + 2);
+  print_splay(sright(node), ind + 2);
+}
+
+static void print_data_structure() {
+  msg("------------=[ SPLAY BEG ]=-------------\n");
+  print_splay(root, 0);
+  msg("------------=[ SPLAY END ]=-------------\n\n");
+}
+
+static void print_heap() {
+  msg("-------=[ HEAP BEGIN ]=--------\n");
+  word_t *crawl = heap_start;
+  int blocks_cnt = 0;
+  int used_cnt = 0;
+  chs = 0;
+  while (crawl < heap_end) {
+    msg("%p [%ld] %s, %s\n", crawl, get_size(crawl),
+        (is_free(crawl) ? "FREE" : "USED"), (is_prevfree(crawl) ? "pf" : "-"));
+    blocks_cnt++;
+    if (is_used(crawl)) {
+      chs += get_size(crawl);
+      used_cnt++;
+    }
+    word_t *next = next_block(crawl);
+    if (next < heap_end) {
+      dassert(is_used(crawl) || (is_prevfree(next) && is_used(next)));
+    }
+    if (next == heap_end) {
+      dassert(last == crawl);
+    }
+    crawl = next;
+  }
+  if (chs > hwm) {
+    hwm = chs;
+  }
+  msg("-------=[  HEAP END  ]=--------\n\n");
+  msg("-------=[  HEAP STATS BEG ]=--------\n");
+  msg("Blocks cnt: [all] %d, [free] %d, [used] %d\n", blocks_cnt,
+      blocks_cnt - used_cnt, used_cnt);
+  msg("last: %p, sentiel: %p\n", last, sentiel);
+#ifdef DEBUG
+  size_t heap_size = (size_t)((void *)heap_end - (void *)heap_start);
+#endif
+  msg("heap size: %ldB, %ld words\n", heap_size, heap_size / sizeof(word_t));
+  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 /* DASSERT */
+
 /* --=[ mm_init ]=---------------------------------------------------------- */
 
 int mm_init(void) {
@@ -647,12 +680,17 @@ static void *get_memory_words(size_t sz) {
 
 /* 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;
   size_t alloc_size = sz;
   used_block_t *block;
   if (is_last_free) {
     alloc_size -= get_size(last);
   }
+
+  dassert(alloc_size > 0);
+
   block = get_memory_words(alloc_size);
   if (is_last_free) {
     block = last;
@@ -665,6 +703,8 @@ static used_block_t *allocate_new(size_t sz) {
 
 /* 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) {
+  msg("Allocating existing %p.\n", block);
+
   erase_fb((free_block_t *)block);
   size_t prev_sz = get_size(block);
   make_used(block, sz, 0);
@@ -683,19 +723,27 @@ static used_block_t *allocate_existing_block(used_block_t *block, size_t sz) {
 
 /* Allocate a block of sz words size */
 static used_block_t *allocate_block(size_t size) {
+  msg(">>>> Allocating block %ld\n", size);
+
   used_block_t *block = (used_block_t *)find_fit(size);
+  msg("Block: %p\n", block);
+
   if (!block) {
     block = allocate_new(size);
   } else {
     block = allocate_existing_block(block, size);
   }
+
+#ifdef DASSERT
+  print_data_structure();
   print_heap();
+#endif
+
   return block;
 }
 
 /* Malloc size bytes */
 void *malloc(size_t size) {
-  msg("Mallocing %ld\n", size);
   if (size == 0)
     return NULL;
   size = btw_size(size + sizeof(used_block_t));
@@ -748,26 +796,34 @@ static void free_block(used_block_t *block) {
 
 /* Free malloced memory under ptr. */
 void free(void *ptr) {
-  msg("Freeing %p", ptr);
   if (ptr == NULL)
     return;
   used_block_t *block = block_fromptr(ptr);
+  msg(">>>> Freeing block %p, ptr %p\n", block, ptr);
+
   free_block(block);
+
+#ifdef DASSERT
+  print_data_structure();
   print_heap();
+#endif
 }
 
 /* --=[ 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));
+
+  msg("Coping from %p to %p, %ld\n", src, dest, size);
   memmove(dest_payload, src_payload, size);
 }
 
+/* Reduce the block size to new_sz. */
 static void reduce_block(used_block_t *block, size_t old_sz, size_t new_sz) {
+  dassert(old_sz > new_sz);
   make_used(block, new_sz, is_prevfree(block));
   free_block_t *next = next_block(block);
   if (block == last)
@@ -776,7 +832,9 @@ static void reduce_block(used_block_t *block, size_t old_sz, size_t new_sz) {
   free_block((used_block_t *)next);
 }
 
+/* Try extending without replacing it. Assumes that next block is free. */
 static bool maybe_extend_block(used_block_t *block, size_t cur_sz, size_t sz) {
+  dassert(is_next_free(block));
   free_block_t *next = next_block(block);
   size_t sz_both = cur_sz + get_size(next);
   if (sz_both < sz)
@@ -799,7 +857,6 @@ static bool maybe_extend_block(used_block_t *block, size_t cur_sz, size_t sz) {
 
 /* Try extending the old_block without replacing it. */
 static bool maybe_realloc_inplace(used_block_t *block, size_t sz) {
-  msg("Maybe maybe?\n");
   size_t cur_sz = get_size(block);
   if (cur_sz == sz) {
     return true;
@@ -812,12 +869,15 @@ static bool maybe_realloc_inplace(used_block_t *block, size_t sz) {
   return false;
 }
 
+/* Extend the block, which is the last block of the heap */
 static void *realloc_to_heap_end(used_block_t *block, size_t sz) {
+  dassert(last == block);
   get_memory_words(sz - get_size(block));
   make_used(block, sz, is_prevfree(block));
   return get_payload(block);
 }
 
+/* Realloc block to some free block. Basically do malloc and copy. */
 static void *realloc_to_new_block(used_block_t *block, size_t sz) {
   used_block_t *new_block = allocate_block(sz);
   copy_block_payload(new_block, block);
@@ -825,27 +885,29 @@ static void *realloc_to_new_block(used_block_t *block, size_t sz) {
   return get_payload(new_block);
 }
 
-// static void *maybe_extend_to_left(used_block_t *block, size_t sz) {
-//   used_block_t *prev = prev_block(block);
-//   size_t both_sz = get_size(prev) + get_size(block);
-//   if (both_sz < sz) return NULL;
-
-//   erase_fb((free_block_t *)prev);
-//   make_used(prev, sz, 0);
-//   copy_block_payload(prev, block);
-//   if (both_sz == sz) {
-//     if (last == block)
-//       last = prev;
-//   }
-//   else { /* both_sz > sz */
-//     used_block_t *next = next_block(prev);
-//     make_free(next, both_sz - sz, 0);
-//     if (last == block)
-//       last = next;
-//     free_block(next);
-//   }
-//   return get_payload(prev);
-// }
+/* I tried it, but its slower and has lower utilisation :(
+static void *maybe_extend_to_left(used_block_t *block, size_t sz) {
+  used_block_t *prev = prev_block(block);
+  size_t both_sz = get_size(prev) + get_size(block);
+  if (both_sz < sz) return NULL;
+
+  erase_fb((free_block_t *)prev);
+  make_used(prev, sz, 0);
+  copy_block_payload(prev, block);
+  if (both_sz == sz) {
+    if (last == block)
+      last = prev;
+  }
+  else { // both_sz > sz
+    used_block_t *next = next_block(prev);
+    make_free(next, both_sz - sz, 0);
+    if (last == block)
+      last = next;
+    free_block(next);
+  }
+  return get_payload(prev);
+}
+*/
 
 /* Reallocate memory under old_ptr so it has size bytes. */
 void *realloc(void *old_ptr, size_t size) {
@@ -859,20 +921,28 @@ void *realloc(void *old_ptr, size_t size) {
 
   size = btw_size(size + sizeof(used_block_t));
   used_block_t *block = block_fromptr(old_ptr);
-  msg("Reallocing %p, %ld\n", block, size);
+  msg(">>>> Reallocating %p %ld\n", old_block, size);
+
   if (maybe_realloc_inplace(block, size)) {
     old_ptr = get_payload(block);
+#ifdef DASSERT
+    print_data_structure();
+    print_heap();
+#endif
   }
-  // else if (is_prevfree(block) && (old_ptr = maybe_extend_to_left(block,
-  // size))) {
-  //   ;
-  // }
-  else if (block == last) {
+  /* else if (is_prevfree(block) && (old_ptr = maybe_extend_to_left(block,
+  size))) {
+    ;
+  } */
+  if (block == last) {
     old_ptr = realloc_to_heap_end(block, size);
+#ifdef DASSERT
+    print_data_structure();
+    print_heap();
+#endif
   } else {
     old_ptr = realloc_to_new_block(block, size);
   }
-  print_heap();
   return old_ptr;
 }
 
@@ -890,4 +960,5 @@ void *calloc(size_t nmemb, size_t size) {
 /* --=[ mm_checkheap ]=----------------------------------------------------- */
 
 void mm_checkheap(int verbose) {
+  /* Maybe that was not a good idea, but I managed debuging myself. */
 }