[GitHub/mt8127/android_kernel_alcatel_ttab.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-2010 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"

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