OSPF: Opaque LSAs and Router Information LSA

Add support for OSPFv2 Opaque LSAs (RFC 5250) and for Router Information
LSA (RFC 7770). The second part is here mainly for testing opaque LSAs.

9 files changed, 227 insertions, 43 deletions

diff --git a/lib/birdlib.h b/lib/birdlib.h
index 428b3209..7cd78032 100644
--- a/lib/birdlib.h
+++ b/lib/birdlib.h
@@ -56,6 +56,13 @@ static inline int u64_cmp(u64 i1, u64 i2)
 #define BIT32_CLR(b,p)		((b)[(p)/32] &= ~BIT32_VAL(p))
 #define BIT32_ZERO(b,l)		memset((b), 0, (l)/8)
 
+/* The same, but counting bits from MSB */
+#define BIT32R_VAL(p)		((((u32) 1) << 31) >> ((p) % 32))
+#define BIT32R_TEST(b,p)	((b)[(p)/32] & BIT32R_VAL(p))
+#define BIT32R_SET(b,p)		((b)[(p)/32] |= BIT32R_VAL(p))
+#define BIT32R_CLR(b,p)		((b)[(p)/32] &= ~BIT32R_VAL(p))
+#define BIT32R_ZERO(b,l)	memset((b), 0, (l)/8)
+
 #ifndef NULL
 #define NULL ((void *) 0)
 #endif
diff --git a/proto/ospf/dbdes.c b/proto/ospf/dbdes.c
index 019aff04..34665dad 100644
--- a/proto/ospf/dbdes.c
+++ b/proto/ospf/dbdes.c
@@ -127,7 +127,7 @@ ospf_prepare_dbdes(struct ospf_proto *p, struct ospf_neighbor *n)
   {
     struct ospf_dbdes2_packet *ps = (void *) pkt;
     ps->iface_mtu = htons(iface_mtu);
-    ps->options = ifa->oa->options;
+    ps->options = ifa->oa->options | OPT_O;
     ps->imms = 0;	/* Will be set later */
     ps->ddseq = htonl(n->dds);
     length = sizeof(struct ospf_dbdes2_packet);
@@ -162,7 +162,8 @@ ospf_prepare_dbdes(struct ospf_proto *p, struct ospf_neighbor *n)
       }
 
       if ((en->lsa.age < LSA_MAXAGE) &&
-	  lsa_flooding_allowed(en->lsa_type, en->domain, ifa))
+	  lsa_flooding_allowed(en->lsa_type, en->domain, ifa) &&
+	  lsa_is_acceptable(en->lsa_type, n, p))
       {
 	lsa_hton_hdr(&(en->lsa), lsas + i);
 	i++;
diff --git a/proto/ospf/lsalib.c b/proto/ospf/lsalib.c
index fbfd8d29..e66d3dc0 100644
--- a/proto/ospf/lsalib.c
+++ b/proto/ospf/lsalib.c
@@ -91,6 +91,30 @@ lsa_flooding_allowed(u32 type, u32 domain, struct ospf_iface *ifa)
   }
 }
 
+int
+lsa_is_acceptable(u32 type, struct ospf_neighbor *n, struct ospf_proto *p)
+{
+  if (ospf_is_v2(p))
+  {
+    if (type == LSA_T_NSSA)
+      return !!(n->options & OPT_N);
+
+    if (lsa_is_opaque(type))
+      return !!(n->options & OPT_O);
+
+    return 1;
+  }
+  else
+  {
+    /*
+     * There should be check whether receiving router understands that type
+     * of LSA (for LSA types with U-bit == 0). But as we do not support any
+     * optional LSA types, this is not needed yet.
+     */
+
+    return 1;
+  }
+}
 
 static int
 unknown_lsa_type(u32 type)
@@ -105,6 +129,9 @@ unknown_lsa_type(u32 type)
   case LSA_T_NSSA:
   case LSA_T_LINK:
   case LSA_T_PREFIX:
+  case LSA_T_RI_LINK:
+  case LSA_T_RI_AREA:
+  case LSA_T_RI_AS:
     return 0;
 
   default:
@@ -112,28 +139,47 @@ unknown_lsa_type(u32 type)
   }
 }
 
-#define LSA_V2_TMAX 8
-static const u16 lsa_v2_types[LSA_V2_TMAX] =
-  {0, LSA_T_RT, LSA_T_NET, LSA_T_SUM_NET, LSA_T_SUM_RT, LSA_T_EXT, 0, LSA_T_NSSA};
+/* Maps OSPFv2 types to OSPFv3 types */
+static const u16 lsa_v2_types[] = {
+  0, LSA_T_RT, LSA_T_NET, LSA_T_SUM_NET, LSA_T_SUM_RT, LSA_T_EXT, 0, LSA_T_NSSA,
+  0, LSA_T_OPAQUE_LINK, LSA_T_OPAQUE_AREA, LSA_T_OPAQUE_AS
+};
+
+/* Maps OSPFv2 opaque types to OSPFv3 function codes */
+static const u16 opaque_lsa_types[] = {
+  [LSA_OT_RI] = LSA_T_RI_,
+};
+
+/* Maps (subset of) OSPFv3 function codes to OSPFv2 opaque types */
+static const u8 opaque_lsa_types_inv[] = {
+  [LSA_T_RI_] = LSA_OT_RI,
+};
+
+#define LOOKUP(a, i) ({ uint _i = (i); (_i < ARRAY_SIZE(a)) ? a[_i] : 0; })
 
 void
-lsa_get_type_domain_(u32 itype, struct ospf_iface *ifa, u32 *otype, u32 *domain)
+lsa_get_type_domain_(u32 type, u32 id, struct ospf_iface *ifa, u32 *otype, u32 *domain)
 {
   if (ospf_is_v2(ifa->oa->po))
   {
-    itype = itype & LSA_T_V2_MASK;
-    itype = (itype < LSA_V2_TMAX) ? lsa_v2_types[itype] : 0;
+    type = type & LSA_T_V2_MASK;
+    type = LOOKUP(lsa_v2_types, type);
+
+    uint code;
+    if (LSA_FUNCTION(type) == LSA_T_OPAQUE_)
+      if (code = LOOKUP(opaque_lsa_types, id >> 24))
+	type = code | LSA_UBIT | LSA_SCOPE(type);
   }
   else
   {
     /* For unkown LSAs without U-bit change scope to LSA_SCOPE_LINK */
-    if (unknown_lsa_type(itype) && !(itype & LSA_UBIT))
-      itype = itype & ~LSA_SCOPE_MASK;
+    if (unknown_lsa_type(type) && !(type & LSA_UBIT))
+      type = type & ~LSA_SCOPE_MASK;
   }
 
-  *otype = itype;
+  *otype = type;
 
-  switch (LSA_SCOPE(itype))
+  switch (LSA_SCOPE(type))
   {
   case LSA_SCOPE_LINK:
     *domain = ifa->iface_id;
@@ -150,6 +196,12 @@ lsa_get_type_domain_(u32 itype, struct ospf_iface *ifa, u32 *otype, u32 *domain)
   }
 }
 
+u32
+lsa_get_opaque_type(u32 type)
+{
+  return LOOKUP(opaque_lsa_types_inv, LSA_FUNCTION(type));
+}
+
 
 void
 lsa_generate_checksum(struct ospf_lsa_header *lsa, const u8 *body)
@@ -548,6 +600,17 @@ lsa_validate_prefix(struct ospf_lsa_header *lsa, struct ospf_lsa_prefix *body)
   return lsa_validate_pxlist(lsa, body->pxcount, sizeof(struct ospf_lsa_prefix), (u8 *) body);
 }
 
+static int
+lsa_validate_ri(struct ospf_lsa_header *lsa UNUSED, struct ospf_lsa_net *body UNUSED)
+{
+  /*
+   * There should be proper validation. But we do not really process RI LSAs, so
+   * we can just accept them like another unknown opaque LSAs.
+   */
+
+  return 1;
+}
+
 
 /**
  * lsa_validate - check whether given LSA is valid
@@ -577,6 +640,14 @@ lsa_validate(struct ospf_lsa_header *lsa, u32 lsa_type, int ospf2, void *body)
     case LSA_T_EXT:
     case LSA_T_NSSA:
       return lsa_validate_ext2(lsa, body);
+    case LSA_T_RI_LINK:
+    case LSA_T_RI_AREA:
+    case LSA_T_RI_AS:
+      return lsa_validate_ri(lsa, body);
+    case LSA_T_OPAQUE_LINK:
+    case LSA_T_OPAQUE_AREA:
+    case LSA_T_OPAQUE_AS:
+      return 1;	/* Unknown Opaque LSAs */
     default:
       return 0;	/* Should not happen, unknown LSAs are already rejected */
     }
@@ -600,6 +671,10 @@ lsa_validate(struct ospf_lsa_header *lsa, u32 lsa_type, int ospf2, void *body)
       return lsa_validate_link(lsa, body);
     case LSA_T_PREFIX:
       return lsa_validate_prefix(lsa, body);
+    case LSA_T_RI_LINK:
+    case LSA_T_RI_AREA:
+    case LSA_T_RI_AS:
+      return lsa_validate_ri(lsa, body);
     default:
       return 1;	/* Unknown LSAs are OK in OSPFv3 */
     }
diff --git a/proto/ospf/lsalib.h b/proto/ospf/lsalib.h
index fca7faec..af8901ce 100644
--- a/proto/ospf/lsalib.h
+++ b/proto/ospf/lsalib.h
@@ -36,16 +36,21 @@ struct ospf_lsa_rt_walk {
 };
 
 
-void lsa_get_type_domain_(u32 itype, struct ospf_iface *ifa, u32 *otype, u32 *domain);
+void lsa_get_type_domain_(u32 type, u32 id, struct ospf_iface *ifa, u32 *otype, u32 *domain);
 
 static inline void lsa_get_type_domain(struct ospf_lsa_header *lsa, struct ospf_iface *ifa, u32 *otype, u32 *domain)
-{ lsa_get_type_domain_(lsa->type_raw, ifa, otype, domain); }
+{ lsa_get_type_domain_(lsa->type_raw, lsa->id, ifa, otype, domain); }
 
 static inline u32 lsa_get_etype(struct ospf_lsa_header *h, struct ospf_proto *p)
 { return ospf_is_v2(p) ? (h->type_raw & LSA_T_V2_MASK) : h->type_raw; }
 
+/* Assuming OSPFv2 - All U-bit LSAs are mapped to Opaque LSAs */
+static inline int lsa_is_opaque(u32 type)
+{ return !!(type & LSA_UBIT); }
 
+u32 lsa_get_opaque_type(u32 type);
 int lsa_flooding_allowed(u32 type, u32 domain, struct ospf_iface *ifa);
+int lsa_is_acceptable(u32 type, struct ospf_neighbor *n, struct ospf_proto *p);
 void lsa_generate_checksum(struct ospf_lsa_header *lsa, const u8 *body);
 u16 lsa_verify_checksum(const void *lsa_n, int lsa_len);
 
diff --git a/proto/ospf/lsreq.c b/proto/ospf/lsreq.c
index 657c0247..45af7533 100644
--- a/proto/ospf/lsreq.c
+++ b/proto/ospf/lsreq.c
@@ -125,7 +125,7 @@ ospf_receive_lsreq(struct ospf_packet *pkt, struct ospf_iface *ifa,
 
     id = ntohl(lsrs[i].id);
     rt = ntohl(lsrs[i].rt);
-    lsa_get_type_domain_(ntohl(lsrs[i].type), ifa, &type, &domain);
+    lsa_get_type_domain_(ntohl(lsrs[i].type), id, ifa, &type, &domain);
 
     DBG("Processing requested LSA: Type: %04x, Id: %R, Rt: %R\n", type, id, rt);
 
diff --git a/proto/ospf/lsupd.c b/proto/ospf/lsupd.c
index a98c9098..7318b751 100644
--- a/proto/ospf/lsupd.c
+++ b/proto/ospf/lsupd.c
@@ -171,7 +171,8 @@ ospf_add_flushed_to_lsrt(struct ospf_proto *p, struct ospf_neighbor *n)
 
   WALK_SLIST(en, p->lsal)
     if ((en->lsa.age == LSA_MAXAGE) && (en->lsa_body != NULL) &&
-	lsa_flooding_allowed(en->lsa_type, en->domain, n->ifa))
+	lsa_flooding_allowed(en->lsa_type, en->domain, n->ifa) &&
+        lsa_is_acceptable(en->lsa_type, n, p))
       ospf_lsa_lsrt_up(en, n);
 
   /* If we found any flushed LSA, we send them ASAP */
@@ -287,9 +288,9 @@ ospf_flood_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_neig
       if (n == from)
 	continue;
 
-      /* In OSPFv3, there should be check whether receiving router understand
-	 that type of LSA (for LSA types with U-bit == 0). But as we do not support
-	 any optional LSA types, this is not needed yet */
+      /* Check whether optional LSAs are supported by neighbor */
+      if (!lsa_is_acceptable(en->lsa_type, n, p))
+	continue;
 
       /* 13.3 (1d) - add LSA to the link state retransmission list */
       ospf_lsa_lsrt_up(en, n);
diff --git a/proto/ospf/ospf.c b/proto/ospf/ospf.c
index a5e22269..73500604 100644
--- a/proto/ospf/ospf.c
+++ b/proto/ospf/ospf.c
@@ -92,11 +92,13 @@
  * - RFC 2328 - main OSPFv2 standard
  * - RFC 5340 - main OSPFv3 standard
  * - RFC 3101 - OSPFv2 NSSA areas
+ * - RFC 5250 - OSPFv2 Opaque LSAs
  * - RFC 5709 - OSPFv2 HMAC-SHA Cryptographic Authentication
  * - RFC 5838 - OSPFv3 Support of Address Families
  * - RFC 6549 - OSPFv2 Multi-Instance Extensions
  * - RFC 6987 - OSPF Stub Router Advertisement
  * - RFC 7166 - OSPFv3 Authentication Trailer
+ * - RFC 7770 - OSPF Router Information LSA
  */
 
 #include <stdlib.h>
@@ -239,6 +241,7 @@ ospf_start(struct proto *P)
   p->rfc1583 = c->rfc1583;
   p->stub_router = c->stub_router;
   p->merge_external = c->merge_external;
+  p->instance_id = c->instance_id;
   p->asbr = c->asbr;
   p->ecmp = c->ecmp;
   p->tick = c->tick;
@@ -648,6 +651,9 @@ ospf_reconfigure(struct proto *P, struct proto_config *CF)
   if (p->rfc1583 != new->rfc1583)
     return 0;
 
+  if (p->instance_id != new->instance_id)
+    return 0;
+
   if (old->abr != new->abr)
     return 0;
 
diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h
index ff55621a..22b87ebe 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -223,6 +223,7 @@ struct ospf_proto
   u8 rfc1583;			/* RFC1583 compatibility */
   u8 stub_router;		/* Do not forward transit traffic */
   u8 merge_external;		/* Should i merge external routes? */
+  u8 instance_id;		/* Differentiate between more OSPF instances */
   u8 asbr;			/* May i originate any ext/NSSA lsa? */
   u8 ecmp;			/* Maximal number of nexthops in ECMP route, or 0 */
   u64 csn64;			/* Last used cryptographic sequence number */
@@ -466,6 +467,7 @@ struct ospf_neighbor
 #define OPT_L_V2	0x0010	/* OSPFv2, link-local signaling, not used */
 #define OPT_R		0x0010	/* OSPFv3, originator is active router */
 #define OPT_DC		0x0020	/* Related to demand circuits, not used */
+#define OPT_O		0x0040	/* OSPFv2 Opaque LSA (RFC 5250) */
 #define OPT_AF		0x0100	/* OSPFv3 Address Families (RFC 5838) */
 #define OPT_L_V3	0x0200	/* OSPFv3, link-local signaling */
 #define OPT_AT          0x0400	/* OSPFv3, authentication trailer */
@@ -541,25 +543,44 @@ struct ospf_auth3
 #define DBDES_IMMS	(DBDES_I | DBDES_M | DBDES_MS)
 
 
-#define LSA_T_RT	0x2001
-#define LSA_T_NET	0x2002
-#define LSA_T_SUM_NET	0x2003
-#define LSA_T_SUM_RT	0x2004
-#define LSA_T_EXT	0x4005
-#define LSA_T_NSSA	0x2007
-#define LSA_T_LINK	0x0008
-#define LSA_T_PREFIX	0x2009
-
-#define LSA_T_V2_MASK	0x00ff
-
-#define LSA_UBIT	0x8000
-
-#define LSA_SCOPE_LINK	0x0000
-#define LSA_SCOPE_AREA	0x2000
-#define LSA_SCOPE_AS	0x4000
-#define LSA_SCOPE_RES	0x6000
-#define LSA_SCOPE_MASK	0x6000
-#define LSA_SCOPE(type)	((type) & LSA_SCOPE_MASK)
+/* OSPFv3 LSA Types / LSA Function Codes */
+/* https://www.iana.org/assignments/ospfv3-parameters/ospfv3-parameters.xhtml#ospfv3-parameters-3 */
+#define LSA_T_RT		0x2001
+#define LSA_T_NET		0x2002
+#define LSA_T_SUM_NET		0x2003
+#define LSA_T_SUM_RT		0x2004
+#define LSA_T_EXT		0x4005
+#define LSA_T_NSSA		0x2007
+#define LSA_T_LINK		0x0008
+#define LSA_T_PREFIX		0x2009
+#define LSA_T_RI_		0x000C
+#define LSA_T_RI_LINK		0x800C
+#define LSA_T_RI_AREA		0xA00C
+#define LSA_T_RI_AS		0xC00C
+#define LSA_T_OPAQUE_		0x1FFF
+#define LSA_T_OPAQUE_LINK	0x9FFF
+#define LSA_T_OPAQUE_AREA	0xBFFF
+#define LSA_T_OPAQUE_AS	 	0xDFFF
+
+#define LSA_T_V2_OPAQUE_	0x0009
+#define LSA_T_V2_MASK		0x00ff
+
+/* OSPFv2 Opaque LSA Types */
+/* https://www.iana.org/assignments/ospf-opaque-types/ospf-opaque-types.xhtml#ospf-opaque-types-2 */
+#define LSA_OT_RI		0x04
+
+#define LSA_FUNCTION_MASK	0x1FFF
+#define LSA_FUNCTION(type)	((type) & LSA_FUNCTION_MASK)
+
+#define LSA_UBIT		0x8000
+
+#define LSA_SCOPE_LINK		0x0000
+#define LSA_SCOPE_AREA		0x2000
+#define LSA_SCOPE_AS		0x4000
+#define LSA_SCOPE_RES		0x6000
+#define LSA_SCOPE_MASK		0x6000
+#define LSA_SCOPE(type)		((type) & LSA_SCOPE_MASK)
+#define LSA_SCOPE_ORDER(type)	(((type) >> 13) & 0x3)
 
 
 #define LSA_MAXAGE	3600	/* 1 hour */
@@ -586,9 +607,20 @@ struct ospf_auth3
 #define LSA_EXT2_TOS	0x7F000000
 #define LSA_EXT2_EBIT	0x80000000
 
-#define LSA_EXT3_EBIT	0x4000000
-#define LSA_EXT3_FBIT	0x2000000
-#define LSA_EXT3_TBIT	0x1000000
+#define LSA_EXT3_EBIT	0x04000000
+#define LSA_EXT3_FBIT	0x02000000
+#define LSA_EXT3_TBIT	0x01000000
+
+/* OSPF Router Information (RI) TLVs */
+/* https://www.iana.org/assignments/ospf-parameters/ospf-parameters.xhtml#ri-tlv */
+#define LSA_RI_RIC		1
+#define LSA_RI_RFC		2
+
+/* OSPF Router Informational Capability Bits */
+/* https://www.iana.org/assignments/ospf-parameters/ospf-parameters.xhtml#router-informational-capability */
+#define LSA_RIC_GR_CAPABLE	0
+#define LSA_RIC_GR_HELPER	1
+#define LSA_RIC_STUB_ROUTER	2
 
 
 struct ospf_lsa_header
@@ -731,6 +763,18 @@ struct ospf_lsa_prefix
   u32 rest[];
 };
 
+struct ospf_tlv
+{
+#ifdef CPU_BIG_ENDIAN
+  u16 type;
+  u16 length;
+#else
+  u16 length;
+  u16 type;
+#endif
+  u32 data[];
+};
+
 
 static inline uint
 lsa_net_count(struct ospf_lsa_header *lsa)
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index e58f1375..f9ca7bfc 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -224,12 +224,17 @@ ospf_do_originate_lsa(struct ospf_proto *p, struct top_hash_entry *en, void *lsa
   /*
    * lsa.type_raw is initialized by ospf_hash_get() to OSPFv3 LSA type.
    * lsa_set_options() implicitly converts it to OSPFv2 LSA type, assuming that
-   * old type is just new type masked by 0xff.  That is not universally true,
-   * but it holds for all OSPFv2 types currently supported by BIRD.
+   * old type is just new type masked by 0xff. That holds for most OSPFv2 types,
+   * but we have to fix it for opaque LSAs.
    */
 
   if (ospf_is_v2(p))
+  {
+    if (lsa_is_opaque(en->lsa_type))
+      en->lsa.type_raw = LSA_T_V2_OPAQUE_ + LSA_SCOPE_ORDER(en->lsa_type);
+
     lsa_set_options(&en->lsa, lsa_opts);
+  }
 
   mb_free(en->lsa_body);
   en->lsa_body = lsa_body;
@@ -273,6 +278,10 @@ ospf_originate_lsa(struct ospf_proto *p, struct ospf_new_lsa *lsa)
   u16 lsa_blen = p->lsab_used;
   u16 lsa_length = sizeof(struct ospf_lsa_header) + lsa_blen;
 
+  /* For OSPFv2 Opaque LSAs, LS ID consists of Opaque Type and Opaque ID */
+  if (ospf_is_v2(p) && lsa_is_opaque(lsa->type))
+    lsa->id |= (u32) lsa_get_opaque_type(lsa->type) << 24;
+
   en = ospf_hash_get(p->gr, lsa->dom, lsa->id, p->router_id, lsa->type);
 
   if (!SNODE_VALID(en))
@@ -1658,6 +1667,41 @@ ospf_originate_prefix_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
   ifa->pxn_lsa = ospf_originate_lsa(p, &lsa);
 }
 
+
+/*
+ *	Router Information LSA handling
+ *	Type = LSA_T_RI_AREA, opaque type = LSA_OT_RI
+ */
+
+void
+ospf_add_ric_tlv(struct ospf_proto *p)
+{
+  struct ospf_tlv *ri = lsab_allocz(p, sizeof(struct ospf_tlv) + sizeof(u32));
+  ri->type = LSA_RI_RIC;
+  ri->length = sizeof(struct ospf_tlv) + sizeof(u32);
+
+  BIT32R_SET(ri->data, LSA_RIC_STUB_ROUTER);
+}
+
+void
+ospf_originate_ri_lsa(struct ospf_proto *p, struct ospf_area *oa)
+{
+  struct ospf_new_lsa lsa = {
+    .type = LSA_T_RI_AREA,
+    .dom  = oa->areaid,
+    .id   = p->instance_id
+  };
+
+  ospf_add_ric_tlv(p);
+
+  ospf_originate_lsa(p, &lsa);
+}
+
+
+/*
+ *	Generic topology code
+ */
+
 static inline int breaks_minlsinterval(struct top_hash_entry *en)
 { return en && (en->lsa.age < LSA_MAXAGE) && (lsa_inst_age(en) < MINLSINTERVAL); }
 
@@ -1692,6 +1736,7 @@ ospf_update_topology(struct ospf_proto *p)
 
       ospf_originate_rt_lsa(p, oa);
       ospf_originate_prefix_rt_lsa(p, oa);
+      ospf_originate_ri_lsa(p, oa);
       oa->update_rt_lsa = 0;
     }
   }