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 | */ | |
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); | |
074c1cd7 | 446 | unsigned int state = start; |
e06f75a6 JJ |
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); | |
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 | */ | |
479 | unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start, | |
480 | const char *str) | |
481 | { | |
0fe1212d JJ |
482 | u16 *def = DEFAULT_TABLE(dfa); |
483 | u32 *base = BASE_TABLE(dfa); | |
484 | u16 *next = NEXT_TABLE(dfa); | |
485 | u16 *check = CHECK_TABLE(dfa); | |
074c1cd7 | 486 | unsigned int state = start; |
0fe1212d JJ |
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 */ | |
074c1cd7 JJ |
496 | while (*str) |
497 | match_char(state, def, base, next, check, | |
498 | equiv[(u8) *str++]); | |
0fe1212d JJ |
499 | } else { |
500 | /* default is direct to next state */ | |
074c1cd7 JJ |
501 | while (*str) |
502 | match_char(state, def, base, next, check, (u8) *str++); | |
0fe1212d JJ |
503 | } |
504 | ||
505 | return state; | |
506 | } | |
507 | ||
508 | /** | |
509 | * aa_dfa_next - step one character to the next state in the dfa | |
5d2371e1 | 510 | * @dfa: the dfa to traverse (NOT NULL) |
0fe1212d JJ |
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 | */ | |
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); | |
0fe1212d JJ |
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); | |
074c1cd7 JJ |
530 | match_char(state, def, base, next, check, equiv[(u8) c]); |
531 | } else | |
532 | match_char(state, def, base, next, check, (u8) c); | |
0fe1212d JJ |
533 | |
534 | return state; | |
e06f75a6 | 535 | } |
cf65fabc | 536 | |
0df34a64 JJ |
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 | ||
cf65fabc JJ |
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 | */ | |
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 | ||
cf65fabc JJ |
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 | */ | |
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 | } | |
21f60661 JJ |
672 | |
673 | #define inc_wb_pos(wb) \ | |
674 | do { \ | |
136db994 JJ |
675 | wb->pos = (wb->pos + 1) & (WB_HISTORY_SIZE - 1); \ |
676 | wb->len = (wb->len + 1) & (WB_HISTORY_SIZE - 1); \ | |
21f60661 JJ |
677 | } while (0) |
678 | ||
679 | /* For DFAs that don't support extended tagging of states */ | |
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) | |
136db994 | 695 | pos = WB_HISTORY_SIZE; |
21f60661 JJ |
696 | pos--; |
697 | } | |
698 | ||
699 | *adjust = i; | |
700 | return true; | |
701 | } | |
702 | ||
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 | */ | |
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 | } |