]> git.proxmox.com Git - mirror_frr.git/blob - isisd/fabricd.c
fabricd: Populate NL from adjdb, not spf
[mirror_frr.git] / isisd / fabricd.c
1 /*
2 * IS-IS Rout(e)ing protocol - OpenFabric extensions
3 *
4 * Copyright (C) 2018 Christian Franke
5 *
6 * This file is part of FreeRangeRouting (FRR)
7 *
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
11 * later version.
12 *
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.
17 *
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
21 */
22 #include <zebra.h>
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"
35
36 DEFINE_MTYPE_STATIC(ISISD, FABRICD_STATE, "ISIS OpenFabric")
37 DEFINE_MTYPE_STATIC(ISISD, FABRICD_NEIGHBOR, "ISIS OpenFabric Neighbor Entry")
38
39 /* Tracks initial synchronization as per section 2.4
40 *
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.
43 */
44 enum fabricd_sync_state {
45 FABRICD_SYNC_PENDING,
46 FABRICD_SYNC_STARTED,
47 FABRICD_SYNC_COMPLETE
48 };
49
50 struct fabricd {
51 struct isis_area *area;
52
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;
57
58 struct isis_spftree *spftree;
59 struct skiplist *neighbors;
60 struct hash *neighbors_neighbors;
61
62 uint8_t tier;
63 uint8_t tier_config;
64 uint8_t tier_pending;
65 struct thread *tier_calculation_timer;
66 struct thread *tier_set_timer;
67 };
68
69 /* Code related to maintaining the neighbor lists */
70
71 struct neighbor_entry {
72 uint8_t id[ISIS_SYS_ID_LEN];
73 struct isis_adjacency *adj;
74 bool present;
75 };
76
77 static struct neighbor_entry *neighbor_entry_new(const uint8_t *id,
78 struct isis_adjacency *adj)
79 {
80 struct neighbor_entry *rv = XMALLOC(MTYPE_FABRICD_NEIGHBOR, sizeof(*rv));
81
82 memcpy(rv->id, id, sizeof(rv->id));
83 rv->adj = adj;
84
85 return rv;
86 }
87
88 static void neighbor_entry_del(struct neighbor_entry *neighbor)
89 {
90 XFREE(MTYPE_FABRICD_NEIGHBOR, neighbor);
91 }
92
93 static void neighbor_entry_del_void(void *arg)
94 {
95 neighbor_entry_del((struct neighbor_entry *)arg);
96 }
97
98 static void neighbor_lists_clear(struct fabricd *f)
99 {
100 while (!skiplist_empty(f->neighbors))
101 skiplist_delete_first(f->neighbors);
102
103 hash_clean(f->neighbors_neighbors, neighbor_entry_del_void);
104 }
105
106 static unsigned neighbor_entry_hash_key(void *np)
107 {
108 struct neighbor_entry *n = np;
109
110 return jhash(n->id, sizeof(n->id), 0x55aa5a5a);
111 }
112
113 static bool neighbor_entry_hash_cmp(const void *a, const void *b)
114 {
115 const struct neighbor_entry *na = a, *nb = b;
116
117 return memcmp(na->id, nb->id, sizeof(na->id)) == 0;
118 }
119
120 static int neighbor_entry_list_cmp(void *a, void *b)
121 {
122 struct neighbor_entry *na = a, *nb = b;
123
124 return -memcmp(na->id, nb->id, sizeof(na->id));
125 }
126
127 static struct neighbor_entry *neighbor_entry_lookup_list(struct skiplist *list,
128 const uint8_t *id)
129 {
130 struct neighbor_entry n = {{0}};
131
132 memcpy(n.id, id, sizeof(n.id));
133
134 struct neighbor_entry *rv;
135
136 if (skiplist_search(list, &n, (void**)&rv))
137 return NULL;
138
139 if (!rv->present)
140 return NULL;
141
142 return rv;
143 }
144
145 static struct neighbor_entry *neighbor_entry_lookup_hash(struct hash *hash,
146 const uint8_t *id)
147 {
148 struct neighbor_entry n = {{0}};
149
150 memcpy(n.id, id, sizeof(n.id));
151
152 struct neighbor_entry *rv = hash_lookup(hash, &n);
153
154 if (!rv || !rv->present)
155 return NULL;
156
157 return rv;
158 }
159
160 static void neighbor_lists_update(struct fabricd *f)
161 {
162 neighbor_lists_clear(f);
163
164 struct listnode *node;
165 struct isis_circuit *circuit;
166
167 for (ALL_LIST_ELEMENTS_RO(f->area->circuit_list, node, circuit)) {
168 if (circuit->state != C_STATE_UP)
169 continue;
170
171 struct isis_adjacency *adj = circuit->u.p2p.neighbor;
172
173 if (!adj || adj->adj_state != ISIS_ADJ_UP)
174 continue;
175
176 struct neighbor_entry *n = neighbor_entry_new(adj->sysid, adj);
177
178 skiplist_insert(f->neighbors, n, n);
179 }
180
181 struct isis_vertex *v;
182
183 for (ALL_QUEUE_ELEMENTS_RO(&f->spftree->paths, node, v)) {
184 if (v->d_N < 2 || !VTYPE_IS(v->type))
185 continue;
186
187 if (v->d_N > 2)
188 break;
189
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,
193 hash_alloc_intern);
194 assert(inserted == n);
195 }
196 }
197
198 struct fabricd *fabricd_new(struct isis_area *area)
199 {
200 struct fabricd *rv = XCALLOC(MTYPE_FABRICD_STATE, sizeof(*rv));
201
202 rv->area = area;
203 rv->initial_sync_state = FABRICD_SYNC_PENDING;
204
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");
211
212 rv->tier = rv->tier_config = ISIS_TIER_UNDEFINED;
213 return rv;
214 };
215
216 void fabricd_finish(struct fabricd *f)
217 {
218 if (f->initial_sync_timeout)
219 thread_cancel(f->initial_sync_timeout);
220
221 if (f->tier_calculation_timer)
222 thread_cancel(f->tier_calculation_timer);
223
224 if (f->tier_set_timer)
225 thread_cancel(f->tier_set_timer);
226
227 isis_spftree_del(f->spftree);
228 neighbor_lists_clear(f);
229 skiplist_free(f->neighbors);
230 hash_free(f->neighbors_neighbors);
231 }
232
233 static int fabricd_initial_sync_timeout(struct thread *thread)
234 {
235 struct fabricd *f = THREAD_ARG(thread);
236
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;
242 return 0;
243 }
244
245 void fabricd_initial_sync_hello(struct isis_circuit *circuit)
246 {
247 struct fabricd *f = circuit->area->fabricd;
248
249 if (!f)
250 return;
251
252 if (f->initial_sync_state > FABRICD_SYNC_PENDING)
253 return;
254
255 f->initial_sync_state = FABRICD_SYNC_STARTED;
256
257 long timeout = 2 * circuit->hello_interval[1] * circuit->hello_multiplier[1];
258
259 f->initial_sync_circuit = circuit;
260 if (f->initial_sync_timeout)
261 return;
262
263 thread_add_timer(master, fabricd_initial_sync_timeout, f,
264 timeout, &f->initial_sync_timeout);
265 f->initial_sync_start = monotime(NULL);
266
267 zlog_info("OpenFabric: Started initial synchronization with %s on %s",
268 sysid_print(circuit->u.p2p.neighbor->sysid),
269 circuit->interface->name);
270 }
271
272 bool fabricd_initial_sync_is_in_progress(struct isis_area *area)
273 {
274 struct fabricd *f = area->fabricd;
275
276 if (!f)
277 return false;
278
279 if (f->initial_sync_state > FABRICD_SYNC_PENDING
280 && f->initial_sync_state < FABRICD_SYNC_COMPLETE)
281 return true;
282
283 return false;
284 }
285
286 bool fabricd_initial_sync_is_complete(struct isis_area *area)
287 {
288 struct fabricd *f = area->fabricd;
289
290 if (!f)
291 return false;
292
293 return f->initial_sync_state == FABRICD_SYNC_COMPLETE;
294 }
295
296 struct isis_circuit *fabricd_initial_sync_circuit(struct isis_area *area)
297 {
298 struct fabricd *f = area->fabricd;
299 if (!f)
300 return NULL;
301
302 return f->initial_sync_circuit;
303 }
304
305 void fabricd_initial_sync_finish(struct isis_area *area)
306 {
307 struct fabricd *f = area->fabricd;
308
309 if (!f)
310 return;
311
312 if (monotime(NULL) - f->initial_sync_start < 5)
313 return;
314
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;
321 }
322
323 static void fabricd_bump_tier_calculation_timer(struct fabricd *f);
324 static void fabricd_set_tier(struct fabricd *f, uint8_t tier);
325
326 static uint8_t fabricd_calculate_fabric_tier(struct isis_area *area)
327 {
328 struct isis_spftree *local_tree = fabricd_spftree(area);
329 struct listnode *node;
330
331 struct isis_vertex *furthest_t0 = NULL,
332 *second_furthest_t0 = NULL;
333
334 struct isis_vertex *v;
335
336 for (ALL_QUEUE_ELEMENTS_RO(&local_tree->paths, node, v)) {
337 struct isis_lsp *lsp = lsp_for_vertex(local_tree, v);
338
339 if (!lsp || !lsp->tlvs
340 || !lsp->tlvs->spine_leaf
341 || !lsp->tlvs->spine_leaf->has_tier
342 || lsp->tlvs->spine_leaf->tier != 0)
343 continue;
344
345 second_furthest_t0 = furthest_t0;
346 furthest_t0 = v;
347 }
348
349 if (!second_furthest_t0) {
350 zlog_info("OpenFabric: Could not find two T0 routers");
351 return ISIS_TIER_UNDEFINED;
352 }
353
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);
356
357 struct isis_spftree *remote_tree =
358 isis_run_hopcount_spf(area, furthest_t0->N.id, NULL);
359
360 struct isis_vertex *furthest_from_remote =
361 isis_vertex_queue_last(&remote_tree->paths);
362
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;
367 } else {
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);
371 }
372
373 int64_t tier = furthest_from_remote->d_N - furthest_t0->d_N;
374 isis_spftree_del(remote_tree);
375
376 if (tier < 0 || tier >= ISIS_TIER_UNDEFINED) {
377 zlog_info("OpenFabric: Calculated tier %" PRId64 " seems implausible",
378 tier);
379 return ISIS_TIER_UNDEFINED;
380 }
381
382 zlog_info("OpenFabric: Calculated %" PRId64 " as tier", tier);
383 return tier;
384 }
385
386 static int fabricd_tier_set_timer(struct thread *thread)
387 {
388 struct fabricd *f = THREAD_ARG(thread);
389 f->tier_set_timer = NULL;
390
391 fabricd_set_tier(f, f->tier_pending);
392 return 0;
393 }
394
395 static int fabricd_tier_calculation_cb(struct thread *thread)
396 {
397 struct fabricd *f = THREAD_ARG(thread);
398 uint8_t tier = ISIS_TIER_UNDEFINED;
399 f->tier_calculation_timer = NULL;
400
401 tier = fabricd_calculate_fabric_tier(f->area);
402 if (tier == ISIS_TIER_UNDEFINED)
403 return 0;
404
405 zlog_info("OpenFabric: Got tier %" PRIu8 " from algorithm. Arming timer.",
406 tier);
407 f->tier_pending = tier;
408 thread_add_timer(master, fabricd_tier_set_timer, f,
409 f->area->lsp_gen_interval[ISIS_LEVEL2 - 1],
410 &f->tier_set_timer);
411
412 return 0;
413 }
414
415 static void fabricd_bump_tier_calculation_timer(struct fabricd *f)
416 {
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;
423 }
424 return;
425 }
426
427 /* If we need to calculate the tier, wait some
428 * time for the topology to settle before running
429 * the calculation */
430 if (f->tier_calculation_timer) {
431 thread_cancel(f->tier_calculation_timer);
432 f->tier_calculation_timer = NULL;
433 }
434
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);
438 }
439
440 static void fabricd_set_tier(struct fabricd *f, uint8_t tier)
441 {
442 if (f->tier == tier)
443 return;
444
445 zlog_info("OpenFabric: Set own tier to %" PRIu8, tier);
446 f->tier = tier;
447
448 fabricd_bump_tier_calculation_timer(f);
449 lsp_regenerate_schedule(f->area, ISIS_LEVEL2, 0);
450 }
451
452 void fabricd_run_spf(struct isis_area *area)
453 {
454 struct fabricd *f = area->fabricd;
455
456 if (!f)
457 return;
458
459 isis_run_hopcount_spf(area, isis->sysid, f->spftree);
460 neighbor_lists_update(f);
461 fabricd_bump_tier_calculation_timer(f);
462 }
463
464 struct isis_spftree *fabricd_spftree(struct isis_area *area)
465 {
466 struct fabricd *f = area->fabricd;
467
468 if (!f)
469 return NULL;
470
471 return f->spftree;
472 }
473
474 void fabricd_configure_tier(struct isis_area *area, uint8_t tier)
475 {
476 struct fabricd *f = area->fabricd;
477
478 if (!f || f->tier_config == tier)
479 return;
480
481 f->tier_config = tier;
482 fabricd_set_tier(f, tier);
483 }
484
485 uint8_t fabricd_tier(struct isis_area *area)
486 {
487 struct fabricd *f = area->fabricd;
488
489 if (!f)
490 return ISIS_TIER_UNDEFINED;
491
492 return f->tier;
493 }
494
495 int fabricd_write_settings(struct isis_area *area, struct vty *vty)
496 {
497 struct fabricd *f = area->fabricd;
498 int written = 0;
499
500 if (!f)
501 return written;
502
503 if (f->tier_config != ISIS_TIER_UNDEFINED) {
504 vty_out(vty, " fabric-tier %" PRIu8 "\n", f->tier_config);
505 written++;
506 }
507
508 return written;
509 }
510
511 static void move_to_queue(struct isis_lsp *lsp, struct neighbor_entry *n,
512 enum isis_tx_type type)
513 {
514 n->present = false;
515
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");
520 }
521
522 if (n->adj)
523 isis_tx_queue_add(n->adj->circuit->tx_queue, lsp, type);
524 }
525
526 static void mark_neighbor_as_present(struct hash_backet *backet, void *arg)
527 {
528 struct neighbor_entry *n = backet->data;
529
530 n->present = true;
531 }
532
533 static void handle_firsthops(struct hash_backet *backet, void *arg)
534 {
535 struct isis_lsp *lsp = arg;
536 struct fabricd *f = lsp->area->fabricd;
537 struct isis_vertex *vertex = backet->data;
538
539 struct neighbor_entry *n;
540
541 n = neighbor_entry_lookup_list(f->neighbors, vertex->N.id);
542 if (n) {
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));
546 }
547 n->present = false;
548 }
549
550 n = neighbor_entry_lookup_hash(f->neighbors_neighbors, vertex->N.id);
551 if (n) {
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));
555 }
556 n->present = false;
557 }
558 }
559
560 static struct isis_lsp *lsp_for_neighbor(struct fabricd *f,
561 struct neighbor_entry *n)
562 {
563 uint8_t id[ISIS_SYS_ID_LEN + 1] = {0};
564
565 memcpy(id, n->id, sizeof(n->id));
566
567 struct isis_vertex vertex = {0};
568
569 isis_vertex_id_init(&vertex, id, VTYPE_NONPSEUDO_TE_IS);
570
571 return lsp_for_vertex(f->spftree, &vertex);
572 }
573
574 void fabricd_lsp_flood(struct isis_lsp *lsp)
575 {
576 struct fabricd *f = lsp->area->fabricd;
577 assert(f);
578
579 void *cursor = NULL;
580 struct neighbor_entry *n;
581
582 /* Mark all elements in NL as present and move T0s into DNR */
583 while (!skiplist_next(f->neighbors, NULL, (void **)&n, &cursor)) {
584 n->present = true;
585
586 struct isis_lsp *node_lsp = lsp_for_neighbor(f, n);
587 if (!node_lsp
588 || !node_lsp->tlvs
589 || !node_lsp->tlvs->spine_leaf
590 || !node_lsp->tlvs->spine_leaf->has_tier
591 || node_lsp->tlvs->spine_leaf->tier != 0) {
592 continue;
593 }
594
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));
598 }
599
600 move_to_queue(lsp, n, TX_LSP_CIRCUIT_SCOPED);
601 }
602
603 /* Mark all elements in NN as present */
604 hash_iterate(f->neighbors_neighbors, mark_neighbor_as_present, NULL);
605
606 struct isis_vertex *originator = isis_find_vertex(&f->spftree->paths,
607 lsp->hdr.lsp_id,
608 VTYPE_NONPSEUDO_TE_IS);
609
610 /* Remove all IS from NL and NN in the shortest path
611 * to the IS that originated the LSP */
612 if (originator)
613 hash_iterate(originator->firsthops, handle_firsthops, lsp);
614
615 /* Iterate over all remaining IS in NL */
616 cursor = NULL;
617 while (!skiplist_next(f->neighbors, NULL, (void **)&n, &cursor)) {
618 if (!n->present)
619 continue;
620
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));
626 }
627
628 move_to_queue(lsp, n, TX_LSP_CIRCUIT_SCOPED);
629 continue;
630 }
631
632 if (isis->debugs & DEBUG_FLOODING) {
633 zlog_debug("Considering %s from NL...",
634 print_sys_hostname(n->id));
635 }
636
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;
642 er; er = er->next) {
643 struct neighbor_entry *nn;
644
645 nn = neighbor_entry_lookup_hash(f->neighbors_neighbors,
646 er->id);
647
648 if (nn) {
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));
652 }
653
654 nn->present = false;
655 need_reflood = true;
656 }
657 }
658
659 move_to_queue(lsp, n, need_reflood ?
660 TX_LSP_NORMAL : TX_LSP_CIRCUIT_SCOPED);
661 }
662
663 if (isis->debugs & DEBUG_FLOODING) {
664 zlog_debug("OpenFabric: Flooding algorithm complete.");
665 }
666 }
667
668 void fabricd_trigger_csnp(struct isis_area *area)
669 {
670 struct fabricd *f = area->fabricd;
671
672 if (!f)
673 return;
674
675 struct listnode *node;
676 struct isis_circuit *circuit;
677
678 for (ALL_LIST_ELEMENTS_RO(area->circuit_list, node, circuit)) {
679 if (!circuit->t_send_csnp[1])
680 continue;
681
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]);
686 }
687 }
688
689 struct list *fabricd_ip_addrs(struct isis_circuit *circuit)
690 {
691 if (circuit->ip_addrs && listcount(circuit->ip_addrs))
692 return circuit->ip_addrs;
693
694 if (!fabricd || !circuit->area || !circuit->area->circuit_list)
695 return NULL;
696
697 struct listnode *node;
698 struct isis_circuit *c;
699
700 for (ALL_LIST_ELEMENTS_RO(circuit->area->circuit_list, node, c)) {
701 if (c->circ_type != CIRCUIT_T_LOOPBACK)
702 continue;
703
704 if (!c->ip_addrs || !listcount(c->ip_addrs))
705 return NULL;
706
707 return c->ip_addrs;
708 }
709
710 return NULL;
711 }