Fix a bad heritage from ospfd. Make neighbors independent of interfaces.

They are not bound as strongly as in ospf and causes problems when the
TCP connection is established from an not connected IP (e.g. a loopback).
Use three RB trees to sort the neighbor list by id, addr and peerid.
More cleanup is needed but this makes ldpd work against peers using
loopback IPs. Problem found, reported and fix tested again by Marcel Wiget.

7 files changed, 88 insertions, 154 deletions

diff --git a/usr.sbin/ldpd/hello.c b/usr.sbin/ldpd/hello.c
index 3511caa622a..e921c364079 100644
--- a/usr.sbin/ldpd/hello.c
+++ b/usr.sbin/ldpd/hello.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: hello.c,v 1.10 2011/01/10 12:05:22 claudio Exp $ */
+/*	$OpenBSD: hello.c,v 1.11 2011/01/10 12:28:25 claudio Exp $ */
 
 /*
  * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org>
@@ -122,7 +122,7 @@ recv_hello(struct iface *iface, struct in_addr src, char *buf, u_int16_t len)
 		return;
 	}
 
-	nbr = nbr_find_ldpid(iface, ldp.lsr_id, ldp.lspace_id);
+	nbr = nbr_find_ldpid(ldp.lsr_id, ldp.lspace_id);
 	if (!nbr) {
 		nbr = nbr_new(ldp.lsr_id, ldp.lspace_id, iface);
 
diff --git a/usr.sbin/ldpd/interface.c b/usr.sbin/ldpd/interface.c
index 02b66c8acf2..a622e282a36 100644
--- a/usr.sbin/ldpd/interface.c
+++ b/usr.sbin/ldpd/interface.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: interface.c,v 1.6 2010/05/19 15:28:51 claudio Exp $ */
+/*	$OpenBSD: interface.c,v 1.7 2011/01/10 12:28:25 claudio Exp $ */
 
 /*
  * Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
@@ -133,7 +133,6 @@ if_new(struct kif *kif, struct kif_addr *ka)
 
 	iface->state = IF_STA_DOWN;
 
-	LIST_INIT(&iface->nbr_list);
 	LIST_INIT(&iface->lde_nbr_list);
 
 	strlcpy(iface->name, kif->ifname, sizeof(iface->name));
@@ -170,14 +169,8 @@ if_new(struct kif *kif, struct kif_addr *ka)
 void
 if_del(struct iface *iface)
 {
-	struct nbr	*nbr = NULL;
-
 	log_debug("if_del: interface %s", iface->name);
 
-	/* clear lists etc */
-	while ((nbr = LIST_FIRST(&iface->nbr_list)) != NULL)
-		nbr_del(nbr);
-
 	if (evtimer_pending(&iface->hello_timer, NULL))
 		evtimer_del(&iface->hello_timer);
 
@@ -267,7 +260,6 @@ if_act_start(struct iface *iface)
 int
 if_act_reset(struct iface *iface)
 {
-/*	struct nbr		*nbr = NULL; */
 	struct in_addr		 addr;
 
 	inet_aton(AllRouters, &addr);
@@ -275,14 +267,6 @@ if_act_reset(struct iface *iface)
 		log_warnx("if_act_reset: error leaving group %s, "
 		    "interface %s", inet_ntoa(addr), iface->name);
 	}
-/*
-	LIST_FOREACH(nbr, &iface->nbr_list, entry) {
-		if (nbr_fsm(nbr, NBR_EVT_KILL_NBR)) {
-			log_debug("if_act_reset: error killing neighbor %s",
-			    inet_ntoa(nbr->id));
-		}
-	}
-*/
 	return (0);
 }
 
@@ -291,7 +275,6 @@ if_to_ctl(struct iface *iface)
 {
 	static struct ctl_iface	 ictl;
 	struct timeval		 tv, now, res;
-	struct nbr		*nbr;
 
 	memcpy(ictl.name, iface->name, sizeof(ictl.name));
 	memcpy(&ictl.addr, &iface->addr, sizeof(ictl.addr));
@@ -300,8 +283,6 @@ if_to_ctl(struct iface *iface)
 	ictl.ifindex = iface->ifindex;
 	ictl.state = iface->state;
 	ictl.mtu = iface->mtu;
-	ictl.nbr_cnt = 0;
-	ictl.adj_cnt = 0;
 	ictl.baudrate = iface->baudrate;
 	ictl.holdtime = iface->holdtime;
 	ictl.hello_interval = iface->hello_interval;
@@ -324,9 +305,6 @@ if_to_ctl(struct iface *iface)
 	} else
 		ictl.uptime = 0;
 
-	LIST_FOREACH(nbr, &iface->nbr_list, entry)
-		ictl.nbr_cnt++;
-
 	return (&ictl);
 }
 
diff --git a/usr.sbin/ldpd/ldpd.h b/usr.sbin/ldpd/ldpd.h
index 8d97bca5cb6..e6c9ed91895 100644
--- a/usr.sbin/ldpd/ldpd.h
+++ b/usr.sbin/ldpd/ldpd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ldpd.h,v 1.27 2010/10/07 12:02:23 claudio Exp $ */
+/*	$OpenBSD: ldpd.h,v 1.28 2011/01/10 12:28:25 claudio Exp $ */
 
 /*
  * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org>
@@ -199,7 +199,6 @@ struct iface {
 	LIST_ENTRY(iface)	 entry;
 	struct event		 hello_timer;
 
-	LIST_HEAD(, nbr)	 nbr_list;
 	LIST_HEAD(, lde_nbr)	 lde_nbr_list;
 
 	char			 name[IF_NAMESIZE];
diff --git a/usr.sbin/ldpd/ldpe.c b/usr.sbin/ldpd/ldpe.c
index 6fccf0d379f..c913d6e6d19 100644
--- a/usr.sbin/ldpd/ldpe.c
+++ b/usr.sbin/ldpd/ldpe.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ldpe.c,v 1.13 2010/10/26 12:03:11 claudio Exp $ */
+/*	$OpenBSD: ldpe.c,v 1.14 2011/01/10 12:28:25 claudio Exp $ */
 
 /*
  * Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
@@ -160,7 +160,6 @@ ldpe(struct ldpd_conf *xconf, int pipe_parent2ldpe[2], int pipe_ldpe2lde[2],
 		fatal("can't drop privileges");
 
 	event_init();
-	nbr_init(NBR_HASHSIZE);
 
 	/* setup signal handler */
 	signal_set(&ev_sigint, SIGINT, ldpe_sig_handler, NULL);
@@ -498,22 +497,3 @@ ldpe_iface_ctl(struct ctl_conn *c, unsigned int idx)
 		}
 	}
 }
-
-void
-ldpe_nbr_ctl(struct ctl_conn *c)
-{
-	struct iface	*iface;
-	struct nbr	*nbr;
-	struct ctl_nbr	*nctl;
-
-	LIST_FOREACH(iface, &leconf->iface_list, entry) {
-		LIST_FOREACH(nbr, &iface->nbr_list, entry) {
-			nctl = nbr_to_ctl(nbr);
-			imsg_compose_event(&c->iev,
-			    IMSG_CTL_SHOW_NBR, 0, 0, -1, nctl,
-			    sizeof(struct ctl_nbr));
-		}
-	}
-
-	imsg_compose_event(&c->iev, IMSG_CTL_END, 0, 0, -1, NULL, 0);
-}
diff --git a/usr.sbin/ldpd/ldpe.h b/usr.sbin/ldpd/ldpe.h
index ff651b7a9d8..394ce3b297a 100644
--- a/usr.sbin/ldpd/ldpe.h
+++ b/usr.sbin/ldpd/ldpe.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ldpe.h,v 1.13 2010/11/04 09:52:16 claudio Exp $ */
+/*	$OpenBSD: ldpe.h,v 1.14 2011/01/10 12:28:25 claudio Exp $ */
 
 /*
  * Copyright (c) 2004, 2005, 2008 Esben Norby <norby@openbsd.org>
@@ -35,7 +35,7 @@ struct mapping_entry {
 };
 
 struct nbr {
-	LIST_ENTRY(nbr)		 entry, hash;
+	RB_ENTRY(nbr)		 id_tree, addr_tree, pid_tree;
 	struct evbuf		 wbuf;
 	struct event		 rev;
 	struct event		 inactivity_timer;
@@ -119,7 +119,6 @@ int		 ldpe_imsg_compose_lde(int, u_int32_t, pid_t, void *,
 u_int32_t	 ldpe_router_id(void);
 void		 ldpe_fib_update(int);
 void		 ldpe_iface_ctl(struct ctl_conn *, unsigned int);
-void		 ldpe_nbr_ctl(struct ctl_conn *);
 
 /* interface.c */
 int		 if_fsm(struct iface *, enum iface_event);
@@ -144,12 +143,11 @@ int	 if_set_tos(int, int);
 int	 if_set_reuse(int, int);
 
 /* neighbor.c */
-void		 nbr_init(u_int32_t);
 struct nbr	*nbr_new(u_int32_t, u_int16_t, struct iface *);
 void		 nbr_del(struct nbr *);
 
-struct nbr	*nbr_find_ip(struct iface *, u_int32_t);
-struct nbr	*nbr_find_ldpid(struct iface *, u_int32_t, u_int16_t);
+struct nbr	*nbr_find_ip(u_int32_t);
+struct nbr	*nbr_find_ldpid(u_int32_t, u_int16_t);
 struct nbr	*nbr_find_peerid(u_int32_t);
 
 int	 nbr_fsm(struct nbr *, enum nbr_event);
@@ -180,6 +178,7 @@ void			 nbr_mapping_list_clr(struct nbr *,
 			    struct mapping_head *);
 
 struct ctl_nbr	*nbr_to_ctl(struct nbr *);
+void		 ldpe_nbr_ctl(struct ctl_conn *);
 
 /* packet.c */
 int	 gen_ldp_hdr(struct ibuf *, struct iface *, u_int16_t);
diff --git a/usr.sbin/ldpd/neighbor.c b/usr.sbin/ldpd/neighbor.c
index 918c4fe1b4e..a446cd2ebb5 100644
--- a/usr.sbin/ldpd/neighbor.c
+++ b/usr.sbin/ldpd/neighbor.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: neighbor.c,v 1.22 2010/10/26 12:22:35 claudio Exp $ */
+/*	$OpenBSD: neighbor.c,v 1.23 2011/01/10 12:28:25 claudio Exp $ */
 
 /*
  * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org>
@@ -37,6 +37,7 @@
 #include "ldpd.h"
 #include "ldp.h"
 #include "ldpe.h"
+#include "control.h"
 #include "log.h"
 #include "lde.h"
 
@@ -44,15 +45,43 @@ int	nbr_establish_connection(struct nbr *);
 void	nbr_send_labelmappings(struct nbr *);
 int	nbr_act_session_operational(struct nbr *);
 
-LIST_HEAD(nbr_head, nbr);
+static __inline int nbr_id_compare(struct nbr *, struct nbr *);
+static __inline int nbr_addr_compare(struct nbr *, struct nbr *);
+static __inline int nbr_pid_compare(struct nbr *, struct nbr *);
+
+RB_HEAD(nbr_id_head, nbr);
+RB_PROTOTYPE(nbr_id_head, nbr, id_tree, nbr_id_compare)
+RB_GENERATE(nbr_id_head, nbr, id_tree, nbr_id_compare)
+RB_HEAD(nbr_addr_head, nbr);
+RB_PROTOTYPE(nbr_addr_head, nbr, addr_tree, nbr_addr_compare)
+RB_GENERATE(nbr_addr_head, nbr, addr_tree, nbr_addr_compare)
+RB_HEAD(nbr_pid_head, nbr);
+RB_PROTOTYPE(nbr_pid_head, nbr, pid_tree, nbr_pid_compare)
+RB_GENERATE(nbr_pid_head, nbr, pid_tree, nbr_pid_compare)
+
+static __inline int
+nbr_id_compare(struct nbr *a, struct nbr *b)
+{
+	if (ntohl(a->id.s_addr) - ntohl(b->id.s_addr) == 0)
+		return (a->lspace - b->lspace);
+	return (ntohl(a->id.s_addr) - ntohl(b->id.s_addr));
+}
+
+static __inline int
+nbr_addr_compare(struct nbr *a, struct nbr *b)
+{
+	return (ntohl(a->addr.s_addr) - ntohl(b->addr.s_addr));
+}
 
-struct nbr_table {
-	struct nbr_head		*hashtbl;
-	u_int32_t		 hashmask;
-} nbrtable;
+static __inline int
+nbr_pid_compare(struct nbr *a, struct nbr *b)
+{
+	return (a->peerid - b->peerid);
+}
 
-#define NBR_HASH(x)		\
-	&nbrtable.hashtbl[(x) & nbrtable.hashmask]
+struct nbr_id_head nbrs_by_id = RB_INITIALIZER(&nbrs_by_id);
+struct nbr_addr_head nbrs_by_addr = RB_INITIALIZER(&nbrs_by_addr);
+struct nbr_pid_head nbrs_by_pid = RB_INITIALIZER(&nbrs_by_pid);
 
 u_int32_t	peercnt = NBR_CNTSTART;
 
@@ -206,27 +235,9 @@ nbr_fsm(struct nbr *nbr, enum nbr_event event)
 	return (ret);
 }
 
-void
-nbr_init(u_int32_t hashsize)
-{
-	u_int32_t        hs, i;
-
-	for (hs = 1; hs < hashsize; hs <<= 1)
-		;
-	nbrtable.hashtbl = calloc(hs, sizeof(struct nbr_head));
-	if (nbrtable.hashtbl == NULL)
-		fatal("nbr_init");
-
-	for (i = 0; i < hs; i++)
-		LIST_INIT(&nbrtable.hashtbl[i]);
-
-	nbrtable.hashmask = hs - 1;
-}
-
 struct nbr *
 nbr_new(u_int32_t nbr_id, u_int16_t lspace, struct iface *iface)
 {
-	struct nbr_head	*head;
 	struct nbr	*nbr;
 
 	if ((nbr = calloc(1, sizeof(*nbr))) == NULL)
@@ -237,17 +248,19 @@ nbr_new(u_int32_t nbr_id, u_int16_t lspace, struct iface *iface)
 	nbr->state = NBR_STA_DOWN;
 	nbr->id.s_addr = nbr_id;
 	nbr->lspace = lspace;
+	nbr->iface = iface;
 
 	/* get next unused peerid */
 	while (nbr_find_peerid(++peercnt))
 		;
 	nbr->peerid = peercnt;
-	head = NBR_HASH(nbr->peerid);
-	LIST_INSERT_HEAD(head, nbr, hash);
 
-	/* add to peer list */
-	nbr->iface = iface;
-	LIST_INSERT_HEAD(&iface->nbr_list, nbr, entry);
+	if (RB_INSERT(nbr_pid_head, &nbrs_by_pid, nbr) != NULL)
+		fatalx("nbr_new: RB_INSERT(nbrs_by_pid) failed");
+	if (RB_INSERT(nbr_addr_head, &nbrs_by_addr, nbr) != NULL)
+		fatalx("nbr_new: RB_INSERT(nbrs_by_addr) failed");
+	if (RB_INSERT(nbr_id_head, &nbrs_by_id, nbr) != NULL)
+		fatalx("nbr_new: RB_INSERT(nbrs_by_id) failed");
 
 	TAILQ_INIT(&nbr->mapping_list);
 	TAILQ_INIT(&nbr->withdraw_list);
@@ -280,8 +293,9 @@ nbr_del(struct nbr *nbr)
 
 	nbr_mapping_list_clr(nbr, &nbr->mapping_list);
 
-	LIST_REMOVE(nbr, entry);
-	LIST_REMOVE(nbr, hash);
+	RB_REMOVE(nbr_pid_head, &nbrs_by_pid, nbr);
+	RB_REMOVE(nbr_addr_head, &nbrs_by_addr, nbr);
+	RB_REMOVE(nbr_id_head, &nbrs_by_id, nbr);
 
 	free(nbr->rbuf);
 	free(nbr);
@@ -290,43 +304,26 @@ nbr_del(struct nbr *nbr)
 struct nbr *
 nbr_find_peerid(u_int32_t peerid)
 {
-	struct nbr_head	*head;
-	struct nbr	*nbr;
-
-	head = NBR_HASH(peerid);
-
-	LIST_FOREACH(nbr, head, hash) {
-		if (nbr->peerid == peerid)
-			return (nbr);
-	}
-
-	return (NULL);
+	struct nbr	n;
+	n.peerid = peerid;
+	return (RB_FIND(nbr_pid_head, &nbrs_by_pid, &n));
 }
 
 struct nbr *
-nbr_find_ip(struct iface *iface, u_int32_t rtr_id)
+nbr_find_ip(u_int32_t addr)
 {
-	struct nbr	*nbr;
-
-	LIST_FOREACH(nbr, &iface->nbr_list, entry) {
-		if (nbr->addr.s_addr == rtr_id)
-			return (nbr);
-	}
-
-	return (NULL);
+	struct nbr	n;
+	n.addr.s_addr = addr;
+	return (RB_FIND(nbr_addr_head, &nbrs_by_addr, &n));
 }
 
 struct nbr *
-nbr_find_ldpid(struct iface *iface, u_int32_t rtr_id, u_int16_t lspace)
+nbr_find_ldpid(u_int32_t rtr_id, u_int16_t lspace)
 {
-	struct nbr	*nbr;
-
-	LIST_FOREACH(nbr, &iface->nbr_list, entry) {
-		if (nbr->id.s_addr == rtr_id && nbr->lspace == lspace)
-			return (nbr);
-	}
-
-	return (NULL);
+	struct nbr	n;
+	n.id.s_addr = rtr_id;
+	n.lspace = lspace;
+	return (RB_FIND(nbr_id_head, &nbrs_by_id, &n));
 }
 
 /* timers */
@@ -629,3 +626,17 @@ nbr_to_ctl(struct nbr *nbr)
 
 	return (&nctl);
 }
+
+void
+ldpe_nbr_ctl(struct ctl_conn *c)
+{
+	struct nbr	*nbr;
+	struct ctl_nbr	*nctl;
+
+	RB_FOREACH(nbr, nbr_addr_head, &nbrs_by_addr) {
+		nctl = nbr_to_ctl(nbr);
+		imsg_compose_event(&c->iev, IMSG_CTL_SHOW_NBR, 0, 0, -1, nctl,
+		    sizeof(struct ctl_nbr));
+	}
+	imsg_compose_event(&c->iev, IMSG_CTL_END, 0, 0, -1, NULL, 0);
+}
diff --git a/usr.sbin/ldpd/packet.c b/usr.sbin/ldpd/packet.c
index 932e1daad3e..80c42a09637 100644
--- a/usr.sbin/ldpd/packet.c
+++ b/usr.sbin/ldpd/packet.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: packet.c,v 1.13 2010/11/04 09:52:16 claudio Exp $ */
+/*	$OpenBSD: packet.c,v 1.14 2011/01/10 12:28:25 claudio Exp $ */
 
 /*
  * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org>
@@ -42,7 +42,6 @@
 int		 ldp_hdr_sanity_check(struct ldp_hdr *, u_int16_t,
 		    const struct iface *);
 struct iface	*find_iface(struct ldpd_conf *, unsigned int, struct in_addr);
-struct iface	*session_find_iface(struct ldpd_conf *, struct in_addr);
 ssize_t		 session_get_pdu(struct ibuf_read *, char **);
 
 static int	 msgcnt = 0;
@@ -60,7 +59,8 @@ gen_ldp_hdr(struct ibuf *buf, struct iface *iface, u_int16_t size)
 
 	ldp_hdr.length = htons(size);
 	ldp_hdr.lsr_id = ldpe_router_id();
-	ldp_hdr.lspace_id = iface->lspace_id;
+	if (iface)
+		ldp_hdr.lspace_id = iface->lspace_id;
 
 	return (ibuf_add(buf, &ldp_hdr, LDP_HDR_SIZE));
 }
@@ -253,8 +253,6 @@ void
 session_accept(int fd, short event, void *bula)
 {
 	struct sockaddr_in	 src;
-	struct ldpd_conf	*xconf = bula;
-	struct iface		*iface;
 	struct nbr		*nbr = NULL;
 	int			 newfd;
 	socklen_t		 len = sizeof(src);
@@ -271,18 +269,12 @@ session_accept(int fd, short event, void *bula)
 
 	session_socket_blockmode(newfd, BM_NONBLOCK);
 
-	if ((iface = session_find_iface(xconf, src.sin_addr)) == NULL) {
-		log_debug("sess_recv_packet: cannot find a matching interface");
-		close(newfd);
-		return;
-	}
-
-	nbr = nbr_find_ip(iface, src.sin_addr.s_addr);
+	nbr = nbr_find_ip(src.sin_addr.s_addr);
 	if (nbr == NULL) {
 		struct ibuf	*buf;
 		/* If there is no neighbor matching there is no
 		   Hello adjacency: try to send notification */
-		buf = send_notification(S_NO_HELLO, iface, 0, 0);
+		buf = send_notification(S_NO_HELLO, NULL, 0, 0);
 		write(newfd, buf->buf, buf->wpos);
 		ibuf_free(buf);
 		close(newfd);
@@ -462,31 +454,6 @@ session_close(struct nbr *nbr)
 	close(nbr->fd);
 }
 
-struct iface *
-session_find_iface(struct ldpd_conf *xconf, struct in_addr src)
-{
-	struct iface	*iface = NULL;
-
-	/* returned interface needs to be active */
-	LIST_FOREACH(iface, &xconf->iface_list, entry) {
-		switch (iface->type) {
-		case IF_TYPE_POINTOPOINT:
-			if (iface->dst.s_addr == src.s_addr &&
-			    !iface->passive)
-				return (iface);
-			break;
-		default:
-			if ((iface->addr.s_addr & iface->mask.s_addr) ==
-			    (src.s_addr & iface->mask.s_addr) &&
-			    !iface->passive)
-				return (iface);
-			break;
-		}
-	}
-
-	return (NULL);
-}
-
 ssize_t
 session_get_pdu(struct ibuf_read *r, char **b)
 {