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