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  * aa_dfa_unpack - unpack the binary tables of a serialized dfa
 252  * @blob: aligned serialized stream of data to unpack  (NOT NULL)
 253  * @size: size of data to unpack
 254  * @flags: flags controlling what type of accept tables are acceptable
 255  *
 256  * Unpack a dfa that has been serialized.  To find information on the dfa
 257  * format look in Documentation/admin-guide/LSM/apparmor.rst
 258  * Assumes the dfa @blob stream has been aligned on a 8 byte boundary
 259  *
 260  * Returns: an unpacked dfa ready for matching or ERR_PTR on failure
 261  */
 262 struct aa_dfa *aa_dfa_unpack(void *blob, size_t size, int flags)
 263 {
 264         int hsize;
 265         int error = -ENOMEM;
 266         char *data = blob;
 267         struct table_header *table = NULL;
 268         struct aa_dfa *dfa = kzalloc(sizeof(struct aa_dfa), GFP_KERNEL);
 269         if (!dfa)
 270                 goto fail;
 271
 272         kref_init(&dfa->count);
 273
 274         error = -EPROTO;
 275
 276         /* get dfa table set header */
 277         if (size < sizeof(struct table_set_header))
 278                 goto fail;
 279
 280         if (ntohl(*(__be32 *) data) != YYTH_MAGIC)
 281                 goto fail;
 282
 283         hsize = ntohl(*(__be32 *) (data + 4));
 284         if (size < hsize)
 285                 goto fail;
 286
 287         dfa->flags = ntohs(*(__be16 *) (data + 12));
 288         if (dfa->flags & ~(YYTH_FLAGS))
 289                 goto fail;
 290
 291         /*
 292          * TODO: needed for dfa to support more than 1 oob
 293          * if (dfa->flags & YYTH_FLAGS_OOB_TRANS) {
 294          *      if (hsize < 16 + 4)
 295          *              goto fail;
 296          *      dfa->max_oob = ntol(*(__be32 *) (data + 16));
 297          *      if (dfa->max <= MAX_OOB_SUPPORTED) {
 298          *              pr_err("AppArmor DFA OOB greater than supported\n");
 299          *              goto fail;
 300          *      }
 301          * }
 302          */
 303         dfa->max_oob = 1;
 304
 305         data += hsize;
 306         size -= hsize;
 307
 308         while (size > 0) {
 309                 table = unpack_table(data, size);
 310                 if (!table)
 311                         goto fail;
 312
 313                 switch (table->td_id) {
 314                 case YYTD_ID_ACCEPT:
 315                         if (!(table->td_flags & ACCEPT1_FLAGS(flags)))
 316                                 goto fail;
 317                         break;
 318                 case YYTD_ID_ACCEPT2:
 319                         if (!(table->td_flags & ACCEPT2_FLAGS(flags)))
 320                                 goto fail;
 321                         break;
 322                 case YYTD_ID_BASE:
 323                         if (table->td_flags != YYTD_DATA32)
 324                                 goto fail;
 325                         break;
 326                 case YYTD_ID_DEF:
 327                 case YYTD_ID_NXT:
 328                 case YYTD_ID_CHK:
 329                         if (table->td_flags != YYTD_DATA16)
 330                                 goto fail;
 331                         break;
 332                 case YYTD_ID_EC:
 333                         if (table->td_flags != YYTD_DATA8)
 334                                 goto fail;
 335                         break;
 336                 default:
 337                         goto fail;
 338                 }
 339                 /* check for duplicate table entry */
 340                 if (dfa->tables[table->td_id])
 341                         goto fail;
 342                 dfa->tables[table->td_id] = table;
 343                 data += table_size(table->td_lolen, table->td_flags);
 344                 size -= table_size(table->td_lolen, table->td_flags);
 345                 table = NULL;
 346         }
 347         error = verify_table_headers(dfa->tables, flags);
 348         if (error)
 349                 goto fail;
 350
 351         if (flags & DFA_FLAG_VERIFY_STATES) {
 352                 error = verify_dfa(dfa);
 353                 if (error)
 354                         goto fail;
 355         }
 356
 357         return dfa;
 358
 359 fail:
 360         kvfree(table);
 361         dfa_free(dfa);
 362         return ERR_PTR(error);
 363 }
 364
 365 #define match_char(state, def, base, next, check, C)    \
 366 do {                                                    \
 367         u32 b = (base)[(state)];                        \
 368         unsigned int pos = base_idx(b) + (C);           \
 369         if ((check)[pos] != (state)) {                  \
 370                 (state) = (def)[(state)];               \
 371                 if (b & MATCH_FLAG_DIFF_ENCODE)         \
 372                         continue;                       \
 373                 break;                                  \
 374         }                                               \
 375         (state) = (next)[pos];                          \
 376         break;                                          \
 377 } while (1)
 378
 379 /**
 380  * aa_dfa_match_len - traverse @dfa to find state @str stops at
 381  * @dfa: the dfa to match @str against  (NOT NULL)
 382  * @start: the state of the dfa to start matching in
 383  * @str: the string of bytes to match against the dfa  (NOT NULL)
 384  * @len: length of the string of bytes to match
 385  *
 386  * aa_dfa_match_len will match @str against the dfa and return the state it
 387  * finished matching in. The final state can be used to look up the accepting
 388  * label, or as the start state of a continuing match.
 389  *
 390  * This function will happily match again the 0 byte and only finishes
 391  * when @len input is consumed.
 392  *
 393  * Returns: final state reached after input is consumed
 394  */
 395 aa_state_t aa_dfa_match_len(struct aa_dfa *dfa, aa_state_t start,
 396                             const char *str, int len)
 397 {
 398         u16 *def = DEFAULT_TABLE(dfa);
 399         u32 *base = BASE_TABLE(dfa);
 400         u16 *next = NEXT_TABLE(dfa);
 401         u16 *check = CHECK_TABLE(dfa);
 402         aa_state_t state = start;
 403
 404         if (state == DFA_NOMATCH)
 405                 return DFA_NOMATCH;
 406
 407         /* current state is <state>, matching character *str */
 408         if (dfa->tables[YYTD_ID_EC]) {
 409                 /* Equivalence class table defined */
 410                 u8 *equiv = EQUIV_TABLE(dfa);
 411                 for (; len; len--)
 412                         match_char(state, def, base, next, check,
 413                                    equiv[(u8) *str++]);
 414         } else {
 415                 /* default is direct to next state */
 416                 for (; len; len--)
 417                         match_char(state, def, base, next, check, (u8) *str++);
 418         }
 419
 420         return state;
 421 }
 422
 423 /**
 424  * aa_dfa_match - traverse @dfa to find state @str stops at
 425  * @dfa: the dfa to match @str against  (NOT NULL)
 426  * @start: the state of the dfa to start matching in
 427  * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
 428  *
 429  * aa_dfa_match will match @str against the dfa and return the state it
 430  * finished matching in. The final state can be used to look up the accepting
 431  * label, or as the start state of a continuing match.
 432  *
 433  * Returns: final state reached after input is consumed
 434  */
 435 aa_state_t aa_dfa_match(struct aa_dfa *dfa, aa_state_t start, const char *str)
 436 {
 437         u16 *def = DEFAULT_TABLE(dfa);
 438         u32 *base = BASE_TABLE(dfa);
 439         u16 *next = NEXT_TABLE(dfa);
 440         u16 *check = CHECK_TABLE(dfa);
 441         aa_state_t state = start;
 442
 443         if (state == DFA_NOMATCH)
 444                 return DFA_NOMATCH;
 445
 446         /* current state is <state>, matching character *str */
 447         if (dfa->tables[YYTD_ID_EC]) {
 448                 /* Equivalence class table defined */
 449                 u8 *equiv = EQUIV_TABLE(dfa);
 450                 /* default is direct to next state */
 451                 while (*str)
 452                         match_char(state, def, base, next, check,
 453                                    equiv[(u8) *str++]);
 454         } else {
 455                 /* default is direct to next state */
 456                 while (*str)
 457                         match_char(state, def, base, next, check, (u8) *str++);
 458         }
 459
 460         return state;
 461 }
 462
 463 /**
 464  * aa_dfa_next - step one character to the next state in the dfa
 465  * @dfa: the dfa to traverse (NOT NULL)
 466  * @state: the state to start in
 467  * @c: the input character to transition on
 468  *
 469  * aa_dfa_match will step through the dfa by one input character @c
 470  *
 471  * Returns: state reach after input @c
 472  */
 473 aa_state_t aa_dfa_next(struct aa_dfa *dfa, aa_state_t state, const char c)
 474 {
 475         u16 *def = DEFAULT_TABLE(dfa);
 476         u32 *base = BASE_TABLE(dfa);
 477         u16 *next = NEXT_TABLE(dfa);
 478         u16 *check = CHECK_TABLE(dfa);
 479
 480         /* current state is <state>, matching character *str */
 481         if (dfa->tables[YYTD_ID_EC]) {
 482                 /* Equivalence class table defined */
 483                 u8 *equiv = EQUIV_TABLE(dfa);
 484                 match_char(state, def, base, next, check, equiv[(u8) c]);
 485         } else
 486                 match_char(state, def, base, next, check, (u8) c);
 487
 488         return state;
 489 }
 490
 491 aa_state_t aa_dfa_outofband_transition(struct aa_dfa *dfa, aa_state_t state)
 492 {
 493         u16 *def = DEFAULT_TABLE(dfa);
 494         u32 *base = BASE_TABLE(dfa);
 495         u16 *next = NEXT_TABLE(dfa);
 496         u16 *check = CHECK_TABLE(dfa);
 497         u32 b = (base)[(state)];
 498
 499         if (!(b & MATCH_FLAG_OOB_TRANSITION))
 500                 return DFA_NOMATCH;
 501
 502         /* No Equivalence class remapping for outofband transitions */
 503         match_char(state, def, base, next, check, -1);
 504
 505         return state;
 506 }
 507
 508 /**
 509  * aa_dfa_match_until - traverse @dfa until accept state or end of input
 510  * @dfa: the dfa to match @str against  (NOT NULL)
 511  * @start: the state of the dfa to start matching in
 512  * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
 513  * @retpos: first character in str after match OR end of string
 514  *
 515  * aa_dfa_match will match @str against the dfa and return the state it
 516  * finished matching in. The final state can be used to look up the accepting
 517  * label, or as the start state of a continuing match.
 518  *
 519  * Returns: final state reached after input is consumed
 520  */
 521 aa_state_t aa_dfa_match_until(struct aa_dfa *dfa, aa_state_t start,
 522                                 const char *str, const char **retpos)
 523 {
 524         u16 *def = DEFAULT_TABLE(dfa);
 525         u32 *base = BASE_TABLE(dfa);
 526         u16 *next = NEXT_TABLE(dfa);
 527         u16 *check = CHECK_TABLE(dfa);
 528         u32 *accept = ACCEPT_TABLE(dfa);
 529         aa_state_t state = start, pos;
 530
 531         if (state == DFA_NOMATCH)
 532                 return DFA_NOMATCH;
 533
 534         /* current state is <state>, matching character *str */
 535         if (dfa->tables[YYTD_ID_EC]) {
 536                 /* Equivalence class table defined */
 537                 u8 *equiv = EQUIV_TABLE(dfa);
 538                 /* default is direct to next state */
 539                 while (*str) {
 540                         pos = base_idx(base[state]) + equiv[(u8) *str++];
 541                         if (check[pos] == state)
 542                                 state = next[pos];
 543                         else
 544                                 state = def[state];
 545                         if (accept[state])
 546                                 break;
 547                 }
 548         } else {
 549                 /* default is direct to next state */
 550                 while (*str) {
 551                         pos = base_idx(base[state]) + (u8) *str++;
 552                         if (check[pos] == state)
 553                                 state = next[pos];
 554                         else
 555                                 state = def[state];
 556                         if (accept[state])
 557                                 break;
 558                 }
 559         }
 560
 561         *retpos = str;
 562         return state;
 563 }
 564
 565 /**
 566  * aa_dfa_matchn_until - traverse @dfa until accept or @n bytes consumed
 567  * @dfa: the dfa to match @str against  (NOT NULL)
 568  * @start: the state of the dfa to start matching in
 569  * @str: the string of bytes to match against the dfa  (NOT NULL)
 570  * @n: length of the string of bytes to match
 571  * @retpos: first character in str after match OR str + n
 572  *
 573  * aa_dfa_match_len will match @str against the dfa and return the state it
 574  * finished matching in. The final state can be used to look up the accepting
 575  * label, or as the start state of a continuing match.
 576  *
 577  * This function will happily match again the 0 byte and only finishes
 578  * when @n input is consumed.
 579  *
 580  * Returns: final state reached after input is consumed
 581  */
 582 aa_state_t aa_dfa_matchn_until(struct aa_dfa *dfa, aa_state_t start,
 583                                  const char *str, int n, const char **retpos)
 584 {
 585         u16 *def = DEFAULT_TABLE(dfa);
 586         u32 *base = BASE_TABLE(dfa);
 587         u16 *next = NEXT_TABLE(dfa);
 588         u16 *check = CHECK_TABLE(dfa);
 589         u32 *accept = ACCEPT_TABLE(dfa);
 590         aa_state_t state = start, pos;
 591
 592         *retpos = NULL;
 593         if (state == DFA_NOMATCH)
 594                 return DFA_NOMATCH;
 595
 596         /* current state is <state>, matching character *str */
 597         if (dfa->tables[YYTD_ID_EC]) {
 598                 /* Equivalence class table defined */
 599                 u8 *equiv = EQUIV_TABLE(dfa);
 600                 /* default is direct to next state */
 601                 for (; n; n--) {
 602                         pos = base_idx(base[state]) + equiv[(u8) *str++];
 603                         if (check[pos] == state)
 604                                 state = next[pos];
 605                         else
 606                                 state = def[state];
 607                         if (accept[state])
 608                                 break;
 609                 }
 610         } else {
 611                 /* default is direct to next state */
 612                 for (; n; n--) {
 613                         pos = base_idx(base[state]) + (u8) *str++;
 614                         if (check[pos] == state)
 615                                 state = next[pos];
 616                         else
 617                                 state = def[state];
 618                         if (accept[state])
 619                                 break;
 620                 }
 621         }
 622
 623         *retpos = str;
 624         return state;
 625 }
 626
 627 #define inc_wb_pos(wb)                                          \
 628 do {                                                            \
 629         wb->pos = (wb->pos + 1) & (WB_HISTORY_SIZE - 1);                \
 630         wb->len = (wb->len + 1) & (WB_HISTORY_SIZE - 1);                \
 631 } while (0)
 632
 633 /* For DFAs that don't support extended tagging of states */
 634 static bool is_loop(struct match_workbuf *wb, aa_state_t state,
 635                     unsigned int *adjust)
 636 {
 637         aa_state_t pos = wb->pos;
 638         aa_state_t i;
 639
 640         if (wb->history[pos] < state)
 641                 return false;
 642
 643         for (i = 0; i <= wb->len; i++) {
 644                 if (wb->history[pos] == state) {
 645                         *adjust = i;
 646                         return true;
 647                 }
 648                 if (pos == 0)
 649                         pos = WB_HISTORY_SIZE;
 650                 pos--;
 651         }
 652
 653         *adjust = i;
 654         return true;
 655 }
 656
 657 static aa_state_t leftmatch_fb(struct aa_dfa *dfa, aa_state_t start,
 658                                  const char *str, struct match_workbuf *wb,
 659                                  unsigned int *count)
 660 {
 661         u16 *def = DEFAULT_TABLE(dfa);
 662         u32 *base = BASE_TABLE(dfa);
 663         u16 *next = NEXT_TABLE(dfa);
 664         u16 *check = CHECK_TABLE(dfa);
 665         aa_state_t state = start, pos;
 666
 667         AA_BUG(!dfa);
 668         AA_BUG(!str);
 669         AA_BUG(!wb);
 670         AA_BUG(!count);
 671
 672         *count = 0;
 673         if (state == DFA_NOMATCH)
 674                 return DFA_NOMATCH;
 675
 676         /* current state is <state>, matching character *str */
 677         if (dfa->tables[YYTD_ID_EC]) {
 678                 /* Equivalence class table defined */
 679                 u8 *equiv = EQUIV_TABLE(dfa);
 680                 /* default is direct to next state */
 681                 while (*str) {
 682                         unsigned int adjust;
 683
 684                         wb->history[wb->pos] = state;
 685                         pos = base_idx(base[state]) + equiv[(u8) *str++];
 686                         if (check[pos] == state)
 687                                 state = next[pos];
 688                         else
 689                                 state = def[state];
 690                         if (is_loop(wb, state, &adjust)) {
 691                                 state = aa_dfa_match(dfa, state, str);
 692                                 *count -= adjust;
 693                                 goto out;
 694                         }
 695                         inc_wb_pos(wb);
 696                         (*count)++;
 697                 }
 698         } else {
 699                 /* default is direct to next state */
 700                 while (*str) {
 701                         unsigned int adjust;
 702
 703                         wb->history[wb->pos] = state;
 704                         pos = base_idx(base[state]) + (u8) *str++;
 705                         if (check[pos] == state)
 706                                 state = next[pos];
 707                         else
 708                                 state = def[state];
 709                         if (is_loop(wb, state, &adjust)) {
 710                                 state = aa_dfa_match(dfa, state, str);
 711                                 *count -= adjust;
 712                                 goto out;
 713                         }
 714                         inc_wb_pos(wb);
 715                         (*count)++;
 716                 }
 717         }
 718
 719 out:
 720         if (!state)
 721                 *count = 0;
 722         return state;
 723 }
 724
 725 /**
 726  * aa_dfa_leftmatch - traverse @dfa to find state @str stops at
 727  * @dfa: the dfa to match @str against  (NOT NULL)
 728  * @start: the state of the dfa to start matching in
 729  * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
 730  * @count: current count of longest left.
 731  *
 732  * aa_dfa_match will match @str against the dfa and return the state it
 733  * finished matching in. The final state can be used to look up the accepting
 734  * label, or as the start state of a continuing match.
 735  *
 736  * Returns: final state reached after input is consumed
 737  */
 738 aa_state_t aa_dfa_leftmatch(struct aa_dfa *dfa, aa_state_t start,
 739                             const char *str, unsigned int *count)
 740 {
 741         DEFINE_MATCH_WB(wb);
 742
 743         /* TODO: match for extended state dfas */
 744
 745         return leftmatch_fb(dfa, start, str, &wb, count);
 746 }