- Rework NPF tables and fix support for IPv6. Implement tree table type trunk
authorrmind <rmind@NetBSD.org>
Sun, 15 Jul 2012 00:22:58 +0000
branchtrunk
changeset 212018 a1568dbde87f
parent 212017 358c522f4e97
child 212019 f14aa6b2e88e
- Rework NPF tables and fix support for IPv6. Implement tree table type using radix / Patricia tree. Universal IPv4/IPv6 comparator for ptree(3) was contributed by Matt Thomas. - NPF tables: update regression tests, improve npfctl(8) error messages. - Fix few bugs when using kernel modules and handle module autounloader. - Few other fixes and misc cleanups. - Bump the version.
lib/libnpf/npf.c
lib/libnpf/npf.h
sys/net/npf/files.npf
sys/net/npf/npf.c
sys/net/npf/npf.h
sys/net/npf/npf_alg.c
sys/net/npf/npf_alg_icmp.c
sys/net/npf/npf_ctl.c
sys/net/npf/npf_handler.c
sys/net/npf/npf_impl.h
sys/net/npf/npf_inet.c
sys/net/npf/npf_instr.c
sys/net/npf/npf_nat.c
sys/net/npf/npf_ruleset.c
sys/net/npf/npf_sendpkt.c
sys/net/npf/npf_session.c
sys/net/npf/npf_state_tcp.c
sys/net/npf/npf_tableset.c
sys/net/npf/npf_tableset_ptree.c
sys/rump/dev/lib/libnpf/Makefile
usr.sbin/npf/npfctl/npf_build.c
usr.sbin/npf/npfctl/npf_data.c
usr.sbin/npf/npfctl/npf_disassemble.c
usr.sbin/npf/npfctl/npf_ncgen.c
usr.sbin/npf/npfctl/npf_parse.y
usr.sbin/npf/npfctl/npfctl.c
usr.sbin/npf/npfctl/npfctl.h
usr.sbin/npf/npftest/libnpftest/npf_table_test.c
--- a/lib/libnpf/npf.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/lib/libnpf/npf.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf.c,v 1.9 2012/07/01 23:21:07 rmind Exp $	*/
+/*	$NetBSD: npf.c,v 1.10 2012/07/15 00:22:59 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2010-2012 The NetBSD Foundation, Inc.
@@ -30,7 +30,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf.c,v 1.9 2012/07/01 23:21:07 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf.c,v 1.10 2012/07/15 00:22:59 rmind Exp $");
 
 #include <sys/types.h>
 #include <netinet/in_systm.h>
@@ -614,7 +614,8 @@
 }
 
 int
-npf_table_add_entry(nl_table_t *tl, npf_addr_t *addr, npf_netmask_t mask)
+npf_table_add_entry(nl_table_t *tl, const int alen,
+    const npf_addr_t *addr, const npf_netmask_t mask)
 {
 	prop_dictionary_t tldict = tl->ntl_dict, entdict;
 	prop_array_t tblents;
@@ -622,10 +623,10 @@
 
 	/* Create the table entry. */
 	entdict = prop_dictionary_create();
-	if (entdict) {
+	if (entdict == NULL) {
 		return ENOMEM;
 	}
-	addrdata = prop_data_create_data(addr, sizeof(npf_addr_t));
+	addrdata = prop_data_create_data(addr, alen);
 	prop_dictionary_set(entdict, "addr", addrdata);
 	prop_dictionary_set_uint8(entdict, "mask", mask);
 	prop_object_release(addrdata);
--- a/lib/libnpf/npf.h	Sun Jul 15 00:16:28 2012 +0000
+++ b/lib/libnpf/npf.h	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf.h,v 1.8 2012/07/01 23:21:07 rmind Exp $	*/
+/*	$NetBSD: npf.h,v 1.9 2012/07/15 00:22:59 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2011-2012 The NetBSD Foundation, Inc.
@@ -96,7 +96,8 @@
 int		npf_nat_insert(nl_config_t *, nl_nat_t *, pri_t);
 
 nl_table_t *	npf_table_create(u_int, int);
-int		npf_table_add_entry(nl_table_t *, npf_addr_t *, npf_netmask_t);
+int		npf_table_add_entry(nl_table_t *, const int,
+		    const npf_addr_t *, const npf_netmask_t);
 bool		npf_table_exists_p(nl_config_t *, u_int);
 int		npf_table_insert(nl_config_t *, nl_table_t *);
 void		npf_table_destroy(nl_table_t *);
--- a/sys/net/npf/files.npf	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/files.npf	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-# $NetBSD: files.npf,v 1.6 2012/02/06 23:30:14 rmind Exp $
+# $NetBSD: files.npf,v 1.7 2012/07/15 00:22:59 rmind Exp $
 #
 # Public Domain.
 #
@@ -19,6 +19,7 @@
 file	net/npf/npf_ruleset.c			npf
 file	net/npf/npf_rproc.c			npf
 file	net/npf/npf_tableset.c			npf
+file	net/npf/npf_tableset_ptree.c		npf
 file	net/npf/npf_inet.c			npf
 file	net/npf/npf_session.c			npf
 file	net/npf/npf_state.c			npf
--- a/sys/net/npf/npf.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf.c,v 1.11 2012/06/22 13:43:17 rmind Exp $	*/
+/*	$NetBSD: npf.c,v 1.12 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2009-2010 The NetBSD Foundation, Inc.
@@ -34,7 +34,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf.c,v 1.11 2012/06/22 13:43:17 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf.c,v 1.12 2012/07/15 00:23:00 rmind Exp $");
 
 #include <sys/param.h>
 #include <sys/types.h>
@@ -170,6 +170,11 @@
 		return npf_init();
 	case MODULE_CMD_FINI:
 		return npf_fini();
+	case MODULE_CMD_AUTOUNLOAD:
+		if (npf_pfil_registered_p() || !npf_default_pass()) {
+			return EBUSY;
+		}
+		break;
 	default:
 		return ENOTTY;
 	}
--- a/sys/net/npf/npf.h	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf.h	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf.h,v 1.18 2012/07/01 23:21:06 rmind Exp $	*/
+/*	$NetBSD: npf.h,v 1.19 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2009-2012 The NetBSD Foundation, Inc.
@@ -45,7 +45,7 @@
 #include <netinet/in_systm.h>
 #include <netinet/in.h>
 
-#define	NPF_VERSION		4
+#define	NPF_VERSION		5
 
 /*
  * Public declarations and definitions.
@@ -94,7 +94,7 @@
 	npf_addr_t *		npc_srcip;
 	npf_addr_t *		npc_dstip;
 	/* Size (v4 or v6) of IP addresses. */
-	int			npc_ipsz;
+	int			npc_alen;
 	u_int			npc_hlen;
 	int			npc_next_proto;
 	/* IPv4, IPv6. */
@@ -188,6 +188,7 @@
 typedef struct npf_ioctl_table {
 	int			nct_action;
 	u_int			nct_tid;
+	int			nct_alen;
 	npf_addr_t		nct_addr;
 	npf_netmask_t		nct_mask;
 } npf_ioctl_table_t;
@@ -216,6 +217,10 @@
 	/* Rule procedure cases. */
 	NPF_STAT_RPROC_LOG,
 	NPF_STAT_RPROC_NORM,
+	/* Fragments. */
+	NPF_STAT_FRAGMENTS,
+	NPF_STAT_REASSEMBLY,
+	NPF_STAT_REASSFAIL,
 	/* Other errors. */
 	NPF_STAT_ERROR,
 	/* Count (last). */
--- a/sys/net/npf/npf_alg.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf_alg.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_alg.c,v 1.4 2012/06/22 13:43:17 rmind Exp $	*/
+/*	$NetBSD: npf_alg.c,v 1.5 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2010 The NetBSD Foundation, Inc.
@@ -34,7 +34,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf_alg.c,v 1.4 2012/06/22 13:43:17 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf_alg.c,v 1.5 2012/07/15 00:23:00 rmind Exp $");
 
 #include <sys/param.h>
 #include <sys/types.h>
@@ -115,9 +115,11 @@
 	pserialize_perform(nat_alg_psz);
 	mutex_exit(&nat_alg_lock);
 
-	npf_nat_freealg(alg);
+	npf_core_enter();
+	npf_ruleset_freealg(npf_core_natset(), alg);
+	npf_core_exit();
+
 	kmem_free(alg, sizeof(npf_alg_t));
-
 	return 0;
 }
 
--- a/sys/net/npf/npf_alg_icmp.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf_alg_icmp.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_alg_icmp.c,v 1.9 2012/02/20 00:18:19 rmind Exp $	*/
+/*	$NetBSD: npf_alg_icmp.c,v 1.10 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2010 The NetBSD Foundation, Inc.
@@ -34,7 +34,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf_alg_icmp.c,v 1.9 2012/02/20 00:18:19 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf_alg_icmp.c,v 1.10 2012/07/15 00:23:00 rmind Exp $");
 
 #include <sys/param.h>
 #include <sys/module.h>
@@ -101,6 +101,8 @@
 		return npf_alg_icmp_init();
 	case MODULE_CMD_FINI:
 		return npf_alg_icmp_fini();
+	case MODULE_CMD_AUTOUNLOAD:
+		return EBUSY;
 	default:
 		return ENOTTY;
 	}
@@ -278,7 +280,7 @@
 	KASSERT(npf_iscached(key, NPC_IP46));
 	KASSERT(npf_iscached(key, NPC_LAYER4));
 	npfa_srcdst_invert(key);
-	key->npc_ipsz = npc->npc_ipsz;
+	key->npc_alen = npc->npc_alen;
 
 	return true;
 }
@@ -325,7 +327,7 @@
 		cksum = npf_fixup16_cksum(cksum, uh->uh_sport, port);
 		l4cksum = uh->uh_sum;
 	}
-	cksum = npf_addr_cksum(cksum, enpc.npc_ipsz, enpc.npc_srcip, addr);
+	cksum = npf_addr_cksum(cksum, enpc.npc_alen, enpc.npc_srcip, addr);
 
 	/*
 	 * Save the original pointers to the main IP header and then advance
--- a/sys/net/npf/npf_ctl.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf_ctl.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_ctl.c,v 1.15 2012/05/30 21:38:03 rmind Exp $	*/
+/*	$NetBSD: npf_ctl.c,v 1.16 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2009-2012 The NetBSD Foundation, Inc.
@@ -37,7 +37,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf_ctl.c,v 1.15 2012/05/30 21:38:03 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf_ctl.c,v 1.16 2012/07/15 00:23:00 rmind Exp $");
 
 #include <sys/param.h>
 #include <sys/conf.h>
@@ -135,12 +135,15 @@
 		while ((ent = prop_object_iterator_next(eit)) != NULL) {
 			const npf_addr_t *addr;
 			npf_netmask_t mask;
+			int alen;
 
 			/* Get address and mask.  Add a table entry. */
-			addr = (const npf_addr_t *)prop_data_data_nocopy(
-			    prop_dictionary_get(ent, "addr"));
+			prop_object_t obj = prop_dictionary_get(ent, "addr");
+			addr = (const npf_addr_t *)prop_data_data_nocopy(obj);
 			prop_dictionary_get_uint8(ent, "mask", &mask);
-			error = npf_table_add_cidr(tblset, tid, addr, mask);
+			alen = prop_data_size(obj);
+
+			error = npf_table_insert(tblset, tid, alen, addr, mask);
 			if (error)
 				break;
 		}
@@ -689,16 +692,16 @@
 	tblset = npf_core_tableset();
 	switch (nct->nct_action) {
 	case NPF_IOCTL_TBLENT_ADD:
-		error = npf_table_add_cidr(tblset, nct->nct_tid,
-		    &nct->nct_addr, nct->nct_mask);
+		error = npf_table_insert(tblset, nct->nct_tid,
+		    nct->nct_alen, &nct->nct_addr, nct->nct_mask);
 		break;
 	case NPF_IOCTL_TBLENT_REM:
-		error = npf_table_rem_cidr(tblset, nct->nct_tid,
-		    &nct->nct_addr, nct->nct_mask);
+		error = npf_table_remove(tblset, nct->nct_tid,
+		    nct->nct_alen, &nct->nct_addr, nct->nct_mask);
 		break;
 	default:
-		error = npf_table_match_addr(tblset, nct->nct_tid,
-		    &nct->nct_addr);
+		error = npf_table_lookup(tblset, nct->nct_tid,
+		    nct->nct_alen, &nct->nct_addr);
 	}
 	npf_core_exit(); /* XXXSMP */
 	return error;
--- a/sys/net/npf/npf_handler.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf_handler.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_handler.c,v 1.19 2012/07/02 06:55:58 rmind Exp $	*/
+/*	$NetBSD: npf_handler.c,v 1.20 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2009-2012 The NetBSD Foundation, Inc.
@@ -34,7 +34,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf_handler.c,v 1.19 2012/07/02 06:55:58 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf_handler.c,v 1.20 2012/07/15 00:23:00 rmind Exp $");
 
 #include <sys/types.h>
 #include <sys/param.h>
@@ -119,11 +119,13 @@
 #endif
 		}
 		if (error) {
+			npf_stats_inc(NPF_STAT_REASSFAIL);
 			se = NULL;
 			goto out;
 		}
 		if (*mp == NULL) {
 			/* More fragments should come; return. */
+			npf_stats_inc(NPF_STAT_FRAGMENTS);
 			return 0;
 		}
 
@@ -136,6 +138,7 @@
 
 		int ret __unused = npf_cache_all(&npc, nbuf);
 		KASSERT((ret & NPC_IPFRAG) == 0);
+		npf_stats_inc(NPF_STAT_REASSEMBLY);
 	}
 
 	/* Inspect the list of sessions. */
@@ -239,9 +242,7 @@
 		*mp = NULL;
 	}
 
-	if (error) {
-		npf_stats_inc(NPF_STAT_ERROR);
-	} else {
+	if (!error) {
 		error = ENETUNREACH;
 	}
 
--- a/sys/net/npf/npf_impl.h	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf_impl.h	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_impl.h,v 1.17 2012/07/01 23:21:06 rmind Exp $	*/
+/*	$NetBSD: npf_impl.h,v 1.18 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2009-2012 The NetBSD Foundation, Inc.
@@ -51,6 +51,7 @@
 #include <sys/queue.h>
 #include <sys/hash.h>
 #include <sys/rbtree.h>
+#include <sys/ptree.h>
 #include <sys/rwlock.h>
 #include <net/if.h>
 
@@ -213,6 +214,8 @@
 void		npf_tableset_sysinit(void);
 void		npf_tableset_sysfini(void);
 
+const pt_tree_ops_t npf_table_ptree_ops;
+
 npf_tableset_t *npf_tableset_create(void);
 void		npf_tableset_destroy(npf_tableset_t *);
 int		npf_tableset_insert(npf_tableset_t *, npf_table_t *);
@@ -225,13 +228,13 @@
 
 npf_table_t *	npf_table_get(npf_tableset_t *, u_int);
 void		npf_table_put(npf_table_t *);
-int		npf_table_check(npf_tableset_t *, u_int, int);
-int		npf_table_add_cidr(npf_tableset_t *, u_int,
-		    const npf_addr_t *, const npf_netmask_t);
-int		npf_table_rem_cidr(npf_tableset_t *, u_int,
-		    const npf_addr_t *, const npf_netmask_t);
-int		npf_table_match_addr(npf_tableset_t *, u_int,
-		    const npf_addr_t *);
+int		npf_table_check(const npf_tableset_t *, u_int, int);
+int		npf_table_insert(npf_tableset_t *, u_int,
+		    const int, const npf_addr_t *, const npf_netmask_t);
+int		npf_table_remove(npf_tableset_t *, u_int,
+		    const int, const npf_addr_t *, const npf_netmask_t);
+int		npf_table_lookup(npf_tableset_t *, u_int,
+		    const int, const npf_addr_t *);
 
 /* Ruleset interface. */
 npf_ruleset_t *	npf_ruleset_create(void);
@@ -241,6 +244,7 @@
 npf_rule_t *	npf_ruleset_matchnat(npf_ruleset_t *, npf_natpolicy_t *);
 npf_rule_t *	npf_ruleset_sharepm(npf_ruleset_t *, npf_natpolicy_t *);
 npf_rule_t *	npf_ruleset_replace(const char *, npf_ruleset_t *);
+void		npf_ruleset_freealg(npf_ruleset_t *, npf_alg_t *);
 
 npf_rule_t *	npf_ruleset_inspect(npf_cache_t *, nbuf_t *, npf_ruleset_t *,
 		    ifnet_t *, const int, const int);
@@ -297,6 +301,7 @@
 void		npf_nat_freepolicy(npf_natpolicy_t *);
 bool		npf_nat_matchpolicy(npf_natpolicy_t *, npf_natpolicy_t *);
 bool		npf_nat_sharepm(npf_natpolicy_t *, npf_natpolicy_t *);
+void		npf_nat_freealg(npf_natpolicy_t *, npf_alg_t *);
 
 int		npf_do_nat(npf_cache_t *, npf_session_t *, nbuf_t *,
 		    ifnet_t *, const int);
@@ -304,7 +309,6 @@
 void		npf_nat_getorig(npf_nat_t *, npf_addr_t **, in_port_t *);
 void		npf_nat_gettrans(npf_nat_t *, npf_addr_t **, in_port_t *);
 void		npf_nat_setalg(npf_nat_t *, npf_alg_t *, uintptr_t);
-void		npf_nat_freealg(npf_alg_t *);
 
 int		npf_nat_save(prop_dictionary_t, prop_array_t, npf_nat_t *);
 npf_nat_t *	npf_nat_restore(prop_dictionary_t, npf_session_t *);
--- a/sys/net/npf/npf_inet.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf_inet.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_inet.c,v 1.13 2012/07/01 23:21:06 rmind Exp $	*/
+/*	$NetBSD: npf_inet.c,v 1.14 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2009-2012 The NetBSD Foundation, Inc.
@@ -39,7 +39,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf_inet.c,v 1.13 2012/07/01 23:21:06 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf_inet.c,v 1.14 2012/07/15 00:23:00 rmind Exp $");
 
 #include <sys/param.h>
 #include <sys/types.h>
@@ -322,7 +322,7 @@
 		}
 
 		/* Cache: layer 3 - IPv4. */
-		npc->npc_ipsz = sizeof(struct in_addr);
+		npc->npc_alen = sizeof(struct in_addr);
 		npc->npc_srcip = (npf_addr_t *)&ip->ip_src;
 		npc->npc_dstip = (npf_addr_t *)&ip->ip_dst;
 		npc->npc_info |= NPC_IP4;
@@ -378,7 +378,7 @@
 		}
 
 		/* Cache: layer 3 - IPv6. */
-		npc->npc_ipsz = sizeof(struct in6_addr);
+		npc->npc_alen = sizeof(struct in6_addr);
 		npc->npc_srcip = (npf_addr_t *)&ip6->ip6_src;
 		npc->npc_dstip = (npf_addr_t *)&ip6->ip6_dst;
 		npc->npc_info |= NPC_IP6;
@@ -427,7 +427,6 @@
 bool
 npf_fetch_udp(npf_cache_t *npc, nbuf_t *nbuf, void *n_ptr)
 {
-	struct ip *ip = &npc->npc_ip.v4;
 	struct udphdr *uh;
 	u_int hlen;
 
@@ -435,7 +434,7 @@
 	if (!npf_iscached(npc, NPC_IP46) && !npf_fetch_ip(npc, nbuf, n_ptr)) {
 		return false;
 	}
-	if (ip->ip_p != IPPROTO_UDP) {
+	if (npf_cache_ipproto(npc) != IPPROTO_UDP) {
 		return false;
 	}
 	uh = &npc->npc_l4.udp;
@@ -457,7 +456,6 @@
 bool
 npf_fetch_icmp(npf_cache_t *npc, nbuf_t *nbuf, void *n_ptr)
 {
-	struct ip *ip = &npc->npc_ip.v4;
 	struct icmp *ic;
 	u_int hlen, iclen;
 
@@ -465,7 +463,7 @@
 	if (!npf_iscached(npc, NPC_IP46) && !npf_fetch_ip(npc, nbuf, n_ptr)) {
 		return false;
 	}
-	if (ip->ip_p != IPPROTO_ICMP) {
+	if (npf_cache_ipproto(npc) != IPPROTO_ICMP) {
 		return false;
 	}
 	ic = &npc->npc_l4.icmp;
@@ -534,11 +532,11 @@
 	}
 
 	/* Advance to the address and rewrite it. */
-	if (nbuf_advstore(&nbuf, &n_ptr, offby, npc->npc_ipsz, addr))
+	if (nbuf_advstore(&nbuf, &n_ptr, offby, npc->npc_alen, addr))
 		return false;
 
 	/* Cache: IP address. */
-	memcpy(oaddr, addr, npc->npc_ipsz);
+	memcpy(oaddr, addr, npc->npc_alen);
 	return true;
 }
 
@@ -605,7 +603,7 @@
 		uint16_t ipsum;
 
 		oaddr = (di == PFIL_OUT) ? npc->npc_srcip : npc->npc_dstip;
-		ipsum = npf_addr_cksum(ip->ip_sum, npc->npc_ipsz, oaddr, addr);
+		ipsum = npf_addr_cksum(ip->ip_sum, npc->npc_alen, oaddr, addr);
 
 		/* Advance to the IPv4 checksum and rewrite it. */
 		offby = offsetof(struct ip, ip_sum);
@@ -647,7 +645,7 @@
 		offby += offsetof(struct udphdr, uh_sum);
 		oport = (di == PFIL_OUT) ? &uh->uh_sport : &uh->uh_dport;
 	}
-	*cksum = npf_addr_cksum(*cksum, npc->npc_ipsz, oaddr, addr);
+	*cksum = npf_addr_cksum(*cksum, npc->npc_alen, oaddr, addr);
 	*cksum = npf_fixup16_cksum(*cksum, *oport, port);
 
 	/* Advance to TCP/UDP checksum and rewrite it. */
--- a/sys/net/npf/npf_instr.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf_instr.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_instr.c,v 1.12 2012/07/01 23:21:06 rmind Exp $	*/
+/*	$NetBSD: npf_instr.c,v 1.13 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2009-2012 The NetBSD Foundation, Inc.
@@ -34,7 +34,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf_instr.c,v 1.12 2012/07/01 23:21:06 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf_instr.c,v 1.13 2012/07/15 00:23:00 rmind Exp $");
 
 #include <sys/param.h>
 #include <sys/types.h>
@@ -95,7 +95,7 @@
 int
 npf_match_proto(npf_cache_t *npc, nbuf_t *nbuf, void *n_ptr, uint32_t ap)
 {
-	const int addrlen = (ap >> 8) & 0xff;
+	const int alen = (ap >> 8) & 0xff;
 	const int proto = ap & 0xff;
 
 	if (!npf_iscached(npc, NPC_IP46)) {
@@ -105,7 +105,7 @@
 		KASSERT(npf_iscached(npc, NPC_IP46));
 	}
 
-	if (addrlen && npc->npc_ipsz != addrlen) {
+	if (alen && npc->npc_alen != alen) {
 		return -1;
 	}
 	return (proto != 0xff && npf_cache_ipproto(npc) != proto) ? -1 : 0;
@@ -118,7 +118,9 @@
 npf_match_table(npf_cache_t *npc, nbuf_t *nbuf, void *n_ptr,
     const int sd, const u_int tid)
 {
+	npf_tableset_t *tblset;
 	npf_addr_t *addr;
+	int alen;
 
 	KASSERT(npf_core_locked());
 
@@ -129,9 +131,11 @@
 		KASSERT(npf_iscached(npc, NPC_IP46));
 	}
 	addr = sd ? npc->npc_srcip : npc->npc_dstip;
+	tblset = npf_core_tableset();
+	alen = npc->npc_alen;
 
 	/* Match address against NPF table. */
-	return npf_table_match_addr(npf_core_tableset(), tid, addr) ? -1 : 0;
+	return npf_table_lookup(tblset, tid, alen, addr) ? -1 : 0;
 }
 
 /*
@@ -150,7 +154,7 @@
 		}
 		KASSERT(npf_iscached(npc, NPC_IP46));
 	}
-	if (npc->npc_ipsz != alen) {
+	if (npc->npc_alen != alen) {
 		return -1;
 	}
 	addr = (szsd & 0x1) ? npc->npc_srcip : npc->npc_dstip;
--- a/sys/net/npf/npf_nat.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf_nat.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_nat.c,v 1.14 2012/07/01 23:21:06 rmind Exp $	*/
+/*	$NetBSD: npf_nat.c,v 1.15 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2010-2012 The NetBSD Foundation, Inc.
@@ -76,7 +76,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf_nat.c,v 1.14 2012/07/01 23:21:06 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf_nat.c,v 1.15 2012/07/15 00:23:00 rmind Exp $");
 
 #include <sys/param.h>
 #include <sys/types.h>
@@ -120,6 +120,7 @@
 	kmutex_t		n_lock;
 	kcondvar_t		n_cv;
 	npf_portmap_t *		n_portmap;
+	/* NPF_NP_CMP_START */
 	int			n_type;
 	u_int			n_flags;
 	size_t			n_addr_sz;
@@ -268,9 +269,18 @@
 }
 
 void
-npf_nat_freealg(npf_alg_t *alg)
+npf_nat_freealg(npf_natpolicy_t *np, npf_alg_t *alg)
 {
-	(void)alg; /* TODO */
+	npf_nat_t *nt;
+
+	mutex_enter(&np->n_lock);
+	LIST_FOREACH(nt, &np->n_nat_list, nt_entry) {
+		if (nt->nt_alg != alg) {
+			continue;
+		}
+		nt->nt_alg = NULL;
+	}
+	mutex_exit(&np->n_lock);
 }
 
 /*
@@ -453,11 +463,11 @@
 	/* Save the original address which may be rewritten. */
 	if (np->n_type == NPF_NATOUT) {
 		/* Source (local) for Outbound NAT. */
-		memcpy(&nt->nt_oaddr, npc->npc_srcip, npc->npc_ipsz);
+		memcpy(&nt->nt_oaddr, npc->npc_srcip, npc->npc_alen);
 	} else {
 		/* Destination (external) for Inbound NAT. */
 		KASSERT(np->n_type == NPF_NATIN);
-		memcpy(&nt->nt_oaddr, npc->npc_dstip, npc->npc_ipsz);
+		memcpy(&nt->nt_oaddr, npc->npc_dstip, npc->npc_alen);
 	}
 
 	/*
--- a/sys/net/npf/npf_ruleset.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf_ruleset.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_ruleset.c,v 1.12 2012/07/01 23:21:06 rmind Exp $	*/
+/*	$NetBSD: npf_ruleset.c,v 1.13 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2009-2012 The NetBSD Foundation, Inc.
@@ -34,7 +34,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf_ruleset.c,v 1.12 2012/07/01 23:21:06 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf_ruleset.c,v 1.13 2012/07/15 00:23:00 rmind Exp $");
 
 #include <sys/param.h>
 #include <sys/types.h>
@@ -165,6 +165,26 @@
 }
 
 /*
+ * npf_ruleset_freealg: inspect the ruleset and disassociate specified
+ * ALG from all NAT entries using it.
+ */
+void
+npf_ruleset_freealg(npf_ruleset_t *rlset, npf_alg_t *alg)
+{
+	npf_rule_t *rl;
+
+	KASSERT(npf_core_locked());
+
+	TAILQ_FOREACH(rl, &rlset->rs_queue, r_entry) {
+		npf_natpolicy_t *np = rl->r_natp;
+
+		if (np != NULL) {
+			npf_nat_freealg(np, alg);
+		}
+	}
+}
+
+/*
  * npf_ruleset_natreload: minimum reload of NAT policies by maching
  * two (active and new) NAT rulesets.
  *
--- a/sys/net/npf/npf_sendpkt.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf_sendpkt.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_sendpkt.c,v 1.11 2012/06/22 13:43:17 rmind Exp $	*/
+/*	$NetBSD: npf_sendpkt.c,v 1.12 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2010-2011 The NetBSD Foundation, Inc.
@@ -34,7 +34,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf_sendpkt.c,v 1.11 2012/06/22 13:43:17 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf_sendpkt.c,v 1.12 2012/07/15 00:23:00 rmind Exp $");
 
 #include <sys/param.h>
 #include <sys/types.h>
@@ -199,7 +199,7 @@
 {
 	void *n_ptr = nbuf_dataptr(nbuf);
 
-	if (!npf_iscached(npc, NPC_IP46) && !npf_fetch_ip(npc, nbuf, n_ptr)) {
+	if (!npf_iscached(npc, NPC_IP46) || !npf_iscached(npc, NPC_LAYER4)) {
 		return false;
 	}
 	switch (npf_cache_ipproto(npc)) {
--- a/sys/net/npf/npf_session.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf_session.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_session.c,v 1.14 2012/07/01 23:21:06 rmind Exp $	*/
+/*	$NetBSD: npf_session.c,v 1.15 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2010-2012 The NetBSD Foundation, Inc.
@@ -74,13 +74,13 @@
  *
  * Lock order
  *
- *	sess_lock ->
+ *	[ sess_lock -> ]
  *		npf_sehash_t::sh_lock ->
  *			npf_state_t::nst_lock
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf_session.c,v 1.14 2012/07/01 23:21:06 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf_session.c,v 1.15 2012/07/15 00:23:00 rmind Exp $");
 
 #include <sys/param.h>
 #include <sys/types.h>
@@ -112,7 +112,7 @@
 	rb_node_t		se_rbnode;
 	npf_session_t *		se_backptr;
 	/* Size of the addresses. */
-	int			se_addr_sz;
+	int			se_alen;
 	/* Source and destination addresses. */
 	npf_addr_t		se_src_addr;
 	npf_addr_t		se_dst_addr;
@@ -236,7 +236,7 @@
 {
 	const npf_sentry_t * const sen1 = n1;
 	const npf_sentry_t * const sen2 = n2;
-	const int sz = sen1->se_addr_sz;
+	const int sz = sen1->se_alen;
 	int ret;
 
 	/*
@@ -251,8 +251,8 @@
 	/*
 	 * Note that hash should minimise differentiation on addresses.
 	 */
-	if (sen1->se_addr_sz != sen2->se_addr_sz) {
-		return (sen1->se_addr_sz < sen2->se_addr_sz) ? -1 : 1;
+	if (sen1->se_alen != sen2->se_alen) {
+		return (sen1->se_alen < sen2->se_alen) ? -1 : 1;
 	}
 	if ((ret = memcmp(&sen1->se_src_addr, &sen2->se_src_addr, sz)) != 0) {
 		return ret;
@@ -269,7 +269,7 @@
 	const npf_sentry_t * const sen1 = n1;
 	const npf_sentry_t * const sen2 = key;
 
-	KASSERT(sen1->se_addr_sz != 0 && sen2->se_addr_sz != 0);
+	KASSERT(sen1->se_alen != 0 && sen2->se_alen != 0);
 	return sess_rbtree_cmp_nodes(NULL, sen1, sen2);
 }
 
@@ -283,7 +283,7 @@
 static inline npf_sehash_t *
 sess_hash_bucket(npf_sehash_t *stbl, const int proto, npf_sentry_t *sen)
 {
-	const int sz = sen->se_addr_sz;
+	const int sz = sen->se_alen;
 	uint32_t hash, mix;
 
 	/* Sum protocol and both addresses (for both directions). */
@@ -390,6 +390,7 @@
 static void
 sess_tracking_stop(void)
 {
+	npf_sehash_t *stbl;
 
 	mutex_enter(&sess_lock);
 	if (sess_tracking == SESS_TRACKING_OFF) {
@@ -405,9 +406,11 @@
 	while (sess_gc_lwp != NULL) {
 		cv_wait(&sess_cv, &sess_lock);
 	}
+	stbl = sess_hashtbl;
+	sess_hashtbl = NULL;
 	mutex_exit(&sess_lock);
 
-	sess_htable_destroy(sess_hashtbl);
+	sess_htable_destroy(stbl);
 	pool_cache_invalidate(sess_cache);
 }
 
@@ -472,23 +475,36 @@
 	/* Note: take protocol from the key. */
 	const int proto = npf_cache_ipproto(key);
 
-	if (proto == IPPROTO_TCP) {
+	switch (proto) {
+	case IPPROTO_TCP: {
 		const struct tcphdr *th = &key->npc_l4.tcp;
 		senkey.se_src_id = th->th_sport;
 		senkey.se_dst_id = th->th_dport;
-	} else if (proto == IPPROTO_UDP) {
+		break;
+	}
+	case IPPROTO_UDP: {
 		const struct udphdr *uh = &key->npc_l4.udp;
 		senkey.se_src_id = uh->uh_sport;
 		senkey.se_dst_id = uh->uh_dport;
-	} else if (npf_iscached(key, NPC_ICMP_ID)) {
-		const struct icmp *ic = &key->npc_l4.icmp;
-		senkey.se_src_id = ic->icmp_id;
-		senkey.se_dst_id = ic->icmp_id;
+		break;
 	}
-	KASSERT(key->npc_srcip && key->npc_dstip && key->npc_ipsz > 0);
-	memcpy(&senkey.se_src_addr, key->npc_srcip, key->npc_ipsz);
-	memcpy(&senkey.se_dst_addr, key->npc_dstip, key->npc_ipsz);
-	senkey.se_addr_sz = key->npc_ipsz;
+	case IPPROTO_ICMP:
+		if (npf_iscached(key, NPC_ICMP_ID)) {
+			const struct icmp *ic = &key->npc_l4.icmp;
+			senkey.se_src_id = ic->icmp_id;
+			senkey.se_dst_id = ic->icmp_id;
+			break;
+		}
+		/* FALLTHROUGH */
+	default:
+		/* Unsupported protocol. */
+		return NULL;
+	}
+
+	KASSERT(key->npc_srcip && key->npc_dstip && key->npc_alen > 0);
+	memcpy(&senkey.se_src_addr, key->npc_srcip, key->npc_alen);
+	memcpy(&senkey.se_dst_addr, key->npc_dstip, key->npc_alen);
+	senkey.se_alen = key->npc_alen;
 
 	/*
 	 * Get a hash bucket from the cached key data.
@@ -552,7 +568,7 @@
 	npf_sentry_t *fw, *bk;
 	npf_sehash_t *sh;
 	npf_session_t *se;
-	int proto, sz;
+	int proto, alen;
 	bool ok;
 
 	/*
@@ -582,10 +598,10 @@
 
 	/* Unique IDs: IP addresses.  Setup "forwards" entry first. */
 	KASSERT(npf_iscached(npc, NPC_IP46));
-	sz = npc->npc_ipsz;
+	alen = npc->npc_alen;
 	fw = &se->s_forw_entry;
-	memcpy(&fw->se_src_addr, npc->npc_srcip, sz);
-	memcpy(&fw->se_dst_addr, npc->npc_dstip, sz);
+	memcpy(&fw->se_src_addr, npc->npc_srcip, alen);
+	memcpy(&fw->se_dst_addr, npc->npc_dstip, alen);
 
 	/* Initialize protocol state. */
 	if (!npf_state_init(npc, nbuf, &se->s_state)) {
@@ -632,14 +648,14 @@
 
 	/* Setup inverted "backwards". */
 	bk = &se->s_back_entry;
-	memcpy(&bk->se_src_addr, &fw->se_dst_addr, sz);
-	memcpy(&bk->se_dst_addr, &fw->se_src_addr, sz);
+	memcpy(&bk->se_src_addr, &fw->se_dst_addr, alen);
+	memcpy(&bk->se_dst_addr, &fw->se_src_addr, alen);
 	bk->se_src_id = fw->se_dst_id;
 	bk->se_dst_id = fw->se_src_id;
 
 	/* Finish the setup of entries. */
 	fw->se_backptr = bk->se_backptr = se;
-	fw->se_addr_sz = bk->se_addr_sz = sz;
+	fw->se_alen = bk->se_alen = alen;
 
 	/*
 	 * Insert the session and both entries into the tree.
@@ -738,13 +754,13 @@
 	npf_nat_gettrans(nt, &taddr, &tport);
 	if (di == PFIL_OUT) {
 		/* NPF_NATOUT: source in "forwards" = destination. */
-		memcpy(&sen->se_dst_addr, taddr, sen->se_addr_sz);
+		memcpy(&sen->se_dst_addr, taddr, sen->se_alen);
 		if (tport) {
 			sen->se_dst_id = tport;
 		}
 	} else {
 		/* NPF_NATIN: destination in "forwards" = source. */
-		memcpy(&sen->se_src_addr, taddr, sen->se_addr_sz);
+		memcpy(&sen->se_src_addr, taddr, sen->se_alen);
 		if (tport) {
 			sen->se_src_id = tport;
 		}
--- a/sys/net/npf/npf_state_tcp.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf_state_tcp.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_state_tcp.c,v 1.8 2012/07/01 18:13:51 rmind Exp $	*/
+/*	$NetBSD: npf_state_tcp.c,v 1.9 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2010-2012 The NetBSD Foundation, Inc.
@@ -34,7 +34,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf_state_tcp.c,v 1.8 2012/07/01 18:13:51 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf_state_tcp.c,v 1.9 2012/07/15 00:23:00 rmind Exp $");
 
 #include <sys/param.h>
 #include <sys/types.h>
@@ -179,7 +179,7 @@
 			[TCPFC_SYN]	= NPF_TCPS_OK,
 			/* SYN-ACK response to original SYN. */
 			[TCPFC_SYNACK]	= NPF_TCPS_SYN_RECEIVED,
-			/* FIN may be sent early. */
+			/* FIN may occur early. */
 			[TCPFC_FIN]	= NPF_TCPS_FIN_RECEIVED,
 		},
 	},
@@ -195,7 +195,7 @@
 			[TCPFC_SYNACK]	= NPF_TCPS_OK,
 			/* XXX: ACK of late SYN in simultaneous case? */
 			[TCPFC_ACK]	= NPF_TCPS_OK,
-			/* FIN may be sent early. */
+			/* FIN may occur early. */
 			[TCPFC_FIN]	= NPF_TCPS_FIN_RECEIVED,
 		},
 	},
--- a/sys/net/npf/npf_tableset.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/net/npf/npf_tableset.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_tableset.c,v 1.12 2012/07/01 23:21:06 rmind Exp $	*/
+/*	$NetBSD: npf_tableset.c,v 1.13 2012/07/15 00:23:00 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2009-2012 The NetBSD Foundation, Inc.
@@ -33,13 +33,12 @@
  * NPF tableset module.
  *
  * TODO:
- * - Convert to Patricia tree.
  * - Dynamic hash growing/shrinking (i.e. re-hash functionality), maybe?
  * - Dynamic array resize.
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: npf_tableset.c,v 1.12 2012/07/01 23:21:06 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: npf_tableset.c,v 1.13 2012/07/15 00:23:00 rmind Exp $");
 
 #include <sys/param.h>
 #include <sys/types.h>
@@ -55,36 +54,38 @@
 
 #include "npf_impl.h"
 
-/* Table entry structure. */
+/*
+ * Table entry, table and key-wrapper structures.
+ */
+
 struct npf_tblent {
-	/* Hash/tree entry. */
 	union {
-		LIST_ENTRY(npf_tblent)	hashq;
-		rb_node_t		rbnode;
+		LIST_ENTRY(npf_tblent) hashq;
+		pt_node_t	node;
 	} te_entry;
-	/* CIDR block. */
-	npf_addr_t			te_addr;
-	npf_netmask_t			te_mask;
+	int			te_alen;
+	npf_addr_t		te_addr;
 };
 
 LIST_HEAD(npf_hashl, npf_tblent);
 
-/* Table structure. */
 struct npf_table {
-	char				t_name[16];
+	char			t_name[16];
 	/* Lock and reference count. */
-	krwlock_t			t_lock;
-	u_int				t_refcnt;
+	krwlock_t		t_lock;
+	u_int			t_refcnt;
 	/* Table ID. */
-	u_int				t_id;
+	u_int			t_id;
 	/* The storage type can be: 1. Hash 2. RB-tree. */
-	int				t_type;
-	struct npf_hashl *		t_hashl;
-	u_long				t_hashmask;
-	rb_tree_t			t_rbtree;
+	int			t_type;
+	struct npf_hashl *	t_hashl;
+	u_long			t_hashmask;
+	pt_tree_t		t_tree[2];
 };
 
-static pool_cache_t			tblent_cache	__read_mostly;
+#define	NPF_ADDRLEN2TREE(alen)	((alen) >> 4)
+
+static pool_cache_t		tblent_cache	__read_mostly;
 
 /*
  * npf_table_sysinit: initialise tableset structures.
@@ -135,7 +136,7 @@
 /*
  * npf_tableset_insert: insert the table into the specified tableset.
  *
- * => Returns 0 on success, fails and returns errno if ID is already used.
+ * => Returns 0 on success.  Fails and returns error if ID is already used.
  */
 int
 npf_tableset_insert(npf_tableset_t *tblset, npf_table_t *t)
@@ -155,46 +156,42 @@
 }
 
 /*
- * Red-black tree storage.
+ * Few helper routines.
  */
 
-static signed int
-table_rbtree_cmp_nodes(void *ctx, const void *n1, const void *n2)
+static npf_tblent_t *
+table_hash_lookup(const npf_table_t *t, const npf_addr_t *addr,
+    const int alen, struct npf_hashl **rhtbl)
 {
-	const npf_tblent_t * const te1 = n1;
-	const npf_tblent_t * const te2 = n2;
+	const uint32_t hidx = hash32_buf(addr, alen, HASH32_BUF_INIT);
+	struct npf_hashl *htbl = &t->t_hashl[hidx & t->t_hashmask];
+	npf_tblent_t *ent;
 
-	return npf_addr_cmp(&te1->te_addr, te1->te_mask,
-	    &te2->te_addr, te2->te_mask, sizeof(npf_addr_t));
+	/*
+	 * Lookup the hash table and check for duplicates.
+	 * Note: mask is ignored for the hash storage.
+	 */
+	LIST_FOREACH(ent, htbl, te_entry.hashq) {
+		if (ent->te_alen != alen) {
+			continue;
+		}
+		if (memcmp(&ent->te_addr, addr, alen) == 0) {
+			break;
+		}
+	}
+	*rhtbl = htbl;
+	return ent;
 }
 
-static signed int
-table_rbtree_cmp_key(void *ctx, const void *n1, const void *key)
+static void
+table_tree_destroy(pt_tree_t *tree)
 {
-	const npf_tblent_t * const te = n1;
-	const npf_addr_t *t2 = key;
-
-	return npf_addr_cmp(&te->te_addr, te->te_mask,
-	    t2, NPF_NO_NETMASK, sizeof(npf_addr_t));
-}
+	npf_tblent_t *ent;
 
-static const rb_tree_ops_t table_rbtree_ops = {
-	.rbto_compare_nodes = table_rbtree_cmp_nodes,
-	.rbto_compare_key = table_rbtree_cmp_key,
-	.rbto_node_offset = offsetof(npf_tblent_t, te_entry.rbnode),
-	.rbto_context = NULL
-};
-
-/*
- * Hash helper routine.
- */
-
-static inline struct npf_hashl *
-table_hash_bucket(npf_table_t *t, const void *buf, size_t sz)
-{
-	const uint32_t hidx = hash32_buf(buf, sz, HASH32_BUF_INIT);
-
-	return &t->t_hashl[hidx & t->t_hashmask];
+	while ((ent = ptree_iterate(tree, NULL, PT_ASCENDING)) != NULL) {
+		ptree_remove_node(tree, ent);
+		pool_cache_put(tblent_cache, ent);
+	}
 }
 
 /*
@@ -210,7 +207,14 @@
 	t = kmem_zalloc(sizeof(npf_table_t), KM_SLEEP);
 	switch (type) {
 	case NPF_TABLE_TREE:
-		rb_tree_init(&t->t_rbtree, &table_rbtree_ops);
+		ptree_init(&t->t_tree[0], &npf_table_ptree_ops,
+		    (void *)(sizeof(struct in_addr) / sizeof(uint32_t)),
+		    offsetof(npf_tblent_t, te_entry.node),
+		    offsetof(npf_tblent_t, te_addr));
+		ptree_init(&t->t_tree[1], &npf_table_ptree_ops,
+		    (void *)(sizeof(struct in6_addr) / sizeof(uint32_t)),
+		    offsetof(npf_tblent_t, te_entry.node),
+		    offsetof(npf_tblent_t, te_addr));
 		break;
 	case NPF_TABLE_HASH:
 		t->t_hashl = hashinit(hsize, HASH_LIST, true, &t->t_hashmask);
@@ -235,26 +239,25 @@
 void
 npf_table_destroy(npf_table_t *t)
 {
-	npf_tblent_t *e;
-	u_int n;
 
 	switch (t->t_type) {
-	case NPF_TABLE_HASH:
-		for (n = 0; n <= t->t_hashmask; n++) {
-			while ((e = LIST_FIRST(&t->t_hashl[n])) != NULL) {
-				LIST_REMOVE(e, te_entry.hashq);
-				pool_cache_put(tblent_cache, e);
+	case NPF_TABLE_HASH: {
+		for (unsigned n = 0; n <= t->t_hashmask; n++) {
+			npf_tblent_t *ent;
+
+			while ((ent = LIST_FIRST(&t->t_hashl[n])) != NULL) {
+				LIST_REMOVE(ent, te_entry.hashq);
+				pool_cache_put(tblent_cache, ent);
 			}
 		}
 		hashdone(t->t_hashl, HASH_LIST, t->t_hashmask);
 		break;
-	case NPF_TABLE_TREE:
-		while ((e = rb_tree_iterate(&t->t_rbtree, NULL,
-		    RB_DIR_LEFT)) != NULL) {
-			rb_tree_remove_node(&t->t_rbtree, e);
-			pool_cache_put(tblent_cache, e);
-		}
+	}
+	case NPF_TABLE_TREE: {
+		table_tree_destroy(&t->t_tree[0]);
+		table_tree_destroy(&t->t_tree[1]);
 		break;
+	}
 	default:
 		KASSERT(false);
 	}
@@ -321,9 +324,9 @@
 
 /*
  * npf_table_check: validate ID and type.
- * */
+ */
 int
-npf_table_check(npf_tableset_t *tset, u_int tid, int type)
+npf_table_check(const npf_tableset_t *tset, u_int tid, int type)
 {
 
 	if ((u_int)tid >= NPF_TABLE_SLOTS) {
@@ -338,25 +341,47 @@
 	return 0;
 }
 
+static int
+npf_table_validate_cidr(const u_int aidx, const npf_addr_t *addr,
+    const npf_netmask_t mask)
+{
+
+	if (mask > NPF_MAX_NETMASK && mask != NPF_NO_NETMASK) {
+		return EINVAL;
+	}
+	if (aidx > 1) {
+		return EINVAL;
+	}
+
+	/*
+	 * For IPv4 (aidx = 0) - 32 and for IPv6 (aidx = 1) - 128.
+	 * If it is a host - shall use NPF_NO_NETMASK.
+	 */
+	if (mask >= (aidx ? 128 : 32) && mask != NPF_NO_NETMASK) {
+		return EINVAL;
+	}
+	return 0;
+}
+
 /*
- * npf_table_add_cidr: add an IP CIDR into the table.
+ * npf_table_insert: add an IP CIDR entry into the table.
  */
 int
-npf_table_add_cidr(npf_tableset_t *tset, u_int tid,
+npf_table_insert(npf_tableset_t *tset, u_int tid, const int alen,
     const npf_addr_t *addr, const npf_netmask_t mask)
 {
-	struct npf_hashl *htbl;
-	npf_tblent_t *ent, *it;
+	const u_int aidx = NPF_ADDRLEN2TREE(alen);
+	npf_tblent_t *ent;
 	npf_table_t *t;
-	npf_addr_t val;
-	int error = 0;
+	int error;
 
-	if (mask > NPF_MAX_NETMASK) {
-		return EINVAL;
+	error = npf_table_validate_cidr(aidx, addr, mask);
+	if (error) {
+		return error;
 	}
 	ent = pool_cache_get(tblent_cache, PR_WAITOK);
-	memcpy(&ent->te_addr, addr, sizeof(npf_addr_t));
-	ent->te_mask = mask;
+	memcpy(&ent->te_addr, addr, alen);
+	ent->te_alen = alen;
 
 	/* Get the table (acquire the lock). */
 	t = npf_table_get(tset, tid);
@@ -365,35 +390,42 @@
 		return EINVAL;
 	}
 
+	/*
+	 * Insert the entry.  Return an error on duplicate.
+	 */
 	switch (t->t_type) {
-	case NPF_TABLE_HASH:
-		/* Generate hash value from: address & mask. */
-		npf_addr_mask(addr, mask, sizeof(npf_addr_t), &val);
-		htbl = table_hash_bucket(t, &val, sizeof(npf_addr_t));
+	case NPF_TABLE_HASH: {
+		struct npf_hashl *htbl;
 
-		/* Lookup to check for duplicates. */
-		LIST_FOREACH(it, htbl, te_entry.hashq) {
-			if (it->te_mask != mask) {
-				continue;
-			}
-			if (!memcmp(&it->te_addr, addr, sizeof(npf_addr_t))) {
-				break;
-			}
+		/*
+		 * Hash tables by the concept support only IPs.
+		 */
+		if (mask != NPF_NO_NETMASK) {
+			error = EINVAL;
+			break;
 		}
-
-		/* If no duplicate - insert entry. */
-		if (__predict_true(it == NULL)) {
+		if (!table_hash_lookup(t, addr, alen, &htbl)) {
 			LIST_INSERT_HEAD(htbl, ent, te_entry.hashq);
 		} else {
 			error = EEXIST;
 		}
 		break;
-	case NPF_TABLE_TREE:
-		/* Insert entry.  Returns false, if duplicate. */
-		if (rb_tree_insert_node(&t->t_rbtree, ent) != ent) {
-			error = EEXIST;
+	}
+	case NPF_TABLE_TREE: {
+		pt_tree_t *tree = &t->t_tree[aidx];
+		bool ok;
+
+		/*
+		 * If no mask specified, use maximum mask.
+		 */
+		if (mask != NPF_NO_NETMASK) {
+			ok = ptree_insert_mask_node(tree, ent, mask);
+		} else {
+			ok = ptree_insert_node(tree, ent);
 		}
+		error = ok ? 0 : EEXIST;
 		break;
+	}
 	default:
 		KASSERT(false);
 	}
@@ -406,55 +438,48 @@
 }
 
 /*
- * npf_table_rem_cidr: remove an IP CIDR from the table.
+ * npf_table_remove: remove the IP CIDR entry from the table.
  */
 int
-npf_table_rem_cidr(npf_tableset_t *tset, u_int tid,
+npf_table_remove(npf_tableset_t *tset, u_int tid, const int alen,
     const npf_addr_t *addr, const npf_netmask_t mask)
 {
-	struct npf_hashl *htbl;
+	const u_int aidx = NPF_ADDRLEN2TREE(alen);
 	npf_tblent_t *ent;
 	npf_table_t *t;
-	npf_addr_t val;
+	int error;
 
-	if (mask > NPF_MAX_NETMASK) {
+	error = npf_table_validate_cidr(aidx, addr, mask);
+	if (error) {
+		return error;
+	}
+	t = npf_table_get(tset, tid);
+	if (t == NULL) {
 		return EINVAL;
 	}
 
-	/* Get the table (acquire the lock). */
-	t = npf_table_get(tset, tid);
-	if (__predict_false(t == NULL)) {
-		return EINVAL;
-	}
-
-	/* Key: (address & mask). */
-	npf_addr_mask(addr, mask, sizeof(npf_addr_t), &val);
-	ent = NULL;
+	switch (t->t_type) {
+	case NPF_TABLE_HASH: {
+		struct npf_hashl *htbl;
 
-	switch (t->t_type) {
-	case NPF_TABLE_HASH:
-		/* Generate hash value from: (address & mask). */
-		htbl = table_hash_bucket(t, &val, sizeof(npf_addr_t));
-		LIST_FOREACH(ent, htbl, te_entry.hashq) {
-			if (ent->te_mask != mask) {
-				continue;
-			}
-			if (!memcmp(&ent->te_addr, addr, sizeof(npf_addr_t))) {
-				break;
-			}
-		}
+		ent = table_hash_lookup(t, addr, alen, &htbl);
 		if (__predict_true(ent != NULL)) {
 			LIST_REMOVE(ent, te_entry.hashq);
 		}
 		break;
-	case NPF_TABLE_TREE:
-		ent = rb_tree_find_node(&t->t_rbtree, &val);
+	}
+	case NPF_TABLE_TREE: {
+		pt_tree_t *tree = &t->t_tree[aidx];
+
+		ent = ptree_find_node(tree, addr);
 		if (__predict_true(ent != NULL)) {
-			rb_tree_remove_node(&t->t_rbtree, ent);
+			ptree_remove_node(tree, ent);
 		}
 		break;
+	}
 	default:
 		KASSERT(false);
+		ent = NULL;
 	}
 	npf_table_put(t);
 
@@ -466,43 +491,40 @@
 }
 
 /*
- * npf_table_match_addr: find the table according to ID, lookup and
- * match the contents with specified IPv4 address.
+ * npf_table_lookup: find the table according to ID, lookup and match
+ * the contents with the specified IP address.
  */
 int
-npf_table_match_addr(npf_tableset_t *tset, u_int tid, const npf_addr_t *addr)
+npf_table_lookup(npf_tableset_t *tset, u_int tid,
+    const int alen, const npf_addr_t *addr)
 {
-	struct npf_hashl *htbl;
-	npf_tblent_t *ent = NULL;
+	const u_int aidx = NPF_ADDRLEN2TREE(alen);
+	npf_tblent_t *ent;
 	npf_table_t *t;
 
-	/* Get the table (acquire the lock). */
+	if (__predict_false(aidx > 1)) {
+		return EINVAL;
+	}
+
 	t = npf_table_get(tset, tid);
 	if (__predict_false(t == NULL)) {
 		return EINVAL;
 	}
 	switch (t->t_type) {
-	case NPF_TABLE_HASH:
-		htbl = table_hash_bucket(t, addr, sizeof(npf_addr_t));
-		LIST_FOREACH(ent, htbl, te_entry.hashq) {
-			if (npf_addr_cmp(addr, ent->te_mask, &ent->te_addr,
-			    NPF_NO_NETMASK, sizeof(npf_addr_t)) == 0) {
-				break;
-			}
-		}
+	case NPF_TABLE_HASH: {
+		struct npf_hashl *htbl;
+		ent = table_hash_lookup(t, addr, alen, &htbl);
 		break;
-	case NPF_TABLE_TREE:
-		ent = rb_tree_find_node(&t->t_rbtree, addr);
+	}
+	case NPF_TABLE_TREE: {
+		ent = ptree_find_node(&t->t_tree[aidx], addr);
 		break;
+	}
 	default:
 		KASSERT(false);
+		ent = NULL;
 	}
 	npf_table_put(t);
 
-	if (ent == NULL) {
-		return ENOENT;
-	}
-	KASSERT(npf_addr_cmp(addr, ent->te_mask, &ent->te_addr,
-	    NPF_NO_NETMASK, sizeof(npf_addr_t)) == 0);
-	return 0;
+	return ent ? 0 : ENOENT;
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/sys/net/npf/npf_tableset_ptree.c	Sun Jul 15 00:22:58 2012 +0000
@@ -0,0 +1,183 @@
+/*	$NetBSD: npf_tableset_ptree.c,v 1.1 2012/07/15 00:23:01 rmind Exp $	*/
+
+/*-
+ * Copyright (c) 2012 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Matt Thomas <matt@3am-software.com>.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * Patricia/RADIX tree comparators for NPF tables.
+ */
+
+#include <sys/cdefs.h>
+__KERNEL_RCSID(0, "$NetBSD: npf_tableset_ptree.c,v 1.1 2012/07/15 00:23:01 rmind Exp $");
+
+#include <sys/param.h>
+#include <sys/types.h>
+
+#include <sys/bitops.h>
+#include <sys/ptree.h>
+
+#include "npf_impl.h"
+
+#define	DIV32		5
+
+static pt_slot_t
+npf_ptree_testkey(const void *vkey, pt_bitoff_t bitoff,
+    pt_bitlen_t bitlen, void *ctx)
+{
+	const uint32_t *addr = (const uint32_t *)vkey;
+
+	KASSERT(bitoff < 32 * (const uintptr_t)ctx);
+	KASSERT(bitlen == 1);
+
+	const uint32_t bits = ntohl(addr[bitoff >> DIV32]);
+	const uint32_t mask = 0x80000000U >> (bitoff & 31);
+	return (bits & mask) ? PT_SLOT_RIGHT : PT_SLOT_LEFT;
+}
+
+static bool
+npf_ptree_matchkey(const void *vleft, const void *vright,
+    pt_bitoff_t bitoff, pt_bitlen_t bitlen, void *ctx)
+{
+	const uint32_t *left = (const uint32_t *)vleft;
+	const uint32_t *right = (const uint32_t *)vright;
+	const u_int nwords = (const uintptr_t)ctx;
+	size_t i = bitoff >> DIV32;
+
+	/* Constrain bitlen to a reasonable value. */
+	if (nwords * 32 < bitoff + bitlen || nwords * 32 < bitlen) {
+		bitlen = nwords * 32 - bitoff;
+	}
+
+	/* Find the first word from the offset. */
+	left += i;
+	right += i;
+	bitoff -= i * 32;
+
+	for (; i < nwords; i++, left++, right++, bitoff = 0) {
+		const uint32_t bits = ntohl(*left ^ *right);
+		const signed int xbitlen = 32 - (bitoff + bitlen);
+		uint32_t mask = UINT32_MAX >> bitoff;
+
+		/*
+		 * We have the mask up to the lowest bit.  Overlap with the
+		 * mask up to required lowest bit, if extacting the middle.
+		 */
+		KASSERT((size_t)bitoff < 32);
+		if (xbitlen > 0) {
+			mask &= UINT32_MAX << xbitlen;
+		}
+
+		/* Compare the masked part of the word. */
+		if (bits & mask) {
+			return false;
+		}
+
+		/* Done if extracting the middle or exactly up to the LSB. */
+		if (xbitlen >= 0) {
+			break;
+		}
+		bitlen = -xbitlen;
+	}
+
+	return true;
+}
+
+static bool
+npf_ptree_matchnode(const void *vleft, const void *vright,
+    pt_bitoff_t maxbitoff, pt_bitoff_t *bitoffp, pt_bitoff_t *slotp, void *ctx)
+{
+	static const uint32_t zeroes[4] = { 0, 0, 0, 0 };
+	const uint32_t *left = (const uint32_t *)vleft;
+	const uint32_t *right = vright ? (const uint32_t *)vright : zeroes;
+	pt_bitoff_t bitoff = *bitoffp;
+	const u_int nwords = (const uintptr_t)ctx;
+	size_t i = bitoff >> DIV32;
+
+	/* Constrain maxbitoff & bitlen to reasonable value. */
+	if (maxbitoff > nwords * 32) {
+		maxbitoff = nwords * 32;
+	}
+	pt_bitoff_t bitlen = maxbitoff - bitoff;
+
+	/* Find the first word from the offset. */
+	*slotp = PT_SLOT_LEFT;
+	left += i;
+	right += i;
+	bitoff -= i * 32;
+
+	for (; i < nwords; i++, left++, right++, bitoff = 0) {
+		const signed int xbitlen = 32 - (bitoff + bitlen);
+		uint32_t bits = ntohl(*left ^ *right);
+		uint32_t mask = UINT32_MAX >> bitoff;
+
+		KASSERT((size_t)bitoff < 32);
+		if (xbitlen > 0) {
+			mask &= UINT32_MAX << xbitlen;
+		}
+
+		/* Compare the masked part of the word. */
+		bits &= mask;
+		if (bits) {
+			/*
+			 * Did not match.  Find the bit where the difference
+			 * occured.  Also, determine the slot.
+			 */
+			bitoff = 32 * i + (32 - fls32(bits));
+
+			KASSERT(bitoff < nwords * 32);
+			KASSERT(bitoff >= *bitoffp);
+			KASSERT(bitoff <= maxbitoff);
+
+			*bitoffp = bitoff;
+			if ((ntohl(*left) >> (31 - bitoff)) & 1) {
+				*slotp = PT_SLOT_RIGHT;
+			}
+
+			KASSERT(npf_ptree_testkey(vleft, bitoff, 1, ctx)
+			    == *slotp);
+			return false;
+		}
+		if (xbitlen >= 0) {
+			i++;
+			break;
+		}
+		bitlen = -xbitlen;
+	}
+
+	bitoff = 32 * i;
+	*bitoffp = bitoff < maxbitoff ? bitoff : maxbitoff;
+	return true;
+}
+
+const pt_tree_ops_t npf_table_ptree_ops = {
+	.ptto_matchnode	= npf_ptree_matchnode,
+	.ptto_matchkey	= npf_ptree_matchkey,
+	.ptto_testnode	= npf_ptree_testkey,
+	.ptto_testkey	= npf_ptree_testkey,
+};
--- a/sys/rump/dev/lib/libnpf/Makefile	Sun Jul 15 00:16:28 2012 +0000
+++ b/sys/rump/dev/lib/libnpf/Makefile	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-#	$NetBSD: Makefile,v 1.3 2012/05/30 21:38:03 rmind Exp $
+#	$NetBSD: Makefile,v 1.4 2012/07/15 00:22:59 rmind Exp $
 #
 # Public Domain.
 #
@@ -10,7 +10,8 @@
 SRCS=	npf.c npf_alg.c npf_ctl.c npf_handler.c
 SRCS+=	npf_inet.c npf_instr.c npf_log.c npf_mbuf.c npf_nat.c
 SRCS+=	npf_processor.c npf_ruleset.c npf_rproc.c npf_sendpkt.c
-SRCS+=	npf_session.c npf_state.c npf_state_tcp.c npf_tableset.c
+SRCS+=	npf_session.c npf_state.c npf_state_tcp.c
+SRCS+=	npf_tableset.c npf_tableset_ptree.c
 
 SRCS+=	component.c
 
--- a/usr.sbin/npf/npfctl/npf_build.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/usr.sbin/npf/npfctl/npf_build.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_build.c,v 1.10 2012/07/01 23:21:06 rmind Exp $	*/
+/*	$NetBSD: npf_build.c,v 1.11 2012/07/15 00:22:58 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2011-2012 The NetBSD Foundation, Inc.
@@ -34,7 +34,7 @@
  */
 
 #include <sys/cdefs.h>
-__RCSID("$NetBSD: npf_build.c,v 1.10 2012/07/01 23:21:06 rmind Exp $");
+__RCSID("$NetBSD: npf_build.c,v 1.11 2012/07/15 00:22:58 rmind Exp $");
 
 #include <sys/types.h>
 #include <sys/ioctl.h>
@@ -42,7 +42,6 @@
 #include <stdlib.h>
 #include <inttypes.h>
 #include <string.h>
-#include <assert.h>
 #include <err.h>
 
 #include "npfctl.h"
@@ -578,7 +577,7 @@
  * npfctl_fill_table: fill NPF table with entries from a specified file.
  */
 static void
-npfctl_fill_table(nl_table_t *tl, const char *fname)
+npfctl_fill_table(nl_table_t *tl, u_int type, const char *fname)
 {
 	char *buf = NULL;
 	int l = 0;
@@ -590,19 +589,24 @@
 		err(EXIT_FAILURE, "open '%s'", fname);
 	}
 	while (l++, getline(&buf, &n, fp) != -1) {
-		fam_addr_mask_t *fam;
+		fam_addr_mask_t fam;
+		int alen;
 
 		if (*buf == '\n' || *buf == '#') {
 			continue;
 		}
-		fam = npfctl_parse_cidr(buf);
-		if (fam == NULL) {
-			errx(EXIT_FAILURE, "%s:%d: invalid table entry",
-			    fname, l);
+
+		if (!npfctl_parse_cidr(buf, &fam, &alen)) {
+			errx(EXIT_FAILURE,
+			    "%s:%d: invalid table entry", fname, l);
+		}
+		if (type == NPF_TABLE_HASH && fam.fam_mask != NPF_NO_NETMASK) {
+			errx(EXIT_FAILURE,
+			    "%s:%d: mask used with the hash table", fname, l);
 		}
 
 		/* Create and add a table entry. */
-		npf_table_add_entry(tl, &fam->fam_addr, fam->fam_mask);
+		npf_table_add_entry(tl, alen, &fam.fam_addr, fam.fam_mask);
 	}
 	if (buf != NULL) {
 		free(buf);
@@ -628,6 +632,6 @@
 	}
 
 	if (fname) {
-		npfctl_fill_table(tl, fname);
+		npfctl_fill_table(tl, type, fname);
 	}
 }
--- a/usr.sbin/npf/npfctl/npf_data.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/usr.sbin/npf/npfctl/npf_data.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_data.c,v 1.14 2012/07/01 23:21:06 rmind Exp $	*/
+/*	$NetBSD: npf_data.c,v 1.15 2012/07/15 00:22:59 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2009-2012 The NetBSD Foundation, Inc.
@@ -31,7 +31,7 @@
  */
 
 #include <sys/cdefs.h>
-__RCSID("$NetBSD: npf_data.c,v 1.14 2012/07/01 23:21:06 rmind Exp $");
+__RCSID("$NetBSD: npf_data.c,v 1.15 2012/07/15 00:22:59 rmind Exp $");
 
 #include <sys/types.h>
 #include <sys/null.h>
@@ -124,21 +124,12 @@
 			return false;
 	}
 
-	switch (fam) {
-	case AF_INET:
-		*mask = 32;
-		break;
-	case AF_INET6:
-		*mask = 128;
-		break;
-	default:
-		yyerror("unknown address family %u", fam);
-		return false;
-	}
-
+	assert(fam == AF_INET || fam == AF_INET6);
+	*mask = NPF_NO_NETMASK;
 	if (ep == NULL) {
 		return true;
 	}
+
 	ap = addr.s6_addr + (*mask / 8) - 1;
 	while (ap >= addr.s6_addr) {
 		for (int j = 8; j > 0; j--) {
@@ -331,21 +322,38 @@
 	return NULL;
 }
 
-fam_addr_mask_t *
-npfctl_parse_cidr(char *cidr)
+bool
+npfctl_parse_cidr(char *cidr, fam_addr_mask_t *fam, int *alen)
 {
-	npfvar_t *vp;
-	char *p;
+	char *mask, *p;
 
-	p = strchr(cidr, '/');
+	p = strchr(cidr, '\n');
 	if (p) {
-		*p++ = '\0';
+		*p = '\0';
+	}
+	mask = strchr(cidr, '/');
+	if (mask) {
+		*mask++ = '\0';
+	}
+
+	memset(fam, 0, sizeof(*fam));
+	if (!npfctl_parse_fam_addr(cidr, &fam->fam_family, &fam->fam_addr)) {
+		return false;
 	}
-	vp = npfctl_parse_fam_addr_mask(cidr, p, NULL);
-	if (vp == NULL) {
-		return NULL;
+	if (!npfctl_parse_mask(mask, fam->fam_family, &fam->fam_mask)) {
+		return false;
 	}
-	return npfvar_get_data(vp, NPFVAR_FAM, 0);
+	switch (fam->fam_family) {
+	case AF_INET:
+		*alen = sizeof(struct in_addr);
+		break;
+	case AF_INET6:
+		*alen = sizeof(struct in6_addr);
+		break;
+	default:
+		return false;
+	}
+	return true;
 }
 
 int
--- a/usr.sbin/npf/npfctl/npf_disassemble.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/usr.sbin/npf/npfctl/npf_disassemble.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_disassemble.c,v 1.6 2012/07/01 23:21:07 rmind Exp $	*/
+/*	$NetBSD: npf_disassemble.c,v 1.7 2012/07/15 00:22:59 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2012 The NetBSD Foundation, Inc.
@@ -30,14 +30,13 @@
  */
 
 #include <sys/cdefs.h>
-__RCSID("$NetBSD: npf_disassemble.c,v 1.6 2012/07/01 23:21:07 rmind Exp $");
+__RCSID("$NetBSD: npf_disassemble.c,v 1.7 2012/07/15 00:22:59 rmind Exp $");
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
 #include <errno.h>
-#include <assert.h>
 #include <err.h>
 #include <sys/socket.h>
 #include <netinet/in.h>
--- a/usr.sbin/npf/npfctl/npf_ncgen.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/usr.sbin/npf/npfctl/npf_ncgen.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_ncgen.c,v 1.11 2012/07/01 23:21:07 rmind Exp $	*/
+/*	$NetBSD: npf_ncgen.c,v 1.12 2012/07/15 00:22:59 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2009-2012 The NetBSD Foundation, Inc.
@@ -34,12 +34,11 @@
  */
 
 #include <sys/cdefs.h>
-__RCSID("$NetBSD: npf_ncgen.c,v 1.11 2012/07/01 23:21:07 rmind Exp $");
+__RCSID("$NetBSD: npf_ncgen.c,v 1.12 2012/07/15 00:22:59 rmind Exp $");
 
 #include <stdlib.h>
 #include <stddef.h>
 #include <inttypes.h>
-#include <assert.h>
 #include <err.h>
 
 #include "npfctl.h"
--- a/usr.sbin/npf/npfctl/npf_parse.y	Sun Jul 15 00:16:28 2012 +0000
+++ b/usr.sbin/npf/npfctl/npf_parse.y	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_parse.y,v 1.9 2012/07/01 23:21:07 rmind Exp $	*/
+/*	$NetBSD: npf_parse.y,v 1.10 2012/07/15 00:22:59 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2011-2012 The NetBSD Foundation, Inc.
@@ -35,7 +35,6 @@
 #include <err.h>
 #include <vis.h>
 #include <netdb.h>
-#include <assert.h>
 
 #include "npfctl.h"
 
--- a/usr.sbin/npf/npfctl/npfctl.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/usr.sbin/npf/npfctl/npfctl.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npfctl.c,v 1.14 2012/07/01 23:21:07 rmind Exp $	*/
+/*	$NetBSD: npfctl.c,v 1.15 2012/07/15 00:22:59 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2009-2012 The NetBSD Foundation, Inc.
@@ -30,7 +30,7 @@
  */
 
 #include <sys/cdefs.h>
-__RCSID("$NetBSD: npfctl.c,v 1.14 2012/07/01 23:21:07 rmind Exp $");
+__RCSID("$NetBSD: npfctl.c,v 1.15 2012/07/15 00:22:59 rmind Exp $");
 
 #include <sys/ioctl.h>
 #include <sys/stat.h>
@@ -42,6 +42,7 @@
 #include <err.h>
 #include <fcntl.h>
 #include <unistd.h>
+#include <errno.h>
 
 #include "npfctl.h"
 
@@ -62,7 +63,7 @@
 	NPFCTL_SESSIONS_LOAD,
 };
 
-static struct operations_s {
+static const struct operations_s {
 	const char *		cmd;
 	int			action;
 } operations[] = {
@@ -144,7 +145,7 @@
 	    "\t%s table <tid> [ flush ]\n",
 	    progname);
 	fprintf(stderr,
-	    "\t%s table <tid> { add | rem } <address/mask>\n",
+	    "\t%s table <tid> { add | rem | test } <address/mask>\n",
 	    progname);
 
 	exit(EXIT_FAILURE);
@@ -205,6 +206,12 @@
 	    "\t%"PRIu64" packets logged\n\t%"PRIu64" packets normalized\n\n",
 	    st[NPF_STAT_RPROC_LOG], st[NPF_STAT_RPROC_NORM]);
 
+	printf("Fragmentation:\n"
+	    "\t%"PRIu64" fragments\n\t%"PRIu64" reassembled\n"
+	    "\t%"PRIu64" failed reassembly\n\n",
+	    st[NPF_STAT_FRAGMENTS], st[NPF_STAT_REASSEMBLY],
+	    st[NPF_STAT_REASSFAIL]);
+
 	printf("Unexpected error cases:\n\t%"PRIu64"\n", st[NPF_STAT_ERROR]);
 
 	free(st);
@@ -237,17 +244,76 @@
 }
 
 static void
+npfctl_table(int fd, char **argv)
+{
+	static const struct tblops_s {
+		const char *	cmd;
+		int		action;
+	} tblops[] = {
+		{ "add",	NPF_IOCTL_TBLENT_ADD },
+		{ "rem",	NPF_IOCTL_TBLENT_REM },
+		{ "test",	0 },
+		{ NULL,		0 }
+	};
+	npf_ioctl_table_t nct;
+	fam_addr_mask_t fam;
+	char *cmd = argv[3];
+	char *arg = argv[3];
+	int n, alen;
+
+	memset(&nct, 0, sizeof(npf_ioctl_table_t));
+	nct.nct_tid = atoi(argv[2]);
+
+	for (n = 0; tblops[n].cmd != NULL; n++) {
+		if (strcmp(cmd, tblops[n].cmd) == 0) {
+			nct.nct_action = tblops[n].action;
+			arg = argv[4];
+			break;
+		}
+	}
+	if (!npfctl_parse_cidr(arg, &fam, &alen)) {
+		errx(EXIT_FAILURE, "invalid CIDR '%s'", arg);
+	}
+	memcpy(&nct.nct_addr, &fam.fam_addr, sizeof(npf_addr_t));
+	nct.nct_mask = fam.fam_mask;
+	nct.nct_alen = alen;
+
+	if (ioctl(fd, IOC_NPF_TABLE, &nct) != -1) {
+		errno = 0;
+	}
+	switch (errno) {
+	case EEXIST:
+		warnx("entry already exists or is conflicting");
+		break;
+	case ENOENT:
+		warnx("no matching entry was not found");
+		break;
+	case EINVAL:
+		warnx("invalid address, mask or table ID");
+		break;
+	case 0:
+		printf("%s: %s\n", getprogname(), nct.nct_action == 0 ?
+		    "matching entry found" : "success");
+		break;
+	default:
+		warn("error");
+	}
+	exit(errno ? EXIT_FAILURE : EXIT_SUCCESS);
+}
+
+static void
 npfctl(int action, int argc, char **argv)
 {
 	int fd, ret, ver, boolval;
-	npf_ioctl_table_t tbl;
-	char *arg;
 
 	fd = open(NPF_DEV_PATH, O_RDONLY);
 	if (fd == -1) {
 		err(EXIT_FAILURE, "cannot open '%s'", NPF_DEV_PATH);
 	}
 	ret = ioctl(fd, IOC_NPF_VERSION, &ver);
+	if (ret == -1) {
+		err(EXIT_FAILURE, "ioctl");
+	}
 	if (ver != NPF_VERSION) {
 		errx(EXIT_FAILURE,
 		    "incompatible NPF interface version (%d, kernel %d)\n"
@@ -266,6 +332,9 @@
 		npfctl_config_init(false);
 		npfctl_parsecfg(argc < 3 ? NPF_CONF_PATH : argv[2]);
 		ret = npfctl_config_send(fd);
+		if (ret) {
+			errx(EXIT_FAILURE, "ioctl: %s", strerror(ret));
+		}
 		break;
 	case NPFCTL_SHOWCONF:
 		ret = npfctl_config_show(fd);
@@ -277,45 +346,19 @@
 		if (argc < 5) {
 			usage();
 		}
-		tbl.nct_tid = atoi(argv[2]);
-		if (strcmp(argv[3], "add") == 0) {
-			/* Add table entry. */
-			tbl.nct_action = NPF_IOCTL_TBLENT_ADD;
-			arg = argv[4];
-		} else if (strcmp(argv[3], "rem") == 0) {
-			/* Remove entry. */
-			tbl.nct_action = NPF_IOCTL_TBLENT_REM;
-			arg = argv[4];
-		} else {
-			/* Default: lookup. */
-			tbl.nct_action = 0;
-			arg = argv[3];
-		}
-		fam_addr_mask_t *fam = npfctl_parse_cidr(arg);
-		if (fam == NULL) {
-			errx(EXIT_FAILURE, "invalid CIDR '%s'", arg);
-		}
-		memcpy(&tbl.nct_addr, &fam->fam_addr, sizeof(npf_addr_t));
-		tbl.nct_mask = fam->fam_mask;
-		ret = ioctl(fd, IOC_NPF_TABLE, &tbl);
-		if (tbl.nct_action == 0) {
-			printf("%s\n", ret ? "not found" : "found");
-			exit(ret ? EXIT_FAILURE : EXIT_SUCCESS);
-		}
+		npfctl_table(fd, argv);
 		break;
 	case NPFCTL_STATS:
 		ret = npfctl_print_stats(fd);
 		break;
 	case NPFCTL_SESSIONS_SAVE:
-		ret = npf_sessions_recv(fd, NPF_SESSDB_PATH);
-		if (ret) {
+		if (npf_sessions_recv(fd, NPF_SESSDB_PATH) != 0) {
 			errx(EXIT_FAILURE, "could not save sessions to '%s'",
 			    NPF_SESSDB_PATH);
 		}
 		break;
 	case NPFCTL_SESSIONS_LOAD:
-		ret = npf_sessions_send(fd, NPF_SESSDB_PATH);
-		if (ret) {
+		if (npf_sessions_send(fd, NPF_SESSDB_PATH) != 0) {
 			errx(EXIT_FAILURE, "no sessions loaded from '%s'",
 			    NPF_SESSDB_PATH);
 		}
--- a/usr.sbin/npf/npfctl/npfctl.h	Sun Jul 15 00:16:28 2012 +0000
+++ b/usr.sbin/npf/npfctl/npfctl.h	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npfctl.h,v 1.16 2012/07/01 23:21:07 rmind Exp $	*/
+/*	$NetBSD: npfctl.h,v 1.17 2012/07/15 00:22:59 rmind Exp $	*/
 
 /*-
  * Copyright (c) 2009-2012 The NetBSD Foundation, Inc.
@@ -32,6 +32,7 @@
 #include <stdio.h>
 #include <stdbool.h>
 #include <inttypes.h>
+#include <assert.h>
 
 #include <net/npf_ncode.h>
 #include <net/npf.h>
@@ -110,7 +111,7 @@
 npfvar_t *	npfctl_parse_port_range_variable(const char *);
 npfvar_t *	npfctl_parse_fam_addr_mask(const char *, const char *,
 		    unsigned long *);
-fam_addr_mask_t *npfctl_parse_cidr(char *);
+bool		npfctl_parse_cidr(char *, fam_addr_mask_t *, int *);
 
 /*
  * N-code generation interface.
--- a/usr.sbin/npf/npftest/libnpftest/npf_table_test.c	Sun Jul 15 00:16:28 2012 +0000
+++ b/usr.sbin/npf/npftest/libnpftest/npf_table_test.c	Sun Jul 15 00:22:58 2012 +0000
@@ -1,4 +1,4 @@
-/*	$NetBSD: npf_table_test.c,v 1.3 2012/07/01 23:21:07 rmind Exp $	*/
+/*	$NetBSD: npf_table_test.c,v 1.4 2012/07/15 00:22:59 rmind Exp $	*/
 
 /*
  * NPF tableset test.
@@ -22,6 +22,13 @@
 	"10.0.0.2",
 };
 
+static const uint32_t ip6_list[][4] = {
+	{ 0x000080fe, 0x00000000, 0xffc0a002, 0x341210fe },
+	{ 0x000080fe, 0x00000000, 0xffc0a002, 0x00000000 },
+	{ 0x000080fe, 0x00000000, 0x00000000, 0x00000000 },
+	{ 0x000080fe, 0x00000000, 0xffc0a002, 0x301210fe },
+};
+
 #define	HASH_TID		1
 #define	TREE_TID		2
 
@@ -29,9 +36,10 @@
 npf_table_test(bool verbose)
 {
 	npf_addr_t addr_storage, *addr = &addr_storage;
+	const int nm = NPF_NO_NETMASK;
 	npf_tableset_t *tblset;
 	npf_table_t *t1, *t2;
-	int error;
+	int error, alen;
 	u_int i;
 
 	npf_tableset_sysinit();
@@ -56,39 +64,38 @@
 	assert(error == 0);
 
 	/* Attempt to match non-existing entries - should fail. */
-	memset(addr, 0, sizeof(npf_addr_t));
 	addr->s6_addr32[0] = inet_addr(ip_list[0]);
+	alen = sizeof(struct in_addr);
 
-	error = npf_table_match_addr(tblset, HASH_TID, addr);
+	error = npf_table_lookup(tblset, HASH_TID, alen, addr);
 	assert(error != 0);
 
-	error = npf_table_match_addr(tblset, TREE_TID, addr);
+	error = npf_table_lookup(tblset, TREE_TID, alen, addr);
 	assert(error != 0);
 
 	/* Fill both tables with IP addresses. */
 	for (i = 0; i < __arraycount(ip_list); i++) {
-		memset(addr, 0, sizeof(npf_addr_t));
 		addr->s6_addr32[0] = inet_addr(ip_list[i]);
 
-		error = npf_table_add_cidr(tblset, HASH_TID, addr, 32);
+		error = npf_table_insert(tblset, HASH_TID, alen, addr, nm);
 		assert(error == 0);
-		error = npf_table_add_cidr(tblset, HASH_TID, addr, 32);
+		error = npf_table_insert(tblset, HASH_TID, alen, addr, nm);
 		assert(error != 0);
 
-		error = npf_table_add_cidr(tblset, TREE_TID, addr, 32);
+		error = npf_table_insert(tblset, TREE_TID, alen, addr, nm);
 		assert(error == 0);
-		error = npf_table_add_cidr(tblset, TREE_TID, addr, 32);
+		error = npf_table_insert(tblset, TREE_TID, alen, addr, nm);
 		assert(error != 0);
 	}
 
 	/* Attempt to add duplicates - should fail. */
-	memset(addr, 0, sizeof(npf_addr_t));
 	addr->s6_addr32[0] = inet_addr(ip_list[0]);
+	alen = sizeof(struct in_addr);
 
-	error = npf_table_add_cidr(tblset, HASH_TID, addr, 32);
+	error = npf_table_insert(tblset, HASH_TID, alen, addr, nm);
 	assert(error != 0);
 
-	error = npf_table_add_cidr(tblset, TREE_TID, addr, 32);
+	error = npf_table_insert(tblset, TREE_TID, alen, addr, nm);
 	assert(error != 0);
 
 	/* Reference checks. */
@@ -102,25 +109,86 @@
 
 	/* Match (validate) each IP entry. */
 	for (i = 0; i < __arraycount(ip_list); i++) {
-		memset(addr, 0, sizeof(npf_addr_t));
 		addr->s6_addr32[0] = inet_addr(ip_list[i]);
 
-		error = npf_table_match_addr(tblset, HASH_TID, addr);
+		error = npf_table_lookup(tblset, HASH_TID, alen, addr);
 		assert(error == 0);
 
-		error = npf_table_match_addr(tblset, TREE_TID, addr);
+		error = npf_table_lookup(tblset, TREE_TID, alen, addr);
 		assert(error == 0);
 	}
 
-	/* Remove all entries. */
+	/* IPv6 addresses. */
+	memcpy(addr, ip6_list[0], sizeof(ip6_list[0]));
+	alen = sizeof(struct in6_addr);
+
+	error = npf_table_insert(tblset, HASH_TID, alen, addr, nm);
+	assert(error == 0);
+	error = npf_table_lookup(tblset, HASH_TID, alen, addr);
+	assert(error == 0);
+	error = npf_table_remove(tblset, HASH_TID, alen, addr, nm);
+	assert(error == 0);
+
+	error = npf_table_insert(tblset, TREE_TID, alen, addr, nm);
+	assert(error == 0);
+	error = npf_table_lookup(tblset, TREE_TID, alen, addr);
+	assert(error == 0);
+	error = npf_table_remove(tblset, TREE_TID, alen, addr, nm);
+	assert(error == 0);
+
+	/*
+	 * Masking: 96, 32, 127.
+	 */
+
+	memcpy(addr, ip6_list[1], sizeof(ip6_list[1]));
+	error = npf_table_insert(tblset, TREE_TID, alen, addr, 96);
+	assert(error == 0);
+
+	memcpy(addr, ip6_list[0], sizeof(ip6_list[0]));
+	error = npf_table_lookup(tblset, TREE_TID, alen, addr);
+	assert(error == 0);
+
+	memcpy(addr, ip6_list[1], sizeof(ip6_list[1]));
+	error = npf_table_remove(tblset, TREE_TID, alen, addr, 96);
+	assert(error == 0);
+
+
+	memcpy(addr, ip6_list[2], sizeof(ip6_list[2]));
+	error = npf_table_insert(tblset, TREE_TID, alen, addr, 32);
+	assert(error == 0);
+
+	memcpy(addr, ip6_list[0], sizeof(ip6_list[0]));
+	error = npf_table_lookup(tblset, TREE_TID, alen, addr);
+	assert(error == 0);
+
+	memcpy(addr, ip6_list[2], sizeof(ip6_list[2]));
+	error = npf_table_remove(tblset, TREE_TID, alen, addr, 32);
+	assert(error == 0);
+
+
+	memcpy(addr, ip6_list[3], sizeof(ip6_list[3]));
+	error = npf_table_insert(tblset, TREE_TID, alen, addr, 126);
+	assert(error == 0);
+
+	memcpy(addr, ip6_list[0], sizeof(ip6_list[0]));
+	error = npf_table_lookup(tblset, TREE_TID, alen, addr);
+	assert(error != 0);
+
+	memcpy(addr, ip6_list[3], sizeof(ip6_list[3]));
+	error = npf_table_remove(tblset, TREE_TID, alen, addr, 126);
+	assert(error == 0);
+
+
+	alen = sizeof(struct in_addr);
+
+	/* Remove all IPv4 entries. */
 	for (i = 0; i < __arraycount(ip_list); i++) {
-		memset(addr, 0, sizeof(npf_addr_t));
 		addr->s6_addr32[0] = inet_addr(ip_list[i]);
 
-		error = npf_table_rem_cidr(tblset, HASH_TID, addr, 32);
+		error = npf_table_remove(tblset, HASH_TID, alen, addr, nm);
 		assert(error == 0);
 
-		error = npf_table_rem_cidr(tblset, TREE_TID, addr, 32);
+		error = npf_table_remove(tblset, TREE_TID, alen, addr, nm);
 		assert(error == 0);
 	}