1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // Semaphore implementation exposed to Go.
6 // Intended use is provide a sleep and wakeup
7 // primitive that can be used in the contended case
8 // of other synchronization primitives.
9 // Thus it targets the same goal as Linux's futex,
10 // but it has much simpler semantics.
12 // That is, don't think of these as semaphores.
13 // Think of them as a way to implement sleep and wakeup
14 // such that every sleep is paired with a single wakeup,
15 // even if, due to races, the wakeup happens before the sleep.
17 // See Mullender and Cox, ``Semaphores in Plan 9,''
18 // http://swtch.com/semaphore.pdf
24 typedef struct SemaWaiter SemaWaiter;
27 uint32 volatile* addr;
30 int32 nrelease; // -1 for acquire
35 typedef struct SemaRoot SemaRoot;
41 // Number of waiters. Read w/o the lock.
42 uint32 volatile nwait;
45 // Prime to not correlate with any user patterns.
46 #define SEMTABLESZ 251
51 uint8 pad[CacheLineSize-sizeof(SemaRoot)];
53 static struct semtable semtable[SEMTABLESZ];
56 semroot(uint32 volatile *addr)
58 return &semtable[((uintptr)addr >> 3) % SEMTABLESZ];
62 semqueue(SemaRoot *root, uint32 volatile *addr, SemaWaiter *s)
76 semdequeue(SemaRoot *root, SemaWaiter *s)
79 s->next->prev = s->prev;
83 s->prev->next = s->next;
91 cansemacquire(uint32 volatile *addr)
95 while((v = runtime_atomicload(addr)) > 0)
96 if(runtime_cas(addr, v, v-1))
102 runtime_semacquire(uint32 volatile *addr, bool profile)
104 SemaWaiter s; // Needs to be allocated on stack, otherwise garbage collector could deallocate it
109 if(cansemacquire(addr))
113 // increment waiter count
114 // try cansemacquire one more time, return if succeeded
115 // enqueue itself as a waiter
117 // (waiter descriptor is dequeued by signaler)
118 root = semroot(addr);
121 if(profile && runtime_blockprofilerate > 0) {
122 t0 = runtime_cputicks();
128 // Add ourselves to nwait to disable "easy case" in semrelease.
129 runtime_xadd(&root->nwait, 1);
130 // Check cansemacquire to avoid missed wakeup.
131 if(cansemacquire(addr)) {
132 runtime_xadd(&root->nwait, -1);
133 runtime_unlock(root);
136 // Any semrelease after the cansemacquire knows we're waiting
137 // (we set nwait above), so go to sleep.
138 semqueue(root, addr, &s);
139 runtime_parkunlock(root, "semacquire");
140 if(cansemacquire(addr)) {
142 runtime_blockevent(s.releasetime - t0, 3);
149 runtime_semrelease(uint32 volatile *addr)
154 root = semroot(addr);
155 runtime_xadd(addr, 1);
157 // Easy case: no waiters?
158 // This check must happen after the xadd, to avoid a missed wakeup
159 // (see loop in semacquire).
160 if(runtime_atomicload(&root->nwait) == 0)
163 // Harder case: search for a waiter and wake it.
165 if(runtime_atomicload(&root->nwait) == 0) {
166 // The count is already consumed by another goroutine,
167 // so no need to wake up another goroutine.
168 runtime_unlock(root);
171 for(s = root->head; s; s = s->next) {
172 if(s->addr == addr) {
173 runtime_xadd(&root->nwait, -1);
178 runtime_unlock(root);
181 s->releasetime = runtime_cputicks();
186 // TODO(dvyukov): move to netpoll.goc once it's used by all OSes.
187 void net_runtime_Semacquire(uint32 *addr)
188 __asm__ (GOSYM_PREFIX "net.runtime_Semacquire");
190 void net_runtime_Semacquire(uint32 *addr)
192 runtime_semacquire(addr, true);
195 void net_runtime_Semrelease(uint32 *addr)
196 __asm__ (GOSYM_PREFIX "net.runtime_Semrelease");
198 void net_runtime_Semrelease(uint32 *addr)
200 runtime_semrelease(addr);
203 func runtime_Semacquire(addr *uint32) {
204 runtime_semacquire(addr, true);
207 func runtime_Semrelease(addr *uint32) {
208 runtime_semrelease(addr);
211 typedef struct SyncSema SyncSema;
219 func runtime_Syncsemcheck(size uintptr) {
220 if(size != sizeof(SyncSema)) {
221 runtime_printf("bad SyncSema size: sync:%D runtime:%D\n", (int64)size, (int64)sizeof(SyncSema));
222 runtime_throw("bad SyncSema size");
226 // Syncsemacquire waits for a pairing Syncsemrelease on the same semaphore s.
227 func runtime_Syncsemacquire(s *SyncSema) {
236 if(runtime_blockprofilerate > 0) {
237 t0 = runtime_cputicks();
242 if(s->head && s->head->nrelease > 0) {
243 // have pending release, consume it
246 if(s->head->nrelease == 0) {
248 s->head = wake->next;
254 runtime_ready(wake->g);
262 runtime_parkunlock(s, "semacquire");
264 runtime_blockevent(w.releasetime - t0, 2);
268 // Syncsemrelease waits for n pairing Syncsemacquire on the same semaphore s.
269 func runtime_Syncsemrelease(s *SyncSema, n uint32) {
273 w.nrelease = (int32)n;
278 while(w.nrelease > 0 && s->head && s->head->nrelease < 0) {
279 // have pending acquire, satisfy it
281 s->head = wake->next;
284 if(wake->releasetime)
285 wake->releasetime = runtime_cputicks();
286 runtime_ready(wake->g);
296 runtime_parkunlock(s, "semarelease");