isisd/isis_spf_private.h

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * IS-IS Rout(e)ing protocol                  - isis_spf_private.h
   4  *
   5  * Copyright (C) 2001,2002   Sampo Saaristo
   6  *                           Tampere University of Technology
   7  *                           Institute of Communications Engineering
   8  * Copyright (C) 2017        Christian Franke <chris@opensourcerouting.org>
   9  */
  10 #ifndef ISIS_SPF_PRIVATE_H
  11 #define ISIS_SPF_PRIVATE_H
  12
  13 #include "hash.h"
  14 #include "jhash.h"
  15 #include "skiplist.h"
  16 #include "lib_errors.h"
  17
  18 enum vertextype {
  19         VTYPE_PSEUDO_IS = 1,
  20         VTYPE_PSEUDO_TE_IS,
  21         VTYPE_NONPSEUDO_IS,
  22         VTYPE_NONPSEUDO_TE_IS,
  23         VTYPE_ES,
  24         VTYPE_IPREACH_INTERNAL,
  25         VTYPE_IPREACH_EXTERNAL,
  26         VTYPE_IPREACH_TE,
  27         VTYPE_IP6REACH_INTERNAL,
  28         VTYPE_IP6REACH_EXTERNAL
  29 };
  30
  31 #define VTYPE_IS(t) ((t) >= VTYPE_PSEUDO_IS && (t) <= VTYPE_NONPSEUDO_TE_IS)
  32 #define VTYPE_ES(t) ((t) == VTYPE_ES)
  33 #define VTYPE_IP(t) ((t) >= VTYPE_IPREACH_INTERNAL && (t) <= VTYPE_IP6REACH_EXTERNAL)
  34
  35 struct prefix_pair {
  36         struct prefix dest;
  37         struct prefix_ipv6 src;
  38 };
  39
  40 struct isis_vertex_adj {
  41         struct isis_spf_adj *sadj;
  42         struct isis_sr_psid_info sr;
  43         struct mpls_label_stack *label_stack;
  44         uint32_t lfa_metric;
  45 };
  46
  47 /*
  48  * Triple <N, d(N), {Adj(N)}>
  49  */
  50 struct isis_vertex {
  51         enum vertextype type;
  52         union {
  53                 uint8_t id[ISIS_SYS_ID_LEN + 1];
  54                 struct {
  55                         struct prefix_pair p;
  56                         struct isis_sr_psid_info sr;
  57                         enum spf_prefix_priority priority;
  58                 } ip;
  59         } N;
  60         uint32_t d_N;     /* d(N) Distance from this IS      */
  61         uint16_t depth; /* The depth in the imaginary tree */
  62         struct list *Adj_N;    /* {Adj(N)} next hop or neighbor list */
  63         struct list *parents;  /* list of parents for ECMP */
  64         struct hash *firsthops; /* first two hops to neighbor */
  65         uint64_t insert_counter;
  66         uint8_t flags;
  67 };
  68 #define F_ISIS_VERTEX_LFA_PROTECTED     0x01
  69
  70 /* Vertex Queue and associated functions */
  71
  72 struct isis_vertex_queue {
  73         union {
  74                 struct skiplist *slist;
  75                 struct list *list;
  76         } l;
  77         struct hash *hash;
  78         uint64_t insert_counter;
  79 };
  80
  81 __attribute__((__unused__))
  82 static unsigned isis_vertex_queue_hash_key(const void *vp)
  83 {
  84         const struct isis_vertex *vertex = vp;
  85
  86         if (VTYPE_IP(vertex->type)) {
  87                 uint32_t key;
  88
  89                 key = prefix_hash_key(&vertex->N.ip.p.dest);
  90                 key = jhash_1word(prefix_hash_key(&vertex->N.ip.p.src), key);
  91                 return key;
  92         }
  93
  94         return jhash(vertex->N.id, ISIS_SYS_ID_LEN + 1, 0x55aa5a5a);
  95 }
  96
  97 __attribute__((__unused__))
  98 static bool isis_vertex_queue_hash_cmp(const void *a, const void *b)
  99 {
 100         const struct isis_vertex *va = a, *vb = b;
 101
 102         if (va->type != vb->type)
 103                 return false;
 104
 105         if (VTYPE_IP(va->type)) {
 106                 if (prefix_cmp(&va->N.ip.p.dest, &vb->N.ip.p.dest))
 107                         return false;
 108
 109                 return prefix_cmp((const struct prefix *)&va->N.ip.p.src,
 110                                   (const struct prefix *)&vb->N.ip.p.src)
 111                        == 0;
 112         }
 113
 114         return memcmp(va->N.id, vb->N.id, ISIS_SYS_ID_LEN + 1) == 0;
 115 }
 116
 117 /*
 118  * Compares vertizes for sorting in the TENT list. Returns true
 119  * if candidate should be considered before current, false otherwise.
 120  */
 121 __attribute__((__unused__)) static int isis_vertex_queue_tent_cmp(const void *a,
 122                                                                   const void *b)
 123 {
 124         const struct isis_vertex *va = a;
 125         const struct isis_vertex *vb = b;
 126
 127         if (va->d_N < vb->d_N)
 128                 return -1;
 129
 130         if (va->d_N > vb->d_N)
 131                 return 1;
 132
 133         if (va->type < vb->type)
 134                 return -1;
 135
 136         if (va->type > vb->type)
 137                 return 1;
 138
 139         if (va->insert_counter < vb->insert_counter)
 140                 return -1;
 141
 142         if (va->insert_counter > vb->insert_counter)
 143                 return 1;
 144
 145         return 0;
 146 }
 147
 148 __attribute__((__unused__))
 149 static struct skiplist *isis_vertex_queue_skiplist(void)
 150 {
 151         return skiplist_new(0, isis_vertex_queue_tent_cmp, NULL);
 152 }
 153
 154 __attribute__((__unused__))
 155 static void isis_vertex_queue_init(struct isis_vertex_queue *queue,
 156                                    const char *name, bool ordered)
 157 {
 158         if (ordered) {
 159                 queue->insert_counter = 1;
 160                 queue->l.slist = isis_vertex_queue_skiplist();
 161         } else {
 162                 queue->insert_counter = 0;
 163                 queue->l.list = list_new();
 164         }
 165         queue->hash = hash_create(isis_vertex_queue_hash_key,
 166                                   isis_vertex_queue_hash_cmp, name);
 167 }
 168
 169 void isis_vertex_del(struct isis_vertex *vertex);
 170
 171 bool isis_vertex_adj_exists(const struct isis_spftree *spftree,
 172                             const struct isis_vertex *vertex,
 173                             const struct isis_spf_adj *sadj);
 174 void isis_vertex_adj_free(void *arg);
 175 struct isis_vertex_adj *
 176 isis_vertex_adj_add(struct isis_spftree *spftree, struct isis_vertex *vertex,
 177                     struct list *vadj_list, struct isis_spf_adj *sadj,
 178                     struct isis_prefix_sid *psid, bool last_hop);
 179
 180 __attribute__((__unused__))
 181 static void isis_vertex_queue_clear(struct isis_vertex_queue *queue)
 182 {
 183         hash_clean(queue->hash, NULL);
 184
 185         if (queue->insert_counter) {
 186                 struct isis_vertex *vertex;
 187                 while (0 == skiplist_first(queue->l.slist, NULL,
 188                                            (void **)&vertex)) {
 189                         isis_vertex_del(vertex);
 190                         skiplist_delete_first(queue->l.slist);
 191                 }
 192                 queue->insert_counter = 1;
 193         } else {
 194                 queue->l.list->del = (void (*)(void *))isis_vertex_del;
 195                 list_delete_all_node(queue->l.list);
 196                 queue->l.list->del = NULL;
 197         }
 198 }
 199
 200 __attribute__((__unused__))
 201 static void isis_vertex_queue_free(struct isis_vertex_queue *queue)
 202 {
 203         isis_vertex_queue_clear(queue);
 204
 205         hash_free(queue->hash);
 206         queue->hash = NULL;
 207
 208         if (queue->insert_counter) {
 209                 skiplist_free(queue->l.slist);
 210                 queue->l.slist = NULL;
 211         } else
 212                 list_delete(&queue->l.list);
 213 }
 214
 215 __attribute__((__unused__))
 216 static unsigned int isis_vertex_queue_count(struct isis_vertex_queue *queue)
 217 {
 218         return hashcount(queue->hash);
 219 }
 220
 221 __attribute__((__unused__))
 222 static void isis_vertex_queue_append(struct isis_vertex_queue *queue,
 223                                      struct isis_vertex *vertex)
 224 {
 225         assert(!queue->insert_counter);
 226
 227         listnode_add(queue->l.list, vertex);
 228
 229         struct isis_vertex *inserted;
 230
 231         inserted = hash_get(queue->hash, vertex, hash_alloc_intern);
 232         assert(inserted == vertex);
 233 }
 234
 235 __attribute__((__unused__))
 236 static struct isis_vertex *isis_vertex_queue_last(struct isis_vertex_queue *queue)
 237 {
 238         struct listnode *tail;
 239
 240         assert(!queue->insert_counter);
 241         tail = listtail(queue->l.list);
 242         assert(tail);
 243         return listgetdata(tail);
 244 }
 245
 246 __attribute__((__unused__))
 247 static void isis_vertex_queue_insert(struct isis_vertex_queue *queue,
 248                                      struct isis_vertex *vertex)
 249 {
 250         assert(queue->insert_counter);
 251         vertex->insert_counter = queue->insert_counter++;
 252         assert(queue->insert_counter != (uint64_t)-1);
 253
 254         skiplist_insert(queue->l.slist, vertex, vertex);
 255
 256         struct isis_vertex *inserted;
 257         inserted = hash_get(queue->hash, vertex, hash_alloc_intern);
 258         assert(inserted == vertex);
 259 }
 260
 261 __attribute__((__unused__))
 262 static struct isis_vertex *
 263 isis_vertex_queue_pop(struct isis_vertex_queue *queue)
 264 {
 265         assert(queue->insert_counter);
 266
 267         struct isis_vertex *rv;
 268
 269         if (skiplist_first(queue->l.slist, NULL, (void **)&rv))
 270                 return NULL;
 271
 272         skiplist_delete_first(queue->l.slist);
 273         hash_release(queue->hash, rv);
 274
 275         return rv;
 276 }
 277
 278 __attribute__((__unused__))
 279 static void isis_vertex_queue_delete(struct isis_vertex_queue *queue,
 280                                      struct isis_vertex *vertex)
 281 {
 282         assert(queue->insert_counter);
 283
 284         skiplist_delete(queue->l.slist, vertex, vertex);
 285         hash_release(queue->hash, vertex);
 286 }
 287
 288 #define ALL_QUEUE_ELEMENTS_RO(queue, node, data)                               \
 289         ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data)
 290
 291 /* End of vertex queue definitions */
 292
 293 struct isis_spftree {
 294         struct isis_vertex_queue paths; /* the SPT */
 295         struct isis_vertex_queue tents; /* TENT */
 296         struct route_table *route_table;
 297         struct route_table *route_table_backup;
 298         struct lspdb_head *lspdb; /* link-state db */
 299         struct hash *prefix_sids; /* SR Prefix-SIDs. */
 300         struct list *sadj_list;
 301         struct isis_spf_nodes adj_nodes;
 302         struct isis_area *area;    /* back pointer to area */
 303         unsigned int runcount;     /* number of runs since uptime */
 304         time_t last_run_timestamp; /* last run timestamp as wall time for display */
 305         time_t last_run_monotime;  /* last run as monotime for scheduling */
 306         time_t last_run_duration;  /* last run duration in msec */
 307
 308         enum spf_type type;
 309         uint8_t sysid[ISIS_SYS_ID_LEN];
 310         uint16_t mtid;
 311         int family;
 312         int level;
 313         enum spf_tree_id tree_id;
 314         struct {
 315                 /* Original pre-failure local SPTs. */
 316                 struct {
 317                         struct isis_spftree *spftree;
 318                         struct isis_spftree *spftree_reverse;
 319                 } old;
 320
 321                 /* Protected resource. */
 322                 struct lfa_protected_resource protected_resource;
 323
 324                 /* P-space and Q-space. */
 325                 struct isis_spf_nodes p_space;
 326                 struct isis_spf_nodes q_space;
 327
 328                 /* Remote LFA related information. */
 329                 struct {
 330                         /* List of RLFAs eligible to be installed. */
 331                         struct rlfa_tree_head rlfas;
 332
 333                         /*
 334                          * RLFA post-convergence SPTs (needed to activate RLFAs
 335                          * once label information is received from LDP).
 336                          */
 337                         struct list *pc_spftrees;
 338
 339                         /* RLFA maximum metric (or zero if absent). */
 340                         uint32_t max_metric;
 341                 } remote;
 342
 343                 /* Protection counters. */
 344                 struct {
 345                         uint32_t lfa[SPF_PREFIX_PRIO_MAX];
 346                         uint32_t rlfa[SPF_PREFIX_PRIO_MAX];
 347                         uint32_t tilfa[SPF_PREFIX_PRIO_MAX];
 348                         uint32_t ecmp[SPF_PREFIX_PRIO_MAX];
 349                         uint32_t total[SPF_PREFIX_PRIO_MAX];
 350                 } protection_counters;
 351         } lfa;
 352         uint8_t flags;
 353 };
 354 #define F_SPFTREE_HOPCOUNT_METRIC 0x01
 355 #define F_SPFTREE_NO_ROUTES 0x02
 356 #define F_SPFTREE_NO_ADJACENCIES 0x04
 357
 358 __attribute__((__unused__))
 359 static void isis_vertex_id_init(struct isis_vertex *vertex, const void *id,
 360                                 enum vertextype vtype)
 361 {
 362         vertex->type = vtype;
 363
 364         if (VTYPE_IS(vtype) || VTYPE_ES(vtype)) {
 365                 memcpy(vertex->N.id, id, ISIS_SYS_ID_LEN + 1);
 366         } else if (VTYPE_IP(vtype)) {
 367                 memcpy(&vertex->N.ip.p, id, sizeof(vertex->N.ip.p));
 368         } else {
 369                 flog_err(EC_LIB_DEVELOPMENT, "Unknown Vertex Type");
 370         }
 371 }
 372
 373 __attribute__((__unused__))
 374 static struct isis_vertex *isis_find_vertex(struct isis_vertex_queue *queue,
 375                                             const void *id,
 376                                             enum vertextype vtype)
 377 {
 378         struct isis_vertex querier;
 379
 380         isis_vertex_id_init(&querier, id, vtype);
 381         return hash_lookup(queue->hash, &querier);
 382 }
 383
 384 __attribute__((__unused__))
 385 static struct isis_lsp *lsp_for_vertex(struct isis_spftree *spftree,
 386                                        struct isis_vertex *vertex)
 387 {
 388         uint8_t lsp_id[ISIS_SYS_ID_LEN + 2];
 389
 390         assert(VTYPE_IS(vertex->type));
 391
 392         memcpy(lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1);
 393         LSP_FRAGMENT(lsp_id) = 0;
 394
 395         struct isis_lsp *lsp = lsp_search(spftree->lspdb, lsp_id);
 396
 397         if (lsp && lsp->hdr.rem_lifetime != 0)
 398                 return lsp;
 399
 400         return NULL;
 401 }
 402
 403 #define VID2STR_BUFFER SRCDEST2STR_BUFFER
 404 const char *vtype2string(enum vertextype vtype);
 405 const char *vid2string(const struct isis_vertex *vertex, char *buff, int size);
 406
 407 #endif