projects/linux·blob master · refs

835 lines · 21.1 KiB

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