Debian Codegraph @

src/backend/utils/mmgr/slab.c

raw
1 /*-------------------------------------------------------------------------
2 *
3 * slab.c
4 * SLAB allocator definitions.
5 *
6 * SLAB is a MemoryContext implementation designed for cases where large
7 * numbers of equally-sized objects can be allocated and freed efficiently
8 * with minimal memory wastage and fragmentation.
9 *
10 *
11 * Portions Copyright (c) 2017-2025, PostgreSQL Global Development Group
12 *
13 * IDENTIFICATION
14 * src/backend/utils/mmgr/slab.c
15 *
16 *
17 * NOTE:
18 * The constant allocation size allows significant simplification and various
19 * optimizations over more general purpose allocators. The blocks are carved
20 * into chunks of exactly the right size, wasting only the space required to
21 * MAXALIGN the allocated chunks.
22 *
23 * Slab can also help reduce memory fragmentation in cases where longer-lived
24 * chunks remain stored on blocks while most of the other chunks have already
25 * been pfree'd. We give priority to putting new allocations into the
26 * "fullest" block. This help avoid having too many sparsely used blocks
27 * around and allows blocks to more easily become completely unused which
28 * allows them to be eventually free'd.
29 *
30 * We identify the "fullest" block to put new allocations on by using a block
31 * from the lowest populated element of the context's "blocklist" array.
32 * This is an array of dlists containing blocks which we partition by the
33 * number of free chunks which block has. Blocks with fewer free chunks are
34 * stored in a lower indexed dlist array slot. Full blocks go on the 0th
35 * element of the blocklist array. So that we don't have to have too many
36 * elements in the array, each dlist in the array is responsible for a range
37 * of free chunks. When a chunk is palloc'd or pfree'd we may need to move
38 * the block onto another dlist if the number of free chunks crosses the
39 * range boundary that the current list is responsible for. Having just a
40 * few blocklist elements reduces the number of times we must move the block
41 * onto another dlist element.
42 *
43 * We keep track of free chunks within each block by using a block-level free
44 * list. We consult this list when we allocate a new chunk in the block.
45 * The free list is a linked list, the head of which is pointed to with
46 * SlabBlock's freehead field. Each subsequent list item is stored in the
47 * free chunk's memory. We ensure chunks are large enough to store this
48 * address.
49 *
50 * When we allocate a new block, technically all chunks are free, however, to
51 * avoid having to write out the entire block to set the linked list for the
52 * free chunks for every chunk in the block, we instead store a pointer to
53 * the next "unused" chunk on the block and keep track of how many of these
54 * unused chunks there are. When a new block is malloc'd, all chunks are
55 * unused. The unused pointer starts with the first chunk on the block and
56 * as chunks are allocated, the unused pointer is incremented. As chunks are
57 * pfree'd, the unused pointer never goes backwards. The unused pointer can
58 * be thought of as a high watermark for the maximum number of chunks in the
59 * block which have been in use concurrently. When a chunk is pfree'd the
60 * chunk is put onto the head of the free list and the unused pointer is not
61 * changed. We only consume more unused chunks if we run out of free chunks
62 * on the free list. This method effectively gives priority to using
63 * previously used chunks over previously unused chunks, which should perform
64 * better due to CPU caching effects.
65 *
66 *-------------------------------------------------------------------------
67 */
68
69 #include "postgres.h"
70
71 #include "lib/ilist.h"
72 #include "utils/memdebug.h"
73 #include "utils/memutils.h"
74 #include "utils/memutils_internal.h"
75 #include "utils/memutils_memorychunk.h"
76
77 #define Slab_BLOCKHDRSZ MAXALIGN(sizeof(SlabBlock))
78
79 #ifdef MEMORY_CONTEXT_CHECKING
80 /*
81 * Size of the memory required to store the SlabContext.
82 * MEMORY_CONTEXT_CHECKING builds need some extra memory for the isChunkFree
83 * array.
84 */
85 #define Slab_CONTEXT_HDRSZ(chunksPerBlock) \
86 (sizeof(SlabContext) + ((chunksPerBlock) * sizeof(bool)))
87 #else
88 #define Slab_CONTEXT_HDRSZ(chunksPerBlock) sizeof(SlabContext)
89 #endif
90
91 /*
92 * The number of partitions to divide the blocklist into based their number of
93 * free chunks. There must be at least 2.
94 */
95 #define SLAB_BLOCKLIST_COUNT 3
96
97 /* The maximum number of completely empty blocks to keep around for reuse. */
98 #define SLAB_MAXIMUM_EMPTY_BLOCKS 10
99
100 /*
101 * SlabContext is a specialized implementation of MemoryContext.
102 */
103 typedef struct SlabContext
104 {
105 MemoryContextData header; /* Standard memory-context fields */
106 /* Allocation parameters for this context: */
107 uint32 chunkSize; /* the requested (non-aligned) chunk size */
108 uint32 fullChunkSize; /* chunk size with chunk header and alignment */
109 uint32 blockSize; /* the size to make each block of chunks */
110 int32 chunksPerBlock; /* number of chunks that fit in 1 block */
111 int32 curBlocklistIndex; /* index into the blocklist[] element
112 * containing the fullest, blocks */
113 #ifdef MEMORY_CONTEXT_CHECKING
114 bool *isChunkFree; /* array to mark free chunks in a block during
115 * SlabCheck */
116 #endif
117
118 int32 blocklist_shift; /* number of bits to shift the nfree count
119 * by to get the index into blocklist[] */
120 dclist_head emptyblocks; /* empty blocks to use up first instead of
121 * mallocing new blocks */
122
123 /*
124 * Blocks with free space, grouped by the number of free chunks they
125 * contain. Completely full blocks are stored in the 0th element.
126 * Completely empty blocks are stored in emptyblocks or free'd if we have
127 * enough empty blocks already.
128 */
129 dlist_head blocklist[SLAB_BLOCKLIST_COUNT];
130 } SlabContext;
131
132 /*
133 * SlabBlock
134 * Structure of a single slab block.
135 *
136 * slab: pointer back to the owning MemoryContext
137 * nfree: number of chunks on the block which are unallocated
138 * nunused: number of chunks on the block unallocated and not on the block's
139 * freelist.
140 * freehead: linked-list header storing a pointer to the first free chunk on
141 * the block. Subsequent pointers are stored in the chunk's memory. NULL
142 * indicates the end of the list.
143 * unused: pointer to the next chunk which has yet to be used.
144 * node: doubly-linked list node for the context's blocklist
145 */
146 typedef struct SlabBlock
147 {
148 SlabContext *slab; /* owning context */
149 int32 nfree; /* number of chunks on free + unused chunks */
150 int32 nunused; /* number of unused chunks */
151 MemoryChunk *freehead; /* pointer to the first free chunk */
152 MemoryChunk *unused; /* pointer to the next unused chunk */
153 dlist_node node; /* doubly-linked list for blocklist[] */
154 } SlabBlock;
155
156
157 #define Slab_CHUNKHDRSZ sizeof(MemoryChunk)
158 #define SlabChunkGetPointer(chk) \
159 ((void *) (((char *) (chk)) + sizeof(MemoryChunk)))
160
161 /*
162 * SlabBlockGetChunk
163 * Obtain a pointer to the nth (0-based) chunk in the block
164 */
165 #define SlabBlockGetChunk(slab, block, n) \
166 ((MemoryChunk *) ((char *) (block) + Slab_BLOCKHDRSZ \
167 + ((n) * (slab)->fullChunkSize)))
168
169 #if defined(MEMORY_CONTEXT_CHECKING) || defined(USE_ASSERT_CHECKING)
170
171 /*
172 * SlabChunkIndex
173 * Get the 0-based index of how many chunks into the block the given
174 * chunk is.
175 */
176 #define SlabChunkIndex(slab, block, chunk) \
177 (((char *) (chunk) - (char *) SlabBlockGetChunk(slab, block, 0)) / \
178 (slab)->fullChunkSize)
179
180 /*
181 * SlabChunkMod
182 * A MemoryChunk should always be at an address which is a multiple of
183 * fullChunkSize starting from the 0th chunk position. This will return
184 * non-zero if it's not.
185 */
186 #define SlabChunkMod(slab, block, chunk) \
187 (((char *) (chunk) - (char *) SlabBlockGetChunk(slab, block, 0)) % \
188 (slab)->fullChunkSize)
189
190 #endif
191
192 /*
193 * SlabIsValid
194 * True iff set is a valid slab allocation set.
195 */
196 #define SlabIsValid(set) (PointerIsValid(set) && IsA(set, SlabContext))
197
198 /*
199 * SlabBlockIsValid
200 * True iff block is a valid block of slab allocation set.
201 */
202 #define SlabBlockIsValid(block) \
203 (PointerIsValid(block) && SlabIsValid((block)->slab))
204
205 /*
206 * SlabBlocklistIndex
207 * Determine the blocklist index that a block should be in for the given
208 * number of free chunks.
209 */
210 static inline int32
211 SlabBlocklistIndex(SlabContext *slab, int nfree)
212 {
213 int32 index;
214 int32 blocklist_shift = slab->blocklist_shift;
215
216 Assert(nfree >= 0 && nfree <= slab->chunksPerBlock);
217
218 /*
219 * Determine the blocklist index based on the number of free chunks. We
220 * must ensure that 0 free chunks is dedicated to index 0. Everything
221 * else must be >= 1 and < SLAB_BLOCKLIST_COUNT.
222 *
223 * To make this as efficient as possible, we exploit some two's complement
224 * arithmetic where we reverse the sign before bit shifting. This results
225 * in an nfree of 0 using index 0 and anything non-zero staying non-zero.
226 * This is exploiting 0 and -0 being the same in two's complement. When
227 * we're done, we just need to flip the sign back over again for a
228 * positive index.
229 */
230 index = -((-nfree) >> blocklist_shift);
231
232 if (nfree == 0)
233 Assert(index == 0);
234 else
235 Assert(index >= 1 && index < SLAB_BLOCKLIST_COUNT);
236
237 return index;
238 }
239
240 /*
241 * SlabFindNextBlockListIndex
242 * Search blocklist for blocks which have free chunks and return the
243 * index of the blocklist found containing at least 1 block with free
244 * chunks. If no block can be found we return 0.
245 *
246 * Note: We give priority to fuller blocks so that these are filled before
247 * emptier blocks. This is done to increase the chances that mostly-empty
248 * blocks will eventually become completely empty so they can be free'd.
249 */
250 static int32
251 SlabFindNextBlockListIndex(SlabContext *slab)
252 {
253 /* start at 1 as blocklist[0] is for full blocks. */
254 for (int i = 1; i < SLAB_BLOCKLIST_COUNT; i++)
255 {
256 /* return the first found non-empty index */
257 if (!dlist_is_empty(&slab->blocklist[i]))
258 return i;
259 }
260
261 /* no blocks with free space */
262 return 0;
263 }
264
265 /*
266 * SlabGetNextFreeChunk
267 * Return the next free chunk in block and update the block to account
268 * for the returned chunk now being used.
269 */
270 static inline MemoryChunk *
271 SlabGetNextFreeChunk(SlabContext *slab, SlabBlock *block)
272 {
273 MemoryChunk *chunk;
274
275 Assert(block->nfree > 0);
276
277 if (block->freehead != NULL)
278 {
279 chunk = block->freehead;
280
281 /*
282 * Pop the chunk from the linked list of free chunks. The pointer to
283 * the next free chunk is stored in the chunk itself.
284 */
285 VALGRIND_MAKE_MEM_DEFINED(SlabChunkGetPointer(chunk), sizeof(MemoryChunk *));
286 block->freehead = *(MemoryChunk **) SlabChunkGetPointer(chunk);
287
288 /* check nothing stomped on the free chunk's memory */
289 Assert(block->freehead == NULL ||
290 (block->freehead >= SlabBlockGetChunk(slab, block, 0) &&
291 block->freehead <= SlabBlockGetChunk(slab, block, slab->chunksPerBlock - 1) &&
292 SlabChunkMod(slab, block, block->freehead) == 0));
293 }
294 else
295 {
296 Assert(block->nunused > 0);
297
298 chunk = block->unused;
299 block->unused = (MemoryChunk *) (((char *) block->unused) + slab->fullChunkSize);
300 block->nunused--;
301 }
302
303 block->nfree--;
304
305 return chunk;
306 }
307
308 /*
309 * SlabContextCreate
310 * Create a new Slab context.
311 *
312 * parent: parent context, or NULL if top-level context
313 * name: name of context (must be statically allocated)
314 * blockSize: allocation block size
315 * chunkSize: allocation chunk size
316 *
317 * The Slab_CHUNKHDRSZ + MAXALIGN(chunkSize + 1) may not exceed
318 * MEMORYCHUNK_MAX_VALUE.
319 * 'blockSize' may not exceed MEMORYCHUNK_MAX_BLOCKOFFSET.
320 */
321 MemoryContext
322 SlabContextCreate(MemoryContext parent,
323 const char *name,
324 Size blockSize,
325 Size chunkSize)
326 {
327 int chunksPerBlock;
328 Size fullChunkSize;
329 SlabContext *slab;
330 int i;
331
332 /* ensure MemoryChunk's size is properly maxaligned */
333 StaticAssertDecl(Slab_CHUNKHDRSZ == MAXALIGN(Slab_CHUNKHDRSZ),
334 "sizeof(MemoryChunk) is not maxaligned");
335 Assert(blockSize <= MEMORYCHUNK_MAX_BLOCKOFFSET);
336
337 /*
338 * Ensure there's enough space to store the pointer to the next free chunk
339 * in the memory of the (otherwise) unused allocation.
340 */
341 if (chunkSize < sizeof(MemoryChunk *))
342 chunkSize = sizeof(MemoryChunk *);
343
344 /* length of the maxaligned chunk including the chunk header */
345 #ifdef MEMORY_CONTEXT_CHECKING
346 /* ensure there's always space for the sentinel byte */
347 fullChunkSize = Slab_CHUNKHDRSZ + MAXALIGN(chunkSize + 1);
348 #else
349 fullChunkSize = Slab_CHUNKHDRSZ + MAXALIGN(chunkSize);
350 #endif
351
352 Assert(fullChunkSize <= MEMORYCHUNK_MAX_VALUE);
353
354 /* compute the number of chunks that will fit on each block */
355 chunksPerBlock = (blockSize - Slab_BLOCKHDRSZ) / fullChunkSize;
356
357 /* Make sure the block can store at least one chunk. */
358 if (chunksPerBlock == 0)
359 elog(ERROR, "block size %zu for slab is too small for %zu-byte chunks",
360 blockSize, chunkSize);
361
362
363
364 slab = (SlabContext *) malloc(Slab_CONTEXT_HDRSZ(chunksPerBlock));
365 if (slab == NULL)
366 {
367 MemoryContextStats(TopMemoryContext);
368 ereport(ERROR,
369 (errcode(ERRCODE_OUT_OF_MEMORY),
370 errmsg("out of memory"),
371 errdetail("Failed while creating memory context \"%s\".",
372 name)));
373 }
374
375 /*
376 * Avoid writing code that can fail between here and MemoryContextCreate;
377 * we'd leak the header if we ereport in this stretch.
378 */
379
380 /* Fill in SlabContext-specific header fields */
381 slab->chunkSize = (uint32) chunkSize;
382 slab->fullChunkSize = (uint32) fullChunkSize;
383 slab->blockSize = (uint32) blockSize;
384 slab->chunksPerBlock = chunksPerBlock;
385 slab->curBlocklistIndex = 0;
386
387 /*
388 * Compute a shift that guarantees that shifting chunksPerBlock with it is
389 * < SLAB_BLOCKLIST_COUNT - 1. The reason that we subtract 1 from
390 * SLAB_BLOCKLIST_COUNT in this calculation is that we reserve the 0th
391 * blocklist element for blocks which have no free chunks.
392 *
393 * We calculate the number of bits to shift by rather than a divisor to
394 * divide by as performing division each time we need to find the
395 * blocklist index would be much slower.
396 */
397 slab->blocklist_shift = 0;
398 while ((slab->chunksPerBlock >> slab->blocklist_shift) >= (SLAB_BLOCKLIST_COUNT - 1))
399 slab->blocklist_shift++;
400
401 /* initialize the list to store empty blocks to be reused */
402 dclist_init(&slab->emptyblocks);
403
404 /* initialize each blocklist slot */
405 for (i = 0; i < SLAB_BLOCKLIST_COUNT; i++)
406 dlist_init(&slab->blocklist[i]);
407
408 #ifdef MEMORY_CONTEXT_CHECKING
409 /* set the isChunkFree pointer right after the end of the context */
410 slab->isChunkFree = (bool *) ((char *) slab + sizeof(SlabContext));
411 #endif
412
413 /* Finally, do the type-independent part of context creation */
414 MemoryContextCreate((MemoryContext) slab,
415 T_SlabContext,
416 MCTX_SLAB_ID,
417 parent,
418 name);
419
420 return (MemoryContext) slab;
421 }
422
423 /*
424 * SlabReset
425 * Frees all memory which is allocated in the given set.
426 *
427 * The code simply frees all the blocks in the context - we don't keep any
428 * keeper blocks or anything like that.
429 */
430 void
431 SlabReset(MemoryContext context)
432 {
433 SlabContext *slab = (SlabContext *) context;
434 dlist_mutable_iter miter;
435 int i;
436
437 Assert(SlabIsValid(slab));
438
439 #ifdef MEMORY_CONTEXT_CHECKING
440 /* Check for corruption and leaks before freeing */
441 SlabCheck(context);
442 #endif
443
444 /* release any retained empty blocks */
445 dclist_foreach_modify(miter, &slab->emptyblocks)
446 {
447 SlabBlock *block = dlist_container(SlabBlock, node, miter.cur);
448
449 dclist_delete_from(&slab->emptyblocks, miter.cur);
450
451 #ifdef CLOBBER_FREED_MEMORY
452 wipe_mem(block, slab->blockSize);
453 #endif
454 free(block);
455 context->mem_allocated -= slab->blockSize;
456 }
457
458 /* walk over blocklist and free the blocks */
459 for (i = 0; i < SLAB_BLOCKLIST_COUNT; i++)
460 {
461 dlist_foreach_modify(miter, &slab->blocklist[i])
462 {
463 SlabBlock *block = dlist_container(SlabBlock, node, miter.cur);
464
465 dlist_delete(miter.cur);
466
467 #ifdef CLOBBER_FREED_MEMORY
468 wipe_mem(block, slab->blockSize);
469 #endif
470 free(block);
471 context->mem_allocated -= slab->blockSize;
472 }
473 }
474
475 slab->curBlocklistIndex = 0;
476
477 Assert(context->mem_allocated == 0);
478 }
479
480 /*
481 * SlabDelete
482 * Free all memory which is allocated in the given context.
483 */
484 void
485 SlabDelete(MemoryContext context)
486 {
487 /* Reset to release all the SlabBlocks */
488 SlabReset(context);
489 /* And free the context header */
490 free(context);
491 }
492
493 /*
494 * Small helper for allocating a new chunk from a chunk, to avoid duplicating
495 * the code between SlabAlloc() and SlabAllocFromNewBlock().
496 */
497 static inline void *
498 SlabAllocSetupNewChunk(MemoryContext context, SlabBlock *block,
499 MemoryChunk *chunk, Size size)
500 {
501 SlabContext *slab = (SlabContext *) context;
502
503 /*
504 * Check that the chunk pointer is actually somewhere on the block and is
505 * aligned as expected.
506 */
507 Assert(chunk >= SlabBlockGetChunk(slab, block, 0));
508 Assert(chunk <= SlabBlockGetChunk(slab, block, slab->chunksPerBlock - 1));
509 Assert(SlabChunkMod(slab, block, chunk) == 0);
510
511 /* Prepare to initialize the chunk header. */
512 VALGRIND_MAKE_MEM_UNDEFINED(chunk, Slab_CHUNKHDRSZ);
513
514 MemoryChunkSetHdrMask(chunk, block, MAXALIGN(slab->chunkSize), MCTX_SLAB_ID);
515
516 #ifdef MEMORY_CONTEXT_CHECKING
517 chunk->requested_size = size;
518 /* slab mark to catch clobber of "unused" space */
519 Assert(slab->chunkSize < (slab->fullChunkSize - Slab_CHUNKHDRSZ));
520 set_sentinel(MemoryChunkGetPointer(chunk), size);
521 VALGRIND_MAKE_MEM_NOACCESS(((char *) chunk) + Slab_CHUNKHDRSZ +
522 slab->chunkSize,
523 slab->fullChunkSize -
524 (slab->chunkSize + Slab_CHUNKHDRSZ));
525 #endif
526
527 #ifdef RANDOMIZE_ALLOCATED_MEMORY
528 /* fill the allocated space with junk */
529 randomize_mem((char *) MemoryChunkGetPointer(chunk), size);
530 #endif
531
532 /* Disallow access to the chunk header. */
533 VALGRIND_MAKE_MEM_NOACCESS(chunk, Slab_CHUNKHDRSZ);
534
535 return MemoryChunkGetPointer(chunk);
536 }
537
538 pg_noinline
539 static void *
540 SlabAllocFromNewBlock(MemoryContext context, Size size, int flags)
541 {
542 SlabContext *slab = (SlabContext *) context;
543 SlabBlock *block;
544 MemoryChunk *chunk;
545 dlist_head *blocklist;
546 int blocklist_idx;
547
548 /* to save allocating a new one, first check the empty blocks list */
549 if (dclist_count(&slab->emptyblocks) > 0)
550 {
551 dlist_node *node = dclist_pop_head_node(&slab->emptyblocks);
552
553 block = dlist_container(SlabBlock, node, node);
554
555 /*
556 * SlabFree() should have left this block in a valid state with all
557 * chunks free. Ensure that's the case.
558 */
559 Assert(block->nfree == slab->chunksPerBlock);
560
561 /* fetch the next chunk from this block */
562 chunk = SlabGetNextFreeChunk(slab, block);
563 }
564 else
565 {
566 block = (SlabBlock *) malloc(slab->blockSize);
567
568 if (unlikely(block == NULL))
569 return MemoryContextAllocationFailure(context, size, flags);
570
571 block->slab = slab;
572 context->mem_allocated += slab->blockSize;
573
574 /* use the first chunk in the new block */
575 chunk = SlabBlockGetChunk(slab, block, 0);
576
577 block->nfree = slab->chunksPerBlock - 1;
578 block->unused = SlabBlockGetChunk(slab, block, 1);
579 block->freehead = NULL;
580 block->nunused = slab->chunksPerBlock - 1;
581 }
582
583 /* find the blocklist element for storing blocks with 1 used chunk */
584 blocklist_idx = SlabBlocklistIndex(slab, block->nfree);
585 blocklist = &slab->blocklist[blocklist_idx];
586
587 /* this better be empty. We just added a block thinking it was */
588 Assert(dlist_is_empty(blocklist));
589
590 dlist_push_head(blocklist, &block->node);
591
592 slab->curBlocklistIndex = blocklist_idx;
593
594 return SlabAllocSetupNewChunk(context, block, chunk, size);
595 }
596
597 /*
598 * SlabAllocInvalidSize
599 * Handle raising an ERROR for an invalid size request. We don't do this
600 * in slab alloc as calling the elog functions would force the compiler
601 * to setup the stack frame in SlabAlloc. For performance reasons, we
602 * want to avoid that.
603 */
604 pg_noinline
605 pg_noreturn
606 static void
607 SlabAllocInvalidSize(MemoryContext context, Size size)
608 {
609 SlabContext *slab = (SlabContext *) context;
610
611 elog(ERROR, "unexpected alloc chunk size %zu (expected %u)", size,
612 slab->chunkSize);
613 }
614
615 /*
616 * SlabAlloc
617 * Returns a pointer to a newly allocated memory chunk or raises an ERROR
618 * on allocation failure, or returns NULL when flags contains
619 * MCXT_ALLOC_NO_OOM. 'size' must be the same size as was specified
620 * during SlabContextCreate().
621 *
622 * This function should only contain the most common code paths. Everything
623 * else should be in pg_noinline helper functions, thus avoiding the overhead
624 * of creating a stack frame for the common cases. Allocating memory is often
625 * a bottleneck in many workloads, so avoiding stack frame setup is
626 * worthwhile. Helper functions should always directly return the newly
627 * allocated memory so that we can just return that address directly as a tail
628 * call.
629 */
630 void *
631 SlabAlloc(MemoryContext context, Size size, int flags)
632 {
633 SlabContext *slab = (SlabContext *) context;
634 SlabBlock *block;
635 MemoryChunk *chunk;
636
637 Assert(SlabIsValid(slab));
638
639 /* sanity check that this is pointing to a valid blocklist */
640 Assert(slab->curBlocklistIndex >= 0);
641 Assert(slab->curBlocklistIndex <= SlabBlocklistIndex(slab, slab->chunksPerBlock));
642
643 /*
644 * Make sure we only allow correct request size. This doubles as the
645 * MemoryContextCheckSize check.
646 */
647 if (unlikely(size != slab->chunkSize))
648 SlabAllocInvalidSize(context, size);
649
650 if (unlikely(slab->curBlocklistIndex == 0))
651 {
652 /*
653 * Handle the case when there are no partially filled blocks
654 * available. This happens either when the last allocation took the
655 * last chunk in the block, or when SlabFree() free'd the final block.
656 */
657 return SlabAllocFromNewBlock(context, size, flags);
658 }
659 else
660 {
661 dlist_head *blocklist = &slab->blocklist[slab->curBlocklistIndex];
662 int new_blocklist_idx;
663
664 Assert(!dlist_is_empty(blocklist));
665
666 /* grab the block from the blocklist */
667 block = dlist_head_element(SlabBlock, node, blocklist);
668
669 /* make sure we actually got a valid block, with matching nfree */
670 Assert(block != NULL);
671 Assert(slab->curBlocklistIndex == SlabBlocklistIndex(slab, block->nfree));
672 Assert(block->nfree > 0);
673
674 /* fetch the next chunk from this block */
675 chunk = SlabGetNextFreeChunk(slab, block);
676
677 /* get the new blocklist index based on the new free chunk count */
678 new_blocklist_idx = SlabBlocklistIndex(slab, block->nfree);
679
680 /*
681 * Handle the case where the blocklist index changes. This also deals
682 * with blocks becoming full as only full blocks go at index 0.
683 */
684 if (unlikely(slab->curBlocklistIndex != new_blocklist_idx))
685 {
686 dlist_delete_from(blocklist, &block->node);
687 dlist_push_head(&slab->blocklist[new_blocklist_idx], &block->node);
688
689 if (dlist_is_empty(blocklist))
690 slab->curBlocklistIndex = SlabFindNextBlockListIndex(slab);
691 }
692 }
693
694 return SlabAllocSetupNewChunk(context, block, chunk, size);
695 }
696
697 /*
698 * SlabFree
699 * Frees allocated memory; memory is removed from the slab.
700 */
701 void
702 SlabFree(void *pointer)
703 {
704 MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
705 SlabBlock *block;
706 SlabContext *slab;
707 int curBlocklistIdx;
708 int newBlocklistIdx;
709
710 /* Allow access to the chunk header. */
711 VALGRIND_MAKE_MEM_DEFINED(chunk, Slab_CHUNKHDRSZ);
712
713 block = MemoryChunkGetBlock(chunk);
714
715 /*
716 * For speed reasons we just Assert that the referenced block is good.
717 * Future field experience may show that this Assert had better become a
718 * regular runtime test-and-elog check.
719 */
720 Assert(SlabBlockIsValid(block));
721 slab = block->slab;
722
723 #ifdef MEMORY_CONTEXT_CHECKING
724 /* See comments in AllocSetFree about uses of ERROR and WARNING here */
725 /* Test for previously-freed chunk */
726 if (unlikely(chunk->requested_size == InvalidAllocSize))
727 elog(ERROR, "detected double pfree in %s %p",
728 slab->header.name, chunk);
729 /* Test for someone scribbling on unused space in chunk */
730 Assert(slab->chunkSize < (slab->fullChunkSize - Slab_CHUNKHDRSZ));
731 if (!sentinel_ok(pointer, slab->chunkSize))
732 elog(WARNING, "detected write past chunk end in %s %p",
733 slab->header.name, chunk);
734 /* Reset requested_size to InvalidAllocSize in free chunks */
735 chunk->requested_size = InvalidAllocSize;
736 #endif
737
738 /* push this chunk onto the head of the block's free list */
739 *(MemoryChunk **) pointer = block->freehead;
740 block->freehead = chunk;
741
742 block->nfree++;
743
744 Assert(block->nfree > 0);
745 Assert(block->nfree <= slab->chunksPerBlock);
746
747 #ifdef CLOBBER_FREED_MEMORY
748 /* don't wipe the free list MemoryChunk pointer stored in the chunk */
749 wipe_mem((char *) pointer + sizeof(MemoryChunk *),
750 slab->chunkSize - sizeof(MemoryChunk *));
751 #endif
752
753 curBlocklistIdx = SlabBlocklistIndex(slab, block->nfree - 1);
754 newBlocklistIdx = SlabBlocklistIndex(slab, block->nfree);
755
756 /*
757 * Check if the block needs to be moved to another element on the
758 * blocklist based on it now having 1 more free chunk.
759 */
760 if (unlikely(curBlocklistIdx != newBlocklistIdx))
761 {
762 /* do the move */
763 dlist_delete_from(&slab->blocklist[curBlocklistIdx], &block->node);
764 dlist_push_head(&slab->blocklist[newBlocklistIdx], &block->node);
765
766 /*
767 * The blocklist[curBlocklistIdx] may now be empty or we may now be
768 * able to use a lower-element blocklist. We'll need to redetermine
769 * what the slab->curBlocklistIndex is if the current blocklist was
770 * changed or if a lower element one was changed. We must ensure we
771 * use the list with the fullest block(s).
772 */
773 if (slab->curBlocklistIndex >= curBlocklistIdx)
774 {
775 slab->curBlocklistIndex = SlabFindNextBlockListIndex(slab);
776
777 /*
778 * We know there must be a block with at least 1 unused chunk as
779 * we just pfree'd one. Ensure curBlocklistIndex reflects this.
780 */
781 Assert(slab->curBlocklistIndex > 0);
782 }
783 }
784
785 /* Handle when a block becomes completely empty */
786 if (unlikely(block->nfree == slab->chunksPerBlock))
787 {
788 /* remove the block */
789 dlist_delete_from(&slab->blocklist[newBlocklistIdx], &block->node);
790
791 /*
792 * To avoid thrashing malloc/free, we keep a list of empty blocks that
793 * we can reuse again instead of having to malloc a new one.
794 */
795 if (dclist_count(&slab->emptyblocks) < SLAB_MAXIMUM_EMPTY_BLOCKS)
796 dclist_push_head(&slab->emptyblocks, &block->node);
797 else
798 {
799 /*
800 * When we have enough empty blocks stored already, we actually
801 * free the block.
802 */
803 #ifdef CLOBBER_FREED_MEMORY
804 wipe_mem(block, slab->blockSize);
805 #endif
806 free(block);
807 slab->header.mem_allocated -= slab->blockSize;
808 }
809
810 /*
811 * Check if we need to reset the blocklist index. This is required
812 * when the blocklist this block is on has become completely empty.
813 */
814 if (slab->curBlocklistIndex == newBlocklistIdx &&
815 dlist_is_empty(&slab->blocklist[newBlocklistIdx]))
816 slab->curBlocklistIndex = SlabFindNextBlockListIndex(slab);
817 }
818 }
819
820 /*
821 * SlabRealloc
822 * Change the allocated size of a chunk.
823 *
824 * As Slab is designed for allocating equally-sized chunks of memory, it can't
825 * do an actual chunk size change. We try to be gentle and allow calls with
826 * exactly the same size, as in that case we can simply return the same
827 * chunk. When the size differs, we throw an error.
828 *
829 * We could also allow requests with size < chunkSize. That however seems
830 * rather pointless - Slab is meant for chunks of constant size, and moreover
831 * realloc is usually used to enlarge the chunk.
832 */
833 void *
834 SlabRealloc(void *pointer, Size size, int flags)
835 {
836 MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
837 SlabBlock *block;
838 SlabContext *slab;
839
840 /* Allow access to the chunk header. */
841 VALGRIND_MAKE_MEM_DEFINED(chunk, Slab_CHUNKHDRSZ);
842
843 block = MemoryChunkGetBlock(chunk);
844
845 /* Disallow access to the chunk header. */
846 VALGRIND_MAKE_MEM_NOACCESS(chunk, Slab_CHUNKHDRSZ);
847
848 /*
849 * Try to verify that we have a sane block pointer: the block header
850 * should reference a slab context. (We use a test-and-elog, not just
851 * Assert, because it seems highly likely that we're here in error in the
852 * first place.)
853 */
854 if (!SlabBlockIsValid(block))
855 elog(ERROR, "could not find block containing chunk %p", chunk);
856 slab = block->slab;
857
858 /* can't do actual realloc with slab, but let's try to be gentle */
859 if (size == slab->chunkSize)
860 return pointer;
861
862 elog(ERROR, "slab allocator does not support realloc()");
863 return NULL; /* keep compiler quiet */
864 }
865
866 /*
867 * SlabGetChunkContext
868 * Return the MemoryContext that 'pointer' belongs to.
869 */
870 MemoryContext
871 SlabGetChunkContext(void *pointer)
872 {
873 MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
874 SlabBlock *block;
875
876 /* Allow access to the chunk header. */
877 VALGRIND_MAKE_MEM_DEFINED(chunk, Slab_CHUNKHDRSZ);
878
879 block = MemoryChunkGetBlock(chunk);
880
881 /* Disallow access to the chunk header. */
882 VALGRIND_MAKE_MEM_NOACCESS(chunk, Slab_CHUNKHDRSZ);
883
884 Assert(SlabBlockIsValid(block));
885
886 return &block->slab->header;
887 }
888
889 /*
890 * SlabGetChunkSpace
891 * Given a currently-allocated chunk, determine the total space
892 * it occupies (including all memory-allocation overhead).
893 */
894 Size
895 SlabGetChunkSpace(void *pointer)
896 {
897 MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
898 SlabBlock *block;
899 SlabContext *slab;
900
901 /* Allow access to the chunk header. */
902 VALGRIND_MAKE_MEM_DEFINED(chunk, Slab_CHUNKHDRSZ);
903
904 block = MemoryChunkGetBlock(chunk);
905
906 /* Disallow access to the chunk header. */
907 VALGRIND_MAKE_MEM_NOACCESS(chunk, Slab_CHUNKHDRSZ);
908
909 Assert(SlabBlockIsValid(block));
910 slab = block->slab;
911
912 return slab->fullChunkSize;
913 }
914
915 /*
916 * SlabIsEmpty
917 * Is the slab empty of any allocated space?
918 */
919 bool
920 SlabIsEmpty(MemoryContext context)
921 {
922 Assert(SlabIsValid((SlabContext *) context));
923
924 return (context->mem_allocated == 0);
925 }
926
927 /*
928 * SlabStats
929 * Compute stats about memory consumption of a Slab context.
930 *
931 * printfunc: if not NULL, pass a human-readable stats string to this.
932 * passthru: pass this pointer through to printfunc.
933 * totals: if not NULL, add stats about this context into *totals.
934 * print_to_stderr: print stats to stderr if true, elog otherwise.
935 */
936 void
937 SlabStats(MemoryContext context,
938 MemoryStatsPrintFunc printfunc, void *passthru,
939 MemoryContextCounters *totals,
940 bool print_to_stderr)
941 {
942 SlabContext *slab = (SlabContext *) context;
943 Size nblocks = 0;
944 Size freechunks = 0;
945 Size totalspace;
946 Size freespace = 0;
947 int i;
948
949 Assert(SlabIsValid(slab));
950
951 /* Include context header in totalspace */
952 totalspace = Slab_CONTEXT_HDRSZ(slab->chunksPerBlock);
953
954 /* Add the space consumed by blocks in the emptyblocks list */
955 totalspace += dclist_count(&slab->emptyblocks) * slab->blockSize;
956
957 for (i = 0; i < SLAB_BLOCKLIST_COUNT; i++)
958 {
959 dlist_iter iter;
960
961 dlist_foreach(iter, &slab->blocklist[i])
962 {
963 SlabBlock *block = dlist_container(SlabBlock, node, iter.cur);
964
965 nblocks++;
966 totalspace += slab->blockSize;
967 freespace += slab->fullChunkSize * block->nfree;
968 freechunks += block->nfree;
969 }
970 }
971
972 if (printfunc)
973 {
974 char stats_string[200];
975
976 /* XXX should we include free chunks on empty blocks? */
977 snprintf(stats_string, sizeof(stats_string),
978 "%zu total in %zu blocks; %u empty blocks; %zu free (%zu chunks); %zu used",
979 totalspace, nblocks, dclist_count(&slab->emptyblocks),
980 freespace, freechunks, totalspace - freespace);
981 printfunc(context, passthru, stats_string, print_to_stderr);
982 }
983
984 if (totals)
985 {
986 totals->nblocks += nblocks;
987 totals->freechunks += freechunks;
988 totals->totalspace += totalspace;
989 totals->freespace += freespace;
990 }
991 }
992
993
994 #ifdef MEMORY_CONTEXT_CHECKING
995
996 /*
997 * SlabCheck
998 * Walk through all blocks looking for inconsistencies.
999 *
1000 * NOTE: report errors as WARNING, *not* ERROR or FATAL. Otherwise you'll
1001 * find yourself in an infinite loop when trouble occurs, because this
1002 * routine will be entered again when elog cleanup tries to release memory!
1003 */
1004 void
1005 SlabCheck(MemoryContext context)
1006 {
1007 SlabContext *slab = (SlabContext *) context;
1008 int i;
1009 int nblocks = 0;
1010 const char *name = slab->header.name;
1011 dlist_iter iter;
1012
1013 Assert(SlabIsValid(slab));
1014 Assert(slab->chunksPerBlock > 0);
1015
1016 /*
1017 * Have a look at the empty blocks. These should have all their chunks
1018 * marked as free. Ensure that's the case.
1019 */
1020 dclist_foreach(iter, &slab->emptyblocks)
1021 {
1022 SlabBlock *block = dlist_container(SlabBlock, node, iter.cur);
1023
1024 if (block->nfree != slab->chunksPerBlock)
1025 elog(WARNING, "problem in slab %s: empty block %p should have %d free chunks but has %d chunks free",
1026 name, block, slab->chunksPerBlock, block->nfree);
1027 }
1028
1029 /* walk the non-empty block lists */
1030 for (i = 0; i < SLAB_BLOCKLIST_COUNT; i++)
1031 {
1032 int j,
1033 nfree;
1034
1035 /* walk all blocks on this blocklist */
1036 dlist_foreach(iter, &slab->blocklist[i])
1037 {
1038 SlabBlock *block = dlist_container(SlabBlock, node, iter.cur);
1039 MemoryChunk *cur_chunk;
1040
1041 /*
1042 * Make sure the number of free chunks (in the block header)
1043 * matches the position in the blocklist.
1044 */
1045 if (SlabBlocklistIndex(slab, block->nfree) != i)
1046 elog(WARNING, "problem in slab %s: block %p is on blocklist %d but should be on blocklist %d",
1047 name, block, i, SlabBlocklistIndex(slab, block->nfree));
1048
1049 /* make sure the block is not empty */
1050 if (block->nfree >= slab->chunksPerBlock)
1051 elog(WARNING, "problem in slab %s: empty block %p incorrectly stored on blocklist element %d",
1052 name, block, i);
1053
1054 /* make sure the slab pointer correctly points to this context */
1055 if (block->slab != slab)
1056 elog(WARNING, "problem in slab %s: bogus slab link in block %p",
1057 name, block);
1058
1059 /* reset the array of free chunks for this block */
1060 memset(slab->isChunkFree, 0, (slab->chunksPerBlock * sizeof(bool)));
1061 nfree = 0;
1062
1063 /* walk through the block's free list chunks */
1064 cur_chunk = block->freehead;
1065 while (cur_chunk != NULL)
1066 {
1067 int chunkidx = SlabChunkIndex(slab, block, cur_chunk);
1068
1069 /*
1070 * Ensure the free list link points to something on the block
1071 * at an address aligned according to the full chunk size.
1072 */
1073 if (cur_chunk < SlabBlockGetChunk(slab, block, 0) ||
1074 cur_chunk > SlabBlockGetChunk(slab, block, slab->chunksPerBlock - 1) ||
1075 SlabChunkMod(slab, block, cur_chunk) != 0)
1076 elog(WARNING, "problem in slab %s: bogus free list link %p in block %p",
1077 name, cur_chunk, block);
1078
1079 /* count the chunk and mark it free on the free chunk array */
1080 nfree++;
1081 slab->isChunkFree[chunkidx] = true;
1082
1083 /* read pointer of the next free chunk */
1084 VALGRIND_MAKE_MEM_DEFINED(MemoryChunkGetPointer(cur_chunk), sizeof(MemoryChunk *));
1085 cur_chunk = *(MemoryChunk **) SlabChunkGetPointer(cur_chunk);
1086 }
1087
1088 /* check that the unused pointer matches what nunused claims */
1089 if (SlabBlockGetChunk(slab, block, slab->chunksPerBlock - block->nunused) !=
1090 block->unused)
1091 elog(WARNING, "problem in slab %s: mismatch detected between nunused chunks and unused pointer in block %p",
1092 name, block);
1093
1094 /*
1095 * count the remaining free chunks that have yet to make it onto
1096 * the block's free list.
1097 */
1098 cur_chunk = block->unused;
1099 for (j = 0; j < block->nunused; j++)
1100 {
1101 int chunkidx = SlabChunkIndex(slab, block, cur_chunk);
1102
1103
1104 /* count the chunk as free and mark it as so in the array */
1105 nfree++;
1106 if (chunkidx < slab->chunksPerBlock)
1107 slab->isChunkFree[chunkidx] = true;
1108
1109 /* move forward 1 chunk */
1110 cur_chunk = (MemoryChunk *) (((char *) cur_chunk) + slab->fullChunkSize);
1111 }
1112
1113 for (j = 0; j < slab->chunksPerBlock; j++)
1114 {
1115 if (!slab->isChunkFree[j])
1116 {
1117 MemoryChunk *chunk = SlabBlockGetChunk(slab, block, j);
1118 SlabBlock *chunkblock;
1119
1120 /* Allow access to the chunk header. */
1121 VALGRIND_MAKE_MEM_DEFINED(chunk, Slab_CHUNKHDRSZ);
1122
1123 chunkblock = (SlabBlock *) MemoryChunkGetBlock(chunk);
1124
1125 /* Disallow access to the chunk header. */
1126 VALGRIND_MAKE_MEM_NOACCESS(chunk, Slab_CHUNKHDRSZ);
1127
1128 /*
1129 * check the chunk's blockoffset correctly points back to
1130 * the block
1131 */
1132 if (chunkblock != block)
1133 elog(WARNING, "problem in slab %s: bogus block link in block %p, chunk %p",
1134 name, block, chunk);
1135
1136 /* check the sentinel byte is intact */
1137 Assert(slab->chunkSize < (slab->fullChunkSize - Slab_CHUNKHDRSZ));
1138 if (!sentinel_ok(chunk, Slab_CHUNKHDRSZ + slab->chunkSize))
1139 elog(WARNING, "problem in slab %s: detected write past chunk end in block %p, chunk %p",
1140 name, block, chunk);
1141 }
1142 }
1143
1144 /*
1145 * Make sure we got the expected number of free chunks (as tracked
1146 * in the block header).
1147 */
1148 if (nfree != block->nfree)
1149 elog(WARNING, "problem in slab %s: nfree in block %p is %d but %d chunk were found as free",
1150 name, block, block->nfree, nfree);
1151
1152 nblocks++;
1153 }
1154 }
1155
1156 /* the stored empty blocks are tracked in mem_allocated too */
1157 nblocks += dclist_count(&slab->emptyblocks);
1158
1159 Assert(nblocks * slab->blockSize == context->mem_allocated);
1160 }
1161
1162 #endif /* MEMORY_CONTEXT_CHECKING */