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