Switch to CRC-32C in WAL and other places

Enterprise / PostgreSQL - Heikki Linnakangas [iki.fi] - 4 November 2014 03:39 UTC

The old algorithm was found to not be the usual CRC-32 algorithm, used by Ethernet et al. We were using a non-reflected lookup table with code meant for a reflected lookup table. That's a strange combination that AFAICS does not correspond to any bit-wise CRC calculation, which makes it difficult to reason about its properties. Although it has worked well in practice, seems safer to use a well-known algorithm.

Since we're changing the algorithm anyway, we might as well choose a different polynomial. The Castagnoli polynomial has better error-correcting properties than the traditional CRC-32 polynomial, even if we had implemented it correctly. Another reason for picking that is that some new CPUs have hardware support for calculating CRC-32C, but not CRC-32, let alone our strange variant of it. This patch doesn't add any support for such hardware, but a future patch could now do that.

The old algorithm is kept around for tsquery and pg_trgm, which use the
values in indexes that need to remain compatible so that pg_upgrade works. While we're at it, share the old lookup table for CRC-32 calculation between hstore, ltree and core. They all use the same table, so might as well.

5028f22 Switch to CRC-32C in WAL and other places.
contrib/hstore/Makefile | 2 +-
contrib/hstore/crc32.c | 106 -------------------------
contrib/hstore/crc32.h | 13 ---
contrib/hstore/hstore_gist.c | 16 +++-
contrib/ltree/crc32.c | 114 +++++----------------------
contrib/pg_trgm/trgm_op.c | 6 +-
src/backend/access/transam/twophase.c | 24 +++---
src/backend/access/transam/xlog.c | 50 ++++++------
src/backend/access/transam/xlogreader.c | 12 +--
src/backend/replication/logical/snapbuild.c | 28 +++----
src/backend/replication/slot.c | 20 ++---
src/backend/utils/adt/tsgistidx.c | 6 +-
src/backend/utils/adt/tsquery.c | 12 +--
src/backend/utils/cache/relmapper.c | 16 ++--
src/bin/pg_controldata/pg_controldata.c | 12 +--
src/bin/pg_resetxlog/pg_resetxlog.c | 30 +++----
src/include/access/xlog_internal.h | 2 +-
src/include/catalog/catversion.h | 2 +-
src/include/utils/pg_crc.h | 93 ++++++++++++++++++----
src/include/utils/pg_crc_tables.h | 77 +++++++++++++++++-
20 files changed, 300 insertions(+), 341 deletions(-)

Upstream: git.postgresql.org

  • Share