[MEDIUM] acl: add tree-based lookups of networks
Networks patterns loaded from files for longest match ACL testing
will now be arranged into a prefix tree. This is possible thanks to
the new prefix features in ebtree v6.0. Longest match testing is
slightly slower than exact data maching. However, the measured impact
of running at 42000 requests per second and testing whether the IP
address found in a header belongs to a list of 52000 networks or
not is 3% CPU (increase from 66% to 69%). This is low enough to
permit true geolocation based on huge tables.
diff --git a/src/acl.c b/src/acl.c
index b474c82..f548c17 100644
--- a/src/acl.c
+++ b/src/acl.c
@@ -344,6 +344,21 @@
return ACL_PAT_FAIL;
}
+/* Lookup an IPv4 address in the expression's pattern tree using the longest
+ * match method. The node is returned if it exists, otherwise NULL.
+ */
+void *acl_lookup_ip(struct acl_test *test, struct acl_expr *expr)
+{
+ struct in_addr *s;
+
+ if (test->i != AF_INET)
+ return ACL_PAT_FAIL;
+
+ s = (void *)test->ptr;
+
+ return ebmb_lookup_longest(&expr->pattern_tree, &s->s_addr);
+}
+
/* Parse a string. It is allocated and duplicated. */
int acl_parse_str(const char **text, struct acl_pattern *pattern, int *opaque)
{
@@ -608,8 +623,33 @@
*/
int acl_parse_ip(const char **text, struct acl_pattern *pattern, int *opaque)
{
- if (str2net(*text, &pattern->val.ipv4.addr, &pattern->val.ipv4.mask))
+ struct eb_root *tree = NULL;
+ if (pattern->flags & ACL_PAT_F_TREE_OK)
+ tree = pattern->val.tree;
+
+ if (str2net(*text, &pattern->val.ipv4.addr, &pattern->val.ipv4.mask)) {
+ unsigned int mask = ntohl(pattern->val.ipv4.mask.s_addr);
+ struct ebmb_node *node;
+ /* check if the mask is contiguous so that we can insert the
+ * network into the tree. A continuous mask has only ones on
+ * the left. This means that this mask + its lower bit added
+ * once again is null.
+ */
+ if (mask + (mask & -mask) == 0 && tree) {
+ mask = mask ? 33 - flsnz(mask & -mask) : 0; /* equals cidr value */
+ /* FIXME: insert <addr>/<mask> into the tree here */
+ node = calloc(1, sizeof(*node) + 4); /* reserve 4 bytes for IPv4 address */
+ if (!node)
+ return 0;
+ memcpy(node->key, &pattern->val.ipv4.addr, 4); /* network byte order */
+ node->node.pfx = mask;
+ if (ebmb_insert_prefix(tree, node, 4) != node)
+ free(node); /* was a duplicate */
+ pattern->flags |= ACL_PAT_F_TREE;
+ return 1;
+ }
return 1;
+ }
else
return 0;
}
@@ -1266,6 +1306,8 @@
/* a tree is present, let's check what type it is */
if (expr->kw->match == acl_match_str)
acl_res |= acl_lookup_str(&test, expr) ? ACL_PAT_PASS : ACL_PAT_FAIL;
+ else if (expr->kw->match == acl_match_ip)
+ acl_res |= acl_lookup_ip(&test, expr) ? ACL_PAT_PASS : ACL_PAT_FAIL;
}
/* call the match() function for all tests on this value */
diff --git a/src/client.c b/src/client.c
index f274245..2955de0 100644
--- a/src/client.c
+++ b/src/client.c
@@ -644,8 +644,8 @@
/* Note: must not be declared <const> as its list will be overwritten */
static struct acl_kw_list acl_kws = {{ },{
{ "src_port", acl_parse_int, acl_fetch_sport, acl_match_int, ACL_USE_TCP_PERMANENT },
- { "src", acl_parse_ip, acl_fetch_src, acl_match_ip, ACL_USE_TCP4_PERMANENT },
- { "dst", acl_parse_ip, acl_fetch_dst, acl_match_ip, ACL_USE_TCP4_PERMANENT },
+ { "src", acl_parse_ip, acl_fetch_src, acl_match_ip, ACL_USE_TCP4_PERMANENT|ACL_MAY_LOOKUP },
+ { "dst", acl_parse_ip, acl_fetch_dst, acl_match_ip, ACL_USE_TCP4_PERMANENT|ACL_MAY_LOOKUP },
{ "dst_port", acl_parse_int, acl_fetch_dport, acl_match_int, ACL_USE_TCP_PERMANENT },
#if 0
{ "src_limit", acl_parse_int, acl_fetch_sconn, acl_match_int },
diff --git a/src/proto_http.c b/src/proto_http.c
index c8835a5..1f13438 100644
--- a/src/proto_http.c
+++ b/src/proto_http.c
@@ -7371,7 +7371,7 @@
{ "url_dir", acl_parse_str, acl_fetch_url, acl_match_dir, ACL_USE_L7REQ_VOLATILE },
{ "url_dom", acl_parse_str, acl_fetch_url, acl_match_dom, ACL_USE_L7REQ_VOLATILE },
{ "url_reg", acl_parse_reg, acl_fetch_url, acl_match_reg, ACL_USE_L7REQ_VOLATILE },
- { "url_ip", acl_parse_ip, acl_fetch_url_ip, acl_match_ip, ACL_USE_L7REQ_VOLATILE },
+ { "url_ip", acl_parse_ip, acl_fetch_url_ip, acl_match_ip, ACL_USE_L7REQ_VOLATILE|ACL_MAY_LOOKUP },
{ "url_port", acl_parse_int, acl_fetch_url_port, acl_match_int, ACL_USE_L7REQ_VOLATILE },
/* note: we should set hdr* to use ACL_USE_HDR_VOLATILE, and chdr* to use L7REQ_VOLATILE */
@@ -7384,7 +7384,7 @@
{ "hdr_dom", acl_parse_str, acl_fetch_chdr, acl_match_dom, ACL_USE_L7REQ_VOLATILE },
{ "hdr_cnt", acl_parse_int, acl_fetch_chdr_cnt,acl_match_int, ACL_USE_L7REQ_VOLATILE },
{ "hdr_val", acl_parse_int, acl_fetch_chdr_val,acl_match_int, ACL_USE_L7REQ_VOLATILE },
- { "hdr_ip", acl_parse_ip, acl_fetch_chdr_ip, acl_match_ip, ACL_USE_L7REQ_VOLATILE },
+ { "hdr_ip", acl_parse_ip, acl_fetch_chdr_ip, acl_match_ip, ACL_USE_L7REQ_VOLATILE|ACL_MAY_LOOKUP },
{ "shdr", acl_parse_str, acl_fetch_shdr, acl_match_str, ACL_USE_L7RTR_VOLATILE|ACL_MAY_LOOKUP },
{ "shdr_reg", acl_parse_reg, acl_fetch_shdr, acl_match_reg, ACL_USE_L7RTR_VOLATILE },
@@ -7395,7 +7395,7 @@
{ "shdr_dom", acl_parse_str, acl_fetch_shdr, acl_match_dom, ACL_USE_L7RTR_VOLATILE },
{ "shdr_cnt", acl_parse_int, acl_fetch_shdr_cnt,acl_match_int, ACL_USE_L7RTR_VOLATILE },
{ "shdr_val", acl_parse_int, acl_fetch_shdr_val,acl_match_int, ACL_USE_L7RTR_VOLATILE },
- { "shdr_ip", acl_parse_ip, acl_fetch_shdr_ip, acl_match_ip, ACL_USE_L7RTR_VOLATILE },
+ { "shdr_ip", acl_parse_ip, acl_fetch_shdr_ip, acl_match_ip, ACL_USE_L7RTR_VOLATILE|ACL_MAY_LOOKUP },
{ "path", acl_parse_str, acl_fetch_path, acl_match_str, ACL_USE_L7REQ_VOLATILE|ACL_MAY_LOOKUP },
{ "path_reg", acl_parse_reg, acl_fetch_path, acl_match_reg, ACL_USE_L7REQ_VOLATILE },