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