From c3c0ac8395502d7e84e94e0281cb72fa37a236c4 Mon Sep 17 00:00:00 2001 From: Donald Sharp Date: Tue, 19 May 2015 18:03:39 -0700 Subject: [PATCH] ospf6d: ospfv3-abr-ecmp-support.patch OSPFv3: Add ABR support and make ECMP > 4. Signed-off-by: Dinesh G Dutt Signed-off-by: Pradosh Mohapatra --- lib/bitfield.h | 102 ++++++++++ lib/libospf.h | 1 + lib/zclient.c | 10 +- ospf6d/ospf6_abr.c | 405 +++++++++++++++++++++++++++------------ ospf6d/ospf6_abr.h | 3 +- ospf6d/ospf6_area.c | 108 ++++++++--- ospf6d/ospf6_area.h | 4 +- ospf6d/ospf6_asbr.c | 26 +-- ospf6d/ospf6_flood.c | 3 + ospf6d/ospf6_interface.c | 5 +- ospf6d/ospf6_intra.c | 39 ++-- ospf6d/ospf6_lsdb.c | 35 +++- ospf6d/ospf6_lsdb.h | 4 + ospf6d/ospf6_main.c | 4 + ospf6d/ospf6_route.c | 294 ++++++++++++++++++++++++---- ospf6d/ospf6_route.h | 52 ++++- ospf6d/ospf6_spf.c | 135 ++++++++----- ospf6d/ospf6_spf.h | 6 +- ospf6d/ospf6_top.c | 2 + ospf6d/ospf6_zebra.c | 110 ++++++++--- ospf6d/ospf6_zebra.h | 2 + ospfd/ospf_abr.h | 1 - zebra/rt_netlink.c | 12 +- zebra/zserv.c | 3 + 24 files changed, 1062 insertions(+), 304 deletions(-) create mode 100644 lib/bitfield.h diff --git a/lib/bitfield.h b/lib/bitfield.h new file mode 100644 index 0000000000..b3f40a948b --- /dev/null +++ b/lib/bitfield.h @@ -0,0 +1,102 @@ +/** + * A simple bit array implementation to allocate and free IDs. An example + * of its usage is in allocating link state IDs for OSPFv3 as OSPFv3 has + * removed all address semantics from LS ID. Another usage can be in + * allocating IDs for BGP neighbors (and dynamic update groups) for + * efficient storage of adj-rib-out. + * + * An example: + * #include "bitfield.h" + * + * bitfield_t bitfield; + * + * bf_init(bitfield, 32); + * ... + * bf_assign_index(bitfield, id1); + * bf_assign_index(bitfield, id2); + * ... + * bf_release_index(bitfield, id1); + */ + +#ifndef _BITFIELD_H +#define _BITFIELD_H + +#include +#include +#include + +typedef unsigned int word_t; +#define WORD_MAX 0xFFFFFFFF +#define WORD_SIZE (sizeof(word_t) * 8) + +/** + * The bitfield structure. + * @data: the bits to manage. + * @n: The current word number that is being used. + * @m: total number of words in 'data' + */ +#define bitfield_t struct { word_t *data; size_t n, m; } + +/** + * Initialize the bits. + * @v: an instance of bitfield_t struct. + * @N: number of bits to start with, which equates to how many + * IDs can be allocated. + */ +#define bf_init(v, N) \ + do { \ + (v).n = 0; \ + (v).m = ((N) / WORD_SIZE + 1); \ + (v).data = calloc(1, ((v).m * sizeof(word_t))); \ + } while (0) + +/** + * allocate and assign an id from bitfield v. + */ +#define bf_assign_index(v, id) \ + do { \ + bf_find_bit(v, id); \ + bf_set_bit(v, id); \ + } while (0) + +/** + * return an id to bitfield v + */ +#define bf_release_index(v, id) \ + (v).data[bf_index(id)] &= ~(1 << (bf_offset(id))) + +#define bf_index(b) ((b) / WORD_SIZE) +#define bf_offset(b) ((b) % WORD_SIZE) + +/** + * Set a bit in the array. If it fills up that word and we are + * out of words, extend it by one more word. + */ +#define bf_set_bit(v, b) \ + do { \ + size_t w = bf_index(b); \ + (v).data[w] |= 1 << (bf_offset(b)); \ + (v).n += ((v).data[w] == WORD_MAX); \ + if ((v).n == (v).m) { \ + (v).m = (v).m + 1; \ + (v).data = realloc((v).data, (v).m * sizeof(word_t)); \ + } \ + } while (0) + +/* Find a clear bit in v and assign it to b. */ +#define bf_find_bit(v, b) \ + do { \ + word_t word; \ + unsigned int w, sh; \ + for (w = 0; w <= (v).n; w++) { \ + if ((word = (v).data[w]) != WORD_MAX) break; \ + } \ + (b) = ((word & 0xFFFF) == 0xFFFF) << 4; word >>= (b); \ + sh = ((word & 0xFF) == 0xFF) << 3; word >>= sh; (b) |= sh; \ + sh = ((word & 0xF) == 0xF) << 2; word >>= sh; (b) |= sh; \ + sh = ((word & 0x3) == 0x3) << 1; word >>= sh; (b) |= sh; \ + sh = ((word & 0x1) == 0x1) << 0; word >>= sh; (b) |= sh; \ + (b) += (w * WORD_SIZE); \ + } while (0) + +#endif diff --git a/lib/libospf.h b/lib/libospf.h index 856c76df55..ade774db6d 100644 --- a/lib/libospf.h +++ b/lib/libospf.h @@ -80,6 +80,7 @@ #define OSPF_FAST_HELLO_DEFAULT 0 #define OSPF_AREA_BACKBONE 0x00000000 /* 0.0.0.0 */ +#define OSPF_AREA_RANGE_COST_UNSPEC -1U /* SPF Throttling timer values. */ #define OSPF_SPF_DELAY_DEFAULT 200 diff --git a/lib/zclient.c b/lib/zclient.c index d8ef0e8536..24962bac34 100644 --- a/lib/zclient.c +++ b/lib/zclient.c @@ -584,7 +584,15 @@ zapi_ipv6_route (u_char cmd, struct zclient *zclient, struct prefix_ipv6 *p, /* Nexthop, ifindex, distance and metric information. */ if (CHECK_FLAG (api->message, ZAPI_MESSAGE_NEXTHOP)) { - stream_putc (s, api->nexthop_num + api->ifindex_num); + if (CHECK_FLAG (api->flags, ZEBRA_FLAG_BLACKHOLE)) + { + stream_putc (s, 1); + stream_putc (s, ZEBRA_NEXTHOP_BLACKHOLE); + /* XXX assert(api->nexthop_num == 0); */ + /* XXX assert(api->ifindex_num == 0); */ + } + else + stream_putc (s, api->nexthop_num + api->ifindex_num); for (i = 0; i < api->nexthop_num; i++) { diff --git a/ospf6d/ospf6_abr.c b/ospf6d/ospf6_abr.c index bb79900e5d..f975ce8427 100644 --- a/ospf6d/ospf6_abr.c +++ b/ospf6d/ospf6_abr.c @@ -38,6 +38,7 @@ #include "ospf6_route.h" #include "ospf6_lsdb.h" #include "ospf6_message.h" +#include "ospf6_zebra.h" #include "ospf6_top.h" #include "ospf6_area.h" @@ -67,6 +68,33 @@ ospf6_is_router_abr (struct ospf6 *o) return 0; } +static int +ospf6_abr_nexthops_belong_to_area (struct ospf6_route *route, + struct ospf6_area *area) +{ + struct ospf6_interface *oi; + + oi = ospf6_interface_lookup_by_ifindex (ospf6_route_get_first_nh_index(route)); + if (oi && oi->area && oi->area == area) + return 1; + else + return 0; +} + +static void +ospf6_abr_delete_route (struct ospf6_route *range, struct ospf6_route *summary, + struct ospf6_route_table *summary_table, + struct ospf6_lsa *old) +{ + if (summary) + { + ospf6_route_remove (summary, summary_table); + } + + if (old) + ospf6_lsa_purge (old); +} + void ospf6_abr_enable_area (struct ospf6_area *area) { @@ -139,12 +167,11 @@ ospf6_abr_disable_area (struct ospf6_area *area) } /* RFC 2328 12.4.3. Summary-LSAs */ -void +int ospf6_abr_originate_summary_to_area (struct ospf6_route *route, struct ospf6_area *area) { struct ospf6_lsa *lsa, *old = NULL; - struct ospf6_interface *oi; struct ospf6_route *summary, *range = NULL; struct ospf6_area *route_area; char buffer[OSPF6_MAX_LSASIZE]; @@ -157,6 +184,54 @@ ospf6_abr_originate_summary_to_area (struct ospf6_route *route, char buf[64]; int is_debug = 0; + /* Only destination type network, range or ASBR are considered */ + if (route->type != OSPF6_DEST_TYPE_NETWORK && + route->type != OSPF6_DEST_TYPE_RANGE && + ((route->type != OSPF6_DEST_TYPE_ROUTER) || + !CHECK_FLAG (route->path.router_bits, OSPF6_ROUTER_BIT_E))) + { + if (is_debug) + zlog_debug ("Route type is none of network, range nor ASBR, ignore"); + return 0; + } + + /* AS External routes are never considered */ + if (route->path.type == OSPF6_PATH_TYPE_EXTERNAL1 || + route->path.type == OSPF6_PATH_TYPE_EXTERNAL2) + { + if (is_debug) + zlog_debug ("Path type is external, skip"); + return 0; + } + + /* do not generate if the path's area is the same as target area */ + if (route->path.area_id == area->area_id) + { + if (is_debug) + zlog_debug ("The route is in the area itself, ignore"); + return 0; + } + + /* do not generate if the nexthops belongs to the target area */ + if (ospf6_abr_nexthops_belong_to_area (route, area)) + { + if (is_debug) + zlog_debug ("The route's nexthop is in the same area, ignore"); + return 0; + } + + if (route->type == OSPF6_DEST_TYPE_ROUTER) + { + if (ADV_ROUTER_IN_PREFIX (&route->prefix) == area->ospf6->router_id) + { + inet_ntop (AF_INET, &(ADV_ROUTER_IN_PREFIX (&route->prefix)), buf, + sizeof (buf)); + zlog_debug ("%s: Skipping ASBR announcement for ABR (%s)", __func__, + buf); + return 0; + } + } + if (route->type == OSPF6_DEST_TYPE_ROUTER) { if (IS_OSPF6_DEBUG_ABR || IS_OSPF6_DEBUG_ORIGINATE (INTER_ROUTER)) @@ -192,76 +267,53 @@ ospf6_abr_originate_summary_to_area (struct ospf6_route *route, { if (is_debug) zlog_debug ("The route has just removed, purge previous LSA"); - if (summary) - ospf6_route_remove (summary, summary_table); - if (old) - ospf6_lsa_purge (old); - return; - } - /* Only destination type network, range or ASBR are considered */ - if (route->type != OSPF6_DEST_TYPE_NETWORK && - route->type != OSPF6_DEST_TYPE_RANGE && - (route->type != OSPF6_DEST_TYPE_ROUTER || - ! CHECK_FLAG (route->path.router_bits, OSPF6_ROUTER_BIT_E))) - { - if (is_debug) - zlog_debug ("Route type is none of network, range nor ASBR, withdraw"); - if (summary) - ospf6_route_remove (summary, summary_table); - if (old) - ospf6_lsa_purge (old); - return; - } + if (route->type == OSPF6_DEST_TYPE_RANGE) + { + /* Whether the route have active longer prefix */ + if (! CHECK_FLAG (route->flag, OSPF6_ROUTE_ACTIVE_SUMMARY)) + { + if (is_debug) + zlog_debug ("The range is not active. withdraw"); + + ospf6_abr_delete_route (route, summary, summary_table, old); + } + } + else + if (old) + ospf6_lsa_purge (old); - /* AS External routes are never considered */ - if (route->path.type == OSPF6_PATH_TYPE_EXTERNAL1 || - route->path.type == OSPF6_PATH_TYPE_EXTERNAL2) - { - if (is_debug) - zlog_debug ("Path type is external, withdraw"); - if (summary) - ospf6_route_remove (summary, summary_table); - if (old) - ospf6_lsa_purge (old); - return; + return 0; } - /* do not generate if the path's area is the same as target area */ - if (route->path.area_id == area->area_id) + if ((route->type == OSPF6_DEST_TYPE_ROUTER) && IS_AREA_STUB(area)) { if (is_debug) - zlog_debug ("The route is in the area itself, ignore"); - if (summary) - ospf6_route_remove (summary, summary_table); - if (old) - ospf6_lsa_purge (old); - return; - } + zlog_debug ("Area has been stubbed, purge Inter-Router LSA"); - /* do not generate if the nexthops belongs to the target area */ - oi = ospf6_interface_lookup_by_ifindex (route->nexthop[0].ifindex); - if (oi && oi->area && oi->area == area) - { - if (is_debug) - zlog_debug ("The route's nexthop is in the same area, ignore"); - if (summary) - ospf6_route_remove (summary, summary_table); - if (old) - ospf6_lsa_purge (old); - return; + ospf6_abr_delete_route (route, summary, summary_table, old); + return 0; } /* do not generate if the route cost is greater or equal to LSInfinity */ if (route->path.cost >= OSPF_LS_INFINITY) { - if (is_debug) - zlog_debug ("The cost exceeds LSInfinity, withdraw"); - if (summary) - ospf6_route_remove (summary, summary_table); - if (old) - ospf6_lsa_purge (old); - return; + /* When we're clearing the range route because all active prefixes + * under the range are gone, we set the range's cost to + * OSPF_AREA_RANGE_COST_UNSPEC, which is > OSPF_LS_INFINITY. We + * don't want to trigger the code here for that. This code is for + * handling routes that have gone to infinity. The range removal happens + * elsewhere. + */ + if ((route->type != OSPF6_DEST_TYPE_RANGE) && + (route->path.cost != OSPF_AREA_RANGE_COST_UNSPEC)) + { + if (is_debug) + zlog_debug ("The cost exceeds LSInfinity, withdraw"); + if (old) + ospf6_lsa_purge (old); + return 0; + } } /* if this is a route to ASBR */ @@ -272,11 +324,8 @@ ospf6_abr_originate_summary_to_area (struct ospf6_route *route, { if (is_debug) zlog_debug ("This is the secondary path to the ASBR, ignore"); - if (summary) - ospf6_route_remove (summary, summary_table); - if (old) - ospf6_lsa_purge (old); - return; + ospf6_abr_delete_route (route, summary, summary_table, old); + return 0; } /* Do not generate if the area is stub */ @@ -305,12 +354,8 @@ ospf6_abr_originate_summary_to_area (struct ospf6_route *route, zlog_debug ("Suppressed by range %s of area %s", buf, route_area->name); } - - if (summary) - ospf6_route_remove (summary, summary_table); - if (old) - ospf6_lsa_purge (old); - return; + ospf6_abr_delete_route (route, summary, summary_table, old); + return 0; } } @@ -322,23 +367,17 @@ ospf6_abr_originate_summary_to_area (struct ospf6_route *route, { if (is_debug) zlog_debug ("This is the range with DoNotAdvertise set. ignore"); - if (summary) - ospf6_route_remove (summary, summary_table); - if (old) - ospf6_lsa_purge (old); - return; + ospf6_abr_delete_route (route, summary, summary_table, old); + return 0; } - /* Whether the route have active longer prefix */ + /* If there are no active prefixes in this range, remove */ if (! CHECK_FLAG (route->flag, OSPF6_ROUTE_ACTIVE_SUMMARY)) { if (is_debug) zlog_debug ("The range is not active. withdraw"); - if (summary) - ospf6_route_remove (summary, summary_table); - if (old) - ospf6_lsa_purge (old); - return; + ospf6_abr_delete_route (route, summary, summary_table, old); + return 0; } } @@ -359,7 +398,7 @@ ospf6_abr_originate_summary_to_area (struct ospf6_route *route, buf, sizeof(buf)); zlog_debug ("prefix %s was denied by export list", buf); } - return; + return 0; } } @@ -380,7 +419,7 @@ ospf6_abr_originate_summary_to_area (struct ospf6_route *route, buf, sizeof (buf)); zlog_debug ("prefix %s was denied by filter-list out", buf); } - return; + return 0; } } @@ -388,16 +427,25 @@ ospf6_abr_originate_summary_to_area (struct ospf6_route *route, if (summary == NULL) { summary = ospf6_route_copy (route); - if (route->type == OSPF6_DEST_TYPE_NETWORK || - route->type == OSPF6_DEST_TYPE_RANGE) - summary->path.origin.type = htons (OSPF6_LSTYPE_INTER_PREFIX); - else - summary->path.origin.type = htons (OSPF6_LSTYPE_INTER_ROUTER); summary->path.origin.adv_router = area->ospf6->router_id; - summary->path.origin.id = - ospf6_new_ls_id (summary->path.origin.type, - summary->path.origin.adv_router, area->lsdb); + + if (route->type == OSPF6_DEST_TYPE_ROUTER) + { + summary->path.origin.type = htons (OSPF6_LSTYPE_INTER_ROUTER); + summary->path.origin.id = ADV_ROUTER_IN_PREFIX (&route->prefix); + } + else + { + summary->path.origin.type = htons (OSPF6_LSTYPE_INTER_PREFIX); + if (route->type == OSPF6_DEST_TYPE_RANGE) + summary->path.origin.id = route->linkstate_id; + else + summary->path.origin.id = + ospf6_new_ls_id (summary->path.origin.type, + summary->path.origin.adv_router, area->lsdb); + } summary = ospf6_route_add (summary, summary_table); + } else { @@ -413,7 +461,7 @@ ospf6_abr_originate_summary_to_area (struct ospf6_route *route, summary->path.area_id = area->area_id; summary->path.type = OSPF6_PATH_TYPE_INTER; summary->path.cost = route->path.cost; - summary->nexthop[0] = route->nexthop[0]; + /* summary->nexthop[0] = route->nexthop[0]; */ /* prepare buffer */ memset (buffer, 0, sizeof (buffer)); @@ -470,35 +518,100 @@ ospf6_abr_originate_summary_to_area (struct ospf6_route *route, /* Originate */ ospf6_lsa_originate_area (lsa, area); + + return 1; } -static void +void ospf6_abr_range_update (struct ospf6_route *range) { u_int32_t cost = 0; struct ospf6_route *ro; + int gen_range_summary = 0; + char buf[INET6_ADDRSTRLEN]; assert (range->type == OSPF6_DEST_TYPE_RANGE); + prefix2str (&range->prefix, buf, sizeof (buf)); - /* update range's cost and active flag */ - for (ro = ospf6_route_match_head (&range->prefix, ospf6->route_table); - ro; ro = ospf6_route_match_next (&range->prefix, ro)) + if (CHECK_FLAG(range->flag, OSPF6_ROUTE_REMOVE)) { - if (ro->path.area_id == range->path.area_id && - ! CHECK_FLAG (ro->flag, OSPF6_ROUTE_REMOVE)) - cost = MAX (cost, ro->path.cost); + UNSET_FLAG (range->flag, OSPF6_ROUTE_ACTIVE_SUMMARY); + gen_range_summary = 1; } - - if (range->path.cost != cost) + else { - range->path.cost = cost; + /* update range's cost and active flag */ + for (ro = ospf6_route_match_head (&range->prefix, ospf6->route_table); + ro; ro = ospf6_route_match_next (&range->prefix, ro)) + { + if (ro->path.area_id == range->path.area_id && + (ro->path.type == OSPF6_PATH_TYPE_INTRA) && + ! CHECK_FLAG (ro->flag, OSPF6_ROUTE_REMOVE)) + cost = MAX (cost, ro->path.cost); + } + } - if (range->path.cost) - SET_FLAG (range->flag, OSPF6_ROUTE_ACTIVE_SUMMARY); + /* Non-zero cost is a proxy for active longer prefixes in this range. + * If there are active routes covered by this range AND either the configured + * cost has changed or the summarized cost has changed then redo summaries. + * Alternately, if there are no longer active prefixes and there are + * summary announcements, withdraw those announcements. + * + * The don't advertise code relies on the path.cost being set to UNSPEC to + * work the first time. Subsequent times the path.cost is not 0 anyway if there + * were active ranges. + */ + if (CHECK_FLAG (range->flag, OSPF6_ROUTE_DO_NOT_ADVERTISE)) + { + if (range->path.cost != 0) + { + range->path.cost = 0; + gen_range_summary = 1; + } + } + else if (cost && + (((range->path.u.cost_config != OSPF_AREA_RANGE_COST_UNSPEC) && + (range->path.cost != range->path.u.cost_config)) || + ((range->path.u.cost_config == OSPF_AREA_RANGE_COST_UNSPEC) && + (range->path.cost != cost)))) + { + if (range->path.u.cost_config == OSPF_AREA_RANGE_COST_UNSPEC) + { + range->path.cost = cost; + } else - UNSET_FLAG (range->flag, OSPF6_ROUTE_ACTIVE_SUMMARY); + { + range->path.cost = range->path.u.cost_config; + } + SET_FLAG (range->flag, OSPF6_ROUTE_ACTIVE_SUMMARY); + gen_range_summary = 1; + } + else if (!cost && CHECK_FLAG (range->flag, OSPF6_ROUTE_ACTIVE_SUMMARY)) + { + UNSET_FLAG (range->flag, OSPF6_ROUTE_ACTIVE_SUMMARY); + range->path.cost = OSPF_AREA_RANGE_COST_UNSPEC; + gen_range_summary = 1; + } + + if (gen_range_summary) + { ospf6_abr_originate_summary (range); + + if (CHECK_FLAG (range->flag, OSPF6_ROUTE_ACTIVE_SUMMARY)) + { + if (IS_OSPF6_DEBUG_ABR) + zlog_debug ("Add discard route"); + + ospf6_zebra_add_discard (range); + } + else + { + if (IS_OSPF6_DEBUG_ABR) + zlog_debug ("Delete discard route"); + + ospf6_zebra_delete_discard (range); + } } } @@ -514,7 +627,9 @@ ospf6_abr_originate_summary (struct ospf6_route *route) oa = ospf6_area_lookup (route->path.area_id, ospf6); range = ospf6_route_lookup_bestmatch (&route->prefix, oa->range_table); if (range) - ospf6_abr_range_update (range); + { + ospf6_abr_range_update (range); + } } for (ALL_LIST_ELEMENTS (ospf6->area_list, node, nnode, oa)) @@ -534,7 +649,6 @@ ospf6_abr_examin_summary (struct ospf6_lsa *lsa, struct ospf6_area *oa) u_int8_t prefix_options = 0; u_int32_t cost = 0; u_char router_bits = 0; - int i; char buf[64]; int is_debug = 0; struct ospf6_inter_prefix_lsa *prefix_lsa = NULL; @@ -575,6 +689,7 @@ ospf6_abr_examin_summary (struct ospf6_lsa *lsa, struct ospf6_area *oa) ospf6_linkstate_prefix (router_lsa->router_id, htonl (0), &prefix); if (is_debug) inet_ntop (AF_INET, &router_lsa->router_id, buf, sizeof (buf)); + table = oa->ospf6->brouter_table; type = OSPF6_DEST_TYPE_ROUTER; options[0] = router_lsa->options[0]; @@ -600,6 +715,8 @@ ospf6_abr_examin_summary (struct ospf6_lsa *lsa, struct ospf6_area *oa) old = route; route = ospf6_route_next (route); } + if (route) + ospf6_route_unlock (route); /* (1) if cost == LSInfinity or if the LSA is MaxAge */ if (cost == OSPF_LS_INFINITY) @@ -666,8 +783,22 @@ ospf6_abr_examin_summary (struct ospf6_lsa *lsa, struct ospf6_area *oa) zlog_debug ("Prefix has NU/LA bit set, ignore"); if (old) ospf6_route_remove (old, table); + return; } + /* Avoid infinite recursion if someone has maliciously announced an + Inter-Router LSA for an ABR + */ + if (lsa->header->adv_router == router_lsa->router_id) + { + if (is_debug) + zlog_debug ("Ignorning Inter-Router LSA for an ABR (%s)", + buf); + if (old) + ospf6_route_remove (old, table); + + return; + } } /* (4) if the routing table entry for the ABR does not exist */ @@ -718,7 +849,7 @@ ospf6_abr_examin_summary (struct ospf6_lsa *lsa, struct ospf6_area *oa) } } - /* (5),(6),(7) the path preference is handled by the sorting + /* (5),(6): the path preference is handled by the sorting in the routing table. Always install the path by substituting old route (if any). */ if (old) @@ -739,12 +870,33 @@ ospf6_abr_examin_summary (struct ospf6_lsa *lsa, struct ospf6_area *oa) route->path.area_id = oa->area_id; route->path.type = OSPF6_PATH_TYPE_INTER; route->path.cost = abr_entry->path.cost + cost; - for (i = 0; i < OSPF6_MULTI_PATH_LIMIT; i++) - route->nexthop[i] = abr_entry->nexthop[i]; - if (is_debug) - zlog_debug ("Install route: %s", buf); - ospf6_route_add (route, table); + ospf6_route_copy_nexthops (route, abr_entry); + + /* (7) If the routes are identical, copy the next hops over to existing + route. ospf6's route table implementation will otherwise string both + routes, but keep the older one as the best route since the routes + are identical. + */ + old = ospf6_route_lookup (&prefix, table); + + if (old && (ospf6_route_cmp (route, old) == 0)) + { + ospf6_route_merge_nexthops (old, route); + /* Update RIB/FIB */ + if (table->hook_add) + (*table->hook_add) (old); + + /* Delete new route */ + ospf6_route_delete (route); + } + else + { + if (is_debug) + zlog_debug ("Install route: %s", buf); + /* ospf6_ia_add_nw_route (table, &prefix, route); */ + ospf6_route_add (route, table); + } } void @@ -752,21 +904,22 @@ ospf6_abr_examin_brouter (u_int32_t router_id) { struct ospf6_lsa *lsa; struct ospf6_area *oa; - struct listnode *node, *nnode; u_int16_t type; - for (ALL_LIST_ELEMENTS (ospf6->area_list, node, nnode, oa)) - { - type = htons (OSPF6_LSTYPE_INTER_ROUTER); - for (lsa = ospf6_lsdb_type_router_head (type, router_id, oa->lsdb); lsa; - lsa = ospf6_lsdb_type_router_next (type, router_id, lsa)) - ospf6_abr_examin_summary (lsa, oa); + if (ospf6_is_router_abr (ospf6)) + oa = ospf6->backbone; + else + oa = listgetdata(listhead(ospf6->area_list)); - type = htons (OSPF6_LSTYPE_INTER_PREFIX); - for (lsa = ospf6_lsdb_type_router_head (type, router_id, oa->lsdb); lsa; - lsa = ospf6_lsdb_type_router_next (type, router_id, lsa)) - ospf6_abr_examin_summary (lsa, oa); - } + type = htons (OSPF6_LSTYPE_INTER_ROUTER); + for (lsa = ospf6_lsdb_type_router_head (type, router_id, oa->lsdb); lsa; + lsa = ospf6_lsdb_type_router_next (type, router_id, lsa)) + ospf6_abr_examin_summary (lsa, oa); + + type = htons (OSPF6_LSTYPE_INTER_PREFIX); + for (lsa = ospf6_lsdb_type_router_head (type, router_id, oa->lsdb); lsa; + lsa = ospf6_lsdb_type_router_next (type, router_id, lsa)) + ospf6_abr_examin_summary (lsa, oa); } void diff --git a/ospf6d/ospf6_abr.h b/ospf6d/ospf6_abr.h index 816f596451..09b1d87c45 100644 --- a/ospf6d/ospf6_abr.h +++ b/ospf6d/ospf6_abr.h @@ -62,12 +62,13 @@ extern int ospf6_is_router_abr (struct ospf6 *o); extern void ospf6_abr_enable_area (struct ospf6_area *oa); extern void ospf6_abr_disable_area (struct ospf6_area *oa); -extern void ospf6_abr_originate_summary_to_area (struct ospf6_route *route, +extern int ospf6_abr_originate_summary_to_area (struct ospf6_route *route, struct ospf6_area *area); extern void ospf6_abr_originate_summary (struct ospf6_route *route); extern void ospf6_abr_examin_summary (struct ospf6_lsa *lsa, struct ospf6_area *oa); extern void ospf6_abr_examin_brouter (u_int32_t router_id); extern void ospf6_abr_reimport (struct ospf6_area *oa); +extern void ospf6_abr_range_update (struct ospf6_route *range); extern int config_write_ospf6_debug_abr (struct vty *vty); extern void install_element_ospf6_debug_abr (void); diff --git a/ospf6d/ospf6_area.c b/ospf6d/ospf6_area.c index 4b4ca1304a..12ab7ce033 100644 --- a/ospf6d/ospf6_area.c +++ b/ospf6d/ospf6_area.c @@ -160,6 +160,7 @@ ospf6_area_create (u_int32_t area_id, struct ospf6 *o) oa->range_table = OSPF6_ROUTE_TABLE_CREATE (AREA, PREFIX_RANGES); oa->range_table->scope = oa; + bf_init(oa->range_table->idspace, 32); oa->summary_prefix = OSPF6_ROUTE_TABLE_CREATE (AREA, SUMMARY_PREFIXES); oa->summary_prefix->scope = oa; oa->summary_router = OSPF6_ROUTE_TABLE_CREATE (AREA, SUMMARY_ROUTERS); @@ -182,6 +183,11 @@ ospf6_area_create (u_int32_t area_id, struct ospf6 *o) oa->ospf6 = o; listnode_add_sort (o->area_list, oa); + if (area_id == OSPF_AREA_BACKBONE) + { + o->backbone = oa; + } + /* import athoer area's routes as inter-area routes */ for (route = ospf6_route_head (o->route_table); route; route = ospf6_route_next (route)) @@ -196,10 +202,6 @@ ospf6_area_delete (struct ospf6_area *oa) struct listnode *n; struct ospf6_interface *oi; - ospf6_route_table_delete (oa->range_table); - ospf6_route_table_delete (oa->summary_prefix); - ospf6_route_table_delete (oa->summary_router); - /* The ospf6_interface structs store configuration * information which should not be lost/reset when * deleting an area. @@ -217,8 +219,9 @@ ospf6_area_delete (struct ospf6_area *oa) ospf6_route_table_delete (oa->spf_table); ospf6_route_table_delete (oa->route_table); - THREAD_OFF (oa->thread_spf_calculation); - THREAD_OFF (oa->thread_route_calculation); + ospf6_route_table_delete (oa->range_table); + ospf6_route_table_delete (oa->summary_prefix); + ospf6_route_table_delete (oa->summary_router); listnode_delete (oa->ospf6->area_list, oa); oa->ospf6 = NULL; @@ -281,9 +284,6 @@ ospf6_area_disable (struct ospf6_area *oa) ospf6_spf_table_finish(oa->spf_table); ospf6_route_remove_all(oa->route_table); - THREAD_OFF (oa->thread_spf_calculation); - THREAD_OFF (oa->thread_route_calculation); - THREAD_OFF (oa->thread_router_lsa); THREAD_OFF (oa->thread_intra_prefix_lsa); } @@ -346,20 +346,17 @@ DEFUN (area_range, int ret; struct ospf6_area *oa; struct prefix prefix; - struct ospf6_route *range; + struct ospf6_route *range, *route; + u_int32_t cost = OSPF_AREA_RANGE_COST_UNSPEC; OSPF6_CMD_AREA_GET (argv[0], oa); - argc--; - argv++; - ret = str2prefix (argv[0], &prefix); + ret = str2prefix (argv[1], &prefix); if (ret != 1 || prefix.family != AF_INET6) { - vty_out (vty, "Malformed argument: %s%s", argv[0], VNL); + vty_out (vty, "Malformed argument: %s%s", argv[1], VNL); return CMD_SUCCESS; } - argc--; - argv++; range = ospf6_route_lookup (&prefix, oa->range_table); if (range == NULL) @@ -367,23 +364,45 @@ DEFUN (area_range, range = ospf6_route_create (); range->type = OSPF6_DEST_TYPE_RANGE; range->prefix = prefix; + range->path.area_id = oa->area_id; + range->path.cost = OSPF_AREA_RANGE_COST_UNSPEC; + range->linkstate_id = + (u_int32_t) htonl(ospf6_new_range_ls_id (oa->range_table)); } - if (argc) + if (argc > 2) { - if (! strcmp (argv[0], "not-advertise")) - SET_FLAG (range->flag, OSPF6_ROUTE_DO_NOT_ADVERTISE); - else if (! strcmp (argv[0], "advertise")) - UNSET_FLAG (range->flag, OSPF6_ROUTE_DO_NOT_ADVERTISE); + if (strcmp (argv[2], "not-advertise") == 0) + { + SET_FLAG (range->flag, OSPF6_ROUTE_DO_NOT_ADVERTISE); + } + else if (strcmp (argv[2], "advertise") == 0) + { + UNSET_FLAG (range->flag, OSPF6_ROUTE_DO_NOT_ADVERTISE); + } + else + { + VTY_GET_INTEGER_RANGE ("cost", cost, argv[2], 0, OSPF_LS_INFINITY); + UNSET_FLAG (range->flag, OSPF6_ROUTE_DO_NOT_ADVERTISE); + } } - if (range->rnode) + range->path.u.cost_config = cost; + + zlog_debug ("%s: for prefix %s, flag = %x\n", __func__, argv[1], range->flag); + if (range->rnode == NULL) { - vty_out (vty, "Range already defined: %s%s", argv[-1], VNL); - return CMD_WARNING; + ospf6_route_add (range, oa->range_table); + } + + if (ospf6_is_router_abr (ospf6)) + { + /* Redo summaries if required */ + for (route = ospf6_route_head (ospf6->route_table); route; + route = ospf6_route_next (route)) + ospf6_abr_originate_summary(route); } - ospf6_route_add (range, oa->range_table); return CMD_SUCCESS; } @@ -396,6 +415,26 @@ ALIAS (area_range, "Specify IPv6 prefix\n" ) +ALIAS (area_range, + area_range_cost_cmd, + "area (A.B.C.D|<0-4294967295>) range X:X::X:X/M cost <0-16777215>", + "OSPF area parameters\n" + OSPF6_AREA_ID_STR + "Summarize routes matching address/mask (border routers only)\n" + "Area range prefix\n" + "User specified metric for this range\n" + "Advertised metric for this range\n") + +ALIAS (area_range, + area_range_advertise_cost_cmd, + "area (A.B.C.D|<0-4294967295>) range X:X::X:X/M advertise cost <0-16777215>", + "OSPF area parameters\n" + OSPF6_AREA_ID_STR + "Summarize routes matching address/mask (border routers only)\n" + "Area range prefix\n" + "User specified metric for this range\n" + "Advertised metric for this range\n") + DEFUN (no_area_range, no_area_range_cmd, "no area A.B.C.D range X:X::X:X/M", @@ -408,7 +447,7 @@ DEFUN (no_area_range, int ret; struct ospf6_area *oa; struct prefix prefix; - struct ospf6_route *range; + struct ospf6_route *range, *route; OSPF6_CMD_AREA_GET (argv[0], oa); argc--; @@ -428,6 +467,21 @@ DEFUN (no_area_range, return CMD_SUCCESS; } + if (ospf6_is_router_abr(oa->ospf6)) + { + /* Blow away the aggregated LSA and route */ + SET_FLAG (range->flag, OSPF6_ROUTE_REMOVE); + + /* Redo summaries if required */ + for (route = ospf6_route_head (ospf6->route_table); route; + route = ospf6_route_next (route)) + ospf6_abr_originate_summary(route); + + /* purge the old aggregated summary LSA */ + ospf6_abr_originate_summary(range); + } + ospf6_release_range_ls_id(oa->range_table, + (u_int32_t) ntohl(range->linkstate_id)); ospf6_route_remove (range, oa->range_table); return CMD_SUCCESS; @@ -801,6 +855,8 @@ ospf6_area_init (void) install_element (OSPF6_NODE, &area_range_cmd); install_element (OSPF6_NODE, &area_range_advertise_cmd); + install_element (OSPF6_NODE, &area_range_cost_cmd); + install_element (OSPF6_NODE, &area_range_advertise_cost_cmd); install_element (OSPF6_NODE, &no_area_range_cmd); install_element (OSPF6_NODE, &area_import_list_cmd); diff --git a/ospf6d/ospf6_area.h b/ospf6d/ospf6_area.h index 655967a9a3..6911869069 100644 --- a/ospf6d/ospf6_area.h +++ b/ospf6d/ospf6_area.h @@ -55,8 +55,6 @@ struct ospf6_area struct ospf6_route_table *spf_table; struct ospf6_route_table *route_table; - struct thread *thread_spf_calculation; - struct thread *thread_route_calculation; u_int32_t spf_calculation; /* SPF calculation count */ struct thread *thread_router_lsa; @@ -98,6 +96,8 @@ struct ospf6_area #define PREFIX_NAME_OUT(A) (A)->plist_out.name #define PREFIX_LIST_OUT(A) (A)->plist_out.list + /* Time stamps. */ + struct timeval ts_spf; /* SPF calculation time stamp. */ }; #define OSPF6_AREA_ENABLE 0x01 diff --git a/ospf6d/ospf6_asbr.c b/ospf6d/ospf6_asbr.c index 4d86c31e46..880e10ed68 100644 --- a/ospf6d/ospf6_asbr.c +++ b/ospf6d/ospf6_asbr.c @@ -159,7 +159,6 @@ ospf6_asbr_lsa_add (struct ospf6_lsa *lsa) struct prefix asbr_id; struct ospf6_route *asbr_entry, *route; char buf[64]; - int i; external = (struct ospf6_as_external_lsa *) OSPF6_LSA_HEADER_END (lsa->header); @@ -218,18 +217,17 @@ ospf6_asbr_lsa_add (struct ospf6_lsa *lsa) route->path.type = OSPF6_PATH_TYPE_EXTERNAL2; route->path.metric_type = 2; route->path.cost = asbr_entry->path.cost; - route->path.cost_e2 = OSPF6_ASBR_METRIC (external); + route->path.u.cost_e2 = OSPF6_ASBR_METRIC (external); } else { route->path.type = OSPF6_PATH_TYPE_EXTERNAL1; route->path.metric_type = 1; route->path.cost = asbr_entry->path.cost + OSPF6_ASBR_METRIC (external); - route->path.cost_e2 = 0; + route->path.u.cost_e2 = 0; } - for (i = 0; i < OSPF6_MULTI_PATH_LIMIT; i++) - ospf6_nexthop_copy (&route->nexthop[i], &asbr_entry->nexthop[i]); + ospf6_route_copy_nexthops (route, asbr_entry); if (IS_OSPF6_DEBUG_EXAMIN (AS_EXTERNAL)) { @@ -408,8 +406,7 @@ ospf6_asbr_redistribute_unset (int type) if (info->type != type) continue; - ospf6_asbr_redistribute_remove (info->type, route->nexthop[0].ifindex, - &route->prefix); + ospf6_asbr_redistribute_remove (info->type, 0, &route->prefix); } ospf6_asbr_routemap_unset (type); @@ -488,9 +485,11 @@ ospf6_asbr_redistribute_add (int type, int ifindex, struct prefix *prefix, } info->type = type; - match->nexthop[0].ifindex = ifindex; + if (nexthop_num && nexthop) - memcpy (&match->nexthop[0].address, nexthop, sizeof (struct in6_addr)); + ospf6_route_add_nexthop (match, ifindex, nexthop); + else + ospf6_route_add_nexthop (match, ifindex, NULL); /* create/update binding in external_id_table */ prefix_id.family = AF_INET; @@ -533,9 +532,10 @@ ospf6_asbr_redistribute_add (int type, int ifindex, struct prefix *prefix, } info->type = type; - route->nexthop[0].ifindex = ifindex; if (nexthop_num && nexthop) - memcpy (&route->nexthop[0].address, nexthop, sizeof (struct in6_addr)); + ospf6_route_add_nexthop (route, ifindex, nexthop); + else + ospf6_route_add_nexthop (route, ifindex, NULL); /* create/update binding in external_id_table */ prefix_id.family = AF_INET; @@ -1274,13 +1274,13 @@ ospf6_asbr_external_route_show (struct vty *vty, struct ospf6_route *route) inet_ntop (AF_INET6, &info->forwarding, forwarding, sizeof (forwarding)); else snprintf (forwarding, sizeof (forwarding), ":: (ifindex %d)", - route->nexthop[0].ifindex); + ospf6_route_get_first_nh_index (route)); vty_out (vty, "%c %-32s %-15s type-%d %5lu %s%s", zebra_route_char(info->type), prefix, id, route->path.metric_type, (u_long) (route->path.metric_type == 2 ? - route->path.cost_e2 : route->path.cost), + route->path.u.cost_e2 : route->path.cost), forwarding, VNL); } diff --git a/ospf6d/ospf6_flood.c b/ospf6d/ospf6_flood.c index 49ed6e265e..4d537f6eda 100644 --- a/ospf6d/ospf6_flood.c +++ b/ospf6d/ospf6_flood.c @@ -892,6 +892,9 @@ ospf6_receive_lsa (struct ospf6_neighbor *from, table calculation (replacing database copy) */ ospf6_install_lsa (new); + if (OSPF6_LSA_IS_MAXAGE (new)) + ospf6_maxage_remove (from->ospf6_if->area->ospf6); + /* (e) possibly acknowledge */ ospf6_acknowledge_lsa (new, ismore_recent, from); diff --git a/ospf6d/ospf6_interface.c b/ospf6d/ospf6_interface.c index f0ef790933..cdea9c4a24 100644 --- a/ospf6d/ospf6_interface.c +++ b/ospf6d/ospf6_interface.c @@ -391,6 +391,7 @@ ospf6_interface_connected_route_update (struct interface *ifp) struct ospf6_route *route; struct connected *c; struct listnode *node, *nnode; + struct in6_addr nh_addr; oi = (struct ospf6_interface *) ifp->info; if (oi == NULL) @@ -446,8 +447,8 @@ ospf6_interface_connected_route_update (struct interface *ifp) route->path.area_id = oi->area->area_id; route->path.type = OSPF6_PATH_TYPE_INTRA; route->path.cost = oi->cost; - route->nexthop[0].ifindex = oi->interface->ifindex; - inet_pton (AF_INET6, "::1", &route->nexthop[0].address); + inet_pton (AF_INET6, "::1", &nh_addr); + ospf6_route_add_nexthop (route, oi->interface->ifindex, &nh_addr); ospf6_route_add (route, oi->route_connected); } diff --git a/ospf6d/ospf6_intra.c b/ospf6d/ospf6_intra.c index 4ad7521e93..a220437af3 100644 --- a/ospf6d/ospf6_intra.c +++ b/ospf6d/ospf6_intra.c @@ -228,7 +228,7 @@ ospf6_router_lsa_originate (struct thread *thread) for (ALL_LIST_ELEMENTS_RO (oi->neighbor_list, j, on)) if (on->state == OSPF6_NEIGHBOR_FULL) count++; - + if (count == 0) continue; @@ -355,14 +355,25 @@ ospf6_router_lsa_originate (struct thread *thread) /* Do premature-aging of rest, undesired Router-LSAs */ type = ntohs (OSPF6_LSTYPE_ROUTER); router = oa->ospf6->router_id; + count = 0; for (lsa = ospf6_lsdb_type_router_head (type, router, oa->lsdb); lsa; lsa = ospf6_lsdb_type_router_next (type, router, lsa)) { if (ntohl (lsa->header->id) < link_state_id) continue; ospf6_lsa_purge (lsa); + count++; } + /* + * Waiting till the LSA is actually removed from the database to trigger + * SPF delays network convergence. Unlike IPv4, for an ABR, when all + * interfaces associated with an area are gone, triggering an SPF right away + * helps convergence with inter-area routes. + */ + if (count && !link_state_id) + ospf6_spf_schedule (oa->ospf6, OSPF6_SPF_FLAGS_ROUTER_LSA_ORIGINATED); + return 0; } @@ -459,7 +470,15 @@ ospf6_network_lsa_originate (struct thread *thread) if (oi->state != OSPF6_INTERFACE_DR) { if (old) - ospf6_lsa_purge (old); + { + ospf6_lsa_purge (old); + /* + * Waiting till the LSA is actually removed from the database to + * trigger SPF delays network convergence. + */ + ospf6_spf_schedule (oi->area->ospf6, + OSPF6_SPF_FLAGS_NETWORK_LSA_ORIGINATED); + } return 0; } @@ -468,11 +487,11 @@ ospf6_network_lsa_originate (struct thread *thread) /* If none of neighbor is adjacent to us */ count = 0; - + for (ALL_LIST_ELEMENTS_RO (oi->neighbor_list, i, on)) if (on->state == OSPF6_NEIGHBOR_FULL) count++; - + if (count == 0) { if (IS_OSPF6_DEBUG_ORIGINATE (NETWORK)) @@ -1078,7 +1097,7 @@ ospf6_intra_prefix_lsa_originate_transit (struct thread *thread) for (ALL_LIST_ELEMENTS_RO (oi->neighbor_list, i, on)) if (on->state == OSPF6_NEIGHBOR_FULL) full_count++; - + if (full_count == 0) { if (IS_OSPF6_DEBUG_ORIGINATE (INTRA_PREFIX)) @@ -1214,7 +1233,7 @@ ospf6_intra_prefix_lsa_add (struct ospf6_lsa *lsa) struct ospf6_intra_prefix_lsa *intra_prefix_lsa; struct prefix ls_prefix; struct ospf6_route *route, *ls_entry; - int i, prefix_num; + int prefix_num; struct ospf6_prefix *op; char *start, *current, *end; char buf[64]; @@ -1310,13 +1329,11 @@ ospf6_intra_prefix_lsa_add (struct ospf6_lsa *lsa) { ifp = if_lookup_prefix(&route->prefix); if (ifp) - route->nexthop[0].ifindex = ifp->ifindex; + ospf6_route_add_nexthop (route, ifp->ifindex, NULL); } else { - for (i = 0; ospf6_nexthop_is_set (&ls_entry->nexthop[i]) && - i < OSPF6_MULTI_PATH_LIMIT; i++) - ospf6_nexthop_copy (&route->nexthop[i], &ls_entry->nexthop[i]); + ospf6_route_copy_nexthops (route, ls_entry); } if (IS_OSPF6_DEBUG_EXAMIN (INTRA_PREFIX)) @@ -1509,7 +1526,7 @@ ospf6_brouter_debug_print (struct ospf6_route *brouter) id, adv_router); zlog_info (" options: %s router-bits: %s metric-type: %d metric: %d/%d", options, capa, brouter->path.metric_type, - brouter->path.cost, brouter->path.cost_e2); + brouter->path.cost, brouter->path.u.cost_e2); } void diff --git a/ospf6d/ospf6_lsdb.c b/ospf6d/ospf6_lsdb.c index 707afc67eb..37259d6c7c 100644 --- a/ospf6d/ospf6_lsdb.c +++ b/ospf6d/ospf6_lsdb.c @@ -31,7 +31,9 @@ #include "ospf6_proto.h" #include "ospf6_lsa.h" #include "ospf6_lsdb.h" +#include "ospf6_route.h" #include "ospf6d.h" +#include "bitfield.h" struct ospf6_lsdb * ospf6_lsdb_create (void *data) @@ -538,21 +540,42 @@ ospf6_lsdb_show (struct vty *vty, int level, } } -/* Decide new Link State ID to originate. - note return value is network byte order */ +/* Decide new Link State ID to originate for the range. */ +u_int32_t +ospf6_new_range_ls_id (struct ospf6_route_table *range_table) +{ + u_int32_t id; + + bf_assign_index(range_table->idspace, id); + return (id); +} + +/* Release the LS ID back to the ID pool */ +void +ospf6_release_range_ls_id (struct ospf6_route_table *range_table, + u_int32_t id) +{ + bf_release_index(range_table->idspace, id); +} + u_int32_t ospf6_new_ls_id (u_int16_t type, u_int32_t adv_router, struct ospf6_lsdb *lsdb) { struct ospf6_lsa *lsa; - u_int32_t id = 1; + u_int32_t id = 1, tmp_id; + /* This routine is curently invoked only for Inter-Prefix LSAs for + * non-summarized routes (no area/range). + */ for (lsa = ospf6_lsdb_type_router_head (type, adv_router, lsdb); lsa; lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa)) { - if (ntohl (lsa->header->id) < id) - continue; - if (ntohl (lsa->header->id) > id) + tmp_id = ntohl (lsa->header->id); + if (tmp_id < id) + continue; + + if (tmp_id > id) { ospf6_lsdb_lsa_unlock (lsa); break; diff --git a/ospf6d/ospf6_lsdb.h b/ospf6d/ospf6_lsdb.h index a124adbf05..ba4218ae56 100644 --- a/ospf6d/ospf6_lsdb.h +++ b/ospf6d/ospf6_lsdb.h @@ -24,6 +24,7 @@ #include "prefix.h" #include "table.h" +#include "ospf6_route.h" struct ospf6_lsdb { @@ -77,6 +78,9 @@ extern void ospf6_lsdb_show (struct vty *vty, int level, u_int16_t *type, extern u_int32_t ospf6_new_ls_id (u_int16_t type, u_int32_t adv_router, struct ospf6_lsdb *lsdb); +extern u_int32_t ospf6_new_range_ls_id (struct ospf6_route_table *range_table); +extern void ospf6_release_range_ls_id (struct ospf6_route_table *range_table, + u_int32_t id); extern u_int32_t ospf6_new_ls_seqnum (u_int16_t type, u_int32_t id, u_int32_t adv_router, struct ospf6_lsdb *lsdb); diff --git a/ospf6d/ospf6_main.c b/ospf6d/ospf6_main.c index 4f6d9e5140..8272d4733d 100644 --- a/ospf6d/ospf6_main.c +++ b/ospf6d/ospf6_main.c @@ -21,6 +21,7 @@ #include #include +#include #include "getopt.h" #include "thread.h" @@ -237,6 +238,9 @@ main (int argc, char *argv[], char *envp[]) /* Preserve name of myself. */ progname = ((p = strrchr (argv[0], '/')) ? ++p : argv[0]); + /* Seed random number for LSA ID */ + srand (time(NULL)); + /* Command line argument treatment. */ while (1) { diff --git a/ospf6d/ospf6_route.c b/ospf6d/ospf6_route.c index 9e6b33e546..0493e77760 100644 --- a/ospf6d/ospf6_route.c +++ b/ospf6d/ospf6_route.c @@ -37,6 +37,7 @@ #include "ospf6_area.h" #include "ospf6_interface.h" #include "ospf6d.h" +#include "ospf6_zebra.h" unsigned char conf_debug_ospf6_route = 0; @@ -173,18 +174,232 @@ const char *ospf6_path_type_substr[OSPF6_PATH_TYPE_MAX] = { "??", "IA", "IE", "E1", "E2", }; +struct ospf6_nexthop * +ospf6_nexthop_create (void) +{ + struct ospf6_nexthop *nh; + + nh = XCALLOC (MTYPE_OSPF6_NEXTHOP, sizeof (struct ospf6_nexthop)); + return nh; +} + +void +ospf6_nexthop_delete (struct ospf6_nexthop *nh) +{ + if (nh) + XFREE (MTYPE_OSPF6_NEXTHOP, nh); +} + +void +ospf6_free_nexthops (struct list *nh_list) +{ + struct ospf6_nexthop *nh; + struct listnode *node, *nnode; + + if (nh_list) + { + for (ALL_LIST_ELEMENTS (nh_list, node, nnode, nh)) + ospf6_nexthop_delete (nh); + } +} + +void +ospf6_clear_nexthops (struct list *nh_list) +{ + struct listnode *node; + struct ospf6_nexthop *nh; + + if (nh_list) + { + for (ALL_LIST_ELEMENTS_RO (nh_list, node, nh)) + ospf6_nexthop_clear (nh); + } +} + +static struct ospf6_nexthop * +ospf6_route_find_nexthop (struct list *nh_list, struct ospf6_nexthop *nh_match) +{ + struct listnode *node; + struct ospf6_nexthop *nh; + + if (nh_list && nh_match) + { + for (ALL_LIST_ELEMENTS_RO (nh_list, node, nh)) + { + if (ospf6_nexthop_is_same (nh, nh_match)) + return (nh); + } + } + + return (NULL); +} + +void +ospf6_copy_nexthops (struct list *dst, struct list *src) +{ + struct ospf6_nexthop *nh_new, *nh; + struct listnode *node; + + if (dst && src) + { + for (ALL_LIST_ELEMENTS_RO (src, node, nh)) + { + if (ospf6_nexthop_is_set (nh)) + { + nh_new = ospf6_nexthop_create (); + ospf6_nexthop_copy (nh_new, nh); + listnode_add (dst, nh_new); + } + } + } +} + +void +ospf6_merge_nexthops (struct list *dst, struct list *src) +{ + struct listnode *node; + struct ospf6_nexthop *nh, *nh_new; + + if (src && dst) + { + for (ALL_LIST_ELEMENTS_RO (src, node, nh)) + { + if (!ospf6_route_find_nexthop (dst, nh)) + { + nh_new = ospf6_nexthop_create (); + ospf6_nexthop_copy (nh_new, nh); + listnode_add (dst, nh_new); + } + } + } +} + +int +ospf6_route_cmp_nexthops (struct ospf6_route *a, struct ospf6_route *b) +{ + struct listnode *anode, *bnode; + struct ospf6_nexthop *anh, *bnh; + + if (a && b) + { + if (listcount(a->nh_list) == listcount(b->nh_list)) + { + for (ALL_LIST_ELEMENTS_RO (a->nh_list, anode, anh)) + { + for (ALL_LIST_ELEMENTS_RO (b->nh_list, bnode, bnh)) + if (!ospf6_nexthop_is_same (anh, bnh)) + return (1); + } + return (0); + } + else + return (1); + } + /* One of the routes doesn't exist ? */ + return (1); +} + +int +ospf6_num_nexthops (struct list *nh_list) +{ + return (listcount(nh_list)); +} + +void +ospf6_add_nexthop (struct list *nh_list, int ifindex, + struct in6_addr *addr) +{ + struct ospf6_nexthop *nh; + struct ospf6_nexthop nh_match; + + if (nh_list) + { + nh_match.ifindex = ifindex; + if (addr != NULL) + memcpy (&nh_match.address, addr, sizeof (struct in6_addr)); + else + memset (&nh_match.address, 0, sizeof (struct in6_addr)); + + if (!ospf6_route_find_nexthop (nh_list, &nh_match)) + { + nh = ospf6_nexthop_create(); + ospf6_nexthop_copy (nh, &nh_match); + listnode_add (nh_list, nh); + } + } +} + +void +ospf6_route_zebra_copy_nexthops (struct ospf6_route *route, + unsigned int *ifindexes, + struct in6_addr **nexthop_addr, + int entries) +{ + struct ospf6_nexthop *nh; + struct listnode *node; + char buf[64]; + int i; + + if (route) + { + i = 0; + for (ALL_LIST_ELEMENTS_RO (route->nh_list, node, nh)) + { + if (IS_OSPF6_DEBUG_ZEBRA (SEND)) + { + char ifname[IFNAMSIZ]; + inet_ntop (AF_INET6, &nh->address, buf, sizeof (buf)); + if (!if_indextoname(nh->ifindex, ifname)) + strlcpy(ifname, "unknown", sizeof(ifname)); + zlog_debug (" nexthop: %s%%%.*s(%d)", buf, IFNAMSIZ, ifname, + nh->ifindex); + } + if (i < entries) + { + nexthop_addr[i] = &nh->address; + ifindexes[i] = nh->ifindex; + i++; + } + else + { + return; + } + } + } +} + +int +ospf6_route_get_first_nh_index (struct ospf6_route *route) +{ + struct ospf6_nexthop *nh; + + if (route) + { + if (nh = (struct ospf6_nexthop *)listhead (route->nh_list)) + return (nh->ifindex); + } + + return (-1); +} + struct ospf6_route * ospf6_route_create (void) { struct ospf6_route *route; route = XCALLOC (MTYPE_OSPF6_ROUTE, sizeof (struct ospf6_route)); + route->nh_list = list_new(); return route; } void ospf6_route_delete (struct ospf6_route *route) { - XFREE (MTYPE_OSPF6_ROUTE, route); + if (route) + { + ospf6_free_nexthops (route->nh_list); + list_free (route->nh_list); + XFREE (MTYPE_OSPF6_ROUTE, route); + } } struct ospf6_route * @@ -193,7 +408,15 @@ ospf6_route_copy (struct ospf6_route *route) struct ospf6_route *new; new = ospf6_route_create (); - memcpy (new, route, sizeof (struct ospf6_route)); + new->type = route->type; + memcpy (&new->prefix, &route->prefix, sizeof (struct prefix)); + new->installed = route->installed; + new->changed = route->changed; + new->flag = route->flag; + new->route_option = route->route_option; + new->linkstate_id = route->linkstate_id; + new->path = route->path; + ospf6_copy_nexthops (new->nh_list, route->nh_list); new->rnode = NULL; new->prev = NULL; new->next = NULL; @@ -226,7 +449,7 @@ ospf6_route_unlock (struct ospf6_route *route) /* Route compare function. If ra is more preferred, it returns less than 0. If rb is more preferred returns greater than 0. Otherwise (neither one is preferred), returns 0 */ -static int +int ospf6_route_cmp (struct ospf6_route *ra, struct ospf6_route *rb) { assert (ospf6_route_is_same (ra, rb)); @@ -246,8 +469,8 @@ ospf6_route_cmp (struct ospf6_route *ra, struct ospf6_route *rb) if (ra->path.type == OSPF6_PATH_TYPE_EXTERNAL2) { - if (ra->path.cost_e2 != rb->path.cost_e2) - return (ra->path.cost_e2 - rb->path.cost_e2); + if (ra->path.u.cost_e2 != rb->path.u.cost_e2) + return (ra->path.u.cost_e2 - rb->path.u.cost_e2); } else { @@ -789,6 +1012,8 @@ ospf6_route_show (struct vty *vty, struct ospf6_route *route) char destination[64], nexthop[64]; char duration[16], ifname[IFNAMSIZ]; struct timeval now, res; + struct listnode *node; + struct ospf6_nexthop *nh; quagga_gettime (QUAGGA_CLK_MONOTONIC, &now); timersub (&now, &route->changed, &res); @@ -804,29 +1029,28 @@ ospf6_route_show (struct vty *vty, struct ospf6_route *route) else prefix2str (&route->prefix, destination, sizeof (destination)); - /* nexthop */ - inet_ntop (AF_INET6, &route->nexthop[0].address, nexthop, - sizeof (nexthop)); - if (! if_indextoname (route->nexthop[0].ifindex, ifname)) - snprintf (ifname, sizeof (ifname), "%d", route->nexthop[0].ifindex); - vty_out (vty, "%c%1s %2s %-30s %-25s %6.*s %s%s", - (ospf6_route_is_best (route) ? '*' : ' '), - OSPF6_DEST_TYPE_SUBSTR (route->type), - OSPF6_PATH_TYPE_SUBSTR (route->path.type), - destination, nexthop, IFNAMSIZ, ifname, duration, VNL); - - for (i = 1; ospf6_nexthop_is_set (&route->nexthop[i]) && - i < OSPF6_MULTI_PATH_LIMIT; i++) + i = 0; + for (ALL_LIST_ELEMENTS_RO (route->nh_list, node, nh)) { /* nexthop */ - inet_ntop (AF_INET6, &route->nexthop[i].address, nexthop, + inet_ntop (AF_INET6, &nh->address, nexthop, sizeof (nexthop)); - if (! if_indextoname (route->nexthop[i].ifindex, ifname)) - snprintf (ifname, sizeof (ifname), "%d", route->nexthop[i].ifindex); - - vty_out (vty, "%c%1s %2s %-30s %-25s %6.*s %s%s", - ' ', "", "", "", nexthop, IFNAMSIZ, ifname, "", VNL); + if (! if_indextoname (nh->ifindex, ifname)) + snprintf (ifname, sizeof (ifname), "%d", nh->ifindex); + + if (!i) + { + vty_out (vty, "%c%1s %2s %-30s %-25s %6.*s %s%s", + (ospf6_route_is_best (route) ? '*' : ' '), + OSPF6_DEST_TYPE_SUBSTR (route->type), + OSPF6_PATH_TYPE_SUBSTR (route->path.type), + destination, nexthop, IFNAMSIZ, ifname, duration, VNL); + i++; + } + else + vty_out (vty, "%c%1s %2s %-30s %-25s %6.*s %s%s", + ' ', "", "", "", nexthop, IFNAMSIZ, ifname, "", VNL); } } @@ -837,7 +1061,8 @@ ospf6_route_show_detail (struct vty *vty, struct ospf6_route *route) char area_id[16], id[16], adv_router[16], capa[16], options[16]; struct timeval now, res; char duration[16]; - int i; + struct listnode *node; + struct ospf6_nexthop *nh; quagga_gettime (QUAGGA_CLK_MONOTONIC, &now); @@ -909,18 +1134,16 @@ ospf6_route_show_detail (struct vty *vty, struct ospf6_route *route) vty_out (vty, "Metric Type: %d%s", route->path.metric_type, VNL); vty_out (vty, "Metric: %d (%d)%s", - route->path.cost, route->path.cost_e2, VNL); + route->path.cost, route->path.u.cost_e2, VNL); /* Nexthops */ vty_out (vty, "Nexthop:%s", VNL); - for (i = 0; ospf6_nexthop_is_set (&route->nexthop[i]) && - i < OSPF6_MULTI_PATH_LIMIT; i++) + for (ALL_LIST_ELEMENTS_RO (route->nh_list, node, nh)) { /* nexthop */ - inet_ntop (AF_INET6, &route->nexthop[i].address, nexthop, - sizeof (nexthop)); - if (! if_indextoname (route->nexthop[i].ifindex, ifname)) - snprintf (ifname, sizeof (ifname), "%d", route->nexthop[i].ifindex); + inet_ntop (AF_INET6, &nh->address, nexthop, sizeof (nexthop)); + if (! if_indextoname (nh->ifindex, ifname)) + snprintf (ifname, sizeof (ifname), "%d", nh->ifindex); vty_out (vty, " %s %.*s%s", nexthop, IFNAMSIZ, ifname, VNL); } vty_out (vty, "%s", VNL); @@ -933,7 +1156,7 @@ ospf6_route_show_table_summary (struct vty *vty, struct ospf6_route *route, *prev = NULL; int i, pathtype[OSPF6_PATH_TYPE_MAX]; unsigned int number = 0; - int nhinval = 0, ecmp = 0; + int nh_count =0 , nhinval = 0, ecmp = 0; int alternative = 0, destination = 0; for (i = 0; i < OSPF6_PATH_TYPE_MAX; i++) @@ -946,9 +1169,10 @@ ospf6_route_show_table_summary (struct vty *vty, destination++; else alternative++; - if (! ospf6_nexthop_is_set (&route->nexthop[0])) + nh_count = ospf6_num_nexthops (route->nh_list); + if (!nh_count) nhinval++; - else if (ospf6_nexthop_is_set (&route->nexthop[1])) + else if (nh_count > 1) ecmp++; pathtype[route->path.type]++; number++; diff --git a/ospf6d/ospf6_route.h b/ospf6d/ospf6_route.h index b384824cb0..0f71595111 100644 --- a/ospf6d/ospf6_route.h +++ b/ospf6d/ospf6_route.h @@ -96,7 +96,10 @@ struct ospf6_path /* Cost */ u_int8_t metric_type; u_int32_t cost; - u_int32_t cost_e2; + union { + u_int32_t cost_e2; + u_int32_t cost_config; + } u; }; #define OSPF6_PATH_TYPE_NONE 0 @@ -109,6 +112,7 @@ struct ospf6_path #include "prefix.h" #include "table.h" +#include "bitfield.h" struct ospf6_route { @@ -132,17 +136,18 @@ struct ospf6_route /* flag */ u_char flag; - /* path */ - struct ospf6_path path; - - /* nexthop */ - struct ospf6_nexthop nexthop[OSPF6_MULTI_PATH_LIMIT]; - /* route option */ void *route_option; /* link state id for advertising */ u_int32_t linkstate_id; + + /* path */ + struct ospf6_path path; + + /* nexthop */ + struct list *nh_list; + }; #define OSPF6_DEST_TYPE_NONE 0 @@ -160,6 +165,7 @@ struct ospf6_route #define OSPF6_ROUTE_ACTIVE_SUMMARY 0x10 #define OSPF6_ROUTE_DO_NOT_ADVERTISE 0x20 #define OSPF6_ROUTE_WAS_REMOVED 0x40 +#define OSPF6_ROUTE_BLACKHOLE_ADDED 0x80 struct ospf6_route_table { @@ -172,6 +178,8 @@ struct ospf6_route_table u_int32_t count; + bitfield_t idspace; + /* hooks */ void (*hook_add) (struct ospf6_route *); void (*hook_change) (struct ospf6_route *); @@ -231,8 +239,8 @@ extern const char *ospf6_path_type_substr[OSPF6_PATH_TYPE_MAX]; ((ra)->type == (rb)->type && \ memcmp (&(ra)->prefix, &(rb)->prefix, sizeof (struct prefix)) == 0 && \ memcmp (&(ra)->path, &(rb)->path, sizeof (struct ospf6_path)) == 0 && \ - memcmp (&(ra)->nexthop, &(rb)->nexthop, \ - sizeof (struct ospf6_nexthop) * OSPF6_MULTI_PATH_LIMIT) == 0) + ospf6_route_cmp_nexthops (ra, rb) == 0) + #define ospf6_route_is_best(r) (CHECK_FLAG ((r)->flag, OSPF6_ROUTE_BEST)) #define ospf6_linkstate_prefix_adv_router(x) \ @@ -251,9 +259,35 @@ extern void ospf6_linkstate_prefix (u_int32_t adv_router, u_int32_t id, extern void ospf6_linkstate_prefix2str (struct prefix *prefix, char *buf, int size); +extern struct ospf6_nexthop *ospf6_nexthop_create (void); +extern void ospf6_nexthop_delete (struct ospf6_nexthop *nh); +extern void ospf6_free_nexthops (struct list *nh_list); +extern void ospf6_clear_nexthops (struct list *nh_list); +extern int ospf6_num_nexthops (struct list *nh_list); +extern void ospf6_copy_nexthops (struct list *dst, struct list *src); +extern void ospf6_merge_nexthops (struct list *dst, struct list *src); +extern void ospf6_add_nexthop (struct list *nh_list, int ifindex, + struct in6_addr *addr); +extern int ospf6_num_nexthops (struct list *nh_list); +extern int ospf6_route_cmp_nexthops (struct ospf6_route *a, + struct ospf6_route *b); +extern void ospf6_route_zebra_copy_nexthops (struct ospf6_route *route, + unsigned int *ifindices, + struct in6_addr **addr, + int entries); +extern int ospf6_route_get_first_nh_index (struct ospf6_route *route); + +/* Hide abstraction of nexthop implementation in route from outsiders */ +#define ospf6_route_copy_nexthops(dst, src) ospf6_copy_nexthops(dst->nh_list, src->nh_list) +#define ospf6_route_merge_nexthops(dst, src) ospf6_merge_nexthops(dst->nh_list, src->nh_list) +#define ospf6_route_num_nexthops(route) ospf6_num_nexthops(route->nh_list) +#define ospf6_route_add_nexthop(route, ifindex, addr) \ + ospf6_add_nexthop(route->nh_list, ifindex, addr) + extern struct ospf6_route *ospf6_route_create (void); extern void ospf6_route_delete (struct ospf6_route *); extern struct ospf6_route *ospf6_route_copy (struct ospf6_route *route); +extern int ospf6_route_cmp (struct ospf6_route *ra, struct ospf6_route *rb); extern void ospf6_route_lock (struct ospf6_route *route); extern void ospf6_route_unlock (struct ospf6_route *route); diff --git a/ospf6d/ospf6_spf.c b/ospf6d/ospf6_spf.c index 3ef5485fde..20ec3721da 100644 --- a/ospf6d/ospf6_spf.c +++ b/ospf6d/ospf6_spf.c @@ -43,6 +43,41 @@ unsigned char conf_debug_ospf6_spf = 0; +static void +ospf6_spf_copy_nexthops_to_route (struct ospf6_route *rt, + struct ospf6_vertex *v) +{ + if (rt && v) + ospf6_copy_nexthops (rt->nh_list, v->nh_list); +} + +static void +ospf6_spf_merge_nexthops_to_route (struct ospf6_route *rt, + struct ospf6_vertex *v) +{ + if (rt && v) + ospf6_merge_nexthops (rt->nh_list, v->nh_list); +} + +static int +ospf6_spf_get_ifindex_from_nh (struct ospf6_vertex *v) +{ + struct ospf6_nexthop *nh; + struct listnode *node; + + if (v) + { + node = listhead(v->nh_list); + if (node) + { + nh = listgetdata (node); + if (nh) + return (nh->ifindex); + } + } + return -1; +} + static int ospf6_vertex_cmp (void *a, void *b) { @@ -76,7 +111,6 @@ static struct ospf6_vertex * ospf6_vertex_create (struct ospf6_lsa *lsa) { struct ospf6_vertex *v; - int i; v = (struct ospf6_vertex *) XMALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_vertex)); @@ -96,6 +130,10 @@ ospf6_vertex_create (struct ospf6_lsa *lsa) /* name */ ospf6_linkstate_prefix2str (&v->vertex_id, v->name, sizeof (v->name)); + if (IS_OSPF6_DEBUG_SPF (PROCESS)) + zlog_debug ("%s: Creating vertex %s of type %s", __func__, v->name, + ((ntohs (lsa->header->type) == OSPF6_LSTYPE_ROUTER) ? "Router" : "N/W")); + /* Associated LSA */ v->lsa = lsa; @@ -105,8 +143,7 @@ ospf6_vertex_create (struct ospf6_lsa *lsa) v->options[1] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 2); v->options[2] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 3); - for (i = 0; i < OSPF6_MULTI_PATH_LIMIT; i++) - ospf6_nexthop_clear (&v->nexthop[i]); + v->nh_list = list_new(); v->parent = NULL; v->child_list = list_new (); @@ -224,7 +261,8 @@ static void ospf6_nexthop_calc (struct ospf6_vertex *w, struct ospf6_vertex *v, caddr_t lsdesc) { - int i, ifindex; + int i; + int ifindex; struct ospf6_interface *oi; u_int16_t type; u_int32_t adv_router; @@ -233,8 +271,14 @@ ospf6_nexthop_calc (struct ospf6_vertex *w, struct ospf6_vertex *v, char buf[64]; assert (VERTEX_IS_TYPE (ROUTER, w)); - ifindex = (VERTEX_IS_TYPE (NETWORK, v) ? v->nexthop[0].ifindex : + ifindex = (VERTEX_IS_TYPE (NETWORK, v) ? ospf6_spf_get_ifindex_from_nh (v) : ROUTER_LSDESC_GET_IFID (lsdesc)); + if (ifindex == -1) + { + zlog_err ("No nexthop ifindex at vertex %s", v->name); + return; + } + oi = ospf6_interface_lookup_by_ifindex (ifindex); if (oi == NULL) { @@ -263,13 +307,8 @@ ospf6_nexthop_calc (struct ospf6_vertex *w, struct ospf6_vertex *v, zlog_debug (" nexthop %s from %s", buf, lsa->name); } - if (i < OSPF6_MULTI_PATH_LIMIT) - { - memcpy (&w->nexthop[i].address, &link_lsa->linklocal_addr, - sizeof (struct in6_addr)); - w->nexthop[i].ifindex = ifindex; - i++; - } + ospf6_add_nexthop (w->nh_list, ifindex, &link_lsa->linklocal_addr); + i++; } if (i == 0 && IS_OSPF6_DEBUG_SPF (PROCESS)) @@ -280,8 +319,7 @@ static int ospf6_spf_install (struct ospf6_vertex *v, struct ospf6_route_table *result_table) { - struct ospf6_route *route; - int i, j; + struct ospf6_route *route, *parent_route; struct ospf6_vertex *prev; if (IS_OSPF6_DEBUG_SPF (PROCESS)) @@ -302,23 +340,7 @@ ospf6_spf_install (struct ospf6_vertex *v, if (IS_OSPF6_DEBUG_SPF (PROCESS)) zlog_debug (" another path found, merge"); - for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && - i < OSPF6_MULTI_PATH_LIMIT; i++) - { - for (j = 0; j < OSPF6_MULTI_PATH_LIMIT; j++) - { - if (ospf6_nexthop_is_set (&route->nexthop[j])) - { - if (ospf6_nexthop_is_same (&route->nexthop[j], - &v->nexthop[i])) - break; - else - continue; - } - ospf6_nexthop_copy (&route->nexthop[j], &v->nexthop[i]); - break; - } - } + ospf6_spf_merge_nexthops_to_route (route, v); prev = (struct ospf6_vertex *) route->route_option; assert (prev->hops <= v->hops); @@ -345,15 +367,35 @@ ospf6_spf_install (struct ospf6_vertex *v, route->path.origin.adv_router = v->lsa->header->adv_router; route->path.metric_type = 1; route->path.cost = v->cost; - route->path.cost_e2 = v->hops; + route->path.u.cost_e2 = v->hops; route->path.router_bits = v->capability; route->path.options[0] = v->options[0]; route->path.options[1] = v->options[1]; route->path.options[2] = v->options[2]; - for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && - i < OSPF6_MULTI_PATH_LIMIT; i++) - ospf6_nexthop_copy (&route->nexthop[i], &v->nexthop[i]); + ospf6_spf_copy_nexthops_to_route (route, v); + + /* + * The SPF logic implementation does not transfer the multipathing properties + * of a parent to a child node. Thus if there was a 3-way multipath to a + * node's parent and a single hop from the parent to the child, the logic of + * creating new vertices and computing next hops prevents there from being 3 + * paths to the child node. This is primarily because the resolution of + * multipath is done in this routine, not in the main spf loop. + * + * The following logic addresses that problem by merging the parent's nexthop + * information with the child's, if the parent is not the root of the tree. + * This is based on the assumption that before a node's route is installed, + * its parent's route's nexthops have already been installed. + */ + if (v->parent && v->parent->hops) + { + parent_route = ospf6_route_lookup (&v->parent->vertex_id, result_table); + if (parent_route) + { + ospf6_route_merge_nexthops (route, parent_route); + } + } if (v->parent) listnode_add_sort (v->parent->child_list, v); @@ -416,19 +458,24 @@ ospf6_spf_calculation (u_int32_t router_id, { struct pqueue *candidate_list; struct ospf6_vertex *root, *v, *w; - int i; int size; caddr_t lsdesc; struct ospf6_lsa *lsa; + struct in6_addr address; ospf6_spf_table_finish (result_table); /* Install the calculating router itself as the root of the SPF tree */ /* construct root vertex */ lsa = ospf6_lsdb_lookup (htons (OSPF6_LSTYPE_ROUTER), htonl (0), - router_id, oa->lsdb); + router_id, oa->lsdb_self); if (lsa == NULL) - return; + { + if (IS_OSPF6_DEBUG_SPF (PROCESS)) + zlog_debug ("%s: No router LSA for area %s\n", + __func__, oa->name); + return; + } /* initialize */ candidate_list = pqueue_create (); @@ -438,8 +485,7 @@ ospf6_spf_calculation (u_int32_t router_id, root->area = oa; root->cost = 0; root->hops = 0; - root->nexthop[0].ifindex = 0; /* loopbak I/F is better ... */ - inet_pton (AF_INET6, "::1", &root->nexthop[0].address); + inet_pton (AF_INET6, "::1", &address); /* Actually insert root to the candidate-list as the only candidate */ pqueue_enqueue (root, candidate_list); @@ -470,6 +516,9 @@ ospf6_spf_calculation (u_int32_t router_id, if (lsa == NULL) continue; + if (OSPF6_LSA_IS_MAXAGE (lsa)) + continue; + if (! ospf6_lsdesc_backlink (lsa, lsdesc, v)) continue; @@ -489,14 +538,12 @@ ospf6_spf_calculation (u_int32_t router_id, /* nexthop calculation */ if (w->hops == 0) - w->nexthop[0].ifindex = ROUTER_LSDESC_GET_IFID (lsdesc); + ospf6_add_nexthop (w->nh_list, ROUTER_LSDESC_GET_IFID (lsdesc), NULL); else if (w->hops == 1 && v->hops == 0) ospf6_nexthop_calc (w, v, lsdesc); else { - for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && - i < OSPF6_MULTI_PATH_LIMIT; i++) - ospf6_nexthop_copy (&w->nexthop[i], &v->nexthop[i]); + ospf6_copy_nexthops (w->nh_list, v->nh_list); } /* add new candidate to the candidate_list */ diff --git a/ospf6d/ospf6_spf.h b/ospf6d/ospf6_spf.h index b3481dc379..7bf525d6fe 100644 --- a/ospf6d/ospf6_spf.h +++ b/ospf6d/ospf6_spf.h @@ -60,9 +60,6 @@ struct ospf6_vertex /* Router hops to this node */ u_char hops; - /* nexthops to this node */ - struct ospf6_nexthop nexthop[OSPF6_MULTI_PATH_LIMIT]; - /* capability bits */ u_char capability; @@ -72,6 +69,9 @@ struct ospf6_vertex /* For tree display */ struct ospf6_vertex *parent; struct list *child_list; + + /* nexthops to this node */ + struct list *nh_list; }; #define OSPF6_VERTEX_TYPE_ROUTER 0x01 diff --git a/ospf6d/ospf6_top.c b/ospf6d/ospf6_top.c index 7191270143..a08826d630 100644 --- a/ospf6d/ospf6_top.c +++ b/ospf6d/ospf6_top.c @@ -92,6 +92,7 @@ ospf6_top_route_hook_add (struct ospf6_route *route) static void ospf6_top_route_hook_remove (struct ospf6_route *route) { + route->flag |= OSPF6_ROUTE_REMOVE; ospf6_abr_originate_summary (route); ospf6_zebra_route_update_remove (route); } @@ -107,6 +108,7 @@ ospf6_top_brouter_hook_add (struct ospf6_route *route) static void ospf6_top_brouter_hook_remove (struct ospf6_route *route) { + route->flag |= OSPF6_ROUTE_REMOVE; ospf6_abr_examin_brouter (ADV_ROUTER_IN_PREFIX (&route->prefix)); ospf6_asbr_lsentry_remove (route); ospf6_abr_originate_summary (route); diff --git a/ospf6d/ospf6_zebra.c b/ospf6d/ospf6_zebra.c index 85f70647f9..04a1fd6488 100644 --- a/ospf6d/ospf6_zebra.c +++ b/ospf6d/ospf6_zebra.c @@ -362,7 +362,7 @@ ospf6_zebra_route_update (int type, struct ospf6_route *request) int nhcount; struct in6_addr **nexthops; unsigned int *ifindexes; - int i, ret = 0; + int ret = 0; struct prefix_ipv6 *dest; if (IS_OSPF6_DEBUG_ZEBRA (SEND)) @@ -408,11 +408,7 @@ ospf6_zebra_route_update (int type, struct ospf6_route *request) return; } - nhcount = 0; - for (i = 0; i < OSPF6_MULTI_PATH_LIMIT; i++) - if (ospf6_nexthop_is_set (&request->nexthop[i])) - nhcount++; - + nhcount = ospf6_route_num_nexthops (request); if (nhcount == 0) { if (IS_OSPF6_DEBUG_ZEBRA (SEND)) @@ -439,21 +435,7 @@ ospf6_zebra_route_update (int type, struct ospf6_route *request) return; } - for (i = 0; i < nhcount; i++) - { - if (IS_OSPF6_DEBUG_ZEBRA (SEND)) - { - char ifname[IFNAMSIZ]; - inet_ntop (AF_INET6, &request->nexthop[i].address, - buf, sizeof (buf)); - if (!if_indextoname(request->nexthop[i].ifindex, ifname)) - strlcpy(ifname, "unknown", sizeof(ifname)); - zlog_debug (" nexthop: %s%%%.*s(%d)", buf, IFNAMSIZ, ifname, - request->nexthop[i].ifindex); - } - nexthops[i] = &request->nexthop[i].address; - ifindexes[i] = request->nexthop[i].ifindex; - } + ospf6_route_zebra_copy_nexthops (request, ifindexes, nexthops, nhcount); api.type = ZEBRA_ROUTE_OSPF6; api.flags = 0; @@ -467,7 +449,7 @@ ospf6_zebra_route_update (int type, struct ospf6_route *request) api.ifindex = ifindexes; SET_FLAG (api.message, ZAPI_MESSAGE_METRIC); api.metric = (request->path.metric_type == 2 ? - request->path.cost_e2 : request->path.cost); + request->path.u.cost_e2 : request->path.cost); dest = (struct prefix_ipv6 *) &request->prefix; if (type == REM) @@ -509,6 +491,90 @@ ospf6_zebra_route_update_remove (struct ospf6_route *request) ospf6_zebra_route_update (REM, request); } +void +ospf6_zebra_add_discard (struct ospf6_route *request) +{ + struct zapi_ipv6 api; + char buf[INET6_ADDRSTRLEN]; + struct prefix_ipv6 *dest; + + if (zclient->redist[ZEBRA_ROUTE_OSPF6]) + { + if (!CHECK_FLAG (request->flag, OSPF6_ROUTE_BLACKHOLE_ADDED)) + { + api.type = ZEBRA_ROUTE_OSPF6; + api.flags = ZEBRA_FLAG_BLACKHOLE; + api.message = 0; + api.safi = SAFI_UNICAST; + SET_FLAG (api.message, ZAPI_MESSAGE_NEXTHOP); + api.nexthop_num = 0; + api.ifindex_num = 0; + + dest = (struct prefix_ipv6 *) &request->prefix; + + zapi_ipv6_route (ZEBRA_IPV6_ROUTE_ADD, zclient, dest, &api); + + if (IS_OSPF6_DEBUG_ZEBRA (SEND)) + zlog_debug ("Zebra: Route add discard %s/%d", + inet_ntop (AF_INET6, &dest->prefix, + buf, INET6_ADDRSTRLEN), + dest->prefixlen); + SET_FLAG (request->flag, OSPF6_ROUTE_BLACKHOLE_ADDED); + } + else + { + dest = (struct prefix_ipv6 *) &request->prefix; + + if (IS_OSPF6_DEBUG_ZEBRA (SEND)) + zlog_debug ("Zebra: Blackhole route present already %s/%d", + inet_ntop (AF_INET6, &dest->prefix, + buf, INET6_ADDRSTRLEN), + dest->prefixlen); + } + } +} + +void +ospf6_zebra_delete_discard (struct ospf6_route *request) +{ + struct zapi_ipv6 api; + char buf[INET6_ADDRSTRLEN]; + struct prefix_ipv6 *dest; + + if (zclient->redist[ZEBRA_ROUTE_OSPF6]) + { + if (CHECK_FLAG (request->flag, OSPF6_ROUTE_BLACKHOLE_ADDED)) + { + + api.type = ZEBRA_ROUTE_OSPF6; + api.flags = ZEBRA_FLAG_BLACKHOLE; + api.message = 0; + api.safi = SAFI_UNICAST; + SET_FLAG (api.message, ZAPI_MESSAGE_NEXTHOP); + api.nexthop_num = 0; + api.ifindex_num = 0; + + dest = (struct prefix_ipv6 *) &request->prefix; + + zapi_ipv6_route (ZEBRA_IPV6_ROUTE_DELETE, zclient, dest, &api); + + if (IS_OSPF6_DEBUG_ZEBRA (SEND)) + zlog_debug ("Zebra: Route delete discard %s/%d", + inet_ntop (AF_INET6, &dest->prefix, buf, + INET6_ADDRSTRLEN), dest->prefixlen); + UNSET_FLAG (request->flag, OSPF6_ROUTE_BLACKHOLE_ADDED); + } + else + { + dest = (struct prefix_ipv6 *) &request->prefix; + if (IS_OSPF6_DEBUG_ZEBRA (SEND)) + zlog_debug ("Zebra: Blackhole route already deleted %s/%d", + inet_ntop (AF_INET6, &dest->prefix, buf, + INET6_ADDRSTRLEN), dest->prefixlen); + } + } +} + DEFUN (redistribute_ospf6, redistribute_ospf6_cmd, "redistribute ospf6", diff --git a/ospf6d/ospf6_zebra.h b/ospf6d/ospf6_zebra.h index 24a4ae6396..753b8edc94 100644 --- a/ospf6d/ospf6_zebra.h +++ b/ospf6d/ospf6_zebra.h @@ -44,6 +44,8 @@ extern void ospf6_zebra_redistribute (int); extern void ospf6_zebra_no_redistribute (int); #define ospf6_zebra_is_redistribute(type) (zclient->redist[type]) extern void ospf6_zebra_init (void); +extern void ospf6_zebra_add_discard (struct ospf6_route *request); +extern void ospf6_zebra_delete_discard (struct ospf6_route *request); extern int config_write_ospf6_debug_zebra (struct vty *vty); extern void install_element_ospf6_debug_zebra (void); diff --git a/ospfd/ospf_abr.h b/ospfd/ospf_abr.h index e367e44772..2a728936d3 100644 --- a/ospfd/ospf_abr.h +++ b/ospfd/ospf_abr.h @@ -52,7 +52,6 @@ struct ospf_area_range /* Configured range cost. */ u_int32_t cost_config; -#define OSPF_AREA_RANGE_COST_UNSPEC -1U }; /* Prototypes. */ diff --git a/zebra/rt_netlink.c b/zebra/rt_netlink.c index 7c6b3782a5..5e8eb7b9f1 100644 --- a/zebra/rt_netlink.c +++ b/zebra/rt_netlink.c @@ -1420,6 +1420,10 @@ netlink_route (int cmd, int family, void *dest, int length, void *gate, req.r.rtm_type = RTN_UNREACHABLE; else assert (RTN_BLACKHOLE != RTN_UNREACHABLE); /* false */ + + if (IS_ZEBRA_DEBUG_KERNEL) + zlog_debug ("%s: Adding discard route for family %s\n", + __FUNCTION__, family == AF_INET ? "IPv4" : "IPv6"); } else req.r.rtm_type = RTN_UNICAST; @@ -1912,13 +1916,17 @@ kernel_delete_ipv4 (struct prefix *p, struct rib *rib) int kernel_add_ipv6 (struct prefix *p, struct rib *rib) { - return netlink_route_multipath (RTM_NEWROUTE, p, rib, AF_INET6); + { + return netlink_route_multipath (RTM_NEWROUTE, p, rib, AF_INET6); + } } int kernel_delete_ipv6 (struct prefix *p, struct rib *rib) { - return netlink_route_multipath (RTM_DELROUTE, p, rib, AF_INET6); + { + return netlink_route_multipath (RTM_DELROUTE, p, rib, AF_INET6); + } } /* Delete IPv6 route from the kernel. */ diff --git a/zebra/zserv.c b/zebra/zserv.c index 3c850e4259..d745a43d5f 100644 --- a/zebra/zserv.c +++ b/zebra/zserv.c @@ -1298,6 +1298,9 @@ zread_ipv6_add (struct zserv *client, u_short length) ifindices[if_count++] = stream_getl (s); } break; + case ZEBRA_NEXTHOP_BLACKHOLE: + nexthop_blackhole_add (rib); + break; } } -- 2.39.5