Maintain a table of OSPF interface pointers paralell to the router LSA. Use the table in nexthop_calculation to find the right OSPF interface for the nexthop. This has the following advantages: - Possible to have multiple PtP interfaces with the same IP address between two routers. - Possible to use Unnumbered PtP on just one end of the link. - No more seaching for the OSPF interface, hence much faster. --- ospfd/ospf_interface.c | 2 + ospfd/ospf_lsa.c | 91 +++++++++++++++++++++++++++-- ospfd/ospf_lsa.h | 12 ++++ ospfd/ospf_spf.c | 151 +++++++++++++++++++++++++---------------= ------- 4 files changed, 179 insertions(+), 77 deletions(-) diff --git a/ospfd/ospf_interface.c b/ospfd/ospf_interface.c index afe3acf..fc39a81 100644 --- a/ospfd/ospf_interface.c +++ b/ospfd/ospf_interface.c @@ -335,6 +335,8 @@ ospf_if_free (struct ospf_interface *oi) listnode_delete (oi->ospf->oiflist, oi); listnode_delete (oi->area->oiflist, oi); + ospf_oi_seq_if_delete(oi); + memset (oi, 0, sizeof (*oi)); XFREE (MTYPE_OSPF_IF, oi); } diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c index 0ba1834..a12dd7a 100644 --- a/ospfd/ospf_lsa.c +++ b/ospfd/ospf_lsa.c @@ -241,6 +241,27 @@ ospf_lsa_dup (struct ospf_lsa *lsa) return new; } +static void +ospf_lsa_oi_seq_free (struct lsa_oi_seq *oi_seq) +{ + XFREE (MTYPE_OSPF_LSA_DATA, oi_seq->seq_nr); + XFREE (MTYPE_OSPF_LSA_DATA, oi_seq); +} + +void +ospf_oi_seq_if_delete(struct ospf_interface *oi) +{ + int i; + struct ospf_lsa *lsa =3D oi->area->router_lsa_self; + + if (!lsa || !lsa->oi_seq) + return; + /* "delete" all entries of oi */ + for (i=3D0; i < lsa->oi_seq->length/sizeof(seq_nr_t); i++) + if (lsa->oi_seq->seq_nr[i] =3D=3D oi) + lsa->oi_seq->seq_nr[i] =3D NULL; +} + /* Free OSPF LSA. */ void ospf_lsa_free (struct ospf_lsa *lsa) @@ -254,6 +275,8 @@ ospf_lsa_free (struct ospf_lsa *lsa) if (lsa->data !=3D NULL) ospf_lsa_data_free (lsa->data); + if (lsa->oi_seq !=3D NULL) + ospf_lsa_oi_seq_free (lsa->oi_seq); assert (lsa->refresh_list < 0); memset (lsa, 0, sizeof (struct ospf_lsa)); @@ -306,6 +329,24 @@ ospf_lsa_data_new (size_t size) return XCALLOC (MTYPE_OSPF_LSA_DATA, size); } +static struct lsa_oi_seq * +ospf_lsa_oi_seq_new (void) +{ + struct lsa_oi_seq *new; + + new =3D XCALLOC (MTYPE_OSPF_LSA_DATA, sizeof(*new)); + return new; +} + +static seq_nr_t * +ospf_lsa_oi_seq_data_new (size_t size) +{ + seq_nr_t *new; + + new =3D XMALLOC (MTYPE_OSPF_LSA_DATA, size); + return new; +} + /* Duplicate LSA data. */ struct lsa_header * ospf_lsa_data_dup (struct lsa_header *lsah) @@ -318,6 +359,18 @@ ospf_lsa_data_dup (struct lsa_header *lsah) return new; } +static void * +ospf_lsa_oi_seq_dup (struct lsa_oi_seq *oi_seq) +{ + struct lsa_oi_seq *new; + + new =3D ospf_lsa_oi_seq_new (); + new->length =3D oi_seq->length; + new->seq_nr =3D ospf_lsa_oi_seq_data_new (oi_seq->length); + memcpy (new->seq_nr, oi_seq->seq_nr, oi_seq->length); + return new; +} + /* Free LSA data. */ void ospf_lsa_data_free (struct lsa_header *lsah) @@ -653,13 +706,24 @@ lsa_link_ptomp_set (struct stream *s, struct ospf= _interface *oi) return links; } +struct ospf_interface * +router_lsa_to_oi(struct ospf_lsa *lsa, int index) +{ + if (lsa->oi_seq && index >=3D 0) + return lsa->oi_seq->seq_nr[index]; + + zlog_debug ("%s: oi_seq:%p, index:%d!", + __func__, lsa->oi_seq, index); + return NULL; +} /* Set router-LSA link information. */ static int -router_lsa_link_set (struct stream *s, struct ospf_area *area) +router_lsa_link_set (struct stream *s, seq_nr_t oi_list[], + struct ospf_area *area) { struct listnode *node; struct ospf_interface *oi; - int links =3D 0; + int links =3D 0, old_links, i; for (ALL_LIST_ELEMENTS_RO (area->oiflist, node, oi)) { @@ -670,6 +734,7 @@ router_lsa_link_set (struct stream *s, struct ospf_= area *area) { if (oi->state !=3D ISM_Down) { + old_links =3D links; /* Describe each link. */ switch (oi->type) { @@ -691,6 +756,8 @@ router_lsa_link_set (struct stream *s, struct ospf_= area *area) case OSPF_IFTYPE_LOOPBACK: links +=3D lsa_link_loopback_set (s, oi); } + for (i =3D old_links; i < links; i++) + oi_list[i] =3D oi; } } } @@ -699,8 +766,9 @@ router_lsa_link_set (struct stream *s, struct ospf_= area *area) } /* Set router-LSA body. */ -static void -ospf_router_lsa_body_set (struct stream *s, struct ospf_area *area) +static u_int16_t +ospf_router_lsa_body_set (struct stream *s, seq_nr_t oi_list[], + struct ospf_area *area) { unsigned long putp; u_int16_t cnt; @@ -718,10 +786,12 @@ ospf_router_lsa_body_set (struct stream *s, struc= t ospf_area *area) stream_putw(s, 0); /* Set all link information. */ - cnt =3D router_lsa_link_set (s, area); + cnt =3D router_lsa_link_set (s, oi_list, area); /* Set # of links here. */ stream_putw_at (s, putp, cnt); + + return cnt; } static int @@ -790,6 +860,9 @@ ospf_router_lsa_new (struct ospf_area *area) struct lsa_header *lsah; struct ospf_lsa *new; int length; + u_int16_t cnt; + /* oi_list, less than 1KB, allocat on stack */ + seq_nr_t oi_list[((OSPF_MAX_LSA_SIZE*2)/3)/sizeof(seq_nr_t)]; if (IS_DEBUG_OSPF (lsa, LSA_GENERATE)) zlog_debug ("LSA[Type1]: Create router-LSA instance"); @@ -806,7 +879,8 @@ ospf_router_lsa_new (struct ospf_area *area) OSPF_ROUTER_LSA, ospf->router_id, ospf->router_id); /* Set router-LSA body fields. */ - ospf_router_lsa_body_set (s, area); + memset(oi_list, 0, sizeof(oi_list)); + cnt =3D ospf_router_lsa_body_set (s, oi_list, area); /* Set length. */ length =3D stream_get_endp (s); @@ -826,6 +900,11 @@ ospf_router_lsa_new (struct ospf_area *area) /* Copy LSA data to store, discard stream. */ new->data =3D ospf_lsa_data_new (length); memcpy (new->data, lsah, length); + + new->oi_seq =3D ospf_lsa_oi_seq_new (); + new->oi_seq->length =3D cnt*sizeof(seq_nr_t); + new->oi_seq->seq_nr =3D ospf_lsa_oi_seq_data_new (new->oi_seq->lengt= h); + memcpy (new->oi_seq->seq_nr, oi_list, new->oi_seq->length); stream_free (s); return new; diff --git a/ospfd/ospf_lsa.h b/ospfd/ospf_lsa.h index 8dd054c..7bee1dc 100644 --- a/ospfd/ospf_lsa.h +++ b/ospfd/ospf_lsa.h @@ -68,6 +68,13 @@ struct lsa_header u_int16_t length; }; +#define seq_nr_t struct ospf_interface * +/* Router LSA sequnce number list */ +struct lsa_oi_seq { + u_int16_t length; + seq_nr_t *seq_nr; +}; + /* OSPF LSA. */ struct ospf_lsa { @@ -84,6 +91,9 @@ struct ospf_lsa /* LSA data. */ struct lsa_header *data; + /* Router LSA OI sequence number */ + struct lsa_oi_seq *oi_seq; + /* Received time stamp. */ struct timeval tv_recv; @@ -247,10 +257,12 @@ extern void ospf_lsa_free (struct ospf_lsa *); extern struct ospf_lsa *ospf_lsa_lock (struct ospf_lsa *); extern void ospf_lsa_unlock (struct ospf_lsa **); extern void ospf_lsa_discard (struct ospf_lsa *); +extern struct ospf_interface * router_lsa_to_oi(struct ospf_lsa *, int= ); extern struct lsa_header *ospf_lsa_data_new (size_t); extern struct lsa_header *ospf_lsa_data_dup (struct lsa_header *); extern void ospf_lsa_data_free (struct lsa_header *); +extern void ospf_oi_seq_if_delete(struct ospf_interface *); /* Prototype for various LSAs */ extern int ospf_router_lsa_update_timer (struct thread *); diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 610fc9b..07a31c5 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -480,13 +480,16 @@ ospf_spf_add_parent (struct vertex *v, struct ver= tex *w, static unsigned int ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, struct vertex *w, struct router_lsa_link *l,= - unsigned int distance) + unsigned int distance, int lsa_pos) { struct listnode *node, *nnode; struct vertex_nexthop *nh; struct vertex_parent *vp; struct ospf_interface *oi =3D NULL; unsigned int added =3D 0; + char buf1[BUFSIZ]; + char buf2[BUFSIZ]; + if (IS_DEBUG_OSPF_EVENT) { @@ -505,30 +508,41 @@ ospf_nexthop_calculation (struct ospf_area *area,= struct vertex *v, the OSPF interface connecting to the destination network/rout= er. */ + /* we *must* be supplied with the link data */ + assert (l !=3D NULL); + + oi =3D router_lsa_to_oi(area->router_lsa_self, lsa_pos); + if (!oi) + { + zlog_debug("%s: OI not found in LSA: lsa_pos:%d link_id:%s link_dat= a:%s", + __func__, lsa_pos, + inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ), + inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ)); + return 0; + } + if (w->type =3D=3D OSPF_VERTEX_ROUTER) { /* l is a link from v to w * l2 will be link from w to v */ struct router_lsa_link *l2 =3D NULL; - - /* we *must* be supplied with the link data */ - assert (l !=3D NULL); - + if (IS_DEBUG_OSPF_EVENT) { - char buf1[BUFSIZ]; - char buf2[BUFSIZ]; - - zlog_debug("ospf_nexthop_calculation(): considering link= " + zlog_debug("%s: considering link " "type %d link_id %s link_data %s", - l->m[0].type, + __func__, l->m[0].type, inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ)= , inet_ntop (AF_INET, &l->link_data, buf2, BUFSI= Z)); } if (l->m[0].type =3D=3D LSA_LINK_TYPE_POINTOPOINT) { + int nh_found =3D 0; + struct in_addr nexthop; + unsigned long ifindex; + /* If the destination is a router which connects to the calculating router via a Point-to-MultiPoint network, the destination's next hop IP address(es) @@ -548,59 +562,50 @@ ospf_nexthop_calculation (struct ospf_area *area,= struct vertex *v, is a constituent of the PtMP link, and its address is= a nexthop address for V. */ - oi =3D ospf_if_is_configured (area->ospf, &l->link_data)= ; - if (oi && oi->type =3D=3D OSPF_IFTYPE_POINTOMULTIPOINT) - { - struct prefix_ipv4 la; - - la.family =3D AF_INET; - la.prefixlen =3D oi->address->prefixlen; - - /* V links to W on PtMP interface - - find the interface address on W */ - while ((l2 =3D ospf_get_next_link (w, v, l2))) - { - la.prefix =3D l2->link_data; - - if (prefix_cmp ((struct prefix *) &la, - oi->address) =3D=3D 0) - /* link_data is on our PtMP network */ - break; - } - } /* end l is on point-to-multipoint link */ - else - { - /* l is a regular point-to-point link. - Look for a link from W to V. - */ - while ((l2 =3D ospf_get_next_link (w, v, l2))) - { - oi =3D ospf_if_is_configured (area->ospf, - &(l2->link_data)); - - if (oi =3D=3D NULL) - continue; - - if (!IPV4_ADDR_SAME (&oi->address->u.prefix4, - &l->link_data)) - continue; - - break; - } - } - - if (oi && l2) + if (oi->type =3D=3D OSPF_IFTYPE_POINTOPOINT) + { + if (ntohl(l->link_data.s_addr) <=3D 0x00ffffff) + nh_found =3D 1; /* Unnumbered */ + else if (IPV4_ADDR_SAME (&oi->address->u.prefix4, + &l->link_data)) + nh_found =3D 1; + nexthop.s_addr =3D 0; /* Nexthop not required */ + } + else if (oi->type =3D=3D OSPF_IFTYPE_POINTOMULTIPOINT) + { + struct prefix_ipv4 la; + + la.family =3D AF_INET; + la.prefixlen =3D oi->address->prefixlen; + + /* V links to W on PtMP interface + - find the interface address on W */ + while ((l2 =3D ospf_get_next_link (w, v, l2))) + { + la.prefix =3D l2->link_data; + + if (prefix_cmp ((struct prefix *) &la, + oi->address) !=3D 0) + continue; + /* link_data is on our PtMP network */ + nh_found =3D 1; + nexthop =3D l2->link_data; + break; + } + } + + if (nh_found) { /* found all necessary info to build nexthop */ nh =3D vertex_nexthop_new (); nh->oi =3D oi; - nh->router =3D l2->link_data; + nh->router =3D nexthop; ospf_spf_add_parent (v, w, nh, distance); return 1; } else - zlog_info("ospf_nexthop_calculation(): " - "could not determine nexthop for link"); + zlog_info("%s: could not determine nexthop for link", + __func__); } /* end point-to-point link from V to W */ else if (l->m[0].type =3D=3D LSA_LINK_TYPE_VIRTUALLINK) { @@ -633,19 +638,22 @@ ospf_nexthop_calculation (struct ospf_area *area,= struct vertex *v, else { assert(w->type =3D=3D OSPF_VERTEX_NETWORK); - oi =3D ospf_if_is_configured (area->ospf, &(l->link_data)); - if (oi) + if (!IPV4_ADDR_SAME (&oi->address->u.prefix4, + &l->link_data)) { - nh =3D vertex_nexthop_new (); - nh->oi =3D oi; - nh->router.s_addr =3D 0; - ospf_spf_add_parent (v, w, nh, distance); - return 1; - } + zlog_info("%s: Interface %s:%s does not match Link Data:%s", + __func__, oi->ifp->name, + inet_ntop (AF_INET, &oi->address->u.prefix4, buf1, BUFSIZ), + inet_ntop (AF_INET, &l->link_id, buf2, BUFSIZ)); + return 0; + } + + nh =3D vertex_nexthop_new (); + nh->oi =3D oi; + nh->router.s_addr =3D 0; + ospf_spf_add_parent (v, w, nh, distance); + return 1; } - zlog_info("ospf_nexthop_calculation(): " - "Unknown attached link"); - return 0; } /* end V is the root */ /* Check if W's parent is a network connected to root. */ else if (v->type =3D=3D OSPF_VERTEX_NETWORK) @@ -714,7 +722,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *= area, u_char *lim; struct router_lsa_link *l =3D NULL; struct in_addr *r; - int type =3D 0; + int type =3D 0, lsa_pos=3D-1, lsa_pos_next=3D0; /* If this is a router-LSA, and bit V of the router-LSA (see Section= A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. *= / @@ -742,7 +750,8 @@ ospf_spf_next (struct vertex *v, struct ospf_area *= area, if (v->lsa->type =3D=3D OSPF_ROUTER_LSA) { l =3D (struct router_lsa_link *) p; - + lsa_pos =3D lsa_pos_next; /* LSA link position */ + lsa_pos_next++; p +=3D (ROUTER_LSA_MIN_SIZE + (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE)); @@ -864,7 +873,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *= area, w =3D ospf_vertex_new (w_lsa); /* Calculate nexthop to W. */ - if (ospf_nexthop_calculation (area, v, w, l, distance)) + if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_p= os)) pqueue_enqueue (w, candidate); else if (IS_DEBUG_OSPF_EVENT) zlog_debug ("Nexthop Calc failed"); @@ -884,7 +893,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *= area, { /* Found an equal-cost path to W. * Calculate nexthop of to W from V. */ - ospf_nexthop_calculation (area, v, w, l, distance); + ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos); } /* less than. */ else @@ -894,7 +903,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *= area, * valid nexthop it will call spf_add_parents, which * will flush the old parents */ - if (ospf_nexthop_calculation (area, v, w, l, distance)) + if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos)= ) /* Decrease the key of the node in the heap. * trickle-sort it up towards root, just in case this * node should now be the new root due the cost change= . -- 1.6.4.4