Fixed diasterous bug with hfree.

Before this fix, hfree would neglect to set the prev pointer in the next
used block and such was leaving the prev pointers invalid after
coalescing frees.

1 files changed, 140 insertions, 23 deletions

diff --git a/02-usart/tests/test_memory.c b/02-usart/tests/test_memory.c
index 2272f20..04e9289 100644
--- a/02-usart/tests/test_memory.c
+++ b/02-usart/tests/test_memory.c
@@ -9,13 +9,6 @@
 #include "kern/common.h"
 #include "kern/mem.h"
 
-extern uint32_t* halloc_start;
-static void wipeout_halloc()
-{
-  memset(halloc_start, 0, 1024);
-  halloc_start = NULL;
-}
-
 struct TEST_STRUCT {
   uint32_t array[3];
 };
@@ -24,6 +17,32 @@ struct TEST_STRUCT2 {
   uint32_t array[10];
 };
 
+/* Copy of the node structure. */
+typedef struct HALLOC_NODE {
+  union {
+    uint32_t header;
+    struct {
+      /* Is this memory block currently in use (hasn't been hfree'd) */
+      bool     used:1;
+      /* Number of words allocated. Does not include the header. */
+      uint16_t size:12;
+      /* The location of the previous block (in WORDS from offest) */
+      uint16_t prev:12;
+      uint8_t canary:7;
+    } PACKED;
+  };
+
+  uint8_t mem[]; /* The memory to use. */
+} halloc_node_t;
+
+extern halloc_node_t* halloc_start;
+
+static void wipeout_halloc()
+{
+  memset(halloc_start, 0, 1024);
+  halloc_start = NULL;
+}
+
 
 static struct TEST_STRUCT* new_test_struct()
 {
@@ -71,6 +90,18 @@ TEST(memory, halloc)
   ASSERT_CHAIN(test3, test4);
   ASSERT_CHAIN(test4, test5);
 
+
+  char buf[1024];
+  if (debug_halloc_assert_consistency(buf, 1024)) {
+    fprintf(
+        stderr,
+        "Consistency check failed. (%s:%d)\n",
+        __FILE__,
+        __LINE__);
+    fprintf(stderr, buf);
+    ASSERT_TRUE(false);
+  }
+
   wipeout_halloc();
 
   return 0;
@@ -98,6 +129,10 @@ struct UNEVEN_STRUCT* new_uneven_struct()
 
 TEST(memory, uneven_halloc)
 {
+  if (halloc_start) {
+    wipeout_halloc();
+  }
+
   struct UNEVEN_STRUCT* test1 = new_uneven_struct();
   struct UNEVEN_STRUCT* test2 = new_uneven_struct();
 
@@ -110,6 +145,10 @@ TEST(memory, uneven_halloc)
 
 TEST(memory, halloc_free)
 {
+  if (halloc_start) {
+    wipeout_halloc();
+  }
+
   struct TEST_STRUCT* test1 = new_test_struct();
   struct TEST_STRUCT2* test2 = new_test_struct2();
   struct TEST_STRUCT* test3 = new_test_struct();
@@ -122,7 +161,7 @@ TEST(memory, halloc_free)
   hfree(test1);
   hfree(test5);
 
-  ASSERT_EQ((*halloc_start >> 1) * 4, MAX_HEAP_SIZE - 4);
+  ASSERT_EQ((int) halloc_start->size * 4, MAX_HEAP_SIZE - 4);
 
   test1 = new_test_struct();
   test2 = new_test_struct2();
@@ -136,7 +175,7 @@ TEST(memory, halloc_free)
   hfree(test4);
   hfree(test5);
 
-  ASSERT_EQ((*halloc_start >> 1) * 4, MAX_HEAP_SIZE - 4);
+  ASSERT_EQ((int) halloc_start->size * 4, MAX_HEAP_SIZE - 4);
 
   test1 = new_test_struct();
   test2 = new_test_struct2();
@@ -150,7 +189,7 @@ TEST(memory, halloc_free)
   hfree(test2);
   hfree(test5);
 
-  ASSERT_EQ((*halloc_start >> 1) * 4, MAX_HEAP_SIZE - 4);
+  ASSERT_EQ((int) halloc_start->size * 4, MAX_HEAP_SIZE - 4);
 
   wipeout_halloc();
 
@@ -159,6 +198,10 @@ TEST(memory, halloc_free)
 
 TEST(memory, halloc_free_alloc2)
 {
+  if (halloc_start) {
+    wipeout_halloc();
+  }
+
   struct TEST_STRUCT2* test1 = new_test_struct2();
   struct TEST_STRUCT2* test2 = new_test_struct2();
 
@@ -189,53 +232,127 @@ TEST(memory, halloc_free_alloc2)
   return 0;
 }
 
+TEST(memory, relink_backref_after_free)
+{
+  if (halloc_start) {
+    wipeout_halloc();
+  }
+
+  struct TEST_STRUCT* test2 = new_test_struct();
+  struct TEST_STRUCT* test3 = new_test_struct();
+
+  hfree(test2);
+  hfree(test3);
+
+  char buf[1024];
+  if (debug_halloc_assert_consistency(buf, 1024)) {
+    fprintf(stderr, "Consistency check failed.\n");
+    fprintf(stderr, buf);
+    ASSERT_TRUE(false);
+  }
+
+  return 0;
+}
+
 TEST(memory, consistency_stress)
 {
+#define NRUNS 500
   if (halloc_start) {
     wipeout_halloc();
   }
 
   int i;
-  void* allocd[500] = { 0 };
+  void* allocd[NRUNS] = { 0 };
   char buf[1024];
 
-  for (i = 0; i < 500; ++ i) {
+  for (i = 0; i < NRUNS; ++ i) {
     size_t nalloc = rand() % 20;
     allocd[i] = halloc(nalloc);
 
+    if (debug_halloc_assert_consistency(buf, 1024)) {
+      fprintf(
+          stderr,
+          "Consistency check failed. (At index=%d, %s:%d)\n",
+          i,
+          __FILE__,
+          __LINE__);
+      fprintf(stderr, buf);
+      ASSERT_TRUE(false);
+    }
+
     ASSERT_TRUE(allocd[i]);
-    size_t idx = rand() % 500;
+
+    memset(allocd[i], 0xFF, nalloc);
+    size_t idx = rand() % NRUNS;
+
+    if (debug_halloc_assert_consistency(buf, 1024)) {
+      fprintf(
+          stderr,
+          "Consistency check failed. (At index=%d, %s:%d)\n",
+          i,
+          __FILE__,
+          __LINE__);
+      fprintf(stderr, buf);
+      ASSERT_TRUE(false);
+    }
 
     hfree(allocd[idx]);
     allocd[idx] = NULL;
 
-    idx = rand() % 500;
+    if (debug_halloc_assert_consistency(buf, 1024)) {
+      fprintf(
+          stderr,
+          "Consistency check failed. (At index=%d, %s:%d)\n",
+          i,
+          __FILE__,
+          __LINE__);
+      fprintf(stderr, buf);
+      ASSERT_TRUE(false);
+    }
+
+    idx = rand() % NRUNS;
     hfree(allocd[idx]);
     allocd[idx] = NULL;
 
     if (debug_halloc_assert_consistency(buf, 1024)) {
-      fprintf(stderr, "Consistency check failed. (At index %d) nalloc=%lu\n", i, nalloc);
+      fprintf(
+          stderr,
+          "Consistency check failed. (At index=%d, %s:%d)\n",
+          i,
+          __FILE__,
+          __LINE__);
       fprintf(stderr, buf);
       ASSERT_TRUE(false);
     }
   }
 
-  for(i = 0; i < 500; ++ i) {
-    hfree(allocd[i]);
-  }
+  for(i = 0; i < NRUNS; ++ i) {
+    if (allocd[i]) {
+      hfree(allocd[i]);
+    }
 
-  if (debug_halloc_assert_consistency(buf, 1024)) {
-    fprintf(stderr, "Consistency check failed. (Final)\n");
-    fprintf(stderr, buf);
-    ASSERT_TRUE(false);
+    if (debug_halloc_assert_consistency(buf, 1024)) {
+        fprintf(
+            stderr,
+            "Consistency check failed. (At index=%d, %s:%d)\n",
+            i,
+            __FILE__,
+            __LINE__);
+      fprintf(stderr, buf);
+      ASSERT_TRUE(false);
+    }
   }
-  ASSERT_EQ((*halloc_start >> 1) * 4, MAX_HEAP_SIZE - 4);
+  ASSERT_EQ((int) halloc_start->size * 4, MAX_HEAP_SIZE - 4);
 
   return 0;
 }
 
 TEST(memory, halloc_free_alloc)
 {
+  if (halloc_start) {
+    wipeout_halloc();
+  }
+
   new_test_struct();
   struct TEST_STRUCT2* test2 = new_test_struct2();
   new_test_struct();