cdbw.c revision 1.4
1 /* $NetBSD: cdbw.c,v 1.4 2012/06/03 21:02:50 joerg Exp $ */ 2 /*- 3 * Copyright (c) 2009, 2010 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. 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.4 2012/06/03 21:02:50 joerg 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 #define unused 0xffffffffU 282 283 struct vertex { 284 uint32_t l_edge, m_edge, r_edge; 285 }; 286 287 struct edge { 288 uint32_t idx; 289 290 uint32_t left, middle, right; 291 uint32_t l_prev, m_prev, l_next; 292 uint32_t r_prev, m_next, r_next; 293 }; 294 295 struct state { 296 uint32_t data_entries; 297 uint32_t entries; 298 uint32_t keys; 299 uint32_t seed; 300 301 uint32_t *g; 302 char *visited; 303 304 struct vertex *verts; 305 struct edge *edges; 306 uint32_t output_index; 307 uint32_t *output_order; 308 }; 309 310 static void 311 remove_vertex(struct state *state, struct vertex *v) 312 { 313 struct edge *e; 314 struct vertex *vl, *vm, *vr; 315 316 if (v->l_edge != unused && v->m_edge != unused) 317 return; 318 if (v->l_edge != unused && v->r_edge != unused) 319 return; 320 if (v->m_edge != unused && v->r_edge != unused) 321 return; 322 if (v->l_edge == unused && v->m_edge == unused && v->r_edge == unused) 323 return; 324 325 if (v->l_edge != unused) { 326 e = &state->edges[v->l_edge]; 327 if (e->l_next != unused) 328 return; 329 } else if (v->m_edge != unused) { 330 e = &state->edges[v->m_edge]; 331 if (e->m_next != unused) 332 return; 333 } else { 334 if (v->r_edge == unused) 335 abort(); 336 e = &state->edges[v->r_edge]; 337 if (e->r_next != unused) 338 return; 339 } 340 341 state->output_order[--state->output_index] = e - state->edges; 342 343 vl = &state->verts[e->left]; 344 vm = &state->verts[e->middle]; 345 vr = &state->verts[e->right]; 346 347 if (e->l_prev == unused) 348 vl->l_edge = e->l_next; 349 else 350 state->edges[e->l_prev].l_next = e->l_next; 351 if (e->l_next != unused) 352 state->edges[e->l_next].l_prev = e->l_prev; 353 354 if (e->m_prev == unused) 355 vm->m_edge = e->m_next; 356 else 357 state->edges[e->m_prev].m_next = e->m_next; 358 if (e->m_next != unused) 359 state->edges[e->m_next].m_prev = e->m_prev; 360 361 if (e->r_prev == unused) 362 vr->r_edge = e->r_next; 363 else 364 state->edges[e->r_prev].r_next = e->r_next; 365 if (e->r_next != unused) 366 state->edges[e->r_next].r_prev = e->r_prev; 367 } 368 369 static int 370 build_graph(struct cdbw *cdbw, struct state *state) 371 { 372 struct key_hash_head *head; 373 struct key_hash *key_hash; 374 struct vertex *v; 375 struct edge *e; 376 uint32_t hashes[3]; 377 size_t i; 378 379 e = state->edges; 380 for (i = 0; i < cdbw->hash_size; ++i) { 381 head = &cdbw->hash[i]; 382 SLIST_FOREACH(key_hash, head, link) { 383 e->idx = key_hash->idx; 384 mi_vector_hash(key_hash->key, key_hash->keylen, 385 state->seed, hashes); 386 e->left = hashes[0] % state->entries; 387 e->middle = hashes[1] % state->entries; 388 e->right = hashes[2] % state->entries; 389 390 ++e; 391 } 392 } 393 394 for (i = 0; i < state->entries; ++i) { 395 v = state->verts + i; 396 v->l_edge = unused; 397 v->m_edge = unused; 398 v->r_edge = unused; 399 } 400 401 for (i = 0; i < state->keys; ++i) { 402 e = state->edges + i; 403 v = state->verts + e->left; 404 if (v->l_edge != unused) 405 state->edges[v->l_edge].l_prev = i; 406 e->l_next = v->l_edge; 407 e->l_prev = unused; 408 v->l_edge = i; 409 410 v = &state->verts[e->middle]; 411 if (v->m_edge != unused) 412 state->edges[v->m_edge].m_prev = i; 413 e->m_next = v->m_edge; 414 e->m_prev = unused; 415 v->m_edge = i; 416 417 v = &state->verts[e->right]; 418 if (v->r_edge != unused) 419 state->edges[v->r_edge].r_prev = i; 420 e->r_next = v->r_edge; 421 e->r_prev = unused; 422 v->r_edge = i; 423 } 424 425 state->output_index = state->keys; 426 for (i = 0; i < state->entries; ++i) 427 remove_vertex(state, state->verts + i); 428 429 i = state->keys; 430 while (i > 0 && i > state->output_index) { 431 --i; 432 e = state->edges + state->output_order[i]; 433 remove_vertex(state, state->verts + e->left); 434 remove_vertex(state, state->verts + e->middle); 435 remove_vertex(state, state->verts + e->right); 436 } 437 438 return state->output_index == 0 ? 0 : -1; 439 } 440 441 static void 442 assign_nodes(struct state *state) 443 { 444 struct edge *e; 445 size_t i; 446 447 for (i = 0; i < state->keys; ++i) { 448 e = state->edges + state->output_order[i]; 449 450 if (!state->visited[e->left]) { 451 state->g[e->left] = 452 (2 * state->data_entries + e->idx 453 - state->g[e->middle] - state->g[e->right]) 454 % state->data_entries; 455 } else if (!state->visited[e->middle]) { 456 state->g[e->middle] = 457 (2 * state->data_entries + e->idx 458 - state->g[e->left] - state->g[e->right]) 459 % state->data_entries; 460 } else { 461 state->g[e->right] = 462 (2 * state->data_entries + e->idx 463 - state->g[e->left] - state->g[e->middle]) 464 % state->data_entries; 465 } 466 state->visited[e->left] = 1; 467 state->visited[e->middle] = 1; 468 state->visited[e->right] = 1; 469 } 470 } 471 472 static size_t 473 compute_size(uint32_t size) 474 { 475 if (size < 0x100) 476 return 1; 477 else if (size < 0x10000) 478 return 2; 479 else 480 return 4; 481 } 482 483 #define COND_FLUSH_BUFFER(n) do { \ 484 if (__predict_false(cur_pos + (n) >= sizeof(buf))) { \ 485 ret = write(fd, buf, cur_pos); \ 486 if (ret == -1 || (size_t)ret != cur_pos) \ 487 return -1; \ 488 cur_pos = 0; \ 489 } \ 490 } while (/* CONSTCOND */ 0) 491 492 static int 493 print_hash(struct cdbw *cdbw, struct state *state, int fd, const char *descr) 494 { 495 uint32_t data_size; 496 uint8_t buf[90000]; 497 size_t i, size, size2, cur_pos; 498 ssize_t ret; 499 500 memcpy(buf, "NBCDB\n\0", 7); 501 buf[7] = 1; 502 strncpy((char *)buf + 8, descr, 16); 503 le32enc(buf + 24, cdbw->data_size); 504 le32enc(buf + 28, cdbw->data_counter); 505 le32enc(buf + 32, state->entries); 506 le32enc(buf + 36, state->seed); 507 cur_pos = 40; 508 509 size = compute_size(state->entries); 510 for (i = 0; i < state->entries; ++i) { 511 COND_FLUSH_BUFFER(4); 512 le32enc(buf + cur_pos, state->g[i]); 513 cur_pos += size; 514 } 515 size2 = compute_size(cdbw->data_size); 516 size = size * state->entries % size2; 517 if (size != 0) { 518 size = size2 - size; 519 COND_FLUSH_BUFFER(4); 520 le32enc(buf + cur_pos, 0); 521 cur_pos += size; 522 } 523 for (data_size = 0, i = 0; i < cdbw->data_counter; ++i) { 524 COND_FLUSH_BUFFER(4); 525 le32enc(buf + cur_pos, data_size); 526 cur_pos += size2; 527 data_size += cdbw->data_len[i]; 528 } 529 COND_FLUSH_BUFFER(4); 530 le32enc(buf + cur_pos, data_size); 531 cur_pos += size2; 532 533 for (i = 0; i < cdbw->data_counter; ++i) { 534 COND_FLUSH_BUFFER(cdbw->data_len[i]); 535 if (cdbw->data_len[i] < sizeof(buf)) { 536 memcpy(buf + cur_pos, cdbw->data_ptr[i], 537 cdbw->data_len[i]); 538 cur_pos += cdbw->data_len[i]; 539 } else { 540 ret = write(fd, cdbw->data_ptr[i], cdbw->data_len[i]); 541 if (ret == -1 || (size_t)ret != cdbw->data_len[i]) 542 return -1; 543 } 544 } 545 if (cur_pos != 0) { 546 ret = write(fd, buf, cur_pos); 547 if (ret == -1 || (size_t)ret != cur_pos) 548 return -1; 549 } 550 return 0; 551 } 552 553 int 554 cdbw_output(struct cdbw *cdbw, int fd, const char descr[16], 555 uint32_t (*seedgen)(void)) 556 { 557 struct state state; 558 int rv; 559 560 if (cdbw->data_counter == 0 || cdbw->key_counter == 0) { 561 state.entries = 0; 562 state.seed = 0; 563 print_hash(cdbw, &state, fd, descr); 564 return 0; 565 } 566 567 #if HAVE_NBTOOL_CONFIG_H 568 if (seedgen == NULL) 569 seedgen = cdbw_stable_seeder; 570 #else 571 if (seedgen == NULL) 572 seedgen = arc4random; 573 #endif 574 575 rv = 0; 576 577 state.keys = cdbw->key_counter; 578 state.data_entries = cdbw->data_counter; 579 state.entries = state.keys + (state.keys + 3) / 4; 580 if (state.entries < 10) 581 state.entries = 10; 582 583 #define NALLOC(var, n) var = calloc(sizeof(*var), n) 584 NALLOC(state.g, state.entries); 585 NALLOC(state.visited, state.entries); 586 NALLOC(state.verts, state.entries); 587 NALLOC(state.edges, state.entries); 588 NALLOC(state.output_order, state.keys); 589 #undef NALLOC 590 591 if (state.g == NULL || state.visited == NULL || state.verts == NULL || 592 state.edges == NULL || state.output_order == NULL) { 593 rv = -1; 594 goto release; 595 } 596 597 state.seed = 0; 598 do { 599 if (seedgen == cdbw_stable_seeder) 600 ++state.seed; 601 else 602 state.seed = (*seedgen)(); 603 } while (build_graph(cdbw, &state)); 604 605 assign_nodes(&state); 606 rv = print_hash(cdbw, &state, fd, descr); 607 608 release: 609 free(state.g); 610 free(state.visited); 611 free(state.verts); 612 free(state.edges); 613 free(state.output_order); 614 615 return rv; 616 } 617
Indexes created Fri Sep 26 20:09:58 GMT 2025