Merge commit 'origin/bfd'

11 files changed, 474 insertions, 18 deletions

diff --git a/lib/birdlib.h b/lib/birdlib.h
index 7e6e8526..b7a5a6a6 100644
--- a/lib/birdlib.h
+++ b/lib/birdlib.h
@@ -10,6 +10,7 @@
 #define _BIRD_BIRDLIB_H_
 
 #include "timer.h"
+#include "alloca.h"
 
 /* Ugly structure offset handling macros */
 
@@ -19,12 +20,14 @@
 
 /* Utility macros */
 
-#ifdef PARSER
 #define _MIN(a,b) (((a)<(b))?(a):(b))
 #define _MAX(a,b) (((a)>(b))?(a):(b))
-#else
-#define MIN(a,b) (((a)<(b))?(a):(b))
-#define MAX(a,b) (((a)>(b))?(a):(b))
+
+#ifndef PARSER
+#undef MIN
+#undef MAX
+#define MIN(a,b) _MIN(a,b)
+#define MAX(a,b) _MAX(a,b)
 #endif
 
 #define ABS(a)   ((a)>=0 ? (a) : -(a))
@@ -40,24 +43,61 @@
 #define IP_VERSION 6
 #endif
 
+
 /* Macros for gcc attributes */
 
 #define NORET __attribute__((noreturn))
 #define UNUSED __attribute__((unused))
 
+
+/* Microsecond time */
+
+typedef s64 btime;
+
+#define _S	*1000000
+#define _MS	*1000
+#define _US	*1
+#define TO_S	/1000000
+#define TO_MS	/1000
+#define TO_US	/1
+
+#ifndef PARSER
+#define S	_S
+#define MS	_MS
+#define US	_US
+#endif
+
+
 /* Logging and dying */
 
+typedef struct buffer {
+  byte *start;
+  byte *pos;
+  byte *end;
+} buffer;
+
+#define STACK_BUFFER_INIT(buf,size)		\
+  do {						\
+    buf.start = alloca(size);			\
+    buf.pos = buf.start;			\
+    buf.end = buf.start + size;			\
+  } while(0)
+
+#define LOG_BUFFER_INIT(buf)			\
+  STACK_BUFFER_INIT(buf, LOG_BUFFER_SIZE)
+
+#define LOG_BUFFER_SIZE 1024
+
+
 struct rate_limit {
   bird_clock_t timestamp;
   int count;
 };
 
 #define log log_msg
-void log_reset(void);
-void log_commit(int class);
+void log_commit(int class, buffer *buf);
 void log_msg(char *msg, ...);
 void log_rl(struct rate_limit *rl, char *msg, ...);
-void logn(char *msg, ...);
 void die(char *msg, ...) NORET;
 void bug(char *msg, ...) NORET;
 
diff --git a/lib/buffer.h b/lib/buffer.h
new file mode 100644
index 00000000..cf073e88
--- /dev/null
+++ b/lib/buffer.h
@@ -0,0 +1,35 @@
+
+#define BUFFER(type)		struct { type *data; uint used, size; }
+
+#define BUFFER_SIZE(v)		((v).size * sizeof(* (v).data))
+
+#define BUFFER_INIT(v,pool,isize)					\
+  ({									\
+    (v).used = 0;							\
+    (v).size = (isize);							\
+    (v).data = mb_alloc(pool, BUFFER_SIZE(v));				\
+  })
+
+#define BUFFER_SET(v,nsize)						\
+  ({									\
+    (v).used = (nsize);							\
+    if ((v).used > (v).size)						\
+      buffer_realloc((void **) &((v).data), &((v).size), (v).used, sizeof(* (v).data)); \
+  })
+
+#define BUFFER_INC(v,step)						\
+  ({									\
+    uint _o = (v).used;							\
+    BUFFER_SET(v, (v).used + (step));					\
+    (v).data + _o;							\
+  })
+
+#define BUFFER_DEC(v,step)	({ (v).used -= (step); })
+
+#define BUFFER_PUSH(v)		(*BUFFER_INC(v,1))
+
+#define BUFFER_POP(v)		BUFFER_DEC(v,1)
+
+#define BUFFER_FLUSH(v)		({ (v).used = 0; })
+
+
diff --git a/lib/hash.h b/lib/hash.h
new file mode 100644
index 00000000..3ac9eebd
--- /dev/null
+++ b/lib/hash.h
@@ -0,0 +1,123 @@
+
+
+#define HASH(type)		struct { type **data; uint count, order; }
+#define HASH_TYPE(v)		typeof(** (v).data)
+#define HASH_SIZE(v)		(1 << (v).order)
+#define HASH_MASK(v)		((1 << (v).order)-1)
+
+
+#define HASH_INIT(v,pool,init_order)					\
+  ({									\
+    (v).count = 0;							\
+    (v).order = (init_order);						\
+    (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data));	\
+  })
+
+#define HASH_FIND(v,id,key...)						\
+  ({									\
+    uint _h = id##_FN((key)) & HASH_MASK(v);				\
+    HASH_TYPE(v) *_n = (v).data[_h];					\
+    while (_n && !id##_EQ(id##_KEY(_n), (key)))				\
+      _n = id##_NEXT(_n);						\
+    _n;									\
+  })
+
+#define HASH_INSERT(v,id,node)						\
+  ({									\
+    uint _h = id##_FN(id##_KEY((node))) & HASH_MASK(v);			\
+    HASH_TYPE(v) **_nn = (v).data + _h;					\
+    id##_NEXT(node) = *_nn;						\
+    *_nn = node;							\
+    (v).count++;							\
+  })
+
+#define HASH_DO_REMOVE(v,id,_nn)					\
+  ({									\
+    HASH_TYPE(v) *_n = *_nn;						\
+    if (_n)								\
+    {									\
+      *_nn = id##_NEXT(_n);						\
+      (v).count--;							\
+    }									\
+    _n;									\
+  })
+
+#define HASH_DELETE(v,id,key...)					\
+  ({									\
+    uint _h = id##_FN((key)) & HASH_MASK(v);				\
+    HASH_TYPE(v) **_nn = (v).data + _h;					\
+									\
+    while ((*_nn) && !id##_EQ(id##_KEY((*_nn)), (key)))			\
+      _nn = &(id##_NEXT((*_nn)));					\
+									\
+    HASH_DO_REMOVE(v,id,_nn);						\
+  })
+
+#define HASH_REMOVE(v,id,node)						\
+  ({									\
+    uint _h = id##_FN(id##_KEY((node))) & HASH_MASK(v);			\
+    HASH_TYPE(v) **_nn = (v).data + _h;					\
+									\
+    while ((*_nn) && (*_nn != (node)))					\
+      _nn = &(id##_NEXT((*_nn)));					\
+									\
+    HASH_DO_REMOVE(v,id,_nn);						\
+  })
+
+
+#define HASH_REHASH(v,id,pool,step)					\
+  ({									\
+    HASH_TYPE(v) *_n, *_n2, **_od;					\
+    uint _i, _s;							\
+									\
+    _s = HASH_SIZE(v);							\
+    _od = (v).data;							\
+    (v).count = 0;							\
+    (v).order += (step);						\
+    (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data));	\
+									\
+    for (_i = 0; _i < _s; _i++)						\
+      for (_n = _od[_i]; _n && (_n2 = id##_NEXT(_n), 1); _n = _n2)	\
+	HASH_INSERT(v, id, _n);						\
+									\
+    mb_free(_od);							\
+  })
+
+#define HASH_DEFINE_REHASH_FN(id, type)					\
+  static void id##_REHASH_FN(void *v, pool *p, int step)		\
+  { HASH_REHASH(* (HASH(type) *) v, id, p, step); }
+
+#define HASH_TRY_REHASH_UP(v,id,pool)					\
+  ({									\
+    if (((v).order < id##_REHASH_MAX) && ((v).count > HASH_SIZE(v)))	\
+      id##_REHASH_FN(&v, pool, 1);					\
+  })
+
+#define HASH_TRY_REHASH_DOWN(v,id,pool)					\
+  ({									\
+    if (((v).order > id##_REHASH_MIN) && ((v).count < HASH_SIZE(v)/2))	\
+      id##_REHASH_FN(&v, pool, -1);					\
+  })
+
+#define HASH_WALK(v,next,n)						\
+  do {									\
+    HASH_TYPE(v) *n;							\
+    uint _i;								\
+    uint _s = HASH_SIZE(v);						\
+    for (_i = 0; _i < _s; _i++)						\
+      for (n = (v).data[_i]; n; n = n->next)
+
+#define HASH_WALK_END } while (0)
+
+
+#define HASH_WALK_DELSAFE(v,next,n)					\
+  do {									\
+    HASH_TYPE(v) *n, *_next;						\
+    uint _i;								\
+    uint _s = HASH_SIZE(v);						\
+    for (_i = 0; _i < _s; _i++)						\
+      for (n = (v).data[_i]; n && (_next = n->next, 1); n = _next)
+
+#define HASH_WALK_DELSAFE_END } while (0)
+
+
diff --git a/lib/heap.h b/lib/heap.h
new file mode 100644
index 00000000..c8c3d348
--- /dev/null
+++ b/lib/heap.h
@@ -0,0 +1,156 @@
+/*
+ *	UCW Library -- Universal Heap Macros
+ *
+ *	(c) 2001 Martin Mares <mj@ucw.cz>
+ *	(c) 2005 Tomas Valla <tom@ucw.cz>
+ *
+ *	This software may be freely distributed and used according to the terms
+ *	of the GNU Lesser General Public License.
+ */
+
+/**
+ * [[intro]]
+ * Introduction
+ * ------------
+ *
+ * Binary heap is a simple data structure, which for example supports efficient insertions, deletions
+ * and access to the minimal inserted item. We define several macros for such operations.
+ * Note that because of simplicity of heaps, we have decided to define direct macros instead
+ * of a <<generic:,macro generator>> as for several other data structures in the Libucw.
+ *
+ * A heap is represented by a number of elements and by an array of values. Beware that we
+ * index this array from one, not from zero as do the standard C arrays.
+ *
+ * Most macros use these parameters:
+ *
+ * - @type - the type of elements
+ * - @num - a variable (signed or unsigned integer) with the number of elements
+ * - @heap - a C array of type @type; the heap is stored in `heap[1] .. heap[num]`; `heap[0]` is unused
+ * - @less - a callback to compare two element values; `less(x, y)` shall return a non-zero value iff @x is lower than @y
+ * - @swap - a callback to swap two array elements; `swap(heap, i, j, t)` must swap `heap[i]` with `heap[j]` with possible help of temporary variable @t (type @type).
+ *
+ * A valid heap must follow these rules:
+ *
+ * - `num >= 0`
+ * - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]`
+ *
+ * The first element `heap[1]` is always lower or equal to all other elements.
+ *
+ * [[macros]]
+ * Macros
+ * ------
+ */
+
+/* For internal usage. */
+#define HEAP_BUBBLE_DOWN_J(heap,num,less,swap)						\
+  for (;;)										\
+    {											\
+      _l = 2*_j;									\
+      if (_l > num)									\
+	break;										\
+      if (less(heap[_j],heap[_l]) && (_l == num || less(heap[_j],heap[_l+1])))		\
+	break;										\
+      if (_l != num && less(heap[_l+1],heap[_l]))					\
+	_l++;										\
+      swap(heap,_j,_l,x);								\
+      _j = _l;										\
+    }
+
+/* For internal usage. */
+#define HEAP_BUBBLE_UP_J(heap,num,less,swap)						\
+  while (_j > 1)									\
+    {											\
+      _u = _j/2;									\
+      if (less(heap[_u], heap[_j]))							\
+	break;										\
+      swap(heap,_u,_j,x);								\
+      _j = _u;										\
+    }
+
+/**
+ * Shuffle the unordered array @heap of @num elements to become a valid heap. The time complexity is linear.
+ **/
+#define HEAP_INIT(heap,num,type,less,swap)						\
+  do {											\
+    uint _i = num;									\
+    uint _j, _l;										\
+    type x;										\
+    while (_i >= 1)									\
+      {											\
+	_j = _i;									\
+        HEAP_BUBBLE_DOWN_J(heap,num,less,swap)						\
+	_i--;										\
+      }											\
+  } while(0)
+
+/**
+ * Delete the minimum element `heap[1]` in `O(log(n))` time.
+ * The removed value is moved just after the resulting heap (`heap[num + 1]`).
+ **/
+#define HEAP_DELMIN(heap,num,type,less,swap)						\
+  do {											\
+    uint _j, _l;										\
+    type x;										\
+    swap(heap,1,num,x);									\
+    num--;										\
+    _j = 1;										\
+    HEAP_BUBBLE_DOWN_J(heap,num,less,swap);						\
+  } while(0)
+
+/**
+ * Insert `heap[num]` in `O(log(n))` time. The value of @num must be increased before.
+ **/
+#define HEAP_INSERT(heap,num,type,less,swap)						\
+  do {											\
+    uint _j, _u;										\
+    type x;										\
+    _j = num;										\
+    HEAP_BUBBLE_UP_J(heap,num,less,swap);						\
+  } while(0)
+
+/**
+ * If you need to increase the value of `heap[pos]`, just do it and then call this macro to rebuild the heap.
+ * Only `heap[pos]` can be changed, the rest of the array must form a valid heap.
+ * The time complexity is `O(log(n))`.
+ **/
+#define HEAP_INCREASE(heap,num,type,less,swap,pos)					\
+  do {											\
+    uint _j, _l;										\
+    type x;										\
+    _j = pos;										\
+    HEAP_BUBBLE_DOWN_J(heap,num,less,swap);						\
+  } while(0)
+
+/**
+ * If you need to decrease the value of `heap[pos]`, just do it and then call this macro to rebuild the heap.
+ * Only `heap[pos]` can be changed, the rest of the array must form a valid heap.
+ * The time complexity is `O(log(n))`.
+ **/
+#define HEAP_DECREASE(heap,num,type,less,swap,pos)					\
+  do {											\
+    uint _j, _u;										\
+    type x;										\
+    _j = pos;										\
+    HEAP_BUBBLE_UP_J(heap,num,less,swap);						\
+  } while(0)
+
+/**
+ * Delete `heap[pos]` in `O(log(n))` time.
+ **/
+#define HEAP_DELETE(heap,num,type,less,swap,pos)					\
+  do {											\
+    uint _j, _l, _u;									\
+    type x;										\
+    _j = pos;										\
+    swap(heap,_j,num,x);								\
+    num--;										\
+    if (less(heap[_j], heap[num+1]))							\
+      HEAP_BUBBLE_UP_J(heap,num,less,swap)						\
+    else										\
+      HEAP_BUBBLE_DOWN_J(heap,num,less,swap);						\
+  } while(0)
+
+/**
+ * Default swapping macro.
+ **/
+#define HEAP_SWAP(heap,a,b,t) (t=heap[a], heap[a]=heap[b], heap[b]=t)
diff --git a/lib/lists.c b/lib/lists.c
index 6d97ff50..d323a4b6 100644
--- a/lib/lists.c
+++ b/lib/lists.c
@@ -101,6 +101,46 @@ rem_node(node *n)
 }
 
 /**
+ * rem2_node - remove a node from a list, with cleanup
+ * @n: node to be removed
+ *
+ * Removes a node @n from the list it's linked in and resets its pointers to NULL.
+ * Useful if you want to distinguish between linked and unlinked nodes.
+ */
+LIST_INLINE void
+rem2_node(node *n)
+{
+  node *z = n->prev;
+  node *x = n->next;
+
+  z->next = x;
+  x->prev = z;
+  n->next = NULL;
+  n->prev = NULL;
+}
+
+/**
+ * replace_node - replace a node in a list with another one
+ * @old: node to be removed
+ * @new: node to be inserted
+ *
+ * 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.
+ */
+LIST_INLINE void
+replace_node(node *old, node *new)
+{
+  old->next->prev = new;
+  old->prev->next = new;
+
+  new->prev = old->prev;
+  new->next = old->next;
+}
+
+/**
  * init_list - create an empty list
  * @l: list
  *
diff --git a/lib/lists.h b/lib/lists.h
index 0b0fdbe3..9153029c 100644
--- a/lib/lists.h
+++ b/lib/lists.h
@@ -51,6 +51,7 @@ typedef struct list {			/* In fact two overlayed nodes */
 void add_tail(list *, node *);
 void add_head(list *, node *);
 void rem_node(node *);
+void rem2_node(node *);
 void add_tail_list(list *, list *);
 void init_list(list *);
 void insert_node(node *, node *);
diff --git a/lib/printf.c b/lib/printf.c
index 14af1062..41e1cc0d 100644
--- a/lib/printf.c
+++ b/lib/printf.c
@@ -276,7 +276,7 @@ int bvsnprintf(char *buf, int size, const char *fmt, va_list args)
 				ip_ntox(va_arg(args, ip_addr), ipbuf);
 			else {
 				ip_ntop(va_arg(args, ip_addr), ipbuf);
-				if (field_width > 0)
+				if (field_width == 1)
 					field_width = STD_ADDRESS_P_LENGTH;
 			}
 			s = ipbuf;
@@ -410,3 +410,40 @@ int bsnprintf(char * buf, int size, const char *fmt, ...)
   va_end(args);
   return i;
 }
+
+int
+buffer_vprint(buffer *buf, const char *fmt, va_list args)
+{
+  int i = bvsnprintf((char *) buf->pos, buf->end - buf->pos, fmt, args);
+  buf->pos = (i >= 0) ? (buf->pos + i) : buf->end;
+  return i;
+}
+
+int
+buffer_print(buffer *buf, const char *fmt, ...)
+{
+  va_list args;
+  int i;
+
+  va_start(args, fmt);
+  i=bvsnprintf((char *) buf->pos, buf->end - buf->pos, fmt, args);
+  va_end(args);
+
+  buf->pos = (i >= 0) ? (buf->pos + i) : buf->end;
+  return i;
+}
+
+void
+buffer_puts(buffer *buf, const char *str)
+{
+  byte *bp = buf->pos;
+  byte *be = buf->end;
+
+  while (bp < be && *str)
+    *bp++ = *str++;
+
+  if (bp < be)
+    *bp = 0;
+
+  buf->pos = bp;
+}
diff --git a/lib/resource.c b/lib/resource.c
index 42243aa2..bf4b3ae9 100644
--- a/lib/resource.c
+++ b/lib/resource.c
@@ -220,7 +220,8 @@ ralloc(pool *p, struct resclass *c)
   bzero(r, c->size);
 
   r->class = c;
-  add_tail(&p->inside, &r->n);
+  if (p)
+    add_tail(&p->inside, &r->n);
   return r;
 }
 
@@ -366,21 +367,21 @@ mb_allocz(pool *p, unsigned size)
 
 /**
  * mb_realloc - reallocate a memory block
- * @p: pool
  * @m: memory block
  * @size: new size of the block
  *
  * mb_realloc() changes the size of the memory block @m to a given size.
  * The contents will be unchanged to the minimum of the old and new sizes;
- * newly allocated memory will be uninitialized. If @m is NULL, the call
- * is equivalent to mb_alloc(@p, @size).
+ * newly allocated memory will be uninitialized. Contrary to realloc()
+ * behavior, @m must be non-NULL, because the resource pool is inherited
+ * from it.
  *
  * Like mb_alloc(), mb_realloc() also returns a pointer to the memory
- * chunk , not to the resource, hence you have to free it using
+ * chunk, not to the resource, hence you have to free it using
  * mb_free(), not rfree().
  */
 void *
-mb_realloc(pool *p, void *m, unsigned size)
+mb_realloc(void *m, unsigned size)
 {
   struct mblock *ob = NULL;
 
@@ -392,9 +393,7 @@ mb_realloc(pool *p, void *m, unsigned size)
     }
 
   struct mblock *b = xrealloc(ob, sizeof(struct mblock) + size);
-
-  b->r.class = &mb_class;
-  add_tail(&p->inside, &b->r.n);
+  replace_node(&b->r.n, &b->r.n);
   b->size = size;
   return b->data;
 }
@@ -413,3 +412,18 @@ mb_free(void *m)
   rfree(b);
 }
 
+
+
+#define STEP_UP(x) ((x) + (x)/2 + 4)
+
+void
+buffer_realloc(void **buf, unsigned *size, unsigned need, unsigned item_size)
+{
+  unsigned nsize = MIN(*size, need);
+
+  while (nsize < need)
+    nsize = STEP_UP(nsize);
+
+  *buf = mb_realloc(*buf, nsize * item_size);
+  *size = nsize;
+}
diff --git a/lib/resource.h b/lib/resource.h
index 5cb5e274..1a62d389 100644
--- a/lib/resource.h
+++ b/lib/resource.h
@@ -52,7 +52,7 @@ extern pool root_pool;
 
 void *mb_alloc(pool *, unsigned size);
 void *mb_allocz(pool *, unsigned size);
-void *mb_realloc(pool *p, void *m, unsigned size);
+void *mb_realloc(void *m, unsigned size);
 void mb_free(void *);
 
 /* Memory pools with linear allocation */
@@ -78,6 +78,9 @@ void sl_free(slab *, void *);
  * outside resource manager and possibly sysdep code.
  */
 
+void buffer_realloc(void **buf, unsigned *size, unsigned need, unsigned item_size);
+
+
 #ifdef HAVE_LIBDMALLOC
 /*
  * The standard dmalloc macros tend to produce lots of namespace
@@ -103,3 +106,4 @@ void *xrealloc(void *, unsigned);
 #endif
 
 #endif
+
diff --git a/lib/socket.h b/lib/socket.h
index 6e0a769b..780d596b 100644
--- a/lib/socket.h
+++ b/lib/socket.h
@@ -44,6 +44,7 @@ typedef struct birdsock {
   /* laddr and lifindex are valid only if SKF_LADDR_RX flag is set to request it */
 
   int fd;				/* System-dependent data */
+  int index;				/* Index in poll buffer */
   node n;
   void *rbuf_alloc, *tbuf_alloc;
   char *password;				/* Password for MD5 authentication */
@@ -91,6 +92,7 @@ extern int sk_priority_control;	/* Suggested priority for control traffic, shoul
 #define SKF_LADDR_TX	4	/* Allow to specify local address for TX packets */
 #define SKF_TTL_RX	8	/* Report TTL / Hop Limit for RX packets */
 
+#define SKF_THREAD	0x100	/* Socked used in thread, Do not add to main loop */
 
 /*
  *	Socket types		     SA SP DA DP IF  TTL SendTo	(?=may, -=must not, *=must)
diff --git a/lib/string.h b/lib/string.h
index 14eaa360..2c477294 100644
--- a/lib/string.h
+++ b/lib/string.h
@@ -17,6 +17,10 @@ int bvsprintf(char *str, const char *fmt, va_list args);
 int bsnprintf(char *str, int size, const char *fmt, ...);
 int bvsnprintf(char *str, int size, const char *fmt, va_list args);
 
+int buffer_vprint(buffer *buf, const char *fmt, va_list args);
+int buffer_print(buffer *buf, const char *fmt, ...);
+void buffer_puts(buffer *buf, const char *str);
+
 int patmatch(byte *pat, byte *str);
 
 #endif