The Joshua Tree

Game Hacking: Part Deux

noreply@blogger.com (Joshua Kriegshauser) — Fri, 22 Nov 2024 01:35:00 +0000

I'm still playing through the Assassin's Creed franchise. But now I've finished Rogue and have moved on to Unity which--although released on the same day--are (console) generations apart. However, this also means that the games were created with different Ubisoft game engines: AC:Rogue was the last game on AnvilNext and AC:Unity was the first game on AnvilNext 2.0.

Different engines ostensibly have different issues, and older engines can have issues on newer hardware. My previous post describes my issues with AC:Rogue where the game would stall for seconds at a time with too many CPUs. And I run an AMD Threadripper 5975W with 32 cores/64 hyperthreads--difficult hardware to come by 10-12 years ago when these engines were created.

Turns out that AC:Unity also has problems with too many CPUs--it crashes to desktop immediately after launch!

Has this already been fixed?

The first step was to see if anyone else has run into this problem and if they've fixed it. Turns out I was in luck. A reddit user running on the same CPU had the same issue. Unfortunately, the workaround was pretty sucky--disable CPU cores in the BIOS. I definitely don't want to have to reboot before and after playing the game.

Fortunately now we know what the problem is--too many CPUs. The fix in the previous blog post was similar, but since this is the second game I've had to fix in the same way, let's see if we can make a fix that is more generic.

Let's make a generic tool! But how?

Enter Microsoft Detours--an amazing tool for hacking (and even some legitimate uses). Basically the plan is to create a .DLL file that we can inject into the process that will intercept (or hook) some system calls and ~~lie~~ present an alternative set of facts to the game. This .DLL can be used with nearly any game, so we could go back and use it with Rogue to fix it without hacking the assembly language.

In the previous post, we pointed out two system calls (GetSystemInfo and GetNativeSystemInfo) that tell us the number of CPUs, but this is just the tip of the iceberg. It turns out that AC:Unity uses many more system calls than this. And for our generic tool to support all games, we should at least figure out what AC:Unity is using and support those calls.

But where do we draw the line? In the past 20+ years we have gone from single CPU to multiple SMP CPUs, to NUMA. Machines are available these days that have over 64 CPUs. AMD is preparing to launch servers with 256 cores next year (order now!). Now it's unlikely people will run games on these machines, but that was probably the thinking back when 32+ CPU machines were unheard-of. The point is that modern Operating Systems have evolved and added system calls to support NUMA, CPU Groups and CPU Sets. While it's conceivable that games could call some or all of these, let's assume that they won't. But maybe we can set up some logging for these functions to see if they're ever called.

The bigger issue is probably going to be affinity. Simply put, affinity is a list of CPUs that a process (or threads) can run on. Typically this list is given as a bit mask since each bit can effectively represent a CPU. Since (historically) the number of CPUs was small, this was fine for a 32-bit value, but now we have over 32 CPUs! No longer can a single 32-bit value represent an affinity mask. Older 32-bit applications typically used a 32-bit value, but newer 64-bit applications generally use 64 bits (but bugs may exist from porting previous code, etc.).

Intercepting Functions

The Detours wiki has a pretty simple minimum example for ~~hooking~~ instrumenting the Sleep function. Let's alter it for GetSystemInfo, one of the functions that we'll need to intercept. (Source Listing)

This listing will compile into a .DLL that, when loaded by an application, will override calls to GetSystemInfo and allow us to alter the responses.

Once DetourTransactionCommit() is called in our InstallDetours() function our hook is in place:

Now whenever GetSystemInfo is called, our version is called instead. We just happen to call the original and then modify the number of processors:

The next step is that we need to get the game to load our new DLL. Unfortunately, this is easier said than done. Games these days typically don't want hackers messing with them and they go to great lengths to try to prevent that (just as I did when working on my games). AC:Rogue didn't have any protections, but AC:Unity has a multiplayer element to it, and multiplayer games typically make attempts to curb hacking/cheating. Now I'm just trying to get the game to run but it doesn't know that.

Detours has (at least) two tools that can be used. The WithDll tool can be used to launch an application and inject a DLL before it fully loads. Unfortunately this method didn't work with AC:Unity because of how it's launched. I purchased the game through Steam, so Steam launches AC:Unity, which sees that it wasn't launched from Ubisoft Connect, so it launches Ubisoft Connect and exits, which does a few things (cloud sync for instance) and then re-launches AC:Unity. Since I cannot control how the game is launched from Ubisoft Connect, this didn't pan out. Interestingly though the app did launch with the injected DLL.

The other tool is SetDll. This tool can modify an executable file to always load a new DLL. This sounds like exactly what we need! Unfortunately, this didn't work either since AC:Unity has hack-prevention checks that noticed that the executable was modified and refused to run.

Frustrated, I started looking in to other ways to inject the DLL. SetDll works on DLLs too, so if I can catch it early enough in the loading process, I could use a different DLL as an injection vector. I fired up Process Monitor and fiddled with the filters to see what the AC:Unity process was doing when it started. Turns out it ships with a DLL that is loaded very early, and that DLL doesn't complain about modifications. Eureka! I have my injection vector.

I added some simple logging (using OutputDebugString that I could view with the DebugView utility) to my simple example to make sure that my function was being called (since AC:Unity also detects debuggers and terminates the process if one is found). Good news--it was being called! But of course, the game was still crashing. So while this was enough to essentially fix AC:Rogue, the newer engine does different things and will need more work.

Affinity Functions

As I mentioned above, the functions that control affinity are probably in use. The Microsoft article about Processor Groups has a good list of functions that control affinity and scheduling. My process was to first add logging for these functions to see if they were being called. The logging would include what arguments that AC:Unity was passing to the functions as well as what the functions returned. Turns out that several of them were being called. Even though GetSystemInfo (and GetNativeSystemInfo) were intercepted and showing a lower number of CPUs, the affinity functions were happily reporting affinity across a larger number of CPUs.

The next process was to change the behavior of these affinity functions to only return bits set for the number of processors that we were emulating.

An interesting function that it turns out AC:Unity was also calling is SetThreadIdealProcessor (and the extended version). This function gives the Windows scheduler a hint about which CPU to schedule the thread on, but it's not as strong as affinity. I also intercepted this function to only allow the processors in our emulated set.

Logical Processor Info

In my work hacking AC:Rogue I discovered that it was optionally looking for and calling a function called GetLogicalProcessorInformation (which also has an extended version). CPUs these days are very complicated: they have multiple layers of caching (some of which are shared with other cores), can share hyperthreads with other cores, not to mention the NUMA relationships. These functions are the means to access this data on Windows, and as you might expect, are quite complicated. The extended version is even more complicated allowing different means of querying data and returning variable-sized information.

It turns out that AC:Unity was also calling these functions, so they are another one that I had to wrangle.

For the original function, all of the data is presented at the same time, so the function returns the same data every time it is called (at least, it is highly unlikely that it would change while the game is running). Therefore, it is easily cached. The first time my intercepted function is called, it queries all of the host data, chops it down to only include our emulated processors, and saves it off so that every subsequent time that we're called we just return the same data.

Unfortunately, the extended function allows specifying a Relationship Type to query, and the data is drastically different based on that query type. My solution here was to cache the chopped-down host data and remember the Relationship Type along with it. So if a different Relationship Type was queried I would throw away the cache and rebuild it. This however was much more complicated because of the variable-sized data. I essentially had to filter the data in place and then copy the filtered data into the cache. For this it's probably better to look at the code directly: (intercept function, cache builder)

Does it run now?

YES! 🎉

In the end, I ended up hooking 12 functions (but three--the Process Group functions--weren't called by AC:Unity and therefore only log).

Finally, I can play the game for a bit.

But... oh no. There's another problem.

The Video Problem

I have a Samsung Odyssey G9 49" monitor. It's aspect ratio is 32:9 and I'm playing a game originally designed to run on consoles that output 16:9. However, the PC port of the game itself beautifully figures out the correct aspect and does pretty well with the super ultrawide display, as evidenced in the screenshot at the top of this post.

The problem is the full-motion videos that it uses for cutscenes. They are originally designed for 16:9 and are stretched out to 32:9--double the width they should be. It's almost breaking my brain trying to watch them and figure out what's going on.

A very wide Mr. Templar tied to a tree

Can I fix this too?

Bink Video

Bink is a popular video encoder and player software package for games. Developed by RAD Game Tools (now owned by Epic and rechristened as Epic Game Tools), Bink was originally released way back in 1999.

Bink is pretty easy to integrate and very fast. I integrated it in to EverQuest 2 back in 2006, so I'm somewhat familiar with the API.

Turns out that Ubisoft uses it in AC:Unity, though a much newer version than the one I used. Fortunately a lot of the API seems to have remained consistent. And all I want to do is prevent the videos from being stretched.

Research

The first step is to figure out how AC:Unity is using Bink. Fortunately I already have the means to do this, just like I did with the CPU Windows system functions--hook the API calls and see how they're being called. Bink is loaded as a DLL, so theoretically I can hook it too.

And the initial tests are promising. I used Microsoft's dumpbin tool to list the exports from the Bink DLL. Pretty much any application is guaranteed to call BinkOpen, so that's the first function that I hook. And testing is quite quick since the first thing AC:Unity shows is the Ubisoft logo video.

Unfortunately, this is where things hit a snag. I've managed to hook a few functions that give me useful information (I can see BinkRegisterFrameBuffers called for instance), but none of the functions with names that sound promising are ever called (BinkCopyToBuffer, BinkCopyToBufferRect, BinkBufferOpen, BinkBufferSetResolution, BinkBufferSetScale). I ended up hooking 20+ of the most interesting sounding functions only to see a tiny few of them being called. How is it accessing the data without calling BinkCopyToBuffer?!?

It's time to get dirty. I can't attach a debugger because of the anti-hack measures (and it will take way too long to reverse engineer those), but I need to see it in a debugger when it's trying to access the data. So I'll make the game hang when it tries to access the framebuffer!

It turns out this isn't too complicated: I register an unhandled exception filter that just sleeps infinitely when a crash happens, and then I call VirtualProtect to tell Windows to make the framebuffer data no-access--any attempt to read or write to it will cause a crash. However, I have to allow Bink to write the data in to the framebuffer, I just want to see where it's read back out, so I have to allow access to the BinkDoFrame function.

As soon as the game hangs (without displaying the first video frame) I use Task Manager to write a full dump. But the dump is confusing. I have no symbols, no function names, nothing to really give me any clues as to what's happening except the assembly code. And it looks like AC:Unity is reading the data directly out of the framebuffers.

That's exactly what it's doing. AC:Unity is calling BinkRegisterFrameBuffers which means it is allocating its own framebuffers and undoubtedly retaining the pointers. BinkDoFrame will decompress the video stream into the framebuffer, and then AC:Unity is reading the data (probably with a shader) to display on the screen.

The video fix

Looking at the allocated framebuffers, they're 1920 x 1080 (16:9 ratio) and their shaders are probably the stretching culprit. I'm not a GPU/graphics guy (ironic given where I work) and I have no idea how to break into the game's shader pipeline. It can be done because there are other mods out there that do, but it will take a long time to learn how to do this. And I want to get back to playing the game, so how do I do it quickly? Is there something I can do to the framebuffers?

It turns out I can! I need AC:Unity to allocate 32:9 framebuffers instead of 16:9, and the first two values in the structure returned from BinkOpen looks like width and height. So the first thing I try is just scaling that width to 32:9. Since buffers historically were powers of two, they typically have a pitch passed to the decoder that says how many bytes represent a line so that it can skip to the start of the next line (extra bytes would just be off the screen). This helps us out here since the pitch tells Bink to skip about half of the line and just start decoding on the next line. It works!

Better?

Well, kinda. Why is half of the screen green? Hey, but at least the aspect ratio is correct. And it's not centered, but we can fix that too (probably).

Alright, so the green screen. Encoding video data as RGB is very inefficient. Remember, Bink is a library developed in 1999 and first used on the PlayStation. It uses the YCrCb color space for its video information to use less space. AC:Unity likely has a pixel shader that computes the RGB values from the YCrCb planes that the framebuffers are allocated from. The buffers started with zeroed bytes and since the right half of the screen is never written to by the decoder, they remain as zeroed bytes. Well converting the zero values for YCrCb ends up with RGB color #008700, a quite greenish hue.

Looking up the value for black in YCrCb and setting the initial state of the buffers to those values gives us a dark gray. Not quite black. But that link has the minimum Y value as 16, which gives us a dark gray, but trying a Y value of 0 gives us black.

So the last issue to tackle is the centering. AC:Unity has given Bink the addresses for the framebuffers by calling BinkRegisterFrameBuffers. Bink decodes data into the first line at the start of the buffer, advances the line pointer by pitch bytes and decodes the next line, so on and so forth. If we can tell it to use a different starting address for the buffer that represents a centered frame, it will move the whole image.

This is pretty easily done, we can just calculate the scaled width of our screen, subtract the width of the video and divide by two to get the framebuffer line offset. We have to do this for each plane separately because the Cr and Cb planes are smaller than the Y/A planes. The tricky thing here though is that Bink requires the framebuffer address to be 16-byte aligned, otherwise a hang occurs in the decoder (speaking from experience).

Voila!

Not so wide now, Mr. Templar!

Source is here. Uploaded to NexusMods and now back to playing the game!

Game Hacking

noreply@blogger.com (Joshua Kriegshauser) — Thu, 10 Oct 2024 02:07:00 +0000

I've been playing through the Assassin's Creed franchise in anticipation of Shadows due out later this year, or well, now pushed to early next year. I really enjoyed Assassin's Creed IV: Black Flag, but ran into an issue that some other people had too: Kenway's Fleet wouldn't load. Fortunately, someone created a patch that fixed it, and additionally made initial connection to Ubisoft much faster.

Fast forward a bit and I'm playing Assassin's Creed: Rogue, which is a great game in its own right, but borrows a lot from Black Flag. However, I started running into an issue: five (or more) second stalls where the game would just freeze (audio would keep playing) and then resume as if nothing happened. I could go a minute or so without these freezes, but sometimes it would be only a second or two after the previous freeze. It was nigh unplayable.

Searching around, other people didn't seem to report the same problems that I did. But my PC is pretty unique: it's an AMD Threadripper with 64 logical cores and 128 GB of RAM. That's a lot of hardware for a game released 10 years ago. Looking in Task Manager, I see that the game has about 280 threads. That's a lot! I wondered if the game is creating a number of worker threads per logical CPU, but perhaps isn't optimized for such a high number of CPUs. Designing software that runs well fully using 4 CPUs is a lot different than software that fully uses 64 CPUs.

Alright, so my working theory: the game has a contention problem that shows up with tons of threads.

How to test that theory? I fire up one of my favorite profilers: Superluminal. Unfortunately, my ability to seriously debug performance issues is going to be hampered by the fact that I don't have any debugging information (or source code) for the game in question. But Superluminal can tell me what the OS is doing, and what requests the game is making of the OS.

So I fire up Superluminal and tell it to start watching "ACC.exe", the AC:Rogue executable. Sure enough, within a few seconds I get a 5 second stall. After it recovers, I head back to superluminal to stop the tracing and start looking at it. The stall is clear as day and I have selected it here:

From this, it's pretty apparent that the main thread is running hard during the stall, and from the function list in the bottom-left corner, I see it's trying to lock and unlock "critical sections" which are Windows mutex-like objects. Note that before and after the stall the main thread spends a decent amount of time synchronizing (the red part of the red/green CPU activity graph). Let's scroll through the other threads and see if we see anything else interesting.

Aha! Thread 86036 has a CPU chart that is all blue. This is Superluminal's visual language for "preemption" that is, the thread was running but the Windows scheduler decided that running something else was more important. Also interesting to note that the other worker threads above are completely blocked on synchronization. They're just waiting during this stall.

Looking through some of the other threads there's not really much that is interesting. A few threads are sleeping and waking up periodically. But the main thread is running hard, this thread 86036 is preempted, and pretty much everything else stops while this is happening. It's possible that Windows (for some unknown reason) chooses to stop running this thread 86036 and instead runs the main thread.

Superluminal gets information about every process running on the system at that time, and the only thing using any CPU is ACC.exe, the game we're profiling.

For additional information, I also captured system state using Event Tracing for Windows by utilizing the UIforETW tool by Bruce Dawson. Looking at the capture I was able to find a different stall in the same thread:

Check out the highlighted line: the thread was ready to run for 4,747,081.6 microseconds (4.7 seconds!) before it ran, and the Readying Thread of -1 indicates that it was in fact preemption. Not immediately apparent from the screenshot (but from further digging through the UI) is that both the main thread and thread 86036 have the same Ideal CPU (0) and Priority (15)

Unfortunately it's still not super apparent exactly what is causing this. A possibility is affinity--which CPUs a thread is allowed to run on--but it's not clear how to check this. Most threads have 0 as their Ideal CPU, so I'm not sure that this value is actually used by Windows 11. But the Priority values are interesting. Most of the threads in the process have Priority values of 13 and 15, which would correspond to a "High" priority class and "normal" and "time critical" priorities respectively. If both the main thread and thread 86036 share a "time critical" priority, they could affect each other running.

But my initial thought was that 280+ threads is a lot, especially if it's running some or all of them as time-critical priority. Let's see if we can get the game to create fewer threads. Unfortunately, this is easier said than done.

Most compute-intensive programs trying to max-out a machine (like games) will typically create at least one thread per CPU, so maybe we can lie to the game about how many CPUs there are. There are actually several API calls that it could be making to determine this, but the most common one would be GetSystemInfo (side note: modern C++ Runtime implementations use GetNativeSystemInfo, but this function does not appear to be used by ACC.exe). Fortunately the game executable doesn't appear to be cryptographically signed, so we should be able to patch it.

The next step is to disassemble the game so that we can find the places where it might be trying to find out the number of CPUs. For this I used IDA Freeware. While the disassembly is quick, the analysis happens in the background and takes a little while. Once analysis was done, I looked at the Imports and found the GetSystemInfo function. There were several cross-references to places that were calling it (I took the liberty of renaming the functions based on a cursory glance of what they were doing):

Let's take a look at the second entry, the one that I renamed to getSystemInfo2. I was really impressed with IDA here: it understands Windows API structures and was able to figure out how members of the structures were being used:

Note that dwNumberOfProcessors is read into the edx register here and stored in various locations. Instead of reading the value from the structure, I want to lie to the game: I want it to see a hard-coded value of 8 CPUs. So now I need to change the bytes (8B 54 24 50) which is the machine code for "mov edx, [rsp+68h+SystemInfo.dwNumberOfProcessors]" to... something else. Something that just gives me the value of 8 in edx. Unfortunately the free version of IDA doesn't do assembling, so I can't write new code here and expect IDA to build me a new executable.

Instead, we're going to do it the hard way: I need to figure out how to get the value of 8 into edx but in 4 bytes or less. Since IDA won't help me out here, I'll use an online assembler to try some things, and then a hex editor to change the actual bytes.

Well, let's try the obvious instruction: "mov edx, 8"

Unfortunately this results in 5 bytes (ba 08 00 00 00), which is difficult to stuff into 4 bytes. What's interesting is that the full immediate 32-bit value representing "8" is present in the machine code, which makes some sense since we're writing to a 32-bit register.

This gave me an idea. What is the machine code to move 8 into the lowest byte of edx (the dl register)? Turns out this is only 2 bytes (b2 08)! The problem is that the other 24 bits of our edx register are garbage. Maybe we can clear the register with an xor (exclusive-or) instruction? If you xor a register against itself the value is always 0. Let's try that: xor edx, edx--this produced machine code (31 d2).

Perfect, so we have our solution:

Then I'll just use my trusty hex editor plugin for VSCode to search for the preceding bytes and write over the old bytes:

We just need to apply this to each location in our cross-reference list above.

Working through the list, we run into a problem with the function that I've called "getMemoryAndCpuInfo". The dwNumberOfProcessors value is written to a different register: r11d. This is an extended register for 64-bit processors and needs 5 machine code bits to read the value into it.

Unfortunately, our trick isn't working here. Assembling "xor r11d,r11d; mov r11b, 8" takes 6 bytes.

Let's try a different approach: push and pop the value, which uses the stack. We really don't want to make any stack changes as moving the stack pointer will cause issues with all of the following instructions that read/write from the stack. But if we immediately reset the stack pointer by popping the value, it should be fine. So let's try that:

Perfect! The push/pop is only 4 instruction bytes, so we had to add a "nop" or no-operation instruction (only one byte) to bring us up to our total of 5.

Our next wrinkle happens in the function that I've dubbed getProcessorTopology. While this function is also calling GetSystemInfo and using dwNumberOfProcessors (easily patched by our previous methods), it's also doing something further:

It's checking to see if Windows is new enough to have a function GetLogicalProcessorInformation and calling it if it does. We don't really want the game to call this function since it ruins our lie about the number of processors. Fortunately, this function is smart enough to handle the situation where that function doesn't exist. So to prevent it from calling this function, we'll just change the name to all X's. It will attempt to find a function called XXXXXX... which obviously doesn't exist. IDA can also confirm for us that this is the only location where that string is used, so we can safely change the name.

Unfortunately we're not out of the woods yet. There is one more function, and it's a doozy:

This function is doing a signed integer divide by the number of processors. None of our tricks thus far will work for this. Let's take a deeper look at what this instruction is doing. It takes a 64-bit value with the most significant 32 bits in edx and the least significant 32 bits in eax and divides by a 32-bit value (in this case, our dwNumberOfProcessors)--eax will receive the quotient and edx will contain the remainder. It does this in only 4 bytes!

However, it doesn't appear to be using the quotient at all, just the remainder. So this is actually doing a modulus by the number of processors. So what we need to do is actually a modulus by our lie of 8 processors. Can we do it in 4 bytes!?

Well, we have a few things going for us. The original function does a cdq (convert doubleword to quadword) instruction to set up for the divide, it also needs eax and edx for the divide but only edx with the result. And since we've chosen a magic power-of-two value of 8, we can achieve a modulus by doing an AND operation with (8 - 1) or 7.

Within reason, we can also move some instructions around as long as the side-effects are the same.

All we really need to do is this, which is only 5 bytes:

And we've already established that we don't need the cdq instruction since that was part of the divide. So cdq + idiv gives us 5 bytes! All we need to do is move the "mov r8, rbx" one byte earlier then we have the 5 bytes that we need together!

That's all the locations calling GetSystemInfo patched up. The question is, does it run?

I fired up the game, and it purrs along like a charm! No more stalls. Seems like the theory of my computer having too many CPUs for an older game trying to take advantage of them was accurate.

I've uploaded the patched executable to Nexus Mods but as of this writing there haven't been any downloads. I guess not many people are trying to play a 10-year-old game with 64+ CPUs! At least I'm enjoying it again 😉

Fixing a Memory Corruption bug in Python

noreply@blogger.com (Joshua Kriegshauser) — Sat, 06 Jul 2024 20:48:00 +0000

For Omniverse we use Python for scripting. About a year and a half ago, we upgraded from Python 3.7 to Python 3.10. Shortly thereafter, we started seeing occasional memory corruption issues crop up, but it took a while to actually link the cause to Python.

A lot of the crashes that we were seeing involved very deep and complex Python stack traces in seemingly innocuous things: the garbage collector, releasing a reference, sometimes allocating new memory within Python. Since my team in the Omniverse group handles the plugin system, we manage the plugin that embeds Python into Omniverse, which means I was assigned all of these crashes for triage.

We do have some internal Python experts, and my team wasn't the tip of the spear on the 3.7 -> 3.10 upgrade (though we were involved). The nature of memory corruption means that crashes can happen in very random ways, since any call to acquire or free memory (which happens a LOT) may trigger a crash. So we had 20+ different stack traces that were considered to be part of the same memory corruption pathology. Curiously, this was only happening on Windows, and another clue was that quite often we would see an error in the log sometimes well before the crash occurred:

RuntimeError: <_overlapped.Overlapped object at 0xXXXXXXXXXXXXXXXX> still has pending operation at deallocation, the process may crash.

"Helpful!" I thought to myself sarcastically. Well, the process was in fact crashing, so this may be an indication as to what happening.

However, this crash was fairly low priority. It wasn't happening often per se, but it was annoying. I made a task to track all of the different automatically generated crash stack traces, and periodically tried to find someone who could look into it. Since it was Windows-only and rare, it never percolated up to the top of anyone's priority queue.

Months passed and I continued to be irritated when another new stack trace would pop up. Everyone, including me, was busier with higher priority tasks. Since no one else could be bothered to fix it, I eventually decided to take a crack at it.

"Overlapped" I/O?

Typically when you're writing a program and you want to do a network request, or reading a file, or any other sort of input/output the easiest thing to do is to stop everything and wait because you need the results before continuing. But in the world of 60+ FPS, stopping and waiting for even a few milliseconds can feel sluggish. We instead want to do things a-synchronously--have them happen in a background process and the program can do other things while waiting. One way of doing this is through parallelization, that is, using a separate thread or CPU to do work, but this can also be messy. Also, Windows is old and computers used to just have one CPU, so a long time ago Windows started doing a-synchronicity through concurrency and the Operating System would handle interleaving all of the requests. "Overlapped" I/O is how Windows started doing that: multiple I/O operations could be done at a time, hence they overlap each other.

The problem is, it's pretty complicated. And even more so in an environment like Python where implementation requires both C code and Python code.

Reproducing the problem

The first step was to try to reduce the problem to a minimum so that it was easier to debug. I also knew that we started having this problem when we moved from Python 3.7 to 3.10, so I looked at the changes to see what might be different. I noticed this in the "what's new in Python 3.8" article:

It turns out that Windows and Linux asyncio event loops are implemented quite differently, which makes sense because Asynchronous IO works quite differently on Windows and Linux. With Python 3.8, asyncio now used Overlapped IO by default through the Proactor event loop.

Omniverse was also doing something different from most Python applications: constantly stopping and re-starting the event loop. See, in most Python applications the program hands control to asyncio until the program finishes; asyncio then dispatches everything that the application does. Since Omniverse uses embedded Python, we still have a graphical application that needs to run, so each frame of the graphical application we would just run the asyncio event loop for one "tick" and then stop it.

I wrote a simple app that emulated that behavior, but I couldn't get it to crash, so that wasn't enough to do it. We had a sample case that could produce the Overlapped error message typically within 5 minutes (which is an eternity when you're waiting for it), so I looked at what it was doing. After much debugging I found another clue: other threads were calling call_soon_threadsafe on the event loop. I added that to my test program. BINGO. This program had an 80% chance to print the error message within 60 seconds:

This program starts a thread that pings away scheduling a dummy function to run on the next loop iteration. It's real purpose is to send a wakeup signal to the event loop. The main thread just constantly does our stop/run idiom like Omniverse does so it doesn't have to hand control to the event loop permanently.

But does it corrupt memory?

The error message comes from the implementation of _overlapped, which is done in C and acts as a bridge between Python code for the asyncio event loop and the Windows API call to manage overlapped I/O. Let's look at what happens before that.

When the run_forever call is cleaning up it tries to cancel the "_self_reading_future":

Which in turn calls into the C code for _overlapped and invokes a Windows API function called CancelIoEx:

Then the run_forever function unregisters the 'overlapped' object (ov) and sets the future to None, effectively destroying the object.

This is where the danger arises! The overlapped structure (managed by the overlapped Python object) has been passed to the Windows API when an IO operation was requested (in this case it's for the socketpair used to notify the event loop for other threads) and cannot be deallocated until Windows reports that it's done with it!

The deallocation function attempts to check this, and reports the error message if Windows isn't done with it. But then goes on to deallocate the structure anyways, which can lead to memory corruption!

While not ideal, a better alternative might be to report the error and leak the OVERLAPPED structure so that a crash won't occur. But the best alternative is to see if we can fix the problem.

With a reproducible case and an understanding of what was going on, I filed a Python issue.

Can we fix it?

I put the initial diagnosis into the Python issue: CancelIoEx is being properly called, returns TRUE meaning that Windows requested the cancellation (NOT that it was cancelled yet!), but the deallocation function sees that the overlapped I/O hasn't yet completed. It tries to call CancelIoEx again (this always fails with ERROR_NOT_FOUND since the previous cancel request succeeded), and then calls GetOverlappedResult (note that wait=false because the second CancelIoEx attempt fails), which will also fail with ERROR_IO_PENDING. As a test I tried changing it to wait, but this just caused a hang.

What gives? Originally I though this was a bug in Windows and handling Overlapped I/O, but then I tried something else. Not only is this system using Overlapped I/O, it's using another complex Windows-ism: I/O Completion Ports. This system is a way to group multiple I/O requests together, so that instead of having to check myriad different requests, you check one "completion port" to find out when any of your requests finish. What if the cancelled I/O request is stuck in the I/O completion port? Instead of waiting on GetOverlappedResult, maybe I need to read the request from GetQueuedCompletionStatus.

BINGO.

Turns out that was the case: it really depends on where within the labyrinthine Windows I/O ecosystem the I/O request ended up before the cancel request happened.

So now we could make an "official" fix recommendation. Generally large projects like Python desire fix recommendations from outsiders like me to be as simple and elegant as possible. Which meant that I would have better luck without completely trying to change how their Overlapped I/O worked. Since all we needed to do was make sure that GetQueuedCompletionStatus was called on our _overlapped object again, that gave us a goal. GetQueuedCompletionStatus was actually called every time the event loop ran, and it already cleaned up finished _overlapped objects once they completed. All we need to do is only allow cleanup after canceling if the I/O was complete, otherwise it would get cleaned up automatically during the next event loop iteration.

So that just meant changing the line

Done and dusted!

Of course, for the official fix I added a unit test and a bunch of comments since Overlapped I/O and I/O Completion Ports are frustratingly touchy.

As a bonus, Guido van Rossum (creator of Python) commented positively on the fix, and eventually we got the fix merged back as far as Python 3.8--the oldest supported version (for security fixes), but also the first version where the ProactorEventLoop became the default.

Basic Callback Hygiene

noreply@blogger.com (Joshua Kriegshauser) — Wed, 05 Jun 2024 15:19:00 +0000

There's a tenet that I've been pushing on for a few years now from my little corner of NVIDIA, and that is the concept of Basic Callback Hygiene.

For the uninitiated, a callback simply-put is a function that I can pass to another function that it will later call to "call me back." A lot of subscription services in programming work like this: Something is going to happen in the future. I want to be notified of it, so I'll call a subscription function and give it a function that it can call to tell me when that happens.

This simple concept gets a lot more complicated when you ask what sorts of things you can do within that callback function. What happens when I don't care about the subscription anymore? What if the module containing the function unloads? What thread is the callback going to happen on? And so on, and so forth.

I've experienced problems with all of these complications over the course of my career, and given the amount of asynchronous and modular code that I've been writing for Omniverse, I finally distilled down a simple set of rules:

Callbacks can ask to be unregistered from within the callback.
Strong recommendation to not hold locks (i.e. a mutex) while calling callbacks.
When a callback asks to be unregistered, there must be a strong guarantee that the callback is not currently being called, nor will ever be called in the future.

That's it. A subscription system that follows these basic principles will avoid 99% of the issues that we typically run into with callbacks.

Let's examine each of these. To put this in practical terms, let's say that we're designing an event system. We can subscribe to an event which will register our callback and we can dispatch an event which will callback all of the subscribers from the context of the dispatching thread (so basically it loops over all subscribers and calls their callback). Our imaginary system is thread-safe, so we can subscribe or dispatch from any thread. We can also unsubscribe to unregister our subscription.

Unregistration from within a callback

This is probably the most useful one. Let's consider the case where I cannot unsubscribe from the callback but I want to. My callback is called and I can handle the event, but I cannot unsubscribe. This particular callback only wants to receive the first event after registration and no more events (an example of this might be a one-shot function that I want to defer until the next frame).

Since I cannot unsubscribe, I must be able to conditionally have a function run later that will then unsubscribe my function outside of the event, and I need to ignore any more events that I might receive in the meantime.

This makes something that should be simple much more troublesome, and every place that I want to do this sort of action now requires more thought, effort, time, testing, etc. Changing the system to allow un-subscription from within the callback means that the complexity of handling that situation is in a singular place: my event system, rather than each and every callback that needs that behavior.

Don't Hold Locks

Holding a lock while calling a callback is dangerous because the callback can execute arbitrary code. The callback may call back into our event system and we don't want the complication of having recursive locks (which are arguably evil) or contributing to lock cycles which can cause deadlocks.

Writing an event system to be thread-safe and yet not hold any locks while calling callbacks is challenging to say the least. Generally this requires something akin to tracking the number of threads that are in the middle of doing callbacks, at a minimum. We typically do it by adding a thread identifier to a list while holding a lock, and then unlocking to call the callback, then re-acquiring the lock and removing the thread identifier from the list. This is more complicated to be sure, and the reason why will be evident in the next section. There are other ways to do it, but you'll need some tracking to maintain state while the mutex is unlocked for the callback.

This also means that how you walk the list of subscriptions must be stateful in a way that can resume after the mutex is unlocked and re-acquired. If these subscriptions are stored in C++'s std::vector for instance, there exists a possibility that unlocking the mutex will allow another thread to subscribe, which may resize and therefore reallocate the vector, which invalidates all iterators; or another thread may unsubscribe which will remove an entry, which can affect the position of the current thread walking over the vector. (Solutions to these, respectively, might involve using indexes instead of iterators, and leaving null pointers in the array to mark empty spaces).

Strong Unregistration Guarantees

This is by far the hardest issue to solve correctly. Here's a real-world scenario: right before a module unloads (in the main thread, say), it tells our Event system to unsubscribe a previously-subscribed callback. Without a strong guarantee, what will happen if another thread is currently calling our subscribed callback? As noted above, we don't want to be holding locks while calling callbacks, so waiting on a lock isn't going to wait for our callback to finish. What has happened in actual code is that the unsubscribe happens quickly, the module proceeds to unload, and then a crash occurs because another thread was still executing a function that was in the module. Or after unloading, objects were destructed since we would no longer get events, but with another thread in our callback function, a crash occurs because deleted memory was accessed.

Or the problem that I'm fixing right now: memory corruption occurs because a dependent structure was freed, but a race with the callback means that we were still changing things inside the structure.

It quickly becomes apparent that any request to unregister must wait for any other calls to finish. Also, once we return from the unregister function, it stands to reason that we cannot ever call the callback again. To do so would be violating the caller's unregistration request.

This then requires a strong ordering guarantee:

Unregister function is called.

WAIT for any calls to the callback in question to finish*.
PREVENT any future calls to the callback.

Return from the unregister function. At this point the caller can guarantee that our event system is free of the callback and it is safe to destroy structures.

"Ah," the astute and observant amongst you might notice, "what if the unregistration is from within the callback?!" This was our first point, above. If we WAIT for any calls to the callback to finish and the unregistration call is coming from the callback, we would wait forever. So we amend the line with the asterisk (*) above instead to say: "WAIT for any calls to the callback in question in other threads to finish."

So our subscription process is pretty simple:

Take the lock
Append our subscription information to the std::vector (or similar)
Unlock the lock

The notification process is a bit more complicated as it has to synchronize with the unsubscribe process:

Take the lock
Iterate over the std::vector (or similar) by index, skipping null entries. For each:

Add the current thread identifier to a list of threads that are notifying.
Unlock the lock
Call the callback function
Re-acquire the lock. At this point, the vector may have been reallocated and grown, and subsequent entries may have been unregistered. Any other thread could have done anything.
Remove our current thread identifier from the list of threads that are notifying.
Is a waiting flag set on the subscription? If so, notify the waiting thread (i.e. using a condition variable).

Unlock the lock

And now, the pièce de résistance: the unsubscribe process:

Take the lock
Find the subscription to remove. If not found, unlock and return; otherwise:
Set the entry in the std::vector to null, but it is not destroyed yet!
Is the subscription currently being notified by a thread other than the current thread? If so, set a waiting flag on the subscription that is used in 2.6 above.
Unlock the lock.
If the waiting flag was set, wait on the condition variable for notification from 2.6 above. Otherwise it is safe to destroy the subscription and return.
Re-acquire the lock.
If the list of notifying threads contains threads besides the current thread go to step 5.
Unlock the lock. It is now safe to destroy the subscription.

This will allow our unsubscribe to wait until no threads are notifying our subscription, or only our thread that is currently unsubscribing during notification.

Of course, there is a lot more nuance to this, especially when it comes to handling recursion (dispatching within a callback) or even just the complexity of working with multiple threads, but this should help you understand the concept of Basic Callback Hygiene.

Resolute Timers

noreply@blogger.com (Joshua Kriegshauser) — Wed, 05 Jul 2017 00:42:00 +0000

This weekend I got linked into a tweetstorm regarding a tool called Set Timer Resolution by one Lucas Hale. People are claiming that using this tool results in better hit accuracy, faster responsiveness and higher frame-rates for King of the Kill and other Daybreak titles.

Seen here, in all its majesty

It looks like other people have said that this helps, and at one point it looks like the download link was removed from the site. At the time of this writing, Download 3K is apparently a valid mirror (MD5: 4b3bccdb3bcbd48162aa77270d910276). I cannot recommend using any specific third-party applications, including this one. Your mileage may vary and incorrect use of software may cause issues.

This specific very simple app (only 32k in size!) does not affect the game in any way shape or form. In fact, it was originally authored back in 2007, way before King of the Kill. Instead, it tells Windows to check it's timers more often. That's it.

Imagine this. You need to do something in 30 seconds, but you only have a clock with a minute hand. You glance at the clock and it says 4:59 pm. Once it changes to 5:00 pm, has 30 seconds elapsed? Not necessarily! What if you glanced at the clock a mere second before it changed? To ensure that a full 30 seconds has elapsed you would actually have to wait until 5:01 pm to guarantee that at least 30 seconds has passed, but up to 1 minute 59 seconds could have passed!

This is the nature of resolution: how often you can check the clock and it will tell you a different value. Now, computers do things a LOT faster than even once a second. Computers can do things in the nanosecond range (1/1,000,000,000 of a second) or even faster! When I started up the Windows 10 machine that I'm writing this post with, the resolution was 15.625 milliseconds (~0.015 sec). That's WAY slower than 0.000000001 sec! In fact, that resolution will only check the clock 64 times per second, which can be slower than some frame rates that people get when playing King of the Kill.

When we do windows programming, when we set a timer or tell a thread to sleep, we specify values in milliseconds (1/1,000 sec), but if it's only checking the clock every 15.625 milliseconds, a 1 millisecond timer can end up waiting 15.625 milliseconds, which is more than a whole frame in some cases. Obviously we want Windows to check the clock much faster than 15.625 milliseconds.

This is about how often I check my phone. And I always forget to check the time.

Yes but does it WORK?

At first I thought this tool might have some confirmation bias behind it, but after digging into it, i'm going to say that it's plausible that it has a positive effect on gameplay. Windows has but one internal timer, and it's shared by everything running on the system. When Daybreak titles start up, we tell Windows that we want 1 millisecond resolution on the system timer. But, to be good software citizens, we tell Windows to set the timer resolution back to what it was when the game is ending. Seems reasonable, right?

Now imagine that everything does that. Say you start up Some App(tm) that sets the timer resolution from 15 ms to 1 ms, then you start up King of the Kill that also tries to set it to 1 ms. However, then you shut down Some App. Thinking that it's a good software citizen also, it sets the timer back to 15 ms. But you're still playing King of the Kill! Now you might see some different behaviors, like getting micro-stutters, and miss hits that should have landed, etc. The game is doing what it's supposed to, but something happened that it didn't expect: the system timer got set back to low resolution. The Set Resolution Timer tool doesn't appear to continually update the Current Resolution display, but I believe it will try periodically to make sure the system timer is at the selected resolution. EDIT: Lucas Hale (the author of SetTimerResolution) commented below to let me know that this assumption is invalid. It appears that Windows will take the maximum resolution requested by any running application. So if the game client requests 1ms resolution, and SetTimerResolution requests 0.5ms resolution, it will take the latter. This is good as it makes the devs' lives easier!

How does Set Timer Resolution work?

This section is not for the technically faint-at-heart. I'm going to wax programmatically on you. First of all, when the game starts up, we call a documented function called timeBeginPeriod with the minimum value reported by the timeGetDevCaps function (generally 1 [millisecond]). This would probably work fine in many cases as long as our game is the only thing running on the machine. But that is never the case. Little programs that do behind-the-scenes things can start and end and do all sorts of stuff. Browsers can be running with multiple tabs open. Streamer software. Video recording software. Etc. If any of those things can affect the system timer while the game is running, then bad things happen.

It looks like Set Timer Resolution goes even deeper than the multimedia functions (like timeBeginPeriod) that our titles are calling. It goes straight to the kernel, the heart of every operating system. It looks like it's calling some undocumented user-mode kernel functions: NtQueryTimerResolution and NtSetTimerResolution. These are likely called deeper down from the multimedia functions that our titles use.

So where do we go from here?

I'd like to make Set Timer Resolution completely unnecessary. Since the game is already trying to set the timer resolution at startup, it seems like we could be doing a better job of making sure it stays set. I'll evaluate this against our current priorities and talk with the team about getting this in an upcoming hotfix.

Boom.

Which patch? Dispatch.

noreply@blogger.com (Joshua Kriegshauser) — Tue, 21 Feb 2017 07:59:00 +0000

**Authors note: I started writing this post a year ago. Hence the references are a bit dated, but the content is relevant.

At the behest of the good people of reddit, I figured I would talk a little bit about a recent issue that cropped up in Planetside 2: a runaway thread in our threading library that went mostly unnoticed and caused reduced performance.

Threads Are Hard

Writing good multi-threaded code isn't easy. I challenge the linked article's author in that multi-threaded programming is actually difficult. Sure, some of it boils down to programmers not following best practices, but there are several other facets that you don't encounter in single-threaded programming:

Synchronization

Reads and Writes to data must be synchronized
Compiler's optimization effect may subtly effect program operation
Lock-less programming considerations
Possibility of dead-locking or live-locking

Non-determinism. This basically means that the program doesn't run the same way every time. This has several repercussions:

Difficult-to-reproduce issues
Testing/error logging can mask issues or create false positives (similar to the Observer effect)
Statistical testing (problems occurring with a low enough frequency that you don't see them until they reach the Live environment)

Woody shares my expression.

However, the availability of hardware is favoring power by having increasingly larger numbers of cores. To take advantage of that power, you need threads.

Concurrency

Threads are a solution to the problem of trying to make a computer seem to do multiple things at the same time. In the olden days, threads didn't exist, but systems could start other processes by forking the process. This would create a copy of the process that could do different things without affecting the parent process. By being a copy, changes that one process made to its memory and variables wouldn't affect the other process. The two processes would still be able to communicate somewhat via IPC, but this is generally much slower than, say, setting a variable within a process.

Like my threads?

But sometimes you want one process to be able to do multiple things at the same time. That's where threads come in to play. Since threads allow multiple things to happen "simultaneously" within the same process, you have concurrency.

I put "simultaneously" in quotes, because multi-processor systems of yore were generally limited to server-class hardware. It was uncommon to find a user's home machine with more than one processor. This means that the system could really only do one thing at a time, but it looked like it was doing things simultaneously because it was switching threads (i.e. things that it was doing) very, very quickly. These days, everything is multi-processor. My house thermostat is probably multi-CPU (ok, not really). The focus in hardware shifted from doing one thing very fast (higher clock speed aka GHz on CPUs) to doing many things pretty fast at the same time. The previous generation consoles (Playstation 3 and Xbox 360) had three to four CPUs whereas today's console generation (PlayStation 4 and Xbox One) have eight. My work computer has 12 "logical" cores.

Early threading involved creating threads for very specific tasks. For example, EverQuest II largely runs in a single thread, but creates specific threads for loading files, talking to the streaming asset server, updating particle effects, etc. Most of the time those specific threads are doing nothing; they're just sleeping. As the number of processors in a system grew, it becomes less practical to have dedicated, specific threads, especially when the number of processors in a system differs from system to system.

Synchronization

Let's take a break for a second to talk about a related topic. Synchronization is a big, huge, gargantuan topic wherein lies most of the problems with multi-threading. I'm only going to say a few words about Synchronization.

Yep, like that.

Nearly everything in the computer system can be considered a resource that must be shared: files, memory, CPU time, DVD drives, graphics, etc. What must be shared must be synchronized so that separate threads don't counter-productively stomp on each other. Process memory is probably the most often shared and problematic resource because everything interacts with it. Something like a file is fairly easy to synchronize because nearly every access of it requires a function call. Memory, on the other hand... For instance, here is an example of a function that just increments a number. What would the value be if you had two threads on a multi-processor machine calling this function 1000 times?

Hint: it's usually not 2000. Surprise! Incrementing a number is not an atomic operation, it's actually a read-modify-write operation. This is one of those things that makes multi-threaded programming so hard! To protect the section of code that increments the number, you have to use some sort of synchronization primitive, like an atomic intrinsic, mutex, spin-lock, or the like.

Tasking

When you have more processors available, it makes more sense to break problems down in to logical tasks or units of work. Instead of having a dedicated thread to load files, now you just have a "load file" task. You have a "collect garbage" task. You have an "animate entity" task. Task, task, task.

Khaaaaaaaannn!!!

This concept of tasks helps you to fill all available processors with work to do. Theoretically, if you can keep the task backlog full, CPUs will always have work to do. If you're using 100% of the available processors, you're doing the maximum amount of work that the system can do.

Dispatch

In 2009, Apple launched Mac OS X 10.6 with a programming API (libdispatch) marketed with the name Grand Central Dispatch (GCD). It is, among other things, a generic task execution system. You have a function or a task that you want to run in the main thread or a separate thread at specific priority levels, immediately or at a scheduled time in the future. You just take that function or task and throw it on a "dispatch queue" and let it run. Simple. Powerful. Efficient. I quickly fell in love with what GCD could offer when I used it for my iPhone game, Bust a Mine.

Fast forward to mid-2014. I became Technical Director of Planetside 2. The team was working on porting Planetside 2 to the PlayStation 4. Performance profiling was showing that the CPUs on the PS4 were slower than average CPUs on our PC players' machines, and Planetside 2 was still largely single-threaded. We started looking at threading technologies like Intel's Threading Building Blocks, OpenMP, and even the C++11 thread support library. However, given my experience with libdispatch and the approach of looking at the problem as tasks rather than dedicated threads, we decided to look around for something similar. We found xdispatch, a port of libdispatch to Windows and Linux (libdispatch was originally written for Mac OS X which is based on BSD). However, it had some issues: namely it didn't support the PS4 (few things did) and was based on a much older version of libdispatch. We began adapting it to the PS4 and it gave us a solid framework to start multi-threading Planetside 2.

Adaptive Tuning

We developed a threading sub-team on the PS4-on-PS2 project that had a primary requirement (increase performance) through two primary points of attack: 1) tune xdispatch to do what we needed and 2) adapt existing threads and operations into tasks that could be done concurrently. Ideally these changes would carry over to the PC version of the game as well.

Both of these facets were challenging. On the tuning front we discovered that part of the reason that GCD works so well on Mac OS X is because the kernel--the core of the operating system itself--is controlling the dispatch scheduling. We didn't have that ability on the PS4, nor could we get the information about how busy the system is! We went several iterations on how to deal with this, but eventually settled on working around this by setting up some guidelines--the standard dispatch queues would only be used for CPU-intensive work (calculation, animation, decompression, etc.) and we would limit them to the number of CPUs available.

The second facet was a much longer pole that would continue throughout the project. Converting existing dedicated threads and PS2's old job-queue system to Dispatch was easy and quickly done, but that didn't net nearly the performance that we would need to see to be viable on PS4. We would have to go much deeper. This would involve taking core aspects of PS2's main loop and breaking them into tasks--entity processing, physics, animation, rendering, etc. This is difficult to do with C++ because non-thread-safe side-effects are nearly impossible to find; we would have to identify everything non-thread-safe that was happening in the single-threaded code before converting it to tasks.

OMG Bugs

That was the song, right?

The reddit post that originally spawned this blog post sheds some insight on to a problem that still existed a year after the PS4 version originally launched. Namely, PC players identified that a thread would take a whole CPU, but they found that if they killed it, performance got better and nothing bad really happened (or was not immediately visible). This was found to be a bug in timers in xdispatch that, to my knowledge, still exists. You can read the above link for more technical information, but it had to do with bad assumptions in the PC port of software originally written for BSD. Shockingly, the problem also existed in the PS4 build even though it shouldn't have. It looks like the timer implementation in xdispatch (and the libdispatch version that it was based on) was functional but not very efficient, so we wrote a new timer outside of xdispatch and used that instead.

Still later, we finally got a handle on one of our long-standing (post-PS4-launch) crash bugs. This was a crash bug that we had never seen internally (see my above point about bugs becoming a statistical problem). It looked like a memory corruption problem, which just made all of the programmers reading this shudder in horror. Memory corruption is terrible. It is an evil problem and few good tools exist to locate it assuming you can figure out how to make it happen. But find it we did, and it was also an issue with converting systems to multi-threading. In this case, an 'animation complete' flag was in a data structure that was getting freed before the task performing the operation finished and set the flag. Since the memory was freed before the flag was set, sometimes the memory had been reused for other things, hence the corruption. This was a problem not with Dispatch itself, but with how a previously single-threaded operation had been converted to a task.

Most recently, we began hearing reports of 'lock-ups' and 'hangs' from PS4 players. This coincided with an update to PS4 SDK 3.500 (from 2.000) for Planetside 2, which, among other things, gave us an additional half of a CPU to use for game logic (with 2.000 the system would reserve two whole CPUs for itself, whereas after 3.000 it only used one-and-a-half). Because of this, we ramped up Dispatch (now a completely retooled version no longer based at all on xdispatch but based on a more current version of libdispatch) to take advantage of that half-a-CPU. Eventually we determined this to be the cause of the lockup, but for unexpected reasons. The game was not experiencing a dead-lock, but a form of live-lock; all of the CPUs were running threads, they just weren't making any progress. This was because of a degenerate case between the design of libdispatch and the PS4 scheduler. Basically, the internals of libdispatch (and our Dispatch library that was based on it) are lock-less--they are doing atomic operations rather than locking mutexes. Some of these atomic operations are loops waiting for conditions to be met, or multiple compare-and-exchange operations in a loop; they try to do an operation based on old information and retry with updated information if it fails. But the PS4 scheduler will not run any thread of a lower priority if a higher priority thread is runnable. We could end up in a state where a lower-priority thread would be preempted after it changed conditions for a higher-priority thread. This would cause a sort of priority inversion that would never resolve. Most operating systems will at least give some time to lower priority threads to prevent starvation, but the PS4 does not. Indeed the default scheduler for the PS4 is the FIFO scheduler, but even the round-robin scheduler will not run lower-priority threads. Our solution to this involved applying a progressive algorithm that would eventually put threads to sleep in extreme cases in order to allow the live-lock to resolve. Generally this might look like a slight momentary dip in frame rate or may not even be noticed at all.

Looking Forward

Make sure your blinker is on.

We're always looking for ways to increase performance across all platforms. As other Daybreak games ramp up we're finding new ways to eke out increasing frame-rates and sharing that knowledge among the teams. Our internal Dispatch implementation is moving into other Daybreak titles and future projects, and it all started here, on Planetside 2. Efforts have been made to keep these types of changes in parity between the different games.

Don't Repeat Yourself

noreply@blogger.com (Joshua Kriegshauser) — Thu, 26 Nov 2015 01:13:00 +0000

Something that I've been working with the Planetside 2 team lately has been a more strategic direction in how we write maintainable code for the future. Part of my direction for this has been adherence to the D.R.Y. principle--Don't Repeat Yourself. Namely, instead of distributing authority out by the expression of Interfaces (and writing a lot of repetitive code), we are architecting unambiguously authoritative systems that can handle all functionality in a common way.

One of our most recent realizations of this principle is in our new UI data-source layer.

Previously, Planetside 2 (and previous Forgelight Engine ancestors) had a concept of a DataSource interface. This was a simple interface that allowed sub-systems (such as Skills or Items) to express data in a string-based row/column format to the UI layer (Planetside 2 uses Scaleform GFx, a Flash-based interpreter/renderer). The Actionscript 3 UI code could find a DataSource by name and query it in the ways expressed by the interface (it could also register as a listener to determine if anything changed).

class IUIDataSourceTable {
public:
    virtual int GetData(int row, int column, String& output) = 0;
    virtual int GetRowCount() = 0;
    virtual int GetColumnCount() = 0;
    virtual String GetColumnName(int column) = 0;
    virtual void AddListener(IUIListener*) = 0;
    virtual void RemoveListener(IUIListener*) = 0;
    virtual void NotifyChanges() = 0;
};

Seems great so far, right?

Because this is an interface, each system is responsible for surfacing internal data to the UI through the GetData call. But each system can implement it completely different. As long as 'output' receives the value of a given cell, where that data comes from isn't important to the UI layer. Also, detecting when that data changed (and notifying listeners) became the responsibility of each system.

Okay... So?

Well, now let's say that you want to do more complex operations with that data, such as sorting, filtering or joining with another IUIDataSourceTable. Sure we could add additional functions to the IUIDataSourceTable, but as our codebase grows, we're faced with a quandary: how do shrinking development teams maintain ever-growing codebases??

Let's look at it a different way. Say I wanted to add a Filter function to my IUIDataSourceTable. Planetside 2 has on the order of about 130 implementations of this interface (give or take) in very disparate systems such as Character Select, Skills, Items, Marketplace, Social, Experience, etc. If I want to add another function to my interface, I'm looking at actually writing 130 functions and doing a lot of research into those systems to find out how they actually surface the data.

This is the problem with distributed authority: it exponentially extends a simple change. Work-arounds in the past involving just two things that we always want to do--filtering and sorting--required either a C++ engineer to add to a specific DataSource implementation, or a UI engineer to gather everything and sort it in Actionscript 3. This is not a very productive or sustainable model and it's ridiculously time intensive (both on the CPU and in development time).

Ok, now let's adopt a don't-repeat-yourself strategy.

Instead of declaring an Interface that each system must adhere to, let's design a system that is unambiguously authoritative in terms of UI data. We want one system that we can tune and add functionality to. And since we're talking about UI datasources, can you think of anything that is designed to store row/column data and has sorting and filtering capabilities? Maybe... like... a database?! Turns out there is such a beast that we can use as the core of our new authoritative UI data system: sqlite3! This gives us a light-weight, in-memory SQL database that we can use to store our data and slice it any way we need! And better yet, browsers (and even mobile devices) have been using it for years!

After getting an engineer excited about this prospect and putting her on the project, she turned out an awesome system called uiDB that exposed game data to the Flash-based UI through SQL and tables. This has some really cool features:

Adding new functionality is trivial. We just added some very broad functionality in less than a day because we changed one authoritative system instead of 130 interface implementations.
sqlite has a callback mechanism, so we can use Actionscript 3's event mechanism to notify the UI when data changes--automatically. C++ just updates the game data in the uiDB system as it changes, and the authoritative uiDB system notifies any listeners. No extra code required.
The AS3 code can create a view to slice, sort, filter, or join data however it wants and can still get notified when any of that data changes. Without having to write any additional C++ code.
The AS3 code can also perform any SQL query on the in-memory UI database whenever it wants. Need data one time? No problem. Need to display data and refresh when it changes? Equally trivial.
We wrote a DataProvider implementation for uiDB tables and views. This is the standard DataProvider that Flash widgets use, so our UI engineers don't have to write any code to handle change events or anything--the DataProvider can do all of that and the UI just updates automatically. Talk about code reduction!

Another surprise out of changing from the interface to authoritative model is that our UI data performance increased, even though we were now using a SQL-interpreting database! This is because of a few different reasons:

In the Interface model, each system retrieved its data through different means. Some could be woefully inefficient.
sqlite3 is a well-tested, highly optimized, tightly-packed, small C library. It has a development team that cares only about its performance and functionality in a variety of settings. As such, we are gaining the wealth of knowledge and experience of another team focusing intently on one piece of technology, allowing us to focus on making a game. (This could branch into another discussion about utilizing as much third-party technology as makes sense).
By consolidating authority in one system instead of spreading it out, we had one target to focus on for performance testing and optimization.

We are continuing to provide additional functionality through this system to our UI engineers in order to make their lives easier (and we're doing this across the board for all disciplines). This is looking forward to the future of Daybreak Games and the Forgelight Engine as much as the future of Planetside2.

All in all, work smarter, save time across the board, and don't repeat yourself!

By the Library of Thor!

noreply@blogger.com (Joshua Kriegshauser) — Mon, 30 Jun 2014 07:36:00 +0000

I recently uploaded to github a C++ template library called Thor, which is something that I've been playing around with. It's really just a way for me to write some crazy template code--a creative outlet if you will. This blog post is meant to show off some of the things that I'm proud of in Thor. The name Thor came in part because of inspiration from Andrei Alexandrescu's template library Loki and his book Modern C++ Design (an excellent advanced C++ book).

Some things in my Thor library are just me implementing things in the way I would if I had full control, and some are a slightly different take on popular concepts. Some things are already outmoded based on offerings in C++11 (especially in terms of atomic support), but are included for posterity.

I apologize that the code samples are images (Blogger currently doesn't do well with template syntax), but generally a link is provided to the code on github.

Containers

The C++ standard library includes several standard, well-known and well-documented containers, however these containers don't often allow for much customization. For instance, std::vector (up until the C++11 standard) had no obvious means to free memory (C++11 adds the shrink_to_fit() function). Although not technically correct, I'll refer to the C++ standard library as STL below for brevity's sake.

thor::basic_string

Thor's string class works very similarly to std::string and std::wstring with a few changes. First, the strings are atomically reference counted, so the underlying string data is shared when possible. Secondly, a template parameter can be specified to pre-reserve (as part of the basic_string instance, not a separate heap allocation) space for the string. The default of zero is a fully dynamic string, but if you need a quick string on the stack and don't want to allocate anything from the heap, it is easily done with the addition of a size template paramter:

Furthermore, in addition the STL constructors for basic_string, additional options are available for printf-style formatting and literal strings (that don't require copying or allocation):

The printf-style formatting is also supported for append, insert, replace and assign variants.

Thor's string also supports conversion between UTF-8 and "wide" (wchar_t). If wchar_t is 32-bits, then the conversion will be between UTF-8 and UTF-32, however the more likely case is that wchar_t is 16-bits, in which case the conversion will be between UTF-8 and UTF-16, complete with support for UTF-16 surrogate pairs.

thor::list

In general node-based STL containers (such as std::list) will allocate a 'dead node' or a terminator node from the heap as soon as they're constructed (even default constructed). Usually this terminator node will include space for the 'T' stored type, although that space will never be used and therefore wastes space. I frown upon the fact that wasted space is allocated from the slower heap for such a simple operation as default constructing a list.

Consider Thor's list class. Instead of heap-allocating a terminator node, the head/tail pointers for the list class use a list_node_base and the address of the list_node_base is used as the terminator. Thus, the terminator (used by the end() iterator) is implemented as such:

This has the advantage of not requiring a heap allocation for the terminator node while still allowing for simple reverse iteration and no need for null-pointer checking at head/tail. However, there are two disadvantages. The first is that any accidental writes to the end() iterator (which is completely invalid anyways) may cause memory corruption. This can be prevented in checked/debug builds with asserts when trying to dereference the end() iterator. The second is that swap semantics require slightly more finesse (although these are more complicated in Thor for another reason explained below). In std::list the swap() function must only exchange pointers and counts between two lists--since the terminator node is allocated on the heap it is not tied to either list and is automatically part of the swap. However, since Thor's list essentially has a local terminator node as part of the instance, care must be taken to fix up the terminators during swap:

Notice that the swap function handles a concept of shareable. This is because of another enhancement of Thor's containers. Essentially, space for a certain number of items can be pre-allocated along with the container, similarly to the string class mentioned above. For instance, thor::list<T,5> specifies that no heap allocations must occur for the first five list entries. Fortunately, thor::list<T,5> inherits from thor::list<T> so that it can be used anywhere where a list is required. However, it also means that the problem of swap() now must handle pre-allocated nodes. It is less efficient to swap() a list with pre-allocated nodes as this requires the nodes be converted to heap allocated nodes.

There are many other extensions to all of the containers, yet they all try to remain true to the C++ standard library specification.

thor::hash_map (et al)

The thor::hashtable class (which forms the basis of hash_map, hash_set and the multi- versions of each) has a noteworthy feature: a policy class that controls how the stored values are organized into buckets. The options are a power-of-two system that is very fast by using bitwise masks instead of divide/mod instructions (although this method can be terrible for pointers as keys as they typically are multiples of 4 or 8 and the bucket strategy loses efficiency leading to collisions), or a more traditional (and slower yet less collision-prone) prime-number strategy.

The C++ standard library hash containers are undefined order containers. This means that the order in which you insert items is not necessarily the same order in which you would iterate over the items. However, thor's hash containers are a fusion of a list and a hashtable, which allows for a defined iteration order as well as amortized O(1) lookup time. This does require a slight change to how iteration starts: the begin() function defaults to 'list' iteration mode but can be changed to 'hash' iteration mode, whereas find() operations default to 'hash' iteration mode.

Embedded Containers

For std::list (or thor::list for that matter), the 'T' type that you're storing in the container is contained within a node that tracks other information for the container. If you had a list of pointers to objects in the heap, then the objects were allocated and the list container must allocate a small node to store the pointer. This is wasteful. The embedded containers can alleviate this by having the node tracking information as part of the object that is being stored. For instance, the 'T' type stored in a thor::embedded_list must contain an embedded_list_link member and the member is given as a template parameter to thor::embedded_list.

Atomic integer/pointer

The thor::atomic_integer system is similar to C++11's atomic wrapper, so while not completely necessary it was a fun exercise to write. The real meat of how it works is based in the platform-specific interlocked system (the Windows version is interlocked_win). This uses template specialization to handle one-, two-, four- and eight-byte integers. By using intrinsics, these atomic_integers actually compile down to very few inline instructions for most operations. Consider how declaring interlocked works on a platform with a 32-bit integer. First, some magic happens based on how the non-specialized interlocked class is declared. There is a second template parameter that is required, but defaults to sizeof(T):

The template parameter T_SIZE defaults to 4 for int, which causes a specialization to be selected:

This specialization uses the correct functions/intrinsics for the numeric type that we're wrapping in atomic_integer. This allows atomic_integer to do the correct operation based on size of the integer parameter:

Memory Alignment

Another place where Thor uses template specialization is with memory alignment. All of the containers do memory allocation through Thor's memory functions. There is a simple class called the align_selector:

This class's only job is to determine if an object can use system-guaranteed alignment or not (most objects can). If the system alignment will suffice, alignment_selector::alignment will be zero. The align_alloc class uses the align_selector as a default template parameter to select the proper specialization for the alignment:

The system default alignment just allocates raw bytes:

But the default version that handles non-default alignments will over-allocate and offset:

Arguably, this version could use _aligned_malloc or memalign or similar, but by using new[] an application may still override new and use their own memory manager if so desired.

There is a lot more to the Thor library. Take a look at it on github and let me know what you think.

Busting Mines

noreply@blogger.com (Joshua Kriegshauser) — Thu, 15 May 2014 23:12:00 +0000

Behold: Bust A Mine. My first iOS development project.

Not a bad run!

Inspiration

When I set out to (once again) try my hand at iOS development, I didn't know what the future would hold. It was around the time that a former game that I worked on, Clone Wars Adventures, had announced that it would be ending on 31 March 2014. One of my favorite mini-games in CWA was called Mine Buster, a simple game that involved creating a chain reaction for points. It was also a mini-game that would soon cease to exist. And a good mini-game that could use a Spiritual Successor.

Beginnings

I started working on my own rendition in early March while professionally employed as the Director of Technology at Molten Games. Within two weeks of late-night spare time I had a working prototype that functioned similarly to its inspiration. I had heard good things about using Cocos2D 3.0 and it seemed to fit the bill. My prototype was still very rough and could only run on the iOS Simulator that comes with Xcode 5. However, I was happy enough with the progress that I decided to spring for the iOS Developer Program so that I could actually run and debug on my iPhone and iPad. There was a little learning curve to overcome as running code on the device requires creating App Identifiers, Certificates for code signing and Provisioning Profiles for signed code to be allowed to run on the device. Being able to run and debug on my devices was instantly gratifying, but also revealed another issue: the need to deal with different screen sizes (iPad vs. iPhone) and aspect ratios.

Artist Wanted

It was time to start finalizing the art--getting real assets at the necessary sizes and building out the art style. For this, I'd actually need an artist. Fortunately, Molten's UI artist was on-board with the project after seeing the prototype running on my phone. He had free reign with the art style and created a look inspired by the likes of Geometry Wars yet unique in its own right. We worked together to integrate the art into the game and iterate on the style. Unfortunately, Molten Games collapsed around this time, towards the end of March. Priorities shifted to finding a new day job since this project was a journey of Experience and less of Business.

To Test or not to Test

Working with an artist brought to light another need that I'd have to figure out: distributing test builds of my app to other people. For this I began using Test Flight. This provided a great way to bring testers on board and get feedback. The only issue was minor: when a new device was registered, I would have to add the device's unique identifier to the provisioning profile and upload another build of the app. I started acquiring testers with a broad spectrum of devices. I also acquired a few devices of my own: non-Retina iPad and older iPhone. I was also blessed with winning an iPad Mini in a contest! I made sure to also test on the newer 64-bit devices. Through this I actually discovered some 64-bit compatibility issues with Cocos2D 3.0 (in beta at the time) and worked with the developers to solve them.

Sprechen Sie Deutsche?

I can understand exactly one of these.

Having visited Moscow and Shanghai for assisting Planetside 2 localization (and working on games for the past decade or so), I'm constantly reminded of the worldwide gaming community. The English-speaking community might be easier for me to market, but it's a small part of the world. Therefore, I wanted to make sure that my app could be distributed and popular in other locales. I had a very small number of strings (less than 100), so professional localization would be fairly easy. I originally started working with Rev.com but found them difficult and obtuse. I ended up going with e2f and found them slightly more expensive, but very easy to work with. They appreciated all of my contextual notes and turned around six languages (French, Italian, German, Spanish, Russian and Simplified Chinese) in less than 24 hours. In hindsight, I should have included a few more items in the translations, such as future (generic) update notes and anything that I would potentially need in the next few months.

Finishing Touches

This game, since it was an exploration of experience, was going to be free and advertisement-supported. However, given the ease of doing in-app purchases, I would offer an in-app purchase to remove the ads. I also wanted GameKit integration to essentially have free Leaderboards. Fortunately many kind developers have written simple APIs around these pieces of functionality and have shared them for free. Integrating the likes of ABGameKitHelper and MKStoreKit was very easily done. My testers also suggesting graphical features such as using UIMotionEffect to simulate a parallax display on iOS 7+.

A Different Beat

Having some manner of background music was important to me. However, I'm not a composer. I don't really know many composers. So I started looking for free music. Interestingly, though, "free" isn't always free. Some companies let you use their music for free for certain purposes, and an app is not generally one of those free uses. I originally wanted to use some songs from Freeplay Music, but after seeing their licensing requirements and reading about their litigation processes, I decided against it. I ended up using music by Chris Zabriskie who offers his music for free with a Creative Commons Attribution license. I feel that his music meshes well with the peaceful, soothing nature of Bust A Mine's laid-back gameplay.

Pre-Launch Checklist

I've heard of using a test market to pre-launch, so I figured I'd give that a try. I have some friends with family in the Philippines and it seems to be a fairly popular test market. Launching in the Philippines also revealed an interesting fact: iAd isn't available in all parts of the world. Therefore, my advertisement strategy would have to change for a worldwide launch.

3... 2... 1... Liftoff!

Bust A Mine officially launched in a limited capacity on 9 May 2014, about 9 weeks after development started. Considering that it was my first foray into iOS development and Objective-C programming in general, I'm calling that a success. Not a business success, but an experiential success. For the full worldwide launch, I'm waiting for Apple to approve the next version that will integrate Google AdMob as a backup to iAd.

To Infinity and Beyond

The background reverberates with explosive force

I really enjoy iOS development. The Objective-C language allows for easy checking to see if features are available on the device it's running on. Furthermore, the Xcode integration with Apple back-end services is very well done and easy to use. Want GameKit integration? Flip a switch and you've got it.

Several people have asked about an Android port as well. Interestingly, no one has asked about a Windows phone version. In any case, I'm considering a port to Cocos2D-X, a C++ library that supports all major mobile platforms.

I've got plenty of ideas for Bust A Mine for the future. And a few of my game designer friends have offered some feedback and ideas of their own. Plus, I have more ideas for future games as well. Mobile development has become a fun little hobby for me.

Download Bust A Mine and give it a try. Leave a review or rating if you feel so inclined. And let me know what you think in the comments!

Githubbing

noreply@blogger.com (Joshua Kriegshauser) — Wed, 05 Feb 2014 07:11:00 +0000

I just created a repository on github.

https://github.com/jkriegshauser/fastjson

For a while I've been writing a json parser (fully RFC-4627 compliant) similar in interface to rapidxml as a fun way to write some simple code that ended up being fairly complex. I mean, there's a good bit of template partial specialization in there, exception/non-exception handling, Unicode support, unit-testing, etc.

It even figures out if you've given it UTF-8, UTF-16 or UTF-32 and whether the endianness matches your machine or not.

Yeah, so that's how I have fun. Enjoy, universe!

Catching Fire

noreply@blogger.com (Joshua Kriegshauser) — Fri, 22 Nov 2013 02:46:00 +0000

Well, it happened.

Nearly two months ago I took the plunge and left Sony Online Entertainment to be the Director of Technology at Molten Games. Molten is a small but well-funded and growing start-up in the San Diego area.

I. Am. Having. A. Blast.

We're building a rock-star team and making a great game. I can't wait until I can talk about it, but you're going to have to stay tuned for a bit.

Getting Ripped

noreply@blogger.com (Joshua Kriegshauser) — Wed, 09 Jan 2013 07:59:00 +0000

For the past few weeks I've been converting my DVD and Blu-ray Disc (BD) collection to MP4 format so everything can be easily viewed on the Apple TV. Generally, this has been fairly painless (especially for DVDs), but there is one thing that I desire that most people probably don't care about: captions.

Maybe I'm getting old, but for about a decade I've preferred to watch shows with captions. There are basically three types of captions present on DVD and BD media:

Closed Captions - text-based captions that may include hard-of-hearing information.
Bitmap Captions - bitmaps that are overlaid on the screen.
Forced Bitmap Captions - technically a subset of (2). Typically shown for foreign languages.

Bitmap Captions allow the DVD/BD publisher to ensure that captions look the same on every player, whereas text-based Closed Captions can look and perform differently on different players, TVs, etc. And in my experience, Bitmap Captions don't display on the Apple TV whereas Closed Captions will. Also of note is that DVD and BD each use a separate type of Bitmap Captions--VobSub for DVD and PGS for BD.

Now, if Bitmap Captions don't show on the Apple TV, why do I care about them? There are two main reasons: 1). If Closed Captions don't exist and 2). Forced Subtitles.

At this point I should mention that I'm using Handbrake to encode my movies for the Apple TV. Several pages exist as guides to using Handbrake, so I'm not going to cover it in much detail, except for dealing with captions.

If Closed Captions Don't Exist

If a DVD has Bitmap Captions (VobSub) but no Closed Caption, then we need to find a way to add text-based Closed Captions. Fortunately, there are a few options.

The first option is my least favorite. Handbrake has the ability to burn-in Bitmap Captions. This means that captions will be present, but there will be no way to turn them off. For all captions, that's not desirable, but as seen below it can be quite handy for Forced Captions.

The second option is to find a SubRipper (SRT) file that someone has created. Fortunately there are some great crowd-sourced resources for this, like Open Subtitles and my personal favorite, SubScene. These sites allow you to search for a SRT file that someone has created and uploaded. Handbrake can import the SRT file by using the Import SRT button (seen in the picture above). The downside to this method is that timing is everything. There can be Special Editions and Director's Cut versions of the movie you're searching for, so ensuring that you have the correct file will involve using Handbrake's Preview feature or using a player (like VLC Media Player) to preview before encoding. Otherwise you could end up with captions that don't match.

The final option is to create your own SRT file from the Bitmap Caption. This can either be done manually (VERY time consuming) or with the aid of OCR software. This was more of a last resort for me, but I did do it for a few of my DVDs. I used a program called Subresync. It is about as naive as OCR software can be, essentially asking the user the first time it encounters a specific pixel pattern:

Forced Captions

This is where things get a bit trickier. Forced captions were typically not a problem for DVDs as all of my DVDs that used Forced Captions actually had them burned in to the video stream. Not so for my BDs. A good example is Star Trek VI: The Undiscovered Country where the Klingon speech is a Forced Caption track and is not burned in to the video stream. And Forced Captions are something that everyone should want as they are essentially part of the movie.

Also complicating this process is the fact that Handbrake does not yet understand PGS-style Bitmap Captions (the system used for BDs). Therefore, the PGS (or 'Sup') Captions must be converted to VobSub before using Handbrake. This involves the following steps:

I use MakeMKV to get the BD data on the hard disk in MKV format.
Load the .mkv file in the mkvmerge tool from MKVToolNix. This will tell you which tracks contain PGS Caption data:

In this example, IDs 2, 3, 4 and 5 contain PGS subtitle data. Leave this program open as we'll come back to it if we do indeed find Forced Captions.
Extract the subtitle data using mkvextract on the command line:
mkvextract tracks Star_Trek_VI...mkv 2:sub2.sup 3:sub3.sup 4:sub4.sup 5:sub5.sup
This will extract tracks 2-5 into files sub2.sup, sub3.sup, sub4.sup and sub5.sup
Open each extracted PGS Subtitle file using BDSup2Sub to see if it contains Forced Captions. In the Star Trek 6 example, we find that track 3 contains nothing but Forced Captions:
Since we've found Forced Captions, we need to convert them to a format that Handbrake understands. Fortunately, this is what BDSup2Sub was designed to do. File->Export gives the following dialog (make sure that 'Export only forced' is checked):

Interestingly, VobSub is made up of a .idx text file and a .sub binary file.
Now we need to add the newly created VobSub captions and re-mux into a new .mkv file. Go back to the mkvmerge that was open from step 2. Click the Add button and select the new .idx file that was created in step 5, then press Start Muxing:
When the muxing finishes, you can now load the new .mkv file up in Handbrake and burn-in the Forced Captions:

Qapla'!

Getting captions to work correctly on the Apple TV with custom-encoded movies can be a bit tricky, but if you're hard-of-hearing or just used to using captions, hopefully this guide can help you.

New Domain!

noreply@blogger.com (Joshua Kriegshauser) — Wed, 02 May 2012 19:17:00 +0000

Well, I've finally gotten around to registering joshuakriegshauser.com. It's about time. Which means that this blog will appear at blog.joshuakriegshauser.com.

Oddly enough, kriegshauser.com is considered a premium domain and is listed for about $1600. I honestly hope whoever is holding it never gets that.

1 in 600,000

noreply@blogger.com (Joshua Kriegshauser) — Fri, 06 Jan 2012 06:03:00 +0000

For Christmas this year, my wife gave me (among other things) Another Tough Puzzle. This puzzle claims that "with millions of wrong solutions, the chance of solving this puzzle is ONE in 600,000!"

There are 16 triangular pieces and each piece has three connections each being one of four possible shapes. The completed puzzle should be a pyramid with six connections on the edges pointing in and six pointed out.

The puzzle also claims that "it looks easy...but just when you think you've solved it, the last piece proves you wrong." This is very true and very frustrating. I (and others) played around with the puzzle for a while always ending up with one piece that didn't fit.

Then I thought, "I write software for a living; why don't I do that here?" I've enjoyed writing solvers in the past (my Minesweeper solver would actually play the GUI for you on previous Windows versions). I mostly use C++, so I decided to use it here as well. Certainly there are languages more suited to rapid development, but I'm a glutton for punishment.

The first step was to describe the pieces. We noticed pretty quickly that half of the pieces have two outward-facing connectors (outputs) and one inward-facing connector (input) and the other half are opposite (two inputs and one output). There are no pieces with three inputs or outputs.

enum FaceType
{
    eFaceTypeClover = 0,
    eFaceTypeHeart,
    eFaceTypeSpade,
    eFaceTypeDiamond,
};

enum Direction
{
    eDirIn = 0,
    eDirOut,
};

struct Node
{
    FaceType face;
    Direction dir;

    bool fits(const Node& rhs) const
    {
        return face == rhs.face && dir != rhs.dir;
    }
};
struct Piece
{
    Node node[eNumSides];

    Piece(FaceType in, FaceType out1, FaceType out2, bool)
    {
        node[0].face = in;
        node[1].face = out1;
        node[2].face = out2;
        node[0].dir = eDirIn;
        node[1].dir = node[2].dir = eDirOut;
    }
    Piece(FaceType in1, FaceType in2, FaceType out)
    {
        node[0].face = in1;
        node[1].face = in2;
        node[2].face = out;
        node[0].dir = node[1].dir = eDirIn;
        node[2].dir = eDirOut;
    }
};

Using these structures, all of the pieces can be declared:

Piece pieces[eNumPieces] =
{
// one input, two outputs
Piece(eFaceTypeSpade, eFaceTypeDiamond, eFaceTypeHeart),        // 0
Piece(eFaceTypeHeart, eFaceTypeDiamond, eFaceTypeSpade),        // 1
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeSpade),       // 2
Piece(eFaceTypeClover, eFaceTypeSpade, eFaceTypeHeart),         // 3
Piece(eFaceTypeSpade, eFaceTypeHeart, eFaceTypeClover),         // 4
Piece(eFaceTypeHeart, eFaceTypeSpade, eFaceTypeClover),         // 5
Piece(eFaceTypeSpade, eFaceTypeClover, eFaceTypeDiamond),       // 6
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeHeart),       // 7

// two inputs, one output
Piece(eFaceTypeClover, eFaceTypeDiamond, eFaceTypeHeart, true), // 8
Piece(eFaceTypeClover, eFaceTypeDiamond, eFaceTypeSpade, true), // 9
Piece(eFaceTypeHeart, eFaceTypeDiamond, eFaceTypeSpade, true),  // a
Piece(eFaceTypeHeart, eFaceTypeClover, eFaceTypeDiamond, true), // b
Piece(eFaceTypeHeart, eFaceTypeClover, eFaceTypeSpade, true),   // c
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeHeart, true), // d
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeSpade, true), // e
Piece(eFaceTypeSpade, eFaceTypeHeart, eFaceTypeDiamond, true)   // f
};

Now that the pieces are all set up, the gameboard must be described. The end result should be a pyramid made up of all 16 pieces (see diagram). Therefore, I had to describe how the pieces relate to each other in the gameboard. This will allow the solver algorithm to test that a piece 'fits' if its connectors match the adjacent pieces. In order to do this, each position in the desired puzzle shape is marked with a number and each side of the triangular pieces are numbered as well. The sides are always numbered clockwise starting at the horizontal side so that adjacent pieces in the puzzle have sides matching (for instance, pieces 7 and 8 both share their side number 2).

The array of PieceLoc structures define how each piece relates to adjacent pieces:

PieceLoc locs[eNumPieces] =
{
// Sides:     0               1               2          // Pieces
PieceLoc(eInvalidPiece,  eInvalidPiece,              1), // 0
PieceLoc(            7,              2,              0), // 1
PieceLoc(eInvalidPiece,              1,              3), // 2
PieceLoc(            9,              4,              2), // 3
PieceLoc(eInvalidPiece,              3,              5), // 4
PieceLoc(           11,              6,              4), // 5
PieceLoc(eInvalidPiece,              5,  eInvalidPiece), // 6
PieceLoc(            1,  eInvalidPiece,              8), // 7
PieceLoc(           12,              9,              7), // 8
PieceLoc(            3,              8,             10), // 9
PieceLoc(           14,             11,              9), // a
PieceLoc(            5,             10,  eInvalidPiece), // b
PieceLoc(            8,  eInvalidPiece,             13), // c
PieceLoc(           15,             14,             12), // d
PieceLoc(           10,             13,  eInvalidPiece), // e
PieceLoc(           13,  eInvalidPiece,  eInvalidPiece)  // f
};

The fitting function is recursive. The first time it is called it has all 16 pieces remaining to try and fit. It loops through all remaining pieces rotating them in all possible positions each time checking to see if the piece fits. If the piece fits, it calls itself again this time with 15 pieces remaining. When a pieces is found that fits, it calls itself again with 14 pieces remaining. And so on, and so forth until all pieces have been used. If a piece doesn't fit, it goes on to the next piece. If a solution is found or no more pieces fit, the function returns and tries the next piece.

Since we only have 16 pieces, I use a bitmask to determine which pieces are already used.

void FitRemaining(int remain)
{
    if (remain <= 0)
    {
        ShowSolution();
    }
    else
    {
        int index = eNumPieces-remain;
        for (int i = 0; i < eNumPieces; ++i)
        {
            if ((used & (1 << i)) == 0)
            {
                used |= (1 << i); // Mark in-use
                pieces[index] = i;
                for (int r = 0; r < eNumRotations; ++r)
                {
                    rotation[index] = r;
                    if (validate(index))
                    {
                        FitRemaining(remain - 1);
                    }
                }
                pieces[index] = eInvalidPiece;
                used &= ~(1 << i); // No longer in-use
            }
        }
    }
}

The last part is the validation function. We really only need to validate the most recent piece added. Figuring out which sides are facing each other is the most difficult part, but even that is pretty easy. Because of how the gameboard is organized we already know that side indexes on adjacent pieces always face each other. All we need to do is take the rotation into account and ensure that the shapes match:

bool validate(int piece) const
{
    assert(piece >= 0 && piece < eNumPieces);
    const Piece* cur = Get(piece);
    int rot1 = rotation[piece];
    const PieceLoc& fit = locs[piece];
    for (int f = 0; f < eNumSides; ++f)
    {
        const Piece* p = Get(fit.neighbors[f]);
        if (p)
        {
            int rot2 = rotation[fit.neighbors[f]];
            if (!cur->node[(rot1 + f) % 3].fits(p->node[(rot2 + f) % 3]))
            {
                return false;
            }
        }
    }
    return true;
}

That's all there is to it! I probably spent less time writing this program than manually (and frustratingly) trying to find the solution.

In fact with this program I found all 518,469 solutions to the puzzle. Here's the first one:

If you'd like the full C++ source: Go here.

GDC Online 2011

noreply@blogger.com (Joshua Kriegshauser) — Thu, 21 Jul 2011 21:44:00 +0000

I haven't done a speaking engagement since LOGIN 2009, but I really enjoyed it, so I figured it was high time to give it another shot.

(And no, acting out Beyoncé's Single Ladies dance on stage at the Developer War Stories panel of Fan Faire 2011 doesn't count.)

I've always enjoyed attending GDC Online (formerly GDC Austin or Austin Game Developers' Conference) and since it has always catered to a large crowd of online game developers (and I do miss Austin a bit), it's as good as any a place to foist my shenanigans on the somnolent audience.

This year I'll be talking about the trials and tribulations of taking a square peg never designed for streaming, EverQuest II and inserting it into a round hole. If you've read this blog, I've mentioned things about this before, but this is your opportunity to see the veil ripped away and the nitty-gritty of the good and bad choices that were made.

If you're heading to GDC Online (and you should for this lecture alone!), click here to see the lecture in their Schedule Builder.

Also (and completely to my surprise), Gamasutra listed my lecture as a 'highlight' of GDC Online. Fortunately they don't know me that well yet. ;D

Philosophy of Code

noreply@blogger.com (Joshua Kriegshauser) — Fri, 01 Apr 2011 01:09:00 +0000

Programming in a business environment requires creating a product or service that is intended to produce a higher profit than cost. However, I believe that few programmers understand this or think about it on a daily basis. At the end of the day, we must be working towards making a profit.

I'll be the first to tell you that I'm not a business major. I'm not an economist. I love programming and was best friends with a keyboard in the third grade. I can write code like the dickens but I'm no Wizard of Business. However, throughout the past year working on Clone Wars Adventures I've had time (while my code is compiling) and inclination to reflect on the nature of programming in a business environment.

I've basically come to the conclusion that programming is a balance of three distinct yet intertwined facets: Developer Efficiency, Code Correctness and Performance. I call this the Philosophy of Code:

Performance - How quickly the code executes.
Developer Efficiency - How quickly developers are able to complete tasks.
Code Correctness - Adherence to best practices (avoiding global memory, avoiding macros, namespaces, templates, etc.).

These three aspects are not necessarily mutually exclusive. Every programming task that we work on has some balance of the above. However, when evaluating this philosophy from a business perspective, I've come to believe that the most important element of the triad is Developer Efficiency. Developing a Philosophy of Code that puts emphasis on Developer Efficiency will allow your programmers (and incidentally your entire development team) to work faster and smarter. It can also require less code to be written and fewer bugs.

Mutual Exclusivity
In some cases, an Efficiency-based Philosophy of Code will compromise the Performance and Code Correctness aspects. For instance, EverQuest II has a console-variable system. With one line of code in an implementation file I can add a semi-constant: a named value that can be changed by typing a slash-command into the chat window:

CV_FLOAT(max_radius, 30.0);

Presto. This is like saying float max_radius = 30.0; but I can also change it in real-time by typing "/max_radius 25" into the chat window. This typically is frowned upon from Code Correctness aspects for a few reasons:

It uses macros
It uses global memory
It causes code to execute before main()

If your Philosophy of Code leans towards Code Correctness, doing it the Right Way™ would entail at least:

Creating a manager object as a member of your application manager class
Writing explicit code to register a member of your class with the manager object
Writing explicit code to unregister that member when your class instance is destroyed
A lot more than one line of code

Leaning towards Code Correctness over Developer Efficiency in this case would require that your programmers spend more time writing code and compiling (since members are typically declared in header files) to accomplish a very simple task.

Compile Times
In some cases, Code Correctness philosophies can institute policies that work to the detriment of Developer Efficiency:

Extensive use of templates
Excessive class declarations
Lack of forward declarations

Excessive templatization typically means that header files are included in more places and more code is written in header files. When header files are changed, they require more of the code to be rebuilt. More code written in header files can also contribute to longer link times.

Time spent compiling and linking can't necessarily be taken at face value. As programmers wait for a rebuild they tend to do something else which probably takes longer than the rebuild. The shorter the rebuild time, the more likely the programmer is going to stay focused. From a Developer Efficiency perspective, it's in your best interest to keep compile times as low as possible.

Code Bloat
The less code that is required to perform a task, the more efficiently a developer can implement said code. I'll give another practical example from EverQuest II. I've previously mentioned a bit about how the designer data system works. Every server-side data file uses the same data format. As such, no special code is required to load each type of file. Weapons, quests, characters, everything is all defined by the same generic data description language. To load data from any data file uses a simple interface:

DataObject* pObject = DataLoader::Load("weapons/sword_of_awesomesauce");
if (pObject->IsA("Weapon"))
{
  String name = pObject->GetField("Name").AsString();
}

Due to data object inheritance, pObject may actually be a Sword, but inherits from Weapon. The server's object model is further generified so that instantiating any object requires just providing the type:

Item* pItem = ObjectFactory::Spawn(Item::Type, "weapons/sword_of_awesomesauce");
if (pItem && pItem->IsA(Weapon::Type))
{
 // Successfully spawned and is actually a Weapon.
}

In other words, there is very little code that needs to be written to add a new game object type.

Conclusion
Programmers should consider their Philosophy of Code. I believe that focusing on Developer Efficiency in a business setting makes the most sense given the deadlines, the complexity of the tasks at hand, and the goal to make a profit.

Debugging information cannot be found? No Problem!

noreply@blogger.com (Joshua Kriegshauser) — Wed, 23 Mar 2011 16:50:00 +0000

In my last post, I discussed the frustrations of Visual Studio 2005 (and later versions) not being able to locate debugging information, even though it was present and fully usable by other tools.

I believe I have discovered a workaround that works nearly all the time: Remote Debugging.

It turns out that running the Remote Debugging Monitor on the same machine and setting up the project to use Remote Debugging seems to work around whatever issue Visual Studio is experiencing.

Remote Debugging is really useful if another machine is experiencing a problem that you can't reproduce locally. The Remote Debugging Monitor is primarily intended to run on a different machine than Visual Studio, but can also run on the same machine.

Here is how to set up Remote Debugging:

Generally, the machine running the Remote Debugging Monitor will need the files. These are found under the Visual Studio install location: C:\Program Files (x86)\Microsoft Visual Studio 8\Common7\IDE\Remote Debugger\x86 (for 32-bit) or C:\Program Files\Microsoft Visual Studio 8\Common7\IDE\Remote Debugger\x64 (for 64-bit).
Copy the files from the above directory to the machine that will run the Remote Debugging Monitor (skip if you are running the Monitor locally).
To start the Remote Debugging Monitor, run msvsmon.exe. If you are running locally, there should be shortcuts in the start menu:
Configure the options if necessary. Take note of 'Server name'.
Configure your project to do Remote Debugging. Change the 'Debugger to launch' to 'Remote Windows Debugger'. The 'Remote Server Name' must match the 'Server name' configured above if using Windows Authentication. If you are running the Monitor on a remote machine, the Remote Command and Working Directory will be paths on the remote machine.

When you Start Debugging, Step Into or Step Over to start debugging the application, Visual Studio will now connect to the Remote Debugging Monitor. You should be able to verify this by looking at the Remote Debugging Monitor and seeing how many connections it has.

So far this appears (for me at least) to be a successful work around to the 'Debugging information for 'X.exe' cannot be found or does not match. No symbols loaded.' error message. There have only been about two times in the past month where a problem occurred. In those cases, a restart of Visual Studio (and killing mspdbsrv.exe) fixed it.

Please let me know if this worked for you!

The (current) Bane of my Existence

noreply@blogger.com (Joshua Kriegshauser) — Fri, 04 Feb 2011 01:23:00 +0000

Yes, Microsoft Visual Studio 2005, I'm looking at you.

Whenever I try to run the Clone Wars Adventures AdminClient in the debugger, I have about an 80% chance of seeing this:

This is a debug build. I most assuredly have debug symbols turned on:

And I'm not the only one to ever have this problem. People have also reported this problem on VS2008.

Oddly enough, no one else on my team has been complaining about this problem. When I start VS2005, I can generally run the client in debug once or twice and then I perpetually get this error.

Sometimes, exiting VS2005 and killing mspdbsrv.exe followed by a restart of VS2005 usually allows me to run a couple more times. However, with our huge solution (112 projects), this takes a few minutes or so. Definitely not conducive to small changes.

Some of the links above have responses from MS folks who state that they aren't able to reproduce the problem, but there is most definitely a problem.

I've only experienced this problem on our internal AdminClient, which, unfortunately, is the project that I'm most often trying to run. Other projects in the solution file seem to work just fine. I've tried several suggestions from the above links, including others like replacing dbghelp.dll with the latest version, altering the symbol search paths, trying to manually load symbols, and so on.

As a last-ditch effort, some of the links above suggest re-installing VS2005. I'll give that a shot.

If that doesn't work, I may have to become a Pirate or something.

Update: (3/23/2011): I believe I have found a work-around by using the Remote Debugging Monitor. More info in this post.

Ladies and Gentlemen, we are LIVE!

noreply@blogger.com (Joshua Kriegshauser) — Wed, 15 Sep 2010 14:14:00 +0000

(Read the title in your best Bruce Buffer voice).

My new game, Clone Wars Adventures, is now LIVE and out of Beta! It's free to play and easy to download so head on over to the website and check it out!

Open Beta!

noreply@blogger.com (Joshua Kriegshauser) — Sat, 28 Aug 2010 05:01:00 +0000

My new game, Clone Wars Adventures, is now in Open Beta! Head on over, create an account and let us know what you think on the forums (must sign in with your Station name)!

Finally!

noreply@blogger.com (Joshua Kriegshauser) — Tue, 01 Jun 2010 16:48:00 +0000

We just announced the new game that I'm working on. Finally I can talk about it!

So, without further ado:

This is a new online free-to-play PC game targeted to kids (and adults) due out this fall. It is built upon the technology first developed for Free Realms. It will be largely mini-game based allowing things from Lightsaber Dueling to Speederbike Racing, the obligatory Starfighter missions and even a 3D tower defense game called Republic Defender. However, there is still a large social aspect with friends, housing, leaderboards and even a kid-friendly Facebook-inspired profile page.

On a personal note, this is a great project to be on. I am a huge Star Wars geek (over 15,000 LEGO bricks in my office representing different Star Wars ships) and my son loves Star Wars and the Clone Wars (and, incidentally, this game too!).

I hope you enjoy the teaser site and video. I look forward to actually being able to show in-game demos (*ahem* E3 *cough*)!

Update 6/1/2010 1:47PM PST:

/resurrect iPhone

noreply@blogger.com (Joshua Kriegshauser) — Thu, 15 Apr 2010 07:51:00 +0000

I broke my iPhone 3G. Again.

A few months ago I dropped it in the supermarket. It landed flat on the screen and when I picked it up I was horrified to discover a spiderweb-shaped crack in the screen. Fortunately, everything still worked. For $70 I had it repaired at Volt Mobile. They did pretty good work, but the touchscreen was intermittent (I'd have to flex the phone to make it work again).

Last week, I dropped it again. This time the touchscreen was completely broken--I couldn't even turn the phone off or enter my passcode to do a backup.

This time, I figured I'd try my own repair. Hey, it's worked in the past.

A quick look online shows several places that sell digitizers (touchpads), LCD screens, batteries, you name it. I ended up going with a digitizer sold from AccessoryOne (which purports to be OEM) for less than $20 shipped and taxed. There is also a three-part video series on cracking open the iPhone and swapping out the digitizer. The videos are made by http://www.directfix.com/ who also have parts but tend to charge a bit more.

This blog basically chronicles my repair. If you're doing this yourself, watch the videos; they're much more informative. Also, there is no guarantee that this will work, and it will void your warranty (mine has already expired). I just figured that I'll be upgrading to the 4th-generation iPhone when it comes out anyways.

The first step was pulling out the screen assembly. Two screws from the base (near the speakers) are all that is holding the screen assembly on. Unlike the videos, I used a suction cup on the screen near the home button to pull the screen out. I believe this works better and doesn't molest the rubber seal around the screen assembly. This picture shows the screen assembly removed from the base:

This picture shows the new digitizer/glass on the left top, the removed LCD screen on the left bottom and the old frame/digitizer assembly on the right bottom:

Removing the LCD screen is tricky and must be done carefully. I've read posts from people who crack their LCD screens at this step and it's a much more expensive component. I was very gentle.

The digitizer that I ordered was just the glass/digitizer combo; it didn't include the screen frame or the components that are mounted to it (speaker, skin sensor, home button, etc). Therefore, the frame must be removed from the original glass/digitizer and attached to the new one. This was probably the most tricky part. It involves using a hair dryer to weaken the glue and pry the frame off. Then new two-sided tape must be applied to the frame and attached to the new glass/digitizer.

This picture shows the removed frame (bottom center) and the old cracked digitizer on the bottom right:

After a few minutes of work, the frame was attached to the new glass/digitizer:

The new glass had an appropriate amount of protective film, so it was fairly easy to minimize dust getting in between the screen and the glass. The new screen assembly with LCD installed is now shown on the bottom:

After getting the screen cables connected I powered on the phone and was able to enter my passcode to unlock the phone (note that the protective film is still on the screen, hence the sticker in the middle of the screen):

Yay! All-in-all, a very successful repair for under $20 and about an hour.

Now... to find a better case...

Be Careful with Default Arguments

noreply@blogger.com (Joshua Kriegshauser) — Tue, 16 Mar 2010 06:08:00 +0000

CRC16::computeMemory( const char* data, unsigned length, uns16 crc = 0 );
CRC16::computeString( const char* data, uns16 crc = 0 );

This little gem caused quite a headache. Allow me to explain.

EQII's streaming client uses 16-bit CRCs to tell if an asset has changed. All 500,000 individual assets have a 16-bit CRC calculated and stored in the master asset list (manifest). When an asset is downloaded, it is cached on disk and stored with the 16-bit CRC. To save time, the client doesn't calculate the CRC on each asset that it downloads, it just uses the CRC stored in the manifest.

Every time the client runs, we download the manifest and check the CRCs in the manifest against the stored CRCs for our cached assets to see if any changed. If an asset has changed (the CRC is different), we delete the cached copy and request the replacement, even if it's not immediately needed.

When the streaming client launched, everything worked as planned. It worked great! Little did we know that a particularly evil bug was lurking.

I discovered a problem when I wrote a utility to convert old PAK files (the game data shipped on the DVD) to cached streaming assets. NOTHING matched the CRCs in the manifest. Every asset was wrong. I looked over the code several times and everything looked fine. This bug didn't make sense.

And then it hit me.

The code that was building the manifests was doing this:

uns16 crc = CRC16::computeString( data, dataLength );

Talk about /facepalm. The function I meant to call was CRC16::computeMemory(). The function I actually called treated the input like a null-terminated string. This means that the CRC was only calculated up to the first NUL character and the dataLength parameter was actually being treated as a starting CRC value. This was a bug that had to get fixed. Someday, perhaps many years from now, this would be a huge bug that would waste a lot of someone's time to hunt down.

Oh, but the fun doesn't end there. I couldn't just change the function to fix the bug. Doing that would mean that every streaming client user would have to re-download everything that they had already downloaded. Every CRC would change and the naïve client would happily delete everything and start over. To fix this properly would take a highly-synchronized effort to fix and push the manifests while deploying a one-time-only tool that would re-calculate the CRC for all assets that people had already downloaded.

The moral of the story: be careful with default arguments. They can really hurt if misused.

Evolution of a Streaming Client

noreply@blogger.com (Joshua Kriegshauser) — Wed, 10 Feb 2010 03:35:00 +0000

It's funny how many things in the game industry start out as "I wish..."
... I wish we had Guild Halls.
... I wish we had Shader 3.0 support.
... I wish we had Battlegrounds.

... I wish our game was easier to download.

It's equally funny how many things are started by people in their own time just trying to make the game better. That's how EverQuest II's streaming client started out.

Taking an existing game (with 12GB of client assets no less) and streaming it is no simple task. I started off with a "proof of concept" just to prove that it could be done with EverQuest II. As I got into it, the concept became a full fledged project. It wasn't officially on the schedule, so it was really a labor of love on my part. After a few weeks of silently working on it, I called the producer into my office and said, "Hey, check this out." Needless to say he was pretty surprised.

There are three major conversion steps for a streaming system.

Serving the assets

EverQuest II has roughly 500,000 client-side asset files: meshes, textures, collision meshes, shaders, data files, sounds, music, you name it. Have you ever tried putting half-a-million tiny files in a directory? Take my word for it: Don't.

My first inclination was to build a custom server. The server would run off of the PAK files that we already ship with the DVD-based game client. I had grandiose plans about how to track files that clients were downloading and automatically send assets to clients that they didn't know they needed.

But alas, it was not to be. A custom server means that every client would have to be talking to our server. We would have to think about where to place the server geographically, handling varying load characteristics, availability, bandwidth, etc. These were all questions that had already been answered; we didn't need to ask them again and try to come up with our own answers.

What else is great at serving files to a large number of clients all over the world? Web servers! Specifically, HTTP servers. We already used a CDN for patching purposes--we just needed to serve all the game assets individually and on-demand now.

This caused another wrinkle. The client needs to know a list of all the assets that are available and whether the assets that it has previously downloaded are out of date. We call this the "manifest." This manifest must be fully up-to-date before the client tries to load ANY assets. My custom server knew how to negotiate a manifest with the client in a fairly bandwidth-friendly way because it was smart. CDNs are less smart--they just serve files. EQII's manifest is about 6MB, which you definitely don't want to download every time you run the game. The solution I developed involves parts of the manifest available as separate files and an overarching CRC file that is requested first. The CRC file is always requested, but it's only about 8KB. Based on comparisons with the CRC file, the client reconstructs the full manifest by grabbing parts that it needs.

Requesting the assets

Compared to everything else, serving the assets is the "easy" part. Requesting the assets is far more difficult. You're essentially replacing file system access with a network connection. That sounds a lot easier than it is. File system access is inherently goverened by the Operating System and allows any thread to open nearly any file and read data from it. A network connection is a single pipe (or in our case, a collection of pipes) that must well-defined and tightly-controlled access. Any thread that could just expect to read from a file at any point must now be synchronized with other threads requesting assets from a network resource.

Another major difference is that file system access is synchronous from an application's perspective. This means that while waiting for the Operating System to read data from a file, the thread goes to sleep and allows the system to do other things. Generally this happens so quickly that you barely notice, but network connections aren't nearly as fast as your local hard disk. For this reason, we want most of our asset requests to be asynchronous: we send the asset request and go about doing other things until it finishes at some later time.

Unfortunately, it's much easier to do synchronous reads than asynchronous. The EverQuest II client had many synchronous reads that you didn't even notice because the file system is fast enough. If they weren't made asynchronous, a streaming client would appear to 'lock up' while waiting for an asset to be fetched. Obviously, this is undesirable, and nearly unavoidable in some cases.

Furthermore, network connections in games are usually given time by the main thread to do their work (colloquially referred to as "pumping"). That won't work in this system. What if the main thread needs to synchronously load an asset (which still happens occasionally, especially on client startup)? It would be waiting for an asset to finish loading and wouldn't be able to update the network connection that it is effectively waiting on.

Clearly, a system is needed that can pump itself. Any thread can request an asset synchronously or asynchronously and the network connection continues updating as long as the client is running. The system should be able to determine if a request for an asset has already been sent and we don't need to waste bandwidth by requesting it again. The system should be able to recognize and quickly send higher priority requests. And, oh yes, let's not forget about failure cases. This piece of technology is the very heart of the streaming client.

Storing the assets

Obviously, once an asset has been downloaded, we don't want to waste bandwidth downloading that asset again. It might take minutes to enter a zone for the first time, but we don't want to take that long every time we enter that zone. Therefore, that asset must be stored locally.

A possibility is to store each asset as its own file, but this fails in practice. Operating Systems are not optimized for hundreds of thousands of tiny files. No, these files must be stored in a larger file, packed together and easily accessible.

EQII already has a packed file format. Unfortunately, the way it's set up does not lend itself to modification. When EQII's packed files are written, they're never intended to change. With new assets being downloaded constantly, these files will be changing, and often.

My solution was to develop a new type of asset database specifically suited to our needs. These database files can store a large number of tiny assets, rapidly add and remove assets and quickly retrieve individual assets.

Other Considerations

The most difficult part of building a streaming system for an existing client has been trying to change synchronous asset requests into asynchronous. Consider the following simple example:

Animation* pAnim = pAssetSystem->LoadAnimation( "animation/player_anim1" );
if ( pAnim )
{
    // Do something with loaded asset
}

The above example would need to fetch player_anim1 synchronously. Changing this to be asynchronous might look like the following example:

Asset<Animation> anim( &myAnimLoadHandler );
pAssetSystem->StartLoad( &anim, "animation/player_anim1" );
...

void AnimLoadHandler::OnLoaded( Asset<Animation>& a )
{
    // Do something with loaded asset
}

There's much complexity missing from the second example, but the point should be clear: making something asynchronous is much more difficult than making something synchronous.

Conclusion

Working on the streaming client was one of the most fun projects that I've ever worked on in a technical sense. It was challenging, but the results are a huge payoff.

Dr. Laura: Dr Jekyll and Mr. Video Gamer

noreply@blogger.com (Joshua Kriegshauser) — Wed, 11 Nov 2009 19:54:00 +0000

Dr. Laura has a video blog about a man who plays video games for his down time:

Now, I actually enjoy reading most Dr. Laura articles. Her common-sense approach to most family psychology issues provides both entertainment and self-reflection.

However, sometimes she's just a little too old-fashioned for me. She seems to come off in this video as entirely anti-video-game. I'll grant that the guy mentioned in the video is acting like a complete idiot, but not all video games are bad. Consoles like the Wii consistently encourage family gameplay.

Maybe it's just because I'm in the video game industry, but if a guy wants to play video games for his downtime, that seems fine. Of course, you have to look at your priorities. Personally, family comes first. Always. I will usually sit down to play games after the rest of my family has turned in for the night. If the rest of the family is napping, occasionally my son and I will enjoy LEGO Star Wars or some other innocuous game.

Everything in moderation, but please don't demonize all video games because some idiot guy can't put down the controller and spend time with his family.