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 | #include "fdr_internal.h" |
30 | #include "fdr_compile_internal.h" |
31 | #include "fdr_confirm.h" |
32 | #include "ue2common.h" |
33 | #include "hs_internal.h" |
34 | #include "fdr_engine_description.h" |
35 | #include "teddy_internal.h" |
36 | #include "teddy_engine_description.h" |
37 | #include "util/make_unique.h" |
38 | |
39 | #include <cmath> |
40 | |
41 | using namespace std; |
42 | |
43 | namespace ue2 { |
44 | |
45 | TeddyEngineDescription::TeddyEngineDescription(const TeddyEngineDef &def) |
46 | : EngineDescription(def.id, targetByArchFeatures(def.cpu_features), |
47 | def.numBuckets), |
48 | numMasks(def.numMasks), packed(def.packed) {} |
49 | |
50 | u32 TeddyEngineDescription::getDefaultFloodSuffixLength() const { |
51 | return numMasks; |
52 | } |
53 | |
54 | void getTeddyDescriptions(vector<TeddyEngineDescription> *out) { |
55 | static const TeddyEngineDef defns[] = { |
56 | { 3, 0 | HS_CPU_FEATURES_AVX2, 1, 16, false }, |
57 | { 4, 0 | HS_CPU_FEATURES_AVX2, 1, 16, true }, |
58 | { 5, 0 | HS_CPU_FEATURES_AVX2, 2, 16, false }, |
59 | { 6, 0 | HS_CPU_FEATURES_AVX2, 2, 16, true }, |
60 | { 7, 0 | HS_CPU_FEATURES_AVX2, 3, 16, false }, |
61 | { 8, 0 | HS_CPU_FEATURES_AVX2, 3, 16, true }, |
62 | { 9, 0 | HS_CPU_FEATURES_AVX2, 4, 16, false }, |
63 | { 10, 0 | HS_CPU_FEATURES_AVX2, 4, 16, true }, |
64 | { 11, 0, 1, 8, false }, |
65 | { 12, 0, 1, 8, true }, |
66 | { 13, 0, 2, 8, false }, |
67 | { 14, 0, 2, 8, true }, |
68 | { 15, 0, 3, 8, false }, |
69 | { 16, 0, 3, 8, true }, |
70 | { 17, 0, 4, 8, false }, |
71 | { 18, 0, 4, 8, true }, |
72 | }; |
73 | out->clear(); |
74 | for (const auto &def : defns) { |
75 | out->emplace_back(def); |
76 | } |
77 | } |
78 | |
79 | static |
80 | size_t maxFloodTailLen(const vector<hwlmLiteral> &vl) { |
81 | size_t max_flood_tail = 0; |
82 | for (const auto &lit : vl) { |
83 | const string &s = lit.s; |
84 | assert(!s.empty()); |
85 | size_t j; |
86 | for (j = 1; j < s.length(); j++) { |
87 | if (s[s.length() - j - 1] != s[s.length() - 1]) { |
88 | break; |
89 | } |
90 | } |
91 | max_flood_tail = max(max_flood_tail, j); |
92 | } |
93 | return max_flood_tail; |
94 | } |
95 | |
96 | /** |
97 | * \brief True if this Teddy engine is qualified to handle this set of literals |
98 | * on this target. |
99 | */ |
100 | static |
101 | bool isAllowed(const vector<hwlmLiteral> &vl, const TeddyEngineDescription &eng, |
102 | const size_t max_lit_len, const target_t &target) { |
103 | if (!eng.isValidOnTarget(target)) { |
104 | DEBUG_PRINTF("%u disallowed: not valid on target\n" , eng.getID()); |
105 | return false; |
106 | } |
107 | if (eng.getNumBuckets() < vl.size() && !eng.packed) { |
108 | DEBUG_PRINTF("%u disallowed: num buckets < num lits and not packed\n" , |
109 | eng.getID()); |
110 | return false; |
111 | } |
112 | if (eng.getNumBuckets() * TEDDY_BUCKET_LOAD < vl.size()) { |
113 | DEBUG_PRINTF("%u disallowed: too many lits for num buckets\n" , |
114 | eng.getID()); |
115 | return false; |
116 | } |
117 | if (eng.numMasks > max_lit_len) { |
118 | DEBUG_PRINTF("%u disallowed: more masks than max lit len (%zu)\n" , |
119 | eng.getID(), max_lit_len); |
120 | return false; |
121 | } |
122 | |
123 | if (vl.size() > 40) { |
124 | u32 n_small_lits = 0; |
125 | for (const auto &lit : vl) { |
126 | if (lit.s.length() < eng.numMasks) { |
127 | n_small_lits++; |
128 | } |
129 | } |
130 | if (n_small_lits * 5 > vl.size()) { |
131 | DEBUG_PRINTF("too many short literals (%u)\n" , n_small_lits); |
132 | return false; |
133 | } |
134 | } |
135 | |
136 | return true; |
137 | } |
138 | |
139 | unique_ptr<TeddyEngineDescription> |
140 | chooseTeddyEngine(const target_t &target, const vector<hwlmLiteral> &vl) { |
141 | vector<TeddyEngineDescription> descs; |
142 | getTeddyDescriptions(&descs); |
143 | const TeddyEngineDescription *best = nullptr; |
144 | |
145 | const size_t max_lit_len = maxLen(vl); |
146 | const size_t max_flood_tail = maxFloodTailLen(vl); |
147 | DEBUG_PRINTF("%zu lits, max_lit_len=%zu, max_flood_tail=%zu\n" , vl.size(), |
148 | max_lit_len, max_flood_tail); |
149 | |
150 | u32 best_score = 0; |
151 | for (size_t engineID = 0; engineID < descs.size(); engineID++) { |
152 | const TeddyEngineDescription &eng = descs[engineID]; |
153 | if (!isAllowed(vl, eng, max_lit_len, target)) { |
154 | continue; |
155 | } |
156 | |
157 | u32 score = 0; |
158 | |
159 | // We prefer unpacked Teddy models. |
160 | if (!eng.packed) { |
161 | score += 100; |
162 | } |
163 | |
164 | // If we're heavily loaded, we prefer to have more masks. |
165 | if (vl.size() > 4 * eng.getNumBuckets()) { |
166 | score += eng.numMasks * 4; |
167 | } else { |
168 | // Lightly loaded cases are great. |
169 | score += 100; |
170 | } |
171 | |
172 | // We want enough masks to avoid becoming flood-prone. |
173 | if (eng.numMasks > max_flood_tail) { |
174 | score += 50; |
175 | } |
176 | |
177 | // We prefer having 3 masks. 3 is just right. |
178 | score += 6 / (abs(3 - (int)eng.numMasks) + 1); |
179 | |
180 | // We prefer cheaper, smaller Teddy models. |
181 | score += 16 / eng.getNumBuckets(); |
182 | |
183 | DEBUG_PRINTF("teddy %u: masks=%u, buckets=%u, packed=%u " |
184 | "-> score=%u\n" , |
185 | eng.getID(), eng.numMasks, eng.getNumBuckets(), |
186 | eng.packed ? 1U : 0U, score); |
187 | |
188 | if (!best || score > best_score) { |
189 | best = ŋ |
190 | best_score = score; |
191 | } |
192 | } |
193 | |
194 | if (!best) { |
195 | DEBUG_PRINTF("failed to find engine\n" ); |
196 | return nullptr; |
197 | } |
198 | |
199 | DEBUG_PRINTF("using engine %u\n" , best->getID()); |
200 | return ue2::make_unique<TeddyEngineDescription>(*best); |
201 | } |
202 | |
203 | unique_ptr<TeddyEngineDescription> getTeddyDescription(u32 engineID) { |
204 | vector<TeddyEngineDescription> descs; |
205 | getTeddyDescriptions(&descs); |
206 | |
207 | for (const auto &desc : descs) { |
208 | if (desc.getID() == engineID) { |
209 | return ue2::make_unique<TeddyEngineDescription>(desc); |
210 | } |
211 | } |
212 | |
213 | return nullptr; |
214 | } |
215 | |
216 | } // namespace ue2 |
217 | |