Support additional scheduling algorithms in the load balancer:

least-states, random, source-hash.  least-states is currently only
supported for redirections and the other ones are currently only
supported by relays.

ok benno@

5 files changed, 83 insertions, 16 deletions

diff --git a/usr.sbin/relayd/parse.y b/usr.sbin/relayd/parse.y
index dc3c7f1b501..3e479c80e73 100644
--- a/usr.sbin/relayd/parse.y
+++ b/usr.sbin/relayd/parse.y
@@ -1,4 +1,4 @@
-/*	$OpenBSD: parse.y,v 1.167 2012/10/04 20:53:30 reyk Exp $	*/
+/*	$OpenBSD: parse.y,v 1.168 2012/10/19 16:49:50 reyk Exp $	*/
 
 /*
  * Copyright (c) 2007-2011 Reyk Floeter <reyk@openbsd.org>
@@ -30,6 +30,7 @@
 #include <sys/stat.h>
 #include <sys/queue.h>
 #include <sys/ioctl.h>
+#include <sys/hash.h>
 
 #include <net/if.h>
 #include <net/pfvar.h>
@@ -157,6 +158,7 @@ typedef struct {
 %token	RETURN ROUNDROBIN ROUTE SACK SCRIPT SEND SESSION SOCKET SPLICE
 %token	SSL STICKYADDR STYLE TABLE TAG TCP TIMEOUT TO ROUTER RTLABEL
 %token	TRANSPARENT TRAP UPDATES URL VIRTUAL WITH TTL RTABLE MATCH
+%token	RANDOM LEASTSTATES SRCHASH
 %token	<v.string>	STRING
 %token  <v.number>	NUMBER
 %type	<v.string>	hostname interface table
@@ -484,9 +486,15 @@ rdroptsl	: forwardmode TO tablespec interface	{
 			if (rdr->table) {
 				rdr->backup = $3;
 				rdr->conf.backup_id = $3->conf.id;
+				if (dstmode != rdr->conf.mode) {
+					yyerror("backup table for %s with "
+					    "different mode", rdr->conf.name);
+					YYERROR;
+				}
 			} else {
 				rdr->table = $3;
 				rdr->conf.table_id = $3->conf.id;
+				rdr->conf.mode = dstmode;
 			}
 			$3->conf.fwdmode = $1;
 			$3->conf.rdrid = rdr->conf.id;
@@ -675,6 +683,8 @@ tableopts	: CHECK tablecheck
 			switch ($2) {
 			case RELAY_DSTMODE_LOADBALANCE:
 			case RELAY_DSTMODE_HASH:
+			case RELAY_DSTMODE_SRCHASH:
+			case RELAY_DSTMODE_RANDOM:
 				if (rdr != NULL) {
 					yyerror("mode not supported "
 					    "for redirections");
@@ -684,6 +694,14 @@ tableopts	: CHECK tablecheck
 			case RELAY_DSTMODE_ROUNDROBIN:
 				dstmode = $2;
 				break;
+			case RELAY_DSTMODE_LEASTSTATES:
+				if (rdr == NULL) {
+					yyerror("mode not supported "
+					    "for relays");
+					YYERROR;
+				}
+				dstmode = $2;
+				break;
 			}
 		}
 		;
@@ -1435,6 +1453,9 @@ dstmode		: /* empty */		{ $$ = RELAY_DSTMODE_DEFAULT; }
 		| LOADBALANCE		{ $$ = RELAY_DSTMODE_LOADBALANCE; }
 		| ROUNDROBIN		{ $$ = RELAY_DSTMODE_ROUNDROBIN; }
 		| HASH			{ $$ = RELAY_DSTMODE_HASH; }
+		| LEASTSTATES		{ $$ = RELAY_DSTMODE_LEASTSTATES; }
+		| SRCHASH		{ $$ = RELAY_DSTMODE_SRCHASH; }
+		| RANDOM		{ $$ = RELAY_DSTMODE_RANDOM; }
 		;
 
 router		: ROUTER STRING		{
@@ -1794,6 +1815,7 @@ lookup(char *s)
 		{ "interval",		INTERVAL },
 		{ "ip",			IP },
 		{ "label",		LABEL },
+		{ "least-states",	LEASTSTATES },
 		{ "listen",		LISTEN },
 		{ "loadbalance",	LOADBALANCE },
 		{ "log",		LOG },
@@ -1814,6 +1836,7 @@ lookup(char *s)
 		{ "priority",		PRIORITY },
 		{ "protocol",		PROTO },
 		{ "query",		QUERYSTR },
+		{ "random",		RANDOM },
 		{ "real",		REAL },
 		{ "redirect",		REDIRECT },
 		{ "relay",		RELAY },
@@ -1832,6 +1855,7 @@ lookup(char *s)
 		{ "send",		SEND },
 		{ "session",		SESSION },
 		{ "socket",		SOCKET },
+		{ "source-hash",	SRCHASH },
 		{ "splice",		SPLICE },
 		{ "ssl",		SSL },
 		{ "sticky-address",	STICKYADDR },
diff --git a/usr.sbin/relayd/pfe_filter.c b/usr.sbin/relayd/pfe_filter.c
index a92871c1dea..1bdc302f22d 100644
--- a/usr.sbin/relayd/pfe_filter.c
+++ b/usr.sbin/relayd/pfe_filter.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pfe_filter.c,v 1.51 2012/10/04 20:53:30 reyk Exp $	*/
+/*	$OpenBSD: pfe_filter.c,v 1.52 2012/10/19 16:49:50 reyk Exp $	*/
 
 /*
  * Copyright (c) 2006 Pierre-Yves Ritschard <pyr@openbsd.org>
@@ -483,7 +483,18 @@ sync_ruleset(struct relayd *env, struct rdr *rdr, int enable)
 			    ntohs(rdr->table->conf.port);
 			rio.rule.rdr.port_op = PF_OP_EQ;
 		}
-		rio.rule.rdr.opts = PF_POOL_ROUNDROBIN;
+
+		switch (rdr->conf.mode) {
+		case RELAY_DSTMODE_ROUNDROBIN:
+			rio.rule.rdr.opts = PF_POOL_ROUNDROBIN;
+			break;
+		case RELAY_DSTMODE_LEASTSTATES:
+			rio.rule.rdr.opts = PF_POOL_LEASTSTATES;
+			break;
+		default:
+			fatalx("sync_ruleset: unsupported mode");
+			/* NOTREACHED */
+		}
 		if (rdr->conf.flags & F_STICKY)
 			rio.rule.rdr.opts |= PF_POOL_STICKYADDR;
 
diff --git a/usr.sbin/relayd/relay.c b/usr.sbin/relayd/relay.c
index f31c6420eba..72729c3c279 100644
--- a/usr.sbin/relayd/relay.c
+++ b/usr.sbin/relayd/relay.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: relay.c,v 1.156 2012/10/04 20:53:30 reyk Exp $	*/
+/*	$OpenBSD: relay.c,v 1.157 2012/10/19 16:49:50 reyk Exp $	*/
 
 /*
  * Copyright (c) 2006 - 2012 Reyk Floeter <reyk@openbsd.org>
@@ -387,10 +387,12 @@ relay_launch(void)
 		TAILQ_FOREACH(rlt, &rlay->rl_tables, rlt_entry) {
 			switch (rlt->rlt_mode) {
 			case RELAY_DSTMODE_ROUNDROBIN:
+			case RELAY_DSTMODE_RANDOM:
 				rlt->rlt_key = 0;
 				break;
 			case RELAY_DSTMODE_LOADBALANCE:
 			case RELAY_DSTMODE_HASH:
+			case RELAY_DSTMODE_SRCHASH:
 				rlt->rlt_key =
 				    hash32_str(rlay->rl_conf.name, HASHINIT);
 				rlt->rlt_key =
@@ -1107,7 +1109,7 @@ relay_from_table(struct rsession *con)
 	struct relay_table	*rlt = NULL;
 	struct table		*table = NULL;
 	u_int32_t		 p = con->se_hashkey;
-	int			 idx = 0;
+	int			 idx = -1;
 
 	/* the table is already selected */
 	if (con->se_table != NULL) {
@@ -1145,16 +1147,28 @@ relay_from_table(struct rsession *con)
 			rlt->rlt_key = 0;
 		idx = (int)rlt->rlt_key;
 		break;
+	case RELAY_DSTMODE_RANDOM:
+		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 */
 	case RELAY_DSTMODE_HASH:
+		/* 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);
-		if ((idx = p % rlt->rlt_nhosts) >= RELAY_MAXHOSTS)
-			return (-1);
+		break;
+	default:
+		fatalx("relay_from_table: unsupported mode");
+		/* NOTREACHED */
 	}
+	if (idx == -1 && (idx = p % rlt->rlt_nhosts) >= RELAY_MAXHOSTS)
+		return (-1);
 	host = rlt->rlt_host[idx];
 	DPRINTF("%s: session %d: table %s host %s, p 0x%08x, idx %d",
 	    __func__, con->se_id, table->conf.name, host->conf.name, p, idx);
diff --git a/usr.sbin/relayd/relayd.conf.5 b/usr.sbin/relayd/relayd.conf.5
index 1dce6f56e48..9e539901eaf 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.130 2012/10/03 08:33:31 reyk Exp $
+.\"	$OpenBSD: relayd.conf.5,v 1.131 2012/10/19 16:49:50 reyk Exp $
 .\"
 .\" Copyright (c) 2006, 2007 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: October 3 2012 $
+.Dd $Mdocdate: October 19 2012 $
 .Dt RELAYD.CONF 5
 .Os
 .Sh NAME
@@ -385,7 +385,7 @@ host from the specified table:
 .Bl -tag -width Ds
 .It Ic mode hash
 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
+hashed name of the relay, the hashed name of the table, and the IP
 address and port of the relay.
 Additional input can be fed into the
 hash by looking at HTTP headers and GET variables;
@@ -393,16 +393,30 @@ see the
 .Sx PROTOCOLS
 section below.
 This mode is only supported by relays.
+.It Ic mode least-states
+Forward each outgoing connection to the active host with the least
+active
+.Xr pf 4
+states.
+This mode is only supported by redirections.
 .It Ic mode loadbalance
 Balances the outgoing connections across the active hosts based on the
-hashed name of the relay, the hashed name of the table, the IP
-address and port of the relay and the IP address of the client.
+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.
+This mode is only supported by relays.
+.It Ic mode random
+Distributes the outgoing connections randomly through all active hosts.
 This mode is only supported by relays.
 .It Ic mode roundrobin
 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
+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
 .Sh REDIRECTIONS
 Redirections represent a
diff --git a/usr.sbin/relayd/relayd.h b/usr.sbin/relayd/relayd.h
index db459cdc486..3ef3f6cfafa 100644
--- a/usr.sbin/relayd/relayd.h
+++ b/usr.sbin/relayd/relayd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: relayd.h,v 1.161 2012/10/04 20:53:30 reyk Exp $	*/
+/*	$OpenBSD: relayd.h,v 1.162 2012/10/19 16:49:50 reyk Exp $	*/
 
 /*
  * Copyright (c) 2006 - 2012 Reyk Floeter <reyk@openbsd.org>
@@ -414,6 +414,7 @@ struct rdr_config {
 	in_port_t		 port;
 	objid_t			 table_id;
 	objid_t			 backup_id;
+	int			 mode;
 	char			 name[SRV_NAME_SIZE];
 	char			 tag[TAG_NAME_SIZE];
 	struct timeval		 timeout;
@@ -648,9 +649,12 @@ struct relay {
 TAILQ_HEAD(relaylist, relay);
 
 enum dstmode {
-	RELAY_DSTMODE_LOADBALANCE	= 0,
-	RELAY_DSTMODE_ROUNDROBIN	= 1,
-	RELAY_DSTMODE_HASH		= 2
+	RELAY_DSTMODE_LOADBALANCE = 0,
+	RELAY_DSTMODE_ROUNDROBIN,
+	RELAY_DSTMODE_HASH,
+	RELAY_DSTMODE_SRCHASH,
+	RELAY_DSTMODE_LEASTSTATES,
+	RELAY_DSTMODE_RANDOM
 };
 #define RELAY_DSTMODE_DEFAULT		RELAY_DSTMODE_ROUNDROBIN