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