LEFT | RIGHT |
(no file at all) | |
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 void | 102 void |
102 runtime·semacquire(uint32 volatile *addr, bool 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 25 matching lines...) Expand all Loading... |
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·semrelease(uint32 volatile *addr) | 149 runtime·semrelease(uint32 volatile *addr) |
149 { | 150 { |
150 » Sema *s; | 151 » SemaWaiter *s; |
151 SemaRoot *root; | 152 SemaRoot *root; |
152 | 153 |
153 root = semroot(addr); | 154 root = semroot(addr); |
154 runtime·xadd(addr, 1); | 155 runtime·xadd(addr, 1); |
155 | 156 |
156 // Easy case: no waiters? | 157 // Easy case: no waiters? |
157 // 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 |
158 // (see loop in semacquire). | 159 // (see loop in semacquire). |
159 if(runtime·atomicload(&root->nwait) == 0) | 160 if(runtime·atomicload(&root->nwait) == 0) |
160 return; | 161 return; |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
193 runtime·semrelease(addr); | 194 runtime·semrelease(addr); |
194 } | 195 } |
195 | 196 |
196 func runtime_Semacquire(addr *uint32) { | 197 func runtime_Semacquire(addr *uint32) { |
197 runtime·semacquire(addr, true); | 198 runtime·semacquire(addr, true); |
198 } | 199 } |
199 | 200 |
200 func runtime_Semrelease(addr *uint32) { | 201 func runtime_Semrelease(addr *uint32) { |
201 runtime·semrelease(addr); | 202 runtime·semrelease(addr); |
202 } | 203 } |
| 204 |
| 205 typedef struct SyncSema SyncSema; |
| 206 struct SyncSema |
| 207 { |
| 208 Lock; |
| 209 SemaWaiter* head; |
| 210 SemaWaiter* tail; |
| 211 }; |
| 212 |
| 213 func runtime_Syncsemcheck(size uintptr) { |
| 214 if(size != sizeof(SyncSema)) { |
| 215 runtime·printf("bad SyncSema size: sync:%D runtime:%D\n", (int64
)size, (int64)sizeof(SyncSema)); |
| 216 runtime·throw("bad SyncSema size"); |
| 217 } |
| 218 } |
| 219 |
| 220 // Syncsemacquire waits for a pairing Syncsemrelease on the same semaphore s. |
| 221 func runtime_Syncsemacquire(s *SyncSema) { |
| 222 SemaWaiter w, *wake; |
| 223 int64 t0; |
| 224 |
| 225 w.g = g; |
| 226 w.nrelease = -1; |
| 227 w.next = nil; |
| 228 w.releasetime = 0; |
| 229 t0 = 0; |
| 230 if(runtime·blockprofilerate > 0) { |
| 231 t0 = runtime·cputicks(); |
| 232 w.releasetime = -1; |
| 233 } |
| 234 |
| 235 runtime·lock(s); |
| 236 if(s->head && s->head->nrelease > 0) { |
| 237 // have pending release, consume it |
| 238 wake = nil; |
| 239 s->head->nrelease--; |
| 240 if(s->head->nrelease == 0) { |
| 241 wake = s->head; |
| 242 s->head = wake->next; |
| 243 if(s->head == nil) |
| 244 s->tail = nil; |
| 245 } |
| 246 runtime·unlock(s); |
| 247 if(wake) |
| 248 runtime·ready(wake->g); |
| 249 } else { |
| 250 // enqueue itself |
| 251 if(s->tail == nil) |
| 252 s->head = &w; |
| 253 else |
| 254 s->tail->next = &w; |
| 255 s->tail = &w; |
| 256 runtime·park(runtime·unlock, s, "semacquire"); |
| 257 if(t0) |
| 258 runtime·blockevent(w.releasetime - t0, 2); |
| 259 } |
| 260 } |
| 261 |
| 262 // Syncsemrelease waits for n pairing Syncsemacquire on the same semaphore s. |
| 263 func runtime_Syncsemrelease(s *SyncSema, n uint32) { |
| 264 SemaWaiter w, *wake; |
| 265 |
| 266 w.g = g; |
| 267 w.nrelease = (int32)n; |
| 268 w.next = nil; |
| 269 w.releasetime = 0; |
| 270 |
| 271 runtime·lock(s); |
| 272 while(w.nrelease > 0 && s->head && s->head->nrelease < 0) { |
| 273 // have pending acquire, satisfy it |
| 274 wake = s->head; |
| 275 s->head = wake->next; |
| 276 if(s->head == nil) |
| 277 s->tail = nil; |
| 278 if(wake->releasetime) |
| 279 wake->releasetime = runtime·cputicks(); |
| 280 runtime·ready(wake->g); |
| 281 w.nrelease--; |
| 282 } |
| 283 if(w.nrelease > 0) { |
| 284 // enqueue itself |
| 285 if(s->tail == nil) |
| 286 s->head = &w; |
| 287 else |
| 288 s->tail->next = &w; |
| 289 s->tail = &w; |
| 290 runtime·park(runtime·unlock, s, "semarelease"); |
| 291 } else |
| 292 runtime·unlock(s); |
| 293 } |
LEFT | RIGHT |