Skip to content

Commit 224dc6a

Browse files
polytypicpolytypic
committed
Add Rwlock 
1 parent db32b99 commit 224dc6a

File tree

9 files changed

+685
-8
lines changed

9 files changed

+685
-8
lines changed

‎bench/bench_hashtbl.ml‎

Lines changed: 45 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@ let run_one ~budgetf ~n_domains ?(n_ops = 100 * Util.iter_factor)
2121

2222
let t = Hashtbl.create 1000 in
2323
let lock = Lock.create ~padded:true () in
24+
let rwlock = Rwlock.create ~padded:true () in
2425
let sem = Sem.create ~padded:true 1 in
2526

2627
let n_ops = (100 + percent_mem) * n_ops / 100 in
@@ -41,6 +42,16 @@ let run_one ~budgetf ~n_domains ?(n_ops = 100 * Util.iter_factor)
4142
Hashtbl.replace t key value
4243
done
4344
end
45+
| `Rwlock ->
46+
Rwlock.holding rwlock @@ fun () ->
47+
Hashtbl.clear t;
48+
if prepopulate then begin
49+
for _ = 1 to n_keys do
50+
let value = Random.bits () in
51+
let key = value mod n_keys in
52+
Hashtbl.replace t key value
53+
done
54+
end
4455
| `Sem ->
4556
Sem.acquire sem;
4657
Hashtbl.clear t;
@@ -87,6 +98,34 @@ let run_one ~budgetf ~n_domains ?(n_ops = 100 * Util.iter_factor)
8798
end
8899
in
89100
work ()
101+
| `Rwlock ->
102+
let rec work () =
103+
let n = Countdown.alloc n_ops_todo ~domain_index ~batch:1000 in
104+
if n <> 0 then begin
105+
for _ = 1 to n do
106+
let value = Random.State.bits state in
107+
let op = (value asr 20) mod 100 in
108+
let key = value mod n_keys in
109+
if op < percent_mem then begin
110+
Rwlock.acquire_shared rwlock;
111+
Hashtbl.find_opt t key |> ignore;
112+
Rwlock.release_shared rwlock
113+
end
114+
else if op < limit_add then begin
115+
Rwlock.acquire rwlock;
116+
Hashtbl.replace t key value;
117+
Rwlock.release rwlock
118+
end
119+
else begin
120+
Rwlock.acquire rwlock;
121+
Hashtbl.remove t key;
122+
Rwlock.release rwlock
123+
end
124+
done;
125+
work ()
126+
end
127+
in
128+
work ()
90129
| `Sem ->
91130
let rec work () =
92131
let n = Countdown.alloc n_ops_todo ~domain_index ~batch:1000 in
@@ -121,14 +160,18 @@ let run_one ~budgetf ~n_domains ?(n_ops = 100 * Util.iter_factor)
121160
Printf.sprintf "%d worker%s, %d%% reads with %s" n_domains
122161
(if n_domains = 1 then "" else "s")
123162
percent_mem
124-
(match lock_type with `Lock -> "Lock" | `Sem -> "Sem")
163+
(match lock_type with
164+
| `Lock -> "Lock"
165+
| `Rwlock -> "Rwlock"
166+
| `Sem -> "Sem")
125167
in
126168
Times.record ~budgetf ~n_domains ~n_warmups:1 ~n_runs_min:1 ~before ~init
127169
~wrap ~work ()
128170
|> Times.to_thruput_metrics ~n:n_ops ~singular:"operation" ~config
129171

130172
let run_suite ~budgetf =
131-
Util.cross [ 1; 2; 4; 8 ] (Util.cross [ `Lock; `Sem ] [ 10; 50; 90; 95; 100 ])
173+
Util.cross [ 1; 2; 4; 8 ]
174+
(Util.cross [ `Lock; `Rwlock; `Sem ] [ 10; 50; 90; 95; 100 ])
132175
|> List.concat_map @@ fun (n_domains, (lock_type, percent_mem)) ->
133176
if Picos_domain.recommended_domain_count () < n_domains then []
134177
else run_one ~budgetf ~n_domains ~percent_mem ~lock_type ()

‎bench/bench_lock_yield.ml‎

Lines changed: 19 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@ let run_one ~budgetf ~n_fibers ~use_domains ~lock_type () =
2020
let n_ops_todo = Countdown.create ~n_domains () in
2121

2222
let lock = Lock.create ~padded:true () in
23+
let rwlock = Rwlock.create ~padded:true () in
2324
let sem =
2425
Sem.create ~padded:true (match lock_type with `Sem_n n -> n | _ -> 1)
2526
in
@@ -53,6 +54,22 @@ let run_one ~budgetf ~n_fibers ~use_domains ~lock_type () =
5354
else work ()
5455
in
5556
loop n
57+
| `Rwlock ->
58+
if n <> 0 then
59+
let rec loop n =
60+
if 0 < n then begin
61+
Rwlock.acquire rwlock;
62+
let x = !v in
63+
v := x + 1;
64+
Control.yield ();
65+
assert (!v = x + 1);
66+
v := x;
67+
Rwlock.release rwlock;
68+
loop (n - 1)
69+
end
70+
else work ()
71+
in
72+
loop n
5673
| `Sem ->
5774
if n <> 0 then
5875
let rec loop n =
@@ -102,6 +119,7 @@ let run_one ~budgetf ~n_fibers ~use_domains ~lock_type () =
102119
(if n_fibers = 1 then "" else "s")
103120
(match lock_type with
104121
| `Lock -> "Lock"
122+
| `Rwlock -> "Rwlock"
105123
| `Sem -> "Sem"
106124
| `Sem_n n -> Printf.sprintf "Sem %d" n)
107125
in
@@ -112,7 +130,7 @@ let run_one ~budgetf ~n_fibers ~use_domains ~lock_type () =
112130
let run_suite ~budgetf =
113131
Util.cross [ false; true ]
114132
(Util.cross
115-
[ `Lock; `Sem; `Sem_n 2; `Sem_n 3; `Sem_n 4 ]
133+
[ `Lock; `Rwlock; `Sem; `Sem_n 2; `Sem_n 3; `Sem_n 4 ]
116134
[ 1; 2; 3; 4; 8; 256; 512; 1024 ])
117135
|> List.concat_map @@ fun (use_domains, (lock_type, n_fibers)) ->
118136
if

‎bench/bench_ref.ml‎

Lines changed: 32 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@ let run_one ~budgetf ?(n_iter = 250 * Util.iter_factor) ~lock_type
2626
(Op (name, value, op1, op2, op_kind)) =
2727
let lock = Lock.create () in
2828
let sem = Sem.create 1 in
29+
let rwlock = Rwlock.create () in
2930

3031
let loc = Ref.make value in
3132

@@ -46,6 +47,32 @@ let run_one ~budgetf ?(n_iter = 250 * Util.iter_factor) ~lock_type
4647
end
4748
in
4849
loop n_iter
50+
| `Rwlock, `RW ->
51+
let rec loop i =
52+
if i > 0 then begin
53+
Rwlock.acquire rwlock;
54+
op1 loc |> ignore;
55+
Rwlock.release rwlock;
56+
Rwlock.acquire rwlock;
57+
op2 loc |> ignore;
58+
Rwlock.release rwlock;
59+
loop (i - 2)
60+
end
61+
in
62+
loop n_iter
63+
| `Rwlock, `RO ->
64+
let rec loop i =
65+
if i > 0 then begin
66+
Rwlock.acquire_shared rwlock;
67+
op1 loc |> ignore;
68+
Rwlock.release_shared rwlock;
69+
Rwlock.acquire_shared rwlock;
70+
op2 loc |> ignore;
71+
Rwlock.release_shared rwlock;
72+
loop (i - 2)
73+
end
74+
in
75+
loop n_iter
4976
| `Sem, _ ->
5077
let rec loop i =
5178
if i > 0 then begin
@@ -63,13 +90,16 @@ let run_one ~budgetf ?(n_iter = 250 * Util.iter_factor) ~lock_type
6390

6491
let config =
6592
Printf.sprintf "%s with %s" name
66-
(match lock_type with `Lock -> "Lock" | `Sem -> "Sem")
93+
(match lock_type with
94+
| `Lock -> "Lock"
95+
| `Rwlock -> "Rwlock"
96+
| `Sem -> "Sem")
6797
in
6898
Times.record ~budgetf ~n_domains:1 ~init ~wrap ~work ()
6999
|> Times.to_thruput_metrics ~n:n_iter ~singular:"op" ~config
70100

71101
let run_suite ~budgetf =
72-
Util.cross [ `Lock; `Sem ]
102+
Util.cross [ `Lock; `Rwlock; `Sem ]
73103
[
74104
(let get x = !x in
75105
Op ("get", 42, get, get, `RO));

‎lib/picos_std.sync/picos_std_sync.ml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@ module Mutex = Mutex
22
module Condition = Condition
33
module Semaphore = Semaphore
44
module Lock = Lock
5+
module Rwlock = Rwlock
56
module Sem = Sem
67
module Lazy = Lazy
78
module Latch = Latch

‎lib/picos_std.sync/picos_std_sync.mli‎

Lines changed: 175 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,7 @@ module Mutex : sig
3030
[~checked:false] on an operation may prevent error checking also on a
3131
subsequent operation.
3232
33-
See also {!Lock}. *)
33+
See also {!Lock}, and {!Rwlock}. *)
3434

3535
type t
3636
(** Represents a mutual-exclusion lock or mutex. *)
@@ -162,9 +162,10 @@ module Lock : sig
162162
163163
🏎️ This uses a low overhead, optimistic, and unfair implementation that
164164
also does not perform runtime ownership error checking. In most cases this
165-
should be the mutual exclusion lock you will want to use.
165+
should be the mutual exclusion lock you will want to use. Consider using
166+
{!Rwlock} in case most operations are reads.
166167
167-
See also {!Mutex}. *)
168+
See also {!Mutex}, and {!Rwlock}. *)
168169

169170
type t
170171
(** Represents a poisonable mutual exclusion lock. *)
@@ -247,6 +248,177 @@ module Lock : sig
247248
in case the [lock] is not currently held exclusively. *)
248249
end
249250

251+
module Rwlock : sig
252+
(** A poisonable, freezable, read-write lock.
253+
254+
🏎️ This uses a low overhead, optimistic, and unfair implementation that
255+
also does not perform runtime ownership error checking. In most cases this
256+
should be the read-write lock you will want to use and should give roughly
257+
equal or better performance than {!Lock} in cases where the majority of
258+
operations are reads.
259+
260+
🐌 This is a "slim" lock. Acquiring the lock in read mode has low overhead,
261+
but limited scalability. For highly parallel use cases you will either
262+
want to use sharding or a "fat" scalable read-write lock.
263+
264+
⚠️ The current implementation allows readers to bypass the queue and does
265+
not prevent writers from starvation. For example, a pair of readers
266+
running concurrently, acquiring and releasing the lock such that there is
267+
never a point where the lock is fully released, prevents writers from
268+
acquiring the lock. This might be changed in the future such that neither
269+
readers nor writers should starve assuming no single party holds the lock
270+
indefinitely.
271+
272+
See also {!Lock}, and {!Mutex}. *)
273+
274+
type t
275+
(** Represents a read-write lock. *)
276+
277+
(** {1 Basic API} *)
278+
279+
val create : ?padded:bool -> unit -> t
280+
(** [create ()] returns a new read-write lock that is initially unlocked. *)
281+
282+
exception Poisoned
283+
(** Exception raised in case the read-write lock has been
284+
{{!poison} poisoned}. *)
285+
286+
val sharing : t -> (unit -> 'a) -> 'a
287+
(** [sharing rwlock thunk] acquires a shared hold on the [rwlock] and calls
288+
[thunk ()]. Whether [thunk ()] returns a value or raises an exception, the
289+
shared hold on the [rwlock] will be released.
290+
291+
A single fiber may acquire a shared hold on a specific [rwlock] multiple
292+
times and other fibers may concurrently acquire shared holds on the
293+
[rwlock] as well.
294+
295+
@raise Poisoned in case the [rwlock] has been {{!poison} poisoned}. *)
296+
297+
exception Frozen
298+
(** Exception raised in case the read-write lock has been {{!freeze} frozen}.
299+
*)
300+
301+
val holding : t -> (unit -> 'a) -> 'a
302+
(** [holding rwlock thunk] acquires an exclusive hold on the [rwlock] and
303+
calls [thunk ()]. In case [thunk ()] returns a value, the read-write lock
304+
is released and the value is returned. Otherwise the read-write lock will
305+
be {{!poison} poisoned} and the exception reraised.
306+
307+
@raise Poisoned in case the [rwlock] has been {{!poison} poisoned}.
308+
@raise Frozen in case the [rwlock] has been {{!freeze} frozen}. *)
309+
310+
val freeze : t -> unit
311+
(** [freeze rwlock] marks a [rwlock] as frozen, which means that one can no
312+
longer acquire an exclusive hold on the [rwlock].
313+
314+
ℹ️ No exclusive hold can be obtained on a frozen lock.
315+
316+
🐌 Freezing a [rwlock] does not improve the scalability of acquiring shared
317+
hold on the [rwlock].
318+
319+
@raise Poisoned in case the [rwlock] has been {{!poison} poisoned}. *)
320+
321+
val protect : t -> (unit -> 'a) -> 'a
322+
(** [protect rwlock thunk] acquires an exclusive hold on the [rwlock], runs
323+
[thunk ()], and releases the [rwlock] after [thunk ()] returns or raises.
324+
325+
@raise Poisoned in case the lock has been {{!poison} poisoned}.
326+
@raise Frozen in case the [rwlock] has been {{!freeze} frozen}. *)
327+
328+
module Condition : sig
329+
(** A condition variable. *)
330+
331+
include Intf.Condition with type lock = t
332+
333+
val wait_shared : t -> lock -> unit
334+
(** [wait_shared condition rwlock] releases the shared hold on [rwlock],
335+
waits for the [condition], and acquires the shared hold on [rwlock]
336+
before returning or raising due to the operation being canceled.
337+
338+
ℹ️ If the lock is {{!poison} poisoned} during the {!wait_shared}, then
339+
the {!Poisoned} exception will be raised. *)
340+
end
341+
342+
(** {1 State query API} *)
343+
344+
val is_locked_shared : t -> bool
345+
(** [is_locked_shared rwlock] determines whether the [rwlock] is currently
346+
held shared or not.
347+
348+
⚠️ [is_locked_shared rwlock] will return [false] in case the [rwlock] is
349+
held exclusively. *)
350+
351+
val is_frozen : t -> bool
352+
(** [is_frozen rwlock] determines whether the [rwlock] has been
353+
{{!freeze} frozen}. *)
354+
355+
val is_locked : t -> bool
356+
(** [is_locked rwlock] determines whether the [rwlock] is currently held
357+
exclusively or not.
358+
359+
⚠️ [is_locked rwlock] will return [false] in case the [rwlock] is held
360+
shared. *)
361+
362+
val is_poisoned : t -> bool
363+
(** [is_poisoned rwlock] determines whether the [rwlock] has been
364+
{{!poison} poisoned}. *)
365+
366+
(** {1 Expert API}
367+
368+
⚠️ The calls in this section must be matched correctly or the state of the
369+
read-write lock may become corrupted. *)
370+
371+
val acquire_shared : t -> unit
372+
(** [acquire_shared rwlock] acquires a shared hold on the [rwlock].
373+
374+
A single fiber may acquire a shared hold on a specific [rwlock] multiple
375+
times and other fibers may concurrently acquire shared holds on the
376+
[rwlock] as well.
377+
378+
@raise Poisoned in case the [rwlock] has been {{!poison} poisoned}. *)
379+
380+
val try_acquire_shared : t -> bool
381+
(** [try_acquire_shared rwlock] attempts to acquire a shared hold on the
382+
[rwlock]. Returns [true] in case of success and [false] in case of
383+
failure.
384+
385+
@raise Poisoned in case the [rwlock] has been {{!poison} poisoned}. *)
386+
387+
val release_shared : t -> unit
388+
(** [release_shared rwlock] releases one shared hold on the [rwlock] or does
389+
nothing in case the [rwlock] has been {{!poison} poisoned}. *)
390+
391+
val acquire : t -> unit
392+
(** [acquire rwlock] acquires an exclusive hold on the [rwlock].
393+
394+
A fiber may acquire an exclusive hold on a specific [rwlock] once at a
395+
time.
396+
397+
@raise Poisoned in case the [rwlock] has been {{!poison} poisoned}.
398+
@raise Frozen in case the [rwlock] has been {{!freeze} frozen}. *)
399+
400+
val try_acquire : t -> bool
401+
(** [try_acquire rwlock] attempts to acquire an exclusive hold on the
402+
[rwlock]. Returns [true] in case of success and [false] in case of
403+
failure.
404+
405+
@raise Poisoned in case the [rwlock] has been {{!poison} poisoned}.
406+
@raise Frozen in case the [rwlock] has been {{!freeze} frozen}. *)
407+
408+
val release : t -> unit
409+
(** [release rwlock] releases the exclusive hold on the [rwlock] or does
410+
nothing in case the [rwlock] has been {{!freeze} frozen} or
411+
{{!poison} poisoned}. *)
412+
413+
val poison : t -> unit
414+
(** [poison rwlock] marks an exclusively held [rwlock] as poisoned.
415+
416+
ℹ️ Neither shared nor exclusive hold can be obtained on a poisoned lock.
417+
418+
@raise Invalid_argument
419+
in case the [rwlock] is not currently write locked. *)
420+
end
421+
250422
module Sem : sig
251423
(** A poisonable counting semaphore.
252424

0 commit comments

Comments
 (0)