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