qsa

Is there a patchfile for this patch for latest rev. or something?

Patch in 11th post should be fine, you may have to patch some parts manually tho.

13x13 doesn't work either

Same it doesn't, it looked logical.

Worst case, 16x16 can be used, if nothing better works/found.

I can bet he's using old mmaps with new revision.

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)

(max map tiles)*(our sub tiles) = (64x64)x(16x16) = 2^20 maximal number of tiles possible on single map. With 64 bit polyRef, we can afford it with no problem. So it wont create us any issues.

The only thing worries me is, us, losing really nice optimization we have, not have to generate paths while destination on same polygon as we are. So, small polygons -> less chances for this to happen -> more calculations. But I guess its a price we have to pay.

In 2x2, 8x8, 32x32, all of the tiles are unconnected. I think it's a float precision problem....

It is, GRID_SIZE = 533.33 dividing it by those portions will result in X.666, rounding to X+1, while dividing by 4, 16 will be X.333 rounded to X. There is multiple parts in code where mathematical conversion is used and not ceil/casting float to int. Actually, this is not consistent use, sometimes its round, sometimes its ceil/cast. May need some checking.

Which brings me to next suggestion, using TILES_PER_MMTILE = 13. This value chosen for 3 reasons:

1) it minimize the precision error in this range.

2) it is in 16x16 range - which seems to give nice results.

3) it is slightly bigger tiles, better optimization.

* we don't really have to worry about not using power of 2. The only thing it will change, is us, having less tiles but using same amount of bits to hold them in polyRef. But since we are not in shortage, its fine.

I think I'll push that patch for 64bit polyRef, from post #683.

Push this one and the one for core, to save/load multiple tiles in same file.

Then we'll have something that can be tested + fine-tuned.

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.

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.

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

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.

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.

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.

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.

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.

If you don't mind you can use this hack code to prevent blinking through door that I wrote for my server. It is not recommended for large server because it fetches SQL for object information. If someone can improve this or have better idea feel free to rewrite it.

* this is only half of the code, the minus(deleting) code shouldn't be removed because it is part of my other code, just take a look on the adding parts *

diff --git a/src/game/Spell.cpp b/src/game/Spell.cpp
index 95e6580..85e3867 100644
--- a/src/game/Spell.cpp
+++ b/src/game/Spell.cpp
@@ -4302,24 +4302,43 @@ SpellCastResult Spell::CheckCast(bool strict)
            case SPELL_EFFECT_LEAP:
            case SPELL_EFFECT_TELEPORT_UNITS_FACE_CASTER:
            {
-                float dis = GetSpellRadius(sSpellRadiusStore.LookupEntry(m_spellInfo->EffectRadiusIndex[i]));
-                float fx = m_caster->GetPositionX() + dis * cos(m_caster->GetOrientation());
-                float fy = m_caster->GetPositionY() + dis * sin(m_caster->GetOrientation());
-                // teleport a bit above terrain level to avoid falling below it
-                float fz = m_caster->GetBaseMap()->GetHeight(fx, fy, m_caster->GetPositionZ(), true);
-                if(fz <= INVALID_HEIGHT)                    // note: this also will prevent use effect in instances without vmaps height enabled
-                    return SPELL_FAILED_TRY_AGAIN;
-
-                float caster_pos_z = m_caster->GetPositionZ();
-                // Control the caster to not climb or drop when +-fz > 8
-                if(!(fz <= caster_pos_z + 8 && fz >= caster_pos_z - 8))
-                    return SPELL_FAILED_TRY_AGAIN;
-
                // not allow use this effect at battleground until battleground start
                if(m_caster->GetTypeId() == TYPEID_PLAYER)
                    if(BattleGround const *bg = ((Player*)m_caster)->GetBattleGround())
                        if(bg->GetStatus() != STATUS_IN_PROGRESS)
                            return SPELL_FAILED_TRY_AGAIN;
+
+                //check door
+                bool findDoor = false;
+                float dis = GetSpellRadius(sSpellRadiusStore.LookupEntry(m_spellInfo->EffectRadiusIndex[i]));
+
+                QueryResult *result = WorldDatabase.PQuery("SELECT id, "
+                    "(POW(position_x - '%f', 2) + POW(position_y - '%f', 2) + POW(position_z - '%f', 2)) AS order_ "
+                    "FROM gameobject WHERE map='%u' AND (POW(position_x - '%f', 2) + POW(position_y - '%f', 2) + POW(position_z - '%f', 2)) <= '%f' ORDER BY order_",
+                    m_caster->GetPositionX(), m_caster->GetPositionY(), m_caster->GetPositionZ(),
+                    m_caster->GetMapId(),m_caster->GetPositionX(), m_caster->GetPositionY(), m_caster->GetPositionZ(), dis*dis+5);
+
+                if (result)
+                {
+                    do
+                    {
+                        Field *fields = result->Fetch();
+                        uint32 entry = fields[0].GetUInt32();
+
+                        GameObjectInfo const * pDoor = sObjectMgr.GetGameObjectInfo(entry);
+
+                        if(!pDoor)
+                            continue;
+
+                        if ( pDoor->type == GAMEOBJECT_TYPE_DOOR )
+                            findDoor = true;
+
+                    } while (result->NextRow());
+                    delete result;
+                }
+                if ( findDoor )
+                    return SPELL_FAILED_TRY_AGAIN;
+
                break;
            }
            case SPELL_EFFECT_STEAL_BENEFICIAL_BUFF:

This is usually done by using grid searchers. Just fill the list and check if there are any solid GO intercept with you're blink vector.

Not like thats the real solution, but it sure better then sql query

What number is gravity in wow?

Either there is none, and all things fall at constant speed of about 54y/s or you reach cruise speed very fast.

Actually calculating it, gives something around 8~ but it varies too much when delta changes.

PS: there's missing "(" in my above post just after arcsin.

New map system applied in [10727]. You have to upgrade your patch to make it compatible with new Core. Personal cheers for MMaps

Just moving few things around, no sweat.

Cheers for pushing those changes.

I think that "magic number" is just angle in radians*100, question is, how to calculate it.

out_angle = asin(grav*dist)/(veloc^2))/2

Wasn't following the entire discussion, but there aren't too many angles you can talk about while talking about trajectory.

Sorry in advance if that isn't what you meant.

As long as we have proper destructors, we can print out all remaining non-freed pointers, and where they were allocated from, right before mangos exits (during normal shutdown).

This wont do you any good either ( in some cases ).

Since at full shutdown map destructors are called, freeing all the memory.

We need some luck here, recognizing the exact case when we allocate something and hold it while we don't need it.

I really hope its just plain old memory leak, this way with just tinny luck ( or longer time ) valgrind will catch it, giving much better result. With no additional code.

here is results of 2 starts with around of 5 mins of server work (with incredible lags)....

Thanks for the logs, but they do not contain memory trace.

You should with "valgrind --tool=memcheck --leak-check=yes --show-reachable=yes --num-callers=20 --track-fds=yes" flags.

Thanks.

PS: you better remove those logs...

Can't we use a technique like the one I deleted here?

It would take some code refactoring... replacing calls to dtAlloc and dtFree, but it shouldn't impact performance like Valgrind does.

This wont really help us, but I guess you meant using smart pointers.

But, well, that's exactly the thing, it wont really help us.

Just consider the case, when maps are loaded, but not unloaded. Its not really memory leak, its just bad logic. No automatic tool can handle those.

i think better to start valgrind at another (test) server where max online is 10 ppl coz i never has online below 100 players even at night

well, maybe it can pull 100 on you system for a while.

But running server with really low population wont find anything, I have one

you can run it for an hour at a time, too long logs aren't best either.

using valrgind now... server dies in lags it takes too much CPU time (99-100%)... is there some paramaters to increase perfomance with valgrind using?

now i will try to use this parameters

valgrind --tool=memcheck --leak-check=yes

maybe it will helps...

Not really, you better try those things at night while relatively low online counts. Since anything over 50~ testers is unplayable.

PS: I warned you

If anyone can run under valgrind with TBB disabled! (important), and actually get leak trace, I'll be able to fix it. But prior to that, I cannot even confirm its there

seems it's the time to do it coz still getting these annoying crashes http://paste2.org/p/1089469 http://paste2.org/p/1089476

Good conclusion. Since without solid dumps I can't find it. So far, couple of leaks fixed, but guess, there are more.

I just wonder when they happen. Since with normal play with few users, there are none.

also there is new one http://paste2.org/p/1089477 (never seen this crash before)

This one don't look like it has anything to do with mmaps.

Thanks in advance.

Hello! Can someone please explain to me some things?

Please read the first post in this thread, it contains all the info you need. MCP's above post can also help.

proposed changes to mmtile format:

https://gist.github.com/674959

MoveMap.h is missing from that diff.

Changes looks just fine. Managing of loaded tiles in core looks just a little bit overcomplicated.

Pushing those after tinny local tests can't hurt.

Cheers.

The only way that patch actually fixes something, is if the real bug casts null pointer to some pointer with "this" offset over 10. Can happen only when base class is static, with no virtual functions, while derived class has VPTR table.

If that's the case, just find where the wrong cast is ...

The reason it doesn't fix anything all the time, is that vptr table location varies with compiler.

TIP: you have to rebuild your maps fresh.

oh god... rebuilding again

This is "work in process". Having to re-extract once in a while is better than having no improvements at all

PS: you better keep the old maps too, just in case you will have to revert

and...

linux compilation

config.status: error: cannot find input file: dep/recastnavigation/Makefile.in

ye, my bad, added to repository now.

Was hoping to use recast provided files, but they assume totally different things, and will require to build them first, before mangos. So, I added same files we used to have.

some places where mmaps doesn't works properly and mobs in these zones tries to jump into the air at aggro (even if you trying to attack them from land) and then evades. http://filebeam.com/9c40d57a6c794e296ce5abc3c565a155.jpg

what about this?

One thing at a time, people get used to thing getting solved

Cheers

there is a small bug, see screenshots:

What exactly is the bug?

You generated _some_ "solo mesh tiled" using recastDemo - this mesh has nothing to do with meshes generated and used in this project.

Build recastDemo from our source, then generate maps with debug output using our extractor. Then load them in debug mode.

Only this will give you idea how our actual maps looks like.

Cheers.