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