synthetic time

[Petar Maymounkov]

Hi all,

I have been working on a fascinating, I think, problem

that pushes the limits of language and runtime, and

raises some interesting questions. These questions

have to do with implementing "synthetic time" and

its applications to real-time control (think robotics 

or Internet congestion control e.g.) algorithms.

First, and briefly: How this problem came to be.

I have been working on a user-space version of the IETF

congestion control protocol DCCP, authored by Eddie Kohler.

My project itself is found at github.com/petar/GoDCCP

At a high-level, the core functionality of this project is

the "control logic" whose job it is to listen for exeternal

network events (like reads) and create responses (like writes),

which (and this is the twist) are scheduled to be executed

at some future point in time.

In order to decouple the control logic from the details of 

networking and OS, the control logic is implemented as an

object (a struct, say, called ControlLogic) which interacts 

with the outside world through a narrow interface, which is 

passed to it upon initialization:

func NewControlLogic(world OutsideWorld) *ControlLogic { ... }

type OutsideWorld interface {

Sleep(nanoseconds int64)  // Block for the duration of nanoseconds

Now() (nanoseconds int64) // Tell me the time now

Read() (packet []byte)    // Block until a packet is available for reading

Write(packet []byte)      // Block until you can write this packet

}

ControlLogic itself has no public methods.

Internally, the control logic is allowed to use the 

facilities of the Go Language. In particular, it can

us the go-operator and it can create and manipulate channels.

However, it does not use any packages whatsoever.

The interesting problem arises, when we attempt to write 

tests for the control logic.

Our goal is to test the control logic as a black box. This means

we want to test whether it _responds_ as expected to its _input_.

Observe that the _input_ to the control logic is implicit in the

behavior of the OutsideWorld interface. There is no other point

of interaction with the outside world.

Furthermore, observe that the _response_ of the control logic is

implicit in what calls it makes to the methods of OutsideWorld

(and in what order and with what timing).

The obvious way to design a test is to implement OutsideWorld,

so that Now and Sleep simply invoke their respective functions

from the time package, while Read and Write can be implemented

to simulate whatever network blocking behavior we like.

This works. But there is an issue with it.

Typically, we would want to run a test that spans minutes

of real time, so that multiple corners of the ControlLogic

can be tested.

In a typical long-lasting execution of the ControlLogic,

most of the time is spend just waiting on Sleep or I/O

operations.

And here comes the crux:

We would like to design a testing environment which runs

instantaneously, while faithfully simulating a long-running 

test in real time. 

Intuitively, we would like to implement a "synthetic time"

version of OutsideWorld, where Sleeps return immediately,

while the Nows account for the passing of time correctly.

It turns out (and this is not hard to check), that we

can simplify the problem, by assuming that the interaction

with the outside world is given by this simpler interface:

type SimpleOutsideWorld interface {

Sleep(nanoseconds int64)

Now() (nanoseconds int64)

}

Is it possible to come up with an implementation SyntheticTime of 

SimpleOutsideWorld in a manner so that executing ControlLogic with

SyntheticTime as its argument is functionally equivalent to 

an execution where SimpleOutsideWorld is implemented by RealTime,

given below:

type RealTime struct {}

func (RealTime) Sleep(nanoseconds int64) { time.Sleep(time.Duration(nanoseconds)) }

func (RealTime) Now() int64 { return int64(time.Now()) }

So, to prove that this is not a hopeless problem, I am inclusing below

an implementation of SyntheticTime that does work, however it relies

on a non-existent (imaginary) function that would be provided by the

Go runtime. This function is called 

// YieldUntilAllOtherBlock blocks the execution of the current Go routine and

// yields to other goroutines. It returns when all other goroutines have blocked.

func YieldUntilAllOtherBlock()

With this imaginary function under our belt, we can implement SyntheticTime

and the implementation is shown below.

I do not think that a semantically correct implementation of SyntheticTime is 

possible in Go without circumventing the language in an unsafe manner, or 

without adding some additional interface into the runtime similar to

YieldUntilAllOtherBlock. 

Furthermore, even if you require that ControlLogic does not

call the go-operator directly, but rather goes through the outside world

interface:

type OutsideWorldWithGo interface {

Sleep(nanoseconds int64)

Now() (nanoseconds int64)

Go(f func())

}

SyntheticTime is still impossible. In fact, SyntheticTime is impossible

even if outside world captures the channel operations of ControlLogic as well.

If you prove me wrong, I will be amazed. The more likely outcome of this

discussion, I think, is that the runtime package of Go needs to include

some additional access to the underlying runtime.

PS: Note that runtime.Gosched() feels very similar to our imaginary

YieldUntilAllOtherBlock, but it does not carry the desired semantics

and does not work as a replacement for YieldUntilAllOtherBlock.

PSS: I am not suggesting that YieldUntilAllOtherBlock is the function that

should be added to the runtime package. For one, it is not clear what

its behavior should be if called from multiple goroutines.

This exposition is supposed to demonstrate that if we believe that

synthetic time is something we should be able to implement, than

_some_ addition has to made to the runtime package of Go.

__________________________________________________________________________

Here goes the code for SyntheticTime:

__________________________________________________________________________

type SyntheticTime struct {

reqch  chan interface{}

donech chan int

}

func NewSyntheticTime() *SyntheticTime {

s := &SyntheticTime{

reqch:  make(chan interface{}, 1),

donech: make(chan int),

}

go s.loop()

return s

}

type requestSleep struct {

duration int64

resp     chan int

}

type requestNow struct {

resp chan int64

}

type scheduledToSleep struct {

wake int64

resp chan int

}

func (x *SyntheticTime) loop() {

var now int64

var sleepers sleeperQueue

ForLoop:

for {

YieldUntilAllOtherBlock()

var req interface{}

select {

case req = <-x.reqch:

default:

}

if req != nil {

switch t := req.(type) {

case requestSleep:

sleepers.Add(&scheduledToSleep{ wake: now + t.duration, resp: t.resp })

case requestNow:

t.resp <- now

default:

panic("unknown request")

} 

continue ForLoop

}

nextToWake := sleepers.DeleteMin()

if nextToWake == nil {

break

}

now = nextToWake.wake

close(nextToWake.resp)

}

}

func (x *SyntheticTime) Sleep(nsec int64) {

resp := make(chan int)

x.reqch <- requestSleep{

duration: nsec,

resp:     resp,

}

<-resp

}

func (x *SyntheticTime) Now() int64 {

resp := make(chan int64)

x.reqch <- requestNow{

resp: resp,

}

return <-resp

}

// sleeperQueue sorts scheduledToSleep instances ascending by timestamp

type sleeperQueue []*scheduledToSleep

func (t sleeperQueue) Len() int {

return len(t)

}

func (t sleeperQueue) Less(i, j int) bool {

return t[i].wake < t[j].wake

}

func (t sleeperQueue) Swap(i, j int) {

t[i], t[j] = t[j], t[i]

}

func (t *sleeperQueue) Add(a *scheduledToSleep) {

*t = append(*t, a)

sort.Sort(t)

}

func (t *sleeperQueue) DeleteMin() *scheduledToSleep {

if len(*t) == 0 {

return nil

}

q := (*t)[0]

*t = (*t)[1:]

return q

}

[Sugu Sougoumarane]

If you'll be happy with just the loop functions yielding to each other, sync.Cond may do the job. Keep a counter for the total number of goroutines you've launched, and another counter for the number of goroutines that are yielding. If they become equal, you signal.

[Petar Maymounkov]

This idea does not work. And it is a fun exercise to figure out why.

I'm happy to explain if you don't want to think about it.

[Petar Maymounkov]

I'll actually give you a hint:

It is possible to have all goroutines blocked, but not all blocks are on Sleep().

Some blocks might be on a chan.

[Sugu Sougoumarane]

Yeah, it won't work if any of your functions blocked on other stuff. However, I think your particular case can still be made to work by using buffered channels (which you already are), adding explicit waits, and signaling any time you sent a message. I had to do similar tricks for a round robin resource pool for vitess.

I guess a global yield is still a very different thing, but I think it's a feature that could get misused. Personally, I prefer the clarity of waiting for specific things.

[Petar Maymounkov]

Yeah, I do believe that if I capture channel make/send/receive operations as well, then it can be done.

Perhaps, if the goal is not to encumber the developer of ControlLogic with having to use

specialized Go and Chan functions, one can achieve this with a source-to-source transform

of the ControlLogic code.

[Jonathan Wills]

If I understand your problem correctly then I think the SyntheticTime in the code below should suffice.  If it doesn't then I think I have misunderstood your problem.

package main

import (

  "fmt"

  "sync"

)

type SimpleOutsideWorld interface {

  Sleep(ns int64)

  Now() int64

}

type syntheticTimeHandle struct {

  t *SyntheticTime

}

func (s *syntheticTimeHandle) sleep(ns int64) {

  m := s.t.wait(s, ns)

  m.Lock()  // When this lock is available ns will have passed

}

type waiter struct {

  t int64

  m *sync.Mutex

}

type SyntheticTime struct {

  now int64

  now_chan chan int64

  update_chan chan int64

  // map from handle to a waiter which indicates when it should be woken, and

  // a mutex for waking it

  waiting map[*syntheticTimeHandle]waiter

}

func MakeSyntheticTime() *SyntheticTime {

  var s SyntheticTime

  s.now_chan = make(chan int64)

  s.update_chan = make(chan int64)

  s.waiting = make(map[*syntheticTimeHandle]waiter)

  go func() {

    var now int64

    for {

      select {

        case s.now_chan <- now:

        case now = <-s.update_chan:

      }

    }

  } ()

  return &s

}

func (s *SyntheticTime) GetHandle() *syntheticTimeHandle {

  return &syntheticTimeHandle{s}

}

func (s *SyntheticTime) wait(h *syntheticTimeHandle, ns int64) *sync.Mutex {

  var m sync.Mutex

  s.waiting[h] = waiter{s.now + ns, &m}

  m.Lock()

  return &m

}

func (s *SyntheticTime) Sleep(ns int64) {

  h := s.GetHandle()

  h.sleep(ns)

}

func (s *SyntheticTime) Now() int64 {

  return <-s.now_chan

}

// Increment now, then check for anyone sleeping that should be woken up.

// If there is anyone waiting, unlock their locks and remove them from the

// list of waiters.

func (s *SyntheticTime) IncrementTime(ns int64) {

  s.now += ns

  s.update_chan <- s.now

  var done []*syntheticTimeHandle

  for h, waiter := range s.waiting {

    if waiter.t <= s.now {

      waiter.m.Unlock()

      done = append(done, h)

    }

  }

  for _, h := range done {

    delete(s.waiting, h)

  }

}

func SleepThenDie(name string, sow SimpleOutsideWorld, ns int64) {

  fmt.Printf("%s: %d\n", name, sow.Now())

  sow.Sleep(ns)

  fmt.Printf("%s: %d\n", name, sow.Now())

  sow.Sleep(ns)

  fmt.Printf("%s: %d\n", name, sow.Now())

}

func main() {

  fmt.Printf("")

  t := MakeSyntheticTime()

  for i := 0; i < 10; i++ {

    go SleepThenDie(fmt.Sprintf("Routine #%d", i), t, 1000000000 + int64(i))

  }

  for i := 0; i < 3000; i++ {

    // fmt.Printf("Current time: %d\n", t.Now())

    t.IncrementTime(1000000)

  }

}

[Kyle Lemons]

The easy way is to not make a completely synthetic time, but make some accelerated time like 1000x real-time.  The problem with WaitUntilOthersBlock is that you shouldn't care about other concurrent processes other than the ones with which you communicate.

On Sat, Apr 28, 2012 at 11:39 AM, Petar Maymounkov <pet...@gmail.com> wrote:

[Russ Cox]

Yes, you do need YieldUntilAllOtherBlock.
That was the core of the p2psim implementation:

while(anyready())
yield();

Once that loop exits, its safe to move time forward
to the next interesting event (someone's Sleep ending).

I don't believe that you can implement this without
hacking the runtime package, and I think that's just fine.

Russ

[Andrew Wilkins]

On Tuesday, 1 May 2012 11:39:14 UTC+8, Russ Cox wrote:

I don't believe that you can implement this without
hacking the runtime package, and I think that's just fine.

Could you just have YieldUntilAllOtherBlock call LockOSThread,

and then wait until all other threads are in the S(leep) state? This

picks up blocking on channels, but won't help for racy things

like blocking I/O, which might unblock soon after you check the

state.

Something like this: https://gist.github.com/2565914

(state check should probably be != "S")

[Andrew Wilkins]

On Tuesday, 1 May 2012 15:29:50 UTC+8, Andrew Wilkins wrote:

Could you just have YieldUntilAllOtherBlock call LockOSThread,

and then wait until all other threads are in the S(leep) state? This

picks up blocking on channels, but won't help for racy things

like blocking I/O, which might unblock soon after you check the

state.

Something like this: https://gist.github.com/2565914

(state check should probably be != "S")

On second thought, this won't necessarily work for channels either.

A thread yet to be checked could easily wake a thread already

found to be sleeping. Perhaps you could do two passes, checking

context switches to see if they woke up and went back to sleep?

But I'd better not think about this any more until I get some sleep.

[Petar Maymounkov]

Thanks for all the good ideas here.

It seems that the two main alternatives are:
(a) changing the runtime a bit
(b) transforming the source of the program that needs to run in
synthetic time

So, I decided to go with (b). I am writing a source-to-source
transformer that slightly rewrites go, chan and time operations.

I will put the result up on github when ready.

[Joubin Houshyar]

On May 1, 8:34 am, Petar Maymounkov <pet...@gmail.com> wrote:
> Thanks for all the good ideas here.
>
> It seems that the two main alternatives are:
> (a) changing the runtime a bit

I think you misunderstood Russ's comment.

> (b) transforming the source of the program that needs to run in
> synthetic time

What will you be testing in that case?

It is arguably reasonable to collapse time for bb testing certain
categories of long running processes, but is that the case here?

[Russ Cox]

On Tue, May 1, 2012 at 8:34 AM, Petar Maymounkov <pet...@gmail.com> wrote:
> (a) changing the runtime a bit
> (b) transforming the source of the program that needs to run in
> synthetic time

For what it's worth, I think (a) is significantly easier than (b).
Here is a patch to runtime:


diff -r bcd5635a53b0 src/pkg/runtime/extern.go
--- a/src/pkg/runtime/extern.go Thu Apr 26 14:25:28 2012 -0400
+++ b/src/pkg/runtime/extern.go Tue May 01 22:18:21 2012 -0400
@@ -138,3 +138,5 @@
// GOARCH is the running program's architecture target:
// 386, amd64, or arm.
const GOARCH string = theGoarch
+
+func WaitIdle()
diff -r bcd5635a53b0 src/pkg/runtime/proc.c
--- a/src/pkg/runtime/proc.c Thu Apr 26 14:25:28 2012 -0400
+++ b/src/pkg/runtime/proc.c Tue May 01 22:18:21 2012 -0400
@@ -74,6 +74,8 @@
bool lockmain; // init called runtime.LockOSThread

Note stopped; // one g can set waitstop and wait here for m's to stop
+
+ G *idler;
};

// The atomic word in sched is an atomic uint32 that
@@ -613,6 +615,11 @@
if((scvg == nil && runtime·sched.grunning == 0) ||
(scvg != nil && runtime·sched.grunning == 1 && runtime·sched.gwait == 0 &&
(scvg->status == Grunning || scvg->status == Gsyscall))) {
+ if(runtime·sched.idler != nil) {
+ readylocked(runtime·sched.idler);
+ runtime·sched.idler = nil;
+ goto top;
+ }
runtime·throw("all goroutines are asleep - deadlock!");
}

@@ -1612,6 +1619,18 @@
runtime·gosched();
}

+void
+runtime·WaitIdle(void)
+{
+ schedlock();
+ if(runtime·sched.idler != nil)
+ runtime·throw("runtime: multiple goroutines using WaitIdle");
+ runtime·sched.idler = g;
+ g->status = Gwaiting;
+ schedunlock();
+ runtime·gosched();
+}
+
// Implementation of runtime.GOMAXPROCS.
// delete when scheduler is stronger
int32

and here is a program to test it:


package main

import "runtime"

func main() {
go idler()
go timer()

go fizz()
go buzz()

sleep(20)
}

func fizz() {
for t := 0; t < 100; t += 3 {
sleep(t)
println(t, "fizz")
}
}

func buzz() {
for t := 0; t < 100; t += 5 {
sleep(t)
println(t, "buzz")
}
}

var idle = make(chan bool)
var sleepc = make(chan request)

type request struct {
t int
c chan int
}

func sleep(t int) int {
c := make(chan int, 1)
sleepc <- request{t, c}
return <-c
}

func idler() {
for {
runtime.WaitIdle()
idle <- true
}
}

func timer() {
now := 0
var reqs []request
for {
select {
case <-idle:
min := -1
for _, req := range reqs {
if min < 0 || req.t < min {
min = req.t
}
}
if min < 0 {
panic("deadlock")
}
if min <= now {
panic("broken")
}
now = min
w := reqs[:0]
for _, req := range reqs {
if req.t <= now {
req.c <- now
} else {
w = append(w, req)
}
}
reqs = w

case req := <-sleepc:
if req.t <= now {
req.c <- now
break
}
reqs = append(reqs, req)
}
}
}

Russ

[Petar Maymounkov]

Oh, wow, thanks Russ. This is educational.

I'll chip in my solution a bit later when it's ready.