parallel-checksum.patch

*** a/src/backend/storage/page/bufpage.c
--- b/src/backend/storage/page/bufpage.c
***************
*** 928,1011 **** PageSetChecksumInplace(Page page, BlockNumber blkno)
  
  /*
   * Calculate checksum for a PostgreSQL Page. This includes the page number (to
   * detect the case when a page is somehow moved to a different location), the
   * page header (excluding the checksum itself), and the page data.
   *
!  * The checksum algorithm is a modified Fletcher 64-bit (which is
!  * order-sensitive). The modification is because, at the end, we have two
!  * 64-bit sums, but we only have room for a 16-bit checksum. So, instead of
!  * using a modulus of 2^32 - 1, we use 2^8 - 1; making it also resemble a
!  * Fletcher 16-bit. We don't use Fletcher 16-bit directly, because processing
!  * single bytes at a time is slower.
   */
  static uint16
  PageCalcChecksum16(Page page, BlockNumber blkno)
  {
! 	PageHeaderData		 header_copy;
! 	uint32				*ptr32Header = (uint32 *) &header_copy;
! 	uint32				*ptr32Page	 = (uint32 *) page;
! 	int64				 sum1		 = 0;
! 	int64				 sum2		 = 0;
  	uint16				 checksum	 = 0;
  	uint8				*p8Checksum	 = (uint8 *) &checksum;
! 	int					 i;
  
  	/* only calculate the checksum for properly-initialized pages */
  	Assert(!PageIsNew(page));
  
  	/*
  	 * Initialize the checksum calculation with the page number. This helps
  	 * catch corruption from whole pages being transposed with other whole
  	 * pages.
  	 */
! 	sum1 = sum2 = (uint64) blkno;
  
  	/*
! 	 * Make a copy of the page header and set the checksum to zero in the
! 	 * copy. That allows us to calculate the checksum 32 bits at a time while
! 	 * ignoring only the checksum field during calculation.
  	 */
! 	memcpy(&header_copy, page, SizeOfPageHeaderData);
! 	header_copy.pd_checksum = 0;
! 
! 	/* compute the checksum of the header */
! 	for (i = 0; i < SizeOfPageHeaderData / sizeof(uint32); i++)
! 	{
! 		sum1 += ptr32Header[i];
! 		sum2 += sum1;
! 	}
  
  	/* now checksum the rest of the page */
! 	for (i = SizeOfPageHeaderData; i < BLCKSZ / sizeof(uint32); i++)
! 	{
! 		sum1 += ptr32Page[i];
! 		sum2 += sum1;
  
! 		/*
! 		 * Testing for overflow makes the algorithm slower, but we know that
! 		 * overflow won't happen, so only use an Assert. The overflow won't
! 		 * happen because sum2 (the larger sum) can grow to a maximum of:
! 		 *
! 		 *   2^32 * (N^2 - N)/2
! 		 *
! 		 * where N is the number of iterations of this loop. The largest block
! 		 * size is 32KB, which is 8192 iterations, which yields a number less
! 		 * than 2^61, which is still within the range of a signed int64.
! 		 */
! 		Assert(BLCKSZ <= 32768 && sum1 >=0 && sum2 >= 0);
! 	}
  
  	/*
  	 * Store the sums as bytes in the checksum. Mod 255 is used instead of 256
  	 * because 256 would miss errors in the high 24 bits of a 32-bit word read
  	 * from the page. We add one to shift the range from 0..255 to 1..256, to
  	 * make zero invalid for checksum bytes (which seems wise).
  	 */
! 	p8Checksum[0] = (sum1 % 255) + 1;
! 	p8Checksum[1] = (sum2 % 255) + 1;
  
  #ifdef DEBUG_CHECKSUM
  	elog(LOG, "checksum %u", checksum);
  #endif
  
  	return checksum;
--- 928,997 ----
  
  /*
   * Calculate checksum for a PostgreSQL Page. This includes the page number (to
   * detect the case when a page is somehow moved to a different location), the
   * page header (excluding the checksum itself), and the page data.
   *
!  * The checksum algorithm is to accumulate 64 parallel 16bit checksum values
!  * using the evolution function value = old_value * prime + data. The parallel
!  * accumulation is done to cut data dependencies and enable vectorization of
!  * the inner loop. Without vector instructions this code is likely to be
!  * load/store bound.
   */
+ #define N_SUMS 64
+ #define HASH_PRIME 31
+ #define PageChecksumOffset (offsetof(PageHeaderData, pd_checksum))
+ 
  static uint16
  PageCalcChecksum16(Page page, BlockNumber blkno)
  {
! 	uint16				(*pageArray)[N_SUMS] = (uint16 (*)[N_SUMS]) page;
! 	uint16				 sums[N_SUMS];
! 	uint32				 combined_sum;
  	uint16				 checksum	 = 0;
  	uint8				*p8Checksum	 = (uint8 *) &checksum;
! 	int					 i, j;
  
  	/* only calculate the checksum for properly-initialized pages */
  	Assert(!PageIsNew(page));
  
  	/*
  	 * Initialize the checksum calculation with the page number. This helps
  	 * catch corruption from whole pages being transposed with other whole
  	 * pages.
  	 */
! 	combined_sum = blkno;
! 
! 	/* First iteration needs to consider the checksum position as zero */
! 	for (i = 0; i < N_SUMS; i++)
! 		sums[i] = (i == PageChecksumOffset / sizeof(uint16)) ? 0 : pageArray[0][i];
  
  	/*
! 	 * As buffer size is a power of two we can safely do it a smaller power
! 	 * of two steps a time.
  	 */
! 	Assert(BLCKSZ / sizeof(uint16) % N_SUMS == 0);
  
  	/* now checksum the rest of the page */
! 	for (i = 1; i < BLCKSZ / sizeof(uint16) / N_SUMS; i++)
! 		for (j = 0; j < N_SUMS; j++)
! 			/* Written as two separate lines to unconfuse gcc */
! 			sums[j] = sums[j]*HASH_PRIME + pageArray[i][j];
  
! 	/* combine the separate sums into a single value */
! 	for (i = 0; i < N_SUMS; i++)
! 		combined_sum = combined_sum*HASH_PRIME + sums[i];
  
  	/*
  	 * Store the sums as bytes in the checksum. Mod 255 is used instead of 256
  	 * because 256 would miss errors in the high 24 bits of a 32-bit word read
  	 * from the page. We add one to shift the range from 0..255 to 1..256, to
  	 * make zero invalid for checksum bytes (which seems wise).
  	 */
! 	p8Checksum[0] = (combined_sum % 255) + 1;
! 	p8Checksum[1] = (combined_sum*HASH_PRIME % 255) + 1;
  
  #ifdef DEBUG_CHECKSUM
  	elog(LOG, "checksum %u", checksum);
  #endif
  
  	return checksum;