Re: [PATCH 3/4] Add rwlocks.

[Ori Bernstein <ori@xxxxxxxxxxxxxx>]

On Sat, 11 Aug 2018 19:15:05 -0700, iriri <iri@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

> I'm not 100% sure about the futex-based implementation, which is based on musl's. I
> kind of think it should favor writers more.

That decision probably needs a benchmark to inform it. You're probably write,
but this implementation has the benefit of being clear, and reasonably easy
to understand.

> ---
>  lib/thread/bld.sub          |   2 +
>  lib/thread/rwlock+futex.myr |  90 ++++++++++++++++++++++
>  lib/thread/rwlock.myr       | 149 ++++++++++++++++++++++++++++++++++++
>  lib/thread/test/mutex.myr   |  15 ++--
>  lib/thread/test/rwlock.myr  |  50 ++++++++++++
>  5 files changed, 297 insertions(+), 9 deletions(-)
>  create mode 100644 lib/thread/rwlock+futex.myr
>  create mode 100644 lib/thread/rwlock.myr
>  create mode 100644 lib/thread/test/rwlock.myr
> 
> diff --git a/lib/thread/bld.sub b/lib/thread/bld.sub
> index ed2ea2dc..eff3c5bd 100644
> --- a/lib/thread/bld.sub
> +++ b/lib/thread/bld.sub
> @@ -6,11 +6,13 @@ lib thread =
>  	condvar.myr
>  	mutex.myr
>  	ncpu.myr
> +	rwlock.myr
>  	sem.myr
>  	waitgrp.myr
>  
>  	# futex-based impls
>  	mutex+futex.myr
> +	rwlock+futex.myr
>  	sem+futex.myr
>  	waitgrp+futex.myr
>  
> diff --git a/lib/thread/rwlock+futex.myr b/lib/thread/rwlock+futex.myr
> new file mode 100644
> index 00000000..a8aadf45
> --- /dev/null
> +++ b/lib/thread/rwlock+futex.myr
> @@ -0,0 +1,90 @@
> +use std
> +
> +use "atomic"
> +use "futex"
> +
> +pkg thread =
> +	type rwlock = struct
> +		_state : ftxtag /* _nreaders:31 : uint32, _wbit:1 : uint32 */
> +	;;
> +
> +	const mkrw       : (-> rwlock)
> +	const rwrlock    : (rw : rwlock# -> void)
> +	const rwwlock    : (rw : rwlock# -> void)
> +	const rwtryrlock : (rw : rwlock# -> bool)
> +	const rwtrywlock : (rw : rwlock# -> bool)
> +	const rwrunlock  : (rw : rwlock# -> void)
> +	const rwwunlock  : (rw : rwlock# -> void)
> +;;
> +
> +const Nrmask = 0x7fffffff
> +const Wbit   = 0x80000000

Slightly confusing naming -- this is a wait bit, not a writer bit.
either comment, or rename to Waitbit.

> +
> +const mkrw = {
> +	-> [._state = 0]
> +}
> +
> +const rwrlock = {rw

I think `rdlock` and `wrlock` are clearer names. Other than that,
generally looks good to me. A bit of comment on what the approach
taken is would be good, but tracing it out on paper makes me think
this is sane.

> +	for ; ;
> +		var s = xget(&rw._state)
> +		match s & Nrmask
> +		| Nrmask - 1: std.die("error: rwlock overflowed\n")
> +		| Nrmask:
> +			if xcas(&rw._state, s, Nrmask | Wbit) == s
> +				ftxwait(&rw._state, Nrmask | Wbit, 0)
> +			;;
> +		| _:
> +			if xcas(&rw._state, s, s + 1) == s
> +				-> void
> +			;;
> +		;;
> +	;;
> +}
> +
> +const rwwlock = {rw
> +	for ; ;
> +		var s = xcas(&rw._state, 0, Nrmask)
> +		if s == 0
> +			-> void
> +		;;
> +
> +		if xcas(&rw._state, s, s | Wbit) == s
> +			ftxwait(&rw._state, s | Wbit, 0)
> +		;;
> +	;;
> +}
> +
> +const rwtryrlock = {rw
> +	for ; ;
> +		var s = xget(&rw._state)
> +		match s & Nrmask
> +		| Nrmask - 1: std.die("error: rwlock overflowed\n")
> +		| Nrmask: -> false
> +		| _:
> +			if xcas(&rw._state, s, s + 1) == s
> +				-> true
> +			;;
> +		;;
> +	;;
> +	-> false /* Unreachable */
> +}
> +
> +const rwtrywlock = {rw
> +	-> xcas(&rw._state, 0, Nrmask) == 0
> +}
> +
> +const rwrunlock = {rw
> +	var prev = xadd(&rw._state, -1)
> +	std.assert(prev & Nrmask != 0, "error: rwlock underflowed\n")
> +	if prev & Nrmask == 1 && prev & Wbit != 0
> +		if xcas(&rw._state, Wbit, 0) == Wbit
> +			ftxwake(&rw._state)
> +		;;
> +	;;
> +}
> +
> +const rwwunlock = {rw
> +	if xchg(&rw._state, 0) & Wbit != 0
> +		ftxwakeall(&rw._state) /* Just Do It(tm). */
> +	;;
> +}
> diff --git a/lib/thread/rwlock.myr b/lib/thread/rwlock.myr
> new file mode 100644
> index 00000000..a8241218

Discussed the fallback on IRC, and I think we have a simpler
implementation. There's a bit more thinking/modeling we need.



-- 
    Ori Bernstein