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 Sema Sema; |
25 struct Sema | 25 struct Sema |
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 Sema* prev; |
31 Sema* next; | 31 Sema* next; |
32 }; | 32 }; |
33 | 33 |
34 typedef struct SemaRoot SemaRoot; | 34 typedef struct SemaRoot SemaRoot; |
35 struct SemaRoot | 35 struct SemaRoot |
36 { | 36 { |
37 Lock; | 37 Lock; |
38 Sema* head; | 38 Sema* head; |
39 Sema* tail; | 39 Sema* tail; |
40 // Number of waiters. Read w/o the lock. | 40 // Number of waiters. Read w/o the lock. |
41 uint32 volatile nwait; | 41 uint32 volatile nwait; |
42 }; | 42 }; |
43 | 43 |
44 // Prime to not correlate with any user patterns. | 44 // Prime to not correlate with any user patterns. |
45 #define SEMTABLESZ 251 | 45 #define SEMTABLESZ 251 |
46 | 46 |
47 static union | 47 union semtable |
48 { | 48 { |
49 SemaRoot; | 49 SemaRoot; |
50 uint8 pad[CacheLineSize]; | 50 uint8 pad[CacheLineSize]; |
51 } semtable[SEMTABLESZ]; | 51 }; |
| 52 #pragma dataflag 16 /* mark semtable as 'no pointers', hiding from garbage colle
ctor */ |
| 53 static union semtable semtable[SEMTABLESZ]; |
52 | 54 |
53 static SemaRoot* | 55 static SemaRoot* |
54 semroot(uint32 *addr) | 56 semroot(uint32 *addr) |
55 { | 57 { |
56 return &semtable[((uintptr)addr >> 3) % SEMTABLESZ]; | 58 return &semtable[((uintptr)addr >> 3) % SEMTABLESZ]; |
57 } | 59 } |
58 | 60 |
59 static void | 61 static void |
60 semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s) | 62 semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s) |
61 { | 63 { |
(...skipping 30 matching lines...) Expand all Loading... |
92 | 94 |
93 while((v = runtime·atomicload(addr)) > 0) | 95 while((v = runtime·atomicload(addr)) > 0) |
94 if(runtime·cas(addr, v, v-1)) | 96 if(runtime·cas(addr, v, v-1)) |
95 return 1; | 97 return 1; |
96 return 0; | 98 return 0; |
97 } | 99 } |
98 | 100 |
99 static void | 101 static void |
100 semacquireimpl(uint32 volatile *addr, int32 profile) | 102 semacquireimpl(uint32 volatile *addr, int32 profile) |
101 { | 103 { |
102 » Sema s; | 104 » Sema s;»// Needs to be allocated on stack, otherwise garbage collector c
ould deallocate it |
103 SemaRoot *root; | 105 SemaRoot *root; |
104 int64 t0; | 106 int64 t0; |
105 ········ | 107 ········ |
106 // Easy case. | 108 // Easy case. |
107 if(cansemacquire(addr)) | 109 if(cansemacquire(addr)) |
108 return; | 110 return; |
109 | 111 |
110 // Harder case: | 112 // Harder case: |
111 // increment waiter count | 113 // increment waiter count |
112 // try cansemacquire one more time, return if succeeded | 114 // try cansemacquire one more time, return if succeeded |
113 // enqueue itself as a waiter | 115 // enqueue itself as a waiter |
114 // sleep | 116 // sleep |
115 // (waiter descriptor is dequeued by signaler) | 117 // (waiter descriptor is dequeued by signaler) |
116 root = semroot(addr); | 118 root = semroot(addr); |
117 t0 = 0; | 119 t0 = 0; |
118 s.releasetime = 0; | 120 s.releasetime = 0; |
119 » if(profile && runtime·ContentionProfileRate > 0) { | 121 » if(profile && runtime·blockprofilerate > 0) { |
120 t0 = runtime·cputicks(); | 122 t0 = runtime·cputicks(); |
121 s.releasetime = -1; | 123 s.releasetime = -1; |
122 } | 124 } |
123 for(;;) { | 125 for(;;) { |
124 runtime·lock(root); | 126 runtime·lock(root); |
125 // Add ourselves to nwait to disable "easy case" in semrelease. | 127 // Add ourselves to nwait to disable "easy case" in semrelease. |
126 runtime·xadd(&root->nwait, 1); | 128 runtime·xadd(&root->nwait, 1); |
127 // Check cansemacquire to avoid missed wakeup. | 129 // Check cansemacquire to avoid missed wakeup. |
128 if(cansemacquire(addr)) { | 130 if(cansemacquire(addr)) { |
129 runtime·xadd(&root->nwait, -1); | 131 runtime·xadd(&root->nwait, -1); |
130 runtime·unlock(root); | 132 runtime·unlock(root); |
131 return; | 133 return; |
132 } | 134 } |
133 // Any semrelease after the cansemacquire knows we're waiting | 135 // Any semrelease after the cansemacquire knows we're waiting |
134 // (we set nwait above), so go to sleep. | 136 // (we set nwait above), so go to sleep. |
135 semqueue(root, addr, &s); | 137 semqueue(root, addr, &s); |
136 » » g->status = Gwaiting; | 138 » » runtime·park(runtime·unlock, root, "semacquire"); |
137 » » g->waitreason = "semacquire"; | |
138 » » runtime·unlock(root); | |
139 » » runtime·gosched(); | |
140 if(cansemacquire(addr)) { | 139 if(cansemacquire(addr)) { |
141 if(t0) | 140 if(t0) |
142 » » » » runtime·contentionevent(s.releasetime - t0, 3); | 141 » » » » runtime·blockevent(s.releasetime - t0, 3); |
143 return; | 142 return; |
144 } | 143 } |
145 } | 144 } |
146 } | 145 } |
147 | 146 |
148 void | 147 void |
149 runtime·semacquire(uint32 volatile *addr) | 148 runtime·semacquire(uint32 volatile *addr) |
150 { | 149 { |
151 semacquireimpl(addr, 0); | 150 semacquireimpl(addr, 0); |
152 } | 151 } |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
189 } | 188 } |
190 } | 189 } |
191 | 190 |
192 func runtime_Semacquire(addr *uint32) { | 191 func runtime_Semacquire(addr *uint32) { |
193 semacquireimpl(addr, 1); | 192 semacquireimpl(addr, 1); |
194 } | 193 } |
195 | 194 |
196 func runtime_Semrelease(addr *uint32) { | 195 func runtime_Semrelease(addr *uint32) { |
197 runtime·semrelease(addr); | 196 runtime·semrelease(addr); |
198 } | 197 } |
LEFT | RIGHT |