isisd/isis_spf_private.h

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