Subversion Repositories openrisc

// 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 volatile *addr)
{
        return &semtable[((uintptr)addr >> 3) % SEMTABLESZ];
}

static void
semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s)
{
        s->g = runtime_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 volatile *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)
{
        G *g;
        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)
        g = runtime_g();
        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);
}