[linux-block.git] / security / apparmor / match.c

/*
 * AppArmor security module
 *
 * This file contains AppArmor dfa based regular expression matching engine
 *
 * Copyright (C) 1998-2008 Novell/SUSE
 * Copyright 2009-2012 Canonical Ltd.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, version 2 of the
 * License.
 */

#include <linux/errno.h>
#include <linux/kernel.h>
#include <linux/mm.h>
#include <linux/slab.h>
#include <linux/vmalloc.h>
#include <linux/err.h>
#include <linux/kref.h>

#include "include/apparmor.h"
#include "include/match.h"

#define base_idx(X) ((X) & 0xffffff)

/**
 * unpack_table - unpack a dfa table (one of accept, default, base, next check)
 * @blob: data to unpack (NOT NULL)
 * @bsize: size of blob
 *
 * Returns: pointer to table else NULL on failure
 *
 * NOTE: must be freed by kvfree (not kfree)
 */
static struct table_header *unpack_table(char *blob, size_t bsize)
{
	struct table_header *table = NULL;
	struct table_header th;
	size_t tsize;

	if (bsize < sizeof(struct table_header))
		goto out;

	/* loaded td_id's start at 1, subtract 1 now to avoid doing
	 * it every time we use td_id as an index
	 */
	th.td_id = be16_to_cpu(*(u16 *) (blob)) - 1;
	if (th.td_id > YYTD_ID_MAX)
		goto out;
	th.td_flags = be16_to_cpu(*(u16 *) (blob + 2));
	th.td_lolen = be32_to_cpu(*(u32 *) (blob + 8));
	blob += sizeof(struct table_header);

	if (!(th.td_flags == YYTD_DATA16 || th.td_flags == YYTD_DATA32 ||
	      th.td_flags == YYTD_DATA8))
		goto out;

	tsize = table_size(th.td_lolen, th.td_flags);
	if (bsize < tsize)
		goto out;

	table = kvzalloc(tsize);
	if (table) {
		*table = th;
		if (th.td_flags == YYTD_DATA8)
			UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
				     u8, byte_to_byte);
		else if (th.td_flags == YYTD_DATA16)
			UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
				     u16, be16_to_cpu);
		else if (th.td_flags == YYTD_DATA32)
			UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
				     u32, be32_to_cpu);
		else
			goto fail;
		/* if table was vmalloced make sure the page tables are synced
		 * before it is used, as it goes live to all cpus.
		 */
		if (is_vmalloc_addr(table))
			vm_unmap_aliases();
	}

out:
	return table;
fail:
	kvfree(table);
	return NULL;
}

/**
 * verify_dfa - verify that transitions and states in the tables are in bounds.
 * @dfa: dfa to test  (NOT NULL)
 * @flags: flags controlling what type of accept table are acceptable
 *
 * Assumes dfa has gone through the first pass verification done by unpacking
 * NOTE: this does not valid accept table values
 *
 * Returns: %0 else error code on failure to verify
 */
static int verify_dfa(struct aa_dfa *dfa, int flags)
{
	size_t i, state_count, trans_count;
	int error = -EPROTO;

	/* check that required tables exist */
	if (!(dfa->tables[YYTD_ID_DEF] &&
	      dfa->tables[YYTD_ID_BASE] &&
	      dfa->tables[YYTD_ID_NXT] && dfa->tables[YYTD_ID_CHK]))
		goto out;

	/* accept.size == default.size == base.size */
	state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
	if (ACCEPT1_FLAGS(flags)) {
		if (!dfa->tables[YYTD_ID_ACCEPT])
			goto out;
		if (state_count != dfa->tables[YYTD_ID_ACCEPT]->td_lolen)
			goto out;
	}
	if (ACCEPT2_FLAGS(flags)) {
		if (!dfa->tables[YYTD_ID_ACCEPT2])
			goto out;
		if (state_count != dfa->tables[YYTD_ID_ACCEPT2]->td_lolen)
			goto out;
	}
	if (state_count != dfa->tables[YYTD_ID_DEF]->td_lolen)
		goto out;

	/* next.size == chk.size */
	trans_count = dfa->tables[YYTD_ID_NXT]->td_lolen;
	if (trans_count != dfa->tables[YYTD_ID_CHK]->td_lolen)
		goto out;

	/* if equivalence classes then its table size must be 256 */
	if (dfa->tables[YYTD_ID_EC] &&
	    dfa->tables[YYTD_ID_EC]->td_lolen != 256)
		goto out;

	if (flags & DFA_FLAG_VERIFY_STATES) {
		for (i = 0; i < state_count; i++) {
			if (DEFAULT_TABLE(dfa)[i] >= state_count)
				goto out;
			if (base_idx(BASE_TABLE(dfa)[i]) + 255 >= trans_count) {
				printk(KERN_ERR "AppArmor DFA next/check upper "
				       "bounds error\n");
				goto out;
			}
		}

		for (i = 0; i < trans_count; i++) {
			if (NEXT_TABLE(dfa)[i] >= state_count)
				goto out;
			if (CHECK_TABLE(dfa)[i] >= state_count)
				goto out;
		}
	}

	error = 0;
out:
	return error;
}

/**
 * dfa_free - free a dfa allocated by aa_dfa_unpack
 * @dfa: the dfa to free  (MAYBE NULL)
 *
 * Requires: reference count to dfa == 0
 */
static void dfa_free(struct aa_dfa *dfa)
{
	if (dfa) {
		int i;

		for (i = 0; i < ARRAY_SIZE(dfa->tables); i++) {
			kvfree(dfa->tables[i]);
			dfa->tables[i] = NULL;
		}
		kfree(dfa);
	}
}

/**
 * aa_dfa_free_kref - free aa_dfa by kref (called by aa_put_dfa)
 * @kr: kref callback for freeing of a dfa  (NOT NULL)
 */
void aa_dfa_free_kref(struct kref *kref)
{
	struct aa_dfa *dfa = container_of(kref, struct aa_dfa, count);
	dfa_free(dfa);
}

/**
 * aa_dfa_unpack - unpack the binary tables of a serialized dfa
 * @blob: aligned serialized stream of data to unpack  (NOT NULL)
 * @size: size of data to unpack
 * @flags: flags controlling what type of accept tables are acceptable
 *
 * Unpack a dfa that has been serialized.  To find information on the dfa
 * format look in Documentation/security/apparmor.txt
 * Assumes the dfa @blob stream has been aligned on a 8 byte boundary
 *
 * Returns: an unpacked dfa ready for matching or ERR_PTR on failure
 */
struct aa_dfa *aa_dfa_unpack(void *blob, size_t size, int flags)
{
	int hsize;
	int error = -ENOMEM;
	char *data = blob;
	struct table_header *table = NULL;
	struct aa_dfa *dfa = kzalloc(sizeof(struct aa_dfa), GFP_KERNEL);
	if (!dfa)
		goto fail;

	kref_init(&dfa->count);

	error = -EPROTO;

	/* get dfa table set header */
	if (size < sizeof(struct table_set_header))
		goto fail;

	if (ntohl(*(u32 *) data) != YYTH_MAGIC)
		goto fail;

	hsize = ntohl(*(u32 *) (data + 4));
	if (size < hsize)
		goto fail;

	dfa->flags = ntohs(*(u16 *) (data + 12));
	data += hsize;
	size -= hsize;

	while (size > 0) {
		table = unpack_table(data, size);
		if (!table)
			goto fail;

		switch (table->td_id) {
		case YYTD_ID_ACCEPT:
			if (!(table->td_flags & ACCEPT1_FLAGS(flags)))
				goto fail;
			break;
		case YYTD_ID_ACCEPT2:
			if (!(table->td_flags & ACCEPT2_FLAGS(flags)))
				goto fail;
			break;
		case YYTD_ID_BASE:
			if (table->td_flags != YYTD_DATA32)
				goto fail;
			break;
		case YYTD_ID_DEF:
		case YYTD_ID_NXT:
		case YYTD_ID_CHK:
			if (table->td_flags != YYTD_DATA16)
				goto fail;
			break;
		case YYTD_ID_EC:
			if (table->td_flags != YYTD_DATA8)
				goto fail;
			break;
		default:
			goto fail;
		}
		/* check for duplicate table entry */
		if (dfa->tables[table->td_id])
			goto fail;
		dfa->tables[table->td_id] = table;
		data += table_size(table->td_lolen, table->td_flags);
		size -= table_size(table->td_lolen, table->td_flags);
		table = NULL;
	}

	error = verify_dfa(dfa, flags);
	if (error)
		goto fail;

	return dfa;

fail:
	kvfree(table);
	dfa_free(dfa);
	return ERR_PTR(error);
}

/**
 * aa_dfa_match_len - traverse @dfa to find state @str stops at
 * @dfa: the dfa to match @str against  (NOT NULL)
 * @start: the state of the dfa to start matching in
 * @str: the string of bytes to match against the dfa  (NOT NULL)
 * @len: length of the string of bytes to match
 *
 * aa_dfa_match_len will match @str against the dfa and return the state it
 * finished matching in. The final state can be used to look up the accepting
 * label, or as the start state of a continuing match.
 *
 * This function will happily match again the 0 byte and only finishes
 * when @len input is consumed.
 *
 * Returns: final state reached after input is consumed
 */
unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int start,
			      const char *str, int len)
{
	u16 *def = DEFAULT_TABLE(dfa);
	u32 *base = BASE_TABLE(dfa);
	u16 *next = NEXT_TABLE(dfa);
	u16 *check = CHECK_TABLE(dfa);
	unsigned int state = start, pos;

	if (state == 0)
		return 0;

	/* current state is <state>, matching character *str */
	if (dfa->tables[YYTD_ID_EC]) {
		/* Equivalence class table defined */
		u8 *equiv = EQUIV_TABLE(dfa);
		/* default is direct to next state */
		for (; len; len--) {
			pos = base_idx(base[state]) + equiv[(u8) *str++];
			if (check[pos] == state)
				state = next[pos];
			else
				state = def[state];
		}
	} else {
		/* default is direct to next state */
		for (; len; len--) {
			pos = base_idx(base[state]) + (u8) *str++;
			if (check[pos] == state)
				state = next[pos];
			else
				state = def[state];
		}
	}

	return state;
}

/**
 * aa_dfa_match - traverse @dfa to find state @str stops at
 * @dfa: the dfa to match @str against  (NOT NULL)
 * @start: the state of the dfa to start matching in
 * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
 *
 * aa_dfa_match will match @str against the dfa and return the state it
 * finished matching in. The final state can be used to look up the accepting
 * label, or as the start state of a continuing match.
 *
 * Returns: final state reached after input is consumed
 */
unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start,
			  const char *str)
{
	u16 *def = DEFAULT_TABLE(dfa);
	u32 *base = BASE_TABLE(dfa);
	u16 *next = NEXT_TABLE(dfa);
	u16 *check = CHECK_TABLE(dfa);
	unsigned int state = start, pos;

	if (state == 0)
		return 0;

	/* current state is <state>, matching character *str */
	if (dfa->tables[YYTD_ID_EC]) {
		/* Equivalence class table defined */
		u8 *equiv = EQUIV_TABLE(dfa);
		/* default is direct to next state */
		while (*str) {
			pos = base_idx(base[state]) + equiv[(u8) *str++];
			if (check[pos] == state)
				state = next[pos];
			else
				state = def[state];
		}
	} else {
		/* default is direct to next state */
		while (*str) {
			pos = base_idx(base[state]) + (u8) *str++;
			if (check[pos] == state)
				state = next[pos];
			else
				state = def[state];
		}
	}

	return state;
}

/**
 * aa_dfa_next - step one character to the next state in the dfa
 * @dfa: the dfa to tranverse (NOT NULL)
 * @state: the state to start in
 * @c: the input character to transition on
 *
 * aa_dfa_match will step through the dfa by one input character @c
 *
 * Returns: state reach after input @c
 */
unsigned int aa_dfa_next(struct aa_dfa *dfa, unsigned int state,
			  const char c)
{
	u16 *def = DEFAULT_TABLE(dfa);
	u32 *base = BASE_TABLE(dfa);
	u16 *next = NEXT_TABLE(dfa);
	u16 *check = CHECK_TABLE(dfa);
	unsigned int pos;

	/* current state is <state>, matching character *str */
	if (dfa->tables[YYTD_ID_EC]) {
		/* Equivalence class table defined */
		u8 *equiv = EQUIV_TABLE(dfa);
		/* default is direct to next state */

		pos = base_idx(base[state]) + equiv[(u8) c];
		if (check[pos] == state)
			state = next[pos];
		else
			state = def[state];
	} else {
		/* default is direct to next state */
		pos = base_idx(base[state]) + (u8) c;
		if (check[pos] == state)
			state = next[pos];
		else
			state = def[state];
	}

	return state;
}
Commit	Line	Data
e06f75a6 JJ	1	/*
	2	* AppArmor security module
	3	*
	4	* This file contains AppArmor dfa based regular expression matching engine
	5	*
	6	* Copyright (C) 1998-2008 Novell/SUSE
8e4ff109	7	* Copyright 2009-2012 Canonical Ltd.
e06f75a6 JJ	8	*
	9	* This program is free software; you can redistribute it and/or
	10	* modify it under the terms of the GNU General Public License as
	11	* published by the Free Software Foundation, version 2 of the
	12	* License.
	13	*/
	14
	15	#include <linux/errno.h>
	16	#include <linux/kernel.h>
	17	#include <linux/mm.h>
	18	#include <linux/slab.h>
	19	#include <linux/vmalloc.h>
	20	#include <linux/err.h>
	21	#include <linux/kref.h>
	22
	23	#include "include/apparmor.h"
	24	#include "include/match.h"
	25
ed686308 JJ	26	#define base_idx(X) ((X) & 0xffffff)
ed686308 JJ	27
e06f75a6 JJ	28	/**
	29	* unpack_table - unpack a dfa table (one of accept, default, base, next check)
	30	* @blob: data to unpack (NOT NULL)
	31	* @bsize: size of blob
	32	*
	33	* Returns: pointer to table else NULL on failure
	34	*
0ca554b9	35	* NOTE: must be freed by kvfree (not kfree)
e06f75a6 JJ	36	*/
	37	static struct table_header unpack_table(char blob, size_t bsize)
	38	{
	39	struct table_header *table = NULL;
	40	struct table_header th;
	41	size_t tsize;
	42
	43	if (bsize < sizeof(struct table_header))
	44	goto out;
	45
	46	/* loaded td_id's start at 1, subtract 1 now to avoid doing
	47	* it every time we use td_id as an index
	48	*/
	49	th.td_id = be16_to_cpu((u16 ) (blob)) - 1;
15756178 JJ	50	if (th.td_id > YYTD_ID_MAX)
15756178 JJ	51	goto out;
e06f75a6 JJ	52	th.td_flags = be16_to_cpu((u16 ) (blob + 2));
	53	th.td_lolen = be32_to_cpu((u32 ) (blob + 8));
	54	blob += sizeof(struct table_header);
	55
	56	if (!(th.td_flags == YYTD_DATA16 \|\| th.td_flags == YYTD_DATA32 \|\|
	57	th.td_flags == YYTD_DATA8))
	58	goto out;
	59
	60	tsize = table_size(th.td_lolen, th.td_flags);
	61	if (bsize < tsize)
	62	goto out;
	63
0ca554b9	64	table = kvzalloc(tsize);
e06f75a6 JJ	65	if (table) {
	66	*table = th;
	67	if (th.td_flags == YYTD_DATA8)
	68	UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
	69	u8, byte_to_byte);
	70	else if (th.td_flags == YYTD_DATA16)
	71	UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
	72	u16, be16_to_cpu);
	73	else if (th.td_flags == YYTD_DATA32)
	74	UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
	75	u32, be32_to_cpu);
	76	else
	77	goto fail;
3197f5ad JJ	78	/* if table was vmalloced make sure the page tables are synced
	79	* before it is used, as it goes live to all cpus.
	80	*/
	81	if (is_vmalloc_addr(table))
	82	vm_unmap_aliases();
e06f75a6 JJ	83	}
	84
	85	out:
e06f75a6 JJ	86	return table;
	87	fail:
	88	kvfree(table);
	89	return NULL;
	90	}
	91
	92	/**
	93	* verify_dfa - verify that transitions and states in the tables are in bounds.
	94	* @dfa: dfa to test (NOT NULL)
	95	* @flags: flags controlling what type of accept table are acceptable
	96	*
	97	* Assumes dfa has gone through the first pass verification done by unpacking
	98	* NOTE: this does not valid accept table values
	99	*
	100	* Returns: %0 else error code on failure to verify
	101	*/
	102	static int verify_dfa(struct aa_dfa *dfa, int flags)
	103	{
	104	size_t i, state_count, trans_count;
	105	int error = -EPROTO;
	106
	107	/* check that required tables exist */
	108	if (!(dfa->tables[YYTD_ID_DEF] &&
	109	dfa->tables[YYTD_ID_BASE] &&
	110	dfa->tables[YYTD_ID_NXT] && dfa->tables[YYTD_ID_CHK]))
	111	goto out;
	112
	113	/* accept.size == default.size == base.size */
	114	state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
	115	if (ACCEPT1_FLAGS(flags)) {
	116	if (!dfa->tables[YYTD_ID_ACCEPT])
	117	goto out;
	118	if (state_count != dfa->tables[YYTD_ID_ACCEPT]->td_lolen)
	119	goto out;
	120	}
	121	if (ACCEPT2_FLAGS(flags)) {
	122	if (!dfa->tables[YYTD_ID_ACCEPT2])
	123	goto out;
	124	if (state_count != dfa->tables[YYTD_ID_ACCEPT2]->td_lolen)
	125	goto out;
	126	}
	127	if (state_count != dfa->tables[YYTD_ID_DEF]->td_lolen)
	128	goto out;
	129
	130	/* next.size == chk.size */
	131	trans_count = dfa->tables[YYTD_ID_NXT]->td_lolen;
	132	if (trans_count != dfa->tables[YYTD_ID_CHK]->td_lolen)
	133	goto out;
	134
	135	/* if equivalence classes then its table size must be 256 */
	136	if (dfa->tables[YYTD_ID_EC] &&
	137	dfa->tables[YYTD_ID_EC]->td_lolen != 256)
	138	goto out;
	139
	140	if (flags & DFA_FLAG_VERIFY_STATES) {
	141	for (i = 0; i < state_count; i++) {
	142	if (DEFAULT_TABLE(dfa)[i] >= state_count)
	143	goto out;
ed686308	144	if (base_idx(BASE_TABLE(dfa)[i]) + 255 >= trans_count) {
e06f75a6 JJ	145	printk(KERN_ERR "AppArmor DFA next/check upper "
	146	"bounds error\n");
	147	goto out;
	148	}
	149	}
	150
	151	for (i = 0; i < trans_count; i++) {
	152	if (NEXT_TABLE(dfa)[i] >= state_count)
	153	goto out;
	154	if (CHECK_TABLE(dfa)[i] >= state_count)
	155	goto out;
	156	}
	157	}
	158
	159	error = 0;
	160	out:
	161	return error;
	162	}
	163
	164	/**
	165	* dfa_free - free a dfa allocated by aa_dfa_unpack
	166	* @dfa: the dfa to free (MAYBE NULL)
	167	*
	168	* Requires: reference count to dfa == 0
	169	*/
	170	static void dfa_free(struct aa_dfa *dfa)
	171	{
	172	if (dfa) {
	173	int i;
	174
	175	for (i = 0; i < ARRAY_SIZE(dfa->tables); i++) {
	176	kvfree(dfa->tables[i]);
	177	dfa->tables[i] = NULL;
	178	}
	179	kfree(dfa);
	180	}
	181	}
	182
	183	/**
	184	* aa_dfa_free_kref - free aa_dfa by kref (called by aa_put_dfa)
	185	* @kr: kref callback for freeing of a dfa (NOT NULL)
	186	*/
	187	void aa_dfa_free_kref(struct kref *kref)
	188	{
	189	struct aa_dfa *dfa = container_of(kref, struct aa_dfa, count);
	190	dfa_free(dfa);
	191	}
	192
	193	/**
	194	* aa_dfa_unpack - unpack the binary tables of a serialized dfa
	195	* @blob: aligned serialized stream of data to unpack (NOT NULL)
	196	* @size: size of data to unpack
	197	* @flags: flags controlling what type of accept tables are acceptable
	198	*
	199	* Unpack a dfa that has been serialized. To find information on the dfa
d410fa4e	200	* format look in Documentation/security/apparmor.txt
25985edc	201	* Assumes the dfa @blob stream has been aligned on a 8 byte boundary
e06f75a6 JJ	202	*
	203	* Returns: an unpacked dfa ready for matching or ERR_PTR on failure
	204	*/
	205	struct aa_dfa aa_dfa_unpack(void blob, size_t size, int flags)
	206	{
	207	int hsize;
	208	int error = -ENOMEM;
	209	char *data = blob;
	210	struct table_header *table = NULL;
	211	struct aa_dfa *dfa = kzalloc(sizeof(struct aa_dfa), GFP_KERNEL);
	212	if (!dfa)
	213	goto fail;
	214
	215	kref_init(&dfa->count);
	216
	217	error = -EPROTO;
	218
	219	/* get dfa table set header */
	220	if (size < sizeof(struct table_set_header))
	221	goto fail;
	222
	223	if (ntohl((u32 ) data) != YYTH_MAGIC)
	224	goto fail;
	225
	226	hsize = ntohl((u32 ) (data + 4));
	227	if (size < hsize)
	228	goto fail;
	229
	230	dfa->flags = ntohs((u16 ) (data + 12));
	231	data += hsize;
	232	size -= hsize;
	233
	234	while (size > 0) {
	235	table = unpack_table(data, size);
	236	if (!table)
	237	goto fail;
	238
	239	switch (table->td_id) {
	240	case YYTD_ID_ACCEPT:
	241	if (!(table->td_flags & ACCEPT1_FLAGS(flags)))
	242	goto fail;
	243	break;
	244	case YYTD_ID_ACCEPT2:
	245	if (!(table->td_flags & ACCEPT2_FLAGS(flags)))
	246	goto fail;
	247	break;
	248	case YYTD_ID_BASE:
	249	if (table->td_flags != YYTD_DATA32)
	250	goto fail;
	251	break;
	252	case YYTD_ID_DEF:
	253	case YYTD_ID_NXT:
	254	case YYTD_ID_CHK:
	255	if (table->td_flags != YYTD_DATA16)
	256	goto fail;
	257	break;
	258	case YYTD_ID_EC:
	259	if (table->td_flags != YYTD_DATA8)
	260	goto fail;
	261	break;
	262	default:
	263	goto fail;
	264	}
	265	/* check for duplicate table entry */
266	if (dfa->tables[table->td_id])
267	goto fail;
268	dfa->tables[table->td_id] = table;
269	data += table_size(table->td_lolen, table->td_flags);
270	size -= table_size(table->td_lolen, table->td_flags);
271	table = NULL;
272	}
273
274	error = verify_dfa(dfa, flags);
275	if (error)
276	goto fail;
277
278	return dfa;
279
280	fail:
281	kvfree(table);
282	dfa_free(dfa);
283	return ERR_PTR(error);
284	}
285
286	/**
287	* aa_dfa_match_len - traverse @dfa to find state @str stops at
288	* @dfa: the dfa to match @str against (NOT NULL)
289	* @start: the state of the dfa to start matching in
290	* @str: the string of bytes to match against the dfa (NOT NULL)
291	* @len: length of the string of bytes to match
292	*
293	* aa_dfa_match_len will match @str against the dfa and return the state it
294	* finished matching in. The final state can be used to look up the accepting
295	* label, or as the start state of a continuing match.
296	*
297	* This function will happily match again the 0 byte and only finishes
298	* when @len input is consumed.
299	*
300	* Returns: final state reached after input is consumed
301	*/
302	unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int start,
303	const char *str, int len)
304	{
305	u16 *def = DEFAULT_TABLE(dfa);
306	u32 *base = BASE_TABLE(dfa);
307	u16 *next = NEXT_TABLE(dfa);
308	u16 *check = CHECK_TABLE(dfa);
309	unsigned int state = start, pos;
310
311	if (state == 0)
312	return 0;
313
314	/* current state is <state>, matching character str /
315	if (dfa->tables[YYTD_ID_EC]) {
316	/* Equivalence class table defined */
317	u8 *equiv = EQUIV_TABLE(dfa);
318	/* default is direct to next state */
319	for (; len; len--) {
ed686308	320	pos = base_idx(base[state]) + equiv[(u8) *str++];
e06f75a6 JJ	321	if (check[pos] == state)
	322	state = next[pos];
	323	else
	324	state = def[state];
	325	}
	326	} else {
	327	/* default is direct to next state */
	328	for (; len; len--) {
ed686308	329	pos = base_idx(base[state]) + (u8) *str++;
e06f75a6 JJ	330	if (check[pos] == state)
	331	state = next[pos];
	332	else
	333	state = def[state];
	334	}
	335	}
	336
	337	return state;
	338	}
	339
	340	/**
0fe1212d	341	* aa_dfa_match - traverse @dfa to find state @str stops at
e06f75a6 JJ	342	* @dfa: the dfa to match @str against (NOT NULL)
	343	* @start: the state of the dfa to start matching in
	344	* @str: the null terminated string of bytes to match against the dfa (NOT NULL)
	345	*
0fe1212d	346	* aa_dfa_match will match @str against the dfa and return the state it
e06f75a6 JJ	347	* finished matching in. The final state can be used to look up the accepting
	348	* label, or as the start state of a continuing match.
	349	*
	350	* Returns: final state reached after input is consumed
	351	*/
	352	unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start,
	353	const char *str)
	354	{
0fe1212d JJ	355	u16 *def = DEFAULT_TABLE(dfa);
	356	u32 *base = BASE_TABLE(dfa);
	357	u16 *next = NEXT_TABLE(dfa);
	358	u16 *check = CHECK_TABLE(dfa);
	359	unsigned int state = start, pos;
	360
	361	if (state == 0)
	362	return 0;
	363
	364	/* current state is <state>, matching character str /
	365	if (dfa->tables[YYTD_ID_EC]) {
	366	/* Equivalence class table defined */
	367	u8 *equiv = EQUIV_TABLE(dfa);
	368	/* default is direct to next state */
	369	while (*str) {
ed686308	370	pos = base_idx(base[state]) + equiv[(u8) *str++];
0fe1212d JJ	371	if (check[pos] == state)
	372	state = next[pos];
	373	else
	374	state = def[state];
	375	}
	376	} else {
	377	/* default is direct to next state */
	378	while (*str) {
ed686308	379	pos = base_idx(base[state]) + (u8) *str++;
0fe1212d JJ	380	if (check[pos] == state)
	381	state = next[pos];
	382	else
	383	state = def[state];
	384	}
	385	}
	386
	387	return state;
	388	}
	389
	390	/**
	391	* aa_dfa_next - step one character to the next state in the dfa
	392	* @dfa: the dfa to tranverse (NOT NULL)
	393	* @state: the state to start in
	394	* @c: the input character to transition on
	395	*
	396	* aa_dfa_match will step through the dfa by one input character @c
	397	*
	398	* Returns: state reach after input @c
	399	*/
	400	unsigned int aa_dfa_next(struct aa_dfa *dfa, unsigned int state,
	401	const char c)
	402	{
	403	u16 *def = DEFAULT_TABLE(dfa);
	404	u32 *base = BASE_TABLE(dfa);
	405	u16 *next = NEXT_TABLE(dfa);
	406	u16 *check = CHECK_TABLE(dfa);
	407	unsigned int pos;
	408
	409	/* current state is <state>, matching character str /
	410	if (dfa->tables[YYTD_ID_EC]) {
	411	/* Equivalence class table defined */
	412	u8 *equiv = EQUIV_TABLE(dfa);
	413	/* default is direct to next state */
	414
ed686308	415	pos = base_idx(base[state]) + equiv[(u8) c];
0fe1212d JJ	416	if (check[pos] == state)
	417	state = next[pos];
	418	else
	419	state = def[state];
	420	} else {
	421	/* default is direct to next state */
ed686308	422	pos = base_idx(base[state]) + (u8) c;
0fe1212d JJ	423	if (check[pos] == state)
	424	state = next[pos];
	425	else
	426	state = def[state];
	427	}
	428
	429	return state;
e06f75a6	430	}