On 14.08.2013 14:18, Ondrej Zajicek wrote:
On Wed, Aug 14, 2013 at 03:35:07AM +0400, Alexander V. Chernikov wrote:
Hello list!
Currently bird performs LSA premature aging in very strange way which
sometimes upsets quagga (up to SIGSEGV) and Cisco.
Every time aging is done via setting seq number to LSA_MAXSEQNO.
RFC 2328, on the opposite, shows us only 2 cases where MaxSequenceNumber
is used in outgoing LSAs:
1) Self LSA originating with given seq num (very rare event)
2) [Premature] Aging of LSA from 1) because a) disappeared net and b)
seq number increase (12.1.6)
For all other cases seq number should be either increased or left intact.
Bird, however, insist on setting LSA_MAXSEQNO while:
1) Receiving self-originating LSA which is not in local LSDB (
ospf_lsupd_receive ) which is not a special case according to 14.1
2) In all other places like handling if-down, external route disappear,
etc... ( ospf_lsupd_flush_nlsa )
You are right that BIRD uses LSA_MAXSEQNO in more cases than prescribed
by RFC 2328 (essentially in most cases when a local LSA is flushed), but
these changes were introduced mostly as a reaction to problems with the
usual flushing (just premature aging), where BIRD sends LSA with MaxAge,
then forgets the LSA and when reintroduced the LSA later, it starts with
InitSeqNum. In cases like external route flaps (and similar events for
other kinds of LSAs) that caused that newer LSA meets MaxAge LSA during
flood, is considered as older and removed (and combined with other
minor inconsistencies in router behaviors this would lead to all kinds
of strange events).
Let me return to this old, but still relevant topic :)
Two patches, unifying work with sn/age LSA fields with sn story-keeping
stuff attached.
First one replaces most initial LSA header setup with single
fill_lsa_header() function.
It is also responsible for (unique) LSA id generation.
Second one handles sequence number keeping for all LSA types using
per-are FIB for most LSAs and
per-proto FIB for AS-boundary (type5/7/0x2007/0x4005).
I'd prefer to use fib2_init() for lookups, but fib_init() seems to be
sufficient, too.
We definitely have to convert ipa_to_rid() to some stateful stuff at
least in IPv6 case, but that's the next step.
We also need to deal more accurately with LSA_MAXSEQ.
The idea behind the behavior is that you should either keep the old
seqnum for your LSA when it is flushed (and continue in it when you
reintroduce it), or you should use LSA_MAXSEQNO to ensure that old seqnum
is eliminated from the OSPF domain so you could forget seqnum and later
start from InitSeqNum. The behavior is not according to RFC 2328, but it
is compatible with it. And i have a work-in-progress code that fixes several
issues in the flooding code together with this.
>From f21fffec1f3d45a7da7c33cd5335ce245fbdeae0 Mon Sep 17 00:00:00 2001
From: "Alexander V. Chernikov" <[email protected]>
Date: Sun, 23 Feb 2014 15:17:43 +0000
Subject: [PATCH 1/2] Unify filling LSA header.
---
proto/ospf/topology.c | 165 +++++++++++++++++++++++++++++++-------------------
1 file changed, 104 insertions(+), 61 deletions(-)
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index 4af5afa..6498585 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -24,6 +24,9 @@ void originate_prefix_rt_lsa(struct ospf_area *oa);
void originate_prefix_net_lsa(struct ospf_iface *ifa);
void flush_prefix_net_lsa(struct ospf_iface *ifa);
+static void fill_lsa_header(struct proto_ospf *po, struct ospf_area *oa,
+ struct ospf_lsa_header *lsa, struct fib_node *fn, struct ospf_iface *ifa);
+
#ifdef OSPFv2
#define ipa_to_rid(x) _I(x)
#else /* OSPFv3 */
@@ -485,17 +488,8 @@ originate_rt_lsa(struct ospf_area *oa)
OSPF_TRACE(D_EVENTS, "Originating router-LSA for area %R", oa->areaid);
- lsa.age = 0;
lsa.type = LSA_T_RT;
-
-#ifdef OSPFv2
- lsa.options = oa->options;
- lsa.id = po->router_id;
-#else /* OSPFv3 */
- lsa.id = 0;
-#endif
-
- lsa.rt = po->router_id;
+ fill_lsa_header(po, oa, &lsa, NULL, NULL);
lsa.sn = get_seqnum(oa->rt);
u32 dom = oa->areaid;
@@ -598,17 +592,8 @@ originate_net_lsa(struct ospf_iface *ifa)
OSPF_TRACE(D_EVENTS, "Originating network-LSA for iface %s", ifa->ifname);
- lsa.age = 0;
lsa.type = LSA_T_NET;
-
-#ifdef OSPFv2
- lsa.options = ifa->oa->options;
- lsa.id = ipa_to_u32(ifa->addr->ip);
-#else /* OSPFv3 */
- lsa.id = ifa->iface_id;
-#endif
-
- lsa.rt = po->router_id;
+ fill_lsa_header(po, ifa->oa, &lsa, NULL, ifa);
lsa.sn = get_seqnum(ifa->net_lsa);
body = originate_net_lsa_body(ifa, &lsa.length, po);
@@ -781,14 +766,8 @@ originate_sum_net_lsa(struct ospf_area *oa, struct fib_node *fn, int metric)
OSPF_TRACE(D_EVENTS, "Originating net-summary-LSA for %I/%d (metric %d)",
fn->prefix, fn->pxlen, metric);
- /* options argument is used in ORT_NET and OSPFv3 only */
- lsa.age = 0;
-#ifdef OSPFv2
- lsa.options = oa->options;
-#endif
lsa.type = LSA_T_SUM_NET;
- lsa.id = fibnode_to_lsaid(po, fn);
- lsa.rt = po->router_id;
+ fill_lsa_header(po, oa, &lsa, fn, NULL);
if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
{
@@ -824,16 +803,11 @@ originate_sum_rt_lsa(struct ospf_area *oa, struct fib_node *fn, int metric, u32
OSPF_TRACE(D_EVENTS, "Originating rt-summary-LSA for %R (metric %d)",
rid, metric);
- lsa.age = 0;
-#ifdef OSPFv2
- lsa.options = oa->options;
-#endif
lsa.type = LSA_T_SUM_RT;
- /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */
- lsa.id = rid;
- lsa.rt = po->router_id;
+ fill_lsa_header(po, oa, &lsa, fn, NULL);
options &= OPTIONS_MASK;
+
if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
{
if (check_sum_rt_lsa_same(en, lsa.id, metric, options))
@@ -855,18 +829,8 @@ flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type)
struct top_hash_entry *en;
struct ospf_lsa_header lsa;
- lsa.rt = po->router_id;
- if (type == ORT_NET)
- {
- lsa.id = fibnode_to_lsaid(po, fn);
- lsa.type = LSA_T_SUM_NET;
- }
- else
- {
- /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */
- lsa.id = ipa_to_rid(fn->prefix);
- lsa.type = LSA_T_SUM_RT;
- }
+ lsa.type = (type == ORT_NET) ? LSA_T_SUM_NET : LSA_T_SUM_RT;
+ fill_lsa_header(po, oa, &lsa, fn, NULL);
if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) != NULL)
{
@@ -1083,13 +1047,9 @@ originate_ext_lsa(struct ospf_area *oa, struct fib_node *fn, int src,
OSPF_TRACE(D_EVENTS, "Originating %s-LSA for %I/%d",
nssa ? "NSSA" : "AS-external", fn->prefix, fn->pxlen);
- lsa.age = 0;
-#ifdef OSPFv2
- lsa.options = nssa ? (pbit ? OPT_P : 0) : OPT_E;
-#endif
+
lsa.type = nssa ? LSA_T_NSSA : LSA_T_EXT;
- lsa.id = fibnode_to_lsaid(po, fn);
- lsa.rt = po->router_id;
+ fill_lsa_header(po, oa, &lsa, fn, NULL);
if (nssa && pbit && ipa_zero(fwaddr))
{
@@ -1104,6 +1064,10 @@ originate_ext_lsa(struct ospf_area *oa, struct fib_node *fn, int src,
}
}
+#ifdef OSPFv2
+ lsa.options = nssa ? (pbit ? OPT_P : 0) : OPT_E;
+#endif
+
if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
{
int rv = check_ext_lsa(en, fn, metric, fwaddr, tag);
@@ -1167,6 +1131,91 @@ flush_ext_lsa(struct ospf_area *oa, struct fib_node *fn, int nssa)
}
+/**
+ * fill_lsa_header - fills in initial values for an LSA
+ * @po: OSPF protocol
+ * @oa: Area
+ * @lsa: LSA header pointer
+ * @fn: prefix if any
+ * @ida: OSPF interface if any
+ */
+static void
+fill_lsa_header(struct proto_ospf *po, struct ospf_area *oa, struct ospf_lsa_header *lsa,
+ struct fib_node *fn, struct ospf_iface *ifa)
+{
+ u32 lsid = 0;
+
+ /*
+ * Determine LSID for given LSA
+ *
+ * LSType#, used, scope, key identifier[, used identifier]
+ *
+ * OSPFv2: RFC2328 (A4.2+, 12.4.1+)
+ *
+ * Type1: singleton, area: [0001][RTRID],
+ * Type2: per-prefix, area: [0002][prefix][/cidr], [iface IP]
+ * Type3: per-prefix, area: [0003][prefix][/cidr], fibnode_to_lsaid()
+ * Type4: per-ASBR, area: [0004][ASBRID][/32], fibnode_to_lsaid()
+ * Type5: per-prefix, AS: [0005][prefix][/cidr], fibnode_to_lsaid()
+ * Type7: per-prefix, NSSA: [0007][prefix][/cidr], fibnode_to_lsaid()
+ *
+ * OSPFv3 mappings: RFC 5340 (4.4.3+)
+ * 0x2001: one/many, area: [0x2001][RTRID][/128], [0.0.0.0]
+ * 0x2002: per-link, area: [0x2002][link#][/128]
+ * 0x2003: per-prefix, area: [0x2003][prefix][/cidr], hash(prefix)
+ * 0x2004: per-ASBR, area: [0x2004][ASBRID][/128], RID(/128 route)
+ * 0x4005: per-prefix, AS: [0x4005][prefix][/cidr], hash(prefix)
+ * 0x2007: per-prefix, NSSA: [0x2007][prefix][/cidr], hash(prefix)
+ * 0x0008: per-link, link: [0x0008][iface#]
+ * 0x2009: one/many(RTR), area: [0x2009][??], [0.0.0.0]
+ * 0x2009: one/many(PX), area: [0x2009][iface#]
+ */
+
+ lsa->age = 0;
+#ifdef OSPFv2
+ lsa->options = oa->options;
+#endif
+ lsa->rt = po->router_id;
+
+ switch (lsa->type)
+ {
+#ifdef OSPFv2
+ case LSA_T_RT:
+ /* Singleton, LS id is router ID */
+ lsid = po->router_id;
+ break;
+ case LSA_T_NET:
+ lsid = ipa_to_u32(ifa->addr->ip);
+ break;
+#else
+ case LSA_T_RT:
+ lsid = 0;
+ break;
+ case LSA_T_PREFIX:
+ if (ifa != NULL)
+ lsid = ifa->iface_id; /* network prefix-LSA */
+ else
+ lsid = 0; /* router prefix-LSA */
+ break;
+ case LSA_T_NET:
+ case LSA_T_LINK:
+ lsid = ifa->iface_id;
+ break;
+#endif
+ case LSA_T_SUM_NET:
+ case LSA_T_EXT:
+ case LSA_T_NSSA:
+ lsid = fibnode_to_lsaid(po, fn);
+ break;
+ case LSA_T_SUM_RT:
+ /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */
+ lsid = ipa_to_rid(fn->prefix);
+ break;
+ }
+
+ lsa->id = lsid;
+}
+
#ifdef OSPFv3
static void *
@@ -1216,10 +1265,8 @@ originate_link_lsa(struct ospf_iface *ifa)
OSPF_TRACE(D_EVENTS, "Originating link-LSA for iface %s", ifa->ifname);
- lsa.age = 0;
lsa.type = LSA_T_LINK;
- lsa.id = ifa->iface_id;
- lsa.rt = po->router_id;
+ fill_lsa_header(po, ifa->oa, &lsa, NULL, ifa);
lsa.sn = get_seqnum(ifa->link_lsa);
u32 dom = ifa->iface_id;
@@ -1362,10 +1409,8 @@ originate_prefix_rt_lsa(struct ospf_area *oa)
OSPF_TRACE(D_EVENTS, "Originating router prefix-LSA for area %R", oa->areaid);
- lsa.age = 0;
lsa.type = LSA_T_PREFIX;
- lsa.id = 0;
- lsa.rt = po->router_id;
+ fill_lsa_header(po, oa, &lsa, NULL, NULL);
lsa.sn = get_seqnum(oa->pxr_lsa);
u32 dom = oa->areaid;
@@ -1501,10 +1546,8 @@ originate_prefix_net_lsa(struct ospf_iface *ifa)
OSPF_TRACE(D_EVENTS, "Originating network prefix-LSA for iface %s", ifa->ifname);
- lsa.age = 0;
lsa.type = LSA_T_PREFIX;
- lsa.id = ifa->iface_id;
- lsa.rt = po->router_id;
+ fill_lsa_header(po, ifa->oa, &lsa, NULL, ifa);
lsa.sn = get_seqnum(ifa->pxn_lsa);
u32 dom = ifa->oa->areaid;
--
1.7.11.5
>From 366d8b2bd7c3762db8da1f33d49b86ee63b3af85 Mon Sep 17 00:00:00 2001
From: "Alexander V. Chernikov" <[email protected]>
Date: Sun, 23 Feb 2014 16:56:50 +0000
Subject: [PATCH 2/2] Remember sequence number for LSAs.
---
proto/ospf/iface.c | 2 +-
proto/ospf/lsalib.c | 5 +-
proto/ospf/lsupd.c | 15 +--
proto/ospf/lsupd.h | 2 +-
proto/ospf/ospf.c | 8 ++
proto/ospf/ospf.h | 4 +
proto/ospf/topology.c | 306 +++++++++++++++++++++++++++++++++++++++++++-------
proto/ospf/topology.h | 17 +++
8 files changed, 301 insertions(+), 58 deletions(-)
diff --git a/proto/ospf/iface.c b/proto/ospf/iface.c
index f4d9be5..171cf7e 100644
--- a/proto/ospf/iface.c
+++ b/proto/ospf/iface.c
@@ -318,7 +318,7 @@ ospf_iface_chstate(struct ospf_iface *ifa, u8 state)
{
ifa->net_lsa->lsa.age = LSA_MAXAGE;
if (state >= OSPF_IS_WAITING)
- ospf_lsupd_flush_nlsa(po, ifa->net_lsa);
+ ospf_lsupd_flush_nlsa(po, ifa->oa, ifa->net_lsa);
if (can_flush_lsa(po))
flush_lsa(ifa->net_lsa, po);
diff --git a/proto/ospf/lsalib.c b/proto/ospf/lsalib.c
index bcf7bcd..2b238e3 100644
--- a/proto/ospf/lsalib.c
+++ b/proto/ospf/lsalib.c
@@ -69,10 +69,7 @@ ospf_age(struct proto_ospf *po)
{
OSPF_TRACE(D_EVENTS, "Refreshing my LSA: Type: %u, Id: %R, Rt: %R",
en->lsa.type, en->lsa.id, en->lsa.rt);
- en->lsa.sn++;
- en->lsa.age = 0;
- en->inst_t = now;
- en->ini_age = 0;
+ update_lsa_seq(po, en, en->lsa.sn + 1); /* XXX: LSA_MAXSEQNO */
lsasum_calculate(&en->lsa, en->lsa_body);
ospf_lsupd_flood(po, NULL, NULL, &en->lsa, en->domain, 1);
continue;
diff --git a/proto/ospf/lsupd.c b/proto/ospf/lsupd.c
index 8f65c53..65c9ae4 100644
--- a/proto/ospf/lsupd.c
+++ b/proto/ospf/lsupd.c
@@ -600,20 +600,14 @@ ospf_lsupd_receive(struct ospf_packet *ps_i, struct ospf_iface *ifa,
if (lsadb)
{
OSPF_TRACE(D_EVENTS, "Reflooding new self-originated LSA with newer sequence number");
- lsadb->lsa.sn = lsatmp.sn + 1;
- lsadb->lsa.age = 0;
- lsadb->inst_t = now;
- lsadb->ini_age = 0;
- lsasum_calculate(&lsadb->lsa, lsadb->lsa_body);
+ update_lsa_seq(po, lsadb, lsatmp.sn + 1); /* XXX: lsatmp.sn == LSA_MAXSEQNO - 1 */
ospf_lsupd_flood(po, NULL, NULL, &lsadb->lsa, domain, 1);
}
else
{
OSPF_TRACE(D_EVENTS, "Premature aging it");
lsatmp.age = LSA_MAXAGE;
- lsatmp.sn = LSA_MAXSEQNO;
lsa->age = htons(LSA_MAXAGE);
- lsa->sn = htonl(LSA_MAXSEQNO);
lsasum_check(lsa, (lsa + 1)); /* It also calculates chsum! */
lsatmp.checksum = ntohs(lsa->checksum);
ospf_lsupd_flood(po, NULL, lsa, &lsatmp, domain, 0);
@@ -749,14 +743,13 @@ ospf_lsupd_receive(struct ospf_packet *ps_i, struct ospf_iface *ifa,
}
void
-ospf_lsupd_flush_nlsa(struct proto_ospf *po, struct top_hash_entry *en)
+ospf_lsupd_flush_nlsa(struct proto_ospf *po, struct ospf_area *oa, struct top_hash_entry *en)
{
struct ospf_lsa_header *lsa = &en->lsa;
struct proto *p = &po->proto;
- lsa->age = LSA_MAXAGE;
- lsa->sn = LSA_MAXSEQNO;
- lsasum_calculate(lsa, en->lsa_body);
+ flush_lsa_seq(po, oa, en);
+
OSPF_TRACE(D_EVENTS, "Premature aging self originated lsa!");
OSPF_TRACE(D_EVENTS, "Type: %04x, Id: %R, Rt: %R", lsa->type, lsa->id, lsa->rt);
ospf_lsupd_flood(po, NULL, NULL, lsa, en->domain, 0);
diff --git a/proto/ospf/lsupd.h b/proto/ospf/lsupd.h
index 8bacfe6..780ba9d 100644
--- a/proto/ospf/lsupd.h
+++ b/proto/ospf/lsupd.h
@@ -18,7 +18,7 @@ void ospf_lsupd_receive(struct ospf_packet *ps_i,
int ospf_lsupd_flood(struct proto_ospf *po,
struct ospf_neighbor *n, struct ospf_lsa_header *hn,
struct ospf_lsa_header *hh, u32 domain, int rtl);
-void ospf_lsupd_flush_nlsa(struct proto_ospf *po, struct top_hash_entry *en);
+void ospf_lsupd_flush_nlsa(struct proto_ospf *po, struct ospf_area *oa, struct top_hash_entry *en);
int ospf_lsa_flooding_allowed(struct ospf_lsa_header *lsa, u32 domain, struct ospf_iface *ifa);
diff --git a/proto/ospf/ospf.c b/proto/ospf/ospf.c
index e751f7c..0684de9 100644
--- a/proto/ospf/ospf.c
+++ b/proto/ospf/ospf.c
@@ -178,6 +178,8 @@ ospf_area_add(struct proto_ospf *po, struct ospf_area_config *ac, int reconf)
if (oa_is_nssa(oa) && ((struct ospf_config *) (p->cf))->abr)
po->ebit = 1;
+ init_seq_fib(po, oa);
+
if (reconf)
ospf_ifaces_reconfigure(oa, ac);
}
@@ -198,6 +200,8 @@ ospf_area_remove(struct ospf_area *oa)
if (oa->translator_timer)
rfree(oa->translator_timer);
+ free_seq_fib(oa->po, oa);
+
oa->po->areano--;
rem_node(NODE oa);
mb_free(oa);
@@ -265,6 +269,8 @@ ospf_start(struct proto *p)
WALK_LIST(ic, c->vlink_list)
ospf_iface_new_vlink(po, ic);
+ init_seq_fib(po, NULL);
+
return PS_UP;
}
@@ -563,6 +569,8 @@ ospf_shutdown(struct proto *p)
}
FIB_WALK_END;
+ free_seq_fib(po, NULL);
+
return PS_DOWN;
}
diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h
index 66719e3..44b3344 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -756,6 +756,8 @@ struct ospf_area
timer *translator_timer; /* For NSSA translator switch */
struct proto_ospf *po;
struct fib rtr; /* Routing tables for routers */
+ struct fib seq_fib; /* Sequence number storage for LSAs */
+ timer *seq_timer; /* Timer for seq_fib pruning */
};
#define TRANS_OFF 0
@@ -786,6 +788,8 @@ struct proto_ospf
sock *vlink_sk; /* IP socket used for vlink TX */
u32 router_id;
u32 last_vlink_id; /* Interface IDs for vlinks (starts at 0x80000000) */
+ struct fib seq_fib; /* Sequence number storage for external LSAs */
+ timer *seq_timer; /* Timer for seq_fib pruning */
};
struct ospf_iface_patt
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index 6498585..cc4c97a 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -27,6 +27,9 @@ void flush_prefix_net_lsa(struct ospf_iface *ifa);
static void fill_lsa_header(struct proto_ospf *po, struct ospf_area *oa,
struct ospf_lsa_header *lsa, struct fib_node *fn, struct ospf_iface *ifa);
+static s32 get_lsa_seq(struct proto_ospf *po, struct ospf_area *oa, struct ospf_lsa_header *lsa);
+static void check_seq_fibs(struct timer *timer);
+
#ifdef OSPFv2
#define ipa_to_rid(x) _I(x)
#else /* OSPFv3 */
@@ -141,23 +144,6 @@ lsab_end(struct proto_ospf *po)
return ((byte *) po->lsab) + po->lsab_used;
}
-static s32
-get_seqnum(struct top_hash_entry *en)
-{
- if (!en)
- return LSA_INITSEQNO;
-
- if (en->lsa.sn == LSA_MAXSEQNO)
- {
- log(L_WARN "OSPF: Premature origination of LSA (Type: %04x, Id: %R, Rt: %R)",
- en->lsa.type, en->lsa.id, en->lsa.rt);
- return LSA_INITSEQNO;
- }
-
- return en->lsa.sn + 1;
-}
-
-
static int
configured_stubnet(struct ospf_area *oa, struct ifa *a)
{
@@ -490,7 +476,7 @@ originate_rt_lsa(struct ospf_area *oa)
lsa.type = LSA_T_RT;
fill_lsa_header(po, oa, &lsa, NULL, NULL);
- lsa.sn = get_seqnum(oa->rt);
+ lsa.sn = get_lsa_seq(po, oa, &lsa);
u32 dom = oa->areaid;
body = originate_rt_lsa_body(oa, &lsa.length);
@@ -594,7 +580,7 @@ originate_net_lsa(struct ospf_iface *ifa)
lsa.type = LSA_T_NET;
fill_lsa_header(po, ifa->oa, &lsa, NULL, ifa);
- lsa.sn = get_seqnum(ifa->net_lsa);
+ lsa.sn = get_lsa_seq(po, ifa->oa, &lsa);
body = originate_net_lsa_body(ifa, &lsa.length, po);
lsasum_calculate(&lsa, body);
@@ -613,9 +599,7 @@ flush_net_lsa(struct ospf_iface *ifa)
return;
OSPF_TRACE(D_EVENTS, "Flushing network-LSA for iface %s", ifa->ifname);
- ifa->net_lsa->lsa.sn += 1;
- ifa->net_lsa->lsa.age = LSA_MAXAGE;
- lsasum_calculate(&ifa->net_lsa->lsa, ifa->net_lsa->lsa_body);
+ flush_lsa_seq(po, ifa->oa, ifa->net_lsa);
ospf_lsupd_flood(po, NULL, NULL, &ifa->net_lsa->lsa, dom, 0);
flush_lsa(ifa->net_lsa, po);
ifa->net_lsa = NULL;
@@ -684,7 +668,7 @@ check_sum_lsa_same(struct top_hash_entry *en, u32 metric)
{
/* Netmask already checked in check_sum_net_lsaid_collision() */
struct ospf_lsa_sum *sum = en->lsa_body;
- return (en->lsa.sn != LSA_MAXSEQNO) && (sum->metric == metric);
+ return (en->lsa.age != LSA_MAXAGE) && (sum->metric == metric);
}
#define check_sum_net_lsa_same(en,metric) \
@@ -727,7 +711,7 @@ check_sum_net_lsa_same(struct top_hash_entry *en, u32 metric)
{
/* Prefix already checked in check_sum_net_lsaid_collision() */
struct ospf_lsa_sum_net *sum = en->lsa_body;
- return (en->lsa.sn != LSA_MAXSEQNO) && (sum->metric == metric);
+ return (en->lsa.age != LSA_MAXAGE) && (sum->metric == metric);
}
static inline void *
@@ -747,7 +731,7 @@ static inline int
check_sum_rt_lsa_same(struct top_hash_entry *en, u32 drid, u32 metric, u32 options)
{
struct ospf_lsa_sum_rt *sum = en->lsa_body;
- return (en->lsa.sn != LSA_MAXSEQNO) && (sum->options == options) &&
+ return (en->lsa.age != LSA_MAXAGE) && (sum->options == options) &&
(sum->metric == metric) && (sum->drid == drid);
}
@@ -781,7 +765,7 @@ originate_sum_net_lsa(struct ospf_area *oa, struct fib_node *fn, int metric)
if (check_sum_net_lsa_same(en, metric))
return;
}
- lsa.sn = get_seqnum(en);
+ lsa.sn = get_lsa_seq(po, oa, &lsa);
body = originate_sum_net_lsa_body(po, &lsa.length, fn, metric);
lsasum_calculate(&lsa, body);
@@ -813,7 +797,7 @@ originate_sum_rt_lsa(struct ospf_area *oa, struct fib_node *fn, int metric, u32
if (check_sum_rt_lsa_same(en, lsa.id, metric, options))
return;
}
- lsa.sn = get_seqnum(en);
+ lsa.sn = get_lsa_seq(po, oa, &lsa);
body = originate_sum_rt_lsa_body(po, &lsa.length, lsa.id, metric, options);
lsasum_calculate(&lsa, body);
@@ -844,10 +828,7 @@ flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type)
return;
}
- struct ospf_lsa_sum *sum = en->lsa_body;
- en->lsa.age = LSA_MAXAGE;
- en->lsa.sn = LSA_MAXSEQNO;
- lsasum_calculate(&en->lsa, sum);
+ flush_lsa_seq(po, oa, en);
ospf_lsupd_flood(po, NULL, NULL, &en->lsa, oa->areaid, 1);
if (can_flush_lsa(po)) flush_lsa(en, po);
}
@@ -893,7 +874,7 @@ check_ext_lsa(struct top_hash_entry *en, struct fib_node *fn, u32 metric, ip_add
if (fn->pxlen != ipa_mklen(ext->netmask))
return -1;
- return (en->lsa.sn != LSA_MAXSEQNO) && (ext->metric == metric) &&
+ return (en->lsa.age != LSA_MAXAGE) && (ext->metric == metric) &&
(ext->tag == tag) && ipa_equal(ext->fwaddr,fwaddr);
}
@@ -946,7 +927,7 @@ check_ext_lsa(struct top_hash_entry *en, struct fib_node *fn, u32 metric, ip_add
if ((fn->pxlen != pxlen) || !ipa_equal(fn->prefix, prefix))
return -1;
- if (en->lsa.sn == LSA_MAXSEQNO)
+ if (en->lsa.age == LSA_MAXAGE)
return 0;
u32 rt_metric = ext->metric & METRIC_MASK;
@@ -1081,7 +1062,7 @@ originate_ext_lsa(struct ospf_area *oa, struct fib_node *fn, int src,
if (rv > 0)
return;
}
- lsa.sn = get_seqnum(en);
+ lsa.sn = get_lsa_seq(po, NULL, &lsa);
body = originate_ext_lsa_body(po, &lsa.length, fn, metric, fwaddr, tag, pbit);
lsasum_calculate(&lsa, body);
@@ -1126,7 +1107,7 @@ flush_ext_lsa(struct ospf_area *oa, struct fib_node *fn, int nssa)
}
fn->x1 = 0;
- ospf_lsupd_flush_nlsa(po, en);
+ ospf_lsupd_flush_nlsa(po, NULL, en);
}
}
@@ -1216,6 +1197,251 @@ fill_lsa_header(struct proto_ospf *po, struct ospf_area *oa, struct ospf_lsa_hea
lsa->id = lsid;
}
+static struct seq_data *
+find_seq(struct proto_ospf *po, struct ospf_area *oa, struct ospf_lsa_header *lsa, int create)
+{
+ struct seq_fib_data *sfd;
+ struct fib *seq_fib;
+ ip_addr addr;
+
+ memset(&addr, 0, sizeof(addr));
+#ifdef IPV6
+ _I3(addr) = lsa->id;
+#else
+ addr = _I(lsa->id);
+#endif
+
+ if (oa != NULL)
+ seq_fib = &oa->seq_fib;
+ else
+ seq_fib = &po->seq_fib;
+
+ if (create != 0)
+ sfd = (struct seq_fib_data *)fib_get(seq_fib, &addr, BITS_PER_IP_ADDRESS);
+ else
+ sfd = (struct seq_fib_data *)fib_find(seq_fib, &addr, BITS_PER_IP_ADDRESS);
+
+ if (sfd == NULL)
+ return NULL;
+
+ return &sfd->type[lsa->type % SEQ_DATA_MAX];
+}
+
+static s32
+get_lsa_seq(struct proto_ospf *po, struct ospf_area *oa, struct ospf_lsa_header *lsa)
+{
+ struct seq_data *sd;
+
+ sd = find_seq(po, oa, lsa, 1);
+
+ if (sd->active == 0)
+ {
+ /* New entry */
+ sd->seq = LSA_INITSEQNO;
+ }
+ else
+ {
+ if (++sd->seq == LSA_MAXSEQNO)
+ {
+ /*
+ * According to 12.1.6 in 2338 RFC
+ * we need to ensure that previous version
+ * is flushed:
+ *
+ * 'As soon as this flood has been acknowledged by
+ * all adjacent neighbors, a new instance can be
+ * originated with sequence number of InitialSequenceNumber.'
+ *
+ * XXX: We're currently not controlling if our adjacent neighbors
+ * acknowledge LSA flush. However, since this is VERY rare case,
+ * simply set seq to InitialSequenceNumber.
+ */
+ sd->seq = LSA_INITSEQNO;
+ }
+ }
+
+ sd->active = 1;
+ sd->last = now;
+
+ return sd->seq;
+}
+
+/**
+ * update_lsa_seq - updates age/seq/checksum for given LSA.
+ * @po: OSPF protocol
+ * @oa: OSPF area
+ * @en: LSA base
+ * @sn: new checksum
+ */
+void
+update_lsa_seq(struct proto_ospf *po, struct top_hash_entry *en, s32 sn)
+{
+ struct ospf_lsa_header *lsa = &en->lsa;
+ struct ospf_area *oa = NULL;
+ struct seq_data *sd;
+
+ lsa->sn = sn;
+ lsa->age = 0;
+ en->inst_t = now;
+ en->ini_age = 0;
+ lsasum_calculate(lsa, en->lsa_body);
+
+ /*
+ * Get area to search into.
+ * Treat LSA_SCOPE_LINK as AREA and
+ * LSA_SCOPE_RES (if any) as AS
+ */
+ switch (LSA_SCOPE(lsa))
+ {
+#ifndef OSPFv2
+ case LSA_SCOPE_LINK:
+#endif
+ case LSA_SCOPE_AREA:
+ oa = ospf_find_area(po, en->domain);
+ break;
+ }
+
+ if ((sd = find_seq(po, oa, lsa, 0)) == NULL)
+ {
+ log(L_WARN "Unable to find LSA sequence for LSA (id=%R type %d)", lsa->id, lsa->type);
+ return;
+ }
+
+ sd->seq = lsa->sn;
+ sd->last = now;
+}
+
+/**
+ * flush_lsa_seq - notify we're not using given LSA anymore. Updates LSA age/checksum.
+ * @po: OSPF protocol
+ * @oa: OSPF area
+ * @en: LSA base
+ */
+void
+flush_lsa_seq(struct proto_ospf *po, struct ospf_area *oa, struct top_hash_entry *en)
+{
+ struct ospf_lsa_header *lsa = &en->lsa;
+ struct seq_data *sd;
+
+ lsa->age = LSA_MAXAGE;
+ lsasum_calculate(lsa, en->lsa_body);
+
+ if ((sd = find_seq(po, oa, lsa, 0)) == NULL)
+ {
+ log(L_WARN "Unable to flush LSA sequence for LSA (id=%R type %d)", lsa->id, lsa->type);
+ return;
+ }
+
+ sd->active = -1;
+ sd->last = now;
+}
+
+/**
+ * check_seq_fib - remove unused prefixes from fib
+ * @po: OSPF protocol
+ * @seq_fib: fib put prune
+ */
+static void
+check_seq_fib(struct proto_ospf *po, struct fib *seq_fib)
+{
+ struct fib_iterator fit;
+ struct seq_fib_data *sfd;
+ struct seq_data *sd;
+ int i, keep;
+
+ FIB_ITERATE_INIT(&fit, seq_fib);
+again:
+ FIB_ITERATE_START(seq_fib, &fit, nftmp)
+ {
+ sfd = (struct seq_fib_data *) nftmp;
+
+ /*
+ * Check if we need purge "old" prefixes.
+ *
+ * RFC 2328, 14 tells us:
+ *
+ * A MaxAge LSA must be removed immediately from the router's link
+ * state database as soon as both a) it is no longer contained on any
+ * neighbor Link state retransmission lists and b) none of the router's
+ * neighbors are in states Exchange or Loading.
+ *
+ * This basically means we have no guaranteed timing on MaxAge LSA
+ * removal, so we keep entries for considerably long amount of time.
+ */
+ keep = 0;
+ for (i = 0; i < SEQ_DATA_MAX; i++)
+ {
+ sd = &sfd->type[i];
+ if (sd->active == 1 || sd->last + 3600 >= now)
+ keep = 1;
+ }
+ if (keep == 0)
+ {
+ FIB_ITERATE_PUT(&fit, nftmp);
+ fib_delete(seq_fib, nftmp);
+ goto again;
+ }
+ }
+ FIB_ITERATE_END(nftmp);
+}
+
+/**
+ * check_seq_fib - remove unused prefixes from fib
+ * @timer: timer
+ */
+static void
+check_seq_fibs(timer *timer)
+{
+ struct proto_ospf *po = timer->data;
+ struct ospf_area *oa;
+
+ /* Check protocol fib first */
+ check_seq_fib(po, &po->seq_fib);
+
+ WALK_LIST(oa, po->area_list)
+ check_seq_fib(po, &oa->seq_fib);
+}
+
+
+/**
+ * init_seq_fib - Initialize fib for sequence storage
+ * @po: OSPF protocol
+ * @oa: OSPF area, if set
+ */
+void
+init_seq_fib(struct proto_ospf *po, struct ospf_area *oa)
+{
+ timer *t;
+ struct fib *seq_fib = (oa == NULL) ? &po->seq_fib : &oa->seq_fib;
+
+ fib_init(seq_fib, po->proto.pool, sizeof(struct seq_fib_data), 0, NULL);
+
+ if (oa == NULL)
+ {
+ t = tm_new(po->proto.pool);
+ t->data = po;
+ t->randomize = 0;
+ t->hook = check_seq_fibs;
+ t->recurrent = 3600 / 3;
+ po->seq_timer = t;
+ tm_start(t, t->recurrent);
+ }
+}
+
+/**
+ * free_seq_fib - iFree sequence storage fib
+ * @po: OSPF protocol
+ */
+void
+free_seq_fib(struct proto_ospf *po, struct ospf_area *oa)
+{
+ struct fib *seq_fib = (oa == NULL) ? &po->seq_fib : &oa->seq_fib;
+
+ fib_free(seq_fib);
+ if (oa != NULL)
+ rfree(oa->seq_timer);
+}
+
#ifdef OSPFv3
static void *
@@ -1267,7 +1493,7 @@ originate_link_lsa(struct ospf_iface *ifa)
lsa.type = LSA_T_LINK;
fill_lsa_header(po, ifa->oa, &lsa, NULL, ifa);
- lsa.sn = get_seqnum(ifa->link_lsa);
+ lsa.sn = get_lsa_seq(po, ifa->oa, &lsa);
u32 dom = ifa->iface_id;
body = originate_link_lsa_body(ifa, &lsa.length);
@@ -1411,7 +1637,7 @@ originate_prefix_rt_lsa(struct ospf_area *oa)
lsa.type = LSA_T_PREFIX;
fill_lsa_header(po, oa, &lsa, NULL, NULL);
- lsa.sn = get_seqnum(oa->pxr_lsa);
+ lsa.sn = get_lsa_seq(po, oa, &lsa);
u32 dom = oa->areaid;
body = originate_prefix_rt_lsa_body(oa, &lsa.length);
@@ -1548,7 +1774,7 @@ originate_prefix_net_lsa(struct ospf_iface *ifa)
lsa.type = LSA_T_PREFIX;
fill_lsa_header(po, ifa->oa, &lsa, NULL, ifa);
- lsa.sn = get_seqnum(ifa->pxn_lsa);
+ lsa.sn = get_lsa_seq(po, ifa->oa, &lsa);
u32 dom = ifa->oa->areaid;
body = originate_prefix_net_lsa_body(ifa, &lsa.length);
@@ -1570,9 +1796,7 @@ flush_prefix_net_lsa(struct ospf_iface *ifa)
OSPF_TRACE(D_EVENTS, "Flushing network prefix-LSA for iface %s", ifa->ifname);
- en->lsa.sn += 1;
- en->lsa.age = LSA_MAXAGE;
- lsasum_calculate(&en->lsa, en->lsa_body);
+ flush_lsa_seq(po, ifa->oa, en);
ospf_lsupd_flood(po, NULL, NULL, &en->lsa, dom, 0);
flush_lsa(en, po);
ifa->pxn_lsa = NULL;
diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h
index cb87648..5cc64c9 100644
--- a/proto/ospf/topology.h
+++ b/proto/ospf/topology.h
@@ -47,6 +47,19 @@ struct top_graph
unsigned int hash_entries_min, hash_entries_max;
};
+struct seq_data {
+ int active;
+ s32 seq;
+ bird_clock_t last;
+};
+#define SEQ_DATA_MAX 16
+
+struct seq_fib_data
+{
+ struct fib_node fn;
+ struct seq_data type[SEQ_DATA_MAX]; /* One for each possible LSA types */
+};
+
struct top_graph *ospf_top_new(pool *);
void ospf_top_free(struct top_graph *);
void ospf_top_dump(struct top_graph *, struct proto *);
@@ -73,6 +86,10 @@ void originate_sum_rt_lsa(struct ospf_area *oa, struct fib_node *fn, int metric,
void flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type);
void originate_ext_lsa(struct ospf_area *oa, struct fib_node *fn, int src, u32 metric, ip_addr fwaddr, u32 tag, int pbit);
void flush_ext_lsa(struct ospf_area *oa, struct fib_node *fn, int nssa);
+void flush_lsa_seq(struct proto_ospf *po, struct ospf_area *oa, struct top_hash_entry *en);
+void update_lsa_seq(struct proto_ospf *po, struct top_hash_entry *en, s32 sn);
+void init_seq_fib(struct proto_ospf *po, struct ospf_area *oa);
+void free_seq_fib(struct proto_ospf *po, struct ospf_area *oa);
#ifdef OSPFv2
--
1.7.11.5
