ACLs using "-i" with "-m str" or "-m beg" are indexed in a list walked
with strncasecmp(). The LRU cache does not help with high-cardinality
samples such as paths or client-controlled headers: with a 100000-entry
list and random Host values, a thread handles ~600 req/s with "-i"
against ~30k without.
Trees were limited to case-sensitive expressions by e56cda9a6
("[MEDIUM] acl: add ability to insert patterns in trees"), when the
flags were set per pattern. They are set per expression since e47e4e238
("BUG/MEDIUM: patterns: last fix was still not enough"), and
expressions with different flags are no longer shared since 7d27f3c12
("BUG/MEDIUM: map/acl: fix unwanted flags inheritance"), so a tree only
holds one kind of keys.
Store the keys lowercased and look up a lowercased copy of the sample.
The copy goes to a per-thread buffer, as the sample may already sit in a
trash chunk after smp_dup(). Only ACLs support "-i", and their result is
unchanged. "get acl" now reports idx=tree.
A 1000-entry list goes from 22k to 29k req/s and a 100000-entry one from
605 to 30.8k, on par with case-sensitive matching. No backport is
needed. A regression test is provided in
reg-tests/http-rules/acl_icase_tree.vtc.
Signed-off-by: William Dauchy <[email protected]>
---
doc/configuration.txt | 9 +-
reg-tests/http-rules/acl_icase_tree.acl | 1 +
reg-tests/http-rules/acl_icase_tree.vtc | 125 ++++++++++++++++++++++++
src/pattern.c | 79 +++++++++++----
4 files changed, 191 insertions(+), 23 deletions(-)
create mode 100644 reg-tests/http-rules/acl_icase_tree.acl
create mode 100644 reg-tests/http-rules/acl_icase_tree.vtc
diff --git a/doc/configuration.txt b/doc/configuration.txt
index ee08fca77..476a0f496 100644
--- a/doc/configuration.txt
+++ b/doc/configuration.txt
@@ -5421,8 +5421,8 @@ tune.pattern.cache-size <number>
Sets the size of the pattern lookup cache to <number> entries. This is an LRU
cache which reminds previous lookups and their results. It is used by ACLs
and maps on slow pattern lookups, namely the ones using the "sub", "reg",
- "dir", "dom", "end", "bin" match methods as well as the case-insensitive
- strings. It applies to pattern expressions which means that it will be able
+ "dir", "dom", "end", "bin" match methods, including their case-insensitive
+ variants. It applies to pattern expressions which means that it will be able
to memorize the result of a lookup among all the patterns specified on a
configuration line (including all those loaded from files). It automatically
invalidates entries which are updated using HTTP actions or on the CLI. The
@@ -21676,8 +21676,9 @@ leading spaces and tabs will be stripped. If it is
absolutely necessary to
insert a valid pattern beginning with a sharp, just prefix it with a space so
that it is not taken for a comment. Depending on the data type and match
method, HAProxy may load the lines into a binary tree, allowing very fast
-lookups. This is true for IPv4 and exact string matching. In this case,
-duplicates will automatically be removed.
+lookups. This is true for IPv4, exact string ("str") and prefix ("beg")
+matching, including their case-insensitive variants. In this case, duplicates
+will automatically be removed.
The "-M" flag allows an ACL to use a map. If this flag is set, the list is
parsed as two column entries. The first column contains the patterns used by
the
diff --git a/reg-tests/http-rules/acl_icase_tree.acl
b/reg-tests/http-rules/acl_icase_tree.acl
new file mode 100644
index 000000000..bc56c4d89
--- /dev/null
+++ b/reg-tests/http-rules/acl_icase_tree.acl
@@ -0,0 +1 @@
+Foo
diff --git a/reg-tests/http-rules/acl_icase_tree.vtc
b/reg-tests/http-rules/acl_icase_tree.vtc
new file mode 100644
index 000000000..495375c36
--- /dev/null
+++ b/reg-tests/http-rules/acl_icase_tree.vtc
@@ -0,0 +1,125 @@
+varnishtest "case-insensitive exact and prefix string matches"
+feature ignore_unknown_macro
+
+#REGTEST_TYPE=default
+
+haproxy h1 -conf {
+ global
+ .if feature(THREAD)
+ thread-groups 1
+ .endif
+
+ defaults
+ mode http
+ timeout connect "${HAPROXY_TEST_TIMEOUT-5s}"
+ timeout client "${HAPROXY_TEST_TIMEOUT-5s}"
+ timeout server "${HAPROXY_TEST_TIMEOUT-5s}"
+
+ frontend fe
+ bind "fd@${fe}"
+ acl host_i hdr(host) -u 10 -i -m str www.Example.COM Other.example.org
+ acl path_i path -u 11 -i -m beg /Api/V1 /static
+ acl ua_mix hdr(user-agent) -f ${testdir}/acl_icase_tree.acl -i -f
${testdir}/acl_icase_tree.acl test
+ http-request return status 201 if host_i
+ http-request return status 202 if path_i
+ http-request return status 203 if ua_mix
+ http-request return status 200
+} -start
+
+client c1 -connect ${h1_fe_sock} {
+ txreq -hdr "Host: www.example.com"
+ rxresp
+ expect resp.status == 201
+
+ txreq -hdr "Host: WWW.EXAMPLE.COM"
+ rxresp
+ expect resp.status == 201
+
+ txreq -hdr "Host: OTHER.Example.Org"
+ rxresp
+ expect resp.status == 201
+
+ txreq -hdr "Host: www.example.co"
+ rxresp
+ expect resp.status == 200
+
+ txreq -hdr "Host: www.example.comx"
+ rxresp
+ expect resp.status == 200
+
+ txreq -url "/api/v1/users" -hdr "Host: a"
+ rxresp
+ expect resp.status == 202
+
+ txreq -url "/STATIC" -hdr "Host: a"
+ rxresp
+ expect resp.status == 202
+
+ txreq -url "/API/V" -hdr "Host: a"
+ rxresp
+ expect resp.status == 200
+
+ txreq -url "/stati" -hdr "Host: a"
+ rxresp
+ expect resp.status == 200
+
+ txreq -hdr "Host: a" -hdr "User-Agent: Foo"
+ rxresp
+ expect resp.status == 203
+
+ txreq -hdr "Host: a" -hdr "User-Agent: FOO"
+ rxresp
+ expect resp.status == 203
+
+ txreq -hdr "Host: a" -hdr "User-Agent: TEST"
+ rxresp
+ expect resp.status == 203
+
+ txreq -hdr "Host: a" -hdr "User-Agent: Fo"
+ rxresp
+ expect resp.status == 200
+} -run
+
+haproxy h1 -cli {
+ send "add acl #10 New.Example.NET"
+ expect ~ "^$"
+
+ send "add acl #11 /Admin"
+ expect ~ "^$"
+}
+
+client c2 -connect ${h1_fe_sock} {
+ txreq -hdr "Host: NEW.example.net"
+ rxresp
+ expect resp.status == 201
+
+ txreq -url "/ADMIN/x" -hdr "Host: a"
+ rxresp
+ expect resp.status == 202
+} -run
+
+haproxy h1 -cli {
+ send "del acl #10 New.Example.NET"
+ expect ~ "^$"
+
+ send "del acl #11 /Admin"
+ expect ~ "^$"
+}
+
+client c3 -connect ${h1_fe_sock} {
+ txreq -hdr "Host: new.example.net"
+ rxresp
+ expect resp.status == 200
+
+ txreq -url "/admin/x" -hdr "Host: a"
+ rxresp
+ expect resp.status == 200
+} -run
+
+haproxy h1 -cli {
+ send "get acl #10 WWW.EXAMPLE.COM"
+ expect ~ "type=str, case=insensitive, match=yes, idx=tree,
pattern=\"www.Example.COM\""
+
+ send "get acl #11 /API/V1/x"
+ expect ~ "type=beg, case=insensitive, match=yes, idx=tree,
pattern=\"/Api/V1\""
+}
diff --git a/src/pattern.c b/src/pattern.c
index ff6e4d54a..87c4e9509 100644
--- a/src/pattern.c
+++ b/src/pattern.c
@@ -155,6 +155,7 @@ static THREAD_LOCAL struct sample_data static_sample_data;
struct list pattern_reference = LIST_HEAD_INIT(pattern_reference);
static THREAD_LOCAL struct lru64_head *pat_lru_tree;
+static THREAD_LOCAL char *pat_lower_buf;
static unsigned long long pat_lru_seed __read_mostly;
unsigned long long patterns_added = 0;
@@ -488,6 +489,22 @@ static inline int pat_match_ensure_str(struct sample *smp)
return 1;
}
+/* Returns a lowercase copy of <smp>'s string, stopped at the first NUL or at
+ * the buffer size. <len> is set to the copied length. A dedicated per-thread
+ * buffer is used since the sample may be in a trash chunk.
+ */
+static inline const char *pat_match_lower_str(const struct sample *smp, size_t
*len)
+{
+ size_t max = MIN(smp->data.u.str.data, global.tune.bufsize - 1);
+ size_t i;
+
+ for (i = 0; i < max && smp->data.u.str.area[i]; i++)
+ pat_lower_buf[i] = tolower((unsigned
char)smp->data.u.str.area[i]);
+ pat_lower_buf[i] = 0;
+ *len = i;
+ return pat_lower_buf;
+}
+
/* NB: For two strings to be identical, it is required that their length match
*/
struct pattern *pat_match_str(struct sample *smp, struct pattern_expr *expr,
int fill)
{
@@ -501,10 +518,20 @@ struct pattern *pat_match_str(struct sample *smp, struct
pattern_expr *expr, int
/* Lookup a string in the expression's pattern tree. */
if (!eb_is_empty(&expr->pattern_tree)) {
- if (!pat_match_ensure_str(smp))
- return NULL;
+ if (expr->mflags & PAT_MF_IGNORE_CASE) {
+ const char *key;
+ size_t len;
- node = ebst_lookup(&expr->pattern_tree, smp->data.u.str.area);
+ key = pat_match_lower_str(smp, &len);
+ if (len != smp->data.u.str.data)
+ return NULL;
+ node = ebst_lookup(&expr->pattern_tree, key);
+ }
+ else {
+ if (!pat_match_ensure_str(smp))
+ return NULL;
+ node = ebst_lookup(&expr->pattern_tree,
smp->data.u.str.area);
+ }
while (node) {
elt = ebmb_entry(node, struct pattern_tree, node);
@@ -677,11 +704,19 @@ struct pattern *pat_match_beg(struct sample *smp, struct
pattern_expr *expr, int
/* Lookup a string in the expression's pattern tree. */
if (!eb_is_empty(&expr->pattern_tree)) {
- if (!pat_match_ensure_str(smp))
- return NULL;
+ if (expr->mflags & PAT_MF_IGNORE_CASE) {
+ const char *key;
+ size_t len;
- node = ebmb_lookup_longest(&expr->pattern_tree,
- smp->data.u.str.area);
+ key = pat_match_lower_str(smp, &len);
+ node = ebmb_lookup_longest(&expr->pattern_tree, key);
+ }
+ else {
+ if (!pat_match_ensure_str(smp))
+ return NULL;
+ node = ebmb_lookup_longest(&expr->pattern_tree,
+ smp->data.u.str.area);
+ }
while (node) {
elt = ebmb_entry(node, struct pattern_tree, node);
@@ -1381,6 +1416,12 @@ int pat_idx_tree_ip(struct pattern_expr *expr, struct
pattern *pat, char **err)
return 0;
}
+static inline void pat_lower_key(unsigned char *key)
+{
+ for (; *key; key++)
+ *key = tolower(*key);
+}
+
int pat_idx_tree_str(struct pattern_expr *expr, struct pattern *pat, char
**err)
{
int len;
@@ -1393,10 +1434,6 @@ int pat_idx_tree_str(struct pattern_expr *expr, struct
pattern *pat, char **err)
return 0;
}
- /* If the flag PAT_F_IGNORE_CASE is set, we cannot use trees */
- if (expr->mflags & PAT_MF_IGNORE_CASE)
- return pat_idx_list_str(expr, pat, err);
-
/* Process the key len */
len = strlen(pat->ptr.str) + 1;
@@ -1413,6 +1450,8 @@ int pat_idx_tree_str(struct pattern_expr *expr, struct
pattern *pat, char **err)
/* copy the string */
memcpy(node->node.key, pat->ptr.str, len);
+ if (expr->mflags & PAT_MF_IGNORE_CASE)
+ pat_lower_key(node->node.key);
/* index the new node */
ebst_insert(&expr->pattern_tree, &node->node);
@@ -1439,10 +1478,6 @@ int pat_idx_tree_pfx(struct pattern_expr *expr, struct
pattern *pat, char **err)
return 0;
}
- /* If the flag PAT_F_IGNORE_CASE is set, we cannot use trees */
- if (expr->mflags & PAT_MF_IGNORE_CASE)
- return pat_idx_list_str(expr, pat, err);
-
/* Process the key len */
len = strlen(pat->ptr.str);
@@ -1459,6 +1494,8 @@ int pat_idx_tree_pfx(struct pattern_expr *expr, struct
pattern *pat, char **err)
/* copy the string and the trailing zero */
memcpy(node->node.key, pat->ptr.str, len + 1);
+ if (expr->mflags & PAT_MF_IGNORE_CASE)
+ pat_lower_key(node->node.key);
node->node.node.pfx = len * 8;
/* index the new node */
@@ -2873,18 +2910,22 @@ int pattern_finalize_config(void)
return 0;
}
-static int pattern_per_thread_lru_alloc()
+static int pattern_per_thread_alloc()
{
+ pat_lower_buf = malloc(global.tune.bufsize);
+ if (!pat_lower_buf)
+ return 0;
if (!global.tune.pattern_cache)
return 1;
pat_lru_tree = lru64_new(global.tune.pattern_cache);
return !!pat_lru_tree;
}
-static void pattern_per_thread_lru_free()
+static void pattern_per_thread_free()
{
lru64_destroy(pat_lru_tree);
+ ha_free(&pat_lower_buf);
}
-REGISTER_PER_THREAD_ALLOC(pattern_per_thread_lru_alloc);
-REGISTER_PER_THREAD_FREE(pattern_per_thread_lru_free);
+REGISTER_PER_THREAD_ALLOC(pattern_per_thread_alloc);
+REGISTER_PER_THREAD_FREE(pattern_per_thread_free);
--
2.56.0