#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"); s='oid'>b272f732f888d4cf43c943a40c9aaa836f9b7431 (diff)parent1f3a8e49d8f28f498b8694464623ac20aebfe62a (diff)
Merge branch 'timers-urgent-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip
Pull timer type cleanups from Thomas Gleixner: "This series does a tree wide cleanup of types related to timers/timekeeping. - Get rid of cycles_t and use a plain u64. The type is not really helpful and caused more confusion than clarity - Get rid of the ktime union. The union has become useless as we use the scalar nanoseconds storage unconditionally now. The 32bit timespec alike storage got removed due to the Y2038 limitations some time ago. That leaves the odd union access around for no reason. Clean it up. Both changes have been done with coccinelle and a small amount of manual mopping up" * 'timers-urgent-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip: ktime: Get rid of ktime_equal() ktime: Cleanup ktime_set() usage ktime: Get rid of the union clocksource: Use a plain u64 instead of cycle_t
Diffstat (limited to 'include/uapi/rdma/hfi')