Improve performance of and reduce overheads of memory management

Whenever we palloc a chunk of memory, traditionally, we prefix the
returned pointer with a pointer to the memory context to which the chunk
belongs.  This is required so that we're able to easily determine the
owning context when performing operations such as pfree() and repalloc().

For the AllocSet context, prior to this commit we additionally prefixed
the pointer to the owning context with the size of the chunk.  This made
the header 16 bytes in size.  This 16-byte overhead was required for all
AllocSet allocations regardless of the allocation size.

For the generation context, the problem was worse; in addition to the
pointer to the owning context and chunk size, we also stored a pointer to
the owning block so that we could track the number of freed chunks on a
block.

The slab allocator had a 16-byte chunk header.

The changes being made here reduce the chunk header size down to just 8
bytes for all 3 of our memory context types.  For small to medium sized
allocations, this significantly increases the number of chunks that we can
fit on a given block which results in much more efficient use of memory.

Additionally, this commit completely changes the rule that pointers to
palloc'd memory must be directly prefixed by a pointer to the owning
memory context and instead, we now insist that they're directly prefixed
by an 8-byte value where the least significant 3-bits are set to a value
to indicate which type of memory context the pointer belongs to.  Using
those 3 bits as an index (known as MemoryContextMethodID) to a new array
which stores the methods for each memory context type, we're now able to
pass the pointer given to functions such as pfree() and repalloc() to the
function specific to that context implementation to allow them to devise
their own methods of finding the memory context which owns the given
allocated chunk of memory.

The reason we're able to reduce the chunk header down to just 8 bytes is
because of the way we make use of the remaining 61 bits of the required
8-byte chunk header.  Here we also implement a general-purpose MemoryChunk
struct which makes use of those 61 remaining bits to allow the storage of
a 30-bit value which the MemoryContext is free to use as it pleases, and
also the number of bytes which must be subtracted from the chunk to get a
reference to the block that the chunk is stored on (also 30 bits).  The 1
additional remaining bit is to denote if the chunk is an "external" chunk
or not.  External here means that the chunk header does not store the
30-bit value or the block offset.  The MemoryContext can use these
external chunks at any time, but must use them if any of the two 30-bit
fields are not large enough for the value(s) that need to be stored in
them.  When the chunk is marked as external, it is up to the MemoryContext
to devise its own means to determine the block offset.

Using 3-bits for the MemoryContextMethodID does mean we're limiting
ourselves to only having a maximum of 8 different memory context types.
We could reduce the bit space for the 30-bit value a little to make way
for more than 3 bits, but it seems like it might be better to do that only
if we ever need more than 8 context types.  This would only be a problem
if some future memory context type which does not use MemoryChunk really
couldn't give up any of the 61 remaining bits in the chunk header.

With this MemoryChunk, each of our 3 memory context types can quickly
obtain a reference to the block any given chunk is located on.  AllocSet
is able to find the context to which the chunk is owned, by first
obtaining a reference to the block by subtracting the block offset as is
stored in the 'hdrmask' field and then referencing the block's 'aset'
field.  The Generation context uses the same method, but GenerationBlock
did not have a field pointing back to the owning context, so one is added
by this commit.

In aset.c and generation.c, all allocations larger than allocChunkLimit
are stored on dedicated blocks.  When there's just a single chunk on a
block like this, it's easy to find the block from the chunk, we just
subtract the size of the block header from the chunk pointer.  The size of
these chunks is also known as we store the endptr on the block, so we can
just subtract the pointer to the allocated memory from that.  Because we
can easily find the owning block and the size of the chunk for these
dedicated blocks, we just always use external chunks for allocation sizes
larger than allocChunkLimit.  For generation.c, this sidesteps the problem
of non-external MemoryChunks being unable to represent chunk sizes >= 1GB.
This is less of a problem for aset.c as we store the free list index in
the MemoryChunk's spare 30-bit field (the value of which will never be
close to using all 30-bits).  We can easily reverse engineer the chunk size
from this when needed.  Storing this saves AllocSetFree() from having to
make a call to AllocSetFreeIndex() to determine which free list to put the
newly freed chunk on.

For the slab allocator, this commit adds a new restriction that slab
chunks cannot be >= 1GB in size.  If there happened to be any users of
slab.c which used chunk sizes this large, they really should be using
AllocSet instead.

Here we also add a restriction that normal non-dedicated blocks cannot be
1GB or larger.  It's now not possible to pass a 'maxBlockSize' >= 1GB
during the creation of an AllocSet or Generation context.  Allocations can
still be larger than 1GB, it's just these will always be on dedicated
blocks (which do not have the 1GB restriction).

Author: Andres Freund, David Rowley
Discussion: https://postgr.es/m/CAApHDvpjauCRXcgcaL6+e3eqecEHoeRm9D-kcbuvBitgPnW=vw@mail.gmail.com

1 files changed, 237 insertions, 0 deletions

diff --git a/src/include/utils/memutils_memorychunk.h b/src/include/utils/memutils_memorychunk.h
new file mode 100644
index 00000000000..685c177b681
--- /dev/null
+++ b/src/include/utils/memutils_memorychunk.h
@@ -0,0 +1,237 @@
+/*-------------------------------------------------------------------------
+ *
+ * memutils_memorychunk.h
+ *	  Here we define a struct named MemoryChunk which implementations of
+ *	  MemoryContexts may use as a header for chunks of memory they allocate.
+ *
+ * MemoryChunk provides a lightweight header that a MemoryContext can use to
+ * store a reference back to the block the which the given chunk is allocated
+ * on and also an additional 30-bits to store another value such as the size
+ * of the allocated chunk.
+ *
+ * Although MemoryChunks are used by each of our MemoryContexts, future
+ * implementations may choose to implement their own method for storing chunk
+ * headers.  The only requirement is that the header ends with an 8-byte value
+ * which the least significant 3-bits of are set to the MemoryContextMethodID
+ * of the given context.
+ *
+ * By default, a MemoryChunk is 8 bytes in size, however, when
+ * MEMORY_CONTEXT_CHECKING is defined the header becomes 16 bytes in size due
+ * to the additional requested_size field.  The MemoryContext may use this
+ * field for whatever they wish, but it is intended to be used for additional
+ * checks which are only done in MEMORY_CONTEXT_CHECKING builds.
+ *
+ * The MemoryChunk contains a uint64 field named 'hdrmask'.  This field is
+ * used to encode 4 separate pieces of information.  Starting with the least
+ * significant bits of 'hdrmask', the bit space is reserved as follows:
+ *
+ * 1.	3-bits to indicate the MemoryContextMethodID as defined by
+ *		MEMORY_CONTEXT_METHODID_MASK
+ * 2.	1-bit to denote an "external" chunk (see below)
+ * 3.	30-bits reserved for the MemoryContext to use for anything it
+ *		requires.  Most MemoryContext likely want to store the size of the
+ *		chunk here.
+ * 4.	30-bits for the number of bytes that must be subtracted from the chunk
+ *		to obtain the address of the block that the chunk is stored on.
+ *
+ * In some cases, for example when memory allocations become large, it's
+ * possible fields 3 and 4 above are not large enough to store the values
+ * required for the chunk.  In this case, the MemoryContext can choose to mark
+ * the chunk as "external" by calling the MemoryChunkSetExternal() function.
+ * When this is done, fields 3 and 4 are unavailable for use by the
+ * MemoryContext and it's up to the MemoryContext itself to devise its own
+ * method for getting the reference to the block.
+ *
+ * Interface:
+ *
+ * MemoryChunkSetHdrMask:
+ *		Used to set up a non-external MemoryChunk.
+ *
+ * MemoryChunkSetHdrMaskExternal:
+ *		Used to set up an externally managed MemoryChunk.
+ *
+ * MemoryChunkIsExternal:
+ *		Determine if the given MemoryChunk is externally managed, i.e.
+ *		MemoryChunkSetHdrMaskExternal() was called on the chunk.
+ *
+ * MemoryChunkGetValue:
+ *		For non-external chunks, return the stored 30-bit value as it was set
+ *		in the call to MemoryChunkSetHdrMask().
+ *
+ * MemoryChunkGetBlock:
+ *		For non-external chunks, return a pointer to the block as it was set
+ *		in the call to MemoryChunkSetHdrMask().
+ *
+ * Also exports:
+ *		MEMORYCHUNK_MAX_VALUE
+ *		MEMORYCHUNK_MAX_BLOCKOFFSET
+ *		PointerGetMemoryChunk
+ *		MemoryChunkGetPointer
+ *
+ * Portions Copyright (c) 2022, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/utils/memutils_memorychunk.h
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#ifndef MEMUTILS_MEMORYCHUNK_H
+#define MEMUTILS_MEMORYCHUNK_H
+
+#include "utils/memutils_internal.h"
+
+ /*
+  * The maximum allowed value that MemoryContexts can store in the value
+  * field.  Must be 1 less than a power of 2.
+  */
+#define MEMORYCHUNK_MAX_VALUE			UINT64CONST(0x3FFFFFFF)
+
+/*
+ * The maximum distance in bytes that a MemoryChunk can be offset from the
+ * block that is storing the chunk.  Must be 1 less than a power of 2.
+ */
+#define MEMORYCHUNK_MAX_BLOCKOFFSET		UINT64CONST(0x3FFFFFFF)
+
+/* define the least significant base-0 bit of each portion of the hdrmask */
+#define MEMORYCHUNK_EXTERNAL_BASEBIT	MEMORY_CONTEXT_METHODID_BITS
+#define MEMORYCHUNK_VALUE_BASEBIT		(MEMORYCHUNK_EXTERNAL_BASEBIT + 1)
+#define MEMORYCHUNK_BLOCKOFFSET_BASEBIT	(MEMORYCHUNK_VALUE_BASEBIT + 30)
+
+/*
+ * A magic number for storing in the free bits of an external chunk.  This
+ * must mask out the bits used for storing the MemoryContextMethodID and the
+ * external bit.
+ */
+#define MEMORYCHUNK_MAGIC		(UINT64CONST(0xB1A8DB858EB6EFBA) >> \
+								 MEMORYCHUNK_VALUE_BASEBIT << \
+								 MEMORYCHUNK_VALUE_BASEBIT)
+
+typedef struct MemoryChunk
+{
+#ifdef MEMORY_CONTEXT_CHECKING
+	Size		requested_size;
+#endif
+
+	/* bitfield for storing details about the chunk */
+	uint64		hdrmask;		/* must be last */
+} MemoryChunk;
+
+/* Get the MemoryChunk from the pointer */
+#define PointerGetMemoryChunk(p) \
+	((MemoryChunk *) ((char *) (p) - sizeof(MemoryChunk)))
+/* Get the pointer from the MemoryChunk */
+#define MemoryChunkGetPointer(c) \
+	((void *) ((char *) (c) + sizeof(MemoryChunk)))
+
+/* private macros for making the inline functions below more simple */
+#define HdrMaskIsExternal(hdrmask) \
+	((hdrmask) & (((uint64) 1) << MEMORYCHUNK_EXTERNAL_BASEBIT))
+#define HdrMaskGetValue(hdrmask) \
+	(((hdrmask) >> MEMORYCHUNK_VALUE_BASEBIT) & MEMORYCHUNK_MAX_VALUE)
+
+/*
+ * We should have used up all the bits here, so the compiler is likely to
+ * optimize out the & MEMORYCHUNK_MAX_BLOCKOFFSET.
+ */
+#define HdrMaskBlockOffset(hdrmask) \
+	(((hdrmask) >> MEMORYCHUNK_BLOCKOFFSET_BASEBIT) & MEMORYCHUNK_MAX_BLOCKOFFSET)
+
+/* For external chunks only, check the magic number matches */
+#define HdrMaskCheckMagic(hdrmask) \
+	(MEMORYCHUNK_MAGIC == \
+	 ((hdrmask) >> MEMORYCHUNK_VALUE_BASEBIT << MEMORYCHUNK_VALUE_BASEBIT))
+/*
+ * MemoryChunkSetHdrMask
+ *		Store the given 'block', 'chunk_size' and 'methodid' in the given
+ *		MemoryChunk.
+ *
+ * The number of bytes between 'block' and 'chunk' must be <=
+ * MEMORYCHUNK_MAX_BLOCKOFFSET.
+ * 'value' must be <= MEMORYCHUNK_MAX_VALUE.
+ */
+static inline void
+MemoryChunkSetHdrMask(MemoryChunk *chunk, void *block,
+					  Size value, MemoryContextMethodID methodid)
+{
+	Size		blockoffset = (char *) chunk - (char *) block;
+
+	Assert((char *) chunk > (char *) block);
+	Assert(blockoffset <= MEMORYCHUNK_MAX_BLOCKOFFSET);
+	Assert(value <= MEMORYCHUNK_MAX_VALUE);
+	Assert(methodid <= MEMORY_CONTEXT_METHODID_MASK);
+
+	chunk->hdrmask = (((uint64) blockoffset) << MEMORYCHUNK_BLOCKOFFSET_BASEBIT) |
+		(((uint64) value) << MEMORYCHUNK_VALUE_BASEBIT) |
+		methodid;
+}
+
+/*
+ * MemoryChunkSetHdrMaskExternal
+ *		Set 'chunk' as an externally managed chunk.  Here we only record the
+ *		MemoryContextMethodID and set the external chunk bit.
+ */
+static inline void
+MemoryChunkSetHdrMaskExternal(MemoryChunk *chunk,
+							  MemoryContextMethodID methodid)
+{
+	Assert(methodid <= MEMORY_CONTEXT_METHODID_MASK);
+
+	chunk->hdrmask = MEMORYCHUNK_MAGIC | (((uint64) 1) << MEMORYCHUNK_EXTERNAL_BASEBIT) |
+		methodid;
+}
+
+/*
+ * MemoryChunkIsExternal
+ *		Return true if 'chunk' is marked as external.
+ */
+static inline bool
+MemoryChunkIsExternal(MemoryChunk *chunk)
+{
+	/*
+	 * External chunks should always store MEMORYCHUNK_MAGIC in the upper
+	 * portion of the hdrmask, check that nothing has stomped on that.
+	 */
+	Assert(!HdrMaskIsExternal(chunk->hdrmask) ||
+		   HdrMaskCheckMagic(chunk->hdrmask));
+
+	return HdrMaskIsExternal(chunk->hdrmask);
+}
+
+/*
+ * MemoryChunkGetValue
+ *		For non-external chunks, returns the value field as it was set in
+ *		MemoryChunkSetHdrMask.
+ */
+static inline Size
+MemoryChunkGetValue(MemoryChunk *chunk)
+{
+	Assert(!HdrMaskIsExternal(chunk->hdrmask));
+
+	return HdrMaskGetValue(chunk->hdrmask);
+}
+
+/*
+ * MemoryChunkGetBlock
+ *		For non-external chunks, returns the pointer to the block as was set
+ *		in MemoryChunkSetHdrMask.
+ */
+static inline void *
+MemoryChunkGetBlock(MemoryChunk *chunk)
+{
+	Assert(!HdrMaskIsExternal(chunk->hdrmask));
+
+	return (void *) ((char *) chunk - HdrMaskBlockOffset(chunk->hdrmask));
+}
+
+/* cleanup all internal definitions */
+#undef MEMORYCHUNK_EXTERNAL_BASEBIT
+#undef MEMORYCHUNK_VALUE_BASEBIT
+#undef MEMORYCHUNK_BLOCKOFFSET_BASEBIT
+#undef MEMORYCHUNK_MAGIC
+#undef HdrMaskIsExternal
+#undef HdrMaskGetValue
+#undef HdrMaskBlockOffset
+#undef HdrMaskCheckMagic
+
+#endif							/* MEMUTILS_MEMORYCHUNK_H */