[PATCH v3 14/14] flow, fwd: Optimise forwarding rule lookup using epoll ref when possible

[David Gibson <david@gibson.dropbear.id.au>]

Now that listening sockets include a reference to the forwarding rule which
created them we can, in many cases, avoid a linear search of the forwarding
table when we want to find the relevant rule.  Instead we can take the
rule index from the socket's epoll reference, and use that to immediately
find the correct rule.

This is conceptually simple, but requires a moderate amount of plumbing to
get the index from the reference through to the rule lookup.  We still
allow fall back to linear search if we don't have the index, and this may
(rarely) be used in the udp_flush_flow() case, where we could get packets
for one flow on a different flow's socket, rather than through a listening
socket as usual.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
---
 flow.c         | 13 +++++++++++--
 flow_table.h   |  2 +-
 fwd.c          |  3 +--
 fwd.h          |  1 +
 icmp.c         |  2 +-
 tcp.c          |  4 ++--
 udp.c          | 14 +++++++++-----
 udp_flow.c     | 14 ++++++++------
 udp_flow.h     |  2 +-
 udp_internal.h |  4 ++--
 10 files changed, 37 insertions(+), 22 deletions(-)

diff --git a/flow.c b/flow.c
index 38f88732..85759970 100644
--- a/flow.c
+++ b/flow.c
@@ -482,12 +482,13 @@ struct flowside *flow_initiate_sa(union flow *flow, uint8_t pif,
  * flow_target() - Determine where flow should forward to, and move to TGT
  * @c:		Execution context
  * @flow:	Flow to forward
+ * @rule_hint:	Index of relevant forwarding rule, or -1 if unknown
  * @proto:	Protocol
  *
  * Return: pointer to the target flowside information
  */
 struct flowside *flow_target(const struct ctx *c, union flow *flow,
-			     uint8_t proto)
+			     int rule_hint, uint8_t proto)
 {
 	char estr[INANY_ADDRSTRLEN], ostr[INANY_ADDRSTRLEN];
 	struct flow_common *f = &flow->f;
@@ -515,7 +516,15 @@ struct flowside *flow_target(const struct ctx *c, union flow *flow,
 		else
 			goto nofwd;
 
-		if (!(rule = fwd_rule_search(fwd, ini))) {
+		if (rule_hint >= 0) {
+			ASSERT((unsigned)rule_hint < fwd->count);
+			rule = &fwd->rules[rule_hint];
+			if (!fwd_rule_match(rule, ini)) {
+				flow_dbg(flow,
+					 "Unexpected mismatching forward rule");
+				goto nofwd;
+			}
+		} else if (!(rule = fwd_rule_search(fwd, ini))) {
 			/* This shouldn't happen, because if there's no rule for
 			 * it we should have no listening socket that would let
 			 * us get here
diff --git a/flow_table.h b/flow_table.h
index 5ee13acc..73de13ba 100644
--- a/flow_table.h
+++ b/flow_table.h
@@ -207,7 +207,7 @@ const struct flowside *flow_target_af(union flow *flow, uint8_t pif,
 				      const void *saddr, in_port_t sport,
 				      const void *daddr, in_port_t dport);
 struct flowside *flow_target(const struct ctx *c, union flow *flow,
-			     uint8_t proto);
+			     int rule_hint, uint8_t proto);
 
 union flow *flow_set_type(union flow *flow, enum flow_type type);
 #define FLOW_SET_TYPE(flow_, t_, var_)	(&flow_set_type((flow_), (t_))->var_)
diff --git a/fwd.c b/fwd.c
index 6727d26f..250b470c 100644
--- a/fwd.c
+++ b/fwd.c
@@ -415,8 +415,7 @@ void fwd_rule_add(struct fwd_ports *fwd, uint8_t flags,
  *
  * Returns: true if the rule applies to the flow, false otherwise
  */
-static bool fwd_rule_match(const struct fwd_rule *rule,
-			   const struct flowside *ini)
+bool fwd_rule_match(const struct fwd_rule *rule, const struct flowside *ini)
 {
 	return inany_matches(&ini->oaddr, fwd_rule_addr(rule)) &&
 		ini->oport >= rule->first && ini->oport <= rule->last;
diff --git a/fwd.h b/fwd.h
index 435f422a..2af7791d 100644
--- a/fwd.h
+++ b/fwd.h
@@ -106,6 +106,7 @@ struct fwd_ports {
 void fwd_rule_add(struct fwd_ports *fwd, uint8_t flags,
 		  const union inany_addr *addr, const char *ifname,
 		  in_port_t first, in_port_t last, in_port_t to);
+bool fwd_rule_match(const struct fwd_rule *rule, const struct flowside *ini);
 const struct fwd_rule *fwd_rule_search(const struct fwd_ports *fwd,
 				       const struct flowside *ini);
 void fwd_rules_print(const struct fwd_ports *fwd);
diff --git a/icmp.c b/icmp.c
index 9564c496..0f4d48bb 100644
--- a/icmp.c
+++ b/icmp.c
@@ -183,7 +183,7 @@ static struct icmp_ping_flow *icmp_ping_new(const struct ctx *c,
 		return NULL;
 
 	flow_initiate_af(flow, PIF_TAP, af, saddr, id, daddr, id);
-	if (!(tgt = flow_target(c, flow, proto)))
+	if (!(tgt = flow_target(c, flow, -1, proto)))
 		goto cancel;
 
 	if (flow->f.pif[TGTSIDE] != PIF_HOST) {
diff --git a/tcp.c b/tcp.c
index fc03e38f..89b22a51 100644
--- a/tcp.c
+++ b/tcp.c
@@ -1657,7 +1657,7 @@ static void tcp_conn_from_tap(const struct ctx *c, sa_family_t af,
 	ini = flow_initiate_af(flow, PIF_TAP,
 			       af, saddr, srcport, daddr, dstport);
 
-	if (!(tgt = flow_target(c, flow, IPPROTO_TCP)))
+	if (!(tgt = flow_target(c, flow, -1, IPPROTO_TCP)))
 		goto cancel;
 
 	if (flow->f.pif[TGTSIDE] != PIF_HOST) {
@@ -2496,7 +2496,7 @@ void tcp_listen_handler(const struct ctx *c, union epoll_ref ref,
 		goto cancel;
 	}
 
-	if (!flow_target(c, flow, IPPROTO_TCP))
+	if (!flow_target(c, flow, ref.listen.rule, IPPROTO_TCP))
 		goto cancel;
 
 	switch (flow->f.pif[TGTSIDE]) {
diff --git a/udp.c b/udp.c
index 761221f6..d7e47e52 100644
--- a/udp.c
+++ b/udp.c
@@ -838,12 +838,13 @@ static void udp_buf_sock_to_tap(const struct ctx *c, int s, int n,
  * udp_sock_fwd() - Forward datagrams from a possibly unconnected socket
  * @c:		Execution context
  * @s:		Socket to forward from
+ * @rule_hint:	Forwarding rule to use, or -1 if unknown
  * @frompif:	Interface to which @s belongs
  * @port:	Our (local) port number of @s
  * @now:	Current timestamp
  */
-void udp_sock_fwd(const struct ctx *c, int s, uint8_t frompif,
-		  in_port_t port, const struct timespec *now)
+void udp_sock_fwd(const struct ctx *c, int s, int rule_hint,
+		  uint8_t frompif, in_port_t port, const struct timespec *now)
 {
 	union sockaddr_inany src;
 	union inany_addr dst;
@@ -868,7 +869,8 @@ void udp_sock_fwd(const struct ctx *c, int s, uint8_t frompif,
 			continue;
 		}
 
-		tosidx = udp_flow_from_sock(c, frompif, &dst, port, &src, now);
+		tosidx = udp_flow_from_sock(c, frompif, &dst, port, &src,
+					    rule_hint, now);
 		topif = pif_at_sidx(tosidx);
 
 		if (pif_is_socket(topif)) {
@@ -910,8 +912,10 @@ void udp_listen_sock_handler(const struct ctx *c,
 			     union epoll_ref ref, uint32_t events,
 			     const struct timespec *now)
 {
-	if (events & (EPOLLERR | EPOLLIN))
-		udp_sock_fwd(c, ref.fd, ref.listen.pif, ref.listen.port, now);
+	if (events & (EPOLLERR | EPOLLIN)) {
+		udp_sock_fwd(c, ref.fd, ref.listen.rule,
+			     ref.listen.pif, ref.listen.port, now);
+	}
 }
 
 /**
diff --git a/udp_flow.c b/udp_flow.c
index 8907f2f7..b82c6c06 100644
--- a/udp_flow.c
+++ b/udp_flow.c
@@ -139,6 +139,7 @@ static int udp_flow_sock(const struct ctx *c,
  * udp_flow_new() - Common setup for a new UDP flow
  * @c:		Execution context
  * @flow:	Initiated flow
+ * @rule_hint:	Index of forwarding rule, or -1 if unknown
  * @now:	Timestamp
  *
  * Return: sidx for the target side of the new UDP flow, or FLOW_SIDX_NONE
@@ -147,13 +148,13 @@ static int udp_flow_sock(const struct ctx *c,
  * #syscalls getsockname
  */
 static flow_sidx_t udp_flow_new(const struct ctx *c, union flow *flow,
-				const struct timespec *now)
+				int rule_hint, const struct timespec *now)
 {
 	struct udp_flow *uflow = NULL;
 	const struct flowside *tgt;
 	unsigned sidei;
 
-	if (!(tgt = flow_target(c, flow, IPPROTO_UDP)))
+	if (!(tgt = flow_target(c, flow, rule_hint, IPPROTO_UDP)))
 		goto cancel;
 
 	uflow = FLOW_SET_TYPE(flow, FLOW_UDP, udp);
@@ -216,6 +217,7 @@ cancel:
  * @dst:	Our (local) address to which the datagram is arriving
  * @port:	Our (local) port number to which the datagram is arriving
  * @s_in:	Source socket address, filled in by recvmmsg()
+ * @rule_hint:	Index of forwarding rule, or -1 if unknown
  * @now:	Timestamp
  *
  * #syscalls fcntl arm:fcntl64 ppc64:fcntl64|fcntl i686:fcntl64
@@ -226,7 +228,7 @@ cancel:
 flow_sidx_t udp_flow_from_sock(const struct ctx *c, uint8_t pif,
 			       const union inany_addr *dst, in_port_t port,
 			       const union sockaddr_inany *s_in,
-			       const struct timespec *now)
+			       int rule_hint, const struct timespec *now)
 {
 	const struct flowside *ini;
 	struct udp_flow *uflow;
@@ -260,7 +262,7 @@ flow_sidx_t udp_flow_from_sock(const struct ctx *c, uint8_t pif,
 		return FLOW_SIDX_NONE;
 	}
 
-	return udp_flow_new(c, flow, now);
+	return udp_flow_new(c, flow, rule_hint, now);
 }
 
 /**
@@ -316,7 +318,7 @@ flow_sidx_t udp_flow_from_tap(const struct ctx *c,
 		return FLOW_SIDX_NONE;
 	}
 
-	return udp_flow_new(c, flow, now);
+	return udp_flow_new(c, flow, -1, now);
 }
 
 /**
@@ -332,7 +334,7 @@ static void udp_flush_flow(const struct ctx *c,
 {
 	/* We don't know exactly where the datagrams will come from, but we know
 	 * they'll have an interface and oport matching this flow */
-	udp_sock_fwd(c, uflow->s[sidei], uflow->f.pif[sidei],
+	udp_sock_fwd(c, -1, uflow->s[sidei], uflow->f.pif[sidei],
 		     uflow->f.side[sidei].oport, now);
 }
 
diff --git a/udp_flow.h b/udp_flow.h
index 4c528e95..14e0f920 100644
--- a/udp_flow.h
+++ b/udp_flow.h
@@ -35,7 +35,7 @@ struct udp_flow *udp_at_sidx(flow_sidx_t sidx);
 flow_sidx_t udp_flow_from_sock(const struct ctx *c, uint8_t pif,
 			       const union inany_addr *dst, in_port_t port,
 			       const union sockaddr_inany *s_in,
-			       const struct timespec *now);
+			       int rule_hint, const struct timespec *now);
 flow_sidx_t udp_flow_from_tap(const struct ctx *c,
 			      uint8_t pif, sa_family_t af,
 			      const void *saddr, const void *daddr,
diff --git a/udp_internal.h b/udp_internal.h
index 96d11cff..f0ce8f14 100644
--- a/udp_internal.h
+++ b/udp_internal.h
@@ -28,7 +28,7 @@ size_t udp_update_hdr4(struct iphdr *ip4h, struct udp_payload_t *bp,
 size_t udp_update_hdr6(struct ipv6hdr *ip6h, struct udp_payload_t *bp,
                        const struct flowside *toside, size_t dlen,
 		       bool no_udp_csum);
-void udp_sock_fwd(const struct ctx *c, int s, uint8_t frompif,
-		  in_port_t port, const struct timespec *now);
+void udp_sock_fwd(const struct ctx *c, int s, int rule_hint,
+		  uint8_t frompif, in_port_t port, const struct timespec *now);
 
 #endif /* UDP_INTERNAL_H */
-- 
2.52.0