OPTIM: startup: fast unique_id allocation for acl.
pattern_finalize_config() uses an inefficient algorithm which is a
problem with very large configuration files. This affects startup, and
therefore reload time. When haproxy is deployed as a router in a
Kubernetes cluster the generated configuration file may be large and
reloads are frequently occuring, which makes this a significant issue.
The old algorithm is O(n^2)
* allocate missing uids - O(n^2)
* sort linked list - O(n^2)
The new algorithm is O(n log n):
* find the user allocated uids - O(n)
* store them for efficient lookup - O(n log n)
* allocate missing uids - n times O(log n)
* sort all uids - O(n log n)
* convert back to linked list - O(n)
Performance examples, startup time in seconds:
pat_refs old new
1000 0.02 0.01
10000 2.1 0.04
20000 12.3 0.07
30000 27.9 0.10
40000 52.5 0.14
50000 77.5 0.17
Please backport to 1.8, 2.0 and 2.1.
diff --git a/include/proto/pattern.h b/include/proto/pattern.h
index 5b99296..73d3cdc 100644
--- a/include/proto/pattern.h
+++ b/include/proto/pattern.h
@@ -37,7 +37,7 @@
extern struct pattern *(*pat_match_fcts[PAT_MATCH_NUM])(struct sample *, struct pattern_expr *, int);
extern int pat_match_types[PAT_MATCH_NUM];
-void pattern_finalize_config(void);
+int pattern_finalize_config(void);
/* return the PAT_MATCH_* index for match name "name", or < 0 if not found */
static inline int pat_find_match_name(const char *name)
diff --git a/src/haproxy.c b/src/haproxy.c
index f02accf..759612d 100644
--- a/src/haproxy.c
+++ b/src/haproxy.c
@@ -1898,7 +1898,11 @@
exit(1);
}
- pattern_finalize_config();
+ err_code |= pattern_finalize_config();
+ if (err_code & (ERR_ABORT|ERR_FATAL)) {
+ ha_alert("Failed to finalize pattern config.\n");
+ exit(1);
+ }
/* recompute the amount of per-process memory depending on nbproc and
* the shared SSL cache size (allowed to exist in all processes).
diff --git a/src/pattern.c b/src/pattern.c
index 4624823..8dfe3cf 100644
--- a/src/pattern.c
+++ b/src/pattern.c
@@ -2642,53 +2642,80 @@
return 1;
}
-/* This function finalize the configuration parsing. Its set all the
+/* This function compares two pat_ref** on unique_id */
+static int cmp_pat_ref(const void *_a, const void *_b)
+{
+ struct pat_ref * const *a = _a;
+ struct pat_ref * const *b = _b;
+
+ if ((*a)->unique_id < (*b)->unique_id)
+ return -1;
+ else if ((*a)->unique_id > (*b)->unique_id)
+ return 1;
+ return 0;
+}
+
+/* This function finalize the configuration parsing. It sets all the
* automatic ids
*/
-void pattern_finalize_config(void)
+int pattern_finalize_config(void)
{
- int i = 0;
- struct pat_ref *ref, *ref2, *ref3;
+ int len = 0;
+ int unassigned_pos = 0;
+ int next_unique_id = 0;
+ int i, j;
+ struct pat_ref *ref, **arr;
struct list pr = LIST_HEAD_INIT(pr);
pat_lru_seed = random();
+ /* Count pat_refs with user defined unique_id and totalt count */
list_for_each_entry(ref, &pattern_reference, list) {
- if (ref->unique_id == -1) {
- /* Look for the first free id. */
- while (1) {
- list_for_each_entry(ref2, &pattern_reference, list) {
- if (ref2->unique_id == i) {
- i++;
- break;
- }
- }
- if (&ref2->list == &pattern_reference)
- break;
- }
+ len++;
+ if (ref->unique_id != -1)
+ unassigned_pos++;
+ }
- /* Uses the unique id and increment it for the next entry. */
- ref->unique_id = i;
- i++;
- }
+ arr = calloc(len, sizeof(*arr));
+ if (arr == NULL) {
+ ha_alert("Out of memory error.\n");
+ return ERR_ALERT | ERR_FATAL;
}
- /* This sort the reference list by id. */
- list_for_each_entry_safe(ref, ref2, &pattern_reference, list) {
- LIST_DEL(&ref->list);
- list_for_each_entry(ref3, &pr, list) {
- if (ref->unique_id < ref3->unique_id) {
- LIST_ADDQ(&ref3->list, &ref->list);
- break;
- }
- }
- if (&ref3->list == &pr)
- LIST_ADDQ(&pr, &ref->list);
+ i = 0;
+ j = unassigned_pos;
+ list_for_each_entry(ref, &pattern_reference, list) {
+ if (ref->unique_id != -1)
+ arr[i++] = ref;
+ else
+ arr[j++] = ref;
}
+ /* Sort first segment of array with user-defined unique ids for
+ * fast lookup when generating unique ids
+ */
+ qsort(arr, unassigned_pos, sizeof(*arr), cmp_pat_ref);
+
+ /* Assign unique ids to the rest of the elements */
+ for (i = unassigned_pos; i < len; i++) {
+ do {
+ arr[i]->unique_id = next_unique_id++;
+ } while (bsearch(&arr[i], arr, unassigned_pos, sizeof(*arr), cmp_pat_ref));
+ }
+
+ /* Sort complete array */
+ qsort(arr, len, sizeof(*arr), cmp_pat_ref);
+
+ /* Convert back to linked list */
+ for (i = 0; i < len; i++)
+ LIST_ADDQ(&pr, &arr[i]->list);
+
/* swap root */
LIST_ADD(&pr, &pattern_reference);
LIST_DEL(&pr);
+
+ free(arr);
+ return 0;
}
static int pattern_per_thread_lru_alloc()