#include #include #include #include #define NODES 100 #define PERF_LOOPS 100000 #define CHECK_LOOPS 100 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 root = RB_ROOT; static struct test_node nodes[NODES]; static struct rnd_state rnd; static void insert(struct test_node *node, struct rb_root *root) { struct rb_node **new = &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); } static inline void erase(struct test_node *node, struct rb_root *root) { rb_erase(&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 *root) { struct rb_node **new = &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, &augment_callbacks); } static void erase_augmented(struct test_node *node, struct rb_root *root) { rb_erase_augmented(&node->rb, root, &augment_callbacks); } static void init(void) { int i; for (i = 0; i < NODES; 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) 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; 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; 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))) - 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; 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; 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 < NODES; j++) insert(nodes + j, &root); for (j = 0; j < NODES; j++) erase(nodes + j, &root); } time2 = get_cycles(); time = time2 - time1; time = div_u64(time, PERF_LOOPS); printk(" -> %llu cycles\n", (unsigned long long)time); for (i = 0; i < CHECK_LOOPS; i++) { init(); for (j = 0; j < NODES; j++) { check(j); insert(nodes + j, &root); } for (j = 0; j < NODES; j++) { check(NODES - 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 < NODES; j++) insert_augmented(nodes + j, &root); for (j = 0; j < NODES; j++) erase_augmented(nodes + j, &root); } time2 = get_cycles(); time = time2 - time1; time = div_u64(time, PERF_LOOPS); printk(" -> %llu cycles\n", (unsigned long long)time); for (i = 0; i < CHECK_LOOPS; i++) { init(); for (j = 0; j < NODES; j++) { check_augmented(j); insert_augmented(nodes + j, &root); } for (j = 0; j < NODES; j++) { check_augmented(NODES - j); erase_augmented(nodes + j, &root); } check_augmented(0); } 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"); 244473074fc0612c169e2e043d58b01'>Merge git://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-nextDavid S. Miller11-40/+60 2017-02-03sched: cls_flower: expose priority to offloading netdeviceJiri Pirko1-0/+1 2017-02-03lib: Introduce priority array area managerJiri Pirko1-0/+76 2017-02-03list: introduce list_for_each_entry_from_reverse helperJiri Pirko1-0/+13 2017-02-03trace: rename trace_print_hex_seq arg and add kdocDaniel Borkmann2-3/+3 2017-02-03bridge: uapi: add per vlan tunnel infoRoopa Prabhu3-0/+13 2017-02-03vxlan: support fdb and learning in COLLECT_METADATA modeRoopa Prabhu1-0/+1 2017-02-03ip_tunnels: new IP_TUNNEL_INFO_BRIDGE flag for ip_tunnel_info modeRoopa Prabhu1-0/+1 2017-02-03net/sched: act_ife: Change to use ife moduleYotam Gigi2-10/+1 2017-02-03net: Introduce ife encapsulation moduleYotam Gigi3-0/+70 2017-02-03net/sched: act_ife: Unexport ife_tlv_meta_encodeYotam Gigi1-2/+0 2017-02-03tcp: add tcp_mss_clamp() helperEric Dumazet1-0/+9 2017-02-02net: add LINUX_MIB_PFMEMALLOCDROP counterEric Dumazet1-0/+1 2017-02-02net: phy: marvell: Add support for 88e1545 PHYAndrew Lunn1-0/+1 2017-02-02unix: add ioctl to open a unix socket file with O_PATHAndrey Vagin1-0/+2 2017-02-02net: phy: Marvell: Add mv88e6390 internal PHYAndrew Lunn1-0/+6 2017-02-02Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/netDavid S. Miller9-30/+40 2017-02-02netfilter: allow logging from non-init namespacesMichal Kubeček1-0/+3 2017-02-02ipvs: free ip_vs_dest structs when refcnt=0David Windsor1-1/+1 2017-02-02netfilter: merge ctinfo into nfct pointer storage areaFlorian Westphal2-17/+15 2017-02-02netfilter: guarantee 8 byte minalign for template addressesFlorian Westphal1-0/+2 2017-02-02netfilter: add and use nf_ct_set helperFlorian Westphal2-2/+9 2017-02-02skbuff: add and use skb_nfct helperFlorian Westphal2-4/+11 2017-02-02netfilter: reduce direct skb->nfct usageFlorian Westphal1-3/+6 2017-02-02netfilter: conntrack: no need to pass ctinfo to error handlerFlorian Westphal1-1/+1