CruiserOne / Daedalus

The Maze generation software "Daedalus", version 3.4
http://www.astrolog.org/labyrnth/daedalus.htm
Other
53 stars 7 forks source link

Memory ovewrite on Ubuntu #3

Closed vineyy closed 1 year ago

vineyy commented 1 year ago

I cloned the code on Ubuntu 20.04, commented out #define WIN and #define PC in util.h and compiled using the makefile mentioned in #1. Build was successful and I was able to generate mazes. But for some values of Size parameters, it crashes

user@MYLABVM:~/Daedalus-master$ ./daedalus 'Size 35 35 1 0 ab P SaveText "files/QWoGKzqOxF"'
malloc(): corrupted top size
Aborted (core dumped)
user@MYLABVM:~/Daedalus-master$ 

Interestingly ./daedalus 'Size 34 34 1 0 ab P SaveText "files/QWoGKzqOxF"' and ./daedalus 'Size 36 36 1 0 ab P SaveText "files/QWoGKzqOxF"' worked without any issue.

gdb to see where the crash is:

(gdb) bt
#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
#1  0x00007ffff7a98859 in __GI_abort () at abort.c:79
#2  0x00007ffff7b0329e in __libc_message (action=action@entry=do_abort, fmt=fmt@entry=0x7ffff7c2d298 "%s\n") at ../sysdeps/posix/libc_fatal.c:155
#3  0x00007ffff7b0b32c in malloc_printerr (str=str@entry=0x7ffff7c2b569 "malloc(): corrupted top size") at malloc.c:5347
#4  0x00007ffff7b0e6ea in _int_malloc (av=av@entry=0x7ffff7c62b80 <main_arena>, bytes=bytes@entry=289) at malloc.c:4107
#5  0x00007ffff7b10184 in __GI___libc_malloc (bytes=289) at malloc.c:3058
#6  0x00005555555a2213 in PAllocate (lcb=lcb@entry=289) at daedalus.cpp:3014
#7  0x0000555555583670 in CMaz::RecursiveGenerate (this=this@entry=0x55555561a778 <bm+120>, xs=4, ys=ys@entry=12) at create.cpp:605
#8  0x0000555555583990 in CMaz::CreateMazeRecursive (this=0x55555561a778 <bm+120>) at create.cpp:680
#9  0x00005555555786c3 in DoCommand (wCmd=1119) at command.cpp:5318
#10 0x000055555557aeab in RunCommandLine (szLine=0x7fffffffde70 "Size 35 35 1 0 ab P SaveText \"files/QWoGKzqOxF\" ", file=0x0) at command.cpp:6153
#11 0x00005555555a96d1 in main (argc=<optimized out>, argv=<optimized out>) at daedalus.cpp:2942
(gdb)

I suspected memory overwrite so I ran it with valgrind:

user@MYLABVM:~/Daedalus-master$ valgrind ./daedalus 'Size 35 35 1 0 ab P SaveText "files/QWoGKzqOxF"'
==339293== Memcheck, a memory error detector
==339293== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==339293== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==339293== Command: ./daedalus Size\ 35\ 35\ 1\ 0\ ab\ P\ SaveText\ "files/QWoGKzqOxF"
==339293==
==339293== Invalid read of size 8
==339293==    at 0x171CA6: CMon::Set(int, int, long) (graphics.cpp:335)
==339293==    by 0x17689C: CMap::FBitmapShiftBy(int, int) (graphics.cpp:1900)
==339293==    by 0x15468F: DoSize(int, int, int, int) (daedalus.cpp:530)
==339293==    by 0x12FF3F: DoOperation(int, char**, int const*, long const*, _IO_FILE*) (command.cpp:3119)
==339293==    by 0x12EF0E: RunCommandLine(char*, _IO_FILE*) (command.cpp:6166)
==339293==    by 0x15D6D0: main (daedalus.cpp:2942)
==339293==  Address 0x4db9b54 is 276 bytes inside a block of size 280 alloc'd
==339293==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==339293==    by 0x156212: PAllocate(long) (daedalus.cpp:3014)
==339293==    by 0x17199C: CMon::FAllocate(int, int, CMap const*) (graphics.cpp:257)
==339293==    by 0x176837: CMap::FBitmapShiftBy(int, int) (graphics.cpp:1896)
==339293==    by 0x15468F: DoSize(int, int, int, int) (daedalus.cpp:530)
==339293==    by 0x12FF3F: DoOperation(int, char**, int const*, long const*, _IO_FILE*) (command.cpp:3119)
==339293==    by 0x12EF0E: RunCommandLine(char*, _IO_FILE*) (command.cpp:6166)
==339293==    by 0x15D6D0: main (daedalus.cpp:2942)
==339293==
==339293== Invalid write of size 8
==339293==    at 0x17231C: CMon::BitmapSet(long) (graphics.cpp:1545)
==339293==    by 0x1920F7: CMaz::MazeClear(long) (maze.cpp:210)
==339293==    by 0x137947: CMaz::CreateMazeRecursive() (create.cpp:677)
==339293==    by 0x12C6C2: DoCommand(int) (command.cpp:5318)
==339293==    by 0x12EEAA: RunCommandLine(char*, _IO_FILE*) (command.cpp:6153)
==339293==    by 0x15D6D0: main (daedalus.cpp:2942)
==339293==  Address 0x4db9b54 is 276 bytes inside a block of size 280 alloc'd
==339293==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==339293==    by 0x156212: PAllocate(long) (daedalus.cpp:3014)
==339293==    by 0x17199C: CMon::FAllocate(int, int, CMap const*) (graphics.cpp:257)
==339293==    by 0x176837: CMap::FBitmapShiftBy(int, int) (graphics.cpp:1896)
==339293==    by 0x15468F: DoSize(int, int, int, int) (daedalus.cpp:530)
==339293==    by 0x12FF3F: DoOperation(int, char**, int const*, long const*, _IO_FILE*) (command.cpp:3119)
==339293==    by 0x12EF0E: RunCommandLine(char*, _IO_FILE*) (command.cpp:6166)
==339293==    by 0x15D6D0: main (daedalus.cpp:2942)
==339293==
==339293== Invalid write of size 8
==339293==    at 0x17231C: CMon::BitmapSet(long) (graphics.cpp:1545)
==339293==    by 0x1920F7: CMaz::MazeClear(long) (maze.cpp:210)
==339293==    by 0x139CAD: CMaz::CreateMazePerfect() (create.cpp:205)
==339293==    by 0x12C65E: DoCommand(int) (command.cpp:5301)
==339293==    by 0x12EEAA: RunCommandLine(char*, _IO_FILE*) (command.cpp:6153)
==339293==    by 0x15D6D0: main (daedalus.cpp:2942)
==339293==  Address 0x4db9b54 is 276 bytes inside a block of size 280 alloc'd
==339293==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==339293==    by 0x156212: PAllocate(long) (daedalus.cpp:3014)
==339293==    by 0x17199C: CMon::FAllocate(int, int, CMap const*) (graphics.cpp:257)
==339293==    by 0x176837: CMap::FBitmapShiftBy(int, int) (graphics.cpp:1896)
==339293==    by 0x15468F: DoSize(int, int, int, int) (daedalus.cpp:530)
==339293==    by 0x12FF3F: DoOperation(int, char**, int const*, long const*, _IO_FILE*) (command.cpp:3119)
==339293==    by 0x12EF0E: RunCommandLine(char*, _IO_FILE*) (command.cpp:6166)
==339293==    by 0x15D6D0: main (daedalus.cpp:2942)
==339293==
==339293== Invalid read of size 8
==339293==    at 0x171588: _Get (graphics.h:249)
==339293==    by 0x171588: CMon::Get(int, int) const (graphics.cpp:319)
==339293==    by 0x179966: CMon::WriteText(_IO_FILE*, int, int, int) const (graphics.cpp:2827)
==339293==    by 0x1561E3: FWriteFile(CMaz const&, CMazK const&, int, char const*, char const*) (daedalus.cpp:440)
==339293==    by 0x15D8BB: FFileSave(int, char const*) (daedalus.cpp:3249)
==339293==    by 0x12FD7B: DoOperation(int, char**, int const*, long const*, _IO_FILE*) (command.cpp:3069)
==339293==    by 0x12EF0E: RunCommandLine(char*, _IO_FILE*) (command.cpp:6166)
==339293==    by 0x15D6D0: main (daedalus.cpp:2942)
==339293==  Address 0x4db9b54 is 276 bytes inside a block of size 280 alloc'd
==339293==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==339293==    by 0x156212: PAllocate(long) (daedalus.cpp:3014)
==339293==    by 0x17199C: CMon::FAllocate(int, int, CMap const*) (graphics.cpp:257)
==339293==    by 0x176837: CMap::FBitmapShiftBy(int, int) (graphics.cpp:1896)
==339293==    by 0x15468F: DoSize(int, int, int, int) (daedalus.cpp:530)
==339293==    by 0x12FF3F: DoOperation(int, char**, int const*, long const*, _IO_FILE*) (command.cpp:3119)
==339293==    by 0x12EF0E: RunCommandLine(char*, _IO_FILE*) (command.cpp:6166)
==339293==    by 0x15D6D0: main (daedalus.cpp:2942)
==339293==
==339293== Invalid read of size 8
==339293==    at 0x171588: _Get (graphics.h:249)
==339293==    by 0x171588: CMon::Get(int, int) const (graphics.cpp:319)
==339293==    by 0x179A4A: CMon::WriteText(_IO_FILE*, int, int, int) const (graphics.cpp:2830)
==339293==    by 0x1561E3: FWriteFile(CMaz const&, CMazK const&, int, char const*, char const*) (daedalus.cpp:440)
==339293==    by 0x15D8BB: FFileSave(int, char const*) (daedalus.cpp:3249)
==339293==    by 0x12FD7B: DoOperation(int, char**, int const*, long const*, _IO_FILE*) (command.cpp:3069)
==339293==    by 0x12EF0E: RunCommandLine(char*, _IO_FILE*) (command.cpp:6166)
==339293==    by 0x15D6D0: main (daedalus.cpp:2942)
==339293==  Address 0x4db9b54 is 276 bytes inside a block of size 280 alloc'd
==339293==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==339293==    by 0x156212: PAllocate(long) (daedalus.cpp:3014)
==339293==    by 0x17199C: CMon::FAllocate(int, int, CMap const*) (graphics.cpp:257)
==339293==    by 0x176837: CMap::FBitmapShiftBy(int, int) (graphics.cpp:1896)
==339293==    by 0x15468F: DoSize(int, int, int, int) (daedalus.cpp:530)
==339293==    by 0x12FF3F: DoOperation(int, char**, int const*, long const*, _IO_FILE*) (command.cpp:3119)
==339293==    by 0x12EF0E: RunCommandLine(char*, _IO_FILE*) (command.cpp:6166)
==339293==    by 0x15D6D0: main (daedalus.cpp:2942)
==339293==
==339293==
==339293== HEAP SUMMARY:
==339293==     in use at exit: 32,000 bytes in 1 blocks
==339293==   total heap usage: 7 allocs, 6 frees, 109,897 bytes allocated
==339293==
==339293== LEAK SUMMARY:
==339293==    definitely lost: 0 bytes in 0 blocks
==339293==    indirectly lost: 0 bytes in 0 blocks
==339293==      possibly lost: 0 bytes in 0 blocks
==339293==    still reachable: 32,000 bytes in 1 blocks
==339293==         suppressed: 0 bytes in 0 blocks
==339293== Rerun with --leak-check=full to see details of leaked memory
==339293==
==339293== For lists of detected and suppressed errors, rerun with: -s
==339293== ERROR SUMMARY: 12 errors from 5 contexts (suppressed: 0 from 0)
user@MYLABVM:~/Daedalus-master$

Machine config:

user@MYLABVM:~/Daedalus-master$ uname -a
Linux MYLABVM 5.15.0-76-generic #83~20.04.1-Ubuntu SMP Wed Jun 21 20:23:31 UTC 2023 x86_64 x86_64 x86_64 GNU/Linux
user@MYLABVM:~/Daedalus-master$

Please let me know if you need any more information.

CruiserOne commented 1 year ago

Thank you for the bug report and investigation! Hmm, errors like this shouldn't happen with such basic operations, and don't reproduce in the Windows version.

The function CMon::Set() explicitly checks that the input coordinates are within the bounds of the bitmap, so can't set memory off the edge. Similarly, CMon::BitmapSet() simply loops over the bitmap's memory addresses, so shouldn't set bad memory either. However, I notice the valgrind errors are "Invalid read of size 8" and "Invalid write of size 8". These should only ever be reads and writes of size 4, because the bitmap is an array of unsigned longs (i.e. 32 bit or 4 byte quantities).

Perhaps there's something going on that's making longs size 8, which is causing read/writes to happen one long beyond the end of the allocation? Indeed, one way to avoid the problem is to ensure the vertical size of the bitmap is even, e.g. do "Size 35 36" instead, which should work. (Every bitmap row is some number of longs, so an even row bitmap is guaranteed to have a even number of longs total, or an integer number of 8 byte chunks.) Similarly, the following quick code change should fix the problem too, by padding the memory allocation with an extra long's worth of space:

In daedalus.cpp line 3010, at the start of the function PAllocate(), insert the following line of code: lcb += 4;

vineyy commented 1 year ago

Perhaps there's something going on that's making longs size 8

Mine is a 64-bit Linux so long is 8 byte.

lcb += 4;

With this fix, I did not see any crashes. I ran it with valgrind and there is no invalid read/write now.

CruiserOne commented 1 year ago

Thank you for trying out the fix, and reporting that it works! Since it does work, I will make sure this change is in the next version of Daedalus.