Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * AppArmor security module
0004  *
0005  * This file contains AppArmor dfa based regular expression matching engine
0006  *
0007  * Copyright (C) 1998-2008 Novell/SUSE
0008  * Copyright 2009-2012 Canonical Ltd.
0009  */
0010 
0011 #include <linux/errno.h>
0012 #include <linux/kernel.h>
0013 #include <linux/mm.h>
0014 #include <linux/slab.h>
0015 #include <linux/vmalloc.h>
0016 #include <linux/err.h>
0017 #include <linux/kref.h>
0018 
0019 #include "include/lib.h"
0020 #include "include/match.h"
0021 
0022 #define base_idx(X) ((X) & 0xffffff)
0023 
0024 static char nulldfa_src[] = {
0025     #include "nulldfa.in"
0026 };
0027 struct aa_dfa *nulldfa;
0028 
0029 static char stacksplitdfa_src[] = {
0030     #include "stacksplitdfa.in"
0031 };
0032 struct aa_dfa *stacksplitdfa;
0033 
0034 int aa_setup_dfa_engine(void)
0035 {
0036     int error;
0037 
0038     nulldfa = aa_dfa_unpack(nulldfa_src, sizeof(nulldfa_src),
0039                 TO_ACCEPT1_FLAG(YYTD_DATA32) |
0040                 TO_ACCEPT2_FLAG(YYTD_DATA32));
0041     if (IS_ERR(nulldfa)) {
0042         error = PTR_ERR(nulldfa);
0043         nulldfa = NULL;
0044         return error;
0045     }
0046 
0047     stacksplitdfa = aa_dfa_unpack(stacksplitdfa_src,
0048                       sizeof(stacksplitdfa_src),
0049                       TO_ACCEPT1_FLAG(YYTD_DATA32) |
0050                       TO_ACCEPT2_FLAG(YYTD_DATA32));
0051     if (IS_ERR(stacksplitdfa)) {
0052         aa_put_dfa(nulldfa);
0053         nulldfa = NULL;
0054         error = PTR_ERR(stacksplitdfa);
0055         stacksplitdfa = NULL;
0056         return error;
0057     }
0058 
0059     return 0;
0060 }
0061 
0062 void aa_teardown_dfa_engine(void)
0063 {
0064     aa_put_dfa(stacksplitdfa);
0065     aa_put_dfa(nulldfa);
0066 }
0067 
0068 /**
0069  * unpack_table - unpack a dfa table (one of accept, default, base, next check)
0070  * @blob: data to unpack (NOT NULL)
0071  * @bsize: size of blob
0072  *
0073  * Returns: pointer to table else NULL on failure
0074  *
0075  * NOTE: must be freed by kvfree (not kfree)
0076  */
0077 static struct table_header *unpack_table(char *blob, size_t bsize)
0078 {
0079     struct table_header *table = NULL;
0080     struct table_header th;
0081     size_t tsize;
0082 
0083     if (bsize < sizeof(struct table_header))
0084         goto out;
0085 
0086     /* loaded td_id's start at 1, subtract 1 now to avoid doing
0087      * it every time we use td_id as an index
0088      */
0089     th.td_id = be16_to_cpu(*(__be16 *) (blob)) - 1;
0090     if (th.td_id > YYTD_ID_MAX)
0091         goto out;
0092     th.td_flags = be16_to_cpu(*(__be16 *) (blob + 2));
0093     th.td_lolen = be32_to_cpu(*(__be32 *) (blob + 8));
0094     blob += sizeof(struct table_header);
0095 
0096     if (!(th.td_flags == YYTD_DATA16 || th.td_flags == YYTD_DATA32 ||
0097           th.td_flags == YYTD_DATA8))
0098         goto out;
0099 
0100     /* if we have a table it must have some entries */
0101     if (th.td_lolen == 0)
0102         goto out;
0103     tsize = table_size(th.td_lolen, th.td_flags);
0104     if (bsize < tsize)
0105         goto out;
0106 
0107     table = kvzalloc(tsize, GFP_KERNEL);
0108     if (table) {
0109         table->td_id = th.td_id;
0110         table->td_flags = th.td_flags;
0111         table->td_lolen = th.td_lolen;
0112         if (th.td_flags == YYTD_DATA8)
0113             UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
0114                      u8, u8, byte_to_byte);
0115         else if (th.td_flags == YYTD_DATA16)
0116             UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
0117                      u16, __be16, be16_to_cpu);
0118         else if (th.td_flags == YYTD_DATA32)
0119             UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
0120                      u32, __be32, be32_to_cpu);
0121         else
0122             goto fail;
0123         /* if table was vmalloced make sure the page tables are synced
0124          * before it is used, as it goes live to all cpus.
0125          */
0126         if (is_vmalloc_addr(table))
0127             vm_unmap_aliases();
0128     }
0129 
0130 out:
0131     return table;
0132 fail:
0133     kvfree(table);
0134     return NULL;
0135 }
0136 
0137 /**
0138  * verify_table_headers - verify that the tables headers are as expected
0139  * @tables - array of dfa tables to check (NOT NULL)
0140  * @flags: flags controlling what type of accept table are acceptable
0141  *
0142  * Assumes dfa has gone through the first pass verification done by unpacking
0143  * NOTE: this does not valid accept table values
0144  *
0145  * Returns: %0 else error code on failure to verify
0146  */
0147 static int verify_table_headers(struct table_header **tables, int flags)
0148 {
0149     size_t state_count, trans_count;
0150     int error = -EPROTO;
0151 
0152     /* check that required tables exist */
0153     if (!(tables[YYTD_ID_DEF] && tables[YYTD_ID_BASE] &&
0154           tables[YYTD_ID_NXT] && tables[YYTD_ID_CHK]))
0155         goto out;
0156 
0157     /* accept.size == default.size == base.size */
0158     state_count = tables[YYTD_ID_BASE]->td_lolen;
0159     if (ACCEPT1_FLAGS(flags)) {
0160         if (!tables[YYTD_ID_ACCEPT])
0161             goto out;
0162         if (state_count != tables[YYTD_ID_ACCEPT]->td_lolen)
0163             goto out;
0164     }
0165     if (ACCEPT2_FLAGS(flags)) {
0166         if (!tables[YYTD_ID_ACCEPT2])
0167             goto out;
0168         if (state_count != tables[YYTD_ID_ACCEPT2]->td_lolen)
0169             goto out;
0170     }
0171     if (state_count != tables[YYTD_ID_DEF]->td_lolen)
0172         goto out;
0173 
0174     /* next.size == chk.size */
0175     trans_count = tables[YYTD_ID_NXT]->td_lolen;
0176     if (trans_count != tables[YYTD_ID_CHK]->td_lolen)
0177         goto out;
0178 
0179     /* if equivalence classes then its table size must be 256 */
0180     if (tables[YYTD_ID_EC] && tables[YYTD_ID_EC]->td_lolen != 256)
0181         goto out;
0182 
0183     error = 0;
0184 out:
0185     return error;
0186 }
0187 
0188 /**
0189  * verify_dfa - verify that transitions and states in the tables are in bounds.
0190  * @dfa: dfa to test  (NOT NULL)
0191  *
0192  * Assumes dfa has gone through the first pass verification done by unpacking
0193  * NOTE: this does not valid accept table values
0194  *
0195  * Returns: %0 else error code on failure to verify
0196  */
0197 static int verify_dfa(struct aa_dfa *dfa)
0198 {
0199     size_t i, state_count, trans_count;
0200     int error = -EPROTO;
0201 
0202     state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
0203     trans_count = dfa->tables[YYTD_ID_NXT]->td_lolen;
0204     if (state_count == 0)
0205         goto out;
0206     for (i = 0; i < state_count; i++) {
0207         if (!(BASE_TABLE(dfa)[i] & MATCH_FLAG_DIFF_ENCODE) &&
0208             (DEFAULT_TABLE(dfa)[i] >= state_count))
0209             goto out;
0210         if (BASE_TABLE(dfa)[i] & MATCH_FLAGS_INVALID) {
0211             pr_err("AppArmor DFA state with invalid match flags");
0212             goto out;
0213         }
0214         if ((BASE_TABLE(dfa)[i] & MATCH_FLAG_DIFF_ENCODE)) {
0215             if (!(dfa->flags & YYTH_FLAG_DIFF_ENCODE)) {
0216                 pr_err("AppArmor DFA diff encoded transition state without header flag");
0217                 goto out;
0218             }
0219         }
0220         if ((BASE_TABLE(dfa)[i] & MATCH_FLAG_OOB_TRANSITION)) {
0221             if (base_idx(BASE_TABLE(dfa)[i]) < dfa->max_oob) {
0222                 pr_err("AppArmor DFA out of bad transition out of range");
0223                 goto out;
0224             }
0225             if (!(dfa->flags & YYTH_FLAG_OOB_TRANS)) {
0226                 pr_err("AppArmor DFA out of bad transition state without header flag");
0227                 goto out;
0228             }
0229         }
0230         if (base_idx(BASE_TABLE(dfa)[i]) + 255 >= trans_count) {
0231             pr_err("AppArmor DFA next/check upper bounds error\n");
0232             goto out;
0233         }
0234     }
0235 
0236     for (i = 0; i < trans_count; i++) {
0237         if (NEXT_TABLE(dfa)[i] >= state_count)
0238             goto out;
0239         if (CHECK_TABLE(dfa)[i] >= state_count)
0240             goto out;
0241     }
0242 
0243     /* Now that all the other tables are verified, verify diffencoding */
0244     for (i = 0; i < state_count; i++) {
0245         size_t j, k;
0246 
0247         for (j = i;
0248              (BASE_TABLE(dfa)[j] & MATCH_FLAG_DIFF_ENCODE) &&
0249              !(BASE_TABLE(dfa)[j] & MARK_DIFF_ENCODE);
0250              j = k) {
0251             k = DEFAULT_TABLE(dfa)[j];
0252             if (j == k)
0253                 goto out;
0254             if (k < j)
0255                 break;      /* already verified */
0256             BASE_TABLE(dfa)[j] |= MARK_DIFF_ENCODE;
0257         }
0258     }
0259     error = 0;
0260 
0261 out:
0262     return error;
0263 }
0264 
0265 /**
0266  * dfa_free - free a dfa allocated by aa_dfa_unpack
0267  * @dfa: the dfa to free  (MAYBE NULL)
0268  *
0269  * Requires: reference count to dfa == 0
0270  */
0271 static void dfa_free(struct aa_dfa *dfa)
0272 {
0273     if (dfa) {
0274         int i;
0275 
0276         for (i = 0; i < ARRAY_SIZE(dfa->tables); i++) {
0277             kvfree(dfa->tables[i]);
0278             dfa->tables[i] = NULL;
0279         }
0280         kfree(dfa);
0281     }
0282 }
0283 
0284 /**
0285  * aa_dfa_free_kref - free aa_dfa by kref (called by aa_put_dfa)
0286  * @kr: kref callback for freeing of a dfa  (NOT NULL)
0287  */
0288 void aa_dfa_free_kref(struct kref *kref)
0289 {
0290     struct aa_dfa *dfa = container_of(kref, struct aa_dfa, count);
0291     dfa_free(dfa);
0292 }
0293 
0294 /**
0295  * aa_dfa_unpack - unpack the binary tables of a serialized dfa
0296  * @blob: aligned serialized stream of data to unpack  (NOT NULL)
0297  * @size: size of data to unpack
0298  * @flags: flags controlling what type of accept tables are acceptable
0299  *
0300  * Unpack a dfa that has been serialized.  To find information on the dfa
0301  * format look in Documentation/admin-guide/LSM/apparmor.rst
0302  * Assumes the dfa @blob stream has been aligned on a 8 byte boundary
0303  *
0304  * Returns: an unpacked dfa ready for matching or ERR_PTR on failure
0305  */
0306 struct aa_dfa *aa_dfa_unpack(void *blob, size_t size, int flags)
0307 {
0308     int hsize;
0309     int error = -ENOMEM;
0310     char *data = blob;
0311     struct table_header *table = NULL;
0312     struct aa_dfa *dfa = kzalloc(sizeof(struct aa_dfa), GFP_KERNEL);
0313     if (!dfa)
0314         goto fail;
0315 
0316     kref_init(&dfa->count);
0317 
0318     error = -EPROTO;
0319 
0320     /* get dfa table set header */
0321     if (size < sizeof(struct table_set_header))
0322         goto fail;
0323 
0324     if (ntohl(*(__be32 *) data) != YYTH_MAGIC)
0325         goto fail;
0326 
0327     hsize = ntohl(*(__be32 *) (data + 4));
0328     if (size < hsize)
0329         goto fail;
0330 
0331     dfa->flags = ntohs(*(__be16 *) (data + 12));
0332     if (dfa->flags & ~(YYTH_FLAGS))
0333         goto fail;
0334 
0335     /*
0336      * TODO: needed for dfa to support more than 1 oob
0337      * if (dfa->flags & YYTH_FLAGS_OOB_TRANS) {
0338      *  if (hsize < 16 + 4)
0339      *      goto fail;
0340      *  dfa->max_oob = ntol(*(__be32 *) (data + 16));
0341      *  if (dfa->max <= MAX_OOB_SUPPORTED) {
0342      *      pr_err("AppArmor DFA OOB greater than supported\n");
0343      *      goto fail;
0344      *  }
0345      * }
0346      */
0347     dfa->max_oob = 1;
0348 
0349     data += hsize;
0350     size -= hsize;
0351 
0352     while (size > 0) {
0353         table = unpack_table(data, size);
0354         if (!table)
0355             goto fail;
0356 
0357         switch (table->td_id) {
0358         case YYTD_ID_ACCEPT:
0359             if (!(table->td_flags & ACCEPT1_FLAGS(flags)))
0360                 goto fail;
0361             break;
0362         case YYTD_ID_ACCEPT2:
0363             if (!(table->td_flags & ACCEPT2_FLAGS(flags)))
0364                 goto fail;
0365             break;
0366         case YYTD_ID_BASE:
0367             if (table->td_flags != YYTD_DATA32)
0368                 goto fail;
0369             break;
0370         case YYTD_ID_DEF:
0371         case YYTD_ID_NXT:
0372         case YYTD_ID_CHK:
0373             if (table->td_flags != YYTD_DATA16)
0374                 goto fail;
0375             break;
0376         case YYTD_ID_EC:
0377             if (table->td_flags != YYTD_DATA8)
0378                 goto fail;
0379             break;
0380         default:
0381             goto fail;
0382         }
0383         /* check for duplicate table entry */
0384         if (dfa->tables[table->td_id])
0385             goto fail;
0386         dfa->tables[table->td_id] = table;
0387         data += table_size(table->td_lolen, table->td_flags);
0388         size -= table_size(table->td_lolen, table->td_flags);
0389         table = NULL;
0390     }
0391     error = verify_table_headers(dfa->tables, flags);
0392     if (error)
0393         goto fail;
0394 
0395     if (flags & DFA_FLAG_VERIFY_STATES) {
0396         error = verify_dfa(dfa);
0397         if (error)
0398             goto fail;
0399     }
0400 
0401     return dfa;
0402 
0403 fail:
0404     kvfree(table);
0405     dfa_free(dfa);
0406     return ERR_PTR(error);
0407 }
0408 
0409 #define match_char(state, def, base, next, check, C)    \
0410 do {                            \
0411     u32 b = (base)[(state)];            \
0412     unsigned int pos = base_idx(b) + (C);       \
0413     if ((check)[pos] != (state)) {          \
0414         (state) = (def)[(state)];       \
0415         if (b & MATCH_FLAG_DIFF_ENCODE)     \
0416             continue;           \
0417         break;                  \
0418     }                       \
0419     (state) = (next)[pos];              \
0420     break;                      \
0421 } while (1)
0422 
0423 /**
0424  * aa_dfa_match_len - traverse @dfa to find state @str stops at
0425  * @dfa: the dfa to match @str against  (NOT NULL)
0426  * @start: the state of the dfa to start matching in
0427  * @str: the string of bytes to match against the dfa  (NOT NULL)
0428  * @len: length of the string of bytes to match
0429  *
0430  * aa_dfa_match_len will match @str against the dfa and return the state it
0431  * finished matching in. The final state can be used to look up the accepting
0432  * label, or as the start state of a continuing match.
0433  *
0434  * This function will happily match again the 0 byte and only finishes
0435  * when @len input is consumed.
0436  *
0437  * Returns: final state reached after input is consumed
0438  */
0439 unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int start,
0440                   const char *str, int len)
0441 {
0442     u16 *def = DEFAULT_TABLE(dfa);
0443     u32 *base = BASE_TABLE(dfa);
0444     u16 *next = NEXT_TABLE(dfa);
0445     u16 *check = CHECK_TABLE(dfa);
0446     unsigned int state = start;
0447 
0448     if (state == 0)
0449         return 0;
0450 
0451     /* current state is <state>, matching character *str */
0452     if (dfa->tables[YYTD_ID_EC]) {
0453         /* Equivalence class table defined */
0454         u8 *equiv = EQUIV_TABLE(dfa);
0455         for (; len; len--)
0456             match_char(state, def, base, next, check,
0457                    equiv[(u8) *str++]);
0458     } else {
0459         /* default is direct to next state */
0460         for (; len; len--)
0461             match_char(state, def, base, next, check, (u8) *str++);
0462     }
0463 
0464     return state;
0465 }
0466 
0467 /**
0468  * aa_dfa_match - traverse @dfa to find state @str stops at
0469  * @dfa: the dfa to match @str against  (NOT NULL)
0470  * @start: the state of the dfa to start matching in
0471  * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
0472  *
0473  * aa_dfa_match will match @str against the dfa and return the state it
0474  * finished matching in. The final state can be used to look up the accepting
0475  * label, or as the start state of a continuing match.
0476  *
0477  * Returns: final state reached after input is consumed
0478  */
0479 unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start,
0480               const char *str)
0481 {
0482     u16 *def = DEFAULT_TABLE(dfa);
0483     u32 *base = BASE_TABLE(dfa);
0484     u16 *next = NEXT_TABLE(dfa);
0485     u16 *check = CHECK_TABLE(dfa);
0486     unsigned int state = start;
0487 
0488     if (state == 0)
0489         return 0;
0490 
0491     /* current state is <state>, matching character *str */
0492     if (dfa->tables[YYTD_ID_EC]) {
0493         /* Equivalence class table defined */
0494         u8 *equiv = EQUIV_TABLE(dfa);
0495         /* default is direct to next state */
0496         while (*str)
0497             match_char(state, def, base, next, check,
0498                    equiv[(u8) *str++]);
0499     } else {
0500         /* default is direct to next state */
0501         while (*str)
0502             match_char(state, def, base, next, check, (u8) *str++);
0503     }
0504 
0505     return state;
0506 }
0507 
0508 /**
0509  * aa_dfa_next - step one character to the next state in the dfa
0510  * @dfa: the dfa to traverse (NOT NULL)
0511  * @state: the state to start in
0512  * @c: the input character to transition on
0513  *
0514  * aa_dfa_match will step through the dfa by one input character @c
0515  *
0516  * Returns: state reach after input @c
0517  */
0518 unsigned int aa_dfa_next(struct aa_dfa *dfa, unsigned int state,
0519               const char c)
0520 {
0521     u16 *def = DEFAULT_TABLE(dfa);
0522     u32 *base = BASE_TABLE(dfa);
0523     u16 *next = NEXT_TABLE(dfa);
0524     u16 *check = CHECK_TABLE(dfa);
0525 
0526     /* current state is <state>, matching character *str */
0527     if (dfa->tables[YYTD_ID_EC]) {
0528         /* Equivalence class table defined */
0529         u8 *equiv = EQUIV_TABLE(dfa);
0530         match_char(state, def, base, next, check, equiv[(u8) c]);
0531     } else
0532         match_char(state, def, base, next, check, (u8) c);
0533 
0534     return state;
0535 }
0536 
0537 unsigned int aa_dfa_outofband_transition(struct aa_dfa *dfa, unsigned int state)
0538 {
0539     u16 *def = DEFAULT_TABLE(dfa);
0540     u32 *base = BASE_TABLE(dfa);
0541     u16 *next = NEXT_TABLE(dfa);
0542     u16 *check = CHECK_TABLE(dfa);
0543     u32 b = (base)[(state)];
0544 
0545     if (!(b & MATCH_FLAG_OOB_TRANSITION))
0546         return DFA_NOMATCH;
0547 
0548     /* No Equivalence class remapping for outofband transitions */
0549     match_char(state, def, base, next, check, -1);
0550 
0551     return state;
0552 }
0553 
0554 /**
0555  * aa_dfa_match_until - traverse @dfa until accept state or end of input
0556  * @dfa: the dfa to match @str against  (NOT NULL)
0557  * @start: the state of the dfa to start matching in
0558  * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
0559  * @retpos: first character in str after match OR end of string
0560  *
0561  * aa_dfa_match will match @str against the dfa and return the state it
0562  * finished matching in. The final state can be used to look up the accepting
0563  * label, or as the start state of a continuing match.
0564  *
0565  * Returns: final state reached after input is consumed
0566  */
0567 unsigned int aa_dfa_match_until(struct aa_dfa *dfa, unsigned int start,
0568                 const char *str, const char **retpos)
0569 {
0570     u16 *def = DEFAULT_TABLE(dfa);
0571     u32 *base = BASE_TABLE(dfa);
0572     u16 *next = NEXT_TABLE(dfa);
0573     u16 *check = CHECK_TABLE(dfa);
0574     u32 *accept = ACCEPT_TABLE(dfa);
0575     unsigned int state = start, pos;
0576 
0577     if (state == 0)
0578         return 0;
0579 
0580     /* current state is <state>, matching character *str */
0581     if (dfa->tables[YYTD_ID_EC]) {
0582         /* Equivalence class table defined */
0583         u8 *equiv = EQUIV_TABLE(dfa);
0584         /* default is direct to next state */
0585         while (*str) {
0586             pos = base_idx(base[state]) + equiv[(u8) *str++];
0587             if (check[pos] == state)
0588                 state = next[pos];
0589             else
0590                 state = def[state];
0591             if (accept[state])
0592                 break;
0593         }
0594     } else {
0595         /* default is direct to next state */
0596         while (*str) {
0597             pos = base_idx(base[state]) + (u8) *str++;
0598             if (check[pos] == state)
0599                 state = next[pos];
0600             else
0601                 state = def[state];
0602             if (accept[state])
0603                 break;
0604         }
0605     }
0606 
0607     *retpos = str;
0608     return state;
0609 }
0610 
0611 /**
0612  * aa_dfa_matchn_until - traverse @dfa until accept or @n bytes consumed
0613  * @dfa: the dfa to match @str against  (NOT NULL)
0614  * @start: the state of the dfa to start matching in
0615  * @str: the string of bytes to match against the dfa  (NOT NULL)
0616  * @n: length of the string of bytes to match
0617  * @retpos: first character in str after match OR str + n
0618  *
0619  * aa_dfa_match_len will match @str against the dfa and return the state it
0620  * finished matching in. The final state can be used to look up the accepting
0621  * label, or as the start state of a continuing match.
0622  *
0623  * This function will happily match again the 0 byte and only finishes
0624  * when @n input is consumed.
0625  *
0626  * Returns: final state reached after input is consumed
0627  */
0628 unsigned int aa_dfa_matchn_until(struct aa_dfa *dfa, unsigned int start,
0629                  const char *str, int n, const char **retpos)
0630 {
0631     u16 *def = DEFAULT_TABLE(dfa);
0632     u32 *base = BASE_TABLE(dfa);
0633     u16 *next = NEXT_TABLE(dfa);
0634     u16 *check = CHECK_TABLE(dfa);
0635     u32 *accept = ACCEPT_TABLE(dfa);
0636     unsigned int state = start, pos;
0637 
0638     *retpos = NULL;
0639     if (state == 0)
0640         return 0;
0641 
0642     /* current state is <state>, matching character *str */
0643     if (dfa->tables[YYTD_ID_EC]) {
0644         /* Equivalence class table defined */
0645         u8 *equiv = EQUIV_TABLE(dfa);
0646         /* default is direct to next state */
0647         for (; n; n--) {
0648             pos = base_idx(base[state]) + equiv[(u8) *str++];
0649             if (check[pos] == state)
0650                 state = next[pos];
0651             else
0652                 state = def[state];
0653             if (accept[state])
0654                 break;
0655         }
0656     } else {
0657         /* default is direct to next state */
0658         for (; n; n--) {
0659             pos = base_idx(base[state]) + (u8) *str++;
0660             if (check[pos] == state)
0661                 state = next[pos];
0662             else
0663                 state = def[state];
0664             if (accept[state])
0665                 break;
0666         }
0667     }
0668 
0669     *retpos = str;
0670     return state;
0671 }
0672 
0673 #define inc_wb_pos(wb)                      \
0674 do {                                \
0675     wb->pos = (wb->pos + 1) & (WB_HISTORY_SIZE - 1);        \
0676     wb->len = (wb->len + 1) & (WB_HISTORY_SIZE - 1);        \
0677 } while (0)
0678 
0679 /* For DFAs that don't support extended tagging of states */
0680 static bool is_loop(struct match_workbuf *wb, unsigned int state,
0681             unsigned int *adjust)
0682 {
0683     unsigned int pos = wb->pos;
0684     unsigned int i;
0685 
0686     if (wb->history[pos] < state)
0687         return false;
0688 
0689     for (i = 0; i <= wb->len; i++) {
0690         if (wb->history[pos] == state) {
0691             *adjust = i;
0692             return true;
0693         }
0694         if (pos == 0)
0695             pos = WB_HISTORY_SIZE;
0696         pos--;
0697     }
0698 
0699     *adjust = i;
0700     return true;
0701 }
0702 
0703 static unsigned int leftmatch_fb(struct aa_dfa *dfa, unsigned int start,
0704                  const char *str, struct match_workbuf *wb,
0705                  unsigned int *count)
0706 {
0707     u16 *def = DEFAULT_TABLE(dfa);
0708     u32 *base = BASE_TABLE(dfa);
0709     u16 *next = NEXT_TABLE(dfa);
0710     u16 *check = CHECK_TABLE(dfa);
0711     unsigned int state = start, pos;
0712 
0713     AA_BUG(!dfa);
0714     AA_BUG(!str);
0715     AA_BUG(!wb);
0716     AA_BUG(!count);
0717 
0718     *count = 0;
0719     if (state == 0)
0720         return 0;
0721 
0722     /* current state is <state>, matching character *str */
0723     if (dfa->tables[YYTD_ID_EC]) {
0724         /* Equivalence class table defined */
0725         u8 *equiv = EQUIV_TABLE(dfa);
0726         /* default is direct to next state */
0727         while (*str) {
0728             unsigned int adjust;
0729 
0730             wb->history[wb->pos] = state;
0731             pos = base_idx(base[state]) + equiv[(u8) *str++];
0732             if (check[pos] == state)
0733                 state = next[pos];
0734             else
0735                 state = def[state];
0736             if (is_loop(wb, state, &adjust)) {
0737                 state = aa_dfa_match(dfa, state, str);
0738                 *count -= adjust;
0739                 goto out;
0740             }
0741             inc_wb_pos(wb);
0742             (*count)++;
0743         }
0744     } else {
0745         /* default is direct to next state */
0746         while (*str) {
0747             unsigned int adjust;
0748 
0749             wb->history[wb->pos] = state;
0750             pos = base_idx(base[state]) + (u8) *str++;
0751             if (check[pos] == state)
0752                 state = next[pos];
0753             else
0754                 state = def[state];
0755             if (is_loop(wb, state, &adjust)) {
0756                 state = aa_dfa_match(dfa, state, str);
0757                 *count -= adjust;
0758                 goto out;
0759             }
0760             inc_wb_pos(wb);
0761             (*count)++;
0762         }
0763     }
0764 
0765 out:
0766     if (!state)
0767         *count = 0;
0768     return state;
0769 }
0770 
0771 /**
0772  * aa_dfa_leftmatch - traverse @dfa to find state @str stops at
0773  * @dfa: the dfa to match @str against  (NOT NULL)
0774  * @start: the state of the dfa to start matching in
0775  * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
0776  * @count: current count of longest left.
0777  *
0778  * aa_dfa_match will match @str against the dfa and return the state it
0779  * finished matching in. The final state can be used to look up the accepting
0780  * label, or as the start state of a continuing match.
0781  *
0782  * Returns: final state reached after input is consumed
0783  */
0784 unsigned int aa_dfa_leftmatch(struct aa_dfa *dfa, unsigned int start,
0785                   const char *str, unsigned int *count)
0786 {
0787     DEFINE_MATCH_WB(wb);
0788 
0789     /* TODO: match for extended state dfas */
0790 
0791     return leftmatch_fb(dfa, start, str, &wb, count);
0792 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!