Linux Perf
strfilter.c
Go to the documentation of this file.
1 // SPDX-License-Identifier: GPL-2.0
2 #include "util.h"
3 #include "string2.h"
4 #include "strfilter.h"
5 
6 #include <errno.h>
7 #include "sane_ctype.h"
8 
9 /* Operators */
10 static const char *OP_and = "&"; /* Logical AND */
11 static const char *OP_or = "|"; /* Logical OR */
12 static const char *OP_not = "!"; /* Logical NOT */
13 
14 #define is_operator(c) ((c) == '|' || (c) == '&' || (c) == '!')
15 #define is_separator(c) (is_operator(c) || (c) == '(' || (c) == ')')
16 
18 {
19  if (node) {
20  if (node->p && !is_operator(*node->p))
21  zfree((char **)&node->p);
24  free(node);
25  }
26 }
27 
29 {
30  if (filter) {
32  free(filter);
33  }
34 }
35 
36 static const char *get_token(const char *s, const char **e)
37 {
38  const char *p;
39 
40  while (isspace(*s)) /* Skip spaces */
41  s++;
42 
43  if (*s == '\0') {
44  p = s;
45  goto end;
46  }
47 
48  p = s + 1;
49  if (!is_separator(*s)) {
50  /* End search */
51 retry:
52  while (*p && !is_separator(*p) && !isspace(*p))
53  p++;
54  /* Escape and special case: '!' is also used in glob pattern */
55  if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) {
56  p++;
57  goto retry;
58  }
59  }
60 end:
61  *e = p;
62  return s;
63 }
64 
65 static struct strfilter_node *strfilter_node__alloc(const char *op,
66  struct strfilter_node *l,
67  struct strfilter_node *r)
68 {
69  struct strfilter_node *node = zalloc(sizeof(*node));
70 
71  if (node) {
72  node->p = op;
73  node->l = l;
74  node->r = r;
75  }
76 
77  return node;
78 }
79 
80 static struct strfilter_node *strfilter_node__new(const char *s,
81  const char **ep)
82 {
83  struct strfilter_node root, *cur, *last_op;
84  const char *e;
85 
86  if (!s)
87  return NULL;
88 
89  memset(&root, 0, sizeof(root));
90  last_op = cur = &root;
91 
92  s = get_token(s, &e);
93  while (*s != '\0' && *s != ')') {
94  switch (*s) {
95  case '&': /* Exchg last OP->r with AND */
96  if (!cur->r || !last_op->r)
97  goto error;
98  cur = strfilter_node__alloc(OP_and, last_op->r, NULL);
99  if (!cur)
100  goto nomem;
101  last_op->r = cur;
102  last_op = cur;
103  break;
104  case '|': /* Exchg the root with OR */
105  if (!cur->r || !root.r)
106  goto error;
107  cur = strfilter_node__alloc(OP_or, root.r, NULL);
108  if (!cur)
109  goto nomem;
110  root.r = cur;
111  last_op = cur;
112  break;
113  case '!': /* Add NOT as a leaf node */
114  if (cur->r)
115  goto error;
116  cur->r = strfilter_node__alloc(OP_not, NULL, NULL);
117  if (!cur->r)
118  goto nomem;
119  cur = cur->r;
120  break;
121  case '(': /* Recursively parses inside the parenthesis */
122  if (cur->r)
123  goto error;
124  cur->r = strfilter_node__new(s + 1, &s);
125  if (!s)
126  goto nomem;
127  if (!cur->r || *s != ')')
128  goto error;
129  e = s + 1;
130  break;
131  default:
132  if (cur->r)
133  goto error;
134  cur->r = strfilter_node__alloc(NULL, NULL, NULL);
135  if (!cur->r)
136  goto nomem;
137  cur->r->p = strndup(s, e - s);
138  if (!cur->r->p)
139  goto nomem;
140  }
141  s = get_token(e, &e);
142  }
143  if (!cur->r)
144  goto error;
145  *ep = s;
146  return root.r;
147 nomem:
148  s = NULL;
149 error:
150  *ep = s;
152  return NULL;
153 }
154 
155 /*
156  * Parse filter rule and return new strfilter.
157  * Return NULL if fail, and *ep == NULL if memory allocation failed.
158  */
159 struct strfilter *strfilter__new(const char *rules, const char **err)
160 {
161  struct strfilter *filter = zalloc(sizeof(*filter));
162  const char *ep = NULL;
163 
164  if (filter)
165  filter->root = strfilter_node__new(rules, &ep);
166 
167  if (!filter || !filter->root || *ep != '\0') {
168  if (err)
169  *err = ep;
170  strfilter__delete(filter);
171  filter = NULL;
172  }
173 
174  return filter;
175 }
176 
177 static int strfilter__append(struct strfilter *filter, bool _or,
178  const char *rules, const char **err)
179 {
180  struct strfilter_node *right, *root;
181  const char *ep = NULL;
182 
183  if (!filter || !rules)
184  return -EINVAL;
185 
186  right = strfilter_node__new(rules, &ep);
187  if (!right || *ep != '\0') {
188  if (err)
189  *err = ep;
190  goto error;
191  }
192  root = strfilter_node__alloc(_or ? OP_or : OP_and, filter->root, right);
193  if (!root) {
194  ep = NULL;
195  goto error;
196  }
197 
198  filter->root = root;
199  return 0;
200 
201 error:
202  strfilter_node__delete(right);
203  return ep ? -EINVAL : -ENOMEM;
204 }
205 
206 int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
207 {
208  return strfilter__append(filter, true, rules, err);
209 }
210 
211 int strfilter__and(struct strfilter *filter, const char *rules,
212  const char **err)
213 {
214  return strfilter__append(filter, false, rules, err);
215 }
216 
218  const char *str)
219 {
220  if (!node || !node->p)
221  return false;
222 
223  switch (*node->p) {
224  case '|': /* OR */
225  return strfilter_node__compare(node->l, str) ||
226  strfilter_node__compare(node->r, str);
227  case '&': /* AND */
228  return strfilter_node__compare(node->l, str) &&
229  strfilter_node__compare(node->r, str);
230  case '!': /* NOT */
231  return !strfilter_node__compare(node->r, str);
232  default:
233  return strglobmatch(str, node->p);
234  }
235 }
236 
237 /* Return true if STR matches the filter rules */
238 bool strfilter__compare(struct strfilter *filter, const char *str)
239 {
240  if (!filter)
241  return false;
242  return strfilter_node__compare(filter->root, str);
243 }
244 
245 static int strfilter_node__sprint(struct strfilter_node *node, char *buf);
246 
247 /* sprint node in parenthesis if needed */
248 static int strfilter_node__sprint_pt(struct strfilter_node *node, char *buf)
249 {
250  int len;
251  int pt = node->r ? 2 : 0; /* don't need to check node->l */
252 
253  if (buf && pt)
254  *buf++ = '(';
255  len = strfilter_node__sprint(node, buf);
256  if (len < 0)
257  return len;
258  if (buf && pt)
259  *(buf + len) = ')';
260  return len + pt;
261 }
262 
263 static int strfilter_node__sprint(struct strfilter_node *node, char *buf)
264 {
265  int len = 0, rlen;
266 
267  if (!node || !node->p)
268  return -EINVAL;
269 
270  switch (*node->p) {
271  case '|':
272  case '&':
273  len = strfilter_node__sprint_pt(node->l, buf);
274  if (len < 0)
275  return len;
276  __fallthrough;
277  case '!':
278  if (buf) {
279  *(buf + len++) = *node->p;
280  buf += len;
281  } else
282  len++;
283  rlen = strfilter_node__sprint_pt(node->r, buf);
284  if (rlen < 0)
285  return rlen;
286  len += rlen;
287  break;
288  default:
289  len = strlen(node->p);
290  if (buf)
291  strcpy(buf, node->p);
292  }
293 
294  return len;
295 }
296 
298 {
299  int len;
300  char *ret = NULL;
301 
302  len = strfilter_node__sprint(filter->root, NULL);
303  if (len < 0)
304  return NULL;
305 
306  ret = malloc(len + 1);
307  if (ret)
308  strfilter_node__sprint(filter->root, ret);
309 
310  return ret;
311 }
Definition: mem2node.c:7
struct strfilter * strfilter__new(const char *rules, const char **err)
Definition: strfilter.c:159
static const char * OP_and
Definition: strfilter.c:10
#define isspace(x)
Definition: sane_ctype.h:33
static int strfilter_node__sprint_pt(struct strfilter_node *node, char *buf)
Definition: strfilter.c:248
int int err
Definition: 5sec.c:44
struct rb_root root
Definition: block-range.c:6
struct strfilter_node * root
Definition: strfilter.h:18
bool strglobmatch(const char *str, const char *pat)
Definition: string.c:265
static int strfilter__append(struct strfilter *filter, bool _or, const char *rules, const char **err)
Definition: strfilter.c:177
int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
Definition: strfilter.c:206
x86 movsq based memset() in arch/x86/lib/memset_64.S") MEMSET_FN(memset_erms
void * malloc(YYSIZE_T)
void strfilter__delete(struct strfilter *filter)
Definition: strfilter.c:28
static const char * OP_not
Definition: strfilter.c:12
static int str(yyscan_t scanner, int token)
#define is_operator(c)
Definition: strfilter.c:14
struct strfilter_node * r
Definition: strfilter.h:12
struct strfilter_node * l
Definition: strfilter.h:11
static struct strfilter_node * strfilter_node__alloc(const char *op, struct strfilter_node *l, struct strfilter_node *r)
Definition: strfilter.c:65
char * strfilter__string(struct strfilter *filter)
Definition: strfilter.c:297
bool strfilter__compare(struct strfilter *filter, const char *str)
Definition: strfilter.c:238
static struct strfilter_node * strfilter_node__new(const char *s, const char **ep)
Definition: strfilter.c:80
#define zfree(ptr)
Definition: util.h:25
struct strfilter * filter
Definition: builtin-probe.c:60
int strfilter__and(struct strfilter *filter, const char *rules, const char **err)
Definition: strfilter.c:211
static bool strfilter_node__compare(struct strfilter_node *node, const char *str)
Definition: strfilter.c:217
#define is_separator(c)
Definition: strfilter.c:15
static void strfilter_node__delete(struct strfilter_node *node)
Definition: strfilter.c:17
void free(void *)
static const char * get_token(const char *s, const char **e)
Definition: strfilter.c:36
static int strfilter_node__sprint(struct strfilter_node *node, char *buf)
Definition: strfilter.c:263
static const char * OP_or
Definition: strfilter.c:11
const char * p
Definition: strfilter.h:13
void static void * zalloc(size_t size)
Definition: util.h:20