blob: b646f0ceef0d04d6cad73226730f0467a74d96ca (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
Guards and locks
================
Apart from ``spawn`` and ``parallel`` Nim also provides all the common low level
concurrency mechanisms like locks, atomic intristics or condition variables.
Nim significantly improves on the safety of these features via additional
pragmas:
1) A `guard`:idx: annotation is introduced to prevent data races.
2) Every access of a guarded memory location needs to happen in an
appropriate `locks`:idx: statement.
3) Locks and routines can be annotated with `lock levels`:idx: to prevent
deadlocks at compile time.
Guards and the locks section
----------------------------
Protecting global variables
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Global variables and object fields can be annotated via an ``guard`` pragma:
.. code-block:: nim
var glock: TLock
var gdata {.guard: glock.}: int
The compiler then ensures that every access of ``gdata`` is within a ``locks``
section:
.. code-block:: nim
proc invalid =
# invalid: unguarded access:
echo gdata
proc valid =
# valid access:
{.locks: [glock].}:
echo gdata
Top level accesses to ``gdata`` are always allowed so that it can be initialized
conveniently. It is *assumed* (but not enforced) that every top level statement
is executed before any concurrent action happens.
The ``locks`` section deliberately looks ugly because it has no runtime
semantics and should not be used directly! It should only be used in templates
that also implement some form of locking at runtime:
.. code-block:: nim
template lock(a: TLock; body: stmt) =
pthread_mutex_lock(a)
{.locks: [a].}:
try:
body
finally:
pthread_mutex_unlock(a)
The guard does not need to be of any particular type. It is flexible enough to
model low level lockfree mechanisms:
.. code-block:: nim
var dummyLock {.compileTime.}: int
var atomicCounter {.guard: dummyLock.}: int
template atomicRead(x): expr =
{.locks: [dummyLock].}:
memoryReadBarrier()
x
echo atomicRead(atomicCounter)
The ``locks`` pragma takes a list of lock expressions ``locks: [a, b, ...]``
in order to support *multi lock* statements. Why these are essential is
explained in the `lock levels`_ section.
Protecting general locations
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The ``guard`` annotation can also be used to protect fields within an object.
The guard then needs to be another field within the same object or a
global variable.
Since objects can reside on the heap or on the stack this greatly enhances the
expressivity of the language:
.. code-block:: nim
type
ProtectedCounter = object
v {.guard: L.}: int
L: TLock
proc incCounters(counters: var openArray[ProtectedCounter]) =
for i in 0..counters.high:
lock counters[i].L:
inc counters[i].v
The access to field ``x.v`` is allowed since its guard ``x.L`` is active.
After template expansion, this amounts to:
.. code-block:: nim
proc incCounters(counters: var openArray[ProtectedCounter]) =
for i in 0..counters.high:
pthread_mutex_lock(counters[i].L)
{.locks: [counters[i].L].}:
try:
inc counters[i].v
finally:
pthread_mutex_unlock(counters[i].L)
There is an analysis that checks that ``counters[i].L`` is the lock that
corresponds to the protected location ``counters[i].v``. This analysis is called
`path analysis`:idx: because it deals with paths to locations
like ``obj.field[i].fieldB[j]``.
The path analysis is **currently unsound**, but that doesn't make it useless.
Two paths are considered equivalent if they are syntactically the same.
This means the following compiles (for now) even though it really should not:
.. code-block:: nim
{.locks: [a[i].L].}:
inc i
access a[i].v
Lock levels
-----------
Lock levels are used to enforce a global locking order in order to prevent
deadlocks at compile-time. A lock level is an constant integer in the range
0..1_000. Lock level 0 means that no lock is acquired at all.
If a section of code holds a lock of level ``M`` than it can also acquire any
lock of level ``N < M``. Another lock of level ``M`` cannot be acquired. Locks
of the same level can only be acquired *at the same time* within a
single ``locks`` section:
.. code-block:: nim
var a, b: TLock[2]
var x: TLock[1]
# invalid locking order: TLock[1] cannot be acquired before TLock[2]:
{.locks: [x].}:
{.locks: [a].}:
...
# valid locking order: TLock[2] acquired before TLock[1]:
{.locks: [a].}:
{.locks: [x].}:
...
# invalid locking order: TLock[2] acquired before TLock[2]:
{.locks: [a].}:
{.locks: [b].}:
...
# valid locking order, locks of the same level acquired at the same time:
{.locks: [a, b].}:
...
So here is how a typical multilock statement can be implemented in Nim:
.. code-block:: nim
template multilock(a, b: ptr TLock; body: stmt) =
if cast[ByteAddress](a) < cast[ByteAddress](b):
pthread_mutex_lock(a)
pthread_mutex_lock(b)
else:
pthread_mutex_lock(b)
pthread_mutex_lock(a)
{.locks: [a, b].}:
try:
body
finally:
pthread_mutex_unlock(a)
pthread_mutex_unlock(b)
Whole routines can also be annotated with a ``locks`` pragma that takes a lock
level. This then means that the routine may acquire locks of up to this level.
This is essential so that procs can be called within a ``locks`` section:
.. code-block:: nim
proc p() {.locks: 3.} = discard
var a: TLock[4]
{.locks: [a].}:
# p's locklevel (3) is strictly less than a's (4) so the call is allowed:
p()
As usual ``locks`` is an inferred effect and there is a subtype
relation: ``proc () {.locks: N.}`` is a subtype of ``proc () {.locks: M.}``
iff (M <= N).
|