zfs_fletcher.c revision b24ab6762772a3f6a89393947930c7fa61306783
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2009 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
/*
* Fletcher Checksums
* ------------------
*
* ZFS's 2nd and 4th order Fletcher checksums are defined by the following
* recurrence relations:
*
* a = a + f
* i i-1 i-1
*
* b = b + a
* i i-1 i
*
* c = c + b (fletcher-4 only)
* i i-1 i
*
* d = d + c (fletcher-4 only)
* i i-1 i
*
* Where
* a_0 = b_0 = c_0 = d_0 = 0
* and
* f_0 .. f_(n-1) are the input data.
*
* Using standard techniques, these translate into the following series:
*
* __n_ __n_
* \ | \ |
* a = > f b = > i * f
* n /___| n - i n /___| n - i
* i = 1 i = 1
*
*
* __n_ __n_
* \ | i*(i+1) \ | i*(i+1)*(i+2)
* c = > ------- f d = > ------------- f
* n /___| 2 n - i n /___| 6 n - i
* i = 1 i = 1
*
* For fletcher-2, the f_is are 64-bit, and [ab]_i are 64-bit accumulators.
* Since the additions are done mod (2^64), errors in the high bits may not
* be noticed. For this reason, fletcher-2 is deprecated.
*
* For fletcher-4, the f_is are 32-bit, and [abcd]_i are 64-bit accumulators.
* A conservative estimate of how big the buffer can get before we overflow
* can be estimated using f_i = 0xffffffff for all i:
*
* % bc
* f=2^32-1;d=0; for (i = 1; d<2^64; i++) { d += f*i*(i+1)*(i+2)/6 }; (i-1)*4
* 2264
* quit
* %
*
* So blocks of up to 2k will not overflow. Our largest block size is
* 128k, which has 32k 4-byte words, so we can compute the largest possible
* accumulators, then divide by 2^64 to figure the max amount of overflow:
*
* % bc
* a=b=c=d=0; f=2^32-1; for (i=1; i<=32*1024; i++) { a+=f; b+=a; c+=b; d+=c }
* a/2^64;b/2^64;c/2^64;d/2^64
* 0
* 0
* 1365
* 11186858
* quit
* %
*
* So a and b cannot overflow. To make sure each bit of input has some
* effect on the contents of c and d, we can look at what the factors of
* the coefficients in the equations for c_n and d_n are. The number of 2s
* in the factors determines the lowest set bit in the multiplier. Running
* through the cases for n*(n+1)/2 reveals that the highest power of 2 is
* 2^14, and for n*(n+1)*(n+2)/6 it is 2^15. So while some data may overflow
* the 64-bit accumulators, every bit of every f_i effects every accumulator,
* even for 128k blocks.
*
* If we wanted to make a stronger version of fletcher4 (fletcher4c?),
* we could do our calculations mod (2^32 - 1) by adding in the carries
* periodically, and store the number of carries in the top 32-bits.
*
* --------------------
* Checksum Performance
* --------------------
*
* There are two interesting components to checksum performance: cached and
* uncached performance. With cached data, fletcher-2 is about four times
* faster than fletcher-4. With uncached data, the performance difference is
* negligible, since the cost of a cache fill dominates the processing time.
* Even though fletcher-4 is slower than fletcher-2, it is still a pretty
* efficient pass over the data.
*
* In normal operation, the data which is being checksummed is in a buffer
* which has been filled either by:
*
* 1. a compression step, which will be mostly cached, or
* 2. a bcopy() or copyin(), which will be uncached (because the
* copy is cache-bypassing).
*
* For both cached and uncached data, both fletcher checksums are much faster
* than sha-256, and slower than 'off', which doesn't touch the data at all.
*/
#include <sys/sysmacros.h>
#include <sys/byteorder.h>
void
{
}
}
void
{
}
}
void
{
uint64_t a, b, c, d;
a += ip[0];
b += a;
c += b;
d += c;
}
ZIO_SET_CHECKSUM(zcp, a, b, c, d);
}
void
{
uint64_t a, b, c, d;
b += a;
c += b;
d += c;
}
ZIO_SET_CHECKSUM(zcp, a, b, c, d);
}
void
{
uint64_t a, b, c, d;
a += ip[0];
b += a;
c += b;
d += c;
}
ZIO_SET_CHECKSUM(zcp, a, b, c, d);
}
void
{
uint64_t a, b, c, d;
b += a;
c += b;
d += c;
}
ZIO_SET_CHECKSUM(zcp, a, b, c, d);
}