diff --git a/sys/netpfil/pf/pf_lb.c b/sys/netpfil/pf/pf_lb.c
--- a/sys/netpfil/pf/pf_lb.c
+++ b/sys/netpfil/pf/pf_lb.c
@@ -52,6 +52,13 @@
 #include <net/pfvar.h>
 #include <net/if_pflog.h>
 
+/*
+ * Limit the amount of work we do to find a free source port for redirects that
+ * introduce a state conflict.
+ */
+#define	V_pf_rdr_srcport_rewrite_tries	VNET(pf_rdr_srcport_rewrite_tries)
+VNET_DEFINE_STATIC(int, pf_rdr_srcport_rewrite_tries) = 16;
+
 #define DPFPRINTF(n, x)	if (V_pf_status.debug >= (n)) printf x
 
 static void		 pf_hash(struct pf_addr *, struct pf_addr *,
@@ -756,6 +763,7 @@
 		break;
 	case PF_RDR: {
 		struct pf_state_key_cmp key;
+		int tries;
 		uint16_t cut, low, high, nport;
 
 		reason = pf_map_addr(pd->af, r, saddr, naddr, NULL, NULL, sn);
@@ -807,11 +815,15 @@
 		if (!pf_find_state_all_exists(&key, PF_OUT))
 			break;
 
+		tries = 0;
+
 		low = 50001;	/* XXX-MJ PF_NAT_PROXY_PORT_LOW/HIGH */
 		high = 65535;
 		cut = arc4random() % (1 + high - low) + low;
 		for (uint32_t tmp = cut;
-		    tmp <= high && tmp <= UINT16_MAX; tmp++) {
+		    tmp <= high && tmp <= UINT16_MAX &&
+		    tries < V_pf_rdr_srcport_rewrite_tries;
+		    tmp++, tries++) {
 			key.port[0] = htons(tmp);
 			if (!pf_find_state_all_exists(&key, PF_OUT)) {
 				/* Update the source port. */
@@ -819,7 +831,9 @@
 				goto out;
 			}
 		}
-		for (uint32_t tmp = cut - 1; tmp >= low; tmp--) {
+		for (uint32_t tmp = cut - 1;
+		    tmp >= low && tries < V_pf_rdr_srcport_rewrite_tries;
+		    tmp--, tries++) {
 			key.port[0] = htons(tmp);
 			if (!pf_find_state_all_exists(&key, PF_OUT)) {
 				/* Update the source port. */