Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0-only
2 : : /*
3 : : * AppArmor security module
4 : : *
5 : : * This file contains AppArmor dfa based regular expression matching engine
6 : : *
7 : : * Copyright (C) 1998-2008 Novell/SUSE
8 : : * Copyright 2009-2012 Canonical Ltd.
9 : : */
10 : :
11 : : #include <linux/errno.h>
12 : : #include <linux/kernel.h>
13 : : #include <linux/mm.h>
14 : : #include <linux/slab.h>
15 : : #include <linux/vmalloc.h>
16 : : #include <linux/err.h>
17 : : #include <linux/kref.h>
18 : :
19 : : #include "include/lib.h"
20 : : #include "include/match.h"
21 : :
22 : : #define base_idx(X) ((X) & 0xffffff)
23 : :
24 : : static char nulldfa_src[] = {
25 : : #include "nulldfa.in"
26 : : };
27 : : struct aa_dfa *nulldfa;
28 : :
29 : : static char stacksplitdfa_src[] = {
30 : : #include "stacksplitdfa.in"
31 : : };
32 : : struct aa_dfa *stacksplitdfa;
33 : :
34 : 0 : int aa_setup_dfa_engine(void)
35 : : {
36 : : int error;
37 : :
38 : 0 : nulldfa = aa_dfa_unpack(nulldfa_src, sizeof(nulldfa_src),
39 : : TO_ACCEPT1_FLAG(YYTD_DATA32) |
40 : : TO_ACCEPT2_FLAG(YYTD_DATA32));
41 [ # # ]: 0 : if (IS_ERR(nulldfa)) {
42 : : error = PTR_ERR(nulldfa);
43 : 0 : nulldfa = NULL;
44 : 0 : return error;
45 : : }
46 : :
47 : 0 : stacksplitdfa = aa_dfa_unpack(stacksplitdfa_src,
48 : : sizeof(stacksplitdfa_src),
49 : : TO_ACCEPT1_FLAG(YYTD_DATA32) |
50 : : TO_ACCEPT2_FLAG(YYTD_DATA32));
51 [ # # ]: 0 : if (IS_ERR(stacksplitdfa)) {
52 : 0 : aa_put_dfa(nulldfa);
53 : 0 : nulldfa = NULL;
54 : 0 : error = PTR_ERR(stacksplitdfa);
55 : 0 : stacksplitdfa = NULL;
56 : 0 : return error;
57 : : }
58 : :
59 : : return 0;
60 : : }
61 : :
62 : 0 : void aa_teardown_dfa_engine(void)
63 : : {
64 : 0 : aa_put_dfa(stacksplitdfa);
65 : 0 : aa_put_dfa(nulldfa);
66 : 0 : }
67 : :
68 : : /**
69 : : * unpack_table - unpack a dfa table (one of accept, default, base, next check)
70 : : * @blob: data to unpack (NOT NULL)
71 : : * @bsize: size of blob
72 : : *
73 : : * Returns: pointer to table else NULL on failure
74 : : *
75 : : * NOTE: must be freed by kvfree (not kfree)
76 : : */
77 : 0 : static struct table_header *unpack_table(char *blob, size_t bsize)
78 : : {
79 : : struct table_header *table = NULL;
80 : : struct table_header th;
81 : : size_t tsize;
82 : :
83 [ # # ]: 0 : if (bsize < sizeof(struct table_header))
84 : : goto out;
85 : :
86 : : /* loaded td_id's start at 1, subtract 1 now to avoid doing
87 : : * it every time we use td_id as an index
88 : : */
89 : 0 : th.td_id = be16_to_cpu(*(__be16 *) (blob)) - 1;
90 [ # # ]: 0 : if (th.td_id > YYTD_ID_MAX)
91 : : goto out;
92 : 0 : th.td_flags = be16_to_cpu(*(__be16 *) (blob + 2));
93 : 0 : th.td_lolen = be32_to_cpu(*(__be32 *) (blob + 8));
94 : 0 : blob += sizeof(struct table_header);
95 : :
96 [ # # # # ]: 0 : if (!(th.td_flags == YYTD_DATA16 || th.td_flags == YYTD_DATA32 ||
97 : : th.td_flags == YYTD_DATA8))
98 : : goto out;
99 : :
100 : : /* if we have a table it must have some entries */
101 [ # # ]: 0 : if (th.td_lolen == 0)
102 : : goto out;
103 : 0 : tsize = table_size(th.td_lolen, th.td_flags);
104 [ # # ]: 0 : if (bsize < tsize)
105 : : goto out;
106 : :
107 : : table = kvzalloc(tsize, GFP_KERNEL);
108 [ # # ]: 0 : if (table) {
109 : 0 : table->td_id = th.td_id;
110 : 0 : table->td_flags = th.td_flags;
111 : 0 : table->td_lolen = th.td_lolen;
112 [ # # ]: 0 : if (th.td_flags == YYTD_DATA8)
113 [ # # ]: 0 : UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
114 : : u8, u8, byte_to_byte);
115 [ # # ]: 0 : else if (th.td_flags == YYTD_DATA16)
116 [ # # ]: 0 : UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
117 : : u16, __be16, be16_to_cpu);
118 [ # # ]: 0 : else if (th.td_flags == YYTD_DATA32)
119 [ # # ]: 0 : UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
120 : : u32, __be32, be32_to_cpu);
121 : : else
122 : : goto fail;
123 : : /* if table was vmalloced make sure the page tables are synced
124 : : * before it is used, as it goes live to all cpus.
125 : : */
126 [ # # ]: 0 : if (is_vmalloc_addr(table))
127 : 0 : vm_unmap_aliases();
128 : : }
129 : :
130 : : out:
131 : 0 : return table;
132 : : fail:
133 : 0 : kvfree(table);
134 : 0 : return NULL;
135 : : }
136 : :
137 : : /**
138 : : * verify_table_headers - verify that the tables headers are as expected
139 : : * @tables - array of dfa tables to check (NOT NULL)
140 : : * @flags: flags controlling what type of accept table are acceptable
141 : : *
142 : : * Assumes dfa has gone through the first pass verification done by unpacking
143 : : * NOTE: this does not valid accept table values
144 : : *
145 : : * Returns: %0 else error code on failure to verify
146 : : */
147 : 0 : static int verify_table_headers(struct table_header **tables, int flags)
148 : : {
149 : : size_t state_count, trans_count;
150 : : int error = -EPROTO;
151 : :
152 : : /* check that required tables exist */
153 [ # # # # : 0 : if (!(tables[YYTD_ID_DEF] && tables[YYTD_ID_BASE] &&
# # # # ]
154 : 0 : tables[YYTD_ID_NXT] && tables[YYTD_ID_CHK]))
155 : : goto out;
156 : :
157 : : /* accept.size == default.size == base.size */
158 : 0 : state_count = tables[YYTD_ID_BASE]->td_lolen;
159 [ # # ]: 0 : if (ACCEPT1_FLAGS(flags)) {
160 [ # # ]: 0 : if (!tables[YYTD_ID_ACCEPT])
161 : : goto out;
162 [ # # ]: 0 : if (state_count != tables[YYTD_ID_ACCEPT]->td_lolen)
163 : : goto out;
164 : : }
165 [ # # ]: 0 : if (ACCEPT2_FLAGS(flags)) {
166 [ # # ]: 0 : if (!tables[YYTD_ID_ACCEPT2])
167 : : goto out;
168 [ # # ]: 0 : if (state_count != tables[YYTD_ID_ACCEPT2]->td_lolen)
169 : : goto out;
170 : : }
171 [ # # ]: 0 : if (state_count != tables[YYTD_ID_DEF]->td_lolen)
172 : : goto out;
173 : :
174 : : /* next.size == chk.size */
175 : 0 : trans_count = tables[YYTD_ID_NXT]->td_lolen;
176 [ # # ]: 0 : if (trans_count != tables[YYTD_ID_CHK]->td_lolen)
177 : : goto out;
178 : :
179 : : /* if equivalence classes then its table size must be 256 */
180 [ # # # # ]: 0 : if (tables[YYTD_ID_EC] && tables[YYTD_ID_EC]->td_lolen != 256)
181 : : goto out;
182 : :
183 : : error = 0;
184 : : out:
185 : 0 : return error;
186 : : }
187 : :
188 : : /**
189 : : * verify_dfa - verify that transitions and states in the tables are in bounds.
190 : : * @dfa: dfa to test (NOT NULL)
191 : : *
192 : : * Assumes dfa has gone through the first pass verification done by unpacking
193 : : * NOTE: this does not valid accept table values
194 : : *
195 : : * Returns: %0 else error code on failure to verify
196 : : */
197 : 0 : static int verify_dfa(struct aa_dfa *dfa)
198 : : {
199 : : size_t i, state_count, trans_count;
200 : : int error = -EPROTO;
201 : :
202 : 0 : state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
203 : 0 : trans_count = dfa->tables[YYTD_ID_NXT]->td_lolen;
204 [ # # ]: 0 : if (state_count == 0)
205 : : goto out;
206 [ # # ]: 0 : for (i = 0; i < state_count; i++) {
207 [ # # # # ]: 0 : if (!(BASE_TABLE(dfa)[i] & MATCH_FLAG_DIFF_ENCODE) &&
208 : 0 : (DEFAULT_TABLE(dfa)[i] >= state_count))
209 : : goto out;
210 [ # # ]: 0 : if (base_idx(BASE_TABLE(dfa)[i]) + 255 >= trans_count) {
211 : 0 : pr_err("AppArmor DFA next/check upper bounds error\n");
212 : 0 : goto out;
213 : : }
214 : : }
215 : :
216 [ # # ]: 0 : for (i = 0; i < trans_count; i++) {
217 [ # # ]: 0 : if (NEXT_TABLE(dfa)[i] >= state_count)
218 : : goto out;
219 [ # # ]: 0 : if (CHECK_TABLE(dfa)[i] >= state_count)
220 : : goto out;
221 : : }
222 : :
223 : : /* Now that all the other tables are verified, verify diffencoding */
224 [ # # ]: 0 : for (i = 0; i < state_count; i++) {
225 : : size_t j, k;
226 : :
227 [ # # ]: 0 : for (j = i;
228 [ # # ]: 0 : (BASE_TABLE(dfa)[j] & MATCH_FLAG_DIFF_ENCODE) &&
229 : 0 : !(BASE_TABLE(dfa)[j] & MARK_DIFF_ENCODE);
230 : : j = k) {
231 : 0 : k = DEFAULT_TABLE(dfa)[j];
232 [ # # ]: 0 : if (j == k)
233 : : goto out;
234 [ # # ]: 0 : if (k < j)
235 : : break; /* already verified */
236 : 0 : BASE_TABLE(dfa)[j] |= MARK_DIFF_ENCODE;
237 : : }
238 : : }
239 : : error = 0;
240 : :
241 : : out:
242 : 0 : return error;
243 : : }
244 : :
245 : : /**
246 : : * dfa_free - free a dfa allocated by aa_dfa_unpack
247 : : * @dfa: the dfa to free (MAYBE NULL)
248 : : *
249 : : * Requires: reference count to dfa == 0
250 : : */
251 : 0 : static void dfa_free(struct aa_dfa *dfa)
252 : : {
253 [ # # ]: 0 : if (dfa) {
254 : : int i;
255 : :
256 [ # # ]: 0 : for (i = 0; i < ARRAY_SIZE(dfa->tables); i++) {
257 : 0 : kvfree(dfa->tables[i]);
258 : 0 : dfa->tables[i] = NULL;
259 : : }
260 : 0 : kfree(dfa);
261 : : }
262 : 0 : }
263 : :
264 : : /**
265 : : * aa_dfa_free_kref - free aa_dfa by kref (called by aa_put_dfa)
266 : : * @kr: kref callback for freeing of a dfa (NOT NULL)
267 : : */
268 : 0 : void aa_dfa_free_kref(struct kref *kref)
269 : : {
270 : : struct aa_dfa *dfa = container_of(kref, struct aa_dfa, count);
271 : 0 : dfa_free(dfa);
272 : 0 : }
273 : :
274 : : /**
275 : : * aa_dfa_unpack - unpack the binary tables of a serialized dfa
276 : : * @blob: aligned serialized stream of data to unpack (NOT NULL)
277 : : * @size: size of data to unpack
278 : : * @flags: flags controlling what type of accept tables are acceptable
279 : : *
280 : : * Unpack a dfa that has been serialized. To find information on the dfa
281 : : * format look in Documentation/admin-guide/LSM/apparmor.rst
282 : : * Assumes the dfa @blob stream has been aligned on a 8 byte boundary
283 : : *
284 : : * Returns: an unpacked dfa ready for matching or ERR_PTR on failure
285 : : */
286 : 0 : struct aa_dfa *aa_dfa_unpack(void *blob, size_t size, int flags)
287 : : {
288 : : int hsize;
289 : : int error = -ENOMEM;
290 : : char *data = blob;
291 : : struct table_header *table = NULL;
292 : 0 : struct aa_dfa *dfa = kzalloc(sizeof(struct aa_dfa), GFP_KERNEL);
293 [ # # ]: 0 : if (!dfa)
294 : : goto fail;
295 : :
296 : : kref_init(&dfa->count);
297 : :
298 : : error = -EPROTO;
299 : :
300 : : /* get dfa table set header */
301 [ # # ]: 0 : if (size < sizeof(struct table_set_header))
302 : : goto fail;
303 : :
304 [ # # ]: 0 : if (ntohl(*(__be32 *) data) != YYTH_MAGIC)
305 : : goto fail;
306 : :
307 : 0 : hsize = ntohl(*(__be32 *) (data + 4));
308 [ # # ]: 0 : if (size < hsize)
309 : : goto fail;
310 : :
311 : 0 : dfa->flags = ntohs(*(__be16 *) (data + 12));
312 [ # # ]: 0 : if (dfa->flags != 0 && dfa->flags != YYTH_FLAG_DIFF_ENCODE)
313 : : goto fail;
314 : :
315 : 0 : data += hsize;
316 : 0 : size -= hsize;
317 : :
318 [ # # ]: 0 : while (size > 0) {
319 : 0 : table = unpack_table(data, size);
320 [ # # ]: 0 : if (!table)
321 : : goto fail;
322 : :
323 [ # # # # : 0 : switch (table->td_id) {
# # ]
324 : : case YYTD_ID_ACCEPT:
325 [ # # ]: 0 : if (!(table->td_flags & ACCEPT1_FLAGS(flags)))
326 : : goto fail;
327 : : break;
328 : : case YYTD_ID_ACCEPT2:
329 [ # # ]: 0 : if (!(table->td_flags & ACCEPT2_FLAGS(flags)))
330 : : goto fail;
331 : : break;
332 : : case YYTD_ID_BASE:
333 [ # # ]: 0 : if (table->td_flags != YYTD_DATA32)
334 : : goto fail;
335 : : break;
336 : : case YYTD_ID_DEF:
337 : : case YYTD_ID_NXT:
338 : : case YYTD_ID_CHK:
339 [ # # ]: 0 : if (table->td_flags != YYTD_DATA16)
340 : : goto fail;
341 : : break;
342 : : case YYTD_ID_EC:
343 [ # # ]: 0 : if (table->td_flags != YYTD_DATA8)
344 : : goto fail;
345 : : break;
346 : : default:
347 : : goto fail;
348 : : }
349 : : /* check for duplicate table entry */
350 [ # # ]: 0 : if (dfa->tables[table->td_id])
351 : : goto fail;
352 : 0 : dfa->tables[table->td_id] = table;
353 : 0 : data += table_size(table->td_lolen, table->td_flags);
354 : 0 : size -= table_size(table->td_lolen, table->td_flags);
355 : : table = NULL;
356 : : }
357 : 0 : error = verify_table_headers(dfa->tables, flags);
358 [ # # ]: 0 : if (error)
359 : : goto fail;
360 : :
361 [ # # ]: 0 : if (flags & DFA_FLAG_VERIFY_STATES) {
362 : 0 : error = verify_dfa(dfa);
363 [ # # ]: 0 : if (error)
364 : : goto fail;
365 : : }
366 : :
367 : 0 : return dfa;
368 : :
369 : : fail:
370 : 0 : kvfree(table);
371 : 0 : dfa_free(dfa);
372 : 0 : return ERR_PTR(error);
373 : : }
374 : :
375 : : #define match_char(state, def, base, next, check, C) \
376 : : do { \
377 : : u32 b = (base)[(state)]; \
378 : : unsigned int pos = base_idx(b) + (C); \
379 : : if ((check)[pos] != (state)) { \
380 : : (state) = (def)[(state)]; \
381 : : if (b & MATCH_FLAG_DIFF_ENCODE) \
382 : : continue; \
383 : : break; \
384 : : } \
385 : : (state) = (next)[pos]; \
386 : : break; \
387 : : } while (1)
388 : :
389 : : /**
390 : : * aa_dfa_match_len - traverse @dfa to find state @str stops at
391 : : * @dfa: the dfa to match @str against (NOT NULL)
392 : : * @start: the state of the dfa to start matching in
393 : : * @str: the string of bytes to match against the dfa (NOT NULL)
394 : : * @len: length of the string of bytes to match
395 : : *
396 : : * aa_dfa_match_len will match @str against the dfa and return the state it
397 : : * finished matching in. The final state can be used to look up the accepting
398 : : * label, or as the start state of a continuing match.
399 : : *
400 : : * This function will happily match again the 0 byte and only finishes
401 : : * when @len input is consumed.
402 : : *
403 : : * Returns: final state reached after input is consumed
404 : : */
405 : 0 : unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int start,
406 : : const char *str, int len)
407 : : {
408 : 0 : u16 *def = DEFAULT_TABLE(dfa);
409 : 0 : u32 *base = BASE_TABLE(dfa);
410 : 0 : u16 *next = NEXT_TABLE(dfa);
411 : 0 : u16 *check = CHECK_TABLE(dfa);
412 : : unsigned int state = start;
413 : :
414 [ # # ]: 0 : if (state == 0)
415 : : return 0;
416 : :
417 : : /* current state is <state>, matching character *str */
418 [ # # ]: 0 : if (dfa->tables[YYTD_ID_EC]) {
419 : : /* Equivalence class table defined */
420 : 0 : u8 *equiv = EQUIV_TABLE(dfa);
421 [ # # ]: 0 : for (; len; len--)
422 [ # # # # ]: 0 : match_char(state, def, base, next, check,
423 : : equiv[(u8) *str++]);
424 : : } else {
425 : : /* default is direct to next state */
426 [ # # ]: 0 : for (; len; len--)
427 [ # # # # ]: 0 : match_char(state, def, base, next, check, (u8) *str++);
428 : : }
429 : :
430 : 0 : return state;
431 : : }
432 : :
433 : : /**
434 : : * aa_dfa_match - traverse @dfa to find state @str stops at
435 : : * @dfa: the dfa to match @str against (NOT NULL)
436 : : * @start: the state of the dfa to start matching in
437 : : * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
438 : : *
439 : : * aa_dfa_match will match @str against the dfa and return the state it
440 : : * finished matching in. The final state can be used to look up the accepting
441 : : * label, or as the start state of a continuing match.
442 : : *
443 : : * Returns: final state reached after input is consumed
444 : : */
445 : 0 : unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start,
446 : : const char *str)
447 : : {
448 : 0 : u16 *def = DEFAULT_TABLE(dfa);
449 : 0 : u32 *base = BASE_TABLE(dfa);
450 : 0 : u16 *next = NEXT_TABLE(dfa);
451 : 0 : u16 *check = CHECK_TABLE(dfa);
452 : : unsigned int state = start;
453 : :
454 [ # # ]: 0 : if (state == 0)
455 : : return 0;
456 : :
457 : : /* current state is <state>, matching character *str */
458 [ # # ]: 0 : if (dfa->tables[YYTD_ID_EC]) {
459 : : /* Equivalence class table defined */
460 : 0 : u8 *equiv = EQUIV_TABLE(dfa);
461 : : /* default is direct to next state */
462 [ # # ]: 0 : while (*str)
463 [ # # # # ]: 0 : match_char(state, def, base, next, check,
464 : : equiv[(u8) *str++]);
465 : : } else {
466 : : /* default is direct to next state */
467 [ # # ]: 0 : while (*str)
468 [ # # # # ]: 0 : match_char(state, def, base, next, check, (u8) *str++);
469 : : }
470 : :
471 : 0 : return state;
472 : : }
473 : :
474 : : /**
475 : : * aa_dfa_next - step one character to the next state in the dfa
476 : : * @dfa: the dfa to traverse (NOT NULL)
477 : : * @state: the state to start in
478 : : * @c: the input character to transition on
479 : : *
480 : : * aa_dfa_match will step through the dfa by one input character @c
481 : : *
482 : : * Returns: state reach after input @c
483 : : */
484 : 0 : unsigned int aa_dfa_next(struct aa_dfa *dfa, unsigned int state,
485 : : const char c)
486 : : {
487 : 0 : u16 *def = DEFAULT_TABLE(dfa);
488 : 0 : u32 *base = BASE_TABLE(dfa);
489 : 0 : u16 *next = NEXT_TABLE(dfa);
490 : 0 : u16 *check = CHECK_TABLE(dfa);
491 : :
492 : : /* current state is <state>, matching character *str */
493 [ # # ]: 0 : if (dfa->tables[YYTD_ID_EC]) {
494 : : /* Equivalence class table defined */
495 : 0 : u8 *equiv = EQUIV_TABLE(dfa);
496 [ # # # # ]: 0 : match_char(state, def, base, next, check, equiv[(u8) c]);
497 : : } else
498 [ # # # # ]: 0 : match_char(state, def, base, next, check, (u8) c);
499 : :
500 : 0 : return state;
501 : : }
502 : :
503 : : /**
504 : : * aa_dfa_match_until - traverse @dfa until accept state or end of input
505 : : * @dfa: the dfa to match @str against (NOT NULL)
506 : : * @start: the state of the dfa to start matching in
507 : : * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
508 : : * @retpos: first character in str after match OR end of string
509 : : *
510 : : * aa_dfa_match will match @str against the dfa and return the state it
511 : : * finished matching in. The final state can be used to look up the accepting
512 : : * label, or as the start state of a continuing match.
513 : : *
514 : : * Returns: final state reached after input is consumed
515 : : */
516 : 0 : unsigned int aa_dfa_match_until(struct aa_dfa *dfa, unsigned int start,
517 : : const char *str, const char **retpos)
518 : : {
519 : 0 : u16 *def = DEFAULT_TABLE(dfa);
520 : 0 : u32 *base = BASE_TABLE(dfa);
521 : 0 : u16 *next = NEXT_TABLE(dfa);
522 : 0 : u16 *check = CHECK_TABLE(dfa);
523 : 0 : u32 *accept = ACCEPT_TABLE(dfa);
524 : : unsigned int state = start, pos;
525 : :
526 [ # # ]: 0 : if (state == 0)
527 : : return 0;
528 : :
529 : : /* current state is <state>, matching character *str */
530 [ # # ]: 0 : if (dfa->tables[YYTD_ID_EC]) {
531 : : /* Equivalence class table defined */
532 : 0 : u8 *equiv = EQUIV_TABLE(dfa);
533 : : /* default is direct to next state */
534 [ # # ]: 0 : while (*str) {
535 : 0 : pos = base_idx(base[state]) + equiv[(u8) *str++];
536 [ # # ]: 0 : if (check[pos] == state)
537 : 0 : state = next[pos];
538 : : else
539 : 0 : state = def[state];
540 [ # # ]: 0 : if (accept[state])
541 : : break;
542 : : }
543 : : } else {
544 : : /* default is direct to next state */
545 [ # # ]: 0 : while (*str) {
546 : 0 : pos = base_idx(base[state]) + (u8) *str++;
547 [ # # ]: 0 : if (check[pos] == state)
548 : 0 : state = next[pos];
549 : : else
550 : 0 : state = def[state];
551 [ # # ]: 0 : if (accept[state])
552 : : break;
553 : : }
554 : : }
555 : :
556 : 0 : *retpos = str;
557 : 0 : return state;
558 : : }
559 : :
560 : : /**
561 : : * aa_dfa_matchn_until - traverse @dfa until accept or @n bytes consumed
562 : : * @dfa: the dfa to match @str against (NOT NULL)
563 : : * @start: the state of the dfa to start matching in
564 : : * @str: the string of bytes to match against the dfa (NOT NULL)
565 : : * @n: length of the string of bytes to match
566 : : * @retpos: first character in str after match OR str + n
567 : : *
568 : : * aa_dfa_match_len will match @str against the dfa and return the state it
569 : : * finished matching in. The final state can be used to look up the accepting
570 : : * label, or as the start state of a continuing match.
571 : : *
572 : : * This function will happily match again the 0 byte and only finishes
573 : : * when @n input is consumed.
574 : : *
575 : : * Returns: final state reached after input is consumed
576 : : */
577 : 0 : unsigned int aa_dfa_matchn_until(struct aa_dfa *dfa, unsigned int start,
578 : : const char *str, int n, const char **retpos)
579 : : {
580 : 0 : u16 *def = DEFAULT_TABLE(dfa);
581 : 0 : u32 *base = BASE_TABLE(dfa);
582 : 0 : u16 *next = NEXT_TABLE(dfa);
583 : 0 : u16 *check = CHECK_TABLE(dfa);
584 : 0 : u32 *accept = ACCEPT_TABLE(dfa);
585 : : unsigned int state = start, pos;
586 : :
587 : 0 : *retpos = NULL;
588 [ # # ]: 0 : if (state == 0)
589 : : return 0;
590 : :
591 : : /* current state is <state>, matching character *str */
592 [ # # ]: 0 : if (dfa->tables[YYTD_ID_EC]) {
593 : : /* Equivalence class table defined */
594 : 0 : u8 *equiv = EQUIV_TABLE(dfa);
595 : : /* default is direct to next state */
596 [ # # ]: 0 : for (; n; n--) {
597 : 0 : pos = base_idx(base[state]) + equiv[(u8) *str++];
598 [ # # ]: 0 : if (check[pos] == state)
599 : 0 : state = next[pos];
600 : : else
601 : 0 : state = def[state];
602 [ # # ]: 0 : if (accept[state])
603 : : break;
604 : : }
605 : : } else {
606 : : /* default is direct to next state */
607 [ # # ]: 0 : for (; n; n--) {
608 : 0 : pos = base_idx(base[state]) + (u8) *str++;
609 [ # # ]: 0 : if (check[pos] == state)
610 : 0 : state = next[pos];
611 : : else
612 : 0 : state = def[state];
613 [ # # ]: 0 : if (accept[state])
614 : : break;
615 : : }
616 : : }
617 : :
618 : 0 : *retpos = str;
619 : 0 : return state;
620 : : }
621 : :
622 : : #define inc_wb_pos(wb) \
623 : : do { \
624 : : wb->pos = (wb->pos + 1) & (wb->size - 1); \
625 : : wb->len = (wb->len + 1) & (wb->size - 1); \
626 : : } while (0)
627 : :
628 : : /* For DFAs that don't support extended tagging of states */
629 : : static bool is_loop(struct match_workbuf *wb, unsigned int state,
630 : : unsigned int *adjust)
631 : : {
632 : : unsigned int pos = wb->pos;
633 : : unsigned int i;
634 : :
635 [ # # # # ]: 0 : if (wb->history[pos] < state)
636 : : return false;
637 : :
638 [ # # # # ]: 0 : for (i = 0; i <= wb->len; i++) {
639 [ # # # # ]: 0 : if (wb->history[pos] == state) {
640 : 0 : *adjust = i;
641 : : return true;
642 : : }
643 [ # # # # ]: 0 : if (pos == 0)
644 : 0 : pos = wb->size;
645 : 0 : pos--;
646 : : }
647 : :
648 : 0 : *adjust = i;
649 : : return true;
650 : : }
651 : :
652 : 0 : static unsigned int leftmatch_fb(struct aa_dfa *dfa, unsigned int start,
653 : : const char *str, struct match_workbuf *wb,
654 : : unsigned int *count)
655 : : {
656 : 0 : u16 *def = DEFAULT_TABLE(dfa);
657 : 0 : u32 *base = BASE_TABLE(dfa);
658 : 0 : u16 *next = NEXT_TABLE(dfa);
659 : 0 : u16 *check = CHECK_TABLE(dfa);
660 : : unsigned int state = start, pos;
661 : :
662 : : AA_BUG(!dfa);
663 : : AA_BUG(!str);
664 : : AA_BUG(!wb);
665 : : AA_BUG(!count);
666 : :
667 : 0 : *count = 0;
668 [ # # ]: 0 : if (state == 0)
669 : : return 0;
670 : :
671 : : /* current state is <state>, matching character *str */
672 [ # # ]: 0 : if (dfa->tables[YYTD_ID_EC]) {
673 : : /* Equivalence class table defined */
674 : 0 : u8 *equiv = EQUIV_TABLE(dfa);
675 : : /* default is direct to next state */
676 [ # # ]: 0 : while (*str) {
677 : : unsigned int adjust;
678 : :
679 : 0 : wb->history[wb->pos] = state;
680 : 0 : pos = base_idx(base[state]) + equiv[(u8) *str++];
681 [ # # ]: 0 : if (check[pos] == state)
682 : 0 : state = next[pos];
683 : : else
684 : 0 : state = def[state];
685 [ # # ]: 0 : if (is_loop(wb, state, &adjust)) {
686 : 0 : state = aa_dfa_match(dfa, state, str);
687 : 0 : *count -= adjust;
688 : : goto out;
689 : : }
690 : 0 : inc_wb_pos(wb);
691 : 0 : (*count)++;
692 : : }
693 : : } else {
694 : : /* default is direct to next state */
695 [ # # ]: 0 : while (*str) {
696 : : unsigned int adjust;
697 : :
698 : 0 : wb->history[wb->pos] = state;
699 : 0 : pos = base_idx(base[state]) + (u8) *str++;
700 [ # # ]: 0 : if (check[pos] == state)
701 : 0 : state = next[pos];
702 : : else
703 : 0 : state = def[state];
704 [ # # ]: 0 : if (is_loop(wb, state, &adjust)) {
705 : 0 : state = aa_dfa_match(dfa, state, str);
706 : 0 : *count -= adjust;
707 : : goto out;
708 : : }
709 : 0 : inc_wb_pos(wb);
710 : 0 : (*count)++;
711 : : }
712 : : }
713 : :
714 : : out:
715 [ # # ]: 0 : if (!state)
716 : 0 : *count = 0;
717 : 0 : return state;
718 : : }
719 : :
720 : : /**
721 : : * aa_dfa_leftmatch - traverse @dfa to find state @str stops at
722 : : * @dfa: the dfa to match @str against (NOT NULL)
723 : : * @start: the state of the dfa to start matching in
724 : : * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
725 : : * @count: current count of longest left.
726 : : *
727 : : * aa_dfa_match will match @str against the dfa and return the state it
728 : : * finished matching in. The final state can be used to look up the accepting
729 : : * label, or as the start state of a continuing match.
730 : : *
731 : : * Returns: final state reached after input is consumed
732 : : */
733 : 0 : unsigned int aa_dfa_leftmatch(struct aa_dfa *dfa, unsigned int start,
734 : : const char *str, unsigned int *count)
735 : : {
736 : 0 : DEFINE_MATCH_WB(wb);
737 : :
738 : : /* TODO: match for extended state dfas */
739 : :
740 : 0 : return leftmatch_fb(dfa, start, str, &wb, count);
741 : : }
|
