Press "Enter" to skip to content

RPG Hacker Posts

What the Bug?!? – Episode #1: Stupid and the Beast

Welcome to what (hopefully) could become the first ever on-going series on this blog. In “What the Bug?!?”, I want to share my experiences with certain bugs in games (and sometimes other software) which, in some way or another, I consider particularly remarkable. This can mean many different things. These bugs could be quite severe, sneaky, well hidden and difficult to find, dumb, or even just plain funny. (I know, I’ve more or less promised a blog post about my experiences working on Darksiders Warmastered Edition a while ago, but there are so many things I want to say about it that I didn’t find the time and motivation yet – plese remain patient). Today, I want to talk about not only one, but actually two bugs I’ve experienced just recently while facing the beast (C++) – one of those totally being my own fault. (Hence the “stupid”) ( ͡° ͜ʖ ͡°)
Both of the bugs occured on our current (unannounced) project, a port of an older game, have to do with the evil nature of C++ and were particularly hard to find.

So for roughly the past two weeks, I’ve been working on migrating the code of our project from an old Havok version to the most recent one. If you don’t know me, let me tell you that I’m not a huge fan of big middleware when it comes to porting games. Middleware certainly has its place, even in game development, but when it comes to porting an old game, it can very easily become a pain in the ass. In most cases, the API of middleware changes a lot over time, so the older the game you’re porting, the more you have to adjust its code to get the middleware back running. Most of the time, staying on older versions of the middleware in question isn’t possible, either, because those old versions usually don’t support the new systems you’re trying to port the game to, and more often than not, you don’t even get full access to the middleware’s source code, so you can’t even port everything yourself (which is actually a legit solution sometimes – e.g. for Darksiders, we actually ported an old version of Scaleform to different systems rather than trying to switch to a newer version of Scaleform). So long story short, for our current project, we need to migrate to a newer version of Havok and this has taken away quite some time already and caused a bunch of problems.

The first of these problems had to do with memory allocation. If you’re not into game development, memory allocation might be a problem you don’t often have to bother with. Even if you’re among the relatively few people (outside of game development) who are still programming software or libraries in C or C++, it’s likely that malloc() and free() or new() and delete() are all you ever really need to use. For games, on the other hand, this is quite different. Especially in the case of console games. When developing games for consoles, there is a good number of reasons why standard memory allocations may not be enough for you.

  1. On some consoles, they may not even be (fully) supported (though this mostly affects older consoles, I think).
  2. RAM on consoles is very limited and you generally want to have some control over what is loaded into memory and where. This problem is certainly getting smaller and smaller the further into the future we get, but since 4K is also becoming a thing now, requiring higher texture resolutions, we’re still far from the point where the amount of RAM in your console is trivial.
  3. For certain things, there may be certain memory requirements. For example: when decoding videos, there may be a requirement for where in RAM your video frames should go and how the memory should be aligned.
  4. Even performance can be a huge factor. For example: certain memory areas could use different memory buses with different speeds, so when performing a task that needs to access a huge block of memory very often, it may be favorable to put that memory into an area with a faster bus.

Long story short, when developing games, chances are high that you’re going to use your own memory allocators, and naturally, middleware designed specifically for games is aware of this fact and also uses custom memory allocators (usually with some means of hooking your own allocators into them).

For the project we’re currently working on, we’ve set up Havok to use a free list memory allocator with a memory block provided by the game. If you don’t know how a free list allocator works, here is a short rundown: it maintains a linked list of elements representing free memory blocks (usually located at the start of said blocks) where each element has a pointer containing the address of the next memory block that is “free” (or null, if there are no more free blocks left). Now whenever you allocate some memory, the allocator looks for an element in the list pointing to a memory block that is large enough for your request (some allocators maintain multiple lists for different block sizes to make this easier and faster), then returns the address to that memory block and removes the element from the list. When you free that memory again, the allocator adds the element back to the list.

Getting back to our first bug now. This bug was a hard crash that always occured in the same location after a certain amount of allocations via this free list allocator. Havok tried to request a certain number of memory blocks from this allocator and upon iterating its free list, the allocator came across an element that was very clearly pointing to an invalid memory block, making the game crash trying to read from it. Inspecting the different elements in the linked list, one fact quickly became apparent: the element pointing to the invalid memory block was located at a very supicious address itself. Most elements in the list had addresses somewhere in the range of 0x6XXXXXXX. This particular element had an address very far away in the range of 0x9XXXXXXX. This memory clearly didn’t seem to belong to the allocator, so it was time to find out how it got there. This actually turned out to be quite tricky. Even with address space layout randomization deactivated, that one suspicious list element always ended up at a different location, making it impossible to just use data breakpoints on it. My only idea here was to use conditional breakpoints with a very generic condition of address >= 0x90000000 && address < 0xA0000000. If you’ve ever used conditional breakpoints, you know how slow these things are. This certainly didn’t help getting closer to a solution. On top of things, after stepping into this rabbit hole for quite some time, it all just led me back to the beginning: into the same allocation function where the crash had occured in the first place. Unfortunately not very helpful.

Corrupted Free List
This is what you might see in Visual Studio 2015

However, tracing the events in my head, I started thinking something along the lines of “well, if a memory allocation is where the game crashes, maybe freeing some memory is what actually causes the crash”, and believe it or not, this line of thought actually led me straight to the answer. Placing a conditional breakpoint in the allocator’s free function revealed the code location where this faulty element was actually added to the allocator for the first time.

So what happened? Something quite remarkable, and this is where some of the evil nature of C++ comes into play: operator overloading. Surely, operator overloading is one of the coolest and most useful features of C++. For example: when writing your own vector class, overloading its math operators to make common math operations more readable and more intuitve makes perfect sense. It doesn’t stop there. C++ is very flexible and even lets you overload things like cast operators and new/delete operators. The latter is where it gets interesting, but also quite dangerous.

You see, as mentioned above, for middleware it’s quite common to evolve their APIs over time, and in the case of Havok, one of the APIs that was greatly affected by this was the memory API. You could go so far as to claim that the memory API was basically completely rewritten at some point. While doing so, the devlopers of Havok probably figured that it would make sense to overload the new and delete operators of all their classes so that calling them would actually use their own memory allocators. That’s exactly what they did. Now unfortunately, there probably was a minor oversight by them in this regard and this minor oversight in rare cases can actually lead to quite some trouble: they forgot (or decided against) overloading the placement new operator of those classes as well.

A placement new, if you’re not familiar with C++, is basically a new that only constructs an object in a certain memory location rather than also allocating memory for it. This is meant for storing objects in memory you’ve already allocated rather than leaving memory allocation up to the new call itself. Now to be fair, this alone might not be a major issue and I’m not even entirely sure if the blame here is on the Havok developers or on the original developers of the game, using Havok code in unintended ways. It’s probably both to some extent, and it also required a second change by the Havok developers, related to reference counting, to ultimately cause this bug.

Getting to the point: the original developers of the game decided to rely on placement news, coupled with their own memory blocks, for creating some of their Havok shapes, yet they also decided to rely on Havok’s reference counting to dispose of these shapes. Apparently, this worked just fine using the original version of Havok, but upon switching to a newer version, this actually made the game crash in in the way described above. If you followed what I’ve been talking about just now, you can probably see where this is going, so I’ll try to be short: when creating Havok shapes, the game places them in its own memory buffers using placement new, but for destroying these shapes, it relies on Havok’s reference couting, which internally is set to just call delete on any object it destroys. This will make use of the overloaded delete operators on those classes, which are set to route all delete requests through Havok’s memory system. This means that when deleting objects this way, Havok’s memory allocators will try to reclaim the memory used for them. At least in the case of the free list allocator, there doesn’t seem to be any validity check for reclaiming memory, so the allocator just inserts it into its linked list and tries to reuse it later. Since in this particular case, this memory doesn’t actually belong to the free list allocator – it belongs to the game – and the game actually reuses and overwrites this memory later at some point, it’s just a matter of time before this leads to a certain crash. That’s exactly what happened and finding this bug took more than a full day. Certainly not the longest I’ve ever spent searching for a bug, but long enough to start feeling a bit of despair.

Tom & Jerry Bomb Trick
It’s a metaphor

Whew, this was quite a lot of text to explain that one bug. I wish I could have made it more graphical and less dry. And we’re not even done yet. There is still a second bug left to talk about, so I’ll try to keep it short. This time, the blame is entirely on me, so there’s even something to laugh about! ;-)

One of the biggest new features in C++ compared to C surely was the introduction of classes and inheritance. A powerful tool that can help you achieving certain things faster, but that also comes at its price and with its own set of dangers. For those reasons, our philosophy is to only use certain C++ features scarcely. Of course you don’t always have full control over this. When porting an old game or when using middleware, you get what you get, and Havok in particular relies heavily on inheritance and polymorphism. From my experience, the latter is one of the most dangerous aspects of object-oriented programming and is exactly what we try to avoid when there are good alternatives, but sometimes you just roll with it.

Back to our port: while migrating the code to the new Havok version, there was a situation where a virtual function had been removed from a Havok base class, but was still present in its derived classes, and the game actually called this function via a pointer to a base class object. By now, we’ve found out that the original developers of the game had actually edited their Havok source code (which they had full access to, unlike us), so in hindsight, it’s entirely possible that this function had never been part of the base class to begin with and that the original developers just hacked it in there. Whatever the case, this function was now missing from the base class, yet we still had to get the game to compile with the new Havok version somehow.

This is the part where experienced C++ programmers can point their fingers at me and take a good laugh, but being the naive and inexperienced programmer I am, I decided to just hack this function into one of the Havok headers. Now this isn’t something I usually do (nor recommend doing), but when already working on a game with a mess of a code base (certainly the case here), and especially when working on a tight schedule, you sometimes dare and decide to pull a “what could go wrong”. Well, in this particular case, we found out rather quickly “what can go wrong”, although again we had to invest more than a day into a needless bug hunt. To be fair here, had we compiled Havok entirely from source, I might have gotten away with my impatient header hack, but we were linking against pre-compiled Havok libraries here, so… yeah, repetition is not recommended.

Corrupted V-Table
A simple setup to reproduce this effect

So what exactly was the problem? Well, it turned out that upon changing that one header, I had completely fucked up the virtual function pointer table of a class, so upon trying to call one of its virtual functions, the application actually jumped into an entirely different function, making the game crash due to incompatible arguments. To be honest, I’m not sure if I had ever found this solution all by myself with my current expertise, despite the symptoms being rather suggestive (mostly because by the time the bug occured, I had already forgotten about my header hack). Thankfully, my boss has been in the industry for way longer than me (a few decades by now), so as a team effort, finding the problem’s source didn’t take as long as it could have.

Corrupted V-Table in Debugger
Be suspicious whenever you see something like this
Watch V-Table in Debugger
Visual Studio lets you inspect the V-Table of objects directly – useful for finding problems

This post has gotten really long and I apologize for this. I wish I could have spiced it up some more with imagery, but I can’t really think of anyhting else relevant to the topic, so this will have to do for now. If you have stuck here until to the end, you certainly deserve a medal and my gratitude. I hope you could at least find some enjoyment from reading this and maybe even learn a thing or to (I know I have). If you did, I would certainly love to see you again on this blog for future posts. See ya!

Leave a Comment

Future Website Plans

Hey there!

If you have read my previous news entry here, you should probably know what’s going on. The short story is that, due to technical problems, I was recently forced to overhaul and clean up my website a bit. I’m not completely done with that yet (still planning to switch to a different theme and clean up some of the outdated pages).

Anyways, all of this got me thinking. Isn’t it kind of a waste that, right now, all I’m really using this website for is the occasional news post every one or two years and a download archive for some of my old (partially obsolete) stuff? Yes, it is. So with that, how about I actually use this website more, now that I’ve gotten rid of multi-language content and made it easier to use?

With that, I got the idea to actually use this website more like a blog by posting news entries more regularly. Some of the topics I am thinking about:

  • Video games in general
  • Video game development (both from a hobby and a professional/job perspective)
  • Programming in general
  • Hobby projects
  • Real life stuff (only when considered interesting enough by me)
  • Probably more

For the near future, one of the things I’m planning is to actually write a lengthy and detailed blog post about my experiences with the development of Darksiders Warmastered Edition. Not only do I consider it a potentially interesting read for other people, but it’ll also be fun for myself to look back in a few years and remember everything that’s happened during the development of some of my past projects. In that sense, you could see these blog posts as some kind of historical preservation for myself.

So if any of this sounds interesting to you, be sure to check back here occasionally so you don’t miss anything.

Leave a Comment

Hello Darkness, My Old Friend!

Well, here we are again, more than a year after that last post (time sure does fly) and, as you may have noticed, this website looks vastly different now.

So a lot has happened recently. My good old friend WYE (yep, that WYE), who has access to some of the webspace on this server (being one of the admins on smwhacking.de, which is also hosted on this server), is currently in the process of developing an entirely new website + forum for SMW Hacking. For ease of development, he decided to manage his soure code via GitHub, a smart move. A somewhat less smart move was to accidentally leak our mySQL database password on that same GitHub repository. Needless to say, the password had to be changed everywhere.

After doing that, I noticed that this website was suddenly broken and inaccessible. Naturally, my conclusion was that the password change had somehow broken the website. I looked for a solution for a good while until I finally decided to contact my server provider. They told me that the servers had recently been upgraded from PHP version 5.3 to version 5.6.

Being the dork I am, I still wasn’t able to put two and two together and kept looking for problems related to the password. Eventually I discovered the debug mode setting of WordPress, which displays usefull error information when something goes wrong. Now finally I started to realise that there wasn’t anything wrong with my password at all, but that the problem had to do with Wordpess all along. The natural assumption here is that the upgrade from PHP 5.3 to 5.6 somehow broke my website, but I didn’t notice it until the problem with the password occured, making me think that the password itself had been the source of the problem.

So after doing some digging, it turned out that the two major problem sources were two things I’ve wanted to get rid of, anyways: the qTranslate plugin and my custom website theme. As mentioned in my last post, maintaining a website in two languages is kinda annoying, so I’ve wanted to get rid of the German part for quite a while now. This problem gave me the perfect opportunity to do so (I hope I haven’t missed any bilangual pages). I also wanted to get a more modern and dynamic website theme, which I now have (although I don’t plan for this to stay the actual theme for a long time, I just went with it since I considered it the least likely to cause any additional trouble). So with this, the first step of my website overhaul is actually done now, and with German out of the way, nothing is standing in the way of posting here more regularly (except for, well, time and motivation).

Next, after finding a more suitable theme for my website, I’m planning to look through some of my old pages and clean them up (removing pages that are out-dated, adding pages that are missing etc.). Also need to update my Portfolio with my most recent project: Darksiders Warmastered Edition.

Stay tuned for more news on this.

1 Comment

*Some Dust off the Surface Blow*

*One Eternity Later*

WOW, it really has been an eternity, hasn’t it? As you may have noticed, it’s been quite a while since my last activity on this website. This is due to a number of reasons. First of all, I rarely have time to work on private stuff nowadays, and when I do, I usually lack the motivation to do something with this website. Usually I’m lazy, but even when I’m not lazy, I prefer to invest my time into programming. Secondly, I’m not really happy with this website’s design anymore. Mostly with the fact that it’s so outdated and static. I’d prefer a more dynamic website, making full use of the potential of modern browsers. At the very least, the website should resize itself depending on monitor size. For this, I may have to use someone else’s WordPress theme as the tools I know lack the functionality to export themes with that capability (and I certainly lack the experience, time and motivation to design a theme from scratch myself). So basically, I want to redo this whole website, but don’t have the time and motivation to do so right now. Thirdly, maintaining website content in multiple languages is really time-consuming, especially when you want all your content to fulfil certain quality criterias. For this reason, I may very well drop multi-language support alltogether. After all, I expect every person visiting this website to have at least a basic understanding of the English language, which is everything needed to understand the content on this website. Multi-language plugins for WordPress are pretty nasty to work with, anyways.

To get an idea of what kind of website dynamics I’m going for, you can check out my Portfolio page here (or by clicking on “My Portfolio” in the navigation bar). That website is also more regularly updated, so you may get a rough idea of what I’ve been up to lately.

I’ll let you know when I make progress with this website.

Leave a Comment

ZED Released

Yeah, it took forever and at this point you probably didn’t even expect it to happen anymore, but the past week I actually took the time to polish my first Games Academy project ZED and put it on my website.
Grab it here!

Now the only thing that still remains is Amazing Tetris. Let’s see when I will get to that…

Leave a Comment

Looking for Musicians

My first own game, Amazing Tetris, is nearing completion and I am now looking for musicians.

Screenshot

Amazing Tetris is a regular Tetris clone with a few gimmicks programmed in Pascal using Allegro.pas. It was our Computer Science team project 2012 at school; now I’m reprogramming my team mates’ parts and also improving a few things for the sake of being able to call the game “my own” and to host it on my site. It is mostly compliant with the official Tetris guidelines and therefore in the current version feels a lot like Tetris DS. There is, however, still one important thing left: The music.

Currently Amazing Tetris uses the music and sound effects of Tetris on Game Boy as a placeholder. Since I want to avoid potential copyright issues I’ll have to replace those resources before releasing the game. Free legal sound effects are pretty easy to find on the internet, but that’s not the case with music. Therefore I’m looking for a musician to help me out with the game’s music. What I need are mostly a few tunes for the menu as well as some gameplay music, including a Remix of Korobeinki. If you are a good musician and interested in helping out or if you know another good musician please contact me.

3 Comments

Website Updated

I’ve just updated this website. I cleaned and completed all of the pages and also added new ones. Enjoy!

In other news, I recently started programming in C++ since Pascal is outdated and it’s hard to find any useful libraries for it that are still maintained. Porting my project from Pascal to C++ could take quite a while, though.

EDIT:
Now with a new theme and updated software.

Leave a Comment

My Artworks

I can’t really call myself an artist, but being forced to take art lessons for at least one year in 12th grade I actually painted a few pictures. Considering how much I dislike art, I think they’ve actually turned out pretty well.

Time Travel
This one is about time travelling. I bet you recognise that space ship, eh?

Eternal Moonwalk
This one is about Michael Jackson. The term “Moonwalk” was taken quite literal here. Instead of Michael Jackson I drew myself, as that was the task for this picture.

Anyways, I’m glad I’m done with art now. Forever!

EDIT:
Here is my final picture for art lessons (for real this time). First the template:

Dog Pic Template

Now the actual picture:

Dog Pic

SUPER SPECIAL AWESOME, no?

Leave a Comment