PostgreSQL Source Code  git master
generation.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * generation.c
4  * Generational allocator definitions.
5  *
6  * Generation is a custom MemoryContext implementation designed for cases of
7  * chunks with similar lifespan.
8  *
9  * Portions Copyright (c) 2017-2024, PostgreSQL Global Development Group
10  *
11  * IDENTIFICATION
12  * src/backend/utils/mmgr/generation.c
13  *
14  *
15  * This memory context is based on the assumption that the chunks are freed
16  * roughly in the same order as they were allocated (FIFO), or in groups with
17  * similar lifespan (generations - hence the name of the context). This is
18  * typical for various queue-like use cases, i.e. when tuples are constructed,
19  * processed and then thrown away.
20  *
21  * The memory context uses a very simple approach to free space management.
22  * Instead of a complex global freelist, each block tracks a number
23  * of allocated and freed chunks. The block is classed as empty when the
24  * number of free chunks is equal to the number of allocated chunks. When
25  * this occurs, instead of freeing the block, we try to "recycle" it, i.e.
26  * reuse it for new allocations. This is done by setting the block in the
27  * context's 'freeblock' field. If the freeblock field is already occupied
28  * by another free block we simply return the newly empty block to malloc.
29  *
30  * This approach to free blocks requires fewer malloc/free calls for truly
31  * first allocated, first free'd allocation patterns.
32  *
33  *-------------------------------------------------------------------------
34  */
35 
36 #include "postgres.h"
37 
38 #include "lib/ilist.h"
39 #include "port/pg_bitutils.h"
40 #include "utils/memdebug.h"
41 #include "utils/memutils.h"
44 
45 
46 #define Generation_BLOCKHDRSZ MAXALIGN(sizeof(GenerationBlock))
47 #define Generation_CHUNKHDRSZ sizeof(MemoryChunk)
48 
49 #define Generation_CHUNK_FRACTION 8
50 
51 typedef struct GenerationBlock GenerationBlock; /* forward reference */
52 
53 typedef void *GenerationPointer;
54 
55 /*
56  * GenerationContext is a simple memory context not reusing allocated chunks,
57  * and freeing blocks once all chunks are freed.
58  */
59 typedef struct GenerationContext
60 {
61  MemoryContextData header; /* Standard memory-context fields */
62 
63  /* Generational context parameters */
64  uint32 initBlockSize; /* initial block size */
65  uint32 maxBlockSize; /* maximum block size */
66  uint32 nextBlockSize; /* next block size to allocate */
67  uint32 allocChunkLimit; /* effective chunk size limit */
68 
69  GenerationBlock *block; /* current (most recently allocated) block */
70  GenerationBlock *freeblock; /* pointer to an empty block that's being
71  * recycled, or NULL if there's no such block. */
72  dlist_head blocks; /* list of blocks */
74 
75 /*
76  * GenerationBlock
77  * GenerationBlock is the unit of memory that is obtained by generation.c
78  * from malloc(). It contains zero or more MemoryChunks, which are the
79  * units requested by palloc() and freed by pfree(). MemoryChunks cannot
80  * be returned to malloc() individually, instead pfree() updates the free
81  * counter of the block and when all chunks in a block are free the whole
82  * block can be returned to malloc().
83  *
84  * GenerationBlock is the header data for a block --- the usable space
85  * within the block begins at the next alignment boundary.
86  */
88 {
89  dlist_node node; /* doubly-linked list of blocks */
90  GenerationContext *context; /* pointer back to the owning context */
91  Size blksize; /* allocated size of this block */
92  int nchunks; /* number of chunks in the block */
93  int nfree; /* number of free chunks */
94  char *freeptr; /* start of free space in this block */
95  char *endptr; /* end of space in this block */
96 };
97 
98 /*
99  * GenerationIsValid
100  * True iff set is valid generation set.
101  */
102 #define GenerationIsValid(set) \
103  (PointerIsValid(set) && IsA(set, GenerationContext))
104 
105 /*
106  * GenerationBlockIsValid
107  * True iff block is valid block of generation set.
108  */
109 #define GenerationBlockIsValid(block) \
110  (PointerIsValid(block) && GenerationIsValid((block)->context))
111 
112 /*
113  * GenerationBlockIsEmpty
114  * True iff block contains no chunks
115  */
116 #define GenerationBlockIsEmpty(b) ((b)->nchunks == 0)
117 
118 /*
119  * We always store external chunks on a dedicated block. This makes fetching
120  * the block from an external chunk easy since it's always the first and only
121  * chunk on the block.
122  */
123 #define ExternalChunkGetBlock(chunk) \
124  (GenerationBlock *) ((char *) chunk - Generation_BLOCKHDRSZ)
125 
126 /* Obtain the keeper block for a generation context */
127 #define KeeperBlock(set) \
128  ((GenerationBlock *) (((char *) set) + \
129  MAXALIGN(sizeof(GenerationContext))))
130 
131 /* Check if the block is the keeper block of the given generation context */
132 #define IsKeeperBlock(set, block) ((block) == (KeeperBlock(set)))
133 
134 /* Inlined helper functions */
135 static inline void GenerationBlockInit(GenerationContext *context,
136  GenerationBlock *block,
137  Size blksize);
138 static inline void GenerationBlockMarkEmpty(GenerationBlock *block);
139 static inline Size GenerationBlockFreeBytes(GenerationBlock *block);
140 static inline void GenerationBlockFree(GenerationContext *set,
141  GenerationBlock *block);
142 
143 
144 /*
145  * Public routines
146  */
147 
148 
149 /*
150  * GenerationContextCreate
151  * Create a new Generation context.
152  *
153  * parent: parent context, or NULL if top-level context
154  * name: name of context (must be statically allocated)
155  * minContextSize: minimum context size
156  * initBlockSize: initial allocation block size
157  * maxBlockSize: maximum allocation block size
158  */
161  const char *name,
162  Size minContextSize,
163  Size initBlockSize,
164  Size maxBlockSize)
165 {
166  Size firstBlockSize;
167  Size allocSize;
168  GenerationContext *set;
169  GenerationBlock *block;
170 
171  /* ensure MemoryChunk's size is properly maxaligned */
173  "sizeof(MemoryChunk) is not maxaligned");
174 
175  /*
176  * First, validate allocation parameters. Asserts seem sufficient because
177  * nobody varies their parameters at runtime. We somewhat arbitrarily
178  * enforce a minimum 1K block size. We restrict the maximum block size to
179  * MEMORYCHUNK_MAX_BLOCKOFFSET as MemoryChunks are limited to this in
180  * regards to addressing the offset between the chunk and the block that
181  * the chunk is stored on. We would be unable to store the offset between
182  * the chunk and block for any chunks that were beyond
183  * MEMORYCHUNK_MAX_BLOCKOFFSET bytes into the block if the block was to be
184  * larger than this.
185  */
186  Assert(initBlockSize == MAXALIGN(initBlockSize) &&
187  initBlockSize >= 1024);
188  Assert(maxBlockSize == MAXALIGN(maxBlockSize) &&
189  maxBlockSize >= initBlockSize &&
190  AllocHugeSizeIsValid(maxBlockSize)); /* must be safe to double */
191  Assert(minContextSize == 0 ||
192  (minContextSize == MAXALIGN(minContextSize) &&
193  minContextSize >= 1024 &&
194  minContextSize <= maxBlockSize));
195  Assert(maxBlockSize <= MEMORYCHUNK_MAX_BLOCKOFFSET);
196 
197  /* Determine size of initial block */
198  allocSize = MAXALIGN(sizeof(GenerationContext)) +
200  if (minContextSize != 0)
201  allocSize = Max(allocSize, minContextSize);
202  else
203  allocSize = Max(allocSize, initBlockSize);
204 
205  /*
206  * Allocate the initial block. Unlike other generation.c blocks, it
207  * starts with the context header and its block header follows that.
208  */
209  set = (GenerationContext *) malloc(allocSize);
210  if (set == NULL)
211  {
213  ereport(ERROR,
214  (errcode(ERRCODE_OUT_OF_MEMORY),
215  errmsg("out of memory"),
216  errdetail("Failed while creating memory context \"%s\".",
217  name)));
218  }
219 
220  /*
221  * Avoid writing code that can fail between here and MemoryContextCreate;
222  * we'd leak the header if we ereport in this stretch.
223  */
224  dlist_init(&set->blocks);
225 
226  /* Fill in the initial block's block header */
227  block = KeeperBlock(set);
228  /* determine the block size and initialize it */
229  firstBlockSize = allocSize - MAXALIGN(sizeof(GenerationContext));
230  GenerationBlockInit(set, block, firstBlockSize);
231 
232  /* add it to the doubly-linked list of blocks */
233  dlist_push_head(&set->blocks, &block->node);
234 
235  /* use it as the current allocation block */
236  set->block = block;
237 
238  /* No free block, yet */
239  set->freeblock = NULL;
240 
241  /* Fill in GenerationContext-specific header fields */
242  set->initBlockSize = (uint32) initBlockSize;
243  set->maxBlockSize = (uint32) maxBlockSize;
244  set->nextBlockSize = (uint32) initBlockSize;
245 
246  /*
247  * Compute the allocation chunk size limit for this context.
248  *
249  * Limit the maximum size a non-dedicated chunk can be so that we can fit
250  * at least Generation_CHUNK_FRACTION of chunks this big onto the maximum
251  * sized block. We must further limit this value so that it's no more
252  * than MEMORYCHUNK_MAX_VALUE. We're unable to have non-external chunks
253  * larger than that value as we store the chunk size in the MemoryChunk
254  * 'value' field in the call to MemoryChunkSetHdrMask().
255  */
256  set->allocChunkLimit = Min(maxBlockSize, MEMORYCHUNK_MAX_VALUE);
257  while ((Size) (set->allocChunkLimit + Generation_CHUNKHDRSZ) >
258  (Size) ((Size) (maxBlockSize - Generation_BLOCKHDRSZ) / Generation_CHUNK_FRACTION))
259  set->allocChunkLimit >>= 1;
260 
261  /* Finally, do the type-independent part of context creation */
263  T_GenerationContext,
265  parent,
266  name);
267 
268  ((MemoryContext) set)->mem_allocated = firstBlockSize;
269 
270  return (MemoryContext) set;
271 }
272 
273 /*
274  * GenerationReset
275  * Frees all memory which is allocated in the given set.
276  *
277  * The initial "keeper" block (which shares a malloc chunk with the context
278  * header) is not given back to the operating system though. In this way, we
279  * don't thrash malloc() when a context is repeatedly reset after small
280  * allocations.
281  */
282 void
284 {
286  dlist_mutable_iter miter;
287 
289 
290 #ifdef MEMORY_CONTEXT_CHECKING
291  /* Check for corruption and leaks before freeing */
292  GenerationCheck(context);
293 #endif
294 
295  /*
296  * NULLify the free block pointer. We must do this before calling
297  * GenerationBlockFree as that function never expects to free the
298  * freeblock.
299  */
300  set->freeblock = NULL;
301 
302  dlist_foreach_modify(miter, &set->blocks)
303  {
304  GenerationBlock *block = dlist_container(GenerationBlock, node, miter.cur);
305 
306  if (IsKeeperBlock(set, block))
308  else
309  GenerationBlockFree(set, block);
310  }
311 
312  /* set it so new allocations to make use of the keeper block */
313  set->block = KeeperBlock(set);
314 
315  /* Reset block size allocation sequence, too */
316  set->nextBlockSize = set->initBlockSize;
317 
318  /* Ensure there is only 1 item in the dlist */
319  Assert(!dlist_is_empty(&set->blocks));
321 }
322 
323 /*
324  * GenerationDelete
325  * Free all memory which is allocated in the given context.
326  */
327 void
329 {
330  /* Reset to release all releasable GenerationBlocks */
332  /* And free the context header and keeper block */
333  free(context);
334 }
335 
336 /*
337  * Helper for GenerationAlloc() that allocates an entire block for the chunk.
338  *
339  * GenerationAlloc()'s comment explains why this is separate.
340  */
342 static void *
344 {
346  GenerationBlock *block;
347  MemoryChunk *chunk;
348  Size chunk_size;
349  Size required_size;
350  Size blksize;
351 
352  /* validate 'size' is within the limits for the given 'flags' */
354 
355 #ifdef MEMORY_CONTEXT_CHECKING
356  /* ensure there's always space for the sentinel byte */
357  chunk_size = MAXALIGN(size + 1);
358 #else
359  chunk_size = MAXALIGN(size);
360 #endif
361  required_size = chunk_size + Generation_CHUNKHDRSZ;
362  blksize = required_size + Generation_BLOCKHDRSZ;
363 
364  block = (GenerationBlock *) malloc(blksize);
365  if (block == NULL)
367 
368  context->mem_allocated += blksize;
369 
370  /* block with a single (used) chunk */
371  block->context = set;
372  block->blksize = blksize;
373  block->nchunks = 1;
374  block->nfree = 0;
375 
376  /* the block is completely full */
377  block->freeptr = block->endptr = ((char *) block) + blksize;
378 
379  chunk = (MemoryChunk *) (((char *) block) + Generation_BLOCKHDRSZ);
380 
381  /* mark the MemoryChunk as externally managed */
383 
384 #ifdef MEMORY_CONTEXT_CHECKING
385  chunk->requested_size = size;
386  /* set mark to catch clobber of "unused" space */
387  Assert(size < chunk_size);
388  set_sentinel(MemoryChunkGetPointer(chunk), size);
389 #endif
390 #ifdef RANDOMIZE_ALLOCATED_MEMORY
391  /* fill the allocated space with junk */
392  randomize_mem((char *) MemoryChunkGetPointer(chunk), size);
393 #endif
394 
395  /* add the block to the list of allocated blocks */
396  dlist_push_head(&set->blocks, &block->node);
397 
398  /* Ensure any padding bytes are marked NOACCESS. */
400  chunk_size - size);
401 
402  /* Disallow access to the chunk header. */
404 
405  return MemoryChunkGetPointer(chunk);
406 }
407 
408 /*
409  * Small helper for allocating a new chunk from a chunk, to avoid duplicating
410  * the code between GenerationAlloc() and GenerationAllocFromNewBlock().
411  */
412 static inline void *
414  Size size, Size chunk_size)
415 {
416  MemoryChunk *chunk = (MemoryChunk *) (block->freeptr);
417 
418  /* validate we've been given a block with enough free space */
419  Assert(block != NULL);
420  Assert((block->endptr - block->freeptr) >=
421  Generation_CHUNKHDRSZ + chunk_size);
422 
423  /* Prepare to initialize the chunk header. */
425 
426  block->nchunks += 1;
427  block->freeptr += (Generation_CHUNKHDRSZ + chunk_size);
428 
429  Assert(block->freeptr <= block->endptr);
430 
431  MemoryChunkSetHdrMask(chunk, block, chunk_size, MCTX_GENERATION_ID);
432 #ifdef MEMORY_CONTEXT_CHECKING
433  chunk->requested_size = size;
434  /* set mark to catch clobber of "unused" space */
435  Assert(size < chunk_size);
436  set_sentinel(MemoryChunkGetPointer(chunk), size);
437 #endif
438 #ifdef RANDOMIZE_ALLOCATED_MEMORY
439  /* fill the allocated space with junk */
440  randomize_mem((char *) MemoryChunkGetPointer(chunk), size);
441 #endif
442 
443  /* Ensure any padding bytes are marked NOACCESS. */
445  chunk_size - size);
446 
447  /* Disallow access to the chunk header. */
449 
450  return MemoryChunkGetPointer(chunk);
451 }
452 
453 /*
454  * Helper for GenerationAlloc() that allocates a new block and returns a chunk
455  * allocated from it.
456  *
457  * GenerationAlloc()'s comment explains why this is separate.
458  */
460 static void *
462  Size chunk_size)
463 {
465  GenerationBlock *block;
466  Size blksize;
467  Size required_size;
468 
469  /*
470  * The first such block has size initBlockSize, and we double the space in
471  * each succeeding block, but not more than maxBlockSize.
472  */
473  blksize = set->nextBlockSize;
474  set->nextBlockSize <<= 1;
475  if (set->nextBlockSize > set->maxBlockSize)
476  set->nextBlockSize = set->maxBlockSize;
477 
478  /* we'll need space for the chunk, chunk hdr and block hdr */
479  required_size = chunk_size + Generation_CHUNKHDRSZ + Generation_BLOCKHDRSZ;
480 
481  /* round the size up to the next power of 2 */
482  if (blksize < required_size)
483  blksize = pg_nextpower2_size_t(required_size);
484 
485  block = (GenerationBlock *) malloc(blksize);
486 
487  if (block == NULL)
489 
490  context->mem_allocated += blksize;
491 
492  /* initialize the new block */
493  GenerationBlockInit(set, block, blksize);
494 
495  /* add it to the doubly-linked list of blocks */
496  dlist_push_head(&set->blocks, &block->node);
497 
498  /* make this the current block */
499  set->block = block;
500 
501  return GenerationAllocChunkFromBlock(context, block, size, chunk_size);
502 }
503 
504 /*
505  * GenerationAlloc
506  * Returns a pointer to allocated memory of given size or raises an ERROR
507  * on allocation failure, or returns NULL when flags contains
508  * MCXT_ALLOC_NO_OOM.
509  *
510  * No request may exceed:
511  * MAXALIGN_DOWN(SIZE_MAX) - Generation_BLOCKHDRSZ - Generation_CHUNKHDRSZ
512  * All callers use a much-lower limit.
513  *
514  * Note: when using valgrind, it doesn't matter how the returned allocation
515  * is marked, as mcxt.c will set it to UNDEFINED. In some paths we will
516  * return space that is marked NOACCESS - GenerationRealloc has to beware!
517  *
518  * This function should only contain the most common code paths. Everything
519  * else should be in pg_noinline helper functions, thus avoiding the overhead
520  * of creating a stack frame for the common cases. Allocating memory is often
521  * a bottleneck in many workloads, so avoiding stack frame setup is
522  * worthwhile. Helper functions should always directly return the newly
523  * allocated memory so that we can just return that address directly as a tail
524  * call.
525  */
526 void *
528 {
530  GenerationBlock *block;
531  Size chunk_size;
532  Size required_size;
533 
535 
536 #ifdef MEMORY_CONTEXT_CHECKING
537  /* ensure there's always space for the sentinel byte */
538  chunk_size = MAXALIGN(size + 1);
539 #else
540  chunk_size = MAXALIGN(size);
541 #endif
542 
543  /*
544  * If requested size exceeds maximum for chunks we hand the the request
545  * off to GenerationAllocLarge().
546  */
547  if (chunk_size > set->allocChunkLimit)
548  return GenerationAllocLarge(context, size, flags);
549 
550  required_size = chunk_size + Generation_CHUNKHDRSZ;
551 
552  /*
553  * Not an oversized chunk. We try to first make use of the current block,
554  * but if there's not enough space in it, instead of allocating a new
555  * block, we look to see if the empty freeblock has enough space. We
556  * don't try reusing the keeper block. If it's become empty we'll reuse
557  * that again only if the context is reset.
558  *
559  * We only try reusing the freeblock if we've no space for this allocation
560  * on the current block. When a freeblock exists, we'll switch to it once
561  * the first time we can't fit an allocation in the current block. We
562  * avoid ping-ponging between the two as we need to be careful not to
563  * fragment differently sized consecutive allocations between several
564  * blocks. Going between the two could cause fragmentation for FIFO
565  * workloads, which generation is meant to be good at.
566  */
567  block = set->block;
568 
569  if (unlikely(GenerationBlockFreeBytes(block) < required_size))
570  {
571  GenerationBlock *freeblock = set->freeblock;
572 
573  /* freeblock, if set, must be empty */
574  Assert(freeblock == NULL || GenerationBlockIsEmpty(freeblock));
575 
576  /* check if we have a freeblock and if it's big enough */
577  if (freeblock != NULL &&
578  GenerationBlockFreeBytes(freeblock) >= required_size)
579  {
580  /* make the freeblock the current block */
581  set->freeblock = NULL;
582  set->block = freeblock;
583 
585  freeblock,
586  size,
587  chunk_size);
588  }
589  else
590  {
591  /*
592  * No freeblock, or it's not big enough for this allocation. Make
593  * a new block.
594  */
595  return GenerationAllocFromNewBlock(context, size, flags, chunk_size);
596  }
597  }
598 
599  /* The current block has space, so just allocate chunk there. */
600  return GenerationAllocChunkFromBlock(context, block, size, chunk_size);
601 }
602 
603 /*
604  * GenerationBlockInit
605  * Initializes 'block' assuming 'blksize'. Does not update the context's
606  * mem_allocated field.
607  */
608 static inline void
610  Size blksize)
611 {
612  block->context = context;
613  block->blksize = blksize;
614  block->nchunks = 0;
615  block->nfree = 0;
616 
617  block->freeptr = ((char *) block) + Generation_BLOCKHDRSZ;
618  block->endptr = ((char *) block) + blksize;
619 
620  /* Mark unallocated space NOACCESS. */
622  blksize - Generation_BLOCKHDRSZ);
623 }
624 
625 /*
626  * GenerationBlockMarkEmpty
627  * Set a block as empty. Does not free the block.
628  */
629 static inline void
631 {
632 #if defined(USE_VALGRIND) || defined(CLOBBER_FREED_MEMORY)
633  char *datastart = ((char *) block) + Generation_BLOCKHDRSZ;
634 #endif
635 
636 #ifdef CLOBBER_FREED_MEMORY
637  wipe_mem(datastart, block->freeptr - datastart);
638 #else
639  /* wipe_mem() would have done this */
640  VALGRIND_MAKE_MEM_NOACCESS(datastart, block->freeptr - datastart);
641 #endif
642 
643  /* Reset the block, but don't return it to malloc */
644  block->nchunks = 0;
645  block->nfree = 0;
646  block->freeptr = ((char *) block) + Generation_BLOCKHDRSZ;
647 }
648 
649 /*
650  * GenerationBlockFreeBytes
651  * Returns the number of bytes free in 'block'
652  */
653 static inline Size
655 {
656  return (block->endptr - block->freeptr);
657 }
658 
659 /*
660  * GenerationBlockFree
661  * Remove 'block' from 'set' and release the memory consumed by it.
662  */
663 static inline void
665 {
666  /* Make sure nobody tries to free the keeper block */
667  Assert(!IsKeeperBlock(set, block));
668  /* We shouldn't be freeing the freeblock either */
669  Assert(block != set->freeblock);
670 
671  /* release the block from the list of blocks */
672  dlist_delete(&block->node);
673 
674  ((MemoryContext) set)->mem_allocated -= block->blksize;
675 
676 #ifdef CLOBBER_FREED_MEMORY
677  wipe_mem(block, block->blksize);
678 #endif
679 
680  free(block);
681 }
682 
683 /*
684  * GenerationFree
685  * Update number of chunks in the block, and consider freeing the block
686  * if it's become empty.
687  */
688 void
689 GenerationFree(void *pointer)
690 {
691  MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
692  GenerationBlock *block;
693  GenerationContext *set;
694 #if (defined(MEMORY_CONTEXT_CHECKING) && defined(USE_ASSERT_CHECKING)) \
695  || defined(CLOBBER_FREED_MEMORY)
696  Size chunksize;
697 #endif
698 
699  /* Allow access to the chunk header. */
701 
702  if (MemoryChunkIsExternal(chunk))
703  {
704  block = ExternalChunkGetBlock(chunk);
705 
706  /*
707  * Try to verify that we have a sane block pointer: the block header
708  * should reference a generation context.
709  */
710  if (!GenerationBlockIsValid(block))
711  elog(ERROR, "could not find block containing chunk %p", chunk);
712 
713 #if (defined(MEMORY_CONTEXT_CHECKING) && defined(USE_ASSERT_CHECKING)) \
714  || defined(CLOBBER_FREED_MEMORY)
715  chunksize = block->endptr - (char *) pointer;
716 #endif
717  }
718  else
719  {
720  block = MemoryChunkGetBlock(chunk);
721 
722  /*
723  * In this path, for speed reasons we just Assert that the referenced
724  * block is good. Future field experience may show that this Assert
725  * had better become a regular runtime test-and-elog check.
726  */
728 
729 #if (defined(MEMORY_CONTEXT_CHECKING) && defined(USE_ASSERT_CHECKING)) \
730  || defined(CLOBBER_FREED_MEMORY)
731  chunksize = MemoryChunkGetValue(chunk);
732 #endif
733  }
734 
735 #ifdef MEMORY_CONTEXT_CHECKING
736  /* Test for someone scribbling on unused space in chunk */
737  Assert(chunk->requested_size < chunksize);
738  if (!sentinel_ok(pointer, chunk->requested_size))
739  elog(WARNING, "detected write past chunk end in %s %p",
740  ((MemoryContext) block->context)->name, chunk);
741 #endif
742 
743 #ifdef CLOBBER_FREED_MEMORY
744  wipe_mem(pointer, chunksize);
745 #endif
746 
747 #ifdef MEMORY_CONTEXT_CHECKING
748  /* Reset requested_size to InvalidAllocSize in freed chunks */
749  chunk->requested_size = InvalidAllocSize;
750 #endif
751 
752  block->nfree += 1;
753 
754  Assert(block->nchunks > 0);
755  Assert(block->nfree <= block->nchunks);
756  Assert(block != block->context->freeblock);
757 
758  /* If there are still allocated chunks in the block, we're done. */
759  if (likely(block->nfree < block->nchunks))
760  return;
761 
762  set = block->context;
763 
764  /*-----------------------
765  * The block this allocation was on has now become completely empty of
766  * chunks. In the general case, we can now return the memory for this
767  * block back to malloc. However, there are cases where we don't want to
768  * do that:
769  *
770  * 1) If it's the keeper block. This block was malloc'd in the same
771  * allocation as the context itself and can't be free'd without
772  * freeing the context.
773  * 2) If it's the current block. We could free this, but doing so would
774  * leave us nothing to set the current block to, so we just mark the
775  * block as empty so new allocations can reuse it again.
776  * 3) If we have no "freeblock" set, then we save a single block for
777  * future allocations to avoid having to malloc a new block again.
778  * This is useful for FIFO workloads as it avoids continual
779  * free/malloc cycles.
780  */
781  if (IsKeeperBlock(set, block) || set->block == block)
782  GenerationBlockMarkEmpty(block); /* case 1 and 2 */
783  else if (set->freeblock == NULL)
784  {
785  /* case 3 */
787  set->freeblock = block;
788  }
789  else
790  GenerationBlockFree(set, block); /* Otherwise, free it */
791 }
792 
793 /*
794  * GenerationRealloc
795  * When handling repalloc, we simply allocate a new chunk, copy the data
796  * and discard the old one. The only exception is when the new size fits
797  * into the old chunk - in that case we just update chunk header.
798  */
799 void *
800 GenerationRealloc(void *pointer, Size size, int flags)
801 {
802  MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
803  GenerationContext *set;
804  GenerationBlock *block;
805  GenerationPointer newPointer;
806  Size oldsize;
807 
808  /* Allow access to the chunk header. */
810 
811  if (MemoryChunkIsExternal(chunk))
812  {
813  block = ExternalChunkGetBlock(chunk);
814 
815  /*
816  * Try to verify that we have a sane block pointer: the block header
817  * should reference a generation context.
818  */
819  if (!GenerationBlockIsValid(block))
820  elog(ERROR, "could not find block containing chunk %p", chunk);
821 
822  oldsize = block->endptr - (char *) pointer;
823  }
824  else
825  {
826  block = MemoryChunkGetBlock(chunk);
827 
828  /*
829  * In this path, for speed reasons we just Assert that the referenced
830  * block is good. Future field experience may show that this Assert
831  * had better become a regular runtime test-and-elog check.
832  */
834 
835  oldsize = MemoryChunkGetValue(chunk);
836  }
837 
838  set = block->context;
839 
840 #ifdef MEMORY_CONTEXT_CHECKING
841  /* Test for someone scribbling on unused space in chunk */
842  Assert(chunk->requested_size < oldsize);
843  if (!sentinel_ok(pointer, chunk->requested_size))
844  elog(WARNING, "detected write past chunk end in %s %p",
845  ((MemoryContext) set)->name, chunk);
846 #endif
847 
848  /*
849  * Maybe the allocated area already is >= the new size. (In particular,
850  * we always fall out here if the requested size is a decrease.)
851  *
852  * This memory context does not use power-of-2 chunk sizing and instead
853  * carves the chunks to be as small as possible, so most repalloc() calls
854  * will end up in the palloc/memcpy/pfree branch.
855  *
856  * XXX Perhaps we should annotate this condition with unlikely()?
857  */
858  if (oldsize >= size)
859  {
860 #ifdef MEMORY_CONTEXT_CHECKING
861  Size oldrequest = chunk->requested_size;
862 
863 #ifdef RANDOMIZE_ALLOCATED_MEMORY
864  /* We can only fill the extra space if we know the prior request */
865  if (size > oldrequest)
866  randomize_mem((char *) pointer + oldrequest,
867  size - oldrequest);
868 #endif
869 
870  chunk->requested_size = size;
871 
872  /*
873  * If this is an increase, mark any newly-available part UNDEFINED.
874  * Otherwise, mark the obsolete part NOACCESS.
875  */
876  if (size > oldrequest)
877  VALGRIND_MAKE_MEM_UNDEFINED((char *) pointer + oldrequest,
878  size - oldrequest);
879  else
880  VALGRIND_MAKE_MEM_NOACCESS((char *) pointer + size,
881  oldsize - size);
882 
883  /* set mark to catch clobber of "unused" space */
884  set_sentinel(pointer, size);
885 #else /* !MEMORY_CONTEXT_CHECKING */
886 
887  /*
888  * We don't have the information to determine whether we're growing
889  * the old request or shrinking it, so we conservatively mark the
890  * entire new allocation DEFINED.
891  */
892  VALGRIND_MAKE_MEM_NOACCESS(pointer, oldsize);
894 #endif
895 
896  /* Disallow access to the chunk header. */
898 
899  return pointer;
900  }
901 
902  /* allocate new chunk (this also checks size is valid) */
903  newPointer = GenerationAlloc((MemoryContext) set, size, flags);
904 
905  /* leave immediately if request was not completed */
906  if (newPointer == NULL)
907  {
908  /* Disallow access to the chunk header. */
910  return MemoryContextAllocationFailure((MemoryContext) set, size, flags);
911  }
912 
913  /*
914  * GenerationAlloc() may have returned a region that is still NOACCESS.
915  * Change it to UNDEFINED for the moment; memcpy() will then transfer
916  * definedness from the old allocation to the new. If we know the old
917  * allocation, copy just that much. Otherwise, make the entire old chunk
918  * defined to avoid errors as we copy the currently-NOACCESS trailing
919  * bytes.
920  */
921  VALGRIND_MAKE_MEM_UNDEFINED(newPointer, size);
922 #ifdef MEMORY_CONTEXT_CHECKING
923  oldsize = chunk->requested_size;
924 #else
925  VALGRIND_MAKE_MEM_DEFINED(pointer, oldsize);
926 #endif
927 
928  /* transfer existing data (certain to fit) */
929  memcpy(newPointer, pointer, oldsize);
930 
931  /* free old chunk */
932  GenerationFree(pointer);
933 
934  return newPointer;
935 }
936 
937 /*
938  * GenerationGetChunkContext
939  * Return the MemoryContext that 'pointer' belongs to.
940  */
943 {
944  MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
945  GenerationBlock *block;
946 
947  /* Allow access to the chunk header. */
949 
950  if (MemoryChunkIsExternal(chunk))
951  block = ExternalChunkGetBlock(chunk);
952  else
953  block = (GenerationBlock *) MemoryChunkGetBlock(chunk);
954 
955  /* Disallow access to the chunk header. */
957 
959  return &block->context->header;
960 }
961 
962 /*
963  * GenerationGetChunkSpace
964  * Given a currently-allocated chunk, determine the total space
965  * it occupies (including all memory-allocation overhead).
966  */
967 Size
969 {
970  MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
971  Size chunksize;
972 
973  /* Allow access to the chunk header. */
975 
976  if (MemoryChunkIsExternal(chunk))
977  {
978  GenerationBlock *block = ExternalChunkGetBlock(chunk);
979 
981  chunksize = block->endptr - (char *) pointer;
982  }
983  else
984  chunksize = MemoryChunkGetValue(chunk);
985 
986  /* Disallow access to the chunk header. */
988 
989  return Generation_CHUNKHDRSZ + chunksize;
990 }
991 
992 /*
993  * GenerationIsEmpty
994  * Is a GenerationContext empty of any allocated space?
995  */
996 bool
998 {
1000  dlist_iter iter;
1001 
1002  Assert(GenerationIsValid(set));
1003 
1004  dlist_foreach(iter, &set->blocks)
1005  {
1006  GenerationBlock *block = dlist_container(GenerationBlock, node, iter.cur);
1007 
1008  if (block->nchunks > 0)
1009  return false;
1010  }
1011 
1012  return true;
1013 }
1014 
1015 /*
1016  * GenerationStats
1017  * Compute stats about memory consumption of a Generation context.
1018  *
1019  * printfunc: if not NULL, pass a human-readable stats string to this.
1020  * passthru: pass this pointer through to printfunc.
1021  * totals: if not NULL, add stats about this context into *totals.
1022  * print_to_stderr: print stats to stderr if true, elog otherwise.
1023  *
1024  * XXX freespace only accounts for empty space at the end of the block, not
1025  * space of freed chunks (which is unknown).
1026  */
1027 void
1029  MemoryStatsPrintFunc printfunc, void *passthru,
1030  MemoryContextCounters *totals, bool print_to_stderr)
1031 {
1033  Size nblocks = 0;
1034  Size nchunks = 0;
1035  Size nfreechunks = 0;
1036  Size totalspace;
1037  Size freespace = 0;
1038  dlist_iter iter;
1039 
1040  Assert(GenerationIsValid(set));
1041 
1042  /* Include context header in totalspace */
1043  totalspace = MAXALIGN(sizeof(GenerationContext));
1044 
1045  dlist_foreach(iter, &set->blocks)
1046  {
1047  GenerationBlock *block = dlist_container(GenerationBlock, node, iter.cur);
1048 
1049  nblocks++;
1050  nchunks += block->nchunks;
1051  nfreechunks += block->nfree;
1052  totalspace += block->blksize;
1053  freespace += (block->endptr - block->freeptr);
1054  }
1055 
1056  if (printfunc)
1057  {
1058  char stats_string[200];
1059 
1060  snprintf(stats_string, sizeof(stats_string),
1061  "%zu total in %zu blocks (%zu chunks); %zu free (%zu chunks); %zu used",
1062  totalspace, nblocks, nchunks, freespace,
1063  nfreechunks, totalspace - freespace);
1064  printfunc(context, passthru, stats_string, print_to_stderr);
1065  }
1066 
1067  if (totals)
1068  {
1069  totals->nblocks += nblocks;
1070  totals->freechunks += nfreechunks;
1071  totals->totalspace += totalspace;
1072  totals->freespace += freespace;
1073  }
1074 }
1075 
1076 
1077 #ifdef MEMORY_CONTEXT_CHECKING
1078 
1079 /*
1080  * GenerationCheck
1081  * Walk through chunks and check consistency of memory.
1082  *
1083  * NOTE: report errors as WARNING, *not* ERROR or FATAL. Otherwise you'll
1084  * find yourself in an infinite loop when trouble occurs, because this
1085  * routine will be entered again when elog cleanup tries to release memory!
1086  */
1087 void
1088 GenerationCheck(MemoryContext context)
1089 {
1091  const char *name = context->name;
1092  dlist_iter iter;
1093  Size total_allocated = 0;
1094 
1095  /* walk all blocks in this context */
1096  dlist_foreach(iter, &gen->blocks)
1097  {
1098  GenerationBlock *block = dlist_container(GenerationBlock, node, iter.cur);
1099  int nfree,
1100  nchunks;
1101  char *ptr;
1102  bool has_external_chunk = false;
1103 
1104  total_allocated += block->blksize;
1105 
1106  /*
1107  * nfree > nchunks is surely wrong. Equality is allowed as the block
1108  * might completely empty if it's the freeblock.
1109  */
1110  if (block->nfree > block->nchunks)
1111  elog(WARNING, "problem in Generation %s: number of free chunks %d in block %p exceeds %d allocated",
1112  name, block->nfree, block, block->nchunks);
1113 
1114  /* check block belongs to the correct context */
1115  if (block->context != gen)
1116  elog(WARNING, "problem in Generation %s: bogus context link in block %p",
1117  name, block);
1118 
1119  /* Now walk through the chunks and count them. */
1120  nfree = 0;
1121  nchunks = 0;
1122  ptr = ((char *) block) + Generation_BLOCKHDRSZ;
1123 
1124  while (ptr < block->freeptr)
1125  {
1126  MemoryChunk *chunk = (MemoryChunk *) ptr;
1127  GenerationBlock *chunkblock;
1128  Size chunksize;
1129 
1130  /* Allow access to the chunk header. */
1132 
1133  if (MemoryChunkIsExternal(chunk))
1134  {
1135  chunkblock = ExternalChunkGetBlock(chunk);
1136  chunksize = block->endptr - (char *) MemoryChunkGetPointer(chunk);
1137  has_external_chunk = true;
1138  }
1139  else
1140  {
1141  chunkblock = MemoryChunkGetBlock(chunk);
1142  chunksize = MemoryChunkGetValue(chunk);
1143  }
1144 
1145  /* move to the next chunk */
1146  ptr += (chunksize + Generation_CHUNKHDRSZ);
1147 
1148  nchunks += 1;
1149 
1150  /* chunks have both block and context pointers, so check both */
1151  if (chunkblock != block)
1152  elog(WARNING, "problem in Generation %s: bogus block link in block %p, chunk %p",
1153  name, block, chunk);
1154 
1155 
1156  /* is chunk allocated? */
1157  if (chunk->requested_size != InvalidAllocSize)
1158  {
1159  /* now make sure the chunk size is correct */
1160  if (chunksize < chunk->requested_size ||
1161  chunksize != MAXALIGN(chunksize))
1162  elog(WARNING, "problem in Generation %s: bogus chunk size in block %p, chunk %p",
1163  name, block, chunk);
1164 
1165  /* check sentinel */
1166  Assert(chunk->requested_size < chunksize);
1167  if (!sentinel_ok(chunk, Generation_CHUNKHDRSZ + chunk->requested_size))
1168  elog(WARNING, "problem in Generation %s: detected write past chunk end in block %p, chunk %p",
1169  name, block, chunk);
1170  }
1171  else
1172  nfree += 1;
1173 
1174  /* if chunk is allocated, disallow access to the chunk header */
1175  if (chunk->requested_size != InvalidAllocSize)
1177  }
1178 
1179  /*
1180  * Make sure we got the expected number of allocated and free chunks
1181  * (as tracked in the block header).
1182  */
1183  if (nchunks != block->nchunks)
1184  elog(WARNING, "problem in Generation %s: number of allocated chunks %d in block %p does not match header %d",
1185  name, nchunks, block, block->nchunks);
1186 
1187  if (nfree != block->nfree)
1188  elog(WARNING, "problem in Generation %s: number of free chunks %d in block %p does not match header %d",
1189  name, nfree, block, block->nfree);
1190 
1191  if (has_external_chunk && nchunks > 1)
1192  elog(WARNING, "problem in Generation %s: external chunk on non-dedicated block %p",
1193  name, block);
1194 
1195  }
1196 
1197  Assert(total_allocated == context->mem_allocated);
1198 }
1199 
1200 #endif /* MEMORY_CONTEXT_CHECKING */
unsigned int uint32
Definition: c.h:493
#define pg_noinline
Definition: c.h:237
#define Min(x, y)
Definition: c.h:991
#define likely(x)
Definition: c.h:297
#define MAXALIGN(LEN)
Definition: c.h:798
#define Max(x, y)
Definition: c.h:985
#define unlikely(x)
Definition: c.h:298
#define StaticAssertDecl(condition, errmessage)
Definition: c.h:923
size_t Size
Definition: c.h:592
int errdetail(const char *fmt,...)
Definition: elog.c:1205
int errcode(int sqlerrcode)
Definition: elog.c:859
int errmsg(const char *fmt,...)
Definition: elog.c:1072
#define WARNING
Definition: elog.h:36
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
#define ereport(elevel,...)
Definition: elog.h:149
static void GenerationBlockInit(GenerationContext *context, GenerationBlock *block, Size blksize)
Definition: generation.c:609
#define IsKeeperBlock(set, block)
Definition: generation.c:132
static pg_noinline void * GenerationAllocLarge(MemoryContext context, Size size, int flags)
Definition: generation.c:343
#define Generation_CHUNK_FRACTION
Definition: generation.c:49
void GenerationReset(MemoryContext context)
Definition: generation.c:283
static Size GenerationBlockFreeBytes(GenerationBlock *block)
Definition: generation.c:654
void * GenerationAlloc(MemoryContext context, Size size, int flags)
Definition: generation.c:527
#define KeeperBlock(set)
Definition: generation.c:127
static void GenerationBlockFree(GenerationContext *set, GenerationBlock *block)
Definition: generation.c:664
void GenerationFree(void *pointer)
Definition: generation.c:689
MemoryContext GenerationGetChunkContext(void *pointer)
Definition: generation.c:942
Size GenerationGetChunkSpace(void *pointer)
Definition: generation.c:968
void * GenerationPointer
Definition: generation.c:53
struct GenerationContext GenerationContext
#define Generation_CHUNKHDRSZ
Definition: generation.c:47
static void GenerationBlockMarkEmpty(GenerationBlock *block)
Definition: generation.c:630
#define GenerationBlockIsValid(block)
Definition: generation.c:109
bool GenerationIsEmpty(MemoryContext context)
Definition: generation.c:997
static pg_noinline void * GenerationAllocFromNewBlock(MemoryContext context, Size size, int flags, Size chunk_size)
Definition: generation.c:461
void GenerationStats(MemoryContext context, MemoryStatsPrintFunc printfunc, void *passthru, MemoryContextCounters *totals, bool print_to_stderr)
Definition: generation.c:1028
#define GenerationBlockIsEmpty(b)
Definition: generation.c:116
static void * GenerationAllocChunkFromBlock(MemoryContext context, GenerationBlock *block, Size size, Size chunk_size)
Definition: generation.c:413
void * GenerationRealloc(void *pointer, Size size, int flags)
Definition: generation.c:800
#define Generation_BLOCKHDRSZ
Definition: generation.c:46
MemoryContext GenerationContextCreate(MemoryContext parent, const char *name, Size minContextSize, Size initBlockSize, Size maxBlockSize)
Definition: generation.c:160
void GenerationDelete(MemoryContext context)
Definition: generation.c:328
#define GenerationIsValid(set)
Definition: generation.c:102
#define ExternalChunkGetBlock(chunk)
Definition: generation.c:123
#define free(a)
Definition: header.h:65
#define malloc(a)
Definition: header.h:50
#define dlist_foreach(iter, lhead)
Definition: ilist.h:623
static void dlist_init(dlist_head *head)
Definition: ilist.h:314
static bool dlist_has_next(const dlist_head *head, const dlist_node *node)
Definition: ilist.h:503
static void dlist_delete(dlist_node *node)
Definition: ilist.h:405
static void dlist_push_head(dlist_head *head, dlist_node *node)
Definition: ilist.h:347
#define dlist_foreach_modify(iter, lhead)
Definition: ilist.h:640
static bool dlist_is_empty(const dlist_head *head)
Definition: ilist.h:336
static dlist_node * dlist_head_node(dlist_head *head)
Definition: ilist.h:565
#define dlist_container(type, membername, ptr)
Definition: ilist.h:593
Assert(fmt[strlen(fmt) - 1] !='\n')
void MemoryContextCreate(MemoryContext node, NodeTag tag, MemoryContextMethodID method_id, MemoryContext parent, const char *name)
Definition: mcxt.c:1088
MemoryContext TopMemoryContext
Definition: mcxt.c:137
void MemoryContextStats(MemoryContext context)
Definition: mcxt.c:802
void * MemoryContextAllocationFailure(MemoryContext context, Size size, int flags)
Definition: mcxt.c:1135
#define VALGRIND_MAKE_MEM_DEFINED(addr, size)
Definition: memdebug.h:26
#define VALGRIND_MAKE_MEM_NOACCESS(addr, size)
Definition: memdebug.h:27
#define VALGRIND_MAKE_MEM_UNDEFINED(addr, size)
Definition: memdebug.h:28
void(* MemoryStatsPrintFunc)(MemoryContext context, void *passthru, const char *stats_string, bool print_to_stderr)
Definition: memnodes.h:54
#define AllocHugeSizeIsValid(size)
Definition: memutils.h:49
#define InvalidAllocSize
Definition: memutils.h:47
static void MemoryContextCheckSize(MemoryContext context, Size size, int flags)
@ MCTX_GENERATION_ID
#define MEMORYCHUNK_MAX_BLOCKOFFSET
#define MEMORYCHUNK_MAX_VALUE
static Size MemoryChunkGetValue(MemoryChunk *chunk)
#define MemoryChunkGetPointer(c)
static bool MemoryChunkIsExternal(MemoryChunk *chunk)
static void MemoryChunkSetHdrMaskExternal(MemoryChunk *chunk, MemoryContextMethodID methodid)
static void * MemoryChunkGetBlock(MemoryChunk *chunk)
#define PointerGetMemoryChunk(p)
static void MemoryChunkSetHdrMask(MemoryChunk *chunk, void *block, Size value, MemoryContextMethodID methodid)
struct MemoryContextData * MemoryContext
Definition: palloc.h:36
#define pg_nextpower2_size_t
Definition: pg_bitutils.h:338
#define snprintf
Definition: port.h:238
tree context
Definition: radixtree.h:1797
static pg_noinline void Size size
Definition: slab.c:607
char * freeptr
Definition: generation.c:94
dlist_node node
Definition: generation.c:89
GenerationContext * context
Definition: generation.c:90
MemoryContextData header
Definition: generation.c:61
GenerationBlock * freeblock
Definition: generation.c:70
uint32 maxBlockSize
Definition: generation.c:65
uint32 nextBlockSize
Definition: generation.c:66
dlist_head blocks
Definition: generation.c:72
uint32 initBlockSize
Definition: generation.c:64
GenerationBlock * block
Definition: generation.c:69
uint32 allocChunkLimit
Definition: generation.c:67
dlist_node * cur
Definition: ilist.h:179
dlist_node * cur
Definition: ilist.h:200
const char * name