LEFT | RIGHT |
1 // Copyright 2009 The Go Authors. All rights reserved. | 1 // Copyright 2009 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 // Semaphore implementation exposed to Go. | 5 // Semaphore implementation exposed to Go. |
6 // Intended use is provide a sleep and wakeup | 6 // Intended use is provide a sleep and wakeup |
7 // primitive that can be used in the contended case | 7 // primitive that can be used in the contended case |
8 // of other synchronization primitives. | 8 // of other synchronization primitives. |
9 // Thus it targets the same goal as Linux's futex, | 9 // Thus it targets the same goal as Linux's futex, |
10 // but it has much simpler semantics. | 10 // but it has much simpler semantics. |
11 // | 11 // |
12 // That is, don't think of these as semaphores. | 12 // That is, don't think of these as semaphores. |
13 // Think of them as a way to implement sleep and wakeup | 13 // Think of them as a way to implement sleep and wakeup |
14 // such that every sleep is paired with a single wakeup, | 14 // such that every sleep is paired with a single wakeup, |
15 // even if, due to races, the wakeup happens before the sleep. | 15 // even if, due to races, the wakeup happens before the sleep. |
16 // | 16 // |
17 // See Mullender and Cox, ``Semaphores in Plan 9,'' | 17 // See Mullender and Cox, ``Semaphores in Plan 9,'' |
18 // http://swtch.com/semaphore.pdf | 18 // http://swtch.com/semaphore.pdf |
19 | 19 |
20 package sync | 20 package sync |
21 #include "runtime.h" | 21 #include "runtime.h" |
22 #include "arch_GOARCH.h" | 22 #include "arch_GOARCH.h" |
23 | 23 |
24 typedef struct Sema Sema; | 24 typedef struct SemaWaiter SemaWaiter; |
25 struct Sema | 25 struct SemaWaiter |
26 { | 26 { |
27 uint32 volatile* addr; | 27 uint32 volatile* addr; |
28 G* g; | 28 G* g; |
29 int64 releasetime; | 29 int64 releasetime; |
30 » Sema*» prev; | 30 » int32» nrelease;» // -1 for acquire |
31 » Sema*» next; | 31 » SemaWaiter*» prev; |
| 32 » SemaWaiter*» next; |
32 }; | 33 }; |
33 | 34 |
34 typedef struct SemaRoot SemaRoot; | 35 typedef struct SemaRoot SemaRoot; |
35 struct SemaRoot | 36 struct SemaRoot |
36 { | 37 { |
37 Lock; | 38 Lock; |
38 » Sema*» head; | 39 » SemaWaiter*» head; |
39 » Sema*» tail; | 40 » SemaWaiter*» tail; |
40 // Number of waiters. Read w/o the lock. | 41 // Number of waiters. Read w/o the lock. |
41 uint32 volatile nwait; | 42 uint32 volatile nwait; |
42 }; | 43 }; |
43 | 44 |
44 // Prime to not correlate with any user patterns. | 45 // Prime to not correlate with any user patterns. |
45 #define SEMTABLESZ 251 | 46 #define SEMTABLESZ 251 |
46 | 47 |
47 struct semtable | 48 struct semtable |
48 { | 49 { |
49 SemaRoot; | 50 SemaRoot; |
50 uint8 pad[CacheLineSize-sizeof(SemaRoot)]; | 51 uint8 pad[CacheLineSize-sizeof(SemaRoot)]; |
51 }; | 52 }; |
52 #pragma dataflag 16 /* mark semtable as 'no pointers', hiding from garbage colle
ctor */ | 53 #pragma dataflag 16 /* mark semtable as 'no pointers', hiding from garbage colle
ctor */ |
53 static struct semtable semtable[SEMTABLESZ]; | 54 static struct semtable semtable[SEMTABLESZ]; |
54 | 55 |
55 static SemaRoot* | 56 static SemaRoot* |
56 semroot(uint32 *addr) | 57 semroot(uint32 *addr) |
57 { | 58 { |
58 return &semtable[((uintptr)addr >> 3) % SEMTABLESZ]; | 59 return &semtable[((uintptr)addr >> 3) % SEMTABLESZ]; |
59 } | 60 } |
60 | 61 |
61 static void | 62 static void |
62 semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s) | 63 semqueue(SemaRoot *root, uint32 volatile *addr, SemaWaiter *s) |
63 { | 64 { |
64 s->g = g; | 65 s->g = g; |
65 s->addr = addr; | 66 s->addr = addr; |
66 s->next = nil; | 67 s->next = nil; |
67 s->prev = root->tail; | 68 s->prev = root->tail; |
68 if(root->tail) | 69 if(root->tail) |
69 root->tail->next = s; | 70 root->tail->next = s; |
70 else | 71 else |
71 root->head = s; | 72 root->head = s; |
72 root->tail = s; | 73 root->tail = s; |
73 } | 74 } |
74 | 75 |
75 static void | 76 static void |
76 semdequeue(SemaRoot *root, Sema *s) | 77 semdequeue(SemaRoot *root, SemaWaiter *s) |
77 { | 78 { |
78 if(s->next) | 79 if(s->next) |
79 s->next->prev = s->prev; | 80 s->next->prev = s->prev; |
80 else | 81 else |
81 root->tail = s->prev; | 82 root->tail = s->prev; |
82 if(s->prev) | 83 if(s->prev) |
83 s->prev->next = s->next; | 84 s->prev->next = s->next; |
84 else | 85 else |
85 root->head = s->next; | 86 root->head = s->next; |
86 s->prev = nil; | 87 s->prev = nil; |
87 s->next = nil; | 88 s->next = nil; |
88 } | 89 } |
89 | 90 |
90 static int32 | 91 static int32 |
91 cansemacquire(uint32 *addr) | 92 cansemacquire(uint32 *addr) |
92 { | 93 { |
93 uint32 v; | 94 uint32 v; |
94 | 95 |
95 while((v = runtime·atomicload(addr)) > 0) | 96 while((v = runtime·atomicload(addr)) > 0) |
96 if(runtime·cas(addr, v, v-1)) | 97 if(runtime·cas(addr, v, v-1)) |
97 return 1; | 98 return 1; |
98 return 0; | 99 return 0; |
99 } | 100 } |
100 | 101 |
101 static void | 102 void |
102 semacquireimpl(uint32 volatile *addr, int32 profile) | 103 runtime·semacquire(uint32 volatile *addr, bool profile) |
103 { | 104 { |
104 » Sema s;»// Needs to be allocated on stack, otherwise garbage collector c
ould deallocate it | 105 » SemaWaiter s;» // Needs to be allocated on stack, otherwise garbage col
lector could deallocate it |
105 SemaRoot *root; | 106 SemaRoot *root; |
106 int64 t0; | 107 int64 t0; |
107 ········ | 108 ········ |
108 // Easy case. | 109 // Easy case. |
109 if(cansemacquire(addr)) | 110 if(cansemacquire(addr)) |
110 return; | 111 return; |
111 | 112 |
112 // Harder case: | 113 // Harder case: |
113 // increment waiter count | 114 // increment waiter count |
114 // try cansemacquire one more time, return if succeeded | 115 // try cansemacquire one more time, return if succeeded |
(...skipping 23 matching lines...) Expand all Loading... |
138 runtime·park(runtime·unlock, root, "semacquire"); | 139 runtime·park(runtime·unlock, root, "semacquire"); |
139 if(cansemacquire(addr)) { | 140 if(cansemacquire(addr)) { |
140 if(t0) | 141 if(t0) |
141 runtime·blockevent(s.releasetime - t0, 3); | 142 runtime·blockevent(s.releasetime - t0, 3); |
142 return; | 143 return; |
143 } | 144 } |
144 } | 145 } |
145 } | 146 } |
146 | 147 |
147 void | 148 void |
148 runtime·semacquire(uint32 volatile *addr) | |
149 { | |
150 semacquireimpl(addr, 0); | |
151 } | |
152 | |
153 void | |
154 runtime·semrelease(uint32 volatile *addr) | 149 runtime·semrelease(uint32 volatile *addr) |
155 { | 150 { |
156 » Sema *s; | 151 » SemaWaiter *s; |
157 SemaRoot *root; | 152 SemaRoot *root; |
158 | 153 |
159 root = semroot(addr); | 154 root = semroot(addr); |
160 runtime·xadd(addr, 1); | 155 runtime·xadd(addr, 1); |
161 | 156 |
162 // Easy case: no waiters? | 157 // Easy case: no waiters? |
163 // This check must happen after the xadd, to avoid a missed wakeup | 158 // This check must happen after the xadd, to avoid a missed wakeup |
164 // (see loop in semacquire). | 159 // (see loop in semacquire). |
165 if(runtime·atomicload(&root->nwait) == 0) | 160 if(runtime·atomicload(&root->nwait) == 0) |
166 return; | 161 return; |
(...skipping 14 matching lines...) Expand all Loading... |
181 } | 176 } |
182 } | 177 } |
183 runtime·unlock(root); | 178 runtime·unlock(root); |
184 if(s) { | 179 if(s) { |
185 if(s->releasetime) | 180 if(s->releasetime) |
186 s->releasetime = runtime·cputicks(); | 181 s->releasetime = runtime·cputicks(); |
187 runtime·ready(s->g); | 182 runtime·ready(s->g); |
188 } | 183 } |
189 } | 184 } |
190 | 185 |
| 186 // TODO(dvyukov): move to netpoll.goc once it's used by all OSes. |
| 187 void net·runtime_Semacquire(uint32 *addr) |
| 188 { |
| 189 runtime·semacquire(addr, true); |
| 190 } |
| 191 |
| 192 void net·runtime_Semrelease(uint32 *addr) |
| 193 { |
| 194 runtime·semrelease(addr); |
| 195 } |
| 196 |
191 func runtime_Semacquire(addr *uint32) { | 197 func runtime_Semacquire(addr *uint32) { |
192 » semacquireimpl(addr, 1); | 198 » runtime·semacquire(addr, true); |
193 } | 199 } |
194 | 200 |
195 func runtime_Semrelease(addr *uint32) { | 201 func runtime_Semrelease(addr *uint32) { |
196 runtime·semrelease(addr); | 202 runtime·semrelease(addr); |
197 } | 203 } |
198 | 204 |
199 typedef struct SyncSema SyncSema; | 205 typedef struct SyncSema SyncSema; |
200 typedef struct SyncSemaWaiter SyncSemaWaiter; | |
201 | |
202 struct SyncSema | 206 struct SyncSema |
203 { | 207 { |
204 Lock; | 208 Lock; |
205 » SyncSemaWaiter*»head; | 209 » SemaWaiter*» head; |
206 » SyncSemaWaiter*»tail; | 210 » SemaWaiter*» tail; |
207 }; | 211 }; |
208 | 212 |
209 struct SyncSemaWaiter | 213 func runtime_Syncsemcheck(size uintptr) { |
210 { | 214 » if(size != sizeof(SyncSema)) { |
211 » G*» g; | 215 » » runtime·printf("bad SyncSema size: sync:%D runtime:%D\n", (int64
)size, (int64)sizeof(SyncSema)); |
212 » int32» nrelease;» // -1 for acquire | 216 » » runtime·throw("bad SyncSema size"); |
213 » int64» releasetime; | 217 » } |
214 » SyncSemaWaiter*»next; | 218 } |
215 }; | 219 |
216 | 220 // Syncsemacquire waits for a pairing Syncsemrelease on the same semaphore s. |
217 func runtime_Syncsemacquire(s *SyncSema) { | 221 func runtime_Syncsemacquire(s *SyncSema) { |
218 » SyncSemaWaiter w, *wake; | 222 » SemaWaiter w, *wake; |
219 int64 t0; | 223 int64 t0; |
220 | 224 |
221 w.g = g; | 225 w.g = g; |
222 w.nrelease = -1; | 226 w.nrelease = -1; |
223 w.next = nil; | 227 w.next = nil; |
224 w.releasetime = 0; | 228 w.releasetime = 0; |
225 t0 = 0; | 229 t0 = 0; |
226 if(runtime·blockprofilerate > 0) { | 230 if(runtime·blockprofilerate > 0) { |
227 t0 = runtime·cputicks(); | 231 t0 = runtime·cputicks(); |
228 w.releasetime = -1; | 232 w.releasetime = -1; |
(...skipping 19 matching lines...) Expand all Loading... |
248 s->head = &w; | 252 s->head = &w; |
249 else | 253 else |
250 s->tail->next = &w; | 254 s->tail->next = &w; |
251 s->tail = &w; | 255 s->tail = &w; |
252 runtime·park(runtime·unlock, s, "semacquire"); | 256 runtime·park(runtime·unlock, s, "semacquire"); |
253 if(t0) | 257 if(t0) |
254 runtime·blockevent(w.releasetime - t0, 2); | 258 runtime·blockevent(w.releasetime - t0, 2); |
255 } | 259 } |
256 } | 260 } |
257 | 261 |
| 262 // Syncsemrelease waits for n pairing Syncsemacquire on the same semaphore s. |
258 func runtime_Syncsemrelease(s *SyncSema, n uint32) { | 263 func runtime_Syncsemrelease(s *SyncSema, n uint32) { |
259 » SyncSemaWaiter w, *wake; | 264 » SemaWaiter w, *wake; |
260 | 265 |
261 w.g = g; | 266 w.g = g; |
262 w.nrelease = (int32)n; | 267 w.nrelease = (int32)n; |
263 w.next = nil; | 268 w.next = nil; |
264 w.releasetime = 0; | 269 w.releasetime = 0; |
265 | 270 |
266 runtime·lock(s); | 271 runtime·lock(s); |
267 while(w.nrelease > 0 && s->head && s->head->nrelease < 0) { | 272 while(w.nrelease > 0 && s->head && s->head->nrelease < 0) { |
268 // have pending acquire, satisfy it | 273 // have pending acquire, satisfy it |
269 wake = s->head; | 274 wake = s->head; |
270 s->head = wake->next; | 275 s->head = wake->next; |
271 if(s->head == nil) | 276 if(s->head == nil) |
272 s->tail = nil; | 277 s->tail = nil; |
273 if(wake->releasetime) | 278 if(wake->releasetime) |
274 wake->releasetime = runtime·cputicks(); | 279 wake->releasetime = runtime·cputicks(); |
275 runtime·ready(wake->g); | 280 runtime·ready(wake->g); |
276 w.nrelease--; | 281 w.nrelease--; |
277 } | 282 } |
278 if(w.nrelease > 0) { | 283 if(w.nrelease > 0) { |
279 // enqueue itself | 284 // enqueue itself |
280 if(s->tail == nil) | 285 if(s->tail == nil) |
281 s->head = &w; | 286 s->head = &w; |
282 else | 287 else |
283 s->tail->next = &w; | 288 s->tail->next = &w; |
284 s->tail = &w; | 289 s->tail = &w; |
285 runtime·park(runtime·unlock, s, "semarelease"); | 290 runtime·park(runtime·unlock, s, "semarelease"); |
286 } else | 291 } else |
287 runtime·unlock(s); | 292 runtime·unlock(s); |
288 } | 293 } |
LEFT | RIGHT |