1 /* $NetBSD: cdbw.c,v 1.6 2017/11/11 18:05:31 alnsn 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.6 2017/11/11 18:05:31 alnsn 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 #ifdef __weak_alias 53 __weak_alias(cdbw_close,_cdbw_close) 54 __weak_alias(cdbw_open,_cdbw_open) 55 __weak_alias(cdbw_output,_cdbw_output) 56 __weak_alias(cdbw_put,_cdbw_put) 57 __weak_alias(cdbw_put_data,_cdbw_put_data) 58 __weak_alias(cdbw_put_key,_cdbw_put_key) 59 #endif 60 61 struct key_hash { 62 SLIST_ENTRY(key_hash) link; 63 uint32_t hashes[3]; 64 uint32_t idx; 65 void *key; 66 size_t keylen; 67 }; 68 69 SLIST_HEAD(key_hash_head, key_hash); 70 71 struct cdbw { 72 size_t data_counter; 73 size_t data_allocated; 74 size_t data_size; 75 size_t *data_len; 76 void **data_ptr; 77 78 size_t hash_size; 79 struct key_hash_head *hash; 80 size_t key_counter; 81 }; 82 83 /* Max. data counter that allows the index size to be 32bit. */ 84 static const uint32_t max_data_counter = 0xccccccccU; 85 86 struct cdbw * 87 cdbw_open(void) 88 { 89 struct cdbw *cdbw; 90 size_t i; 91 92 cdbw = calloc(sizeof(*cdbw), 1); 93 if (cdbw == NULL) 94 return NULL; 95 96 cdbw->hash_size = 1024; 97 cdbw->hash = calloc(cdbw->hash_size, sizeof(*cdbw->hash)); 98 if (cdbw->hash == NULL) { 99 free(cdbw); 100 return NULL; 101 } 102 103 for (i = 0; i < cdbw->hash_size; ++i) 104 SLIST_INIT(cdbw->hash + i); 105 106 return cdbw; 107 } 108 109 int 110 cdbw_put(struct cdbw *cdbw, const void *key, size_t keylen, 111 const void *data, size_t datalen) 112 { 113 uint32_t idx; 114 int rv; 115 116 rv = cdbw_put_data(cdbw, data, datalen, &idx); 117 if (rv) 118 return rv; 119 rv = cdbw_put_key(cdbw, key, keylen, idx); 120 if (rv) { 121 --cdbw->data_counter; 122 free(cdbw->data_ptr[cdbw->data_counter]); 123 cdbw->data_size -= datalen; 124 return rv; 125 } 126 return 0; 127 } 128 129 int 130 cdbw_put_data(struct cdbw *cdbw, const void *data, size_t datalen, 131 uint32_t *idx) 132 { 133 134 if (cdbw->data_counter == max_data_counter) 135 return -1; 136 137 if (cdbw->data_size + datalen < cdbw->data_size || 138 cdbw->data_size + datalen > 0xffffffffU) 139 return -1; /* Overflow */ 140 141 if (cdbw->data_allocated == cdbw->data_counter) { 142 void **new_data_ptr; 143 size_t *new_data_len; 144 size_t new_allocated; 145 146 if (cdbw->data_allocated == 0) 147 new_allocated = 256; 148 else 149 new_allocated = cdbw->data_allocated * 2; 150 151 new_data_ptr = realloc(cdbw->data_ptr, 152 sizeof(*cdbw->data_ptr) * new_allocated); 153 if (new_data_ptr == NULL) 154 return -1; 155 cdbw->data_ptr = new_data_ptr; 156 157 new_data_len = realloc(cdbw->data_len, 158 sizeof(*cdbw->data_len) * new_allocated); 159 if (new_data_len == NULL) 160 return -1; 161 cdbw->data_len = new_data_len; 162 163 cdbw->data_allocated = new_allocated; 164 } 165 166 cdbw->data_ptr[cdbw->data_counter] = malloc(datalen); 167 if (cdbw->data_ptr[cdbw->data_counter] == NULL) 168 return -1; 169 memcpy(cdbw->data_ptr[cdbw->data_counter], data, datalen); 170 cdbw->data_len[cdbw->data_counter] = datalen; 171 cdbw->data_size += datalen; 172 *idx = cdbw->data_counter++; 173 return 0; 174 } 175 176 int 177 cdbw_put_key(struct cdbw *cdbw, const void *key, size_t keylen, uint32_t idx) 178 { 179 uint32_t hashes[3]; 180 struct key_hash_head *head, *head2, *new_head; 181 struct key_hash *key_hash; 182 size_t new_hash_size, i; 183 184 if (idx >= cdbw->data_counter || 185 cdbw->key_counter == max_data_counter) 186 return -1; 187 188 mi_vector_hash(key, keylen, 0, hashes); 189 190 head = cdbw->hash + (hashes[0] & (cdbw->hash_size - 1)); 191 SLIST_FOREACH(key_hash, head, link) { 192 if (key_hash->keylen != keylen) 193 continue; 194 if (key_hash->hashes[0] != hashes[0]) 195 continue; 196 if (key_hash->hashes[1] != hashes[1]) 197 continue; 198 if (key_hash->hashes[2] != hashes[2]) 199 continue; 200 if (memcmp(key, key_hash->key, keylen)) 201 continue; 202 return -1; 203 } 204 key_hash = malloc(sizeof(*key_hash)); 205 if (key_hash == NULL) 206 return -1; 207 key_hash->key = malloc(keylen); 208 if (key_hash->key == NULL) { 209 free(key_hash); 210 return -1; 211 } 212 memcpy(key_hash->key, key, keylen); 213 key_hash->hashes[0] = hashes[0]; 214 key_hash->hashes[1] = hashes[1]; 215 key_hash->hashes[2] = hashes[2]; 216 key_hash->keylen = keylen; 217 key_hash->idx = idx; 218 SLIST_INSERT_HEAD(head, key_hash, link); 219 ++cdbw->key_counter; 220 221 if (cdbw->key_counter <= cdbw->hash_size) 222 return 0; 223 224 /* Try to resize the hash table, but ignore errors. */ 225 new_hash_size = cdbw->hash_size * 2; 226 new_head = calloc(sizeof(*new_head), new_hash_size); 227 if (new_head == NULL) 228 return 0; 229 230 head = &cdbw->hash[hashes[0] & (cdbw->hash_size - 1)]; 231 for (i = 0; i < new_hash_size; ++i) 232 SLIST_INIT(new_head + i); 233 234 for (i = 0; i < cdbw->hash_size; ++i) { 235 head = cdbw->hash + i; 236 237 while ((key_hash = SLIST_FIRST(head)) != NULL) { 238 SLIST_REMOVE_HEAD(head, link); 239 head2 = new_head + 240 (key_hash->hashes[0] & (new_hash_size - 1)); 241 SLIST_INSERT_HEAD(head2, key_hash, link); 242 } 243 } 244 free(cdbw->hash); 245 cdbw->hash_size = new_hash_size; 246 cdbw->hash = new_head; 247 248 return 0; 249 } 250 251 void 252 cdbw_close(struct cdbw *cdbw) 253 { 254 struct key_hash_head *head; 255 struct key_hash *key_hash; 256 size_t i; 257 258 for (i = 0; i < cdbw->hash_size; ++i) { 259 head = cdbw->hash + i; 260 while ((key_hash = SLIST_FIRST(head)) != NULL) { 261 SLIST_REMOVE_HEAD(head, link); 262 free(key_hash->key); 263 free(key_hash); 264 } 265 } 266 267 for (i = 0; i < cdbw->data_counter; ++i) 268 free(cdbw->data_ptr[i]); 269 free(cdbw->data_ptr); 270 free(cdbw->data_len); 271 free(cdbw->hash); 272 free(cdbw); 273 } 274 275 uint32_t 276 cdbw_stable_seeder(void) 277 { 278 return 0; 279 } 280 281 /* 282 * The algorithm below is based on paper 283 * Cache-Oblivious Peeling of Random Hypergraphs by Djamal Belazzougui, 284 * Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini, and Sebastiano 285 * Vigna. 286 * http://zola.di.unipi.it/rossano/wp-content/papercite-data/pdf/dcc14.pdf 287 */ 288 289 /* 290 * Data type for a valid oriented edge (v0, v1, v2), v1 < v2. 291 * The first vertex v0 is implicit and is determined by an index 292 * of the corresponding element in the state->oedges array. 293 * If the degree of v0 is greater than 1, other members don't 294 * make sense because they're a result of XORing multiple values. 295 */ 296 struct oedge { 297 uint32_t degree; /* Degree of v0. */ 298 uint32_t verts[2]; /* v1 and v2 */ 299 uint32_t edge; 300 }; 301 302 struct edge { 303 uint32_t idx; 304 305 uint32_t left, middle, right; 306 }; 307 308 struct state { 309 uint32_t data_entries; 310 uint32_t entries; 311 uint32_t keys; 312 uint32_t seed; 313 314 uint32_t *g; 315 char *visited; 316 317 struct oedge *oedges; 318 struct edge *edges; 319 uint32_t output_index; 320 uint32_t *output_order; 321 }; 322 323 /* 324 * Add (delta == 1) or remove (delta == -1) the edge e from vertex v0. 325 */ 326 static inline void 327 add_remove_edge(struct oedge *o, int delta, uint32_t e, 328 uint32_t v0, uint32_t v1, uint32_t v2) 329 { 330 331 o[v0].verts[v1 < v2 ? 0 : 1] ^= v1; 332 o[v0].verts[v1 < v2 ? 1 : 0] ^= v2; 333 o[v0].degree += delta; 334 o[v0].edge ^= e; 335 } 336 337 static inline void 338 add_edge(struct oedge *o, uint32_t e, 339 uint32_t v0, uint32_t v1, uint32_t v2) 340 { 341 342 add_remove_edge(o, 1, e, v0, v1, v2); 343 } 344 345 static inline void 346 remove_vertex(struct state *state, uint32_t v0) 347 { 348 uint32_t e, v1, v2; 349 struct oedge *o = state->oedges; 350 351 if (o[v0].degree == 1) { 352 e = o[v0].edge; 353 v1 = o[v0].verts[0]; 354 v2 = o[v0].verts[1]; 355 o[v0].degree = 0; 356 add_remove_edge(o, -1, e, v1, v0, v2); 357 add_remove_edge(o, -1, e, v2, v0, v1); 358 state->output_order[--state->output_index] = e; 359 } 360 } 361 362 static int 363 build_graph(struct cdbw *cdbw, struct state *state) 364 { 365 struct key_hash_head *head; 366 struct key_hash *key_hash; 367 struct edge *e; 368 uint32_t hashes[3]; 369 size_t i; 370 371 memset(state->oedges, 0, sizeof(struct oedge) * state->entries); 372 373 e = state->edges; 374 for (i = 0; i < cdbw->hash_size; ++i) { 375 head = &cdbw->hash[i]; 376 SLIST_FOREACH(key_hash, head, link) { 377 e->idx = key_hash->idx; 378 mi_vector_hash(key_hash->key, key_hash->keylen, 379 state->seed, hashes); 380 e->left = hashes[0] % state->entries; 381 e->middle = hashes[1] % state->entries; 382 e->right = hashes[2] % state->entries; 383 384 if (e->left == e->middle) 385 return -1; 386 add_edge(state->oedges, e - state->edges, 387 e->right, e->left, e->middle); 388 if (e->left == e->right) 389 return -1; 390 add_edge(state->oedges, e - state->edges, 391 e->middle, e->left, e->right); 392 if (e->middle == e->right) 393 return -1; 394 add_edge(state->oedges, e - state->edges, 395 e->left, e->middle, e->right); 396 397 ++e; 398 } 399 } 400 401 state->output_index = state->keys; 402 for (i = 0; i < state->entries; ++i) 403 remove_vertex(state, i); 404 405 i = state->keys; 406 while (i > 0 && i > state->output_index) { 407 --i; 408 e = state->edges + state->output_order[i]; 409 remove_vertex(state, e->left); 410 remove_vertex(state, e->middle); 411 remove_vertex(state, e->right); 412 } 413 414 return state->output_index == 0 ? 0 : -1; 415 } 416 417 static void 418 assign_nodes(struct state *state) 419 { 420 struct edge *e; 421 size_t i; 422 423 for (i = 0; i < state->keys; ++i) { 424 e = state->edges + state->output_order[i]; 425 426 if (!state->visited[e->left]) { 427 state->g[e->left] = 428 (2 * state->data_entries + e->idx 429 - state->g[e->middle] - state->g[e->right]) 430 % state->data_entries; 431 } else if (!state->visited[e->middle]) { 432 state->g[e->middle] = 433 (2 * state->data_entries + e->idx 434 - state->g[e->left] - state->g[e->right]) 435 % state->data_entries; 436 } else { 437 state->g[e->right] = 438 (2 * state->data_entries + e->idx 439 - state->g[e->left] - state->g[e->middle]) 440 % state->data_entries; 441 } 442 state->visited[e->left] = 1; 443 state->visited[e->middle] = 1; 444 state->visited[e->right] = 1; 445 } 446 } 447 448 static size_t 449 compute_size(uint32_t size) 450 { 451 if (size < 0x100) 452 return 1; 453 else if (size < 0x10000) 454 return 2; 455 else 456 return 4; 457 } 458 459 #define COND_FLUSH_BUFFER(n) do { \ 460 if (__predict_false(cur_pos + (n) >= sizeof(buf))) { \ 461 ret = write(fd, buf, cur_pos); \ 462 if (ret == -1 || (size_t)ret != cur_pos) \ 463 return -1; \ 464 cur_pos = 0; \ 465 } \ 466 } while (/* CONSTCOND */ 0) 467 468 static int 469 print_hash(struct cdbw *cdbw, struct state *state, int fd, const char *descr) 470 { 471 uint32_t data_size; 472 uint8_t buf[90000]; 473 size_t i, size, size2, cur_pos; 474 ssize_t ret; 475 476 memcpy(buf, "NBCDB\n\0", 7); 477 buf[7] = 1; 478 strncpy((char *)buf + 8, descr, 16); 479 le32enc(buf + 24, cdbw->data_size); 480 le32enc(buf + 28, cdbw->data_counter); 481 le32enc(buf + 32, state->entries); 482 le32enc(buf + 36, state->seed); 483 cur_pos = 40; 484 485 size = compute_size(state->entries); 486 for (i = 0; i < state->entries; ++i) { 487 COND_FLUSH_BUFFER(4); 488 le32enc(buf + cur_pos, state->g[i]); 489 cur_pos += size; 490 } 491 size2 = compute_size(cdbw->data_size); 492 size = size * state->entries % size2; 493 if (size != 0) { 494 size = size2 - size; 495 COND_FLUSH_BUFFER(4); 496 le32enc(buf + cur_pos, 0); 497 cur_pos += size; 498 } 499 for (data_size = 0, i = 0; i < cdbw->data_counter; ++i) { 500 COND_FLUSH_BUFFER(4); 501 le32enc(buf + cur_pos, data_size); 502 cur_pos += size2; 503 data_size += cdbw->data_len[i]; 504 } 505 COND_FLUSH_BUFFER(4); 506 le32enc(buf + cur_pos, data_size); 507 cur_pos += size2; 508 509 for (i = 0; i < cdbw->data_counter; ++i) { 510 COND_FLUSH_BUFFER(cdbw->data_len[i]); 511 if (cdbw->data_len[i] < sizeof(buf)) { 512 memcpy(buf + cur_pos, cdbw->data_ptr[i], 513 cdbw->data_len[i]); 514 cur_pos += cdbw->data_len[i]; 515 } else { 516 ret = write(fd, cdbw->data_ptr[i], cdbw->data_len[i]); 517 if (ret == -1 || (size_t)ret != cdbw->data_len[i]) 518 return -1; 519 } 520 } 521 if (cur_pos != 0) { 522 ret = write(fd, buf, cur_pos); 523 if (ret == -1 || (size_t)ret != cur_pos) 524 return -1; 525 } 526 return 0; 527 } 528 529 int 530 cdbw_output(struct cdbw *cdbw, int fd, const char descr[16], 531 uint32_t (*seedgen)(void)) 532 { 533 struct state state; 534 int rv; 535 536 if (cdbw->data_counter == 0 || cdbw->key_counter == 0) { 537 state.entries = 0; 538 state.seed = 0; 539 print_hash(cdbw, &state, fd, descr); 540 return 0; 541 } 542 543 #if HAVE_NBTOOL_CONFIG_H 544 if (seedgen == NULL) 545 seedgen = cdbw_stable_seeder; 546 #else 547 if (seedgen == NULL) 548 seedgen = arc4random; 549 #endif 550 551 rv = 0; 552 553 state.keys = cdbw->key_counter; 554 state.data_entries = cdbw->data_counter; 555 state.entries = state.keys + (state.keys + 3) / 4; 556 if (state.entries < 10) 557 state.entries = 10; 558 559 #define NALLOC(var, n) var = calloc(sizeof(*var), n) 560 NALLOC(state.g, state.entries); 561 NALLOC(state.visited, state.entries); 562 NALLOC(state.oedges, state.entries); 563 NALLOC(state.edges, state.keys); 564 NALLOC(state.output_order, state.keys); 565 #undef NALLOC 566 567 if (state.g == NULL || state.visited == NULL || state.oedges == NULL || 568 state.edges == NULL || state.output_order == NULL) { 569 rv = -1; 570 goto release; 571 } 572 573 state.seed = 0; 574 do { 575 if (seedgen == cdbw_stable_seeder) 576 ++state.seed; 577 else 578 state.seed = (*seedgen)(); 579 } while (build_graph(cdbw, &state)); 580 581 assign_nodes(&state); 582 rv = print_hash(cdbw, &state, fd, descr); 583 584 release: 585 free(state.g); 586 free(state.visited); 587 free(state.oedges); 588 free(state.edges); 589 free(state.output_order); 590 591 return rv; 592 } 593