2 * IS-IS Rout(e)ing protocol - isis_spf_private.h
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>
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)
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
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
23 #ifndef ISIS_SPF_PRIVATE_H
24 #define ISIS_SPF_PRIVATE_H
29 #include "lib_errors.h"
35 VTYPE_NONPSEUDO_TE_IS
,
37 VTYPE_IPREACH_INTERNAL
,
38 VTYPE_IPREACH_EXTERNAL
,
40 VTYPE_IP6REACH_INTERNAL
,
41 VTYPE_IP6REACH_EXTERNAL
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)
50 struct prefix_ipv6 src
;
54 * Triple <N, d(N), {Adj(N)}>
59 uint8_t id
[ISIS_SYS_ID_LEN
+ 1];
60 struct prefix_pair ip
;
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
;
70 /* Vertex Queue and associated functions */
72 struct isis_vertex_queue
{
74 struct skiplist
*slist
;
78 uint64_t insert_counter
;
81 __attribute__((__unused__
))
82 static unsigned isis_vertex_queue_hash_key(void *vp
)
84 struct isis_vertex
*vertex
= vp
;
86 if (VTYPE_IP(vertex
->type
)) {
89 key
= prefix_hash_key(&vertex
->N
.ip
.dest
);
90 key
= jhash_1word(prefix_hash_key(&vertex
->N
.ip
.src
), key
);
94 return jhash(vertex
->N
.id
, ISIS_SYS_ID_LEN
+ 1, 0x55aa5a5a);
97 __attribute__((__unused__
))
98 static bool isis_vertex_queue_hash_cmp(const void *a
, const void *b
)
100 const struct isis_vertex
*va
= a
, *vb
= b
;
102 if (va
->type
!= vb
->type
)
105 if (VTYPE_IP(va
->type
)) {
106 if (prefix_cmp(&va
->N
.ip
.dest
, &vb
->N
.ip
.dest
))
109 return prefix_cmp((const struct prefix
*)&va
->N
.ip
.src
,
110 (const struct prefix
*)&vb
->N
.ip
.src
) == 0;
113 return memcmp(va
->N
.id
, vb
->N
.id
, ISIS_SYS_ID_LEN
+ 1) == 0;
117 * Compares vertizes for sorting in the TENT list. Returns true
118 * if candidate should be considered before current, false otherwise.
120 __attribute__((__unused__
))
121 static int isis_vertex_queue_tent_cmp(void *a
, void *b
)
123 struct isis_vertex
*va
= a
;
124 struct isis_vertex
*vb
= b
;
126 if (va
->d_N
< vb
->d_N
)
129 if (va
->d_N
> vb
->d_N
)
132 if (va
->type
< vb
->type
)
135 if (va
->type
> vb
->type
)
138 if (va
->insert_counter
< vb
->insert_counter
)
141 if (va
->insert_counter
> vb
->insert_counter
)
147 __attribute__((__unused__
))
148 static struct skiplist
*isis_vertex_queue_skiplist(void)
150 return skiplist_new(0, isis_vertex_queue_tent_cmp
, NULL
);
153 __attribute__((__unused__
))
154 static void isis_vertex_queue_init(struct isis_vertex_queue
*queue
,
155 const char *name
, bool ordered
)
158 queue
->insert_counter
= 1;
159 queue
->l
.slist
= isis_vertex_queue_skiplist();
161 queue
->insert_counter
= 0;
162 queue
->l
.list
= list_new();
164 queue
->hash
= hash_create(isis_vertex_queue_hash_key
,
165 isis_vertex_queue_hash_cmp
, name
);
168 __attribute__((__unused__
))
169 static void isis_vertex_del(struct isis_vertex
*vertex
)
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
;
179 memset(vertex
, 0, sizeof(struct isis_vertex
));
180 XFREE(MTYPE_ISIS_VERTEX
, vertex
);
183 __attribute__((__unused__
))
184 static void isis_vertex_queue_clear(struct isis_vertex_queue
*queue
)
186 hash_clean(queue
->hash
, NULL
);
188 if (queue
->insert_counter
) {
189 struct isis_vertex
*vertex
;
190 while (0 == skiplist_first(queue
->l
.slist
, NULL
,
192 isis_vertex_del(vertex
);
193 skiplist_delete_first(queue
->l
.slist
);
195 queue
->insert_counter
= 1;
197 queue
->l
.list
->del
= (void (*)(void *))isis_vertex_del
;
198 list_delete_all_node(queue
->l
.list
);
199 queue
->l
.list
->del
= NULL
;
203 __attribute__((__unused__
))
204 static void isis_vertex_queue_free(struct isis_vertex_queue
*queue
)
206 isis_vertex_queue_clear(queue
);
208 hash_free(queue
->hash
);
211 if (queue
->insert_counter
) {
212 skiplist_free(queue
->l
.slist
);
213 queue
->l
.slist
= NULL
;
215 list_delete(&queue
->l
.list
);
218 __attribute__((__unused__
))
219 static unsigned int isis_vertex_queue_count(struct isis_vertex_queue
*queue
)
221 return hashcount(queue
->hash
);
224 __attribute__((__unused__
))
225 static void isis_vertex_queue_append(struct isis_vertex_queue
*queue
,
226 struct isis_vertex
*vertex
)
228 assert(!queue
->insert_counter
);
230 listnode_add(queue
->l
.list
, vertex
);
232 struct isis_vertex
*inserted
;
234 inserted
= hash_get(queue
->hash
, vertex
, hash_alloc_intern
);
235 assert(inserted
== vertex
);
238 __attribute__((__unused__
))
239 static struct isis_vertex
*isis_vertex_queue_last(struct isis_vertex_queue
*queue
)
241 struct listnode
*tail
;
243 assert(!queue
->insert_counter
);
244 tail
= listtail(queue
->l
.list
);
246 return listgetdata(tail
);
249 __attribute__((__unused__
))
250 static void isis_vertex_queue_insert(struct isis_vertex_queue
*queue
,
251 struct isis_vertex
*vertex
)
253 assert(queue
->insert_counter
);
254 vertex
->insert_counter
= queue
->insert_counter
++;
255 assert(queue
->insert_counter
!= (uint64_t)-1);
257 skiplist_insert(queue
->l
.slist
, vertex
, vertex
);
259 struct isis_vertex
*inserted
;
260 inserted
= hash_get(queue
->hash
, vertex
, hash_alloc_intern
);
261 assert(inserted
== vertex
);
264 __attribute__((__unused__
))
265 static struct isis_vertex
*
266 isis_vertex_queue_pop(struct isis_vertex_queue
*queue
)
268 assert(queue
->insert_counter
);
270 struct isis_vertex
*rv
;
272 if (skiplist_first(queue
->l
.slist
, NULL
, (void **)&rv
))
275 skiplist_delete_first(queue
->l
.slist
);
276 hash_release(queue
->hash
, rv
);
281 __attribute__((__unused__
))
282 static void isis_vertex_queue_delete(struct isis_vertex_queue
*queue
,
283 struct isis_vertex
*vertex
)
285 assert(queue
->insert_counter
);
287 skiplist_delete(queue
->l
.slist
, vertex
, vertex
);
288 hash_release(queue
->hash
, vertex
);
291 #define ALL_QUEUE_ELEMENTS_RO(queue, node, data) \
292 ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data)
294 /* End of vertex queue definitions */
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 */
309 enum spf_tree_id tree_id
;
310 bool hopcount_metric
;
313 __attribute__((__unused__
))
314 static void isis_vertex_id_init(struct isis_vertex
*vertex
, const void *id
,
315 enum vertextype vtype
)
317 vertex
->type
= vtype
;
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
));
324 flog_err(EC_LIB_DEVELOPMENT
, "Unknown Vertex Type");
328 __attribute__((__unused__
))
329 static struct isis_vertex
*isis_find_vertex(struct isis_vertex_queue
*queue
,
331 enum vertextype vtype
)
333 struct isis_vertex querier
;
335 isis_vertex_id_init(&querier
, id
, vtype
);
336 return hash_lookup(queue
->hash
, &querier
);
339 __attribute__((__unused__
))
340 static struct isis_lsp
*lsp_for_vertex(struct isis_spftree
*spftree
,
341 struct isis_vertex
*vertex
)
343 uint8_t lsp_id
[ISIS_SYS_ID_LEN
+ 2];
345 assert(VTYPE_IS(vertex
->type
));
347 memcpy(lsp_id
, vertex
->N
.id
, ISIS_SYS_ID_LEN
+ 1);
348 LSP_FRAGMENT(lsp_id
) = 0;
350 dict_t
*lspdb
= spftree
->area
->lspdb
[spftree
->level
- 1];
351 struct isis_lsp
*lsp
= lsp_search(lsp_id
, lspdb
);
353 if (lsp
&& lsp
->hdr
.rem_lifetime
!= 0)
359 #define VID2STR_BUFFER SRCDEST2STR_BUFFER
360 const char *vid2string(struct isis_vertex
*vertex
, char *buff
, int size
);