Language support for use of critical sections?

[Lars Pensjö]

It was some time I followed the Go development, so I might be out of sync.

Go has the excellent adage to share by communication instead of communicate by sharing. That is, using a channel as a mechanism to implement critical sections. With the case of single writer and multiple readers, this is less efficient. There are the mutex package that will support the classical solution for that.

For a considerable time, I have been playing around with a game server for a MMORPG, with the intent to support 10000+ simultaneous players on the same server. I found Go and the use of goroutines to be a very good tool, and had a thoroughly enjoyable experience. Even though GC is problematic in hard real time, tests indicates that timing is good enough for my game. This is a typical example of one writer (a goroutine for every player) and many readers (goroutines for other players and processes), as well as several critical data sections.

As I had several critical data sections, I got into some troubles regarding the use of locks. If I wasn't careful, I could get a dead-lock. One solution is to never have more than one lock, but that wasn't possible in my case. My solution was to acquire locks in a certain order, which prevents dead-locks. However, the game server was big and complex, and somewhat lacking on overall design (stemming from the classical growth pain problems). To get around that, I used a naming conventions on all functions, based on what locks they might acquire. An example is ProcSpawnMonsters_WLwWLuWLqWLmBlWLc, which is a function that can acquire 6 different locks in worst case, using the syntax "WLx" and "RLx" to indicate a write lock or read lock on critical area 'x'.

So I ended up with a manual control system to prevent dead-locking. I suppose it would also be possible to add some kind of run-time checks. However, I started to think that this all could have been supported by the language itself. The compiler would generate an error if a situation could arise that leads to a dead-lock? I think the transition to massively parallel algorithms is accelerating, and so such a support would be nice.

Is this a feasible idea?

One trigger for the idea is how "const" works in C++. If you call a const member function, it can only call other const member-functions. So you get compiler support to force you to stay in line.

The language could then support

• setting priorities to critical sections
  
• automatically set and release locks
• deny access of data that is not locked properly
• automatic use of atomic operations instead of mutexes, where possible

[Dmitry Vyukov]

I don't deadlock prevention is possible during compilation, because of
all the problems with alias analysis, control flow analysis, etc.

However, reasonably good deadlock detection is possible at runtime. At
least for mutexes.

I am just working on such a prototype.
Please describe the types of deadlocks that you had encountered. Was
it typical lock order inversions? Did they involved only mutexes or
other primitives as well (chans, waitgroups, etc)?

[egon]

On Friday, February 28, 2014 8:33:01 AM UTC+2, Lars Pensjö wrote:

It was some time I followed the Go development, so I might be out of sync.

Go has the excellent adage to share by communication instead of communicate by sharing. That is, using a channel as a mechanism to implement critical sections. With the case of single writer and multiple readers, this is less efficient. There are the mutex package that will support the classical solution for that.

For a considerable time, I have been playing around with a game server for a MMORPG, with the intent to support 10000+ simultaneous players on the same server. I found Go and the use of goroutines to be a very good tool, and had a thoroughly enjoyable experience. Even though GC is problematic in hard real time, tests indicates that timing is good enough for my game. This is a typical example of one writer (a goroutine for every player) and many readers (goroutines for other players and processes), as well as several critical data sections.

As I had several critical data sections, I got into some troubles regarding the use of locks. If I wasn't careful, I could get a dead-lock. One solution is to never have more than one lock, but that wasn't possible in my case. My solution was to acquire locks in a certain order, which prevents dead-locks. However, the game server was big and complex, and somewhat lacking on overall design (stemming from the classical growth pain problems). To get around that, I used a naming conventions on all functions, based on what locks they might acquire. An example is ProcSpawnMonsters_WLwWLuWLqWLmBlWLc, which is a function that can acquire 6 different locks in worst case, using the syntax "WLx" and "RLx" to indicate a write lock or read lock on critical area 'x'.

I guess the better solution is to try and get rid of the shared state as much as possible.

For those kinds of things I start with two basic principles, 1. as much as possible should be possible to move to different computers, 2. assume that each computer can fail. This ensures that you have as little state sharing as possible and you get scaling for free.

The basic idea could be something like: http://play.golang.org/p/exCd3o2amJ

Of course, when you have multiple different world locations (that can't interact) you can use different goroutines and split the world state... i.e. possibly simulating two different parts of the world on different computers.

+ egon

[Nate Finch]

I have some code for a MUD I was hacking up for the fun of it.  The way I got around the same problem was to give every object in the game a unique ID (an int64), and then when you need to lock the objects, just do so in ID order.  

I don't actually understand how naming of functions with the locks they use is helping you (and it's certainly hurting you... damn).  

As Dmitry said, doing static deadlock checking seems impossible, or at least so incredibly hard that it's not worth trying.

[Lars Pensjö]

Lock order inversions combined with blocking I/O operations (file access, socket operations).

On Friday, 28 February 2014 09:48:46 UTC+1, egon wrote:

I guess the better solution is to try and get rid of the shared state as much as possible.

The game main design is to allow many players in the same world, not using instances, which makes this harder. However, I use Quadtree to minimize cross dependencies.

 On Friday, 28 February 2014 13:01:54 UTC+1, Nate Finch wrote:

I don't actually understand how naming of functions with the locks they use is helping you (and it's certainly hurting you... damn).  

 

Calling a function named with any mutex lock information "taints" the caller, forcing it to be named likewise. As long as I follow this principle, I can see immediately from the function name if calling it could lead to dead locks.

 

As Dmitry said, doing static deadlock checking seems impossible, or at least so incredibly hard that it's not worth trying.

 

Yes, I see. However, the language could still help me with the "taint analysis". Possibly, this could be done as a separate tool, instead of extended the language to support it?

[minux]

On Sat, Mar 1, 2014 at 12:56 AM, Lars Pensjö <lars....@gmail.com> wrote:

As Dmitry said, doing static deadlock checking seems impossible, or at least so incredibly hard that it's not worth trying.

 

Yes, I see. However, the language could still help me with the "taint analysis". Possibly, this could be done as a separate tool, instead of extended the language to support it?

Yeah, with go/* packages and go.tools/go/types, it seems not very difficult to develop your own

golint that enforces your naming rules (maybe even check the lock order matches the name,

and so on)