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
41using namespace std;
42
43namespace ue2 {
44
45TeddyEngineDescription::TeddyEngineDescription(const TeddyEngineDef &def)
46 : EngineDescription(def.id, targetByArchFeatures(def.cpu_features),
47 def.numBuckets),
48 numMasks(def.numMasks), packed(def.packed) {}
49
50u32 TeddyEngineDescription::getDefaultFloodSuffixLength() const {
51 return numMasks;
52}
53
54void 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
79static
80size_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 */
100static
101bool 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
139unique_ptr<TeddyEngineDescription>
140chooseTeddyEngine(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 = &eng;
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
203unique_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