From baac7009063d94799821422ecc63ea2af41561ea Mon Sep 17 00:00:00 2001
From: Maria Matejka <mq@ucw.cz>
Date: Wed, 14 Aug 2019 16:23:58 +0200
Subject: List expensive check.

---
 lib/lists.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 61 insertions(+)

(limited to 'lib/lists.c')

diff --git a/lib/lists.c b/lib/lists.c
index 4a48d3b7..c162a991 100644
--- a/lib/lists.c
+++ b/lib/lists.c
@@ -29,6 +29,42 @@
 #include "nest/bird.h"
 #include "lib/lists.h"
 
+LIST_INLINE int
+check_list(list *l, node *n)
+{
+  if (!l)
+  {
+    ASSERT_DIE(n);
+    ASSERT_DIE(n->prev);
+
+    do { n = n->prev; } while (n->prev);
+
+    l = SKIP_BACK(list, head_node, n);
+  }
+
+  int seen = 0;
+
+  ASSERT_DIE(l->null == NULL);
+  ASSERT_DIE(l->head != NULL);
+  ASSERT_DIE(l->tail != NULL);
+
+  node *prev = &l->head_node, *cur = l->head, *next = l->head->next;
+  while (next)
+  {
+    if (cur == n)
+      seen++;
+    ASSERT_DIE(cur->prev == prev);
+    prev = cur;
+    cur = next;
+    next = next->next;
+  }
+
+  ASSERT_DIE(cur == &(l->tail_node));
+  ASSERT_DIE(!n || (seen == 1));
+
+  return 1;
+}
+
 /**
  * add_tail - append a node to a list
  * @l: linked list
@@ -39,6 +75,10 @@
 LIST_INLINE void
 add_tail(list *l, node *n)
 {
+  EXPENSIVE_CHECK(check_list(l, NULL));
+  ASSUME(n->prev == NULL);
+  ASSUME(n->next == NULL);
+
   node *z = l->tail;
 
   n->next = &l->tail_node;
@@ -57,6 +97,10 @@ add_tail(list *l, node *n)
 LIST_INLINE void
 add_head(list *l, node *n)
 {
+  EXPENSIVE_CHECK(check_list(l, NULL));
+  ASSUME(n->prev == NULL);
+  ASSUME(n->next == NULL);
+
   node *z = l->head;
 
   n->next = z;
@@ -76,6 +120,10 @@ add_head(list *l, node *n)
 LIST_INLINE void
 insert_node(node *n, node *after)
 {
+  EXPENSIVE_CHECK(check_list(l, after));
+  ASSUME(n->prev == NULL);
+  ASSUME(n->next == NULL);
+
   node *z = after->next;
 
   n->next = z;
@@ -93,6 +141,8 @@ insert_node(node *n, node *after)
 LIST_INLINE void
 rem_node(node *n)
 {
+  EXPENSIVE_CHECK(check_list(NULL, n));
+
   node *z = n->prev;
   node *x = n->next;
 
@@ -116,6 +166,10 @@ rem_node(node *n)
 LIST_INLINE void
 replace_node(node *old, node *new)
 {
+  EXPENSIVE_CHECK(check_list(NULL, old));
+  ASSUME(new->prev == NULL);
+  ASSUME(new->next == NULL);
+
   old->next->prev = new;
   old->prev->next = new;
 
@@ -149,6 +203,9 @@ init_list(list *l)
 LIST_INLINE void
 add_tail_list(list *to, list *l)
 {
+  EXPENSIVE_CHECK(check_list(to, NULL));
+  EXPENSIVE_CHECK(check_list(l, NULL));
+
   node *p = to->tail;
   node *q = l->head;
 
@@ -157,6 +214,8 @@ add_tail_list(list *to, list *l)
   q = l->tail;
   q->next = &to->tail_node;
   to->tail = q;
+
+  EXPENSIVE_CHECK(check_list(to, NULL));
 }
 
 LIST_INLINE uint
@@ -165,6 +224,8 @@ list_length(list *l)
   uint len = 0;
   node *n;
 
+  EXPENSIVE_CHECK(check_list(l, NULL));
+
   WALK_LIST(n, *l)
     len++;
 
-- 
cgit v1.2.3


From e26a5195dd6c62e6f4b80d13b6ecd5f40ee68546 Mon Sep 17 00:00:00 2001
From: Maria Matejka <mq@ucw.cz>
Date: Sat, 17 Aug 2019 14:03:47 +0200
Subject: Lists: fix a stupid sanitizer bug

---
 lib/lists.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

(limited to 'lib/lists.c')

diff --git a/lib/lists.c b/lib/lists.c
index c162a991..8553ee27 100644
--- a/lib/lists.c
+++ b/lib/lists.c
@@ -167,8 +167,12 @@ LIST_INLINE void
 replace_node(node *old, node *new)
 {
   EXPENSIVE_CHECK(check_list(NULL, old));
-  ASSUME(new->prev == NULL);
-  ASSUME(new->next == NULL);
+
+  if (old != new)
+  {
+    ASSUME(new->prev == NULL);
+    ASSUME(new->next == NULL);
+  }
 
   old->next->prev = new;
   old->prev->next = new;
-- 
cgit v1.2.3


From 9ac13d7af25d6b26866bf4f4a4fab371925fb1df Mon Sep 17 00:00:00 2001
From: Maria Matejka <mq@ucw.cz>
Date: Mon, 19 Aug 2019 14:36:51 +0200
Subject: Lists: Replaced replace_node() by update_node() which is the only use
 of that function.

---
 lib/lists.c      | 28 ++++++++--------------------
 lib/lists_test.c | 13 ++++++++-----
 lib/resource.c   |  2 +-
 3 files changed, 17 insertions(+), 26 deletions(-)

(limited to 'lib/lists.c')

diff --git a/lib/lists.c b/lib/lists.c
index 8553ee27..200576cf 100644
--- a/lib/lists.c
+++ b/lib/lists.c
@@ -153,32 +153,20 @@ rem_node(node *n)
 }
 
 /**
- * replace_node - replace a node in a list with another one
- * @old: node to be removed
- * @new: node to be inserted
+ * update_node - update node after calling realloc on it
+ * @n: node to be updated
  *
- * Replaces node @old in the list it's linked in with node @new.  Node
- * @old may be a copy of the original node, which is not accessed
- * through the list. The function could be called with @old == @new,
- * which just fixes neighbors' pointers in the case that the node
- * was reallocated.
+ * Fixes neighbor pointers.
  */
 LIST_INLINE void
-replace_node(node *old, node *new)
+update_node(node *n)
 {
-  EXPENSIVE_CHECK(check_list(NULL, old));
+  ASSUME(n->next->prev == n->prev->next);
 
-  if (old != new)
-  {
-    ASSUME(new->prev == NULL);
-    ASSUME(new->next == NULL);
-  }
+  n->next->prev = n;
+  n->prev->next = n;
 
-  old->next->prev = new;
-  old->prev->next = new;
-
-  new->prev = old->prev;
-  new->next = old->next;
+  EXPENSIVE_CHECK(check_list(NULL, n));
 }
 
 /**
diff --git a/lib/lists_test.c b/lib/lists_test.c
index f26a88e2..cf0021fe 100644
--- a/lib/lists_test.c
+++ b/lib/lists_test.c
@@ -222,26 +222,29 @@ t_remove_node(void)
 }
 
 static int
-t_replace_node(void)
+t_update_node(void)
 {
   node head, inside, tail;
 
   init_list_();
   fill_list();
 
-  replace_node(&nodes[0], &head);
+  head = nodes[0];
+  update_node(&head);
   bt_assert(l.head == &head);
   bt_assert(head.prev == NODE &l.head);
   bt_assert(head.next == &nodes[1]);
   bt_assert(nodes[1].prev == &head);
 
-  replace_node(&nodes[MAX_NUM/2], &inside);
+  inside = nodes[MAX_NUM/2];
+  update_node(&inside);
   bt_assert(nodes[MAX_NUM/2-1].next == &inside);
   bt_assert(nodes[MAX_NUM/2+1].prev == &inside);
   bt_assert(inside.prev == &nodes[MAX_NUM/2-1]);
   bt_assert(inside.next == &nodes[MAX_NUM/2+1]);
 
-  replace_node(&nodes[MAX_NUM-1], &tail);
+  tail = nodes[MAX_NUM-1];
+  update_node(&tail);
   bt_assert(l.tail == &tail);
   bt_assert(tail.prev == &nodes[MAX_NUM-2]);
   bt_assert(tail.next == NODE &l.null);
@@ -280,7 +283,7 @@ main(int argc, char *argv[])
   bt_test_suite(t_add_head, "Adding nodes to head of list");
   bt_test_suite(t_insert_node, "Inserting nodes to list");
   bt_test_suite(t_remove_node, "Removing nodes from list");
-  bt_test_suite(t_replace_node, "Replacing nodes in list");
+  bt_test_suite(t_update_node, "Updating nodes in list");
   bt_test_suite(t_add_tail_list, "At the tail of a list adding the another list");
 
   return bt_exit_value();
diff --git a/lib/resource.c b/lib/resource.c
index 7e624321..5589373e 100644
--- a/lib/resource.c
+++ b/lib/resource.c
@@ -388,7 +388,7 @@ mb_realloc(void *m, unsigned size)
   struct mblock *b = SKIP_BACK(struct mblock, data, m);
 
   b = xrealloc(b, sizeof(struct mblock) + size);
-  replace_node(&b->r.n, &b->r.n);
+  update_node(&b->r.n);
   b->size = size;
   return b->data;
 }
-- 
cgit v1.2.3