Oops, sorry for the previous one, I was typing faster than
thinking. :-\ Of course, it's pfsync changes are needed. It's only
the state count manipulation that was wrong. Routing rules do not
have anything common with this. So the final (I hope) version is
here.

Index: if_pflog.c
===================================================================
RCS file: /cvs/src/sys/net/if_pflog.c,v
retrieving revision 1.32
diff -u -p -r1.32 if_pflog.c
--- if_pflog.c	21 Sep 2010 22:49:14 -0000	1.32
+++ if_pflog.c	16 Nov 2010 11:35:27 -0000
@@ -212,7 +212,7 @@ pflogioctl(struct ifnet *ifp, u_long cmd
 int
 pflog_packet(struct pfi_kif *kif, struct mbuf *m, sa_family_t af, u_int8_t dir,
     u_int8_t reason, struct pf_rule *rm, struct pf_rule *am,
-    struct pf_ruleset *ruleset, struct pf_pdesc *pd)
+    struct pf_rule *rtr, struct pf_ruleset *ruleset, struct pf_pdesc *pd)
 {
 #if NBPFILTER > 0
 	struct ifnet *ifn;
@@ -241,6 +241,10 @@ pflog_packet(struct pfi_kif *kif, struct
 			strlcpy(hdr.ruleset, ruleset->anchor->name,
 			    sizeof(hdr.ruleset));
 	}
+	if (rtr == NULL)
+		hdr.rt_rulenr = htonl(-1);
+	else
+		hdr.rt_rulenr = htonl(rtr->nr);
 	if (rm->log & PF_LOG_SOCKET_LOOKUP && !pd->lookup.done)
 		pd->lookup.done = pf_socket_lookup(dir, pd);
 	if (pd->lookup.done > 0) {
Index: if_pflog.h
===================================================================
RCS file: /cvs/src/sys/net/if_pflog.h,v
retrieving revision 1.17
diff -u -p -r1.17 if_pflog.h
--- if_pflog.h	21 Sep 2010 11:05:10 -0000	1.17
+++ if_pflog.h	16 Nov 2010 11:35:27 -0000
@@ -59,6 +59,7 @@ struct pfloghdr {
 	struct pf_addr	daddr;
 	u_int16_t	sport;
 	u_int16_t	dport;
+	u_int32_t	rt_rulenr;
 };
 
 #define PFLOG_HDRLEN		sizeof(struct pfloghdr)
@@ -70,9 +71,9 @@ struct pfloghdr {
 void	pflog_bpfcopy(const void *, void *, size_t);
 
 #if NPFLOG > 0
-#define	PFLOG_PACKET(i,x,a,b,c,d,e,f,g,h) pflog_packet(i,a,b,c,d,e,f,g,h)
+#define	PFLOG_PACKET(i,x,a,b,c,d,e,f,g,h,j) pflog_packet(i,a,b,c,d,e,f,g,h,j)
 #else
-#define	PFLOG_PACKET(i,x,a,b,c,d,e,f,g,h) ((void)0)
+#define	PFLOG_PACKET(i,x,a,b,c,d,e,f,g,h,j) ((void)0)
 #endif /* NPFLOG > 0 */
 #endif /* _KERNEL */
 #endif /* _NET_IF_PFLOG_H_ */
Index: if_pfsync.c
===================================================================
RCS file: /cvs/src/sys/net/if_pfsync.c,v
retrieving revision 1.156
diff -u -p -r1.156 if_pfsync.c
--- if_pfsync.c	27 Sep 2010 23:45:48 -0000	1.156
+++ if_pfsync.c	16 Nov 2010 11:35:27 -0000
@@ -466,6 +466,15 @@ pfsync_state_export(struct pfsync_state 
 		sp->anchor = htonl(st->anchor.ptr->nr);
 	sp->nat_rule = htonl(-1);	/* left for compat, nat_rule is gone */
 
+	/*
+	 * Make pfsync with and without support of routing rules co-exist: leave
+	 * 0 instead -1 and do the decrement dance in pfsync_state_import().
+	 */
+	if (st->rt_rule == NULL)
+		sp->rt_rule = 0;
+	else
+		sp->rt_rule = htonl(st->rt_rule->nr + 1);
+
 	pf_state_counter_hton(st->packets[0], sp->packets[0]);
 	pf_state_counter_hton(st->packets[1], sp->packets[1]);
 	pf_state_counter_hton(st->bytes[0], sp->bytes[0]);
@@ -481,7 +490,7 @@ pfsync_state_import(struct pfsync_state 
 {
 	struct pf_state	*st = NULL;
 	struct pf_state_key *skw = NULL, *sks = NULL;
-	struct pf_rule *r = NULL;
+	struct pf_rule *r = NULL, *rtr = NULL;
 	struct pfi_kif	*kif;
 	int pool_flags;
 	int error;
@@ -504,12 +513,18 @@ pfsync_state_import(struct pfsync_state 
 	 * If the ruleset checksums match or the state is coming from the ioctl,
 	 * it's safe to associate the state with the rule of that number.
 	 */
-	if (sp->rule != htonl(-1) && sp->anchor == htonl(-1) &&
-	    (flags & (PFSYNC_SI_IOCTL | PFSYNC_SI_CKSUM)) && ntohl(sp->rule) <
-	    pf_main_ruleset.rules.active.rcount)
-		r = pf_main_ruleset.rules.active.ptr_array[ntohl(sp->rule)];
-	else
-		r = &pf_default_rule;
+	if ((flags & (PFSYNC_SI_IOCTL | PFSYNC_SI_CKSUM))) {
+		if (sp->rule != htonl(-1) && sp->anchor == htonl(-1) &&
+		    ntohl(sp->rule) < pf_main_ruleset.rules.active.rcount)
+			r = pf_main_ruleset.rules.active.ptr_array[ntohl(sp->rule)];
+		else
+			r = &pf_default_rule;
+
+		/* 0 means either "no routing rule" or "routing rules not supported" */
+		if (sp->rt_rule != 0 &&
+		    ntohl(sp->rt_rule) - 1 < pf_main_ruleset.rules.active.rcount)
+			rtr = pf_main_ruleset.rules.active.ptr_array[ntohl(sp->rt_rule) - 1];
+	}
 
 	if ((r->max_states && r->states_cur >= r->max_states))
 		goto cleanup;
@@ -588,6 +603,7 @@ pfsync_state_import(struct pfsync_state 
 	st->rule.ptr = r;
 	st->anchor.ptr = NULL;
 	st->rt_kif = NULL;
+	st->rt_rule = rtr;
 
 	st->pfsync_time = time_uptime;
 	st->sync_state = PFSYNC_S_NONE;
Index: pf.c
===================================================================
RCS file: /cvs/src/sys/net/pf.c,v
retrieving revision 1.713
diff -u -p -r1.713 pf.c
--- pf.c	24 Sep 2010 02:28:10 -0000	1.713
+++ pf.c	16 Nov 2010 11:35:28 -0000
@@ -263,11 +263,11 @@ enum { PF_ICMP_MULTI_NONE, PF_ICMP_MULTI
 		s = pf_find_state(i, k, d, m);			\
 		if (s == NULL || (s)->timeout == PFTM_PURGE)		\
 			return (PF_DROP);				\
-		if (d == PF_OUT &&					\
-		    (((s)->rule.ptr->rt == PF_ROUTETO &&		\
-		    (s)->rule.ptr->direction == PF_OUT) ||		\
-		    ((s)->rule.ptr->rt == PF_REPLYTO &&			\
-		    (s)->rule.ptr->direction == PF_IN)) &&		\
+		if (d == PF_OUT && (s)->rt_rule != NULL &&		\
+		    (((s)->rt_rule->rt == PF_ROUTETO &&			\
+		    (s)->rt_rule->direction == PF_OUT) ||		\
+		    ((s)->rt_rule->rt == PF_REPLYTO &&			\
+		    (s)->rt_rule->direction == PF_IN)) &&		\
 		    (s)->rt_kif != NULL &&				\
 		    (s)->rt_kif != i)					\
 			return (PF_PASS);				\
@@ -2695,11 +2695,11 @@ pf_calc_mss(struct pf_addr *addr, sa_fam
 void
 pf_set_rt_ifp(struct pf_state *s, struct pf_addr *saddr)
 {
-	struct pf_rule *r = s->rule.ptr;
+	struct pf_rule *r = s->rt_rule;
 	struct pf_src_node *sn = NULL;
 
 	s->rt_kif = NULL;
-	if (!r->rt || r->rt == PF_FASTROUTE)
+	if (r == NULL || !r->rt || r->rt == PF_FASTROUTE)
 		return;
 	switch (s->key[PF_SK_WIRE]->af) {
 #ifdef INET
@@ -2764,6 +2764,8 @@ pf_rule_to_actions(struct pf_rule *r, st
 		a->min_ttl = r->min_ttl;
 	if (r->max_mss)
 		a->max_mss = r->max_mss;
+	if (r->rt)
+		a->rt_rule = r;
 	a->flags |= (r->scrub_flags & (PFSTATE_NODF|PFSTATE_RANDOMID|
 	    PFSTATE_SETTOS|PFSTATE_SCRUB_TCP));
 }
@@ -2944,7 +2946,7 @@ pf_test_rule(struct pf_rule **rm, struct
 					if (r->log || act.log & PF_LOG_MATCHES)
 						PFLOG_PACKET(kif, h, m, af,
 						    direction, reason, r,
-						    a, ruleset, pd);
+						    a, act.rt_rule, ruleset, pd);
 				} else {
 					match = 1;
 					*rm = r;
@@ -2953,7 +2955,7 @@ pf_test_rule(struct pf_rule **rm, struct
 					if (act.log & PF_LOG_MATCHES)
 						PFLOG_PACKET(kif, h, m, af,
 						    direction, reason, r,
-						    a, ruleset, pd);
+						    a, act.rt_rule, ruleset, pd);
 				}
 
 				if ((*rm)->quick)
@@ -2981,7 +2983,7 @@ pf_test_rule(struct pf_rule **rm, struct
 
 	if (r->log || act.log & PF_LOG_MATCHES)
 		PFLOG_PACKET(kif, h, m, af, direction, reason,
-		    r, a, ruleset, pd);
+		    r, a, act.rt_rule, ruleset, pd);
 
 	if ((r->action == PF_DROP) &&
 	    ((r->rule_flag & PFRULE_RETURNRST) ||
@@ -3147,6 +3149,7 @@ pf_create_state(struct pf_rule *r, struc
 	s->min_ttl = act->min_ttl;
 	s->set_tos = act->set_tos;
 	s->max_mss = act->max_mss;
+	s->rt_rule = act->rt_rule;
 	s->state_flags |= act->flags;
 	s->sync_state = PFSYNC_S_NONE;
 	switch (pd->proto) {
@@ -3419,7 +3422,7 @@ pf_test_fragment(struct pf_rule **rm, in
     struct mbuf *m, void *h, struct pf_pdesc *pd, struct pf_rule **am,
     struct pf_ruleset **rsm)
 {
-	struct pf_rule		*r, *a = NULL;
+	struct pf_rule		*r, *a = NULL, *rtr = NULL;
 	struct pf_ruleset	*ruleset = NULL;
 	sa_family_t		 af = pd->af;
 	u_short			 reason;
@@ -3464,6 +3467,7 @@ pf_test_fragment(struct pf_rule **rm, in
 		else if (r->match_tag && !pf_match_tag(m, r, &tag))
 			r = TAILQ_NEXT(r, entries);
 		else {
+			/* XXX: No handling of "match" rules? */
 			if (r->anchor == NULL) {
 				match = 1;
 				*rm = r;
@@ -3483,12 +3487,14 @@ pf_test_fragment(struct pf_rule **rm, in
 	r = *rm;
 	a = *am;
 	ruleset = *rsm;
+	if (r->rt)
+		rtr = r;
 
 	REASON_SET(&reason, PFRES_MATCH);
 
 	if (r->log)
-		PFLOG_PACKET(kif, h, m, af, direction, reason, r, a, ruleset,
-		    pd);
+		PFLOG_PACKET(kif, h, m, af, direction, reason, r, a, rtr,
+		    ruleset, pd);
 
 	if (r->action == PF_DROP)
 		return (PF_DROP);
@@ -5830,7 +5836,7 @@ pf_test(int dir, struct ifnet *ifp, stru
 	u_short			 action, reason = 0, pflog = 0;
 	struct mbuf		*m = *m0;
 	struct ip		*h;
-	struct pf_rule		*a = NULL, *r = &pf_default_rule;
+	struct pf_rule		*a = NULL, *r = &pf_default_rule, *rtr = NULL;
 	struct pf_state		*s = NULL;
 	struct pf_ruleset	*ruleset = NULL;
 	struct pf_pdesc		 pd;
@@ -5998,12 +6004,15 @@ done:
 			qid = s->pqid;
 		else
 			qid = s->qid;
+		rtr = s->rt_rule;
 	} else {
 		pf_scrub_ip(&m, r->scrub_flags, r->min_ttl, r->set_tos);
 		if (pqid || (pd.tos & IPTOS_LOWDELAY))
 			qid = r->pqid;
 		else
 			qid = r->qid;
+		if (r->rt)
+			rtr = r;
 	}
 
 	if (dir == PF_IN && s && s->key[PF_SK_STACK])
@@ -6052,12 +6061,13 @@ done:
 
 		if (pflog & PF_LOG_FORCE || r->log & PF_LOG_ALL)
 			PFLOG_PACKET(kif, h, m, AF_INET, dir, reason, r, a,
-			    ruleset, &pd);
+			    rtr, ruleset, &pd);
 		if (s) {
 			SLIST_FOREACH(ri, &s->match_rules, entry)
 				if (ri->r->log & PF_LOG_ALL)
 					PFLOG_PACKET(kif, h, m, AF_INET, dir,
-					    reason, ri->r, a, ruleset, &pd);
+					    reason, ri->r, a, rtr, ruleset,
+					    &pd);
 		}
 	}
 
@@ -6077,8 +6087,8 @@ done:
 		break;
 	default:
 		/* pf_route can free the mbuf causing *m0 to become NULL */
-		if (r->rt)
-			pf_route(m0, r, dir, kif->pfik_ifp, s, &pd);
+		if (rtr != NULL)
+			pf_route(m0, rtr, dir, kif->pfik_ifp, s, &pd);
 		break;
 	}
 
@@ -6095,7 +6105,7 @@ pf_test6(int dir, struct ifnet *ifp, str
 	u_short			 action, reason = 0, pflog = 0;
 	struct mbuf		*m = *m0, *n = NULL;
 	struct ip6_hdr		*h;
-	struct pf_rule		*a = NULL, *r = &pf_default_rule;
+	struct pf_rule		*a = NULL, *r = &pf_default_rule, *rtr = NULL;
 	struct pf_state		*s = NULL;
 	struct pf_ruleset	*ruleset = NULL;
 	struct pf_pdesc		 pd;
@@ -6267,10 +6277,14 @@ done:
 		    "pf: dropping packet with dangerous v6 headers");
 	}
 
-	if (s)
+	if (s) {
 		pf_scrub_ip6(&m, s->min_ttl);
-	else
+		rtr = s->rt_rule;
+	} else {
 		pf_scrub_ip6(&m, r->min_ttl);
+		if (r->rt)
+			rtr = r;
+	}
 
 	if (s && s->tag)
 		pf_tag_packet(m, s ? s->tag : 0, s->rtableid[pd.didx]);
@@ -6320,12 +6334,13 @@ done:
 
 		if (pflog & PF_LOG_FORCE || r->log & PF_LOG_ALL)
 			PFLOG_PACKET(kif, h, m, AF_INET6, dir, reason, r, a,
-			    ruleset, &pd);
+			    rtr, ruleset, &pd);
 		if (s) {
 			SLIST_FOREACH(ri, &s->match_rules, entry)
 				if (ri->r->log & PF_LOG_ALL)
 					PFLOG_PACKET(kif, h, m, AF_INET6, dir,
-					    reason, ri->r, a, ruleset, &pd);
+					    reason, ri->r, a, rtr, ruleset,
+					    &pd);
 		}
 	}
 
@@ -6345,8 +6360,8 @@ done:
 		break;
 	default:
 		/* pf_route6 can free the mbuf causing *m0 to become NULL */
-		if (r->rt)
-			pf_route6(m0, r, dir, kif->pfik_ifp, s, &pd);
+		if (rtr != NULL)
+			pf_route6(m0, rtr, dir, kif->pfik_ifp, s, &pd);
 		break;
 	}
 
Index: pfvar.h
===================================================================
RCS file: /cvs/src/sys/net/pfvar.h,v
retrieving revision 1.318
diff -u -p -r1.318 pfvar.h
--- pfvar.h	23 Oct 2010 15:38:18 -0000	1.318
+++ pfvar.h	16 Nov 2010 11:35:29 -0000
@@ -520,15 +520,16 @@ struct pf_osfp_ioctl {
 };
 
 struct pf_rule_actions {
-	int		rtableid;
-	u_int16_t	qid;
-	u_int16_t	pqid;
-	u_int16_t	max_mss;
-	u_int8_t	log;
-	u_int8_t	set_tos;
-	u_int8_t	min_ttl;
-	u_int8_t	pad[1];
-	u_int16_t	flags;
+	struct pf_rule	*rt_rule;
+	int		 rtableid;
+	u_int16_t	 qid;
+	u_int16_t	 pqid;
+	u_int16_t	 max_mss;
+	u_int8_t	 log;
+	u_int8_t	 set_tos;
+	u_int8_t	 min_ttl;
+	u_int8_t	 pad[1];
+	u_int16_t	 flags;
 };
 
 union pf_rule_ptr {
@@ -807,6 +808,7 @@ struct pf_state {
 	struct pf_state_key	*key[2];	/* addresses stack and wire  */
 	struct pfi_kif		*kif;
 	struct pfi_kif		*rt_kif;
+	struct pf_rule		*rt_rule;
 	u_int64_t		 packets[2];
 	u_int64_t		 bytes[2];
 	u_int32_t		 creation;
@@ -896,7 +898,7 @@ struct pfsync_state {
 	u_int8_t	 updates;
 	u_int8_t	 min_ttl;
 	u_int8_t	 set_tos;
-	u_int8_t	 pad[4];
+	u_int32_t	 rt_rule;
 } __packed;
 
 #define PFSYNC_FLAG_SRCNODE	0x04
@@ -1758,8 +1760,8 @@ void   *pf_pull_hdr(struct mbuf *, int, 
 	    sa_family_t);
 void	pf_change_a(void *, u_int16_t *, u_int32_t, u_int8_t);
 int	pflog_packet(struct pfi_kif *, struct mbuf *, sa_family_t, u_int8_t,
-	    u_int8_t, struct pf_rule *, struct pf_rule *, struct pf_ruleset *,
-	    struct pf_pdesc *);
+	    u_int8_t, struct pf_rule *, struct pf_rule *, struct pf_rule *,
+	    struct pf_ruleset *, struct pf_pdesc *);
 void	pf_send_deferred_syn(struct pf_state *);
 int	pf_match_addr(u_int8_t, struct pf_addr *, struct pf_addr *,
 	    struct pf_addr *, sa_family_t);