[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH 3/4] Add rwlocks.
- Subject: Re: [PATCH 3/4] Add rwlocks.
- From: Ori Bernstein <ori@xxxxxxxxxxxxxx>
- Reply-to: myrddin-dev@xxxxxxxxxxxxxx
- Date: Wed, 15 Aug 2018 22:20:22 -0700
- To: myrddin-dev@xxxxxxxxxxxxxx
- Cc: iriri <iri@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
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