summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--isisd/fabricd.c7
-rw-r--r--isisd/isis_spf.c85
-rw-r--r--isisd/isis_spf.h8
-rw-r--r--isisd/isis_spf_private.h1
-rw-r--r--tests/isisd/test_isis_spf.c32
-rw-r--r--tests/isisd/test_isis_spf.in3
-rw-r--r--tests/isisd/test_isis_spf.refout84
7 files changed, 207 insertions, 13 deletions
diff --git a/isisd/fabricd.c b/isisd/fabricd.c
index 2953ee681c..1a081bbea6 100644
--- a/isisd/fabricd.c
+++ b/isisd/fabricd.c
@@ -221,9 +221,10 @@ struct fabricd *fabricd_new(struct isis_area *area)
rv->area = area;
rv->initial_sync_state = FABRICD_SYNC_PENDING;
- rv->spftree = isis_spftree_new(area, &area->lspdb[IS_LEVEL_2 - 1],
- area->isis->sysid, ISIS_LEVEL2,
- SPFTREE_IPV4, F_SPFTREE_HOPCOUNT_METRIC);
+ rv->spftree =
+ isis_spftree_new(area, &area->lspdb[IS_LEVEL_2 - 1],
+ area->isis->sysid, ISIS_LEVEL2, SPFTREE_IPV4,
+ SPF_TYPE_FORWARD, F_SPFTREE_HOPCOUNT_METRIC);
rv->neighbors = skiplist_new(0, neighbor_entry_list_cmp,
neighbor_entry_del_void);
rv->neighbors_neighbors = hash_create(neighbor_entry_hash_key,
diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c
index 19a373791e..dd0a6ec824 100644
--- a/isisd/isis_spf.c
+++ b/isisd/isis_spf.c
@@ -276,7 +276,8 @@ static void isis_spf_adj_free(void *arg)
struct isis_spftree *isis_spftree_new(struct isis_area *area,
struct lspdb_head *lspdb,
const uint8_t *sysid, int level,
- enum spf_tree_id tree_id, uint8_t flags)
+ enum spf_tree_id tree_id,
+ enum spf_type type, uint8_t flags)
{
struct isis_spftree *tree;
@@ -293,6 +294,7 @@ struct isis_spftree *isis_spftree_new(struct isis_area *area,
tree->last_run_monotime = 0;
tree->last_run_duration = 0;
tree->runcount = 0;
+ tree->type = type;
memcpy(tree->sysid, sysid, ISIS_SYS_ID_LEN);
tree->level = level;
tree->tree_id = tree_id;
@@ -336,9 +338,10 @@ void spftree_area_init(struct isis_area *area)
if (area->spftree[tree][level - 1])
continue;
- area->spftree[tree][level - 1] = isis_spftree_new(
- area, &area->lspdb[level - 1],
- area->isis->sysid, level, tree, 0);
+ area->spftree[tree][level - 1] =
+ isis_spftree_new(area, &area->lspdb[level - 1],
+ area->isis->sysid, level, tree,
+ SPF_TYPE_FORWARD, 0);
}
}
}
@@ -956,6 +959,76 @@ static void isis_spf_preload_tent(struct isis_spftree *spftree,
}
}
+struct spf_adj_find_reverse_metric_args {
+ const uint8_t *id_self;
+ uint32_t reverse_metric;
+};
+
+static int spf_adj_find_reverse_metric_cb(const uint8_t *id, uint32_t metric,
+ bool oldmetric,
+ struct isis_ext_subtlvs *subtlvs,
+ void *arg)
+{
+ struct spf_adj_find_reverse_metric_args *args = arg;
+
+ if (memcmp(id, args->id_self, ISIS_SYS_ID_LEN))
+ return LSP_ITER_CONTINUE;
+
+ args->reverse_metric = metric;
+
+ return LSP_ITER_STOP;
+}
+
+/*
+ * Change all SPF adjacencies to use the link cost in the direction from the
+ * next hop back towards root in place of the link cost in the direction away
+ * from root towards the next hop.
+ */
+static void spf_adj_get_reverse_metrics(struct isis_spftree *spftree)
+{
+ struct isis_spf_adj *sadj;
+ struct listnode *node, *nnode;
+
+ for (ALL_LIST_ELEMENTS(spftree->sadj_list, node, nnode, sadj)) {
+ uint8_t lspid[ISIS_SYS_ID_LEN + 2];
+ struct isis_lsp *lsp_adj;
+ const uint8_t *id_self;
+ struct spf_adj_find_reverse_metric_args args;
+
+ /* Skip pseudonodes. */
+ if (LSP_PSEUDO_ID(sadj->id))
+ continue;
+
+ /* Find LSP of the corresponding adjacency. */
+ memcpy(lspid, sadj->id, ISIS_SYS_ID_LEN);
+ LSP_PSEUDO_ID(lspid) = 0;
+ LSP_FRAGMENT(lspid) = 0;
+ lsp_adj = lsp_search(spftree->lspdb, lspid);
+ if (lsp_adj == NULL || lsp_adj->hdr.rem_lifetime == 0) {
+ /* Delete one-way adjacency. */
+ listnode_delete(spftree->sadj_list, sadj);
+ continue;
+ }
+
+ /* Find root node in the LSP of the adjacent router. */
+ if (CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST))
+ id_self = sadj->lan.desig_is_id;
+ else
+ id_self = spftree->sysid;
+ args.id_self = id_self;
+ args.reverse_metric = UINT32_MAX;
+ isis_lsp_iterate_is_reach(lsp_adj, spftree->mtid,
+ spf_adj_find_reverse_metric_cb,
+ &args);
+ if (args.reverse_metric == UINT32_MAX) {
+ /* Delete one-way adjacency. */
+ listnode_delete(spftree->sadj_list, sadj);
+ continue;
+ }
+ sadj->metric = args.reverse_metric;
+ }
+}
+
static void spf_adj_list_parse_tlv(struct isis_spftree *spftree,
struct list *adj_list, const uint8_t *id,
const uint8_t *desig_is_id,
@@ -1092,6 +1165,9 @@ static void isis_spf_build_adj_list(struct isis_spftree *spftree,
if (!CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES))
list_delete(&adj_list);
+
+ if (spftree->type == SPF_TYPE_REVERSE)
+ spf_adj_get_reverse_metrics(spftree);
}
/*
@@ -1181,6 +1257,7 @@ struct isis_spftree *isis_run_hopcount_spf(struct isis_area *area,
if (!spftree)
spftree = isis_spftree_new(area, &area->lspdb[IS_LEVEL_2 - 1],
sysid, ISIS_LEVEL2, SPFTREE_IPV4,
+ SPF_TYPE_FORWARD,
F_SPFTREE_HOPCOUNT_METRIC);
init_spt(spftree, ISIS_MT_IPV4_UNICAST);
diff --git a/isisd/isis_spf.h b/isisd/isis_spf.h
index 61a107bea2..b2dc23496f 100644
--- a/isisd/isis_spf.h
+++ b/isisd/isis_spf.h
@@ -26,6 +26,11 @@
struct isis_spftree;
+enum spf_type {
+ SPF_TYPE_FORWARD = 1,
+ SPF_TYPE_REVERSE,
+};
+
struct isis_spf_adj {
uint8_t id[ISIS_SYS_ID_LEN + 1];
struct isis_adjacency *adj;
@@ -43,7 +48,8 @@ struct isis_spf_adj {
struct isis_spftree *isis_spftree_new(struct isis_area *area,
struct lspdb_head *lspdb,
const uint8_t *sysid, int level,
- enum spf_tree_id tree_id, uint8_t flags);
+ enum spf_tree_id tree_id,
+ enum spf_type type, uint8_t flags);
void isis_spf_invalidate_routes(struct isis_spftree *tree);
void isis_spf_verify_routes(struct isis_area *area,
struct isis_spftree **trees);
diff --git a/isisd/isis_spf_private.h b/isisd/isis_spf_private.h
index 6bdf900d1c..1e61bf0f48 100644
--- a/isisd/isis_spf_private.h
+++ b/isisd/isis_spf_private.h
@@ -314,6 +314,7 @@ struct isis_spftree {
time_t last_run_monotime; /* last run as monotime for scheduling */
time_t last_run_duration; /* last run duration in msec */
+ enum spf_type type;
uint8_t sysid[ISIS_SYS_ID_LEN];
uint16_t mtid;
int family;
diff --git a/tests/isisd/test_isis_spf.c b/tests/isisd/test_isis_spf.c
index 4e1d7b050f..dae906b956 100644
--- a/tests/isisd/test_isis_spf.c
+++ b/tests/isisd/test_isis_spf.c
@@ -38,6 +38,7 @@
enum test_type {
TEST_SPF = 1,
+ TEST_REVERSE_SPF,
};
#define F_DISPLAY_LSPDB 0x01
@@ -51,13 +52,15 @@ static struct isis *isis;
static void test_run_spf(struct vty *vty, const struct isis_topology *topology,
const struct isis_test_node *root,
struct isis_area *area, struct lspdb_head *lspdb,
- int level, int tree)
+ int level, int tree, bool reverse)
{
struct isis_spftree *spftree;
+ enum spf_type spf_type;
/* Run SPF. */
+ spf_type = reverse ? SPF_TYPE_REVERSE : SPF_TYPE_FORWARD;
spftree = isis_spftree_new(area, lspdb, root->sysid, level, tree,
- F_SPFTREE_NO_ADJACENCIES);
+ spf_type, F_SPFTREE_NO_ADJACENCIES);
isis_run_spf(spftree);
/* Print the SPT and the corresponding routing table. */
@@ -110,7 +113,12 @@ static int test_run(struct vty *vty, const struct isis_topology *topology,
case TEST_SPF:
test_run_spf(vty, topology, root, area,
&area->lspdb[level - 1], level,
- tree);
+ tree, false);
+ break;
+ case TEST_REVERSE_SPF:
+ test_run_spf(vty, topology, root, area,
+ &area->lspdb[level - 1], level,
+ tree, true);
break;
}
}
@@ -126,7 +134,11 @@ static int test_run(struct vty *vty, const struct isis_topology *topology,
}
DEFUN(test_isis, test_isis_cmd,
- "test isis topology (1-13) root HOSTNAME spf\
+ "test isis topology (1-13) root HOSTNAME\
+ <\
+ spf\
+ |reverse-spf\
+ >\
[display-lspdb] [<ipv4-only|ipv6-only>] [<level-1-only|level-2-only>]",
"Test command\n"
"IS-IS routing protocol\n"
@@ -135,6 +147,7 @@ DEFUN(test_isis, test_isis_cmd,
"SPF root\n"
"SPF root hostname\n"
"Normal Shortest Path First\n"
+ "Reverse Shortest Path First\n"
"Display the LSPDB\n"
"Do IPv4 processing only\n"
"Do IPv6 processing only\n"
@@ -144,6 +157,7 @@ DEFUN(test_isis, test_isis_cmd,
uint16_t topology_number;
const struct isis_topology *topology;
const struct isis_test_node *root;
+ enum test_type test_type;
uint8_t flags = 0;
int idx = 0;
@@ -165,6 +179,14 @@ DEFUN(test_isis, test_isis_cmd,
return CMD_WARNING;
}
+ /* Parse test information. */
+ if (argv_find(argv, argc, "spf", &idx))
+ test_type = TEST_SPF;
+ else if (argv_find(argv, argc, "reverse-spf", &idx))
+ test_type = TEST_REVERSE_SPF;
+ else
+ return CMD_WARNING;
+
/* Parse control flags. */
if (argv_find(argv, argc, "display-lspdb", &idx))
SET_FLAG(flags, F_DISPLAY_LSPDB);
@@ -177,7 +199,7 @@ DEFUN(test_isis, test_isis_cmd,
else if (argv_find(argv, argc, "level-2-only", &idx))
SET_FLAG(flags, F_LEVEL2_ONLY);
- return test_run(vty, topology, root, TEST_SPF, flags);
+ return test_run(vty, topology, root, test_type, flags);
}
static void vty_do_exit(int isexit)
diff --git a/tests/isisd/test_isis_spf.in b/tests/isisd/test_isis_spf.in
index 28d3c59e1e..d9a61782e9 100644
--- a/tests/isisd/test_isis_spf.in
+++ b/tests/isisd/test_isis_spf.in
@@ -11,3 +11,6 @@ test isis topology 10 root rt1 spf
test isis topology 11 root rt1 spf
test isis topology 12 root rt1 spf ipv4-only
test isis topology 13 root rt1 spf ipv4-only
+
+test isis topology 4 root rt1 reverse-spf ipv4-only
+test isis topology 11 root rt1 reverse-spf
diff --git a/tests/isisd/test_isis_spf.refout b/tests/isisd/test_isis_spf.refout
index ee82926197..ed0569947c 100644
--- a/tests/isisd/test_isis_spf.refout
+++ b/tests/isisd/test_isis_spf.refout
@@ -615,5 +615,89 @@ IS-IS L1 IPv4 routing table:
10.0.255.6/32 30 - rt3 -
10.0.255.7/32 40 - rt3 -
+test#
+test# test isis topology 4 root rt1 reverse-spf ipv4-only
+IS-IS paths to level-1 routers that speak IP
+Vertex Type Metric Next-Hop Interface Parent
+rt1
+10.0.255.1/32 IP internal 0 rt1(4)
+rt2 TE-IS 10 rt2 - rt1(4)
+rt3 TE-IS 10 rt3 - rt1(4)
+rt4 TE-IS 20 rt2 - rt2(4)
+rt5 TE-IS 20 rt3 - rt3(4)
+10.0.255.2/32 IP TE 20 rt2 - rt2(4)
+10.0.255.3/32 IP TE 20 rt3 - rt3(4)
+rt6 TE-IS 30 rt2 - rt4(4)
+rt7 TE-IS 30 rt3 - rt5(4)
+10.0.255.4/32 IP TE 30 rt2 - rt4(4)
+10.0.255.5/32 IP TE 30 rt3 - rt5(4)
+rt8 TE-IS 40 rt2 - rt6(4)
+10.0.255.6/32 IP TE 40 rt2 - rt6(4)
+10.0.255.7/32 IP TE 40 rt3 - rt7(4)
+10.0.255.8/32 IP TE 50 rt2 - rt8(4)
+
+IS-IS L1 IPv4 routing table:
+
+ Prefix Metric Interface Nexthop Label(s)
+ -----------------------------------------------------
+ 10.0.255.2/32 20 - rt2 -
+ 10.0.255.3/32 20 - rt3 -
+ 10.0.255.4/32 30 - rt2 -
+ 10.0.255.5/32 30 - rt3 -
+ 10.0.255.6/32 40 - rt2 -
+ 10.0.255.7/32 40 - rt3 -
+ 10.0.255.8/32 50 - rt2 -
+
+test# test isis topology 11 root rt1 reverse-spf
+IS-IS paths to level-1 routers that speak IP
+Vertex Type Metric Next-Hop Interface Parent
+rt1
+10.0.255.1/32 IP internal 0 rt1(4)
+rt2 TE-IS 10 rt1(4)
+rt3 TE-IS 10 rt3 - rt1(4)
+rt2 pseudo_TE-IS 20 rt3 - rt3(4)
+rt4 TE-IS 20 rt2(4)
+rt5 TE-IS 20 rt3 - rt3(4)
+10.0.255.2/32 IP TE 20 rt2(4)
+10.0.255.3/32 IP TE 20 rt3 - rt3(4)
+rt6 TE-IS 30 rt3 - rt4(4)
+ rt5(4)
+10.0.255.4/32 IP TE 30 rt4(4)
+10.0.255.5/32 IP TE 30 rt3 - rt5(4)
+10.0.255.6/32 IP TE 40 rt3 - rt6(4)
+
+IS-IS L1 IPv4 routing table:
+
+ Prefix Metric Interface Nexthop Label(s)
+ -----------------------------------------------------
+ 10.0.255.3/32 20 - rt3 -
+ 10.0.255.5/32 30 - rt3 -
+ 10.0.255.6/32 40 - rt3 -
+
+IS-IS paths to level-1 routers that speak IPv6
+Vertex Type Metric Next-Hop Interface Parent
+rt1
+2001:db8::1/128 IP6 internal 0 rt1(4)
+rt2 TE-IS 10 rt1(4)
+rt3 TE-IS 10 rt3 - rt1(4)
+rt2 pseudo_TE-IS 20 rt3 - rt3(4)
+rt4 TE-IS 20 rt2(4)
+rt5 TE-IS 20 rt3 - rt3(4)
+2001:db8::2/128 IP6 internal 20 rt2(4)
+2001:db8::3/128 IP6 internal 20 rt3 - rt3(4)
+rt6 TE-IS 30 rt3 - rt4(4)
+ rt5(4)
+2001:db8::4/128 IP6 internal 30 rt4(4)
+2001:db8::5/128 IP6 internal 30 rt3 - rt5(4)
+2001:db8::6/128 IP6 internal 40 rt3 - rt6(4)
+
+IS-IS L1 IPv6 routing table:
+
+ Prefix Metric Interface Nexthop Label(s)
+ -------------------------------------------------------
+ 2001:db8::3/128 20 - rt3 -
+ 2001:db8::5/128 30 - rt3 -
+ 2001:db8::6/128 40 - rt3 -
+
test#
end.