tictoc_atomicread_test.cpp

/* -------------------------------------------------------
 *  tictoc_atomicread_test.cpp
 *
 *  The MIT License (MIT)
 *  Copyright (c) 2017 SAKATA Sinji
 *
 *  References
 *  - TicToc https://people.csail.mit.edu/sanchez/papers/2016.tictoc.sigmod.pdf
 *  - oltp-cc-bench https://github.com/starpos/oltp-cc-bench
 * ------------------------------------------------------- */

#include <iostream>
#include <thread>
#include <xmmintrin.h>

using namespace std;

struct TsWord {
	union {
		uint64_t obj;
		struct {
			bool lock:1;
			uint16_t delta:15;
			uint64_t wts:48;
		};
	};

	TsWord() {}
	void init() {
		obj = 0;
	}
	TsWord(uint64_t v) : obj(v) {}
	operator uint64_t() const {
		return obj;
	}
	bool operator==(const TsWord& rhs) const {
		return obj == rhs.obj;
	}
	bool operator!=(const TsWord& rhs) const {
		return !operator==(rhs);
	}
	uint64_t rts() const { return wts + delta; }
};

struct Mutex {
	TsWord tsw;

	Mutex() : tsw() { tsw.init(); }
	TsWord atomicRead() const {
		return (TsWord)__atomic_load_n(&tsw.obj, __ATOMIC_RELAXED);
	}
	bool compareAndSwap(TsWord& expected, const TsWord desired) {
		return __atomic_compare_exchange_n(
			&tsw.obj, &expected.obj, desired.obj,
			false, __ATOMIC_RELAXED, __ATOMIC_RELAXED);
	}
	void set(const TsWord& desired) {
		tsw.obj = desired.obj;
	}

	void atomicSet(const TsWord& desired) {
		__atomic_store_n(&tsw.obj, desired.obj, __ATOMIC_RELAXED);
	}
};

void lock(Mutex *mutex) {
	TsWord v1 = mutex->atomicRead();
	TsWord v2;

	while (true) {
		while (v1.lock) {
			_mm_pause();
			v1 = mutex->atomicRead();
		}

		v2 = v1;
		v2.lock = true;
		if (mutex->compareAndSwap(v1, v2)) {
			break;
		}
	}
}

void unlock(Mutex *mutex, const TsWord& desired) {
	__atomic_thread_fence(__ATOMIC_RELEASE);
	mutex->set(desired);
}

inline void readFence() {
	__atomic_thread_fence(__ATOMIC_ACQUIRE);
}

struct Row {
	Mutex mutex;
	int data;
};

Row master;

Row read(Row *row) {
	TsWord v1, v2;
	int data;
	do {
		v1 = row->mutex.atomicRead();
		data = row->data;
		readFence();
		v2 = row->mutex.atomicRead();
	} while (v1 != v2 || v1.lock);

	Row resp;
	resp.mutex.tsw = v1;
	resp.data = data;

	return resp;
}

#define TASK_NUM 10000000

void reader() {
	for (int i = 0; i < TASK_NUM; i++) {
		Row row = read(&master);
		if (row.data != (int)row.mutex.tsw.wts) {
			printf("anomaly: data=%d wts=%d\n", row.data, (int)row.mutex.tsw.wts);
			break;
		}
	}
}

void writer() {
	TsWord v;
	v.init();
	for (int i = 1; i <= TASK_NUM; i++) {
		__atomic_thread_fence(__ATOMIC_ACQ_REL);
		lock(&master.mutex);
		v.wts = i;
		master.data = i;
		unlock(&master.mutex, v);
	}
}

int main() {
	thread t1(reader);
	thread t2(writer);

	t1.join();
	t2.join();

	cout << "master.data:  " << master.data << endl;
	cout << "master.wts:   " << master.mutex.tsw.wts << endl;
	cout << "master.lock:  " << master.mutex.tsw.lock << endl;
	cout << "master.delta: " << master.mutex.tsw.delta << endl;
}