Implement RCU synchronization mechanism
ClosedPublic
Actions

Authored by deadalnix on Dec 31 2018, 17:06.

Details

Reviewers

Fabien
jasonbcox

Group Reviewers

Restricted Project

Commits

rSTAGING9189d17f97d3: Implement RCU synchronization mechanism
rABC9189d17f97d3: Implement RCU synchronization mechanism

Summary

This is a userspace implementation of the RCU synchronization primitives.

It is achieved by using a structure per thread in thread local storage. The structures are put together in a linked list that can be traversed lock free by the synchronize operation. The structures are removed from the linkedlist when a thread is shut down.

The synchronization is based on a global revision variable which works in a way similar to source control. The synchronize operation increment the revision and wait for each thread is eithernotholding the lock or have advanced past the revision numer to consider a given state synchronized.

Each thread keep track of the revision it has reached when acquiring the RCULock in its threadlocal datastructure. When the lock is released, a special value is put in the local state indicating that the thread is not currently holding the lock.

Test Plan

Added unit test to cover the whole mechanism and check each intermediate step. Ran the test with COUNT = 4000000 .

Diff Detail

Repository

rABC Bitcoin ABC

Lint

Lint Not Applicable

Unit

Tests Not Applicable

Event Timeline

deadalnix created this revision.Dec 31 2018, 17:06

Herald added a reviewer: Restricted Project. · View Herald TranscriptDec 31 2018, 17:06

Herald added a subscriber: schancel. · View Herald Transcript

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing started.

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing passed.

Harbormaster completed remote builds in B4392: Diff 6475.Dec 31 2018, 17:16

Fabien requested changes to this revision.Jan 2 2019, 22:55

Fabien added a subscriber: Fabien.

Fabien added inline comments.

src/rcu.cpp
14 ↗	(On Diff #6475)	tim->time
14 ↗	(On Diff #6475)	buzy->busy
14 ↗	(On Diff #6475)	yeilding->yelding
49 ↗	(On Diff #6475)	concurently wth->concurrently with
64 ↗	(On Diff #6475)	successful->successful
77 ↗	(On Diff #6475)	concurently->concurrently
78 ↗	(On Diff #6475)	atomicaly->atomically
87 ↗	(On Diff #6475)	resurected->resurrected
88 ↗	(On Diff #6475)	we sure->we make sure, concurent->concurrent
97 ↗	(On Diff #6475)	concurent->concurrent
118 ↗	(On Diff #6475)	You may want to move it outside of the loop, as there is a theoretical max number of time you can lock the same mutex
123 ↗	(On Diff #6475)	This call is not needed, the one from `hasSynced()` is enough
138 ↗	(On Diff #6475)	ony->only
140 ↗	(On Diff #6475)	concurent->concurrent, also tip->head would be more accurate
149 ↗	(On Diff #6475)	to to->to
src/test/rcu_tests.cpp
16 ↗	(On Diff #6475)	Should return bool
81 ↗	(On Diff #6475)	th eother->the other

This revision now requires changes to proceed.Jan 2 2019, 22:55

Fabien added inline comments.Jan 2 2019, 22:57

src/rcu.cpp
14 ↗	(On Diff #6475)	yeilding->yielding

deadalnix added inline comments.Jan 3 2019, 08:19

src/rcu.cpp
118 ↗	(On Diff #6475)	That would prevent any concurrent thread from moving forward as long as this is not finished, which doesn't seem very desirable.
123 ↗	(On Diff #6475)	This is reading the linked list, so this require a lock. Technically, there is the mutex that makes it redundant, but it make the code fragile.

Mostly typos

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing started.

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing passed.

Harbormaster completed remote builds in B4403: Diff 6489.Jan 3 2019, 08:30

Use static when apropriate

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing started.

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing passed.

Harbormaster completed remote builds in B4429: Diff 6530.Jan 7 2019, 00:03

jasonbcox requested changes to this revision.Jan 7 2019, 07:24

jasonbcox added a subscriber: jasonbcox.

jasonbcox added inline comments.

src/rcu.cpp
168 ↗	(On Diff #6530)	Should reset count to 0, otherwise it will yield every time after RCU_ACTIVE_LOOP_COUNT

This revision now requires changes to proceed.Jan 7 2019, 07:24

deadalnix requested review of this revision.Jan 7 2019, 14:32

deadalnix added inline comments.

src/rcu.cpp
168 ↗	(On Diff #6530)	Yes. Reaching this point clearly indicate that there is some other thread holding the lock for a long time and starving it of resources isn't going to help it be faster.

jasonbcox added inline comments.Jan 7 2019, 21:43

src/rcu.cpp
168 ↗	(On Diff #6530)	Ok. Just making sure this was thought through.
src/test/rcu_tests.cpp
100 ↗	(On Diff #6530)	Just for my understanding: is `otherstep.load()` necessary here? It seems that just `otherstep` can be used since `std::atomic::operator T` is atomic. Related: I noticed the implementation uses `.store()` and `.load()` throughout, but the tests do not. For consistency, I think it makes sense to use them explicitly, but this is not strictly necessary.