[mirror_frr.git] / ldpd / rlfa.c

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Copyright (C) 2020  NetDEF, Inc.
 *                     Renato Westphal
 */

#include <zebra.h>

#include "ldpd.h"
#include "lde.h"
#include "ldpe.h"
#include "log.h"
#include "ldp_debug.h"
#include "rlfa.h"

#include <lib/log.h>

struct ldp_rlfa_node_head rlfa_node_tree;

static int ldp_rlfa_client_compare(const struct ldp_rlfa_client *a,
				   const struct ldp_rlfa_client *b)
{
	if (a->igp.vrf_id < b->igp.vrf_id)
		return -1;
	if (a->igp.vrf_id > b->igp.vrf_id)
		return 1;

	if (a->igp.protocol < b->igp.protocol)
		return -1;
	if (a->igp.protocol > b->igp.protocol)
		return 1;

	if (a->igp.isis.spf.tree_id < b->igp.isis.spf.tree_id)
		return -1;
	if (a->igp.isis.spf.tree_id > b->igp.isis.spf.tree_id)
		return 1;

	if (a->igp.isis.spf.level < b->igp.isis.spf.level)
		return -1;
	if (a->igp.isis.spf.level > b->igp.isis.spf.level)
		return 1;

	return 0;
}
RB_GENERATE(ldp_rlfa_client_head, ldp_rlfa_client, entry,
	    ldp_rlfa_client_compare)

static int ldp_rlfa_node_compare(const struct ldp_rlfa_node *a,
				 const struct ldp_rlfa_node *b)
{
	if (ntohl(a->pq_address.s_addr) < ntohl(b->pq_address.s_addr))
		return -1;
	if (ntohl(a->pq_address.s_addr) > ntohl(b->pq_address.s_addr))
		return 1;

	return prefix_cmp(&a->destination, &b->destination);
}
RB_GENERATE(ldp_rlfa_node_head, ldp_rlfa_node, entry, ldp_rlfa_node_compare)

struct ldp_rlfa_client *rlfa_client_new(struct ldp_rlfa_node *rnode,
					struct zapi_rlfa_igp *igp)
{
	struct ldp_rlfa_client *rclient;

	if ((rclient = calloc(1, sizeof(*rclient))) == NULL)
		fatal(__func__);

	rclient->igp = *igp;
	rclient->node = rnode;
	RB_INSERT(ldp_rlfa_client_head, &rnode->clients, rclient);

	return rclient;
}

void rlfa_client_del(struct ldp_rlfa_client *rclient)
{
	struct ldp_rlfa_node *rnode = rclient->node;

	RB_REMOVE(ldp_rlfa_client_head, &rnode->clients, rclient);
	free(rclient);

	/* Delete RLFA node if it's empty. */
	if (RB_EMPTY(ldp_rlfa_client_head, &rnode->clients))
		rlfa_node_del(rnode);
}

struct ldp_rlfa_client *rlfa_client_find(struct ldp_rlfa_node *rnode,
					 struct zapi_rlfa_igp *igp)
{
	struct ldp_rlfa_client rclient;

	rclient.igp = *igp;
	return RB_FIND(ldp_rlfa_client_head, &rnode->clients, &rclient);
}

struct ldp_rlfa_node *rlfa_node_new(const struct prefix *destination,
				    struct in_addr pq_address)
{
	struct ldp_rlfa_node *rnode;

	if ((rnode = calloc(1, sizeof(*rnode))) == NULL)
		fatal(__func__);

	rnode->destination = *destination;
	rnode->pq_address = pq_address;
	rnode->pq_label = MPLS_INVALID_LABEL;
	RB_INIT(ldp_rlfa_client_head, &rnode->clients);
	RB_INSERT(ldp_rlfa_node_head, &rlfa_node_tree, rnode);

	return rnode;
}

void rlfa_node_del(struct ldp_rlfa_node *rnode)
{
	/* Delete RLFA clients. */
	while (!RB_EMPTY(ldp_rlfa_client_head, &rnode->clients)) {
		struct ldp_rlfa_client *rclient;

		rclient = RB_ROOT(ldp_rlfa_client_head, &rnode->clients);
		rlfa_client_del(rclient);
	}

	RB_REMOVE(ldp_rlfa_node_head, &rlfa_node_tree, rnode);
	free(rnode);
}

struct ldp_rlfa_node *rlfa_node_find(const struct prefix *destination,
				     struct in_addr pq_address)
{
	struct ldp_rlfa_node rnode = {};

	rnode.destination = *destination;
	rnode.pq_address = pq_address;
	return RB_FIND(ldp_rlfa_node_head, &rlfa_node_tree, &rnode);
}

void lde_rlfa_client_send(struct ldp_rlfa_client *rclient)
{
	struct ldp_rlfa_node		*rnode = rclient->node;
	struct zapi_rlfa_response	 rlfa_labels = {};
	struct fec			 fec;
	struct fec_node			*fn;
	struct fec_nh			*fnh;
	int				 i = 0;

	/* Fill in inner label (allocated by PQ node). */
	rlfa_labels.igp = rclient->igp;
	rlfa_labels.destination = rnode->destination;
	rlfa_labels.pq_label = rnode->pq_label;

	/* Fill in outer label(s) (allocated by the nexthop routers). */
	fec.type = FEC_TYPE_IPV4;
	fec.u.ipv4.prefix = rnode->pq_address;
	fec.u.ipv4.prefixlen = IPV4_MAX_BITLEN;
	fn = (struct fec_node *)fec_find(&ft, &fec);
	if (!fn)
		return;
	LIST_FOREACH(fnh, &fn->nexthops, entry) {
		if (fnh->remote_label == NO_LABEL)
			continue;

		rlfa_labels.nexthops[i].family = fnh->af;
		switch (fnh->af) {
		case AF_INET:
			rlfa_labels.nexthops[i].gate.ipv4 = fnh->nexthop.v4;
			break;
		case AF_INET6:
			rlfa_labels.nexthops[i].gate.ipv6 = fnh->nexthop.v6;
			break;
		default:
			continue;
		}
		rlfa_labels.nexthops[i].label = fnh->remote_label;
		i++;
	}
	rlfa_labels.nexthop_num = i;

	lde_imsg_compose_parent(IMSG_RLFA_LABELS, 0, &rlfa_labels,
				sizeof(rlfa_labels));
}

void lde_rlfa_label_update(const struct fec *fec)
{
	struct ldp_rlfa_node *rnode;

	if (fec->type != FEC_TYPE_IPV4
	    || fec->u.ipv4.prefixlen != IPV4_MAX_BITLEN)
		return;

	/*
	 * TODO: use an rb-tree lookup to restrict the iteration to the RLFAs
	 * that were effectivelly affected by the label update.
	 */
	RB_FOREACH (rnode, ldp_rlfa_node_head, &rlfa_node_tree) {
		struct ldp_rlfa_client *rclient;

		if (!IPV4_ADDR_SAME(&rnode->pq_address, &fec->u.ipv4.prefix))
			continue;

		RB_FOREACH (rclient, ldp_rlfa_client_head, &rnode->clients)
			lde_rlfa_client_send(rclient);
	}
}

void lde_rlfa_check(struct ldp_rlfa_client *rclient)
{
	struct lde_nbr *ln;
	struct lde_map *me;
	struct fec fec;
	union ldpd_addr pq_address = {};

	pq_address.v4 = rclient->node->pq_address;
	ln = lde_nbr_find_by_addr(AF_INET, &pq_address);
	if (!ln)
		return;

	lde_prefix2fec(&rclient->node->destination, &fec);
	me = (struct lde_map *)fec_find(&ln->recv_map, &fec);
	if (!me)
		return;

	rclient->node->pq_label = me->map.label;
	lde_rlfa_client_send(rclient);
}

/*
 * Check if there's any registered RLFA client for this prefix/neighbor (PQ
 * node) and notify about the updated label.
 */
void lde_rlfa_update_clients(struct fec *fec, struct lde_nbr *ln,
			     uint32_t label)
{
	struct prefix		 rlfa_dest;
	struct ldp_rlfa_node	*rnode;

	lde_fec2prefix(fec, &rlfa_dest);
	rnode = rlfa_node_find(&rlfa_dest, ln->id);
	if (rnode) {
		struct ldp_rlfa_client *rclient;

		rnode->pq_label = label;
		RB_FOREACH (rclient, ldp_rlfa_client_head, &rnode->clients)
			lde_rlfa_client_send(rclient);
	} else
		lde_rlfa_label_update(fec);
}

void ldpe_rlfa_init(struct ldp_rlfa_client *rclient)
{
	struct tnbr *tnbr;
	union ldpd_addr pq_address = {};

	pq_address.v4 = rclient->node->pq_address;
	tnbr = tnbr_find(leconf, AF_INET, &pq_address);
	if (tnbr == NULL) {
		tnbr = tnbr_new(AF_INET, &pq_address);
		tnbr_update(tnbr);
		RB_INSERT(tnbr_head, &leconf->tnbr_tree, tnbr);
	}

	tnbr->rlfa_count++;
}

void ldpe_rlfa_exit(struct ldp_rlfa_client *rclient)
{
	struct tnbr *tnbr;
	union ldpd_addr pq_address = {};

	pq_address.v4 = rclient->node->pq_address;
	tnbr = tnbr_find(leconf, AF_INET, &pq_address);
	if (tnbr) {
		tnbr->rlfa_count--;
		tnbr_check(leconf, tnbr);
	}
}
Commit	Line	Data
acddc0ed	1	// SPDX-License-Identifier: GPL-2.0-or-later
077d336a RW	2	/*
	3	* Copyright (C) 2020 NetDEF, Inc.
	4	* Renato Westphal
077d336a RW	5	*/
	6
	7	#include <zebra.h>
	8
	9	#include "ldpd.h"
	10	#include "lde.h"
	11	#include "ldpe.h"
	12	#include "log.h"
	13	#include "ldp_debug.h"
	14	#include "rlfa.h"
	15
	16	#include <lib/log.h>
	17
	18	struct ldp_rlfa_node_head rlfa_node_tree;
	19
	20	static int ldp_rlfa_client_compare(const struct ldp_rlfa_client *a,
	21	const struct ldp_rlfa_client *b)
	22	{
	23	if (a->igp.vrf_id < b->igp.vrf_id)
	24	return -1;
	25	if (a->igp.vrf_id > b->igp.vrf_id)
	26	return 1;
	27
	28	if (a->igp.protocol < b->igp.protocol)
	29	return -1;
	30	if (a->igp.protocol > b->igp.protocol)
	31	return 1;
	32
	33	if (a->igp.isis.spf.tree_id < b->igp.isis.spf.tree_id)
	34	return -1;
	35	if (a->igp.isis.spf.tree_id > b->igp.isis.spf.tree_id)
	36	return 1;
	37
	38	if (a->igp.isis.spf.level < b->igp.isis.spf.level)
	39	return -1;
	40	if (a->igp.isis.spf.level > b->igp.isis.spf.level)
	41	return 1;
	42
	43	return 0;
	44	}
	45	RB_GENERATE(ldp_rlfa_client_head, ldp_rlfa_client, entry,
	46	ldp_rlfa_client_compare)
	47
	48	static int ldp_rlfa_node_compare(const struct ldp_rlfa_node *a,
	49	const struct ldp_rlfa_node *b)
	50	{
	51	if (ntohl(a->pq_address.s_addr) < ntohl(b->pq_address.s_addr))
	52	return -1;
	53	if (ntohl(a->pq_address.s_addr) > ntohl(b->pq_address.s_addr))
	54	return 1;
	55
	56	return prefix_cmp(&a->destination, &b->destination);
	57	}
	58	RB_GENERATE(ldp_rlfa_node_head, ldp_rlfa_node, entry, ldp_rlfa_node_compare)
	59
	60	struct ldp_rlfa_client rlfa_client_new(struct ldp_rlfa_node rnode,
	61	struct zapi_rlfa_igp *igp)
	62	{
	63	struct ldp_rlfa_client *rclient;
	64
	65	if ((rclient = calloc(1, sizeof(*rclient))) == NULL)
	66	fatal(__func__);
	67
	68	rclient->igp = *igp;
69	rclient->node = rnode;
70	RB_INSERT(ldp_rlfa_client_head, &rnode->clients, rclient);
71
72	return rclient;
73	}
74
75	void rlfa_client_del(struct ldp_rlfa_client *rclient)
76	{
77	struct ldp_rlfa_node *rnode = rclient->node;
78
79	RB_REMOVE(ldp_rlfa_client_head, &rnode->clients, rclient);
80	free(rclient);
81
82	/* Delete RLFA node if it's empty. */
83	if (RB_EMPTY(ldp_rlfa_client_head, &rnode->clients))
84	rlfa_node_del(rnode);
85	}
86
87	struct ldp_rlfa_client rlfa_client_find(struct ldp_rlfa_node rnode,
88	struct zapi_rlfa_igp *igp)
89	{
90	struct ldp_rlfa_client rclient;
91
92	rclient.igp = *igp;
93	return RB_FIND(ldp_rlfa_client_head, &rnode->clients, &rclient);
94	}
95
96	struct ldp_rlfa_node rlfa_node_new(const struct prefix destination,
97	struct in_addr pq_address)
98	{
99	struct ldp_rlfa_node *rnode;
100
101	if ((rnode = calloc(1, sizeof(*rnode))) == NULL)
102	fatal(__func__);
103
104	rnode->destination = *destination;
105	rnode->pq_address = pq_address;
106	rnode->pq_label = MPLS_INVALID_LABEL;
107	RB_INIT(ldp_rlfa_client_head, &rnode->clients);
108	RB_INSERT(ldp_rlfa_node_head, &rlfa_node_tree, rnode);
109
110	return rnode;
111	}
112
113	void rlfa_node_del(struct ldp_rlfa_node *rnode)
114	{
115	/* Delete RLFA clients. */
116	while (!RB_EMPTY(ldp_rlfa_client_head, &rnode->clients)) {
117	struct ldp_rlfa_client *rclient;
118
119	rclient = RB_ROOT(ldp_rlfa_client_head, &rnode->clients);
120	rlfa_client_del(rclient);
121	}
122
123	RB_REMOVE(ldp_rlfa_node_head, &rlfa_node_tree, rnode);
124	free(rnode);
125	}
126
127	struct ldp_rlfa_node rlfa_node_find(const struct prefix destination,
128	struct in_addr pq_address)
129	{
130	struct ldp_rlfa_node rnode = {};
131
132	rnode.destination = *destination;
133	rnode.pq_address = pq_address;
134	return RB_FIND(ldp_rlfa_node_head, &rlfa_node_tree, &rnode);
135	}
136
137	void lde_rlfa_client_send(struct ldp_rlfa_client *rclient)
138	{
139	struct ldp_rlfa_node *rnode = rclient->node;
140	struct zapi_rlfa_response rlfa_labels = {};
141	struct fec fec;
142	struct fec_node *fn;
143	struct fec_nh *fnh;
144	int i = 0;
145
146	/* Fill in inner label (allocated by PQ node). */
147	rlfa_labels.igp = rclient->igp;
148	rlfa_labels.destination = rnode->destination;
149	rlfa_labels.pq_label = rnode->pq_label;
150
151	/* Fill in outer label(s) (allocated by the nexthop routers). */
152	fec.type = FEC_TYPE_IPV4;
153	fec.u.ipv4.prefix = rnode->pq_address;
154	fec.u.ipv4.prefixlen = IPV4_MAX_BITLEN;
155	fn = (struct fec_node *)fec_find(&ft, &fec);
156	if (!fn)
157	return;
158	LIST_FOREACH(fnh, &fn->nexthops, entry) {
159	if (fnh->remote_label == NO_LABEL)
160	continue;
161
162	rlfa_labels.nexthops[i].family = fnh->af;
163	switch (fnh->af) {
164	case AF_INET:
165	rlfa_labels.nexthops[i].gate.ipv4 = fnh->nexthop.v4;
166	break;
167	case AF_INET6:
168	rlfa_labels.nexthops[i].gate.ipv6 = fnh->nexthop.v6;
169	break;
170	default:
171	continue;
172	}
173	rlfa_labels.nexthops[i].label = fnh->remote_label;
174	i++;
175	}
176	rlfa_labels.nexthop_num = i;
177
178	lde_imsg_compose_parent(IMSG_RLFA_LABELS, 0, &rlfa_labels,
179	sizeof(rlfa_labels));
180	}
181
182	void lde_rlfa_label_update(const struct fec *fec)
183	{
184	struct ldp_rlfa_node *rnode;
185
186	if (fec->type != FEC_TYPE_IPV4
187	\|\| fec->u.ipv4.prefixlen != IPV4_MAX_BITLEN)
188	return;
189
190	/*
191	* TODO: use an rb-tree lookup to restrict the iteration to the RLFAs
192	* that were effectivelly affected by the label update.
193	*/
194	RB_FOREACH (rnode, ldp_rlfa_node_head, &rlfa_node_tree) {
195	struct ldp_rlfa_client *rclient;
196
197	if (!IPV4_ADDR_SAME(&rnode->pq_address, &fec->u.ipv4.prefix))
198	continue;
199
200	RB_FOREACH (rclient, ldp_rlfa_client_head, &rnode->clients)
201	lde_rlfa_client_send(rclient);
202	}
203	}
204
205	void lde_rlfa_check(struct ldp_rlfa_client *rclient)
206	{
207	struct lde_nbr *ln;
208	struct lde_map *me;
209	struct fec fec;
210	union ldpd_addr pq_address = {};
211
212	pq_address.v4 = rclient->node->pq_address;
213	ln = lde_nbr_find_by_addr(AF_INET, &pq_address);
214	if (!ln)
215	return;
216
217	lde_prefix2fec(&rclient->node->destination, &fec);
218	me = (struct lde_map *)fec_find(&ln->recv_map, &fec);
219	if (!me)
220	return;
221
222	rclient->node->pq_label = me->map.label;
223	lde_rlfa_client_send(rclient);
224	}
225
226	/*
227	* Check if there's any registered RLFA client for this prefix/neighbor (PQ
228	* node) and notify about the updated label.
229	*/
230	void lde_rlfa_update_clients(struct fec fec, struct lde_nbr ln,
231	uint32_t label)
232	{
233	struct prefix rlfa_dest;
234	struct ldp_rlfa_node *rnode;
235
236	lde_fec2prefix(fec, &rlfa_dest);
237	rnode = rlfa_node_find(&rlfa_dest, ln->id);
238	if (rnode) {
239	struct ldp_rlfa_client *rclient;
240
241	rnode->pq_label = label;
242	RB_FOREACH (rclient, ldp_rlfa_client_head, &rnode->clients)
243	lde_rlfa_client_send(rclient);
244	} else
245	lde_rlfa_label_update(fec);
246	}
247
248	void ldpe_rlfa_init(struct ldp_rlfa_client *rclient)
249	{
250	struct tnbr *tnbr;
251	union ldpd_addr pq_address = {};
252
253	pq_address.v4 = rclient->node->pq_address;
254	tnbr = tnbr_find(leconf, AF_INET, &pq_address);
255	if (tnbr == NULL) {
256	tnbr = tnbr_new(AF_INET, &pq_address);
257	tnbr_update(tnbr);
258	RB_INSERT(tnbr_head, &leconf->tnbr_tree, tnbr);
259	}
260
261	tnbr->rlfa_count++;
262	}
263
264	void ldpe_rlfa_exit(struct ldp_rlfa_client *rclient)
265	{
266	struct tnbr *tnbr;
267	union ldpd_addr pq_address = {};
268
269	pq_address.v4 = rclient->node->pq_address;
270	tnbr = tnbr_find(leconf, AF_INET, &pq_address);
271	if (tnbr) {
272	tnbr->rlfa_count--;
273	tnbr_check(leconf, tnbr);
274	}
275	}