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