Hi Dhruv,
I am formatting your patch, and doing a few minor adjustments
It addresses Andres Freund's feedback
> FWIW, on machines with the necessary hardware support, postgres'
instr_time.h
> should now be quite fast, it's using rdtsc[p] if available.
This version uses instr_time and a a little bit of pre-processing to write
the
benchmark as
+ BEGIN_TIMING("insert", n)
+ int32 j = w_ord[i];
+ BufTableInsert(&ptag[j], phash[j], bufids[j]);
+ END_TIMING
+
+ BEGIN_TIMING("hit", n)
+ int32 j = r_ord[i];
+ sink += BufTableLookup(&ptag[j], phash[j]);
+ END_TIMING
I also increased the number of buckets to make 1/3 < occupation < 2/3
instead of 1/2 < occupation < 1. 100% occupation could produce longer
chains (not critical though, as it is not using open addressing).
> I don't really understand the race condition this is trying to address:
>
>> + /* Unlock buffer header after the entry is deleted to avoid a race
condition:
>> + * If unlocked prior, a concurrent GetVictimBuffer() could insert
a new entry
>> + * for the same buffer and overwrite the entry slot. Then, the
BufTableDelete()
>> + * would be unable to find the entry and would corrupt the
hashtable. */
>> + UnlockBufHdrExt(buf, buf_state,
>> + 0,
>> + BUF_FLAG_MASK | BUF_USAGECOUNT_MASK,
>> + 0);
>
>How could there be a concurrent insertion while the buffer partition lock
is
>held?
I am removing that part as there is a consensus among the big guys that
we shouldn't hold a spin-lock while doing the BufferTableDelete.
I think I could explain why this is necessary, but I want to see your
argument.
Was it safe before? if so, what is the property of dynhash that we lost on
this
patch.
I could argue that BufferTableDelete is safe if we check for the bounds of
.next and make sure there are no cycles in the chain. But again I will let
you elaborate that argument.
Regards,
Alexandre
From 62fd0eea23eab846bed6801017d4ca4a33094b70 Mon Sep 17 00:00:00 2001
From: Dhruv Aron <[email protected]>
Date: Wed, 8 Jul 2026 17:29:00 +0100
Subject: [PATCH] Buffer table test module
This module implements a function buftable_bench_probe that
measures times of inserting, searching and deleting all of them
repeatetedly, and returns each measurement as a row.
This uses "portability/instr_time.h" for time measurement,
Analysis can be performed using SQL e.g.
CREATE EXTENSION buftable_bench;
SELECT rand, op,
avg(avg_ns) AS avg,
min(avg_ns) AS min,
percentile_disc(0.25) WITHIN GROUP (ORDER BY avg_ns) AS \"[q1\",
percentile_disc(0.50) WITHIN GROUP (ORDER BY avg_ns) AS median,
percentile_disc(0.75) WITHIN GROUP (ORDER BY avg_ns) AS \"q3]\",
percentile_disc(0.99) WITHIN GROUP (ORDER BY avg_ns) AS p99,
stddev(avg_ns) AS std
FROM
unnest(ARRAY[false, true]) rand(rand),
LATERAL buftable_bench_probe($N, $ROUNDS, rand)
GROUP BY rand, op, id
ORDER BY id, rand;
---
src/test/modules/buftable_bench/Makefile | 23 ++
.../buftable_bench/buftable_bench--1.0.sql | 19 ++
.../modules/buftable_bench/buftable_bench.c | 223 ++++++++++++++++++
.../buftable_bench/buftable_bench.control | 4 +
src/test/modules/buftable_bench/meson.build | 23 ++
src/test/modules/buftable_bench/no_optimise.c | 27 +++
src/test/modules/buftable_bench/no_optimise.h | 16 ++
7 files changed, 335 insertions(+)
create mode 100644 src/test/modules/buftable_bench/Makefile
create mode 100644 src/test/modules/buftable_bench/buftable_bench--1.0.sql
create mode 100644 src/test/modules/buftable_bench/buftable_bench.c
create mode 100644 src/test/modules/buftable_bench/buftable_bench.control
create mode 100644 src/test/modules/buftable_bench/meson.build
create mode 100644 src/test/modules/buftable_bench/no_optimise.c
create mode 100644 src/test/modules/buftable_bench/no_optimise.h
diff --git a/src/test/modules/buftable_bench/Makefile b/src/test/modules/buftable_bench/Makefile
new file mode 100644
index 00000000000..1f968496cf2
--- /dev/null
+++ b/src/test/modules/buftable_bench/Makefile
@@ -0,0 +1,23 @@
+# src/test/modules/buftable_bench/Makefile
+
+PGFILEDESC = "buftable_bench - rdtsc micro-benchmark for the buffer mapping table"
+
+MODULE_big = buftable_bench
+OBJS = \
+ $(WIN32RES) \
+ buftable_bench.o \
+ no_optimise.o
+
+EXTENSION = buftable_bench
+DATA = buftable_bench--1.0.sql
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = src/test/modules/buftable_bench
+top_builddir = ../../../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
diff --git a/src/test/modules/buftable_bench/buftable_bench--1.0.sql b/src/test/modules/buftable_bench/buftable_bench--1.0.sql
new file mode 100644
index 00000000000..468259d8190
--- /dev/null
+++ b/src/test/modules/buftable_bench/buftable_bench--1.0.sql
@@ -0,0 +1,19 @@
+/* src/test/modules/buftable_bench/buftable_bench--1.0.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "CREATE EXTENSION buftable_bench" to load this file. \quit
+
+CREATE FUNCTION buftable_bench_probe(
+ IN n int8,
+ IN rounds int8 DEFAULT 1,
+ IN random bool DEFAULT true,
+ OUT op text,
+ OUT avg_ns float8,
+ OUT batch_size int8,
+ OUT id int8
+)
+RETURNS SETOF record
+AS 'MODULE_PATHNAME', 'buftable_bench_probe'
+LANGUAGE C;
+
+REVOKE ALL ON FUNCTION buftable_bench_probe(int8, int8, bool) FROM PUBLIC;
diff --git a/src/test/modules/buftable_bench/buftable_bench.c b/src/test/modules/buftable_bench/buftable_bench.c
new file mode 100644
index 00000000000..5575f264183
--- /dev/null
+++ b/src/test/modules/buftable_bench/buftable_bench.c
@@ -0,0 +1,223 @@
+/*-------------------------------------------------------------------------
+ *
+ * buftable_bench.c
+ * Pollution-free in-place benchmark of the shared buffer mapping table.
+ *
+ * Throwaway micro-benchmark module (NOT for upstream). One SQL function,
+ * buftable_bench_probe(n, rounds), times lookup (hit+miss), insert, and delete
+ * by calling BufTable{Insert,Lookup,Delete} DIRECTLY on the real shared table
+ * -- no ReadBuffer, no 8 KB page copy, no per-op timing. Each op's loop is
+ * bulk-timed with a single instr_time pair (RDTSC on x86 when available), so
+ * the measurement isn't polluted by page-copy cache traffic or per-op timer
+ * overhead.
+ *
+ * It works against STOCK PostgreSQL: it only calls the existing public
+ * BufTable* / BufTableHashCode functions, so no core changes are needed -- the
+ * two arms being compared are just two stock builds (flat table vs dynahash).
+ *
+ * Insert/delete mutate the live table, so we only use FREE buffer slots (their
+ * mapping entry is guaranteed empty) and restore the table afterward.
+ *
+ * x86_64 only (rdtsc).
+ *
+ * IDENTIFICATION
+ * src/test/modules/buftable_bench/buftable_bench.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "fmgr.h"
+#include "funcapi.h"
+#include "miscadmin.h"
+#include "portability/instr_time.h"
+#include "storage/buf_internals.h"
+#include "storage/bufmgr.h"
+#include "utils/builtins.h"
+#include "utils/tuplestore.h"
+#include "common/pg_prng.h"
+
+#include "no_optimise.h"
+
+PG_MODULE_MAGIC;
+
+PG_FUNCTION_INFO_V1(buftable_bench_probe);
+
+/*
+ * Auxiliary macros for readability
+*/
+static int64 timing_operation_id = 0;
+#define BEGIN_TIMING(name, n) \
+{\
+ instr_time t0, t1, dt; \
+ Datum values[4]; \
+ bool nulls[4] = {0}; \
+ values[0] = CStringGetTextDatum(name); \
+ INSTR_TIME_SET_CURRENT_FAST(t0); \
+ for(int64 i = 0; i < n; ++i) \
+ {
+
+#define END_TIMING \
+ } \
+ INSTR_TIME_SET_CURRENT_FAST(t1); \
+ INSTR_TIME_SET_ZERO(dt); \
+ INSTR_TIME_ACCUM_DIFF(dt, t1, t0); \
+ values[1] = Float8GetDatum((double)INSTR_TIME_GET_NANOSEC(dt) / (double) (n)); \
+ values[2] = Int64GetDatum(n); \
+ values[3] = Int64GetDatum(++timing_operation_id); \
+ tuplestore_putvalues(rsinfo->setResult, rsinfo->setDesc, values, nulls); \
+}
+
+/* synthetic relfilenodes for bench tags — unlikely to collide with anything real */
+#define BENCH_SPC_OID 0xB0B0
+#define BENCH_DB_OID 0xB1B1
+#define BENCH_REL_PRESENT ((RelFileNumber) 0x7E570001)
+#define BENCH_REL_ABSENT ((RelFileNumber) 0x7E570002)
+
+
+/*
+ * buftable_bench_probe(n, rounds) -> SETOF (op text, avg_ns float8, count int8)
+ *
+ * Rows: insert, lookup_hit, lookup_miss, delete. See file header.
+ */
+Datum
+buftable_bench_probe(PG_FUNCTION_ARGS)
+{
+ int64 n = PG_GETARG_INT64(0);
+ int64 rounds = PG_ARGISNULL(1) ? 1 : PG_GETARG_INT64(1);
+ bool randomize = PG_ARGISNULL(2) ? true : PG_GETARG_BOOL(2);
+ ReturnSetInfo *rsinfo = (ReturnSetInfo *) fcinfo->resultinfo;
+ int *bufids;
+ int32 *r_ord,
+ *w_ord;
+ BufferTag *ptag,
+ *atag;
+ uint64 *phash,
+ *ahash;
+ int64 nfree = 0;
+ volatile int64 sink = 0;
+ RelFileLocator rp = {.spcOid = BENCH_SPC_OID,.dbOid = BENCH_DB_OID,.relNumber = BENCH_REL_PRESENT};
+ RelFileLocator ra = {.spcOid = BENCH_SPC_OID,.dbOid = BENCH_DB_OID,.relNumber = BENCH_REL_ABSENT};
+
+ if (n <= 0 || rounds <= 0)
+ ereport(ERROR, (errmsg("n and rounds must be positive")));
+
+ InitMaterializedSRF(fcinfo, 0);
+
+ /* collect up to n FREE buffer slots (mapping entry guaranteed empty) */
+ bufids = palloc(sizeof(int) * n);
+ for (int i = 0; i < NBuffers && nfree < n; i++)
+ {
+ BufferDesc *desc = GetBufferDescriptor(i);
+ uint64 state = pg_atomic_read_u64(&desc->state);
+
+ if (!(state & BM_TAG_VALID))
+ bufids[nfree++] = i;
+ }
+ n = nfree;
+ if (n == 0)
+ ereport(ERROR, (errmsg("no free buffers to probe with")));
+
+ /* build present + absent tags and their hashes */
+ ptag = palloc(sizeof(BufferTag) * n);
+ atag = palloc(sizeof(BufferTag) * n);
+ phash = palloc(sizeof(uint64) * n);
+ ahash = palloc(sizeof(uint64) * n);
+ for (int64 j = 0; j < n; j++)
+ {
+ InitBufferTag(&ptag[j], &rp, MAIN_FORKNUM, (BlockNumber) j);
+ InitBufferTag(&atag[j], &ra, MAIN_FORKNUM, (BlockNumber) j);
+ phash[j] = BufTableHashCode(&ptag[j]);
+ ahash[j] = BufTableHashCode(&atag[j]);
+ }
+
+ /*
+ * Iteration order over the keys: identity (sequential) or a Fisher-Yates
+ * shuffle (random). A shuffled order makes the timed loops visit keys in
+ * an order uncorrelated with where their entries/elements live, so BOTH
+ * arms' entry/element access is random (not just the bucket access, which
+ * the hash already scatters). Done once in setup (untimed).
+ */
+ r_ord = palloc(sizeof(int64) * n);
+ w_ord = palloc(sizeof(int64) * n);
+ for (int64 i = 0; i < n; i++){
+ r_ord[i] = i;
+ w_ord[i] = i;
+ }
+ if (randomize)
+ {
+ pg_prng_state rng;
+ pg_prng_seed(&rng, 0x9E3779B97F4A7C15ULL);
+
+ for (int64 i = n - 1; i > 0; i--)
+ {
+ int32 k;
+ int32 tmp;
+ k = pg_prng_int64_range(&rng, 0, i);
+ tmp = r_ord[i]; r_ord[i] = r_ord[k]; r_ord[k] = tmp;
+
+ k = pg_prng_int64_range(&rng, 0, i);
+ tmp = w_ord[i]; w_ord[i] = w_ord[k]; w_ord[k] = tmp;
+
+ k = pg_prng_int64_range(&rng, 0, i);
+ tmp = bufids[i]; bufids[i] = bufids[k]; bufids[k] = tmp;
+ }
+
+ }
+
+ if (!timing_initialized)
+ pg_initialize_timing();
+
+ PG_TRY();
+ {
+ for (int64 r = 0; r < rounds; r++)
+ {
+ timing_operation_id = 0;
+ BEGIN_TIMING("insert", n)
+ int32 j = w_ord[i];
+ BufTableInsert(&ptag[j], phash[j], bufids[j]);
+ END_TIMING
+
+ BEGIN_TIMING("hit", n)
+ int32 j = r_ord[i];
+ sink += BufTableLookup(&ptag[j], phash[j]);
+ END_TIMING;
+
+ BEGIN_TIMING("miss", n)
+ int32 j = r_ord[i];
+ sink += BufTableLookup(&atag[j], ahash[j]);
+ END_TIMING
+
+ BEGIN_TIMING("del", n)
+ int32 j = r_ord[i];
+ BufTableDelete(&ptag[j], phash[j]);
+ END_TIMING
+
+ BEGIN_TIMING("hash", n)
+ int32 j = r_ord[i];
+ sink += BufTableHashCode(&ptag[j]);
+ END_TIMING
+
+ BEGIN_TIMING("compare", n)
+ int32 j = r_ord[i];
+ sink += ext_BufferTagsEqual(&ptag[j], &ptag[i]);
+ END_TIMING
+
+ BEGIN_TIMING("nop", n)
+ int32 j = r_ord[i];
+ ext_nop(&ptag[j], phash[j]);
+ END_TIMING
+ }
+ }
+ PG_CATCH();
+ {
+ /* best-effort restore: remove any present tag still mapped */
+ for (int64 j = 0; j < n; j++)
+ if (BufTableLookup(&ptag[j], phash[j]) >= 0)
+ BufTableDelete(&ptag[j], phash[j]);
+ PG_RE_THROW();
+ }
+ PG_END_TRY();
+ (void) sink;
+ return (Datum) 0;
+}
\ No newline at end of file
diff --git a/src/test/modules/buftable_bench/buftable_bench.control b/src/test/modules/buftable_bench/buftable_bench.control
new file mode 100644
index 00000000000..aae6cb1810f
--- /dev/null
+++ b/src/test/modules/buftable_bench/buftable_bench.control
@@ -0,0 +1,4 @@
+comment = 'rdtsc micro-benchmark for the shared buffer mapping table'
+default_version = '1.0'
+module_pathname = '$libdir/buftable_bench'
+relocatable = true
diff --git a/src/test/modules/buftable_bench/meson.build b/src/test/modules/buftable_bench/meson.build
new file mode 100644
index 00000000000..070d79e96b8
--- /dev/null
+++ b/src/test/modules/buftable_bench/meson.build
@@ -0,0 +1,23 @@
+# Copyright (c) 2024-2026, PostgreSQL Global Development Group
+
+buftable_bench_sources = files(
+ 'buftable_bench.c',
+ 'no_optimise.c',
+)
+
+if host_system == 'windows'
+ buftable_bench_sources += rc_lib_gen.process(win32ver_rc, extra_args: [
+ '--NAME', 'buftable_bench',
+ '--FILEDESC', 'buftable_bench - rdtsc micro-benchmark for the buffer mapping table',])
+endif
+
+buftable_bench = shared_module('buftable_bench',
+ buftable_bench_sources,
+ kwargs: pg_test_mod_args,
+)
+test_install_libs += buftable_bench
+
+test_install_data += files(
+ 'buftable_bench.control',
+ 'buftable_bench--1.0.sql',
+)
diff --git a/src/test/modules/buftable_bench/no_optimise.c b/src/test/modules/buftable_bench/no_optimise.c
new file mode 100644
index 00000000000..2fffcd471e8
--- /dev/null
+++ b/src/test/modules/buftable_bench/no_optimise.c
@@ -0,0 +1,27 @@
+/*-------------------------------------------------------------------------
+ *
+ * no_optimise.c
+ * Opaque call targets for the buftable_bench dummy ops.
+ *
+ * These live in a separate translation unit so the compiler compiling
+ * buftable_bench.c cannot see the bodies, inline them, or delete unused
+ * calls. (Does not survive -flto.)
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "no_optimise.h"
+
+void
+ext_nop(BufferTag *tag, uint64 hashcode)
+{
+ (void) tag;
+ (void) hashcode;
+}
+
+bool
+ext_BufferTagsEqual(const BufferTag *tag1, const BufferTag *tag2)
+{
+ return BufferTagsEqual(tag1, tag2);
+}
diff --git a/src/test/modules/buftable_bench/no_optimise.h b/src/test/modules/buftable_bench/no_optimise.h
new file mode 100644
index 00000000000..83f34e353bc
--- /dev/null
+++ b/src/test/modules/buftable_bench/no_optimise.h
@@ -0,0 +1,16 @@
+/*-------------------------------------------------------------------------
+ *
+ * no_optimise.h
+ * Declarations for opaque dummy ops (bodies in no_optimise.c).
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef NO_OPTIMISE_H
+#define NO_OPTIMISE_H
+
+#include "storage/buf_internals.h"
+
+extern void ext_nop(BufferTag *tag, uint64 hashcode);
+extern bool ext_BufferTagsEqual(const BufferTag *tag1, const BufferTag *tag2);
+
+#endif /* NO_OPTIMISE_H */
--
2.53.0
From 62fd0eea23eab846bed6801017d4ca4a33094b70 Mon Sep 17 00:00:00 2001
From: Dhruv Aron <[email protected]>
Date: Wed, 8 Jul 2026 17:29:00 +0100
Subject: [PATCH-v1 1/2] Inline SharedBufHash
Replaces the dynamic hash shared buffer lookup table with an inline
implementation of a separate chaining hash array implementation,
with pinned memory.
buckets[num_buckets] - hash lookup
entries[NBuffers] - linked-list<BufferTag>
buckets are int32 (4 bytes), and entries is a linked list node
containing a buffer tag and a pointer to the next item in the chain
The dynhash previously used required about 56 bytes per entry.
On a 64-bit machine
elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(hctl->entrysize);
With .hash_info.keysize = sizeof(BufferTag) = 20
it was MAXALIGN(12) + MAXALIGN(20) = 16 + 24 = 40
assuming buckets = entries we would have another 8 bytes per bucket head
and 8 bytes per segment, assuming buckets = 2 * entries we would have
stounf 56 + 2*8/256, not too far from allocated size.
The execution flow, in hash_search_with_hash_value had,
in addition to the external call, at least 6 extra branches,
and about the same number of additional pointer dereferences
Memory per bucket reduced from 8 to 4
Memory per entry reduced from 40 to 24
The entries live in a single array about 2k times smaller
than shared_buffers, e.g. 1GB of shared buffers mean 3MB
entries. And about 1MB for buckets (and occupation < 50%).
---
src/backend/storage/buffer/buf_table.c | 224 ++++++++++++++++++-------
1 file changed, 168 insertions(+), 56 deletions(-)
diff --git a/src/backend/storage/buffer/buf_table.c b/src/backend/storage/buffer/buf_table.c
index 347bf267d73..7836d0dd664 100644
--- a/src/backend/storage/buffer/buf_table.c
+++ b/src/backend/storage/buffer/buf_table.c
@@ -3,6 +3,27 @@
* buf_table.c
* routines for mapping BufferTags to buffer indexes.
*
+ * The shared buffer mapping table is a flat, index-linked hash table (an
+ * open-chaining replacement for the former dynahash-based table). It is made
+ * of two shared-memory arrays:
+ *
+ * buckets[num_buckets] - one chain head per hash bucket
+ * entries[NBuffers] - one entry per buffer, indexed by buf_id
+ *
+ * Each buffer slot i permanently owns entry slot i, so no freelist is needed:
+ * bufmgr always removes a buffer's old mapping (BufTableDelete, called from
+ * InvalidateVictimBuffer) before inserting a new tag for that same buf_id (see
+ * GetVictimBuffer / BufferAlloc in bufmgr.c). Empty entry slots are marked by
+ * tag.blockNum == P_NEW; chains are linked by int index and terminated by
+ * BUF_TABLE_CHAIN_END.
+ *
+ * num_buckets is a power of two and a multiple of NUM_BUFFER_PARTITIONS, so the
+ * bucket index (hashcode % num_buckets) shares its low bits with the partition
+ * index (hashcode % NUM_BUFFER_PARTITIONS). Every tag that maps to a given
+ * bucket therefore maps to a single partition, and the caller's BufMappingLock
+ * fully serializes each chain -- the same guarantee the dynahash table relied
+ * on.
+ *
* Note: the routines in this file do no locking of their own. The caller
* must hold a suitable lock on the appropriate BufMappingLock, as specified
* in the comments. We can't do the locking inside these functions because
@@ -21,56 +42,114 @@
*/
#include "postgres.h"
+#include "common/hashfn.h"
+#include "miscadmin.h"
+#include "port/pg_bitutils.h"
#include "storage/buf_internals.h"
+#include "storage/bufmgr.h"
+#include "storage/shmem.h"
#include "storage/subsystems.h"
+#define BUF_TABLE_CHAIN_END (-1)
+
+/* bucket for buffer lookup hashtable */
+typedef struct
+{
+ int head; /* head of hash chain, or BUF_TABLE_CHAIN_END */
+} BufferLookupBucket;
+
/* entry for buffer lookup hashtable */
typedef struct
{
- BufferTag key; /* Tag of a disk page */
- int id; /* Associated buffer ID */
+ BufferTag tag; /* Tag of a disk page, or P_NEW if empty */
+ int next; /* next entry in hash chain */
} BufferLookupEnt;
-static HTAB *SharedBufHash;
+/* bucket and entry arrays for buffer lookup hashtable (in shared memory) */
+static BufferLookupBucket *buckets;
+static BufferLookupEnt *entries;
+
+/* number of hash buckets; power of two and multiple of NUM_BUFFER_PARTITIONS */
+static int num_buckets;
static void BufTableShmemRequest(void *arg);
+static void BufTableShmemInit(void *arg);
+static void BufTableShmemAttach(void *arg);
const ShmemCallbacks BufTableShmemCallbacks = {
.request_fn = BufTableShmemRequest,
- /* no special initialization needed, the hash table will start empty */
+ .init_fn = BufTableShmemInit,
+ .attach_fn = BufTableShmemAttach,
};
/*
- * Register shmem hash table for mapping buffers.
- * size is the desired hash table size (possibly more than NBuffers)
+ * Number of hash buckets for the current NBuffers.
+ *
+ * Must be a power of two (so hashcode % num_buckets == hashcode & (num_buckets
+ * - 1)) and a multiple of NUM_BUFFER_PARTITIONS, so that every tag in a bucket
+ * maps to a single buffer partition (see file header).
+ */
+static inline int
+BufTableNumBuckets(void)
+{
+ return Max(NUM_BUFFER_PARTITIONS, pg_nextpower2_32(1.5 * NBuffers));
+}
+
+/*
+ * Register shared memory arrays for mapping buffers.
*/
void
BufTableShmemRequest(void *arg)
{
- int size;
+ num_buckets = BufTableNumBuckets();
+ Assert(num_buckets % NUM_BUFFER_PARTITIONS == 0);
- /*
- * Request the shared buffer lookup hashtable.
- *
- * Since we can't tolerate running out of lookup table entries, we must be
- * sure to specify an adequate table size here. The maximum steady-state
- * usage is of course NBuffers entries, but BufferAlloc() tries to insert
- * a new entry before deleting the old. In principle this could be
- * happening in each partition concurrently, so we could need as many as
- * NBuffers + NUM_BUFFER_PARTITIONS entries.
- */
- size = NBuffers + NUM_BUFFER_PARTITIONS;
-
- ShmemRequestHash(.name = "Shared Buffer Lookup Table",
- .nelems = size,
- .ptr = &SharedBufHash,
- .hash_info.keysize = sizeof(BufferTag),
- .hash_info.entrysize = sizeof(BufferLookupEnt),
- .hash_info.num_partitions = NUM_BUFFER_PARTITIONS,
- .hash_flags = HASH_ELEM | HASH_BLOBS | HASH_PARTITION | HASH_FIXED_SIZE,
+ ShmemRequestStruct(.name = "Shared Buffer Lookup Buckets",
+ .size = (Size) num_buckets * sizeof(BufferLookupBucket),
+ .ptr = (void **) &buckets,
+ );
+
+ ShmemRequestStruct(.name = "Shared Buffer Lookup Entries",
+ .size = (Size) NBuffers * sizeof(BufferLookupEnt),
+ .ptr = (void **) &entries,
);
}
+/*
+ * Initialize the shared buffer lookup table. Called once during shared-memory
+ * initialization (in the postmaster, or in a standalone backend).
+ *
+ * Shared memory is zeroed, but zero is a valid buf_id and block 0 is a valid
+ * block number, so we must explicitly mark every bucket empty
+ * (BUF_TABLE_CHAIN_END) and every entry empty (tag.blockNum == P_NEW).
+ */
+void
+BufTableShmemInit(void *arg)
+{
+ num_buckets = BufTableNumBuckets();
+
+ for (int i = 0; i < num_buckets; i++)
+ buckets[i].head = BUF_TABLE_CHAIN_END;
+
+ for (int i = 0; i < NBuffers; i++)
+ {
+ entries[i].tag.blockNum = P_NEW;
+ entries[i].next = BUF_TABLE_CHAIN_END;
+ }
+}
+
+/*
+ * Per-backend attach. The buckets/entries pointers are restored by the shmem
+ * framework, but num_buckets is a process-local scalar that must be recomputed
+ * in each backend. Forked children inherit it, but EXEC_BACKEND children run
+ * only the attach callback, so set it here too.
+ */
+void
+BufTableShmemAttach(void *arg)
+{
+ num_buckets = BufTableNumBuckets();
+}
+
/*
* BufTableHashCode
* Compute the hash code associated with a BufferTag
@@ -83,7 +162,7 @@ BufTableShmemRequest(void *arg)
uint32
BufTableHashCode(BufferTag *tagPtr)
{
- return get_hash_value(SharedBufHash, tagPtr);
+ return tag_hash(tagPtr, sizeof(BufferTag));
}
/*
@@ -95,19 +174,15 @@ BufTableHashCode(BufferTag *tagPtr)
int
BufTableLookup(BufferTag *tagPtr, uint32 hashcode)
{
- BufferLookupEnt *result;
-
- result = (BufferLookupEnt *)
- hash_search_with_hash_value(SharedBufHash,
- tagPtr,
- hashcode,
- HASH_FIND,
- NULL);
-
- if (!result)
- return -1;
+ int id = buckets[hashcode % num_buckets].head;
- return result->id;
+ while (id != BUF_TABLE_CHAIN_END)
+ {
+ if (BufferTagsEqual(&entries[id].tag, tagPtr))
+ return id;
+ id = entries[id].next;
+ }
+ return -1;
}
/*
@@ -123,23 +198,35 @@ BufTableLookup(BufferTag *tagPtr, uint32 hashcode)
int
BufTableInsert(BufferTag *tagPtr, uint32 hashcode, int buf_id)
{
- BufferLookupEnt *result;
- bool found;
+ int bucket_id = hashcode % num_buckets;
+ int head = buckets[bucket_id].head;
+ int id = head;
- Assert(buf_id >= 0); /* -1 is reserved for not-in-table */
+ Assert(buf_id >= 0 && buf_id < NBuffers);
Assert(tagPtr->blockNum != P_NEW); /* invalid tag */
- result = (BufferLookupEnt *)
- hash_search_with_hash_value(SharedBufHash,
- tagPtr,
- hashcode,
- HASH_ENTER,
- &found);
+ /* If the tag is already in the chain, surface the existing buf_id. */
+ while (id != BUF_TABLE_CHAIN_END)
+ {
+ if (BufferTagsEqual(&entries[id].tag, tagPtr))
+ return id;
+ id = entries[id].next;
+ }
- if (found) /* found something already in the table */
- return result->id;
+ /*
+ * Not present. entry[buf_id] must be empty: bufmgr always deletes a
+ * buffer's old mapping before inserting a new tag for that buf_id.
+ */
+ Assert(entries[buf_id].tag.blockNum == P_NEW);
- result->id = buf_id;
+ /*
+ * Link entry[buf_id] at the chain head, keeping the prior head as its
+ * successor. (Use the saved `head`, not `id`, which the loop above has
+ * advanced to BUF_TABLE_CHAIN_END.)
+ */
+ entries[buf_id].tag = *tagPtr;
+ entries[buf_id].next = head;
+ buckets[bucket_id].head = buf_id;
return -1;
}
@@ -153,15 +240,32 @@ BufTableInsert(BufferTag *tagPtr, uint32 hashcode, int buf_id)
void
BufTableDelete(BufferTag *tagPtr, uint32 hashcode)
{
- BufferLookupEnt *result;
+ int bucket_id = hashcode % num_buckets;
+ int prev = BUF_TABLE_CHAIN_END;
+ int id = buckets[bucket_id].head;
- result = (BufferLookupEnt *)
- hash_search_with_hash_value(SharedBufHash,
- tagPtr,
- hashcode,
- HASH_REMOVE,
- NULL);
+ while (id != BUF_TABLE_CHAIN_END)
+ {
+ if (BufferTagsEqual(&entries[id].tag, tagPtr))
+ {
+ /* unlink from the chain */
+ if (prev == BUF_TABLE_CHAIN_END)
+ buckets[bucket_id].head = entries[id].next;
+ else
+ entries[prev].next = entries[id].next;
+ /* mark the entry empty */
+ entries[id].tag.blockNum = P_NEW;
+ entries[id].next = BUF_TABLE_CHAIN_END;
+ return;
+ }
+ prev = id;
+ id = entries[id].next;
+ }
- if (!result) /* shouldn't happen */
- elog(ERROR, "shared buffer hash table corrupted");
+ /*
+ * Entry not in table. Callers never double-delete (deletion is gated by
+ * BM_TAG_VALID on the buffer header), so this indicates corruption.
+ */
+ Assert(false);
+ elog(ERROR, "shared buffer hash table corrupted");
}
--
2.53.0
