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