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 };
  58
  59 /*
  60  * Triple <N, d(N), {Adj(N)}>
  61  */
  62 struct isis_vertex {
  63         enum vertextype type;
  64         union {
  65                 uint8_t id[ISIS_SYS_ID_LEN + 1];
  66                 struct {
  67                         struct prefix_pair p;
  68                         struct isis_sr_psid_info sr;
  69                 } ip;
  70         } N;
  71         uint32_t d_N;     /* d(N) Distance from this IS      */
  72         uint16_t depth; /* The depth in the imaginary tree */
  73         struct list *Adj_N;    /* {Adj(N)} next hop or neighbor list */
  74         struct list *parents;  /* list of parents for ECMP */
  75         struct hash *firsthops; /* first two hops to neighbor */
  76         uint64_t insert_counter;
  77 };
  78
  79 /* Vertex Queue and associated functions */
  80
  81 struct isis_vertex_queue {
  82         union {
  83                 struct skiplist *slist;
  84                 struct list *list;
  85         } l;
  86         struct hash *hash;
  87         uint64_t insert_counter;
  88 };
  89
  90 __attribute__((__unused__))
  91 static unsigned isis_vertex_queue_hash_key(const void *vp)
  92 {
  93         const struct isis_vertex *vertex = vp;
  94
  95         if (VTYPE_IP(vertex->type)) {
  96                 uint32_t key;
  97
  98                 key = prefix_hash_key(&vertex->N.ip.p.dest);
  99                 key = jhash_1word(prefix_hash_key(&vertex->N.ip.p.src), key);
 100                 return key;
 101         }
 102
 103         return jhash(vertex->N.id, ISIS_SYS_ID_LEN + 1, 0x55aa5a5a);
 104 }
 105
 106 __attribute__((__unused__))
 107 static bool isis_vertex_queue_hash_cmp(const void *a, const void *b)
 108 {
 109         const struct isis_vertex *va = a, *vb = b;
 110
 111         if (va->type != vb->type)
 112                 return false;
 113
 114         if (VTYPE_IP(va->type)) {
 115                 if (prefix_cmp(&va->N.ip.p.dest, &vb->N.ip.p.dest))
 116                         return false;
 117
 118                 return prefix_cmp((const struct prefix *)&va->N.ip.p.src,
 119                                   (const struct prefix *)&vb->N.ip.p.src)
 120                        == 0;
 121         }
 122
 123         return memcmp(va->N.id, vb->N.id, ISIS_SYS_ID_LEN + 1) == 0;
 124 }
 125
 126 /*
 127  * Compares vertizes for sorting in the TENT list. Returns true
 128  * if candidate should be considered before current, false otherwise.
 129  */
 130 __attribute__((__unused__)) static int isis_vertex_queue_tent_cmp(const void *a,
 131                                                                   const void *b)
 132 {
 133         const struct isis_vertex *va = a;
 134         const struct isis_vertex *vb = b;
 135
 136         if (va->d_N < vb->d_N)
 137                 return -1;
 138
 139         if (va->d_N > vb->d_N)
 140                 return 1;
 141
 142         if (va->type < vb->type)
 143                 return -1;
 144
 145         if (va->type > vb->type)
 146                 return 1;
 147
 148         if (va->insert_counter < vb->insert_counter)
 149                 return -1;
 150
 151         if (va->insert_counter > vb->insert_counter)
 152                 return 1;
 153
 154         return 0;
 155 }
 156
 157 __attribute__((__unused__))
 158 static struct skiplist *isis_vertex_queue_skiplist(void)
 159 {
 160         return skiplist_new(0, isis_vertex_queue_tent_cmp, NULL);
 161 }
 162
 163 __attribute__((__unused__))
 164 static void isis_vertex_queue_init(struct isis_vertex_queue *queue,
 165                                    const char *name, bool ordered)
 166 {
 167         if (ordered) {
 168                 queue->insert_counter = 1;
 169                 queue->l.slist = isis_vertex_queue_skiplist();
 170         } else {
 171                 queue->insert_counter = 0;
 172                 queue->l.list = list_new();
 173         }
 174         queue->hash = hash_create(isis_vertex_queue_hash_key,
 175                                   isis_vertex_queue_hash_cmp, name);
 176 }
 177
 178 __attribute__((__unused__))
 179 static void isis_vertex_del(struct isis_vertex *vertex)
 180 {
 181         list_delete(&vertex->Adj_N);
 182         list_delete(&vertex->parents);
 183         if (vertex->firsthops) {
 184                 hash_clean(vertex->firsthops, NULL);
 185                 hash_free(vertex->firsthops);
 186                 vertex->firsthops = NULL;
 187         }
 188
 189         memset(vertex, 0, sizeof(struct isis_vertex));
 190         XFREE(MTYPE_ISIS_VERTEX, vertex);
 191 }
 192
 193 bool isis_vertex_adj_exists(const struct isis_spftree *spftree,
 194                             const struct isis_vertex *vertex,
 195                             const struct isis_spf_adj *sadj);
 196
 197 __attribute__((__unused__))
 198 static void isis_vertex_queue_clear(struct isis_vertex_queue *queue)
 199 {
 200         hash_clean(queue->hash, NULL);
 201
 202         if (queue->insert_counter) {
 203                 struct isis_vertex *vertex;
 204                 while (0 == skiplist_first(queue->l.slist, NULL,
 205                                            (void **)&vertex)) {
 206                         isis_vertex_del(vertex);
 207                         skiplist_delete_first(queue->l.slist);
 208                 }
 209                 queue->insert_counter = 1;
 210         } else {
 211                 queue->l.list->del = (void (*)(void *))isis_vertex_del;
 212                 list_delete_all_node(queue->l.list);
 213                 queue->l.list->del = NULL;
 214         }
 215 }
 216
 217 __attribute__((__unused__))
 218 static void isis_vertex_queue_free(struct isis_vertex_queue *queue)
 219 {
 220         isis_vertex_queue_clear(queue);
 221
 222         hash_free(queue->hash);
 223         queue->hash = NULL;
 224
 225         if (queue->insert_counter) {
 226                 skiplist_free(queue->l.slist);
 227                 queue->l.slist = NULL;
 228         } else
 229                 list_delete(&queue->l.list);
 230 }
 231
 232 __attribute__((__unused__))
 233 static unsigned int isis_vertex_queue_count(struct isis_vertex_queue *queue)
 234 {
 235         return hashcount(queue->hash);
 236 }
 237
 238 __attribute__((__unused__))
 239 static void isis_vertex_queue_append(struct isis_vertex_queue *queue,
 240                                      struct isis_vertex *vertex)
 241 {
 242         assert(!queue->insert_counter);
 243
 244         listnode_add(queue->l.list, vertex);
 245
 246         struct isis_vertex *inserted;
 247
 248         inserted = hash_get(queue->hash, vertex, hash_alloc_intern);
 249         assert(inserted == vertex);
 250 }
 251
 252 __attribute__((__unused__))
 253 static struct isis_vertex *isis_vertex_queue_last(struct isis_vertex_queue *queue)
 254 {
 255         struct listnode *tail;
 256
 257         assert(!queue->insert_counter);
 258         tail = listtail(queue->l.list);
 259         assert(tail);
 260         return listgetdata(tail);
 261 }
 262
 263 __attribute__((__unused__))
 264 static void isis_vertex_queue_insert(struct isis_vertex_queue *queue,
 265                                      struct isis_vertex *vertex)
 266 {
 267         assert(queue->insert_counter);
 268         vertex->insert_counter = queue->insert_counter++;
 269         assert(queue->insert_counter != (uint64_t)-1);
 270
 271         skiplist_insert(queue->l.slist, vertex, vertex);
 272
 273         struct isis_vertex *inserted;
 274         inserted = hash_get(queue->hash, vertex, hash_alloc_intern);
 275         assert(inserted == vertex);
 276 }
 277
 278 __attribute__((__unused__))
 279 static struct isis_vertex *
 280 isis_vertex_queue_pop(struct isis_vertex_queue *queue)
 281 {
 282         assert(queue->insert_counter);
 283
 284         struct isis_vertex *rv;
 285
 286         if (skiplist_first(queue->l.slist, NULL, (void **)&rv))
 287                 return NULL;
 288
 289         skiplist_delete_first(queue->l.slist);
 290         hash_release(queue->hash, rv);
 291
 292         return rv;
 293 }
 294
 295 __attribute__((__unused__))
 296 static void isis_vertex_queue_delete(struct isis_vertex_queue *queue,
 297                                      struct isis_vertex *vertex)
 298 {
 299         assert(queue->insert_counter);
 300
 301         skiplist_delete(queue->l.slist, vertex, vertex);
 302         hash_release(queue->hash, vertex);
 303 }
 304
 305 #define ALL_QUEUE_ELEMENTS_RO(queue, node, data)                               \
 306         ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data)
 307
 308 /* End of vertex queue definitions */
 309
 310 struct isis_spftree {
 311         struct isis_vertex_queue paths; /* the SPT */
 312         struct isis_vertex_queue tents; /* TENT */
 313         struct route_table *route_table;
 314         struct route_table *route_table_backup;
 315         struct lspdb_head *lspdb; /* link-state db */
 316         struct hash *prefix_sids; /* SR Prefix-SIDs. */
 317         struct list *sadj_list;
 318         struct isis_spf_nodes adj_nodes;
 319         struct isis_area *area;    /* back pointer to area */
 320         unsigned int runcount;     /* number of runs since uptime */
 321         time_t last_run_timestamp; /* last run timestamp as wall time for display */
 322         time_t last_run_monotime;  /* last run as monotime for scheduling */
 323         time_t last_run_duration;  /* last run duration in msec */
 324
 325         enum spf_type type;
 326         uint8_t sysid[ISIS_SYS_ID_LEN];
 327         uint16_t mtid;
 328         int family;
 329         int level;
 330         enum spf_tree_id tree_id;
 331         struct {
 332                 /* Original pre-failure local SPTs. */
 333                 struct {
 334                         struct isis_spftree *spftree;
 335                         struct isis_spftree *spftree_reverse;
 336                 } old;
 337
 338                 /* Protected resource. */
 339                 struct lfa_protected_resource protected_resource;
 340
 341                 /* P-space and Q-space. */
 342                 struct isis_spf_nodes p_space;
 343                 struct isis_spf_nodes q_space;
 344         } lfa;
 345         uint8_t flags;
 346 };
 347 #define F_SPFTREE_HOPCOUNT_METRIC 0x01
 348 #define F_SPFTREE_NO_ROUTES 0x02
 349 #define F_SPFTREE_NO_ADJACENCIES 0x04
 350
 351 __attribute__((__unused__))
 352 static void isis_vertex_id_init(struct isis_vertex *vertex, const void *id,
 353                                 enum vertextype vtype)
 354 {
 355         vertex->type = vtype;
 356
 357         if (VTYPE_IS(vtype) || VTYPE_ES(vtype)) {
 358                 memcpy(vertex->N.id, id, ISIS_SYS_ID_LEN + 1);
 359         } else if (VTYPE_IP(vtype)) {
 360                 memcpy(&vertex->N.ip.p, id, sizeof(vertex->N.ip.p));
 361         } else {
 362                 flog_err(EC_LIB_DEVELOPMENT, "Unknown Vertex Type");
 363         }
 364 }
 365
 366 __attribute__((__unused__))
 367 static struct isis_vertex *isis_find_vertex(struct isis_vertex_queue *queue,
 368                                             const void *id,
 369                                             enum vertextype vtype)
 370 {
 371         struct isis_vertex querier;
 372
 373         isis_vertex_id_init(&querier, id, vtype);
 374         return hash_lookup(queue->hash, &querier);
 375 }
 376
 377 __attribute__((__unused__))
 378 static struct isis_lsp *lsp_for_vertex(struct isis_spftree *spftree,
 379                                        struct isis_vertex *vertex)
 380 {
 381         uint8_t lsp_id[ISIS_SYS_ID_LEN + 2];
 382
 383         assert(VTYPE_IS(vertex->type));
 384
 385         memcpy(lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1);
 386         LSP_FRAGMENT(lsp_id) = 0;
 387
 388         struct isis_lsp *lsp = lsp_search(spftree->lspdb, lsp_id);
 389
 390         if (lsp && lsp->hdr.rem_lifetime != 0)
 391                 return lsp;
 392
 393         return NULL;
 394 }
 395
 396 #define VID2STR_BUFFER SRCDEST2STR_BUFFER
 397 const char *vtype2string(enum vertextype vtype);
 398 const char *vid2string(const struct isis_vertex *vertex, char *buff, int size);
 399
 400 #endif