slab.c File Reference

#include "postgres.h"
#include "lib/ilist.h"
#include "utils/memdebug.h"
#include "utils/memutils.h"

Include dependency graph for slab.c:

Go to the source code of this file.

Data Structures
struct	SlabContext
struct	SlabBlock
struct	SlabChunk

Macros
#define	SlabPointerGetChunk(ptr)    ((SlabChunk *)(((char *)(ptr)) - sizeof(SlabChunk)))
#define	SlabChunkGetPointer(chk)    ((void *)(((char *)(chk)) + sizeof(SlabChunk)))
#define	SlabBlockGetChunk(slab, block, idx)
#define	SlabBlockStart(block)    ((char *) block + sizeof(SlabBlock))
#define	SlabChunkIndex(slab, block, chunk)    (((char *) chunk - SlabBlockStart(block)) / slab->fullChunkSize)

Typedefs
typedef struct SlabContext	SlabContext
typedef struct SlabBlock	SlabBlock
typedef struct SlabChunk	SlabChunk

Functions
static void *	SlabAlloc (MemoryContext context, Size size)
static void	SlabFree (MemoryContext context, void *pointer)
static void *	SlabRealloc (MemoryContext context, void *pointer, Size size)
static void	SlabReset (MemoryContext context)
static void	SlabDelete (MemoryContext context)
static Size	SlabGetChunkSpace (MemoryContext context, void *pointer)
static bool	SlabIsEmpty (MemoryContext context)
static void	SlabStats (MemoryContext context, MemoryStatsPrintFunc printfunc, void *passthru, MemoryContextCounters *totals, bool print_to_stderr)
MemoryContext	SlabContextCreate (MemoryContext parent, const char *name, Size blockSize, Size chunkSize)

Variables
static const MemoryContextMethods	SlabMethods

Macro Definition Documentation

SlabBlockGetChunk

#define SlabBlockGetChunk	(		slab,
			block,
			idx
	)

Value:

    ((SlabChunk *) ((char *) (block) + sizeof(SlabBlock)    \
                    + (idx * slab->fullChunkSize)))

Definition at line 118 of file slab.c.

SlabBlockStart

#define SlabBlockStart

(

block

)

((char *) block + sizeof(SlabBlock))

Definition at line 121 of file slab.c.

SlabChunkGetPointer

#define SlabChunkGetPointer

(

chk

)

((void *)(((char *)(chk)) + sizeof(SlabChunk)))

Definition at line 116 of file slab.c.

SlabChunkIndex

#define SlabChunkIndex	(		slab,
			block,
			chunk
	)		(((char *) chunk - SlabBlockStart(block)) / slab->fullChunkSize)

Definition at line 123 of file slab.c.

SlabPointerGetChunk

#define SlabPointerGetChunk

(

ptr

)

((SlabChunk *)(((char *)(ptr)) - sizeof(SlabChunk)))

Definition at line 114 of file slab.c.

Typedef Documentation

SlabBlock

typedef struct SlabBlock SlabBlock

SlabChunk

typedef struct SlabChunk SlabChunk

SlabContext

typedef struct SlabContext SlabContext

Function Documentation

SlabAlloc()

static void * SlabAlloc ( MemoryContext  context, Size  size  )

static

Definition at line 340 of file slab.c.

{
    SlabContext *slab = castNode(SlabContext, context);
    SlabBlock  *block;
    SlabChunk  *chunk;
    int         idx;
 
    Assert(slab);
 
    Assert((slab->minFreeChunks >= 0) &&
           (slab->minFreeChunks < slab->chunksPerBlock));
 
    /* make sure we only allow correct request size */
    if (size != slab->chunkSize)
        elog(ERROR, "unexpected alloc chunk size %zu (expected %zu)",
             size, slab->chunkSize);
 
    /*
     * If there are no free chunks in any existing block, create a new block
     * and put it to the last freelist bucket.
     *
     * slab->minFreeChunks == 0 means there are no blocks with free chunks,
     * thanks to how minFreeChunks is updated at the end of SlabAlloc().
     */
    if (slab->minFreeChunks == 0)
    {
        block = (SlabBlock *) malloc(slab->blockSize);
 
        if (block == NULL)
            return NULL;
 
        block->nfree = slab->chunksPerBlock;
        block->firstFreeChunk = 0;
 
        /*
         * Put all the chunks on a freelist. Walk the chunks and point each
         * one to the next one.
         */
        for (idx = 0; idx < slab->chunksPerBlock; idx++)
        {
            chunk = SlabBlockGetChunk(slab, block, idx);
            *(int32 *) SlabChunkGetPointer(chunk) = (idx + 1);
        }
 
        /*
         * And add it to the last freelist with all chunks empty.
         *
         * We know there are no blocks in the freelist, otherwise we wouldn't
         * need a new block.
         */
        Assert(dlist_is_empty(&slab->freelist[slab->chunksPerBlock]));
 
        dlist_push_head(&slab->freelist[slab->chunksPerBlock], &block->node);
 
        slab->minFreeChunks = slab->chunksPerBlock;
        slab->nblocks += 1;
        context->mem_allocated += slab->blockSize;
    }
 
    /* grab the block from the freelist (even the new block is there) */
    block = dlist_head_element(SlabBlock, node,
                               &slab->freelist[slab->minFreeChunks]);
 
    /* make sure we actually got a valid block, with matching nfree */
    Assert(block != NULL);
    Assert(slab->minFreeChunks == block->nfree);
    Assert(block->nfree > 0);
 
    /* we know index of the first free chunk in the block */
    idx = block->firstFreeChunk;
 
    /* make sure the chunk index is valid, and that it's marked as empty */
    Assert((idx >= 0) && (idx < slab->chunksPerBlock));
 
    /* compute the chunk location block start (after the block header) */
    chunk = SlabBlockGetChunk(slab, block, idx);
 
    /*
     * Update the block nfree count, and also the minFreeChunks as we've
     * decreased nfree for a block with the minimum number of free chunks
     * (because that's how we chose the block).
     */
    block->nfree--;
    slab->minFreeChunks = block->nfree;
 
    /*
     * Remove the chunk from the freelist head. The index of the next free
     * chunk is stored in the chunk itself.
     */
    VALGRIND_MAKE_MEM_DEFINED(SlabChunkGetPointer(chunk), sizeof(int32));
    block->firstFreeChunk = *(int32 *) SlabChunkGetPointer(chunk);
 
    Assert(block->firstFreeChunk >= 0);
    Assert(block->firstFreeChunk <= slab->chunksPerBlock);
 
    Assert((block->nfree != 0 &&
            block->firstFreeChunk < slab->chunksPerBlock) ||
           (block->nfree == 0 &&
            block->firstFreeChunk == slab->chunksPerBlock));
 
    /* move the whole block to the right place in the freelist */
    dlist_delete(&block->node);
    dlist_push_head(&slab->freelist[block->nfree], &block->node);
 
    /*
     * And finally update minFreeChunks, i.e. the index to the block with the
     * lowest number of free chunks. We only need to do that when the block
     * got full (otherwise we know the current block is the right one). We'll
     * simply walk the freelist until we find a non-empty entry.
     */
    if (slab->minFreeChunks == 0)
    {
        for (idx = 1; idx <= slab->chunksPerBlock; idx++)
        {
            if (dlist_is_empty(&slab->freelist[idx]))
                continue;
 
            /* found a non-empty freelist */
            slab->minFreeChunks = idx;
            break;
        }
    }
 
    if (slab->minFreeChunks == slab->chunksPerBlock)
        slab->minFreeChunks = 0;
 
    /* Prepare to initialize the chunk header. */
    VALGRIND_MAKE_MEM_UNDEFINED(chunk, sizeof(SlabChunk));
 
    chunk->block = block;
    chunk->slab = slab;
 
#ifdef MEMORY_CONTEXT_CHECKING
    /* slab mark to catch clobber of "unused" space */
    if (slab->chunkSize < (slab->fullChunkSize - sizeof(SlabChunk)))
    {
        set_sentinel(SlabChunkGetPointer(chunk), size);
        VALGRIND_MAKE_MEM_NOACCESS(((char *) chunk) +
                                   sizeof(SlabChunk) + slab->chunkSize,
                                   slab->fullChunkSize -
                                   (slab->chunkSize + sizeof(SlabChunk)));
    }
#endif
#ifdef RANDOMIZE_ALLOCATED_MEMORY
    /* fill the allocated space with junk */
    randomize_mem((char *) SlabChunkGetPointer(chunk), size);
#endif
 
    Assert(slab->nblocks * slab->blockSize == context->mem_allocated);
 
    return SlabChunkGetPointer(chunk);
}

References Assert(), SlabChunk::block, SlabContext::blockSize, castNode, SlabContext::chunkSize, SlabContext::chunksPerBlock, dlist_delete(), dlist_head_element, dlist_is_empty(), dlist_push_head(), elog, ERROR, SlabBlock::firstFreeChunk, SlabContext::freelist, SlabContext::fullChunkSize, idx(), malloc, MemoryContextData::mem_allocated, SlabContext::minFreeChunks, SlabContext::nblocks, SlabBlock::nfree, SlabBlock::node, SlabChunk::slab, SlabBlockGetChunk, SlabChunkGetPointer, VALGRIND_MAKE_MEM_DEFINED, VALGRIND_MAKE_MEM_NOACCESS, and VALGRIND_MAKE_MEM_UNDEFINED.

SlabContextCreate()

MemoryContext SlabContextCreate	(	MemoryContext	parent,
		const char *	name,
		Size	blockSize,
		Size	chunkSize
	)

Definition at line 175 of file slab.c.

{
    int         chunksPerBlock;
    Size        fullChunkSize;
    Size        freelistSize;
    Size        headerSize;
    SlabContext *slab;
    int         i;
 
    /* Assert we padded SlabChunk properly */
    StaticAssertStmt(sizeof(SlabChunk) == MAXALIGN(sizeof(SlabChunk)),
                     "sizeof(SlabChunk) is not maxaligned");
    StaticAssertStmt(offsetof(SlabChunk, slab) + sizeof(MemoryContext) ==
                     sizeof(SlabChunk),
                     "padding calculation in SlabChunk is wrong");
 
    /* Make sure the linked list node fits inside a freed chunk */
    if (chunkSize < sizeof(int))
        chunkSize = sizeof(int);
 
    /* chunk, including SLAB header (both addresses nicely aligned) */
    fullChunkSize = sizeof(SlabChunk) + MAXALIGN(chunkSize);
 
    /* Make sure the block can store at least one chunk. */
    if (blockSize < fullChunkSize + sizeof(SlabBlock))
        elog(ERROR, "block size %zu for slab is too small for %zu chunks",
             blockSize, chunkSize);
 
    /* Compute maximum number of chunks per block */
    chunksPerBlock = (blockSize - sizeof(SlabBlock)) / fullChunkSize;
 
    /* The freelist starts with 0, ends with chunksPerBlock. */
    freelistSize = sizeof(dlist_head) * (chunksPerBlock + 1);
 
    /*
     * Allocate the context header.  Unlike aset.c, we never try to combine
     * this with the first regular block; not worth the extra complication.
     */
 
    /* Size of the memory context header */
    headerSize = offsetof(SlabContext, freelist) + freelistSize;
 
#ifdef MEMORY_CONTEXT_CHECKING
 
    /*
     * With memory checking, we need to allocate extra space for the bitmap of
     * free chunks. The bitmap is an array of bools, so we don't need to worry
     * about alignment.
     */
    headerSize += chunksPerBlock * sizeof(bool);
#endif
 
    slab = (SlabContext *) malloc(headerSize);
    if (slab == NULL)
    {
        MemoryContextStats(TopMemoryContext);
        ereport(ERROR,
                (errcode(ERRCODE_OUT_OF_MEMORY),
                 errmsg("out of memory"),
                 errdetail("Failed while creating memory context \"%s\".",
                           name)));
    }
 
    /*
     * Avoid writing code that can fail between here and MemoryContextCreate;
     * we'd leak the header if we ereport in this stretch.
     */
 
    /* Fill in SlabContext-specific header fields */
    slab->chunkSize = chunkSize;
    slab->fullChunkSize = fullChunkSize;
    slab->blockSize = blockSize;
    slab->headerSize = headerSize;
    slab->chunksPerBlock = chunksPerBlock;
    slab->minFreeChunks = 0;
    slab->nblocks = 0;
 
    /* initialize the freelist slots */
    for (i = 0; i < (slab->chunksPerBlock + 1); i++)
        dlist_init(&slab->freelist[i]);
 
#ifdef MEMORY_CONTEXT_CHECKING
    /* set the freechunks pointer right after the freelists array */
    slab->freechunks
        = (bool *) slab + offsetof(SlabContext, freelist) + freelistSize;
#endif
 
    /* Finally, do the type-independent part of context creation */
    MemoryContextCreate((MemoryContext) slab,
                        T_SlabContext,
                        &SlabMethods,
                        parent,
                        name);
 
    return (MemoryContext) slab;
}

References SlabContext::blockSize, SlabContext::chunkSize, SlabContext::chunksPerBlock, dlist_init(), elog, ereport, errcode(), errdetail(), errmsg(), ERROR, SlabContext::freelist, SlabContext::fullChunkSize, SlabContext::headerSize, i, malloc, MAXALIGN, MemoryContextCreate(), MemoryContextStats(), SlabContext::minFreeChunks, name, SlabContext::nblocks, offsetof, SlabMethods, StaticAssertStmt, T_SlabContext, and TopMemoryContext.

Referenced by ReorderBufferAllocate().

SlabDelete()

static void SlabDelete ( MemoryContext  context )

static

Definition at line 326 of file slab.c.

{
    /* Reset to release all the SlabBlocks */
    SlabReset(context);
    /* And free the context header */
    free(context);
}

References free, and SlabReset().

SlabFree()

static void SlabFree ( MemoryContext  context, void *  pointer  )

static

Definition at line 498 of file slab.c.

{
    int         idx;
    SlabContext *slab = castNode(SlabContext, context);
    SlabChunk  *chunk = SlabPointerGetChunk(pointer);
    SlabBlock  *block = chunk->block;
 
#ifdef MEMORY_CONTEXT_CHECKING
    /* Test for someone scribbling on unused space in chunk */
    if (slab->chunkSize < (slab->fullChunkSize - sizeof(SlabChunk)))
        if (!sentinel_ok(pointer, slab->chunkSize))
            elog(WARNING, "detected write past chunk end in %s %p",
                 slab->header.name, chunk);
#endif
 
    /* compute index of the chunk with respect to block start */
    idx = SlabChunkIndex(slab, block, chunk);
 
    /* add chunk to freelist, and update block nfree count */
    *(int32 *) pointer = block->firstFreeChunk;
    block->firstFreeChunk = idx;
    block->nfree++;
 
    Assert(block->nfree > 0);
    Assert(block->nfree <= slab->chunksPerBlock);
 
#ifdef CLOBBER_FREED_MEMORY
    /* XXX don't wipe the int32 index, used for block-level freelist */
    wipe_mem((char *) pointer + sizeof(int32),
             slab->chunkSize - sizeof(int32));
#endif
 
    /* remove the block from a freelist */
    dlist_delete(&block->node);
 
    /*
     * See if we need to update the minFreeChunks field for the slab - we only
     * need to do that if there the block had that number of free chunks
     * before we freed one. In that case, we check if there still are blocks
     * in the original freelist and we either keep the current value (if there
     * still are blocks) or increment it by one (the new block is still the
     * one with minimum free chunks).
     *
     * The one exception is when the block will get completely free - in that
     * case we will free it, se we can't use it for minFreeChunks. It however
     * means there are no more blocks with free chunks.
     */
    if (slab->minFreeChunks == (block->nfree - 1))
    {
        /* Have we removed the last chunk from the freelist? */
        if (dlist_is_empty(&slab->freelist[slab->minFreeChunks]))
        {
            /* but if we made the block entirely free, we'll free it */
            if (block->nfree == slab->chunksPerBlock)
                slab->minFreeChunks = 0;
            else
                slab->minFreeChunks++;
        }
    }
 
    /* If the block is now completely empty, free it. */
    if (block->nfree == slab->chunksPerBlock)
    {
        free(block);
        slab->nblocks--;
        context->mem_allocated -= slab->blockSize;
    }
    else
        dlist_push_head(&slab->freelist[block->nfree], &block->node);
 
    Assert(slab->nblocks >= 0);
    Assert(slab->nblocks * slab->blockSize == context->mem_allocated);
}

References Assert(), SlabChunk::block, SlabContext::blockSize, castNode, SlabContext::chunkSize, SlabContext::chunksPerBlock, dlist_delete(), dlist_is_empty(), dlist_push_head(), elog, SlabBlock::firstFreeChunk, free, SlabContext::freelist, SlabContext::fullChunkSize, SlabContext::header, idx(), MemoryContextData::mem_allocated, SlabContext::minFreeChunks, MemoryContextData::name, SlabContext::nblocks, SlabBlock::nfree, SlabBlock::node, SlabChunkIndex, SlabPointerGetChunk, and WARNING.

SlabGetChunkSpace()

static Size SlabGetChunkSpace ( MemoryContext  context, void *  pointer  )

static

Definition at line 606 of file slab.c.

{
    SlabContext *slab = castNode(SlabContext, context);
 
    Assert(slab);
 
    return slab->fullChunkSize;
}

References Assert(), castNode, and SlabContext::fullChunkSize.

SlabIsEmpty()

static bool SlabIsEmpty ( MemoryContext  context )

static

Definition at line 620 of file slab.c.

{
    SlabContext *slab = castNode(SlabContext, context);
 
    Assert(slab);
 
    return (slab->nblocks == 0);
}

References Assert(), castNode, and SlabContext::nblocks.

SlabRealloc()

static void * SlabRealloc ( MemoryContext  context, void *  pointer, Size  size  )

static

Definition at line 586 of file slab.c.

{
    SlabContext *slab = castNode(SlabContext, context);
 
    Assert(slab);
 
    /* can't do actual realloc with slab, but let's try to be gentle */
    if (size == slab->chunkSize)
        return pointer;
 
    elog(ERROR, "slab allocator does not support realloc()");
    return NULL;                /* keep compiler quiet */
}

References Assert(), castNode, SlabContext::chunkSize, elog, and ERROR.

SlabReset()

static void SlabReset ( MemoryContext  context )

static

Definition at line 283 of file slab.c.

{
    int         i;
    SlabContext *slab = castNode(SlabContext, context);
 
    Assert(slab);
 
#ifdef MEMORY_CONTEXT_CHECKING
    /* Check for corruption and leaks before freeing */
    SlabCheck(context);
#endif
 
    /* walk over freelists and free the blocks */
    for (i = 0; i <= slab->chunksPerBlock; i++)
    {
        dlist_mutable_iter miter;
 
        dlist_foreach_modify(miter, &slab->freelist[i])
        {
            SlabBlock  *block = dlist_container(SlabBlock, node, miter.cur);
 
            dlist_delete(miter.cur);
 
#ifdef CLOBBER_FREED_MEMORY
            wipe_mem(block, slab->blockSize);
#endif
            free(block);
            slab->nblocks--;
            context->mem_allocated -= slab->blockSize;
        }
    }
 
    slab->minFreeChunks = 0;
 
    Assert(slab->nblocks == 0);
    Assert(context->mem_allocated == 0);
}

References Assert(), SlabContext::blockSize, castNode, SlabContext::chunksPerBlock, dlist_mutable_iter::cur, dlist_container, dlist_delete(), dlist_foreach_modify, free, SlabContext::freelist, i, MemoryContextData::mem_allocated, SlabContext::minFreeChunks, and SlabContext::nblocks.

Referenced by SlabDelete().

SlabStats()

static void SlabStats ( MemoryContext  context, MemoryStatsPrintFunc  printfunc, void *  passthru, MemoryContextCounters *  totals, bool  print_to_stderr  )

static

Definition at line 639 of file slab.c.

{
    SlabContext *slab = castNode(SlabContext, context);
    Size        nblocks = 0;
    Size        freechunks = 0;
    Size        totalspace;
    Size        freespace = 0;
    int         i;
 
    /* Include context header in totalspace */
    totalspace = slab->headerSize;
 
    for (i = 0; i <= slab->chunksPerBlock; i++)
    {
        dlist_iter  iter;
 
        dlist_foreach(iter, &slab->freelist[i])
        {
            SlabBlock  *block = dlist_container(SlabBlock, node, iter.cur);
 
            nblocks++;
            totalspace += slab->blockSize;
            freespace += slab->fullChunkSize * block->nfree;
            freechunks += block->nfree;
        }
    }
 
    if (printfunc)
    {
        char        stats_string[200];
 
        snprintf(stats_string, sizeof(stats_string),
                 "%zu total in %zu blocks; %zu free (%zu chunks); %zu used",
                 totalspace, nblocks, freespace, freechunks,
                 totalspace - freespace);
        printfunc(context, passthru, stats_string, print_to_stderr);
    }
 
    if (totals)
    {
        totals->nblocks += nblocks;
        totals->freechunks += freechunks;
        totals->totalspace += totalspace;
        totals->freespace += freespace;
    }
}

References SlabContext::blockSize, castNode, SlabContext::chunksPerBlock, dlist_iter::cur, dlist_container, dlist_foreach, MemoryContextCounters::freechunks, SlabContext::freelist, MemoryContextCounters::freespace, SlabContext::fullChunkSize, SlabContext::headerSize, i, MemoryContextCounters::nblocks, SlabBlock::nfree, snprintf, and MemoryContextCounters::totalspace.

Variable Documentation

SlabMethods

const MemoryContextMethods SlabMethods

static

Initial value:

= {
    SlabAlloc,
    SlabFree,
    SlabRealloc,
    SlabReset,
    SlabDelete,
    SlabGetChunkSpace,
    SlabIsEmpty,
    SlabStats
 
 
 
}

Definition at line 147 of file slab.c.

Referenced by SlabContextCreate().