diff options
Diffstat (limited to 'src/pkg/runtime/sema.goc')
| -rw-r--r-- | src/pkg/runtime/sema.goc | 180 |
1 files changed, 180 insertions, 0 deletions
diff --git a/src/pkg/runtime/sema.goc b/src/pkg/runtime/sema.goc new file mode 100644 index 000000000..ae84351ed --- /dev/null +++ b/src/pkg/runtime/sema.goc @@ -0,0 +1,180 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Semaphore implementation exposed to Go. +// Intended use is provide a sleep and wakeup +// primitive that can be used in the contended case +// of other synchronization primitives. +// Thus it targets the same goal as Linux's futex, +// but it has much simpler semantics. +// +// That is, don't think of these as semaphores. +// Think of them as a way to implement sleep and wakeup +// such that every sleep is paired with a single wakeup, +// even if, due to races, the wakeup happens before the sleep. +// +// See Mullender and Cox, ``Semaphores in Plan 9,'' +// http://swtch.com/semaphore.pdf + +package runtime +#include "runtime.h" + +typedef struct Sema Sema; +struct Sema +{ + uint32 volatile *addr; + G *g; + Sema *prev; + Sema *next; +}; + +typedef struct SemaRoot SemaRoot; +struct SemaRoot +{ + Lock; + Sema *head; + Sema *tail; + // Number of waiters. Read w/o the lock. + uint32 volatile nwait; +}; + +// Prime to not correlate with any user patterns. +#define SEMTABLESZ 251 + +static union +{ + SemaRoot; + // Modern processors tend to have 64-byte cache lines, + // potentially with 128-byte effective cache line size for reading. + // While there are hypothetical architectures + // with 16-4096 byte cache lines, 128 looks like a good compromise. + uint8 pad[128]; +} semtable[SEMTABLESZ]; + +static SemaRoot* +semroot(uint32 *addr) +{ + return &semtable[((uintptr)addr >> 3) % SEMTABLESZ]; +} + +static void +semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s) +{ + s->g = g; + s->addr = addr; + s->next = nil; + s->prev = root->tail; + if(root->tail) + root->tail->next = s; + else + root->head = s; + root->tail = s; +} + +static void +semdequeue(SemaRoot *root, Sema *s) +{ + if(s->next) + s->next->prev = s->prev; + else + root->tail = s->prev; + if(s->prev) + s->prev->next = s->next; + else + root->head = s->next; + s->prev = nil; + s->next = nil; +} + +static int32 +cansemacquire(uint32 *addr) +{ + uint32 v; + + while((v = runtime·atomicload(addr)) > 0) + if(runtime·cas(addr, v, v-1)) + return 1; + return 0; +} + +void +runtime·semacquire(uint32 volatile *addr) +{ + Sema s; + SemaRoot *root; + + // Easy case. + if(cansemacquire(addr)) + return; + + // Harder case: + // increment waiter count + // try cansemacquire one more time, return if succeeded + // enqueue itself as a waiter + // sleep + // (waiter descriptor is dequeued by signaler) + root = semroot(addr); + for(;;) { + runtime·lock(root); + // Add ourselves to nwait to disable "easy case" in semrelease. + runtime·xadd(&root->nwait, 1); + // Check cansemacquire to avoid missed wakeup. + if(cansemacquire(addr)) { + runtime·xadd(&root->nwait, -1); + runtime·unlock(root); + return; + } + // Any semrelease after the cansemacquire knows we're waiting + // (we set nwait above), so go to sleep. + semqueue(root, addr, &s); + g->status = Gwaiting; + runtime·unlock(root); + runtime·gosched(); + if(cansemacquire(addr)) + return; + } +} + +void +runtime·semrelease(uint32 volatile *addr) +{ + Sema *s; + SemaRoot *root; + + root = semroot(addr); + runtime·xadd(addr, 1); + + // Easy case: no waiters? + // This check must happen after the xadd, to avoid a missed wakeup + // (see loop in semacquire). + if(runtime·atomicload(&root->nwait) == 0) + return; + + // Harder case: search for a waiter and wake it. + runtime·lock(root); + if(runtime·atomicload(&root->nwait) == 0) { + // The count is already consumed by another goroutine, + // so no need to wake up another goroutine. + runtime·unlock(root); + return; + } + for(s = root->head; s; s = s->next) { + if(s->addr == addr) { + runtime·xadd(&root->nwait, -1); + semdequeue(root, s); + break; + } + } + runtime·unlock(root); + if(s) + runtime·ready(s->g); +} + +func Semacquire(addr *uint32) { + runtime·semacquire(addr); +} + +func Semrelease(addr *uint32) { + runtime·semrelease(addr); +} |