]>
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 | */ | |
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 | 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 int 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 0; | |
104 | ||
105 | if (VTYPE_IP(va->type)) { | |
106 | if (prefix_cmp(&va->N.ip.dest, &vb->N.ip.dest)) | |
107 | return 0; | |
108 | ||
109 | return prefix_cmp((struct prefix *)&va->N.ip.src, | |
110 | (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_and_null(&vertex->Adj_N); | |
172 | list_delete_and_null(&vertex->parents); | |
173 | ||
174 | memset(vertex, 0, sizeof(struct isis_vertex)); | |
175 | XFREE(MTYPE_ISIS_VERTEX, vertex); | |
176 | } | |
177 | ||
178 | __attribute__((__unused__)) | |
179 | static void isis_vertex_queue_clear(struct isis_vertex_queue *queue) | |
180 | { | |
181 | hash_clean(queue->hash, NULL); | |
182 | ||
183 | if (queue->insert_counter) { | |
184 | struct isis_vertex *vertex; | |
185 | while (0 == skiplist_first(queue->l.slist, NULL, | |
186 | (void **)&vertex)) { | |
187 | isis_vertex_del(vertex); | |
188 | skiplist_delete_first(queue->l.slist); | |
189 | } | |
190 | queue->insert_counter = 1; | |
191 | } else { | |
192 | queue->l.list->del = (void (*)(void *))isis_vertex_del; | |
193 | list_delete_all_node(queue->l.list); | |
194 | queue->l.list->del = NULL; | |
195 | } | |
196 | } | |
197 | ||
198 | __attribute__((__unused__)) | |
199 | static void isis_vertex_queue_free(struct isis_vertex_queue *queue) | |
200 | { | |
201 | isis_vertex_queue_clear(queue); | |
202 | ||
203 | hash_free(queue->hash); | |
204 | queue->hash = NULL; | |
205 | ||
206 | if (queue->insert_counter) { | |
207 | skiplist_free(queue->l.slist); | |
208 | queue->l.slist = NULL; | |
209 | } else | |
210 | list_delete_and_null(&queue->l.list); | |
211 | } | |
212 | ||
213 | __attribute__((__unused__)) | |
214 | static unsigned int isis_vertex_queue_count(struct isis_vertex_queue *queue) | |
215 | { | |
216 | return hashcount(queue->hash); | |
217 | } | |
218 | ||
219 | __attribute__((__unused__)) | |
220 | static void isis_vertex_queue_append(struct isis_vertex_queue *queue, | |
221 | struct isis_vertex *vertex) | |
222 | { | |
223 | assert(!queue->insert_counter); | |
224 | ||
225 | listnode_add(queue->l.list, vertex); | |
226 | ||
227 | struct isis_vertex *inserted; | |
228 | ||
229 | inserted = hash_get(queue->hash, vertex, hash_alloc_intern); | |
230 | assert(inserted == vertex); | |
231 | } | |
232 | ||
233 | __attribute__((__unused__)) | |
234 | static struct isis_vertex *isis_vertex_queue_last(struct isis_vertex_queue *queue) | |
235 | { | |
236 | assert(!queue->insert_counter); | |
237 | ||
238 | return listgetdata(listtail(queue->l.list)); | |
239 | } | |
240 | ||
241 | __attribute__((__unused__)) | |
242 | static void isis_vertex_queue_insert(struct isis_vertex_queue *queue, | |
243 | struct isis_vertex *vertex) | |
244 | { | |
245 | assert(queue->insert_counter); | |
246 | vertex->insert_counter = queue->insert_counter++; | |
247 | assert(queue->insert_counter != (uint64_t)-1); | |
248 | ||
249 | skiplist_insert(queue->l.slist, vertex, vertex); | |
250 | ||
251 | struct isis_vertex *inserted; | |
252 | inserted = hash_get(queue->hash, vertex, hash_alloc_intern); | |
253 | assert(inserted == vertex); | |
254 | } | |
255 | ||
256 | __attribute__((__unused__)) | |
257 | static struct isis_vertex * | |
258 | isis_vertex_queue_pop(struct isis_vertex_queue *queue) | |
259 | { | |
260 | assert(queue->insert_counter); | |
261 | ||
262 | struct isis_vertex *rv; | |
263 | ||
264 | if (skiplist_first(queue->l.slist, NULL, (void **)&rv)) | |
265 | return NULL; | |
266 | ||
267 | skiplist_delete_first(queue->l.slist); | |
268 | hash_release(queue->hash, rv); | |
269 | ||
270 | return rv; | |
271 | } | |
272 | ||
273 | __attribute__((__unused__)) | |
274 | static void isis_vertex_queue_delete(struct isis_vertex_queue *queue, | |
275 | struct isis_vertex *vertex) | |
276 | { | |
277 | assert(queue->insert_counter); | |
278 | ||
279 | skiplist_delete(queue->l.slist, vertex, vertex); | |
280 | hash_release(queue->hash, vertex); | |
281 | } | |
282 | ||
283 | #define ALL_QUEUE_ELEMENTS_RO(queue, node, data) \ | |
284 | ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data) | |
285 | ||
286 | /* End of vertex queue definitions */ | |
287 | ||
288 | struct isis_spftree { | |
289 | struct isis_vertex_queue paths; /* the SPT */ | |
290 | struct isis_vertex_queue tents; /* TENT */ | |
291 | struct route_table *route_table; | |
292 | struct isis_area *area; /* back pointer to area */ | |
293 | unsigned int runcount; /* number of runs since uptime */ | |
294 | time_t last_run_timestamp; /* last run timestamp as wall time for display */ | |
295 | time_t last_run_monotime; /* last run as monotime for scheduling */ | |
296 | time_t last_run_duration; /* last run duration in msec */ | |
297 | ||
298 | uint16_t mtid; | |
299 | int family; | |
300 | int level; | |
301 | enum spf_tree_id tree_id; | |
302 | bool hopcount_metric; | |
303 | }; | |
304 | ||
305 | __attribute__((__unused__)) | |
306 | static void isis_vertex_id_init(struct isis_vertex *vertex, union isis_N *n, | |
307 | enum vertextype vtype) | |
308 | { | |
309 | vertex->type = vtype; | |
310 | ||
311 | if (VTYPE_IS(vtype) || VTYPE_ES(vtype)) { | |
312 | memcpy(vertex->N.id, n->id, ISIS_SYS_ID_LEN + 1); | |
313 | } else if (VTYPE_IP(vtype)) { | |
314 | memcpy(&vertex->N.ip, &n->ip, sizeof(n->ip)); | |
315 | } else { | |
316 | flog_err(LIB_ERR_DEVELOPMENT, "Unknown Vertex Type"); | |
317 | } | |
318 | } | |
319 | ||
320 | __attribute__((__unused__)) | |
321 | static struct isis_vertex *isis_find_vertex(struct isis_vertex_queue *queue, | |
322 | union isis_N *n, | |
323 | enum vertextype vtype) | |
324 | { | |
325 | struct isis_vertex querier; | |
326 | ||
327 | isis_vertex_id_init(&querier, n, vtype); | |
328 | return hash_lookup(queue->hash, &querier); | |
329 | } | |
330 | ||
331 | __attribute__((__unused__)) | |
332 | static struct isis_lsp *lsp_for_vertex(struct isis_spftree *spftree, | |
333 | struct isis_vertex *vertex) | |
334 | { | |
335 | uint8_t lsp_id[ISIS_SYS_ID_LEN + 2]; | |
336 | ||
337 | assert(VTYPE_IS(vertex->type)); | |
338 | ||
339 | memcpy(lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1); | |
340 | LSP_FRAGMENT(lsp_id) = 0; | |
341 | ||
342 | dict_t *lspdb = spftree->area->lspdb[spftree->level - 1]; | |
343 | struct isis_lsp *lsp = lsp_search(lsp_id, lspdb); | |
344 | ||
345 | if (lsp && lsp->hdr.rem_lifetime != 0) | |
346 | return lsp; | |
347 | ||
348 | return NULL; | |
349 | } | |
350 | ||
351 | #endif |