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