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

Commite0a6ed8

Browse files
committed
Use doubly-linked block lists in aset.c to reduce large-chunk overhead.
Large chunks (those too large for any palloc freelist) are managed asseparate blocks. Formerly, realloc'ing or pfree'ing such a chunk requiredO(N) time in a context with N blocks, since we had to traipse down thesingly-linked block list to locate the block's predecessor before we couldfix the list links. This can result in O(N^2) runtime in situations wherelarge numbers of such chunks are manipulated within one context. Caseslike that were not foreseen in the original design of aset.c, and indeeddidn't arise until fairly recently. But such problems can now occur inreorderbuffer.c and in hash joining, both of which make repeated largerequests without scaling up their request size as they do so, and whichwill free their requests in not-necessarily-LIFO order.To fix, change the block list from singly-linked to doubly-linked.This adds another 4 or 8 bytes to ALLOC_BLOCKHDRSZ, but that doesn'tseem like unacceptable overhead, since aset.c's blocks are normally8K or more, and never less than 1K in current practice.In passing, get rid of some redundant AllocChunkGetPointer() calls inAllocSetRealloc (the compiler might be smart enough to optimize theseaway anyway, but no need to assume that) and improve AllocSetCheck'schecking of block header fields.Back-patch to 9.4 where reorderbuffer.c appeared. We could take thisfurther back, but currently there's no evidence that it would be useful.Discussion:https://postgr.es/m/CAMkU=1x1hvue1XYrZoWk_omG0Ja5nBvTdvgrOeVkkeqs71CV8g@mail.gmail.com
1 parentfeb4d35 commite0a6ed8

File tree

1 file changed

+66
-42
lines changed

1 file changed

+66
-42
lines changed

‎src/backend/utils/mmgr/aset.c

Lines changed: 66 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -201,7 +201,8 @@ typedef AllocSetContext *AllocSet;
201201
typedefstructAllocBlockData
202202
{
203203
AllocSetaset;/* aset that owns this block */
204-
AllocBlocknext;/* next block in aset's blocks list */
204+
AllocBlockprev;/* prev block in aset's blocks list, if any */
205+
AllocBlocknext;/* next block in aset's blocks list, if any */
205206
char*freeptr;/* start of free space in this block */
206207
char*endptr;/* end of space in this block */
207208
}AllocBlockData;
@@ -513,7 +514,10 @@ AllocSetContextCreate(MemoryContext parent,
513514
block->aset=set;
514515
block->freeptr= ((char*)block)+ALLOC_BLOCKHDRSZ;
515516
block->endptr= ((char*)block)+blksize;
517+
block->prev=NULL;
516518
block->next=set->blocks;
519+
if (block->next)
520+
block->next->prev=block;
517521
set->blocks=block;
518522
/* Mark block as not to be released at reset time */
519523
set->keeper=block;
@@ -595,6 +599,7 @@ AllocSetReset(MemoryContext context)
595599
VALGRIND_MAKE_MEM_NOACCESS(datastart,block->freeptr-datastart);
596600
#endif
597601
block->freeptr=datastart;
602+
block->prev=NULL;
598603
block->next=NULL;
599604
}
600605
else
@@ -701,16 +706,20 @@ AllocSetAlloc(MemoryContext context, Size size)
701706
#endif
702707

703708
/*
704-
* Stick the new block underneath the active allocation block,so that
705-
* we don't lose the use of the space remaining therein.
709+
* Stick the new block underneath the active allocation block,if any,
710+
*so thatwe don't lose the use of the space remaining therein.
706711
*/
707712
if (set->blocks!=NULL)
708713
{
714+
block->prev=set->blocks;
709715
block->next=set->blocks->next;
716+
if (block->next)
717+
block->next->prev=block;
710718
set->blocks->next=block;
711719
}
712720
else
713721
{
722+
block->prev=NULL;
714723
block->next=NULL;
715724
set->blocks=block;
716725
}
@@ -891,7 +900,10 @@ AllocSetAlloc(MemoryContext context, Size size)
891900
VALGRIND_MAKE_MEM_NOACCESS(block->freeptr,
892901
blksize-ALLOC_BLOCKHDRSZ);
893902

903+
block->prev=NULL;
894904
block->next=set->blocks;
905+
if (block->next)
906+
block->next->prev=block;
895907
set->blocks=block;
896908
}
897909

@@ -951,29 +963,28 @@ AllocSetFree(MemoryContext context, void *pointer)
951963
{
952964
/*
953965
* Big chunks are certain to have been allocated as single-chunk
954-
* blocks.Find the containing block and return it to malloc().
966+
* blocks.Just unlink that block and return it to malloc().
955967
*/
956-
AllocBlockblock=set->blocks;
957-
AllocBlockprevblock=NULL;
968+
AllocBlockblock= (AllocBlock) (((char*)chunk)-ALLOC_BLOCKHDRSZ);
958969

959-
while (block!=NULL)
960-
{
961-
if (chunk== (AllocChunk) (((char*)block)+ALLOC_BLOCKHDRSZ))
962-
break;
963-
prevblock=block;
964-
block=block->next;
965-
}
966-
if (block==NULL)
970+
/*
971+
* Try to verify that we have a sane block pointer: it should
972+
* reference the correct aset, and freeptr and endptr should point
973+
* just past the chunk.
974+
*/
975+
if (block->aset!=set||
976+
block->freeptr!=block->endptr||
977+
block->freeptr!= ((char*)block)+
978+
(chunk->size+ALLOC_BLOCKHDRSZ+ALLOC_CHUNKHDRSZ))
967979
elog(ERROR,"could not find block containing chunk %p",chunk);
968-
/* let's just make sure chunk is the only one in the block */
969-
Assert(block->freeptr== ((char*)block)+
970-
(chunk->size+ALLOC_BLOCKHDRSZ+ALLOC_CHUNKHDRSZ));
971980

972981
/* OK, remove block from aset's list and free it */
973-
if (prevblock==NULL)
974-
set->blocks=block->next;
982+
if (block->prev)
983+
block->prev->next=block->next;
975984
else
976-
prevblock->next=block->next;
985+
set->blocks=block->next;
986+
if (block->next)
987+
block->next->prev=block->prev;
977988
#ifdefCLOBBER_FREED_MEMORY
978989
wipe_mem(block,block->freeptr- ((char*)block));
979990
#endif
@@ -1079,27 +1090,24 @@ AllocSetRealloc(MemoryContext context, void *pointer, Size size)
10791090
if (oldsize>set->allocChunkLimit)
10801091
{
10811092
/*
1082-
* The chunk must have been allocated as a single-chunk block.Find
1083-
*the containing block and userealloc() to makeitbigger with
1084-
*minimum spacewastage.
1093+
* The chunk must have been allocated as a single-chunk block.Use
1094+
* realloc() to makethe containing blockbigger with minimum space
1095+
* wastage.
10851096
*/
1086-
AllocBlockblock=set->blocks;
1087-
AllocBlockprevblock=NULL;
1097+
AllocBlockblock= (AllocBlock) (((char*)chunk)-ALLOC_BLOCKHDRSZ);
10881098
Sizechksize;
10891099
Sizeblksize;
10901100

1091-
while (block!=NULL)
1092-
{
1093-
if (chunk== (AllocChunk) (((char*)block)+ALLOC_BLOCKHDRSZ))
1094-
break;
1095-
prevblock=block;
1096-
block=block->next;
1097-
}
1098-
if (block==NULL)
1101+
/*
1102+
* Try to verify that we have a sane block pointer: it should
1103+
* reference the correct aset, and freeptr and endptr should point
1104+
* just past the chunk.
1105+
*/
1106+
if (block->aset!=set||
1107+
block->freeptr!=block->endptr||
1108+
block->freeptr!= ((char*)block)+
1109+
(chunk->size+ALLOC_BLOCKHDRSZ+ALLOC_CHUNKHDRSZ))
10991110
elog(ERROR,"could not find block containing chunk %p",chunk);
1100-
/* let's just make sure chunk is the only one in the block */
1101-
Assert(block->freeptr== ((char*)block)+
1102-
(chunk->size+ALLOC_BLOCKHDRSZ+ALLOC_CHUNKHDRSZ));
11031111

11041112
/* Do the realloc */
11051113
chksize=MAXALIGN(size);
@@ -1112,10 +1120,12 @@ AllocSetRealloc(MemoryContext context, void *pointer, Size size)
11121120
/* Update pointers since block has likely been moved */
11131121
chunk= (AllocChunk) (((char*)block)+ALLOC_BLOCKHDRSZ);
11141122
pointer=AllocChunkGetPointer(chunk);
1115-
if (prevblock==NULL)
1116-
set->blocks=block;
1123+
if (block->prev)
1124+
block->prev->next=block;
11171125
else
1118-
prevblock->next=block;
1126+
set->blocks=block;
1127+
if (block->next)
1128+
block->next->prev=block;
11191129
chunk->size=chksize;
11201130

11211131
#ifdefMEMORY_CONTEXT_CHECKING
@@ -1139,7 +1149,7 @@ AllocSetRealloc(MemoryContext context, void *pointer, Size size)
11391149

11401150
/* set mark to catch clobber of "unused" space */
11411151
if (size<chunk->size)
1142-
set_sentinel(AllocChunkGetPointer(chunk),size);
1152+
set_sentinel(pointer,size);
11431153
#else/* !MEMORY_CONTEXT_CHECKING */
11441154

11451155
/*
@@ -1152,7 +1162,8 @@ AllocSetRealloc(MemoryContext context, void *pointer, Size size)
11521162

11531163
/* Make any trailing alignment padding NOACCESS. */
11541164
VALGRIND_MAKE_MEM_NOACCESS((char*)pointer+size,chksize-size);
1155-
returnAllocChunkGetPointer(chunk);
1165+
1166+
returnpointer;
11561167
}
11571168
else
11581169
{
@@ -1306,9 +1317,12 @@ AllocSetCheck(MemoryContext context)
13061317
{
13071318
AllocSetset= (AllocSet)context;
13081319
char*name=set->header.name;
1320+
AllocBlockprevblock;
13091321
AllocBlockblock;
13101322

1311-
for (block=set->blocks;block!=NULL;block=block->next)
1323+
for (prevblock=NULL,block=set->blocks;
1324+
block!=NULL;
1325+
prevblock=block,block=block->next)
13121326
{
13131327
char*bpoz= ((char*)block)+ALLOC_BLOCKHDRSZ;
13141328
longblk_used=block->freeptr-bpoz;
@@ -1325,6 +1339,16 @@ AllocSetCheck(MemoryContext context)
13251339
name,block);
13261340
}
13271341

1342+
/*
1343+
* Check block header fields
1344+
*/
1345+
if (block->aset!=set||
1346+
block->prev!=prevblock||
1347+
block->freeptr<bpoz||
1348+
block->freeptr>block->endptr)
1349+
elog(WARNING,"problem in alloc set %s: corrupt header in block %p",
1350+
name,block);
1351+
13281352
/*
13291353
* Chunk walker
13301354
*/

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp