Revision 5f4fc6d440d77a2cf74fe4ea56955674ac7e35e7 authored by Linus Torvalds on 19 July 2019, 17:06:06 UTC, committed by Linus Torvalds on 19 July 2019, 17:06:06 UTC
Pull networking fixes from David Miller: 1) Fix AF_XDP cq entry leak, from Ilya Maximets. 2) Fix handling of PHY power-down on RTL8411B, from Heiner Kallweit. 3) Add some new PCI IDs to iwlwifi, from Ihab Zhaika. 4) Fix handling of neigh timers wrt. entries added by userspace, from Lorenzo Bianconi. 5) Various cases of missing of_node_put(), from Nishka Dasgupta. 6) The new NET_ACT_CT needs to depend upon NF_NAT, from Yue Haibing. 7) Various RDS layer fixes, from Gerd Rausch. 8) Fix some more fallout from TCQ_F_CAN_BYPASS generalization, from Cong Wang. 9) Fix FIB source validation checks over loopback, also from Cong Wang. 10) Use promisc for unsupported number of filters, from Justin Chen. 11) Missing sibling route unlink on failure in ipv6, from Ido Schimmel. * git://git.kernel.org/pub/scm/linux/kernel/git/davem/net: (90 commits) tcp: fix tcp_set_congestion_control() use from bpf hook ag71xx: fix return value check in ag71xx_probe() ag71xx: fix error return code in ag71xx_probe() usb: qmi_wwan: add D-Link DWM-222 A2 device ID bnxt_en: Fix VNIC accounting when enabling aRFS on 57500 chips. net: dsa: sja1105: Fix missing unlock on error in sk_buff() gve: replace kfree with kvfree selftests/bpf: fix test_xdp_noinline on s390 selftests/bpf: fix "valid read map access into a read-only array 1" on s390 net/mlx5: Replace kfree with kvfree MAINTAINERS: update netsec driver ipv6: Unlink sibling route in case of failure liquidio: Replace vmalloc + memset with vzalloc udp: Fix typo in net/ipv4/udp.c net: bcmgenet: use promisc for unsupported filters ipv6: rt6_check should return NULL if 'from' is NULL tipc: initialize 'validated' field of received packets selftests: add a test case for rp_filter fib: relax source validation check for loopback packets mlxsw: spectrum: Do not process learned records with a dummy FID ...
rbtree_test.c
// SPDX-License-Identifier: GPL-2.0-only
#include <linux/module.h>
#include <linux/moduleparam.h>
#include <linux/rbtree_augmented.h>
#include <linux/random.h>
#include <linux/slab.h>
#include <asm/timex.h>
#define __param(type, name, init, msg) \
static type name = init; \
module_param(name, type, 0444); \
MODULE_PARM_DESC(name, msg);
__param(int, nnodes, 100, "Number of nodes in the rb-tree");
__param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree");
__param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");
struct test_node {
u32 key;
struct rb_node rb;
/* following fields used for testing augmented rbtree functionality */
u32 val;
u32 augmented;
};
static struct rb_root_cached root = RB_ROOT_CACHED;
static struct test_node *nodes = NULL;
static struct rnd_state rnd;
static void insert(struct test_node *node, struct rb_root_cached *root)
{
struct rb_node **new = &root->rb_root.rb_node, *parent = NULL;
u32 key = node->key;
while (*new) {
parent = *new;
if (key < rb_entry(parent, struct test_node, rb)->key)
new = &parent->rb_left;
else
new = &parent->rb_right;
}
rb_link_node(&node->rb, parent, new);
rb_insert_color(&node->rb, &root->rb_root);
}
static void insert_cached(struct test_node *node, struct rb_root_cached *root)
{
struct rb_node **new = &root->rb_root.rb_node, *parent = NULL;
u32 key = node->key;
bool leftmost = true;
while (*new) {
parent = *new;
if (key < rb_entry(parent, struct test_node, rb)->key)
new = &parent->rb_left;
else {
new = &parent->rb_right;
leftmost = false;
}
}
rb_link_node(&node->rb, parent, new);
rb_insert_color_cached(&node->rb, root, leftmost);
}
static inline void erase(struct test_node *node, struct rb_root_cached *root)
{
rb_erase(&node->rb, &root->rb_root);
}
static inline void erase_cached(struct test_node *node, struct rb_root_cached *root)
{
rb_erase_cached(&node->rb, root);
}
static inline u32 augment_recompute(struct test_node *node)
{
u32 max = node->val, child_augmented;
if (node->rb.rb_left) {
child_augmented = rb_entry(node->rb.rb_left, struct test_node,
rb)->augmented;
if (max < child_augmented)
max = child_augmented;
}
if (node->rb.rb_right) {
child_augmented = rb_entry(node->rb.rb_right, struct test_node,
rb)->augmented;
if (max < child_augmented)
max = child_augmented;
}
return max;
}
RB_DECLARE_CALLBACKS(static, augment_callbacks, struct test_node, rb,
u32, augmented, augment_recompute)
static void insert_augmented(struct test_node *node,
struct rb_root_cached *root)
{
struct rb_node **new = &root->rb_root.rb_node, *rb_parent = NULL;
u32 key = node->key;
u32 val = node->val;
struct test_node *parent;
while (*new) {
rb_parent = *new;
parent = rb_entry(rb_parent, struct test_node, rb);
if (parent->augmented < val)
parent->augmented = val;
if (key < parent->key)
new = &parent->rb.rb_left;
else
new = &parent->rb.rb_right;
}
node->augmented = val;
rb_link_node(&node->rb, rb_parent, new);
rb_insert_augmented(&node->rb, &root->rb_root, &augment_callbacks);
}
static void insert_augmented_cached(struct test_node *node,
struct rb_root_cached *root)
{
struct rb_node **new = &root->rb_root.rb_node, *rb_parent = NULL;
u32 key = node->key;
u32 val = node->val;
struct test_node *parent;
bool leftmost = true;
while (*new) {
rb_parent = *new;
parent = rb_entry(rb_parent, struct test_node, rb);
if (parent->augmented < val)
parent->augmented = val;
if (key < parent->key)
new = &parent->rb.rb_left;
else {
new = &parent->rb.rb_right;
leftmost = false;
}
}
node->augmented = val;
rb_link_node(&node->rb, rb_parent, new);
rb_insert_augmented_cached(&node->rb, root,
leftmost, &augment_callbacks);
}
static void erase_augmented(struct test_node *node, struct rb_root_cached *root)
{
rb_erase_augmented(&node->rb, &root->rb_root, &augment_callbacks);
}
static void erase_augmented_cached(struct test_node *node,
struct rb_root_cached *root)
{
rb_erase_augmented_cached(&node->rb, root, &augment_callbacks);
}
static void init(void)
{
int i;
for (i = 0; i < nnodes; i++) {
nodes[i].key = prandom_u32_state(&rnd);
nodes[i].val = prandom_u32_state(&rnd);
}
}
static bool is_red(struct rb_node *rb)
{
return !(rb->__rb_parent_color & 1);
}
static int black_path_count(struct rb_node *rb)
{
int count;
for (count = 0; rb; rb = rb_parent(rb))
count += !is_red(rb);
return count;
}
static void check_postorder_foreach(int nr_nodes)
{
struct test_node *cur, *n;
int count = 0;
rbtree_postorder_for_each_entry_safe(cur, n, &root.rb_root, rb)
count++;
WARN_ON_ONCE(count != nr_nodes);
}
static void check_postorder(int nr_nodes)
{
struct rb_node *rb;
int count = 0;
for (rb = rb_first_postorder(&root.rb_root); rb; rb = rb_next_postorder(rb))
count++;
WARN_ON_ONCE(count != nr_nodes);
}
static void check(int nr_nodes)
{
struct rb_node *rb;
int count = 0, blacks = 0;
u32 prev_key = 0;
for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {
struct test_node *node = rb_entry(rb, struct test_node, rb);
WARN_ON_ONCE(node->key < prev_key);
WARN_ON_ONCE(is_red(rb) &&
(!rb_parent(rb) || is_red(rb_parent(rb))));
if (!count)
blacks = black_path_count(rb);
else
WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) &&
blacks != black_path_count(rb));
prev_key = node->key;
count++;
}
WARN_ON_ONCE(count != nr_nodes);
WARN_ON_ONCE(count < (1 << black_path_count(rb_last(&root.rb_root))) - 1);
check_postorder(nr_nodes);
check_postorder_foreach(nr_nodes);
}
static void check_augmented(int nr_nodes)
{
struct rb_node *rb;
check(nr_nodes);
for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {
struct test_node *node = rb_entry(rb, struct test_node, rb);
WARN_ON_ONCE(node->augmented != augment_recompute(node));
}
}
static int __init rbtree_test_init(void)
{
int i, j;
cycles_t time1, time2, time;
struct rb_node *node;
nodes = kmalloc_array(nnodes, sizeof(*nodes), GFP_KERNEL);
if (!nodes)
return -ENOMEM;
printk(KERN_ALERT "rbtree testing");
prandom_seed_state(&rnd, 3141592653589793238ULL);
init();
time1 = get_cycles();
for (i = 0; i < perf_loops; i++) {
for (j = 0; j < nnodes; j++)
insert(nodes + j, &root);
for (j = 0; j < nnodes; j++)
erase(nodes + j, &root);
}
time2 = get_cycles();
time = time2 - time1;
time = div_u64(time, perf_loops);
printk(" -> test 1 (latency of nnodes insert+delete): %llu cycles\n",
(unsigned long long)time);
time1 = get_cycles();
for (i = 0; i < perf_loops; i++) {
for (j = 0; j < nnodes; j++)
insert_cached(nodes + j, &root);
for (j = 0; j < nnodes; j++)
erase_cached(nodes + j, &root);
}
time2 = get_cycles();
time = time2 - time1;
time = div_u64(time, perf_loops);
printk(" -> test 2 (latency of nnodes cached insert+delete): %llu cycles\n",
(unsigned long long)time);
for (i = 0; i < nnodes; i++)
insert(nodes + i, &root);
time1 = get_cycles();
for (i = 0; i < perf_loops; i++) {
for (node = rb_first(&root.rb_root); node; node = rb_next(node))
;
}
time2 = get_cycles();
time = time2 - time1;
time = div_u64(time, perf_loops);
printk(" -> test 3 (latency of inorder traversal): %llu cycles\n",
(unsigned long long)time);
time1 = get_cycles();
for (i = 0; i < perf_loops; i++)
node = rb_first(&root.rb_root);
time2 = get_cycles();
time = time2 - time1;
time = div_u64(time, perf_loops);
printk(" -> test 4 (latency to fetch first node)\n");
printk(" non-cached: %llu cycles\n", (unsigned long long)time);
time1 = get_cycles();
for (i = 0; i < perf_loops; i++)
node = rb_first_cached(&root);
time2 = get_cycles();
time = time2 - time1;
time = div_u64(time, perf_loops);
printk(" cached: %llu cycles\n", (unsigned long long)time);
for (i = 0; i < nnodes; i++)
erase(nodes + i, &root);
/* run checks */
for (i = 0; i < check_loops; i++) {
init();
for (j = 0; j < nnodes; j++) {
check(j);
insert(nodes + j, &root);
}
for (j = 0; j < nnodes; j++) {
check(nnodes - j);
erase(nodes + j, &root);
}
check(0);
}
printk(KERN_ALERT "augmented rbtree testing");
init();
time1 = get_cycles();
for (i = 0; i < perf_loops; i++) {
for (j = 0; j < nnodes; j++)
insert_augmented(nodes + j, &root);
for (j = 0; j < nnodes; j++)
erase_augmented(nodes + j, &root);
}
time2 = get_cycles();
time = time2 - time1;
time = div_u64(time, perf_loops);
printk(" -> test 1 (latency of nnodes insert+delete): %llu cycles\n", (unsigned long long)time);
time1 = get_cycles();
for (i = 0; i < perf_loops; i++) {
for (j = 0; j < nnodes; j++)
insert_augmented_cached(nodes + j, &root);
for (j = 0; j < nnodes; j++)
erase_augmented_cached(nodes + j, &root);
}
time2 = get_cycles();
time = time2 - time1;
time = div_u64(time, perf_loops);
printk(" -> test 2 (latency of nnodes cached insert+delete): %llu cycles\n", (unsigned long long)time);
for (i = 0; i < check_loops; i++) {
init();
for (j = 0; j < nnodes; j++) {
check_augmented(j);
insert_augmented(nodes + j, &root);
}
for (j = 0; j < nnodes; j++) {
check_augmented(nnodes - j);
erase_augmented(nodes + j, &root);
}
check_augmented(0);
}
kfree(nodes);
return -EAGAIN; /* Fail will directly unload the module */
}
static void __exit rbtree_test_exit(void)
{
printk(KERN_ALERT "test exit\n");
}
module_init(rbtree_test_init)
module_exit(rbtree_test_exit)
MODULE_LICENSE("GPL");
MODULE_AUTHOR("Michel Lespinasse");
MODULE_DESCRIPTION("Red Black Tree test");
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...