Line data Source code
1 : /*
2 : * Copyright (C) 2011 Andrea Mazzoleni
3 : *
4 : * This program is free software: you can redistribute it and/or modify
5 : * it under the terms of the GNU General Public License as published by
6 : * the Free Software Foundation, either version 3 of the License, or
7 : * (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, see <http://www.gnu.org/licenses/>.
16 : */
17 :
18 : #include "portable.h"
19 :
20 : #include "snapraid.h"
21 : #include "util.h"
22 : #include "raid/raid.h"
23 : #include "raid/cpu.h"
24 : #include "raid/combo.h"
25 : #include "raid/internal.h"
26 : #include "raid/test.h"
27 : #include "elem.h"
28 : #include "state.h"
29 : #include "support.h"
30 : #include "tommyds/tommyhash.h"
31 : #include "tommyds/tommyarray.h"
32 : #include "tommyds/tommyarrayblkof.h"
33 : #include "tommyds/tommyhashdyn.h"
34 :
35 : struct hash32_test_vector {
36 : const char* data;
37 : int len;
38 : uint32_t digest;
39 : uint32_t seed;
40 : };
41 :
42 : struct strhash32_test_vector {
43 : char* data;
44 : uint32_t digest;
45 : uint32_t seed;
46 : };
47 :
48 : struct hash64_test_vector {
49 : const char* data;
50 : int len;
51 : uint64_t digest;
52 : uint64_t seed;
53 : };
54 :
55 : struct hash_test_vector {
56 : const char* data;
57 : int len;
58 : unsigned char digest[HASH_MAX];
59 : unsigned char seed[HASH_MAX];
60 : };
61 :
62 : /**
63 : * Test vectors for tommy_hash32
64 : */
65 : static struct hash32_test_vector TEST_HASH32[] = {
66 : { "", 0, 0x8614384c, 0xa766795d },
67 : { "a", 1, 0x12c16c36, 0xa766795d },
68 : { "abc", 3, 0xc58e8af5, 0xa766795d },
69 : { "message digest", 14, 0x006b32f1, 0xa766795d },
70 : { "abcdefghijklmnopqrstuvwxyz", 26, 0x7e6fcfe0, 0xa766795d },
71 : { "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", 62, 0x8604adf8, 0xa766795d },
72 : { "The quick brown fox jumps over the lazy dog", 43, 0xdeba3d3a, 0xa766795d },
73 : { "\x00", 1, 0x4a7d1c33, 0xa766795d },
74 : { "\x16\x27", 2, 0x8b50899b, 0xa766795d },
75 : { "\xe2\x56\xb4", 3, 0x60406493, 0xa766795d },
76 : { "\xc9\x4d\x9c\xda", 4, 0xa049144a, 0xa766795d },
77 : { "\x79\xf1\x29\x69\x5d", 5, 0x4da2c2f1, 0xa766795d },
78 : { "\x00\x7e\xdf\x1e\x31\x1c", 6, 0x59de30cf, 0xa766795d },
79 : { "\x2a\x4c\xe1\xff\x9e\x6f\x53", 7, 0x219e149c, 0xa766795d },
80 : { "\xba\x02\xab\x18\x30\xc5\x0e\x8a", 8, 0x25067520, 0xa766795d },
81 : { "\xec\x4e\x7a\x72\x1e\x71\x2a\xc9\x33", 9, 0xa1f368d8, 0xa766795d },
82 : { "\xfd\xe2\x9c\x0f\x72\xb7\x08\xea\xd0\x78", 10, 0x805fc63d, 0xa766795d },
83 : { "\x65\xc4\x8a\xb8\x80\x86\x9a\x79\x00\xb7\xae", 11, 0x7f75dd0f, 0xa766795d },
84 : { "\x77\xe9\xd7\x80\x0e\x3f\x5c\x43\xc8\xc2\x46\x39", 12, 0xb9154382, 0xa766795d },
85 : { 0, 0, 0, 0 }
86 : };
87 :
88 : /**
89 : * Test vectors for tommy_strhash32
90 : */
91 : struct strhash32_test_vector TEST_STRHASH32[] = {
92 : { "", 0x0af1416d, 0xa766795d },
93 : { "a", 0x68fa0f3f, 0xa766795d },
94 : { "abc", 0xfc68ffc5, 0xa766795d },
95 : { "message digest", 0x08477b63, 0xa766795d },
96 : { "abcdefghijklmnopqrstuvwxyz", 0x5b9c25e5, 0xa766795d },
97 : { "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", 0x1e530ce7, 0xa766795d },
98 : { "The quick brown fox jumps over the lazy dog", 0xaf93eefe, 0xa766795d },
99 : { "\xff", 0xfc88801b, 0xa766795d },
100 : { "\x16\x27", 0xcd7216db, 0xa766795d },
101 : { "\xe2\x56\xb4", 0x05f98d02, 0xa766795d },
102 : { "\xc9\x4d\x9c\xda", 0xf65206f8, 0xa766795d },
103 : { "\x79\xf1\x29\x69\x5d", 0x72bd6bda, 0xa766795d },
104 : { "\xff\x7e\xdf\x1e\x31\x1c", 0x57dfb9b4, 0xa766795d },
105 : { "\x2a\x4c\xe1\xff\x9e\x6f\x53", 0x499ff634, 0xa766795d },
106 : { "\xba\x02\xab\x18\x30\xc5\x0e\x8a", 0xe896b7ce, 0xa766795d },
107 : { "\xec\x4e\x7a\x72\x1e\x71\x2a\xc9\x33", 0xfe3939f0, 0xa766795d },
108 : { "\xfd\xe2\x9c\x0f\x72\xb7\x08\xea\xd0\x78", 0x4351d482, 0xa766795d },
109 : { "\x65\xc4\x8a\xb8\x80\x86\x9a\x79\xff\xb7\xae", 0x88e92135, 0xa766795d },
110 : { "\x77\xe9\xd7\x80\x0e\x3f\x5c\x43\xc8\xc2\x46\x39", 0x01109c16, 0xa766795d },
111 : { "\x87\xd8\x61\x61\x4c\x89\x17\x4e\xa1\xa4\xef\x13\xa9", 0xbcb050dc, 0xa766795d },
112 : { "\xfe\xa6\x5b\xc2\xda\xe8\x95\xd4\x64\xab\x4c\x39\x58\x29", 0xbe5e1fd5, 0xa766795d },
113 : { "\x94\x49\xc0\x78\xa0\x80\xda\xc7\x71\x4e\x17\x37\xa9\x7c\x40", 0x70d8c97f, 0xa766795d },
114 : { "\x53\x7e\x36\xb4\x2e\xc9\xb9\xcc\x18\x3e\x9a\x5f\xfc\xb7\xb0\x61", 0x957440a9, 0xa766795d },
115 : { 0, 0, 0 }
116 : };
117 :
118 : /**
119 : * Test vectors for tommy_hash64
120 : */
121 : static struct hash64_test_vector TEST_HASH64[] = {
122 : { "", 0, 0x8614384cb5165fbfULL, 0x2f022773a766795dULL },
123 : { "a", 1, 0x1a2e0298a8e94a3dULL, 0x2f022773a766795dULL },
124 : { "abc", 3, 0x7555796b7a7d21ebULL, 0x2f022773a766795dULL },
125 : { "message digest", 14, 0x9411a57d04b92fb4ULL, 0x2f022773a766795dULL },
126 : { "abcdefghijklmnopqrstuvwxyz", 26, 0x3ca3f8d2b4e69832ULL, 0x2f022773a766795dULL },
127 : { "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", 62, 0x6dae542ba0015a4dULL, 0x2f022773a766795dULL },
128 : { "The quick brown fox jumps over the lazy dog", 43, 0xe06d8cbb3d2ea1a6ULL, 0x2f022773a766795dULL },
129 : { "\x00", 1, 0x201e664fb5f2c021ULL, 0x2f022773a766795dULL },
130 : { "\x16\x27", 2, 0xef42fa8032c4b775ULL, 0x2f022773a766795dULL },
131 : { "\xe2\x56\xb4", 3, 0x6e6c498a6688466cULL, 0x2f022773a766795dULL },
132 : { "\xc9\x4d\x9c\xda", 4, 0x5195005419905423ULL, 0x2f022773a766795dULL },
133 : { "\x79\xf1\x29\x69\x5d", 5, 0x221235b48afee7c1ULL, 0x2f022773a766795dULL },
134 : { "\x00\x7e\xdf\x1e\x31\x1c", 6, 0x1b1f18b9266f095bULL, 0x2f022773a766795dULL },
135 : { "\x2a\x4c\xe1\xff\x9e\x6f\x53", 7, 0x2cbafa8e741d49caULL, 0x2f022773a766795dULL },
136 : { "\xba\x02\xab\x18\x30\xc5\x0e\x8a", 8, 0x4677f04c06e0758dULL, 0x2f022773a766795dULL },
137 : { "\xec\x4e\x7a\x72\x1e\x71\x2a\xc9\x33", 9, 0x5afe09e8214e2163ULL, 0x2f022773a766795dULL },
138 : { "\xfd\xe2\x9c\x0f\x72\xb7\x08\xea\xd0\x78", 10, 0x115b6276d209fab6ULL, 0x2f022773a766795dULL },
139 : { "\x65\xc4\x8a\xb8\x80\x86\x9a\x79\x00\xb7\xae", 11, 0xd0636d2f01cf3a3eULL, 0x2f022773a766795dULL },
140 : { "\x77\xe9\xd7\x80\x0e\x3f\x5c\x43\xc8\xc2\x46\x39", 12, 0x6d259f5fef74f93eULL, 0x2f022773a766795dULL },
141 : { 0, 0, 0, 0 }
142 : };
143 :
144 : /**
145 : * Test vectors for MurmorHash3_x86_128
146 : */
147 : static struct hash_test_vector TEST_MURMUR3[] = {
148 : #include "murmur3test.c"
149 : { 0, 0, { 0 }, { 0 } }
150 : };
151 :
152 : /**
153 : * Test vectors for SpookyHash_128
154 : */
155 : static struct hash_test_vector TEST_SPOOKY2[] = {
156 : #include "spooky2test.c"
157 : { 0, 0, { 0 }, { 0 } }
158 : };
159 :
160 : /**
161 : * Test vectors for MetroHash_128_1
162 : */
163 : static struct hash_test_vector TEST_METRO[] = {
164 : #include "metrotest.c"
165 : { 0, 0, { 0 }, { 0 } }
166 : };
167 :
168 : #define HASH_TEST_MAX 512 /* tests are never longer than 512 bytes */
169 :
170 1 : static void test_hash(void)
171 : {
172 : unsigned i;
173 : unsigned char* seed_aligned;
174 : void* seed_alloc;
175 : unsigned char* buffer_aligned;
176 : void* buffer_alloc;
177 :
178 1 : seed_aligned = malloc_nofail_align(HASH_MAX, &seed_alloc);
179 1 : buffer_aligned = malloc_nofail_align(HASH_TEST_MAX, &buffer_alloc);
180 :
181 20 : for (i = 0; TEST_HASH32[i].data; ++i) {
182 : uint32_t digest;
183 19 : memcpy(buffer_aligned, TEST_HASH32[i].data, TEST_HASH32[i].len);
184 19 : digest = tommy_hash_u32(TEST_HASH32[i].seed, buffer_aligned, TEST_HASH32[i].len);
185 19 : if (digest != TEST_HASH32[i].digest) {
186 : /* LCOV_EXCL_START */
187 : log_fatal("Failed hash32 test\n");
188 : exit(EXIT_FAILURE);
189 : /* LCOV_EXCL_STOP */
190 : }
191 : }
192 :
193 24 : for (i = 0; TEST_STRHASH32[i].data; ++i) {
194 : uint32_t digest;
195 23 : memcpy(buffer_aligned, TEST_STRHASH32[i].data, strlen(TEST_STRHASH32[i].data) + 1);
196 23 : digest = tommy_strhash_u32(TEST_STRHASH32[i].seed, buffer_aligned);
197 23 : if (digest != TEST_STRHASH32[i].digest) {
198 : /* LCOV_EXCL_START */
199 : log_fatal("Failed strhash32 test\n");
200 : exit(EXIT_FAILURE);
201 : /* LCOV_EXCL_STOP */
202 : }
203 : }
204 :
205 20 : for (i = 0; TEST_HASH64[i].data; ++i) {
206 : uint64_t digest;
207 19 : memcpy(buffer_aligned, TEST_HASH64[i].data, TEST_HASH64[i].len);
208 19 : digest = tommy_hash_u64(TEST_HASH64[i].seed, buffer_aligned, TEST_HASH64[i].len);
209 19 : if (digest != TEST_HASH64[i].digest) {
210 : /* LCOV_EXCL_START */
211 : log_fatal("Failed hash64 test\n");
212 : exit(EXIT_FAILURE);
213 : /* LCOV_EXCL_STOP */
214 : }
215 : }
216 :
217 :
218 264 : for (i = 0; TEST_MURMUR3[i].data; ++i) {
219 : unsigned char digest[HASH_MAX];
220 263 : memcpy(buffer_aligned, TEST_MURMUR3[i].data, TEST_MURMUR3[i].len);
221 263 : memcpy(seed_aligned, TEST_MURMUR3[i].seed, HASH_MAX);
222 263 : memhash(HASH_MURMUR3, seed_aligned, digest, buffer_aligned, TEST_MURMUR3[i].len);
223 263 : if (memcmp(digest, TEST_MURMUR3[i].digest, HASH_MAX) != 0) {
224 : /* LCOV_EXCL_START */
225 : log_fatal("Failed Murmur3 test\n");
226 : exit(EXIT_FAILURE);
227 : /* LCOV_EXCL_STOP */
228 : }
229 : }
230 :
231 264 : for (i = 0; TEST_SPOOKY2[i].data; ++i) {
232 : unsigned char digest[HASH_MAX];
233 263 : memcpy(buffer_aligned, TEST_SPOOKY2[i].data, TEST_SPOOKY2[i].len);
234 263 : memcpy(seed_aligned, TEST_SPOOKY2[i].seed, HASH_MAX);
235 263 : memhash(HASH_SPOOKY2, seed_aligned, digest, buffer_aligned, TEST_SPOOKY2[i].len);
236 263 : if (memcmp(digest, TEST_SPOOKY2[i].digest, HASH_MAX) != 0) {
237 : /* LCOV_EXCL_START */
238 : log_fatal("Failed Spooky2 test\n");
239 : exit(EXIT_FAILURE);
240 : /* LCOV_EXCL_STOP */
241 : }
242 : }
243 :
244 266 : for (i = 0; TEST_METRO[i].data; ++i) {
245 : unsigned char digest[HASH_MAX];
246 265 : memcpy(buffer_aligned, TEST_METRO[i].data, TEST_METRO[i].len);
247 265 : memcpy(seed_aligned, TEST_METRO[i].seed, HASH_MAX);
248 265 : memhash(HASH_METRO, seed_aligned, digest, buffer_aligned, TEST_METRO[i].len);
249 265 : if (memcmp(digest, TEST_METRO[i].digest, HASH_MAX) != 0) {
250 : /* LCOV_EXCL_START */
251 : log_fatal("Failed Metro test\n");
252 : exit(EXIT_FAILURE);
253 : /* LCOV_EXCL_STOP */
254 : }
255 : }
256 :
257 1 : free(buffer_alloc);
258 1 : free(seed_alloc);
259 1 : }
260 :
261 : struct crc_test_vector {
262 : const char* data;
263 : int len;
264 : uint32_t digest;
265 : };
266 :
267 : /**
268 : * Test vectors for CRC32C (Castagnoli)
269 : */
270 : static struct crc_test_vector TEST_CRC32C[] = {
271 : { "", 0, 0 },
272 : { "\x61", 1, 0xc1d04330 },
273 : { "\x66\x6f\x6f", 3, 0xcfc4ae1d },
274 : { "\x68\x65\x6c\x6c\x6f\x20\x77\x6f\x72\x6c\x64", 11, 0xc99465aa },
275 : { "\x68\x65\x6c\x6c\x6f\x20", 6, 0x7e627e58 },
276 : { "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00", 32, 0x8a9136aa },
277 : { "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff", 32, 0x62a8ab43 },
278 : { "\x1f\x1e\x1d\x1c\x1b\x1a\x19\x18\x17\x16\x15\x14\x13\x12\x11\x10\x0f\x0e\x0d\x0c\x0b\x0a\x09\x08\x07\x06\x05\x04\x03\x02\x01\x00", 32, 0x113fdb5c },
279 : { "\x01\xc0\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x14\x00\x00\x00\x00\x00\x04\x00\x00\x00\x00\x14\x00\x00\x00\x18\x28\x00\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00", 48, 0xd9963a56 },
280 : { "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f", 32, 0x46dd794e },
281 : { "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f\x20\x21\x22\x23\x24\x25\x26\x27\x28", 40, 0x0e2c157f },
282 : { "\x29\x2a\x2b\x2c\x2d\x2e\x2f\x30\x31\x32\x33\x34\x35\x36\x37\x38\x39\x3a\x3b\x3c\x3d\x3e\x3f\x40\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4a\x4b\x4c\x4d\x4e\x4f\x50", 40, 0xe980ebf6 },
283 : { "\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5a\x5b\x5c\x5d\x5e\x5f\x60\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6a\x6b\x6c\x6d\x6e\x6f\x70\x71\x72\x73\x74\x75\x76\x77\x78", 40, 0xde74bded },
284 : { "\x79\x7a\x7b\x7c\x7d\x7e\x7f\x80\x81\x82\x83\x84\x85\x86\x87\x88\x89\x8a\x8b\x8c\x8d\x8e\x8f\x90\x91\x92\x93\x94\x95\x96\x97\x98\x99\x9a\x9b\x9c\x9d\x9e\x9f\xa0", 40, 0xd579c862 },
285 : { "\xa1\xa2\xa3\xa4\xa5\xa6\xa7\xa8\xa9\xaa\xab\xac\xad\xae\xaf\xb0\xb1\xb2\xb3\xb4\xb5\xb6\xb7\xb8\xb9\xba\xbb\xbc\xbd\xbe\xbf\xc0\xc1\xc2\xc3\xc4\xc5\xc6\xc7\xc8", 40, 0xba979ad0 },
286 : { "\xc9\xca\xcb\xcc\xcd\xce\xcf\xd0\xd1\xd2\xd3\xd4\xd5\xd6\xd7\xd8\xd9\xda\xdb\xdc\xdd\xde\xdf\xe0\xe1\xe2\xe3\xe4\xe5\xe6\xe7\xe8\xe9\xea\xeb\xec\xed\xee\xef\xf0", 40, 0x2b29d913 },
287 : { "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f\x20\x21\x22\x23\x24\x25\x26\x27\x28\x29\x2a\x2b\x2c\x2d\x2e\x2f\x30\x31\x32\x33\x34\x35\x36\x37\x38\x39\x3a\x3b\x3c\x3d\x3e\x3f\x40\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4a\x4b\x4c\x4d\x4e\x4f\x50\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5a\x5b\x5c\x5d\x5e\x5f\x60\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6a\x6b\x6c\x6d\x6e\x6f\x70\x71\x72\x73\x74\x75\x76\x77\x78\x79\x7a\x7b\x7c\x7d\x7e\x7f\x80\x81\x82\x83\x84\x85\x86\x87\x88\x89\x8a\x8b\x8c\x8d\x8e\x8f\x90\x91\x92\x93\x94\x95\x96\x97\x98\x99\x9a\x9b\x9c\x9d\x9e\x9f\xa0\xa1\xa2\xa3\xa4\xa5\xa6\xa7\xa8\xa9\xaa\xab\xac\xad\xae\xaf\xb0\xb1\xb2\xb3\xb4\xb5\xb6\xb7\xb8\xb9\xba\xbb\xbc\xbd\xbe\xbf\xc0\xc1\xc2\xc3\xc4\xc5\xc6\xc7\xc8\xc9\xca\xcb\xcc\xcd\xce\xcf\xd0\xd1\xd2\xd3\xd4\xd5\xd6\xd7\xd8\xd9\xda\xdb\xdc\xdd\xde\xdf\xe0\xe1\xe2\xe3\xe4\xe5\xe6\xe7\xe8\xe9\xea\xeb\xec\xed\xee\xef\xf0", 240, 0x24c5d375 },
288 : { 0, 0, 0 }
289 : };
290 :
291 1 : static void test_crc32c(void)
292 : {
293 : unsigned i;
294 :
295 18 : for (i = 0; TEST_CRC32C[i].data; ++i) {
296 : uint32_t digest;
297 : uint32_t digest_gen;
298 :
299 17 : digest = crc32c(0, (const unsigned char*)TEST_CRC32C[i].data, TEST_CRC32C[i].len);
300 17 : digest_gen = crc32c_gen(0, (const unsigned char*)TEST_CRC32C[i].data, TEST_CRC32C[i].len);
301 :
302 17 : if (digest != TEST_CRC32C[i].digest || digest_gen != TEST_CRC32C[i].digest) {
303 : /* LCOV_EXCL_START */
304 : log_fatal("Failed CRC32C test\n");
305 : exit(EXIT_FAILURE);
306 : /* LCOV_EXCL_STOP */
307 : }
308 : }
309 1 : }
310 :
311 : /**
312 : * Size of tommy data structures.
313 : */
314 : #define TOMMY_SIZE 256
315 :
316 384 : static int tommy_test_search(const void* arg, const void* obj)
317 : {
318 384 : return arg != obj;
319 : }
320 :
321 4324 : static int tommy_test_compare(const void* void_arg_a, const void* void_arg_b)
322 : {
323 4324 : if (void_arg_a < void_arg_b)
324 2007 : return -1;
325 2317 : if (void_arg_a > void_arg_b)
326 2058 : return 1;
327 259 : return 0;
328 : }
329 :
330 : static unsigned tommy_test_foreach_count;
331 :
332 512 : static void tommy_test_foreach(void* obj)
333 : {
334 : (void)obj;
335 :
336 512 : ++tommy_test_foreach_count;
337 512 : }
338 :
339 512 : static void tommy_test_foreach_arg(void* void_arg, void* obj)
340 : {
341 512 : unsigned* arg = void_arg;
342 :
343 : (void)obj;
344 :
345 512 : ++*arg;
346 512 : }
347 :
348 1 : static void test_tommy(void)
349 : {
350 : tommy_array array;
351 : tommy_arrayblkof arrayblkof;
352 : tommy_list list;
353 : tommy_hashdyn hashdyn;
354 : tommy_tree tree;
355 : tommy_node node[TOMMY_SIZE + 1];
356 : unsigned i;
357 :
358 1 : tommy_array_init(&array);
359 1 : tommy_arrayblkof_init(&arrayblkof, sizeof(unsigned));
360 :
361 257 : for (i = 0; i < TOMMY_SIZE; ++i) {
362 256 : tommy_array_insert(&array, &node[i]);
363 256 : tommy_arrayblkof_grow(&arrayblkof, i + 1);
364 256 : *(unsigned*)tommy_arrayblkof_ref(&arrayblkof, i) = i;
365 : }
366 :
367 1 : tommy_array_grow(&array, TOMMY_SIZE);
368 1 : tommy_arrayblkof_grow(&arrayblkof, TOMMY_SIZE);
369 :
370 1 : if (tommy_array_memory_usage(&array) < TOMMY_SIZE * sizeof(void*)) {
371 : /* LCOV_EXCL_START */
372 : goto bail;
373 : /* LCOV_EXCL_STOP */
374 : }
375 1 : if (tommy_arrayblkof_memory_usage(&arrayblkof) < TOMMY_SIZE * sizeof(unsigned)) {
376 : /* LCOV_EXCL_START */
377 : goto bail;
378 : /* LCOV_EXCL_STOP */
379 : }
380 :
381 257 : for (i = 0; i < TOMMY_SIZE; ++i) {
382 256 : if (tommy_array_get(&array, i) != &node[i]) {
383 : /* LCOV_EXCL_START */
384 : goto bail;
385 : /* LCOV_EXCL_STOP */
386 : }
387 256 : if (*(unsigned*)tommy_arrayblkof_ref(&arrayblkof, i) != i) {
388 : /* LCOV_EXCL_START */
389 : goto bail;
390 : /* LCOV_EXCL_STOP */
391 : }
392 : }
393 :
394 1 : tommy_arrayblkof_done(&arrayblkof);
395 1 : tommy_array_done(&array);
396 :
397 1 : tommy_list_init(&list);
398 :
399 1 : if (!tommy_list_empty(&list)) {
400 : /* LCOV_EXCL_START */
401 : goto bail;
402 : /* LCOV_EXCL_STOP */
403 : }
404 :
405 1 : if (tommy_list_tail(&list)) {
406 : /* LCOV_EXCL_START */
407 : goto bail;
408 : /* LCOV_EXCL_STOP */
409 : }
410 :
411 1 : if (tommy_list_head(&list)) {
412 : /* LCOV_EXCL_START */
413 : goto bail;
414 : /* LCOV_EXCL_STOP */
415 : }
416 :
417 1 : tommy_list_insert_tail(&list, &node[0], &node[0]);
418 :
419 1 : if (tommy_list_tail(&list) != tommy_list_head(&list)) {
420 : /* LCOV_EXCL_START */
421 : goto bail;
422 : /* LCOV_EXCL_STOP */
423 : }
424 :
425 1 : tommy_hashdyn_init(&hashdyn);
426 :
427 257 : for (i = 0; i < TOMMY_SIZE; ++i)
428 256 : tommy_hashdyn_insert(&hashdyn, &node[i], &node[i], i % 64);
429 :
430 1 : if (tommy_hashdyn_count(&hashdyn) != TOMMY_SIZE) {
431 : /* LCOV_EXCL_START */
432 : goto bail;
433 : /* LCOV_EXCL_STOP */
434 : }
435 :
436 1 : if (tommy_hashdyn_memory_usage(&hashdyn) < TOMMY_SIZE * sizeof(tommy_node)) {
437 : /* LCOV_EXCL_START */
438 : goto bail;
439 : /* LCOV_EXCL_STOP */
440 : }
441 :
442 1 : tommy_test_foreach_count = 0;
443 1 : tommy_hashdyn_foreach(&hashdyn, tommy_test_foreach);
444 1 : if (tommy_test_foreach_count != TOMMY_SIZE) {
445 : /* LCOV_EXCL_START */
446 : goto bail;
447 : /* LCOV_EXCL_STOP */
448 : }
449 :
450 1 : tommy_test_foreach_count = 0;
451 1 : tommy_hashdyn_foreach_arg(&hashdyn, tommy_test_foreach_arg, &tommy_test_foreach_count);
452 1 : if (tommy_test_foreach_count != TOMMY_SIZE) {
453 : /* LCOV_EXCL_START */
454 : goto bail;
455 : /* LCOV_EXCL_STOP */
456 : }
457 :
458 129 : for (i = 0; i < TOMMY_SIZE / 2; ++i)
459 128 : tommy_hashdyn_remove_existing(&hashdyn, &node[i]);
460 :
461 129 : for (i = 0; i < TOMMY_SIZE / 2; ++i) {
462 128 : if (tommy_hashdyn_remove(&hashdyn, tommy_test_search, &node[i], i % 64) != 0) {
463 : /* LCOV_EXCL_START */
464 : goto bail;
465 : /* LCOV_EXCL_STOP */
466 : }
467 : }
468 129 : for (i = TOMMY_SIZE / 2; i < TOMMY_SIZE; ++i) {
469 128 : if (tommy_hashdyn_remove(&hashdyn, tommy_test_search, &node[i], i % 64) == 0) {
470 : /* LCOV_EXCL_START */
471 : goto bail;
472 : /* LCOV_EXCL_STOP */
473 : }
474 : }
475 :
476 1 : if (tommy_hashdyn_count(&hashdyn) != 0) {
477 : /* LCOV_EXCL_START */
478 : goto bail;
479 : /* LCOV_EXCL_STOP */
480 : }
481 :
482 1 : tommy_hashdyn_done(&hashdyn);
483 :
484 1 : tommy_tree_init(&tree, tommy_test_compare);
485 :
486 257 : for (i = 0; i < TOMMY_SIZE; ++i)
487 256 : tommy_tree_insert(&tree, &node[i], (void*)(uintptr_t)(i + 1));
488 :
489 : /* try to insert a duplicate, count should not change */
490 1 : tommy_tree_insert(&tree, &node[TOMMY_SIZE], (void*)(uintptr_t)1);
491 :
492 1 : if (tommy_tree_count(&tree) != TOMMY_SIZE) {
493 : /* LCOV_EXCL_START */
494 : goto bail;
495 : /* LCOV_EXCL_STOP */
496 : }
497 1 : if (tommy_tree_memory_usage(&tree) < TOMMY_SIZE * sizeof(tommy_node)) {
498 : /* LCOV_EXCL_START */
499 : goto bail;
500 : /* LCOV_EXCL_STOP */
501 : }
502 1 : if (tommy_tree_search(&tree, (void*)1) != (void*)1) {
503 : /* LCOV_EXCL_START */
504 : goto bail;
505 : /* LCOV_EXCL_STOP */
506 : }
507 1 : if (tommy_tree_search(&tree, (void*)-1) != 0) {
508 : /* LCOV_EXCL_START */
509 : goto bail;
510 : /* LCOV_EXCL_STOP */
511 : }
512 1 : if (tommy_tree_search_compare(&tree, tommy_test_compare, (void*)1) != (void*)1) {
513 : /* LCOV_EXCL_START */
514 : goto bail;
515 : /* LCOV_EXCL_STOP */
516 : }
517 1 : if (tommy_tree_search_compare(&tree, tommy_test_compare, (void*)-1) != 0) {
518 : /* LCOV_EXCL_START */
519 : goto bail;
520 : /* LCOV_EXCL_STOP */
521 : }
522 :
523 1 : tommy_test_foreach_count = 0;
524 1 : tommy_tree_foreach(&tree, tommy_test_foreach);
525 1 : if (tommy_test_foreach_count != TOMMY_SIZE) {
526 : /* LCOV_EXCL_START */
527 : goto bail;
528 : /* LCOV_EXCL_STOP */
529 : }
530 :
531 1 : tommy_test_foreach_count = 0;
532 1 : tommy_tree_foreach_arg(&tree, tommy_test_foreach_arg, &tommy_test_foreach_count);
533 1 : if (tommy_test_foreach_count != TOMMY_SIZE) {
534 : /* LCOV_EXCL_START */
535 : goto bail;
536 : /* LCOV_EXCL_STOP */
537 : }
538 :
539 129 : for (i = 0; i < TOMMY_SIZE / 2; ++i)
540 128 : tommy_tree_remove_existing(&tree, &node[i]);
541 :
542 129 : for (i = 0; i < TOMMY_SIZE / 2; ++i) {
543 128 : if (tommy_tree_remove(&tree, (void*)(uintptr_t)(i + 1)) != 0) {
544 : /* LCOV_EXCL_START */
545 : goto bail;
546 : /* LCOV_EXCL_STOP */
547 : }
548 : }
549 :
550 129 : for (i = TOMMY_SIZE / 2; i < TOMMY_SIZE; ++i) {
551 128 : if (tommy_tree_remove(&tree, (void*)(uintptr_t)(i + 1)) == 0) {
552 : /* LCOV_EXCL_START */
553 : goto bail;
554 : /* LCOV_EXCL_STOP */
555 : }
556 : }
557 :
558 1 : if (tommy_tree_count(&tree) != 0) {
559 : /* LCOV_EXCL_START */
560 : goto bail;
561 : /* LCOV_EXCL_STOP */
562 : }
563 :
564 1 : return;
565 0 : bail:
566 : /* LCOV_EXCL_START */
567 : log_fatal("Failed tommy test\n");
568 : exit(EXIT_FAILURE);
569 : /* LCOV_EXCL_STOP */
570 : }
571 :
572 1 : void selftest(void)
573 : {
574 1 : log_tag("selftest:\n");
575 1 : log_flush();
576 :
577 1 : msg_progress("Self test...\n");
578 :
579 : /* large file check */
580 : if (sizeof(off_t) < sizeof(uint64_t)) {
581 : /* LCOV_EXCL_START */
582 : log_fatal("Missing support for large files\n");
583 : exit(EXIT_FAILURE);
584 : /* LCOV_EXCL_STOP */
585 : }
586 :
587 1 : test_hash();
588 1 : test_crc32c();
589 1 : test_tommy();
590 1 : if (raid_selftest() != 0) {
591 : /* LCOV_EXCL_START */
592 : log_fatal("Failed SELF test\n");
593 : exit(EXIT_FAILURE);
594 : /* LCOV_EXCL_STOP */
595 : }
596 1 : if (raid_test_sort() != 0) {
597 : /* LCOV_EXCL_START */
598 : log_fatal("Failed SORT test\n");
599 : exit(EXIT_FAILURE);
600 : /* LCOV_EXCL_STOP */
601 : }
602 1 : if (raid_test_insert() != 0) {
603 : /* LCOV_EXCL_START */
604 : log_fatal("Failed INSERT test\n");
605 : exit(EXIT_FAILURE);
606 : /* LCOV_EXCL_STOP */
607 : }
608 1 : if (raid_test_combo() != 0) {
609 : /* LCOV_EXCL_START */
610 : log_fatal("Failed COMBO test\n");
611 : exit(EXIT_FAILURE);
612 : /* LCOV_EXCL_STOP */
613 : }
614 1 : if (raid_test_par(RAID_MODE_VANDERMONDE, 32, 256) != 0) {
615 : /* LCOV_EXCL_START */
616 : log_fatal("Failed GEN Vandermonde test\n");
617 : exit(EXIT_FAILURE);
618 : /* LCOV_EXCL_STOP */
619 : }
620 1 : if (raid_test_rec(RAID_MODE_VANDERMONDE, 12, 256) != 0) {
621 : /* LCOV_EXCL_START */
622 : log_fatal("Failed REC Vandermonde test\n");
623 : exit(EXIT_FAILURE);
624 : /* LCOV_EXCL_STOP */
625 : }
626 1 : if (raid_test_par(RAID_MODE_CAUCHY, 32, 256) != 0) {
627 : /* LCOV_EXCL_START */
628 : log_fatal("Failed GEN Cauchy test\n");
629 : exit(EXIT_FAILURE);
630 : /* LCOV_EXCL_STOP */
631 : }
632 1 : if (raid_test_rec(RAID_MODE_CAUCHY, 12, 256) != 0) {
633 : /* LCOV_EXCL_START */
634 : log_fatal("Failed REC Cauchy test\n");
635 : exit(EXIT_FAILURE);
636 : /* LCOV_EXCL_STOP */
637 : }
638 1 : if (raid_test_par(RAID_MODE_CAUCHY, 1, 256) != 0) {
639 : /* LCOV_EXCL_START */
640 : log_fatal("Failed GEN Cauchy test single data disk\n");
641 : exit(EXIT_FAILURE);
642 : /* LCOV_EXCL_STOP */
643 : }
644 1 : }
645 :
|
