Index: sbin/ipfw/ipfw2.c
===================================================================
--- sbin/ipfw/ipfw2.c
+++ sbin/ipfw/ipfw2.c
@@ -3949,8 +3949,6 @@
 
 	case TOK_NAT:
 		action->opcode = O_NAT;
-		action->len = F_INSN_SIZE(ipfw_insn_nat);
-		CHECK_ACTLEN;
 		if (*av != NULL && _substrcmp(*av, "global") == 0) {
 			action->arg1 = IP_FW_NAT44_GLOBAL;
 			av++;
Index: sys/netpfil/ipfw/ip_fw2.c
===================================================================
--- sys/netpfil/ipfw/ip_fw2.c
+++ sys/netpfil/ipfw/ip_fw2.c
@@ -180,7 +180,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_priv *, uint16_t);
 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;
@@ -3151,17 +3151,14 @@
 					retval = ipfw_nat_ptr(args, NULL, m);
 					break;
 				}
-				t = ((ipfw_insn_nat *)cmd)->nat;
-				if (t == NULL) {
-					nat_id = TARG(cmd->arg1, nat);
-					t = (*lookup_nat_ptr)(&chain->nat, nat_id);
+				nat_id = TARG(cmd->arg1, nat);
+				IPFW_UH_RLOCK(chain);
+				t = (*lookup_nat_ptr)(chain->nat, nat_id);
+				IPFW_UH_RUNLOCK(chain);
 
-					if (t == NULL) {
-					    retval = IP_FW_DENY;
-					    break;
-					}
-					if (cmd->arg1 != IP_FW_TARG)
-					    ((ipfw_insn_nat *)cmd)->nat = t;
+				if (t == NULL) {
+				    retval = IP_FW_DENY;
+				    break;
 				}
 				retval = ipfw_nat_ptr(args, t, m);
 				break;
@@ -3418,9 +3415,6 @@
 #ifdef IPFIREWALL_VERBOSE_LIMIT
 	V_verbose_limit = IPFIREWALL_VERBOSE_LIMIT;
 #endif
-#ifdef IPFIREWALL_NAT
-	LIST_INIT(&chain->nat);
-#endif
 
 	/* Init shared services hash table */
 	ipfw_init_srv(chain);
Index: sys/netpfil/ipfw/ip_fw_nat.c
===================================================================
--- sys/netpfil/ipfw/ip_fw_nat.c
+++ sys/netpfil/ipfw/ip_fw_nat.c
@@ -75,7 +75,7 @@
 	uint16_t		rport;	/* remote port	*/
 	uint16_t		pport_cnt;	/* number of public ports */
 	uint16_t		rport_cnt;	/* number of remote ports */
-	struct alias_link	**alink;	
+	struct alias_link	**alink;
 	u_int16_t		spool_cnt; /* num of entry in spool chain */
 	/* chain of spool instances */
 	LIST_HEAD(spool_chain, cfg_spool) spool_chain;
@@ -85,18 +85,26 @@
 struct cfg_nat {
 	/* chain of nat instances */
 	LIST_ENTRY(cfg_nat)	_next;
-	int			id;		/* nat id  */
+	uint16_t		id;		/* nat id  */
 	struct in_addr		ip;		/* nat ip address */
 	struct libalias		*lib;		/* libalias instance */
 	int			mode;		/* aliasing mode */
 	int			redir_cnt; /* number of entry in spool chain */
 	/* chain of redir instances */
-	LIST_HEAD(redir_chain, cfg_redir) redir_chain;  
+	LIST_HEAD(redir_chain, cfg_redir) redir_chain;
 	char			if_name[IF_NAMESIZE];	/* interface name */
 	u_short			alias_port_lo;	/* low range for port aliasing */
 	u_short			alias_port_hi;	/* high range for port aliasing */
 };
 
+/* Nat management. */
+struct nat_priv {
+	LIST_HEAD(cfg_list, cfg_nat) list; /* table of lists of nat entries */
+	struct cfg_nat	**idxmap;	/* map id to instance */
+	uint16_t	idxsize;	/* size of of nat lookup table */
+	uint32_t	gencnt;		/* NAT configuration change count */
+};
+
 static eventhandler_tag ifaddr_event_tag;
 
 static void
@@ -115,7 +123,7 @@
 	chain = &V_layer3_chain;
 	IPFW_UH_WLOCK(chain);
 	/* Check every nat entry... */
-	LIST_FOREACH(ptr, &chain->nat, _next) {
+	LIST_FOREACH(ptr, &chain->nat->list, _next) {
 		struct epoch_tracker et;
 
 		/* ...using nic 'ifp->if_xname' as dynamic alias address. */
@@ -138,24 +146,6 @@
 	IPFW_UH_WUNLOCK(chain);
 }
 
-/*
- * delete the pointers for nat entry ix, or all of them if ix < 0
- */
-static void
-flush_nat_ptrs(struct ip_fw_chain *chain, const int ix)
-{
-	ipfw_insn_nat *cmd;
-	int i;
-
-	IPFW_WLOCK_ASSERT(chain);
-	for (i = 0; i < chain->n_rules; i++) {
-		cmd = (ipfw_insn_nat *)ipfw_get_action(chain->map[i]);
-		if (cmd->o.opcode == O_NAT && cmd->nat != NULL &&
-			    (ix < 0 || cmd->nat->id == ix))
-			cmd->nat = NULL;
-	}
-}
-
 static void
 del_redir_spool_cfg(struct cfg_nat *n, struct redir_chain *head)
 {
@@ -360,7 +350,7 @@
 		chain = &V_layer3_chain;
 		IPFW_RLOCK_ASSERT(chain);
 		/* Check every nat entry... */
-		LIST_FOREACH(t, &chain->nat, _next) {
+		LIST_FOREACH(t, &chain->nat->list, _next) {
 			if ((t->mode & PKT_ALIAS_SKIP_GLOBAL) != 0)
 				continue;
 			retval = LibAliasOutTry(t->lib, c,
@@ -461,60 +451,78 @@
 }
 
 static struct cfg_nat *
-lookup_nat(struct nat_list *l, int nat_id)
+lookup_nat(struct nat_priv *l, uint16_t nat_id)
 {
-	struct cfg_nat *res;
+	IPFW_UH_LOCK_ASSERT(&V_layer3_chain);
+	if (nat_id > l->idxsize || nat_id == 0)
+		return NULL;
 
-	LIST_FOREACH(res, l, _next) {
-		if (res->id == nat_id)
-			break;
-	}
-	return res;
+	return l->idxmap[nat_id-1];
 }
 
-static struct cfg_nat *
-lookup_nat_name(struct nat_list *l, char *name)
+static uint16_t
+validate_nat_name(char *name)
 {
-	struct cfg_nat *res;
 	int id;
 	char *errptr;
 
 	id = strtol(name, &errptr, 10);
-	if (id == 0 || *errptr != '\0')
+	if (id <= 0 || id >= 65535 || *errptr != '\0')
+		return 0;
+
+	return id;
+}
+
+static struct cfg_nat *
+lookup_nat_name(struct nat_priv *l, char *name)
+{
+	uint16_t id;
+
+	id = validate_nat_name(name);
+	if (id == 0)
 		return (NULL);
 
-	LIST_FOREACH(res, l, _next) {
-		if (res->id == id)
-			break;
-	}
-	return (res);
+	return lookup_nat(l, id);
 }
 
 /* IP_FW3 configuration routines */
 
 static void
-nat44_config(struct ip_fw_chain *chain, struct nat44_cfg_nat *ucfg)
+nat44_config(struct ip_fw_chain *chain, struct nat44_cfg_nat *ucfg, uint16_t id)
 {
-	struct cfg_nat *ptr, *tcfg;
-	int gencnt;
+	struct cfg_nat *ptr, *tcfg, **tmap;
+	int gencnt, resize_to;
+
+	tmap = NULL;
+	resize_to = 0;
 
 	/*
 	 * Find/create nat rule.
 	 */
 	IPFW_UH_WLOCK(chain);
-	gencnt = chain->gencnt;
-	ptr = lookup_nat_name(&chain->nat, ucfg->name);
+	gencnt = chain->nat->gencnt;
+	ptr = lookup_nat(chain->nat, id);
 	if (ptr == NULL) {
+		/* enough space to add entry? Test as long as we have the lock */
+		if (id > chain->nat->idxsize)
+			resize_to = id;
 		IPFW_UH_WUNLOCK(chain);
+
 		/* New rule: allocate and init new instance. */
 		ptr = malloc(sizeof(struct cfg_nat), M_IPFW, M_WAITOK | M_ZERO);
+		ptr->id = id;
 		ptr->lib = LibAliasInit(NULL);
 		LIST_INIT(&ptr->redir_chain);
+
+		/* allocate new table without lockw, syscall can block */
+		if (resize_to)
+			tmap = malloc(resize_to * sizeof(*tmap),
+			    M_IPFW, M_WAITOK | M_ZERO);
 	} else {
 		/* Entry already present: temporarily unhook it. */
 		IPFW_WLOCK(chain);
 		LIST_REMOVE(ptr, _next);
-		flush_nat_ptrs(chain, ptr->id);
+		chain->nat->idxmap[ptr->id - 1] = NULL;
 		IPFW_WUNLOCK(chain);
 		IPFW_UH_WUNLOCK(chain);
 	}
@@ -522,7 +530,6 @@
 	/*
 	 * Basic nat (re)configuration.
 	 */
-	ptr->id = strtol(ucfg->name, NULL, 10);
 	/*
 	 * XXX - what if this rule doesn't nat any ip and just
 	 * redirect?
@@ -545,23 +552,48 @@
 	del_redir_spool_cfg(ptr, &ptr->redir_chain);
 	/* Add new entries. */
 	add_redir_spool_cfg((char *)(ucfg + 1), ptr);
+
 	IPFW_UH_WLOCK(chain);
 
 	/* Extra check to avoid race with another ipfw_nat_cfg() */
 	tcfg = NULL;
-	if (gencnt != chain->gencnt)
-	    tcfg = lookup_nat_name(&chain->nat, ucfg->name);
+	if (gencnt != chain->nat->gencnt)
+		tcfg = lookup_nat(chain->nat, id);
+
 	IPFW_WLOCK(chain);
+	/* (our) latest config wins */
 	if (tcfg != NULL)
 		LIST_REMOVE(tcfg, _next);
-	LIST_INSERT_HEAD(&chain->nat, ptr, _next);
+
+	/* ensure a large enough idxmap */
+	if (resize_to > chain->nat->idxsize) {
+		struct cfg_nat *known, **swap;
+
+		/* rebuild (usually) sparse map from list */
+		LIST_FOREACH(known, &chain->nat->list, _next)
+		    tmap[known->id - 1] = known;
+		/* swap pointers, free old later */
+		swap = chain->nat->idxmap;
+		chain->nat->idxmap = tmap;
+		tmap = swap;
+		/* new array in place */
+		chain->nat->idxsize = resize_to;
+	}
+
+	/* add new element */
+	LIST_INSERT_HEAD(&chain->nat->list, ptr, _next);
+	chain->nat->idxmap[ptr->id - 1] = ptr;
 	IPFW_WUNLOCK(chain);
-	chain->gencnt++;
 
+	/* inform other, that something changed */
+	chain->nat->gencnt++;
 	IPFW_UH_WUNLOCK(chain);
 
 	if (tcfg != NULL)
 		free_nat_instance(ptr);
+
+	if (tmap != NULL)
+		free(tmap, M_IPFW);
 }
 
 /*
@@ -577,9 +609,8 @@
 {
 	ipfw_obj_header *oh;
 	struct nat44_cfg_nat *ucfg;
-	int id;
+	uint16_t id;
 	size_t read;
-	char *errptr;
 
 	/* Check minimum header size */
 	if (sd->valsize < (sizeof(*oh) + sizeof(*ucfg)))
@@ -594,10 +625,8 @@
 	ucfg = (struct nat44_cfg_nat *)(oh + 1);
 
 	/* Check if name is properly terminated and looks like number */
-	if (strnlen(ucfg->name, sizeof(ucfg->name)) == sizeof(ucfg->name))
-		return (EINVAL);
-	id = strtol(ucfg->name, &errptr, 10);
-	if (id == 0 || *errptr != '\0')
+	id = validate_nat_name(ucfg->name);
+	if(id == 0)
 		return (EINVAL);
 
 	read = sizeof(*oh) + sizeof(*ucfg);
@@ -605,7 +634,7 @@
 	if (sd->valsize < read + ucfg->redir_cnt*sizeof(struct nat44_cfg_redir))
 		return (EINVAL);
 
-	nat44_config(chain, ucfg);
+	nat44_config(chain, ucfg, id);
 	return (0);
 }
 
@@ -640,14 +669,14 @@
 		return (EINVAL);
 
 	IPFW_UH_WLOCK(chain);
-	ptr = lookup_nat_name(&chain->nat, ntlv->name);
+	ptr = lookup_nat_name(chain->nat, ntlv->name);
 	if (ptr == NULL) {
 		IPFW_UH_WUNLOCK(chain);
 		return (ESRCH);
 	}
 	IPFW_WLOCK(chain);
 	LIST_REMOVE(ptr, _next);
-	flush_nat_ptrs(chain, ptr->id);
+	chain->nat->idxmap[ptr->id - 1] = NULL;
 	IPFW_WUNLOCK(chain);
 	IPFW_UH_WUNLOCK(chain);
 
@@ -707,7 +736,7 @@
 		return (EINVAL);
 
 	IPFW_UH_RLOCK(chain);
-	ptr = lookup_nat_name(&chain->nat, ucfg->name);
+	ptr = lookup_nat_name(chain->nat, ucfg->name);
 	if (ptr == NULL) {
 		IPFW_UH_RUNLOCK(chain);
 		return (ESRCH);
@@ -789,7 +818,7 @@
 	olh = (ipfw_obj_lheader *)ipfw_get_sopt_header(sd, sizeof(*olh));
 	IPFW_UH_RLOCK(chain);
 	nat_count = 0;
-	LIST_FOREACH(ptr, &chain->nat, _next)
+	LIST_FOREACH(ptr, &chain->nat->list, _next)
 		nat_count++;
 
 	olh->count = nat_count;
@@ -801,7 +830,7 @@
 		return (ENOMEM);
 	}
 
-	LIST_FOREACH(ptr, &chain->nat, _next) {
+	LIST_FOREACH(ptr, &chain->nat->list, _next) {
 		ucfg = (struct nat44_cfg_nat *)ipfw_get_sopt_space(sd,
 		    sizeof(*ucfg));
 		export_nat_cfg(ptr, ucfg);
@@ -848,7 +877,7 @@
 		return (EINVAL);
 
 	IPFW_UH_RLOCK(chain);
-	ptr = lookup_nat_name(&chain->nat, ucfg->name);
+	ptr = lookup_nat_name(chain->nat, ucfg->name);
 	if (ptr == NULL) {
 		IPFW_UH_RUNLOCK(chain);
 		return (ESRCH);
@@ -989,7 +1018,7 @@
 		rdir++;
 	}
 
-	nat44_config(&V_layer3_chain, ucfg);
+	nat44_config(&V_layer3_chain, ucfg, cfg->id);
 
 out:
 	free(buf, M_TEMP);
@@ -1006,14 +1035,14 @@
 	sooptcopyin(sopt, &i, sizeof i, sizeof i);
 	/* XXX validate i */
 	IPFW_UH_WLOCK(chain);
-	ptr = lookup_nat(&chain->nat, i);
+	ptr = lookup_nat(chain->nat, i);
 	if (ptr == NULL) {
 		IPFW_UH_WUNLOCK(chain);
 		return (EINVAL);
 	}
 	IPFW_WLOCK(chain);
 	LIST_REMOVE(ptr, _next);
-	flush_nat_ptrs(chain, i);
+	chain->nat->idxmap[i - 1] = NULL;
 	IPFW_WUNLOCK(chain);
 	IPFW_UH_WUNLOCK(chain);
 	free_nat_instance(ptr);
@@ -1038,9 +1067,9 @@
 
 	IPFW_UH_RLOCK(chain);
 retry:
-	gencnt = chain->gencnt;
+	gencnt = chain->nat->gencnt;
 	/* Estimate memory amount */
-	LIST_FOREACH(n, &chain->nat, _next) {
+	LIST_FOREACH(n, &chain->nat->list, _next) {
 		nat_cnt++;
 		len += sizeof(struct cfg_nat_legacy);
 		LIST_FOREACH(r, &n->redir_chain, _next) {
@@ -1058,12 +1087,12 @@
 	len = sizeof(nat_cnt);
 
 	IPFW_UH_RLOCK(chain);
-	if (gencnt != chain->gencnt) {
+	if (gencnt != chain->nat->gencnt) {
 		free(data, M_TEMP);
 		goto retry;
 	}
 	/* Serialize all the data. */
-	LIST_FOREACH(n, &chain->nat, _next) {
+	LIST_FOREACH(n, &chain->nat->list, _next) {
 		ucfg = (struct cfg_nat_legacy *)&data[len];
 		ucfg->id = n->id;
 		ucfg->ip = n->ip;
@@ -1115,7 +1144,7 @@
 	IPFW_RLOCK(chain);
 	/* one pass to count, one to copy the data */
 	i = 0;
-	LIST_FOREACH(ptr, &chain->nat, _next) {
+	LIST_FOREACH(ptr, &chain->nat->list, _next) {
 		if (ptr->lib->logDesc == NULL)
 			continue;
 		i++;
@@ -1127,7 +1156,7 @@
 		return (ENOSPC);
 	}
 	i = 0;
-	LIST_FOREACH(ptr, &chain->nat, _next) {
+	LIST_FOREACH(ptr, &chain->nat->list, _next) {
 		if (ptr->lib->logDesc == NULL)
 			continue;
 		bcopy(&ptr->id, &data[i], sizeof(int));
@@ -1144,9 +1173,32 @@
 static int
 vnet_ipfw_nat_init(const void *arg __unused)
 {
+	struct nat_priv * priv;
+	struct ip_fw_chain *chain;
+	int err;
 
-	V_ipfw_nat_ready = 1;
-	return (0);
+	priv = malloc(sizeof(*priv), M_IPFW, M_WAITOK | M_ZERO);
+	priv->idxmap = malloc(sizeof(*(priv->idxmap)), M_IPFW, M_WAITOK | M_ZERO);
+	priv->idxsize = 1;
+	LIST_INIT(&priv->list);
+
+	chain = &V_layer3_chain;
+	err = 0;
+
+	IPFW_WLOCK(chain);
+	if(chain->nat != NULL)
+		err = 1;
+	else
+		chain->nat = priv;
+	IPFW_WUNLOCK(chain);
+
+	if(err) {
+		free(priv->idxmap, M_IPFW);
+		free(priv, M_IPFW);
+	} else
+		V_ipfw_nat_ready = 1;
+
+	return (err);
 }
 
 static int
@@ -1158,11 +1210,13 @@
 	chain = &V_layer3_chain;
 	IPFW_WLOCK(chain);
 	V_ipfw_nat_ready = 0;
-	LIST_FOREACH_SAFE(ptr, &chain->nat, _next, ptr_temp) {
+	LIST_FOREACH_SAFE(ptr, &chain->nat->list, _next, ptr_temp) {
 		LIST_REMOVE(ptr, _next);
 		free_nat_instance(ptr);
 	}
-	flush_nat_ptrs(chain, -1 /* flush all */);
+	free(chain->nat->idxmap, M_IPFW);
+	free(chain->nat, M_IPFW);
+	chain->nat = NULL;
 	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
@@ -249,6 +249,7 @@
 VNET_DECLARE(unsigned int, fw_tables_sets);
 #define V_fw_tables_sets	VNET(fw_tables_sets)
 
+struct nat_priv;
 struct tables_config;
 
 #ifdef _KERNEL
@@ -301,8 +302,7 @@
 	struct rmlock	rwmtx;
 #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_priv	*nat;		/* nat instances */
 	struct ip_fw	*default_rule;
 	struct tables_config *tblcfg;	/* tables module data */
 	void		*ifcfg;		/* interface module data */
@@ -426,6 +426,7 @@
 	rw_destroy(&(_chain)->uh_lock);			\
 	} while (0)
 
+#define	IPFW_LOCK_ASSERT(_chain)	rw_assert(&(_chain)->rwmtx, RA_LOCKED)
 #define	IPFW_RLOCK_ASSERT(_chain)	rw_assert(&(_chain)->rwmtx, RA_RLOCKED)
 #define	IPFW_WLOCK_ASSERT(_chain)	rw_assert(&(_chain)->rwmtx, RA_WLOCKED)
 
@@ -447,6 +448,7 @@
 	rw_destroy(&(_chain)->uh_lock);			\
 	} while (0)
 
+#define	IPFW_LOCK_ASSERT(_chain)	rm_assert(&(_chain)->rwmtx, RA_LOCKED)
 #define	IPFW_RLOCK_ASSERT(_chain)	rm_assert(&(_chain)->rwmtx, RA_RLOCKED)
 #define	IPFW_WLOCK_ASSERT(_chain)	rm_assert(&(_chain)->rwmtx, RA_WLOCKED)
 
@@ -459,6 +461,7 @@
 #define	IPFW_PF_RUNLOCK(p)		IPFW_RUNLOCK(p)
 #endif
 
+#define	IPFW_UH_LOCK_ASSERT(_chain)	rw_assert(&(_chain)->uh_lock, RA_LOCKED)
 #define	IPFW_UH_RLOCK_ASSERT(_chain)	rw_assert(&(_chain)->uh_lock, RA_RLOCKED)
 #define	IPFW_UH_WLOCK_ASSERT(_chain)	rw_assert(&(_chain)->uh_lock, RA_WLOCKED)
 #define	IPFW_UH_UNLOCK_ASSERT(_chain)	rw_assert(&(_chain)->uh_lock, RA_UNLOCKED)
@@ -785,7 +788,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_priv *, uint16_t);
 
 typedef int ipfw_nat_t(struct ip_fw_args *, struct cfg_nat *, struct mbuf *);
 typedef int ipfw_nat_cfg_t(struct sockopt *);
Index: sys/netpfil/ipfw/ip_fw_sockopt.c
===================================================================
--- sys/netpfil/ipfw/ip_fw_sockopt.c
+++ sys/netpfil/ipfw/ip_fw_sockopt.c
@@ -1993,9 +1993,10 @@
 		case O_NAT:
 			if (!IPFW_NAT_LOADED)
 				return EINVAL;
-			if (cmdlen != F_INSN_SIZE(ipfw_insn_nat))
- 				goto bad_size;		
- 			goto check_action;
+			/* temporary allow old ipfw binaries to send larger commands */
+			if (cmdlen < F_INSN_SIZE(ipfw_insn))
+				goto bad_size;
+			goto check_action;
 		case O_CHECK_STATE:
 			ci->object_opcodes++;
 			/* FALLTHROUGH */