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