blob: 51981fd9833d173f39ec5226cee332dc787fb09a [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>
15
16#include <common/config.h>
17#include <common/standard.h>
18
19#include <types/global.h>
20#include <types/pattern.h>
21
Thierry FOURNIER46006bd2014-03-21 21:45:15 +010022#include <proto/log.h>
Thierry FOURNIERed66c292013-11-28 11:05:19 +010023#include <proto/pattern.h>
Thierry FOURNIERe3ded592013-12-06 15:36:54 +010024#include <proto/sample.h>
Thierry FOURNIERed66c292013-11-28 11:05:19 +010025
26#include <ebsttree.h>
27
Thierry FOURNIERa65b3432013-11-28 18:22:00 +010028char *pat_match_names[PAT_MATCH_NUM] = {
29 [PAT_MATCH_FOUND] = "found",
30 [PAT_MATCH_BOOL] = "bool",
31 [PAT_MATCH_INT] = "int",
32 [PAT_MATCH_IP] = "ip",
33 [PAT_MATCH_BIN] = "bin",
34 [PAT_MATCH_LEN] = "len",
35 [PAT_MATCH_STR] = "str",
36 [PAT_MATCH_BEG] = "beg",
37 [PAT_MATCH_SUB] = "sub",
38 [PAT_MATCH_DIR] = "dir",
39 [PAT_MATCH_DOM] = "dom",
40 [PAT_MATCH_END] = "end",
41 [PAT_MATCH_REG] = "reg",
Thierry FOURNIERed66c292013-11-28 11:05:19 +010042};
43
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +020044int (*pat_parse_fcts[PAT_MATCH_NUM])(const char *, struct pattern *, int, char **) = {
Thierry FOURNIERa65b3432013-11-28 18:22:00 +010045 [PAT_MATCH_FOUND] = pat_parse_nothing,
46 [PAT_MATCH_BOOL] = pat_parse_nothing,
47 [PAT_MATCH_INT] = pat_parse_int,
48 [PAT_MATCH_IP] = pat_parse_ip,
49 [PAT_MATCH_BIN] = pat_parse_bin,
Thierry FOURNIER5d344082014-01-27 14:19:53 +010050 [PAT_MATCH_LEN] = pat_parse_int,
Thierry FOURNIERa65b3432013-11-28 18:22:00 +010051 [PAT_MATCH_STR] = pat_parse_str,
52 [PAT_MATCH_BEG] = pat_parse_str,
53 [PAT_MATCH_SUB] = pat_parse_str,
54 [PAT_MATCH_DIR] = pat_parse_str,
55 [PAT_MATCH_DOM] = pat_parse_str,
56 [PAT_MATCH_END] = pat_parse_str,
57 [PAT_MATCH_REG] = pat_parse_reg,
Thierry FOURNIERed66c292013-11-28 11:05:19 +010058};
59
Thierry FOURNIERb9b08462013-12-13 15:12:32 +010060int (*pat_index_fcts[PAT_MATCH_NUM])(struct pattern_expr *, struct pattern *, char **) = {
61 [PAT_MATCH_FOUND] = pat_idx_list_val,
62 [PAT_MATCH_BOOL] = pat_idx_list_val,
63 [PAT_MATCH_INT] = pat_idx_list_val,
64 [PAT_MATCH_IP] = pat_idx_tree_ip,
65 [PAT_MATCH_BIN] = pat_idx_list_ptr,
66 [PAT_MATCH_LEN] = pat_idx_list_val,
67 [PAT_MATCH_STR] = pat_idx_tree_str,
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +020068 [PAT_MATCH_BEG] = pat_idx_tree_pfx,
Thierry FOURNIERb9b08462013-12-13 15:12:32 +010069 [PAT_MATCH_SUB] = pat_idx_list_str,
70 [PAT_MATCH_DIR] = pat_idx_list_str,
71 [PAT_MATCH_DOM] = pat_idx_list_str,
72 [PAT_MATCH_END] = pat_idx_list_str,
73 [PAT_MATCH_REG] = pat_idx_list_reg,
74};
75
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +010076void (*pat_delete_fcts[PAT_MATCH_NUM])(struct pattern_expr *, struct pat_ref_elt *) = {
Thierry FOURNIERb1136502014-01-15 11:38:49 +010077 [PAT_MATCH_FOUND] = pat_del_list_val,
78 [PAT_MATCH_BOOL] = pat_del_list_val,
79 [PAT_MATCH_INT] = pat_del_list_val,
80 [PAT_MATCH_IP] = pat_del_tree_ip,
81 [PAT_MATCH_BIN] = pat_del_list_ptr,
82 [PAT_MATCH_LEN] = pat_del_list_val,
83 [PAT_MATCH_STR] = pat_del_tree_str,
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +020084 [PAT_MATCH_BEG] = pat_del_tree_str,
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +010085 [PAT_MATCH_SUB] = pat_del_list_ptr,
86 [PAT_MATCH_DIR] = pat_del_list_ptr,
87 [PAT_MATCH_DOM] = pat_del_list_ptr,
88 [PAT_MATCH_END] = pat_del_list_ptr,
Thierry FOURNIERb1136502014-01-15 11:38:49 +010089 [PAT_MATCH_REG] = pat_del_list_reg,
90};
91
Thierry FOURNIER6f7203d2014-01-14 16:24:51 +010092void (*pat_prune_fcts[PAT_MATCH_NUM])(struct pattern_expr *) = {
93 [PAT_MATCH_FOUND] = pat_prune_val,
94 [PAT_MATCH_BOOL] = pat_prune_val,
95 [PAT_MATCH_INT] = pat_prune_val,
96 [PAT_MATCH_IP] = pat_prune_val,
97 [PAT_MATCH_BIN] = pat_prune_ptr,
98 [PAT_MATCH_LEN] = pat_prune_val,
99 [PAT_MATCH_STR] = pat_prune_ptr,
100 [PAT_MATCH_BEG] = pat_prune_ptr,
101 [PAT_MATCH_SUB] = pat_prune_ptr,
102 [PAT_MATCH_DIR] = pat_prune_ptr,
103 [PAT_MATCH_DOM] = pat_prune_ptr,
104 [PAT_MATCH_END] = pat_prune_ptr,
105 [PAT_MATCH_REG] = pat_prune_reg,
106};
107
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100108struct pattern *(*pat_match_fcts[PAT_MATCH_NUM])(struct sample *, struct pattern_expr *, int) = {
Thierry FOURNIERa65b3432013-11-28 18:22:00 +0100109 [PAT_MATCH_FOUND] = NULL,
110 [PAT_MATCH_BOOL] = pat_match_nothing,
111 [PAT_MATCH_INT] = pat_match_int,
112 [PAT_MATCH_IP] = pat_match_ip,
113 [PAT_MATCH_BIN] = pat_match_bin,
114 [PAT_MATCH_LEN] = pat_match_len,
115 [PAT_MATCH_STR] = pat_match_str,
116 [PAT_MATCH_BEG] = pat_match_beg,
117 [PAT_MATCH_SUB] = pat_match_sub,
118 [PAT_MATCH_DIR] = pat_match_dir,
119 [PAT_MATCH_DOM] = pat_match_dom,
120 [PAT_MATCH_END] = pat_match_end,
121 [PAT_MATCH_REG] = pat_match_reg,
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100122};
123
Thierry FOURNIERe3ded592013-12-06 15:36:54 +0100124/* Just used for checking configuration compatibility */
125int pat_match_types[PAT_MATCH_NUM] = {
126 [PAT_MATCH_FOUND] = SMP_T_UINT,
127 [PAT_MATCH_BOOL] = SMP_T_UINT,
128 [PAT_MATCH_INT] = SMP_T_UINT,
129 [PAT_MATCH_IP] = SMP_T_ADDR,
Thierry FOURNIER7654c9f2013-12-17 00:20:33 +0100130 [PAT_MATCH_BIN] = SMP_T_BIN,
131 [PAT_MATCH_LEN] = SMP_T_STR,
132 [PAT_MATCH_STR] = SMP_T_STR,
133 [PAT_MATCH_BEG] = SMP_T_STR,
134 [PAT_MATCH_SUB] = SMP_T_STR,
135 [PAT_MATCH_DIR] = SMP_T_STR,
136 [PAT_MATCH_DOM] = SMP_T_STR,
137 [PAT_MATCH_END] = SMP_T_STR,
138 [PAT_MATCH_REG] = SMP_T_STR,
Thierry FOURNIERe3ded592013-12-06 15:36:54 +0100139};
140
Thierry FOURNIER1794fdf2014-01-17 15:25:13 +0100141/* this struct is used to return information */
142static struct pattern static_pattern;
143
Thierry FOURNIER1e00d382014-02-11 11:31:40 +0100144/* This is the root of the list of all pattern_ref avalaibles. */
145struct list pattern_reference = LIST_HEAD_INIT(pattern_reference);
146
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100147/*
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100148 *
149 * The following functions are not exported and are used by internals process
150 * of pattern matching
151 *
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100152 */
153
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100154/* Background: Fast way to find a zero byte in a word
155 * http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord
156 * hasZeroByte = (v - 0x01010101UL) & ~v & 0x80808080UL;
157 *
158 * To look for 4 different byte values, xor the word with those bytes and
159 * then check for zero bytes:
160 *
161 * v = (((unsigned char)c * 0x1010101U) ^ delimiter)
162 * where <delimiter> is the 4 byte values to look for (as an uint)
163 * and <c> is the character that is being tested
164 */
165static inline unsigned int is_delimiter(unsigned char c, unsigned int mask)
166{
167 mask ^= (c * 0x01010101); /* propagate the char to all 4 bytes */
168 return (mask - 0x01010101) & ~mask & 0x80808080U;
169}
170
171static inline unsigned int make_4delim(unsigned char d1, unsigned char d2, unsigned char d3, unsigned char d4)
172{
173 return d1 << 24 | d2 << 16 | d3 << 8 | d4;
174}
175
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100176
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100177/*
178 *
179 * These functions are exported and may be used by any other component.
180 *
181 * The following functions are used for parsing pattern matching
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100182 * input value. The <text> contain the string to be parsed. <pattern>
183 * must be a preallocated pattern. The pat_parse_* functions fill this
184 * structure with the parsed value. <usage> can be PAT_U_COMPILE or
185 * PAT_U_LOOKUP. If the value PAT_U_COMPILE is used memory is allocated
186 * for filling the pattern. If the value PAT_U_LOOKUP is set, the parser
187 * use "trash" or return pointers to the input strings. In both cases,
188 * the caller must use the value PAT_U_LOOKUP with caution. <err> is
189 * filled with an error message built with memprintf() function.
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100190 *
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100191 * In succes case, the pat_parse_* function return 1. If the function
192 * fail, it returns 0 and <err> is filled.
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100193 *
194 */
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100195
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100196/* ignore the current line */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200197int pat_parse_nothing(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100198{
199 return 1;
200}
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100201
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100202/* Parse a string. It is allocated and duplicated. */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200203int pat_parse_str(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100204{
Thierry FOURNIER7654c9f2013-12-17 00:20:33 +0100205 pattern->type = SMP_T_STR;
Thierry FOURNIERedc15c32013-12-13 15:36:59 +0100206 pattern->ptr.str = (char *)text;
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100207 pattern->len = strlen(text);
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100208 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100209}
210
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100211/* Parse a binary written in hexa. It is allocated. */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200212int pat_parse_bin(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100213{
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100214 struct chunk *trash;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100215
Thierry FOURNIER7654c9f2013-12-17 00:20:33 +0100216 pattern->type = SMP_T_BIN;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100217 trash = get_trash_chunk();
218 pattern->len = trash->size;
219 pattern->ptr.str = trash->str;
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100220 return !!parse_binary(text, &pattern->ptr.str, &pattern->len, err);
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100221}
222
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100223/* Parse a regex. It is allocated. */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200224int pat_parse_reg(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100225{
Thierry FOURNIER0b2fe4a2013-12-06 20:33:50 +0100226 struct chunk *trash;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100227
Thierry FOURNIERedc15c32013-12-13 15:36:59 +0100228 trash = get_trash_chunk();
229 if (trash->size < sizeof(*pattern->ptr.reg)) {
230 memprintf(err, "no space avalaible in the buffer. expect %d, provides %d",
231 (int)sizeof(*pattern->ptr.reg), trash->size);
232 return 0;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100233 }
234
Thierry FOURNIER0b6d15f2014-01-29 19:35:16 +0100235 pattern->ptr.str = (char *)text;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100236
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100237 return 1;
238}
239
240/* Parse a range of positive integers delimited by either ':' or '-'. If only
241 * one integer is read, it is set as both min and max. An operator may be
242 * specified as the prefix, among this list of 5 :
243 *
244 * 0:eq, 1:gt, 2:ge, 3:lt, 4:le
245 *
246 * The default operator is "eq". It supports range matching. Ranges are
247 * rejected for other operators. The operator may be changed at any time.
248 * The operator is stored in the 'opaque' argument.
249 *
250 * If err is non-NULL, an error message will be returned there on errors and
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100251 * the caller will have to free it. The function returns zero on error, and
252 * non-zero on success.
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100253 *
254 */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200255int pat_parse_int(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100256{
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100257 const char *ptr = text;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100258
259 pattern->type = SMP_T_UINT;
Thierry FOURNIER7148ce62013-12-06 19:06:43 +0100260
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100261 /* Empty string is not valid */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100262 if (!*text)
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100263 goto not_valid_range;
264
265 /* Search ':' or '-' separator. */
266 while (*ptr != '\0' && *ptr != ':' && *ptr != '-')
267 ptr++;
268
269 /* If separator not found. */
270 if (!*ptr) {
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100271 if (strl2llrc(text, ptr - text, &pattern->val.range.min) != 0) {
272 memprintf(err, "'%s' is not a number", text);
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100273 return 0;
274 }
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100275 pattern->val.range.max = pattern->val.range.min;
276 pattern->val.range.min_set = 1;
277 pattern->val.range.max_set = 1;
278 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100279 }
280
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100281 /* If the separator is the first character. */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100282 if (ptr == text && *(ptr + 1) != '\0') {
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100283 if (strl2llrc(ptr + 1, strlen(ptr + 1), &pattern->val.range.max) != 0)
284 goto not_valid_range;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100285
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100286 pattern->val.range.min_set = 0;
287 pattern->val.range.max_set = 1;
288 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100289 }
290
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100291 /* If separator is the last character. */
292 if (*(ptr + 1) == '\0') {
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100293 if (strl2llrc(text, ptr - text, &pattern->val.range.min) != 0)
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100294 goto not_valid_range;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100295
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100296 pattern->val.range.min_set = 1;
297 pattern->val.range.max_set = 0;
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100298 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100299 }
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100300
301 /* Else, parse two numbers. */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100302 if (strl2llrc(text, ptr - text, &pattern->val.range.min) != 0)
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100303 goto not_valid_range;
304
305 if (strl2llrc(ptr + 1, strlen(ptr + 1), &pattern->val.range.max) != 0)
306 goto not_valid_range;
307
308 if (pattern->val.range.min > pattern->val.range.max)
309 goto not_valid_range;
310
311 pattern->val.range.min_set = 1;
312 pattern->val.range.max_set = 1;
313 return 1;
314
315 not_valid_range:
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100316 memprintf(err, "'%s' is not a valid number range", text);
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100317 return 0;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100318}
319
320/* Parse a range of positive 2-component versions delimited by either ':' or
321 * '-'. The version consists in a major and a minor, both of which must be
322 * smaller than 65536, because internally they will be represented as a 32-bit
323 * integer.
324 * If only one version is read, it is set as both min and max. Just like for
325 * pure integers, an operator may be specified as the prefix, among this list
326 * of 5 :
327 *
328 * 0:eq, 1:gt, 2:ge, 3:lt, 4:le
329 *
330 * The default operator is "eq". It supports range matching. Ranges are
331 * rejected for other operators. The operator may be changed at any time.
332 * The operator is stored in the 'opaque' argument. This allows constructs
333 * such as the following one :
334 *
335 * acl obsolete_ssl ssl_req_proto lt 3
336 * acl unsupported_ssl ssl_req_proto gt 3.1
337 * acl valid_ssl ssl_req_proto 3.0-3.1
338 *
339 */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200340int pat_parse_dotted_ver(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100341{
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100342 const char *ptr = text;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100343
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100344 pattern->type = SMP_T_UINT;
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100345
346 /* Search ':' or '-' separator. */
347 while (*ptr != '\0' && *ptr != ':' && *ptr != '-')
348 ptr++;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100349
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100350 /* If separator not found. */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100351 if (*ptr == '\0' && ptr > text) {
352 if (strl2llrc_dotted(text, ptr-text, &pattern->val.range.min) != 0) {
353 memprintf(err, "'%s' is not a dotted number", text);
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100354 return 0;
355 }
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100356 pattern->val.range.max = pattern->val.range.min;
357 pattern->val.range.min_set = 1;
358 pattern->val.range.max_set = 1;
359 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100360 }
361
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100362 /* If the separator is the first character. */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100363 if (ptr == text && *(ptr+1) != '\0') {
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100364 if (strl2llrc_dotted(ptr+1, strlen(ptr+1), &pattern->val.range.max) != 0) {
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100365 memprintf(err, "'%s' is not a valid dotted number range", text);
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100366 return 0;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100367 }
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100368 pattern->val.range.min_set = 0;
369 pattern->val.range.max_set = 1;
370 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100371 }
372
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100373 /* If separator is the last character. */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100374 if (ptr == &text[strlen(text)-1]) {
375 if (strl2llrc_dotted(text, ptr-text, &pattern->val.range.min) != 0) {
376 memprintf(err, "'%s' is not a valid dotted number range", text);
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100377 return 0;
378 }
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100379 pattern->val.range.min_set = 1;
380 pattern->val.range.max_set = 0;
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100381 return 1;
382 }
383
384 /* Else, parse two numbers. */
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100385 if (strl2llrc_dotted(text, ptr-text, &pattern->val.range.min) != 0) {
386 memprintf(err, "'%s' is not a valid dotted number range", text);
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100387 return 0;
388 }
389 if (strl2llrc_dotted(ptr+1, strlen(ptr+1), &pattern->val.range.max) != 0) {
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100390 memprintf(err, "'%s' is not a valid dotted number range", text);
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100391 return 0;
392 }
393 if (pattern->val.range.min > pattern->val.range.max) {
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100394 memprintf(err, "'%s' is not a valid dotted number range", text);
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100395 return 0;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100396 }
Thierry FOURNIER511e9472014-01-23 17:40:34 +0100397 pattern->val.range.min_set = 1;
398 pattern->val.range.max_set = 1;
399 return 1;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100400}
401
402/* Parse an IP address and an optional mask in the form addr[/mask].
403 * The addr may either be an IPv4 address or a hostname. The mask
404 * may either be a dotted mask or a number of bits. Returns 1 if OK,
405 * otherwise 0. NOTE: IP address patterns are typed (IPV4/IPV6).
406 */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200407int pat_parse_ip(const char *text, struct pattern *pattern, int mflags, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100408{
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200409 if (str2net(text, !(mflags & PAT_MF_NO_DNS) && (global.mode & MODE_STARTING),
Thierry FOURNIERfc7ac7b2014-02-11 15:23:04 +0100410 &pattern->val.ipv4.addr, &pattern->val.ipv4.mask)) {
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100411 pattern->type = SMP_T_IPV4;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100412 return 1;
413 }
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100414 else if (str62net(text, &pattern->val.ipv6.addr, &pattern->val.ipv6.mask)) {
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100415 pattern->type = SMP_T_IPV6;
416 return 1;
417 }
418 else {
Thierry FOURNIER580c32c2014-01-24 10:58:12 +0100419 memprintf(err, "'%s' is not a valid IPv4 or IPv6 address", text);
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100420 return 0;
421 }
422}
423
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100424/*
425 *
426 * These functions are exported and may be used by any other component.
427 *
428 * This fucntion just take a sample <smp> and check if this sample match
429 * with the pattern <pattern>. This fucntion return just PAT_MATCH or
430 * PAT_NOMATCH.
431 *
432 */
433
434/* always return false */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100435struct pattern *pat_match_nothing(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100436{
Thierry FOURNIERe5978bf2014-03-17 19:53:10 +0100437 if (smp->data.uint) {
438 if (fill) {
439 static_pattern.smp = NULL;
440 static_pattern.ref = NULL;
Thierry FOURNIERe5978bf2014-03-17 19:53:10 +0100441 static_pattern.type = 0;
442 static_pattern.ptr.str = NULL;
443 }
444 return &static_pattern;
445 }
446 else
447 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100448}
449
450
451/* NB: For two strings to be identical, it is required that their lengths match */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100452struct pattern *pat_match_str(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100453{
454 int icase;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100455 struct ebmb_node *node;
456 char prev;
457 struct pattern_tree *elt;
458 struct pattern_list *lst;
459 struct pattern *pattern;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100460
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100461 /* Lookup a string in the expression's pattern tree. */
462 if (!eb_is_empty(&expr->pattern_tree)) {
463 /* we may have to force a trailing zero on the test pattern */
464 prev = smp->data.str.str[smp->data.str.len];
465 if (prev)
466 smp->data.str.str[smp->data.str.len] = '\0';
467 node = ebst_lookup(&expr->pattern_tree, smp->data.str.str);
468 if (prev)
469 smp->data.str.str[smp->data.str.len] = prev;
470
471 if (node) {
472 if (fill) {
473 elt = ebmb_entry(node, struct pattern_tree, node);
474 static_pattern.smp = elt->smp;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +0100475 static_pattern.ref = elt->ref;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200476 static_pattern.sflags = PAT_SF_TREE;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100477 static_pattern.type = SMP_T_STR;
478 static_pattern.ptr.str = (char *)elt->node.key;
479 }
480 return &static_pattern;
481 }
482 }
483
484 /* look in the list */
485 list_for_each_entry(lst, &expr->patterns, list) {
486 pattern = &lst->pat;
487
488 if (pattern->len != smp->data.str.len)
489 continue;
490
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200491 icase = expr->mflags & PAT_MF_IGNORE_CASE;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100492 if ((icase && strncasecmp(pattern->ptr.str, smp->data.str.str, smp->data.str.len) == 0) ||
493 (!icase && strncmp(pattern->ptr.str, smp->data.str.str, smp->data.str.len) == 0))
494 return pattern;
495 }
496
497 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100498}
499
500/* NB: For two binaries buf to be identical, it is required that their lengths match */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100501struct pattern *pat_match_bin(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100502{
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100503 struct pattern_list *lst;
504 struct pattern *pattern;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100505
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100506 /* Look in the list. */
507 list_for_each_entry(lst, &expr->patterns, list) {
508 pattern = &lst->pat;
509
510 if (pattern->len != smp->data.str.len)
511 continue;
512
513 if (memcmp(pattern->ptr.str, smp->data.str.str, smp->data.str.len) == 0)
514 return pattern;
515 }
516
517 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100518}
519
520/* Executes a regex. It temporarily changes the data to add a trailing zero,
521 * and restores the previous character when leaving.
522 */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100523struct pattern *pat_match_reg(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100524{
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100525 struct pattern_list *lst;
526 struct pattern *pattern;
527
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100528 /* look in the list */
529 list_for_each_entry(lst, &expr->patterns, list) {
530 pattern = &lst->pat;
531
532 if (regex_exec(pattern->ptr.reg, smp->data.str.str, smp->data.str.len) == 0)
533 return pattern;
534 }
535 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100536}
537
538/* Checks that the pattern matches the beginning of the tested string. */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100539struct pattern *pat_match_beg(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100540{
541 int icase;
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +0200542 struct ebmb_node *node;
543 char prev;
544 struct pattern_tree *elt;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100545 struct pattern_list *lst;
546 struct pattern *pattern;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100547
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +0200548 /* Lookup a string in the expression's pattern tree. */
549 if (!eb_is_empty(&expr->pattern_tree)) {
550 /* we may have to force a trailing zero on the test pattern */
551 prev = smp->data.str.str[smp->data.str.len];
552 if (prev)
553 smp->data.str.str[smp->data.str.len] = '\0';
554 node = ebmb_lookup_longest(&expr->pattern_tree, smp->data.str.str);
555 if (prev)
556 smp->data.str.str[smp->data.str.len] = prev;
557
558 if (node) {
559 if (fill) {
560 elt = ebmb_entry(node, struct pattern_tree, node);
561 static_pattern.smp = elt->smp;
562 static_pattern.ref = elt->ref;
563 static_pattern.sflags = PAT_SF_TREE;
564 static_pattern.type = SMP_T_STR;
565 static_pattern.ptr.str = (char *)elt->node.key;
566 }
567 return &static_pattern;
568 }
569 }
570
571 /* look in the list */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100572 list_for_each_entry(lst, &expr->patterns, list) {
573 pattern = &lst->pat;
574
575 if (pattern->len > smp->data.str.len)
576 continue;
577
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200578 icase = expr->mflags & PAT_MF_IGNORE_CASE;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100579 if ((icase && strncasecmp(pattern->ptr.str, smp->data.str.str, pattern->len) != 0) ||
580 (!icase && strncmp(pattern->ptr.str, smp->data.str.str, pattern->len) != 0))
581 continue;
582
583 return pattern;
584 }
585 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100586}
587
588/* Checks that the pattern matches the end of the tested string. */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100589struct pattern *pat_match_end(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100590{
591 int icase;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100592 struct pattern_list *lst;
593 struct pattern *pattern;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100594
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100595 list_for_each_entry(lst, &expr->patterns, list) {
596 pattern = &lst->pat;
597
598 if (pattern->len > smp->data.str.len)
599 continue;
600
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200601 icase = expr->mflags & PAT_MF_IGNORE_CASE;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100602 if ((icase && strncasecmp(pattern->ptr.str, smp->data.str.str + smp->data.str.len - pattern->len, pattern->len) != 0) ||
603 (!icase && strncmp(pattern->ptr.str, smp->data.str.str + smp->data.str.len - pattern->len, pattern->len) != 0))
604 continue;
605
606 return pattern;
607 }
608 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100609}
610
611/* Checks that the pattern is included inside the tested string.
612 * NB: Suboptimal, should be rewritten using a Boyer-Moore method.
613 */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100614struct pattern *pat_match_sub(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100615{
616 int icase;
617 char *end;
618 char *c;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100619 struct pattern_list *lst;
620 struct pattern *pattern;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100621
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100622 list_for_each_entry(lst, &expr->patterns, list) {
623 pattern = &lst->pat;
624
625 if (pattern->len > smp->data.str.len)
626 continue;
627
628 end = smp->data.str.str + smp->data.str.len - pattern->len;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200629 icase = expr->mflags & PAT_MF_IGNORE_CASE;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100630 if (icase) {
631 for (c = smp->data.str.str; c <= end; c++) {
632 if (tolower(*c) != tolower(*pattern->ptr.str))
633 continue;
634 if (strncasecmp(pattern->ptr.str, c, pattern->len) == 0)
635 return pattern;
636 }
637 } else {
638 for (c = smp->data.str.str; c <= end; c++) {
639 if (*c != *pattern->ptr.str)
640 continue;
641 if (strncmp(pattern->ptr.str, c, pattern->len) == 0)
642 return pattern;
643 }
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100644 }
645 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100646 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100647}
648
649/* This one is used by other real functions. It checks that the pattern is
650 * included inside the tested string, but enclosed between the specified
651 * delimiters or at the beginning or end of the string. The delimiters are
652 * provided as an unsigned int made by make_4delim() and match up to 4 different
653 * delimiters. Delimiters are stripped at the beginning and end of the pattern.
654 */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200655static int match_word(struct sample *smp, struct pattern *pattern, int mflags, unsigned int delimiters)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100656{
657 int may_match, icase;
658 char *c, *end;
659 char *ps;
660 int pl;
661
662 pl = pattern->len;
663 ps = pattern->ptr.str;
664
665 while (pl > 0 && is_delimiter(*ps, delimiters)) {
666 pl--;
667 ps++;
668 }
669
670 while (pl > 0 && is_delimiter(ps[pl - 1], delimiters))
671 pl--;
672
673 if (pl > smp->data.str.len)
674 return PAT_NOMATCH;
675
676 may_match = 1;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200677 icase = mflags & PAT_MF_IGNORE_CASE;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100678 end = smp->data.str.str + smp->data.str.len - pl;
679 for (c = smp->data.str.str; c <= end; c++) {
680 if (is_delimiter(*c, delimiters)) {
681 may_match = 1;
682 continue;
683 }
684
685 if (!may_match)
686 continue;
687
688 if (icase) {
689 if ((tolower(*c) == tolower(*ps)) &&
690 (strncasecmp(ps, c, pl) == 0) &&
691 (c == end || is_delimiter(c[pl], delimiters)))
692 return PAT_MATCH;
693 } else {
694 if ((*c == *ps) &&
695 (strncmp(ps, c, pl) == 0) &&
696 (c == end || is_delimiter(c[pl], delimiters)))
697 return PAT_MATCH;
698 }
699 may_match = 0;
700 }
701 return PAT_NOMATCH;
702}
703
704/* Checks that the pattern is included inside the tested string, but enclosed
705 * between the delimiters '?' or '/' or at the beginning or end of the string.
706 * Delimiters at the beginning or end of the pattern are ignored.
707 */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100708struct pattern *pat_match_dir(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100709{
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100710 struct pattern_list *lst;
711 struct pattern *pattern;
712
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100713 list_for_each_entry(lst, &expr->patterns, list) {
714 pattern = &lst->pat;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200715 if (match_word(smp, pattern, expr->mflags, make_4delim('/', '?', '?', '?')))
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100716 return pattern;
717 }
718 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100719}
720
721/* Checks that the pattern is included inside the tested string, but enclosed
722 * between the delmiters '/', '?', '.' or ":" or at the beginning or end of
723 * the string. Delimiters at the beginning or end of the pattern are ignored.
724 */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100725struct pattern *pat_match_dom(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100726{
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100727 struct pattern_list *lst;
728 struct pattern *pattern;
729
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100730 list_for_each_entry(lst, &expr->patterns, list) {
731 pattern = &lst->pat;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200732 if (match_word(smp, pattern, expr->mflags, make_4delim('/', '?', '.', ':')))
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100733 return pattern;
734 }
735 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100736}
737
738/* Checks that the integer in <test> is included between min and max */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100739struct pattern *pat_match_int(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100740{
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100741 struct pattern_list *lst;
742 struct pattern *pattern;
743
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100744 list_for_each_entry(lst, &expr->patterns, list) {
745 pattern = &lst->pat;
746 if ((!pattern->val.range.min_set || pattern->val.range.min <= smp->data.uint) &&
747 (!pattern->val.range.max_set || smp->data.uint <= pattern->val.range.max))
748 return pattern;
749 }
750 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100751}
752
753/* Checks that the length of the pattern in <test> is included between min and max */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100754struct pattern *pat_match_len(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100755{
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100756 struct pattern_list *lst;
757 struct pattern *pattern;
758
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100759 list_for_each_entry(lst, &expr->patterns, list) {
760 pattern = &lst->pat;
761 if ((!pattern->val.range.min_set || pattern->val.range.min <= smp->data.str.len) &&
762 (!pattern->val.range.max_set || smp->data.str.len <= pattern->val.range.max))
763 return pattern;
764 }
765 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100766}
767
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100768struct pattern *pat_match_ip(struct sample *smp, struct pattern_expr *expr, int fill)
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100769{
770 unsigned int v4; /* in network byte order */
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100771 struct in6_addr tmp6;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100772 struct in_addr *s;
773 struct ebmb_node *node;
774 struct pattern_tree *elt;
775 struct pattern_list *lst;
776 struct pattern *pattern;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100777
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100778 /* The input sample is IPv4. Try to match in the trees. */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100779 if (smp->type == SMP_T_IPV4) {
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100780 /* Lookup an IPv4 address in the expression's pattern tree using
781 * the longest match method.
782 */
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100783 s = &smp->data.ipv4;
784 node = ebmb_lookup_longest(&expr->pattern_tree, &s->s_addr);
785 if (node) {
786 if (fill) {
787 elt = ebmb_entry(node, struct pattern_tree, node);
788 static_pattern.smp = elt->smp;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +0100789 static_pattern.ref = elt->ref;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200790 static_pattern.sflags = PAT_SF_TREE;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100791 static_pattern.type = SMP_T_IPV4;
792 memcpy(&static_pattern.val.ipv4.addr.s_addr, elt->node.key, 4);
793 if (!cidr2dotted(elt->node.node.pfx, &static_pattern.val.ipv4.mask))
794 return NULL;
795 }
796 return &static_pattern;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100797 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100798
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100799 /* The IPv4 sample dont match the IPv4 tree. Convert the IPv4
800 * sample address to IPv6 with the mapping method using the ::ffff:
801 * prefix, and try to lookup in the IPv6 tree.
802 */
803 memset(&tmp6, 0, 10);
804 *(uint16_t*)&tmp6.s6_addr[10] = htons(0xffff);
805 *(uint32_t*)&tmp6.s6_addr[12] = smp->data.ipv4.s_addr;
806 node = ebmb_lookup_longest(&expr->pattern_tree_2, &tmp6);
807 if (node) {
808 if (fill) {
809 elt = ebmb_entry(node, struct pattern_tree, node);
810 static_pattern.smp = elt->smp;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +0100811 static_pattern.ref = elt->ref;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200812 static_pattern.sflags = PAT_SF_TREE;
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100813 static_pattern.type = SMP_T_IPV6;
814 memcpy(&static_pattern.val.ipv6.addr, elt->node.key, 16);
815 static_pattern.val.ipv6.mask = elt->node.node.pfx;
816 }
817 return &static_pattern;
818 }
819 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100820
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100821 /* The input sample is IPv6. Try to match in the trees. */
822 if (smp->type == SMP_T_IPV6) {
823 /* Lookup an IPv6 address in the expression's pattern tree using
824 * the longest match method.
825 */
826 node = ebmb_lookup_longest(&expr->pattern_tree_2, &smp->data.ipv6);
827 if (node) {
828 if (fill) {
829 elt = ebmb_entry(node, struct pattern_tree, node);
830 static_pattern.smp = elt->smp;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +0100831 static_pattern.ref = elt->ref;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200832 static_pattern.sflags = PAT_SF_TREE;
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100833 static_pattern.type = SMP_T_IPV6;
834 memcpy(&static_pattern.val.ipv6.addr, elt->node.key, 16);
835 static_pattern.val.ipv6.mask = elt->node.node.pfx;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100836 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100837 return &static_pattern;
838 }
839
840 /* Try to convert 6 to 4 when the start of the ipv6 address match the
841 * following forms :
842 * - ::ffff:ip:v4 (ipv4 mapped)
843 * - ::0000:ip:v4 (old ipv4 mapped)
844 * - 2002:ip:v4:: (6to4)
845 */
846 if ((*(uint32_t*)&smp->data.ipv6.s6_addr[0] == 0 &&
847 *(uint32_t*)&smp->data.ipv6.s6_addr[4] == 0 &&
848 (*(uint32_t*)&smp->data.ipv6.s6_addr[8] == 0 ||
849 *(uint32_t*)&smp->data.ipv6.s6_addr[8] == htonl(0xFFFF))) ||
850 *(uint16_t*)&smp->data.ipv6.s6_addr[0] == htons(0x2002)) {
851 if (*(uint32_t*)&smp->data.ipv6.s6_addr[0] == 0)
852 v4 = *(uint32_t*)&smp->data.ipv6.s6_addr[12];
853 else
854 v4 = htonl((ntohs(*(uint16_t*)&smp->data.ipv6.s6_addr[2]) << 16) +
855 ntohs(*(uint16_t*)&smp->data.ipv6.s6_addr[4]));
856
857 /* Lookup an IPv4 address in the expression's pattern tree using the longest
858 * match method.
859 */
860 node = ebmb_lookup_longest(&expr->pattern_tree, &v4);
861 if (node) {
862 if (fill) {
863 elt = ebmb_entry(node, struct pattern_tree, node);
864 static_pattern.smp = elt->smp;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +0100865 static_pattern.ref = elt->ref;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +0200866 static_pattern.sflags = PAT_SF_TREE;
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100867 static_pattern.type = SMP_T_IPV4;
868 memcpy(&static_pattern.val.ipv4.addr.s_addr, elt->node.key, 4);
869 if (!cidr2dotted(elt->node.node.pfx, &static_pattern.val.ipv4.mask))
870 return NULL;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100871 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100872 return &static_pattern;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100873 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100874 }
875 }
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100876
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100877 /* Lookup in the list. the list contain only IPv4 patterns */
878 list_for_each_entry(lst, &expr->patterns, list) {
879 pattern = &lst->pat;
880
881 /* The input sample is IPv4, use it as is. */
882 if (smp->type == SMP_T_IPV4) {
883 v4 = smp->data.ipv4.s_addr;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100884 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100885 else if (smp->type == SMP_T_IPV6) {
886 /* v4 match on a V6 sample. We want to check at least for
887 * the following forms :
888 * - ::ffff:ip:v4 (ipv4 mapped)
889 * - ::0000:ip:v4 (old ipv4 mapped)
890 * - 2002:ip:v4:: (6to4)
891 */
892 if (*(uint32_t*)&smp->data.ipv6.s6_addr[0] == 0 &&
893 *(uint32_t*)&smp->data.ipv6.s6_addr[4] == 0 &&
894 (*(uint32_t*)&smp->data.ipv6.s6_addr[8] == 0 ||
895 *(uint32_t*)&smp->data.ipv6.s6_addr[8] == htonl(0xFFFF))) {
896 v4 = *(uint32_t*)&smp->data.ipv6.s6_addr[12];
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100897 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100898 else if (*(uint16_t*)&smp->data.ipv6.s6_addr[0] == htons(0x2002)) {
899 v4 = htonl((ntohs(*(uint16_t*)&smp->data.ipv6.s6_addr[2]) << 16) +
900 ntohs(*(uint16_t*)&smp->data.ipv6.s6_addr[4]));
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100901 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100902 else
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100903 continue;
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100904 }
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100905
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100906 /* Check if the input sample match the current pattern. */
907 if (((v4 ^ pattern->val.ipv4.addr.s_addr) & pattern->val.ipv4.mask.s_addr) == 0)
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100908 return pattern;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100909 }
Thierry FOURNIER5338eea2013-12-16 14:22:13 +0100910 return NULL;
Thierry FOURNIERe7ba2362014-01-21 11:25:41 +0100911}
912
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100913void free_pattern_tree(struct eb_root *root)
914{
915 struct eb_node *node, *next;
Thierry FOURNIERe1bcac52013-12-13 16:09:50 +0100916 struct pattern_tree *elt;
Thierry FOURNIER3ce88c72013-12-09 11:29:46 +0100917
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100918 node = eb_first(root);
919 while (node) {
920 next = eb_next(node);
921 eb_delete(node);
Thierry FOURNIERe1bcac52013-12-13 16:09:50 +0100922 elt = container_of(node, struct pattern_tree, node);
Thierry FOURNIERc64de3f2013-12-10 15:08:39 +0100923 free(elt->smp);
Thierry FOURNIER3ce88c72013-12-09 11:29:46 +0100924 free(elt);
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100925 node = next;
926 }
927}
928
Thierry FOURNIER6f7203d2014-01-14 16:24:51 +0100929void pat_prune_val(struct pattern_expr *expr)
Thierry FOURNIERd163e1c2013-11-28 11:41:23 +0100930{
Thierry FOURNIER6f7203d2014-01-14 16:24:51 +0100931 struct pattern_list *pat, *tmp;
932
933 list_for_each_entry_safe(pat, tmp, &expr->patterns, list) {
934 free(pat->pat.smp);
935 free(pat);
936 }
937
Thierry FOURNIERd163e1c2013-11-28 11:41:23 +0100938 free_pattern_tree(&expr->pattern_tree);
Thierry FOURNIER33a74332013-12-19 23:54:54 +0100939 free_pattern_tree(&expr->pattern_tree_2);
Thierry FOURNIERd163e1c2013-11-28 11:41:23 +0100940 LIST_INIT(&expr->patterns);
941}
942
Thierry FOURNIER6f7203d2014-01-14 16:24:51 +0100943void pat_prune_ptr(struct pattern_expr *expr)
944{
945 struct pattern_list *pat, *tmp;
946
947 list_for_each_entry_safe(pat, tmp, &expr->patterns, list) {
948 free(pat->pat.ptr.ptr);
949 free(pat->pat.smp);
950 free(pat);
951 }
952
953 free_pattern_tree(&expr->pattern_tree);
954 free_pattern_tree(&expr->pattern_tree_2);
955 LIST_INIT(&expr->patterns);
956}
957
958void pat_prune_reg(struct pattern_expr *expr)
959{
960 struct pattern_list *pat, *tmp;
961
962 list_for_each_entry_safe(pat, tmp, &expr->patterns, list) {
963 regex_free(pat->pat.ptr.ptr);
964 free(pat->pat.smp);
965 free(pat);
966 }
967
968 free_pattern_tree(&expr->pattern_tree);
969 free_pattern_tree(&expr->pattern_tree_2);
970 LIST_INIT(&expr->patterns);
971}
972
Thierry FOURNIERb9b08462013-12-13 15:12:32 +0100973/*
974 *
975 * The following functions are used for the pattern indexation
976 *
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100977 */
Thierry FOURNIERb9b08462013-12-13 15:12:32 +0100978
979int pat_idx_list_val(struct pattern_expr *expr, struct pattern *pat, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100980{
Thierry FOURNIERb9b08462013-12-13 15:12:32 +0100981 struct pattern_list *patl;
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100982
Thierry FOURNIERb9b08462013-12-13 15:12:32 +0100983 /* allocate pattern */
984 patl = calloc(1, sizeof(*patl));
985 if (!patl) {
986 memprintf(err, "out of memory while indexing pattern");
Thierry FOURNIER972028f2014-01-23 17:53:31 +0100987 return 0;
988 }
Thierry FOURNIERed66c292013-11-28 11:05:19 +0100989
Thierry FOURNIERb9b08462013-12-13 15:12:32 +0100990 /* duplicate pattern */
991 memcpy(&patl->pat, pat, sizeof(*pat));
Thierry FOURNIER7148ce62013-12-06 19:06:43 +0100992
Thierry FOURNIERb9b08462013-12-13 15:12:32 +0100993 /* chain pattern in the expression */
994 LIST_ADDQ(&expr->patterns, &patl->list);
995
996 /* that's ok */
997 return 1;
998}
999
1000int pat_idx_list_ptr(struct pattern_expr *expr, struct pattern *pat, char **err)
1001{
1002 struct pattern_list *patl;
1003
1004 /* allocate pattern */
1005 patl = calloc(1, sizeof(*patl));
1006 if (!patl)
Thierry FOURNIER972028f2014-01-23 17:53:31 +01001007 return 0;
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001008
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001009 /* duplicate pattern */
1010 memcpy(&patl->pat, pat, sizeof(*pat));
1011 patl->pat.ptr.ptr = malloc(patl->pat.len);
1012 if (!patl->pat.ptr.ptr) {
1013 free(patl);
1014 memprintf(err, "out of memory while indexing pattern");
1015 return 0;
1016 }
1017 memcpy(patl->pat.ptr.ptr, pat->ptr.ptr, pat->len);
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001018
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001019 /* chain pattern in the expression */
1020 LIST_ADDQ(&expr->patterns, &patl->list);
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001021
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001022 /* that's ok */
1023 return 1;
1024}
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001025
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001026int pat_idx_list_str(struct pattern_expr *expr, struct pattern *pat, char **err)
1027{
1028 struct pattern_list *patl;
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001029
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001030 /* allocate pattern */
1031 patl = calloc(1, sizeof(*patl));
1032 if (!patl) {
1033 memprintf(err, "out of memory while indexing pattern");
1034 return 0;
1035 }
1036
1037 /* duplicate pattern */
1038 memcpy(&patl->pat, pat, sizeof(*pat));
1039 patl->pat.ptr.str = malloc(patl->pat.len + 1);
1040 if (!patl->pat.ptr.str) {
1041 free(patl);
1042 memprintf(err, "out of memory while indexing pattern");
1043 return 0;
1044 }
1045 memcpy(patl->pat.ptr.ptr, pat->ptr.ptr, pat->len);
1046 patl->pat.ptr.str[patl->pat.len] = '\0';
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001047
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001048 /* chain pattern in the expression */
1049 LIST_ADDQ(&expr->patterns, &patl->list);
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001050
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001051 /* that's ok */
1052 return 1;
1053}
1054
1055int pat_idx_list_reg(struct pattern_expr *expr, struct pattern *pat, char **err)
1056{
1057 struct pattern_list *patl;
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001058
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001059 /* allocate pattern */
1060 patl = calloc(1, sizeof(*patl));
1061 if (!patl) {
1062 memprintf(err, "out of memory while indexing pattern");
1063 return 0;
Thierry FOURNIER972028f2014-01-23 17:53:31 +01001064 }
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001065
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001066 /* duplicate pattern */
1067 memcpy(&patl->pat, pat, sizeof(*pat));
1068
1069 /* allocate regex */
1070 patl->pat.ptr.reg = calloc(1, sizeof(*patl->pat.ptr.reg));
1071 if (!patl->pat.ptr.reg) {
1072 free(patl);
1073 memprintf(err, "out of memory while indexing pattern");
1074 return 0;
1075 }
1076
1077 /* compile regex */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02001078 if (!regex_comp(pat->ptr.str, patl->pat.ptr.reg, !(expr->mflags & PAT_MF_IGNORE_CASE), 0, err)) {
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001079 free(patl);
1080 free(patl->pat.ptr.reg);
1081 return 0;
1082 }
1083
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001084 /* chain pattern in the expression */
1085 LIST_ADDQ(&expr->patterns, &patl->list);
1086
1087 /* that's ok */
1088 return 1;
1089}
1090
1091int pat_idx_tree_ip(struct pattern_expr *expr, struct pattern *pat, char **err)
1092{
1093 unsigned int mask;
Thierry FOURNIERe1bcac52013-12-13 16:09:50 +01001094 struct pattern_tree *node;
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001095
1096 /* Only IPv4 can be indexed */
1097 if (pat->type == SMP_T_IPV4) {
Thierry FOURNIER972028f2014-01-23 17:53:31 +01001098 /* in IPv4 case, check if the mask is contiguous so that we can
1099 * insert the network into the tree. A continuous mask has only
1100 * ones on the left. This means that this mask + its lower bit
1101 * added once again is null.
1102 */
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001103 mask = ntohl(pat->val.ipv4.mask.s_addr);
1104 if (mask + (mask & -mask) == 0) {
1105 mask = mask ? 33 - flsnz(mask & -mask) : 0; /* equals cidr value */
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001106
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001107 /* node memory allocation */
1108 node = calloc(1, sizeof(*node) + 4);
1109 if (!node) {
1110 memprintf(err, "out of memory while loading pattern");
1111 return 0;
1112 }
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001113
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001114 /* copy the pointer to sample associated to this node */
1115 node->smp = pat->smp;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +01001116 node->ref = pat->ref;
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001117
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001118 /* FIXME: insert <addr>/<mask> into the tree here */
1119 memcpy(node->node.key, &pat->val.ipv4.addr, 4); /* network byte order */
1120 node->node.node.pfx = mask;
Thierry FOURNIER31db4ae2014-01-30 00:27:15 +01001121
1122 /* Insert the entry. */
1123 ebmb_insert_prefix(&expr->pattern_tree, &node->node, 4);
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001124
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001125 /* that's ok */
1126 return 1;
1127 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001128 else {
1129 /* If the mask is not contiguous, just add the pattern to the list */
1130 return pat_idx_list_val(expr, pat, err);
1131 }
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001132 }
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001133 else if (pat->type == SMP_T_IPV6) {
1134 /* IPv6 also can be indexed */
1135 node = calloc(1, sizeof(*node) + 16);
1136 if (!node) {
1137 memprintf(err, "out of memory while loading pattern");
1138 return 0;
1139 }
1140
1141 /* copy the pointer to sample associated to this node */
1142 node->smp = pat->smp;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +01001143 node->ref = pat->ref;
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001144
1145 /* FIXME: insert <addr>/<mask> into the tree here */
1146 memcpy(node->node.key, &pat->val.ipv6.addr, 16); /* network byte order */
1147 node->node.node.pfx = pat->val.ipv6.mask;
Thierry FOURNIER31db4ae2014-01-30 00:27:15 +01001148
1149 /* Insert the entry. */
1150 ebmb_insert_prefix(&expr->pattern_tree_2, &node->node, 16);
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001151
1152 /* that's ok */
1153 return 1;
1154 }
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001155
Thierry FOURNIER33a74332013-12-19 23:54:54 +01001156 return 0;
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001157}
1158
1159int pat_idx_tree_str(struct pattern_expr *expr, struct pattern *pat, char **err)
1160{
1161 int len;
Thierry FOURNIERe1bcac52013-12-13 16:09:50 +01001162 struct pattern_tree *node;
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001163
1164 /* Only string can be indexed */
Thierry FOURNIER7654c9f2013-12-17 00:20:33 +01001165 if (pat->type != SMP_T_STR) {
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001166 memprintf(err, "internal error: string expected, but the type is '%s'",
1167 smp_to_type[pat->type]);
1168 return 0;
Thierry FOURNIER972028f2014-01-23 17:53:31 +01001169 }
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001170
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001171 /* If the flag PAT_F_IGNORE_CASE is set, we cannot use trees */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02001172 if (expr->mflags & PAT_MF_IGNORE_CASE)
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001173 return pat_idx_list_str(expr, pat, err);
Thierry FOURNIER7148ce62013-12-06 19:06:43 +01001174
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001175 /* Process the key len */
1176 len = strlen(pat->ptr.str) + 1;
1177
1178 /* node memory allocation */
1179 node = calloc(1, sizeof(*node) + len);
1180 if (!node) {
1181 memprintf(err, "out of memory while loading pattern");
1182 return 0;
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001183 }
1184
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001185 /* copy the pointer to sample associated to this node */
1186 node->smp = pat->smp;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +01001187 node->ref = pat->ref;
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001188
1189 /* copy the string */
1190 memcpy(node->node.key, pat->ptr.str, len);
1191
1192 /* index the new node */
Thierry FOURNIER31db4ae2014-01-30 00:27:15 +01001193 ebst_insert(&expr->pattern_tree, &node->node);
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001194
1195 /* that's ok */
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001196 return 1;
1197}
1198
Willy Tarreaub1dd9bf2014-05-10 08:53:48 +02001199int pat_idx_tree_pfx(struct pattern_expr *expr, struct pattern *pat, char **err)
1200{
1201 int len;
1202 struct pattern_tree *node;
1203
1204 /* Only string can be indexed */
1205 if (pat->type != SMP_T_STR) {
1206 memprintf(err, "internal error: string expected, but the type is '%s'",
1207 smp_to_type[pat->type]);
1208 return 0;
1209 }
1210
1211 /* If the flag PAT_F_IGNORE_CASE is set, we cannot use trees */
1212 if (expr->mflags & PAT_MF_IGNORE_CASE)
1213 return pat_idx_list_str(expr, pat, err);
1214
1215 /* Process the key len */
1216 len = strlen(pat->ptr.str);
1217
1218 /* node memory allocation */
1219 node = calloc(1, sizeof(*node) + len + 1);
1220 if (!node) {
1221 memprintf(err, "out of memory while loading pattern");
1222 return 0;
1223 }
1224
1225 /* copy the pointer to sample associated to this node */
1226 node->smp = pat->smp;
1227 node->ref = pat->ref;
1228
1229 /* copy the string and the trailing zero */
1230 memcpy(node->node.key, pat->ptr.str, len + 1);
1231 node->node.node.pfx = len * 8;
1232
1233 /* index the new node */
1234 ebmb_insert_prefix(&expr->pattern_tree, &node->node, len);
1235
1236 /* that's ok */
1237 return 1;
1238}
1239
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001240void pat_del_list_val(struct pattern_expr *expr, struct pat_ref_elt *ref)
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001241{
1242 struct pattern_list *pat;
1243 struct pattern_list *safe;
1244
1245 list_for_each_entry_safe(pat, safe, &expr->patterns, list) {
1246 /* Check equality. */
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001247 if (pat->pat.ref != ref)
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001248 continue;
1249
1250 /* Delete and free entry. */
1251 LIST_DEL(&pat->list);
1252 free(pat->pat.smp);
1253 free(pat);
1254 }
1255}
1256
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001257void pat_del_tree_ip(struct pattern_expr *expr, struct pat_ref_elt *ref)
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001258{
1259 struct ebmb_node *node, *next_node;
1260 struct pattern_tree *elt;
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001261
1262 /* browse each node of the tree for IPv4 addresses. */
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001263 for (node = ebmb_first(&expr->pattern_tree), next_node = node ? ebmb_next(node) : NULL;
1264 node;
1265 node = next_node, next_node = node ? ebmb_next(node) : NULL) {
1266 /* Extract container of the tree node. */
1267 elt = container_of(node, struct pattern_tree, node);
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001268
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001269 /* Check equality. */
1270 if (elt->ref != ref)
1271 continue;
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001272
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001273 /* Delete and free entry. */
1274 ebmb_delete(node);
1275 free(elt->smp);
1276 free(elt);
1277 }
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001278
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001279 /* Browse each node of the list for IPv4 addresses. */
1280 pat_del_list_val(expr, ref);
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001281
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001282 /* browse each node of the tree for IPv6 addresses. */
1283 for (node = ebmb_first(&expr->pattern_tree_2), next_node = node ? ebmb_next(node) : NULL;
1284 node;
1285 node = next_node, next_node = node ? ebmb_next(node) : NULL) {
1286 /* Extract container of the tree node. */
1287 elt = container_of(node, struct pattern_tree, node);
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001288
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001289 /* Check equality. */
1290 if (elt->ref != ref)
1291 continue;
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001292
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001293 /* Delete and free entry. */
1294 ebmb_delete(node);
1295 free(elt->smp);
1296 free(elt);
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001297 }
1298}
1299
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001300void pat_del_list_ptr(struct pattern_expr *expr, struct pat_ref_elt *ref)
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001301{
1302 struct pattern_list *pat;
1303 struct pattern_list *safe;
1304
1305 list_for_each_entry_safe(pat, safe, &expr->patterns, list) {
1306 /* Check equality. */
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001307 if (pat->pat.ref != ref)
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001308 continue;
1309
1310 /* Delete and free entry. */
1311 LIST_DEL(&pat->list);
1312 free(pat->pat.ptr.ptr);
1313 free(pat->pat.smp);
1314 free(pat);
1315 }
1316}
1317
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001318void pat_del_tree_str(struct pattern_expr *expr, struct pat_ref_elt *ref)
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001319{
1320 struct ebmb_node *node, *next_node;
1321 struct pattern_tree *elt;
1322
1323 /* browse each node of the tree. */
1324 for (node = ebmb_first(&expr->pattern_tree), next_node = node ? ebmb_next(node) : NULL;
1325 node;
1326 node = next_node, next_node = node ? ebmb_next(node) : NULL) {
1327 /* Extract container of the tree node. */
1328 elt = container_of(node, struct pattern_tree, node);
1329
1330 /* Check equality. */
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001331 if (elt->ref != ref)
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001332 continue;
1333
1334 /* Delete and free entry. */
1335 ebmb_delete(node);
1336 free(elt->smp);
1337 free(elt);
1338 }
1339}
1340
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001341void pat_del_list_reg(struct pattern_expr *expr, struct pat_ref_elt *ref)
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001342{
1343 struct pattern_list *pat;
1344 struct pattern_list *safe;
1345
1346 list_for_each_entry_safe(pat, safe, &expr->patterns, list) {
1347 /* Check equality. */
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001348 if (pat->pat.ref != ref)
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001349 continue;
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001350
1351 /* Delete and free entry. */
1352 LIST_DEL(&pat->list);
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001353 regex_free(pat->pat.ptr.ptr);
1354 free(pat->pat.smp);
1355 free(pat);
1356 }
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001357}
1358
1359void pattern_init_expr(struct pattern_expr *expr)
1360{
1361 LIST_INIT(&expr->patterns);
Thierry FOURNIER31db4ae2014-01-30 00:27:15 +01001362 expr->pattern_tree = EB_ROOT;
1363 expr->pattern_tree_2 = EB_ROOT;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001364}
1365
1366void pattern_init_head(struct pattern_head *head)
1367{
1368 LIST_INIT(&head->head);
1369}
1370
1371/* The following functions are relative to the management of the reference
1372 * lists. These lists are used to store the original pattern and associated
1373 * value as string form.
1374 *
1375 * This is used with modifiable ACL and MAPS
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001376 *
1377 * The pattern reference are stored with two identifiers: the unique_id and
1378 * the reference.
1379 *
1380 * The reference identify a file. Each file with the same name point to the
1381 * same reference. We can register many times one file. If the file is modified,
1382 * all his dependencies are also modified. The reference can be used with map or
1383 * acl.
1384 *
1385 * The unique_id identify inline acl. The unique id is unique for each acl.
1386 * You cannot force the same id in the configuration file, because this repoort
1387 * an error.
1388 *
1389 * A particular case appears if the filename is a number. In this case, the
1390 * unique_id is set with the number represented by the filename and the
1391 * reference is also set. This method prevent double unique_id.
1392 *
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001393 */
1394
1395/* This function lookup for reference. If the reference is found, they return
1396 * pointer to the struct pat_ref, else return NULL.
1397 */
1398struct pat_ref *pat_ref_lookup(const char *reference)
1399{
1400 struct pat_ref *ref;
1401
1402 list_for_each_entry(ref, &pattern_reference, list)
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001403 if (ref->reference && strcmp(reference, ref->reference) == 0)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001404 return ref;
1405 return NULL;
1406}
1407
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001408/* This function lookup for unique id. If the reference is found, they return
1409 * pointer to the struct pat_ref, else return NULL.
1410 */
1411struct pat_ref *pat_ref_lookupid(int unique_id)
1412{
1413 struct pat_ref *ref;
1414
1415 list_for_each_entry(ref, &pattern_reference, list)
1416 if (ref->unique_id == unique_id)
1417 return ref;
1418 return NULL;
1419}
1420
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001421/* This function remove all pattern matching the pointer <refelt> from
1422 * the the reference and from each expr member of the reference. This
1423 * function returns 1 if the deletion is done and return 0 is the entry
1424 * is not found.
1425 */
1426int pat_ref_delete_by_id(struct pat_ref *ref, struct pat_ref_elt *refelt)
1427{
1428 struct pattern_expr *expr;
1429 struct pat_ref_elt *elt, *safe;
1430
1431 /* delete pattern from reference */
1432 list_for_each_entry_safe(elt, safe, &ref->head, list) {
1433 if (elt == refelt) {
1434 LIST_DEL(&elt->list);
1435 free(elt->sample);
1436 free(elt->pattern);
1437 free(elt);
1438
1439 list_for_each_entry(expr, &ref->pat, list)
1440 pattern_delete(expr, elt);
1441
1442 return 1;
1443 }
1444 }
1445 return 0;
1446}
1447
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001448/* This function remove all pattern match <key> from the the reference
1449 * and from each expr member of the reference. This fucntion returns 1
1450 * if the deletion is done and return 0 is the entry is not found.
1451 */
1452int pat_ref_delete(struct pat_ref *ref, const char *key)
1453{
1454 struct pattern_expr *expr;
1455 struct pat_ref_elt *elt, *safe;
1456 int found = 0;
1457
1458 /* delete pattern from reference */
1459 list_for_each_entry_safe(elt, safe, &ref->head, list) {
1460 if (strcmp(key, elt->pattern) == 0) {
1461 LIST_DEL(&elt->list);
1462 free(elt->sample);
1463 free(elt->pattern);
1464 free(elt);
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001465
1466 list_for_each_entry(expr, &ref->pat, list)
1467 pattern_delete(expr, elt);
1468
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001469 found = 1;
1470 }
1471 }
1472
1473 if (!found)
1474 return 0;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001475 return 1;
1476}
1477
Baptiste Assmann953f74d2014-04-25 16:57:03 +02001478/*
1479 * find and return an element <elt> matching <key> in a reference <ref>
1480 * return NULL if not found
1481 */
1482struct pat_ref_elt *pat_ref_find_elt(struct pat_ref *ref, const char *key)
1483{
1484 struct pat_ref_elt *elt;
1485
1486 list_for_each_entry(elt, &ref->head, list) {
1487 if (strcmp(key, elt->pattern) == 0)
1488 return elt;
1489 }
1490
1491 return NULL;
1492}
1493
1494
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001495 /* This function modify the sample of the first pattern that match the <key>. */
1496static inline int pat_ref_set_elt(struct pat_ref *ref, struct pat_ref_elt *elt,
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001497 const char *value, char **err)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001498{
1499 struct pattern_expr *expr;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001500 struct sample_storage **smp;
1501 char *sample;
Thierry FOURNIER149e0fe2014-01-29 19:35:06 +01001502 struct sample_storage test;
1503
1504 /* Try all needed converters. */
1505 list_for_each_entry(expr, &ref->pat, list) {
1506 if (!expr->pat_head->parse_smp)
1507 continue;
1508
1509 if (!expr->pat_head->parse_smp(value, &test)) {
1510 memprintf(err, "unable to parse '%s'", value);
1511 return 0;
1512 }
1513 }
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001514
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001515 /* Modify pattern from reference. */
1516 sample = strdup(value);
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001517 if (!sample) {
1518 memprintf(err, "out of memory error");
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001519 return 0;
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001520 }
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001521 free(elt->sample);
1522 elt->sample = sample;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001523
Thierry FOURNIER149e0fe2014-01-29 19:35:06 +01001524 /* Load sample in each reference. All the conversion are tested
1525 * below, normally these calls dosn't fail.
1526 */
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01001527 list_for_each_entry(expr, &ref->pat, list) {
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001528 if (!expr->pat_head->parse_smp)
1529 continue;
1530
1531 smp = pattern_find_smp(expr, elt);
Thierry FOURNIER149e0fe2014-01-29 19:35:06 +01001532 if (smp && *smp && !expr->pat_head->parse_smp(sample, *smp))
1533 *smp = NULL;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001534 }
1535
Thierry FOURNIER149e0fe2014-01-29 19:35:06 +01001536 return 1;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001537}
1538
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001539/* This function modify the sample of the first pattern that match the <key>. */
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001540int 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 +01001541{
1542 struct pat_ref_elt *elt;
1543
1544 /* Look for pattern in the reference. */
1545 list_for_each_entry(elt, &ref->head, list) {
1546 if (elt == refelt) {
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001547 if (!pat_ref_set_elt(ref, elt, value, err))
1548 return 0;
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001549 return 1;
1550 }
1551 }
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001552
1553 memprintf(err, "key or pattern not found");
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001554 return 0;
1555}
1556
1557/* This function modify the sample of the first pattern that match the <key>. */
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001558int pat_ref_set(struct pat_ref *ref, const char *key, const char *value, char **err)
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001559{
1560 struct pat_ref_elt *elt;
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001561 int found = 0;
1562 char *_merr;
1563 char **merr;
1564
1565 if (err) {
1566 merr = &_merr;
1567 *merr = NULL;
1568 }
1569 else
1570 merr = NULL;
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001571
1572 /* Look for pattern in the reference. */
1573 list_for_each_entry(elt, &ref->head, list) {
1574 if (strcmp(key, elt->pattern) == 0) {
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001575 if (!pat_ref_set_elt(ref, elt, value, merr)) {
1576 if (!found)
1577 *err = *merr;
1578 else {
1579 memprintf(err, "%s, %s", *err, *merr);
1580 free(*merr);
1581 *merr = NULL;
1582 }
1583 }
1584 found = 1;
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001585 }
1586 }
Thierry FOURNIER364cfdf2014-01-29 19:08:49 +01001587
1588 if (!found) {
1589 memprintf(err, "entry not found");
1590 return 0;
1591 }
1592 return 1;
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01001593}
1594
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001595/* This function create new reference. <ref> is the reference name.
1596 * <flags> are PAT_REF_*. /!\ The reference is not checked, and must
1597 * be unique. The user must check the reference with "pat_ref_lookup()"
1598 * before calling this function. If the fucntion fail, it return NULL,
1599 * else return new struct pat_ref.
1600 */
Thierry FOURNIER0d6ba512014-02-11 03:31:34 +01001601struct pat_ref *pat_ref_new(const char *reference, const char *display, unsigned int flags)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001602{
1603 struct pat_ref *ref;
1604
1605 ref = malloc(sizeof(*ref));
1606 if (!ref)
1607 return NULL;
1608
Thierry FOURNIER0d6ba512014-02-11 03:31:34 +01001609 if (display) {
1610 ref->display = strdup(display);
1611 if (!ref->display) {
1612 free(ref);
1613 return NULL;
1614 }
1615 }
1616 else
1617 ref->display = NULL;
1618
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001619 ref->reference = strdup(reference);
1620 if (!ref->reference) {
Thierry FOURNIER0d6ba512014-02-11 03:31:34 +01001621 free(ref->display);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001622 free(ref);
1623 return NULL;
1624 }
1625
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001626 ref->flags = flags;
1627 ref->unique_id = -1;
1628
1629 LIST_INIT(&ref->head);
1630 LIST_INIT(&ref->pat);
1631
1632 LIST_ADDQ(&pattern_reference, &ref->list);
1633
1634 return ref;
1635}
1636
1637/* This function create new reference. <unique_id> is the unique id. If
1638 * the value of <unique_id> is -1, the unique id is calculated later.
1639 * <flags> are PAT_REF_*. /!\ The reference is not checked, and must
1640 * be unique. The user must check the reference with "pat_ref_lookup()"
1641 * or pat_ref_lookupid before calling this function. If the function
1642 * fail, it return NULL, else return new struct pat_ref.
1643 */
Thierry FOURNIER0d6ba512014-02-11 03:31:34 +01001644struct pat_ref *pat_ref_newid(int unique_id, const char *display, unsigned int flags)
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001645{
1646 struct pat_ref *ref;
1647
1648 ref = malloc(sizeof(*ref));
1649 if (!ref)
1650 return NULL;
1651
Thierry FOURNIER0d6ba512014-02-11 03:31:34 +01001652 if (display) {
1653 ref->display = strdup(display);
1654 if (!ref->display) {
1655 free(ref);
1656 return NULL;
1657 }
1658 }
1659 else
1660 ref->display = NULL;
1661
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001662 ref->reference = NULL;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001663 ref->flags = flags;
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01001664 ref->unique_id = unique_id;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001665 LIST_INIT(&ref->head);
1666 LIST_INIT(&ref->pat);
1667
1668 LIST_ADDQ(&pattern_reference, &ref->list);
1669
1670 return ref;
1671}
1672
1673/* This function adds entry to <ref>. It can failed with memory error.
1674 * If the function fails, it returns 0.
1675 */
1676int pat_ref_append(struct pat_ref *ref, char *pattern, char *sample, int line)
1677{
1678 struct pat_ref_elt *elt;
1679
1680 elt = malloc(sizeof(*elt));
1681 if (!elt)
1682 return 0;
1683
1684 elt->line = line;
1685
1686 elt->pattern = strdup(pattern);
1687 if (!elt->pattern) {
1688 free(elt);
1689 return 0;
1690 }
1691
1692 if (sample) {
1693 elt->sample = strdup(sample);
1694 if (!elt->sample) {
1695 free(elt->pattern);
1696 free(elt);
1697 return 0;
1698 }
1699 }
1700 else
1701 elt->sample = NULL;
1702
1703 LIST_ADDQ(&ref->head, &elt->list);
1704
1705 return 1;
Thierry FOURNIERb1136502014-01-15 11:38:49 +01001706}
1707
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001708/* This function create sample found in <elt>, parse the pattern also
1709 * found in <elt> and insert it in <expr>. The function copy <patflags>
1710 * in <expr>. If the function fails, it returns0 and <err> is filled.
1711 * In succes case, the function returns 1.
1712 */
1713static inline
1714int pat_ref_push(struct pat_ref_elt *elt, struct pattern_expr *expr,
1715 int patflags, char **err)
1716{
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001717 struct sample_storage *smp;
Thierry FOURNIERd25c8422014-01-28 15:34:35 +01001718 struct pattern pattern;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001719
1720 /* Create sample */
1721 if (elt->sample && expr->pat_head->parse_smp) {
1722 /* New sample. */
1723 smp = malloc(sizeof(*smp));
1724 if (!smp)
1725 return 0;
1726
1727 /* Parse value. */
1728 if (!expr->pat_head->parse_smp(elt->sample, smp)) {
1729 memprintf(err, "unable to parse '%s'", elt->sample);
1730 free(smp);
1731 return 0;
1732 }
1733
1734 }
1735 else
1736 smp = NULL;
1737
Thierry FOURNIERd25c8422014-01-28 15:34:35 +01001738 /* initialise pattern */
1739 memset(&pattern, 0, sizeof(pattern));
Thierry FOURNIERd25c8422014-01-28 15:34:35 +01001740 pattern.smp = smp;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +01001741 pattern.ref = elt;
Thierry FOURNIERd25c8422014-01-28 15:34:35 +01001742
1743 /* parse pattern */
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02001744 if (!expr->pat_head->parse(elt->pattern, &pattern, expr->mflags, err)) {
Thierry FOURNIERd25c8422014-01-28 15:34:35 +01001745 free(smp);
1746 return 0;
1747 }
1748
1749 /* index pattern */
1750 if (!expr->pat_head->index(expr, &pattern, err)) {
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001751 free(smp);
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001752 return 0;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001753 }
Thierry FOURNIERb9b08462013-12-13 15:12:32 +01001754
1755 return 1;
1756}
1757
Thierry FOURNIER31db4ae2014-01-30 00:27:15 +01001758/* This function adds entry to <ref>. It can failed with memory error. The new
1759 * entry is added at all the pattern_expr registered in this reference. The
1760 * function stop on the first error encountered. It returns 0 and err is
1761 * filled. If an error is encountered, the complete add operation is cancelled.
1762 * If the insertion is a success the function returns 1.
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001763 */
1764int pat_ref_add(struct pat_ref *ref,
1765 const char *pattern, const char *sample,
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02001766 char **err)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001767{
1768 struct pat_ref_elt *elt;
1769 struct pattern_expr *expr;
1770
1771 elt = malloc(sizeof(*elt));
1772 if (!elt) {
1773 memprintf(err, "out of memory error");
1774 return 0;
1775 }
1776
1777 elt->line = -1;
1778
1779 elt->pattern = strdup(pattern);
1780 if (!elt->pattern) {
1781 free(elt);
1782 memprintf(err, "out of memory error");
1783 return 0;
1784 }
1785
1786 if (sample) {
1787 elt->sample = strdup(sample);
1788 if (!elt->sample) {
1789 free(elt->pattern);
1790 free(elt);
1791 memprintf(err, "out of memory error");
1792 return 0;
1793 }
1794 }
1795 else
1796 elt->sample = NULL;
1797
1798 LIST_ADDQ(&ref->head, &elt->list);
1799
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01001800 list_for_each_entry(expr, &ref->pat, list) {
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02001801 if (!pat_ref_push(elt, expr, 0, err)) {
Thierry FOURNIER31db4ae2014-01-30 00:27:15 +01001802 /* If the insertion fails, try to delete all the added entries. */
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01001803 pat_ref_delete_by_id(ref, elt);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001804 return 0;
1805 }
1806 }
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001807 return 1;
1808}
1809
Thierry FOURNIER46006bd2014-03-21 21:45:15 +01001810/* This function prune <ref>, replace all reference by the references
1811 * of <replace>, and reindex all the news values.
1812 *
1813 * The pattern are loaded in best effort and the errors are ignored,
1814 * but writed in the logs.
1815 */
1816void pat_ref_reload(struct pat_ref *ref, struct pat_ref *replace)
1817{
1818 struct pattern_expr *expr;
1819 struct pat_ref_elt *elt;
1820 char *err = NULL;
1821
1822 pat_ref_prune(ref);
1823
1824 LIST_ADD(&replace->head, &ref->head);
1825 LIST_DEL(&replace->head);
1826
1827 list_for_each_entry(elt, &ref->head, list) {
1828 list_for_each_entry(expr, &ref->pat, list) {
1829 if (!pat_ref_push(elt, expr, 0, &err)) {
1830 send_log(NULL, LOG_NOTICE, "%s", err);
1831 free(err);
1832 err = NULL;
1833 }
1834 }
1835 }
1836}
1837
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001838/* This function prune all entries of <ref>. This function
1839 * prune the associated pattern_expr.
1840 */
1841void pat_ref_prune(struct pat_ref *ref)
1842{
1843 struct pat_ref_elt *elt, *safe;
1844 struct pattern_expr *expr;
1845
1846 list_for_each_entry_safe(elt, safe, &ref->head, list) {
1847 LIST_DEL(&elt->list);
1848 free(elt->pattern);
1849 free(elt->sample);
1850 free(elt);
1851 }
1852
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01001853 list_for_each_entry(expr, &ref->pat, list)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001854 expr->pat_head->prune(expr);
1855}
1856
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001857/* This function lookup for existing reference <ref> in pattern_head <head>. */
1858struct pattern_expr *pattern_lookup_expr(struct pattern_head *head, struct pat_ref *ref)
1859{
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01001860 struct pattern_expr_list *expr;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001861
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01001862 list_for_each_entry(expr, &head->head, list)
1863 if (expr->expr->ref == ref)
1864 return expr->expr;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001865 return NULL;
1866}
1867
1868/* This function create new pattern_expr associated to the reference <ref>.
1869 * <ref> can be NULL. If an error is occured, the function returns NULL and
1870 * <err> is filled. Otherwise, the function returns new pattern_expr linked
1871 * with <head> and <ref>.
1872 */
1873struct pattern_expr *pattern_new_expr(struct pattern_head *head, struct pat_ref *ref, char **err)
1874{
1875 struct pattern_expr *expr;
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01001876 struct pattern_expr_list *list;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001877
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01001878 /* Memory and initialization of the chain element. */
1879 list = malloc(sizeof(*list));
1880 if (!list) {
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001881 memprintf(err, "out of memory");
1882 return NULL;
1883 }
1884
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01001885 /* Look for existing similar expr. No that only the index, parse and
1886 * parse_smp function must be identical for having similar pattern.
1887 * The other function depends of theses first.
1888 */
1889 if (ref) {
1890 list_for_each_entry(expr, &ref->pat, list)
1891 if (expr->pat_head->index == head->index &&
1892 expr->pat_head->parse == head->parse &&
1893 expr->pat_head->parse_smp == head->parse_smp)
1894 break;
1895 if (&expr->list == &ref->pat)
1896 expr = NULL;
1897 }
1898 else
1899 expr = NULL;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001900
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01001901 /* If no similar expr was found, we create new expr. */
1902 if (!expr) {
1903 /* Get a lot of memory for the expr struct. */
1904 expr = malloc(sizeof(*expr));
1905 if (!expr) {
1906 memprintf(err, "out of memory");
1907 return NULL;
1908 }
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001909
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01001910 /* Initialize this new expr. */
1911 pattern_init_expr(expr);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001912
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01001913 /* This new pattern expression reference one of his heads. */
1914 expr->pat_head = head;
1915
1916 /* Link with ref, or to self to facilitate LIST_DEL() */
1917 if (ref)
1918 LIST_ADDQ(&ref->pat, &expr->list);
1919 else
1920 LIST_INIT(&expr->list);
1921
1922 expr->ref = ref;
1923
1924 /* We must free this pattern if it is no more used. */
1925 list->do_free = 1;
1926 }
1927 else {
1928 /* If the pattern used already exists, it is already linked
1929 * with ref and we must not free it.
1930 */
1931 list->do_free = 0;
1932 }
1933
1934 /* The new list element reference the pattern_expr. */
1935 list->expr = expr;
1936
1937 /* Link the list element with the pattern_head. */
1938 LIST_ADDQ(&head->head, &list->list);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01001939 return expr;
1940}
1941
Thierry FOURNIERed66c292013-11-28 11:05:19 +01001942/* Reads patterns from a file. If <err_msg> is non-NULL, an error message will
1943 * be returned there on errors and the caller will have to free it.
Thierry FOURNIER39bef452014-01-29 13:29:45 +01001944 *
1945 * The file contains one key + value per line. Lines which start with '#' are
1946 * ignored, just like empty lines. Leading tabs/spaces are stripped. The key is
1947 * then the first "word" (series of non-space/tabs characters), and the value is
1948 * what follows this series of space/tab till the end of the line excluding
1949 * trailing spaces/tabs.
1950 *
1951 * Example :
1952 *
1953 * # this is a comment and is ignored
1954 * 62.212.114.60 1wt.eu \n
1955 * <-><-----------><---><----><---->
1956 * | | | | `--- trailing spaces ignored
1957 * | | | `-------- value
1958 * | | `--------------- middle spaces ignored
1959 * | `------------------------ key
1960 * `-------------------------------- leading spaces ignored
1961 *
1962 * Return non-zero in case of succes, otherwise 0.
1963 */
1964int pat_ref_read_from_file_smp(struct pat_ref *ref, const char *filename, char **err)
1965{
1966 FILE *file;
1967 char *c;
1968 int ret = 0;
1969 int line = 0;
1970 char *key_beg;
1971 char *key_end;
1972 char *value_beg;
1973 char *value_end;
1974
1975 file = fopen(filename, "r");
1976 if (!file) {
1977 memprintf(err, "failed to open pattern file <%s>", filename);
1978 return 0;
1979 }
1980
1981 /* now parse all patterns. The file may contain only one pattern
1982 * followed by one value per line. The start spaces, separator spaces
1983 * and and spaces are stripped. Each can contain comment started by '#'
1984 */
1985 while (fgets(trash.str, trash.size, file) != NULL) {
1986 line++;
1987 c = trash.str;
1988
1989 /* ignore lines beginning with a dash */
1990 if (*c == '#')
1991 continue;
1992
1993 /* strip leading spaces and tabs */
1994 while (*c == ' ' || *c == '\t')
1995 c++;
1996
1997 /* empty lines are ignored too */
1998 if (*c == '\0' || *c == '\r' || *c == '\n')
1999 continue;
2000
2001 /* look for the end of the key */
2002 key_beg = c;
2003 while (*c && *c != ' ' && *c != '\t' && *c != '\n' && *c != '\r')
2004 c++;
2005
2006 key_end = c;
2007
2008 /* strip middle spaces and tabs */
2009 while (*c == ' ' || *c == '\t')
2010 c++;
2011
2012 /* look for the end of the value, it is the end of the line */
2013 value_beg = c;
2014 while (*c && *c != '\n' && *c != '\r')
2015 c++;
2016 value_end = c;
2017
2018 /* trim possibly trailing spaces and tabs */
2019 while (value_end > value_beg && (value_end[-1] == ' ' || value_end[-1] == '\t'))
2020 value_end--;
2021
2022 /* set final \0 and check entries */
2023 *key_end = '\0';
2024 *value_end = '\0';
2025
2026 /* insert values */
2027 if (!pat_ref_append(ref, key_beg, value_beg, line)) {
2028 memprintf(err, "out of memory");
2029 goto out_close;
2030 }
2031 }
2032
2033 /* succes */
2034 ret = 1;
2035
2036 out_close:
2037 fclose(file);
2038 return ret;
2039}
2040
2041/* Reads patterns from a file. If <err_msg> is non-NULL, an error message will
2042 * be returned there on errors and the caller will have to free it.
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002043 */
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002044int pat_ref_read_from_file(struct pat_ref *ref, const char *filename, char **err)
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002045{
2046 FILE *file;
2047 char *c;
2048 char *arg;
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002049 int ret = 0;
2050 int line = 0;
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002051
2052 file = fopen(filename, "r");
2053 if (!file) {
2054 memprintf(err, "failed to open pattern file <%s>", filename);
2055 return 0;
2056 }
2057
2058 /* now parse all patterns. The file may contain only one pattern per
2059 * line. If the line contains spaces, they will be part of the pattern.
2060 * The pattern stops at the first CR, LF or EOF encountered.
2061 */
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002062 while (fgets(trash.str, trash.size, file) != NULL) {
2063 line++;
2064 c = trash.str;
2065
2066 /* ignore lines beginning with a dash */
2067 if (*c == '#')
2068 continue;
2069
2070 /* strip leading spaces and tabs */
2071 while (*c == ' ' || *c == '\t')
2072 c++;
2073
2074
2075 arg = c;
2076 while (*c && *c != '\n' && *c != '\r')
2077 c++;
2078 *c = 0;
2079
2080 /* empty lines are ignored too */
2081 if (c == arg)
2082 continue;
2083
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002084 if (!pat_ref_append(ref, arg, NULL, line)) {
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002085 memprintf(err, "out of memory when loading patterns from file <%s>", filename);
2086 goto out_close;
2087 }
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002088 }
2089
2090 ret = 1; /* success */
2091
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002092 out_close:
2093 fclose(file);
2094 return ret;
2095}
2096
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002097int pattern_read_from_file(struct pattern_head *head, unsigned int refflags,
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002098 const char *filename, int patflags, int load_smp,
Thierry FOURNIER94580c92014-02-11 14:36:45 +01002099 char **err, const char *file, int line)
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002100{
2101 struct pat_ref *ref;
2102 struct pattern_expr *expr;
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002103 struct pat_ref_elt *elt;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002104
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002105 /* Lookup for the existing reference. */
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002106 ref = pat_ref_lookup(filename);
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002107
2108 /* If the reference doesn't exists, create it and load associated file. */
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002109 if (!ref) {
Thierry FOURNIER94580c92014-02-11 14:36:45 +01002110 chunk_printf(&trash,
2111 "pattern loaded from file '%s' used by %s at file '%s' line %d",
2112 filename, refflags & PAT_REF_MAP ? "map" : "acl", file, line);
2113
2114 ref = pat_ref_new(filename, trash.str, refflags);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002115 if (!ref) {
2116 memprintf(err, "out of memory");
2117 return 0;
2118 }
2119
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002120 if (load_smp) {
Thierry FOURNIERc0bd9102014-01-29 12:32:58 +01002121 ref->flags |= PAT_REF_SMP;
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002122 if (!pat_ref_read_from_file_smp(ref, filename, err))
2123 return 0;
2124 }
2125 else {
2126 if (!pat_ref_read_from_file(ref, filename, err))
2127 return 0;
2128 }
2129 }
2130 else {
Thierry FOURNIERc0bd9102014-01-29 12:32:58 +01002131 /* The reference already exists, check the map compatibility. */
2132
2133 /* If the load require samples and the flag PAT_REF_SMP is not set,
2134 * the reference doesn't contain sample, and cannot be used.
2135 */
2136 if (load_smp) {
2137 if (!(ref->flags & PAT_REF_SMP)) {
2138 memprintf(err, "The file \"%s\" is already used as one column file "
2139 "and cannot be used by as two column file.",
2140 filename);
2141 return 0;
2142 }
2143 }
2144 else {
2145 /* The load doesn't require samples. If the flag PAT_REF_SMP is
2146 * set, the reference contains a sample, and cannot be used.
2147 */
2148 if (ref->flags & PAT_REF_SMP) {
2149 memprintf(err, "The file \"%s\" is already used as two column file "
2150 "and cannot be used by as one column file.",
2151 filename);
2152 return 0;
2153 }
2154 }
2155
Thierry FOURNIER94580c92014-02-11 14:36:45 +01002156 /* Extends display */
2157 chunk_printf(&trash, "%s", ref->display);
2158 chunk_appendf(&trash, ", by %s at file '%s' line %d",
2159 refflags & PAT_REF_MAP ? "map" : "acl", file, line);
2160 free(ref->display);
2161 ref->display = strdup(trash.str);
2162 if (!ref->display) {
2163 memprintf(err, "out of memory");
2164 return 0;
2165 }
2166
Thierry FOURNIERc0bd9102014-01-29 12:32:58 +01002167 /* Merge flags. */
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002168 ref->flags |= refflags;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002169 }
2170
2171 /* Now, we can loading patterns from the reference. */
2172
2173 /* Lookup for existing reference in the head. If the reference
2174 * doesn't exists, create it.
2175 */
2176 expr = pattern_lookup_expr(head, ref);
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02002177 if (!expr || (expr->mflags != patflags)) {
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002178 expr = pattern_new_expr(head, ref, err);
2179 if (!expr)
2180 return 0;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02002181 expr->mflags = patflags;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002182 }
2183
Thierry FOURNIER39bef452014-01-29 13:29:45 +01002184 /* Load reference content in the pattern expression. */
2185 list_for_each_entry(elt, &ref->head, list) {
2186 if (!pat_ref_push(elt, expr, patflags, err)) {
2187 if (elt->line > 0)
2188 memprintf(err, "%s at line %d of file '%s'",
2189 *err, elt->line, filename);
2190 return 0;
2191 }
2192 }
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002193
2194 return 1;
2195}
2196
Thierry FOURNIER1794fdf2014-01-17 15:25:13 +01002197/* This function executes a pattern match on a sample. It applies pattern <expr>
2198 * to sample <smp>. The function returns NULL if the sample dont match. It returns
2199 * non-null if the sample match. If <fill> is true and the sample match, the
2200 * function returns the matched pattern. In many cases, this pattern can be a
2201 * static buffer.
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002202 */
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002203struct pattern *pattern_exec_match(struct pattern_head *head, struct sample *smp, int fill)
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002204{
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002205 struct pattern_expr_list *list;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002206 struct pattern *pat;
2207
2208 if (!head->match) {
Thierry FOURNIER1794fdf2014-01-17 15:25:13 +01002209 if (fill) {
Thierry FOURNIER5338eea2013-12-16 14:22:13 +01002210 static_pattern.smp = NULL;
Thierry FOURNIER6bb53ff2014-01-28 15:54:36 +01002211 static_pattern.ref = NULL;
Thierry FOURNIERe47e4e22014-04-28 11:18:57 +02002212 static_pattern.sflags = 0;
Thierry FOURNIER5338eea2013-12-16 14:22:13 +01002213 static_pattern.type = SMP_T_UINT;
2214 static_pattern.val.i = 1;
Thierry FOURNIER1794fdf2014-01-17 15:25:13 +01002215 }
Thierry FOURNIER1794fdf2014-01-17 15:25:13 +01002216 return &static_pattern;
2217 }
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002218
Thierry FOURNIER5d344082014-01-27 14:19:53 +01002219 /* convert input to string */
2220 if (!sample_convert(smp, head->expect_type))
2221 return NULL;
2222
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002223 list_for_each_entry(list, &head->head, list) {
2224 pat = head->match(smp, list->expr, fill);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002225 if (pat)
2226 return pat;
2227 }
2228 return NULL;
Thierry FOURNIERed66c292013-11-28 11:05:19 +01002229}
2230
Thierry FOURNIER6f7203d2014-01-14 16:24:51 +01002231/* This function prune the pattern expression. */
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002232void pattern_prune(struct pattern_head *head)
Thierry FOURNIER6f7203d2014-01-14 16:24:51 +01002233{
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002234 struct pattern_expr_list *list, *safe;
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002235
Thierry FOURNIERc5959fd2014-01-20 14:29:33 +01002236 list_for_each_entry_safe(list, safe, &head->head, list) {
2237 LIST_DEL(&list->list);
2238 if (list->do_free) {
2239 LIST_DEL(&list->expr->list);
2240 head->prune(list->expr);
2241 free(list->expr);
2242 }
2243 free(list);
Thierry FOURNIER1e00d382014-02-11 11:31:40 +01002244 }
Thierry FOURNIER6f7203d2014-01-14 16:24:51 +01002245}
2246
Thierry FOURNIER55d0b102014-01-15 11:25:26 +01002247/* This function lookup for a pattern matching the <key> and return a
2248 * pointer to a pointer of the sample stoarge. If the <key> dont match,
2249 * the function returns NULL. If the key cannot be parsed, the function
2250 * fill <err>.
2251 */
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01002252struct sample_storage **pattern_find_smp(struct pattern_expr *expr, struct pat_ref_elt *ref)
Thierry FOURNIER55d0b102014-01-15 11:25:26 +01002253{
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01002254 struct ebmb_node *node;
2255 struct pattern_tree *elt;
2256 struct pattern_list *pat;
Thierry FOURNIER55d0b102014-01-15 11:25:26 +01002257
Thierry FOURNIERe369ca22014-01-29 16:24:55 +01002258 for (node = ebmb_first(&expr->pattern_tree);
2259 node;
2260 node = ebmb_next(node)) {
2261 elt = container_of(node, struct pattern_tree, node);
2262 if (elt->ref == ref)
2263 return &elt->smp;
2264 }
2265
2266 for (node = ebmb_first(&expr->pattern_tree_2);
2267 node;
2268 node = ebmb_next(node)) {
2269 elt = container_of(node, struct pattern_tree, node);
2270 if (elt->ref == ref)
2271 return &elt->smp;
2272 }
2273
2274 list_for_each_entry(pat, &expr->patterns, list)
2275 if (pat->pat.ref == ref)
2276 return &pat->pat.smp;
2277
2278 return NULL;
Thierry FOURNIER55d0b102014-01-15 11:25:26 +01002279}
2280
Thierry FOURNIERb1136502014-01-15 11:38:49 +01002281/* This function search all the pattern matching the <key> and delete it.
2282 * If the parsing of the input key fails, the function returns 0 and the
2283 * <err> is filled, else return 1;
2284 */
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01002285int pattern_delete(struct pattern_expr *expr, struct pat_ref_elt *ref)
Thierry FOURNIERb1136502014-01-15 11:38:49 +01002286{
Thierry FOURNIER7acca4b2014-01-28 16:43:36 +01002287 expr->pat_head->delete(expr, ref);
Thierry FOURNIERb1136502014-01-15 11:38:49 +01002288 return 1;
2289}
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002290
2291/* This function finalize the configuration parsing. Its set all the
2292 * automatic ids
2293 */
2294void pattern_finalize_config(void)
2295{
2296 int i = 0;
2297 struct pat_ref *ref, *ref2, *ref3;
2298 struct list pr = LIST_HEAD_INIT(pr);
2299
2300 list_for_each_entry(ref, &pattern_reference, list) {
2301 if (ref->unique_id == -1) {
2302 /* Look for the first free id. */
2303 while (1) {
2304 list_for_each_entry(ref2, &pattern_reference, list) {
2305 if (ref2->unique_id == i) {
2306 i++;
2307 break;
2308 }
2309 }
Willy Tarreau3b786962014-04-26 12:37:25 +02002310 if (&ref2->list == &pattern_reference)
Thierry FOURNIERaf5a29d2014-03-11 14:29:22 +01002311 break;
2312 }
2313
2314 /* Uses the unique id and increment it for the next entry. */
2315 ref->unique_id = i;
2316 i++;
2317 }
2318 }
2319
2320 /* This sort the reference list by id. */
2321 list_for_each_entry_safe(ref, ref2, &pattern_reference, list) {
2322 LIST_DEL(&ref->list);
2323 list_for_each_entry(ref3, &pr, list) {
2324 if (ref->unique_id < ref3->unique_id) {
2325 LIST_ADDQ(&ref3->list, &ref->list);
2326 break;
2327 }
2328 }
2329 if (&ref3->list == &pr)
2330 LIST_ADDQ(&pr, &ref->list);
2331 }
2332
2333 /* swap root */
2334 LIST_ADD(&pr, &pattern_reference);
2335 LIST_DEL(&pr);
2336}