3 files changed, 328 insertions, 370 deletions

diff --git a/usr.sbin/ldpd/lde.c b/usr.sbin/ldpd/lde.c
index 2213fbc66ff..a4780e87ce1 100644
--- a/usr.sbin/ldpd/lde.c
+++ b/usr.sbin/ldpd/lde.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: lde.c,v 1.14 2010/05/25 13:29:45 claudio Exp $ */
+/*	$OpenBSD: lde.c,v 1.15 2010/06/02 11:56:29 claudio Exp $ */
 
 /*
  * Copyright (c) 2004, 2005 Claudio Jeker <claudio@openbsd.org>
@@ -22,6 +22,7 @@
 #include <sys/socket.h>
 #include <sys/queue.h>
 #include <netinet/in.h>
+#include <netmpls/mpls.h>
 #include <arpa/inet.h>
 #include <err.h>
 #include <errno.h>
@@ -43,15 +44,13 @@ void		 lde_shutdown(void);
 void		 lde_dispatch_imsg(int, short, void *);
 void		 lde_dispatch_parent(int, short, void *);
 
-void		 lde_nbr_init(u_int32_t);
-void		 lde_nbr_free(void);
 struct lde_nbr	*lde_nbr_find(u_int32_t);
 struct lde_nbr	*lde_nbr_new(u_int32_t, struct lde_nbr *);
 void		 lde_nbr_del(struct lde_nbr *);
+void		 lde_nbr_clear(void);
 
+void		 lde_map_free(void *);
 void		 lde_address_list_free(struct lde_nbr *);
-void		 lde_req_list_free(struct lde_nbr *);
-void		 lde_map_list_free(struct lde_nbr *);
 
 struct ldpd_conf	*ldeconf = NULL, *nconf = NULL;
 struct imsgev		*iev_ldpe;
@@ -114,7 +113,6 @@ lde(struct ldpd_conf *xconf, int pipe_parent2lde[2], int pipe_ldpe2lde[2],
 		fatal("can't drop privileges");
 
 	event_init();
-	lde_nbr_init(NBR_HASHSIZE);
 
 	/* setup signal handler */
 	signal_set(&ev_sigint, SIGINT, lde_sig_handler, NULL);
@@ -149,8 +147,6 @@ lde(struct ldpd_conf *xconf, int pipe_parent2lde[2], int pipe_ldpe2lde[2],
 	    iev_main->handler, iev_main);
 	event_add(&iev_main->ev, NULL);
 
-	rt_init();
-
 	gettimeofday(&now, NULL);
 	ldeconf->uptime = now.tv_sec;
 
@@ -165,10 +161,9 @@ lde(struct ldpd_conf *xconf, int pipe_parent2lde[2], int pipe_ldpe2lde[2],
 void
 lde_shutdown(void)
 {
+	lde_nbr_clear();
 	rt_clear();
 
-	lde_nbr_free();
-
 	msgbuf_clear(&iev_ldpe->ibuf.w);
 	free(iev_ldpe);
 	msgbuf_clear(&iev_main->ibuf.w);
@@ -425,9 +420,13 @@ lde_dispatch_parent(int fd, short event, void *bula)
 }
 
 u_int32_t
-lde_router_id(void)
+lde_assign_label(void)
 {
-	return (ldeconf->rtr_id.s_addr);
+	static u_int32_t label = MPLS_LABEL_RESERVED_MAX;
+
+	/* XXX some checks needed */
+	label++;
+	return (htonl(label << MPLS_LABEL_OFFSET));
 }
 
 void
@@ -436,11 +435,11 @@ lde_send_insert_klabel(struct rt_node *r)
 	struct kroute	kr;
 
 	bzero(&kr, sizeof(kr));
-	kr.prefix.s_addr = r->prefix.s_addr;
+	kr.prefix.s_addr = r->fec.prefix.s_addr;
+	kr.prefixlen = r->fec.prefixlen;
 	kr.nexthop.s_addr = r->nexthop.s_addr;
 	kr.local_label = r->local_label;
 	kr.remote_label = r->remote_label;
-	kr.prefixlen = r->prefixlen;
 
 	imsg_compose_event(iev_main, IMSG_KLABEL_INSERT, 0, 0, -1,
 	     &kr, sizeof(kr));
@@ -452,11 +451,11 @@ lde_send_change_klabel(struct rt_node *r)
 	struct kroute	kr;
 
 	bzero(&kr, sizeof(kr));
-	kr.prefix.s_addr = r->prefix.s_addr;
+	kr.prefix.s_addr = r->fec.prefix.s_addr;
+	kr.prefixlen = r->fec.prefixlen;
 	kr.nexthop.s_addr = r->nexthop.s_addr;
 	kr.local_label = r->local_label;
 	kr.remote_label = r->remote_label;
-	kr.prefixlen = r->prefixlen;
 
 	imsg_compose_event(iev_main, IMSG_KLABEL_CHANGE, 0, 0, -1,
 	     &kr, sizeof(kr));
@@ -468,8 +467,8 @@ lde_send_delete_klabel(struct rt_node *r)
 	struct kroute	 kr;
 
 	bzero(&kr, sizeof(kr));
-	kr.prefix.s_addr = r->prefix.s_addr;
-	kr.prefixlen = r->prefixlen;
+	kr.prefix.s_addr = r->fec.prefix.s_addr;
+	kr.prefixlen = r->fec.prefixlen;
 
 	imsg_compose_event(iev_main, IMSG_KLABEL_DELETE, 0, 0, -1,
 	     &kr, sizeof(kr));
@@ -519,61 +518,34 @@ lde_send_notification(u_int32_t peerid, u_int32_t code, u_int32_t msgid,
 	    -1, &nm, sizeof(nm));
 }
 
-LIST_HEAD(lde_nbr_head, lde_nbr);
-
-struct nbr_table {
-	struct lde_nbr_head	*hashtbl;
-	u_int32_t		 hashmask;
-} ldenbrtable;
-
-#define LDE_NBR_HASH(x)		\
-	&ldenbrtable.hashtbl[(x) & ldenbrtable.hashmask]
-
-void
-lde_nbr_init(u_int32_t hashsize)
-{
-	u_int32_t		 hs, i;
-
-	for (hs = 1; hs < hashsize; hs <<= 1)
-		;
-	ldenbrtable.hashtbl = calloc(hs, sizeof(struct lde_nbr_head));
-	if (ldenbrtable.hashtbl == NULL)
-		fatal("lde_nbr_init");
+static __inline int lde_nbr_compare(struct lde_nbr *, struct lde_nbr *);
 
-	for (i = 0; i < hs; i++)
-		LIST_INIT(&ldenbrtable.hashtbl[i]);
+RB_HEAD(nbr_tree, lde_nbr);
+RB_PROTOTYPE(nbr_tree, lde_nbr, entry, lde_nbr_compare)
+RB_GENERATE(nbr_tree, lde_nbr, entry, lde_nbr_compare)
 
-	ldenbrtable.hashmask = hs - 1;
-}
+struct nbr_tree lde_nbrs = RB_INITIALIZER(&lde_nbrs);
 
-void
-lde_nbr_free(void)
+static __inline int
+lde_nbr_compare(struct lde_nbr *a, struct lde_nbr *b)
 {
-	free(ldenbrtable.hashtbl);
+	return (a->peerid - b->peerid);
 }
 
 struct lde_nbr *
 lde_nbr_find(u_int32_t peerid)
 {
-	struct lde_nbr_head	*head;
-	struct lde_nbr		*nbr;
+	struct lde_nbr	n;
 
-	head = LDE_NBR_HASH(peerid);
+	n.peerid = peerid;
 
-	LIST_FOREACH(nbr, head, hash) {
-		if (nbr->peerid == peerid)
-			return (nbr);
-	}
-
-	return (NULL);
+	return (RB_FIND(nbr_tree, &lde_nbrs, &n));
 }
 
 struct lde_nbr *
 lde_nbr_new(u_int32_t peerid, struct lde_nbr *new)
 {
-	struct lde_nbr_head	*head;
-	struct lde_nbr		*nbr;
-	struct iface		*iface;
+	struct lde_nbr	*nbr;
 
 	if (lde_nbr_find(peerid))
 		return (NULL);
@@ -583,22 +555,16 @@ lde_nbr_new(u_int32_t peerid, struct lde_nbr *new)
 
 	memcpy(nbr, new, sizeof(*nbr));
 	nbr->peerid = peerid;
+	fec_init(&nbr->recv_map);
+	fec_init(&nbr->sent_map);
+	fec_init(&nbr->recv_req);
+	fec_init(&nbr->sent_req);
+	fec_init(&nbr->sent_wdraw);
 
 	TAILQ_INIT(&nbr->addr_list);
-	TAILQ_INIT(&nbr->req_list);
-	TAILQ_INIT(&nbr->sent_map_list);
-	TAILQ_INIT(&nbr->recv_map_list);
-	TAILQ_INIT(&nbr->labels_list);
 
-	head = LDE_NBR_HASH(peerid);
-	LIST_INSERT_HEAD(head, nbr, hash);
-
-	LIST_FOREACH(iface, &ldeconf->iface_list, entry) {
-		if (iface->ifindex == new->ifindex) {
-			LIST_INSERT_HEAD(&iface->lde_nbr_list, nbr, entry);
-			break;
-		}
-	}
+	if (RB_INSERT(nbr_tree, &lde_nbrs, nbr) != NULL)
+		fatalx("lde_nbr_new: RB_INSERT failed");
 
 	return (nbr);
 }
@@ -609,17 +575,98 @@ lde_nbr_del(struct lde_nbr *nbr)
 	if (nbr == NULL)
 		return;
 
-	lde_req_list_free(nbr);
-	lde_map_list_free(nbr);
 	lde_address_list_free(nbr);
-	lde_label_list_free(nbr);
 
-	LIST_REMOVE(nbr, hash);
-	LIST_REMOVE(nbr, entry);
+	fec_clear(&nbr->recv_map, lde_map_free);
+	fec_clear(&nbr->sent_map, lde_map_free);
+	fec_clear(&nbr->recv_req, free);
+	fec_clear(&nbr->sent_req, free);
+	fec_clear(&nbr->sent_wdraw, free);
+
+	RB_REMOVE(nbr_tree, &lde_nbrs, nbr);
 
 	free(nbr);
 }
 
+void
+lde_nbr_clear(void)
+{
+	struct lde_nbr	*nbr;
+
+	 while ((nbr = RB_ROOT(&lde_nbrs)) != NULL)
+		lde_nbr_del(nbr);
+}
+
+void
+lde_nbr_do_mappings(struct rt_node *rn)
+{
+	struct lde_nbr	*ln;
+	struct lde_map	*lm;
+	struct lde_req	*lr;
+	struct map	 map;
+
+	map.label = (ntohl(rn->local_label) & MPLS_LABEL_MASK) >>
+	    MPLS_LABEL_OFFSET;
+	map.prefix = rn->fec.prefix.s_addr;
+	map.prefixlen = rn->fec.prefixlen;
+
+	RB_FOREACH(ln, nbr_tree, &lde_nbrs) {
+		/* Did we already send a mapping to this peer? */
+		lm = (struct lde_map *)fec_find(&ln->sent_map, &rn->fec);
+		if (lm && lm->label == map.label)
+			/* same mapping already sent, skip */
+			continue;
+
+		/* Is this from a pending request? */
+		lr = (struct lde_req *)fec_find(&ln->recv_req, &rn->fec);
+		if (ldeconf->mode & MODE_ADV_ONDEMAND && lr == NULL)
+			/* adv. on demand but no req pending, skip */
+			continue;
+
+		if (ldeconf->mode & MODE_DIST_ORDERED) {
+			/* ordered mode needs the downstream path to be
+			 * ready before we can send the mapping upstream */
+			if (rn->nexthop.s_addr != INADDR_ANY &&
+			    rn->remote_label == NO_LABEL)
+				/* not local FEC but no remote-label, skip */
+				continue;
+		}
+
+		if (lr) {
+			/* set label request msg id in the mapping response. */
+			map.requestid = lr->msgid;
+			map.flags = F_MAP_REQ_ID;
+			fec_remove(&ln->sent_req, &lr->fec);
+		}
+
+		if (lm == NULL) {
+			lm = calloc(1, sizeof(*lm));
+			if (lm == NULL)
+				fatal("lde_nbr_do_mappings");
+			lm->fec = rn->fec;
+			lm->nexthop = ln;
+
+			LIST_INSERT_HEAD(&rn->upstream, lm, entry);
+			if (fec_insert(&ln->sent_map, &lm->fec))
+				log_warnx("failed to add %s/%u to sent map",
+				    inet_ntoa(lm->fec.prefix),
+				    lm->fec.prefixlen);
+		}
+		lm->label = map.label;
+
+		lde_send_labelmapping(ln->peerid, &map);
+	}
+}
+
+void
+lde_map_free(void *ptr)
+{
+	struct lde_map	*map = ptr;
+
+	LIST_REMOVE(map, entry);
+	free(map);
+}
+
 int
 lde_address_add(struct lde_nbr *lr, struct in_addr *addr)
 {
@@ -682,44 +729,14 @@ lde_address_list_free(struct lde_nbr *nbr)
 	}
 }
 
-void
-lde_req_list_free(struct lde_nbr *nbr)
-{
-	struct lde_req_entry	*req;
-
-	while ((req = TAILQ_FIRST(&nbr->req_list)) != NULL) {
-		TAILQ_REMOVE(&nbr->req_list, req, entry);
-		free(req);
-	}
-}
-
-void
-lde_map_list_free(struct lde_nbr *nbr)
-{
-	struct lde_map_entry	*map;
-
-	while ((map = TAILQ_FIRST(&nbr->recv_map_list)) != NULL) {
-		TAILQ_REMOVE(&nbr->recv_map_list, map, entry);
-		free(map);
-	}
-
-	while ((map = TAILQ_FIRST(&nbr->sent_map_list)) != NULL) {
-		TAILQ_REMOVE(&nbr->sent_map_list, map, entry);
-		free(map);
-	}
-}
-
 struct lde_nbr *
 lde_find_address(struct in_addr address)
 {
-	struct iface	*iface;
 	struct lde_nbr	*ln;
 
-	LIST_FOREACH(iface, &ldeconf->iface_list, entry) {
-		LIST_FOREACH(ln, &iface->lde_nbr_list, entry) {
-			if (lde_address_find(ln, &address) != NULL)
-				return (ln);
-		}
+	RB_FOREACH(ln, nbr_tree, &lde_nbrs) {
+		if (lde_address_find(ln, &address) != NULL)
+			return (ln);
 	}
 
 	return (NULL);
diff --git a/usr.sbin/ldpd/lde.h b/usr.sbin/ldpd/lde.h
index 331df88872b..aaa15ec4ef8 100644
--- a/usr.sbin/ldpd/lde.h
+++ b/usr.sbin/ldpd/lde.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: lde.h,v 1.10 2010/05/25 13:29:45 claudio Exp $ */
+/*	$OpenBSD: lde.h,v 1.11 2010/06/02 11:56:29 claudio Exp $ */
 
 /*
  * Copyright (c) 2004, 2005 Esben Norby <norby@openbsd.org>
@@ -26,19 +26,30 @@
 #include <event.h>
 #include <limits.h>
 
-/* Label mapping request pending */
-struct lde_req_entry {
-	TAILQ_ENTRY(lde_req_entry)	entry;
-	struct in_addr			prefix;
-	u_int8_t			prefixlen;
+RB_HEAD(fec_tree, fec);
+
+struct fec {
+	RB_ENTRY(fec)		entry;
+	struct in_addr		prefix;
+	u_int8_t		prefixlen;
 };
 
-/* Label mapping message sent */
-struct lde_map_entry {
-	TAILQ_ENTRY(lde_map_entry)	entry;
-	struct in_addr			prefix;
-	u_int32_t			label;
-	u_int8_t			prefixlen;
+/*
+ * fec tree of pending label request
+ * Note: currently only one outstanding request per FEC can be tracked but
+ *       should not be a problem since ldpd does not support multipath for now.
+ */
+struct lde_req {
+	struct fec		fec;
+	u_int32_t		msgid;	
+};
+
+/* mapping entries */
+struct lde_map {
+	struct fec		 fec;
+	LIST_ENTRY(lde_map)	 entry;
+	struct lde_nbr		*nexthop;
+	u_int32_t		 label;
 };
 
 /* Addresses belonging to neighbor */
@@ -49,14 +60,15 @@ struct lde_nbr_address {
 
 /* just the info LDE needs */
 struct lde_nbr {
-	LIST_ENTRY(lde_nbr)		 hash, entry;
+	RB_ENTRY(lde_nbr)		 entry;
 	struct in_addr			 id;
 
-	TAILQ_HEAD(, lde_req_entry)	 req_list;
-	TAILQ_HEAD(, lde_map_entry)	 recv_map_list;
-	TAILQ_HEAD(, lde_map_entry)	 sent_map_list;
+	struct fec_tree			 recv_req;
+	struct fec_tree			 sent_req;
+	struct fec_tree			 recv_map;
+	struct fec_tree			 sent_map;
+	struct fec_tree			 sent_wdraw;
 	TAILQ_HEAD(, lde_nbr_address)	 addr_list;
-	TAILQ_HEAD(, rt_label)		 labels_list;
 
 	u_int32_t			 peerid;
 	unsigned int			 ifindex;
@@ -65,27 +77,17 @@ struct lde_nbr {
 	u_int16_t			 lspace;
 };
 
-struct rt_node;
-
-struct rt_label {
-	TAILQ_ENTRY(rt_label)	 node_l, nbr_l;
-	struct lde_nbr		*nexthop;
-	struct rt_node		*node;
-	u_int32_t		 label;
-};
-
 struct rt_node {
-	RB_ENTRY(rt_node)	entry;
-	TAILQ_HEAD(, rt_label)	labels_list;
-	struct in_addr		prefix;
+	struct fec		fec;
 	struct in_addr		nexthop;
 
+	LIST_HEAD(, lde_map)	upstream;	/* recv mappings */
+	LIST_HEAD(, lde_map)	downstream;	/* sent mappings */
+
 	u_int32_t		local_label;
 	u_int32_t		remote_label;
-
 	u_int16_t		lspace;
 	u_int8_t		flags;
-	u_int8_t		prefixlen;
 	u_int8_t		invalid;
 	u_int8_t		present;	/* Is it present in fib? */
 };
@@ -93,7 +95,7 @@ struct rt_node {
 /* lde.c */
 pid_t		lde(struct ldpd_conf *, int [2], int [2], int [2]);
 int		lde_imsg_compose_ldpe(int, u_int32_t, pid_t, void *, u_int16_t);
-u_int32_t	lde_router_id(void);
+u_int32_t	lde_assign_label(void);
 void		lde_send_insert_klabel(struct rt_node *);
 void		lde_send_change_klabel(struct rt_node *);
 void		lde_send_delete_klabel(struct rt_node *);
@@ -104,6 +106,7 @@ void		lde_send_notification(u_int32_t, u_int32_t, u_int32_t,
 		   u_int32_t);
 
 void		lde_nbr_del(struct lde_nbr *);
+void		lde_nbr_do_mappings(struct rt_node *);
 struct lde_nbr *lde_find_address(struct in_addr);
 
 
@@ -112,17 +115,17 @@ struct lde_nbr_address	*lde_address_find(struct lde_nbr *, struct in_addr *);
 int			 lde_address_del(struct lde_nbr *, struct in_addr *);
 
 /* lde_lib.c */
-void		 rt_init(void);
-int		 rt_compare(struct rt_node *, struct rt_node *);
-int		 rt_insert(struct rt_node *);
-int		 rt_remove(struct rt_node *);
-struct rt_node	*rt_find(in_addr_t, u_int8_t);
-void		 rt_clear(void);
-void		 route_reset_timers(struct rt_node *);
-int		 route_start_timeout(struct rt_node *);
-void		 route_start_garbage(struct rt_node *);
+void		 fec_init(struct fec_tree *);
+int		 fec_insert(struct fec_tree *, struct fec *);
+int		 fec_remove(struct fec_tree *, struct fec *);
+struct fec	*fec_find_prefix(struct fec_tree *, in_addr_t, u_int8_t);
+struct fec	*fec_find(struct fec_tree *, struct fec *);
+void		 fec_clear(struct fec_tree *, void (*)(void *));
+
 void		 rt_dump(pid_t);
 void		 rt_snap(u_int32_t);
+void		 rt_clear(void);
+
 void		 lde_kernel_insert(struct kroute *);
 void		 lde_kernel_remove(struct kroute *);
 void		 lde_check_mapping(struct map *, struct lde_nbr *);
diff --git a/usr.sbin/ldpd/lde_lib.c b/usr.sbin/ldpd/lde_lib.c
index c10d42cf520..032ab63694b 100644
--- a/usr.sbin/ldpd/lde_lib.c
+++ b/usr.sbin/ldpd/lde_lib.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: lde_lib.c,v 1.18 2010/05/25 09:31:25 claudio Exp $ */
+/*	$OpenBSD: lde_lib.c,v 1.19 2010/06/02 11:56:29 claudio Exp $ */
 
 /*
  * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org>
@@ -20,11 +20,11 @@
 #include <sys/ioctl.h>
 #include <sys/time.h>
 #include <sys/socket.h>
-#include <netinet/in.h>
-#include <arpa/inet.h>
 #include <net/if.h>
 #include <net/if_types.h>
+#include <netinet/in.h>
 #include <netmpls/mpls.h>
+#include <arpa/inet.h>
 #include <ctype.h>
 #include <err.h>
 #include <stdio.h>
@@ -38,22 +38,24 @@
 #include "log.h"
 #include "lde.h"
 
+static int fec_compare(struct fec *, struct fec *);
+
+RB_PROTOTYPE(fec_tree, fec, entry, fec_compare)
+RB_GENERATE(fec_tree, fec, entry, fec_compare)
+
 extern struct ldpd_conf		*ldeconf;
-RB_HEAD(rt_tree, rt_node)	 rt;
-RB_PROTOTYPE(rt_tree, rt_node, entry, rt_compare)
-RB_GENERATE(rt_tree, rt_node, entry, rt_compare)
 
-u_int32_t	lde_assign_label(void);
+struct fec_tree	rt = RB_INITIALIZER(&rt);
 
-/* route table */
+/* FEC tree fucntions */
 void
-rt_init(void)
+fec_init(struct fec_tree *fh)
 {
-	RB_INIT(&rt);
+	RB_INIT(fh);
 }
 
-int
-rt_compare(struct rt_node *a, struct rt_node *b)
+static int
+fec_compare(struct fec *a, struct fec *b)
 {
 	if (ntohl(a->prefix.s_addr) < ntohl(b->prefix.s_addr))
 		return (-1);
@@ -67,52 +69,66 @@ rt_compare(struct rt_node *a, struct rt_node *b)
 	return (0);
 }
 
-struct rt_node *
-rt_find(in_addr_t prefix, u_int8_t prefixlen)
+struct fec *
+fec_find_prefix(struct fec_tree *fh, in_addr_t prefix, u_int8_t prefixlen)
 {
-	struct rt_node	 s;
+	struct fec	 s;
 
 	s.prefix.s_addr = prefix;
 	s.prefixlen = prefixlen;
 
-	return (RB_FIND(rt_tree, &rt, &s));
+	return (fec_find(fh, &s));
 }
 
+struct fec *
+fec_find(struct fec_tree *fh, struct fec *f)
+{
+	return (RB_FIND(fec_tree, fh, f));
+}
+
+
 int
-rt_insert(struct rt_node *r)
+fec_insert(struct fec_tree *fh, struct fec *f)
 {
-	if (RB_INSERT(rt_tree, &rt, r) != NULL) {
-		log_warnx("rt_insert failed for %s/%u",
-		    inet_ntoa(r->prefix), r->prefixlen);
-		free(r);
+	if (RB_INSERT(fec_tree, fh, f) != NULL)
 		return (-1);
-	}
-
 	return (0);
 }
 
 int
-rt_remove(struct rt_node *r)
+fec_remove(struct fec_tree *fh, struct fec *f)
 {
-	if (RB_REMOVE(rt_tree, &rt, r) == NULL) {
-		log_warnx("rt_remove failed for %s/%u",
-		    inet_ntoa(r->prefix), r->prefixlen);
+	if (RB_REMOVE(fec_tree, fh, f) == NULL) {
+		log_warnx("fec_remove failed for %s/%u",
+		    inet_ntoa(f->prefix), f->prefixlen);
 		return (-1);
 	}
-
-	free(r);
 	return (0);
 }
 
 void
+fec_clear(struct fec_tree *fh, void (*free_cb)(void *))
+{
+	struct fec	*f;
+
+	while ((f = RB_ROOT(fh)) != NULL) {
+		fec_remove(fh, f);
+		free_cb(f);
+	}
+}
+
+
+void
 rt_dump(pid_t pid)
 {
+	struct fec		*f;
 	struct rt_node		*r;
 	static struct ctl_rt	 rtctl;
 
-	RB_FOREACH(r, rt_tree, &rt) {
-		rtctl.prefix.s_addr = r->prefix.s_addr;
-		rtctl.prefixlen = r->prefixlen;
+	RB_FOREACH(f, fec_tree, &rt) {
+		r = (struct rt_node *)f;
+		rtctl.prefix.s_addr = r->fec.prefix.s_addr;
+		rtctl.prefixlen = r->fec.prefixlen;
 		rtctl.nexthop.s_addr = r->nexthop.s_addr;
 		rtctl.flags = r->flags;
 		rtctl.local_label = r->local_label;
@@ -136,14 +152,15 @@ rt_dump(pid_t pid)
 void
 rt_snap(u_int32_t peerid)
 {
+	struct fec	*f;
 	struct rt_node	*r;
 	struct map	 map;
 
 	bzero(&map, sizeof(map));
-
-	RB_FOREACH(r, rt_tree, &rt) {
-		map.prefix = r->prefix.s_addr;
-		map.prefixlen = r->prefixlen;
+	RB_FOREACH(f, fec_tree, &rt) {
+		r = (struct rt_node *)f;
+		map.prefix = r->fec.prefix.s_addr;
+		map.prefixlen = r->fec.prefixlen;
 		map.label = (ntohl(r->local_label) & MPLS_LABEL_MASK) >>
 		    MPLS_LABEL_OFFSET;
 
@@ -155,45 +172,33 @@ rt_snap(u_int32_t peerid)
 void
 rt_clear(void)
 {
-	struct rt_node	*r;
-
-	while ((r = RB_MIN(rt_tree, &rt)) != NULL)
-		rt_remove(r);
-}
-
-u_int32_t
-lde_assign_label()
-{
-	static u_int32_t label = MPLS_LABEL_RESERVED_MAX;
-
-	/* XXX some checks needed */
-	label++;
-	return (htonl(label << MPLS_LABEL_OFFSET));
+	fec_clear(&rt, free);
 }
 
 void
 lde_kernel_insert(struct kroute *kr)
 {
 	struct rt_node		*rn;
-	struct rt_label		*rl;
-	struct iface		*iface;
-	struct lde_nbr		*ln;
 	struct lde_nbr_address	*addr;
-	struct map		 localmap;
+	struct lde_map		*map;
 
-	rn = rt_find(kr->prefix.s_addr, kr->prefixlen);
+	rn = (struct rt_node *)fec_find_prefix(&rt, kr->prefix.s_addr,
+	    kr->prefixlen);
 	if (rn == NULL) {
 		rn = calloc(1, sizeof(*rn));
 		if (rn == NULL)
 			fatal("lde_insert");
 
-		rn->prefix.s_addr = kr->prefix.s_addr;
-		rn->prefixlen = kr->prefixlen;
+		rn->fec.prefix.s_addr = kr->prefix.s_addr;
+		rn->fec.prefixlen = kr->prefixlen;
 		rn->remote_label = NO_LABEL;
 		rn->local_label = NO_LABEL;
-		TAILQ_INIT(&rn->labels_list);
+		LIST_INIT(&rn->upstream);
+		LIST_INIT(&rn->downstream);
 
-		rt_insert(rn);
+		if (fec_insert(&rt, &rn->fec))
+			log_warnx("failed to add %s/%u to rt tree",
+			    inet_ntoa(rn->fec.prefix), rn->fec.prefixlen);
 	}
 
 	if (rn->present) {
@@ -211,17 +216,18 @@ lde_kernel_insert(struct kroute *kr)
 			return;
 		}
 
-		TAILQ_FOREACH(rl, &rn->labels_list, node_l) {
-			addr = lde_address_find(rl->nexthop, &rn->nexthop);
+		LIST_FOREACH(map, &rn->downstream, entry) {
+			addr = lde_address_find(map->nexthop, &rn->nexthop);
 			if (addr != NULL) {
 				rn->remote_label =
-				    htonl(rl->label << MPLS_LABEL_OFFSET);
+				    htonl(map->label << MPLS_LABEL_OFFSET);
 				break;
 			}
 		}
 
-		log_debug("lde_kernel_insert: prefix %s, changing label to %u",
-		    inet_ntoa(rn->prefix), rl ? rl->label : 0);
+		log_debug("lde_kernel_insert: prefix %s%u, "
+		    "changing label to %u", inet_ntoa(rn->fec.prefix),
+		    rn->fec.prefixlen, map ? map->label : 0);
 
 		lde_send_change_klabel(rn);
 		return;
@@ -232,15 +238,15 @@ lde_kernel_insert(struct kroute *kr)
 
 	/* There is static assigned label for this route, record it in lib */
 	if (kr->local_label != NO_LABEL) {
-		rn->local_label = (htonl(kr->local_label) << MPLS_LABEL_OFFSET);
+		rn->local_label = htonl(kr->local_label << MPLS_LABEL_OFFSET);
 		return;
 	}
 
-	TAILQ_FOREACH(rl, &rn->labels_list, node_l) {
-		addr = lde_address_find(rl->nexthop, &rn->nexthop);
+	LIST_FOREACH(map, &rn->downstream, entry) {
+		addr = lde_address_find(map->nexthop, &rn->nexthop);
 		if (addr != NULL) {
 			rn->remote_label =
-			    htonl(rl->label << MPLS_LABEL_OFFSET);
+			    htonl(map->label << MPLS_LABEL_OFFSET);
 			break;
 		}
 	}
@@ -258,52 +264,37 @@ lde_kernel_insert(struct kroute *kr)
 	lde_send_insert_klabel(rn);
 
 	/* Redistribute the current mapping to every nbr */
-	localmap.label = (ntohl(rn->local_label) & MPLS_LABEL_MASK) >>
-	    MPLS_LABEL_OFFSET;
-	localmap.prefix = rn->prefix.s_addr;
-	localmap.prefixlen = rn->prefixlen;
-
-	LIST_FOREACH(iface, &ldeconf->iface_list, entry) {
-		LIST_FOREACH(ln, &iface->lde_nbr_list, entry) {
-			if (ldeconf->mode & MODE_ADV_UNSOLICITED &&
-			    ldeconf->mode & MODE_DIST_INDEPENDENT)
-				lde_send_labelmapping(ln->peerid, &localmap);
-
-			if (ldeconf->mode & MODE_ADV_UNSOLICITED &&
-			    ldeconf->mode & MODE_DIST_ORDERED) {
-			       /* XXX */
-				if (rn->nexthop.s_addr == INADDR_ANY ||
-				    rn->remote_label != NO_LABEL)
-					lde_send_labelmapping(ln->peerid,
-					    &localmap);
-			}
-		}
-	}
+	lde_nbr_do_mappings(rn);
 }
 
 void
 lde_kernel_remove(struct kroute *kr)
 {
 	struct rt_node		*rn;
-	struct rt_label		*rl;
+	struct lde_map		*map;
 	struct lde_nbr		*ln;
 
-	rn = rt_find(kr->prefix.s_addr, kr->prefixlen);
+	rn = (struct rt_node *)fec_find_prefix(&rt, kr->prefix.s_addr,
+	    kr->prefixlen);
 	if (rn == NULL)
 		return;
 
 	if (ldeconf->mode & MODE_RET_LIBERAL) {
 		ln = lde_find_address(rn->nexthop);
 		if (ln) {
-			rl = calloc(1, sizeof(*rl));
-			if (rl == NULL)
+			map = calloc(1, sizeof(*map));
+			if (map == NULL)
 				fatal("lde_kernel_remove");
 
-			rl->label = rn->remote_label;
-			rl->node = rn;
-			rl->nexthop = ln;
-			TAILQ_INSERT_TAIL(&rn->labels_list, rl, node_l);
-			TAILQ_INSERT_TAIL(&ln->labels_list, rl, nbr_l);
+			map->label = (ntohl(rn->remote_label) &
+			    MPLS_LABEL_MASK) >> MPLS_LABEL_OFFSET;
+			map->fec = rn->fec;
+			map->nexthop = ln;
+			LIST_INSERT_HEAD(&rn->downstream, map, entry);
+			if (fec_insert(&ln->recv_map, &map->fec))
+				log_warnx("failed to add %s/%u to recv map (1)",
+				    inet_ntoa(map->fec.prefix),
+				    map->fec.prefixlen);
 		}
 	}
 
@@ -316,17 +307,14 @@ void
 lde_check_mapping(struct map *map, struct lde_nbr *ln)
 {
 	struct rt_node		*rn;
-	struct rt_label		*rl;
 	struct lde_nbr_address	*addr;
-	struct lde_map_entry	*me, *menew;
-	struct lde_req_entry	*req;
-	struct iface		*iface;
-	struct map		 localmap;
-
-	/* The route is not yet in fib. If we are in liberal mode create a
-	   route and record the label */
-	rn = rt_find(map->prefix, map->prefixlen);
+	struct lde_map		*me;
+
+	rn = (struct rt_node *)fec_find_prefix(&rt, map->prefix,
+	    map->prefixlen);
 	if (rn == NULL) {
+		/* The route is not yet in fib. If we are in liberal mode
+		 *  create a route and record the label */
 		if (ldeconf->mode & MODE_RET_CONSERVATIVE)
 			return;
 
@@ -334,44 +322,58 @@ lde_check_mapping(struct map *map, struct lde_nbr *ln)
 		if (rn == NULL)
 			fatal("lde_check_mapping");
 
-		rn->prefix.s_addr = map->prefix;
-		rn->prefixlen = map->prefixlen;
+		rn->fec.prefix.s_addr = map->prefix;
+		rn->fec.prefixlen = map->prefixlen;
 		rn->local_label = lde_assign_label();
 		rn->remote_label = NO_LABEL;
 		rn->present = 0;
 
-		TAILQ_INIT(&rn->labels_list);
+		LIST_INIT(&rn->upstream);
+		LIST_INIT(&rn->downstream);
 
-		rt_insert(rn);
+		if (fec_insert(&rt, &rn->fec))
+			log_warnx("failed to add %s/%u to rt tree",
+			    inet_ntoa(rn->fec.prefix), rn->fec.prefixlen);
 	}
 
-	TAILQ_FOREACH(me, &ln->recv_map_list, entry) {
-		if (me->prefix.s_addr == map->prefix &&
-		    me->prefixlen == map->prefixlen) {
+	LIST_FOREACH(me, &rn->downstream, entry) {
+		if (ln == me->nexthop) {
 			if (me->label == map->label) {
+				/* Duplicate: RFC says to send back a release,
+				 * even though we did not release the actual
+				 * mapping. This is confusing.
+				 */
 				lde_send_labelrelease(ln->peerid, map);
 				return;
 			}
+			/* old mapping that is now changed */
+			break;
 		}
 	}
 
 	addr = lde_address_find(ln, &rn->nexthop);
 	if (addr == NULL || !rn->present) {
+		/* route not yet available */
 		if (ldeconf->mode & MODE_RET_CONSERVATIVE) {
 			lde_send_labelrelease(ln->peerid, map);
 			return;
 		}
+		/* in liberal mode just note the mapping */
+		if (me == NULL) {
+			me = calloc(1, sizeof(*me));
+			if (me == NULL)
+				fatal("lde_check_mapping");
+			me->fec = rn->fec;
+			me->nexthop = ln;
+
+			LIST_INSERT_HEAD(&rn->downstream, me, entry);
+			if (fec_insert(&ln->recv_map, &me->fec))
+				log_warnx("failed to add %s/%u to recv map (2)",
+				    inet_ntoa(me->fec.prefix),
+				    me->fec.prefixlen);
+		}
+		me->label = map->label;
 
-		rl = calloc(1, sizeof(*rl));
-		if (rl == NULL)
-			fatal("lde_check_mapping");
-
-		rl->label = map->label;
-		rl->node = rn;
-		rl->nexthop = ln;
-
-		TAILQ_INSERT_TAIL(&rn->labels_list, rl, node_l);
-		TAILQ_INSERT_TAIL(&ln->labels_list, rl, nbr_l);
 		return;
 	}
 
@@ -382,87 +384,36 @@ lde_check_mapping(struct map *map, struct lde_nbr *ln)
 		lde_send_change_klabel(rn);
 
 	/* Record the mapping from this peer */	
-	menew = calloc(1, sizeof(*menew));
-	if (menew == NULL)
-		fatal("lde_check_mapping");
-
-	menew->prefix.s_addr = map->prefix;
-	menew->prefixlen = map->prefixlen;
-	menew->label = map->label;
-
-	TAILQ_INSERT_HEAD(&ln->recv_map_list, menew, entry);
-
-	/* Redistribute the current mapping to every nbr */
-	localmap.label = rn->local_label;
-	localmap.prefix = rn->prefix.s_addr;
-	localmap.prefixlen = rn->prefixlen;
-
-	LIST_FOREACH(iface, &ldeconf->iface_list, entry) {
-		LIST_FOREACH(ln, &iface->lde_nbr_list, entry) {
-			/* Did we already send a mapping to this peer? */
-			TAILQ_FOREACH(me, &ln->sent_map_list, entry) {
-				if (me->prefix.s_addr == rn->prefix.s_addr &&
-				    me->prefixlen == rn->prefixlen)
-					break;
-			}
-			if (me != NULL) {
-				/* XXX: check RAttributes */
-				continue;
-			}
-
-			if (ldeconf->mode & MODE_ADV_UNSOLICITED &&
-			    ldeconf->mode & MODE_DIST_ORDERED) {
-				lde_send_labelmapping(ln->peerid, &localmap);
-
-				menew = calloc(1, sizeof(*menew));
-				if (menew == NULL)
-					fatal("lde_check_mapping");
-
-				menew->prefix.s_addr = map->prefix;
-				menew->prefixlen = map->prefixlen;
-				menew->label = map->label;
-
-				TAILQ_INSERT_HEAD(&ln->sent_map_list, menew,
-				    entry);
-			}
-
-			TAILQ_FOREACH(req, &ln->req_list, entry) {
-				if (req->prefix.s_addr == rn->prefix.s_addr &&
-				    req->prefixlen == rn->prefixlen)
-					break;
-			}
-			if (req != NULL) {
-				lde_send_labelmapping(ln->peerid, &localmap);
-
-				menew = calloc(1, sizeof(*menew));
-				if (menew == NULL)
-					fatal("lde_check_mapping");
-
-				menew->prefix.s_addr = map->prefix;
-				menew->prefixlen = map->prefixlen;
-				menew->label = map->label;
-
-				TAILQ_INSERT_HEAD(&ln->sent_map_list, menew,
-				    entry);
+	if (me == NULL) {
+		me = calloc(1, sizeof(*me));
+		if (me == NULL)
+			fatal("lde_check_mapping");
 
-				TAILQ_REMOVE(&ln->req_list, req, entry);
-				free(req);
-			}
-		}
+		me->fec = rn->fec;
+		me->nexthop = ln;
+		LIST_INSERT_HEAD(&rn->downstream, me, entry);
+		if (fec_insert(&ln->recv_map, &me->fec))
+			log_warnx("failed to add %s/%u to recv map (3)",
+			    inet_ntoa(me->fec.prefix), me->fec.prefixlen);
 	}
+	me->label = map->label;
 
 	lde_send_change_klabel(rn);
+
+	/* Redistribute the current mapping to every nbr */
+	lde_nbr_do_mappings(rn);
 }
 
 void
 lde_check_request(struct map *map, struct lde_nbr *ln)
 {
-	struct lde_req_entry	*lre, *newlre;
-	struct rt_node		*rn;
-	struct lde_nbr		*lnn;
-	struct map		 localmap;
+	struct lde_req	*lre;
+	struct rt_node	*rn;
+	struct lde_nbr	*lnn;
+	struct map	 localmap;
 
-	rn = rt_find(map->prefix, map->prefixlen);
+	rn = (struct rt_node *)fec_find_prefix(&rt, map->prefix,
+	    map->prefixlen);
 	if (rn == NULL || rn->remote_label == NO_LABEL) {
 		lde_send_notification(ln->peerid, S_NO_ROUTE, map->messageid,
 		    MSG_TYPE_LABELREQUEST);
@@ -475,14 +426,12 @@ lde_check_request(struct map *map, struct lde_nbr *ln)
 		return;
 	}
 
-	TAILQ_FOREACH(lre, &ln->req_list, entry) {
-		if (lre->prefix.s_addr == map->prefix &&
-		    lre->prefixlen == map->prefixlen)
-			return;
-	}
+	lre = (struct lde_req *)fec_find(&ln->recv_req, &rn->fec);
+	if (lre != NULL)
+		return;
 
-	/* XXX: if we are egress ? */
-	if (rn->remote_label != NO_LABEL) {
+	if (rn->nexthop.s_addr == INADDR_ANY ||
+	    rn->remote_label != NO_LABEL) {
 		bzero(&localmap, sizeof(localmap));
 		localmap.prefix = map->prefix;
 		localmap.prefixlen = map->prefixlen;
@@ -492,18 +441,21 @@ lde_check_request(struct map *map, struct lde_nbr *ln)
 	} else {
 		lnn = lde_find_address(rn->nexthop);
 		if (lnn == NULL)
+			/* XXX this feels wrong.... */
 			return;
 
 		lde_send_labelrequest(lnn->peerid, map);
 
-		newlre = calloc(1, sizeof(*newlre));
-		if (newlre == NULL)
+		lre = calloc(1, sizeof(*lre));
+		if (lre == NULL)
 			fatal("lde_check_request");
 
-		newlre->prefix.s_addr = map->prefix;
-		newlre->prefixlen = map->prefixlen;
+		lre->fec = rn->fec;
+		lre->msgid = map->messageid;
 
-		TAILQ_INSERT_HEAD(&ln->req_list, newlre, entry);
+		if (fec_insert(&ln->recv_req, &lre->fec))
+			log_warnx("failed to add %s/%u to recv req",
+			    inet_ntoa(lre->fec.prefix), lre->fec.prefixlen);
 	}
 }
 
@@ -511,17 +463,3 @@ void
 lde_check_release(struct map *map, struct lde_nbr *ln)
 {
 }
-
-void
-lde_label_list_free(struct lde_nbr *nbr)
-{
-	struct rt_label	*rl;
-
-	while ((rl = TAILQ_FIRST(&nbr->labels_list)) != NULL) {
-		TAILQ_REMOVE(&nbr->labels_list, rl, nbr_l);
-		TAILQ_REMOVE(&nbr->labels_list, rl, node_l);
-		if (TAILQ_EMPTY(&rl->node->labels_list))
-			rt_remove(rl->node);
-		free(rl);
-	}
-}