Implement consistent host hashing for relayd, based on

work done by andre@

Re-add a randomized hash seed (which had apparently
gotten inadvertently removed in the past).

Allows for multiple relayd instances to be configured
to forward traffic to the same host, falling back to
the random seed when not explicitly configured to do so.

ok reyk@

4 files changed, 121 insertions, 17 deletions

diff --git a/usr.sbin/relayd/parse.y b/usr.sbin/relayd/parse.y
index 888d50b0c04..ff90a86d776 100644
--- a/usr.sbin/relayd/parse.y
+++ b/usr.sbin/relayd/parse.y
@@ -1,4 +1,4 @@
-/*	$OpenBSD: parse.y,v 1.187 2014/07/11 17:35:16 reyk Exp $	*/
+/*	$OpenBSD: parse.y,v 1.188 2014/08/29 09:03:36 blambert Exp $	*/
 
 /*
  * Copyright (c) 2007 - 2014 Reyk Floeter <reyk@openbsd.org>
@@ -119,6 +119,8 @@ static enum key_type	 keytype = KEY_TYPE_NONE;
 static enum direction	 dir = RELAY_DIR_ANY;
 static char		*rulefile = NULL;
 
+static u_int32_t	 hashseed = 0;
+
 struct address	*host_v4(const char *);
 struct address	*host_v6(const char *);
 int		 host_dns(const char *, struct addresslist *,
@@ -168,7 +170,7 @@ typedef struct {
 %token	SOCKET SPLICE SSL STICKYADDR STYLE TABLE TAG TAGGED TCP TIMEOUT TO
 %token	ROUTER RTLABEL TRANSPARENT TRAP UPDATES URL VIRTUAL WITH TTL RTABLE
 %token	MATCH PARAMS RANDOM LEASTSTATES SRCHASH KEY CERTIFICATE PASSWORD ECDH
-%token	EDH CURVE
+%token	EDH CURVE SEED
 %token	<v.string>	STRING
 %token  <v.number>	NUMBER
 %type	<v.string>	hostname interface table value optstring
@@ -177,7 +179,7 @@ typedef struct {
 %type	<v.number>	optssl optsslclient sslcache
 %type	<v.number>	redirect_proto relay_proto match
 %type	<v.number>	action ruleaf key_option
-%type	<v.number>	ssldhparams sslecdhcurve
+%type	<v.number>	ssldhparams sslecdhcurve hashseed
 %type	<v.port>	port
 %type	<v.host>	host
 %type	<v.addr>	address
@@ -728,7 +730,7 @@ tableopts	: CHECK tablecheck
 			table->conf.skip_cnt =
 			    ($2 / conf->sc_interval.tv_sec) - 1;
 		}
-		| MODE dstmode		{
+		| MODE dstmode hashseed	{
 			switch ($2) {
 			case RELAY_DSTMODE_LOADBALANCE:
 			case RELAY_DSTMODE_HASH:
@@ -739,6 +741,7 @@ tableopts	: CHECK tablecheck
 					    "for redirections");
 					YYERROR;
 				}
+				table->conf.hash_seed = $3;
 				/* FALLTHROUGH */
 			case RELAY_DSTMODE_ROUNDROBIN:
 				dstmode = $2;
@@ -755,6 +758,9 @@ tableopts	: CHECK tablecheck
 		}
 		;
 
+hashseed	: /* nothing */		{ $$ = hashseed; }
+		| SEED STRING		{ $$ = hash32_str($2, HASHINIT); }
+
 tablecheck	: ICMP			{ table->conf.check = CHECK_ICMP; }
 		| TCP			{ table->conf.check = CHECK_TCP; }
 		| SSL			{
@@ -1727,6 +1733,7 @@ forwardspec	: STRING port retry	{
 			rlt->rlt_table->conf.flags |= F_USED;
 			rlt->rlt_mode = dstmode;
 			rlt->rlt_flags = F_USED;
+			rlt->rlt_key = rlt->rlt_table->conf.hash_seed;
 			if (!TAILQ_EMPTY(&rlay->rl_tables))
 				rlt->rlt_flags |= F_BACKUP;
 
@@ -2150,6 +2157,7 @@ lookup(char *s)
 		{ "rtlabel",		RTLABEL },
 		{ "sack",		SACK },
 		{ "script",		SCRIPT },
+		{ "seed",		SEED },
 		{ "send",		SEND },
 		{ "session",		SESSION },
 		{ "set",		SET },
@@ -2544,6 +2552,9 @@ load_config(const char *filename, struct relayd *x_conf)
 	conf = x_conf;
 	conf->sc_flags = 0;
 
+	while (hashseed == 0)
+		hashseed = arc4random();
+
 	loadcfg = 1;
 	errors = 0;
 	last_host_id = last_table_id = last_rdr_id = last_proto_id =
diff --git a/usr.sbin/relayd/relay.c b/usr.sbin/relayd/relay.c
index b5d5f8ff165..b3f581d0024 100644
--- a/usr.sbin/relayd/relay.c
+++ b/usr.sbin/relayd/relay.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: relay.c,v 1.175 2014/07/14 00:11:12 bluhm Exp $	*/
+/*	$OpenBSD: relay.c,v 1.176 2014/08/29 09:03:36 blambert Exp $	*/
 
 /*
  * Copyright (c) 2006 - 2014 Reyk Floeter <reyk@openbsd.org>
@@ -72,6 +72,11 @@ void		 relay_accept(int, short, void *);
 void		 relay_input(struct rsession *);
 
 u_int32_t	 relay_hash_addr(struct sockaddr_storage *, u_int32_t);
+int		 relay_host_ring_lookup(u_int32_t, struct table *);
+void		 relay_host_ring_update(struct table *);
+u_int32_t	 relay_host_ring_hash(u_int32_t);
+static int	 relay_host_ring_cmp(const void *, const void *);
+
 
 DH *		 relay_ssl_get_dhparams(int);
 void		 relay_ssl_callback_info(const SSL *, int, int);
@@ -431,7 +436,8 @@ relay_launch(void)
 			case RELAY_DSTMODE_HASH:
 			case RELAY_DSTMODE_SRCHASH:
 				rlt->rlt_key =
-				    hash32_str(rlay->rl_conf.name, HASHINIT);
+				    hash32_str(rlay->rl_conf.name,
+				    rlt->rlt_key);
 				rlt->rlt_key =
 				    hash32_str(rlt->rlt_table->conf.name,
 				    rlt->rlt_key);
@@ -442,6 +448,8 @@ relay_launch(void)
 				if (rlt->rlt_nhosts >= RELAY_MAXHOSTS)
 					fatal("relay_init: "
 					    "too many hosts in table");
+				host->ringkey = relay_hash_addr(&host->conf.ss,
+				    HASHINIT);
 				host->idx = rlt->rlt_nhosts;
 				rlt->rlt_host[rlt->rlt_nhosts++] = host;
 			}
@@ -1232,23 +1240,25 @@ relay_from_table(struct rsession *con)
 		idx = (int)arc4random_uniform(rlt->rlt_nhosts);
 		break;
 	case RELAY_DSTMODE_SRCHASH:
-	case RELAY_DSTMODE_LOADBALANCE:
 		/* Source IP address without port */
 		p = relay_hash_addr(&con->se_in.ss, p);
-		if (rlt->rlt_mode == RELAY_DSTMODE_SRCHASH)
-			break;
-		/* FALLTHROUGH */
+		idx = relay_host_ring_lookup(p, table);
+		break;
+	case RELAY_DSTMODE_LOADBALANCE:
 	case RELAY_DSTMODE_HASH:
+		/* Source IP address without port */
+		p = relay_hash_addr(&con->se_in.ss, p);
 		/* Local "destination" IP address and port */
 		p = relay_hash_addr(&rlay->rl_conf.ss, p);
 		p = hash32_buf(&rlay->rl_conf.port,
 		    sizeof(rlay->rl_conf.port), p);
+		idx = relay_host_ring_lookup(p, table);
 		break;
 	default:
 		fatalx("relay_from_table: unsupported mode");
 		/* NOTREACHED */
 	}
-	if (idx == -1 && (idx = p % rlt->rlt_nhosts) >= RELAY_MAXHOSTS)
+	if (idx == -1)
 		return (-1);
 	host = rlt->rlt_host[idx];
 	DPRINTF("%s: session %d: table %s host %s, p 0x%08x, idx %d",
@@ -2649,6 +2659,67 @@ relay_load_certfiles(struct relay *rlay)
 	return (0);
 }
 
+static int
+relay_host_ring_cmp(const void *aa, const void *bb)
+{
+	const struct host_ring *a = aa;
+	const struct host_ring *b = bb;
+
+	if (a->ringkey < b->ringkey)
+		return (-1);
+	else if (a->ringkey > b->ringkey)
+		return (1);
+	else
+		return (0);
+}
+
+int
+relay_host_ring_lookup(u_int32_t dstkey, struct table *table)
+{
+	struct host_ring	*r;
+	int			 n = table->nhosts;
+
+	if (!table->up)
+		return (-1);
+
+	do {
+		r = &table->host_ring[--n];
+		if (dstkey > r->ringkey)
+			break;
+	} while (n);
+	if (n == 0 && dstkey < r->ringkey)
+		r = &table->host_ring[table->nhosts - 1];
+	return (r->host->idx);
+}
+
+void
+relay_host_ring_update(struct table *table)
+{
+	struct host	*host;
+	int		 nhosts = 0;
+
+	if (table->up == table->lastup)
+		return;
+
+	table->lastup = table->up;
+	bzero(&table->host_ring, sizeof(table->host_ring));
+	if (!table->up)
+		return;
+
+	TAILQ_FOREACH(host, &table->hosts, entry) {
+		if (host->up  != HOST_UP)
+			continue;
+		table->host_ring[nhosts].ringkey = host->ringkey;
+		table->host_ring[nhosts].host = host;
+		nhosts++;
+	}
+
+	if (nhosts)
+		qsort(table->host_ring, nhosts, sizeof(struct host_ring),
+		    relay_host_ring_cmp);
+	table->nhosts = nhosts;
+}
+
 int
 relay_session_cmp(struct rsession *a, struct rsession *b)
 {
diff --git a/usr.sbin/relayd/relayd.conf.5 b/usr.sbin/relayd/relayd.conf.5
index 24f823fcd60..93800a18cb0 100644
--- a/usr.sbin/relayd/relayd.conf.5
+++ b/usr.sbin/relayd/relayd.conf.5
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: relayd.conf.5,v 1.147 2014/07/11 16:59:38 reyk Exp $
+.\"	$OpenBSD: relayd.conf.5,v 1.148 2014/08/29 09:03:36 blambert Exp $
 .\"
 .\" Copyright (c) 2006 - 2014 Reyk Floeter <reyk@openbsd.org>
 .\" Copyright (c) 2006, 2007 Pierre-Yves Ritschard <pyr@openbsd.org>
@@ -15,7 +15,7 @@
 .\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 .\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 .\"
-.Dd $Mdocdate: July 11 2014 $
+.Dd $Mdocdate: August 29 2014 $
 .Dt RELAYD.CONF 5
 .Os
 .Sh NAME
@@ -390,7 +390,7 @@ This will override the global timeout, which is 200 milliseconds by default.
 The following options will set the scheduling algorithm to select a
 host from the specified table:
 .Bl -tag -width Ds
-.It Ic mode hash
+.It Ic mode hash Op Ic seed Ar string
 Balances the outgoing connections across the active hosts based on the
 hashed name of the relay, the hashed name of the table, and the IP
 address and port of the relay.
@@ -406,7 +406,7 @@ active
 .Xr pf 4
 states.
 This mode is only supported by redirections.
-.It Ic mode loadbalance
+.It Ic mode loadbalance Op Ic seed Ar string
 Balances the outgoing connections across the active hosts based on the
 hashed name of the relay, the hashed name of the table, the source IP
 address of the client, and the IP address and port of the relay.
@@ -419,12 +419,24 @@ Distributes the outgoing connections using a round-robin scheduler
 through all active hosts.
 This is the default mode and will be used if no option has been specified.
 This mode is supported by redirections and relays.
-.It Ic mode source-hash
+.It Ic mode source-hash Op Ic seed Ar string
 Balances the outgoing connections across the active hosts based on the
 hashed name of the redirection or relay, the hashed name of the table,
 and the source IP address of the client.
 This mode is only supported by relays.
 .El
+.Pp
+For the
+.Ic hash ,
+.Ic loadbalance ,
+and
+.Ic source-hash
+modes, a random 32-bit hash seed is chosen during configuration.
+In order to facilitate consistent hashing between instances of
+.Xr relayd 8
+operating on multiple hosts, an explicit
+.Ic seed
+string may be specified.
 .Sh REDIRECTIONS
 Redirections represent a
 .Xr pf 4
diff --git a/usr.sbin/relayd/relayd.h b/usr.sbin/relayd/relayd.h
index ffd2aa008dc..4a6a3114d7b 100644
--- a/usr.sbin/relayd/relayd.h
+++ b/usr.sbin/relayd/relayd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: relayd.h,v 1.190 2014/08/18 12:59:00 reyk Exp $	*/
+/*	$OpenBSD: relayd.h,v 1.191 2014/08/29 09:03:36 blambert Exp $	*/
 
 /*
  * Copyright (c) 2006 - 2014 Reyk Floeter <reyk@openbsd.org>
@@ -395,11 +395,17 @@ struct host {
 	u_long			 up_cnt;
 	int			 retry_cnt;
 	int			 idx;
+	u_int32_t		 ringkey;
 	u_int16_t		 he;
 	struct ctl_tcp_event	 cte;
 };
 TAILQ_HEAD(hostlist, host);
 
+struct host_ring {
+	struct host		*host;
+	u_int32_t		 ringkey;
+};
+
 enum host_error {
 	HCE_NONE		= 0,
 	HCE_ABORT,
@@ -462,6 +468,7 @@ struct table_config {
 	char			 digest[41]; /* length of sha1 digest * 2 */
 	u_int8_t		 digest_type;
 	enum forwardmode	 fwdmode;
+	u_int32_t		 hash_seed;
 };
 
 struct table {
@@ -470,6 +477,9 @@ struct table {
 	int			 up;
 	int			 skipped;
 	struct hostlist		 hosts;
+	struct host_ring	 host_ring[RELAY_MAXHOSTS];
+	int			 nhosts;
+	int			 lastup;
 	SSL_CTX			*ssl_ctx;
 	char			*sendbuf;
 };