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