match.c (4b4193256c8d3bc3a5397b5cd9494c2ad386317d) match.c (33fc95d8293cfca352ac875668857293e22d7d51)
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.

--- 422 unchanged lines hidden (view full) ---

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 */
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.

--- 422 unchanged lines hidden (view full) ---

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)
439aa_state_t aa_dfa_match_len(struct aa_dfa *dfa, aa_state_t 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);
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;
446 aa_state_t state = start;
447
447
448 if (state == 0)
449 return 0;
448 if (state == DFA_NOMATCH)
449 return DFA_NOMATCH;
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++]);

--- 13 unchanged lines hidden (view full) ---

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 */
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++]);

--- 13 unchanged lines hidden (view full) ---

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)
479aa_state_t aa_dfa_match(struct aa_dfa *dfa, aa_state_t start, 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);
480{
481 u16 *def = DEFAULT_TABLE(dfa);
482 u32 *base = BASE_TABLE(dfa);
483 u16 *next = NEXT_TABLE(dfa);
484 u16 *check = CHECK_TABLE(dfa);
486 unsigned int state = start;
485 aa_state_t state = start;
487
486
488 if (state == 0)
489 return 0;
487 if (state == DFA_NOMATCH)
488 return DFA_NOMATCH;
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,

--- 12 unchanged lines hidden (view full) ---

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 */
489
490 /* current state is <state>, matching character *str */
491 if (dfa->tables[YYTD_ID_EC]) {
492 /* Equivalence class table defined */
493 u8 *equiv = EQUIV_TABLE(dfa);
494 /* default is direct to next state */
495 while (*str)
496 match_char(state, def, base, next, check,

--- 12 unchanged lines hidden (view full) ---

509 * @dfa: the dfa to traverse (NOT NULL)
510 * @state: the state to start in
511 * @c: the input character to transition on
512 *
513 * aa_dfa_match will step through the dfa by one input character @c
514 *
515 * Returns: state reach after input @c
516 */
518unsigned int aa_dfa_next(struct aa_dfa *dfa, unsigned int state,
519 const char c)
517aa_state_t aa_dfa_next(struct aa_dfa *dfa, aa_state_t state, 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
518{
519 u16 *def = DEFAULT_TABLE(dfa);
520 u32 *base = BASE_TABLE(dfa);
521 u16 *next = NEXT_TABLE(dfa);
522 u16 *check = CHECK_TABLE(dfa);
523
524 /* current state is <state>, matching character *str */
525 if (dfa->tables[YYTD_ID_EC]) {
526 /* Equivalence class table defined */
527 u8 *equiv = EQUIV_TABLE(dfa);
528 match_char(state, def, base, next, check, equiv[(u8) c]);
529 } else
530 match_char(state, def, base, next, check, (u8) c);
531
532 return state;
533}
534
537unsigned int aa_dfa_outofband_transition(struct aa_dfa *dfa, unsigned int state)
535aa_state_t aa_dfa_outofband_transition(struct aa_dfa *dfa, aa_state_t 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))

--- 13 unchanged lines hidden (view full) ---

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 */
536{
537 u16 *def = DEFAULT_TABLE(dfa);
538 u32 *base = BASE_TABLE(dfa);
539 u16 *next = NEXT_TABLE(dfa);
540 u16 *check = CHECK_TABLE(dfa);
541 u32 b = (base)[(state)];
542
543 if (!(b & MATCH_FLAG_OOB_TRANSITION))

--- 13 unchanged lines hidden (view full) ---

557 * @retpos: first character in str after match OR end of string
558 *
559 * aa_dfa_match will match @str against the dfa and return the state it
560 * finished matching in. The final state can be used to look up the accepting
561 * label, or as the start state of a continuing match.
562 *
563 * Returns: final state reached after input is consumed
564 */
567unsigned int aa_dfa_match_until(struct aa_dfa *dfa, unsigned int start,
565aa_state_t aa_dfa_match_until(struct aa_dfa *dfa, aa_state_t 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);
566 const char *str, const char **retpos)
567{
568 u16 *def = DEFAULT_TABLE(dfa);
569 u32 *base = BASE_TABLE(dfa);
570 u16 *next = NEXT_TABLE(dfa);
571 u16 *check = CHECK_TABLE(dfa);
572 u32 *accept = ACCEPT_TABLE(dfa);
575 unsigned int state = start, pos;
573 aa_state_t state = start, pos;
576
574
577 if (state == 0)
578 return 0;
575 if (state == DFA_NOMATCH)
576 return DFA_NOMATCH;
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++];

--- 33 unchanged lines hidden (view full) ---

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 */
577
578 /* current state is <state>, matching character *str */
579 if (dfa->tables[YYTD_ID_EC]) {
580 /* Equivalence class table defined */
581 u8 *equiv = EQUIV_TABLE(dfa);
582 /* default is direct to next state */
583 while (*str) {
584 pos = base_idx(base[state]) + equiv[(u8) *str++];

--- 33 unchanged lines hidden (view full) ---

618 * finished matching in. The final state can be used to look up the accepting
619 * label, or as the start state of a continuing match.
620 *
621 * This function will happily match again the 0 byte and only finishes
622 * when @n input is consumed.
623 *
624 * Returns: final state reached after input is consumed
625 */
628unsigned int aa_dfa_matchn_until(struct aa_dfa *dfa, unsigned int start,
626aa_state_t aa_dfa_matchn_until(struct aa_dfa *dfa, aa_state_t 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);
627 const char *str, int n, const char **retpos)
628{
629 u16 *def = DEFAULT_TABLE(dfa);
630 u32 *base = BASE_TABLE(dfa);
631 u16 *next = NEXT_TABLE(dfa);
632 u16 *check = CHECK_TABLE(dfa);
633 u32 *accept = ACCEPT_TABLE(dfa);
636 unsigned int state = start, pos;
634 aa_state_t state = start, pos;
637
638 *retpos = NULL;
635
636 *retpos = NULL;
639 if (state == 0)
640 return 0;
637 if (state == DFA_NOMATCH)
638 return DFA_NOMATCH;
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++];

--- 23 unchanged lines hidden (view full) ---

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 */
639
640 /* current state is <state>, matching character *str */
641 if (dfa->tables[YYTD_ID_EC]) {
642 /* Equivalence class table defined */
643 u8 *equiv = EQUIV_TABLE(dfa);
644 /* default is direct to next state */
645 for (; n; n--) {
646 pos = base_idx(base[state]) + equiv[(u8) *str++];

--- 23 unchanged lines hidden (view full) ---

670
671#define inc_wb_pos(wb) \
672do { \
673 wb->pos = (wb->pos + 1) & (WB_HISTORY_SIZE - 1); \
674 wb->len = (wb->len + 1) & (WB_HISTORY_SIZE - 1); \
675} while (0)
676
677/* For DFAs that don't support extended tagging of states */
680static bool is_loop(struct match_workbuf *wb, unsigned int state,
678static bool is_loop(struct match_workbuf *wb, aa_state_t state,
681 unsigned int *adjust)
682{
679 unsigned int *adjust)
680{
683 unsigned int pos = wb->pos;
684 unsigned int i;
681 aa_state_t pos = wb->pos;
682 aa_state_t 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
683
684 if (wb->history[pos] < state)
685 return false;
686
687 for (i = 0; i <= wb->len; i++) {
688 if (wb->history[pos] == state) {
689 *adjust = i;
690 return true;
691 }
692 if (pos == 0)
693 pos = WB_HISTORY_SIZE;
694 pos--;
695 }
696
697 *adjust = i;
698 return true;
699}
700
703static unsigned int leftmatch_fb(struct aa_dfa *dfa, unsigned int start,
701static aa_state_t leftmatch_fb(struct aa_dfa *dfa, aa_state_t 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);
702 const char *str, struct match_workbuf *wb,
703 unsigned int *count)
704{
705 u16 *def = DEFAULT_TABLE(dfa);
706 u32 *base = BASE_TABLE(dfa);
707 u16 *next = NEXT_TABLE(dfa);
708 u16 *check = CHECK_TABLE(dfa);
711 unsigned int state = start, pos;
709 aa_state_t state = start, pos;
712
713 AA_BUG(!dfa);
714 AA_BUG(!str);
715 AA_BUG(!wb);
716 AA_BUG(!count);
717
718 *count = 0;
710
711 AA_BUG(!dfa);
712 AA_BUG(!str);
713 AA_BUG(!wb);
714 AA_BUG(!count);
715
716 *count = 0;
719 if (state == 0)
720 return 0;
717 if (state == DFA_NOMATCH)
718 return DFA_NOMATCH;
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;

--- 47 unchanged lines hidden (view full) ---

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 */
719
720 /* current state is <state>, matching character *str */
721 if (dfa->tables[YYTD_ID_EC]) {
722 /* Equivalence class table defined */
723 u8 *equiv = EQUIV_TABLE(dfa);
724 /* default is direct to next state */
725 while (*str) {
726 unsigned int adjust;

--- 47 unchanged lines hidden (view full) ---

774 * @count: current count of longest left.
775 *
776 * aa_dfa_match will match @str against the dfa and return the state it
777 * finished matching in. The final state can be used to look up the accepting
778 * label, or as the start state of a continuing match.
779 *
780 * Returns: final state reached after input is consumed
781 */
784unsigned int aa_dfa_leftmatch(struct aa_dfa *dfa, unsigned int start,
785 const char *str, unsigned int *count)
782aa_state_t aa_dfa_leftmatch(struct aa_dfa *dfa, aa_state_t start,
783 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}
784{
785 DEFINE_MATCH_WB(wb);
786
787 /* TODO: match for extended state dfas */
788
789 return leftmatch_fb(dfa, start, str, &wb, count);
790}