2 * IS-IS Rout(e)ing protocol - OpenFabric extensions
4 * Copyright (C) 2018 Christian Franke
6 * This file is part of FreeRangeRouting (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_memory.h"
26 #include "isisd/isis_circuit.h"
27 #include "isisd/isis_misc.h"
28 #include "isisd/isis_adjacency.h"
29 #include "isisd/isis_spf.h"
30 #include "isisd/isis_tlvs.h"
31 #include "isisd/isis_lsp.h"
32 #include "isisd/isis_spf_private.h"
33 #include "isisd/isis_tx_queue.h"
34 #include "isisd/isis_csm.h"
36 DEFINE_MTYPE_STATIC(ISISD
, FABRICD_STATE
, "ISIS OpenFabric")
37 DEFINE_MTYPE_STATIC(ISISD
, FABRICD_NEIGHBOR
, "ISIS OpenFabric Neighbor Entry")
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 /* Code related to maintaining the neighbor lists */
71 struct neighbor_entry
{
72 uint8_t id
[ISIS_SYS_ID_LEN
];
73 struct isis_adjacency
*adj
;
77 static struct neighbor_entry
*neighbor_entry_new(const uint8_t *id
,
78 struct isis_adjacency
*adj
)
80 struct neighbor_entry
*rv
= XMALLOC(MTYPE_FABRICD_NEIGHBOR
, sizeof(*rv
));
82 memcpy(rv
->id
, id
, sizeof(rv
->id
));
88 static void neighbor_entry_del(struct neighbor_entry
*neighbor
)
90 XFREE(MTYPE_FABRICD_NEIGHBOR
, neighbor
);
93 static void neighbor_entry_del_void(void *arg
)
95 neighbor_entry_del((struct neighbor_entry
*)arg
);
98 static void neighbor_lists_clear(struct fabricd
*f
)
100 while (!skiplist_empty(f
->neighbors
))
101 skiplist_delete_first(f
->neighbors
);
103 hash_clean(f
->neighbors_neighbors
, neighbor_entry_del_void
);
106 static unsigned neighbor_entry_hash_key(void *np
)
108 struct neighbor_entry
*n
= np
;
110 return jhash(n
->id
, sizeof(n
->id
), 0x55aa5a5a);
113 static bool neighbor_entry_hash_cmp(const void *a
, const void *b
)
115 const struct neighbor_entry
*na
= a
, *nb
= b
;
117 return memcmp(na
->id
, nb
->id
, sizeof(na
->id
)) == 0;
120 static int neighbor_entry_list_cmp(void *a
, void *b
)
122 struct neighbor_entry
*na
= a
, *nb
= b
;
124 return -memcmp(na
->id
, nb
->id
, sizeof(na
->id
));
127 static struct neighbor_entry
*neighbor_entry_lookup_list(struct skiplist
*list
,
130 struct neighbor_entry n
= {{0}};
132 memcpy(n
.id
, id
, sizeof(n
.id
));
134 struct neighbor_entry
*rv
;
136 if (skiplist_search(list
, &n
, (void**)&rv
))
145 static struct neighbor_entry
*neighbor_entry_lookup_hash(struct hash
*hash
,
148 struct neighbor_entry n
= {{0}};
150 memcpy(n
.id
, id
, sizeof(n
.id
));
152 struct neighbor_entry
*rv
= hash_lookup(hash
, &n
);
154 if (!rv
|| !rv
->present
)
160 static void neighbor_lists_update(struct fabricd
*f
)
162 neighbor_lists_clear(f
);
164 struct listnode
*node
;
165 struct isis_circuit
*circuit
;
167 for (ALL_LIST_ELEMENTS_RO(f
->area
->circuit_list
, node
, circuit
)) {
168 if (circuit
->state
!= C_STATE_UP
)
171 struct isis_adjacency
*adj
= circuit
->u
.p2p
.neighbor
;
173 if (!adj
|| adj
->adj_state
!= ISIS_ADJ_UP
)
176 struct neighbor_entry
*n
= neighbor_entry_new(adj
->sysid
, adj
);
178 skiplist_insert(f
->neighbors
, n
, n
);
181 struct isis_vertex
*v
;
183 for (ALL_QUEUE_ELEMENTS_RO(&f
->spftree
->paths
, node
, v
)) {
184 if (v
->d_N
< 2 || !VTYPE_IS(v
->type
))
190 struct neighbor_entry
*n
= neighbor_entry_new(v
->N
.id
, NULL
);
191 struct neighbor_entry
*inserted
;
192 inserted
= hash_get(f
->neighbors_neighbors
, n
,
194 assert(inserted
== n
);
198 struct fabricd
*fabricd_new(struct isis_area
*area
)
200 struct fabricd
*rv
= XCALLOC(MTYPE_FABRICD_STATE
, sizeof(*rv
));
203 rv
->initial_sync_state
= FABRICD_SYNC_PENDING
;
205 rv
->spftree
= isis_spftree_new(area
);
206 rv
->neighbors
= skiplist_new(0, neighbor_entry_list_cmp
,
207 neighbor_entry_del_void
);
208 rv
->neighbors_neighbors
= hash_create(neighbor_entry_hash_key
,
209 neighbor_entry_hash_cmp
,
210 "Fabricd Neighbors");
212 rv
->tier
= rv
->tier_config
= ISIS_TIER_UNDEFINED
;
216 void fabricd_finish(struct fabricd
*f
)
218 if (f
->initial_sync_timeout
)
219 thread_cancel(f
->initial_sync_timeout
);
221 if (f
->tier_calculation_timer
)
222 thread_cancel(f
->tier_calculation_timer
);
224 if (f
->tier_set_timer
)
225 thread_cancel(f
->tier_set_timer
);
227 isis_spftree_del(f
->spftree
);
228 neighbor_lists_clear(f
);
229 skiplist_free(f
->neighbors
);
230 hash_free(f
->neighbors_neighbors
);
233 static int fabricd_initial_sync_timeout(struct thread
*thread
)
235 struct fabricd
*f
= THREAD_ARG(thread
);
237 zlog_info("OpenFabric: Initial synchronization on %s timed out!",
238 f
->initial_sync_circuit
->interface
->name
);
239 f
->initial_sync_state
= FABRICD_SYNC_PENDING
;
240 f
->initial_sync_circuit
= NULL
;
241 f
->initial_sync_timeout
= NULL
;
245 void fabricd_initial_sync_hello(struct isis_circuit
*circuit
)
247 struct fabricd
*f
= circuit
->area
->fabricd
;
252 if (f
->initial_sync_state
> FABRICD_SYNC_PENDING
)
255 f
->initial_sync_state
= FABRICD_SYNC_STARTED
;
257 long timeout
= 2 * circuit
->hello_interval
[1] * circuit
->hello_multiplier
[1];
259 f
->initial_sync_circuit
= circuit
;
260 if (f
->initial_sync_timeout
)
263 thread_add_timer(master
, fabricd_initial_sync_timeout
, f
,
264 timeout
, &f
->initial_sync_timeout
);
265 f
->initial_sync_start
= monotime(NULL
);
267 zlog_info("OpenFabric: Started initial synchronization with %s on %s",
268 sysid_print(circuit
->u
.p2p
.neighbor
->sysid
),
269 circuit
->interface
->name
);
272 bool fabricd_initial_sync_is_in_progress(struct isis_area
*area
)
274 struct fabricd
*f
= area
->fabricd
;
279 if (f
->initial_sync_state
> FABRICD_SYNC_PENDING
280 && f
->initial_sync_state
< FABRICD_SYNC_COMPLETE
)
286 bool fabricd_initial_sync_is_complete(struct isis_area
*area
)
288 struct fabricd
*f
= area
->fabricd
;
293 return f
->initial_sync_state
== FABRICD_SYNC_COMPLETE
;
296 struct isis_circuit
*fabricd_initial_sync_circuit(struct isis_area
*area
)
298 struct fabricd
*f
= area
->fabricd
;
302 return f
->initial_sync_circuit
;
305 void fabricd_initial_sync_finish(struct isis_area
*area
)
307 struct fabricd
*f
= area
->fabricd
;
312 if (monotime(NULL
) - f
->initial_sync_start
< 5)
315 zlog_info("OpenFabric: Initial synchronization on %s complete.",
316 f
->initial_sync_circuit
->interface
->name
);
317 f
->initial_sync_state
= FABRICD_SYNC_COMPLETE
;
318 f
->initial_sync_circuit
= NULL
;
319 thread_cancel(f
->initial_sync_timeout
);
320 f
->initial_sync_timeout
= NULL
;
323 static void fabricd_bump_tier_calculation_timer(struct fabricd
*f
);
324 static void fabricd_set_tier(struct fabricd
*f
, uint8_t tier
);
326 static uint8_t fabricd_calculate_fabric_tier(struct isis_area
*area
)
328 struct isis_spftree
*local_tree
= fabricd_spftree(area
);
329 struct listnode
*node
;
331 struct isis_vertex
*furthest_t0
= NULL
,
332 *second_furthest_t0
= NULL
;
334 struct isis_vertex
*v
;
336 for (ALL_QUEUE_ELEMENTS_RO(&local_tree
->paths
, node
, v
)) {
337 struct isis_lsp
*lsp
= lsp_for_vertex(local_tree
, v
);
339 if (!lsp
|| !lsp
->tlvs
340 || !lsp
->tlvs
->spine_leaf
341 || !lsp
->tlvs
->spine_leaf
->has_tier
342 || lsp
->tlvs
->spine_leaf
->tier
!= 0)
345 second_furthest_t0
= furthest_t0
;
349 if (!second_furthest_t0
) {
350 zlog_info("OpenFabric: Could not find two T0 routers");
351 return ISIS_TIER_UNDEFINED
;
354 zlog_info("OpenFabric: Found %s as furthest t0 from local system, dist == %"
355 PRIu32
, rawlspid_print(furthest_t0
->N
.id
), furthest_t0
->d_N
);
357 struct isis_spftree
*remote_tree
=
358 isis_run_hopcount_spf(area
, furthest_t0
->N
.id
, NULL
);
360 struct isis_vertex
*furthest_from_remote
=
361 isis_vertex_queue_last(&remote_tree
->paths
);
363 if (!furthest_from_remote
) {
364 zlog_info("OpenFabric: Found no furthest node in remote spf");
365 isis_spftree_del(remote_tree
);
366 return ISIS_TIER_UNDEFINED
;
368 zlog_info("OpenFabric: Found %s as furthest from remote dist == %"
369 PRIu32
, rawlspid_print(furthest_from_remote
->N
.id
),
370 furthest_from_remote
->d_N
);
373 int64_t tier
= furthest_from_remote
->d_N
- furthest_t0
->d_N
;
374 isis_spftree_del(remote_tree
);
376 if (tier
< 0 || tier
>= ISIS_TIER_UNDEFINED
) {
377 zlog_info("OpenFabric: Calculated tier %" PRId64
" seems implausible",
379 return ISIS_TIER_UNDEFINED
;
382 zlog_info("OpenFabric: Calculated %" PRId64
" as tier", tier
);
386 static int fabricd_tier_set_timer(struct thread
*thread
)
388 struct fabricd
*f
= THREAD_ARG(thread
);
389 f
->tier_set_timer
= NULL
;
391 fabricd_set_tier(f
, f
->tier_pending
);
395 static int fabricd_tier_calculation_cb(struct thread
*thread
)
397 struct fabricd
*f
= THREAD_ARG(thread
);
398 uint8_t tier
= ISIS_TIER_UNDEFINED
;
399 f
->tier_calculation_timer
= NULL
;
401 tier
= fabricd_calculate_fabric_tier(f
->area
);
402 if (tier
== ISIS_TIER_UNDEFINED
)
405 zlog_info("OpenFabric: Got tier %" PRIu8
" from algorithm. Arming timer.",
407 f
->tier_pending
= tier
;
408 thread_add_timer(master
, fabricd_tier_set_timer
, f
,
409 f
->area
->lsp_gen_interval
[ISIS_LEVEL2
- 1],
415 static void fabricd_bump_tier_calculation_timer(struct fabricd
*f
)
417 /* Cancel timer if we already know our tier */
418 if (f
->tier
!= ISIS_TIER_UNDEFINED
419 || f
->tier_set_timer
) {
420 if (f
->tier_calculation_timer
) {
421 thread_cancel(f
->tier_calculation_timer
);
422 f
->tier_calculation_timer
= NULL
;
427 /* If we need to calculate the tier, wait some
428 * time for the topology to settle before running
430 if (f
->tier_calculation_timer
) {
431 thread_cancel(f
->tier_calculation_timer
);
432 f
->tier_calculation_timer
= NULL
;
435 thread_add_timer(master
, fabricd_tier_calculation_cb
, f
,
436 2 * f
->area
->lsp_gen_interval
[ISIS_LEVEL2
- 1],
437 &f
->tier_calculation_timer
);
440 static void fabricd_set_tier(struct fabricd
*f
, uint8_t tier
)
445 zlog_info("OpenFabric: Set own tier to %" PRIu8
, tier
);
448 fabricd_bump_tier_calculation_timer(f
);
449 lsp_regenerate_schedule(f
->area
, ISIS_LEVEL2
, 0);
452 void fabricd_run_spf(struct isis_area
*area
)
454 struct fabricd
*f
= area
->fabricd
;
459 isis_run_hopcount_spf(area
, isis
->sysid
, f
->spftree
);
460 neighbor_lists_update(f
);
461 fabricd_bump_tier_calculation_timer(f
);
464 struct isis_spftree
*fabricd_spftree(struct isis_area
*area
)
466 struct fabricd
*f
= area
->fabricd
;
474 void fabricd_configure_tier(struct isis_area
*area
, uint8_t tier
)
476 struct fabricd
*f
= area
->fabricd
;
478 if (!f
|| f
->tier_config
== tier
)
481 f
->tier_config
= tier
;
482 fabricd_set_tier(f
, tier
);
485 uint8_t fabricd_tier(struct isis_area
*area
)
487 struct fabricd
*f
= area
->fabricd
;
490 return ISIS_TIER_UNDEFINED
;
495 int fabricd_write_settings(struct isis_area
*area
, struct vty
*vty
)
497 struct fabricd
*f
= area
->fabricd
;
503 if (f
->tier_config
!= ISIS_TIER_UNDEFINED
) {
504 vty_out(vty
, " fabric-tier %" PRIu8
"\n", f
->tier_config
);
511 static void move_to_queue(struct isis_lsp
*lsp
, struct neighbor_entry
*n
,
512 enum isis_tx_type type
)
516 if (isis
->debugs
& DEBUG_FLOODING
) {
517 zlog_debug("OpenFabric: Adding %s to %s",
518 print_sys_hostname(n
->id
),
519 (type
== TX_LSP_NORMAL
) ? "RF" : "DNR");
523 isis_tx_queue_add(n
->adj
->circuit
->tx_queue
, lsp
, type
);
526 static void mark_neighbor_as_present(struct hash_backet
*backet
, void *arg
)
528 struct neighbor_entry
*n
= backet
->data
;
533 static void handle_firsthops(struct hash_backet
*backet
, void *arg
)
535 struct isis_lsp
*lsp
= arg
;
536 struct fabricd
*f
= lsp
->area
->fabricd
;
537 struct isis_vertex
*vertex
= backet
->data
;
539 struct neighbor_entry
*n
;
541 n
= neighbor_entry_lookup_list(f
->neighbors
, vertex
->N
.id
);
543 if (isis
->debugs
& DEBUG_FLOODING
) {
544 zlog_debug("Removing %s from NL as its in the reverse path",
545 print_sys_hostname(n
->id
));
550 n
= neighbor_entry_lookup_hash(f
->neighbors_neighbors
, vertex
->N
.id
);
552 if (isis
->debugs
& DEBUG_FLOODING
) {
553 zlog_debug("Removing %s from NN as its in the reverse path",
554 print_sys_hostname(n
->id
));
560 static struct isis_lsp
*lsp_for_neighbor(struct fabricd
*f
,
561 struct neighbor_entry
*n
)
563 uint8_t id
[ISIS_SYS_ID_LEN
+ 1] = {0};
565 memcpy(id
, n
->id
, sizeof(n
->id
));
567 struct isis_vertex vertex
= {0};
569 isis_vertex_id_init(&vertex
, id
, VTYPE_NONPSEUDO_TE_IS
);
571 return lsp_for_vertex(f
->spftree
, &vertex
);
574 void fabricd_lsp_flood(struct isis_lsp
*lsp
)
576 struct fabricd
*f
= lsp
->area
->fabricd
;
580 struct neighbor_entry
*n
;
582 /* Mark all elements in NL as present and move T0s into DNR */
583 while (!skiplist_next(f
->neighbors
, NULL
, (void **)&n
, &cursor
)) {
586 struct isis_lsp
*node_lsp
= lsp_for_neighbor(f
, n
);
589 || !node_lsp
->tlvs
->spine_leaf
590 || !node_lsp
->tlvs
->spine_leaf
->has_tier
591 || node_lsp
->tlvs
->spine_leaf
->tier
!= 0) {
595 if (isis
->debugs
& DEBUG_FLOODING
) {
596 zlog_debug("Moving %s to DNR because it's T0",
597 rawlspid_print(node_lsp
->hdr
.lsp_id
));
600 move_to_queue(lsp
, n
, TX_LSP_CIRCUIT_SCOPED
);
603 /* Mark all elements in NN as present */
604 hash_iterate(f
->neighbors_neighbors
, mark_neighbor_as_present
, NULL
);
606 struct isis_vertex
*originator
= isis_find_vertex(&f
->spftree
->paths
,
608 VTYPE_NONPSEUDO_TE_IS
);
610 /* Remove all IS from NL and NN in the shortest path
611 * to the IS that originated the LSP */
613 hash_iterate(originator
->firsthops
, handle_firsthops
, lsp
);
615 /* Iterate over all remaining IS in NL */
617 while (!skiplist_next(f
->neighbors
, NULL
, (void **)&n
, &cursor
)) {
621 struct isis_lsp
*nlsp
= lsp_for_neighbor(f
, n
);
622 if (!nlsp
|| !nlsp
->tlvs
) {
623 if (isis
->debugs
& DEBUG_FLOODING
) {
624 zlog_debug("Moving %s to DNR as it has no LSP",
625 print_sys_hostname(n
->id
));
628 move_to_queue(lsp
, n
, TX_LSP_CIRCUIT_SCOPED
);
632 if (isis
->debugs
& DEBUG_FLOODING
) {
633 zlog_debug("Considering %s from NL...",
634 print_sys_hostname(n
->id
));
637 /* For all neighbors of the NL IS check whether they are present
638 * in NN. If yes, remove from NN and set need_reflood. */
639 bool need_reflood
= false;
640 struct isis_extended_reach
*er
;
641 for (er
= (struct isis_extended_reach
*)nlsp
->tlvs
->extended_reach
.head
;
643 struct neighbor_entry
*nn
;
645 nn
= neighbor_entry_lookup_hash(f
->neighbors_neighbors
,
649 if (isis
->debugs
& DEBUG_FLOODING
) {
650 zlog_debug("Found neighbor %s in NN, removing it from NN and setting reflood.",
651 print_sys_hostname(nn
->id
));
659 move_to_queue(lsp
, n
, need_reflood
?
660 TX_LSP_NORMAL
: TX_LSP_CIRCUIT_SCOPED
);
663 if (isis
->debugs
& DEBUG_FLOODING
) {
664 zlog_debug("OpenFabric: Flooding algorithm complete.");
668 void fabricd_trigger_csnp(struct isis_area
*area
)
670 struct fabricd
*f
= area
->fabricd
;
675 struct listnode
*node
;
676 struct isis_circuit
*circuit
;
678 for (ALL_LIST_ELEMENTS_RO(area
->circuit_list
, node
, circuit
)) {
679 if (!circuit
->t_send_csnp
[1])
682 thread_cancel(circuit
->t_send_csnp
[ISIS_LEVEL2
- 1]);
683 thread_add_timer_msec(master
, send_l2_csnp
, circuit
,
684 isis_jitter(500, CSNP_JITTER
),
685 &circuit
->t_send_csnp
[ISIS_LEVEL2
- 1]);
689 struct list
*fabricd_ip_addrs(struct isis_circuit
*circuit
)
691 if (circuit
->ip_addrs
&& listcount(circuit
->ip_addrs
))
692 return circuit
->ip_addrs
;
694 if (!fabricd
|| !circuit
->area
|| !circuit
->area
->circuit_list
)
697 struct listnode
*node
;
698 struct isis_circuit
*c
;
700 for (ALL_LIST_ELEMENTS_RO(circuit
->area
->circuit_list
, node
, c
)) {
701 if (c
->circ_type
!= CIRCUIT_T_LOOPBACK
)
704 if (!c
->ip_addrs
|| !listcount(c
->ip_addrs
))