/*-------------------------------------------------------------------------
 *
 * generation.c
 *   Generational allocator definitions.
 *
 * Generation is a custom MemoryContext implementation designed for cases of
 * chunks with similar lifespan.
 *
 * Portions Copyright (c) 2017-2025, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *   src/backend/utils/mmgr/generation.c
 *
 *
 * This memory context is based on the assumption that the chunks are freed
 * roughly in the same order as they were allocated (FIFO), or in groups with
 * similar lifespan (generations - hence the name of the context). This is
 * typical for various queue-like use cases, i.e. when tuples are constructed,
 * processed and then thrown away.
 *
 * The memory context uses a very simple approach to free space management.
 * Instead of a complex global freelist, each block tracks a number
 * of allocated and freed chunks.  The block is classed as empty when the
 * number of free chunks is equal to the number of allocated chunks.  When
 * this occurs, instead of freeing the block, we try to "recycle" it, i.e.
 * reuse it for new allocations.  This is done by setting the block in the
 * context's 'freeblock' field.  If the freeblock field is already occupied
 * by another free block we simply return the newly empty block to malloc.
 *
 * This approach to free blocks requires fewer malloc/free calls for truly
 * first allocated, first free'd allocation patterns.
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "lib/ilist.h"
#include "port/pg_bitutils.h"
#include "utils/memdebug.h"
#include "utils/memutils.h"
#include "utils/memutils_internal.h"
#include "utils/memutils_memorychunk.h"


#define Generation_BLOCKHDRSZ MAXALIGN(sizeof(GenerationBlock))
#define Generation_CHUNKHDRSZ sizeof(MemoryChunk)

#define Generation_CHUNK_FRACTION 8

typedef struct GenerationBlock GenerationBlock; /* forward reference */

typedef void *GenerationPointer;

/*
 * GenerationContext is a simple memory context not reusing allocated chunks,
 * and freeing blocks once all chunks are freed.
 */
typedef struct GenerationContext
{
 MemoryContextData header; /* Standard memory-context fields */

 /* Generational context parameters */
 uint32  initBlockSize; /* initial block size */
 uint32  maxBlockSize; /* maximum block size */
 uint32  nextBlockSize; /* next block size to allocate */
 uint32  allocChunkLimit; /* effective chunk size limit */

 GenerationBlock *block;  /* current (most recently allocated) block */
 GenerationBlock *freeblock; /* pointer to an empty block that's being
 * recycled, or NULL if there's no such block. */
 dlist_head blocks;   /* list of blocks */
} GenerationContext;

/*
 * GenerationBlock
 *  GenerationBlock is the unit of memory that is obtained by generation.c
 *  from malloc().  It contains zero or more MemoryChunks, which are the
 *  units requested by palloc() and freed by pfree().  MemoryChunks cannot
 *  be returned to malloc() individually, instead pfree() updates the free
 *  counter of the block and when all chunks in a block are free the whole
 *  block can be returned to malloc().
 *
 *  GenerationBlock is the header data for a block --- the usable space
 *  within the block begins at the next alignment boundary.
 */
struct GenerationBlock
{
 dlist_node node;   /* doubly-linked list of blocks */
 GenerationContext *context; /* pointer back to the owning context */
 Size  blksize;  /* allocated size of this block */
 int   nchunks;  /* number of chunks in the block */
 int   nfree;   /* number of free chunks */
 char    *freeptr;  /* start of free space in this block */
 char    *endptr;   /* end of space in this block */
};

/*
 * GenerationIsValid
 *  True iff set is valid generation set.
 */
#define GenerationIsValid(set) \
 (PointerIsValid(set) && IsA(set, GenerationContext))

/*
 * GenerationBlockIsValid
 *  True iff block is valid block of generation set.
 */
#define GenerationBlockIsValid(block) \
 (PointerIsValid(block) && GenerationIsValid((block)->context))

/*
 * GenerationBlockIsEmpty
 *  True iff block contains no chunks
 */
#define GenerationBlockIsEmpty(b) ((b)->nchunks == 0)

/*
 * We always store external chunks on a dedicated block.  This makes fetching
 * the block from an external chunk easy since it's always the first and only
 * chunk on the block.
 */
#define ExternalChunkGetBlock(chunk) \
 (GenerationBlock *) ((char *) chunk - Generation_BLOCKHDRSZ)

/* Obtain the keeper block for a generation context */
#define KeeperBlock(set) \
 ((GenerationBlock *) (((char *) set) + \
 MAXALIGN(sizeof(GenerationContext))))

/* Check if the block is the keeper block of the given generation context */
#define IsKeeperBlock(set, block) ((block) == (KeeperBlock(set)))

/* Inlined helper functions */
static inline void GenerationBlockInit(GenerationContext *context,
            GenerationBlock *block,
            Size blksize);
static inline void GenerationBlockMarkEmpty(GenerationBlock *block);
static inline Size GenerationBlockFreeBytes(GenerationBlock *block);
static inline void GenerationBlockFree(GenerationContext *set,
            GenerationBlock *block);


/*
 * Public routines
 */


/*
 * GenerationContextCreate
 *  Create a new Generation context.
 *
 * parent: parent context, or NULL if top-level context
 * name: name of context (must be statically allocated)
 * minContextSize: minimum context size
 * initBlockSize: initial allocation block size
 * maxBlockSize: maximum allocation block size
 */
MemoryContext
GenerationContextCreate(MemoryContext parent,
      const char *name,
      Size minContextSize,
      Size initBlockSize,
      Size maxBlockSize)
{
 Size  firstBlockSize;
 Size  allocSize;
 GenerationContext *set;
 GenerationBlock *block;

 /* ensure MemoryChunk's size is properly maxaligned */
 StaticAssertDecl(Generation_CHUNKHDRSZ == MAXALIGN(Generation_CHUNKHDRSZ),
      "sizeof(MemoryChunk) is not maxaligned");

 /*
  * First, validate allocation parameters.  Asserts seem sufficient because
  * nobody varies their parameters at runtime.  We somewhat arbitrarily
  * enforce a minimum 1K block size.  We restrict the maximum block size to
  * MEMORYCHUNK_MAX_BLOCKOFFSET as MemoryChunks are limited to this in
  * regards to addressing the offset between the chunk and the block that
  * the chunk is stored on.  We would be unable to store the offset between
  * the chunk and block for any chunks that were beyond
  * MEMORYCHUNK_MAX_BLOCKOFFSET bytes into the block if the block was to be
  * larger than this.
 */
 Assert(initBlockSize == MAXALIGN(initBlockSize) &&
     initBlockSize >= 1024);
 Assert(maxBlockSize == MAXALIGN(maxBlockSize) &&
     maxBlockSize >= initBlockSize &&
     AllocHugeSizeIsValid(maxBlockSize)); /* must be safe to double */
 Assert(minContextSize == 0 ||
     (minContextSize == MAXALIGN(minContextSize) &&
   minContextSize >= 1024 &&
   minContextSize <= maxBlockSize));
 Assert(maxBlockSize <= MEMORYCHUNK_MAX_BLOCKOFFSET);

 /* Determine size of initial block */
 allocSize = MAXALIGN(sizeof(GenerationContext)) +
  Generation_BLOCKHDRSZ + Generation_CHUNKHDRSZ;
 if (minContextSize != 0)
  allocSize = Max(allocSize, minContextSize);
 else
  allocSize = Max(allocSize, initBlockSize);

 /*
  * Allocate the initial block.  Unlike other generation.c blocks, it
  * starts with the context header and its block header follows that.
 */
 set = (GenerationContext *) malloc(allocSize);
 if (set == NULL)
 {
  MemoryContextStats(TopMemoryContext);
  ereport(ERROR,
    (errcode(ERRCODE_OUT_OF_MEMORY),
     errmsg("out of memory"),
     errdetail("Failed while creating memory context \"%s\".",
         name)));
 }

 /*
  * Avoid writing code that can fail between here and MemoryContextCreate;
  * we'd leak the header if we ereport in this stretch.
 */
 dlist_init(&set->blocks);

 /* Fill in the initial block's block header */
 block = KeeperBlock(set);
 /* determine the block size and initialize it */
 firstBlockSize = allocSize - MAXALIGN(sizeof(GenerationContext));
 GenerationBlockInit(set, block, firstBlockSize);

 /* add it to the doubly-linked list of blocks */
 dlist_push_head(&set->blocks, &block->node);

 /* use it as the current allocation block */
 set->block = block;

 /* No free block, yet */
 set->freeblock = NULL;

 /* Fill in GenerationContext-specific header fields */
 set->initBlockSize = (uint32) initBlockSize;
 set->maxBlockSize = (uint32) maxBlockSize;
 set->nextBlockSize = (uint32) initBlockSize;

 /*
  * Compute the allocation chunk size limit for this context.
  *
  * Limit the maximum size a non-dedicated chunk can be so that we can fit
  * at least Generation_CHUNK_FRACTION of chunks this big onto the maximum
  * sized block.  We must further limit this value so that it's no more
  * than MEMORYCHUNK_MAX_VALUE.  We're unable to have non-external chunks
  * larger than that value as we store the chunk size in the MemoryChunk
  * 'value' field in the call to MemoryChunkSetHdrMask().
 */
 set->allocChunkLimit = Min(maxBlockSize, MEMORYCHUNK_MAX_VALUE);
 while ((Size) (set->allocChunkLimit + Generation_CHUNKHDRSZ) >
     (Size) ((Size) (maxBlockSize - Generation_BLOCKHDRSZ) / Generation_CHUNK_FRACTION))
  set->allocChunkLimit >>= 1;

 /* Finally, do the type-independent part of context creation */
 MemoryContextCreate((MemoryContext) set,
      T_GenerationContext,
      MCTX_GENERATION_ID,
      parent,
      name);

 ((MemoryContext) set)->mem_allocated = firstBlockSize;

 return (MemoryContext) set;
}

/*
 * GenerationReset
 *  Frees all memory which is allocated in the given set.
 *
 * The initial "keeper" block (which shares a malloc chunk with the context
 * header) is not given back to the operating system though.  In this way, we
 * don't thrash malloc() when a context is repeatedly reset after small
 * allocations.
 */
void
GenerationReset(MemoryContext context)
{
 GenerationContext *set = (GenerationContext *) context;
 dlist_mutable_iter miter;

 Assert(GenerationIsValid(set));

#ifdef MEMORY_CONTEXT_CHECKING
 /* Check for corruption and leaks before freeing */
 GenerationCheck(context);
#endif

 /*
  * NULLify the free block pointer.  We must do this before calling
  * GenerationBlockFree as that function never expects to free the
  * freeblock.
 */
 set->freeblock = NULL;

 dlist_foreach_modify(miter, &set->blocks)
 {
  GenerationBlock *block = dlist_container(GenerationBlock, node, miter.cur);

  if (IsKeeperBlock(set, block))
   GenerationBlockMarkEmpty(block);
  else
   GenerationBlockFree(set, block);
 }

 /* set it so new allocations to make use of the keeper block */
 set->block = KeeperBlock(set);

 /* Reset block size allocation sequence, too */
 set->nextBlockSize = set->initBlockSize;

 /* Ensure there is only 1 item in the dlist */
 Assert(!dlist_is_empty(&set->blocks));
 Assert(!dlist_has_next(&set->blocks, dlist_head_node(&set->blocks)));
}

/*
 * GenerationDelete
 *  Free all memory which is allocated in the given context.
 */
void
GenerationDelete(MemoryContext context)
{
 /* Reset to release all releasable GenerationBlocks */
 GenerationReset(context);
 /* And free the context header and keeper block */
 free(context);
}

/*
 * Helper for GenerationAlloc() that allocates an entire block for the chunk.
 *
 * GenerationAlloc()'s comment explains why this is separate.
 */
pg_noinline
static void *
GenerationAllocLarge(MemoryContext context, Size size, int flags)
{
 GenerationContext *set = (GenerationContext *) context;
 GenerationBlock *block;
 MemoryChunk *chunk;
 Size  chunk_size;
 Size  required_size;
 Size  blksize;

 /* validate 'size' is within the limits for the given 'flags' */
 MemoryContextCheckSize(context, size, flags);

#ifdef MEMORY_CONTEXT_CHECKING
 /* ensure there's always space for the sentinel byte */
 chunk_size = MAXALIGN(size + 1);
#else
 chunk_size = MAXALIGN(size);
#endif
 required_size = chunk_size + Generation_CHUNKHDRSZ;
 blksize = required_size + Generation_BLOCKHDRSZ;

 block = (GenerationBlock *) malloc(blksize);
 if (block == NULL)
  return MemoryContextAllocationFailure(context, size, flags);

 context->mem_allocated += blksize;

 /* block with a single (used) chunk */
 block->context = set;
 block->blksize = blksize;
 block->nchunks = 1;
 block->nfree = 0;

 /* the block is completely full */
 block->freeptr = block->endptr = ((char *) block) + blksize;

 chunk = (MemoryChunk *) (((char *) block) + Generation_BLOCKHDRSZ);

 /* mark the MemoryChunk as externally managed */
 MemoryChunkSetHdrMaskExternal(chunk, MCTX_GENERATION_ID);

#ifdef MEMORY_CONTEXT_CHECKING
 chunk->requested_size = size;
 /* set mark to catch clobber of "unused" space */
 Assert(size < chunk_size);
 set_sentinel(MemoryChunkGetPointer(chunk), size);
#endif
#ifdef RANDOMIZE_ALLOCATED_MEMORY
 /* fill the allocated space with junk */
 randomize_mem((char *) MemoryChunkGetPointer(chunk), size);
#endif

 /* add the block to the list of allocated blocks */
 dlist_push_head(&set->blocks, &block->node);

 /* Ensure any padding bytes are marked NOACCESS. */
 VALGRIND_MAKE_MEM_NOACCESS((char *) MemoryChunkGetPointer(chunk) + size,
          chunk_size - size);

 /* Disallow access to the chunk header. */
 VALGRIND_MAKE_MEM_NOACCESS(chunk, Generation_CHUNKHDRSZ);

 return MemoryChunkGetPointer(chunk);
}

/*
 * Small helper for allocating a new chunk from a chunk, to avoid duplicating
 * the code between GenerationAlloc() and GenerationAllocFromNewBlock().
 */
static inline void *
GenerationAllocChunkFromBlock(MemoryContext context, GenerationBlock *block,
         Size size, Size chunk_size)
{
 MemoryChunk *chunk = (MemoryChunk *) (block->freeptr);

 /* validate we've been given a block with enough free space */
 Assert(block != NULL);
 Assert((block->endptr - block->freeptr) >=
     Generation_CHUNKHDRSZ + chunk_size);

 /* Prepare to initialize the chunk header. */
 VALGRIND_MAKE_MEM_UNDEFINED(chunk, Generation_CHUNKHDRSZ);

 block->nchunks += 1;
 block->freeptr += (Generation_CHUNKHDRSZ + chunk_size);

 Assert(block->freeptr <= block->endptr);

 MemoryChunkSetHdrMask(chunk, block, chunk_size, MCTX_GENERATION_ID);
#ifdef MEMORY_CONTEXT_CHECKING
 chunk->requested_size = size;
 /* set mark to catch clobber of "unused" space */
 Assert(size < chunk_size);
 set_sentinel(MemoryChunkGetPointer(chunk), size);
#endif
#ifdef RANDOMIZE_ALLOCATED_MEMORY
 /* fill the allocated space with junk */
 randomize_mem((char *) MemoryChunkGetPointer(chunk), size);
#endif

 /* Ensure any padding bytes are marked NOACCESS. */
 VALGRIND_MAKE_MEM_NOACCESS((char *) MemoryChunkGetPointer(chunk) + size,
          chunk_size - size);

 /* Disallow access to the chunk header. */
 VALGRIND_MAKE_MEM_NOACCESS(chunk, Generation_CHUNKHDRSZ);

 return MemoryChunkGetPointer(chunk);
}

/*
 * Helper for GenerationAlloc() that allocates a new block and returns a chunk
 * allocated from it.
 *
 * GenerationAlloc()'s comment explains why this is separate.
 */
pg_noinline
static void *
GenerationAllocFromNewBlock(MemoryContext context, Size size, int flags,
       Size chunk_size)
{
 GenerationContext *set = (GenerationContext *) context;
 GenerationBlock *block;
 Size  blksize;
 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;

 /* we'll need space for the chunk, chunk hdr and block hdr */
 required_size = chunk_size + Generation_CHUNKHDRSZ + Generation_BLOCKHDRSZ;

 /* round the size up to the next power of 2 */
 if (blksize < required_size)
  blksize = pg_nextpower2_size_t(required_size);

 block = (GenerationBlock *) malloc(blksize);

 if (block == NULL)
  return MemoryContextAllocationFailure(context, size, flags);

 context->mem_allocated += blksize;

 /* initialize the new block */
 GenerationBlockInit(set, block, blksize);

 /* add it to the doubly-linked list of blocks */
 dlist_push_head(&set->blocks, &block->node);

 /* make this the current block */
 set->block = block;

 return GenerationAllocChunkFromBlock(context, block, size, chunk_size);
}

/*
 * GenerationAlloc
 *  Returns a pointer to allocated memory of given size or raises an ERROR
 *  on allocation failure, or returns NULL when flags contains
 *  MCXT_ALLOC_NO_OOM.
 *
 * No request may exceed:
 *  MAXALIGN_DOWN(SIZE_MAX) - Generation_BLOCKHDRSZ - Generation_CHUNKHDRSZ
 * All callers use a much-lower limit.
 *
 * Note: when using valgrind, it doesn't matter how the returned allocation
 * is marked, as mcxt.c will set it to UNDEFINED.  In some paths we will
 * return space that is marked NOACCESS - GenerationRealloc has to beware!
 *
 * This function should only contain the most common code paths.  Everything
 * else should be in pg_noinline helper functions, thus avoiding the overhead
 * of creating a stack frame for the common cases.  Allocating memory is often
 * a bottleneck in many workloads, so avoiding stack frame setup is
 * worthwhile.  Helper functions should always directly return the newly
 * allocated memory so that we can just return that address directly as a tail
 * call.
 */
void *
GenerationAlloc(MemoryContext context, Size size, int flags)
{
 GenerationContext *set = (GenerationContext *) context;
 GenerationBlock *block;
 Size  chunk_size;
 Size  required_size;

 Assert(GenerationIsValid(set));

#ifdef MEMORY_CONTEXT_CHECKING
 /* ensure there's always space for the sentinel byte */
 chunk_size = MAXALIGN(size + 1);
#else
 chunk_size = MAXALIGN(size);
#endif

 /*
  * If requested size exceeds maximum for chunks we hand the request off to
  * GenerationAllocLarge().
 */
 if (chunk_size > set->allocChunkLimit)
  return GenerationAllocLarge(context, size, flags);

 required_size = chunk_size + Generation_CHUNKHDRSZ;

 /*
  * Not an oversized chunk.  We try to first make use of the current block,
  * but if there's not enough space in it, instead of allocating a new
  * block, we look to see if the empty freeblock has enough space.  We
  * don't try reusing the keeper block.  If it's become empty we'll reuse
  * that again only if the context is reset.
  *
  * We only try reusing the freeblock if we've no space for this allocation
  * on the current block.  When a freeblock exists, we'll switch to it once
  * the first time we can't fit an allocation in the current block.  We
  * avoid ping-ponging between the two as we need to be careful not to
  * fragment differently sized consecutive allocations between several
  * blocks.  Going between the two could cause fragmentation for FIFO
  * workloads, which generation is meant to be good at.
 */
 block = set->block;

 if (unlikely(GenerationBlockFreeBytes(block) < required_size))
 {
  GenerationBlock *freeblock = set->freeblock;

  /* freeblock, if set, must be empty */
  Assert(freeblock == NULL || GenerationBlockIsEmpty(freeblock));

  /* check if we have a freeblock and if it's big enough */
  if (freeblock != NULL &&
   GenerationBlockFreeBytes(freeblock) >= required_size)
  {
   /* make the freeblock the current block */
   set->freeblock = NULL;
   set->block = freeblock;

   return GenerationAllocChunkFromBlock(context,
             freeblock,
             size,
             chunk_size);
  }
  else
  {
   /*
    * No freeblock, or it's not big enough for this allocation.  Make
    * a new block.
 */
   return GenerationAllocFromNewBlock(context, size, flags, chunk_size);
  }
 }

 /* The current block has space, so just allocate chunk there. */
 return GenerationAllocChunkFromBlock(context, block, size, chunk_size);
}

/*
 * GenerationBlockInit
 *  Initializes 'block' assuming 'blksize'.  Does not update the context's
 *  mem_allocated field.
 */
static inline void
GenerationBlockInit(GenerationContext *context, GenerationBlock *block,
     Size blksize)
{
 block->context = context;
 block->blksize = blksize;
 block->nchunks = 0;
 block->nfree = 0;

 block->freeptr = ((char *) block) + Generation_BLOCKHDRSZ;
 block->endptr = ((char *) block) + blksize;

 /* Mark unallocated space NOACCESS. */
 VALGRIND_MAKE_MEM_NOACCESS(block->freeptr,
          blksize - Generation_BLOCKHDRSZ);
}

/*
 * GenerationBlockMarkEmpty
 *  Set a block as empty.  Does not free the block.
 */
static inline void
GenerationBlockMarkEmpty(GenerationBlock *block)
{
#if defined(USE_VALGRIND) || defined(CLOBBER_FREED_MEMORY)
 char    *datastart = ((char *) block) + Generation_BLOCKHDRSZ;
#endif

#ifdef CLOBBER_FREED_MEMORY
 wipe_mem(datastart, block->freeptr - datastart);
#else
 /* wipe_mem() would have done this */
 VALGRIND_MAKE_MEM_NOACCESS(datastart, block->freeptr - datastart);
#endif

 /* Reset the block, but don't return it to malloc */
 block->nchunks = 0;
 block->nfree = 0;
 block->freeptr = ((char *) block) + Generation_BLOCKHDRSZ;
}

/*
 * GenerationBlockFreeBytes
 *  Returns the number of bytes free in 'block'
 */
static inline Size
GenerationBlockFreeBytes(GenerationBlock *block)
{
 return (block->endptr - block->freeptr);
}

/*
 * GenerationBlockFree
 *  Remove 'block' from 'set' and release the memory consumed by it.
 */
static inline void
GenerationBlockFree(GenerationContext *set, GenerationBlock *block)
{
 /* Make sure nobody tries to free the keeper block */
 Assert(!IsKeeperBlock(set, block));
 /* We shouldn't be freeing the freeblock either */
 Assert(block != set->freeblock);

 /* release the block from the list of blocks */
 dlist_delete(&block->node);

 ((MemoryContext) set)->mem_allocated -= block->blksize;

#ifdef CLOBBER_FREED_MEMORY
 wipe_mem(block, block->blksize);
#endif

 free(block);
}

/*
 * GenerationFree
 *  Update number of chunks in the block, and consider freeing the block
 *  if it's become empty.
 */
void
GenerationFree(void *pointer)
{
 MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
 GenerationBlock *block;
 GenerationContext *set;
#if (defined(MEMORY_CONTEXT_CHECKING) && defined(USE_ASSERT_CHECKING)) \
 || defined(CLOBBER_FREED_MEMORY)
 Size  chunksize;
#endif

 /* Allow access to the chunk header. */
 VALGRIND_MAKE_MEM_DEFINED(chunk, Generation_CHUNKHDRSZ);

 if (MemoryChunkIsExternal(chunk))
 {
  block = ExternalChunkGetBlock(chunk);

  /*
   * Try to verify that we have a sane block pointer: the block header
   * should reference a generation context.
 */
  if (!GenerationBlockIsValid(block))
   elog(ERROR, "could not find block containing chunk %p", chunk);

#if (defined(MEMORY_CONTEXT_CHECKING) && defined(USE_ASSERT_CHECKING)) \
 || defined(CLOBBER_FREED_MEMORY)
  chunksize = block->endptr - (char *) pointer;
#endif
 }
 else
 {
  block = MemoryChunkGetBlock(chunk);

  /*
   * In this path, for speed reasons we just Assert that the referenced
   * block is good.  Future field experience may show that this Assert
   * had better become a regular runtime test-and-elog check.
 */
  Assert(GenerationBlockIsValid(block));

#if (defined(MEMORY_CONTEXT_CHECKING) && defined(USE_ASSERT_CHECKING)) \
 || defined(CLOBBER_FREED_MEMORY)
  chunksize = MemoryChunkGetValue(chunk);
#endif
 }

#ifdef MEMORY_CONTEXT_CHECKING
 /* See comments in AllocSetFree about uses of ERROR and WARNING here */
 /* Test for previously-freed chunk */
 if (unlikely(chunk->requested_size == InvalidAllocSize))
  elog(ERROR, "detected double pfree in %s %p",
    ((MemoryContext) block->context)->name, chunk);
 /* Test for someone scribbling on unused space in chunk */
 Assert(chunk->requested_size < chunksize);
 if (!sentinel_ok(pointer, chunk->requested_size))
  elog(WARNING, "detected write past chunk end in %s %p",
    ((MemoryContext) block->context)->name, chunk);
#endif

#ifdef CLOBBER_FREED_MEMORY
 wipe_mem(pointer, chunksize);
#endif

#ifdef MEMORY_CONTEXT_CHECKING
 /* Reset requested_size to InvalidAllocSize in freed chunks */
 chunk->requested_size = InvalidAllocSize;
#endif

 block->nfree += 1;

 Assert(block->nchunks > 0);
 Assert(block->nfree <= block->nchunks);
 Assert(block != block->context->freeblock);

 /* If there are still allocated chunks in the block, we're done. */
 if (likely(block->nfree < block->nchunks))
  return;

 set = block->context;

 /*-----------------------
  * The block this allocation was on has now become completely empty of
  * chunks.  In the general case, we can now return the memory for this
  * block back to malloc.  However, there are cases where we don't want to
  * do that:
  *
  * 1) If it's the keeper block.  This block was malloc'd in the same
  *  allocation as the context itself and can't be free'd without
  *  freeing the context.
  * 2) If it's the current block.  We could free this, but doing so would
  *  leave us nothing to set the current block to, so we just mark the
  *  block as empty so new allocations can reuse it again.
  * 3) If we have no "freeblock" set, then we save a single block for
  *  future allocations to avoid having to malloc a new block again.
  *  This is useful for FIFO workloads as it avoids continual
  *  free/malloc cycles.
 */
 if (IsKeeperBlock(set, block) || set->block == block)
  GenerationBlockMarkEmpty(block); /* case 1 and 2 */
 else if (set->freeblock == NULL)
 {
  /* case 3 */
  GenerationBlockMarkEmpty(block);
  set->freeblock = block;
 }
 else
  GenerationBlockFree(set, block); /* Otherwise, free it */
}

/*
 * GenerationRealloc
 *  When handling repalloc, we simply allocate a new chunk, copy the data
 *  and discard the old one. The only exception is when the new size fits
 *  into the old chunk - in that case we just update chunk header.
 */
void *
GenerationRealloc(void *pointer, Size size, int flags)
{
 MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
 GenerationContext *set;
 GenerationBlock *block;
 GenerationPointer newPointer;
 Size  oldsize;

 /* Allow access to the chunk header. */
 VALGRIND_MAKE_MEM_DEFINED(chunk, Generation_CHUNKHDRSZ);

 if (MemoryChunkIsExternal(chunk))
 {
  block = ExternalChunkGetBlock(chunk);

  /*
   * Try to verify that we have a sane block pointer: the block header
   * should reference a generation context.
 */
  if (!GenerationBlockIsValid(block))
   elog(ERROR, "could not find block containing chunk %p", chunk);

  oldsize = block->endptr - (char *) pointer;
 }
 else
 {
  block = MemoryChunkGetBlock(chunk);

  /*
   * In this path, for speed reasons we just Assert that the referenced
   * block is good.  Future field experience may show that this Assert
   * had better become a regular runtime test-and-elog check.
 */
  Assert(GenerationBlockIsValid(block));

  oldsize = MemoryChunkGetValue(chunk);
 }

 set = block->context;

#ifdef MEMORY_CONTEXT_CHECKING
 /* See comments in AllocSetFree about uses of ERROR and WARNING here */
 /* Test for previously-freed chunk */
 if (unlikely(chunk->requested_size == InvalidAllocSize))
  elog(ERROR, "detected realloc of freed chunk in %s %p",
    ((MemoryContext) set)->name, chunk);
 /* Test for someone scribbling on unused space in chunk */
 Assert(chunk->requested_size < oldsize);
 if (!sentinel_ok(pointer, chunk->requested_size))
  elog(WARNING, "detected write past chunk end in %s %p",
    ((MemoryContext) set)->name, chunk);
#endif

 /*
  * Maybe the allocated area already big enough.  (In particular, we always
  * fall out here if the requested size is a decrease.)
  *
  * This memory context does not use power-of-2 chunk sizing and instead
  * carves the chunks to be as small as possible, so most repalloc() calls
  * will end up in the palloc/memcpy/pfree branch.
  *
  * XXX Perhaps we should annotate this condition with unlikely()?
 */
#ifdef MEMORY_CONTEXT_CHECKING
 /* With MEMORY_CONTEXT_CHECKING, we need an extra byte for the sentinel */
 if (oldsize > size)
#else
 if (oldsize >= size)
#endif
 {
#ifdef MEMORY_CONTEXT_CHECKING
  Size  oldrequest = chunk->requested_size;

#ifdef RANDOMIZE_ALLOCATED_MEMORY
  /* We can only fill the extra space if we know the prior request */
  if (size > oldrequest)
   randomize_mem((char *) pointer + oldrequest,
        size - oldrequest);
#endif

  chunk->requested_size = size;

  /*
   * If this is an increase, mark any newly-available part UNDEFINED.
   * Otherwise, mark the obsolete part NOACCESS.
 */
  if (size > oldrequest)
   VALGRIND_MAKE_MEM_UNDEFINED((char *) pointer + oldrequest,
          size - oldrequest);
  else
   VALGRIND_MAKE_MEM_NOACCESS((char *) pointer + size,
            oldsize - size);

  /* set mark to catch clobber of "unused" space */
  set_sentinel(pointer, size);
#else       /* !MEMORY_CONTEXT_CHECKING */

  /*
   * We don't have the information to determine whether we're growing
   * the old request or shrinking it, so we conservatively mark the
   * entire new allocation DEFINED.
 */
  VALGRIND_MAKE_MEM_NOACCESS(pointer, oldsize);
  VALGRIND_MAKE_MEM_DEFINED(pointer, size);
#endif

  /* Disallow access to the chunk header. */
  VALGRIND_MAKE_MEM_NOACCESS(chunk, Generation_CHUNKHDRSZ);

  return pointer;
 }

 /* allocate new chunk (this also checks size is valid) */
 newPointer = GenerationAlloc((MemoryContext) set, size, flags);

 /* leave immediately if request was not completed */
 if (newPointer == NULL)
 {
  /* Disallow access to the chunk header. */
  VALGRIND_MAKE_MEM_NOACCESS(chunk, Generation_CHUNKHDRSZ);
  return MemoryContextAllocationFailure((MemoryContext) set, size, flags);
 }

 /*
  * GenerationAlloc() may have returned a region that is still NOACCESS.
  * Change it to UNDEFINED for the moment; memcpy() will then transfer
  * definedness from the old allocation to the new.  If we know the old
  * allocation, copy just that much.  Otherwise, make the entire old chunk
  * defined to avoid errors as we copy the currently-NOACCESS trailing
  * bytes.
 */
 VALGRIND_MAKE_MEM_UNDEFINED(newPointer, size);
#ifdef MEMORY_CONTEXT_CHECKING
 oldsize = chunk->requested_size;
#else
 VALGRIND_MAKE_MEM_DEFINED(pointer, oldsize);
#endif

 /* transfer existing data (certain to fit) */
 memcpy(newPointer, pointer, oldsize);

 /* free old chunk */
 GenerationFree(pointer);

 return newPointer;
}

/*
 * GenerationGetChunkContext
 *  Return the MemoryContext that 'pointer' belongs to.
 */
MemoryContext
GenerationGetChunkContext(void *pointer)
{
 MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
 GenerationBlock *block;

 /* Allow access to the chunk header. */
 VALGRIND_MAKE_MEM_DEFINED(chunk, Generation_CHUNKHDRSZ);

 if (MemoryChunkIsExternal(chunk))
  block = ExternalChunkGetBlock(chunk);
 else
  block = (GenerationBlock *) MemoryChunkGetBlock(chunk);

 /* Disallow access to the chunk header. */
 VALGRIND_MAKE_MEM_NOACCESS(chunk, Generation_CHUNKHDRSZ);

 Assert(GenerationBlockIsValid(block));
 return &block->context->header;
}

/*
 * GenerationGetChunkSpace
 *  Given a currently-allocated chunk, determine the total space
 *  it occupies (including all memory-allocation overhead).
 */
Size
GenerationGetChunkSpace(void *pointer)
{
 MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
 Size  chunksize;

 /* Allow access to the chunk header. */
 VALGRIND_MAKE_MEM_DEFINED(chunk, Generation_CHUNKHDRSZ);

 if (MemoryChunkIsExternal(chunk))
 {
  GenerationBlock *block = ExternalChunkGetBlock(chunk);

  Assert(GenerationBlockIsValid(block));
  chunksize = block->endptr - (char *) pointer;
 }
 else
  chunksize = MemoryChunkGetValue(chunk);

 /* Disallow access to the chunk header. */
 VALGRIND_MAKE_MEM_NOACCESS(chunk, Generation_CHUNKHDRSZ);

 return Generation_CHUNKHDRSZ + chunksize;
}

/*
 * GenerationIsEmpty
 *  Is a GenerationContext empty of any allocated space?
 */
bool
GenerationIsEmpty(MemoryContext context)
{
 GenerationContext *set = (GenerationContext *) context;
 dlist_iter iter;

 Assert(GenerationIsValid(set));

 dlist_foreach(iter, &set->blocks)
 {
  GenerationBlock *block = dlist_container(GenerationBlock, node, iter.cur);

  if (block->nchunks > 0)
   return false;
 }

 return true;
}

/*
 * GenerationStats
 *  Compute stats about memory consumption of a Generation context.
 *
 * printfunc: if not NULL, pass a human-readable stats string to this.
 * passthru: pass this pointer through to printfunc.
 * totals: if not NULL, add stats about this context into *totals.
 * print_to_stderr: print stats to stderr if true, elog otherwise.
 *
 * XXX freespace only accounts for empty space at the end of the block, not
 * space of freed chunks (which is unknown).
 */
void
GenerationStats(MemoryContext context,
    MemoryStatsPrintFunc printfunc, void *passthru,
    MemoryContextCounters *totals, bool print_to_stderr)
{
 GenerationContext *set = (GenerationContext *) context;
 Size  nblocks = 0;
 Size  nchunks = 0;
 Size  nfreechunks = 0;
 Size  totalspace;
 Size  freespace = 0;
 dlist_iter iter;

 Assert(GenerationIsValid(set));

 /* Include context header in totalspace */
 totalspace = MAXALIGN(sizeof(GenerationContext));

 dlist_foreach(iter, &set->blocks)
 {
  GenerationBlock *block = dlist_container(GenerationBlock, node, iter.cur);

  nblocks++;
  nchunks += block->nchunks;
  nfreechunks += block->nfree;
  totalspace += block->blksize;
  freespace += (block->endptr - block->freeptr);
 }

 if (printfunc)
 {
  char  stats_string[200];

  snprintf(stats_string, sizeof(stats_string),
     "%zu total in %zu blocks (%zu chunks); %zu free (%zu chunks); %zu used",
     totalspace, nblocks, nchunks, freespace,
     nfreechunks, totalspace - freespace);
  printfunc(context, passthru, stats_string, print_to_stderr);
 }

 if (totals)
 {
  totals->nblocks += nblocks;
  totals->freechunks += nfreechunks;
  totals->totalspace += totalspace;
  totals->freespace += freespace;
 }
}


#ifdef MEMORY_CONTEXT_CHECKING

/*
 * GenerationCheck
 *  Walk through chunks and check consistency of memory.
 *
 * NOTE: report errors as WARNING, *not* ERROR or FATAL.  Otherwise you'll
 * find yourself in an infinite loop when trouble occurs, because this
 * routine will be entered again when elog cleanup tries to release memory!
 */
void
GenerationCheck(MemoryContext context)
{
 GenerationContext *gen = (GenerationContext *) context;
 const char *name = context->name;
 dlist_iter iter;
 Size  total_allocated = 0;

 /* walk all blocks in this context */
 dlist_foreach(iter, &gen->blocks)
 {
  GenerationBlock *block = dlist_container(GenerationBlock, node, iter.cur);
  int   nfree,
     nchunks;
  char    *ptr;
  bool  has_external_chunk = false;

  total_allocated += block->blksize;

  /*
   * nfree > nchunks is surely wrong.  Equality is allowed as the block
   * might completely empty if it's the freeblock.
 */
  if (block->nfree > block->nchunks)
   elog(WARNING, "problem in Generation %s: number of free chunks %d in block %p exceeds %d allocated",
     name, block->nfree, block, block->nchunks);

  /* check block belongs to the correct context */
  if (block->context != gen)
   elog(WARNING, "problem in Generation %s: bogus context link in block %p",
     name, block);

  /* Now walk through the chunks and count them. */
  nfree = 0;
  nchunks = 0;
  ptr = ((char *) block) + Generation_BLOCKHDRSZ;

  while (ptr < block->freeptr)
  {
   MemoryChunk *chunk = (MemoryChunk *) ptr;
   GenerationBlock *chunkblock;
   Size  chunksize;

   /* Allow access to the chunk header. */
   VALGRIND_MAKE_MEM_DEFINED(chunk, Generation_CHUNKHDRSZ);

   if (MemoryChunkIsExternal(chunk))
   {
    chunkblock = ExternalChunkGetBlock(chunk);
    chunksize = block->endptr - (char *) MemoryChunkGetPointer(chunk);
    has_external_chunk = true;
   }
   else
   {
    chunkblock = MemoryChunkGetBlock(chunk);
    chunksize = MemoryChunkGetValue(chunk);
   }

   /* move to the next chunk */
   ptr += (chunksize + Generation_CHUNKHDRSZ);

   nchunks += 1;

   /* chunks have both block and context pointers, so check both */
   if (chunkblock != block)
    elog(WARNING, "problem in Generation %s: bogus block link in block %p, chunk %p",
      name, block, chunk);


   /* is chunk allocated? */
   if (chunk->requested_size != InvalidAllocSize)
   {
    /* now make sure the chunk size is correct */
    if (chunksize < chunk->requested_size ||
     chunksize != MAXALIGN(chunksize))
     elog(WARNING, "problem in Generation %s: bogus chunk size in block %p, chunk %p",
       name, block, chunk);

    /* check sentinel */
    Assert(chunk->requested_size < chunksize);
    if (!sentinel_ok(chunk, Generation_CHUNKHDRSZ + chunk->requested_size))
     elog(WARNING, "problem in Generation %s: detected write past chunk end in block %p, chunk %p",
       name, block, chunk);
   }
   else
    nfree += 1;

   /* if chunk is allocated, disallow access to the chunk header */
   if (chunk->requested_size != InvalidAllocSize)
    VALGRIND_MAKE_MEM_NOACCESS(chunk, Generation_CHUNKHDRSZ);
  }

  /*
   * Make sure we got the expected number of allocated and free chunks
   * (as tracked in the block header).
 */
  if (nchunks != block->nchunks)
   elog(WARNING, "problem in Generation %s: number of allocated chunks %d in block %p does not match header %d",
     name, nchunks, block, block->nchunks);

  if (nfree != block->nfree)
   elog(WARNING, "problem in Generation %s: number of free chunks %d in block %p does not match header %d",
     name, nfree, block, block->nfree);

  if (has_external_chunk && nchunks > 1)
   elog(WARNING, "problem in Generation %s: external chunk on non-dedicated block %p",
     name, block);

 }

 Assert(total_allocated == context->mem_allocated);
}

#endif       /* MEMORY_CONTEXT_CHECKING */