Debian Codegraph @

src/backend/utils/mmgr/generation.c

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