lde_lib.c revision 1.22 
1/*	$OpenBSD: lde_lib.c,v 1.22 2010/06/30 01:47:11 claudio Exp $ */
2
3/*
4 * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org>
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19#include <sys/types.h>
20#include <sys/ioctl.h>
21#include <sys/time.h>
22#include <sys/socket.h>
23#include <net/if.h>
24#include <net/if_types.h>
25#include <netinet/in.h>
26#include <netmpls/mpls.h>
27#include <arpa/inet.h>
28#include <ctype.h>
29#include <err.h>
30#include <stdio.h>
31#include <stdlib.h>
32#include <unistd.h>
33#include <string.h>
34#include <event.h>
35
36#include "ldpd.h"
37#include "ldp.h"
38#include "log.h"
39#include "lde.h"
40
41static int fec_compare(struct fec *, struct fec *);
42
43RB_PROTOTYPE(fec_tree, fec, entry, fec_compare)
44RB_GENERATE(fec_tree, fec, entry, fec_compare)
45
46extern struct ldpd_conf		*ldeconf;
47
48struct fec_tree	rt = RB_INITIALIZER(&rt);
49
50/* FEC tree fucntions */
51void
52fec_init(struct fec_tree *fh)
53{
54	RB_INIT(fh);
55}
56
57static int
58fec_compare(struct fec *a, struct fec *b)
59{
60	if (ntohl(a->prefix.s_addr) < ntohl(b->prefix.s_addr))
61		return (-1);
62	if (ntohl(a->prefix.s_addr) > ntohl(b->prefix.s_addr))
63		return (1);
64	if (a->prefixlen < b->prefixlen)
65		return (-1);
66	if (a->prefixlen > b->prefixlen)
67		return (1);
68
69	return (0);
70}
71
72struct fec *
73fec_find_prefix(struct fec_tree *fh, in_addr_t prefix, u_int8_t prefixlen)
74{
75	struct fec	 s;
76
77	s.prefix.s_addr = prefix;
78	s.prefixlen = prefixlen;
79
80	return (fec_find(fh, &s));
81}
82
83struct fec *
84fec_find(struct fec_tree *fh, struct fec *f)
85{
86	return (RB_FIND(fec_tree, fh, f));
87}
88
89
90int
91fec_insert(struct fec_tree *fh, struct fec *f)
92{
93	if (RB_INSERT(fec_tree, fh, f) != NULL)
94		return (-1);
95	return (0);
96}
97
98int
99fec_remove(struct fec_tree *fh, struct fec *f)
100{
101	if (RB_REMOVE(fec_tree, fh, f) == NULL) {
102		log_warnx("fec_remove failed for %s/%u",
103		    inet_ntoa(f->prefix), f->prefixlen);
104		return (-1);
105	}
106	return (0);
107}
108
109void
110fec_clear(struct fec_tree *fh, void (*free_cb)(void *))
111{
112	struct fec	*f;
113
114	while ((f = RB_ROOT(fh)) != NULL) {
115		fec_remove(fh, f);
116		free_cb(f);
117	}
118}
119
120
121void
122rt_dump(pid_t pid)
123{
124	struct fec		*f;
125	struct rt_node		*r;
126	static struct ctl_rt	 rtctl;
127
128	RB_FOREACH(f, fec_tree, &rt) {
129		r = (struct rt_node *)f;
130		rtctl.prefix.s_addr = r->fec.prefix.s_addr;
131		rtctl.prefixlen = r->fec.prefixlen;
132		rtctl.nexthop.s_addr = r->nexthop.s_addr;
133		rtctl.flags = r->flags;
134		rtctl.local_label = r->local_label;
135		rtctl.remote_label = r->remote_label;
136
137		if (!r->present)
138			rtctl.in_use = 0;
139		else
140			rtctl.in_use = 1;
141
142		if (rtctl.nexthop.s_addr == htonl(INADDR_LOOPBACK))
143			rtctl.connected = 1;
144		else
145			rtctl.connected = 0;
146
147		lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB, 0, pid, &rtctl,
148		    sizeof(rtctl));
149	}
150}
151
152void
153rt_snap(u_int32_t peerid)
154{
155	struct fec	*f;
156	struct rt_node	*r;
157	struct map	 map;
158
159	bzero(&map, sizeof(map));
160	RB_FOREACH(f, fec_tree, &rt) {
161		r = (struct rt_node *)f;
162		map.prefix = r->fec.prefix;
163		map.prefixlen = r->fec.prefixlen;
164		map.label = r->local_label;
165
166		lde_imsg_compose_ldpe(IMSG_MAPPING_ADD, peerid, 0, &map,
167		    sizeof(map));
168	}
169}
170
171void
172rt_clear(void)
173{
174	fec_clear(&rt, free);
175}
176
177void
178lde_kernel_insert(struct kroute *kr)
179{
180	struct rt_node		*rn;
181	struct lde_nbr_address	*addr;
182	struct lde_map		*map;
183
184	log_debug("kernel add route %s/%u", inet_ntoa(kr->prefix),
185	    kr->prefixlen);
186
187	rn = (struct rt_node *)fec_find_prefix(&rt, kr->prefix.s_addr,
188	    kr->prefixlen);
189	if (rn == NULL) {
190		rn = calloc(1, sizeof(*rn));
191		if (rn == NULL)
192			fatal("lde_insert");
193
194		rn->fec.prefix.s_addr = kr->prefix.s_addr;
195		rn->fec.prefixlen = kr->prefixlen;
196		rn->remote_label = NO_LABEL;
197		rn->local_label = NO_LABEL;
198		LIST_INIT(&rn->upstream);
199		LIST_INIT(&rn->downstream);
200
201		if (fec_insert(&rt, &rn->fec))
202			log_warnx("failed to add %s/%u to rt tree",
203			    inet_ntoa(rn->fec.prefix), rn->fec.prefixlen);
204	}
205
206	if (rn->present) {
207		if (kr->nexthop.s_addr == rn->nexthop.s_addr)
208			return;
209
210		/* The nexthop has changed, change also the label associated
211		   with prefix */
212		rn->remote_label = NO_LABEL;
213		rn->nexthop.s_addr = kr->nexthop.s_addr;
214
215		if ((ldeconf->mode & MODE_RET_LIBERAL) == 0) {
216			/* XXX: we support just liberal retention for now */
217			log_warnx("lde_kernel_insert: missing mode");
218			return;
219		}
220
221		LIST_FOREACH(map, &rn->downstream, entry) {
222			addr = lde_address_find(map->nexthop, &rn->nexthop);
223			if (addr != NULL) {
224				rn->remote_label = map->label;
225				break;
226			}
227		}
228
229		log_debug("lde_kernel_insert: prefix %s%u, "
230		    "changing label to %u", inet_ntoa(rn->fec.prefix),
231		    rn->fec.prefixlen, map ? map->label : 0);
232
233		lde_send_change_klabel(rn);
234		return;
235	}
236
237	rn->present = 1;
238	rn->nexthop.s_addr = kr->nexthop.s_addr;
239
240	/* There is static assigned label for this route, record it in lib */
241	if (kr->local_label != NO_LABEL) {
242		rn->local_label = kr->local_label;
243		return;
244	}
245
246	LIST_FOREACH(map, &rn->downstream, entry) {
247		addr = lde_address_find(map->nexthop, &rn->nexthop);
248		if (addr != NULL) {
249			rn->remote_label = map->label;
250			break;
251		}
252	}
253
254	if (rn->local_label == NO_LABEL) {
255		/* Directly connected route */
256		if (kr->nexthop.s_addr == INADDR_ANY) {
257			rn->local_label = MPLS_LABEL_IMPLNULL;
258			rn->nexthop.s_addr = htonl(INADDR_LOOPBACK);
259		} else
260			rn->local_label = lde_assign_label();
261	}
262
263	lde_send_insert_klabel(rn);
264
265	/* Redistribute the current mapping to every nbr */
266	lde_nbr_do_mappings(rn);
267}
268
269void
270lde_kernel_remove(struct kroute *kr)
271{
272	struct rt_node		*rn;
273	struct lde_map		*map;
274	struct lde_nbr		*ln;
275
276	log_debug("kernel remove route %s/%u", inet_ntoa(kr->prefix),
277	    kr->prefixlen);
278
279	rn = (struct rt_node *)fec_find_prefix(&rt, kr->prefix.s_addr,
280	    kr->prefixlen);
281	if (rn == NULL)
282		return;
283
284	if (ldeconf->mode & MODE_RET_LIBERAL) {
285		ln = lde_find_address(rn->nexthop);
286		if (ln) {
287			map = calloc(1, sizeof(*map));
288			if (map == NULL)
289				fatal("lde_kernel_remove");
290
291			map->label = rn->remote_label;
292			map->fec = rn->fec;
293			map->nexthop = ln;
294			LIST_INSERT_HEAD(&rn->downstream, map, entry);
295			if (fec_insert(&ln->recv_map, &map->fec))
296				log_warnx("failed to add %s/%u to recv map (1)",
297				    inet_ntoa(map->fec.prefix),
298				    map->fec.prefixlen);
299		}
300	}
301
302	rn->remote_label = NO_LABEL;
303	rn->nexthop.s_addr = INADDR_ANY;
304	rn->present = 0;
305}
306
307void
308lde_check_mapping(struct map *map, struct lde_nbr *ln)
309{
310	struct rt_node		*rn;
311	struct lde_nbr_address	*addr;
312	struct lde_map		*me;
313
314	log_debug("label mapping from nbr %s, FEC %s/%u, label %u",
315	    inet_ntoa(ln->id), log_fec(map), map->label);
316
317	rn = (struct rt_node *)fec_find_prefix(&rt, map->prefix.s_addr,
318	    map->prefixlen);
319	if (rn == NULL) {
320		/* The route is not yet in fib. If we are in liberal mode
321		 *  create a route and record the label */
322		if (ldeconf->mode & MODE_RET_CONSERVATIVE)
323			return;
324
325		rn = calloc(1, sizeof(*rn));
326		if (rn == NULL)
327			fatal("lde_check_mapping");
328
329		rn->fec.prefix = map->prefix;
330		rn->fec.prefixlen = map->prefixlen;
331		rn->local_label = lde_assign_label();
332		rn->remote_label = NO_LABEL;
333		rn->present = 0;
334
335		LIST_INIT(&rn->upstream);
336		LIST_INIT(&rn->downstream);
337
338		if (fec_insert(&rt, &rn->fec))
339			log_warnx("failed to add %s/%u to rt tree",
340			    inet_ntoa(rn->fec.prefix), rn->fec.prefixlen);
341	}
342
343	LIST_FOREACH(me, &rn->downstream, entry) {
344		if (ln == me->nexthop) {
345			if (me->label == map->label) {
346				/* Duplicate: RFC says to send back a release,
347				 * even though we did not release the actual
348				 * mapping. This is confusing.
349				 */
350				lde_send_labelrelease(ln->peerid, map);
351				return;
352			}
353			/* old mapping that is now changed */
354			break;
355		}
356	}
357
358	addr = lde_address_find(ln, &rn->nexthop);
359	if (addr == NULL || !rn->present) {
360		/* route not yet available */
361		if (ldeconf->mode & MODE_RET_CONSERVATIVE) {
362			lde_send_labelrelease(ln->peerid, map);
363			return;
364		}
365		/* in liberal mode just note the mapping */
366		if (me == NULL) {
367			me = calloc(1, sizeof(*me));
368			if (me == NULL)
369				fatal("lde_check_mapping");
370			me->fec = rn->fec;
371			me->nexthop = ln;
372
373			LIST_INSERT_HEAD(&rn->downstream, me, entry);
374			if (fec_insert(&ln->recv_map, &me->fec))
375				log_warnx("failed to add %s/%u to recv map (2)",
376				    inet_ntoa(me->fec.prefix),
377				    me->fec.prefixlen);
378		}
379		me->label = map->label;
380
381		return;
382	}
383
384	rn->remote_label = map->label;
385
386	/* If we are ingress for this LSP install the label */
387	if (rn->nexthop.s_addr == INADDR_ANY)
388		lde_send_change_klabel(rn);
389
390	/* Record the mapping from this peer */
391	if (me == NULL) {
392		me = calloc(1, sizeof(*me));
393		if (me == NULL)
394			fatal("lde_check_mapping");
395
396		me->fec = rn->fec;
397		me->nexthop = ln;
398		LIST_INSERT_HEAD(&rn->downstream, me, entry);
399		if (fec_insert(&ln->recv_map, &me->fec))
400			log_warnx("failed to add %s/%u to recv map (3)",
401			    inet_ntoa(me->fec.prefix), me->fec.prefixlen);
402	}
403	me->label = map->label;
404
405	lde_send_change_klabel(rn);
406
407	/* Redistribute the current mapping to every nbr */
408	lde_nbr_do_mappings(rn);
409}
410
411void
412lde_check_request(struct map *map, struct lde_nbr *ln)
413{
414	struct lde_req	*lre;
415	struct rt_node	*rn;
416	struct lde_nbr	*lnn;
417	struct map	 localmap;
418
419	log_debug("label request from nbr %s, FEC %s",
420	    inet_ntoa(ln->id), log_fec(map));
421
422	rn = (struct rt_node *)fec_find_prefix(&rt, map->prefix.s_addr,
423	    map->prefixlen);
424	if (rn == NULL || rn->remote_label == NO_LABEL) {
425		lde_send_notification(ln->peerid, S_NO_ROUTE, map->messageid,
426		    MSG_TYPE_LABELREQUEST);
427		return;
428	}
429
430	if (lde_address_find(ln, &rn->nexthop)) {
431		lde_send_notification(ln->peerid, S_LOOP_DETECTED,
432		    map->messageid, MSG_TYPE_LABELREQUEST);
433		return;
434	}
435
436	lre = (struct lde_req *)fec_find(&ln->recv_req, &rn->fec);
437	if (lre != NULL)
438		return;
439
440	if (rn->nexthop.s_addr == INADDR_ANY ||
441	    rn->remote_label != NO_LABEL) {
442		bzero(&localmap, sizeof(localmap));
443		localmap.prefix = map->prefix;
444		localmap.prefixlen = map->prefixlen;
445		localmap.label = rn->local_label;
446
447		lde_send_labelmapping(ln->peerid, &localmap);
448	} else {
449		lnn = lde_find_address(rn->nexthop);
450		if (lnn == NULL)
451			/* XXX this feels wrong.... */
452			return;
453
454		lde_send_labelrequest(lnn->peerid, map);
455
456		lre = calloc(1, sizeof(*lre));
457		if (lre == NULL)
458			fatal("lde_check_request");
459
460		lre->fec = rn->fec;
461		lre->msgid = map->messageid;
462
463		if (fec_insert(&ln->recv_req, &lre->fec))
464			log_warnx("failed to add %s/%u to recv req",
465			    inet_ntoa(lre->fec.prefix), lre->fec.prefixlen);
466	}
467}
468
469void
470lde_check_release(struct map *map, struct lde_nbr *ln)
471{
472	log_debug("label mapping from nbr %s, FEC %s",
473	    inet_ntoa(ln->id), log_fec(map));
474
475	/* check withdraw list */
476	/* check sent map list */
477}
478