Add support for source-specific IPv6 routes to BIRD core

This patch adds support for source-specific IPv6 routes to BIRD core.
This is based on Dean Luga's original patch, with the review comments
addressed. SADR support is added to network address parsing in confbase.Y
and to the kernel protocol on Linux.

Currently there is no way to mix source-specific and non-source-specific
routes (i.e., SADR tables cannot be connected to non-SADR tables).

Thanks to Toke Hoiland-Jorgensen for the original patch.
Minor changes by Ondrej Santiago Zajicek.

3 files changed, 54 insertions, 3 deletions

diff --git a/nest/config.Y b/nest/config.Y
index af5114f5..ab09a10c 100644
--- a/nest/config.Y
+++ b/nest/config.Y
@@ -66,7 +66,7 @@ CF_DECLS
 
 CF_KEYWORDS(ROUTER, ID, PROTOCOL, TEMPLATE, PREFERENCE, DISABLED, DEBUG, ALL, OFF, DIRECT)
 CF_KEYWORDS(INTERFACE, IMPORT, EXPORT, FILTER, NONE, VRF, TABLE, STATES, ROUTES, FILTERS)
-CF_KEYWORDS(IPV4, IPV6, VPN4, VPN6, ROA4, ROA6)
+CF_KEYWORDS(IPV4, IPV6, VPN4, VPN6, ROA4, ROA6, FLOW4, FLOW6, SADR, MPLS)
 CF_KEYWORDS(RECEIVE, LIMIT, ACTION, WARN, BLOCK, RESTART, DISABLE, KEEP, FILTERED)
 CF_KEYWORDS(PASSWORD, FROM, PASSIVE, TO, ID, EVENTS, PACKETS, PROTOCOLS, INTERFACES)
 CF_KEYWORDS(ALGORITHM, KEYED, HMAC, MD5, SHA1, SHA256, SHA384, SHA512)
@@ -77,7 +77,7 @@ CF_KEYWORDS(TIMEFORMAT, ISO, SHORT, LONG, ROUTE, PROTOCOL, BASE, LOG, S, MS, US)
 CF_KEYWORDS(GRACEFUL, RESTART, WAIT, MAX, FLUSH, AS)
 
 /* For r_args_channel */
-CF_KEYWORDS(IPV4, IPV4_MC, IPV4_MPLS, IPV6, IPV6_MC, IPV6_MPLS, VPN4, VPN4_MC, VPN4_MPLS, VPN6, VPN6_MC, VPN6_MPLS, ROA4, ROA6, FLOW4, FLOW6, MPLS, PRI, SEC)
+CF_KEYWORDS(IPV4, IPV4_MC, IPV4_MPLS, IPV6, IPV6_MC, IPV6_MPLS, IPV6_SADR, VPN4, VPN4_MC, VPN4_MPLS, VPN6, VPN6_MC, VPN6_MPLS, ROA4, ROA6, FLOW4, FLOW6, MPLS, PRI, SEC)
 
 CF_ENUM(T_ENUM_RTS, RTS_, DUMMY, STATIC, INHERIT, DEVICE, STATIC_DEVICE, REDIRECT,
 	RIP, OSPF, OSPF_IA, OSPF_EXT1, OSPF_EXT2, BGP, PIPE, BABEL)
@@ -134,6 +134,7 @@ gr_opts: GRACEFUL RESTART WAIT expr ';' { new_config->gr_wait = $4; } ;
 net_type:
    IPV4 { $$ = NET_IP4; }
  | IPV6 { $$ = NET_IP6; }
+ | IPV6 SADR { $$ = NET_IP6_SADR; }
  | VPN4 { $$ = NET_VPN4; }
  | VPN6 { $$ = NET_VPN6; }
  | ROA4 { $$ = NET_ROA4; }
@@ -143,7 +144,7 @@ net_type:
  | MPLS { $$ = NET_MPLS; }
  ;
 
-CF_ENUM(T_ENUM_NETTYPE, NET_, IP4, IP6, VPN4, VPN6, ROA4, ROA6, FLOW4, FLOW6)
+CF_ENUM(T_ENUM_NETTYPE, NET_, IP4, IP6, VPN4, VPN6, ROA4, ROA6, FLOW4, FLOW6, IP6_SADR)
 
 
 /* Creation of routing tables */
@@ -625,6 +626,7 @@ r_args_for:
   }
  | net_vpn4_
  | net_vpn6_
+ | net_ip6_sadr_
  | VPN_RD IP4 {
     $$ = cfg_alloc(sizeof(net_addr_vpn4));
     net_fill_vpn4($$, $2, IP4_MAX_PREFIX_LENGTH, $1);
@@ -633,6 +635,10 @@ r_args_for:
     $$ = cfg_alloc(sizeof(net_addr_vpn6));
     net_fill_vpn6($$, $2, IP6_MAX_PREFIX_LENGTH, $1);
   }
+ | IP6 FROM IP6 {
+    $$ = cfg_alloc(sizeof(net_addr_ip6_sadr));
+    net_fill_ip6_sadr($$, $1, IP6_MAX_PREFIX_LENGTH, $3, IP6_MAX_PREFIX_LENGTH);
+  }
  | SYM {
      if ($1->class == (SYM_CONSTANT | T_IP))
      {
@@ -666,6 +672,7 @@ r_args_channel:
  | IPV6		{ $$ = "ipv6"; }
  | IPV6_MC	{ $$ = "ipv6-mc"; }
  | IPV6_MPLS	{ $$ = "ipv6-mpls"; }
+ | IPV6_SADR	{ $$ = "ipv6-sadr"; }
  | VPN4		{ $$ = "vpn4"; }
  | VPN4_MC	{ $$ = "vpn4-mc"; }
  | VPN4_MPLS	{ $$ = "vpn4-mpls"; }
diff --git a/nest/rt-fib.c b/nest/rt-fib.c
index 169d6a4f..18ccbfc3 100644
--- a/nest/rt-fib.c
+++ b/nest/rt-fib.c
@@ -236,6 +236,7 @@ fib_find(struct fib *f, const net_addr *a)
   case NET_ROA6: return FIB_FIND(f, a, roa6);
   case NET_FLOW4: return FIB_FIND(f, a, flow4);
   case NET_FLOW6: return FIB_FIND(f, a, flow6);
+  case NET_IP6_SADR: return FIB_FIND(f, a, ip6_sadr);
   case NET_MPLS: return FIB_FIND(f, a, mpls);
   default: bug("invalid type");
   }
@@ -256,6 +257,7 @@ fib_insert(struct fib *f, const net_addr *a, struct fib_node *e)
   case NET_ROA6: FIB_INSERT(f, a, e, roa6); return;
   case NET_FLOW4: FIB_INSERT(f, a, e, flow4); return;
   case NET_FLOW6: FIB_INSERT(f, a, e, flow6); return;
+  case NET_IP6_SADR: FIB_INSERT(f, a, e, ip6_sadr); return;
   case NET_MPLS: FIB_INSERT(f, a, e, mpls); return;
   default: bug("invalid type");
   }
diff --git a/nest/rt-table.c b/nest/rt-table.c
index 0f53c93f..686d0e84 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -85,6 +85,45 @@ net_route_ip6(rtable *t, net_addr_ip6 *n)
   return r;
 }
 
+static inline void *
+net_route_ip6_sadr(rtable *t, net_addr_ip6_sadr *n)
+{
+  struct fib_node *fn;
+
+  while (1)
+  {
+    net *best = NULL;
+    int best_pxlen = 0;
+
+    /* We need to do dst first matching. Since sadr addresses are hashed on dst
+       prefix only, find the hash table chain and go through it to find the
+       match with the smallest matching src prefix. */
+    for (fn = fib_get_chain(&t->fib, (net_addr *) n); fn; fn = fn->next)
+    {
+      net_addr_ip6_sadr *a = (void *) fn->addr;
+
+      if (net_equal_dst_ip6_sadr(n, a) &&
+	  net_in_net_src_ip6_sadr(n, a) &&
+	  (a->src_pxlen >= best_pxlen))
+      {
+	best = fib_node_to_user(&t->fib, fn);
+	best_pxlen = a->src_pxlen;
+      }
+    }
+
+    if (best)
+      return best;
+
+    if (!n->dst_pxlen)
+      break;
+
+    n->dst_pxlen--;
+    ip6_clrbit(&n->dst_prefix, n->dst_pxlen);
+  }
+
+  return NULL;
+}
+
 void *
 net_route(rtable *tab, const net_addr *n)
 {
@@ -105,6 +144,9 @@ net_route(rtable *tab, const net_addr *n)
   case NET_ROA6:
     return net_route_ip6(tab, (net_addr_ip6 *) n0);
 
+  case NET_IP6_SADR:
+    return net_route_ip6_sadr(tab, (net_addr_ip6_sadr *) n0);
+
   default:
     return NULL;
   }