test_atomics.cc

/* Masstree
 * Eddie Kohler, Yandong Mao, Robert Morris
 * Copyright (c) 2012-2013 President and Fellows of Harvard College
 * Copyright (c) 2012-2013 Massachusetts Institute of Technology
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Masstree LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Masstree LICENSE file; the license in that file
 * is legally binding.
 */
#define HAVE_ALL_ASSERTIONS_ENABLED 1
#include "compiler.hh"
#include <stdlib.h>
#include <algorithm>
#include <sys/time.h>
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include "kvrandom.hh"
#include "string_slice.hh"
#include "kpermuter.hh"
#include "value_bag.hh"
#include "value_string.hh"
#include "json.hh"
#include "serial_changeset.hh"
using namespace lcdf;

uint8_t xb[100];
uint16_t xw[100];
uint32_t xl[100];

struct fake_threadinfo {
    static void* allocate(size_t sz, memtag = memtag_none) {
	return new char[sz];
    }
    static void deallocate(void* p, size_t, memtag = memtag_none) {
	delete[] reinterpret_cast<char*>(p);
    }
};

// also check bitfield layout
union myunion {
    uint32_t x;
    struct {
	unsigned one : 1;
	unsigned two : 2;
	unsigned three : 3;
    };
} xunion;

void test_atomics() {
    uint32_t x;

    xunion.one = 1;
    assert(xunion.x == 1);

    x = xchg(&xb[0], 2);
    assert(x == 0 && xb[0] == 2 && xb[1] == 0 && xb[2] == 0 && xb[3] == 0);
    x = xchg(&xb[0], 3);
    assert(x == 2 && xb[0] == 3 && xb[1] == 0 && xb[2] == 0 && xb[3] == 0);

    x = xchg(&xw[0], 1);
    assert(x == 0);

    x = fetch_and_add(&xl[0], 100);
    assert(x == 0 && xl[0] == 100);
    x = cmpxchg(&xl[0], 100, 200);
    assert(x == 100 && xl[0] == 200);
    if (bool_cmpxchg(&xl[0], 200, 300))
	xl[1] = 400;
    assert(xl[0] == 300 && xl[1] == 400);
    if (bool_cmpxchg(&xl[0], 400, 100))
	xl[1] = 500;
    assert(xl[0] == 300 && xl[1] == 400);
}

void test_psdes_nr() {
    kvrandom_psdes_nr r;
    union {
	uint32_t u;
	float f;
    } u;

    r.reset(1);
    u.u = r.next();
    assert(u.u == 0x509C0C23U);
    u.u = r[99];
    assert(u.u == 0xA66CB41A);

    r.reset(99);
    u.u = r.next();
    assert(u.u == 0x64300984);
    u.u = r[99];
    assert(u.u == 0x59BA89EB);
}

template <typename T>
void time_random() {
    T r;
    uint32_t x = 0;
    for (int i = 0; i < 1000000000; ++i)
	x ^= r.next();
    assert(x != 0);
}

template <typename T>
void time_keyslice() {
    char *b = (char *) malloc(4096);
    FILE *f = fopen("/dev/urandom", "rb");
    ssize_t rr = fread(b, 1, 4096, f);
    assert(rr == 4096);
    fclose(f);
    T x = 0;
    kvrandom_lcg_nr r;
    x ^= string_slice<T>::make(b, 1);
    for (int i = 0; i < 1000000000; ++i)
	x ^= string_slice<T>::make(b + r.next() % 2048, r.next() % 16);
    assert(x);
}

void test_kpermuter() {
    typedef kpermuter<15> kpermuter_type;
    kpermuter_type k = kpermuter_type::make_empty();
    int i = k.insert_from_back(0);
    assert(k.size() == 1 && i == 0 && k[0] == 0);
    i = k.insert_from_back(0);
    assert(k.size() == 2 && i == 1 && k[0] == 1 && k[1] == 0);
    i = k.insert_from_back(2);
    assert(k.size() == 3 && i == 2 && k[0] == 1 && k[1] == 0 && k[2] == 2);
    k.remove(1);
    assert(k.size() == 2 && k[0] == 1 && k[1] == 2 && k[2] == 0);
    k.remove(1);
    assert(k.size() == 1 && k[0] == 1 && k[1] == 2 && k[2] == 0 && k[3] == 14);
    i = k.insert_from_back(0);
    assert(k.size() == 2 && i == 3 && k[0] == 3 && k[1] == 1 && k[2] == 2 && k[3] == 0 && k[4] == 14);
    k.insert_selected(0, 3);
    assert(k.size() == 3 && k[0] == 0 && k[1] == 3 && k[2] == 1 && k[3] == 2 && k[4] == 14);
    k.insert_selected(2, 11);
    assert(k.size() == 4 && k[0] == 0 && k[1] == 3 && k[2] == 7 && k[3] == 1 && k[4] == 2
	   && k[5] == 14 && k[11] == 8 && k[12] == 6);
    k.insert_selected(2, 14);
    assert(k.size() == 5 && k[0] == 0 && k[1] == 3 && k[2] == 4 && k[3] == 7 && k[4] == 1 && k[5] == 2
	   && k[6] == 14 && k[12] == 8 && k[13] == 6);
    k.exchange(0, 1);
    assert(k.size() == 5 && k[0] == 3 && k[1] == 0 && k[2] == 4 && k[3] == 7 && k[4] == 1 && k[5] == 2
	   && k[6] == 14 && k[12] == 8 && k[13] == 6);
    k.remove_to_back(2);
    assert(k.size() == 4 && k[0] == 3 && k[1] == 0 && k[2] == 7 && k[3] == 1 && k[4] == 2
	   && k[5] == 14 && k[11] == 8 && k[12] == 6 && k[14] == 4);
    assert(k.back() == 4);
    i = k.insert_from_back(2);
    assert(k.size() == 5 && k[0] == 3 && k[1] == 0 && k[2] == 4 && k[3] == 7 && k[4] == 1 && k[5] == 2
	   && k[6] == 14 && k[12] == 8 && k[13] == 6 && i == 4);
    k.exchange(0, 0);
    assert(k.size() == 5 && k[0] == 3 && k[1] == 0 && k[2] == 4 && k[3] == 7 && k[4] == 1 && k[5] == 2
	   && k[6] == 14 && k[12] == 8 && k[13] == 6 && i == 4);

    assert(find_lowest_zero_nibble(0x0120U) == 0);
    assert(find_lowest_zero_nibble(0x0123U) == 3);
    assert(find_lowest_zero_nibble(0x12345678U) == -1);

    kpermuter<14> ka = kpermuter<14>::make_empty();
    i = ka.insert_from_back(0);
    assert(ka.size() == 1 && i == 0 && ka[0] == 0);
    i = ka.insert_from_back(0);
    assert(ka.size() == 2 && i == 1 && ka[0] == 1 && ka[1] == 0);
    i = ka.insert_from_back(2);
    assert(ka.size() == 3 && i == 2 && ka[0] == 1 && ka[1] == 0 && ka[2] == 2);
    ka.remove_to_back(1);
    assert(ka.size() == 2 && ka[0] == 1 && ka[1] == 2 && ka.back() == 0);
}

void test_string_slice() {
    typedef string_slice<uint32_t> ss_type;
    assert(ss_type::make("a", 1) == ss_type::make("aaa", 1));
    assert(ss_type::make_sloppy("0123abcdef" + 4, 1)
	   == ss_type::make_sloppy("bcdea01293" + 4, 1));
    assert(ss_type::make_comparable("a", 1) < ss_type::make_comparable("b", 1));
    assert(ss_type::equals_sloppy("0123abcdef" + 4, "abcdea02345" + 5, 1));
    assert(ss_type::make_comparable("abcd", 4) < ss_type::make_comparable("abce", 4));
    assert(ss_type::make_comparable("abce", 4) > ss_type::make_comparable("abcd", 4));
    assert(ss_type::equals_sloppy("0123abcdef" + 4, "abcdeabcd5" + 5, 4));
    assert(!ss_type::equals_sloppy("0123abcdef" + 4, "abcdeabcd5" + 5, 5));
    assert(String("12345").find_right("") == 5);
    assert(String("12345").find_right("5") == 4);
    assert(String("12345").find_right("23") == 1);
    assert(String("12345", 0).find_right("23") == -1);
}

void test_string_bag() {
    fake_threadinfo ti;
    typedef value_bag<uint16_t> bag_t;
    bag_t eb;
    if (eb.size() > sizeof(bag_t))
	fprintf(stderr, "sizes are off: %zu vs. %zu\n", eb.size(), sizeof(bag_t));
    assert(eb.size() <= sizeof(bag_t));
    bag_t* b = eb.update(0, Str("A", 1), 1, ti);
    assert(b->row_string() == Str("\001\000\006\000\007\000A", 7));
    assert(b->ncol() == 1);
    assert(b->col(0) == Str("A", 1));

    bag_t* bx = bag_t::create1(Str("A", 1), 1, ti);
    assert(bx->row_string() == b->row_string());
    bx->deallocate(ti);

    bag_t *bb = b->update(1, Str("BB", 2), 2, ti);
    b->deallocate(ti);
    b = bb;
    assert(b->row_string() == Str("\002\000"
				  "\010\000\011\000\013\000"
				  "ABB", 013));
    assert(b->ncol() == 2);
    assert(b->col(0) == Str("A", 1));
    assert(b->col(1) == Str("BB", 2));

    bb = b->update(3, Str("CCC", 3), 3, ti);
    b->deallocate(ti);
    b = bb;
    assert(b->row_string() == Str("\004\000"
				  "\014\000\015\000\017\000\017\000\022\000"
				  "ABBCCC", 022));
    assert(b->ncol() == 4);
    assert(b->col(0) == Str("A", 1));
    assert(b->col(1) == Str("BB", 2));
    assert(b->col(2) == Str("", 0));
    assert(b->col(3) == Str("CCC", 3));

    bb = b->update(1, Str("bbb", 3), 4, ti);
    b->deallocate(ti);
    b = bb;
    assert(b->row_string() == Str("\004\000"
				  "\014\000\015\000\020\000\020\000\023\000"
				  "AbbbCCC", 023));
    assert(b->ncol() == 4);
    assert(b->col(0) == Str("A", 1));
    assert(b->col(1) == Str("bbb", 3));
    assert(b->col(2) == Str("", 0));
    assert(b->col(3) == Str("CCC", 3));

    bb = b->update(0, Str("a", 1), 4, ti);
    b->deallocate(ti);
    b = bb;
    assert(b->row_string() == Str("\004\000"
				  "\014\000\015\000\020\000\020\000\023\000"
				  "abbbCCC", 023));
    assert(b->ncol() == 4);
    assert(b->col(0) == Str("a", 1));
    assert(b->col(1) == Str("bbb", 3));
    assert(b->col(2) == Str("", 0));
    assert(b->col(3) == Str("CCC", 3));

    bb = b->update(1, Str("", 0), 4, ti);
    b->deallocate(ti);
    b = bb;
    assert(b->row_string() == Str("\004\000"
				  "\014\000\015\000\015\000\015\000\020\000"
				  "aCCC", 020));
    assert(b->ncol() == 4);
    assert(b->col(0) == Str("a", 1));
    assert(b->col(1) == Str("", 0));
    assert(b->col(2) == Str("", 0));
    assert(b->col(3) == Str("CCC", 3));

    b->deallocate(ti);
}

void test_json()
{
    Json j;
    assert(j.empty());
    assert(!j);

    j = Json::make_object();
    assert(j.empty());
    assert(j);

    j.set("foo", "bar");
    assert(j["foo"]);
    assert(j["foo"].to_s() == "bar");
    assert(j.size() == 1);

    j.set("baz", "flim");
    assert(j.size() == 2);
    assert(j.unparse() == "{\"foo\":\"bar\",\"baz\":\"flim\"}");

    j.erase("foo");
    assert(j.size() == 1);

    j.assign_parse("2");
    assert(j == 2);

    j.assign_parse("null");
    assert(j == Json());

    j.assign_parse("\"a\"");
    assert(j == "a");

    j.assign_parse("[1,2]");
    assert(j.unparse() == "[1,2]");

    j.assign_parse("[[[]],{\"a\":{}}]");
    assert(j.unparse() == "[[[]],{\"a\":{}}]");

    j = Json::parse("{\"x22\":{\n\
      \"git-revision\":\"ebbd3d4767847300f552b181a10bda57a926f554M\",\n\
      \"time\":\"Tue Feb  7 20:20:33 2012\",\n\
      \"machine\":\"rtshanks-laptop\",\n\
      \"cores\":2,\n\
      \"runs\":[\"x22\\/rw2\\/mb\\/0\"]\n\
    },\n\
    \"x23\":{\n\
      \"git-revision\":\"ebbd3d4767847300f552b181a10bda57a926f554M\",\n\
      \"time\":\"Tue Feb  7 20:31:05 2012\",\n\
      \"machine\":\"rtshanks-laptop\",\n\
      \"cores\":2,\n\
      \"runs\":[\"x23\\/rw2\\/mb\\/0\",\"x23\\/rw1\\/mb\\/0\",\"x23\\/rw3\\/mb\\/0\"]\n\
    },\n\
    \"x24\":{\n\
      \"git-revision\":\"62e9970ca8ae9c6eebf2d71b7065ea694fb25282M\",\n\
      \"time\":\"Sat Feb 11 15:54:01 2012\",\n\
      \"machine\":\"rtshanks-laptop\",\n\
      \"cores\":2,\n\
      \"runs\":[\"x24\\/rw1\\/b\\/0\"]\n\
    },\"b\":\"c\",\"c\":\"d\"}");
    assert(j["x22"]["time"] == "Tue Feb  7 20:20:33 2012");
    assert(j["x22"]["cores"] == 2);
    {
	Json::object_iterator it = j.obegin();
	assert(it.key() == "x22");
	++it;
	assert(it.key() == "x23");
	++it;
	assert(it.key() == "x24");
	++it;
	assert(it.key() == "b");
	++it;
	assert(it.key() == "c");
    }

    {
	Json jcopy = j;
	assert(j.size() == 5);
	int count = 0;
	for (Json::iterator it = jcopy.begin(); it != jcopy.end(); ++it) {
	    it->second = Json();
	    ++count;
	}
	assert(!jcopy["x22"]);
	assert(j["x22"]["cores"] == 2);
	assert(count == jcopy.size());
    }

    assert(!j["x49"]);
    assert(j.size() == 5);
    assert(!j["x49"]["45"][2]["a"]);
    assert(j.size() == 5);
    j["x49"]["45"][2]["a"] = 1;
    assert(j.size() == 6);
    assert(j["x22"].is_object() && j.get("x22").is_object());
    assert(j["x23"].is_object() && j.get("x23").is_object());
    assert(j["b"].is_string() && j.get("b").is_string());
    assert(j["x49"].is_object() && j.get("x49").is_object());
    assert(j["x49"]["45"].is_array());
    assert(j["x49"]["45"].size() == 3 && j["x49"]["45"][2].is_object());

    j = Json::make_object();
    j["a"] = j["b"];
    assert(j.size() == 1);
    assert(j["a"].is_null());
    assert(j.count("a") == 1);

    j = Json::make_object();
    Json k = Json::make_array();
    j["a"] = k[2];
    assert(j.size() == 1);
    assert(k.size() == 0);
    assert(j["a"].is_null());
    assert(j.count("a") == 1);

    j = Json(1);
    assert(j.get("a").is_null());

    j.assign_parse("{\"a\":1,\"b\":true,\"c\":\"\"}");
    {
	int i = 0;
	bool b = false;
	String s;
	assert(j.get("a", i));
	assert(i == 1);
	assert(j.get("a", i).get("b", b));
	assert(b == true);
	assert(!j.get("a", s).status());
	assert(!j.get("a", s).status(b));
	assert(b == false);
	assert(j.get("a", k));
	assert(k == Json(1));
	assert(!j.get("cc", k));
    }

    j["a"] = Json(5);
    j.set("a", Json(5));
    j["b"] = Json::parse("[]");
}

void test_serial_changeset() {
    fake_threadinfo ti;
    typedef value_bag<uint16_t> bag_t;
    bag_t* eb = new(ti.allocate(sizeof(bag_t))) bag_t;
    value_string* strb = new(ti.allocate(sizeof(value_string))) value_string;

    kvout* kv = new_bufkvout();
    KVW(kv, (short) 0);
    KVW(kv, Str("ABC", 3));
    KVW(kv, (short) 1);
    KVW(kv, Str("def", 3));
    KVW(kv, (short) 2);
    KVW(kv, Str("EGHIJ", 5));
    KVW(kv, (short) 3);
    KVW(kv, Str("klm", 3));
    Str blorp(kv->buf, kv->n);

    kvout* strkv = new_bufkvout();
    KVW(strkv, (short) 0);
    KVW(strkv, (short) 3);
    KVW(strkv, Str("ABC", 3));
    KVW(strkv, (short) 3);
    KVW(strkv, (short) 3);
    KVW(strkv, Str("def", 3));
    KVW(strkv, (short) 6);
    KVW(strkv, (short) 5);
    KVW(strkv, Str("EGHIJ", 5));
    KVW(strkv, (short) 11);
    KVW(strkv, (short) 3);
    KVW(strkv, Str("klm", 3));
    Str strblorp(strkv->buf, strkv->n);

    {
        serial_changeset<short> sc(blorp);
        assert(!sc.empty());
        assert(!sc.single_index());
        assert(sc.last_index() == 3);
        bag_t* eb2 = eb->update(sc, 1, ti);
        eb->deallocate(ti);
        eb = eb2;
        assert(eb->col(0) == Str("ABC"));
        assert(eb->col(1) == Str("def"));
        assert(eb->col(2) == Str("EGHIJ"));
        assert(eb->col(3) == Str("klm"));
    }

    {
        serial_changeset<short> sc(Str(kv->buf, 9));
        assert(!sc.empty());
        assert(sc.single_index());
        assert(sc.last_index() == 0);
    }

#if 0
    kvtimestamp_t t0 = timestamp();
    for (int i = 0; i != 100000000; ++i) {
        serial_changeset<short> sc(blorp);
        bag_t* eb2 = eb->update(sc, 1, ti);
        eb->deallocate(ti);
        eb = eb2;
    }
    std::cerr << (timestamp() - t0) << "\n";
    eb->print(stderr, ">> ", 0, "K", 0);

    t0 = timestamp();
    for (int i = 0; i != 100000000; ++i) {
        serial_changeset<valueindex_string> sc(strblorp);
        value_string* strb2 = strb->update(sc, 1, ti);
        strb->deallocate(ti);
        strb = strb2;
    }
    std::cerr << (timestamp() - t0) << "\n";
    strb->print(stderr, ">> ", 0, "K", 0);
#endif

    eb->deallocate(ti);
    strb->deallocate(ti);
    free_kvout(kv);
    free_kvout(strkv);
}

int main(int, char *[])
{
    //test_atomics();
    //test_psdes_nr();
    //time_random<kvrandom_lcg_nr>();
    assert(iceil_log2(2) == 2);
    assert(iceil_log2(3) == 4);
    assert(ifloor_log2(2) == 2);
    assert(ifloor_log2(3) == 2);
    //time_keyslice<uint64_t>();
    test_kpermuter();
    test_string_slice();
    test_string_bag();
    test_json();
    test_serial_changeset();
    return 0;
}