From 05af21eed40faf17e414b1c351cbd52bb7cf7ab4 Mon Sep 17 00:00:00 2001 From: jxiong Date: Tue, 29 Jan 2008 13:28:12 +0000 Subject: [PATCH] Use interval tree to eliminate the extent lock traverse overhead in ost side. b=11300 r=vitaly,nikita --- lustre/include/interval_tree.h | 106 ++++++ lustre/ldlm/interval_tree.c | 745 +++++++++++++++++++++++++++++++++++++++++ lustre/tests/it_test.c | 522 +++++++++++++++++++++++++++++ 3 files changed, 1373 insertions(+) create mode 100644 lustre/include/interval_tree.h create mode 100644 lustre/ldlm/interval_tree.c create mode 100644 lustre/tests/it_test.c diff --git a/lustre/include/interval_tree.h b/lustre/include/interval_tree.h new file mode 100644 index 0000000..41436c1 --- /dev/null +++ b/lustre/include/interval_tree.h @@ -0,0 +1,106 @@ +/* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*- + * (visit-tags-table FILE) + * vim:expandtab:shiftwidth=8:tabstop=8: + * + * Copyright (c) 2002, 2007 Cluster File Systems, Inc. + * Author: Huang Wei + * Author: Jay Xiong + * + * This file is part of the Lustre file system, http://www.lustre.org + * Lustre is a trademark of Cluster File Systems, Inc. + * + * You may have signed or agreed to another license before downloading + * this software. If so, you are bound by the terms and conditions + * of that agreement, and the following does not apply to you. See the + * LICENSE file included with this distribution for more information. + * + * If you did not agree to a different license, then this copy of Lustre + * is open source software; you can redistribute it and/or modify it + * under the terms of version 2 of the GNU General Public License as + * published by the Free Software Foundation. + * + * In either case, Lustre is distributed in the hope that it will be + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * license text for more details. + */ + +#ifndef _INTERVAL_H__ +#define _INTERVAL_H__ + +#include /* __u8, __u64 etc. */ +#include /* LASSERT. */ + +struct interval_node { + struct interval_node *in_left; + struct interval_node *in_right; + struct interval_node *in_parent; + __u8 in_color; + __u8 res1[7]; /* tags, 8-bytes aligned */ + __u64 in_max_high; + struct interval_node_extent { + __u64 start; + __u64 end; + } in_extent; +}; + +enum interval_iter { + INTERVAL_ITER_CONT = 1, + INTERVAL_ITER_STOP = 2 +}; + +static inline __u64 interval_low(struct interval_node *node) +{ + return node->in_extent.start; +} + +static inline __u64 interval_high(struct interval_node *node) +{ + return node->in_extent.end; +} + +static inline void interval_set(struct interval_node *node, + __u64 start, __u64 end) +{ + LASSERT(start <= end); + node->in_extent.start = start; + node->in_extent.end = end; + node->in_max_high = end; +} + +/* Rules to write an interval callback. + * - the callback returns INTERVAL_ITER_STOP when it thinks the iteration + * should be stopped. It will then cause the iteration function to return + * immediately with return value INTERVAL_ITER_STOP. + * - callbacks for interval_iterate and interval_iterate_reverse: Every + * nodes in the tree will be set to @node before the callback being called + * - callback for interval_search: Only overlapped node will be set to @node + * before the callback being called. + */ +typedef enum interval_iter (*interval_callback_t)(struct interval_node *node, + void *args); + +struct interval_node *interval_insert(struct interval_node *node, + struct interval_node **root); +void interval_erase(struct interval_node *node, struct interval_node **root); + +/* Search the extents in the tree and call @func for each overlapped + * extents. */ +enum interval_iter interval_search(struct interval_node *root, + struct interval_node_extent *ex, + interval_callback_t func, void *data); + +/* Iterate every node in the tree - by reverse order or regular order. */ +enum interval_iter interval_iterate(struct interval_node *root, + interval_callback_t func, void *data); +enum interval_iter interval_iterate_reverse(struct interval_node *root, + interval_callback_t func,void *data); + +void interval_expand(struct interval_node *root, + struct interval_node_extent *ext, + struct interval_node_extent *limiter); +int interval_is_overlapped(struct interval_node *root, + struct interval_node_extent *ex); +struct interval_node *interval_find(struct interval_node *root, + struct interval_node_extent *ex); +#endif diff --git a/lustre/ldlm/interval_tree.c b/lustre/ldlm/interval_tree.c new file mode 100644 index 0000000..e119fff --- /dev/null +++ b/lustre/ldlm/interval_tree.c @@ -0,0 +1,745 @@ +/* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*- + * vim:expandtab:shiftwidth=8:tabstop=8: + * + * Interval tree library used by ldlm extent lock code + * + * Copyright (c) 2007 Cluster File Systems, Inc. + * Author: Huang Wei + * Author: Jay Xiong + * + * This file is part of the Lustre file system, http://www.lustre.org + * Lustre is a trademark of Cluster File Systems, Inc. + * + * You may have signed or agreed to another license before downloading + * this software. If so, you are bound by the terms and conditions + * of that agreement, and the following does not apply to you. See the + * LICENSE file included with this distribution for more information. + * + * If you did not agree to a different license, then this copy of Lustre + * is open source software; you can redistribute it and/or modify it + * under the terms of version 2 of the GNU General Public License as + * published by the Free Software Foundation. + * + * In either case, Lustre is distributed in the hope that it will be + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * license text for more details. + */ +#include + +enum { + INTERVAL_RED = 0, + INTERVAL_BLACK = 1 +}; + +static inline int node_is_left_child(struct interval_node *node) +{ + LASSERT(node->in_parent != NULL); + return node == node->in_parent->in_left; +} + +static inline int node_is_right_child(struct interval_node *node) +{ + LASSERT(node->in_parent != NULL); + return node == node->in_parent->in_right; +} + +static inline int node_is_red(struct interval_node *node) +{ + return node->in_color == INTERVAL_RED; +} + +static inline int node_is_black(struct interval_node *node) +{ + return node->in_color == INTERVAL_BLACK; +} + +static inline int extent_compare(struct interval_node_extent *e1, + struct interval_node_extent *e2) +{ + int rc; + if (e1->start == e2->start) { + if (e1->end < e2->end) + rc = -1; + else if (e1->end > e2->end) + rc = 1; + else + rc = 0; + } else { + if (e1->start < e2->start) + rc = -1; + else + rc = 1; + } + return rc; +} + +static inline int extent_equal(struct interval_node_extent *e1, + struct interval_node_extent *e2) +{ + return (e1->start == e2->start) && (e1->end == e2->end); +} + +static inline int extent_overlapped(struct interval_node_extent *e1, + struct interval_node_extent *e2) +{ + return (e1->start <= e2->end) && (e2->start <= e1->end); +} + +static inline int node_compare(struct interval_node *n1, + struct interval_node *n2) +{ + return extent_compare(&n1->in_extent, &n2->in_extent); +} + +static inline int node_equal(struct interval_node *n1, + struct interval_node *n2) +{ + return extent_equal(&n1->in_extent, &n2->in_extent); +} + +static inline __u64 max_u64(__u64 x, __u64 y) +{ + return x > y ? x : y; +} + +static inline __u64 min_u64(__u64 x, __u64 y) +{ + return x < y ? x : y; +} + +#define interval_for_each(node, root) \ +for (node = interval_first(root); node != NULL; \ + node = interval_next(node)) + +#define interval_for_each_reverse(node, root) \ +for (node = interval_last(root); node != NULL; \ + node = interval_prev(node)) + +static struct interval_node *interval_first(struct interval_node *node) +{ + ENTRY; + + if (!node) + RETURN(NULL); + while (node->in_left) + node = node->in_left; + RETURN(node); +} + +static struct interval_node *interval_last(struct interval_node *node) +{ + ENTRY; + + if (!node) + RETURN(NULL); + while (node->in_right) + node = node->in_right; + RETURN(node); +} + +static struct interval_node *interval_next(struct interval_node *node) +{ + ENTRY; + + if (!node) + RETURN(NULL); + if (node->in_right) + RETURN(interval_first(node->in_right)); + while (node->in_parent && node_is_right_child(node)) + node = node->in_parent; + RETURN(node->in_parent); +} + +static struct interval_node *interval_prev(struct interval_node *node) +{ + ENTRY; + + if (!node) + RETURN(NULL); + + if (node->in_left) + RETURN(interval_last(node->in_left)); + + while (node->in_parent && node_is_left_child(node)) + node = node->in_parent; + + RETURN(node->in_parent); +} + +enum interval_iter interval_iterate(struct interval_node *root, + interval_callback_t func, + void *data) +{ + struct interval_node *node; + enum interval_iter rc = INTERVAL_ITER_CONT; + ENTRY; + + interval_for_each(node, root) { + rc = func(node, data); + if (rc == INTERVAL_ITER_STOP) + break; + } + + RETURN(rc); +} +EXPORT_SYMBOL(interval_iterate); + +enum interval_iter interval_iterate_reverse(struct interval_node *root, + interval_callback_t func, + void *data) +{ + struct interval_node *node; + enum interval_iter rc = INTERVAL_ITER_CONT; + ENTRY; + + interval_for_each_reverse(node, root) { + rc = func(node, data); + if (rc == INTERVAL_ITER_STOP) + break; + } + + RETURN(rc); +} +EXPORT_SYMBOL(interval_iterate_reverse); + +/* try to find a node with same interval in the tree, + * if found, return the pointer to the node, otherwise return NULL*/ +struct interval_node *interval_find(struct interval_node *root, + struct interval_node_extent *ex) +{ + struct interval_node *walk = root; + int rc; + ENTRY; + + while (walk) { + rc = extent_compare(ex, &walk->in_extent); + if (rc == 0) + break; + else if (rc < 0) + walk = walk->in_left; + else + walk = walk->in_right; + } + + RETURN(walk); +} +EXPORT_SYMBOL(interval_find); + +static void __rotate_change_maxhigh(struct interval_node *node, + struct interval_node *rotate) +{ + __u64 left_max, right_max; + + rotate->in_max_high = node->in_max_high; + left_max = node->in_left ? node->in_left->in_max_high : 0; + right_max = node->in_right ? node->in_right->in_max_high : 0; + node->in_max_high = max_u64(interval_high(node), + max_u64(left_max,right_max)); +} + +/* The left rotation "pivots" around the link from node to node->right, and + * - node will be linked to node->right's left child, and + * - node->right's left child will be linked to node's right child. */ +static void __rotate_left(struct interval_node *node, + struct interval_node **root) +{ + struct interval_node *right = node->in_right; + struct interval_node *parent = node->in_parent; + + node->in_right = right->in_left; + if (node->in_right) + right->in_left->in_parent = node; + + right->in_left = node; + right->in_parent = parent; + if (parent) { + if (node_is_left_child(node)) + parent->in_left = right; + else + parent->in_right = right; + } else { + *root = right; + } + node->in_parent = right; + + /* update max_high for node and right */ + __rotate_change_maxhigh(node, right); +} + +/* The right rotation "pivots" around the link from node to node->left, and + * - node will be linked to node->left's right child, and + * - node->left's right child will be linked to node's left child. */ +static void __rotate_right(struct interval_node *node, + struct interval_node **root) +{ + struct interval_node *left = node->in_left; + struct interval_node *parent = node->in_parent; + + node->in_left = left->in_right; + if (node->in_left) + left->in_right->in_parent = node; + left->in_right = node; + + left->in_parent = parent; + if (parent) { + if (node_is_right_child(node)) + parent->in_right = left; + else + parent->in_left = left; + } else { + *root = left; + } + node->in_parent = left; + + /* update max_high for node and left */ + __rotate_change_maxhigh(node, left); +} + +#define interval_swap(a, b) do { \ + struct interval_node *c = a; a = b; b = c; \ +} while (0) + +/* + * Operations INSERT and DELETE, when run on a tree with n keys, + * take O(logN) time.Because they modify the tree, the result + * may violate the red-black properties.To restore these properties, + * we must change the colors of some of the nodes in the tree + * and also change the pointer structure. + */ +static void interval_insert_color(struct interval_node *node, + struct interval_node **root) +{ + struct interval_node *parent, *gparent; + ENTRY; + + while ((parent = node->in_parent) && node_is_red(parent)) { + gparent = parent->in_parent; + /* Parent is RED, so gparent must not be NULL */ + if (node_is_left_child(parent)) { + struct interval_node *uncle; + uncle = gparent->in_right; + if (uncle && node_is_red(uncle)) { + uncle->in_color = INTERVAL_BLACK; + parent->in_color = INTERVAL_BLACK; + gparent->in_color = INTERVAL_RED; + node = gparent; + continue; + } + + if (parent->in_right == node) { + __rotate_left(parent, root); + interval_swap(node, parent); + } + + parent->in_color = INTERVAL_BLACK; + gparent->in_color = INTERVAL_RED; + __rotate_right(gparent, root); + } else { + struct interval_node *uncle; + uncle = gparent->in_left; + if (uncle && node_is_red(uncle)) { + uncle->in_color = INTERVAL_BLACK; + parent->in_color = INTERVAL_BLACK; + gparent->in_color = INTERVAL_RED; + node = gparent; + continue; + } + + if (node_is_left_child(node)) { + __rotate_right(parent, root); + interval_swap(node, parent); + } + + parent->in_color = INTERVAL_BLACK; + gparent->in_color = INTERVAL_RED; + __rotate_left(gparent, root); + } + } + + (*root)->in_color = INTERVAL_BLACK; + EXIT; +} + +struct interval_node *interval_insert(struct interval_node *node, + struct interval_node **root) + +{ + struct interval_node **p, *parent = NULL; + ENTRY; + + p = root; + while (*p) { + parent = *p; + if (node_equal(parent, node)) + RETURN(parent); + + /* max_high field must be updated after each iteration */ + if (parent->in_max_high < interval_high(node)) + parent->in_max_high = interval_high(node); + + if (node_compare(node, parent) < 0) + p = &parent->in_left; + else + p = &parent->in_right; + } + + /* link node into the tree */ + node->in_parent = parent; + node->in_color = INTERVAL_RED; + node->in_left = node->in_right = NULL; + *p = node; + + interval_insert_color(node, root); + + RETURN(NULL); +} +EXPORT_SYMBOL(interval_insert); + +static inline int node_is_black_or_0(struct interval_node *node) +{ + return !node || node_is_black(node); +} + +static void interval_erase_color(struct interval_node *node, + struct interval_node *parent, + struct interval_node **root) +{ + struct interval_node *tmp; + ENTRY; + + while (node_is_black_or_0(node) && node != *root) { + if (parent->in_left == node) { + tmp = parent->in_right; + if (node_is_red(tmp)) { + tmp->in_color = INTERVAL_BLACK; + parent->in_color = INTERVAL_RED; + __rotate_left(parent, root); + tmp = parent->in_right; + } + if (node_is_black_or_0(tmp->in_left) && + node_is_black_or_0(tmp->in_right)) { + tmp->in_color = INTERVAL_RED; + node = parent; + parent = node->in_parent; + } else { + if (node_is_black_or_0(tmp->in_right)) { + struct interval_node *o_left; + if ((o_left = tmp->in_left)) + o_left->in_color = INTERVAL_BLACK; + tmp->in_color = INTERVAL_RED; + __rotate_right(tmp, root); + tmp = parent->in_right; + } + tmp->in_color = parent->in_color; + parent->in_color = INTERVAL_BLACK; + if (tmp->in_right) + tmp->in_right->in_color = INTERVAL_BLACK; + __rotate_left(parent, root); + node = *root; + break; + } + } else { + tmp = parent->in_left; + if (node_is_red(tmp)) { + tmp->in_color = INTERVAL_BLACK; + parent->in_color = INTERVAL_RED; + __rotate_right(parent, root); + tmp = parent->in_left; + } + if (node_is_black_or_0(tmp->in_left) && + node_is_black_or_0(tmp->in_right)) { + tmp->in_color = INTERVAL_RED; + node = parent; + parent = node->in_parent; + } else { + if (node_is_black_or_0(tmp->in_left)) { + struct interval_node *o_right; + if ((o_right = tmp->in_right)) + o_right->in_color = INTERVAL_BLACK; + tmp->in_color = INTERVAL_RED; + __rotate_left(tmp, root); + tmp = parent->in_left; + } + tmp->in_color = parent->in_color; + parent->in_color = INTERVAL_BLACK; + if (tmp->in_left) + tmp->in_left->in_color = INTERVAL_BLACK; + __rotate_right(parent, root); + node = *root; + break; + } + } + } + if (node) + node->in_color = INTERVAL_BLACK; + EXIT; +} + +/* + * if the @max_high value of @node is changed, this function traverse a path + * from node up to the root to update max_high for the whole tree. + */ +static void update_maxhigh(struct interval_node *node, + __u64 old_maxhigh) +{ + __u64 left_max, right_max; + ENTRY; + + while (node) { + left_max = node->in_left ? node->in_left->in_max_high : 0; + right_max = node->in_right ? node->in_right->in_max_high : 0; + node->in_max_high = max_u64(interval_high(node), + max_u64(left_max, right_max)); + + if (node->in_max_high >= old_maxhigh) + break; + node = node->in_parent; + } + EXIT; +} + +void interval_erase(struct interval_node *node, + struct interval_node **root) +{ + struct interval_node *child, *parent; + int color; + ENTRY; + + if (!node->in_left) { + child = node->in_right; + } else if (!node->in_right) { + child = node->in_left; + } else { /* Both left and right child are not NULL */ + struct interval_node *old = node; + + node = interval_next(node); + child = node->in_right; + parent = node->in_parent; + color = node->in_color; + + if (child) + child->in_parent = parent; + if (parent == old) { + parent->in_right = child; + parent = node; + } else { + parent->in_left = child; + } + + node->in_color = old->in_color; + node->in_right = old->in_right; + node->in_left = old->in_left; + node->in_parent = old->in_parent; + + if (old->in_parent) { + if (node_is_left_child(old)) + old->in_parent->in_left = node; + else + old->in_parent->in_right = node; + } else { + *root = node; + } + + old->in_left->in_parent = node; + if (old->in_right) + old->in_right->in_parent = node; + update_maxhigh(child, node->in_max_high); + update_maxhigh(node, old->in_max_high); + goto color; + } + parent = node->in_parent; + color = node->in_color; + + if (child) + child->in_parent = parent; + if (parent) { + if (node_is_left_child(node)) + parent->in_left = child; + else + parent->in_right = child; + } else { + *root = child; + } + + update_maxhigh(child, node->in_max_high); + +color: + if (color == INTERVAL_BLACK) + interval_erase_color(child, parent, root); + EXIT; +} +EXPORT_SYMBOL(interval_erase); + +static inline int interval_may_overlap(struct interval_node *node, + struct interval_node_extent *ext) +{ + return (ext->start <= node->in_max_high && + ext->end >= interval_low(node)); +} + +/* + * This function finds all intervals that overlap interval ext, + * and calls func to handle resulted intervals one by one. + * in lustre, this function will find all conflicting locks in + * the granted queue and add these locks to the ast work list. + * + * { + * if (node == NULL) + * return 0; + * if (ext->end < interval_low(node)) { + * interval_search(node->in_left, ext, func, data); + * } else if (interval_may_overlap(node, ext)) { + * if (extent_overlapped(ext, &node->in_extent)) + * func(node, data); + * interval_search(node->in_left, ext, func, data); + * interval_search(node->in_right, ext, func, data); + * } + * return 0; + * } + * + */ +enum interval_iter interval_search(struct interval_node *node, + struct interval_node_extent *ext, + interval_callback_t func, + void *data) +{ + struct interval_node *parent; + enum interval_iter rc = INTERVAL_ITER_CONT; + + LASSERT(ext != NULL); + LASSERT(func != NULL); + + while (node) { + if (ext->end < interval_low(node)) { + if (node->in_left) { + node = node->in_left; + continue; + } + } else if (interval_may_overlap(node, ext)) { + if (extent_overlapped(ext, &node->in_extent)) { + rc = func(node, data); + if (rc == INTERVAL_ITER_STOP) + break; + } + + if (node->in_left) { + node = node->in_left; + continue; + } + if (node->in_right) { + node = node->in_right; + continue; + } + } + + parent = node->in_parent; + while (parent) { + if (node_is_left_child(node) && + parent->in_right) { + /* If we ever got the left, it means that the + * parent met ext->endin_right; + break; + } + node = parent; + parent = parent->in_parent; + } + if (parent == NULL || !interval_may_overlap(parent, ext)) + break; + } + + return rc; +} +EXPORT_SYMBOL(interval_search); + +static enum interval_iter interval_overlap_cb(struct interval_node *n, + void *args) +{ + *(int *)args = 1; + return INTERVAL_ITER_STOP; +} + +int interval_is_overlapped(struct interval_node *root, + struct interval_node_extent *ext) +{ + int has = 0; + (void)interval_search(root, ext, interval_overlap_cb, &has); + return has; +} +EXPORT_SYMBOL(interval_is_overlapped); + +/* Don't expand to low. Expanding downwards is expensive, and meaningless to + * some extents, because programs seldom do IO backward. + * + * The recursive algorithm of expanding low: + * expand_low { + * struct interval_node *tmp; + * static __u64 res = 0; + * + * if (root == NULL) + * return res; + * if (root->in_max_high < low) { + * res = max_u64(root->in_max_high + 1, res); + * return res; + * } else if (low < interval_low(root)) { + * interval_expand_low(root->in_left, low); + * return res; + * } + * + * if (interval_high(root) < low) + * res = max_u64(interval_high(root) + 1, res); + * interval_expand_low(root->in_left, low); + * interval_expand_low(root->in_right, low); + * + * return res; + * } + * + * It's much easy to eliminate the recursion, see interval_search for + * an example. -jay + */ +static inline __u64 interval_expand_low(struct interval_node *root, __u64 low) +{ + /* we only concern the empty tree right now. */ + if (root == NULL) + return 0; + return low; +} + +static inline __u64 interval_expand_high(struct interval_node *node, __u64 high) +{ + __u64 result = ~0; + + while (node != NULL) { + if (node->in_max_high < high) + break; + + if (interval_low(node) > high) { + result = interval_low(node) - 1; + node = node->in_left; + } else { + node = node->in_right; + } + } + + return result; +} + +/* expanding the extent based on @ext. */ +void interval_expand(struct interval_node *root, + struct interval_node_extent *ext, + struct interval_node_extent *limiter) +{ + /* The assertion of interval_is_overlapped is expensive because we may + * travel many nodes to find the overlapped node. */ + LASSERT(interval_is_overlapped(root, ext) == 0); + if (!limiter || limiter->start < ext->start) + ext->start = interval_expand_low(root, ext->start); + if (!limiter || limiter->end > ext->end) + ext->end = interval_expand_high(root, ext->end); + LASSERT(interval_is_overlapped(root, ext) == 0); +} +EXPORT_SYMBOL(interval_expand); diff --git a/lustre/tests/it_test.c b/lustre/tests/it_test.c new file mode 100644 index 0000000..9e45671 --- /dev/null +++ b/lustre/tests/it_test.c @@ -0,0 +1,522 @@ +/* vi:set ts=8 sw=8 expandtab: */ +/* Unit test tool for interval tree. + * Written by jay + */ +#include +#include +#include +#include + +/* warning remove */ +#undef EXPORT_SYMBOL +#define EXPORT_SYMBOL(a) +#include <../ldlm/interval_tree.c> + +#define dprintf(fmt, args...) //printf(fmt, ##args) +#define error(fmt, args...) do { \ + fflush(stdout), fflush(stderr); \ + fprintf(stderr, "\nError:" fmt, ##args); \ + abort(); \ +} while(0) + +#define __F(ext) (ext)->start, (ext)->end +#define __S "[%llx:%llx]" + +#define ALIGN_SIZE 4096 +#define ALIGN_MASK (~(ALIGN_SIZE - 1)) + +static struct it_node { + struct interval_node node; + struct list_head list; + int hit, valid; +} *it_array; +static int it_count; +static struct list_head header = LIST_HEAD_INIT(header); +static unsigned long max_count = ULONG_MAX & ALIGN_MASK; +static int have_wide_lock = 0; + +static void it_test_clear(void) +{ + int i = 0; + for (i = 0; i < it_count; i++) + it_array[i].hit = 0; +} + +static enum interval_iter cb(struct interval_node *n, void *args) +{ + struct it_node *node = (struct it_node *)n; + static int count = 1; + + if (node->hit == 1) { + dprintf("NODE "__S" has ever been accessed\n", + __F(&n->in_extent)); + return INTERVAL_ITER_CONT; + error("duplicate node accessing found\n"); + return INTERVAL_ITER_STOP; + } + + if (node->valid == 0) { + error("A deleted node "__S" being accessed\n", + __F(&n->in_extent)); + return INTERVAL_ITER_STOP; + } + + if (count++ == 8) { + dprintf("\n"); + count = 1; + } + dprintf(""__S" ", __F(&n->in_extent)); + fflush(stdout); + + node->hit = 1; + return INTERVAL_ITER_CONT; +} + +static int it_test_search(struct interval_node *root) +{ + struct it_node *n; + struct interval_node_extent ext; + int times = 10, i, err = 0; + + while (times--) { + it_test_clear(); + ext.start = (random() % max_count) & ALIGN_MASK; + ext.end = random() % (max_count - ext.start + 2) + ext.start; + ext.end &= ALIGN_MASK; + if (ext.end > max_count) + ext.end = max_count; + + dprintf("\n\nSearching the node overlapped "__S" ..\n", + __F(&ext)); + + interval_search(root, &ext, cb, NULL); + + dprintf("\nverifing ..."); + + /* verify */ + for (i = 0; i < it_count; i++) { + n = &it_array[i]; + if (n->valid == 0) + continue; + + if (extent_overlapped(&ext, &n->node.in_extent) && + n->hit == 0) + error("node "__S" overlaps" __S"," + "but never to be hit.\n", + __F(&n->node.in_extent), + __F(&ext)); + + if (!extent_overlapped(&ext, &n->node.in_extent) && + n->hit) + error("node "__S" overlaps" __S", but hit.\n", + __F(&n->node.in_extent), + __F(&ext)); + } + if (err) error("search error\n"); + dprintf("ok.\n"); + } + + return 0; +} + +static int it_test_iterate(struct interval_node *root) +{ + int i; + + dprintf("\n\nIterate testing start..\n"); + + it_test_clear(); + interval_iterate(root, cb, NULL); + + /* verify */ + for (i = 0; i < it_count; i++) { + if (it_array[i].valid == 0) + continue; + if (it_array[i].hit == 0) + error("Node "__S" is not accessed\n", + __F(&it_array[i].node.in_extent)); + } + + return 0; +} + +static int it_test_iterate_reverse(struct interval_node *root) +{ + int i; + + dprintf("\n\niterate reverse testing start..\n"); + it_test_clear(); + interval_iterate_reverse(root, cb, NULL); + + /* verify */ + for (i = 0; i < it_count; i++) { + if (it_array[i].valid == 0) + continue; + if (it_array[i].hit == 0) + error("Not every extent is accessed\n"); + } + + return 0; +} + +static int it_test_find(struct interval_node *root) +{ + int idx; + struct interval_node_extent *ext; + + dprintf("\ninterval_find testing start ..\n"); + for (idx = 0; idx < it_count; idx++) { + if (it_array[idx].valid == 0) + continue; + + ext = &it_array[idx].node.in_extent; + dprintf("Try to find "__S"\n", __F(ext)); + if (!interval_find(root, ext)) + error("interval_find, try to find "__S"\n", __F(ext)); + } + return 0; +} + +/* sanity test is tightly coupled with implementation, so when you changed + * the interval tree implementation, change this code also. */ +static enum interval_iter sanity_cb(struct interval_node *node, void *args) +{ + __u64 max_high = node->in_max_high; + struct interval_node *tmp, *parent; + int left = 1, has = 0, nr = 0; + + parent = node->in_parent; + node->in_parent = NULL; + interval_for_each(tmp, node) { + if ((left && node_compare(tmp, node) > 0) || + (!left && node_compare(tmp, node) < 0)) + error("interval tree sanity test\n"); + + if (tmp->in_max_high > max_high) { + dprintf("max high sanity check, max_high is %llu," + "child max_high: %llu"__S"\n", + max_high, tmp->in_max_high, + __F(&tmp->in_extent)); + goto err; + } else if (tmp->in_max_high == max_high) { + has = 1; + } + + if (tmp == node) { + left = 0; + continue; + } + } + + if (!has) { + int count = 1; +err: + dprintf("node"__S":%llu Child list:\n", + node->in_extent.start, + node->in_extent.end, + node->in_max_high); + + interval_for_each(tmp, node) { + dprintf(""__S":%llu ", + __F(&tmp->in_extent), + tmp->in_max_high); + if (count++ == 8) { + dprintf("\n"); + count = 1; + } + } + + error("max high sanity check, has == %d\n", has); + } + node->in_parent = parent; + + tmp = node; + while (tmp) { + if (node_is_black(tmp)) + nr++; + else if ((tmp->in_left && node_is_red(tmp->in_left)) || + (tmp->in_right && node_is_red(tmp->in_right))) + error("wrong tree, a red node has red child\n"); + tmp = tmp->in_left; + } + + tmp = node; + while (tmp) { + if (node_is_black(tmp)) + nr--; + tmp = tmp->in_right; + } + if (nr) + error("wrong tree, unbalanced!\n"); + + return 0; +} + +static int it_test_sanity(struct interval_node *root) +{ + it_test_clear(); + interval_iterate(root, sanity_cb, NULL); + return 0; +} + +static int it_test_search_hole(struct interval_node *root) +{ + int i, count = 10; + struct interval_node_extent ext, ext2; + struct it_node *n; + __u64 low = 0, high = ~0; + + do { + if (--count == 0) + return 0; + + ext.start = random() % max_count; + ext.end = ext.start; + } while (interval_is_overlapped(root, &ext)); + ext2 = ext; + + interval_expand(root, &ext, NULL); + dprintf("Extending "__S" to .."__S"\n", __F(&ext2), __F(&ext)); + for (i = 0; i < it_count; i++) { + n = &it_array[i]; + if (n->valid == 0) + continue; + + if (extent_overlapped(&ext, &n->node.in_extent)) { + error("Extending "__S" to .."__S" overlaps node"__S"\n", + __F(&ext2), __F(&ext), __F(&n->node.in_extent)); + } + + if (n->node.in_extent.end < ext2.start) + low = max_u64(n->node.in_extent.end + 1, low); + + if (n->node.in_extent.start > ext2.end) + high = min_u64(n->node.in_extent.start - 1, high); + } + + /* only expanding high right now */ + if (ext2.start != ext.start || high != ext.end) { + ext2.start = low, ext2.end = high; + error("Real extending result:"__S", expected:"__S"\n", + __F(&ext), __F(&ext2)); + } + + return 0; +} + +static int contended_count = 0; +#define LOOP_COUNT 1000 +static enum interval_iter perf_cb(struct interval_node *n, void *args) +{ + unsigned long count = LOOP_COUNT; + while (count--); + contended_count++; + return INTERVAL_ITER_CONT; +} + +static inline long tv_delta(struct timeval *s, struct timeval *e) +{ + long c = e->tv_sec - s->tv_sec; + c *= 1000; + c += (long int)(e->tv_usec - s->tv_usec) / 1000; + dprintf("\tStart: %lu:%lu -> End: %lu:%lu\n", + s->tv_sec, s->tv_usec, e->tv_sec, e->tv_usec); + return c; +} + +static int it_test_performance(struct interval_node *root, unsigned long len) +{ + int i = 0, interval_time, list_time; + struct interval_node_extent ext; + struct it_node *n; + struct timeval start, end; + unsigned long count; + + ext.start = (random() % (max_count - len)) & ALIGN_MASK; + ext.end = (ext.start + len) & ALIGN_MASK; + if (have_wide_lock) { + ext.start = (max_count - len) & ALIGN_MASK; + ext.end = max_count; + } + + dprintf("Extent search"__S"\n", __F(&ext)); + + /* list */ + contended_count = 0; + gettimeofday(&start, NULL); + list_for_each_entry(n, &header, list) { + if (extent_overlapped(&ext, &n->node.in_extent)) { + count = LOOP_COUNT; + while (count--); + contended_count++; + } + } + gettimeofday(&end, NULL); + list_time = tv_delta(&start, &end); + i = contended_count; + + /* interval */ + contended_count = 0; + gettimeofday(&start, NULL); + interval_search(root, &ext, perf_cb, &contended_count); + gettimeofday(&end, NULL); + interval_time = tv_delta(&start, &end); + + if (i != contended_count) + error("count of contended lock don't match(%d: %d)\n", + i, contended_count); + + printf("\tList vs Int. search: \n\t\t" + "(%d vs %d)ms, %d contended lock.\n", + list_time, interval_time, contended_count); + + return 0; +} + +static struct interval_node *it_test_helper(struct interval_node *root) +{ + int idx, count = 0; + struct it_node *n; + + count = random() % it_count; + while (count--) { + idx = random() % it_count; + n = &it_array[idx]; + if (n->valid) { + if (!interval_find(root, &n->node.in_extent)) + error("Cannot find an existent node\n"); + dprintf("Erasing a node "__S"\n", + __F(&n->node.in_extent)); + interval_erase(&n->node, &root); + n->valid = 0; + list_del_init(&n->list); + } else { + __u64 low, high; + low = (random() % max_count) & ALIGN_MASK; + high = ((random() % max_count + 1) & ALIGN_MASK) + low; + if (high > max_count) + high = max_count; + interval_set(&n->node, low, high); + while (interval_insert(&n->node, &root)) + interval_set(&n->node, low, ++high); + dprintf("Adding a node "__S"\n", + __F(&n->node.in_extent)); + n->valid = 1; + list_add(&n->list, &header); + } + } + + return root; +} + +static struct interval_node *it_test_init(int count) +{ + int i; + uint64_t high, low, len; + struct it_node *n; + struct interval_node *root = NULL; + + it_count = count; + it_array = (struct it_node *)malloc(sizeof(struct it_node) * count); + if (it_array == NULL) + error("it_array == NULL, no memory\n"); + + have_wide_lock = 0; + for (i = 0; i < count; i++) { + n = &it_array[i]; + do { + low = (random() % max_count + 1) & ALIGN_MASK; + len = (random() % 256 + 1) * ALIGN_SIZE; + if (!have_wide_lock && !(random() % count)) { + low = 0; + len = max_count; + have_wide_lock = 1; + } + high = low + (len & ALIGN_MASK); + + interval_set(&n->node, low, high); + } while (interval_insert(&n->node, &root)); + n->hit = 0; + n->valid = 1; + if (i == 0) + list_add_tail(&n->list, &header); + else + list_add_tail(&n->list, &it_array[rand()%i].list); + } + + return root; +} + +static void it_test_fini(void) +{ + free(it_array); + it_array = NULL; + it_count = 0; + max_count = 0; +} + +int main(int argc, char *argv[]) +{ + int count = 5, perf = 0; + struct interval_node *root; + struct timeval tv; + + gettimeofday(&tv, NULL); + srandom(tv.tv_usec); + + if (argc == 2) { + if (strcmp(argv[1], "-p")) + error("Unknow options, usage: %s [-p]\n", argv[0]); + perf = 1; + count = 1; + } + + if (perf) { + int M = 1024 * 1024; + root = it_test_init(1000000); + printf("1M locks with 4K request size\n"); + it_test_performance(root, 4096); + printf("1M locks with 128K request size\n"); + it_test_performance(root, 128 * 1024); + printf("1M locks with 256K request size\n"); + it_test_performance(root, 256 * 1024); + printf("1M locks with 1M request size\n"); + it_test_performance(root, 1 * M); + printf("1M locks with 16M request size\n"); + it_test_performance(root, 16 * M); + printf("1M locks with 32M request size\n"); + it_test_performance(root, 32 * M); + printf("1M locks with 64M request size\n"); + it_test_performance(root, 64 * M); + printf("1M locks with 128M request size\n"); + it_test_performance(root, 128 * M); + printf("1M locks with 256M request size\n"); + it_test_performance(root, 256 * M); + printf("1M locks with 512M request size\n"); + it_test_performance(root, 512 * M); + printf("1M locks with 1G request size\n"); + it_test_performance(root, 1024 * M); + printf("1M locks with 2G request size\n"); + it_test_performance(root, 2048 * M); + printf("1M locks with 3G request size\n"); + it_test_performance(root, 3072 * M); + printf("1M locks with 4G request size\n"); + it_test_performance(root, max_count - 1); + it_test_fini(); + return 0; + } + + root = it_test_init(random() % 100000 + 1000); + while (count--) { + it_test_sanity(root); + it_test_iterate(root); + it_test_iterate_reverse(root); + it_test_find(root); + it_test_search_hole(root); + it_test_search(root); + root = it_test_helper(root); + } + it_test_fini(); + + return 0; +} -- 1.8.3.1