Skip to content

Commit 86482e1

Browse files
tglsfdctglsfdc
committed
Correct serious bug in hashtable expansion routine: under the
right circumstances it would leave old and new bucket headers pointing to the same list of records.
1 parent 7f79496 commit 86482e1

File tree

1 file changed

+44
-38
lines changed

1 file changed

+44
-38
lines changed

‎src/backend/utils/hash/dynahash.c

Lines changed: 44 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
*
88
*
99
* IDENTIFICATION
10-
* $Header: /cvsroot/pgsql/src/backend/utils/hash/dynahash.c,v 1.22 1999/05/25 16:12:28 momjian Exp $
10+
* $Header: /cvsroot/pgsql/src/backend/utils/hash/dynahash.c,v 1.23 1999/05/31 17:01:52 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -52,25 +52,23 @@
5252
#include "utils/memutils.h"
5353

5454
/*
55-
* Fast arithmetic, relying on powers of 2,
56-
* and on pre-processor concatenation property
55+
* Fast MOD arithmetic, assuming that y is a power of 2 !
5756
*/
5857

5958
#define MOD(x,y) ((x) & ((y)-1))
6059

61-
/*
62-
* external routines
63-
*/
64-
6560
/*
6661
* Private function prototypes
6762
*/
6863
static long *DynaHashAlloc(unsigned int size);
6964
static void DynaHashFree(Pointer ptr);
70-
static uint32 call_hash(HTAB *hashp, char *k, int len);
65+
static uint32 call_hash(HTAB *hashp, char *k);
7166
static SEG_OFFSET seg_alloc(HTAB *hashp);
7267
static int bucket_alloc(HTAB *hashp);
7368
static int dir_realloc(HTAB *hashp);
69+
static int expand_table(HTAB *hashp);
70+
static int hdefault(HTAB *hashp);
71+
static int init_htab(HTAB *hashp, int nelem);
7472

7573
typedef long *((*dhalloc_ptr) ());
7674

@@ -118,15 +116,6 @@ DynaHashFree(Pointer ptr)
118116

119117
#endif /* FRONTEND */
120118

121-
/* ----------------
122-
* Internal routines
123-
* ----------------
124-
*/
125-
126-
static int expand_table(HTAB *hashp);
127-
static int hdefault(HTAB *hashp);
128-
static int init_htab(HTAB *hashp, int nelem);
129-
130119

131120
/*
132121
* pointer access macros. Shared memory implementation cannot
@@ -220,6 +209,8 @@ hash_create(int nelem, HASHCTL *info, int flags)
220209
{
221210
hctl->ssize = info->ssize;
222211
hctl->sshift = my_log2(info->ssize);
212+
/* ssize had better be a power of 2 */
213+
Assert(hctl->ssize == (1L << hctl->sshift));
223214
}
224215
if (flags & HASH_FFACTOR)
225216
hctl->ffactor = info->ffactor;
@@ -412,6 +403,8 @@ hash_estimate_size(long num_entries, long keysize, long datasize)
412403
* XXX this sure looks thoroughly broken to me --- tgl 2/99.
413404
* It's freeing every entry individually --- but they weren't
414405
* allocated individually, see bucket_alloc!! Why doesn't it crash?
406+
* ANSWER: it probably does crash, but is never invoked in normal
407+
* operations...
415408
*/
416409

417410
void
@@ -479,14 +472,13 @@ hash_stats(char *where, HTAB *hashp)
479472
/*******************************SEARCH ROUTINES *****************************/
480473

481474
static uint32
482-
call_hash(HTAB *hashp, char *k, int len)
475+
call_hash(HTAB *hashp, char *k)
483476
{
477+
HHDR *hctl = hashp->hctl;
484478
long hash_val,
485479
bucket;
486-
HHDR *hctl;
487480

488-
hctl = hashp->hctl;
489-
hash_val = hashp->hash(k, len);
481+
hash_val = hashp->hash(k, (int) hctl->keysize);
490482

491483
bucket = hash_val & hctl->high_mask;
492484
if (bucket > hctl->max_bucket)
@@ -550,9 +542,9 @@ hash_search(HTAB *hashp,
550542
}
551543
else
552544
{
553-
bucket = call_hash(hashp, keyPtr, hctl->keysize);
545+
bucket = call_hash(hashp, keyPtr);
554546
segment_num = bucket >> hctl->sshift;
555-
segment_ndx = bucket & (hctl->ssize - 1);
547+
segment_ndx = MOD(bucket, hctl->ssize);
556548

557549
segp = GET_SEG(hashp, segment_num);
558550

@@ -598,8 +590,10 @@ hash_search(HTAB *hashp,
598590
Assert(hctl->nkeys > 0);
599591
hctl->nkeys--;
600592

601-
/* add the bucket to the freelist for this table. */
593+
/* remove record from hash bucket's chain. */
602594
*prevIndexPtr = curr->next;
595+
596+
/* add the record to the freelist for this table. */
603597
curr->next = hctl->freeBucketIndex;
604598
hctl->freeBucketIndex = currIndex;
605599

@@ -639,7 +633,6 @@ hash_search(HTAB *hashp,
639633
currIndex = hctl->freeBucketIndex;
640634
if (currIndex == INVALID_INDEX)
641635
{
642-
643636
/* no free elements. allocate another chunk of buckets */
644637
if (!bucket_alloc(hashp))
645638
return NULL;
@@ -722,7 +715,7 @@ hash_seq(HTAB *hashp)
722715
* initialize the search within this bucket.
723716
*/
724717
segment_num = curBucket >> hctl->sshift;
725-
segment_ndx = curBucket & (hctl->ssize - 1);
718+
segment_ndx = MOD(curBucket, hctl->ssize);
726719

727720
/*
728721
* first find the right segment in the table directory.
@@ -751,6 +744,10 @@ hash_seq(HTAB *hashp)
751744

752745

753746
/********************************* UTILITIES ************************/
747+
748+
/*
749+
* Expand the table by adding one more hash bucket.
750+
*/
754751
static int
755752
expand_table(HTAB *hashp)
756753
{
@@ -790,19 +787,31 @@ expand_table(HTAB *hashp)
790787
hctl->nsegs++;
791788
}
792789

793-
/* OK, we got a new bucket */
790+
/* OK, we created a new bucket */
794791
hctl->max_bucket++;
795-
old_bucket = (hctl->max_bucket & hctl->low_mask);
796792

793+
/*
794+
* *Before* changing masks, find old bucket corresponding to same hash
795+
* values; values in that bucket may need to be relocated to new bucket.
796+
* Note that new_bucket is certainly larger than low_mask at this point,
797+
* so we can skip the first step of the regular hash mask calc.
798+
*/
799+
old_bucket = (new_bucket & hctl->low_mask);
800+
801+
/*
802+
* If we crossed a power of 2, readjust masks.
803+
*/
797804
if (new_bucket > hctl->high_mask)
798805
{
799-
/* Starting a new doubling */
800806
hctl->low_mask = hctl->high_mask;
801807
hctl->high_mask = new_bucket | hctl->low_mask;
802808
}
803809

804810
/*
805-
* Relocate records to the new bucket
811+
* Relocate records to the new bucket. NOTE: because of the way the
812+
* hash masking is done in call_hash, only one old bucket can need to
813+
* be split at this point. With a different way of reducing the hash
814+
* value, that might not be true!
806815
*/
807816
old_segnum = old_bucket >> hctl->sshift;
808817
old_segndx = MOD(old_bucket, hctl->ssize);
@@ -816,12 +825,9 @@ expand_table(HTAB *hashp)
816825
chainIndex != INVALID_INDEX;
817826
chainIndex = nextIndex)
818827
{
819-
820828
chain = GET_BUCKET(hashp, chainIndex);
821829
nextIndex = chain->next;
822-
if (call_hash(hashp,
823-
(char *) &(chain->key),
824-
hctl->keysize) == old_bucket)
830+
if (call_hash(hashp, (char *) &(chain->key)) == old_bucket)
825831
{
826832
*old = chainIndex;
827833
old = &chain->next;
@@ -831,8 +837,10 @@ expand_table(HTAB *hashp)
831837
*newbi = chainIndex;
832838
newbi = &chain->next;
833839
}
834-
chain->next = INVALID_INDEX;
835840
}
841+
/* don't forget to terminate the rebuilt hash chains... */
842+
*old = INVALID_INDEX;
843+
*newbi = INVALID_INDEX;
836844
return 1;
837845
}
838846

@@ -907,15 +915,13 @@ bucket_alloc(HTAB *hashp)
907915
/* make sure its aligned correctly */
908916
bucketSize = MAXALIGN(bucketSize);
909917

910-
/*
911-
* tmpIndex is the shmem offset into the first bucket of the array.
912-
*/
913918
tmpBucket = (ELEMENT *)
914919
hashp->alloc((unsigned long) BUCKET_ALLOC_INCR * bucketSize);
915920

916921
if (!tmpBucket)
917922
return 0;
918923

924+
/* tmpIndex is the shmem offset into the first bucket of the array */
919925
tmpIndex = MAKE_HASHOFFSET(hashp, tmpBucket);
920926

921927
/* set the freebucket list to point to the first bucket */

0 commit comments

Comments
 (0)