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 */ 33static 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(th.td_lolen, th.td_flags); 60 if (bsize < tsize) 61 goto out; 62 63 table = kvzalloc(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(table)) 83 vm_unmap_aliases(); 84 } 85 86out: 87 return table; 88fail: 89 kvfree(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 */ 103static int verify_table_headers(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; 140out: 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 */ 153static 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 217out: 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 */ 227static 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(dfa->tables[i]); 234 dfa->tables[i] = NULL; 235 } 236 kfree(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 */ 244void 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 */ 262struct 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(sizeof(struct aa_dfa), GFP_KERNEL); 269 if (!dfa) 270 goto fail; 271 272 kref_init(&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(data, 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(table->td_lolen, table->td_flags); 344 size -= table_size(table->td_lolen, table->td_flags); 345 table = NULL; 346 } 347 error = verify_table_headers(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 359fail: 360 kvfree(table); 361 dfa_free(dfa); 362 return ERR_PTR(error); 363} 364 365#define match_char(state, def, base, next, check, C) \ 366do { \ 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 */ 395aa_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 */ 435aa_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 */ 473aa_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 491aa_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 */ 521aa_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 */ 582aa_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) \ 628do { \ 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 */ 634static 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 657static 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)) { 691 state = aa_dfa_match(dfa, 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)) { 710 state = aa_dfa_match(dfa, state, str); 711 *count -= adjust; 712 goto out; 713 } 714 inc_wb_pos(wb); 715 (*count)++; 716 } 717 } 718 719out: 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 */ 738aa_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, count); 746} 747