From 0844bed7d365c32e39368c9ee072ecb0572c6bde Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fr=C3=A9d=C3=A9ric=20L=C3=A9caille?= Date: Tue, 22 Aug 2023 16:52:47 +0200 Subject: [PATCH] MEDIUM: map/acl: Improve pat_ref_set() efficiency (for "set-map", "add-acl" action perfs) Organize reference to pattern element of map (struct pat_ref_elt) into an ebtree: - add an eb_root member to the map (pat_ref struct) and an ebpt_node to its element (pat_ref_elt struct), - modify the code to insert these nodes into their ebtrees each time they are allocated. This is done in pat_ref_append(). Note that ->head member (struct list) of map (struct pat_ref) is not removed could have been removed. This is not the case because still necessary to dump the map contents from the CLI in the order the map elememnts have been inserted. This patch also modifies http_action_set_map() which is the callback at least used by "set-map" action. The pat_ref_elt element returned by pat_ref_find_elt() is no more ignored, but reused if not NULL by pat_ref_set() as first element to lookup from. This latter is also modified to use the ebtree attached to the map in place of the ->head list attached to each map element (pat_ref_elt struct). Also modify pat_ref_find_elt() to makes it use ->eb_root map ebtree added to the map by this patch in place of inspecting all the elements with a strcmp() call. --- include/haproxy/pattern-t.h | 2 ++ include/haproxy/pattern.h | 2 +- src/hlua.c | 2 +- src/http_act.c | 9 +++++-- src/map.c | 2 +- src/pattern.c | 52 +++++++++++++++++++++++-------------- 6 files changed, 45 insertions(+), 24 deletions(-) diff --git a/include/haproxy/pattern-t.h b/include/haproxy/pattern-t.h index 1d1de602fe..803620d78a 100644 --- a/include/haproxy/pattern-t.h +++ b/include/haproxy/pattern-t.h @@ -104,6 +104,7 @@ struct pat_ref { char *reference; /* The reference name. */ char *display; /* String displayed to identify the pattern origin. */ struct list head; /* The head of the list of struct pat_ref_elt. */ + struct eb_root ebpt_root; /* The tree where pattern reference elements are attached. */ struct list pat; /* The head of the list of struct pattern_expr. */ unsigned int flags; /* flags PAT_REF_*. */ unsigned int curr_gen; /* current generation number (anything below can be removed) */ @@ -120,6 +121,7 @@ struct pat_ref { */ struct pat_ref_elt { struct list list; /* Used to chain elements. */ + struct ebpt_node node; /* Node to attach this element to its ebtree. */ struct list back_refs; /* list of users tracking this pat ref */ void *list_head; /* all &pattern_list->from_ref derived from this reference, ends with NULL */ void *tree_head; /* all &pattern_tree->from_ref derived from this reference, ends with NULL */ diff --git a/include/haproxy/pattern.h b/include/haproxy/pattern.h index be4106f1e4..ab56711af4 100644 --- a/include/haproxy/pattern.h +++ b/include/haproxy/pattern.h @@ -185,7 +185,7 @@ struct pat_ref_elt *pat_ref_append(struct pat_ref *ref, const char *pattern, con struct pat_ref_elt *pat_ref_load(struct pat_ref *ref, unsigned int gen, const char *pattern, const char *sample, int line, char **err); int pat_ref_push(struct pat_ref_elt *elt, struct pattern_expr *expr, int patflags, char **err); int pat_ref_add(struct pat_ref *ref, const char *pattern, const char *sample, char **err); -int pat_ref_set(struct pat_ref *ref, const char *pattern, const char *sample, char **err); +int pat_ref_set(struct pat_ref *ref, const char *pattern, const char *sample, char **err, struct pat_ref_elt *elt); int pat_ref_set_by_id(struct pat_ref *ref, struct pat_ref_elt *refelt, const char *value, char **err); int pat_ref_delete(struct pat_ref *ref, const char *key); void pat_ref_delete_by_ptr(struct pat_ref *ref, struct pat_ref_elt *elt); diff --git a/src/hlua.c b/src/hlua.c index 7b682c7ff8..30a8713152 100644 --- a/src/hlua.c +++ b/src/hlua.c @@ -1956,7 +1956,7 @@ static int hlua_set_map(lua_State *L) HA_SPIN_LOCK(PATREF_LOCK, &ref->lock); if (pat_ref_find_elt(ref, key) != NULL) - pat_ref_set(ref, key, value, NULL); + pat_ref_set(ref, key, value, NULL, NULL); else pat_ref_add(ref, key, value, NULL); HA_SPIN_UNLOCK(PATREF_LOCK, &ref->lock); diff --git a/src/http_act.c b/src/http_act.c index 2505ad212d..e815095876 100644 --- a/src/http_act.c +++ b/src/http_act.c @@ -1847,6 +1847,9 @@ static enum act_return http_action_set_map(struct act_rule *rule, struct proxy * break; case 1: // set-map + { + struct pat_ref_elt *elt; + /* allocate value */ value = alloc_trash_chunk(); if (!value) @@ -1857,9 +1860,10 @@ static enum act_return http_action_set_map(struct act_rule *rule, struct proxy * value->area[value->data] = '\0'; HA_SPIN_LOCK(PATREF_LOCK, &ref->lock); - if (pat_ref_find_elt(ref, key->area) != NULL) { + elt = pat_ref_find_elt(ref, key->area); + if (elt) { /* update entry if it exists */ - pat_ref_set(ref, key->area, value->area, NULL); + pat_ref_set(ref, key->area, value->area, NULL, elt); } else { /* insert a new entry */ @@ -1867,6 +1871,7 @@ static enum act_return http_action_set_map(struct act_rule *rule, struct proxy * } HA_SPIN_UNLOCK(PATREF_LOCK, &ref->lock); break; + } case 2: // del-acl case 3: // del-map diff --git a/src/map.c b/src/map.c index fe694b5fc5..f4e74fb99f 100644 --- a/src/map.c +++ b/src/map.c @@ -794,7 +794,7 @@ static int cli_parse_set_map(char **args, char *payload, struct appctx *appctx, */ err = NULL; HA_SPIN_LOCK(PATREF_LOCK, &ctx->ref->lock); - if (!pat_ref_set(ctx->ref, args[3], args[4], &err)) { + if (!pat_ref_set(ctx->ref, args[3], args[4], &err, NULL)) { HA_SPIN_UNLOCK(PATREF_LOCK, &ctx->ref->lock); if (err) return cli_dynerr(appctx, memprintf(&err, "%s.\n", err)); diff --git a/src/pattern.c b/src/pattern.c index ce0f07b40a..c77d236088 100644 --- a/src/pattern.c +++ b/src/pattern.c @@ -14,6 +14,8 @@ #include #include +#include +#include #include #include @@ -1624,6 +1626,7 @@ void pat_ref_delete_by_ptr(struct pat_ref *ref, struct pat_ref_elt *elt) HA_RWLOCK_WRUNLOCK(PATEXP_LOCK, &expr->lock); LIST_DELETE(&elt->list); + ebpt_delete(&elt->node); free(elt->sample); free(elt->pattern); free(elt); @@ -1673,12 +1676,11 @@ int pat_ref_delete(struct pat_ref *ref, const char *key) */ struct pat_ref_elt *pat_ref_find_elt(struct pat_ref *ref, const char *key) { - struct pat_ref_elt *elt; + struct ebpt_node *node; - list_for_each_entry(elt, &ref->head, list) { - if (strcmp(key, elt->pattern) == 0) - return elt; - } + node = ebis_lookup(&ref->ebpt_root, key); + if (node) + return ebpt_entry(node, struct pat_ref_elt, node); return NULL; } @@ -1759,12 +1761,12 @@ int pat_ref_set_by_id(struct pat_ref *ref, struct pat_ref_elt *refelt, const cha /* This function modifies to the sample of all patterns matching * under . */ -int pat_ref_set(struct pat_ref *ref, const char *key, const char *value, char **err) +int pat_ref_set(struct pat_ref *ref, const char *key, const char *value, char **err, struct pat_ref_elt *elt) { - struct pat_ref_elt *elt; int found = 0; char *_merr; char **merr; + struct ebpt_node *node; if (err) { merr = &_merr; @@ -1773,21 +1775,28 @@ int pat_ref_set(struct pat_ref *ref, const char *key, const char *value, char ** else merr = NULL; - /* Look for pattern in the reference. */ - list_for_each_entry(elt, &ref->head, list) { - if (strcmp(key, elt->pattern) == 0) { - if (!pat_ref_set_elt(ref, elt, value, merr)) { - if (err && merr) { - if (!found) { - *err = *merr; - } else { - memprintf(err, "%s, %s", *err, *merr); - ha_free(merr); - } + if (elt) { + node = &elt->node; + } + else { + /* Look for pattern in the reference. */ + node = ebis_lookup(&ref->ebpt_root, key); + } + + while (node) { + elt = ebpt_entry(node, struct pat_ref_elt, node); + node = ebpt_next_dup(node); + if (!pat_ref_set_elt(ref, elt, value, merr)) { + if (err && merr) { + if (!found) { + *err = *merr; + } else { + memprintf(err, "%s, %s", *err, *merr); + ha_free(merr); } } - found = 1; } + found = 1; } if (!found) { @@ -1832,6 +1841,7 @@ struct pat_ref *pat_ref_new(const char *reference, const char *display, unsigned ref->entry_cnt = 0; LIST_INIT(&ref->head); + ref->ebpt_root = EB_ROOT; LIST_INIT(&ref->pat); HA_SPIN_INIT(&ref->lock); LIST_APPEND(&pattern_reference, &ref->list); @@ -1868,6 +1878,7 @@ struct pat_ref *pat_ref_newid(int unique_id, const char *display, unsigned int f ref->next_gen = 0; ref->unique_id = unique_id; LIST_INIT(&ref->head); + ref->ebpt_root = EB_ROOT; LIST_INIT(&ref->pat); HA_SPIN_INIT(&ref->lock); LIST_APPEND(&pattern_reference, &ref->list); @@ -1905,6 +1916,8 @@ struct pat_ref_elt *pat_ref_append(struct pat_ref *ref, const char *pattern, con elt->list_head = NULL; elt->tree_head = NULL; LIST_APPEND(&ref->head, &elt->list); + elt->node.key = elt->pattern; + ebis_insert(&ref->ebpt_root, &elt->node); return elt; fail: if (elt) @@ -2075,6 +2088,7 @@ int pat_ref_purge_range(struct pat_ref *ref, uint from, uint to, int budget) pat_delete_gen(ref, elt); LIST_DELETE(&elt->list); + ebpt_delete(&elt->node); free(elt->pattern); free(elt->sample); free(elt); -- 2.39.5