diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Kconfig | 2 | ||||
-rw-r--r-- | lib/asn1_decoder.c | 16 | ||||
-rw-r--r-- | lib/assoc_array.c | 4 | ||||
-rw-r--r-- | lib/dma-debug.c | 4 | ||||
-rw-r--r-- | lib/dump_stack.c | 7 | ||||
-rw-r--r-- | lib/iov_iter.c | 24 | ||||
-rw-r--r-- | lib/klist.c | 6 | ||||
-rw-r--r-- | lib/libcrc32c.c | 1 | ||||
-rw-r--r-- | lib/lz4/lz4defs.h | 21 | ||||
-rw-r--r-- | lib/mpi/mpicoder.c | 60 | ||||
-rw-r--r-- | lib/radix-tree.c | 12 | ||||
-rw-r--r-- | lib/string_helpers.c | 63 | ||||
-rw-r--r-- | lib/test-string_helpers.c | 67 | ||||
-rw-r--r-- | lib/ucs2_string.c | 62 |
14 files changed, 232 insertions, 117 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index f0df318104e7..1a48744253d7 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -210,9 +210,11 @@ config RANDOM32_SELFTEST # compression support is select'ed if needed # config 842_COMPRESS + select CRC32 tristate config 842_DECOMPRESS + select CRC32 tristate config ZLIB_INFLATE diff --git a/lib/asn1_decoder.c b/lib/asn1_decoder.c index 2b3f46c049d4..554522934c44 100644 --- a/lib/asn1_decoder.c +++ b/lib/asn1_decoder.c @@ -74,7 +74,7 @@ next_tag: /* Extract a tag from the data */ tag = data[dp++]; - if (tag == 0) { + if (tag == ASN1_EOC) { /* It appears to be an EOC. */ if (data[dp++] != 0) goto invalid_eoc; @@ -96,10 +96,8 @@ next_tag: /* Extract the length */ len = data[dp++]; - if (len <= 0x7f) { - dp += len; - goto next_tag; - } + if (len <= 0x7f) + goto check_length; if (unlikely(len == ASN1_INDEFINITE_LENGTH)) { /* Indefinite length */ @@ -110,14 +108,18 @@ next_tag: } n = len - 0x80; - if (unlikely(n > sizeof(size_t) - 1)) + if (unlikely(n > sizeof(len) - 1)) goto length_too_long; if (unlikely(n > datalen - dp)) goto data_overrun_error; - for (len = 0; n > 0; n--) { + len = 0; + for (; n > 0; n--) { len <<= 8; len |= data[dp++]; } +check_length: + if (len > datalen - dp) + goto data_overrun_error; dp += len; goto next_tag; diff --git a/lib/assoc_array.c b/lib/assoc_array.c index 03dd576e6773..59fd7c0b119c 100644 --- a/lib/assoc_array.c +++ b/lib/assoc_array.c @@ -524,7 +524,9 @@ static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit, free_slot = i; continue; } - if (ops->compare_object(assoc_array_ptr_to_leaf(ptr), index_key)) { + if (assoc_array_ptr_is_leaf(ptr) && + ops->compare_object(assoc_array_ptr_to_leaf(ptr), + index_key)) { pr_devel("replace in slot %d\n", i); edit->leaf_p = &node->slots[i]; edit->dead_leaf = node->slots[i]; diff --git a/lib/dma-debug.c b/lib/dma-debug.c index d34bd24c2c84..51a76af25c66 100644 --- a/lib/dma-debug.c +++ b/lib/dma-debug.c @@ -657,9 +657,9 @@ static struct dma_debug_entry *dma_entry_alloc(void) spin_lock_irqsave(&free_entries_lock, flags); if (list_empty(&free_entries)) { - pr_err("DMA-API: debugging out of memory - disabling\n"); global_disable = true; spin_unlock_irqrestore(&free_entries_lock, flags); + pr_err("DMA-API: debugging out of memory - disabling\n"); return NULL; } @@ -1181,7 +1181,7 @@ static inline bool overlap(void *addr, unsigned long len, void *start, void *end static void check_for_illegal_area(struct device *dev, void *addr, unsigned long len) { - if (overlap(addr, len, _text, _etext) || + if (overlap(addr, len, _stext, _etext) || overlap(addr, len, __start_rodata, __end_rodata)) err_printk(dev, NULL, "DMA-API: device driver maps memory from kernel text or rodata [addr=%p] [len=%lu]\n", addr, len); } diff --git a/lib/dump_stack.c b/lib/dump_stack.c index 6745c6230db3..c30d07e99dba 100644 --- a/lib/dump_stack.c +++ b/lib/dump_stack.c @@ -25,6 +25,7 @@ static atomic_t dump_lock = ATOMIC_INIT(-1); asmlinkage __visible void dump_stack(void) { + unsigned long flags; int was_locked; int old; int cpu; @@ -33,9 +34,8 @@ asmlinkage __visible void dump_stack(void) * Permit this cpu to perform nested stack dumps while serialising * against other CPUs */ - preempt_disable(); - retry: + local_irq_save(flags); cpu = smp_processor_id(); old = atomic_cmpxchg(&dump_lock, -1, cpu); if (old == -1) { @@ -43,6 +43,7 @@ retry: } else if (old == cpu) { was_locked = 1; } else { + local_irq_restore(flags); cpu_relax(); goto retry; } @@ -52,7 +53,7 @@ retry: if (!was_locked) atomic_set(&dump_lock, -1); - preempt_enable(); + local_irq_restore(flags); } #else asmlinkage __visible void dump_stack(void) diff --git a/lib/iov_iter.c b/lib/iov_iter.c index 75232ad0a5e7..daca582a8ed0 100644 --- a/lib/iov_iter.c +++ b/lib/iov_iter.c @@ -298,33 +298,13 @@ done: } /* - * Fault in the first iovec of the given iov_iter, to a maximum length - * of bytes. Returns 0 on success, or non-zero if the memory could not be - * accessed (ie. because it is an invalid address). - * - * writev-intensive code may want this to prefault several iovecs -- that - * would be possible (callers must not rely on the fact that _only_ the - * first iovec will be faulted with the current implementation). - */ -int iov_iter_fault_in_readable(struct iov_iter *i, size_t bytes) -{ - if (!(i->type & (ITER_BVEC|ITER_KVEC))) { - char __user *buf = i->iov->iov_base + i->iov_offset; - bytes = min(bytes, i->iov->iov_len - i->iov_offset); - return fault_in_pages_readable(buf, bytes); - } - return 0; -} -EXPORT_SYMBOL(iov_iter_fault_in_readable); - -/* * Fault in one or more iovecs of the given iov_iter, to a maximum length of * bytes. For each iovec, fault in each page that constitutes the iovec. * * Return 0 on success, or non-zero if the memory could not be accessed (i.e. * because it is an invalid address). */ -int iov_iter_fault_in_multipages_readable(struct iov_iter *i, size_t bytes) +int iov_iter_fault_in_readable(struct iov_iter *i, size_t bytes) { size_t skip = i->iov_offset; const struct iovec *iov; @@ -341,7 +321,7 @@ int iov_iter_fault_in_multipages_readable(struct iov_iter *i, size_t bytes) } return 0; } -EXPORT_SYMBOL(iov_iter_fault_in_multipages_readable); +EXPORT_SYMBOL(iov_iter_fault_in_readable); void iov_iter_init(struct iov_iter *i, int direction, const struct iovec *iov, unsigned long nr_segs, diff --git a/lib/klist.c b/lib/klist.c index d74cf7a29afd..0507fa5d84c5 100644 --- a/lib/klist.c +++ b/lib/klist.c @@ -282,9 +282,9 @@ void klist_iter_init_node(struct klist *k, struct klist_iter *i, struct klist_node *n) { i->i_klist = k; - i->i_cur = n; - if (n) - kref_get(&n->n_ref); + i->i_cur = NULL; + if (n && kref_get_unless_zero(&n->n_ref)) + i->i_cur = n; } EXPORT_SYMBOL_GPL(klist_iter_init_node); diff --git a/lib/libcrc32c.c b/lib/libcrc32c.c index 6a08ce7d6adc..acf9da449f81 100644 --- a/lib/libcrc32c.c +++ b/lib/libcrc32c.c @@ -74,3 +74,4 @@ module_exit(libcrc32c_mod_fini); MODULE_AUTHOR("Clay Haapala <chaapala@cisco.com>"); MODULE_DESCRIPTION("CRC32c (Castagnoli) calculations"); MODULE_LICENSE("GPL"); +MODULE_SOFTDEP("pre: crc32c"); diff --git a/lib/lz4/lz4defs.h b/lib/lz4/lz4defs.h index abcecdc2d0f2..0710a62ad2f6 100644 --- a/lib/lz4/lz4defs.h +++ b/lib/lz4/lz4defs.h @@ -11,8 +11,7 @@ /* * Detects 64 bits mode */ -#if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) \ - || defined(__ppc64__) || defined(__LP64__)) +#if defined(CONFIG_64BIT) #define LZ4_ARCH64 1 #else #define LZ4_ARCH64 0 @@ -35,6 +34,10 @@ typedef struct _U64_S { u64 v; } U64_S; #define PUT4(s, d) (A32(d) = A32(s)) #define PUT8(s, d) (A64(d) = A64(s)) + +#define LZ4_READ_LITTLEENDIAN_16(d, s, p) \ + (d = s - A16(p)) + #define LZ4_WRITE_LITTLEENDIAN_16(p, v) \ do { \ A16(p) = v; \ @@ -51,10 +54,13 @@ typedef struct _U64_S { u64 v; } U64_S; #define PUT8(s, d) \ put_unaligned(get_unaligned((const u64 *) s), (u64 *) d) -#define LZ4_WRITE_LITTLEENDIAN_16(p, v) \ - do { \ - put_unaligned(v, (u16 *)(p)); \ - p += 2; \ +#define LZ4_READ_LITTLEENDIAN_16(d, s, p) \ + (d = s - get_unaligned_le16(p)) + +#define LZ4_WRITE_LITTLEENDIAN_16(p, v) \ + do { \ + put_unaligned_le16(v, (u16 *)(p)); \ + p += 2; \ } while (0) #endif @@ -140,9 +146,6 @@ typedef struct _U64_S { u64 v; } U64_S; #endif -#define LZ4_READ_LITTLEENDIAN_16(d, s, p) \ - (d = s - get_unaligned_le16(p)) - #define LZ4_WILDCOPY(s, d, e) \ do { \ LZ4_COPYPACKET(s, d); \ diff --git a/lib/mpi/mpicoder.c b/lib/mpi/mpicoder.c index 3db76b8c1115..e37dbf53e226 100644 --- a/lib/mpi/mpicoder.c +++ b/lib/mpi/mpicoder.c @@ -128,6 +128,23 @@ leave: } EXPORT_SYMBOL_GPL(mpi_read_from_buffer); +static int count_lzeros(MPI a) +{ + mpi_limb_t alimb; + int i, lzeros = 0; + + for (i = a->nlimbs - 1; i >= 0; i--) { + alimb = a->d[i]; + if (alimb == 0) { + lzeros += sizeof(mpi_limb_t); + } else { + lzeros += count_leading_zeros(alimb) / 8; + break; + } + } + return lzeros; +} + /** * mpi_read_buffer() - read MPI to a bufer provided by user (msb first) * @@ -146,7 +163,7 @@ int mpi_read_buffer(MPI a, uint8_t *buf, unsigned buf_len, unsigned *nbytes, uint8_t *p; mpi_limb_t alimb; unsigned int n = mpi_get_size(a); - int i, lzeros = 0; + int i, lzeros; if (buf_len < n || !buf || !nbytes) return -EINVAL; @@ -154,14 +171,7 @@ int mpi_read_buffer(MPI a, uint8_t *buf, unsigned buf_len, unsigned *nbytes, if (sign) *sign = a->sign; - p = (void *)&a->d[a->nlimbs] - 1; - - for (i = a->nlimbs * sizeof(alimb) - 1; i >= 0; i--, p--) { - if (!*p) - lzeros++; - else - break; - } + lzeros = count_lzeros(a); p = buf; *nbytes = n - lzeros; @@ -343,7 +353,7 @@ int mpi_write_to_sgl(MPI a, struct scatterlist *sgl, unsigned *nbytes, u8 *p, *p2; mpi_limb_t alimb, alimb2; unsigned int n = mpi_get_size(a); - int i, x, y = 0, lzeros = 0, buf_len; + int i, x, y = 0, lzeros, buf_len; if (!nbytes || *nbytes < n) return -EINVAL; @@ -351,20 +361,15 @@ int mpi_write_to_sgl(MPI a, struct scatterlist *sgl, unsigned *nbytes, if (sign) *sign = a->sign; - p = (void *)&a->d[a->nlimbs] - 1; - - for (i = a->nlimbs * sizeof(alimb) - 1; i >= 0; i--, p--) { - if (!*p) - lzeros++; - else - break; - } + lzeros = count_lzeros(a); *nbytes = n - lzeros; buf_len = sgl->length; p2 = sg_virt(sgl); - for (i = a->nlimbs - 1; i >= 0; i--) { + for (i = a->nlimbs - 1 - lzeros / BYTES_PER_MPI_LIMB, + lzeros %= BYTES_PER_MPI_LIMB; + i >= 0; i--) { alimb = a->d[i]; p = (u8 *)&alimb2; #if BYTES_PER_MPI_LIMB == 4 @@ -385,17 +390,12 @@ int mpi_write_to_sgl(MPI a, struct scatterlist *sgl, unsigned *nbytes, #error please implement for this limb size. #endif if (lzeros > 0) { - if (lzeros >= sizeof(alimb)) { - p -= sizeof(alimb); - continue; - } else { - mpi_limb_t *limb1 = (void *)p - sizeof(alimb); - mpi_limb_t *limb2 = (void *)p - sizeof(alimb) - + lzeros; - *limb1 = *limb2; - p -= lzeros; - y = lzeros; - } + mpi_limb_t *limb1 = (void *)p - sizeof(alimb); + mpi_limb_t *limb2 = (void *)p - sizeof(alimb) + + lzeros; + *limb1 = *limb2; + p -= lzeros; + y = lzeros; lzeros -= sizeof(alimb); } diff --git a/lib/radix-tree.c b/lib/radix-tree.c index fcf5d98574ce..6b79e9026e24 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1019,9 +1019,13 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results, return 0; radix_tree_for_each_slot(slot, root, &iter, first_index) { - results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot)); + results[ret] = rcu_dereference_raw(*slot); if (!results[ret]) continue; + if (radix_tree_is_indirect_ptr(results[ret])) { + slot = radix_tree_iter_retry(&iter); + continue; + } if (++ret == max_items) break; } @@ -1098,9 +1102,13 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, return 0; radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { - results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot)); + results[ret] = rcu_dereference_raw(*slot); if (!results[ret]) continue; + if (radix_tree_is_indirect_ptr(results[ret])) { + slot = radix_tree_iter_retry(&iter); + continue; + } if (++ret == max_items) break; } diff --git a/lib/string_helpers.c b/lib/string_helpers.c index 5939f63d90cd..5c88204b6f1f 100644 --- a/lib/string_helpers.c +++ b/lib/string_helpers.c @@ -43,50 +43,73 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units, [STRING_UNITS_10] = 1000, [STRING_UNITS_2] = 1024, }; - int i, j; - u32 remainder = 0, sf_cap, exp; + static const unsigned int rounding[] = { 500, 50, 5 }; + int i = 0, j; + u32 remainder = 0, sf_cap; char tmp[8]; const char *unit; tmp[0] = '\0'; - i = 0; - if (!size) + + if (blk_size == 0) + size = 0; + if (size == 0) goto out; - while (blk_size >= divisor[units]) { - remainder = do_div(blk_size, divisor[units]); + /* This is Napier's algorithm. Reduce the original block size to + * + * coefficient * divisor[units]^i + * + * we do the reduction so both coefficients are just under 32 bits so + * that multiplying them together won't overflow 64 bits and we keep + * as much precision as possible in the numbers. + * + * Note: it's safe to throw away the remainders here because all the + * precision is in the coefficients. + */ + while (blk_size >> 32) { + do_div(blk_size, divisor[units]); i++; } - exp = divisor[units] / (u32)blk_size; - /* - * size must be strictly greater than exp here to ensure that remainder - * is greater than divisor[units] coming out of the if below. - */ - if (size > exp) { - remainder = do_div(size, divisor[units]); - remainder *= blk_size; + while (size >> 32) { + do_div(size, divisor[units]); i++; - } else { - remainder *= size; } + /* now perform the actual multiplication keeping i as the sum of the + * two logarithms */ size *= blk_size; - size += remainder / divisor[units]; - remainder %= divisor[units]; + /* and logarithmically reduce it until it's just under the divisor */ while (size >= divisor[units]) { remainder = do_div(size, divisor[units]); i++; } + /* work out in j how many digits of precision we need from the + * remainder */ sf_cap = size; for (j = 0; sf_cap*10 < 1000; j++) sf_cap *= 10; - if (j) { + if (units == STRING_UNITS_2) { + /* express the remainder as a decimal. It's currently the + * numerator of a fraction whose denominator is + * divisor[units], which is 1 << 10 for STRING_UNITS_2 */ remainder *= 1000; - remainder /= divisor[units]; + remainder >>= 10; + } + + /* add a 5 to the digit below what will be printed to ensure + * an arithmetical round up and carry it through to size */ + remainder += rounding[j]; + if (remainder >= 1000) { + remainder -= 1000; + size += 1; + } + + if (j) { snprintf(tmp, sizeof(tmp), ".%03u", remainder); tmp[j+1] = '\0'; } diff --git a/lib/test-string_helpers.c b/lib/test-string_helpers.c index 98866a770770..25b5cbfb7615 100644 --- a/lib/test-string_helpers.c +++ b/lib/test-string_helpers.c @@ -327,36 +327,67 @@ out: } #define string_get_size_maxbuf 16 -#define test_string_get_size_one(size, blk_size, units, exp_result) \ +#define test_string_get_size_one(size, blk_size, exp_result10, exp_result2) \ do { \ - BUILD_BUG_ON(sizeof(exp_result) >= string_get_size_maxbuf); \ - __test_string_get_size((size), (blk_size), (units), \ - (exp_result)); \ + BUILD_BUG_ON(sizeof(exp_result10) >= string_get_size_maxbuf); \ + BUILD_BUG_ON(sizeof(exp_result2) >= string_get_size_maxbuf); \ + __test_string_get_size((size), (blk_size), (exp_result10), \ + (exp_result2)); \ } while (0) -static __init void __test_string_get_size(const u64 size, const u64 blk_size, - const enum string_size_units units, - const char *exp_result) +static __init void test_string_get_size_check(const char *units, + const char *exp, + char *res, + const u64 size, + const u64 blk_size) { - char buf[string_get_size_maxbuf]; - - string_get_size(size, blk_size, units, buf, sizeof(buf)); - if (!memcmp(buf, exp_result, strlen(exp_result) + 1)) + if (!memcmp(res, exp, strlen(exp) + 1)) return; - buf[sizeof(buf) - 1] = '\0'; - pr_warn("Test 'test_string_get_size_one' failed!\n"); - pr_warn("string_get_size(size = %llu, blk_size = %llu, units = %d\n", + res[string_get_size_maxbuf - 1] = '\0'; + + pr_warn("Test 'test_string_get_size' failed!\n"); + pr_warn("string_get_size(size = %llu, blk_size = %llu, units = %s)\n", size, blk_size, units); - pr_warn("expected: '%s', got '%s'\n", exp_result, buf); + pr_warn("expected: '%s', got '%s'\n", exp, res); +} + +static __init void __test_string_get_size(const u64 size, const u64 blk_size, + const char *exp_result10, + const char *exp_result2) +{ + char buf10[string_get_size_maxbuf]; + char buf2[string_get_size_maxbuf]; + + string_get_size(size, blk_size, STRING_UNITS_10, buf10, sizeof(buf10)); + string_get_size(size, blk_size, STRING_UNITS_2, buf2, sizeof(buf2)); + + test_string_get_size_check("STRING_UNITS_10", exp_result10, buf10, + size, blk_size); + + test_string_get_size_check("STRING_UNITS_2", exp_result2, buf2, + size, blk_size); } static __init void test_string_get_size(void) { - test_string_get_size_one(16384, 512, STRING_UNITS_2, "8.00 MiB"); - test_string_get_size_one(8192, 4096, STRING_UNITS_10, "32.7 MB"); - test_string_get_size_one(1, 512, STRING_UNITS_10, "512 B"); + /* small values */ + test_string_get_size_one(0, 512, "0 B", "0 B"); + test_string_get_size_one(1, 512, "512 B", "512 B"); + test_string_get_size_one(1100, 1, "1.10 kB", "1.07 KiB"); + + /* normal values */ + test_string_get_size_one(16384, 512, "8.39 MB", "8.00 MiB"); + test_string_get_size_one(500118192, 512, "256 GB", "238 GiB"); + test_string_get_size_one(8192, 4096, "33.6 MB", "32.0 MiB"); + + /* weird block sizes */ + test_string_get_size_one(3000, 1900, "5.70 MB", "5.44 MiB"); + + /* huge values */ + test_string_get_size_one(U64_MAX, 4096, "75.6 ZB", "64.0 ZiB"); + test_string_get_size_one(4096, U64_MAX, "75.6 ZB", "64.0 ZiB"); } static int __init test_string_helpers_init(void) diff --git a/lib/ucs2_string.c b/lib/ucs2_string.c index 6f500ef2301d..f0b323abb4c6 100644 --- a/lib/ucs2_string.c +++ b/lib/ucs2_string.c @@ -49,3 +49,65 @@ ucs2_strncmp(const ucs2_char_t *a, const ucs2_char_t *b, size_t len) } } EXPORT_SYMBOL(ucs2_strncmp); + +unsigned long +ucs2_utf8size(const ucs2_char_t *src) +{ + unsigned long i; + unsigned long j = 0; + + for (i = 0; i < ucs2_strlen(src); i++) { + u16 c = src[i]; + + if (c >= 0x800) + j += 3; + else if (c >= 0x80) + j += 2; + else + j += 1; + } + + return j; +} +EXPORT_SYMBOL(ucs2_utf8size); + +/* + * copy at most maxlength bytes of whole utf8 characters to dest from the + * ucs2 string src. + * + * The return value is the number of characters copied, not including the + * final NUL character. + */ +unsigned long +ucs2_as_utf8(u8 *dest, const ucs2_char_t *src, unsigned long maxlength) +{ + unsigned int i; + unsigned long j = 0; + unsigned long limit = ucs2_strnlen(src, maxlength); + + for (i = 0; maxlength && i < limit; i++) { + u16 c = src[i]; + + if (c >= 0x800) { + if (maxlength < 3) + break; + maxlength -= 3; + dest[j++] = 0xe0 | (c & 0xf000) >> 12; + dest[j++] = 0x80 | (c & 0x0fc0) >> 6; + dest[j++] = 0x80 | (c & 0x003f); + } else if (c >= 0x80) { + if (maxlength < 2) + break; + maxlength -= 2; + dest[j++] = 0xc0 | (c & 0x7c0) >> 6; + dest[j++] = 0x80 | (c & 0x03f); + } else { + maxlength -= 1; + dest[j++] = c & 0x7f; + } + } + if (maxlength) + dest[j] = '\0'; + return j; +} +EXPORT_SYMBOL(ucs2_as_utf8); |