Start reworking the LDE. Implement a FEC RB tree that can be used for the

route table and the per neighbor request and mapping lists.
The received and sent mappings are added to the per neighbor RB tree and
additionally linked to the route table. This makes lookups, etc. a lot
easier. While there flip the neighbor hash list over to a RB tree.
OK michele@

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);
-	}
-}