Skip to content

Instantly share code, notes, and snippets.

@davedice
davedice / InflatableSeqLock.cpp
Last active January 17, 2021 00:53
Inflatable SeqLock
// InflatableSeqLock
// Copyright(C) 2016 Oracle and/or its affiliates
// Dave Dice : https://blogs.oracle.com/dave
//
// Remarks:
// * Implements composite writer mutex and seqlock in a single word-sized lock.
// Allows optimistic reading and pessimistic writing.
// Readers don't write to shared synchronization metadata, which helps avoid
// coherence traffic. Readers must tolerate observing inconsistent state, however.
// * Writer mutex is based on LIFO-CR lock from http://arxiv.org/abs/1511.06035.
// Build: g++ -O3 -std=gnu++14 -m64 MonoTime.cc -lpthread -o MonoTime -mmemory-model=tso
//
// Dave Dice -- blogs.oracle.com/dave
#include <thread>
#include <chrono>
#include <iostream>
#include <vector>
#include <mutex>
#include <random>
Acquire(L) :
auto n = QNodeAllocate()
n->Locked = 1
auto prv = swap (&L->Tail, n)
while prv->Locked != 0 : Pause
QnodeFree (prv)
L->Owner = n
Release(L) :