Use reader lock where possible

[ivmai]

This idea (pointed out by @bcardiff in #362) is to improve concurrency with RWLock - acquire writer lock during GC, while reader lock should be sufficient to access GC_lookup_thread and manipulating data local to the current thread (e.g. as in GC_do_blocking_inner).
READER_[UN}LOCK() macros could be introduced.
Replacing LOCK to READER_LOCK could be done independently in each function where possible.
Configuration macro: e.g. USE_RWLOCK (to use SRWLOCK (Win32) or pthread_rwlock_t)

[1] https://docs.microsoft.com/en-us/windows/win32/sync/slim-reader-writer--srw--locks (Windows Vista+)
[2] https://linux.die.net/man/3/pthread_rwlock_wrlock

[ivmai]

More links (about unlocking in case of POSIX rw lock):

• https://man7.org/linux/man-pages/man3/pthread_rwlock_unlock.3p.html
• https://codebrowser.dev/glibc/glibc/nptl/pthread_rwlock_common.c.html#__pthread_rwlock_rdunlock

[ivmai]

The major operations that could benefit from introducing RW lock are

• client callers of GC_REVEAL_POINTER (because converting a hidden to a real pointer requires verifying that the object still exists)
• GC_do_blocking (in case of using it to switch between routines - GC_do_blocking(SwitchtoFiber, fb))

However GC_do_blocking writes SP to GC context of the current thread, thus there seems a need of a store release barrier (so that changes made to GC threads context be visible to the thread which acquires the writer lock (to do garbage collection which involves reading of all GC thread contexts).

I've added 3 macros to support reader variant of the GC lock:

• READER_LOCK()
• READER_UNLOCK()
• READER_UNLOCK_RELEASE() - READER_UNLOCK() with the guarantee that local writes done before it will be visible to the thread after normal (exclusive) LOCK().

[ivmai]

About READER_UNLOCK_RELEASE() implementation: does pthread_rw_rdunlock contain a release barrier? Same question for ReleaseSRWLockShared.

[ivmai]

client callers of GC_REVEAL_POINTER (because converting a hidden to a real pointer requires verifying that the object still exists)

To support this I'm planning to add GC_call_with_reader_lock(fn, arg, int release) // where release!=0 means to call READER_UNLOCK_RELEASE() instead of READER_UNLOCK().
(Of course, using of the new API will require changes on client side.)

[ivmai]

@hboehm, @bcardiff, do you know about release semantic of unlocking of the reader lock (so that to see data changes after acquiring the exclusive lock)? See my posts above.

[hboehm]

I haven't looked at the potential bdwgc use case here carefully. In general a rwlock reader unlock should "synchronize with", i.e. make memory operations visible to a subsequent writer lock acquisition, and the same with a writer unlock and a subsequent reader lock. C++ is clear about this; Posix less so, but I think it basically still says that. I'm pretty sure that Android bionic gets it right. I think this mostly has to be the case for anything to work correctly. However it doesn't seem completely inconceivable that somebody would mishandle write in a reader critical section, which is your case. Note that the reader unlock operation needs to have at least partial release semantics to ensure that the reader critical section can't see writes from a later writer critical section. But hardware tends to have fences that are restricted to loads or stores, so it may still be possible to get this wrong by not supporting writes . But I think it would be hard to defend such an interpretation in light of current specifications. Thus I would be inclined to assume that relock unlock operations have the release semantics you need. A general concern about the use of rwlocks is that individual lock/unlock operations tend to be no cheaper, and maybe slightly more expensive than simple mutex operations. And readers will still contend on the cache line containing the lock. So the question is whether the critical sections are long enough for actual reader concurrency buys enough to make this worthwhile. Hans

…

On Fri, Sep 9, 2022 at 12:15 AM Ivan Maidanski ***@***.***> wrote: @hboehm <https://github.com/hboehm>, @bcardiff <https://github.com/bcardiff>, do you know about release semantic of unlocking of the reader lock (so that to see data changes after acquiring the exclusive lock)? See my posts above. — Reply to this email directly, view it on GitHub <#473 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAHUHKX4K6MTISCCBJWU3VLV5LPZ3ANCNFSM6AAAAAAQEUVWVM> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[bcardiff]

In Crystal, the RWLock uses mostly sequential consistent semantics (as explained in https://llvm.org/docs/LangRef.html#atomic-memory-ordering-constraints) for it's implementation. This has proven better for us than acquiring a GC lock.

For reference the implementation is at https://github.com/crystal-lang/crystal/blob/master/src/crystal/rw_lock.cr. The relevant implementation of the Atomic counter are https://github.com/crystal-lang/crystal/blob/master/src/atomic.cr#L50-L70 and https://github.com/crystal-lang/crystal/blob/master/src/atomic.cr#L182-L195 . The two things that might be worth mentioning is that write_unlock uses a lazy_set (ie: normal write) at https://github.com/crystal-lang/crystal/blob/master/src/crystal/rw_lock.cr#L35 and that we yield the cpu while waiting on reader and writer locks at https://github.com/crystal-lang/crystal/blob/master/src/crystal/rw_lock.cr#L8-L10 and https://github.com/crystal-lang/crystal/blob/master/src/crystal/rw_lock.cr#L24-L32 . That yielding is arch dependent and is implemented by https://github.com/crystal-lang/crystal/blob/master/src/intrinsics.cr#L163-L169 .

Maybe @ggiraldez or @ysbaddaden can offer some other insight from their time implementing this.

[hboehm]

I think the concern here would be with an implementation that implements read-unlock with only a "load-store fence", i.e. a fence that orders only loads with respect to stores, and doesn't order stores with respect to stores. Such a fence exists on a few architectures (SPARC, RISC-V), but not in most programming languages. But, I think it would take a very creative interpretation of the Posix spec to allow that, since it doesn't say anything about restricting reader critical sections to load. In fact, it's pretty clear from the spec that if you have only two threads, one of which uses read locks and the other uses only write locks, then a rwlock should behave like a mutex. But that would be false for such an implementation that uses a load-store fence for the reader. I'm more and more convinced that if pthread_rwlock_unlock doesn't have the release semantics Ivan wants, that should just be reported as a bug.

…

On Mon, Sep 12, 2022 at 1:14 PM Brian J. Cardiff ***@***.***> wrote: In Crystal, the RWLock uses mostly sequential consistent semantics (as explained in https://llvm.org/docs/LangRef.html#atomic-memory-ordering-constraints) for it's implementation. This has proven better for us than acquiring a GC lock. For reference the implementation is at https://github.com/crystal-lang/crystal/blob/master/src/crystal/rw_lock.cr. The relevant implementation of the Atomic counter are https://github.com/crystal-lang/crystal/blob/master/src/atomic.cr#L50-L70 and https://github.com/crystal-lang/crystal/blob/master/src/atomic.cr#L182-L195 . The two things that might be worth mentioning is that write_unlock uses a lazy_set (ie: normal write) at https://github.com/crystal-lang/crystal/blob/master/src/crystal/rw_lock.cr#L35 and that we yield the cpu while waiting on reader and writer locks at https://github.com/crystal-lang/crystal/blob/master/src/crystal/rw_lock.cr#L8-L10 and https://github.com/crystal-lang/crystal/blob/master/src/crystal/rw_lock.cr#L24-L32 . That yielding is arch dependent and is implemented by https://github.com/crystal-lang/crystal/blob/master/src/intrinsics.cr#L163-L169 . Maybe @ggiraldez <https://github.com/ggiraldez> or @ysbaddaden <https://github.com/ysbaddaden> can offer some other insight from their time implementing this. — Reply to this email directly, view it on GitHub <#473 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAHUHKQWJZPGJ52PWDIFSATV56FKXANCNFSM6AAAAAAQEUVWVM> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[ivmai]

This is an experimental implementation of the feature,
As of commit 3bfb499, the mutex-based allocator lock is replaced with rwlock (SWRLock on Win32) if the collector is built with -D USE_RWLOCK.

[ivmai]

Sometimes a hang occurs on Linux, I need to debug this.
Build: https://app.travis-ci.com/github/ivmai/bdwgc/jobs/611184313

[ivmai]

no implementation of detection that rwlock (or SWRLock) is provided by the platform

rwlock/SWRLock prototypes availability:

• Windows: if _WIN32_WINNT >= 0x0600
• pthreads: if defined __USE_UNIX98 || defined __USE_XOPEN2K
• cygwin: if __XSI_VISIBLE >= 500 || __POSIX_VISIBLE >= 200112 || __cplusplus >= 201402L

[ivmai]

Sometimes a hang occurs on Linux, I need to debug this.

The scenario is:

• one thread is trying to acquire a reader lock
• other thread is holding writer lock and does suspension of the 1st thread (using GC_suspend_thread API)
• GC_suspend_thread complete normally and the 1st thread stays inside GC_suspend_handler_inner
• no other thread can acquire writer lock - hang

I've applied a workaround - disable GC_suspend_thread if USE_RWLOCK,

[ivmai]

The feature is enabled by passing --enable-rwlock to configure or -Denable_rwlock=ON to cmake.

[ivmai]

Current limitations:

• I_HOLD_READER_LOCK() (for assertions) is always true
• no implementation of detection that rwlock (or SWRLock) is provided by the platform
• no spin locking (i.e. pthread_rwlock_trywrlock is not used)

I have not done any performance measurements so far.

[ivmai]

@bcardiff, please check the functionality. I have no more plans to do anything else regarding shared locks, as of now.