Lines Matching refs:dfa
5 * This file contains AppArmor dfa based regular expression matching engine
69 * unpack_table - unpack a dfa table (one of accept, default, base, next check)
139 * @tables - array of dfa tables to check (NOT NULL)
142 * Assumes dfa has gone through the first pass verification done by unpacking
190 * @dfa: dfa to test (NOT NULL)
192 * Assumes dfa has gone through the first pass verification done by unpacking
197 static int verify_dfa(struct aa_dfa *dfa)
202 state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
203 trans_count = dfa->tables[YYTD_ID_NXT]->td_lolen;
207 if (!(BASE_TABLE(dfa)[i] & MATCH_FLAG_DIFF_ENCODE) &&
208 (DEFAULT_TABLE(dfa)[i] >= state_count))
210 if (BASE_TABLE(dfa)[i] & MATCH_FLAGS_INVALID) {
214 if ((BASE_TABLE(dfa)[i] & MATCH_FLAG_DIFF_ENCODE)) {
215 if (!(dfa->flags & YYTH_FLAG_DIFF_ENCODE)) {
220 if ((BASE_TABLE(dfa)[i] & MATCH_FLAG_OOB_TRANSITION)) {
221 if (base_idx(BASE_TABLE(dfa)[i]) < dfa->max_oob) {
225 if (!(dfa->flags & YYTH_FLAG_OOB_TRANS)) {
230 if (base_idx(BASE_TABLE(dfa)[i]) + 255 >= trans_count) {
237 if (NEXT_TABLE(dfa)[i] >= state_count)
239 if (CHECK_TABLE(dfa)[i] >= state_count)
248 (BASE_TABLE(dfa)[j] & MATCH_FLAG_DIFF_ENCODE) &&
249 !(BASE_TABLE(dfa)[j] & MARK_DIFF_ENCODE);
251 k = DEFAULT_TABLE(dfa)[j];
256 BASE_TABLE(dfa)[j] |= MARK_DIFF_ENCODE;
266 * dfa_free - free a dfa allocated by aa_dfa_unpack
267 * @dfa: the dfa to free (MAYBE NULL)
269 * Requires: reference count to dfa == 0
271 static void dfa_free(struct aa_dfa *dfa)
273 if (dfa) {
276 for (i = 0; i < ARRAY_SIZE(dfa->tables); i++) {
277 kvfree(dfa->tables[i]);
278 dfa->tables[i] = NULL;
280 kfree(dfa);
286 * @kr: kref callback for freeing of a dfa (NOT NULL)
290 struct aa_dfa *dfa = container_of(kref, struct aa_dfa, count);
291 dfa_free(dfa);
295 * aa_dfa_unpack - unpack the binary tables of a serialized dfa
300 * Unpack a dfa that has been serialized. To find information on the dfa
302 * Assumes the dfa @blob stream has been aligned on a 8 byte boundary
304 * Returns: an unpacked dfa ready for matching or ERR_PTR on failure
312 struct aa_dfa *dfa = kzalloc(sizeof(struct aa_dfa), GFP_KERNEL);
313 if (!dfa)
316 kref_init(&dfa->count);
320 /* get dfa table set header */
331 dfa->flags = ntohs(*(__be16 *) (data + 12));
332 if (dfa->flags & ~(YYTH_FLAGS))
336 * TODO: needed for dfa to support more than 1 oob
337 * if (dfa->flags & YYTH_FLAGS_OOB_TRANS) {
340 * dfa->max_oob = ntol(*(__be32 *) (data + 16));
341 * if (dfa->max <= MAX_OOB_SUPPORTED) {
347 dfa->max_oob = 1;
384 if (dfa->tables[table->td_id])
386 dfa->tables[table->td_id] = table;
391 error = verify_table_headers(dfa->tables, flags);
396 error = verify_dfa(dfa);
401 return dfa;
405 dfa_free(dfa);
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)
430 * aa_dfa_match_len will match @str against the dfa and return the state it
439 aa_state_t aa_dfa_match_len(struct aa_dfa *dfa, aa_state_t start,
442 u16 *def = DEFAULT_TABLE(dfa);
443 u32 *base = BASE_TABLE(dfa);
444 u16 *next = NEXT_TABLE(dfa);
445 u16 *check = CHECK_TABLE(dfa);
452 if (dfa->tables[YYTD_ID_EC]) {
454 u8 *equiv = EQUIV_TABLE(dfa);
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)
473 * aa_dfa_match will match @str against the dfa and return the state it
479 aa_state_t aa_dfa_match(struct aa_dfa *dfa, aa_state_t start, const char *str)
481 u16 *def = DEFAULT_TABLE(dfa);
482 u32 *base = BASE_TABLE(dfa);
483 u16 *next = NEXT_TABLE(dfa);
484 u16 *check = CHECK_TABLE(dfa);
491 if (dfa->tables[YYTD_ID_EC]) {
493 u8 *equiv = EQUIV_TABLE(dfa);
508 * aa_dfa_next - step one character to the next state in the dfa
509 * @dfa: the dfa to traverse (NOT NULL)
513 * aa_dfa_match will step through the dfa by one input character @c
517 aa_state_t aa_dfa_next(struct aa_dfa *dfa, aa_state_t state, const char c)
519 u16 *def = DEFAULT_TABLE(dfa);
520 u32 *base = BASE_TABLE(dfa);
521 u16 *next = NEXT_TABLE(dfa);
522 u16 *check = CHECK_TABLE(dfa);
525 if (dfa->tables[YYTD_ID_EC]) {
527 u8 *equiv = EQUIV_TABLE(dfa);
535 aa_state_t aa_dfa_outofband_transition(struct aa_dfa *dfa, aa_state_t state)
537 u16 *def = DEFAULT_TABLE(dfa);
538 u32 *base = BASE_TABLE(dfa);
539 u16 *next = NEXT_TABLE(dfa);
540 u16 *check = CHECK_TABLE(dfa);
553 * aa_dfa_match_until - traverse @dfa until accept state or end of input
554 * @dfa: the dfa to match @str against (NOT NULL)
555 * @start: the state of the dfa to start matching in
556 * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
559 * aa_dfa_match will match @str against the dfa and return the state it
565 aa_state_t aa_dfa_match_until(struct aa_dfa *dfa, aa_state_t start,
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);
579 if (dfa->tables[YYTD_ID_EC]) {
581 u8 *equiv = EQUIV_TABLE(dfa);
610 * aa_dfa_matchn_until - traverse @dfa until accept or @n bytes consumed
611 * @dfa: the dfa to match @str against (NOT NULL)
612 * @start: the state of the dfa to start matching in
613 * @str: the string of bytes to match against the dfa (NOT NULL)
617 * aa_dfa_match_len will match @str against the dfa and return the state it
626 aa_state_t aa_dfa_matchn_until(struct aa_dfa *dfa, aa_state_t start,
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);
641 if (dfa->tables[YYTD_ID_EC]) {
643 u8 *equiv = EQUIV_TABLE(dfa);
701 static aa_state_t leftmatch_fb(struct aa_dfa *dfa, aa_state_t start,
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 AA_BUG(!dfa);
721 if (dfa->tables[YYTD_ID_EC]) {
723 u8 *equiv = EQUIV_TABLE(dfa);
735 state = aa_dfa_match(dfa, state, str);
754 state = aa_dfa_match(dfa, state, str);
770 * aa_dfa_leftmatch - traverse @dfa to find state @str stops at
771 * @dfa: the dfa to match @str against (NOT NULL)
772 * @start: the state of the dfa to start matching in
773 * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
776 * aa_dfa_match will match @str against the dfa and return the state it
782 aa_state_t aa_dfa_leftmatch(struct aa_dfa *dfa, aa_state_t start,
789 return leftmatch_fb(dfa, start, str, &wb, count);