blob: 9f3f4a2b39fe35853a1a8d73aee7cfa899a7e73d [file] [log] [blame]
// 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"
#include "arch.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;
uint8 pad[CacheLineSize];
} 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;
g->waitreason = "semacquire";
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);
}