// 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);
}