Subject: Re: PATCH: two slab-like memory allocators
To: Andres Freund <andres@anarazel.de>
References: 
 <CALkS6B8hisTEJJ7ZCQ_GiBLNVzKfsevAD+92rYN6myyFK=UQtw@mail.gmail.com>
 <11821eb9-95a5-353e-ccba-13e8e9351e62@2ndquadrant.com>
 <b8ded0aa-2515-7ffd-162b-8f515df5eca1@2ndquadrant.com>
 <CA+Tgmob7u4thiBbdvyseQk1aVApJeG10C_rFFt8LPV03-UzD7g@mail.gmail.com>
 <a4593432-c989-8ec4-2320-943e3f97ce6d@2ndquadrant.com>
 <CA+TgmobJrM74FRTcmn2JDMVbLB0a5pj5e3ieLBMzkDNtrxF4dw@mail.gmail.com>
 <9818b54a-fcb6-f018-0b16-96d6a1d1da27@2ndquadrant.com>
 <34a6d4ea-7f3d-a62c-fff1-7a9108c078d7@2ndquadrant.com>
 <f2aaf4a5-412c-a4b9-389d-c9f682fbdc77@2ndquadrant.com>
 <4f176a6c-c197-165d-dee4-5de8f279f1f4@2ndquadrant.com>
 <20161112191257.3a4n6kzegvu637qn@alap3.anarazel.de>
Cc: Petr Jelinek <petr@2ndquadrant.com>, Robert Haas <robertmhaas@gmail.com>,
 John Gorman <johngorman2@gmail.com>,
 pgsql-hackers <pgsql-hackers@postgresql.org>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <efd47210-cf95-d7ee-e984-a873f76596a8@2ndquadrant.com>
Date: Mon, 14 Nov 2016 01:20:00 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:46.0) Gecko/20100101
 Thunderbird/46.0a2
MIME-Version: 1.0
In-Reply-To: <20161112191257.3a4n6kzegvu637qn@alap3.anarazel.de>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

On 11/12/2016 08:12 PM, Andres Freund wrote:
> Hi,
>
> Subject: [PATCH 1/2] slab allocator
>
> diff --git a/src/backend/replication/logical/reorderbuffer.c b/src/backend/replication/logical/reorderbuffer.c
> index 6ad7e7d..520f295 100644
> --- a/src/backend/replication/logical/reorderbuffer.c
> +++ b/src/backend/replication/logical/reorderbuffer.c
>
> I'd rather have that in a separate followup commit...
>
>
> + * IDENTIFICATION
> + *	  src/backend/utils/mmgr/slab.c
> + *
> + *
> + *	The constant allocation size allows significant simplification and various
> + *	optimizations that are not possible in AllocSet. Firstly, we can get rid
> + *	of the doubling and carve the blocks into chunks of exactly the right size
> + *	(plus alignment), not wasting memory.
>
> References to AllocSet aren't necessarily a good idea, they'll quite
> possibly get out of date. The argument can be quite easily be made
> without referring to a concrete reference to behaviour elsewhere.
>

Yeah, that's probably true.

> + *
> + *	At the context level, we use 'freelist' array to track blocks grouped by
> + *	number of free chunks. For example freelist[0] is a list of completely full
> + *	blocks, freelist[1] is a block with a single free chunk, etc.
>
> Hm. Those arrays are going to be quite large for small allocations w/
> big blocks (an imo sensible combination). Maybe it'd make more sense to
> model it as a linked list of blocks? Full blocks are at one end, empty
> ones at the other?

So there'd be one huge list of blocks, sorted by the number of empty 
chunks? Hmm, that might work I guess.

I don't think the combination of large blocks with small allocations is 
particularly sensible, though - what exactly would be the benefit of 
such combination? I would even consider enforcing some upper limit on 
the number of chunks per block - say, 256, for example.

>
>
> + *	About MEMORY_CONTEXT_CHECKING:
> + *
> + *	Since we usually round request sizes up to the next power of 2, there
> + *	is often some unused space immediately after a requested data
> area.
>
> I assume the "round up" stuff is copy-paste?
>

Yeah, sorry about that.

>
> + *	Thus, if someone makes the common error of writing past what they've
> + *	requested, the problem is likely to go unnoticed ... until the day when
> + *	there *isn't* any wasted space, perhaps because of different memory
> + *	...
> + *
> + *	See also the cooperating Valgrind client requests in mcxt.c.
>
> I think we need a preliminary patch moving a lot of this into something
> like mcxt_internal.h. Copying this comment, and a lot of the utility
> functions, into every memory context implementation is a bad pattern.
>

Yes, I planned to do that for the next version of patch. Laziness.

>
> +typedef struct SlabBlockData *SlabBlock;		/* forward reference */
> +typedef struct SlabChunkData *SlabChunk;
>
> Can we please not continue hiding pointers behind typedefs? It's a bad
> pattern, and that it's fairly widely used isn't a good excuse to
> introduce further usages of it.
>

Why is it a bad pattern?

> +/*
> + * SlabContext is a specialized implementation of MemoryContext.
> + */
> +typedef struct SlabContext
> +{
> +	MemoryContextData header;	/* Standard memory-context fields */
> +	/* Allocation parameters for this context: */
> +	Size		chunkSize;		/* chunk size */
> +	Size		fullChunkSize;	/* chunk size including header and alignment */
> +	Size		blockSize;		/* block size */
> +	int			chunksPerBlock;	/* number of chunks per block */
> +	int			minFreeChunks;	/* min number of free chunks in any block */
> +	int			nblocks;		/* number of blocks allocated */
> +	/* Info about storage allocated in this context: */
> +	SlabBlock	freelist[1];	/* free lists (block-level) */
>
> I assume this is a variable-length array? If so, that a) should be
> documented b) use FLEXIBLE_ARRAY_MEMBER as length - not doing so
> actually will cause compiler warnings and potential misoptimizations.
>

Will fix, thanks.

> +/*
> + * SlabBlockData
> + *		Structure of a single block in SLAB allocator.
> + *
> + * slab: context owning this block
>
> What do we need this for?
>

You're right the pointer to the owning context is unnecessary - there's 
nothing like "standard block header" and we already have the pointer in 
the standard chunk header. But maybe keeping the pointer at least with 
MEMORY_CONTEXT_CHECKING would be a good idea?

> + * prev, next: used for doubly-linked list of blocks in global freelist
>
> I'd prefer using an embedded list here (cf. ilist.h).
>

Makes sense.

> +/*
> + * SlabChunk
> + *		The prefix of each piece of memory in an SlabBlock
> + *
> + * NB: this MUST match StandardChunkHeader as defined by utils/memutils.h.
> + * However it's possible to fields in front of the StandardChunkHeader fields,
> + * which is used to add pointer to the block.
> + */
>
> Wouldn't that be easier to enforce - particularly around alignment
> requirements - by embedding a StandardChunkHeader here? That'd also
> avoid redundancies.
>

Also makes sense.

> +/* ----------
> + * Debug macros
> + * ----------
> + */
> +#ifdef HAVE_ALLOCINFO
> +#define SlabFreeInfo(_cxt, _chunk) \
> +			fprintf(stderr, "SlabFree: %s: %p, %d\n", \
> +				(_cxt)->header.name, (_chunk), (_chunk)->size)
> +#define SlabAllocInfo(_cxt, _chunk) \
> +			fprintf(stderr, "SlabAlloc: %s: %p, %d\n", \
> +				(_cxt)->header.name, (_chunk), (_chunk)->size)
> +#else
> +#define SlabFreeInfo(_cxt, _chunk)
> +#define SlabAllocInfo(_cxt, _chunk)
> +#endif
>
> Do we really have to copy that stuff from aset.c? Obviously no-one uses
> that, since it doesn't even compile cleanly if HAVE_ALLOCINFO is
> defined:
> /home/andres/src/postgresql/src/backend/utils/mmgr/aset.c:302:20: warning: format ‘%d’ expects argument of type ‘int’, but argument 5 has type ‘Size {aka long unsigned int}’ [-Wformat=]
>     fprintf(stderr, "AllocAlloc: %s: %p, %d\n", \
>

I don't really care. Sure, we should fix the warning, but not supporting 
HAVE_ALLOCINFO in the new allocator(s) seems wrong - we should either 
support it everywhere, or we should rip it out. That's not the purpose 
of this patch, though.

>
> +#ifdef CLOBBER_FREED_MEMORY
> +
> +/* Wipe freed memory for debugging purposes */
> +static void
> +wipe_mem(void *ptr, size_t size)
>
> +#ifdef MEMORY_CONTEXT_CHECKING
> +static void
> +set_sentinel(void *base, Size offset)
> +
> +static bool
> +sentinel_ok(const void *base, Size offset)
> +#endif
>
> +#ifdef RANDOMIZE_ALLOCATED_MEMORY
> +static void
> +randomize_mem(char *ptr, size_t size)
>
> Let's move these into an mcxt_internal.h or mcxt_impl.h or such, as
> static inlines.
>

Yes, next to the valgrind stuff.

> +MemoryContext
> +SlabContextCreate(MemoryContext parent,
> +					  const char *name,
> +					  Size blockSize,
> +					  Size chunkSize)
> +{
> +	int		chunksPerBlock;
> +	Size	fullChunkSize;
> +	Slab	set;
> +
> +	/* chunk, including SLAB header (both addresses nicely aligned) */
> +	fullChunkSize = MAXALIGN(sizeof(SlabChunkData) + MAXALIGN(chunkSize));
>
> +	/* make sure the block can store at least one chunk (plus a bitmap) */
> +	if (blockSize - sizeof(SlabChunkData) < fullChunkSize + 1)
> +		elog(ERROR, "block size %ld for slab is too small for chunks %ld",
> +					blockSize, chunkSize);
>
> I assume the 1 is the bitmap size?
>

Yes, the smallest bitmap is 1 byte.

>
> +	/* so how many chunks can we fit into a block, including header and bitmap? */
> +	chunksPerBlock
> +		=  (8 * (blockSize - sizeof(SlabBlockData)) - 7) / (8 * fullChunkSize + 1);
>
> I'm slightly drunk due to bad airline wine, but right now that seems a
> bit odd and/or documentation worthy. I understand the (xxx + 7) / 8
> pattern elsewhere, but right now I can't follow the - 7.
>

We need all the bits (header, chunks and bitmap) to fit onto the block, 
so this needs to hold:

    blockSize >= sizeof(SlabBlockData) +
                 chunksPerBlock * fullChunkSize +
                 (chunksPerBlock + 7) / 8

solve for 'chunksPerBlock' and you'll get the above formula. Moving the 
7 to the other side of the inequality is the reason for the minus.

But documenting this is probably a good idea.

> +/*
> + * SlabAlloc
> + *		Returns pointer to allocated memory of given size or NULL if
> + *		request could not be completed; memory is added to the set.
> + *
> + * No request may exceed:
> + *		MAXALIGN_DOWN(SIZE_MAX) - SLAB_BLOCKHDRSZ - SLAB_CHUNKHDRSZ
> + * All callers use a much-lower limit.
>
> That seems like a meaningless comment in the context of a slab allocator
> with a fixed size.
>

Why? It might be worth moving this to SlabContextCreate though.

>
> +	/*
> +	 * If there are no free chunks in any existing block, create a new block
> +	 * and put it to the last freelist bucket.
> +	 *
> +	 * (set->minFreeChunks == 0) means there are no blocks with free chunks,
> +	 * thanks to how minFreeChunks is updated at the end of SlabAlloc().
> +	 */
> +	if (set->minFreeChunks == 0)
> +	{
> +		block = (SlabBlock)malloc(set->blockSize);
>
> Space after cast - maybe run pgindent over the file before submission?
> Doing that manually helps to avoid ugly damange by the per-release run
> later. I'm pretty sure there'll be a significant number of changes.
>

Will do.

>
>
> +	if (block->nfree == 0)
> +		block->firstFreeChunk = set->chunksPerBlock;
> +	else
> +	{
> +		/* look for the next free chunk in the block, after the first one */
> +		while ((++block->firstFreeChunk) < set->chunksPerBlock)
> +		{
> +			int byte = block->firstFreeChunk / 8;
> +			int bit  = block->firstFreeChunk % 8;
> +
> +			/* stop when you find 0 (unused chunk) */
> +			if (! (block->bitmapptr[byte] & (0x01 << bit)))
> +				break;
> +		}
>
> I haven't profiled (or even compiled) this patchset yet, but FWIW, in
> the tuple deforming code, I could measure a noticeable speedup by
> accessing bitmap-bytes in the native word-size, rather than char. I'm
> *NOT* saying you should do that, but if this ever shows up as a
> bottlneck, it might be worthwhile to optimize.
>

OK, will try, although I don't expect this branch to be very hot.

> +	/*
> +	 * 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 (set->minFreeChunks == 0)
> +		for (idx = 1; idx <= set->chunksPerBlock; idx++)
> +			if (set->freelist[idx])
> +			{
> +				set->minFreeChunks = idx;
> +				break;
> +			}
>
> Yuck. This definitely needs braces.
>

OK ;-)


thanks

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers