[linux-2.6-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;
	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;
	}

out:
	/* 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();
	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;
	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
0ca554b9	62	table = kvzalloc(tsize);
e06f75a6 JJ	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;
	76	}
	77
	78	out:
	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	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;
ed686308	142	if (base_idx(BASE_TABLE(dfa)[i]) + 255 >= trans_count) {
e06f75a6 JJ	143	printk(KERN_ERR "AppArmor DFA next/check upper "
	144	"bounds error\n");
	145	goto out;
	146	}
	147	}
	148
	149	for (i = 0; i < trans_count; i++) {
	150	if (NEXT_TABLE(dfa)[i] >= state_count)
	151	goto out;
	152	if (CHECK_TABLE(dfa)[i] >= state_count)
	153	goto out;
	154	}
	155	}
	156
	157	error = 0;
	158	out:
	159	return error;
	160	}
	161
	162	/**
	163	* dfa_free - free a dfa allocated by aa_dfa_unpack
	164	* @dfa: the dfa to free (MAYBE NULL)
	165	*
	166	* Requires: reference count to dfa == 0
	167	*/
	168	static void dfa_free(struct aa_dfa *dfa)
	169	{
	170	if (dfa) {
	171	int i;
	172
	173	for (i = 0; i < ARRAY_SIZE(dfa->tables); i++) {
	174	kvfree(dfa->tables[i]);
	175	dfa->tables[i] = NULL;
	176	}
	177	kfree(dfa);
	178	}
	179	}
	180
	181	/**
	182	* aa_dfa_free_kref - free aa_dfa by kref (called by aa_put_dfa)
	183	* @kr: kref callback for freeing of a dfa (NOT NULL)
	184	*/
	185	void aa_dfa_free_kref(struct kref *kref)
	186	{
	187	struct aa_dfa *dfa = container_of(kref, struct aa_dfa, count);
	188	dfa_free(dfa);
	189	}
	190
	191	/**
	192	* aa_dfa_unpack - unpack the binary tables of a serialized dfa
	193	* @blob: aligned serialized stream of data to unpack (NOT NULL)
	194	* @size: size of data to unpack
	195	* @flags: flags controlling what type of accept tables are acceptable
	196	*
	197	* Unpack a dfa that has been serialized. To find information on the dfa
d410fa4e	198	* format look in Documentation/security/apparmor.txt
25985edc	199	* Assumes the dfa @blob stream has been aligned on a 8 byte boundary
e06f75a6 JJ	200	*
	201	* Returns: an unpacked dfa ready for matching or ERR_PTR on failure
	202	*/
	203	struct aa_dfa aa_dfa_unpack(void blob, size_t size, int flags)
	204	{
	205	int hsize;
	206	int error = -ENOMEM;
	207	char *data = blob;
	208	struct table_header *table = NULL;
	209	struct aa_dfa *dfa = kzalloc(sizeof(struct aa_dfa), GFP_KERNEL);
	210	if (!dfa)
	211	goto fail;
	212
	213	kref_init(&dfa->count);
	214
	215	error = -EPROTO;
	216
	217	/* get dfa table set header */
	218	if (size < sizeof(struct table_set_header))
	219	goto fail;
	220
	221	if (ntohl((u32 ) data) != YYTH_MAGIC)
	222	goto fail;
	223
	224	hsize = ntohl((u32 ) (data + 4));
	225	if (size < hsize)
	226	goto fail;
	227
	228	dfa->flags = ntohs((u16 ) (data + 12));
	229	data += hsize;
	230	size -= hsize;
	231
	232	while (size > 0) {
	233	table = unpack_table(data, size);
	234	if (!table)
	235	goto fail;
	236
	237	switch (table->td_id) {
	238	case YYTD_ID_ACCEPT:
	239	if (!(table->td_flags & ACCEPT1_FLAGS(flags)))
	240	goto fail;
	241	break;
	242	case YYTD_ID_ACCEPT2:
	243	if (!(table->td_flags & ACCEPT2_FLAGS(flags)))
	244	goto fail;
	245	break;
	246	case YYTD_ID_BASE:
	247	if (table->td_flags != YYTD_DATA32)
	248	goto fail;
	249	break;
	250	case YYTD_ID_DEF:
	251	case YYTD_ID_NXT:
	252	case YYTD_ID_CHK:
	253	if (table->td_flags != YYTD_DATA16)
	254	goto fail;
	255	break;
	256	case YYTD_ID_EC:
	257	if (table->td_flags != YYTD_DATA8)
	258	goto fail;
	259	break;
	260	default:
	261	goto fail;
	262	}
	263	/* check for duplicate table entry */
264	if (dfa->tables[table->td_id])
265	goto fail;
266	dfa->tables[table->td_id] = table;
267	data += table_size(table->td_lolen, table->td_flags);
268	size -= table_size(table->td_lolen, table->td_flags);
269	table = NULL;
270	}
271
272	error = verify_dfa(dfa, flags);
273	if (error)
274	goto fail;
275
276	return dfa;
277
278	fail:
279	kvfree(table);
280	dfa_free(dfa);
281	return ERR_PTR(error);
282	}
283
284	/**
285	* aa_dfa_match_len - traverse @dfa to find state @str stops at
286	* @dfa: the dfa to match @str against (NOT NULL)
287	* @start: the state of the dfa to start matching in
288	* @str: the string of bytes to match against the dfa (NOT NULL)
289	* @len: length of the string of bytes to match
290	*
291	* aa_dfa_match_len will match @str against the dfa and return the state it
292	* finished matching in. The final state can be used to look up the accepting
293	* label, or as the start state of a continuing match.
294	*
295	* This function will happily match again the 0 byte and only finishes
296	* when @len input is consumed.
297	*
298	* Returns: final state reached after input is consumed
299	*/
300	unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int start,
301	const char *str, int len)
302	{
303	u16 *def = DEFAULT_TABLE(dfa);
304	u32 *base = BASE_TABLE(dfa);
305	u16 *next = NEXT_TABLE(dfa);
306	u16 *check = CHECK_TABLE(dfa);
307	unsigned int state = start, pos;
308
309	if (state == 0)
310	return 0;
311
312	/* current state is <state>, matching character str /
313	if (dfa->tables[YYTD_ID_EC]) {
314	/* Equivalence class table defined */
315	u8 *equiv = EQUIV_TABLE(dfa);
316	/* default is direct to next state */
317	for (; len; len--) {
ed686308	318	pos = base_idx(base[state]) + equiv[(u8) *str++];
e06f75a6 JJ	319	if (check[pos] == state)
	320	state = next[pos];
	321	else
	322	state = def[state];
	323	}
	324	} else {
	325	/* default is direct to next state */
	326	for (; len; len--) {
ed686308	327	pos = base_idx(base[state]) + (u8) *str++;
e06f75a6 JJ	328	if (check[pos] == state)
	329	state = next[pos];
	330	else
	331	state = def[state];
	332	}
	333	}
	334
	335	return state;
	336	}
	337
	338	/**
0fe1212d	339	* aa_dfa_match - traverse @dfa to find state @str stops at
e06f75a6 JJ	340	* @dfa: the dfa to match @str against (NOT NULL)
	341	* @start: the state of the dfa to start matching in
	342	* @str: the null terminated string of bytes to match against the dfa (NOT NULL)
	343	*
0fe1212d	344	* aa_dfa_match will match @str against the dfa and return the state it
e06f75a6 JJ	345	* finished matching in. The final state can be used to look up the accepting
	346	* label, or as the start state of a continuing match.
	347	*
	348	* Returns: final state reached after input is consumed
	349	*/
	350	unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start,
	351	const char *str)
	352	{
0fe1212d JJ	353	u16 *def = DEFAULT_TABLE(dfa);
	354	u32 *base = BASE_TABLE(dfa);
	355	u16 *next = NEXT_TABLE(dfa);
	356	u16 *check = CHECK_TABLE(dfa);
	357	unsigned int state = start, pos;
	358
	359	if (state == 0)
	360	return 0;
	361
	362	/* current state is <state>, matching character str /
	363	if (dfa->tables[YYTD_ID_EC]) {
	364	/* Equivalence class table defined */
	365	u8 *equiv = EQUIV_TABLE(dfa);
	366	/* default is direct to next state */
	367	while (*str) {
ed686308	368	pos = base_idx(base[state]) + equiv[(u8) *str++];
0fe1212d JJ	369	if (check[pos] == state)
	370	state = next[pos];
	371	else
	372	state = def[state];
	373	}
	374	} else {
	375	/* default is direct to next state */
	376	while (*str) {
ed686308	377	pos = base_idx(base[state]) + (u8) *str++;
0fe1212d JJ	378	if (check[pos] == state)
	379	state = next[pos];
	380	else
	381	state = def[state];
	382	}
	383	}
	384
	385	return state;
	386	}
	387
	388	/**
	389	* aa_dfa_next - step one character to the next state in the dfa
	390	* @dfa: the dfa to tranverse (NOT NULL)
	391	* @state: the state to start in
	392	* @c: the input character to transition on
	393	*
	394	* aa_dfa_match will step through the dfa by one input character @c
	395	*
	396	* Returns: state reach after input @c
	397	*/
	398	unsigned int aa_dfa_next(struct aa_dfa *dfa, unsigned int state,
	399	const char c)
	400	{
	401	u16 *def = DEFAULT_TABLE(dfa);
	402	u32 *base = BASE_TABLE(dfa);
	403	u16 *next = NEXT_TABLE(dfa);
	404	u16 *check = CHECK_TABLE(dfa);
	405	unsigned int pos;
	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	/* default is direct to next state */
	412
ed686308	413	pos = base_idx(base[state]) + equiv[(u8) c];
0fe1212d JJ	414	if (check[pos] == state)
	415	state = next[pos];
	416	else
	417	state = def[state];
	418	} else {
	419	/* default is direct to next state */
ed686308	420	pos = base_idx(base[state]) + (u8) c;
0fe1212d JJ	421	if (check[pos] == state)
	422	state = next[pos];
	423	else
	424	state = def[state];
	425	}
	426
	427	return state;
e06f75a6	428	}