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