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