sys/cddl/contrib/opensolaris/uts/common/fs/zfs/fletcher.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25
  26 /*
  27  * Fletcher Checksums
  28  * ------------------
  29  *
  30  * ZFS's 2nd and 4th order Fletcher checksums are defined by the following
  31  * recurrence relations:
  32  *
  33  *      a  = a    + f
  34  *       i    i-1    i-1
  35  *
  36  *      b  = b    + a
  37  *       i    i-1    i
  38  *
  39  *      c  = c    + b           (fletcher-4 only)
  40  *       i    i-1    i
  41  *
  42  *      d  = d    + c           (fletcher-4 only)
  43  *       i    i-1    i
  44  *
  45  * Where
  46  *      a_0 = b_0 = c_0 = d_0 = 0
  47  * and
  48  *      f_0 .. f_(n-1) are the input data.
  49  *
  50  * Using standard techniques, these translate into the following series:
  51  *
  52  *           __n_                            __n_
  53  *           \   |                           \   |
  54  *      a  =  >     f                   b  =  >     i * f
  55  *       n   /___|   n - i               n   /___|       n - i
  56  *           i = 1                           i = 1
  57  *
  58  *
  59  *           __n_                            __n_
  60  *           \   |  i*(i+1)                  \   |  i*(i+1)*(i+2)
  61  *      c  =  >     ------- f           d  =  >     ------------- f
  62  *       n   /___|     2     n - i       n   /___|        6        n - i
  63  *           i = 1                           i = 1
  64  *
  65  * For fletcher-2, the f_is are 64-bit, and [ab]_i are 64-bit accumulators.
  66  * Since the additions are done mod (2^64), errors in the high bits may not
  67  * be noticed.  For this reason, fletcher-2 is deprecated.
  68  *
  69  * For fletcher-4, the f_is are 32-bit, and [abcd]_i are 64-bit accumulators.
  70  * A conservative estimate of how big the buffer can get before we overflow
  71  * can be estimated using f_i = 0xffffffff for all i:
  72  *
  73  * % bc
  74  *  f=2^32-1;d=0; for (i = 1; d<2^64; i++) { d += f*i*(i+1)*(i+2)/6 }; (i-1)*4
  75  * 2264
  76  *  quit
  77  * %
  78  *
  79  * So blocks of up to 2k will not overflow.  Our largest block size is
  80  * 128k, which has 32k 4-byte words, so we can compute the largest possible
  81  * accumulators, then divide by 2^64 to figure the max amount of overflow:
  82  *
  83  * % bc
  84  *  a=b=c=d=0; f=2^32-1; for (i=1; i<=32*1024; i++) { a+=f; b+=a; c+=b; d+=c }
  85  *  a/2^64;b/2^64;c/2^64;d/2^64
  86  * 0
  87  * 0
  88  * 1365
  89  * 11186858
  90  *  quit
  91  * %
  92  *
  93  * So a and b cannot overflow.  To make sure each bit of input has some
  94  * effect on the contents of c and d, we can look at what the factors of
  95  * the coefficients in the equations for c_n and d_n are.  The number of 2s
  96  * in the factors determines the lowest set bit in the multiplier.  Running
  97  * through the cases for n*(n+1)/2 reveals that the highest power of 2 is
  98  * 2^14, and for n*(n+1)*(n+2)/6 it is 2^15.  So while some data may overflow
  99  * the 64-bit accumulators, every bit of every f_i effects every accumulator,
 100  * even for 128k blocks.
 101  *
 102  * If we wanted to make a stronger version of fletcher4 (fletcher4c?),
 103  * we could do our calculations mod (2^32 - 1) by adding in the carries
 104  * periodically, and store the number of carries in the top 32-bits.
 105  *
 106  * --------------------
 107  * Checksum Performance
 108  * --------------------
 109  *
 110  * There are two interesting components to checksum performance: cached and
 111  * uncached performance.  With cached data, fletcher-2 is about four times
 112  * faster than fletcher-4.  With uncached data, the performance difference is
 113  * negligible, since the cost of a cache fill dominates the processing time.
 114  * Even though fletcher-4 is slower than fletcher-2, it is still a pretty
 115  * efficient pass over the data.
 116  *
 117  * In normal operation, the data which is being checksummed is in a buffer
 118  * which has been filled either by:
 119  *
 120  *      1. a compression step, which will be mostly cached, or
 121  *      2. a bcopy() or copyin(), which will be uncached (because the
 122  *         copy is cache-bypassing).
 123  *
 124  * For both cached and uncached data, both fletcher checksums are much faster
 125  * than sha-256, and slower than 'off', which doesn't touch the data at all.
 126  */
 127
 128 #include <sys/types.h>
 129 #include <sys/sysmacros.h>
 130 #include <sys/byteorder.h>
 131 #include <sys/spa.h>
 132
 133 void
 134 fletcher_2_native(const void *buf, uint64_t size, zio_cksum_t *zcp)
 135 {
 136         const uint64_t *ip = buf;
 137         const uint64_t *ipend = ip + (size / sizeof (uint64_t));
 138         uint64_t a0, b0, a1, b1;
 139
 140         for (a0 = b0 = a1 = b1 = 0; ip < ipend; ip += 2) {
 141                 a0 += ip[0];
 142                 a1 += ip[1];
 143                 b0 += a0;
 144                 b1 += a1;
 145         }
 146
 147         ZIO_SET_CHECKSUM(zcp, a0, a1, b0, b1);
 148 }
 149
 150 void
 151 fletcher_2_byteswap(const void *buf, uint64_t size, zio_cksum_t *zcp)
 152 {
 153         const uint64_t *ip = buf;
 154         const uint64_t *ipend = ip + (size / sizeof (uint64_t));
 155         uint64_t a0, b0, a1, b1;
 156
 157         for (a0 = b0 = a1 = b1 = 0; ip < ipend; ip += 2) {
 158                 a0 += BSWAP_64(ip[0]);
 159                 a1 += BSWAP_64(ip[1]);
 160                 b0 += a0;
 161                 b1 += a1;
 162         }
 163
 164         ZIO_SET_CHECKSUM(zcp, a0, a1, b0, b1);
 165 }
 166
 167 void
 168 fletcher_4_native(const void *buf, uint64_t size, zio_cksum_t *zcp)
 169 {
 170         const uint32_t *ip = buf;
 171         const uint32_t *ipend = ip + (size / sizeof (uint32_t));
 172         uint64_t a, b, c, d;
 173
 174         for (a = b = c = d = 0; ip < ipend; ip++) {
 175                 a += ip[0];
 176                 b += a;
 177                 c += b;
 178                 d += c;
 179         }
 180
 181         ZIO_SET_CHECKSUM(zcp, a, b, c, d);
 182 }
 183
 184 void
 185 fletcher_4_byteswap(const void *buf, uint64_t size, zio_cksum_t *zcp)
 186 {
 187         const uint32_t *ip = buf;
 188         const uint32_t *ipend = ip + (size / sizeof (uint32_t));
 189         uint64_t a, b, c, d;
 190
 191         for (a = b = c = d = 0; ip < ipend; ip++) {
 192                 a += BSWAP_32(ip[0]);
 193                 b += a;
 194                 c += b;
 195                 d += c;
 196         }
 197
 198         ZIO_SET_CHECKSUM(zcp, a, b, c, d);
 199 }
 200
 201 void
 202 fletcher_4_incremental_native(const void *buf, uint64_t size,
 203     zio_cksum_t *zcp)
 204 {
 205         const uint32_t *ip = buf;
 206         const uint32_t *ipend = ip + (size / sizeof (uint32_t));
 207         uint64_t a, b, c, d;
 208
 209         a = zcp->zc_word[0];
 210         b = zcp->zc_word[1];
 211         c = zcp->zc_word[2];
 212         d = zcp->zc_word[3];
 213
 214         for (; ip < ipend; ip++) {
 215                 a += ip[0];
 216                 b += a;
 217                 c += b;
 218                 d += c;
 219         }
 220
 221         ZIO_SET_CHECKSUM(zcp, a, b, c, d);
 222 }
 223
 224 void
 225 fletcher_4_incremental_byteswap(const void *buf, uint64_t size,
 226     zio_cksum_t *zcp)
 227 {
 228         const uint32_t *ip = buf;
 229         const uint32_t *ipend = ip + (size / sizeof (uint32_t));
 230         uint64_t a, b, c, d;
 231
 232         a = zcp->zc_word[0];
 233         b = zcp->zc_word[1];
 234         c = zcp->zc_word[2];
 235         d = zcp->zc_word[3];
 236
 237         for (; ip < ipend; ip++) {
 238                 a += BSWAP_32(ip[0]);
 239                 b += a;
 240                 c += b;
 241                 d += c;
 242         }
 243
 244         ZIO_SET_CHECKSUM(zcp, a, b, c, d);
 245 }