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 /*
  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/zio.h>
 132 #include <sys/spa.h>
 133
 134 void
 135 fletcher_2_native(const void *buf, uint64_t size, zio_cksum_t *zcp)
 136 {
 137         const uint64_t *ip = buf;
 138         const uint64_t *ipend = ip + (size / sizeof (uint64_t));
 139         uint64_t a0, b0, a1, b1;
 140
 141         for (a0 = b0 = a1 = b1 = 0; ip < ipend; ip += 2) {
 142                 a0 += ip[0];
 143                 a1 += ip[1];
 144                 b0 += a0;
 145                 b1 += a1;
 146         }
 147
 148         ZIO_SET_CHECKSUM(zcp, a0, a1, b0, b1);
 149 }
 150
 151 void
 152 fletcher_2_byteswap(const void *buf, uint64_t size, zio_cksum_t *zcp)
 153 {
 154         const uint64_t *ip = buf;
 155         const uint64_t *ipend = ip + (size / sizeof (uint64_t));
 156         uint64_t a0, b0, a1, b1;
 157
 158         for (a0 = b0 = a1 = b1 = 0; ip < ipend; ip += 2) {
 159                 a0 += BSWAP_64(ip[0]);
 160                 a1 += BSWAP_64(ip[1]);
 161                 b0 += a0;
 162                 b1 += a1;
 163         }
 164
 165         ZIO_SET_CHECKSUM(zcp, a0, a1, b0, b1);
 166 }
 167
 168 void
 169 fletcher_4_native(const void *buf, uint64_t size, zio_cksum_t *zcp)
 170 {
 171         const uint32_t *ip = buf;
 172         const uint32_t *ipend = ip + (size / sizeof (uint32_t));
 173         uint64_t a, b, c, d;
 174
 175         for (a = b = c = d = 0; ip < ipend; ip++) {
 176                 a += ip[0];
 177                 b += a;
 178                 c += b;
 179                 d += c;
 180         }
 181
 182         ZIO_SET_CHECKSUM(zcp, a, b, c, d);
 183 }
 184
 185 void
 186 fletcher_4_byteswap(const void *buf, uint64_t size, zio_cksum_t *zcp)
 187 {
 188         const uint32_t *ip = buf;
 189         const uint32_t *ipend = ip + (size / sizeof (uint32_t));
 190         uint64_t a, b, c, d;
 191
 192         for (a = b = c = d = 0; ip < ipend; ip++) {
 193                 a += BSWAP_32(ip[0]);
 194                 b += a;
 195                 c += b;
 196                 d += c;
 197         }
 198
 199         ZIO_SET_CHECKSUM(zcp, a, b, c, d);
 200 }
 201
 202 void
 203 fletcher_4_incremental_native(const void *buf, uint64_t size,
 204     zio_cksum_t *zcp)
 205 {
 206         const uint32_t *ip = buf;
 207         const uint32_t *ipend = ip + (size / sizeof (uint32_t));
 208         uint64_t a, b, c, d;
 209
 210         a = zcp->zc_word[0];
 211         b = zcp->zc_word[1];
 212         c = zcp->zc_word[2];
 213         d = zcp->zc_word[3];
 214
 215         for (; ip < ipend; ip++) {
 216                 a += ip[0];
 217                 b += a;
 218                 c += b;
 219                 d += c;
 220         }
 221
 222         ZIO_SET_CHECKSUM(zcp, a, b, c, d);
 223 }
 224
 225 void
 226 fletcher_4_incremental_byteswap(const void *buf, uint64_t size,
 227     zio_cksum_t *zcp)
 228 {
 229         const uint32_t *ip = buf;
 230         const uint32_t *ipend = ip + (size / sizeof (uint32_t));
 231         uint64_t a, b, c, d;
 232
 233         a = zcp->zc_word[0];
 234         b = zcp->zc_word[1];
 235         c = zcp->zc_word[2];
 236         d = zcp->zc_word[3];
 237
 238         for (; ip < ipend; ip++) {
 239                 a += BSWAP_32(ip[0]);
 240                 b += a;
 241                 c += b;
 242                 d += c;
 243         }
 244
 245         ZIO_SET_CHECKSUM(zcp, a, b, c, d);
 246 }