Index: sbin/ipfw/ipfw.8
===================================================================
--- sbin/ipfw/ipfw.8
+++ sbin/ipfw/ipfw.8
@@ -3644,6 +3644,10 @@
 .It Va net.inet.ip.fw.tables_max: No 128
 Defines number of tables available in ipfw.
 Number cannot exceed 65534.
+.It Va net.inet.ip.fw.nat_hash: No 1
+Defines size of the hash table for accessing ipfw NAT instances.
+The number should be set to half of the number of expected instances.
+It works best with sequentially numbered instances.
 .El
 .Sh SYSCTL VARIABLES
 A set of
Index: sys/netpfil/ipfw/ip_fw2.c
===================================================================
--- sys/netpfil/ipfw/ip_fw2.c
+++ sys/netpfil/ipfw/ip_fw2.c
@@ -130,6 +130,9 @@
 /* Use 128 tables by default */
 static unsigned int default_fw_tables = IPFW_TABLES_DEFAULT;
 
+/* Keep hash as small as possible */
+int fw_nat_hash = 1;
+
 #ifndef LINEAR_SKIPTO
 static int jump_fast(struct ip_fw_chain *chain, struct ip_fw *f, int num,
     int tablearg, int jump_backwards);
@@ -166,7 +169,7 @@
 VNET_DEFINE(int, ipfw_nat_ready) = 0;
 
 ipfw_nat_t *ipfw_nat_ptr = NULL;
-struct cfg_nat *(*lookup_nat_ptr)(struct nat_list *, int);
+struct cfg_nat *(*lookup_nat_ptr)(struct nat_lists *, int);
 ipfw_nat_cfg_t *ipfw_nat_cfg_ptr;
 ipfw_nat_cfg_t *ipfw_nat_del_ptr;
 ipfw_nat_cfg_t *ipfw_nat_get_cfg_ptr;
@@ -209,6 +212,9 @@
 SYSCTL_INT(_net_inet_ip_fw, OID_AUTO, static_count,
     CTLFLAG_VNET | CTLFLAG_RD, &VNET_NAME(layer3_chain.n_rules), 0,
     "Number of static rules");
+SYSCTL_INT(_net_inet_ip_fw, OID_AUTO, nat_hash, CTLFLAG_RDTUN,
+    &fw_nat_hash, 0,
+    "Size of hash table for NAT instances.");
 
 #ifdef INET6
 SYSCTL_DECL(_net_inet6_ip6);
@@ -3327,6 +3333,9 @@
 	if (default_fw_tables > IPFW_TABLES_MAX)
 	  default_fw_tables = IPFW_TABLES_MAX;
 
+	if (fw_nat_hash < 1)
+	  fw_nat_hash = 1;
+
 	ipfw_init_sopt_handler();
 	ipfw_init_obj_rewriter();
 	ipfw_iface_init();
@@ -3369,9 +3378,6 @@
 #endif
 #ifdef IPFIREWALL_VERBOSE_LIMIT
 	V_verbose_limit = IPFIREWALL_VERBOSE_LIMIT;
-#endif
-#ifdef IPFIREWALL_NAT
-	LIST_INIT(&chain->nat);
 #endif
 
 	/* Init shared services hash table */
Index: sys/netpfil/ipfw/ip_fw_nat.c
===================================================================
--- sys/netpfil/ipfw/ip_fw_nat.c
+++ sys/netpfil/ipfw/ip_fw_nat.c
@@ -103,6 +103,7 @@
 	struct cfg_nat *ptr;
 	struct ifaddr *ifa;
 	struct ip_fw_chain *chain;
+	int i;
 
 	KASSERT(curvnet == ifp->if_vnet,
 	    ("curvnet(%p) differs from iface vnet(%p)", curvnet, ifp->if_vnet));
@@ -113,26 +114,27 @@
 	chain = &V_layer3_chain;
 	IPFW_UH_WLOCK(chain);
 	/* Check every nat entry... */
-	LIST_FOREACH(ptr, &chain->nat, _next) {
-		struct epoch_tracker et;
+	for(i = 0; i < chain->nat.len; i++)
+		LIST_FOREACH(ptr, &chain->nat.tbl[i], _next) {
+			struct epoch_tracker et;
 
-		/* ...using nic 'ifp->if_xname' as dynamic alias address. */
-		if (strncmp(ptr->if_name, ifp->if_xname, IF_NAMESIZE) != 0)
-			continue;
-		NET_EPOCH_ENTER(et);
-		CK_STAILQ_FOREACH(ifa, &ifp->if_addrhead, ifa_link) {
-			if (ifa->ifa_addr == NULL)
+			/* ...using nic 'ifp->if_xname' as dynamic alias address. */
+			if (strncmp(ptr->if_name, ifp->if_xname, IF_NAMESIZE) != 0)
 				continue;
-			if (ifa->ifa_addr->sa_family != AF_INET)
-				continue;
-			IPFW_WLOCK(chain);
-			ptr->ip = ((struct sockaddr_in *)
-			    (ifa->ifa_addr))->sin_addr;
-			LibAliasSetAddress(ptr->lib, ptr->ip);
-			IPFW_WUNLOCK(chain);
+			NET_EPOCH_ENTER(et);
+			CK_STAILQ_FOREACH(ifa, &ifp->if_addrhead, ifa_link) {
+				if (ifa->ifa_addr == NULL)
+					continue;
+				if (ifa->ifa_addr->sa_family != AF_INET)
+					continue;
+				IPFW_WLOCK(chain);
+				ptr->ip = ((struct sockaddr_in *)
+				    (ifa->ifa_addr))->sin_addr;
+				LibAliasSetAddress(ptr->lib, ptr->ip);
+				IPFW_WUNLOCK(chain);
+			}
+			NET_EPOCH_EXIT(et);
 		}
-		NET_EPOCH_EXIT(et);
-	}
 	IPFW_UH_WUNLOCK(chain);
 }
 
@@ -348,6 +350,8 @@
 
 	/* Check if this is 'global' instance */
 	if (t == NULL) {
+		int i;
+
 		if (args->flags & IPFW_ARGS_IN) {
 			/* Wrong direction, skip processing */
 			args->m = mcl;
@@ -358,17 +362,18 @@
 		chain = &V_layer3_chain;
 		IPFW_RLOCK_ASSERT(chain);
 		/* Check every nat entry... */
-		LIST_FOREACH(t, &chain->nat, _next) {
-			if ((t->mode & PKT_ALIAS_SKIP_GLOBAL) != 0)
-				continue;
-			retval = LibAliasOutTry(t->lib, c,
-			    mcl->m_len + M_TRAILINGSPACE(mcl), 0);
-			if (retval == PKT_ALIAS_OK) {
-				/* Nat instance recognises state */
-				found = 1;
-				break;
+		for(i = 0; i < chain->nat.len; i++)
+			LIST_FOREACH(t, &chain->nat.tbl[i], _next) {
+				if ((t->mode & PKT_ALIAS_SKIP_GLOBAL) != 0)
+					continue;
+				retval = LibAliasOutTry(t->lib, c,
+				    mcl->m_len + M_TRAILINGSPACE(mcl), 0);
+				if (retval == PKT_ALIAS_OK) {
+					/* Nat instance recognises state */
+					found = 1;
+					break;
+				}
 			}
-		}
 		if (found != 1) {
 			/* No instance found, return ignore */
 			args->m = mcl;
@@ -459,10 +464,14 @@
 }
 
 static struct cfg_nat *
-lookup_nat(struct nat_list *l, int nat_id)
+lookup_nat(struct nat_lists *ls, int nat_id)
 {
 	struct cfg_nat *res;
+	struct nat_list * l;
 
+	KASSERT(ls->len > 0 && ls->tbl != NULL, "Query an uninitialzed nat chain.");
+	l = NAT_TABLE_LIST(*ls, nat_id);
+
 	LIST_FOREACH(res, l, _next) {
 		if (res->id == nat_id)
 			break;
@@ -471,9 +480,8 @@
 }
 
 static struct cfg_nat *
-lookup_nat_name(struct nat_list *l, char *name)
+lookup_nat_name(struct nat_lists *ls, char *name)
 {
-	struct cfg_nat *res;
 	int id;
 	char *errptr;
 
@@ -481,11 +489,7 @@
 	if (id == 0 || *errptr != '\0')
 		return (NULL);
 
-	LIST_FOREACH(res, l, _next) {
-		if (res->id == id)
-			break;
-	}
-	return (res);
+	return lookup_nat(ls, id);
 }
 
 /* IP_FW3 configuration routines */
@@ -549,7 +553,7 @@
 	IPFW_WLOCK(chain);
 	if (tcfg != NULL)
 		LIST_REMOVE(tcfg, _next);
-	LIST_INSERT_HEAD(&chain->nat, ptr, _next);
+	LIST_INSERT_HEAD(NAT_TABLE_LIST(chain->nat, ptr->id), ptr, _next);
 	IPFW_WUNLOCK(chain);
 	chain->gencnt++;
 
@@ -774,7 +778,7 @@
 	ipfw_obj_lheader *olh;
 	struct nat44_cfg_nat *ucfg;
 	struct cfg_nat *ptr;
-	int nat_count;
+	int nat_count, i;
 
 	/* Check minimum header size */
 	if (sd->valsize < sizeof(ipfw_obj_lheader))
@@ -783,8 +787,9 @@
 	olh = (ipfw_obj_lheader *)ipfw_get_sopt_header(sd, sizeof(*olh));
 	IPFW_UH_RLOCK(chain);
 	nat_count = 0;
-	LIST_FOREACH(ptr, &chain->nat, _next)
-		nat_count++;
+	for(i = 0; i < chain->nat.len; i++)
+		LIST_FOREACH(ptr, &chain->nat.tbl[i], _next)
+			nat_count++;
 
 	olh->count = nat_count;
 	olh->objsize = sizeof(struct nat44_cfg_nat);
@@ -795,11 +800,12 @@
 		return (ENOMEM);
 	}
 
-	LIST_FOREACH(ptr, &chain->nat, _next) {
-		ucfg = (struct nat44_cfg_nat *)ipfw_get_sopt_space(sd,
-		    sizeof(*ucfg));
-		export_nat_cfg(ptr, ucfg);
-	}
+	for(i = 0; i < chain->nat.len; i++)
+		LIST_FOREACH(ptr, &chain->nat.tbl[i], _next) {
+			ucfg = (struct nat44_cfg_nat *)ipfw_get_sopt_space(sd,
+			    sizeof(*ucfg));
+			export_nat_cfg(ptr, ucfg);
+		}
 
 	IPFW_UH_RUNLOCK(chain);
 
@@ -1027,7 +1033,7 @@
 	struct cfg_redir_legacy *ser_r;
 	struct cfg_spool_legacy *ser_s;
 	char *data;
-	int gencnt, nat_cnt, len, error;
+	int gencnt, nat_cnt, len, error, i;
 
 	nat_cnt = 0;
 	len = sizeof(nat_cnt);
@@ -1036,15 +1042,16 @@
 retry:
 	gencnt = chain->gencnt;
 	/* Estimate memory amount */
-	LIST_FOREACH(n, &chain->nat, _next) {
-		nat_cnt++;
-		len += sizeof(struct cfg_nat_legacy);
-		LIST_FOREACH(r, &n->redir_chain, _next) {
-			len += sizeof(struct cfg_redir_legacy);
-			LIST_FOREACH(s, &r->spool_chain, _next)
-				len += sizeof(struct cfg_spool_legacy);
+	for(i = 0; i < chain->nat.len; i++)
+		LIST_FOREACH(n, &chain->nat.tbl[i], _next) {
+			nat_cnt++;
+			len += sizeof(struct cfg_nat_legacy);
+			LIST_FOREACH(r, &n->redir_chain, _next) {
+				len += sizeof(struct cfg_redir_legacy);
+				LIST_FOREACH(s, &r->spool_chain, _next)
+					len += sizeof(struct cfg_spool_legacy);
+			}
 		}
-	}
 	IPFW_UH_RUNLOCK(chain);
 
 	data = malloc(len, M_TEMP, M_WAITOK | M_ZERO);
@@ -1059,36 +1066,37 @@
 		goto retry;
 	}
 	/* Serialize all the data. */
-	LIST_FOREACH(n, &chain->nat, _next) {
-		ucfg = (struct cfg_nat_legacy *)&data[len];
-		ucfg->id = n->id;
-		ucfg->ip = n->ip;
-		ucfg->redir_cnt = n->redir_cnt;
-		ucfg->mode = n->mode;
-		strlcpy(ucfg->if_name, n->if_name, sizeof(ucfg->if_name));
-		len += sizeof(struct cfg_nat_legacy);
-		LIST_FOREACH(r, &n->redir_chain, _next) {
-			ser_r = (struct cfg_redir_legacy *)&data[len];
-			ser_r->mode = r->mode;
-			ser_r->laddr = r->laddr;
-			ser_r->paddr = r->paddr;
-			ser_r->raddr = r->raddr;
-			ser_r->lport = r->lport;
-			ser_r->pport = r->pport;
-			ser_r->rport = r->rport;
-			ser_r->pport_cnt = r->pport_cnt;
-			ser_r->rport_cnt = r->rport_cnt;
-			ser_r->proto = r->proto;
-			ser_r->spool_cnt = r->spool_cnt;
-			len += sizeof(struct cfg_redir_legacy);
-			LIST_FOREACH(s, &r->spool_chain, _next) {
-				ser_s = (struct cfg_spool_legacy *)&data[len];
-				ser_s->addr = s->addr;
-				ser_s->port = s->port;
-				len += sizeof(struct cfg_spool_legacy);
+	for(i = 0; i < chain->nat.len; i++)
+		LIST_FOREACH(n, &chain->nat.tbl[i], _next) {
+			ucfg = (struct cfg_nat_legacy *)&data[len];
+			ucfg->id = n->id;
+			ucfg->ip = n->ip;
+			ucfg->redir_cnt = n->redir_cnt;
+			ucfg->mode = n->mode;
+			strlcpy(ucfg->if_name, n->if_name, sizeof(ucfg->if_name));
+			len += sizeof(struct cfg_nat_legacy);
+			LIST_FOREACH(r, &n->redir_chain, _next) {
+				ser_r = (struct cfg_redir_legacy *)&data[len];
+				ser_r->mode = r->mode;
+				ser_r->laddr = r->laddr;
+				ser_r->paddr = r->paddr;
+				ser_r->raddr = r->raddr;
+				ser_r->lport = r->lport;
+				ser_r->pport = r->pport;
+				ser_r->rport = r->rport;
+				ser_r->pport_cnt = r->pport_cnt;
+				ser_r->rport_cnt = r->rport_cnt;
+				ser_r->proto = r->proto;
+				ser_r->spool_cnt = r->spool_cnt;
+				len += sizeof(struct cfg_redir_legacy);
+				LIST_FOREACH(s, &r->spool_chain, _next) {
+					ser_s = (struct cfg_spool_legacy *)&data[len];
+					ser_s->addr = s->addr;
+					ser_s->port = s->port;
+					len += sizeof(struct cfg_spool_legacy);
+				}
 			}
 		}
-	}
 	IPFW_UH_RUNLOCK(chain);
 
 	error = sooptcopyout(sopt, data, len);
@@ -1102,7 +1110,7 @@
 {
 	uint8_t *data;
 	struct cfg_nat *ptr;
-	int i, size;
+	int i, k, size;
 	struct ip_fw_chain *chain;
 	IPFW_RLOCK_TRACKER;
 
@@ -1111,11 +1119,12 @@
 	IPFW_RLOCK(chain);
 	/* one pass to count, one to copy the data */
 	i = 0;
-	LIST_FOREACH(ptr, &chain->nat, _next) {
-		if (ptr->lib->logDesc == NULL)
-			continue;
-		i++;
-	}
+	for(k = 0; k < chain->nat.len; k++)
+		LIST_FOREACH(ptr, &chain->nat.tbl[k], _next) {
+			if (ptr->lib->logDesc == NULL)
+				continue;
+			i++;
+		}
 	size = i * (LIBALIAS_BUF_SIZE + sizeof(int));
 	data = malloc(size, M_IPFW, M_NOWAIT | M_ZERO);
 	if (data == NULL) {
@@ -1123,14 +1132,15 @@
 		return (ENOSPC);
 	}
 	i = 0;
-	LIST_FOREACH(ptr, &chain->nat, _next) {
-		if (ptr->lib->logDesc == NULL)
-			continue;
-		bcopy(&ptr->id, &data[i], sizeof(int));
-		i += sizeof(int);
-		bcopy(ptr->lib->logDesc, &data[i], LIBALIAS_BUF_SIZE);
-		i += LIBALIAS_BUF_SIZE;
-	}
+	for(k = 0; k < chain->nat.len; k++)
+		LIST_FOREACH(ptr, &chain->nat.tbl[k], _next) {
+			if (ptr->lib->logDesc == NULL)
+				continue;
+			bcopy(&ptr->id, &data[i], sizeof(int));
+			i += sizeof(int);
+			bcopy(ptr->lib->logDesc, &data[i], LIBALIAS_BUF_SIZE);
+			i += LIBALIAS_BUF_SIZE;
+		}
 	IPFW_RUNLOCK(chain);
 	sooptcopyout(sopt, data, size);
 	free(data, M_IPFW);
@@ -1140,8 +1150,19 @@
 static int
 vnet_ipfw_nat_init(const void *arg __unused)
 {
+	struct ip_fw_chain *chain;
+	int i;
 
+	chain = &V_layer3_chain;
+	IPFW_WLOCK(chain);
+	chain->nat.len = fw_nat_hash;
+	chain->nat.tbl = malloc(chain->nat.len * sizeof(*chain->nat.tbl),
+	    M_IPFW, M_NOWAIT | M_ZERO);
+	for(i = 0; i < chain->nat.len; i++) 
+	    LIST_INIT(&chain->nat.tbl[i]);
+
 	V_ipfw_nat_ready = 1;
+	IPFW_WUNLOCK(chain);
 	return (0);
 }
 
@@ -1150,15 +1171,19 @@
 {
 	struct cfg_nat *ptr, *ptr_temp;
 	struct ip_fw_chain *chain;
+	int i;
 
 	chain = &V_layer3_chain;
 	IPFW_WLOCK(chain);
 	V_ipfw_nat_ready = 0;
-	LIST_FOREACH_SAFE(ptr, &chain->nat, _next, ptr_temp) {
-		LIST_REMOVE(ptr, _next);
-		free_nat_instance(ptr);
-	}
+	for(i = 0; i < chain->nat.len; i++)
+		LIST_FOREACH_SAFE(ptr, &chain->nat.tbl[i], _next, ptr_temp) {
+			LIST_REMOVE(ptr, _next);
+			free_nat_instance(ptr);
+		}
 	flush_nat_ptrs(chain, -1 /* flush all */);
+	chain->nat.len = 0;
+	free(chain->nat.tbl, M_IPFW);
 	IPFW_WUNLOCK(chain);
 	return (0);
 }
Index: sys/netpfil/ipfw/ip_fw_private.h
===================================================================
--- sys/netpfil/ipfw/ip_fw_private.h
+++ sys/netpfil/ipfw/ip_fw_private.h
@@ -250,6 +250,8 @@
 VNET_DECLARE(unsigned int, fw_tables_sets);
 #define V_fw_tables_sets	VNET(fw_tables_sets)
 
+extern int fw_nat_hash;
+
 struct tables_config;
 
 #ifdef _KERNEL
@@ -288,6 +290,12 @@
 
 #endif
 
+struct nat_lists {
+	LIST_HEAD(nat_list, cfg_nat) *tbl;       /* table of lists of nat entries */
+	int		len;		/* size of of nat lookup table */
+};
+#define NAT_TABLE_LIST(n,i)	(&((n).tbl[(i)%(n).len]))
+
 struct ip_fw_chain {
 	struct ip_fw	**map;		/* array of rule ptrs to ease lookup */
 	uint32_t	id;		/* ruleset id */
@@ -303,7 +311,7 @@
 #endif
 	int		static_len;	/* total len of static rules (v0) */
 	uint32_t	gencnt;		/* NAT generation count */
-	LIST_HEAD(nat_list, cfg_nat) nat;       /* list of nat entries */
+	struct nat_lists nat;		/* nat entries  */
 	struct ip_fw	*default_rule;
 	struct tables_config *tblcfg;	/* tables module data */
 	void		*ifcfg;		/* interface module data */
@@ -788,7 +796,7 @@
 
 /* In ip_fw_nat.c -- XXX to be moved to ip_var.h */
 
-extern struct cfg_nat *(*lookup_nat_ptr)(struct nat_list *, int);
+extern struct cfg_nat *(*lookup_nat_ptr)(struct nat_lists *, int);
 
 typedef int ipfw_nat_t(struct ip_fw_args *, struct cfg_nat *, struct mbuf *);
 typedef int ipfw_nat_cfg_t(struct sockopt *);