Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit86482e1

Browse files
committed
Correct serious bug in hashtable expansion routine: under the
right circumstances it would leave old and new bucket headers pointing tothe same list of records.
1 parent7f79496 commit86482e1

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
#defineMOD(x,y) ((x) & ((y)-1))
6059

61-
/*
62-
* external routines
63-
*/
64-
6560
/*
6661
* Private function prototypes
6762
*/
6863
staticlong*DynaHashAlloc(unsignedintsize);
6964
staticvoidDynaHashFree(Pointerptr);
70-
staticuint32call_hash(HTAB*hashp,char*k,intlen);
65+
staticuint32call_hash(HTAB*hashp,char*k);
7166
staticSEG_OFFSETseg_alloc(HTAB*hashp);
7267
staticintbucket_alloc(HTAB*hashp);
7368
staticintdir_realloc(HTAB*hashp);
69+
staticintexpand_table(HTAB*hashp);
70+
staticinthdefault(HTAB*hashp);
71+
staticintinit_htab(HTAB*hashp,intnelem);
7472

7573
typedeflong*((*dhalloc_ptr) ());
7674

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

119117
#endif/* FRONTEND */
120118

121-
/* ----------------
122-
* Internal routines
123-
* ----------------
124-
*/
125-
126-
staticintexpand_table(HTAB*hashp);
127-
staticinthdefault(HTAB*hashp);
128-
staticintinit_htab(HTAB*hashp,intnelem);
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
staticuint32
482-
call_hash(HTAB*hashp,char*k,intlen)
475+
call_hash(HTAB*hashp,char*k)
483476
{
477+
HHDR*hctl=hashp->hctl;
484478
longhash_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
returnNULL;
@@ -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
staticint
755752
expand_table(HTAB*hashp)
756753
{
@@ -790,19 +787,31 @@ expand_table(HTAB *hashp)
790787
hctl->nsegs++;
791788
}
792789

793-
/* OK, wegot a new bucket */
790+
/* OK, wecreated 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
return1;
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
return0;
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)
[8]ページ先頭
©2009-2025 Movatter.jp