* [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code
@ 2011-10-04 23:53 Darrick J. Wong
2011-10-04 23:54 ` [PATCH 1/4] crc32: Bolt on crc32c Darrick J. Wong
` (4 more replies)
0 siblings, 5 replies; 15+ messages in thread
From: Darrick J. Wong @ 2011-10-04 23:53 UTC (permalink / raw)
To: Andreas Dilger, Herbert Xu, Theodore Tso, David Miller,
Darrick J. Wong
Cc: Joakim Tjernlund, Bob Pearson, linux-kernel, Mingming Cao,
linux-crypto, linux-fsdevel, linux-ext4
Hi all,
This patchset (re)uses Bob Pearson's crc32 slice-by-8 code to stamp out a
software crc32c implementation. It requires that all ten of his patches (at
least the ones dated 31 Aug 2011) be applied. It removes the crc32c
implementation in crypto/ in favor of using the stamped-out one in lib/. There
is also a change to Kconfig so that the kernel builder can pick an
implementation best suited for the hardware.
The motivation for this patchset is that I am working on adding full metadata
checksumming to ext4. As far as performance impact of adding checksumming
goes, I see nearly no change with a standard mail server ffsb simulation. On a
test that involves only file creation and deletion and extent tree writes, I
see a drop of about 50 pcercent with the current kernel crc32c implementation;
this improves to a drop of about 20 percent with the enclosed crc32c code.
When metadata is usually a small fraction of total IO, this new implementation
doesn't help much because metadata is usually a small fraction of total IO.
However, when we are doing IO that is almost all metadata (such as rm -rf'ing a
tree), then this patch speeds up the operation substantially.
Incidentally, given that iscsi, sctp, and btrfs also use crc32c, this patchset
should improve their speed as well. I have not yet quantified that, however.
--D
^ permalink raw reply [flat|nested] 15+ messages in thread* [PATCH 1/4] crc32: Bolt on crc32c 2011-10-04 23:53 [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code Darrick J. Wong @ 2011-10-04 23:54 ` Darrick J. Wong 2011-10-21 12:28 ` Herbert Xu 2011-10-04 23:54 ` [PATCH 2/4] crypto: crc32c should use library implementation Darrick J. Wong ` (3 subsequent siblings) 4 siblings, 1 reply; 15+ messages in thread From: Darrick J. Wong @ 2011-10-04 23:54 UTC (permalink / raw) To: Andreas Dilger, Herbert Xu, Theodore Tso, David Miller, Darrick J. Wong Cc: Joakim Tjernlund, Bob Pearson, linux-kernel, Mingming Cao, linux-crypto, linux-fsdevel, linux-ext4 Reuse the existing crc32 code to stamp out a crc32c implementation. Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> --- include/linux/crc32.h | 2 ++ lib/Kconfig | 8 +++--- lib/crc32.c | 62 +++++++++++++++++++++++++++++++------------------ lib/crc32defs.h | 7 ++++++ lib/gen_crc32table.c | 35 ++++++++++++++++++++++------ 5 files changed, 80 insertions(+), 34 deletions(-) diff --git a/include/linux/crc32.h b/include/linux/crc32.h index 391a259..68267b6 100644 --- a/include/linux/crc32.h +++ b/include/linux/crc32.h @@ -11,6 +11,8 @@ extern u32 crc32_le(u32 crc, unsigned char const *p, size_t len); extern u32 crc32_be(u32 crc, unsigned char const *p, size_t len); +extern u32 __crc32c_le(u32 crc, unsigned char const *p, size_t len); + #define crc32(seed, data, length) crc32_le(seed, (unsigned char const *)(data), length) /* diff --git a/lib/Kconfig b/lib/Kconfig index 8e0bcbd..477be04 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -51,14 +51,14 @@ config CRC_ITU_T functions require M here. config CRC32 - tristate "CRC32 functions" + tristate "CRC32/CRC32c functions" default y select BITREVERSE help This option is provided for the case where no in-kernel-tree - modules require CRC32 functions, but a module built outside the - kernel tree does. Such modules that use library CRC32 functions - require M here. + modules require CRC32/CRC32c functions, but a module built outside + the kernel tree does. Such modules that use library CRC32/CRC32c + functions require M here. config CRC32_SELFTEST bool "CRC32 perform self test on init" diff --git a/lib/crc32.c b/lib/crc32.c index d56516d..8df9561 100644 --- a/lib/crc32.c +++ b/lib/crc32.c @@ -46,7 +46,7 @@ #include "crc32table.h" MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>"); -MODULE_DESCRIPTION("Ethernet CRC32 calculations"); +MODULE_DESCRIPTION("Various CRC32 calculations"); MODULE_LICENSE("GPL"); #if CRC_LE_BITS > 8 || CRC_BE_BITS > 8 @@ -135,46 +135,57 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) * @p: pointer to buffer over which CRC is run * @len: length of buffer @p */ -u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) +static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p, + size_t len, const u32 (*tab)[256], + u32 polynomial) { #if CRC_LE_BITS == 1 int i; while (len--) { crc ^= *p++; for (i = 0; i < 8; i++) - crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0); + crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0); } # elif CRC_LE_BITS == 2 while (len--) { crc ^= *p++; - crc = (crc >> 2) ^ crc32table_le[0][crc & 3]; - crc = (crc >> 2) ^ crc32table_le[0][crc & 3]; - crc = (crc >> 2) ^ crc32table_le[0][crc & 3]; - crc = (crc >> 2) ^ crc32table_le[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; } # elif CRC_LE_BITS == 4 while (len--) { crc ^= *p++; - crc = (crc >> 4) ^ crc32table_le[0][crc & 15]; - crc = (crc >> 4) ^ crc32table_le[0][crc & 15]; + crc = (crc >> 4) ^ tab[0][crc & 15]; + crc = (crc >> 4) ^ tab[0][crc & 15]; } # elif CRC_LE_BITS == 8 /* aka Sarwate algorithm */ while (len--) { crc ^= *p++; - crc = (crc >> 8) ^ crc32table_le[0][crc & 255]; + crc = (crc >> 8) ^ tab[0][crc & 255]; } # else - const u32 (*tab)[] = crc32table_le; - crc = (__force u32) __cpu_to_le32(crc); crc = crc32_body(crc, p, len, tab); crc = __le32_to_cpu((__force __le32)crc); #endif return crc; } + +u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_le_generic(crc, p, len, crc32table_le, CRCPOLY_LE); +} EXPORT_SYMBOL(crc32_le); +u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_le_generic(crc, p, len, crc32ctable_le, CRC32C_POLY_LE); +} +EXPORT_SYMBOL(__crc32c_le); + /** * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for @@ -182,7 +193,9 @@ EXPORT_SYMBOL(crc32_le); * @p: pointer to buffer over which CRC is run * @len: length of buffer @p */ -u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) +static inline u32 __pure crc32_be_generic(u32 crc, unsigned char const *p, + size_t len, const u32 (*tab)[256], + u32 polynomial) { #if CRC_BE_BITS == 1 int i; @@ -190,37 +203,40 @@ u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) crc ^= *p++ << 24; for (i = 0; i < 8; i++) crc = - (crc << 1) ^ ((crc & 0x80000000) ? CRCPOLY_BE : + (crc << 1) ^ ((crc & 0x80000000) ? polynomial : 0); } # elif CRC_BE_BITS == 2 while (len--) { crc ^= *p++ << 24; - crc = (crc << 2) ^ crc32table_be[0][crc >> 30]; - crc = (crc << 2) ^ crc32table_be[0][crc >> 30]; - crc = (crc << 2) ^ crc32table_be[0][crc >> 30]; - crc = (crc << 2) ^ crc32table_be[0][crc >> 30]; + crc = (crc << 2) ^ tab[0][crc >> 30]; + crc = (crc << 2) ^ tab[0][crc >> 30]; + crc = (crc << 2) ^ tab[0][crc >> 30]; + crc = (crc << 2) ^ tab[0][crc >> 30]; } # elif CRC_BE_BITS == 4 while (len--) { crc ^= *p++ << 24; - crc = (crc << 4) ^ crc32table_be[0][crc >> 28]; - crc = (crc << 4) ^ crc32table_be[0][crc >> 28]; + crc = (crc << 4) ^ tab[0][crc >> 28]; + crc = (crc << 4) ^ tab[0][crc >> 28]; } # elif CRC_BE_BITS == 8 while (len--) { crc ^= *p++ << 24; - crc = (crc << 8) ^ crc32table_be[0][crc >> 24]; + crc = (crc << 8) ^ tab[0][crc >> 24]; } # else - const u32 (*tab)[] = crc32table_be; - crc = (__force u32) __cpu_to_be32(crc); crc = crc32_body(crc, p, len, tab); crc = __be32_to_cpu((__force __be32)crc); # endif return crc; } + +u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_be_generic(crc, p, len, crc32table_be, CRCPOLY_BE); +} EXPORT_SYMBOL(crc32_be); #ifdef CONFIG_CRC32_SELFTEST diff --git a/lib/crc32defs.h b/lib/crc32defs.h index 8181592..6fd1917 100644 --- a/lib/crc32defs.h +++ b/lib/crc32defs.h @@ -7,6 +7,13 @@ #define CRCPOLY_BE 0x04c11db7 /* + * This is the CRC32c polynomial, as outlined by Castagnoli. + * x^32+x^28+x^27+x^26+x^25+x^23+x^22+x^20+x^19+x^18+x^14+x^13+x^11+x^10+x^9+ + * x^8+x^6+x^0 + */ +#define CRC32C_POLY_LE 0x82F63B78 + +/* * How many bits at a time to use. Valid values are 1, 2, 4, 8, 32 and 64. * For less performance-sensitive, use 4 or 8 to save table size. * For larger systems choose same as CPU architecture as default. diff --git a/lib/gen_crc32table.c b/lib/gen_crc32table.c index 0d9edd1..8f8d543 100644 --- a/lib/gen_crc32table.c +++ b/lib/gen_crc32table.c @@ -23,6 +23,7 @@ static uint32_t crc32table_le[LE_TABLE_ROWS][256]; static uint32_t crc32table_be[BE_TABLE_ROWS][256]; +static uint32_t crc32ctable_le[LE_TABLE_ROWS][256]; /** * crc32init_le() - allocate and initialize LE table data @@ -31,27 +32,38 @@ static uint32_t crc32table_be[BE_TABLE_ROWS][256]; * fact that crctable[i^j] = crctable[i] ^ crctable[j]. * */ -static void crc32init_le(void) +static void crc32init_le_generic(const uint32_t polynomial, + uint32_t (*tab)[256]) { unsigned i, j; uint32_t crc = 1; - crc32table_le[0][0] = 0; + tab[0][0] = 0; for (i = LE_TABLE_SIZE >> 1; i; i >>= 1) { - crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0); + crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0); for (j = 0; j < LE_TABLE_SIZE; j += 2 * i) - crc32table_le[0][i + j] = crc ^ crc32table_le[0][j]; + tab[0][i + j] = crc ^ tab[0][j]; } for (i = 0; i < LE_TABLE_SIZE; i++) { - crc = crc32table_le[0][i]; + crc = tab[0][i]; for (j = 1; j < LE_TABLE_ROWS; j++) { - crc = crc32table_le[0][crc & 0xff] ^ (crc >> 8); - crc32table_le[j][i] = crc; + crc = tab[0][crc & 0xff] ^ (crc >> 8); + tab[j][i] = crc; } } } +static void crc32init_le(void) +{ + crc32init_le_generic(CRCPOLY_LE, crc32table_le); +} + +static void crc32cinit_le(void) +{ + crc32init_le_generic(CRC32C_POLY_LE, crc32ctable_le); +} + /** * crc32init_be() - allocate and initialize BE table data */ @@ -114,6 +126,15 @@ int main(int argc, char** argv) BE_TABLE_SIZE, "tobe"); printf("};\n"); } + if (CRC_LE_BITS > 1) { + crc32cinit_le(); + printf("static const u32 __cacheline_aligned " + "crc32ctable_le[%d][%d] = {", + LE_TABLE_ROWS, LE_TABLE_SIZE); + output_table(crc32ctable_le, LE_TABLE_ROWS, + LE_TABLE_SIZE, "tole"); + printf("};\n"); + } return 0; } ^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH 1/4] crc32: Bolt on crc32c 2011-10-04 23:54 ` [PATCH 1/4] crc32: Bolt on crc32c Darrick J. Wong @ 2011-10-21 12:28 ` Herbert Xu 2011-10-21 16:57 ` Darrick J. Wong 0 siblings, 1 reply; 15+ messages in thread From: Herbert Xu @ 2011-10-21 12:28 UTC (permalink / raw) To: Darrick J. Wong Cc: Andreas Dilger, Theodore Tso, David Miller, Joakim Tjernlund, Bob Pearson, linux-kernel, Mingming Cao, linux-crypto, linux-fsdevel, linux-ext4 On Tue, Oct 04, 2011 at 04:54:03PM -0700, Darrick J. Wong wrote: > Reuse the existing crc32 code to stamp out a crc32c implementation. > > Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Did you want this to go through my tree? If so then there is a problem since it doesn't apply at all. Cheers, -- Email: Herbert Xu <herbert@gondor.apana.org.au> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 1/4] crc32: Bolt on crc32c 2011-10-21 12:28 ` Herbert Xu @ 2011-10-21 16:57 ` Darrick J. Wong 2011-10-21 19:15 ` Herbert Xu 0 siblings, 1 reply; 15+ messages in thread From: Darrick J. Wong @ 2011-10-21 16:57 UTC (permalink / raw) To: Herbert Xu Cc: Andreas Dilger, Theodore Tso, David Miller, Joakim Tjernlund, Bob Pearson, linux-kernel, Mingming Cao, linux-crypto, linux-fsdevel, linux-ext4 On Fri, Oct 21, 2011 at 02:28:03PM +0200, Herbert Xu wrote: > On Tue, Oct 04, 2011 at 04:54:03PM -0700, Darrick J. Wong wrote: > > Reuse the existing crc32 code to stamp out a crc32c implementation. > > > > Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> > > Did you want this to go through my tree? If so then there is a > problem since it doesn't apply at all. My patchset builds upon Bob Pearson's crc32 patchset from early September. Do my patches fail to apply after applying his patchset? Or, to speed things along, should I simply repost both Bob's and my patches as one big series? Bob, have you sent out a new iteration of your patches since September 6th? --D > > Cheers, > -- > Email: Herbert Xu <herbert@gondor.apana.org.au> > Home Page: http://gondor.apana.org.au/~herbert/ > PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt > -- > To unsubscribe from this list: send the line "unsubscribe linux-ext4" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html > ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 1/4] crc32: Bolt on crc32c 2011-10-21 16:57 ` Darrick J. Wong @ 2011-10-21 19:15 ` Herbert Xu 2011-10-26 17:16 ` Darrick J. Wong 2011-11-15 8:48 ` [PATCH 1/4] crc32: Bolt on crc32c Darrick J. Wong 0 siblings, 2 replies; 15+ messages in thread From: Herbert Xu @ 2011-10-21 19:15 UTC (permalink / raw) To: Darrick J. Wong Cc: Andreas Dilger, Theodore Tso, David Miller, Joakim Tjernlund, Bob Pearson, linux-kernel, Mingming Cao, linux-crypto, linux-fsdevel, linux-ext4 On Fri, Oct 21, 2011 at 09:57:03AM -0700, Darrick J. Wong wrote: > > My patchset builds upon Bob Pearson's crc32 patchset from early September. Do > my patches fail to apply after applying his patchset? > > Or, to speed things along, should I simply repost both Bob's and my patches as > one big series? > > Bob, have you sent out a new iteration of your patches since September 6th? I'm fine with you pushing this through whichever tree that Bob's patches are going through. Cheers, -- Email: Herbert Xu <herbert@gondor.apana.org.au> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 1/4] crc32: Bolt on crc32c 2011-10-21 19:15 ` Herbert Xu @ 2011-10-26 17:16 ` Darrick J. Wong 2011-10-27 18:32 ` Time for a fresh slice-by-8 crc32.c posting? Darrick J. Wong 2011-11-15 8:48 ` [PATCH 1/4] crc32: Bolt on crc32c Darrick J. Wong 1 sibling, 1 reply; 15+ messages in thread From: Darrick J. Wong @ 2011-10-26 17:16 UTC (permalink / raw) To: Bob Pearson Cc: Andreas Dilger, Theodore Tso, David Miller, Joakim Tjernlund, Bob Pearson, linux-kernel, Mingming Cao, linux-crypto, linux-fsdevel, linux-ext4, Herbert Xu On Fri, Oct 21, 2011 at 09:15:14PM +0200, Herbert Xu wrote: > On Fri, Oct 21, 2011 at 09:57:03AM -0700, Darrick J. Wong wrote: > > > > My patchset builds upon Bob Pearson's crc32 patchset from early September. Do > > my patches fail to apply after applying his patchset? > > > > Or, to speed things along, should I simply repost both Bob's and my patches as > > one big series? > > > > Bob, have you sent out a new iteration of your patches since September 6th? > > I'm fine with you pushing this through whichever tree that Bob's > patches are going through. Bob, Which tree (if any) are your patches going through? --D ^ permalink raw reply [flat|nested] 15+ messages in thread
* Time for a fresh slice-by-8 crc32.c posting? 2011-10-26 17:16 ` Darrick J. Wong @ 2011-10-27 18:32 ` Darrick J. Wong 0 siblings, 0 replies; 15+ messages in thread From: Darrick J. Wong @ 2011-10-27 18:32 UTC (permalink / raw) To: Bob Pearson Cc: Andreas Dilger, Theodore Tso, David Miller, Joakim Tjernlund, linux-kernel, Mingming Cao, linux-crypto, linux-fsdevel, linux-ext4, Herbert Xu, Andrew Morton Hi Bob, Would you mind posting your current crc32 patches to lkml again? A couple of months have gone by, and it sure would be nice to replace the circa-July patch in -next with a newer one. I recall that there were requests for some code changes even in Bob's 8/31 submission, so it'd be nice to have a fresh set from you with your latest changes. I'd also like to freshen my crc32c refactor patches and send them along too. To clarify, I tried the new crc32{,c} on my ppc32 and it passed the self test. --D On Wed, Oct 26, 2011 at 10:16:10AM -0700, Darrick J. Wong wrote: > On Fri, Oct 21, 2011 at 09:15:14PM +0200, Herbert Xu wrote: > > On Fri, Oct 21, 2011 at 09:57:03AM -0700, Darrick J. Wong wrote: > > > > > > My patchset builds upon Bob Pearson's crc32 patchset from early September. Do > > > my patches fail to apply after applying his patchset? > > > > > > Or, to speed things along, should I simply repost both Bob's and my patches as > > > one big series? > > > > > > Bob, have you sent out a new iteration of your patches since September 6th? > > > > I'm fine with you pushing this through whichever tree that Bob's > > patches are going through. > > Bob, > > Which tree (if any) are your patches going through? > > --D > > -- > To unsubscribe from this list: send the line "unsubscribe linux-ext4" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 1/4] crc32: Bolt on crc32c 2011-10-21 19:15 ` Herbert Xu 2011-10-26 17:16 ` Darrick J. Wong @ 2011-11-15 8:48 ` Darrick J. Wong 2011-11-15 15:38 ` Bob Pearson 1 sibling, 1 reply; 15+ messages in thread From: Darrick J. Wong @ 2011-11-15 8:48 UTC (permalink / raw) To: Herbert Xu Cc: Andreas Dilger, Theodore Tso, David Miller, Joakim Tjernlund, Bob Pearson, linux-kernel, Mingming Cao, linux-crypto, linux-fsdevel, linux-ext4 On Fri, Oct 21, 2011 at 09:15:14PM +0200, Herbert Xu wrote: > On Fri, Oct 21, 2011 at 09:57:03AM -0700, Darrick J. Wong wrote: > > > > My patchset builds upon Bob Pearson's crc32 patchset from early September. Do > > my patches fail to apply after applying his patchset? > > > > Or, to speed things along, should I simply repost both Bob's and my patches as > > one big series? > > > > Bob, have you sent out a new iteration of your patches since September 6th? > > I'm fine with you pushing this through whichever tree that Bob's > patches are going through. Well... it's been 2.5 weeks since I last asked about this. No reply, afaict. I haven't seen any complaints about Bob's latest patchset, nor any complaints about my set that sits atop his. On the other hand, I'm pretty sure I haven't seen Bob's patches appear in any trees, and Google shows no recent progress. Herbert, would you object to pushing the whole patchset through the crypto tree? --D > > Cheers, > -- > Email: Herbert Xu <herbert@gondor.apana.org.au> > Home Page: http://gondor.apana.org.au/~herbert/ > PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt > -- > To unsubscribe from this list: send the line "unsubscribe linux-ext4" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html > ^ permalink raw reply [flat|nested] 15+ messages in thread
* RE: [PATCH 1/4] crc32: Bolt on crc32c 2011-11-15 8:48 ` [PATCH 1/4] crc32: Bolt on crc32c Darrick J. Wong @ 2011-11-15 15:38 ` Bob Pearson 0 siblings, 0 replies; 15+ messages in thread From: Bob Pearson @ 2011-11-15 15:38 UTC (permalink / raw) To: djwong, 'Herbert Xu' Cc: 'Andreas Dilger', 'Theodore Tso', 'David Miller', 'Joakim Tjernlund', 'linux-kernel', 'Mingming Cao', 'linux-crypto', 'linux-fsdevel', linux-ext4 I'd have sent new bits by now. Although the changes are minor and cosmetic. The problem is that due to getting things ready for SC11 (where I am now) I have been unable to test anything for the past two weeks. I can retest everything next week or you can go with the bits that are out there. > -----Original Message----- > From: Darrick J. Wong [mailto:djwong@us.ibm.com] > Sent: Tuesday, November 15, 2011 2:48 AM > To: Herbert Xu > Cc: Andreas Dilger; Theodore Tso; David Miller; Joakim Tjernlund; Bob > Pearson; linux-kernel; Mingming Cao; linux-crypto; linux-fsdevel; linux- > ext4@vger.kernel.org > Subject: Re: [PATCH 1/4] crc32: Bolt on crc32c > > On Fri, Oct 21, 2011 at 09:15:14PM +0200, Herbert Xu wrote: > > On Fri, Oct 21, 2011 at 09:57:03AM -0700, Darrick J. Wong wrote: > > > > > > My patchset builds upon Bob Pearson's crc32 patchset from early > September. Do > > > my patches fail to apply after applying his patchset? > > > > > > Or, to speed things along, should I simply repost both Bob's and my > patches as > > > one big series? > > > > > > Bob, have you sent out a new iteration of your patches since September > 6th? > > > > I'm fine with you pushing this through whichever tree that Bob's > > patches are going through. > > Well... it's been 2.5 weeks since I last asked about this. No reply, afaict. > I haven't seen any complaints about Bob's latest patchset, nor any complaints > about my set that sits atop his. On the other hand, I'm pretty sure I haven't > seen Bob's patches appear in any trees, and Google shows no recent > progress. > > Herbert, would you object to pushing the whole patchset through the crypto > tree? > > --D > > > > Cheers, > > -- > > Email: Herbert Xu <herbert@gondor.apana.org.au> > > Home Page: http://gondor.apana.org.au/~herbert/ > > PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt > > -- > > To unsubscribe from this list: send the line "unsubscribe linux-ext4" in > > the body of a message to majordomo@vger.kernel.org > > More majordomo info at http://vger.kernel.org/majordomo-info.html > > ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 2/4] crypto: crc32c should use library implementation 2011-10-04 23:53 [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code Darrick J. Wong 2011-10-04 23:54 ` [PATCH 1/4] crc32: Bolt on crc32c Darrick J. Wong @ 2011-10-04 23:54 ` Darrick J. Wong 2011-10-04 23:54 ` [PATCH 3/4] crc32: Add self-test code for crc32c Darrick J. Wong ` (2 subsequent siblings) 4 siblings, 0 replies; 15+ messages in thread From: Darrick J. Wong @ 2011-10-04 23:54 UTC (permalink / raw) To: Andreas Dilger, Herbert Xu, Theodore Tso, David Miller, Darrick J. Wong Cc: Joakim Tjernlund, Bob Pearson, linux-kernel, Mingming Cao, linux-crypto, linux-fsdevel, linux-ext4 Since lib/crc32.c now provides crc32c, remove the software implementation here and call the library function instead. Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> --- crypto/Kconfig | 1 + crypto/crc32c.c | 94 ++----------------------------------------------------- 2 files changed, 4 insertions(+), 91 deletions(-) diff --git a/crypto/Kconfig b/crypto/Kconfig index ae27b75..28fdbf6 100644 --- a/crypto/Kconfig +++ b/crypto/Kconfig @@ -302,6 +302,7 @@ comment "Digest" config CRYPTO_CRC32C tristate "CRC32c CRC algorithm" select CRYPTO_HASH + select CRC32 help Castagnoli, et al Cyclic Redundancy-Check Algorithm. Used by iSCSI for header and data digests and by others. diff --git a/crypto/crc32c.c b/crypto/crc32c.c index 3f9ad28..06f7018 100644 --- a/crypto/crc32c.c +++ b/crypto/crc32c.c @@ -40,6 +40,7 @@ #include <linux/module.h> #include <linux/string.h> #include <linux/kernel.h> +#include <linux/crc32.h> #define CHKSUM_BLOCK_SIZE 1 #define CHKSUM_DIGEST_SIZE 4 @@ -53,95 +54,6 @@ struct chksum_desc_ctx { }; /* - * This is the CRC-32C table - * Generated with: - * width = 32 bits - * poly = 0x1EDC6F41 - * reflect input bytes = true - * reflect output bytes = true - */ - -static const u32 crc32c_table[256] = { - 0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L, - 0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL, - 0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL, - 0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L, - 0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL, - 0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L, - 0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L, - 0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL, - 0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL, - 0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L, - 0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L, - 0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL, - 0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L, - 0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL, - 0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL, - 0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L, - 0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L, - 0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L, - 0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L, - 0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L, - 0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L, - 0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L, - 0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L, - 0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L, - 0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L, - 0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L, - 0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L, - 0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L, - 0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L, - 0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L, - 0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L, - 0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L, - 0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL, - 0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L, - 0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L, - 0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL, - 0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L, - 0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL, - 0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL, - 0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L, - 0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L, - 0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL, - 0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL, - 0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L, - 0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL, - 0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L, - 0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L, - 0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL, - 0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L, - 0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL, - 0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL, - 0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L, - 0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL, - 0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L, - 0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L, - 0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL, - 0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL, - 0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L, - 0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L, - 0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL, - 0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L, - 0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL, - 0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL, - 0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L -}; - -/* - * Steps through buffer one byte at at time, calculates reflected - * crc using table. - */ - -static u32 crc32c(u32 crc, const u8 *data, unsigned int length) -{ - while (length--) - crc = crc32c_table[(crc ^ *data++) & 0xFFL] ^ (crc >> 8); - - return crc; -} - -/* * Steps through buffer one byte at at time, calculates reflected * crc using table. */ @@ -179,7 +91,7 @@ static int chksum_update(struct shash_desc *desc, const u8 *data, { struct chksum_desc_ctx *ctx = shash_desc_ctx(desc); - ctx->crc = crc32c(ctx->crc, data, length); + ctx->crc = __crc32c_le(ctx->crc, data, length); return 0; } @@ -193,7 +105,7 @@ static int chksum_final(struct shash_desc *desc, u8 *out) static int __chksum_finup(u32 *crcp, const u8 *data, unsigned int len, u8 *out) { - *(__le32 *)out = ~cpu_to_le32(crc32c(*crcp, data, len)); + *(__le32 *)out = ~cpu_to_le32(__crc32c_le(*crcp, data, len)); return 0; } ^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH 3/4] crc32: Add self-test code for crc32c 2011-10-04 23:53 [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code Darrick J. Wong 2011-10-04 23:54 ` [PATCH 1/4] crc32: Bolt on crc32c Darrick J. Wong 2011-10-04 23:54 ` [PATCH 2/4] crypto: crc32c should use library implementation Darrick J. Wong @ 2011-10-04 23:54 ` Darrick J. Wong 2011-10-04 23:54 ` [PATCH 4/4] crc32: Select an algorithm via kconfig Darrick J. Wong 2011-10-06 20:20 ` [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code Darrick J. Wong 4 siblings, 0 replies; 15+ messages in thread From: Darrick J. Wong @ 2011-10-04 23:54 UTC (permalink / raw) To: Andreas Dilger, Herbert Xu, Theodore Tso, David Miller, Darrick J. Wong Cc: Joakim Tjernlund, Bob Pearson, linux-kernel, Mingming Cao, linux-crypto, linux-fsdevel, linux-ext4 Add self-test code for crc32c. Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> --- lib/crc32.c | 363 ++++++++++++++++++++++++++++++++++++++++++----------------- 1 files changed, 261 insertions(+), 102 deletions(-) diff --git a/lib/crc32.c b/lib/crc32.c index 8df9561..382fa76 100644 --- a/lib/crc32.c +++ b/lib/crc32.c @@ -765,113 +765,265 @@ static struct crc_test { u32 length; /* random 11 bit length of test */ u32 crc_le; /* expected crc32_le result */ u32 crc_be; /* expected crc32_be result */ + u32 crc32c_le; /* expected crc32c_le result */ } test[] = { - {0x674bf11d, 0x00000038, 0x00000542, 0x0af6d466, 0xd8b6e4c1}, - {0x35c672c6, 0x0000003a, 0x000001aa, 0xc6d3dfba, 0x28aaf3ad}, - {0x496da28e, 0x00000039, 0x000005af, 0xd933660f, 0x5d57e81f}, - {0x09a9b90e, 0x00000027, 0x000001f8, 0xb45fe007, 0xf45fca9a}, - {0xdc97e5a9, 0x00000025, 0x000003b6, 0xf81a3562, 0xe0126ba2}, - {0x47c58900, 0x0000000a, 0x000000b9, 0x8e58eccf, 0xf3afc793}, - {0x292561e8, 0x0000000c, 0x00000403, 0xa2ba8aaf, 0x0b797aed}, - {0x415037f6, 0x00000003, 0x00000676, 0xa17d52e8, 0x7f0fdf35}, - {0x3466e707, 0x00000026, 0x00000042, 0x258319be, 0x75c484a2}, - {0xafd1281b, 0x00000023, 0x000002ee, 0x4428eaf8, 0x06c7ad10}, - {0xd3857b18, 0x00000028, 0x000004a2, 0x5c430821, 0xb062b7cb}, - {0x1d825a8f, 0x0000002b, 0x0000050b, 0xd2c45f0c, 0xd68634e0}, - {0x5033e3bc, 0x0000000b, 0x00000078, 0xa3ea4113, 0xac6d31fb}, - {0x94f1fb5e, 0x0000000f, 0x000003a2, 0xfbfc50b1, 0x3cfe50ed}, - {0xc9a0fe14, 0x00000009, 0x00000473, 0x5fb61894, 0x87070591}, - {0x88a034b1, 0x0000001c, 0x000005ad, 0xc1b16053, 0x46f95c67}, - {0xf0f72239, 0x00000020, 0x0000026d, 0xa6fa58f3, 0xf8c2c1dd}, - {0xcc20a5e3, 0x0000003b, 0x0000067a, 0x7740185a, 0x308b979a}, - {0xce589c95, 0x0000002b, 0x00000641, 0xd055e987, 0x40aae25b}, - {0x78edc885, 0x00000035, 0x000005be, 0xa39cb14b, 0x035b0d1f}, - {0x9d40a377, 0x0000003b, 0x00000038, 0x1f47ccd2, 0x197fbc9d}, - {0x703d0e01, 0x0000003c, 0x000006f1, 0x88735e7c, 0xfed57c5a}, - {0x776bf505, 0x0000000f, 0x000005b2, 0x5cc4fc01, 0xf32efb97}, - {0x4a3e7854, 0x00000027, 0x000004b8, 0x8d923c82, 0x0cbfb4a2}, - {0x209172dd, 0x0000003b, 0x00000356, 0xb89e9c2b, 0xd7868138}, - {0x3ba4cc5b, 0x0000002f, 0x00000203, 0xe51601a9, 0x5b2a1032}, - {0xfc62f297, 0x00000000, 0x00000079, 0x71a8e1a2, 0x5d88685f}, - {0x64280b8b, 0x00000016, 0x000007ab, 0x0fa7a30c, 0xda3a455f}, - {0x97dd724b, 0x00000033, 0x000007ad, 0x5788b2f4, 0xd7326d32}, - {0x61394b52, 0x00000035, 0x00000571, 0xc66525f1, 0xcabe7fef}, - {0x29b4faff, 0x00000024, 0x0000006e, 0xca13751e, 0x993648e0}, - {0x29bfb1dc, 0x0000000b, 0x00000244, 0x436c43f7, 0x429f7a59}, - {0x86ae934b, 0x00000035, 0x00000104, 0x0760ec93, 0x9cf7d0f4}, - {0xc4c1024e, 0x0000002e, 0x000006b1, 0x6516a3ec, 0x19321f9c}, - {0x3287a80a, 0x00000026, 0x00000496, 0x0b257eb1, 0x754ebd51}, - {0xa4db423e, 0x00000023, 0x0000045d, 0x9b3a66dc, 0x873e9f11}, - {0x7a1078df, 0x00000015, 0x0000014a, 0x8c2484c5, 0x6a628659}, - {0x6048bd5b, 0x00000006, 0x0000006a, 0x897e3559, 0xac9961af}, - {0xd8f9ea20, 0x0000003d, 0x00000277, 0x60eb905b, 0xed2aaf99}, - {0xea5ec3b4, 0x0000002a, 0x000004fe, 0x869965dc, 0x6c1f833b}, - {0x2dfb005d, 0x00000016, 0x00000345, 0x6a3b117e, 0xf05e8521}, - {0x5a214ade, 0x00000020, 0x000005b6, 0x467f70be, 0xcb22ccd3}, - {0xf0ab9cca, 0x00000032, 0x00000515, 0xed223df3, 0x7f3ef01d}, - {0x91b444f9, 0x0000002e, 0x000007f8, 0x84e9a983, 0x5676756f}, - {0x1b5d2ddb, 0x0000002e, 0x0000012c, 0xba638c4c, 0x3f42047b}, - {0xd824d1bb, 0x0000003a, 0x000007b5, 0x6288653b, 0x3a3ebea0}, - {0x0470180c, 0x00000034, 0x000001f0, 0x9d5b80d6, 0x3de08195}, - {0xffaa3a3f, 0x00000036, 0x00000299, 0xf3a82ab8, 0x53e0c13d}, - {0x6406cfeb, 0x00000023, 0x00000600, 0xa920b8e8, 0xe4e2acf4}, - {0xb24aaa38, 0x0000003e, 0x000004a1, 0x657cc328, 0x5077b2c3}, - {0x58b2ab7c, 0x00000039, 0x000002b4, 0x3a17ee7e, 0x9dcb3643}, - {0x3db85970, 0x00000006, 0x000002b6, 0x95268b59, 0xb9812c10}, - {0x857830c5, 0x00000003, 0x00000590, 0x4ef439d5, 0xf042161d}, - {0xe1fcd978, 0x0000003e, 0x000007d8, 0xae8d8699, 0xce0a1ef5}, - {0xb982a768, 0x00000016, 0x000006e0, 0x62fad3df, 0x5f8a067b}, - {0x1d581ce8, 0x0000001e, 0x0000058b, 0xf0f5da53, 0x26e39eee}, - {0x2456719b, 0x00000025, 0x00000503, 0x4296ac64, 0xd50e4c14}, - {0xfae6d8f2, 0x00000000, 0x0000055d, 0x057fdf2e, 0x2a31391a}, - {0xcba828e3, 0x00000039, 0x000002ce, 0xe3f22351, 0x8f00877b}, - {0x13d25952, 0x0000000a, 0x0000072d, 0x76d4b4cc, 0x5eb67ec3}, - {0x0342be3f, 0x00000015, 0x00000599, 0xec75d9f1, 0x9d4d2826}, - {0xeaa344e0, 0x00000014, 0x000004d8, 0x72a4c981, 0x2064ea06}, - {0xbbb52021, 0x0000003b, 0x00000272, 0x04af99fc, 0xaf042d35}, - {0xb66384dc, 0x0000001d, 0x000007fc, 0xd7629116, 0x782bd801}, - {0x616c01b6, 0x00000022, 0x000002c8, 0x5b1dab30, 0x783ce7d2}, - {0xce2bdaad, 0x00000016, 0x0000062a, 0x932535c8, 0x3f02926d}, - {0x00fe84d7, 0x00000005, 0x00000205, 0x850e50aa, 0x753d649c}, - {0xbebdcb4c, 0x00000006, 0x0000055d, 0xbeaa37a2, 0x2d8c9eba}, - {0xd8b1a02a, 0x00000010, 0x00000387, 0x5017d2fc, 0x503541a5}, - {0x3b96cad2, 0x00000036, 0x00000347, 0x1d2372ae, 0x926cd90b}, - {0xc94c1ed7, 0x00000005, 0x0000038b, 0x9e9fdb22, 0x144a9178}, - {0x1aad454e, 0x00000025, 0x000002b2, 0xc3f6315c, 0x5c7a35b3}, - {0xa4fec9a6, 0x00000000, 0x000006d6, 0x90be5080, 0xa4107605}, - {0x1bbe71e2, 0x0000001f, 0x000002fd, 0x4e504c3b, 0x284ccaf1}, - {0x4201c7e4, 0x00000002, 0x000002b7, 0x7822e3f9, 0x0cc912a9}, - {0x23fddc96, 0x00000003, 0x00000627, 0x8a385125, 0x07767e78}, - {0xd82ba25c, 0x00000016, 0x0000063e, 0x98e4148a, 0x283330c9}, - {0x786f2032, 0x0000002d, 0x0000060f, 0xf201600a, 0xf561bfcd}, - {0xfebe4e1f, 0x0000002a, 0x000004f2, 0x95e51961, 0xfd80dcab}, - {0x1a6e0a39, 0x00000008, 0x00000672, 0x8af6c2a5, 0x78dd84cb}, - {0x56000ab8, 0x0000000e, 0x000000e5, 0x36bacb8f, 0x22ee1f77}, - {0x4717fe0c, 0x00000000, 0x000006ec, 0x8439f342, 0x5c8e03da}, - {0xd5d5d68e, 0x0000003c, 0x000003a3, 0x46fff083, 0x177d1b39}, - {0xc25dd6c6, 0x00000024, 0x000006c0, 0x5ceb8eb4, 0x892b0d16}, - {0xe9b11300, 0x00000023, 0x00000683, 0x07a5d59a, 0x6c6a3208}, - {0x95cd285e, 0x00000001, 0x00000047, 0x7b3a4368, 0x0202c07e}, - {0xd9245a25, 0x0000001e, 0x000003a6, 0xd33c1841, 0x1936c0d5}, - {0x103279db, 0x00000006, 0x0000039b, 0xca09b8a0, 0x77d62892}, - {0x1cba3172, 0x00000027, 0x000001c8, 0xcb377194, 0xebe682db}, - {0x8f613739, 0x0000000c, 0x000001df, 0xb4b0bc87, 0x7710bd43}, - {0x1c6aa90d, 0x0000001b, 0x0000053c, 0x70559245, 0xda7894ac}, - {0xaabe5b93, 0x0000003d, 0x00000715, 0xcdbf42fa, 0x0c3b99e7}, - {0xf15dd038, 0x00000006, 0x000006db, 0x6e104aea, 0x8d5967f2}, - {0x584dd49c, 0x00000020, 0x000007bc, 0x36b6cfd6, 0xad4e23b2}, - {0x5d8c9506, 0x00000020, 0x00000470, 0x4c62378e, 0x31d92640}, - {0xb80d17b0, 0x00000032, 0x00000346, 0x22a5bb88, 0x9a7ec89f}, - {0xdaf0592e, 0x00000023, 0x000007b0, 0x3cab3f99, 0x9b1fdd99}, - {0x4793cc85, 0x0000000d, 0x00000706, 0xe82e04f6, 0xed3db6b7}, - {0x82ebf64e, 0x00000009, 0x000007c3, 0x69d590a9, 0x9efa8499}, - {0xb18a0319, 0x00000026, 0x000007db, 0x1cf98dcc, 0x8fa9ad6a}, + {0x674bf11d, 0x00000038, 0x00000542, 0x0af6d466, 0xd8b6e4c1, + 0xf6e93d6c}, + {0x35c672c6, 0x0000003a, 0x000001aa, 0xc6d3dfba, 0x28aaf3ad, + 0x0fe92aca}, + {0x496da28e, 0x00000039, 0x000005af, 0xd933660f, 0x5d57e81f, + 0x52e1ebb8}, + {0x09a9b90e, 0x00000027, 0x000001f8, 0xb45fe007, 0xf45fca9a, + 0x0798af9a}, + {0xdc97e5a9, 0x00000025, 0x000003b6, 0xf81a3562, 0xe0126ba2, + 0x18eb3152}, + {0x47c58900, 0x0000000a, 0x000000b9, 0x8e58eccf, 0xf3afc793, + 0xd00d08c7}, + {0x292561e8, 0x0000000c, 0x00000403, 0xa2ba8aaf, 0x0b797aed, + 0x8ba966bc}, + {0x415037f6, 0x00000003, 0x00000676, 0xa17d52e8, 0x7f0fdf35, + 0x11d694a2}, + {0x3466e707, 0x00000026, 0x00000042, 0x258319be, 0x75c484a2, + 0x6ab3208d}, + {0xafd1281b, 0x00000023, 0x000002ee, 0x4428eaf8, 0x06c7ad10, + 0xba4603c5}, + {0xd3857b18, 0x00000028, 0x000004a2, 0x5c430821, 0xb062b7cb, + 0xe6071c6f}, + {0x1d825a8f, 0x0000002b, 0x0000050b, 0xd2c45f0c, 0xd68634e0, + 0x179ec30a}, + {0x5033e3bc, 0x0000000b, 0x00000078, 0xa3ea4113, 0xac6d31fb, + 0x0903beb8}, + {0x94f1fb5e, 0x0000000f, 0x000003a2, 0xfbfc50b1, 0x3cfe50ed, + 0x6a7cb4fa}, + {0xc9a0fe14, 0x00000009, 0x00000473, 0x5fb61894, 0x87070591, + 0xdb535801}, + {0x88a034b1, 0x0000001c, 0x000005ad, 0xc1b16053, 0x46f95c67, + 0x92bed597}, + {0xf0f72239, 0x00000020, 0x0000026d, 0xa6fa58f3, 0xf8c2c1dd, + 0x192a3f1b}, + {0xcc20a5e3, 0x0000003b, 0x0000067a, 0x7740185a, 0x308b979a, + 0xccbaec1a}, + {0xce589c95, 0x0000002b, 0x00000641, 0xd055e987, 0x40aae25b, + 0x7eabae4d}, + {0x78edc885, 0x00000035, 0x000005be, 0xa39cb14b, 0x035b0d1f, + 0x28c72982}, + {0x9d40a377, 0x0000003b, 0x00000038, 0x1f47ccd2, 0x197fbc9d, + 0xc3cd4d18}, + {0x703d0e01, 0x0000003c, 0x000006f1, 0x88735e7c, 0xfed57c5a, + 0xbca8f0e7}, + {0x776bf505, 0x0000000f, 0x000005b2, 0x5cc4fc01, 0xf32efb97, + 0x713f60b3}, + {0x4a3e7854, 0x00000027, 0x000004b8, 0x8d923c82, 0x0cbfb4a2, + 0xebd08fd5}, + {0x209172dd, 0x0000003b, 0x00000356, 0xb89e9c2b, 0xd7868138, + 0x64406c59}, + {0x3ba4cc5b, 0x0000002f, 0x00000203, 0xe51601a9, 0x5b2a1032, + 0x7421890e}, + {0xfc62f297, 0x00000000, 0x00000079, 0x71a8e1a2, 0x5d88685f, + 0xe9347603}, + {0x64280b8b, 0x00000016, 0x000007ab, 0x0fa7a30c, 0xda3a455f, + 0x1bef9060}, + {0x97dd724b, 0x00000033, 0x000007ad, 0x5788b2f4, 0xd7326d32, + 0x34720072}, + {0x61394b52, 0x00000035, 0x00000571, 0xc66525f1, 0xcabe7fef, + 0x48310f59}, + {0x29b4faff, 0x00000024, 0x0000006e, 0xca13751e, 0x993648e0, + 0x783a4213}, + {0x29bfb1dc, 0x0000000b, 0x00000244, 0x436c43f7, 0x429f7a59, + 0x9e8efd41}, + {0x86ae934b, 0x00000035, 0x00000104, 0x0760ec93, 0x9cf7d0f4, + 0xfc3d34a5}, + {0xc4c1024e, 0x0000002e, 0x000006b1, 0x6516a3ec, 0x19321f9c, + 0x17a52ae2}, + {0x3287a80a, 0x00000026, 0x00000496, 0x0b257eb1, 0x754ebd51, + 0x886d935a}, + {0xa4db423e, 0x00000023, 0x0000045d, 0x9b3a66dc, 0x873e9f11, + 0xeaaeaeb2}, + {0x7a1078df, 0x00000015, 0x0000014a, 0x8c2484c5, 0x6a628659, + 0x8e900a4b}, + {0x6048bd5b, 0x00000006, 0x0000006a, 0x897e3559, 0xac9961af, + 0xd74662b1}, + {0xd8f9ea20, 0x0000003d, 0x00000277, 0x60eb905b, 0xed2aaf99, + 0xd26752ba}, + {0xea5ec3b4, 0x0000002a, 0x000004fe, 0x869965dc, 0x6c1f833b, + 0x8b1fcd62}, + {0x2dfb005d, 0x00000016, 0x00000345, 0x6a3b117e, 0xf05e8521, + 0xf54342fe}, + {0x5a214ade, 0x00000020, 0x000005b6, 0x467f70be, 0xcb22ccd3, + 0x5b95b988}, + {0xf0ab9cca, 0x00000032, 0x00000515, 0xed223df3, 0x7f3ef01d, + 0x2e1176be}, + {0x91b444f9, 0x0000002e, 0x000007f8, 0x84e9a983, 0x5676756f, + 0x66120546}, + {0x1b5d2ddb, 0x0000002e, 0x0000012c, 0xba638c4c, 0x3f42047b, + 0xf256a5cc}, + {0xd824d1bb, 0x0000003a, 0x000007b5, 0x6288653b, 0x3a3ebea0, + 0x4af1dd69}, + {0x0470180c, 0x00000034, 0x000001f0, 0x9d5b80d6, 0x3de08195, + 0x56f0a04a}, + {0xffaa3a3f, 0x00000036, 0x00000299, 0xf3a82ab8, 0x53e0c13d, + 0x74f6b6b2}, + {0x6406cfeb, 0x00000023, 0x00000600, 0xa920b8e8, 0xe4e2acf4, + 0x085951fd}, + {0xb24aaa38, 0x0000003e, 0x000004a1, 0x657cc328, 0x5077b2c3, + 0xc65387eb}, + {0x58b2ab7c, 0x00000039, 0x000002b4, 0x3a17ee7e, 0x9dcb3643, + 0x1ca9257b}, + {0x3db85970, 0x00000006, 0x000002b6, 0x95268b59, 0xb9812c10, + 0xfd196d76}, + {0x857830c5, 0x00000003, 0x00000590, 0x4ef439d5, 0xf042161d, + 0x5ef88339}, + {0xe1fcd978, 0x0000003e, 0x000007d8, 0xae8d8699, 0xce0a1ef5, + 0x2c3714d9}, + {0xb982a768, 0x00000016, 0x000006e0, 0x62fad3df, 0x5f8a067b, + 0x58576548}, + {0x1d581ce8, 0x0000001e, 0x0000058b, 0xf0f5da53, 0x26e39eee, + 0xfd7c57de}, + {0x2456719b, 0x00000025, 0x00000503, 0x4296ac64, 0xd50e4c14, + 0xd5fedd59}, + {0xfae6d8f2, 0x00000000, 0x0000055d, 0x057fdf2e, 0x2a31391a, + 0x1cc3b17b}, + {0xcba828e3, 0x00000039, 0x000002ce, 0xe3f22351, 0x8f00877b, + 0x270eed73}, + {0x13d25952, 0x0000000a, 0x0000072d, 0x76d4b4cc, 0x5eb67ec3, + 0x91ecbb11}, + {0x0342be3f, 0x00000015, 0x00000599, 0xec75d9f1, 0x9d4d2826, + 0x05ed8d0c}, + {0xeaa344e0, 0x00000014, 0x000004d8, 0x72a4c981, 0x2064ea06, + 0x0b09ad5b}, + {0xbbb52021, 0x0000003b, 0x00000272, 0x04af99fc, 0xaf042d35, + 0xf8d511fb}, + {0xb66384dc, 0x0000001d, 0x000007fc, 0xd7629116, 0x782bd801, + 0x5ad832cc}, + {0x616c01b6, 0x00000022, 0x000002c8, 0x5b1dab30, 0x783ce7d2, + 0x1214d196}, + {0xce2bdaad, 0x00000016, 0x0000062a, 0x932535c8, 0x3f02926d, + 0x5747218a}, + {0x00fe84d7, 0x00000005, 0x00000205, 0x850e50aa, 0x753d649c, + 0xde8f14de}, + {0xbebdcb4c, 0x00000006, 0x0000055d, 0xbeaa37a2, 0x2d8c9eba, + 0x3563b7b9}, + {0xd8b1a02a, 0x00000010, 0x00000387, 0x5017d2fc, 0x503541a5, + 0x071475d0}, + {0x3b96cad2, 0x00000036, 0x00000347, 0x1d2372ae, 0x926cd90b, + 0x54c79d60}, + {0xc94c1ed7, 0x00000005, 0x0000038b, 0x9e9fdb22, 0x144a9178, + 0x4c53eee6}, + {0x1aad454e, 0x00000025, 0x000002b2, 0xc3f6315c, 0x5c7a35b3, + 0x10137a3c}, + {0xa4fec9a6, 0x00000000, 0x000006d6, 0x90be5080, 0xa4107605, + 0xaa9d6c73}, + {0x1bbe71e2, 0x0000001f, 0x000002fd, 0x4e504c3b, 0x284ccaf1, + 0xb63d23e7}, + {0x4201c7e4, 0x00000002, 0x000002b7, 0x7822e3f9, 0x0cc912a9, + 0x7f53e9cf}, + {0x23fddc96, 0x00000003, 0x00000627, 0x8a385125, 0x07767e78, + 0x13c1cd83}, + {0xd82ba25c, 0x00000016, 0x0000063e, 0x98e4148a, 0x283330c9, + 0x49ff5867}, + {0x786f2032, 0x0000002d, 0x0000060f, 0xf201600a, 0xf561bfcd, + 0x8467f211}, + {0xfebe4e1f, 0x0000002a, 0x000004f2, 0x95e51961, 0xfd80dcab, + 0x3f9683b2}, + {0x1a6e0a39, 0x00000008, 0x00000672, 0x8af6c2a5, 0x78dd84cb, + 0x76a3f874}, + {0x56000ab8, 0x0000000e, 0x000000e5, 0x36bacb8f, 0x22ee1f77, + 0x863b702f}, + {0x4717fe0c, 0x00000000, 0x000006ec, 0x8439f342, 0x5c8e03da, + 0xdc6c58ff}, + {0xd5d5d68e, 0x0000003c, 0x000003a3, 0x46fff083, 0x177d1b39, + 0x0622cc95}, + {0xc25dd6c6, 0x00000024, 0x000006c0, 0x5ceb8eb4, 0x892b0d16, + 0xe85605cd}, + {0xe9b11300, 0x00000023, 0x00000683, 0x07a5d59a, 0x6c6a3208, + 0x31da5f06}, + {0x95cd285e, 0x00000001, 0x00000047, 0x7b3a4368, 0x0202c07e, + 0xa1f2e784}, + {0xd9245a25, 0x0000001e, 0x000003a6, 0xd33c1841, 0x1936c0d5, + 0xb07cc616}, + {0x103279db, 0x00000006, 0x0000039b, 0xca09b8a0, 0x77d62892, + 0xbf943b6c}, + {0x1cba3172, 0x00000027, 0x000001c8, 0xcb377194, 0xebe682db, + 0x2c01af1c}, + {0x8f613739, 0x0000000c, 0x000001df, 0xb4b0bc87, 0x7710bd43, + 0x0fe5f56d}, + {0x1c6aa90d, 0x0000001b, 0x0000053c, 0x70559245, 0xda7894ac, + 0xf8943b2d}, + {0xaabe5b93, 0x0000003d, 0x00000715, 0xcdbf42fa, 0x0c3b99e7, + 0xe4d89272}, + {0xf15dd038, 0x00000006, 0x000006db, 0x6e104aea, 0x8d5967f2, + 0x7c2f6bbb}, + {0x584dd49c, 0x00000020, 0x000007bc, 0x36b6cfd6, 0xad4e23b2, + 0xabbf388b}, + {0x5d8c9506, 0x00000020, 0x00000470, 0x4c62378e, 0x31d92640, + 0x1dca1f4e}, + {0xb80d17b0, 0x00000032, 0x00000346, 0x22a5bb88, 0x9a7ec89f, + 0x5c170e23}, + {0xdaf0592e, 0x00000023, 0x000007b0, 0x3cab3f99, 0x9b1fdd99, + 0xc0e9d672}, + {0x4793cc85, 0x0000000d, 0x00000706, 0xe82e04f6, 0xed3db6b7, + 0xc18bdc86}, + {0x82ebf64e, 0x00000009, 0x000007c3, 0x69d590a9, 0x9efa8499, + 0xa874fcdd}, + {0xb18a0319, 0x00000026, 0x000007db, 0x1cf98dcc, 0x8fa9ad6a, + 0x9dc0bb48}, }; #include <linux/time.h> -static int __init crc32_init(void) +static int __init crc32c_test(void) +{ + int i; + int errors = 0; + int bytes = 0; + struct timespec start, stop; + u64 nsec; + unsigned long flags; + + /* keep static to prevent cache warming code from + * getting eliminated by the compiler */ + static u32 crc; + + /* pre-warm the cache */ + for (i = 0; i < 100; i++) { + bytes += 2*test[i].length; + + crc ^= __crc32c_le(test[i].crc, test_buf + + test[i].start, test[i].length); + } + + /* reduce OS noise */ + local_irq_save(flags); + local_irq_disable(); + + getnstimeofday(&start); + for (i = 0; i < 100; i++) { + if (test[i].crc32c_le != __crc32c_le(test[i].crc, test_buf + + test[i].start, test[i].length)) + errors++; + } + getnstimeofday(&stop); + + local_irq_restore(flags); + local_irq_enable(); + + nsec = stop.tv_nsec - start.tv_nsec + + 1000000000 * (stop.tv_sec - start.tv_sec); + + pr_info("crc32c: CRC_LE_BITS = %d\n", CRC_LE_BITS); + + if (errors) + pr_warn("crc32c: %d self tests failed\n", errors); + else { + pr_info("crc32c: self tests passed, processed %d bytes in %lld nsec\n", + bytes, nsec); + } + + return 0; +} + +static int __init crc32_test(void) { int i; int errors = 0; @@ -930,10 +1082,17 @@ static int __init crc32_init(void) return 0; } +static int __init crc32test_init(void) +{ + crc32_test(); + crc32c_test(); + return 0; +} + static void __exit crc32_exit(void) { } -module_init(crc32_init); +module_init(crc32test_init); module_exit(crc32_exit); #endif /* CONFIG_CRC32_SELFTEST */ ^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH 4/4] crc32: Select an algorithm via kconfig 2011-10-04 23:53 [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code Darrick J. Wong ` (2 preceding siblings ...) 2011-10-04 23:54 ` [PATCH 3/4] crc32: Add self-test code for crc32c Darrick J. Wong @ 2011-10-04 23:54 ` Darrick J. Wong 2011-10-08 7:42 ` [PATCH v5.1 " Darrick J. Wong 2011-10-06 20:20 ` [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code Darrick J. Wong 4 siblings, 1 reply; 15+ messages in thread From: Darrick J. Wong @ 2011-10-04 23:54 UTC (permalink / raw) To: Andreas Dilger, Herbert Xu, Theodore Tso, David Miller, Darrick J. Wong Cc: Joakim Tjernlund, Bob Pearson, linux-kernel, Mingming Cao, linux-crypto, linux-fsdevel, linux-ext4 Allow the kernel builder to choose a crc32* algorithm for the kernel. Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> --- lib/Kconfig | 35 +++++++++++++++++++++++++++++++++++ lib/crc32defs.h | 18 ++++++++++++++++++ 2 files changed, 53 insertions(+), 0 deletions(-) diff --git a/lib/Kconfig b/lib/Kconfig index 477be04..9f08b64 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -70,6 +70,41 @@ config CRC32_SELFTEST and crc32_be over byte strings with random alignment and length and computes the total elapsed time and number of bytes processed. +choice + prompt "CRC32 implementation" + depends on CRC32 + default CRC32_SLICEBY8 + +config CRC32_SLICEBY8 + bool "Slice by 8 bytes" + help + Calculate checksum 8 bytes at a time with a clever slicing algorithm. + This is the fastest algorithm, but comes with a 8KiB lookup table. + Most modern processors have enough cache that this shouldn't be + a problem. + + If you don't know which to choose, choose this one. + +config CRC32_SLICEBY4 + bool "Slice by 4 bytes" + help + Calculate checksum 8 bytes at a time with a clever slicing algorithm. + This is reasonably fast, but has a 4KiB lookup table. + +config CRC32_SARWATE + bool "Sarwate's Algorithm (one byte at a time)" + help + Calculate checksum a byte at a time using Sarwate's algorithm. This + is not particularly fast, but has a small 256 byte lookup table. + +config CRC32_BIT + bool "Classic Algorithm (one bit at a time)" + help + Calculate checksum one bit at a time. This is VERY slow, but has + no lookup table. This is provided as a debugging option. + +endchoice + config CRC7 tristate "CRC7 functions" help diff --git a/lib/crc32defs.h b/lib/crc32defs.h index 6fd1917..64cba2c 100644 --- a/lib/crc32defs.h +++ b/lib/crc32defs.h @@ -13,6 +13,24 @@ */ #define CRC32C_POLY_LE 0x82F63B78 +/* Try to choose an implementation variant via Kconfig */ +#ifdef CONFIG_CRC32_SLICEBY8 +# define CRC_LE_BITS 64 +# define CRC_BE_BITS 64 +#endif +#ifdef CONFIG_CRC32_SLICEBY4 +# define CRC_LE_BITS 32 +# define CRC_BE_BITS 32 +#endif +#ifdef CONFIG_CRC32_SARWATE +# define CRC_LE_BITS 8 +# define CRC_BE_BITS 8 +#endif +#ifdef CONFIG_CRC32_BIT +# define CRC_LE_BITS 1 +# define CRC_BE_BITS 1 +#endif + /* * How many bits at a time to use. Valid values are 1, 2, 4, 8, 32 and 64. * For less performance-sensitive, use 4 or 8 to save table size. ^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH v5.1 4/4] crc32: Select an algorithm via kconfig 2011-10-04 23:54 ` [PATCH 4/4] crc32: Select an algorithm via kconfig Darrick J. Wong @ 2011-10-08 7:42 ` Darrick J. Wong 0 siblings, 0 replies; 15+ messages in thread From: Darrick J. Wong @ 2011-10-08 7:42 UTC (permalink / raw) To: Andreas Dilger, Herbert Xu, Theodore Tso, David Miller Cc: Joakim Tjernlund, Bob Pearson, linux-kernel, Mingming Cao, linux-crypto, linux-fsdevel, linux-ext4 Oops, the description of CRC32_SLICEBY4 is a bit screwy. Let's try that again. --- Allow the kernel builder to choose a crc32* algorithm for the kernel. Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> --- lib/Kconfig | 36 ++++++++++++++++++++++++++++++++++++ lib/crc32defs.h | 18 ++++++++++++++++++ 2 files changed, 54 insertions(+), 0 deletions(-) diff --git a/lib/Kconfig b/lib/Kconfig index 477be04..27881d9 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -70,6 +70,42 @@ config CRC32_SELFTEST and crc32_be over byte strings with random alignment and length and computes the total elapsed time and number of bytes processed. +choice + prompt "CRC32 implementation" + depends on CRC32 + default CRC32_SLICEBY8 + +config CRC32_SLICEBY8 + bool "Slice by 8 bytes" + help + Calculate checksum 8 bytes at a time with a clever slicing algorithm. + This is the fastest algorithm, but comes with a 8KiB lookup table. + Most modern processors have enough cache that this shouldn't be + a problem. + + If you don't know which to choose, choose this one. + +config CRC32_SLICEBY4 + bool "Slice by 4 bytes" + help + Calculate checksum 4 bytes at a time with a clever slicing algorithm. + This is a bit slower than slice by 8, but has a smaller 4KiB lookup + table. + +config CRC32_SARWATE + bool "Sarwate's Algorithm (one byte at a time)" + help + Calculate checksum a byte at a time using Sarwate's algorithm. This + is not particularly fast, but has a small 256 byte lookup table. + +config CRC32_BIT + bool "Classic Algorithm (one bit at a time)" + help + Calculate checksum one bit at a time. This is VERY slow, but has + no lookup table. This is provided as a debugging option. + +endchoice + config CRC7 tristate "CRC7 functions" help diff --git a/lib/crc32defs.h b/lib/crc32defs.h index 6fd1917..64cba2c 100644 --- a/lib/crc32defs.h +++ b/lib/crc32defs.h @@ -13,6 +13,24 @@ */ #define CRC32C_POLY_LE 0x82F63B78 +/* Try to choose an implementation variant via Kconfig */ +#ifdef CONFIG_CRC32_SLICEBY8 +# define CRC_LE_BITS 64 +# define CRC_BE_BITS 64 +#endif +#ifdef CONFIG_CRC32_SLICEBY4 +# define CRC_LE_BITS 32 +# define CRC_BE_BITS 32 +#endif +#ifdef CONFIG_CRC32_SARWATE +# define CRC_LE_BITS 8 +# define CRC_BE_BITS 8 +#endif +#ifdef CONFIG_CRC32_BIT +# define CRC_LE_BITS 1 +# define CRC_BE_BITS 1 +#endif + /* * How many bits at a time to use. Valid values are 1, 2, 4, 8, 32 and 64. * For less performance-sensitive, use 4 or 8 to save table size. ^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code 2011-10-04 23:53 [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code Darrick J. Wong ` (3 preceding siblings ...) 2011-10-04 23:54 ` [PATCH 4/4] crc32: Select an algorithm via kconfig Darrick J. Wong @ 2011-10-06 20:20 ` Darrick J. Wong 2011-10-07 7:38 ` Joakim Tjernlund 4 siblings, 1 reply; 15+ messages in thread From: Darrick J. Wong @ 2011-10-06 20:20 UTC (permalink / raw) To: Andreas Dilger, Herbert Xu, Theodore Tso, David Miller Cc: Joakim Tjernlund, Bob Pearson, linux-kernel, Mingming Cao, linux-crypto, linux-fsdevel, linux-ext4 On Tue, Oct 04, 2011 at 04:53:57PM -0700, Darrick J. Wong wrote: > Hi all, > > This patchset (re)uses Bob Pearson's crc32 slice-by-8 code to stamp out a > software crc32c implementation. It requires that all ten of his patches (at > least the ones dated 31 Aug 2011) be applied. It removes the crc32c > implementation in crypto/ in favor of using the stamped-out one in lib/. There > is also a change to Kconfig so that the kernel builder can pick an > implementation best suited for the hardware. > > The motivation for this patchset is that I am working on adding full metadata > checksumming to ext4. As far as performance impact of adding checksumming > goes, I see nearly no change with a standard mail server ffsb simulation. On a > test that involves only file creation and deletion and extent tree writes, I > see a drop of about 50 pcercent with the current kernel crc32c implementation; > this improves to a drop of about 20 percent with the enclosed crc32c code. > > When metadata is usually a small fraction of total IO, this new implementation > doesn't help much because metadata is usually a small fraction of total IO. > However, when we are doing IO that is almost all metadata (such as rm -rf'ing a > tree), then this patch speeds up the operation substantially. > > Incidentally, given that iscsi, sctp, and btrfs also use crc32c, this patchset > should improve their speed as well. I have not yet quantified that, however. As for Mr. Tjernlund's unresolved questions regarding the v4 patch, I have tested this new code on x64/x32/ppc32/ppc64 and it seems to work fine, both with the crc32c selftest and also on a practical level with ext4 metadata checksumming enabled. Updating to Bob's newest calculation code brings about a 10-15% speedup on the ppc64 box. I also see that slice-by-8 is about 20% faster than slice-by-4 on my ppc32 box. I did _not_ see any failures on ppc32 when running an extended ext4+checksum test suite. Details of the ppc32 box: root@dyn9047029101:~# cat /proc/cpuinfo processor : 0 cpu : 740/750 temperature : 45 C (uncalibrated) clock : 500.000000MHz revision : 131.0 (pvr 0008 8300) bogomips : 49.86 total bogomips : 49.86 timebase : 24934966 platform : PowerMac model : PowerMac1,1 machine : PowerMac1,1 motherboard : PowerMac1,1 MacRISC Power Macintosh detected as : 66 (Blue&White G3) pmac flags : 00000000 L2 cache : 1024K unified pmac-generation : NewWorld Memory : 896 MB root@dyn9047029101:~# gcc --version gcc-4.4.real (Ubuntu 4.4.3-4ubuntu5) 4.4.3 Copyright (C) 2009 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. root@dyn9047029101:~# for i in /sys/devices/system/cpu/cpu0/cache/*/*; do echo $i $(cat $i); done /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size 32 /sys/devices/system/cpu/cpu0/cache/index0/level 1 /sys/devices/system/cpu/cpu0/cache/index0/number_of_sets 128 /sys/devices/system/cpu/cpu0/cache/index0/shared_cpu_map 00000000,00000000,00000000,00000001 /sys/devices/system/cpu/cpu0/cache/index0/size 32K /sys/devices/system/cpu/cpu0/cache/index0/type Data /sys/devices/system/cpu/cpu0/cache/index0/ways_of_associativity 8 /sys/devices/system/cpu/cpu0/cache/index1/coherency_line_size 32 /sys/devices/system/cpu/cpu0/cache/index1/level 1 /sys/devices/system/cpu/cpu0/cache/index1/number_of_sets 128 /sys/devices/system/cpu/cpu0/cache/index1/shared_cpu_map 00000000,00000000,00000000,00000001 /sys/devices/system/cpu/cpu0/cache/index1/size 32K /sys/devices/system/cpu/cpu0/cache/index1/type Instruction /sys/devices/system/cpu/cpu0/cache/index1/ways_of_associativity 8 /sys/devices/system/cpu/cpu0/cache/index2/coherency_line_size 128 /sys/devices/system/cpu/cpu0/cache/index2/level 2 /sys/devices/system/cpu/cpu0/cache/index2/number_of_sets 4096 /sys/devices/system/cpu/cpu0/cache/index2/shared_cpu_map 00000000,00000000,00000000,00000001 /sys/devices/system/cpu/cpu0/cache/index2/size 1024K /sys/devices/system/cpu/cpu0/cache/index2/type Unified /sys/devices/system/cpu/cpu0/cache/index2/ways_of_associativity 2 The ppc64 box: root@elm3c7:~# cat /proc/cpuinfo processor : 0 cpu : POWER5+ (gs) clock : 1900.098000MHz revision : 2.0 (pvr 003b 0200) (the rest is omitted for brevity) root@elm3c7:~# gcc --version gcc-4.4.real (Ubuntu 4.4.3-4ubuntu5) 4.4.3 Copyright (C) 2009 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. root@elm3c7:~# for i in /sys/devices/system/cpu/cpu0/cache/*/*; do echo $i $(cat $i); done /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size 128 /sys/devices/system/cpu/cpu0/cache/index0/level 1 /sys/devices/system/cpu/cpu0/cache/index0/number_of_sets 64 /sys/devices/system/cpu/cpu0/cache/index0/shared_cpu_map 00000000,00000000,00000000,00000001 /sys/devices/system/cpu/cpu0/cache/index0/size 32K /sys/devices/system/cpu/cpu0/cache/index0/type Data /sys/devices/system/cpu/cpu0/cache/index0/ways_of_associativity 4 /sys/devices/system/cpu/cpu0/cache/index1/coherency_line_size 128 /sys/devices/system/cpu/cpu0/cache/index1/level 1 /sys/devices/system/cpu/cpu0/cache/index1/number_of_sets 256 /sys/devices/system/cpu/cpu0/cache/index1/shared_cpu_map 00000000,00000000,00000000,00000001 /sys/devices/system/cpu/cpu0/cache/index1/size 64K /sys/devices/system/cpu/cpu0/cache/index1/type Instruction /sys/devices/system/cpu/cpu0/cache/index1/ways_of_associativity 2 /sys/devices/system/cpu/cpu0/cache/index2/coherency_line_size 128 /sys/devices/system/cpu/cpu0/cache/index2/level 2 /sys/devices/system/cpu/cpu0/cache/index2/number_of_sets 1536 /sys/devices/system/cpu/cpu0/cache/index2/shared_cpu_map 00000000,00000000,00000000,00000005 /sys/devices/system/cpu/cpu0/cache/index2/size 1920K /sys/devices/system/cpu/cpu0/cache/index2/type Unified /sys/devices/system/cpu/cpu0/cache/index2/ways_of_associativity 10 /sys/devices/system/cpu/cpu0/cache/index3/coherency_line_size 128 /sys/devices/system/cpu/cpu0/cache/index3/level 3 /sys/devices/system/cpu/cpu0/cache/index3/number_of_sets 1 /sys/devices/system/cpu/cpu0/cache/index3/shared_cpu_map 00000000,00000000,00000000,00000005 /sys/devices/system/cpu/cpu0/cache/index3/size 36864K /sys/devices/system/cpu/cpu0/cache/index3/type Unified /sys/devices/system/cpu/cpu0/cache/index3/ways_of_associativity 0 --D ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code 2011-10-06 20:20 ` [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code Darrick J. Wong @ 2011-10-07 7:38 ` Joakim Tjernlund 0 siblings, 0 replies; 15+ messages in thread From: Joakim Tjernlund @ 2011-10-07 7:38 UTC (permalink / raw) To: djwong Cc: Andreas Dilger, Mingming Cao, David Miller, Herbert Xu, linux-crypto, linux-ext4, linux-fsdevel, linux-kernel, Bob Pearson, Theodore Tso "Darrick J. Wong" <djwong@us.ibm.com> wrote on 2011/10/06 22:20:42: > Subject: Re: [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code > > On Tue, Oct 04, 2011 at 04:53:57PM -0700, Darrick J. Wong wrote: > > Hi all, > > > > This patchset (re)uses Bob Pearson's crc32 slice-by-8 code to stamp out a > > software crc32c implementation. It requires that all ten of his patches (at > > least the ones dated 31 Aug 2011) be applied. It removes the crc32c > > implementation in crypto/ in favor of using the stamped-out one in lib/. There > > is also a change to Kconfig so that the kernel builder can pick an > > implementation best suited for the hardware. > > > > The motivation for this patchset is that I am working on adding full metadata > > checksumming to ext4. As far as performance impact of adding checksumming > > goes, I see nearly no change with a standard mail server ffsb simulation. On a > > test that involves only file creation and deletion and extent tree writes, I > > see a drop of about 50 pcercent with the current kernel crc32c implementation; > > this improves to a drop of about 20 percent with the enclosed crc32c code. > > > > When metadata is usually a small fraction of total IO, this new implementation > > doesn't help much because metadata is usually a small fraction of total IO. > > However, when we are doing IO that is almost all metadata (such as rm -rf'ing a > > tree), then this patch speeds up the operation substantially. > > > > Incidentally, given that iscsi, sctp, and btrfs also use crc32c, this patchset > > should improve their speed as well. I have not yet quantified that, however. > > As for Mr. Tjernlund's unresolved questions regarding the v4 patch, I have > tested this new code on x64/x32/ppc32/ppc64 and it seems to work fine, both > with the crc32c selftest and also on a practical level with ext4 metadata > checksumming enabled. Updating to Bob's newest calculation code brings about a > 10-15% speedup on the ppc64 box. I also see that slice-by-8 is about 20% > faster than slice-by-4 on my ppc32 box. > > I did _not_ see any failures on ppc32 when running an extended ext4+checksum > test suite. Hi Darrick, I finally had some time to look this series over and I like this much better. Thank you for your patience with me :) Acked-By: Joakim Tjernlund <joakim.tjernlund@transmode.se> Jocke ^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2011-11-15 15:38 UTC | newest] Thread overview: 15+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2011-10-04 23:53 [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code Darrick J. Wong 2011-10-04 23:54 ` [PATCH 1/4] crc32: Bolt on crc32c Darrick J. Wong 2011-10-21 12:28 ` Herbert Xu 2011-10-21 16:57 ` Darrick J. Wong 2011-10-21 19:15 ` Herbert Xu 2011-10-26 17:16 ` Darrick J. Wong 2011-10-27 18:32 ` Time for a fresh slice-by-8 crc32.c posting? Darrick J. Wong 2011-11-15 8:48 ` [PATCH 1/4] crc32: Bolt on crc32c Darrick J. Wong 2011-11-15 15:38 ` Bob Pearson 2011-10-04 23:54 ` [PATCH 2/4] crypto: crc32c should use library implementation Darrick J. Wong 2011-10-04 23:54 ` [PATCH 3/4] crc32: Add self-test code for crc32c Darrick J. Wong 2011-10-04 23:54 ` [PATCH 4/4] crc32: Select an algorithm via kconfig Darrick J. Wong 2011-10-08 7:42 ` [PATCH v5.1 " Darrick J. Wong 2011-10-06 20:20 ` [PATCH v5 0/4] crc32c: Add faster algorithm and self-test code Darrick J. Wong 2011-10-07 7:38 ` Joakim Tjernlund
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).