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 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 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 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 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 * 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 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 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 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 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 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 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 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 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 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 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 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 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
Indexes created Sat Sep 20 22:09:52 GMT 2025