]>
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 | ||
53 | /* | |
54 | * Triple <N, d(N), {Adj(N)}> | |
55 | */ | |
cbd8e49e CF |
56 | struct isis_vertex { |
57 | enum vertextype type; | |
f6ae63ca CF |
58 | union { |
59 | uint8_t id[ISIS_SYS_ID_LEN + 1]; | |
60 | struct prefix_pair ip; | |
61 | } N; | |
cbd8e49e CF |
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 */ | |
686afe9f | 66 | struct hash *firsthops; /* first two hops to neighbor */ |
cbd8e49e CF |
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__)) | |
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)) { | |
106 | if (prefix_cmp(&va->N.ip.dest, &vb->N.ip.dest)) | |
74df8d6d | 107 | return false; |
cbd8e49e | 108 | |
36de6e0e A |
109 | return prefix_cmp((const struct prefix *)&va->N.ip.src, |
110 | (const struct prefix *)&vb->N.ip.src) == 0; | |
cbd8e49e CF |
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 | { | |
6a154c88 DL |
171 | list_delete(&vertex->Adj_N); |
172 | list_delete(&vertex->parents); | |
686afe9f CF |
173 | if (vertex->firsthops) { |
174 | hash_clean(vertex->firsthops, NULL); | |
175 | hash_free(vertex->firsthops); | |
176 | vertex->firsthops = NULL; | |
177 | } | |
cbd8e49e CF |
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 | |
6a154c88 | 215 | list_delete(&queue->l.list); |
cbd8e49e CF |
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 | { | |
3be6e411 | 241 | struct listnode *tail; |
cbd8e49e | 242 | |
3be6e411 DL |
243 | assert(!queue->insert_counter); |
244 | tail = listtail(queue->l.list); | |
245 | assert(tail); | |
246 | return listgetdata(tail); | |
cbd8e49e CF |
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__)) | |
f6ae63ca | 314 | static void isis_vertex_id_init(struct isis_vertex *vertex, const void *id, |
cbd8e49e CF |
315 | enum vertextype vtype) |
316 | { | |
317 | vertex->type = vtype; | |
318 | ||
319 | if (VTYPE_IS(vtype) || VTYPE_ES(vtype)) { | |
f6ae63ca | 320 | memcpy(vertex->N.id, id, ISIS_SYS_ID_LEN + 1); |
cbd8e49e | 321 | } else if (VTYPE_IP(vtype)) { |
f6ae63ca | 322 | memcpy(&vertex->N.ip, id, sizeof(vertex->N.ip)); |
cbd8e49e | 323 | } else { |
450971aa | 324 | flog_err(EC_LIB_DEVELOPMENT, "Unknown Vertex Type"); |
cbd8e49e CF |
325 | } |
326 | } | |
327 | ||
328 | __attribute__((__unused__)) | |
329 | static struct isis_vertex *isis_find_vertex(struct isis_vertex_queue *queue, | |
f6ae63ca | 330 | const void *id, |
cbd8e49e CF |
331 | enum vertextype vtype) |
332 | { | |
333 | struct isis_vertex querier; | |
334 | ||
f6ae63ca | 335 | isis_vertex_id_init(&querier, id, vtype); |
cbd8e49e CF |
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 | ||
4bef0ec4 DL |
350 | struct lspdb_head *lspdb = &spftree->area->lspdb[spftree->level - 1]; |
351 | struct isis_lsp *lsp = lsp_search(lspdb, lsp_id); | |
cbd8e49e CF |
352 | |
353 | if (lsp && lsp->hdr.rem_lifetime != 0) | |
354 | return lsp; | |
355 | ||
356 | return NULL; | |
357 | } | |
358 | ||
d4cff91a CF |
359 | #define VID2STR_BUFFER SRCDEST2STR_BUFFER |
360 | const char *vid2string(struct isis_vertex *vertex, char *buff, int size); | |
361 | ||
cbd8e49e | 362 | #endif |