Initial commit on integrated BIRD

New data types net_addr and variants (in lib/net.h) describing
network addresses (prefix/pxlen). Modifications of FIB structures
to handle these data types and changing everything to use these
data types instead of prefix/pxlen pairs where possible.

The commit is WiP, some protocols are not yet updated (BGP, Kernel),
and the code contains some temporary scaffolding.

Comments are welcome.

7 files changed, 294 insertions, 11 deletions

diff --git a/lib/bitops.c b/lib/bitops.c
index 81586e87..efb8710e 100644
--- a/lib/bitops.c
+++ b/lib/bitops.c
@@ -28,15 +28,15 @@ u32_mkmask(uint n)
  *
  * This function checks whether the given integer @x represents
  * a valid bit mask (binary representation contains first ones, then
- * zeroes) and returns the number of ones or -1 if the mask is invalid.
+ * zeroes) and returns the number of ones or 255 if the mask is invalid.
  */
-int
+uint
 u32_masklen(u32 x)
 {
   int l = 0;
   u32 n = ~x;
 
-  if (n & (n+1)) return -1;
+  if (n & (n+1)) return 255;
   if (x & 0x0000ffff) { x &= 0x0000ffff; l += 16; }
   if (x & 0x00ff00ff) { x &= 0x00ff00ff; l += 8; }
   if (x & 0x0f0f0f0f) { x &= 0x0f0f0f0f; l += 4; }
diff --git a/lib/bitops.h b/lib/bitops.h
index c0ad1a70..82bef699 100644
--- a/lib/bitops.h
+++ b/lib/bitops.h
@@ -19,7 +19,7 @@
  */
 
 u32 u32_mkmask(uint n);
-int u32_masklen(u32 x);
+uint u32_masklen(u32 x);
 
 u32 u32_log2(u32 v);
 
diff --git a/lib/ip.c b/lib/ip.c
index 3dc8919a..6b0b0bc2 100644
--- a/lib/ip.c
+++ b/lib/ip.c
@@ -58,7 +58,7 @@ ip6_mkmask(uint n)
   return a;
 }
 
-int
+uint
 ip6_masklen(ip6_addr *a)
 {
   int i, j, n;
@@ -72,7 +72,7 @@ ip6_masklen(ip6_addr *a)
       n += j;
       while (++i < 4)
 	if (a->addr[i])
-	  return -1;
+	  return 255;
       break;
     }
 
diff --git a/lib/ip.h b/lib/ip.h
index 9ac5798a..9b4400ba 100644
--- a/lib/ip.h
+++ b/lib/ip.h
@@ -30,6 +30,9 @@
 #define IP4_NONE		_MI4(0)
 #define IP6_NONE		_MI6(0,0,0,0)
 
+#define IP4_MAX_PREFIX_LENGTH	32
+#define IP6_MAX_PREFIX_LENGTH	128
+
 #define IP4_MIN_MTU		576
 #define IP6_MIN_MTU		1280
 
@@ -39,17 +42,14 @@
 #define IP6_HEADER_LENGTH	40
 #define UDP_HEADER_LENGTH	8
 
-
 #ifdef IPV6
 #define MAX_PREFIX_LENGTH 128
 #define BITS_PER_IP_ADDRESS 128
 #define STD_ADDRESS_P_LENGTH 39
-#define SIZE_OF_IP_HEADER 40
 #else
 #define MAX_PREFIX_LENGTH 32
 #define BITS_PER_IP_ADDRESS 32
 #define STD_ADDRESS_P_LENGTH 15
-#define SIZE_OF_IP_HEADER 24
 #endif
 
 
@@ -319,11 +319,11 @@ static inline int ipa_classify_net(ip_addr a)
 static inline ip4_addr ip4_mkmask(uint n)
 { return _MI4(u32_mkmask(n)); }
 
-static inline int ip4_masklen(ip4_addr a)
+static inline uint ip4_masklen(ip4_addr a)
 { return u32_masklen(_I(a)); }
 
 ip6_addr ip6_mkmask(uint n);
-int ip6_masklen(ip6_addr *a);
+uint ip6_masklen(ip6_addr *a);
 
 /* ipX_pxlen() requires that x != y */
 static inline uint ip4_pxlen(ip4_addr a, ip4_addr b)
@@ -345,6 +345,18 @@ static inline u32 ip4_getbit(ip4_addr a, uint pos)
 static inline u32 ip6_getbit(ip6_addr a, uint pos)
 { return a.addr[pos / 32] & (0x80000000 >> (pos % 32)); }
 
+static inline u32 ip4_setbit(ip4_addr *a, uint pos)
+{ return _I(*a) |= (0x80000000 >> pos); }
+
+static inline u32 ip6_setbit(ip6_addr *a, uint pos)
+{ return a->addr[pos / 32] |= (0x80000000 >> (pos % 32)); }
+
+static inline u32 ip4_clrbit(ip4_addr *a, uint pos)
+{ return _I(*a) &= ~(0x80000000 >> pos); }
+
+static inline u32 ip6_clrbit(ip6_addr *a, uint pos)
+{ return a->addr[pos / 32] &= ~(0x80000000 >> (pos % 32)); }
+
 static inline ip4_addr ip4_opposite_m1(ip4_addr a)
 { return _MI4(_I(a) ^ 1); }
 
@@ -364,6 +376,8 @@ ip4_addr ip4_class_mask(ip4_addr ad);
 #define ipa_masklen(x) ip6_masklen(&x)
 #define ipa_pxlen(x,y) ip6_pxlen(x,y)
 #define ipa_getbit(x,n) ip6_getbit(x,n)
+#define ipa_setbit(x,n) ip6_setbit(x,n)
+#define ipa_clrbit(x,n) ip6_clrbit(x,n)
 #define ipa_opposite_m1(x) ip6_opposite_m1(x)
 #define ipa_opposite_m2(x) ip6_opposite_m2(x)
 #else
@@ -371,6 +385,8 @@ ip4_addr ip4_class_mask(ip4_addr ad);
 #define ipa_masklen(x) ip4_masklen(x)
 #define ipa_pxlen(x,y) ip4_pxlen(x,y)
 #define ipa_getbit(x,n) ip4_getbit(x,n)
+#define ipa_setbit(x,n) ip4_setbit(x,n)
+#define ipa_clrbit(x,n) ip4_clrbit(x,n)
 #define ipa_opposite_m1(x) ip4_opposite_m1(x)
 #define ipa_opposite_m2(x) ip4_opposite_m2(x)
 #endif
diff --git a/lib/net.c b/lib/net.c
new file mode 100644
index 00000000..87d4aa16
--- /dev/null
+++ b/lib/net.c
@@ -0,0 +1,47 @@
+
+#include "nest/bird.h"
+#include "lib/ip.h"
+#include "lib/net.h"
+
+const u16 net_addr_length[] = {
+  [NET_IP4] = sizeof(net_addr_ip4),
+  [NET_IP6] = sizeof(net_addr_ip6),
+  [NET_VPN4] = sizeof(net_addr_vpn4),
+  [NET_VPN6] = sizeof(net_addr_vpn6)
+}
+
+char *
+net_format(const net_addr *N, char *buf, int buflen)
+{
+  net_addr_union *n = (void *) N;
+
+  /* FIXME: quick hack */
+  switch (n->n.type)
+  {
+  case NET_IP4:
+    return bsnprintf(buf, buflen, "%I/%d", n->ip4.prefix, n->ip4.pxlen);
+  case NET_IP6:
+    return bsnprintf(buf, buflen, "%I/%d", n->ip6.prefix, n->ip6.pxlen);
+  case NET_VPN4:
+    return bsnprintf(buf, buflen, "%u:%u %I/%d", (u32) (n->vpn4.rd >> 32), (u32) n->vpn4.rd, n->vpn4.prefix, n->vpn4.pxlen);
+  case NET_VPN6:
+    return bsnprintf(buf, buflen, "%u:%u %I/%d", (u32) (n->vpn6.rd >> 32), (u32) n->vpn6.rd, n->vpn6.prefix, n->vpn6.pxlen);
+  }
+}
+
+int
+net_classify(const net_addr *N)
+{
+  net_addr_union *n = (void *) N;
+
+  switch (n->n.type)
+  {
+  case NET_IP4:
+  case NET_VPN4:
+    return ip4_zero(n->ip4.prefix) ? (IADDR_HOST | SCOPE_UNIVERSE) : ip4_classify(n->ip4.prefix);
+
+  case NET_IP6:
+  case NET_VPN6:
+    return ip6_zero(n->ip6.prefix) ? (IADDR_HOST | SCOPE_UNIVERSE) : ip6_classify(n->ip6.prefix);
+  }
+}
diff --git a/lib/net.h b/lib/net.h
new file mode 100644
index 00000000..f6bf95f3
--- /dev/null
+++ b/lib/net.h
@@ -0,0 +1,214 @@
+/*
+ *	BIRD Internet Routing Daemon -- Network addresses
+ *
+ *	(c) 2015 Ondrej Zajicek <santiago@crfreenet.org>
+ *	(c) 2015 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#ifndef _BIRD_NET_H_
+#define _BIRD_NET_H_
+
+#include "lib/ip.h"
+
+
+#define NET_IP4		1
+#define NET_IP6		2
+#define NET_VPN4	3
+#define NET_VPN6	4
+#define NET_MAX		5
+
+
+typedef struct net_addr {
+  u8 type;
+  u8 pxlen;
+  u16 length;
+  u64 align[0];
+  u32 space[4];
+} net_addr;
+
+typedef struct net_addr_ip4 {
+  u8 type;
+  u8 pxlen;
+  u16 length;
+  ip4_addr prefix;
+} net_addr_ip4;
+
+typedef struct net_addr_ip6 {
+  u8 type;
+  u8 pxlen;
+  u16 length;
+  ip6_addr prefix;
+} net_addr_ip6;
+
+typedef struct net_addr_vpn4 {
+  u8 type;
+  u8 pxlen;
+  u16 length;
+  ip4_addr prefix;
+  u64 rd;
+} net_addr_vpn4;
+
+typedef struct net_addr_vpn6 {
+  u8 type;
+  u8 pxlen;
+  u16 length;
+  ip6_addr prefix;
+  u64 rd;
+} net_addr_vpn6;
+
+
+typedef union net_addr_union {
+  net_addr n;
+  net_addr_ip4 ip4;
+  net_addr_ip6 ip6;
+  net_addr_vpn4 vpn4;
+  net_addr_vpn6 vpn6;
+} net_addr_union;
+
+
+extern const u16 net_addr_length[];
+
+
+#define NET_ADDR_IP4(prefix,pxlen) \
+  ((net_addr_ip4) { NET_IP4, pxlen, sizeof(net_addr_ip4), prefix })
+
+#define NET_ADDR_IP6(prefix,pxlen) \
+  ((net_addr_ip6) { NET_IP6, pxlen, sizeof(net_addr_ip6), prefix })
+
+#define NET_ADDR_VPN4(prefix,pxlen,rd) \
+  ((net_addr_vpn4) { NET_VPN4, pxlen, sizeof(net_addr_vpn4), prefix, rd })
+
+#define NET_ADDR_VPN6(prefix,pxlen,rd) \
+  ((net_addr_vpn6) { NET_VPN6, pxlen, sizeof(net_addr_vpn6), prefix, rd })
+
+
+static inline void net_fill_ip4(net_addr *a, ip4_addr prefix, uint pxlen)
+{ *(net_addr_ip4 *)a = NET_ADDR_IP4(prefix, pxlen); }
+
+static inline void net_fill_ip6(net_addr *a, ip6_addr prefix, uint pxlen)
+{ *(net_addr_ip6 *)a = NET_ADDR_IP6(prefix, pxlen); }
+
+static inline void net_fill_vpn4(net_addr *a, ip4_addr prefix, uint pxlen, u64 rd)
+{ *(net_addr_vpn4 *)a = NET_ADDR_VPN4(prefix, pxlen, rd); }
+
+static inline void net_fill_vpn6(net_addr *a, ip6_addr prefix, uint pxlen, u64 rd)
+{ *(net_addr_vpn6 *)a = NET_ADDR_VPN6(prefix, pxlen, rd); }
+
+static inline void net_fill_ipa(net_addr *a, ip_addr prefix, uint pxlen)
+{
+  if (ipa_is_ip4(prefix))
+    net_fill_ip4(a, ipa_to_ip4(prefix), pxlen);
+  else
+    net_fill_ip6(a, ipa_to_ip6(prefix), pxlen);
+}
+
+static inline ip4_addr net4_prefix(const net_addr *a)
+{ return ((net_addr_ip4 *) a)->prefix; }
+
+static inline ip6_addr net6_prefix(const net_addr *a)
+{ return ((net_addr_ip6 *) a)->prefix; }
+
+static inline ip_addr net_prefix(const net_addr *a)
+{
+  switch (a->type)
+  {
+  case NET_IP4:
+  case NET_VPN4: return ipa_from_ip4(net4_prefix(a));
+  case NET_IP6:
+  case NET_VPN6: return ipa_from_ip6(net6_prefix(a));
+  default: return IPA_NONE;
+  }
+}
+
+static inline uint net4_pxlen(const net_addr *a)
+{ return a->pxlen; }
+
+static inline uint net6_pxlen(const net_addr *a)
+{ return a->pxlen; }
+
+static inline uint net_pxlen(const net_addr *a)
+{ return a->pxlen; }
+
+
+static inline int net_equal(const net_addr *a, const net_addr *b)
+{ return (a->length == b->length) && !memcmp(a, b, a->length); }
+
+static inline int net_equal_ip4(const net_addr_ip4 *a, const net_addr_ip4 *b)
+{ return !memcmp(a, b, sizeof(net_addr_ip4)); }
+
+static inline int net_equal_ip6(const net_addr_ip6 *a, const net_addr_ip6 *b)
+{ return !memcmp(a, b, sizeof(net_addr_ip6)); }
+
+static inline int net_equal_vpn4(const net_addr_vpn4 *a, const net_addr_vpn4 *b)
+{ return !memcmp(a, b, sizeof(net_addr_vpn4)); }
+
+static inline int net_equal_vpn6(const net_addr_vpn6 *a, const net_addr_vpn6 *b)
+{ return !memcmp(a, b, sizeof(net_addr_vpn6)); }
+
+
+static inline int net_zero_ip4(const net_addr_ip4 *a)
+{ return !a->pxlen && ip4_zero(a->prefix); }
+
+static inline int net_zero_ip6(const net_addr_ip6 *a)
+{ return !a->pxlen && ip6_zero(a->prefix); }
+
+static inline int net_zero_vpn4(const net_addr_vpn4 *a)
+{ return !a->pxlen && ip4_zero(a->prefix) && !a->rd; }
+
+static inline int net_zero_vpn6(const net_addr_vpn6 *a)
+{ return !a->pxlen && ip6_zero(a->prefix) && !a->rd; }
+
+
+static inline void net_copy(net_addr *dst, const net_addr *src)
+{ memcpy(dst, src, src->length); }
+
+static inline void net_copy_ip4(net_addr_ip4 *dst, const net_addr_ip4 *src)
+{ memcpy(dst, src, sizeof(net_addr_ip4)); }
+
+static inline void net_copy_ip6(net_addr_ip6 *dst, const net_addr_ip6 *src)
+{ memcpy(dst, src, sizeof(net_addr_ip6)); }
+
+static inline void net_copy_vpn4(net_addr_vpn4 *dst, const net_addr_vpn4 *src)
+{ memcpy(dst, src, sizeof(net_addr_vpn4)); }
+
+static inline void net_copy_vpn6(net_addr_vpn6 *dst, const net_addr_vpn6 *src)
+{ memcpy(dst, src, sizeof(net_addr_vpn6)); }
+
+
+static inline u32 net_hash_ip4(const net_addr_ip4 *n)
+{ return ip4_hash(n->prefix) ^ ((u32) n->pxlen << 26); }
+
+static inline u32 net_hash_ip6(const net_addr_ip6 *n)
+{ return ip6_hash(n->prefix) ^ ((u32) n->pxlen << 26); }
+
+/* XXXX */
+static inline u32 u64_hash(u32 a)
+{ return u32_hash(a); }
+
+static inline u32 net_hash_vpn4(const net_addr_vpn4 *n)
+{ return ip4_hash(n->prefix) ^ ((u32) n->pxlen << 26) ^ u64_hash(n->rd); }
+
+static inline u32 net_hash_vpn6(const net_addr_vpn6 *n)
+{ return ip6_hash(n->prefix) ^ ((u32) n->pxlen << 26) ^ u64_hash(n->rd); }
+
+
+static inline void net_normalize_ip4(net_addr_ip4 *n)
+{ n->prefix = ip4_and(n->prefix, ip4_mkmask(n->pxlen)); }
+
+static inline void net_normalize_ip6(net_addr_ip6 *n)
+{ n->prefix = ip6_and(n->prefix, ip6_mkmask(n->pxlen)); }
+
+void net_normalize(net_addr *N);
+
+int net_validate(const net_addr *N);
+int net_classify(const net_addr *N);
+char * net_format(const net_addr *N, char *buf, int buflen);
+
+
+
+#endif
+
+
+
diff --git a/lib/printf.c b/lib/printf.c
index e4cc3006..1a8c2a90 100644
--- a/lib/printf.c
+++ b/lib/printf.c
@@ -236,6 +236,12 @@ int bvsnprintf(char *buf, int size, const char *fmt, va_list args)
 		case 'M':
 			s = strerror(va_arg(args, int));
 			goto str;
+		case 'N':
+			if (field_width == 1)
+				field_width = STD_ADDRESS_P_LENGTH; /* XXXX */
+			net_format(va_arg(args, net_addr *), ipbuf, sizeof(ipbuf));
+			s = ipbuf;
+			goto str;
 		case 's':
 			s = va_arg(args, char *);
 			if (!s)