1 | /* |
2 | * Copyright (c) 2015-2016, Intel Corporation |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions are met: |
6 | * |
7 | * * Redistributions of source code must retain the above copyright notice, |
8 | * this list of conditions and the following disclaimer. |
9 | * * Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * * Neither the name of Intel Corporation nor the names of its contributors |
13 | * may be used to endorse or promote products derived from this software |
14 | * without specific prior written permission. |
15 | * |
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
26 | * POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
28 | |
29 | #include "repeat.h" |
30 | #include "util/join.h" |
31 | |
32 | /* impl of limex functions which depend only on state size */ |
33 | |
34 | #if !defined(SIZE) || !defined(STATE_T) || !defined(LOAD_FROM_ENG) \ |
35 | || !defined(INLINE_ATTR) |
36 | # error Must define SIZE, STATE_T, LOAD_FROM_ENG and INLINE_ATTR in includer. |
37 | #endif |
38 | |
39 | #define IMPL_NFA_T JOIN(struct LimExNFA, SIZE) |
40 | |
41 | #define TESTEOD_FN JOIN(moNfaTestEod, SIZE) |
42 | #define LIMEX_INACCEPT_FN JOIN(limexInAccept, SIZE) |
43 | #define LIMEX_INANYACCEPT_FN JOIN(limexInAnyAccept, SIZE) |
44 | #define EXPIRE_ESTATE_FN JOIN(limexExpireExtendedState, SIZE) |
45 | #define REPORTCURRENT_FN JOIN(moNfaReportCurrent, SIZE) |
46 | #define INITIAL_FN JOIN(moNfaInitial, SIZE) |
47 | #define TOP_FN JOIN(moNfaTop, SIZE) |
48 | #define TOPN_FN JOIN(moNfaTopN, SIZE) |
49 | #define PROCESS_ACCEPTS_IMPL_FN JOIN(moProcessAcceptsImpl, SIZE) |
50 | #define PROCESS_ACCEPTS_FN JOIN(moProcessAccepts, SIZE) |
51 | #define PROCESS_ACCEPTS_NOSQUASH_FN JOIN(moProcessAcceptsNoSquash, SIZE) |
52 | #define CONTEXT_T JOIN(NFAContext, SIZE) |
53 | #define ONES_STATE JOIN(ones_, STATE_T) |
54 | #define AND_STATE JOIN(and_, STATE_T) |
55 | #define OR_STATE JOIN(or_, STATE_T) |
56 | #define ANDNOT_STATE JOIN(andnot_, STATE_T) |
57 | #define CLEARBIT_STATE JOIN(clearbit_, STATE_T) |
58 | #define TESTBIT_STATE JOIN(testbit_, STATE_T) |
59 | #define ISNONZERO_STATE JOIN(isNonZero_, STATE_T) |
60 | #define ISZERO_STATE JOIN(isZero_, STATE_T) |
61 | #define SQUASH_UNTUG_BR_FN JOIN(lazyTug, SIZE) |
62 | #define GET_NFA_REPEAT_INFO_FN JOIN(getNfaRepeatInfo, SIZE) |
63 | |
64 | #if defined(ARCH_64_BIT) && (SIZE >= 64) |
65 | #define CHUNK_T u64a |
66 | #define FIND_AND_CLEAR_FN findAndClearLSB_64 |
67 | #define POPCOUNT_FN popcount64 |
68 | #define RANK_IN_MASK_FN rank_in_mask64 |
69 | #else |
70 | #define CHUNK_T u32 |
71 | #define FIND_AND_CLEAR_FN findAndClearLSB_32 |
72 | #define POPCOUNT_FN popcount32 |
73 | #define RANK_IN_MASK_FN rank_in_mask32 |
74 | #endif |
75 | |
76 | #define NUM_STATE_CHUNKS (sizeof(STATE_T) / sizeof(CHUNK_T)) |
77 | |
78 | static really_inline |
79 | void SQUASH_UNTUG_BR_FN(const IMPL_NFA_T *limex, |
80 | const union RepeatControl *repeat_ctrl, |
81 | const char *repeat_state, u64a offset, |
82 | STATE_T *accstate) { |
83 | // switch off cyclic tug-accepts which aren't tuggable right now. |
84 | |
85 | /* TODO: might be nice to work which br to examine based on accstate rather |
86 | * than iterating overall br */ |
87 | |
88 | if (!limex->repeatCount) { |
89 | return; |
90 | } |
91 | |
92 | assert(repeat_ctrl); |
93 | assert(repeat_state); |
94 | |
95 | for (u32 i = 0; i < limex->repeatCount; i++) { |
96 | const struct NFARepeatInfo *info = GET_NFA_REPEAT_INFO_FN(limex, i); |
97 | |
98 | u32 cyclicState = info->cyclicState; |
99 | if (!TESTBIT_STATE(*accstate, cyclicState)) { |
100 | continue; |
101 | } |
102 | |
103 | DEBUG_PRINTF("repeat %u (cyclic state %u) is active\n" , i, cyclicState); |
104 | DEBUG_PRINTF("checking if offset %llu would match\n" , offset); |
105 | |
106 | const union RepeatControl *ctrl = repeat_ctrl + i; |
107 | const char *state = repeat_state + info->stateOffset; |
108 | const struct RepeatInfo *repeat = getRepeatInfo(info); |
109 | if (repeatHasMatch(repeat, ctrl, state, offset) != REPEAT_MATCH) { |
110 | DEBUG_PRINTF("not ready to accept yet\n" ); |
111 | CLEARBIT_STATE(accstate, cyclicState); |
112 | } |
113 | } |
114 | } |
115 | |
116 | static really_inline |
117 | char PROCESS_ACCEPTS_IMPL_FN(const IMPL_NFA_T *limex, const STATE_T *s, |
118 | STATE_T *squash, const STATE_T *acceptMask, |
119 | const struct NFAAccept *acceptTable, u64a offset, |
120 | NfaCallback callback, void *context) { |
121 | assert(s); |
122 | assert(limex); |
123 | assert(callback); |
124 | |
125 | const STATE_T accept_mask = *acceptMask; |
126 | STATE_T accepts = AND_STATE(*s, accept_mask); |
127 | |
128 | // Caller must ensure that we have at least one accept state on. |
129 | assert(ISNONZERO_STATE(accepts)); |
130 | |
131 | CHUNK_T chunks[NUM_STATE_CHUNKS]; |
132 | memcpy(chunks, &accepts, sizeof(accepts)); |
133 | |
134 | CHUNK_T mask_chunks[NUM_STATE_CHUNKS]; |
135 | memcpy(mask_chunks, &accept_mask, sizeof(accept_mask)); |
136 | |
137 | u32 base_index = 0; // Cumulative sum of mask popcount up to current chunk. |
138 | for (u32 i = 0; i < NUM_STATE_CHUNKS; i++) { |
139 | CHUNK_T chunk = chunks[i]; |
140 | while (chunk != 0) { |
141 | u32 bit = FIND_AND_CLEAR_FN(&chunk); |
142 | u32 local_idx = RANK_IN_MASK_FN(mask_chunks[i], bit); |
143 | u32 idx = local_idx + base_index; |
144 | const struct NFAAccept *a = &acceptTable[idx]; |
145 | DEBUG_PRINTF("state %u: firing report list=%u, offset=%llu\n" , |
146 | bit + i * (u32)sizeof(chunk) * 8, a->reports, offset); |
147 | int rv = limexRunAccept((const char *)limex, a, callback, context, |
148 | offset); |
149 | if (unlikely(rv == MO_HALT_MATCHING)) { |
150 | return 1; |
151 | } |
152 | if (squash != NULL && a->squash != MO_INVALID_IDX) { |
153 | DEBUG_PRINTF("applying squash mask at offset %u\n" , a->squash); |
154 | const ENG_STATE_T *sq = |
155 | (const ENG_STATE_T *)((const char *)limex + a->squash); |
156 | *squash = AND_STATE(*squash, LOAD_FROM_ENG(sq)); |
157 | } |
158 | } |
159 | base_index += POPCOUNT_FN(mask_chunks[i]); |
160 | } |
161 | |
162 | return 0; |
163 | } |
164 | |
165 | static never_inline |
166 | char PROCESS_ACCEPTS_FN(const IMPL_NFA_T *limex, STATE_T *s, |
167 | const STATE_T *acceptMask, |
168 | const struct NFAAccept *acceptTable, u64a offset, |
169 | NfaCallback callback, void *context) { |
170 | // We have squash masks we might have to apply after firing reports. |
171 | STATE_T squash = ONES_STATE; |
172 | return PROCESS_ACCEPTS_IMPL_FN(limex, s, &squash, acceptMask, acceptTable, |
173 | offset, callback, context); |
174 | |
175 | *s = AND_STATE(*s, squash); |
176 | } |
177 | |
178 | static never_inline |
179 | char PROCESS_ACCEPTS_NOSQUASH_FN(const IMPL_NFA_T *limex, const STATE_T *s, |
180 | const STATE_T *acceptMask, |
181 | const struct NFAAccept *acceptTable, |
182 | u64a offset, NfaCallback callback, |
183 | void *context) { |
184 | STATE_T *squash = NULL; |
185 | return PROCESS_ACCEPTS_IMPL_FN(limex, s, squash, acceptMask, acceptTable, |
186 | offset, callback, context); |
187 | } |
188 | |
189 | // Run EOD accepts. Note that repeat_ctrl and repeat_state may be NULL if this |
190 | // LimEx contains no repeat structures. |
191 | static really_inline |
192 | char TESTEOD_FN(const IMPL_NFA_T *limex, const STATE_T *s, |
193 | const union RepeatControl *repeat_ctrl, |
194 | const char *repeat_state, u64a offset, |
195 | NfaCallback callback, void *context) { |
196 | assert(limex && s); |
197 | |
198 | // There may not be any EOD accepts in this NFA. |
199 | if (!limex->acceptEodCount) { |
200 | return MO_CONTINUE_MATCHING; |
201 | } |
202 | |
203 | const STATE_T acceptEodMask = LOAD_FROM_ENG(&limex->acceptAtEOD); |
204 | STATE_T foundAccepts = AND_STATE(*s, acceptEodMask); |
205 | |
206 | SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state, |
207 | offset + 1 /* EOD 'symbol' */, &foundAccepts); |
208 | |
209 | if (unlikely(ISNONZERO_STATE(foundAccepts))) { |
210 | const struct NFAAccept *acceptEodTable = getAcceptEodTable(limex); |
211 | if (PROCESS_ACCEPTS_NOSQUASH_FN(limex, &foundAccepts, &acceptEodMask, |
212 | acceptEodTable, offset, callback, |
213 | context)) { |
214 | return MO_HALT_MATCHING; |
215 | } |
216 | } |
217 | |
218 | return MO_CONTINUE_MATCHING; |
219 | } |
220 | |
221 | // Run accepts corresponding to current state. |
222 | static really_inline |
223 | char REPORTCURRENT_FN(const IMPL_NFA_T *limex, const struct mq *q) { |
224 | assert(limex && q); |
225 | assert(q->state); |
226 | assert(q_cur_type(q) == MQE_START); |
227 | |
228 | STATE_T s = *(STATE_T *)q->state; |
229 | STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept); |
230 | STATE_T foundAccepts = AND_STATE(s, acceptMask); |
231 | |
232 | if (unlikely(ISNONZERO_STATE(foundAccepts))) { |
233 | DEBUG_PRINTF("found accepts\n" ); |
234 | DEBUG_PRINTF("for nfa %p\n" , limex); |
235 | const struct NFAAccept *acceptTable = getAcceptTable(limex); |
236 | u64a offset = q_cur_offset(q); |
237 | |
238 | if (PROCESS_ACCEPTS_NOSQUASH_FN(limex, &foundAccepts, &acceptMask, |
239 | acceptTable, offset, q->cb, |
240 | q->context)) { |
241 | return MO_HALT_MATCHING; |
242 | } |
243 | } |
244 | |
245 | return MO_CONTINUE_MATCHING; |
246 | } |
247 | |
248 | static really_inline |
249 | STATE_T INITIAL_FN(const IMPL_NFA_T *impl, char onlyDs) { |
250 | return LOAD_FROM_ENG(onlyDs ? &impl->initDS : &impl->init); |
251 | } |
252 | |
253 | static really_inline |
254 | STATE_T TOP_FN(const IMPL_NFA_T *impl, char onlyDs, STATE_T state) { |
255 | return OR_STATE(INITIAL_FN(impl, onlyDs), state); |
256 | } |
257 | |
258 | static really_inline |
259 | STATE_T TOPN_FN(const IMPL_NFA_T *limex, STATE_T state, u32 n) { |
260 | assert(n < limex->topCount); |
261 | const ENG_STATE_T *topsptr = |
262 | (const ENG_STATE_T *)((const char *)limex + limex->topOffset); |
263 | STATE_T top = LOAD_FROM_ENG(&topsptr[n]); |
264 | return OR_STATE(top, state); |
265 | } |
266 | |
267 | static really_inline |
268 | void EXPIRE_ESTATE_FN(const IMPL_NFA_T *limex, struct CONTEXT_T *ctx, |
269 | u64a offset) { |
270 | assert(limex); |
271 | assert(ctx); |
272 | |
273 | if (!limex->repeatCount) { |
274 | return; |
275 | } |
276 | |
277 | DEBUG_PRINTF("expire estate at offset %llu\n" , offset); |
278 | |
279 | const STATE_T cyclics |
280 | = AND_STATE(ctx->s, LOAD_FROM_ENG(&limex->repeatCyclicMask)); |
281 | if (ISZERO_STATE(cyclics)) { |
282 | DEBUG_PRINTF("no cyclic states are on\n" ); |
283 | return; |
284 | } |
285 | |
286 | for (u32 i = 0; i < limex->repeatCount; i++) { |
287 | const struct NFARepeatInfo *info = GET_NFA_REPEAT_INFO_FN(limex, i); |
288 | |
289 | u32 cyclicState = info->cyclicState; |
290 | if (!TESTBIT_STATE(cyclics, cyclicState)) { |
291 | continue; |
292 | } |
293 | |
294 | DEBUG_PRINTF("repeat %u (cyclic state %u) is active\n" , i, |
295 | cyclicState); |
296 | |
297 | const struct RepeatInfo *repeat = getRepeatInfo(info); |
298 | if (repeat->repeatMax == REPEAT_INF) { |
299 | continue; // can't expire |
300 | } |
301 | |
302 | const union RepeatControl *repeat_ctrl = ctx->repeat_ctrl + i; |
303 | const char *repeat_state = ctx->repeat_state + info->stateOffset; |
304 | u64a last_top = repeatLastTop(repeat, repeat_ctrl, repeat_state); |
305 | assert(repeat->repeatMax < REPEAT_INF); |
306 | DEBUG_PRINTF("offset %llu, last_top %llu repeatMax %u\n" , offset, |
307 | last_top, repeat->repeatMax); |
308 | u64a adj = 0; |
309 | /* if the cycle's tugs are active at repeat max, it is still alive */ |
310 | if (TESTBIT_STATE(LOAD_FROM_ENG(&limex->accept), cyclicState) || |
311 | TESTBIT_STATE(LOAD_FROM_ENG(&limex->acceptAtEOD), cyclicState)) { |
312 | DEBUG_PRINTF("lazy tug possible - may still be inspected\n" ); |
313 | adj = 1; |
314 | } else { |
315 | const ENG_STATE_T *tug_mask = |
316 | (const ENG_STATE_T *)((const char *)info + info->tugMaskOffset); |
317 | if (ISNONZERO_STATE(AND_STATE(ctx->s, LOAD_FROM_ENG(tug_mask)))) { |
318 | DEBUG_PRINTF("tug possible - may still be inspected\n" ); |
319 | adj = 1; |
320 | } |
321 | } |
322 | |
323 | if (offset >= last_top + repeat->repeatMax + adj) { |
324 | DEBUG_PRINTF("repeat state is stale, squashing state %u\n" , |
325 | cyclicState); |
326 | CLEARBIT_STATE(&ctx->s, cyclicState); |
327 | } |
328 | } |
329 | } |
330 | |
331 | // Specialised inAccept call: LimEx NFAs with the "lazy tug" optimisation (see |
332 | // UE-1636) need to guard cyclic tug-accepts as well. |
333 | static really_inline |
334 | char LIMEX_INACCEPT_FN(const IMPL_NFA_T *limex, STATE_T state, |
335 | union RepeatControl *repeat_ctrl, char *repeat_state, |
336 | u64a offset, ReportID report) { |
337 | assert(limex); |
338 | |
339 | const STATE_T accept_mask = LOAD_FROM_ENG(&limex->accept); |
340 | STATE_T accepts = AND_STATE(state, accept_mask); |
341 | |
342 | // Are we in an accept state? |
343 | if (ISZERO_STATE(accepts)) { |
344 | DEBUG_PRINTF("no accept states are on\n" ); |
345 | return 0; |
346 | } |
347 | |
348 | SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state, offset, &accepts); |
349 | |
350 | DEBUG_PRINTF("looking for report %u\n" , report); |
351 | |
352 | const struct NFAAccept *acceptTable = getAcceptTable(limex); |
353 | |
354 | CHUNK_T chunks[NUM_STATE_CHUNKS]; |
355 | memcpy(chunks, &accepts, sizeof(accepts)); |
356 | |
357 | CHUNK_T mask_chunks[NUM_STATE_CHUNKS]; |
358 | memcpy(mask_chunks, &accept_mask, sizeof(accept_mask)); |
359 | |
360 | u32 base_index = 0; // Cumulative sum of mask popcount up to current chunk. |
361 | for (u32 i = 0; i < NUM_STATE_CHUNKS; i++) { |
362 | CHUNK_T chunk = chunks[i]; |
363 | while (chunk != 0) { |
364 | u32 bit = FIND_AND_CLEAR_FN(&chunk); |
365 | u32 local_idx = RANK_IN_MASK_FN(mask_chunks[i], bit); |
366 | u32 idx = local_idx + base_index; |
367 | assert(idx < limex->acceptCount); |
368 | const struct NFAAccept *a = &acceptTable[idx]; |
369 | DEBUG_PRINTF("state %u is on, report list at %u\n" , |
370 | bit + i * (u32)sizeof(chunk) * 8, a->reports); |
371 | |
372 | if (limexAcceptHasReport((const char *)limex, a, report)) { |
373 | DEBUG_PRINTF("report %u is on\n" , report); |
374 | return 1; |
375 | } |
376 | } |
377 | base_index += POPCOUNT_FN(mask_chunks[i]); |
378 | } |
379 | |
380 | return 0; |
381 | } |
382 | |
383 | static really_inline |
384 | char LIMEX_INANYACCEPT_FN(const IMPL_NFA_T *limex, STATE_T state, |
385 | union RepeatControl *repeat_ctrl, char *repeat_state, |
386 | u64a offset) { |
387 | assert(limex); |
388 | |
389 | const STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept); |
390 | STATE_T accstate = AND_STATE(state, acceptMask); |
391 | |
392 | // Are we in an accept state? |
393 | if (ISZERO_STATE(accstate)) { |
394 | DEBUG_PRINTF("no accept states are on\n" ); |
395 | return 0; |
396 | } |
397 | |
398 | SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state, offset, &accstate); |
399 | |
400 | return ISNONZERO_STATE(accstate); |
401 | } |
402 | |
403 | #undef TESTEOD_FN |
404 | #undef REPORTCURRENT_FN |
405 | #undef EXPIRE_ESTATE_FN |
406 | #undef LIMEX_INACCEPT_FN |
407 | #undef LIMEX_INANYACCEPT_FN |
408 | #undef INITIAL_FN |
409 | #undef TOP_FN |
410 | #undef TOPN_FN |
411 | #undef CONTEXT_T |
412 | #undef IMPL_NFA_T |
413 | #undef ONES_STATE |
414 | #undef AND_STATE |
415 | #undef OR_STATE |
416 | #undef ANDNOT_STATE |
417 | #undef CLEARBIT_STATE |
418 | #undef TESTBIT_STATE |
419 | #undef ISNONZERO_STATE |
420 | #undef ISZERO_STATE |
421 | #undef PROCESS_ACCEPTS_IMPL_FN |
422 | #undef PROCESS_ACCEPTS_FN |
423 | #undef PROCESS_ACCEPTS_NOSQUASH_FN |
424 | #undef SQUASH_UNTUG_BR_FN |
425 | #undef GET_NFA_REPEAT_INFO_FN |
426 | |
427 | #undef CHUNK_T |
428 | #undef FIND_AND_CLEAR_FN |
429 | #undef POPCOUNT_FN |
430 | #undef RANK_IN_MASK_FN |
431 | #undef NUM_STATE_CHUNKS |
432 | |