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