1 /*
2 * Copyright (C) 2014-2021 Canonical, Ltd.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 *
18 * This code is a complete clean re-write of the stress tool by
19 * Colin Ian King <colin.king@canonical.com> and attempts to be
20 * backwardly compatible with the stress tool by Amos Waterland
21 * <apw@rossby.metr.ou.edu> but has more stress tests and more
22 * functionality.
23 *
24 */
25 #include "stress-ng.h"
26
27 /*
28 * stress_hash_jenkin()
29 * Jenkin's hash on random data
30 * http://www.burtleburtle.net/bob/hash/doobs.html
31 */
stress_hash_jenkin(const uint8_t * data,const size_t len)32 uint32_t HOT OPTIMIZE3 stress_hash_jenkin(const uint8_t *data, const size_t len)
33 {
34 register size_t i;
35 register uint32_t h = 0;
36
37 for (i = 0; i < len; i++) {
38 h += *data++;
39 h += h << 10;
40 h ^= h >> 6;
41 }
42 h += h << 3;
43 h ^= h >> 11;
44 h += h << 15;
45
46 return h;
47 }
48
49 /*
50 * stress_hash_pjw()
51 * Hash a string, from Aho, Sethi, Ullman, Compiling Techniques.
52 */
stress_hash_pjw(const char * str)53 uint32_t HOT OPTIMIZE3 stress_hash_pjw(const char *str)
54 {
55 register uint32_t h = 0;
56
57 while (*str) {
58 register uint32_t g;
59
60 h = (h << 4) + (uint32_t)(*str);
61 if (0 != (g = h & 0xf0000000)) {
62 h = h ^ (g >> 24);
63 h = h ^ g;
64 }
65 str++;
66 }
67 return h;
68 }
69
70 /*
71 * stress_hash_djb2a()
72 * Hash a string, from Dan Bernstein comp.lang.c (xor version)
73 */
stress_hash_djb2a(const char * str)74 uint32_t HOT OPTIMIZE3 stress_hash_djb2a(const char *str)
75 {
76 register uint32_t hash = 5381;
77 register int c;
78
79 while ((c = *str++)) {
80 /* (hash * 33) ^ c */
81 hash = ((hash << 5) + hash) ^ (uint32_t)c;
82 }
83 return hash;
84 }
85
86 /*
87 * stress_hash_fnv1a()
88 * Hash a string, using the improved 32 bit FNV-1a hash
89 */
stress_hash_fnv1a(const char * str)90 uint32_t HOT OPTIMIZE3 stress_hash_fnv1a(const char *str)
91 {
92 register uint32_t hash = 5381;
93 const uint32_t fnv_prime = 16777619; /* 2^24 + 2^9 + 0x93 */
94 register int c;
95
96 while ((c = *str++)) {
97 hash ^= (uint32_t)c;
98 hash *= fnv_prime;
99 }
100 return hash;
101 }
102
103 /*
104 * stress_hash_sdbm()
105 * Hash a string, using the sdbm data base hash and also
106 * apparently used in GNU awk.
107 */
stress_hash_sdbm(const char * str)108 uint32_t HOT OPTIMIZE3 stress_hash_sdbm(const char *str)
109 {
110 register uint32_t hash = 0;
111 register int c;
112
113 while ((c = *str++))
114 hash = (uint32_t)c + (hash << 6) + (hash << 16) - hash;
115 return hash;
116 }
117
118 /*
119 * stress_hash_nhash()
120 * Hash a string using a C implementation of the Exim nhash
121 * algorithm.
122 */
stress_hash_nhash(const char * str)123 uint32_t HOT OPTIMIZE3 stress_hash_nhash(const char *str)
124 {
125 static const uint32_t primes[] = {
126 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
127 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
128 79, 83, 89, 97, 101, 103, 107, 109, 113
129 };
130 const int n = SIZEOF_ARRAY(primes);
131 register int i = 0;
132 register uint32_t sum = 0;
133
134 while (*str) {
135 i += (n - 1);
136 if (i >= n)
137 i -= n;
138
139 sum += primes[i] * (uint32_t)*(str++);
140 }
141 return sum;
142 }
143
144
145 /*
146 * stress_hash_murmur_32_scramble
147 * helper to scramble bits
148 */
stress_hash_murmur_32_scramble(uint32_t k)149 static inline uint32_t HOT OPTIMIZE3 stress_hash_murmur_32_scramble(uint32_t k)
150 {
151 k *= 0xcc9e2d51;
152 k = (k << 15) | (k >> 17);
153 k *= 0x1b873593;
154 return k;
155 }
156
157 /*
158 * stress_hash_murmur3_32
159 * 32 bit murmur3 hash based on Austin Appleby's
160 * Murmur3 hash, code derived from example code in
161 * https://en.wikipedia.org/wiki/MurmurHash
162 */
stress_hash_murmur3_32(const uint8_t * key,size_t len,uint32_t seed)163 uint32_t HOT OPTIMIZE3 stress_hash_murmur3_32(
164 const uint8_t* key,
165 size_t len,
166 uint32_t seed)
167 {
168 uint32_t h = seed;
169 uint32_t k;
170 register size_t i;
171
172 for (i = len >> 2; i; i--) {
173 (void)memcpy(&k, key, sizeof(k));
174 key += sizeof(k);
175 h ^= stress_hash_murmur_32_scramble(k);
176 h = (h << 13) | (h >> 19);
177 h = h * 5 + 0xe6546b64;
178 }
179
180 k = 0;
181 for (i = len & 3; i; i--) {
182 k <<= 8;
183 k |= key[i - 1];
184 }
185 h ^= stress_hash_murmur_32_scramble(k);
186 h ^= len;
187 h ^= h >> 16;
188 h *= 0x85ebca6b;
189 h ^= h >> 13;
190 h *= 0xc2b2ae35;
191 h ^= h >> 16;
192
193 return h;
194 }
195
196 /*
197 * stress_hash_create()
198 * create a hash table with size of n base hash entries
199 */
stress_hash_create(const size_t n)200 stress_hash_table_t *stress_hash_create(const size_t n)
201 {
202 stress_hash_table_t *hash_table;
203
204 if (n == 0)
205 return NULL;
206
207 hash_table = calloc(1, sizeof(*hash_table));
208 if (!hash_table)
209 return NULL;
210
211 hash_table->table = calloc(n, sizeof(*(hash_table->table)));
212 if (!hash_table->table) {
213 free(hash_table);
214 return NULL;
215 }
216 hash_table->n = n;
217
218 return hash_table;
219 }
220
221 #define HASH_STR(hash) (((char *)hash) + sizeof(*hash))
222
stress_hash_find(stress_hash_t * hash,const char * str)223 static inline stress_hash_t *stress_hash_find(stress_hash_t *hash, const char *str)
224 {
225 while (hash) {
226 if (!strcmp(str, HASH_STR(hash)))
227 return hash;
228 hash = hash->next;
229 }
230 return NULL;
231 }
232
233 /*
234 * stress_hash_get()
235 * get a hash entry based on the given string. returns NULL if it does
236 * not exist
237 */
stress_hash_get(stress_hash_table_t * hash_table,const char * str)238 stress_hash_t *stress_hash_get(stress_hash_table_t *hash_table, const char *str)
239 {
240 uint32_t h;
241
242 if (UNLIKELY(!hash_table))
243 return NULL;
244 if (UNLIKELY(!str))
245 return NULL;
246
247 h = stress_hash_sdbm(str) % hash_table->n;
248 return stress_hash_find(hash_table->table[h], str);
249 }
250
251 /*
252 * stress_hash_add()
253 * add a hash entry based on the given string. If the string already is
254 * hashed it is not re-added. Returns null if an error occurs (e.g. out of
255 * memory).
256 */
stress_hash_add(stress_hash_table_t * hash_table,const char * str)257 stress_hash_t *stress_hash_add(stress_hash_table_t *hash_table, const char *str)
258 {
259 stress_hash_t *hash;
260 uint32_t h;
261 size_t len;
262
263 if (UNLIKELY(!hash_table))
264 return NULL;
265 if (UNLIKELY(!str))
266 return NULL;
267
268 h = stress_hash_sdbm(str) % hash_table->n;
269 hash = stress_hash_find(hash_table->table[h], str);
270 if (hash)
271 return hash;
272
273 /* Not found, so add a new hash */
274 len = strlen(str) + 1;
275 hash = malloc(sizeof(*hash) + len);
276 if (UNLIKELY(!hash))
277 return NULL; /* cppcheck-suppress memleak */
278
279 hash->next = hash_table->table[h];
280 hash_table->table[h] = hash;
281 (void)memcpy(HASH_STR(hash), str, len);
282
283 return hash;
284 }
285
286 /*
287 * stress_hash_delete()
288 * delete a hash table and all entries in the table
289 */
stress_hash_delete(stress_hash_table_t * hash_table)290 void stress_hash_delete(stress_hash_table_t *hash_table)
291 {
292 size_t i;
293
294 if (!hash_table)
295 return;
296
297 for (i = 0; i < hash_table->n; i++) {
298 stress_hash_t *hash = hash_table->table[i];
299
300 while (hash) {
301 stress_hash_t *next = hash->next;
302
303 free(hash);
304 hash = next;
305 }
306 }
307 free(hash_table->table);
308 free(hash_table);
309 }
310