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