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