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
;
53 struct isis_vertex_adj
{
54 struct isis_spf_adj
*sadj
;
55 struct isis_sr_psid_info sr
;
56 struct mpls_label_stack
*label_stack
;
61 * Triple <N, d(N), {Adj(N)}>
66 uint8_t id
[ISIS_SYS_ID_LEN
+ 1];
69 struct isis_sr_psid_info sr
;
70 enum spf_prefix_priority priority
;
73 uint32_t d_N
; /* d(N) Distance from this IS */
74 uint16_t depth
; /* The depth in the imaginary tree */
75 struct list
*Adj_N
; /* {Adj(N)} next hop or neighbor list */
76 struct list
*parents
; /* list of parents for ECMP */
77 struct hash
*firsthops
; /* first two hops to neighbor */
78 uint64_t insert_counter
;
81 /* Vertex Queue and associated functions */
83 struct isis_vertex_queue
{
85 struct skiplist
*slist
;
89 uint64_t insert_counter
;
92 __attribute__((__unused__
))
93 static unsigned isis_vertex_queue_hash_key(const void *vp
)
95 const struct isis_vertex
*vertex
= vp
;
97 if (VTYPE_IP(vertex
->type
)) {
100 key
= prefix_hash_key(&vertex
->N
.ip
.p
.dest
);
101 key
= jhash_1word(prefix_hash_key(&vertex
->N
.ip
.p
.src
), key
);
105 return jhash(vertex
->N
.id
, ISIS_SYS_ID_LEN
+ 1, 0x55aa5a5a);
108 __attribute__((__unused__
))
109 static bool isis_vertex_queue_hash_cmp(const void *a
, const void *b
)
111 const struct isis_vertex
*va
= a
, *vb
= b
;
113 if (va
->type
!= vb
->type
)
116 if (VTYPE_IP(va
->type
)) {
117 if (prefix_cmp(&va
->N
.ip
.p
.dest
, &vb
->N
.ip
.p
.dest
))
120 return prefix_cmp((const struct prefix
*)&va
->N
.ip
.p
.src
,
121 (const struct prefix
*)&vb
->N
.ip
.p
.src
)
125 return memcmp(va
->N
.id
, vb
->N
.id
, ISIS_SYS_ID_LEN
+ 1) == 0;
129 * Compares vertizes for sorting in the TENT list. Returns true
130 * if candidate should be considered before current, false otherwise.
132 __attribute__((__unused__
)) static int isis_vertex_queue_tent_cmp(const void *a
,
135 const struct isis_vertex
*va
= a
;
136 const struct isis_vertex
*vb
= b
;
138 if (va
->d_N
< vb
->d_N
)
141 if (va
->d_N
> vb
->d_N
)
144 if (va
->type
< vb
->type
)
147 if (va
->type
> vb
->type
)
150 if (va
->insert_counter
< vb
->insert_counter
)
153 if (va
->insert_counter
> vb
->insert_counter
)
159 __attribute__((__unused__
))
160 static struct skiplist
*isis_vertex_queue_skiplist(void)
162 return skiplist_new(0, isis_vertex_queue_tent_cmp
, NULL
);
165 __attribute__((__unused__
))
166 static void isis_vertex_queue_init(struct isis_vertex_queue
*queue
,
167 const char *name
, bool ordered
)
170 queue
->insert_counter
= 1;
171 queue
->l
.slist
= isis_vertex_queue_skiplist();
173 queue
->insert_counter
= 0;
174 queue
->l
.list
= list_new();
176 queue
->hash
= hash_create(isis_vertex_queue_hash_key
,
177 isis_vertex_queue_hash_cmp
, name
);
180 __attribute__((__unused__
))
181 static void isis_vertex_del(struct isis_vertex
*vertex
)
183 list_delete(&vertex
->Adj_N
);
184 list_delete(&vertex
->parents
);
185 if (vertex
->firsthops
) {
186 hash_clean(vertex
->firsthops
, NULL
);
187 hash_free(vertex
->firsthops
);
188 vertex
->firsthops
= NULL
;
191 memset(vertex
, 0, sizeof(struct isis_vertex
));
192 XFREE(MTYPE_ISIS_VERTEX
, vertex
);
195 bool isis_vertex_adj_exists(const struct isis_spftree
*spftree
,
196 const struct isis_vertex
*vertex
,
197 const struct isis_spf_adj
*sadj
);
198 void isis_vertex_adj_free(void *arg
);
199 struct isis_vertex_adj
*
200 isis_vertex_adj_add(struct isis_spftree
*spftree
, struct isis_vertex
*vertex
,
201 struct list
*vadj_list
, struct isis_spf_adj
*sadj
,
202 struct isis_prefix_sid
*psid
, bool last_hop
);
204 __attribute__((__unused__
))
205 static void isis_vertex_queue_clear(struct isis_vertex_queue
*queue
)
207 hash_clean(queue
->hash
, NULL
);
209 if (queue
->insert_counter
) {
210 struct isis_vertex
*vertex
;
211 while (0 == skiplist_first(queue
->l
.slist
, NULL
,
213 isis_vertex_del(vertex
);
214 skiplist_delete_first(queue
->l
.slist
);
216 queue
->insert_counter
= 1;
218 queue
->l
.list
->del
= (void (*)(void *))isis_vertex_del
;
219 list_delete_all_node(queue
->l
.list
);
220 queue
->l
.list
->del
= NULL
;
224 __attribute__((__unused__
))
225 static void isis_vertex_queue_free(struct isis_vertex_queue
*queue
)
227 isis_vertex_queue_clear(queue
);
229 hash_free(queue
->hash
);
232 if (queue
->insert_counter
) {
233 skiplist_free(queue
->l
.slist
);
234 queue
->l
.slist
= NULL
;
236 list_delete(&queue
->l
.list
);
239 __attribute__((__unused__
))
240 static unsigned int isis_vertex_queue_count(struct isis_vertex_queue
*queue
)
242 return hashcount(queue
->hash
);
245 __attribute__((__unused__
))
246 static void isis_vertex_queue_append(struct isis_vertex_queue
*queue
,
247 struct isis_vertex
*vertex
)
249 assert(!queue
->insert_counter
);
251 listnode_add(queue
->l
.list
, vertex
);
253 struct isis_vertex
*inserted
;
255 inserted
= hash_get(queue
->hash
, vertex
, hash_alloc_intern
);
256 assert(inserted
== vertex
);
259 __attribute__((__unused__
))
260 static struct isis_vertex
*isis_vertex_queue_last(struct isis_vertex_queue
*queue
)
262 struct listnode
*tail
;
264 assert(!queue
->insert_counter
);
265 tail
= listtail(queue
->l
.list
);
267 return listgetdata(tail
);
270 __attribute__((__unused__
))
271 static void isis_vertex_queue_insert(struct isis_vertex_queue
*queue
,
272 struct isis_vertex
*vertex
)
274 assert(queue
->insert_counter
);
275 vertex
->insert_counter
= queue
->insert_counter
++;
276 assert(queue
->insert_counter
!= (uint64_t)-1);
278 skiplist_insert(queue
->l
.slist
, vertex
, vertex
);
280 struct isis_vertex
*inserted
;
281 inserted
= hash_get(queue
->hash
, vertex
, hash_alloc_intern
);
282 assert(inserted
== vertex
);
285 __attribute__((__unused__
))
286 static struct isis_vertex
*
287 isis_vertex_queue_pop(struct isis_vertex_queue
*queue
)
289 assert(queue
->insert_counter
);
291 struct isis_vertex
*rv
;
293 if (skiplist_first(queue
->l
.slist
, NULL
, (void **)&rv
))
296 skiplist_delete_first(queue
->l
.slist
);
297 hash_release(queue
->hash
, rv
);
302 __attribute__((__unused__
))
303 static void isis_vertex_queue_delete(struct isis_vertex_queue
*queue
,
304 struct isis_vertex
*vertex
)
306 assert(queue
->insert_counter
);
308 skiplist_delete(queue
->l
.slist
, vertex
, vertex
);
309 hash_release(queue
->hash
, vertex
);
312 #define ALL_QUEUE_ELEMENTS_RO(queue, node, data) \
313 ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data)
315 /* End of vertex queue definitions */
317 struct isis_spftree
{
318 struct isis_vertex_queue paths
; /* the SPT */
319 struct isis_vertex_queue tents
; /* TENT */
320 struct route_table
*route_table
;
321 struct route_table
*route_table_backup
;
322 struct lspdb_head
*lspdb
; /* link-state db */
323 struct hash
*prefix_sids
; /* SR Prefix-SIDs. */
324 struct list
*sadj_list
;
325 struct isis_spf_nodes adj_nodes
;
326 struct isis_area
*area
; /* back pointer to area */
327 unsigned int runcount
; /* number of runs since uptime */
328 time_t last_run_timestamp
; /* last run timestamp as wall time for display */
329 time_t last_run_monotime
; /* last run as monotime for scheduling */
330 time_t last_run_duration
; /* last run duration in msec */
333 uint8_t sysid
[ISIS_SYS_ID_LEN
];
337 enum spf_tree_id tree_id
;
339 /* Original pre-failure local SPTs. */
341 struct isis_spftree
*spftree
;
342 struct isis_spftree
*spftree_reverse
;
345 /* Protected resource. */
346 struct lfa_protected_resource protected_resource
;
348 /* P-space and Q-space. */
349 struct isis_spf_nodes p_space
;
350 struct isis_spf_nodes q_space
;
352 /* Protection counters. */
354 uint32_t lfa
[SPF_PREFIX_PRIO_MAX
];
355 uint32_t rlfa
[SPF_PREFIX_PRIO_MAX
];
356 uint32_t tilfa
[SPF_PREFIX_PRIO_MAX
];
357 uint32_t ecmp
[SPF_PREFIX_PRIO_MAX
];
358 uint32_t total
[SPF_PREFIX_PRIO_MAX
];
359 } protection_counters
;
363 #define F_SPFTREE_HOPCOUNT_METRIC 0x01
364 #define F_SPFTREE_NO_ROUTES 0x02
365 #define F_SPFTREE_NO_ADJACENCIES 0x04
367 __attribute__((__unused__
))
368 static void isis_vertex_id_init(struct isis_vertex
*vertex
, const void *id
,
369 enum vertextype vtype
)
371 vertex
->type
= vtype
;
373 if (VTYPE_IS(vtype
) || VTYPE_ES(vtype
)) {
374 memcpy(vertex
->N
.id
, id
, ISIS_SYS_ID_LEN
+ 1);
375 } else if (VTYPE_IP(vtype
)) {
376 memcpy(&vertex
->N
.ip
.p
, id
, sizeof(vertex
->N
.ip
.p
));
378 flog_err(EC_LIB_DEVELOPMENT
, "Unknown Vertex Type");
382 __attribute__((__unused__
))
383 static struct isis_vertex
*isis_find_vertex(struct isis_vertex_queue
*queue
,
385 enum vertextype vtype
)
387 struct isis_vertex querier
;
389 isis_vertex_id_init(&querier
, id
, vtype
);
390 return hash_lookup(queue
->hash
, &querier
);
393 __attribute__((__unused__
))
394 static struct isis_lsp
*lsp_for_vertex(struct isis_spftree
*spftree
,
395 struct isis_vertex
*vertex
)
397 uint8_t lsp_id
[ISIS_SYS_ID_LEN
+ 2];
399 assert(VTYPE_IS(vertex
->type
));
401 memcpy(lsp_id
, vertex
->N
.id
, ISIS_SYS_ID_LEN
+ 1);
402 LSP_FRAGMENT(lsp_id
) = 0;
404 struct isis_lsp
*lsp
= lsp_search(spftree
->lspdb
, lsp_id
);
406 if (lsp
&& lsp
->hdr
.rem_lifetime
!= 0)
412 #define VID2STR_BUFFER SRCDEST2STR_BUFFER
413 const char *vtype2string(enum vertextype vtype
);
414 const char *vid2string(const struct isis_vertex
*vertex
, char *buff
, int size
);