aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2015-09-03 11:08:17 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2015-09-03 11:08:17 -0400
commitdd5cdb48edfd34401799056a9acf61078d773f90 (patch)
tree8e251fb4a4c196540fe9b6a6d8b13275f93a057c /lib
parent1e1a4e8f439113b7820bc7150569f685e1cc2b43 (diff)
parent62da98656b62a5ca57f22263705175af8ded5aa1 (diff)
Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next
Pull networking updates from David Miller: "Another merge window, another set of networking changes. I've heard rumblings that the lightweight tunnels infrastructure has been voted networking change of the year. But what do I know? 1) Add conntrack support to openvswitch, from Joe Stringer. 2) Initial support for VRF (Virtual Routing and Forwarding), which allows the segmentation of routing paths without using multiple devices. There are some semantic kinks to work out still, but this is a reasonably strong foundation. From David Ahern. 3) Remove spinlock fro act_bpf fast path, from Alexei Starovoitov. 4) Ignore route nexthops with a link down state in ipv6, just like ipv4. From Andy Gospodarek. 5) Remove spinlock from fast path of act_gact and act_mirred, from Eric Dumazet. 6) Document the DSA layer, from Florian Fainelli. 7) Add netconsole support to bcmgenet, systemport, and DSA. Also from Florian Fainelli. 8) Add Mellanox Switch Driver and core infrastructure, from Jiri Pirko. 9) Add support for "light weight tunnels", which allow for encapsulation and decapsulation without bearing the overhead of a full blown netdevice. From Thomas Graf, Jiri Benc, and a cast of others. 10) Add Identifier Locator Addressing support for ipv6, from Tom Herbert. 11) Support fragmented SKBs in iwlwifi, from Johannes Berg. 12) Allow perf PMUs to be accessed from eBPF programs, from Kaixu Xia. 13) Add BQL support to 3c59x driver, from Loganaden Velvindron. 14) Stop using a zero TX queue length to mean that a device shouldn't have a qdisc attached, use an explicit flag instead. From Phil Sutter. 15) Use generic geneve netdevice infrastructure in openvswitch, from Pravin B Shelar. 16) Add infrastructure to avoid re-forwarding a packet in software that was already forwarded by a hardware switch. From Scott Feldman. 17) Allow AF_PACKET fanout function to be implemented in a bpf program, from Willem de Bruijn" * git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next: (1458 commits) netfilter: nf_conntrack: make nf_ct_zone_dflt built-in netfilter: nf_dup{4, 6}: fix build error when nf_conntrack disabled net: fec: clear receive interrupts before processing a packet ipv6: fix exthdrs offload registration in out_rt path xen-netback: add support for multicast control bgmac: Update fixed_phy_register() sock, diag: fix panic in sock_diag_put_filterinfo flow_dissector: Use 'const' where possible. flow_dissector: Fix function argument ordering dependency ixgbe: Resolve "initialized field overwritten" warnings ixgbe: Remove bimodal SR-IOV disabling ixgbe: Add support for reporting 2.5G link speed ixgbe: fix bounds checking in ixgbe_setup_tc for 82598 ixgbe: support for ethtool set_rxfh ixgbe: Avoid needless PHY access on copper phys ixgbe: cleanup to use cached mask value ixgbe: Remove second instance of lan_id variable ixgbe: use kzalloc for allocating one thing flow: Move __get_hash_from_flowi{4,6} into flow_dissector.c ixgbe: Remove unused PCI bus types ...
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig10
-rw-r--r--lib/Makefile2
-rw-r--r--lib/average.c64
-rw-r--r--lib/test_bpf.c817
-rw-r--r--lib/test_rhashtable.c163
5 files changed, 975 insertions, 81 deletions
diff --git a/lib/Kconfig b/lib/Kconfig
index dc516164415a..a16555281d53 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -460,16 +460,6 @@ config ARCH_HAS_ATOMIC64_DEC_IF_POSITIVE
460config LRU_CACHE 460config LRU_CACHE
461 tristate 461 tristate
462 462
463config AVERAGE
464 bool "Averaging functions"
465 help
466 This option is provided for the case where no in-kernel-tree
467 modules require averaging functions, but a module built outside
468 the kernel tree does. Such modules that use library averaging
469 functions require Y here.
470
471 If unsure, say N.
472
473config CLZ_TAB 463config CLZ_TAB
474 bool 464 bool
475 465
diff --git a/lib/Makefile b/lib/Makefile
index 2ee6ea2e9b08..f2610061bfa4 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -138,8 +138,6 @@ obj-$(CONFIG_GENERIC_ATOMIC64) += atomic64.o
138 138
139obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o 139obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o
140 140
141obj-$(CONFIG_AVERAGE) += average.o
142
143obj-$(CONFIG_CPU_RMAP) += cpu_rmap.o 141obj-$(CONFIG_CPU_RMAP) += cpu_rmap.o
144 142
145obj-$(CONFIG_CORDIC) += cordic.o 143obj-$(CONFIG_CORDIC) += cordic.o
diff --git a/lib/average.c b/lib/average.c
deleted file mode 100644
index 114d1beae0c7..000000000000
--- a/lib/average.c
+++ /dev/null
@@ -1,64 +0,0 @@
1/*
2 * lib/average.c
3 *
4 * This source code is licensed under the GNU General Public License,
5 * Version 2. See the file COPYING for more details.
6 */
7
8#include <linux/export.h>
9#include <linux/average.h>
10#include <linux/kernel.h>
11#include <linux/bug.h>
12#include <linux/log2.h>
13
14/**
15 * DOC: Exponentially Weighted Moving Average (EWMA)
16 *
17 * These are generic functions for calculating Exponentially Weighted Moving
18 * Averages (EWMA). We keep a structure with the EWMA parameters and a scaled
19 * up internal representation of the average value to prevent rounding errors.
20 * The factor for scaling up and the exponential weight (or decay rate) have to
21 * be specified thru the init fuction. The structure should not be accessed
22 * directly but only thru the helper functions.
23 */
24
25/**
26 * ewma_init() - Initialize EWMA parameters
27 * @avg: Average structure
28 * @factor: Factor to use for the scaled up internal value. The maximum value
29 * of averages can be ULONG_MAX/(factor*weight). For performance reasons
30 * factor has to be a power of 2.
31 * @weight: Exponential weight, or decay rate. This defines how fast the
32 * influence of older values decreases. For performance reasons weight has
33 * to be a power of 2.
34 *
35 * Initialize the EWMA parameters for a given struct ewma @avg.
36 */
37void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight)
38{
39 WARN_ON(!is_power_of_2(weight) || !is_power_of_2(factor));
40
41 avg->weight = ilog2(weight);
42 avg->factor = ilog2(factor);
43 avg->internal = 0;
44}
45EXPORT_SYMBOL(ewma_init);
46
47/**
48 * ewma_add() - Exponentially weighted moving average (EWMA)
49 * @avg: Average structure
50 * @val: Current value
51 *
52 * Add a sample to the average.
53 */
54struct ewma *ewma_add(struct ewma *avg, unsigned long val)
55{
56 unsigned long internal = ACCESS_ONCE(avg->internal);
57
58 ACCESS_ONCE(avg->internal) = internal ?
59 (((internal << avg->weight) - internal) +
60 (val << avg->factor)) >> avg->weight :
61 (val << avg->factor);
62 return avg;
63}
64EXPORT_SYMBOL(ewma_add);
diff --git a/lib/test_bpf.c b/lib/test_bpf.c
index 7f58c735d745..d1377390b3ad 100644
--- a/lib/test_bpf.c
+++ b/lib/test_bpf.c
@@ -18,10 +18,12 @@
18#include <linux/init.h> 18#include <linux/init.h>
19#include <linux/module.h> 19#include <linux/module.h>
20#include <linux/filter.h> 20#include <linux/filter.h>
21#include <linux/bpf.h>
21#include <linux/skbuff.h> 22#include <linux/skbuff.h>
22#include <linux/netdevice.h> 23#include <linux/netdevice.h>
23#include <linux/if_vlan.h> 24#include <linux/if_vlan.h>
24#include <linux/random.h> 25#include <linux/random.h>
26#include <linux/highmem.h>
25 27
26/* General test specific settings */ 28/* General test specific settings */
27#define MAX_SUBTESTS 3 29#define MAX_SUBTESTS 3
@@ -55,6 +57,7 @@
55/* Flags that can be passed to test cases */ 57/* Flags that can be passed to test cases */
56#define FLAG_NO_DATA BIT(0) 58#define FLAG_NO_DATA BIT(0)
57#define FLAG_EXPECTED_FAIL BIT(1) 59#define FLAG_EXPECTED_FAIL BIT(1)
60#define FLAG_SKB_FRAG BIT(2)
58 61
59enum { 62enum {
60 CLASSIC = BIT(6), /* Old BPF instructions only. */ 63 CLASSIC = BIT(6), /* Old BPF instructions only. */
@@ -80,6 +83,7 @@ struct bpf_test {
80 __u32 result; 83 __u32 result;
81 } test[MAX_SUBTESTS]; 84 } test[MAX_SUBTESTS];
82 int (*fill_helper)(struct bpf_test *self); 85 int (*fill_helper)(struct bpf_test *self);
86 __u8 frag_data[MAX_DATA];
83}; 87};
84 88
85/* Large test cases need separate allocation and fill handler. */ 89/* Large test cases need separate allocation and fill handler. */
@@ -355,6 +359,81 @@ static int bpf_fill_ja(struct bpf_test *self)
355 return __bpf_fill_ja(self, 12, 9); 359 return __bpf_fill_ja(self, 12, 9);
356} 360}
357 361
362static int bpf_fill_ld_abs_get_processor_id(struct bpf_test *self)
363{
364 unsigned int len = BPF_MAXINSNS;
365 struct sock_filter *insn;
366 int i;
367
368 insn = kmalloc_array(len, sizeof(*insn), GFP_KERNEL);
369 if (!insn)
370 return -ENOMEM;
371
372 for (i = 0; i < len - 1; i += 2) {
373 insn[i] = __BPF_STMT(BPF_LD | BPF_B | BPF_ABS, 0);
374 insn[i + 1] = __BPF_STMT(BPF_LD | BPF_W | BPF_ABS,
375 SKF_AD_OFF + SKF_AD_CPU);
376 }
377
378 insn[len - 1] = __BPF_STMT(BPF_RET | BPF_K, 0xbee);
379
380 self->u.ptr.insns = insn;
381 self->u.ptr.len = len;
382
383 return 0;
384}
385
386#define PUSH_CNT 68
387/* test: {skb->data[0], vlan_push} x 68 + {skb->data[0], vlan_pop} x 68 */
388static int bpf_fill_ld_abs_vlan_push_pop(struct bpf_test *self)
389{
390 unsigned int len = BPF_MAXINSNS;
391 struct bpf_insn *insn;
392 int i = 0, j, k = 0;
393
394 insn = kmalloc_array(len, sizeof(*insn), GFP_KERNEL);
395 if (!insn)
396 return -ENOMEM;
397
398 insn[i++] = BPF_MOV64_REG(R6, R1);
399loop:
400 for (j = 0; j < PUSH_CNT; j++) {
401 insn[i++] = BPF_LD_ABS(BPF_B, 0);
402 insn[i] = BPF_JMP_IMM(BPF_JNE, R0, 0x34, len - i - 2);
403 i++;
404 insn[i++] = BPF_MOV64_REG(R1, R6);
405 insn[i++] = BPF_MOV64_IMM(R2, 1);
406 insn[i++] = BPF_MOV64_IMM(R3, 2);
407 insn[i++] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
408 bpf_skb_vlan_push_proto.func - __bpf_call_base);
409 insn[i] = BPF_JMP_IMM(BPF_JNE, R0, 0, len - i - 2);
410 i++;
411 }
412
413 for (j = 0; j < PUSH_CNT; j++) {
414 insn[i++] = BPF_LD_ABS(BPF_B, 0);
415 insn[i] = BPF_JMP_IMM(BPF_JNE, R0, 0x34, len - i - 2);
416 i++;
417 insn[i++] = BPF_MOV64_REG(R1, R6);
418 insn[i++] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
419 bpf_skb_vlan_pop_proto.func - __bpf_call_base);
420 insn[i] = BPF_JMP_IMM(BPF_JNE, R0, 0, len - i - 2);
421 i++;
422 }
423 if (++k < 5)
424 goto loop;
425
426 for (; i < len - 1; i++)
427 insn[i] = BPF_ALU32_IMM(BPF_MOV, R0, 0xbef);
428
429 insn[len - 1] = BPF_EXIT_INSN();
430
431 self->u.ptr.insns = insn;
432 self->u.ptr.len = len;
433
434 return 0;
435}
436
358static struct bpf_test tests[] = { 437static struct bpf_test tests[] = {
359 { 438 {
360 "TAX", 439 "TAX",
@@ -3674,6 +3753,9 @@ static struct bpf_test tests[] = {
3674 .u.insns_int = { 3753 .u.insns_int = {
3675 BPF_LD_IMM64(R0, 0x0123456789abcdefLL), 3754 BPF_LD_IMM64(R0, 0x0123456789abcdefLL),
3676 BPF_ENDIAN(BPF_FROM_BE, R0, 32), 3755 BPF_ENDIAN(BPF_FROM_BE, R0, 32),
3756 BPF_ALU64_REG(BPF_MOV, R1, R0),
3757 BPF_ALU64_IMM(BPF_RSH, R1, 32),
3758 BPF_ALU32_REG(BPF_ADD, R0, R1), /* R1 = 0 */
3677 BPF_EXIT_INSN(), 3759 BPF_EXIT_INSN(),
3678 }, 3760 },
3679 INTERNAL, 3761 INTERNAL,
@@ -3708,6 +3790,9 @@ static struct bpf_test tests[] = {
3708 .u.insns_int = { 3790 .u.insns_int = {
3709 BPF_LD_IMM64(R0, 0x0123456789abcdefLL), 3791 BPF_LD_IMM64(R0, 0x0123456789abcdefLL),
3710 BPF_ENDIAN(BPF_FROM_LE, R0, 32), 3792 BPF_ENDIAN(BPF_FROM_LE, R0, 32),
3793 BPF_ALU64_REG(BPF_MOV, R1, R0),
3794 BPF_ALU64_IMM(BPF_RSH, R1, 32),
3795 BPF_ALU32_REG(BPF_ADD, R0, R1), /* R1 = 0 */
3711 BPF_EXIT_INSN(), 3796 BPF_EXIT_INSN(),
3712 }, 3797 },
3713 INTERNAL, 3798 INTERNAL,
@@ -4392,6 +4477,618 @@ static struct bpf_test tests[] = {
4392 { { 0, 0xababcbac } }, 4477 { { 0, 0xababcbac } },
4393 .fill_helper = bpf_fill_maxinsns11, 4478 .fill_helper = bpf_fill_maxinsns11,
4394 }, 4479 },
4480 {
4481 "BPF_MAXINSNS: ld_abs+get_processor_id",
4482 { },
4483 CLASSIC,
4484 { },
4485 { { 1, 0xbee } },
4486 .fill_helper = bpf_fill_ld_abs_get_processor_id,
4487 },
4488 {
4489 "BPF_MAXINSNS: ld_abs+vlan_push/pop",
4490 { },
4491 INTERNAL,
4492 { 0x34 },
4493 { { 1, 0xbef } },
4494 .fill_helper = bpf_fill_ld_abs_vlan_push_pop,
4495 },
4496 /*
4497 * LD_IND / LD_ABS on fragmented SKBs
4498 */
4499 {
4500 "LD_IND byte frag",
4501 .u.insns = {
4502 BPF_STMT(BPF_LDX | BPF_IMM, 0x40),
4503 BPF_STMT(BPF_LD | BPF_IND | BPF_B, 0x0),
4504 BPF_STMT(BPF_RET | BPF_A, 0x0),
4505 },
4506 CLASSIC | FLAG_SKB_FRAG,
4507 { },
4508 { {0x40, 0x42} },
4509 .frag_data = {
4510 0x42, 0x00, 0x00, 0x00,
4511 0x43, 0x44, 0x00, 0x00,
4512 0x21, 0x07, 0x19, 0x83,
4513 },
4514 },
4515 {
4516 "LD_IND halfword frag",
4517 .u.insns = {
4518 BPF_STMT(BPF_LDX | BPF_IMM, 0x40),
4519 BPF_STMT(BPF_LD | BPF_IND | BPF_H, 0x4),
4520 BPF_STMT(BPF_RET | BPF_A, 0x0),
4521 },
4522 CLASSIC | FLAG_SKB_FRAG,
4523 { },
4524 { {0x40, 0x4344} },
4525 .frag_data = {
4526 0x42, 0x00, 0x00, 0x00,
4527 0x43, 0x44, 0x00, 0x00,
4528 0x21, 0x07, 0x19, 0x83,
4529 },
4530 },
4531 {
4532 "LD_IND word frag",
4533 .u.insns = {
4534 BPF_STMT(BPF_LDX | BPF_IMM, 0x40),
4535 BPF_STMT(BPF_LD | BPF_IND | BPF_W, 0x8),
4536 BPF_STMT(BPF_RET | BPF_A, 0x0),
4537 },
4538 CLASSIC | FLAG_SKB_FRAG,
4539 { },
4540 { {0x40, 0x21071983} },
4541 .frag_data = {
4542 0x42, 0x00, 0x00, 0x00,
4543 0x43, 0x44, 0x00, 0x00,
4544 0x21, 0x07, 0x19, 0x83,
4545 },
4546 },
4547 {
4548 "LD_IND halfword mixed head/frag",
4549 .u.insns = {
4550 BPF_STMT(BPF_LDX | BPF_IMM, 0x40),
4551 BPF_STMT(BPF_LD | BPF_IND | BPF_H, -0x1),
4552 BPF_STMT(BPF_RET | BPF_A, 0x0),
4553 },
4554 CLASSIC | FLAG_SKB_FRAG,
4555 { [0x3e] = 0x25, [0x3f] = 0x05, },
4556 { {0x40, 0x0519} },
4557 .frag_data = { 0x19, 0x82 },
4558 },
4559 {
4560 "LD_IND word mixed head/frag",
4561 .u.insns = {
4562 BPF_STMT(BPF_LDX | BPF_IMM, 0x40),
4563 BPF_STMT(BPF_LD | BPF_IND | BPF_W, -0x2),
4564 BPF_STMT(BPF_RET | BPF_A, 0x0),
4565 },
4566 CLASSIC | FLAG_SKB_FRAG,
4567 { [0x3e] = 0x25, [0x3f] = 0x05, },
4568 { {0x40, 0x25051982} },
4569 .frag_data = { 0x19, 0x82 },
4570 },
4571 {
4572 "LD_ABS byte frag",
4573 .u.insns = {
4574 BPF_STMT(BPF_LD | BPF_ABS | BPF_B, 0x40),
4575 BPF_STMT(BPF_RET | BPF_A, 0x0),
4576 },
4577 CLASSIC | FLAG_SKB_FRAG,
4578 { },
4579 { {0x40, 0x42} },
4580 .frag_data = {
4581 0x42, 0x00, 0x00, 0x00,
4582 0x43, 0x44, 0x00, 0x00,
4583 0x21, 0x07, 0x19, 0x83,
4584 },
4585 },
4586 {
4587 "LD_ABS halfword frag",
4588 .u.insns = {
4589 BPF_STMT(BPF_LD | BPF_ABS | BPF_H, 0x44),
4590 BPF_STMT(BPF_RET | BPF_A, 0x0),
4591 },
4592 CLASSIC | FLAG_SKB_FRAG,
4593 { },
4594 { {0x40, 0x4344} },
4595 .frag_data = {
4596 0x42, 0x00, 0x00, 0x00,
4597 0x43, 0x44, 0x00, 0x00,
4598 0x21, 0x07, 0x19, 0x83,
4599 },
4600 },
4601 {
4602 "LD_ABS word frag",
4603 .u.insns = {
4604 BPF_STMT(BPF_LD | BPF_ABS | BPF_W, 0x48),
4605 BPF_STMT(BPF_RET | BPF_A, 0x0),
4606 },
4607 CLASSIC | FLAG_SKB_FRAG,
4608 { },
4609 { {0x40, 0x21071983} },
4610 .frag_data = {
4611 0x42, 0x00, 0x00, 0x00,
4612 0x43, 0x44, 0x00, 0x00,
4613 0x21, 0x07, 0x19, 0x83,
4614 },
4615 },
4616 {
4617 "LD_ABS halfword mixed head/frag",
4618 .u.insns = {
4619 BPF_STMT(BPF_LD | BPF_ABS | BPF_H, 0x3f),
4620 BPF_STMT(BPF_RET | BPF_A, 0x0),
4621 },
4622 CLASSIC | FLAG_SKB_FRAG,
4623 { [0x3e] = 0x25, [0x3f] = 0x05, },
4624 { {0x40, 0x0519} },
4625 .frag_data = { 0x19, 0x82 },
4626 },
4627 {
4628 "LD_ABS word mixed head/frag",
4629 .u.insns = {
4630 BPF_STMT(BPF_LD | BPF_ABS | BPF_W, 0x3e),
4631 BPF_STMT(BPF_RET | BPF_A, 0x0),
4632 },
4633 CLASSIC | FLAG_SKB_FRAG,
4634 { [0x3e] = 0x25, [0x3f] = 0x05, },
4635 { {0x40, 0x25051982} },
4636 .frag_data = { 0x19, 0x82 },
4637 },
4638 /*
4639 * LD_IND / LD_ABS on non fragmented SKBs
4640 */
4641 {
4642 /*
4643 * this tests that the JIT/interpreter correctly resets X
4644 * before using it in an LD_IND instruction.
4645 */
4646 "LD_IND byte default X",
4647 .u.insns = {
4648 BPF_STMT(BPF_LD | BPF_IND | BPF_B, 0x1),
4649 BPF_STMT(BPF_RET | BPF_A, 0x0),
4650 },
4651 CLASSIC,
4652 { [0x1] = 0x42 },
4653 { {0x40, 0x42 } },
4654 },
4655 {
4656 "LD_IND byte positive offset",
4657 .u.insns = {
4658 BPF_STMT(BPF_LDX | BPF_IMM, 0x3e),
4659 BPF_STMT(BPF_LD | BPF_IND | BPF_B, 0x1),
4660 BPF_STMT(BPF_RET | BPF_A, 0x0),
4661 },
4662 CLASSIC,
4663 { [0x3c] = 0x25, [0x3d] = 0x05, [0x3e] = 0x19, [0x3f] = 0x82 },
4664 { {0x40, 0x82 } },
4665 },
4666 {
4667 "LD_IND byte negative offset",
4668 .u.insns = {
4669 BPF_STMT(BPF_LDX | BPF_IMM, 0x3e),
4670 BPF_STMT(BPF_LD | BPF_IND | BPF_B, -0x1),
4671 BPF_STMT(BPF_RET | BPF_A, 0x0),
4672 },
4673 CLASSIC,
4674 { [0x3c] = 0x25, [0x3d] = 0x05, [0x3e] = 0x19, [0x3f] = 0x82 },
4675 { {0x40, 0x05 } },
4676 },
4677 {
4678 "LD_IND halfword positive offset",
4679 .u.insns = {
4680 BPF_STMT(BPF_LDX | BPF_IMM, 0x20),
4681 BPF_STMT(BPF_LD | BPF_IND | BPF_H, 0x2),
4682 BPF_STMT(BPF_RET | BPF_A, 0x0),
4683 },
4684 CLASSIC,
4685 {
4686 [0x1c] = 0xaa, [0x1d] = 0x55,
4687 [0x1e] = 0xbb, [0x1f] = 0x66,
4688 [0x20] = 0xcc, [0x21] = 0x77,
4689 [0x22] = 0xdd, [0x23] = 0x88,
4690 },
4691 { {0x40, 0xdd88 } },
4692 },
4693 {
4694 "LD_IND halfword negative offset",
4695 .u.insns = {
4696 BPF_STMT(BPF_LDX | BPF_IMM, 0x20),
4697 BPF_STMT(BPF_LD | BPF_IND | BPF_H, -0x2),
4698 BPF_STMT(BPF_RET | BPF_A, 0x0),
4699 },
4700 CLASSIC,
4701 {
4702 [0x1c] = 0xaa, [0x1d] = 0x55,
4703 [0x1e] = 0xbb, [0x1f] = 0x66,
4704 [0x20] = 0xcc, [0x21] = 0x77,
4705 [0x22] = 0xdd, [0x23] = 0x88,
4706 },
4707 { {0x40, 0xbb66 } },
4708 },
4709 {
4710 "LD_IND halfword unaligned",
4711 .u.insns = {
4712 BPF_STMT(BPF_LDX | BPF_IMM, 0x20),
4713 BPF_STMT(BPF_LD | BPF_IND | BPF_H, -0x1),
4714 BPF_STMT(BPF_RET | BPF_A, 0x0),
4715 },
4716 CLASSIC,
4717 {
4718 [0x1c] = 0xaa, [0x1d] = 0x55,
4719 [0x1e] = 0xbb, [0x1f] = 0x66,
4720 [0x20] = 0xcc, [0x21] = 0x77,
4721 [0x22] = 0xdd, [0x23] = 0x88,
4722 },
4723 { {0x40, 0x66cc } },
4724 },
4725 {
4726 "LD_IND word positive offset",
4727 .u.insns = {
4728 BPF_STMT(BPF_LDX | BPF_IMM, 0x20),
4729 BPF_STMT(BPF_LD | BPF_IND | BPF_W, 0x4),
4730 BPF_STMT(BPF_RET | BPF_A, 0x0),
4731 },
4732 CLASSIC,
4733 {
4734 [0x1c] = 0xaa, [0x1d] = 0x55,
4735 [0x1e] = 0xbb, [0x1f] = 0x66,
4736 [0x20] = 0xcc, [0x21] = 0x77,
4737 [0x22] = 0xdd, [0x23] = 0x88,
4738 [0x24] = 0xee, [0x25] = 0x99,
4739 [0x26] = 0xff, [0x27] = 0xaa,
4740 },
4741 { {0x40, 0xee99ffaa } },
4742 },
4743 {
4744 "LD_IND word negative offset",
4745 .u.insns = {
4746 BPF_STMT(BPF_LDX | BPF_IMM, 0x20),
4747 BPF_STMT(BPF_LD | BPF_IND | BPF_W, -0x4),
4748 BPF_STMT(BPF_RET | BPF_A, 0x0),
4749 },
4750 CLASSIC,
4751 {
4752 [0x1c] = 0xaa, [0x1d] = 0x55,
4753 [0x1e] = 0xbb, [0x1f] = 0x66,
4754 [0x20] = 0xcc, [0x21] = 0x77,
4755 [0x22] = 0xdd, [0x23] = 0x88,
4756 [0x24] = 0xee, [0x25] = 0x99,
4757 [0x26] = 0xff, [0x27] = 0xaa,
4758 },
4759 { {0x40, 0xaa55bb66 } },
4760 },
4761 {
4762 "LD_IND word unaligned (addr & 3 == 2)",
4763 .u.insns = {
4764 BPF_STMT(BPF_LDX | BPF_IMM, 0x20),
4765 BPF_STMT(BPF_LD | BPF_IND | BPF_W, -0x2),
4766 BPF_STMT(BPF_RET | BPF_A, 0x0),
4767 },
4768 CLASSIC,
4769 {
4770 [0x1c] = 0xaa, [0x1d] = 0x55,
4771 [0x1e] = 0xbb, [0x1f] = 0x66,
4772 [0x20] = 0xcc, [0x21] = 0x77,
4773 [0x22] = 0xdd, [0x23] = 0x88,
4774 [0x24] = 0xee, [0x25] = 0x99,
4775 [0x26] = 0xff, [0x27] = 0xaa,
4776 },
4777 { {0x40, 0xbb66cc77 } },
4778 },
4779 {
4780 "LD_IND word unaligned (addr & 3 == 1)",
4781 .u.insns = {
4782 BPF_STMT(BPF_LDX | BPF_IMM, 0x20),
4783 BPF_STMT(BPF_LD | BPF_IND | BPF_W, -0x3),
4784 BPF_STMT(BPF_RET | BPF_A, 0x0),
4785 },
4786 CLASSIC,
4787 {
4788 [0x1c] = 0xaa, [0x1d] = 0x55,
4789 [0x1e] = 0xbb, [0x1f] = 0x66,
4790 [0x20] = 0xcc, [0x21] = 0x77,
4791 [0x22] = 0xdd, [0x23] = 0x88,
4792 [0x24] = 0xee, [0x25] = 0x99,
4793 [0x26] = 0xff, [0x27] = 0xaa,
4794 },
4795 { {0x40, 0x55bb66cc } },
4796 },
4797 {
4798 "LD_IND word unaligned (addr & 3 == 3)",
4799 .u.insns = {
4800 BPF_STMT(BPF_LDX | BPF_IMM, 0x20),
4801 BPF_STMT(BPF_LD | BPF_IND | BPF_W, -0x1),
4802 BPF_STMT(BPF_RET | BPF_A, 0x0),
4803 },
4804 CLASSIC,
4805 {
4806 [0x1c] = 0xaa, [0x1d] = 0x55,
4807 [0x1e] = 0xbb, [0x1f] = 0x66,
4808 [0x20] = 0xcc, [0x21] = 0x77,
4809 [0x22] = 0xdd, [0x23] = 0x88,
4810 [0x24] = 0xee, [0x25] = 0x99,
4811 [0x26] = 0xff, [0x27] = 0xaa,
4812 },
4813 { {0x40, 0x66cc77dd } },
4814 },
4815 {
4816 "LD_ABS byte",
4817 .u.insns = {
4818 BPF_STMT(BPF_LD | BPF_ABS | BPF_B, 0x20),
4819 BPF_STMT(BPF_RET | BPF_A, 0x0),
4820 },
4821 CLASSIC,
4822 {
4823 [0x1c] = 0xaa, [0x1d] = 0x55,
4824 [0x1e] = 0xbb, [0x1f] = 0x66,
4825 [0x20] = 0xcc, [0x21] = 0x77,
4826 [0x22] = 0xdd, [0x23] = 0x88,
4827 [0x24] = 0xee, [0x25] = 0x99,
4828 [0x26] = 0xff, [0x27] = 0xaa,
4829 },
4830 { {0x40, 0xcc } },
4831 },
4832 {
4833 "LD_ABS halfword",
4834 .u.insns = {
4835 BPF_STMT(BPF_LD | BPF_ABS | BPF_H, 0x22),
4836 BPF_STMT(BPF_RET | BPF_A, 0x0),
4837 },
4838 CLASSIC,
4839 {
4840 [0x1c] = 0xaa, [0x1d] = 0x55,
4841 [0x1e] = 0xbb, [0x1f] = 0x66,
4842 [0x20] = 0xcc, [0x21] = 0x77,
4843 [0x22] = 0xdd, [0x23] = 0x88,
4844 [0x24] = 0xee, [0x25] = 0x99,
4845 [0x26] = 0xff, [0x27] = 0xaa,
4846 },
4847 { {0x40, 0xdd88 } },
4848 },
4849 {
4850 "LD_ABS halfword unaligned",
4851 .u.insns = {
4852 BPF_STMT(BPF_LD | BPF_ABS | BPF_H, 0x25),
4853 BPF_STMT(BPF_RET | BPF_A, 0x0),
4854 },
4855 CLASSIC,
4856 {
4857 [0x1c] = 0xaa, [0x1d] = 0x55,
4858 [0x1e] = 0xbb, [0x1f] = 0x66,
4859 [0x20] = 0xcc, [0x21] = 0x77,
4860 [0x22] = 0xdd, [0x23] = 0x88,
4861 [0x24] = 0xee, [0x25] = 0x99,
4862 [0x26] = 0xff, [0x27] = 0xaa,
4863 },
4864 { {0x40, 0x99ff } },
4865 },
4866 {
4867 "LD_ABS word",
4868 .u.insns = {
4869 BPF_STMT(BPF_LD | BPF_ABS | BPF_W, 0x1c),
4870 BPF_STMT(BPF_RET | BPF_A, 0x0),
4871 },
4872 CLASSIC,
4873 {
4874 [0x1c] = 0xaa, [0x1d] = 0x55,
4875 [0x1e] = 0xbb, [0x1f] = 0x66,
4876 [0x20] = 0xcc, [0x21] = 0x77,
4877 [0x22] = 0xdd, [0x23] = 0x88,
4878 [0x24] = 0xee, [0x25] = 0x99,
4879 [0x26] = 0xff, [0x27] = 0xaa,
4880 },
4881 { {0x40, 0xaa55bb66 } },
4882 },
4883 {
4884 "LD_ABS word unaligned (addr & 3 == 2)",
4885 .u.insns = {
4886 BPF_STMT(BPF_LD | BPF_ABS | BPF_W, 0x22),
4887 BPF_STMT(BPF_RET | BPF_A, 0x0),
4888 },
4889 CLASSIC,
4890 {
4891 [0x1c] = 0xaa, [0x1d] = 0x55,
4892 [0x1e] = 0xbb, [0x1f] = 0x66,
4893 [0x20] = 0xcc, [0x21] = 0x77,
4894 [0x22] = 0xdd, [0x23] = 0x88,
4895 [0x24] = 0xee, [0x25] = 0x99,
4896 [0x26] = 0xff, [0x27] = 0xaa,
4897 },
4898 { {0x40, 0xdd88ee99 } },
4899 },
4900 {
4901 "LD_ABS word unaligned (addr & 3 == 1)",
4902 .u.insns = {
4903 BPF_STMT(BPF_LD | BPF_ABS | BPF_W, 0x21),
4904 BPF_STMT(BPF_RET | BPF_A, 0x0),
4905 },
4906 CLASSIC,
4907 {
4908 [0x1c] = 0xaa, [0x1d] = 0x55,
4909 [0x1e] = 0xbb, [0x1f] = 0x66,
4910 [0x20] = 0xcc, [0x21] = 0x77,
4911 [0x22] = 0xdd, [0x23] = 0x88,
4912 [0x24] = 0xee, [0x25] = 0x99,
4913 [0x26] = 0xff, [0x27] = 0xaa,
4914 },
4915 { {0x40, 0x77dd88ee } },
4916 },
4917 {
4918 "LD_ABS word unaligned (addr & 3 == 3)",
4919 .u.insns = {
4920 BPF_STMT(BPF_LD | BPF_ABS | BPF_W, 0x23),
4921 BPF_STMT(BPF_RET | BPF_A, 0x0),
4922 },
4923 CLASSIC,
4924 {
4925 [0x1c] = 0xaa, [0x1d] = 0x55,
4926 [0x1e] = 0xbb, [0x1f] = 0x66,
4927 [0x20] = 0xcc, [0x21] = 0x77,
4928 [0x22] = 0xdd, [0x23] = 0x88,
4929 [0x24] = 0xee, [0x25] = 0x99,
4930 [0x26] = 0xff, [0x27] = 0xaa,
4931 },
4932 { {0x40, 0x88ee99ff } },
4933 },
4934 /*
4935 * verify that the interpreter or JIT correctly sets A and X
4936 * to 0.
4937 */
4938 {
4939 "ADD default X",
4940 .u.insns = {
4941 /*
4942 * A = 0x42
4943 * A = A + X
4944 * ret A
4945 */
4946 BPF_STMT(BPF_LD | BPF_IMM, 0x42),
4947 BPF_STMT(BPF_ALU | BPF_ADD | BPF_X, 0),
4948 BPF_STMT(BPF_RET | BPF_A, 0x0),
4949 },
4950 CLASSIC | FLAG_NO_DATA,
4951 {},
4952 { {0x1, 0x42 } },
4953 },
4954 {
4955 "ADD default A",
4956 .u.insns = {
4957 /*
4958 * A = A + 0x42
4959 * ret A
4960 */
4961 BPF_STMT(BPF_ALU | BPF_ADD | BPF_K, 0x42),
4962 BPF_STMT(BPF_RET | BPF_A, 0x0),
4963 },
4964 CLASSIC | FLAG_NO_DATA,
4965 {},
4966 { {0x1, 0x42 } },
4967 },
4968 {
4969 "SUB default X",
4970 .u.insns = {
4971 /*
4972 * A = 0x66
4973 * A = A - X
4974 * ret A
4975 */
4976 BPF_STMT(BPF_LD | BPF_IMM, 0x66),
4977 BPF_STMT(BPF_ALU | BPF_SUB | BPF_X, 0),
4978 BPF_STMT(BPF_RET | BPF_A, 0x0),
4979 },
4980 CLASSIC | FLAG_NO_DATA,
4981 {},
4982 { {0x1, 0x66 } },
4983 },
4984 {
4985 "SUB default A",
4986 .u.insns = {
4987 /*
4988 * A = A - -0x66
4989 * ret A
4990 */
4991 BPF_STMT(BPF_ALU | BPF_SUB | BPF_K, -0x66),
4992 BPF_STMT(BPF_RET | BPF_A, 0x0),
4993 },
4994 CLASSIC | FLAG_NO_DATA,
4995 {},
4996 { {0x1, 0x66 } },
4997 },
4998 {
4999 "MUL default X",
5000 .u.insns = {
5001 /*
5002 * A = 0x42
5003 * A = A * X
5004 * ret A
5005 */
5006 BPF_STMT(BPF_LD | BPF_IMM, 0x42),
5007 BPF_STMT(BPF_ALU | BPF_MUL | BPF_X, 0),
5008 BPF_STMT(BPF_RET | BPF_A, 0x0),
5009 },
5010 CLASSIC | FLAG_NO_DATA,
5011 {},
5012 { {0x1, 0x0 } },
5013 },
5014 {
5015 "MUL default A",
5016 .u.insns = {
5017 /*
5018 * A = A * 0x66
5019 * ret A
5020 */
5021 BPF_STMT(BPF_ALU | BPF_MUL | BPF_K, 0x66),
5022 BPF_STMT(BPF_RET | BPF_A, 0x0),
5023 },
5024 CLASSIC | FLAG_NO_DATA,
5025 {},
5026 { {0x1, 0x0 } },
5027 },
5028 {
5029 "DIV default X",
5030 .u.insns = {
5031 /*
5032 * A = 0x42
5033 * A = A / X ; this halt the filter execution if X is 0
5034 * ret 0x42
5035 */
5036 BPF_STMT(BPF_LD | BPF_IMM, 0x42),
5037 BPF_STMT(BPF_ALU | BPF_DIV | BPF_X, 0),
5038 BPF_STMT(BPF_RET | BPF_K, 0x42),
5039 },
5040 CLASSIC | FLAG_NO_DATA,
5041 {},
5042 { {0x1, 0x0 } },
5043 },
5044 {
5045 "DIV default A",
5046 .u.insns = {
5047 /*
5048 * A = A / 1
5049 * ret A
5050 */
5051 BPF_STMT(BPF_ALU | BPF_DIV | BPF_K, 0x1),
5052 BPF_STMT(BPF_RET | BPF_A, 0x0),
5053 },
5054 CLASSIC | FLAG_NO_DATA,
5055 {},
5056 { {0x1, 0x0 } },
5057 },
5058 {
5059 "JMP EQ default A",
5060 .u.insns = {
5061 /*
5062 * cmp A, 0x0, 0, 1
5063 * ret 0x42
5064 * ret 0x66
5065 */
5066 BPF_JUMP(BPF_JMP | BPF_JEQ | BPF_K, 0x0, 0, 1),
5067 BPF_STMT(BPF_RET | BPF_K, 0x42),
5068 BPF_STMT(BPF_RET | BPF_K, 0x66),
5069 },
5070 CLASSIC | FLAG_NO_DATA,
5071 {},
5072 { {0x1, 0x42 } },
5073 },
5074 {
5075 "JMP EQ default X",
5076 .u.insns = {
5077 /*
5078 * A = 0x0
5079 * cmp A, X, 0, 1
5080 * ret 0x42
5081 * ret 0x66
5082 */
5083 BPF_STMT(BPF_LD | BPF_IMM, 0x0),
5084 BPF_JUMP(BPF_JMP | BPF_JEQ | BPF_X, 0x0, 0, 1),
5085 BPF_STMT(BPF_RET | BPF_K, 0x42),
5086 BPF_STMT(BPF_RET | BPF_K, 0x66),
5087 },
5088 CLASSIC | FLAG_NO_DATA,
5089 {},
5090 { {0x1, 0x42 } },
5091 },
4395}; 5092};
4396 5093
4397static struct net_device dev; 5094static struct net_device dev;
@@ -4427,6 +5124,9 @@ static struct sk_buff *populate_skb(char *buf, int size)
4427 5124
4428static void *generate_test_data(struct bpf_test *test, int sub) 5125static void *generate_test_data(struct bpf_test *test, int sub)
4429{ 5126{
5127 struct sk_buff *skb;
5128 struct page *page;
5129
4430 if (test->aux & FLAG_NO_DATA) 5130 if (test->aux & FLAG_NO_DATA)
4431 return NULL; 5131 return NULL;
4432 5132
@@ -4434,7 +5134,38 @@ static void *generate_test_data(struct bpf_test *test, int sub)
4434 * subtests generate skbs of different sizes based on 5134 * subtests generate skbs of different sizes based on
4435 * the same data. 5135 * the same data.
4436 */ 5136 */
4437 return populate_skb(test->data, test->test[sub].data_size); 5137 skb = populate_skb(test->data, test->test[sub].data_size);
5138 if (!skb)
5139 return NULL;
5140
5141 if (test->aux & FLAG_SKB_FRAG) {
5142 /*
5143 * when the test requires a fragmented skb, add a
5144 * single fragment to the skb, filled with
5145 * test->frag_data.
5146 */
5147 void *ptr;
5148
5149 page = alloc_page(GFP_KERNEL);
5150
5151 if (!page)
5152 goto err_kfree_skb;
5153
5154 ptr = kmap(page);
5155 if (!ptr)
5156 goto err_free_page;
5157 memcpy(ptr, test->frag_data, MAX_DATA);
5158 kunmap(page);
5159 skb_add_rx_frag(skb, 0, page, 0, MAX_DATA, MAX_DATA);
5160 }
5161
5162 return skb;
5163
5164err_free_page:
5165 __free_page(page);
5166err_kfree_skb:
5167 kfree_skb(skb);
5168 return NULL;
4438} 5169}
4439 5170
4440static void release_test_data(const struct bpf_test *test, void *data) 5171static void release_test_data(const struct bpf_test *test, void *data)
@@ -4515,6 +5246,8 @@ static struct bpf_prog *generate_filter(int which, int *err)
4515 } 5246 }
4516 5247
4517 fp->len = flen; 5248 fp->len = flen;
5249 /* Type doesn't really matter here as long as it's not unspec. */
5250 fp->type = BPF_PROG_TYPE_SOCKET_FILTER;
4518 memcpy(fp->insnsi, fptr, fp->len * sizeof(struct bpf_insn)); 5251 memcpy(fp->insnsi, fptr, fp->len * sizeof(struct bpf_insn));
4519 5252
4520 bpf_prog_select_runtime(fp); 5253 bpf_prog_select_runtime(fp);
@@ -4545,14 +5278,14 @@ static int __run_one(const struct bpf_prog *fp, const void *data,
4545 u64 start, finish; 5278 u64 start, finish;
4546 int ret = 0, i; 5279 int ret = 0, i;
4547 5280
4548 start = ktime_to_us(ktime_get()); 5281 start = ktime_get_ns();
4549 5282
4550 for (i = 0; i < runs; i++) 5283 for (i = 0; i < runs; i++)
4551 ret = BPF_PROG_RUN(fp, data); 5284 ret = BPF_PROG_RUN(fp, data);
4552 5285
4553 finish = ktime_to_us(ktime_get()); 5286 finish = ktime_get_ns();
4554 5287
4555 *duration = (finish - start) * 1000ULL; 5288 *duration = finish - start;
4556 do_div(*duration, runs); 5289 do_div(*duration, runs);
4557 5290
4558 return ret; 5291 return ret;
@@ -4572,6 +5305,11 @@ static int run_one(const struct bpf_prog *fp, struct bpf_test *test)
4572 break; 5305 break;
4573 5306
4574 data = generate_test_data(test, i); 5307 data = generate_test_data(test, i);
5308 if (!data && !(test->aux & FLAG_NO_DATA)) {
5309 pr_cont("data generation failed ");
5310 err_cnt++;
5311 break;
5312 }
4575 ret = __run_one(fp, data, runs, &duration); 5313 ret = __run_one(fp, data, runs, &duration);
4576 release_test_data(test, data); 5314 release_test_data(test, data);
4577 5315
@@ -4587,10 +5325,73 @@ static int run_one(const struct bpf_prog *fp, struct bpf_test *test)
4587 return err_cnt; 5325 return err_cnt;
4588} 5326}
4589 5327
5328static char test_name[64];
5329module_param_string(test_name, test_name, sizeof(test_name), 0);
5330
5331static int test_id = -1;
5332module_param(test_id, int, 0);
5333
5334static int test_range[2] = { 0, ARRAY_SIZE(tests) - 1 };
5335module_param_array(test_range, int, NULL, 0);
5336
5337static __init int find_test_index(const char *test_name)
5338{
5339 int i;
5340
5341 for (i = 0; i < ARRAY_SIZE(tests); i++) {
5342 if (!strcmp(tests[i].descr, test_name))
5343 return i;
5344 }
5345 return -1;
5346}
5347
4590static __init int prepare_bpf_tests(void) 5348static __init int prepare_bpf_tests(void)
4591{ 5349{
4592 int i; 5350 int i;
4593 5351
5352 if (test_id >= 0) {
5353 /*
5354 * if a test_id was specified, use test_range to
5355 * cover only that test.
5356 */
5357 if (test_id >= ARRAY_SIZE(tests)) {
5358 pr_err("test_bpf: invalid test_id specified.\n");
5359 return -EINVAL;
5360 }
5361
5362 test_range[0] = test_id;
5363 test_range[1] = test_id;
5364 } else if (*test_name) {
5365 /*
5366 * if a test_name was specified, find it and setup
5367 * test_range to cover only that test.
5368 */
5369 int idx = find_test_index(test_name);
5370
5371 if (idx < 0) {
5372 pr_err("test_bpf: no test named '%s' found.\n",
5373 test_name);
5374 return -EINVAL;
5375 }
5376 test_range[0] = idx;
5377 test_range[1] = idx;
5378 } else {
5379 /*
5380 * check that the supplied test_range is valid.
5381 */
5382 if (test_range[0] >= ARRAY_SIZE(tests) ||
5383 test_range[1] >= ARRAY_SIZE(tests) ||
5384 test_range[0] < 0 || test_range[1] < 0) {
5385 pr_err("test_bpf: test_range is out of bound.\n");
5386 return -EINVAL;
5387 }
5388
5389 if (test_range[1] < test_range[0]) {
5390 pr_err("test_bpf: test_range is ending before it starts.\n");
5391 return -EINVAL;
5392 }
5393 }
5394
4594 for (i = 0; i < ARRAY_SIZE(tests); i++) { 5395 for (i = 0; i < ARRAY_SIZE(tests); i++) {
4595 if (tests[i].fill_helper && 5396 if (tests[i].fill_helper &&
4596 tests[i].fill_helper(&tests[i]) < 0) 5397 tests[i].fill_helper(&tests[i]) < 0)
@@ -4610,6 +5411,11 @@ static __init void destroy_bpf_tests(void)
4610 } 5411 }
4611} 5412}
4612 5413
5414static bool exclude_test(int test_id)
5415{
5416 return test_id < test_range[0] || test_id > test_range[1];
5417}
5418
4613static __init int test_bpf(void) 5419static __init int test_bpf(void)
4614{ 5420{
4615 int i, err_cnt = 0, pass_cnt = 0; 5421 int i, err_cnt = 0, pass_cnt = 0;
@@ -4619,6 +5425,9 @@ static __init int test_bpf(void)
4619 struct bpf_prog *fp; 5425 struct bpf_prog *fp;
4620 int err; 5426 int err;
4621 5427
5428 if (exclude_test(i))
5429 continue;
5430
4622 pr_info("#%d %s ", i, tests[i].descr); 5431 pr_info("#%d %s ", i, tests[i].descr);
4623 5432
4624 fp = generate_filter(i, &err); 5433 fp = generate_filter(i, &err);
diff --git a/lib/test_rhashtable.c b/lib/test_rhashtable.c
index c90777eae1f8..8c1ad1ced72c 100644
--- a/lib/test_rhashtable.c
+++ b/lib/test_rhashtable.c
@@ -16,10 +16,14 @@
16#include <linux/init.h> 16#include <linux/init.h>
17#include <linux/jhash.h> 17#include <linux/jhash.h>
18#include <linux/kernel.h> 18#include <linux/kernel.h>
19#include <linux/kthread.h>
19#include <linux/module.h> 20#include <linux/module.h>
20#include <linux/rcupdate.h> 21#include <linux/rcupdate.h>
21#include <linux/rhashtable.h> 22#include <linux/rhashtable.h>
23#include <linux/semaphore.h>
22#include <linux/slab.h> 24#include <linux/slab.h>
25#include <linux/sched.h>
26#include <linux/vmalloc.h>
23 27
24#define MAX_ENTRIES 1000000 28#define MAX_ENTRIES 1000000
25#define TEST_INSERT_FAIL INT_MAX 29#define TEST_INSERT_FAIL INT_MAX
@@ -44,11 +48,21 @@ static int size = 8;
44module_param(size, int, 0); 48module_param(size, int, 0);
45MODULE_PARM_DESC(size, "Initial size hint of table (default: 8)"); 49MODULE_PARM_DESC(size, "Initial size hint of table (default: 8)");
46 50
51static int tcount = 10;
52module_param(tcount, int, 0);
53MODULE_PARM_DESC(tcount, "Number of threads to spawn (default: 10)");
54
47struct test_obj { 55struct test_obj {
48 int value; 56 int value;
49 struct rhash_head node; 57 struct rhash_head node;
50}; 58};
51 59
60struct thread_data {
61 int id;
62 struct task_struct *task;
63 struct test_obj *objs;
64};
65
52static struct test_obj array[MAX_ENTRIES]; 66static struct test_obj array[MAX_ENTRIES];
53 67
54static struct rhashtable_params test_rht_params = { 68static struct rhashtable_params test_rht_params = {
@@ -59,6 +73,9 @@ static struct rhashtable_params test_rht_params = {
59 .nulls_base = (3U << RHT_BASE_SHIFT), 73 .nulls_base = (3U << RHT_BASE_SHIFT),
60}; 74};
61 75
76static struct semaphore prestart_sem;
77static struct semaphore startup_sem = __SEMAPHORE_INITIALIZER(startup_sem, 0);
78
62static int __init test_rht_lookup(struct rhashtable *ht) 79static int __init test_rht_lookup(struct rhashtable *ht)
63{ 80{
64 unsigned int i; 81 unsigned int i;
@@ -87,6 +104,8 @@ static int __init test_rht_lookup(struct rhashtable *ht)
87 return -EINVAL; 104 return -EINVAL;
88 } 105 }
89 } 106 }
107
108 cond_resched_rcu();
90 } 109 }
91 110
92 return 0; 111 return 0;
@@ -160,6 +179,8 @@ static s64 __init test_rhashtable(struct rhashtable *ht)
160 } else if (err) { 179 } else if (err) {
161 return err; 180 return err;
162 } 181 }
182
183 cond_resched();
163 } 184 }
164 185
165 if (insert_fails) 186 if (insert_fails)
@@ -183,6 +204,8 @@ static s64 __init test_rhashtable(struct rhashtable *ht)
183 204
184 rhashtable_remove_fast(ht, &obj->node, test_rht_params); 205 rhashtable_remove_fast(ht, &obj->node, test_rht_params);
185 } 206 }
207
208 cond_resched();
186 } 209 }
187 210
188 end = ktime_get_ns(); 211 end = ktime_get_ns();
@@ -193,10 +216,97 @@ static s64 __init test_rhashtable(struct rhashtable *ht)
193 216
194static struct rhashtable ht; 217static struct rhashtable ht;
195 218
219static int thread_lookup_test(struct thread_data *tdata)
220{
221 int i, err = 0;
222
223 for (i = 0; i < entries; i++) {
224 struct test_obj *obj;
225 int key = (tdata->id << 16) | i;
226
227 obj = rhashtable_lookup_fast(&ht, &key, test_rht_params);
228 if (obj && (tdata->objs[i].value == TEST_INSERT_FAIL)) {
229 pr_err(" found unexpected object %d\n", key);
230 err++;
231 } else if (!obj && (tdata->objs[i].value != TEST_INSERT_FAIL)) {
232 pr_err(" object %d not found!\n", key);
233 err++;
234 } else if (obj && (obj->value != key)) {
235 pr_err(" wrong object returned (got %d, expected %d)\n",
236 obj->value, key);
237 err++;
238 }
239 }
240 return err;
241}
242
243static int threadfunc(void *data)
244{
245 int i, step, err = 0, insert_fails = 0;
246 struct thread_data *tdata = data;
247
248 up(&prestart_sem);
249 if (down_interruptible(&startup_sem))
250 pr_err(" thread[%d]: down_interruptible failed\n", tdata->id);
251
252 for (i = 0; i < entries; i++) {
253 tdata->objs[i].value = (tdata->id << 16) | i;
254 err = rhashtable_insert_fast(&ht, &tdata->objs[i].node,
255 test_rht_params);
256 if (err == -ENOMEM || err == -EBUSY) {
257 tdata->objs[i].value = TEST_INSERT_FAIL;
258 insert_fails++;
259 } else if (err) {
260 pr_err(" thread[%d]: rhashtable_insert_fast failed\n",
261 tdata->id);
262 goto out;
263 }
264 }
265 if (insert_fails)
266 pr_info(" thread[%d]: %d insert failures\n",
267 tdata->id, insert_fails);
268
269 err = thread_lookup_test(tdata);
270 if (err) {
271 pr_err(" thread[%d]: rhashtable_lookup_test failed\n",
272 tdata->id);
273 goto out;
274 }
275
276 for (step = 10; step > 0; step--) {
277 for (i = 0; i < entries; i += step) {
278 if (tdata->objs[i].value == TEST_INSERT_FAIL)
279 continue;
280 err = rhashtable_remove_fast(&ht, &tdata->objs[i].node,
281 test_rht_params);
282 if (err) {
283 pr_err(" thread[%d]: rhashtable_remove_fast failed\n",
284 tdata->id);
285 goto out;
286 }
287 tdata->objs[i].value = TEST_INSERT_FAIL;
288 }
289 err = thread_lookup_test(tdata);
290 if (err) {
291 pr_err(" thread[%d]: rhashtable_lookup_test (2) failed\n",
292 tdata->id);
293 goto out;
294 }
295 }
296out:
297 while (!kthread_should_stop()) {
298 set_current_state(TASK_INTERRUPTIBLE);
299 schedule();
300 }
301 return err;
302}
303
196static int __init test_rht_init(void) 304static int __init test_rht_init(void)
197{ 305{
198 int i, err; 306 int i, err, started_threads = 0, failed_threads = 0;
199 u64 total_time = 0; 307 u64 total_time = 0;
308 struct thread_data *tdata;
309 struct test_obj *objs;
200 310
201 entries = min(entries, MAX_ENTRIES); 311 entries = min(entries, MAX_ENTRIES);
202 312
@@ -232,6 +342,57 @@ static int __init test_rht_init(void)
232 do_div(total_time, runs); 342 do_div(total_time, runs);
233 pr_info("Average test time: %llu\n", total_time); 343 pr_info("Average test time: %llu\n", total_time);
234 344
345 if (!tcount)
346 return 0;
347
348 pr_info("Testing concurrent rhashtable access from %d threads\n",
349 tcount);
350 sema_init(&prestart_sem, 1 - tcount);
351 tdata = vzalloc(tcount * sizeof(struct thread_data));
352 if (!tdata)
353 return -ENOMEM;
354 objs = vzalloc(tcount * entries * sizeof(struct test_obj));
355 if (!objs) {
356 vfree(tdata);
357 return -ENOMEM;
358 }
359
360 err = rhashtable_init(&ht, &test_rht_params);
361 if (err < 0) {
362 pr_warn("Test failed: Unable to initialize hashtable: %d\n",
363 err);
364 vfree(tdata);
365 vfree(objs);
366 return -EINVAL;
367 }
368 for (i = 0; i < tcount; i++) {
369 tdata[i].id = i;
370 tdata[i].objs = objs + i * entries;
371 tdata[i].task = kthread_run(threadfunc, &tdata[i],
372 "rhashtable_thrad[%d]", i);
373 if (IS_ERR(tdata[i].task))
374 pr_err(" kthread_run failed for thread %d\n", i);
375 else
376 started_threads++;
377 }
378 if (down_interruptible(&prestart_sem))
379 pr_err(" down interruptible failed\n");
380 for (i = 0; i < tcount; i++)
381 up(&startup_sem);
382 for (i = 0; i < tcount; i++) {
383 if (IS_ERR(tdata[i].task))
384 continue;
385 if ((err = kthread_stop(tdata[i].task))) {
386 pr_warn("Test failed: thread %d returned: %d\n",
387 i, err);
388 failed_threads++;
389 }
390 }
391 pr_info("Started %d threads, %d failed\n",
392 started_threads, failed_threads);
393 rhashtable_destroy(&ht);
394 vfree(tdata);
395 vfree(objs);
235 return 0; 396 return 0;
236} 397}
237 398
generated by cgit v1.2.2 (git 2.25.0) at 2025-02-21 20:18:05 -0500