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)
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.

Referenced by SlabAlloc(), and SlabStats().

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.

Referenced by SlabAlloc(), and SlabStats().

SlabChunkIndex

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

Definition at line 123 of file slab.c.

Referenced by SlabFree().

SlabPointerGetChunk

#define SlabPointerGetChunk

(

ptr

)

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

Definition at line 114 of file slab.c.

Referenced by SlabFree().

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 339 of file slab.c.

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.

{
    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);
}

SlabContextCreate()

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

Definition at line 174 of file slab.c.

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(), offsetof, StaticAssertStmt, T_SlabContext, and TopMemoryContext.

Referenced by ReorderBufferAllocate().

{
    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;
}

SlabDelete()

static void SlabDelete ( MemoryContext  context )

static

Definition at line 325 of file slab.c.

References free, and SlabReset().

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

SlabFree()

static void SlabFree ( MemoryContext  context, void *  pointer  )

static

Definition at line 497 of file slab.c.

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.

{
    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);
}

SlabGetChunkSpace()

static Size SlabGetChunkSpace ( MemoryContext  context, void *  pointer  )

static

Definition at line 605 of file slab.c.

References Assert, castNode, and SlabContext::fullChunkSize.

{
    SlabContext *slab = castNode(SlabContext, context);

    Assert(slab);

    return slab->fullChunkSize;
}

SlabIsEmpty()

static bool SlabIsEmpty ( MemoryContext  context )

static

Definition at line 619 of file slab.c.

References Assert, castNode, and SlabContext::nblocks.

{
    SlabContext *slab = castNode(SlabContext, context);

    Assert(slab);

    return (slab->nblocks == 0);
}

SlabRealloc()

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

static

Definition at line 585 of file slab.c.

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

{
    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 */
}

SlabReset()

static void SlabReset ( MemoryContext  context )

static

Definition at line 282 of file slab.c.

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().

{
    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);
}

SlabStats()

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

static

Definition at line 637 of file slab.c.

References Assert, SlabChunk::block, SlabContext::blockSize, castNode, SlabContext::chunkSize, SlabContext::chunksPerBlock, dlist_iter::cur, dlist_container, dlist_foreach, elog, SlabBlock::firstFreeChunk, MemoryContextCounters::freechunks, SlabContext::freelist, MemoryContextCounters::freespace, SlabContext::fullChunkSize, SlabContext::header, SlabContext::headerSize, i, idx(), MemoryContextData::mem_allocated, MemoryContextData::name, name, MemoryContextCounters::nblocks, SlabContext::nblocks, SlabBlock::nfree, SlabChunk::slab, SlabBlockGetChunk, SlabChunkGetPointer, snprintf, MemoryContextCounters::totalspace, VALGRIND_MAKE_MEM_DEFINED, and WARNING.

{
    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 %zd blocks; %zu free (%zd chunks); %zu used",
                 totalspace, nblocks, freespace, freechunks,
                 totalspace - freespace);
        printfunc(context, passthru, stats_string);
    }

    if (totals)
    {
        totals->nblocks += nblocks;
        totals->freechunks += freechunks;
        totals->totalspace += totalspace;
        totals->freespace += freespace;
    }
}

Variable Documentation

SlabMethods

const MemoryContextMethods SlabMethods

static

Initial value:

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



}

Definition at line 146 of file slab.c.