MMaps Redux

[faramir118]

Updated to [10727], some compatibility changes applied in 7b836bc57

[KAPATEJIb]

Seems these memory leaks are disappeared after i start to compile my server with USE_STANDARD_MALLOC or i just can't reproduce it now

[faramir118]

Hopefully fixed in 26c0b1795

BUT: I'm unsure of how to handle case where USE_STANDARD_MALLOC is defined (mainly because I'm not sure where USE_STANDARD_MALLOC is expected to be defined - compiler setting for project/library, header, ?)

Would this work?

#ifndef USE_STANDARD_MALLOC
   ///- Initialize detour memory management
   dtAllocSetCustom(dtCustomAlloc, dtCustomFree);
#endif

[DasBlub]

afaik you normally set the USE_STANDARD_MALLOC when you call the compiler, so you'd compile with -DUSE_STANDARD_MALLOC, but no guaranties for that and i don't know exactly how it'd be done on windows (though i'm working on windows, but i've never done it)

[KAPATEJIb]

Hopefully fixed in 26c0b1795

BUT: I'm unsure of how to handle case where USE_STANDARD_MALLOC is defined (mainly because I'm not sure where USE_STANDARD_MALLOC is expected to be defined - compiler setting for project/library, header, ?)

Would this work?

#ifndef USE_STANDARD_MALLOC
   ///- Initialize detour memory management
   dtAllocSetCustom(dtCustomAlloc, dtCustomFree);
#endif

i'm using this

diff --git a/src/framework/Policies/MemoryManagement.cpp b/src/framework/Policies/MemoryManagement.cpp
index fcf41a8..4450b8c 100644
--- a/src/framework/Policies/MemoryManagement.cpp
+++ b/src/framework/Policies/MemoryManagement.cpp
@@ -18,6 +18,7 @@

//lets use Intel scalable_allocator by default and
//switch to OS specific allocator only when _STANDARD_MALLOC is defined
+#define USE_STANDARD_MALLOC
#ifndef USE_STANDARD_MALLOC

#include "../../dep/tbb/include/tbb/scalable_allocator.h"

but this will disable TBB at windows too ^^

[faramir118]

gcc:

autoconf adds a compiler flag when you use --with-std-malloc yes

vc:

You need the define on both the framework project and game project

If you put the define in the src, it needs to be something that is included by MemoryManagement.cpp, MoveMap.h, and World.cpp (so that you don't get linking errors, or have detour using scalable_malloc and mangos using malloc).

I defer to the devs on this one...

[qsa]

Much better question is : why can't TBB coexist with system's standard allocation.

Lets assume this is the case, then why don't we have exactly the same problem with other 3rd party libs, g3dlite for example?

What I'm really saying here, is that, we are too swift to blame it on TBB.

[darkstalker]

TBB is used on all the C++ memory allocation (new, delete) since if redefines the global "void* operator new" (see framework/Policies/MemoryManagement.cpp). This overrides default standard library memory allocation with a custom one. Its a link-time process.

Two kinds of memory management can coexist if you don't mix them (like allocating with malloc and freeing with operator delete). Probably the detour library comes with an "optimized malloc" for people who doesn't care about memory management, but in our case we doing it, so the best would be disable it so it uses TBB. Maybe this will require extra work since if you're using malloc-like functions to get memory then you need placement new to create objects on it.

[qsa]

TBB is used on all the C++ memory allocation (new, delete) since if redefines the global "void* operator new" (see framework/Policies/MemoryManagement.cpp). This overrides default standard library memory allocation with a custom one. Its a link-time process.

You misunderstood my question.

Its scope only where it is defined. All 3rd party libs use their own or system default yet, we don't have problem with them. So this doesn't answer my question.

PS: Detour doesn't come with anything, by default it uses systems malloc/free, nor the calls are messed.

[faramir118]

From what I've looked at...

For g3dlite, only G3D::Array, G3D::Table, and G3D::Data classes use a non-standard memory manager, but I don't think we use those in mangos.

Similarly, ACE seems to do all of its allocations with ACE_New_Allocator::malloc (by default), which uses operator new, which is defined in MemoryManager.cpp to use scalable_malloc

Obviously, I can't be 100% sure.

But since you asked, and I did all this digging, I found out we should just make our dtCustomAlloc use operator new.

[Ambal]

Similarly, ACE seems to do all of its allocations with ACE_New_Allocator::malloc (by default), which uses operator new, which is defined in MemoryManager.cpp to use scalable_malloc

This function is PRIVATE to ACE.dll so changes in MemoryManager.cpp do not interfere with ACE internal memory management. Also, be very careful mixing malloc/free with operators new/delete and any custom functions to allocate/deallocate memory - you can get in BIG trouble doing this.

[faramir118]

I ignored that they are linked separately... oops.

Since ACE uses unmodified new, qsa is correct - it probably isn't tbb.

I reverted the change, since we need more information about this leak. Personally, I'm unable to replicate it.

[Ambal]

Compile w/o TBB memory manager and try to find the leak again - this way there won't be any additional components which could lead to faulty results.

[qsa]

Thats the problem, we even cannot confirm there's a problem

I'm not saying KAPATEJIb's report isn't accurate. I'm just saying that we either have a leak and it needs very specific situation to appear, or we don't have any, and all the symptoms was due to something totally unrelated to mmaps.

More testing on more systems will surely be handy here. I'm having really hard time to belive only KAPATEJIb and Wojta test this patch. Actually, I know it isn't the case

Don't be shy guys, post your results. The faster you report something, the faster it will be solved.

If you don't post, we assume everything if fine. But in this case, even positive results are needed.

faramir118: I think having Detour using TBB allocations isn't bad idea.

Not exactly the code you revert, since it wont work if TBB is disabled, but instead using "return scalable_malloc(size);" we can use "return new..." so it will work properly regardless of configuration.

[qsa]

Below migration to 64bit polyRef patch.

diff --git a/contrib/mmap/src/MapBuilder.cpp b/contrib/mmap/src/MapBuilder.cpp
index e7fc2e3..43efd5b 100644
--- a/contrib/mmap/src/MapBuilder.cpp
+++ b/contrib/mmap/src/MapBuilder.cpp
@@ -641,9 +641,12 @@ namespace MMAP
        set<uint32>* tiles = getTileList(mapID);

        /*** calculate number of bits needed to store tiles & polys ***/
-        int tileBits = rcMin((int)dtIlog2(dtNextPow2(tiles->size())), 12);
-        if (tileBits < 1) tileBits = 1;                                     // need at least one bit!
-        int polyBits = sizeof(dtPolyRef)*8 - SALT_MIN_BITS - tileBits;
+        int tileBits = STATIC_TILE_BITS;    //rcMin((int)dtIlog2(dtNextPow2(tiles->size())), 12);
+        //if (tileBits < 1) tileBits = 1;                                     // need at least one bit!
+        int polyBits = STATIC_POLY_BITS;    //sizeof(dtPolyRef)*8 - SALT_MIN_BITS - tileBits;
+
+        // we cannot have over 31 bits for either tile or poly due to assumptions like this
+        // which are all over the code!
        int maxTiles = 1 << tileBits;
        int maxPolysPerTile = 1 << polyBits;

diff --git a/dep/recastnavigation/Detour/Include/DetourNavMesh.h b/dep/recastnavigation/Detour/Include/DetourNavMesh.h
index 889563c..25f85c4 100644
--- a/dep/recastnavigation/Detour/Include/DetourNavMesh.h
+++ b/dep/recastnavigation/Detour/Include/DetourNavMesh.h
@@ -21,14 +21,26 @@

#include "DetourAlloc.h"

+#ifdef WIN32
+    typedef unsigned __int64   uint64;
+#else
+#include <stdint.h>
+#ifndef uint64_t 
+#ifdef __linux__
+#include <linux/types.h> 
+#endif
+#endif
+    typedef uint64_t           uint64;
+#endif
+
// Note: If you want to use 64-bit refs, change the types of both dtPolyRef & dtTileRef.
// It is also recommended to change dtHashRef() to proper 64-bit hash too.

// Reference to navigation polygon.
-typedef unsigned int dtPolyRef;
+typedef uint64 dtPolyRef;

// Reference to navigation mesh tile.
-typedef unsigned int dtTileRef;
+typedef uint64 dtTileRef;

// Maximum number of vertices per navigation polygon.
static const int DT_VERTS_PER_POLYGON = 6;
@@ -45,7 +57,9 @@ static const unsigned int DT_OFFMESH_CON_BIDIR = 1;

static const int DT_MAX_AREAS = 64;

-static const int SALT_MIN_BITS = 4;
+static const int SALT_MIN_BITS = 10;
+static const int STATIC_TILE_BITS = 23;
+static const int STATIC_POLY_BITS = 31;

// Flags for addTile
enum dtTileFlags
diff --git a/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp b/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp
index a0a8310..2c1ac03 100644
--- a/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp
+++ b/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp
@@ -204,9 +204,9 @@ dtStatus dtNavMesh::init(const dtNavMeshParams* params)
    }

    // Init ID generator values.
-    m_tileBits = dtIlog2(dtNextPow2((unsigned int)params->maxTiles));
-    m_polyBits = dtIlog2(dtNextPow2((unsigned int)params->maxPolys));
-    m_saltBits = 32 - m_tileBits - m_polyBits;
+    m_tileBits = STATIC_TILE_BITS;    //dtIlog2(dtNextPow2((unsigned int)params->maxTiles));
+    m_polyBits = STATIC_POLY_BITS;    //dtIlog2(dtNextPow2((unsigned int)params->maxPolys));
+    m_saltBits = sizeof(dtPolyRef)*8 - m_tileBits - m_polyBits;
    if (m_saltBits < SALT_MIN_BITS)
        return DT_FAILURE;

diff --git a/dep/recastnavigation/Detour/Source/DetourNode.cpp b/dep/recastnavigation/Detour/Source/DetourNode.cpp
index 7b4d94a..0d1af83 100644
--- a/dep/recastnavigation/Detour/Source/DetourNode.cpp
+++ b/dep/recastnavigation/Detour/Source/DetourNode.cpp
@@ -24,13 +24,13 @@

inline unsigned int dtHashRef(dtPolyRef a)
{
-    a += ~(a<<15);
-    a ^=  (a>>10);
-    a +=  (a<<3);
-    a ^=  (a>>6);
-    a += ~(a<<11);
-    a ^=  (a>>16);
-    return (unsigned int)a;
+    a = (~a) + (a << 18);
+    a = a ^ (a >> 31);
+    a = a * 21;
+    a = a ^ (a >> 11);
+    a = a + (a << 6);
+    a = a ^ (a >> 22);
+    return (unsigned int)a;
}

//////////////////////////////////////////////////////////////////////////////////////////

I had to hardcode the bits assigned to poly and to tile.

This is done to simplify the code. Since, all the code, assumes that there less than 2^31 tiles or polygons.

We are fine with this assumption. The only problem is at Detour side, not taking this limitation into account.

Maybe I'll make a patch for Mikko's repo later. The problem (from his perspective) is on 32bit systems, he keeps things like "polyCount" in integers, limiting the real range to 2^31 as mentioned above, while the rest of the code assumes any number of bits.

The hash used is narrowing one, 64bit into 32bit, but it should work just fine on 64bit systems as well.

PS: didn't want to push it into repo just yet, since right now we don't really need. We wont need it till we split tiles as planed.

[qsa]

Below patch allows Detour use TBB allocations when globally enabled.

Same idea we spoke about in post #682. Based on faramir118's revision.

diff --git a/src/game/Makefile.am b/src/game/Makefile.am
index dc1942f..5dcf273 100644
--- a/src/game/Makefile.am
+++ b/src/game/Makefile.am
@@ -186,6 +186,7 @@ libmangosgame_a_SOURCES = \\
    MotionMaster.cpp \\
    MotionMaster.h \\
    MoveMap.cpp \\
+    MoveMap.h \\
    MovementGenerator.cpp \\
    MovementGenerator.h \\
    MovementGeneratorImpl.h \\
diff --git a/src/game/MoveMap.h b/src/game/MoveMap.h
new file mode 100644
index 0000000..6e243fe
--- /dev/null
+++ b/src/game/MoveMap.h
@@ -0,0 +1,34 @@
+/*
+ * Copyright (C) 2005-2010 MaNGOS <http://getmangos.eu/>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#ifndef _MOVE_MAP_H
+#define _MOVE_MAP_H
+
+#include "../../dep/recastnavigation/Detour/Include/DetourAlloc.h"
+
+inline void* dtCustomAlloc(int size, dtAllocHint hint)
+{
+    return (void*)new unsigned char[size*sizeof(char)];
+}
+
+inline void dtCustomFree(void* ptr)
+{
+    delete [] ptr;
+}
+
+#endif
diff --git a/src/game/World.cpp b/src/game/World.cpp
index c1a03a1..56beecd 100644
--- a/src/game/World.cpp
+++ b/src/game/World.cpp
@@ -61,6 +61,8 @@
#include "Util.h"
#include "CharacterDatabaseCleaner.h"

+#include "MoveMap.h"
+
INSTANTIATE_SINGLETON_1( World );

volatile bool World::m_stopEvent = false;
@@ -884,6 +886,9 @@ void World::SetInitialWorldSettings()
    ///- Time server startup
    uint32 uStartTime = getMSTime();

+    ///- Initialize detour memory management
+    dtAllocSetCustom(dtCustomAlloc, dtCustomFree);
+
    ///- Initialize config settings
    LoadConfigSettings();

diff --git a/win/VC100/game.vcxproj b/win/VC100/game.vcxproj
index e0b24ab..b431800 100644
--- a/win/VC100/game.vcxproj
+++ b/win/VC100/game.vcxproj
@@ -578,6 +578,7 @@
    <ClInclude Include="..\\..\\src\\game\\MapReference.h" />
    <ClInclude Include="..\\..\\src\\game\\MapRefManager.h" />
    <ClInclude Include="..\\..\\src\\game\\MotionMaster.h" />
+    <ClInclude Include="..\\..\\src\\game\\MoveMap.h" />
    <ClInclude Include="..\\..\\src\\game\\MovementGenerator.h" />
    <ClInclude Include="..\\..\\src\\game\\NPCHandler.h" />
    <ClInclude Include="..\\..\\src\\game\\NullCreatureAI.h" />
diff --git a/win/VC100/game.vcxproj.filters b/win/VC100/game.vcxproj.filters
index 2a47dd1..ad4b70c 100644
--- a/win/VC100/game.vcxproj.filters
+++ b/win/VC100/game.vcxproj.filters
@@ -844,5 +844,8 @@
    <ClInclude Include="..\\..\\src\\game\\Camera.h">
      <Filter>Object</Filter>
    </ClInclude>
+    <ClInclude Include="..\\..\\src\\game\\MoveMap.h">
+      <Filter>World/Handlers</Filter>
+    </ClInclude>
  </ItemGroup>
</Project>
\\ No newline at end of file
diff --git a/win/VC90/game.vcproj b/win/VC90/game.vcproj
index 7832487..952439b 100644
--- a/win/VC90/game.vcproj
+++ b/win/VC90/game.vcproj
@@ -851,6 +851,10 @@
                >
            </File>
            <File
+                RelativePath="..\\..\\src\\game\\MoveMap.h"
+                >
+            </File>
+            <File
                RelativePath="..\\..\\src\\game\\MovementHandler.cpp"
                >
            </File>

Best regards.

[KAPATEJIb]

seems leak isn't fixed by disabling TBB %) i have first crash for 4 days and it crashed with 2964 Mbytes dump http://paste2.org/p/1098467

at TerrainInfo::Load

pMap = (GridMap *) 0x0 - it's ok?

EDIT:

and another crash, but not caused by leak now http://paste2.org/p/1098620

source files ofc more recent (as said in dump), but nothing related to mmaps changed, only spell fixes added.

[qsa]

seems leak isn't fixed by disabling TBB %) i have first crash for 4 days and it crashed with 2964 Mbytes dump http://paste2.org/p/1098467

at TerrainInfo::Load

pMap = (GridMap *) 0x0 - it's ok?

the null there is Ok,

but.. well, how do I put it, mangos getting to 3giga memory usage isn't nothing new.

Even without any memory leaks. That's the fact.

I don't know why on your system after it reaches maximal physical memory, mallocs fails. It may have something to do with your particular system.

The only thing I can suggest is using patch from post #684. It will change malloc use in favor of system's new, or TTB allocation, if you have it enabled.

Try it, with and w/o TTB, maybe it helps you.

EDIT:

and another crash, but not caused by leak now http://paste2.org/p/1098620

source files ofc more recent (as said in dump), but nothing related to mmaps changed, only spell fixes added.

Same problem as we used to have, too many polygons on some tile. Try patch in #683 post. It isn't very well tested, but should work. You'll have to re-extract all your maps

About supposed memory leaks : I'm still waiting for those valgrind logs

[cyberium]

I don't know why on your system after it reaches maximal physical memory, mallocs fails. It may have something to do with your particular system.

Traditionaly due to pagefile disabled.

That can explain why, anyway 4 day uptime is not bad at all with more than 500 users.

Greetings

[qsa]

I don't know why on your system after it reaches maximal physical memory, mallocs fails. It may have something to do with your particular system.

Traditionaly due to pagefile disabled.

That can explain why, anyway 4 day uptime is not bad at all with more than 500 users.

Greetings

Same logic says new operators should fail too, but it doesn't throw any exceptions, while malloc just return's null pointers.

Well, actually maybe new does throw something, but system may handle it differently, but mehh... I'm not going to debug it.

[faramir118]

pMap = (GridMap *) 0x0 - it's ok?

That just means it hadn't been loaded yet. The next frame on the stack (#5) is where it gets loaded:

at GridMap.cpp:1124

map = (GridMap *) 0x95a9b5c0

and another crash, but not caused by leak now http://paste2.org/p/1098620

Any idea what map? If not I'll find it myself eventually

Well, actually maybe new does throw something, but system may handle it differently

Probably better to use this:

return (void*)new (std::nothrow) unsigned char[size];

When allocation fails, nothrow returns null instead of throwing an exception

And I think that your sizeof(char) is redundant - there is implicit sizeof(unsigned char). And the standard says it's supposed to be 1 anyway

[KAPATEJIb]

Traditionaly due to pagefile disabled.

Never heard about this can you explain what it does and how to enable it? I'm still newb in linux...

Any idea what map?

i don't know where it happen... using logfile level 0

[qsa]

Probably better to use this:

return (void*)new (std::nothrow) unsigned char[size];

When allocation fails, nothrow returns null instead of throwing an exception

Actually, I do want it to throw exceptions just like system new does. Then we'll be able to remove all those null asserts. Its not like we can recover for memory allocation failure anyway.

And I think that your sizeof(char) is redundant - there is implicit sizeof(unsigned char). And the standard says it's supposed to be 1 anyway

You are right, its bullshit code, guess I was thinking about malloc when I wrote it

I think I'll push it after all, the only way to get it really tested

and maybe those 64bit polyRef, any objections?

Never heard about this can you explain what it does and how to enable it? I'm still newb in linux...

I seriously doubt that's your issue, but this like will help you : http://linux.about.com/od/linux101/l/blnewbie4_2_13.htm just in case you still want to mess with it.

[DuB]

hi everybody

can someone help me?

if I use git pull git://github.com/faramir118/mangos.git

I get a error, says some files need merging

I use playerbot by blueboy and ahbot by cyberium and the newest mangos

how to merge or how to solve problem?

[faramir118]

Having an issue with multiple dtTiles per mmtile...

White lines indicate tile connection.

Heavy blue lines indicate a tile edge that is unconnected.

2x2

4x4

8x8

16x16

32x32

64x64

In 2x2, 8x8, 32x32, all of the tiles are unconnected. I think it's a float precision problem, but it's hard to tell since higher tile counts work normally.

This leaves us with 4x4 or 16x16, unless I manage to correct the problem (64x64 was just for giggles ).

Haven't done the math (too lazy) but I don't think it 16x16 is too much for 64bit refs. However, it does create some stupid detours (that visibility optimization trick would fix it)

edit: also noticed that with smaller dtTiles, there are extra sections of navmesh on those mountains.

edit2: changes here