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. |
(...skipping 18 matching lines...) Expand all Loading... |
29 Sema *next; | 29 Sema *next; |
30 }; | 30 }; |
31 | 31 |
32 typedef struct SemaRoot SemaRoot; | 32 typedef struct SemaRoot SemaRoot; |
33 struct SemaRoot | 33 struct SemaRoot |
34 { | 34 { |
35 Lock; | 35 Lock; |
36 Sema *head; | 36 Sema *head; |
37 Sema *tail; | 37 Sema *tail; |
38 // Number of waiters. Read w/o the lock. | 38 // Number of waiters. Read w/o the lock. |
39 » uint32 volatile cnt; | 39 » uint32 volatile nwait; |
40 }; | 40 }; |
41 | 41 |
42 // Prime to not correlate with any user patterns. | 42 // Prime to not correlate with any user patterns. |
43 #define SEMTABLESZ 251 | 43 #define SEMTABLESZ 251 |
44 | 44 |
45 static union | 45 static union |
46 { | 46 { |
47 SemaRoot; | 47 SemaRoot; |
48 // Modern processors tend to have 64-byte cache lines, | 48 // Modern processors tend to have 64-byte cache lines, |
49 // potentially with 128-byte effective cache line size for reading. | 49 // potentially with 128-byte effective cache line size for reading. |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
85 root->head = s->next; | 85 root->head = s->next; |
86 s->prev = nil; | 86 s->prev = nil; |
87 s->next = nil; | 87 s->next = nil; |
88 } | 88 } |
89 | 89 |
90 static int32 | 90 static int32 |
91 cansemacquire(uint32 *addr) | 91 cansemacquire(uint32 *addr) |
92 { | 92 { |
93 uint32 v; | 93 uint32 v; |
94 | 94 |
95 » while((v = *addr) > 0) | 95 » while((v = runtime·atomicload(addr)) > 0) |
96 if(runtime·cas(addr, v, v-1)) | 96 if(runtime·cas(addr, v, v-1)) |
97 return 1; | 97 return 1; |
98 return 0; | 98 return 0; |
99 } | 99 } |
100 | 100 |
101 void | 101 void |
102 runtime·semacquire(uint32 volatile *addr) | 102 runtime·semacquire(uint32 volatile *addr) |
103 { | 103 { |
104 Sema s; | 104 Sema s; |
105 SemaRoot *root; | 105 SemaRoot *root; |
106 | 106 |
107 // Easy case. | 107 // Easy case. |
108 if(cansemacquire(addr)) | 108 if(cansemacquire(addr)) |
109 return; | 109 return; |
110 | 110 |
111 // Harder case: | 111 // Harder case: |
112 // increment waiter count | 112 // increment waiter count |
113 // try cansemacquire one more time, return if succeeded | 113 // try cansemacquire one more time, return if succeeded |
114 // enqueue itself as a waiter | 114 // enqueue itself as a waiter |
115 // sleep | 115 // sleep |
116 // (waiter descriptor is dequeued by signaler) | 116 // (waiter descriptor is dequeued by signaler) |
117 root = semroot(addr); | 117 root = semroot(addr); |
118 for(;;) { | 118 for(;;) { |
119 runtime·lock(root); | 119 runtime·lock(root); |
120 » » runtime·xadd(&root->cnt, 1); | 120 » » // Add ourselves to nwait to disable "easy case" in semrelease. |
| 121 » » runtime·xadd(&root->nwait, 1); |
| 122 » » // Check cansemacquire to avoid missed wakeup. |
121 if(cansemacquire(addr)) { | 123 if(cansemacquire(addr)) { |
| 124 runtime·xadd(&root->nwait, -1); |
122 runtime·unlock(root); | 125 runtime·unlock(root); |
123 runtime·xadd(&root->cnt, -1); | |
124 return; | 126 return; |
125 } | 127 } |
| 128 // Any semrelease after the cansemacquire knows we're waiting |
| 129 // (we set nwait above), so go to sleep. |
126 semqueue(root, addr, &s); | 130 semqueue(root, addr, &s); |
127 g->status = Gwaiting; | 131 g->status = Gwaiting; |
128 runtime·unlock(root); | 132 runtime·unlock(root); |
129 runtime·gosched(); | 133 runtime·gosched(); |
130 if(cansemacquire(addr)) | 134 if(cansemacquire(addr)) |
131 return; | 135 return; |
132 } | 136 } |
133 } | 137 } |
134 | 138 |
135 void | 139 void |
136 runtime·semrelease(uint32 volatile *addr) | 140 runtime·semrelease(uint32 volatile *addr) |
137 { | 141 { |
138 Sema *s; | 142 Sema *s; |
139 SemaRoot *root; | 143 SemaRoot *root; |
140 | 144 |
141 // Easy case: no waiters? | |
142 root = semroot(addr); | 145 root = semroot(addr); |
143 runtime·xadd(addr, 1); | 146 runtime·xadd(addr, 1); |
144 » if(runtime·atomicload(&root->cnt) == 0) | 147 |
| 148 » // Easy case: no waiters? |
| 149 » // This check must happen after the xadd, to avoid a missed wakeup |
| 150 » // (see loop in semacquire). |
| 151 » if(runtime·atomicload(&root->nwait) == 0) |
145 return; | 152 return; |
146 | 153 |
147 // Harder case: search for a waiter and wake it. | 154 // Harder case: search for a waiter and wake it. |
148 runtime·lock(root); | 155 runtime·lock(root); |
| 156 if(runtime·atomicload(&root->nwait) == 0) { |
| 157 // The count is already consumed by another goroutine, |
| 158 // so no need to wake up another goroutine. |
| 159 runtime·unlock(root); |
| 160 return; |
| 161 } |
149 for(s = root->head; s; s = s->next) { | 162 for(s = root->head; s; s = s->next) { |
150 if(s->addr == addr) { | 163 if(s->addr == addr) { |
151 » » » // The count is already consumed by another goroutine, | 164 » » » runtime·xadd(&root->nwait, -1); |
152 » » » // so no need to wake up another goroutine. | 165 » » » semdequeue(root, s); |
153 » » » if(runtime·atomicload(&root->cnt) == 0) | |
154 » » » » s = nil; | |
155 » » » else | |
156 » » » » semdequeue(root, s); | |
157 break; | 166 break; |
158 } | 167 } |
159 } | 168 } |
160 runtime·unlock(root); | 169 runtime·unlock(root); |
161 » if(s) { | 170 » if(s) |
162 » » runtime·xadd(&root->cnt, -1); | |
163 runtime·ready(s->g); | 171 runtime·ready(s->g); |
164 } | |
165 } | 172 } |
166 | 173 |
167 func Semacquire(addr *uint32) { | 174 func Semacquire(addr *uint32) { |
168 runtime·semacquire(addr); | 175 runtime·semacquire(addr); |
169 } | 176 } |
170 | 177 |
171 func Semrelease(addr *uint32) { | 178 func Semrelease(addr *uint32) { |
172 runtime·semrelease(addr); | 179 runtime·semrelease(addr); |
173 } | 180 } |
LEFT | RIGHT |