MEDIUM: pattern: change the pat_del_* functions to delete from the references
This is the next step in speeding up entry removal. Now we don't scan
the whole lists or trees for elements pointing to the target reference,
instead we start from the reference and delete all linked patterns.
This simplifies some delete functions since we don't need anymore to
delete multiple times from an expression since all nodes appear after
the reference element. We can now have one generic list and one generic
tree deletion function.
This required the replacement of pattern_delete() with an open-coded
version since we now need to lock all expressions first before proceeding.
This means there is a high risk of lock inversion here but given that the
expressions are always scanned in the same order from the same head, this
must not happen.
Now deleting first entries is instantaneous, and it's still slow to
delete the last ones when looking up their ID since it still requires
to look them up by a full scan, but it's already way faster than
previously. Typically removing the last 10 IP from a 20M entries ACL
with a full-scan each took less than 2 seconds.
It would be technically possible to make use of indexed entries to
speed up most lookups for removal by value (e.g. IP addresses) but
that's for later.
diff --git a/include/haproxy/acl-t.h b/include/haproxy/acl-t.h
index e7de2a2..3dec96d 100644
--- a/include/haproxy/acl-t.h
+++ b/include/haproxy/acl-t.h
@@ -81,7 +81,7 @@
int match_type; /* Contain PAT_MATCH_* */
int (*parse)(const char *text, struct pattern *pattern, int flags, char **err);
int (*index)(struct pattern_expr *expr, struct pattern *pattern, char **err);
- void (*delete)(struct pattern_expr *expr, struct pat_ref_elt *);
+ void (*delete)(struct pat_ref *, struct pat_ref_elt *);
void (*prune)(struct pattern_expr *expr);
struct pattern *(*match)(struct sample *smp, struct pattern_expr *expr, int fill);
/* must be after the config params */
diff --git a/include/haproxy/pattern-t.h b/include/haproxy/pattern-t.h
index 2f5f58c..8c01760 100644
--- a/include/haproxy/pattern-t.h
+++ b/include/haproxy/pattern-t.h
@@ -216,7 +216,7 @@
int (*parse)(const char *text, struct pattern *pattern, int flags, char **err);
int (*parse_smp)(const char *text, struct sample_data *data);
int (*index)(struct pattern_expr *, struct pattern *, char **);
- void (*delete)(struct pattern_expr *, struct pat_ref_elt *);
+ void (*delete)(struct pat_ref *, struct pat_ref_elt *);
void (*prune)(struct pattern_expr *);
struct pattern *(*match)(struct sample *, struct pattern_expr *, int);
int expect_type; /* type of the expected sample (SMP_T_*) */
diff --git a/include/haproxy/pattern.h b/include/haproxy/pattern.h
index e9266f4..0046a7f 100644
--- a/include/haproxy/pattern.h
+++ b/include/haproxy/pattern.h
@@ -34,7 +34,7 @@
extern int (*pat_parse_fcts[PAT_MATCH_NUM])(const char *, struct pattern *, int, char **);
extern int (*pat_index_fcts[PAT_MATCH_NUM])(struct pattern_expr *, struct pattern *, char **);
-extern void (*pat_delete_fcts[PAT_MATCH_NUM])(struct pattern_expr *, struct pat_ref_elt *);
+extern void (*pat_delete_fcts[PAT_MATCH_NUM])(struct pat_ref *, struct pat_ref_elt *);
extern void (*pat_prune_fcts[PAT_MATCH_NUM])(struct pattern_expr *);
extern struct pattern *(*pat_match_fcts[PAT_MATCH_NUM])(struct sample *, struct pattern_expr *, int);
@@ -78,14 +78,12 @@
/*
*
- * The following functions search pattern <pattern> into the pattern
- * expression <expr>. If the pattern is found, delete it. This function
- * never fails.
+ * The following functions deletes all patterns related to reference pattern
+ * element <elt> in pattern refernce <ref>.
*
*/
-void pat_del_list_gen(struct pattern_expr *expr, struct pat_ref_elt *ref);
-void pat_del_tree_ip(struct pattern_expr *expr, struct pat_ref_elt *ref);
-void pat_del_tree_str(struct pattern_expr *expr, struct pat_ref_elt *ref);
+void pat_del_list_gen(struct pat_ref *ref, struct pat_ref_elt *elt);
+void pat_del_tree_gen(struct pat_ref *ref, struct pat_ref_elt *elt);
/*
*
diff --git a/src/pattern.c b/src/pattern.c
index 3045c3c..2908bd0 100644
--- a/src/pattern.c
+++ b/src/pattern.c
@@ -79,15 +79,15 @@
[PAT_MATCH_REGM] = pat_idx_list_regm,
};
-void (*pat_delete_fcts[PAT_MATCH_NUM])(struct pattern_expr *, struct pat_ref_elt *) = {
+void (*pat_delete_fcts[PAT_MATCH_NUM])(struct pat_ref *, struct pat_ref_elt *) = {
[PAT_MATCH_FOUND] = pat_del_list_gen,
[PAT_MATCH_BOOL] = pat_del_list_gen,
[PAT_MATCH_INT] = pat_del_list_gen,
- [PAT_MATCH_IP] = pat_del_tree_ip,
+ [PAT_MATCH_IP] = pat_del_tree_gen,
[PAT_MATCH_BIN] = pat_del_list_gen,
[PAT_MATCH_LEN] = pat_del_list_gen,
- [PAT_MATCH_STR] = pat_del_tree_str,
- [PAT_MATCH_BEG] = pat_del_tree_str,
+ [PAT_MATCH_STR] = pat_del_tree_gen,
+ [PAT_MATCH_BEG] = pat_del_tree_gen,
[PAT_MATCH_SUB] = pat_del_list_gen,
[PAT_MATCH_DIR] = pat_del_list_gen,
[PAT_MATCH_DOM] = pat_del_list_gen,
@@ -1402,15 +1402,17 @@
return 1;
}
-void pat_del_list_gen(struct pattern_expr *expr, struct pat_ref_elt *ref)
+/* Deletes all list-based patterns from reference <elt>. Note that all of their
+ * expressions must be locked, and the pattern lock must be held as well.
+ */
+void pat_del_list_gen(struct pat_ref *ref, struct pat_ref_elt *elt)
{
struct pattern_list *pat;
struct pattern_list *safe;
- list_for_each_entry_safe(pat, safe, &expr->patterns, list) {
+ list_for_each_entry_safe(pat, safe, &elt->list_head, from_ref) {
/* Check equality. */
- if (pat->pat.ref != ref)
- continue;
+ BUG_ON(pat->pat.ref != elt);
/* Delete and free entry. */
LIST_DEL(&pat->list);
@@ -1422,82 +1424,27 @@
free(pat->pat.data);
free(pat);
}
- expr->ref->revision = rdtsc();
+ ref->revision = rdtsc();
}
-void pat_del_tree_ip(struct pattern_expr *expr, struct pat_ref_elt *ref)
+/* Deletes all tree-based patterns from reference <elt>. Note that all of their
+ * expressions must be locked, and the pattern lock must be held as well.
+ */
+void pat_del_tree_gen(struct pat_ref *ref, struct pat_ref_elt *elt)
{
- struct ebmb_node *node, *next_node;
- struct pattern_tree *elt;
-
- /* browse each node of the tree for IPv4 addresses. */
- for (node = ebmb_first(&expr->pattern_tree), next_node = node ? ebmb_next(node) : NULL;
- node;
- node = next_node, next_node = node ? ebmb_next(node) : NULL) {
- /* Extract container of the tree node. */
- elt = container_of(node, struct pattern_tree, node);
-
- /* Check equality. */
- if (elt->ref != ref)
- continue;
-
- /* Delete and free entry. */
- ebmb_delete(node);
- LIST_DEL(&elt->from_ref);
- free(elt->data);
- free(elt);
- }
-
- /* Browse each node of the list for IPv4 addresses. */
- pat_del_list_gen(expr, ref);
-
- /* browse each node of the tree for IPv6 addresses. */
- for (node = ebmb_first(&expr->pattern_tree_2), next_node = node ? ebmb_next(node) : NULL;
- node;
- node = next_node, next_node = node ? ebmb_next(node) : NULL) {
- /* Extract container of the tree node. */
- elt = container_of(node, struct pattern_tree, node);
+ struct pattern_tree *tree, *tree_bck;
- /* Check equality. */
- if (elt->ref != ref)
- continue;
+ list_for_each_entry_safe(tree, tree_bck, &elt->tree_head, from_ref) {
+ BUG_ON(tree->ref != elt);
- /* Delete and free entry. */
- ebmb_delete(node);
- LIST_DEL(&elt->from_ref);
- free(elt->data);
- free(elt);
+ ebmb_delete(&tree->node);
+ LIST_DEL(&tree->from_ref);
+ free(tree->data);
+ free(tree);
}
- expr->ref->revision = rdtsc();
-}
-
-void pat_del_tree_str(struct pattern_expr *expr, struct pat_ref_elt *ref)
-{
- struct ebmb_node *node, *next_node;
- struct pattern_tree *elt;
- /* If the flag PAT_F_IGNORE_CASE is set, we cannot use trees */
- if (expr->mflags & PAT_MF_IGNORE_CASE)
- return pat_del_list_gen(expr, ref);
-
- /* browse each node of the tree. */
- for (node = ebmb_first(&expr->pattern_tree), next_node = node ? ebmb_next(node) : NULL;
- node;
- node = next_node, next_node = node ? ebmb_next(node) : NULL) {
- /* Extract container of the tree node. */
- elt = container_of(node, struct pattern_tree, node);
-
- /* Check equality. */
- if (elt->ref != ref)
- continue;
-
- /* Delete and free entry. */
- ebmb_delete(node);
- LIST_DEL(&elt->from_ref);
- free(elt->data);
- free(elt);
- }
- expr->ref->revision = rdtsc();
+ /* Also check the lists ofr immediate IPs or case-insensitive strings */
+ pat_del_list_gen(ref, elt);
}
void pattern_init_expr(struct pattern_expr *expr)
@@ -1586,8 +1533,15 @@
LIST_ADDQ(&LIST_ELEM(elt->list.n, typeof(elt), list)->back_refs, &bref->users);
bref->ref = elt->list.n;
}
+
list_for_each_entry(expr, &ref->pat, list)
- pattern_delete(expr, elt);
+ HA_RWLOCK_WRLOCK(PATEXP_LOCK, &expr->lock);
+
+ list_for_each_entry(expr, &ref->pat, list)
+ expr->pat_head->delete(expr->ref, elt);
+
+ list_for_each_entry(expr, &ref->pat, list)
+ HA_RWLOCK_WRUNLOCK(PATEXP_LOCK, &expr->lock);
/* pat_ref_elt is trashed once all expr
are cleaned and there is no ref remaining */
@@ -1626,8 +1580,15 @@
LIST_ADDQ(&LIST_ELEM(elt->list.n, typeof(elt), list)->back_refs, &bref->users);
bref->ref = elt->list.n;
}
+
+ list_for_each_entry(expr, &ref->pat, list)
+ HA_RWLOCK_WRLOCK(PATEXP_LOCK, &expr->lock);
+
+ list_for_each_entry(expr, &ref->pat, list)
+ expr->pat_head->delete(expr->ref, elt);
+
list_for_each_entry(expr, &ref->pat, list)
- pattern_delete(expr, elt);
+ HA_RWLOCK_WRUNLOCK(PATEXP_LOCK, &expr->lock);
/* pat_ref_elt is trashed once all expr
are cleaned and there is no ref remaining */
@@ -2609,18 +2570,6 @@
return NULL;
}
-/* This function delets from expression <expr> all occurrences of patterns
- * corresponding to pattern reference element <ref>. The function always
- * returns 1.
- */
-int pattern_delete(struct pattern_expr *expr, struct pat_ref_elt *ref)
-{
- HA_RWLOCK_WRLOCK(PATEXP_LOCK, &expr->lock);
- expr->pat_head->delete(expr, ref);
- HA_RWLOCK_WRUNLOCK(PATEXP_LOCK, &expr->lock);
- return 1;
-}
-
/* This function compares two pat_ref** on their unique_id, and returns -1/0/1
* depending on their order (suitable for sorting).
*/