it_test.c

lustre 1.6.5 source code

/* vi:set ts=8 sw=8 expandtab: */
/* Unit test tool for interval tree.
 * Written by jay <[e-mail]> 
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

#include <libcfs/kp30.h>
#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              "["LPX64":"LPX64"]"

#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;
CFS_LIST_HEAD(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)
{