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