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 void isis_vertex_del(struct isis_vertex *vertex);
 183
 184 bool isis_vertex_adj_exists(const struct isis_spftree *spftree,
 185                             const struct isis_vertex *vertex,
 186                             const struct isis_spf_adj *sadj);
 187 void isis_vertex_adj_free(void *arg);
 188 struct isis_vertex_adj *
 189 isis_vertex_adj_add(struct isis_spftree *spftree, struct isis_vertex *vertex,
 190                     struct list *vadj_list, struct isis_spf_adj *sadj,
 191                     struct isis_prefix_sid *psid, bool last_hop);
 192
 193 __attribute__((__unused__))
 194 static void isis_vertex_queue_clear(struct isis_vertex_queue *queue)
 195 {
 196         hash_clean(queue->hash, NULL);
 197
 198         if (queue->insert_counter) {
 199                 struct isis_vertex *vertex;
 200                 while (0 == skiplist_first(queue->l.slist, NULL,
 201                                            (void **)&vertex)) {
 202                         isis_vertex_del(vertex);
 203                         skiplist_delete_first(queue->l.slist);
 204                 }
 205                 queue->insert_counter = 1;
 206         } else {
 207                 queue->l.list->del = (void (*)(void *))isis_vertex_del;
 208                 list_delete_all_node(queue->l.list);
 209                 queue->l.list->del = NULL;
 210         }
 211 }
 212
 213 __attribute__((__unused__))
 214 static void isis_vertex_queue_free(struct isis_vertex_queue *queue)
 215 {
 216         isis_vertex_queue_clear(queue);
 217
 218         hash_free(queue->hash);
 219         queue->hash = NULL;
 220
 221         if (queue->insert_counter) {
 222                 skiplist_free(queue->l.slist);
 223                 queue->l.slist = NULL;
 224         } else
 225                 list_delete(&queue->l.list);
 226 }
 227
 228 __attribute__((__unused__))
 229 static unsigned int isis_vertex_queue_count(struct isis_vertex_queue *queue)
 230 {
 231         return hashcount(queue->hash);
 232 }
 233
 234 __attribute__((__unused__))
 235 static void isis_vertex_queue_append(struct isis_vertex_queue *queue,
 236                                      struct isis_vertex *vertex)
 237 {
 238         assert(!queue->insert_counter);
 239
 240         listnode_add(queue->l.list, vertex);
 241
 242         struct isis_vertex *inserted;
 243
 244         inserted = hash_get(queue->hash, vertex, hash_alloc_intern);
 245         assert(inserted == vertex);
 246 }
 247
 248 __attribute__((__unused__))
 249 static struct isis_vertex *isis_vertex_queue_last(struct isis_vertex_queue *queue)
 250 {
 251         struct listnode *tail;
 252
 253         assert(!queue->insert_counter);
 254         tail = listtail(queue->l.list);
 255         assert(tail);
 256         return listgetdata(tail);
 257 }
 258
 259 __attribute__((__unused__))
 260 static void isis_vertex_queue_insert(struct isis_vertex_queue *queue,
 261                                      struct isis_vertex *vertex)
 262 {
 263         assert(queue->insert_counter);
 264         vertex->insert_counter = queue->insert_counter++;
 265         assert(queue->insert_counter != (uint64_t)-1);
 266
 267         skiplist_insert(queue->l.slist, vertex, vertex);
 268
 269         struct isis_vertex *inserted;
 270         inserted = hash_get(queue->hash, vertex, hash_alloc_intern);
 271         assert(inserted == vertex);
 272 }
 273
 274 __attribute__((__unused__))
 275 static struct isis_vertex *
 276 isis_vertex_queue_pop(struct isis_vertex_queue *queue)
 277 {
 278         assert(queue->insert_counter);
 279
 280         struct isis_vertex *rv;
 281
 282         if (skiplist_first(queue->l.slist, NULL, (void **)&rv))
 283                 return NULL;
 284
 285         skiplist_delete_first(queue->l.slist);
 286         hash_release(queue->hash, rv);
 287
 288         return rv;
 289 }
 290
 291 __attribute__((__unused__))
 292 static void isis_vertex_queue_delete(struct isis_vertex_queue *queue,
 293                                      struct isis_vertex *vertex)
 294 {
 295         assert(queue->insert_counter);
 296
 297         skiplist_delete(queue->l.slist, vertex, vertex);
 298         hash_release(queue->hash, vertex);
 299 }
 300
 301 #define ALL_QUEUE_ELEMENTS_RO(queue, node, data)                               \
 302         ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data)
 303
 304 /* End of vertex queue definitions */
 305
 306 struct isis_spftree {
 307         struct isis_vertex_queue paths; /* the SPT */
 308         struct isis_vertex_queue tents; /* TENT */
 309         struct route_table *route_table;
 310         struct route_table *route_table_backup;
 311         struct lspdb_head *lspdb; /* link-state db */
 312         struct hash *prefix_sids; /* SR Prefix-SIDs. */
 313         struct list *sadj_list;
 314         struct isis_spf_nodes adj_nodes;
 315         struct isis_area *area;    /* back pointer to area */
 316         unsigned int runcount;     /* number of runs since uptime */
 317         time_t last_run_timestamp; /* last run timestamp as wall time for display */
 318         time_t last_run_monotime;  /* last run as monotime for scheduling */
 319         time_t last_run_duration;  /* last run duration in msec */
 320
 321         enum spf_type type;
 322         uint8_t sysid[ISIS_SYS_ID_LEN];
 323         uint16_t mtid;
 324         int family;
 325         int level;
 326         enum spf_tree_id tree_id;
 327         struct {
 328                 /* Original pre-failure local SPTs. */
 329                 struct {
 330                         struct isis_spftree *spftree;
 331                         struct isis_spftree *spftree_reverse;
 332                 } old;
 333
 334                 /* Protected resource. */
 335                 struct lfa_protected_resource protected_resource;
 336
 337                 /* P-space and Q-space. */
 338                 struct isis_spf_nodes p_space;
 339                 struct isis_spf_nodes q_space;
 340
 341                 /* Remote LFA related information. */
 342                 struct {
 343                         /* List of RLFAs eligible to be installed. */
 344                         struct rlfa_tree_head rlfas;
 345
 346                         /*
 347                          * RLFA post-convergence SPTs (needed to activate RLFAs
 348                          * once label information is received from LDP).
 349                          */
 350                         struct list *pc_spftrees;
 351
 352                         /* RLFA maximum metric (or zero if absent). */
 353                         uint32_t max_metric;
 354                 } remote;
 355
 356                 /* Protection counters. */
 357                 struct {
 358                         uint32_t lfa[SPF_PREFIX_PRIO_MAX];
 359                         uint32_t rlfa[SPF_PREFIX_PRIO_MAX];
 360                         uint32_t tilfa[SPF_PREFIX_PRIO_MAX];
 361                         uint32_t ecmp[SPF_PREFIX_PRIO_MAX];
 362                         uint32_t total[SPF_PREFIX_PRIO_MAX];
 363                 } protection_counters;
 364         } lfa;
 365         uint8_t flags;
 366 };
 367 #define F_SPFTREE_HOPCOUNT_METRIC 0x01
 368 #define F_SPFTREE_NO_ROUTES 0x02
 369 #define F_SPFTREE_NO_ADJACENCIES 0x04
 370
 371 __attribute__((__unused__))
 372 static void isis_vertex_id_init(struct isis_vertex *vertex, const void *id,
 373                                 enum vertextype vtype)
 374 {
 375         vertex->type = vtype;
 376
 377         if (VTYPE_IS(vtype) || VTYPE_ES(vtype)) {
 378                 memcpy(vertex->N.id, id, ISIS_SYS_ID_LEN + 1);
 379         } else if (VTYPE_IP(vtype)) {
 380                 memcpy(&vertex->N.ip.p, id, sizeof(vertex->N.ip.p));
 381         } else {
 382                 flog_err(EC_LIB_DEVELOPMENT, "Unknown Vertex Type");
 383         }
 384 }
 385
 386 __attribute__((__unused__))
 387 static struct isis_vertex *isis_find_vertex(struct isis_vertex_queue *queue,
 388                                             const void *id,
 389                                             enum vertextype vtype)
 390 {
 391         struct isis_vertex querier;
 392
 393         isis_vertex_id_init(&querier, id, vtype);
 394         return hash_lookup(queue->hash, &querier);
 395 }
 396
 397 __attribute__((__unused__))
 398 static struct isis_lsp *lsp_for_vertex(struct isis_spftree *spftree,
 399                                        struct isis_vertex *vertex)
 400 {
 401         uint8_t lsp_id[ISIS_SYS_ID_LEN + 2];
 402
 403         assert(VTYPE_IS(vertex->type));
 404
 405         memcpy(lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1);
 406         LSP_FRAGMENT(lsp_id) = 0;
 407
 408         struct isis_lsp *lsp = lsp_search(spftree->lspdb, lsp_id);
 409
 410         if (lsp && lsp->hdr.rem_lifetime != 0)
 411                 return lsp;
 412
 413         return NULL;
 414 }
 415
 416 #define VID2STR_BUFFER SRCDEST2STR_BUFFER
 417 const char *vtype2string(enum vertextype vtype);
 418 const char *vid2string(const struct isis_vertex *vertex, char *buff, int size);
 419
 420 #endif