src/budb/db_hash.c

   1 /*
   2  * Copyright 2000, International Business Machines Corporation and others.
   3  * All Rights Reserved.
   4  *
   5  * This software has been released under the terms of the IBM Public
   6  * License.  For details, see the LICENSE file in the top-level source
   7  * directory or online at http://www.openafs.org/dl/license10.html
   8  */
   9
  10 #include <afsconfig.h>
  11 #include <afs/param.h>
  12
  13 RCSID
  14     ("$Header$");
  15
  16 #ifdef AFS_NT40_ENV
  17 #include <winsock2.h>
  18 #else
  19 #include <netinet/in.h>
  20 #endif
  21 #include <string.h>
  22 #include <sys/types.h>
  23 #include <afs/stds.h>
  24 #include <ubik.h>
  25 #include <afs/bubasics.h>
  26 #include "budb_errs.h"
  27 #include "database.h"
  28 #include "error_macros.h"
  29
  30
  31 int sizeFunctions[HT_MAX_FUNCTION + 1];
  32 int nHTBuckets = NhtBucketS;    /* testing: we need small HT blocks */
  33
  34 /* ht_TableSize - return the size of table necessary to represent a hashtable
  35  * of given length in memory.  It basically rounds the length up by the number
  36  * of buckets per block. */
  37
  38 int
  39 ht_TableSize(length)
  40      int length;
  41 {
  42     int n;
  43     if (length == 0)
  44         return 0;
  45     n = (length + nHTBuckets - 1) / nHTBuckets;
  46     return n * sizeof(struct memoryHTBlock *);
  47 }
  48
  49 /* ht_ResetT - resets the in-memory representation of a hashtable block array.
  50  * It also resets the global variable nHTBuckets. */
  51
  52 static void
  53 ht_ResetT(blocksP, sizeP, length)
  54      struct memoryHTBlock ***blocksP;
  55      int *sizeP;
  56      int length;
  57 {
  58     struct memoryHTBlock **b = *blocksP;
  59     int newsize;
  60     int n;
  61     int i;
  62
  63     nHTBuckets = ntohl(db.h.nHTBuckets);
  64     if (b) {
  65         n = *sizeP / sizeof(b[0]);
  66         newsize = ht_TableSize(length);
  67         if (*sizeP != newsize) {
  68             /* free all blocks in the old array */
  69             for (i = 0; i < n; i++)
  70                 if (b[i])
  71                     free(b[i]);
  72             free(b);
  73             *sizeP = 0;
  74             *blocksP = 0;
  75         } else {
  76             /* invalidate the blocks of the array  */
  77             for (i = 0; i < n; i++)
  78                 if (b[i])
  79                     b[i]->valid = 0;
  80         }
  81     }
  82 }
  83
  84 /* ht_Reset
  85  *      reinitialize a memory hash table.
  86  *      Calls ht_ResetT to invalidate the two block arrays.
  87  */
  88
  89 void
  90 ht_Reset(mht)
  91      struct memoryHashTable *mht;
  92 {
  93     struct hashTable *ht;
  94
  95     if (!(mht && (ht = mht->ht)))
  96         db_panic("some ht called with bad mht");
  97     mht->threadOffset = ntohl(ht->threadOffset);
  98     mht->length = ntohl(ht->length);
  99     mht->oldLength = ntohl(ht->oldLength);
 100     mht->progress = ntohl(ht->progress);
 101     ht_ResetT(&mht->blocks, &mht->size, mht->length);
 102     ht_ResetT(&mht->oldBlocks, &mht->oldSize, mht->oldLength);
 103 }
 104
 105 /* InitDBhash - When server starts, do hash table initialization.
 106      test - initialization parameters: bit 4 is small ht. */
 107
 108 afs_int32
 109 InitDBhash()
 110 {
 111     sizeFunctions[0] = 0;
 112
 113     sizeFunctions[HT_dumpIden_FUNCTION] = sizeof(struct dump);
 114     sizeFunctions[HT_dumpName_FUNCTION] = sizeof(struct dump);
 115     sizeFunctions[HT_volName_FUNCTION] = sizeof(struct volInfo);
 116     sizeFunctions[HT_tapeName_FUNCTION] = sizeof(struct tape);
 117
 118     db.volName.ht = &db.h.volName;
 119     db.tapeName.ht = &db.h.tapeName;
 120     db.dumpName.ht = &db.h.dumpName;
 121     db.dumpIden.ht = &db.h.dumpIden;
 122     return 0;
 123 }
 124
 125 /* ht_DBInit - When rebuilding database, this sets up the hash tables. */
 126
 127 void
 128 ht_DBInit()
 129 {
 130     db.h.nHTBuckets = htonl(nHTBuckets);
 131
 132     {
 133         struct volInfo *s = 0;
 134         db.h.volName.threadOffset =
 135             htonl((char *)&s->nameHashChain - (char *)s);
 136         db.h.volName.functionType = htonl(HT_volName_FUNCTION);
 137     }
 138     {
 139         struct tape *s = 0;
 140         db.h.tapeName.threadOffset =
 141             htonl((char *)&s->nameHashChain - (char *)s);
 142         db.h.tapeName.functionType = htonl(HT_tapeName_FUNCTION);
 143     }
 144     {
 145         struct dump *s = 0;
 146         db.h.dumpName.threadOffset =
 147             htonl((char *)&s->nameHashChain - (char *)s);
 148         db.h.dumpName.functionType = htonl(HT_dumpName_FUNCTION);
 149
 150         db.h.dumpIden.threadOffset =
 151             htonl((char *)&s->idHashChain - (char *)s);
 152         db.h.dumpIden.functionType = htonl(HT_dumpIden_FUNCTION);
 153     }
 154     ht_Reset(&db.volName);
 155     ht_Reset(&db.tapeName);
 156     ht_Reset(&db.dumpName);
 157     ht_Reset(&db.dumpIden);
 158 }
 159
 160 afs_int32
 161 ht_AllocTable(ut, mht)
 162      struct ubik_trans *ut;
 163      struct memoryHashTable *mht;
 164 {
 165     struct hashTable *ht;
 166     afs_int32 code;
 167     int len;
 168     int nb, mnb;                /* number of blocks for hashTable */
 169     int i;
 170     struct memoryHTBlock **b;
 171
 172     if (!(mht && (ht = mht->ht)))
 173         db_panic("some ht called with bad mht");
 174     if (ht->length || mht->blocks)
 175         db_panic("previous table still allocated");
 176
 177     len = ntohl(ht->entries) * 2;       /* allow room to grow */
 178     nb = (len + nHTBuckets - 1) / nHTBuckets;
 179     mnb = ht_minHBlocks(mht);
 180     if (nb < mnb)
 181         nb = mnb;               /* use minimum */
 182     len = nb * nHTBuckets;      /* new hash table length */
 183
 184     mht->size = nb * sizeof(struct memoryHTBlock *);
 185     b = mht->blocks = (struct memoryHTBlock **)malloc(mht->size);
 186     memset(b, 0, mht->size);
 187
 188     for (i = 0; i < nb; i++) {
 189         b[i] = (struct memoryHTBlock *)malloc(sizeof(struct memoryHTBlock));
 190         code = AllocBlock(ut, (struct block *)&b[i]->b, &b[i]->a);
 191         if (code)
 192             return code;
 193         b[i]->valid = 0;
 194
 195         b[i]->b.h.type = hashTable_BLOCK;
 196
 197         /* thread the blocks */
 198         if (i)
 199             b[i - 1]->b.h.next = htonl(b[i]->a);
 200     }
 201     for (i = 0; i < nb; i++) {
 202         code =
 203             dbwrite(ut, b[i]->a, (char *)&b[i]->b,
 204                     sizeof(struct htBlock) + (nHTBuckets -
 205                                               NhtBucketS) * sizeof(dbadr));
 206         if (code)
 207             return code;
 208     }
 209     if (code = set_word_addr(ut, 0, &db.h, &ht->table, htonl(b[0]->a)))
 210         return code;
 211
 212     if (code = set_word_addr(ut, 0, &db.h, &ht->length, htonl(len)))
 213         return code;
 214     mht->length = len;
 215     return 0;
 216 }
 217
 218 afs_int32
 219 ht_FreeTable(ut, mht)
 220      struct ubik_trans *ut;
 221      struct memoryHashTable *mht;
 222 {
 223     struct hashTable *ht;
 224     afs_int32 code;
 225     struct blockHeader bh;
 226     dbadr a, na;
 227
 228     if (!(mht && (ht = mht->ht)))
 229         db_panic("some ht called with bad mht");
 230     if (ht->oldLength == 0)
 231         db_panic("no table to free");
 232
 233     ht_ResetT(&mht->oldBlocks, &mht->oldSize, 0);
 234
 235     for (a = ntohl(ht->oldTable); a; a = na) {
 236         if (dbread(ut, a, (char *)&bh, sizeof(bh))) {
 237             Log("ht_FreeTable: dbread failed\n");
 238             return BUDB_IO;
 239         }
 240         na = ntohl(bh.next);
 241         if (code = FreeBlock(ut, &bh, a))
 242             return code;
 243     }
 244     if (set_word_addr(ut, 0, &db.h, &ht->oldTable, 0)
 245         || set_word_addr(ut, 0, &db.h, &ht->oldLength, 0)
 246         || set_word_addr(ut, 0, &db.h, &ht->progress, 0))
 247         return BUDB_IO;
 248     mht->oldLength = mht->progress = 0;
 249     return 0;
 250 }
 251
 252 afs_int32
 253 ht_GetTableBlock(ut, mht, hash, old, blockP, boP)
 254      struct ubik_trans *ut;
 255      struct memoryHashTable *mht;
 256      afs_uint32 hash;
 257      int old;
 258      struct memoryHTBlock **blockP;
 259      int *boP;
 260 {
 261     struct hashTable *ht;
 262     struct memoryHTBlock **b;
 263     int hi, bi;
 264     struct memoryHTBlock ***blocksP;
 265     int *sizeP;
 266     int n;
 267     int i;
 268     int length;
 269     dbadr ta;
 270
 271     if ((mht == 0)
 272         || ((ht = mht->ht) == 0)
 273         ) {
 274         db_panic("some ht called with bad mht");
 275     }
 276
 277     *blockP = 0;
 278
 279     if (old) {
 280         if ((length = mht->oldLength) == 0)
 281             return 0;           /* no entries */
 282         hi = hash % length;
 283         if (hi < mht->progress)
 284             return 0;           /* no such entry */
 285         blocksP = &mht->oldBlocks;
 286         sizeP = &mht->oldSize;
 287     } else {
 288         if ((length = mht->length) == 0)
 289             return 0;           /* no entries */
 290         hi = hash % length;
 291         blocksP = &mht->blocks;
 292         sizeP = &mht->size;
 293     }
 294
 295     bi = hi / nHTBuckets;       /* block index */
 296     *boP = hi - bi * nHTBuckets;        /* block offset ptr */
 297
 298     if (*blocksP == 0) {
 299         *sizeP = ht_TableSize(length);
 300         *blocksP = (struct memoryHTBlock **)malloc(*sizeP);
 301         memset(*blocksP, 0, *sizeP);
 302     }
 303     n = *sizeP / sizeof(struct memoryHTBlock *);
 304     if (bi >= n)
 305         db_panic("table size inconsistent");
 306     b = *blocksP;
 307
 308     /* find an allocated block or the beginning of the block array */
 309     for (i = bi; (i > 0) && (b[i] == 0); i--);
 310
 311     while (1) {
 312         if (b[i] == 0) {
 313             if (i == 0) {       /* the first block is found from the hashTable */
 314                 ta = ntohl(old ? ht->oldTable : ht->table);
 315                 if (ta == 0)
 316                     db_panic("non-zero length, but no table");
 317             }
 318             /* else ta is set from last time around loop */
 319             b[i] =
 320                 (struct memoryHTBlock *)malloc(sizeof(struct memoryHTBlock));
 321             b[i]->a = ta;
 322             b[i]->valid = 0;
 323         }
 324
 325         if (!b[i]->valid) {
 326             if (dbread(ut, b[i]->a, (char *)&b[i]->b, sizeof(struct htBlock)))
 327                 return BUDB_IO;
 328             b[i]->valid = 1;
 329         }
 330
 331         if (i == bi) {
 332             *blockP = b[bi];
 333             /* printf("ht_GetTableBlock: hash %d block %d offset %d\n",
 334              * hash, *blockP, *boP); */
 335             return 0;
 336         }
 337
 338         ta = ntohl(b[i++]->b.h.next);   /* get next ptr from current block */
 339     }
 340 }
 341
 342 /* ht_MaybeAdjust
 343  *      Decide when to push the current hash table to the old hash table.
 344  *      The entries in the old hash table are VALID, and are slowly hashed
 345  *      into the current table.
 346  */
 347
 348 static afs_int32
 349 ht_MaybeAdjust(ut, mht)
 350      struct ubik_trans *ut;
 351      struct memoryHashTable *mht;
 352 {
 353     struct hashTable *ht = mht->ht;
 354     int numberEntries = ntohl(ht->entries);
 355
 356     /* old hash table must be empty */
 357     if (mht->oldLength != 0)
 358         return (0);
 359
 360     /*
 361      * It costs a lot to grow and shrink the hash table. Therefore, we will not
 362      * shrink the hash table (only grow it). If the table is more than 2 entries per
 363      * chain (average) we need to grow: push the entries to the old hash table.
 364      *
 365      * Don't shrink it:
 366      * || ((mht->length > nHTBuckets) && (numberEntries*8 < mht->length))
 367      */
 368
 369     /* Only grow a hash table if the number of entries is twice the
 370      * number of hash length and is less than 20,450 (20 hash blocks). This
 371      * means that the volname hash table will not grow (its initial
 372      * hashtable size contains 30,600 buckets). Earlier revisions of
 373      * the buserver have the initial size at 510 and 5,100 buckets -
 374      * in which case we do want to grow it). We don't grow anything larger
 375      * than 20,450 entries because it's expensive to re-hash everything.
 376      */
 377     if ((numberEntries > mht->length * 2) && (numberEntries < 20450)) { /* push current hash table to old hash table */
 378         ht->oldLength = ht->length;
 379         ht->oldTable = ht->table;
 380         ht->progress = 0;
 381         ht->length = 0;
 382         ht->table = 0;
 383         if (dbwrite
 384             (ut, ((char *)ht - (char *)&db.h), (char *)ht, sizeof(*ht)))
 385             return BUDB_IO;
 386
 387         ht_Reset(mht);
 388         LogDebug(2, "ht_MaybeAdjust: push ht to old\n");
 389     }
 390     return 0;
 391 }
 392
 393 dbadr
 394 ht_LookupBucket(ut, mht, hash, old)
 395      struct ubik_trans *ut;
 396      struct memoryHashTable *mht;
 397      afs_uint32 hash;
 398      int old;
 399 {
 400     struct memoryHTBlock *block;
 401     int bo;
 402     afs_int32 code;
 403
 404     if ((old ? mht->oldLength : mht->length) == 0)
 405         return 0;
 406     code = ht_GetTableBlock(ut, mht, hash, old, &block, &bo);
 407     if (code || (block == 0))
 408         return 0;
 409     return ntohl(block->b.bucket[bo]);
 410 }
 411
 412 /* This function is not too bad, for small hash tables, but suffers, I think,
 413  * from insufficient mixing of the hash information. */
 414
 415 afs_uint32
 416 Old2StringHashFunction(str)
 417      unsigned char *str;
 418 {
 419     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
 420     while (*str)
 421         hash = (hash << 1) + (hash >> 31) + *str++;
 422     return hash;
 423 }
 424
 425 /* This was actually a coding error, and produces dreadful results.  The
 426  * problem is that the hash needs to be mixed up not the incoming character. */
 427
 428 afs_uint32
 429 Old3StringHashFunction(str)
 430      unsigned char *str;
 431 {
 432     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
 433     while (*str)
 434         hash += (*str++) * 0x072a51a4;
 435     return hash;
 436 }
 437
 438 /* This function is pretty good.  Its main problem is that the low two bits of
 439  * the hash multiplier are zero which tends to shift information too far left.
 440  * It behaves especially badly for hash tables whose size is a power of two. */
 441
 442 afs_uint32
 443 Old4StringHashFunction(str)
 444      unsigned char *str;
 445 {
 446     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
 447     while (*str)
 448         hash = (*str++) + hash * 0x072a51a4;
 449     return hash;
 450 }
 451
 452 /* While this is good for a hash table with 500 buckets it is nearly as bad as
 453  * #3 with a hash table as big as 8200. */
 454
 455 afs_uint32
 456 Old5StringHashFunction(str)
 457      unsigned char *str;
 458 {
 459     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
 460     while (*str)
 461         hash += (*str++);
 462     return hash;
 463 }
 464
 465 /* This was an attempt to produce a hash function with the smallest and
 466  * simplest mixing multiplier.  This is only a little worse than the real one,
 467  * and the difference seems to be smaller with larger hash tables.  It behaves
 468  * better than the random hash function. */
 469
 470 afs_uint32
 471 Old6StringHashFunction(str)
 472      unsigned char *str;
 473 {
 474     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
 475     while (*str)
 476         hash = hash * 0x81 + (*str++);
 477     return hash;
 478 }
 479
 480 /* This actually seems to be little better then the real one.  Having the same
 481  * number of bits but only 5 bits apart seems to produce worse results but
 482  * having the bits spanning the same range farther apart also doesn't do as
 483  * well.  All these differences are fairly small, however. */
 484
 485 afs_uint32
 486 Old7StringHashFunction(str)
 487      unsigned char *str;
 488 {
 489     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
 490     while (*str)
 491         hash = hash * 0x42108421 + (*str++);
 492     return hash;
 493 }
 494
 495 /* This function tries to provide some non-linearity by providing some feedback
 496  * from higher-order bits in the word.  It also uses shifts instead of
 497  * multiplies, which may be faster on some architectures. */
 498
 499 afs_uint32
 500 Old8StringHashFunction(str)
 501      unsigned char *str;
 502 {
 503     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
 504     while (*str)
 505         hash =
 506             hash + (hash << 7) + (hash << 14) + (hash << 21) + (hash << 28) +
 507             (hash >> 17) + *str++;
 508     return hash;
 509 }
 510
 511 /* This is the result of the above search for good hash functions.  It seems
 512  * that the choice of multipliers is somewhat arbitrary but has several
 513  * constraints.  It shouldn't have too many or too few one bits and should be
 514  * odd.  It behaves beeter than the random hash function. */
 515
 516 afs_uint32
 517 StringHashFunction(str)
 518      unsigned char *str;
 519 {
 520     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
 521     /* The multiplicative constant should be odd and have a goodly number of
 522      * one bits. */
 523     while (*str)
 524         hash = (*str++) + hash * 0x10204081;
 525     return hash;
 526 }
 527
 528 afs_uint32
 529 IdHashFunction(id)
 530      afs_uint32 id;
 531 {
 532     afs_uint32 l, r;
 533     id *= 81847;
 534     l = id | 0xaaaaaaaa;
 535     r = id | 0x55555555;
 536     return (l * r);
 537 }
 538
 539 /* The minimum hash table blocks to allocate. Each block contains 510
 540  * buckets. They hash table grows when the number of entries reaches
 541  * twice the number of buckets.
 542  */
 543 int
 544 ht_minHBlocks(mht)
 545      struct memoryHashTable *mht;
 546 {
 547     int retval;
 548
 549     switch (ntohl(mht->ht->functionType)) {
 550     case HT_dumpIden_FUNCTION:
 551     case HT_dumpName_FUNCTION:  /* hash table able to handle (befor it grows) ... */
 552         retval = 2;             /*     1,020 dump entries */
 553         break;
 554
 555     case HT_tapeName_FUNCTION:
 556         retval = 4;             /*      2,040 tape entries */
 557         break;
 558
 559     case HT_volName_FUNCTION:
 560         retval = 60;            /*     61,200 volInfo entries (with different names) */
 561         break;
 562
 563     default:
 564         db_panic("Illegal hash function type");
 565     }
 566     return (retval);
 567 }
 568
 569 afs_uint32
 570 ht_HashEntry(mht, e)
 571      struct memoryHashTable *mht;
 572      char *e;                   /* entry's address (in b) */
 573 {
 574     int type = ntohl(mht->ht->functionType);
 575     afs_uint32 retval;
 576
 577     switch (type) {
 578     case HT_dumpIden_FUNCTION:
 579         retval = IdHashFunction(ntohl(((struct dump *)e)->id));
 580         LogDebug(5, "HashEntry: dumpid returns %d\n", retval);
 581         break;
 582
 583     case HT_dumpName_FUNCTION:
 584         retval = StringHashFunction(((struct dump *)e)->dumpName);
 585         LogDebug(5, "HashEntry: dumpname returns %d\n", retval);
 586         break;
 587
 588     case HT_tapeName_FUNCTION:
 589         retval = StringHashFunction(((struct tape *)e)->name);
 590         LogDebug(5, "HashEntry: tapename returns %d\n", retval);
 591         break;
 592
 593     case HT_volName_FUNCTION:
 594         retval = StringHashFunction(((struct volInfo *)e)->name);
 595         LogDebug(5, "HashEntry: volname returns %d\n", retval);
 596         break;
 597
 598     default:
 599         db_panic("illegal hash function");
 600     }
 601
 602     return (retval);
 603 }
 604
 605
 606 /* ht_GetType
 607  *      returns a ptr to the memory hash table for the specified hash
 608  *      list.
 609  */
 610
 611 struct memoryHashTable *
 612 ht_GetType(type, e_sizeP)
 613      int type;
 614      int *e_sizeP;
 615 {
 616     struct memoryHashTable *mht;
 617
 618     if ((type <= 0) || (type > HT_MAX_FUNCTION))
 619         return 0;
 620
 621     if (e_sizeP)
 622         *e_sizeP = sizeFunctions[type];
 623     switch (type) {
 624     case HT_dumpIden_FUNCTION:
 625         mht = &db.dumpIden;
 626         break;
 627
 628     case HT_dumpName_FUNCTION:
 629         mht = &db.dumpName;
 630         break;
 631
 632     case HT_tapeName_FUNCTION:
 633         mht = &db.tapeName;
 634         break;
 635
 636     case HT_volName_FUNCTION:
 637         mht = &db.volName;
 638         break;
 639
 640     default:
 641         return 0;
 642     }
 643     if (ntohl(mht->ht->functionType) != type)
 644         db_panic("ht types don't match");
 645     return mht;
 646 }
 647
 648 static int
 649 ht_KeyMatch(type, key, e)
 650      int type;
 651      char *key;
 652      char *e;
 653 {
 654     switch (type) {
 655     case HT_dumpIden_FUNCTION:
 656         return *(dumpId *) key == ntohl(((struct dump *)e)->id);
 657     case HT_dumpName_FUNCTION:
 658         return strcmp(key, ((struct dump *)e)->dumpName) == 0;
 659     case HT_tapeName_FUNCTION:
 660         return strcmp(key, ((struct tape *)e)->name) == 0;
 661     case HT_volName_FUNCTION:
 662         return strcmp(key, ((struct volInfo *)e)->name) == 0;
 663
 664     default:
 665         db_panic("illegal hash function");
 666     }
 667     /* not reached */
 668     return 0;
 669 }
 670
 671 /* ht_LookupEntry
 672  * entry:
 673  *      ut - ubik transaction
 674  *      mht - memory hash table ptr
 675  *      key - hash and lookup key
 676  * exit:
 677  *      eaP - dbaddr of entry found or zero if failed
 678   *     e - contents of located entry
 679  */
 680
 681 afs_int32
 682 ht_LookupEntry(ut, mht, key, eaP, e)
 683      struct ubik_trans *ut;
 684      struct memoryHashTable *mht;
 685      char *key;                 /* pointer to lookup key to match */
 686      dbadr *eaP;                /* db addr of entry found or zero */
 687      char *e;                   /* contents of located entry */
 688 {
 689     struct hashTable *ht;
 690     int type;
 691     int e_size;
 692     int old;
 693     afs_uint32 hash;
 694     dbadr a;
 695
 696     if (!key || !eaP || !e)
 697         db_panic("null ptrs passed to LookupEntry");
 698     if (!(mht && (ht = mht->ht)))
 699         db_panic("some ht called with bad mht");
 700
 701     *eaP = 0;                   /* initialize not-found indicator */
 702
 703     type = ntohl(ht->functionType);
 704     e_size = sizeFunctions[type];
 705     if (type == HT_dumpIden_FUNCTION)
 706         hash = IdHashFunction(*(dumpId *) key);
 707     else
 708         hash = StringHashFunction(key);
 709
 710     for (old = 0;; old++) {
 711         a = ht_LookupBucket(ut, mht, hash, old);
 712         while (a) {
 713             if (dbread(ut, a, e, e_size))
 714                 return BUDB_IO;
 715             if (ht_KeyMatch(type, key, e)) {
 716                 *eaP = a;
 717                 return 0;
 718             }
 719             a = ntohl(*(dbadr *) (e + mht->threadOffset));
 720         }
 721         if (old)
 722             return 0;
 723     }
 724 }
 725
 726 /* ht_HashInList
 727  * entry:
 728  *      opQuota - max # of items to move
 729  * exit:
 730  *      opQuota - adjusted to reflect # of moves
 731  */
 732
 733 static afs_int32
 734 ht_HashInList(ut, mht, opQuota, block, blockOffset)
 735      struct ubik_trans *ut;
 736      struct memoryHashTable *mht;
 737      int *opQuota;
 738      struct memoryHTBlock *block;
 739      int blockOffset;
 740 {
 741     struct hashTable *ht = mht->ht;
 742     afs_int32 code;
 743     dbadr ea, next_ea;
 744     dbadr listA;
 745     char e[sizeof(struct block)];       /* unnecessarily conservative */
 746     int e_size = sizeFunctions[ntohl(ht->functionType)];
 747
 748     if (mht->length == 0) {
 749         if (code = ht_AllocTable(ut, mht)) {
 750             Log("ht_HashInList: ht_AllocTable failed\n");
 751             return code;
 752         }
 753     }
 754
 755     listA = ntohl(block->b.bucket[blockOffset]);
 756
 757     if (listA == 0) {
 758         Log("ht_HashInList: expecting non-zero bucket\n");
 759         return 0;
 760     }
 761
 762     for (ea = listA; ea; ea = next_ea) {        /*f */
 763
 764         LogDebug(3, "ht_HashInList: move entry at %d, type %d\n", ea,
 765                  ntohl(mht->ht->functionType));
 766
 767         if (dbread(ut, ea, e, e_size))
 768             return BUDB_IO;
 769
 770         /* LogNetDump((struct dump *) e); */
 771
 772         /* get the address of the next item on the list */
 773         next_ea = ntohl(*(dbadr *) (e + mht->threadOffset));
 774
 775         /* write the link into the bucket */
 776         code =
 777             set_word_addr(ut, block->a, &block->b,
 778                           &block->b.bucket[blockOffset], htonl(next_ea));
 779         if (code) {
 780             Log("ht_HashInList: bucket update failed\n");
 781             return (code);
 782         }
 783
 784         {
 785             struct memoryHTBlock *block;
 786             int bo;
 787             afs_uint32 hash;
 788
 789             /* get the hash value */
 790             hash = ht_HashEntry(mht, e) % mht->length;
 791             LogDebug(4, "ht_HashInList: moved to %d\n", hash);
 792
 793             /* get the new hash table block */
 794             code = ht_GetTableBlock(ut, mht, hash, 0 /*old */ , &block, &bo);
 795             if (code) {
 796                 Log("ht_HashInList: ht_GetTableBlock failed\n");
 797                 return code;
 798             }
 799             if (block == 0) {
 800                 Log("ht_HashInList: ht_GetTableBlock returned 0\n");
 801                 return BUDB_INTERNALERROR;
 802             }
 803
 804             /* Chain entry at front of bucket;
 805              * first threadOffset of entry = bucket
 806              * then bucket = addr of entry
 807              */
 808             if (set_word_offset
 809                 (ut, ea, e, mht->threadOffset, block->b.bucket[bo])
 810                 || set_word_addr(ut, block->a, &block->b,
 811                                  &block->b.bucket[bo], htonl(ea)))
 812                 return BUDB_IO;
 813         }
 814
 815         if (--(*opQuota) == 0)
 816             break;
 817     }                           /*f */
 818     return 0;
 819 }
 820
 821
 822 /* ht_MoveEntries
 823  *      The hash table is needs to be re-sized. Move entries from the old
 824  *      to the new.
 825  */
 826
 827 static afs_int32
 828 ht_MoveEntries(ut, mht)
 829      struct ubik_trans *ut;
 830      struct memoryHashTable *mht;
 831 {
 832     struct memoryHTBlock *block;
 833     afs_uint32 hash;
 834     int count;
 835     int bo;
 836     afs_int32 code;
 837
 838     if (mht->oldLength == 0)
 839         return 0;
 840
 841     LogDebug(3, "ht_MoveEntries:\n");
 842     /* we assume here that the hash function will map numbers smaller than the
 843      * size of the hash table straight through to hash table indexes.
 844      */
 845     hash = mht->progress;
 846
 847     /* get hash table block ? */
 848     code = ht_GetTableBlock(ut, mht, hash, 1 /*old */ , &block, &bo);
 849     if (code)
 850         return code;
 851
 852     if (block == 0)
 853         return BUDB_INTERNALERROR;
 854
 855     count = 10;                 /* max. # entries to move */
 856
 857     do {
 858         if (block->b.bucket[bo]) {
 859             code = ht_HashInList(ut, mht, &count, block, bo);
 860             if (code) {
 861                 Log("ht_MoveEntries: ht_HashInList failed\n");
 862                 return (BUDB_IO);
 863             }
 864         }
 865
 866         if (block->b.bucket[bo] == 0) {
 867             /* this bucket is now empty */
 868             mht->progress++;
 869         }
 870
 871         /* don't exceed the quota of items to be moved */
 872         if (count == 0)
 873             break;
 874
 875     } while (++bo < nHTBuckets);
 876
 877     if (mht->progress >= mht->oldLength)
 878         return (ht_FreeTable(ut, mht));
 879
 880     if (set_word_addr(ut, 0, &db.h, &mht->ht->progress, htonl(mht->progress))) {
 881         Log("ht_MoveEntries: progress set failed\n");
 882         return BUDB_IO;
 883     }
 884     return 0;
 885 }
 886
 887
 888 #ifdef notdef
 889 static afs_int32
 890 ht_MoveEntries(ut, mht)
 891      struct ubik_trans *ut;
 892      struct memoryHashTable *mht;
 893 {
 894     afs_uint32 hash;
 895     int bo;
 896     struct memoryHTBlock *block;
 897     afs_int32 code;
 898
 899     if (mht->oldLength == 0)
 900         return 0;
 901
 902     LogDebug(3, "ht_MoveEntries:\n");
 903     /* we assume here that the hash function will map numbers smaller than the
 904      * size of the hash table straight through to hash table indexes.
 905      */
 906     hash = mht->progress;
 907
 908     /* get hash table block ? */
 909     code = ht_GetTableBlock(ut, mht, hash, 1 /*old */ , &block, &bo);
 910     if (code)
 911         return code;
 912
 913     if (block == 0)
 914         return BUDB_INTERNALERROR;
 915
 916     do {
 917         mht->progress++;
 918         if (block->b.bucket[bo]) {
 919             code = ht_HashInList(ut, mht, ntohl(block->b.bucket[bo]));
 920             if (code) {
 921                 Log("ht_MoveEntries: ht_HashInList failed\n");
 922                 return (BUDB_IO);
 923             }
 924             code =
 925                 set_word_addr(ut, block->a, &block->b, &block->b.bucket[bo],
 926                               0);
 927             if (code) {
 928                 Log("ht_MoveEntries: clear old entry failed\n");
 929                 return BUDB_IO;
 930             }
 931             break;
 932         }
 933     } while (++bo < nHTBuckets);
 934
 935     if (mht->progress >= mht->oldLength)
 936         return (ht_FreeTable(ut, mht));
 937
 938     if (set_word_addr(ut, 0, &db.h, &mht->ht->progress, htonl(mht->progress))) {
 939         Log("ht_MoveEntries: progress set failed\n");
 940         return BUDB_IO;
 941     }
 942     return 0;
 943 }
 944 #endif /* notdef */
 945
 946 afs_int32
 947 ht_HashIn(ut, mht, ea, e)
 948      struct ubik_trans *ut;
 949      struct memoryHashTable *mht;
 950      dbadr ea;                  /* block db address */
 951      char *e;                   /* entry's address (in b) */
 952 {
 953     struct hashTable *ht;
 954     afs_uint32 hash;
 955     struct memoryHTBlock *block;
 956     int bo;
 957     afs_int32 code;
 958
 959     if (!(mht && (ht = mht->ht)))
 960         db_panic("some ht called with bad mht");
 961
 962     if (code = ht_MaybeAdjust(ut, mht))
 963         return code;
 964     if (mht->length == 0)
 965         if (code = ht_AllocTable(ut, mht))
 966             return code;
 967
 968     hash = ht_HashEntry(mht, e);
 969     code = ht_GetTableBlock(ut, mht, hash, 0 /*old */ , &block, &bo);
 970     if (code)
 971         return code;
 972     if (!block)
 973         return BUDB_INTERNALERROR;
 974
 975     code = set_word_offset(ut, ea, e, mht->threadOffset, block->b.bucket[bo]);
 976     if (code)
 977         return BUDB_IO;
 978     LogDebug(5, "Hashin: set %d to %d\n", mht->threadOffset,
 979              block->b.bucket[bo]);
 980
 981     code =
 982         set_word_addr(ut, block->a, &block->b, &block->b.bucket[bo],
 983                       htonl(ea));
 984     if (code)
 985         return BUDB_IO;
 986     LogDebug(5, "Hashin: set %d to %d\n", &block->b.bucket[bo], htonl(ea));
 987
 988     code =
 989         set_word_addr(ut, 0, &db.h, &ht->entries,
 990                       htonl(ntohl(ht->entries) + 1));
 991     if (code)
 992         return BUDB_IO;
 993
 994     return ht_MoveEntries(ut, mht);
 995 }
 996
 997 /* RemoveFromList - generic procedure to delete an entry from a list given its
 998  * head and thread offset.  Only a single long is modified by this routine.
 999  * The head pointer is modified, in place, using set_word_addr if the entry is
1000  * at the head of the list, otherwise only the thread of the previous entry is
1001  * modified.  The entry pointer is only used to calculate the thread offset,
1002  * but is not otherwise used. */
1003
1004 afs_int32
1005 RemoveFromList(ut, ea, e, head, ta, t, thread)
1006      struct ubik_trans *ut;
1007      dbadr ea;                  /* db addr of head structure */
1008      char *e;                   /* head structure */
1009      dbadr *head;               /* address of head pointer */
1010      dbadr ta;                  /* db addr of strucure to be removed */
1011      char *t;                   /* structure being removed */
1012      dbadr *thread;             /* pointer to thread pointer */
1013 {
1014     afs_int32 code;
1015     int threadOffset = ((char *)thread - t);
1016     dbadr next_a;               /* db addr of next element in list */
1017     dbadr loop_a;               /* db addr of current list element */
1018
1019     if (*head == 0)
1020         return -1;              /* empty list: not found */
1021     next_a = ntohl(*head);      /* start at head of list */
1022     if (next_a == ta) {         /* remove from head of list */
1023         code = set_word_addr(ut, ea, e, head, *thread);
1024         return code;
1025     }
1026     do {
1027         loop_a = next_a;
1028         code =
1029             dbread(ut, loop_a + threadOffset, (char *)&next_a, sizeof(dbadr));
1030         if (code)
1031             return code;
1032         if (next_a == 0)
1033             return -1;          /* end of list: not found */
1034     } while (ta != (next_a = ntohl(next_a)));
1035     code = dbwrite(ut, loop_a + threadOffset, (char *)thread, sizeof(dbadr));
1036     return code;
1037 }
1038
1039 afs_int32
1040 ht_HashOutT(ut, mht, hash, ea, e, old)
1041      struct ubik_trans *ut;
1042      struct memoryHashTable *mht;
1043      afs_uint32 hash;
1044      dbadr ea;
1045      char *e;
1046      int old;
1047 {
1048     struct memoryHTBlock *block;
1049     int bo;
1050     afs_int32 code;
1051
1052     if ((old ? mht->oldLength : mht->length) == 0)
1053         return -1;
1054     code = ht_GetTableBlock(ut, mht, hash, old, &block, &bo);
1055     if (code)
1056         return code;
1057     if ((block == 0) || (block->b.bucket[bo] == 0))
1058         return -1;
1059
1060     code =
1061         RemoveFromList(ut, block->a, (char *)&block->b, &block->b.bucket[bo],
1062                        ea, e, (dbadr *) (e + mht->threadOffset));
1063     if (code)
1064         return code;
1065 #if 0
1066     net_ea = htonl(ea);
1067     unthread_ea = *(afs_int32 *) ((char *)e + mht->threadOffset);
1068     if (block->b.bucket[bo] == net_ea) {
1069         if (set_word_addr
1070             (ut, block->a, &block->b, &block->b.bucket[bo], unthread_ea))
1071             return BUDB_IO;
1072         goto done;
1073     }
1074     loop_a = ntohl(block->b.bucket[bo]);
1075     while (1) {
1076         if (dbread
1077             (ut, loop_a + mht->threadOffset, (char *)&next_loop_a,
1078              sizeof(dbadr)))
1079             return BUDB_IO;
1080         if (next_loop_a == 0)
1081             return -1;          /* not found */
1082         if (net_ea == next_loop_a) {
1083             if (dbwrite
1084                 (ut, loop_a + mht->threadOffset, (char *)&unthread_ea,
1085                  sizeof(dbadr)))
1086                 return BUDB_IO;
1087             goto done;
1088         }
1089         loop_a = ntohl(next_loop_a);
1090     }
1091   done:
1092 #endif
1093     if (set_word_addr
1094         (ut, 0, &db.h, &mht->ht->entries, htonl(ntohl(mht->ht->entries) - 1)))
1095         return BUDB_IO;
1096     return 0;
1097 }
1098
1099 afs_int32
1100 ht_HashOut(ut, mht, ea, e)
1101      struct ubik_trans *ut;
1102      struct memoryHashTable *mht;
1103      dbadr ea;
1104      char *e;
1105 {
1106     afs_uint32 hash;
1107     afs_int32 code;
1108
1109     if (!mht)
1110         db_panic("some ht called with bad mht");
1111     hash = ht_HashEntry(mht, e);
1112     if (mht->oldLength) {
1113         code = ht_HashOutT(ut, mht, hash, ea, e, 1 /*old */ );
1114         if (code == 0)
1115             return 0;
1116         else if (code != -1)
1117             ERROR(code);
1118     }
1119     if (mht->length == 0)       /* not found */
1120         ERROR(BUDB_INTERNALERROR);
1121     code = ht_HashOutT(ut, mht, hash, ea, e, 0 /*old */ );
1122     if (code == -1)
1123         ERROR(BUDB_NOENT);
1124     if (code)
1125         ERROR(code);
1126
1127     code = ht_MoveEntries(ut, mht);
1128     if (code)
1129         ERROR(code);
1130     code = ht_MaybeAdjust(ut, mht);
1131     if (code)
1132         ERROR(code);
1133
1134   error_exit:
1135     return (code);
1136 }
1137
1138 /* generic hash table traversal routines */
1139
1140
1141 afs_int32
1142 scanHashTableBlock(ut, mhtPtr, htBlockPtr, old, length, index, selectFn,
1143                    operationFn, rockPtr)
1144      struct ubik_trans *ut;
1145      struct memoryHashTable *mhtPtr;
1146      struct htBlock *htBlockPtr;
1147      int old;
1148      afs_int32 length;          /* size of whole hash table */
1149      int index;                 /* base index of this block */
1150      int (*selectFn) ();
1151      int (*operationFn) ();
1152      char *rockPtr;
1153 {
1154     int type;                   /* hash table type */
1155     int entrySize;              /* hashed entry size */
1156
1157     afs_uint32 *mapEntryPtr = 0;        /* for status checks */
1158
1159     char entry[sizeof(struct block)];
1160     dbadr entryAddr, nextEntryAddr;
1161
1162     int i;
1163     afs_int32 code = 0;
1164
1165     type = ntohl(mhtPtr->ht->functionType);
1166     entrySize = sizeFunctions[type];
1167
1168     /* step through this hash table block, being careful to stop
1169      * before the end of the overall hash table
1170      */
1171
1172     for (i = 0; (i < nHTBuckets) && (index < length); i++, index++) {   /*f */
1173         entryAddr = 0;
1174         nextEntryAddr = ntohl(htBlockPtr->bucket[i]);
1175
1176         /* if this is the old hash table, all entries below the progress mark
1177          * should have been moved to the new hash table
1178          */
1179         if (old && (index < mhtPtr->progress) && nextEntryAddr)
1180             return BUDB_INTERNALERROR;
1181
1182         /* now walk down the chain of each bucket */
1183         while (nextEntryAddr) { /*w */
1184
1185             entryAddr = nextEntryAddr;
1186             if (dbread(ut, entryAddr, &entry[0], entrySize))
1187                 return (BUDB_INTERNALERROR);
1188
1189             if ((*selectFn) (entryAddr, &entry[0], rockPtr)) {
1190                 (*operationFn) (entryAddr, &entry[0], rockPtr);
1191             }
1192
1193             nextEntryAddr =
1194                 ntohl(*((dbadr *) (entry + mhtPtr->threadOffset)));
1195         }                       /*w */
1196
1197     }                           /*f */
1198
1199     return (0);
1200 }
1201
1202 afs_int32
1203 scanHashTable(ut, mhtPtr, selectFn, operationFn, rockPtr)
1204      struct ubik_trans *ut;
1205      struct memoryHashTable *mhtPtr;
1206      int (*selectFn) ();
1207      int (*operationFn) ();
1208      char *rockPtr;
1209 {
1210     struct htBlock hashTableBlock;
1211     dbadr tableAddr;            /* disk addr of hash block */
1212     int tableLength;            /* # entries */
1213     int blockLength;            /* # blocks */
1214     int hashIndex;
1215     int old;
1216     int i;
1217     afs_int32 code = 0;
1218
1219     extern int nHTBuckets;      /* # buckets in a hash table */
1220
1221     for (old = 0; old <= 1; old++) {    /*fo */
1222         if (old) {
1223             /* check the old hash table */
1224             tableLength = mhtPtr->oldLength;
1225             if (tableLength == 0)
1226                 continue;       /* nothing to do */
1227
1228             tableAddr = ntohl(mhtPtr->ht->oldTable);
1229         } else {
1230             /* check current hash table */
1231             tableLength = mhtPtr->length;
1232             if (tableLength == 0)
1233                 continue;       /* nothing to do */
1234
1235             tableAddr = ntohl(mhtPtr->ht->table);
1236         }
1237
1238         blockLength = (tableLength - 1) / nHTBuckets;
1239         hashIndex = 0;
1240
1241         /* follow the hash chain */
1242         for (i = 0; i <= blockLength; i++) {    /*fi */
1243             /* chain too short */
1244             if (tableAddr == 0)
1245                 ERROR(BUDB_DATABASEINCONSISTENT);
1246
1247             code =
1248                 dbread(ut, tableAddr, &hashTableBlock,
1249                        sizeof(hashTableBlock));
1250             if (code)
1251                 goto error_exit;
1252
1253             code =
1254                 scanHashTableBlock(ut, mhtPtr, &hashTableBlock, old,
1255                                    tableLength, hashIndex, selectFn,
1256                                    operationFn, rockPtr);
1257             if (code)
1258                 goto error_exit;
1259
1260             hashIndex += nHTBuckets;
1261             tableAddr = ntohl(hashTableBlock.h.next);
1262         }                       /*fi */
1263     }                           /*fo */
1264
1265   error_exit:
1266     return (code);
1267 }