[qemu.git] / tests / test-hbitmap.c

/*
 * Hierarchical bitmap unit-tests.
 *
 * Copyright (C) 2012 Red Hat Inc.
 *
 * Author: Paolo Bonzini <[email protected]>
 *
 * This work is licensed under the terms of the GNU GPL, version 2 or later.
 * See the COPYING file in the top-level directory.
 */

#include <glib.h>
#include <stdarg.h>
#include <string.h>
#include <sys/types.h>
#include "qemu/hbitmap.h"

#define LOG_BITS_PER_LONG          (BITS_PER_LONG == 32 ? 5 : 6)

#define L1                         BITS_PER_LONG
#define L2                         (BITS_PER_LONG * L1)
#define L3                         (BITS_PER_LONG * L2)

typedef struct TestHBitmapData {
    HBitmap       *hb;
    unsigned long *bits;
    size_t         size;
    size_t         old_size;
    int            granularity;
} TestHBitmapData;


/* Check that the HBitmap and the shadow bitmap contain the same data,
 * ignoring the same "first" bits.
 */
static void hbitmap_test_check(TestHBitmapData *data,
                               uint64_t first)
{
    uint64_t count = 0;
    size_t pos;
    int bit;
    HBitmapIter hbi;
    int64_t i, next;

    hbitmap_iter_init(&hbi, data->hb, first);

    i = first;
    for (;;) {
        next = hbitmap_iter_next(&hbi);
        if (next < 0) {
            next = data->size;
        }

        while (i < next) {
            pos = i >> LOG_BITS_PER_LONG;
            bit = i & (BITS_PER_LONG - 1);
            i++;
            g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0);
        }

        if (next == data->size) {
            break;
        }

        pos = i >> LOG_BITS_PER_LONG;
        bit = i & (BITS_PER_LONG - 1);
        i++;
        count++;
        g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0);
    }

    if (first == 0) {
        g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
    }
}

/* This is provided instead of a test setup function so that the sizes
   are kept in the test functions (and not in main()) */
static void hbitmap_test_init(TestHBitmapData *data,
                              uint64_t size, int granularity)
{
    size_t n;
    data->hb = hbitmap_alloc(size, granularity);

    n = (size + BITS_PER_LONG - 1) / BITS_PER_LONG;
    if (n == 0) {
        n = 1;
    }
    data->bits = g_new0(unsigned long, n);
    data->size = size;
    data->granularity = granularity;
    if (size) {
        hbitmap_test_check(data, 0);
    }
}

static inline size_t hbitmap_test_array_size(size_t bits)
{
    size_t n = (bits + BITS_PER_LONG - 1) / BITS_PER_LONG;
    return n ? n : 1;
}

static void hbitmap_test_truncate_impl(TestHBitmapData *data,
                                       size_t size)
{
    size_t n;
    size_t m;
    data->old_size = data->size;
    data->size = size;

    if (data->size == data->old_size) {
        return;
    }

    n = hbitmap_test_array_size(size);
    m = hbitmap_test_array_size(data->old_size);
    data->bits = g_realloc(data->bits, sizeof(unsigned long) * n);
    if (n > m) {
        memset(&data->bits[m], 0x00, sizeof(unsigned long) * (n - m));
    }

    /* If we shrink to an uneven multiple of sizeof(unsigned long),
     * scrub the leftover memory. */
    if (data->size < data->old_size) {
        m = size % (sizeof(unsigned long) * 8);
        if (m) {
            unsigned long mask = (1ULL << m) - 1;
            data->bits[n-1] &= mask;
        }
    }

    hbitmap_truncate(data->hb, size);
}

static void hbitmap_test_teardown(TestHBitmapData *data,
                                  const void *unused)
{
    if (data->hb) {
        hbitmap_free(data->hb);
        data->hb = NULL;
    }
    g_free(data->bits);
    data->bits = NULL;
}

/* Set a range in the HBitmap and in the shadow "simple" bitmap.
 * The two bitmaps are then tested against each other.
 */
static void hbitmap_test_set(TestHBitmapData *data,
                             uint64_t first, uint64_t count)
{
    hbitmap_set(data->hb, first, count);
    while (count-- != 0) {
        size_t pos = first >> LOG_BITS_PER_LONG;
        int bit = first & (BITS_PER_LONG - 1);
        first++;

        data->bits[pos] |= 1UL << bit;
    }

    if (data->granularity == 0) {
        hbitmap_test_check(data, 0);
    }
}

/* Reset a range in the HBitmap and in the shadow "simple" bitmap.
 */
static void hbitmap_test_reset(TestHBitmapData *data,
                               uint64_t first, uint64_t count)
{
    hbitmap_reset(data->hb, first, count);
    while (count-- != 0) {
        size_t pos = first >> LOG_BITS_PER_LONG;
        int bit = first & (BITS_PER_LONG - 1);
        first++;

        data->bits[pos] &= ~(1UL << bit);
    }

    if (data->granularity == 0) {
        hbitmap_test_check(data, 0);
    }
}

static void hbitmap_test_reset_all(TestHBitmapData *data)
{
    size_t n;

    hbitmap_reset_all(data->hb);

    n = (data->size + BITS_PER_LONG - 1) / BITS_PER_LONG;
    if (n == 0) {
        n = 1;
    }
    memset(data->bits, 0, n * sizeof(unsigned long));

    if (data->granularity == 0) {
        hbitmap_test_check(data, 0);
    }
}

static void hbitmap_test_check_get(TestHBitmapData *data)
{
    uint64_t count = 0;
    uint64_t i;

    for (i = 0; i < data->size; i++) {
        size_t pos = i >> LOG_BITS_PER_LONG;
        int bit = i & (BITS_PER_LONG - 1);
        unsigned long val = data->bits[pos] & (1UL << bit);
        count += hbitmap_get(data->hb, i);
        g_assert_cmpint(hbitmap_get(data->hb, i), ==, val != 0);
    }
    g_assert_cmpint(count, ==, hbitmap_count(data->hb));
}

static void test_hbitmap_zero(TestHBitmapData *data,
                               const void *unused)
{
    hbitmap_test_init(data, 0, 0);
}

static void test_hbitmap_unaligned(TestHBitmapData *data,
                                   const void *unused)
{
    hbitmap_test_init(data, L3 + 23, 0);
    hbitmap_test_set(data, 0, 1);
    hbitmap_test_set(data, L3 + 22, 1);
}

static void test_hbitmap_iter_empty(TestHBitmapData *data,
                                    const void *unused)
{
    hbitmap_test_init(data, L1, 0);
}

static void test_hbitmap_iter_partial(TestHBitmapData *data,
                                      const void *unused)
{
    hbitmap_test_init(data, L3, 0);
    hbitmap_test_set(data, 0, L3);
    hbitmap_test_check(data, 1);
    hbitmap_test_check(data, L1 - 1);
    hbitmap_test_check(data, L1);
    hbitmap_test_check(data, L1 * 2 - 1);
    hbitmap_test_check(data, L2 - 1);
    hbitmap_test_check(data, L2);
    hbitmap_test_check(data, L2 + 1);
    hbitmap_test_check(data, L2 + L1);
    hbitmap_test_check(data, L2 + L1 * 2 - 1);
    hbitmap_test_check(data, L2 * 2 - 1);
    hbitmap_test_check(data, L2 * 2);
    hbitmap_test_check(data, L2 * 2 + 1);
    hbitmap_test_check(data, L2 * 2 + L1);
    hbitmap_test_check(data, L2 * 2 + L1 * 2 - 1);
    hbitmap_test_check(data, L3 / 2);
}

static void test_hbitmap_set_all(TestHBitmapData *data,
                                 const void *unused)
{
    hbitmap_test_init(data, L3, 0);
    hbitmap_test_set(data, 0, L3);
}

static void test_hbitmap_get_all(TestHBitmapData *data,
                                 const void *unused)
{
    hbitmap_test_init(data, L3, 0);
    hbitmap_test_set(data, 0, L3);
    hbitmap_test_check_get(data);
}

static void test_hbitmap_get_some(TestHBitmapData *data,
                                  const void *unused)
{
    hbitmap_test_init(data, 2 * L2, 0);
    hbitmap_test_set(data, 10, 1);
    hbitmap_test_check_get(data);
    hbitmap_test_set(data, L1 - 1, 1);
    hbitmap_test_check_get(data);
    hbitmap_test_set(data, L1, 1);
    hbitmap_test_check_get(data);
    hbitmap_test_set(data, L2 - 1, 1);
    hbitmap_test_check_get(data);
    hbitmap_test_set(data, L2, 1);
    hbitmap_test_check_get(data);
}

static void test_hbitmap_set_one(TestHBitmapData *data,
                                 const void *unused)
{
    hbitmap_test_init(data, 2 * L2, 0);
    hbitmap_test_set(data, 10, 1);
    hbitmap_test_set(data, L1 - 1, 1);
    hbitmap_test_set(data, L1, 1);
    hbitmap_test_set(data, L2 - 1, 1);
    hbitmap_test_set(data, L2, 1);
}

static void test_hbitmap_set_two_elem(TestHBitmapData *data,
                                      const void *unused)
{
    hbitmap_test_init(data, 2 * L2, 0);
    hbitmap_test_set(data, L1 - 1, 2);
    hbitmap_test_set(data, L1 * 2 - 1, 4);
    hbitmap_test_set(data, L1 * 4, L1 + 1);
    hbitmap_test_set(data, L1 * 8 - 1, L1 + 1);
    hbitmap_test_set(data, L2 - 1, 2);
    hbitmap_test_set(data, L2 + L1 - 1, 8);
    hbitmap_test_set(data, L2 + L1 * 4, L1 + 1);
    hbitmap_test_set(data, L2 + L1 * 8 - 1, L1 + 1);
}

static void test_hbitmap_set(TestHBitmapData *data,
                             const void *unused)
{
    hbitmap_test_init(data, L3 * 2, 0);
    hbitmap_test_set(data, L1 - 1, L1 + 2);
    hbitmap_test_set(data, L1 * 3 - 1, L1 + 2);
    hbitmap_test_set(data, L1 * 5, L1 * 2 + 1);
    hbitmap_test_set(data, L1 * 8 - 1, L1 * 2 + 1);
    hbitmap_test_set(data, L2 - 1, L1 + 2);
    hbitmap_test_set(data, L2 + L1 * 2 - 1, L1 + 2);
    hbitmap_test_set(data, L2 + L1 * 4, L1 * 2 + 1);
    hbitmap_test_set(data, L2 + L1 * 7 - 1, L1 * 2 + 1);
    hbitmap_test_set(data, L2 * 2 - 1, L3 * 2 - L2 * 2);
}

static void test_hbitmap_set_twice(TestHBitmapData *data,
                                   const void *unused)
{
    hbitmap_test_init(data, L1 * 3, 0);
    hbitmap_test_set(data, 0, L1 * 3);
    hbitmap_test_set(data, L1, 1);
}

static void test_hbitmap_set_overlap(TestHBitmapData *data,
                                     const void *unused)
{
    hbitmap_test_init(data, L3 * 2, 0);
    hbitmap_test_set(data, L1 - 1, L1 + 2);
    hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2);
    hbitmap_test_set(data, 0, L1 * 3);
    hbitmap_test_set(data, L1 * 8 - 1, L2);
    hbitmap_test_set(data, L2, L1);
    hbitmap_test_set(data, L2 - L1 - 1, L1 * 8 + 2);
    hbitmap_test_set(data, L2, L3 - L2 + 1);
    hbitmap_test_set(data, L3 - L1, L1 * 3);
    hbitmap_test_set(data, L3 - 1, 3);
    hbitmap_test_set(data, L3 - 1, L2);
}

static void test_hbitmap_reset_empty(TestHBitmapData *data,
                                     const void *unused)
{
    hbitmap_test_init(data, L3, 0);
    hbitmap_test_reset(data, 0, L3);
}

static void test_hbitmap_reset(TestHBitmapData *data,
                               const void *unused)
{
    hbitmap_test_init(data, L3 * 2, 0);
    hbitmap_test_set(data, L1 - 1, L1 + 2);
    hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2);
    hbitmap_test_set(data, 0, L1 * 3);
    hbitmap_test_reset(data, L1 * 8 - 1, L2);
    hbitmap_test_set(data, L2, L1);
    hbitmap_test_reset(data, L2 - L1 - 1, L1 * 8 + 2);
    hbitmap_test_set(data, L2, L3 - L2 + 1);
    hbitmap_test_reset(data, L3 - L1, L1 * 3);
    hbitmap_test_set(data, L3 - 1, 3);
    hbitmap_test_reset(data, L3 - 1, L2);
    hbitmap_test_set(data, 0, L3 * 2);
    hbitmap_test_reset(data, 0, L1);
    hbitmap_test_reset(data, 0, L2);
    hbitmap_test_reset(data, L3, L3);
    hbitmap_test_set(data, L3 / 2, L3);
}

static void test_hbitmap_reset_all(TestHBitmapData *data,
                                   const void *unused)
{
    hbitmap_test_init(data, L3 * 2, 0);
    hbitmap_test_set(data, L1 - 1, L1 + 2);
    hbitmap_test_reset_all(data);
    hbitmap_test_set(data, 0, L1 * 3);
    hbitmap_test_reset_all(data);
    hbitmap_test_set(data, L2, L1);
    hbitmap_test_reset_all(data);
    hbitmap_test_set(data, L2, L3 - L2 + 1);
    hbitmap_test_reset_all(data);
    hbitmap_test_set(data, L3 - 1, 3);
    hbitmap_test_reset_all(data);
    hbitmap_test_set(data, 0, L3 * 2);
    hbitmap_test_reset_all(data);
    hbitmap_test_set(data, L3 / 2, L3);
    hbitmap_test_reset_all(data);
}

static void test_hbitmap_granularity(TestHBitmapData *data,
                                     const void *unused)
{
    /* Note that hbitmap_test_check has to be invoked manually in this test.  */
    hbitmap_test_init(data, L1, 1);
    hbitmap_test_set(data, 0, 1);
    g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
    hbitmap_test_check(data, 0);
    hbitmap_test_set(data, 2, 1);
    g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
    hbitmap_test_check(data, 0);
    hbitmap_test_set(data, 0, 3);
    g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
    hbitmap_test_reset(data, 0, 1);
    g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
}

static void test_hbitmap_iter_granularity(TestHBitmapData *data,
                                          const void *unused)
{
    HBitmapIter hbi;

    /* Note that hbitmap_test_check has to be invoked manually in this test.  */
    hbitmap_test_init(data, 131072 << 7, 7);
    hbitmap_iter_init(&hbi, data->hb, 0);
    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);

    hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
    hbitmap_iter_init(&hbi, data->hb, 0);
    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);

    hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);

    hbitmap_test_set(data, (131072 << 7) - 8, 8);
    hbitmap_iter_init(&hbi, data->hb, 0);
    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);

    hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
}

static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
{
    size_t size = data->size;

    /* First bit */
    hbitmap_test_set(data, 0, 1);
    if (diff < 0) {
        /* Last bit in new, shortened map */
        hbitmap_test_set(data, size + diff - 1, 1);

        /* First bit to be truncated away */
        hbitmap_test_set(data, size + diff, 1);
    }
    /* Last bit */
    hbitmap_test_set(data, size - 1, 1);
    if (data->granularity == 0) {
        hbitmap_test_check_get(data);
    }
}

static void hbitmap_test_check_boundary_bits(TestHBitmapData *data)
{
    size_t size = MIN(data->size, data->old_size);

    if (data->granularity == 0) {
        hbitmap_test_check_get(data);
        hbitmap_test_check(data, 0);
    } else {
        /* If a granularity was set, note that every distinct
         * (bit >> granularity) value that was set will increase
         * the bit pop count by 2^granularity, not just 1.
         *
         * The hbitmap_test_check facility does not currently tolerate
         * non-zero granularities, so test the boundaries and the population
         * count manually.
         */
        g_assert(hbitmap_get(data->hb, 0));
        g_assert(hbitmap_get(data->hb, size - 1));
        g_assert_cmpint(2 << data->granularity, ==, hbitmap_count(data->hb));
    }
}

/* Generic truncate test. */
static void hbitmap_test_truncate(TestHBitmapData *data,
                                  size_t size,
                                  ssize_t diff,
                                  int granularity)
{
    hbitmap_test_init(data, size, granularity);
    hbitmap_test_set_boundary_bits(data, diff);
    hbitmap_test_truncate_impl(data, size + diff);
    hbitmap_test_check_boundary_bits(data);
}

static void test_hbitmap_truncate_nop(TestHBitmapData *data,
                                      const void *unused)
{
    hbitmap_test_truncate(data, L2, 0, 0);
}

/**
 * Grow by an amount smaller than the granularity, without crossing
 * a granularity alignment boundary. Effectively a NOP.
 */
static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data,
                                                  const void *unused)
{
    size_t size = L2 - 1;
    size_t diff = 1;
    int granularity = 1;

    hbitmap_test_truncate(data, size, diff, granularity);
}

/**
 * Shrink by an amount smaller than the granularity, without crossing
 * a granularity alignment boundary. Effectively a NOP.
 */
static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data,
                                                    const void *unused)
{
    size_t size = L2;
    ssize_t diff = -1;
    int granularity = 1;

    hbitmap_test_truncate(data, size, diff, granularity);
}

/**
 * Grow by an amount smaller than the granularity, but crossing over
 * a granularity alignment boundary.
 */
static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data,
                                            const void *unused)
{
    size_t size = L2 - 2;
    ssize_t diff = 1;
    int granularity = 1;

    hbitmap_test_truncate(data, size, diff, granularity);
}

/**
 * Shrink by an amount smaller than the granularity, but crossing over
 * a granularity alignment boundary.
 */
static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data,
                                              const void *unused)
{
    size_t size = L2 - 1;
    ssize_t diff = -1;
    int granularity = 1;

    hbitmap_test_truncate(data, size, diff, granularity);
}

/**
 * Grow by an amount smaller than sizeof(long), and not crossing over
 * a sizeof(long) alignment boundary.
 */
static void test_hbitmap_truncate_grow_small(TestHBitmapData *data,
                                             const void *unused)
{
    size_t size = L2 + 1;
    size_t diff = sizeof(long) / 2;

    hbitmap_test_truncate(data, size, diff, 0);
}

/**
 * Shrink by an amount smaller than sizeof(long), and not crossing over
 * a sizeof(long) alignment boundary.
 */
static void test_hbitmap_truncate_shrink_small(TestHBitmapData *data,
                                               const void *unused)
{
    size_t size = L2;
    size_t diff = sizeof(long) / 2;

    hbitmap_test_truncate(data, size, -diff, 0);
}

/**
 * Grow by an amount smaller than sizeof(long), while crossing over
 * a sizeof(long) alignment boundary.
 */
static void test_hbitmap_truncate_grow_medium(TestHBitmapData *data,
                                              const void *unused)
{
    size_t size = L2 - 1;
    size_t diff = sizeof(long) / 2;

    hbitmap_test_truncate(data, size, diff, 0);
}

/**
 * Shrink by an amount smaller than sizeof(long), while crossing over
 * a sizeof(long) alignment boundary.
 */
static void test_hbitmap_truncate_shrink_medium(TestHBitmapData *data,
                                                const void *unused)
{
    size_t size = L2 + 1;
    size_t diff = sizeof(long) / 2;

    hbitmap_test_truncate(data, size, -diff, 0);
}

/**
 * Grow by an amount larger than sizeof(long).
 */
static void test_hbitmap_truncate_grow_large(TestHBitmapData *data,
                                             const void *unused)
{
    size_t size = L2;
    size_t diff = 8 * sizeof(long);

    hbitmap_test_truncate(data, size, diff, 0);
}

/**
 * Shrink by an amount larger than sizeof(long).
 */
static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
                                               const void *unused)
{
    size_t size = L2;
    size_t diff = 8 * sizeof(long);

    hbitmap_test_truncate(data, size, -diff, 0);
}

static void hbitmap_test_add(const char *testpath,
                                   void (*test_func)(TestHBitmapData *data, const void *user_data))
{
    g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func,
               hbitmap_test_teardown);
}

int main(int argc, char **argv)
{
    g_test_init(&argc, &argv, NULL);
    hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero);
    hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
    hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
    hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
    hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
    hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
    hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
    hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
    hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one);
    hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem);
    hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set);
    hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice);
    hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
    hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
    hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
    hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all);
    hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);

    hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop);
    hbitmap_test_add("/hbitmap/truncate/grow/negligible",
                     test_hbitmap_truncate_grow_negligible);
    hbitmap_test_add("/hbitmap/truncate/shrink/negligible",
                     test_hbitmap_truncate_shrink_negligible);
    hbitmap_test_add("/hbitmap/truncate/grow/tiny",
                     test_hbitmap_truncate_grow_tiny);
    hbitmap_test_add("/hbitmap/truncate/shrink/tiny",
                     test_hbitmap_truncate_shrink_tiny);
    hbitmap_test_add("/hbitmap/truncate/grow/small",
                     test_hbitmap_truncate_grow_small);
    hbitmap_test_add("/hbitmap/truncate/shrink/small",
                     test_hbitmap_truncate_shrink_small);
    hbitmap_test_add("/hbitmap/truncate/grow/medium",
                     test_hbitmap_truncate_grow_medium);
    hbitmap_test_add("/hbitmap/truncate/shrink/medium",
                     test_hbitmap_truncate_shrink_medium);
    hbitmap_test_add("/hbitmap/truncate/grow/large",
                     test_hbitmap_truncate_grow_large);
    hbitmap_test_add("/hbitmap/truncate/shrink/large",
                     test_hbitmap_truncate_shrink_large);
    g_test_run();

    return 0;
}
Commit	Line	Data
e7c033c3 PB	1	/*
	2	* Hierarchical bitmap unit-tests.
	3	*
	4	* Copyright (C) 2012 Red Hat Inc.
	5	*
	6	* Author: Paolo Bonzini <[email protected]>
	7	*
	8	* This work is licensed under the terms of the GNU GPL, version 2 or later.
	9	* See the COPYING file in the top-level directory.
	10	*/
	11
	12	#include <glib.h>
	13	#include <stdarg.h>
a94e87c0 JS	14	#include <string.h>
a94e87c0 JS	15	#include <sys/types.h>
e7c033c3 PB	16	#include "qemu/hbitmap.h"
	17
	18	#define LOG_BITS_PER_LONG (BITS_PER_LONG == 32 ? 5 : 6)
	19
	20	#define L1 BITS_PER_LONG
	21	#define L2 (BITS_PER_LONG * L1)
	22	#define L3 (BITS_PER_LONG * L2)
	23
	24	typedef struct TestHBitmapData {
	25	HBitmap *hb;
	26	unsigned long *bits;
	27	size_t size;
a94e87c0	28	size_t old_size;
e7c033c3 PB	29	int granularity;
	30	} TestHBitmapData;
	31
	32
	33	/* Check that the HBitmap and the shadow bitmap contain the same data,
	34	* ignoring the same "first" bits.
	35	*/
	36	static void hbitmap_test_check(TestHBitmapData *data,
	37	uint64_t first)
	38	{
	39	uint64_t count = 0;
	40	size_t pos;
	41	int bit;
	42	HBitmapIter hbi;
	43	int64_t i, next;
	44
	45	hbitmap_iter_init(&hbi, data->hb, first);
	46
	47	i = first;
	48	for (;;) {
	49	next = hbitmap_iter_next(&hbi);
	50	if (next < 0) {
	51	next = data->size;
	52	}
	53
	54	while (i < next) {
	55	pos = i >> LOG_BITS_PER_LONG;
	56	bit = i & (BITS_PER_LONG - 1);
	57	i++;
	58	g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0);
	59	}
	60
	61	if (next == data->size) {
	62	break;
	63	}
	64
	65	pos = i >> LOG_BITS_PER_LONG;
	66	bit = i & (BITS_PER_LONG - 1);
	67	i++;
	68	count++;
	69	g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0);
	70	}
	71
	72	if (first == 0) {
	73	g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
	74	}
	75	}
	76
	77	/* This is provided instead of a test setup function so that the sizes
	78	are kept in the test functions (and not in main()) */
	79	static void hbitmap_test_init(TestHBitmapData *data,
	80	uint64_t size, int granularity)
	81	{
	82	size_t n;
	83	data->hb = hbitmap_alloc(size, granularity);
	84
	85	n = (size + BITS_PER_LONG - 1) / BITS_PER_LONG;
	86	if (n == 0) {
	87	n = 1;
	88	}
	89	data->bits = g_new0(unsigned long, n);
	90	data->size = size;
	91	data->granularity = granularity;
1b095244 PB	92	if (size) {
	93	hbitmap_test_check(data, 0);
	94	}
e7c033c3 PB	95	}
e7c033c3 PB	96
a94e87c0 JS	97	static inline size_t hbitmap_test_array_size(size_t bits)
	98	{
	99	size_t n = (bits + BITS_PER_LONG - 1) / BITS_PER_LONG;
	100	return n ? n : 1;
	101	}
	102
	103	static void hbitmap_test_truncate_impl(TestHBitmapData *data,
	104	size_t size)
	105	{
	106	size_t n;
	107	size_t m;
	108	data->old_size = data->size;
	109	data->size = size;
	110
	111	if (data->size == data->old_size) {
	112	return;
	113	}
	114
	115	n = hbitmap_test_array_size(size);
	116	m = hbitmap_test_array_size(data->old_size);
	117	data->bits = g_realloc(data->bits, sizeof(unsigned long) * n);
	118	if (n > m) {
	119	memset(&data->bits[m], 0x00, sizeof(unsigned long) * (n - m));
	120	}
	121
	122	/* If we shrink to an uneven multiple of sizeof(unsigned long),
	123	* scrub the leftover memory. */
	124	if (data->size < data->old_size) {
	125	m = size % (sizeof(unsigned long) * 8);
	126	if (m) {
	127	unsigned long mask = (1ULL << m) - 1;
	128	data->bits[n-1] &= mask;
	129	}
	130	}
	131
	132	hbitmap_truncate(data->hb, size);
	133	}
	134
e7c033c3 PB	135	static void hbitmap_test_teardown(TestHBitmapData *data,
	136	const void *unused)
	137	{
	138	if (data->hb) {
	139	hbitmap_free(data->hb);
	140	data->hb = NULL;
	141	}
012aef07 MA	142	g_free(data->bits);
012aef07 MA	143	data->bits = NULL;
e7c033c3 PB	144	}
	145
	146	/* Set a range in the HBitmap and in the shadow "simple" bitmap.
	147	* The two bitmaps are then tested against each other.
	148	*/
	149	static void hbitmap_test_set(TestHBitmapData *data,
	150	uint64_t first, uint64_t count)
	151	{
	152	hbitmap_set(data->hb, first, count);
	153	while (count-- != 0) {
	154	size_t pos = first >> LOG_BITS_PER_LONG;
	155	int bit = first & (BITS_PER_LONG - 1);
	156	first++;
	157
	158	data->bits[pos] \|= 1UL << bit;
	159	}
	160
	161	if (data->granularity == 0) {
	162	hbitmap_test_check(data, 0);
	163	}
	164	}
	165
	166	/* Reset a range in the HBitmap and in the shadow "simple" bitmap.
	167	*/
	168	static void hbitmap_test_reset(TestHBitmapData *data,
	169	uint64_t first, uint64_t count)
	170	{
	171	hbitmap_reset(data->hb, first, count);
	172	while (count-- != 0) {
	173	size_t pos = first >> LOG_BITS_PER_LONG;
	174	int bit = first & (BITS_PER_LONG - 1);
	175	first++;
	176
	177	data->bits[pos] &= ~(1UL << bit);
	178	}
	179
	180	if (data->granularity == 0) {
	181	hbitmap_test_check(data, 0);
	182	}
	183	}
	184
c6a8c328 WC	185	static void hbitmap_test_reset_all(TestHBitmapData *data)
	186	{
	187	size_t n;
	188
	189	hbitmap_reset_all(data->hb);
	190
	191	n = (data->size + BITS_PER_LONG - 1) / BITS_PER_LONG;
	192	if (n == 0) {
	193	n = 1;
	194	}
	195	memset(data->bits, 0, n * sizeof(unsigned long));
	196
	197	if (data->granularity == 0) {
	198	hbitmap_test_check(data, 0);
	199	}
	200	}
	201
e7c033c3 PB	202	static void hbitmap_test_check_get(TestHBitmapData *data)
	203	{
	204	uint64_t count = 0;
	205	uint64_t i;
	206
	207	for (i = 0; i < data->size; i++) {
	208	size_t pos = i >> LOG_BITS_PER_LONG;
	209	int bit = i & (BITS_PER_LONG - 1);
	210	unsigned long val = data->bits[pos] & (1UL << bit);
	211	count += hbitmap_get(data->hb, i);
	212	g_assert_cmpint(hbitmap_get(data->hb, i), ==, val != 0);
	213	}
	214	g_assert_cmpint(count, ==, hbitmap_count(data->hb));
	215	}
	216
	217	static void test_hbitmap_zero(TestHBitmapData *data,
	218	const void *unused)
	219	{
	220	hbitmap_test_init(data, 0, 0);
	221	}
	222
	223	static void test_hbitmap_unaligned(TestHBitmapData *data,
	224	const void *unused)
	225	{
	226	hbitmap_test_init(data, L3 + 23, 0);
	227	hbitmap_test_set(data, 0, 1);
	228	hbitmap_test_set(data, L3 + 22, 1);
	229	}
	230
	231	static void test_hbitmap_iter_empty(TestHBitmapData *data,
	232	const void *unused)
	233	{
	234	hbitmap_test_init(data, L1, 0);
	235	}
	236
	237	static void test_hbitmap_iter_partial(TestHBitmapData *data,
	238	const void *unused)
	239	{
	240	hbitmap_test_init(data, L3, 0);
	241	hbitmap_test_set(data, 0, L3);
	242	hbitmap_test_check(data, 1);
	243	hbitmap_test_check(data, L1 - 1);
	244	hbitmap_test_check(data, L1);
	245	hbitmap_test_check(data, L1 * 2 - 1);
	246	hbitmap_test_check(data, L2 - 1);
	247	hbitmap_test_check(data, L2);
	248	hbitmap_test_check(data, L2 + 1);
	249	hbitmap_test_check(data, L2 + L1);
	250	hbitmap_test_check(data, L2 + L1 * 2 - 1);
	251	hbitmap_test_check(data, L2 * 2 - 1);
	252	hbitmap_test_check(data, L2 * 2);
	253	hbitmap_test_check(data, L2 * 2 + 1);
	254	hbitmap_test_check(data, L2 * 2 + L1);
	255	hbitmap_test_check(data, L2 * 2 + L1 * 2 - 1);
	256	hbitmap_test_check(data, L3 / 2);
	257	}
	258
e7c033c3 PB	259	static void test_hbitmap_set_all(TestHBitmapData *data,
	260	const void *unused)
	261	{
	262	hbitmap_test_init(data, L3, 0);
	263	hbitmap_test_set(data, 0, L3);
	264	}
	265
	266	static void test_hbitmap_get_all(TestHBitmapData *data,
	267	const void *unused)
	268	{
	269	hbitmap_test_init(data, L3, 0);
	270	hbitmap_test_set(data, 0, L3);
	271	hbitmap_test_check_get(data);
	272	}
	273
	274	static void test_hbitmap_get_some(TestHBitmapData *data,
	275	const void *unused)
	276	{
	277	hbitmap_test_init(data, 2 * L2, 0);
	278	hbitmap_test_set(data, 10, 1);
	279	hbitmap_test_check_get(data);
	280	hbitmap_test_set(data, L1 - 1, 1);
	281	hbitmap_test_check_get(data);
	282	hbitmap_test_set(data, L1, 1);
	283	hbitmap_test_check_get(data);
	284	hbitmap_test_set(data, L2 - 1, 1);
	285	hbitmap_test_check_get(data);
	286	hbitmap_test_set(data, L2, 1);
	287	hbitmap_test_check_get(data);
	288	}
	289
	290	static void test_hbitmap_set_one(TestHBitmapData *data,
	291	const void *unused)
	292	{
	293	hbitmap_test_init(data, 2 * L2, 0);
	294	hbitmap_test_set(data, 10, 1);
	295	hbitmap_test_set(data, L1 - 1, 1);
	296	hbitmap_test_set(data, L1, 1);
	297	hbitmap_test_set(data, L2 - 1, 1);
	298	hbitmap_test_set(data, L2, 1);
	299	}
	300
	301	static void test_hbitmap_set_two_elem(TestHBitmapData *data,
	302	const void *unused)
	303	{
	304	hbitmap_test_init(data, 2 * L2, 0);
	305	hbitmap_test_set(data, L1 - 1, 2);
	306	hbitmap_test_set(data, L1 * 2 - 1, 4);
	307	hbitmap_test_set(data, L1 * 4, L1 + 1);
	308	hbitmap_test_set(data, L1 * 8 - 1, L1 + 1);
	309	hbitmap_test_set(data, L2 - 1, 2);
	310	hbitmap_test_set(data, L2 + L1 - 1, 8);
	311	hbitmap_test_set(data, L2 + L1 * 4, L1 + 1);
	312	hbitmap_test_set(data, L2 + L1 * 8 - 1, L1 + 1);
	313	}
	314
	315	static void test_hbitmap_set(TestHBitmapData *data,
	316	const void *unused)
	317	{
	318	hbitmap_test_init(data, L3 * 2, 0);
	319	hbitmap_test_set(data, L1 - 1, L1 + 2);
	320	hbitmap_test_set(data, L1 * 3 - 1, L1 + 2);
	321	hbitmap_test_set(data, L1 * 5, L1 * 2 + 1);
	322	hbitmap_test_set(data, L1 * 8 - 1, L1 * 2 + 1);
323	hbitmap_test_set(data, L2 - 1, L1 + 2);
324	hbitmap_test_set(data, L2 + L1 * 2 - 1, L1 + 2);
325	hbitmap_test_set(data, L2 + L1 * 4, L1 * 2 + 1);
326	hbitmap_test_set(data, L2 + L1 * 7 - 1, L1 * 2 + 1);
327	hbitmap_test_set(data, L2 * 2 - 1, L3 * 2 - L2 * 2);
328	}
329
330	static void test_hbitmap_set_twice(TestHBitmapData *data,
331	const void *unused)
332	{
333	hbitmap_test_init(data, L1 * 3, 0);
334	hbitmap_test_set(data, 0, L1 * 3);
335	hbitmap_test_set(data, L1, 1);
336	}
337
338	static void test_hbitmap_set_overlap(TestHBitmapData *data,
339	const void *unused)
340	{
341	hbitmap_test_init(data, L3 * 2, 0);
342	hbitmap_test_set(data, L1 - 1, L1 + 2);
343	hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2);
344	hbitmap_test_set(data, 0, L1 * 3);
345	hbitmap_test_set(data, L1 * 8 - 1, L2);
346	hbitmap_test_set(data, L2, L1);
347	hbitmap_test_set(data, L2 - L1 - 1, L1 * 8 + 2);
348	hbitmap_test_set(data, L2, L3 - L2 + 1);
349	hbitmap_test_set(data, L3 - L1, L1 * 3);
350	hbitmap_test_set(data, L3 - 1, 3);
351	hbitmap_test_set(data, L3 - 1, L2);
352	}
353
354	static void test_hbitmap_reset_empty(TestHBitmapData *data,
355	const void *unused)
356	{
357	hbitmap_test_init(data, L3, 0);
358	hbitmap_test_reset(data, 0, L3);
359	}
360
361	static void test_hbitmap_reset(TestHBitmapData *data,
362	const void *unused)
363	{
364	hbitmap_test_init(data, L3 * 2, 0);
365	hbitmap_test_set(data, L1 - 1, L1 + 2);
366	hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2);
367	hbitmap_test_set(data, 0, L1 * 3);
368	hbitmap_test_reset(data, L1 * 8 - 1, L2);
369	hbitmap_test_set(data, L2, L1);
370	hbitmap_test_reset(data, L2 - L1 - 1, L1 * 8 + 2);
371	hbitmap_test_set(data, L2, L3 - L2 + 1);
372	hbitmap_test_reset(data, L3 - L1, L1 * 3);
373	hbitmap_test_set(data, L3 - 1, 3);
374	hbitmap_test_reset(data, L3 - 1, L2);
375	hbitmap_test_set(data, 0, L3 * 2);
376	hbitmap_test_reset(data, 0, L1);
377	hbitmap_test_reset(data, 0, L2);
378	hbitmap_test_reset(data, L3, L3);
379	hbitmap_test_set(data, L3 / 2, L3);
380	}
381
c6a8c328 WC	382	static void test_hbitmap_reset_all(TestHBitmapData *data,
	383	const void *unused)
	384	{
	385	hbitmap_test_init(data, L3 * 2, 0);
	386	hbitmap_test_set(data, L1 - 1, L1 + 2);
	387	hbitmap_test_reset_all(data);
	388	hbitmap_test_set(data, 0, L1 * 3);
	389	hbitmap_test_reset_all(data);
	390	hbitmap_test_set(data, L2, L1);
	391	hbitmap_test_reset_all(data);
	392	hbitmap_test_set(data, L2, L3 - L2 + 1);
	393	hbitmap_test_reset_all(data);
	394	hbitmap_test_set(data, L3 - 1, 3);
	395	hbitmap_test_reset_all(data);
	396	hbitmap_test_set(data, 0, L3 * 2);
	397	hbitmap_test_reset_all(data);
	398	hbitmap_test_set(data, L3 / 2, L3);
	399	hbitmap_test_reset_all(data);
	400	}
	401
e7c033c3 PB	402	static void test_hbitmap_granularity(TestHBitmapData *data,
	403	const void *unused)
	404	{
	405	/* Note that hbitmap_test_check has to be invoked manually in this test. */
	406	hbitmap_test_init(data, L1, 1);
	407	hbitmap_test_set(data, 0, 1);
	408	g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
	409	hbitmap_test_check(data, 0);
	410	hbitmap_test_set(data, 2, 1);
	411	g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
	412	hbitmap_test_check(data, 0);
	413	hbitmap_test_set(data, 0, 3);
	414	g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
	415	hbitmap_test_reset(data, 0, 1);
	416	g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
	417	}
	418
	419	static void test_hbitmap_iter_granularity(TestHBitmapData *data,
	420	const void *unused)
	421	{
	422	HBitmapIter hbi;
	423
	424	/* Note that hbitmap_test_check has to be invoked manually in this test. */
	425	hbitmap_test_init(data, 131072 << 7, 7);
	426	hbitmap_iter_init(&hbi, data->hb, 0);
	427	g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
	428
	429	hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
	430	hbitmap_iter_init(&hbi, data->hb, 0);
	431	g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
	432	g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
	433
	434	hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
	435	g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
	436
	437	hbitmap_test_set(data, (131072 << 7) - 8, 8);
	438	hbitmap_iter_init(&hbi, data->hb, 0);
	439	g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
	440	g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
	441	g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
	442
	443	hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
	444	g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
	445	g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
	446	}
	447
a94e87c0 JS	448	static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
	449	{
	450	size_t size = data->size;
	451
	452	/* First bit */
	453	hbitmap_test_set(data, 0, 1);
	454	if (diff < 0) {
	455	/* Last bit in new, shortened map */
	456	hbitmap_test_set(data, size + diff - 1, 1);
	457
	458	/* First bit to be truncated away */
	459	hbitmap_test_set(data, size + diff, 1);
	460	}
	461	/* Last bit */
	462	hbitmap_test_set(data, size - 1, 1);
	463	if (data->granularity == 0) {
	464	hbitmap_test_check_get(data);
	465	}
	466	}
	467
	468	static void hbitmap_test_check_boundary_bits(TestHBitmapData *data)
	469	{
	470	size_t size = MIN(data->size, data->old_size);
	471
	472	if (data->granularity == 0) {
	473	hbitmap_test_check_get(data);
	474	hbitmap_test_check(data, 0);
	475	} else {
	476	/* If a granularity was set, note that every distinct
	477	* (bit >> granularity) value that was set will increase
	478	* the bit pop count by 2^granularity, not just 1.
	479	*
	480	* The hbitmap_test_check facility does not currently tolerate
	481	* non-zero granularities, so test the boundaries and the population
	482	* count manually.
	483	*/
	484	g_assert(hbitmap_get(data->hb, 0));
	485	g_assert(hbitmap_get(data->hb, size - 1));
	486	g_assert_cmpint(2 << data->granularity, ==, hbitmap_count(data->hb));
	487	}
	488	}
	489
	490	/* Generic truncate test. */
	491	static void hbitmap_test_truncate(TestHBitmapData *data,
	492	size_t size,
	493	ssize_t diff,
	494	int granularity)
	495	{
	496	hbitmap_test_init(data, size, granularity);
	497	hbitmap_test_set_boundary_bits(data, diff);
	498	hbitmap_test_truncate_impl(data, size + diff);
	499	hbitmap_test_check_boundary_bits(data);
	500	}
	501
	502	static void test_hbitmap_truncate_nop(TestHBitmapData *data,
	503	const void *unused)
	504	{
	505	hbitmap_test_truncate(data, L2, 0, 0);
	506	}
	507
	508	/**
	509	* Grow by an amount smaller than the granularity, without crossing
	510	* a granularity alignment boundary. Effectively a NOP.
	511	*/
512	static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data,
513	const void *unused)
514	{
515	size_t size = L2 - 1;
516	size_t diff = 1;
517	int granularity = 1;
518
519	hbitmap_test_truncate(data, size, diff, granularity);
520	}
521
522	/**
523	* Shrink by an amount smaller than the granularity, without crossing
524	* a granularity alignment boundary. Effectively a NOP.
525	*/
526	static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data,
527	const void *unused)
528	{
529	size_t size = L2;
530	ssize_t diff = -1;
531	int granularity = 1;
532
533	hbitmap_test_truncate(data, size, diff, granularity);
534	}
535
536	/**
537	* Grow by an amount smaller than the granularity, but crossing over
538	* a granularity alignment boundary.
539	*/
540	static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data,
541	const void *unused)
542	{
543	size_t size = L2 - 2;
544	ssize_t diff = 1;
545	int granularity = 1;
546
547	hbitmap_test_truncate(data, size, diff, granularity);
548	}
549
550	/**
551	* Shrink by an amount smaller than the granularity, but crossing over
552	* a granularity alignment boundary.
553	*/
554	static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data,
555	const void *unused)
556	{
557	size_t size = L2 - 1;
558	ssize_t diff = -1;
559	int granularity = 1;
560
561	hbitmap_test_truncate(data, size, diff, granularity);
562	}
563
564	/**
565	* Grow by an amount smaller than sizeof(long), and not crossing over
566	* a sizeof(long) alignment boundary.
567	*/
568	static void test_hbitmap_truncate_grow_small(TestHBitmapData *data,
569	const void *unused)
570	{
571	size_t size = L2 + 1;
572	size_t diff = sizeof(long) / 2;
573
574	hbitmap_test_truncate(data, size, diff, 0);
575	}
576
577	/**
578	* Shrink by an amount smaller than sizeof(long), and not crossing over
579	* a sizeof(long) alignment boundary.
580	*/
581	static void test_hbitmap_truncate_shrink_small(TestHBitmapData *data,
582	const void *unused)
583	{
584	size_t size = L2;
585	size_t diff = sizeof(long) / 2;
586
587	hbitmap_test_truncate(data, size, -diff, 0);
588	}
589
590	/**
591	* Grow by an amount smaller than sizeof(long), while crossing over
592	* a sizeof(long) alignment boundary.
593	*/
594	static void test_hbitmap_truncate_grow_medium(TestHBitmapData *data,
595	const void *unused)
596	{
597	size_t size = L2 - 1;
598	size_t diff = sizeof(long) / 2;
599
600	hbitmap_test_truncate(data, size, diff, 0);
601	}
602
603	/**
604	* Shrink by an amount smaller than sizeof(long), while crossing over
605	* a sizeof(long) alignment boundary.
606	*/
607	static void test_hbitmap_truncate_shrink_medium(TestHBitmapData *data,
608	const void *unused)
609	{
610	size_t size = L2 + 1;
611	size_t diff = sizeof(long) / 2;
612
613	hbitmap_test_truncate(data, size, -diff, 0);
614	}
615
616	/**
617	* Grow by an amount larger than sizeof(long).
618	*/
619	static void test_hbitmap_truncate_grow_large(TestHBitmapData *data,
620	const void *unused)
621	{
622	size_t size = L2;
623	size_t diff = 8 * sizeof(long);
624
625	hbitmap_test_truncate(data, size, diff, 0);
626	}
627
628	/**
629	* Shrink by an amount larger than sizeof(long).
630	*/
631	static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
632	const void *unused)
633	{
634	size_t size = L2;
635	size_t diff = 8 * sizeof(long);
636
637	hbitmap_test_truncate(data, size, -diff, 0);
638	}
639
e7c033c3 PB	640	static void hbitmap_test_add(const char *testpath,
	641	void (test_func)(TestHBitmapData data, const void *user_data))
	642	{
	643	g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func,
	644	hbitmap_test_teardown);
	645	}
	646
	647	int main(int argc, char **argv)
	648	{
	649	g_test_init(&argc, &argv, NULL);
	650	hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero);
	651	hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
	652	hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
e7c033c3 PB	653	hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
	654	hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
	655	hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
	656	hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
	657	hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
	658	hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one);
	659	hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem);
	660	hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set);
	661	hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice);
	662	hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
	663	hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
	664	hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
c6a8c328	665	hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all);
e7c033c3	666	hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
a94e87c0 JS	667
	668	hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop);
	669	hbitmap_test_add("/hbitmap/truncate/grow/negligible",
	670	test_hbitmap_truncate_grow_negligible);
	671	hbitmap_test_add("/hbitmap/truncate/shrink/negligible",
	672	test_hbitmap_truncate_shrink_negligible);
	673	hbitmap_test_add("/hbitmap/truncate/grow/tiny",
	674	test_hbitmap_truncate_grow_tiny);
	675	hbitmap_test_add("/hbitmap/truncate/shrink/tiny",
	676	test_hbitmap_truncate_shrink_tiny);
	677	hbitmap_test_add("/hbitmap/truncate/grow/small",
	678	test_hbitmap_truncate_grow_small);
	679	hbitmap_test_add("/hbitmap/truncate/shrink/small",
	680	test_hbitmap_truncate_shrink_small);
	681	hbitmap_test_add("/hbitmap/truncate/grow/medium",
	682	test_hbitmap_truncate_grow_medium);
	683	hbitmap_test_add("/hbitmap/truncate/shrink/medium",
	684	test_hbitmap_truncate_shrink_medium);
	685	hbitmap_test_add("/hbitmap/truncate/grow/large",
	686	test_hbitmap_truncate_grow_large);
	687	hbitmap_test_add("/hbitmap/truncate/shrink/large",
	688	test_hbitmap_truncate_shrink_large);
e7c033c3 PB	689	g_test_run();
	690
	691	return 0;
	692	}