一、简介

postgresql大部分的内存分配管理都是通过MemoryContext进行操作的，
多个相关的MemoryContext构成了一个树型结构，
多个树构成了一个森林。

实现了三种MemoryContext:

• SlabContext
• GenerationContext
• AllocSetContext

使用全局变量CurrentMemoryContext进行MemoryContext切换

二、编程范式

2.1 创建MemoryContext

newcontext = AllocSetContextCreate((MemoryContext) NULL,"TestMemoryContext",ALLOCSET_DEFAULT_SIZES);

2.2 切换需要使用的MemoryContext

MemoryContextSwitchTo(newcontext);

2.3 使用相应API进行分配/释放空间

//分配空间
item = (text *) palloc(VARHDRSZ + len + 1);
//分配空间，并且清空
plabel = palloc0(sizeof(pending_label));
//扩容/缩容
es->steps = repalloc(es->steps, sizeof(ExprEvalStep) * es->steps_alloc);
//释放空间
pfree(r);

2.4 重置MemoryContext

MemoryContextReset(argContext);

2.5 销毁MemoryContext

MemoryContextDelete(tmpCxt);

三、实现原理

3.1 数据结构简介

AllocSetContext由三部分构成， MemoryContextData + AllocBlock + AllocChunk
MemoryContextData：

• 由如下字段将各个MemoryContext构成树型结构

MemoryContext parent;		/* NULL if no parent (toplevel context) */
MemoryContext firstchild;	/* head of linked list of children */
MemoryContext prevchild;	/* previous child of same parent */
MemoryContext nextchild;	/* next child of same parent */

• 虚函数表，实现统一接口，不同实现

const MemoryContextMethods *methods;	/* virtual function table */

AllocBlock：

• 由如下字段将block构成一个双向链表

AllocBlock	prev;			/* prev block in aset's blocks list, if any */
AllocBlock	next;			/* next block in aset's blocks list, if any */

• 标识可用空间范围

char	   *freeptr;		/* start of free space in this block */
char	   *endptr;			/* end of space in this block */

AllocChunk：

• chunk中可用大小

Size		size;

3.2 初始化

#define AllocSetContextCreate \AllocSetContextCreateInternal#define ALLOCSET_DEFAULT_MINSIZE   0
#define ALLOCSET_DEFAULT_INITSIZE  (8 * 1024)
#define ALLOCSET_DEFAULT_MAXSIZE   (8 * 1024 * 1024)
#define ALLOCSET_DEFAULT_SIZES \ALLOCSET_DEFAULT_MINSIZE, ALLOCSET_DEFAULT_INITSIZE, ALLOCSET_DEFAULT_MAXSIZETopMemoryContext = AllocSetContextCreate((MemoryContext) NULL,"TopMemoryContext",ALLOCSET_DEFAULT_SIZES);

MemoryContext
AllocSetContextCreateInternal(MemoryContext parent,const char *name,Size minContextSize,Size initBlockSize,Size maxBlockSize)
{int			freeListIndex;Size		firstBlockSize;AllocSet	set;AllocBlock	block;
.../* Determine size of initial block */firstBlockSize = MAXALIGN(sizeof(AllocSetContext)) +ALLOC_BLOCKHDRSZ + ALLOC_CHUNKHDRSZ;if (minContextSize != 0)firstBlockSize = Max(firstBlockSize, minContextSize);elsefirstBlockSize = Max(firstBlockSize, initBlockSize);/** Allocate the initial block.  Unlike other aset.c blocks, it starts with* the context header and its block header follows that.*/set = (AllocSet) malloc(firstBlockSize);.../* Fill in the initial block's block header */block = (AllocBlock) (((char *) set) + MAXALIGN(sizeof(AllocSetContext)));block->aset = set;block->freeptr = ((char *) block) + ALLOC_BLOCKHDRSZ;block->endptr = ((char *) set) + firstBlockSize;block->prev = NULL;block->next = NULL;
.../* Remember block as part of block list */set->blocks = block;/* Mark block as not to be released at reset time */set->keeper = block;...set->initBlockSize = initBlockSize;set->maxBlockSize = maxBlockSize;set->nextBlockSize = initBlockSize;set->freeListIndex = freeListIndex;
...set->allocChunkLimit = ALLOC_CHUNK_LIMIT;while ((Size) (set->allocChunkLimit + ALLOC_CHUNKHDRSZ) >(Size) ((maxBlockSize - ALLOC_BLOCKHDRSZ) / ALLOC_CHUNK_FRACTION))set->allocChunkLimit >>= 1;/* Finally, do the type-independent part of context creation */MemoryContextCreate((MemoryContext) set,T_AllocSetContext,&AllocSetMethods,parent,name);((MemoryContext) set)->mem_allocated = firstBlockSize;return (MemoryContext) set;
}

3.3 分配空间

void *
palloc(Size size)
{/* duplicates MemoryContextAlloc to avoid increased overhead */void	   *ret;MemoryContext context = CurrentMemoryContext;
...context->isReset = false;ret = context->methods->alloc(context, size);
...return ret;
}

3.3.1 分配空间大于allocChunkLimit

static void *
AllocSetAlloc(MemoryContext context, Size size)
{AllocSet	set = (AllocSet) context;AllocBlock	block;AllocChunk	chunk;int			fidx;Size		chunk_size;Size		blksize;.../** If requested size exceeds maximum for chunks, allocate an entire block* for this request.*/if (size > set->allocChunkLimit){chunk_size = MAXALIGN(size);blksize = chunk_size + ALLOC_BLOCKHDRSZ + ALLOC_CHUNKHDRSZ;block = (AllocBlock) malloc(blksize);if (block == NULL)return NULL;context->mem_allocated += blksize;block->aset = set;block->freeptr = block->endptr = ((char *) block) + blksize;chunk = (AllocChunk) (((char *) block) + ALLOC_BLOCKHDRSZ);chunk->aset = set;chunk->size = chunk_size;/** Stick the new block underneath the active allocation block, if any,* so that we don't lose the use of the space remaining therein.*/if (set->blocks != NULL){block->prev = set->blocks;block->next = set->blocks->next;if (block->next)block->next->prev = block;set->blocks->next = block;}else{block->prev = NULL;block->next = NULL;set->blocks = block;}return AllocChunkGetPointer(chunk);}
...
}

例如分配16K

char *ptr = palloc(16 * 1024);

例如分配32K

char *ptr = palloc(32 * 1024);

3.3.2 分配空间小于等于allocChunkLimit

#define ALLOC_MINBITS		3	/* smallest chunk size is 8 bytes */static inline int
AllocSetFreeIndex(Size size)
{int			idx;if (size > (1 << ALLOC_MINBITS)){
...idx = 31 - __builtin_clz((uint32) size - 1) - ALLOC_MINBITS + 1;
...}elseidx = 0;return idx;
}

fidx = AllocSetFreeIndex(size);/** Choose the actual chunk size to allocate.*/
chunk_size = (1 << ALLOC_MINBITS) << fidx;

• 分配小于等于8字节
  小于等于8的，最终将分配8字节

• 分配大于8字节
  通过__builtin_clz计算size-1的前导0的个数，然后通过减法计算size的对其位数（非常高效的方式）

3.3.2.1 当前block有足够空间

if ((block = set->blocks) != NULL)
{
...
}
/** OK, do the allocation*/chunk = (AllocChunk) (block->freeptr);
...block->freeptr += (chunk_size + ALLOC_CHUNKHDRSZ);
...chunk->aset = (void *) set;chunk->size = chunk_size;
...return AllocChunkGetPointer(chunk);

例如分配20byte

char *ptr = palloc(20);

通过对其，实际分配32byte

3.3.2.2 当前block没有足够的空间

随着分配，当前block中的可用空间越来越小，再次分配时，将不够当前分配

Size availspace = block->endptr - block->freeptr;
if (availspace < (chunk_size + ALLOC_CHUNKHDRSZ))
{
...
}

3.3.2.2.1 当前block还有一些空间

if (availspace < (chunk_size + ALLOC_CHUNKHDRSZ)){while (availspace >= ((1 << ALLOC_MINBITS) + ALLOC_CHUNKHDRSZ)){Size		availchunk = availspace - ALLOC_CHUNKHDRSZ;int			a_fidx = AllocSetFreeIndex(availchunk);...if (availchunk != ((Size) 1 << (a_fidx + ALLOC_MINBITS))){a_fidx--;Assert(a_fidx >= 0);availchunk = ((Size) 1 << (a_fidx + ALLOC_MINBITS));}chunk = (AllocChunk) (block->freeptr);
...block->freeptr += (availchunk + ALLOC_CHUNKHDRSZ);availspace -= (availchunk + ALLOC_CHUNKHDRSZ);chunk->size = availchunk;chunk->aset = (void *) set->freelist[a_fidx];set->freelist[a_fidx] = chunk;}/* Mark that we need to create a new block */block = NULL;}

将剩余空间大小，按照对其的大小放到freelist中，构成一个单链表，用于后续分配时，直接从这里获取。
可能会有一小块用不了的空间

3.3.2.2.2 创建新block

• 第一次创建时，使用initBlockSize
• 后续将会是上次block的两倍，当大于maxBlockSize，使用maxBlockSize
• 如果新block大小依然小于需要分配的空间，则继续扩大

/** Time to create a new regular (multi-chunk) block?*/if (block == NULL){Size		required_size;/** The first such block has size initBlockSize, and we double the* space in each succeeding block, but not more than maxBlockSize.*/blksize = set->nextBlockSize;set->nextBlockSize <<= 1;if (set->nextBlockSize > set->maxBlockSize)set->nextBlockSize = set->maxBlockSize;/** If initBlockSize is less than ALLOC_CHUNK_LIMIT, we could need more* space... but try to keep it a power of 2.*/required_size = chunk_size + ALLOC_BLOCKHDRSZ + ALLOC_CHUNKHDRSZ;while (blksize < required_size)blksize <<= 1;/* Try to allocate it */block = (AllocBlock) malloc(blksize);
...if (block == NULL)return NULL;context->mem_allocated += blksize;block->aset = set;block->freeptr = ((char *) block) + ALLOC_BLOCKHDRSZ;block->endptr = ((char *) block) + blksize;/* Mark unallocated space NOACCESS. */VALGRIND_MAKE_MEM_NOACCESS(block->freeptr,blksize - ALLOC_BLOCKHDRSZ);block->prev = NULL;block->next = set->blocks;if (block->next)block->next->prev = block;set->blocks = block;}

3.3.3 从freelist中分配

fidx = AllocSetFreeIndex(size);
chunk = set->freelist[fidx];
if (chunk != NULL)
{set->freelist[fidx] = (AllocChunk) chunk->aset;chunk->aset = (void *) set;
...return AllocChunkGetPointer(chunk);
}

3.4 释放空间

void
pfree(void *pointer)
{MemoryContext context = GetMemoryChunkContext(pointer);context->methods->free_p(context, pointer);
...
}

3.4.1 直接释放

static void
AllocSetFree(MemoryContext context, void *pointer)
{AllocSet	set = (AllocSet) context;AllocChunk	chunk = AllocPointerGetChunk(pointer);
...if (chunk->size > set->allocChunkLimit){AllocBlock	block = (AllocBlock) (((char *) chunk) - ALLOC_BLOCKHDRSZ);.../* OK, remove block from aset's list and free it */if (block->prev)block->prev->next = block->next;elseset->blocks = block->next;if (block->next)block->next->prev = block->prev;context->mem_allocated -= block->endptr - ((char *) block);
...free(block);}else{...}
}

见 3.3.1, 大于chunklimit的直接malloc的空间，而不是从block中分配的，因此直接释放，并且将此block从双向链表中删除。

3.4.2 加入freelist中

static void
AllocSetFree(MemoryContext context, void *pointer)
{AllocSet	set = (AllocSet) context;AllocChunk	chunk = AllocPointerGetChunk(pointer);/* Allow access to private part of chunk header. */VALGRIND_MAKE_MEM_DEFINED(chunk, ALLOCCHUNK_PRIVATE_LEN);#ifdef MEMORY_CONTEXT_CHECKING/* Test for someone scribbling on unused space in chunk */if (chunk->requested_size < chunk->size)if (!sentinel_ok(pointer, chunk->requested_size))elog(WARNING, "detected write past chunk end in %s %p",set->header.name, chunk);
#endifif (chunk->size > set->allocChunkLimit){...}else{/* Normal case, put the chunk into appropriate freelist */int			fidx = AllocSetFreeIndex(chunk->size);chunk->aset = (void *) set->freelist[fidx];
...set->freelist[fidx] = chunk;}
}