gSuneido Roller Coaster

One of the questions with the Go version of Suneido (gSuneido) was the Windows UI interface. In the long run I'm hoping to switch to a browser based front end, but that's a long term project and I would like to replace cSuneido sooner than that. One option is to implement cSuneido's general purpose DLL interface. But this involved some ugly low level code (even some assembler) that I didn't really want to port. Another option was to use Go's syscall facilities to write the specific Win32 functions that we needed. I did a quick check on how many functions we needed to open the IDE. It was about 100. I knew the final number would be higher, but it seemed reasonable to hand write that many. One advantage of doing this is that it moved the "unsafe" code from Suneido to Go, which seemed safer.

Of course, it took much longer than I expected to write (and debug) the interface functions. There were about 300 in the end. (It's not just the functions, it's converting to and from all the structs involved as well.) I definitely had a few doubts whether this was the right approach. In retrospect, I'm pretty sure I could have ported the general purpose interface in less time. It was also a bit depressing knowing that if/when we got the browser interface finished, then this code would all be thrown out. If I was to do it again, I might write a tool that would take the cSuneido definitions and generate Go language definitions.

But finally I got near to complete and I could actually run the Suneido GUI. That felt pretty good.

Except there were intermittent crashes. I didn't worry about it too much at first. This kind of low level unsafe code can easily crash if you have bugs. But even after I cleaned up the majority of the bugs, it was still crashing. It worked most of the time, so I didn't think it was blatant errors in the code. I spent days trying to track it down. Of course, like many elusive bugs, it almost never crashed in the debugger.

My first thought was something related to garbage collection. But disabling garbage collection didn't help.

Another possibility was stack movement. Because Go supports high numbers of goroutines, they start out with relatively small stacks, which grow as necessary. This is a tricky process because you have local variables on the stack, and pointers between them, all of which have to be adjusted when the stack is moved. I couldn't figure out how to debug this. There was no way to turn it off, and no way to trace when it happened. I tried to detect it by storing the address of a stack value in an integer where it wouldn't get adjusted. But this didn't seem to work and I never did figure out why. (Part of the problem is that unlike C(++), in Go you don't control whether things are on the stack or the heap. That's all handled automatically by the compiler. It's quite possible that my value was ending on the heap and therefore useless for detecting stack movement.)

Needless to say, this was another low point. For starters, all that work for nothing - it was useless if it crashed randomly. And secondly, what now? If I couldn't reliably interface with the Windows GUI from Go, then the only other option I could see was to write the GUI interface in a separate C(++) program and use some kind of interprocess communication. Presumably that would work, but it would be ugly.

It might seem odd that something so objective and abstract would involve so much emotion like elation and depression. But software development (at least so far) is a human activity, and human are nothing if not subjective and emotional.

One thing that puzzled me was that I knew there were several other Go projects that interfaced with the Windows GUI. (Like https://github.com/lxn/win and walk) Why didn't they have this problem? I started searching and soon found this issue:

don't use Go heap for MSG
It's not entirely clear to me what's going on here, and I'm only
half-certain that this fixes the issue, due to it being somewhat hard to
reproduce ... While this might point to deeper Go runtime issues, we
just work around this here by allocating the variable using GlobalAlloc.
At the very least, I haven't been able to reproduce the bug after
applying this patch.

Following the links and looking at the related issues it sounded very much like what I was seeing. I applied their fix/workaround and sure enough the crashes went away, accompanied by feelings of relief and joy.

Part of the problem/complexity is that the way the Windows GUI works, there are nested callbacks and DLL/sycalls. i.e. Windows calls application code which calls Windows code which calls application code, and so on. On top of that, Go syscalls and callbacks do a complicated dance to switch between Go stacks and syscall stacks, and attempt to protect non-Go code from garbage collection and stack movement. It's not at all surprising that there would be ugly corner cases.

Well, my happiness lasted all of a day before I had another crash. Hmmm... was that the old problem still there, or something else? I crossed my fingers that it was something unrelated. There's a fine line between wishful thinking and having a positive attitude. Sadly, the crashes kept happening and it became obvious the problem wasn't solved.

But the lxn/walk issue had seemed so similar. And the fix had certainly reduced the number of crashes. If the issue was passing pointers to stack values, then I was doing this in a lot more places than just the message loop MSG. Whereas the lxn win/walk code always took the pointers as arguments rather than declaring them locally. (Of course, I didn't figure this out quite as step by step as it sounds. There was a lot of frowning and frustration first. )

I tried changing a few of the common crash sites to avoid anything Go might put on the stack. That reduced crashes even further. Of course, once the crashes get rare, it becomes very difficult to know whether you've fixed anything or not. It always seems to work at first. Just when you're ready to declare success, then it crashes again.

It seemed like I was on the right track, so I took the plunge and changed all the functions to allocate temporary values on my own "heap/stack". This was a bit of a gamble since it was a lot of changes (several days work) with no guarantee it would help.

But the gamble seemed to pay off. No more crashes! I was a happy camper.

I soon had more or less the whole IDE working. There were numerous little glitches but they were mostly easy to fix. Until one glitch that was more problematic. I happened to try dragging some text within an editor window, and it didn't work. At first I thought the drop was failing since the text didn't appear at the destination. But I soon realized it was getting inserted at the very beginning or end of the text, instead of where I was trying to drop it. I couldn't remember how drag and drop worked so I had to do a little digging. At this point I was still assuming it was just some minor error in one of the functions. But it wasn't anything obvious. I narrowed it down to a couple of notification callbacks (EN_CHANGE or SCEN_MODIFIED). If those callbacks did anything significant then the drop would go to the wrong place. It didn't seem to matter what they did. I never did narrow it down to whether it was call stack or heap usage.

The problem was, this was a bit of a dead end. Inserting seemingly harmless, irrelevant code in between Windows and Scintilla (the editor control) caused drag and drop to fail. I looked at the Scintilla code but it didn't seem to be doing anything unusual or suspicious.

I spent another couple of days on this issue until I admitted defeat. Again, there seemed to be something going wrong in the depths of Go's complex syscall / concurrent garbage collection / stack movement. In theory I should submit a Go bug report. But, understandably, they'd want a small example that consistently reproduced the problem. And I don't have anything close to that. I have a large system that crashes rarely.

Another low point. Now what? Such a small symptom, but there's no such thing as minor corruption, it's a bit like a little bit pregnant.

Back to my previous idea of a separate GUI process written in C. Probably the fastest interprocess communication would be shared memory. But you'd still need some kind of synchronization. It still seemed ugly.

Did I really need a separate process? I want some isolation, but maybe I can do that within a single process. Go has a facility for incorporating C code in your Go program (Cgo). What if the C GUI code ran in a separate OS thread, but still within the same process? That would separate the Windows GUI code from all the Go issues of concurrent garbage collection and stack movement. But you wouldn't have the overhead and complexity of a separate process and interprocess communications. And you could, of course, share memory. (carefully!)

But you still need synchronization. When the Go side made a call to the C side, it would need to wait for the result. Similarly when the C side made a callback to the Go side, it would need to wait for the result. One option was to use a Windows synchronization facility. That would mean a syscall on the Go side. The other option was to use a Go synchronization facility, which would mean a callback from the C side. I decided it made more sense to use Go synchronization because I suspected that would play better with the Go scheduler and concurrency.

One way to handle the synchronization was to use Go channels. If it was pure Go code I might have gone that way. But with C involved it looked like sync.Cond would be simpler. When I searched for how to use sync.Cond, what I found was an issue where someone suggested the documentation needed to be improved. I wouldn't have thought that would be at all contentious. But  it seems some of the Go team doesn't like sync.Cond and don't think people should use it, and therefore don't want the documentation improved. Personally,  I question the logic of that. It seems like poor documentation just increases the chances of people misusing it. I appreciate the Go team and I'm grateful for all they've done, but sometimes there seems like a bit of a "we know better" attitude. (Of course, most of the time, I have no doubt they do indeed know better.) Another example is the refusal to supply a goroutine ID or any kind of goroutine local storage, again because "it might be abused". And yet internally, they use goroutine ID's. I'm just an ignorant bystander, but it seems like a bit of a double standard to me.

Despite the poor documentation (and with the help of Stack Overflow)  I figured out how to use sync.Cond. Whether I used it appropriately is a question someone else can debate. No doubt some people would say I should be using channels instead.

Using Cgo turned out to be fairly straightforward. It requires GCC so I installed Mingw64. I decided to stick to C rather than use C++. For the small amount of code I had to write, it seemed simpler and therefore safer. It took a few tries to get the synchronization working properly. The code wasn't complex, but as with all concurrency, the devil is in the details.

Thankfully, it didn't require a lot of changes to my existing Go code. I basically just swapped out the syscall and callback facilities.

Of course, it was another gamble to implement a whole approach on the basis of not much more than a gut feeling it should work. And gut feelings are notoriously unreliable in software development. But it only took a day or two to implement, and I was back to running the the Suneido IDE. And the moment of truth - would drag and drop work now? It did! By this point my reaction was more sigh of relief than elation.

Are there other bugs lurking? Almost certainly. But I'm cautiously optimistic that I've solved the crashing and corruption. The only thing talking to Windows is now a single C thread (with a regular dedicated fixed stack and no garbage collection or even heap allocation) which is a very tried and true setup. You can't get much more basic than that. The only interaction is C calling a Go function to signal and wait. No stack or heap pointers are shared between the two sides. Go's concurrent garbage collection and stack movement can work totally independently of the C thread. And as a bonus, it's more efficient to run the message loop in C with no Go syscall overhead.

I was all ready to post this, but I was a little nervous because I really hadn't tested much. I didn't want to declare victory and then find another problem. Of course, there were always going to be "other problems".

So I did some more testing and it seemed a little sluggish. At first I didn't pay much attention - there's so much background stuff going on in our computers these days that can affect speed. But it didn't go away. I did a quick benchmark of a simple Windows call and got 70 us per call. That seemed high but I wasn't sure. I checked cSuneido and it was 2 us. Ouch. Maybe it was just Go syscall overhead? (i.e. can I blame someone else?) No, directly from go it was .3 us.  My guess is that there is some kind of bad interaction with sync.Cond, but I don't really know.

Another downer, just when I thought I'd won. C'est la vie. The obvious alternative (that I had considered earlier) was to use Windows synchronization. Luckily Windows condition variables and critical sections were similar enough to Go sync.Cond that it didn't take long to switch.

I didn't actually hold my breath when I ran the benchmark, but I mentally had my fingers crossed. And it worked - now it was 1 us per call, better than cSuneido. And the IDE no longer felt sluggish.

I've been running this version for a couple of days, and it seems that this chapter of the saga is over, so I will post this and move on to other bugs.

Thread-Safe Tree Comparison

When I implemented jSuneido (Java) I ignored a lot of potential concurrency issues. (That's not as bad as it sounds - there is almost no concurrency in our application code.) But Go (gSuneido) is a lot stricter. I was surprised to get fatal potential data race errors even without the race detector.

So I was more or less forced to handle some of these issues. As usual, concurrency is trickier than you think, even if you think it's tricky.

One issue I ran into was comparing containers. The obvious approach is to compare recursively (which is what cSuneido and jSuneido did). My first attempt at making it thread-safe was to lock each container as you recursed into it. But then I realized that this would acquire multiple locks, which has the potential to deadlock. (I found sasha-s/go-deadlock useful.) The normal solution is to make sure you lock/unlock in a consistent order. But I did not have control over the order of recursion.

I searched the web for algorithms but I didn't find much. (Which was part of what prompted me to write this up.)

One option is to just use thread-safe low level operations e.g. to get a child. But locking at a low level means a lot of lock overhead. (Uncontended locks are fast these days, but they can still have performance implications.)

The only other decent solution I could come up with was to lock the object, copy the list of children, and then unlock it.

But I didn't want to add a bunch of heap allocation to copy the children. So I switched to an explicit stack and iteration instead of recursion. This may still allocate when it grows the stack, but after that it can reuse the space (which should be in cache). And it's much less than if you allocated a list for each child.

I implemented "equals" first. When I went to implement "compare" (less or greater than) it was a little trickier because I needed lexicographic order, whereas my stack was LIFO. That turned out to be relatively easy to handle by pushing the children onto the stack in reverse order.

(This code is further complicated because you have to detect recursive data. So you have to track the comparisons in progress.)

This approach is thread "safe" in terms of not crashing or getting random data. It's not necessarily "correct". But if you are making changes to containers at the same time as comparing them, I'm not sure what "correct" means. If you had immutable persistent data structures then you could grab a "snapshot" of the two containers. But even then, how do you get the two snapshots "at the same time"? Yet another lock?

Here's a link to the main part of the code as of this blog post. If you actually wanted to use this code it would probably be a good idea to look at the latest version in case I fix any bugs or come up with a better approach.