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