lib/dbz.c

   1 /*
   2   dbz.c  V6.1.1
   3
   4 Copyright 1988 Jon Zeeff (zeeff@b-tech.ann-arbor.mi.us)
   5 You can use this code in any manner, as long as you leave my name on it
   6 and don't hold me responsible for any problems with it.
   7
   8 Hacked on by gdb@ninja.UUCP (David Butler); Sun Jun  5 00:27:08 CDT 1988
   9
  10 Various improvments + INCORE by moraes@ai.toronto.edu (Mark Moraes)
  11
  12 Major reworking by Henry Spencer as part of the C News project.
  13
  14 Minor lint and CodeCenter (Saber) fluff removal by Rich $alz (March, 1991).
  15 Non-portable CloseOnExec() calls added by Rich $alz (September, 1991).
  16 Added "writethrough" and tagmask calculation code from
  17 <rob@violet.berkeley.edu> and <leres@ee.lbl.gov> by Rich $alz (December, 1992).
  18 Merged in MMAP code by David Robinson, formerly <david@elroy.jpl.nasa.gov>
  19 now <david.robinson@sun.com> (January, 1993).
  20
  21 Major reworking by Clayton O'Neill (coneill@oneill.net).  Removed all the
  22 C News and backwards compatible cruft.  Ripped out all the tagmask stuff
  23 and replaced it with hashed .pag entries.  This removes the need for
  24 base file access.  Primary bottleneck now appears to be the hash
  25 algorithm and search().  You can change DBZ_INTERNAL_HASH_SIZE in
  26 dbz.h to increase the size of the stored hash.
  27
  28 These routines replace dbm as used by the usenet news software
  29 (it's not a full dbm replacement by any means).  It's fast and
  30 simple.  It contains no AT&T code.
  31
  32 The dbz database exploits the fact that when news stores a <key,value>
  33 tuple, the `value' part is a seek offset into a text file, pointing to
  34 a copy of the `key' part.  This avoids the need to store a copy of
  35 the key in the dbz files.
  36
  37 The basic format of the database is two hash tables, each in it's own
  38 file. One contains the offsets into the history text file , and the
  39 other contains a hash of the message id.  A value is stored by
  40 indexing into the tables using a hash value computed from the key;
  41 collisions are resolved by linear probing (just search forward for an
  42 empty slot, wrapping around to the beginning of the table if
  43 necessary).  Linear probing is a performance disaster when the table
  44 starts to get full, so a complication is introduced.  Each file actually
  45 contains one *or more* tables, stored sequentially in the files, and
  46 the length of the linear-probe sequences is limited.  The search (for
  47 an existing item or an empy slot always starts in the first table of
  48 the hash file, and whenever MAXRUN probes have been done in table N,
  49 probing continues in table N+1.  It is best not to overflow into more
  50 than 1-2 tables or else massive performance degradation may occur.
  51 Choosing the size of the database is extremely important because of this.
  52
  53 The table size is fixed for any particular database, but is determined
  54 dynamically when a database is rebuilt.  The strategy is to try to pick
  55 the size so the first table will be no more than 2/3 full, that being
  56 slightly before the point where performance starts to degrade.  (It is
  57 desirable to be a bit conservative because the overflow strategy tends
  58 to produce files with holes in them, which is a nuisance.)
  59
  60 Tagged hash + offset fuzzy technique merged by Sang-yong Suh (Nov, 1997)
  61
  62 Fixed a bug handling larger than 1Gb history offset by Sang-yong Suh(1998)
  63 Similar fix was suggested by Mike Hucka <hucka@umich.edu> (Jan, 1998) for
  64 dbz-3.3.2.
  65
  66 Limited can't tag warnings once per dbzinit() by Sang-yong Suh (May, 1998)
  67
  68 */
  69
  70 #include "config.h"
  71 #include "clibrary.h"
  72 #include <ctype.h>
  73 #include <errno.h>
  74 #include <fcntl.h>
  75 #include <netinet/in.h>
  76 #include <sys/mman.h>
  77 #include <sys/stat.h>
  78 #include <sys/time.h>
  79
  80 #include "dbz.h"
  81 #include "inn/messages.h"
  82 #include "inn/innconf.h"
  83 #include "inn/mmap.h"
  84 #include "libinn.h"
  85
  86 /* Needed on AIX 4.1 to get fd_set and friends. */
  87 #ifdef HAVE_SYS_SELECT_H
  88 # include <sys/select.h>
  89 #endif
  90
  91 /*
  92  * "LIA" = "leave it alone unless you know what you're doing".
  93  *
  94  * DBZTEST      Generate a standalone program for testing and benchmarking
  95  * DEFSIZE      default table size (not as critical as in old dbz)
  96  * NMEMORY      number of days of memory for use in sizing new table (LIA)
  97  * MAXRUN       length of run which shifts to next table (see below) (LIA)
  98  */
  99
 100 static int dbzversion = 6;      /* for validating .dir file format */
 101
 102 #ifdef DO_TAGGED_HASH
 103 /* assume that for tagged hash, we don't want more than 4byte of_t even if
 104  * off_t is 8 bytes -- people who use tagged-hash are usually short on
 105  * RAM.
 106  */
 107 #define of_t long
 108 #else
 109 #define of_t            off_t
 110 #endif
 111 #define SOF             (sizeof(of_t))
 112 #define NOTFOUND        ((of_t)-1)
 113 #ifdef  DO_TAGGED_HASH
 114
 115 #define OVERFLOW
 116 #ifdef OVERFLOW
 117 #include <limits.h>
 118 #endif
 119
 120 /* MAXDROPBITS is the maximum number of bits dropped from the offset value.
 121    The least significant bits are dropped.  The space is used to
 122    store hash additional bits, thereby increasing the possibility of the
 123    hash detection */
 124 #define MAXDROPBITS     4       /* max # of bits to drop from the offset */
 125
 126 /* MAXFUZZYLENGTH is the maximum in the offset value due to the MAXDROPBITS */
 127 #define MAXFUZZYLENGTH ((1 << MAXDROPBITS) - 1)
 128
 129 /*
 130  * We assume that unused areas of a binary file are zeros, and that the
 131  * bit pattern of `(of_t)0' is all zeros.  The alternative is rather
 132  * painful file initialization.  Note that okayvalue(), if OVERFLOW is
 133  * defined, knows what value of an offset would cause overflow.
 134  */
 135 #define VACANT          ((of_t)0)
 136 #define BIAS(o)         ((o)+1)         /* make any valid of_t non-VACANT */
 137 #define UNBIAS(o)       ((o)-1)         /* reverse BIAS() effect */
 138
 139 #define HASTAG(o)       ((o)&taghere)
 140 #define TAG(o)          ((o)&tagbits)
 141 #define NOTAG(o)        ((o)&~tagboth)
 142 #define CANTAG(o)       (((o)&tagboth) == 0)
 143 #define MKTAG(v)        (((v)<<conf.tagshift)&tagbits)
 144
 145 #ifndef NOTAGS
 146 #define TAGENB          0x80    /* tag enable is top bit, tag is next 7 */
 147 #define TAGMASK         0x7f
 148 #define TAGSHIFT        24
 149 #else
 150 #define TAGENB          0       /* no tags */
 151 #define TAGMASK         0
 152 #define TAGSHIFT        0
 153 #endif
 154
 155 /*
 156  * Stdio buffer for base-file reads.  Message-IDs (all news ever needs to
 157  * read) are essentially never longer than 64 bytes, and the typical stdio
 158  * buffer is so much larger that it is much more expensive to fill.
 159  */
 160
 161 static of_t tagbits;            /* pre-shifted tag mask */
 162 static of_t taghere;            /* pre-shifted tag-enable bit */
 163 static of_t tagboth;            /* tagbits|taghere */
 164 static int canttag_warned;              /* flag to control can't tag warning */
 165
 166 #endif  /* DO_TAGGED_HASH */
 167
 168 /* Old dbz used a long as the record type for dbz entries, which became
 169  * really gross in places because of mixed references.  We define these to
 170  * make it a bit easier if we want to store more in here.
 171  */
 172
 173 /* A new, from-scratch database, not built as a rebuild of an old one, needs
 174  * to know table size.  Normally the user supplies this info, but there have
 175  * to be defaults.  Making this too small can have devestating effects on
 176  * history speed for the current history implementation whereas making it too
 177  * big just wastes disk space, so err on the side of caution.  This may still
 178  * be a bit too small.  Assume people using tagged hash are running somewhat
 179  * smaller servers.
 180  */
 181 #ifndef DEFSIZE
 182
 183 #ifdef  DO_TAGGED_HASH
 184 #define DEFSIZE         1000003         /* I need a prime number */
 185 #else
 186 #define DEFSIZE         10000000
 187 #endif
 188
 189 #endif  /* DEFSIZE */
 190 /*
 191  * We read configuration info from the .dir file into this structure,
 192  * so we can avoid wired-in assumptions for an existing database.
 193  *
 194  * Among the info is a record of recent peak usages, so that a new table
 195  * size can be chosen intelligently when rebuilding.  10 is a good
 196  * number of usages to keep, since news displays marked fluctuations
 197  * in volume on a 7-day cycle.
 198  */
 199 #ifndef NMEMORY
 200 #define NMEMORY 10      /* # days of use info to remember */
 201 #endif
 202 #define NUSEDS  (1+NMEMORY)
 203
 204 typedef struct {
 205     long tsize;                 /* table size */
 206     long used[NUSEDS];          /* entries used today, yesterday, ... */
 207     long vused[NUSEDS];         /* ditto for text size */
 208     int valuesize;              /* size of table values, == sizeof(dbzrec) */
 209     int fillpercent;            /* fillpercent/100 is the percent full we'll
 210                                    try to keep the .pag file */
 211     of_t tagenb;                /* unshifted tag-enable bit */
 212     of_t tagmask;               /* unshifted tag mask */
 213     int tagshift;               /* shift count for tagmask and tagenb */
 214     int dropbits;               /* number of bits to discard from offset */
 215     int lenfuzzy;               /* num of fuzzy characters in offset */
 216 } dbzconfig;
 217 static dbzconfig conf;
 218
 219 /*
 220  * Default dbzoptions to
 221  */
 222 static dbzoptions options = {
 223     false,              /* write through off */
 224     INCORE_NO,          /* index/pag from disk */
 225 #ifdef HAVE_MMAP
 226     INCORE_MMAP,        /* exists mmap'ed. ignored in tagged hash mode */
 227 #else
 228     INCORE_NO,          /* exists from disk. ignored in tagged hash mode */
 229 #endif
 230     true                /* non-blocking writes */
 231 };
 232
 233 /*
 234  * Data structure for recording info about searches.
 235  */
 236 typedef struct {
 237     of_t place;         /* current location in file */
 238     int tabno;                  /* which table we're in */
 239     int run;                    /* how long we'll stay in this table */
 240 #               ifndef MAXRUN
 241 #               define  MAXRUN  100
 242 #               endif
 243     HASH hash;                  /* the key's hash code */
 244     unsigned long shorthash;    /* integer version of the hash, used for
 245                                    determining the entries location.
 246                                    Tagged_hash stores the 31-bit hash here */
 247     of_t tag;           /* tag we are looking for */
 248     int aborted;                /* has i/o error aborted search? */
 249 } searcher;
 250 #define FRESH   ((searcher *)NULL)
 251
 252 /*
 253  * Arguably the searcher struct for a given routine ought to be local to
 254  * it, but a fetch() is very often immediately followed by a store(), and
 255  * in some circumstances it is a useful performance win to remember where
 256  * the fetch() completed.  So we use a global struct and remember whether
 257  * it is current.
 258  */
 259 static searcher srch;
 260 static searcher *prevp; /* &srch or FRESH */
 261
 262 /* Structure for hash tables */
 263 typedef struct {
 264     int fd;                     /* Non-blocking descriptor for writes */
 265     off_t pos;                  /* Current offset into the table */
 266     int reclen;                 /* Length of records in the table */
 267     dbz_incore_val incore;      /* What we're using core for */
 268     void *core;                 /* Pointer to in-core table */
 269 } hash_table;
 270
 271 /* central data structures */
 272 static bool opendb = false;     /* Indicates if a database is currently open */
 273 static FILE *dirf;              /* descriptor for .dir file */
 274 static bool readonly;           /* database open read-only? */
 275 #ifdef  DO_TAGGED_HASH
 276 static FILE *basef;             /* descriptor for base file */
 277 static char *basefname;         /* name for not-yet-opened base file */
 278 static hash_table pagtab;       /* pag hash table, stores hash + offset */
 279 #else
 280 static hash_table idxtab;       /* index hash table, used for data retrieval */
 281 static hash_table etab;         /* existance hash table, used for existance checks */
 282 #endif
 283 static bool dirty;              /* has a store() been done? */
 284 static erec empty_rec;          /* empty rec to compare against
 285                                    initalized in dbzinit */
 286
 287 /* misc. forwards */
 288 static bool getcore(hash_table *tab);
 289 static bool putcore(hash_table *tab);
 290 static bool getconf(FILE *df, dbzconfig *cp);
 291 static int  putconf(FILE *f, dbzconfig *cp);
 292 static void start(searcher *sp, const HASH hash, searcher *osp);
 293 #ifdef  DO_TAGGED_HASH
 294 static of_t search(searcher *sp);
 295 static bool set_pag(searcher *sp, of_t value);
 296 #else
 297 static bool search(searcher *sp);
 298 #endif
 299 static bool set(searcher *sp, hash_table *tab, void *value);
 300
 301 /* file-naming stuff */
 302 static char dir[] = ".dir";
 303 #ifdef  DO_TAGGED_HASH
 304 static char pag[] = ".pag";
 305 #else
 306 static char idx[] = ".index";
 307 static char exists[] = ".hash";
 308 #endif
 309
 310 int dbzneedfilecount(void) {
 311 #ifdef  DO_TAGGED_HASH
 312     return 2; /* basef and dirf are fopen()'ed and kept */
 313 #else
 314     return 1; /* dirf is fopen()'ed and kept */
 315 #endif
 316 }
 317
 318 #ifdef  DO_TAGGED_HASH
 319 /*
 320  - dbzconfbase - reconfigure dbzconf from base file size.
 321  */
 322 static void
 323 config_by_text_size(dbzconfig *c, of_t basesize)
 324 {
 325     int                 i;
 326     unsigned long       m;
 327
 328     /* if no tag requested, just return. */
 329     if ((c->tagmask | c->tagenb) == 0)
 330         return;
 331
 332     /* Use 10 % larger base file size.  Sometimes the offset overflows */
 333     basesize += basesize / 10;
 334
 335     /* calculate tagging from old file */
 336     for (m = 1, i = 0; m < (unsigned long)basesize; i++, m <<= 1)
 337         continue;
 338
 339     /* if we had more tags than the default, use the new data */
 340     c->dropbits = 0;
 341     while (m > (1 << TAGSHIFT)) {
 342         if (c->dropbits >= MAXDROPBITS)
 343             break;
 344         c->dropbits++;
 345         m >>= 1;
 346         i--;
 347     }
 348     c->tagenb = TAGENB;
 349     c->tagmask = TAGMASK;
 350     c->tagshift = TAGSHIFT;
 351     if ((c->tagmask | c->tagenb) && m > (1 << TAGSHIFT)) {
 352         c->tagshift = i;
 353         c->tagmask = (~(unsigned long)0) >> (i + 1);
 354         c->tagenb = (c->tagmask << 1) & ~c->tagmask;
 355     }
 356     c->lenfuzzy = (int)(1 << c->dropbits) - 1;
 357
 358     m = (c->tagmask | c->tagenb) << c->tagshift;
 359     if (m & (basesize >> c->dropbits)) {
 360         fprintf(stderr, "m 0x%lx size 0x%lx\n", m, basesize);
 361         exit(1);
 362     }
 363 }
 364 #endif  /* DO_TAGGED_HASH */
 365
 366 /*
 367  - create and truncate .pag, .idx, or .hash files
 368  - return false on error
 369  */
 370 static bool
 371 create_truncate(const char *name, const char *pag1)
 372 {
 373     char *fn;
 374     FILE *f;
 375
 376     fn = concat(name, pag1, (char *) 0);
 377     f = Fopen(fn, "w", TEMPORARYOPEN);
 378     free(fn);
 379     if (f == NULL) {
 380         syswarn("unable to create/truncate %s", pag1);
 381         return false;
 382     } else
 383         Fclose(f);
 384     return true;
 385 }
 386
 387 /* dbzfresh - set up a new database, no historical info
 388  * Return true for success, false for failure
 389  * name - base name; .dir and .pag must exist
 390  * size - table size (0 means default)
 391  */
 392 bool
 393 dbzfresh(const char *name, off_t size)
 394 {
 395     char *fn;
 396     dbzconfig c;
 397     FILE *f;
 398 #ifdef  DO_TAGGED_HASH
 399     struct stat sb;
 400     of_t m;
 401 #endif
 402
 403     if (opendb) {
 404         warn("dbzfresh: database already open");
 405         return false;
 406     }
 407     if (size != 0 && size < 2) {
 408         warn("dbzfresh: preposterous size (%ld)", (long) size);
 409         return false;
 410     }
 411
 412     /* get default configuration */
 413     if (!getconf(NULL, &c))
 414         return false;   /* "can't happen" */
 415
 416 #ifdef  DO_TAGGED_HASH
 417     /* and mess with it as specified */
 418     if (size != 0)
 419         c.tsize = size;
 420     m = c.tagmask;
 421     c.tagshift = 0;
 422     while (!(m & 1)) {
 423         m >>= 1;
 424         c.tagshift++;
 425     }
 426     c.tagmask = m;
 427     c.tagenb = (m << 1) & ~m;
 428     c.dropbits = 0;
 429     c.lenfuzzy = 0;
 430
 431     /* if big enough basb file exists, update config */
 432     if (stat(name, &sb) != -1)
 433         config_by_text_size(&c, sb.st_size);
 434 #else
 435     /* set the size as specified, make sure we get at least 2 bytes
 436        of implicit hash */
 437     if (size != 0)
 438         c.tsize = size > (64 * 1024) ? size : 64 * 1024;
 439 #endif
 440
 441     /* write it out */
 442     fn = concat(name, dir, (char *) 0);
 443     f = Fopen(fn, "w", TEMPORARYOPEN);
 444     free(fn);
 445     if (f == NULL) {
 446         syswarn("dbzfresh: unable to write config");
 447         return false;
 448     }
 449     if (putconf(f, &c) < 0) {
 450         Fclose(f);
 451         return false;
 452     }
 453     if (Fclose(f) == EOF) {
 454         syswarn("dbzfresh: fclose failure");
 455         return false;
 456     }
 457
 458     /* create and truncate .pag, or .index/.hash files */
 459 #ifdef  DO_TAGGED_HASH
 460     if (!create_truncate(name, pag))
 461         return false;
 462 #else
 463     if (!create_truncate(name, idx))
 464         return false;
 465     if (!create_truncate(name, exists))
 466         return false;
 467 #endif  /* DO_TAGGED_HASH */
 468
 469     /* and punt to dbzinit for the hard work */
 470     return dbzinit(name);
 471 }
 472
 473 #ifdef  DO_TAGGED_HASH
 474 /*
 475  - isprime - is a number prime?
 476  */
 477 static bool
 478 isprime(long x)
 479 {
 480     static int quick[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 0 };
 481     int *ip;
 482     long div1, stop;
 483
 484     /* hit the first few primes quickly to eliminate easy ones */
 485     /* this incidentally prevents ridiculously small tables */
 486     for (ip = quick; (div1 = *ip) != 0; ip++)
 487         if (x % div1 == 0) {
 488             debug("isprime: quick result on %ld", x);
 489             return false;
 490         }
 491
 492     /* approximate square root of x */
 493     for (stop = x; x/stop < stop; stop >>= 1)
 494         continue;
 495     stop <<= 1;
 496
 497     /* try odd numbers up to stop */
 498     for (div1 = *--ip; div1 < stop; div1 += 2)
 499         if (x%div1 == 0)
 500             return false;
 501
 502     return true;
 503 }
 504 #endif
 505
 506 /*
 507  * dbzsize  - what's a good table size to hold this many entries?
 508  * contents - size of table (0 means return the default)
 509  */
 510 long
 511 dbzsize(off_t contents)
 512 {
 513     of_t            n;
 514
 515     if (contents <= 0) {        /* foulup or default inquiry */
 516         debug("dbzsize: preposterous input (%ld)", (long) contents);
 517         return DEFSIZE;
 518     }
 519
 520     if ((conf.fillpercent > 0) && (conf.fillpercent < 100))
 521         n = (contents / conf.fillpercent) * 100;
 522     else
 523         n = (contents * 3) / 2; /* try to keep table at most 2/3's full */
 524
 525     /* Make sure that we get at least 2 bytes of implicit hash */
 526     if (n < (64 * 1024))
 527         n = 64 * 1024;
 528
 529 #ifdef  DO_TAGGED_HASH
 530     if (!(n & 1))
 531         n += 1;                 /* make it odd */
 532     debug("dbzsize: tentative size %ld", n);
 533     while (!isprime(n))         /* look for a prime */
 534         n += 2;
 535 #endif
 536
 537     debug("dbzsize: final size %ld", (long) n);
 538     return n;
 539 }
 540
 541 /* dbzagain - set up a new database to be a rebuild of an old one
 542  * Returns true on success, false on failure
 543  * name - base name; .dir and .pag must exist
 544  * oldname - basename, all must exist
 545  */
 546 bool
 547 dbzagain(const char *name, const char *oldname)
 548 {
 549     char *fn;
 550     dbzconfig c;
 551     bool result;
 552     int i;
 553     long top;
 554     FILE *f;
 555     int newtable;
 556     of_t newsize;
 557 #ifdef  DO_TAGGED_HASH
 558     long vtop;
 559     struct stat sb;
 560 #endif
 561
 562     if (opendb) {
 563         warn("dbzagain: database already open");
 564         return false;
 565     }
 566
 567     /* pick up the old configuration */
 568     fn = concat(oldname, dir, (char *) 0);
 569     f = Fopen(fn, "r", TEMPORARYOPEN);
 570     free(fn);
 571     if (f == NULL) {
 572         syswarn("dbzagain: cannot open old .dir file");
 573         return false;
 574     }
 575     result = getconf(f, &c);
 576     Fclose(f);
 577     if (!result) {
 578         syswarn("dbzagain: getconf failed");
 579         return false;
 580     }
 581
 582     /* tinker with it */
 583     top = 0;
 584     newtable = 0;
 585     for (i = 0; i < NUSEDS; i++) {
 586         if (top < c.used[i])
 587             top = c.used[i];
 588         if (c.used[i] == 0)
 589             newtable = 1;       /* hasn't got full usage history yet */
 590     }
 591     if (top == 0) {
 592         debug("dbzagain: old table has no contents!");
 593         newtable = 1;
 594     }
 595     for (i = NUSEDS-1; i > 0; i--)
 596         c.used[i] = c.used[i-1];
 597     c.used[0] = 0;
 598
 599 #ifdef  DO_TAGGED_HASH
 600     vtop = 0;
 601     for (i = 0; i < NUSEDS; i++) {
 602         if (vtop < c.vused[i])
 603             vtop = c.vused[i];
 604         if (c.vused[i] == 0)
 605             newtable = 1;       /* hasn't got full usage history yet */
 606     }
 607     if (top != 0 && vtop == 0) {
 608         debug("dbzagain: old table has no contents!");
 609         newtable = 1;
 610     }
 611     for (i = NUSEDS-1; i > 0; i--)
 612         c.vused[i] = c.vused[i-1];
 613     c.vused[0] = 0;
 614
 615     /* calculate tagging from old file */
 616     if (stat(oldname, &sb) != -1 && vtop < sb.st_size)
 617         vtop = sb.st_size;
 618     config_by_text_size(&c, vtop);
 619 #endif
 620
 621     newsize = dbzsize(top);
 622     if (!newtable || newsize > c.tsize) /* don't shrink new table */
 623         c.tsize = newsize;
 624
 625     /* write it out */
 626     fn = concat(name, dir, (char *) 0);
 627     f = Fopen(fn, "w", TEMPORARYOPEN);
 628     free(fn);
 629     if (f == NULL) {
 630         syswarn("dbzagain: unable to write new .dir");
 631         return false;
 632     }
 633     i = putconf(f, &c);
 634     Fclose(f);
 635     if (i < 0) {
 636         warn("dbzagain: putconf failed");
 637         return false;
 638     }
 639
 640     /* create and truncate .pag, or .index/.hash files */
 641 #ifdef  DO_TAGGED_HASH
 642     if (!create_truncate(name, pag))
 643         return false;
 644 #else
 645     if (!create_truncate(name, idx))
 646         return false;
 647     if (!create_truncate(name, exists))
 648         return false;
 649 #endif
 650
 651     /* and let dbzinit do the work */
 652     return dbzinit(name);
 653 }
 654
 655 static bool
 656 openhashtable(const char *base, const char *ext, hash_table *tab,
 657               const size_t reclen, const dbz_incore_val incore)
 658 {
 659     char *name;
 660     int oerrno;
 661
 662     name = concat(base, ext, (char *) 0);
 663     if ((tab->fd = open(name, readonly ? O_RDONLY : O_RDWR)) < 0) {
 664         syswarn("openhashtable: could not open raw");
 665         oerrno = errno;
 666         free(name);
 667         errno = oerrno;
 668         return false;
 669     }
 670     free(name);
 671
 672     tab->reclen = reclen;
 673     close_on_exec(tab->fd, true);
 674     tab->pos = -1;
 675
 676     /* get first table into core, if it looks desirable and feasible */
 677     tab->incore = incore;
 678     if (tab->incore != INCORE_NO) {
 679         if (!getcore(tab)) {
 680             syswarn("openhashtable: getcore failure");
 681             oerrno = errno;
 682             close(tab->fd);
 683             errno = oerrno;
 684             return false;
 685         }
 686     }
 687
 688     if (options.nonblock && nonblocking(tab->fd, true) < 0) {
 689         syswarn("fcntl: could not set nonblock");
 690         oerrno = errno;
 691         close(tab->fd);
 692         errno = oerrno;
 693         return false;
 694     }
 695     return true;
 696 }
 697
 698 static void closehashtable(hash_table *tab) {
 699     close(tab->fd);
 700     if (tab->incore == INCORE_MEM)
 701         free(tab->core);
 702     if (tab->incore == INCORE_MMAP) {
 703 #if defined(HAVE_MMAP)
 704         if (munmap(tab->core, conf.tsize * tab->reclen) == -1) {
 705             syswarn("closehashtable: munmap failed");
 706         }
 707 #else
 708         warn("closehashtable: can't mmap files");
 709 #endif
 710     }
 711 }
 712
 713 #ifdef  DO_TAGGED_HASH
 714 static bool
 715 openbasefile(const char *name)
 716 {
 717     basef = Fopen(name, "r", DBZ_BASE);
 718     if (basef == NULL) {
 719         syswarn("dbzinit: basefile open failed");
 720         basefname = xstrdup(name);
 721     } else
 722         basefname = NULL;
 723     if (basef != NULL)
 724         close_on_exec(fileno(basef), true);
 725     if (basef != NULL)
 726          setvbuf(basef, NULL, _IOFBF, 64);
 727     return true;
 728 }
 729 #endif  /* DO_TAGGED_HASH */
 730
 731 /*
 732  * dbzinit - open a database, creating it (using defaults) if necessary
 733  *
 734  * We try to leave errno set plausibly, to the extent that underlying
 735  * functions permit this, since many people consult it if dbzinit() fails.
 736  * return true for success, false for failure
 737  */
 738 bool
 739 dbzinit(const char *name)
 740 {
 741     char *fname;
 742
 743     if (opendb) {
 744         warn("dbzinit: dbzinit already called once");
 745         errno = 0;
 746         return false;
 747     }
 748
 749     /* open the .dir file */
 750     fname = concat(name, dir, (char *) 0);
 751     if ((dirf = Fopen(fname, "r+", DBZ_DIR)) == NULL) {
 752         dirf = Fopen(fname, "r", DBZ_DIR);
 753         readonly = true;
 754     } else
 755         readonly = false;
 756     free(fname);
 757     if (dirf == NULL) {
 758         syswarn("dbzinit: can't open .dir file");
 759         return false;
 760     }
 761     close_on_exec(fileno(dirf), true);
 762
 763     /* pick up configuration */
 764     if (!getconf(dirf, &conf)) {
 765         warn("dbzinit: getconf failure");
 766         Fclose(dirf);
 767         errno = EDOM;   /* kind of a kludge, but very portable */
 768         return false;
 769     }
 770
 771     /* open pag or idx/exists file */
 772 #ifdef  DO_TAGGED_HASH
 773     if (!openhashtable(name, pag, &pagtab, SOF, options.pag_incore)) {
 774         Fclose(dirf);
 775         return false;
 776     }
 777     if (!openbasefile(name)) {
 778         close(pagtab.fd);
 779         Fclose(dirf);
 780         return false;
 781     }
 782     tagbits = conf.tagmask << conf.tagshift;
 783     taghere = conf.tagenb << conf.tagshift;
 784     tagboth = tagbits | taghere;
 785     canttag_warned = 0;
 786 #else
 787     if (!openhashtable(name, idx, &idxtab, sizeof(of_t), options.pag_incore)) {
 788         Fclose(dirf);
 789         return false;
 790     }
 791     if (!openhashtable(name, exists, &etab, sizeof(erec),
 792                 options.exists_incore)) {
 793         Fclose(dirf);
 794         return false;
 795     }
 796 #endif
 797
 798     /* misc. setup */
 799     dirty = false;
 800     opendb = true;
 801     prevp = FRESH;
 802     memset(&empty_rec, '\0', sizeof(empty_rec));
 803     debug("dbzinit: succeeded");
 804     return true;
 805 }
 806
 807 /* dbzclose - close a database
 808  */
 809 bool
 810 dbzclose(void)
 811 {
 812     bool ret = true;
 813
 814     if (!opendb) {
 815         warn("dbzclose: not opened!");
 816         return false;
 817     }
 818
 819     if (!dbzsync())
 820         ret = false;
 821
 822 #ifdef  DO_TAGGED_HASH
 823     closehashtable(&pagtab);
 824     if (Fclose(basef) == EOF) {
 825         syswarn("dbzclose: fclose(basef) failed");
 826         ret = false;
 827     }
 828     if (basefname != NULL)
 829         free(basefname);
 830     basef = NULL;
 831 #else
 832     closehashtable(&idxtab);
 833     closehashtable(&etab);
 834 #endif
 835
 836     if (Fclose(dirf) == EOF) {
 837         syswarn("dbzclose: fclose(dirf) failed");
 838         ret = false;
 839     }
 840
 841     debug("dbzclose: %s", (ret == true) ? "succeeded" : "failed");
 842     if (ret)
 843         opendb = false;
 844     return ret;
 845 }
 846
 847 /* dbzsync - push all in-core data out to disk
 848  */
 849 bool
 850 dbzsync(void)
 851 {
 852     bool ret = true;
 853
 854     if (!opendb) {
 855         warn("dbzsync: not opened!");
 856         return false;
 857     }
 858
 859     if (!dirty)
 860         return true;;
 861
 862 #ifdef  DO_TAGGED_HASH
 863     if (!putcore(&pagtab)) {
 864 #else
 865     if (!putcore(&idxtab) || !putcore(&etab)) {
 866 #endif
 867         warn("dbzsync: putcore failed");
 868         ret = false;
 869     }
 870
 871     if (putconf(dirf, &conf) < 0)
 872         ret = false;
 873
 874     debug("dbzsync: %s", ret ? "succeeded" : "failed");
 875     return ret;
 876 }
 877
 878 #ifdef  DO_TAGGED_HASH
 879 /*
 880  - okayvalue - check that a value can be stored
 881  */
 882 static int
 883 okayvalue(of_t value)
 884 {
 885     if (HASTAG(value))
 886         return(0);
 887 #ifdef OVERFLOW
 888     if (value == LONG_MAX)      /* BIAS() and UNBIAS() will overflow */
 889         return(0);
 890 #endif
 891     return(1);
 892 }
 893 #endif
 894
 895 /* dbzexists - check if the given message-id is in the database */
 896 bool
 897 dbzexists(const HASH key)
 898 {
 899 #ifdef  DO_TAGGED_HASH
 900     off_t value;
 901
 902     return (dbzfetch(key, &value) != 0);
 903 #else
 904
 905     if (!opendb) {
 906         warn("dbzexists: database not open!");
 907         return false;
 908     }
 909
 910     prevp = FRESH;
 911     start(&srch, key, FRESH);
 912     return search(&srch);
 913 #endif
 914 }
 915
 916 /*
 917  * dbzfetch - get offset of an entry from the database
 918  *
 919  * Returns the offset of the text file for input key,
 920  * or -1 if NOTFOUND or error occurs.
 921  */
 922 bool
 923 dbzfetch(const HASH key, off_t *value)
 924 {
 925 #ifdef  DO_TAGGED_HASH
 926 #define MAX_NB2RD       (DBZMAXKEY + MAXFUZZYLENGTH + 2)
 927 #define MIN_KEY_LENGTH  6       /* strlen("<1@a>") + strlen("\t") */
 928     char *bp, buffer[MAX_NB2RD];
 929     int keylen, j, nb2r;
 930     HASH hishash;
 931     char *keytext = NULL;
 932     of_t offset = NOTFOUND;
 933 #endif
 934
 935     prevp = FRESH;
 936
 937     if (!opendb) {
 938         warn("dbzfetch: database not open!");
 939         return false;
 940     }
 941
 942     start(&srch, key, FRESH);
 943 #ifdef  DO_TAGGED_HASH
 944     /*
 945      * nb2r: number of bytes to read from history file.
 946      *       It can be reduced if history text is written as hashes only.
 947      */
 948     nb2r = sizeof(buffer) - 1;
 949
 950     while ((offset = search(&srch)) != NOTFOUND) {
 951         debug("got 0x%lx", key_ptr);
 952
 953         /* fetch the key */
 954         offset <<= conf.dropbits;
 955         if (offset)             /* backspace 1 character to read '\n' */
 956             offset--;
 957         if (fseeko(basef, offset, SEEK_SET) != 0) {
 958             syswarn("dbzfetch: seek failed");
 959             return false;
 960         }
 961         keylen = fread(buffer, 1, nb2r, basef);
 962         if (keylen < MIN_KEY_LENGTH) {
 963             syswarn("dbzfetch: read failed");
 964             return false;
 965         }
 966         buffer[keylen] = '\0';  /* terminate the string */
 967
 968         if (offset) {           /* find the '\n', the previous EOL */
 969             if (keylen > conf.lenfuzzy)
 970                 keylen = conf.lenfuzzy; /* keylen is fuzzy distance now */
 971             for (j=0,bp=buffer; j<keylen; j++,bp++)
 972                 if (*bp == '\n')
 973                     break;
 974             if (*bp != '\n') {
 975                 debug("dbzfetch: can't locate EOL");
 976                 /* pag entry should be deleted, but I'm lazy... */
 977                 continue;
 978             }
 979             offset++;
 980             bp++;       /* now *bp is the start of key */
 981         } else {
 982             j = 0;      /* We are looking for the first history line. */
 983             bp = buffer;
 984         }
 985
 986         /* Does this history line really have same key? */
 987         if (*bp == '[') {
 988             if (!keytext)
 989                 keytext = HashToText(key);
 990             if (memcmp(keytext, bp+1, sizeof(HASH)*2) != 0)
 991                 continue;
 992         } else if (*bp == '<') {
 993             char *p = strchr(bp+1, '\t');
 994             if (!p)             /* history has a corrupted line */
 995                 continue;
 996             *p = '\0';
 997             hishash = HashMessageID(bp);
 998             if (memcmp(&key, &hishash, sizeof(HASH)) != 0)
 999                 continue;
1000         } else
1001             continue;
1002
1003         /* we found it */
1004         offset += j;
1005         debug("fetch: successful");
1006         *value = offset;
1007         return true;
1008     }
1009
1010     /* we didn't find it */
1011     debug("fetch: failed");
1012     prevp = &srch;                      /* remember where we stopped */
1013     return false;
1014 #else   /* DO_TAGGED_HASH */
1015     if (search(&srch) == true) {
1016         /* Actually get the data now */
1017         if ((options.pag_incore != INCORE_NO) && (srch.place < conf.tsize)) {
1018             memcpy(value, &((of_t *)idxtab.core)[srch.place], sizeof(of_t));
1019         } else {
1020             if (pread(idxtab.fd, value, sizeof(of_t), srch.place * idxtab.reclen) != sizeof(of_t)) {
1021                 syswarn("fetch: read failed");
1022                 idxtab.pos = -1;
1023                 srch.aborted = 1;
1024                 return false;
1025             }
1026         }
1027         debug("fetch: successful");
1028         return true;
1029     }
1030
1031     /* we didn't find it */
1032     debug("fetch: failed");
1033     prevp = &srch;                      /* remember where we stopped */
1034     return false;
1035 #endif
1036 }
1037
1038 /*
1039  * dbzstore - add an entry to the database
1040  * returns true for success and false for failure
1041  */
1042 DBZSTORE_RESULT
1043 dbzstore(const HASH key, off_t data)
1044 {
1045 #ifdef  DO_TAGGED_HASH
1046     of_t value;
1047 #else
1048     erec     evalue;
1049 #endif
1050
1051     if (!opendb) {
1052         warn("dbzstore: database not open!");
1053         return DBZSTORE_ERROR;
1054     }
1055     if (readonly) {
1056         warn("dbzstore: database open read-only");
1057         return DBZSTORE_ERROR;
1058     }
1059
1060 #ifdef  DO_TAGGED_HASH
1061     /* copy the value in to ensure alignment */
1062     memcpy(&value, &data, SOF);
1063
1064     /* update maximum offset value if necessary */
1065     if (value > conf.vused[0])
1066         conf.vused[0] = value;
1067
1068     /* now value is in fuzzy format */
1069     value >>= conf.dropbits;
1070     debug("dbzstore: (%ld)", (long) value);
1071
1072     if (!okayvalue(value)) {
1073         warn("dbzstore: reserved bit or overflow in 0x%lx", value);
1074         return DBZSTORE_ERROR;
1075     }
1076
1077     /* find the place, exploiting previous search if possible */
1078     start(&srch, key, prevp);
1079     while (search(&srch) != NOTFOUND)
1080         continue;
1081
1082     prevp = FRESH;
1083     conf.used[0]++;
1084     debug("store: used count %ld", conf.used[0]);
1085     dirty = 1;
1086     if (!set_pag(&srch, value))
1087         return DBZSTORE_ERROR;
1088     return DBZSTORE_OK;
1089 #else   /* DO_TAGGED_HASH */
1090
1091     /* find the place, exploiting previous search if possible */
1092     start(&srch, key, prevp);
1093     if (search(&srch) == true)
1094         return DBZSTORE_EXISTS;
1095
1096     prevp = FRESH;
1097     conf.used[0]++;
1098     debug("store: used count %ld", conf.used[0]);
1099     dirty = true;
1100
1101     memcpy(&evalue.hash, &srch.hash,
1102            sizeof(evalue.hash) < sizeof(srch.hash) ? sizeof(evalue.hash) : sizeof(srch.hash));
1103
1104     /* Set the value in the index first since we don't care if it's out of date */
1105     if (!set(&srch, &idxtab, (void *)&data))
1106         return DBZSTORE_ERROR;
1107     if (!set(&srch, &etab, &evalue))
1108         return DBZSTORE_ERROR;
1109     return DBZSTORE_OK;
1110 #endif  /* DO_TAGGED_HASH */
1111 }
1112
1113 /*
1114  * getconf - get configuration from .dir file
1115  *   df    - NULL means just give me the default
1116  *   pf    - NULL means don't care about .pag
1117  *   returns true for success, false for failure
1118  */
1119 static bool
1120 getconf(FILE *df, dbzconfig *cp)
1121 {
1122     int         i;
1123
1124     /* empty file, no configuration known */
1125 #ifdef  DO_TAGGED_HASH
1126     if (df == NULL) {
1127         cp->tsize = DEFSIZE;
1128         for (i = 0; i < NUSEDS; i++)
1129             cp->used[i] = 0;
1130         for (i = 0; i < NUSEDS; i++)
1131             cp->vused[i] = 0;
1132         cp->valuesize = sizeof(of_t);
1133         cp->fillpercent = 50;
1134         cp->tagenb = TAGENB;
1135         cp->tagmask = TAGMASK;
1136         cp->tagshift = TAGSHIFT;
1137         cp->dropbits = 0;
1138         cp->lenfuzzy = 0;
1139         debug("getconf: defaults (%ld, %c, (0x%lx/0x%lx<<%d %d))",
1140               cp->tsize, cp->casemap, cp->tagenb,
1141               cp->tagmask, cp->tagshift, cp->dropbits);
1142         return true;
1143     }
1144
1145     i = fscanf(df, "dbz 6 %ld %d %d %ld %ld %d %d\n", &cp->tsize,
1146                 &cp->valuesize, &cp->fillpercent, &cp->tagenb,
1147                 &cp->tagmask, &cp->tagshift, &cp->dropbits);
1148     if (i != 7) {
1149         warn("dbz: bad first line in config");
1150         return false;
1151     }
1152     if (cp->valuesize != sizeof(of_t)) {
1153         warn("dbz: wrong of_t size (%d)", cp->valuesize);
1154         return false;
1155     }
1156     cp->lenfuzzy = (int)(1 << cp->dropbits) - 1;
1157 #else   /* DO_TAGGED_HASH */
1158     if (df == NULL) {
1159         cp->tsize = DEFSIZE;
1160         for (i = 0; i < NUSEDS; i++)
1161             cp->used[i] = 0;
1162         cp->valuesize = sizeof(of_t) + sizeof(erec);
1163         cp->fillpercent = 66;
1164         debug("getconf: defaults (%ld)", cp->tsize);
1165         return true;
1166     }
1167
1168     i = fscanf(df, "dbz 6 %ld %d %d\n", &cp->tsize,
1169                 &cp->valuesize, &cp->fillpercent);
1170     if (i != 3) {
1171         warn("dbz: bad first line in config");
1172         return false;
1173     }
1174     if (cp->valuesize != (sizeof(of_t) + sizeof(erec))) {
1175         warn("dbz: wrong of_t size (%d)", cp->valuesize);
1176         return false;
1177     }
1178 #endif  /* DO_TAGGED_HASH */
1179     debug("size %ld", cp->tsize);
1180
1181     /* second line, the usages */
1182     for (i = 0; i < NUSEDS; i++)
1183         if (!fscanf(df, "%ld", &cp->used[i])) {
1184             warn("dbz: bad usage value in config");
1185             return false;
1186         }
1187     debug("used %ld %ld %ld...", cp->used[0], cp->used[1], cp->used[2]);
1188
1189 #ifdef  DO_TAGGED_HASH
1190     /* third line, the text usages */
1191     for (i = 0; i < NUSEDS; i++)
1192         if (!fscanf(df, "%ld", &cp->vused[i])) {
1193             warn("dbz: bad text usage value in config");
1194             return false;
1195         }
1196     debug("vused %ld %ld %ld...", cp->vused[0], cp->vused[1], cp->vused[2]);
1197 #endif  /* DO_TAGGED_HASH */
1198
1199     return true;
1200 }
1201
1202 /* putconf - write configuration to .dir file
1203  * Returns: 0 for success, -1 for failure
1204  */
1205 static int
1206 putconf(FILE *f, dbzconfig *cp)
1207 {
1208     int i;
1209     int ret = 0;
1210
1211     if (fseeko(f, 0, SEEK_SET) != 0) {
1212         syswarn("dbz: fseeko failure in putconf");
1213         ret = -1;
1214     }
1215
1216 #ifdef  DO_TAGGED_HASH
1217     fprintf(f, "dbz %d %ld %d %d %ld %ld %d %d\n", dbzversion, cp->tsize,
1218                 cp->valuesize, cp->fillpercent, cp->tagenb,
1219                 cp->tagmask, cp->tagshift, cp->dropbits);
1220 #else   /* DO_TAGGED_HASH */
1221     fprintf(f, "dbz %d %ld %d %d\n", dbzversion, cp->tsize,
1222                    cp->valuesize, cp->fillpercent);
1223 #endif  /* DO_TAGGED_HASH */
1224
1225     for (i = 0; i < NUSEDS; i++)
1226         fprintf(f, "%ld%c", cp->used[i], (i < NUSEDS-1) ? ' ' : '\n');
1227
1228 #ifdef  DO_TAGGED_HASH
1229     for (i = 0; i < NUSEDS; i++)
1230         fprintf(f, "%ld%c", cp->vused[i], (i < NUSEDS-1) ? ' ' : '\n');
1231 #endif
1232
1233     fflush(f);
1234     if (ferror(f))
1235         ret = -1;
1236
1237     debug("putconf status %d", ret);
1238     return ret;
1239 }
1240
1241 /* getcore - try to set up an in-core copy of file
1242  *
1243  * Returns: pointer to copy of file or NULL on errror
1244  */
1245 static bool
1246 getcore(hash_table *tab)
1247 {
1248     char *it;
1249     ssize_t nread;
1250     size_t i;
1251     struct stat st;
1252     size_t length = conf.tsize * tab->reclen;
1253
1254     if (tab->incore == INCORE_MMAP) {
1255 #if defined(HAVE_MMAP)
1256         if (fstat(tab->fd, &st) == -1) {
1257             syswarn("dbz: getcore: fstat failed");
1258             return false;
1259         }
1260         if (length > st.st_size) {
1261             /* file too small; extend it */
1262             if (ftruncate(tab->fd, length) == -1) {
1263                 syswarn("dbz: getcore: ftruncate failed");
1264                 return false;
1265             }
1266         }
1267         it = mmap(NULL, length, readonly ? PROT_READ : PROT_WRITE | PROT_READ,
1268                   MAP_SHARED, tab->fd, 0);
1269         if (it == (char *)-1) {
1270             syswarn("dbz: getcore: mmap failed");
1271             return false;
1272         }
1273 #if defined (MADV_RANDOM) && defined(HAVE_MADVISE)
1274         /* not present in all versions of mmap() */
1275         madvise(it, length, MADV_RANDOM);
1276 #endif
1277 #else
1278         warn("dbz: getcore: can't mmap files");
1279         return false;
1280 #endif
1281     } else {
1282         it = xmalloc(length);
1283
1284         nread = read(tab->fd, it, length);
1285         if (nread < 0) {
1286             syswarn("dbz: getcore: read failed");
1287             free(it);
1288             return false;
1289         }
1290
1291         i = length - nread;
1292         memset(it + nread, '\0', i);
1293     }
1294
1295     tab->core = it;
1296     return true;
1297 }
1298
1299 /* putcore - try to rewrite an in-core table
1300  *
1301  * Returns true on success, false on failure
1302  */
1303 static bool
1304 putcore(hash_table *tab)
1305 {
1306     size_t size;
1307     ssize_t result;
1308
1309     if (tab->incore == INCORE_MEM) {
1310         if(options.writethrough)
1311             return true;
1312         nonblocking(tab->fd, false);
1313         size = tab->reclen * conf.tsize;
1314         result = xpwrite(tab->fd, tab->core, size, 0);
1315         if (result < 0 || (size_t) result != size) {
1316             nonblocking(tab->fd, options.nonblock);
1317             return false;
1318         }
1319         nonblocking(tab->fd, options.nonblock);
1320     }
1321 #ifdef HAVE_MMAP
1322     if(tab->incore == INCORE_MMAP) {
1323         msync(tab->core, conf.tsize * tab->reclen, MS_ASYNC);
1324     }
1325 #endif
1326     return true;
1327 }
1328
1329 #ifdef  DO_TAGGED_HASH
1330 /*
1331  - makehash31 : make 31-bit hash from HASH
1332  */
1333 static unsigned int
1334 makehash31(const HASH *hash)
1335 {
1336     unsigned int h;
1337     memcpy(&h, hash, sizeof(h));
1338     return (h >> 1);
1339 }
1340 #endif
1341
1342 /* start - set up to start or restart a search
1343  * osp == NULL is acceptable
1344  */
1345 static void
1346 start(searcher *sp, const HASH hash, searcher *osp)
1347 {
1348 #ifdef  DO_TAGGED_HASH
1349     unsigned int        h;
1350
1351     h = makehash31(&hash);
1352     if (osp != FRESH && osp->shorthash == h) {
1353         if (sp != osp)
1354             *sp = *osp;
1355         sp->run--;
1356         debug("search restarted");
1357     } else {
1358         sp->shorthash = h;
1359         sp->tag = MKTAG(h / conf.tsize);
1360         sp->place = h % conf.tsize;
1361         debug("hash %8.8lx tag %8.8lx place %ld",
1362               sp->shorthash, sp->tag, sp->place);
1363         sp->tabno = 0;
1364         sp->run = -1;
1365         sp->aborted = 0;
1366     }
1367
1368 #else   /* DO_TAGGED_HASH */
1369     int tocopy;
1370
1371     if (osp != FRESH && !memcmp(&osp->hash, &hash, sizeof(hash))) {
1372         if (sp != osp)
1373             *sp = *osp;
1374         sp->run--;
1375         debug("search restarted");
1376     } else {
1377         sp->hash = hash;
1378         tocopy = sizeof(hash) < sizeof(sp->shorthash) ? sizeof(hash) : sizeof(sp->shorthash);
1379         /* Copy the bottom half of thhe hash into sp->shorthash */
1380         memcpy(&sp->shorthash, (const char *)&hash + (sizeof(hash) - tocopy),
1381                tocopy);
1382         sp->shorthash >>= 1;
1383         sp->tabno = 0;
1384         sp->run = -1;
1385         sp->aborted = 0;
1386     }
1387 #endif  /* DO_TAGGED_HASH */
1388 }
1389
1390 #ifdef  DO_TAGGED_HASH
1391 /*
1392  - search - conduct part of a search
1393  */
1394 static of_t                     /* NOTFOUND if we hit VACANT or error */
1395 search(searcher *sp)
1396 {
1397     of_t value;
1398     unsigned long taboffset = sp->tabno * conf.tsize;
1399
1400     if (sp->aborted)
1401         return(NOTFOUND);
1402
1403     for (;;) {
1404         /* go to next location */
1405         if (sp->run++ == MAXRUN) {
1406             sp->tabno++;
1407             sp->run = 0;
1408             taboffset = sp->tabno * conf.tsize;
1409         }
1410         sp->place = ((sp->shorthash + sp->run) % conf.tsize) + taboffset;
1411         debug("search @ %ld", place);
1412
1413         /* get the tagged value */
1414         if ((options.pag_incore != INCORE_NO) && (sp->place < conf.tsize)) {
1415             debug("search: in core");
1416             value = ((of_t *)pagtab.core)[sp->place];
1417         } else {
1418             off_t dest;
1419             dest = sp->place * SOF;
1420
1421             /* read it */
1422             errno = 0;
1423             if (pread(pagtab.fd, &value, sizeof(value), dest) != sizeof(value)) {
1424                 if (errno != 0) {
1425                     syswarn("dbz: search: read failed");
1426                     pagtab.pos = -1;
1427                     sp->aborted = 1;
1428                     return(NOTFOUND);
1429                 } else
1430                     value = VACANT;
1431                 pagtab.pos = -1;
1432             } else
1433                 pagtab.pos += sizeof(value);
1434         }
1435
1436         /* vacant slot is always cause to return */
1437         if (value == VACANT) {
1438             debug("search: empty slot");
1439             return(NOTFOUND);
1440         };
1441
1442         /* check the tag */
1443         value = UNBIAS(value);
1444         debug("got 0x%lx", value);
1445         if (!HASTAG(value)) {
1446             debug("tagless");
1447             return(value);
1448         } else if (TAG(value) == sp->tag) {
1449             debug("match");
1450             return(NOTAG(value));
1451         } else {
1452             debug("mismatch 0x%lx", TAG(value));
1453         }
1454     }
1455     /* NOTREACHED */
1456 }
1457
1458 #else   /* DO_TAGGED_HASH */
1459
1460 /* search - conduct part of a search
1461  *
1462  * return false if we hit vacant rec's or error
1463  */
1464 static bool
1465 search(searcher *sp)
1466 {
1467     erec value;
1468     unsigned long taboffset = 0;
1469
1470     if (sp->aborted)
1471         return false;
1472
1473     for (;;) {
1474         /* go to next location */
1475         if (sp->run++ == MAXRUN) {
1476             sp->tabno++;
1477             sp->run = 0;
1478             taboffset = sp->tabno * conf.tsize;
1479         }
1480
1481         sp->place = ((sp->shorthash + sp->run) % conf.tsize) + taboffset;
1482         debug("search @ %ld", (long) sp->place);
1483
1484         /* get the value */
1485         if ((options.exists_incore != INCORE_NO) && (sp->place < conf.tsize)) {
1486             debug("search: in core");
1487             memcpy(&value, &((erec *)etab.core)[sp->place], sizeof(erec));
1488         } else {
1489             off_t dest;
1490             dest = sp->place * sizeof(erec);
1491
1492             /* read it */
1493             errno = 0;
1494             if (pread(etab.fd, &value, sizeof(erec), dest) != sizeof(erec)) {
1495                 if (errno != 0) {
1496                     debug("search: read failed");
1497                     etab.pos = -1;
1498                     sp->aborted = 1;
1499                     return false;
1500                 } else {
1501                     memset(&value, '\0', sizeof(erec));
1502                 }
1503             }
1504
1505             /* and finish up */
1506             etab.pos += sizeof(erec);
1507         }
1508
1509         /* Check for an empty record */
1510         if (!memcmp(&value, &empty_rec, sizeof(erec))) {
1511             debug("search: empty slot");
1512             return false;
1513         }
1514
1515         /* check the value */
1516         debug("got 0x%.*s", DBZ_INTERNAL_HASH_SIZE, value.hash);
1517         if (!memcmp(&value.hash, &sp->hash, DBZ_INTERNAL_HASH_SIZE)) {
1518             return true;
1519         }
1520     }
1521     /* NOTREACHED */
1522 }
1523 #endif  /* DO_TAGGED_HASH */
1524
1525 /* set - store a value into a location previously found by search
1526  *
1527  * Returns:  true success, false failure
1528  */
1529 static bool
1530 set(searcher *sp, hash_table *tab, void *value)
1531 {
1532     off_t offset;
1533
1534     if (sp->aborted)
1535         return false;
1536
1537     /* If we have the index file in memory, use it */
1538     if ((tab->incore != INCORE_NO) && (sp->place < conf.tsize)) {
1539         void *where = (char *)tab->core + (sp->place * tab->reclen);
1540
1541         memcpy(where, value, tab->reclen);
1542         debug("set: incore");
1543         if (tab->incore == INCORE_MMAP) {
1544             if (innconf->nfswriter) {
1545                 inn_mapcntl(where, tab->reclen, MS_ASYNC);
1546             }
1547             return true;
1548         }
1549         if (!options.writethrough)
1550             return true;
1551     }
1552
1553     /* seek to spot */
1554     tab->pos = -1;              /* invalidate position memory */
1555     offset = sp->place * tab->reclen;
1556
1557     /* write in data */
1558     while (pwrite(tab->fd, value, tab->reclen, offset) != tab->reclen) {
1559         if (errno == EAGAIN) {
1560             fd_set writeset;
1561
1562             FD_ZERO(&writeset);
1563             FD_SET(tab->fd, &writeset);
1564             if (select(tab->fd + 1, NULL, &writeset, NULL, NULL) < 1) {
1565                 syswarn("dbz: set: select failed");
1566                 sp->aborted = 1;
1567                 return false;
1568             }
1569             continue;
1570         }
1571         syswarn("dbz: set: write failed");
1572         sp->aborted = 1;
1573         return false;
1574     }
1575
1576     debug("set: succeeded");
1577     return true;
1578 }
1579
1580 #ifdef  DO_TAGGED_HASH
1581 /*
1582  - set_pag - store a value into a location previously found by search
1583  -       on the pag table.
1584  - Returns: true success, false failure
1585  */
1586 static bool
1587 set_pag(searcher *sp, of_t value)
1588 {
1589     of_t v = value;
1590
1591     if (CANTAG(v)) {
1592         v |= sp->tag | taghere;
1593         if (v != UNBIAS(VACANT))        /* BIAS(v) won't look VACANT */
1594 #ifdef OVERFLOW
1595             if (v != LONG_MAX)          /* and it won't overflow */
1596 #endif
1597                 value = v;
1598     } else if (canttag_warned == 0) {
1599         fprintf(stderr, "dbz.c(set): can't tag value 0x%lx", v);
1600         fprintf(stderr, " tagboth = 0x%lx\n", tagboth);
1601         canttag_warned = 1;
1602     }
1603     debug("tagged value is 0x%lx", value);
1604     value = BIAS(value);
1605
1606     return set(sp, &pagtab, &value);
1607 }
1608 #endif  /* DO_TAGGED_HASH */
1609
1610 /* dbzsetoptions - set runtime options for the database.
1611  */
1612 void
1613 dbzsetoptions(const dbzoptions o)
1614 {
1615     options = o;
1616 #ifndef HAVE_MMAP
1617     /* Without a working mmap on files, we should avoid it. */
1618     if (options.pag_incore == INCORE_MMAP) options.pag_incore = INCORE_NO;
1619     if (options.exists_incore == INCORE_MMAP) options.exists_incore = INCORE_NO;
1620 #endif
1621 }
1622
1623 /* dbzgetoptions - get runtime options for the database.
1624  */
1625 void
1626 dbzgetoptions(dbzoptions *o)
1627 {
1628     *o = options;
1629 }
1630
1631
1632 #ifdef DBZTEST
1633
1634 int
1635 timediffms(struct timeval start, struct timeval end)
1636 {
1637     return (((end.tv_sec - start.tv_sec) * 1000) +
1638             ((end.tv_usec - start.tv_usec)) / 1000);
1639 }
1640
1641 void
1642 RemoveDBZ(char *filename)
1643 {
1644     char *fn;
1645
1646 #ifdef DO_TAGGED_HASH
1647     fn = concat(filename, pag, (char *) 0);
1648     unlink(fn);
1649     free(fn);
1650 #else
1651     fn = concat(filename, exists, (char *) 0);
1652     unlink(fn);
1653     free(fn);
1654     fn = concat(filename, idx, (char *) 0);
1655     unlink(fn);
1656     free(fn);
1657 #endif
1658     fn = concat(filename, dir, (char *) 0);
1659     unlink(fn);
1660     free(fn);
1661 }
1662
1663 static void
1664 usage(void)
1665 {
1666     fprintf(stderr, "usage: dbztest [-i] [-n|m] [-N] [-s size] <history>\n");
1667 #ifdef DO_TAGGED_HASH
1668     fprintf(stderr, "  -i       initialize history. deletes .pag files\n");
1669 #else
1670     fprintf(stderr, "  -i       initialize history. deletes .exists and .index files\n");
1671 #endif
1672     fprintf(stderr, "  -n or m  use INCORE_NO, INCORE_MMAP. default = INCORE_MEM\n");
1673     fprintf(stderr, "  -N       using nfswriter mode\n");
1674     fprintf(stderr, "  -s size  number of history lines[2500000]\n");
1675     fprintf(stderr, "  history  history text file\n");
1676     exit(1);
1677 }
1678
1679 int
1680 main(int argc, char *argv[])
1681 {
1682     int  i, line;
1683     FILE *fpi;
1684     char ibuf[2048], *p;
1685     HASH key;
1686     off_t where;
1687     int  initialize = 0, size = 2500000;
1688     char *history = NULL;
1689     dbzoptions opt;
1690     dbz_incore_val incore = INCORE_MEM;
1691     struct timeval start, end;
1692     off_t ivalue;
1693
1694     innconf = xcalloc(1, sizeof(struct innconf));
1695
1696     for (i=1; i<argc; i++)
1697         if (strcmp(argv[i], "-i") == 0)
1698             initialize = 1;
1699         else if (strcmp(argv[i], "-n") == 0)
1700             incore = INCORE_NO;
1701         else if (strcmp(argv[i], "-N") == 0)
1702             innconf->nfswriter = true;
1703         else if (strcmp(argv[i], "-m") == 0)
1704 #if defined(HAVE_MMAP)
1705             incore = INCORE_MMAP;
1706 #else
1707             fprintf (stderr, "can't mmap files\n");
1708 #endif
1709         else if (strcmp(argv[i], "-s") == 0)
1710             size = atoi(argv[++i]);
1711         else if (*argv[i] != '-' && history == NULL)
1712             history = argv[i];
1713         else
1714             usage();
1715
1716     if (history == NULL)
1717         usage();
1718     if ((fpi = fopen(history, "r")) == NULL) {
1719         fprintf(stderr, "can't open %s\n", history);
1720         usage();
1721     }
1722
1723     dbzgetoptions(&opt);
1724     opt.pag_incore = incore;
1725     dbzsetoptions(opt);
1726
1727     if (initialize) {
1728         RemoveDBZ(history);
1729         gettimeofday(&start, NULL);
1730         if (dbzfresh(history, dbzsize(size)) < 0) {
1731             fprintf(stderr, "cant dbzfresh %s\n", history);
1732             exit(1);
1733         }
1734         gettimeofday(&end, NULL);
1735         printf("dbzfresh: %d msec\n", timediffms(start, end));
1736     } else {
1737         gettimeofday(&start, NULL);
1738         if (dbzinit(history) < 0) {
1739             fprintf(stderr, "cant dbzinit %s\n", history);
1740             exit(1);
1741         }
1742         gettimeofday(&end, NULL);
1743         printf("dbzinit: %d msec\n", timediffms(start, end));
1744     }
1745
1746     gettimeofday(&start, NULL);
1747     where = ftello(fpi);
1748     for (line=1; fgets(ibuf, sizeof(ibuf), fpi); line++, where=ftello(fpi)) {
1749         if (*ibuf == '<') {
1750             if ((p = strchr(ibuf, '\t')) == NULL) {
1751                 fprintf(stderr, "ignoreing bad line: %s\n", ibuf);
1752                 continue;
1753             }
1754             *p = '\0';
1755             key = HashMessageID(ibuf);
1756         } else if (*ibuf == '[')
1757             key = TextToHash(ibuf+1);
1758         else
1759             continue;
1760         if (initialize) {
1761             if (dbzstore(key, where) == DBZSTORE_ERROR) {
1762                 fprintf(stderr, "cant store %s\n", ibuf);
1763                 exit(1);
1764             }
1765         } else {
1766             if (!dbzfetch(key, &ivalue)) {
1767                     fprintf(stderr, "line %d can't fetch %s\n", line, ibuf);
1768                     exit(1);
1769                 }
1770         }
1771     }
1772     line--;
1773     gettimeofday(&end, NULL);
1774     i = timediffms(start, end);
1775     printf("%s: %d lines %.3f msec/id\n",
1776         (initialize) ? "dbzstore" : "dbzfetch",
1777         line, (double)i / (double)line);
1778
1779     gettimeofday(&end, NULL);
1780     dbzclose();
1781     gettimeofday(&end, NULL);
1782     printf("dbzclose: %d msec\n", timediffms(start, end));
1783     return(0);
1784 }
1785 #endif  /* DBZTEST */