security/apparmor/match.c

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