1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * IS-IS Rout(e)ing protocol - isis_spf_private.h
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>
10 #ifndef ISIS_SPF_PRIVATE_H
11 #define ISIS_SPF_PRIVATE_H
16 #include "lib_errors.h"
22 VTYPE_NONPSEUDO_TE_IS
,
24 VTYPE_IPREACH_INTERNAL
,
25 VTYPE_IPREACH_EXTERNAL
,
27 VTYPE_IP6REACH_INTERNAL
,
28 VTYPE_IP6REACH_EXTERNAL
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)
37 struct prefix_ipv6 src
;
40 struct isis_vertex_adj
{
41 struct isis_spf_adj
*sadj
;
42 struct isis_sr_psid_info sr
;
43 struct mpls_label_stack
*label_stack
;
48 * Triple <N, d(N), {Adj(N)}>
53 uint8_t id
[ISIS_SYS_ID_LEN
+ 1];
56 struct isis_sr_psid_info sr
;
57 enum spf_prefix_priority priority
;
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 */
64 struct hash
*firsthops
; /* first two hops to neighbor */
65 uint64_t insert_counter
;
68 #define F_ISIS_VERTEX_LFA_PROTECTED 0x01
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(const void *vp
)
84 const struct isis_vertex
*vertex
= vp
;
86 if (VTYPE_IP(vertex
->type
)) {
89 key
= prefix_hash_key(&vertex
->N
.ip
.p
.dest
);
90 key
= jhash_1word(prefix_hash_key(&vertex
->N
.ip
.p
.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
.p
.dest
, &vb
->N
.ip
.p
.dest
))
109 return prefix_cmp((const struct prefix
*)&va
->N
.ip
.p
.src
,
110 (const struct prefix
*)&vb
->N
.ip
.p
.src
)
114 return memcmp(va
->N
.id
, vb
->N
.id
, ISIS_SYS_ID_LEN
+ 1) == 0;
118 * Compares vertizes for sorting in the TENT list. Returns true
119 * if candidate should be considered before current, false otherwise.
121 __attribute__((__unused__
)) static int isis_vertex_queue_tent_cmp(const void *a
,
124 const struct isis_vertex
*va
= a
;
125 const struct isis_vertex
*vb
= b
;
127 if (va
->d_N
< vb
->d_N
)
130 if (va
->d_N
> vb
->d_N
)
133 if (va
->type
< vb
->type
)
136 if (va
->type
> vb
->type
)
139 if (va
->insert_counter
< vb
->insert_counter
)
142 if (va
->insert_counter
> vb
->insert_counter
)
148 __attribute__((__unused__
))
149 static struct skiplist
*isis_vertex_queue_skiplist(void)
151 return skiplist_new(0, isis_vertex_queue_tent_cmp
, NULL
);
154 __attribute__((__unused__
))
155 static void isis_vertex_queue_init(struct isis_vertex_queue
*queue
,
156 const char *name
, bool ordered
)
159 queue
->insert_counter
= 1;
160 queue
->l
.slist
= isis_vertex_queue_skiplist();
162 queue
->insert_counter
= 0;
163 queue
->l
.list
= list_new();
165 queue
->hash
= hash_create(isis_vertex_queue_hash_key
,
166 isis_vertex_queue_hash_cmp
, name
);
169 void isis_vertex_del(struct isis_vertex
*vertex
);
171 bool isis_vertex_adj_exists(const struct isis_spftree
*spftree
,
172 const struct isis_vertex
*vertex
,
173 const struct isis_spf_adj
*sadj
);
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
);
180 __attribute__((__unused__
))
181 static void isis_vertex_queue_clear(struct isis_vertex_queue
*queue
)
183 hash_clean(queue
->hash
, NULL
);
185 if (queue
->insert_counter
) {
186 struct isis_vertex
*vertex
;
187 while (0 == skiplist_first(queue
->l
.slist
, NULL
,
189 isis_vertex_del(vertex
);
190 skiplist_delete_first(queue
->l
.slist
);
192 queue
->insert_counter
= 1;
194 queue
->l
.list
->del
= (void (*)(void *))isis_vertex_del
;
195 list_delete_all_node(queue
->l
.list
);
196 queue
->l
.list
->del
= NULL
;
200 __attribute__((__unused__
))
201 static void isis_vertex_queue_free(struct isis_vertex_queue
*queue
)
203 isis_vertex_queue_clear(queue
);
205 hash_free(queue
->hash
);
208 if (queue
->insert_counter
) {
209 skiplist_free(queue
->l
.slist
);
210 queue
->l
.slist
= NULL
;
212 list_delete(&queue
->l
.list
);
215 __attribute__((__unused__
))
216 static unsigned int isis_vertex_queue_count(struct isis_vertex_queue
*queue
)
218 return hashcount(queue
->hash
);
221 __attribute__((__unused__
))
222 static void isis_vertex_queue_append(struct isis_vertex_queue
*queue
,
223 struct isis_vertex
*vertex
)
225 assert(!queue
->insert_counter
);
227 listnode_add(queue
->l
.list
, vertex
);
229 struct isis_vertex
*inserted
;
231 inserted
= hash_get(queue
->hash
, vertex
, hash_alloc_intern
);
232 assert(inserted
== vertex
);
235 __attribute__((__unused__
))
236 static struct isis_vertex
*isis_vertex_queue_last(struct isis_vertex_queue
*queue
)
238 struct listnode
*tail
;
240 assert(!queue
->insert_counter
);
241 tail
= listtail(queue
->l
.list
);
243 return listgetdata(tail
);
246 __attribute__((__unused__
))
247 static void isis_vertex_queue_insert(struct isis_vertex_queue
*queue
,
248 struct isis_vertex
*vertex
)
250 assert(queue
->insert_counter
);
251 vertex
->insert_counter
= queue
->insert_counter
++;
252 assert(queue
->insert_counter
!= (uint64_t)-1);
254 skiplist_insert(queue
->l
.slist
, vertex
, vertex
);
256 struct isis_vertex
*inserted
;
257 inserted
= hash_get(queue
->hash
, vertex
, hash_alloc_intern
);
258 assert(inserted
== vertex
);
261 __attribute__((__unused__
))
262 static struct isis_vertex
*
263 isis_vertex_queue_pop(struct isis_vertex_queue
*queue
)
265 assert(queue
->insert_counter
);
267 struct isis_vertex
*rv
;
269 if (skiplist_first(queue
->l
.slist
, NULL
, (void **)&rv
))
272 skiplist_delete_first(queue
->l
.slist
);
273 hash_release(queue
->hash
, rv
);
278 __attribute__((__unused__
))
279 static void isis_vertex_queue_delete(struct isis_vertex_queue
*queue
,
280 struct isis_vertex
*vertex
)
282 assert(queue
->insert_counter
);
284 skiplist_delete(queue
->l
.slist
, vertex
, vertex
);
285 hash_release(queue
->hash
, vertex
);
288 #define ALL_QUEUE_ELEMENTS_RO(queue, node, data) \
289 ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data)
291 /* End of vertex queue definitions */
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
;
297 struct route_table
*route_table_backup
;
298 struct lspdb_head
*lspdb
; /* link-state db */
299 struct hash
*prefix_sids
; /* SR Prefix-SIDs. */
300 struct list
*sadj_list
;
301 struct isis_spf_nodes adj_nodes
;
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 */
309 uint8_t sysid
[ISIS_SYS_ID_LEN
];
313 enum spf_tree_id tree_id
;
315 /* Original pre-failure local SPTs. */
317 struct isis_spftree
*spftree
;
318 struct isis_spftree
*spftree_reverse
;
321 /* Protected resource. */
322 struct lfa_protected_resource protected_resource
;
324 /* P-space and Q-space. */
325 struct isis_spf_nodes p_space
;
326 struct isis_spf_nodes q_space
;
328 /* Remote LFA related information. */
330 /* List of RLFAs eligible to be installed. */
331 struct rlfa_tree_head rlfas
;
334 * RLFA post-convergence SPTs (needed to activate RLFAs
335 * once label information is received from LDP).
337 struct list
*pc_spftrees
;
339 /* RLFA maximum metric (or zero if absent). */
343 /* Protection counters. */
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
;
354 #define F_SPFTREE_HOPCOUNT_METRIC 0x01
355 #define F_SPFTREE_NO_ROUTES 0x02
356 #define F_SPFTREE_NO_ADJACENCIES 0x04
358 __attribute__((__unused__
))
359 static void isis_vertex_id_init(struct isis_vertex
*vertex
, const void *id
,
360 enum vertextype vtype
)
362 vertex
->type
= vtype
;
364 if (VTYPE_IS(vtype
) || VTYPE_ES(vtype
)) {
365 memcpy(vertex
->N
.id
, id
, ISIS_SYS_ID_LEN
+ 1);
366 } else if (VTYPE_IP(vtype
)) {
367 memcpy(&vertex
->N
.ip
.p
, id
, sizeof(vertex
->N
.ip
.p
));
369 flog_err(EC_LIB_DEVELOPMENT
, "Unknown Vertex Type");
373 __attribute__((__unused__
))
374 static struct isis_vertex
*isis_find_vertex(struct isis_vertex_queue
*queue
,
376 enum vertextype vtype
)
378 struct isis_vertex querier
;
380 isis_vertex_id_init(&querier
, id
, vtype
);
381 return hash_lookup(queue
->hash
, &querier
);
384 __attribute__((__unused__
))
385 static struct isis_lsp
*lsp_for_vertex(struct isis_spftree
*spftree
,
386 struct isis_vertex
*vertex
)
388 uint8_t lsp_id
[ISIS_SYS_ID_LEN
+ 2];
390 assert(VTYPE_IS(vertex
->type
));
392 memcpy(lsp_id
, vertex
->N
.id
, ISIS_SYS_ID_LEN
+ 1);
393 LSP_FRAGMENT(lsp_id
) = 0;
395 struct isis_lsp
*lsp
= lsp_search(spftree
->lspdb
, lsp_id
);
397 if (lsp
&& lsp
->hdr
.rem_lifetime
!= 0)
403 #define VID2STR_BUFFER SRCDEST2STR_BUFFER
404 const char *vtype2string(enum vertextype vtype
);
405 const char *vid2string(const struct isis_vertex
*vertex
, char *buff
, int size
);