parallel-fnv-checksum.patch

*** a/src/backend/storage/page/README
--- b/src/backend/storage/page/README
***************
*** 61,63 **** checksums are enabled.  Systems in Hot-Standby mode may benefit from hint bits
--- 61,110 ----
  being set, but with checksums enabled, a page cannot be dirtied after setting a
  hint bit (due to the torn page risk). So, it must wait for full-page images
  containing the hint bit updates to arrive from the master.
+ 
+ Checksum algorithm
+ ------------------
+ 
+ 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 4 bytes at
+ a time according to the formula:
+ 
+     hash = (hash ^ value) * FNV_PRIME(16777619)
+ 
+ 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 3 bits. The number 3 was chosen as it is a small odd, prime, and
+ experimentally provides enough mixing for the high order bits to avalanche
+ into lower positions. The actual hash formula used as the basis is:
+ 
+     hash = (hash ^ value) * ((hash ^ value) >> 3)
+ 
+ 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. Each hash function 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. The page is then treated
+ as 32 wide array of 32bit values and each column is aggregated according to
+ the above formula. Finally one more iteration of the formula is performed with
+ value 0 to mix the bits of the last value added.
+ 
+ The partial checksums are then aggregated together using xor and the block
+ number is xor'ed in to detect transposed pages. This results in a 32bit
+ checksum. This is then taken modulo 2^16-1 to fit this value into 16bits
+ while keeping the value 0 as a special invalid checksum value. This results
+ in a very slight bias towards lower values but this is not significant for
+ the performance of the checksum.
+ 
+ Vectorization of the algorithm requires 32bit x 32bit -> 32bit integer
+ multiplication instruction. As of 2013 the corresponding instruction is
+ available on x86 SSE4.1 extensions (pmulld) and ARM NEON (vmul.i32).
+ Vectorization requires a compiler to do the vectorization for us. For recent
+ GCC versions the flags -msse4.1 -funroll-loops -ftree-vectorize are enough
+ to achieve vectorization.
*** a/src/backend/storage/page/bufpage.c
--- b/src/backend/storage/page/bufpage.c
***************
*** 936,941 **** PageSetChecksumInplace(Page page, BlockNumber blkno)
--- 936,979 ----
  	return;
  }
  
+ /* ----------------------------------------------------------------
+  *						Checksum functions
+  * ----------------------------------------------------------------
+  */
+ 
+ /*
+  * See src/backend/storage/page/README for specification of the
+  * checksum algorithm used here.
+  */
+ 
+ /* number of checksums to calculate in parallel */
+ #define N_SUMS 32
+ /* prime multiplier of FNV-1a hash */
+ #define FNV_PRIME 16777619
+ 
+ /*
+  * 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
+ };
+ 
+ /*
+  * Calculate one round of the checksum.
+  */
+ #define CHECKSUM_COMP(checksum, value) do {\
+ 	uint32 __tmp = (checksum) ^ (value);\
+ 	(checksum) = __tmp * FNV_PRIME ^ (__tmp >> 3);\
+ } while (0)
+ 
  /*
   * Calculate checksum for a PostgreSQL Page. This includes the block number (to
   * detect the case when a page is somehow moved to a different location), the
***************
*** 948,980 **** PageSetChecksumInplace(Page page, BlockNumber blkno)
  static uint16
  PageCalcChecksum16(Page page, BlockNumber blkno)
  {
! 	pg_crc32    		crc;
! 	PageHeader	p = (PageHeader) page;
  
  	/* only calculate the checksum for properly-initialized pages */
  	Assert(!PageIsNew(page));
  
! 	INIT_CRC32(crc);
  
! 	/*
! 	 * Initialize the checksum calculation with the block number. This helps
! 	 * catch corruption from whole blocks being transposed with other whole
! 	 * blocks.
! 	 */
! 	COMP_CRC32(crc, &blkno, sizeof(blkno));
  
! 	/*
! 	 * Now add in the LSN, which is always the first field on the page.
! 	 */
! 	COMP_CRC32(crc, page, sizeof(p->pd_lsn));
  
! 	/*
! 	 * Now add the rest of the page, skipping the pd_checksum field.
! 	 */
! 	COMP_CRC32(crc, page + sizeof(p->pd_lsn) + sizeof(p->pd_checksum),
! 				  BLCKSZ - sizeof(p->pd_lsn) - sizeof(p->pd_checksum));
  
! 	FIN_CRC32(crc);
  
! 	return (uint16) crc;
  }
--- 986,1026 ----
  static uint16
  PageCalcChecksum16(Page page, BlockNumber blkno)
  {
! 	uint32 sums[N_SUMS];
! 	uint32 (*pageArr)[N_SUMS] = (uint32 (*)[N_SUMS]) page;
! 	uint32 result = blkno;
! 	int i, j;
! 	int pd_checksum_word = offsetof(PageHeaderData, pd_checksum)/sizeof(uint32);
! 	int pd_checksum_half = (offsetof(PageHeaderData, pd_checksum) % sizeof(uint32)) / sizeof(uint16);
  
  	/* only calculate the checksum for properly-initialized pages */
  	Assert(!PageIsNew(page));
  
! 	/* initialize partial checksums to their corresponding offsets */
! 	memcpy(sums, checksumBaseOffsets, sizeof(checksumBaseOffsets));
  
! 	/* first iteration needs to mask out pd_checksum field itself with zero */
! 	for (j = 0; j < N_SUMS; j++)
! 	{
! 		uint32 value = pageArr[0][j];
! 		if (j == pd_checksum_word)
! 			((uint16*) &value)[pd_checksum_half] = 0;
! 		CHECKSUM_COMP(sums[j], value);
! 	}
  
! 	/* now add in the rest of the page */
! 	for (i = 1; i < BLCKSZ/sizeof(uint32)/N_SUMS; i++)
! 		for (j = 0; j < N_SUMS; j++)
! 			CHECKSUM_COMP(sums[j], pageArr[i][j]);
  
! 	/* finally add in one round of zeroes for one more layer of mixing */
! 	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];
  
! 	/* use mod mapping to map the value into 16 bits and offset from zero */
! 	return (result % 65535) + 1;
  }