Monthly Archives: February 2009

A Divine TraceMonkey Bug

I spent the better part of the last week or so on a rather annoying TraceMonkey bug. A few weeks ago I mentioned that we extended multiple type-specialized trees to include specialization on global types. Suddenly a rare but dangerous class of bugs appeared.

The Bug

When a trace exits back to the interpreter, it does so through a guard. These guards contain an “exit typemap,” which tells the interpreter how to take types from the native CPU and box them back into generic containers for the interpreter. The bug was that some global variables were being boxed back as the wrong type. For example, the 32-bits in an integer would be stored in a slot interpreted as a 64-bit double, or an object would be tagged as a string. When the interpreter went to unbox these again, it got garbage. That’s bad. The only way this can happen is if the exit typemap contains wrong type information.

Lazily Specialization

Global variables are tracked lazily. The overarching Trace Monitor keeps track of which global variables have been seen on trace. For example, say we have a type-stable tree, Tree 1. It has no global variables, and thus has empty exit and entry typemaps (for globals). Later, the global variable X is encountered. It’s now being tracked, but Tree 1 doesn’t have a type entry for it.

If Tree 1 wants to execute again, it will lazily update its entry typemap. The exit typemaps on the other hand are fixed and cannot be modified. So now Tree 1 looks like this:

Tree 1 Entry: X = Object
Tree 1 Exit: 

When exiting the tree, we merge the exit and outermost entry types together, giving a complete typemap. More on this later. When entering Tree 1, X is unboxed and boxed as an Object, even if it never gets used. This is because Tree 1 could call into a nested tree that does use X.

Problem #1

Let’s say later we build Tree 2. It’s the same loop as Tree 1, but it’s type-unstable. The typemaps look like this:

Tree 2 Entry: X = String
Tree 2 Exit:  X = Object

TraceMonkey’s multitrees kicks in, and now Tree 2‘s exit will go directly to Tree 1‘s entry, since their types link together. When Tree 1 exits, we combine the outermost typemap with the exit typemap. In this case, Tree 2‘s entry is the outermost typemap, but it contains the wrong type! The type of X is an Object, but now it’s being boxed as a String. Crash.

Note: This is different from normal type instability, because type unstable traces represent a path where a type is actually changed. In this scenario, the type is being mistaken, which is deadly.

Failed Solutions

Solving this was complicated by nested trees. Trees can be deeply nested, and each tree along the way could be missing global types, so it seemed like we needed to recover missing global types incrementally up the call stack. That is:

  1. Start with global types from the innermost exit.
  2. Add missing globals from each tree on the call stack, starting at the deepest, and ending at the outermost tree.

Since the outermost tree is the original tree we started with, it is guaranteed to have all missing types, so it was the last resort. Achieving this ended up with three different implementations as the patch progressed, but the idea was: as we enter trees, push them onto a stack. As we exit trees, pop the stack. If we hit a guard (which exits), immediately reconstruct the full global typemap using that stack of trees. By the time we exit back to the interpreter, a global typemap will have been prepared already.

Alas, this wasn’t enough, because…

Problem #2

Say we have two trees on the same loop, Tree 1 and Tree 2. Their typemaps are:

Tree 1 Entry: X = Object
Tree 1 Exit:  X = String
Tree 2 Entry: X = String
Tree 2 Exit:  X = String

In this situation, Tree 1‘s exit is linked to Tree 2‘s entry. Later, a new global appears, Y. We execute Tree 2 with X = String and Y = Object. Then we execute Tree 1 with X = Object and Y = String. Because of lazy specialization, the typemaps now look like this:

Tree 1 Entry: X = Object, Y = String
Tree 1 Exit:  X = String
Tree 2 Entry: X = String, Y = Object
Tree 2 Exit:  X = String

This is problematic, because Tree 1 is still connected to Tree 2, but their typemaps are incompatible! If we run Tree 1, Y will be unboxed as a String and reboxed as an Object, without the underlying type actually changing. The solution to Problem #1 doesn’t fix this.

Solution

Linked trees should never have incompatible typemaps. What counts as a linked tree? Any two trees that are connected via a nested call (nested loops), or any two trees that are connected via type instability (multitrees), are “friendly.”

In pseudocode:

LazilySpecialize(Tree):
  AddMissingGlobalTypes(Tree)
  FOREACH Tree IN FriendlyTrees
    IF MissingGlobals(Tree)
      LazilySpecialize(Tree)

Now when a tree exits, it suffices to use only the exit typemap and the typemap of the innermost entry (that is, the tree the exit immediately came from). This neatly solves Problem #1. If any one tree gets a new global, the entire graph of connected trees is updated, solving Problem #2.

This is probably one of the more difficult TraceMonkey bugs I’ve had to reason through. Nested trees always seems to complicate how you reason about tracing, and in this case it ended up not mattering. And though the problems are conceptually disjoint, they also feed into each other: fixing only #1 led to #2 breaking.

What’s next for AlliedModders?

It’s the question no one asked!

SourceMod Motivation

As I’ve too often said, the original SourceMod failed because we tried to do too much without understanding project management, the scope, or even how to code most of what we wanted to do. When we began talking about restarting the project, we did so from a research point of view. We asked the community: should we spend time writing a new language, or just get something to market on Pawn?

The community voted the latter, so we approached the project with the following questions: What would SourcePawn look like if it were modernized a bit? What would AMX Mod X look like if it had a much cleaner and more consistent API?

We wrote a new VM and JIT for Pawn. We added fast strings, basic function pointers, and dynamic arrays to the language. We boxed it into a fairly simple plugin with a small API and watched it take off, adding more as it got requested. Commands, events, menus, FFI, et cetera. It was fun designing all this.

What’s left to do that’s interesting? There’s a lot of open bugs for features people want. Perhaps the only really big ticket item left for SourceMod is script-level detouring of virtual functions, which has been in the works for a long time (and is about 50-60% done).

Most of what needs to be done though is hacking away at the indescribably infuriating Source engine, and all of the closed source games that run on it. This is boring. Sure, we’ll continue to do it. But it’s not interesting. It’s rote reverse engineering against the same old stuff. It’s monotonous and tedious, not to mention fragile. If we were developing a full product (game), we’d have access to everything. But we don’t, and we’re stuck in what’s ultimately a script kiddy’s role.

SourcePawn is Limited

SourceMod has stretched Pawn to its limits. It’s a crufty language. There is no heap. Memory management is manual. Strings are byte buffers. There are no types. There is no data integrity or safety. There are no structures or classes, just C-style functions and opaque integer values.

Basically, writing SourceMod plugins feels vaguely reminiscent of WinAPI except you don’t have any of the advantages of C.

Compiling plugins is asinine. It causes so many problems – arbitrary compatibility issues, secret backdoors, license violations, site and forum maintenance difficulty, et cetera.

Pawn is very fast because it’s so limited, but it’s also hard to squeeze more optimizations out. Everything has to go through natives, even small trivial functions. The bytecode is very low level, and though Pawn as a language has immense JIT potential, our JIT is very basic because the bytecode is too hard to analyze.

So… where do we go from here?

I want to start looking at more involved questions. The type of questions SourceMod might have asked if we had chosen the former path when restarting the project. I’ve boiled this down to two issues:

  • What would a language look like if it were specifically designed with trace compilation, game scripting, and embedding in mind?
  • What would Pawn, a language designed to be simple, look like as a truly modern scripting language, and not something from 1980?

Relatedly, there are two interesting questions for SourceMod:

  • What would SourceMod (as an “AMX Mod X done right”) look like with a more modern, object-oriented language available?
  • Can SourceMod be self-hosted?

I have mentioned this before. Most people say “Just use Python, or JavaScript, or Mono, or X!” where X is some random language that I don’t want to use. That’s not something I’m interested in. If you want to see what your favorite language looks like in Source, go ahead and embed it. This isn’t a case of NIH. It’s something I very much want to pursue to see where it goes.

The Next Project

The next project has been started. It’s a new programming language. I’ve chatted a bit about it in IRC, mostly to get some bikeshedding out of the way. As the project is not official yet, there’s no official name.

I have no idea how far this will go, or if it will go anywhere. But it’s been started. Goals, or rather, properties of the language will be:

  • Dynamically typed.
  • Strongly typed.
  • Object oriented.
  • Garbage collected.
  • Static lexical scoping.
  • Nested block scoping.
  • Explicit variable declaration.

I’ve started work on a garbage collected, register-based bytecode interpreter. I won’t start the actual compiler until I’m pleased enough with backend progress, and I won’t start the JIT until I’m pleased enough with overall maturity.

Everything will be incremental. Parity with Pawn is enough to let people start playing with things, and that would be a huge, huge step.

If anything ever comes of this, it will be interested to see how it can fit into SourceMod. While we can never get rid of Pawn because of compatibility, there’s lots of room for potential. IRC goer theY4Kman embedded Python in a SourceMod extension. We could try something similar as a starting point, or we could do something like EventScripts where Python and the “old language” of the older, darker times lives alongside.

Who is working on this?

For the most part, just me (and, if they so desire, other SourceMod developers). This is a pet project and I don’t want to be too distracted. I also don’t want to tie SourceMod to its success, so it has no relation to SourceMod’s roadmap in any way. But like SourceMod, it’s something I will attempt to work on incrementally in my free time.

If progress on this is something people are interested in, I can keep talking about it. If you’re really interested in it, feel free to find me on IRC (irc.gamesurge.net, #sourcemod). More than likely I’ll be occasionally throwing random design questions around out loud.

AAA Doesn’t Like Doing Work

Since I’ve returned to the wonderful and freezing east coast in December, I’ve had two encounters with AAA while staying with my parents.

Encounter 1
Around December 20th or so our car couldn’t get up an unplowed hill in New Hampshire. It was a two-wheel drive Mazda (I forget the model), and for whatever reason we couldn’t gun it enough to get to our house.

We called AAA to see if the car could be towed up the hill. No go, they said, if we couldn’t get it up then they couldn’t get it up either. Furthermore that didn’t count as something that would be covered, since the problem was with the road, not the car.

We said, “well eventually we’ll be stuck long enough out here that we’ll run out of gas.” The reply? “Well, in that case we’d come bring you more gas.” Uh.

I can believe them that that towing the car up the hill seemed implausible. But they could have offered something, like, towing the car somewhere safe and then bringing us up the hill.

Instead, we had to walk. In 10F degree (-9.5C) snowing weather. Up a steep hill, in the dark, for what we later clocked to be 0.7 miles (1 km). While carrying all of our luggage. It felt like the desert scene from Spaceballs, but we didn’t have any food or supplies at the house, so there were more necessities than usual.

I have severe chronic asthma, which though has gotten much better over the years, still needs work. It must have taken me around fifteen minutes to breath normally again after deeply inhaling freezing cold air for so long.

Later the next day, a family acquaintance with a plow came and plowed the street, then managed to gun the car straight up the hill with no problem. Gee, I wonder if AAA could have done that.

The incident caused my parents to, a mere ten days later, get a used 2006 Toyota Highlander Hybrid for its four wheel drive.

Encounter 2
Cars are supposedly supposed to turn off their internal lights once they’ve been closed and locked. For one reason or another that didn’t happen in the Toyota Hybrid, and the battery drained. We didn’t have jumper cables for that car yet so we called AAA.

AAA refused to jump the car because it was a hybrid. They hadn’t developed a procedure for hybrids yet. Huh? Hybrids have been out for a decade. What has AAA been doing all this time?

But that’s irrelevant, because it’s a normal battery like any other car. The owner’s manual even tells you how to jump it, and it’s exactly the same as any other vehicle.

So AAA tows the car back to our house, but the guy AAA contracted wants to try jumping it anyway out of curiosity. He connects positive to positive, then negative to negative – wait what?

You’re not supposed to connect the dead negative terminal – it’s supposed to go to ground. So AAA apparently doesn’t know how to jump a normal car. The guy was nice though, was glad to know the correct procedure, and what do you know? The hybrid jumped fine.

Conclusion
I’m not really sure I have one, other than that AAA clearly isn’t going to go out of their way to help you. They have some tome of procedures and will obey it to the letter. Maybe they’re afraid hybrids will detonate into some sort of mushroom cloud explosion. Perhaps in 2050 they’ll know how to jump them (or, any car).