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 }