From 91e6a0e5ca973c7183f638987b67aa370e9b484c Mon Sep 17 00:00:00 2001 From: Dinesh Dutt Date: Tue, 4 Dec 2012 10:46:37 -0800 Subject: ospf: Convert MAX_AGE LSA list to tree Store the MaxAge LSA list in a tree instead of a linked list for efficient access. Walking the list can be quite inefficient in some large systems and under certain tests. ospfd maintains the list of LSA's that have been MaxAge'd out in a separate linked list for removal by a remover/walker thread. When a new LSA is to be installed, the old LSA is ejected and when it is ejected, the MaxAge LSA list is traversed to ensure that the old LSA is also removed from this list if it exists on this list. When a large number (> 5K) MaxAge LSAs are bombarding the system, walking this list takes a significant time causing timers to fire and actions to be taken such as expiring neighbors due to expiry of DeadInterval (especially when timer is really low, <= 12s), creating a spiral of instability. By making this MaxAge LSA list be a tree, this problem is mitigated. Signed-off-by: Dinesh Dutt Reviewed-by: Ayan Banerjee Reviewed-by: Scott Feldman Reviewed-by: Shrijeet Mukherjee Signed-off-by: Scott Feldman --- ospfd/ospf_lsa.c | 52 +++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 43 insertions(+), 9 deletions(-) (limited to 'ospfd/ospf_lsa.c') diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c index e778251c..66c7e1c0 100644 --- a/ospfd/ospf_lsa.c +++ b/ospfd/ospf_lsa.c @@ -2828,7 +2828,7 @@ ospf_maxage_lsa_remover (struct thread *thread) { struct ospf *ospf = THREAD_ARG (thread); struct ospf_lsa *lsa; - struct listnode *node, *nnode; + struct route_node *rn; int reschedule = 0; ospf->t_maxage = NULL; @@ -2839,8 +2839,13 @@ ospf_maxage_lsa_remover (struct thread *thread) reschedule = !ospf_check_nbr_status (ospf); if (!reschedule) - for (ALL_LIST_ELEMENTS (ospf->maxage_lsa, node, nnode, lsa)) + for (rn = route_top(ospf->maxage_lsa); rn; rn = route_next(rn)) { + if ((lsa = rn->info) == NULL) + { + continue; + } + if (lsa->retransmit_counter > 0) { reschedule = 1; @@ -2893,13 +2898,22 @@ ospf_maxage_lsa_remover (struct thread *thread) void ospf_lsa_maxage_delete (struct ospf *ospf, struct ospf_lsa *lsa) { - struct listnode *n; + struct route_node *rn; + struct prefix_ls lsa_prefix; - if ((n = listnode_lookup (ospf->maxage_lsa, lsa))) + ls_prefix_set (&lsa_prefix, lsa); + + if ((rn = route_node_lookup(ospf->maxage_lsa, + (struct prefix *)&lsa_prefix))) { - list_delete_node (ospf->maxage_lsa, n); - UNSET_FLAG(lsa->flags, OSPF_LSA_IN_MAXAGE); - ospf_lsa_unlock (&lsa); /* maxage_lsa */ + if (rn->info == lsa) + { + UNSET_FLAG(lsa->flags, OSPF_LSA_IN_MAXAGE); + ospf_lsa_unlock (&lsa); /* maxage_lsa */ + rn->info = NULL; + route_unlock_node (rn); /* route_node_lookup */ + } + route_unlock_node (rn); /* route_node_lookup */ } } @@ -2911,6 +2925,9 @@ ospf_lsa_maxage_delete (struct ospf *ospf, struct ospf_lsa *lsa) void ospf_lsa_maxage (struct ospf *ospf, struct ospf_lsa *lsa) { + struct prefix_ls lsa_prefix; + struct route_node *rn; + /* When we saw a MaxAge LSA flooded to us, we put it on the list and schedule the MaxAge LSA remover. */ if (CHECK_FLAG(lsa->flags, OSPF_LSA_IN_MAXAGE)) @@ -2921,8 +2938,25 @@ ospf_lsa_maxage (struct ospf *ospf, struct ospf_lsa *lsa) return; } - listnode_add (ospf->maxage_lsa, ospf_lsa_lock (lsa)); - SET_FLAG(lsa->flags, OSPF_LSA_IN_MAXAGE); + ls_prefix_set (&lsa_prefix, lsa); + if ((rn = route_node_get (ospf->maxage_lsa, + (struct prefix *)&lsa_prefix)) != NULL) + { + if (rn->info != NULL) + { + route_unlock_node (rn); + } + else + { + rn->info = ospf_lsa_lock(lsa); + SET_FLAG(lsa->flags, OSPF_LSA_IN_MAXAGE); + } + } + else + { + zlog_err("Unable to allocate memory for maxage lsa\n"); + assert(0); + } if (IS_DEBUG_OSPF (lsa, LSA_FLOODING)) zlog_debug ("LSA[%s]: MaxAge LSA remover scheduled.", dump_lsa_key (lsa)); -- cgit v1.2.3 From 2345a2221aa0a02b96846beab6088815f41e791b Mon Sep 17 00:00:00 2001 From: Leonard Tracy Date: Tue, 4 Dec 2012 11:02:35 -0800 Subject: ospf: Fix type-4 network mask to 0 per RFC The OSPF RFC (2328) states that the network mask field of a type 4 LSA "is not meaningful and must be zero". OSPFD has been setting the mask as /32. This patch changes OSPFD to set the mask to 0 per the RFC Signed-off-by: Scott Feldman --- ospfd/ospf_lsa.c | 6 +----- 1 file changed, 1 insertion(+), 5 deletions(-) (limited to 'ospfd/ospf_lsa.c') diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c index 66c7e1c0..fb55f7ff 100644 --- a/ospfd/ospf_lsa.c +++ b/ospfd/ospf_lsa.c @@ -1340,12 +1340,8 @@ static void ospf_summary_asbr_lsa_body_set (struct stream *s, struct prefix *p, u_int32_t metric) { - struct in_addr mask; - - masklen2ip (p->prefixlen, &mask); - /* Put Network Mask. */ - stream_put_ipv4 (s, mask.s_addr); + stream_put_ipv4 (s, (u_int32_t) 0); /* Set # TOS. */ stream_putc (s, (u_char) 0); -- cgit v1.2.3 From 0798cee34f5c436cd2a4b6e1d9a1ca90eee94292 Mon Sep 17 00:00:00 2001 From: Andrew Certain Date: Tue, 4 Dec 2012 13:43:42 -0800 Subject: ospfd: compile warning cleanups A set of patches to clarify some comments as well as cleanup code that was causing warnings. After these patches, the code can be compiled with -Wall -Wsign-compare -Wpointer-arith -Wbad-function-cast -Wwrite-strings -Wmissing-prototypes -Wmissing-declarations -Wchar-subscripts -Wcast-qual -Wextra -Wno-unused-parameter -Wno-missing-field-initializers (what is current in trunk plus -Wextra -Wno-unused-parameter -Wno-missing-field-initializers). Signed-off-by: Scott Feldman --- ospfd/ospf_lsa.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'ospfd/ospf_lsa.c') diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c index fb55f7ff..4f7fb00a 100644 --- a/ospfd/ospf_lsa.c +++ b/ospfd/ospf_lsa.c @@ -2733,7 +2733,9 @@ ospf_lsa_install (struct ospf *ospf, struct ospf_interface *oi, if (IS_LSA_SELF (lsa)) lsa->oi = oi; /* Specify outgoing ospf-interface for this LSA. */ else - ; /* Incoming "oi" for this LSA has set at LSUpd reception. */ + { + /* Incoming "oi" for this LSA has set at LSUpd reception. */ + } /* Fallthrough */ case OSPF_OPAQUE_AREA_LSA: case OSPF_OPAQUE_AS_LSA: -- cgit v1.2.3 From e0630cb4d61557f956318a088f68f1fc4d261ef3 Mon Sep 17 00:00:00 2001 From: Dinesh G Dutt Date: Mon, 7 Jan 2013 10:12:52 -0800 Subject: ospfd: Remove dup MaxAge LSA flood Stop additional, unnecessary flooding of MaxAge LSAs. When a MaxAge LSA is installed, if the LSA is prematurely aged or the LSA is not self-originated, the LSA is flushed. This results in a the LSA being flooded a second time and in some cases flooded back to the receiver (unless the receiver is also the advertising router). A MaxAge'd LSA has already been flooded in ospf_flood() as part of the LSA receive processing (ospf_ls_upd). A self-originated LSA will be flooded from the originate/refresh routine. Thus, in the install routine, a MaxAge'd LSA only needs to be added to the MaxAge LSA list. Signed-off-by: Dinesh G Dutt Signed-off-by: Scott Feldman --- ospfd/ospf_lsa.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'ospfd/ospf_lsa.c') diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c index 4f7fb00a..dfd1a61e 100644 --- a/ospfd/ospf_lsa.c +++ b/ospfd/ospf_lsa.c @@ -2780,15 +2780,14 @@ ospf_lsa_install (struct ospf *ospf, struct ospf_interface *oi, If received LSA' ls_age is MaxAge, or lsa is being prematurely aged (it's getting flushed out of the area), set LSA on MaxAge LSA list. */ - if ((lsa->flags & OSPF_LSA_PREMATURE_AGE) || - (IS_LSA_MAXAGE (new) && !IS_LSA_SELF (new))) + if (IS_LSA_MAXAGE (new)) { if (IS_DEBUG_OSPF (lsa, LSA_INSTALL)) zlog_debug ("LSA[Type%d:%s]: Install LSA 0x%p, MaxAge", new->data->type, inet_ntoa (new->data->id), lsa); - ospf_lsa_flush (ospf, lsa); + ospf_lsa_maxage (ospf, lsa); } return new; -- cgit v1.2.3