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"
35 DEFINE_MTYPE_STATIC(ISISD
, FABRICD_STATE
, "ISIS OpenFabric")
36 DEFINE_MTYPE_STATIC(ISISD
, FABRICD_NEIGHBOR
, "ISIS OpenFabric Neighbor Entry")
38 /* Tracks initial synchronization as per section 2.4
40 * We declare the sync complete once we have seen at least one
41 * CSNP and there are no more LSPs with SSN or SRM set.
43 enum fabricd_sync_state
{
50 struct isis_area
*area
;
52 enum fabricd_sync_state initial_sync_state
;
53 time_t initial_sync_start
;
54 struct isis_circuit
*initial_sync_circuit
;
55 struct thread
*initial_sync_timeout
;
57 struct isis_spftree
*spftree
;
58 struct skiplist
*neighbors
;
59 struct hash
*neighbors_neighbors
;
64 struct thread
*tier_calculation_timer
;
65 struct thread
*tier_set_timer
;
68 /* Code related to maintaining the neighbor lists */
70 struct neighbor_entry
{
71 struct isis_vertex
*vertex
;
75 static struct neighbor_entry
*neighbor_entry_new(struct isis_vertex
*vertex
)
77 struct neighbor_entry
*rv
= XMALLOC(MTYPE_FABRICD_NEIGHBOR
, sizeof(*rv
));
83 static void neighbor_entry_del(struct neighbor_entry
*neighbor
)
85 XFREE(MTYPE_FABRICD_NEIGHBOR
, neighbor
);
88 static void neighbor_entry_del_void(void *arg
)
90 neighbor_entry_del((struct neighbor_entry
*)arg
);
93 static void neighbor_lists_clear(struct fabricd
*f
)
95 while (!skiplist_empty(f
->neighbors
))
96 skiplist_delete_first(f
->neighbors
);
98 hash_clean(f
->neighbors_neighbors
, neighbor_entry_del_void
);
101 static unsigned neighbor_entry_hash_key(void *np
)
103 struct neighbor_entry
*n
= np
;
105 return jhash(n
->vertex
->N
.id
, ISIS_SYS_ID_LEN
, 0x55aa5a5a);
108 static bool neighbor_entry_hash_cmp(const void *a
, const void *b
)
110 const struct neighbor_entry
*na
= a
, *nb
= b
;
112 return memcmp(na
->vertex
->N
.id
, nb
->vertex
->N
.id
, ISIS_SYS_ID_LEN
) == 0;
115 static int neighbor_entry_list_cmp(void *a
, void *b
)
117 struct neighbor_entry
*na
= a
, *nb
= b
;
119 return -memcmp(na
->vertex
->N
.id
, nb
->vertex
->N
.id
, ISIS_SYS_ID_LEN
);
122 static struct neighbor_entry
*neighbor_entry_lookup_list(struct skiplist
*list
,
125 struct isis_vertex querier
;
126 isis_vertex_id_init(&querier
, id
, VTYPE_NONPSEUDO_TE_IS
);
128 struct neighbor_entry n
= {
132 struct neighbor_entry
*rv
;
134 if (skiplist_search(list
, &n
, (void**)&rv
))
143 static struct neighbor_entry
*neighbor_entry_lookup_hash(struct hash
*hash
,
146 struct isis_vertex querier
;
147 isis_vertex_id_init(&querier
, id
, VTYPE_NONPSEUDO_TE_IS
);
149 struct neighbor_entry n
= {
153 struct neighbor_entry
*rv
= hash_lookup(hash
, &n
);
155 if (!rv
|| !rv
->present
)
161 static void neighbor_lists_update(struct fabricd
*f
)
163 neighbor_lists_clear(f
);
165 struct listnode
*node
;
166 struct isis_vertex
*v
;
168 for (ALL_QUEUE_ELEMENTS_RO(&f
->spftree
->paths
, node
, v
)) {
169 if (!v
->d_N
|| !VTYPE_IS(v
->type
))
175 struct neighbor_entry
*n
= neighbor_entry_new(v
);
177 skiplist_insert(f
->neighbors
, n
, n
);
179 struct neighbor_entry
*inserted
;
180 inserted
= hash_get(f
->neighbors_neighbors
, n
, hash_alloc_intern
);
181 assert(inserted
== n
);
186 struct fabricd
*fabricd_new(struct isis_area
*area
)
188 struct fabricd
*rv
= XCALLOC(MTYPE_FABRICD_STATE
, sizeof(*rv
));
191 rv
->initial_sync_state
= FABRICD_SYNC_PENDING
;
193 rv
->spftree
= isis_spftree_new(area
);
194 rv
->neighbors
= skiplist_new(0, neighbor_entry_list_cmp
,
195 neighbor_entry_del_void
);
196 rv
->neighbors_neighbors
= hash_create(neighbor_entry_hash_key
,
197 neighbor_entry_hash_cmp
,
198 "Fabricd Neighbors");
200 rv
->tier
= rv
->tier_config
= ISIS_TIER_UNDEFINED
;
204 void fabricd_finish(struct fabricd
*f
)
206 if (f
->initial_sync_timeout
)
207 thread_cancel(f
->initial_sync_timeout
);
209 if (f
->tier_calculation_timer
)
210 thread_cancel(f
->tier_calculation_timer
);
212 if (f
->tier_set_timer
)
213 thread_cancel(f
->tier_set_timer
);
215 isis_spftree_del(f
->spftree
);
216 neighbor_lists_clear(f
);
217 skiplist_free(f
->neighbors
);
218 hash_free(f
->neighbors_neighbors
);
221 static int fabricd_initial_sync_timeout(struct thread
*thread
)
223 struct fabricd
*f
= THREAD_ARG(thread
);
225 zlog_info("OpenFabric: Initial synchronization on %s timed out!",
226 f
->initial_sync_circuit
->interface
->name
);
227 f
->initial_sync_state
= FABRICD_SYNC_PENDING
;
228 f
->initial_sync_circuit
= NULL
;
229 f
->initial_sync_timeout
= NULL
;
233 void fabricd_initial_sync_hello(struct isis_circuit
*circuit
)
235 struct fabricd
*f
= circuit
->area
->fabricd
;
240 if (f
->initial_sync_state
> FABRICD_SYNC_PENDING
)
243 f
->initial_sync_state
= FABRICD_SYNC_STARTED
;
245 long timeout
= 2 * circuit
->hello_interval
[1] * circuit
->hello_multiplier
[1];
247 f
->initial_sync_circuit
= circuit
;
248 if (f
->initial_sync_timeout
)
251 thread_add_timer(master
, fabricd_initial_sync_timeout
, f
,
252 timeout
, &f
->initial_sync_timeout
);
253 f
->initial_sync_start
= monotime(NULL
);
255 zlog_info("OpenFabric: Started initial synchronization with %s on %s",
256 sysid_print(circuit
->u
.p2p
.neighbor
->sysid
),
257 circuit
->interface
->name
);
260 bool fabricd_initial_sync_is_in_progress(struct isis_area
*area
)
262 struct fabricd
*f
= area
->fabricd
;
267 if (f
->initial_sync_state
> FABRICD_SYNC_PENDING
268 && f
->initial_sync_state
< FABRICD_SYNC_COMPLETE
)
274 bool fabricd_initial_sync_is_complete(struct isis_area
*area
)
276 struct fabricd
*f
= area
->fabricd
;
281 return f
->initial_sync_state
== FABRICD_SYNC_COMPLETE
;
284 struct isis_circuit
*fabricd_initial_sync_circuit(struct isis_area
*area
)
286 struct fabricd
*f
= area
->fabricd
;
290 return f
->initial_sync_circuit
;
293 void fabricd_initial_sync_finish(struct isis_area
*area
)
295 struct fabricd
*f
= area
->fabricd
;
300 if (monotime(NULL
) - f
->initial_sync_start
< 5)
303 zlog_info("OpenFabric: Initial synchronization on %s complete.",
304 f
->initial_sync_circuit
->interface
->name
);
305 f
->initial_sync_state
= FABRICD_SYNC_COMPLETE
;
306 f
->initial_sync_circuit
= NULL
;
307 thread_cancel(f
->initial_sync_timeout
);
308 f
->initial_sync_timeout
= NULL
;
311 static void fabricd_bump_tier_calculation_timer(struct fabricd
*f
);
312 static void fabricd_set_tier(struct fabricd
*f
, uint8_t tier
);
314 static uint8_t fabricd_calculate_fabric_tier(struct isis_area
*area
)
316 struct isis_spftree
*local_tree
= fabricd_spftree(area
);
317 struct listnode
*node
;
319 struct isis_vertex
*furthest_t0
= NULL
,
320 *second_furthest_t0
= NULL
;
322 struct isis_vertex
*v
;
324 for (ALL_QUEUE_ELEMENTS_RO(&local_tree
->paths
, node
, v
)) {
325 struct isis_lsp
*lsp
= lsp_for_vertex(local_tree
, v
);
327 if (!lsp
|| !lsp
->tlvs
328 || !lsp
->tlvs
->spine_leaf
329 || !lsp
->tlvs
->spine_leaf
->has_tier
330 || lsp
->tlvs
->spine_leaf
->tier
!= 0)
333 second_furthest_t0
= furthest_t0
;
337 if (!second_furthest_t0
) {
338 zlog_info("OpenFabric: Could not find two T0 routers");
339 return ISIS_TIER_UNDEFINED
;
342 zlog_info("OpenFabric: Found %s as furthest t0 from local system, dist == %"
343 PRIu32
, rawlspid_print(furthest_t0
->N
.id
), furthest_t0
->d_N
);
345 struct isis_spftree
*remote_tree
=
346 isis_run_hopcount_spf(area
, furthest_t0
->N
.id
, NULL
);
348 struct isis_vertex
*furthest_from_remote
=
349 isis_vertex_queue_last(&remote_tree
->paths
);
351 if (!furthest_from_remote
) {
352 zlog_info("OpenFabric: Found no furthest node in remote spf");
353 isis_spftree_del(remote_tree
);
354 return ISIS_TIER_UNDEFINED
;
356 zlog_info("OpenFabric: Found %s as furthest from remote dist == %"
357 PRIu32
, rawlspid_print(furthest_from_remote
->N
.id
),
358 furthest_from_remote
->d_N
);
361 int64_t tier
= furthest_from_remote
->d_N
- furthest_t0
->d_N
;
362 isis_spftree_del(remote_tree
);
364 if (tier
< 0 || tier
>= ISIS_TIER_UNDEFINED
) {
365 zlog_info("OpenFabric: Calculated tier %" PRId64
" seems implausible",
367 return ISIS_TIER_UNDEFINED
;
370 zlog_info("OpenFabric: Calculated %" PRId64
" as tier", tier
);
374 static int fabricd_tier_set_timer(struct thread
*thread
)
376 struct fabricd
*f
= THREAD_ARG(thread
);
377 f
->tier_set_timer
= NULL
;
379 fabricd_set_tier(f
, f
->tier_pending
);
383 static int fabricd_tier_calculation_cb(struct thread
*thread
)
385 struct fabricd
*f
= THREAD_ARG(thread
);
386 uint8_t tier
= ISIS_TIER_UNDEFINED
;
387 f
->tier_calculation_timer
= NULL
;
389 tier
= fabricd_calculate_fabric_tier(f
->area
);
390 if (tier
== ISIS_TIER_UNDEFINED
)
393 zlog_info("OpenFabric: Got tier %" PRIu8
" from algorithm. Arming timer.",
395 f
->tier_pending
= tier
;
396 thread_add_timer(master
, fabricd_tier_set_timer
, f
,
397 f
->area
->lsp_gen_interval
[ISIS_LEVEL2
- 1],
403 static void fabricd_bump_tier_calculation_timer(struct fabricd
*f
)
405 /* Cancel timer if we already know our tier */
406 if (f
->tier
!= ISIS_TIER_UNDEFINED
407 || f
->tier_set_timer
) {
408 if (f
->tier_calculation_timer
) {
409 thread_cancel(f
->tier_calculation_timer
);
410 f
->tier_calculation_timer
= NULL
;
415 /* If we need to calculate the tier, wait some
416 * time for the topology to settle before running
418 if (f
->tier_calculation_timer
) {
419 thread_cancel(f
->tier_calculation_timer
);
420 f
->tier_calculation_timer
= NULL
;
423 thread_add_timer(master
, fabricd_tier_calculation_cb
, f
,
424 2 * f
->area
->lsp_gen_interval
[ISIS_LEVEL2
- 1],
425 &f
->tier_calculation_timer
);
428 static void fabricd_set_tier(struct fabricd
*f
, uint8_t tier
)
433 zlog_info("OpenFabric: Set own tier to %" PRIu8
, tier
);
436 fabricd_bump_tier_calculation_timer(f
);
437 lsp_regenerate_schedule(f
->area
, ISIS_LEVEL2
, 0);
440 void fabricd_run_spf(struct isis_area
*area
)
442 struct fabricd
*f
= area
->fabricd
;
447 isis_run_hopcount_spf(area
, isis
->sysid
, f
->spftree
);
448 neighbor_lists_update(f
);
449 fabricd_bump_tier_calculation_timer(f
);
452 struct isis_spftree
*fabricd_spftree(struct isis_area
*area
)
454 struct fabricd
*f
= area
->fabricd
;
462 void fabricd_configure_tier(struct isis_area
*area
, uint8_t tier
)
464 struct fabricd
*f
= area
->fabricd
;
466 if (!f
|| f
->tier_config
== tier
)
469 f
->tier_config
= tier
;
470 fabricd_set_tier(f
, tier
);
473 uint8_t fabricd_tier(struct isis_area
*area
)
475 struct fabricd
*f
= area
->fabricd
;
478 return ISIS_TIER_UNDEFINED
;
483 int fabricd_write_settings(struct isis_area
*area
, struct vty
*vty
)
485 struct fabricd
*f
= area
->fabricd
;
491 if (f
->tier_config
!= ISIS_TIER_UNDEFINED
) {
492 vty_out(vty
, " fabric-tier %" PRIu8
"\n", f
->tier_config
);
499 static void move_to_dnr(struct isis_lsp
*lsp
, struct neighbor_entry
*n
)
501 struct isis_adjacency
*adj
= listnode_head(n
->vertex
->Adj_N
);
505 if (isis
->debugs
& DEBUG_FABRICD_FLOODING
) {
506 char buff
[PREFIX2STR_BUFFER
];
507 zlog_debug("OpenFabric: Adding %s to DNR",
508 vid2string(n
->vertex
, buff
, sizeof(buff
)));
512 isis_tx_queue_add(adj
->circuit
->tx_queue
, lsp
,
513 TX_LSP_CIRCUIT_SCOPED
);
517 static void move_to_rf(struct isis_lsp
*lsp
, struct neighbor_entry
*n
)
519 struct isis_adjacency
*adj
= listnode_head(n
->vertex
->Adj_N
);
523 if (isis
->debugs
& DEBUG_FABRICD_FLOODING
) {
524 char buff
[PREFIX2STR_BUFFER
];
525 zlog_debug("OpenFabric: Adding %s to RF",
526 vid2string(n
->vertex
, buff
, sizeof(buff
)));
530 isis_tx_queue_add(adj
->circuit
->tx_queue
, lsp
,
535 static void mark_neighbor_as_present(struct hash_backet
*backet
, void *arg
)
537 struct neighbor_entry
*n
= backet
->data
;
542 static void handle_firsthops(struct hash_backet
*backet
, void *arg
)
544 struct isis_lsp
*lsp
= arg
;
545 struct fabricd
*f
= lsp
->area
->fabricd
;
546 struct isis_vertex
*vertex
= backet
->data
;
548 struct neighbor_entry
*n
;
550 n
= neighbor_entry_lookup_list(f
->neighbors
, vertex
->N
.id
);
552 if (isis
->debugs
& DEBUG_FABRICD_FLOODING
) {
553 char buff
[PREFIX2STR_BUFFER
];
554 zlog_debug("Removing %s from NL as its in the reverse path",
555 vid2string(vertex
, buff
, sizeof(buff
)));
560 n
= neighbor_entry_lookup_hash(f
->neighbors_neighbors
, vertex
->N
.id
);
562 if (isis
->debugs
& DEBUG_FABRICD_FLOODING
) {
563 char buff
[PREFIX2STR_BUFFER
];
564 zlog_debug("Removing %s from NN as its in the reverse path",
565 vid2string(vertex
, buff
, sizeof(buff
)));
571 void fabricd_lsp_flood(struct isis_lsp
*lsp
)
573 struct fabricd
*f
= lsp
->area
->fabricd
;
577 struct neighbor_entry
*n
;
579 if (isis
->debugs
& DEBUG_FABRICD_FLOODING
) {
580 zlog_debug("OpenFabric: Flooding LSP %s",
581 rawlspid_print(lsp
->hdr
.lsp_id
));
584 /* Mark all elements in NL as present and move T0s into DNR */
585 while (!skiplist_next(f
->neighbors
, NULL
, (void **)&n
, &cursor
)) {
588 struct isis_lsp
*node_lsp
= lsp_for_vertex(f
->spftree
,
592 || !node_lsp
->tlvs
->spine_leaf
593 || !node_lsp
->tlvs
->spine_leaf
->has_tier
594 || node_lsp
->tlvs
->spine_leaf
->tier
!= 0) {
598 if (isis
->debugs
& DEBUG_FABRICD_FLOODING
) {
599 zlog_debug("Moving %s to DNR because it's T0",
600 rawlspid_print(node_lsp
->hdr
.lsp_id
));
606 /* Mark all elements in NN as present */
607 hash_iterate(f
->neighbors_neighbors
, mark_neighbor_as_present
, NULL
);
609 struct isis_vertex
*originator
= isis_find_vertex(&f
->spftree
->paths
,
611 VTYPE_NONPSEUDO_TE_IS
);
613 /* Remove all IS from NL and NN in the shortest path
614 * to the IS that originated the LSP */
616 hash_iterate(originator
->firsthops
, handle_firsthops
, lsp
);
618 /* Iterate over all remaining IS in NL */
620 while (!skiplist_next(f
->neighbors
, NULL
, (void **)&n
, &cursor
)) {
624 struct isis_lsp
*nlsp
= lsp_for_vertex(f
->spftree
, n
->vertex
);
625 if (!nlsp
|| !nlsp
->tlvs
) {
626 if (isis
->debugs
& DEBUG_FABRICD_FLOODING
) {
627 char buff
[PREFIX2STR_BUFFER
];
628 zlog_debug("Moving %s to DNR as it has no LSP",
629 vid2string(n
->vertex
, buff
, sizeof(buff
)));
636 if (isis
->debugs
& DEBUG_FABRICD_FLOODING
) {
637 char buff
[PREFIX2STR_BUFFER
];
638 zlog_debug("Considering %s from NL...",
639 vid2string(n
->vertex
, buff
, sizeof(buff
)));
642 /* For all neighbors of the NL IS check whether they are present
643 * in NN. If yes, remove from NN and set need_reflood. */
644 bool need_reflood
= false;
645 struct isis_extended_reach
*er
;
646 for (er
= (struct isis_extended_reach
*)nlsp
->tlvs
->extended_reach
.head
;
648 struct neighbor_entry
*nn
;
650 nn
= neighbor_entry_lookup_hash(f
->neighbors_neighbors
,
654 if (isis
->debugs
& DEBUG_FABRICD_FLOODING
) {
655 char buff
[PREFIX2STR_BUFFER
];
656 zlog_debug("Found neighbor %s in NN, removing it from NN and setting reflood.",
657 vid2string(nn
->vertex
, buff
, sizeof(buff
)));
671 if (isis
->debugs
& DEBUG_FABRICD_FLOODING
) {
672 zlog_debug("OpenFabric: Flooding algorithm complete.");
676 void fabricd_trigger_csnp(struct isis_area
*area
)
678 struct fabricd
*f
= area
->fabricd
;
683 struct listnode
*node
;
684 struct isis_circuit
*circuit
;
686 for (ALL_LIST_ELEMENTS_RO(area
->circuit_list
, node
, circuit
)) {
687 if (!circuit
->t_send_csnp
[1])
690 thread_cancel(circuit
->t_send_csnp
[ISIS_LEVEL2
- 1]);
691 thread_add_timer_msec(master
, send_l2_csnp
, circuit
,
692 isis_jitter(500, CSNP_JITTER
),
693 &circuit
->t_send_csnp
[ISIS_LEVEL2
- 1]);
697 struct list
*fabricd_ip_addrs(struct isis_circuit
*circuit
)
699 if (circuit
->ip_addrs
&& listcount(circuit
->ip_addrs
))
700 return circuit
->ip_addrs
;
702 if (!fabricd
|| !circuit
->area
|| !circuit
->area
->circuit_list
)
705 struct listnode
*node
;
706 struct isis_circuit
*c
;
708 for (ALL_LIST_ELEMENTS_RO(circuit
->area
->circuit_list
, node
, c
)) {
709 if (c
->circ_type
!= CIRCUIT_T_LOOPBACK
)
712 if (!c
->ip_addrs
|| !listcount(c
->ip_addrs
))