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 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 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,unsigned int start,const char * str,int len)439 unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int 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 	unsigned int state = start;
447 
448 	if (state == 0)
449 		return 0;
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,unsigned int start,const char * str)479 unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start,
480 			  const char *str)
481 {
482 	u16 *def = DEFAULT_TABLE(dfa);
483 	u32 *base = BASE_TABLE(dfa);
484 	u16 *next = NEXT_TABLE(dfa);
485 	u16 *check = CHECK_TABLE(dfa);
486 	unsigned int state = start;
487 
488 	if (state == 0)
489 		return 0;
490 
491 	/* current state is <state>, matching character *str */
492 	if (dfa->tables[YYTD_ID_EC]) {
493 		/* Equivalence class table defined */
494 		u8 *equiv = EQUIV_TABLE(dfa);
495 		/* default is direct to next state */
496 		while (*str)
497 			match_char(state, def, base, next, check,
498 				   equiv[(u8) *str++]);
499 	} else {
500 		/* default is direct to next state */
501 		while (*str)
502 			match_char(state, def, base, next, check, (u8) *str++);
503 	}
504 
505 	return state;
506 }
507 
508 /**
509  * aa_dfa_next - step one character to the next state in the dfa
510  * @dfa: the dfa to traverse (NOT NULL)
511  * @state: the state to start in
512  * @c: the input character to transition on
513  *
514  * aa_dfa_match will step through the dfa by one input character @c
515  *
516  * Returns: state reach after input @c
517  */
aa_dfa_next(struct aa_dfa * dfa,unsigned int state,const char c)518 unsigned int aa_dfa_next(struct aa_dfa *dfa, unsigned int state,
519 			  const char c)
520 {
521 	u16 *def = DEFAULT_TABLE(dfa);
522 	u32 *base = BASE_TABLE(dfa);
523 	u16 *next = NEXT_TABLE(dfa);
524 	u16 *check = CHECK_TABLE(dfa);
525 
526 	/* current state is <state>, matching character *str */
527 	if (dfa->tables[YYTD_ID_EC]) {
528 		/* Equivalence class table defined */
529 		u8 *equiv = EQUIV_TABLE(dfa);
530 		match_char(state, def, base, next, check, equiv[(u8) c]);
531 	} else
532 		match_char(state, def, base, next, check, (u8) c);
533 
534 	return state;
535 }
536 
aa_dfa_outofband_transition(struct aa_dfa * dfa,unsigned int state)537 unsigned int aa_dfa_outofband_transition(struct aa_dfa *dfa, unsigned int state)
538 {
539 	u16 *def = DEFAULT_TABLE(dfa);
540 	u32 *base = BASE_TABLE(dfa);
541 	u16 *next = NEXT_TABLE(dfa);
542 	u16 *check = CHECK_TABLE(dfa);
543 	u32 b = (base)[(state)];
544 
545 	if (!(b & MATCH_FLAG_OOB_TRANSITION))
546 		return DFA_NOMATCH;
547 
548 	/* No Equivalence class remapping for outofband transitions */
549 	match_char(state, def, base, next, check, -1);
550 
551 	return state;
552 }
553 
554 /**
555  * aa_dfa_match_until - traverse @dfa until accept state or end of input
556  * @dfa: the dfa to match @str against  (NOT NULL)
557  * @start: the state of the dfa to start matching in
558  * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
559  * @retpos: first character in str after match OR end of string
560  *
561  * aa_dfa_match will match @str against the dfa and return the state it
562  * finished matching in. The final state can be used to look up the accepting
563  * label, or as the start state of a continuing match.
564  *
565  * Returns: final state reached after input is consumed
566  */
aa_dfa_match_until(struct aa_dfa * dfa,unsigned int start,const char * str,const char ** retpos)567 unsigned int aa_dfa_match_until(struct aa_dfa *dfa, unsigned int start,
568 				const char *str, const char **retpos)
569 {
570 	u16 *def = DEFAULT_TABLE(dfa);
571 	u32 *base = BASE_TABLE(dfa);
572 	u16 *next = NEXT_TABLE(dfa);
573 	u16 *check = CHECK_TABLE(dfa);
574 	u32 *accept = ACCEPT_TABLE(dfa);
575 	unsigned int state = start, pos;
576 
577 	if (state == 0)
578 		return 0;
579 
580 	/* current state is <state>, matching character *str */
581 	if (dfa->tables[YYTD_ID_EC]) {
582 		/* Equivalence class table defined */
583 		u8 *equiv = EQUIV_TABLE(dfa);
584 		/* default is direct to next state */
585 		while (*str) {
586 			pos = base_idx(base[state]) + equiv[(u8) *str++];
587 			if (check[pos] == state)
588 				state = next[pos];
589 			else
590 				state = def[state];
591 			if (accept[state])
592 				break;
593 		}
594 	} else {
595 		/* default is direct to next state */
596 		while (*str) {
597 			pos = base_idx(base[state]) + (u8) *str++;
598 			if (check[pos] == state)
599 				state = next[pos];
600 			else
601 				state = def[state];
602 			if (accept[state])
603 				break;
604 		}
605 	}
606 
607 	*retpos = str;
608 	return state;
609 }
610 
611 /**
612  * aa_dfa_matchn_until - traverse @dfa until accept or @n bytes consumed
613  * @dfa: the dfa to match @str against  (NOT NULL)
614  * @start: the state of the dfa to start matching in
615  * @str: the string of bytes to match against the dfa  (NOT NULL)
616  * @n: length of the string of bytes to match
617  * @retpos: first character in str after match OR str + n
618  *
619  * aa_dfa_match_len will match @str against the dfa and return the state it
620  * finished matching in. The final state can be used to look up the accepting
621  * label, or as the start state of a continuing match.
622  *
623  * This function will happily match again the 0 byte and only finishes
624  * when @n input is consumed.
625  *
626  * Returns: final state reached after input is consumed
627  */
aa_dfa_matchn_until(struct aa_dfa * dfa,unsigned int start,const char * str,int n,const char ** retpos)628 unsigned int aa_dfa_matchn_until(struct aa_dfa *dfa, unsigned int start,
629 				 const char *str, int n, const char **retpos)
630 {
631 	u16 *def = DEFAULT_TABLE(dfa);
632 	u32 *base = BASE_TABLE(dfa);
633 	u16 *next = NEXT_TABLE(dfa);
634 	u16 *check = CHECK_TABLE(dfa);
635 	u32 *accept = ACCEPT_TABLE(dfa);
636 	unsigned int state = start, pos;
637 
638 	*retpos = NULL;
639 	if (state == 0)
640 		return 0;
641 
642 	/* current state is <state>, matching character *str */
643 	if (dfa->tables[YYTD_ID_EC]) {
644 		/* Equivalence class table defined */
645 		u8 *equiv = EQUIV_TABLE(dfa);
646 		/* default is direct to next state */
647 		for (; n; n--) {
648 			pos = base_idx(base[state]) + equiv[(u8) *str++];
649 			if (check[pos] == state)
650 				state = next[pos];
651 			else
652 				state = def[state];
653 			if (accept[state])
654 				break;
655 		}
656 	} else {
657 		/* default is direct to next state */
658 		for (; n; n--) {
659 			pos = base_idx(base[state]) + (u8) *str++;
660 			if (check[pos] == state)
661 				state = next[pos];
662 			else
663 				state = def[state];
664 			if (accept[state])
665 				break;
666 		}
667 	}
668 
669 	*retpos = str;
670 	return state;
671 }
672 
673 #define inc_wb_pos(wb)						\
674 do {								\
675 	wb->pos = (wb->pos + 1) & (WB_HISTORY_SIZE - 1);		\
676 	wb->len = (wb->len + 1) & (WB_HISTORY_SIZE - 1);		\
677 } while (0)
678 
679 /* For DFAs that don't support extended tagging of states */
is_loop(struct match_workbuf * wb,unsigned int state,unsigned int * adjust)680 static bool is_loop(struct match_workbuf *wb, unsigned int state,
681 		    unsigned int *adjust)
682 {
683 	unsigned int pos = wb->pos;
684 	unsigned int i;
685 
686 	if (wb->history[pos] < state)
687 		return false;
688 
689 	for (i = 0; i <= wb->len; i++) {
690 		if (wb->history[pos] == state) {
691 			*adjust = i;
692 			return true;
693 		}
694 		if (pos == 0)
695 			pos = WB_HISTORY_SIZE;
696 		pos--;
697 	}
698 
699 	*adjust = i;
700 	return true;
701 }
702 
leftmatch_fb(struct aa_dfa * dfa,unsigned int start,const char * str,struct match_workbuf * wb,unsigned int * count)703 static unsigned int leftmatch_fb(struct aa_dfa *dfa, unsigned int start,
704 				 const char *str, struct match_workbuf *wb,
705 				 unsigned int *count)
706 {
707 	u16 *def = DEFAULT_TABLE(dfa);
708 	u32 *base = BASE_TABLE(dfa);
709 	u16 *next = NEXT_TABLE(dfa);
710 	u16 *check = CHECK_TABLE(dfa);
711 	unsigned int state = start, pos;
712 
713 	AA_BUG(!dfa);
714 	AA_BUG(!str);
715 	AA_BUG(!wb);
716 	AA_BUG(!count);
717 
718 	*count = 0;
719 	if (state == 0)
720 		return 0;
721 
722 	/* current state is <state>, matching character *str */
723 	if (dfa->tables[YYTD_ID_EC]) {
724 		/* Equivalence class table defined */
725 		u8 *equiv = EQUIV_TABLE(dfa);
726 		/* default is direct to next state */
727 		while (*str) {
728 			unsigned int adjust;
729 
730 			wb->history[wb->pos] = state;
731 			pos = base_idx(base[state]) + equiv[(u8) *str++];
732 			if (check[pos] == state)
733 				state = next[pos];
734 			else
735 				state = def[state];
736 			if (is_loop(wb, state, &adjust)) {
737 				state = aa_dfa_match(dfa, state, str);
738 				*count -= adjust;
739 				goto out;
740 			}
741 			inc_wb_pos(wb);
742 			(*count)++;
743 		}
744 	} else {
745 		/* default is direct to next state */
746 		while (*str) {
747 			unsigned int adjust;
748 
749 			wb->history[wb->pos] = state;
750 			pos = base_idx(base[state]) + (u8) *str++;
751 			if (check[pos] == state)
752 				state = next[pos];
753 			else
754 				state = def[state];
755 			if (is_loop(wb, state, &adjust)) {
756 				state = aa_dfa_match(dfa, state, str);
757 				*count -= adjust;
758 				goto out;
759 			}
760 			inc_wb_pos(wb);
761 			(*count)++;
762 		}
763 	}
764 
765 out:
766 	if (!state)
767 		*count = 0;
768 	return state;
769 }
770 
771 /**
772  * aa_dfa_leftmatch - traverse @dfa to find state @str stops at
773  * @dfa: the dfa to match @str against  (NOT NULL)
774  * @start: the state of the dfa to start matching in
775  * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
776  * @count: current count of longest left.
777  *
778  * aa_dfa_match will match @str against the dfa and return the state it
779  * finished matching in. The final state can be used to look up the accepting
780  * label, or as the start state of a continuing match.
781  *
782  * Returns: final state reached after input is consumed
783  */
aa_dfa_leftmatch(struct aa_dfa * dfa,unsigned int start,const char * str,unsigned int * count)784 unsigned int aa_dfa_leftmatch(struct aa_dfa *dfa, unsigned int start,
785 			      const char *str, unsigned int *count)
786 {
787 	DEFINE_MATCH_WB(wb);
788 
789 	/* TODO: match for extended state dfas */
790 
791 	return leftmatch_fb(dfa, start, str, &wb, count);
792 }
793