PostgreSQL Source Code  git master
slab.c
Go to the documentation of this file.
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"
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  */
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[] */
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
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
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
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 *
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  */
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 MAXALIGN(chunkSize) may not exceed MEMORYCHUNK_MAX_VALUE
318  */
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 */
332  "sizeof(MemoryChunk) is not maxaligned");
333  Assert(MAXALIGN(chunkSize) <= MEMORYCHUNK_MAX_VALUE);
334 
335  /*
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  */
339  if (chunkSize < sizeof(MemoryChunk *))
340  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 */
345  fullChunkSize = Slab_CHUNKHDRSZ + MAXALIGN(chunkSize + 1);
346 #else
347  fullChunkSize = Slab_CHUNKHDRSZ + MAXALIGN(chunkSize);
348 #endif
349 
350  /* compute the number of chunks that will fit on each block */
351  chunksPerBlock = (blockSize - Slab_BLOCKHDRSZ) / fullChunkSize;
352 
353  /* Make sure the block can store at least one chunk. */
354  if (chunksPerBlock == 0)
355  elog(ERROR, "block size %zu for slab is too small for %zu-byte chunks",
356  blockSize, chunkSize);
357 
358 
359 
360  slab = (SlabContext *) malloc(Slab_CONTEXT_HDRSZ(chunksPerBlock));
361  if (slab == NULL)
362  {
364  ereport(ERROR,
365  (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 */
377  slab->chunkSize = chunkSize;
378  slab->fullChunkSize = fullChunkSize;
379  slab->blockSize = blockSize;
380  slab->chunksPerBlock = chunksPerBlock;
381  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  slab->blocklist_shift = 0;
394  while ((slab->chunksPerBlock >> slab->blocklist_shift) >= (SLAB_BLOCKLIST_COUNT - 1))
395  slab->blocklist_shift++;
396 
397  /* initialize the list to store empty blocks to be reused */
398  dclist_init(&slab->emptyblocks);
399 
400  /* initialize each blocklist slot */
401  for (i = 0; i < SLAB_BLOCKLIST_COUNT; i++)
402  dlist_init(&slab->blocklist[i]);
403 
404 #ifdef MEMORY_CONTEXT_CHECKING
405  /* set the isChunkFree pointer right after the end of the context */
406  slab->isChunkFree = (bool *) ((char *) slab + sizeof(SlabContext));
407 #endif
408 
409  /* Finally, do the type-independent part of context creation */
411  T_SlabContext,
412  MCTX_SLAB_ID,
413  parent,
414  name);
415 
416  return (MemoryContext) slab;
417 }
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
428 {
429  SlabContext *slab = (SlabContext *) context;
430  dlist_mutable_iter miter;
431  int i;
432 
433  Assert(SlabIsValid(slab));
434 
435 #ifdef MEMORY_CONTEXT_CHECKING
436  /* Check for corruption and leaks before freeing */
437  SlabCheck(context);
438 #endif
439 
440  /* release any retained empty blocks */
441  dclist_foreach_modify(miter, &slab->emptyblocks)
442  {
443  SlabBlock *block = dlist_container(SlabBlock, node, miter.cur);
444 
445  dclist_delete_from(&slab->emptyblocks, miter.cur);
446 
447 #ifdef CLOBBER_FREED_MEMORY
448  wipe_mem(block, slab->blockSize);
449 #endif
450  free(block);
451  context->mem_allocated -= slab->blockSize;
452  }
453 
454  /* walk over blocklist and free the blocks */
455  for (i = 0; i < SLAB_BLOCKLIST_COUNT; i++)
456  {
457  dlist_foreach_modify(miter, &slab->blocklist[i])
458  {
459  SlabBlock *block = dlist_container(SlabBlock, node, miter.cur);
460 
461  dlist_delete(miter.cur);
462 
463 #ifdef CLOBBER_FREED_MEMORY
464  wipe_mem(block, slab->blockSize);
465 #endif
466  free(block);
467  context->mem_allocated -= slab->blockSize;
468  }
469  }
470 
471  slab->curBlocklistIndex = 0;
472 
473  Assert(context->mem_allocated == 0);
474 }
475 
476 /*
477  * SlabDelete
478  * Free all memory which is allocated in the given context.
479  */
480 void
482 {
483  /* Reset to release all the SlabBlocks */
484  SlabReset(context);
485  /* And free the context header */
486  free(context);
487 }
488 
489 /*
490  * SlabAlloc
491  * Returns a pointer to allocated memory of given size or NULL if
492  * request could not be completed; memory is added to the slab.
493  */
494 void *
496 {
497  SlabContext *slab = (SlabContext *) context;
498  SlabBlock *block;
499  MemoryChunk *chunk;
500 
501  Assert(SlabIsValid(slab));
502 
503  /* sanity check that this is pointing to a valid blocklist */
504  Assert(slab->curBlocklistIndex >= 0);
506 
507  /* make sure we only allow correct request size */
508  if (unlikely(size != slab->chunkSize))
509  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  */
519  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  if (dclist_count(&slab->emptyblocks) > 0)
526  {
528 
529  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  Assert(block->nfree == slab->chunksPerBlock);
536 
537  /* fetch the next chunk from this block */
538  chunk = SlabGetNextFreeChunk(slab, block);
539  }
540  else
541  {
542  block = (SlabBlock *) malloc(slab->blockSize);
543 
544  if (unlikely(block == NULL))
545  return NULL;
546 
547  block->slab = slab;
548  context->mem_allocated += slab->blockSize;
549 
550  /* use the first chunk in the new block */
551  chunk = SlabBlockGetChunk(slab, block, 0);
552 
553  block->nfree = slab->chunksPerBlock - 1;
554  block->unused = SlabBlockGetChunk(slab, block, 1);
555  block->freehead = NULL;
556  block->nunused = slab->chunksPerBlock - 1;
557  }
558 
559  /* find the blocklist element for storing blocks with 1 used chunk */
560  blocklist_idx = SlabBlocklistIndex(slab, block->nfree);
561  blocklist = &slab->blocklist[blocklist_idx];
562 
563  /* this better be empty. We just added a block thinking it was */
564  Assert(dlist_is_empty(blocklist));
565 
566  dlist_push_head(blocklist, &block->node);
567 
568  slab->curBlocklistIndex = blocklist_idx;
569  }
570  else
571  {
572  dlist_head *blocklist = &slab->blocklist[slab->curBlocklistIndex];
573  int new_blocklist_idx;
574 
575  Assert(!dlist_is_empty(blocklist));
576 
577  /* grab the block from the blocklist */
578  block = dlist_head_element(SlabBlock, node, blocklist);
579 
580  /* make sure we actually got a valid block, with matching nfree */
581  Assert(block != NULL);
582  Assert(slab->curBlocklistIndex == SlabBlocklistIndex(slab, block->nfree));
583  Assert(block->nfree > 0);
584 
585  /* fetch the next chunk from this block */
586  chunk = SlabGetNextFreeChunk(slab, block);
587 
588  /* get the new blocklist index based on the new free chunk count */
589  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  if (unlikely(slab->curBlocklistIndex != new_blocklist_idx))
596  {
597  dlist_delete_from(blocklist, &block->node);
598  dlist_push_head(&slab->blocklist[new_blocklist_idx], &block->node);
599 
600  if (dlist_is_empty(blocklist))
602  }
603  }
604 
605  /*
606  * Check that the chunk pointer is actually somewhere on the block and is
607  * aligned as expected.
608  */
609  Assert(chunk >= SlabBlockGetChunk(slab, block, 0));
610  Assert(chunk <= SlabBlockGetChunk(slab, block, slab->chunksPerBlock - 1));
611  Assert(SlabChunkMod(slab, block, chunk) == 0);
612 
613  /* Prepare to initialize the chunk header. */
615 
616  MemoryChunkSetHdrMask(chunk, block, MAXALIGN(slab->chunkSize),
617  MCTX_SLAB_ID);
618 #ifdef MEMORY_CONTEXT_CHECKING
619  /* slab mark to catch clobber of "unused" space */
620  Assert(slab->chunkSize < (slab->fullChunkSize - Slab_CHUNKHDRSZ));
621  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));
626 #endif
627 
628 #ifdef RANDOMIZE_ALLOCATED_MEMORY
629  /* fill the allocated space with junk */
630  randomize_mem((char *) MemoryChunkGetPointer(chunk), size);
631 #endif
632 
633  /* Disallow access to the chunk header. */
635 
636  return MemoryChunkGetPointer(chunk);
637 }
638 
639 /*
640  * SlabFree
641  * Frees allocated memory; memory is removed from the slab.
642  */
643 void
644 SlabFree(void *pointer)
645 {
646  MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
647  SlabBlock *block;
648  SlabContext *slab;
649  int curBlocklistIdx;
650  int newBlocklistIdx;
651 
652  /* Allow access to the chunk header. */
654 
655  block = MemoryChunkGetBlock(chunk);
656 
657  /*
658  * For speed reasons we just Assert that the referenced block is good.
659  * Future field experience may show that this Assert had better become a
660  * regular runtime test-and-elog check.
661  */
662  Assert(SlabBlockIsValid(block));
663  slab = block->slab;
664 
665 #ifdef MEMORY_CONTEXT_CHECKING
666  /* Test for someone scribbling on unused space in chunk */
667  Assert(slab->chunkSize < (slab->fullChunkSize - Slab_CHUNKHDRSZ));
668  if (!sentinel_ok(pointer, slab->chunkSize))
669  elog(WARNING, "detected write past chunk end in %s %p",
670  slab->header.name, chunk);
671 #endif
672 
673  /* push this chunk onto the head of the block's free list */
674  *(MemoryChunk **) pointer = block->freehead;
675  block->freehead = chunk;
676 
677  block->nfree++;
678 
679  Assert(block->nfree > 0);
680  Assert(block->nfree <= slab->chunksPerBlock);
681 
682 #ifdef CLOBBER_FREED_MEMORY
683  /* don't wipe the free list MemoryChunk pointer stored in the chunk */
684  wipe_mem((char *) pointer + sizeof(MemoryChunk *),
685  slab->chunkSize - sizeof(MemoryChunk *));
686 #endif
687 
688  curBlocklistIdx = SlabBlocklistIndex(slab, block->nfree - 1);
689  newBlocklistIdx = SlabBlocklistIndex(slab, block->nfree);
690 
691  /*
692  * Check if the block needs to be moved to another element on the
693  * blocklist based on it now having 1 more free chunk.
694  */
695  if (unlikely(curBlocklistIdx != newBlocklistIdx))
696  {
697  /* do the move */
698  dlist_delete_from(&slab->blocklist[curBlocklistIdx], &block->node);
699  dlist_push_head(&slab->blocklist[newBlocklistIdx], &block->node);
700 
701  /*
702  * The blocklist[curBlocklistIdx] may now be empty or we may now be
703  * able to use a lower-element blocklist. We'll need to redetermine
704  * what the slab->curBlocklistIndex is if the current blocklist was
705  * changed or if a lower element one was changed. We must ensure we
706  * use the list with the fullest block(s).
707  */
708  if (slab->curBlocklistIndex >= curBlocklistIdx)
709  {
711 
712  /*
713  * We know there must be a block with at least 1 unused chunk as
714  * we just pfree'd one. Ensure curBlocklistIndex reflects this.
715  */
716  Assert(slab->curBlocklistIndex > 0);
717  }
718  }
719 
720  /* Handle when a block becomes completely empty */
721  if (unlikely(block->nfree == slab->chunksPerBlock))
722  {
723  /* remove the block */
724  dlist_delete_from(&slab->blocklist[newBlocklistIdx], &block->node);
725 
726  /*
727  * To avoid thrashing malloc/free, we keep a list of empty blocks that
728  * we can reuse again instead of having to malloc a new one.
729  */
731  dclist_push_head(&slab->emptyblocks, &block->node);
732  else
733  {
734  /*
735  * When we have enough empty blocks stored already, we actually
736  * free the block.
737  */
738 #ifdef CLOBBER_FREED_MEMORY
739  wipe_mem(block, slab->blockSize);
740 #endif
741  free(block);
742  slab->header.mem_allocated -= slab->blockSize;
743  }
744 
745  /*
746  * Check if we need to reset the blocklist index. This is required
747  * when the blocklist this block is on has become completely empty.
748  */
749  if (slab->curBlocklistIndex == newBlocklistIdx &&
750  dlist_is_empty(&slab->blocklist[newBlocklistIdx]))
752  }
753 }
754 
755 /*
756  * SlabRealloc
757  * Change the allocated size of a chunk.
758  *
759  * As Slab is designed for allocating equally-sized chunks of memory, it can't
760  * do an actual chunk size change. We try to be gentle and allow calls with
761  * exactly the same size, as in that case we can simply return the same
762  * chunk. When the size differs, we throw an error.
763  *
764  * We could also allow requests with size < chunkSize. That however seems
765  * rather pointless - Slab is meant for chunks of constant size, and moreover
766  * realloc is usually used to enlarge the chunk.
767  */
768 void *
769 SlabRealloc(void *pointer, Size size)
770 {
771  MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
772  SlabBlock *block;
773  SlabContext *slab;
774 
775  /* Allow access to the chunk header. */
777 
778  block = MemoryChunkGetBlock(chunk);
779 
780  /* Disallow access to the chunk header. */
782 
783  /*
784  * Try to verify that we have a sane block pointer: the block header
785  * should reference a slab context. (We use a test-and-elog, not just
786  * Assert, because it seems highly likely that we're here in error in the
787  * first place.)
788  */
789  if (!SlabBlockIsValid(block))
790  elog(ERROR, "could not find block containing chunk %p", chunk);
791  slab = block->slab;
792 
793  /* can't do actual realloc with slab, but let's try to be gentle */
794  if (size == slab->chunkSize)
795  return pointer;
796 
797  elog(ERROR, "slab allocator does not support realloc()");
798  return NULL; /* keep compiler quiet */
799 }
800 
801 /*
802  * SlabGetChunkContext
803  * Return the MemoryContext that 'pointer' belongs to.
804  */
806 SlabGetChunkContext(void *pointer)
807 {
808  MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
809  SlabBlock *block;
810 
811  /* Allow access to the chunk header. */
813 
814  block = MemoryChunkGetBlock(chunk);
815 
816  /* Disallow access to the chunk header. */
818 
819  Assert(SlabBlockIsValid(block));
820 
821  return &block->slab->header;
822 }
823 
824 /*
825  * SlabGetChunkSpace
826  * Given a currently-allocated chunk, determine the total space
827  * it occupies (including all memory-allocation overhead).
828  */
829 Size
830 SlabGetChunkSpace(void *pointer)
831 {
832  MemoryChunk *chunk = PointerGetMemoryChunk(pointer);
833  SlabBlock *block;
834  SlabContext *slab;
835 
836  /* Allow access to the chunk header. */
838 
839  block = MemoryChunkGetBlock(chunk);
840 
841  /* Disallow access to the chunk header. */
843 
844  Assert(SlabBlockIsValid(block));
845  slab = block->slab;
846 
847  return slab->fullChunkSize;
848 }
849 
850 /*
851  * SlabIsEmpty
852  * Is the slab empty of any allocated space?
853  */
854 bool
856 {
857  Assert(SlabIsValid((SlabContext *) context));
858 
859  return (context->mem_allocated == 0);
860 }
861 
862 /*
863  * SlabStats
864  * Compute stats about memory consumption of a Slab context.
865  *
866  * printfunc: if not NULL, pass a human-readable stats string to this.
867  * passthru: pass this pointer through to printfunc.
868  * totals: if not NULL, add stats about this context into *totals.
869  * print_to_stderr: print stats to stderr if true, elog otherwise.
870  */
871 void
873  MemoryStatsPrintFunc printfunc, void *passthru,
874  MemoryContextCounters *totals,
875  bool print_to_stderr)
876 {
877  SlabContext *slab = (SlabContext *) context;
878  Size nblocks = 0;
879  Size freechunks = 0;
880  Size totalspace;
881  Size freespace = 0;
882  int i;
883 
884  Assert(SlabIsValid(slab));
885 
886  /* Include context header in totalspace */
887  totalspace = Slab_CONTEXT_HDRSZ(slab->chunksPerBlock);
888 
889  /* Add the space consumed by blocks in the emptyblocks list */
890  totalspace += dclist_count(&slab->emptyblocks) * slab->blockSize;
891 
892  for (i = 0; i < SLAB_BLOCKLIST_COUNT; i++)
893  {
894  dlist_iter iter;
895 
896  dlist_foreach(iter, &slab->blocklist[i])
897  {
898  SlabBlock *block = dlist_container(SlabBlock, node, iter.cur);
899 
900  nblocks++;
901  totalspace += slab->blockSize;
902  freespace += slab->fullChunkSize * block->nfree;
903  freechunks += block->nfree;
904  }
905  }
906 
907  if (printfunc)
908  {
909  char stats_string[200];
910 
911  /* XXX should we include free chunks on empty blocks? */
912  snprintf(stats_string, sizeof(stats_string),
913  "%zu total in %zu blocks; %u empty blocks; %zu free (%zu chunks); %zu used",
914  totalspace, nblocks, dclist_count(&slab->emptyblocks),
915  freespace, freechunks, totalspace - freespace);
916  printfunc(context, passthru, stats_string, print_to_stderr);
917  }
918 
919  if (totals)
920  {
921  totals->nblocks += nblocks;
922  totals->freechunks += freechunks;
923  totals->totalspace += totalspace;
924  totals->freespace += freespace;
925  }
926 }
927 
928 
929 #ifdef MEMORY_CONTEXT_CHECKING
930 
931 /*
932  * SlabCheck
933  * Walk through all blocks looking for inconsistencies.
934  *
935  * NOTE: report errors as WARNING, *not* ERROR or FATAL. Otherwise you'll
936  * find yourself in an infinite loop when trouble occurs, because this
937  * routine will be entered again when elog cleanup tries to release memory!
938  */
939 void
940 SlabCheck(MemoryContext context)
941 {
942  SlabContext *slab = (SlabContext *) context;
943  int i;
944  int nblocks = 0;
945  const char *name = slab->header.name;
946  dlist_iter iter;
947 
948  Assert(SlabIsValid(slab));
949  Assert(slab->chunksPerBlock > 0);
950 
951  /*
952  * Have a look at the empty blocks. These should have all their chunks
953  * marked as free. Ensure that's the case.
954  */
955  dclist_foreach(iter, &slab->emptyblocks)
956  {
957  SlabBlock *block = dlist_container(SlabBlock, node, iter.cur);
958 
959  if (block->nfree != slab->chunksPerBlock)
960  elog(WARNING, "problem in slab %s: empty block %p should have %d free chunks but has %d chunks free",
961  name, block, slab->chunksPerBlock, block->nfree);
962  }
963 
964  /* walk the non-empty block lists */
965  for (i = 0; i < SLAB_BLOCKLIST_COUNT; i++)
966  {
967  int j,
968  nfree;
969 
970  /* walk all blocks on this blocklist */
971  dlist_foreach(iter, &slab->blocklist[i])
972  {
973  SlabBlock *block = dlist_container(SlabBlock, node, iter.cur);
974  MemoryChunk *cur_chunk;
975 
976  /*
977  * Make sure the number of free chunks (in the block header)
978  * matches the position in the blocklist.
979  */
980  if (SlabBlocklistIndex(slab, block->nfree) != i)
981  elog(WARNING, "problem in slab %s: block %p is on blocklist %d but should be on blocklist %d",
982  name, block, i, SlabBlocklistIndex(slab, block->nfree));
983 
984  /* make sure the block is not empty */
985  if (block->nfree >= slab->chunksPerBlock)
986  elog(WARNING, "problem in slab %s: empty block %p incorrectly stored on blocklist element %d",
987  name, block, i);
988 
989  /* make sure the slab pointer correctly points to this context */
990  if (block->slab != slab)
991  elog(WARNING, "problem in slab %s: bogus slab link in block %p",
992  name, block);
993 
994  /* reset the array of free chunks for this block */
995  memset(slab->isChunkFree, 0, (slab->chunksPerBlock * sizeof(bool)));
996  nfree = 0;
997 
998  /* walk through the block's free list chunks */
999  cur_chunk = block->freehead;
1000  while (cur_chunk != NULL)
1001  {
1002  int chunkidx = SlabChunkIndex(slab, block, cur_chunk);
1003 
1004  /*
1005  * Ensure the free list link points to something on the block
1006  * at an address aligned according to the full chunk size.
1007  */
1008  if (cur_chunk < SlabBlockGetChunk(slab, block, 0) ||
1009  cur_chunk > SlabBlockGetChunk(slab, block, slab->chunksPerBlock - 1) ||
1010  SlabChunkMod(slab, block, cur_chunk) != 0)
1011  elog(WARNING, "problem in slab %s: bogus free list link %p in block %p",
1012  name, cur_chunk, block);
1013 
1014  /* count the chunk and mark it free on the free chunk array */
1015  nfree++;
1016  slab->isChunkFree[chunkidx] = true;
1017 
1018  /* read pointer of the next free chunk */
1020  cur_chunk = *(MemoryChunk **) SlabChunkGetPointer(cur_chunk);
1021  }
1022 
1023  /* check that the unused pointer matches what nunused claims */
1024  if (SlabBlockGetChunk(slab, block, slab->chunksPerBlock - block->nunused) !=
1025  block->unused)
1026  elog(WARNING, "problem in slab %s: mismatch detected between nunused chunks and unused pointer in block %p",
1027  name, block);
1028 
1029  /*
1030  * count the remaining free chunks that have yet to make it onto
1031  * the block's free list.
1032  */
1033  cur_chunk = block->unused;
1034  for (j = 0; j < block->nunused; j++)
1035  {
1036  int chunkidx = SlabChunkIndex(slab, block, cur_chunk);
1037 
1038 
1039  /* count the chunk as free and mark it as so in the array */
1040  nfree++;
1041  if (chunkidx < slab->chunksPerBlock)
1042  slab->isChunkFree[chunkidx] = true;
1043 
1044  /* move forward 1 chunk */
1045  cur_chunk = (MemoryChunk *) (((char *) cur_chunk) + slab->fullChunkSize);
1046  }
1047 
1048  for (j = 0; j < slab->chunksPerBlock; j++)
1049  {
1050  if (!slab->isChunkFree[j])
1051  {
1052  MemoryChunk *chunk = SlabBlockGetChunk(slab, block, j);
1053  SlabBlock *chunkblock;
1054 
1055  /* Allow access to the chunk header. */
1057 
1058  chunkblock = (SlabBlock *) MemoryChunkGetBlock(chunk);
1059 
1060  /* Disallow access to the chunk header. */
1062 
1063  /*
1064  * check the chunk's blockoffset correctly points back to
1065  * the block
1066  */
1067  if (chunkblock != block)
1068  elog(WARNING, "problem in slab %s: bogus block link in block %p, chunk %p",
1069  name, block, chunk);
1070 
1071  /* check the sentinel byte is intact */
1072  Assert(slab->chunkSize < (slab->fullChunkSize - Slab_CHUNKHDRSZ));
1073  if (!sentinel_ok(chunk, Slab_CHUNKHDRSZ + slab->chunkSize))
1074  elog(WARNING, "problem in slab %s: detected write past chunk end in block %p, chunk %p",
1075  name, block, chunk);
1076  }
1077  }
1078 
1079  /*
1080  * Make sure we got the expected number of free chunks (as tracked
1081  * in the block header).
1082  */
1083  if (nfree != block->nfree)
1084  elog(WARNING, "problem in slab %s: nfree in block %p is %d but %d chunk were found as free",
1085  name, block, block->nfree, nfree);
1086 
1087  nblocks++;
1088  }
1089  }
1090 
1091  /* the stored empty blocks are tracked in mem_allocated too */
1092  nblocks += dclist_count(&slab->emptyblocks);
1093 
1094  Assert(nblocks * slab->blockSize == context->mem_allocated);
1095 }
1096 
1097 #endif /* MEMORY_CONTEXT_CHECKING */
#define MAXALIGN(LEN)
Definition: c.h:795
signed int int32
Definition: c.h:478
#define unlikely(x)
Definition: c.h:295
#define StaticAssertDecl(condition, errmessage)
Definition: c.h:920
size_t Size
Definition: c.h:589
int errdetail(const char *fmt,...)
Definition: elog.c:1202
int errcode(int sqlerrcode)
Definition: elog.c:858
int errmsg(const char *fmt,...)
Definition: elog.c:1069
#define WARNING
Definition: elog.h:36
#define ERROR
Definition: elog.h:39
#define ereport(elevel,...)
Definition: elog.h:149
const char * name
Definition: encode.c:571
#define free(a)
Definition: header.h:65
#define malloc(a)
Definition: header.h:50
#define dlist_foreach(iter, lhead)
Definition: ilist.h:623
static void dlist_init(dlist_head *head)
Definition: ilist.h:314
static void dlist_delete_from(dlist_head *head, dlist_node *node)
Definition: ilist.h:429
#define dlist_head_element(type, membername, lhead)
Definition: ilist.h:603
static void dlist_delete(dlist_node *node)
Definition: ilist.h:405
static uint32 dclist_count(const dclist_head *head)
Definition: ilist.h:932
static void dlist_push_head(dlist_head *head, dlist_node *node)
Definition: ilist.h:347
#define dlist_foreach_modify(iter, lhead)
Definition: ilist.h:640
static bool dlist_is_empty(const dlist_head *head)
Definition: ilist.h:336
static void dclist_delete_from(dclist_head *head, dlist_node *node)
Definition: ilist.h:763
static void dclist_push_head(dclist_head *head, dlist_node *node)
Definition: ilist.h:693
static void dclist_init(dclist_head *head)
Definition: ilist.h:671
#define dclist_foreach_modify(iter, lhead)
Definition: ilist.h:973
#define dlist_container(type, membername, ptr)
Definition: ilist.h:593
#define dclist_foreach(iter, lhead)
Definition: ilist.h:970
static dlist_node * dclist_pop_head_node(dclist_head *head)
Definition: ilist.h:789
int j
Definition: isn.c:74
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
void MemoryContextCreate(MemoryContext node, NodeTag tag, MemoryContextMethodID method_id, MemoryContext parent, const char *name)
Definition: mcxt.c:973
MemoryContext TopMemoryContext
Definition: mcxt.c:141
void MemoryContextStats(MemoryContext context)
Definition: mcxt.c:699
#define VALGRIND_MAKE_MEM_DEFINED(addr, size)
Definition: memdebug.h:26
#define VALGRIND_MAKE_MEM_NOACCESS(addr, size)
Definition: memdebug.h:27
#define VALGRIND_MAKE_MEM_UNDEFINED(addr, size)
Definition: memdebug.h:28
void(* MemoryStatsPrintFunc)(MemoryContext context, void *passthru, const char *stats_string, bool print_to_stderr)
Definition: memnodes.h:54
@ MCTX_SLAB_ID
#define MEMORYCHUNK_MAX_VALUE
#define MemoryChunkGetPointer(c)
static void * MemoryChunkGetBlock(MemoryChunk *chunk)
#define PointerGetMemoryChunk(p)
static void MemoryChunkSetHdrMask(MemoryChunk *chunk, void *block, Size value, MemoryContextMethodID methodid)
#define snprintf
Definition: port.h:238
#define Slab_BLOCKHDRSZ
Definition: slab.c:77
struct SlabBlock SlabBlock
#define SlabIsValid(set)
Definition: slab.c:196
void * SlabAlloc(MemoryContext context, Size size)
Definition: slab.c:495
void SlabFree(void *pointer)
Definition: slab.c:644
void SlabReset(MemoryContext context)
Definition: slab.c:427
#define Slab_CHUNKHDRSZ
Definition: slab.c:157
struct SlabContext SlabContext
#define SlabChunkGetPointer(chk)
Definition: slab.c:158
MemoryContext SlabContextCreate(MemoryContext parent, const char *name, Size blockSize, Size chunkSize)
Definition: slab.c:320
static int32 SlabBlocklistIndex(SlabContext *slab, int nfree)
Definition: slab.c:211
Size SlabGetChunkSpace(void *pointer)
Definition: slab.c:830
#define Slab_CONTEXT_HDRSZ(chunksPerBlock)
Definition: slab.c:88
bool SlabIsEmpty(MemoryContext context)
Definition: slab.c:855
MemoryContext SlabGetChunkContext(void *pointer)
Definition: slab.c:806
static int32 SlabFindNextBlockListIndex(SlabContext *slab)
Definition: slab.c:251
static MemoryChunk * SlabGetNextFreeChunk(SlabContext *slab, SlabBlock *block)
Definition: slab.c:271
#define SlabBlockGetChunk(slab, block, n)
Definition: slab.c:165
void SlabStats(MemoryContext context, MemoryStatsPrintFunc printfunc, void *passthru, MemoryContextCounters *totals, bool print_to_stderr)
Definition: slab.c:872
void * SlabRealloc(void *pointer, Size size)
Definition: slab.c:769
void SlabDelete(MemoryContext context)
Definition: slab.c:481
#define SLAB_BLOCKLIST_COUNT
Definition: slab.c:95
#define SlabBlockIsValid(block)
Definition: slab.c:202
#define SLAB_MAXIMUM_EMPTY_BLOCKS
Definition: slab.c:98
Size mem_allocated
Definition: memnodes.h:87
const char * name
Definition: memnodes.h:93
int32 nfree
Definition: slab.c:149
MemoryChunk * freehead
Definition: slab.c:151
MemoryChunk * unused
Definition: slab.c:152
SlabContext * slab
Definition: slab.c:148
dlist_node node
Definition: slab.c:153
int32 nunused
Definition: slab.c:150
Size blockSize
Definition: slab.c:109
Size fullChunkSize
Definition: slab.c:108
dlist_head blocklist[SLAB_BLOCKLIST_COUNT]
Definition: slab.c:129
int32 chunksPerBlock
Definition: slab.c:110
MemoryContextData header
Definition: slab.c:105
int32 curBlocklistIndex
Definition: slab.c:111
Size chunkSize
Definition: slab.c:107
int32 blocklist_shift
Definition: slab.c:118
dclist_head emptyblocks
Definition: slab.c:120
dlist_node * cur
Definition: ilist.h:179
dlist_node * cur
Definition: ilist.h:200
Definition: type.h:95