Page MenuHomePhabricator

Implement RCU synchronization mechanism
ClosedPublic

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

Details

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

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
src/rcu.cpp
14

yeilding->yielding

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.

Use static when apropriate

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 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.

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.

Loogs good to me, just a question regarding style

src/rcu.h
23 ↗(On Diff #6530)

Why do you prefer using this method rather than UINT64_MAX or std::numerical_limits<uint64_t>::max() ?

This revision is now accepted and ready to land.Jan 8 2019, 20:16
This revision was automatically updated to reflect the committed changes.