1 | /* |
2 | * Copyright (c) 2015-2018, 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 | /** \file |
30 | * \brief ReportManager: tracks Report structures, exhaustion and dedupe keys. |
31 | */ |
32 | |
33 | #include "report_manager.h" |
34 | |
35 | #include "grey.h" |
36 | #include "ue2common.h" |
37 | #include "compiler/compiler.h" |
38 | #include "nfagraph/ng.h" |
39 | #include "rose/rose_build.h" |
40 | #include "util/compile_error.h" |
41 | #include "util/container.h" |
42 | |
43 | #include <deque> |
44 | #include <map> |
45 | #include <sstream> |
46 | #include <vector> |
47 | |
48 | using namespace std; |
49 | |
50 | namespace ue2 { |
51 | |
52 | ReportManager::ReportManager(const Grey &g) |
53 | : grey(g), freeEIndex(0), global_exhaust(true) {} |
54 | |
55 | u32 ReportManager::getInternalId(const Report &ir) { |
56 | auto it = reportIdToInternalMap.find(ir); |
57 | if (it != reportIdToInternalMap.end()) { |
58 | DEBUG_PRINTF("existing report %zu\n" , it->second); |
59 | return it->second; |
60 | } |
61 | |
62 | // Construct a new internal report and assign it a ReportID. |
63 | |
64 | if (numReports() >= grey.limitReportCount) { |
65 | throw ResourceLimitError(); |
66 | } |
67 | |
68 | u32 size = reportIds.size(); |
69 | reportIds.push_back(ir); |
70 | reportIdToInternalMap.emplace(ir, size); |
71 | DEBUG_PRINTF("new report %u\n" , size); |
72 | return size; |
73 | } |
74 | |
75 | const Report &ReportManager::getReport(u32 id) const { |
76 | assert(id < reportIds.size()); |
77 | return reportIds.at(id); |
78 | } |
79 | |
80 | size_t ReportManager::numReports() const { |
81 | return reportIds.size(); |
82 | } |
83 | |
84 | u32 ReportManager::getExhaustibleKey(u32 a) { |
85 | auto it = toExhaustibleKeyMap.find(a); |
86 | if (it == toExhaustibleKeyMap.end()) { |
87 | // get size before assigning to avoid wacky LHS shenanigans |
88 | u32 size = toExhaustibleKeyMap.size(); |
89 | bool inserted; |
90 | tie(it, inserted) = toExhaustibleKeyMap.emplace(s64a{a}, size); |
91 | assert(inserted); |
92 | } |
93 | |
94 | DEBUG_PRINTF("%lld -> ekey %u\n" , it->first, it->second); |
95 | return it->second; |
96 | } |
97 | |
98 | const set<u32> &ReportManager::getRelateCKeys(u32 lkey) { |
99 | auto it = pl.lkey2ckeys.find(lkey); |
100 | assert(it != pl.lkey2ckeys.end()); |
101 | return it->second; |
102 | } |
103 | |
104 | void ReportManager::logicalKeyRenumber() { |
105 | pl.logicalKeyRenumber(); |
106 | // assign to corresponding report |
107 | for (u32 i = 0; i < reportIds.size(); i++) { |
108 | Report &ir = reportIds[i]; |
109 | if (contains(pl.toLogicalKeyMap, ir.onmatch)) { |
110 | ir.lkey = pl.toLogicalKeyMap.at(ir.onmatch); |
111 | } |
112 | } |
113 | } |
114 | |
115 | const vector<LogicalOp> &ReportManager::getLogicalTree() const { |
116 | return pl.logicalTree; |
117 | } |
118 | |
119 | const vector<CombInfo> &ReportManager::getCombInfoMap() const { |
120 | return pl.combInfoMap; |
121 | } |
122 | |
123 | u32 ReportManager::getUnassociatedExhaustibleKey(void) { |
124 | u32 rv = toExhaustibleKeyMap.size(); |
125 | bool inserted; |
126 | map<s64a, u32>::const_iterator it; |
127 | tie(it, inserted) = toExhaustibleKeyMap.emplace(--freeEIndex, rv); |
128 | assert(inserted); |
129 | assert(it->second == rv); |
130 | |
131 | return rv; |
132 | } |
133 | |
134 | u32 ReportManager::numDkeys() const { |
135 | DEBUG_PRINTF("%zu dkeys\n" , reportIdToDedupeKey.size()); |
136 | return reportIdToDedupeKey.size(); |
137 | } |
138 | |
139 | u32 ReportManager::numEkeys() const { |
140 | return (u32) toExhaustibleKeyMap.size(); |
141 | } |
142 | |
143 | u32 ReportManager::numLogicalKeys() const { |
144 | return (u32) pl.toLogicalKeyMap.size(); |
145 | } |
146 | |
147 | u32 ReportManager::numLogicalOps() const { |
148 | return (u32) pl.logicalTree.size(); |
149 | } |
150 | |
151 | u32 ReportManager::numCkeys() const { |
152 | return (u32) pl.toCombKeyMap.size(); |
153 | } |
154 | |
155 | bool ReportManager::patternSetCanExhaust() const { |
156 | return global_exhaust && !toExhaustibleKeyMap.empty(); |
157 | } |
158 | |
159 | vector<ReportID> ReportManager::getDkeyToReportTable() const { |
160 | vector<ReportID> rv(reportIdToDedupeKey.size()); |
161 | |
162 | for (const auto &m : reportIdToDedupeKey) { |
163 | assert(m.second < rv.size()); |
164 | rv[m.second] = m.first; |
165 | } |
166 | |
167 | return rv; |
168 | } |
169 | |
170 | void ReportManager::assignDkeys(const RoseBuild *rose) { |
171 | DEBUG_PRINTF("assigning...\n" ); |
172 | |
173 | map<u32, flat_set<ReportID>> ext_to_int; |
174 | |
175 | for (u32 i = 0; i < reportIds.size(); i++) { |
176 | const Report &ir = reportIds[i]; |
177 | |
178 | /* need to populate dkey */ |
179 | if (isExternalReport(ir)) { |
180 | ext_to_int[ir.onmatch].insert(i); |
181 | } |
182 | } |
183 | |
184 | auto dedupe = rose->generateDedupeAux(); |
185 | |
186 | for (const auto &m : ext_to_int) { |
187 | u32 ext = m.first; |
188 | |
189 | if (!dedupe->requiresDedupeSupport(m.second)) { |
190 | DEBUG_PRINTF("%u does not require dedupe\n" , ext); |
191 | continue; /* no dedupe required for this set */ |
192 | } |
193 | |
194 | u32 dkey = reportIdToDedupeKey.size(); |
195 | reportIdToDedupeKey[ext] = dkey; |
196 | DEBUG_PRINTF("ext=%u -> dkey=%u\n" , ext, dkey); |
197 | } |
198 | } |
199 | |
200 | u32 ReportManager::getDkey(const Report &r) const { |
201 | if (!isExternalReport(r)) { |
202 | return ~u32{0}; |
203 | } |
204 | |
205 | auto it = reportIdToDedupeKey.find(r.onmatch); |
206 | if (it == reportIdToDedupeKey.end()) { |
207 | return ~u32{0}; |
208 | } |
209 | return it->second; |
210 | } |
211 | |
212 | void ReportManager::registerExtReport(ReportID id, |
213 | const external_report_info &ext) { |
214 | auto it = externalIdMap.find(id); |
215 | if (it != externalIdMap.end()) { |
216 | const external_report_info &eri = it->second; |
217 | if (eri.highlander != ext.highlander) { |
218 | /* we have a problem */ |
219 | ostringstream out; |
220 | out << "Expression (index " << ext.first_pattern_index |
221 | << ") with match ID " << id << " " ; |
222 | if (!ext.highlander) { |
223 | out << "did not specify " ; |
224 | } else { |
225 | out << "specified " ; |
226 | } |
227 | out << "HS_FLAG_SINGLEMATCH whereas previous expression (index " |
228 | << eri.first_pattern_index << ") with the same match ID did" ; |
229 | if (ext.highlander) { |
230 | out << " not" ; |
231 | } |
232 | out << "." ; |
233 | throw CompileError(ext.first_pattern_index, out.str()); |
234 | } |
235 | } else { |
236 | externalIdMap.emplace(id, ext); |
237 | } |
238 | |
239 | // Any non-highlander pattern will render us not globally exhaustible. |
240 | if (!ext.highlander) { |
241 | global_exhaust = false; |
242 | } |
243 | } |
244 | |
245 | Report ReportManager::getBasicInternalReport(const ExpressionInfo &expr, |
246 | s32 adj) { |
247 | /* validate that we are not violating highlander constraints, this will |
248 | * throw a CompileError if so. */ |
249 | registerExtReport(expr.report, |
250 | external_report_info(expr.highlander, expr.index)); |
251 | |
252 | /* create the internal report */ |
253 | u32 ekey = INVALID_EKEY; |
254 | if (expr.highlander) { |
255 | /* all patterns with the same report id share an ekey */ |
256 | ekey = getExhaustibleKey(expr.report); |
257 | } |
258 | |
259 | return makeECallback(expr.report, adj, ekey, expr.quiet); |
260 | } |
261 | |
262 | void ReportManager::setProgramOffset(ReportID id, u32 programOffset) { |
263 | assert(id < reportIds.size()); |
264 | assert(!contains(reportIdToProgramOffset, id)); |
265 | reportIdToProgramOffset.emplace(id, programOffset); |
266 | } |
267 | |
268 | u32 ReportManager::getProgramOffset(ReportID id) const { |
269 | assert(id < reportIds.size()); |
270 | assert(contains(reportIdToProgramOffset, id)); |
271 | return reportIdToProgramOffset.at(id); |
272 | } |
273 | |
274 | static |
275 | void ekeysUnion(std::set<u32> *ekeys, u32 more) { |
276 | if (!ekeys->empty()) { |
277 | if (more == INVALID_EKEY) { |
278 | ekeys->clear(); |
279 | } else { |
280 | ekeys->insert(more); |
281 | } |
282 | } |
283 | } |
284 | |
285 | set<u32> reportsToEkeys(const set<ReportID> &reports, const ReportManager &rm) { |
286 | assert(!reports.empty()); |
287 | |
288 | set<u32> ekeys; |
289 | |
290 | for (auto it = reports.begin(), ite = reports.end(); it != ite; ++it) { |
291 | u32 e = rm.getReport(*it).ekey; |
292 | if (it == reports.begin()) { |
293 | if (e != INVALID_EKEY) { |
294 | ekeys.insert(e); |
295 | } |
296 | } else { |
297 | ekeysUnion(&ekeys, e); |
298 | } |
299 | } |
300 | |
301 | return ekeys; |
302 | } |
303 | |
304 | } // namespace ue2 |
305 | |