crypto: powerpc - Factor out the core CRC vpmsum algorithm
Subsystems (3)
PATCH 1/4 crypto: powerpc - Factor out the core CRC vpmsum algorithm
The core nuts and bolts of the crc32c vpmsum algorithm will also work for a number of other CRC algorithms with different polynomials. Factor out the function into a new asm file.
To handle multiple users of the function, a user simply provides constants, defines the name of their CRC function, and then #includes the core algorithm file.
--
It's possible at this point to argue that the address of the constant tables should be passed in to the function, rather than doing this somewhat unconventional #include.
However, we're about to add further #ifdef's back into the core that will be provided by the encapsulaing code, and which couldn't be done as a variable without performance loss.
--- arch/powerpc/crypto/crc32-vpmsum_core.S | 726 ++++++++++++++++++++++++++++++++ arch/powerpc/crypto/crc32c-vpmsum_asm.S | 714 +------------------------------ 2 files changed, 729 insertions(+), 711 deletions(-) create mode 100644 arch/powerpc/crypto/crc32-vpmsum_core.S
arch/powerpc/crypto/crc32-vpmsum_core.S new file +726 -0
@@ -0,0 +1,726 @@ +/* + * Core of the accelerated CRC algorithm. + * In your file, define the constants and CRC_FUNCTION_NAME + * Then include this file. + * + * Calculate the checksum of data that is 16 byte aligned and a multiple of + * 16 bytes. + * + * The first step is to reduce it to 1024 bits. We do this in 8 parallel + * chunks in order to mask the latency of the vpmsum instructions. If we + * have more than 32 kB of data to checksum we repeat this step multiple + * times, passing in the previous 1024 bits. + * + * The next step is to reduce the 1024 bits to 64 bits. This step adds + * 32 bits of 0s to the end - this matches what a CRC does. We just + * calculate constants that land the data in this 32 bits. + * + * We then use fixed point Barrett reduction to compute a mod n over GF(2) + * for n = CRC using POWER8 instructions. We use x = 32. + * + * http://en.wikipedia.org/wiki/Barrett_reduction + * + * Copyright (C) 2015 Anton Blanchard <[email protected]>, IBM + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version + * 2 of the License, or (at your option) any later version. +*/ + +#include <asm/ppc_asm.h> +#include <asm/ppc-opcode.h> + +#define MAX_SIZE 32768 + + .text + +#if defined(__BIG_ENDIAN__) +#define BYTESWAP_DATA +#else +#undef BYTESWAP_DATA +#endif + +#define off16 r25 +#define off32 r26 +#define off48 r27 +#define off64 r28 +#define off80 r29 +#define off96 r30 +#define off112 r31 + +#define const1 v24 +#define const2 v25 + +#define byteswap v26 +#define mask_32bit v27 +#define mask_64bit v28 +#define zeroes v29 + +#ifdef BYTESWAP_DATA +#define VPERM(A, B, C, D) vperm A, B, C, D +#else +#define VPERM(A, B, C, D) +#endif + +/* unsigned int CRC_FUNCTION_NAME(unsigned int crc, void *p, unsigned long len) */ +FUNC_START(CRC_FUNCTION_NAME) + std r31,-8(r1) + std r30,-16(r1) + std r29,-24(r1) + std r28,-32(r1) + std r27,-40(r1) + std r26,-48(r1) + std r25,-56(r1) + + li off16,16 + li off32,32 + li off48,48 + li off64,64 + li off80,80 + li off96,96 + li off112,112 + li r0,0 + + /* Enough room for saving 10 non volatile VMX registers */ + subi r6,r1,56+10*16 + subi r7,r1,56+2*16 + + stvx v20,0,r6 + stvx v21,off16,r6 + stvx v22,off32,r6 + stvx v23,off48,r6 + stvx v24,off64,r6 + stvx v25,off80,r6 + stvx v26,off96,r6 + stvx v27,off112,r6 + stvx v28,0,r7 + stvx v29,off16,r7 + + mr r10,r3 + + vxor zeroes,zeroes,zeroes + vspltisw v0,-1 + + vsldoi mask_32bit,zeroes,v0,4 + vsldoi mask_64bit,zeroes,v0,8 + + /* Get the initial value into v8 */ + vxor v8,v8,v8 + MTVRD(v8, R3) + vsldoi v8,zeroes,v8,8 /* shift into bottom 32 bits */ + +#ifdef BYTESWAP_DATA + addis r3,r2,.byteswap_constant@toc@ha + addi r3,r3,.byteswap_constant@toc@l + + lvx byteswap,0,r3 + addi r3,r3,16 +#endif + + cmpdi r5,256 + blt .Lshort + + rldicr r6,r5,0,56 + + /* Checksum in blocks of MAX_SIZE */ +1: lis r7,MAX_SIZE@h + ori r7,r7,MAX_SIZE@l + mr r9,r7 + cmpd r6,r7 + bgt 2f + mr r7,r6 +2: subf r6,r7,r6 + + /* our main loop does 128 bytes at a time */ + srdi r7,r7,7 + + /* + * Work out the offset into the constants table to start at. Each + * constant is 16 bytes, and it is used against 128 bytes of input + * data - 128 / 16 = 8 + */ + sldi r8,r7,4 + srdi r9,r9,3 + subf r8,r8,r9 + + /* We reduce our final 128 bytes in a separate step */ + addi r7,r7,-1 + mtctr r7 + + addis r3,r2,.constants@toc@ha + addi r3,r3,.constants@toc@l + + /* Find the start of our constants */ + add r3,r3,r8 + + /* zero v0-v7 which will contain our checksums */ + vxor v0,v0,v0 + vxor v1,v1,v1 + vxor v2,v2,v2 + vxor v3,v3,v3 + vxor v4,v4,v4 + vxor v5,v5,v5 + vxor v6,v6,v6 + vxor v7,v7,v7 + + lvx const1,0,r3 + + /* + * If we are looping back to consume more data we use the values + * already in v16-v23. + */ + cmpdi r0,1 + beq 2f + + /* First warm up pass */ + lvx v16,0,r4 + lvx v17,off16,r4 + VPERM(v16,v16,v16,byteswap) + VPERM(v17,v17,v17,byteswap) + lvx v18,off32,r4 + lvx v19,off48,r4 + VPERM(v18,v18,v18,byteswap) + VPERM(v19,v19,v19,byteswap) + lvx v20,off64,r4 + lvx v21,off80,r4 + VPERM(v20,v20,v20,byteswap) + VPERM(v21,v21,v21,byteswap) + lvx v22,off96,r4 + lvx v23,off112,r4 + VPERM(v22,v22,v22,byteswap) + VPERM(v23,v23,v23,byteswap) + addi r4,r4,8*16 + + /* xor in initial value */ + vxor v16,v16,v8 + +2: bdz .Lfirst_warm_up_done + + addi r3,r3,16 + lvx const2,0,r3 + + /* Second warm up pass */ + VPMSUMD(v8,v16,const1) + lvx v16,0,r4 + VPERM(v16,v16,v16,byteswap) + ori r2,r2,0 + + VPMSUMD(v9,v17,const1) + lvx v17,off16,r4 + VPERM(v17,v17,v17,byteswap) + ori r2,r2,0 + + VPMSUMD(v10,v18,const1) + lvx v18,off32,r4 + VPERM(v18,v18,v18,byteswap) + ori r2,r2,0 + + VPMSUMD(v11,v19,const1) + lvx v19,off48,r4 + VPERM(v19,v19,v19,byteswap) + ori r2,r2,0 + + VPMSUMD(v12,v20,const1) + lvx v20,off64,r4 + VPERM(v20,v20,v20,byteswap) + ori r2,r2,0 + + VPMSUMD(v13,v21,const1) + lvx v21,off80,r4 + VPERM(v21,v21,v21,byteswap) + ori r2,r2,0 + + VPMSUMD(v14,v22,const1) + lvx v22,off96,r4 + VPERM(v22,v22,v22,byteswap) + ori r2,r2,0 + + VPMSUMD(v15,v23,const1) + lvx v23,off112,r4 + VPERM(v23,v23,v23,byteswap) + + addi r4,r4,8*16 + + bdz .Lfirst_cool_down + + /* + * main loop. We modulo schedule it such that it takes three iterations + * to complete - first iteration load, second iteration vpmsum, third + * iteration xor. + */ + .balign 16 +4: lvx const1,0,r3 + addi r3,r3,16 + ori r2,r2,0 + + vxor v0,v0,v8 + VPMSUMD(v8,v16,const2) + lvx v16,0,r4 + VPERM(v16,v16,v16,byteswap) + ori r2,r2,0 + + vxor v1,v1,v9 + VPMSUMD(v9,v17,const2) + lvx v17,off16,r4 + VPERM(v17,v17,v17,byteswap) + ori r2,r2,0 + + vxor v2,v2,v10 + VPMSUMD(v10,v18,const2) + lvx v18,off32,r4 + VPERM(v18,v18,v18,byteswap) + ori r2,r2,0 + + vxor v3,v3,v11 + VPMSUMD(v11,v19,const2) + lvx v19,off48,r4 + VPERM(v19,v19,v19,byteswap) + lvx const2,0,r3 + ori r2,r2,0 + + vxor v4,v4,v12 + VPMSUMD(v12,v20,const1) + lvx v20,off64,r4 + VPERM(v20,v20,v20,byteswap) + ori r2,r2,0 + + vxor v5,v5,v13 + VPMSUMD(v13,v21,const1) + lvx v21,off80,r4 + VPERM(v21,v21,v21,byteswap) + ori r2,r2,0 + + vxor v6,v6,v14 + VPMSUMD(v14,v22,const1) + lvx v22,off96,r4 + VPERM(v22,v22,v22,byteswap) + ori r2,r2,0 + + vxor v7,v7,v15 + VPMSUMD(v15,v23,const1) + lvx v23,off112,r4 + VPERM(v23,v23,v23,byteswap) + + addi r4,r4,8*16 + + bdnz 4b + +.Lfirst_cool_down: + /* First cool down pass */ + lvx const1,0,r3 + addi r3,r3,16 + + vxor v0,v0,v8 + VPMSUMD(v8,v16,const1) + ori r2,r2,0 + + vxor v1,v1,v9 + VPMSUMD(v9,v17,const1) + ori r2,r2,0 + + vxor v2,v2,v10 + VPMSUMD(v10,v18,const1) + ori r2,r2,0 + + vxor v3,v3,v11 + VPMSUMD(v11,v19,const1) + ori r2,r2,0 + + vxor v4,v4,v12 + VPMSUMD(v12,v20,const1) + ori r2,r2,0 + + vxor v5,v5,v13 + VPMSUMD(v13,v21,const1) + ori r2,r2,0 + + vxor v6,v6,v14 + VPMSUMD(v14,v22,const1) + ori r2,r2,0 + + vxor v7,v7,v15 + VPMSUMD(v15,v23,const1) + ori r2,r2,0 + +.Lsecond_cool_down: + /* Second cool down pass */ + vxor v0,v0,v8 + vxor v1,v1,v9 + vxor v2,v2,v10 + vxor v3,v3,v11 + vxor v4,v4,v12 + vxor v5,v5,v13 + vxor v6,v6,v14 + vxor v7,v7,v15 + + /* + * vpmsumd produces a 96 bit result in the least significant bits + * of the register. Since we are bit reflected we have to shift it + * left 32 bits so it occupies the least significant bits in the + * bit reflected domain. + */ + vsldoi v0,v0,zeroes,4 + vsldoi v1,v1,zeroes,4 + vsldoi v2,v2,zeroes,4 + vsldoi v3,v3,zeroes,4 + vsldoi v4,v4,zeroes,4 + vsldoi v5,v5,zeroes,4 + vsldoi v6,v6,zeroes,4 + vsldoi v7,v7,zeroes,4 + + /* xor with last 1024 bits */ + lvx v8,0,r4 + lvx v9,off16,r4 + VPERM(v8,v8,v8,byteswap) + VPERM(v9,v9,v9,byteswap) + lvx v10,off32,r4 + lvx v11,off48,r4 + VPERM(v10,v10,v10,byteswap) + VPERM(v11,v11,v11,byteswap) + lvx v12,off64,r4 + lvx v13,off80,r4 + VPERM(v12,v12,v12,byteswap) + VPERM(v13,v13,v13,byteswap) + lvx v14,off96,r4 + lvx v15,off112,r4 + VPERM(v14,v14,v14,byteswap) + VPERM(v15,v15,v15,byteswap) + + addi r4,r4,8*16 + + vxor v16,v0,v8 + vxor v17,v1,v9 + vxor v18,v2,v10 + vxor v19,v3,v11 + vxor v20,v4,v12 + vxor v21,v5,v13 + vxor v22,v6,v14 + vxor v23,v7,v15 + + li r0,1 + cmpdi r6,0 + addi r6,r6,128 + bne 1b + + /* Work out how many bytes we have left */ + andi. r5,r5,127 + + /* Calculate where in the constant table we need to start */ + subfic r6,r5,128 + add r3,r3,r6 + + /* How many 16 byte chunks are in the tail */ + srdi r7,r5,4 + mtctr r7 + + /* + * Reduce the previously calculated 1024 bits to 64 bits, shifting + * 32 bits to include the trailing 32 bits of zeros + */ + lvx v0,0,r3 + lvx v1,off16,r3 + lvx v2,off32,r3 + lvx v3,off48,r3 + lvx v4,off64,r3 + lvx v5,off80,r3 + lvx v6,off96,r3 + lvx v7,off112,r3 + addi r3,r3,8*16 + + VPMSUMW(v0,v16,v0) + VPMSUMW(v1,v17,v1) + VPMSUMW(v2,v18,v2) + VPMSUMW(v3,v19,v3) + VPMSUMW(v4,v20,v4) + VPMSUMW(v5,v21,v5) + VPMSUMW(v6,v22,v6) + VPMSUMW(v7,v23,v7) + + /* Now reduce the tail (0 - 112 bytes) */ + cmpdi r7,0 + beq 1f + + lvx v16,0,r4 + lvx v17,0,r3 + VPERM(v16,v16,v16,byteswap) + VPMSUMW(v16,v16,v17) + vxor v0,v0,v16 + bdz 1f + + lvx v16,off16,r4 + lvx v17,off16,r3 + VPERM(v16,v16,v16,byteswap) + VPMSUMW(v16,v16,v17) + vxor v0,v0,v16 + bdz 1f + + lvx v16,off32,r4 + lvx v17,off32,r3 + VPERM(v16,v16,v16,byteswap) + VPMSUMW(v16,v16,v17) + vxor v0,v0,v16 + bdz 1f + + lvx v16,off48,r4 + lvx v17,off48,r3 + VPERM(v16,v16,v16,byteswap) + VPMSUMW(v16,v16,v17) + vxor v0,v0,v16 + bdz 1f + + lvx v16,off64,r4 + lvx v17,off64,r3 + VPERM(v16,v16,v16,byteswap) + VPMSUMW(v16,v16,v17) + vxor v0,v0,v16 + bdz 1f + + lvx v16,off80,r4 + lvx v17,off80,r3 + VPERM(v16,v16,v16,byteswap) + VPMSUMW(v16,v16,v17) + vxor v0,v0,v16 + bdz 1f + + lvx v16,off96,r4 + lvx v17,off96,r3 + VPERM(v16,v16,v16,byteswap) + VPMSUMW(v16,v16,v17) + vxor v0,v0,v16 + + /* Now xor all the parallel chunks together */ +1: vxor v0,v0,v1 + vxor v2,v2,v3 + vxor v4,v4,v5 + vxor v6,v6,v7 + + vxor v0,v0,v2 + vxor v4,v4,v6 + + vxor v0,v0,v4 + +.Lbarrett_reduction: + /* Barrett constants */ + addis r3,r2,.barrett_constants@toc@ha + addi r3,r3,.barrett_constants@toc@l + + lvx const1,0,r3 + lvx const2,off16,r3 + + vsldoi v1,v0,v0,8 + vxor v0,v0,v1 /* xor two 64 bit results together */ + + /* shift left one bit */ + vspltisb v1,1 + vsl v0,v0,v1 + + vand v0,v0,mask_64bit + + /* + * The reflected version of Barrett reduction. Instead of bit + * reflecting our data (which is expensive to do), we bit reflect our + * constants and our algorithm, which means the intermediate data in + * our vector registers goes from 0-63 instead of 63-0. We can reflect + * the algorithm because we don't carry in mod 2 arithmetic. + */ + vand v1,v0,mask_32bit /* bottom 32 bits of a */ + VPMSUMD(v1,v1,const1) /* ma */ + vand v1,v1,mask_32bit /* bottom 32bits of ma */ + VPMSUMD(v1,v1,const2) /* qn */ + vxor v0,v0,v1 /* a - qn, subtraction is xor in GF(2) */ + + /* + * Since we are bit reflected, the result (ie the low 32 bits) is in + * the high 32 bits. We just need to shift it left 4 bytes + * V0 [ 0 1 X 3 ] + * V0 [ 0 X 2 3 ] + */ + vsldoi v0,v0,zeroes,4 /* shift result into top 64 bits of */ + + /* Get it into r3 */ + MFVRD(R3, v0) + +.Lout: + subi r6,r1,56+10*16 + subi r7,r1,56+2*16 + + lvx v20,0,r6 + lvx v21,off16,r6 + lvx v22,off32,r6 + lvx v23,off48,r6 + lvx v24,off64,r6 + lvx v25,off80,r6 + lvx v26,off96,r6 + lvx v27,off112,r6 + lvx v28,0,r7 + lvx v29,off16,r7 + + ld r31,-8(r1) + ld r30,-16(r1) + ld r29,-24(r1) + ld r28,-32(r1) + ld r27,-40(r1) + ld r26,-48(r1) + ld r25,-56(r1) + + blr + +.Lfirst_warm_up_done: + lvx const1,0,r3 + addi r3,r3,16 + + VPMSUMD(v8,v16,const1) + VPMSUMD(v9,v17,const1) + VPMSUMD(v10,v18,const1) + VPMSUMD(v11,v19,const1) + VPMSUMD(v12,v20,const1) + VPMSUMD(v13,v21,const1) + VPMSUMD(v14,v22,const1) + VPMSUMD(v15,v23,const1) + + b .Lsecond_cool_down + +.Lshort: + cmpdi r5,0 + beq .Lzero + + addis r3,r2,.short_constants@toc@ha + addi r3,r3,.short_constants@toc@l + + /* Calculate where in the constant table we need to start */ + subfic r6,r5,256 + add r3,r3,r6 + + /* How many 16 byte chunks? */ + srdi r7,r5,4 + mtctr r7 + + vxor v19,v19,v19 + vxor v20,v20,v20 + + lvx v0,0,r4 + lvx v16,0,r3 + VPERM(v0,v0,v16,byteswap) + vxor v0,v0,v8 /* xor in initial value */ + VPMSUMW(v0,v0,v16) + bdz .Lv0 + + lvx v1,off16,r4 + lvx v17,off16,r3 + VPERM(v1,v1,v17,byteswap) + VPMSUMW(v1,v1,v17) + bdz .Lv1 + + lvx v2,off32,r4 + lvx v16,off32,r3 + VPERM(v2,v2,v16,byteswap) + VPMSUMW(v2,v2,v16) + bdz .Lv2 + + lvx v3,off48,r4 + lvx v17,off48,r3 + VPERM(v3,v3,v17,byteswap) + VPMSUMW(v3,v3,v17) + bdz .Lv3 + + lvx v4,off64,r4 + lvx v16,off64,r3 + VPERM(v4,v4,v16,byteswap) + VPMSUMW(v4,v4,v16) + bdz .Lv4 + + lvx v5,off80,r4 + lvx v17,off80,r3 + VPERM(v5,v5,v17,byteswap) + VPMSUMW(v5,v5,v17) + bdz .Lv5 + + lvx v6,off96,r4 + lvx v16,off96,r3 + VPERM(v6,v6,v16,byteswap) + VPMSUMW(v6,v6,v16) + bdz .Lv6 + + lvx v7,off112,r4 + lvx v17,off112,r3 + VPERM(v7,v7,v17,byteswap) + VPMSUMW(v7,v7,v17) + bdz .Lv7 + + addi r3,r3,128 + addi r4,r4,128 + + lvx v8,0,r4 + lvx v16,0,r3 + VPERM(v8,v8,v16,byteswap) + VPMSUMW(v8,v8,v16) + bdz .Lv8 + + lvx v9,off16,r4 + lvx v17,off16,r3 + VPERM(v9,v9,v17,byteswap) + VPMSUMW(v9,v9,v17) + bdz .Lv9 + + lvx v10,off32,r4 + lvx v16,off32,r3 + VPERM(v10,v10,v16,byteswap) + VPMSUMW(v10,v10,v16) + bdz .Lv10 + + lvx v11,off48,r4 + lvx v17,off48,r3 + VPERM(v11,v11,v17,byteswap) + VPMSUMW(v11,v11,v17) + bdz .Lv11 + + lvx v12,off64,r4 + lvx v16,off64,r3 + VPERM(v12,v12,v16,byteswap) + VPMSUMW(v12,v12,v16) + bdz .Lv12 + + lvx v13,off80,r4 + lvx v17,off80,r3 + VPERM(v13,v13,v17,byteswap) + VPMSUMW(v13,v13,v17) + bdz .Lv13 + + lvx v14,off96,r4 + lvx v16,off96,r3 + VPERM(v14,v14,v16,byteswap) + VPMSUMW(v14,v14,v16) + bdz .Lv14 + + lvx v15,off112,r4 + lvx v17,off112,r3 + VPERM(v15,v15,v17,byteswap) + VPMSUMW(v15,v15,v17) + +.Lv15: vxor v19,v19,v15 +.Lv14: vxor v20,v20,v14 +.Lv13: vxor v19,v19,v13 +.Lv12: vxor v20,v20,v12 +.Lv11: vxor v19,v19,v11 +.Lv10: vxor v20,v20,v10 +.Lv9: vxor v19,v19,v9 +.Lv8: vxor v20,v20,v8 +.Lv7: vxor v19,v19,v7 +.Lv6: vxor v20,v20,v6 +.Lv5: vxor v19,v19,v5 +.Lv4: vxor v20,v20,v4 +.Lv3: vxor v19,v19,v3 +.Lv2: vxor v20,v20,v2 +.Lv1: vxor v19,v19,v1 +.Lv0: vxor v20,v20,v0 + + vxor v0,v19,v20 + + b .Lbarrett_reduction + +.Lzero: + mr r3,r10 + b .Lout + +FUNC_END(CRC_FUNCTION_NAME)
arch/powerpc/crypto/crc32c-vpmsum_asm.S +3 -711
733 lines not on this page · raw message
Signature · 1 line
2.9.3
PATCH 2/4 crypto: powerpc - Re-enable non-REFLECTed CRCs
When CRC32c was included in the kernel, Anton ripped out the #ifdefs around reflected polynomials, because CRC32c is always reflected. However, not all CRCs use reflection so we'd like to make it optional.
Restore the REFLECT parts from Anton's original CRC32 implementation (https://github.com/antonblanchard/crc32-vpmsum)
That implementation is available under GPLv2+, so we're OK from a licensing point of view:
https://github.com/antonblanchard/crc32-vpmsum/blob/master/LICENSE.TXT
As CRC32c requires REFLECT, add that #define.
---
I compared the disassembly of the CRC32c module on LE before and after the change, and verified that they were the same.
I verified that the crypto self-tests still pass on LE and BE, and my tests in patch 4 still pass as well.
--- arch/powerpc/crypto/crc32-vpmsum_core.S | 31 ++++++++++++++++++++++++++++++- arch/powerpc/crypto/crc32c-vpmsum_asm.S | 1 + 2 files changed, 31 insertions(+), 1 deletion(-)
arch/powerpc/crypto/crc32-vpmsum_core.S +30 -1
@@ -35,7 +35,9 @@ .text -#if defined(__BIG_ENDIAN__) +#if defined(__BIG_ENDIAN__) && defined(REFLECT) +#define BYTESWAP_DATA +#elif defined(__LITTLE_ENDIAN__) && !defined(REFLECT) #define BYTESWAP_DATA #else #undef BYTESWAP_DATA
@@ -108,7 +110,11 @@ FUNC_START(CRC_FUNCTION_NAME) /* Get the initial value into v8 */ vxor v8,v8,v8 MTVRD(v8, R3) +#ifdef REFLECT vsldoi v8,zeroes,v8,8 /* shift into bottom 32 bits */ +#else + vsldoi v8,v8,zeroes,4 /* shift into top 32 bits */ +#endif #ifdef BYTESWAP_DATA addis r3,r2,.byteswap_constant@toc@ha
@@ -354,6 +360,7 @@ FUNC_START(CRC_FUNCTION_NAME) vxor v6,v6,v14 vxor v7,v7,v15 +#ifdef REFLECT /* * vpmsumd produces a 96 bit result in the least significant bits * of the register. Since we are bit reflected we have to shift it
@@ -368,6 +375,7 @@ FUNC_START(CRC_FUNCTION_NAME) vsldoi v5,v5,zeroes,4 vsldoi v6,v6,zeroes,4 vsldoi v7,v7,zeroes,4 +#endif /* xor with last 1024 bits */ lvx v8,0,r4
@@ -511,13 +519,33 @@ FUNC_START(CRC_FUNCTION_NAME) vsldoi v1,v0,v0,8 vxor v0,v0,v1 /* xor two 64 bit results together */ +#ifdef REFLECT /* shift left one bit */ vspltisb v1,1 vsl v0,v0,v1 +#endif vand v0,v0,mask_64bit +#ifndef REFLECT + /* + * Now for the Barrett reduction algorithm. The idea is to calculate q, + * the multiple of our polynomial that we need to subtract. By + * doing the computation 2x bits higher (ie 64 bits) and shifting the + * result back down 2x bits, we round down to the nearest multiple. + */ + VPMSUMD(v1,v0,const1) /* ma */ + vsldoi v1,zeroes,v1,8 /* q = floor(ma/(2^64)) */ + VPMSUMD(v1,v1,const2) /* qn */ + vxor v0,v0,v1 /* a - qn, subtraction is xor in GF(2) */ /* + * Get the result into r3. We need to shift it left 8 bytes: + * V0 [ 0 1 2 X ] + * V0 [ 0 X 2 3 ] + */ + vsldoi v0,v0,zeroes,8 /* shift result into top 64 bits */ +#else + /* * The reflected version of Barrett reduction. Instead of bit * reflecting our data (which is expensive to do), we bit reflect our * constants and our algorithm, which means the intermediate data in
@@ -537,6 +565,7 @@ FUNC_START(CRC_FUNCTION_NAME) * V0 [ 0 X 2 3 ] */ vsldoi v0,v0,zeroes,4 /* shift result into top 64 bits of */ +#endif /* Get it into r3 */ MFVRD(R3, v0)
arch/powerpc/crypto/crc32c-vpmsum_asm.S +1 -0
@@ -842,4 +842,5 @@ .octa 0x00000000000000000000000105ec76f1 #define CRC_FUNCTION_NAME __crc32c_vpmsum +#define REFLECT #include "crc32-vpmsum_core.S"
Signature · 1 line
2.9.3
Michael Ellerman
reviewerRe: [PATCH 2/4] crypto: powerpc - Re-enable non-REFLECTed CRCs
Quoted 11 lines · Daniel Axtens
When CRC32c was included in the kernel, Anton ripped out the #ifdefs around reflected polynomials, because CRC32c is always reflected. However, not all CRCs use reflection so we'd like to make it optional.
Restore the REFLECT parts from Anton's original CRC32 implementation (https://github.com/antonblanchard/crc32-vpmsum)
That implementation is available under GPLv2+, so we're OK from a licensing point of view:
https://github.com/antonblanchard/crc32-vpmsum/blob/master/LICENSE.TXT
It's also written by Anton and copyright IBM, so you (we (IBM)) could always just relicense it anyway.
So doubly OK IMO.
cheers
PATCH 3/4 crypto: powerpc - Add CRC-T10DIF acceleration
In reply to Daniel AxtensT10DIF is a CRC16 used heavily in NVMe.
It turns out we can accelerate it with a CRC32 library and a few little tricks.
Provide the accelerator based the refactored CRC32 code.
Cc: Anton Blanchard <[email protected]>
Thanks-to: Hong Bo Peng <[email protected]>
--- arch/powerpc/crypto/Makefile | 2 + arch/powerpc/crypto/crct10dif-vpmsum_asm.S | 850 ++++++++++++++++++++++++++++ arch/powerpc/crypto/crct10dif-vpmsum_glue.c | 125 ++++ crypto/Kconfig | 9 + 4 files changed, 986 insertions(+) create mode 100644 arch/powerpc/crypto/crct10dif-vpmsum_asm.S create mode 100644 arch/powerpc/crypto/crct10dif-vpmsum_glue.c
arch/powerpc/crypto/Makefile +2 -0
@@ -10,6 +10,7 @@ obj-$(CONFIG_CRYPTO_SHA1_PPC) += sha1-powerpc.o obj-$(CONFIG_CRYPTO_SHA1_PPC_SPE) += sha1-ppc-spe.o obj-$(CONFIG_CRYPTO_SHA256_PPC_SPE) += sha256-ppc-spe.o obj-$(CONFIG_CRYPTO_CRC32C_VPMSUM) += crc32c-vpmsum.o +obj-$(CONFIG_CRYPTO_CRCT10DIF_VPMSUM) += crct10dif-vpmsum.o aes-ppc-spe-y := aes-spe-core.o aes-spe-keys.o aes-tab-4k.o aes-spe-modes.o aes-spe-glue.o md5-ppc-y := md5-asm.o md5-glue.o
@@ -17,3 +18,4 @@ sha1-powerpc-y := sha1-powerpc-asm.o sha1.o sha1-ppc-spe-y := sha1-spe-asm.o sha1-spe-glue.o sha256-ppc-spe-y := sha256-spe-asm.o sha256-spe-glue.o crc32c-vpmsum-y := crc32c-vpmsum_asm.o crc32c-vpmsum_glue.o +crct10dif-vpmsum-y := crct10dif-vpmsum_asm.o crct10dif-vpmsum_glue.o
arch/powerpc/crypto/crct10dif-vpmsum_asm.S new file +850 -0
850 lines not on this page · raw message
arch/powerpc/crypto/crct10dif-vpmsum_glue.c new file +125 -0
125 lines not on this page · raw message
crypto/Kconfig +9 -0
@@ -513,6 +513,15 @@ config CRYPTO_CRCT10DIF_PCLMUL 'crct10dif-plcmul' module, which is faster when computing the crct10dif checksum as compared with the generic table implementation. +config CRYPTO_CRCT10DIF_VPMSUM + tristate "CRC32T10DIF powerpc64 hardware acceleration" + depends on PPC64 && ALTIVEC && CRC_T10DIF + select CRYPTO_HASH + help + CRC10T10DIF algorithm implemented using vector polynomial + multiply-sum (vpmsum) instructions, introduced in POWER8. Enable on + POWER8 and newer processors for improved performance. + config CRYPTO_GHASH tristate "GHASH digest algorithm" select CRYPTO_GF128MUL
Signature · 1 line
2.9.3
PATCH 4/4 crypto: powerpc - Stress test for vpmsum implementations
In reply to Daniel Axtensvpmsum implementations often don't kick in for short test vectors. This is a simple test module that does a configurable number of random tests, each up to 64kB and each with random offsets.
Both CRC-T10DIF and CRC32C are tested.
--
Not super fussy about the inclusion or otherwise of this - it was very useful for debugging my code, and more tests are good :)
Also, I originally found the bug in Anton's CRC32c using this.
Tests pass on both BE 64 bit and LE 64 bit.
--- arch/powerpc/crypto/Makefile | 1 + arch/powerpc/crypto/crc-vpmsum_test.c | 137 ++++++++++++++++++++++++++++++++++ crypto/Kconfig | 8 ++ 3 files changed, 146 insertions(+) create mode 100644 arch/powerpc/crypto/crc-vpmsum_test.c
arch/powerpc/crypto/Makefile +1 -0
@@ -11,6 +11,7 @@ obj-$(CONFIG_CRYPTO_SHA1_PPC_SPE) += sha1-ppc-spe.o obj-$(CONFIG_CRYPTO_SHA256_PPC_SPE) += sha256-ppc-spe.o obj-$(CONFIG_CRYPTO_CRC32C_VPMSUM) += crc32c-vpmsum.o obj-$(CONFIG_CRYPTO_CRCT10DIF_VPMSUM) += crct10dif-vpmsum.o +obj-$(CONFIG_CRYPTO_VPMSUM_TESTER) += crc-vpmsum_test.o aes-ppc-spe-y := aes-spe-core.o aes-spe-keys.o aes-tab-4k.o aes-spe-modes.o aes-spe-glue.o md5-ppc-y := md5-asm.o md5-glue.o
arch/powerpc/crypto/crc-vpmsum_test.c new file +137 -0
137 lines not on this page · raw message
crypto/Kconfig +8 -0
@@ -522,6 +522,14 @@ config CRYPTO_CRCT10DIF_VPMSUM multiply-sum (vpmsum) instructions, introduced in POWER8. Enable on POWER8 and newer processors for improved performance. +config CRYPTO_VPMSUM_TESTER + tristate "Powerpc64 vpmsum hardware acceleration tester" + depends on CRYPTO_CRCT10DIF_VPMSUM && CRYPTO_CRC32C_VPMSUM + help + Stress test for CRC32c and CRC-T10DIF algorithms implemented with + POWER8 vpmsum instructions. + Unless you are testing these algorithms, you don't need this. + config CRYPTO_GHASH tristate "GHASH digest algorithm" select CRYPTO_GF128MUL
Signature · 1 line
2.9.3
From: Linuxppc-dev Daniel Axtens
Quoted 8 lines
Sent: 15 March 2017 12:38
The core nuts and bolts of the crc32c vpmsum algorithm will also work for a number of other CRC algorithms with different polynomials. Factor out the function into a new asm file.To handle multiple users of the function, a user simply provides constants, defines the name of their CRC function, and then #includes the core algorithm file.
...
While not part of this change, the unrolled loops look as though they just destroy the cpu cache.
I'd like be convinced that anything does CRC over long enough buffers to make it a gain at all.
With modern (not that modern now) superscalar cpus you can often get the loop instructions 'for free'.
Sometimes pipelining the loop is needed to get full throughput. Unlike the IP checksum, you don't even have to 'loop carry' the cpu carry flag.
David
Hi David,
Quoted 10 lines
While not part of this change, the unrolled loops look as though they just destroy the cpu cache.
I'd like be convinced that anything does CRC over long enough buffers to make it a gain at all.With modern (not that modern now) superscalar cpus you can often get the loop instructions 'for free'.
Sometimes pipelining the loop is needed to get full throughput. Unlike the IP checksum, you don't even have to 'loop carry' the cpu carry flag.
Internal testing on a NVMe device with T10DIF enabled on 4k blocks shows a 20x - 30x improvement. Without these patches, crc_t10dif_generic uses over 60% of CPU time - with these patches CRC drops to single digits.
I should probably have lead with that, sorry.
FWIW, the original patch showed a 3.7x gain on btrfs as well - 6dd7a82cc54e ("crypto: powerpc - Add POWER8 optimised crc32c")
When Anton wrote the original code he had access to IBM's internal tooling for looking at how instructions flow through the various stages of the CPU, so I trust it's pretty much optimal from that point of view.
Regards,
Daniel
From: Daniel Axtens
Quoted 14 lines
Sent: 15 March 2017 22:30
Hi David,Quoted 10 lines
While not part of this change, the unrolled loops look as though they just destroy the cpu cache.
I'd like be convinced that anything does CRC over long enough buffers to make it a gain at all.With modern (not that modern now) superscalar cpus you can often get the loop instructions 'for free'.
Sometimes pipelining the loop is needed to get full throughput. Unlike the IP checksum, you don't even have to 'loop carry' the cpu carry flag.
Quoted 6 lines
Internal testing on a NVMe device with T10DIF enabled on 4k blocks shows a 20x - 30x improvement. Without these patches,
crc_t10dif_genericuses over 60% of CPU time - with these patches CRC drops to single digits.I should probably have lead with that, sorry.
I'm not doubting that using the cpu instruction for crcs gives a massive performance boost.
Just that the heavily unrolled loop is unlikely to help overall. Some 'cold cache' tests on shorter buffers might be illuminating.
Quoted 6 lines
FWIW, the original patch showed a 3.7x gain on btrfs as well -
6dd7a82cc54e("crypto: powerpc - Add POWER8 optimised crc32c")When Anton wrote the original code he had access to IBM's internal tooling for looking at how instructions flow through the various stages of the CPU, so I trust it's pretty much optimal from that point of view.
Doesn't mean he used it :-)
David
Hi David,
Quoted 4 lines
While not part of this change, the unrolled loops look as though they just destroy the cpu cache.
I'd like be convinced that anything does CRC over long enough buffers to make it a gain at all.
btrfs data checksumming is one area.
Quoted 2 lines
With modern (not that modern now) superscalar cpus you can often get the loop instructions 'for free'.
A branch on POWER8 is a three cycle redirect. The vpmsum instructions are 6 cycles.
Quoted 3 lines
Sometimes pipelining the loop is needed to get full throughput. Unlike the IP checksum, you don't even have to 'loop carry' the cpu carry flag.
It went through quite a lot of simulation to reach peak performance. The loop is quite delicate, we have to pace it just right to avoid some pipeline reject conditions.
Note also that we already modulo schedule the loop across three iterations, required to hide the latency of the vpmsum instructions.
Anton
Michael Ellerman
reviewerQuoted 17 lines · Daniel Axtens
The core nuts and bolts of the crc32c vpmsum algorithm will also work for a number of other CRC algorithms with different polynomials. Factor out the function into a new asm file.
To handle multiple users of the function, a user simply provides constants, defines the name of their CRC function, and then #includes the core algorithm file.
Cc Anton Blanchard <[email protected]>Signed-off-by Daniel Axtens <[email protected]>--
It's possible at this point to argue that the address of the constant tables should be passed in to the function, rather than doing this somewhat unconventional #include.
Quoted 8 lines
However, we're about to add further #ifdef's back into the core that will be provided by the encapsulaing code, and which couldn't be done as a variable without performance loss.
--- arch/powerpc/crypto/crc32-vpmsum_core.S | 726 ++++++++++++++++++++++++++++++++ arch/powerpc/crypto/crc32c-vpmsum_asm.S | 714 +------------------------------ 2 files changed, 729 insertions(+), 711 deletions(-) create mode 100644 arch/powerpc/crypto/crc32-vpmsum_core.S
So although this sits in arch/powerpc, it's heavy on the crypto which is not my area of expertise (to say the least!), so I think it should probably go via Herbert and the crypto tree?
cheers
Quoted 3 lines
So although this sits in
arch/powerpc, it's heavy on the crypto which is not my area of expertise (to say the least!), so I think it should probably go via Herbert and the crypto tree?
That was my thought as well. Sorry - probably should have put that in the comments somewhere.
Regards,
Daniel
Herbert Xu
maintainerQuoted 10 lines · Daniel Axtens
The core nuts and bolts of the crc32c vpmsum algorithm will also work for a number of other CRC algorithms with different polynomials. Factor out the function into a new asm file.
To handle multiple users of the function, a user simply provides constants, defines the name of their CRC function, and then #includes the core algorithm file.
Cc Anton Blanchard <[email protected]>Signed-off-by Daniel Axtens <[email protected]>
All patches applied. Thanks.
Signature · 3 lines
Email: Herbert Xu <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt