Merge branch 'mq-resource-locking' into thread-next

9 files changed, 521 insertions, 59 deletions

diff --git a/lib/Makefile b/lib/Makefile
index f4ade9a6..6ed778cc 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -2,6 +2,6 @@ src := a-path.c a-set.c bitmap.c bitops.c blake2s.c blake2b.c checksum.c event.c
 obj := $(src-o-files)
 $(all-daemon)
 
-tests_src := a-set_test.c a-path_test.c bitmap_test.c heap_test.c buffer_test.c event_test.c flowspec_test.c bitops_test.c patmatch_test.c fletcher16_test.c slist_test.c checksum_test.c lists_test.c mac_test.c ip_test.c hash_test.c printf_test.c slab_test.c type_test.c
+tests_src := a-set_test.c a-path_test.c bitmap_test.c heap_test.c buffer_test.c event_test.c flowspec_test.c bitops_test.c patmatch_test.c fletcher16_test.c slist_test.c checksum_test.c lists_test.c mac_test.c ip_test.c hash_test.c printf_test.c slab_test.c tlists_test.c type_test.c
 tests_targets := $(tests_targets) $(tests-target-files)
 tests_objs := $(tests_objs) $(src-o-files)
diff --git a/lib/hash_test.c b/lib/hash_test.c
index ecfcdd66..30213320 100644
--- a/lib/hash_test.c
+++ b/lib/hash_test.c
@@ -61,7 +61,7 @@ dump_nodes(void)
 static void
 init_hash_(uint order)
 {
-  my_pool = rp_new(&root_pool, "Test pool");
+  my_pool = rp_new(&root_pool, the_bird_domain.the_bird, "Test pool");
 
   HASH_INIT(hash, my_pool, order);
 
diff --git a/lib/io-loop.h b/lib/io-loop.h
index 877cd5ce..80cd2ea2 100644
--- a/lib/io-loop.h
+++ b/lib/io-loop.h
@@ -17,7 +17,7 @@
 extern struct birdloop main_birdloop;
 
 /* Start a new birdloop owned by given pool and domain */
-struct birdloop *birdloop_new(pool *p, uint order, const char *name, btime max_latency);
+struct birdloop *birdloop_new(pool *p, uint order, btime max_latency, const char *fmt, ...);
 
 /* Stop the loop. At the end, the @stopped callback is called unlocked in tail
  * position to finish cleanup. Run birdloop_free() from that callback to free
@@ -31,6 +31,10 @@ event_list *birdloop_event_list(struct birdloop *loop);
 
 /* Get birdloop's time heap */
 struct timeloop *birdloop_time_loop(struct birdloop *loop);
+#define birdloop_domain(l)  (birdloop_time_loop((l))->domain)
+
+/* Get birdloop's pool */
+pool *birdloop_pool(struct birdloop *loop);
 
 /* Enter and exit the birdloop */
 void birdloop_enter(struct birdloop *loop);
diff --git a/lib/locking.h b/lib/locking.h
index 6bed14bf..751eecbd 100644
--- a/lib/locking.h
+++ b/lib/locking.h
@@ -13,8 +13,8 @@ struct domain_generic;
 
 /* Here define the global lock order; first to last. */
 struct lock_order {
-  struct domain_generic *meta;
   struct domain_generic *the_bird;
+  struct domain_generic *meta;
   struct domain_generic *control;
   struct domain_generic *proto;
   struct domain_generic *service;
diff --git a/lib/resource.c b/lib/resource.c
index 94b8d019..2071a411 100644
--- a/lib/resource.c
+++ b/lib/resource.c
@@ -46,6 +46,16 @@ static struct resclass pool_class = {
 
 pool root_pool;
 
+static void
+rp_init(pool *z, struct domain_generic *dom, const char *name)
+{
+  ASSERT_DIE(DG_IS_LOCKED(dom));
+
+  z->name = name;
+  z->domain = dom;
+  z->inside = (TLIST_LIST(resource)) {};
+}
+
 /**
  * rp_new - create a resource pool
  * @p: parent pool
@@ -55,71 +65,106 @@ pool root_pool;
  * parent pool.
  */
 pool *
-rp_new(pool *p, const char *name)
+rp_new(pool *p, struct domain_generic *dom, const char *name)
 {
   pool *z = ralloc(p, &pool_class);
-  z->name = name;
-  init_list(&z->inside);
+
+  if (dg_order(p->domain) > dg_order(dom))
+    bug("Requested reverse order pool creation: %s (%d) can't be a parent of %s (%d)",
+	domain_name(p->domain), dg_order(p->domain),
+	domain_name(dom), dg_order(dom));
+
+  if ((dg_order(p->domain) == dg_order(dom)) && (p->domain != dom))
+    bug("Requested incomparable order pool creation: %s (%d) can't be a parent of %s (%d)",
+	domain_name(p->domain), dg_order(p->domain),
+	domain_name(dom), dg_order(dom));
+
+  rp_init(z, dom, name);
   return z;
 }
 
 pool *
-rp_newf(pool *p, const char *fmt, ...)
+rp_vnewf(pool *p, struct domain_generic *dom, const char *fmt, va_list args)
 {
-  pool *z = rp_new(p, NULL);
+  pool *z = rp_new(p, dom, NULL);
+  z->name = mb_vsprintf(p, fmt, args);
+  return z;
+}
 
+pool *
+rp_newf(pool *p, struct domain_generic *dom, const char *fmt, ...)
+{
   va_list args;
   va_start(args, fmt);
-  z->name = mb_vsprintf(p, fmt, args);
+  pool *z = rp_vnewf(p, dom, fmt, args);
   va_end(args);
 
   return z;
 }
 
+#define POOL_LOCK				\
+  struct domain_generic *dom = p->domain;	\
+  int locking = !DG_IS_LOCKED(dom);		\
+  if (locking)					\
+    DG_LOCK(dom);				\
+
+#define POOL_UNLOCK if (locking) DG_UNLOCK(dom);\
+
+void rp_free(pool *p)
+{
+  ASSERT_DIE(DG_IS_LOCKED(p->domain));
+  rfree(p);
+}
 
 static void
 pool_free(resource *P)
 {
   pool *p = (pool *) P;
-  resource *r, *rr;
 
-  r = HEAD(p->inside);
-  while (rr = (resource *) r->n.next)
+  POOL_LOCK;
+  WALK_TLIST_DELSAFE(resource, r, &p->inside)
     {
       r->class->free(r);
       xfree(r);
-      r = rr;
     }
+  POOL_UNLOCK;
 }
 
+
 static void
 pool_dump(resource *P, unsigned indent)
 {
   pool *p = (pool *) P;
-  resource *r;
+
+  POOL_LOCK;
 
   debug("%s\n", p->name);
-  WALK_LIST(r, p->inside)
+  WALK_TLIST_DELSAFE(resource, r, &p->inside)
     rdump(r, indent + 3);
+
+  POOL_UNLOCK;
 }
 
 static struct resmem
 pool_memsize(resource *P)
 {
   pool *p = (pool *) P;
-  resource *r;
   struct resmem sum = {
     .effective = 0,
     .overhead = sizeof(pool) + ALLOC_OVERHEAD,
   };
 
-  WALK_LIST(r, p->inside)
+  POOL_LOCK;
+
+  WALK_TLIST(resource, r, &p->inside)
   {
     struct resmem add = rmemsize(r);
     sum.effective += add.effective;
     sum.overhead += add.overhead;
   }
 
+  POOL_UNLOCK;
+
   return sum;
 }
 
@@ -127,14 +172,25 @@ static resource *
 pool_lookup(resource *P, unsigned long a)
 {
   pool *p = (pool *) P;
-  resource *r, *q;
+  resource *q = NULL;
+
+  POOL_LOCK;
 
-  WALK_LIST(r, p->inside)
+  WALK_TLIST(resource, r, &p->inside)
     if (r->class->lookup && (q = r->class->lookup(r, a)))
-      return q;
-  return NULL;
+      break;
+
+  POOL_UNLOCK;
+  return q;
 }
 
+static pool *
+resource_parent(resource *r)
+{
+  return SKIP_BACK(pool, inside, resource_enlisted(r));
+}
+
+
 /**
  * rmove - move a resource
  * @res: resource
@@ -146,13 +202,13 @@ pool_lookup(resource *P, unsigned long a)
 void rmove(void *res, pool *p)
 {
   resource *r = res;
+  pool *orig = resource_parent(r);
 
-  if (r)
-    {
-      if (r->n.next)
-        rem_node(&r->n);
-      add_tail(&p->inside, &r->n);
-    }
+  ASSERT_DIE(DG_IS_LOCKED(orig->domain));
+  ASSERT_DIE(DG_IS_LOCKED(p->domain));
+
+  resource_rem_node(&orig->inside, r);
+  resource_add_tail(&p->inside, r);
 }
 
 /**
@@ -173,8 +229,10 @@ rfree(void *res)
   if (!r)
     return;
 
-  if (r->n.next)
-    rem_node(&r->n);
+  pool *orig = resource_parent(r);
+  ASSERT_DIE(DG_IS_LOCKED(orig->domain));
+  resource_rem_node(&orig->inside, r);
+
   r->class->free(r);
   r->class = NULL;
   xfree(r);
@@ -233,12 +291,14 @@ rmemsize(void *res)
 void *
 ralloc(pool *p, struct resclass *c)
 {
+  ASSERT_DIE(DG_IS_LOCKED(p->domain));
+
   resource *r = xmalloc(c->size);
   bzero(r, c->size);
 
   r->class = c;
-  if (p)
-    add_tail(&p->inside, &r->n);
+  resource_add_tail(&p->inside, r);
+
   return r;
 }
 
@@ -278,28 +338,29 @@ resource_init(void)
   rcu_init();
   resource_sys_init();
 
-  root_pool.r.class = &pool_class;
-  root_pool.name = "Root";
-  init_list(&root_pool.inside);
-  tmp_init(&root_pool);
+  rp_init(&root_pool, the_bird_domain.the_bird, "Root");
+  tmp_init(&root_pool, the_bird_domain.the_bird);
 }
 
 _Thread_local struct tmp_resources tmp_res;
 
 void
-tmp_init(pool *p)
+tmp_init(pool *p, struct domain_generic *dom)
 {
   tmp_res.lp = lp_new_default(p);
   tmp_res.parent = p;
-  tmp_res.pool = rp_new(p, "TMP");
+  tmp_res.pool = rp_new(p, dom, "TMP");
+  tmp_res.domain = dom;
 }
 
 void
 tmp_flush(void)
 {
+  ASSERT_DIE(DG_IS_LOCKED(tmp_res.domain));
+
   lp_flush(tmp_linpool);
-  rfree(tmp_res.pool);
-  tmp_res.pool = rp_new(tmp_res.parent, "TMP");
+  rp_free(tmp_res.pool);
+  tmp_res.pool = rp_new(tmp_res.parent, tmp_res.domain, "TMP");
 }
 
 
@@ -379,11 +440,13 @@ static struct resclass mb_class = {
 void *
 mb_alloc(pool *p, unsigned size)
 {
+  ASSERT_DIE(DG_IS_LOCKED(p->domain));
+
   struct mblock *b = xmalloc(sizeof(struct mblock) + size);
 
   b->r.class = &mb_class;
-  b->r.n = (node) {};
-  add_tail(&p->inside, &b->r.n);
+  b->r.n = (struct resource_node) {};
+  resource_add_tail(&p->inside, &b->r);
   b->size = size;
   return b->data;
 }
@@ -428,10 +491,14 @@ void *
 mb_realloc(void *m, unsigned size)
 {
   struct mblock *b = SKIP_BACK(struct mblock, data, m);
+  struct pool *p = resource_parent(&b->r);
+
+  ASSERT_DIE(DG_IS_LOCKED(p->domain));
 
   b = xrealloc(b, sizeof(struct mblock) + size);
-  update_node(&b->r.n);
   b->size = size;
+
+  resource_update_node(&p->inside, &b->r);
   return b->data;
 }
 
@@ -449,7 +516,7 @@ mb_free(void *m)
     return;
 
   struct mblock *b = SKIP_BACK(struct mblock, data, m);
-  rfree(b);
+  rfree(&b->r);
 }
 
 
diff --git a/lib/resource.h b/lib/resource.h
index 911b990d..810334c1 100644
--- a/lib/resource.h
+++ b/lib/resource.h
@@ -10,7 +10,10 @@
 #ifndef _BIRD_RESOURCE_H_
 #define _BIRD_RESOURCE_H_
 
-#include "lib/lists.h"
+#include "lib/locking.h"
+#include "lib/tlists.h"
+
+#include <stdarg.h>
 
 struct resmem {
   size_t effective;			/* Memory actually used for data storage */
@@ -19,11 +22,20 @@ struct resmem {
 
 /* Resource */
 
+#define TLIST_PREFIX resource
+#define TLIST_TYPE struct resource
+#define TLIST_ITEM n
+#define TLIST_WANT_WALK
+#define TLIST_WANT_ADD_TAIL
+#define TLIST_WANT_UPDATE_NODE
+
 typedef struct resource {
-  node n;				/* Inside resource pool */
-  struct resclass *class;		/* Resource class */
+  TLIST_DEFAULT_NODE;			/* Inside resource pool */
+  const struct resclass *class;		/* Resource class */
 } resource;
 
+#include "lib/tlists.h"
+
 /* Resource class */
 
 struct resclass {
@@ -42,14 +54,13 @@ struct resclass {
 
 typedef struct pool {
   resource r;
-  list inside;
+  TLIST_LIST(resource) inside;
+  struct domain_generic *domain;
   const char *name;
 } pool;
 
 
 void resource_init(void);
-pool *rp_new(pool *, const char *);	/* Create new pool */
-pool *rp_newf(pool *, const char *, ...);	/* Create a new pool with a formatted string as its name */
 void rfree(void *);			/* Free single resource */
 void rdump(void *, unsigned indent);	/* Dump to debug output */
 struct resmem rmemsize(void *res);		/* Return size of memory used by the resource */
@@ -58,6 +69,11 @@ void rmove(void *, pool *);		/* Move to a different pool */
 
 void *ralloc(pool *, struct resclass *);
 
+pool *rp_new(pool *, struct domain_generic *, const char *);		/* Create a new pool */
+pool *rp_newf(pool *, struct domain_generic *, const char *, ...);	/* Create a new pool with a formatted string as its name */
+pool *rp_vnewf(pool *, struct domain_generic *, const char *, va_list);	/* Create a new pool with a formatted string as its name */
+void rp_free(pool *p);							/* Free the whole pool */
+
 extern pool root_pool;
 
 /* Normal memory blocks */
@@ -88,6 +104,7 @@ void lp_restore(linpool *m, lp_state *p);	/* Restore state */
 struct tmp_resources {
   pool *pool, *parent;
   linpool *lp;
+  struct domain_generic *domain;
 };
 
 extern _Thread_local struct tmp_resources tmp_res;
@@ -97,7 +114,7 @@ extern _Thread_local struct tmp_resources tmp_res;
 #define tmp_allocu(sz)	lp_allocu(tmp_linpool, sz)
 #define tmp_allocz(sz)	lp_allocz(tmp_linpool, sz)
 
-void tmp_init(pool *p);
+void tmp_init(pool *p, struct domain_generic *dg);
 void tmp_flush(void);
 
 
@@ -111,6 +128,7 @@ slab *sl_new(pool *, unsigned size);
 void *sl_alloc(slab *);
 void *sl_allocz(slab *);
 void sl_free(void *);
+void sl_delete(slab *);
 
 /*
  * Low-level memory allocation functions, please don't use
diff --git a/lib/socket.h b/lib/socket.h
index 4b169581..6225977b 100644
--- a/lib/socket.h
+++ b/lib/socket.h
@@ -88,6 +88,7 @@ sock *sock_new(pool *);			/* Allocate new socket */
 
 int sk_open(sock *, struct birdloop *);		/* Open socket */
 void sk_reloop(sock *, struct birdloop *);	/* Move socket to another loop. Both loops must be locked. */
+static inline void sk_close(sock *s) { rfree(&s->r); }	/* Explicitly close socket */
 
 int sk_rx_ready(sock *s);
 _Bool sk_tx_pending(sock *s);
diff --git a/lib/tlists.h b/lib/tlists.h
index 1437e17e..d7f1cf03 100644
--- a/lib/tlists.h
+++ b/lib/tlists.h
@@ -79,19 +79,27 @@ typedef struct TLIST_LIST_STRUCT {
   TLIST_TYPE *last;
 } TLIST_LIST_STRUCT;
 
+static inline struct TLIST_LIST_STRUCT * TLIST_NAME(enlisted)(TLIST_TYPE *node)
+{
+  return node->TLIST_ITEM.list;
+}
+
 #ifdef TLIST_WANT_WALK
 static inline struct TLIST_NAME(node) * TLIST_NAME(node_get)(TLIST_TYPE *node)
 { return &(node->TLIST_ITEM); }
 #endif
 
-#ifdef TLIST_WANT_ADD_HEAD
+#if defined(TLIST_WANT_ADD_HEAD) || defined(TLIST_WANT_ADD_AFTER)
 static inline void TLIST_NAME(add_head)(TLIST_LIST_STRUCT *list, TLIST_TYPE *node)
 {
-  ASSERT_DIE(!node->TLIST_ITEM.prev && !node->TLIST_ITEM.next);
+  ASSERT_DIE(!TLIST_NAME(enlisted)(node));
+  node->TLIST_ITEM.list = list;
+
   if (node->TLIST_ITEM.next = list->first)
     list->first->TLIST_ITEM.prev = node;
   else
     list->last = node;
+
   list->first = node;
 }
 #endif
@@ -99,17 +107,65 @@ static inline void TLIST_NAME(add_head)(TLIST_LIST_STRUCT *list, TLIST_TYPE *nod
 #ifdef TLIST_WANT_ADD_TAIL
 static inline void TLIST_NAME(add_tail)(TLIST_LIST_STRUCT *list, TLIST_TYPE *node)
 {
-  ASSERT_DIE(!node->TLIST_ITEM.prev && !node->TLIST_ITEM.next);
+  ASSERT_DIE(!TLIST_NAME(enlisted)(node));
+  node->TLIST_ITEM.list = list;
+
   if (node->TLIST_ITEM.prev = list->last)
     list->last->TLIST_ITEM.next = node;
   else
     list->first = node;
+
   list->last = node;
 }
 #endif
 
+#ifdef TLIST_WANT_UPDATE_NODE
+static inline void TLIST_NAME(update_node)(TLIST_LIST_STRUCT *list, TLIST_TYPE *node)
+{
+  ASSERT_DIE(TLIST_NAME(enlisted)(node) == list);
+
+  if (node->TLIST_ITEM.prev)
+    node->TLIST_ITEM.prev->TLIST_ITEM.next = node;
+  else
+    list->first = node;
+
+  if (node->TLIST_ITEM.next)
+    node->TLIST_ITEM.next->TLIST_ITEM.prev = node;
+  else
+    list->last = node;
+}
+#endif
+
+#ifdef TLIST_WANT_ADD_AFTER
+static inline void TLIST_NAME(add_after)(TLIST_LIST_STRUCT *list, TLIST_TYPE *node, TLIST_TYPE *after)
+{
+  ASSERT_DIE(!TLIST_NAME(enlisted)(node));
+
+  /* Adding to beginning */
+  if (!(node->TLIST_ITEM.prev = after))
+    return TLIST_NAME(add_head)(list, node);
+
+  /* OK, Adding after a real node */
+  node->TLIST_ITEM.list = list;
+
+  /* There is another node after the anchor */
+  if (node->TLIST_ITEM.next = after->TLIST_ITEM.next)
+    /* Link back */
+    node->TLIST_ITEM.next->TLIST_ITEM.prev = node;
+  else
+    /* Or we are adding the last node */
+    list->last = node;
+
+  /* Link forward from "after" */
+  after->TLIST_ITEM.next = node;
+}
+#endif
+
+
 static inline void TLIST_NAME(rem_node)(TLIST_LIST_STRUCT *list, TLIST_TYPE *node)
 {
+  ASSERT_DIE(TLIST_NAME(enlisted)(node) == list);
+
   if (node->TLIST_ITEM.prev)
     node->TLIST_ITEM.prev->TLIST_ITEM.next = node->TLIST_ITEM.next;
   else
@@ -127,6 +183,7 @@ static inline void TLIST_NAME(rem_node)(TLIST_LIST_STRUCT *list, TLIST_TYPE *nod
   }
 
   node->TLIST_ITEM.next = node->TLIST_ITEM.prev = NULL;
+  node->TLIST_ITEM.list = NULL;
 }
 
 #undef TLIST_PREFIX
@@ -136,6 +193,7 @@ static inline void TLIST_NAME(rem_node)(TLIST_LIST_STRUCT *list, TLIST_TYPE *nod
 #undef TLIST_ITEM
 #undef TLIST_WANT_ADD_HEAD
 #undef TLIST_WANT_ADD_TAIL
+#undef TLIST_WANT_UPDATE_NODE
 
 # endif
 #else
@@ -147,12 +205,12 @@ static inline void TLIST_NAME(rem_node)(TLIST_LIST_STRUCT *list, TLIST_TYPE *nod
 #error "You should first include lib/tlists.h without requesting a TLIST"
 #endif
 
-#define TLIST_NODE_CONTENTS(_type)	{ _type *next; _type *prev; }
-#define TLIST_NODE(_name, _type)	struct _name##_node TLIST_NODE_CONTENTS(_type) 
-#define TLIST_DEFAULT_NODE		struct MACRO_CONCAT_AFTER(TLIST_PREFIX,_node) \
-					TLIST_NODE_CONTENTS(TLIST_TYPE) TLIST_ITEM
+#define TLIST_LIST(_name)		struct _name##_list
 
-#define TLIST_LIST(_name)		struct _name##_list 
+#define TLIST_NODE_IN(_name, _type)	{ _type *next; _type *prev; TLIST_LIST(_name) *list; }
+#define TLIST_NODE(_name, _type)	struct _name##_node TLIST_NODE_IN(_name, _type)
+#define TLIST_DEFAULT_NODE		struct MACRO_CONCAT_AFTER(TLIST_PREFIX,_node) \
+					TLIST_NODE_IN(TLIST_PREFIX,TLIST_TYPE) TLIST_ITEM
 
 
 /* Use ->first and ->last to access HEAD and TAIL */
diff --git a/lib/tlists_test.c b/lib/tlists_test.c
new file mode 100644
index 00000000..8ba080a6
--- /dev/null
+++ b/lib/tlists_test.c
@@ -0,0 +1,314 @@
+/*
+ *	BIRD Library -- Linked Lists Tests
+ *
+ *	(c) 2015 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include "test/birdtest.h"
+#include "lib/tlists.h"
+
+#define TLIST_PREFIX tp
+#define TLIST_TYPE struct test_node
+#define TLIST_ITEM n
+#define TLIST_WANT_ADD_HEAD
+#define TLIST_WANT_ADD_TAIL
+#define TLIST_WANT_ADD_AFTER
+#define TLIST_WANT_UPDATE_NODE
+
+struct test_node {
+  TLIST_DEFAULT_NODE;
+};
+
+#include "lib/tlists.h"
+
+#define MAX_NUM 1000
+
+static struct test_node nodes[MAX_NUM];
+static TLIST_LIST(tp) l;
+
+static void
+show_list(void)
+{
+  bt_debug("\n");
+  bt_debug("list.first points to %p\n", l.first);
+  bt_debug("list.last  points to %p\n", l.last);
+
+  int i;
+  for (i = 0; i < MAX_NUM; i++)
+  {
+    bt_debug("n[%3i] is at %p\n", i, &nodes[i]);
+    bt_debug("  prev is at %p and point to %p\n", &(nodes[i].n.prev), nodes[i].n.prev);
+    bt_debug("  next is at %p and point to %p\n", &(nodes[i].n.next), nodes[i].n.next);
+  }
+}
+
+static int
+is_filled_list_well_linked(void)
+{
+  int i;
+  bt_assert(l.first == &nodes[0]);
+  bt_assert(l.last == &nodes[MAX_NUM-1]);
+  bt_assert(!nodes[0].n.prev);
+  bt_assert(!nodes[MAX_NUM-1].n.next);
+
+  for (i = 0; i < MAX_NUM; i++)
+  {
+    bt_assert(nodes[i].n.list == &l);
+
+    if (i < (MAX_NUM-1))
+      bt_assert(nodes[i].n.next == &nodes[i+1]);
+
+    if (i > 0)
+      bt_assert(nodes[i].n.prev == &nodes[i-1]);
+  }
+
+  return 1;
+}
+
+static int
+is_empty_list_well_unlinked(void)
+{
+  int i;
+
+  bt_assert(!l.first);
+  bt_assert(!l.last);
+  bt_assert(EMPTY_TLIST(tp, &l));
+
+  for (i = 0; i < MAX_NUM; i++)
+  {
+    bt_assert(nodes[i].n.next == NULL);
+    bt_assert(nodes[i].n.prev == NULL);
+    bt_assert(nodes[i].n.list == NULL);
+  }
+
+  return 1;
+}
+
+static void
+init_list__(TLIST_LIST(tp) *l, struct test_node nodes[])
+{
+  *l = (TLIST_LIST(tp)) {};
+
+  int i;
+  for (i = 0; i < MAX_NUM; i++)
+  {
+    nodes[i].n.next = NULL;
+    nodes[i].n.prev = NULL;
+    nodes[i].n.list = NULL;
+  }
+}
+
+static void
+init_list_(void)
+{
+  init_list__(&l, nodes);
+}
+
+static int
+t_add_tail(void)
+{
+  int i;
+
+  init_list_();
+  for (i = 0; i < MAX_NUM; i++)
+  {
+    tp_add_tail(&l, &nodes[i]);
+    bt_debug(".");
+    bt_assert(l.last == &nodes[i]);
+    bt_assert(l.first == &nodes[0]);
+
+    bt_assert(nodes[i].n.list == &l);
+    bt_assert(!nodes[i].n.next);
+
+    if (i > 0)
+    {
+      bt_assert(nodes[i-1].n.next == &nodes[i]);
+      bt_assert(nodes[i].n.prev == &nodes[i-1]);
+    }
+  }
+  show_list();
+  bt_assert(is_filled_list_well_linked());
+
+  return 1;
+}
+
+static int
+t_add_head(void)
+{
+  int i;
+
+  init_list_();
+  for (i = MAX_NUM-1; i >= 0; i--)
+  {
+    tp_add_head(&l, &nodes[i]);
+    bt_debug(".");
+    bt_assert(l.first == &nodes[i]);
+    bt_assert(l.last == &nodes[MAX_NUM-1]);
+    if (i < MAX_NUM-1)
+    {
+      bt_assert(nodes[i+1].n.prev == &nodes[i]);
+      bt_assert(nodes[i].n.next == &nodes[i+1]);
+    }
+  }
+  show_list();
+  bt_assert(is_filled_list_well_linked());
+
+  return 1;
+}
+
+static void
+insert_node_(TLIST_LIST(tp) *l, struct test_node *n, struct test_node *after)
+{
+  tp_add_after(l, n, after);
+  bt_debug(".");
+}
+
+static int
+t_insert_node(void)
+{
+  int i;
+
+  init_list_();
+
+  // add first node
+  insert_node_(&l, &nodes[0], NULL);
+
+  // add odd nodes
+  for (i = 2; i < MAX_NUM; i+=2)
+    insert_node_(&l, &nodes[i], &nodes[i-2]);
+
+  // add even nodes
+  for (i = 1; i < MAX_NUM; i+=2)
+    insert_node_(&l, &nodes[i], &nodes[i-1]);
+
+  bt_debug("\n");
+  bt_assert(is_filled_list_well_linked());
+
+  return 1;
+}
+
+static void
+fill_list2(TLIST_LIST(tp) *l, struct test_node nodes[])
+{
+  int i;
+  for (i = 0; i < MAX_NUM; i++)
+    tp_add_tail(l, &nodes[i]);
+}
+
+static void
+fill_list(void)
+{
+  fill_list2(&l, nodes);
+}
+
+static int
+t_remove_node(void)
+{
+  int i;
+
+  init_list_();
+
+  /* Fill & Remove & Check */
+  fill_list();
+  for (i = 0; i < MAX_NUM; i++)
+    tp_rem_node(&l, &nodes[i]);
+  bt_assert(is_empty_list_well_unlinked());
+
+  /* Fill & Remove the half of nodes & Check & Remove the rest nodes & Check */
+  fill_list();
+  for (i = 0; i < MAX_NUM; i+=2)
+    tp_rem_node(&l, &nodes[i]);
+
+  int tail_node_index = (MAX_NUM % 2) ? MAX_NUM - 2 : MAX_NUM - 1;
+  bt_assert(l.first == &nodes[1]);
+  bt_assert(l.last == &nodes[tail_node_index]);
+  bt_assert(!nodes[tail_node_index].n.next);
+
+  for (i = 1; i < MAX_NUM; i+=2)
+  {
+    if (i > 1)
+      bt_assert(nodes[i].n.prev == &nodes[i-2]);
+    if (i < tail_node_index)
+      bt_assert(nodes[i].n.next == &nodes[i+2]);
+  }
+
+  for (i = 1; i < MAX_NUM; i+=2)
+    tp_rem_node(&l, &nodes[i]);
+  bt_assert(is_empty_list_well_unlinked());
+
+  return 1;
+}
+
+static int
+t_update_node(void)
+{
+  struct test_node head, inside, tail;
+
+  init_list_();
+  fill_list();
+
+  head = nodes[0];
+  tp_update_node(&l, &head);
+  bt_assert(l.first == &head);
+  bt_assert(head.n.prev == NULL);
+  bt_assert(head.n.next == &nodes[1]);
+  bt_assert(nodes[1].n.prev == &head);
+
+  inside = nodes[MAX_NUM/2];
+  tp_update_node(&l, &inside);
+  bt_assert(nodes[MAX_NUM/2-1].n.next == &inside);
+  bt_assert(nodes[MAX_NUM/2+1].n.prev == &inside);
+  bt_assert(inside.n.prev == &nodes[MAX_NUM/2-1]);
+  bt_assert(inside.n.next == &nodes[MAX_NUM/2+1]);
+
+  tail = nodes[MAX_NUM-1];
+  tp_update_node(&l, &tail);
+  bt_assert(l.last == &tail);
+  bt_assert(tail.n.prev == &nodes[MAX_NUM-2]);
+  bt_assert(tail.n.next == NULL);
+  bt_assert(nodes[MAX_NUM-2].n.next == &tail);
+
+  return 1;
+}
+
+#if 0
+static int
+t_add_tail_list(void)
+{
+  node nodes2[MAX_NUM];
+  list l2;
+
+  init_list__(&l, (node *) nodes);
+  fill_list2(&l, (node *) nodes);
+
+  init_list__(&l2, (node *) nodes2);
+  fill_list2(&l2, (node *) nodes2);
+
+  add_tail_list(&l, &l2);
+
+  bt_assert(nodes[MAX_NUM-1].next == &nodes2[0]);
+  bt_assert(nodes2[0].prev == &nodes[MAX_NUM-1]);
+  bt_assert(l.tail == &nodes2[MAX_NUM-1]);
+
+  return 1;
+}
+#endif
+
+int
+main(int argc, char *argv[])
+{
+  bt_init(argc, argv);
+
+  bt_test_suite(t_add_tail, "Adding nodes to tail of list");
+  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_update_node, "Updating nodes in list");
+#if 0
+  bt_test_suite(t_add_tail_list, "At the tail of a list adding the another list");
+#endif
+
+  return bt_exit_value();
+}