Collaborate on Project

[Arklon]

Well, I have an odd job that you could maybe help me with. I'm investigating the weirdest/best bug ever discovered in OP2:

If that looks familiar, it's because it infamously originally happened in Swarm.

Here's what I've been able to determine so far:

• The tileset overwriting only occurs in 1.3.4. With 1.3.5, it simply crashes. This apparently has to do with a new bug you introduced with the double unit limit hack (more on that later)
• It is most definitely related to adding too many units (over all time, not all at once) FightGroups - and it's specific to FightGroups, not plain ScGroups (so ex. TakeUnit, a function inherited from ScGroup, doesn't have anything to do with it apparently). The data that overwrites the tilesets appears to be DestWaypoints structs. The offending code seems to be either within the virtual function "ScStub_Group_CombatBase_???4" (in the OllyDbg comment file, function is at 0x4286D0, vftable entry is at 0x4CFF34) or a function that it calls - I determined this by hooking the vfunc and just outputting debug messages before/after calling the real function. When the game crashes, it does not make it as far as returning from the function. I am pretty sure that this function gets called every game cycle along with all the other processing functions but I might be wrong since I didn't actually look at the game loop code.
• What area of memory actually gets overwritten is random-ish - not surprising, as the things it overwrites are heap-allocated. It's not 100% random, but it seems to pick between several different areas of memory to screw up (per mission run, not randomized every tick), including tilesets and the actual map itself, and which area is most "favored" depends on several factors that I haven't been able to fully determine.
• When tilesets get overwritten, first white lines appear, then after all tiles have been covered in white lines it begins overwriting the tileset's palette data, and things start to look very... interesting, especially with the various lightlevels
• If it chooses anything other than tilesets to corrupt, it invariably results in a crash or freeze. If tilesets or the map are overwritten, the crash invariably happens after some multiple of 64 (2^n?) units has been created (in the case of tilesets this happens after every tileset has been overwritten). It's possible to delay crashing if map data gets overwritten by making the game window small.
• Whether you are running on XP or Vista+ affects it, presumably due to the new memory manager in Vista+. It can have some effect on the palette corruption, but the most profound effect is on which area of memory is chosen to be corrupted. For example, in both XP and Vista+, on Swarm.map (a 64x64 map), it very reliably overwrites tileset data, but slightly less reliably with Vista+; whereas with Axen's Home (512x256), it always crashes on XP, but works semi-reliably on Vista+.
• Assuming tilesets get overwritten and the mission is playing out exactly the same, the corruption, colors and everything will be consistent from test to test - but on rare occasions (has to do with what other programs you are running?!), the color pattern changes, and then any subsequent tests will be consistent with the new colors. But, bizarrely, they seem to be dependent on unit type (not just track type apparently, and different units give different results even if you make move speeds the same), move speed, size of the map, size of any assigned GuardedRects for the fightgroups, and unit spawn location.
• If unit speed is 0 (or fast units cheat is on which does the same thing), the corruption/crash never happens no matter what. Aside from that, the rate at which the corruption (or crash) manifests is dependent on unit speed, among other possible factors. It takes more time for fast units and less time for slow units if I remember correctly.
• Often times, including when it begins overwriting data past all the tilesets, it crashes at 0x446B9A, which is probably a big clue. "mov [ecx], eax ; Waypoint[j].freeListNext := EAX". The bug has to do with the free waypoint list breaking maybe?
• When exiting/restarting the mission after tileset data has been corrupted, the game will crash trying to free objects allocated on the heap (because of a null pointer?), but nothing interesting in the call stack

While trying to reproduce this bug I also discovered another pretty serious issue. If a unit destroyed too soon after it is created (and/or the other way around - need to test more), it "breaks" an entry in the free unit array, effectively reducing the hard unit limit by one (or however many times this happens) once 1024 units have been created over all time (or 2048 for 1.3.5?). I don't know much about this one since I've been focusing on the bug I'm actually chasing. I did figure out enough to realize that this is definitely a separate bug from the "acid trip" bug, with a different cause.

Additionally, unit->previous and unit->next (as in the internal unit data) are apparently not being initialized properly for units 1024-2047 in 1.3.5. While it doesn't seem to have detrimental effects in normal gameplay, it does seem have to do with why the game crashes instead of acid tripping, as the crash happens at 0x437633 when reading the unit linked list.


Here is my test project: link. There's configurable vars at the top of Main.cpp with a bunch of comments. It requires HFL. Note that it was built with an older version of the OP2 SDK (because I'm too lazy to set up the newer version ), so you'll need to fix up all the level export and SCRIPT_API stuff, project include folders, etc. to make it compatible with the newer SDK. Also, it uses __thiscall explicitly, so you need to either use MSVC 2005+ (or whatever other compilers may support it), or you need to change them to __fastcall and add dummy 2nd args to emulate __thiscall. For reference, I used MSVC 2008. The Swarm.map included in it is different from the original Swarm map, modified to utilize more tilesets.

[Hooman]

Hmm, that's a surprisingly detailed analysis Arklon. I know Vista uses Address Space Layout Randomization, which provides protections against certain exploits. It will only randomize code and stack locations for executables that declare they want it, but the heap randomization I believe is turned on for everything. Hence it makes sense if different sections of heap data get corrupted. It's also not surprising that image data gets corrupted incrementally, and then a crash occurs once the corruption has moved beyond the image data to something perhaps more sensitive to corruption. I may have to check out those memory locations at some point.

Lukc, happy to hear you're interested. I'd like to know a little more about you. Perhaps I can ask a few broad questions. What is it about Outpost 1 that interests you in particular? Do you have a preference for turn based games over real time strategies? Are there any particular technologies you've used? Desktop programming? Web programming? Nothing, but curious?

Traditionally I've liked hacking away at Outpost 2, but I've been wondering if a turn based web game might make for an interesting project. Perhaps new and simple game rules, but re-use art from the existing games, or some of the user created content posted to the forums. I'm not saying that's for sure what I want to work on, I'm just saying I'm open to new ideas. I'd like to find a project that's interesting to other people.

TH300, understood. Whatever I propose I'd like to work on in an open manner where other people can observe and jump in on development if desired. I'd like to choose something reasonable small and manageable that won't take too much of a commitment to understand and contribute to, or to complete.

[Hooman]

Arklon, I was just looking at your second last point, and I think I know what's going on.

The function in your second last point tries to return a recycled object if one exists, otherwise it allocates new memory for the object. When it allocates memory, it allocates a chunk from a pre-reserved range, where each chunk holds 16 objects. It then initializes the next pointers for those 16 new objects. The problem is the memory allocation isn't checked. When the reserved range runs out, the allocation can fail. If you create a lot of units, and they all need those objects to compute their paths, then the reserved range is probably being exhausted.

If the code used the unchecked return value, it would crash almost right away, since address 0 is never writable to help catch null pointer errors. Instead, the code uses the address it requested, assuming it would be allocated. Hence, it writes to heap memory, which is a valid write address, and corrupts it.

A quick fix would be to increase the size of the reserved memory range. See address 0x00446B06 for the size being reserved.

[Arklon]

Arklon, I was just looking at your second last point, and I think I know what's going on.

The function in your second last point tries to return a recycled object if one exists, otherwise it allocates new memory for the object. When it allocates memory, it allocates a chunk from a pre-reserved range, where each chunk holds 16 objects. It then initializes the next pointers for those 16 new objects. The problem is the memory allocation isn't checked. When the reserved range runs out, the allocation can fail. If you create a lot of units, and they all need those objects to compute their paths, then the reserved range is probably being exhausted.

If the code used the unchecked return value, it would crash almost right away, since address 0 is never writable to help catch null pointer errors. Instead, the code uses the address it requested, assuming it would be allocated. Hence, it writes to heap memory, which is a valid write address, and corrupts it.

A quick fix would be to increase the size of the reserved memory range. See address 0x00446B06 for the size being reserved.

I see. I still would like to know why this occurs when I add units to FightGroups, yet it doesn't when I just issue them move commands instead. And yeah, when I said DestWaypoints I was referring to the large structure with all the various pathfinding data (in DataStructure PathFinder.txt it's the Waypoint struct, or in my test project it's in OP2Types\OP2Pathfinder.h as DestWaypoints). Although, are you actually referring to the char direction[64] part? Because that'd be interesting, since I thought to the unit class would point to the DestWaypoints struct it's stored in.

Increasing the size of the block would only prolong the inevitable, it'd just take more units to trigger the overflow. We'd have to make it allocate the objects on the heap, find and patch the recycling code to deallocate the objects, and find out what causes objects to sometimes fail to recycle.

And, of course, I would like to know how to intentionally emulate the bug by getting pointers to the tilesets and overwriting their bitmap and palette data with DestWaypoints data, since just fixing the bug and leaving it at that would do an injustice to such an amazing bug. I have a feeling that might involve having to decipher the functionality of the pathfinder functions (to see what's being written to the DestWaypoints object) which were too much of a mess even for you, though. I was looking at the pathfinding code myself a while back and I pretty much "nope"-d out of it. I guess if you decipher what all the fields in the struct mean you can probably guesstimate which fields are likely getting written to and in what way, but ideally I'd like to just find some pathfinder function which I can pass a pointer into the tileset bitmap/palette data as the input for DestWaypoints pointer along with some waypoints/etc. just to keep it simple.


On a side note, I was looking at one of your older posts on your work on 1.3.5, and you mentioned that you'd like to strip the relocation table from Outpost2.exe in case it might interfere with any baked-in code patches. I feel differently about it, actually. I think it's fortunate that older compilers tended to compile exe's with relocation tables by default (even though they're pretty unnecessary for exe's unlike dll's), as was the case with OP2. Because that information exists, you can, for example, parse it to find every (direct) pointer to an internal object.

It's a very convenient means of resizing/replacing statically-allocated objects and arrays like the graphics object or the unitTypeInfo array, so additional sprites/etc. or unit types can be added. For some of these things, trying to do it by patching each reference by hand would be pretty sick - for example, the graphics object has 226 references! Fortunately, the locations of all 226 are conveniently contained in the relocation table. It also has the locations of all direct function pointers (such as in vftables), but that does not include relative pointers (mainly CALL REL32 which is a regular function call) nor RVA pointers, as relocation info for those types of pointers only exist in unlinked .objs.

If you're concerned with the relocation table messing with code patches (you move or delete a direct pointer reference), you can patch the reloc table to point to the new offset of the pointer or set the relocation type to 0 (IMAGE_REL_BASED_ABSOLUTE) which makes it get ignored, or I guess set the RELOCS_STRIPPED or whatever flag in the file header since that would still keep the physical data.

Here is a link to a dump of the relocation table: link. It includes the actual pointers that get relocated, which dumpbin doesn't show. IBR stands for IMAGE_BASE_RELOCATION, which is the header of each relocation block, and REL is a relocation entry. Each block contains relocations for (by default) a 4096-byte range, for example 0x00401000-0x00402000. x86 PE relocations are always type 3 (IMAGE_REL_BASED_HIGHLOW), but sometimes a dummy type 0 relocation is added to the end of a block to pad the next block to 4 bytes (since relocation entries are WORDs).

[Hooman]

I have no idea why you only observe this behavior for FightGroups. Perhaps there is more to the problem.

Thank you for pointing out that txt file. That is indeed the correct structure. I'd forgotten about that txt file, and it may save me some time if I write the info into a C++ header file.

The Unit class points to the big struct. The path drawing code uses the big struct to access numerous fields, and then walks the direction field in a loop to draw each tile-by-tile line.

If you want to emulate the bug, replace the head* with the address of the tile set data. The linked list pointers will need to be initialized though, so replace head* after the call to VirtualAlloc, but before the linked list pointers are initialized. Maybe set a breakpoint at 0x00446B84, and manually modify the value being stored to point to the tile set data. That would actually be a good way to visually test if this is related to your problem.

I don't know if objects fail to recycle or not. It might simply be a case of not having reserved enough memory to deal with maximum possible usage. This is particularly true when the unit limit was doubled. If every vehicle unit potentially needs more than one of these structs, which I believe is true, then there might not be enough to go around. Usage though, depends on whether or not the vehicle is moving. As not all vehicles are typically moving at once, this problem could easily have gone unnoticed by the original developers. Looking at the range of memory reserved for these objects, there is room for 2046 objects. If each vehicle uses multiple objects, there might not be enough structs to go around.


You're completely right about the relocations. I had thought of mining the relocation information to do some automated analysis of the code. My thoughts at the time were automatic type propagation. It sounded like a big project though, and I was lazy. Also, since many of the early patches were applied by a hex editor, without regard to the relocation table, it might already be partially corrupt. I later found I could do patches in OllyDbg, and have it save the modified memory as an executable file. I vaguely remember OllyDbg being aware of the relocations. I don't remember if it patched them up, or simply warned about potential problems. At any rate, we still have the original executable file to go back to if needed, hence I don't see a major issue about stripping relocations. Unless of course some new security feature of future versions of Windows require relocatable code, similar to Address Space Layout Randomization in Vista+, but enabled by default for old code too. But that would break backwards compatibility for Windows. At any rate, if the relocation information is there, but wrong, it will corrupt the code when it's applied. Hence, why it might be good to strip it if it's wrong.

I think the original reason for stripping, aside from correctness, was a way to save space. That's not much of a concern now. I think I'd rather correct the relocations, or verify they're still correct, rather than strip the information.

Can you commit your code to dump the relocations to SVN?

[Arklon]

Can you commit your code to dump the relocations to SVN?

You could look at Patcher::PatchGlobalReferences in Patcher.cpp in my test project I linked towards the start of the thread and modify it a bit to print the information.

[Hooman]

Hmm, yes, you have learned much.

I really think you should commit that code to SVN.

[Arklon]

I don't know if objects fail to recycle or not. It might simply be a case of not having reserved enough memory to deal with maximum possible usage. This is particularly true when the unit limit was doubled. If every vehicle unit potentially needs more than one of these structs, which I believe is true, then there might not be enough to go around. Usage though, depends on whether or not the vehicle is moving. As not all vehicles are typically moving at once, this problem could easily have gone unnoticed by the original developers. Looking at the range of memory reserved for these objects, there is room for 2046 objects. If each vehicle uses multiple objects, there might not be enough structs to go around.

No, that's not what must be going on here, or else it would be dependent on the number of units that are currently active/alive. Instead, it's dependent on the number of units ever added (including ones that get destroyed afterwards) to a FightGroup over the span of the game. Even if there's only a single active unit in the FightGroup at any given time, it can still happen if too many (now-dead) units had been added to it prior. My guess is the FightGroup itself is allocating some amount of those objects for whatever reason whenever or after units get added and it never deallocates them.

I did that test you suggested, and yep, the results look familiar. Based on how the corruption is propagating into the tileset data, it looks like the objects look to be getting recycled properly for units not part of FightGroups, which is what I expected. How far into the tileset it corrupts is based on how many units were given a move command at once, so if you're just selecting and moving units by hand you're limited to as far as 32 units can propagate the corruption. When the bug is induced by FightGroups, though, the corruption spreads further and further over time even with just a single unit being created then destroyed at a time, though there's still a lot of rewriting of the same areas so recycling probably isn't being totally broken.

[Hooman]

Thank you for the update. Your testing is interesting. It does sound like there is some kind of leak related to FightGroups.

Back to OllyDbg!

[Hooman]

While trying to reproduce this bug I also discovered another pretty serious issue. If a unit destroyed too soon after it is created (and/or the other way around - need to test more), it "breaks" an entry in the free unit array, effectively reducing the hard unit limit by one (or however many times this happens) once 1024 units have been created over all time (or 2048 for 1.3.5?). I don't know much about this one since I've been focusing on the bug I'm actually chasing. I did figure out enough to realize that this is definitely a separate bug from the "acid trip" bug, with a different cause.

I was just thinking back to this. If FightGroup is causing unit records to be lost, and those unit records are referencing the waypoint data, that waypoint data is also getting lost. Hence these two may very well be related in that sense. Are records being lost at the same rate, or does the waypoint data disappear faster? A factor of 2 faster, or a lot faster? I know unit records have two pointers to the waypoint data.

Perhaps AIProc could be used to scan the Unit array for lost records, and cause a debug break when one is detected.

Additionally, unit->previous and unit->next (as in the internal unit data) are apparently not being initialized properly for units 1024-2047 in 1.3.5. While it doesn't seem to have detrimental effects in normal gameplay, it does seem have to do with why the game crashes instead of acid tripping, as the crash happens at 0x437633 when reading the unit linked list.

While looking through the code I came across the section that initializes these pointers. It looks like it should work for all units. The constant had been modified for the larger unit array. Could you comment on how you tested this? Is it a single record causing the crash, or did you examine all (or many) records above 1024 and observed this? Were those unit records live?

[Arklon]

While trying to reproduce this bug I also discovered another pretty serious issue. If a unit destroyed too soon after it is created (and/or the other way around - need to test more), it "breaks" an entry in the free unit array, effectively reducing the hard unit limit by one (or however many times this happens) once 1024 units have been created over all time (or 2048 for 1.3.5?). I don't know much about this one since I've been focusing on the bug I'm actually chasing. I did figure out enough to realize that this is definitely a separate bug from the "acid trip" bug, with a different cause.

I was just thinking back to this. If FightGroup is causing unit records to be lost, and those unit records are referencing the waypoint data, that waypoint data is also getting lost. Hence these two may very well be related in that sense. Are records being lost at the same rate, or does the waypoint data disappear faster? A factor of 2 faster, or a lot faster? I know unit records have two pointers to the waypoint data.

This other bug happens independently of (but can still happen with) FightGroups, actually, but they're at least superficially related in that they're both different kinds of linked lists related to units getting broken. As opposed to the FightGroup "acid trip" bug, where the rate is linear but dependent on a number of factors (I outlined the ones that I know of in my original post), this particular bug happens at a simple linear rate - for each individual unit you destroy too soon after creating it (might be the other way around), 1 free unit record gets broken. The game is able to create units fine until (hard unit limit-# of broken free unit records?) have been created over the course of the game. After that point, unit creation can fail. I'm not entirely sure on what that entails, other than if I break 160 free unit records, then try to create 176 units, only 16 units will successfully be created, though I have sometimes seen this number alternate or fluctuate strangely if I try other numbers for records broken/units created which was possibly an effect of stacking FightGroups with this bug. I didn't look into this one all too extensively, since I was just concerned with figuring out why it was happening in my test mission so I could stop it from happening and be able to test the FightGroup-related bug properly.

Additionally, unit->previous and unit->next (as in the internal unit data) are apparently not being initialized properly for units 1024-2047 in 1.3.5. While it doesn't seem to have detrimental effects in normal gameplay, it does seem have to do with why the game crashes instead of acid tripping, as the crash happens at 0x437633 when reading the unit linked list.

While looking through the code I came across the section that initializes these pointers. It looks like it should work for all units. The constant had been modified for the larger unit array. Could you comment on how you tested this? Is it a single record causing the crash, or did you examine all (or many) records above 1024 and observed this? Were those unit records live?

It was a long time ago that I figured out this was broken, actually. I don't remember the details too well. I was trying to step through the linked list, but I think after 1024 or 2048 units created the *next pointer would be garbage (I think? Pretty sure it wasn't null). I didn't care too much at the time because I could just use Map.lastUsedUnitIndex and iterate through the actual unit array instead. When I was looking at the internal FightGroup functions (the ones in that big function pointer table with the rest of the CombatBase data), I did see there were one or two functions that referenced the unit linked list. I believe they're the only functions I have seen reference it, actually. I guess that's why it never seemed to be a problem in normal gameplay, but it's possible it could happen after an extended period of time in missions with AI. I guess I could mess with this again to refresh my memory on how it was broken. Where is the code that sets the pointers?

[Hooman]

Hmm, interesting comment about those functions from the function pointer table. I looked a little into those recently, but not a whole lot yet. There seemed to be little structure to go on, so I was delaying looking into them until I had a better picture of the Group class. I've now come across info on the index into that table, each index specifying a different behavior. (0 = DoGuardRect, 1 = DoPatrolOnly, 2 = DoGuardGroup, 3 = DoGuardUnit, 4 = DoAttackUnit, 5 = DoAttackEnemy, 6 = DoExitMap). I had actually suspected there might be a problem in there, but can't quite remember why I thought that.

Also, if you try to add a unit to a group that already contains 32 units, the extra units will go "poof". (As in ctMoPoof). Perhaps that could be related to leaking of unit or waypoint records. I also saw some nearby code that looked like improper handling of the nextFreeUnitNode tracking list in the Group class, so that's another candidate location. It forms a linked list using indexes rather than pointers, but seems to be incrementing the index, rather than following the next field. I marked it as a potential bug in my OllyDbg comments, but haven't fully analysed how those fields are used and updated.


Does anyone have any thoughts for other projects around here? Would anyone consider working on a small web game for instance? Turn based OP1/2 colony builder? Turn based battle sim with OP2 units? ... An Outpost themed game of soduku?

[Arklon]

Also, if you try to add a unit to a group that already contains 32 units, the extra units will go "poof". (As in ctMoPoof). Perhaps that could be related to leaking of unit or waypoint records.

I'm aware of that behavior, which is why in my test mission I make a bunch of FightGroups to be able to hold all the units if I want to create more than 32 at a time. I doubt that has to do with the bug, though, but then I guess I haven't really attempted seeing what happens if I try to add many units past 32 to one FightGroup.

[Hooman]

I finally got around to trying to compile your code. The current state of the API seems to be a bit of a mess. The projects files for the API are for Visual Studio 6, released in 1998. I've downloaded the free Visual Studio 2010, which can't read those project files. This means re-creating the project files to be able to work with the code.

Arklon, your project files are for Visual Studio 2008 (which I can read). There is also a Visual Studio 2013 available for download, but only for Windows 7+. Microsoft still provides Visual Studio 2010 for older operating systems. (My old laptop uses Vista). Perhaps we should update the project files in the SVN to use a more current version of Visual Studio.

Arklon, can your version of Visual Studio upgrade the old project and workspace files? I've heard the 2008 version can, but the 2010 version can't. If you can, could you please upgrade the core API project and workspace files?

I think we should standardize on a newer version of Visual Studio for project files. I'm thinking 2010, since it's available as a free download, and has good OS compatibility. If so, we should have someone with an older version of Visual Studio upgrade project files to something at least readable by that version.


I was also thinking the SVN could use a BugReproducer folder in it, for projects such as the "Acid" bug. (outpost2/LevelsAndMods/trunk/BugReproducer/<ProjectName>)

That could help share code, for working on understanding bugs. Projects in such a folder wouldn't necessarily be full levels, but just small bits of code to try and isolate some odd behavior. I would love to see this code in there. Arklon, I think you should commit your project, so you'll be listed as the author. Don't worry about fixing it up before committing. That can (and should) be done after the fact.

The actual full project would also be very welcome in SVN, perhaps under the "Levels" folder.


I was also thinking a level project might be an excellent project for people to collaborate on.

[Hooman]

Ok, I've split the posts about this bug into their own topic. Sorry that the split wasn't done very cleanly. Some posts referenced both threads of conversation, but the blunt moderator tools only let me split by post, not post contents.

I've added two bug reproducer projects to SVN. They were an attempt at reproducing the core of the unit creation and deletion in a minimal manner. The only difference between the two projects, is the number of groups created, but not how many are actually used. This results in two different crash addresses. This casts doubt on the two bugs being unrelated. Remember that memory problems produce undefined results, where basically anything can happen. It might be the groups merely offset memory corruption enough to cause a crash to happen elsewhere.

This could still be two unrelated bugs. I just feel the evidence is no longer quite as compelling, particularly given this is a memory corruption bug. It might be that one form of memory corruption, applied carefully, can cause a secondary form of memory corruption.

[Leviathan]

It would be nice to clean up the API code. I suggest we move to Visual Studio 2015 projects, its the most recent version and there are free versions of the software available.

Re-creating would be best but I could install 2008 and try and upgrade them at some point. I may have a VM with 2008 still installed.

MSVS 2015 projects may in fact be no different than 2012/2013 projects as I opened my older projects with it and it didn't give any notification or upgrade messages.

It would be great if you can commit your code Arklon.

In general we should try and share more code and get more onto the SVN. I have contacted a few old forum members hoping that they will reply and still have their source code to various projects.

Thanks for adding the BugReproducer folder and projects.