View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0002897 | FSSCP | public | 2013-06-30 05:41 | 2013-07-07 22:46 | |
| Reporter | Echelon9 | Assigned To | Echelon9 | ||
| Priority | normal | Severity | minor | Reproducibility | have not tried |
| Status | resolved | Resolution | fixed | ||
| Product Version | 3.7.0 RC2 | ||||
| Target Version | 3.7.0 | ||||
| Summary | 0002897: Heap corruption in dock_evaluate_all_docked_objects() objectdock.cpp | ||||
| Description | As reported by Droid803 on HLP forums here : http://www.hard-light.net/forums/index.php?topic=84900.0 Appears to be caused by the following vm_free in dock_evaluate_all_docked_objects() per callstack ====================================== // evaluate a certain function for all docked objects void dock_evaluate_all_docked_objects(object *objp, dock_function_info *infop, void (*function)(object *, dock_function_info *)) { Assert((objp != NULL) && (infop != NULL) && (function != NULL)); // not docked? if (!object_is_docked(objp)) { // call the function for just the one object function(objp, infop); return; } ... // we have multiple objects docked and we must treat them as a tree else { // create a bit array to mark the objects we check ubyte *visited_bitstring = (ubyte *) vm_malloc(calculate_num_bytes(Num_objects)); // clear it memset(visited_bitstring, 0, calculate_num_bytes(Num_objects)); // start evaluating the tree dock_evaluate_tree(objp, infop, function, visited_bitstring); // destroy the bit array vm_free(visited_bitstring); visited_bitstring = NULL; } } | ||||
| Steps To Reproduce | Unsure, may have something to do with warping in objects that are docked together. | ||||
| Additional Information | ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000e711f at pc 0x101a70814 bp 0x7fff5fbfbfb0 sp 0x7fff5fbfbfa8 READ of size 1 at 0x6020000e711f thread T0 #0 0x101a70813 in dock_evaluate_tree, unsigned char*) objectdock.cpp:350 0000001 0x101a68129 in dock_evaluate_all_docked_objects) objectdock.cpp:339 0000002 0x101a714cf in dock_move_docked_objects objectdock.cpp:397 0000003 0x101a90703 in obj_move_all object.cpp:1467 0000004 0x1002f06bc in game_simulation_frame freespace.cpp:3985 0000005 0x1002f53c0 in game_frame freespace.cpp:4378 0000006 0x1002fabdb in game_do_frame freespace.cpp:4789 0000007 0x100306736 in game_do_state freespace.cpp:6465 0000008 0x100901f28 in gameseq_process_events gamesequence.cpp:405 0000009 0x10030cfd6 in game_main freespace.cpp:7032 0000010 0x10030e674 in SDL_main freespace.cpp:7166 #11 0x100002c33 in -[SDLMain applicationDidFinishLaunching:] SDLMain.m:300 0000012 0x7fff95444ed9 in _CFXNotificationPost (in CoreFoundation) + 2553 0000013 0x7fff8f5c67b5 in -[NSNotificationCenter postNotificationName:object:userInfo:] (in Foundation) + 63 0000014 0x7fff98e5c52c in -[NSApplication _postDidFinishNotification] (in AppKit) + 291 0000015 0x7fff98e5c265 in -[NSApplication _sendFinishLaunchingNotification] (in AppKit) + 215 0000016 0x7fff98e59451 in -[NSApplication(NSAppleEventHandling) _handleAEOpenEvent:] (in AppKit) + 565 0000017 0x7fff98e5904b in -[NSApplication(NSAppleEventHandling) _handleCoreEvent:withReplyEvent:] (in AppKit) + 350 0000018 0x7fff8f5e007a in -[NSAppleEventManager dispatchRawAppleEvent:withRawReply:handlerRefCon:] (in Foundation) + 307 0000019 0x7fff8f5dfedc in _NSAppleEventManagerGenericHandler (in Foundation) + 105 0000020 0x7fff94e91077 in aeDispatchAppleEvent(AEDesc const*, AEDesc*, unsigned int, unsigned char*) (in AE) + 306 0000021 0x7fff94e90ed8 in dispatchEventAndSendReply(AEDesc const*, AEDesc*) (in AE) + 36 0000022 0x7fff94e90d98 in aeProcessAppleEvent (in AE) + 317 0000023 0x7fff93c24708 in AEProcessAppleEvent (in HIToolbox) + 99 0000024 0x7fff98e55835 in _DPSNextEvent (in AppKit) + 1455 0000025 0x7fff98e54df1 in -[NSApplication nextEventMatchingMask:untilDate:inMode:dequeue:] (in AppKit) + 127 0000026 0x7fff98e4c1a2 in -[NSApplication run] (in AppKit) + 516 0000027 0x100004da2 in CustomApplicationMain SDLMain.m:227 0000028 0x10000480f in main SDLMain.m:377 0000029 0x100001953 in start (in FS2_Open (debug)) + 51 0000030 0x0 in 0x0 0x6020000e711f is located 0 bytes to the right of 15-byte region [0x6020000e7110,0x6020000e711f) allocated by thread T0 here: #0 0x1053d88f1 in wrap_malloc _asan_rtl_ 0000001 0x1025f4828 in _vm_malloc stubs.cpp:571 0000002 0x101a67ec2 in dock_evaluate_all_docked_objects) objectdock.cpp:333 0000003 0x101a714cf in dock_move_docked_objects objectdock.cpp:397 0000004 0x101a90703 in obj_move_all object.cpp:1467 0000005 0x1002f06bc in game_simulation_frame freespace.cpp:3985 0000006 0x1002f53c0 in game_frame freespace.cpp:4378 0000007 0x1002fabdb in game_do_frame freespace.cpp:4789 0000008 0x100306736 in game_do_state freespace.cpp:6465 0000009 0x100901f28 in gameseq_process_events gamesequence.cpp:405 0000010 0x10030cfd6 in game_main freespace.cpp:7032 #11 0x10030e674 in SDL_main freespace.cpp:7166 0000012 0x100002c33 in -[SDLMain applicationDidFinishLaunching:] SDLMain.m:300 0000013 0x7fff95444ed9 in _CFXNotificationPost (in CoreFoundation) + 2553 0000014 0x7fff8f5c67b5 in -[NSNotificationCenter postNotificationName:object:userInfo:] (in Foundation) + 63 0000015 0x7fff98e5c52c in -[NSApplication _postDidFinishNotification] (in AppKit) + 291 0000016 0x7fff98e5c265 in -[NSApplication _sendFinishLaunchingNotification] (in AppKit) + 215 0000017 0x7fff98e59451 in -[NSApplication(NSAppleEventHandling) _handleAEOpenEvent:] (in AppKit) + 565 0000018 0x7fff98e5904b in -[NSApplication(NSAppleEventHandling) _handleCoreEvent:withReplyEvent:] (in AppKit) + 350 0000019 0x7fff8f5e007a in -[NSAppleEventManager dispatchRawAppleEvent:withRawReply:handlerRefCon:] (in Foundation) + 307 0000020 0x7fff8f5dfedc in _NSAppleEventManagerGenericHandler (in Foundation) + 105 0000021 0x7fff94e91077 in aeDispatchAppleEvent(AEDesc const*, AEDesc*, unsigned int, unsigned char*) (in AE) + 306 0000022 0x7fff94e90ed8 in dispatchEventAndSendReply(AEDesc const*, AEDesc*) (in AE) + 36 0000023 0x7fff94e90d98 in aeProcessAppleEvent (in AE) + 317 0000024 0x7fff93c24708 in AEProcessAppleEvent (in HIToolbox) + 99 0000025 0x7fff98e55835 in _DPSNextEvent (in AppKit) + 1455 0000026 0x7fff98e54df1 in -[NSApplication nextEventMatchingMask:untilDate:inMode:dequeue:] (in AppKit) + 127 0000027 0x7fff98e4c1a2 in -[NSApplication run] (in AppKit) + 516 0000028 0x100004da2 in CustomApplicationMain SDLMain.m:227 0000029 0x10000480f in main SDLMain.m:377 Shadow bytes around the buggy address: 0x1c040001cdd0: fa fa fd fa fa fa fd fa fa fa fd fd fa fa 00 04 0x1c040001cde0: fa fa 00 00 fa fa fa fa fa fa 00 00 fa fa fa fa 0x1c040001cdf0: fa fa fa fa fa fa 00 fa fa fa 00 00 fa fa fa fa 0x1c040001ce00: fa fa fd fd fa fa fa fa fa fa fa fa fa fa fa fa 0x1c040001ce10: fa fa fd fd fa fa fa fa fa fa fa fa fa fa fd fd =>0x1c040001ce20: fa fa 00[07]fa fa fd fd fa fa fa fa fa fa fa fa 0x1c040001ce30: fa fa fa fa fa fa 04 fa fa fa 00 fa fa fa 00 00 0x1c040001ce40: fa fa fd fa fa fa fa fa fa fa 00 00 fa fa fd fd 0x1c040001ce50: fa fa fd fd fa fa fd fd fa fa 00 00 fa fa 00 00 0x1c040001ce60: fa fa fd fd fa fa 00 00 fa fa 00 fa fa fa fd fd 0x1c040001ce70: fa fa 00 fa fa fa fd fa fa fa fd fa fa fa fd fa Shadow byte legend (one shadow byte represents 8 application bytes): Addressable: 00 Partially addressable: 01 02 03 04 05 06 07 Heap left redzone: fa Heap right redzone: fb Freed heap region: fd Stack left redzone: f1 Stack mid redzone: f2 Stack right redzone: f3 Stack partial redzone: f4 Stack after return: f5 Stack use after scope: f8 Global redzone: f9 Global init order: f6 Poisoned by user: f7 ASan internal: fe ==15124==ABORTING | ||||
| Tags | No tags attached. | ||||
|
|
|
|
|
I would want to see the mission: specifically when the crash occurs and what the value of Num_objects is at the time of the crash. It occurred to me that if this function were evaluated when Num_objects was still -1 (which would supposedly be at the beginning of the mission before any objects were created), the size of the bitstring would be 0, and therefore any writes would be off the end of the array. |
|
|
The core problem would have to be that there were more objects in the dock tree than Num_objects. That would cause the bitstring to be too short for navigating the tree. The question, of course, is how that could possibly occur. |
|
|
Either AddressSanitizer or the LLVM sibling IOC (integer overflow checker) should pick this up if we can repro it. |
|
|
Have been able to reproduce this in AddressSanitizer using private data shared by Droid. Additional Information has been updated. Currently working through the memory steps leading up to the crash. |
|
|
Somehow objects are getting added to the Objects[] array without increasing Num_objects to track the same. At the time of vm_malloc()'ing visited_bitstring in dock_evaluate_all_docked_objects() =========================================== calculate_num_bytes(Num_objects) = 15, and Num_objects = 113 At the time of calling get_bit() in dock_evaluate_tree() <- the crash =========================================== trying to access visited_bitstring[15], OBJ_INDEX(objp) = 121, and Num_objects = 113 i.e. as Goober predicted, that OBJ_INDEX(objp) > Num_objects is the issue |
|
|
mantis-2897-temp-fix.patch (712 bytes)
Index: code/object/objectdock.cpp
===================================================================
--- code/object/objectdock.cpp (revision 9699)
+++ code/object/objectdock.cpp (working copy)
@@ -330,10 +330,10 @@
else
{
// create a bit array to mark the objects we check
- ubyte *visited_bitstring = (ubyte *) vm_malloc(calculate_num_bytes(Num_objects));
+ ubyte *visited_bitstring = (ubyte *) vm_malloc(calculate_num_bytes(Num_objects + 20));
// clear it
- memset(visited_bitstring, 0, calculate_num_bytes(Num_objects));
+ memset(visited_bitstring, 0, calculate_num_bytes(Num_objects + 20));
// start evaluating the tree
dock_evaluate_tree(objp, infop, function, visited_bitstring);
|
|
|
Attaching a temporary fix patch -- this ensures the visited_bitstring bit array is setup with a slightly larger size than initially expected. If we want to get a temporary fix into 3.7.0 Final, this may be appropriate. Continuing to get to the bottom of this. |
|
|
mantis-2897-resolution.patch (720 bytes)
Index: code/object/objectdock.cpp
===================================================================
--- code/object/objectdock.cpp (revision 9706)
+++ code/object/objectdock.cpp (working copy)
@@ -330,10 +330,10 @@
else
{
// create a bit array to mark the objects we check
- ubyte *visited_bitstring = (ubyte *) vm_malloc(calculate_num_bytes(Num_objects));
+ ubyte *visited_bitstring = (ubyte *) vm_malloc(calculate_num_bytes(Highest_object_index));
// clear it
- memset(visited_bitstring, 0, calculate_num_bytes(Num_objects));
+ memset(visited_bitstring, 0, calculate_num_bytes(Highest_object_index));
// start evaluating the tree
dock_evaluate_tree(objp, infop, function, visited_bitstring);
|
|
|
Patch attached for code review that undertakes the proper resolution. This is ready for 3.7.0 subject to review comments. ======================== The underlying issue is that Num_objects is an inappropriate measure to use, when we have a non-compacting Objects garbage collection algorithm. Num_objects does correctly track the in use items in the Objects[] array. However, the index of the highest in use item in the Objects[] array can be well above the value set at Num_objects, particularly where there has been many objects initialised and then deleted (as was the case in Droid's mission). A value that works for any algorithm that later uses OBJ_INDEX() to walk the Objects[] array is a measure of high water mark item usage in Objects. Such a value is stored in Highest_object_index. Until such time as we implement a compacting garbage collection memory system, care should be used using Num_objects outside of the object allocation and free'ing functions. ======================== To note there is one other possible dangerous use of Num_objects in the code base within init_ai_objects(). I will open a second Mantis report for that issue. |
|
|
Great catch. :yes: I probably designed the code with the assumption that Num_objects represented the upper bound of an array that was always compacted. But you're right, that's an incorrect assumption. I think, however, that I'll change the calculation to use MAX_OBJECTS. That will put it in sync with parsedockedobject.cpp which uses Parse_objects.size(). It will also move some of the run-time calculation into compile-time calculation (which will save an insignificant amount of time, but still). The other thing to keep in mind is that when you have a 0-based array, the highest index is always one less than the length. So if we had used Highest_object_index, we would have had to add a +1. I'll commit this and assign credit to you for doing the footwork. |
|
|
Fix committed to trunk@9708. |
| Date Modified | Username | Field | Change |
|---|---|---|---|
| 2013-06-30 05:41 | Echelon9 | New Issue | |
| 2013-06-30 05:41 | Echelon9 | File Added: Droid803_fs2_open.log | |
| 2013-06-30 12:45 | Echelon9 | Assigned To | => Echelon9 |
| 2013-06-30 12:45 | Echelon9 | Status | new => assigned |
| 2013-07-01 01:58 | Goober5000 | Note Added: 0015152 | |
| 2013-07-01 02:00 | Goober5000 | Note Added: 0015153 | |
| 2013-07-01 14:37 | Echelon9 | Note Added: 0015154 | |
| 2013-07-07 07:26 | Echelon9 | Additional Information Updated | |
| 2013-07-07 07:27 | Echelon9 | Note Added: 0015163 | |
| 2013-07-07 07:27 | Echelon9 | Status | assigned => acknowledged |
| 2013-07-07 08:09 | Echelon9 | Note Added: 0015164 | |
| 2013-07-07 08:21 | Echelon9 | Note Edited: 0015164 | |
| 2013-07-07 08:22 | Echelon9 | Note Edited: 0015164 | |
| 2013-07-07 08:30 | Echelon9 | File Added: mantis-2897-temp-fix.patch | |
| 2013-07-07 08:31 | Echelon9 | Note Added: 0015165 | |
| 2013-07-07 08:31 | Echelon9 | Assigned To | Echelon9 => Goober5000 |
| 2013-07-07 08:31 | Echelon9 | Status | acknowledged => code review |
| 2013-07-07 08:32 | Echelon9 | Note Edited: 0015165 | |
| 2013-07-07 11:50 | Echelon9 | File Added: mantis-2897-resolution.patch | |
| 2013-07-07 11:55 | Echelon9 | Note Added: 0015166 | |
| 2013-07-07 12:06 | Echelon9 | Relationship added | related to 0002900 |
| 2013-07-07 22:44 | Goober5000 | Note Added: 0015169 | |
| 2013-07-07 22:44 | Goober5000 | Assigned To | Goober5000 => Echelon9 |
| 2013-07-07 22:46 | Goober5000 | Changeset attached | => fs2open trunk r9708 |
| 2013-07-07 22:46 | Goober5000 | Note Added: 0015170 | |
| 2013-07-07 22:46 | Goober5000 | Status | code review => resolved |
| 2013-07-07 22:46 | Goober5000 | Resolution | open => fixed |
