[mirror_frr.git] / isisd / isis_spf_private.h

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * IS-IS Rout(e)ing protocol                  - isis_spf_private.h
 *
 * Copyright (C) 2001,2002   Sampo Saaristo
 *                           Tampere University of Technology
 *                           Institute of Communications Engineering
 * Copyright (C) 2017        Christian Franke <chris@opensourcerouting.org>
 */
#ifndef ISIS_SPF_PRIVATE_H
#define ISIS_SPF_PRIVATE_H

#include "hash.h"
#include "jhash.h"
#include "skiplist.h"
#include "lib_errors.h"

enum vertextype {
	VTYPE_PSEUDO_IS = 1,
	VTYPE_PSEUDO_TE_IS,
	VTYPE_NONPSEUDO_IS,
	VTYPE_NONPSEUDO_TE_IS,
	VTYPE_ES,
	VTYPE_IPREACH_INTERNAL,
	VTYPE_IPREACH_EXTERNAL,
	VTYPE_IPREACH_TE,
	VTYPE_IP6REACH_INTERNAL,
	VTYPE_IP6REACH_EXTERNAL
};

#define VTYPE_IS(t) ((t) >= VTYPE_PSEUDO_IS && (t) <= VTYPE_NONPSEUDO_TE_IS)
#define VTYPE_ES(t) ((t) == VTYPE_ES)
#define VTYPE_IP(t) ((t) >= VTYPE_IPREACH_INTERNAL && (t) <= VTYPE_IP6REACH_EXTERNAL)

struct prefix_pair {
	struct prefix dest;
	struct prefix_ipv6 src;
};

struct isis_vertex_adj {
	struct isis_spf_adj *sadj;
	struct isis_sr_psid_info sr;
	struct mpls_label_stack *label_stack;
	uint32_t lfa_metric;
};

/*
 * Triple <N, d(N), {Adj(N)}>
 */
struct isis_vertex {
	enum vertextype type;
	union {
		uint8_t id[ISIS_SYS_ID_LEN + 1];
		struct {
			struct prefix_pair p;
			struct isis_sr_psid_info sr;
			enum spf_prefix_priority priority;
		} ip;
	} N;
	uint32_t d_N;	  /* d(N) Distance from this IS      */
	uint16_t depth;	/* The depth in the imaginary tree */
	struct list *Adj_N;    /* {Adj(N)} next hop or neighbor list */
	struct list *parents;  /* list of parents for ECMP */
	struct hash *firsthops; /* first two hops to neighbor */
	uint64_t insert_counter;
	uint8_t flags;
};
#define F_ISIS_VERTEX_LFA_PROTECTED	0x01

/* Vertex Queue and associated functions */

struct isis_vertex_queue {
	union {
		struct skiplist *slist;
		struct list *list;
	} l;
	struct hash *hash;
	uint64_t insert_counter;
};

__attribute__((__unused__))
static unsigned isis_vertex_queue_hash_key(const void *vp)
{
	const struct isis_vertex *vertex = vp;

	if (VTYPE_IP(vertex->type)) {
		uint32_t key;

		key = prefix_hash_key(&vertex->N.ip.p.dest);
		key = jhash_1word(prefix_hash_key(&vertex->N.ip.p.src), key);
		return key;
	}

	return jhash(vertex->N.id, ISIS_SYS_ID_LEN + 1, 0x55aa5a5a);
}

__attribute__((__unused__))
static bool isis_vertex_queue_hash_cmp(const void *a, const void *b)
{
	const struct isis_vertex *va = a, *vb = b;

	if (va->type != vb->type)
		return false;

	if (VTYPE_IP(va->type)) {
		if (prefix_cmp(&va->N.ip.p.dest, &vb->N.ip.p.dest))
			return false;

		return prefix_cmp((const struct prefix *)&va->N.ip.p.src,
				  (const struct prefix *)&vb->N.ip.p.src)
		       == 0;
	}

	return memcmp(va->N.id, vb->N.id, ISIS_SYS_ID_LEN + 1) == 0;
}

/*
 * Compares vertizes for sorting in the TENT list. Returns true
 * if candidate should be considered before current, false otherwise.
 */
__attribute__((__unused__)) static int isis_vertex_queue_tent_cmp(const void *a,
								  const void *b)
{
	const struct isis_vertex *va = a;
	const struct isis_vertex *vb = b;

	if (va->d_N < vb->d_N)
		return -1;

	if (va->d_N > vb->d_N)
		return 1;

	if (va->type < vb->type)
		return -1;

	if (va->type > vb->type)
		return 1;

	if (va->insert_counter < vb->insert_counter)
		return -1;

	if (va->insert_counter > vb->insert_counter)
		return 1;

	return 0;
}

__attribute__((__unused__))
static struct skiplist *isis_vertex_queue_skiplist(void)
{
	return skiplist_new(0, isis_vertex_queue_tent_cmp, NULL);
}

__attribute__((__unused__))
static void isis_vertex_queue_init(struct isis_vertex_queue *queue,
				   const char *name, bool ordered)
{
	if (ordered) {
		queue->insert_counter = 1;
		queue->l.slist = isis_vertex_queue_skiplist();
	} else {
		queue->insert_counter = 0;
		queue->l.list = list_new();
	}
	queue->hash = hash_create(isis_vertex_queue_hash_key,
				  isis_vertex_queue_hash_cmp, name);
}

void isis_vertex_del(struct isis_vertex *vertex);

bool isis_vertex_adj_exists(const struct isis_spftree *spftree,
			    const struct isis_vertex *vertex,
			    const struct isis_spf_adj *sadj);
void isis_vertex_adj_free(void *arg);
struct isis_vertex_adj *
isis_vertex_adj_add(struct isis_spftree *spftree, struct isis_vertex *vertex,
		    struct list *vadj_list, struct isis_spf_adj *sadj,
		    struct isis_prefix_sid *psid, bool last_hop);

__attribute__((__unused__))
static void isis_vertex_queue_clear(struct isis_vertex_queue *queue)
{
	hash_clean(queue->hash, NULL);

	if (queue->insert_counter) {
		struct isis_vertex *vertex;
		while (0 == skiplist_first(queue->l.slist, NULL,
					   (void **)&vertex)) {
			isis_vertex_del(vertex);
			skiplist_delete_first(queue->l.slist);
		}
		queue->insert_counter = 1;
	} else {
		queue->l.list->del = (void (*)(void *))isis_vertex_del;
		list_delete_all_node(queue->l.list);
		queue->l.list->del = NULL;
	}
}

__attribute__((__unused__))
static void isis_vertex_queue_free(struct isis_vertex_queue *queue)
{
	isis_vertex_queue_clear(queue);

	hash_free(queue->hash);
	queue->hash = NULL;

	if (queue->insert_counter) {
		skiplist_free(queue->l.slist);
		queue->l.slist = NULL;
	} else
		list_delete(&queue->l.list);
}

__attribute__((__unused__))
static unsigned int isis_vertex_queue_count(struct isis_vertex_queue *queue)
{
	return hashcount(queue->hash);
}

__attribute__((__unused__))
static void isis_vertex_queue_append(struct isis_vertex_queue *queue,
				     struct isis_vertex *vertex)
{
	assert(!queue->insert_counter);

	listnode_add(queue->l.list, vertex);

	struct isis_vertex *inserted;

	inserted = hash_get(queue->hash, vertex, hash_alloc_intern);
	assert(inserted == vertex);
}

__attribute__((__unused__))
static struct isis_vertex *isis_vertex_queue_last(struct isis_vertex_queue *queue)
{
	struct listnode *tail;

	assert(!queue->insert_counter);
	tail = listtail(queue->l.list);
	assert(tail);
	return listgetdata(tail);
}

__attribute__((__unused__))
static void isis_vertex_queue_insert(struct isis_vertex_queue *queue,
				     struct isis_vertex *vertex)
{
	assert(queue->insert_counter);
	vertex->insert_counter = queue->insert_counter++;
	assert(queue->insert_counter != (uint64_t)-1);

	skiplist_insert(queue->l.slist, vertex, vertex);

	struct isis_vertex *inserted;
	inserted = hash_get(queue->hash, vertex, hash_alloc_intern);
	assert(inserted == vertex);
}

__attribute__((__unused__))
static struct isis_vertex *
isis_vertex_queue_pop(struct isis_vertex_queue *queue)
{
	assert(queue->insert_counter);

	struct isis_vertex *rv;

	if (skiplist_first(queue->l.slist, NULL, (void **)&rv))
		return NULL;

	skiplist_delete_first(queue->l.slist);
	hash_release(queue->hash, rv);

	return rv;
}

__attribute__((__unused__))
static void isis_vertex_queue_delete(struct isis_vertex_queue *queue,
				     struct isis_vertex *vertex)
{
	assert(queue->insert_counter);

	skiplist_delete(queue->l.slist, vertex, vertex);
	hash_release(queue->hash, vertex);
}

#define ALL_QUEUE_ELEMENTS_RO(queue, node, data)                               \
	ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data)

/* End of vertex queue definitions */

struct isis_spftree {
	struct isis_vertex_queue paths; /* the SPT */
	struct isis_vertex_queue tents; /* TENT */
	struct route_table *route_table;
	struct route_table *route_table_backup;
	struct lspdb_head *lspdb; /* link-state db */
	struct hash *prefix_sids; /* SR Prefix-SIDs. */
	struct list *sadj_list;
	struct isis_spf_nodes adj_nodes;
	struct isis_area *area;    /* back pointer to area */
	unsigned int runcount;     /* number of runs since uptime */
	time_t last_run_timestamp; /* last run timestamp as wall time for display */
	time_t last_run_monotime;  /* last run as monotime for scheduling */
	time_t last_run_duration;  /* last run duration in msec */

	enum spf_type type;
	uint8_t sysid[ISIS_SYS_ID_LEN];
	uint16_t mtid;
	int family;
	int level;
	enum spf_tree_id tree_id;
	struct {
		/* Original pre-failure local SPTs. */
		struct {
			struct isis_spftree *spftree;
			struct isis_spftree *spftree_reverse;
		} old;

		/* Protected resource. */
		struct lfa_protected_resource protected_resource;

		/* P-space and Q-space. */
		struct isis_spf_nodes p_space;
		struct isis_spf_nodes q_space;

		/* Remote LFA related information. */
		struct {
			/* List of RLFAs eligible to be installed. */
			struct rlfa_tree_head rlfas;

			/*
			 * RLFA post-convergence SPTs (needed to activate RLFAs
			 * once label information is received from LDP).
			 */
			struct list *pc_spftrees;

			/* RLFA maximum metric (or zero if absent). */
			uint32_t max_metric;
		} remote;

		/* Protection counters. */
		struct {
			uint32_t lfa[SPF_PREFIX_PRIO_MAX];
			uint32_t rlfa[SPF_PREFIX_PRIO_MAX];
			uint32_t tilfa[SPF_PREFIX_PRIO_MAX];
			uint32_t ecmp[SPF_PREFIX_PRIO_MAX];
			uint32_t total[SPF_PREFIX_PRIO_MAX];
		} protection_counters;
	} lfa;
	uint8_t algorithm;
	uint8_t flags;
};
#define F_SPFTREE_HOPCOUNT_METRIC 0x01
#define F_SPFTREE_NO_ROUTES 0x02
#define F_SPFTREE_NO_ADJACENCIES 0x04
#ifndef FABRICD
/* flex-algo */
#define F_SPFTREE_DISABLED 0x08
#endif /* ifndef FABRICD */

__attribute__((__unused__))
static void isis_vertex_id_init(struct isis_vertex *vertex, const void *id,
				enum vertextype vtype)
{
	vertex->type = vtype;

	if (VTYPE_IS(vtype) || VTYPE_ES(vtype)) {
		memcpy(vertex->N.id, id, ISIS_SYS_ID_LEN + 1);
	} else if (VTYPE_IP(vtype)) {
		memcpy(&vertex->N.ip.p, id, sizeof(vertex->N.ip.p));
	} else {
		flog_err(EC_LIB_DEVELOPMENT, "Unknown Vertex Type");
	}
}

__attribute__((__unused__))
static struct isis_vertex *isis_find_vertex(struct isis_vertex_queue *queue,
					    const void *id,
					    enum vertextype vtype)
{
	struct isis_vertex querier;

	isis_vertex_id_init(&querier, id, vtype);
	return hash_lookup(queue->hash, &querier);
}

__attribute__((__unused__))
static struct isis_lsp *lsp_for_vertex(struct isis_spftree *spftree,
				       struct isis_vertex *vertex)
{
	uint8_t lsp_id[ISIS_SYS_ID_LEN + 2];

	assert(VTYPE_IS(vertex->type));

	memcpy(lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1);
	LSP_FRAGMENT(lsp_id) = 0;

	struct isis_lsp *lsp = lsp_search(spftree->lspdb, lsp_id);

	if (lsp && lsp->hdr.rem_lifetime != 0)
		return lsp;

	return NULL;
}

#define VID2STR_BUFFER SRCDEST2STR_BUFFER
const char *vtype2string(enum vertextype vtype);
const char *vid2string(const struct isis_vertex *vertex, char *buff, int size);

#endif
Commit	Line	Data
acddc0ed	1	// SPDX-License-Identifier: GPL-2.0-or-later
cbd8e49e CF	2	/*
	3	* IS-IS Rout(e)ing protocol - isis_spf_private.h
	4	*
	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>
cbd8e49e CF	9	*/
	10	#ifndef ISIS_SPF_PRIVATE_H
	11	#define ISIS_SPF_PRIVATE_H
	12
	13	#include "hash.h"
	14	#include "jhash.h"
	15	#include "skiplist.h"
	16	#include "lib_errors.h"
	17
	18	enum vertextype {
	19	VTYPE_PSEUDO_IS = 1,
	20	VTYPE_PSEUDO_TE_IS,
	21	VTYPE_NONPSEUDO_IS,
	22	VTYPE_NONPSEUDO_TE_IS,
	23	VTYPE_ES,
	24	VTYPE_IPREACH_INTERNAL,
	25	VTYPE_IPREACH_EXTERNAL,
	26	VTYPE_IPREACH_TE,
	27	VTYPE_IP6REACH_INTERNAL,
	28	VTYPE_IP6REACH_EXTERNAL
	29	};
	30
	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)
	34
	35	struct prefix_pair {
	36	struct prefix dest;
	37	struct prefix_ipv6 src;
	38	};
	39
7b36d36e RW	40	struct isis_vertex_adj {
7b36d36e RW	41	struct isis_spf_adj *sadj;
d47d6089	42	struct isis_sr_psid_info sr;
7b36d36e	43	struct mpls_label_stack *label_stack;
e886416f	44	uint32_t lfa_metric;
7b36d36e RW	45	};
7b36d36e RW	46
cbd8e49e CF	47	/*
	48	* Triple <N, d(N), {Adj(N)}>
	49	*/
cbd8e49e CF	50	struct isis_vertex {
cbd8e49e CF	51	enum vertextype type;
f6ae63ca CF	52	union {
f6ae63ca CF	53	uint8_t id[ISIS_SYS_ID_LEN + 1];
d47d6089 RW	54	struct {
	55	struct prefix_pair p;
	56	struct isis_sr_psid_info sr;
e886416f	57	enum spf_prefix_priority priority;
d47d6089	58	} ip;
f6ae63ca	59	} N;
cbd8e49e CF	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 */
686afe9f	64	struct hash firsthops; / first two hops to neighbor */
cbd8e49e	65	uint64_t insert_counter;
16fe8cff	66	uint8_t flags;
cbd8e49e	67	};
16fe8cff	68	#define F_ISIS_VERTEX_LFA_PROTECTED 0x01
cbd8e49e CF	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__))
d8b87afe	82	static unsigned isis_vertex_queue_hash_key(const void *vp)
cbd8e49e	83	{
d8b87afe	84	const struct isis_vertex *vertex = vp;
cbd8e49e CF	85
	86	if (VTYPE_IP(vertex->type)) {
	87	uint32_t key;
	88
d47d6089 RW	89	key = prefix_hash_key(&vertex->N.ip.p.dest);
d47d6089 RW	90	key = jhash_1word(prefix_hash_key(&vertex->N.ip.p.src), key);
cbd8e49e CF	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
cbd8e49e CF	105	if (VTYPE_IP(va->type)) {
d47d6089	106	if (prefix_cmp(&va->N.ip.p.dest, &vb->N.ip.p.dest))
74df8d6d	107	return false;
cbd8e49e	108
d47d6089 RW	109	return prefix_cmp((const struct prefix *)&va->N.ip.p.src,
	110	(const struct prefix *)&vb->N.ip.p.src)
	111	== 0;
cbd8e49e CF	112	}
	113
	114	return memcmp(va->N.id, vb->N.id, ISIS_SYS_ID_LEN + 1) == 0;
	115	}
	116
	117	/*
	118	* Compares vertizes for sorting in the TENT list. Returns true
	119	* if candidate should be considered before current, false otherwise.
	120	*/
1a4189d4 DS	121	__attribute__((__unused__)) static int isis_vertex_queue_tent_cmp(const void *a,
1a4189d4 DS	122	const void *b)
cbd8e49e	123	{
1a4189d4 DS	124	const struct isis_vertex *va = a;
1a4189d4 DS	125	const struct isis_vertex *vb = b;
cbd8e49e CF	126
	127	if (va->d_N < vb->d_N)
	128	return -1;
	129
	130	if (va->d_N > vb->d_N)
	131	return 1;
	132
	133	if (va->type < vb->type)
	134	return -1;
	135
	136	if (va->type > vb->type)
	137	return 1;
	138
	139	if (va->insert_counter < vb->insert_counter)
	140	return -1;
	141
	142	if (va->insert_counter > vb->insert_counter)
	143	return 1;
	144
	145	return 0;
	146	}
	147
	148	__attribute__((__unused__))
	149	static struct skiplist *isis_vertex_queue_skiplist(void)
	150	{
	151	return skiplist_new(0, isis_vertex_queue_tent_cmp, NULL);
	152	}
	153
	154	__attribute__((__unused__))
	155	static void isis_vertex_queue_init(struct isis_vertex_queue *queue,
	156	const char *name, bool ordered)
	157	{
	158	if (ordered) {
	159	queue->insert_counter = 1;
	160	queue->l.slist = isis_vertex_queue_skiplist();
	161	} else {
	162	queue->insert_counter = 0;
	163	queue->l.list = list_new();
	164	}
	165	queue->hash = hash_create(isis_vertex_queue_hash_key,
	166	isis_vertex_queue_hash_cmp, name);
	167	}
	168
66b9a381	169	void isis_vertex_del(struct isis_vertex *vertex);
cbd8e49e	170
7b36d36e RW	171	bool isis_vertex_adj_exists(const struct isis_spftree *spftree,
	172	const struct isis_vertex *vertex,
	173	const struct isis_spf_adj *sadj);
e886416f RW	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);
7b36d36e	179
cbd8e49e CF	180	__attribute__((__unused__))
	181	static void isis_vertex_queue_clear(struct isis_vertex_queue *queue)
	182	{
	183	hash_clean(queue->hash, NULL);
	184
	185	if (queue->insert_counter) {
	186	struct isis_vertex *vertex;
	187	while (0 == skiplist_first(queue->l.slist, NULL,
	188	(void **)&vertex)) {
	189	isis_vertex_del(vertex);
	190	skiplist_delete_first(queue->l.slist);
	191	}
	192	queue->insert_counter = 1;
	193	} else {
	194	queue->l.list->del = (void ()(void ))isis_vertex_del;
	195	list_delete_all_node(queue->l.list);
	196	queue->l.list->del = NULL;
	197	}
	198	}
	199
	200	__attribute__((__unused__))
	201	static void isis_vertex_queue_free(struct isis_vertex_queue *queue)
	202	{
	203	isis_vertex_queue_clear(queue);
	204
	205	hash_free(queue->hash);
	206	queue->hash = NULL;
	207
	208	if (queue->insert_counter) {
	209	skiplist_free(queue->l.slist);
	210	queue->l.slist = NULL;
	211	} else
6a154c88	212	list_delete(&queue->l.list);
cbd8e49e CF	213	}
	214
	215	__attribute__((__unused__))
	216	static unsigned int isis_vertex_queue_count(struct isis_vertex_queue *queue)
	217	{
	218	return hashcount(queue->hash);
	219	}
	220
	221	__attribute__((__unused__))
	222	static void isis_vertex_queue_append(struct isis_vertex_queue *queue,
	223	struct isis_vertex *vertex)
	224	{
	225	assert(!queue->insert_counter);
	226
	227	listnode_add(queue->l.list, vertex);
	228
	229	struct isis_vertex *inserted;
	230
	231	inserted = hash_get(queue->hash, vertex, hash_alloc_intern);
	232	assert(inserted == vertex);
	233	}
	234
	235	__attribute__((__unused__))
	236	static struct isis_vertex isis_vertex_queue_last(struct isis_vertex_queue queue)
	237	{
3be6e411	238	struct listnode *tail;
cbd8e49e	239
3be6e411 DL	240	assert(!queue->insert_counter);
	241	tail = listtail(queue->l.list);
	242	assert(tail);
	243	return listgetdata(tail);
cbd8e49e CF	244	}
	245
	246	__attribute__((__unused__))
	247	static void isis_vertex_queue_insert(struct isis_vertex_queue *queue,
	248	struct isis_vertex *vertex)
	249	{
	250	assert(queue->insert_counter);
	251	vertex->insert_counter = queue->insert_counter++;
	252	assert(queue->insert_counter != (uint64_t)-1);
	253
	254	skiplist_insert(queue->l.slist, vertex, vertex);
	255
	256	struct isis_vertex *inserted;
	257	inserted = hash_get(queue->hash, vertex, hash_alloc_intern);
	258	assert(inserted == vertex);
	259	}
	260
	261	__attribute__((__unused__))
	262	static struct isis_vertex *
	263	isis_vertex_queue_pop(struct isis_vertex_queue *queue)
	264	{
	265	assert(queue->insert_counter);
	266
	267	struct isis_vertex *rv;
	268
	269	if (skiplist_first(queue->l.slist, NULL, (void **)&rv))
	270	return NULL;
	271
	272	skiplist_delete_first(queue->l.slist);
	273	hash_release(queue->hash, rv);
	274
	275	return rv;
	276	}
	277
	278	__attribute__((__unused__))
	279	static void isis_vertex_queue_delete(struct isis_vertex_queue *queue,
	280	struct isis_vertex *vertex)
	281	{
	282	assert(queue->insert_counter);
	283
	284	skiplist_delete(queue->l.slist, vertex, vertex);
	285	hash_release(queue->hash, vertex);
	286	}
	287
	288	#define ALL_QUEUE_ELEMENTS_RO(queue, node, data) \
	289	ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data)
	290
	291	/* End of vertex queue definitions */
	292
	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;
c951ee6e	297	struct route_table *route_table_backup;
7b36d36e	298	struct lspdb_head lspdb; / link-state db */
2f7cc7bc	299	struct hash prefix_sids; / SR Prefix-SIDs. */
7b36d36e	300	struct list *sadj_list;
c951ee6e	301	struct isis_spf_nodes adj_nodes;
cbd8e49e CF	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 */
	307
75aa7aa1	308	enum spf_type type;
7b36d36e	309	uint8_t sysid[ISIS_SYS_ID_LEN];
cbd8e49e CF	310	uint16_t mtid;
	311	int family;
	312	int level;
	313	enum spf_tree_id tree_id;
c951ee6e RW	314	struct {
	315	/* Original pre-failure local SPTs. */
	316	struct {
	317	struct isis_spftree *spftree;
	318	struct isis_spftree *spftree_reverse;
	319	} old;
	320
	321	/* Protected resource. */
	322	struct lfa_protected_resource protected_resource;
	323
	324	/* P-space and Q-space. */
	325	struct isis_spf_nodes p_space;
	326	struct isis_spf_nodes q_space;
fc156c28	327
16fe8cff RW	328	/* Remote LFA related information. */
	329	struct {
	330	/* List of RLFAs eligible to be installed. */
	331	struct rlfa_tree_head rlfas;
	332
	333	/*
	334	* RLFA post-convergence SPTs (needed to activate RLFAs
	335	* once label information is received from LDP).
	336	*/
	337	struct list *pc_spftrees;
	338
	339	/* RLFA maximum metric (or zero if absent). */
	340	uint32_t max_metric;
	341	} remote;
	342
fc156c28 RW	343	/* Protection counters. */
	344	struct {
	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;
c951ee6e	351	} lfa;
329f87b3	352	uint8_t algorithm;
7b36d36e	353	uint8_t flags;
cbd8e49e	354	};
7b36d36e RW	355	#define F_SPFTREE_HOPCOUNT_METRIC 0x01
	356	#define F_SPFTREE_NO_ROUTES 0x02
	357	#define F_SPFTREE_NO_ADJACENCIES 0x04
860b75b4 HS	358	#ifndef FABRICD
	359	/* flex-algo */
	360	#define F_SPFTREE_DISABLED 0x08
	361	#endif /* ifndef FABRICD */
cbd8e49e CF	362
cbd8e49e CF	363	__attribute__((__unused__))
f6ae63ca	364	static void isis_vertex_id_init(struct isis_vertex vertex, const void id,
cbd8e49e CF	365	enum vertextype vtype)
	366	{
	367	vertex->type = vtype;
	368
	369	if (VTYPE_IS(vtype) \|\| VTYPE_ES(vtype)) {
f6ae63ca	370	memcpy(vertex->N.id, id, ISIS_SYS_ID_LEN + 1);
cbd8e49e	371	} else if (VTYPE_IP(vtype)) {
d47d6089	372	memcpy(&vertex->N.ip.p, id, sizeof(vertex->N.ip.p));
cbd8e49e	373	} else {
450971aa	374	flog_err(EC_LIB_DEVELOPMENT, "Unknown Vertex Type");
cbd8e49e CF	375	}
	376	}
	377
	378	__attribute__((__unused__))
	379	static struct isis_vertex isis_find_vertex(struct isis_vertex_queue queue,
f6ae63ca	380	const void *id,
cbd8e49e CF	381	enum vertextype vtype)
	382	{
	383	struct isis_vertex querier;
	384
f6ae63ca	385	isis_vertex_id_init(&querier, id, vtype);
cbd8e49e CF	386	return hash_lookup(queue->hash, &querier);
	387	}
	388
	389	__attribute__((__unused__))
	390	static struct isis_lsp lsp_for_vertex(struct isis_spftree spftree,
	391	struct isis_vertex *vertex)
	392	{
	393	uint8_t lsp_id[ISIS_SYS_ID_LEN + 2];
	394
	395	assert(VTYPE_IS(vertex->type));
	396
	397	memcpy(lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1);
	398	LSP_FRAGMENT(lsp_id) = 0;
	399
7b36d36e	400	struct isis_lsp *lsp = lsp_search(spftree->lspdb, lsp_id);
cbd8e49e CF	401
	402	if (lsp && lsp->hdr.rem_lifetime != 0)
	403	return lsp;
	404
	405	return NULL;
	406	}
	407
d4cff91a	408	#define VID2STR_BUFFER SRCDEST2STR_BUFFER
c951ee6e RW	409	const char *vtype2string(enum vertextype vtype);
c951ee6e RW	410	const char vid2string(const struct isis_vertex vertex, char *buff, int size);
d4cff91a	411
cbd8e49e	412	#endif