Simplify the code that handles the HTTP headers by using an RB tree

with associated lists instead of the complicated lookup table and
"others" list.  This might add a little malloc overhead for common
headers but also fixes some issues like the handling of repeated
headers -  for example, handling of multiple "Set-Cookie" headers.

ok bluhm@ (regress part)
ok benno@

9 files changed, 184 insertions, 486 deletions

diff --git a/regress/usr.sbin/relayd/args-http-change-cookie.pl b/regress/usr.sbin/relayd/args-http-change-cookie.pl
index ac0dd71c83f..c6808c98159 100644
--- a/regress/usr.sbin/relayd/args-http-change-cookie.pl
+++ b/regress/usr.sbin/relayd/args-http-change-cookie.pl
@@ -1,7 +1,7 @@
 use strict;
 use warnings;
 
-my $name = "X-Set-Cookie";
+my $name = "Set-Cookie";
 my %header = ("$name" => [ "test=a;", "test=b;" ]);
 our %args = (
     client => {
diff --git a/regress/usr.sbin/relayd/args-http-change-path.pl b/regress/usr.sbin/relayd/args-http-change-path.pl
index 41a547d672b..c4070b2a76b 100644
--- a/regress/usr.sbin/relayd/args-http-change-path.pl
+++ b/regress/usr.sbin/relayd/args-http-change-path.pl
@@ -13,7 +13,7 @@ our %args = (
 	    'match request path set "*" value "/foopath" \
 		url log "*"',
 	],
-	loggrep => { qr/\, done\, \[foo.bar\/foopath\]/ => 1 },
+	loggrep => { qr/ (?:done|last write \(done\)), \[foo.bar\/foopath\]/ => 1 },
     },
     server => {
 	func => \&http_server,
diff --git a/regress/usr.sbin/relayd/args-http-remove.pl b/regress/usr.sbin/relayd/args-http-remove.pl
index 6cc061d177a..45800210b6c 100644
--- a/regress/usr.sbin/relayd/args-http-remove.pl
+++ b/regress/usr.sbin/relayd/args-http-remove.pl
@@ -16,7 +16,7 @@ our %args = (
     relayd => {
 	protocol => [ "http",
 	    'match response header remove X-Header-Foo',
-	    'match response header log "*"',
+	    'match response header log "*Foo"',
 	],
 	loggrep => { qr/ (?:done|last write \(done\)), \[X-Header-Foo: foo \(removed\)\s*\]/ => 1 },
     },
diff --git a/usr.sbin/relayd/config.c b/usr.sbin/relayd/config.c
index edc97759585..df17935da61 100644
--- a/usr.sbin/relayd/config.c
+++ b/usr.sbin/relayd/config.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: config.c,v 1.16 2014/07/09 23:30:34 reyk Exp $	*/
+/*	$OpenBSD: config.c,v 1.17 2014/07/11 11:48:50 reyk Exp $	*/
 
 /*
  * Copyright (c) 2011 - 2014 Reyk Floeter <reyk@openbsd.org>
@@ -762,6 +762,7 @@ config_getrule(struct relayd *env, struct imsg *imsg)
 
 	memset(&rule->rule_kv[0], 0, sizeof(struct kv));
 	for (i = 1; i < KEY_TYPE_MAX; i++) {
+		TAILQ_INIT(&rule->rule_kv[i].kv_children);
 		GETKV(i, key);
 		GETKV(i, value);
 	}
diff --git a/usr.sbin/relayd/http.h b/usr.sbin/relayd/http.h
index cd7a931030b..0cf9b790244 100644
--- a/usr.sbin/relayd/http.h
+++ b/usr.sbin/relayd/http.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: http.h,v 1.1 2014/07/09 16:42:05 reyk Exp $	*/
+/*	$OpenBSD: http.h,v 1.2 2014/07/11 11:48:50 reyk Exp $	*/
 
 /*
  * Copyright (c) 2012 - 2014 Reyk Floeter <reyk@openbsd.org>
@@ -72,278 +72,6 @@ struct http_method {
 	{ HTTP_METHOD_NONE,		NULL }		\
 }
 
-enum httpheader {
-	HTTP_HEADER_NONE	= 0,
-
-	/* HTTP Header Field Registration, RFC 4229 */
-	HTTP_HEADER_A_IM,
-	HTTP_HEADER_ACCEPT,
-	HTTP_HEADER_ACCEPT_ADDITIONS,
-	HTTP_HEADER_ACCEPT_CHARSET,
-	HTTP_HEADER_ACCEPT_ENCODING,
-	HTTP_HEADER_ACCEPT_FEATURES,
-	HTTP_HEADER_ACCEPT_LANGUAGE,
-	HTTP_HEADER_ACCEPT_RANGES,
-	HTTP_HEADER_AGE,
-	HTTP_HEADER_ALLOW,
-	HTTP_HEADER_ALTERNATES,
-	HTTP_HEADER_AUTHENTICATION_INFO,
-	HTTP_HEADER_AUTHORIZATION,
-	HTTP_HEADER_C_EXT,
-	HTTP_HEADER_C_MAN,
-	HTTP_HEADER_C_OPT,
-	HTTP_HEADER_C_PEP,
-	HTTP_HEADER_C_PEP_INFO,
-	HTTP_HEADER_CACHE_CONTROL,
-	HTTP_HEADER_CONNECTION,
-	HTTP_HEADER_CONTENT_BASE,
-	HTTP_HEADER_CONTENT_DISPOSITION,
-	HTTP_HEADER_CONTENT_ENCODING,
-	HTTP_HEADER_CONTENT_ID,
-	HTTP_HEADER_CONTENT_LANGUAGE,
-	HTTP_HEADER_CONTENT_LENGTH,
-	HTTP_HEADER_CONTENT_LOCATION,
-	HTTP_HEADER_CONTENT_MD5,
-	HTTP_HEADER_CONTENT_RANGE,
-	HTTP_HEADER_CONTENT_SCRIPT_TYPE,
-	HTTP_HEADER_CONTENT_STYLE_TYPE,
-	HTTP_HEADER_CONTENT_TYPE,
-	HTTP_HEADER_CONTENT_VERSION,
-	HTTP_HEADER_COOKIE,
-	HTTP_HEADER_COOKIE2,
-	HTTP_HEADER_DAV,
-	HTTP_HEADER_DATE,
-	HTTP_HEADER_DEFAULT_STYLE,
-	HTTP_HEADER_DELTA_BASE,
-	HTTP_HEADER_DEPTH,
-	HTTP_HEADER_DERIVED_FROM,
-	HTTP_HEADER_DESTINATION,
-	HTTP_HEADER_DIFFERENTIAL_ID,
-	HTTP_HEADER_DIGEST,
-	HTTP_HEADER_ETAG,
-	HTTP_HEADER_EXPECT,
-	HTTP_HEADER_EXPIRES,
-	HTTP_HEADER_EXT,
-	HTTP_HEADER_FROM,
-	HTTP_HEADER_GETPROFILE,
-	HTTP_HEADER_HOST,
-	HTTP_HEADER_IM,
-	HTTP_HEADER_IF,
-	HTTP_HEADER_IF_MATCH,
-	HTTP_HEADER_IF_MODIFIED_SINCE,
-	HTTP_HEADER_IF_NONE_MATCH,
-	HTTP_HEADER_IF_RANGE,
-	HTTP_HEADER_IF_UNMODIFIED_SINCE,
-	HTTP_HEADER_KEEP_ALIVE,
-	HTTP_HEADER_LABEL,
-	HTTP_HEADER_LAST_MODIFIED,
-	HTTP_HEADER_LINK,
-	HTTP_HEADER_LOCATION,
-	HTTP_HEADER_LOCK_TOKEN,
-	HTTP_HEADER_MIME_VERSION,
-	HTTP_HEADER_MAN,
-	HTTP_HEADER_MAX_FORWARDS,
-	HTTP_HEADER_METER,
-	HTTP_HEADER_NEGOTIATE,
-	HTTP_HEADER_OPT,
-	HTTP_HEADER_ORDERING_TYPE,
-	HTTP_HEADER_OVERWRITE,
-	HTTP_HEADER_P3P,
-	HTTP_HEADER_PEP,
-	HTTP_HEADER_PICS_LABEL,
-	HTTP_HEADER_PEP_INFO,
-	HTTP_HEADER_POSITION,
-	HTTP_HEADER_PRAGMA,
-	HTTP_HEADER_PROFILEOBJECT,
-	HTTP_HEADER_PROTOCOL,
-	HTTP_HEADER_PROTOCOL_INFO,
-	HTTP_HEADER_PROTOCOL_QUERY,
-	HTTP_HEADER_PROTOCOL_REQUEST,
-	HTTP_HEADER_PROXY_AUTHENTICATE,
-	HTTP_HEADER_PROXY_AUTHENTICATION_INFO,
-	HTTP_HEADER_PROXY_AUTHORIZATION,
-	HTTP_HEADER_PROXY_FEATURES,
-	HTTP_HEADER_PROXY_INSTRUCTION,
-	HTTP_HEADER_PUBLIC,
-	HTTP_HEADER_RANGE,
-	HTTP_HEADER_REFERER,
-	HTTP_HEADER_RETRY_AFTER,
-	HTTP_HEADER_SAFE,
-	HTTP_HEADER_SECURITY_SCHEME,
-	HTTP_HEADER_SERVER,
-	HTTP_HEADER_SET_COOKIE,
-	HTTP_HEADER_SET_COOKIE2,
-	HTTP_HEADER_SETPROFILE,
-	HTTP_HEADER_SOAPACTION,
-	HTTP_HEADER_STATUS_URI,
-	HTTP_HEADER_SURROGATE_CAPABILITY,
-	HTTP_HEADER_SURROGATE_CONTROL,
-	HTTP_HEADER_TCN,
-	HTTP_HEADER_TE,
-	HTTP_HEADER_TIMEOUT,
-	HTTP_HEADER_TRAILER,
-	HTTP_HEADER_TRANSFER_ENCODING,
-	HTTP_HEADER_URI,
-	HTTP_HEADER_UPGRADE,
-	HTTP_HEADER_USER_AGENT,
-	HTTP_HEADER_VARIANT_VARY,
-	HTTP_HEADER_VARY,
-	HTTP_HEADER_VIA,
-	HTTP_HEADER_WWW_AUTHENTICATE,
-	HTTP_HEADER_WANT_DIGEST,
-	HTTP_HEADER_WARNING,
-
-	/* PATCH, RFC 5789 */
-	HTTP_HEADER_ACCEPT_PATCH,
-
-	/* Other extensions */
-	HTTP_HEADER_X_REQUESTED_WITH,	/* AJAX */
-	HTTP_HEADER_X_FORWARDED_FOR,
-	HTTP_HEADER_X_FORWARDED_BY,
-	HTTP_HEADER_X_POWERED_BY,
-	HTTP_HEADER_X_XSS_PROTECTION,
-	HTTP_HEADER_ORIGIN,		/* Anti-XSRF */
-	HTTP_HEADER_DNT,		/* Do-Not-Track */
-
-	/* Array size */
-	HTTP_HEADER_MAX,
-#define	HTTP_HEADER_OTHER		HTTP_HEADER_MAX
-};
-
-struct http_header {
-	enum httpheader		 header_id;
-	const char		*header_name;
-	int			 header_isused;
-};
-/* Has to be sorted alphabetically */
-#define HTTP_HEADERS		{					\
-	{ HTTP_HEADER_ACCEPT,			"Accept" },		\
-	{ HTTP_HEADER_ACCEPT_ADDITIONS,		"Accept-Additions" },	\
-	{ HTTP_HEADER_ACCEPT_CHARSET,		"Accept-Charset" },	\
-	{ HTTP_HEADER_ACCEPT_ENCODING,		"Accept-Encoding" },	\
-	{ HTTP_HEADER_ACCEPT_FEATURES,		"Accept-Features" },	\
-	{ HTTP_HEADER_ACCEPT_LANGUAGE,		"Accept-Language" },	\
-	{ HTTP_HEADER_ACCEPT_PATCH,		"Accept-Patch" },	\
-	{ HTTP_HEADER_ACCEPT_RANGES,		"Accept-Ranges" },	\
-	{ HTTP_HEADER_AGE,			"Age" },		\
-	{ HTTP_HEADER_ALLOW,			"Allow" },		\
-	{ HTTP_HEADER_ALTERNATES,		"Alternates" },		\
-	{ HTTP_HEADER_AUTHENTICATION_INFO,	"Authentication-Info" },\
-	{ HTTP_HEADER_AUTHORIZATION,		"Authorization" },	\
-	{ HTTP_HEADER_A_IM,			"A-IM" },		\
-	{ HTTP_HEADER_CACHE_CONTROL,		"Cache-Control" },	\
-	{ HTTP_HEADER_CONNECTION,		"Connection" },		\
-	{ HTTP_HEADER_CONTENT_BASE,		"Content-Base" },	\
-	{ HTTP_HEADER_CONTENT_DISPOSITION,	"Content-Disposition" },\
-	{ HTTP_HEADER_CONTENT_ENCODING,		"Content-Encoding" },	\
-	{ HTTP_HEADER_CONTENT_ID,		"Content-ID" },		\
-	{ HTTP_HEADER_CONTENT_LANGUAGE,		"Content-Language" },	\
-	{ HTTP_HEADER_CONTENT_LENGTH,		"Content-Length" },	\
-	{ HTTP_HEADER_CONTENT_LOCATION,		"Content-Location" },	\
-	{ HTTP_HEADER_CONTENT_MD5,		"Content-MD5" },	\
-	{ HTTP_HEADER_CONTENT_RANGE,		"Content-Range" },	\
-	{ HTTP_HEADER_CONTENT_SCRIPT_TYPE,	"Content-Script-Type" },\
-	{ HTTP_HEADER_CONTENT_STYLE_TYPE,	"Content-Style-Type" },	\
-	{ HTTP_HEADER_CONTENT_TYPE,		"Content-Type" },	\
-	{ HTTP_HEADER_CONTENT_VERSION,		"Content-Version" },	\
-	{ HTTP_HEADER_COOKIE,			"Cookie" },		\
-	{ HTTP_HEADER_COOKIE2,			"Cookie2" },		\
-	{ HTTP_HEADER_C_EXT,			"C-Ext" },		\
-	{ HTTP_HEADER_C_MAN,			"C-Man" },		\
-	{ HTTP_HEADER_C_OPT,			"C-Opt" },		\
-	{ HTTP_HEADER_C_PEP,			"C-PEP" },		\
-	{ HTTP_HEADER_C_PEP_INFO,		"C-PEP-Info" },		\
-	{ HTTP_HEADER_DATE,			"Date" },		\
-	{ HTTP_HEADER_DAV,			"DAV" },		\
-	{ HTTP_HEADER_DEFAULT_STYLE,		"Default-Style" },	\
-	{ HTTP_HEADER_DELTA_BASE,		"Delta-Base" },		\
-	{ HTTP_HEADER_DEPTH,			"Depth" },		\
-	{ HTTP_HEADER_DERIVED_FROM,		"Derived-From" },	\
-	{ HTTP_HEADER_DESTINATION,		"Destination" },	\
-	{ HTTP_HEADER_DIFFERENTIAL_ID,		"Differential-Id" },	\
-	{ HTTP_HEADER_DIGEST,			"Digest" },		\
-	{ HTTP_HEADER_DNT,			"DNT" },		\
-	{ HTTP_HEADER_ETAG,			"ETag" },		\
-	{ HTTP_HEADER_EXPECT,			"Expect" },		\
-	{ HTTP_HEADER_EXPIRES,			"Expires" },		\
-	{ HTTP_HEADER_EXT,			"Ext" },		\
-	{ HTTP_HEADER_FROM,			"From" },		\
-	{ HTTP_HEADER_GETPROFILE,		"GetProfile" },		\
-	{ HTTP_HEADER_HOST,			"Host", 1 /* used */ },	\
-	{ HTTP_HEADER_IF,			"If" },			\
-	{ HTTP_HEADER_IF_MATCH,			"If-Match" },		\
-	{ HTTP_HEADER_IF_MODIFIED_SINCE,	"If-Modified-Since" },	\
-	{ HTTP_HEADER_IF_NONE_MATCH,		"If-None-Match" },	\
-	{ HTTP_HEADER_IF_RANGE,			"If-Range" },		\
-	{ HTTP_HEADER_IF_UNMODIFIED_SINCE,	"If-Unmodified-Since" },\
-	{ HTTP_HEADER_IM,			"IM" },			\
-	{ HTTP_HEADER_KEEP_ALIVE,		"Keep-Alive" },		\
-	{ HTTP_HEADER_LABEL,			"Label" },		\
-	{ HTTP_HEADER_LAST_MODIFIED,		"Last-Modified" },	\
-	{ HTTP_HEADER_LINK,			"Link" },		\
-	{ HTTP_HEADER_LOCATION,			"Location" },		\
-	{ HTTP_HEADER_LOCK_TOKEN,		"Lock-Token" },		\
-	{ HTTP_HEADER_MAN,			"Man" },		\
-	{ HTTP_HEADER_MAX_FORWARDS,		"Max-Forwards" },	\
-	{ HTTP_HEADER_METER,			"Meter" },		\
-	{ HTTP_HEADER_MIME_VERSION,		"MIME-Version" },	\
-	{ HTTP_HEADER_NEGOTIATE,		"Negotiate" },		\
-	{ HTTP_HEADER_OPT,			"Opt" },		\
-	{ HTTP_HEADER_ORDERING_TYPE,		"Ordering-Type" },	\
-	{ HTTP_HEADER_ORIGIN,			"Origin" },		\
-	{ HTTP_HEADER_OVERWRITE,		"Overwrite" },		\
-	{ HTTP_HEADER_P3P,			"P3P" },		\
-	{ HTTP_HEADER_PEP,			"PEP" },		\
-	{ HTTP_HEADER_PEP_INFO,			"Pep-Info" },		\
-	{ HTTP_HEADER_PICS_LABEL,		"PICS-Label" },		\
-	{ HTTP_HEADER_POSITION,			"Position" },		\
-	{ HTTP_HEADER_PRAGMA,			"Pragma" },		\
-	{ HTTP_HEADER_PROFILEOBJECT,		"ProfileObject" },	\
-	{ HTTP_HEADER_PROTOCOL,			"Protocol" },		\
-	{ HTTP_HEADER_PROTOCOL_INFO,		"Protocol-Info" },	\
-	{ HTTP_HEADER_PROTOCOL_QUERY,		"Protocol-Query" },	\
-	{ HTTP_HEADER_PROTOCOL_REQUEST,		"Protocol-Request" },	\
-	{ HTTP_HEADER_PROXY_AUTHENTICATE,	"Proxy-Authenticate" },	\
-	{ HTTP_HEADER_PROXY_AUTHENTICATION_INFO,"Proxy-Authenticate-Info" },\
-	{ HTTP_HEADER_PROXY_AUTHORIZATION,	"Proxy-Authorization" },\
-	{ HTTP_HEADER_PROXY_FEATURES,		"Proxy-Features" },	\
-	{ HTTP_HEADER_PROXY_INSTRUCTION,	"Proxy-Instruction" },	\
-	{ HTTP_HEADER_PUBLIC,			"Public" },		\
-	{ HTTP_HEADER_RANGE,			"Range" },		\
-	{ HTTP_HEADER_REFERER,			"Referer" },		\
-	{ HTTP_HEADER_RETRY_AFTER,		"Retry-After" },	\
-	{ HTTP_HEADER_SAFE,			"Safe" },		\
-	{ HTTP_HEADER_SECURITY_SCHEME,		"Security-Scheme" },	\
-	{ HTTP_HEADER_SERVER,			"Server" },		\
-	{ HTTP_HEADER_SETPROFILE,		"SetProfile" },		\
-	{ HTTP_HEADER_SET_COOKIE,		"Set-Cookie" },		\
-	{ HTTP_HEADER_SET_COOKIE2,		"Set-Cookie2" },	\
-	{ HTTP_HEADER_SOAPACTION,		"SoapAction" },		\
-	{ HTTP_HEADER_STATUS_URI,		"Status-URI" },		\
-	{ HTTP_HEADER_SURROGATE_CAPABILITY,	"Surrogate-Capability" },\
-	{ HTTP_HEADER_SURROGATE_CONTROL,	"Surrogate-Control" },	\
-	{ HTTP_HEADER_TCN,			"TCN" },		\
-	{ HTTP_HEADER_TE,			"TE" },			\
-	{ HTTP_HEADER_TIMEOUT,			"Timeout" },		\
-	{ HTTP_HEADER_TRAILER,			"Trailer" },		\
-	{ HTTP_HEADER_TRANSFER_ENCODING,	"Transfer-Encoding" },	\
-	{ HTTP_HEADER_UPGRADE,			"Upgrade" },		\
-	{ HTTP_HEADER_URI,			"URI" },		\
-	{ HTTP_HEADER_USER_AGENT,		"User-Agent" },		\
-	{ HTTP_HEADER_VARIANT_VARY,		"Variant-Vary" },	\
-	{ HTTP_HEADER_VARY,			"Vary" },		\
-	{ HTTP_HEADER_VIA,			"Via" },		\
-	{ HTTP_HEADER_WANT_DIGEST,		"Want-Digest" },	\
-	{ HTTP_HEADER_WARNING,			"Warning" },		\
-	{ HTTP_HEADER_WWW_AUTHENTICATE,		"WWW-Authenticate" },	\
-	{ HTTP_HEADER_X_FORWARDED_BY,		"X-Forwarded-By" },	\
-	{ HTTP_HEADER_X_FORWARDED_FOR,		"X-Forwarded-For" },	\
-	{ HTTP_HEADER_X_POWERED_BY,		"X-Powered-By" },	\
-	{ HTTP_HEADER_X_REQUESTED_WITH,		"X-Requested-With" },	\
-	{ HTTP_HEADER_X_XSS_PROTECTION,		"X-XSS-Protection" },	\
-	{ HTTP_HEADER_OTHER,			NULL }			\
-}
-
 /* Used during runtime */
 struct http_descriptor {
 	struct kv		 http_pathquery;
@@ -359,13 +87,9 @@ struct http_descriptor {
 	enum httpmethod		 http_method;
 	int			 http_chunked;
 
-	/*
-	 * A linked list of headers and an array with pointers
-	 * pointing to well-known headers that have been found to
-	 * speed up lookups.
-	 */
-	struct kvlist		 http_headers;
-	struct kv		*http_header[HTTP_HEADER_MAX];
+	/* A tree of headers and attached lists for repeated headers. */
+	struct kvtree		 http_headers;
+	struct kv		*http_lastheader;
 };
 
 #endif /* _RELAYD_HTTP_H */
diff --git a/usr.sbin/relayd/parse.y b/usr.sbin/relayd/parse.y
index 624ea6cb5f2..3a41bff6269 100644
--- a/usr.sbin/relayd/parse.y
+++ b/usr.sbin/relayd/parse.y
@@ -1,4 +1,4 @@
-/*	$OpenBSD: parse.y,v 1.184 2014/07/09 16:42:05 reyk Exp $	*/
+/*	$OpenBSD: parse.y,v 1.185 2014/07/11 11:48:50 reyk Exp $	*/
 
 /*
  * Copyright (c) 2007 - 2014 Reyk Floeter <reyk@openbsd.org>
@@ -1154,7 +1154,7 @@ ruleopts_t	: ruleopts ruleopts_t
 ruleopts	: METHOD STRING					{
 			u_int	id;
 			if ((id = relay_httpmethod_byname($2)) ==
-			    HTTP_HEADER_NONE) {
+			    HTTP_METHOD_NONE) {
 				yyerror("unknown HTTP method currently not "
 				    "supported");
 				free($2);
@@ -1186,8 +1186,6 @@ ruleopts	: METHOD STRING					{
 			keytype = KEY_TYPE_HEADER;
 			memset(&rule->rule_kv[keytype], 0,
 			    sizeof(rule->rule_kv[keytype]));
-			rule->rule_kv[keytype].kv_header_id =
-			    relay_httpheader_byname($3);
 			rule->rule_kv[keytype].kv_option = $2;
 			rule->rule_kv[keytype].kv_key = strdup($3);
 			rule->rule_kv[keytype].kv_value = (($4 != NULL) ?
diff --git a/usr.sbin/relayd/relay_http.c b/usr.sbin/relayd/relay_http.c
index f4d235162f7..7bf18cc9501 100644
--- a/usr.sbin/relayd/relay_http.c
+++ b/usr.sbin/relayd/relay_http.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: relay_http.c,v 1.22 2014/07/10 20:02:32 bluhm Exp $	*/
+/*	$OpenBSD: relay_http.c,v 1.23 2014/07/11 11:48:50 reyk Exp $	*/
 
 /*
  * Copyright (c) 2006 - 2014 Reyk Floeter <reyk@openbsd.org>
@@ -59,6 +59,7 @@ void		 relay_read_httpcontent(struct bufferevent *, void *);
 void		 relay_read_httpchunks(struct bufferevent *, void *);
 char		*relay_expand_http(struct ctl_relay_event *, char *,
 		    char *, size_t);
+int		 relay_writeheader_kv(struct ctl_relay_event *, struct kv *);
 int		 relay_writeheader_http(struct ctl_relay_event *,
 		    struct ctl_relay_event *);
 int		 relay_writerequest_http(struct ctl_relay_event *,
@@ -67,7 +68,6 @@ int		 relay_writeresponse_http(struct ctl_relay_event *,
 		    struct ctl_relay_event *);
 void		 relay_reset_http(struct ctl_relay_event *);
 static int	 relay_httpmethod_cmp(const void *, const void *);
-static int	 relay_httpheader_cmp(const void *, const void *);
 int		 relay_httpquery_test(struct ctl_relay_event *,
 		    struct relay_rule *, struct kvlist *);
 int		 relay_httpheader_test(struct ctl_relay_event *,
@@ -86,7 +86,6 @@ void		 relay_httpdesc_free(struct http_descriptor *);
 static struct relayd	*env = NULL;
 
 static struct http_method	 http_methods[] = HTTP_METHODS;
-static struct http_header	 http_headers[] = HTTP_HEADERS;
 
 void
 relay_http(struct relayd *x_env)
@@ -100,9 +99,6 @@ relay_http(struct relayd *x_env)
 	qsort(http_methods, sizeof(http_methods) /
 	    sizeof(http_methods[0]) - 1,
 	    sizeof(http_methods[0]), relay_httpmethod_cmp);
-	qsort(http_headers, sizeof(http_headers) /
-	    sizeof(http_headers[0]) - 1,
-	    sizeof(http_headers[0]), relay_httpheader_cmp);
 }
 
 void
@@ -123,7 +119,8 @@ relay_httpdesc_init(struct ctl_relay_event *cre)
 
 	if ((desc = calloc(1, sizeof(*desc))) == NULL)
 		return (-1);
-	TAILQ_INIT(&desc->http_headers);
+
+	RB_INIT(&desc->http_headers);
 	cre->desc = desc;
 
 	return (0);
@@ -132,8 +129,6 @@ relay_httpdesc_init(struct ctl_relay_event *cre)
 void
 relay_httpdesc_free(struct http_descriptor *desc)
 {
-	int	i;
-
 	if (desc->http_path != NULL) {
 		free(desc->http_path);
 		desc->http_path = NULL;
@@ -154,8 +149,6 @@ relay_httpdesc_free(struct http_descriptor *desc)
 		free(desc->query_val);
 		desc->query_val = NULL;
 	}
-	for (i = HTTP_HEADER_NONE; i < HTTP_HEADER_MAX; i++)
-		desc->http_header[i] = NULL;
 	kv_purge(&desc->http_headers);
 }
 
@@ -173,7 +166,6 @@ relay_read_http(struct bufferevent *bev, void *arg)
 	const char		*errstr;
 	size_t			 size;
 	struct kv		*hdr = NULL;
-	enum httpheader		 hdrid;
 
 	getmonotime(&con->se_tv_last);
 
@@ -218,7 +210,8 @@ relay_read_http(struct bufferevent *bev, void *arg)
 			}
 
 			/* Append line to the last header, if present */
-			if (kv_extend(&desc->http_headers, line) == NULL) {
+			if (kv_extend(&desc->http_headers,
+			    desc->http_lastheader, line) == NULL) {
 				free(line);
 				goto fail;
 			}
@@ -341,21 +334,7 @@ relay_read_http(struct bufferevent *bev, void *arg)
 				free(line);
 				goto fail;
 			}
-			/*
-			 * Remember the header if it is known to us for a
-			 * quicker lookup later.
-			 */
-			if ((hdrid = relay_httpheader_byname(key)) !=
-			    HTTP_HEADER_OTHER) {
-				if (desc->http_header[hdrid] != NULL) {
-					kv_delete(&desc->http_headers, hdr);
-					free(line);
-					relay_abort_http(con, 400, "repeated "
-					    "header line", 0);
-					return;
-				}
-				desc->http_header[hdrid] = hdr;
-			}
+			desc->http_lastheader = hdr;
 		}
 
 		free(line);
@@ -1077,26 +1056,48 @@ relay_writeresponse_http(struct ctl_relay_event *dst,
 }
 
 int
+relay_writeheader_kv(struct ctl_relay_event *dst, struct kv *hdr)
+{
+	char			*ptr;
+	const char		*key;
+
+	if (hdr->kv_flags & KV_FLAG_INVALID)
+		return (0);
+
+	/* The key might have been updated in the parent */
+	if (hdr->kv_parent != NULL && hdr->kv_parent->kv_key != NULL)
+		key = hdr->kv_parent->kv_key;
+	else
+		key = hdr->kv_key;
+
+	ptr = hdr->kv_value;
+	DPRINTF("%s: ptr %s", __func__, ptr);
+	if (relay_bufferevent_print(dst, key) == -1 ||
+	    (ptr != NULL &&
+	    (relay_bufferevent_print(dst, ": ") == -1 ||
+	    relay_bufferevent_print(dst, ptr) == -1 ||
+	    relay_bufferevent_print(dst, "\r\n") == -1)))
+		return (-1);
+	DPRINTF("%s: %s: %s", __func__, key,
+	    hdr->kv_value == NULL ? "" : hdr->kv_value);
+
+	return (0);
+}
+
+int
 relay_writeheader_http(struct ctl_relay_event *dst, struct ctl_relay_event
     *cre)
 {
-	struct kv		*hdr;
+	struct kv		*hdr, *kv;
 	struct http_descriptor	*desc = (struct http_descriptor *)cre->desc;
-	char			*ptr;
 
-	TAILQ_FOREACH(hdr, &desc->http_headers, kv_entry) {
-		if (hdr->kv_flags & KV_FLAG_INVALID)
-			continue;
-		ptr = hdr->kv_value;
-		DPRINTF("%s: ptr %s", __func__, ptr);
-		if (relay_bufferevent_print(dst, hdr->kv_key) == -1 ||
-		    (ptr != NULL &&
-		    (relay_bufferevent_print(dst, ": ") == -1 ||
-		    relay_bufferevent_print(dst, ptr) == -1 ||
-		    relay_bufferevent_print(dst, "\r\n") == -1)))
+	RB_FOREACH(hdr, kvtree, &desc->http_headers) {
+		if (relay_writeheader_kv(dst, hdr) == -1)
 			return (-1);
-		DPRINTF("%s: %s: %s", __func__, hdr->kv_key,
-			hdr->kv_value == NULL ? "" : hdr->kv_value);
+		TAILQ_FOREACH(kv, &hdr->kv_children, kv_entry) {
+			if (relay_writeheader_kv(dst, kv) == -1)
+				return (-1);
+		}
 	}
 
 	return (0);
@@ -1139,43 +1140,6 @@ relay_httpmethod_byid(u_int id)
 	return (name);
 }
 
-const char *
-relay_httpheader_byid(u_int id)
-{
-	const char	*name = NULL;
-	int		 i;
-
-	for (i = 0; http_headers[i].header_name != NULL; i++) {
-		if (http_headers[i].header_id == id) {
-			name = http_headers[i].header_name;
-			break;
-		}
-	}
-
-	return (name);
-}
-
-u_int
-relay_httpheader_byname(const char *name)
-{
-	enum httpheader		 id = HTTP_HEADER_OTHER;
-	struct http_header	 header, *res = NULL;
-
-	/* Set up key */
-	header.header_name = name;
-
-	/*
-	 * In contrast to HTTP methods, HTTP header names are
-	 * case-insensitive (see RFC 2616 section 2.4).
-	 */
-	if ((res = bsearch(&header, http_headers,
-	    sizeof(http_headers) / sizeof(http_headers[0]) - 1,
-	    sizeof(http_headers[0]), relay_httpheader_cmp)) != NULL)
-		id = res->header_id;
-
-	return (id);
-}
-
 static int
 relay_httpmethod_cmp(const void *a, const void *b)
 {
@@ -1184,14 +1148,6 @@ relay_httpmethod_cmp(const void *a, const void *b)
 	return (strcmp(ma->method_name, mb->method_name));
 }
 
-static int
-relay_httpheader_cmp(const void *a, const void *b)
-{
-	const struct http_header *ha = a;
-	const struct http_header *hb = b;
-	return (strcasecmp(ha->header_name, hb->header_name));
-}
-
 int
 relay_httpquery_test(struct ctl_relay_event *cre, struct relay_rule *rule,
     struct kvlist *actions)
@@ -1219,43 +1175,18 @@ relay_httpheader_test(struct ctl_relay_event *cre, struct relay_rule *rule,
 	struct http_descriptor	*desc = cre->desc;
 	struct kv		*kv = &rule->rule_kv[KEY_TYPE_HEADER];
 	struct kv		*match;
-	u_int			 id = kv->kv_header_id;
-	const char		*value;
 
-	kv->kv_matchptr = NULL;
-
-	if (id == HTTP_HEADER_NONE || kv->kv_type != KEY_TYPE_HEADER)
+	if (kv->kv_type != KEY_TYPE_HEADER)
 		return (0);
-	else if (id < HTTP_HEADER_MAX) {
-		match = desc->http_header[id];
-		DPRINTF("%s: standard header %s: %p", __func__,
-		    kv->kv_key, match);
-		if (match != NULL)
-			kv->kv_matchptr = &desc->http_header[id];
-	} else {
-		DPRINTF("%s: other header %s", __func__, kv->kv_key);
-		TAILQ_FOREACH_REVERSE(match, &desc->http_headers,
-		    kvlist, kv_entry) {
-			if (strcasecmp(match->kv_key, kv->kv_key) == 0 ||
-			    fnmatch(kv->kv_key, match->kv_key, FNM_CASEFOLD) !=
-			    FNM_NOMATCH)
-				goto done;
-		}
-		match = NULL;
-	}
 
- done:
+	match = kv_find(&desc->http_headers, kv);
+
 	if (kv->kv_option == KEY_OPTION_APPEND ||
 	    kv->kv_option == KEY_OPTION_SET) {
 		/* header can be NULL and will be added later */
 	} else if (match == NULL) {
 		/* Fail if header doesn't exist */
 		return (-1);
-	} else if (kv->kv_value != NULL) {
-		/* Test header value using shell globbing rules */
-		value = match->kv_value == NULL ? "" : match->kv_value;
-		if (fnmatch(kv->kv_value, value, FNM_CASEFOLD) == FNM_NOMATCH)
-			return (-1);
 	}
 
 	relay_match(actions, kv, match, &desc->http_headers);
@@ -1294,13 +1225,18 @@ relay_httpurl_test(struct ctl_relay_event *cre, struct relay_rule *rule,
     struct kvlist *actions)
 {
 	struct http_descriptor	*desc = cre->desc;
-	struct kv		*host = desc->http_header[HTTP_HEADER_HOST];
+	struct kv		*host, key;
 	struct kv		*kv = &rule->rule_kv[KEY_TYPE_URL];
 	struct kv		*match = &desc->http_pathquery;
 
-	if (cre->dir == RELAY_DIR_RESPONSE || kv->kv_type != KEY_TYPE_URL)
+	if (cre->dir == RELAY_DIR_RESPONSE || kv->kv_type != KEY_TYPE_URL ||
+	    kv->kv_key == NULL)
 		return (0);
-	else if (kv->kv_key == NULL || host == NULL || host->kv_value == NULL)
+
+	key.kv_key = "Host";
+	host = kv_find(&desc->http_headers, &key);
+
+	if (host == NULL || host->kv_value == NULL)
 		return (0);
 	else if (rule->rule_action != RULE_ACTION_BLOCK &&
 	    kv->kv_option == KEY_OPTION_LOG &&
@@ -1319,8 +1255,7 @@ relay_httpcookie_test(struct ctl_relay_event *cre, struct relay_rule *rule,
     struct kvlist *actions)
 {
 	struct http_descriptor	*desc = cre->desc;
-	struct kv		*kv = &rule->rule_kv[KEY_TYPE_COOKIE];
-	u_int			 id = HTTP_HEADER_NONE;
+	struct kv               *kv = &rule->rule_kv[KEY_TYPE_COOKIE], key;
 	struct kv		*match = NULL;
 
 	if (kv->kv_type != KEY_TYPE_COOKIE)
@@ -1328,28 +1263,24 @@ relay_httpcookie_test(struct ctl_relay_event *cre, struct relay_rule *rule,
 
 	switch (cre->dir) {
 	case RELAY_DIR_REQUEST:
-		id = HTTP_HEADER_COOKIE;
+		key.kv_key = "Cookie";
 		break;
 	case RELAY_DIR_RESPONSE:
-		id = HTTP_HEADER_SET_COOKIE;
+		key.kv_key = "Set-Cookie";
 		break;
 	default:
 		return (0);
 		/* NOTREACHED */
 		break;
 	}
+
 	if (kv->kv_option == KEY_OPTION_APPEND ||
 	    kv->kv_option == KEY_OPTION_SET) {
-		kv->kv_header_id = id;
 		/* no cookie, can be NULL and will be added later */
-	} else if (id == HTTP_HEADER_NONE) {
-		/* Fail if cookie doesn't exist */
-		return (-1);
 	} else {
-		match = desc->http_header[id];
+		match = kv_find(&desc->http_headers, &key);
 		if (match == NULL)
 			return (-1);
-		kv->kv_matchptr = &desc->http_header[id];
 		if (kv->kv_key == NULL || match->kv_value == NULL)
 			return (0);
 		else if (relay_lookup_cookie(cre, match->kv_value, kv) != 0)
@@ -1386,13 +1317,13 @@ relay_match_actions(struct ctl_relay_event *cre, struct relay_rule *rule,
 	if (matches == NULL) {
 		/* 'pass' or 'block' rule */
 		TAILQ_FOREACH(kv, &rule->rule_kvlist, kv_rule_entry) {
-			TAILQ_INSERT_TAIL(actions, kv, kv_entry);
+			TAILQ_INSERT_TAIL(actions, kv, kv_action_entry);
 			TAILQ_REMOVE(&rule->rule_kvlist, kv, kv_rule_entry);
 		}
 	} else {
 		/* 'match' rule */
 		TAILQ_FOREACH(kv, matches, kv_match_entry) {
-			TAILQ_INSERT_TAIL(actions, kv, kv_entry);
+			TAILQ_INSERT_TAIL(actions, kv, kv_action_entry);
 		}
 	}
 
@@ -1406,20 +1337,19 @@ relay_apply_actions(struct ctl_relay_event *cre, struct kvlist *actions)
 	struct http_descriptor	*desc = cre->desc;
 	struct kv		*host = NULL;
 	const char		*value;
-	struct kv		*kv, *match, *kp, *mp, kvcopy, matchcopy;
-	int			 httpindex, addkv, ret;
+	struct kv		*kv, *match, *kp, *mp, kvcopy, matchcopy, key;
+	int			 addkv, ret;
 	char			 buf[IBUF_READ_SIZE], *ptr;
-	enum httpheader		 hdrid;
 
 	memset(&kvcopy, 0, sizeof(kvcopy));
 	memset(&matchcopy, 0, sizeof(matchcopy));
 
 	ret = -1;
 	kp = mp = NULL;
-	TAILQ_FOREACH(kv, actions, kv_entry) {
+	TAILQ_FOREACH(kv, actions, kv_action_entry) {
 		kp = NULL;
 		match = kv->kv_match;
-		httpindex = addkv = 0;
+		addkv = 0;
 
 		/*
 		 * Although marked as deleted, give a chance to non-critical
@@ -1450,16 +1380,12 @@ relay_apply_actions(struct ctl_relay_event *cre, struct kvlist *actions)
 				if (kv_set(kp, "%s=%s;", kp->kv_key,
 				    kp->kv_value) == -1)
 					goto fail;
-				if (kv->kv_header_id >= HTTP_HEADER_MAX ||
-				    kv->kv_header_id <= HTTP_HEADER_NONE)
-					goto fail;
-				if (kv_setkey(kp, "%s",
-				    relay_httpheader_byid(kp->kv_header_id)) ==
-				    -1)
+				if (kv_setkey(kp, "%s", cre->dir ==
+				    RELAY_DIR_REQUEST ?
+				    "Cookie" : "Set-Cookie") == -1)
 					goto fail;
 				/* FALLTHROUGH cookie is a header */
 			case KEY_TYPE_HEADER:
-				httpindex = 1;
 				if (match == NULL) {
 					addkv = 1;
 					break;
@@ -1488,12 +1414,10 @@ relay_apply_actions(struct ctl_relay_event *cre, struct kvlist *actions)
 				break;
 			case KEY_TYPE_COOKIE:
 			case KEY_TYPE_HEADER:
-				if (kv->kv_matchlist != NULL)
+				if (kv->kv_matchtree != NULL)
 					match->kv_flags |= KV_FLAG_INVALID;
 				else
 					kv_free(match);
-				if (kv->kv_matchptr)
-					*kv->kv_matchptr = NULL;
 				match = kv->kv_match = NULL;
 				break;
 			default:
@@ -1528,24 +1452,15 @@ relay_apply_actions(struct ctl_relay_event *cre, struct kvlist *actions)
 		/* from now on, reads from kp writes to kv */
 		if (kp == NULL)
 			kp = kv;
-		if (addkv && kv->kv_matchlist != NULL) {
+		if (addkv && kv->kv_matchtree != NULL) {
 			/* Add new entry to the list (eg. new HTTP header) */
-			if ((match = kv_add(kv->kv_matchlist, kp->kv_key,
+			if ((match = kv_add(kv->kv_matchtree, kp->kv_key,
 			    kp->kv_value)) == NULL)
 				goto fail;
 			match->kv_option = kp->kv_option;
 			match->kv_type = kp->kv_type;
 			kv->kv_match = match;
 		}
-		if (httpindex && kv->kv_matchptr != NULL) {
-			/* Re-index the fast lookup method */
-			if ((hdrid = relay_httpheader_byname(kp->kv_key)) !=
-			    HTTP_HEADER_OTHER) {
-				desc->http_header[hdrid] = match;
-				kv->kv_matchptr = &desc->http_header[hdrid];
-			} else
-				kv->kv_matchptr = NULL;
-		}
 		if (match != NULL && kp->kv_flags & KV_FLAG_MACRO) {
 			bzero(buf, sizeof(buf));
 			if ((ptr = relay_expand_http(cre, kp->kv_value, buf,
@@ -1554,6 +1469,7 @@ relay_apply_actions(struct ctl_relay_event *cre, struct kvlist *actions)
 			if (kv_set(match, ptr) == -1)
 				goto fail;
 		}
+
  matchdel:
 		switch(kv->kv_option) {
 		case KEY_OPTION_LOG:
@@ -1569,7 +1485,8 @@ relay_apply_actions(struct ctl_relay_event *cre, struct kvlist *actions)
 			}
 			switch(kv->kv_type) {
 			case KEY_TYPE_URL:
-				host = desc->http_header[HTTP_HEADER_HOST];
+				key.kv_key = "Host";
+				host = kv_find(&desc->http_headers, &key);
 				switch (kv->kv_digest) {
 				case DIGEST_NONE:
 					if (host == NULL ||
@@ -1599,7 +1516,7 @@ relay_apply_actions(struct ctl_relay_event *cre, struct kvlist *actions)
 
 		/* actions applied, cleanup kv */
 		kv->kv_match = NULL;
-		kv->kv_matchlist = NULL;
+		kv->kv_matchtree = NULL;
 		TAILQ_REMOVE(actions, kv, kv_match_entry);
 
 		kv_free(&kvcopy);
@@ -1767,11 +1684,11 @@ relay_calc_skip_steps(struct relay_rules *rules)
 
 void
 relay_match(struct kvlist *actions, struct kv *kv, struct kv *match,
-    struct kvlist *matchlist)
+    struct kvtree *matchtree)
 {
 	if (kv->kv_option != KEY_OPTION_NONE) {
 		kv->kv_match = match;
-		kv->kv_matchlist = matchlist;
+		kv->kv_matchtree = matchtree;
 		TAILQ_INSERT_TAIL(actions, kv, kv_match_entry);
 	}
 }
diff --git a/usr.sbin/relayd/relayd.c b/usr.sbin/relayd/relayd.c
index 38f29a6276e..cf434bd589f 100644
--- a/usr.sbin/relayd/relayd.c
+++ b/usr.sbin/relayd/relayd.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: relayd.c,v 1.128 2014/07/10 00:05:59 reyk Exp $	*/
+/*	$OpenBSD: relayd.c,v 1.129 2014/07/11 11:48:50 reyk Exp $	*/
 
 /*
  * Copyright (c) 2007 - 2014 Reyk Floeter <reyk@openbsd.org>
@@ -33,6 +33,7 @@
 #include <stdlib.h>
 #include <fcntl.h>
 #include <getopt.h>
+#include <fnmatch.h>
 #include <err.h>
 #include <errno.h>
 #include <event.h>
@@ -637,9 +638,9 @@ purge_relay(struct relayd *env, struct relay *rlay)
 
 
 struct kv *
-kv_add(struct kvlist *keys, char *key, char *value)
+kv_add(struct kvtree *keys, char *key, char *value)
 {
-	struct kv	*kv;
+	struct kv	*kv, *oldkv;
 
 	if (key == NULL)
 		return (NULL);
@@ -655,8 +656,12 @@ kv_add(struct kvlist *keys, char *key, char *value)
 		free(kv);
 		return (NULL);
 	}
+	TAILQ_INIT(&kv->kv_children);
 
-	TAILQ_INSERT_TAIL(keys, kv, kv_entry);
+	if ((oldkv = RB_INSERT(kvtree, keys, kv)) != NULL) {
+		TAILQ_INSERT_TAIL(&oldkv->kv_children, kv, kv_entry);
+		kv->kv_parent = oldkv;
+	}
 
 	return (kv);
 }
@@ -664,14 +669,23 @@ kv_add(struct kvlist *keys, char *key, char *value)
 int
 kv_set(struct kv *kv, char *fmt, ...)
 {
-	va_list  ap;
-	char	*value = NULL;
+	va_list		  ap;
+	char		*value = NULL;
+	struct kv	*ckv;
 
 	va_start(ap, fmt);
 	if (vasprintf(&value, fmt, ap) == -1)
 		return (-1);
 	va_end(ap);
 
+	/* Remove all children */
+	while ((ckv = TAILQ_FIRST(&kv->kv_children)) != NULL) {
+		TAILQ_REMOVE(&kv->kv_children, ckv, kv_entry);
+		kv_free(ckv);
+		free(ckv);
+	}
+
+	/* Set the new value */
 	if (kv->kv_value != NULL)
 		free(kv->kv_value);
 	kv->kv_value = value;
@@ -698,23 +712,31 @@ kv_setkey(struct kv *kv, char *fmt, ...)
 }
 
 void
-kv_delete(struct kvlist *keys, struct kv *kv)
+kv_delete(struct kvtree *keys, struct kv *kv)
 {
-	TAILQ_REMOVE(keys, kv, kv_entry);
+	struct kv	*ckv;
+
+	RB_REMOVE(kvtree, keys, kv);
+
+	/* Remove all children */
+	while ((ckv = TAILQ_FIRST(&kv->kv_children)) != NULL) {
+		TAILQ_REMOVE(&kv->kv_children, ckv, kv_entry);
+		kv_free(ckv);
+		free(ckv);
+	}
+
 	kv_free(kv);
 	free(kv);
 }
 
 struct kv *
-kv_extend(struct kvlist *keys, char *value)
+kv_extend(struct kvtree *keys, struct kv *kv, char *value)
 {
-	struct kv	*kv;
 	char		*newvalue;
 
-	if ((kv = TAILQ_LAST(keys, kvlist)) == NULL)
+	if (kv == NULL) {
 		return (NULL);
-
-	if (kv->kv_value != NULL) {
+	} else if (kv->kv_value != NULL) {
 		if (asprintf(&newvalue, "%s%s", kv->kv_value, value) == -1)
 			return (NULL);
 
@@ -727,11 +749,11 @@ kv_extend(struct kvlist *keys, char *value)
 }
 
 void
-kv_purge(struct kvlist *keys)
+kv_purge(struct kvtree *keys)
 {
 	struct kv	*kv;
 
-	while ((kv = TAILQ_FIRST(keys)))
+	while ((kv = RB_MIN(kvtree, keys)) != NULL)
 		kv_delete(keys, kv);
 }
 
@@ -748,8 +770,7 @@ kv_free(struct kv *kv)
 		free(kv->kv_value);
 	}
 	kv->kv_value = NULL;
-	kv->kv_matchlist = NULL;
-	kv->kv_matchptr = NULL;
+	kv->kv_matchtree = NULL;
 	kv->kv_match = NULL;
 	memset(kv, 0, sizeof(*kv));
 }
@@ -759,6 +780,7 @@ kv_inherit(struct kv *dst, struct kv *src)
 {
 	memset(dst, 0, sizeof(*dst));
 	memcpy(dst, src, sizeof(*dst));
+	TAILQ_INIT(&dst->kv_children);
 
 	if (src->kv_key != NULL) {
 		if ((dst->kv_key = strdup(src->kv_key)) == NULL) {
@@ -775,10 +797,8 @@ kv_inherit(struct kv *dst, struct kv *src)
 
 	if (src->kv_match != NULL)
 		dst->kv_match = src->kv_match;
-	if (src->kv_matchptr != NULL)
-		dst->kv_matchptr = src->kv_matchptr;
-	if (src->kv_matchlist != NULL)
-		dst->kv_matchlist = src->kv_matchlist;
+	if (src->kv_matchtree != NULL)
+		dst->kv_matchtree = src->kv_matchtree;
 
 	return (dst);
 }
@@ -806,6 +826,35 @@ kv_log(struct evbuffer *log, struct kv *kv, u_int16_t labelid)
 	return (0);
 }
 
+struct kv *
+kv_find(struct kvtree *keys, struct kv *kv)
+{
+	struct kv	*match;
+	const char	*key;
+
+	if (kv->kv_flags & KV_FLAG_GLOBBING) {
+		/* Test header key using shell globbing rules */
+		key = kv->kv_key == NULL ? "" : kv->kv_key;
+		RB_FOREACH(match, kvtree, keys) {
+			if (fnmatch(key, match->kv_key, FNM_CASEFOLD) == 0)
+				break;
+		}
+	} else {
+		/* Fast tree-based lookup only works without globbing */
+		match = RB_FIND(kvtree, keys, kv);
+	}
+
+	return (match);
+}
+
+int
+kv_cmp(struct kv *a, struct kv *b)
+{
+	return (strcasecmp(a->kv_key, b->kv_key));
+}
+
+RB_GENERATE(kvtree, kv, kv_node, kv_cmp);
+
 int
 rule_add(struct protocol *proto, struct relay_rule *rule, const char *rulefile)
 {
@@ -821,9 +870,6 @@ rule_add(struct protocol *proto, struct relay_rule *rule, const char *rulefile)
 		if (kv->kv_type != i)
 			continue;
 
-		if (kv->kv_value != NULL && strchr(kv->kv_value, '$') != NULL)
-			kv->kv_flags |= KV_FLAG_MACRO;
-
 		switch (kv->kv_option) {
 		case KEY_OPTION_LOG:
 			/* log action needs a key or a file to be specified */
@@ -845,6 +891,11 @@ rule_add(struct protocol *proto, struct relay_rule *rule, const char *rulefile)
 		default:
 			break;
 		}
+
+		if (kv->kv_value != NULL && strchr(kv->kv_value, '$') != NULL)
+			kv->kv_flags |= KV_FLAG_MACRO;
+		if (kv->kv_key != NULL && strpbrk(kv->kv_key, "*?[") != NULL)
+			kv->kv_flags |= KV_FLAG_GLOBBING;
 	}
 
 	if (rulefile == NULL) {
diff --git a/usr.sbin/relayd/relayd.h b/usr.sbin/relayd/relayd.h
index 35e8b0b014c..16ee60a9422 100644
--- a/usr.sbin/relayd/relayd.h
+++ b/usr.sbin/relayd/relayd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: relayd.h,v 1.182 2014/07/09 16:42:05 reyk Exp $	*/
+/*	$OpenBSD: relayd.h,v 1.183 2014/07/11 11:48:50 reyk Exp $	*/
 
 /*
  * Copyright (c) 2006 - 2014 Reyk Floeter <reyk@openbsd.org>
@@ -272,6 +272,9 @@ enum digest_type {
 	DIGEST_MD5		= 2
 };
 
+TAILQ_HEAD(kvlist, kv);
+RB_HEAD(kvtree, kv);
+
 struct kv {
 	char			*kv_key;
 	char			*kv_value;
@@ -279,22 +282,26 @@ struct kv {
 	enum key_type		 kv_type;
 	enum key_option		 kv_option;
 	enum digest_type	 kv_digest;
-	u_int			 kv_header_id;
 
 #define KV_FLAG_MACRO		 0x01
 #define KV_FLAG_INVALID		 0x02
+#define KV_FLAG_GLOBBING	 0x04
 	u_int8_t		 kv_flags;
 
+	struct kvlist		 kv_children;
+	struct kv		*kv_parent;
+	TAILQ_ENTRY(kv)		 kv_entry;
+
+	RB_ENTRY(kv)		 kv_node;
+
 	/* A few pointers used by the rule actions */
 	struct kv		*kv_match;
-	struct kvlist		*kv_matchlist;
-	struct kv		**kv_matchptr;
+	struct kvtree		*kv_matchtree;
 
 	TAILQ_ENTRY(kv)		 kv_match_entry;
 	TAILQ_ENTRY(kv)		 kv_rule_entry;
-	TAILQ_ENTRY(kv)		 kv_entry;
+	TAILQ_ENTRY(kv)		 kv_action_entry;
 };
-TAILQ_HEAD(kvlist, kv);
 
 struct portrange {
 	in_port_t		 val[2];
@@ -1121,7 +1128,7 @@ int	 relay_bufferevent_write(struct ctl_relay_event *,
 int	 relay_test(struct protocol *, struct ctl_relay_event *);
 void	 relay_calc_skip_steps(struct relay_rules *);
 void	 relay_match(struct kvlist *, struct kv *, struct kv *,
-	    struct kvlist *);
+	    struct kvtree *);
 
 SPLAY_PROTOTYPE(session_tree, rsession, se_nodes, relay_session_cmp);
 
@@ -1135,9 +1142,6 @@ void	 relay_close_http(struct rsession *);
 u_int	 relay_httpmethod_byname(const char *);
 const char
 	*relay_httpmethod_byid(u_int);
-u_int	 relay_httpheader_byname(const char *);
-const char
-	*relay_httpheader_byid(u_int id);
 int	 relay_httpdesc_init(struct ctl_relay_event *);
 
 /* relay_udp.c */
@@ -1220,15 +1224,17 @@ struct in6_addr *prefixlen2mask6(u_int8_t, u_int32_t *);
 u_int32_t	 prefixlen2mask(u_int8_t);
 int		 accept_reserve(int, struct sockaddr *, socklen_t *, int,
 		     volatile int *);
-struct kv	*kv_add(struct kvlist *, char *, char *);
+struct kv	*kv_add(struct kvtree *, char *, char *);
 int		 kv_set(struct kv *, char *, ...);
 int		 kv_setkey(struct kv *, char *, ...);
-void		 kv_delete(struct kvlist *, struct kv *);
-struct kv	*kv_extend(struct kvlist *, char *);
-void		 kv_purge(struct kvlist *);
+void		 kv_delete(struct kvtree *, struct kv *);
+struct kv	*kv_extend(struct kvtree *, struct kv *, char *);
+void		 kv_purge(struct kvtree *);
 void		 kv_free(struct kv *);
 struct kv	*kv_inherit(struct kv *, struct kv *);
 int		 kv_log(struct evbuffer *, struct kv *, u_int16_t);
+struct kv	*kv_find(struct kvtree *, struct kv *);
+int		 kv_cmp(struct kv *, struct kv *);
 int		 rule_add(struct protocol *, struct relay_rule *, const char
 		     *);
 void		 rule_delete(struct relay_rules *, struct relay_rule *);
@@ -1236,6 +1242,7 @@ void		 rule_free(struct relay_rule *);
 struct relay_rule
 		*rule_inherit(struct relay_rule *);
 void		 rule_settable(struct relay_rules *, struct relay_table *);
+RB_PROTOTYPE(kvtree, kv, kv_node, kv_cmp);
 
 /* carp.c */
 int	 carp_demote_init(char *, int);