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 }