Make the RDE IPv6 ready missing is the message handling. The internal

prefix tree changed form a hash table to a per AF RB tree.
OK henning@ some ideas are from Brent Graveland.

8 files changed, 347 insertions, 160 deletions

diff --git a/usr.sbin/bgpd/bgpd.h b/usr.sbin/bgpd/bgpd.h
index 2f8c42f4be6..96edba5445e 100644
--- a/usr.sbin/bgpd/bgpd.h
+++ b/usr.sbin/bgpd/bgpd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bgpd.h,v 1.129 2004/06/22 07:22:31 henning Exp $ */
+/*	$OpenBSD: bgpd.h,v 1.130 2004/06/22 20:28:58 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -593,16 +593,21 @@ void	 imsg_free(struct imsg *);
 int	 imsg_get_fd(struct imsgbuf *);
 
 /* kroute.c */
-int	kr_init(int);
-int	kr_change(struct kroute *);
-int	kr_delete(struct kroute *);
-void	kr_shutdown(void);
-void	kr_fib_couple(void);
-void	kr_fib_decouple(void);
-int	kr_dispatch_msg(void);
-int	kr_nexthop_add(struct bgpd_addr *);
-void	kr_nexthop_delete(struct bgpd_addr *);
-void	kr_show_route(struct imsg *);
+int		kr_init(int);
+int		kr_change(struct kroute *);
+int		kr_delete(struct kroute *);
+void		kr_shutdown(void);
+void		kr_fib_couple(void);
+void		kr_fib_decouple(void);
+int		kr_dispatch_msg(void);
+int		kr_nexthop_add(struct bgpd_addr *);
+void		kr_nexthop_delete(struct bgpd_addr *);
+void		kr_show_route(struct imsg *);
+in_addr_t	prefixlen2mask(u_int8_t);
+int		prefix_equal(const struct bgpd_addr *, const struct bgpd_addr *,
+		    int);
+void		inet6applymask(struct in6_addr *, const struct in6_addr *, int);
+
 
 /* control.c */
 int	control_init(void);
diff --git a/usr.sbin/bgpd/kroute.c b/usr.sbin/bgpd/kroute.c
index d2440c8ee44..07a152c78ac 100644
--- a/usr.sbin/bgpd/kroute.c
+++ b/usr.sbin/bgpd/kroute.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: kroute.c,v 1.97 2004/06/22 07:22:31 henning Exp $ */
+/*	$OpenBSD: kroute.c,v 1.98 2004/06/22 20:28:58 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -98,7 +98,6 @@ void			 kroute_detach_nexthop(struct knexthop_node *);
 int		protect_lo(void);
 u_int8_t	prefixlen_classful(in_addr_t);
 u_int8_t	mask2prefixlen(in_addr_t);
-in_addr_t	prefixlen2mask(u_int8_t);
 void		get_rtaddrs(int, struct sockaddr *, struct sockaddr **);
 void		if_change(u_short, int, struct if_data *);
 void		if_announce(void *);
@@ -817,6 +816,60 @@ prefixlen2mask(u_int8_t prefixlen)
 	return (0xffffffff << (32 - prefixlen));
 }
 
+int
+prefix_equal(const struct bgpd_addr *a, const struct bgpd_addr *b,
+    int prefixlen)
+{
+	in_addr_t	mask;
+	int		i;
+	u_int8_t	m;
+	
+	if (a->af != b->af)
+		return 0;
+	switch (a->af) {
+	case AF_INET:
+		if (prefixlen > 32)
+			fatalx("prefix_cmp: bad IPv4 prefixlen");
+		mask = htonl(prefixlen2mask(prefixlen));
+		if ((a->v4.s_addr & mask) == (b->v4.s_addr & mask))
+			return (1);
+		else
+			return (0);
+	case AF_INET6:
+		for (i = 0; i < prefixlen / 8; i++)
+			if (a->v6.s6_addr[i] != b->v6.s6_addr[i])
+				return (0);
+		i = prefixlen % 8;
+		if (i) {
+			m = 0xff00 >> i;
+			if ((a->v6.s6_addr[prefixlen / 8] & m) != 
+			    (b->v6.s6_addr[prefixlen / 8] & m))
+				return (0);
+		}
+		return (1);
+	default:
+		fatalx("prefix_cmp: unknown af");
+	}
+	return (0);
+}
+
+void
+inet6applymask(struct in6_addr *dest, const struct in6_addr *src, int prefixlen)
+{
+	struct in6_addr	mask;
+	int		i;
+
+	bzero(&mask, sizeof(mask));
+	for (i = 0; i < prefixlen / 8; i++)
+		mask.s6_addr[i] = 0xff;
+	i = prefixlen % 8;
+	if (i)
+		mask.s6_addr[prefixlen / 8] = 0xff00 >> i;
+
+	for (i = 0; i < 16; i++)
+		dest->s6_addr[i] = src->s6_addr[i] & mask.s6_addr[i];
+}
+
 #define	ROUNDUP(a, size)	\
     (((a) & ((size) - 1)) ? (1 + ((a) | ((size) - 1))) : (a))
 
diff --git a/usr.sbin/bgpd/mrt.c b/usr.sbin/bgpd/mrt.c
index 484b7910b32..121800b6eef 100644
--- a/usr.sbin/bgpd/mrt.c
+++ b/usr.sbin/bgpd/mrt.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: mrt.c,v 1.31 2004/06/20 18:35:12 henning Exp $ */
+/*	$OpenBSD: mrt.c,v 1.32 2004/06/22 20:28:58 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org>
@@ -237,10 +237,12 @@ mrt_dump_entry(struct mrt_config *mrt, struct prefix *p, u_int16_t snum,
 {
 	struct buf	*buf;
 	void		*bptr;
+	struct bgpd_addr addr;
 	u_int16_t	 len, attr_len;
 
 	attr_len = mrt_attr_length(&p->aspath->flags);
 	len = MRT_DUMP_HEADER_SIZE + attr_len;
+	pt_getaddr(p->prefix, &addr);
 
 	if ((buf = imsg_create(mrt->ibuf, IMSG_MRT_MSG, mrt->id,
 	    len + MRT_HEADER_SIZE)) == NULL) {
@@ -255,7 +257,7 @@ mrt_dump_entry(struct mrt_config *mrt, struct prefix *p, u_int16_t snum,
 
 	DUMP_SHORT(buf, 0);
 	DUMP_SHORT(buf, snum);
-	DUMP_NLONG(buf, p->prefix->prefix.v4.s_addr);
+	DUMP_NLONG(buf, addr.v4.s_addr);
 	DUMP_BYTE(buf, p->prefix->prefixlen);
 	DUMP_BYTE(buf, 1);		/* state */
 	DUMP_LONG(buf, p->lastchange);	/* originated */
diff --git a/usr.sbin/bgpd/rde.c b/usr.sbin/bgpd/rde.c
index d0f366df4ed..24d229c0403 100644
--- a/usr.sbin/bgpd/rde.c
+++ b/usr.sbin/bgpd/rde.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.c,v 1.117 2004/06/20 18:35:12 henning Exp $ */
+/*	$OpenBSD: rde.c,v 1.118 2004/06/22 20:28:58 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -290,7 +290,7 @@ rde_dispatch_imsg_session(struct imsgbuf *ibuf)
 				break;
 			}
 			pid = imsg.hdr.pid;
-			pt_dump(network_dump_upcall, &pid);
+			pt_dump(network_dump_upcall, &pid, AF_UNSPEC);
 			imsg_compose_pid(&ibuf_se, IMSG_CTL_END, pid, NULL, 0);
 			break;
 		case IMSG_CTL_SHOW_RIB:
@@ -299,7 +299,7 @@ rde_dispatch_imsg_session(struct imsgbuf *ibuf)
 				break;
 			}
 			pid = imsg.hdr.pid;
-			pt_dump(rde_dump_upcall, &pid);
+			pt_dump(rde_dump_upcall, &pid, AF_UNSPEC);
 			imsg_compose_pid(&ibuf_se, IMSG_CTL_END, pid, NULL, 0);
 			break;
 		case IMSG_CTL_SHOW_RIB_AS:
@@ -404,7 +404,7 @@ rde_dispatch_imsg_parent(struct imsgbuf *ibuf)
 			mrt.ibuf = &ibuf_main;
 			if (mrt.type == MRT_TABLE_DUMP) {
 				mrt_clear_seq();
-				pt_dump(mrt_dump_upcall, &mrt);
+				pt_dump(mrt_dump_upcall, &mrt, AF_UNSPEC);
 				if (imsg_compose(&ibuf_main, IMSG_MRT_END,
 				    mrt.id, NULL, 0) == -1)
 					fatalx("imsg_compose error");
@@ -741,7 +741,7 @@ rde_dump_rib_as(struct prefix *p, pid_t pid)
 	rib.active_cnt = p->aspath->active_cnt;
 	memcpy(&rib.nexthop, &p->aspath->nexthop->true_nexthop,
 	    sizeof(rib.nexthop));
-	memcpy(&rib.prefix, &p->prefix->prefix, sizeof(rib.prefix));
+	pt_getaddr(p->prefix, &rib.prefix);
 	rib.prefixlen = p->prefix->prefixlen;
 	rib.origin = p->aspath->flags.origin;
 	rib.flags = 0;
@@ -772,7 +772,7 @@ rde_dump_rib_prefix(struct prefix *p, pid_t pid)
 	struct ctl_show_rib_prefix	 prefix;
 
 	prefix.lastchange = p->lastchange;
-	memcpy(&prefix.prefix, &p->prefix->prefix, sizeof(prefix.prefix));
+	pt_getaddr(p->prefix, &prefix.prefix);
 	prefix.prefixlen = p->prefix->prefixlen;
 	prefix.flags = 0;
 	if (p->aspath->nexthop->state == NEXTHOP_REACH)
@@ -829,14 +829,16 @@ rde_dump_prefix_upcall(struct pt_entry *pt, void *ptr)
 	struct {
 		pid_t				 pid;
 		struct ctl_show_rib_prefix	*pref;
-	}		*ctl = ptr;
-	struct prefix	*p;
-	in_addr_t	 mask;
+	}			*ctl = ptr;
+	struct prefix		*p;
+	struct bgpd_addr	 addr;
 
-	mask = htonl(0xffffffff << (32 - ctl->pref->prefixlen));
-	if (ctl->pref->prefixlen <= pt->prefixlen &&
-	    (ctl->pref->prefix.v4.s_addr & mask) ==
-	    (pt->prefix.v4.s_addr & mask))
+	pt_getaddr(pt, &addr);
+	if (addr.af != ctl->pref->prefix.af)
+		return;
+	if (ctl->pref->prefixlen > pt->prefixlen)
+		return;
+	if (prefix_equal(&ctl->pref->prefix, &addr, ctl->pref->prefixlen))
 		LIST_FOREACH(p, &pt->prefix_h, prefix_l)
 			rde_dump_rib_as(p, ctl->pid);
 }
@@ -856,7 +858,7 @@ rde_dump_prefix(struct ctl_show_rib_prefix *pref, pid_t pid)
 	} else if (pref->flags & F_LONGER) {
 		ctl.pid = pid;
 		ctl.pref = pref;
-		pt_dump(rde_dump_prefix_upcall, &ctl);
+		pt_dump(rde_dump_prefix_upcall, &ctl, AF_UNSPEC);
 	} else {
 		if ((pt = pt_get(&pref->prefix, pref->prefixlen)) != NULL)
 			rde_dump_upcall(pt, &pid);
@@ -869,7 +871,8 @@ rde_dump_prefix(struct ctl_show_rib_prefix *pref, pid_t pid)
 void
 rde_send_kroute(struct prefix *new, struct prefix *old)
 {
-	struct kroute	 kr;
+	struct kroute		kr;
+	struct bgpd_addr	addr;
 	struct prefix	*p;
 	enum imsg_type	 type;
 
@@ -897,7 +900,8 @@ rde_send_kroute(struct prefix *new, struct prefix *old)
 		kr.nexthop.s_addr = p->aspath->nexthop->true_nexthop.v4.s_addr;
 	}
 
-	kr.prefix.s_addr = p->prefix->prefix.v4.s_addr;
+	pt_getaddr(p->prefix, &addr);
+	kr.prefix.s_addr = addr.v4.s_addr;
 	kr.prefixlen = p->prefix->prefixlen;
 
 	if (imsg_compose(&ibuf_main, type, 0, &kr, sizeof(kr)) == -1)
@@ -1207,7 +1211,7 @@ peer_dump(u_int32_t id, u_int16_t afi, u_int8_t safi)
 	if (afi == AFI_ALL || afi == AFI_IPv4)
 		if (safi == SAFI_ALL || safi == SAFI_UNICAST ||
 		    safi == SAFI_BOTH) {
-			pt_dump(up_dump_upcall, peer);
+			pt_dump(up_dump_upcall, peer, AF_INET);
 			return;
 		}
 
@@ -1280,6 +1284,7 @@ network_dump_upcall(struct pt_entry *pt, void *ptr)
 {
 	struct prefix		*p;
 	struct kroute		 k;
+	struct bgpd_addr	 addr;
 	pid_t			 pid;
 
 	memcpy(&pid, ptr, sizeof(pid));
@@ -1287,8 +1292,8 @@ network_dump_upcall(struct pt_entry *pt, void *ptr)
 	LIST_FOREACH(p, &pt->prefix_h, prefix_l)
 	    if (p->aspath->nexthop->flags & NEXTHOP_ANNOUNCE) {
 		    bzero(&k, sizeof(k));
-		    memcpy(&k.prefix, &p->prefix->prefix.v4.s_addr,
-			sizeof(k.prefix));
+		    pt_getaddr(p->prefix, &addr);
+		    k.prefix = addr.v4;
 		    k.prefixlen = p->prefix->prefixlen;
 		    if (p->peer == &peerself)
 			    k.flags = F_KERNEL;
diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h
index 319655debae..e82c3b548de 100644
--- a/usr.sbin/bgpd/rde.h
+++ b/usr.sbin/bgpd/rde.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.h,v 1.41 2004/06/20 18:35:12 henning Exp $ */
+/*	$OpenBSD: rde.h,v 1.42 2004/06/22 20:28:58 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org> and
@@ -179,13 +179,22 @@ struct rde_aspath {
 	struct attr_flags		 flags;
 };
 
+/* generic entry without address specific part */
 struct pt_entry {
-	LIST_ENTRY(pt_entry)		 pt_l;	/* currently we are using a
-						   hash list for prefixes */
-	struct bgpd_addr		 prefix;
+	RB_ENTRY(pt_entry)		 pt_e;
+	sa_family_t			 af;
 	u_int8_t			 prefixlen;
 	struct prefix_head		 prefix_h;
 	struct prefix			*active; /* for fast access */
+};
+
+struct pt_entry4 {
+	RB_ENTRY(pt_entry)		 pt_e;
+	sa_family_t			 af;
+	u_int8_t			 prefixlen;
+	struct prefix_head		 prefix_h;
+	struct prefix			*active; /* for fast access */
+	struct in_addr			 prefix4;
 	/*
 	 * Route Flap Damping structures
 	 * Currently I think they belong into the prefix but for the moment
@@ -193,6 +202,15 @@ struct pt_entry {
 	 */
 };
 
+struct pt_entry6 {
+	RB_ENTRY(pt_entry)		 pt_e;
+	sa_family_t			 af;
+	u_int8_t			 prefixlen;
+	struct prefix_head		 prefix_h;
+	struct prefix			*active; /* for fast access */
+	struct in6_addr			 prefix6;
+};
+
 struct prefix {
 	LIST_ENTRY(prefix)		 prefix_l, path_l;
 	struct rde_aspath		*aspath;
@@ -297,11 +315,13 @@ void		 up_dump_upcall(struct pt_entry *, void *);
 void		 pt_init(void);
 void		 pt_shutdown(void);
 int		 pt_empty(struct pt_entry *);
+void		 pt_getaddr(struct pt_entry *, struct bgpd_addr *);
 struct pt_entry	*pt_get(struct bgpd_addr *, int);
 struct pt_entry *pt_add(struct bgpd_addr *, int);
 void		 pt_remove(struct pt_entry *);
 struct pt_entry	*pt_lookup(struct bgpd_addr *);
-void		 pt_dump(void (*)(struct pt_entry *, void *), void *);
+void		 pt_dump(void (*)(struct pt_entry *, void *), void *,
+		     sa_family_t);
 
 /* rde_filter.c */
 enum filter_actions rde_filter(struct rde_peer *, struct attr_flags *,
diff --git a/usr.sbin/bgpd/rde_prefix.c b/usr.sbin/bgpd/rde_prefix.c
index 7a47fc756c6..d58245a7cc0 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.13 2004/03/11 17:34:01 henning Exp $ */
+/*	$OpenBSD: rde_prefix.c,v 1.14 2004/06/22 20:28:58 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org>
@@ -43,40 +43,20 @@
  */
 
 /* internal prototypes */
-static struct pt_entry	*pt_alloc(void);
+static struct pt_entry4	*pt_alloc4(void);
+static struct pt_entry6	*pt_alloc6(void);
 static void		 pt_free(struct pt_entry *);
 
-/*
- * currently we are using a hash list to store the prefixes. This may be
- * replaced with a red-black trie if necessary.
- */
-LIST_HEAD(pt_entryhead, pt_entry);
-
-struct pt_table {
-	struct pt_entryhead	*pt_hashtbl;
-	u_int32_t		 pt_hashmask;
-};
+int	pt_prefix_cmp(const struct pt_entry *, const struct pt_entry *);
 
 #define MIN_PREFIX 0
 #define MAX_PREFIX 32
+RB_HEAD(pt_tree, pt_entry);
+RB_PROTOTYPE(pt_tree, pt_entry, pt_e, pt_prefix_cmp);
+RB_GENERATE(pt_tree, pt_entry, pt_e, pt_prefix_cmp);
 
-/*
- * size of the hashtable per prefixlen. The sizes were chosen from a bgp
- * dump done on Nov 4. 2003.
- */
-u_int32_t pthashsize[MAX_PREFIX + 1 - MIN_PREFIX] = {
-	/* need to be power of 2 */
-	1, 1, 1, 1, 1, 1, 1, 1,
-	16, 8, 8, 16, 32, 64, 256, 256,
-	4096, 1024, 2048, 8192, 8192, 4096, 8192, 8192,
-	32768, 1, 1, 1, 1, 1, 1, 1, 1
-};
-
-struct pt_table	pttable[MAX_PREFIX + 1 - MIN_PREFIX];
-
-#define PT_HASH(p, plen)				\
-	&pttable[plen].pt_hashtbl[((p >> plen) ^ (p >> (plen + 5))) & \
-	    pttable[plen].pt_hashmask]
+struct pt_tree	pttable4;
+struct pt_tree	pttable6;
 
 /*
  * Statistics collector.
@@ -87,48 +67,29 @@ struct pt_table	pttable[MAX_PREFIX + 1 - MIN_PREFIX];
 struct pt_stats {
 	u_int64_t		 pt_alloc;
 	u_int64_t		 pt_free;
-	u_int64_t		 pt_add[MAX_PREFIX + 1 - MIN_PREFIX];
-	u_int64_t		 pt_get[MAX_PREFIX + 1 - MIN_PREFIX];
-	u_int64_t		 pt_remove[MAX_PREFIX + 1 - MIN_PREFIX];
+	u_int64_t		 pt_add;
+	u_int64_t		 pt_get;
+	u_int64_t		 pt_remove;
 	u_int64_t		 pt_lookup;
 	u_int64_t		 pt_dump;
 } ptstats;
 /* simple macros to update statistics */
 #define PT_STAT(x)	(ptstats.x++)
-#define PT_STAT2(x, p)	(ptstats.x[p]++)
 
 void
 pt_init(void)
 {
-	int		i;
-	u_int32_t	j;
-
-	for (i = MIN_PREFIX; i <= MAX_PREFIX; i++) {
-		pttable[i].pt_hashtbl = calloc(pthashsize[i],
-		    sizeof(struct pt_entryhead));
-		if (pttable[i].pt_hashtbl == NULL)
-			fatal("pt_init");
-
-		for (j = 0; j < pthashsize[i]; j++)
-			LIST_INIT(&pttable[i].pt_hashtbl[j]);
-
-		pttable[i].pt_hashmask = pthashsize[i] - 1;
-	}
+	RB_INIT(&pttable4);
+	RB_INIT(&pttable6);
 }
 
 void
 pt_shutdown(void)
 {
-	int		i;
-	u_int32_t	j;
-
-	for (i = MIN_PREFIX; i <= MAX_PREFIX; i++) {
-		for (j = 0; j < pthashsize[i]; j++)
-			if (!LIST_EMPTY(&pttable[i].pt_hashtbl[j]))
-				log_warnx("pt_free: free non-free table "
-				    "[%d][%d]", i, j);
-		free(pttable[i].pt_hashtbl);
-	}
+	if (!RB_EMPTY(&pttable4))
+		log_debug("pt_shutdown: IPv4 tree is not empty.");
+	if (!RB_EMPTY(&pttable6))
+		log_debug("pt_shutdown: IPv6 tree is not empty.");
 }
 
 int
@@ -138,109 +99,242 @@ pt_empty(struct pt_entry *pte)
 	return LIST_EMPTY(&pte->prefix_h);
 }
 
+void
+pt_getaddr(struct pt_entry *pte, struct bgpd_addr *addr)
+{
+	bzero(addr, sizeof(struct bgpd_addr));
+	switch (pte->af) {
+	case AF_INET:
+		addr->af = pte->af;
+		addr->v4 = ((struct pt_entry4 *)pte)->prefix4;
+		break;
+	case AF_INET6:
+		addr->af = pte->af;
+		memcpy(&addr->v6, &((struct pt_entry6 *)pte)->prefix6,
+		    sizeof(addr->v6));
+		/* XXX scope_id ??? */
+		break;
+	default:
+		fatalx("pt_getaddr: unknown af");
+	}
+}
+
 struct pt_entry *
 pt_get(struct bgpd_addr *prefix, int prefixlen)
 {
-	struct pt_entryhead	*head;
-	struct pt_entry		*p;
-	u_int32_t		 p_hbo;
-
-	ENSURE(MIN_PREFIX <= prefixlen && prefixlen <= MAX_PREFIX);
-	PT_STAT2(pt_get, prefixlen);
-
-	p_hbo = ntohl(prefix->v4.s_addr);
-	head = PT_HASH(p_hbo, prefixlen);
-	ENSURE(head != NULL);
-
-	LIST_FOREACH(p, head, pt_l) {
-		if (prefix->v4.s_addr == p->prefix.v4.s_addr)
-			return p;
+	struct pt_entry4	pte4;
+	struct pt_entry6	pte6;
+	in_addr_t		addr_hbo;
+
+	PT_STAT(pt_get);
+
+	switch (prefix->af) {
+	case AF_INET:
+		if (prefixlen > 32)
+			fatalx("pt_get: bad IPv4 prefixlen");
+		pte4.af = AF_INET;
+		addr_hbo = ntohl(prefix->v4.s_addr);
+		pte4.prefix4.s_addr = htonl(addr_hbo & 
+		    prefixlen2mask(prefixlen));
+		pte4.prefixlen = prefixlen;
+		return RB_FIND(pt_tree, &pttable4, (struct pt_entry *)&pte4);
+	case AF_INET6:
+		if (prefixlen > 128)
+			fatalx("pt_get: bad IPv6 prefixlen");
+		pte6.af = AF_INET6;
+		pte6.prefixlen = prefixlen;
+		inet6applymask(&pte6.prefix6, &prefix->v6, prefixlen);
+		return RB_FIND(pt_tree, &pttable6, (struct pt_entry *)&pte6);
+	default:
+		log_warnx("pt_get: unknown af");
 	}
-	return NULL;
+	return (NULL);
 }
 
 struct pt_entry *
 pt_add(struct bgpd_addr *prefix, int prefixlen)
 {
-	struct pt_entryhead	*head;
-	struct pt_entry		*p;
-	u_int32_t		 p_hbo;
+	struct pt_tree		*tree = NULL;
+	struct pt_entry		*p = NULL;
+	struct pt_entry4	*p4;
+	struct pt_entry6	*p6;
+	in_addr_t		 addr_hbo;
 
-	ENSURE(MIN_PREFIX <= prefixlen && prefixlen <= MAX_PREFIX);
 	ENSURE(pt_get(prefix, prefixlen) == NULL);
-	PT_STAT2(pt_add, prefixlen);
-
-	p_hbo = ntohl(prefix->v4.s_addr);
-	head = PT_HASH(p_hbo, prefixlen);
-	ENSURE(head != NULL);
-
-	p = pt_alloc();
-	memcpy(&p->prefix, prefix, sizeof(p->prefix));
-	p->prefixlen = prefixlen;
+	PT_STAT(pt_add);
+
+	switch (prefix->af) {
+	case AF_INET:
+		p4 = pt_alloc4();
+		if (prefixlen > 32)
+			fatalx("pt_add: bad IPv4 prefixlen");
+		p4->af = AF_INET;
+		p4->prefixlen = prefixlen;
+		addr_hbo = ntohl(prefix->v4.s_addr);
+		p4->prefix4.s_addr = htonl(addr_hbo & 
+		    prefixlen2mask(prefixlen));
+		p = (struct pt_entry *)p4;
+		tree = &pttable4;
+		break;
+	case AF_INET6:
+		p6 = pt_alloc6();
+		if (prefixlen > 128)
+			fatalx("pt_add: bad IPv6 prefixlen");
+		p6->af = AF_INET6;
+		p6->prefixlen = prefixlen;
+		inet6applymask(&p6->prefix6, &prefix->v6, prefixlen);
+		p = (struct pt_entry *)p6;
+		tree = &pttable6;
+		break;
+	default:
+		fatalx("pt_add: unknown af");
+	}
 	LIST_INIT(&p->prefix_h);
 
-	LIST_INSERT_HEAD(head, p, pt_l);
+	if (RB_INSERT(pt_tree, &pttable4, p) != NULL) {
+		log_warnx("prefix_add: insert failed");
+		return (NULL);
+	}
 
-	return p;
+	return (p);
 }
 
 void
 pt_remove(struct pt_entry *pte)
 {
 	ENSURE(pt_empty(pte));
-	PT_STAT2(pt_remove, pte->prefixlen);
+	PT_STAT(pt_remove);
+
+	switch (pte->af) {
+	case AF_INET:
+		if (RB_REMOVE(pt_tree, &pttable4, pte) == NULL)
+			log_warnx("pt_remove: remove failed.");
+		break;
+	case AF_INET6:
+		if (RB_REMOVE(pt_tree, &pttable6, pte) == NULL)
+			log_warnx("pt_remove: remove failed.");
+		break;
+	default:
+		fatalx("pt_remove: unknown af");
+	}
 
-	LIST_REMOVE(pte, pt_l);
 	pt_free(pte);
 }
 
 struct pt_entry *
 pt_lookup(struct bgpd_addr *prefix)
 {
-	struct bgpd_addr pmasked;
 	struct pt_entry	*p;
-	u_int32_t	 addr_hbo;
 	int		 i;
 
 	PT_STAT(pt_lookup);
-	bzero(&pmasked, sizeof(pmasked));
-	pmasked.af = AF_INET;
-	addr_hbo = ntohl(prefix->v4.s_addr);
-	for (i = MAX_PREFIX; i >= MIN_PREFIX; i--) {
-		pmasked.v4.s_addr = htonl(addr_hbo & (0xffffffff << (32 - i)));
-		p = pt_get(&pmasked, i);
-		if (p != NULL)
-			return (p);
+	switch (prefix->af) {
+	case AF_INET:
+		for (i = 32; i >= 0; i--) {
+			p = pt_get(prefix, i);
+			if (p != NULL)
+				return (p);
+		}
+		break;
+	case AF_INET6:
+		for (i = 128; i >= 0; i--) {
+			p = pt_get(prefix, i);
+			if (p != NULL)
+				return (p);
+		}
+		break;
+	default:
+		fatalx("pt_lookup: unknown af");
 	}
 	return (NULL);
 }
 
 void
-pt_dump(void (*upcall)(struct pt_entry *, void *), void *arg)
+pt_dump(void (*upcall)(struct pt_entry *, void *), void *arg, sa_family_t af)
 {
-	struct pt_entry	*p;
-	int		 i;
-	u_int32_t	 j;
+	struct pt_entry *p;
+
+	if (af == AF_INET || af == AF_UNSPEC)
+		RB_FOREACH(p, pt_tree, &pttable4)
+		    upcall(p, arg);
+	if (af == AF_INET6 || af == AF_UNSPEC)
+		RB_FOREACH(p, pt_tree, &pttable6)
+		    upcall(p, arg);
+}
 
-	PT_STAT(pt_dump);
-	for (i = MAX_PREFIX; i >= MIN_PREFIX; i--) {
-		for (j = 0; j < pthashsize[i]; j++)
-			LIST_FOREACH(p, &pttable[i].pt_hashtbl[j], pt_l)
-				upcall(p, arg);
+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;
+
+	if (a == NULL)
+		return (1);
+	if (b == NULL)
+		return (-1);
+
+	if (a->af != b->af)
+		log_debug("af non equal a %d b %d\n", a->af, b->af);
+	ENSURE(a->af == b->af);
+
+	switch (a->af) {
+	case AF_INET:
+		a4 = (const struct pt_entry4 *)a;
+		b4 = (const struct pt_entry4 *)b;
+		if (ntohl(a4->prefix4.s_addr) > ntohl(b4->prefix4.s_addr))
+			return (1);
+		if (ntohl(a4->prefix4.s_addr) < ntohl(b4->prefix4.s_addr))
+			return (-1);
+		if (a4->prefixlen > b4->prefixlen)
+			return (1);
+		if (a4->prefixlen < b4->prefixlen)
+			return (-1);
+		return (0);
+	case AF_INET6:
+		a6 = (const struct pt_entry6 *)a;
+		b6 = (const struct pt_entry6 *)b;
+
+		i = memcmp(&a6->prefix6, &b6->prefix6, sizeof(struct in6_addr));
+		if (i > 0)
+			return (1);
+		if (i < 0)
+			return (-1);
+		if (a6->prefixlen < b6->prefixlen)
+			return (-1);
+		if (a6->prefixlen > b6->prefixlen)
+			return (1);
+		return (0);
+
+	default:
+		fatalx("pt_prefix_cmp: unknown af");
 	}
+	return (-1);
 }
 
 /* returns a zeroed pt_entry function may not return on fail */
-static struct pt_entry *
-pt_alloc(void)
+static struct pt_entry4 *
+pt_alloc4(void)
 {
-	struct pt_entry	*p;
+	struct pt_entry4	*p;
+
+	PT_STAT(pt_alloc);
+	p = calloc(1, sizeof(*p));
+	if (p == NULL)
+		fatal("pt_alloc");
+	return (p);
+}
+
+static struct pt_entry6 *
+pt_alloc6(void)
+{
+	struct pt_entry6	*p;
 
 	PT_STAT(pt_alloc);
 	p = calloc(1, sizeof(*p));
 	if (p == NULL)
 		fatal("pt_alloc");
-	return p;
+	return (p);
 }
 
 static void
diff --git a/usr.sbin/bgpd/rde_rib.c b/usr.sbin/bgpd/rde_rib.c
index b1793e85ee9..c93d0498631 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.47 2004/06/22 07:22:31 henning Exp $ */
+/*	$OpenBSD: rde_rib.c,v 1.48 2004/06/22 20:28:58 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org>
@@ -178,13 +178,15 @@ void
 path_remove(struct rde_aspath *asp)
 {
 	struct prefix	*p;
+	struct bgpd_addr addr;
 
 	RIB_STAT(path_remove);
 
 	while ((p = LIST_FIRST(&asp->prefix_h)) != NULL) {
 		/* Commit is done in peer_down() */
+		pt_getaddr(p->prefix, &addr);
 		rde_send_pftable(p->aspath->flags.pftable,
-		    &p->prefix->prefix, p->prefix->prefixlen, 1);
+		    &addr, p->prefix->prefixlen, 1);
 
 		prefix_destroy(p);
 	}
@@ -305,14 +307,17 @@ struct prefix *
 prefix_get(struct rde_aspath *asp, struct bgpd_addr *prefix, int prefixlen)
 {
 	struct prefix	*p;
+	struct bgpd_addr addr;
 
 	RIB_STAT(prefix_get);
 	ENSURE(asp != NULL);
 
 	LIST_FOREACH(p, &asp->prefix_h, path_l) {
 		ENSURE(p->prefix != NULL);
-		if (p->prefix->prefixlen == prefixlen &&
-		    p->prefix->prefix.v4.s_addr == prefix->v4.s_addr) {
+		if (p->prefix->prefixlen != prefixlen)
+			continue;
+		pt_getaddr(p->prefix, &addr);
+		if (prefix_equal(&addr, prefix, prefixlen)) {
 			ENSURE(p->aspath == asp);
 			return p;
 		}
diff --git a/usr.sbin/bgpd/rde_update.c b/usr.sbin/bgpd/rde_update.c
index 3d0db418b8d..88adabcc2b9 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.19 2004/06/20 18:35:12 henning Exp $ */
+/*	$OpenBSD: rde_update.c,v 1.20 2004/06/22 20:28:58 claudio Exp $ */
 
 /*
  * Copyright (c) 2004 Claudio Jeker <claudio@openbsd.org>
@@ -213,6 +213,7 @@ up_generate_updates(struct rde_peer *peer,
 	struct update_prefix		*p;
 	struct attr			*atr;
 	struct attr_flags		 attrs;
+	struct bgpd_addr		 addr;
 
 	ENSURE(peer->state == PEER_UP);
 	/*
@@ -302,7 +303,8 @@ up_generate_updates(struct rde_peer *peer,
 		/* copy attributes for output filter */
 		attr_copy(&attrs, &old->aspath->flags);
 
-		if (rde_filter(peer, &attrs, &old->prefix->prefix,
+		pt_getaddr(old->prefix, &addr);
+		if (rde_filter(peer, &attrs, &addr,
 		    old->prefix->prefixlen, DIR_OUT) == ACTION_DENY) {
 			attr_free(&attrs);
 			return;
@@ -314,7 +316,7 @@ up_generate_updates(struct rde_peer *peer,
 		if (p == NULL)
 			fatal("up_queue_update");
 
-		p->prefix = old->prefix->prefix;
+		p->prefix = addr;
 		p->prefixlen = old->prefix->prefixlen;
 		if (up_add(peer, p, NULL) == -1)
 			log_warnx("queuing withdraw failed.");
@@ -395,7 +397,8 @@ up_generate_updates(struct rde_peer *peer,
 		/* copy attributes for output filter */
 		attr_copy(&attrs, &new->aspath->flags);
 
-		if (rde_filter(peer, &attrs, &new->prefix->prefix,
+		pt_getaddr(new->prefix, &addr);
+		if (rde_filter(peer, &attrs, &addr,
 		    new->prefix->prefixlen, DIR_OUT) == ACTION_DENY) {
 			attr_free(&attrs);
 			up_generate_updates(peer, NULL, old);
@@ -439,7 +442,7 @@ up_generate_updates(struct rde_peer *peer,
 		 * but currently I don't care.
 		 */
 		a->attr_hash = aspath_hash(attrs.aspath);
-		p->prefix = new->prefix->prefix;
+		p->prefix = addr;
 		p->prefixlen = new->prefix->prefixlen;
 
 		/* no longer needed */