[mirror_ubuntu-artful-kernel.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/lib.h"
#include "include/match.h"

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

static char nulldfa_src[] = {
	#include "nulldfa.in"
};
struct aa_dfa *nulldfa;

int aa_setup_dfa_engine(void)
{
	int error;

	nulldfa = aa_dfa_unpack(nulldfa_src, sizeof(nulldfa_src),
				TO_ACCEPT1_FLAG(YYTD_DATA32) |
				TO_ACCEPT2_FLAG(YYTD_DATA32));
	if (!IS_ERR(nulldfa))
		return 0;

	error = PTR_ERR(nulldfa);
	nulldfa = NULL;

	return error;
}

void aa_teardown_dfa_engine(void)
{
	aa_put_dfa(nulldfa);
	nulldfa = NULL;
}

/**
 * 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(*(__be16 *) (blob)) - 1;
	if (th.td_id > YYTD_ID_MAX)
		goto out;
	th.td_flags = be16_to_cpu(*(__be16 *) (blob + 2));
	th.td_lolen = be32_to_cpu(*(__be32 *) (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->td_id = th.td_id;
		table->td_flags = th.td_flags;
		table->td_lolen = th.td_lolen;
		if (th.td_flags == YYTD_DATA8)
			UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
				     u8, u8, byte_to_byte);
		else if (th.td_flags == YYTD_DATA16)
			UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
				     u16, __be16, be16_to_cpu);
		else if (th.td_flags == YYTD_DATA32)
			UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
				     u32, __be32, 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(*(__be32 *) data) != YYTH_MAGIC)
		goto fail;

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

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