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

Commitff97741

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 parentf35742c commitff97741

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
@@ -148,7 +148,8 @@ typedef AllocSetContext *AllocSet;
148148
typedefstructAllocBlockData
149149
{
150150
AllocSetaset;/* aset that owns this block */
151-
AllocBlocknext;/* next block in aset's blocks list */
151+
AllocBlockprev;/* prev block in aset's blocks list, if any */
152+
AllocBlocknext;/* next block in aset's blocks list, if any */
152153
char*freeptr;/* start of free space in this block */
153154
char*endptr;/* end of space in this block */
154155
}AllocBlockData;
@@ -407,7 +408,10 @@ AllocSetContextCreate(MemoryContext parent,
407408
block->aset=set;
408409
block->freeptr= ((char*)block)+ALLOC_BLOCKHDRSZ;
409410
block->endptr= ((char*)block)+blksize;
411+
block->prev=NULL;
410412
block->next=set->blocks;
413+
if (block->next)
414+
block->next->prev=block;
411415
set->blocks=block;
412416
/* Mark block as not to be released at reset time */
413417
set->keeper=block;
@@ -489,6 +493,7 @@ AllocSetReset(MemoryContext context)
489493
VALGRIND_MAKE_MEM_NOACCESS(datastart,block->freeptr-datastart);
490494
#endif
491495
block->freeptr=datastart;
496+
block->prev=NULL;
492497
block->next=NULL;
493498
}
494499
else
@@ -595,16 +600,20 @@ AllocSetAlloc(MemoryContext context, Size size)
595600
#endif
596601

597602
/*
598-
* Stick the new block underneath the active allocation block,so that
599-
* we don't lose the use of the space remaining therein.
603+
* Stick the new block underneath the active allocation block,if any,
604+
*so thatwe don't lose the use of the space remaining therein.
600605
*/
601606
if (set->blocks!=NULL)
602607
{
608+
block->prev=set->blocks;
603609
block->next=set->blocks->next;
610+
if (block->next)
611+
block->next->prev=block;
604612
set->blocks->next=block;
605613
}
606614
else
607615
{
616+
block->prev=NULL;
608617
block->next=NULL;
609618
set->blocks=block;
610619
}
@@ -785,7 +794,10 @@ AllocSetAlloc(MemoryContext context, Size size)
785794
VALGRIND_MAKE_MEM_NOACCESS(block->freeptr,
786795
blksize-ALLOC_BLOCKHDRSZ);
787796

797+
block->prev=NULL;
788798
block->next=set->blocks;
799+
if (block->next)
800+
block->next->prev=block;
789801
set->blocks=block;
790802
}
791803

@@ -845,29 +857,28 @@ AllocSetFree(MemoryContext context, void *pointer)
845857
{
846858
/*
847859
* Big chunks are certain to have been allocated as single-chunk
848-
* blocks.Find the containing block and return it to malloc().
860+
* blocks.Just unlink that block and return it to malloc().
849861
*/
850-
AllocBlockblock=set->blocks;
851-
AllocBlockprevblock=NULL;
862+
AllocBlockblock= (AllocBlock) (((char*)chunk)-ALLOC_BLOCKHDRSZ);
852863

853-
while (block!=NULL)
854-
{
855-
if (chunk== (AllocChunk) (((char*)block)+ALLOC_BLOCKHDRSZ))
856-
break;
857-
prevblock=block;
858-
block=block->next;
859-
}
860-
if (block==NULL)
864+
/*
865+
* Try to verify that we have a sane block pointer: it should
866+
* reference the correct aset, and freeptr and endptr should point
867+
* just past the chunk.
868+
*/
869+
if (block->aset!=set||
870+
block->freeptr!=block->endptr||
871+
block->freeptr!= ((char*)block)+
872+
(chunk->size+ALLOC_BLOCKHDRSZ+ALLOC_CHUNKHDRSZ))
861873
elog(ERROR,"could not find block containing chunk %p",chunk);
862-
/* let's just make sure chunk is the only one in the block */
863-
Assert(block->freeptr== ((char*)block)+
864-
(chunk->size+ALLOC_BLOCKHDRSZ+ALLOC_CHUNKHDRSZ));
865874

866875
/* OK, remove block from aset's list and free it */
867-
if (prevblock==NULL)
868-
set->blocks=block->next;
876+
if (block->prev)
877+
block->prev->next=block->next;
869878
else
870-
prevblock->next=block->next;
879+
set->blocks=block->next;
880+
if (block->next)
881+
block->next->prev=block->prev;
871882
#ifdefCLOBBER_FREED_MEMORY
872883
wipe_mem(block,block->freeptr- ((char*)block));
873884
#endif
@@ -973,27 +984,24 @@ AllocSetRealloc(MemoryContext context, void *pointer, Size size)
973984
if (oldsize>set->allocChunkLimit)
974985
{
975986
/*
976-
* The chunk must have been allocated as a single-chunk block.Find
977-
*the containing block and userealloc() to makeitbigger with
978-
*minimum spacewastage.
987+
* The chunk must have been allocated as a single-chunk block.Use
988+
* realloc() to makethe containing blockbigger with minimum space
989+
* wastage.
979990
*/
980-
AllocBlockblock=set->blocks;
981-
AllocBlockprevblock=NULL;
991+
AllocBlockblock= (AllocBlock) (((char*)chunk)-ALLOC_BLOCKHDRSZ);
982992
Sizechksize;
983993
Sizeblksize;
984994

985-
while (block!=NULL)
986-
{
987-
if (chunk== (AllocChunk) (((char*)block)+ALLOC_BLOCKHDRSZ))
988-
break;
989-
prevblock=block;
990-
block=block->next;
991-
}
992-
if (block==NULL)
995+
/*
996+
* Try to verify that we have a sane block pointer: it should
997+
* reference the correct aset, and freeptr and endptr should point
998+
* just past the chunk.
999+
*/
1000+
if (block->aset!=set||
1001+
block->freeptr!=block->endptr||
1002+
block->freeptr!= ((char*)block)+
1003+
(chunk->size+ALLOC_BLOCKHDRSZ+ALLOC_CHUNKHDRSZ))
9931004
elog(ERROR,"could not find block containing chunk %p",chunk);
994-
/* let's just make sure chunk is the only one in the block */
995-
Assert(block->freeptr== ((char*)block)+
996-
(chunk->size+ALLOC_BLOCKHDRSZ+ALLOC_CHUNKHDRSZ));
9971005

9981006
/* Do the realloc */
9991007
chksize=MAXALIGN(size);
@@ -1006,10 +1014,12 @@ AllocSetRealloc(MemoryContext context, void *pointer, Size size)
10061014
/* Update pointers since block has likely been moved */
10071015
chunk= (AllocChunk) (((char*)block)+ALLOC_BLOCKHDRSZ);
10081016
pointer=AllocChunkGetPointer(chunk);
1009-
if (prevblock==NULL)
1010-
set->blocks=block;
1017+
if (block->prev)
1018+
block->prev->next=block;
10111019
else
1012-
prevblock->next=block;
1020+
set->blocks=block;
1021+
if (block->next)
1022+
block->next->prev=block;
10131023
chunk->size=chksize;
10141024

10151025
#ifdefMEMORY_CONTEXT_CHECKING
@@ -1033,7 +1043,7 @@ AllocSetRealloc(MemoryContext context, void *pointer, Size size)
10331043

10341044
/* set mark to catch clobber of "unused" space */
10351045
if (size<chunk->size)
1036-
set_sentinel(AllocChunkGetPointer(chunk),size);
1046+
set_sentinel(pointer,size);
10371047
#else/* !MEMORY_CONTEXT_CHECKING */
10381048

10391049
/*
@@ -1046,7 +1056,8 @@ AllocSetRealloc(MemoryContext context, void *pointer, Size size)
10461056

10471057
/* Make any trailing alignment padding NOACCESS. */
10481058
VALGRIND_MAKE_MEM_NOACCESS((char*)pointer+size,chksize-size);
1049-
returnAllocChunkGetPointer(chunk);
1059+
1060+
returnpointer;
10501061
}
10511062
else
10521063
{
@@ -1200,9 +1211,12 @@ AllocSetCheck(MemoryContext context)
12001211
{
12011212
AllocSetset= (AllocSet)context;
12021213
char*name=set->header.name;
1214+
AllocBlockprevblock;
12031215
AllocBlockblock;
12041216

1205-
for (block=set->blocks;block!=NULL;block=block->next)
1217+
for (prevblock=NULL,block=set->blocks;
1218+
block!=NULL;
1219+
prevblock=block,block=block->next)
12061220
{
12071221
char*bpoz= ((char*)block)+ALLOC_BLOCKHDRSZ;
12081222
longblk_used=block->freeptr-bpoz;
@@ -1219,6 +1233,16 @@ AllocSetCheck(MemoryContext context)
12191233
name,block);
12201234
}
12211235

1236+
/*
1237+
* Check block header fields
1238+
*/
1239+
if (block->aset!=set||
1240+
block->prev!=prevblock||
1241+
block->freeptr<bpoz||
1242+
block->freeptr>block->endptr)
1243+
elog(WARNING,"problem in alloc set %s: corrupt header in block %p",
1244+
name,block);
1245+
12221246
/*
12231247
* Chunk walker
12241248
*/

0 commit comments

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