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