From bf3dd3f0efe5b45947a991e22660c62d4ce6b671 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Thu, 4 Dec 2008 12:51:36 -0800 Subject: [PATCH] add mutex.Mutex R=r DELTA=349 (348 added, 0 deleted, 1 changed) OCL=20380 CL=20472 --- src/cmd/gc/sys.go | 4 +- src/cmd/gc/sysimport.c | 2 + src/lib/Makefile | 2 + src/lib/sync/Makefile | 56 ++++++++++++ src/lib/sync/asm_amd64.s | 23 +++++ src/lib/sync/mutex.go | 39 ++++++++ src/lib/sync/mutex_test.go | 53 +++++++++++ src/run.bash | 6 ++ src/runtime/Makefile | 1 + src/runtime/sema.c | 178 +++++++++++++++++++++++++++++++++++++ 10 files changed, 363 insertions(+), 1 deletion(-) create mode 100644 src/lib/sync/Makefile create mode 100644 src/lib/sync/asm_amd64.s create mode 100644 src/lib/sync/mutex.go create mode 100644 src/lib/sync/mutex_test.go create mode 100644 src/runtime/sema.c diff --git a/src/cmd/gc/sys.go b/src/cmd/gc/sys.go index 1f34e0cd6c..775b83e51e 100644 --- a/src/cmd/gc/sys.go +++ b/src/cmd/gc/sys.go @@ -3,7 +3,7 @@ // license that can be found in the LICENSE file. -package SYS // rename to avoid redeclaration +package SYS // rename to avoid redeclaration errors export func mal(int32) *any; export func breakpoint(); @@ -92,3 +92,5 @@ export func exit(int); export func symdat() (symtab *[]byte, pclntab *[]byte); +export func semacquire(sema *int32); +export func semrelease(sema *int32); diff --git a/src/cmd/gc/sysimport.c b/src/cmd/gc/sysimport.c index ba09bb970e..3a3dbcedc0 100644 --- a/src/cmd/gc/sysimport.c +++ b/src/cmd/gc/sysimport.c @@ -71,5 +71,7 @@ char *sysimport = "export func sys.stringtorune (? string, ? int) (? int, ? int)\n" "export func sys.exit (? int)\n" "export func sys.symdat () (symtab *[]uint8, pclntab *[]uint8)\n" + "export func sys.semacquire (sema *int32)\n" + "export func sys.semrelease (sema *int32)\n" "\n" "$$\n"; diff --git a/src/lib/Makefile b/src/lib/Makefile index 7b685511ea..a50bdf0316 100644 --- a/src/lib/Makefile +++ b/src/lib/Makefile @@ -18,6 +18,7 @@ DIRS=\ reflect\ regexp\ strconv\ + sync\ tabwriter\ time\ @@ -95,4 +96,5 @@ reflect.dirinstall: strconv.dirinstall strconv.dirinstall: os.dirinstall utf8.install tabwriter.dirinstall: os.dirinstall io.dirinstall container/array.dirinstall time.dirinstall: once.install os.dirinstall +sync.dirinstall: diff --git a/src/lib/sync/Makefile b/src/lib/sync/Makefile new file mode 100644 index 0000000000..86aeeef8b1 --- /dev/null +++ b/src/lib/sync/Makefile @@ -0,0 +1,56 @@ +# 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. + +# DO NOT EDIT. Automatically generated by gobuild. +# gobuild -m >Makefile +O=6 +GC=$(O)g +CC=$(O)c -w +AS=$(O)a +AR=$(O)ar + +default: packages + +clean: + rm -f *.$O *.a $O.out + +test: packages + gotest + +coverage: packages + gotest + 6cov -g `pwd` | grep -v '_test\.go:' + +%.$O: %.go + $(GC) $*.go + +%.$O: %.c + $(CC) $*.c + +%.$O: %.s + $(AS) $*.s + +O1=\ + asm_$(GOARCH).$O\ + mutex.$O\ + +sync.a: a1 + +a1: $(O1) + $(AR) grc sync.a asm_$(GOARCH).$O mutex.$O + rm -f $(O1) + +newpkg: clean + $(AR) grc sync.a + +$(O1): newpkg + +nuke: clean + rm -f $(GOROOT)/pkg/sync.a + +packages: sync.a + +install: packages + cp sync.a $(GOROOT)/pkg/sync.a + diff --git a/src/lib/sync/asm_amd64.s b/src/lib/sync/asm_amd64.s new file mode 100644 index 0000000000..07389dd3b5 --- /dev/null +++ b/src/lib/sync/asm_amd64.s @@ -0,0 +1,23 @@ +// 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. + +// func cas(val *int32, old, new int32) bool +// Atomically: +// if *val == old { +// *val = new; +// return true; +// }else +// return false; +TEXT sync·cas(SB), 7, $0 + MOVQ 8(SP), BX + MOVL 16(SP), AX + MOVL 20(SP), CX + LOCK + CMPXCHGL CX, 0(BX) + JZ ok + MOVL $0, 24(SP) + RET +ok: + MOVL $1, 24(SP) + RET diff --git a/src/lib/sync/mutex.go b/src/lib/sync/mutex.go new file mode 100644 index 0000000000..accf55a76a --- /dev/null +++ b/src/lib/sync/mutex.go @@ -0,0 +1,39 @@ +// 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. + +package sync + +package func cas(val *int32, old, new int32) bool + +export type Mutex struct { + key int32; + sema int32; +} + +func xadd(val *int32, delta int32) (new int32) { + for { + v := *val; + if cas(val, v, v+delta) { + return v+delta; + } + } + panic("unreached") +} + +func (m *Mutex) Lock() { + if xadd(&m.key, 1) == 1 { + // changed from 0 to 1; we hold lock + return; + } + sys.semacquire(&m.sema); +} + +func (m *Mutex) Unlock() { + if xadd(&m.key, -1) == 0 { + // changed from 1 to 0; no contention + return; + } + sys.semrelease(&m.sema); +} + diff --git a/src/lib/sync/mutex_test.go b/src/lib/sync/mutex_test.go new file mode 100644 index 0000000000..7a6dd1814d --- /dev/null +++ b/src/lib/sync/mutex_test.go @@ -0,0 +1,53 @@ +// 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. + +// GOMAXPROCS=10 gotest + +package sync + +import ( + "sync"; + "testing" +) + +func HammerSemaphore(s *int32, cdone *chan bool) { + for i := 0; i < 1000; i++ { + sys.semacquire(s); + sys.semrelease(s); + } + cdone <- true; +} + +export func TestSemaphore(t *testing.T) { + s := new(int32); + *s = 1; + c := new(chan bool); + for i := 0; i < 10; i++ { + go HammerSemaphore(s, c); + } + for i := 0; i < 10; i++ { + <-c; + } +} + + +func HammerMutex(m *Mutex, cdone *chan bool) { + for i := 0; i < 1000; i++ { + m.Lock(); + m.Unlock(); + } + cdone <- true; +} + +export func TestMutex(t *testing.T) { + m := new(Mutex); + c := new(chan bool); + for i := 0; i < 10; i++ { + go HammerMutex(m, c); + } + for i := 0; i < 10; i++ { + <-c; + } +} + diff --git a/src/run.bash b/src/run.bash index 4bba1bf53b..64795b5e72 100755 --- a/src/run.bash +++ b/src/run.bash @@ -34,6 +34,12 @@ maketest \ (xcd lib; make test) || exit $? +(xcd lib/sync; +make clean; +time make +GOMAXPROCS=10 make test +) || exit $? + (xcd ../usr/gri/pretty make clean time make diff --git a/src/runtime/Makefile b/src/runtime/Makefile index da12c2ccb9..000c889030 100644 --- a/src/runtime/Makefile +++ b/src/runtime/Makefile @@ -25,6 +25,7 @@ LIBOFILES=\ print.$O\ rune.$O\ proc.$O\ + sema.$O\ stack.$O\ string.$O\ symtab.$O\ diff --git a/src/runtime/sema.c b/src/runtime/sema.c new file mode 100644 index 0000000000..117b0797a7 --- /dev/null +++ b/src/runtime/sema.c @@ -0,0 +1,178 @@ +// 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 + +#include "runtime.h" + +typedef struct Sema Sema; +struct Sema +{ + uint32 *addr; + G *g; + Sema *prev; + Sema *next; +}; + +// TODO: For now, a linked list; maybe a hash table of linked lists later. +static Sema *semfirst, *semlast; +static Lock semlock; + +static void +semqueue(uint32 *addr, Sema *s) +{ + s->addr = addr; + s->g = nil; + + lock(&semlock); + s->prev = semlast; + s->next = nil; + if(semlast) + semlast->next = s; + else + semfirst = s; + semlast = s; + unlock(&semlock); +} + +static void +semdequeue(Sema *s) +{ + lock(&semlock); + if(s->next) + s->next->prev = s->prev; + else + semlast = s->prev; + if(s->prev) + s->prev->next = s->next; + else + semfirst = s->next; + s->prev = nil; + s->next = nil; + unlock(&semlock); +} + +static void +semwakeup(uint32 *addr) +{ + Sema *s; + + lock(&semlock); + for(s=semfirst; s; s=s->next) { + if(s->addr == addr && s->g) { + ready(s->g); + s->g = nil; + break; + } + } + unlock(&semlock); +} + +// Step 1 of sleep: make ourselves available for wakeup. +// TODO(rsc): Maybe we can write a version without +// locks by using cas on s->g. Maybe not: I need to +// think more about whether it would be correct. +static void +semsleep1(Sema *s) +{ + lock(&semlock); + s->g = g; + unlock(&semlock); +} + +// Decided not to go through with it: undo step 1. +static void +semsleepundo1(Sema *s) +{ + lock(&semlock); + if(s->g != nil) { + s->g = nil; // back ourselves out + } else { + // If s->g == nil already, semwakeup + // already readied us. Since we never stopped + // running, readying us just set g->readyonstop. + // Clear it. + if(g->readyonstop == 0) + *(int32*)0x555 = 555; + g->readyonstop = 0; + } + unlock(&semlock); +} + +// Step 2: wait for the wakeup. +static void +semsleep2(Sema *s) +{ + USED(s); + g->status = Gwaiting; + sys·gosched(); +} + +static int32 +cansemacquire(uint32 *addr) +{ + uint32 v; + + while((v = *addr) > 0) + if(cas(addr, v, v-1)) + return 1; + return 0; +} + +// func sys.semacquire(addr *uint32) +// For now has no return value. +// Might return an ok (not interrupted) bool in the future? +void +sys·semacquire(uint32 *addr) +{ + Sema s; + + // Easy case. + if(cansemacquire(addr)) + return; + + // Harder case: + // queue + // try semacquire one more time, sleep if failed + // dequeue + // wake up one more guy to avoid races (TODO(rsc): maybe unnecessary?) + semqueue(addr, &s); + for(;;) { + semsleep1(&s); + if(cansemacquire(addr)) { + semsleepundo1(&s); + break; + } + semsleep2(&s); + } + semdequeue(&s); + semwakeup(addr); +} + +// func sys.semrelease(addr *uint32) +void +sys·semrelease(uint32 *addr) +{ + uint32 v; + + for(;;) { + v = *addr; + if(cas(addr, v, v+1)) + break; + } + semwakeup(addr); +} -- 2.48.1