Merge 1.8.0~pre4 packaging into master
[pkg-k5-afs_openafs.git] / src / budb / db_hash.c
blob7aa2847ad55b7b7ea4da8996a572efbf1fe8d0a2
1 /*
2 * Copyright 2000, International Business Machines Corporation and others.
3 * All Rights Reserved.
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 */
10 #include <afsconfig.h>
11 #include <afs/param.h>
12 #include <afs/stds.h>
14 #include <roken.h>
16 #include <ubik.h>
17 #include <afs/bubasics.h>
19 #include "budb_errs.h"
20 #include "database.h"
21 #include "budb_internal.h"
22 #include "error_macros.h"
25 int sizeFunctions[HT_MAX_FUNCTION + 1];
26 int nHTBuckets = NhtBucketS; /* testing: we need small HT blocks */
28 int ht_minHBlocks(struct memoryHashTable *mht);
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. */
34 int
35 ht_TableSize(int length)
37 int n;
38 if (length == 0)
39 return 0;
40 n = (length + nHTBuckets - 1) / nHTBuckets;
41 return n * sizeof(struct memoryHTBlock *);
44 /* ht_ResetT - resets the in-memory representation of a hashtable block array.
45 * It also resets the global variable nHTBuckets. */
47 static void
48 ht_ResetT(struct memoryHTBlock ***blocksP, int *sizeP, int length)
50 struct memoryHTBlock **b = *blocksP;
51 int newsize;
52 int n;
53 int i;
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;
76 /* ht_Reset
77 * reinitialize a memory hash table.
78 * Calls ht_ResetT to invalidate the two block arrays.
81 void
82 ht_Reset(struct memoryHashTable *mht)
84 struct hashTable *ht = NULL;
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);
96 /* InitDBhash - When server starts, do hash table initialization.
97 test - initialization parameters: bit 4 is small ht. */
99 afs_int32
100 InitDBhash(void)
102 sizeFunctions[0] = 0;
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);
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;
116 /* ht_DBInit - When rebuilding database, this sets up the hash tables. */
118 void
119 ht_DBInit(void)
121 db.h.nHTBuckets = htonl(nHTBuckets);
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);
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);
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);
141 db.h.dumpIden.threadOffset =
142 htonl((char *)&s->idHashChain - (char *)s);
143 db.h.dumpIden.functionType = htonl(HT_dumpIden_FUNCTION);
145 ht_Reset(&db.volName);
146 ht_Reset(&db.tapeName);
147 ht_Reset(&db.dumpName);
148 ht_Reset(&db.dumpIden);
151 afs_int32
152 ht_AllocTable(struct ubik_trans *ut, struct memoryHashTable *mht)
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;
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");
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 */
174 mht->size = nb * sizeof(struct memoryHTBlock *);
175 b = mht->blocks = calloc(1, mht->size);
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;
184 b[i]->b.h.type = hashTable_BLOCK;
186 /* thread the blocks */
187 if (i)
188 b[i - 1]->b.h.next = htonl(b[i]->a);
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;
198 if ((code = set_word_addr(ut, 0, &db.h, &ht->table, htonl(b[0]->a))))
199 return code;
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;
208 afs_int32
209 ht_FreeTable(struct ubik_trans *ut, struct memoryHashTable *mht)
211 struct hashTable *ht = NULL;
212 afs_int32 code;
213 struct blockHeader bh;
214 dbadr a, na;
215 afs_int32 *plen, *pprog;
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");
222 ht_ResetT(&mht->oldBlocks, &mht->oldSize, 0);
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;
229 na = ntohl(bh.next);
230 if ((code = FreeBlock(ut, &bh, a)))
231 return code;
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;
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)
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;
258 if ((mht == 0)
259 || ((ht = mht->ht) == 0)
261 db_panic("some ht called with bad mht");
264 *blockP = 0;
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;
282 bi = hi / nHTBuckets; /* block index */
283 *boP = hi - bi * nHTBuckets; /* block offset ptr */
285 if (*blocksP == 0) {
286 *sizeP = ht_TableSize(length);
287 *blocksP = calloc(1, *sizeP);
289 n = *sizeP / sizeof(struct memoryHTBlock *);
290 if (bi >= n)
291 db_panic("table size inconsistent");
292 b = *blocksP;
294 /* find an allocated block or the beginning of the block array */
295 for (i = bi; (i > 0) && (b[i] == 0); i--);
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");
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;
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;
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;
323 ta = ntohl(b[i++]->b.h.next); /* get next ptr from current block */
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.
333 static afs_int32
334 ht_MaybeAdjust(struct ubik_trans *ut, struct memoryHashTable *mht)
336 struct hashTable *ht = mht->ht;
337 int numberEntries = ntohl(ht->entries);
339 /* old hash table must be empty */
340 if (mht->oldLength != 0)
341 return (0);
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.
348 * Don't shrink it:
349 * || ((mht->length > nHTBuckets) && (numberEntries*8 < mht->length))
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.
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;
370 ht_Reset(mht);
371 LogDebug(2, "ht_MaybeAdjust: push ht to old\n");
373 return 0;
376 dbadr
377 ht_LookupBucket(struct ubik_trans *ut, struct memoryHashTable *mht,
378 afs_uint32 hash, int old)
380 struct memoryHTBlock *block;
381 int bo;
382 afs_int32 code;
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]);
392 /* This function is not too bad, for small hash tables, but suffers, I think,
393 * from insufficient mixing of the hash information. */
395 afs_uint32
396 Old2StringHashFunction(unsigned char *str)
398 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
399 while (*str)
400 hash = (hash << 1) + (hash >> 31) + *str++;
401 return hash;
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. */
407 afs_uint32
408 Old3StringHashFunction(unsigned char *str)
410 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
411 while (*str)
412 hash += (*str++) * 0x072a51a4;
413 return hash;
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. */
420 afs_uint32
421 Old4StringHashFunction(unsigned char *str)
423 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
424 while (*str)
425 hash = (*str++) + hash * 0x072a51a4;
426 return hash;
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. */
432 afs_uint32
433 Old5StringHashFunction(unsigned char *str)
435 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
436 while (*str)
437 hash += (*str++);
438 return hash;
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. */
446 afs_uint32
447 Old6StringHashFunction(unsigned char *str)
449 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
450 while (*str)
451 hash = hash * 0x81 + (*str++);
452 return hash;
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. */
460 afs_uint32
461 Old7StringHashFunction(unsigned char *str)
463 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
464 while (*str)
465 hash = hash * 0x42108421 + (*str++);
466 return hash;
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. */
473 afs_uint32
474 Old8StringHashFunction(unsigned char *str)
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;
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. */
489 afs_uint32
490 StringHashFunction(unsigned char *str)
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;
500 afs_uint32
501 IdHashFunction(afs_uint32 id)
503 afs_uint32 l, r;
504 id *= 81847;
505 l = id | 0xaaaaaaaa;
506 r = id | 0x55555555;
507 return (l * r);
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.
515 ht_minHBlocks(struct memoryHashTable *mht)
517 int retval;
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;
525 case HT_tapeName_FUNCTION:
526 retval = 4; /* 2,040 tape entries */
527 break;
529 case HT_volName_FUNCTION:
530 retval = 60; /* 61,200 volInfo entries (with different names) */
531 break;
533 default:
534 db_panic("Illegal hash function type");
535 retval = -1; /* not reached */
537 return (retval);
540 afs_uint32
541 ht_HashEntry(struct memoryHashTable *mht,
542 char *e) /* entry's address (in b) */
544 int type = ntohl(mht->ht->functionType);
545 afs_uint32 retval;
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;
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;
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;
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;
568 default:
569 db_panic("illegal hash function");
570 retval = -1; /* not reached */
573 return (retval);
577 /* ht_GetType
578 * returns a ptr to the memory hash table for the specified hash
579 * list.
582 struct memoryHashTable *
583 ht_GetType(int type, int *e_sizeP)
585 struct memoryHashTable *mht;
587 if ((type <= 0) || (type > HT_MAX_FUNCTION))
588 return 0;
590 if (e_sizeP)
591 *e_sizeP = sizeFunctions[type];
592 switch (type) {
593 case HT_dumpIden_FUNCTION:
594 mht = &db.dumpIden;
595 break;
597 case HT_dumpName_FUNCTION:
598 mht = &db.dumpName;
599 break;
601 case HT_tapeName_FUNCTION:
602 mht = &db.tapeName;
603 break;
605 case HT_volName_FUNCTION:
606 mht = &db.volName;
607 break;
609 default:
610 return 0;
612 if (ntohl(mht->ht->functionType) != type)
613 db_panic("ht types don't match");
614 return mht;
617 static int
618 ht_KeyMatch(int type, char *key, char *e)
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;
630 default:
631 db_panic("illegal hash function");
633 /* not reached */
634 return 0;
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
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 */
654 struct hashTable *ht = NULL;
655 int type;
656 int e_size;
657 int old;
658 afs_uint32 hash;
659 dbadr a;
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");
666 *eaP = 0; /* initialize not-found indicator */
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);
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;
684 a = ntohl(*(dbadr *) ((char *)e + mht->threadOffset));
686 if (old)
687 return 0;
691 /* ht_HashInList
692 * entry:
693 * opQuota - max # of items to move
694 * exit:
695 * opQuota - adjusted to reflect # of moves
698 static afs_int32
699 ht_HashInList(struct ubik_trans *ut, struct memoryHashTable *mht,
700 int *opQuota, struct memoryHTBlock *block, int blockOffset)
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)];
709 if (mht->length == 0) {
710 if ((code = ht_AllocTable(ut, mht))) {
711 Log("ht_HashInList: ht_AllocTable failed\n");
712 return code;
716 listA = ntohl(block->b.bucket[blockOffset]);
718 if (listA == 0) {
719 Log("ht_HashInList: expecting non-zero bucket\n");
720 return 0;
723 for (ea = listA; ea; ea = next_ea) { /*f */
725 LogDebug(3, "ht_HashInList: move entry at %u, type %d\n", ea,
726 ntohl(mht->ht->functionType));
728 if (dbread(ut, ea, e, e_size))
729 return BUDB_IO;
731 /* get the address of the next item on the list */
732 next_ea = ntohl(*(dbadr *) (e + mht->threadOffset));
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);
744 struct memoryHTBlock *block;
745 int bo;
746 afs_uint32 hash;
748 /* get the hash value */
749 hash = ht_HashEntry(mht, e) % mht->length;
750 LogDebug(4, "ht_HashInList: moved to %u\n", hash);
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;
758 if (block == 0) {
759 Log("ht_HashInList: ht_GetTableBlock returned 0\n");
760 return BUDB_INTERNALERROR;
763 /* Chain entry at front of bucket;
764 * first threadOffset of entry = bucket
765 * then bucket = addr of entry
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;
774 if (--(*opQuota) == 0)
775 break;
776 } /*f */
777 return 0;
781 /* ht_MoveEntries
782 * The hash table is needs to be re-sized. Move entries from the old
783 * to the new.
786 static afs_int32
787 ht_MoveEntries(struct ubik_trans *ut, struct memoryHashTable *mht)
789 struct memoryHTBlock *block;
790 afs_uint32 hash;
791 int count;
792 int bo;
793 afs_int32 code;
794 afs_int32 *pprog;
796 if (mht->oldLength == 0)
797 return 0;
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.
803 hash = mht->progress;
805 /* get hash table block ? */
806 code = ht_GetTableBlock(ut, mht, hash, 1 /*old */ , &block, &bo);
807 if (code)
808 return code;
810 if (block == 0)
811 return BUDB_INTERNALERROR;
813 count = 10; /* max. # entries to move */
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);
824 if (block->b.bucket[bo] == 0) {
825 /* this bucket is now empty */
826 mht->progress++;
829 /* don't exceed the quota of items to be moved */
830 if (count == 0)
831 break;
833 } while (++bo < nHTBuckets);
835 if (mht->progress >= mht->oldLength)
836 return (ht_FreeTable(ut, mht));
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;
843 return 0;
847 #ifdef notdef
848 static afs_int32
849 ht_MoveEntries(struct ubik_trans *ut, struct memoryHashTable *mht)
851 afs_uint32 hash;
852 int bo;
853 struct memoryHTBlock *block;
854 afs_int32 code;
856 if (mht->oldLength == 0)
857 return 0;
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.
863 hash = mht->progress;
865 /* get hash table block ? */
866 code = ht_GetTableBlock(ut, mht, hash, 1 /*old */ , &block, &bo);
867 if (code)
868 return code;
870 if (block == 0)
871 return BUDB_INTERNALERROR;
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);
881 code =
882 set_word_addr(ut, block->a, &block->b, &block->b.bucket[bo],
884 if (code) {
885 Log("ht_MoveEntries: clear old entry failed\n");
886 return BUDB_IO;
888 break;
890 } while (++bo < nHTBuckets);
892 if (mht->progress >= mht->oldLength)
893 return (ht_FreeTable(ut, mht));
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;
899 return 0;
901 #endif /* notdef */
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) */
909 struct hashTable *ht = NULL;
910 afs_uint32 hash;
911 struct memoryHTBlock *block;
912 int bo;
913 afs_int32 code;
914 afs_int32 *pentries;
916 if (!(mht && (ht = mht->ht)))
917 db_panic("some ht called with bad mht");
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;
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;
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]);
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));
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;
953 return ht_MoveEntries(ut, mht);
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. */
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 */
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 */
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;
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;
997 afs_int32
998 ht_HashOutT(struct ubik_trans *ut, struct memoryHashTable *mht,
999 afs_uint32 hash, dbadr ea, char *e, int old)
1001 struct memoryHTBlock *block;
1002 int bo;
1003 afs_int32 code;
1004 afs_int32 *pentries;
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;
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;
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;
1043 loop_a = ntohl(next_loop_a);
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;
1054 afs_int32
1055 ht_HashOut(struct ubik_trans *ut, struct memoryHashTable *mht, dbadr ea,
1056 void *e)
1058 afs_uint32 hash;
1059 afs_int32 code;
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);
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);
1079 code = ht_MoveEntries(ut, mht);
1080 if (code)
1081 ERROR(code);
1082 code = ht_MaybeAdjust(ut, mht);
1083 if (code)
1084 ERROR(code);
1086 error_exit:
1087 return (code);
1090 /* generic hash table traversal routines */
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)
1104 int type; /* hash table type */
1105 int entrySize; /* hashed entry size */
1107 char entry[sizeof(struct block)];
1108 dbadr entryAddr;
1110 int i;
1112 type = ntohl(mhtPtr->ht->functionType);
1113 entrySize = sizeFunctions[type];
1115 /* step through this hash table block, being careful to stop
1116 * before the end of the overall hash table
1119 for (i = 0; (i < nHTBuckets) && (index < length); i++, index++) { /*f */
1120 entryAddr = ntohl(htBlockPtr->bucket[i]);
1122 /* if this is the old hash table, all entries below the progress mark
1123 * should have been moved to the new hash table
1125 if (old && (index < mhtPtr->progress) && entryAddr)
1126 return BUDB_INTERNALERROR;
1128 /* now walk down the chain of each bucket */
1129 while (entryAddr) { /*w */
1131 if (dbread(ut, entryAddr, &entry[0], entrySize))
1132 return (BUDB_INTERNALERROR);
1134 if ((*selectFn) (entryAddr, &entry[0], rockPtr)) {
1135 (*operationFn) (entryAddr, &entry[0], rockPtr);
1138 entryAddr =
1139 ntohl(*((dbadr *) (entry + mhtPtr->threadOffset)));
1140 } /*w */
1142 } /*f */
1144 return (0);
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)
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;
1162 extern int nHTBuckets; /* # buckets in a hash table */
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 */
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 */
1178 tableAddr = ntohl(mhtPtr->ht->table);
1181 blockLength = (tableLength - 1) / nHTBuckets;
1182 hashIndex = 0;
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);
1190 code =
1191 dbread(ut, tableAddr, &hashTableBlock,
1192 sizeof(hashTableBlock));
1193 if (code)
1194 goto error_exit;
1196 code =
1197 scanHashTableBlock(ut, mhtPtr, &hashTableBlock, old,
1198 tableLength, hashIndex, selectFn,
1199 operationFn, rockPtr);
1200 if (code)
1201 goto error_exit;
1203 hashIndex += nHTBuckets;
1204 tableAddr = ntohl(hashTableBlock.h.next);
1205 } /*fi */
1206 } /*fo */
1208 error_exit:
1209 return (code);