aboutsummaryrefslogtreecommitdiff
path: root/lib
Commit message (Collapse)AuthorAgeFilesLines
* lib/mpi: fix off by one in mpi_read_raw_from_sglStephan Mueller2017-04-111-1/+4
| | | | | | | | | | | The patch fixes the analysis of the input data which contains an off by one. The issue is visible when the SGL contains one byte per SG entry. The code for checking for zero bytes does not operate on the data byte. Signed-off-by: Stephan Mueller <smueller@chronox.de> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
* move count_zeroes.h out of asm-genericChristoph Hellwig2017-04-112-2/+2
| | | | | | | | This header contains a few helpers currenly only used by the mpi implementation, and not default implementation of architecture code. Signed-off-by: Christoph Hellwig <hch@lst.de> Signed-off-by: Arnd Bergmann <arnd@arndb.de>
* lib/mpi: Add mpi sgl helpersTadeusz Struk2017-04-111-0/+196
| | | | | | | Add mpi_read_raw_from_sgl and mpi_write_to_sgl helpers. Signed-off-by: Tadeusz Struk <tadeusz.struk@intel.com> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
* MPI: Fix mpi_read_bufferTadeusz Struk2017-04-111-13/+25
| | | | | | | | Change mpi_read_buffer to return a number without leading zeros so that mpi_read_buffer and mpi_get_buffer return the same thing. Signed-off-by: Tadeusz Struk <tadeusz.struk@intel.com> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
* MPILIB: add mpi_read_buf() and mpi_get_size() helpersTadeusz Struk2017-04-112-22/+71
| | | | | | | | | | Added a mpi_read_buf() helper function to export MPI to a buf provided by the user, and a mpi_get_size() helper, that tells the user how big the buf is. Changed mpi_free to use kzfree instead of kfree because it is used to free crypto keys. Signed-off-by: Tadeusz Struk <tadeusz.struk@intel.com> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
* MPI: MIPS: Fix compilation error with GCC 5.1Jaedon Shin2017-04-111-2/+2
| | | | | | | | | | | | This patch fixes mips compilation error: lib/mpi/generic_mpih-mul1.c: In function 'mpihelp_mul_1': lib/mpi/longlong.h:651:2: error: impossible constraint in 'asm' Signed-off-by: Jaedon Shin <jaedon.shin@gmail.com> Cc: Linux-MIPS <linux-mips@linux-mips.org> Patchwork: https://patchwork.linux-mips.org/patch/10546/ Signed-off-by: Ralf Baechle <ralf@linux-mips.org>
* MPILIB: Fix comparison of negative MPIsRasmus Villemoes2017-04-111-1/+1
| | | | | | | | | | | If u and v both represent negative integers and their limb counts happen to differ, mpi_cmp will always return a positive value - this is obviously bogus. u is smaller than v if and only if it is larger in absolute value. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: David Howells <dhowells@redhat.com> Acked-by: Dmitry Kasatkin <dmitry.kasatkin@gmail.com>
* MPILIB: Fix obvious but harmless typoRasmus Villemoes2017-04-111-1/+1
| | | | | | | The macro MPN_COPY_INCR this occurs in isn't used anywhere. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: David Howells <dhowells@redhat.com>
* MPILIB: Deobfuscate mpi_cmpRasmus Villemoes2017-04-111-5/+3
| | | | | | | | | | | | | The condition preceding 'return 1;' makes my head hurt. At this point, we know that u and v have the same sign; if they are negative, they compare opposite to how their absolute values compare (which mpihelp_cmp found for us), otherwise cmp itself is the answer. Negating cmp is ok since mpihelp_cmp returns {-1,0,1}; -INT_MIN==INT_MIN won't bite us. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: David Howells <dhowells@redhat.com> Acked-by: Dmitry Kasatkin <dmitry.kasatkin@gmail.com>
* MPILIB: add module description and licenseKonstantin Khlebnikov2017-04-111-0/+3
| | | | | | | This patch fixes lack of license, otherwise mpi.ko taints kernel. Signed-off-by: Konstantin Khlebnikov <khlebnikov@openvz.org> Signed-off-by: David Howells <dhowells@redhat.com>
* alpha: Modernize lib/mpi/longlong.hRichard Henderson2017-04-111-10/+7
| | | | | | | | | Remove the compile warning for __udiv_qrnnd not having a prototype. Use the __builtin_alpha_umulh introduced in gcc 4.0. Reviewed-and-Tested-by: Matt Turner <mattst88@gmail.com> Signed-off-by: Matt Turner <mattst88@gmail.com> Signed-off-by: Richard Henderson <rth@twiddle.net>
* lib: add glibc style strchrnul() variantGrant Likely2017-04-111-0/+18
| | | | | | | | | | The strchrnul() variant helpfully returns a the end of the string instead of a NULL if the requested character is not found. This can simplify string parsing code since it doesn't need to expicitly check for a NULL return. If a valid string pointer is passed in, then a valid null terminated string will always come back out. Signed-off-by: Grant Likely <grant.likely@linaro.org>
* lib/bitmap.c: bitmap_parselist can accept string with whitespaces on head or ↵Pan Xinhui2017-04-111-14/+18
| | | | | | | | | | | | | | | | | | | | tail In __bitmap_parselist we can accept whitespaces on head or tail during every parsing procedure. If input has valid ranges, there is no reason to reject the user. For example, bitmap_parselist(" 1-3, 5, ", &mask, nmaskbits). After separating the string, we get " 1-3", " 5", and " ". It's possible and reasonable to accept such string as long as the parsing result is correct. Signed-off-by: Pan Xinhui <xinhuix.pan@intel.com> Cc: Yury Norov <yury.norov@gmail.com> Cc: Chris Metcalf <cmetcalf@ezchip.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Sudeep Holla <sudeep.holla@arm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib/bitmap.c: fix a special string handling bug in __bitmap_parselistPan Xinhui2017-04-111-0/+4
| | | | | | | | | | | | | | If string end with '-', for exapmle, bitmap_parselist("1,0-",&mask, nmaskbits), It is not in a valid pattern, so add a check after loop. Return -EINVAL on such condition. Signed-off-by: Pan Xinhui <xinhuix.pan@intel.com> Cc: Yury Norov <yury.norov@gmail.com> Cc: Chris Metcalf <cmetcalf@ezchip.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Sudeep Holla <sudeep.holla@arm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib/bitmap.c: correct a code style and do some, optimizationPan Xinhui2017-04-111-3/+4
| | | | | | | | | | | | | | We can avoid in-loop incrementation of ndigits. Save current totaldigits to ndigits before loop, and check ndigits against totaldigits after the loop. Signed-off-by: Pan Xinhui <xinhuix.pan@intel.com> Cc: Yury Norov <yury.norov@gmail.com> Cc: Chris Metcalf <cmetcalf@ezchip.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Sudeep Holla <sudeep.holla@arm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib/bitmap.c: bitmap_[empty,full]: remove code duplicationYury Norov2017-04-111-30/+0
| | | | | | | | | | | | | | | bitmap_empty() has its own implementation. But it's clearly as simple as: find_first_bit(src, nbits) == nbits The same is true for 'bitmap_full'. Signed-off-by: Yury Norov <yury.norov@gmail.com> Cc: George Spelvin <linux@horizon.com> Cc: Alexey Klimov <klimov.linux@gmail.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: remove redundant code from __bitmap_shift_leftRasmus Villemoes2017-04-111-7/+2
| | | | | | | | | | | | | The first of these conditionals is completely redundant: If k == lim-1, we must have off==0, so the second conditional will also trigger and then it wouldn't matter if upper had some high bits set. But the second conditional is in fact also redundant, since it only serves to clear out some high-order "don't care" bits of dst, about which no guarantee is made. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: eliminate branch in __bitmap_shift_leftRasmus Villemoes2017-04-111-4/+3
| | | | | | | | | | We can shift the bits from lower and upper into place before assembling dst[k + off]; moving the shift of lower into the branch where we already know that rem is non-zero allows us to remove a conditional. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: change bitmap_shift_left to take unsigned parametersRasmus Villemoes2017-04-111-5/+6
| | | | | | | | | | | | | | | | | | | gcc can generate slightly better code for stuff like "nbits % BITS_PER_LONG" when it knows nbits is not negative. Since negative size bitmaps or shift amounts don't make sense, change these parameters of bitmap_shift_right to unsigned. If off >= lim (which requires shift >= nbits), k is initialized with a large positive value, but since I've let k continue to be signed, the loop will never run and dst will be zeroed as expected. Inside the loop, k is guaranteed to be non-negative, so the fact that it is promoted to unsigned in the various expressions it appears in is harmless. Also use "shift" and "nbits" consistently for the parameter names. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: yet another simplification in __bitmap_shift_rightRasmus Villemoes2017-04-111-4/+4
| | | | | | | | | | If left is 0, we can just let mask be ~0UL, so that anding with it is a no-op. Conveniently, BITMAP_LAST_WORD_MASK provides precisely what we need, and we can eliminate left. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: remove redundant code from __bitmap_shift_rightRasmus Villemoes2017-04-111-2/+0
| | | | | | | | | | | | If the condition k==lim-1 is true, we must have off == 0 (otherwise, k could never become that big). But in that case we have upper == 0 and hence dst[k] == (src[k] & mask) >> rem. Since mask consists of a consecutive range of bits starting from the LSB, anding dst[k] with mask is a no-op. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: eliminate branch in __bitmap_shift_rightRasmus Villemoes2017-04-111-3/+3
| | | | | | | | | | We can shift the bits from lower and upper into place before assembling dst[k]; moving the shift of upper into the branch where we already know that rem is non-zero allows us to remove a conditional. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: change bitmap_shift_right to take unsigned parametersRasmus Villemoes2017-04-111-5/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | I've previously changed the nbits parameter of most bitmap_* functions to unsigned; now it is bitmap_shift_{left,right}'s turn. This alone saves some .text, but while at it I found that there were a few other things one could do. The end result of these seven patches is $ scripts/bloat-o-meter /tmp/bitmap.o.{old,new} add/remove: 0/0 grow/shrink: 0/2 up/down: 0/-328 (-328) function old new delta __bitmap_shift_right 384 226 -158 __bitmap_shift_left 306 136 -170 and less importantly also a smaller stack footprint $ stack-o-meter.pl master bitmap file function old new delta lib/bitmap.o __bitmap_shift_right 24 8 -16 lib/bitmap.o __bitmap_shift_left 24 0 -24 For each pair of 0 <= shift <= nbits <= 256 I've tested the end result with a few randomly filled src buffers (including garbage beyond nbits), in each case verifying that the shift {left,right}-most bits of dst are zero and the remaining nbits-shift bits correspond to src, so I'm fairly confident I didn't screw up. That hasn't stopped me from being wrong before, though. This patch (of 7): gcc can generate slightly better code for stuff like "nbits % BITS_PER_LONG" when it knows nbits is not negative. Since negative size bitmaps or shift amounts don't make sense, change these parameters of bitmap_shift_right to unsigned. The expressions involving "lim - 1" are still ok, since if lim is 0 the loop is never executed. Also use "shift" and "nbits" consistently for the parameter names. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib/bitmap.c: elide bitmap_copy_le on little-endianRasmus Villemoes2017-04-111-0/+2
| | | | | | | | | On little-endian, there's no reason to have an extra, presumably less efficient, way of copying a bitmap. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib/bitmap.c: change prototype of bitmap_copy_leRasmus Villemoes2017-04-111-5/+4
| | | | | | | | | | | | | | | | | Make the prototype of bitmap_copy_le the same as bitmap_copy's. All other bitmap_* functions take unsigned long* parameters; there's no reason this should be special. The only current user is the static inline uwb_mas_bm_copy_le, which already does the void* laundering, so the end users can pass their u8 or __le32 buffers without a cast. Furthermore, this allows us to simply let bitmap_copy_le be an alias for bitmap_copy on little-endian; see next patch. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib/bitmap.c: make the bits parameter of bitmap_remap unsignedRasmus Villemoes2017-04-111-8/+8
| | | | | | | | | Also, rename bits to nbits. Both changes for consistency with other bitmap_* functions. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib/bitmap.c: simplify bitmap_ord_to_posRasmus Villemoes2017-04-111-17/+11
| | | | | | | | | | | | | | Make the return value and the ord and nbits parameters of bitmap_ord_to_pos unsigned. Also, simplify the implementation and as a side effect make the result fully defined, returning nbits for ord >= weight, in analogy with what find_{first,next}_bit does. This is a better sentinel than the former ("unofficial") 0. No current users are affected by this change. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib/bitmap.c: simplify bitmap_pos_to_ordRasmus Villemoes2017-04-111-16/+6
| | | | | | | | | | | | | | | | | | The ordinal of a set bit is simply the number of set bits before it; counting those doesn't need to be done one bit at a time. While at it, update the parameters to unsigned int. It is not completely unthinkable that gcc would see pos as compile-time constant 0 in one of the uses of bitmap_pos_to_ord. Since the static inline frontend bitmap_weight doesn't handle nbits==0 correctly (it would behave exactly as if nbits==BITS_PER_LONG), use __bitmap_weight. Alternatively, the last line could be spelled bitmap_weight(buf, pos+1)-1, but this is simpler. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib/bitmap.c: change parameters of bitmap_fold to unsignedRasmus Villemoes2017-04-111-5/+5
| | | | | | | | | | | | Change the sz and nbits parameters of bitmap_fold to unsigned int for consistency with other bitmap_* functions, and to save another few bytes in the generated code. [akpm@linux-foundation.org: fix kerneldoc] Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Wu Fengguang <fengguang.wu@intel.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib/bitmap.c: update bitmap_onto to unsignedRasmus Villemoes2017-04-111-2/+2
| | | | | | | | | | Change the nbits parameter of bitmap_onto to unsigned int for consistency with other bitmap_* functions. [akpm@linux-foundation.org: coding-style fixes] Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: add missing mask in bitmap_andnotRasmus Villemoes2017-04-111-2/+5
| | | | | | | | | | Apparently, bitmap_andnot is supposed to return whether the new bitmap is empty. But it didn't take potential garbage bits in the last word into account. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: add missing mask in bitmap_andRasmus Villemoes2017-04-111-2/+5
| | | | | | | | | | Apparently, bitmap_and is supposed to return whether the new bitmap is empty. But it didn't take potential garbage bits in the last word into account. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: micro-optimize bitmap_allocate_regionRasmus Villemoes2017-04-111-2/+1
| | | | | | | | | __reg_op(..., REG_OP_ALLOC) always returns 0, so we might as well use that and save an instruction. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: change parameter of bitmap_*_region to unsignedRasmus Villemoes2017-04-111-6/+6
| | | | | | | | | | | | | Changing the pos parameter of __reg_op to unsigned allows the compiler to generate slightly smaller and simpler code. Also update its callers bitmap_*_region to receive and pass unsigned int. The return types of bitmap_find_free_region and bitmap_allocate_region are still int to allow a negative error code to be returned. An int is certainly capable of representing any realistic return value. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: fix typo in kerneldoc for bitmap_pos_to_ordRasmus Villemoes2017-04-111-1/+1
| | | | | | | | | A few lines above, it was stated that positions for non-set bits are mapped to -1, which is obviously also what the code does. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: simplify bitmap_parselistRasmus Villemoes2017-04-111-7/+2
| | | | | | | | | | | We want len to be the index of the first '\n', or the length of the string if there is no newline. This is a good example of the usefulness of strchrnul(). Use that instead, thus eliminating a branch and a call to strlen(). Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: make the start index of bitmap_clear unsignedRasmus Villemoes2017-04-111-5/+5
| | | | | | | | | | | | The compiler can generate slightly smaller and simpler code when it knows that "start" is non-negative. Also, use the names "start" and "len" for the two parameters for consistency with bitmap_set. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: add bitmap_find_next_zero_area_off()Michal Nazarewicz2017-04-111-10/+12
| | | | | | | | | | | | | This commit adds a bitmap_find_next_zero_area_off() function which works like bitmap_find_next_zero_area() function expect it allows an offset to be specified when alignment is checked. This lets caller request a bit such that its number plus the offset is aligned according to the mask. Change-Id: Ib0593cf578ed69ba4c51b1e102a1f8ea1aeb93e8 Signed-off-by: Michal Nazarewicz <mina86@mina86.com> Signed-off-by: Larry Bassel <lbassel@codeaurora.org> (cherry picked from commit 5f2929128ae4db1a6577748c72437f102ed400a5)
* lib: bitmap: make the start index of bitmap_set unsignedRasmus Villemoes2017-04-111-5/+5
| | | | | | | | | | | | The compiler can generate slightly smaller and simpler code when it knows that "start" is non-negative. Also, use the names "start" and "len" for the two parameters in both header file and implementation, instead of the previous mix. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: make nbits parameter of bitmap_weight unsignedRasmus Villemoes2017-04-111-2/+3
| | | | | | | | | | | | | | The compiler can generate slightly smaller and simpler code when it knows that "nbits" is non-negative. Since no-one passes a negative bit-count, this shouldn't affect the semantics. I didn't change the return type, since that might change the semantics of some expression containing a call to bitmap_weight(). Certainly an int is capable of holding the result. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: make nbits parameter of bitmap_subset unsignedRasmus Villemoes2017-04-111-2/+2
| | | | | | | | | | The compiler can generate slightly smaller and simpler code when it knows that "nbits" is non-negative. Since no-one passes a negative bit-count, this shouldn't affect the semantics. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: make nbits parameter of bitmap_intersects unsignedRasmus Villemoes2017-04-111-2/+2
| | | | | | | | | | The compiler can generate slightly smaller and simpler code when it knows that "nbits" is non-negative. Since no-one passes a negative bit-count, this shouldn't affect the semantics. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: make nbits parameter of bitmap_{and,or,xor,andnot} unsignedRasmus Villemoes2017-04-111-12/+12
| | | | | | | | | | | This change is only for consistency with the changes to the other bitmap_* functions; it doesn't change the size of the generated code: inside BITS_TO_LONGS there is a sizeof(long), which causes bits to be interpreted as unsigned anyway. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: remove unnecessary mask from bitmap_complementRasmus Villemoes2017-04-111-1/+1
| | | | | | | | | | Since the extra bits are "don't care", there is no reason to mask the last word to the used bits when complementing. This shaves off yet a few bytes. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: make nbits parameter of bitmap_complement unsignedRasmus Villemoes2017-04-111-2/+2
| | | | | | | | | | The compiler can generate slightly smaller and simpler code when it knows that "nbits" is non-negative. Since no-one passes a negative bit-count, this shouldn't affect the semantics. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: make nbits parameter of bitmap_equal unsignedRasmus Villemoes2017-04-111-2/+2
| | | | | | | | | | The compiler can generate slightly smaller and simpler code when it knows that "nbits" is non-negative. Since no-one passes a negative bit-count, this shouldn't affect the semantics. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: make nbits parameter of bitmap_full unsignedRasmus Villemoes2017-04-111-2/+2
| | | | | | | | | | The compiler can generate slightly smaller and simpler code when it knows that "nbits" is non-negative. Since no-one passes a negative bit-count, this shouldn't affect the semantics. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: bitmap: make nbits parameter of bitmap_empty unsignedRasmus Villemoes2017-04-111-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Many functions in lib/bitmap.c start with an expression such as lim = bits/BITS_PER_LONG. Since bits has type (signed) int, and since gcc cannot know that it is in fact non-negative, it generates worse code than it could. These patches, mostly consisting of changing various parameters to unsigned, gives a slight overall code reduction: add/remove: 1/1 grow/shrink: 8/16 up/down: 251/-414 (-163) function old new delta tick_device_uses_broadcast 335 425 +90 __irq_alloc_descs 498 554 +56 __bitmap_andnot 73 115 +42 __bitmap_and 70 101 +31 bitmap_weight - 11 +11 copy_hugetlb_page_range 752 762 +10 follow_hugetlb_page 846 854 +8 hugetlb_init 1415 1417 +2 hugetlb_nrpages_setup 130 131 +1 hugetlb_add_hstate 377 376 -1 bitmap_allocate_region 82 80 -2 select_task_rq_fair 2202 2191 -11 hweight_long 66 55 -11 __reg_op 230 219 -11 dm_stats_message 2849 2833 -16 bitmap_parselist 92 74 -18 __bitmap_weight 115 97 -18 __bitmap_subset 153 129 -24 __bitmap_full 128 104 -24 __bitmap_empty 120 96 -24 bitmap_set 179 149 -30 bitmap_clear 185 155 -30 __bitmap_equal 136 105 -31 __bitmap_intersects 148 108 -40 __bitmap_complement 109 67 -42 tick_device_setup_broadcast_func.isra 81 - -81 [The increases in __bitmap_and{,not} are due to bug fixes 17/18,18/18. No idea why bitmap_weight suddenly appears.] While 163 bytes treewide is insignificant, I believe the bitmap functions are often called with locks held, so saving even a few cycles might be worth it. While making these changes, I found a few other things that might be worth including. 16,17,18 are actual bug fixes. The rest shouldn't change the behaviour of any of the functions, provided no-one passed negative nbits values. If something should come up, it should be fairly bisectable. A few issues I thought about, but didn't know what to do with: * Many of the functions misbehave if nbits is compile-time 0; the out-of-line functions generally handle 0 correctly. bitmap_fill() is particularly bad, whether the 0 is known at compile time or not. It would probably be nice to add detection of at least compile-time 0 and handle that appropriately. * I didn't change __bitmap_shift_{left,right} to use unsigned because I want to fully understand why the algorithm works before making that change. However, AFAICT, they behave correctly for all (positive) shift amounts. This is not the case for the small_const_nbits versions. If for example nbits = n = BITS_PER_LONG, the shift operators turn into no-ops (at least on x86), so one get *dst = *src, whereas one would expect to get *dst=0. That difference in behaviour is somewhat annoying. This patch (of 18): The compiler can generate slightly smaller and simpler code when it knows that "nbits" is non-negative. Since no-one passes a negative bit-count, this shouldn't affect the semantics. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: radix_tree: tree node interfaceJohannes Weiner2017-04-111-115/+148
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Make struct radix_tree_node part of the public interface and provide API functions to create, look up, and delete whole nodes. Refactor the existing insert, look up, delete functions on top of these new node primitives. This will allow the VM to track and garbage collect page cache radix tree nodes. [sasha.levin@oracle.com: return correct error code on insertion failure] Signed-off-by: Johannes Weiner <hannes@cmpxchg.org> Reviewed-by: Rik van Riel <riel@redhat.com> Cc: Andrea Arcangeli <aarcange@redhat.com> Cc: Bob Liu <bob.liu@oracle.com> Cc: Christoph Hellwig <hch@infradead.org> Cc: Dave Chinner <david@fromorbit.com> Cc: Greg Thelen <gthelen@google.com> Cc: Hugh Dickins <hughd@google.com> Cc: Jan Kara <jack@suse.cz> Cc: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com> Cc: Luigi Semenzato <semenzato@google.com> Cc: Mel Gorman <mgorman@suse.de> Cc: Metin Doslu <metin@citusdata.com> Cc: Michel Lespinasse <walken@google.com> Cc: Ozgun Erdogan <ozgun@citusdata.com> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Roman Gushchin <klamm@yandex-team.ru> Cc: Ryan Mallon <rmallon@gmail.com> Cc: Tejun Heo <tj@kernel.org> Cc: Vlastimil Babka <vbabka@suse.cz> Signed-off-by: Sasha Levin <sasha.levin@oracle.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: radix-tree: add radix_tree_delete_item()Johannes Weiner2017-04-111-4/+27
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Provide a function that does not just delete an entry at a given index, but also allows passing in an expected item. Delete only if that item is still located at the specified index. This is handy when lockless tree traversals want to delete entries as well because they don't have to do an second, locked lookup to verify the slot has not changed under them before deleting the entry. Signed-off-by: Johannes Weiner <hannes@cmpxchg.org> Reviewed-by: Minchan Kim <minchan@kernel.org> Reviewed-by: Rik van Riel <riel@redhat.com> Acked-by: Mel Gorman <mgorman@suse.de> Cc: Andrea Arcangeli <aarcange@redhat.com> Cc: Bob Liu <bob.liu@oracle.com> Cc: Christoph Hellwig <hch@infradead.org> Cc: Dave Chinner <david@fromorbit.com> Cc: Greg Thelen <gthelen@google.com> Cc: Hugh Dickins <hughd@google.com> Cc: Jan Kara <jack@suse.cz> Cc: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com> Cc: Luigi Semenzato <semenzato@google.com> Cc: Metin Doslu <metin@citusdata.com> Cc: Michel Lespinasse <walken@google.com> Cc: Ozgun Erdogan <ozgun@citusdata.com> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Roman Gushchin <klamm@yandex-team.ru> Cc: Ryan Mallon <rmallon@gmail.com> Cc: Tejun Heo <tj@kernel.org> Cc: Vlastimil Babka <vbabka@suse.cz> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
generated by cgit v1.2.3 (git 2.39.1) at 2026-05-14 06:12:59 +0000