1/*
2 * Copyright (c) 2015-2017, 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/**
30 * \file
31 * \brief SOM Slot Manager.
32 */
33
34#include "slot_manager.h"
35
36#include "slot_manager_internal.h"
37#include "ue2common.h"
38#include "nfagraph/ng_holder.h"
39#include "nfagraph/ng_is_equal.h"
40#include "nfagraph/ng_som_util.h"
41#include "nfagraph/ng_region.h"
42#include "util/charreach.h"
43#include "util/hash.h"
44#include "util/make_unique.h"
45#include "util/dump_charclass.h"
46#include "util/verify_types.h"
47
48#include <cassert>
49#include <deque>
50#include <utility>
51
52using namespace std;
53
54namespace ue2 {
55
56/** \brief Define this to disable the cache and have everyone get their own
57 * SOM slot. */
58//#define NO_SLOT_CACHING
59
60SlotCacheEntry::SlotCacheEntry(const NGHolder &prefix_in,
61 const CharReach &escapes_in, u32 parent_in,
62 bool is_reset_in, u32 slot_in)
63 : prefix(cloneHolder(prefix_in)), escapes(escapes_in),
64 parent_slot(parent_in), is_reset(is_reset_in), slot(slot_in) {}
65
66size_t SlotEntryHasher::operator()(const SlotCacheEntry &e) const {
67 assert(e.prefix);
68
69 size_t v = hash_all(hash_holder(*e.prefix), e.parent_slot,
70 e.is_reset, e.escapes);
71
72 DEBUG_PRINTF("%zu vertices, parent_slot=%u, escapes=%s, is_reset=%d "
73 "hashes to %zx\n", num_vertices(*e.prefix), e.parent_slot,
74 describeClass(e.escapes, 10, CC_OUT_TEXT).c_str(),
75 (int)e.is_reset, v);
76 return v;
77}
78
79bool SlotEntryEqual::operator()(const SlotCacheEntry &a,
80 const SlotCacheEntry &b) const {
81 assert(a.prefix);
82 assert(b.prefix);
83 return a.parent_slot == b.parent_slot
84 && a.is_reset == b.is_reset
85 && a.escapes == b.escapes
86 && is_equal(*a.prefix, *b.prefix);
87 // NOTE: slot not compared.
88}
89
90void SlotCache::insert(const NGHolder &prefix, const CharReach &escapes,
91 u32 parent_slot, bool is_reset, u32 slot) {
92 store.emplace(prefix, escapes, parent_slot, is_reset, slot);
93}
94
95const SlotCacheEntry *SlotCache::find(const NGHolder &prefix,
96 const CharReach &escapes, u32 parent_slot,
97 bool is_reset) {
98 SlotCacheEntry entry(prefix, escapes, parent_slot, is_reset,
99 0 /* unused for searching with SlotEntryEqual */);
100 CacheStore::const_iterator it = store.find(entry);
101 if (it != store.end()) {
102 return &(*it);
103 }
104 return nullptr;
105}
106
107SomSlotManager::SomSlotManager(u8 p)
108 : nextSomSlot(0), cache(ue2::make_unique<SlotCache>()), historyRequired(0),
109 precision(p) {}
110
111SomSlotManager::~SomSlotManager() { }
112
113u32 SomSlotManager::getSomSlot(const NGHolder &prefix,
114 const CharReach &escapes, bool is_reset,
115 u32 parent_slot) {
116 assert(parent_slot == NO_PARENT || parent_slot < nextSomSlot);
117
118 DEBUG_PRINTF("prefix with %zu vertices, parent_slot=%u\n",
119 num_vertices(prefix), parent_slot);
120 DEBUG_PRINTF("nextSomSlot=%u\n", nextSomSlot);
121
122#ifdef NO_SLOT_CACHING
123 return nextSomSlot++;
124#endif
125
126 const SlotCacheEntry *entry =
127 cache->find(prefix, escapes, parent_slot, is_reset);
128 if (entry) {
129 DEBUG_PRINTF("cache hit: slot %u\n", entry->slot);
130 return entry->slot;
131 }
132
133 DEBUG_PRINTF("cache miss: handing out new slot %u\n", nextSomSlot);
134 cache->insert(prefix, escapes, parent_slot, is_reset, nextSomSlot);
135 return nextSomSlot++;
136}
137
138u32 SomSlotManager::getInitialResetSomSlot(const NGHolder &prefix,
139 const NGHolder &g,
140 const unordered_map<NFAVertex, u32> &region_map,
141 u32 last_sent_region, bool *prefix_already_implemented) {
142 DEBUG_PRINTF("getting initial reset; last sent region %u\n",
143 last_sent_region);
144 assert(last_sent_region);
145 assert(!hasBigCycles(prefix));
146 *prefix_already_implemented = false;
147
148#ifdef NO_SLOT_CACHING
149 return nextSomSlot++;
150#endif
151
152 shared_ptr<const NGHolder> pp = cloneHolder(prefix);
153 assert(hash_holder(*pp) == hash_holder(prefix));
154
155 auto hs_it = cache->initial_prefixes.find(pp);
156 if (hs_it != cache->initial_prefixes.end()) {
157 DEBUG_PRINTF("pulling from cache\n");
158 pp = *hs_it;
159 } else {
160 DEBUG_PRINTF("storing in cache entry %zu, hash=%llu\n",
161 cache->initial_prefixes.size(), hash_holder(*pp));
162 cache->initial_prefixes.insert(pp);
163 }
164
165 // Clone a copy of g (and its region map) that we will be able to store
166 // later on.
167 shared_ptr<NGHolder> gg = make_shared<NGHolder>();
168 unordered_map<NFAVertex, NFAVertex> orig_to_copy;
169 cloneHolder(*gg, g, &orig_to_copy);
170 unordered_map<NFAVertex, u32> gg_region_map;
171 for (const auto &m : region_map) {
172 assert(contains(region_map, m.first));
173 gg_region_map.emplace(orig_to_copy.at(m.first), m.second);
174 }
175
176 u32 first_bad_region = ~0U;
177 UNUSED bool rv = sentClearsTail(g, region_map, *pp, last_sent_region,
178 &first_bad_region);
179 assert(!rv || first_bad_region == ~0U);
180
181 InitialResetInfo *ir = nullptr;
182
183 for (auto &reset : cache->initial_resets) {
184 /* is this prefix already in our list? */
185 auto has_prefix_func =
186 [&pp](const InitialResetEntry &e) { return e.sent == pp; };
187 bool already_seen_prefix =
188 find_if(reset.entries.begin(), reset.entries.end(),
189 has_prefix_func) != reset.entries.end();
190
191 for (auto &e : reset.entries) {
192 u32 temp = 0;
193 /* we don't need to test against sentinels which are identical to
194 * our current one as races don't matter and we know it clears
195 * sufficiently. */
196 if (e.sent != pp &&
197 !sentClearsTail(g, region_map, *e.sent, last_sent_region - 1,
198 &temp) &&
199 (temp < first_bad_region || first_bad_region == ~0U)) {
200 goto try_next;
201 }
202
203 /* if we have already seen the prefix it must be fine */
204 if (!already_seen_prefix &&
205 !sentClearsTail(*e.body, e.body_regions, prefix,
206 e.sent_region - 1, &temp) &&
207 (temp < e.first_bad_region || e.first_bad_region == ~0U)) {
208 goto try_next;
209 }
210 }
211 DEBUG_PRINTF("sharing\n");
212 if (already_seen_prefix) {
213 /* if we have already created this prefix using this som slot, we
214 * can avoid creating another copy of the prefix. */
215 *prefix_already_implemented = true;
216 }
217 ir = &reset;
218 goto found;
219 try_next:;
220 }
221
222 cache->initial_resets.emplace_back(nextSomSlot++);
223 ir = &cache->initial_resets.back();
224
225found:
226 ir->entries.emplace_back(pp, gg, gg_region_map, last_sent_region,
227 first_bad_region);
228 return ir->slot;
229}
230
231u32 SomSlotManager::getPrivateSomSlot(void) {
232 return nextSomSlot++;
233}
234
235void SomSlotManager::rollbackSomTo(u32 num) {
236 assert(nextSomSlot >= num);
237 nextSomSlot = num;
238}
239
240u32 SomSlotManager::numSomSlots() const {
241 return nextSomSlot;
242}
243
244u32 SomSlotManager::addRevNfa(bytecode_ptr<NFA> nfa, u32 maxWidth) {
245 u32 rv = verify_u32(rev_nfas.size());
246 rev_nfas.push_back(move(nfa));
247
248 // A rev nfa commits us to having enough history around to handle its
249 // max width.
250 historyRequired = max(historyRequired, maxWidth);
251
252 return rv;
253}
254
255} // namespace ue2
256