cdbw.c revision 1.2
1 /* $NetBSD: cdbw.c,v 1.2 2012/03/13 21:13:31 christos 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.2 2012/03/13 21:13:31 christos Exp $"); 40 41 #include "namespace.h" 42 43 #include <sys/endian.h> 44 #include <sys/queue.h> 45 #include <assert.h> 46 #include <cdbw.h> 47 #include <stdlib.h> 48 #include <string.h> 49 #include <unistd.h> 50 51 #ifdef __weak_alias 52 __weak_alias(cdbw_close,_cdbw_close) 53 __weak_alias(cdbw_open,_cdbw_open) 54 __weak_alias(cdbw_output,_cdbw_output) 55 __weak_alias(cdbw_put,_cdbw_put) 56 __weak_alias(cdbw_put_data,_cdbw_put_data) 57 __weak_alias(cdbw_put_key,_cdbw_put_key) 58 #endif 59 60 struct key_hash { 61 SLIST_ENTRY(key_hash) link; 62 uint32_t hashes[3]; 63 uint32_t idx; 64 void *key; 65 size_t keylen; 66 }; 67 68 SLIST_HEAD(key_hash_head, key_hash); 69 70 struct cdbw { 71 size_t data_counter; 72 size_t data_allocated; 73 size_t data_size; 74 size_t *data_len; 75 void **data_ptr; 76 77 size_t hash_size; 78 struct key_hash_head *hash; 79 size_t key_counter; 80 }; 81 82 /* Max. data counter that allows the index size to be 32bit. */ 83 static const uint32_t max_data_counter = 0xccccccccU; 84 85 struct cdbw * 86 cdbw_open(void) 87 { 88 struct cdbw *cdbw; 89 size_t i; 90 91 cdbw = calloc(sizeof(*cdbw), 1); 92 if (cdbw == NULL) 93 return NULL; 94 95 cdbw->hash_size = 1024; 96 cdbw->hash = calloc(cdbw->hash_size, sizeof(*cdbw->hash)); 97 if (cdbw->hash == NULL) { 98 free(cdbw); 99 return NULL; 100 } 101 102 for (i = 0; i < cdbw->hash_size; ++i) 103 SLIST_INIT(cdbw->hash + i); 104 105 return cdbw; 106 } 107 108 int 109 cdbw_put(struct cdbw *cdbw, const void *key, size_t keylen, 110 const void *data, size_t datalen) 111 { 112 uint32_t idx; 113 int rv; 114 115 rv = cdbw_put_data(cdbw, data, datalen, &idx); 116 if (rv) 117 return rv; 118 rv = cdbw_put_key(cdbw, key, keylen, idx); 119 if (rv) { 120 --cdbw->data_counter; 121 free(cdbw->data_ptr[cdbw->data_counter]); 122 cdbw->data_size -= datalen; 123 return rv; 124 } 125 return 0; 126 } 127 128 int 129 cdbw_put_data(struct cdbw *cdbw, const void *data, size_t datalen, 130 uint32_t *idx) 131 { 132 133 if (cdbw->data_counter == max_data_counter) 134 return -1; 135 136 if (cdbw->data_size + datalen < cdbw->data_size || 137 cdbw->data_size + datalen > 0xffffffffU) 138 return -1; /* Overflow */ 139 140 if (cdbw->data_allocated == cdbw->data_counter) { 141 void **new_data_ptr; 142 size_t *new_data_len; 143 size_t new_allocated; 144 145 if (cdbw->data_allocated == 0) 146 new_allocated = 256; 147 else 148 new_allocated = cdbw->data_allocated * 2; 149 150 new_data_ptr = realloc(cdbw->data_ptr, 151 sizeof(*cdbw->data_ptr) * new_allocated); 152 if (new_data_ptr == NULL) 153 return -1; 154 cdbw->data_ptr = new_data_ptr; 155 156 new_data_len = realloc(cdbw->data_len, 157 sizeof(*cdbw->data_len) * new_allocated); 158 if (new_data_len == NULL) 159 return -1; 160 cdbw->data_len = new_data_len; 161 162 cdbw->data_allocated = new_allocated; 163 } 164 165 cdbw->data_ptr[cdbw->data_counter] = malloc(datalen); 166 if (cdbw->data_ptr[cdbw->data_counter] == NULL) 167 return -1; 168 memcpy(cdbw->data_ptr[cdbw->data_counter], data, datalen); 169 cdbw->data_len[cdbw->data_counter] = datalen; 170 cdbw->data_size += datalen; 171 _DIAGASSERT(__type_fit(uint32_t, cdbw->data_counter)); 172 *idx = (uint32_t)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 #define unused 0xffffffffU 276 277 struct vertex { 278 uint32_t l_edge, m_edge, r_edge; 279 }; 280 281 struct edge { 282 uint32_t idx; 283 284 uint32_t left, middle, right; 285 uint32_t l_prev, m_prev, l_next; 286 uint32_t r_prev, m_next, r_next; 287 }; 288 289 struct state { 290 uint32_t data_entries; 291 uint32_t entries; 292 uint32_t keys; 293 uint32_t seed; 294 295 uint32_t *g; 296 char *visited; 297 298 struct vertex *verts; 299 struct edge *edges; 300 uint32_t output_index; 301 uint32_t *output_order; 302 }; 303 304 static void 305 remove_vertex(struct state *state, struct vertex *v) 306 { 307 struct edge *e; 308 struct vertex *vl, *vm, *vr; 309 310 if (v->l_edge != unused && v->m_edge != unused) 311 return; 312 if (v->l_edge != unused && v->r_edge != unused) 313 return; 314 if (v->m_edge != unused && v->r_edge != unused) 315 return; 316 if (v->l_edge == unused && v->m_edge == unused && v->r_edge == unused) 317 return; 318 319 if (v->l_edge != unused) { 320 e = &state->edges[v->l_edge]; 321 if (e->l_next != unused) 322 return; 323 } else if (v->m_edge != unused) { 324 e = &state->edges[v->m_edge]; 325 if (e->m_next != unused) 326 return; 327 } else { 328 if (v->r_edge == unused) 329 abort(); 330 e = &state->edges[v->r_edge]; 331 if (e->r_next != unused) 332 return; 333 } 334 335 ptrdiff_t td = e - state->edges; 336 _DIAGASSERT(__type_fit(uint32_t, td)); 337 state->output_order[--state->output_index] = (uint32_t)td; 338 339 vl = &state->verts[e->left]; 340 vm = &state->verts[e->middle]; 341 vr = &state->verts[e->right]; 342 343 if (e->l_prev == unused) 344 vl->l_edge = e->l_next; 345 else 346 state->edges[e->l_prev].l_next = e->l_next; 347 if (e->l_next != unused) 348 state->edges[e->l_next].l_prev = e->l_prev; 349 350 if (e->m_prev == unused) 351 vm->m_edge = e->m_next; 352 else 353 state->edges[e->m_prev].m_next = e->m_next; 354 if (e->m_next != unused) 355 state->edges[e->m_next].m_prev = e->m_prev; 356 357 if (e->r_prev == unused) 358 vr->r_edge = e->r_next; 359 else 360 state->edges[e->r_prev].r_next = e->r_next; 361 if (e->r_next != unused) 362 state->edges[e->r_next].r_prev = e->r_prev; 363 } 364 365 static int 366 build_graph(struct cdbw *cdbw, struct state *state) 367 { 368 struct key_hash_head *head; 369 struct key_hash *key_hash; 370 struct vertex *v; 371 struct edge *e; 372 uint32_t hashes[3], i; 373 374 e = state->edges; 375 for (i = 0; i < cdbw->hash_size; ++i) { 376 head = &cdbw->hash[i]; 377 SLIST_FOREACH(key_hash, head, link) { 378 e->idx = key_hash->idx; 379 mi_vector_hash(key_hash->key, key_hash->keylen, 380 state->seed, hashes); 381 e->left = hashes[0] % state->entries; 382 e->middle = hashes[1] % state->entries; 383 e->right = hashes[2] % state->entries; 384 385 ++e; 386 } 387 } 388 389 for (i = 0; i < state->entries; ++i) { 390 v = state->verts + i; 391 v->l_edge = unused; 392 v->m_edge = unused; 393 v->r_edge = unused; 394 } 395 396 for (i = 0; i < state->keys; ++i) { 397 e = state->edges + i; 398 v = state->verts + e->left; 399 if (v->l_edge != unused) 400 state->edges[v->l_edge].l_prev = i; 401 e->l_next = v->l_edge; 402 e->l_prev = unused; 403 v->l_edge = i; 404 405 v = &state->verts[e->middle]; 406 if (v->m_edge != unused) 407 state->edges[v->m_edge].m_prev = i; 408 e->m_next = v->m_edge; 409 e->m_prev = unused; 410 v->m_edge = i; 411 412 v = &state->verts[e->right]; 413 if (v->r_edge != unused) 414 state->edges[v->r_edge].r_prev = i; 415 e->r_next = v->r_edge; 416 e->r_prev = unused; 417 v->r_edge = i; 418 } 419 420 state->output_index = state->keys; 421 for (i = 0; i < state->entries; ++i) 422 remove_vertex(state, state->verts + i); 423 424 i = state->keys; 425 while (i > 0 && i > state->output_index) { 426 --i; 427 e = state->edges + state->output_order[i]; 428 remove_vertex(state, state->verts + e->left); 429 remove_vertex(state, state->verts + e->middle); 430 remove_vertex(state, state->verts + e->right); 431 } 432 433 return state->output_index == 0 ? 0 : -1; 434 } 435 436 static void 437 assign_nodes(struct state *state) 438 { 439 struct edge *e; 440 size_t i; 441 442 for (i = 0; i < state->keys; ++i) { 443 e = state->edges + state->output_order[i]; 444 445 if (!state->visited[e->left]) { 446 state->g[e->left] = 447 (2 * state->data_entries + e->idx 448 - state->g[e->middle] - state->g[e->right]) 449 % state->data_entries; 450 } else if (!state->visited[e->middle]) { 451 state->g[e->middle] = 452 (2 * state->data_entries + e->idx 453 - state->g[e->left] - state->g[e->right]) 454 % state->data_entries; 455 } else { 456 state->g[e->right] = 457 (2 * state->data_entries + e->idx 458 - state->g[e->left] - state->g[e->middle]) 459 % state->data_entries; 460 } 461 state->visited[e->left] = 1; 462 state->visited[e->middle] = 1; 463 state->visited[e->right] = 1; 464 } 465 } 466 467 static size_t 468 compute_size(uint32_t size) 469 { 470 if (size < 0x100) 471 return 1; 472 else if (size < 0x10000) 473 return 2; 474 else 475 return 4; 476 } 477 478 #define COND_FLUSH_BUFFER(n) do { \ 479 if (__predict_false(cur_pos + (n) >= sizeof(buf))) { \ 480 ret = write(fd, buf, cur_pos); \ 481 if (ret == -1 || (size_t)ret != cur_pos) \ 482 return -1; \ 483 cur_pos = 0; \ 484 } \ 485 } while (/* CONSTCOND */ 0) 486 487 static int 488 print_hash(struct cdbw *cdbw, struct state *state, int fd, const char *descr) 489 { 490 uint32_t data_size; 491 uint8_t buf[90000]; 492 size_t i, size, size2, cur_pos; 493 ssize_t ret; 494 495 memcpy(buf, "NBCDB\n\0", 7); 496 buf[7] = 1; 497 strncpy((char *)buf + 8, descr, 16); 498 _DIAGASSERT(__type_fit(uint32_t, cdbw->data_size)); 499 le32enc(buf + 24, (uint32_t)cdbw->data_size); 500 _DIAGASSERT(__type_fit(uint32_t, cdbw->data_counter)); 501 le32enc(buf + 28, (uint32_t)cdbw->data_counter); 502 le32enc(buf + 32, state->entries); 503 le32enc(buf + 36, state->seed); 504 cur_pos = 40; 505 506 size = compute_size(state->entries); 507 for (i = 0; i < state->entries; ++i) { 508 COND_FLUSH_BUFFER(4); 509 le32enc(buf + cur_pos, state->g[i]); 510 cur_pos += size; 511 } 512 _DIAGASSERT(__type_fit(uint32_t, cdbw->data_counter)); 513 size2 = compute_size((uint32_t)cdbw->data_size); 514 size = size * state->entries % size2; 515 if (size != 0) { 516 size = size2 - size; 517 COND_FLUSH_BUFFER(4); 518 le32enc(buf + cur_pos, 0); 519 cur_pos += size; 520 } 521 for (data_size = 0, i = 0; i < cdbw->data_counter; ++i) { 522 COND_FLUSH_BUFFER(4); 523 le32enc(buf + cur_pos, data_size); 524 cur_pos += size2; 525 _DIAGASSERT(__type_fit(uint32_t, 526 data_size + cdbw->data_len[i])); 527 data_size += (uint32_t)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 (seedgen == NULL) 568 seedgen = arc4random; 569 570 rv = 0; 571 572 _DIAGASSERT(__type_fit(uint32_t, cdbw->key_counter)); 573 state.keys = (uint32_t)cdbw->key_counter; 574 _DIAGASSERT(__type_fit(uint32_t, cdbw->key_counter)); 575 state.data_entries = (uint32_t)cdbw->data_counter; 576 state.entries = state.keys + (state.keys + 3) / 4; 577 if (state.entries < 10) 578 state.entries = 10; 579 580 #define NALLOC(var, n) var = calloc(sizeof(*var), n) 581 NALLOC(state.g, state.entries); 582 NALLOC(state.visited, state.entries); 583 NALLOC(state.verts, state.entries); 584 NALLOC(state.edges, state.entries); 585 NALLOC(state.output_order, state.keys); 586 #undef NALLOC 587 588 if (state.g == NULL || state.visited == NULL || state.verts == NULL || 589 state.edges == NULL || state.output_order == NULL) { 590 rv = -1; 591 goto release; 592 } 593 594 do { 595 state.seed = (*seedgen)(); 596 } while (build_graph(cdbw, &state)); 597 598 assign_nodes(&state); 599 rv = print_hash(cdbw, &state, fd, descr); 600 601 release: 602 free(state.g); 603 free(state.visited); 604 free(state.verts); 605 free(state.edges); 606 free(state.output_order); 607 608 return rv; 609 } 610
Indexes created Wed Sep 24 05:09:52 GMT 2025