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