Pthreads infrastructure -- initial commit

New files: lib/qpthreads.c & .h

  Encapsulates the Pthreads facilities to be used in Quagga.

  Implicitly documents the sub-set of Pthreads being used.

  Provides error checking for a number of functions which may return
  errors, but are not generally expected to and for whom an error is
  treated as fatal.

  Could be modified to "null out" the use of Pthreads.

New files: lib/qtime.c & .h

  Defines a 64-bit integer time value which is a lot easier to
  handle than the usual timespec and timeval structures.  (C99
  requires a 64-bit integer.)

  Provides front ends for gettimeofday() & clock_gettime() which
  return 64-bit time value.  Also conversions to and from timespec and
  timeval.

  Provides a monotonic clock for when CLOCK_MONOTONIC is not available.
  (This is based on code from Joakim Tjernlund.)

New files: lib/heap.c  & .h

  Implements a heap data structure closely allied to the vector.

  This will be used for timer handling.

Modified: lib/memtypes.c

  New memory types for qpthreads structures and for the heap.

Modified: lib/zassert.h

  Added explicit "passert" == assert which is not subject to NDEBUG.

  Added explicit "nassert" == assert which is subject to NDEBUG.

  Added zabort, zabort_errno and zabbort_err for when something has
  gone fatally wrong.  (Require changes to lib/log.c which are TBD.)

9 files changed, 1818 insertions, 5 deletions

diff --git a/lib/Makefile.am b/lib/Makefile.am
index f655ac39..08f834ae 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -12,7 +12,8 @@ libzebra_la_SOURCES = \
 	sockunion.c prefix.c thread.c if.c memory.c buffer.c table.c hash.c \
 	filter.c routemap.c distribute.c stream.c str.c log.c plist.c \
 	zclient.c sockopt.c smux.c md5.c if_rmap.c keychain.c privs.c \
-	sigevent.c pqueue.c jhash.c memtypes.c workqueue.c symtab.c
+	sigevent.c pqueue.c jhash.c memtypes.c workqueue.c symtab.c heap.c \
+	qtime.c qpthreads.c
 
 BUILT_SOURCES = memtypes.h route_types.h
 
@@ -27,7 +28,8 @@ pkginclude_HEADERS = \
 	str.h stream.h table.h thread.h vector.h version.h vty.h zebra.h \
 	plist.h zclient.h sockopt.h smux.h md5.h if_rmap.h keychain.h \
 	privs.h sigevent.h pqueue.h jhash.h zassert.h memtypes.h \
-	workqueue.h route_types.h symtab.h
+	workqueue.h route_types.h symtab.h heap.h \
+	qtime.h qpthreads.h
 
 EXTRA_DIST = regex.c regex-gnu.h memtypes.awk route_types.awk route_types.txt
 
diff --git a/lib/heap.c b/lib/heap.c
new file mode 100644
index 00000000..63e3fe75
--- /dev/null
+++ b/lib/heap.c
@@ -0,0 +1,504 @@
+/* Generic heap data structure -- functions.
+ * Copyright (C) 2009 Chris Hall (GMCH), Highwayman
+ *
+ * This file is part of GNU Zebra.
+ *
+ * GNU Zebra is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2, or (at your option) any
+ * later version.
+ *
+ * GNU Zebra is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Zebra; see the file COPYING.  If not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ * 02111-1307, USA.
+ */
+
+#include <zebra.h>
+
+#include "heap.h"
+#include "memory.h"
+
+/* Heaps are implemented as a structure which includes a vector structure.
+ * So items in the heap are items in a vector, which are pointers to the item
+ * values.
+ *
+ * The heap structure may be statically allocated, embedded in another
+ * structure, or allocated dynamically.  In any case the heap operations
+ * require the address of the heap structure -- see typedef for heap.
+ *
+ * An essential component of a heap is its comparison function.  So, cannot
+ * use a heap before it has been initialised and the comparison function set.
+ * (This is unlike a vector, which may be implicitly initialised empty by
+ * zeroizing the vector structure.)
+ *
+ * Items may be pushed onto or popped off the heap, which is organised so that
+ * the top item has the smallest value -- according to the heap's comparison
+ * function.  (For equal values, the order is undefined.)
+ *
+ * The top item in the heap may be examined, and its value may be updated.
+ * (Updating the top item is more efficient than popping and then pushing it.)
+ *
+ * Items may be deleted from the heap.  Items may have their value updated
+ * while they are in the heap.  Both of these operations cause the heap to be
+ * reorganised to maintain the heap's partial ordering.  Note: these operations
+ * require knowledge of where in the heap the item is -- which, by default, is
+ * done by a linear scan of the heap.  For large heaps, there is the option to
+ * keep a "backlink" from the item to it's heap position.
+ *
+ * Vectors may be pushed onto a heap -- copying or moving the contents.
+ *
+ * Heaps may popped to a vector -- copying or moving the contents.  The
+ * resulting vector is fully sorted.
+ *
+ * ----------------------------
+ * Comparison function for heap.
+ *
+ *   int heap_cmp(...** a, ...**) ...
+ *
+ * Must return -1, 0, +1 : where -1 => a < b, 0 => a == b & +1 => a > b
+ *
+ * Heap will sort "smallest" to the top.  If you want the biggest at the top,
+ * return -1 * usual comparison.  Note that the effective heap ordering for
+ * equal values is, essentially, random.
+ *
+ * NB: like other comparison functions (cf qsort) the parameters are pointers
+ *     to pointers to the value.
+ *
+ * NB: there should never be NULL items in the heap.
+ */
+
+/* Forward reference the mechanics.	*/
+static void heap_bubble(heap h, vector_index i, p_vector_item p_v) ;
+static void heap_bubble_up(heap h, vector_index i, p_vector_item p_v);
+static void heap_bubble_down(heap h, vector_index i, p_vector_item p_v)  ;
+
+/*==============================================================================
+ * Initialisation, allocation, reset etc.
+ */
+
+static heap
+heap_setup(heap h, int new_vector, vector_index size, heap_cmp* cmp,
+                                int with_backlink, unsigned int backlink_offset)
+{
+  assert(cmp != NULL) ;         /* or there will be tears */
+
+  h->cmp   = cmp ;
+  h->state = with_backlink ? Heap_Has_Backlink : 0 ;
+  h->backlink_offset = backlink_offset ;
+
+  if (new_vector)
+    vector_init_new(&h->v, size) ;
+  else
+    vector_re_init(&h->v, size) ;
+
+  return h ;
+} ;
+
+/* Initialize heap.
+ *
+ * Allocates heap structure if none given.
+ * Does not allocate the underlying vector if the heap is initialised empty.
+ *
+ * eg:
+ *
+ *  ... = heap_new_init_simple(NULL, 0, (heap_cmp*)my_cmp)
+ *
+ * NB: when initialising an existing heap structure it is ESSENTIAL that
+ *     any previous heap and its contents have been released, because this
+ *     function simply discards whatever was there before.  (This function may
+ *     be called to initialise a heap structure which has never been
+ *     initialised.)
+ *
+ * Backlink:
+ *
+ *   The heap_delete_item and heap_update_item functions need the heap
+ *   position of the item.  The default way of finding that is to scan the
+ *   underlying heap array, looking for the address of the item.
+ *
+ *   If either of these functions is done often and on large heaps, it is
+ *   possible to speed this up by implementing a 'backlink'.  This requires
+ *   a field of type heap_backlink_t in the item structure, and it is the
+ *   offset of that which must be initialised here, eg:
+ *
+ *     ... = heap_new_init_backlink(NULL, 0, (heap_cmp*)my_cmp,
+ *     				offset_of(struct xxx_heap_item, backlink)) ;
+ *
+ *   This adds a little extra work to every change in the heap -- keeping the
+ *   backlink of any moved item up to date.  But avoids a linear search for
+ *   every heap_delete_item or heap_update_item.
+ */
+heap
+heap_init_new(heap h, vector_index size, heap_cmp* cmp,
+                                int with_backlink, unsigned int backlink_offset)
+{
+  if (h == NULL)
+    h = XCALLOC(MTYPE_HEAP, sizeof(struct heap)) ;
+  else
+    memset(h, 0, sizeof(struct heap)) ;
+
+  return heap_setup(h, 1, size, cmp, with_backlink, backlink_offset) ;
+} ;
+
+/* Re-Initialize heap (or create a new one, if h == NULL).
+ *
+ * Allocates heap structure if none given -- allocating vector if size != 0.
+ * Otherwise, re-initialise the heap and any vector (reusing its memory).
+ *
+ * NB: when re-initialising an existing heap it is the caller's
+ *     responsibility to release any item values *before* doing this.
+ */
+heap
+heap_re_init(heap h, vector_index size, heap_cmp* cmp,
+                                int with_backlink, unsigned int backlink_offset)
+{
+  if (h == NULL)
+    return heap_init_new(h, size, cmp, with_backlink, backlink_offset) ;
+  else
+    return heap_setup(h, 0, size, cmp, with_backlink, backlink_offset) ;
+} ;
+
+/* Release heap contents (underlying vector), and (if required) release the
+ * heap structure.
+ *
+ * Return NULL if releases heap, otherwise the address of the heap.
+ *
+ * If does not release the heap, it retains the comparison function and any
+ * backlink setting -- so heap can be reused without reinitialising it.
+ *
+ * NB: it is the callers responsibility to release any heap item values
+ *     *before* doing this.
+ */
+heap
+heap_reset(heap h, int free_structure)
+{
+  vector_reset(&h->v, 0) ;
+
+  if (free_structure)
+    {
+      XFREE(MTYPE_VECTOR, h) ;
+      return NULL ;
+    } ;
+
+  return h ;
+} ;
+
+/* Remove last item from heap.
+ *
+ * If heap is empty, release the underlying vector, and (if required) release
+ * the heap structure.
+ *
+ * Useful for emptying out and discarding a heap:
+ *
+ *     while ((p_v = heap_ream_out(v, 1)))
+ *       ... do what's required to release the item p_v
+ *
+ * Returns NULL when heap is empty.
+ *
+ * If does not release the heap, it retains the comparison function and any
+ * backlink setting -- so heap can be reused without reinitialising it.
+ *
+ * NB: by 'last' this does NOT mean last according to the heap ordering,
+ *     it just means last in the underlying vector -- which won't be the
+ *     first in heap order (unless heap contains only one item).
+ */
+p_vector_item
+heap_ream(heap h, int free_structure)
+{
+  p_vector_item p_v ;
+
+  if (h == NULL)
+    return NULL ;
+
+  if ((p_v = vector_ream_keep(&h->v)) == NULL)
+    heap_reset(h, free_structure) ;
+
+  return p_v ;
+} ;
+
+/*==============================================================================
+ * Simple Heap Operations
+ */
+
+/* Push given item onto the heap                                          */
+void
+heap_push_item(heap h, p_vector_item p_v)
+{
+  assert(p_v) ;	 /* no NULLs, thank you.  */
+  heap_bubble_up(h, vector_extend_by_1(&h->v), p_v) ;
+} ;
+
+/* Pop item off the heap.
+ *
+ * Returns NULL if heap is empty.
+ */
+p_vector_item
+heap_pop_item(heap h)
+{
+  p_vector_item p_v ;
+  p_vector_item p_x ;
+
+  p_x = vector_pop_item(&h->v) ;  /* extract last item, if any 	        */
+  if (h->v.end == 0)
+    return p_x ;                  /* done if last was also first        */
+
+  p_v = h->v.p_items[0] ;	  /* this is what we are popping	*/
+
+  heap_bubble_down(h, 0, p_x) ;	  /* reposition what was the last item	*/
+				  /* updating any backlink		*/
+  return p_v ;
+} ;
+
+/* Get address of top item on heap.  Re-establish heap order if required.
+ *
+ * Returns NULL if heap is empty.
+ */
+p_vector_item
+heap_top_item(heap h)
+{
+  return vector_get_first_item(&h->v) ;  /* if any */
+} ;
+
+/* Update heap to reflect new value of top item.        */
+void
+heap_update_top_item(heap h)
+{
+  heap_bubble_down(h, 0, vector_get_first_item(&h->v)) ;
+} ;
+
+/*==============================================================================
+ * Heap Operations which use 'backlink', if implemented.
+ */
+
+static vector_index heap_find_item(heap h, p_vector_item) ;
+
+/* Delete given item from the heap.
+ *
+ * See notes on backlink, above.
+ *
+ * NB: do NOT try this on items which are not in the given heap !
+ */
+void
+heap_delete_item(heap h, p_vector_item p_v)
+{
+  p_vector_item p_x ;
+  vector_index i ;
+
+  i = heap_find_item(h, p_v) ;
+
+  p_x = vector_pop_item(&h->v) ;  /* extract last item, if any 		*/
+
+  if (i == h->v.end)
+    return ;			  /* stop now if deleting last item	*/
+
+  heap_bubble(h, i, p_x) ;	  /* move what was last into position	*/
+				  /* updating any backlink		*/
+} ;
+
+/* Update heap to reflect new value of given item.
+ *
+ * See notes on backlink, above.
+ */
+void heap_update_item(heap h, p_vector_item p_v)
+{
+  heap_bubble(h, heap_find_item(h, p_v), p_v) ;
+} ;
+
+/*==============================================================================
+ * Other Heap Operations.
+ */
+
+/* Push entire vector onto heap copying or moving items as required.
+ *
+ * Copy or move vector to end of heap's vector, then move each
+ * (non-NULL) item into heap order.
+ */
+void
+heap_push_vector(heap h, vector v, int move_vector)
+{
+  vector_index i = h->v.end ;
+  vector_index e ;
+  vector_index n = v->end ;
+
+  if (move_vector)
+    vector_move_append(&h->v, v) ;
+  else
+    vector_copy_append(&h->v, v) ;
+
+  e = i ;                           /* old end of the heap.     */
+  while (n--) {
+    p_vector_item p_v = h->v.p_items[i++] ;
+    if (p_v != NULL)
+      heap_bubble_up(h, e++, p_v) ; /* move new item into position in heap  */
+                                    /* setting any backlink                 */
+  } ;
+
+  h->v.end = e ;                    /* new end of heap          */
+} ;
+
+/* Pop given heap to vector -- creating vector if required (v == NULL).
+ *
+ * Resulting vector is fully sorted.
+ *
+ * Moves or copies the contents of the heap.
+ *
+ * NB: when creating new vector, will be exactly the required size.
+ *
+ * NB: if re-initialising existing vector, it is the caller's responsibility
+ *     to release any existing items if that is required.
+ *
+ * NB: if re-initialising existing vector, it is the caller's responsibility
+ *     to ensure the vector structure is currently valid.
+*/
+
+vector
+heap_pop_vector(vector v, heap h, int move_heap)
+{
+  vector_index n = h->v.end ;
+  vector_index i ;
+
+  v = vector_re_init(v, n) ;
+  v->end = n ;
+
+  for (i = 0 ; i < n ; i++)
+    v->p_items[i] = heap_pop_item(h) ;
+
+  if (!move_heap)
+    vector_copy_here(&h->v, v) ;  /* fully sorted is also heap ordered ! */
+
+  return v ;
+} ;
+
+/*==============================================================================
+ * The Heap internal mechanics.
+ */
+
+/* Returns pointer to backlink value in heap item: lvalue or rvalue	*/
+#define HEAP_BACKLINK(h, p_v) \
+  *(heap_backlink_t*)((char*)(p_v) + (h)->backlink_offset)
+/* Sets backlink, if required.						*/
+#define heap_set_backlink(h, p_v, i) \
+  if ((h)->state & Heap_Has_Backlink) HEAP_BACKLINK(h, p_v) = (i)
+
+/* Returns index of parent.		*/
+#define HEAP_UP(i)   (((i) * 2) + 1)
+/* Returns index of left child.		*/
+#define HEAP_DOWN(i) (((i) - 1) / 2)
+
+/* Insert given item in the required place in heap, given that there is now
+ * a hole at the given position -- may move up or down the heap, or stay put.
+ *
+ * Bubbles up or down as required.
+ *
+ * Note that this sets the backlink on the given item.
+ */
+static void
+heap_bubble(heap h, vector_index i, p_vector_item p_v)
+{
+  /* If this is < parent, we bubble upwards.	*/
+  if ((i != 0) && (h->cmp(&p_v, &h->v.p_items[HEAP_UP(i)]) < 0))
+    heap_bubble_up(h, i, p_v) ;
+  /* Otherwise we try bubbling downwards.       */
+  else
+    heap_bubble_down(h, i, p_v) ;
+} ;
+
+/* Insert given item in the required place in heap, given that there is now
+ * a hole at the given position -- where we know may *only* move up the heap.
+ *
+ * Note that this sets the backlink on the given item.
+ *
+ * NB: ignores anything in the heap beyond 'i' -- in particular does not use
+ *     v.end at all.  So this can be used to work along a vector and bring
+ *     items into heap order.
+ */
+static void
+heap_bubble_up(heap h, vector_index i, p_vector_item p_v)
+{
+  p_vector_item* ha = h->v.p_items ;    /* underlying array     */
+
+  while (i != 0)
+    {
+      vector_index ip = HEAP_UP(i) ;
+      p_vector_item p_p = &ha[ip] ;
+
+      if (h->cmp(&p_p, &p_v) <= 0)
+	break ;				/* stop when parent is <= us	*/
+      ha[i] = p_p ;		        /* move parent down...		*/
+      heap_set_backlink(h, p_p, i) ;	/* ...updating any backlink	*/
+      i = ip ;				/* move up the heap		*/
+    }
+
+  ha[i] = p_v ;		                /* place in new position...	*/
+  heap_set_backlink(h, p_v, i) ;	/* ...updating any backlink	*/
+} ;
+
+/* Insert given item in the required place in heap, given that there is now
+ * a hole at the given position -- where we know may *only* move down the heap.
+ *
+ * Note that this sets the backlink on the given item.
+ */
+static void
+heap_bubble_down(heap h, vector_index i, p_vector_item p_v)
+{
+  vector_index   e  = h->v.end ;        /* end of heap          */
+  p_vector_item* ha = h->v.p_items ;    /* underlying array     */
+
+  while (1)
+    {
+      vector_index ic ;			/* index of child	*/
+      vector_index is ;			/* index of sibling	*/
+      p_vector_item p_c ;		/* pointer to child	*/
+      p_vector_item p_s ;		/* pointer to sibling	*/
+
+      ic = HEAP_DOWN(i) ;
+      if (ic >= e)
+	break ;				/* Quit if run out of heap ! */
+      p_c = &ha[ic] ;
+
+      is = ic + 1 ;
+      if (is < e)
+	{
+	  p_s = &ha[is] ;
+	  if (h->cmp(&p_s, &p_c) < 0)
+	    {
+	      ic  = is ;		/* select smaller sibling	*/
+	      p_c = p_s ;
+	    }
+	}
+
+      if (h->cmp(&p_v, &p_c) <= 0)
+	break ;				/* stop when we are <= both children  */
+      ha[i] = p_c ;		        /* move smaller child up	      */
+      heap_set_backlink(h, p_c, i) ;	/* ...updating any backlink	      */
+      i = ic ;				/* move down the heap		      */
+    }
+
+  ha[i] = p_v ;
+  heap_set_backlink(h, p_v, i) ;
+} ;
+
+/* Find index of given item in the given heap.		*/
+static vector_index
+heap_find_item(heap h, p_vector_item p_v)
+{
+  vector_index i ;
+
+  if (h->state & Heap_Has_Backlink)
+    i = HEAP_BACKLINK(h, p_v) ;
+  else
+    {
+      for (i = 0 ; i < h->v.end ; ++i)
+	if (h->v.p_items[i] == p_v)
+	  break ;
+    } ;
+
+  assert((i < h->v.end) && (h->v.p_items[i] == p_v)) ;
+
+  return i ;
+} ;
diff --git a/lib/heap.h b/lib/heap.h
new file mode 100644
index 00000000..d91fff4a
--- /dev/null
+++ b/lib/heap.h
@@ -0,0 +1,96 @@
+/* Generic heap data structure -- header.
+ * Copyright (C) 2009 Chris Hall (GMCH), Highwayman
+ *.
+ * This file is part of GNU Zebra.
+ *
+ * GNU Zebra is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Zebra; see the file COPYING.  If not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ * 02111-1307, USA.
+ */
+
+#ifndef _ZEBRA_HEAP_H
+#define _ZEBRA_HEAP_H
+
+#include "vector.h"
+
+/* Macro in case there are particular compiler issues.    */
+#ifndef Inline
+  #define Inline static inline
+#endif
+
+typedef int heap_cmp(p_vector_item* a, p_vector_item*) ;
+
+enum heap_state {
+  Heap_Has_Backlink  = 0x01,    /* Set if backlink set  */
+};
+
+struct heap
+{
+  heap_cmp* cmp ;
+
+  enum heap_state state ;
+  unsigned int backlink_offset ;
+
+  struct vector v ;
+};
+
+typedef struct heap* heap;
+
+typedef vector_index heap_backlink_t ;
+
+/* Prototypes. */
+
+extern heap heap_init_new(heap h, vector_index size, heap_cmp* cmp,
+                            int with_backlink, unsigned int backlink_offset) ;
+#define heap_init_new_simple(h, size, cmp) \
+  heap_init_new(h, size, cmp, 0, 0)
+#define heap_init_new_backlinked(h, size, cmp, off) \
+  heap_init_new(h, size, cmp, 1, off)
+
+extern heap heap_re_init(heap h, vector_index size, heap_cmp* cmp,
+			    int with_backlink, unsigned int backlink_offset) ;
+#define heap_re_init_simple(h, size, cmp) \
+  heap_re_init(h, size, cmp, 0, 0)
+#define heap_re_init_backlinked(h, size, cmp, off) \
+  heap_re_init(h, size, cmp, 1, off)
+
+extern heap heap_reset(heap h, int free_structure) ;
+extern p_vector_item heap_ream(heap h, int free_structure) ;
+
+/* Reset heap and free the heap structure.	*/
+#define heap_reset_free(h) heap_reset(h, 1) ;
+/* Reset heap but keep the heap structure.	*/
+#define heap_reset_keep(h) heap_reset(h, 0) ;
+/* Ream out heap and free the heap structure.	*/
+#define heap_ream_free(h) heap_ream_out(h, 1) ;
+/* Ream out heap but keep the heap structure.	*/
+#define heap_ream_keep(h) heap_ream_out(h, 0) ;
+
+extern void heap_push_item(heap h, p_vector_item p_v) ;
+extern p_vector_item heap_pop_item(heap h) ;
+extern p_vector_item heap_top_item(heap h) ;
+extern void heap_update_top_item(heap h) ;
+
+extern void heap_delete_item(heap h, p_vector_item p_v) ;
+extern void heap_update_item(heap h, p_vector_item p_v) ;
+
+extern void heap_push_vector(heap h, vector v, int move_vector) ;
+#define heap_push_vector_copy(h, v) \
+  heap_push_vector(h, v, 0)
+#define heap_push_vector_move(h, v) \
+  heap_push_vector(h, v, 1)
+extern vector heap_pop_vector(vector v, heap h, int move_heap) ;
+#define heap_pop_vector_copy(v, h)  \
+  heap_pop_vector(v, h, 0)
+#define heap_pop_vector_move(v, h)  \
+  heap_pop_vector(v, h, 1)
+
+extern vector heap_vector(heap h, int unset_heap_order) ;
+
+#endif /* _ZEBRA_HEAP_H */
diff --git a/lib/memtypes.c b/lib/memtypes.c
index 197fb88c..fb2557c8 100644
--- a/lib/memtypes.c
+++ b/lib/memtypes.c
@@ -16,18 +16,22 @@ struct memory_list memory_list_lib[] =
 {
   { MTYPE_TMP,			"Temporary memory"		},
   { MTYPE_STRVEC,		"String vector"			},
-  { MTYPE_VECTOR,		"Vector structure"		},
-  { MTYPE_VECTOR_BODY,		"Vector body"			},
+  { MTYPE_VECTOR,               "Vector structure"              },
+  { MTYPE_VECTOR_BODY,          "Vector body"                   },
   { MTYPE_SYMBOL_TABLE,         "Symbol Table structure"        },
   { MTYPE_SYMBOL_BASES,         "Symbol Table chain bases"      },
   { MTYPE_SYMBOL,               "Symbol"                        },
   { MTYPE_SYMBOL_REF,           "Symbol Reference"              },
+  { MTYPE_HEAP,                 "Heap structure"                },
   { MTYPE_LINK_LIST,		"Link List"			},
   { MTYPE_LINK_NODE,		"Link Node"			},
   { MTYPE_THREAD,		"Thread"			},
   { MTYPE_THREAD_MASTER,	"Thread master"			},
   { MTYPE_THREAD_STATS,		"Thread stats"			},
-  { MTYPE_THREAD_FUNCNAME,	"Thread function name" 		},
+  { MTYPE_THREAD_FUNCNAME,      "Thread function name"          },
+  { MTYPE_QPT_THREAD_ATTR,      "qpt thread attributes"         },
+  { MTYPE_QPT_MUTEX,            "qpt mutex"                     },
+  { MTYPE_QPT_COND,             "qpt condition variable"        },
   { MTYPE_VTY,			"VTY"				},
   { MTYPE_VTY_OUT_BUF,		"VTY output buffer"		},
   { MTYPE_VTY_HIST,		"VTY history"			},
diff --git a/lib/qpthreads.c b/lib/qpthreads.c
new file mode 100644
index 00000000..87ee00d3
--- /dev/null
+++ b/lib/qpthreads.c
@@ -0,0 +1,435 @@
+/* Quagga Pthreads support -- header
+ * Copyright (C) 2009 Chris Hall (GMCH), Highwayman
+ *
+ * This file is part of GNU Zebra.
+ *
+ * GNU Zebra is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published
+ * by the Free Software Foundation; either version 2, or (at your
+ * option) any later version.
+ *
+ * GNU Zebra is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Zebra; see the file COPYING.  If not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include "qpthreads.h"
+#include "memory.h"
+
+/*==============================================================================
+ * Quagga Pthread Interface -- qpt_xxxx
+ *
+ * Here (and in qpthreads.h) are captured all the pthreads features used in
+ * Quagga.
+ *
+ * This provides:
+ *
+ *   * "wrappers" around functions which should not fail, but whose return
+ *     code it is best to check... at least in a debug environment.
+ *
+ *   * the possibility of a separate no pthreads build where pthread facilities
+ *     are either dummied out or otherwise dealt with.
+ *
+ *   * the ability to add any work-arounds which may be required if poorly
+ *     conforming pthreads implementations are encountered
+ *
+ * Pthread Thread Attributes -- Scheduling
+ * =======================================
+ *
+ * Pthreads defines some useful looking real-time scheduling features.
+ *
+ * One would like to be able to give I/O intensive threads an advantage over
+ * CPU bound threads.
+ *
+ * Unfortunately, conformance allows a system to have its own scheduling
+ * system -- so long as the standard ones are implemented.  Further, there is
+ * no way of telling what priority values are reasonable, even in the standard
+ * scheduling policies.
+ *
+ * The approach taken here is that by default a thread will be created with
+ * the system default attributes -- which may mean inheriting the creating
+ * thread's scheduling attributes.
+ *
+ * It is also possible to construct a set of attributes, using the most
+ * obviously useful properties.  It is envisaged that this may be used when a
+ * configuration file is used to set locally sensible values.   The attributes
+ * supported are:
+ *
+ *    * attr_detached       -- whether to start detached or not
+ *    * attr_inherit_sched  -- whether to inherit scheduling attributes
+ *    * attr_sched_scope    -- scheduling scope
+ *    * attr_sched_policy   -- scheduling policy
+ *    * attr_sched_priority -- scheduling priority
+ *
+ * See qpt_thread_attr_init, below.
+ *
+ * Not supported here are:
+ *
+ *    * attr_guardsize
+ *    * attr_stack
+ *    * attr_stacksize
+ *
+ * Pthread Mutex Attributes -- Error Checking
+ * ==========================================
+ *
+ * Mutexes are kept simple, only attr_type is used, and that by default.
+ *
+ * POSIX defines four types of mutex:
+ *
+ *   _NORMAL      no ownership check   -- owner will deadlock if locks mutex !
+ *                                     -- undefined what happens if unlock
+ *                                        mutex not owned by self !
+ *                no recursive locking
+ *
+ *   _ERRORCHECK  checks for ownership on lock and unlock
+ *                no recursive locking
+ *
+ *   _RECURSIVE   checks for ownership on lock and unlock
+ *                counts up locks and counts down unlocks
+ *
+ *                This looks useful, but goes wrong with condition variables !
+ *
+ *   _DEFAULT     undefined whether checks owner or not, on lock and/or unlock.
+ *                no recursive locking
+ *
+ * See qpthreads.h for discussion of Quagga's standard type (QPT_MUTEX_TYPE).
+ *
+ * Other attributes are left in their default state:
+ *
+ *   * attr_prioceiling  -- default undefined
+ *   * attr_protocol     -- default undefined
+ *   * attr_pshared      -- defaults to _PROCESS_PRIVATE
+ *
+ * For the time being it is assumed that these are too exotic.
+ *
+ * Pthread Condition Variable Attributes
+ * =====================================
+ *
+ * Condition variables have only two attributes:
+ *
+ *   * attr_clock        -- which clock to use
+ *   * attr_pshared      -- defaults to _PROCESS_PRIVATE
+ *
+ * The use a clock other than Quagga's standard (QPT_COND_CLOCK_ID) is possible,
+ * but not recommended.  (See qpthreads.h for discussion of this.)
+ */
+
+/*==============================================================================
+ * Thread creation and attributes.
+ *
+ * Threads may be created with a given set of attributes if required.
+ *
+ * qpt_thread_attr_init() will initialise a set of attributes including the
+ * current standard scheduling attributes.  It is envisaged that configuration
+ * options may be used to specify these.
+ *
+ * qpt_thread_create() creates a thread using the given attributes.  If those
+ * are NULL, then the system defaults are used.
+ */
+
+/* Initialise a set of attributes -- setting the scheduling options.
+ *
+ * Options:
+ *
+ *   qpt_attr_joinable       -- the default if nothing specified.
+ *   qpt_attr_detached       -- overrides qpt_attr_joinable.
+ *
+ *   qpt_attr_sched_inherit  -- all scheduling attributes are to be inherited.
+ *                              No explicit scheduling attributes may be set.
+ *
+ *   qpt_attr_sched_scope    -- set explicit, given, scope.
+ *   qpt_attr_sched_policy   -- set explicit, given, policy
+ *   qpt_attr_sched_priority -- set explicit, given, priority
+ *
+ * If none of the _sched_ options are given, then the scheduling attributes are
+ * left to whatever default values the system chooses.
+ *
+ * If the _sched_inherit option is specified, none of the other _sched_ options
+ * may be specified.
+ *
+ * If any of the explicit scheduling options are given, they are set in this
+ * order.  If only some of these options are given, then the caller is
+ * assuming that the system will choose sensible defaults.
+ *
+ * The scope, policy and priority arguments are use only if the corresponding
+ * option is specified.
+ *
+ * Returns the address of the qpt_thread_attr_t structure.
+ */
+qpt_thread_attr_t*
+qpt_thread_attr_init(qpt_thread_attr_t* attr, enum qpt_attr_options opts,
+                                          int scope, int policy, int priority)
+{
+  int err ;
+
+  assert((opts & ~qpt_attr_known) == 0) ;
+
+  /* Initialise thread attributes structure (allocating if required.)   */
+  if (attr == NULL)
+    attr = XMALLOC(MTYPE_QPT_THREAD_ATTR, sizeof(qpt_thread_attr_t)) ;
+
+  err = pthread_attr_init(attr) ;
+  if (err != 0)
+    zabort_err("pthread_attr_init failed", err) ;
+
+  /* If not qpt_attr_detached, then set joinable.       */
+  err = pthread_attr_setdetachstate(attr,
+                         (opts & qpt_attr_detached) ? PTHREAD_CREATE_DETACHED
+                                                    : PTHREAD_CREATE_JOINABLE) ;
+  if (err != 0)
+    zabort_err("pthread_attr_setdetachstate failed", err) ;
+
+  /* If setting anything to do with scheduling...       */
+  if (opts & qpt_attr_sched_setting)
+    {
+      /* Either we inherit or we set explicit parameters.       */
+
+      err = pthread_attr_setinheritsched(attr,
+                    (opts & qpt_attr_sched_inherit) ? PTHREAD_INHERIT_SCHED
+                                                    : PTHREAD_EXPLICIT_SCHED) ;
+      if (err != 0)
+        zabort_err("pthread_attr_setinheritsched", err) ;
+
+      if (opts & qpt_attr_sched_inherit)
+        assert((opts & qpt_attr_sched_explicit) == 0) ;
+      else
+        {
+          if (opts & qpt_attr_sched_scope)
+            {
+              err = pthread_attr_setscope(attr, scope) ;
+              if (err != 0)
+                zabort_err("pthread_attr_setscope failed", err) ;
+            } ;
+          if (opts & qpt_attr_sched_policy)
+            {
+              err = pthread_attr_setschedpolicy(attr, scope) ;
+              if (err != 0)
+                zabort_err("pthread_attr_setschedpolicy failed", err) ;
+            } ;
+          if (opts & qpt_attr_sched_priority)
+            {
+              struct sched_param sparm ;
+              err = pthread_attr_getschedparam(attr, &sparm) ;
+              if (err != 0)
+                zabort_err("pthread_attr_getschedparam failed", err) ;
+              sparm.sched_priority = priority ;
+              err = pthread_attr_setschedparam(attr, &sparm) ;
+              if (err != 0)
+                zabort_err("pthread_attr_setschedparam failed", err) ;
+            } ;
+        } ;
+    } ;
+
+  /* Done -- return qpt_thread_attr_t*     */
+  return attr ;
+} ;
+
+/* Create Thread with given attributes (if any).
+ *
+ * If no attributes are given (attr == NULL) the thread is created with system
+ * default attributes -- *except* that it is created joinable.
+ *
+ * Returns the qpt_thread_t "thread id".
+ */
+qpt_thread_t
+qpt_thread_create(void* (*start)(void*), void* arg, qpt_thread_attr_t* attr)
+{
+  qpt_thread_attr_t thread_attr ;
+  qpt_thread_t      thread_id ;
+  int default_attr ;
+  int err ;
+
+  default_attr = (attr == NULL) ;
+  if (default_attr)
+    attr = qpt_thread_attr_init(&thread_attr, qpt_attr_joinable, 0, 0, 0) ;
+
+  err = pthread_create(&thread_id, attr, start, arg) ;
+  if (err != 0)
+    zabort_err("pthread_create failed", err) ;
+
+  if (default_attr)
+    {
+      err = pthread_attr_destroy(attr) ;        /* being tidy */
+      if (err != 0)
+        zabort_err("pthread_attr_destroy failed", err) ;
+    } ;
+
+  return thread_id ;
+} ;
+
+/*==============================================================================
+ * Mutex initialise and destroy.
+ */
+
+/* Initialise Mutex (allocating if required).
+ *
+ * Options:
+ *
+ *   qpt_mutex_quagga      -- see qpthreads.h for discussion of this.
+ *   qpt_mutex_normal      -- ie PTHREAD_MUTEX_NORMAL
+ *   qpt_mutex_recursive   -- ie PTHREAD_MUTEX_RECURSIVE
+ *   qpt_mutex_errorcheck  -- ie PTHREAD_MUTEX_ERRORCHECK
+ *   qpt_mutex_default     -- system default
+ *
+ * Of these _recursive is the most likely alternative to _quagga...  BUT do
+ * remember that such mutexes DO NOT play well with condition variables.
+ */
+qpt_mutex_t*
+qpt_mutex_init(qpt_mutex_t* mx, enum qpt_mutex_options opts)
+{
+  pthread_mutexattr_t mutex_attr ;
+  int type ;
+  int err ;
+
+  if (mx == NULL)
+    mx = XMALLOC(MTYPE_QPT_MUTEX, sizeof(qpt_mutex_t)) ;
+
+  /* Set up attributes so we can set the mutex type     */
+  err = pthread_mutexattr_init(&mutex_attr);
+  if (err != 0)
+    zabort_err("pthread_mutexattr_init failed", err) ;
+
+  switch(opts)
+  {
+    case qpt_mutex_quagga:
+      type = QPT_MUTEX_TYPE ;
+      break ;
+    case qpt_mutex_normal:
+      type = PTHREAD_MUTEX_NORMAL ;
+      break ;
+    case qpt_mutex_recursive:
+      type = PTHREAD_MUTEX_RECURSIVE ;
+      break ;
+    case qpt_mutex_errorcheck:
+      type = PTHREAD_MUTEX_ERRORCHECK ;
+      break ;
+    case qpt_mutex_default:
+      type = PTHREAD_MUTEX_DEFAULT ;
+      break ;
+    default:
+      zabort("Invalid qpt_mutex option") ;
+  } ;
+
+#ifndef PTHREAD_MUTEXATTR_SETTYPE_MISSING
+  err = pthread_mutexattr_settype(&mutex_attr, type);
+  if (err != 0)
+    zabort_err("pthread_mutexattr_settype failed", err) ;
+#endif
+
+  /* Now we're ready to initialize the mutex itself     */
+  err = pthread_mutex_init(mx, &mutex_attr) ;
+  if (err != 0)
+    zabort_err("pthread_mutex_init failed", err) ;
+
+  /* Be tidy with the attributes                        */
+  err = pthread_mutexattr_destroy(&mutex_attr) ;
+  if (err != 0)
+    zabort_err("pthread_mutexattr_destroy failed", err) ;
+
+  /* Done: return the mutex                             */
+  return mx ;
+} ;
+
+/* Destroy given mutex, and (if required) free it.
+ *
+ * Returns NULL.
+*/
+qpt_mutex_t*
+qpt_mutex_destroy(qpt_mutex_t* mx, int free_mutex)
+{
+  int err ;
+
+  err = pthread_mutex_destroy(mx) ;
+  if (err != 0)
+    zabort_err("pthread_mutex_destroy failed", err) ;
+
+  if (free_mutex)
+      XFREE(MTYPE_QPT_MUTEX, mx) ;
+
+  return NULL ;
+} ;
+
+/*==============================================================================
+ * Condition Variable initialise and destroy.
+ */
+
+/* Initialise Condition Variable (allocating if required).
+ *
+ * Options:
+ *
+ *   qpt_cond_quagga     -- use Quagga's default clock
+ *   qpt_cond_realtime   -- force CLOCK_REALTIME
+ *   qpt_cond_monotonic  -- force CLOCK_MONOTONIC  (if available)
+ */
+qpt_cond_t*
+qpt_cond_init(qpt_cond_t* cv, enum qpt_cond_options opts)
+{
+  pthread_condattr_t cond_attr ;
+  int clock ;
+  int err ;
+
+  if (cv == NULL)
+    cv = XMALLOC(MTYPE_QPT_COND, sizeof(qpt_cond_t)) ;
+
+  /* Set up attributes so we can set the  type     */
+  err = pthread_condattr_init(&cond_attr);
+  if (err != 0)
+    zabort_err("pthread_condattr_init failed", err) ;
+
+  switch(opts)
+  {
+    case qpt_cond_quagga:
+      clock = QPT_COND_CLOCK_ID ;
+      break ;
+    case qpt_cond_realtime:
+      clock = CLOCK_REALTIME ;
+      break ;
+    case qpt_cond_monotonic:
+      clock = CLOCK_MONOTONIC ;
+      break ;
+    default:
+      zabort("Invalid qpt_cond option") ;
+  } ;
+
+  err = pthread_condattr_setclock(&cond_attr, clock);
+  if (err != 0)
+    zabort_err("pthread_condattr_setclock failed", err) ;
+
+  /* Now we're ready to initialize the condition variable itself        */
+  err = pthread_cond_init(cv, &cond_attr) ;
+  if (err != 0)
+    zabort_err("pthread_cond_init failed", err) ;
+
+  /* Be tidy with the attributes                        */
+  err = pthread_condattr_destroy(&cond_attr) ;
+  if (err != 0)
+    zabort_err("pthread_condattr_destroy failed", err) ;
+
+  /* Done: return the condition variable                */
+  return cv ;
+} ;
+
+/* Destroy given mutex, and (if required) free it.
+ *
+ * Returns NULL.
+*/
+qpt_cond_t*
+qpt_cond_destroy(qpt_cond_t* cv, int free_cond)
+{
+  int err ;
+
+  err = pthread_cond_destroy(cv) ;
+  if (err != 0)
+    zabort_err("pthread_cond_destroy failed", err) ;
+
+  if (free_cond)
+      XFREE(MTYPE_QPT_COND, cv) ;
+
+  return NULL ;
+} ;
diff --git a/lib/qpthreads.h b/lib/qpthreads.h
new file mode 100644
index 00000000..189eabc6
--- /dev/null
+++ b/lib/qpthreads.h
@@ -0,0 +1,393 @@
+/* Quagga Pthreads support -- header
+ * Copyright (C) 2009 Chris Hall (GMCH), Highwayman
+ *
+ * This file is part of GNU Zebra.
+ *
+ * GNU Zebra is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published
+ * by the Free Software Foundation; either version 2, or (at your
+ * option) any later version.
+ *
+ * GNU Zebra is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Zebra; see the file COPYING.  If not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#ifndef _ZEBRA_QPTHREADS_H
+#define _ZEBRA_QPTHREADS_H
+
+#include <stdint.h>
+#include <time.h>
+#include <pthread.h>
+#include <unistd.h>
+#include <errno.h>
+
+#include "zassert.h"
+#include "qtime.h"
+
+
+#ifndef Inline
+#define Inline static inline
+#endif
+
+/*==============================================================================
+ * Quagga Pthread Interface -- qpt_xxxx
+ *
+ * Here are captured all the pthreads features used in Quagga.
+ *
+ * This provides:
+ *
+ *   * "wrappers" around functions which should not fail, but whose return
+ *     code it is best to check... at least in a debug environment.
+ *
+ *   * the possibility of a separate no pthreads build where pthread facilities
+ *     are either dummied out or otherwise dealt with.
+ *
+ *   * the ability to add any work-arounds which may be required if poorly
+ *     conforming pthreads implementations are encountered
+ */
+
+#if !defined(_POSIX_THREADS) || (_POSIX_THREADS <= 0)
+#error Require _POSIX_THREADS
+#endif
+
+/*==============================================================================
+ * TEMPORARY WORKAROUND
+ *
+ * TODO: discover why PTHREAD_MUTEX_NORMAL etc are not defined !!
+ *
+ */
+
+#define PTHREAD_MUTEXATTR_SETTYPE_MISSING 1
+
+#ifdef PTHREAD_MUTEXATTR_SETTYPE_MISSING
+#define PTHREAD_MUTEX_NORMAL      PTHREAD_MUTEX_TIMED_NP
+#define PTHREAD_MUTEX_ERRORCHECK  PTHREAD_MUTEX_ERRORCHECK_NP
+#define PTHREAD_MUTEX_RECURSIVE   PTHREAD_MUTEX_RECURSIVE_NP
+#define PTHREAD_MUTEX_DEFAULT     PTHREAD_MUTEX_NORMAL
+#endif
+
+/*==============================================================================
+ * Data types
+ */
+
+typedef pthread_t        qpt_thread_t ;
+typedef pthread_mutex_t  qpt_mutex_t ;
+typedef pthread_cond_t   qpt_cond_t ;
+
+typedef pthread_attr_t   qpt_thread_attr_t ;
+
+/*==============================================================================
+ * Thread Creation -- see qpthreads.c for further discussion.
+ */
+
+enum qpt_attr_options {
+  qpt_attr_joinable        = 0,         /* the default for Quagga       */
+
+  qpt_attr_detached        = 0x0001,    /* otherwise will set joinable  */
+
+  qpt_attr_sched_inherit   = 0x0002,    /* otherwise will use default   */
+
+  qpt_attr_sched_scope     = 0x0004,    /* otherwise inherit/default    */
+  qpt_attr_sched_policy    = 0x0008,    /* otherwise inherit/default    */
+  qpt_attr_sched_priority  = 0x0010,    /* otherwise inherit/default    */
+} ;
+
+#define qpt_attr_sched_explicit  ( qpt_attr_sched_scope   \
+                                 | qpt_attr_sched_policy  \
+                                 | qpt_attr_sched_priority )
+
+#define qpt_attr_sched_setting   ( qpt_attr_sched_inherit \
+                                 | qpt_attr_sched_explicit )
+
+#define qpt_attr_known ( qpt_attr_detached | qpt_attr_sched_setting )
+
+extern qpt_thread_attr_t*
+qpt_thread_attr_init(qpt_thread_attr_t* attr, enum qpt_attr_options opts,
+                                          int scope, int policy, int priority) ;
+extern qpt_thread_t
+qpt_thread_create(void* (*start)(void*), void* arg, qpt_thread_attr_t* attr) ;
+
+/*==============================================================================
+ * Mutex handling.
+ *
+ * Quagga's default mutex type is:
+ *
+ *   * PTHREAD_MUTEX_ERRORCHECK unless NDEBUG && NDEBUG_QPTHREADS
+ *   * QPT_MUTEX_TYPE_DEFAULT
+ *
+ * QPT_MUTEX_TYPE_DEFAULT may be set elsewhere.  If it is not set then it is
+ * set here to be PTHREAD_MUTEX_NORMAL.
+ *
+ * NB: on the face of it PTHREAD_MUTEX_NORMAL should be the fastest.  It is
+ *     possible that PTHREAD_MUTEX_DEFAULT may have system specific semantics
+ *     that make it faster than the standard _NORMAL.  It is also possible that
+ *     a given system may elect to provide a safer mutex than the _NORMAL by
+ *     default.
+ *
+ *     If _DEFAULT is faster than _NORMAL, then QPT_MUTEX_TYPE_DEFAULT may be
+ *     used to override this choice.
+ */
+
+enum qpt_mutex_options {
+  qpt_mutex_quagga      = 0x0000,       /* Quagga's default     */
+  qpt_mutex_normal      = 0x0001,
+  qpt_mutex_recursive   = 0x0002,
+  qpt_mutex_errorcheck  = 0x0003,
+  qpt_mutex_default     = 0x0004,       /* system default       */
+} ;
+
+#ifndef QPT_MUTEX_TYPE_DEFAULT
+# define QPT_MUTEX_TYPE_DEFAULT  PTHREAD_MUTEX_NORMAL
+#endif
+
+#if defined(NDEBUG) && defined(NDEBUG_QPTHREADS)
+# define QPT_MUTEX_TYPE  QPT_MUTEX_TYPE_DEFAULT
+#else
+# define QPT_MUTEX_TYPE  PTHREAD_MUTEX_ERRORCHECK
+#endif
+
+extern qpt_mutex_t*
+qpt_mutex_init(qpt_mutex_t* mx, enum qpt_mutex_options opts) ;
+
+extern qpt_mutex_t*
+qpt_mutex_destroy(qpt_mutex_t* mx, int free_mutex) ;
+
+#define qpt_mutex_destroy_keep(mx) qpt_mutex_destroy(mx, 0)
+#define qpt_mutex_destroy_free(mx) qpt_mutex_destroy(mx, 1)
+
+Inline void
+qpt_mutex_lock(qpt_mutex_t* mx) ;       /* do nothing if mx == NULL     */
+
+Inline int
+qpt_mutex_trylock(qpt_mutex_t* mx) ;    /* do nothing if mx == NULL     */
+
+Inline void
+qpt_mutex_unlock(qpt_mutex_t* mx) ;     /* do nothing if mx == NULL     */
+
+/*==============================================================================
+ * Condition Variable handling
+ *
+ * Quagga's default clock for condition variables is QPT_COND_CLOCK_ID, which
+ * may be set elsewhere.  If it is not set then it is set here to be:
+ *
+ *   * CLOCK_MONOTONIC if available
+ *   * CLOCK_REALTIME otherwise  -- this is the standard default.
+ *
+ * NB: qpt_cond_get_timeout_time uses QPT_COND_CLOCK_ID.
+ *
+ *     If a specific clock is required, it can be set... but the user of the
+ *     condition variable must take care to base time-out times on that clock.
+ *
+ * NB: static initialisation of condition variables is not supported, to avoid
+ *     confusion between the standard default and Quagga's default.
+ */
+
+#ifndef QPT_COND_CLOCK_ID
+# ifndef HAVE_CLOCK_MONOTONIC
+#  define QPT_COND_CLOCK_ID  CLOCK_REALTIME
+# else
+#  define QPT_COND_CLOCK_ID  CLOCK_MONOTONIC
+# endif
+#endif
+
+enum qpt_cond_options {
+  qpt_cond_quagga      = 0x0000,  /* Quagga's default   */
+  qpt_cond_realtime    = 0x0001,  /* standard default   */
+  qpt_cond_monotonic   = 0x0002,
+} ;
+
+extern qpt_cond_t*
+qpt_cond_init(qpt_cond_t* cv, enum qpt_cond_options opts) ;
+
+extern qpt_cond_t*
+qpt_cond_destroy(qpt_cond_t* cv, int free_cond) ;
+
+#define qpt_cond_destroy_keep(cv) qpt_cond_destroy(cv, 0)
+#define qpt_cond_destroy_free(cv) qpt_cond_destroy(cv, 1)
+
+Inline void
+qpt_cond_wait(qpt_cond_t* cv, qpt_mutex_t* mx) ;
+
+Inline qtime_t
+qpt_cond_get_timeout_time(qtime_t wait) ;
+
+Inline int
+qpt_cond_timedwait(qpt_cond_t* cv, qpt_mutex_t* mx, qtime_t tot) ;
+
+Inline void
+qpt_cond_signal(qpt_cond_t* cv) ;
+
+Inline void
+qpt_cond_broadcast(qpt_cond_t* cv) ;
+
+/*==============================================================================
+ * Mutex inline functions
+ */
+
+/* Lock given mutex.
+ *
+ * Unless both NCHECK_QPTHREADS and NDEBUG are defined, checks that the
+ * return value is valid -- zabort_errno if it isn't.
+ */
+
+Inline void
+qpt_mutex_lock(qpt_mutex_t* mx)         /* do nothing if mx == NULL     */
+{
+  if (mx != NULL)
+    {
+#if defined(NDEBUG) && defined(NDEBUG_QPTHREADS)
+      pthread_mutex_lock(mx) ;
+#else
+      int err = pthread_mutex_lock(mx) ;
+      if (err != 0)
+        zabort_err("pthread_mutex_lock failed", err) ;
+#endif
+    } ;
+} ;
+
+/* Try to lock given mutex.
+ *
+ * Returns: lock succeeded (1 => have locked, 0 => unable to lock).
+ *
+ * Has to check the return value, so zabort_errno if not EBUSY.
+ */
+
+Inline int
+qpt_mutex_trylock(qpt_mutex_t* mx)      /* do nothing if mx == NULL     */
+{
+  if (mx != NULL)
+    {
+      int err = pthread_mutex_trylock(mx) ;
+      if (err == 0)
+        return 1 ;                      /* success: it's locked.        */
+      if (err == EBUSY)
+        return 0 ;                      /* unable to lock               */
+
+      zabort_err("pthread_mutex_trylock failed", err) ;
+                                        /* crunch                       */
+    } ;
+} ;
+
+/* Unlock given mutex.
+ *
+ * Unless both NCHECK_QPTHREADS and NDEBUG are defined, checks that the
+ * return value is valid -- zabort_errno if it isn't.
+ */
+Inline void
+qpt_mutex_unlock(qpt_mutex_t* mx)       /* do nothing if mx == NULL     */
+{
+  if (mx != NULL)
+    {
+#if defined(NDEBUG) && defined(NDEBUG_QPTHREADS)
+      pthread_mutex_unlock(mx) ;
+#else
+      int err = pthread_mutex_lock(mx) ;
+      if (err != 0)
+        zabort_err("pthread_mutex_lock failed", err) ;
+#endif
+    } ;
+} ;
+
+/*==============================================================================
+ * Condition variable inline functions
+ */
+
+/* Wait for given condition variable.
+ *
+ * Unless both NCHECK_QPTHREADS and NDEBUG are defined, checks that the
+ * return value is valid -- zabort_errno if it isn't.
+ */
+
+Inline void
+qpt_cond_wait(qpt_cond_t* cv, qpt_mutex_t* mx)
+{
+#if defined(NDEBUG) && defined(NDEBUG_QPTHREADS)
+  pthread_cond_wait(cv, mx) ;
+#else
+  int err = pthread_cond_wait(cv, mx) ;
+  if (err != 0)
+    zabort_err("pthread_cond_wait failed", err) ;
+#endif
+} ;
+
+/* Get a time-out time (for use with qpt_cond_timedwait).
+ *
+ * Returns the current system time plus the given wait time.
+ */
+
+Inline qtime_t
+qpt_cond_get_timeout_time(qtime_t wait)
+{
+  return qt_clock_gettime(QPT_COND_CLOCK_ID) + wait ;
+} ;
+
+/* Wait for given condition variable or time-out.
+ *
+ * Returns: wait succeeded (1 => success, 0 => timed-out).
+ *
+ * The time-out is an *absolute* time expressed as a qtime_t.
+ *
+ * NB: qpt_cond_get_timeout_time() should be used to generate the required
+ *     time-out.  That uses CLOCK_
+ *
+ * Has to check the return value, so zabort_errno if not EBUSY.
+ */
+
+Inline int
+qpt_cond_timedwait(qpt_cond_t* cv, qpt_mutex_t* mx, qtime_t tot)
+{
+  struct timespec ts ;
+
+  int err = pthread_cond_timedwait(cv, mx, qtime2timespec(&ts, tot)) ;
+  if (err == 0)
+    return 1 ;                  /* got condition        */
+  if (err == ETIMEDOUT)
+    return 0 ;                  /* got time-out         */
+
+  zabort_err("pthread_cond_timedwait failed", err) ;
+                                /* crunch               */
+} ;
+
+/* Signal given condition.
+ *
+ * Unless both NCHECK_QPTHREADS and NDEBUG are defined, checks that the
+ * return value is valid -- zabort_errno if it isn't.
+ */
+
+Inline void
+qpt_cond_signal(qpt_cond_t* cv)
+{
+#if defined(NDEBUG) && defined(NDEBUG_QPTHREADS)
+  pthread_cond_signal(cv) ;
+#else
+  int err = pthread_cond_signal(cv) ;
+  if (err != 0)
+    zabort_err("pthread_cond_signal failed", err) ;
+#endif
+} ;
+
+/* Broadcast given condition.
+ *
+ * Unless both NCHECK_QPTHREADS and NDEBUG are defined, checks that the
+ * return value is valid -- zabort_errno if it isn't.
+ */
+Inline void
+qpt_cond_broadcast(qpt_cond_t* cv)
+{
+#if defined(NDEBUG) && defined(NDEBUG_QPTHREADS)
+  pthread_cond_broadcast(cv) ;
+#else
+  int err = pthread_cond_broadcast(cv) ;
+  if (err != 0)
+    zabort_err("pthread_cond_broadcast failed", err) ;
+#endif
+} ;
+
+#endif /* _ZEBRA_QPTHREADS_H */
diff --git a/lib/qtime.c b/lib/qtime.c
new file mode 100644
index 00000000..cdcf09f9
--- /dev/null
+++ b/lib/qtime.c
@@ -0,0 +1,128 @@
+/* Quagga Realtime Clock handling -- functions
+ * Copyright (C) 2009 Chris Hall (GMCH), Highwayman
+ *
+ * This file is part of GNU Zebra.
+ *
+ * GNU Zebra is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published
+ * by the Free Software Foundation; either version 2, or (at your
+ * option) any later version.
+ *
+ * GNU Zebra is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Zebra; see the file COPYING.  If not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include <sys/times.h>
+#include <errno.h>
+
+#include "zassert.h"
+#include "qtime.h"
+
+/*==============================================================================
+ * This is a collection of functions and (in qtime.h) macros and inline
+ * functions which support system time and a monotonic clock.
+ */
+
+/*==============================================================================
+ * Replacement for CLOCK_MONOTONIC.
+ *
+ * With thanks to Joakim Tjernlund for reminding everyone of the return value
+ * from times() !
+ *
+ * times() is defined to return a value which is the time since some fixed time
+ * before the application started (or when the application started).  This time
+ * is measured in units of sysconf(_SC_CLK_TCK) ticks per second.
+ *
+ * The only tricky bit is that the value returned (of type clock_t) is a
+ * signed integer, which may wrap round.  It is not defined exactly how it
+ * does this... but it is generally assumed that this_sample - last_sample will
+ * give the time between the samples.
+ *
+ * The qtime_t value is in nano-seconds.
+ *
+ * The result from times() is in units of sysconf(_SC_CLK_TCK).
+ *
+ * NB: it is assumed that qt_craft_monotonic will be called often enough to
+ *     ensure that it is not fooled by the clock wrapping round.
+ *
+ *     Assuming that clock_t is a signed 32-bit integer, which is kept +ve,
+ *     then the clock wraps round in 2^31 ticks which is:
+ *
+ *       at     1,000 ticks/sec: > 24 days !
+ *       at 1,000,000 ticks/sec: > 35 minutes
+ *
+ *     So this should be a safe assumption -- particularly as 60, 100, 250 and
+ *     1000 ticks per second appear to be the popular options.
+ *
+ *     For safety, this asserts that the value is <= 1,000,000.
+ */
+
+#ifdef GNU_LINUX
+#define TIMES_TAKES_NULL 1
+#else
+#undef  TIMES_TAKES_NULL
+#endif
+
+static uint64_t monotonic          = 0 ;  /* monotonic clock in _SC_CLK_TCK's */
+static uint64_t last_times_sample  = 0 ;  /* last value returned by times()   */
+
+static int64_t  times_clk_tcks     = 0 ;  /* sysconf(_SC_CLK_TCK)             */
+static qtime_t  times_scale_q      = 0 ;  /* 10**9 / times_clk_tcks           */
+static qtime_t  times_scale_r      = 0 ;  /* 10**9 % times_clk_tcks           */
+
+qtime_t
+qt_craft_monotonic(void) {
+  struct tms dummy ;
+  uint64_t   this_times_sample ;
+
+  /* No errors are defined for times(), but a return of -1 is defined   */
+  /* to indicate an error condition, with errno saying what it is !     */
+  /*                                                                    */
+  /* The following deals carefully with this -- cannot afford for the   */
+  /* clock either to jump or to get stuck !                             */
+
+#ifdef TIMES_TAKES_NULL
+  this_times_sample = times(NULL) ;     /* assume this saves effort !   */
+#else
+  this_times_sample = times(&dummy) ;
+#endif
+
+  if (this_times_sample == (clock_t)-1)
+    {
+       errno = 0 ;
+       this_times_sample = times(&dummy) ;
+       if (errno != 0)
+         zabort_errno("times() failed") ;
+    } ;
+
+
+  if (times_clk_tcks == 0)      /* Is zero until it's initialized       */
+    {
+      lldiv_t qr ;
+      confirm(sizeof(qtime_t) <= sizeof(long long int)) ;
+
+      times_clk_tcks = sysconf(_SC_CLK_TCK) ;
+      passert((times_clk_tcks > 0) && (times_clk_tcks <= 1000000)) ;
+
+      qr = lldiv(QTIME_SECOND, times_clk_tcks) ;
+      times_scale_q = qr.quot ;
+      times_scale_r = qr.rem ;
+
+      last_times_sample = this_times_sample ;
+    } ;
+
+  monotonic += (this_times_sample - last_times_sample) ;
+
+  if (times_scale_r == 0)
+    return monotonic * times_scale_q ;
+  else
+    return (monotonic * times_scale_q) +
+                                ((monotonic * times_scale_r) / times_clk_tcks) ;
+} ;
diff --git a/lib/qtime.h b/lib/qtime.h
new file mode 100644
index 00000000..a9e635d1
--- /dev/null
+++ b/lib/qtime.h
@@ -0,0 +1,213 @@
+/* Quagga Realtime Clock handling -- header
+ * Copyright (C) 2009 Chris Hall (GMCH), Highwayman
+ *
+ * This file is part of GNU Zebra.
+ *
+ * GNU Zebra is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published
+ * by the Free Software Foundation; either version 2, or (at your
+ * option) any later version.
+ *
+ * GNU Zebra is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Zebra; see the file COPYING.  If not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#ifndef _ZEBRA_QTIME_H
+#define _ZEBRA_QTIME_H
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <time.h>
+#include <sys/time.h>
+#include <unistd.h>
+
+#include "zassert.h"
+#include "config.h"
+
+#ifndef Inline
+#define Inline static inline
+#endif
+
+/*==============================================================================
+ * qtime_t -- signed 64-bit integer.
+ *
+ * The various time functions work in terms of the structures:
+ *
+ *   timespec   -- tv_secs    seconds
+ *                 tv_nsecs   nano-seconds
+ *
+ *   timeval    -- tv_secs    seconds
+ *                 tv_usecs   micro-seconds
+ *
+ * Given a 64-bit integer it is much easier to do operations on a 64 bit
+ * (signed) nano-second value.  That gives 34 bits for the seconds count, which
+ * is > 290 years.
+ */
+
+typedef int64_t qtime_t ;
+
+/* A qtime_t second       123456789 -- nano-seconds             */
+#define QTIME_SECOND     1000000000
+#define TIMESPEC_SECOND  1000000000
+#define TIMEVAL_SECOND   1000000
+
+/* Macro to convert time in seconds to a qtime_t                */
+#define QTIME(s) ((qtime_t)((s) * QTIME_SECOND))
+
+Inline qtime_t
+timespec2qtime(struct timespec* p_ts) ;
+
+Inline qtime_t
+timeval2qtime(struct timeval* p_tv) ;
+
+Inline struct timespec*
+qtime2timespec(struct timespec* p_ts, qtime_t qt) ;
+
+Inline struct timeval*
+qtime2timeval(struct timeval* p_tv, qtime_t qt) ;
+
+/*==============================================================================
+ * Clocks.
+ *
+ * Here is support for:
+ *
+ *   * System Clock
+ *
+ *     This can be read using either clock_gettime(CLOCK_REALTIME, &ts) or
+ *     gettimeofday(&tv, NULL) -- which (are believed to) return the same clock,
+ *     but in different units.
+ *
+ *   * Monotonic Clock
+ *
+ *     Using clock_gettime(CLOCK_MONOTONIC, &ts) if it is available, otherwise
+ *     a manufactured equivalent using times().
+ */
+
+Inline qtime_t
+qt_get_timeofday(void) ;        /* gettimeofday(&tv, NULL)              */
+
+Inline qtime_t
+qt_get_realtime(void) ;         /* clock_gettime(CLOCK_REALTIME, &ts)   */
+
+Inline qtime_t
+qt_get_monotonic(void) ;        /* clock_gettime(CLOCK_MONOTONIC, &ts   */
+                                /* OR equivalent using times()          */
+
+/* Function to manufacture a monotonic clock.   */
+extern qtime_t qt_craft_monotonic(void) ;
+
+/*==============================================================================
+ * Inline conversion functions
+ */
+
+/* Convert timespec to qtime_t
+ *
+ * Returns qtime_t value.
+ */
+Inline qtime_t
+timespec2qtime(struct timespec* p_ts)
+{
+  return ((qtime_t)(p_ts->tv_sec) * QTIME_SECOND) + p_ts->tv_nsec ;
+} ;
+
+/* Convert timeval to qtime_t
+ *
+ * Returns qtime_t value.
+ */
+Inline qtime_t
+timeval2qtime(struct timeval* p_tv)
+{
+  return ((qtime_t)(p_tv->tv_sec) * QTIME_SECOND) + (p_tv->tv_usec * 1000) ;
+} ;
+
+/* Convert qtime_t to timespec
+ *
+ * Takes address of struct timespec and returns that address.
+ */
+Inline struct timespec*
+qtime2timespec(struct timespec* p_ts, qtime_t qt)
+{
+  lldiv_t imd = lldiv(qt, QTIME_SECOND) ;
+  p_ts->tv_sec  = imd.quot ;
+  p_ts->tv_nsec = imd.rem ;
+
+  return p_ts ;
+} ;
+
+/* Convert timespec to qtime_t
+ *
+ * Takes address of struct timespec and returns that address.
+ */
+Inline struct timeval*
+qtime2timeval(struct timeval* p_tv, qtime_t qt)
+{
+  lldiv_t imd = lldiv(qt, QTIME_SECOND) ;
+  p_tv->tv_sec  = imd.quot ;
+  p_tv->tv_usec = imd.rem / 1000 ;
+
+  return p_tv ;
+} ;
+
+/*==============================================================================
+ * Inline Clock Functions.
+ */
+
+/* Read given clock & return a qtime_t value.
+ *
+ * Crunch, zabbort_errno, if fails: cannot continue with broken time value !
+ */
+
+Inline qtime_t
+qt_clock_gettime(clockid_t clock_id)
+{
+  struct timespec ts ;
+
+  if (clock_gettime(clock_id, &ts) != 0)
+    zabort_errno("clock_gettime failed") ;
+
+  return timespec2qtime(&ts) ;
+} ;
+
+/* gettimeofday(&tv, NULL) -- returning qtime_t value
+ */
+Inline qtime_t
+qt_get_timeofday(void)
+{
+  struct timeval tv ;
+  gettimeofday(&tv, NULL) ;
+  return timeval2qtime(&tv) ;
+}
+
+/* clock_gettime(CLOCK_REALTIME, &ts) -- returning qtime_t value
+ *
+ * Crunch, zabbort_errno, if fails: cannot continue with broken time value !
+ */
+Inline qtime_t
+qt_get_realtime(void)
+{
+  return qt_clock_gettime(CLOCK_REALTIME) ;
+} ;
+
+/* clock_gettime(CLOCK_MONOTONIC, &ts) OR qt_craft_monotonic()
+ *                                                   -- returning qtime_t value
+ *
+ * Crunch, zabbort_errno, if fails: cannot continue with broken time value !
+ */
+Inline qtime_t
+qt_get_monotonic(void)
+{
+#ifdef HAVE_CLOCK_MONOTONIC
+  return qt_clock_gettime(CLOCK_MONOTONIC) ;
+#else
+  return qt_craft_monotonic() ;
+#endif
+} ;
+
+#endif /* _ZEBRA_QTIME_H */
diff --git a/lib/zassert.h b/lib/zassert.h
index 79126760..26b67da6 100644
--- a/lib/zassert.h
+++ b/lib/zassert.h
@@ -21,7 +21,45 @@ extern void _zlog_assert_failed (const char *assertion, const char *file,
 			    (_zlog_assert_failed(#EX, __FILE__, __LINE__, \
 						 __ASSERT_FUNCTION), 0)))
 
+/* Implicitly *permanent* assert() -- irrespective of NDEBUG    */
 #undef assert
 #define assert(EX) zassert(EX)
 
+/* Explicitly permanent assert()                                */
+#define passert(EX) zassert(EX)
+
+/* NDEBUG time assert()                                         */
+#ifndef NDEBUG
+#define dassert(EX) zassert(EX)
+#else
+#define dassert(EX)
+#endif
+
+/* TODO: implement _zlog_abort() to give required messages      */
+
+/* Abort with message                                           */
+#define zabort(MS) _zlog_assert_failed(MS, __FILE__, __LINE__, \
+                                                              __ASSERT_FUNCTION)
+
+/* Abort with message and errno and strerror() thereof          */
+#define zabort_errno(MS) _zlog_assert_failed(MS, __FILE__, __LINE__, \
+                                                              __ASSERT_FUNCTION)
+
+/* Abort with message and given error and strerror() thereof    */
+#define zabort_err(MS, ERR) _zlog_assert_failed(MS, __FILE__, __LINE__, \
+                                                              __ASSERT_FUNCTION)
+
+/*==============================================================================
+ * Compile time CONFIRM gizmo
+ *
+ * Two forms:  CONFIRM(e) for use at top (file) level
+ *             confirm(e) for use inside compound statements
+ */
+#ifndef CONFIRM
+
+ #define CONFIRM(e)  extern void CONFIRMATION(char CONFIRM[(e) ? 1 : -1]) ;
+ #define confirm(e)  { CONFIRM(e) }
+
+#endif
+
 #endif /* _QUAGGA_ASSERT_H */