Index: sbin/ipfw/ipfw2.c
===================================================================
--- sbin/ipfw/ipfw2.c
+++ sbin/ipfw/ipfw2.c
@@ -3934,8 +3934,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/netinet/ip_fw.h
===================================================================
--- sys/netinet/ip_fw.h
+++ sys/netinet/ip_fw.h
@@ -552,12 +552,6 @@
 	uint32_t	redir_cnt;	/* number of entry in spool chain */
 };
 
-/* Nat command. */
-typedef struct	_ipfw_insn_nat {
- 	ipfw_insn	o;
- 	struct cfg_nat *nat;
-} ipfw_insn_nat;
-
 /* Apply ipv6 mask on ipv6 addr */
 #define APPLY_MASK(addr,mask)	do {					\
     (addr)->__u6_addr.__u6_addr32[0] &= (mask)->__u6_addr.__u6_addr32[0]; \
Index: sys/netpfil/ipfw/ip_fw2.c
===================================================================
--- sys/netpfil/ipfw/ip_fw2.c
+++ sys/netpfil/ipfw/ip_fw2.c
@@ -3095,7 +3095,7 @@
 				 * Ensure that we do not invoke NAT handler for
 				 * non IPv4 packets. Libalias expects only IPv4.
 				 */
-				if (!is_ipv4 || !IPFW_NAT_LOADED) {
+				if (!is_ipv4 || chain->nat == NULL) {
 				    retval = IP_FW_DENY;
 				    break;
 				}
@@ -3110,17 +3110,12 @@
 					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);
+				t = (*lookup_nat_ptr)(chain->nat, nat_id);
 
-					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;
@@ -3369,9 +3364,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
@@ -95,6 +95,14 @@
 	char			if_name[IF_NAMESIZE];	/* interface name */
 };
 
+/* Nat managment. */
+struct nat_list {
+	LIST_HEAD(cfg_all, cfg_nat) all; /* table of lists of nat entries */
+	struct cfg_nat	**byid;		/* map id to instance */
+	int		size;		/* size of of nat lookup table */
+	uint32_t	gencnt;		/* NAT configuration change count */
+};
+
 static eventhandler_tag ifaddr_event_tag;
 
 static void
@@ -113,7 +121,7 @@
 	chain = &V_layer3_chain;
 	IPFW_UH_WLOCK(chain);
 	/* Check every nat entry... */
-	LIST_FOREACH(ptr, &chain->nat, _next) {
+	LIST_FOREACH(ptr, &chain->nat->all, _next) {
 		struct epoch_tracker et;
 
 		/* ...using nic 'ifp->if_xname' as dynamic alias address. */
@@ -136,25 +144,7 @@
 	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)
 {
 	struct cfg_redir *r, *tmp_r;
@@ -358,7 +348,7 @@
 		chain = &V_layer3_chain;
 		IPFW_RLOCK_ASSERT(chain);
 		/* Check every nat entry... */
-		LIST_FOREACH(t, &chain->nat, _next) {
+		LIST_FOREACH(t, &chain->nat->all, _next) {
 			if ((t->mode & PKT_ALIAS_SKIP_GLOBAL) != 0)
 				continue;
 			retval = LibAliasOutTry(t->lib, c,
@@ -461,19 +451,15 @@
 static struct cfg_nat *
 lookup_nat(struct nat_list *l, int nat_id)
 {
-	struct cfg_nat *res;
+	if (nat_id >= l->size)
+		return NULL;
 
-	LIST_FOREACH(res, l, _next) {
-		if (res->id == nat_id)
-			break;
-	}
-	return res;
+	return l->byid[nat_id];
 }
 
 static struct cfg_nat *
 lookup_nat_name(struct nat_list *l, char *name)
 {
-	struct cfg_nat *res;
 	int id;
 	char *errptr;
 
@@ -481,11 +467,7 @@
 	if (id == 0 || *errptr != '\0')
 		return (NULL);
 
-	LIST_FOREACH(res, l, _next) {
-		if (res->id == id)
-			break;
-	}
-	return (res);
+	return lookup_nat(l, id);
 }
 
 /* IP_FW3 configuration routines */
@@ -500,8 +482,8 @@
 	 * 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_name(chain->nat, ucfg->name);
 	if (ptr == NULL) {
 		IPFW_UH_WUNLOCK(chain);
 		/* New rule: allocate and init new instance. */
@@ -512,7 +494,7 @@
 		/* Entry already present: temporarily unhook it. */
 		IPFW_WLOCK(chain);
 		LIST_REMOVE(ptr, _next);
-		flush_nat_ptrs(chain, ptr->id);
+		chain->nat->byid[ptr->id] = NULL;
 		IPFW_WUNLOCK(chain);
 		IPFW_UH_WUNLOCK(chain);
 	}
@@ -544,14 +526,23 @@
 
 	/* 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_name(chain->nat, ucfg->name);
 	IPFW_WLOCK(chain);
 	if (tcfg != NULL)
 		LIST_REMOVE(tcfg, _next);
-	LIST_INSERT_HEAD(&chain->nat, ptr, _next);
+	LIST_INSERT_HEAD(&chain->nat->all, ptr, _next);
+	if (ptr->id >= chain->nat->size) {
+		chain->nat->size = ptr->id + 1;
+		chain->nat->byid = realloc(chain->nat->byid,
+		    chain->nat->size * sizeof(chain->nat->byid[0]),
+		    M_IPFW, M_WAITOK);
+		KASSERT(chain->nat->byid != NULL,
+		    ("Out of memory allocating NAT entry %d\n", ptr->id));
+	}
+	chain->nat->byid[ptr->id] = ptr;
 	IPFW_WUNLOCK(chain);
-	chain->gencnt++;
+	chain->nat->gencnt++;
 
 	IPFW_UH_WUNLOCK(chain);
 
@@ -635,14 +626,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->byid[ptr->id] = NULL;
 	IPFW_WUNLOCK(chain);
 	IPFW_UH_WUNLOCK(chain);
 
@@ -700,7 +691,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);
@@ -783,7 +774,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->all, _next)
 		nat_count++;
 
 	olh->count = nat_count;
@@ -795,7 +786,7 @@
 		return (ENOMEM);
 	}
 
-	LIST_FOREACH(ptr, &chain->nat, _next) {
+	LIST_FOREACH(ptr, &chain->nat->all, _next) {
 		ucfg = (struct nat44_cfg_nat *)ipfw_get_sopt_space(sd,
 		    sizeof(*ucfg));
 		export_nat_cfg(ptr, ucfg);
@@ -842,7 +833,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);
@@ -1002,14 +993,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->byid[i] = NULL;
 	IPFW_WUNLOCK(chain);
 	IPFW_UH_WUNLOCK(chain);
 	free_nat_instance(ptr);
@@ -1034,9 +1025,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->all, _next) {
 		nat_cnt++;
 		len += sizeof(struct cfg_nat_legacy);
 		LIST_FOREACH(r, &n->redir_chain, _next) {
@@ -1054,12 +1045,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->all, _next) {
 		ucfg = (struct cfg_nat_legacy *)&data[len];
 		ucfg->id = n->id;
 		ucfg->ip = n->ip;
@@ -1111,7 +1102,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->all, _next) {
 		if (ptr->lib->logDesc == NULL)
 			continue;
 		i++;
@@ -1123,7 +1114,7 @@
 		return (ENOSPC);
 	}
 	i = 0;
-	LIST_FOREACH(ptr, &chain->nat, _next) {
+	LIST_FOREACH(ptr, &chain->nat->all, _next) {
 		if (ptr->lib->logDesc == NULL)
 			continue;
 		bcopy(&ptr->id, &data[i], sizeof(int));
@@ -1142,6 +1133,16 @@
 {
 
 	V_ipfw_nat_ready = 1;
+	struct ip_fw_chain *chain;
+
+	chain = &V_layer3_chain;
+	IPFW_WLOCK(chain);
+	chain->nat = malloc(sizeof(*(chain->nat)), M_IPFW, M_WAITOK | M_ZERO);
+	chain->nat->byid = malloc(sizeof(*(chain->nat->byid)),
+	    M_IPFW, M_WAITOK | M_ZERO);
+	chain->nat->size = 1;
+	LIST_INIT(&chain->nat->all);
+	IPFW_WUNLOCK(chain);
 	return (0);
 }
 
@@ -1154,11 +1155,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->all, _next, ptr_temp) {
 		LIST_REMOVE(ptr, _next);
 		free_nat_instance(ptr);
 	}
-	flush_nat_ptrs(chain, -1 /* flush all */);
+	free(chain->nat->byid, 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
@@ -302,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_list	*nat;		/* nat instances */
 	struct ip_fw	*default_rule;
 	struct tables_config *tblcfg;	/* tables module data */
 	void		*ifcfg;		/* interface module data */
Index: sys/netpfil/ipfw/ip_fw_sockopt.c
===================================================================
--- sys/netpfil/ipfw/ip_fw_sockopt.c
+++ sys/netpfil/ipfw/ip_fw_sockopt.c
@@ -2002,9 +2002,8 @@
 		case O_NAT:
 			if (!IPFW_NAT_LOADED)
 				return EINVAL;
-			if (cmdlen != F_INSN_SIZE(ipfw_insn_nat))
- 				goto bad_size;		
- 			goto check_action;
+			else
+				goto check_size;
 		case O_CHECK_STATE:
 			ci->object_opcodes++;
 			/* FALLTHROUGH */