summaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2016-03-19 10:05:34 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2016-03-19 10:05:34 -0700
commit1200b6809dfd9d73bc4c7db76d288c35fa4b2ebe (patch)
tree552e03de245cdbd0780ca1215914edc4a26540f7 /lib
parent6b5f04b6cf8ebab9a65d9c0026c650bb2538fd0f (diff)
parentfe30937b65354c7fec244caebbdaae68e28ca797 (diff)
downloadlinux-1200b6809dfd9d73bc4c7db76d288c35fa4b2ebe.tar.gz
linux-1200b6809dfd9d73bc4c7db76d288c35fa4b2ebe.tar.bz2
linux-1200b6809dfd9d73bc4c7db76d288c35fa4b2ebe.zip
Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next
Pull networking updates from David Miller: "Highlights: 1) Support more Realtek wireless chips, from Jes Sorenson. 2) New BPF types for per-cpu hash and arrap maps, from Alexei Starovoitov. 3) Make several TCP sysctls per-namespace, from Nikolay Borisov. 4) Allow the use of SO_REUSEPORT in order to do per-thread processing of incoming TCP/UDP connections. The muxing can be done using a BPF program which hashes the incoming packet. From Craig Gallek. 5) Add a multiplexer for TCP streams, to provide a messaged based interface. BPF programs can be used to determine the message boundaries. From Tom Herbert. 6) Add 802.1AE MACSEC support, from Sabrina Dubroca. 7) Avoid factorial complexity when taking down an inetdev interface with lots of configured addresses. We were doing things like traversing the entire address less for each address removed, and flushing the entire netfilter conntrack table for every address as well. 8) Add and use SKB bulk free infrastructure, from Jesper Brouer. 9) Allow offloading u32 classifiers to hardware, and implement for ixgbe, from John Fastabend. 10) Allow configuring IRQ coalescing parameters on a per-queue basis, from Kan Liang. 11) Extend ethtool so that larger link mode masks can be supported. From David Decotigny. 12) Introduce devlink, which can be used to configure port link types (ethernet vs Infiniband, etc.), port splitting, and switch device level attributes as a whole. From Jiri Pirko. 13) Hardware offload support for flower classifiers, from Amir Vadai. 14) Add "Local Checksum Offload". Basically, for a tunneled packet the checksum of the outer header is 'constant' (because with the checksum field filled into the inner protocol header, the payload of the outer frame checksums to 'zero'), and we can take advantage of that in various ways. From Edward Cree" * git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next: (1548 commits) bonding: fix bond_get_stats() net: bcmgenet: fix dma api length mismatch net/mlx4_core: Fix backward compatibility on VFs phy: mdio-thunder: Fix some Kconfig typos lan78xx: add ndo_get_stats64 lan78xx: handle statistics counter rollover RDS: TCP: Remove unused constant RDS: TCP: Add sysctl tunables for sndbuf/rcvbuf on rds-tcp socket net: smc911x: convert pxa dma to dmaengine team: remove duplicate set of flag IFF_MULTICAST bonding: remove duplicate set of flag IFF_MULTICAST net: fix a comment typo ethernet: micrel: fix some error codes ip_tunnels, bpf: define IP_TUNNEL_OPTS_MAX and use it bpf, dst: add and use dst_tclassid helper bpf: make skb->tc_classid also readable net: mvneta: bm: clarify dependencies cls_bpf: reset class and reuse major in da ldmvsw: Checkpatch sunvnet.c and sunvnet_common.c ldmvsw: Add ldmvsw.c driver code ...
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig.debug8
-rw-r--r--lib/Makefile1
-rw-r--r--lib/bitmap.c89
-rw-r--r--lib/checksum.c4
-rw-r--r--lib/random32.c1
-rw-r--r--lib/test_bitmap.c358
6 files changed, 458 insertions, 3 deletions
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index f28f7fad452f..eed9987bceb9 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1766,6 +1766,14 @@ config TEST_KSTRTOX
config TEST_PRINTF
tristate "Test printf() family of functions at runtime"
+config TEST_BITMAP
+ tristate "Test bitmap_*() family of functions at runtime"
+ default n
+ help
+ Enable this option to test the bitmap functions at boot.
+
+ If unsure, say N.
+
config TEST_RHASHTABLE
tristate "Perform selftest on resizable hash table"
default n
diff --git a/lib/Makefile b/lib/Makefile
index a7c26a41a738..dda4039588b1 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -43,6 +43,7 @@ obj-$(CONFIG_TEST_USER_COPY) += test_user_copy.o
obj-$(CONFIG_TEST_STATIC_KEYS) += test_static_keys.o
obj-$(CONFIG_TEST_STATIC_KEYS) += test_static_key_base.o
obj-$(CONFIG_TEST_PRINTF) += test_printf.o
+obj-$(CONFIG_TEST_BITMAP) += test_bitmap.o
ifeq ($(CONFIG_DEBUG_KOBJECT),y)
CFLAGS_kobject.o += -DDEBUG
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 814814397cce..c66da508cbf7 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -12,6 +12,8 @@
#include <linux/bitmap.h>
#include <linux/bitops.h>
#include <linux/bug.h>
+#include <linux/kernel.h>
+#include <linux/string.h>
#include <asm/page.h>
#include <asm/uaccess.h>
@@ -1060,6 +1062,93 @@ int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
EXPORT_SYMBOL(bitmap_allocate_region);
/**
+ * bitmap_from_u32array - copy the contents of a u32 array of bits to bitmap
+ * @bitmap: array of unsigned longs, the destination bitmap, non NULL
+ * @nbits: number of bits in @bitmap
+ * @buf: array of u32 (in host byte order), the source bitmap, non NULL
+ * @nwords: number of u32 words in @buf
+ *
+ * copy min(nbits, 32*nwords) bits from @buf to @bitmap, remaining
+ * bits between nword and nbits in @bitmap (if any) are cleared. In
+ * last word of @bitmap, the bits beyond nbits (if any) are kept
+ * unchanged.
+ *
+ * Return the number of bits effectively copied.
+ */
+unsigned int
+bitmap_from_u32array(unsigned long *bitmap, unsigned int nbits,
+ const u32 *buf, unsigned int nwords)
+{
+ unsigned int dst_idx, src_idx;
+
+ for (src_idx = dst_idx = 0; dst_idx < BITS_TO_LONGS(nbits); ++dst_idx) {
+ unsigned long part = 0;
+
+ if (src_idx < nwords)
+ part = buf[src_idx++];
+
+#if BITS_PER_LONG == 64
+ if (src_idx < nwords)
+ part |= ((unsigned long) buf[src_idx++]) << 32;
+#endif
+
+ if (dst_idx < nbits/BITS_PER_LONG)
+ bitmap[dst_idx] = part;
+ else {
+ unsigned long mask = BITMAP_LAST_WORD_MASK(nbits);
+
+ bitmap[dst_idx] = (bitmap[dst_idx] & ~mask)
+ | (part & mask);
+ }
+ }
+
+ return min_t(unsigned int, nbits, 32*nwords);
+}
+EXPORT_SYMBOL(bitmap_from_u32array);
+
+/**
+ * bitmap_to_u32array - copy the contents of bitmap to a u32 array of bits
+ * @buf: array of u32 (in host byte order), the dest bitmap, non NULL
+ * @nwords: number of u32 words in @buf
+ * @bitmap: array of unsigned longs, the source bitmap, non NULL
+ * @nbits: number of bits in @bitmap
+ *
+ * copy min(nbits, 32*nwords) bits from @bitmap to @buf. Remaining
+ * bits after nbits in @buf (if any) are cleared.
+ *
+ * Return the number of bits effectively copied.
+ */
+unsigned int
+bitmap_to_u32array(u32 *buf, unsigned int nwords,
+ const unsigned long *bitmap, unsigned int nbits)
+{
+ unsigned int dst_idx = 0, src_idx = 0;
+
+ while (dst_idx < nwords) {
+ unsigned long part = 0;
+
+ if (src_idx < BITS_TO_LONGS(nbits)) {
+ part = bitmap[src_idx];
+ if (src_idx >= nbits/BITS_PER_LONG)
+ part &= BITMAP_LAST_WORD_MASK(nbits);
+ src_idx++;
+ }
+
+ buf[dst_idx++] = part & 0xffffffffUL;
+
+#if BITS_PER_LONG == 64
+ if (dst_idx < nwords) {
+ part >>= 32;
+ buf[dst_idx++] = part & 0xffffffffUL;
+ }
+#endif
+ }
+
+ return min_t(unsigned int, nbits, 32*nwords);
+}
+EXPORT_SYMBOL(bitmap_to_u32array);
+
+/**
* bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
* @dst: destination buffer
* @src: bitmap to copy
diff --git a/lib/checksum.c b/lib/checksum.c
index 8b39e86dbab5..d3ec93f9e5f3 100644
--- a/lib/checksum.c
+++ b/lib/checksum.c
@@ -191,9 +191,7 @@ static inline u32 from64to32(u64 x)
}
__wsum csum_tcpudp_nofold(__be32 saddr, __be32 daddr,
- unsigned short len,
- unsigned short proto,
- __wsum sum)
+ __u32 len, __u8 proto, __wsum sum)
{
unsigned long long s = (__force u32)sum;
diff --git a/lib/random32.c b/lib/random32.c
index 12111910ccd0..510d1ce7d4d2 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -255,6 +255,7 @@ void prandom_seed_full_state(struct rnd_state __percpu *pcpu_state)
prandom_warmup(state);
}
}
+EXPORT_SYMBOL(prandom_seed_full_state);
/*
* Generate better values after random number generator
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
new file mode 100644
index 000000000000..e2cbd43d193c
--- /dev/null
+++ b/lib/test_bitmap.c
@@ -0,0 +1,358 @@
+/*
+ * Test cases for printf facility.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/bitmap.h>
+#include <linux/init.h>
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/printk.h>
+#include <linux/slab.h>
+#include <linux/string.h>
+
+static unsigned total_tests __initdata;
+static unsigned failed_tests __initdata;
+
+static char pbl_buffer[PAGE_SIZE] __initdata;
+
+
+static bool __init
+__check_eq_uint(const char *srcfile, unsigned int line,
+ const unsigned int exp_uint, unsigned int x)
+{
+ if (exp_uint != x) {
+ pr_warn("[%s:%u] expected %u, got %u\n",
+ srcfile, line, exp_uint, x);
+ return false;
+ }
+ return true;
+}
+
+
+static bool __init
+__check_eq_bitmap(const char *srcfile, unsigned int line,
+ const unsigned long *exp_bmap, unsigned int exp_nbits,
+ const unsigned long *bmap, unsigned int nbits)
+{
+ if (exp_nbits != nbits) {
+ pr_warn("[%s:%u] bitmap length mismatch: expected %u, got %u\n",
+ srcfile, line, exp_nbits, nbits);
+ return false;
+ }
+
+ if (!bitmap_equal(exp_bmap, bmap, nbits)) {
+ pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
+ srcfile, line,
+ exp_nbits, exp_bmap, nbits, bmap);
+ return false;
+ }
+ return true;
+}
+
+static bool __init
+__check_eq_pbl(const char *srcfile, unsigned int line,
+ const char *expected_pbl,
+ const unsigned long *bitmap, unsigned int nbits)
+{
+ snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap);
+ if (strcmp(expected_pbl, pbl_buffer)) {
+ pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n",
+ srcfile, line,
+ expected_pbl, pbl_buffer);
+ return false;
+ }
+ return true;
+}
+
+static bool __init
+__check_eq_u32_array(const char *srcfile, unsigned int line,
+ const u32 *exp_arr, unsigned int exp_len,
+ const u32 *arr, unsigned int len)
+{
+ if (exp_len != len) {
+ pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
+ srcfile, line,
+ exp_len, len);
+ return false;
+ }
+
+ if (memcmp(exp_arr, arr, len*sizeof(*arr))) {
+ pr_warn("[%s:%u] array contents differ\n", srcfile, line);
+ print_hex_dump(KERN_WARNING, " exp: ", DUMP_PREFIX_OFFSET,
+ 32, 4, exp_arr, exp_len*sizeof(*exp_arr), false);
+ print_hex_dump(KERN_WARNING, " got: ", DUMP_PREFIX_OFFSET,
+ 32, 4, arr, len*sizeof(*arr), false);
+ return false;
+ }
+
+ return true;
+}
+
+#define __expect_eq(suffix, ...) \
+ ({ \
+ int result = 0; \
+ total_tests++; \
+ if (!__check_eq_ ## suffix(__FILE__, __LINE__, \
+ ##__VA_ARGS__)) { \
+ failed_tests++; \
+ result = 1; \
+ } \
+ result; \
+ })
+
+#define expect_eq_uint(...) __expect_eq(uint, ##__VA_ARGS__)
+#define expect_eq_bitmap(...) __expect_eq(bitmap, ##__VA_ARGS__)
+#define expect_eq_pbl(...) __expect_eq(pbl, ##__VA_ARGS__)
+#define expect_eq_u32_array(...) __expect_eq(u32_array, ##__VA_ARGS__)
+
+static void __init test_zero_fill_copy(void)
+{
+ DECLARE_BITMAP(bmap1, 1024);
+ DECLARE_BITMAP(bmap2, 1024);
+
+ bitmap_zero(bmap1, 1024);
+ bitmap_zero(bmap2, 1024);
+
+ /* single-word bitmaps */
+ expect_eq_pbl("", bmap1, 23);
+
+ bitmap_fill(bmap1, 19);
+ expect_eq_pbl("0-18", bmap1, 1024);
+
+ bitmap_copy(bmap2, bmap1, 23);
+ expect_eq_pbl("0-18", bmap2, 1024);
+
+ bitmap_fill(bmap2, 23);
+ expect_eq_pbl("0-22", bmap2, 1024);
+
+ bitmap_copy(bmap2, bmap1, 23);
+ expect_eq_pbl("0-18", bmap2, 1024);
+
+ bitmap_zero(bmap1, 23);
+ expect_eq_pbl("", bmap1, 1024);
+
+ /* multi-word bitmaps */
+ bitmap_zero(bmap1, 1024);
+ expect_eq_pbl("", bmap1, 1024);
+
+ bitmap_fill(bmap1, 109);
+ expect_eq_pbl("0-108", bmap1, 1024);
+
+ bitmap_copy(bmap2, bmap1, 1024);
+ expect_eq_pbl("0-108", bmap2, 1024);
+
+ bitmap_fill(bmap2, 1024);
+ expect_eq_pbl("0-1023", bmap2, 1024);
+
+ bitmap_copy(bmap2, bmap1, 1024);
+ expect_eq_pbl("0-108", bmap2, 1024);
+
+ /* the following tests assume a 32- or 64-bit arch (even 128b
+ * if we care)
+ */
+
+ bitmap_fill(bmap2, 1024);
+ bitmap_copy(bmap2, bmap1, 109); /* ... but 0-padded til word length */
+ expect_eq_pbl("0-108,128-1023", bmap2, 1024);
+
+ bitmap_fill(bmap2, 1024);
+ bitmap_copy(bmap2, bmap1, 97); /* ... but aligned on word length */
+ expect_eq_pbl("0-108,128-1023", bmap2, 1024);
+
+ bitmap_zero(bmap2, 97); /* ... but 0-padded til word length */
+ expect_eq_pbl("128-1023", bmap2, 1024);
+}
+
+static void __init test_bitmap_u32_array_conversions(void)
+{
+ DECLARE_BITMAP(bmap1, 1024);
+ DECLARE_BITMAP(bmap2, 1024);
+ u32 exp_arr[32], arr[32];
+ unsigned nbits;
+
+ for (nbits = 0 ; nbits < 257 ; ++nbits) {
+ const unsigned int used_u32s = DIV_ROUND_UP(nbits, 32);
+ unsigned int i, rv;
+
+ bitmap_zero(bmap1, nbits);
+ bitmap_set(bmap1, nbits, 1024 - nbits); /* garbage */
+
+ memset(arr, 0xff, sizeof(arr));
+ rv = bitmap_to_u32array(arr, used_u32s, bmap1, nbits);
+ expect_eq_uint(nbits, rv);
+
+ memset(exp_arr, 0xff, sizeof(exp_arr));
+ memset(exp_arr, 0, used_u32s*sizeof(*exp_arr));
+ expect_eq_u32_array(exp_arr, 32, arr, 32);
+
+ bitmap_fill(bmap2, 1024);
+ rv = bitmap_from_u32array(bmap2, nbits, arr, used_u32s);
+ expect_eq_uint(nbits, rv);
+ expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
+
+ for (i = 0 ; i < nbits ; ++i) {
+ /*
+ * test conversion bitmap -> u32[]
+ */
+
+ bitmap_zero(bmap1, 1024);
+ __set_bit(i, bmap1);
+ bitmap_set(bmap1, nbits, 1024 - nbits); /* garbage */
+
+ memset(arr, 0xff, sizeof(arr));
+ rv = bitmap_to_u32array(arr, used_u32s, bmap1, nbits);
+ expect_eq_uint(nbits, rv);
+
+ /* 1st used u32 words contain expected bit set, the
+ * remaining words are left unchanged (0xff)
+ */
+ memset(exp_arr, 0xff, sizeof(exp_arr));
+ memset(exp_arr, 0, used_u32s*sizeof(*exp_arr));
+ exp_arr[i/32] = (1U<<(i%32));
+ expect_eq_u32_array(exp_arr, 32, arr, 32);
+
+
+ /* same, with longer array to fill
+ */
+ memset(arr, 0xff, sizeof(arr));
+ rv = bitmap_to_u32array(arr, 32, bmap1, nbits);
+ expect_eq_uint(nbits, rv);
+
+ /* 1st used u32 words contain expected bit set, the
+ * remaining words are all 0s
+ */
+ memset(exp_arr, 0, sizeof(exp_arr));
+ exp_arr[i/32] = (1U<<(i%32));
+ expect_eq_u32_array(exp_arr, 32, arr, 32);
+
+ /*
+ * test conversion u32[] -> bitmap
+ */
+
+ /* the 1st nbits of bmap2 are identical to
+ * bmap1, the remaining bits of bmap2 are left
+ * unchanged (all 1s)
+ */
+ bitmap_fill(bmap2, 1024);
+ rv = bitmap_from_u32array(bmap2, nbits,
+ exp_arr, used_u32s);
+ expect_eq_uint(nbits, rv);
+
+ expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
+
+ /* same, with more bits to fill
+ */
+ memset(arr, 0xff, sizeof(arr)); /* garbage */
+ memset(arr, 0, used_u32s*sizeof(u32));
+ arr[i/32] = (1U<<(i%32));
+
+ bitmap_fill(bmap2, 1024);
+ rv = bitmap_from_u32array(bmap2, 1024, arr, used_u32s);
+ expect_eq_uint(used_u32s*32, rv);
+
+ /* the 1st nbits of bmap2 are identical to
+ * bmap1, the remaining bits of bmap2 are cleared
+ */
+ bitmap_zero(bmap1, 1024);
+ __set_bit(i, bmap1);
+ expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
+
+
+ /*
+ * test short conversion bitmap -> u32[] (1
+ * word too short)
+ */
+ if (used_u32s > 1) {
+ bitmap_zero(bmap1, 1024);
+ __set_bit(i, bmap1);
+ bitmap_set(bmap1, nbits,
+ 1024 - nbits); /* garbage */
+ memset(arr, 0xff, sizeof(arr));
+
+ rv = bitmap_to_u32array(arr, used_u32s - 1,
+ bmap1, nbits);
+ expect_eq_uint((used_u32s - 1)*32, rv);
+
+ /* 1st used u32 words contain expected
+ * bit set, the remaining words are
+ * left unchanged (0xff)
+ */
+ memset(exp_arr, 0xff, sizeof(exp_arr));
+ memset(exp_arr, 0,
+ (used_u32s-1)*sizeof(*exp_arr));
+ if ((i/32) < (used_u32s - 1))
+ exp_arr[i/32] = (1U<<(i%32));
+ expect_eq_u32_array(exp_arr, 32, arr, 32);
+ }
+
+ /*
+ * test short conversion u32[] -> bitmap (3
+ * bits too short)
+ */
+ if (nbits > 3) {
+ memset(arr, 0xff, sizeof(arr)); /* garbage */
+ memset(arr, 0, used_u32s*sizeof(*arr));
+ arr[i/32] = (1U<<(i%32));
+
+ bitmap_zero(bmap1, 1024);
+ rv = bitmap_from_u32array(bmap1, nbits - 3,
+ arr, used_u32s);
+ expect_eq_uint(nbits - 3, rv);
+
+ /* we are expecting the bit < nbits -
+ * 3 (none otherwise), and the rest of
+ * bmap1 unchanged (0-filled)
+ */
+ bitmap_zero(bmap2, 1024);
+ if (i < nbits - 3)
+ __set_bit(i, bmap2);
+ expect_eq_bitmap(bmap2, 1024, bmap1, 1024);
+
+ /* do the same with bmap1 initially
+ * 1-filled
+ */
+
+ bitmap_fill(bmap1, 1024);
+ rv = bitmap_from_u32array(bmap1, nbits - 3,
+ arr, used_u32s);
+ expect_eq_uint(nbits - 3, rv);
+
+ /* we are expecting the bit < nbits -
+ * 3 (none otherwise), and the rest of
+ * bmap1 unchanged (1-filled)
+ */
+ bitmap_zero(bmap2, 1024);
+ if (i < nbits - 3)
+ __set_bit(i, bmap2);
+ bitmap_set(bmap2, nbits-3, 1024 - nbits + 3);
+ expect_eq_bitmap(bmap2, 1024, bmap1, 1024);
+ }
+ }
+ }
+}
+
+static int __init test_bitmap_init(void)
+{
+ test_zero_fill_copy();
+ test_bitmap_u32_array_conversions();
+
+ if (failed_tests == 0)
+ pr_info("all %u tests passed\n", total_tests);
+ else
+ pr_warn("failed %u out of %u tests\n",
+ failed_tests, total_tests);
+
+ return failed_tests ? -EINVAL : 0;
+}
+
+static void __exit test_bitmap_cleanup(void)
+{
+}
+
+module_init(test_bitmap_init);
+module_exit(test_bitmap_cleanup);
+
+MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
+MODULE_LICENSE("GPL");