Add Linus' optimized sha1 hash for checksum

It does appear to be pretty fast.

Signed-off-by: Jens Axboe <jens.axboe@oracle.com>

diff --git a/HOWTO b/HOWTO
index aec00e84e548f1c9d65952e73803d8fcb5df53e9..bc23052d61e568434b23488c150e525d0ee48407 100644 (file)
--- a/HOWTO
+++ b/HOWTO
@@ -794,6 +794,8 @@ verify=str  If writing to a file, fio can verify the file contents
 
                        sha256  Use sha256 as the checksum function.
 
 
                        sha256  Use sha256 as the checksum function.
 

+                       sha1    Use optimized sha1 as the checksum function.
+

                        meta    Write extra information about each io
                                (timestamp, block number etc.). The block
                                number is verified.
                        meta    Write extra information about each io
                                (timestamp, block number etc.). The block
                                number is verified.

diff --git a/Makefile b/Makefile
index 99acec97921120983ec1b4698aefaab4b2212da1..59e53a723d722d322b169eb93ec9cbd2fcc7897a 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -14,6 +14,7 @@ OBJS += crc/crc32.o
 OBJS += crc/crc32c.o
 OBJS += crc/crc32c-intel.o
 OBJS += crc/crc64.o
 OBJS += crc/crc32c.o
 OBJS += crc/crc32c-intel.o
 OBJS += crc/crc64.o

+OBJS += crc/sha1.o

 OBJS += crc/sha256.o
 OBJS += crc/sha512.o
 OBJS += crc/md5.o
 OBJS += crc/sha256.o
 OBJS += crc/sha512.o
 OBJS += crc/md5.o

diff --git a/Makefile.FreeBSD b/Makefile.FreeBSD
index 30277cdce364c9833599c773e2be82d745d99751..b9c6f83e701af220dc4fd1a3c7d13673f90faa7e 100644 (file)
--- a/Makefile.FreeBSD
+++ b/Makefile.FreeBSD
@@ -14,6 +14,7 @@ OBJS += crc/crc32.o
 OBJS += crc/crc32c.o
 OBJS += crc/crc32c-intel.o
 OBJS += crc/crc64.o
 OBJS += crc/crc32c.o
 OBJS += crc/crc32c-intel.o
 OBJS += crc/crc64.o

+OBJS += crc/sha1.o

 OBJS += crc/sha256.o
 OBJS += crc/sha512.o
 OBJS += crc/md5.o
 OBJS += crc/sha256.o
 OBJS += crc/sha512.o
 OBJS += crc/md5.o

diff --git a/Makefile.solaris b/Makefile.solaris
index 27adf1bd6745a8858b996c4e69c62f204f153a86..595f85450d143e966b8dbf556d9517cf9fd93adc 100644 (file)
--- a/Makefile.solaris
+++ b/Makefile.solaris
@@ -12,6 +12,7 @@ OBJS += crc/crc32.o
 OBJS += crc/crc32c.o
 OBJS += crc/crc32c-intel.o
 OBJS += crc/crc64.o
 OBJS += crc/crc32c.o
 OBJS += crc/crc32c-intel.o
 OBJS += crc/crc64.o

+OBJS += crc/sha1.o

 OBJS += crc/sha256.o
 OBJS += crc/sha512.o
 OBJS += crc/md5.o
 OBJS += crc/sha256.o
 OBJS += crc/sha512.o
 OBJS += crc/md5.o

diff --git a/crc/sha1.c b/crc/sha1.c
new file mode 100644 (file)
index 0000000..6206797
--- /dev/null
+++ b/crc/sha1.c
@@ -0,0 +1,220 @@
+/*
+ * Based on the Mozilla SHA1 (see mozilla-sha1/sha1.c),
+ * optimized to do word accesses rather than byte accesses,
+ * and to avoid unnecessary copies into the context array.
+ */
+
+#include <string.h>
+#include <arpa/inet.h>
+
+#include "sha1.h"
+
+/* Hash one 64-byte block of data */
+static void blk_SHA1Block(struct sha1_ctx *ctx, const unsigned int *data);
+
+void sha1_init(struct sha1_ctx *ctx)
+{
+       ctx->size = 0;
+
+       /* Initialize H with the magic constants (see FIPS180 for constants)
+        */
+       ctx->H[0] = 0x67452301;
+       ctx->H[1] = 0xefcdab89;
+       ctx->H[2] = 0x98badcfe;
+       ctx->H[3] = 0x10325476;
+       ctx->H[4] = 0xc3d2e1f0;
+}
+
+void sha1_update(struct sha1_ctx *ctx, const void *data, unsigned long len)
+{
+       int lenW = ctx->size & 63;
+
+       ctx->size += len;
+
+       /* Read the data into W and process blocks as they get full
+        */
+       if (lenW) {
+               int left = 64 - lenW;
+               if (len < left)
+                       left = len;
+               memcpy(lenW + (char *)ctx->W, data, left);
+               lenW = (lenW + left) & 63;
+               len -= left;
+               data += left;
+               if (lenW)
+                       return;
+               blk_SHA1Block(ctx, ctx->W);
+       }
+       while (len >= 64) {
+               blk_SHA1Block(ctx, data);
+               data += 64;
+               len -= 64;
+       }
+       if (len)
+               memcpy(ctx->W, data, len);
+}
+
+void sha1_final(unsigned char hashout[20], struct sha1_ctx *ctx)
+{
+       static const unsigned char pad[64] = { 0x80 };
+       unsigned int padlen[2];
+       int i;
+
+       /* Pad with a binary 1 (ie 0x80), then zeroes, then length
+        */
+       padlen[0] = htonl(ctx->size >> 29);
+       padlen[1] = htonl(ctx->size << 3);
+
+       i = ctx->size & 63;
+       sha1_update(ctx, pad, 1+ (63 & (55 - i)));
+       sha1_update(ctx, padlen, 8);
+
+       /* Output hash
+        */
+       for (i = 0; i < 5; i++)
+               ((unsigned int *)hashout)[i] = htonl(ctx->H[i]);
+}
+
+#if defined(__i386__) || defined(__x86_64__)
+
+#define SHA_ASM(op, x, n) ({ unsigned int __res; __asm__(op " %1,%0":"=r" (__res):"i" (n), "0" (x)); __res; })
+#define SHA_ROL(x,n)   SHA_ASM("rol", x, n)
+#define SHA_ROR(x,n)   SHA_ASM("ror", x, n)
+
+#else
+
+#define SHA_ROT(X,l,r) (((X) << (l)) | ((X) >> (r)))
+#define SHA_ROL(X,n)   SHA_ROT(X,n,32-(n))
+#define SHA_ROR(X,n)   SHA_ROT(X,32-(n),n)
+
+#endif
+
+/* This "rolls" over the 512-bit array */
+#define W(x) (array[(x)&15])
+#define setW(x, val) (*(volatile unsigned int *)&W(x) = (val))
+
+/*
+ * Where do we get the source from? The first 16 iterations get it from
+ * the input data, the next mix it from the 512-bit array.
+ */
+#define SHA_SRC(t) htonl(data[t])
+#define SHA_MIX(t) SHA_ROL(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1)
+
+#define SHA_ROUND(t, input, fn, constant, A, B, C, D, E) do { \
+       unsigned int TEMP = input(t); setW(t, TEMP); \
+       E += TEMP + SHA_ROL(A,5) + (fn) + (constant); \
+       B = SHA_ROR(B, 2); } while (0)
+
+#define T_0_15(t, A, B, C, D, E)  SHA_ROUND(t, SHA_SRC, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )
+#define T_16_19(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )
+#define T_20_39(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (B^C^D) , 0x6ed9eba1, A, B, C, D, E )
+#define T_40_59(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, ((B&C)+(D&(B^C))) , 0x8f1bbcdc, A, B, C, D, E )
+#define T_60_79(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (B^C^D) ,  0xca62c1d6, A, B, C, D, E )
+
+static void blk_SHA1Block(struct sha1_ctx *ctx, const unsigned int *data)
+{
+       unsigned int A,B,C,D,E;
+       unsigned int array[16];
+
+       A = ctx->H[0];
+       B = ctx->H[1];
+       C = ctx->H[2];
+       D = ctx->H[3];
+       E = ctx->H[4];
+
+       /* Round 1 - iterations 0-16 take their input from 'data' */
+       T_0_15( 0, A, B, C, D, E);
+       T_0_15( 1, E, A, B, C, D);
+       T_0_15( 2, D, E, A, B, C);
+       T_0_15( 3, C, D, E, A, B);
+       T_0_15( 4, B, C, D, E, A);
+       T_0_15( 5, A, B, C, D, E);
+       T_0_15( 6, E, A, B, C, D);
+       T_0_15( 7, D, E, A, B, C);
+       T_0_15( 8, C, D, E, A, B);
+       T_0_15( 9, B, C, D, E, A);
+       T_0_15(10, A, B, C, D, E);
+       T_0_15(11, E, A, B, C, D);
+       T_0_15(12, D, E, A, B, C);
+       T_0_15(13, C, D, E, A, B);
+       T_0_15(14, B, C, D, E, A);
+       T_0_15(15, A, B, C, D, E);
+
+       /* Round 1 - tail. Input from 512-bit mixing array */
+       T_16_19(16, E, A, B, C, D);
+       T_16_19(17, D, E, A, B, C);
+       T_16_19(18, C, D, E, A, B);
+       T_16_19(19, B, C, D, E, A);
+
+       /* Round 2 */
+       T_20_39(20, A, B, C, D, E);
+       T_20_39(21, E, A, B, C, D);
+       T_20_39(22, D, E, A, B, C);
+       T_20_39(23, C, D, E, A, B);
+       T_20_39(24, B, C, D, E, A);
+       T_20_39(25, A, B, C, D, E);
+       T_20_39(26, E, A, B, C, D);
+       T_20_39(27, D, E, A, B, C);
+       T_20_39(28, C, D, E, A, B);
+       T_20_39(29, B, C, D, E, A);
+       T_20_39(30, A, B, C, D, E);
+       T_20_39(31, E, A, B, C, D);
+       T_20_39(32, D, E, A, B, C);
+       T_20_39(33, C, D, E, A, B);
+       T_20_39(34, B, C, D, E, A);
+       T_20_39(35, A, B, C, D, E);
+       T_20_39(36, E, A, B, C, D);
+       T_20_39(37, D, E, A, B, C);
+       T_20_39(38, C, D, E, A, B);
+       T_20_39(39, B, C, D, E, A);
+
+       /* Round 3 */
+       T_40_59(40, A, B, C, D, E);
+       T_40_59(41, E, A, B, C, D);
+       T_40_59(42, D, E, A, B, C);
+       T_40_59(43, C, D, E, A, B);
+       T_40_59(44, B, C, D, E, A);
+       T_40_59(45, A, B, C, D, E);
+       T_40_59(46, E, A, B, C, D);
+       T_40_59(47, D, E, A, B, C);
+       T_40_59(48, C, D, E, A, B);
+       T_40_59(49, B, C, D, E, A);
+       T_40_59(50, A, B, C, D, E);
+       T_40_59(51, E, A, B, C, D);
+       T_40_59(52, D, E, A, B, C);
+       T_40_59(53, C, D, E, A, B);
+       T_40_59(54, B, C, D, E, A);
+       T_40_59(55, A, B, C, D, E);
+       T_40_59(56, E, A, B, C, D);
+       T_40_59(57, D, E, A, B, C);
+       T_40_59(58, C, D, E, A, B);
+       T_40_59(59, B, C, D, E, A);
+
+       /* Round 4 */
+       T_60_79(60, A, B, C, D, E);
+       T_60_79(61, E, A, B, C, D);
+       T_60_79(62, D, E, A, B, C);
+       T_60_79(63, C, D, E, A, B);
+       T_60_79(64, B, C, D, E, A);
+       T_60_79(65, A, B, C, D, E);
+       T_60_79(66, E, A, B, C, D);
+       T_60_79(67, D, E, A, B, C);
+       T_60_79(68, C, D, E, A, B);
+       T_60_79(69, B, C, D, E, A);
+       T_60_79(70, A, B, C, D, E);
+       T_60_79(71, E, A, B, C, D);
+       T_60_79(72, D, E, A, B, C);
+       T_60_79(73, C, D, E, A, B);
+       T_60_79(74, B, C, D, E, A);
+       T_60_79(75, A, B, C, D, E);
+       T_60_79(76, E, A, B, C, D);
+       T_60_79(77, D, E, A, B, C);
+       T_60_79(78, C, D, E, A, B);
+       T_60_79(79, B, C, D, E, A);
+
+       ctx->H[0] += A;
+       ctx->H[1] += B;
+       ctx->H[2] += C;
+       ctx->H[3] += D;
+       ctx->H[4] += E;
+}

diff --git a/crc/sha1.h b/crc/sha1.h
new file mode 100644 (file)
index 0000000..af4165a
--- /dev/null
+++ b/crc/sha1.h
@@ -0,0 +1,20 @@
+#ifndef FIO_SHA1
+#define FIO_SHA1
+
+/*
+ * Based on the Mozilla SHA1 (see mozilla-sha1/sha1.h),
+ * optimized to do word accesses rather than byte accesses,
+ * and to avoid unnecessary copies into the context array.
+ */
+
+struct sha1_ctx {
+       uint32_t *H;
+       unsigned int W[16];
+       unsigned long long size;
+};
+
+void sha1_init(struct sha1_ctx *);
+void sha1_update(struct sha1_ctx *, const void *dataIn, unsigned long len);
+void sha1_final(unsigned char hashout[20], struct sha1_ctx *);
+
+#endif

diff --git a/options.c b/options.c
index b7262a7ff4eefb3be41413308e8a88374a27b863..ef20c24bdc2c51e9083c37e51204c93dd8716fac 100644 (file)
--- a/options.c
+++ b/options.c
@@ -1206,6 +1206,10 @@ static struct fio_option options[] = {
                            .oval = VERIFY_CRC7,
                            .help = "Use crc7 checksums for verification",
                          },
                            .oval = VERIFY_CRC7,
                            .help = "Use crc7 checksums for verification",
                          },

+                         { .ival = "sha1",
+                           .oval = VERIFY_SHA1,
+                           .help = "Use sha1 checksums for verification",
+                         },

                          { .ival = "sha256",
                            .oval = VERIFY_SHA256,
                            .help = "Use sha256 checksums for verification",
                          { .ival = "sha256",
                            .oval = VERIFY_SHA256,
                            .help = "Use sha256 checksums for verification",

diff --git a/verify.c b/verify.c
index 10bad7e2bab5f65c8b9168333a5f2567e40d19e1..193e171871928265dad467d6570800dc788cd669 100644 (file)
--- a/verify.c
+++ b/verify.c
@@ -19,6 +19,7 @@
 #include "crc/crc7.h"
 #include "crc/sha256.h"
 #include "crc/sha512.h"
 #include "crc/crc7.h"
 #include "crc/sha256.h"
 #include "crc/sha512.h"

+#include "crc/sha1.h"

 
 static void fill_random_bytes(struct thread_data *td, void *p, unsigned int len)
 {
 
 static void fill_random_bytes(struct thread_data *td, void *p, unsigned int len)
 {


@@ -149,6 +150,9 @@ static inline unsigned int __hdr_size(int verify_type)
        case VERIFY_META:
                len = sizeof(struct vhdr_meta);
                break;
        case VERIFY_META:
                len = sizeof(struct vhdr_meta);
                break;

+       case VERIFY_SHA1:
+               len = sizeof(struct vhdr_sha1);
+               break;

        default:
                log_err("fio: unknown verify header!\n");
                assert(0);
        default:
                log_err("fio: unknown verify header!\n");
                assert(0);


@@ -246,6 +250,32 @@ static int verify_io_u_sha256(struct verify_header *hdr, struct io_u *io_u,
        return 0;
 }
 
        return 0;
 }
 

+static int verify_io_u_sha1(struct verify_header *hdr, struct io_u *io_u,
+                           unsigned int header_num)
+{
+       void *p = io_u_verify_off(hdr, io_u, header_num);
+       struct vhdr_sha1 *vh = hdr_priv(hdr);
+       uint32_t sha1[5];
+       struct sha1_ctx sha1_ctx = {
+               .H = sha1,
+       };
+
+       dprint(FD_VERIFY, "sha1 verify io_u %p, len %u\n", io_u, hdr->len);
+
+       sha1_init(&sha1_ctx);
+       sha1_update(&sha1_ctx, p, hdr->len - hdr_size(hdr));
+
+       if (memcmp(vh->sha1, sha1_ctx.H, sizeof(sha1))) {
+               log_err("sha1: verify failed at %llu/%u\n",
+                               io_u->offset + header_num * hdr->len, hdr->len);
+               hexdump(vh->sha1, sizeof(vh->sha1));
+               hexdump(sha1_ctx.H, sizeof(sha1));
+               return EILSEQ;
+       }
+
+       return 0;
+}
+

 static int verify_io_u_crc7(struct verify_header *hdr, struct io_u *io_u,
                            unsigned char header_num)
 {
 static int verify_io_u_crc7(struct verify_header *hdr, struct io_u *io_u,
                            unsigned char header_num)
 {


@@ -520,6 +550,9 @@ int verify_io_u(struct thread_data *td, struct io_u *io_u)
                case VERIFY_META:
                        ret = verify_io_u_meta(hdr, td, io_u, hdr_num);
                        break;
                case VERIFY_META:
                        ret = verify_io_u_meta(hdr, td, io_u, hdr_num);
                        break;

+               case VERIFY_SHA1:
+                       ret = verify_io_u_sha1(hdr, io_u, hdr_num);
+                       break;

                default:
                        log_err("Bad verify type %u\n", hdr->verify_type);
                        ret = EINVAL;
                default:
                        log_err("Bad verify type %u\n", hdr->verify_type);
                        ret = EINVAL;


@@ -566,6 +599,17 @@ static void fill_sha256(struct verify_header *hdr, void *p, unsigned int len)
        sha256_update(&sha256_ctx, p, len);
 }
 
        sha256_update(&sha256_ctx, p, len);
 }
 

+static void fill_sha1(struct verify_header *hdr, void *p, unsigned int len)
+{
+       struct vhdr_sha1 *vh = hdr_priv(hdr);
+       struct sha1_ctx sha1_ctx = {
+               .H = vh->sha1,
+       };
+
+       sha1_init(&sha1_ctx);
+       sha1_update(&sha1_ctx, p, len);
+}
+

 static void fill_crc7(struct verify_header *hdr, void *p, unsigned int len)
 {
        struct vhdr_crc7 *vh = hdr_priv(hdr);
 static void fill_crc7(struct verify_header *hdr, void *p, unsigned int len)
 {
        struct vhdr_crc7 *vh = hdr_priv(hdr);


@@ -690,6 +734,11 @@ void populate_verify_io_u(struct thread_data *td, struct io_u *io_u)
                                                        io_u, hdr->len);
                        fill_meta(hdr, td, io_u, header_num);
                        break;
                                                        io_u, hdr->len);
                        fill_meta(hdr, td, io_u, header_num);
                        break;

+               case VERIFY_SHA1:
+                       dprint(FD_VERIFY, "fill sha1 io_u %p, len %u\n",
+                                                       io_u, hdr->len);
+                       fill_sha1(hdr, data, data_len);
+                       break;

                default:
                        log_err("fio: bad verify type: %d\n", td->o.verify);
                        assert(0);
                default:
                        log_err("fio: bad verify type: %d\n", td->o.verify);
                        assert(0);

diff --git a/verify.h b/verify.h
index 50c8e4328b44960b1056ed733589ad269fa656c7..c12bc7d0a7a1babb2c266358a05b2a73df4c6c0a 100644 (file)
--- a/verify.h
+++ b/verify.h
@@ -15,6 +15,7 @@ enum {
        VERIFY_SHA256,                  /* sha256 sum data blocks */
        VERIFY_SHA512,                  /* sha512 sum data blocks */
        VERIFY_META,                    /* block_num, timestamp etc. */
        VERIFY_SHA256,                  /* sha256 sum data blocks */
        VERIFY_SHA512,                  /* sha512 sum data blocks */
        VERIFY_META,                    /* block_num, timestamp etc. */

+       VERIFY_SHA1,                    /* sha1 sum data blocks */

        VERIFY_NULL,                    /* pretend to verify */
 };
 
        VERIFY_NULL,                    /* pretend to verify */
 };
 


@@ -38,6 +39,9 @@ struct vhdr_sha512 {
 struct vhdr_sha256 {
        uint8_t sha256[128];
 };
 struct vhdr_sha256 {
        uint8_t sha256[128];
 };

+struct vhdr_sha1 {
+       uint32_t sha1[5];
+};

 struct vhdr_crc64 {
        uint64_t crc64;
 };
 struct vhdr_crc64 {
        uint64_t crc64;
 };