summaryrefslogtreecommitdiffstats
path: root/proto/ospf/topology.c
diff options
context:
space:
mode:
Diffstat (limited to 'proto/ospf/topology.c')
-rw-r--r--proto/ospf/topology.c1420
1 files changed, 1083 insertions, 337 deletions
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index 5d8c7a9..4665681 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -20,7 +20,76 @@
#define HASH_LO_STEP 2
#define HASH_LO_MIN 8
-int ptp_unnumbered_stub_lsa = 0;
+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);
+
+#ifdef OSPFv2
+#define ipa_to_rid(x) _I(x)
+#else /* OSPFv3 */
+#define ipa_to_rid(x) _I3(x)
+#endif
+
+
+#ifdef OSPFv2
+static inline u32
+fibnode_to_lsaid(struct proto_ospf *po, struct fib_node *fn)
+{
+ /* We have to map IP prefixes to u32 in such manner that resulting
+ u32 interpreted as IP address is a member of given
+ prefix. Therefore, /32 prefix have to be mapped on itself.
+ All received prefixes have to be mapped on different u32s.
+
+ We have an assumption that if there is nontrivial (non-/32)
+ network prefix, then there is not /32 prefix for the first
+ and the last IP address of the network (these are usually
+ reserved, therefore it is not an important restriction).
+ The network prefix is mapped to the first or the last
+ IP address in the manner that disallow collisions - we
+ use IP address that cannot be used by parent prefix.
+
+ For example:
+ 192.168.0.0/24 maps to 192.168.0.255
+ 192.168.1.0/24 maps to 192.168.1.0
+ because 192.168.0.0 and 192.168.1.255 might be used by
+ 192.168.0.0/23 .
+
+ This is not compatible with older RFC 1583, so we have an option
+ to the RFC 1583 compatible assignment (that always uses the first
+ address) which disallows subnetting.
+
+ Appendig E of RFC 2328 suggests different algorithm, that tries
+ to maximize both compatibility and subnetting. But as it is not
+ possible to have both reliably and the suggested algorithm was
+ unnecessary complicated and it does crazy things like changing
+ LSA ID for a network because different network appeared, we
+ choose a different way. */
+
+ u32 id = _I(fn->prefix);
+
+ if ((po->rfc1583) || (fn->pxlen == 0) || (fn->pxlen == 32))
+ return id;
+
+ if (id & (1 << (32 - fn->pxlen)))
+ return id;
+ else
+ return id | ~u32_mkmask(fn->pxlen);
+}
+
+#else /* OSPFv3 */
+
+static inline u32
+fibnode_to_lsaid(struct proto_ospf *po, struct fib_node *fn)
+{
+ /* In OSPFv3, it is simpler. There is not a requirement
+ for membership of the result in input network, so we
+ just use hash-based unique ID. */
+
+ return fn->uid;
+}
+
+#endif
+
static void *
lsab_alloc(struct proto_ospf *po, unsigned size)
@@ -52,6 +121,19 @@ lsab_flush(struct proto_ospf *po)
return r;
}
+static inline void *
+lsab_offset(struct proto_ospf *po, unsigned offset)
+{
+ return ((byte *) po->lsab) + offset;
+}
+
+static inline void *
+lsab_end(struct proto_ospf *po)
+{
+ return ((byte *) po->lsab) + po->lsab_used;
+}
+
+
static int
configured_stubnet(struct ospf_area *oa, struct ifa *a)
{
@@ -72,25 +154,53 @@ configured_stubnet(struct ospf_area *oa, struct ifa *a)
return 0;
}
+int
+bcast_net_active(struct ospf_iface *ifa)
+{
+ struct ospf_neighbor *neigh;
+
+ if (ifa->state == OSPF_IS_WAITING)
+ return 0;
+
+ WALK_LIST(neigh, ifa->neigh_list)
+ {
+ if (neigh->state == NEIGHBOR_FULL)
+ {
+ if (neigh->rid == ifa->drid)
+ return 1;
+
+ if (ifa->state == OSPF_IS_DR)
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
+
+#ifdef OSPFv2
+
static void *
-originate_rt_lsa_body(struct ospf_area *oa, u16 * length)
+originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
{
struct proto_ospf *po = oa->po;
struct ospf_iface *ifa;
- int i = 0, j = 0, k = 0, bitv = 0;
+ int i = 0, bitv = 0;
struct ospf_lsa_rt *rt;
struct ospf_lsa_rt_link *ln;
struct ospf_neighbor *neigh;
- DBG("%s: Originating RT_lsa body for area %R.\n", po->proto.name,
- oa->areaid);
-
ASSERT(po->lsab_used == 0);
rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt));
+
+ rt->options = 0;
+
if (po->areano > 1)
- rt->veb.bit.b = 1;
+ rt->options |= OPT_RT_B;
+
if ((po->ebit) && (!oa->stub))
- rt->veb.bit.e = 1;
+ rt->options |= OPT_RT_E;
+
rt = NULL; /* buffer might be reallocated later */
WALK_LIST(ifa, po->iface_list)
@@ -123,7 +233,7 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 * length)
ln->data = (ifa->iface->addr->flags & IA_UNNUMBERED) ?
ifa->iface->index : ipa_to_u32(ifa->iface->addr->ip);
ln->metric = ifa->cost;
- ln->notos = 0;
+ ln->padding = 0;
i++;
master = 1;
}
@@ -131,26 +241,14 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 * length)
case OSPF_IT_BCAST: /* RFC2328 - 12.4.1.2 */
case OSPF_IT_NBMA:
- if (ifa->state == OSPF_IS_WAITING)
- break;
-
- j = 0, k = 0;
- WALK_LIST(neigh, ifa->neigh_list)
- {
- if ((neigh->rid == ifa->drid) && (neigh->state == NEIGHBOR_FULL))
- k = 1;
- if (neigh->state == NEIGHBOR_FULL)
- j = 1;
- }
-
- if (((ifa->state == OSPF_IS_DR) && (j == 1)) || (k == 1))
+ if (bcast_net_active(ifa))
{
ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
ln->type = LSART_NET;
ln->id = ipa_to_u32(ifa->drip);
ln->data = ipa_to_u32(ifa->iface->addr->ip);
ln->metric = ifa->cost;
- ln->notos = 0;
+ ln->padding = 0;
i++;
master = 1;
}
@@ -165,7 +263,7 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 * length)
ln->id = neigh->rid;
ln->data = ipa_to_u32(ifa->iface->addr->ip);
ln->metric = ifa->cost;
- ln->notos = 0;
+ ln->padding = 0;
i++;
master = 1;
}
@@ -192,7 +290,7 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 * length)
ln->id = ipa_to_u32(a->prefix);
ln->data = ipa_to_u32(ipa_mkmask(a->pxlen));
ln->metric = ifa->cost;
- ln->notos = 0;
+ ln->padding = 0;
i++;
}
}
@@ -206,17 +304,111 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 * length)
ln->id = ipa_to_u32(sn->px.addr);
ln->data = ipa_to_u32(ipa_mkmask(sn->px.len));
ln->metric = sn->cost;
- ln->notos = 0;
+ ln->padding = 0;
i++;
}
rt = po->lsab;
rt->links = i;
- rt->veb.bit.v = bitv;
+
+ if (bitv)
+ rt->options |= OPT_RT_V;
+
*length = po->lsab_used + sizeof(struct ospf_lsa_header);
return lsab_flush(po);
}
+#else /* OSPFv3 */
+
+static void
+add_lsa_rt_link(struct proto_ospf *po, struct ospf_iface *ifa, u8 type, u32 nif, u32 id)
+{
+ struct ospf_lsa_rt_link *ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
+ ln->type = type;
+ ln->padding = 0;
+ ln->metric = ifa->cost;
+ ln->lif = ifa->iface->index;
+ ln->nif = nif;
+ ln->id = id;
+}
+
+static void *
+originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
+{
+ struct proto_ospf *po = oa->po;
+ struct ospf_iface *ifa;
+ int bitv = 0;
+ struct ospf_lsa_rt *rt;
+ struct ospf_neighbor *neigh;
+
+ ASSERT(po->lsab_used == 0);
+ rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt));
+
+ rt->options = oa->options & OPTIONS_MASK;
+
+ if (po->areano > 1)
+ rt->options |= OPT_RT_B;
+
+ if ((po->ebit) && (!oa->stub))
+ rt->options |= OPT_RT_E;
+
+ rt = NULL; /* buffer might be reallocated later */
+
+ WALK_LIST(ifa, po->iface_list)
+ {
+ if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
+ (!EMPTY_LIST(ifa->neigh_list)))
+ {
+ neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
+ if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
+ bitv = 1;
+ }
+
+ if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
+ continue;
+
+ /* BIRD does not support interface loops */
+ ASSERT(ifa->state != OSPF_IS_LOOP);
+
+ /* RFC5340 - 4.4.3.2 */
+ switch (ifa->type)
+ {
+ case OSPF_IT_PTP:
+ neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
+ if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL))
+ add_lsa_rt_link(po, ifa, LSART_PTP, neigh->iface_id, neigh->rid);
+ break;
+
+ case OSPF_IT_BCAST:
+ case OSPF_IT_NBMA:
+ if (bcast_net_active(ifa))
+ add_lsa_rt_link(po, ifa, LSART_NET, ifa->dr_iface_id, ifa->drid);
+ break;
+
+ case OSPF_IT_VLINK:
+ neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
+ if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
+ add_lsa_rt_link(po, ifa, LSART_VLNK, neigh->iface_id, neigh->rid);
+ break;
+
+ default:
+ log("Unknown interface type %s", ifa->iface->name);
+ break;
+ }
+ }
+
+ if (bitv)
+ {
+ rt = po->lsab;
+ rt->options |= OPT_RT_V;
+ }
+
+ *length = po->lsab_used + sizeof(struct ospf_lsa_header);
+ return lsab_flush(po);
+}
+
+#endif
+
/**
* originate_rt_lsa - build new instance of router LSA
* @oa: ospf_area which is LSA built to
@@ -232,10 +424,33 @@ originate_rt_lsa(struct ospf_area *oa)
struct ospf_lsa_header lsa;
struct proto_ospf *po = oa->po;
struct proto *p = &po->proto;
- u32 rtid = po->proto.cf->global->router_id;
- struct top_hash_entry *en;
void *body;
+ 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;
+#endif
+
+ lsa.id = po->router_id;
+ lsa.rt = po->router_id;
+ lsa.sn = oa->rt ? (oa->rt->lsa.sn + 1) : LSA_INITSEQNO;
+ u32 dom = oa->areaid;
+
+ body = originate_rt_lsa_body(oa, &lsa.length);
+ lsasum_calculate(&lsa, body);
+ oa->rt = lsa_install_new(po, &lsa, dom, body);
+ ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
+}
+
+void
+update_rt_lsa(struct ospf_area *oa)
+{
+ struct proto_ospf *po = oa->po;
+
if ((oa->rt) && ((oa->rt->inst_t + MINLSINTERVAL)) > now)
return;
/*
@@ -244,59 +459,65 @@ originate_rt_lsa(struct ospf_area *oa)
* try to do it next tick.
*/
- OSPF_TRACE(D_EVENTS, "Originating RT_lsa for area %R.", oa->areaid);
+ originate_rt_lsa(oa);
+#ifdef OSPFv3
+ originate_prefix_rt_lsa(oa);
+#endif
- lsa.age = 0;
- lsa.id = rtid;
- lsa.type = LSA_T_RT;
- lsa.rt = rtid;
- lsa.options = oa->opt.byte;
- if (oa->rt == NULL)
- {
- lsa.sn = LSA_INITSEQNO;
- }
- else
- {
- lsa.sn = oa->rt->lsa.sn + 1;
- }
- body = originate_rt_lsa_body(oa, &lsa.length);
- lsasum_calculate(&lsa, body);
- en = lsa_install_new(&lsa, body, oa);
- oa->rt = en;
- ospf_lsupd_flood(NULL, NULL, &oa->rt->lsa, NULL, oa, 1);
schedule_rtcalc(po);
oa->origrt = 0;
}
static void *
-originate_net_lsa_body(struct ospf_iface *ifa, u16 * length,
+originate_net_lsa_body(struct ospf_iface *ifa, u16 *length,
struct proto_ospf *po)
{
u16 i = 1;
struct ospf_neighbor *n;
- u32 *body;
struct ospf_lsa_net *net;
+ int nodes = ifa->fadj + 1;
+
+ net = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_net)
+ + nodes * sizeof(u32));
- net = mb_alloc(po->proto.pool, sizeof(u32) * (ifa->fadj + 1) +
- sizeof(struct ospf_lsa_net));
+#ifdef OSPFv2
net->netmask = ipa_mkmask(ifa->iface->addr->pxlen);
+#endif
+
+#ifdef OSPFv3
+ /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
+ struct top_hash_entry *en;
+ u32 options = 0;
+#endif
+
+ net->routers[0] = po->router_id;
- body = (u32 *) (net + 1);
- i = 1;
- *body = po->proto.cf->global->router_id;
WALK_LIST(n, ifa->neigh_list)
{
if (n->state == NEIGHBOR_FULL)
{
- *(body + i) = n->rid;
+#ifdef OSPFv3
+ en = ospf_hash_find(po->gr, ifa->iface->index, n->iface_id, n->rid, LSA_T_LINK);
+ if (en)
+ options |= ((struct ospf_lsa_link *) en->lsa_body)->options;
+#endif
+
+ net->routers[i] = n->rid;
i++;
}
}
- *length = i * sizeof(u32) + sizeof(struct ospf_lsa_header) +
- sizeof(struct ospf_lsa_net);
+ ASSERT(i == nodes);
+
+#ifdef OSPFv3
+ net->options = options & OPTIONS_MASK;
+#endif
+
+ *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_net)
+ + nodes * sizeof(u32);
return net;
}
+
/**
* originate_net_lsa - originates of deletes network LSA
* @ifa: interface which is LSA originated for
@@ -310,12 +531,60 @@ void
originate_net_lsa(struct ospf_iface *ifa)
{
struct proto_ospf *po = ifa->oa->po;
- struct ospf_lsa_header lsa;
- u32 rtid = po->proto.cf->global->router_id;
struct proto *p = &po->proto;
+ struct ospf_lsa_header lsa;
+ u32 dom = ifa->oa->areaid;
+
void *body;
- if (ifa->nlsa && ((ifa->nlsa->inst_t + MINLSINTERVAL) > now))
+ OSPF_TRACE(D_EVENTS, "Originating network-LSA for iface %s",
+ ifa->iface->name);
+
+ lsa.age = 0;
+ lsa.type = LSA_T_NET;
+
+#ifdef OSPFv2
+ lsa.options = ifa->oa->options;
+ lsa.id = ipa_to_u32(ifa->iface->addr->ip);
+#else /* OSPFv3 */
+ lsa.id = ifa->iface->index;
+#endif
+
+ lsa.rt = po->router_id;
+ lsa.sn = ifa->net_lsa ? (ifa->net_lsa->lsa.sn + 1) : LSA_INITSEQNO;
+
+ body = originate_net_lsa_body(ifa, &lsa.length, po);
+ lsasum_calculate(&lsa, body);
+ ifa->net_lsa = lsa_install_new(po, &lsa, dom, body);
+ ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
+}
+
+void
+flush_net_lsa(struct ospf_iface *ifa)
+{
+ struct proto_ospf *po = ifa->oa->po;
+ struct proto *p = &po->proto;
+ u32 dom = ifa->oa->areaid;
+
+ if (ifa->net_lsa == NULL)
+ return;
+
+ OSPF_TRACE(D_EVENTS, "Flushing network-LSA for iface %s",
+ ifa->iface->name);
+ ifa->net_lsa->lsa.sn += 1;
+ ifa->net_lsa->lsa.age = LSA_MAXAGE;
+ lsasum_calculate(&ifa->net_lsa->lsa, ifa->net_lsa->lsa_body);
+ ospf_lsupd_flood(po, NULL, NULL, &ifa->net_lsa->lsa, dom, 0);
+ flush_lsa(ifa->net_lsa, po);
+ ifa->net_lsa = NULL;
+}
+
+void
+update_net_lsa(struct ospf_iface *ifa)
+{
+ struct proto_ospf *po = ifa->oa->po;
+
+ if (ifa->net_lsa && ((ifa->net_lsa->inst_t + MINLSINTERVAL) > now))
return;
/*
* It's too early to originate new network LSA. We will
@@ -323,233 +592,241 @@ originate_net_lsa(struct ospf_iface *ifa)
*/
if ((ifa->state != OSPF_IS_DR) || (ifa->fadj == 0))
- {
- if (ifa->nlsa == NULL)
- return;
+ {
+ flush_net_lsa(ifa);
+#ifdef OSPFv3
+ flush_prefix_net_lsa(ifa);
+#endif
+ }
+ else
+ {
+ originate_net_lsa(ifa);
+#ifdef OSPFv3
+ originate_prefix_net_lsa(ifa);
+#endif
+ }
- OSPF_TRACE(D_EVENTS, "Deleting Net lsa for iface \"%s\".",
- ifa->iface->name);
- ifa->nlsa->lsa.sn += 1;
- ifa->nlsa->lsa.age = LSA_MAXAGE;
- lsasum_calculate(&ifa->nlsa->lsa, ifa->nlsa->lsa_body);
- ospf_lsupd_flood(NULL, NULL, &ifa->nlsa->lsa, NULL, ifa->oa, 0);
- s_rem_node(SNODE ifa->nlsa);
- if (ifa->nlsa->lsa_body != NULL)
- mb_free(ifa->nlsa->lsa_body);
- ifa->nlsa->lsa_body = NULL;
- ospf_hash_delete(po->gr, ifa->nlsa);
- schedule_rtcalc(po);
- ifa->nlsa = NULL;
- return;
- }
+ schedule_rtcalc(po);
+ ifa->orignet = 0;
+}
- OSPF_TRACE(D_EVENTS, "Originating Net lsa for iface \"%s\".",
- ifa->iface->name);
+#ifdef OSPFv2
- lsa.age = 0;
- lsa.id = ipa_to_u32(ifa->iface->addr->ip);
- lsa.type = LSA_T_NET;
- lsa.rt = rtid;
- lsa.options = ifa->oa->opt.byte;
- if (ifa->nlsa == NULL)
- {
- lsa.sn = LSA_INITSEQNO;
- }
- else
- {
- lsa.sn = ifa->nlsa->lsa.sn + 1;
- }
+static inline void *
+originate_sum_lsa_body(struct proto_ospf *po, u16 *length, u32 mlen, u32 metric)
+{
+ struct ospf_lsa_sum *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum));
+ *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum);
- body = originate_net_lsa_body(ifa, &lsa.length, po);
- lsasum_calculate(&lsa, body);
- ifa->nlsa = lsa_install_new(&lsa, body, ifa->oa);
- ospf_lsupd_flood(NULL, NULL, &ifa->nlsa->lsa, NULL, ifa->oa, 1);
- ifa->orignet = 0;
+ sum->netmask = ipa_mkmask(mlen);
+ sum->metric = metric;
+
+ return sum;
}
+#define originate_sum_net_lsa_body(po,length,fn,metric) \
+ originate_sum_lsa_body(po, length, (fn)->pxlen, metric)
-static void *
-originate_ext_lsa_body(net * n, rte * e, struct proto_ospf *po,
- struct ea_list *attrs)
+#define originate_sum_rt_lsa_body(po,length,drid,metric,options) \
+ originate_sum_lsa_body(po, length, 0, metric)
+
+static inline int
+check_sum_net_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
{
- struct proto *p = &po->proto;
- struct ospf_lsa_ext *ext;
- struct ospf_lsa_ext_tos *et;
- u32 m1 = ea_get_int(attrs, EA_OSPF_METRIC1, LSINFINITY);
- u32 m2 = ea_get_int(attrs, EA_OSPF_METRIC2, 10000);
- u32 tag = ea_get_int(attrs, EA_OSPF_TAG, 0);
- int inas = 0;
+ struct ospf_lsa_sum *sum = en->lsa_body;
+ return fn->pxlen != ipa_mklen(sum->netmask);
+}
- ext = mb_alloc(p->pool, sizeof(struct ospf_lsa_ext) +
- sizeof(struct ospf_lsa_ext_tos));
- ext->netmask = ipa_mkmask(n->n.pxlen);
+static inline int
+check_ext_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
+{
+ struct ospf_lsa_ext *ext = en->lsa_body;
+ return fn->pxlen != ipa_mklen(ext->netmask);
+}
- et = (struct ospf_lsa_ext_tos *) (ext + 1);
+#else /* OSPFv3 */
- if (m1 != LSINFINITY)
- {
- et->etm.metric = m1;
- et->etm.etos.tos = 0;
- et->etm.etos.ebit = 0;
- }
- else
- {
- et->etm.metric = m2;
- et->etm.etos.tos = 0;
- et->etm.etos.ebit = 1;
- }
- et->tag = tag;
- if (!ipa_equal(e->attrs->gw, IPA_NONE))
- {
- if (ospf_iface_find((struct proto_ospf *) p, e->attrs->iface) != NULL)
- inas = 1;
- }
+static inline void *
+originate_sum_net_lsa_body(struct proto_ospf *po, u16 *length, struct fib_node *fn, u32 metric)
+{
+ int size = sizeof(struct ospf_lsa_sum_net) + IPV6_PREFIX_SPACE(fn->pxlen);
+ struct ospf_lsa_sum_net *sum = mb_alloc(po->proto.pool, size);
+ *length = sizeof(struct ospf_lsa_header) + size;
- if (!inas)
- et->fwaddr = IPA_NONE;
- else
- et->fwaddr = e->attrs->gw;
- return ext;
+ sum->metric = metric;
+ put_ipv6_prefix(sum->prefix, fn->prefix, fn->pxlen, 0, 0);
+
+ return sum;
}
-/**
- * max_ext_lsa - calculate the maximum amount of external networks
- * possible for the given prefix length.
- * @pxlen: network prefix length
- *
- * This is a fix for the previous static use of MAXNETS which did
- * only work correct if MAXNETS < possible IPs for given prefix.
- * This solution is kind of a hack as there can now only be one
- * route for /32 type entries but this is better than the crashes
- * I did experience whith close together /32 routes originating
- * on different hosts.
- */
+static inline int
+check_sum_net_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
+{
+ struct ospf_lsa_sum_net *sum = en->lsa_body;
+ ip_addr prefix;
+ int pxlen;
+ u8 pxopts;
+ u16 rest;
+
+ lsa_get_ipv6_prefix(sum->prefix, &prefix, &pxlen, &pxopts, &rest);
+ return (fn->pxlen != pxlen) || !ipa_equal(fn->prefix, prefix);
+}
-int
-max_ext_lsa(unsigned pxlen)
+static inline int
+check_ext_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
{
- int i;
- for (i = 1; pxlen < BITS_PER_IP_ADDRESS; pxlen++, i <<= 1)
- if (i >= MAXNETS)
- return MAXNETS;
- return i;
+ struct ospf_lsa_ext *ext = en->lsa_body;
+ ip_addr prefix;
+ int pxlen;
+ u8 pxopts;
+ u16 rest;
+
+ lsa_get_ipv6_prefix(ext->rest, &prefix, &pxlen, &pxopts, &rest);
+ return (fn->pxlen != pxlen) || !ipa_equal(fn->prefix, prefix);
}
+static inline void *
+originate_sum_rt_lsa_body(struct proto_ospf *po, u16 *length, u32 drid, u32 metric, u32 options)
+{
+ struct ospf_lsa_sum_rt *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum_rt));
+ *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum_rt);
+
+ sum->options = options & OPTIONS_MASK;
+ sum->metric = metric;
+ sum->drid = drid;
+
+ return sum;
+}
+
+#endif
+
void
-flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type)
+originate_sum_net_lsa(struct ospf_area *oa, struct fib_node *fn, int metric)
{
struct proto_ospf *po = oa->po;
struct proto *p = &po->proto;
struct top_hash_entry *en;
- u32 rtid = po->proto.cf->global->router_id;
+ u32 dom = oa->areaid;
struct ospf_lsa_header lsa;
- int max, i;
- struct ospf_lsa_sum *sum = NULL;
+ void *body;
- lsa.rt = rtid;
- lsa.type = LSA_T_SUM_NET;
- if (type == ORT_ROUTER)
- lsa.type = LSA_T_SUM_RT;
+ OSPF_TRACE(D_EVENTS, "Originating net-summary-LSA for %I/%d (metric %d)",
+ fn->prefix, fn->pxlen, metric);
- max = max_ext_lsa(fn->pxlen);
+ /* 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;
+ lsa.sn = LSA_INITSEQNO;
- for (i = 0; i < max; i++)
+ if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
{
- lsa.id = ipa_to_u32(fn->prefix) + i;
- if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) != NULL)
- {
- sum = en->lsa_body;
- if ((type == ORT_ROUTER) || (fn->pxlen == ipa_mklen(sum->netmask)))
+ if (check_sum_net_lsaid_collision(fn, en))
{
- en->lsa.age = LSA_MAXAGE;
- en->lsa.sn = LSA_MAXSEQNO;
- lsasum_calculate(&en->lsa, sum);
- OSPF_TRACE(D_EVENTS, "Flushing summary lsa. (id=%R, type=%d)",
- en->lsa.id, en->lsa.type);
- ospf_lsupd_flood(NULL, NULL, &en->lsa, NULL, oa, 1);
- if (can_flush_lsa(po)) flush_lsa(en, po);
- break;
+ log(L_ERR, "%s: LSAID collision for %I/%d",
+ p->name, fn->prefix, fn->pxlen);
+ return;
}
- }
+
+ lsa.sn = en->lsa.sn + 1;
}
+
+ body = originate_sum_net_lsa_body(po, &lsa.length, fn, metric);
+ lsasum_calculate(&lsa, body);
+ en = lsa_install_new(po, &lsa, dom, body);
+ ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
}
void
-originate_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type, int metric)
+originate_sum_rt_lsa(struct ospf_area *oa, struct fib_node *fn, int metric, u32 options)
{
struct proto_ospf *po = oa->po;
struct proto *p = &po->proto;
struct top_hash_entry *en;
- u32 rtid = po->proto.cf->global->router_id;
+ u32 dom = oa->areaid;
struct ospf_lsa_header lsa;
- int i, max, mlen = fn->pxlen, free = 0;
- u32 freeid = 0xFFFF;
- struct ospf_lsa_sum *sum = NULL;
- union ospf_lsa_sum_tm *tm;
- lsa.type = LSA_T_SUM_NET;
+ void *body;
- if (type == ORT_ROUTER)
- {
- lsa.type = LSA_T_SUM_RT;
- mlen = 0;
- }
+ OSPF_TRACE(D_EVENTS, "Originating rt-summary-LSA for %R (metric %d)",
+ lsa.id, metric);
lsa.age = 0;
- lsa.rt = rtid;
+#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 = ipa_to_rid(fn->prefix);
+ lsa.rt = po->router_id;
lsa.sn = LSA_INITSEQNO;
- lsa.length = sizeof(struct ospf_lsa_sum) + sizeof(union ospf_lsa_sum_tm) +
- sizeof(struct ospf_lsa_header);
- lsa.options = oa->opt.byte;
- max = max_ext_lsa(fn->pxlen);
- for (i = 0; i < max; i++)
- {
- lsa.id = ipa_to_u32(fn->prefix) + i;
- if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) == NULL)
+ if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
+ lsa.sn = en->lsa.sn + 1;
+
+ body = originate_sum_rt_lsa_body(po, &lsa.length, lsa.id, metric, options);
+ lsasum_calculate(&lsa, body);
+ en = lsa_install_new(po, &lsa, dom, body);
+ ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
+}
+
+
+void
+originate_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type, int metric, u32 options)
+{
+ if (type == ORT_NET)
+ originate_sum_net_lsa(oa, fn, metric);
+ else
+ originate_sum_rt_lsa(oa, fn, metric, options);
+}
+
+
+void
+flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type)
+{
+ struct proto_ospf *po = oa->po;
+ struct proto *p = &po->proto;
+ struct top_hash_entry *en;
+ struct ospf_lsa_header lsa;
+
+ lsa.rt = po->router_id;
+ if (type == ORT_NET)
{
- if (!free)
- {
- freeid = lsa.id;
- free = 1;
- }
+ lsa.id = fibnode_to_lsaid(po, fn);
+ lsa.type = LSA_T_SUM_NET;
}
- else
+ else
{
- sum = en->lsa_body;
- if (mlen == ipa_mklen(sum->netmask))
- {
- tm = (union ospf_lsa_sum_tm *) (sum + 1);
- if (tm->metric == (unsigned) metric) return; /* No reason for origination */
- lsa.sn = en->lsa.sn + 1;
- freeid = en->lsa.id;
- free = 1;
- break;
- }
+ /* 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;
}
- }
- if(!free)
- {
- log("%s: got more routes for one /%d network then %d, ignoring", p->name,
- fn->pxlen, max);
- return;
- }
- lsa.id = freeid;
-
- OSPF_TRACE(D_EVENTS, "Originating summary (type %d) lsa for %I/%d (met %d).", lsa.type, fn->prefix,
- fn->pxlen, metric);
+ if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) != NULL)
+ {
+ if ((type == ORT_NET) && check_sum_net_lsaid_collision(fn, en))
+ {
+ log(L_ERR, "%s: LSAID collision for %I/%d",
+ p->name, fn->prefix, fn->pxlen);
+ return;
+ }
- sum = mb_alloc(p->pool, sizeof(struct ospf_lsa_sum) + sizeof(union ospf_lsa_sum_tm));
- sum->netmask = ipa_mkmask(mlen);
- tm = (union ospf_lsa_sum_tm *) (sum + 1);
- tm->metric = metric;
- tm->tos.tos = 0;
+ struct ospf_lsa_sum *sum = en->lsa_body;
+ en->lsa.age = LSA_MAXAGE;
+ en->lsa.sn = LSA_MAXSEQNO;
+ lsasum_calculate(&en->lsa, sum);
- lsasum_calculate(&lsa, sum);
- en = lsa_install_new(&lsa, sum, oa);
- ospf_lsupd_flood(NULL, NULL, &en->lsa, NULL, oa, 1);
+ OSPF_TRACE(D_EVENTS, "Flushing summary-LSA (id=%R, type=%d)",
+ en->lsa.id, en->lsa.type);
+ ospf_lsupd_flood(po, NULL, NULL, &en->lsa, oa->areaid, 1);
+ if (can_flush_lsa(po)) flush_lsa(en, po);
+ }
}
+
void
check_sum_lsa(struct proto_ospf *po, ort *nf, int dest)
{
@@ -572,7 +849,7 @@ check_sum_lsa(struct proto_ospf *po, ort *nf, int dest)
flush = 0;
if ((nf->n.metric1 >= LSINFINITY) || (nf->n.type > RTS_OSPF_IA))
flush = 1;
- if ((dest == ORT_ROUTER) && (!(nf->n.capa & ORTA_ASBR)))
+ if ((dest == ORT_ROUTER) && (!(nf->n.options & ORTA_ASBR)))
flush = 1;
if ((!nf->n.oa) || (nf->n.oa->areaid == oa->areaid))
flush = 1;
@@ -591,19 +868,81 @@ check_sum_lsa(struct proto_ospf *po, ort *nf, int dest)
mlen = nf->fn.pxlen;
ip = ipa_and(nf->fn.prefix, ipa_mkmask(mlen));
- if ((oa == po->backbone) && (nf->n.type == RTS_OSPF_IA)) flush = 1; /* Only intra-area can go to the backbone */
+ if ((oa == po->backbone) && (nf->n.type == RTS_OSPF_IA))
+ flush = 1; /* Only intra-area can go to the backbone */
- if ((!flush) && (dest == ORT_NET) && fib_route(&nf->n.oa->net_fib, ip, mlen)) /* The route fits into area networks */
+ if ((!flush) && (dest == ORT_NET) && fib_route(&nf->n.oa->net_fib, ip, mlen))
{
+ /* The route fits into area networks */
flush = 1;
if ((nf->n.oa == po->backbone) && (oa->trcap)) flush = 0;
}
- if(flush)
+ if (flush)
flush_sum_lsa(oa, &nf->fn, dest);
else
- originate_sum_lsa(oa, &nf->fn, dest, nf->n.metric1);
+ originate_sum_lsa(oa, &nf->fn, dest, nf->n.metric1, nf->n.options);
+ }
+}
+
+
+static void *
+originate_ext_lsa_body(net *n, rte *e, u16 *length, struct proto_ospf *po,
+ struct ea_list *attrs)
+{
+ struct proto *p = &po->proto;
+ struct ospf_lsa_ext *ext;
+ u32 m1 = ea_get_int(attrs, EA_OSPF_METRIC1, LSINFINITY);
+ u32 m2 = ea_get_int(attrs, EA_OSPF_METRIC2, 10000);
+ u32 tag = ea_get_int(attrs, EA_OSPF_TAG, 0);
+ int gw = 0;
+ int size = sizeof(struct ospf_lsa_ext);
+ u32 *buf;
+
+ if (!ipa_equal(e->attrs->gw, IPA_NONE))
+ {
+ /* FIXME: check for link-local in OSPFv3 ? */
+ if (ospf_iface_find((struct proto_ospf *) p, e->attrs->iface) != NULL)
+ gw = 1;
}
+
+#ifdef OSPFv3
+ size += IPV6_PREFIX_SPACE(n->n.pxlen);
+
+ if (gw)
+ size += 16;
+
+ if (tag)
+ size += 4;
+#endif
+
+ ext = mb_alloc(p->pool, size);
+ *length = sizeof(struct ospf_lsa_header) + size;
+
+ ext->metric = (m1 != LSINFINITY) ? m1 : (m2 | LSA_EXT_EBIT);
+
+#ifdef OSPFv2
+ ext->netmask = ipa_mkmask(n->n.pxlen);
+ ext->fwaddr = gw ? e->attrs->gw : IPA_NONE;
+ ext->tag = tag;
+#else /* OSPFv3 */
+ buf = ext->rest;
+ buf = put_ipv6_prefix(buf, n->n.prefix, n->n.pxlen, 0, 0);
+
+ if (gw)
+ {
+ ext->metric |= LSA_EXT_FBIT;
+ buf = put_ipv6_addr(buf, e->attrs->gw);
+ }
+
+ if (tag)
+ {
+ ext->metric |= LSA_EXT_TBIT;
+ *buf++ = tag;
+ }
+#endif
+
+ return ext;
}
/**
@@ -625,75 +964,399 @@ void
originate_ext_lsa(net * n, rte * e, struct proto_ospf *po,
struct ea_list *attrs)
{
+ struct proto *p = &po->proto;
+ struct fib_node *fn = &n->n;
struct ospf_lsa_header lsa;
- u32 rtid = po->proto.cf->global->router_id;
struct top_hash_entry *en = NULL;
- void *body = NULL;
- struct proto *p = &po->proto;
+ void *body;
struct ospf_area *oa;
- struct ospf_lsa_ext *ext1, *ext2;
- int i, max;
- OSPF_TRACE(D_EVENTS, "Originating Ext lsa for %I/%d.", n->n.prefix,
- n->n.pxlen);
+ OSPF_TRACE(D_EVENTS, "Originating AS-external-LSA for %I/%d",
+ fn->prefix, fn->pxlen);
lsa.age = 0;
- lsa.id = ipa_to_u32(n->n.prefix);
+#ifdef OSPFv2
+ lsa.options = 0; /* or oa->options ? */
+#endif
lsa.type = LSA_T_EXT;
- lsa.rt = rtid;
+ lsa.id = fibnode_to_lsaid(po, fn);
+ lsa.rt = po->router_id;
lsa.sn = LSA_INITSEQNO;
- lsa.options = 0;
- body = originate_ext_lsa_body(n, e, po, attrs);
- lsa.length = sizeof(struct ospf_lsa_ext) + sizeof(struct ospf_lsa_ext_tos) +
- sizeof(struct ospf_lsa_header);
- ext1 = body;
- max = max_ext_lsa(n->n.pxlen);
+ if ((en = ospf_hash_find_header(po->gr, 0, &lsa)) != NULL)
+ {
+ if (check_ext_lsaid_collision(fn, en))
+ {
+ log(L_ERR, "%s: LSAID collision for %I/%d",
+ p->name, fn->prefix, fn->pxlen);
+ return;
+ }
+
+ lsa.sn = en->lsa.sn + 1;
+ }
+
+ body = originate_ext_lsa_body(n, e, &lsa.length, po, attrs);
+ lsasum_calculate(&lsa, body);
- for (i = 0; i < max; i++)
+ en = lsa_install_new(po, &lsa, 0, body);
+ ospf_lsupd_flood(po, NULL, NULL, &lsa, 0, 1);
+
+ if (po->ebit == 0)
{
- if ((en = ospf_hash_find_header(po->gr, 0 , &lsa)) != NULL)
+ po->ebit = 1;
+ WALK_LIST(oa, po->area_list)
{
- ext2 = en->lsa_body;
- if (ipa_compare(ext1->netmask, ext2->netmask) != 0)
- lsa.id++;
- else
- break;
+ schedule_rt_lsa(oa);
}
- else
- break;
}
+}
- if (i == max)
- {
- log("%s: got more routes for one /%d network then %d, ignoring", p->name,
- n->n.pxlen, max);
- mb_free(body);
+void
+flush_ext_lsa(net *n, struct proto_ospf *po)
+{
+ struct proto *p = &po->proto;
+ struct fib_node *fn = &n->n;
+ struct ospf_area *oa;
+ struct top_hash_entry *en;
+
+ OSPF_TRACE(D_EVENTS, "Flushing AS-external-LSA for %I/%d",
+ fn->prefix, fn->pxlen);
+
+ u32 lsaid = fibnode_to_lsaid(po, fn);
+
+ if (en = ospf_hash_find(po->gr, 0, lsaid, po->router_id, LSA_T_EXT))
+ {
+ if (check_ext_lsaid_collision(fn, en))
+ {
+ log(L_ERR, "%s: LSAID collision for %I/%d",
+ p->name, fn->prefix, fn->pxlen);
+ return;
+ }
+
+ ospf_lsupd_flush_nlsa(po, en);
+ }
+}
+
+
+#ifdef OSPFv3
+
+static void *
+originate_link_lsa_body(struct ospf_iface *ifa, u16 *length)
+{
+ struct proto_ospf *po = ifa->oa->po;
+ struct ospf_lsa_link *ll;
+ int i = 0;
+ u8 flags;
+
+ ASSERT(po->lsab_used == 0);
+ ll = lsab_allocz(po, sizeof(struct ospf_lsa_link));
+ ll->options = ifa->oa->options | (ifa->priority << 24);
+ ll->lladdr = ifa->lladdr;
+ ll = NULL; /* buffer might be reallocated later */
+
+ struct ifa *a;
+ WALK_LIST(a, ifa->iface->addrs)
+ {
+ if ((a->flags & IA_SECONDARY) ||
+ (a->scope < SCOPE_SITE))
+ continue;
+
+ flags = (a->pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
+ put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(a->pxlen)),
+ a->ip, a->pxlen, flags, 0);
+ i++;
+ }
+
+ ll = po->lsab;
+ ll->pxcount = i;
+ *length = po->lsab_used + sizeof(struct ospf_lsa_header);
+ return lsab_flush(po);
+}
+
+void
+originate_link_lsa(struct ospf_iface *ifa)
+{
+ struct ospf_lsa_header lsa;
+ struct proto_ospf *po = ifa->oa->po;
+ struct proto *p = &po->proto;
+ void *body;
+
+ /* FIXME check for vlink and skip that? */
+ OSPF_TRACE(D_EVENTS, "Originating link-LSA for iface %s", ifa->iface->name);
+
+ lsa.age = 0;
+ lsa.type = LSA_T_LINK;
+ lsa.id = ifa->iface->index;
+ lsa.rt = po->router_id;
+ lsa.sn = ifa->link_lsa ? (ifa->link_lsa->lsa.sn + 1) : LSA_INITSEQNO;
+ u32 dom = ifa->iface->index;
+
+ body = originate_link_lsa_body(ifa, &lsa.length);
+ lsasum_calculate(&lsa, body);
+ ifa->link_lsa = lsa_install_new(po, &lsa, dom, body);
+ ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
+
+ /* Just to be sure to not forget on our link LSA */
+ if (ifa->state == OSPF_IS_DR)
+ schedule_net_lsa(ifa);
+}
+
+void
+update_link_lsa(struct ospf_iface *ifa)
+{
+ if (ifa->link_lsa && ((ifa->link_lsa->inst_t + MINLSINTERVAL) > now))
return;
+ /*
+ * It's too early to originate new link LSA. We will
+ * try to do it next tick
+ */
+ originate_link_lsa(ifa);
+ ifa->origlink = 0;
+}
+
+static void *
+originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length)
+{
+ struct proto_ospf *po = oa->po;
+ struct ospf_iface *ifa;
+ struct ospf_lsa_prefix *lp;
+ int net_lsa;
+ int i = 0;
+ u8 flags;
+
+ ASSERT(po->lsab_used == 0);
+ lp = lsab_allocz(po, sizeof(struct ospf_lsa_prefix));
+ lp->ref_type = LSA_T_RT;
+ lp->ref_id = 0;
+ lp->ref_rt = po->router_id;
+ lp = NULL; /* buffer might be reallocated later */
+
+ WALK_LIST(ifa, po->iface_list)
+ {
+ if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
+ continue;
+
+ if ((ifa->type == OSPF_IT_BCAST) ||
+ (ifa->type == OSPF_IT_NBMA))
+ net_lsa = bcast_net_active(ifa);
+ else
+ net_lsa = 0;
+
+ struct ifa *a;
+ WALK_LIST(a, ifa->iface->addrs)
+ {
+ if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) ||
+ (a->flags & IA_SECONDARY) ||
+ (a->flags & IA_UNNUMBERED) ||
+ (a->scope <= SCOPE_LINK) ||
+ configured_stubnet(oa, a))
+ continue;
+
+ flags = (a->pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
+ put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(a->pxlen)),
+ a->ip, a->pxlen, flags, ifa->cost);
+ i++;
+ }
}
+
+ /* FIXME Handle vlinks? see RFC5340, page 38 */
+
+ struct ospf_stubnet_config *sn;
+ WALK_LIST(sn, oa->ac->stubnet_list)
+ if (!sn->hidden)
+ {
+ flags = (sn->px.len < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
+ put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(sn->px.len)),
+ sn->px.addr, sn->px.len, flags, sn->cost);
+ i++;
+ }
+
+ lp = po->lsab;
+ lp->pxcount = i;
+ *length = po->lsab_used + sizeof(struct ospf_lsa_header);
+ return lsab_flush(po);
+}
+
+void
+originate_prefix_rt_lsa(struct ospf_area *oa)
+{
+ struct proto_ospf *po = oa->po;
+ struct proto *p = &po->proto;
+ struct ospf_lsa_header lsa;
+ void *body;
+
+ 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;
+ lsa.sn = oa->pxr_lsa ? (oa->pxr_lsa->lsa.sn + 1) : LSA_INITSEQNO;
+ u32 dom = oa->areaid;
+
+ body = originate_prefix_rt_lsa_body(oa, &lsa.length);
lsasum_calculate(&lsa, body);
- WALK_LIST(oa, po->area_list)
- {
- if (!oa->stub)
+ oa->pxr_lsa = lsa_install_new(po, &lsa, dom, body);
+ ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
+}
+
+
+static inline int
+prefix_space(u32 *buf)
+{
+ int pxl = *buf >> 24;
+ return IPV6_PREFIX_SPACE(pxl);
+}
+
+static inline int
+prefix_same(u32 *b1, u32 *b2)
+{
+ int pxl1 = *b1 >> 24;
+ int pxl2 = *b2 >> 24;
+ int pxs, i;
+
+ if (pxl1 != pxl2)
+ return 0;
+
+ pxs = IPV6_PREFIX_WORDS(pxl1);
+ for (i = 1; i < pxs; i++)
+ if (b1[i] != b2[i])
+ return 0;
+
+ return 1;
+}
+
+static inline u32 *
+prefix_advance(u32 *buf)
+{
+ int pxl = *buf >> 24;
+ return buf + IPV6_PREFIX_WORDS(pxl);
+}
+
+static void
+add_prefix(struct proto_ospf *po, u32 *px, int offset, int *pxc)
+{
+ u32 *pxl = lsab_offset(po, offset);
+ int i;
+ for (i = 0; i < *pxc; i++)
{
- en = lsa_install_new(&lsa, body, oa);
- ospf_lsupd_flood(NULL, NULL, &en->lsa, NULL, oa, 1);
- body = originate_ext_lsa_body(n, e, po, attrs);
+ if (prefix_same(px, pxl))
+ {
+ /* Options should be logically OR'ed together */
+ *pxl |= *px;
+ return;
+ }
+ pxl = prefix_advance(pxl);
}
- }
- mb_free(body);
- if (po->ebit == 0)
- {
- po->ebit = 1;
- WALK_LIST(oa, po->area_list)
+ ASSERT(pxl == lsab_end(po));
+
+ int pxspace = prefix_space(px);
+ pxl = lsab_alloc(po, pxspace);
+ memcpy(pxl, px, pxspace);
+ (*pxc)++;
+}
+
+static void
+add_link_lsa(struct proto_ospf *po, struct top_hash_entry *en, int offset, int *pxc)
+{
+ struct ospf_lsa_link *ll = en->lsa_body;
+ u32 *pxb = ll->rest;
+ int j;
+
+ for (j = 0; j < ll->pxcount; j++)
{
- schedule_rt_lsa(oa);
+ add_prefix(po, pxb, offset, pxc);
+ pxb = prefix_advance(pxb);
}
- }
}
+
+static void *
+originate_prefix_net_lsa_body(struct ospf_iface *ifa, u16 *length)
+{
+ struct proto_ospf *po = ifa->oa->po;
+ struct ospf_lsa_prefix *lp;
+ struct ospf_neighbor *n;
+ struct top_hash_entry *en;
+ int pxc, offset;
+
+ ASSERT(po->lsab_used == 0);
+ lp = lsab_allocz(po, sizeof(struct ospf_lsa_prefix));
+ lp->ref_type = LSA_T_NET;
+ lp->ref_id = ifa->net_lsa->lsa.id;
+ lp->ref_rt = po->router_id;
+ lp = NULL; /* buffer might be reallocated later */
+
+ pxc = 0;
+ offset = po->lsab_used;
+
+ /* Find all Link LSAs associated with the link and merge their prefixes */
+ if (ifa->link_lsa)
+ add_link_lsa(po, ifa->link_lsa, offset, &pxc);
+
+ WALK_LIST(n, ifa->neigh_list)
+ if ((n->state == NEIGHBOR_FULL) &&
+ (en = ospf_hash_find(po->gr, ifa->iface->index, n->iface_id, n->rid, LSA_T_LINK)))
+ add_link_lsa(po, en, offset, &pxc);
+
+ lp = po->lsab;
+ lp->pxcount = pxc;
+ *length = po->lsab_used + sizeof(struct ospf_lsa_header);
+ return lsab_flush(po);
+}
+
+void
+originate_prefix_net_lsa(struct ospf_iface *ifa)
+{
+ struct proto_ospf *po = ifa->oa->po;
+ struct proto *p = &po->proto;
+ struct ospf_lsa_header lsa;
+ void *body;
+
+ OSPF_TRACE(D_EVENTS, "Originating network prefix-LSA for iface %s",
+ ifa->iface->name);
+
+ lsa.age = 0;
+ lsa.type = LSA_T_PREFIX;
+ lsa.id = ifa->iface->index;
+ lsa.rt = po->router_id;
+ lsa.sn = ifa->pxn_lsa ? (ifa->pxn_lsa->lsa.sn + 1) : LSA_INITSEQNO;
+ u32 dom = ifa->oa->areaid;
+
+ body = originate_prefix_net_lsa_body(ifa, &lsa.length);
+ lsasum_calculate(&lsa, body);
+ ifa->pxn_lsa = lsa_install_new(po, &lsa, dom, body);
+ ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
+}
+
+void
+flush_prefix_net_lsa(struct ospf_iface *ifa)
+{
+ struct proto_ospf *po = ifa->oa->po;
+ struct proto *p = &po->proto;
+ struct top_hash_entry *en = ifa->pxn_lsa;
+ u32 dom = ifa->oa->areaid;
+
+ if (en == NULL)
+ return;
+
+ OSPF_TRACE(D_EVENTS, "Flushing network prefix-LSA for iface %s",
+ ifa->iface->name);
+
+ en->lsa.sn += 1;
+ en->lsa.age = LSA_MAXAGE;
+ lsasum_calculate(&en->lsa, en->lsa_body);
+ ospf_lsupd_flood(po, NULL, NULL, &en->lsa, dom, 0);
+ flush_lsa(en, po);
+ ifa->pxn_lsa = NULL;
+}
+
+
+#endif
+
+
static void
ospf_top_ht_alloc(struct top_graph *f)
{
@@ -730,24 +1393,34 @@ ospf_top_hash_u32(u32 a)
}
static inline unsigned
-ospf_top_hash(struct top_graph *f, u32 areaid, u32 lsaid, u32 rtrid, u32 type)
-{
-#if 1 /* Dirty patch to make rt table calculation work. */
- return (ospf_top_hash_u32(lsaid) +
- ospf_top_hash_u32((type ==
- LSA_T_NET) ? lsaid : rtrid) + type +
- (type == LSA_T_EXT ? 0 : areaid)) & f->hash_mask;
-#else
+ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type)
+{
+ /* In OSPFv2, we don't know Router ID when looking for network LSAs.
+ In OSPFv3, we don't know LSA ID when looking for router LSAs.
+ In both cases, there is (usually) just one (or small number)
+ appropriate LSA, so we just clear unknown part of key. */
+
+ return (
+#ifdef OSPFv2
+ ((type == LSA_T_NET) ? 0 : ospf_top_hash_u32(rtrid)) +
+ ospf_top_hash_u32(lsaid) +
+#else /* OSPFv3 */
+ ospf_top_hash_u32(rtrid) +
+ ((type == LSA_T_RT) ? 0 : ospf_top_hash_u32(lsaid)) +
+#endif
+ type + domain) & f->hash_mask;
+
+ /*
return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
type + areaid) & f->hash_mask;
-#endif
+ */
}
/**
* ospf_top_new - allocated new topology database
- * @p: current instance of OSPF
+ * @p: current instance of ospf
*
- * This dynamically hashed structure is often used for keeping LSAs. Mainly
+ * this dynamically hashed structure is often used for keeping lsas. mainly
* its used in @ospf_area structure.
*/
struct top_graph *
@@ -781,7 +1454,7 @@ ospf_top_rehash(struct top_graph *f, int step)
oldn = f->hash_size;
oldt = f->hash_table;
- DBG("Re-hashing topology hash from order %d to %d\n", f->hash_order,
+ DBG("re-hashing topology hash from order %d to %d\n", f->hash_order,
f->hash_order + step);
f->hash_order += step;
ospf_top_ht_alloc(f);
@@ -793,7 +1466,7 @@ ospf_top_rehash(struct top_graph *f, int step)
while (e)
{
x = e->next;
- n = newt + ospf_top_hash(f, e->oa->areaid, e->lsa.id, e->lsa.rt, e->lsa.type);
+ n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa.type);
e->next = *n;
*n = e;
e = x;
@@ -802,65 +1475,137 @@ ospf_top_rehash(struct top_graph *f, int step)
ospf_top_ht_free(oldt);
}
+#ifdef OSPFv2
+
+u32
+ospf_lsa_domain(u32 type, struct ospf_iface *ifa)
+{
+ return (type == LSA_T_EXT) ? 0 : ifa->oa->areaid;
+}
+
+#else /* OSPFv3 */
+
+u32
+ospf_lsa_domain(u32 type, struct ospf_iface *ifa)
+{
+ switch (type & LSA_SCOPE_MASK)
+ {
+ case LSA_SCOPE_LINK:
+ return ifa->iface->index;
+
+ case LSA_SCOPE_AREA:
+ return ifa->oa->areaid;
+
+ case LSA_SCOPE_AS:
+ default:
+ return 0;
+ }
+}
+
+#endif
+
struct top_hash_entry *
-ospf_hash_find_header(struct top_graph *f, u32 areaid, struct ospf_lsa_header *h)
+ospf_hash_find_header(struct top_graph *f, u32 domain, struct ospf_lsa_header *h)
{
- return ospf_hash_find(f, areaid, h->id, h->rt, h->type);
+ return ospf_hash_find(f, domain, h->id, h->rt, h->type);
}
struct top_hash_entry *
-ospf_hash_get_header(struct top_graph *f, struct ospf_area *oa, struct ospf_lsa_header *h)
+ospf_hash_get_header(struct top_graph *f, u32 domain, struct ospf_lsa_header *h)
{
- return ospf_hash_get(f, oa, h->id, h->rt, h->type);
+ return ospf_hash_get(f, domain, h->id, h->rt, h->type);
}
struct top_hash_entry *
-ospf_hash_find(struct top_graph *f, u32 areaid, u32 lsa, u32 rtr, u32 type)
+ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
{
struct top_hash_entry *e;
+ e = f->hash_table[ospf_top_hash(f, domain, lsa, rtr, type)];
- e = f->hash_table[ospf_top_hash(f, areaid, lsa, rtr, type)];
+ while (e && (e->lsa.id != lsa || e->lsa.type != type || e->lsa.rt != rtr || e->domain != domain))
+ e = e->next;
- /* Dirty patch to make rt table calculation work. */
- if (type == LSA_T_NET)
- {
- while (e && (e->lsa.id != lsa || e->lsa.type != LSA_T_NET || e->oa->areaid != areaid))
- e = e->next;
- }
- else if (type == LSA_T_EXT)
- {
- while (e && (e->lsa.id != lsa || e->lsa.type != type || e->lsa.rt != rtr))
- e = e->next;
- }
- else
- {
- while (e && (e->lsa.id != lsa || e->lsa.type != type || e->lsa.rt != rtr || e->oa->areaid != areaid))
+ return e;
+}
+
+
+#ifdef OSPFv2
+
+/* In OSPFv2, sometimes we don't know Router ID when looking for network LSAs.
+ There should be just one, so we find any match. */
+struct top_hash_entry *
+ospf_hash_find_net(struct top_graph *f, u32 domain, u32 lsa)
+{
+ struct top_hash_entry *e;
+ e = f->hash_table[ospf_top_hash(f, domain, lsa, 0, LSA_T_NET)];
+
+ while (e && (e->lsa.id != lsa || e->lsa.type != LSA_T_NET || e->domain != domain))
+ e = e->next;
+
+ return e;
+}
+
+#endif
+
+
+#ifdef OSPFv3
+
+/* In OSPFv3, usually we don't know LSA ID when looking for router
+ LSAs. We return matching LSA with smallest LSA ID. */
+struct top_hash_entry *
+ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr)
+{
+ struct top_hash_entry *rv = NULL;
+ struct top_hash_entry *e;
+ e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
+
+ while (e)
+ {
+ if (e->lsa.rt == rtr && e->lsa.type == LSA_T_RT && e->domain == domain)
+ if (!rv || e->lsa.id < rv->lsa.id)
+ rv = e;
e = e->next;
- }
+ }
+ return rv;
+}
+
+static inline struct top_hash_entry *
+find_matching_rt(struct top_hash_entry *e, u32 domain, u32 rtr)
+{
+ while (e && (e->lsa.rt != rtr || e->lsa.type != LSA_T_RT || e->domain != domain))
+ e = e->next;
return e;
}
struct top_hash_entry *
-ospf_hash_get(struct top_graph *f, struct ospf_area *oa, u32 lsa, u32 rtr, u32 type)
+ospf_hash_find_rt_first(struct top_graph *f, u32 domain, u32 rtr)
+{
+ struct top_hash_entry *e;
+ e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
+ return find_matching_rt(e, domain, rtr);
+}
+
+struct top_hash_entry *
+ospf_hash_find_rt_next(struct top_hash_entry *e)
+{
+ return find_matching_rt(e->next, e->domain, e->lsa.rt);
+}
+
+#endif
+
+
+struct top_hash_entry *
+ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
{
struct top_hash_entry **ee;
struct top_hash_entry *e;
- u32 nareaid = (type == LSA_T_EXT ? 0 : oa->areaid);
- ee = f->hash_table + ospf_top_hash(f, nareaid, lsa, rtr, type);
+ ee = f->hash_table + ospf_top_hash(f, domain, lsa, rtr, type);
e = *ee;
- if (type == LSA_T_EXT)
- {
- while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type))
- e = e->next;
- }
- else
- {
- while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type || e->oa->areaid != nareaid))
- e = e->next;
- }
+ while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type || e->domain != domain))
+ e = e->next;
if (e)
return e;
@@ -876,7 +1621,7 @@ ospf_hash_get(struct top_graph *f, struct ospf_area *oa, u32 lsa, u32 rtr, u32 t
e->lsa.type = type;
e->lsa_body = NULL;
e->nhi = NULL;
- e->oa = oa;
+ e->domain = domain;
e->next = *ee;
*ee = e;
if (f->hash_entries++ > f->hash_entries_max)
@@ -888,7 +1633,7 @@ void
ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
{
struct top_hash_entry **ee = f->hash_table +
- ospf_top_hash(f, e->oa->areaid, e->lsa.id, e->lsa.rt, e->lsa.type);
+ ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa.type);
while (*ee)
{
@@ -908,6 +1653,7 @@ ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
static void
ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
{
+ /*
struct ospf_lsa_rt *rt = NULL;
struct ospf_lsa_rt_link *rr = NULL;
struct ospf_lsa_net *ln = NULL;
@@ -916,7 +1662,8 @@ ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
- he->lsa.checksum, he->oa ? he->oa->areaid : 0 );
+ he->lsa.checksum, he->domain);
+
switch (he->lsa.type)
{
@@ -924,7 +1671,7 @@ ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
rt = he->lsa_body;
rr = (struct ospf_lsa_rt_link *) (rt + 1);
- for (i = 0; i < rt->links; i++)
+ for (i = 0; i < lsa_rt_items(&he->lsa); i++)
OSPF_TRACE(D_EVENTS, " - %1x %-1R %-1R %5u",
rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
break;
@@ -932,16 +1679,15 @@ ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
case LSA_T_NET:
ln = he->lsa_body;
rts = (u32 *) (ln + 1);
- max = (he->lsa.length - sizeof(struct ospf_lsa_header) -
- sizeof(struct ospf_lsa_net)) / sizeof(u32);
- for (i = 0; i < max; i++)
+ for (i = 0; i < lsa_net_items(&he->lsa); i++)
OSPF_TRACE(D_EVENTS, " - %-1R", rts[i]);
break;
default:
break;
}
+ */
}
void