tictoc_increase_test.cpp

/* -------------------------------------------------------
 *  tictoc_increase_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; }
	void setRts(uint64_t rts) { delta = rts - wts; }
};

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) {
	TsWord desired = mutex->tsw;
	desired.lock = false;
	mutex->set(desired);
}

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 1000000

bool workload() {
	__atomic_thread_fence(__ATOMIC_ACQ_REL);

	/* Read phase */
	Row row = read(&master);
	row.data++;
	/* Read phase end */

	/* Validation phase */
	lock(&master.mutex);

	TsWord commit_ts;
	commit_ts.init();
	TsWord v = master.mutex.atomicRead();
	commit_ts.wts = v.rts() + 1;

	if (row.mutex.tsw.rts() < commit_ts) {
		bool is_atomic;
		do {
			is_atomic = true;
			v = master.mutex.atomicRead();
			if (row.mutex.tsw.wts != v.wts /* || (v.rts < commit_ts && locked by other) */) {
				// abort;
				unlock(&master.mutex);
				return false;
			} else {
				// expand rts
				TsWord v2 = v;
				v2.setRts(commit_ts);
				is_atomic = master.mutex.compareAndSwap(v, v2);
			}
		} while (!is_atomic);

	}
	/* Validation phase end */

	/* Write phase */
	master.data = row.data;
	unlock(&master.mutex, commit_ts);
	/* Write phase end */

	return true;
}

void writer() {
	int abort_cnt = 0;
	for (int i = 1; i <= TASK_NUM;) {
		if (workload()) {
			i++;
		} else {
			abort_cnt++;
		}
	}

	cout << "abort_cnt: " << abort_cnt << endl;
}

int main() {
	thread t1(writer);
	thread t2(writer);
	thread t3(writer);
	thread t4(writer);

	t1.join();
	t2.join();
	t3.join();
	t4.join();

	cout << endl;
	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;
}