Add support for BGP MPLS VPN aka RFC 4364. This is only the RDE part so

that it is possible to use OpenBGPD as a route-reflector for VPNv4.
Some clean up of the BGP MP code so that multiple protocols are easier
supported. kroute/kernel support not yet done but comming.
OK henning@, reyk@

9 files changed, 453 insertions, 132 deletions

diff --git a/usr.sbin/bgpd/bgpd.h b/usr.sbin/bgpd/bgpd.h
index c78ebd1fb40..16e82ea8ae7 100644
--- a/usr.sbin/bgpd/bgpd.h
+++ b/usr.sbin/bgpd/bgpd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bgpd.h,v 1.251 2010/01/10 00:15:09 claudio Exp $ */
+/*	$OpenBSD: bgpd.h,v 1.252 2010/01/13 06:02:37 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -113,10 +113,11 @@ enum reconf_action {
 #define	AFI_IPv6	2
 
 /* Subsequent Address Family Identifier as per RFC 4760 */
-#define	SAFI_NONE	0x00
-#define	SAFI_UNICAST	0x01
-#define	SAFI_MULTICAST	0x02
-#define	SAFI_MPLS	0x04
+#define	SAFI_NONE	0
+#define	SAFI_UNICAST	1
+#define	SAFI_MULTICAST	2
+#define	SAFI_MPLS	4
+#define	SAFI_MPLSVPN	128
 
 struct aid {
 	u_int16_t	 afi;
@@ -130,33 +131,50 @@ extern const struct aid aid_vals[];
 #define	AID_UNSPEC	0
 #define	AID_INET	1
 #define	AID_INET6	2
-#define	AID_MAX		3
+#define	AID_VPN_IPv4	3
+#define	AID_MAX		4
 
 #define AID_VALS	{					\
 	/* afi, af, safii, name */				\
 	{ AFI_UNSPEC, AF_UNSPEC, SAFI_NONE, "unspec"},		\
 	{ AFI_IPv4, AF_INET, SAFI_UNICAST, "IPv4 unicast" },	\
-	{ AFI_IPv6, AF_INET6, SAFI_UNICAST, "IPv6 unicast" }	\
+	{ AFI_IPv6, AF_INET6, SAFI_UNICAST, "IPv6 unicast" },	\
+	{ AFI_IPv4, AF_INET, SAFI_MPLSVPN, "IPv4 vpn" }		\
 }
 
 #define AID_PTSIZE	{				\
 	0,						\
 	sizeof(struct pt_entry4), 			\
-	sizeof(struct pt_entry6)			\
+	sizeof(struct pt_entry6),			\
+	sizeof(struct pt_entry_vpn4)			\
 }
 
+struct vpn4_addr {
+	u_int64_t	rd;
+	struct in_addr	addr;
+	u_int8_t	labelstack[21];	/* max that makes sense */
+	u_int8_t	labellen;
+	u_int8_t	pad1;
+	u_int8_t	pad2;
+};
+
+#define BGP_MPLS_BOS	0x01
+
 struct bgpd_addr {
-	u_int8_t	aid;
 	union {
 		struct in_addr		v4;
 		struct in6_addr		v6;
-		u_int8_t		addr8[16];
-		u_int16_t		addr16[8];
-		u_int32_t		addr32[4];
+		struct vpn4_addr	vpn4;
+		/* maximum size for a prefix is 256 bits */
+		u_int8_t		addr8[32];
+		u_int16_t		addr16[16];
+		u_int32_t		addr32[8];
 	} ba;		    /* 128-bit address */
 	u_int32_t	scope_id;	/* iface scope id for v6 */
+	u_int8_t	aid;
 #define	v4	ba.v4
 #define	v6	ba.v6
+#define	vpn4	ba.vpn4
 #define	addr8	ba.addr8
 #define	addr16	ba.addr16
 #define	addr32	ba.addr32
diff --git a/usr.sbin/bgpd/control.c b/usr.sbin/bgpd/control.c
index a91f1636ab0..a7430a63885 100644
--- a/usr.sbin/bgpd/control.c
+++ b/usr.sbin/bgpd/control.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: control.c,v 1.67 2009/12/08 15:54:50 jsg Exp $ */
+/*	$OpenBSD: control.c,v 1.68 2010/01/13 06:02:37 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -404,8 +404,7 @@ control_dispatch_msg(struct pollfd *pfd, u_int *ctl_cnt)
 					break;
 				}
 				if ((imsg.hdr.type == IMSG_CTL_SHOW_RIB_PREFIX)
-				    && (ribreq->prefix.aid != AID_INET)
-				    && (ribreq->prefix.aid != AID_INET6)) {
+				    && (ribreq->prefix.aid == AID_UNSPEC)) {
 					/* malformed request, must specify af */
 					control_result(c, CTL_RES_PARSE_ERROR);
 					break;
diff --git a/usr.sbin/bgpd/parse.y b/usr.sbin/bgpd/parse.y
index 779c3f923da..11b5742445f 100644
--- a/usr.sbin/bgpd/parse.y
+++ b/usr.sbin/bgpd/parse.y
@@ -1,4 +1,4 @@
-/*	$OpenBSD: parse.y,v 1.247 2010/01/11 03:24:35 deraadt Exp $ */
+/*	$OpenBSD: parse.y,v 1.248 2010/01/13 06:02:37 claudio Exp $ */
 
 /*
  * Copyright (c) 2002, 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -852,9 +852,11 @@ peeropts	: REMOTEAS as4number	{
 			if (!strcmp($3, "none")) {
 				safi = SAFI_UNICAST;
 				val = 0;
-			} else if (!strcmp($3, "unicast"))
+			} else if (!strcmp($3, "unicast")) {
 				safi = SAFI_UNICAST;
-			else {
+			} else if (!strcmp($3, "vpn")) {
+				safi = SAFI_MPLSVPN;
+			} else {
 				yyerror("unknown/unsupported SAFI \"%s\"",
 				    $3);
 				free($3);
diff --git a/usr.sbin/bgpd/rde.c b/usr.sbin/bgpd/rde.c
index d323b9a102b..a5d16e70045 100644
--- a/usr.sbin/bgpd/rde.c
+++ b/usr.sbin/bgpd/rde.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.c,v 1.283 2010/01/11 01:34:35 claudio Exp $ */
+/*	$OpenBSD: rde.c,v 1.284 2010/01/13 06:02:37 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -51,7 +51,7 @@ void		 rde_update_withdraw(struct rde_peer *, struct bgpd_addr *,
 int		 rde_attr_parse(u_char *, u_int16_t, struct rde_peer *,
 		     struct rde_aspath *, struct mpattr *);
 u_int8_t	 rde_attr_missing(struct rde_aspath *, int, u_int16_t);
-int		 rde_get_mp_nexthop(u_char *, u_int16_t, u_int16_t,
+int		 rde_get_mp_nexthop(u_char *, u_int16_t, u_int8_t,
 		     struct rde_aspath *);
 int		 rde_update_extract_prefix(u_char *, u_int16_t, void *,
 		     u_int8_t, u_int8_t);
@@ -59,6 +59,8 @@ int		 rde_update_get_prefix(u_char *, u_int16_t, struct bgpd_addr *,
 		     u_int8_t *);
 int		 rde_update_get_prefix6(u_char *, u_int16_t, struct bgpd_addr *,
 		     u_int8_t *);
+int		 rde_update_get_vpn4(u_char *, u_int16_t, struct bgpd_addr *,
+		     u_int8_t *);
 void		 rde_update_err(struct rde_peer *, u_int8_t , u_int8_t,
 		     void *, u_int16_t);
 void		 rde_update_log(const char *, u_int16_t,
@@ -85,7 +87,7 @@ void		 rde_softreconfig_out(struct rib_entry *, void *);
 void		 rde_softreconfig_in(struct rib_entry *, void *);
 void		 rde_softreconfig_load(struct rib_entry *, void *);
 void		 rde_update_queue_runner(void);
-void		 rde_update6_queue_runner(void);
+void		 rde_update6_queue_runner(u_int8_t);
 
 void		 peer_init(u_int32_t);
 void		 peer_shutdown(void);
@@ -158,6 +160,7 @@ rde_main(int pipe_m2r[2], int pipe_s2r[2], int pipe_m2s[2], int pipe_s2rctl[2],
 	void			*newp;
 	u_int			 pfd_elms = 0, i, j;
 	int			 timeout;
+	u_int8_t		 aid;
 
 	switch (pid = fork()) {
 	case -1:
@@ -310,7 +313,8 @@ rde_main(int pipe_m2r[2], int pipe_s2r[2], int pipe_m2s[2], int pipe_s2rctl[2],
 		}
 
 		rde_update_queue_runner();
-		rde_update6_queue_runner();
+		for (aid = AID_INET6; aid < AID_MAX; aid++)
+			rde_update6_queue_runner(aid);
 		if (ibuf_se_ctl->w.queued <= 0)
 			rib_dump_runner();
 	}
@@ -424,7 +428,7 @@ rde_dispatch_imsg_session(struct imsgbuf *ibuf)
 					goto badnet;
 				network_add(&netconf_s, 0);
 				break;
-				case AID_INET6:
+			case AID_INET6:
 				if (netconf_s.prefixlen > 128)
 					goto badnet;
 				network_add(&netconf_s, 0);
@@ -922,6 +926,32 @@ rde_update_dispatch(struct imsg *imsg)
 				rde_update_withdraw(peer, &prefix, prefixlen);
 			}
 			break;
+		case AID_VPN_IPv4:
+			while (mplen > 0) {
+				if ((pos = rde_update_get_vpn4(mpp, mplen,
+				    &prefix, &prefixlen)) == -1) {
+					log_peer_warnx(&peer->conf,
+					    "bad VPNv4 withdraw prefix");
+					rde_update_err(peer, ERR_UPDATE,
+					    ERR_UPD_OPTATTR,
+					    mpa.unreach, mpa.unreach_len);
+					goto done;
+				}
+				if (prefixlen > 32) {
+					log_peer_warnx(&peer->conf,
+					    "bad VPNv4 withdraw prefix");
+					rde_update_err(peer, ERR_UPDATE,
+					    ERR_UPD_OPTATTR,
+					    mpa.unreach, mpa.unreach_len);
+					goto done;
+				}
+
+				mpp += pos;
+				mplen -= pos;
+
+				rde_update_withdraw(peer, &prefix, prefixlen);
+			}
+			break;
 		default:
 			/* silently ignore unsupported multiprotocol AF */
 			break;
@@ -1016,8 +1046,8 @@ rde_update_dispatch(struct imsg *imsg)
 			(void)nexthop_delete(asp->nexthop);
 			asp->nexthop = NULL;
 		}
-		if ((pos = rde_get_mp_nexthop(mpp, mplen, afi, asp)) == -1) {
-			log_peer_warnx(&peer->conf, "bad IPv6 nlri prefix");
+		if ((pos = rde_get_mp_nexthop(mpp, mplen, aid, asp)) == -1) {
+			log_peer_warnx(&peer->conf, "bad nlri prefix");
 			rde_update_err(peer, ERR_UPDATE, ERR_UPD_OPTATTR,
 			    mpa.reach, mpa.reach_len);
 			goto done;
@@ -1062,6 +1092,42 @@ rde_update_dispatch(struct imsg *imsg)
 
 			}
 			break;
+		case AID_VPN_IPv4:
+			while (mplen > 0) {
+				if ((pos = rde_update_get_vpn4(mpp, mplen,
+				    &prefix, &prefixlen)) == -1) {
+					log_peer_warnx(&peer->conf,
+					    "bad VPNv4 nlri prefix");
+					rde_update_err(peer, ERR_UPDATE,
+					    ERR_UPD_OPTATTR,
+					    mpa.reach, mpa.reach_len);
+					goto done;
+				}
+				if (prefixlen > 32) {
+					rde_update_err(peer, ERR_UPDATE,
+					    ERR_UPD_OPTATTR,
+					    mpa.reach, mpa.reach_len);
+					goto done;
+				}
+
+				mpp += pos;
+				mplen -= pos;
+
+				rde_update_update(peer, asp, &prefix,
+				    prefixlen);
+
+				/* max prefix checker */
+				if (peer->conf.max_prefix &&
+				    peer->prefix_cnt >= peer->conf.max_prefix) {
+					log_peer_warnx(&peer->conf,
+					    "prefix limit reached");
+					rde_update_err(peer, ERR_CEASE,
+					    ERR_CEASE_MAX_PREFIX, NULL, 0);
+					goto done;
+				}
+
+			}
+			break;
 		default:
 			/* silently ignore unsupported multiprotocol AF */
 			break;
@@ -1502,7 +1568,7 @@ rde_attr_missing(struct rde_aspath *a, int ebgp, u_int16_t nlrilen)
 }
 
 int
-rde_get_mp_nexthop(u_char *data, u_int16_t len, u_int16_t afi,
+rde_get_mp_nexthop(u_char *data, u_int16_t len, u_int8_t aid,
     struct rde_aspath *asp)
 {
 	struct bgpd_addr	nexthop;
@@ -1519,8 +1585,9 @@ rde_get_mp_nexthop(u_char *data, u_int16_t len, u_int16_t afi,
 		return (-1);
 
 	bzero(&nexthop, sizeof(nexthop));
-	switch (afi) {
-	case AFI_IPv6:
+	nexthop.aid = aid;
+	switch (aid) {
+	case AID_INET6:
 		/*
 		 * RFC2545 describes that there may be a link-local
 		 * address carried in nexthop. Yikes!
@@ -1533,27 +1600,48 @@ rde_get_mp_nexthop(u_char *data, u_int16_t len, u_int16_t afi,
 			log_warnx("bad multiprotocol nexthop, bad size");
 			return (-1);
 		}
-		nexthop.aid = AID_INET6;
 		memcpy(&nexthop.v6.s6_addr, data, 16);
-		asp->nexthop = nexthop_get(&nexthop);
+		break;
+	case AID_VPN_IPv4:
 		/*
-		 * lock the nexthop because it is not yet linked else
-		 * withdraws may remove this nexthop which in turn would
-		 * cause a use after free error.
+		 * Neither RFC4364 nor RFC3107 specify the format of the
+		 * nexthop in an explicit way. The quality of RFC went down
+		 * the toilet the larger the the number got. 
+		 * RFC4364 is very confusing about VPN-IPv4 address and the
+		 * VPN-IPv4 prefix that carries also a MPLS label.
+		 * So the nexthop is a 12-byte address with a 64bit RD and
+		 * an IPv4 address following. In the nexthop case the RD can
+		 * be ignored.
+		 * Since the nexthop has to be in the main IPv4 table just
+		 * create an AID_INET nexthop. So we don't need to handle
+		 * AID_VPN_IPv4 in nexthop and kroute.
 		 */
-		asp->nexthop->refcnt++;
-
-		/* ignore reserved (old SNPA) field as per RFC 4760 */
-		totlen += nhlen + 1;
-		data += nhlen + 1;
-
-		return (totlen);
-	default:
-		log_warnx("bad multiprotocol nexthop, bad AF");
+		if (nhlen != 12) {
+			log_warnx("bad multiprotocol nexthop, bad size");
+			return (-1);
+		}
+		data += sizeof(u_int64_t);
+		nexthop.aid = AID_INET;
+		memcpy(&nexthop.v4, data, sizeof(nexthop.v4));
 		break;
+	default:
+		log_warnx("bad multiprotocol nexthop, bad AID");
+		return (-1);
 	}
 
-	return (-1);
+	asp->nexthop = nexthop_get(&nexthop);
+	/*
+	 * lock the nexthop because it is not yet linked else
+	 * withdraws may remove this nexthop which in turn would
+	 * cause a use after free error.
+	 */
+	asp->nexthop->refcnt++;
+
+	/* ignore reserved (old SNPA) field as per RFC4760 */
+	totlen += nhlen + 1;
+	data += nhlen + 1;
+
+	return (totlen);
 }
 
 int
@@ -1630,6 +1718,61 @@ rde_update_get_prefix6(u_char *p, u_int16_t len, struct bgpd_addr *prefix,
 	return (plen + 1);	/* pfxlen needs to be added */
 }
 
+int
+rde_update_get_vpn4(u_char *p, u_int16_t len, struct bgpd_addr *prefix,
+    u_int8_t *prefixlen)
+{
+	int		 rv, done = 0;
+	u_int8_t	 pfxlen;
+	u_int16_t	 plen;
+
+	if (len < 1)
+		return (-1);
+
+	memcpy(&pfxlen, p, 1);
+	p += 1;
+	plen = 1;
+
+	bzero(prefix, sizeof(struct bgpd_addr));
+
+	/* label stack */
+	do {
+		if (len - plen < 3 || pfxlen < 3 * 8)
+			return (-1);
+		if (prefix->vpn4.labellen + 3U >
+		    sizeof(prefix->vpn4.labelstack))
+			return (-1);
+		prefix->vpn4.labelstack[prefix->vpn4.labellen++] = *p++;
+		prefix->vpn4.labelstack[prefix->vpn4.labellen++] = *p++;
+		prefix->vpn4.labelstack[prefix->vpn4.labellen] = *p++;
+		if (prefix->vpn4.labelstack[prefix->vpn4.labellen] &
+		    BGP_MPLS_BOS)
+			done = 1;
+		prefix->vpn4.labellen++;
+		plen += 3;
+		pfxlen -= 3 * 8;
+	} while (!done);
+
+	/* RD */
+	if (len - plen < (int)sizeof(u_int64_t) ||
+	    pfxlen < sizeof(u_int64_t) * 8)
+		return (-1);
+	memcpy(&prefix->vpn4.rd, p, sizeof(u_int64_t));
+	pfxlen -= sizeof(u_int64_t) * 8;
+	p += sizeof(u_int64_t);
+	plen += sizeof(u_int64_t);
+
+	/* prefix */
+	prefix->aid = AID_VPN_IPv4;
+	*prefixlen = pfxlen;
+
+	if ((rv = rde_update_extract_prefix(p, len, &prefix->vpn4.addr,
+	    pfxlen, sizeof(prefix->vpn4.addr))) == -1)
+		return (-1);
+
+	return (plen + rv);
+}
+
 void
 rde_update_err(struct rde_peer *peer, u_int8_t error, u_int8_t suberr,
     void *data, u_int16_t size)
@@ -2133,6 +2276,10 @@ rde_send_kroute(struct prefix *new, struct prefix *old)
 		    sizeof(kl6)) == -1)
 			fatal("imsg_compose error");
 		break;
+	case AID_VPN_IPv4:
+		break;
+	default:
+		fatal("rde_send_kroute: unhandled AID");
 	}
 }
 
@@ -2418,7 +2565,7 @@ rde_update_queue_runner(void)
 			/* first withdraws */
 			wpos = 2; /* reserve space for the length field */
 			r = up_dump_prefix(queue_buf + wpos, len - wpos - 2,
-			    &peer->withdraws, peer);
+			    &peer->withdraws[AID_INET], peer);
 			wd_len = r;
 			/* write withdraws length filed */
 			wd_len = htons(wd_len);
@@ -2466,7 +2613,7 @@ rde_update_queue_runner(void)
 }
 
 void
-rde_update6_queue_runner(void)
+rde_update6_queue_runner(u_int8_t aid)
 {
 	struct rde_peer		*peer;
 	u_char			*b;
@@ -2482,7 +2629,7 @@ rde_update6_queue_runner(void)
 			if (peer->state != PEER_UP)
 				continue;
 			len = sizeof(queue_buf) - MSGSIZE_HEADER;
-			b = up_dump_mp_unreach(queue_buf, &len, peer);
+			b = up_dump_mp_unreach(queue_buf, &len, peer, aid);
 
 			if (b == NULL)
 				continue;
@@ -2505,7 +2652,7 @@ rde_update6_queue_runner(void)
 			if (peer->state != PEER_UP)
 				continue;
 			len = sizeof(queue_buf) - MSGSIZE_HEADER;
-			r = up_dump_mp_reach(queue_buf, &len, peer);
+			r = up_dump_mp_reach(queue_buf, &len, peer, aid);
 			switch (r) {
 			case -2:
 				continue;
diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h
index 0d66294c990..6742ebdc64a 100644
--- a/usr.sbin/bgpd/rde.h
+++ b/usr.sbin/bgpd/rde.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.h,v 1.128 2010/01/10 08:32:08 claudio Exp $ */
+/*	$OpenBSD: rde.h,v 1.129 2010/01/13 06:02:37 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org> and
@@ -56,10 +56,8 @@ struct rde_peer {
 	struct bgpd_addr		 local_v6_addr;
 	struct uptree_prefix		 up_prefix;
 	struct uptree_attr		 up_attrs;
-	struct uplist_attr		 updates;
-	struct uplist_prefix		 withdraws;
-	struct uplist_attr		 updates6;
-	struct uplist_prefix		 withdraws6;
+	struct uplist_attr		 updates[AID_MAX];
+	struct uplist_prefix		 withdraws[AID_MAX];
 	struct capabilities		 capa;
 	u_int64_t			 prefix_rcvd_update;
 	u_int64_t			 prefix_rcvd_withdraw;
@@ -241,6 +239,19 @@ struct pt_entry6 {
 	struct in6_addr			 prefix6;
 };
 
+struct pt_entry_vpn4 {
+	RB_ENTRY(pt_entry)		 pt_e;
+	u_int8_t			 aid;
+	u_int8_t			 prefixlen;
+	u_int16_t			 refcnt;
+	struct in_addr			 prefix4;
+	u_int64_t			 rd;
+	u_int8_t			 labelstack[21];
+	u_int8_t			 labellen;
+	u_int8_t			 pad1;
+	u_int8_t			 pad2;
+};
+
 struct rib_context {
 	LIST_ENTRY(rib_context)		 entry;
 	struct rib_entry		*ctx_re;
@@ -425,8 +436,10 @@ int		 up_generate_marker(struct rde_peer *, u_int8_t);
 int		 up_dump_prefix(u_char *, int, struct uplist_prefix *,
 		     struct rde_peer *);
 int		 up_dump_attrnlri(u_char *, int, struct rde_peer *);
-u_char		*up_dump_mp_unreach(u_char *, u_int16_t *, struct rde_peer *);
-int		 up_dump_mp_reach(u_char *, u_int16_t *, struct rde_peer *);
+u_char		*up_dump_mp_unreach(u_char *, u_int16_t *, struct rde_peer *,
+		     u_int8_t);
+int		 up_dump_mp_reach(u_char *, u_int16_t *, struct rde_peer *,
+		     u_int8_t);
 
 /* rde_prefix.c */
 #define pt_empty(pt)	((pt)->refcnt == 0)
diff --git a/usr.sbin/bgpd/rde_prefix.c b/usr.sbin/bgpd/rde_prefix.c
index 019e8123464..ee6a5522107 100644
--- a/usr.sbin/bgpd/rde_prefix.c
+++ b/usr.sbin/bgpd/rde_prefix.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde_prefix.c,v 1.30 2009/12/01 14:28:05 claudio Exp $ */
+/*	$OpenBSD: rde_prefix.c,v 1.31 2010/01/13 06:02:37 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org>
@@ -81,6 +81,14 @@ pt_getaddr(struct pt_entry *pte, struct bgpd_addr *addr)
 		    sizeof(addr->v6));
 		/* XXX scope_id ??? */
 		break;
+	case AID_VPN_IPv4:
+		addr->vpn4.addr = ((struct pt_entry_vpn4 *)pte)->prefix4;
+		addr->vpn4.rd = ((struct pt_entry_vpn4 *)pte)->rd;
+		addr->vpn4.labellen = ((struct pt_entry_vpn4 *)pte)->labellen;
+		memcpy(addr->vpn4.labelstack,
+		    ((struct pt_entry_vpn4 *)pte)->labelstack,
+		    addr->vpn4.labellen);
+		break;
 	default:
 		fatalx("pt_getaddr: unknown af");
 	}
@@ -89,15 +97,15 @@ pt_getaddr(struct pt_entry *pte, struct bgpd_addr *addr)
 struct pt_entry *
 pt_fill(struct bgpd_addr *prefix, int prefixlen)
 {
-	static struct pt_entry4	pte4;
-	static struct pt_entry6	pte6;
-	in_addr_t		addr_hbo;
+	static struct pt_entry4		pte4;
+	static struct pt_entry6		pte6;
+	static struct pt_entry_vpn4	pte_vpn4;
+	in_addr_t			addr_hbo;
 
 	switch (prefix->aid) {
 	case AID_INET:
 		bzero(&pte4, sizeof(pte4));
-		if (af2aid(AF_INET, 0, &pte4.aid))
-			fatalx("pt_fill: unknown aid");
+		pte4.aid = prefix->aid;
 		if (prefixlen > 32)
 			fatalx("pt_fill: bad IPv4 prefixlen");
 		addr_hbo = ntohl(prefix->v4.s_addr);
@@ -107,16 +115,28 @@ pt_fill(struct bgpd_addr *prefix, int prefixlen)
 		return ((struct pt_entry *)&pte4);
 	case AID_INET6:
 		bzero(&pte6, sizeof(pte6));
-		if (af2aid(AF_INET6, 0, &pte6.aid))
-			fatalx("pt_fill: unknown aid");
+		pte6.aid = prefix->aid;
 		if (prefixlen > 128)
 			fatalx("pt_get: bad IPv6 prefixlen");
 		pte6.prefixlen = prefixlen;
 		inet6applymask(&pte6.prefix6, &prefix->v6, prefixlen);
 		return ((struct pt_entry *)&pte6);
+	case AID_VPN_IPv4:
+		bzero(&pte_vpn4, sizeof(pte_vpn4));
+		pte_vpn4.aid = prefix->aid;
+		if (prefixlen > 32)
+			fatalx("pt_fill: bad IPv4 prefixlen");
+		addr_hbo = ntohl(prefix->vpn4.addr.s_addr);
+		pte_vpn4.prefix4.s_addr = htonl(addr_hbo &
+		    prefixlen2mask(prefixlen));
+		pte_vpn4.prefixlen = prefixlen;
+		pte_vpn4.rd = prefix->vpn4.rd;
+		pte_vpn4.labellen = prefix->vpn4.labellen;
+		memcpy(pte_vpn4.labelstack, prefix->vpn4.labelstack,
+		    prefix->vpn4.labellen);
+		return ((struct pt_entry *)&pte_vpn4);
 	default:
-		log_warnx("pt_fill: unknown af");
-		return (NULL);
+		fatalx("pt_fill: unknown af");
 	}
 }
 
@@ -164,6 +184,7 @@ pt_lookup(struct bgpd_addr *addr)
 
 	switch (addr->aid) {
 	case AID_INET:
+	case AID_VPN_IPv4:
 		i = 32;
 		break;
 	case AID_INET6:
@@ -183,9 +204,10 @@ pt_lookup(struct bgpd_addr *addr)
 int
 pt_prefix_cmp(const struct pt_entry *a, const struct pt_entry *b)
 {
-	const struct pt_entry4	*a4, *b4;
-	const struct pt_entry6	*a6, *b6;
-	int			 i;
+	const struct pt_entry4		*a4, *b4;
+	const struct pt_entry6		*a6, *b6;
+	const struct pt_entry_vpn4	*va4, *vb4;
+	int				 i;
 
 	if (a->aid > b->aid)
 		return (1);
@@ -219,6 +241,22 @@ pt_prefix_cmp(const struct pt_entry *a, const struct pt_entry *b)
 		if (a6->prefixlen > b6->prefixlen)
 			return (1);
 		return (0);
+	case AID_VPN_IPv4:
+		va4 = (const struct pt_entry_vpn4 *)a;
+		vb4 = (const struct pt_entry_vpn4 *)b;
+		if (ntohl(va4->prefix4.s_addr) > ntohl(vb4->prefix4.s_addr))
+			return (1);
+		if (ntohl(va4->prefix4.s_addr) < ntohl(vb4->prefix4.s_addr))
+			return (-1);
+		if (va4->prefixlen > vb4->prefixlen)
+			return (1);
+		if (va4->prefixlen < vb4->prefixlen)
+			return (-1);
+		if (betoh64(va4->rd) > betoh64(vb4->rd))
+			return (1);
+		if (betoh64(va4->rd) < betoh64(vb4->rd))
+			return (-1);
+		return (0);
 	default:
 		fatalx("pt_prefix_cmp: unknown af");
 	}
diff --git a/usr.sbin/bgpd/rde_rib.c b/usr.sbin/bgpd/rde_rib.c
index e8c81c121bb..c8a605d7d7d 100644
--- a/usr.sbin/bgpd/rde_rib.c
+++ b/usr.sbin/bgpd/rde_rib.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde_rib.c,v 1.119 2010/01/10 00:15:09 claudio Exp $ */
+/*	$OpenBSD: rde_rib.c,v 1.120 2010/01/13 06:02:37 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org>
@@ -175,6 +175,7 @@ rib_lookup(struct rib *rib, struct bgpd_addr *addr)
 
 	switch (addr->aid) {
 	case AID_INET:
+	case AID_VPN_IPv4:
 		for (i = 32; i >= 0; i--) {
 			re = rib_get(rib, addr, i);
 			if (re != NULL)
@@ -661,6 +662,24 @@ prefix_compare(const struct bgpd_addr *a, const struct bgpd_addr *b,
 				    (b->v6.s6_addr[prefixlen / 8] & m));
 		}
 		return (0);
+	case AID_VPN_IPv4:
+		if (prefixlen > 32)
+			fatalx("prefix_cmp: bad IPv4 VPN prefixlen");
+		if (betoh64(a->vpn4.rd) > betoh64(b->vpn4.rd))
+			return (1);
+		if (betoh64(a->vpn4.rd) < betoh64(b->vpn4.rd))
+			return (-1);
+		mask = htonl(prefixlen2mask(prefixlen));
+		aa = ntohl(a->vpn4.addr.s_addr & mask);
+		ba = ntohl(b->vpn4.addr.s_addr & mask);
+		if (aa != ba)
+			return (aa - ba);
+		if (a->vpn4.labellen > b->vpn4.labellen)
+			return (1);
+		if (a->vpn4.labellen < b->vpn4.labellen)
+			return (-1);
+		return (memcmp(a->vpn4.labelstack, b->vpn4.labelstack,
+		    a->vpn4.labellen));
 	default:
 		fatalx("prefix_cmp: unknown af");
 	}
@@ -807,16 +826,33 @@ prefix_write(u_char *buf, int len, struct bgpd_addr *prefix, u_int8_t plen)
 {
 	int	totlen;
 
-	if (prefix->aid != AID_INET && prefix->aid != AID_INET6)
-		return (-1);
-
-	totlen = PREFIX_SIZE(plen);
+	switch (prefix->aid) {
+	case AID_INET:
+	case AID_INET6:
+		totlen = PREFIX_SIZE(plen);
 
-	if (totlen > len)
+		if (totlen > len)
+			return (-1);
+		*buf++ = plen;
+		memcpy(buf, &prefix->ba, totlen - 1);
+		return (totlen);
+	case AID_VPN_IPv4:
+		totlen = PREFIX_SIZE(plen) + sizeof(prefix->vpn4.rd) +
+		    prefix->vpn4.labellen;
+		plen += (sizeof(prefix->vpn4.rd) + prefix->vpn4.labellen) * 8;
+
+		if (totlen > len)
+			return (-1);
+		*buf++ = plen;
+		memcpy(buf, &prefix->vpn4.labelstack, prefix->vpn4.labellen);
+		buf += prefix->vpn4.labellen;
+		memcpy(buf, &prefix->vpn4.rd, sizeof(prefix->vpn4.rd));
+		buf += sizeof(prefix->vpn4.rd);
+		memcpy(buf, &prefix->vpn4.addr, PREFIX_SIZE(plen) - 1);
+		return (totlen);
+	default:
 		return (-1);
-	*buf++ = plen;
-	memcpy(buf, &prefix->ba, totlen - 1);
-	return (totlen);
+	}
 }
 
 /*
@@ -1277,7 +1313,7 @@ nexthop_hash(struct bgpd_addr *nexthop)
 		    nexthoptable.nexthop_hashmask;
 		break;
 	case AID_INET6:
-		h = hash32_buf(nexthop->v6.s6_addr, sizeof(struct in6_addr),
+		h = hash32_buf(&nexthop->v6, sizeof(struct in6_addr),
 		    HASHINIT) & nexthoptable.nexthop_hashmask;
 		break;
 	default:
diff --git a/usr.sbin/bgpd/rde_update.c b/usr.sbin/bgpd/rde_update.c
index b78b3a49616..c3e63268c08 100644
--- a/usr.sbin/bgpd/rde_update.c
+++ b/usr.sbin/bgpd/rde_update.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde_update.c,v 1.76 2010/01/10 08:32:08 claudio Exp $ */
+/*	$OpenBSD: rde_update.c,v 1.77 2010/01/13 06:02:37 claudio Exp $ */
 
 /*
  * Copyright (c) 2004 Claudio Jeker <claudio@openbsd.org>
@@ -65,10 +65,12 @@ RB_GENERATE(uptree_attr, update_attr, entry, up_attr_cmp)
 void
 up_init(struct rde_peer *peer)
 {
-	TAILQ_INIT(&peer->updates);
-	TAILQ_INIT(&peer->withdraws);
-	TAILQ_INIT(&peer->updates6);
-	TAILQ_INIT(&peer->withdraws6);
+	u_int8_t	i;
+
+	for (i = 0; i < AID_MAX; i++) {
+		TAILQ_INIT(&peer->updates[i]);
+		TAILQ_INIT(&peer->withdraws[i]);
+	}
 	RB_INIT(&peer->up_prefix);
 	RB_INIT(&peer->up_attrs);
 	peer->up_pcnt = 0;
@@ -103,8 +105,10 @@ up_clear(struct uplist_attr *updates, struct uplist_prefix *withdraws)
 void
 up_down(struct rde_peer *peer)
 {
-	up_clear(&peer->updates, &peer->withdraws);
-	up_clear(&peer->updates6, &peer->withdraws6);
+	u_int8_t	i;
+
+	for (i = 0; i < AID_MAX; i++)
+		up_clear(&peer->updates[i], &peer->withdraws[i]);
 
 	RB_INIT(&peer->up_prefix);
 	RB_INIT(&peer->up_attrs);
@@ -140,6 +144,25 @@ up_prefix_cmp(struct update_prefix *a, struct update_prefix *b)
 		if (i < 0)
 			return (-1);
 		break;
+	case AID_VPN_IPv4:
+		if (betoh64(a->prefix.vpn4.rd) < betoh64(b->prefix.vpn4.rd))
+			return (-1);
+		if (betoh64(a->prefix.vpn4.rd) > betoh64(b->prefix.vpn4.rd))
+			return (1);
+		if (ntohl(a->prefix.v4.s_addr) < ntohl(b->prefix.v4.s_addr))
+			return (-1);
+		if (ntohl(a->prefix.v4.s_addr) > ntohl(b->prefix.v4.s_addr))
+			return (1);
+		if (a->prefixlen < b->prefixlen)
+			return (-1);
+		if (a->prefixlen > b->prefixlen)
+			return (1);
+		if (a->prefix.vpn4.labellen < b->prefix.vpn4.labellen)
+			return (-1);
+		if (a->prefix.vpn4.labellen > b->prefix.vpn4.labellen)
+			return (1);
+		return (memcmp(a->prefix.vpn4.labelstack,
+		    b->prefix.vpn4.labelstack, a->prefix.vpn4.labellen));
 	default:
 		fatalx("pt_prefix_cmp: unknown af");
 	}
@@ -174,18 +197,8 @@ up_add(struct rde_peer *peer, struct update_prefix *p, struct update_attr *a)
 	struct uplist_attr	*upl = NULL;
 	struct uplist_prefix	*wdl = NULL;
 
-	switch (p->prefix.aid) {
-	case AID_INET:
-		upl = &peer->updates;
-		wdl = &peer->withdraws;
-		break;
-	case AID_INET6:
-		upl = &peer->updates6;
-		wdl = &peer->withdraws6;
-		break;
-	default:
-		fatalx("up_add: unknown AID");
-	}
+	upl = &peer->updates[p->prefix.aid];
+	wdl = &peer->withdraws[p->prefix.aid];
 
 	/* 1. search for attr */
 	if (a != NULL && (na = RB_FIND(uptree_attr, &peer->up_attrs, a)) ==
@@ -489,18 +502,8 @@ up_generate_marker(struct rde_peer *peer, u_int8_t aid)
 	ua = calloc(1, sizeof(struct update_attr));
 	if (ua == NULL)
 		fatal("up_generate_marker");
-	
 
-	switch (aid) {
-	case AID_INET:
-		upl = &peer->updates;
-		break;
-	case AID_INET6:
-		upl = &peer->updates6;
-		break;
-	default:
-		fatalx("up_generate_marker: unknown AID");
-	}
+	upl = &peer->updates[aid];
 
 	/* 1. search for attr */
 	if ((na = RB_FIND(uptree_attr, &peer->up_attrs, ua)) == NULL) {
@@ -595,9 +598,10 @@ up_generate_mp_reach(struct rde_peer *peer, struct update_attr *upa,
 		upa->mpattr = malloc(upa->mpattr_len);
 		if (upa->mpattr == NULL)
 			fatal("up_generate_mp_reach");
-		tmp = htons(AFI_IPv6);
+		if (aid2afi(aid, &tmp, &upa->mpattr[2]))
+			fatalx("up_generate_mp_reachi: bad AID");
+		tmp = htons(tmp);
 		memcpy(upa->mpattr, &tmp, sizeof(tmp));
-		upa->mpattr[2] = SAFI_UNICAST;
 		upa->mpattr[3] = sizeof(struct in6_addr);
 		upa->mpattr[20] = 0; /* Reserved must be 0 */
 
@@ -637,6 +641,54 @@ up_generate_mp_reach(struct rde_peer *peer, struct update_attr *upa,
 			memcpy(&upa->mpattr[4], &peer->local_v6_addr.v6,
 			    sizeof(struct in6_addr));
 		return (0);
+	case AID_VPN_IPv4:
+		upa->mpattr_len = 17; /* AFI + SAFI + NH LEN + NH + Reserved */
+		upa->mpattr = calloc(upa->mpattr_len, 1);
+		if (upa->mpattr == NULL)
+			fatal("up_generate_mp_reach");
+		if (aid2afi(aid, &tmp, &upa->mpattr[2]))
+			fatalx("up_generate_mp_reachi: bad AID");
+		tmp = htons(tmp);
+		memcpy(upa->mpattr, &tmp, sizeof(tmp));
+		upa->mpattr[3] = sizeof(u_int64_t) + sizeof(struct in_addr);
+
+		/* nexthop dance see also up_get_nexthop() */
+		if (peer->conf.ebgp == 0) {
+			/* ibgp */
+			if (a->nexthop == NULL ||
+			    (a->nexthop->exit_nexthop.aid == AID_INET &&
+			    memcmp(&a->nexthop->exit_nexthop.v4,
+			    &peer->remote_addr.v4, sizeof(struct in_addr))))
+				memcpy(&upa->mpattr[12],
+				    &peer->local_v4_addr.v4,
+				    sizeof(struct in_addr));
+			else
+				memcpy(&upa->mpattr[12],
+				    &a->nexthop->exit_nexthop.v4,
+				    sizeof(struct in_addr));
+		} else if (peer->conf.distance == 1) {
+			/* ebgp directly connected */
+			if (a->nexthop != NULL &&
+			    a->nexthop->flags & NEXTHOP_CONNECTED)
+				if (prefix_compare(&peer->remote_addr,
+				    &a->nexthop->nexthop_net,
+				    a->nexthop->nexthop_netlen) == 0) {
+					/*
+					 * nexthop and peer are in the same
+					 * subnet
+					 */
+					memcpy(&upa->mpattr[12],
+					    &a->nexthop->exit_nexthop.v4,
+					    sizeof(struct in_addr));
+					return (0);
+				}
+			memcpy(&upa->mpattr[12], &peer->local_v4_addr.v4,
+			    sizeof(struct in_addr));
+		} else
+			/* ebgp multihop */
+			memcpy(&upa->mpattr[12], &peer->local_v4_addr.v4,
+			    sizeof(struct in_addr));
+		return (0);
 	default:
 		break;
 	}
@@ -846,6 +898,7 @@ up_dump_prefix(u_char *buf, int len, struct uplist_prefix *prefix_head,
 {
 	struct update_prefix	*upp;
 	int			 r, wpos = 0;
+	u_int8_t		 i;
 
 	while ((upp = TAILQ_FIRST(prefix_head)) != NULL) {
 		if ((r = prefix_write(buf + wpos, len - wpos,
@@ -856,13 +909,14 @@ up_dump_prefix(u_char *buf, int len, struct uplist_prefix *prefix_head,
 			log_warnx("dequeuing update failed.");
 		TAILQ_REMOVE(upp->prefix_h, upp, prefix_l);
 		peer->up_pcnt--;
-		if (upp->prefix_h == &peer->withdraws ||
-		    upp->prefix_h == &peer->withdraws6) {
-			peer->up_wcnt--;
-			peer->prefix_sent_withdraw++;
-		} else {
-			peer->up_nlricnt--;
-			peer->prefix_sent_update++;
+		for (i = 0; i < AID_MAX; i++) {
+			if (upp->prefix_h == &peer->withdraws[i]) {
+				peer->up_wcnt--;
+				peer->prefix_sent_withdraw++;
+			} else {
+				peer->up_nlricnt--;
+				peer->prefix_sent_update++;
+			}
 		}
 		free(upp);
 	}
@@ -880,13 +934,13 @@ up_dump_attrnlri(u_char *buf, int len, struct rde_peer *peer)
 	 * It is possible that a queued path attribute has no nlri prefix.
 	 * Ignore and remove those path attributes.
 	 */
-	while ((upa = TAILQ_FIRST(&peer->updates)) != NULL)
+	while ((upa = TAILQ_FIRST(&peer->updates[AID_INET])) != NULL)
 		if (TAILQ_EMPTY(&upa->prefix_h)) {
 			attr_len = upa->attr_len;
 			if (RB_REMOVE(uptree_attr, &peer->up_attrs,
 			    upa) == NULL)
 				log_warnx("dequeuing update failed.");
-			TAILQ_REMOVE(&peer->updates, upa, attr_l);
+			TAILQ_REMOVE(&peer->updates[AID_INET], upa, attr_l);
 			free(upa->attr);
 			free(upa->mpattr);
 			free(upa);
@@ -925,7 +979,7 @@ up_dump_attrnlri(u_char *buf, int len, struct rde_peer *peer)
 	if (TAILQ_EMPTY(&upa->prefix_h)) {
 		if (RB_REMOVE(uptree_attr, &peer->up_attrs, upa) == NULL)
 			log_warnx("dequeuing update failed.");
-		TAILQ_REMOVE(&peer->updates, upa, attr_l);
+		TAILQ_REMOVE(&peer->updates[AID_INET], upa, attr_l);
 		free(upa->attr);
 		free(upa->mpattr);
 		free(upa);
@@ -936,12 +990,13 @@ up_dump_attrnlri(u_char *buf, int len, struct rde_peer *peer)
 }
 
 u_char *
-up_dump_mp_unreach(u_char *buf, u_int16_t *len, struct rde_peer *peer)
+up_dump_mp_unreach(u_char *buf, u_int16_t *len, struct rde_peer *peer,
+    u_int8_t aid)
 {
 	int		wpos;
 	u_int16_t	datalen, tmp;
 	u_int16_t	attrlen = 2;	/* attribute header (without len) */
-	u_int8_t	flags = ATTR_OPTIONAL;
+	u_int8_t	flags = ATTR_OPTIONAL, safi;
 
 	/*
 	 * reserve space for withdraw len, attr len, the attribute header
@@ -953,7 +1008,7 @@ up_dump_mp_unreach(u_char *buf, u_int16_t *len, struct rde_peer *peer)
 		return (NULL);
 
 	datalen = up_dump_prefix(buf + wpos, *len - wpos,
-	    &peer->withdraws6, peer);
+	    &peer->withdraws[aid], peer);
 	if (datalen == 0)
 		return (NULL);
 
@@ -961,9 +1016,11 @@ up_dump_mp_unreach(u_char *buf, u_int16_t *len, struct rde_peer *peer)
 
 	/* prepend header, need to do it reverse */
 	/* safi & afi */
-	buf[--wpos] = SAFI_UNICAST;
+	if (aid2afi(aid, &tmp, &safi))
+		fatalx("up_dump_mp_unreach: bad AID");
+	buf[--wpos] = safi;
 	wpos -= sizeof(u_int16_t);
-	tmp = htons(AFI_IPv6);
+	tmp = htons(tmp);
 	memcpy(buf + wpos, &tmp, sizeof(u_int16_t));
 
 	/* attribute length */
@@ -1001,7 +1058,8 @@ up_dump_mp_unreach(u_char *buf, u_int16_t *len, struct rde_peer *peer)
 }
 
 int
-up_dump_mp_reach(u_char *buf, u_int16_t *len, struct rde_peer *peer)
+up_dump_mp_reach(u_char *buf, u_int16_t *len, struct rde_peer *peer,
+    u_int8_t aid)
 {
 	struct update_attr	*upa;
 	int			wpos;
@@ -1012,13 +1070,13 @@ up_dump_mp_reach(u_char *buf, u_int16_t *len, struct rde_peer *peer)
 	 * It is possible that a queued path attribute has no nlri prefix.
 	 * Ignore and remove those path attributes.
 	 */
-	while ((upa = TAILQ_FIRST(&peer->updates6)) != NULL)
+	while ((upa = TAILQ_FIRST(&peer->updates[aid])) != NULL)
 		if (TAILQ_EMPTY(&upa->prefix_h)) {
 			attr_len = upa->attr_len;
 			if (RB_REMOVE(uptree_attr, &peer->up_attrs,
 			    upa) == NULL)
 				log_warnx("dequeuing update failed.");
-			TAILQ_REMOVE(&peer->updates6, upa, attr_l);
+			TAILQ_REMOVE(&peer->updates[aid], upa, attr_l);
 			free(upa->attr);
 			free(upa->mpattr);
 			free(upa);
@@ -1084,7 +1142,7 @@ up_dump_mp_reach(u_char *buf, u_int16_t *len, struct rde_peer *peer)
 	if (TAILQ_EMPTY(&upa->prefix_h)) {
 		if (RB_REMOVE(uptree_attr, &peer->up_attrs, upa) == NULL)
 			log_warnx("dequeuing update failed.");
-		TAILQ_REMOVE(&peer->updates6, upa, attr_l);
+		TAILQ_REMOVE(&peer->updates[aid], upa, attr_l);
 		free(upa->attr);
 		free(upa->mpattr);
 		free(upa);
diff --git a/usr.sbin/bgpd/util.c b/usr.sbin/bgpd/util.c
index 507ab7f94f9..aa217e1ef42 100644
--- a/usr.sbin/bgpd/util.c
+++ b/usr.sbin/bgpd/util.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: util.c,v 1.9 2009/12/16 15:40:55 claudio Exp $ */
+/*	$OpenBSD: util.c,v 1.10 2010/01/13 06:02:37 claudio Exp $ */
 
 /*
  * Copyright (c) 2006 Claudio Jeker <claudio@openbsd.org>
@@ -33,10 +33,20 @@ log_addr(const struct bgpd_addr *addr)
 {
 	static char	buf[48];
 
-	if (inet_ntop(aid2af(addr->aid), &addr->ba, buf, sizeof(buf)) == NULL)
-		return ("?");
-	else
+	switch (addr->aid) {
+	case AID_INET:
+	case AID_INET6:
+		if (inet_ntop(aid2af(addr->aid), &addr->ba, buf,
+		    sizeof(buf)) == NULL)
+			return ("?");
+		return (buf);
+	case AID_VPN_IPv4:
+		if (inet_ntop(AF_INET, &addr->vpn4.addr, buf,
+		    sizeof(buf)) == NULL)
+			return ("?");
 		return (buf);
+	}
+	return ("???");
 }
 
 const char *