Age Owner TLA Line data Source code
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-2023, 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_memorychunk.h"
75 : #include "utils/memutils_internal.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 : Size chunkSize; /* the requested (non-aligned) chunk size */
108 : Size fullChunkSize; /* chunk size with chunk header and alignment */
109 : Size 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
110 drowley 211 GNC 9560935 : SlabBlocklistIndex(SlabContext *slab, int nfree)
212 : {
213 : int32 index;
214 9560935 : int32 blocklist_shift = slab->blocklist_shift;
215 :
216 9560935 : 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 9560935 : index = -((-nfree) >> blocklist_shift);
231 :
232 9560935 : if (nfree == 0)
233 46454 : Assert(index == 0);
234 : else
235 9514481 : Assert(index >= 1 && index < SLAB_BLOCKLIST_COUNT);
236 :
237 9560935 : 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 106553 : SlabFindNextBlockListIndex(SlabContext *slab)
252 : {
253 : /* start at 1 as blocklist[0] is for full blocks. */
254 175236 : for (int i = 1; i < SLAB_BLOCKLIST_COUNT; i++)
255 : {
256 : /* return the first found non-empty index */
257 144636 : if (!dlist_is_empty(&slab->blocklist[i]))
258 75953 : return i;
259 : }
260 :
261 : /* no blocks with free space */
262 30600 : 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 1915610 : SlabGetNextFreeChunk(SlabContext *slab, SlabBlock *block)
272 : {
273 : MemoryChunk *chunk;
274 :
275 1915610 : Assert(block->nfree > 0);
276 :
277 1915610 : if (block->freehead != NULL)
278 : {
279 1736375 : 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 1736375 : block->freehead = *(MemoryChunk **) SlabChunkGetPointer(chunk);
287 :
288 : /* check nothing stomped on the free chunk's memory */
289 1736375 : 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 179235 : Assert(block->nunused > 0);
297 :
298 179235 : chunk = block->unused;
299 179235 : block->unused = (MemoryChunk *) (((char *) block->unused) + slab->fullChunkSize);
300 179235 : block->nunused--;
301 : }
302 :
303 1915610 : block->nfree--;
304 :
305 1915610 : 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 MAXALIGN(chunkSize) may not exceed MEMORYCHUNK_MAX_VALUE
318 : */
319 : MemoryContext
2232 andres 320 GIC 1646 : SlabContextCreate(MemoryContext parent,
321 : const char *name,
322 : Size blockSize,
323 : Size chunkSize)
324 : {
325 : int chunksPerBlock;
326 : Size fullChunkSize;
327 : SlabContext *slab;
328 : int i;
329 :
330 : /* ensure MemoryChunk's size is properly maxaligned */
331 : StaticAssertDecl(Slab_CHUNKHDRSZ == MAXALIGN(Slab_CHUNKHDRSZ),
332 : "sizeof(MemoryChunk) is not maxaligned");
223 drowley 333 GNC 1646 : Assert(MAXALIGN(chunkSize) <= MEMORYCHUNK_MAX_VALUE);
334 :
110 drowley 335 ECB : /*
336 : * Ensure there's enough space to store the pointer to the next free chunk
337 : * in the memory of the (otherwise) unused allocation.
338 : */
110 drowley 339 GNC 1646 : if (chunkSize < sizeof(MemoryChunk *))
110 drowley 340 UNC 0 : chunkSize = sizeof(MemoryChunk *);
341 :
342 : /* length of the maxaligned chunk including the chunk header */
343 : #ifdef MEMORY_CONTEXT_CHECKING
344 : /* ensure there's always space for the sentinel byte */
214 drowley 345 GNC 1646 : fullChunkSize = Slab_CHUNKHDRSZ + MAXALIGN(chunkSize + 1);
346 : #else
347 : fullChunkSize = Slab_CHUNKHDRSZ + MAXALIGN(chunkSize);
214 drowley 348 ECB : #endif
349 :
350 : /* compute the number of chunks that will fit on each block */
222 drowley 351 GNC 1646 : chunksPerBlock = (blockSize - Slab_BLOCKHDRSZ) / fullChunkSize;
352 :
353 : /* Make sure the block can store at least one chunk. */
110 354 1646 : if (chunksPerBlock == 0)
110 drowley 355 UNC 0 : elog(ERROR, "block size %zu for slab is too small for %zu-byte chunks",
356 : blockSize, chunkSize);
357 :
358 :
359 :
110 drowley 360 GNC 1646 : slab = (SlabContext *) malloc(Slab_CONTEXT_HDRSZ(chunksPerBlock));
1943 tgl 361 CBC 1646 : if (slab == NULL)
362 : {
1943 tgl 363 LBC 0 : MemoryContextStats(TopMemoryContext);
1943 tgl 364 UIC 0 : ereport(ERROR,
1943 tgl 365 ECB : (errcode(ERRCODE_OUT_OF_MEMORY),
366 : errmsg("out of memory"),
367 : errdetail("Failed while creating memory context \"%s\".",
368 : name)));
369 : }
370 :
371 : /*
372 : * Avoid writing code that can fail between here and MemoryContextCreate;
373 : * we'd leak the header if we ereport in this stretch.
374 : */
375 :
376 : /* Fill in SlabContext-specific header fields */
2232 andres 377 GIC 1646 : slab->chunkSize = chunkSize;
378 1646 : slab->fullChunkSize = fullChunkSize;
1943 tgl 379 CBC 1646 : slab->blockSize = blockSize;
2232 andres 380 GIC 1646 : slab->chunksPerBlock = chunksPerBlock;
110 drowley 381 GNC 1646 : slab->curBlocklistIndex = 0;
382 :
383 : /*
384 : * Compute a shift that guarantees that shifting chunksPerBlock with it is
385 : * < SLAB_BLOCKLIST_COUNT - 1. The reason that we subtract 1 from
386 : * SLAB_BLOCKLIST_COUNT in this calculation is that we reserve the 0th
387 : * blocklist element for blocks which have no free chunks.
388 : *
389 : * We calculate the number of bits to shift by rather than a divisor to
390 : * divide by as performing division each time we need to find the
391 : * blocklist index would be much slower.
392 : */
393 1646 : slab->blocklist_shift = 0;
394 9876 : while ((slab->chunksPerBlock >> slab->blocklist_shift) >= (SLAB_BLOCKLIST_COUNT - 1))
395 8230 : slab->blocklist_shift++;
396 :
397 : /* initialize the list to store empty blocks to be reused */
398 1646 : dclist_init(&slab->emptyblocks);
399 :
400 : /* initialize each blocklist slot */
401 6584 : for (i = 0; i < SLAB_BLOCKLIST_COUNT; i++)
402 4938 : dlist_init(&slab->blocklist[i]);
403 :
404 : #ifdef MEMORY_CONTEXT_CHECKING
405 : /* set the isChunkFree pointer right after the end of the context */
406 1646 : slab->isChunkFree = (bool *) ((char *) slab + sizeof(SlabContext));
407 : #endif
408 :
409 : /* Finally, do the type-independent part of context creation */
1943 tgl 410 GIC 1646 : MemoryContextCreate((MemoryContext) slab,
411 : T_SlabContext,
412 : MCTX_SLAB_ID,
1943 tgl 413 ECB : parent,
414 : name);
415 :
1943 tgl 416 GIC 1646 : return (MemoryContext) slab;
2232 andres 417 ECB : }
418 :
419 : /*
420 : * SlabReset
421 : * Frees all memory which is allocated in the given set.
422 : *
423 : * The code simply frees all the blocks in the context - we don't keep any
424 : * keeper blocks or anything like that.
425 : */
426 : void
2232 andres 427 GIC 1390 : SlabReset(MemoryContext context)
2232 andres 428 ECB : {
181 tgl 429 GNC 1390 : SlabContext *slab = (SlabContext *) context;
430 : dlist_mutable_iter miter;
431 : int i;
2232 andres 432 ECB :
163 peter 433 GNC 1390 : Assert(SlabIsValid(slab));
434 :
435 : #ifdef MEMORY_CONTEXT_CHECKING
436 : /* Check for corruption and leaks before freeing */
2232 andres 437 GIC 1390 : SlabCheck(context);
438 : #endif
2232 andres 439 ECB :
440 : /* release any retained empty blocks */
110 drowley 441 GNC 2098 : dclist_foreach_modify(miter, &slab->emptyblocks)
2232 andres 442 ECB : {
110 drowley 443 GNC 708 : SlabBlock *block = dlist_container(SlabBlock, node, miter.cur);
444 :
445 708 : dclist_delete_from(&slab->emptyblocks, miter.cur);
446 :
447 : #ifdef CLOBBER_FREED_MEMORY
448 708 : wipe_mem(block, slab->blockSize);
449 : #endif
450 708 : free(block);
451 708 : context->mem_allocated -= slab->blockSize;
452 : }
453 :
454 : /* walk over blocklist and free the blocks */
455 5560 : for (i = 0; i < SLAB_BLOCKLIST_COUNT; i++)
456 : {
457 4222 : dlist_foreach_modify(miter, &slab->blocklist[i])
2232 andres 458 ECB : {
2232 andres 459 GIC 52 : SlabBlock *block = dlist_container(SlabBlock, node, miter.cur);
2232 andres 460 ECB :
2232 andres 461 GIC 52 : dlist_delete(miter.cur);
462 :
463 : #ifdef CLOBBER_FREED_MEMORY
464 52 : wipe_mem(block, slab->blockSize);
465 : #endif
466 52 : free(block);
1116 jdavis 467 52 : context->mem_allocated -= slab->blockSize;
468 : }
469 : }
470 :
110 drowley 471 GNC 1390 : slab->curBlocklistIndex = 0;
472 :
1116 jdavis 473 CBC 1390 : Assert(context->mem_allocated == 0);
2232 andres 474 GIC 1390 : }
475 :
476 : /*
477 : * SlabDelete
478 : * Free all memory which is allocated in the given context.
479 : */
480 : void
481 1390 : SlabDelete(MemoryContext context)
482 : {
483 : /* Reset to release all the SlabBlocks */
484 1390 : SlabReset(context);
485 : /* And free the context header */
1943 tgl 486 CBC 1390 : free(context);
2232 andres 487 GIC 1390 : }
488 :
489 : /*
490 : * SlabAlloc
491 : * Returns a pointer to allocated memory of given size or NULL if
2232 andres 492 ECB : * request could not be completed; memory is added to the slab.
2232 andres 493 EUB : */
494 : void *
2232 andres 495 GIC 1918429 : SlabAlloc(MemoryContext context, Size size)
496 : {
181 tgl 497 GNC 1918429 : SlabContext *slab = (SlabContext *) context;
2232 andres 498 ECB : SlabBlock *block;
499 : MemoryChunk *chunk;
500 :
163 peter 501 GNC 1918429 : Assert(SlabIsValid(slab));
502 :
503 : /* sanity check that this is pointing to a valid blocklist */
110 drowley 504 1918429 : Assert(slab->curBlocklistIndex >= 0);
505 1918429 : Assert(slab->curBlocklistIndex <= SlabBlocklistIndex(slab, slab->chunksPerBlock));
506 :
2232 andres 507 ECB : /* make sure we only allow correct request size */
110 drowley 508 GNC 1918429 : if (unlikely(size != slab->chunkSize))
2232 andres 509 UIC 0 : elog(ERROR, "unexpected alloc chunk size %zu (expected %zu)",
510 : size, slab->chunkSize);
511 :
512 : /*
513 : * Handle the case when there are no partially filled blocks available.
514 : * SlabFree() will have updated the curBlocklistIndex setting it to zero
515 : * to indicate that it has freed the final block. Also later in
516 : * SlabAlloc() we will set the curBlocklistIndex to zero if we end up
517 : * filling the final block.
518 : */
110 drowley 519 GNC 1918429 : if (unlikely(slab->curBlocklistIndex == 0))
520 : {
521 : dlist_head *blocklist;
522 : int blocklist_idx;
523 :
524 : /* to save allocating a new one, first check the empty blocks list */
525 30642 : if (dclist_count(&slab->emptyblocks) > 0)
110 drowley 526 ECB : {
110 drowley 527 GNC 27823 : dlist_node *node = dclist_pop_head_node(&slab->emptyblocks);
528 :
529 27823 : block = dlist_container(SlabBlock, node, node);
530 :
531 : /*
532 : * SlabFree() should have left this block in a valid state with
533 : * all chunks free. Ensure that's the case.
534 : */
535 27823 : Assert(block->nfree == slab->chunksPerBlock);
536 :
537 : /* fetch the next chunk from this block */
538 27823 : chunk = SlabGetNextFreeChunk(slab, block);
539 : }
540 : else
541 : {
542 2819 : block = (SlabBlock *) malloc(slab->blockSize);
543 :
544 2819 : if (unlikely(block == NULL))
110 drowley 545 UNC 0 : return NULL;
546 :
110 drowley 547 GNC 2819 : block->slab = slab;
548 2819 : context->mem_allocated += slab->blockSize;
549 :
550 : /* use the first chunk in the new block */
551 2819 : chunk = SlabBlockGetChunk(slab, block, 0);
552 :
553 2819 : block->nfree = slab->chunksPerBlock - 1;
554 2819 : block->unused = SlabBlockGetChunk(slab, block, 1);
555 2819 : block->freehead = NULL;
556 2819 : block->nunused = slab->chunksPerBlock - 1;
557 : }
558 :
559 : /* find the blocklist element for storing blocks with 1 used chunk */
560 30642 : blocklist_idx = SlabBlocklistIndex(slab, block->nfree);
561 30642 : blocklist = &slab->blocklist[blocklist_idx];
2232 andres 562 ECB :
563 : /* this better be empty. We just added a block thinking it was */
110 drowley 564 GNC 30642 : Assert(dlist_is_empty(blocklist));
2232 andres 565 ECB :
110 drowley 566 GNC 30642 : dlist_push_head(blocklist, &block->node);
567 :
568 30642 : slab->curBlocklistIndex = blocklist_idx;
569 : }
570 : else
571 : {
572 1887787 : dlist_head *blocklist = &slab->blocklist[slab->curBlocklistIndex];
573 : int new_blocklist_idx;
574 :
575 1887787 : Assert(!dlist_is_empty(blocklist));
576 :
577 : /* grab the block from the blocklist */
578 1887787 : block = dlist_head_element(SlabBlock, node, blocklist);
579 :
580 : /* make sure we actually got a valid block, with matching nfree */
581 1887787 : Assert(block != NULL);
582 1887787 : Assert(slab->curBlocklistIndex == SlabBlocklistIndex(slab, block->nfree));
583 1887787 : Assert(block->nfree > 0);
584 :
585 : /* fetch the next chunk from this block */
586 1887787 : chunk = SlabGetNextFreeChunk(slab, block);
587 :
588 : /* get the new blocklist index based on the new free chunk count */
589 1887787 : new_blocklist_idx = SlabBlocklistIndex(slab, block->nfree);
590 :
591 : /*
592 : * Handle the case where the blocklist index changes. This also deals
593 : * with blocks becoming full as only full blocks go at index 0.
594 : */
595 1887787 : if (unlikely(slab->curBlocklistIndex != new_blocklist_idx))
596 : {
597 49342 : dlist_delete_from(blocklist, &block->node);
598 49342 : dlist_push_head(&slab->blocklist[new_blocklist_idx], &block->node);
599 :
600 49342 : if (dlist_is_empty(blocklist))
601 49277 : slab->curBlocklistIndex = SlabFindNextBlockListIndex(slab);
602 : }
603 : }
2232 andres 604 ECB :
605 : /*
606 : * Check that the chunk pointer is actually somewhere on the block and is
607 : * aligned as expected.
608 : */
110 drowley 609 GNC 1918429 : Assert(chunk >= SlabBlockGetChunk(slab, block, 0));
610 1918429 : Assert(chunk <= SlabBlockGetChunk(slab, block, slab->chunksPerBlock - 1));
611 1918429 : Assert(SlabChunkMod(slab, block, chunk) == 0);
2232 andres 612 ECB :
613 : /* Prepare to initialize the chunk header. */
614 : VALGRIND_MAKE_MEM_UNDEFINED(chunk, Slab_CHUNKHDRSZ);
615 :
223 drowley 616 GNC 1918429 : MemoryChunkSetHdrMask(chunk, block, MAXALIGN(slab->chunkSize),
617 : MCTX_SLAB_ID);
2232 andres 618 ECB : #ifdef MEMORY_CONTEXT_CHECKING
619 : /* slab mark to catch clobber of "unused" space */
214 drowley 620 GNC 1918429 : Assert(slab->chunkSize < (slab->fullChunkSize - Slab_CHUNKHDRSZ));
621 1918429 : set_sentinel(MemoryChunkGetPointer(chunk), size);
622 : VALGRIND_MAKE_MEM_NOACCESS(((char *) chunk) +
623 : Slab_CHUNKHDRSZ + slab->chunkSize,
624 : slab->fullChunkSize -
625 : (slab->chunkSize + Slab_CHUNKHDRSZ));
2232 andres 626 ECB : #endif
627 :
628 : #ifdef RANDOMIZE_ALLOCATED_MEMORY
629 : /* fill the allocated space with junk */
630 : randomize_mem((char *) MemoryChunkGetPointer(chunk), size);
631 : #endif
632 :
223 drowley 633 GNC 1918429 : return MemoryChunkGetPointer(chunk);
634 : }
635 :
2232 andres 636 ECB : /*
637 : * SlabFree
638 : * Frees allocated memory; memory is removed from the slab.
639 : */
640 : void
223 drowley 641 GNC 1918119 : SlabFree(void *pointer)
2232 andres 642 ECB : {
223 drowley 643 GNC 1918119 : MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
644 1918119 : SlabBlock *block = MemoryChunkGetBlock(chunk);
645 : SlabContext *slab;
646 : int curBlocklistIdx;
647 : int newBlocklistIdx;
648 :
649 : /*
650 : * For speed reasons we just Assert that the referenced block is good.
651 : * Future field experience may show that this Assert had better become a
652 : * regular runtime test-and-elog check.
653 : */
163 peter 654 1918119 : Assert(SlabBlockIsValid(block));
181 tgl 655 1918119 : slab = block->slab;
656 :
657 : #ifdef MEMORY_CONTEXT_CHECKING
2232 andres 658 ECB : /* Test for someone scribbling on unused space in chunk */
214 drowley 659 GNC 1918119 : Assert(slab->chunkSize < (slab->fullChunkSize - Slab_CHUNKHDRSZ));
660 1918119 : if (!sentinel_ok(pointer, slab->chunkSize))
214 drowley 661 UNC 0 : elog(WARNING, "detected write past chunk end in %s %p",
662 : slab->header.name, chunk);
663 : #endif
664 :
665 : /* push this chunk onto the head of the block's free list */
110 drowley 666 GNC 1918119 : *(MemoryChunk **) pointer = block->freehead;
667 1918119 : block->freehead = chunk;
668 :
2232 andres 669 GIC 1918119 : block->nfree++;
670 :
671 1918119 : Assert(block->nfree > 0);
672 1918119 : Assert(block->nfree <= slab->chunksPerBlock);
2232 andres 673 ECB :
674 : #ifdef CLOBBER_FREED_MEMORY
675 : /* don't wipe the free list MemoryChunk pointer stored in the chunk */
110 drowley 676 GNC 1918119 : wipe_mem((char *) pointer + sizeof(MemoryChunk *),
677 1918119 : slab->chunkSize - sizeof(MemoryChunk *));
678 : #endif
679 :
680 1918119 : curBlocklistIdx = SlabBlocklistIndex(slab, block->nfree - 1);
681 1918119 : newBlocklistIdx = SlabBlocklistIndex(slab, block->nfree);
682 :
2232 andres 683 ECB : /*
684 : * Check if the block needs to be moved to another element on the
685 : * blocklist based on it now having 1 more free chunk.
686 : */
110 drowley 687 GNC 1918119 : if (unlikely(curBlocklistIdx != newBlocklistIdx))
2232 andres 688 ECB : {
689 : /* do the move */
110 drowley 690 GNC 49336 : dlist_delete_from(&slab->blocklist[curBlocklistIdx], &block->node);
691 49336 : dlist_push_head(&slab->blocklist[newBlocklistIdx], &block->node);
692 :
693 : /*
694 : * The blocklist[curBlocklistIdx] may now be empty or we may now be
695 : * able to use a lower-element blocklist. We'll need to redetermine
696 : * what the slab->curBlocklistIndex is if the current blocklist was
697 : * changed or if a lower element one was changed. We must ensure we
698 : * use the list with the fullest block(s).
699 : */
108 700 49336 : if (slab->curBlocklistIndex >= curBlocklistIdx)
2232 andres 701 ECB : {
110 drowley 702 GNC 49336 : slab->curBlocklistIndex = SlabFindNextBlockListIndex(slab);
703 :
704 : /*
705 : * We know there must be a block with at least 1 unused chunk as
706 : * we just pfree'd one. Ensure curBlocklistIndex reflects this.
707 : */
708 49336 : Assert(slab->curBlocklistIndex > 0);
709 : }
710 : }
711 :
712 : /* Handle when a block becomes completely empty */
713 1918119 : if (unlikely(block->nfree == slab->chunksPerBlock))
714 : {
715 : /* remove the block */
716 30571 : dlist_delete_from(&slab->blocklist[newBlocklistIdx], &block->node);
717 :
718 : /*
719 : * To avoid thrashing malloc/free, we keep a list of empty blocks that
720 : * we can reuse again instead of having to malloc a new one.
721 : */
722 30571 : if (dclist_count(&slab->emptyblocks) < SLAB_MAXIMUM_EMPTY_BLOCKS)
723 28858 : dclist_push_head(&slab->emptyblocks, &block->node);
724 : else
725 : {
726 : /*
727 : * When we have enough empty blocks stored already, we actually
728 : * free the block.
729 : */
730 : #ifdef CLOBBER_FREED_MEMORY
731 1713 : wipe_mem(block, slab->blockSize);
732 : #endif
733 1713 : free(block);
734 1713 : slab->header.mem_allocated -= slab->blockSize;
735 : }
736 :
737 : /*
738 : * Check if we need to reset the blocklist index. This is required
739 : * when the blocklist this block is on has become completely empty.
740 : */
741 42926 : if (slab->curBlocklistIndex == newBlocklistIdx &&
742 12355 : dlist_is_empty(&slab->blocklist[newBlocklistIdx]))
743 7940 : slab->curBlocklistIndex = SlabFindNextBlockListIndex(slab);
744 : }
2232 andres 745 CBC 1918119 : }
746 :
747 : /*
2232 andres 748 ECB : * SlabRealloc
749 : * Change the allocated size of a chunk.
750 : *
2223 tgl 751 : * As Slab is designed for allocating equally-sized chunks of memory, it can't
752 : * do an actual chunk size change. We try to be gentle and allow calls with
753 : * exactly the same size, as in that case we can simply return the same
754 : * chunk. When the size differs, we throw an error.
2232 andres 755 : *
2223 tgl 756 : * We could also allow requests with size < chunkSize. That however seems
757 : * rather pointless - Slab is meant for chunks of constant size, and moreover
758 : * realloc is usually used to enlarge the chunk.
2232 andres 759 : */
760 : void *
223 drowley 761 UNC 0 : SlabRealloc(void *pointer, Size size)
2232 andres 762 ECB : {
223 drowley 763 UNC 0 : MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
764 0 : SlabBlock *block = MemoryChunkGetBlock(chunk);
765 : SlabContext *slab;
766 :
767 : /*
768 : * Try to verify that we have a sane block pointer: the block header
769 : * should reference a slab context. (We use a test-and-elog, not just
770 : * Assert, because it seems highly likely that we're here in error in the
771 : * first place.)
772 : */
181 tgl 773 0 : if (!SlabBlockIsValid(block))
774 0 : elog(ERROR, "could not find block containing chunk %p", chunk);
775 0 : slab = block->slab;
776 :
777 : /* can't do actual realloc with slab, but let's try to be gentle */
2232 andres 778 LBC 0 : if (size == slab->chunkSize)
2232 andres 779 UIC 0 : return pointer;
2232 andres 780 ECB :
2232 andres 781 LBC 0 : elog(ERROR, "slab allocator does not support realloc()");
782 : return NULL; /* keep compiler quiet */
2232 andres 783 ECB : }
784 :
785 : /*
786 : * SlabGetChunkContext
787 : * Return the MemoryContext that 'pointer' belongs to.
788 : */
789 : MemoryContext
223 drowley 790 UNC 0 : SlabGetChunkContext(void *pointer)
791 : {
792 0 : MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
793 0 : SlabBlock *block = MemoryChunkGetBlock(chunk);
794 :
163 peter 795 0 : Assert(SlabBlockIsValid(block));
181 tgl 796 0 : return &block->slab->header;
797 : }
798 :
799 : /*
800 : * SlabGetChunkSpace
801 : * Given a currently-allocated chunk, determine the total space
802 : * it occupies (including all memory-allocation overhead).
803 : */
804 : Size
223 drowley 805 0 : SlabGetChunkSpace(void *pointer)
2232 andres 806 ECB : {
223 drowley 807 UNC 0 : MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
808 0 : SlabBlock *block = MemoryChunkGetBlock(chunk);
809 : SlabContext *slab;
2232 andres 810 ECB :
163 peter 811 UNC 0 : Assert(SlabBlockIsValid(block));
181 tgl 812 0 : slab = block->slab;
813 :
2232 andres 814 UIC 0 : return slab->fullChunkSize;
815 : }
2232 andres 816 ECB :
817 : /*
818 : * SlabIsEmpty
819 : * Is the slab empty of any allocated space?
820 : */
821 : bool
2232 andres 822 UIC 0 : SlabIsEmpty(MemoryContext context)
823 : {
110 drowley 824 UNC 0 : Assert(SlabIsValid((SlabContext *) context));
825 :
826 0 : return (context->mem_allocated == 0);
827 : }
828 :
829 : /*
830 : * SlabStats
1943 tgl 831 ECB : * Compute stats about memory consumption of a Slab context.
832 : *
833 : * printfunc: if not NULL, pass a human-readable stats string to this.
834 : * passthru: pass this pointer through to printfunc.
835 : * totals: if not NULL, add stats about this context into *totals.
836 : * print_to_stderr: print stats to stderr if true, elog otherwise.
837 : */
838 : void
1839 tgl 839 LBC 0 : SlabStats(MemoryContext context,
840 : MemoryStatsPrintFunc printfunc, void *passthru,
733 fujii 841 ECB : MemoryContextCounters *totals,
842 : bool print_to_stderr)
843 : {
181 tgl 844 UNC 0 : SlabContext *slab = (SlabContext *) context;
2232 andres 845 UIC 0 : Size nblocks = 0;
846 0 : Size freechunks = 0;
847 : Size totalspace;
848 0 : Size freespace = 0;
849 : int i;
850 :
163 peter 851 UNC 0 : Assert(SlabIsValid(slab));
181 tgl 852 ECB :
853 : /* Include context header in totalspace */
110 drowley 854 UNC 0 : totalspace = Slab_CONTEXT_HDRSZ(slab->chunksPerBlock);
855 :
856 : /* Add the space consumed by blocks in the emptyblocks list */
857 0 : totalspace += dclist_count(&slab->emptyblocks) * slab->blockSize;
858 :
859 0 : for (i = 0; i < SLAB_BLOCKLIST_COUNT; i++)
860 : {
861 : dlist_iter iter;
2232 andres 862 ECB :
110 drowley 863 UNC 0 : dlist_foreach(iter, &slab->blocklist[i])
2232 andres 864 EUB : {
2232 andres 865 UIC 0 : SlabBlock *block = dlist_container(SlabBlock, node, iter.cur);
866 :
867 0 : nblocks++;
868 0 : totalspace += slab->blockSize;
2232 andres 869 LBC 0 : freespace += slab->fullChunkSize * block->nfree;
870 0 : freechunks += block->nfree;
871 : }
2232 andres 872 ECB : }
873 :
1839 tgl 874 LBC 0 : if (printfunc)
2232 andres 875 ECB : {
876 : char stats_string[200];
877 :
878 : /* XXX should we include free chunks on empty blocks? */
1839 tgl 879 UIC 0 : snprintf(stats_string, sizeof(stats_string),
880 : "%zu total in %zu blocks; %u empty blocks; %zu free (%zu chunks); %zu used",
110 drowley 881 UNC 0 : totalspace, nblocks, dclist_count(&slab->emptyblocks),
882 : freespace, freechunks, totalspace - freespace);
733 fujii 883 UIC 0 : printfunc(context, passthru, stats_string, print_to_stderr);
2232 andres 884 ECB : }
885 :
2232 andres 886 UIC 0 : if (totals)
887 : {
888 0 : totals->nblocks += nblocks;
889 0 : totals->freechunks += freechunks;
890 0 : totals->totalspace += totalspace;
2232 andres 891 LBC 0 : totals->freespace += freespace;
892 : }
2232 andres 893 UIC 0 : }
2232 andres 894 ECB :
895 :
896 : #ifdef MEMORY_CONTEXT_CHECKING
897 :
898 : /*
899 : * SlabCheck
900 : * Walk through all blocks looking for inconsistencies.
901 : *
902 : * NOTE: report errors as WARNING, *not* ERROR or FATAL. Otherwise you'll
903 : * find yourself in an infinite loop when trouble occurs, because this
904 : * routine will be entered again when elog cleanup tries to release memory!
905 : */
906 : void
2232 andres 907 GIC 1390 : SlabCheck(MemoryContext context)
908 : {
181 tgl 909 GNC 1390 : SlabContext *slab = (SlabContext *) context;
910 : int i;
110 drowley 911 1390 : int nblocks = 0;
1943 tgl 912 GIC 1390 : const char *name = slab->header.name;
913 : dlist_iter iter;
2232 andres 914 ECB :
163 peter 915 GNC 1390 : Assert(SlabIsValid(slab));
2232 andres 916 GIC 1390 : Assert(slab->chunksPerBlock > 0);
917 :
918 : /*
919 : * Have a look at the empty blocks. These should have all their chunks
920 : * marked as free. Ensure that's the case.
921 : */
110 drowley 922 GNC 2098 : dclist_foreach(iter, &slab->emptyblocks)
923 : {
924 708 : SlabBlock *block = dlist_container(SlabBlock, node, iter.cur);
925 :
926 708 : if (block->nfree != slab->chunksPerBlock)
110 drowley 927 UNC 0 : elog(WARNING, "problem in slab %s: empty block %p should have %d free chunks but has %d chunks free",
928 : name, block, slab->chunksPerBlock, block->nfree);
929 : }
930 :
931 : /* walk the non-empty block lists */
110 drowley 932 GNC 5560 : for (i = 0; i < SLAB_BLOCKLIST_COUNT; i++)
933 : {
934 : int j,
2232 andres 935 ECB : nfree;
936 :
937 : /* walk all blocks on this blocklist */
110 drowley 938 GNC 4222 : dlist_foreach(iter, &slab->blocklist[i])
939 : {
2232 andres 940 CBC 52 : SlabBlock *block = dlist_container(SlabBlock, node, iter.cur);
941 : MemoryChunk *cur_chunk;
942 :
943 : /*
944 : * Make sure the number of free chunks (in the block header)
945 : * matches the position in the blocklist.
946 : */
110 drowley 947 GNC 52 : if (SlabBlocklistIndex(slab, block->nfree) != i)
110 drowley 948 UNC 0 : elog(WARNING, "problem in slab %s: block %p is on blocklist %d but should be on blocklist %d",
949 : name, block, i, SlabBlocklistIndex(slab, block->nfree));
950 :
951 : /* make sure the block is not empty */
110 drowley 952 GNC 52 : if (block->nfree >= slab->chunksPerBlock)
110 drowley 953 UNC 0 : elog(WARNING, "problem in slab %s: empty block %p incorrectly stored on blocklist element %d",
954 : name, block, i);
955 :
956 : /* make sure the slab pointer correctly points to this context */
223 drowley 957 GNC 52 : if (block->slab != slab)
223 drowley 958 UNC 0 : elog(WARNING, "problem in slab %s: bogus slab link in block %p",
959 : name, block);
960 :
961 : /* reset the array of free chunks for this block */
110 drowley 962 GNC 52 : memset(slab->isChunkFree, 0, (slab->chunksPerBlock * sizeof(bool)));
963 52 : nfree = 0;
964 :
965 : /* walk through the block's free list chunks */
966 52 : cur_chunk = block->freehead;
967 633 : while (cur_chunk != NULL)
968 : {
969 581 : int chunkidx = SlabChunkIndex(slab, block, cur_chunk);
970 :
971 : /*
972 : * Ensure the free list link points to something on the block
973 : * at an address aligned according to the full chunk size.
974 : */
975 581 : if (cur_chunk < SlabBlockGetChunk(slab, block, 0) ||
976 581 : cur_chunk > SlabBlockGetChunk(slab, block, slab->chunksPerBlock - 1) ||
977 581 : SlabChunkMod(slab, block, cur_chunk) != 0)
110 drowley 978 UNC 0 : elog(WARNING, "problem in slab %s: bogus free list link %p in block %p",
979 : name, cur_chunk, block);
980 :
981 : /* count the chunk and mark it free on the free chunk array */
110 drowley 982 GNC 581 : nfree++;
983 581 : slab->isChunkFree[chunkidx] = true;
984 :
985 : /* read pointer of the next free chunk */
986 : VALGRIND_MAKE_MEM_DEFINED(MemoryChunkGetPointer(cur_chunk), sizeof(MemoryChunk *));
987 581 : cur_chunk = *(MemoryChunk **) SlabChunkGetPointer(cur_chunk);
988 : }
989 :
990 : /* check that the unused pointer matches what nunused claims */
991 52 : if (SlabBlockGetChunk(slab, block, slab->chunksPerBlock - block->nunused) !=
992 52 : block->unused)
110 drowley 993 UNC 0 : elog(WARNING, "problem in slab %s: mismatch detected between nunused chunks and unused pointer in block %p",
994 : name, block);
995 :
996 : /*
997 : * count the remaining free chunks that have yet to make it onto
998 : * the block's free list.
2232 andres 999 ECB : */
110 drowley 1000 GNC 52 : cur_chunk = block->unused;
1001 1672 : for (j = 0; j < block->nunused; j++)
1002 : {
1003 1620 : int chunkidx = SlabChunkIndex(slab, block, cur_chunk);
1004 :
1005 :
1006 : /* count the chunk as free and mark it as so in the array */
2232 andres 1007 GIC 1620 : nfree++;
110 drowley 1008 GNC 1620 : if (chunkidx < slab->chunksPerBlock)
1009 1620 : slab->isChunkFree[chunkidx] = true;
1010 :
1011 : /* move forward 1 chunk */
1012 1620 : cur_chunk = (MemoryChunk *) (((char *) cur_chunk) + slab->fullChunkSize);
1013 : }
1014 :
2232 andres 1015 GIC 2542 : for (j = 0; j < slab->chunksPerBlock; j++)
1016 : {
110 drowley 1017 GNC 2490 : if (!slab->isChunkFree[j])
2232 andres 1018 EUB : {
223 drowley 1019 GNC 289 : MemoryChunk *chunk = SlabBlockGetChunk(slab, block, j);
1020 289 : SlabBlock *chunkblock = (SlabBlock *) MemoryChunkGetBlock(chunk);
1021 :
1022 : /*
1023 : * check the chunk's blockoffset correctly points back to
1024 : * the block
1025 : */
1026 289 : if (chunkblock != block)
2232 andres 1027 UIC 0 : elog(WARNING, "problem in slab %s: bogus block link in block %p, chunk %p",
1028 : name, block, chunk);
1029 :
1030 : /* check the sentinel byte is intact */
214 drowley 1031 GNC 289 : Assert(slab->chunkSize < (slab->fullChunkSize - Slab_CHUNKHDRSZ));
1032 289 : if (!sentinel_ok(chunk, Slab_CHUNKHDRSZ + slab->chunkSize))
214 drowley 1033 UNC 0 : elog(WARNING, "problem in slab %s: detected write past chunk end in block %p, chunk %p",
214 drowley 1034 EUB : name, block, chunk);
1035 : }
2232 andres 1036 : }
1037 :
1038 : /*
1039 : * Make sure we got the expected number of free chunks (as tracked
1040 : * in the block header).
1041 : */
2232 andres 1042 GIC 52 : if (nfree != block->nfree)
110 drowley 1043 UNC 0 : elog(WARNING, "problem in slab %s: nfree in block %p is %d but %d chunk were found as free",
1044 : name, block, block->nfree, nfree);
1045 :
110 drowley 1046 GNC 52 : nblocks++;
2232 andres 1047 EUB : }
1048 : }
1286 tomas.vondra 1049 :
1050 : /* the stored empty blocks are tracked in mem_allocated too */
110 drowley 1051 GNC 1390 : nblocks += dclist_count(&slab->emptyblocks);
1052 :
1053 1390 : Assert(nblocks * slab->blockSize == context->mem_allocated);
2232 andres 1054 GIC 1390 : }
2232 andres 1055 EUB :
2118 tgl 1056 : #endif /* MEMORY_CONTEXT_CHECKING */
|
