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     /* not reached */
 675     return 0;
 676 }
 677
 678 /* ht_LookupEntry
 679  * entry:
 680  *      ut - ubik transaction
 681  *      mht - memory hash table ptr
 682  *      key - hash and lookup key
 683  * exit:
 684  *      eaP - dbaddr of entry found or zero if failed
 685   *     e - contents of located entry
 686  */
 687
 688 afs_int32
 689 ht_LookupEntry(ut, mht, key, eaP, e)
 690      struct ubik_trans *ut;
 691      struct memoryHashTable *mht;
 692      char *key;                 /* pointer to lookup key to match */
 693      dbadr *eaP;                /* db addr of entry found or zero */
 694      char *e;                   /* contents of located entry */
 695 {
 696     struct hashTable *ht;
 697     int type;
 698     int e_size;
 699     int old;
 700     afs_uint32 hash;
 701     dbadr a;
 702
 703     if (!key || !eaP || !e)
 704         db_panic("null ptrs passed to LookupEntry");
 705     if (!(mht && (ht = mht->ht)))
 706         db_panic("some ht called with bad mht");
 707
 708     *eaP = 0;                   /* initialize not-found indicator */
 709
 710     type = ntohl(ht->functionType);
 711     e_size = sizeFunctions[type];
 712     if (type == HT_dumpIden_FUNCTION)
 713         hash = IdHashFunction(*(dumpId *) key);
 714     else
 715         hash = StringHashFunction(key);
 716
 717     for (old = 0;; old++) {
 718         a = ht_LookupBucket(ut, mht, hash, old);
 719         while (a) {
 720             if (dbread(ut, a, e, e_size))
 721                 return BUDB_IO;
 722             if (ht_KeyMatch(type, key, e)) {
 723                 *eaP = a;
 724                 return 0;
 725             }
 726             a = ntohl(*(dbadr *) (e + mht->threadOffset));
 727         }
 728         if (old)
 729             return 0;
 730     }
 731 }
 732
 733 /* ht_HashInList
 734  * entry:
 735  *      opQuota - max # of items to move
 736  * exit:
 737  *      opQuota - adjusted to reflect # of moves
 738  */
 739
 740 static afs_int32
 741 ht_HashInList(ut, mht, opQuota, block, blockOffset)
 742      struct ubik_trans *ut;
 743      struct memoryHashTable *mht;
 744      int *opQuota;
 745      struct memoryHTBlock *block;
 746      int blockOffset;
 747 {
 748     struct hashTable *ht = mht->ht;
 749     afs_int32 code;
 750     dbadr ea, next_ea;
 751     dbadr listA;
 752     char e[sizeof(struct block)];       /* unnecessarily conservative */
 753     int e_size = sizeFunctions[ntohl(ht->functionType)];
 754
 755     if (mht->length == 0) {
 756         if (code = ht_AllocTable(ut, mht)) {
 757             Log("ht_HashInList: ht_AllocTable failed\n");
 758             return code;
 759         }
 760     }
 761
 762     listA = ntohl(block->b.bucket[blockOffset]);
 763
 764     if (listA == 0) {
 765         Log("ht_HashInList: expecting non-zero bucket\n");
 766         return 0;
 767     }
 768
 769     for (ea = listA; ea; ea = next_ea) {        /*f */
 770
 771         LogDebug(3, "ht_HashInList: move entry at %d, type %d\n", ea,
 772                  ntohl(mht->ht->functionType));
 773
 774         if (dbread(ut, ea, e, e_size))
 775             return BUDB_IO;
 776
 777         /* LogNetDump((struct dump *) e); */
 778
 779         /* get the address of the next item on the list */
 780         next_ea = ntohl(*(dbadr *) (e + mht->threadOffset));
 781
 782         /* write the link into the bucket */
 783         code =
 784             set_word_addr(ut, block->a, &block->b,
 785                           &block->b.bucket[blockOffset], htonl(next_ea));
 786         if (code) {
 787             Log("ht_HashInList: bucket update failed\n");
 788             return (code);
 789         }
 790
 791         {
 792             struct memoryHTBlock *block;
 793             int bo;
 794             afs_uint32 hash;
 795
 796             /* get the hash value */
 797             hash = ht_HashEntry(mht, e) % mht->length;
 798             LogDebug(4, "ht_HashInList: moved to %d\n", hash);
 799
 800             /* get the new hash table block */
 801             code = ht_GetTableBlock(ut, mht, hash, 0 /*old */ , &block, &bo);
 802             if (code) {
 803                 Log("ht_HashInList: ht_GetTableBlock failed\n");
 804                 return code;
 805             }
 806             if (block == 0) {
 807                 Log("ht_HashInList: ht_GetTableBlock returned 0\n");
 808                 return BUDB_INTERNALERROR;
 809             }
 810
 811             /* Chain entry at front of bucket;
 812              * first threadOffset of entry = bucket
 813              * then bucket = addr of entry
 814              */
 815             if (set_word_offset
 816                 (ut, ea, e, mht->threadOffset, block->b.bucket[bo])
 817                 || set_word_addr(ut, block->a, &block->b,
 818                                  &block->b.bucket[bo], htonl(ea)))
 819                 return BUDB_IO;
 820         }
 821
 822         if (--(*opQuota) == 0)
 823             break;
 824     }                           /*f */
 825     return 0;
 826 }
 827
 828
 829 /* ht_MoveEntries
 830  *      The hash table is needs to be re-sized. Move entries from the old
 831  *      to the new.
 832  */
 833
 834 static afs_int32
 835 ht_MoveEntries(ut, mht)
 836      struct ubik_trans *ut;
 837      struct memoryHashTable *mht;
 838 {
 839     struct memoryHTBlock *block;
 840     afs_uint32 hash;
 841     int count;
 842     int bo;
 843     afs_int32 code;
 844
 845     if (mht->oldLength == 0)
 846         return 0;
 847
 848     LogDebug(3, "ht_MoveEntries:\n");
 849     /* we assume here that the hash function will map numbers smaller than the
 850      * size of the hash table straight through to hash table indexes.
 851      */
 852     hash = mht->progress;
 853
 854     /* get hash table block ? */
 855     code = ht_GetTableBlock(ut, mht, hash, 1 /*old */ , &block, &bo);
 856     if (code)
 857         return code;
 858
 859     if (block == 0)
 860         return BUDB_INTERNALERROR;
 861
 862     count = 10;                 /* max. # entries to move */
 863
 864     do {
 865         if (block->b.bucket[bo]) {
 866             code = ht_HashInList(ut, mht, &count, block, bo);
 867             if (code) {
 868                 Log("ht_MoveEntries: ht_HashInList failed\n");
 869                 return (BUDB_IO);
 870             }
 871         }
 872
 873         if (block->b.bucket[bo] == 0) {
 874             /* this bucket is now empty */
 875             mht->progress++;
 876         }
 877
 878         /* don't exceed the quota of items to be moved */
 879         if (count == 0)
 880             break;
 881
 882     } while (++bo < nHTBuckets);
 883
 884     if (mht->progress >= mht->oldLength)
 885         return (ht_FreeTable(ut, mht));
 886
 887     if (set_word_addr(ut, 0, &db.h, &mht->ht->progress, htonl(mht->progress))) {
 888         Log("ht_MoveEntries: progress set failed\n");
 889         return BUDB_IO;
 890     }
 891     return 0;
 892 }
 893
 894
 895 #ifdef notdef
 896 static afs_int32
 897 ht_MoveEntries(ut, mht)
 898      struct ubik_trans *ut;
 899      struct memoryHashTable *mht;
 900 {
 901     afs_uint32 hash;
 902     int bo;
 903     struct memoryHTBlock *block;
 904     afs_int32 code;
 905
 906     if (mht->oldLength == 0)
 907         return 0;
 908
 909     LogDebug(3, "ht_MoveEntries:\n");
 910     /* we assume here that the hash function will map numbers smaller than the
 911      * size of the hash table straight through to hash table indexes.
 912      */
 913     hash = mht->progress;
 914
 915     /* get hash table block ? */
 916     code = ht_GetTableBlock(ut, mht, hash, 1 /*old */ , &block, &bo);
 917     if (code)
 918         return code;
 919
 920     if (block == 0)
 921         return BUDB_INTERNALERROR;
 922
 923     do {
 924         mht->progress++;
 925         if (block->b.bucket[bo]) {
 926             code = ht_HashInList(ut, mht, ntohl(block->b.bucket[bo]));
 927             if (code) {
 928                 Log("ht_MoveEntries: ht_HashInList failed\n");
 929                 return (BUDB_IO);
 930             }
 931             code =
 932                 set_word_addr(ut, block->a, &block->b, &block->b.bucket[bo],
 933                               0);
 934             if (code) {
 935                 Log("ht_MoveEntries: clear old entry failed\n");
 936                 return BUDB_IO;
 937             }
 938             break;
 939         }
 940     } while (++bo < nHTBuckets);
 941
 942     if (mht->progress >= mht->oldLength)
 943         return (ht_FreeTable(ut, mht));
 944
 945     if (set_word_addr(ut, 0, &db.h, &mht->ht->progress, htonl(mht->progress))) {
 946         Log("ht_MoveEntries: progress set failed\n");
 947         return BUDB_IO;
 948     }
 949     return 0;
 950 }
 951 #endif /* notdef */
 952
 953 afs_int32
 954 ht_HashIn(ut, mht, ea, e)
 955      struct ubik_trans *ut;
 956      struct memoryHashTable *mht;
 957      dbadr ea;                  /* block db address */
 958      char *e;                   /* entry's address (in b) */
 959 {
 960     struct hashTable *ht;
 961     afs_uint32 hash;
 962     struct memoryHTBlock *block;
 963     int bo;
 964     afs_int32 code;
 965
 966     if (!(mht && (ht = mht->ht)))
 967         db_panic("some ht called with bad mht");
 968
 969     if (code = ht_MaybeAdjust(ut, mht))
 970         return code;
 971     if (mht->length == 0)
 972         if (code = ht_AllocTable(ut, mht))
 973             return code;
 974
 975     hash = ht_HashEntry(mht, e);
 976     code = ht_GetTableBlock(ut, mht, hash, 0 /*old */ , &block, &bo);
 977     if (code)
 978         return code;
 979     if (!block)
 980         return BUDB_INTERNALERROR;
 981
 982     code = set_word_offset(ut, ea, e, mht->threadOffset, block->b.bucket[bo]);
 983     if (code)
 984         return BUDB_IO;
 985     LogDebug(5, "Hashin: set %d to %d\n", mht->threadOffset,
 986              block->b.bucket[bo]);
 987
 988     code =
 989         set_word_addr(ut, block->a, &block->b, &block->b.bucket[bo],
 990                       htonl(ea));
 991     if (code)
 992         return BUDB_IO;
 993     LogDebug(5, "Hashin: set %d to %d\n", &block->b.bucket[bo], htonl(ea));
 994
 995     code =
 996         set_word_addr(ut, 0, &db.h, &ht->entries,
 997                       htonl(ntohl(ht->entries) + 1));
 998     if (code)
 999         return BUDB_IO;
1000
1001     return ht_MoveEntries(ut, mht);
1002 }
1003
1004 /* RemoveFromList - generic procedure to delete an entry from a list given its
1005  * head and thread offset.  Only a single long is modified by this routine.
1006  * The head pointer is modified, in place, using set_word_addr if the entry is
1007  * at the head of the list, otherwise only the thread of the previous entry is
1008  * modified.  The entry pointer is only used to calculate the thread offset,
1009  * but is not otherwise used. */
1010
1011 afs_int32
1012 RemoveFromList(ut, ea, e, head, ta, t, thread)
1013      struct ubik_trans *ut;
1014      dbadr ea;                  /* db addr of head structure */
1015      char *e;                   /* head structure */
1016      dbadr *head;               /* address of head pointer */
1017      dbadr ta;                  /* db addr of strucure to be removed */
1018      char *t;                   /* structure being removed */
1019      dbadr *thread;             /* pointer to thread pointer */
1020 {
1021     afs_int32 code;
1022     int threadOffset = ((char *)thread - t);
1023     dbadr next_a;               /* db addr of next element in list */
1024     dbadr loop_a;               /* db addr of current list element */
1025
1026     if (*head == 0)
1027         return -1;              /* empty list: not found */
1028     next_a = ntohl(*head);      /* start at head of list */
1029     if (next_a == ta) {         /* remove from head of list */
1030         code = set_word_addr(ut, ea, e, head, *thread);
1031         return code;
1032     }
1033     do {
1034         loop_a = next_a;
1035         code =
1036             dbread(ut, loop_a + threadOffset, (char *)&next_a, sizeof(dbadr));
1037         if (code)
1038             return code;
1039         if (next_a == 0)
1040             return -1;          /* end of list: not found */
1041     } while (ta != (next_a = ntohl(next_a)));
1042     code = dbwrite(ut, loop_a + threadOffset, (char *)thread, sizeof(dbadr));
1043     return code;
1044 }
1045
1046 afs_int32
1047 ht_HashOutT(ut, mht, hash, ea, e, old)
1048      struct ubik_trans *ut;
1049      struct memoryHashTable *mht;
1050      afs_uint32 hash;
1051      dbadr ea;
1052      char *e;
1053      int old;
1054 {
1055     struct memoryHTBlock *block;
1056     int bo;
1057     afs_int32 code;
1058
1059     if ((old ? mht->oldLength : mht->length) == 0)
1060         return -1;
1061     code = ht_GetTableBlock(ut, mht, hash, old, &block, &bo);
1062     if (code)
1063         return code;
1064     if ((block == 0) || (block->b.bucket[bo] == 0))
1065         return -1;
1066
1067     code =
1068         RemoveFromList(ut, block->a, (char *)&block->b, &block->b.bucket[bo],
1069                        ea, e, (dbadr *) (e + mht->threadOffset));
1070     if (code)
1071         return code;
1072 #if 0
1073     net_ea = htonl(ea);
1074     unthread_ea = *(afs_int32 *) ((char *)e + mht->threadOffset);
1075     if (block->b.bucket[bo] == net_ea) {
1076         if (set_word_addr
1077             (ut, block->a, &block->b, &block->b.bucket[bo], unthread_ea))
1078             return BUDB_IO;
1079         goto done;
1080     }
1081     loop_a = ntohl(block->b.bucket[bo]);
1082     while (1) {
1083         if (dbread
1084             (ut, loop_a + mht->threadOffset, (char *)&next_loop_a,
1085              sizeof(dbadr)))
1086             return BUDB_IO;
1087         if (next_loop_a == 0)
1088             return -1;          /* not found */
1089         if (net_ea == next_loop_a) {
1090             if (dbwrite
1091                 (ut, loop_a + mht->threadOffset, (char *)&unthread_ea,
1092                  sizeof(dbadr)))
1093                 return BUDB_IO;
1094             goto done;
1095         }
1096         loop_a = ntohl(next_loop_a);
1097     }
1098   done:
1099 #endif
1100     if (set_word_addr
1101         (ut, 0, &db.h, &mht->ht->entries, htonl(ntohl(mht->ht->entries) - 1)))
1102         return BUDB_IO;
1103     return 0;
1104 }
1105
1106 afs_int32
1107 ht_HashOut(ut, mht, ea, e)
1108      struct ubik_trans *ut;
1109      struct memoryHashTable *mht;
1110      dbadr ea;
1111      char *e;
1112 {
1113     afs_uint32 hash;
1114     afs_int32 code;
1115
1116     if (!mht)
1117         db_panic("some ht called with bad mht");
1118     hash = ht_HashEntry(mht, e);
1119     if (mht->oldLength) {
1120         code = ht_HashOutT(ut, mht, hash, ea, e, 1 /*old */ );
1121         if (code == 0)
1122             return 0;
1123         else if (code != -1)
1124             ERROR(code);
1125     }
1126     if (mht->length == 0)       /* not found */
1127         ERROR(BUDB_INTERNALERROR);
1128     code = ht_HashOutT(ut, mht, hash, ea, e, 0 /*old */ );
1129     if (code == -1)
1130         ERROR(BUDB_NOENT);
1131     if (code)
1132         ERROR(code);
1133
1134     code = ht_MoveEntries(ut, mht);
1135     if (code)
1136         ERROR(code);
1137     code = ht_MaybeAdjust(ut, mht);
1138     if (code)
1139         ERROR(code);
1140
1141   error_exit:
1142     return (code);
1143 }
1144
1145 /* generic hash table traversal routines */
1146
1147
1148 afs_int32
1149 scanHashTableBlock(ut, mhtPtr, htBlockPtr, old, length, index, selectFn,
1150                    operationFn, rockPtr)
1151      struct ubik_trans *ut;
1152      struct memoryHashTable *mhtPtr;
1153      struct htBlock *htBlockPtr;
1154      int old;
1155      afs_int32 length;          /* size of whole hash table */
1156      int index;                 /* base index of this block */
1157      int (*selectFn) ();
1158      int (*operationFn) ();
1159      char *rockPtr;
1160 {
1161     int type;                   /* hash table type */
1162     int entrySize;              /* hashed entry size */
1163
1164     afs_uint32 *mapEntryPtr = 0;        /* for status checks */
1165
1166     char entry[sizeof(struct block)];
1167     dbadr entryAddr, nextEntryAddr;
1168
1169     int i;
1170     afs_int32 code = 0;
1171
1172     type = ntohl(mhtPtr->ht->functionType);
1173     entrySize = sizeFunctions[type];
1174
1175     /* step through this hash table block, being careful to stop
1176      * before the end of the overall hash table
1177      */
1178
1179     for (i = 0; (i < nHTBuckets) && (index < length); i++, index++) {   /*f */
1180         entryAddr = 0;
1181         nextEntryAddr = ntohl(htBlockPtr->bucket[i]);
1182
1183         /* if this is the old hash table, all entries below the progress mark
1184          * should have been moved to the new hash table
1185          */
1186         if (old && (index < mhtPtr->progress) && nextEntryAddr)
1187             return BUDB_INTERNALERROR;
1188
1189         /* now walk down the chain of each bucket */
1190         while (nextEntryAddr) { /*w */
1191
1192             entryAddr = nextEntryAddr;
1193             if (dbread(ut, entryAddr, &entry[0], entrySize))
1194                 return (BUDB_INTERNALERROR);
1195
1196             if ((*selectFn) (entryAddr, &entry[0], rockPtr)) {
1197                 (*operationFn) (entryAddr, &entry[0], rockPtr);
1198             }
1199
1200             nextEntryAddr =
1201                 ntohl(*((dbadr *) (entry + mhtPtr->threadOffset)));
1202         }                       /*w */
1203
1204     }                           /*f */
1205
1206     return (0);
1207 }
1208
1209 afs_int32
1210 scanHashTable(ut, mhtPtr, selectFn, operationFn, rockPtr)
1211      struct ubik_trans *ut;
1212      struct memoryHashTable *mhtPtr;
1213      int (*selectFn) ();
1214      int (*operationFn) ();
1215      char *rockPtr;
1216 {
1217     struct htBlock hashTableBlock;
1218     dbadr tableAddr;            /* disk addr of hash block */
1219     int tableLength;            /* # entries */
1220     int blockLength;            /* # blocks */
1221     int hashIndex;
1222     int old;
1223     int i;
1224     afs_int32 code = 0;
1225
1226     extern int nHTBuckets;      /* # buckets in a hash table */
1227
1228     for (old = 0; old <= 1; old++) {    /*fo */
1229         if (old) {
1230             /* check the old hash table */
1231             tableLength = mhtPtr->oldLength;
1232             if (tableLength == 0)
1233                 continue;       /* nothing to do */
1234
1235             tableAddr = ntohl(mhtPtr->ht->oldTable);
1236         } else {
1237             /* check current hash table */
1238             tableLength = mhtPtr->length;
1239             if (tableLength == 0)
1240                 continue;       /* nothing to do */
1241
1242             tableAddr = ntohl(mhtPtr->ht->table);
1243         }
1244
1245         blockLength = (tableLength - 1) / nHTBuckets;
1246         hashIndex = 0;
1247
1248         /* follow the hash chain */
1249         for (i = 0; i <= blockLength; i++) {    /*fi */
1250             /* chain too short */
1251             if (tableAddr == 0)
1252                 ERROR(BUDB_DATABASEINCONSISTENT);
1253
1254             code =
1255                 dbread(ut, tableAddr, &hashTableBlock,
1256                        sizeof(hashTableBlock));
1257             if (code)
1258                 goto error_exit;
1259
1260             code =
1261                 scanHashTableBlock(ut, mhtPtr, &hashTableBlock, old,
1262                                    tableLength, hashIndex, selectFn,
1263                                    operationFn, rockPtr);
1264             if (code)
1265                 goto error_exit;
1266
1267             hashIndex += nHTBuckets;
1268             tableAddr = ntohl(hashTableBlock.h.next);
1269         }                       /*fi */
1270     }                           /*fo */
1271
1272   error_exit:
1273     return (code);
1274 }