1 /* $OpenBSD: hash_bigkey.c,v 1.19 2015/12/28 22:08:18 mmcc Exp $ */ 2 3 /*- 4 * Copyright (c) 1990, 1993, 1994 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Margo Seltzer. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 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 the 17 * documentation and/or other materials provided with the distribution. 18 * 3. Neither the name of the University nor the names of its contributors 19 * may be used to endorse or promote products derived from this software 20 * without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35 /* 36 * PACKAGE: hash 37 * DESCRIPTION: 38 * Big key/data handling for the hashing package. 39 * 40 * ROUTINES: 41 * External 42 * __big_keydata 43 * __big_split 44 * __big_insert 45 * __big_return 46 * __big_delete 47 * __find_last_page 48 * Internal 49 * collect_key 50 * collect_data 51 */ 52 53 #include <errno.h> 54 #include <stdio.h> 55 #include <stdlib.h> 56 #include <string.h> 57 58 #ifdef DEBUG 59 #include <assert.h> 60 #endif 61 62 #include <db.h> 63 #include "hash.h" 64 #include "page.h" 65 #include "extern.h" 66 67 #define MINIMUM(a, b) (((a) < (b)) ? (a) : (b)) 68 69 static int collect_key(HTAB *, BUFHEAD *, int, DBT *, int); 70 static int collect_data(HTAB *, BUFHEAD *, int, int); 71 72 /* 73 * Big_insert 74 * 75 * You need to do an insert and the key/data pair is too big 76 * 77 * Returns: 78 * 0 ==> OK 79 *-1 ==> ERROR 80 */ 81 int 82 __big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val) 83 { 84 u_int16_t *p; 85 int key_size, n, val_size; 86 u_int16_t space, move_bytes, off; 87 char *cp, *key_data, *val_data; 88 89 cp = bufp->page; /* Character pointer of p. */ 90 p = (u_int16_t *)cp; 91 92 key_data = (char *)key->data; 93 key_size = key->size; 94 val_data = (char *)val->data; 95 val_size = val->size; 96 97 /* First move the Key */ 98 for (space = FREESPACE(p) - BIGOVERHEAD; key_size; 99 space = FREESPACE(p) - BIGOVERHEAD) { 100 move_bytes = MINIMUM(space, key_size); 101 off = OFFSET(p) - move_bytes; 102 memmove(cp + off, key_data, move_bytes); 103 key_size -= move_bytes; 104 key_data += move_bytes; 105 n = p[0]; 106 p[++n] = off; 107 p[0] = ++n; 108 FREESPACE(p) = off - PAGE_META(n); 109 OFFSET(p) = off; 110 p[n] = PARTIAL_KEY; 111 bufp = __add_ovflpage(hashp, bufp); 112 if (!bufp) 113 return (-1); 114 n = p[0]; 115 if (!key_size) { 116 space = FREESPACE(p); 117 if (space) { 118 move_bytes = MINIMUM(space, val_size); 119 /* 120 * If the data would fit exactly in the 121 * remaining space, we must overflow it to the 122 * next page; otherwise the invariant that the 123 * data must end on a page with FREESPACE 124 * non-zero would fail. 125 */ 126 if (space == val_size && val_size == val->size) 127 goto toolarge; 128 off = OFFSET(p) - move_bytes; 129 memmove(cp + off, val_data, move_bytes); 130 val_data += move_bytes; 131 val_size -= move_bytes; 132 p[n] = off; 133 p[n - 2] = FULL_KEY_DATA; 134 FREESPACE(p) = FREESPACE(p) - move_bytes; 135 OFFSET(p) = off; 136 } else { 137 toolarge: 138 p[n - 2] = FULL_KEY; 139 } 140 } 141 p = (u_int16_t *)bufp->page; 142 cp = bufp->page; 143 bufp->flags |= BUF_MOD; 144 } 145 146 /* Now move the data */ 147 for (space = FREESPACE(p) - BIGOVERHEAD; val_size; 148 space = FREESPACE(p) - BIGOVERHEAD) { 149 move_bytes = MINIMUM(space, val_size); 150 /* 151 * Here's the hack to make sure that if the data ends on the 152 * same page as the key ends, FREESPACE is at least one. 153 */ 154 if (space == val_size && val_size == val->size) 155 move_bytes--; 156 off = OFFSET(p) - move_bytes; 157 memmove(cp + off, val_data, move_bytes); 158 val_size -= move_bytes; 159 val_data += move_bytes; 160 n = p[0]; 161 p[++n] = off; 162 p[0] = ++n; 163 FREESPACE(p) = off - PAGE_META(n); 164 OFFSET(p) = off; 165 if (val_size) { 166 p[n] = FULL_KEY; 167 bufp = __add_ovflpage(hashp, bufp); 168 if (!bufp) 169 return (-1); 170 cp = bufp->page; 171 p = (u_int16_t *)cp; 172 } else 173 p[n] = FULL_KEY_DATA; 174 bufp->flags |= BUF_MOD; 175 } 176 return (0); 177 } 178 179 /* 180 * Called when bufp's page contains a partial key (index should be 1) 181 * 182 * All pages in the big key/data pair except bufp are freed. We cannot 183 * free bufp because the page pointing to it is lost and we can't get rid 184 * of its pointer. 185 * 186 * Returns: 187 * 0 => OK 188 *-1 => ERROR 189 */ 190 int 191 __big_delete(HTAB *hashp, BUFHEAD *bufp) 192 { 193 BUFHEAD *last_bfp, *rbufp; 194 u_int16_t *bp, pageno; 195 int key_done, n; 196 197 rbufp = bufp; 198 last_bfp = NULL; 199 bp = (u_int16_t *)bufp->page; 200 pageno = 0; 201 key_done = 0; 202 203 while (!key_done || (bp[2] != FULL_KEY_DATA)) { 204 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) 205 key_done = 1; 206 207 /* 208 * If there is freespace left on a FULL_KEY_DATA page, then 209 * the data is short and fits entirely on this page, and this 210 * is the last page. 211 */ 212 if (bp[2] == FULL_KEY_DATA && FREESPACE(bp)) 213 break; 214 pageno = bp[bp[0] - 1]; 215 rbufp->flags |= BUF_MOD; 216 rbufp = __get_buf(hashp, pageno, rbufp, 0); 217 if (last_bfp) 218 __free_ovflpage(hashp, last_bfp); 219 last_bfp = rbufp; 220 if (!rbufp) 221 return (-1); /* Error. */ 222 bp = (u_int16_t *)rbufp->page; 223 } 224 225 /* 226 * If we get here then rbufp points to the last page of the big 227 * key/data pair. Bufp points to the first one -- it should now be 228 * empty pointing to the next page after this pair. Can't free it 229 * because we don't have the page pointing to it. 230 */ 231 232 /* This is information from the last page of the pair. */ 233 n = bp[0]; 234 pageno = bp[n - 1]; 235 236 /* Now, bp is the first page of the pair. */ 237 bp = (u_int16_t *)bufp->page; 238 if (n > 2) { 239 /* There is an overflow page. */ 240 bp[1] = pageno; 241 bp[2] = OVFLPAGE; 242 bufp->ovfl = rbufp->ovfl; 243 } else 244 /* This is the last page. */ 245 bufp->ovfl = NULL; 246 n -= 2; 247 bp[0] = n; 248 FREESPACE(bp) = hashp->BSIZE - PAGE_META(n); 249 OFFSET(bp) = hashp->BSIZE; 250 251 bufp->flags |= BUF_MOD; 252 if (rbufp) 253 __free_ovflpage(hashp, rbufp); 254 if (last_bfp && last_bfp != rbufp) 255 __free_ovflpage(hashp, last_bfp); 256 257 hashp->NKEYS--; 258 return (0); 259 } 260 /* 261 * Returns: 262 * 0 = key not found 263 * -1 = get next overflow page 264 * -2 means key not found and this is big key/data 265 * -3 error 266 */ 267 int 268 __find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size) 269 { 270 u_int16_t *bp; 271 char *p; 272 int ksize; 273 u_int16_t bytes; 274 char *kkey; 275 276 bp = (u_int16_t *)bufp->page; 277 p = bufp->page; 278 ksize = size; 279 kkey = key; 280 281 for (bytes = hashp->BSIZE - bp[ndx]; 282 bytes <= size && bp[ndx + 1] == PARTIAL_KEY; 283 bytes = hashp->BSIZE - bp[ndx]) { 284 if (memcmp(p + bp[ndx], kkey, bytes)) 285 return (-2); 286 kkey += bytes; 287 ksize -= bytes; 288 bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0); 289 if (!bufp) 290 return (-3); 291 p = bufp->page; 292 bp = (u_int16_t *)p; 293 ndx = 1; 294 } 295 296 if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) { 297 #ifdef HASH_STATISTICS 298 ++hash_collisions; 299 #endif 300 return (-2); 301 } else 302 return (ndx); 303 } 304 305 /* 306 * Given the buffer pointer of the first overflow page of a big pair, 307 * find the end of the big pair 308 * 309 * This will set bpp to the buffer header of the last page of the big pair. 310 * It will return the pageno of the overflow page following the last page 311 * of the pair; 0 if there isn't any (i.e. big pair is the last key in the 312 * bucket) 313 */ 314 u_int16_t 315 __find_last_page(HTAB *hashp, BUFHEAD **bpp) 316 { 317 BUFHEAD *bufp; 318 u_int16_t *bp, pageno; 319 int n; 320 321 bufp = *bpp; 322 bp = (u_int16_t *)bufp->page; 323 for (;;) { 324 n = bp[0]; 325 326 /* 327 * This is the last page if: the tag is FULL_KEY_DATA and 328 * either only 2 entries OVFLPAGE marker is explicit there 329 * is freespace on the page. 330 */ 331 if (bp[2] == FULL_KEY_DATA && 332 ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp)))) 333 break; 334 335 pageno = bp[n - 1]; 336 bufp = __get_buf(hashp, pageno, bufp, 0); 337 if (!bufp) 338 return (0); /* Need to indicate an error! */ 339 bp = (u_int16_t *)bufp->page; 340 } 341 342 *bpp = bufp; 343 if (bp[0] > 2) 344 return (bp[3]); 345 else 346 return (0); 347 } 348 349 /* 350 * Return the data for the key/data pair that begins on this page at this 351 * index (index should always be 1). 352 */ 353 int 354 __big_return(HTAB *hashp, BUFHEAD *bufp, int ndx, DBT *val, int set_current) 355 { 356 BUFHEAD *save_p; 357 u_int16_t *bp, len, off, save_addr; 358 char *tp; 359 360 bp = (u_int16_t *)bufp->page; 361 while (bp[ndx + 1] == PARTIAL_KEY) { 362 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 363 if (!bufp) 364 return (-1); 365 bp = (u_int16_t *)bufp->page; 366 ndx = 1; 367 } 368 369 if (bp[ndx + 1] == FULL_KEY) { 370 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 371 if (!bufp) 372 return (-1); 373 bp = (u_int16_t *)bufp->page; 374 save_p = bufp; 375 save_addr = save_p->addr; 376 off = bp[1]; 377 len = 0; 378 } else 379 if (!FREESPACE(bp)) { 380 /* 381 * This is a hack. We can't distinguish between 382 * FULL_KEY_DATA that contains complete data or 383 * incomplete data, so we require that if the data 384 * is complete, there is at least 1 byte of free 385 * space left. 386 */ 387 off = bp[bp[0]]; 388 len = bp[1] - off; 389 save_p = bufp; 390 save_addr = bufp->addr; 391 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 392 if (!bufp) 393 return (-1); 394 bp = (u_int16_t *)bufp->page; 395 } else { 396 /* The data is all on one page. */ 397 tp = (char *)bp; 398 off = bp[bp[0]]; 399 val->data = (u_char *)tp + off; 400 val->size = bp[1] - off; 401 if (set_current) { 402 if (bp[0] == 2) { /* No more buckets in 403 * chain */ 404 hashp->cpage = NULL; 405 hashp->cbucket++; 406 hashp->cndx = 1; 407 } else { 408 hashp->cpage = __get_buf(hashp, 409 bp[bp[0] - 1], bufp, 0); 410 if (!hashp->cpage) 411 return (-1); 412 hashp->cndx = 1; 413 if (!((u_int16_t *) 414 hashp->cpage->page)[0]) { 415 hashp->cbucket++; 416 hashp->cpage = NULL; 417 } 418 } 419 } 420 return (0); 421 } 422 423 val->size = (size_t)collect_data(hashp, bufp, (int)len, set_current); 424 if (val->size == (size_t)-1) 425 return (-1); 426 if (save_p->addr != save_addr) { 427 /* We are pretty short on buffers. */ 428 errno = EINVAL; /* OUT OF BUFFERS */ 429 return (-1); 430 } 431 memmove(hashp->tmp_buf, (save_p->page) + off, len); 432 val->data = (u_char *)hashp->tmp_buf; 433 return (0); 434 } 435 /* 436 * Count how big the total datasize is by recursing through the pages. Then 437 * allocate a buffer and copy the data as you recurse up. 438 */ 439 static int 440 collect_data(HTAB *hashp, BUFHEAD *bufp, int len, int set) 441 { 442 u_int16_t *bp; 443 char *p; 444 BUFHEAD *xbp; 445 u_int16_t save_addr; 446 int mylen, totlen; 447 448 p = bufp->page; 449 bp = (u_int16_t *)p; 450 mylen = hashp->BSIZE - bp[1]; 451 save_addr = bufp->addr; 452 453 if (bp[2] == FULL_KEY_DATA) { /* End of Data */ 454 totlen = len + mylen; 455 free(hashp->tmp_buf); 456 if ((hashp->tmp_buf = (char *)malloc(totlen)) == NULL) 457 return (-1); 458 if (set) { 459 hashp->cndx = 1; 460 if (bp[0] == 2) { /* No more buckets in chain */ 461 hashp->cpage = NULL; 462 hashp->cbucket++; 463 } else { 464 hashp->cpage = 465 __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 466 if (!hashp->cpage) 467 return (-1); 468 else if (!((u_int16_t *)hashp->cpage->page)[0]) { 469 hashp->cbucket++; 470 hashp->cpage = NULL; 471 } 472 } 473 } 474 } else { 475 xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 476 if (!xbp || ((totlen = 477 collect_data(hashp, xbp, len + mylen, set)) < 1)) 478 return (-1); 479 } 480 if (bufp->addr != save_addr) { 481 errno = EINVAL; /* Out of buffers. */ 482 return (-1); 483 } 484 memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen); 485 return (totlen); 486 } 487 488 /* 489 * Fill in the key and data for this big pair. 490 */ 491 int 492 __big_keydata(HTAB *hashp, BUFHEAD *bufp, DBT *key, DBT *val, int set) 493 { 494 key->size = (size_t)collect_key(hashp, bufp, 0, val, set); 495 if (key->size == (size_t)-1) 496 return (-1); 497 key->data = (u_char *)hashp->tmp_key; 498 return (0); 499 } 500 501 /* 502 * Count how big the total key size is by recursing through the pages. Then 503 * collect the data, allocate a buffer and copy the key as you recurse up. 504 */ 505 static int 506 collect_key(HTAB *hashp, BUFHEAD *bufp, int len, DBT *val, int set) 507 { 508 BUFHEAD *xbp; 509 char *p; 510 int mylen, totlen; 511 u_int16_t *bp, save_addr; 512 513 p = bufp->page; 514 bp = (u_int16_t *)p; 515 mylen = hashp->BSIZE - bp[1]; 516 517 save_addr = bufp->addr; 518 totlen = len + mylen; 519 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) { /* End of Key. */ 520 free(hashp->tmp_key); 521 if ((hashp->tmp_key = (char *)malloc(totlen)) == NULL) 522 return (-1); 523 if (__big_return(hashp, bufp, 1, val, set)) 524 return (-1); 525 } else { 526 xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 527 if (!xbp || ((totlen = 528 collect_key(hashp, xbp, totlen, val, set)) < 1)) 529 return (-1); 530 } 531 if (bufp->addr != save_addr) { 532 errno = EINVAL; /* MIS -- OUT OF BUFFERS */ 533 return (-1); 534 } 535 memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen); 536 return (totlen); 537 } 538 539 /* 540 * Returns: 541 * 0 => OK 542 * -1 => error 543 */ 544 int 545 __big_split(HTAB *hashp, 546 BUFHEAD *op, /* Pointer to where to put keys that go in old bucket */ 547 BUFHEAD *np, /* Pointer to new bucket page */ 548 BUFHEAD *big_keyp, /* Pointer to first page containing the big key/data */ 549 int addr, /* Address of big_keyp */ 550 u_int32_t obucket, /* Old Bucket */ 551 SPLIT_RETURN *ret) 552 { 553 BUFHEAD *bp, *tmpp; 554 DBT key, val; 555 u_int32_t change; 556 u_int16_t free_space, n, off, *tp; 557 558 bp = big_keyp; 559 560 /* Now figure out where the big key/data goes */ 561 if (__big_keydata(hashp, big_keyp, &key, &val, 0)) 562 return (-1); 563 change = (__call_hash(hashp, key.data, key.size) != obucket); 564 565 if ((ret->next_addr = __find_last_page(hashp, &big_keyp))) { 566 if (!(ret->nextp = 567 __get_buf(hashp, ret->next_addr, big_keyp, 0))) 568 return (-1); 569 } else 570 ret->nextp = NULL; 571 572 /* Now make one of np/op point to the big key/data pair */ 573 #ifdef DEBUG 574 assert(np->ovfl == NULL); 575 #endif 576 if (change) 577 tmpp = np; 578 else 579 tmpp = op; 580 581 tmpp->flags |= BUF_MOD; 582 #ifdef DEBUG1 583 (void)fprintf(stderr, 584 "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr, 585 (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0)); 586 #endif 587 tmpp->ovfl = bp; /* one of op/np point to big_keyp */ 588 tp = (u_int16_t *)tmpp->page; 589 #ifdef DEBUG 590 assert(FREESPACE(tp) >= OVFLSIZE); 591 #endif 592 n = tp[0]; 593 off = OFFSET(tp); 594 free_space = FREESPACE(tp); 595 tp[++n] = (u_int16_t)addr; 596 tp[++n] = OVFLPAGE; 597 tp[0] = n; 598 OFFSET(tp) = off; 599 FREESPACE(tp) = free_space - OVFLSIZE; 600 601 /* 602 * Finally, set the new and old return values. BIG_KEYP contains a 603 * pointer to the last page of the big key_data pair. Make sure that 604 * big_keyp has no following page (2 elements) or create an empty 605 * following page. 606 */ 607 608 ret->newp = np; 609 ret->oldp = op; 610 611 tp = (u_int16_t *)big_keyp->page; 612 big_keyp->flags |= BUF_MOD; 613 if (tp[0] > 2) { 614 /* 615 * There may be either one or two offsets on this page. If 616 * there is one, then the overflow page is linked on normally 617 * and tp[4] is OVFLPAGE. If there are two, tp[4] contains 618 * the second offset and needs to get stuffed in after the 619 * next overflow page is added. 620 */ 621 n = tp[4]; 622 free_space = FREESPACE(tp); 623 off = OFFSET(tp); 624 tp[0] -= 2; 625 FREESPACE(tp) = free_space + OVFLSIZE; 626 OFFSET(tp) = off; 627 tmpp = __add_ovflpage(hashp, big_keyp); 628 if (!tmpp) 629 return (-1); 630 tp[4] = n; 631 } else 632 tmpp = big_keyp; 633 634 if (change) 635 ret->newp = tmpp; 636 else 637 ret->oldp = tmpp; 638 return (0); 639 } 640