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