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