Commit | Line | Data |
---|---|---|
b886d83c | 1 | // SPDX-License-Identifier: GPL-2.0-only |
e06f75a6 JJ |
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 | |
8e4ff109 | 8 | * Copyright 2009-2012 Canonical Ltd. |
e06f75a6 JJ |
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 | ||
12557dcb | 19 | #include "include/lib.h" |
e06f75a6 JJ |
20 | #include "include/match.h" |
21 | ||
ed686308 JJ |
22 | #define base_idx(X) ((X) & 0xffffff) |
23 | ||
11c236b8 JJ |
24 | static char nulldfa_src[] = { |
25 | #include "nulldfa.in" | |
26 | }; | |
27 | struct aa_dfa *nulldfa; | |
28 | ||
6e0654d2 JJ |
29 | static char stacksplitdfa_src[] = { |
30 | #include "stacksplitdfa.in" | |
31 | }; | |
32 | struct aa_dfa *stacksplitdfa; | |
33 | ||
11c236b8 JJ |
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)); | |
6e0654d2 JJ |
41 | if (IS_ERR(nulldfa)) { |
42 | error = PTR_ERR(nulldfa); | |
43 | nulldfa = NULL; | |
44 | return error; | |
45 | } | |
11c236b8 | 46 | |
6e0654d2 JJ |
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 | } | |
11c236b8 | 58 | |
6e0654d2 | 59 | return 0; |
11c236b8 JJ |
60 | } |
61 | ||
62 | void aa_teardown_dfa_engine(void) | |
63 | { | |
6e0654d2 | 64 | aa_put_dfa(stacksplitdfa); |
11c236b8 | 65 | aa_put_dfa(nulldfa); |
11c236b8 JJ |
66 | } |
67 | ||
e06f75a6 JJ |
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 | * | |
0ca554b9 | 75 | * NOTE: must be freed by kvfree (not kfree) |
e06f75a6 JJ |
76 | */ |
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 | */ | |
e6e8bf41 | 89 | th.td_id = be16_to_cpu(*(__be16 *) (blob)) - 1; |
15756178 JJ |
90 | if (th.td_id > YYTD_ID_MAX) |
91 | goto out; | |
e6e8bf41 JJ |
92 | th.td_flags = be16_to_cpu(*(__be16 *) (blob + 2)); |
93 | th.td_lolen = be32_to_cpu(*(__be32 *) (blob + 8)); | |
e06f75a6 JJ |
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 | ||
c27c6bd2 JJ |
100 | /* if we have a table it must have some entries */ |
101 | if (th.td_lolen == 0) | |
102 | goto out; | |
e06f75a6 JJ |
103 | tsize = table_size(th.td_lolen, th.td_flags); |
104 | if (bsize < tsize) | |
105 | goto out; | |
106 | ||
a7c3e901 | 107 | table = kvzalloc(tsize, GFP_KERNEL); |
e06f75a6 | 108 | if (table) { |
f4ee2def HS |
109 | table->td_id = th.td_id; |
110 | table->td_flags = th.td_flags; | |
111 | table->td_lolen = th.td_lolen; | |
e06f75a6 JJ |
112 | if (th.td_flags == YYTD_DATA8) |
113 | UNPACK_ARRAY(table->td_data, blob, th.td_lolen, | |
e6e8bf41 | 114 | u8, u8, byte_to_byte); |
e06f75a6 JJ |
115 | else if (th.td_flags == YYTD_DATA16) |
116 | UNPACK_ARRAY(table->td_data, blob, th.td_lolen, | |
e6e8bf41 | 117 | u16, __be16, be16_to_cpu); |
e06f75a6 JJ |
118 | else if (th.td_flags == YYTD_DATA32) |
119 | UNPACK_ARRAY(table->td_data, blob, th.td_lolen, | |
e6e8bf41 | 120 | u32, __be32, be32_to_cpu); |
e06f75a6 JJ |
121 | else |
122 | goto fail; | |
3197f5ad JJ |
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(); | |
e06f75a6 JJ |
128 | } |
129 | ||
130 | out: | |
e06f75a6 JJ |
131 | return table; |
132 | fail: | |
133 | kvfree(table); | |
134 | return NULL; | |
135 | } | |
136 | ||
137 | /** | |
d901d6a2 JJ |
138 | * verify_table_headers - verify that the tables headers are as expected |
139 | * @tables - array of dfa tables to check (NOT NULL) | |
e06f75a6 JJ |
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 | */ | |
d901d6a2 | 147 | static int verify_table_headers(struct table_header **tables, int flags) |
e06f75a6 | 148 | { |
d901d6a2 | 149 | size_t state_count, trans_count; |
e06f75a6 JJ |
150 | int error = -EPROTO; |
151 | ||
152 | /* check that required tables exist */ | |
d901d6a2 JJ |
153 | if (!(tables[YYTD_ID_DEF] && tables[YYTD_ID_BASE] && |
154 | tables[YYTD_ID_NXT] && tables[YYTD_ID_CHK])) | |
e06f75a6 JJ |
155 | goto out; |
156 | ||
157 | /* accept.size == default.size == base.size */ | |
d901d6a2 | 158 | state_count = tables[YYTD_ID_BASE]->td_lolen; |
e06f75a6 | 159 | if (ACCEPT1_FLAGS(flags)) { |
d901d6a2 | 160 | if (!tables[YYTD_ID_ACCEPT]) |
e06f75a6 | 161 | goto out; |
d901d6a2 | 162 | if (state_count != tables[YYTD_ID_ACCEPT]->td_lolen) |
e06f75a6 JJ |
163 | goto out; |
164 | } | |
165 | if (ACCEPT2_FLAGS(flags)) { | |
d901d6a2 | 166 | if (!tables[YYTD_ID_ACCEPT2]) |
e06f75a6 | 167 | goto out; |
d901d6a2 | 168 | if (state_count != tables[YYTD_ID_ACCEPT2]->td_lolen) |
e06f75a6 JJ |
169 | goto out; |
170 | } | |
d901d6a2 | 171 | if (state_count != tables[YYTD_ID_DEF]->td_lolen) |
e06f75a6 JJ |
172 | goto out; |
173 | ||
174 | /* next.size == chk.size */ | |
d901d6a2 JJ |
175 | trans_count = tables[YYTD_ID_NXT]->td_lolen; |
176 | if (trans_count != tables[YYTD_ID_CHK]->td_lolen) | |
e06f75a6 JJ |
177 | goto out; |
178 | ||
179 | /* if equivalence classes then its table size must be 256 */ | |
d901d6a2 | 180 | if (tables[YYTD_ID_EC] && tables[YYTD_ID_EC]->td_lolen != 256) |
e06f75a6 JJ |
181 | goto out; |
182 | ||
d901d6a2 JJ |
183 | error = 0; |
184 | out: | |
185 | return error; | |
186 | } | |
e06f75a6 | 187 | |
d901d6a2 JJ |
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 | */ | |
197 | static int verify_dfa(struct aa_dfa *dfa) | |
198 | { | |
199 | size_t i, state_count, trans_count; | |
d53c9f4d | 200 | int error = -EPROTO; |
d901d6a2 JJ |
201 | |
202 | state_count = dfa->tables[YYTD_ID_BASE]->td_lolen; | |
203 | trans_count = dfa->tables[YYTD_ID_NXT]->td_lolen; | |
c27c6bd2 JJ |
204 | if (state_count == 0) |
205 | goto out; | |
d901d6a2 JJ |
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; | |
c6596969 JJ |
210 | if (BASE_TABLE(dfa)[i] & MATCH_FLAGS_INVALID) { |
211 | pr_err("AppArmor DFA state with invalid match flags"); | |
212 | goto out; | |
213 | } | |
dae60293 JJ |
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 | } | |
0df34a64 JJ |
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 | } | |
d901d6a2 JJ |
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; | |
e06f75a6 JJ |
233 | } |
234 | } | |
235 | ||
d901d6a2 JJ |
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 | ||
031dcc8f | 243 | /* Now that all the other tables are verified, verify diffencoding */ |
d901d6a2 | 244 | for (i = 0; i < state_count; i++) { |
031dcc8f JJ |
245 | size_t j, k; |
246 | ||
d901d6a2 JJ |
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; | |
031dcc8f JJ |
257 | } |
258 | } | |
e06f75a6 | 259 | error = 0; |
d901d6a2 | 260 | |
e06f75a6 JJ |
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 | */ | |
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 | */ | |
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 | |
26fccd9e | 301 | * format look in Documentation/admin-guide/LSM/apparmor.rst |
25985edc | 302 | * Assumes the dfa @blob stream has been aligned on a 8 byte boundary |
e06f75a6 JJ |
303 | * |
304 | * Returns: an unpacked dfa ready for matching or ERR_PTR on failure | |
305 | */ | |
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 | ||
e6e8bf41 | 324 | if (ntohl(*(__be32 *) data) != YYTH_MAGIC) |
e06f75a6 JJ |
325 | goto fail; |
326 | ||
e6e8bf41 | 327 | hsize = ntohl(*(__be32 *) (data + 4)); |
e06f75a6 JJ |
328 | if (size < hsize) |
329 | goto fail; | |
330 | ||
e6e8bf41 | 331 | dfa->flags = ntohs(*(__be16 *) (data + 12)); |
0df34a64 | 332 | if (dfa->flags & ~(YYTH_FLAGS)) |
031dcc8f JJ |
333 | goto fail; |
334 | ||
0df34a64 JJ |
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 | ||
e06f75a6 JJ |
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 | } | |
d901d6a2 | 391 | error = verify_table_headers(dfa->tables, flags); |
e06f75a6 JJ |
392 | if (error) |
393 | goto fail; | |
394 | ||
d901d6a2 JJ |
395 | if (flags & DFA_FLAG_VERIFY_STATES) { |
396 | error = verify_dfa(dfa); | |
397 | if (error) | |
398 | goto fail; | |
399 | } | |
400 | ||
e06f75a6 JJ |
401 | return dfa; |
402 | ||
403 | fail: | |
404 | kvfree(table); | |
405 | dfa_free(dfa); | |
406 | return ERR_PTR(error); | |
407 | } | |
408 | ||
074c1cd7 JJ |
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)]; \ | |
031dcc8f JJ |
415 | if (b & MATCH_FLAG_DIFF_ENCODE) \ |
416 | continue; \ | |
074c1cd7 JJ |
417 | break; \ |
418 | } \ | |
419 | (state) = (next)[pos]; \ | |
420 | break; \ | |
421 | } while (1) | |
422 | ||
e06f75a6 JJ |
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 | */ | |
33fc95d8 JJ |
439 | aa_state_t aa_dfa_match_len(struct aa_dfa *dfa, aa_state_t start, |
440 | const char *str, int len) | |
e06f75a6 JJ |
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); | |
33fc95d8 | 446 | aa_state_t state = start; |
e06f75a6 | 447 | |
33fc95d8 JJ |
448 | if (state == DFA_NOMATCH) |
449 | return DFA_NOMATCH; | |
e06f75a6 JJ |
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); | |
074c1cd7 JJ |
455 | for (; len; len--) |
456 | match_char(state, def, base, next, check, | |
457 | equiv[(u8) *str++]); | |
e06f75a6 JJ |
458 | } else { |
459 | /* default is direct to next state */ | |
074c1cd7 JJ |
460 | for (; len; len--) |
461 | match_char(state, def, base, next, check, (u8) *str++); | |
e06f75a6 JJ |
462 | } |
463 | ||
464 | return state; | |
465 | } | |
466 | ||
467 | /** | |
0fe1212d | 468 | * aa_dfa_match - traverse @dfa to find state @str stops at |
e06f75a6 JJ |
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 | * | |
0fe1212d | 473 | * aa_dfa_match will match @str against the dfa and return the state it |
e06f75a6 JJ |
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 | */ | |
33fc95d8 | 479 | aa_state_t aa_dfa_match(struct aa_dfa *dfa, aa_state_t start, const char *str) |
e06f75a6 | 480 | { |
0fe1212d JJ |
481 | u16 *def = DEFAULT_TABLE(dfa); |
482 | u32 *base = BASE_TABLE(dfa); | |
483 | u16 *next = NEXT_TABLE(dfa); | |
484 | u16 *check = CHECK_TABLE(dfa); | |
33fc95d8 | 485 | aa_state_t state = start; |
0fe1212d | 486 | |
33fc95d8 JJ |
487 | if (state == DFA_NOMATCH) |
488 | return DFA_NOMATCH; | |
0fe1212d JJ |
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 */ | |
074c1cd7 JJ |
495 | while (*str) |
496 | match_char(state, def, base, next, check, | |
497 | equiv[(u8) *str++]); | |
0fe1212d JJ |
498 | } else { |
499 | /* default is direct to next state */ | |
074c1cd7 JJ |
500 | while (*str) |
501 | match_char(state, def, base, next, check, (u8) *str++); | |
0fe1212d JJ |
502 | } |
503 | ||
504 | return state; | |
505 | } | |
506 | ||
507 | /** | |
508 | * aa_dfa_next - step one character to the next state in the dfa | |
5d2371e1 | 509 | * @dfa: the dfa to traverse (NOT NULL) |
0fe1212d JJ |
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 | */ | |
33fc95d8 | 517 | aa_state_t aa_dfa_next(struct aa_dfa *dfa, aa_state_t state, const char c) |
0fe1212d JJ |
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); | |
0fe1212d JJ |
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); | |
074c1cd7 JJ |
528 | match_char(state, def, base, next, check, equiv[(u8) c]); |
529 | } else | |
530 | match_char(state, def, base, next, check, (u8) c); | |
0fe1212d JJ |
531 | |
532 | return state; | |
e06f75a6 | 533 | } |
cf65fabc | 534 | |
33fc95d8 | 535 | aa_state_t aa_dfa_outofband_transition(struct aa_dfa *dfa, aa_state_t state) |
0df34a64 JJ |
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 | ||
cf65fabc JJ |
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 | */ | |
33fc95d8 | 565 | aa_state_t aa_dfa_match_until(struct aa_dfa *dfa, aa_state_t start, |
cf65fabc JJ |
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); | |
33fc95d8 | 573 | aa_state_t state = start, pos; |
cf65fabc | 574 | |
33fc95d8 JJ |
575 | if (state == DFA_NOMATCH) |
576 | return DFA_NOMATCH; | |
cf65fabc JJ |
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 | ||
cf65fabc JJ |
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 | */ | |
33fc95d8 | 626 | aa_state_t aa_dfa_matchn_until(struct aa_dfa *dfa, aa_state_t start, |
cf65fabc JJ |
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); | |
33fc95d8 | 634 | aa_state_t state = start, pos; |
cf65fabc JJ |
635 | |
636 | *retpos = NULL; | |
33fc95d8 JJ |
637 | if (state == DFA_NOMATCH) |
638 | return DFA_NOMATCH; | |
cf65fabc JJ |
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 | } | |
21f60661 JJ |
670 | |
671 | #define inc_wb_pos(wb) \ | |
672 | do { \ | |
136db994 JJ |
673 | wb->pos = (wb->pos + 1) & (WB_HISTORY_SIZE - 1); \ |
674 | wb->len = (wb->len + 1) & (WB_HISTORY_SIZE - 1); \ | |
21f60661 JJ |
675 | } while (0) |
676 | ||
677 | /* For DFAs that don't support extended tagging of states */ | |
33fc95d8 | 678 | static bool is_loop(struct match_workbuf *wb, aa_state_t state, |
21f60661 JJ |
679 | unsigned int *adjust) |
680 | { | |
33fc95d8 JJ |
681 | aa_state_t pos = wb->pos; |
682 | aa_state_t i; | |
21f60661 JJ |
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) | |
136db994 | 693 | pos = WB_HISTORY_SIZE; |
21f60661 JJ |
694 | pos--; |
695 | } | |
696 | ||
697 | *adjust = i; | |
698 | return true; | |
699 | } | |
700 | ||
33fc95d8 | 701 | static aa_state_t leftmatch_fb(struct aa_dfa *dfa, aa_state_t start, |
21f60661 JJ |
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); | |
33fc95d8 | 709 | aa_state_t state = start, pos; |
21f60661 JJ |
710 | |
711 | AA_BUG(!dfa); | |
712 | AA_BUG(!str); | |
713 | AA_BUG(!wb); | |
714 | AA_BUG(!count); | |
715 | ||
716 | *count = 0; | |
33fc95d8 JJ |
717 | if (state == DFA_NOMATCH) |
718 | return DFA_NOMATCH; | |
21f60661 JJ |
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 | */ | |
33fc95d8 JJ |
782 | aa_state_t aa_dfa_leftmatch(struct aa_dfa *dfa, aa_state_t start, |
783 | const char *str, unsigned int *count) | |
21f60661 JJ |
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 | } |