2 * IS-IS Rout(e)ing protocol - OpenFabric extensions
4 * Copyright (C) 2018 Christian Franke
6 * This file is part of FRRouting (FRR)
8 * FRR is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation; either version 2, or (at your option) any
13 * FRR is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
18 * You should have received a copy of the GNU General Public License along
19 * with this program; see the file COPYING; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 #include "isisd/fabricd.h"
24 #include "isisd/isisd.h"
25 #include "isisd/isis_circuit.h"
26 #include "isisd/isis_misc.h"
27 #include "isisd/isis_adjacency.h"
28 #include "isisd/isis_spf.h"
29 #include "isisd/isis_tlvs.h"
30 #include "isisd/isis_lsp.h"
31 #include "isisd/isis_spf_private.h"
32 #include "isisd/isis_tx_queue.h"
33 #include "isisd/isis_csm.h"
35 DEFINE_MTYPE_STATIC(ISISD
, FABRICD_STATE
, "ISIS OpenFabric");
36 DEFINE_MTYPE_STATIC(ISISD
, FABRICD_NEIGHBOR
, "ISIS OpenFabric Neighbor Entry");
37 DEFINE_MTYPE_STATIC(ISISD
, FABRICD_FLOODING_INFO
, "ISIS OpenFabric Flooding Log");
39 /* Tracks initial synchronization as per section 2.4
41 * We declare the sync complete once we have seen at least one
42 * CSNP and there are no more LSPs with SSN or SRM set.
44 enum fabricd_sync_state
{
51 struct isis_area
*area
;
53 enum fabricd_sync_state initial_sync_state
;
54 time_t initial_sync_start
;
55 struct isis_circuit
*initial_sync_circuit
;
56 struct thread
*initial_sync_timeout
;
58 struct isis_spftree
*spftree
;
59 struct skiplist
*neighbors
;
60 struct hash
*neighbors_neighbors
;
65 struct thread
*tier_calculation_timer
;
66 struct thread
*tier_set_timer
;
69 bool always_send_csnp
;
72 /* Code related to maintaining the neighbor lists */
74 struct neighbor_entry
{
75 uint8_t id
[ISIS_SYS_ID_LEN
];
76 struct isis_adjacency
*adj
;
80 static struct neighbor_entry
*neighbor_entry_new(const uint8_t *id
,
81 struct isis_adjacency
*adj
)
83 struct neighbor_entry
*rv
= XMALLOC(MTYPE_FABRICD_NEIGHBOR
,
86 memcpy(rv
->id
, id
, sizeof(rv
->id
));
92 static void neighbor_entry_del(struct neighbor_entry
*neighbor
)
94 XFREE(MTYPE_FABRICD_NEIGHBOR
, neighbor
);
97 static void neighbor_entry_del_void(void *arg
)
99 neighbor_entry_del((struct neighbor_entry
*)arg
);
102 static void neighbor_lists_clear(struct fabricd
*f
)
104 while (!skiplist_empty(f
->neighbors
))
105 skiplist_delete_first(f
->neighbors
);
107 hash_clean(f
->neighbors_neighbors
, neighbor_entry_del_void
);
110 static unsigned neighbor_entry_hash_key(const void *np
)
112 const struct neighbor_entry
*n
= np
;
114 return jhash(n
->id
, sizeof(n
->id
), 0x55aa5a5a);
117 static bool neighbor_entry_hash_cmp(const void *a
, const void *b
)
119 const struct neighbor_entry
*na
= a
, *nb
= b
;
121 return memcmp(na
->id
, nb
->id
, sizeof(na
->id
)) == 0;
124 static int neighbor_entry_list_cmp(const void *a
, const void *b
)
126 const struct neighbor_entry
*na
= a
, *nb
= b
;
128 return -memcmp(na
->id
, nb
->id
, sizeof(na
->id
));
131 static struct neighbor_entry
*neighbor_entry_lookup_list(struct skiplist
*list
,
134 struct neighbor_entry n
= { {0} };
136 memcpy(n
.id
, id
, sizeof(n
.id
));
138 struct neighbor_entry
*rv
;
140 if (skiplist_search(list
, &n
, (void**)&rv
))
149 static struct neighbor_entry
*neighbor_entry_lookup_hash(struct hash
*hash
,
152 struct neighbor_entry n
= {{0}};
154 memcpy(n
.id
, id
, sizeof(n
.id
));
156 struct neighbor_entry
*rv
= hash_lookup(hash
, &n
);
158 if (!rv
|| !rv
->present
)
164 static int fabricd_handle_adj_state_change(struct isis_adjacency
*arg
)
166 struct fabricd
*f
= arg
->circuit
->area
->fabricd
;
171 while (!skiplist_empty(f
->neighbors
))
172 skiplist_delete_first(f
->neighbors
);
174 struct listnode
*node
;
175 struct isis_circuit
*circuit
;
177 for (ALL_LIST_ELEMENTS_RO(f
->area
->circuit_list
, node
, circuit
)) {
178 if (circuit
->state
!= C_STATE_UP
)
181 struct isis_adjacency
*adj
= circuit
->u
.p2p
.neighbor
;
183 if (!adj
|| adj
->adj_state
!= ISIS_ADJ_UP
)
186 struct neighbor_entry
*n
= neighbor_entry_new(adj
->sysid
, adj
);
188 skiplist_insert(f
->neighbors
, n
, n
);
194 static void neighbors_neighbors_update(struct fabricd
*f
)
196 hash_clean(f
->neighbors_neighbors
, neighbor_entry_del_void
);
198 struct listnode
*node
;
199 struct isis_vertex
*v
;
201 for (ALL_QUEUE_ELEMENTS_RO(&f
->spftree
->paths
, node
, v
)) {
202 if (v
->d_N
< 2 || !VTYPE_IS(v
->type
))
208 struct neighbor_entry
*n
= neighbor_entry_new(v
->N
.id
, NULL
);
209 struct neighbor_entry
*inserted
;
210 inserted
= hash_get(f
->neighbors_neighbors
, n
,
212 assert(inserted
== n
);
216 struct fabricd
*fabricd_new(struct isis_area
*area
)
218 struct fabricd
*rv
= XCALLOC(MTYPE_FABRICD_STATE
, sizeof(*rv
));
221 rv
->initial_sync_state
= FABRICD_SYNC_PENDING
;
224 isis_spftree_new(area
, &area
->lspdb
[IS_LEVEL_2
- 1],
225 area
->isis
->sysid
, ISIS_LEVEL2
, SPFTREE_IPV4
,
226 SPF_TYPE_FORWARD
, F_SPFTREE_HOPCOUNT_METRIC
);
227 rv
->neighbors
= skiplist_new(0, neighbor_entry_list_cmp
,
228 neighbor_entry_del_void
);
229 rv
->neighbors_neighbors
= hash_create(neighbor_entry_hash_key
,
230 neighbor_entry_hash_cmp
,
231 "Fabricd Neighbors");
233 rv
->tier
= rv
->tier_config
= ISIS_TIER_UNDEFINED
;
235 rv
->csnp_delay
= FABRICD_DEFAULT_CSNP_DELAY
;
239 void fabricd_finish(struct fabricd
*f
)
241 THREAD_OFF(f
->initial_sync_timeout
);
243 THREAD_OFF(f
->tier_calculation_timer
);
245 THREAD_OFF(f
->tier_set_timer
);
247 isis_spftree_del(f
->spftree
);
248 neighbor_lists_clear(f
);
249 skiplist_free(f
->neighbors
);
250 hash_free(f
->neighbors_neighbors
);
253 static void fabricd_initial_sync_timeout(struct thread
*thread
)
255 struct fabricd
*f
= THREAD_ARG(thread
);
257 if (IS_DEBUG_ADJ_PACKETS
)
259 "OpenFabric: Initial synchronization on %s timed out!",
260 f
->initial_sync_circuit
->interface
->name
);
261 f
->initial_sync_state
= FABRICD_SYNC_PENDING
;
262 f
->initial_sync_circuit
= NULL
;
265 void fabricd_initial_sync_hello(struct isis_circuit
*circuit
)
267 struct fabricd
*f
= circuit
->area
->fabricd
;
272 if (f
->initial_sync_state
> FABRICD_SYNC_PENDING
)
275 f
->initial_sync_state
= FABRICD_SYNC_STARTED
;
277 long timeout
= 2 * circuit
->hello_interval
[1] * circuit
->hello_multiplier
[1];
279 f
->initial_sync_circuit
= circuit
;
280 if (f
->initial_sync_timeout
)
283 thread_add_timer(master
, fabricd_initial_sync_timeout
, f
,
284 timeout
, &f
->initial_sync_timeout
);
285 f
->initial_sync_start
= monotime(NULL
);
287 if (IS_DEBUG_ADJ_PACKETS
)
289 "OpenFabric: Started initial synchronization with %s on %s",
290 sysid_print(circuit
->u
.p2p
.neighbor
->sysid
),
291 circuit
->interface
->name
);
294 bool fabricd_initial_sync_is_in_progress(struct isis_area
*area
)
296 struct fabricd
*f
= area
->fabricd
;
301 if (f
->initial_sync_state
> FABRICD_SYNC_PENDING
302 && f
->initial_sync_state
< FABRICD_SYNC_COMPLETE
)
308 bool fabricd_initial_sync_is_complete(struct isis_area
*area
)
310 struct fabricd
*f
= area
->fabricd
;
315 return f
->initial_sync_state
== FABRICD_SYNC_COMPLETE
;
318 struct isis_circuit
*fabricd_initial_sync_circuit(struct isis_area
*area
)
320 struct fabricd
*f
= area
->fabricd
;
324 return f
->initial_sync_circuit
;
327 void fabricd_initial_sync_finish(struct isis_area
*area
)
329 struct fabricd
*f
= area
->fabricd
;
334 if (monotime(NULL
) - f
->initial_sync_start
< 5)
337 zlog_info("OpenFabric: Initial synchronization on %s complete.",
338 f
->initial_sync_circuit
->interface
->name
);
339 f
->initial_sync_state
= FABRICD_SYNC_COMPLETE
;
340 f
->initial_sync_circuit
= NULL
;
341 THREAD_OFF(f
->initial_sync_timeout
);
344 static void fabricd_bump_tier_calculation_timer(struct fabricd
*f
);
345 static void fabricd_set_tier(struct fabricd
*f
, uint8_t tier
);
347 static uint8_t fabricd_calculate_fabric_tier(struct isis_area
*area
)
349 struct isis_spftree
*local_tree
= fabricd_spftree(area
);
350 struct listnode
*node
;
352 struct isis_vertex
*furthest_t0
= NULL
,
353 *second_furthest_t0
= NULL
;
355 struct isis_vertex
*v
;
357 for (ALL_QUEUE_ELEMENTS_RO(&local_tree
->paths
, node
, v
)) {
358 struct isis_lsp
*lsp
= lsp_for_vertex(local_tree
, v
);
360 if (!lsp
|| !lsp
->tlvs
361 || !lsp
->tlvs
->spine_leaf
362 || !lsp
->tlvs
->spine_leaf
->has_tier
363 || lsp
->tlvs
->spine_leaf
->tier
!= 0)
366 second_furthest_t0
= furthest_t0
;
370 if (!second_furthest_t0
) {
371 zlog_info("OpenFabric: Could not find two T0 routers");
372 return ISIS_TIER_UNDEFINED
;
375 zlog_info("OpenFabric: Found %s as furthest t0 from local system, dist == %u", rawlspid_print(furthest_t0
->N
.id
), furthest_t0
->d_N
);
377 struct isis_spftree
*remote_tree
=
378 isis_run_hopcount_spf(area
, furthest_t0
->N
.id
, NULL
);
380 struct isis_vertex
*furthest_from_remote
=
381 isis_vertex_queue_last(&remote_tree
->paths
);
383 if (!furthest_from_remote
) {
384 zlog_info("OpenFabric: Found no furthest node in remote spf");
385 isis_spftree_del(remote_tree
);
386 return ISIS_TIER_UNDEFINED
;
388 zlog_info("OpenFabric: Found %s as furthest from remote dist == %u", rawlspid_print(furthest_from_remote
->N
.id
),
389 furthest_from_remote
->d_N
);
392 int64_t tier
= furthest_from_remote
->d_N
- furthest_t0
->d_N
;
393 isis_spftree_del(remote_tree
);
395 if (tier
< 0 || tier
>= ISIS_TIER_UNDEFINED
) {
396 zlog_info("OpenFabric: Calculated tier %" PRId64
" seems implausible",
398 return ISIS_TIER_UNDEFINED
;
401 zlog_info("OpenFabric: Calculated %" PRId64
" as tier", tier
);
405 static void fabricd_tier_set_timer(struct thread
*thread
)
407 struct fabricd
*f
= THREAD_ARG(thread
);
409 fabricd_set_tier(f
, f
->tier_pending
);
412 static void fabricd_tier_calculation_cb(struct thread
*thread
)
414 struct fabricd
*f
= THREAD_ARG(thread
);
415 uint8_t tier
= ISIS_TIER_UNDEFINED
;
417 tier
= fabricd_calculate_fabric_tier(f
->area
);
418 if (tier
== ISIS_TIER_UNDEFINED
)
421 zlog_info("OpenFabric: Got tier %hhu from algorithm. Arming timer.",
423 f
->tier_pending
= tier
;
424 thread_add_timer(master
, fabricd_tier_set_timer
, f
,
425 f
->area
->lsp_gen_interval
[ISIS_LEVEL2
- 1],
430 static void fabricd_bump_tier_calculation_timer(struct fabricd
*f
)
432 /* Cancel timer if we already know our tier */
433 if (f
->tier
!= ISIS_TIER_UNDEFINED
|| f
->tier_set_timer
) {
434 THREAD_OFF(f
->tier_calculation_timer
);
438 /* If we need to calculate the tier, wait some
439 * time for the topology to settle before running
441 THREAD_OFF(f
->tier_calculation_timer
);
443 thread_add_timer(master
, fabricd_tier_calculation_cb
, f
,
444 2 * f
->area
->lsp_gen_interval
[ISIS_LEVEL2
- 1],
445 &f
->tier_calculation_timer
);
448 static void fabricd_set_tier(struct fabricd
*f
, uint8_t tier
)
453 zlog_info("OpenFabric: Set own tier to %hhu", tier
);
456 fabricd_bump_tier_calculation_timer(f
);
457 lsp_regenerate_schedule(f
->area
, ISIS_LEVEL2
, 0);
460 void fabricd_run_spf(struct isis_area
*area
)
462 struct fabricd
*f
= area
->fabricd
;
467 isis_run_hopcount_spf(area
, area
->isis
->sysid
, f
->spftree
);
468 neighbors_neighbors_update(f
);
469 fabricd_bump_tier_calculation_timer(f
);
472 struct isis_spftree
*fabricd_spftree(struct isis_area
*area
)
474 struct fabricd
*f
= area
->fabricd
;
482 void fabricd_configure_tier(struct isis_area
*area
, uint8_t tier
)
484 struct fabricd
*f
= area
->fabricd
;
486 if (!f
|| f
->tier_config
== tier
)
489 f
->tier_config
= tier
;
490 fabricd_set_tier(f
, tier
);
493 uint8_t fabricd_tier(struct isis_area
*area
)
495 struct fabricd
*f
= area
->fabricd
;
498 return ISIS_TIER_UNDEFINED
;
503 int fabricd_write_settings(struct isis_area
*area
, struct vty
*vty
)
505 struct fabricd
*f
= area
->fabricd
;
511 if (f
->tier_config
!= ISIS_TIER_UNDEFINED
) {
512 vty_out(vty
, " fabric-tier %hhu\n", f
->tier_config
);
516 if (f
->csnp_delay
!= FABRICD_DEFAULT_CSNP_DELAY
517 || f
->always_send_csnp
) {
518 vty_out(vty
, " triggered-csnp-delay %d%s\n", f
->csnp_delay
,
519 f
->always_send_csnp
? " always" : "");
525 static void move_to_queue(struct isis_lsp
*lsp
, struct neighbor_entry
*n
,
526 enum isis_tx_type type
, struct isis_circuit
*circuit
)
530 if (n
->adj
&& n
->adj
->circuit
== circuit
)
533 if (IS_DEBUG_FLOODING
) {
534 zlog_debug("OpenFabric: Adding %s to %s",
535 print_sys_hostname(n
->id
),
536 (type
== TX_LSP_NORMAL
) ? "RF" : "DNR");
540 isis_tx_queue_add(n
->adj
->circuit
->tx_queue
, lsp
, type
);
542 uint8_t *neighbor_id
= XMALLOC(MTYPE_FABRICD_FLOODING_INFO
,
545 memcpy(neighbor_id
, n
->id
, sizeof(n
->id
));
546 listnode_add(lsp
->flooding_neighbors
[type
], neighbor_id
);
549 static void mark_neighbor_as_present(struct hash_bucket
*bucket
, void *arg
)
551 struct neighbor_entry
*n
= bucket
->data
;
556 static void handle_firsthops(struct hash_bucket
*bucket
, void *arg
)
558 struct isis_lsp
*lsp
= arg
;
559 struct fabricd
*f
= lsp
->area
->fabricd
;
560 struct isis_vertex
*vertex
= bucket
->data
;
562 struct neighbor_entry
*n
;
564 n
= neighbor_entry_lookup_list(f
->neighbors
, vertex
->N
.id
);
566 if (IS_DEBUG_FLOODING
) {
567 zlog_debug("Removing %s from NL as its in the reverse path",
568 print_sys_hostname(n
->id
));
573 n
= neighbor_entry_lookup_hash(f
->neighbors_neighbors
, vertex
->N
.id
);
575 if (IS_DEBUG_FLOODING
) {
576 zlog_debug("Removing %s from NN as its in the reverse path",
577 print_sys_hostname(n
->id
));
583 static struct isis_lsp
*lsp_for_neighbor(struct fabricd
*f
,
584 struct neighbor_entry
*n
)
586 uint8_t id
[ISIS_SYS_ID_LEN
+ 1] = {0};
588 memcpy(id
, n
->id
, sizeof(n
->id
));
590 struct isis_vertex vertex
= {0};
592 isis_vertex_id_init(&vertex
, id
, VTYPE_NONPSEUDO_TE_IS
);
594 return lsp_for_vertex(f
->spftree
, &vertex
);
597 static void fabricd_free_lsp_flooding_info(void *val
)
599 XFREE(MTYPE_FABRICD_FLOODING_INFO
, val
);
602 static void fabricd_lsp_reset_flooding_info(struct isis_lsp
*lsp
,
603 struct isis_circuit
*circuit
)
605 lsp
->flooding_time
= time(NULL
);
607 XFREE(MTYPE_FABRICD_FLOODING_INFO
, lsp
->flooding_interface
);
608 for (enum isis_tx_type type
= TX_LSP_NORMAL
;
609 type
<= TX_LSP_CIRCUIT_SCOPED
; type
++) {
610 if (lsp
->flooding_neighbors
[type
]) {
611 list_delete_all_node(lsp
->flooding_neighbors
[type
]);
615 lsp
->flooding_neighbors
[type
] = list_new();
616 lsp
->flooding_neighbors
[type
]->del
=
617 fabricd_free_lsp_flooding_info
;
621 lsp
->flooding_interface
= XSTRDUP(MTYPE_FABRICD_FLOODING_INFO
,
622 circuit
->interface
->name
);
625 lsp
->flooding_circuit_scoped
= false;
628 void fabricd_lsp_flood(struct isis_lsp
*lsp
, struct isis_circuit
*circuit
)
630 struct fabricd
*f
= lsp
->area
->fabricd
;
633 fabricd_lsp_reset_flooding_info(lsp
, circuit
);
636 struct neighbor_entry
*n
;
638 /* Mark all elements in NL as present */
639 while (!skiplist_next(f
->neighbors
, NULL
, (void **)&n
, &cursor
))
642 /* Mark all elements in NN as present */
643 hash_iterate(f
->neighbors_neighbors
, mark_neighbor_as_present
, NULL
);
645 struct isis_vertex
*originator
=
646 isis_find_vertex(&f
->spftree
->paths
,
648 VTYPE_NONPSEUDO_TE_IS
);
650 /* Remove all IS from NL and NN in the shortest path
651 * to the IS that originated the LSP */
653 hash_iterate(originator
->firsthops
, handle_firsthops
, lsp
);
655 /* Iterate over all remaining IS in NL */
657 while (!skiplist_next(f
->neighbors
, NULL
, (void **)&n
, &cursor
)) {
661 struct isis_lsp
*nlsp
= lsp_for_neighbor(f
, n
);
662 if (!nlsp
|| !nlsp
->tlvs
) {
663 if (IS_DEBUG_FLOODING
) {
664 zlog_debug("Moving %s to DNR as it has no LSP",
665 print_sys_hostname(n
->id
));
668 move_to_queue(lsp
, n
, TX_LSP_CIRCUIT_SCOPED
, circuit
);
672 if (IS_DEBUG_FLOODING
) {
673 zlog_debug("Considering %s from NL...",
674 print_sys_hostname(n
->id
));
677 /* For all neighbors of the NL IS check whether they are present
678 * in NN. If yes, remove from NN and set need_reflood. */
679 bool need_reflood
= false;
680 struct isis_extended_reach
*er
;
681 for (er
= (struct isis_extended_reach
*)nlsp
->tlvs
->extended_reach
.head
;
683 struct neighbor_entry
*nn
;
685 nn
= neighbor_entry_lookup_hash(f
->neighbors_neighbors
,
689 if (IS_DEBUG_FLOODING
) {
690 zlog_debug("Found neighbor %s in NN, removing it from NN and setting reflood.",
691 print_sys_hostname(nn
->id
));
699 move_to_queue(lsp
, n
, need_reflood
?
700 TX_LSP_NORMAL
: TX_LSP_CIRCUIT_SCOPED
,
704 if (IS_DEBUG_FLOODING
) {
705 zlog_debug("OpenFabric: Flooding algorithm complete.");
709 void fabricd_trigger_csnp(struct isis_area
*area
, bool circuit_scoped
)
711 struct fabricd
*f
= area
->fabricd
;
716 if (!circuit_scoped
&& !f
->always_send_csnp
)
719 struct listnode
*node
;
720 struct isis_circuit
*circuit
;
722 for (ALL_LIST_ELEMENTS_RO(area
->circuit_list
, node
, circuit
)) {
723 if (!circuit
->t_send_csnp
[1])
726 THREAD_OFF(circuit
->t_send_csnp
[ISIS_LEVEL2
- 1]);
727 thread_add_timer_msec(master
, send_l2_csnp
, circuit
,
728 isis_jitter(f
->csnp_delay
, CSNP_JITTER
),
729 &circuit
->t_send_csnp
[ISIS_LEVEL2
- 1]);
733 struct list
*fabricd_ip_addrs(struct isis_circuit
*circuit
)
735 if (listcount(circuit
->ip_addrs
))
736 return circuit
->ip_addrs
;
738 if (!fabricd
|| !circuit
->area
|| !circuit
->area
->circuit_list
)
741 struct listnode
*node
;
742 struct isis_circuit
*c
;
744 for (ALL_LIST_ELEMENTS_RO(circuit
->area
->circuit_list
, node
, c
)) {
745 if (c
->circ_type
!= CIRCUIT_T_LOOPBACK
)
748 if (!listcount(c
->ip_addrs
))
757 void fabricd_lsp_free(struct isis_lsp
*lsp
)
759 XFREE(MTYPE_FABRICD_FLOODING_INFO
, lsp
->flooding_interface
);
760 for (enum isis_tx_type type
= TX_LSP_NORMAL
;
761 type
<= TX_LSP_CIRCUIT_SCOPED
; type
++) {
762 if (!lsp
->flooding_neighbors
[type
])
765 list_delete(&lsp
->flooding_neighbors
[type
]);
769 void fabricd_update_lsp_no_flood(struct isis_lsp
*lsp
,
770 struct isis_circuit
*circuit
)
775 fabricd_lsp_reset_flooding_info(lsp
, circuit
);
776 lsp
->flooding_circuit_scoped
= true;
779 void fabricd_configure_triggered_csnp(struct isis_area
*area
, int delay
,
780 bool always_send_csnp
)
782 struct fabricd
*f
= area
->fabricd
;
787 f
->csnp_delay
= delay
;
788 f
->always_send_csnp
= always_send_csnp
;
791 void fabricd_init(void)
793 hook_register(isis_adj_state_change_hook
,
794 fabricd_handle_adj_state_change
);