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 2019 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 ; 447 return (0); 448 } 449 450 int hitab[16] 451 /* 452 * ken's 453 * { 454 * 055,043,036,054,063,014,004,005, 455 * 010,064,077,000,035,027,025,071, 456 * }; 457 */ 458 = { 61, 57, 53, 49, 45, 41, 37, 33, 459 29, 25, 21, 17, 13, 9, 5, 1, 460 }; 461 long hltab[64] = { 462 06100151277L, 06106161736L, 06452611562L, 05001724107L, 463 02614772546L, 04120731531L, 04665262210L, 07347467531L, 464 06735253126L, 06042345173L, 03072226605L, 01464164730L, 465 03247435524L, 07652510057L, 01546775256L, 05714532133L, 466 06173260402L, 07517101630L, 02431460343L, 01743245566L, 467 00261675137L, 02433103631L, 03421772437L, 04447707466L, 468 04435620103L, 03757017115L, 03641531772L, 06767633246L, 469 02673230344L, 00260612216L, 04133454451L, 00615531516L, 470 06137717526L, 02574116560L, 02304023373L, 07061702261L, 471 05153031405L, 05322056705L, 07401116734L, 06552375715L, 472 06165233473L, 05311063631L, 01212221723L, 01052267235L, 473 06000615237L, 01075222665L, 06330216006L, 04402355630L, 474 01451177262L, 02000133436L, 06025467062L, 07121076461L, 475 03123433522L, 01010635225L, 01716177066L, 05161746527L, 476 01736635071L, 06243505026L, 03637211610L, 01756474365L, 477 04723077174L, 03642763134L, 05750130273L, 03655541561L, 478 }; 479 480 long 481 hashinc(long hash) 482 { 483 long bit; 484 485 hash &= hmask; 486 bit = hmask+1; 487 for (;;) { 488 bit >>= 1; 489 if (bit == 0) 490 return (0L); 491 if ((hash&bit) == 0) 492 return (hash|bit); 493 hash &= ~bit; 494 } 495 } 496 497 long 498 calchash(datum item) 499 { 500 int i, j, f; 501 long hashl; 502 int hashi; 503 504 hashl = 0; 505 hashi = 0; 506 for (i = 0; i < item.dsize; i++) { 507 f = item.dptr[i]; 508 for (j = 0; j < BYTESIZ; j += 4) { 509 hashi += hitab[f&017]; 510 hashl += hltab[hashi&63]; 511 f >>= 4; 512 } 513 } 514 return (hashl); 515 } 516 517 void 518 delitem(char buf[PBLKSIZ], int n) 519 { 520 short *sp; 521 int i1, i2, i3; 522 523 sp = (short *)buf; 524 if (n < 0 || n >= sp[0]) 525 goto bad; 526 i1 = sp[n+1]; 527 i2 = PBLKSIZ; 528 if (n > 0) 529 i2 = sp[n+1-1]; 530 i3 = sp[sp[0]+1-1]; 531 if (i2 > i1) 532 while (i1 > i3) { 533 i1--; 534 i2--; 535 buf[i2] = buf[i1]; 536 buf[i1] = 0; 537 } 538 i2 -= i1; 539 for (i1 = n+1; i1 < sp[0]; i1++) 540 sp[i1+1-1] = sp[i1+1] + i2; 541 sp[0]--; 542 sp[sp[0]+1] = 0; 543 return; 544 545 bad: 546 (void) printf("bad delitem\n"); 547 abort(); 548 } 549 550 int 551 additem(char buf[PBLKSIZ], datum item) 552 { 553 short *sp; 554 int i1, i2; 555 556 sp = (short *)buf; 557 i1 = PBLKSIZ; 558 if (sp[0] > 0) 559 i1 = sp[sp[0]+1-1]; 560 i1 -= item.dsize; 561 i2 = (int)((sp[0]+2) * sizeof (short)); 562 if (i1 <= i2) 563 return (-1); 564 sp[sp[0]+1] = (short)i1; 565 for (i2 = 0; i2 < item.dsize; i2++) { 566 buf[i1] = item.dptr[i2]; 567 i1++; 568 } 569 sp[0]++; 570 return (sp[0]-1); 571 } 572 573 void 574 chkblk(char buf[PBLKSIZ]) 575 { 576 short *sp; 577 int t, i; 578 579 sp = (short *)buf; 580 t = PBLKSIZ; 581 for (i = 0; i < sp[0]; i++) { 582 if (sp[i+1] > t) 583 goto bad; 584 t = sp[i+1]; 585 } 586 if (t < (sp[0]+1)*sizeof (short)) 587 goto bad; 588 return; 589 590 bad: 591 (void) printf("bad block\n"); 592 abort(); 593 } 594