Paths

Table of Contentst

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

Branch

rcumap

Lint

Lint Passed

Unit

No Test Coverage

Build Status

Buildable 4392
Build 6849: Bitcoin ABC Buildbot (legacy)
Build 6848: arc lint + arc unit

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	tim->time
14	buzy->busy
14	yeilding->yelding
49	concurently wth->concurrently with
64	successful->successful
77	concurently->concurrently
78	atomicaly->atomically
87	resurected->resurrected
88	we sure->we make sure, concurent->concurrent
97	concurent->concurrent
118	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	This call is not needed, the one from `hasSynced()` is enough
138	ony->only
140	concurent->concurrent, also tip->head would be more accurate
149	to to->to
src/test/rcu_tests.cpp
16	Should return bool
81	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	yeilding->yielding

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

src/rcu.cpp
118	That would prevent any concurrent thread from moving forward as long as this is not finished, which doesn't seem very desirable.
123	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.