Add skip steps for rule action (pass/block vs. scrub) and direction

(in vs. out). This speeds up rule set evaluation considerably, because
the rules set used to be linearly traversed (even twice) when looking
for scrub rules. Ok frantzen@, deraadt@

3 files changed, 64 insertions, 65 deletions

diff --git a/sys/net/pf.c b/sys/net/pf.c
index b5a0d0f4fd7..f654077abb9 100644
--- a/sys/net/pf.c
+++ b/sys/net/pf.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pf.c,v 1.187 2002/02/11 16:22:48 dhartmei Exp $ */
+/*	$OpenBSD: pf.c,v 1.188 2002/02/14 15:32:11 dhartmei Exp $ */
 
 /*
  * Copyright (c) 2001 Daniel Hartmeier
@@ -2188,7 +2188,12 @@ pf_calc_skip_steps(struct pf_rulequeue *rules)
 		}
 		s = TAILQ_NEXT(r, entries);
 		while (a && s != NULL) {
+			PF_CALC_SKIP_STEP(PF_SKIP_ACTION,
+			    (s->action == PF_SCRUB && r->action == PF_SCRUB) ||
+			    (s->action != PF_SCRUB && r->action != PF_SCRUB));
 			PF_CALC_SKIP_STEP(PF_SKIP_IFP, s->ifp == r->ifp);
+			PF_CALC_SKIP_STEP(PF_SKIP_DIR,
+			    s->direction == r->direction);
 			PF_CALC_SKIP_STEP(PF_SKIP_AF, s->af == r->af);
 			PF_CALC_SKIP_STEP(PF_SKIP_PROTO, s->proto == r->proto);
 			PF_CALC_SKIP_STEP(PF_SKIP_SRC_ADDR,
@@ -2866,13 +2871,13 @@ pf_test_tcp(struct pf_rule **rm, int direction, struct ifnet *ifp,
 
 	r = TAILQ_FIRST(pf_rules_active);
 	while (r != NULL) {
-		if (r->action == PF_SCRUB) {
-			r = TAILQ_NEXT(r, entries);
-			continue;
-		}
 		r->evaluations++;
-		if (r->ifp != NULL && r->ifp != ifp)
+		if (r->action == PF_SCRUB)
+			r = r->skip[PF_SKIP_ACTION];
+		else if (r->ifp != NULL && r->ifp != ifp)
 			r = r->skip[PF_SKIP_IFP];
+		else if (r->direction != direction)
+			r = r->skip[PF_SKIP_DIR];
 		else if (r->af && r->af != af)
 			r = r->skip[PF_SKIP_AF];
 		else if (r->proto && r->proto != IPPROTO_TCP)
@@ -2889,8 +2894,6 @@ pf_test_tcp(struct pf_rule **rm, int direction, struct ifnet *ifp,
 		else if (r->dst.port_op && !pf_match_port(r->dst.port_op,
 		    r->dst.port[0], r->dst.port[1], th->th_dport))
 			r = r->skip[PF_SKIP_DST_PORT];
-		else if (r->direction != direction)
-			r = TAILQ_NEXT(r, entries);
 		else if ((r->flagset & th->th_flags) != r->flags)
 			r = TAILQ_NEXT(r, entries);
 		else {
@@ -3092,14 +3095,13 @@ pf_test_udp(struct pf_rule **rm, int direction, struct ifnet *ifp,
 
 	r = TAILQ_FIRST(pf_rules_active);
 	while (r != NULL) {
-		if (r->action == PF_SCRUB) {
-			r = TAILQ_NEXT(r, entries);
-			continue;
-		}
 		r->evaluations++;
-
-		if (r->ifp != NULL && r->ifp != ifp)
+		if (r->action == PF_SCRUB)
+			r = r->skip[PF_SKIP_ACTION];
+		else if (r->ifp != NULL && r->ifp != ifp)
 			r = r->skip[PF_SKIP_IFP];
+		else if (r->direction != direction)
+			r = r->skip[PF_SKIP_DIR];
 		else if (r->af && r->af != af)
 			r = r->skip[PF_SKIP_AF];
 		else if (r->proto && r->proto != IPPROTO_UDP)
@@ -3118,8 +3120,6 @@ pf_test_udp(struct pf_rule **rm, int direction, struct ifnet *ifp,
 		else if (r->dst.port_op && !pf_match_port(r->dst.port_op,
 		    r->dst.port[0], r->dst.port[1], uh->uh_dport))
 			r = r->skip[PF_SKIP_DST_PORT];
-		else if (r->direction != direction)
-			r = TAILQ_NEXT(r, entries);
 		else {
 			*rm = r;
 			if ((*rm)->quick)
@@ -3349,13 +3349,13 @@ pf_test_icmp(struct pf_rule **rm, int direction, struct ifnet *ifp,
 
 	r = TAILQ_FIRST(pf_rules_active);
 	while (r != NULL) {
-		if (r->action == PF_SCRUB) {
-			r = TAILQ_NEXT(r, entries);
-			continue;
-		}
 		r->evaluations++;
-		if (r->ifp != NULL && r->ifp != ifp)
+		if (r->action == PF_SCRUB)
+			r = r->skip[PF_SKIP_ACTION];
+		else if (r->ifp != NULL && r->ifp != ifp)
 			r = r->skip[PF_SKIP_IFP];
+		else if (r->direction != direction)
+			r = r->skip[PF_SKIP_DIR];
 		else if (r->af && r->af != af)
 			r = r->skip[PF_SKIP_AF];
 		else if (r->proto && r->proto != pd->proto)
@@ -3366,8 +3366,6 @@ pf_test_icmp(struct pf_rule **rm, int direction, struct ifnet *ifp,
 		else if (!PF_AZERO(&r->dst.mask, af) && !PF_MATCHA(r->dst.not,
 		    &r->dst.addr, &r->dst.mask, daddr, af))
 			r = r->skip[PF_SKIP_DST_ADDR];
-		else if (r->direction != direction)
-			r = TAILQ_NEXT(r, entries);
 		else if (r->ifp != NULL && r->ifp != ifp)
 			r = TAILQ_NEXT(r, entries);
 		else if (r->type && r->type != icmptype + 1)
@@ -3549,13 +3547,13 @@ pf_test_other(struct pf_rule **rm, int direction, struct ifnet *ifp,
 
 	r = TAILQ_FIRST(pf_rules_active);
 	while (r != NULL) {
-		if (r->action == PF_SCRUB) {
-			r = TAILQ_NEXT(r, entries);
-			continue;
-		}
 		r->evaluations++;
-		if (r->ifp != NULL && r->ifp != ifp)
+		if (r->action == PF_SCRUB)
+			r = r->skip[PF_SKIP_ACTION];
+		else if (r->ifp != NULL && r->ifp != ifp)
 			r = r->skip[PF_SKIP_IFP];
+		else if (r->direction != direction)
+			r = r->skip[PF_SKIP_DIR];
 		else if (r->af && r->af != af)
 			r = r->skip[PF_SKIP_AF];
 		else if (r->proto && r->proto != pd->proto)
@@ -3566,8 +3564,6 @@ pf_test_other(struct pf_rule **rm, int direction, struct ifnet *ifp,
 		else if (!PF_AZERO(&r->dst.mask, af) && !PF_MATCHA(r->dst.not,
 		    &r->dst.addr, &r->dst.mask, pd->dst, af))
 			r = r->skip[PF_SKIP_DST_ADDR];
-		else if (r->direction != direction)
-			r = TAILQ_NEXT(r, entries);
 		else {
 			*rm = r;
 			if ((*rm)->quick)
diff --git a/sys/net/pf_norm.c b/sys/net/pf_norm.c
index 2edd0c11ff2..71fe269a5e6 100644
--- a/sys/net/pf_norm.c
+++ b/sys/net/pf_norm.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pf_norm.c,v 1.17 2002/01/23 00:39:48 art Exp $ */
+/*	$OpenBSD: pf_norm.c,v 1.18 2002/02/14 15:32:11 dhartmei Exp $ */
 
 /*
  * Copyright 2001 Niels Provos <provos@citi.umich.edu>
@@ -445,9 +445,27 @@ pf_normalize_ip(struct mbuf **m0, int dir, struct ifnet *ifp, u_short *reason)
 	u_int16_t fragoff = (h->ip_off & IP_OFFMASK) << 3;
 	u_int16_t max;
 
-	TAILQ_FOREACH(r, pf_rules_active, entries) {
-		if ((r->action == PF_SCRUB) &&
-		    MATCH_TUPLE(h, r, dir, ifp, AF_INET))
+	r = TAILQ_FIRST(pf_rules_active);
+	while (r != NULL) {
+		if (r->action != PF_SCRUB)
+			r = r->skip[PF_SKIP_ACTION];
+		else if (r->ifp != NULL && r->ifp != ifp)
+			r = r->skip[PF_SKIP_IFP];
+		else if (r->direction != dir)
+			r = r->skip[PF_SKIP_DIR];
+		else if (r->af && r->af != AF_INET)
+			r = r->skip[PF_SKIP_AF];
+		else if (r->proto && r->proto != h->ip_p)
+			r = r->skip[PF_SKIP_PROTO];
+		else if (!PF_AZERO(&r->src.mask, AF_INET) &&
+		    !PF_MATCHA(r->src.not, &r->src.addr, &r->src.mask,
+		    (struct pf_addr *)&h->ip_src.s_addr, AF_INET))
+			r = r->skip[PF_SKIP_SRC_ADDR];
+		else if (!PF_AZERO(&r->dst.mask, AF_INET) &&
+		    !PF_MATCHA(r->dst.not, &r->dst.addr, &r->dst.mask,
+		    (struct pf_addr *)&h->ip_dst.s_addr, AF_INET))
+			r = r->skip[PF_SKIP_DST_ADDR];
+		else
 			break;
 	}
 
@@ -566,12 +584,12 @@ pf_normalize_tcp(int dir, struct ifnet *ifp, struct mbuf *m, int ipoff,
 
 	r = TAILQ_FIRST(pf_rules_active);
 	while (r != NULL) {
-		if (r->action != PF_SCRUB) {
-			r = TAILQ_NEXT(r, entries);
-			continue;
-		}
-		if (r->ifp != NULL && r->ifp != ifp)
+		if (r->action != PF_SCRUB)
+			r = r->skip[PF_SKIP_ACTION];
+		else if (r->ifp != NULL && r->ifp != ifp)
 			r = r->skip[PF_SKIP_IFP];
+		else if (r->direction != dir)
+			r = r->skip[PF_SKIP_DIR];
 		else if (r->af && r->af != af)
 			r = r->skip[PF_SKIP_AF];
 		else if (r->proto && r->proto != pd->proto)
@@ -591,10 +609,6 @@ pf_normalize_tcp(int dir, struct ifnet *ifp, struct mbuf *m, int ipoff,
 		else if (r->dst.port_op && !pf_match_port(r->dst.port_op,
 			    r->dst.port[0], r->dst.port[1], th->th_dport))
 			r = r->skip[PF_SKIP_DST_PORT];
-		else if (r->direction != dir)
-			r = TAILQ_NEXT(r, entries);
-		else if (r->ifp != NULL && r->ifp != ifp)
-			r = TAILQ_NEXT(r, entries);
 		else {
 			rm = r;
 			break;
diff --git a/sys/net/pfvar.h b/sys/net/pfvar.h
index 91f12649109..0ae6b13f794 100644
--- a/sys/net/pfvar.h
+++ b/sys/net/pfvar.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pfvar.h,v 1.61 2002/01/11 20:13:11 mickey Exp $ */
+/*	$OpenBSD: pfvar.h,v 1.62 2002/02/14 15:32:11 dhartmei Exp $ */
 
 /*
  * Copyright (c) 2001 Daniel Hartmeier
@@ -199,14 +199,16 @@ struct pf_rule {
 	struct pf_rule_addr dst;
 	struct pf_addr	 rt_addr;
 
-#define PF_SKIP_IFP		0
-#define PF_SKIP_AF		1
-#define PF_SKIP_PROTO		2
-#define PF_SKIP_SRC_ADDR	3
-#define PF_SKIP_SRC_PORT	4
-#define PF_SKIP_DST_ADDR	5
-#define PF_SKIP_DST_PORT	6
-#define PF_SKIP_COUNT		7
+#define PF_SKIP_ACTION		0
+#define PF_SKIP_IFP		1
+#define PF_SKIP_DIR		2
+#define PF_SKIP_AF		3
+#define PF_SKIP_PROTO		4
+#define PF_SKIP_SRC_ADDR	5
+#define PF_SKIP_SRC_PORT	6
+#define PF_SKIP_DST_ADDR	7
+#define PF_SKIP_DST_PORT	8
+#define PF_SKIP_COUNT		9
 	struct pf_rule	*skip[PF_SKIP_COUNT];
 	TAILQ_ENTRY(pf_rule)	entries;
 
@@ -276,19 +278,6 @@ struct pf_state {
 	u_int8_t	 allow_opts;
 };
 
-#define		MATCH_TUPLE(h,r,d,i,a) \
-		( \
-		  (r->direction == d) && \
-		  (r->ifp == NULL || r->ifp == i) && \
-		  (!r->proto || r->proto == h->ip_p) && \
-		  (!r->src.mask.addr32[0] || \
-		   pf_match_addr(r->src.not, &(r)->src.addr, \
-		   &(r)->src.mask, (struct pf_addr *)&h->ip_src.s_addr, a)) && \
-		  (!r->dst.mask.addr32[0] || \
-		   pf_match_addr(r->dst.not, &(r)->dst.addr, \
-		   &(r)->dst.mask, (struct pf_addr *)&h->ip_dst.s_addr, a)) \
-		)
-
 struct pf_nat {
 	char		 ifname[IFNAMSIZ];
 	struct ifnet	*ifp;