blob: 80ff0259b3c5d66ab22afbe46deb1890cd245c84 [file] [log] [blame]
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001/*
2 * Pattern management functions.
3 *
4 * Copyright 2000-2013 Willy Tarreau <w@1wt.eu>
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version
9 * 2 of the License, or (at your option) any later version.
10 *
11 */
12
13#include <ctype.h>
14#include <stdio.h>
Jerome Magninb8bd6d72020-01-17 18:01:20 +010015#include <errno.h>
Thierry FOURNIERed66c292013-11-28 11:05:19 +010016
Willy Tarreaub2551052020-06-09 09:07:15 +020017#include <import/ebsttree.h>
18#include <import/lru.h>
19#include <import/xxhash.h>
20
Willy Tarreau4c7e4b72020-05-27 12:58:42 +020021#include <haproxy/api.h>
Willy Tarreauf268ee82020-06-04 17:05:57 +020022#include <haproxy/global.h>
Willy Tarreauaeed4a82020-06-04 22:01:04 +020023#include <haproxy/log.h>
Willy Tarreau6131d6a2020-06-02 16:48:09 +020024#include <haproxy/net_helper.h>
Willy Tarreau225a90a2020-06-04 15:06:28 +020025#include <haproxy/pattern.h>
Willy Tarreau7cd8b6e2020-06-02 17:32:26 +020026#include <haproxy/regex.h>
Willy Tarreaue6ce10b2020-06-04 15:33:47 +020027#include <haproxy/sample.h>
Willy Tarreaub2551052020-06-09 09:07:15 +020028#include <haproxy/tools.h>
Thierry FOURNIERed66c292013-11-28 11:05:19 +010029
Thierry FOURNIERed66c292013-11-28 11:05:19 +010030
Willy Tarreau9057a002021-04-10 17:44:27 +020031const char *const pat_match_names[PAT_MATCH_NUM] = {
Thierry FOURNIERa65b3432013-11-28 18:22:00 +010032 [PAT_MATCH_FOUND] = "found",
33 [PAT_MATCH_BOOL] = "bool",
34 [PAT_MATCH_INT] = "int",
35 [PAT_MATCH_IP] = "ip",
36 [PAT_MATCH_BIN] = "bin",
37 [PAT_MATCH_LEN] = "len",
38 [PAT_MATCH_STR] = "str",
39 [PAT_MATCH_BEG] = "beg",
40 [PAT_MATCH_SUB] = "sub",
41 [PAT_MATCH_DIR] = "dir",
42 [PAT_MATCH_DOM] = "dom",
43 [PAT_MATCH_END] = "end",
44 [PAT_MATCH_REG] = "reg",
Thierry Fournier8feaa662016-02-10 22:55:20 +010045 [PAT_MATCH_REGM] = "regm",
Thierry FOURNIERed66c292013-11-28 11:05:19 +010046};
47
Willy Tarreau9057a002021-04-10 17:44:27 +020048int (*const pat_parse_fcts[PAT_MATCH_NUM])(const char *, struct pattern *, int, char **) = {
Thierry FOURNIERa65b3432013-11-28 18:22:00 +010049 [PAT_MATCH_FOUND] = pat_parse_nothing,
50 [PAT_MATCH_BOOL] = pat_parse_nothing,
51 [PAT_MATCH_INT] = pat_parse_int,
52 [PAT_MATCH_IP] = pat_parse_ip,
53 [PAT_MATCH_BIN] = pat_parse_bin,
Thierry FOURNIER5d344082014-01-27 14:19:53 +010054 [PAT_MATCH_LEN] = pat_parse_int,
Thierry FOURNIERa65b3432013-11-28 18:22:00 +010055 [PAT_MATCH_STR] = pat_parse_str,
56 [PAT_MATCH_BEG] = pat_parse_str,
57 [PAT_MATCH_SUB] = pat_parse_str,
58 [PAT_MATCH_DIR] = pat_parse_str,
59 [PAT_MATCH_DOM] = pat_parse_str,
60 [PAT_MATCH_END] = pat_parse_str,
61 [PAT_MATCH_REG] = pat_parse_reg,
Thierry Fournier8feaa662016-02-10 22:55:20 +010062 [PAT_MATCH_REGM] = pat_parse_reg,
Thierry FOURNIERed66c292013-11-28 11:05:19 +010063};
64
Willy Tarreau9057a002021-04-10 17:44:27 +020065int (*const pat_index_fcts[PAT_MATCH_NUM])(struct pattern_expr *, struct pattern *, char **) = {
Thierry FOURNIERb9b08462013-12-13 15:12:32 +010066 [PAT_MATCH_FOUND] = pat_idx_list_val,
67 [PAT_MATCH_BOOL] = pat_idx_list_val,
68 [PAT_MATCH_INT] = pat_idx_list_val,
69 [PAT_MATCH_IP] = pat_idx_tree_ip,
70 [PAT_MATCH_BIN] = pat_idx_list_ptr,
71 [PAT_MATCH_LEN] = pat_idx_list_val,
72 [PAT_MATCH_STR] = pat_idx_tree_str,
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +020073 [PAT_MATCH_BEG] = pat_idx_tree_pfx,
Thierry FOURNIERb9b08462013-12-13 15:12:32 +010074 [PAT_MATCH_SUB] = pat_idx_list_str,
75 [PAT_MATCH_DIR] = pat_idx_list_str,
76 [PAT_MATCH_DOM] = pat_idx_list_str,
77 [PAT_MATCH_END] = pat_idx_list_str,
78 [PAT_MATCH_REG] = pat_idx_list_reg,
Thierry Fournier8feaa662016-02-10 22:55:20 +010079 [PAT_MATCH_REGM] = pat_idx_list_regm,
Thierry FOURNIERb9b08462013-12-13 15:12:32 +010080};
81
Willy Tarreau9057a002021-04-10 17:44:27 +020082void (*const pat_prune_fcts[PAT_MATCH_NUM])(struct pattern_expr *) = {
Willy Tarreau6d8a6892020-11-02 19:26:02 +010083 [PAT_MATCH_FOUND] = pat_prune_gen,
84 [PAT_MATCH_BOOL] = pat_prune_gen,
85 [PAT_MATCH_INT] = pat_prune_gen,
86 [PAT_MATCH_IP] = pat_prune_gen,
87 [PAT_MATCH_BIN] = pat_prune_gen,
88 [PAT_MATCH_LEN] = pat_prune_gen,
89 [PAT_MATCH_STR] = pat_prune_gen,
90 [PAT_MATCH_BEG] = pat_prune_gen,
91 [PAT_MATCH_SUB] = pat_prune_gen,
92 [PAT_MATCH_DIR] = pat_prune_gen,
93 [PAT_MATCH_DOM] = pat_prune_gen,
94 [PAT_MATCH_END] = pat_prune_gen,
95 [PAT_MATCH_REG] = pat_prune_gen,
96 [PAT_MATCH_REGM] = pat_prune_gen,
Thierry FOURNIER6f7203d2014-01-14 16:24:51 +010097};
98
Willy Tarreau9057a002021-04-10 17:44:27 +020099struct pattern *(*const pat_match_fcts[PAT_MATCH_NUM])(struct sample *, struct pattern_expr *, int) = {
Thierry FOURNIERa65b3432013-11-28 18:22:00 +0100100 [PAT_MATCH_FOUND] = NULL,
101 [PAT_MATCH_BOOL] = pat_match_nothing,
102 [PAT_MATCH_INT] = pat_match_int,
103 [PAT_MATCH_IP] = pat_match_ip,
104 [PAT_MATCH_BIN] = pat_match_bin,
105 [PAT_MATCH_LEN] = pat_match_len,
106 [PAT_MATCH_STR] = pat_match_str,
107 [PAT_MATCH_BEG] = pat_match_beg,
108 [PAT_MATCH_SUB] = pat_match_sub,
109 [PAT_MATCH_DIR] = pat_match_dir,
110 [PAT_MATCH_DOM] = pat_match_dom,
111 [PAT_MATCH_END] = pat_match_end,
112 [PAT_MATCH_REG] = pat_match_reg,
Thierry Fournier8feaa662016-02-10 22:55:20 +0100113 [PAT_MATCH_REGM] = pat_match_regm,
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100114};
115
Thierry FOURNIERe3ded592013-12-06 15:36:54 +0100116/* Just used for checking configuration compatibility */
Willy Tarreau9057a002021-04-10 17:44:27 +0200117int const pat_match_types[PAT_MATCH_NUM] = {
Thierry FOURNIER07ee64e2015-07-06 23:43:03 +0200118 [PAT_MATCH_FOUND] = SMP_T_SINT,
119 [PAT_MATCH_BOOL] = SMP_T_SINT,
120 [PAT_MATCH_INT] = SMP_T_SINT,
Thierry FOURNIERe3ded592013-12-06 15:36:54 +0100121 [PAT_MATCH_IP] = SMP_T_ADDR,
Thierry FOURNIER7654c9f2013-12-17 00:20:33 +0100122 [PAT_MATCH_BIN] = SMP_T_BIN,
123 [PAT_MATCH_LEN] = SMP_T_STR,
124 [PAT_MATCH_STR] = SMP_T_STR,
125 [PAT_MATCH_BEG] = SMP_T_STR,
126 [PAT_MATCH_SUB] = SMP_T_STR,
127 [PAT_MATCH_DIR] = SMP_T_STR,
128 [PAT_MATCH_DOM] = SMP_T_STR,
129 [PAT_MATCH_END] = SMP_T_STR,
130 [PAT_MATCH_REG] = SMP_T_STR,
Thierry Fournier8feaa662016-02-10 22:55:20 +0100131 [PAT_MATCH_REGM] = SMP_T_STR,
Thierry FOURNIERe3ded592013-12-06 15:36:54 +0100132};
133
Thierry FOURNIER1794fdf2014-01-17 15:25:13 +0100134/* this struct is used to return information */
Emeric Brunb5997f72017-07-03 11:34:05 +0200135static THREAD_LOCAL struct pattern static_pattern;
136static THREAD_LOCAL struct sample_data static_sample_data;
Thierry FOURNIER1794fdf2014-01-17 15:25:13 +0100137
Thierry FOURNIER1e00d382014-02-11 11:31:40 +0100138/* This is the root of the list of all pattern_ref avalaibles. */
139struct list pattern_reference = LIST_HEAD_INIT(pattern_reference);
140
Willy Tarreau403bfbb2019-10-23 06:59:31 +0200141static THREAD_LOCAL struct lru64_head *pat_lru_tree;
Willy Tarreau295a89c2021-04-10 17:42:04 +0200142static unsigned long long pat_lru_seed __read_mostly;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200143
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100144/*
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100145 *
146 * The following functions are not exported and are used by internals process
147 * of pattern matching
148 *
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100149 */
150
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100151/* Background: Fast way to find a zero byte in a word
152 * http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord
153 * hasZeroByte = (v - 0x01010101UL) & ~v & 0x80808080UL;
154 *
155 * To look for 4 different byte values, xor the word with those bytes and
156 * then check for zero bytes:
157 *
158 * v = (((unsigned char)c * 0x1010101U) ^ delimiter)
159 * where <delimiter> is the 4 byte values to look for (as an uint)
160 * and <c> is the character that is being tested
161 */
162static inline unsigned int is_delimiter(unsigned char c, unsigned int mask)
163{
164 mask ^= (c * 0x01010101); /* propagate the char to all 4 bytes */
165 return (mask - 0x01010101) & ~mask & 0x80808080U;
166}
167
168static inline unsigned int make_4delim(unsigned char d1, unsigned char d2, unsigned char d3, unsigned char d4)
169{
170 return d1 << 24 | d2 << 16 | d3 << 8 | d4;
171}
172
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100173
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100174/*
175 *
176 * These functions are exported and may be used by any other component.
177 *
Willy Tarreau5def8ef2014-08-29 15:19:33 +0200178 * The following functions are used for parsing pattern matching input value.
179 * The <text> contain the string to be parsed. <pattern> must be a preallocated
180 * pattern. The pat_parse_* functions fill this structure with the parsed value.
181 * <err> is filled with an error message built with memprintf() function. It is
182 * allowed to use a trash as a temporary storage for the returned pattern, as
183 * the next call after these functions will be pat_idx_*.
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100184 *
Willy Tarreau5def8ef2014-08-29 15:19:33 +0200185 * In success case, the pat_parse_* function returns 1. If the function
186 * fails, it returns 0 and <err> is filled.
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100187 */
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100188
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100189/* ignore the current line */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200190int pat_parse_nothing(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100191{
192 return 1;
193}
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100194
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100195/* Parse a string. It is allocated and duplicated. */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200196int pat_parse_str(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100197{
Thierry FOURNIER7654c9f2013-12-17 00:20:33 +0100198 pattern->type = SMP_T_STR;
Thierry FOURNIERedc15c32013-12-13 15:36:59 +0100199 pattern->ptr.str = (char *)text;
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100200 pattern->len = strlen(text);
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100201 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100202}
203
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100204/* Parse a binary written in hexa. It is allocated. */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200205int pat_parse_bin(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100206{
Willy Tarreau83061a82018-07-13 11:56:34 +0200207 struct buffer *trash;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100208
Thierry FOURNIER7654c9f2013-12-17 00:20:33 +0100209 pattern->type = SMP_T_BIN;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100210 trash = get_trash_chunk();
211 pattern->len = trash->size;
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200212 pattern->ptr.str = trash->area;
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100213 return !!parse_binary(text, &pattern->ptr.str, &pattern->len, err);
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100214}
215
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100216/* Parse a regex. It is allocated. */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200217int pat_parse_reg(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100218{
Thierry FOURNIER0b6d15f2014-01-29 19:35:16 +0100219 pattern->ptr.str = (char *)text;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100220 return 1;
221}
222
223/* Parse a range of positive integers delimited by either ':' or '-'. If only
224 * one integer is read, it is set as both min and max. An operator may be
225 * specified as the prefix, among this list of 5 :
226 *
227 * 0:eq, 1:gt, 2:ge, 3:lt, 4:le
228 *
229 * The default operator is "eq". It supports range matching. Ranges are
230 * rejected for other operators. The operator may be changed at any time.
231 * The operator is stored in the 'opaque' argument.
232 *
233 * If err is non-NULL, an error message will be returned there on errors and
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100234 * the caller will have to free it. The function returns zero on error, and
235 * non-zero on success.
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100236 *
237 */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200238int pat_parse_int(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100239{
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100240 const char *ptr = text;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100241
Thierry FOURNIER07ee64e2015-07-06 23:43:03 +0200242 pattern->type = SMP_T_SINT;
Thierry FOURNIER7148ce62013-12-06 19:06:43 +0100243
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100244 /* Empty string is not valid */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100245 if (!*text)
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100246 goto not_valid_range;
247
248 /* Search ':' or '-' separator. */
249 while (*ptr != '\0' && *ptr != ':' && *ptr != '-')
250 ptr++;
251
252 /* If separator not found. */
253 if (!*ptr) {
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100254 if (strl2llrc(text, ptr - text, &pattern->val.range.min) != 0) {
255 memprintf(err, "'%s' is not a number", text);
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100256 return 0;
257 }
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100258 pattern->val.range.max = pattern->val.range.min;
259 pattern->val.range.min_set = 1;
260 pattern->val.range.max_set = 1;
261 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100262 }
263
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100264 /* If the separator is the first character. */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100265 if (ptr == text && *(ptr + 1) != '\0') {
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100266 if (strl2llrc(ptr + 1, strlen(ptr + 1), &pattern->val.range.max) != 0)
267 goto not_valid_range;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100268
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100269 pattern->val.range.min_set = 0;
270 pattern->val.range.max_set = 1;
271 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100272 }
273
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100274 /* If separator is the last character. */
275 if (*(ptr + 1) == '\0') {
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100276 if (strl2llrc(text, ptr - text, &pattern->val.range.min) != 0)
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100277 goto not_valid_range;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100278
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100279 pattern->val.range.min_set = 1;
280 pattern->val.range.max_set = 0;
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100281 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100282 }
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100283
284 /* Else, parse two numbers. */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100285 if (strl2llrc(text, ptr - text, &pattern->val.range.min) != 0)
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100286 goto not_valid_range;
287
288 if (strl2llrc(ptr + 1, strlen(ptr + 1), &pattern->val.range.max) != 0)
289 goto not_valid_range;
290
291 if (pattern->val.range.min > pattern->val.range.max)
292 goto not_valid_range;
293
294 pattern->val.range.min_set = 1;
295 pattern->val.range.max_set = 1;
296 return 1;
297
298 not_valid_range:
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100299 memprintf(err, "'%s' is not a valid number range", text);
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100300 return 0;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100301}
302
303/* Parse a range of positive 2-component versions delimited by either ':' or
304 * '-'. The version consists in a major and a minor, both of which must be
305 * smaller than 65536, because internally they will be represented as a 32-bit
306 * integer.
307 * If only one version is read, it is set as both min and max. Just like for
308 * pure integers, an operator may be specified as the prefix, among this list
309 * of 5 :
310 *
311 * 0:eq, 1:gt, 2:ge, 3:lt, 4:le
312 *
313 * The default operator is "eq". It supports range matching. Ranges are
314 * rejected for other operators. The operator may be changed at any time.
315 * The operator is stored in the 'opaque' argument. This allows constructs
316 * such as the following one :
317 *
318 * acl obsolete_ssl ssl_req_proto lt 3
319 * acl unsupported_ssl ssl_req_proto gt 3.1
320 * acl valid_ssl ssl_req_proto 3.0-3.1
321 *
322 */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200323int pat_parse_dotted_ver(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100324{
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100325 const char *ptr = text;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100326
Thierry FOURNIER07ee64e2015-07-06 23:43:03 +0200327 pattern->type = SMP_T_SINT;
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100328
329 /* Search ':' or '-' separator. */
330 while (*ptr != '\0' && *ptr != ':' && *ptr != '-')
331 ptr++;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100332
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100333 /* If separator not found. */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100334 if (*ptr == '\0' && ptr > text) {
335 if (strl2llrc_dotted(text, ptr-text, &pattern->val.range.min) != 0) {
336 memprintf(err, "'%s' is not a dotted number", text);
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100337 return 0;
338 }
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100339 pattern->val.range.max = pattern->val.range.min;
340 pattern->val.range.min_set = 1;
341 pattern->val.range.max_set = 1;
342 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100343 }
344
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100345 /* If the separator is the first character. */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100346 if (ptr == text && *(ptr+1) != '\0') {
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100347 if (strl2llrc_dotted(ptr+1, strlen(ptr+1), &pattern->val.range.max) != 0) {
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100348 memprintf(err, "'%s' is not a valid dotted number range", text);
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100349 return 0;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100350 }
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100351 pattern->val.range.min_set = 0;
352 pattern->val.range.max_set = 1;
353 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100354 }
355
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100356 /* If separator is the last character. */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100357 if (ptr == &text[strlen(text)-1]) {
358 if (strl2llrc_dotted(text, ptr-text, &pattern->val.range.min) != 0) {
359 memprintf(err, "'%s' is not a valid dotted number range", text);
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100360 return 0;
361 }
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100362 pattern->val.range.min_set = 1;
363 pattern->val.range.max_set = 0;
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100364 return 1;
365 }
366
367 /* Else, parse two numbers. */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100368 if (strl2llrc_dotted(text, ptr-text, &pattern->val.range.min) != 0) {
369 memprintf(err, "'%s' is not a valid dotted number range", text);
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100370 return 0;
371 }
372 if (strl2llrc_dotted(ptr+1, strlen(ptr+1), &pattern->val.range.max) != 0) {
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100373 memprintf(err, "'%s' is not a valid dotted number range", text);
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100374 return 0;
375 }
376 if (pattern->val.range.min > pattern->val.range.max) {
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100377 memprintf(err, "'%s' is not a valid dotted number range", text);
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100378 return 0;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100379 }
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100380 pattern->val.range.min_set = 1;
381 pattern->val.range.max_set = 1;
382 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100383}
384
385/* Parse an IP address and an optional mask in the form addr[/mask].
386 * The addr may either be an IPv4 address or a hostname. The mask
387 * may either be a dotted mask or a number of bits. Returns 1 if OK,
388 * otherwise 0. NOTE: IP address patterns are typed (IPV4/IPV6).
389 */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200390int pat_parse_ip(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100391{
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200392 if (str2net(text, !(mflags & PAT_MF_NO_DNS) && (global.mode & MODE_STARTING),
Thierry FOURNIERfc7ac7b2014-02-11 15:23:04 +0100393 &pattern->val.ipv4.addr, &pattern->val.ipv4.mask)) {
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100394 pattern->type = SMP_T_IPV4;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100395 return 1;
396 }
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100397 else if (str62net(text, &pattern->val.ipv6.addr, &pattern->val.ipv6.mask)) {
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100398 pattern->type = SMP_T_IPV6;
399 return 1;
400 }
401 else {
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100402 memprintf(err, "'%s' is not a valid IPv4 or IPv6 address", text);
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100403 return 0;
404 }
405}
406
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100407/*
408 *
409 * These functions are exported and may be used by any other component.
410 *
Joseph Herlant4189d672018-11-15 10:22:31 -0800411 * This function just takes a sample <smp> and checks if this sample matches
412 * with the pattern <pattern>. This function returns only PAT_MATCH or
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100413 * PAT_NOMATCH.
414 *
415 */
416
417/* always return false */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100418struct pattern *pat_match_nothing(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100419{
Thierry FOURNIER136f9d32015-08-19 09:07:19 +0200420 if (smp->data.u.sint) {
Thierry FOURNIERe5978bf2014-03-17 19:53:10 +0100421 if (fill) {
Thierry FOURNIER503bb092015-08-19 08:35:43 +0200422 static_pattern.data = NULL;
Thierry FOURNIERe5978bf2014-03-17 19:53:10 +0100423 static_pattern.ref = NULL;
Thierry FOURNIERe5978bf2014-03-17 19:53:10 +0100424 static_pattern.type = 0;
425 static_pattern.ptr.str = NULL;
426 }
427 return &static_pattern;
428 }
429 else
430 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100431}
432
433
Joseph Herlant4189d672018-11-15 10:22:31 -0800434/* NB: For two strings to be identical, it is required that their length match */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100435struct pattern *pat_match_str(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100436{
437 int icase;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100438 struct ebmb_node *node;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100439 struct pattern_tree *elt;
440 struct pattern_list *lst;
441 struct pattern *pattern;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200442 struct pattern *ret = NULL;
443 struct lru64 *lru = NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100444
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100445 /* Lookup a string in the expression's pattern tree. */
446 if (!eb_is_empty(&expr->pattern_tree)) {
Christopher Fauletb4cf7ab2020-06-30 18:52:32 +0200447 char prev = 0;
448
449 if (smp->data.u.str.data < smp->data.u.str.size) {
450 /* we may have to force a trailing zero on the test pattern and
Thierry Fourniera68affe2020-11-10 20:51:36 +0100451 * the buffer is large enough to accommodate it. If the flag
452 * CONST is set, duplicate the string
Christopher Fauletb4cf7ab2020-06-30 18:52:32 +0200453 */
454 prev = smp->data.u.str.area[smp->data.u.str.data];
Thierry Fourniera68affe2020-11-10 20:51:36 +0100455 if (prev) {
456 if (smp->flags & SMP_F_CONST) {
457 if (!smp_dup(smp))
458 return NULL;
459 } else {
460 smp->data.u.str.area[smp->data.u.str.data] = '\0';
461 }
462 }
Christopher Fauletb4cf7ab2020-06-30 18:52:32 +0200463 }
464 else {
465 /* Otherwise, the sample is duplicated. A trailing zero
466 * is automatically added to the string.
467 */
468 if (!smp_dup(smp))
469 return NULL;
470 }
471
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200472 node = ebst_lookup(&expr->pattern_tree, smp->data.u.str.area);
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100473 if (prev)
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200474 smp->data.u.str.area[smp->data.u.str.data] = prev;
Willy Tarreauc93da692020-10-29 09:41:34 +0100475
476 while (node) {
477 elt = ebmb_entry(node, struct pattern_tree, node);
478 if (elt->ref->gen_id != expr->ref->curr_gen) {
479 node = ebmb_next(node);
480 continue;
481 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100482 if (fill) {
Thierry FOURNIER503bb092015-08-19 08:35:43 +0200483 static_pattern.data = elt->data;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +0100484 static_pattern.ref = elt->ref;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200485 static_pattern.sflags = PAT_SF_TREE;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100486 static_pattern.type = SMP_T_STR;
487 static_pattern.ptr.str = (char *)elt->node.key;
488 }
489 return &static_pattern;
490 }
491 }
492
493 /* look in the list */
Willy Tarreauf3045d22015-04-29 16:24:50 +0200494 if (pat_lru_tree) {
Willy Tarreauaee93142015-05-04 17:18:42 +0200495 unsigned long long seed = pat_lru_seed ^ (long)expr;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200496
Dragan Dosen967e7e72020-12-22 13:22:34 +0100497 lru = lru64_get(XXH3(smp->data.u.str.area, smp->data.u.str.data, seed),
Willy Tarreau3ee0de12020-11-02 15:26:51 +0100498 pat_lru_tree, expr, expr->ref->revision);
Willy Tarreau403bfbb2019-10-23 06:59:31 +0200499 if (lru && lru->domain) {
Emeric Brunb5997f72017-07-03 11:34:05 +0200500 ret = lru->data;
Emeric Brunb5997f72017-07-03 11:34:05 +0200501 return ret;
502 }
Willy Tarreauf3045d22015-04-29 16:24:50 +0200503 }
504
Emeric Brunb5997f72017-07-03 11:34:05 +0200505
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100506 list_for_each_entry(lst, &expr->patterns, list) {
507 pattern = &lst->pat;
508
Willy Tarreauc93da692020-10-29 09:41:34 +0100509 if (pattern->ref->gen_id != expr->ref->curr_gen)
510 continue;
511
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200512 if (pattern->len != smp->data.u.str.data)
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100513 continue;
514
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200515 icase = expr->mflags & PAT_MF_IGNORE_CASE;
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200516 if ((icase && strncasecmp(pattern->ptr.str, smp->data.u.str.area, smp->data.u.str.data) == 0) ||
517 (!icase && strncmp(pattern->ptr.str, smp->data.u.str.area, smp->data.u.str.data) == 0)) {
Willy Tarreauf3045d22015-04-29 16:24:50 +0200518 ret = pattern;
519 break;
520 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100521 }
522
Willy Tarreau403bfbb2019-10-23 06:59:31 +0200523 if (lru)
Willy Tarreau3ee0de12020-11-02 15:26:51 +0100524 lru64_commit(lru, ret, expr, expr->ref->revision, NULL);
Willy Tarreauf3045d22015-04-29 16:24:50 +0200525
526 return ret;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100527}
528
529/* NB: For two binaries buf to be identical, it is required that their lengths match */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100530struct pattern *pat_match_bin(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100531{
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100532 struct pattern_list *lst;
533 struct pattern *pattern;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200534 struct pattern *ret = NULL;
535 struct lru64 *lru = NULL;
536
537 if (pat_lru_tree) {
Willy Tarreauaee93142015-05-04 17:18:42 +0200538 unsigned long long seed = pat_lru_seed ^ (long)expr;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100539
Dragan Dosen967e7e72020-12-22 13:22:34 +0100540 lru = lru64_get(XXH3(smp->data.u.str.area, smp->data.u.str.data, seed),
Willy Tarreau3ee0de12020-11-02 15:26:51 +0100541 pat_lru_tree, expr, expr->ref->revision);
Willy Tarreau403bfbb2019-10-23 06:59:31 +0200542 if (lru && lru->domain) {
Emeric Brunb5997f72017-07-03 11:34:05 +0200543 ret = lru->data;
Emeric Brunb5997f72017-07-03 11:34:05 +0200544 return ret;
545 }
Willy Tarreauf3045d22015-04-29 16:24:50 +0200546 }
547
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100548 list_for_each_entry(lst, &expr->patterns, list) {
549 pattern = &lst->pat;
550
Willy Tarreauc93da692020-10-29 09:41:34 +0100551 if (pattern->ref->gen_id != expr->ref->curr_gen)
552 continue;
553
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200554 if (pattern->len != smp->data.u.str.data)
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100555 continue;
556
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200557 if (memcmp(pattern->ptr.str, smp->data.u.str.area, smp->data.u.str.data) == 0) {
Willy Tarreauf3045d22015-04-29 16:24:50 +0200558 ret = pattern;
559 break;
560 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100561 }
562
Willy Tarreau403bfbb2019-10-23 06:59:31 +0200563 if (lru)
Willy Tarreau3ee0de12020-11-02 15:26:51 +0100564 lru64_commit(lru, ret, expr, expr->ref->revision, NULL);
Willy Tarreauf3045d22015-04-29 16:24:50 +0200565
566 return ret;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100567}
568
569/* Executes a regex. It temporarily changes the data to add a trailing zero,
Thierry Fournier8feaa662016-02-10 22:55:20 +0100570 * and restores the previous character when leaving. This function fills
571 * a matching array.
572 */
573struct pattern *pat_match_regm(struct sample *smp, struct pattern_expr *expr, int fill)
574{
575 struct pattern_list *lst;
576 struct pattern *pattern;
577 struct pattern *ret = NULL;
578
579 list_for_each_entry(lst, &expr->patterns, list) {
580 pattern = &lst->pat;
581
Willy Tarreauc93da692020-10-29 09:41:34 +0100582 if (pattern->ref->gen_id != expr->ref->curr_gen)
583 continue;
584
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200585 if (regex_exec_match2(pattern->ptr.reg, smp->data.u.str.area, smp->data.u.str.data,
Thierry Fournier8feaa662016-02-10 22:55:20 +0100586 MAX_MATCH, pmatch, 0)) {
587 ret = pattern;
588 smp->ctx.a[0] = pmatch;
589 break;
590 }
591 }
592
593 return ret;
594}
595
596/* Executes a regex. It temporarily changes the data to add a trailing zero,
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100597 * and restores the previous character when leaving.
598 */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100599struct pattern *pat_match_reg(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100600{
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100601 struct pattern_list *lst;
602 struct pattern *pattern;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200603 struct pattern *ret = NULL;
604 struct lru64 *lru = NULL;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100605
Willy Tarreauf3045d22015-04-29 16:24:50 +0200606 if (pat_lru_tree) {
Willy Tarreauaee93142015-05-04 17:18:42 +0200607 unsigned long long seed = pat_lru_seed ^ (long)expr;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200608
Dragan Dosen967e7e72020-12-22 13:22:34 +0100609 lru = lru64_get(XXH3(smp->data.u.str.area, smp->data.u.str.data, seed),
Willy Tarreau3ee0de12020-11-02 15:26:51 +0100610 pat_lru_tree, expr, expr->ref->revision);
Willy Tarreau403bfbb2019-10-23 06:59:31 +0200611 if (lru && lru->domain) {
Emeric Brunb5997f72017-07-03 11:34:05 +0200612 ret = lru->data;
Emeric Brunb5997f72017-07-03 11:34:05 +0200613 return ret;
614 }
Willy Tarreauf3045d22015-04-29 16:24:50 +0200615 }
616
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100617 list_for_each_entry(lst, &expr->patterns, list) {
618 pattern = &lst->pat;
619
Willy Tarreauc93da692020-10-29 09:41:34 +0100620 if (pattern->ref->gen_id != expr->ref->curr_gen)
621 continue;
622
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200623 if (regex_exec2(pattern->ptr.reg, smp->data.u.str.area, smp->data.u.str.data)) {
Willy Tarreauf3045d22015-04-29 16:24:50 +0200624 ret = pattern;
625 break;
626 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100627 }
Willy Tarreauf3045d22015-04-29 16:24:50 +0200628
Willy Tarreau403bfbb2019-10-23 06:59:31 +0200629 if (lru)
Willy Tarreau3ee0de12020-11-02 15:26:51 +0100630 lru64_commit(lru, ret, expr, expr->ref->revision, NULL);
Willy Tarreauf3045d22015-04-29 16:24:50 +0200631
632 return ret;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100633}
634
635/* Checks that the pattern matches the beginning of the tested string. */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100636struct pattern *pat_match_beg(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100637{
638 int icase;
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +0200639 struct ebmb_node *node;
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +0200640 struct pattern_tree *elt;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100641 struct pattern_list *lst;
642 struct pattern *pattern;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200643 struct pattern *ret = NULL;
644 struct lru64 *lru = NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100645
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +0200646 /* Lookup a string in the expression's pattern tree. */
647 if (!eb_is_empty(&expr->pattern_tree)) {
Christopher Fauletb4cf7ab2020-06-30 18:52:32 +0200648 char prev = 0;
649
650 if (smp->data.u.str.data < smp->data.u.str.size) {
651 /* we may have to force a trailing zero on the test pattern and
652 * the buffer is large enough to accommodate it.
653 */
654 prev = smp->data.u.str.area[smp->data.u.str.data];
655 if (prev)
656 smp->data.u.str.area[smp->data.u.str.data] = '\0';
657 }
658 else {
659 /* Otherwise, the sample is duplicated. A trailing zero
660 * is automatically added to the string.
661 */
662 if (!smp_dup(smp))
663 return NULL;
664 }
665
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200666 node = ebmb_lookup_longest(&expr->pattern_tree,
667 smp->data.u.str.area);
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +0200668 if (prev)
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200669 smp->data.u.str.area[smp->data.u.str.data] = prev;
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +0200670
Willy Tarreauc93da692020-10-29 09:41:34 +0100671 while (node) {
672 elt = ebmb_entry(node, struct pattern_tree, node);
673 if (elt->ref->gen_id != expr->ref->curr_gen) {
674 node = ebmb_next(node);
675 continue;
676 }
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +0200677 if (fill) {
Thierry FOURNIER503bb092015-08-19 08:35:43 +0200678 static_pattern.data = elt->data;
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +0200679 static_pattern.ref = elt->ref;
680 static_pattern.sflags = PAT_SF_TREE;
681 static_pattern.type = SMP_T_STR;
682 static_pattern.ptr.str = (char *)elt->node.key;
683 }
684 return &static_pattern;
685 }
686 }
687
688 /* look in the list */
Willy Tarreauf3045d22015-04-29 16:24:50 +0200689 if (pat_lru_tree) {
Willy Tarreauaee93142015-05-04 17:18:42 +0200690 unsigned long long seed = pat_lru_seed ^ (long)expr;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200691
Dragan Dosen967e7e72020-12-22 13:22:34 +0100692 lru = lru64_get(XXH3(smp->data.u.str.area, smp->data.u.str.data, seed),
Willy Tarreau3ee0de12020-11-02 15:26:51 +0100693 pat_lru_tree, expr, expr->ref->revision);
Willy Tarreau403bfbb2019-10-23 06:59:31 +0200694 if (lru && lru->domain) {
Emeric Brunb5997f72017-07-03 11:34:05 +0200695 ret = lru->data;
Emeric Brunb5997f72017-07-03 11:34:05 +0200696 return ret;
697 }
Willy Tarreauf3045d22015-04-29 16:24:50 +0200698 }
699
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100700 list_for_each_entry(lst, &expr->patterns, list) {
701 pattern = &lst->pat;
702
Willy Tarreauc93da692020-10-29 09:41:34 +0100703 if (pattern->ref->gen_id != expr->ref->curr_gen)
704 continue;
705
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200706 if (pattern->len > smp->data.u.str.data)
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100707 continue;
708
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200709 icase = expr->mflags & PAT_MF_IGNORE_CASE;
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200710 if ((icase && strncasecmp(pattern->ptr.str, smp->data.u.str.area, pattern->len) != 0) ||
711 (!icase && strncmp(pattern->ptr.str, smp->data.u.str.area, pattern->len) != 0))
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100712 continue;
713
Willy Tarreauf3045d22015-04-29 16:24:50 +0200714 ret = pattern;
715 break;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100716 }
Willy Tarreauf3045d22015-04-29 16:24:50 +0200717
Willy Tarreau403bfbb2019-10-23 06:59:31 +0200718 if (lru)
Willy Tarreau3ee0de12020-11-02 15:26:51 +0100719 lru64_commit(lru, ret, expr, expr->ref->revision, NULL);
Willy Tarreauf3045d22015-04-29 16:24:50 +0200720
721 return ret;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100722}
723
724/* Checks that the pattern matches the end of the tested string. */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100725struct pattern *pat_match_end(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100726{
727 int icase;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100728 struct pattern_list *lst;
729 struct pattern *pattern;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200730 struct pattern *ret = NULL;
731 struct lru64 *lru = NULL;
732
733 if (pat_lru_tree) {
Willy Tarreauaee93142015-05-04 17:18:42 +0200734 unsigned long long seed = pat_lru_seed ^ (long)expr;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200735
Dragan Dosen967e7e72020-12-22 13:22:34 +0100736 lru = lru64_get(XXH3(smp->data.u.str.area, smp->data.u.str.data, seed),
Willy Tarreau3ee0de12020-11-02 15:26:51 +0100737 pat_lru_tree, expr, expr->ref->revision);
Willy Tarreau403bfbb2019-10-23 06:59:31 +0200738 if (lru && lru->domain) {
Emeric Brunb5997f72017-07-03 11:34:05 +0200739 ret = lru->data;
Emeric Brunb5997f72017-07-03 11:34:05 +0200740 return ret;
741 }
Willy Tarreauf3045d22015-04-29 16:24:50 +0200742 }
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100743
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100744 list_for_each_entry(lst, &expr->patterns, list) {
745 pattern = &lst->pat;
746
Willy Tarreauc93da692020-10-29 09:41:34 +0100747 if (pattern->ref->gen_id != expr->ref->curr_gen)
748 continue;
749
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200750 if (pattern->len > smp->data.u.str.data)
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100751 continue;
752
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200753 icase = expr->mflags & PAT_MF_IGNORE_CASE;
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200754 if ((icase && strncasecmp(pattern->ptr.str, smp->data.u.str.area + smp->data.u.str.data - pattern->len, pattern->len) != 0) ||
755 (!icase && strncmp(pattern->ptr.str, smp->data.u.str.area + smp->data.u.str.data - pattern->len, pattern->len) != 0))
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100756 continue;
757
Willy Tarreauf3045d22015-04-29 16:24:50 +0200758 ret = pattern;
759 break;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100760 }
Willy Tarreauf3045d22015-04-29 16:24:50 +0200761
Willy Tarreau403bfbb2019-10-23 06:59:31 +0200762 if (lru)
Willy Tarreau3ee0de12020-11-02 15:26:51 +0100763 lru64_commit(lru, ret, expr, expr->ref->revision, NULL);
Willy Tarreauf3045d22015-04-29 16:24:50 +0200764
765 return ret;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100766}
767
768/* Checks that the pattern is included inside the tested string.
769 * NB: Suboptimal, should be rewritten using a Boyer-Moore method.
770 */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100771struct pattern *pat_match_sub(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100772{
773 int icase;
774 char *end;
775 char *c;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100776 struct pattern_list *lst;
777 struct pattern *pattern;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200778 struct pattern *ret = NULL;
779 struct lru64 *lru = NULL;
780
781 if (pat_lru_tree) {
Willy Tarreauaee93142015-05-04 17:18:42 +0200782 unsigned long long seed = pat_lru_seed ^ (long)expr;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200783
Dragan Dosen967e7e72020-12-22 13:22:34 +0100784 lru = lru64_get(XXH3(smp->data.u.str.area, smp->data.u.str.data, seed),
Willy Tarreau3ee0de12020-11-02 15:26:51 +0100785 pat_lru_tree, expr, expr->ref->revision);
Willy Tarreau403bfbb2019-10-23 06:59:31 +0200786 if (lru && lru->domain) {
Emeric Brunb5997f72017-07-03 11:34:05 +0200787 ret = lru->data;
Emeric Brunb5997f72017-07-03 11:34:05 +0200788 return ret;
789 }
Willy Tarreauf3045d22015-04-29 16:24:50 +0200790 }
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100791
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100792 list_for_each_entry(lst, &expr->patterns, list) {
793 pattern = &lst->pat;
794
Willy Tarreauc93da692020-10-29 09:41:34 +0100795 if (pattern->ref->gen_id != expr->ref->curr_gen)
796 continue;
797
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200798 if (pattern->len > smp->data.u.str.data)
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100799 continue;
800
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200801 end = smp->data.u.str.area + smp->data.u.str.data - pattern->len;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200802 icase = expr->mflags & PAT_MF_IGNORE_CASE;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100803 if (icase) {
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200804 for (c = smp->data.u.str.area; c <= end; c++) {
Willy Tarreauf278eec2020-07-05 21:46:32 +0200805 if (tolower((unsigned char)*c) != tolower((unsigned char)*pattern->ptr.str))
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100806 continue;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200807 if (strncasecmp(pattern->ptr.str, c, pattern->len) == 0) {
808 ret = pattern;
809 goto leave;
810 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100811 }
812 } else {
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200813 for (c = smp->data.u.str.area; c <= end; c++) {
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100814 if (*c != *pattern->ptr.str)
815 continue;
Willy Tarreauf3045d22015-04-29 16:24:50 +0200816 if (strncmp(pattern->ptr.str, c, pattern->len) == 0) {
817 ret = pattern;
818 goto leave;
819 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100820 }
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100821 }
822 }
Willy Tarreauf3045d22015-04-29 16:24:50 +0200823 leave:
Willy Tarreau403bfbb2019-10-23 06:59:31 +0200824 if (lru)
Willy Tarreau3ee0de12020-11-02 15:26:51 +0100825 lru64_commit(lru, ret, expr, expr->ref->revision, NULL);
Willy Tarreauf3045d22015-04-29 16:24:50 +0200826
827 return ret;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100828}
829
830/* This one is used by other real functions. It checks that the pattern is
831 * included inside the tested string, but enclosed between the specified
832 * delimiters or at the beginning or end of the string. The delimiters are
833 * provided as an unsigned int made by make_4delim() and match up to 4 different
834 * delimiters. Delimiters are stripped at the beginning and end of the pattern.
835 */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200836static int match_word(struct sample *smp, struct pattern *pattern, int mflags, unsigned int delimiters)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100837{
838 int may_match, icase;
839 char *c, *end;
840 char *ps;
841 int pl;
842
843 pl = pattern->len;
844 ps = pattern->ptr.str;
845
846 while (pl > 0 && is_delimiter(*ps, delimiters)) {
847 pl--;
848 ps++;
849 }
850
851 while (pl > 0 && is_delimiter(ps[pl - 1], delimiters))
852 pl--;
853
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200854 if (pl > smp->data.u.str.data)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100855 return PAT_NOMATCH;
856
857 may_match = 1;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200858 icase = mflags & PAT_MF_IGNORE_CASE;
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200859 end = smp->data.u.str.area + smp->data.u.str.data - pl;
860 for (c = smp->data.u.str.area; c <= end; c++) {
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100861 if (is_delimiter(*c, delimiters)) {
862 may_match = 1;
863 continue;
864 }
865
866 if (!may_match)
867 continue;
868
869 if (icase) {
Willy Tarreauf278eec2020-07-05 21:46:32 +0200870 if ((tolower((unsigned char)*c) == tolower((unsigned char)*ps)) &&
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100871 (strncasecmp(ps, c, pl) == 0) &&
872 (c == end || is_delimiter(c[pl], delimiters)))
873 return PAT_MATCH;
874 } else {
875 if ((*c == *ps) &&
876 (strncmp(ps, c, pl) == 0) &&
877 (c == end || is_delimiter(c[pl], delimiters)))
878 return PAT_MATCH;
879 }
880 may_match = 0;
881 }
882 return PAT_NOMATCH;
883}
884
885/* Checks that the pattern is included inside the tested string, but enclosed
886 * between the delimiters '?' or '/' or at the beginning or end of the string.
887 * Delimiters at the beginning or end of the pattern are ignored.
888 */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100889struct pattern *pat_match_dir(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100890{
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100891 struct pattern_list *lst;
892 struct pattern *pattern;
893
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100894 list_for_each_entry(lst, &expr->patterns, list) {
895 pattern = &lst->pat;
Willy Tarreauc93da692020-10-29 09:41:34 +0100896
897 if (pattern->ref->gen_id != expr->ref->curr_gen)
898 continue;
899
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200900 if (match_word(smp, pattern, expr->mflags, make_4delim('/', '?', '?', '?')))
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100901 return pattern;
902 }
903 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100904}
905
906/* Checks that the pattern is included inside the tested string, but enclosed
907 * between the delmiters '/', '?', '.' or ":" or at the beginning or end of
908 * the string. Delimiters at the beginning or end of the pattern are ignored.
909 */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100910struct pattern *pat_match_dom(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100911{
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100912 struct pattern_list *lst;
913 struct pattern *pattern;
914
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100915 list_for_each_entry(lst, &expr->patterns, list) {
916 pattern = &lst->pat;
Willy Tarreauc93da692020-10-29 09:41:34 +0100917
918 if (pattern->ref->gen_id != expr->ref->curr_gen)
919 continue;
920
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200921 if (match_word(smp, pattern, expr->mflags, make_4delim('/', '?', '.', ':')))
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100922 return pattern;
923 }
924 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100925}
926
927/* Checks that the integer in <test> is included between min and max */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100928struct pattern *pat_match_int(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100929{
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100930 struct pattern_list *lst;
931 struct pattern *pattern;
932
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100933 list_for_each_entry(lst, &expr->patterns, list) {
934 pattern = &lst->pat;
Willy Tarreauc93da692020-10-29 09:41:34 +0100935
936 if (pattern->ref->gen_id != expr->ref->curr_gen)
937 continue;
938
Thierry FOURNIER136f9d32015-08-19 09:07:19 +0200939 if ((!pattern->val.range.min_set || pattern->val.range.min <= smp->data.u.sint) &&
940 (!pattern->val.range.max_set || smp->data.u.sint <= pattern->val.range.max))
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100941 return pattern;
942 }
943 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100944}
945
946/* Checks that the length of the pattern in <test> is included between min and max */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100947struct pattern *pat_match_len(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100948{
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100949 struct pattern_list *lst;
950 struct pattern *pattern;
951
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100952 list_for_each_entry(lst, &expr->patterns, list) {
953 pattern = &lst->pat;
Willy Tarreauc93da692020-10-29 09:41:34 +0100954
955 if (pattern->ref->gen_id != expr->ref->curr_gen)
956 continue;
957
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200958 if ((!pattern->val.range.min_set || pattern->val.range.min <= smp->data.u.str.data) &&
959 (!pattern->val.range.max_set || smp->data.u.str.data <= pattern->val.range.max))
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100960 return pattern;
961 }
962 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100963}
964
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100965struct pattern *pat_match_ip(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100966{
967 unsigned int v4; /* in network byte order */
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100968 struct in6_addr tmp6;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100969 struct in_addr *s;
970 struct ebmb_node *node;
971 struct pattern_tree *elt;
972 struct pattern_list *lst;
973 struct pattern *pattern;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100974
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100975 /* The input sample is IPv4. Try to match in the trees. */
Thierry FOURNIER8c542ca2015-08-19 09:00:18 +0200976 if (smp->data.type == SMP_T_IPV4) {
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100977 /* Lookup an IPv4 address in the expression's pattern tree using
978 * the longest match method.
979 */
Thierry FOURNIER136f9d32015-08-19 09:07:19 +0200980 s = &smp->data.u.ipv4;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100981 node = ebmb_lookup_longest(&expr->pattern_tree, &s->s_addr);
Willy Tarreauc93da692020-10-29 09:41:34 +0100982 while (node) {
983 elt = ebmb_entry(node, struct pattern_tree, node);
984 if (elt->ref->gen_id != expr->ref->curr_gen) {
985 node = ebmb_next(node);
986 continue;
987 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100988 if (fill) {
Thierry FOURNIER503bb092015-08-19 08:35:43 +0200989 static_pattern.data = elt->data;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +0100990 static_pattern.ref = elt->ref;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200991 static_pattern.sflags = PAT_SF_TREE;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100992 static_pattern.type = SMP_T_IPV4;
Willy Tarreau296cfd12020-02-25 09:58:41 +0100993 static_pattern.val.ipv4.addr.s_addr = read_u32(elt->node.key);
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100994 if (!cidr2dotted(elt->node.node.pfx, &static_pattern.val.ipv4.mask))
995 return NULL;
996 }
997 return &static_pattern;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100998 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100999
Thayne McCombs8f0cc5c2021-01-07 21:35:52 -07001000 /* The IPv4 sample don't match the IPv4 tree. Convert the IPv4
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001001 * sample address to IPv6 with the mapping method using the ::ffff:
1002 * prefix, and try to lookup in the IPv6 tree.
1003 */
1004 memset(&tmp6, 0, 10);
Willy Tarreau296cfd12020-02-25 09:58:41 +01001005 write_u16(&tmp6.s6_addr[10], htons(0xffff));
1006 write_u32(&tmp6.s6_addr[12], smp->data.u.ipv4.s_addr);
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001007 node = ebmb_lookup_longest(&expr->pattern_tree_2, &tmp6);
Willy Tarreauc93da692020-10-29 09:41:34 +01001008 while (node) {
1009 elt = ebmb_entry(node, struct pattern_tree, node);
1010 if (elt->ref->gen_id != expr->ref->curr_gen) {
1011 node = ebmb_next(node);
1012 continue;
1013 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001014 if (fill) {
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001015 static_pattern.data = elt->data;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +01001016 static_pattern.ref = elt->ref;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02001017 static_pattern.sflags = PAT_SF_TREE;
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001018 static_pattern.type = SMP_T_IPV6;
Willy Tarreau296cfd12020-02-25 09:58:41 +01001019 memcpy(&static_pattern.val.ipv6.addr, elt->node.key, 16);
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001020 static_pattern.val.ipv6.mask = elt->node.node.pfx;
1021 }
1022 return &static_pattern;
1023 }
1024 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +01001025
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001026 /* The input sample is IPv6. Try to match in the trees. */
Thierry FOURNIER8c542ca2015-08-19 09:00:18 +02001027 if (smp->data.type == SMP_T_IPV6) {
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001028 /* Lookup an IPv6 address in the expression's pattern tree using
1029 * the longest match method.
1030 */
Thierry FOURNIER136f9d32015-08-19 09:07:19 +02001031 node = ebmb_lookup_longest(&expr->pattern_tree_2, &smp->data.u.ipv6);
Willy Tarreauc93da692020-10-29 09:41:34 +01001032 while (node) {
1033 elt = ebmb_entry(node, struct pattern_tree, node);
1034 if (elt->ref->gen_id != expr->ref->curr_gen) {
1035 node = ebmb_next(node);
1036 continue;
1037 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001038 if (fill) {
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001039 static_pattern.data = elt->data;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +01001040 static_pattern.ref = elt->ref;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02001041 static_pattern.sflags = PAT_SF_TREE;
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001042 static_pattern.type = SMP_T_IPV6;
Willy Tarreau296cfd12020-02-25 09:58:41 +01001043 memcpy(&static_pattern.val.ipv6.addr, elt->node.key, 16);
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001044 static_pattern.val.ipv6.mask = elt->node.node.pfx;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +01001045 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001046 return &static_pattern;
1047 }
1048
1049 /* Try to convert 6 to 4 when the start of the ipv6 address match the
1050 * following forms :
1051 * - ::ffff:ip:v4 (ipv4 mapped)
1052 * - ::0000:ip:v4 (old ipv4 mapped)
1053 * - 2002:ip:v4:: (6to4)
1054 */
Willy Tarreau296cfd12020-02-25 09:58:41 +01001055 if ((read_u64(&smp->data.u.ipv6.s6_addr[0]) == 0 &&
1056 (read_u32(&smp->data.u.ipv6.s6_addr[8]) == 0 ||
1057 read_u32(&smp->data.u.ipv6.s6_addr[8]) == htonl(0xFFFF))) ||
1058 read_u16(&smp->data.u.ipv6.s6_addr[0]) == htons(0x2002)) {
1059 if (read_u32(&smp->data.u.ipv6.s6_addr[0]) == 0)
1060 v4 = read_u32(&smp->data.u.ipv6.s6_addr[12]);
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001061 else
Willy Tarreau296cfd12020-02-25 09:58:41 +01001062 v4 = htonl((ntohs(read_u16(&smp->data.u.ipv6.s6_addr[2])) << 16) +
1063 ntohs(read_u16(&smp->data.u.ipv6.s6_addr[4])));
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001064
1065 /* Lookup an IPv4 address in the expression's pattern tree using the longest
1066 * match method.
1067 */
1068 node = ebmb_lookup_longest(&expr->pattern_tree, &v4);
Willy Tarreauc93da692020-10-29 09:41:34 +01001069 while (node) {
1070 elt = ebmb_entry(node, struct pattern_tree, node);
1071 if (elt->ref->gen_id != expr->ref->curr_gen) {
1072 node = ebmb_next(node);
1073 continue;
1074 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001075 if (fill) {
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001076 static_pattern.data = elt->data;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +01001077 static_pattern.ref = elt->ref;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02001078 static_pattern.sflags = PAT_SF_TREE;
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001079 static_pattern.type = SMP_T_IPV4;
Willy Tarreau296cfd12020-02-25 09:58:41 +01001080 static_pattern.val.ipv4.addr.s_addr = read_u32(elt->node.key);
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001081 if (!cidr2dotted(elt->node.node.pfx, &static_pattern.val.ipv4.mask))
1082 return NULL;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +01001083 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001084 return &static_pattern;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +01001085 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001086 }
1087 }
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +01001088
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001089 /* Lookup in the list. the list contain only IPv4 patterns */
1090 list_for_each_entry(lst, &expr->patterns, list) {
1091 pattern = &lst->pat;
1092
Willy Tarreauc93da692020-10-29 09:41:34 +01001093 if (pattern->ref->gen_id != expr->ref->curr_gen)
1094 continue;
1095
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001096 /* The input sample is IPv4, use it as is. */
Thierry FOURNIER8c542ca2015-08-19 09:00:18 +02001097 if (smp->data.type == SMP_T_IPV4) {
Thierry FOURNIER136f9d32015-08-19 09:07:19 +02001098 v4 = smp->data.u.ipv4.s_addr;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +01001099 }
Thierry FOURNIER8c542ca2015-08-19 09:00:18 +02001100 else if (smp->data.type == SMP_T_IPV6) {
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001101 /* v4 match on a V6 sample. We want to check at least for
1102 * the following forms :
1103 * - ::ffff:ip:v4 (ipv4 mapped)
1104 * - ::0000:ip:v4 (old ipv4 mapped)
1105 * - 2002:ip:v4:: (6to4)
1106 */
Willy Tarreau296cfd12020-02-25 09:58:41 +01001107 if (read_u64(&smp->data.u.ipv6.s6_addr[0]) == 0 &&
1108 (read_u32(&smp->data.u.ipv6.s6_addr[8]) == 0 ||
1109 read_u32(&smp->data.u.ipv6.s6_addr[8]) == htonl(0xFFFF))) {
1110 v4 = read_u32(&smp->data.u.ipv6.s6_addr[12]);
Thierry FOURNIER5338eea2013-12-16 14:22:13 +01001111 }
Willy Tarreau296cfd12020-02-25 09:58:41 +01001112 else if (read_u16(&smp->data.u.ipv6.s6_addr[0]) == htons(0x2002)) {
1113 v4 = htonl((ntohs(read_u16(&smp->data.u.ipv6.s6_addr[2])) << 16) +
1114 ntohs(read_u16(&smp->data.u.ipv6.s6_addr[4])));
Thierry FOURNIER5338eea2013-12-16 14:22:13 +01001115 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001116 else
Thierry FOURNIER5338eea2013-12-16 14:22:13 +01001117 continue;
Andreas Seltenreichf0653192016-03-03 20:08:35 +01001118 } else {
1119 /* impossible */
1120 continue;
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001121 }
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +01001122
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001123 /* Check if the input sample match the current pattern. */
1124 if (((v4 ^ pattern->val.ipv4.addr.s_addr) & pattern->val.ipv4.mask.s_addr) == 0)
Thierry FOURNIER5338eea2013-12-16 14:22:13 +01001125 return pattern;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +01001126 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +01001127 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +01001128}
1129
Willy Tarreau867a8a52020-11-03 11:22:04 +01001130/* finds the pattern holding <list> from list head <head> and deletes it.
1131 * This is made for use for pattern removal within an expression.
1132 */
Willy Tarreau38d41992020-11-03 14:50:29 +01001133static void pat_unlink_from_head(void **head, void **list)
Willy Tarreau867a8a52020-11-03 11:22:04 +01001134{
Willy Tarreau38d41992020-11-03 14:50:29 +01001135 while (*head) {
1136 if (*head == list) {
1137 *head = *list;
Willy Tarreau867a8a52020-11-03 11:22:04 +01001138 return;
1139 }
Willy Tarreau38d41992020-11-03 14:50:29 +01001140 head = *head;
Willy Tarreau867a8a52020-11-03 11:22:04 +01001141 }
1142}
1143
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001144void free_pattern_tree(struct eb_root *root)
1145{
1146 struct eb_node *node, *next;
Thierry FOURNIERe1bcac52013-12-13 16:09:50 +01001147 struct pattern_tree *elt;
Thierry FOURNIER3ce88c72013-12-09 11:29:46 +01001148
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001149 node = eb_first(root);
1150 while (node) {
1151 next = eb_next(node);
1152 eb_delete(node);
Thierry FOURNIERe1bcac52013-12-13 16:09:50 +01001153 elt = container_of(node, struct pattern_tree, node);
Willy Tarreau867a8a52020-11-03 11:22:04 +01001154 pat_unlink_from_head(&elt->ref->tree_head, &elt->from_ref);
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001155 free(elt->data);
Thierry FOURNIER3ce88c72013-12-09 11:29:46 +01001156 free(elt);
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001157 node = next;
1158 }
1159}
1160
Willy Tarreau6d8a6892020-11-02 19:26:02 +01001161void pat_prune_gen(struct pattern_expr *expr)
Thierry FOURNIERd163e1c2013-11-28 11:41:23 +01001162{
Thierry FOURNIER6f7203d2014-01-14 16:24:51 +01001163 struct pattern_list *pat, *tmp;
1164
1165 list_for_each_entry_safe(pat, tmp, &expr->patterns, list) {
Willy Tarreau2b718102021-04-21 07:32:39 +02001166 LIST_DELETE(&pat->list);
Willy Tarreau867a8a52020-11-03 11:22:04 +01001167 pat_unlink_from_head(&pat->pat.ref->list_head, &pat->from_ref);
Willy Tarreau6d8a6892020-11-02 19:26:02 +01001168 if (pat->pat.sflags & PAT_SF_REGFREE)
1169 regex_free(pat->pat.ptr.ptr);
1170 else
1171 free(pat->pat.ptr.ptr);
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001172 free(pat->pat.data);
Thierry FOURNIER6f7203d2014-01-14 16:24:51 +01001173 free(pat);
1174 }
1175
Thierry FOURNIERd163e1c2013-11-28 11:41:23 +01001176 free_pattern_tree(&expr->pattern_tree);
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001177 free_pattern_tree(&expr->pattern_tree_2);
Thierry FOURNIERd163e1c2013-11-28 11:41:23 +01001178 LIST_INIT(&expr->patterns);
Willy Tarreau3ee0de12020-11-02 15:26:51 +01001179 expr->ref->revision = rdtsc();
Thierry FOURNIERd163e1c2013-11-28 11:41:23 +01001180}
1181
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001182/*
1183 *
1184 * The following functions are used for the pattern indexation
1185 *
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001186 */
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001187
1188int pat_idx_list_val(struct pattern_expr *expr, struct pattern *pat, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001189{
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001190 struct pattern_list *patl;
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001191
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001192 /* allocate pattern */
1193 patl = calloc(1, sizeof(*patl));
1194 if (!patl) {
1195 memprintf(err, "out of memory while indexing pattern");
Thierry FOURNIER972028f2014-01-23 17:53:31 +01001196 return 0;
1197 }
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001198
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001199 /* duplicate pattern */
1200 memcpy(&patl->pat, pat, sizeof(*pat));
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001201
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001202 /* chain pattern in the expression */
Willy Tarreau2b718102021-04-21 07:32:39 +02001203 LIST_APPEND(&expr->patterns, &patl->list);
Willy Tarreau4bdd0a12020-11-02 12:10:48 +01001204 /* and from the reference */
Willy Tarreau38d41992020-11-03 14:50:29 +01001205 patl->from_ref = pat->ref->list_head;
1206 pat->ref->list_head = &patl->from_ref;
Willy Tarreau3ee0de12020-11-02 15:26:51 +01001207 expr->ref->revision = rdtsc();
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001208
1209 /* that's ok */
1210 return 1;
1211}
1212
1213int pat_idx_list_ptr(struct pattern_expr *expr, struct pattern *pat, char **err)
1214{
1215 struct pattern_list *patl;
1216
1217 /* allocate pattern */
1218 patl = calloc(1, sizeof(*patl));
Thierry FOURNIER8aa83842015-02-06 17:50:55 +01001219 if (!patl) {
1220 memprintf(err, "out of memory while indexing pattern");
Thierry FOURNIER972028f2014-01-23 17:53:31 +01001221 return 0;
Thierry FOURNIER8aa83842015-02-06 17:50:55 +01001222 }
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001223
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001224 /* duplicate pattern */
1225 memcpy(&patl->pat, pat, sizeof(*pat));
1226 patl->pat.ptr.ptr = malloc(patl->pat.len);
1227 if (!patl->pat.ptr.ptr) {
1228 free(patl);
1229 memprintf(err, "out of memory while indexing pattern");
1230 return 0;
1231 }
1232 memcpy(patl->pat.ptr.ptr, pat->ptr.ptr, pat->len);
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001233
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001234 /* chain pattern in the expression */
Willy Tarreau2b718102021-04-21 07:32:39 +02001235 LIST_APPEND(&expr->patterns, &patl->list);
Willy Tarreau4bdd0a12020-11-02 12:10:48 +01001236 /* and from the reference */
Willy Tarreau38d41992020-11-03 14:50:29 +01001237 patl->from_ref = pat->ref->list_head;
1238 pat->ref->list_head = &patl->from_ref;
Willy Tarreau3ee0de12020-11-02 15:26:51 +01001239 expr->ref->revision = rdtsc();
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001240
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001241 /* that's ok */
1242 return 1;
1243}
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001244
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001245int pat_idx_list_str(struct pattern_expr *expr, struct pattern *pat, char **err)
1246{
1247 struct pattern_list *patl;
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001248
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001249 /* allocate pattern */
1250 patl = calloc(1, sizeof(*patl));
1251 if (!patl) {
1252 memprintf(err, "out of memory while indexing pattern");
1253 return 0;
1254 }
1255
1256 /* duplicate pattern */
1257 memcpy(&patl->pat, pat, sizeof(*pat));
1258 patl->pat.ptr.str = malloc(patl->pat.len + 1);
1259 if (!patl->pat.ptr.str) {
1260 free(patl);
1261 memprintf(err, "out of memory while indexing pattern");
1262 return 0;
1263 }
1264 memcpy(patl->pat.ptr.ptr, pat->ptr.ptr, pat->len);
1265 patl->pat.ptr.str[patl->pat.len] = '\0';
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001266
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001267 /* chain pattern in the expression */
Willy Tarreau2b718102021-04-21 07:32:39 +02001268 LIST_APPEND(&expr->patterns, &patl->list);
Willy Tarreau4bdd0a12020-11-02 12:10:48 +01001269 /* and from the reference */
Willy Tarreau38d41992020-11-03 14:50:29 +01001270 patl->from_ref = pat->ref->list_head;
1271 pat->ref->list_head = &patl->from_ref;
Willy Tarreau3ee0de12020-11-02 15:26:51 +01001272 expr->ref->revision = rdtsc();
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001273
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001274 /* that's ok */
1275 return 1;
1276}
1277
Thierry Fournier8feaa662016-02-10 22:55:20 +01001278int pat_idx_list_reg_cap(struct pattern_expr *expr, struct pattern *pat, int cap, char **err)
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001279{
1280 struct pattern_list *patl;
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001281
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001282 /* allocate pattern */
1283 patl = calloc(1, sizeof(*patl));
1284 if (!patl) {
1285 memprintf(err, "out of memory while indexing pattern");
1286 return 0;
Thierry FOURNIER972028f2014-01-23 17:53:31 +01001287 }
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001288
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001289 /* duplicate pattern */
1290 memcpy(&patl->pat, pat, sizeof(*pat));
1291
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001292 /* compile regex */
Willy Tarreau9b5c8bb2020-11-02 19:16:23 +01001293 patl->pat.sflags |= PAT_SF_REGFREE;
Dragan Dosen26743032019-04-30 15:54:36 +02001294 if (!(patl->pat.ptr.reg = regex_comp(pat->ptr.str, !(expr->mflags & PAT_MF_IGNORE_CASE),
1295 cap, err))) {
Dirkjan Bussink07fcaaa2014-04-28 22:57:16 +00001296 free(patl);
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001297 return 0;
1298 }
1299
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001300 /* chain pattern in the expression */
Willy Tarreau2b718102021-04-21 07:32:39 +02001301 LIST_APPEND(&expr->patterns, &patl->list);
Willy Tarreau4bdd0a12020-11-02 12:10:48 +01001302 /* and from the reference */
Willy Tarreau38d41992020-11-03 14:50:29 +01001303 patl->from_ref = pat->ref->list_head;
1304 pat->ref->list_head = &patl->from_ref;
Willy Tarreau3ee0de12020-11-02 15:26:51 +01001305 expr->ref->revision = rdtsc();
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001306
1307 /* that's ok */
1308 return 1;
1309}
1310
Thierry Fournier8feaa662016-02-10 22:55:20 +01001311int pat_idx_list_reg(struct pattern_expr *expr, struct pattern *pat, char **err)
1312{
1313 return pat_idx_list_reg_cap(expr, pat, 0, err);
1314}
1315
1316int pat_idx_list_regm(struct pattern_expr *expr, struct pattern *pat, char **err)
1317{
1318 return pat_idx_list_reg_cap(expr, pat, 1, err);
1319}
1320
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001321int pat_idx_tree_ip(struct pattern_expr *expr, struct pattern *pat, char **err)
1322{
1323 unsigned int mask;
Thierry FOURNIERe1bcac52013-12-13 16:09:50 +01001324 struct pattern_tree *node;
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001325
1326 /* Only IPv4 can be indexed */
1327 if (pat->type == SMP_T_IPV4) {
Thierry FOURNIER972028f2014-01-23 17:53:31 +01001328 /* in IPv4 case, check if the mask is contiguous so that we can
1329 * insert the network into the tree. A continuous mask has only
1330 * ones on the left. This means that this mask + its lower bit
1331 * added once again is null.
1332 */
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001333 mask = ntohl(pat->val.ipv4.mask.s_addr);
1334 if (mask + (mask & -mask) == 0) {
1335 mask = mask ? 33 - flsnz(mask & -mask) : 0; /* equals cidr value */
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001336
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001337 /* node memory allocation */
1338 node = calloc(1, sizeof(*node) + 4);
1339 if (!node) {
1340 memprintf(err, "out of memory while loading pattern");
1341 return 0;
1342 }
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001343
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001344 /* copy the pointer to sample associated to this node */
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001345 node->data = pat->data;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +01001346 node->ref = pat->ref;
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001347
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001348 /* FIXME: insert <addr>/<mask> into the tree here */
1349 memcpy(node->node.key, &pat->val.ipv4.addr, 4); /* network byte order */
1350 node->node.node.pfx = mask;
Thierry FOURNIER31db4ae2014-01-30 00:27:15 +01001351
1352 /* Insert the entry. */
1353 ebmb_insert_prefix(&expr->pattern_tree, &node->node, 4);
Willy Tarreau38d41992020-11-03 14:50:29 +01001354 node->from_ref = pat->ref->tree_head;
1355 pat->ref->tree_head = &node->from_ref;
Willy Tarreau3ee0de12020-11-02 15:26:51 +01001356 expr->ref->revision = rdtsc();
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001357
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001358 /* that's ok */
1359 return 1;
1360 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001361 else {
1362 /* If the mask is not contiguous, just add the pattern to the list */
1363 return pat_idx_list_val(expr, pat, err);
1364 }
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001365 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001366 else if (pat->type == SMP_T_IPV6) {
1367 /* IPv6 also can be indexed */
1368 node = calloc(1, sizeof(*node) + 16);
1369 if (!node) {
1370 memprintf(err, "out of memory while loading pattern");
1371 return 0;
1372 }
1373
1374 /* copy the pointer to sample associated to this node */
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001375 node->data = pat->data;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +01001376 node->ref = pat->ref;
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001377
1378 /* FIXME: insert <addr>/<mask> into the tree here */
1379 memcpy(node->node.key, &pat->val.ipv6.addr, 16); /* network byte order */
1380 node->node.node.pfx = pat->val.ipv6.mask;
Thierry FOURNIER31db4ae2014-01-30 00:27:15 +01001381
1382 /* Insert the entry. */
1383 ebmb_insert_prefix(&expr->pattern_tree_2, &node->node, 16);
Willy Tarreau38d41992020-11-03 14:50:29 +01001384 node->from_ref = pat->ref->tree_head;
1385 pat->ref->tree_head = &node->from_ref;
Willy Tarreau3ee0de12020-11-02 15:26:51 +01001386 expr->ref->revision = rdtsc();
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001387
1388 /* that's ok */
1389 return 1;
1390 }
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001391
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001392 return 0;
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001393}
1394
1395int pat_idx_tree_str(struct pattern_expr *expr, struct pattern *pat, char **err)
1396{
1397 int len;
Thierry FOURNIERe1bcac52013-12-13 16:09:50 +01001398 struct pattern_tree *node;
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001399
1400 /* Only string can be indexed */
Thierry FOURNIER7654c9f2013-12-17 00:20:33 +01001401 if (pat->type != SMP_T_STR) {
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001402 memprintf(err, "internal error: string expected, but the type is '%s'",
1403 smp_to_type[pat->type]);
1404 return 0;
Thierry FOURNIER972028f2014-01-23 17:53:31 +01001405 }
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001406
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001407 /* If the flag PAT_F_IGNORE_CASE is set, we cannot use trees */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02001408 if (expr->mflags & PAT_MF_IGNORE_CASE)
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001409 return pat_idx_list_str(expr, pat, err);
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001410
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001411 /* Process the key len */
1412 len = strlen(pat->ptr.str) + 1;
1413
1414 /* node memory allocation */
1415 node = calloc(1, sizeof(*node) + len);
1416 if (!node) {
1417 memprintf(err, "out of memory while loading pattern");
1418 return 0;
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001419 }
1420
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001421 /* copy the pointer to sample associated to this node */
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001422 node->data = pat->data;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +01001423 node->ref = pat->ref;
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001424
1425 /* copy the string */
1426 memcpy(node->node.key, pat->ptr.str, len);
1427
1428 /* index the new node */
Thierry FOURNIER31db4ae2014-01-30 00:27:15 +01001429 ebst_insert(&expr->pattern_tree, &node->node);
Willy Tarreau38d41992020-11-03 14:50:29 +01001430 node->from_ref = pat->ref->tree_head;
1431 pat->ref->tree_head = &node->from_ref;
Willy Tarreau3ee0de12020-11-02 15:26:51 +01001432 expr->ref->revision = rdtsc();
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001433
1434 /* that's ok */
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001435 return 1;
1436}
1437
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +02001438int pat_idx_tree_pfx(struct pattern_expr *expr, struct pattern *pat, char **err)
1439{
1440 int len;
1441 struct pattern_tree *node;
1442
1443 /* Only string can be indexed */
1444 if (pat->type != SMP_T_STR) {
1445 memprintf(err, "internal error: string expected, but the type is '%s'",
1446 smp_to_type[pat->type]);
1447 return 0;
1448 }
1449
1450 /* If the flag PAT_F_IGNORE_CASE is set, we cannot use trees */
1451 if (expr->mflags & PAT_MF_IGNORE_CASE)
1452 return pat_idx_list_str(expr, pat, err);
1453
1454 /* Process the key len */
1455 len = strlen(pat->ptr.str);
1456
1457 /* node memory allocation */
1458 node = calloc(1, sizeof(*node) + len + 1);
1459 if (!node) {
1460 memprintf(err, "out of memory while loading pattern");
1461 return 0;
1462 }
1463
1464 /* copy the pointer to sample associated to this node */
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001465 node->data = pat->data;
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +02001466 node->ref = pat->ref;
1467
1468 /* copy the string and the trailing zero */
1469 memcpy(node->node.key, pat->ptr.str, len + 1);
1470 node->node.node.pfx = len * 8;
1471
1472 /* index the new node */
1473 ebmb_insert_prefix(&expr->pattern_tree, &node->node, len);
Willy Tarreau38d41992020-11-03 14:50:29 +01001474 node->from_ref = pat->ref->tree_head;
1475 pat->ref->tree_head = &node->from_ref;
Willy Tarreau3ee0de12020-11-02 15:26:51 +01001476 expr->ref->revision = rdtsc();
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +02001477
1478 /* that's ok */
1479 return 1;
1480}
1481
Willy Tarreauf1c08922020-11-02 19:53:16 +01001482/* Deletes all patterns from reference <elt>. Note that all of their
Willy Tarreau78777ea2020-11-02 13:55:22 +01001483 * expressions must be locked, and the pattern lock must be held as well.
1484 */
Willy Tarreauf1c08922020-11-02 19:53:16 +01001485void pat_delete_gen(struct pat_ref *ref, struct pat_ref_elt *elt)
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001486{
Willy Tarreau38d41992020-11-03 14:50:29 +01001487 struct pattern_tree *tree;
1488 struct pattern_list *pat;
1489 void **node;
Willy Tarreauf1c08922020-11-02 19:53:16 +01001490
1491 /* delete all known tree nodes. They are all allocated inline */
Willy Tarreau38d41992020-11-03 14:50:29 +01001492 for (node = elt->tree_head; node;) {
1493 tree = container_of(node, struct pattern_tree, from_ref);
1494 node = *node;
Willy Tarreauf1c08922020-11-02 19:53:16 +01001495 BUG_ON(tree->ref != elt);
1496
1497 ebmb_delete(&tree->node);
Willy Tarreauf1c08922020-11-02 19:53:16 +01001498 free(tree->data);
1499 free(tree);
1500 }
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001501
Willy Tarreauf1c08922020-11-02 19:53:16 +01001502 /* delete all list nodes and free their pattern entries (str/reg) */
Willy Tarreau38d41992020-11-03 14:50:29 +01001503 for (node = elt->list_head; node;) {
1504 pat = container_of(node, struct pattern_list, from_ref);
1505 node = *node;
Willy Tarreau78777ea2020-11-02 13:55:22 +01001506 BUG_ON(pat->pat.ref != elt);
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001507
1508 /* Delete and free entry. */
Willy Tarreau2b718102021-04-21 07:32:39 +02001509 LIST_DELETE(&pat->list);
Willy Tarreau6d8a6892020-11-02 19:26:02 +01001510 if (pat->pat.sflags & PAT_SF_REGFREE)
1511 regex_free(pat->pat.ptr.reg);
1512 else
1513 free(pat->pat.ptr.ptr);
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001514 free(pat->pat.data);
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001515 free(pat);
1516 }
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001517
Willy Tarreauf1c08922020-11-02 19:53:16 +01001518 /* update revision number to refresh the cache */
1519 ref->revision = rdtsc();
Willy Tarreau38d41992020-11-03 14:50:29 +01001520 elt->tree_head = NULL;
1521 elt->list_head = NULL;
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001522}
1523
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001524void pattern_init_expr(struct pattern_expr *expr)
1525{
1526 LIST_INIT(&expr->patterns);
Thierry FOURNIER31db4ae2014-01-30 00:27:15 +01001527 expr->pattern_tree = EB_ROOT;
1528 expr->pattern_tree_2 = EB_ROOT;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001529}
1530
1531void pattern_init_head(struct pattern_head *head)
1532{
1533 LIST_INIT(&head->head);
1534}
1535
1536/* The following functions are relative to the management of the reference
1537 * lists. These lists are used to store the original pattern and associated
1538 * value as string form.
1539 *
1540 * This is used with modifiable ACL and MAPS
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001541 *
1542 * The pattern reference are stored with two identifiers: the unique_id and
1543 * the reference.
1544 *
1545 * The reference identify a file. Each file with the same name point to the
1546 * same reference. We can register many times one file. If the file is modified,
1547 * all his dependencies are also modified. The reference can be used with map or
1548 * acl.
1549 *
1550 * The unique_id identify inline acl. The unique id is unique for each acl.
1551 * You cannot force the same id in the configuration file, because this repoort
1552 * an error.
1553 *
1554 * A particular case appears if the filename is a number. In this case, the
1555 * unique_id is set with the number represented by the filename and the
1556 * reference is also set. This method prevent double unique_id.
1557 *
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001558 */
1559
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01001560/* This function looks up a reference by name. If the reference is found, a
1561 * pointer to the struct pat_ref is returned, otherwise NULL is returned.
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001562 */
1563struct pat_ref *pat_ref_lookup(const char *reference)
1564{
1565 struct pat_ref *ref;
1566
1567 list_for_each_entry(ref, &pattern_reference, list)
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001568 if (ref->reference && strcmp(reference, ref->reference) == 0)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001569 return ref;
1570 return NULL;
1571}
1572
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01001573/* This function looks up a reference's unique id. If the reference is found, a
1574 * pointer to the struct pat_ref is returned, otherwise NULL is returned.
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001575 */
1576struct pat_ref *pat_ref_lookupid(int unique_id)
1577{
1578 struct pat_ref *ref;
1579
1580 list_for_each_entry(ref, &pattern_reference, list)
1581 if (ref->unique_id == unique_id)
1582 return ref;
1583 return NULL;
1584}
1585
Willy Tarreau1fd52f72020-11-02 17:30:17 +01001586/* This function removes from the pattern reference <ref> all the patterns
1587 * attached to the reference element <elt>, and the element itself. The
1588 * reference must be locked.
1589 */
1590void pat_ref_delete_by_ptr(struct pat_ref *ref, struct pat_ref_elt *elt)
1591{
1592 struct pattern_expr *expr;
1593 struct bref *bref, *back;
1594
1595 /*
1596 * we have to unlink all watchers from this reference pattern. We must
1597 * not relink them if this elt was the last one in the list.
1598 */
1599 list_for_each_entry_safe(bref, back, &elt->back_refs, users) {
Willy Tarreau2b718102021-04-21 07:32:39 +02001600 LIST_DELETE(&bref->users);
Willy Tarreau1fd52f72020-11-02 17:30:17 +01001601 LIST_INIT(&bref->users);
1602 if (elt->list.n != &ref->head)
Willy Tarreau2b718102021-04-21 07:32:39 +02001603 LIST_APPEND(&LIST_ELEM(elt->list.n, typeof(elt), list)->back_refs, &bref->users);
Willy Tarreau1fd52f72020-11-02 17:30:17 +01001604 bref->ref = elt->list.n;
1605 }
1606
1607 /* delete all entries from all expressions for this pattern */
1608 list_for_each_entry(expr, &ref->pat, list)
1609 HA_RWLOCK_WRLOCK(PATEXP_LOCK, &expr->lock);
1610
1611 pat_delete_gen(ref, elt);
1612
1613 list_for_each_entry(expr, &ref->pat, list)
1614 HA_RWLOCK_WRUNLOCK(PATEXP_LOCK, &expr->lock);
1615
Willy Tarreau2b718102021-04-21 07:32:39 +02001616 LIST_DELETE(&elt->list);
Willy Tarreau1fd52f72020-11-02 17:30:17 +01001617 free(elt->sample);
1618 free(elt->pattern);
1619 free(elt);
1620}
1621
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01001622/* This function removes all the patterns matching the pointer <refelt> from
1623 * the reference and from each expr member of this reference. This function
1624 * returns 1 if the entry was found and deleted, otherwise zero.
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001625 */
1626int pat_ref_delete_by_id(struct pat_ref *ref, struct pat_ref_elt *refelt)
1627{
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001628 struct pat_ref_elt *elt, *safe;
1629
1630 /* delete pattern from reference */
1631 list_for_each_entry_safe(elt, safe, &ref->head, list) {
1632 if (elt == refelt) {
Willy Tarreau1fd52f72020-11-02 17:30:17 +01001633 pat_ref_delete_by_ptr(ref, elt);
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001634 return 1;
1635 }
1636 }
1637 return 0;
1638}
1639
Willy Tarreau1fd52f72020-11-02 17:30:17 +01001640/* This function removes all patterns matching <key> from the reference
Joseph Herlant4189d672018-11-15 10:22:31 -08001641 * and from each expr member of the reference. This function returns 1
Willy Tarreau1fd52f72020-11-02 17:30:17 +01001642 * if the deletion is done and returns 0 is the entry is not found.
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001643 */
1644int pat_ref_delete(struct pat_ref *ref, const char *key)
1645{
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001646 struct pat_ref_elt *elt, *safe;
1647 int found = 0;
1648
1649 /* delete pattern from reference */
1650 list_for_each_entry_safe(elt, safe, &ref->head, list) {
1651 if (strcmp(key, elt->pattern) == 0) {
Willy Tarreau1fd52f72020-11-02 17:30:17 +01001652 pat_ref_delete_by_ptr(ref, elt);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001653 found = 1;
1654 }
1655 }
1656
Willy Tarreau1fd52f72020-11-02 17:30:17 +01001657 return found;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001658}
1659
Baptiste Assmann953f74d2014-04-25 16:57:03 +02001660/*
1661 * find and return an element <elt> matching <key> in a reference <ref>
1662 * return NULL if not found
1663 */
1664struct pat_ref_elt *pat_ref_find_elt(struct pat_ref *ref, const char *key)
1665{
1666 struct pat_ref_elt *elt;
1667
1668 list_for_each_entry(elt, &ref->head, list) {
1669 if (strcmp(key, elt->pattern) == 0)
1670 return elt;
1671 }
1672
1673 return NULL;
1674}
1675
1676
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01001677/* This function modifies the sample of pat_ref_elt <elt> in all expressions
1678 * found under <ref> to become <value>. It is assumed that the caller has
1679 * already verified that <elt> belongs to <ref>.
1680 */
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001681static inline int pat_ref_set_elt(struct pat_ref *ref, struct pat_ref_elt *elt,
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001682 const char *value, char **err)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001683{
1684 struct pattern_expr *expr;
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001685 struct sample_data **data;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001686 char *sample;
Thierry FOURNIER12ba0c22015-08-14 00:02:11 +02001687 struct sample_data test;
Thierry FOURNIER149e0fe2014-01-29 19:35:06 +01001688
1689 /* Try all needed converters. */
1690 list_for_each_entry(expr, &ref->pat, list) {
1691 if (!expr->pat_head->parse_smp)
1692 continue;
1693
1694 if (!expr->pat_head->parse_smp(value, &test)) {
1695 memprintf(err, "unable to parse '%s'", value);
1696 return 0;
1697 }
1698 }
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001699
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001700 /* Modify pattern from reference. */
1701 sample = strdup(value);
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001702 if (!sample) {
1703 memprintf(err, "out of memory error");
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001704 return 0;
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001705 }
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01001706 /* Load sample in each reference. All the conversions are tested
1707 * below, normally these calls don't fail.
Thierry FOURNIER149e0fe2014-01-29 19:35:06 +01001708 */
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01001709 list_for_each_entry(expr, &ref->pat, list) {
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001710 if (!expr->pat_head->parse_smp)
1711 continue;
1712
Christopher Faulet2a944ee2017-11-07 10:42:54 +01001713 HA_RWLOCK_WRLOCK(PATEXP_LOCK, &expr->lock);
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001714 data = pattern_find_smp(expr, elt);
1715 if (data && *data && !expr->pat_head->parse_smp(sample, *data))
1716 *data = NULL;
Christopher Faulet2a944ee2017-11-07 10:42:54 +01001717 HA_RWLOCK_WRUNLOCK(PATEXP_LOCK, &expr->lock);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001718 }
1719
Emeric Brunb5997f72017-07-03 11:34:05 +02001720 /* free old sample only when all exprs are updated */
1721 free(elt->sample);
1722 elt->sample = sample;
1723
1724
Thierry FOURNIER149e0fe2014-01-29 19:35:06 +01001725 return 1;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001726}
1727
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01001728/* This function modifies the sample of pat_ref_elt <refelt> in all expressions
1729 * found under <ref> to become <value>, after checking that <refelt> really
1730 * belongs to <ref>.
1731 */
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001732int pat_ref_set_by_id(struct pat_ref *ref, struct pat_ref_elt *refelt, const char *value, char **err)
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001733{
1734 struct pat_ref_elt *elt;
1735
1736 /* Look for pattern in the reference. */
1737 list_for_each_entry(elt, &ref->head, list) {
1738 if (elt == refelt) {
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001739 if (!pat_ref_set_elt(ref, elt, value, err))
1740 return 0;
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001741 return 1;
1742 }
1743 }
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001744
1745 memprintf(err, "key or pattern not found");
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001746 return 0;
1747}
1748
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01001749/* This function modifies to <value> the sample of all patterns matching <key>
1750 * under <ref>.
1751 */
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001752int pat_ref_set(struct pat_ref *ref, const char *key, const char *value, char **err)
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001753{
1754 struct pat_ref_elt *elt;
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001755 int found = 0;
1756 char *_merr;
1757 char **merr;
1758
1759 if (err) {
1760 merr = &_merr;
1761 *merr = NULL;
1762 }
1763 else
1764 merr = NULL;
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001765
1766 /* Look for pattern in the reference. */
1767 list_for_each_entry(elt, &ref->head, list) {
1768 if (strcmp(key, elt->pattern) == 0) {
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001769 if (!pat_ref_set_elt(ref, elt, value, merr)) {
William Lallemand579fb252018-06-11 10:53:46 +02001770 if (err && merr) {
1771 if (!found) {
1772 *err = *merr;
1773 } else {
1774 memprintf(err, "%s, %s", *err, *merr);
Willy Tarreau61cfdf42021-02-20 10:46:51 +01001775 ha_free(merr);
William Lallemand579fb252018-06-11 10:53:46 +02001776 }
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001777 }
1778 }
1779 found = 1;
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001780 }
1781 }
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001782
1783 if (!found) {
1784 memprintf(err, "entry not found");
1785 return 0;
1786 }
1787 return 1;
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001788}
1789
Joseph Herlant4189d672018-11-15 10:22:31 -08001790/* This function creates a new reference. <ref> is the reference name.
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001791 * <flags> are PAT_REF_*. /!\ The reference is not checked, and must
1792 * be unique. The user must check the reference with "pat_ref_lookup()"
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01001793 * before calling this function. If the function fails, it returns NULL,
1794 * otherwise it returns the new struct pat_ref.
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001795 */
Thierry FOURNIER0d6ba512014-02-11 03:31:34 +01001796struct pat_ref *pat_ref_new(const char *reference, const char *display, unsigned int flags)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001797{
1798 struct pat_ref *ref;
1799
Willy Tarreau8135d9b2020-10-30 15:35:11 +01001800 ref = calloc(1, sizeof(*ref));
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001801 if (!ref)
1802 return NULL;
1803
Thierry FOURNIER0d6ba512014-02-11 03:31:34 +01001804 if (display) {
1805 ref->display = strdup(display);
1806 if (!ref->display) {
1807 free(ref);
1808 return NULL;
1809 }
1810 }
Thierry FOURNIER0d6ba512014-02-11 03:31:34 +01001811
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001812 ref->reference = strdup(reference);
1813 if (!ref->reference) {
Thierry FOURNIER0d6ba512014-02-11 03:31:34 +01001814 free(ref->display);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001815 free(ref);
1816 return NULL;
1817 }
1818
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001819 ref->flags = flags;
1820 ref->unique_id = -1;
Willy Tarreau3ee0de12020-11-02 15:26:51 +01001821 ref->revision = 0;
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001822
1823 LIST_INIT(&ref->head);
1824 LIST_INIT(&ref->pat);
Christopher Faulet2a944ee2017-11-07 10:42:54 +01001825 HA_SPIN_INIT(&ref->lock);
Willy Tarreau2b718102021-04-21 07:32:39 +02001826 LIST_APPEND(&pattern_reference, &ref->list);
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001827
1828 return ref;
1829}
1830
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01001831/* This function creates a new reference. <unique_id> is the unique id. If
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001832 * the value of <unique_id> is -1, the unique id is calculated later.
1833 * <flags> are PAT_REF_*. /!\ The reference is not checked, and must
1834 * be unique. The user must check the reference with "pat_ref_lookup()"
1835 * or pat_ref_lookupid before calling this function. If the function
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01001836 * fails, it returns NULL, otherwise it returns the new struct pat_ref.
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001837 */
Thierry FOURNIER0d6ba512014-02-11 03:31:34 +01001838struct pat_ref *pat_ref_newid(int unique_id, const char *display, unsigned int flags)
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001839{
1840 struct pat_ref *ref;
1841
Willy Tarreau8135d9b2020-10-30 15:35:11 +01001842 ref = calloc(1, sizeof(*ref));
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001843 if (!ref)
1844 return NULL;
1845
Thierry FOURNIER0d6ba512014-02-11 03:31:34 +01001846 if (display) {
1847 ref->display = strdup(display);
1848 if (!ref->display) {
1849 free(ref);
1850 return NULL;
1851 }
1852 }
Thierry FOURNIER0d6ba512014-02-11 03:31:34 +01001853
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001854 ref->reference = NULL;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001855 ref->flags = flags;
Willy Tarreau29947742020-10-28 11:43:49 +01001856 ref->curr_gen = 0;
1857 ref->next_gen = 0;
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001858 ref->unique_id = unique_id;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001859 LIST_INIT(&ref->head);
1860 LIST_INIT(&ref->pat);
Aurélien Nephtali564d15a2018-04-19 16:56:07 +02001861 HA_SPIN_INIT(&ref->lock);
Willy Tarreau2b718102021-04-21 07:32:39 +02001862 LIST_APPEND(&pattern_reference, &ref->list);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001863
1864 return ref;
1865}
1866
Willy Tarreauf4edb722020-10-28 10:52:46 +01001867/* This function adds entry to <ref>. It can fail on memory error. It returns
1868 * the newly added element on success, or NULL on failure. The PATREF_LOCK on
Willy Tarreau29947742020-10-28 11:43:49 +01001869 * <ref> must be held. It sets the newly created pattern's generation number
1870 * to the same value as the reference's.
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001871 */
Willy Tarreauf4edb722020-10-28 10:52:46 +01001872struct pat_ref_elt *pat_ref_append(struct pat_ref *ref, const char *pattern, const char *sample, int line)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001873{
1874 struct pat_ref_elt *elt;
1875
Willy Tarreau8135d9b2020-10-30 15:35:11 +01001876 elt = calloc(1, sizeof(*elt));
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001877 if (!elt)
Willy Tarreauf4edb722020-10-28 10:52:46 +01001878 goto fail;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001879
Willy Tarreau29947742020-10-28 11:43:49 +01001880 elt->gen_id = ref->curr_gen;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001881 elt->line = line;
1882
1883 elt->pattern = strdup(pattern);
Willy Tarreauf4edb722020-10-28 10:52:46 +01001884 if (!elt->pattern)
1885 goto fail;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001886
1887 if (sample) {
1888 elt->sample = strdup(sample);
Willy Tarreauf4edb722020-10-28 10:52:46 +01001889 if (!elt->sample)
1890 goto fail;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001891 }
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001892
Emeric Brun8d85aa42017-06-29 15:40:33 +02001893 LIST_INIT(&elt->back_refs);
Willy Tarreau38d41992020-11-03 14:50:29 +01001894 elt->list_head = NULL;
1895 elt->tree_head = NULL;
Willy Tarreau2b718102021-04-21 07:32:39 +02001896 LIST_APPEND(&ref->head, &elt->list);
Willy Tarreauf4edb722020-10-28 10:52:46 +01001897 return elt;
1898 fail:
1899 if (elt)
1900 free(elt->pattern);
1901 free(elt);
1902 return NULL;
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001903}
1904
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01001905/* This function creates sample found in <elt>, parses the pattern also
1906 * found in <elt> and inserts it in <expr>. The function copies <patflags>
1907 * into <expr>. If the function fails, it returns 0 and <err> is filled.
Ilya Shipitsin47d17182020-06-21 21:42:57 +05001908 * In success case, the function returns 1.
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001909 */
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001910int pat_ref_push(struct pat_ref_elt *elt, struct pattern_expr *expr,
1911 int patflags, char **err)
1912{
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001913 struct sample_data *data;
Thierry FOURNIERd25c8422014-01-28 15:34:35 +01001914 struct pattern pattern;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001915
1916 /* Create sample */
1917 if (elt->sample && expr->pat_head->parse_smp) {
1918 /* New sample. */
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001919 data = malloc(sizeof(*data));
1920 if (!data)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001921 return 0;
1922
1923 /* Parse value. */
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001924 if (!expr->pat_head->parse_smp(elt->sample, data)) {
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001925 memprintf(err, "unable to parse '%s'", elt->sample);
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001926 free(data);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001927 return 0;
1928 }
1929
1930 }
1931 else
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001932 data = NULL;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001933
Thierry FOURNIERd25c8422014-01-28 15:34:35 +01001934 /* initialise pattern */
1935 memset(&pattern, 0, sizeof(pattern));
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001936 pattern.data = data;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +01001937 pattern.ref = elt;
Thierry FOURNIERd25c8422014-01-28 15:34:35 +01001938
1939 /* parse pattern */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02001940 if (!expr->pat_head->parse(elt->pattern, &pattern, expr->mflags, err)) {
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001941 free(data);
Thierry FOURNIERd25c8422014-01-28 15:34:35 +01001942 return 0;
1943 }
1944
Christopher Faulet2a944ee2017-11-07 10:42:54 +01001945 HA_RWLOCK_WRLOCK(PATEXP_LOCK, &expr->lock);
Thierry FOURNIERd25c8422014-01-28 15:34:35 +01001946 /* index pattern */
1947 if (!expr->pat_head->index(expr, &pattern, err)) {
Christopher Faulet2a944ee2017-11-07 10:42:54 +01001948 HA_RWLOCK_WRUNLOCK(PATEXP_LOCK, &expr->lock);
Thierry FOURNIER503bb092015-08-19 08:35:43 +02001949 free(data);
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001950 return 0;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001951 }
Christopher Faulet2a944ee2017-11-07 10:42:54 +01001952 HA_RWLOCK_WRUNLOCK(PATEXP_LOCK, &expr->lock);
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001953
1954 return 1;
1955}
1956
Willy Tarreau0439e5e2020-10-28 18:45:45 +01001957/* This function tries to commit entry <elt> into <ref>. The new entry must
1958 * have already been inserted using pat_ref_append(), and its generation number
1959 * may have been adjusted as it will not be changed. <err> must point to a NULL
1960 * pointer. The PATREF lock on <ref> must be held. All the pattern_expr for
1961 * this reference will be updated (parsing, indexing). On success, non-zero is
1962 * returned. On failure, all the operation is rolled back (the element is
1963 * deleted from all expressions and is freed), zero is returned and the error
1964 * pointer <err> may have been updated (and the caller must free it). Failure
1965 * causes include memory allocation, parsing error or indexing error.
1966 */
Willy Tarreaudc2410d2021-01-15 14:11:59 +01001967int pat_ref_commit_elt(struct pat_ref *ref, struct pat_ref_elt *elt, char **err)
Willy Tarreau0439e5e2020-10-28 18:45:45 +01001968{
1969 struct pattern_expr *expr;
1970
1971 list_for_each_entry(expr, &ref->pat, list) {
1972 if (!pat_ref_push(elt, expr, 0, err)) {
1973 pat_ref_delete_by_ptr(ref, elt);
1974 return 0;
1975 }
1976 }
1977 return 1;
1978}
1979
Willy Tarreau1a6857b2020-10-29 09:21:43 +01001980/* Loads <pattern>:<sample> into <ref> for generation <gen>. <sample> may be
1981 * NULL if none exists (e.g. ACL). If not needed, the generation number should
1982 * be set to ref->curr_gen. The error pointer must initially point to NULL. The
1983 * new entry will be propagated to all use places, involving allocation, parsing
1984 * and indexing. On error (parsing, allocation), the operation will be rolled
1985 * back, an error may be reported, and NULL will be reported. On success, the
1986 * freshly allocated element will be returned. The PATREF lock on <ref> must be
1987 * held during the operation.
1988 */
1989struct pat_ref_elt *pat_ref_load(struct pat_ref *ref, unsigned int gen,
1990 const char *pattern, const char *sample,
1991 int line, char **err)
1992{
1993 struct pat_ref_elt *elt;
1994
1995 elt = pat_ref_append(ref, pattern, sample, line);
1996 if (elt) {
1997 elt->gen_id = gen;
Willy Tarreaudc2410d2021-01-15 14:11:59 +01001998 if (!pat_ref_commit_elt(ref, elt, err))
Willy Tarreau1a6857b2020-10-29 09:21:43 +01001999 elt = NULL;
2000 } else
2001 memprintf(err, "out of memory error");
2002
2003 return elt;
2004}
2005
Willy Tarreau6a174072020-10-28 10:58:05 +01002006/* This function adds entry to <ref>. It can fail on memory error. The new
Thierry FOURNIER31db4ae2014-01-30 00:27:15 +01002007 * entry is added at all the pattern_expr registered in this reference. The
Willy Tarreau6a174072020-10-28 10:58:05 +01002008 * function stops on the first error encountered. It returns 0 and <err> is
Thierry FOURNIER31db4ae2014-01-30 00:27:15 +01002009 * filled. If an error is encountered, the complete add operation is cancelled.
2010 * If the insertion is a success the function returns 1.
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002011 */
2012int pat_ref_add(struct pat_ref *ref,
2013 const char *pattern, const char *sample,
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02002014 char **err)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002015{
Willy Tarreau1a6857b2020-10-29 09:21:43 +01002016 return !!pat_ref_load(ref, ref->curr_gen, pattern, sample, -1, err);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002017}
2018
Willy Tarreau94b9abe2020-10-28 18:23:49 +01002019/* This function purges all elements from <ref> that are older than generation
2020 * <oldest>. It will not purge more than <budget> entries at once, in order to
2021 * remain responsive. If budget is negative, no limit is applied.
2022 * The caller must already hold the PATREF_LOCK on <ref>. The function will
2023 * take the PATEXP_LOCK on all expressions of the pattern as needed. It returns
2024 * non-zero on completion, or zero if it had to stop before the end after
2025 * <budget> was depleted.
2026 */
2027int pat_ref_purge_older(struct pat_ref *ref, unsigned int oldest, int budget)
2028{
2029 struct pat_ref_elt *elt, *elt_bck;
2030 struct bref *bref, *bref_bck;
2031 struct pattern_expr *expr;
2032 int done;
2033
2034 list_for_each_entry(expr, &ref->pat, list)
2035 HA_RWLOCK_WRLOCK(PATEXP_LOCK, &expr->lock);
2036
2037 /* all expr are locked, we can safely remove all pat_ref */
2038
2039 /* assume completion for e.g. empty lists */
2040 done = 1;
2041 list_for_each_entry_safe(elt, elt_bck, &ref->head, list) {
2042 if ((int)(elt->gen_id - oldest) >= 0)
2043 continue;
2044
2045 if (budget >= 0 && !budget--) {
2046 done = 0;
2047 break;
2048 }
2049
2050 /*
2051 * we have to unlink all watchers from this reference pattern. We must
2052 * not relink them if this elt was the last one in the list.
2053 */
2054 list_for_each_entry_safe(bref, bref_bck, &elt->back_refs, users) {
Willy Tarreau2b718102021-04-21 07:32:39 +02002055 LIST_DELETE(&bref->users);
Willy Tarreau94b9abe2020-10-28 18:23:49 +01002056 LIST_INIT(&bref->users);
2057 if (elt->list.n != &ref->head)
Willy Tarreau2b718102021-04-21 07:32:39 +02002058 LIST_APPEND(&LIST_ELEM(elt->list.n, typeof(elt), list)->back_refs, &bref->users);
Willy Tarreau94b9abe2020-10-28 18:23:49 +01002059 bref->ref = elt->list.n;
2060 }
2061
2062 /* delete the storage for all representations of this pattern. */
2063 pat_delete_gen(ref, elt);
2064
Willy Tarreau2b718102021-04-21 07:32:39 +02002065 LIST_DELETE(&elt->list);
Willy Tarreau94b9abe2020-10-28 18:23:49 +01002066 free(elt->pattern);
2067 free(elt->sample);
2068 free(elt);
2069 }
2070
2071 list_for_each_entry(expr, &ref->pat, list)
2072 HA_RWLOCK_WRUNLOCK(PATEXP_LOCK, &expr->lock);
2073
2074#if defined(HA_HAVE_MALLOC_TRIM)
2075 if (done) {
2076 malloc_trim(0);
2077 }
2078#endif
2079
2080 return done;
2081}
2082
Joseph Herlant4189d672018-11-15 10:22:31 -08002083/* This function prunes <ref>, replaces all references by the references
2084 * of <replace>, and reindexes all the news values.
Thierry FOURNIER46006bd2014-03-21 21:45:15 +01002085 *
Joseph Herlant4189d672018-11-15 10:22:31 -08002086 * The patterns are loaded in best effort and the errors are ignored,
2087 * but written in the logs.
Thierry FOURNIER46006bd2014-03-21 21:45:15 +01002088 */
2089void pat_ref_reload(struct pat_ref *ref, struct pat_ref *replace)
2090{
2091 struct pattern_expr *expr;
Emeric Brunb5997f72017-07-03 11:34:05 +02002092 struct pat_ref_elt *elt, *safe;
2093 struct bref *bref, *back;
Emeric Brunb5997f72017-07-03 11:34:05 +02002094 struct pattern pattern;
Thierry FOURNIER46006bd2014-03-21 21:45:15 +01002095
Thierry FOURNIER46006bd2014-03-21 21:45:15 +01002096
Christopher Faulet2a944ee2017-11-07 10:42:54 +01002097 HA_SPIN_LOCK(PATREF_LOCK, &ref->lock);
Emeric Brunb5997f72017-07-03 11:34:05 +02002098 list_for_each_entry(expr, &ref->pat, list) {
Christopher Faulet2a944ee2017-11-07 10:42:54 +01002099 HA_RWLOCK_WRLOCK(PATEXP_LOCK, &expr->lock);
Emeric Brunb5997f72017-07-03 11:34:05 +02002100 }
2101
2102 /* all expr are locked, we can safely remove all pat_ref */
2103 list_for_each_entry_safe(elt, safe, &ref->head, list) {
2104 list_for_each_entry_safe(bref, back, &elt->back_refs, users) {
Willy Tarreaud4164dc2020-10-27 18:55:20 +01002105 /* we have to unlink all watchers. */
2106 LIST_DEL_INIT(&bref->users);
2107 bref->ref = NULL;
Emeric Brunb5997f72017-07-03 11:34:05 +02002108 }
Willy Tarreau28174722020-11-03 13:36:58 +01002109 pat_delete_gen(ref, elt);
Willy Tarreau2b718102021-04-21 07:32:39 +02002110 LIST_DELETE(&elt->list);
Emeric Brunb5997f72017-07-03 11:34:05 +02002111 free(elt->pattern);
2112 free(elt->sample);
2113 free(elt);
2114 }
2115
2116 /* switch pat_ret_elt lists */
Willy Tarreau2b718102021-04-21 07:32:39 +02002117 LIST_INSERT(&replace->head, &ref->head);
2118 LIST_DELETE(&replace->head);
Thierry FOURNIER46006bd2014-03-21 21:45:15 +01002119
Emeric Brunb5997f72017-07-03 11:34:05 +02002120 list_for_each_entry(expr, &ref->pat, list) {
Emeric Brunb5997f72017-07-03 11:34:05 +02002121 list_for_each_entry(elt, &ref->head, list) {
Dragan Dosenf1474792018-09-18 20:18:09 +02002122 char *err = NULL;
2123 struct sample_data *data = NULL;
2124
Emeric Brunb5997f72017-07-03 11:34:05 +02002125 /* Create sample */
2126 if (elt->sample && expr->pat_head->parse_smp) {
2127 /* New sample. */
2128 data = malloc(sizeof(*data));
2129 if (!data)
2130 continue;
2131
2132 /* Parse value. */
2133 if (!expr->pat_head->parse_smp(elt->sample, data)) {
2134 memprintf(&err, "unable to parse '%s'", elt->sample);
2135 send_log(NULL, LOG_NOTICE, "%s", err);
2136 free(err);
2137 free(data);
2138 continue;
2139 }
2140
2141 }
Emeric Brunb5997f72017-07-03 11:34:05 +02002142
2143 /* initialise pattern */
2144 memset(&pattern, 0, sizeof(pattern));
2145 pattern.data = data;
2146 pattern.ref = elt;
2147
2148 /* parse pattern */
2149 if (!expr->pat_head->parse(elt->pattern, &pattern, expr->mflags, &err)) {
Thierry FOURNIER46006bd2014-03-21 21:45:15 +01002150 send_log(NULL, LOG_NOTICE, "%s", err);
2151 free(err);
Emeric Brunb5997f72017-07-03 11:34:05 +02002152 free(data);
2153 continue;
2154 }
2155
2156 /* index pattern */
2157 if (!expr->pat_head->index(expr, &pattern, &err)) {
2158 send_log(NULL, LOG_NOTICE, "%s", err);
2159 free(err);
2160 free(data);
2161 continue;
Thierry FOURNIER46006bd2014-03-21 21:45:15 +01002162 }
2163 }
Christopher Faulet2a944ee2017-11-07 10:42:54 +01002164 HA_RWLOCK_WRUNLOCK(PATEXP_LOCK, &expr->lock);
Thierry FOURNIER46006bd2014-03-21 21:45:15 +01002165 }
Christopher Faulet2a944ee2017-11-07 10:42:54 +01002166 HA_SPIN_UNLOCK(PATREF_LOCK, &ref->lock);
Willy Tarreau114d6982020-11-03 15:55:35 +01002167
2168#if defined(HA_HAVE_MALLOC_TRIM)
2169 malloc_trim(0);
2170#endif
Thierry FOURNIER46006bd2014-03-21 21:45:15 +01002171}
2172
Willy Tarreauae83e632020-11-03 10:37:31 +01002173/* This function prunes all entries of <ref> and all their associated
2174 * pattern_expr. It may return before the end of the list is reached,
2175 * returning 0, to yield, indicating to the caller that it must call it again.
2176 * until it returns non-zero. All patterns are purged, both current ones and
2177 * future or incomplete ones. This is used by "clear map" or "clear acl".
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002178 */
Willy Tarreaud1d005d2019-12-20 18:22:02 +01002179int pat_ref_prune(struct pat_ref *ref)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002180{
Willy Tarreauae83e632020-11-03 10:37:31 +01002181 return pat_ref_purge_older(ref, ref->curr_gen + 1, 100) &&
2182 pat_ref_purge_older(ref, ref->next_gen + 1, 100);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002183}
2184
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01002185/* This function looks up any existing reference <ref> in pattern_head <head>, and
2186 * returns the associated pattern_expr pointer if found, otherwise NULL.
2187 */
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002188struct pattern_expr *pattern_lookup_expr(struct pattern_head *head, struct pat_ref *ref)
2189{
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002190 struct pattern_expr_list *expr;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002191
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002192 list_for_each_entry(expr, &head->head, list)
2193 if (expr->expr->ref == ref)
2194 return expr->expr;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002195 return NULL;
2196}
2197
Joseph Herlant4189d672018-11-15 10:22:31 -08002198/* This function creates new pattern_expr associated to the reference <ref>.
2199 * <ref> can be NULL. If an error occurs, the function returns NULL and
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002200 * <err> is filled. Otherwise, the function returns new pattern_expr linked
2201 * with <head> and <ref>.
Thierry FOURNIER315ec422014-11-24 11:14:42 +01002202 *
Joseph Herlant4189d672018-11-15 10:22:31 -08002203 * The returned value can be an already filled pattern list, in this case the
Thierry FOURNIER315ec422014-11-24 11:14:42 +01002204 * flag <reuse> is set.
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002205 */
Thierry FOURNIER315ec422014-11-24 11:14:42 +01002206struct pattern_expr *pattern_new_expr(struct pattern_head *head, struct pat_ref *ref,
Emeric Brun7d27f3c2017-07-03 17:54:23 +02002207 int patflags, char **err, int *reuse)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002208{
2209 struct pattern_expr *expr;
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002210 struct pattern_expr_list *list;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002211
Thierry FOURNIER315ec422014-11-24 11:14:42 +01002212 if (reuse)
2213 *reuse = 0;
2214
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002215 /* Memory and initialization of the chain element. */
Willy Tarreau8135d9b2020-10-30 15:35:11 +01002216 list = calloc(1, sizeof(*list));
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002217 if (!list) {
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002218 memprintf(err, "out of memory");
2219 return NULL;
2220 }
2221
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002222 /* Look for existing similar expr. No that only the index, parse and
2223 * parse_smp function must be identical for having similar pattern.
Joseph Herlant4189d672018-11-15 10:22:31 -08002224 * The other function depends of these first.
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002225 */
2226 if (ref) {
2227 list_for_each_entry(expr, &ref->pat, list)
2228 if (expr->pat_head->index == head->index &&
2229 expr->pat_head->parse == head->parse &&
Emeric Brun7d27f3c2017-07-03 17:54:23 +02002230 expr->pat_head->parse_smp == head->parse_smp &&
2231 expr->mflags == patflags)
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002232 break;
2233 if (&expr->list == &ref->pat)
2234 expr = NULL;
2235 }
2236 else
2237 expr = NULL;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002238
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002239 /* If no similar expr was found, we create new expr. */
2240 if (!expr) {
2241 /* Get a lot of memory for the expr struct. */
Willy Tarreau8135d9b2020-10-30 15:35:11 +01002242 expr = calloc(1, sizeof(*expr));
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002243 if (!expr) {
Andreas Seltenreiche6e22e82016-03-03 20:20:23 +01002244 free(list);
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002245 memprintf(err, "out of memory");
2246 return NULL;
2247 }
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002248
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002249 /* Initialize this new expr. */
2250 pattern_init_expr(expr);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002251
Emeric Brun7d27f3c2017-07-03 17:54:23 +02002252 /* Copy the pattern matching and indexing flags. */
2253 expr->mflags = patflags;
2254
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002255 /* This new pattern expression reference one of his heads. */
2256 expr->pat_head = head;
2257
Willy Tarreau2b718102021-04-21 07:32:39 +02002258 /* Link with ref, or to self to facilitate LIST_DELETE() */
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002259 if (ref)
Willy Tarreau2b718102021-04-21 07:32:39 +02002260 LIST_APPEND(&ref->pat, &expr->list);
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002261 else
2262 LIST_INIT(&expr->list);
2263
2264 expr->ref = ref;
2265
Christopher Faulet2a944ee2017-11-07 10:42:54 +01002266 HA_RWLOCK_INIT(&expr->lock);
Emeric Brunb5997f72017-07-03 11:34:05 +02002267
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002268 /* We must free this pattern if it is no more used. */
2269 list->do_free = 1;
2270 }
2271 else {
2272 /* If the pattern used already exists, it is already linked
2273 * with ref and we must not free it.
2274 */
2275 list->do_free = 0;
Thierry FOURNIER315ec422014-11-24 11:14:42 +01002276 if (reuse)
2277 *reuse = 1;
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002278 }
2279
2280 /* The new list element reference the pattern_expr. */
2281 list->expr = expr;
2282
2283 /* Link the list element with the pattern_head. */
Willy Tarreau2b718102021-04-21 07:32:39 +02002284 LIST_APPEND(&head->head, &list->list);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002285 return expr;
2286}
2287
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002288/* Reads patterns from a file. If <err_msg> is non-NULL, an error message will
2289 * be returned there on errors and the caller will have to free it.
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002290 *
2291 * The file contains one key + value per line. Lines which start with '#' are
2292 * ignored, just like empty lines. Leading tabs/spaces are stripped. The key is
2293 * then the first "word" (series of non-space/tabs characters), and the value is
2294 * what follows this series of space/tab till the end of the line excluding
2295 * trailing spaces/tabs.
2296 *
2297 * Example :
2298 *
2299 * # this is a comment and is ignored
2300 * 62.212.114.60 1wt.eu \n
2301 * <-><-----------><---><----><---->
2302 * | | | | `--- trailing spaces ignored
2303 * | | | `-------- value
2304 * | | `--------------- middle spaces ignored
2305 * | `------------------------ key
2306 * `-------------------------------- leading spaces ignored
2307 *
Ilya Shipitsin47d17182020-06-21 21:42:57 +05002308 * Return non-zero in case of success, otherwise 0.
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002309 */
2310int pat_ref_read_from_file_smp(struct pat_ref *ref, const char *filename, char **err)
2311{
2312 FILE *file;
2313 char *c;
2314 int ret = 0;
2315 int line = 0;
2316 char *key_beg;
2317 char *key_end;
2318 char *value_beg;
2319 char *value_end;
2320
2321 file = fopen(filename, "r");
2322 if (!file) {
2323 memprintf(err, "failed to open pattern file <%s>", filename);
2324 return 0;
2325 }
2326
2327 /* now parse all patterns. The file may contain only one pattern
2328 * followed by one value per line. The start spaces, separator spaces
2329 * and and spaces are stripped. Each can contain comment started by '#'
2330 */
Willy Tarreau843b7cb2018-07-13 10:54:26 +02002331 while (fgets(trash.area, trash.size, file) != NULL) {
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002332 line++;
Willy Tarreau843b7cb2018-07-13 10:54:26 +02002333 c = trash.area;
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002334
2335 /* ignore lines beginning with a dash */
2336 if (*c == '#')
2337 continue;
2338
2339 /* strip leading spaces and tabs */
2340 while (*c == ' ' || *c == '\t')
2341 c++;
2342
2343 /* empty lines are ignored too */
2344 if (*c == '\0' || *c == '\r' || *c == '\n')
2345 continue;
2346
2347 /* look for the end of the key */
2348 key_beg = c;
2349 while (*c && *c != ' ' && *c != '\t' && *c != '\n' && *c != '\r')
2350 c++;
2351
2352 key_end = c;
2353
2354 /* strip middle spaces and tabs */
2355 while (*c == ' ' || *c == '\t')
2356 c++;
2357
2358 /* look for the end of the value, it is the end of the line */
2359 value_beg = c;
2360 while (*c && *c != '\n' && *c != '\r')
2361 c++;
2362 value_end = c;
2363
2364 /* trim possibly trailing spaces and tabs */
2365 while (value_end > value_beg && (value_end[-1] == ' ' || value_end[-1] == '\t'))
2366 value_end--;
2367
2368 /* set final \0 and check entries */
2369 *key_end = '\0';
2370 *value_end = '\0';
2371
2372 /* insert values */
2373 if (!pat_ref_append(ref, key_beg, value_beg, line)) {
2374 memprintf(err, "out of memory");
2375 goto out_close;
2376 }
2377 }
2378
Jerome Magnin3c79d4b2020-01-17 16:09:33 +01002379 if (ferror(file)) {
2380 memprintf(err, "error encountered while reading <%s> : %s",
2381 filename, strerror(errno));
2382 goto out_close;
2383 }
Ilya Shipitsin47d17182020-06-21 21:42:57 +05002384 /* success */
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002385 ret = 1;
2386
2387 out_close:
2388 fclose(file);
2389 return ret;
2390}
2391
2392/* Reads patterns from a file. If <err_msg> is non-NULL, an error message will
2393 * be returned there on errors and the caller will have to free it.
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002394 */
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002395int pat_ref_read_from_file(struct pat_ref *ref, const char *filename, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002396{
2397 FILE *file;
2398 char *c;
2399 char *arg;
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002400 int ret = 0;
2401 int line = 0;
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002402
2403 file = fopen(filename, "r");
2404 if (!file) {
2405 memprintf(err, "failed to open pattern file <%s>", filename);
2406 return 0;
2407 }
2408
2409 /* now parse all patterns. The file may contain only one pattern per
2410 * line. If the line contains spaces, they will be part of the pattern.
2411 * The pattern stops at the first CR, LF or EOF encountered.
2412 */
Willy Tarreau843b7cb2018-07-13 10:54:26 +02002413 while (fgets(trash.area, trash.size, file) != NULL) {
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002414 line++;
Willy Tarreau843b7cb2018-07-13 10:54:26 +02002415 c = trash.area;
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002416
2417 /* ignore lines beginning with a dash */
2418 if (*c == '#')
2419 continue;
2420
2421 /* strip leading spaces and tabs */
2422 while (*c == ' ' || *c == '\t')
2423 c++;
2424
2425
2426 arg = c;
2427 while (*c && *c != '\n' && *c != '\r')
2428 c++;
2429 *c = 0;
2430
2431 /* empty lines are ignored too */
2432 if (c == arg)
2433 continue;
2434
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002435 if (!pat_ref_append(ref, arg, NULL, line)) {
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002436 memprintf(err, "out of memory when loading patterns from file <%s>", filename);
2437 goto out_close;
2438 }
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002439 }
2440
Jerome Magnin3c79d4b2020-01-17 16:09:33 +01002441 if (ferror(file)) {
2442 memprintf(err, "error encountered while reading <%s> : %s",
2443 filename, strerror(errno));
2444 goto out_close;
2445 }
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002446 ret = 1; /* success */
2447
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002448 out_close:
2449 fclose(file);
2450 return ret;
2451}
2452
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002453int pattern_read_from_file(struct pattern_head *head, unsigned int refflags,
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002454 const char *filename, int patflags, int load_smp,
Thierry FOURNIER94580c92014-02-11 14:36:45 +01002455 char **err, const char *file, int line)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002456{
2457 struct pat_ref *ref;
2458 struct pattern_expr *expr;
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002459 struct pat_ref_elt *elt;
Willy Tarreau4deaf392014-11-26 13:17:03 +01002460 int reuse = 0;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002461
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002462 /* Lookup for the existing reference. */
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002463 ref = pat_ref_lookup(filename);
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002464
2465 /* If the reference doesn't exists, create it and load associated file. */
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002466 if (!ref) {
Thierry FOURNIER94580c92014-02-11 14:36:45 +01002467 chunk_printf(&trash,
2468 "pattern loaded from file '%s' used by %s at file '%s' line %d",
2469 filename, refflags & PAT_REF_MAP ? "map" : "acl", file, line);
2470
Willy Tarreau843b7cb2018-07-13 10:54:26 +02002471 ref = pat_ref_new(filename, trash.area, refflags);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002472 if (!ref) {
2473 memprintf(err, "out of memory");
2474 return 0;
2475 }
2476
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002477 if (load_smp) {
Thierry FOURNIERc0bd9102014-01-29 12:32:58 +01002478 ref->flags |= PAT_REF_SMP;
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002479 if (!pat_ref_read_from_file_smp(ref, filename, err))
2480 return 0;
2481 }
2482 else {
2483 if (!pat_ref_read_from_file(ref, filename, err))
2484 return 0;
2485 }
2486 }
2487 else {
Thierry FOURNIERc0bd9102014-01-29 12:32:58 +01002488 /* The reference already exists, check the map compatibility. */
2489
2490 /* If the load require samples and the flag PAT_REF_SMP is not set,
2491 * the reference doesn't contain sample, and cannot be used.
2492 */
2493 if (load_smp) {
2494 if (!(ref->flags & PAT_REF_SMP)) {
2495 memprintf(err, "The file \"%s\" is already used as one column file "
2496 "and cannot be used by as two column file.",
2497 filename);
2498 return 0;
2499 }
2500 }
2501 else {
2502 /* The load doesn't require samples. If the flag PAT_REF_SMP is
2503 * set, the reference contains a sample, and cannot be used.
2504 */
2505 if (ref->flags & PAT_REF_SMP) {
2506 memprintf(err, "The file \"%s\" is already used as two column file "
2507 "and cannot be used by as one column file.",
2508 filename);
2509 return 0;
2510 }
2511 }
2512
Thierry FOURNIER94580c92014-02-11 14:36:45 +01002513 /* Extends display */
2514 chunk_printf(&trash, "%s", ref->display);
2515 chunk_appendf(&trash, ", by %s at file '%s' line %d",
2516 refflags & PAT_REF_MAP ? "map" : "acl", file, line);
2517 free(ref->display);
Willy Tarreau843b7cb2018-07-13 10:54:26 +02002518 ref->display = strdup(trash.area);
Thierry FOURNIER94580c92014-02-11 14:36:45 +01002519 if (!ref->display) {
2520 memprintf(err, "out of memory");
2521 return 0;
2522 }
2523
Thierry FOURNIERc0bd9102014-01-29 12:32:58 +01002524 /* Merge flags. */
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002525 ref->flags |= refflags;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002526 }
2527
2528 /* Now, we can loading patterns from the reference. */
2529
2530 /* Lookup for existing reference in the head. If the reference
2531 * doesn't exists, create it.
2532 */
2533 expr = pattern_lookup_expr(head, ref);
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02002534 if (!expr || (expr->mflags != patflags)) {
Emeric Brun7d27f3c2017-07-03 17:54:23 +02002535 expr = pattern_new_expr(head, ref, patflags, err, &reuse);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002536 if (!expr)
2537 return 0;
2538 }
2539
Thierry FOURNIER315ec422014-11-24 11:14:42 +01002540 /* The returned expression may be not empty, because the function
2541 * "pattern_new_expr" lookup for similar pattern list and can
2542 * reuse a already filled pattern list. In this case, we can not
2543 * reload the patterns.
2544 */
2545 if (reuse)
2546 return 1;
2547
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002548 /* Load reference content in the pattern expression. */
2549 list_for_each_entry(elt, &ref->head, list) {
2550 if (!pat_ref_push(elt, expr, patflags, err)) {
2551 if (elt->line > 0)
2552 memprintf(err, "%s at line %d of file '%s'",
2553 *err, elt->line, filename);
2554 return 0;
2555 }
2556 }
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002557
2558 return 1;
2559}
2560
Thierry FOURNIER1794fdf2014-01-17 15:25:13 +01002561/* This function executes a pattern match on a sample. It applies pattern <expr>
Thayne McCombs8f0cc5c2021-01-07 21:35:52 -07002562 * to sample <smp>. The function returns NULL if the sample don't match. It returns
Thierry FOURNIER1794fdf2014-01-17 15:25:13 +01002563 * non-null if the sample match. If <fill> is true and the sample match, the
2564 * function returns the matched pattern. In many cases, this pattern can be a
2565 * static buffer.
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002566 */
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002567struct pattern *pattern_exec_match(struct pattern_head *head, struct sample *smp, int fill)
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002568{
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002569 struct pattern_expr_list *list;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002570 struct pattern *pat;
2571
2572 if (!head->match) {
Thierry FOURNIER1794fdf2014-01-17 15:25:13 +01002573 if (fill) {
Thierry FOURNIER503bb092015-08-19 08:35:43 +02002574 static_pattern.data = NULL;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +01002575 static_pattern.ref = NULL;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02002576 static_pattern.sflags = 0;
Thierry FOURNIER07ee64e2015-07-06 23:43:03 +02002577 static_pattern.type = SMP_T_SINT;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +01002578 static_pattern.val.i = 1;
Thierry FOURNIER1794fdf2014-01-17 15:25:13 +01002579 }
Thierry FOURNIER1794fdf2014-01-17 15:25:13 +01002580 return &static_pattern;
2581 }
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002582
Thierry FOURNIER5d344082014-01-27 14:19:53 +01002583 /* convert input to string */
2584 if (!sample_convert(smp, head->expect_type))
2585 return NULL;
2586
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002587 list_for_each_entry(list, &head->head, list) {
Christopher Faulet2a944ee2017-11-07 10:42:54 +01002588 HA_RWLOCK_RDLOCK(PATEXP_LOCK, &list->expr->lock);
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002589 pat = head->match(smp, list->expr, fill);
Emeric Brunb5997f72017-07-03 11:34:05 +02002590 if (pat) {
2591 /* We duplicate the pattern cause it could be modified
2592 by another thread */
2593 if (pat != &static_pattern) {
2594 memcpy(&static_pattern, pat, sizeof(struct pattern));
2595 pat = &static_pattern;
2596 }
2597
2598 /* We also duplicate the sample data for
2599 same reason */
2600 if (pat->data && (pat->data != &static_sample_data)) {
Christopher Faulet09fdf4b2017-11-09 16:14:16 +01002601 switch(pat->data->type) {
Emeric Brunb5997f72017-07-03 11:34:05 +02002602 case SMP_T_STR:
2603 static_sample_data.type = SMP_T_STR;
2604 static_sample_data.u.str = *get_trash_chunk();
Willy Tarreau843b7cb2018-07-13 10:54:26 +02002605 static_sample_data.u.str.data = pat->data->u.str.data;
2606 if (static_sample_data.u.str.data >= static_sample_data.u.str.size)
2607 static_sample_data.u.str.data = static_sample_data.u.str.size - 1;
2608 memcpy(static_sample_data.u.str.area,
Willy Tarreau2fc761e2020-06-11 16:37:35 +02002609 pat->data->u.str.area, static_sample_data.u.str.data);
Willy Tarreau843b7cb2018-07-13 10:54:26 +02002610 static_sample_data.u.str.area[static_sample_data.u.str.data] = 0;
Willy Tarreau2fc761e2020-06-11 16:37:35 +02002611 pat->data = &static_sample_data;
2612 break;
2613
Emeric Brunb5997f72017-07-03 11:34:05 +02002614 case SMP_T_IPV4:
2615 case SMP_T_IPV6:
2616 case SMP_T_SINT:
2617 memcpy(&static_sample_data, pat->data, sizeof(struct sample_data));
Willy Tarreau2fc761e2020-06-11 16:37:35 +02002618 pat->data = &static_sample_data;
2619 break;
Emeric Brunb5997f72017-07-03 11:34:05 +02002620 default:
Willy Tarreau2fc761e2020-06-11 16:37:35 +02002621 /* unimplemented pattern type */
Emeric Brunb5997f72017-07-03 11:34:05 +02002622 pat->data = NULL;
Willy Tarreau2fc761e2020-06-11 16:37:35 +02002623 break;
Emeric Brunb5997f72017-07-03 11:34:05 +02002624 }
Emeric Brunb5997f72017-07-03 11:34:05 +02002625 }
Christopher Faulet2a944ee2017-11-07 10:42:54 +01002626 HA_RWLOCK_RDUNLOCK(PATEXP_LOCK, &list->expr->lock);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002627 return pat;
Emeric Brunb5997f72017-07-03 11:34:05 +02002628 }
Christopher Faulet2a944ee2017-11-07 10:42:54 +01002629 HA_RWLOCK_RDUNLOCK(PATEXP_LOCK, &list->expr->lock);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002630 }
2631 return NULL;
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002632}
2633
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01002634/* This function prunes the pattern expressions starting at pattern_head <head>. */
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002635void pattern_prune(struct pattern_head *head)
Thierry FOURNIER6f7203d2014-01-14 16:24:51 +01002636{
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002637 struct pattern_expr_list *list, *safe;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002638
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002639 list_for_each_entry_safe(list, safe, &head->head, list) {
Willy Tarreau2b718102021-04-21 07:32:39 +02002640 LIST_DELETE(&list->list);
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002641 if (list->do_free) {
Willy Tarreau2b718102021-04-21 07:32:39 +02002642 LIST_DELETE(&list->expr->list);
Christopher Faulet2a944ee2017-11-07 10:42:54 +01002643 HA_RWLOCK_WRLOCK(PATEXP_LOCK, &list->expr->lock);
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002644 head->prune(list->expr);
Christopher Faulet2a944ee2017-11-07 10:42:54 +01002645 HA_RWLOCK_WRUNLOCK(PATEXP_LOCK, &list->expr->lock);
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002646 free(list->expr);
2647 }
2648 free(list);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002649 }
Thierry FOURNIER6f7203d2014-01-14 16:24:51 +01002650}
2651
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01002652/* This function searches occurrences of pattern reference element <ref> in
2653 * expression <expr> and returns a pointer to a pointer of the sample storage.
2654 * If <ref> is not found, NULL is returned.
Thierry FOURNIER55d0b102014-01-15 11:25:26 +01002655 */
Thierry FOURNIER12ba0c22015-08-14 00:02:11 +02002656struct sample_data **pattern_find_smp(struct pattern_expr *expr, struct pat_ref_elt *ref)
Thierry FOURNIER55d0b102014-01-15 11:25:26 +01002657{
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01002658 struct ebmb_node *node;
2659 struct pattern_tree *elt;
2660 struct pattern_list *pat;
Thierry FOURNIER55d0b102014-01-15 11:25:26 +01002661
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01002662 for (node = ebmb_first(&expr->pattern_tree);
2663 node;
2664 node = ebmb_next(node)) {
2665 elt = container_of(node, struct pattern_tree, node);
2666 if (elt->ref == ref)
Thierry FOURNIER503bb092015-08-19 08:35:43 +02002667 return &elt->data;
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01002668 }
2669
2670 for (node = ebmb_first(&expr->pattern_tree_2);
2671 node;
2672 node = ebmb_next(node)) {
2673 elt = container_of(node, struct pattern_tree, node);
2674 if (elt->ref == ref)
Thierry FOURNIER503bb092015-08-19 08:35:43 +02002675 return &elt->data;
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01002676 }
2677
2678 list_for_each_entry(pat, &expr->patterns, list)
2679 if (pat->pat.ref == ref)
Thierry FOURNIER503bb092015-08-19 08:35:43 +02002680 return &pat->pat.data;
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01002681
2682 return NULL;
Thierry FOURNIER55d0b102014-01-15 11:25:26 +01002683}
2684
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01002685/* This function compares two pat_ref** on their unique_id, and returns -1/0/1
2686 * depending on their order (suitable for sorting).
2687 */
Carl Henrik Lundef91ac192020-02-27 16:45:50 +01002688static int cmp_pat_ref(const void *_a, const void *_b)
2689{
2690 struct pat_ref * const *a = _a;
2691 struct pat_ref * const *b = _b;
2692
2693 if ((*a)->unique_id < (*b)->unique_id)
2694 return -1;
2695 else if ((*a)->unique_id > (*b)->unique_id)
2696 return 1;
2697 return 0;
2698}
2699
Willy Tarreaua5bbaaf2020-10-30 16:03:50 +01002700/* This function finalizes the configuration parsing. It sets all the
2701 * automatic ids.
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002702 */
Carl Henrik Lundef91ac192020-02-27 16:45:50 +01002703int pattern_finalize_config(void)
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002704{
Tim Duesterhusb584b442020-03-17 21:08:24 +01002705 size_t len = 0;
2706 size_t unassigned_pos = 0;
Carl Henrik Lundef91ac192020-02-27 16:45:50 +01002707 int next_unique_id = 0;
Tim Duesterhusb584b442020-03-17 21:08:24 +01002708 size_t i, j;
Carl Henrik Lundef91ac192020-02-27 16:45:50 +01002709 struct pat_ref *ref, **arr;
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002710 struct list pr = LIST_HEAD_INIT(pr);
2711
Willy Tarreau52bf8392020-03-08 00:42:37 +01002712 pat_lru_seed = ha_random();
Willy Tarreauf3045d22015-04-29 16:24:50 +02002713
Carl Henrik Lundef91ac192020-02-27 16:45:50 +01002714 /* Count pat_refs with user defined unique_id and totalt count */
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002715 list_for_each_entry(ref, &pattern_reference, list) {
Carl Henrik Lundef91ac192020-02-27 16:45:50 +01002716 len++;
2717 if (ref->unique_id != -1)
2718 unassigned_pos++;
2719 }
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002720
Tim Duesterhusb584b442020-03-17 21:08:24 +01002721 if (len == 0) {
2722 return 0;
2723 }
2724
Carl Henrik Lundef91ac192020-02-27 16:45:50 +01002725 arr = calloc(len, sizeof(*arr));
2726 if (arr == NULL) {
2727 ha_alert("Out of memory error.\n");
2728 return ERR_ALERT | ERR_FATAL;
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002729 }
2730
Carl Henrik Lundef91ac192020-02-27 16:45:50 +01002731 i = 0;
2732 j = unassigned_pos;
2733 list_for_each_entry(ref, &pattern_reference, list) {
2734 if (ref->unique_id != -1)
2735 arr[i++] = ref;
2736 else
2737 arr[j++] = ref;
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002738 }
2739
Carl Henrik Lundef91ac192020-02-27 16:45:50 +01002740 /* Sort first segment of array with user-defined unique ids for
2741 * fast lookup when generating unique ids
2742 */
2743 qsort(arr, unassigned_pos, sizeof(*arr), cmp_pat_ref);
2744
2745 /* Assign unique ids to the rest of the elements */
2746 for (i = unassigned_pos; i < len; i++) {
2747 do {
2748 arr[i]->unique_id = next_unique_id++;
2749 } while (bsearch(&arr[i], arr, unassigned_pos, sizeof(*arr), cmp_pat_ref));
2750 }
2751
2752 /* Sort complete array */
2753 qsort(arr, len, sizeof(*arr), cmp_pat_ref);
2754
2755 /* Convert back to linked list */
2756 for (i = 0; i < len; i++)
Willy Tarreau2b718102021-04-21 07:32:39 +02002757 LIST_APPEND(&pr, &arr[i]->list);
Carl Henrik Lundef91ac192020-02-27 16:45:50 +01002758
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002759 /* swap root */
Willy Tarreau2b718102021-04-21 07:32:39 +02002760 LIST_INSERT(&pr, &pattern_reference);
2761 LIST_DELETE(&pr);
Carl Henrik Lundef91ac192020-02-27 16:45:50 +01002762
2763 free(arr);
2764 return 0;
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002765}
Willy Tarreau403bfbb2019-10-23 06:59:31 +02002766
2767static int pattern_per_thread_lru_alloc()
2768{
2769 if (!global.tune.pattern_cache)
2770 return 1;
2771 pat_lru_tree = lru64_new(global.tune.pattern_cache);
2772 return !!pat_lru_tree;
2773}
2774
2775static void pattern_per_thread_lru_free()
2776{
2777 lru64_destroy(pat_lru_tree);
2778}
2779
2780REGISTER_PER_THREAD_ALLOC(pattern_per_thread_lru_alloc);
2781REGISTER_PER_THREAD_FREE(pattern_per_thread_lru_free);