summaryrefslogtreecommitdiffstats
path: root/lib/crc32.c
Commit message (Collapse)AuthorAgeFilesLines
* lib/crc32: Make crc32_be weak for arch overrideKevin Bracey2022-01-311-2/+3
| | | | | | | crc32_le and __crc32c_le can be overridden - extend this to crc32_be. Signed-off-by: Kevin Bracey <kevin@bracey.fi> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
* lib/crc32: remove unneeded castsKevin Bracey2022-01-311-6/+3
| | | | | | | | | | Casts were added in commit 8f243af42ade ("sections: fix const sections for crc32 table") to cope with the tables not being const. They are no longer required since commit f5e38b9284e1 ("lib: crc32: constify crc32 lookup table"). Signed-off-by: Kevin Bracey <kevin@bracey.fi> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
* lib/crc32.c: fix trivial typo in preprocessor conditionTobias Jordan2020-10-161-1/+1
| | | | | | | | | | | | | | | | | | Whether crc32_be needs a lookup table is chosen based on CRC_LE_BITS. Obviously, the _be function should be governed by the _BE_ define. This probably never pops up as it's hard to come up with a configuration where CRC_BE_BITS isn't the same as CRC_LE_BITS and as nobody is using bitwise CRC anyway. Fixes: 46c5801eaf86 ("crc32: bolt on crc32c") Signed-off-by: Tobias Jordan <kernel@cdqe.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Cc: Krzysztof Kozlowski <krzk@kernel.org> Cc: Jonathan Corbet <corbet@lwn.net> Cc: Mauro Carvalho Chehab <mchehab+huawei@kernel.org> Link: https://lkml.kernel.org/r/20200923182122.GA3338@agrajag.zerfleddert.de Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* docs: move remaining stuff under Documentation/*.txt to Documentation/stagingMauro Carvalho Chehab2020-06-191-1/+1
| | | | | | | | | | | | | | There are several files that I was unable to find a proper place for them, and 3 ones that are still in plain old text format. Let's place those stuff behind the carpet, as we'd like to keep the root directory clean. We can later discuss and move those into better places. Signed-off-by: Mauro Carvalho Chehab <mchehab+huawei@kernel.org> Link: https://lore.kernel.org/r/11bd0d75e65a874f7c276a0aeab0fe13f3376f5f.1592203650.git.mchehab+huawei@kernel.org Signed-off-by: Jonathan Corbet <corbet@lwn.net>
* lib/crc32.c: mark crc32_le_base/__crc32c_le_base aliases as __pureMiguel Ojeda2019-02-151-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | The upcoming GCC 9 release extends the -Wmissing-attributes warnings (enabled by -Wall) to C and aliases: it warns when particular function attributes are missing in the aliases but not in their target. In particular, it triggers here because crc32_le_base/__crc32c_le_base aren't __pure while their target crc32_le/__crc32c_le are. These aliases are used by architectures as a fallback in accelerated versions of CRC32. See commit 9784d82db3eb ("lib/crc32: make core crc32() routines weak so they can be overridden"). Therefore, being fallbacks, it is likely that even if the aliases were called from C, there wouldn't be any optimizations possible. Currently, the only user is arm64, which calls this from asm. Still, marking the aliases as __pure makes sense and is a good idea for documentation purposes and possible future optimizations, which also silences the warning. Acked-by: Ard Biesheuvel <ard.biesheuvel@linaro.org> Tested-by: Laura Abbott <labbott@redhat.com> Signed-off-by: Miguel Ojeda <miguel.ojeda.sandonis@gmail.com>
* lib/crc32: make core crc32() routines weak so they can be overriddenArd Biesheuvel2018-09-101-4/+7
| | | | | | | | | | | Allow architectures to drop in accelerated CRC32 routines by making the crc32_le/__crc32c_le entry points weak, and exposing non-weak aliases for them that may be used by the accelerated versions as fallbacks in case the instructions they rely upon are not available. Acked-by: Herbert Xu <herbert@gondor.apana.org.au> Signed-off-by: Ard Biesheuvel <ard.biesheuvel@linaro.org> Signed-off-by: Catalin Marinas <catalin.marinas@arm.com>
* lib/crc: Use consistent naming for CRC-32 polynomialsKrzysztof Kozlowski2018-07-271-5/+5
| | | | | | | | Header was defining CRCPOLY_LE/BE and CRC32C_POLY_LE but in fact all of them are CRC-32 polynomials so use consistent naming. Signed-off-by: Krzysztof Kozlowski <krzk@kernel.org> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
* lib/crc: Move polynomial definition to separate headerKrzysztof Kozlowski2018-07-271-0/+1
| | | | | | | | | Allow other drivers and parts of kernel to use the same define for CRC32 polynomial, instead of duplicating it in many places. This code does not bring any functional changes, except moving existing code. Signed-off-by: Krzysztof Kozlowski <krzk@kernel.org> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
* docs: clean up and add rest of CRC functions to kernel-api.rstRandy Dunlap2017-09-261-1/+1
| | | | | | | | | | | | Add the rest of the CRC library functions to kernel-api. - try to clarify crc32() by adding '@' to a function parameter - reorder kernel-api CRC functions to be less random - add more CRC functions to kernel-api - correct the function parameter names in several places Signed-off-by: Randy Dunlap <rdunlap@infradead.org> Signed-off-by: Jonathan Corbet <corbet@lwn.net>
* lib: add module support to crc32 testsGeert Uytterhoeven2017-02-241-824/+0
| | | | | | | | | | | Extract the crc32 test code into its own source file, to allow to compile it either to a loadable module, or builtin into the kernel. Link: http://lkml.kernel.org/r/1483470276-10517-1-git-send-email-geert@linux-m68k.org Signed-off-by: Geert Uytterhoeven <geert@linux-m68k.org> Reviewed-by: Andy Shevchenko <andy.shevchenko@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: use ktime_get_ns() for measurementArnd Bergmann2016-08-021-12/+4
| | | | | | | | | | | | | | | | The crc32 test function measures the elapsed time in nanoseconds, but uses 'struct timespec' for that. We want to remove timespec from the kernel for y2038 compatibility, and ktime_get_ns() also helps make the code simpler here. It is also slightly better to use monontonic time, as we are only interested in the time difference. Link: http://lkml.kernel.org/r/20160617143932.3289626-1-arnd@arndb.de Signed-off-by: Arnd Bergmann <arnd@arndb.de> Cc: "David S . Miller" <davem@davemloft.net> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: crc32: Add some additional __pure annotationsGeorge Spelvin2014-06-251-1/+1
| | | | | | | | In case they help the compiler. Signed-off-by: George Spelvin <linux@horizon.com> Signed-off-by: Daniel Borkmann <dborkman@redhat.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* lib: crc32: Mark test data __initconstGeorge Spelvin2014-06-251-2/+2
| | | | | | | | So it gets discarded after the selftest. Signed-off-by: George Spelvin <linux@horizon.com> Signed-off-by: Daniel Borkmann <dborkman@redhat.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* lib: crc32: Greatly shrink CRC combining codeGeorge Spelvin2014-06-251-77/+70
| | | | | | | | | | | | | | | | | | There's no need for a full 32x32 matrix, when rows before the last are just shifted copies of the rows after them. There's still room for improvement (especially on X86 processors with CRC32 and PCLMUL instructions), but this is a large step in the right direction [which is in particular useful for its current user, namely SCTP checksumming over multiple skb frags[] entries, i.e. in IPVS balancing when other CRC32 offloads are not available]. The internal primitive is now called crc32_generic_shift and takes one less argument; the XOR with crc2 is done in inline wrappers. Signed-off-by: George Spelvin <linux@horizon.com> Signed-off-by: Daniel Borkmann <dborkman@redhat.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* lib/crc32.c: remove unnecessary __constantFabian Frederick2014-06-041-2/+2
| | | | | | | | | Use cpu_to_le32 instead of __constant_cpu_to_le32. Signed-off-by: Fabian Frederick <fabf@skynet.be> Cc: "David S. Miller" <davem@davemloft.net> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: crc32: reduce number of cases for crc32{, c}_combineDaniel Borkmann2013-11-041-2/+2
| | | | | | | | | | | We can safely reduce the number of test cases by a tenth. There is no particular need to run as many as we're running now for crc32{,c}_combine, that gives us still ~8000 tests we're doing if people run kernels with crc selftests enabled which is perfectly fine. Signed-off-by: Daniel Borkmann <dborkman@redhat.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* lib: crc32: conditionally resched when running testcasesDaniel Borkmann2013-11-041-0/+3
| | | | | | | | | | | | | Fengguang reports that when crc32 selftests are running on startup, on some e.g. 32bit systems, we can get a CPU stall like "INFO: rcu_sched self-detected stall on CPU { 0} (t=2101 jiffies g=4294967081 c=4294967080 q=41)". As this is not intended, add a cond_resched() at the end of a test case to fix it. Introduced by efba721f63 ("lib: crc32: add test cases for crc32{, c}_combine routines"). Reported-by: Fengguang Wu <fengguang.wu@intel.com> Signed-off-by: Daniel Borkmann <dborkman@redhat.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* lib: crc32: add test cases for crc32{, c}_combine routinesDaniel Borkmann2013-11-031-0/+72
| | | | | | | | | | | | | | | | | | | | We already have 100 test cases for crcs itself, so split the test buffer with a-prio known checksums, and test crc of two blocks against crc of the whole block for the same results. Output/result with CONFIG_CRC32_SELFTEST=y: [ 2.687095] crc32: CRC_LE_BITS = 64, CRC_BE BITS = 64 [ 2.687097] crc32: self tests passed, processed 225944 bytes in 278177 nsec [ 2.687383] crc32c: CRC_LE_BITS = 64 [ 2.687385] crc32c: self tests passed, processed 225944 bytes in 141708 nsec [ 7.336771] crc32_combine: 113072 self tests passed [ 12.050479] crc32c_combine: 113072 self tests passed [ 17.633089] alg: No test for crc32 (crc32-pclmul) Signed-off-by: Daniel Borkmann <dborkman@redhat.com> Cc: linux-kernel@vger.kernel.org Signed-off-by: David S. Miller <davem@davemloft.net>
* lib: crc32: add functionality to combine two crc32{, c}s in GF(2)Daniel Borkmann2013-11-031-0/+81
| | | | | | | | | | | | | | | | This patch adds a combinator to merge two or more crc32{,c}s into a new one. This is useful for checksum computations of fragmented skbs that use crc32/crc32c as checksums. The arithmetics for combining both in the GF(2) was taken and slightly modified from zlib. Only passing two crcs is insufficient as two crcs and the length of the second piece is needed for merging. The code is made generic, so that only polynomials need to be passed for crc32_le resp. crc32c_le. Signed-off-by: Daniel Borkmann <dborkman@redhat.com> Cc: linux-kernel@vger.kernel.org Signed-off-by: David S. Miller <davem@davemloft.net>
* lib: crc32: clean up spacing in test casesDaniel Borkmann2013-11-031-200/+100
| | | | | | | | | | This is nothing more but a whitepace cleanup, as 80 chars is not a hard but soft limit, and otherwise makes the test cases array really look ugly. So fix it up. Signed-off-by: Daniel Borkmann <dborkman@redhat.com> Cc: linux-kernel@vger.kernel.org Signed-off-by: David S. Miller <davem@davemloft.net>
* lib/crc32: update the comments of crc32_{be,le}_generic()Gu Zheng2013-09-111-6/+11
| | | | | | | [akpm@linux-foundation.org: coding-style fixes] Signed-off-by: Gu Zheng <guz.fnst@cn.fujitsu.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* sections: fix const sections for crc32 tableJoe Mario2012-10-061-3/+6
| | | | | | | | | | | | | | Fix the const sections for the code generated by crc32 table. There's no ro version of the cacheline aligned section, so we cannot put in const data without a conflict Just don't make the crc tables const for now. [ak@linux.intel.com: some fixes and new description] [akpm@linux-foundation.org: checkpatch fixes] Signed-off-by: Joe Mario <jmario@redhat.com> Signed-off-by: Andi Kleen <ak@linux.intel.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib/crc32.c: fix unused variables warningsThiago Rafael Becker2012-07-301-0/+2
| | | | | | | | | | | | | | | | | Variables t4, t5, t6 and t7 are only used when CRC_LE_BITS != 32. Fix the following compilation warnings: lib/crc32.c: In function 'crc32_body': lib/crc32.c:77:55: warning: unused variable 't7' lib/crc32.c:77:41: warning: unused variable 't6' lib/crc32.c:77:27: warning: unused variable 't5' lib/crc32.c:77:13: warning: unused variable 't4' Signed-off-by: Thiago Rafael Becker <trbecker@trbecker.org> Cc: "Darrick J. Wong" <djwong@us.ibm.com> Cc: Bob Pearson <rpearson@systemfabricworks.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: add self-test code for crc32cDarrick J. Wong2012-03-231-102/+261
| | | | | | | | | Add self-test code for crc32c. Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Cc: Bob Pearson <rpearson@systemfabricworks.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: bolt on crc32cDarrick J. Wong2012-03-231-23/+56
| | | | | | | | | | | Reuse the existing crc32 code to stamp out a crc32c implementation. Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Cc: Herbert Xu <herbert@gondor.apana.org.au> Cc: Bob Pearson <rpearson@systemfabricworks.com> Cc: Randy Dunlap <rdunlap@xenotime.net> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: add note about this patchset to crc32.cBob Pearson2012-03-231-0/+4
| | | | | | | | | | Add a comment at the top of crc32.c [djwong@us.ibm.com: Minor changelog tweaks] Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com> Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: optimize loop counter for x86Bob Pearson2012-03-231-0/+13
| | | | | | | | | | | | | | | | | | | | | | | Add two changes that improve the performance of x86 systems 1. replace main loop with incrementing counter this change improves the performance of the selftest by about 5-6% on Nehalem CPUs. The apparent reason is that the compiler can use the loop index to perform an indexed memory access. This is reported to make the performance of PowerPC CPUs to get worse. 2. replace the rem_len loop with incrementing counter this change improves the performance of the selftest, which has more than the usual number of occurances, by about 1-2% on x86 CPUs. In actual work loads the length is most often a multiple of 4 bytes and this code does not get executed as often if at all. Again this change is reported to make the performance of PowerPC get worse. [djwong@us.ibm.com: Minor changelog tweaks] Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com> Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: add slice-by-8 algorithm to existing codeBob Pearson2012-03-231-11/+27
| | | | | | | | | | | | | | | Add slicing-by-8 algorithm to the existing slicing-by-4 algorithm. This consists of: - extend largest BITS size from 32 to 64 - extend tables from tab[4][256] to up to tab[8][256] - Add code for inner loop. [djwong@us.ibm.com: Minor changelog tweaks] Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com> Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: make CRC_*_BITS definition correspond to actual bit countsBob Pearson2012-03-231-3/+14
| | | | | | | | | | | | | | | | | | | | | | | | | crc32.c provides a choice of one of several algorithms for computing the LSB and LSB versions of the CRC32 checksum based on the parameters CRC_LE_BITS and CRC_BE_BITS. In the original version the values 1, 2, 4 and 8 respectively selected versions of the alrogithm that computed the crc 1, 2, 4 and 32 bits as a time. This patch series adds a new version that computes the CRC 64 bits at a time. To make things easier to understand the parameter has been reinterpreted to actually stand for the number of bits processed in each step of the algorithm so that the old value 8 has been replaced with the value 32. This also allows us to add in a widely used crc algorithm that computes the crc 8 bits at a time called the Sarwate algorithm. [djwong@us.ibm.com: Minor changelog tweaks] Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com> Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: fix mixing of endian-specific typesBob Pearson2012-03-231-6/+6
| | | | | | | | | | | | crc32.c in its original version freely mixed u32, __le32 and __be32 types which caused warnings from sparse with __CHECK_ENDIAN__. This patch fixes these by forcing the types to u32. [djwong@us.ibm.com: Minor changelog tweaks] Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com> Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: miscellaneous cleanupsBob Pearson2012-03-231-68/+36
| | | | | | | | | | | | | | | | | | | | | | | | | | Misc cleanup of lib/crc32.c and related files. - remove unnecessary header files. - straighten out some convoluted ifdef's - rewrite some references to 2 dimensional arrays as 1 dimensional arrays to make them correct. I.e. replace tab[i] with tab[0][i]. - a few trivial whitespace changes - fix a warning in gen_crc32tables.c caused by a mismatch in the type of the pointer passed to output table. Since the table is only used at kernel compile time, it is simpler to make the table big enough to hold the largest column size used. One cannot make the column size smaller in output_table because it has to be used by both the le and be tables and they can have different column sizes. [djwong@us.ibm.com: Minor changelog tweaks] Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com> Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: simplify unit test codeBob Pearson2012-03-231-117/+681
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Replace the unit test provided in crc32.c, which doesn't have a makefile and doesn't compile with current headers, with a simpler self test routine that also gives a measure of performance and runs at module init time. The self test option can be enabled through a configuration option CONFIG_CRC32_SELFTEST. The test stresses the pre and post loops and is thus not very realistic since actual uses will likely have addresses and lengths that are at least 4 byte aligned. However, the main loop is long enough so that the performance is dominated by that loop. The expected values for crc32_le and crc32_be were generated with the original version of crc32.c using CRC_BITS_LE = 8 and CRC_BITS_BE = 8. These values were then used to check all the values of the BITS parameters in both the original and new versions. The performance results show some variability from run to run in spite of attempts to both warm the cache and reduce the amount of OS noise by limiting interrutps during the test. To get comparable results and to analyse options wrt performance the best time reported over a small sample of runs has been taken. [djwong@us.ibm.com: Minor changelog tweaks] Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com> Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: move long comment about crc32 fundamentals to Documentation/Bob Pearson2012-03-231-127/+2
| | | | | | | | | | | | | | | | Move a long comment from lib/crc32.c to Documentation/crc32.txt where it will more likely get read. Edited the resulting document to add an explanation of the slicing-by-n algorithm. [djwong@us.ibm.com: minor changelog tweaks] [akpm@linux-foundation.org: fix typo, per George] Signed-off-by: George Spelvin <linux@horizon.com> Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com> Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: remove two instances of trailing whitespacesBob Pearson2012-03-231-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patchset (re)uses Bob Pearson's crc32 slice-by-8 code to stamp out a software crc32c implementation. 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. This latest submission combines Bob's patches from late August 2011 with mine so that they can be one coherent patch set. Please excuse my inability to combine some of the patches; I've been advised to leave Bob's patches alone and build atop them instead. :/ Since the last posting, I've also collected some crc32c test results on a bunch of different x86/powerpc/sparc platforms. The results can be viewed here: http://goo.gl/sgt3i ; the "crc32-kern-le" and "crc32c" columns describe the performance of the kernel's current crc32 and crc32c software implementations. The "crc32c-by8-le" column shows crc32c performance with this patchset applied. I expect crc32 performance to be roughly the same. The two _boost columns at the right side of the spreadsheet shows how much faster the new implementation is over the old one. As you can see, crc32 rises substantially, and crc32c experiences a huge increase. This patch: - remove trailing whitespace from lib/crc32.c - remove trailing whitespace from lib/crc32defs.h [djwong@us.ibm.com: changelog tweaks] Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com> Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: optimize inner loopJoakim Tjernlund2012-01-101-10/+11
| | | | | | | | | | | | Taking a pointer reference to each row in the crc table matrix, one can reduce the inner loop with a few insn's Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se> Cc: Bob Pearson <rpearson@systemfabricworks.com> Cc: Frank Zago <fzago@systemfabricworks.com> Cc: Eric Dumazet <eric.dumazet@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* atomic: use <linux/atomic.h>Arun Sharma2011-07-261-1/+1
| | | | | | | | | | | | | | This allows us to move duplicated code in <asm/atomic.h> (atomic_inc_not_zero() for now) to <linux/atomic.h> Signed-off-by: Arun Sharma <asharma@fb.com> Reviewed-by: Eric Dumazet <eric.dumazet@gmail.com> Cc: Ingo Molnar <mingo@elte.hu> Cc: David Miller <davem@davemloft.net> Cc: Eric Dumazet <eric.dumazet@gmail.com> Acked-by: Mike Frysinger <vapier@gentoo.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* revert "crc32: use __BYTE_ORDER macro for endian detection"Andrew Morton2010-05-261-1/+1
| | | | | | | | | | It doesn't work on big-endian - those architectures don't define __LITTLE_ENDIAN. Cc: Joakim Tjernlund <joakim.tjernlund@transmode.se> Reported-by: Stephen Rothwell <sfr@canb.auug.org.au> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: use __BYTE_ORDER macro for endian detection.Joakim Tjernlund2010-05-251-1/+1
| | | | | | | | | Since crc32.c contains a nifty test program that can be executed in user space, make sure endian detection works reliably in user space too. Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: major optimizationJoakim Tjernlund2010-05-251-9/+15
| | | | | | | | | | | | | | Precompute more crc32 values(0xcc00, 0xcc0000 and 0xcc000000) into tables. This increases the table size from 1KB to 4KB but the performance benfit makes it worth it: 28% faster on MPC8321, 266 MHz 2x faster on Core 2 Duo, 3.1GHz [akpm@linux-foundation.org: coding-style fixes] Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* include cleanup: Update gfp.h and slab.h includes to prepare for breaking ↵Tejun Heo2010-03-301-1/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | implicit slab.h inclusion from percpu.h percpu.h is included by sched.h and module.h and thus ends up being included when building most .c files. percpu.h includes slab.h which in turn includes gfp.h making everything defined by the two files universally available and complicating inclusion dependencies. percpu.h -> slab.h dependency is about to be removed. Prepare for this change by updating users of gfp and slab facilities include those headers directly instead of assuming availability. As this conversion needs to touch large number of source files, the following script is used as the basis of conversion. http://userweb.kernel.org/~tj/misc/slabh-sweep.py The script does the followings. * Scan files for gfp and slab usages and update includes such that only the necessary includes are there. ie. if only gfp is used, gfp.h, if slab is used, slab.h. * When the script inserts a new include, it looks at the include blocks and try to put the new include such that its order conforms to its surrounding. It's put in the include block which contains core kernel includes, in the same order that the rest are ordered - alphabetical, Christmas tree, rev-Xmas-tree or at the end if there doesn't seem to be any matching order. * If the script can't find a place to put a new include (mostly because the file doesn't have fitting include block), it prints out an error message indicating which .h file needs to be added to the file. The conversion was done in the following steps. 1. The initial automatic conversion of all .c files updated slightly over 4000 files, deleting around 700 includes and adding ~480 gfp.h and ~3000 slab.h inclusions. The script emitted errors for ~400 files. 2. Each error was manually checked. Some didn't need the inclusion, some needed manual addition while adding it to implementation .h or embedding .c file was more appropriate for others. This step added inclusions to around 150 files. 3. The script was run again and the output was compared to the edits from #2 to make sure no file was left behind. 4. Several build tests were done and a couple of problems were fixed. e.g. lib/decompress_*.c used malloc/free() wrappers around slab APIs requiring slab.h to be added manually. 5. The script was run on all .h files but without automatically editing them as sprinkling gfp.h and slab.h inclusions around .h files could easily lead to inclusion dependency hell. Most gfp.h inclusion directives were ignored as stuff from gfp.h was usually wildly available and often used in preprocessor macros. Each slab.h inclusion directive was examined and added manually as necessary. 6. percpu.h was updated not to include slab.h. 7. Build test were done on the following configurations and failures were fixed. CONFIG_GCOV_KERNEL was turned off for all tests (as my distributed build env didn't work with gcov compiles) and a few more options had to be turned off depending on archs to make things build (like ipr on powerpc/64 which failed due to missing writeq). * x86 and x86_64 UP and SMP allmodconfig and a custom test config. * powerpc and powerpc64 SMP allmodconfig * sparc and sparc64 SMP allmodconfig * ia64 SMP allmodconfig * s390 SMP allmodconfig * alpha SMP allmodconfig * um on x86_64 SMP allmodconfig 8. percpu.h modifications were reverted so that it could be applied as a separate patch and serve as bisection point. Given the fact that I had only a couple of failures from tests on step 6, I'm fairly confident about the coverage of this conversion patch. If there is a breakage, it's likely to be something in one of the arch headers which should be easily discoverable easily on most builds of the specific arch. Signed-off-by: Tejun Heo <tj@kernel.org> Guess-its-ok-by: Christoph Lameter <cl@linux-foundation.org> Cc: Ingo Molnar <mingo@redhat.com> Cc: Lee Schermerhorn <Lee.Schermerhorn@hp.com>
* crc32: some minor cleanupsJoakim Tjernlund2010-03-061-16/+14
| | | | | | Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* crc32: minor optimizations and cleanupJoakim Tjernlund2009-12-151-77/+44
| | | | | | | | | | Move common crc body to new function crc32_body() cleaup and micro optimize crc32_body for speed and less size. [akpm@linux-foundation.org: coding-style fixes] Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib/: Spelling fixesJoe Perches2008-02-031-1/+1
| | | | | Signed-off-by: Joe Perches <joe@perches.com> Signed-off-by: Adrian Bunk <bunk@kernel.org>
* Replace __attribute_pure__ with __pureRalf Baechle2007-10-181-6/+6
| | | | | | | | | | | | | | | To be consistent with the use of attributes in the rest of the kernel replace all use of __attribute_pure__ with __pure and delete the definition of __attribute_pure__. Signed-off-by: Ralf Baechle <ralf@linux-mips.org> Cc: Russell King <rmk@arm.linux.org.uk> Acked-by: Mauro Carvalho Chehab <mchehab@infradead.org> Cc: Bryan Wu <bryan.wu@analog.com> Cc: Paul Mackerras <paulus@samba.org> Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* [PATCH] crc32: replace bitreverse by bitrev32Akinobu Mita2006-12-081-23/+5
| | | | | | | | | | | This patch replaces bitreverse() by bitrev32. The only users of bitreverse() are crc32 itself and via-velocity. Cc: Jeff Garzik <jgarzik@pobox.com> Cc: Matt Domsch <Matt_Domsch@dell.com> Signed-off-by: Akinobu Mita <akinobu.mita@gmail.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* [PATCH] kernel-doc for lib/crc*.cRandy Dunlap2006-06-251-32/+22
| | | | | | | | | Make kernel-doc corrections & additions to lib/crc*.c. Add crc functions to kernel-api.tmpl in DocBook. Signed-off-by: Randy Dunlap <rdunlap@xenotime.net> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* [PATCH] crc32.c typo fixDominik Hackl2005-08-071-1/+1
| | | | | | | | | This patch fixes a typo in lib/crc32.c which results in incorrect debug output. Signed-off-by: Dominik Hackl <dominik@hackl.dhs.org> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* Linux-2.6.12-rc2v2.6.12-rc2Linus Torvalds2005-04-161-0/+529
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!