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