1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 /* Copyright (c) 1983, 1984, 1985, 1986, 1987, 1988, 1989 AT&T */ 28 /* All Rights Reserved */ 29 30 /* 31 * Portions of this source code were derived from Berkeley 32 * under license from the Regents of the University of 33 * California. 34 */ 35 36 #pragma ident "%Z%%M% %I% %E% SMI" 37 38 #include <rpcsvc/dbm.h> 39 #include <sys/types.h> 40 #include <rpc/trace.h> 41 #include <sys/stat.h> 42 #include <string.h> 43 #include <unistd.h> 44 #include <stdlib.h> 45 #include <fcntl.h> 46 #include <stdio.h> 47 #include <errno.h> 48 49 #if defined(sparc) 50 #define _FSTAT _fstat 51 extern int _fstat(int, struct stat *); 52 #else /* !sparc */ 53 #define _FSTAT fstat 54 #endif /* sparc */ 55 56 57 void dbm_access(long); 58 void delitem(char *, int); 59 void chkblk(char *); 60 int additem(char *, datum); 61 int getbit(void); 62 int setbit(void); 63 int cmpdatum(datum, datum); 64 65 int 66 dbminit(file) 67 char *file; 68 { 69 struct stat statb; 70 71 trace1(TR_dbminit, 0); 72 dbrdonly = 0; 73 if (strlcpy(pagbuf, file, sizeof (pagbuf)) >= sizeof (pagbuf) || 74 strlcat(pagbuf, ".pag", sizeof (pagbuf)) >= sizeof (pagbuf)) { 75 /* 76 * file.pag does not fit into pagbuf. 77 * fails with ENAMETOOLONG. 78 */ 79 trace1(TR_dbminit, 1); 80 errno = ENAMETOOLONG; 81 return (-1); 82 } 83 pagf = open(pagbuf, 2); 84 if (pagf < 0) { 85 pagf = open(pagbuf, 0); 86 dbrdonly = 1; 87 } 88 /* 89 * We know this won't overflow so it is safe to ignore the 90 * return value; we use strl* to prevent false hits in 91 * code sweeps. 92 */ 93 (void) strlcpy(pagbuf, file, sizeof (pagbuf)); 94 (void) strlcat(pagbuf, ".dir", sizeof (pagbuf)); 95 dirf = open(pagbuf, 2); 96 if (dirf < 0) { 97 dirf = open(pagbuf, 0); 98 dbrdonly = 1; 99 } 100 if (pagf < 0 || dirf < 0) { 101 trace1(TR_dbminit, 1); 102 return (-1); 103 } 104 _FSTAT(dirf, &statb); 105 maxbno = statb.st_size*BYTESIZ-1; 106 trace1(TR_dbminit, 1); 107 return (0); 108 } 109 110 static long oldb1 = -1; 111 static long oldb2 = -1; 112 113 /* Avoid using cached data for subsequent accesses. */ 114 int 115 dbmflush() 116 { 117 trace1(TR_dbmflush, 0); 118 oldb1 = -1; 119 oldb2 = -1; 120 trace1(TR_dbmflush, 1); 121 return (0); 122 } 123 124 /* Clean up after ourself. */ 125 int 126 dbmclose() 127 { 128 trace1(TR_dbmclose, 0); 129 (void) close(pagf); 130 (void) close(dirf); 131 bitno = 0; 132 maxbno = 0; 133 blkno = 0; 134 hmask = 0; 135 oldb1 = -1; 136 oldb2 = -1; 137 trace1(TR_dbmclose, 1); 138 return (0); 139 } 140 141 long 142 forder(key) 143 datum key; 144 { 145 long hash; 146 147 trace1(TR_forder, 0); 148 hash = calchash(key); 149 for (hmask = 0; ; hmask = (hmask<<1) + 1) { 150 blkno = hash & hmask; 151 bitno = blkno + hmask; 152 if (getbit() == 0) 153 break; 154 } 155 trace1(TR_forder, 1); 156 return (blkno); 157 } 158 159 datum 160 fetch(key) 161 datum key; 162 { 163 int i; 164 datum item; 165 166 trace1(TR_fetch, 0); 167 dbm_access(calchash(key)); 168 for (i = 0; ; i += 2) { 169 item = makdatum(pagbuf, i); 170 if (item.dptr == NULL) { 171 trace1(TR_fetch, 1); 172 return (item); 173 } 174 if (cmpdatum(key, item) == 0) { 175 item = makdatum(pagbuf, i+1); 176 if (item.dptr == NULL) 177 (void) printf("items not in pairs\n"); 178 trace1(TR_fetch, 1); 179 return (item); 180 } 181 } 182 } 183 184 int 185 delete(key) 186 datum key; 187 { 188 int i; 189 datum item; 190 191 trace1(TR_delete, 0); 192 if (dbrdonly) { 193 trace1(TR_delete, 1); 194 return (-1); 195 } 196 dbm_access(calchash(key)); 197 for (i = 0; ; i += 2) { 198 item = makdatum(pagbuf, i); 199 if (item.dptr == NULL) { 200 trace1(TR_delete, 1); 201 return (-1); 202 } 203 if (cmpdatum(key, item) == 0) { 204 delitem(pagbuf, i); 205 delitem(pagbuf, i); 206 break; 207 } 208 } 209 (void) lseek(pagf, blkno*PBLKSIZ, 0); 210 (void) write(pagf, pagbuf, PBLKSIZ); 211 trace1(TR_delete, 1); 212 return (0); 213 } 214 215 int 216 store(key, dat) 217 datum key, dat; 218 { 219 int i; 220 datum item; 221 char ovfbuf[PBLKSIZ]; 222 223 trace1(TR_store, 0); 224 if (dbrdonly) { 225 trace1(TR_store, 1); 226 return (-1); 227 } 228 loop: 229 dbm_access(calchash(key)); 230 for (i = 0; ; i += 2) { 231 item = makdatum(pagbuf, i); 232 if (item.dptr == NULL) 233 break; 234 if (cmpdatum(key, item) == 0) { 235 delitem(pagbuf, i); 236 delitem(pagbuf, i); 237 break; 238 } 239 } 240 i = additem(pagbuf, key); 241 if (i < 0) 242 goto split; 243 if (additem(pagbuf, dat) < 0) { 244 delitem(pagbuf, i); 245 goto split; 246 } 247 (void) lseek(pagf, blkno*PBLKSIZ, 0); 248 (void) write(pagf, pagbuf, PBLKSIZ); 249 trace1(TR_store, 1); 250 return (0); 251 252 split: 253 if (key.dsize + dat.dsize + 3 * sizeof (short) >= PBLKSIZ) { 254 (void) printf("entry too big\n"); 255 trace1(TR_store, 1); 256 return (-1); 257 } 258 (void) memset((char *)&ovfbuf, 0, PBLKSIZ); 259 for (i = 0; ; ) { 260 item = makdatum(pagbuf, i); 261 if (item.dptr == NULL) 262 break; 263 if (calchash(item) & (hmask+1)) { 264 (void) additem(ovfbuf, item); 265 delitem(pagbuf, i); 266 item = makdatum(pagbuf, i); 267 if (item.dptr == NULL) { 268 (void) printf("split not paired\n"); 269 break; 270 } 271 (void) additem(ovfbuf, item); 272 delitem(pagbuf, i); 273 continue; 274 } 275 i += 2; 276 } 277 (void) lseek(pagf, blkno*PBLKSIZ, 0); 278 if (write(pagf, pagbuf, PBLKSIZ) < 0) { 279 trace1(TR_store, 1); 280 return (-1); 281 } 282 (void) lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0); 283 if (write(pagf, ovfbuf, PBLKSIZ) < 0) { 284 trace1(TR_store, 1); 285 return (-1); 286 } 287 if (setbit() < 0) { 288 trace1(TR_store, 1); 289 return (-1); 290 } 291 goto loop; 292 } 293 294 datum 295 firstkey() 296 { 297 datum dummy; 298 299 trace1(TR_firstkey, 0); 300 dummy = firsthash(0L); 301 trace1(TR_firstkey, 1); 302 return (dummy); 303 } 304 305 datum 306 nextkey(key) 307 datum key; 308 { 309 int i; 310 datum item, bitem; 311 long hash; 312 int f; 313 datum dummy; 314 315 trace1(TR_nextkey, 0); 316 #ifdef lint 317 bitem.dptr = NULL; 318 bitem.dsize = 0; 319 #endif /* lint */ 320 hash = calchash(key); 321 dbm_access(hash); 322 f = 1; 323 for (i = 0; ; i += 2) { 324 item = makdatum(pagbuf, i); 325 if (item.dptr == NULL) 326 break; 327 if (cmpdatum(key, item) <= 0) 328 continue; 329 if (f || cmpdatum(bitem, item) < 0) { 330 bitem = item; 331 f = 0; 332 } 333 } 334 if (f == 0) { 335 trace1(TR_nextkey, 1); 336 return (bitem); 337 } 338 hash = hashinc(hash); 339 if (hash == 0) { 340 trace1(TR_nextkey, 1); 341 return (item); 342 } 343 dummy = firsthash(hash); 344 trace1(TR_nextkey, 1); 345 return (dummy); 346 } 347 348 datum 349 firsthash(hash) 350 long hash; 351 { 352 int i; 353 datum item, bitem; 354 355 trace2(TR_firsthash, 0, hash); 356 loop: 357 dbm_access(hash); 358 bitem = makdatum(pagbuf, 0); 359 for (i = 2; ; i += 2) { 360 item = makdatum(pagbuf, i); 361 if (item.dptr == NULL) 362 break; 363 if (cmpdatum(bitem, item) < 0) 364 bitem = item; 365 } 366 if (bitem.dptr != NULL) { 367 trace1(TR_firsthash, 1); 368 return (bitem); 369 } 370 hash = hashinc(hash); 371 if (hash == 0) { 372 trace1(TR_firsthash, 1); 373 return (item); 374 } 375 goto loop; 376 } 377 378 void 379 dbm_access(hash) 380 long hash; 381 { 382 ssize_t readsize; 383 384 trace2(TR_dbm_access, 0, hash); 385 for (hmask = 0; ; hmask = (hmask<<1) + 1) { 386 blkno = hash & hmask; 387 bitno = blkno + hmask; 388 if (getbit() == 0) 389 break; 390 } 391 if (blkno != oldb1) { 392 (void) lseek(pagf, blkno*PBLKSIZ, 0); 393 readsize = read(pagf, pagbuf, PBLKSIZ); 394 if (readsize != PBLKSIZ) { 395 if (readsize < 0) readsize = 0; 396 (void) memset((char *)(&pagbuf+readsize), 397 0, PBLKSIZ-readsize); 398 } 399 chkblk(pagbuf); 400 oldb1 = blkno; 401 } 402 trace1(TR_dbm_access, 1); 403 } 404 405 int 406 getbit(void) 407 { 408 long bn; 409 ssize_t readsize; 410 long b, i, n; 411 412 trace1(TR_getbit, 0); 413 if (bitno > maxbno) { 414 trace1(TR_getbit, 1); 415 return (0); 416 } 417 n = bitno % BYTESIZ; 418 bn = bitno / BYTESIZ; 419 i = bn % DBLKSIZ; 420 b = bn / DBLKSIZ; 421 if (b != oldb2) { 422 (void) lseek(dirf, (long)b*DBLKSIZ, 0); 423 readsize = read(dirf, dirbuf, DBLKSIZ); 424 if (readsize != DBLKSIZ) { 425 if (readsize < 0) readsize = 0; 426 (void) memset((char *)(&dirbuf+readsize), 427 0, DBLKSIZ-readsize); 428 } 429 oldb2 = b; 430 } 431 if (dirbuf[i] & (1<<n)) { 432 trace1(TR_getbit, 1); 433 return (1); 434 } 435 trace1(TR_getbit, 1); 436 return (0); 437 } 438 439 int 440 setbit(void) 441 { 442 long bn; 443 long i, n, b; 444 445 trace1(TR_setbit, 0); 446 if (dbrdonly) { 447 trace1(TR_setbit, 1); 448 return (-1); 449 } 450 if (bitno > maxbno) { 451 maxbno = bitno; 452 (void) getbit(); 453 } 454 n = bitno % BYTESIZ; 455 bn = bitno / BYTESIZ; 456 i = bn % DBLKSIZ; 457 b = bn / DBLKSIZ; 458 dirbuf[i] |= 1<<n; 459 (void) lseek(dirf, (long)b*DBLKSIZ, 0); 460 if (write(dirf, dirbuf, DBLKSIZ) < 0) { 461 trace1(TR_setbit, 1); 462 return (-1); 463 } 464 trace1(TR_setbit, 1); 465 return (0); 466 } 467 468 datum 469 makdatum(char buf[PBLKSIZ], int n) 470 { 471 short *sp; 472 int t; 473 datum item; 474 475 trace1(TR_makdatum, 0); 476 sp = (short *)buf; 477 if (n < 0 || n >= sp[0]) 478 goto null; 479 t = PBLKSIZ; 480 if (n > 0) 481 t = sp[n+1-1]; 482 item.dptr = buf+sp[n+1]; 483 item.dsize = t - sp[n+1]; 484 trace1(TR_makdatum, 1); 485 return (item); 486 487 null: 488 item.dptr = NULL; 489 item.dsize = 0; 490 trace1(TR_makdatum, 1); 491 return (item); 492 } 493 494 int 495 cmpdatum(d1, d2) 496 datum d1, d2; 497 { 498 int n; 499 char *p1, *p2; 500 501 trace1(TR_cmpdatum, 0); 502 n = d1.dsize; 503 if (n != d2.dsize) { 504 trace1(TR_cmpdatum, 1); 505 return (n - d2.dsize); 506 } 507 if (n == 0) { 508 trace1(TR_cmpdatum, 1); 509 return (0); 510 } 511 p1 = d1.dptr; 512 p2 = d2.dptr; 513 do 514 if (*p1++ != *p2++) { 515 trace1(TR_cmpdatum, 1); 516 return (*--p1 - *--p2); 517 } 518 while (--n); 519 trace1(TR_cmpdatum, 1); 520 return (0); 521 } 522 523 int hitab[16] 524 /* 525 * ken's 526 * { 527 * 055, 043, 036, 054, 063, 014, 004, 005, 528 * 010, 064, 077, 000, 035, 027, 025, 071, 529 * }; 530 */ 531 = { 61, 57, 53, 49, 45, 41, 37, 33, 532 29, 25, 21, 17, 13, 9, 5, 1, 533 }; 534 long hltab[64] 535 = { 536 06100151277L, 06106161736L, 06452611562L, 05001724107L, 537 02614772546L, 04120731531L, 04665262210L, 07347467531L, 538 06735253126L, 06042345173L, 03072226605L, 01464164730L, 539 03247435524L, 07652510057L, 01546775256L, 05714532133L, 540 06173260402L, 07517101630L, 02431460343L, 01743245566L, 541 00261675137L, 02433103631L, 03421772437L, 04447707466L, 542 04435620103L, 03757017115L, 03641531772L, 06767633246L, 543 02673230344L, 00260612216L, 04133454451L, 00615531516L, 544 06137717526L, 02574116560L, 02304023373L, 07061702261L, 545 05153031405L, 05322056705L, 07401116734L, 06552375715L, 546 06165233473L, 05311063631L, 01212221723L, 01052267235L, 547 06000615237L, 01075222665L, 06330216006L, 04402355630L, 548 01451177262L, 02000133436L, 06025467062L, 07121076461L, 549 03123433522L, 01010635225L, 01716177066L, 05161746527L, 550 01736635071L, 06243505026L, 03637211610L, 01756474365L, 551 04723077174L, 03642763134L, 05750130273L, 03655541561L, 552 }; 553 554 long 555 hashinc(hash) 556 long hash; 557 { 558 long bit; 559 560 trace2(TR_hashinc, 0, hash); 561 hash &= hmask; 562 bit = hmask+1; 563 for (; ; ) { 564 bit >>= 1; 565 if (bit == 0) { 566 trace1(TR_hashinc, 1); 567 return (0L); 568 } 569 if ((hash&bit) == 0) { 570 trace1(TR_hashinc, 1); 571 return (hash|bit); 572 } 573 hash &= ~bit; 574 } 575 } 576 577 long 578 calchash(item) 579 datum item; 580 { 581 int i, j, f; 582 long hashl; 583 int hashi; 584 585 trace1(TR_calchash, 0); 586 hashl = 0; 587 hashi = 0; 588 for (i = 0; i < item.dsize; i++) { 589 f = item.dptr[i]; 590 for (j = 0; j < BYTESIZ; j += 4) { 591 hashi += hitab[f&017]; 592 hashl += hltab[hashi&63]; 593 f >>= 4; 594 } 595 } 596 trace1(TR_calchash, 1); 597 return (hashl); 598 } 599 600 void 601 delitem(buf, n) 602 char buf[PBLKSIZ]; 603 int n; 604 { 605 short *sp; 606 int i1, i2, i3; 607 608 trace1(TR_delitem, 0); 609 sp = (short *)buf; 610 if (n < 0 || n >= sp[0]) 611 goto bad; 612 i1 = sp[n+1]; 613 i2 = PBLKSIZ; 614 if (n > 0) 615 i2 = sp[n+1-1]; 616 i3 = sp[sp[0]+1-1]; 617 if (i2 > i1) 618 while (i1 > i3) { 619 i1--; 620 i2--; 621 buf[i2] = buf[i1]; 622 buf[i1] = 0; 623 } 624 i2 -= i1; 625 for (i1 = n + 1; i1 < sp[0]; i1++) 626 sp[i1+1-1] = sp[i1+1] + i2; 627 sp[0]--; 628 sp[sp[0]+1] = 0; 629 trace1(TR_delitem, 1); 630 return; 631 632 bad: 633 (void) printf("bad delitem\n"); 634 trace1(TR_delitem, 1); 635 abort(); 636 } 637 638 int 639 additem(buf, item) 640 char buf[PBLKSIZ]; 641 datum item; 642 { 643 short *sp; 644 int i1, i2; 645 646 trace1(TR_additem, 0); 647 sp = (short *)buf; 648 i1 = PBLKSIZ; 649 if (sp[0] > 0) 650 i1 = sp[sp[0]+1-1]; 651 i1 -= item.dsize; 652 i2 = (sp[0]+2) * (int)sizeof (short); 653 if (i1 <= i2) { 654 trace1(TR_additem, 1); 655 return (-1); 656 } 657 sp[sp[0]+1] = (short)i1; 658 for (i2 = 0; i2 < item.dsize; i2++) { 659 buf[i1] = item.dptr[i2]; 660 i1++; 661 } 662 sp[0]++; 663 trace1(TR_additem, 1); 664 return (sp[0]-1); 665 } 666 667 void 668 chkblk(buf) 669 char buf[PBLKSIZ]; 670 { 671 short *sp; 672 int t, i; 673 674 trace1(TR_chkblk, 0); 675 sp = (short *)buf; 676 t = PBLKSIZ; 677 for (i = 0; i < sp[0]; i++) { 678 if (sp[i+1] > t) 679 goto bad; 680 t = sp[i+1]; 681 } 682 if (t < (sp[0]+1) * sizeof (short)) 683 goto bad; 684 trace1(TR_chkblk, 1); 685 return; 686 687 bad: 688 (void) printf("bad block\n"); 689 trace1(TR_chkblk, 1); 690 abort(); 691 (void) memset((char *)&buf, 0, PBLKSIZ); 692 } 693