diff --git a/sys/netpfil/ipfw/ip_fw2.c b/sys/netpfil/ipfw/ip_fw2.c
--- a/sys/netpfil/ipfw/ip_fw2.c
+++ b/sys/netpfil/ipfw/ip_fw2.c
@@ -144,14 +144,14 @@
 /* Use 128 tables by default */
 static unsigned int default_fw_tables = IPFW_TABLES_DEFAULT;
 
+static int jump_lookup_pos(struct ip_fw_chain *chain, struct ip_fw *f, int num,
+    int tablearg, int jump_backwards);
 #ifndef LINEAR_SKIPTO
-static int jump_fast(struct ip_fw_chain *chain, struct ip_fw *f, int num,
+static int jump_cached(struct ip_fw_chain *chain, struct ip_fw *f, int num,
     int tablearg, int jump_backwards);
-#define	JUMP(ch, f, num, targ, back)	jump_fast(ch, f, num, targ, back)
+#define	JUMP(ch, f, num, targ, back)	jump_cached(ch, f, num, targ, back)
 #else
-static int jump_linear(struct ip_fw_chain *chain, struct ip_fw *f, int num,
-    int tablearg, int jump_backwards);
-#define	JUMP(ch, f, num, targ, back)	jump_linear(ch, f, num, targ, back)
+#define	JUMP(ch, f, num, targ, back)	jump_lookup_pos(ch, f, num, targ, back)
 #endif
 
 /*
@@ -1227,56 +1227,79 @@
 	args->flags |= IPFW_ARGS_REF;
 }
 
-#ifndef LINEAR_SKIPTO
-/*
- * Helper function to enable cached rule lookups using
- * cached_id and cached_pos fields in ipfw rule.
- */
 static int
-jump_fast(struct ip_fw_chain *chain, struct ip_fw *f, int num,
+jump_lookup_pos(struct ip_fw_chain *chain, struct ip_fw *f, int num,
     int tablearg, int jump_backwards)
 {
-	int f_pos;
+	int f_pos, i;
 
-	/* If possible use cached f_pos (in f->cached_pos),
-	 * whose version is written in f->cached_id
-	 * (horrible hacks to avoid changing the ABI).
-	 */
-	if (num != IP_FW_TARG && f->cached_id == chain->id)
-		f_pos = f->cached_pos;
-	else {
-		int i = IP_FW_ARG_TABLEARG(chain, num, skipto);
-		/* make sure we do not jump backward */
-		if (jump_backwards == 0 && i <= f->rulenum)
-			i = f->rulenum + 1;
-		if (chain->idxmap != NULL)
-			f_pos = chain->idxmap[i];
-		else
-			f_pos = ipfw_find_rule(chain, i, 0);
-		/* update the cache */
-		if (num != IP_FW_TARG) {
-			f->cached_id = chain->id;
-			f->cached_pos = f_pos;
-		}
-	}
+	i = IP_FW_ARG_TABLEARG(chain, num, skipto);
+	/* make sure we do not jump backward */
+	if (jump_backwards == 0 && i <= f->rulenum)
+		i = f->rulenum + 1;
+
+#ifndef LINEAR_SKIPTO
+	if (chain->idxmap != NULL)
+		f_pos = chain->idxmap[i];
+	else
+		f_pos = ipfw_find_rule(chain, i, 0);
+#else
+	f_pos = chain->idxmap[i];
+#endif
 
 	return (f_pos);
 }
-#else
+
+
+#ifndef LINEAR_SKIPTO
 /*
- * Helper function to enable real fast rule lookups.
+ * Helper function to enable cached rule lookups using
+ * cache.id and cache.pos fields in ipfw rule.
  */
 static int
-jump_linear(struct ip_fw_chain *chain, struct ip_fw *f, int num,
+jump_cached(struct ip_fw_chain *chain, struct ip_fw *f, int num,
     int tablearg, int jump_backwards)
 {
 	int f_pos;
 
-	num = IP_FW_ARG_TABLEARG(chain, num, skipto);
-	/* make sure we do not jump backward */
-	if (jump_backwards == 0 && num <= f->rulenum)
-		num = f->rulenum + 1;
-	f_pos = chain->idxmap[num];
+	/* Can't use cache with IP_FW_TARG */
+	if (num == IP_FW_TARG)
+		return jump_lookup_pos(chain, f, num, tablearg, jump_backwards);
+
+	/* If possible use cached f_pos (in f->cache.pos),
+	 * whose version is written in f->cache.id
+	 * (horrible hacks to avoid changing the ABI).
+	 *
+	 * Multiple threads can execute the same rule simultaneously,
+	 * we need to ensure that cache.pos is updated before cache.id.
+	 */
+
+#ifdef __LP64__
+	struct ip_fw_jump_cache cache;
+
+	cache.raw_value = f->cache.raw_value;
+	if (cache.id == chain->id)
+		return (cache.pos);
+
+	f_pos = jump_lookup_pos(chain, f, num, tablearg, jump_backwards);
+
+	cache.pos = f_pos;
+	cache.id = chain->id;
+	f->cache.raw_value = cache.raw_value;
+#else
+	if (f->cache.id == chain->id) {
+		/* Load pos after id */
+		atomic_thread_fence_acq();
+		return (f->cache.pos);
+	}
+
+	f_pos = jump_lookup_pos(chain, f, num, tablearg, jump_backwards);
+
+	f->cache.pos = f_pos;
+	/* Store id after pos */
+	atomic_thread_fence_rel();
+	f->cache.id = chain->id;
+#endif
 
 	return (f_pos);
 }
diff --git a/sys/netpfil/ipfw/ip_fw_private.h b/sys/netpfil/ipfw/ip_fw_private.h
--- a/sys/netpfil/ipfw/ip_fw_private.h
+++ b/sys/netpfil/ipfw/ip_fw_private.h
@@ -265,6 +265,15 @@
  *  ACTION_PTR(r)	is the start of the first action (things to do
  *			once a rule matched).
  */
+struct ip_fw_jump_cache {
+	union {
+		struct {
+			uint32_t	id;
+			uint32_t	pos;
+		};
+		uint64_t	raw_value;
+	};
+};
 
 struct ip_fw {
 	uint16_t	act_ofs;	/* offset of action in 32-bit units */
@@ -273,10 +282,9 @@
 	uint8_t		set;		/* rule set (0..31)		*/
 	uint8_t		flags;		/* currently unused		*/
 	counter_u64_t	cntr;		/* Pointer to rule counters	*/
+	struct ip_fw_jump_cache	cache;	/* used by jump_fast            */
 	uint32_t	timestamp;	/* tv_sec of last match		*/
 	uint32_t	id;		/* rule id			*/
-	uint32_t	cached_id;	/* used by jump_fast		*/
-	uint32_t	cached_pos;	/* used by jump_fast		*/
 	uint32_t	refcnt;		/* number of references		*/
 
 	struct ip_fw	*next;		/* linked list of deleted rules */