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;
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 
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 
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 request off to
545  * 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 {
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 
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 {
803  GenerationContext *set;
804  GenerationBlock *block;
805  GenerationPointer newPointer;
806  Size oldsize;
807 
808  /* Allow access to the chunk header. */
810 
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 big enough. (In particular, we always
850  * 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 #ifdef MEMORY_CONTEXT_CHECKING
859  /* With MEMORY_CONTEXT_CHECKING, we need an extra byte for the sentinel */
860  if (oldsize > size)
861 #else
862  if (oldsize >= size)
863 #endif
864  {
865 #ifdef MEMORY_CONTEXT_CHECKING
866  Size oldrequest = chunk->requested_size;
867 
868 #ifdef RANDOMIZE_ALLOCATED_MEMORY
869  /* We can only fill the extra space if we know the prior request */
870  if (size > oldrequest)
871  randomize_mem((char *) pointer + oldrequest,
872  size - oldrequest);
873 #endif
874 
875  chunk->requested_size = size;
876 
877  /*
878  * If this is an increase, mark any newly-available part UNDEFINED.
879  * Otherwise, mark the obsolete part NOACCESS.
880  */
881  if (size > oldrequest)
882  VALGRIND_MAKE_MEM_UNDEFINED((char *) pointer + oldrequest,
883  size - oldrequest);
884  else
885  VALGRIND_MAKE_MEM_NOACCESS((char *) pointer + size,
886  oldsize - size);
887 
888  /* set mark to catch clobber of "unused" space */
889  set_sentinel(pointer, size);
890 #else /* !MEMORY_CONTEXT_CHECKING */
891 
892  /*
893  * We don't have the information to determine whether we're growing
894  * the old request or shrinking it, so we conservatively mark the
895  * entire new allocation DEFINED.
896  */
897  VALGRIND_MAKE_MEM_NOACCESS(pointer, oldsize);
899 #endif
900 
901  /* Disallow access to the chunk header. */
903 
904  return pointer;
905  }
906 
907  /* allocate new chunk (this also checks size is valid) */
908  newPointer = GenerationAlloc((MemoryContext) set, size, flags);
909 
910  /* leave immediately if request was not completed */
911  if (newPointer == NULL)
912  {
913  /* Disallow access to the chunk header. */
915  return MemoryContextAllocationFailure((MemoryContext) set, size, flags);
916  }
917 
918  /*
919  * GenerationAlloc() may have returned a region that is still NOACCESS.
920  * Change it to UNDEFINED for the moment; memcpy() will then transfer
921  * definedness from the old allocation to the new. If we know the old
922  * allocation, copy just that much. Otherwise, make the entire old chunk
923  * defined to avoid errors as we copy the currently-NOACCESS trailing
924  * bytes.
925  */
926  VALGRIND_MAKE_MEM_UNDEFINED(newPointer, size);
927 #ifdef MEMORY_CONTEXT_CHECKING
928  oldsize = chunk->requested_size;
929 #else
930  VALGRIND_MAKE_MEM_DEFINED(pointer, oldsize);
931 #endif
932 
933  /* transfer existing data (certain to fit) */
934  memcpy(newPointer, pointer, oldsize);
935 
936  /* free old chunk */
937  GenerationFree(pointer);
938 
939  return newPointer;
940 }
941 
942 /*
943  * GenerationGetChunkContext
944  * Return the MemoryContext that 'pointer' belongs to.
945  */
948 {
950  GenerationBlock *block;
951 
952  /* Allow access to the chunk header. */
954 
956  block = ExternalChunkGetBlock(chunk);
957  else
959 
960  /* Disallow access to the chunk header. */
962 
964  return &block->context->header;
965 }
966 
967 /*
968  * GenerationGetChunkSpace
969  * Given a currently-allocated chunk, determine the total space
970  * it occupies (including all memory-allocation overhead).
971  */
972 Size
974 {
976  Size chunksize;
977 
978  /* Allow access to the chunk header. */
980 
982  {
984 
986  chunksize = block->endptr - (char *) pointer;
987  }
988  else
989  chunksize = MemoryChunkGetValue(chunk);
990 
991  /* Disallow access to the chunk header. */
993 
994  return Generation_CHUNKHDRSZ + chunksize;
995 }
996 
997 /*
998  * GenerationIsEmpty
999  * Is a GenerationContext empty of any allocated space?
1000  */
1001 bool
1003 {
1005  dlist_iter iter;
1006 
1007  Assert(GenerationIsValid(set));
1008 
1009  dlist_foreach(iter, &set->blocks)
1010  {
1011  GenerationBlock *block = dlist_container(GenerationBlock, node, iter.cur);
1012 
1013  if (block->nchunks > 0)
1014  return false;
1015  }
1016 
1017  return true;
1018 }
1019 
1020 /*
1021  * GenerationStats
1022  * Compute stats about memory consumption of a Generation context.
1023  *
1024  * printfunc: if not NULL, pass a human-readable stats string to this.
1025  * passthru: pass this pointer through to printfunc.
1026  * totals: if not NULL, add stats about this context into *totals.
1027  * print_to_stderr: print stats to stderr if true, elog otherwise.
1028  *
1029  * XXX freespace only accounts for empty space at the end of the block, not
1030  * space of freed chunks (which is unknown).
1031  */
1032 void
1034  MemoryStatsPrintFunc printfunc, void *passthru,
1035  MemoryContextCounters *totals, bool print_to_stderr)
1036 {
1038  Size nblocks = 0;
1039  Size nchunks = 0;
1040  Size nfreechunks = 0;
1041  Size totalspace;
1042  Size freespace = 0;
1043  dlist_iter iter;
1044 
1045  Assert(GenerationIsValid(set));
1046 
1047  /* Include context header in totalspace */
1048  totalspace = MAXALIGN(sizeof(GenerationContext));
1049 
1050  dlist_foreach(iter, &set->blocks)
1051  {
1052  GenerationBlock *block = dlist_container(GenerationBlock, node, iter.cur);
1053 
1054  nblocks++;
1055  nchunks += block->nchunks;
1056  nfreechunks += block->nfree;
1057  totalspace += block->blksize;
1058  freespace += (block->endptr - block->freeptr);
1059  }
1060 
1061  if (printfunc)
1062  {
1063  char stats_string[200];
1064 
1065  snprintf(stats_string, sizeof(stats_string),
1066  "%zu total in %zu blocks (%zu chunks); %zu free (%zu chunks); %zu used",
1067  totalspace, nblocks, nchunks, freespace,
1068  nfreechunks, totalspace - freespace);
1069  printfunc(context, passthru, stats_string, print_to_stderr);
1070  }
1071 
1072  if (totals)
1073  {
1074  totals->nblocks += nblocks;
1075  totals->freechunks += nfreechunks;
1076  totals->totalspace += totalspace;
1077  totals->freespace += freespace;
1078  }
1079 }
1080 
1081 
1082 #ifdef MEMORY_CONTEXT_CHECKING
1083 
1084 /*
1085  * GenerationCheck
1086  * Walk through chunks and check consistency of memory.
1087  *
1088  * NOTE: report errors as WARNING, *not* ERROR or FATAL. Otherwise you'll
1089  * find yourself in an infinite loop when trouble occurs, because this
1090  * routine will be entered again when elog cleanup tries to release memory!
1091  */
1092 void
1093 GenerationCheck(MemoryContext context)
1094 {
1096  const char *name = context->name;
1097  dlist_iter iter;
1098  Size total_allocated = 0;
1099 
1100  /* walk all blocks in this context */
1101  dlist_foreach(iter, &gen->blocks)
1102  {
1103  GenerationBlock *block = dlist_container(GenerationBlock, node, iter.cur);
1104  int nfree,
1105  nchunks;
1106  char *ptr;
1107  bool has_external_chunk = false;
1108 
1109  total_allocated += block->blksize;
1110 
1111  /*
1112  * nfree > nchunks is surely wrong. Equality is allowed as the block
1113  * might completely empty if it's the freeblock.
1114  */
1115  if (block->nfree > block->nchunks)
1116  elog(WARNING, "problem in Generation %s: number of free chunks %d in block %p exceeds %d allocated",
1117  name, block->nfree, block, block->nchunks);
1118 
1119  /* check block belongs to the correct context */
1120  if (block->context != gen)
1121  elog(WARNING, "problem in Generation %s: bogus context link in block %p",
1122  name, block);
1123 
1124  /* Now walk through the chunks and count them. */
1125  nfree = 0;
1126  nchunks = 0;
1127  ptr = ((char *) block) + Generation_BLOCKHDRSZ;
1128 
1129  while (ptr < block->freeptr)
1130  {
1131  MemoryChunk *chunk = (MemoryChunk *) ptr;
1132  GenerationBlock *chunkblock;
1133  Size chunksize;
1134 
1135  /* Allow access to the chunk header. */
1137 
1139  {
1140  chunkblock = ExternalChunkGetBlock(chunk);
1141  chunksize = block->endptr - (char *) MemoryChunkGetPointer(chunk);
1142  has_external_chunk = true;
1143  }
1144  else
1145  {
1146  chunkblock = MemoryChunkGetBlock(chunk);
1147  chunksize = MemoryChunkGetValue(chunk);
1148  }
1149 
1150  /* move to the next chunk */
1151  ptr += (chunksize + Generation_CHUNKHDRSZ);
1152 
1153  nchunks += 1;
1154 
1155  /* chunks have both block and context pointers, so check both */
1156  if (chunkblock != block)
1157  elog(WARNING, "problem in Generation %s: bogus block link in block %p, chunk %p",
1158  name, block, chunk);
1159 
1160 
1161  /* is chunk allocated? */
1162  if (chunk->requested_size != InvalidAllocSize)
1163  {
1164  /* now make sure the chunk size is correct */
1165  if (chunksize < chunk->requested_size ||
1166  chunksize != MAXALIGN(chunksize))
1167  elog(WARNING, "problem in Generation %s: bogus chunk size in block %p, chunk %p",
1168  name, block, chunk);
1169 
1170  /* check sentinel */
1171  Assert(chunk->requested_size < chunksize);
1172  if (!sentinel_ok(chunk, Generation_CHUNKHDRSZ + chunk->requested_size))
1173  elog(WARNING, "problem in Generation %s: detected write past chunk end in block %p, chunk %p",
1174  name, block, chunk);
1175  }
1176  else
1177  nfree += 1;
1178 
1179  /* if chunk is allocated, disallow access to the chunk header */
1180  if (chunk->requested_size != InvalidAllocSize)
1182  }
1183 
1184  /*
1185  * Make sure we got the expected number of allocated and free chunks
1186  * (as tracked in the block header).
1187  */
1188  if (nchunks != block->nchunks)
1189  elog(WARNING, "problem in Generation %s: number of allocated chunks %d in block %p does not match header %d",
1190  name, nchunks, block, block->nchunks);
1191 
1192  if (nfree != block->nfree)
1193  elog(WARNING, "problem in Generation %s: number of free chunks %d in block %p does not match header %d",
1194  name, nfree, block, block->nfree);
1195 
1196  if (has_external_chunk && nchunks > 1)
1197  elog(WARNING, "problem in Generation %s: external chunk on non-dedicated block %p",
1198  name, block);
1199 
1200  }
1201 
1202  Assert(total_allocated == context->mem_allocated);
1203 }
1204 
1205 #endif /* MEMORY_CONTEXT_CHECKING */
unsigned int uint32
Definition: c.h:518
#define pg_noinline
Definition: c.h:265
#define Min(x, y)
Definition: c.h:1007
#define likely(x)
Definition: c.h:325
#define MAXALIGN(LEN)
Definition: c.h:814
#define Max(x, y)
Definition: c.h:1001
#define Assert(condition)
Definition: c.h:861
#define unlikely(x)
Definition: c.h:326
#define StaticAssertDecl(condition, errmessage)
Definition: c.h:939
size_t Size
Definition: c.h:608
int errdetail(const char *fmt,...)
Definition: elog.c:1203
int errcode(int sqlerrcode)
Definition: elog.c:853
int errmsg(const char *fmt,...)
Definition: elog.c:1070
#define WARNING
Definition: elog.h:36
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
#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:947
Size GenerationGetChunkSpace(void *pointer)
Definition: generation.c:973
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:1002
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:1033
#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
uint64 chunk
#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
void MemoryContextCreate(MemoryContext node, NodeTag tag, MemoryContextMethodID method_id, MemoryContext parent, const char *name)
Definition: mcxt.c:1100
MemoryContext TopMemoryContext
Definition: mcxt.c:149
void MemoryContextStats(MemoryContext context)
Definition: mcxt.c:814
void * MemoryContextAllocationFailure(MemoryContext context, Size size, int flags)
Definition: mcxt.c:1147
#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:417
#define snprintf
Definition: port.h:238
tree context
Definition: radixtree.h:1835
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