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