PostgreSQL Computes Page Checksums Fast

Every page PostgreSQL writes to disk gets a checksum: two bytes in the page header that let the server notice, on the next read, that the page it just read is not the page it wrote.

That sounds trivial. It is not, and the reason is a nice illustration of how a deceptively simple requirement turns into a performance problem. The checksum is computed over 8 kB of memory, on every page write and every page read, and the whole point of the feature is that it must be cheap enough to always leave on. A checksum that costs five percent of your I/O is not a checksum; it is a tax you eventually turn off.

So PostgreSQL does something quite clever: it computes thirty-two checksums at once, over a thirty-two-column view of the page, so that the latency of the one expensive instruction in the algorithm — the multiplication — is hidden behind the others. Thirty-two is not an arbitrary number. It is the number that fits in the register file.

This is the story of that design, in version 20devel (commit e75fcc9867f).

Where the checksum lives

Two bytes, in the page header:

c
// src/include/storage/bufpage.h
typedef struct PageHeaderData
{
	/* XXX LSN is member of *any* block, not only page-organized ones */
	PageXLogRecPtr pd_lsn;		/* LSN: next byte after last byte of xlog
								 * record for last change to this page */
	uint16		pd_checksum;	/* checksum */
	uint16		pd_flags;		/* flag bits, see below */
	LocationIndex pd_lower;		/* offset to start of free space */
	LocationIndex pd_upper;		/* offset to end of free space */
	LocationIndex pd_special;	/* offset to start of special space */
	uint16		pd_pagesize_version;
	TransactionId pd_prune_xid; /* oldest prunable XID, or zero if none */
	ItemIdData	pd_linp[FLEXIBLE_ARRAY_MEMBER]; /* line pointer array */
} PageHeaderData;

The header comment above the struct explains the semantics, and they are subtler than they look:

pd_checksum stores the page checksum, if it has been set for this page; zero is a valid value for a checksum. If a checksum is not in use then we leave the field unset. This will typically mean the field is zero though non-zero values may also be present if databases have been pg_upgraded from releases prior to 9.3, when the same byte offset was used to store the current timelineid when the page was last updated. Note that there is no indication on a page as to whether the checksum is valid or not, a deliberate design choice which avoids the problem of relying on the page contents to decide whether to verify it. Hence there are no flag bits relating to checksums.

That last sentence is the design decision that makes the whole feature tractable: a page does not say “I have a checksum”. Whether a checksum is expected is a property of the cluster, not of the page. That means the verification code never has to guess, and it means enabling checksums on an existing cluster is a cluster-wide decision recorded in pg_control.

The states live in src/include/storage/checksum.h:

c
// src/include/storage/checksum.h
/*
 * Checksum state 0 is used for when data checksums are disabled (OFF).
 * PG_DATA_CHECKSUM_INPROGRESS_{ON|OFF} defines that data checksums are either
 * currently being enabled or disabled, and PG_DATA_CHECKSUM_VERSION defines
 * that data checksums are enabled.  The ChecksumStateType is stored in
 * pg_control so changing requires a catversion bump, and the values cannot
 * be reordered.  New states must be added at the end.
 */
typedef enum ChecksumStateType
{
	PG_DATA_CHECKSUM_OFF = 0,
	PG_DATA_CHECKSUM_VERSION = 1,
	PG_DATA_CHECKSUM_INPROGRESS_OFF = 2,
	PG_DATA_CHECKSUM_INPROGRESS_ON = 3,
} ChecksumStateType;

Note the two “in progress” states. pg_checksums can be run offline to turn checksums on or off for a stopped cluster, but turning them on while the server is running has to be WAL-logged and crash-safe, so there is a state where checksums are written but not yet verified, and a state where they are verified but not yet written. Both matter for the “is a checksum expected here?” question.

The two runtime predicates are in src/backend/access/transam/xlog.c:

c
// src/backend/access/transam/xlog.c
/*
 * DataChecksumsNeedWrite
 *		Returns whether data checksums must be written or not
 *
 * Returns true if data checksums are enabled, or are in the process of being
 * enabled. During "inprogress-on" and "inprogress-off" states checksums must
 * be written even though they are not verified (see datachecksum_state.c for
 * a longer discussion).
 *
 * This function is intended for callsites which are about to write a data page
 * to storage, and need to know whether to re-calculate the checksum for the
 * page header. Calling this function must be performed as close to the write
 * operation as possible to keep the critical section short.
 */
bool
DataChecksumsNeedWrite(void)
{
	return (LocalDataChecksumState == PG_DATA_CHECKSUM_VERSION ||
			LocalDataChecksumState == PG_DATA_CHECKSUM_INPROGRESS_ON ||
			LocalDataChecksumState == PG_DATA_CHECKSUM_INPROGRESS_OFF);
}

c
// src/backend/access/transam/xlog.c
/*
 * DataChecksumsNeedVerify
 *		Returns whether data checksums must be verified or not
 *
 * Data checksums are only verified if they are fully enabled in the cluster.
 * During the "inprogress-on" and "inprogress-off" states they are only
 * updated, not verified (see datachecksum_state.c for a longer discussion).
 *
 * This function is intended for callsites which have read data and are about
 * to perform checksum validation based on the result of this.  Calling this
 * function must be performed as close to the validation call as possible to
 * keep the critical section short. This is in order to protect against time of
 * check/time of use situations around data checksum validation.
 */
bool
DataChecksumsNeedVerify(void)
{
	return (LocalDataChecksumState == PG_DATA_CHECKSUM_VERSION);
}

Note the asymmetry: DataChecksumsNeedWrite() is true in three states (the “on” state and both “in progress” states), while DataChecksumsNeedVerify() is true only in the fully-enabled state. You must not verify a checksum that was never written.

The algorithm: FNV-1a, with a twist

The core of the algorithm is documented in one of the best comments in the PostgreSQL tree. From src/include/storage/checksum_impl.h:

c
// src/include/storage/checksum_impl.h
/*
 * The algorithm used to checksum pages is chosen for very fast calculation.
 * Workloads where the database working set fits into OS file cache but not
 * into shared buffers can read in pages at a very fast pace and the checksum
 * algorithm itself can become the largest bottleneck.
 *
 * The checksum algorithm itself is based on the FNV-1a hash (FNV is shorthand
 * for Fowler/Noll/Vo).  The primitive of a plain FNV-1a hash folds in data 1
 * byte at a time according to the formula:
 *
 *	   hash = (hash ^ value) * FNV_PRIME
 *
 * FNV-1a algorithm is described at http://www.isthe.com/chongo/tech/comp/fnv/
 *
 * PostgreSQL doesn't use FNV-1a hash directly because it has bad mixing of
 * high bits - high order bits in input data only affect high order bits in
 * output data. To resolve this we xor in the value prior to multiplication
 * shifted right by 17 bits. The number 17 was chosen because it doesn't
 * have common denominator with set bit positions in FNV_PRIME and empirically
 * provides the fastest mixing for high order bits of final iterations quickly
 * avalanche into lower positions. For performance reasons we choose to combine
 * 4 bytes at a time. The actual hash formula used as the basis is:
 *
 *	   hash = (hash ^ value) * FNV_PRIME ^ ((hash ^ value) >> 17)
 *
 * The main bottleneck in this calculation is the multiplication latency. To
 * hide the latency and to make use of SIMD parallelism multiple hash values
 * are calculated in parallel. The page is treated as a 32 column two
 * dimensional array of 32 bit values. Each column is aggregated separately
 * into a partial checksum. Each partial checksum uses a different initial
 * value (offset basis in FNV terminology). The initial values actually used
 * were chosen randomly, as the values themselves don't matter as much as that
 * they are different and don't match anything in real data. After initializing
 * partial checksums each value in the column is aggregated according to the
 * above formula. Finally two more iterations of the formula are performed with
 * value 0 to mix the bits of the last value added.
 *
 * The partial checksums are then folded together using xor to form a single
 * 32-bit checksum. The caller can safely reduce the value to 16 bits
 * using modulo 2^16-1. That will cause a very slight bias towards lower
 * values but this is not significant for the performance of the
 * checksum.

The base is FNV-1a: a one-byte-at-a-time hash with the formula

text

   hash = (hash ^ value) * FNV_PRIME

PostgreSQL does not use it unmodified, for the reason given: plain FNV-1a mixes badly — high-order bits of the input only affect high-order bits of the output, which is exactly the kind of weakness a checksum cannot afford when the input is a page full of mostly-zero bytes.

The fix is to fold in the value shifted as well:

text

   hash = (hash ^ value) * FNV_PRIME ^ ((hash ^ value) >> 17)

The shift by 17 is not arbitrary; the comment explains that 17 “doesn’t have common denominator with set bit positions in FNV_PRIME and empirically provides the fastest mixing for high order bits”.

And then the crucial decision:

For performance reasons we choose to combine 4 bytes at a time.

So the unit of work is a 32-bit word, not a byte. The formula is implemented as a macro:

c
// src/include/storage/checksum_impl.h
/*
 * Calculate one round of the checksum.
 */
#define CHECKSUM_COMP(checksum, value) \
do { \
	uint32 __tmp = (checksum) ^ (value); \
	(checksum) = __tmp * FNV_PRIME ^ (__tmp >> 17); \
} while (0)

__tmp is the xor of the running hash and the new word. The hash becomes __tmp * FNV_PRIME, xored with __tmp >> 17. Note that the xor with the shifted value happens after the multiplication — the shift of the pre-multiplication value, which is the same as __tmp >> 17 because the multiplication is applied to __tmp in the first term only.

Why thirty-two hashes

Here is the paragraph that explains the whole design:

The main bottleneck in this calculation is the multiplication latency. To hide the latency and to make use of SIMD parallelism multiple hash values are calculated in parallel. The page is treated as a 32 column two dimensional array of 32 bit values. Each column is aggregated separately into a partial checksum. Each partial checksum uses a different initial value (offset basis in FNV terminology).

An integer multiply on a modern x86 has a latency of about three cycles and a throughput of one per cycle. The critical path in the checksum loop is: multiply (3 cycles) → xor → multiply → xor … If you have only one hash in flight, you are latency-bound and the multiply unit is idle most of the time. If you have several independent hashes in flight, they fill the gap: the CPU issues all the multiplies, then all the xors, and the latency of one is covered by the throughput of the others.

So the page is viewed as a matrix, and the columns are the parallel hashes:

text

   page bytes, viewed as uint32 words

   col 0:  w[0]   w[32]  w[64]  ... w[2016]     ──▶ hash 0
   col 1:  w[1]   w[33]  w[65]  ... w[2017]     ──▶ hash 1
   col 2:  w[2]   w[34]  w[66]  ... w[2018]     ──▶ hash 2
    ...
   col 31: w[31]  w[63]  w[95]  ... w[2047]     ──▶ hash 31

Each column is a contiguous run of words in the page, strided by 32 words. The 32 hashes march through their columns in lockstep, one word per row, and each row’s 32 multiplies are independent.

The implementation of that view is a union:

c
// src/include/storage/checksum_impl.h
#include "storage/bufpage.h"

/* number of checksums to calculate in parallel */
#define N_SUMS 32
/* prime multiplier of FNV-1a hash */
#define FNV_PRIME 16777619

/* Use a union so that this code is valid under strict aliasing */
typedef union
{
	PageHeaderData phdr;
	uint32		data[BLCKSZ / (sizeof(uint32) * N_SUMS)][N_SUMS];
} PGChecksummablePage;

/*
 * Base offsets to initialize each of the parallel FNV hashes into a
 * different initial state.
 */
static const uint32 checksumBaseOffsets[N_SUMS] = {
	0x5B1F36E9, 0xB8525960, 0x02AB50AA, 0x1DE66D2A,
	0x79FF467A, 0x9BB9F8A3, 0x217E7CD2, 0x83E13D2C,
	0xF8D4474F, 0xE39EB970, 0x42C6AE16, 0x993216FA,
	0x7B093B5D, 0x98DAFF3C, 0xF718902A, 0x0B1C9CDB,
	0xE58F764B, 0x187636BC, 0x5D7B3BB1, 0xE73DE7DE,
	0x92BEC979, 0xCCA6C0B2, 0x304A0979, 0x85AA43D4,
	0x783125BB, 0x6CA8EAA2, 0xE407EAC6, 0x4B5CFC3E,
	0x9FBF8C76, 0x15CA20BE, 0xF2CA9FD3, 0x959BD756
};

Two things are hiding in there.

The union is not incidental — it is a strict-aliasing workaround. The comment says so: “Use a union so that this code is valid under strict aliasing”. The page is a char *; the code wants to read it as an array of uint32. If you did that with a cast and a pointer, the compiler would be entitled to assume that the uint32 accesses never alias the char accesses and could reorder or elide them — technically undefined behavior, and the kind that produces a checksum that is correct on one compiler and wrong on another. Putting the two views in a union is the standard C way of saying “these are the same bytes, and I know what I’m doing”. (PostgreSQL also compiles with -fno-strict-aliasing in some configurations, but the union is the portable answer, and it is what the code does.)

The array shape is the algorithm. data[BLCKSZ / (sizeof(uint32) * N_SUMS)][N_SUMS] is a 64-by-32 array of uint32 for an 8 kB page: 8192 / (4 * 32) = 64 rows, 32 columns. The first index is the row (which step along a column) and the second is the column (which hash). That is why page->data[i][j] in the main loop means “row i, column j” and why the inner loop over j is the vectorizable one.

The initial values for the 32 hashes are constants:

c
// src/include/storage/checksum_impl.h
/*
 * Base offsets to initialize each of the parallel FNV hashes into a
 * different initial state.
 */
static const uint32 checksumBaseOffsets[N_SUMS] = {
	0x5B1F36E9, 0xB8525960, 0x02AB50AA, 0x1DE66D2A,
	0x79FF467A, 0x9BB9F8A3, 0x217E7CD2, 0x83E13D2C,
	0xF8D4474F, 0xE39EB970, 0x42C6AE16, 0x993216FA,
	0x7B093B5D, 0x98DAFF3C, 0xF718902A, 0x0B1C9CDB,
	0xE58F764B, 0x187636BC, 0x5D7B3BB1, 0xE73DE7DE,
	0x92BEC979, 0xCCA6C0B2, 0x304A0979, 0x85AA43D4,
	0x783125BB, 0x6CA8EAA2, 0xE407EAC6, 0x4B5CFC3E,
	0x9FBF8C76, 0x15CA20BE, 0xF2CA9FD3, 0x959BD756
};

and the comment above them says exactly what they are for:

Base offsets to initialize each of the parallel FNV hashes into a different initial state.

The header comment adds a note that is easy to miss and quite philosophical:

Each partial checksum uses a different initial value (offset basis in FNV terminology). The initial values actually used were chosen randomly, as the values themselves don’t matter as much as that they are different and don’t match anything in real data.

So the constants are not magic numbers with a story; they are just 32 different random 32-bit numbers, chosen so that no two hashes start in the same state.

The core loop

The actual algorithm lives in a separate header, checksum_block_internal.h, which is #included — as a body, not as a function — into whichever implementation is being compiled. That is the trick that lets the same algorithm be compiled four ways (see below) without any duplication.

c
// src/include/storage/checksum_block_internal.h
/* there is deliberately not an #ifndef CHECKSUM_BLOCK_INTERNAL_H here */

uint32		sums[N_SUMS];
uint32		result = 0;
uint32		i,
			j;

/* ensure that the size is compatible with the algorithm */
Assert(sizeof(PGChecksummablePage) == BLCKSZ);

/* initialize partial checksums to their corresponding offsets */
memcpy(sums, checksumBaseOffsets, sizeof(checksumBaseOffsets));

/* main checksum calculation */
for (i = 0; i < (uint32) (BLCKSZ / (sizeof(uint32) * N_SUMS)); i++)
	for (j = 0; j < N_SUMS; j++)
		CHECKSUM_COMP(sums[j], page->data[i][j]);

/* finally add in two rounds of zeroes for additional mixing */
for (i = 0; i < 2; i++)
	for (j = 0; j < N_SUMS; j++)
		CHECKSUM_COMP(sums[j], 0);

/* xor fold partial checksums together */
for (i = 0; i < N_SUMS; i++)
	result ^= sums[i];

return result;

Read it as four phases.

Phase 1: initialize. The 32 partial checksums start at their base offsets.

Phase 2: the main loop. for i in 64 rows, for j in 32 columns: CHECKSUM_COMP(sums[j], page->data[i][j]). The inner loop over j is the vectorizable one: 32 independent multiply-xor chains, one per column. The compiler can put eight of them in a 256-bit AVX2 register (or four in a 128-bit SSE2 register) and issue a vector multiply.

Phase 3: two rounds of zeroes. CHECKSUM_COMP(sums[j], 0) twice. The header comment explains why:

Finally two more iterations of the formula are performed with value 0 to mix the bits of the last value added.

Without this, the last word added to each column would have a weaker effect on the final result than earlier words. Two extra rounds of the same mixing operation push the influence of the last real word further down the mix.

Phase 4: the fold. All 32 partial checksums are xored together into a single 32-bit value:

The partial checksums are then folded together using xor to form a single 32-bit checksum.

Note this is an XOR, not an addition. That matters: XOR is associative, commutative, and order-independent, so the fold is exact and there is no carry propagation between columns. It also means the fold is itself embarrassingly parallel — though at 32 elements, that hardly matters.

From 32 bits to 16

The fold produces a 32-bit value. The page header has sixteen bits. The final mapping is in pg_checksum_page():

c
// src/include/storage/checksum_impl.h
/*
 * Compute the checksum for a Postgres page.
 *
 * The page must be adequately aligned (at least on a 4-byte boundary).
 * Beware also that the checksum field of the page is transiently zeroed.
 *
 * The checksum includes the block number (to detect the case where a page is
 * somehow moved to a different location), the page header (excluding the
 * checksum itself), and the page data.
 */
uint16
pg_checksum_page(char *page, BlockNumber blkno)
{
	PGChecksummablePage *cpage = (PGChecksummablePage *) page;
	uint16		save_checksum;
	uint32		checksum;

	/* We only calculate the checksum for properly-initialized pages */
	Assert(!PageIsNew((Page) page));

	/*
	 * Save pd_checksum and temporarily set it to zero, so that the checksum
	 * calculation isn't affected by the old checksum stored on the page.
	 * Restore it after, because actually updating the checksum is NOT part of
	 * the API of this function.
	 */
	save_checksum = cpage->phdr.pd_checksum;
	cpage->phdr.pd_checksum = 0;
	checksum = pg_checksum_block(cpage);
	cpage->phdr.pd_checksum = save_checksum;

	/* Mix in the block number to detect transposed pages */
	checksum ^= blkno;

	/*
	 * Reduce to a uint16 (to fit in the pd_checksum field) with an offset of
	 * one. That avoids checksums of zero, which seems like a good idea.
	 */
	return (uint16) ((checksum % 65535) + 1);
}

Several things are going on here.

The checksum is not self-referential. The header comment says it, and the code does it:

c
	save_checksum = cpage->phdr.pd_checksum;
	cpage->phdr.pd_checksum = 0;
	checksum = pg_checksum_block(cpage);
	cpage->phdr.pd_checksum = save_checksum;

The old checksum is saved, the field is zeroed, the checksum is computed over the page including the (now zero) checksum field, and the old value is restored — because, as the comment notes, “actually updating the checksum is NOT part of the API of this function”. The caller does that.

Zeroing the field rather than excluding it from the hash is simpler, and it means the checksum covers the whole 8 kB without a special case for two bytes.

The block number is mixed in afterwards:

c
	/* Mix in the block number to detect transposed pages */
	checksum ^= blkno;

A page copied to the wrong position in the file — a “transposed page” — would otherwise have a perfectly valid checksum, because its contents are intact. Xoring in the block number means such a page fails verification.

The reduction to sixteen bits avoids zero:

c
	/*
	 * Reduce to a uint16 (to fit in the pd_checksum field) with an offset of
	 * one. That avoids checksums of zero, which seems like a good idea.
	 */
	return (uint16) ((checksum % 65535) + 1);

Modulo 65535 rather than 65536 keeps the result in 1..65535, so the stored value is never zero. And the header comment is upfront about the consequence:

The caller can safely reduce the value to 16 bits using modulo 2^16-1. That will cause a very slight bias towards lower values but this is not significant for the performance of the checksum.

The bias is real: 0xFFFF can never occur, and 0x0001 occurs slightly more often than its neighbors. For a corruption-detection checksum, that is irrelevant.

Where it is called from

Two places, and they are not symmetric.

Writing goes through PageSetChecksum():

c
// src/backend/storage/page/bufpage.c
 * If the page is in shared buffers, it needs to be locked in at least
 * share-exclusive mode.
 *
 * If checksums are disabled, or if the page is not initialized, just
 * return. Otherwise compute and set the checksum.
 *
 * In the past this needed to be done on a copy of the page, due to the
 * possibility of e.g., hint bits being set concurrently. However, this is not
 * necessary anymore as hint bits won't be set while IO is going on.
 */
void
PageSetChecksum(Page page, BlockNumber blkno)
{
	HOLD_INTERRUPTS();
	/* If we don't need a checksum, just return */
	if (PageIsNew(page) || !DataChecksumsNeedWrite())
	{
		RESUME_INTERRUPTS();
		return;
	}

	((PageHeader) page)->pd_checksum = pg_checksum_page(page, blkno);
	RESUME_INTERRUPTS();
}

Note the HOLD_INTERRUPTS() / RESUME_INTERRUPTS() bracket, and note the comment above the function:

In the past this needed to be done on a copy of the page, due to the possibility of e.g., hint bits being set concurrently. However, this is not necessary anymore as hint bits won’t be set while IO is going on.

Reading goes through PageIsVerified():

c
// src/backend/storage/page/bufpage.c
bool
PageIsVerified(PageData *page, BlockNumber blkno, int flags, bool *checksum_failure_p)
{
	const PageHeaderData *p = (const PageHeaderData *) page;
	size_t	   *pagebytes;
	bool		checksum_failure = false;
	bool		header_sane = false;
	uint16		checksum = 0;

	if (checksum_failure_p)
		*checksum_failure_p = false;

	/*
	 * Don't verify page data unless the page passes basic non-zero test
	 */
	if (!PageIsNew(page))
	{
		/*
		 * There shouldn't be any check for interrupt calls happening in this
		 * codepath, but just to be on the safe side we hold interrupts since
		 * if they did happen the data checksum state could change during
		 * verifying checksums, which could lead to incorrect verification
		 * results.
		 */
		HOLD_INTERRUPTS();
		if (DataChecksumsNeedVerify())
		{
			checksum = pg_checksum_page(page, blkno);

			if (checksum != p->pd_checksum)
			{
				checksum_failure = true;
				if (checksum_failure_p)
					*checksum_failure_p = true;
			}
		}
		RESUME_INTERRUPTS();

		/*
		 * The following checks don't prove the header is correct, only that
		 * it looks sane enough to allow into the buffer pool. Later usage of
		 * the block can still reveal problems, which is why we offer the
		 * checksum option.
		 */
		if ((p->pd_flags & ~PD_VALID_FLAG_BITS) == 0 &&
			p->pd_lower <= p->pd_upper &&
			p->pd_upper <= p->pd_special &&
			p->pd_special <= BLCKSZ &&
			p->pd_special == MAXALIGN(p->pd_special))
			header_sane = true;

		if (header_sane && !checksum_failure)
			return true;
	}

Note the order of the checks. The checksum is verified first, and then the header is checked for sanity — but the sanity check is explicitly not treated as proof:

c
		/*
		 * The following checks don't prove the header is correct, only that
		 * it looks sane enough to allow into the buffer pool. Later usage of
		 * the block can still reveal problems, which is why we offer the
		 * checksum option.
		 */

And the all-zero page case is handled separately, because a zeroed page is a legitimate thing to find (a backend extended a relation and crashed before writing any WAL about it).

Runtime dispatch: the AVX2 path

Now the part that makes this a performance story rather than an algorithm story.

The checksum algorithm is a few dozen lines, but it is compiled into several implementations, and the right one is chosen at runtime.

c
// src/backend/storage/page/checksum.c
#include "postgres.h"

#include "port/pg_cpu.h"
#include "storage/checksum.h"
/*
 * The actual code is in storage/checksum_impl.h.  This is done so that
 * external programs can incorporate the checksum code by #include'ing
 * that file from the exported Postgres headers.  (Compare our legacy
 * CRC code in pg_crc.h.)
 * The PG_CHECKSUM_INTERNAL symbol allows core to use hardware-specific
 * coding without affecting external programs.
 */
#define PG_CHECKSUM_INTERNAL
#include "storage/checksum_impl.h"	/* IWYU pragma: keep */


static uint32
pg_checksum_block_fallback(const PGChecksummablePage *page)
{
#include "storage/checksum_block_internal.h"
}

/*
 * AVX2-optimized block checksum algorithm.
 */
#ifdef USE_AVX2_WITH_RUNTIME_CHECK
pg_attribute_target("avx2")
static uint32
pg_checksum_block_avx2(const PGChecksummablePage *page)
{
#include "storage/checksum_block_internal.h"
}
#endif							/* USE_AVX2_WITH_RUNTIME_CHECK */

/*
 * Choose the best available checksum implementation.
 */
static uint32
pg_checksum_choose(const PGChecksummablePage *page)
{
	pg_checksum_block = pg_checksum_block_fallback;

#ifdef USE_AVX2_WITH_RUNTIME_CHECK
	if (x86_feature_available(PG_AVX2))
		pg_checksum_block = pg_checksum_block_avx2;
#endif

	return pg_checksum_block(page);
}

static uint32 (*pg_checksum_block) (const PGChecksummablePage *page) = pg_checksum_choose;

Four things are going on.

The function pointer. pg_checksum_block is a function pointer, initialized to pg_checksum_choose. The first call to pg_checksum_page goes through the pointer, and pg_checksum_choose replaces the pointer with the best available implementation before doing the work. Every subsequent call is a direct-ish indirect call to the chosen implementation. The AVX2 commit message explains the tradeoff:

Similar to other hardware-specific paths, we set a function pointer on first use. We don’t bother to avoid this on platforms without AVX2 since the overhead of indirect calls doesn’t matter for multi-kilobyte inputs.

That is the right call. The input is 8 kB; an indirect call is worth about a nanosecond. The AVX2 win is worth hundreds.

The same source, four ways. The pg_checksum_block_* functions do not contain the algorithm; they #include it:

c
#include "storage/checksum_block_internal.h"

So the algorithm is textually included in the fallback and in the AVX2 variant. There is exactly one copy of the algorithm, and it is compiled twice with different compiler flags. That is the whole reason for the awkward “include a body” idiom.

The AVX2 variant uses a function attribute. pg_attribute_target("avx2") expands to __attribute__((target("avx2"))), which tells the compiler “compile this function for AVX2, even though the rest of the program was not compiled for AVX2”. The attribute is applied to a single function, so the rest of the binary remains runnable on a pre-AVX2 CPU. The macro itself:

c
// src/include/c.h
 * pg_attribute_target allows specifying different target options that the
 * function should be compiled with (e.g., for using special CPU instructions).
 * Note that there still needs to be a configure-time check to verify that a
 * specific target is understood by the compiler.
 */
#if __has_attribute (target)
#define pg_attribute_target(...) __attribute__((target(__VA_ARGS__)))
#else
#define pg_attribute_target(...)
#endif

Note the comment’s warning: “Note that there still needs to be a configure-time check to verify that a specific target is understood by the compiler.” That is exactly what PGAC_AVX2_SUPPORT() in configure.ac is for.

Whether the compiler supports it is decided at configure time:

c
// configure.ac
# Check for AVX2 target support
#
if test x"$host_cpu" = x"x86_64"; then
  PGAC_AVX2_SUPPORT()
  if test x"$pgac_avx2_support" = x"yes"; then
    AC_DEFINE(USE_AVX2_WITH_RUNTIME_CHECK, 1, [Define to 1 to use AVX2 instructions with a runtime check.])
  fi
fi

and the runtime check uses the CPUID-based feature detection in src/include/port/pg_cpu.h:

c
// src/include/port/pg_cpu.h
#if defined(__x86_64__) || defined(__i386__)

typedef enum X86FeatureId
{
	/* Have we run feature detection? */
	INIT_PG_X86,

	/* scalar registers and 128-bit XMM registers */
	PG_SSE4_2,
	PG_POPCNT,

	/* 256-bit YMM registers */
	PG_AVX2,

	/* 512-bit ZMM registers */
	PG_AVX512_BW,
	PG_AVX512_VL,
	PG_AVX512_VPCLMULQDQ,
	PG_AVX512_VPOPCNTDQ,

	/* identification */
	PG_HYPERVISOR,

	/* Time-Stamp Counter (TSC) flags */
	PG_RDTSCP,
	PG_TSC_INVARIANT,

x86_feature_available(PG_AVX2) triggers set_x86_features() on first use and then reads a cached array.

The fallback relies on the compiler. For a build without AVX2 — or on a non-x86 platform — the fallback implementation is compiled with -funroll-loops -ftree-vectorize, applied to this one object file:

make
# src/backend/storage/page/Makefile
# Provide special optimization flags for checksum.c
checksum.o: CFLAGS += ${CFLAGS_UNROLL_LOOPS} ${CFLAGS_VECTORIZE}

The header comment explains why those two flags are the whole trick:

Vectorization of the algorithm works best with a 32bit x 32bit -> 32bit vector integer multiplication instruction, Examples include x86 AVX2 extensions (vpmulld) and ARM NEON (vmul.i32). Without that, vectorization is still possible if the compiler can turn multiplication by FNV_PRIME into a sequence of vectorized shifts and adds. For simplicity we rely on the compiler to do the vectorization for us. For GCC and clang the flags -funroll-loops -ftree-vectorize are enough to achieve vectorization.

So: on AVX2 hardware you get real vector multiply (vpmulld), eight columns per instruction. Elsewhere you get the compiler’s best attempt at expressing the constant multiply x * 16777619 as shifts and adds, which is what SSE2 has to do — SSE2 has no 32-bit vector multiply at all.

Why thirty-two, exactly?

The header comment is explicit:

The parallelism number 32 was chosen based on the fact that it is the largest state that fits into architecturally visible x86 SSE registers while leaving some free registers for intermediate values. For processors with 256-bit vector registers this leaves some performance on the table.

So: 32 partial hashes = 32 × 32 bits = 1024 bits of state. In 128-bit XMM registers that is eight registers — half of x86-64’s sixteen XMM registers, leaving the other half free for the loop’s intermediate values. With AVX2’s 256-bit YMM registers you could hold twice as much state, but you cannot: the number 32 is baked into the algorithm.

And it cannot be unbaked:

The number chosen is a fixed part of the algorithm because changing the parallelism changes the checksum result.

Caveats

N_SUMS is part of the on-disk format

This is the big one. N_SUMS is 32, the base offsets are a fixed table, and the fold is a fixed XOR. The resulting 16-bit value is stored in pd_checksum on every page of every relation in the cluster. If you changed N_SUMS to 16, or reordered the base offsets, or changed the prime, every existing page in every existing cluster would fail verification. The checksum algorithm is not an implementation detail; it is a storage format.

This is why the algorithm lives in checksum_impl.h with the comment:

This file exists for the benefit of external programs that may wish to check Postgres page checksums. They can #include this to get the code referenced by storage/checksum.h.

External tools — pg_checksums, the pageinspect extension, backup and restore tooling, third-party extensions — need to compute the same value, so the algorithm is published as a header that anyone can include. The PG_CHECKSUM_INTERNAL symbol then splits it:

c
// src/include/storage/checksum_impl.h
/*
 * Block checksum algorithm.  The page must be adequately aligned
 * (at least on 4-byte boundary).
 */
#ifdef PG_CHECKSUM_INTERNAL
/* definitions in src/backend/storage/page/checksum.c */
static uint32 (*pg_checksum_block) (const PGChecksummablePage *page);

#else
/* static definition for external programs */
static uint32
pg_checksum_block(const PGChecksummablePage *page)
{
#include "storage/checksum_block_internal.h"
}

#endif

With PG_CHECKSUM_INTERNAL defined (as in src/backend/storage/page/checksum.c), the core gets the runtime-dispatched function pointer. Without it, an external program gets a plain static function and never has to know that dispatch exists.

What the checksum does and does not cover

It covers the whole page: the page header (with the checksum field zeroed), the line pointer array, the tuple data, and the special space. It does not cover the block number — the block number is mixed in afterwards, by XOR.

It cannot detect all corruption. Sixteen bits means a false-negative rate of roughly 1 in 65535 for a random corruption; the header comment quotes the measured figure:

Tests of 1-4 uncorrelated bit errors, stray 0 and 0xFF bytes, overwriting page from random position to end with 0 bytes, and overwriting random segments of page with 0x00, 0xFF and random data all show optimal 2e-16 false positive rate within margin of error.

(That “false positive rate” is the rate of undetected corruption — the terminology in the comment is from the perspective of “the checksum says OK when the data is bad”.)

And it is not a substitute for WAL. A page checksum detects that this page is corrupt; it cannot tell you what the page should have contained, and it cannot undo the damage. Recovery from corruption still requires a restore from backup or a pg_checksums-style surgical repair.

The cost is real

Every dirty page written to disk pays for the checksum, and every page read from disk pays for the verification. For a write-heavy workload on slow storage, that is measurable. That is why checksums are opt-in at initdb time (initdb --data-checksums), and why the pg_checksums utility exists to turn them on or off offline for an existing cluster.

The AVX2 commit message names the case where the cost hurts most:

This matters most when using io_uring since in that case the checksum computation is not done in parallel by IO workers.

Which is to say: the checksum is computed on the path to disk, and anything that adds work to that path shows up.

The “in progress” states are subtle

A cluster in the PG_DATA_CHECKSUM_INPROGRESS_ON state writes checksums but does not verify them; a cluster in PG_DATA_CHECKSUM_INPROGRESS_OFF state does neither. Getting this wrong means either failing to notice corruption or failing to read your own data, so the state machine is stored in pg_control and the transitions are WAL-logged.

Sixteen bits is not a lot

The stored value is a 16-bit checksum, and the reduction is not uniform: checksum % 65535 + 1 can produce 1..65535, so 0x0000 is impossible and the distribution is very slightly skewed. It is fine for detecting “this page is garbage”, and it is not fine for anything stronger. Do not confuse it with a cryptographic digest.

Look at it yourself

The pg_checksums utility is the supported way to inspect and repair checksums on a stopped cluster:

pg_checksums --check -D /var/lib/postgresql/16/main
pg_checksums --enable -D /var/lib/postgresql/16/main

pg_controldata shows the cluster’s checksum state:

pg_controldata /var/lib/postgresql/16/main | grep -i checksum

And to watch the algorithm run, look at the assembly of the fallback implementation — the pmulld/vpmulld in the AVX2 object file is the whole point:

objdump -d src/backend/storage/page/checksum.o | less

What it all means in practice

The checksum algorithm is a latency problem, not a throughput problem. The single expensive operation is a 32-bit multiply, and multiply latency — not bandwidth — is what limits a dependent chain of hashes. The fix is not a faster multiply; it is thirty-two independent chains so the CPU’s out-of-order engine can fill the pipeline. That is a general-purpose optimization that applies to any hash-like construction.

The page is treated as a matrix, and the matrix shape is the algorithm. Thirty-two columns, sixty-four rows. The inner loop walks across columns, and that is the loop that vectorizes. It is a staggered layout — column j reads words j, j+32, j+64 — so it is not contiguous, but it is perfectly regular, which is what the compiler and the vectorizer need.

Register pressure is a design constraint, not an afterthought. The number 32 came from “the largest state that fits into architecturally visible x86 SSE registers while leaving some free registers for intermediate values”. AVX2 could double it. It cannot, because the constant is part of the on-disk format. This is the general shape of optimizing a persistent format: the moment you define it, your implementation choices freeze.

Runtime dispatch with a function pointer is the pragmatic way to get AVX2 without breaking old CPUs. Compile one function with __attribute__((target("avx2"))), detect AVX2 with CPUID, and swap the pointer on first use. The overhead is one indirect call per 8 kB page, which is nothing.

The correctness argument rests on the compiler. The fallback implementation is not hand-written SIMD; it is the same C code with -funroll-loops -ftree-vectorize, trusting GCC or clang to vectorize the constant multiplication into shifts and adds. The result must be bit-identical to the AVX2 path, and it is, because both are the same source text.

Where the checksum lives

The algorithm: FNV-1a, with a twist

Why thirty-two hashes

The core loop

From 32 bits to 16

Where it is called from

Runtime dispatch: the AVX2 path

Why thirty-two, exactly?

Caveats

N_SUMS is part of the on-disk format

What the checksum does and does not cover

The cost is real

The “in progress” states are subtle

Sixteen bits is not a lot

Look at it yourself

What it all means in practice

Further reading