OSPF: Redesign LSA checksumming

New LSA checksumming code separates generic Fletcher-16 and OSPF-specific
code and avoids back and forth endianity conversions, making it much more
readable and also several times faster.

4 files changed, 30 insertions, 133 deletions

diff --git a/proto/ospf/lsalib.c b/proto/ospf/lsalib.c
index ce6fb178..66a3a23d 100644
--- a/proto/ospf/lsalib.c
+++ b/proto/ospf/lsalib.c
@@ -2,14 +2,15 @@
  *	BIRD -- OSPF
  *
  *	(c) 1999--2004 Ondrej Filip <feela@network.cz>
- *	(c) 2009--2014 Ondrej Zajicek <santiago@crfreenet.org>
- *	(c) 2009--2014 CZ.NIC z.s.p.o.
+ *	(c) 2009--2015 Ondrej Zajicek <santiago@crfreenet.org>
+ *	(c) 2009--2015 CZ.NIC z.s.p.o.
  *
  *	Can be freely distributed and used under the terms of the GNU GPL.
  */
 
 #include "ospf.h"
 
+#include "lib/fletcher16.h"
 
 #ifndef CPU_BIG_ENDIAN
 void
@@ -150,145 +151,41 @@ lsa_get_type_domain_(u32 itype, struct ospf_iface *ifa, u32 *otype, u32 *domain)
 }
 
 
-
-/*
 void
-buf_dump(const char *hdr, const byte *buf, int blen)
+lsa_generate_checksum(struct ospf_lsa_header *lsa, const u8 *body)
 {
-  char b2[1024];
-  char *bp;
-  int first = 1;
-  int i;
-
-  const char *lhdr = hdr;
-
-  bp = b2;
-  for(i = 0; i < blen; i++)
-    {
-      if ((i > 0) && ((i % 16) == 0))
-	{
-	      *bp = 0;
-	      log(L_WARN "%s\t%s", lhdr, b2);
-	      lhdr = "";
-	      bp = b2;
-	}
-
-      bp += snprintf(bp, 1022, "%02x ", buf[i]);
-
-    }
-
-  *bp = 0;
-  log(L_WARN "%s\t%s", lhdr, b2);
-}
-*/
-
-#define MODX 4102		/* larges signed value without overflow */
-
-/* Fletcher Checksum -- Refer to RFC1008. */
-#define MODX                 4102
-#define LSA_CHECKSUM_OFFSET    15
-
-/* FIXME This is VERY uneficient, I have huge endianity problems */
-void
-lsasum_calculate(struct ospf_lsa_header *h, void *body)
-{
-  u16 length = h->length;
-
-  //  log(L_WARN "Checksum %R %R %d start (len %d)", h->id, h->rt, h->type, length);
-  lsa_hton_hdr(h, h);
-  lsa_hton_body1(body, length - sizeof(struct ospf_lsa_header));
+  struct fletcher16_context ctx;
+  struct ospf_lsa_header hdr;
+  u16 len = lsa->length;
 
   /*
-  char buf[1024];
-  memcpy(buf, h, sizeof(struct ospf_lsa_header));
-  memcpy(buf + sizeof(struct ospf_lsa_header), body, length - sizeof(struct ospf_lsa_header));
-  buf_dump("CALC", buf, length);
-  */
+   * lsa and body are in the host order, we need to compute Fletcher-16 checksum
+   * for data in the network order. We also skip the initial age field.
+   */
 
-  (void) lsasum_check(h, body, 1);
+  lsa_hton_hdr(lsa, &hdr);
+  hdr.checksum = 0;
 
-  //  log(L_WARN "Checksum result %4x", h->checksum);
-
-  lsa_ntoh_hdr(h, h);
-  lsa_ntoh_body1(body, length - sizeof(struct ospf_lsa_header));
+  fletcher16_init(&ctx);
+  fletcher16_update(&ctx, (u8 *) &hdr + 2, sizeof(struct ospf_lsa_header) - 2);
+  fletcher16_update_n32(&ctx, body, len - sizeof(struct ospf_lsa_header));
+  lsa->checksum = fletcher16_final(&ctx, len, OFFSETOF(struct ospf_lsa_header, checksum));
 }
 
-/*
- * Calculates the Fletcher checksum of an OSPF LSA.
- *
- * If 'update' is non-zero, the checkbytes (X and Y in RFC905) are calculated
- * and the checksum field in the header is updated. The return value is the
- * checksum as placed in the header (in network byte order).
- *
- * If 'update' is zero, only C0 and C1 are calculated and the header is kept
- * intact. The return value is a combination of C0 and C1; if the return value
- * is exactly zero the checksum is considered valid, any non-zero value is
- * invalid.
- *
- * Note that this function expects the input LSA to be in network byte order.
- */
 u16
-lsasum_check(struct ospf_lsa_header *h, void *body, int update)
+lsa_verify_checksum(const void *lsa_n, int lsa_len)
 {
-  u8 *sp, *ep, *p, *q, *b;
-  int c0 = 0, c1 = 0;
-  int x, y;
-  u16 length;
-
-  b = body;
-  sp = (char *) h;
-  sp += 2; /* Skip Age field */
-  length = ntohs(h->length) - 2;
-  if (update) h->checksum = 0;
-
-  for (ep = sp + length; sp < ep; sp = q)
-  {				/* Actually MODX is very large, do we need the for-cyclus? */
-    q = sp + MODX;
-    if (q > ep)
-      q = ep;
-    for (p = sp; p < q; p++)
-    {
-      /*
-       * I count with bytes from header and than from body
-       * but if there is no body, it's appended to header
-       * (probably checksum in update receiving) and I go on
-       * after header
-       */
-      if ((b == NULL) || (p < (u8 *) (h + 1)))
-      {
-	c0 += *p;
-      }
-      else
-      {
-	c0 += *(b + (p - (u8 *) (h + 1)));
-      }
-
-      c1 += c0;
-    }
-    c0 %= 255;
-    c1 %= 255;
-  }
+  struct fletcher16_context ctx;
 
-  if (!update) {
-    /*
-     * When testing the checksum, we don't need to calculate x and y. The
-     * checksum passes if c0 and c1 are both 0.
-     */
-    return (c0 << 8) | (c1 & 0xff);
-  }
+  /* The whole LSA is at lsa_n in net order, we just skip initial age field */
 
-  x = (int)((length - LSA_CHECKSUM_OFFSET) * c0 - c1) % 255;
-  if (x <= 0)
-    x += 255;
-  y = 510 - c0 - x;
-  if (y > 255)
-    y -= 255;
+  fletcher16_init(&ctx);
+  fletcher16_update(&ctx, (u8 *) lsa_n + 2, lsa_len - 2);
 
-  ((u8 *) & h->checksum)[0] = x;
-  ((u8 *) & h->checksum)[1] = y;
-  return h->checksum;
+  return fletcher16_compute(&ctx) == 0;
 }
 
+
 int
 lsa_comp(struct ospf_lsa_header *l1, struct ospf_lsa_header *l2)
 			/* Return codes from point of view of l1 */
diff --git a/proto/ospf/lsalib.h b/proto/ospf/lsalib.h
index 4ad770e8..ae6af044 100644
--- a/proto/ospf/lsalib.h
+++ b/proto/ospf/lsalib.h
@@ -46,9 +46,9 @@ static inline u32 lsa_get_etype(struct ospf_lsa_header *h, struct ospf_proto *p)
 
 
 int lsa_flooding_allowed(u32 type, u32 domain, struct ospf_iface *ifa);
+void lsa_generate_checksum(struct ospf_lsa_header *lsa, const u8 *body);
+u16 lsa_verify_checksum(const void *lsa_n, int lsa_len);
 
-void lsasum_calculate(struct ospf_lsa_header *header, void *body);
-u16 lsasum_check(struct ospf_lsa_header *h, void *body, int update);
 #define CMP_NEWER 1
 #define CMP_SAME 0
 #define CMP_OLDER -1
diff --git a/proto/ospf/lsupd.c b/proto/ospf/lsupd.c
index 6e7dce26..c6a734ca 100644
--- a/proto/ospf/lsupd.c
+++ b/proto/ospf/lsupd.c
@@ -530,8 +530,8 @@ ospf_receive_lsupd(struct ospf_packet *pkt, struct ospf_iface *ifa,
     DBG("Update Type: %04x, Id: %R, Rt: %R, Sn: 0x%08x, Age: %u, Sum: %u\n",
 	lsa_type, lsa.id, lsa.rt, lsa.sn, lsa.age, lsa.checksum);
 
-    /* RFC 2328 13. (1) - validate LSA checksum */
-    if ((lsa_n->checksum == 0) || (lsasum_check(lsa_n, NULL, 0) != 0))
+    /* RFC 2328 13. (1) - verify LSA checksum */
+    if ((lsa_n->checksum == 0) || !lsa_verify_checksum(lsa_n, lsa_len))
       SKIP("invalid checksum");
 
     /* RFC 2328 13. (2) */
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index 0613d34d..8119cfa6 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -129,7 +129,7 @@ ospf_advance_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_ls
       en->lsa.age = 0;
       en->init_age = 0;
       en->inst_time = now;
-      lsasum_calculate(&en->lsa, en->lsa_body);
+      lsa_generate_checksum(&en->lsa, en->lsa_body);
 
       OSPF_TRACE(D_EVENTS, "Advancing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
 		 en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
@@ -238,7 +238,7 @@ ospf_do_originate_lsa(struct ospf_proto *p, struct top_hash_entry *en, void *lsa
   en->lsa.age = 0;
   en->init_age = 0;
   en->inst_time = now;
-  lsasum_calculate(&en->lsa, en->lsa_body);
+  lsa_generate_checksum(&en->lsa, en->lsa_body);
 
   OSPF_TRACE(D_EVENTS, "Originating LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
 	     en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
@@ -382,7 +382,7 @@ ospf_refresh_lsa(struct ospf_proto *p, struct top_hash_entry *en)
   en->lsa.age = 0;
   en->init_age = 0;
   en->inst_time = now;
-  lsasum_calculate(&en->lsa, en->lsa_body);
+  lsa_generate_checksum(&en->lsa, en->lsa_body);
   ospf_flood_lsa(p, en, NULL);
 }