View Issue Details

IDProjectCategoryView StatusLast Update
0004251The Dark ModCodingpublic02.12.2015 18:08
ReporterSteveL Assigned ToSteveL  
PrioritynormalSeveritynormalReproducibilitysometimes
Status resolvedResolutionfixed 
Product VersionTDM 2.03 
Target VersionTDM 2.04Fixed in VersionTDM 2.04 
Summary0004251: Boolean objectives can mess up when you have more than 16 objectives
DescriptionMap objectives are stored in an idList which initially reserves space for 16 objectives, the default for any idList. Objectives with boolean success or failure conditions create a decision tree in memory (made of SBoolParseNode) whose nodes store pointers to their parents.

The problem is that if the number of objectives exceeds 16, the list will be moved to a new larger memory block, but the pointers will be copied unchanged. So if you have any boolean objectives in the first 16, they will hold dangling pointers after the move. Sometimes there will be no problem, because the old memory block won't yet have been written over. But if it does get written over (essentially random), the objectives will behave wrong.

Currently affects only 1 map: A Reputation to Uphold.
Additional InformationFrom the dev forum: http://forums.thedarkmod.com/topic/17442-any-changes-to-triggers-or-trigger-relays-in-203/page-2#entry382276
TagsNo tags attached.

Activities

SteveL

SteveL

26.11.2015 19:02

reporter   ~0007892

This could also affect any single objective that has very complicated success or failure logic: "complicated" meaning, more than 16 conditions and a mix of AND and OR in there.

One solution might have been to use another container from idLib to hold the decision tree (SBoolParseNodes) instead of idList. idList is the only one that reallocates memory and moves things round. But I read through them all and none of them are suitable. idLinkList is the closest, but it doesn't do garbage collection and it doesn't allow random access.

Likewise none of the c++ std:: containers quite fit the bill. std::list doesn't allow random access. std::deque doesn't guarantee no memory movement on all systems.

An easy fix would have been to set a hard limit on the number of objectives and the number of conditions that are allowed, then always allocate enough memory when the lists are created to hold that limit. But that would have added complexity to the documentation and code without making for an elegant solution. We'd still have pointers into managed memory, that could surprise anyone who tweaks the system later.

The latest idea I'm checking out is another hack, but one that's probably safer for future devs than all the above: repair the pointers after the decision trees are fully constructed.
Cons:
• We still have pointers into managed memory, so we don't actuallty correct the original design error.
Pros:
• Those pointers won't cause bugs. Once the trees are fully constructed they don't have to be changed again.
• Very little disturbance to existing code, so there's less that can go wrong.
• The problem and the fix will be immediately clear and comprehensible to any future coder who touches it. The code to repair the pointers will sit with the SBoolParseNode class, which'll highlight the original problem with the class design for anyone who looks at it. And the code that constructs the trees will call the repair function.
SteveL

SteveL

01.12.2015 18:14

reporter   ~0007894

That worked, but I don't like it because the calls to RepairPointers ended up being needed in 3 places. So there's obvious potential for someone to trip over it in future.

Currently testing: override the copy and assignment operators for the SBoolParseNode class, so that if any node gets copied to a new memory location, it repairs the pointers below it.

This should fix it once and for all. I'll make some of the data members in the struct private (and declare the struct as a class), so that there's no way for any future code to copy a SBoolParseNode while avoiding the fix code.
SteveL

SteveL

01.12.2015 18:31

reporter   ~0007895

Forget the bit about making some data members private. All are accessed throughout the objective code, so that'd be lots of changes, and anyway no-one would write custom code to copy a struct without looking at the struct declaration, which now has plenty of documentation.
SteveL

SteveL

02.12.2015 18:08

reporter   ~0007897

Committed at rev 6557

/trunk/game/Objectives/BoolParseNode.h -- the changes
/trunk/game/Objectives/MissionData.cpp -- deletion of 1 unnecessary line of code

Issue History

Date Modified Username Field Change
24.11.2015 20:28 SteveL New Issue
24.11.2015 20:28 SteveL Status new => assigned
24.11.2015 20:28 SteveL Assigned To => SteveL
26.11.2015 19:02 SteveL Note Added: 0007892
01.12.2015 18:14 SteveL Note Added: 0007894
01.12.2015 18:31 SteveL Note Added: 0007895
02.12.2015 18:08 SteveL Note Added: 0007897
02.12.2015 18:08 SteveL Status assigned => resolved
02.12.2015 18:08 SteveL Fixed in Version => TDM 2.04
02.12.2015 18:08 SteveL Resolution open => fixed