1 /* $NetBSD: cdbw.c,v 1.9 2023/08/08 10:34:08 riastradh Exp $ */
2 /*-
3 * Copyright (c) 2009, 2010, 2015 The NetBSD Foundation, Inc.
4 * All rights reserved.
5 *
6 * This code is derived from software contributed to The NetBSD Foundation
7 * by Joerg Sonnenberger and Alexander Nasonov.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
28 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
29 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
30 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34 #if HAVE_NBTOOL_CONFIG_H
35 #include "nbtool_config.h"
36 #endif
37
38 #include <sys/cdefs.h>
39 __RCSID("$NetBSD: cdbw.c,v 1.9 2023/08/08 10:34:08 riastradh Exp $");
40
41 #include "namespace.h"
42
43 #if !HAVE_NBTOOL_CONFIG_H || HAVE_SYS_ENDIAN_H
44 #include <sys/endian.h>
45 #endif
46 #include <sys/queue.h>
47 #include <cdbw.h>
48 #include <stdlib.h>
49 #include <string.h>
50 #include <unistd.h>
51
52 #if !HAVE_NBTOOL_CONFIG_H
53 #include <sys/bitops.h>
54 #else
55 static inline int
my_fls32(uint32_t n)56 my_fls32(uint32_t n)
57 {
58 int v;
59
60 if (!n)
61 return 0;
62
63 v = 32;
64 if ((n & 0xFFFF0000U) == 0) {
65 n <<= 16;
66 v -= 16;
67 }
68 if ((n & 0xFF000000U) == 0) {
69 n <<= 8;
70 v -= 8;
71 }
72 if ((n & 0xF0000000U) == 0) {
73 n <<= 4;
74 v -= 4;
75 }
76 if ((n & 0xC0000000U) == 0) {
77 n <<= 2;
78 v -= 2;
79 }
80 if ((n & 0x80000000U) == 0) {
81 n <<= 1;
82 v -= 1;
83 }
84 return v;
85 }
86
87 static inline void
fast_divide32_prepare(uint32_t div,uint32_t * m,uint8_t * s1,uint8_t * s2)88 fast_divide32_prepare(uint32_t div, uint32_t * m,
89 uint8_t *s1, uint8_t *s2)
90 {
91 uint64_t mt;
92 int l;
93
94 l = my_fls32(div - 1);
95 mt = (uint64_t)(0x100000000ULL * ((1ULL << l) - div));
96 *m = (uint32_t)(mt / div + 1);
97 *s1 = (l > 1) ? 1U : (uint8_t)l;
98 *s2 = (l == 0) ? 0 : (uint8_t)(l - 1);
99 }
100
101 static inline uint32_t
fast_divide32(uint32_t v,uint32_t div,uint32_t m,uint8_t s1,uint8_t s2)102 fast_divide32(uint32_t v, uint32_t div, uint32_t m, uint8_t s1,
103 uint8_t s2)
104 {
105 uint32_t t;
106
107 t = (uint32_t)(((uint64_t)v * m) >> 32);
108 return (t + ((v - t) >> s1)) >> s2;
109 }
110
111 static inline uint32_t
fast_remainder32(uint32_t v,uint32_t div,uint32_t m,uint8_t s1,uint8_t s2)112 fast_remainder32(uint32_t v, uint32_t div, uint32_t m, uint8_t s1,
113 uint8_t s2)
114 {
115
116 return v - div * fast_divide32(v, div, m, s1, s2);
117 }
118 #endif
119
120 #ifdef __weak_alias
121 __weak_alias(cdbw_close,_cdbw_close)
122 __weak_alias(cdbw_open,_cdbw_open)
123 __weak_alias(cdbw_output,_cdbw_output)
124 __weak_alias(cdbw_put,_cdbw_put)
125 __weak_alias(cdbw_put_data,_cdbw_put_data)
126 __weak_alias(cdbw_put_key,_cdbw_put_key)
127 #endif
128
129 struct key_hash {
130 SLIST_ENTRY(key_hash) link;
131 uint32_t hashes[3];
132 uint32_t idx;
133 void *key;
134 size_t keylen;
135 };
136
137 SLIST_HEAD(key_hash_head, key_hash);
138
139 struct cdbw {
140 size_t data_counter;
141 size_t data_allocated;
142 size_t data_size;
143 size_t *data_len;
144 void **data_ptr;
145
146 size_t hash_size;
147 struct key_hash_head *hash;
148 size_t key_counter;
149 };
150
151 /* Max. data counter that allows the index size to be 32bit. */
152 static const uint32_t max_data_counter = 0xccccccccU;
153
154 struct cdbw *
cdbw_open(void)155 cdbw_open(void)
156 {
157 struct cdbw *cdbw;
158 size_t i;
159
160 cdbw = calloc(sizeof(*cdbw), 1);
161 if (cdbw == NULL)
162 return NULL;
163
164 cdbw->hash_size = 1024;
165 cdbw->hash = calloc(cdbw->hash_size, sizeof(*cdbw->hash));
166 if (cdbw->hash == NULL) {
167 free(cdbw);
168 return NULL;
169 }
170
171 for (i = 0; i < cdbw->hash_size; ++i)
172 SLIST_INIT(cdbw->hash + i);
173
174 return cdbw;
175 }
176
177 int
cdbw_put(struct cdbw * cdbw,const void * key,size_t keylen,const void * data,size_t datalen)178 cdbw_put(struct cdbw *cdbw, const void *key, size_t keylen,
179 const void *data, size_t datalen)
180 {
181 uint32_t idx;
182 int rv;
183
184 rv = cdbw_put_data(cdbw, data, datalen, &idx);
185 if (rv)
186 return rv;
187 rv = cdbw_put_key(cdbw, key, keylen, idx);
188 if (rv) {
189 --cdbw->data_counter;
190 free(cdbw->data_ptr[cdbw->data_counter]);
191 cdbw->data_size -= datalen;
192 return rv;
193 }
194 return 0;
195 }
196
197 int
cdbw_put_data(struct cdbw * cdbw,const void * data,size_t datalen,uint32_t * idx)198 cdbw_put_data(struct cdbw *cdbw, const void *data, size_t datalen,
199 uint32_t *idx)
200 {
201
202 if (cdbw->data_counter == max_data_counter)
203 return -1;
204
205 if (cdbw->data_size + datalen < cdbw->data_size ||
206 cdbw->data_size + datalen > 0xffffffffU)
207 return -1; /* Overflow */
208
209 if (cdbw->data_allocated == cdbw->data_counter) {
210 void **new_data_ptr;
211 size_t *new_data_len;
212 size_t new_allocated;
213
214 if (cdbw->data_allocated == 0)
215 new_allocated = 256;
216 else
217 new_allocated = cdbw->data_allocated * 2;
218
219 new_data_ptr = realloc(cdbw->data_ptr,
220 sizeof(*cdbw->data_ptr) * new_allocated);
221 if (new_data_ptr == NULL)
222 return -1;
223 cdbw->data_ptr = new_data_ptr;
224
225 new_data_len = realloc(cdbw->data_len,
226 sizeof(*cdbw->data_len) * new_allocated);
227 if (new_data_len == NULL)
228 return -1;
229 cdbw->data_len = new_data_len;
230
231 cdbw->data_allocated = new_allocated;
232 }
233
234 cdbw->data_ptr[cdbw->data_counter] = malloc(datalen);
235 if (cdbw->data_ptr[cdbw->data_counter] == NULL)
236 return -1;
237 memcpy(cdbw->data_ptr[cdbw->data_counter], data, datalen);
238 cdbw->data_len[cdbw->data_counter] = datalen;
239 cdbw->data_size += datalen;
240 *idx = cdbw->data_counter++;
241 return 0;
242 }
243
244 int
cdbw_put_key(struct cdbw * cdbw,const void * key,size_t keylen,uint32_t idx)245 cdbw_put_key(struct cdbw *cdbw, const void *key, size_t keylen, uint32_t idx)
246 {
247 uint32_t hashes[3];
248 struct key_hash_head *head, *head2, *new_head;
249 struct key_hash *key_hash;
250 size_t new_hash_size, i;
251
252 if (idx >= cdbw->data_counter ||
253 cdbw->key_counter == max_data_counter)
254 return -1;
255
256 mi_vector_hash(key, keylen, 0, hashes);
257
258 head = cdbw->hash + (hashes[0] & (cdbw->hash_size - 1));
259 SLIST_FOREACH(key_hash, head, link) {
260 if (key_hash->keylen != keylen)
261 continue;
262 if (key_hash->hashes[0] != hashes[0])
263 continue;
264 if (key_hash->hashes[1] != hashes[1])
265 continue;
266 if (key_hash->hashes[2] != hashes[2])
267 continue;
268 if (memcmp(key, key_hash->key, keylen))
269 continue;
270 return -1;
271 }
272 key_hash = malloc(sizeof(*key_hash));
273 if (key_hash == NULL)
274 return -1;
275 key_hash->key = malloc(keylen);
276 if (key_hash->key == NULL) {
277 free(key_hash);
278 return -1;
279 }
280 memcpy(key_hash->key, key, keylen);
281 key_hash->hashes[0] = hashes[0];
282 key_hash->hashes[1] = hashes[1];
283 key_hash->hashes[2] = hashes[2];
284 key_hash->keylen = keylen;
285 key_hash->idx = idx;
286 SLIST_INSERT_HEAD(head, key_hash, link);
287 ++cdbw->key_counter;
288
289 if (cdbw->key_counter <= cdbw->hash_size)
290 return 0;
291
292 /* Try to resize the hash table, but ignore errors. */
293 new_hash_size = cdbw->hash_size * 2;
294 new_head = calloc(sizeof(*new_head), new_hash_size);
295 if (new_head == NULL)
296 return 0;
297
298 head = &cdbw->hash[hashes[0] & (cdbw->hash_size - 1)];
299 for (i = 0; i < new_hash_size; ++i)
300 SLIST_INIT(new_head + i);
301
302 for (i = 0; i < cdbw->hash_size; ++i) {
303 head = cdbw->hash + i;
304
305 while ((key_hash = SLIST_FIRST(head)) != NULL) {
306 SLIST_REMOVE_HEAD(head, link);
307 head2 = new_head +
308 (key_hash->hashes[0] & (new_hash_size - 1));
309 SLIST_INSERT_HEAD(head2, key_hash, link);
310 }
311 }
312 free(cdbw->hash);
313 cdbw->hash_size = new_hash_size;
314 cdbw->hash = new_head;
315
316 return 0;
317 }
318
319 void
cdbw_close(struct cdbw * cdbw)320 cdbw_close(struct cdbw *cdbw)
321 {
322 struct key_hash_head *head;
323 struct key_hash *key_hash;
324 size_t i;
325
326 for (i = 0; i < cdbw->hash_size; ++i) {
327 head = cdbw->hash + i;
328 while ((key_hash = SLIST_FIRST(head)) != NULL) {
329 SLIST_REMOVE_HEAD(head, link);
330 free(key_hash->key);
331 free(key_hash);
332 }
333 }
334
335 for (i = 0; i < cdbw->data_counter; ++i)
336 free(cdbw->data_ptr[i]);
337 free(cdbw->data_ptr);
338 free(cdbw->data_len);
339 free(cdbw->hash);
340 free(cdbw);
341 }
342
343 uint32_t
cdbw_stable_seeder(void)344 cdbw_stable_seeder(void)
345 {
346 return 0;
347 }
348
349 /*
350 * For each vertex in the 3-graph, the incidence lists needs to be kept.
351 * Avoid storing the full list by just XORing the indices of the still
352 * incident edges and remember the number of such edges as that's all
353 * the peeling computation needs. This is inspired by:
354 * Cache-Oblivious Peeling of Random Hypergraphs by Djamal Belazzougui,
355 * Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini, and Sebastiano
356 * Vigna. https://arxiv.org/abs/1312.0526
357 *
358 * Unlike in the paper, we don't care about external storage and have
359 * the edge list at hand all the time. As such, no ordering is necessary
360 * and the vertices of the edge don't have to be copied.
361 *
362 * The core observation of the paper above is that for a degree of one,
363 * the incident edge can be obtained directly.
364 */
365 struct vertex {
366 uint32_t degree;
367 uint32_t edges;
368 };
369
370 struct edge {
371 uint32_t vertices[3];
372 uint32_t idx;
373 };
374
375 struct state {
376 uint32_t data_entries;
377 uint32_t entries;
378 uint32_t keys;
379 uint32_t seed;
380
381 uint32_t *g;
382 char *visited;
383
384 struct vertex *vertices;
385 struct edge *edges;
386 uint32_t output_index;
387 uint32_t *output_order;
388 };
389
390 /*
391 * Add (delta == 1) or remove (delta == -1) the edge e
392 * from the incidence lists.
393 */
394 static inline void
change_edge(struct state * state,int delta,uint32_t e)395 change_edge(struct state *state, int delta, uint32_t e)
396 {
397 int i;
398 struct vertex *v;
399 struct edge *e_ = &state->edges[e];
400
401 for (i = 0; i < 3; ++i) {
402 v = &state->vertices[e_->vertices[i]];
403 v->edges ^= e;
404 v->degree += delta;
405 }
406 }
407
408 static inline void
remove_vertex(struct state * state,uint32_t v)409 remove_vertex(struct state *state, uint32_t v)
410 {
411 struct vertex *v_ = &state->vertices[v];
412 uint32_t e;
413
414 if (v_->degree == 1) {
415 e = v_->edges;
416 state->output_order[--state->output_index] = e;
417 change_edge(state, -1, e);
418 }
419 }
420
421 static int
build_graph(struct cdbw * cdbw,struct state * state)422 build_graph(struct cdbw *cdbw, struct state *state)
423 {
424 struct key_hash_head *head;
425 struct key_hash *key_hash;
426 struct edge *e;
427 uint32_t entries_m;
428 uint8_t entries_s1, entries_s2;
429 uint32_t hashes[3];
430 size_t i;
431 int j;
432
433 memset(state->vertices, 0, sizeof(*state->vertices) * state->entries);
434
435 e = state->edges;
436 fast_divide32_prepare(state->entries, &entries_m, &entries_s1,
437 &entries_s2);
438
439 for (i = 0; i < cdbw->hash_size; ++i) {
440 head = &cdbw->hash[i];
441 SLIST_FOREACH(key_hash, head, link) {
442 mi_vector_hash(key_hash->key, key_hash->keylen,
443 state->seed, hashes);
444
445 for (j = 0; j < 3; ++j) {
446 e->vertices[j] = fast_remainder32(hashes[j],
447 state->entries, entries_m, entries_s1,
448 entries_s2);
449 }
450
451 if (e->vertices[0] == e->vertices[1])
452 return -1;
453 if (e->vertices[0] == e->vertices[2])
454 return -1;
455 if (e->vertices[1] == e->vertices[2])
456 return -1;
457 e->idx = key_hash->idx;
458 ++e;
459 }
460 }
461
462 /*
463 * Do the edge processing separately as there is a good chance
464 * the degraded edge case above will happen; this avoid
465 *unnecessary work.
466 */
467 for (i = 0; i < state->keys; ++i)
468 change_edge(state, 1, i);
469
470 state->output_index = state->keys;
471 for (i = 0; i < state->entries; ++i)
472 remove_vertex(state, i);
473
474 i = state->keys;
475 while (i > 0 && i > state->output_index) {
476 --i;
477 e = state->edges + state->output_order[i];
478 for (j = 0; j < 3; ++j)
479 remove_vertex(state, e->vertices[j]);
480 }
481
482 return state->output_index == 0 ? 0 : -1;
483 }
484
485 static void
assign_nodes(struct state * state)486 assign_nodes(struct state *state)
487 {
488 struct edge *e;
489 size_t i;
490
491 uint32_t v0, v1, v2, entries_m;
492 uint8_t entries_s1, entries_s2;
493
494 fast_divide32_prepare(state->data_entries, &entries_m, &entries_s1,
495 &entries_s2);
496
497 for (i = 0; i < state->keys; ++i) {
498 e = state->edges + state->output_order[i];
499 if (!state->visited[e->vertices[0]]) {
500 v0 = e->vertices[0];
501 v1 = e->vertices[1];
502 v2 = e->vertices[2];
503 } else if (!state->visited[e->vertices[1]]) {
504 v0 = e->vertices[1];
505 v1 = e->vertices[0];
506 v2 = e->vertices[2];
507 } else {
508 v0 = e->vertices[2];
509 v1 = e->vertices[0];
510 v2 = e->vertices[1];
511 }
512 state->g[v0] =
513 fast_remainder32((2 * state->data_entries + e->idx
514 - state->g[v1] - state->g[v2]),
515 state->data_entries, entries_m,
516 entries_s1, entries_s2);
517 state->visited[v0] = 1;
518 state->visited[v1] = 1;
519 state->visited[v2] = 1;
520 }
521 }
522
523 static size_t
compute_size(uint32_t size)524 compute_size(uint32_t size)
525 {
526 if (size < 0x100)
527 return 1;
528 else if (size < 0x10000)
529 return 2;
530 else
531 return 4;
532 }
533
534 #define COND_FLUSH_BUFFER(n) do { \
535 if (__predict_false(cur_pos + (n) >= sizeof(buf))) { \
536 ret = write(fd, buf, cur_pos); \
537 if (ret == -1 || (size_t)ret != cur_pos) \
538 return -1; \
539 cur_pos = 0; \
540 } \
541 } while (0)
542
543 static int
print_hash(struct cdbw * cdbw,struct state * state,int fd,const char * descr)544 print_hash(struct cdbw *cdbw, struct state *state, int fd, const char *descr)
545 {
546 uint32_t data_size;
547 uint8_t buf[90000];
548 size_t i, size, size2, cur_pos;
549 ssize_t ret;
550
551 memcpy(buf, "NBCDB\n\0", 7);
552 buf[7] = 1;
553 strncpy((char *)buf + 8, descr, 16);
554 le32enc(buf + 24, cdbw->data_size);
555 le32enc(buf + 28, cdbw->data_counter);
556 le32enc(buf + 32, state->entries);
557 le32enc(buf + 36, state->seed);
558 cur_pos = 40;
559
560 size = compute_size(state->entries);
561 for (i = 0; i < state->entries; ++i) {
562 COND_FLUSH_BUFFER(4);
563 le32enc(buf + cur_pos, state->g[i]);
564 cur_pos += size;
565 }
566 size2 = compute_size(cdbw->data_size);
567 size = size * state->entries % size2;
568 if (size != 0) {
569 size = size2 - size;
570 COND_FLUSH_BUFFER(4);
571 le32enc(buf + cur_pos, 0);
572 cur_pos += size;
573 }
574 for (data_size = 0, i = 0; i < cdbw->data_counter; ++i) {
575 COND_FLUSH_BUFFER(4);
576 le32enc(buf + cur_pos, data_size);
577 cur_pos += size2;
578 data_size += cdbw->data_len[i];
579 }
580 COND_FLUSH_BUFFER(4);
581 le32enc(buf + cur_pos, data_size);
582 cur_pos += size2;
583
584 for (i = 0; i < cdbw->data_counter; ++i) {
585 COND_FLUSH_BUFFER(cdbw->data_len[i]);
586 if (cdbw->data_len[i] < sizeof(buf)) {
587 memcpy(buf + cur_pos, cdbw->data_ptr[i],
588 cdbw->data_len[i]);
589 cur_pos += cdbw->data_len[i];
590 } else {
591 ret = write(fd, cdbw->data_ptr[i], cdbw->data_len[i]);
592 if (ret == -1 || (size_t)ret != cdbw->data_len[i])
593 return -1;
594 }
595 }
596 if (cur_pos != 0) {
597 ret = write(fd, buf, cur_pos);
598 if (ret == -1 || (size_t)ret != cur_pos)
599 return -1;
600 }
601 return 0;
602 }
603
604 int
cdbw_output(struct cdbw * cdbw,int fd,const char * descr,uint32_t (* seedgen)(void))605 cdbw_output(struct cdbw *cdbw, int fd, const char *descr,
606 uint32_t (*seedgen)(void))
607 {
608 struct state state;
609 int rv;
610
611 if (cdbw->data_counter == 0 || cdbw->key_counter == 0) {
612 state.entries = 0;
613 state.seed = 0;
614 print_hash(cdbw, &state, fd, descr);
615 return 0;
616 }
617
618 #if HAVE_NBTOOL_CONFIG_H
619 if (seedgen == NULL)
620 seedgen = cdbw_stable_seeder;
621 #else
622 if (seedgen == NULL)
623 seedgen = arc4random;
624 #endif
625
626 rv = 0;
627
628 state.keys = cdbw->key_counter;
629 state.data_entries = cdbw->data_counter;
630 state.entries = state.keys + (state.keys + 3) / 4;
631 if (state.entries < 10)
632 state.entries = 10;
633
634 #define NALLOC(var, n) var = calloc(sizeof(*var), n)
635 NALLOC(state.g, state.entries);
636 NALLOC(state.visited, state.entries);
637 NALLOC(state.vertices, state.entries);
638 NALLOC(state.edges, state.keys);
639 NALLOC(state.output_order, state.keys);
640 #undef NALLOC
641
642 if (state.g == NULL || state.visited == NULL || state.edges == NULL ||
643 state.vertices == NULL || state.output_order == NULL) {
644 rv = -1;
645 goto release;
646 }
647
648 state.seed = 0;
649 do {
650 if (seedgen == cdbw_stable_seeder)
651 ++state.seed;
652 else
653 state.seed = (*seedgen)();
654 } while (build_graph(cdbw, &state));
655
656 assign_nodes(&state);
657 rv = print_hash(cdbw, &state, fd, descr);
658
659 release:
660 free(state.g);
661 free(state.visited);
662 free(state.vertices);
663 free(state.edges);
664 free(state.output_order);
665
666 return rv;
667 }
668