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
  35 DEFINE_MTYPE_STATIC(ISISD, FABRICD_STATE, "ISIS OpenFabric")
  36 DEFINE_MTYPE_STATIC(ISISD, FABRICD_NEIGHBOR, "ISIS OpenFabric Neighbor Entry")
  37
  38 /* Tracks initial synchronization as per section 2.4
  39  *
  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.
  42  */
  43 enum fabricd_sync_state {
  44         FABRICD_SYNC_PENDING,
  45         FABRICD_SYNC_STARTED,
  46         FABRICD_SYNC_COMPLETE
  47 };
  48
  49 struct fabricd {
  50         struct isis_area *area;
  51
  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;
  56
  57         struct isis_spftree *spftree;
  58         struct skiplist *neighbors;
  59         struct hash *neighbors_neighbors;
  60
  61         uint8_t tier;
  62         uint8_t tier_config;
  63         uint8_t tier_pending;
  64         struct thread *tier_calculation_timer;
  65         struct thread *tier_set_timer;
  66 };
  67
  68 /* Code related to maintaining the neighbor lists */
  69
  70 struct neighbor_entry {
  71         struct isis_vertex *vertex;
  72         bool present;
  73 };
  74
  75 static struct neighbor_entry *neighbor_entry_new(struct isis_vertex *vertex)
  76 {
  77         struct neighbor_entry *rv = XMALLOC(MTYPE_FABRICD_NEIGHBOR, sizeof(*rv));
  78
  79         rv->vertex = vertex;
  80         return rv;
  81 }
  82
  83 static void neighbor_entry_del(struct neighbor_entry *neighbor)
  84 {
  85         XFREE(MTYPE_FABRICD_NEIGHBOR, neighbor);
  86 }
  87
  88 static void neighbor_entry_del_void(void *arg)
  89 {
  90         neighbor_entry_del((struct neighbor_entry *)arg);
  91 }
  92
  93 static void neighbor_lists_clear(struct fabricd *f)
  94 {
  95         while (!skiplist_empty(f->neighbors))
  96                 skiplist_delete_first(f->neighbors);
  97
  98         hash_clean(f->neighbors_neighbors, neighbor_entry_del_void);
  99 }
 100
 101 static unsigned neighbor_entry_hash_key(void *np)
 102 {
 103         struct neighbor_entry *n = np;
 104
 105         return jhash(n->vertex->N.id, ISIS_SYS_ID_LEN, 0x55aa5a5a);
 106 }
 107
 108 static int neighbor_entry_hash_cmp(const void *a, const void *b)
 109 {
 110         const struct neighbor_entry *na = a, *nb = b;
 111
 112         return memcmp(na->vertex->N.id, nb->vertex->N.id, ISIS_SYS_ID_LEN) == 0;
 113 }
 114
 115 static int neighbor_entry_list_cmp(void *a, void *b)
 116 {
 117         struct neighbor_entry *na = a, *nb = b;
 118
 119         return -memcmp(na->vertex->N.id, nb->vertex->N.id, ISIS_SYS_ID_LEN);
 120 }
 121
 122 static struct neighbor_entry *neighbor_entry_lookup_list(struct skiplist *list,
 123                                                          const uint8_t *id)
 124 {
 125         struct isis_vertex querier;
 126         isis_vertex_id_init(&querier, id, VTYPE_NONPSEUDO_TE_IS);
 127
 128         struct neighbor_entry n = {
 129                 .vertex = &querier
 130         };
 131
 132         struct neighbor_entry *rv;
 133
 134         if (skiplist_search(list, &n, (void**)&rv))
 135                 return NULL;
 136
 137         if (!rv->present)
 138                 return NULL;
 139
 140         return rv;
 141 }
 142
 143 static struct neighbor_entry *neighbor_entry_lookup_hash(struct hash *hash,
 144                                                          const uint8_t *id)
 145 {
 146         struct isis_vertex querier;
 147         isis_vertex_id_init(&querier, id, VTYPE_NONPSEUDO_TE_IS);
 148
 149         struct neighbor_entry n = {
 150                 .vertex = &querier
 151         };
 152
 153         struct neighbor_entry *rv = hash_lookup(hash, &n);
 154
 155         if (!rv || !rv->present)
 156                 return NULL;
 157
 158         return rv;
 159 }
 160
 161 static void neighbor_lists_update(struct fabricd *f)
 162 {
 163         neighbor_lists_clear(f);
 164
 165         struct listnode *node;
 166         struct isis_vertex *v;
 167
 168         for (ALL_QUEUE_ELEMENTS_RO(&f->spftree->paths, node, v)) {
 169                 if (!v->d_N || !VTYPE_IS(v->type))
 170                         continue;
 171
 172                 if (v->d_N > 2)
 173                         break;
 174
 175                 struct neighbor_entry *n = neighbor_entry_new(v);
 176                 if (v->d_N == 1) {
 177                         skiplist_insert(f->neighbors, n, n);
 178                 } else {
 179                         struct neighbor_entry *inserted;
 180                         inserted = hash_get(f->neighbors_neighbors, n, hash_alloc_intern);
 181                         assert(inserted == n);
 182                 }
 183         }
 184 }
 185
 186 struct fabricd *fabricd_new(struct isis_area *area)
 187 {
 188         struct fabricd *rv = XCALLOC(MTYPE_FABRICD_STATE, sizeof(*rv));
 189
 190         rv->area = area;
 191         rv->initial_sync_state = FABRICD_SYNC_PENDING;
 192
 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");
 199
 200         rv->tier = rv->tier_config = ISIS_TIER_UNDEFINED;
 201         return rv;
 202 };
 203
 204 void fabricd_finish(struct fabricd *f)
 205 {
 206         if (f->initial_sync_timeout)
 207                 thread_cancel(f->initial_sync_timeout);
 208
 209         if (f->tier_calculation_timer)
 210                 thread_cancel(f->tier_calculation_timer);
 211
 212         if (f->tier_set_timer)
 213                 thread_cancel(f->tier_set_timer);
 214
 215         isis_spftree_del(f->spftree);
 216         neighbor_lists_clear(f);
 217         skiplist_free(f->neighbors);
 218         hash_free(f->neighbors_neighbors);
 219 }
 220
 221 static int fabricd_initial_sync_timeout(struct thread *thread)
 222 {
 223         struct fabricd *f = THREAD_ARG(thread);
 224
 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;
 230         return 0;
 231 }
 232
 233 void fabricd_initial_sync_hello(struct isis_circuit *circuit)
 234 {
 235         struct fabricd *f = circuit->area->fabricd;
 236
 237         if (!f)
 238                 return;
 239
 240         if (f->initial_sync_state > FABRICD_SYNC_PENDING)
 241                 return;
 242
 243         f->initial_sync_state = FABRICD_SYNC_STARTED;
 244
 245         long timeout = 2 * circuit->hello_interval[1] * circuit->hello_multiplier[1];
 246
 247         f->initial_sync_circuit = circuit;
 248         if (f->initial_sync_timeout)
 249                 return;
 250
 251         thread_add_timer(master, fabricd_initial_sync_timeout, f,
 252                          timeout, &f->initial_sync_timeout);
 253         f->initial_sync_start = monotime(NULL);
 254
 255         zlog_info("OpenFabric: Started initial synchronization with %s on %s",
 256                   sysid_print(circuit->u.p2p.neighbor->sysid),
 257                   circuit->interface->name);
 258 }
 259
 260 bool fabricd_initial_sync_is_in_progress(struct isis_area *area)
 261 {
 262         struct fabricd *f = area->fabricd;
 263
 264         if (!f)
 265                 return false;
 266
 267         if (f->initial_sync_state > FABRICD_SYNC_PENDING
 268             && f->initial_sync_state < FABRICD_SYNC_COMPLETE)
 269                 return true;
 270
 271         return false;
 272 }
 273
 274 struct isis_circuit *fabricd_initial_sync_circuit(struct isis_area *area)
 275 {
 276         struct fabricd *f = area->fabricd;
 277         if (!f)
 278                 return NULL;
 279
 280         return f->initial_sync_circuit;
 281 }
 282
 283 void fabricd_initial_sync_finish(struct isis_area *area)
 284 {
 285         struct fabricd *f = area->fabricd;
 286
 287         if (!f)
 288                 return;
 289
 290         if (monotime(NULL) - f->initial_sync_start < 5)
 291                 return;
 292
 293         zlog_info("OpenFabric: Initial synchronization on %s complete.",
 294                   f->initial_sync_circuit->interface->name);
 295         f->initial_sync_state = FABRICD_SYNC_COMPLETE;
 296         f->initial_sync_circuit = NULL;
 297         thread_cancel(f->initial_sync_timeout);
 298         f->initial_sync_timeout = NULL;
 299 }
 300
 301 static void fabricd_bump_tier_calculation_timer(struct fabricd *f);
 302 static void fabricd_set_tier(struct fabricd *f, uint8_t tier);
 303
 304 static uint8_t fabricd_calculate_fabric_tier(struct isis_area *area)
 305 {
 306         struct isis_spftree *local_tree = fabricd_spftree(area);
 307         struct listnode *node;
 308
 309         struct isis_vertex *furthest_t0 = NULL,
 310                            *second_furthest_t0 = NULL;
 311
 312         struct isis_vertex *v;
 313
 314         for (ALL_QUEUE_ELEMENTS_RO(&local_tree->paths, node, v)) {
 315                 struct isis_lsp *lsp = lsp_for_vertex(local_tree, v);
 316
 317                 if (!lsp || !lsp->tlvs
 318                     || !lsp->tlvs->spine_leaf
 319                     || !lsp->tlvs->spine_leaf->has_tier
 320                     || lsp->tlvs->spine_leaf->tier != 0)
 321                         continue;
 322
 323                 second_furthest_t0 = furthest_t0;
 324                 furthest_t0 = v;
 325         }
 326
 327         if (!second_furthest_t0) {
 328                 zlog_info("OpenFabric: Could not find two T0 routers");
 329                 return ISIS_TIER_UNDEFINED;
 330         }
 331
 332         zlog_info("OpenFabric: Found %s as furthest t0 from local system, dist == %"
 333                   PRIu32, rawlspid_print(furthest_t0->N.id), furthest_t0->d_N);
 334
 335         struct isis_spftree *remote_tree =
 336                 isis_run_hopcount_spf(area, furthest_t0->N.id, NULL);
 337
 338         struct isis_vertex *furthest_from_remote =
 339                 isis_vertex_queue_last(&remote_tree->paths);
 340
 341         if (!furthest_from_remote) {
 342                 zlog_info("OpenFabric: Found no furthest node in remote spf");
 343                 isis_spftree_del(remote_tree);
 344                 return ISIS_TIER_UNDEFINED;
 345         } else {
 346                 zlog_info("OpenFabric: Found %s as furthest from remote dist == %"
 347                           PRIu32, rawlspid_print(furthest_from_remote->N.id),
 348                           furthest_from_remote->d_N);
 349         }
 350
 351         int64_t tier = furthest_from_remote->d_N - furthest_t0->d_N;
 352         isis_spftree_del(remote_tree);
 353
 354         if (tier < 0 || tier >= ISIS_TIER_UNDEFINED) {
 355                 zlog_info("OpenFabric: Calculated tier %" PRId64 " seems implausible",
 356                           tier);
 357                 return ISIS_TIER_UNDEFINED;
 358         }
 359
 360         zlog_info("OpenFabric: Calculated %" PRId64 " as tier", tier);
 361         return tier;
 362 }
 363
 364 static int fabricd_tier_set_timer(struct thread *thread)
 365 {
 366         struct fabricd *f = THREAD_ARG(thread);
 367         f->tier_set_timer = NULL;
 368
 369         fabricd_set_tier(f, f->tier_pending);
 370         return 0;
 371 }
 372
 373 static int fabricd_tier_calculation_cb(struct thread *thread)
 374 {
 375         struct fabricd *f = THREAD_ARG(thread);
 376         uint8_t tier = ISIS_TIER_UNDEFINED;
 377         f->tier_calculation_timer = NULL;
 378
 379         tier = fabricd_calculate_fabric_tier(f->area);
 380         if (tier == ISIS_TIER_UNDEFINED)
 381                 return 0;
 382
 383         zlog_info("OpenFabric: Got tier %" PRIu8 " from algorithm. Arming timer.",
 384                   tier);
 385         f->tier_pending = tier;
 386         thread_add_timer(master, fabricd_tier_set_timer, f,
 387                          f->area->lsp_gen_interval[ISIS_LEVEL2 - 1],
 388                          &f->tier_set_timer);
 389
 390         return 0;
 391 }
 392
 393 static void fabricd_bump_tier_calculation_timer(struct fabricd *f)
 394 {
 395         /* Cancel timer if we already know our tier */
 396         if (f->tier != ISIS_TIER_UNDEFINED
 397             || f->tier_set_timer) {
 398                 if (f->tier_calculation_timer) {
 399                         thread_cancel(f->tier_calculation_timer);
 400                         f->tier_calculation_timer = NULL;
 401                 }
 402                 return;
 403         }
 404
 405         /* If we need to calculate the tier, wait some
 406          * time for the topology to settle before running
 407          * the calculation */
 408         if (f->tier_calculation_timer) {
 409                 thread_cancel(f->tier_calculation_timer);
 410                 f->tier_calculation_timer = NULL;
 411         }
 412
 413         thread_add_timer(master, fabricd_tier_calculation_cb, f,
 414                          2 * f->area->lsp_gen_interval[ISIS_LEVEL2 - 1],
 415                          &f->tier_calculation_timer);
 416 }
 417
 418 static void fabricd_set_tier(struct fabricd *f, uint8_t tier)
 419 {
 420         if (f->tier == tier)
 421                 return;
 422
 423         zlog_info("OpenFabric: Set own tier to %" PRIu8, tier);
 424         f->tier = tier;
 425
 426         fabricd_bump_tier_calculation_timer(f);
 427         lsp_regenerate_schedule(f->area, ISIS_LEVEL2, 0);
 428 }
 429
 430 void fabricd_run_spf(struct isis_area *area)
 431 {
 432         struct fabricd *f = area->fabricd;
 433
 434         if (!f)
 435                 return;
 436
 437         isis_run_hopcount_spf(area, isis->sysid, f->spftree);
 438         neighbor_lists_update(f);
 439         fabricd_bump_tier_calculation_timer(f);
 440 }
 441
 442 struct isis_spftree *fabricd_spftree(struct isis_area *area)
 443 {
 444         struct fabricd *f = area->fabricd;
 445
 446         if (!f)
 447                 return NULL;
 448
 449         return f->spftree;
 450 }
 451
 452 void fabricd_configure_tier(struct isis_area *area, uint8_t tier)
 453 {
 454         struct fabricd *f = area->fabricd;
 455
 456         if (!f || f->tier_config == tier)
 457                 return;
 458
 459         f->tier_config = tier;
 460         fabricd_set_tier(f, tier);
 461 }
 462
 463 uint8_t fabricd_tier(struct isis_area *area)
 464 {
 465         struct fabricd *f = area->fabricd;
 466
 467         if (!f)
 468                 return ISIS_TIER_UNDEFINED;
 469
 470         return f->tier;
 471 }
 472
 473 int fabricd_write_settings(struct isis_area *area, struct vty *vty)
 474 {
 475         struct fabricd *f = area->fabricd;
 476         int written = 0;
 477
 478         if (!f)
 479                 return written;
 480
 481         if (f->tier_config != ISIS_TIER_UNDEFINED) {
 482                 vty_out(vty, " fabric-tier %" PRIu8 "\n", f->tier_config);
 483                 written++;
 484         }
 485
 486         return written;
 487 }
 488
 489 static void move_to_dnr(struct isis_lsp *lsp, struct neighbor_entry *n)
 490 {
 491         struct isis_adjacency *adj = listnode_head(n->vertex->Adj_N);
 492
 493         n->present = false;
 494         if (adj) {
 495                 isis_tx_queue_add(adj->circuit->tx_queue, lsp,
 496                                   TX_LSP_CIRCUIT_SCOPED);
 497         }
 498 }
 499
 500 static void move_to_rf(struct isis_lsp *lsp, struct neighbor_entry *n)
 501 {
 502         struct isis_adjacency *adj = listnode_head(n->vertex->Adj_N);
 503
 504         n->present = false;
 505         if (adj) {
 506                 isis_tx_queue_add(adj->circuit->tx_queue, lsp,
 507                                   TX_LSP_NORMAL);
 508         }
 509 }
 510
 511 static void mark_neighbor_as_present(struct hash_backet *backet, void *arg)
 512 {
 513         struct neighbor_entry *n = backet->data;
 514
 515         n->present = true;
 516 }
 517
 518 static void handle_firsthops(struct hash_backet *backet, void *arg)
 519 {
 520         struct isis_lsp *lsp = arg;
 521         struct fabricd *f = lsp->area->fabricd;
 522         struct isis_vertex *vertex = backet->data;
 523
 524         struct neighbor_entry *n;
 525
 526         n = neighbor_entry_lookup_list(f->neighbors, vertex->N.id);
 527         if (n)
 528                 n->present = false;
 529
 530         n = neighbor_entry_lookup_hash(f->neighbors_neighbors, vertex->N.id);
 531         if (n)
 532                 n->present = false;
 533 }
 534
 535 void fabricd_lsp_flood(struct isis_lsp *lsp)
 536 {
 537         struct fabricd *f = lsp->area->fabricd;
 538         assert(f);
 539
 540         void *cursor = NULL;
 541         struct neighbor_entry *n;
 542
 543         /* Mark all elements in NL as present and move T0s into DNR */
 544         while (!skiplist_next(f->neighbors, NULL, (void **)&n, &cursor)) {
 545                 n->present = true;
 546
 547                 struct isis_lsp *lsp = lsp_for_vertex(f->spftree, n->vertex);
 548                 if (!lsp || !lsp->tlvs || !lsp->tlvs->spine_leaf)
 549                         continue;
 550
 551                 if (!lsp->tlvs->spine_leaf->has_tier
 552                     || lsp->tlvs->spine_leaf->tier != 0)
 553                         continue;
 554
 555                 move_to_dnr(lsp, n);
 556         }
 557
 558         /* Mark all elements in NN as present */
 559         hash_iterate(f->neighbors_neighbors, mark_neighbor_as_present, NULL);
 560
 561         struct isis_vertex *originator = isis_find_vertex(&f->spftree->paths,
 562                                                           lsp->hdr.lsp_id,
 563                                                           VTYPE_NONPSEUDO_TE_IS);
 564
 565         /* Remove all IS from NL and NN in the shortest path
 566          * to the IS that originated the LSP */
 567         if (originator)
 568                 hash_iterate(originator->firsthops, handle_firsthops, lsp);
 569
 570         /* Iterate over all remaining IS in NL */
 571         cursor = NULL;
 572         while (!skiplist_next(f->neighbors, NULL, (void **)&n, &cursor)) {
 573                 if (!n->present)
 574                         continue;
 575
 576                 struct isis_lsp *nlsp = lsp_for_vertex(f->spftree, n->vertex);
 577                 if (!nlsp || !nlsp->tlvs) {
 578                         move_to_dnr(lsp, n);
 579                         continue;
 580                 }
 581
 582                 /* For all neighbors of the NL IS check whether they are present
 583                  * in NN. If yes, remove from NN and set need_reflood. */
 584                 bool need_reflood = false;
 585                 struct isis_extended_reach *er;
 586                 for (er = (struct isis_extended_reach *)nlsp->tlvs->extended_reach.head;
 587                      er; er = er->next) {
 588                         struct neighbor_entry *nn;
 589
 590                         nn = neighbor_entry_lookup_hash(f->neighbors_neighbors,
 591                                                         er->id);
 592
 593                         if (nn) {
 594                                 nn->present = false;
 595                                 need_reflood = true;
 596                         }
 597                 }
 598
 599                 if (need_reflood)
 600                         move_to_rf(lsp, n);
 601                 else
 602                         move_to_dnr(lsp, n);
 603         }
 604 }