[Bug 4.0] Memory Management Issues

[Cyrus Hall]

Ciao -

I compiled the new version out of git on Linux and pretty much immediately ran into issues in game.  First, whenever a new vehicle gets close to it's first station, the game faults:

gdb) bt
#0  0x0000000000456701 in freelist_t::gimme_node (size=4)
    at dataobj/freelist.cc:111
#1  0x00000000005859d2 in haltestelle_t::path::operator new ()
    at simhalt.cc:3855
#2  0x0000000000591ebe in haltestelle_t::calculate_paths (this=0x3a65500, goal=
      {static data = 0x1b2ff90, static next = 18, static size = 1024, entry = 6256}, category=0 '\0') at simhalt.cc:1651
#3  0x0000000000592469 in haltestelle_t::get_path_to (this=0x3a65500, goal=
      {static data = 0x1b2ff90, static next = 18, static size = 1024, entry = 6384}, category=0 '\0') at simhalt.cc:1823
#4  0x00000000005925f3 in haltestelle_t::find_route (this=0x3a65500,
    ziel_list=0x265ede0, ware=@0x7fff61cb1b80, previous_journey_time=65535)
    at simhalt.cc:2032
#5  0x000000000055aff6 in stadt_t::step_passagiere (this=0x283efd0)
    at simcity.cc:2009
#6  0x000000000055ffec in stadt_t::step (this=0x283efd0, delta_t=201)
    at simcity.cc:1450
#7  0x00000000005cd1ce in karte_t::step (this=0x1ea3c10) at simworld.cc:2941
#8  0x00000000005cdfa7 in karte_t::interactive (this=0x1ea3c10)
    at simworld.cc:4656
#9  0x000000000059f47f in simu_main (argc=2, argv=0x7fff61cb40b8)
    at simmain.cc:948
#10 0x00000000006043f4 in main (argc=2, argv=0x7fff61cb40b8) at simsys_s.cc:729

This is on a brand new map.  There are no existing vehicles.

Since it seemed to be a memory problem, I broke out valgrind.  To my horror, I whole spew of problems started to scroll across my screen.  I've uploaded a valgrind trace up until the point of the crash.  Note that the crash happens a bit later in valgrind, which indicates that the problem is indeed memory management related, and that valgrind's buffering of mallocs is hiding the bug seen in the above stack trace.  Never the less, the crash is very close to when the created vehicle reaches the station.  You can grab the trace here:

http://atelier.inf.unisi.ch/~hallc/crash-valgrind

Save game is here:

http://atelier.inf.unisi.ch/~hallc/64-init.sve

I would not be surprised if the result is different on Windows or 32-bit Linux, as memory problems are often exposed by changing architectures.  Hope the traces help - the simutrans memory subsystem appears to be several days of time to learn.  Note that all dumps are from a non-optimized compile - those wouldn't even run.

Better news is that rotation works great. :-)

Cheers,
Pugget

[jamespetts]

Pugget,

thank you very much for your report :-) I know that there have been some problems with 64-bit compiles in the past. To make sure that this really is a Simutrans-Experimental issue, can you try compiling the latest nightly of Simutrans-Standard and see whether it is any better? Thank you very much :-)

[Cyrus Hall]

Frankly, simutrans non-experimental it doesn't build on 64-bit linux at all.  I'm going to try and pinpoint the check-in in the experimental repository where the bug crops up.  If that doesn't work, well, I'll just wait for the 32-bit build.  Or read how to do 32-bit builds on a 64-bit machine.

Cheers,
Pugget

[jamespetts]

Pugget,

I think that Simutrans-Standard was recently fixed to enable it to compile on 64-bit, so you could try that? Otherwise, I'd be very interested to know whether you get the same crash with the 32-bit build when it comes out to-morrow. Thank you very much for your assistance :-)

[Cyrus Hall]

I cloned from the git repository and simutrans standard fails to build in either 16 or 8-bit mode:

hallcp@maya:~/junk/simutrans.git$ make simgraph16.o
===> CXX simgraph16.cc
simgraph16.cc: Assembler messages:
simgraph16.cc:1788: Error: suffix or operands invalid for `jmp'
make: *** [simgraph16.o] Error 1
hallcp@maya:~/junk/simutrans.git$ make simgraph8.o
===> CXX simgraph8.cc
simgraph8.cc:1484: warning: unused parameter 'player'
simgraph8.cc: In function 'int display_calc_proportional_string_len_width(constchar*, int)':
simgraph8.cc:2056: error: cannot convert 'int*' to 'size_t*' for argument '2' to 'utf16 utf8_to_utf16(const utf8*, size_t*)'
simgraph8.cc: In function 'int display_text_proportional_len_clip(KOORD_VAL, KOORD_VAL, const char*, int, PLAYER_COLOR_VAL, int)':
simgraph8.cc:2198: error: cannot convert 'int*' to 'size_t*' for argument '2' to 'utf16 utf8_to_utf16(const utf8*, size_t*)'
make: *** [simgraph8.o] Error 1

I fixed simgraph8 such that all the object files finished compiling, but then the link fails with a list of missing symbols.  In particular:
symbols with the name display_text_proportional_*. 

I'm not going to look into the problem any further at this point and just hope that the 32-bit build works. 

Cheers,
Pugget

[prissi]

You need to add -DUSE_C to the flags of the compiler, since the assembler syntax of the 64Bit version does not work correctly. (That file should be also there for experimental, imho!)

[jamespetts]

Prissi,

how would I do that?

[Cyrus Hall]

James-

I can confirm that this is not a problem with a 64-bit build of simutrans standard.  Thanks for the compile tip prissi.

[jamespetts]

Ahh, thank you for the information. Before I conduct any further investigations, can you check the 32-bit binary and see whether that crashes for you?

[Cyrus Hall]

James-

32-bit version is not yet posted.  However, my repository digging appears to have found the culprit check-in.  Check-in 93720d29c8b5e6c6dad4dbe8bc6087993d57fafe works, more or less, fine.  64b318909fa9ea001b8d3fe35ab83f1f7665468c experiences the issue everytime.  Looking at the diff, there isn't anything obvious.  But 64b3 experiences the crash every time, every map.

Cheers,
Pugget

Edit: I can further report that git revert 64b3[...] does *not* fix the problem.  The mystery continues...

[Cyrus Hall]

James-

Some progress.  I noticed the USE_INDEPENDENT_PATH_POOL define and played with turning it on.  After providing the missing methods path_node::operator new(unsigned long x) and path_node::operator delete(void* x) by using plain malloc and free, and uncommenting line 237 in simhalt.h (a missing data member in struct path_node), the game runs without crashing.  Runs extremely slowly, but runs. 

Cheers,
Pugget

[knightly]

James,

The mechanism of freelist_t is that, when you request a piece of memory, it will return the address of a piece of memory of size equal to a multiple of 4. E.g. requesting a memory of size 3 will give you a piece of 4-byte memory. So, the minimum size is 4 byte.

Another characteristic about freelist_t is that, recycled memory pieces are converted to a (nodelist_node_t *) pointer for storge at each "slot" in all_lists[]. Recycled memory pieces are chained together as a stack. That is, all_lists[1] will point to a chain of recycled memory pieces of size 4.

Under a 32-bit system, pointers are 4-bytes in size, so converting memory pieces into (nodelist_node_t *) pointer will not consitute a problem, because the smallest memory piece in freelist_t has a size of 4. However, under a 64-bit system, a pointer occupy 8 bytes, causing the code to read or write beyond the boundary of a 4-byte memory piece.

You may wonder why the problem doesn't appear in Simutrans Standards. I tested the latest nightly with Wipi's save game for half a game year, and all_lists[1] was still NULL -- this means the smallest memory pieces ever allocated in Simutrans Standard are 8 bytes and thus such problem wasn't triggered. But in Simutrans Experimental, we at least have path objects which uses freelist_t and which are only 4 bytes in size.

I would suggest to add a conditional compiling block which changes the smallest memory piece size to 8 bytes when compiling 64-bit Simutrans. I suppose this should better be done in Simutrans Standard trunk, though.

[Cyrus Hall]

Knightly, James-

Knightly's analysis seemed very likely to be correct, so I went in and made sure all allocations were at least 8 bytes.  I then turned off independent path allocations, recompiled, and bingo, simutrans worked nicely.  So, a simple set of #defines to assure all allocations are 8 bytes on x64 should do the trick.

Cheers,
Pugget

[knightly]

Pugget,

Thanks for your swift testing Are there any other Valgrind warnings after fixing freelist_t? It would help to know if there are any memory leaks. Many thanks in advance!

[jamespetts]

Knightly and Pugget,

thank you both very much for your work on this issue! It is most helpful. In the meantime, I have been re-working the independent pathing pool, so that that now works without error (and gives proper memory pooling for path nodes) when enabled, in case any further problems arise with freelist.

Might I ask two things: firstly, where in the freelist class is the maximum bite size to increase, and, secondly, do either of you know whether there is any way of automatically checking for a 64-bit compiler, or whether I have to define my own #ifdef and instruct all 64-bit people manually to define it?

[Cyrus Hall]

James-

Not sure on a compiler agnostic check.  sizeof could of course work, but it may not be pre-processor macro in all implementations of C.

In terms of where to check, I put in my two line hack on line 208 of freelist.cc:

if(size < 8 ) {
  size = 8;
}

Elegant, I know.

Cheers,
Pugget

[knightly]

James,

Sorry that I can't help with your 2nd question.

As for the 1st one, if I haven't misunderstood your question, I suppose you need to modify the value of size for 64-bit compilations, in both gimme_node() :

void *freelist_t::gimme_node(size_t size)
{
   nodelist_node_t ** list = NULL;
   if(size==0) {
      return NULL;
   }

   // all sizes should be dividable by 4
   size = ((size+3)>>2)<<2;

and putback_node() :

void freelist_t::putback_node( size_t size, void *p )
{
   nodelist_node_t ** list = NULL;
   if(size==0  ||  p==NULL) {
      return;
   }

   // all sizes should be dividable by 4
   size = ((size+3)>>2);

For gimme_node(), whenever calculated size is 4, change it to 8. For putback_node(), size represents size divided by 4, so if size equals 1, change it to 2.