]>
Commit | Line | Data |
---|---|---|
acddc0ed | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
cbd8e49e CF |
2 | /* |
3 | * IS-IS Rout(e)ing protocol - isis_spf_private.h | |
4 | * | |
5 | * Copyright (C) 2001,2002 Sampo Saaristo | |
6 | * Tampere University of Technology | |
7 | * Institute of Communications Engineering | |
8 | * Copyright (C) 2017 Christian Franke <chris@opensourcerouting.org> | |
cbd8e49e CF |
9 | */ |
10 | #ifndef ISIS_SPF_PRIVATE_H | |
11 | #define ISIS_SPF_PRIVATE_H | |
12 | ||
13 | #include "hash.h" | |
14 | #include "jhash.h" | |
15 | #include "skiplist.h" | |
16 | #include "lib_errors.h" | |
17 | ||
18 | enum vertextype { | |
19 | VTYPE_PSEUDO_IS = 1, | |
20 | VTYPE_PSEUDO_TE_IS, | |
21 | VTYPE_NONPSEUDO_IS, | |
22 | VTYPE_NONPSEUDO_TE_IS, | |
23 | VTYPE_ES, | |
24 | VTYPE_IPREACH_INTERNAL, | |
25 | VTYPE_IPREACH_EXTERNAL, | |
26 | VTYPE_IPREACH_TE, | |
27 | VTYPE_IP6REACH_INTERNAL, | |
28 | VTYPE_IP6REACH_EXTERNAL | |
29 | }; | |
30 | ||
31 | #define VTYPE_IS(t) ((t) >= VTYPE_PSEUDO_IS && (t) <= VTYPE_NONPSEUDO_TE_IS) | |
32 | #define VTYPE_ES(t) ((t) == VTYPE_ES) | |
33 | #define VTYPE_IP(t) ((t) >= VTYPE_IPREACH_INTERNAL && (t) <= VTYPE_IP6REACH_EXTERNAL) | |
34 | ||
35 | struct prefix_pair { | |
36 | struct prefix dest; | |
37 | struct prefix_ipv6 src; | |
38 | }; | |
39 | ||
7b36d36e RW |
40 | struct isis_vertex_adj { |
41 | struct isis_spf_adj *sadj; | |
d47d6089 | 42 | struct isis_sr_psid_info sr; |
7b36d36e | 43 | struct mpls_label_stack *label_stack; |
e886416f | 44 | uint32_t lfa_metric; |
7b36d36e RW |
45 | }; |
46 | ||
cbd8e49e CF |
47 | /* |
48 | * Triple <N, d(N), {Adj(N)}> | |
49 | */ | |
cbd8e49e CF |
50 | struct isis_vertex { |
51 | enum vertextype type; | |
f6ae63ca CF |
52 | union { |
53 | uint8_t id[ISIS_SYS_ID_LEN + 1]; | |
d47d6089 RW |
54 | struct { |
55 | struct prefix_pair p; | |
56 | struct isis_sr_psid_info sr; | |
e886416f | 57 | enum spf_prefix_priority priority; |
d47d6089 | 58 | } ip; |
f6ae63ca | 59 | } N; |
cbd8e49e CF |
60 | uint32_t d_N; /* d(N) Distance from this IS */ |
61 | uint16_t depth; /* The depth in the imaginary tree */ | |
62 | struct list *Adj_N; /* {Adj(N)} next hop or neighbor list */ | |
63 | struct list *parents; /* list of parents for ECMP */ | |
686afe9f | 64 | struct hash *firsthops; /* first two hops to neighbor */ |
cbd8e49e | 65 | uint64_t insert_counter; |
16fe8cff | 66 | uint8_t flags; |
cbd8e49e | 67 | }; |
16fe8cff | 68 | #define F_ISIS_VERTEX_LFA_PROTECTED 0x01 |
cbd8e49e CF |
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__)) | |
d8b87afe | 82 | static unsigned isis_vertex_queue_hash_key(const void *vp) |
cbd8e49e | 83 | { |
d8b87afe | 84 | const struct isis_vertex *vertex = vp; |
cbd8e49e CF |
85 | |
86 | if (VTYPE_IP(vertex->type)) { | |
87 | uint32_t key; | |
88 | ||
d47d6089 RW |
89 | key = prefix_hash_key(&vertex->N.ip.p.dest); |
90 | key = jhash_1word(prefix_hash_key(&vertex->N.ip.p.src), key); | |
cbd8e49e CF |
91 | return key; |
92 | } | |
93 | ||
94 | return jhash(vertex->N.id, ISIS_SYS_ID_LEN + 1, 0x55aa5a5a); | |
95 | } | |
96 | ||
97 | __attribute__((__unused__)) | |
74df8d6d | 98 | static bool isis_vertex_queue_hash_cmp(const void *a, const void *b) |
cbd8e49e CF |
99 | { |
100 | const struct isis_vertex *va = a, *vb = b; | |
101 | ||
102 | if (va->type != vb->type) | |
74df8d6d | 103 | return false; |
cbd8e49e CF |
104 | |
105 | if (VTYPE_IP(va->type)) { | |
d47d6089 | 106 | if (prefix_cmp(&va->N.ip.p.dest, &vb->N.ip.p.dest)) |
74df8d6d | 107 | return false; |
cbd8e49e | 108 | |
d47d6089 RW |
109 | return prefix_cmp((const struct prefix *)&va->N.ip.p.src, |
110 | (const struct prefix *)&vb->N.ip.p.src) | |
111 | == 0; | |
cbd8e49e CF |
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 | */ | |
1a4189d4 DS |
121 | __attribute__((__unused__)) static int isis_vertex_queue_tent_cmp(const void *a, |
122 | const void *b) | |
cbd8e49e | 123 | { |
1a4189d4 DS |
124 | const struct isis_vertex *va = a; |
125 | const struct isis_vertex *vb = b; | |
cbd8e49e CF |
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 | ||
66b9a381 | 169 | void isis_vertex_del(struct isis_vertex *vertex); |
cbd8e49e | 170 | |
7b36d36e RW |
171 | bool isis_vertex_adj_exists(const struct isis_spftree *spftree, |
172 | const struct isis_vertex *vertex, | |
173 | const struct isis_spf_adj *sadj); | |
e886416f RW |
174 | void isis_vertex_adj_free(void *arg); |
175 | struct isis_vertex_adj * | |
176 | isis_vertex_adj_add(struct isis_spftree *spftree, struct isis_vertex *vertex, | |
177 | struct list *vadj_list, struct isis_spf_adj *sadj, | |
178 | struct isis_prefix_sid *psid, bool last_hop); | |
7b36d36e | 179 | |
cbd8e49e CF |
180 | __attribute__((__unused__)) |
181 | static void isis_vertex_queue_clear(struct isis_vertex_queue *queue) | |
182 | { | |
183 | hash_clean(queue->hash, NULL); | |
184 | ||
185 | if (queue->insert_counter) { | |
186 | struct isis_vertex *vertex; | |
187 | while (0 == skiplist_first(queue->l.slist, NULL, | |
188 | (void **)&vertex)) { | |
189 | isis_vertex_del(vertex); | |
190 | skiplist_delete_first(queue->l.slist); | |
191 | } | |
192 | queue->insert_counter = 1; | |
193 | } else { | |
194 | queue->l.list->del = (void (*)(void *))isis_vertex_del; | |
195 | list_delete_all_node(queue->l.list); | |
196 | queue->l.list->del = NULL; | |
197 | } | |
198 | } | |
199 | ||
200 | __attribute__((__unused__)) | |
201 | static void isis_vertex_queue_free(struct isis_vertex_queue *queue) | |
202 | { | |
203 | isis_vertex_queue_clear(queue); | |
204 | ||
205 | hash_free(queue->hash); | |
206 | queue->hash = NULL; | |
207 | ||
208 | if (queue->insert_counter) { | |
209 | skiplist_free(queue->l.slist); | |
210 | queue->l.slist = NULL; | |
211 | } else | |
6a154c88 | 212 | list_delete(&queue->l.list); |
cbd8e49e CF |
213 | } |
214 | ||
215 | __attribute__((__unused__)) | |
216 | static unsigned int isis_vertex_queue_count(struct isis_vertex_queue *queue) | |
217 | { | |
218 | return hashcount(queue->hash); | |
219 | } | |
220 | ||
221 | __attribute__((__unused__)) | |
222 | static void isis_vertex_queue_append(struct isis_vertex_queue *queue, | |
223 | struct isis_vertex *vertex) | |
224 | { | |
225 | assert(!queue->insert_counter); | |
226 | ||
227 | listnode_add(queue->l.list, vertex); | |
228 | ||
229 | struct isis_vertex *inserted; | |
230 | ||
231 | inserted = hash_get(queue->hash, vertex, hash_alloc_intern); | |
232 | assert(inserted == vertex); | |
233 | } | |
234 | ||
235 | __attribute__((__unused__)) | |
236 | static struct isis_vertex *isis_vertex_queue_last(struct isis_vertex_queue *queue) | |
237 | { | |
3be6e411 | 238 | struct listnode *tail; |
cbd8e49e | 239 | |
3be6e411 DL |
240 | assert(!queue->insert_counter); |
241 | tail = listtail(queue->l.list); | |
242 | assert(tail); | |
243 | return listgetdata(tail); | |
cbd8e49e CF |
244 | } |
245 | ||
246 | __attribute__((__unused__)) | |
247 | static void isis_vertex_queue_insert(struct isis_vertex_queue *queue, | |
248 | struct isis_vertex *vertex) | |
249 | { | |
250 | assert(queue->insert_counter); | |
251 | vertex->insert_counter = queue->insert_counter++; | |
252 | assert(queue->insert_counter != (uint64_t)-1); | |
253 | ||
254 | skiplist_insert(queue->l.slist, vertex, vertex); | |
255 | ||
256 | struct isis_vertex *inserted; | |
257 | inserted = hash_get(queue->hash, vertex, hash_alloc_intern); | |
258 | assert(inserted == vertex); | |
259 | } | |
260 | ||
261 | __attribute__((__unused__)) | |
262 | static struct isis_vertex * | |
263 | isis_vertex_queue_pop(struct isis_vertex_queue *queue) | |
264 | { | |
265 | assert(queue->insert_counter); | |
266 | ||
267 | struct isis_vertex *rv; | |
268 | ||
269 | if (skiplist_first(queue->l.slist, NULL, (void **)&rv)) | |
270 | return NULL; | |
271 | ||
272 | skiplist_delete_first(queue->l.slist); | |
273 | hash_release(queue->hash, rv); | |
274 | ||
275 | return rv; | |
276 | } | |
277 | ||
278 | __attribute__((__unused__)) | |
279 | static void isis_vertex_queue_delete(struct isis_vertex_queue *queue, | |
280 | struct isis_vertex *vertex) | |
281 | { | |
282 | assert(queue->insert_counter); | |
283 | ||
284 | skiplist_delete(queue->l.slist, vertex, vertex); | |
285 | hash_release(queue->hash, vertex); | |
286 | } | |
287 | ||
288 | #define ALL_QUEUE_ELEMENTS_RO(queue, node, data) \ | |
289 | ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data) | |
290 | ||
291 | /* End of vertex queue definitions */ | |
292 | ||
293 | struct isis_spftree { | |
294 | struct isis_vertex_queue paths; /* the SPT */ | |
295 | struct isis_vertex_queue tents; /* TENT */ | |
296 | struct route_table *route_table; | |
c951ee6e | 297 | struct route_table *route_table_backup; |
7b36d36e | 298 | struct lspdb_head *lspdb; /* link-state db */ |
2f7cc7bc | 299 | struct hash *prefix_sids; /* SR Prefix-SIDs. */ |
7b36d36e | 300 | struct list *sadj_list; |
c951ee6e | 301 | struct isis_spf_nodes adj_nodes; |
cbd8e49e CF |
302 | struct isis_area *area; /* back pointer to area */ |
303 | unsigned int runcount; /* number of runs since uptime */ | |
304 | time_t last_run_timestamp; /* last run timestamp as wall time for display */ | |
305 | time_t last_run_monotime; /* last run as monotime for scheduling */ | |
306 | time_t last_run_duration; /* last run duration in msec */ | |
307 | ||
75aa7aa1 | 308 | enum spf_type type; |
7b36d36e | 309 | uint8_t sysid[ISIS_SYS_ID_LEN]; |
cbd8e49e CF |
310 | uint16_t mtid; |
311 | int family; | |
312 | int level; | |
313 | enum spf_tree_id tree_id; | |
c951ee6e RW |
314 | struct { |
315 | /* Original pre-failure local SPTs. */ | |
316 | struct { | |
317 | struct isis_spftree *spftree; | |
318 | struct isis_spftree *spftree_reverse; | |
319 | } old; | |
320 | ||
321 | /* Protected resource. */ | |
322 | struct lfa_protected_resource protected_resource; | |
323 | ||
324 | /* P-space and Q-space. */ | |
325 | struct isis_spf_nodes p_space; | |
326 | struct isis_spf_nodes q_space; | |
fc156c28 | 327 | |
16fe8cff RW |
328 | /* Remote LFA related information. */ |
329 | struct { | |
330 | /* List of RLFAs eligible to be installed. */ | |
331 | struct rlfa_tree_head rlfas; | |
332 | ||
333 | /* | |
334 | * RLFA post-convergence SPTs (needed to activate RLFAs | |
335 | * once label information is received from LDP). | |
336 | */ | |
337 | struct list *pc_spftrees; | |
338 | ||
339 | /* RLFA maximum metric (or zero if absent). */ | |
340 | uint32_t max_metric; | |
341 | } remote; | |
342 | ||
fc156c28 RW |
343 | /* Protection counters. */ |
344 | struct { | |
345 | uint32_t lfa[SPF_PREFIX_PRIO_MAX]; | |
346 | uint32_t rlfa[SPF_PREFIX_PRIO_MAX]; | |
347 | uint32_t tilfa[SPF_PREFIX_PRIO_MAX]; | |
348 | uint32_t ecmp[SPF_PREFIX_PRIO_MAX]; | |
349 | uint32_t total[SPF_PREFIX_PRIO_MAX]; | |
350 | } protection_counters; | |
c951ee6e | 351 | } lfa; |
329f87b3 | 352 | uint8_t algorithm; |
7b36d36e | 353 | uint8_t flags; |
cbd8e49e | 354 | }; |
7b36d36e RW |
355 | #define F_SPFTREE_HOPCOUNT_METRIC 0x01 |
356 | #define F_SPFTREE_NO_ROUTES 0x02 | |
357 | #define F_SPFTREE_NO_ADJACENCIES 0x04 | |
860b75b4 HS |
358 | #ifndef FABRICD |
359 | /* flex-algo */ | |
360 | #define F_SPFTREE_DISABLED 0x08 | |
361 | #endif /* ifndef FABRICD */ | |
cbd8e49e CF |
362 | |
363 | __attribute__((__unused__)) | |
f6ae63ca | 364 | static void isis_vertex_id_init(struct isis_vertex *vertex, const void *id, |
cbd8e49e CF |
365 | enum vertextype vtype) |
366 | { | |
367 | vertex->type = vtype; | |
368 | ||
369 | if (VTYPE_IS(vtype) || VTYPE_ES(vtype)) { | |
f6ae63ca | 370 | memcpy(vertex->N.id, id, ISIS_SYS_ID_LEN + 1); |
cbd8e49e | 371 | } else if (VTYPE_IP(vtype)) { |
d47d6089 | 372 | memcpy(&vertex->N.ip.p, id, sizeof(vertex->N.ip.p)); |
cbd8e49e | 373 | } else { |
450971aa | 374 | flog_err(EC_LIB_DEVELOPMENT, "Unknown Vertex Type"); |
cbd8e49e CF |
375 | } |
376 | } | |
377 | ||
378 | __attribute__((__unused__)) | |
379 | static struct isis_vertex *isis_find_vertex(struct isis_vertex_queue *queue, | |
f6ae63ca | 380 | const void *id, |
cbd8e49e CF |
381 | enum vertextype vtype) |
382 | { | |
383 | struct isis_vertex querier; | |
384 | ||
f6ae63ca | 385 | isis_vertex_id_init(&querier, id, vtype); |
cbd8e49e CF |
386 | return hash_lookup(queue->hash, &querier); |
387 | } | |
388 | ||
389 | __attribute__((__unused__)) | |
390 | static struct isis_lsp *lsp_for_vertex(struct isis_spftree *spftree, | |
391 | struct isis_vertex *vertex) | |
392 | { | |
393 | uint8_t lsp_id[ISIS_SYS_ID_LEN + 2]; | |
394 | ||
395 | assert(VTYPE_IS(vertex->type)); | |
396 | ||
397 | memcpy(lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1); | |
398 | LSP_FRAGMENT(lsp_id) = 0; | |
399 | ||
7b36d36e | 400 | struct isis_lsp *lsp = lsp_search(spftree->lspdb, lsp_id); |
cbd8e49e CF |
401 | |
402 | if (lsp && lsp->hdr.rem_lifetime != 0) | |
403 | return lsp; | |
404 | ||
405 | return NULL; | |
406 | } | |
407 | ||
d4cff91a | 408 | #define VID2STR_BUFFER SRCDEST2STR_BUFFER |
c951ee6e RW |
409 | const char *vtype2string(enum vertextype vtype); |
410 | const char *vid2string(const struct isis_vertex *vertex, char *buff, int size); | |
d4cff91a | 411 | |
cbd8e49e | 412 | #endif |