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



Reply via email to