use-after-free in editor

To reproduce the bug with the resources tool:

1. Place some water on the map
2. Add fish
3. Change the map origin
4. Hit the undo button twice

The underlying problem here is that undo stops working for all editor tools once the map origin changes. The other tools simply won't undo anything (or maybe undo something in the wrong location?)

==29319==ERROR: AddressSanitizer: heap-use-after-free on address 0x63300005a349 at pc 0x000000fb7e40 bp 0x7ffc300a1910 sp 0x7ffc300a1900
WRITE of size 1 at 0x63300005a349 thread T0
    #0 0xfb7e3f in Widelands::Map::initialize_resources(Widelands::FCoords const&, unsigned char, unsigned char) /home/bratzbert/sources/widelands/asan/src/logic/map.cc:1819
    #1 0xe2e2da in EditorSetResourcesTool::handle_undo_impl(Widelands::World const&, Widelands::NodeAndTriangle<Widelands::Coords, Widelands::Coords> const&, EditorInteractive&, EditorActionArgs*, Widelands::Map*) /home/bratzbert/sources/widelands/asan/src/editor/tools/set_resources_tool.cc:75
    #2 0xe23344 in EditorIncreaseResourcesTool::handle_undo_impl(Widelands::World const&, Widelands::NodeAndTriangle<Widelands::Coords, Widelands::Coords> const&, EditorInteractive&, EditorActionArgs*, Widelands::Map*) /home/bratzbert/sources/widelands/asan/src/editor/tools/increase_resources_tool.cc:71
    #3 0xe172dd in EditorTool::handle_undo(EditorTool::ToolIndex, Widelands::World const&, Widelands::NodeAndTriangle<Widelands::Coords, Widelands::Coords> const&, EditorInteractive&, EditorActionArgs*, Widelands::Map*) /home/bratzbert/sources/widelands/asan/src/editor/tools/tool.h:70
    #4 0xe1870e in EditorHistory::undo_action(Widelands::World const&) /home/bratzbert/sources/widelands/asan/src/editor/tools/history.cc:67
    #5 0xdd2bc0 in operator() /home/bratzbert/sources/widelands/asan/src/editor/editorinteractive.cc:133

0x63300005a349 is located 23369 bytes inside of 106496-byte region [0x633000054800,0x63300006e800)
freed by thread T0 here:
    #0 0x7fd14bcb1caa in operator delete[](void*) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x99caa)
    #1 0xfc3258 in std::default_delete<Widelands::Field []>::operator()(Widelands::Field*) const /usr/include/c++/5/bits/unique_ptr.h:119
    #2 0xfbf642 in std::unique_ptr<Widelands::Field [], std::default_delete<Widelands::Field []> >::reset(Widelands::Field*) /usr/include/c++/5/bits/unique_ptr.h:581
    #3 0xfb01dc in Widelands::Map::set_origin(Widelands::Coords const&) /home/bratzbert/sources/widelands/asan/src/logic/map.cc:362
    #4 0xe2bd0f in EditorSetOriginTool::handle_click_impl(Widelands::World const&, Widelands::NodeAndTriangle<Widelands::Coords, Widelands::Coords> const&, EditorInteractive&, EditorActionArgs*, Widelands::Map*) /home/bratzbert/sources/widelands/asan/src/editor/tools/set_origin_tool.cc:31
    #5 0xe17123 in EditorTool::handle_click(EditorTool::ToolIndex, Widelands::World const&, Widelands::NodeAndTriangle<Widelands::Coords, Widelands::Coords> const&, EditorInteractive&, EditorActionArgs*, Widelands::Map*) /home/bratzbert/sources/widelands/asan/src/editor/tools/tool.h:60
    #6 0xe1900f in EditorHistory::do_action(EditorTool&, EditorTool::ToolIndex, Widelands::Map&, Widelands::World const&, Widelands:...

I can't reproduce the bug with the resources tool. I used trunk (revno 8528) and Debian 9.1 which has libasan3. The backtrace of #1 says that libasan.so.2 has used when the bug found.

Can reproduce the bug mentioned in #1 with bzr8530[trunk] (Debug)

With r8531 and no ASAN try the following:

 1. Open Editor
 2. Place the immovable 'Ruin' (the column) at position 2/7
 3. Use Set Origin at the position 2/13, the position of the ruin is now at 0/58
 4. Hit undo -> The Ruin appears now at position 3/8 (one down, one right, compares to step 2)
 6. Hit redo -> The Ruin appears now at position 0/59 (one right compares to step 3)
 7. Hit undo -> The Ruin appears now at position 3/9 (one to right, compares to step 4)
 8. Hit redo -> The Ruin appears now at position 1/60 (one down, one right, compares to step 6)
 9. Hit undo -> The Ruin appears now at position 4/10 (one to right, one to down compares to step 7)
 ... The more one uses Redo Undo, the more the immovable 'walks' to the right and down.

Now close widelands and run again to get a clean environment, do the same as above until step 4. and then:
 5. click Undo again -> nothing happens, but normally one would suspect the ruin get removed
 6. click Redo -> The ruin appears twice, once at the position 3/8 and an additional one at position 2,7 (the initial position)

When doing the things in #1 and do the first Undo it changes the Origin, a second undo should remove the fish, but this is done only partial: Fish on the bottom right didn't get removed. Doing a third Undo should remove the Terrain water, but removing is the same as with the fish: Some terrain of Water on the bottom right stays on the map.

Looks like this bug is already in build19. With build19(release) it crashes when trying to do the things mentioned in #1.

Now I can reproduce the bug by following the instructions of #4. Thanks kaputtnik!
I thought that the "Change the map origin" of #1 meant moving the origin and not setting it. My mistake!

Is there happening a wrong action for the step 4? of #4. Should the origin move back to the position where it was before the step 3.

Yes, we have an index error while undoing. The position in 2 and in 4 need to be identical.

Thanks for tracking this down, Kaputtnik!

For testing purposes i used to place the ruin at 0/0 and set the origin at 63/0. Using Undo then returns wrong values in:

http://bazaar.launchpad.net/~widelands-dev/widelands/trunk/view/head:/src/editor/tools/set_origin_tool.cc#L44

BTW: It is very annoying that the map position 0/0 is at the top left of the screen when the editor starts or a map get loaded, while using set origin the position 0/0 is at the center of the screen.

Can some one with ASAN turned on test the attached branch?

Here it fixes the bug...

What i have done is to remove the hardcoded substraction of '1' in set_origin_tool and instead call map.normalize_coords which is more save method to handle with the map turnaround (the border where width=64 is width=0)

Just found that i have introduced this bug by myself :-D

https://bugs.launchpad.net/widelands/+bug/1566720/comments/2

I tested the bug-1735980_fix_undo_set_origin branch and

Step 4 of #4 -> Now the Ruin appears at position 1/7
Step 5 of #4 -> Now the Ruin appears at position 63/58

I ment
Step 6 of #4 -> Now the Ruin appears at position 63/58

I didn't notice that there was missing a step and the 5th was used later. :)

The heap-use-after-free problem of #1 is still there.

hm... you are right. Dammn...

I guess there are two bugs: A wrong calculation for undo set origin and the 'heap use after free'? Or do they stick together?

If you, or some one else, could investigate i would be fine :-)

The ruin may get correct position if we remove -1 only from the Y-coordinate and not from the X. But, this may be too easy way to fix it. The map is using a coordinate system that I don't understand and I need to learn more until I can do some map related changes.

I think the reset of fields_ (src/logic/map.cc:362) deletes something which is used afterwards. This can be easily tested if we clear the fields_ before the reset. Asan propably say that the clear before the actual reset causing the heap-use-after-free.

Yes, looks like we have 2 different bugs here.

In the Map::set_origin method is said that
"because of the triangle design, we have to take special care about cases where y is changed by an odd number".
In the method there is added +1 to X-coordinate if Y-coordinate of new origin and an immovable are both an odd number. So the added +1 must be removed when doing an undo. I tested this and it worked with the #4.

We get rid of the heap-use-after-free case if we copy the coordines from the new_field_order to the fields_ instead of doing the reset. I used just a for loop and it worked fine.

Please provide a branch :-)

Yes, whenever you have found a solution for a bug, please make a branch and create a merge request. It will really help us a lot with our workflow if you do this :)

Sure, a branch is coming soon.

Cool, thanks! :)

Fixed in build20-rc1