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
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; 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
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.

deadalnix updated this revision to Diff 6489.Jan 3 2019, 08:19

Mostly typos

deadalnix updated this revision to Diff 6530.Jan 6 2019, 23:52

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

Fabien accepted this revision.Jan 8 2019, 10:56

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() ?

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