feat(Tools/MMapsGenerator): Improve multithreading of mmaps_generator (#10963)

* cherry-pick commit (https://github.com/Shauren/TrinityCore/commit/699edaa0144fa3b0033dc45e24ad74222cc8240e)

Co-authored-by: Giacomo Pozzoni <giacomopoz@gmail.com>

5 files changed, 252 insertions, 80 deletions

diff --git a/src/cmake/compiler/clang/settings.cmake b/src/cmake/compiler/clang/settings.cmake
index d53c673a94..93e85762e0 100644
--- a/src/cmake/compiler/clang/settings.cmake
+++ b/src/cmake/compiler/clang/settings.cmake
@@ -66,6 +66,52 @@ if(WITH_COREDEBUG)
   message(STATUS "Clang: Debug-flags set (-g3)")
 endif()
 
+if(MSAN)
+    target_compile_options(acore-compile-option-interface
+            INTERFACE
+            -fno-omit-frame-pointer
+            -fsanitize=memory
+            -fsanitize-memory-track-origins
+            -mllvm
+            -msan-keep-going=1)
+
+    target_link_options(acore-compile-option-interface
+            INTERFACE
+            -fno-omit-frame-pointer
+            -fsanitize=memory
+            -fsanitize-memory-track-origins)
+
+    message(STATUS "Clang: Enabled Memory Sanitizer MSan")
+endif()
+
+if(UBSAN)
+    target_compile_options(acore-compile-option-interface
+            INTERFACE
+            -fno-omit-frame-pointer
+            -fsanitize=undefined)
+
+    target_link_options(acore-compile-option-interface
+            INTERFACE
+            -fno-omit-frame-pointer
+            -fsanitize=undefined)
+
+    message(STATUS "Clang: Enabled Undefined Behavior Sanitizer UBSan")
+endif()
+
+if(TSAN)
+    target_compile_options(acore-compile-option-interface
+            INTERFACE
+            -fno-omit-frame-pointer
+            -fsanitize=thread)
+
+    target_link_options(acore-compile-option-interface
+            INTERFACE
+            -fno-omit-frame-pointer
+            -fsanitize=thread)
+
+    message(STATUS "Clang: Enabled Thread Sanitizer TSan")
+endif()
+
 # -Wno-narrowing needed to suppress a warning in g3d
 # -Wno-deprecated-register is needed to suppress gsoap warnings on Unix systems.
 target_compile_options(acore-compile-option-interface
diff --git a/src/cmake/showoptions.cmake b/src/cmake/showoptions.cmake
index 1d2366a281..08467d8df8 100644
--- a/src/cmake/showoptions.cmake
+++ b/src/cmake/showoptions.cmake
@@ -168,6 +168,27 @@ elseif (WITH_DETAILED_METRICS)
   add_definitions(-DWITH_DETAILED_METRICS)
 endif()
 
+if(MSAN)
+    message("")
+    message(" *** MSAN - WARNING!")
+    message(" *** Please note that this is for DEBUGGING WITH MEMORY SANITIZER only!")
+    add_definitions(-DMSAN)
+endif()
+
+if(UBSAN)
+    message("")
+    message(" *** UBSAN - WARNING!")
+    message(" *** Please note that this is for DEBUGGING WITH UNDEFINED BEHAVIOR SANITIZER only!")
+    add_definitions(-DUBSAN)
+endif()
+
+if(TSAN)
+    message("")
+    message(" *** TSAN - WARNING!")
+    message(" *** Please note that this is for DEBUGGING WITH THREAD SANITIZER only!")
+    add_definitions(-DTSAN -DNO_BUFFERPOOL)
+endif()
+
 if(BUILD_SHARED_LIBS)
   message("")
   message(" *** WITH_DYNAMIC_LINKING - INFO!")
diff --git a/src/tools/mmaps_generator/MapBuilder.cpp b/src/tools/mmaps_generator/MapBuilder.cpp
index dcf7f05c50..2b7fdade48 100644
--- a/src/tools/mmaps_generator/MapBuilder.cpp
+++ b/src/tools/mmaps_generator/MapBuilder.cpp
@@ -26,15 +26,43 @@
 
 namespace MMAP
 {
+    TileBuilder::TileBuilder(MapBuilder* mapBuilder, bool skipLiquid, bool bigBaseUnit, bool debugOutput) :
+            m_bigBaseUnit(bigBaseUnit),
+            m_debugOutput(debugOutput),
+            m_mapBuilder(mapBuilder),
+            m_terrainBuilder(nullptr),
+            m_workerThread(&TileBuilder::WorkerThread, this),
+            m_rcContext(nullptr)
+    {
+        m_terrainBuilder = new TerrainBuilder(skipLiquid);
+        m_rcContext = new rcContext(false);
+    }
+
+    TileBuilder::~TileBuilder()
+    {
+        WaitCompletion();
+
+        delete m_terrainBuilder;
+        delete m_rcContext;
+    }
+
+    void TileBuilder::WaitCompletion()
+    {
+        if (m_workerThread.joinable())
+            m_workerThread.join();
+    }
+
     MapBuilder::MapBuilder(Optional<float> maxWalkableAngle, Optional<float> maxWalkableAngleNotSteep, bool skipLiquid,
                            bool skipContinents, bool skipJunkMaps, bool skipBattlegrounds,
-                           bool debugOutput, bool bigBaseUnit, int mapid, const char* offMeshFilePath) :
+                           bool debugOutput, bool bigBaseUnit, int mapid, const char* offMeshFilePath, unsigned int threads) :
 
         m_debugOutput        (debugOutput),
         m_offMeshFilePath    (offMeshFilePath),
+        m_threads            (threads),
         m_skipContinents     (skipContinents),
         m_skipJunkMaps       (skipJunkMaps),
         m_skipBattlegrounds  (skipBattlegrounds),
+        m_skipLiquid         (skipLiquid),
         m_maxWalkableAngle   (maxWalkableAngle),
         m_maxWalkableAngleNotSteep (maxWalkableAngleNotSteep),
         m_bigBaseUnit        (bigBaseUnit),
@@ -48,6 +76,9 @@ namespace MMAP
 
         m_rcContext = new rcContext(false);
 
+        // At least 1 thread is needed
+        m_threads = std::max(1u, m_threads);
+
         discoverTiles();
     }
 
@@ -170,29 +201,26 @@ namespace MMAP
     }
 
     /**************************************************************************/
-    void MapBuilder::buildAllMaps(unsigned int threads)
+    void MapBuilder::buildMaps(Optional<uint32> mapID)
     {
-        printf("Using %u threads to extract mmaps\n", threads);
+        printf("Using %u threads to generate mmaps\n", m_threads);
 
-        for (unsigned int i = 0; i < threads; ++i)
+        for (unsigned int i = 0; i < m_threads; ++i)
         {
-            _workerThreads.emplace_back(&MapBuilder::WorkerThread, this);
+            m_tileBuilders.push_back(new TileBuilder(this, m_skipLiquid, m_bigBaseUnit, m_debugOutput));
         }
 
-        m_tiles.sort([](MapTiles a, MapTiles b)
+        if (mapID)
         {
-            return a.m_tiles->size() > b.m_tiles->size();
-        });
-
-        for (auto & m_tile : m_tiles)
+            buildMap(*mapID);
+        }
+        else
         {
-            uint32 mapId = m_tile.m_mapId;
-            if (!shouldSkipMap(mapId))
+            // Build all maps if no map id has been specified
+            for (TileList::iterator it = m_tiles.begin(); it != m_tiles.end(); ++it)
             {
-                if (threads > 0)
-                    _queue.Push(mapId);
-                else
-                    buildMap(mapId);
+                if (!shouldSkipMap(it->m_mapId))
+                    buildMap(it->m_mapId);
             }
         }
 
@@ -205,10 +233,10 @@ namespace MMAP
 
         _queue.Cancel();
 
-        for (auto& thread : _workerThreads)
-        {
-            thread.join();
-        }
+        for (auto& builder : m_tileBuilders)
+            delete builder;
+
+        m_tileBuilders.clear();
     }
 
     /**************************************************************************/
@@ -337,7 +365,8 @@ namespace MMAP
         getTileBounds(tileX, tileY, data.solidVerts.getCArray(), data.solidVerts.size() / 3, bmin, bmax);
 
         // build navmesh tile
-        buildMoveMapTile(mapId, tileX, tileY, data, bmin, bmax, navMesh);
+        TileBuilder tileBuilder = TileBuilder(this, m_skipLiquid, m_bigBaseUnit, m_debugOutput);
+        tileBuilder.buildMoveMapTile(mapId, tileX, tileY, data, bmin, bmax, navMesh);
         fclose(file);
     }
 
@@ -352,22 +381,39 @@ namespace MMAP
             return;
         }
 
-        buildTile(mapID, tileX, tileY, navMesh);
+        // ToDo: delete the old tile as the user clearly wants to rebuild it
+
+        TileBuilder tileBuilder = TileBuilder(this, m_skipLiquid, m_bigBaseUnit, m_debugOutput);
+        tileBuilder.buildTile(mapID, tileX, tileY, navMesh);
         dtFreeNavMesh(navMesh);
+
+        _cancelationToken = true;
+
+        _queue.Cancel();
     }
 
-    void MapBuilder::WorkerThread()
+    void TileBuilder::WorkerThread()
     {
         while (true)
         {
-            uint32 mapId = 0;
+            TileInfo tileInfo;
+
+            m_mapBuilder->_queue.WaitAndPop(tileInfo);
 
-            _queue.WaitAndPop(mapId);
+            if (m_mapBuilder->_cancelationToken)
+                return;
 
-            if (_cancelationToken)
+            dtNavMesh* navMesh = dtAllocNavMesh();
+            if (!navMesh->init(&tileInfo.m_navMeshParams))
+            {
+                printf("[Map %04i] Failed creating navmesh for tile %i,%i !\n", tileInfo.m_mapId, tileInfo.m_tileX, tileInfo.m_tileY);
+                dtFreeNavMesh(navMesh);
                 return;
+            }
+
+            buildTile(tileInfo.m_mapId, tileInfo.m_tileX, tileInfo.m_tileY, navMesh);
 
-            buildMap(mapId);
+            dtFreeNavMesh(navMesh);
         }
     }
 
@@ -397,22 +443,28 @@ namespace MMAP
                 // unpack tile coords
                 StaticMapTree::unpackTileID(tile, tileX, tileY);
 
-                if (!shouldSkipTile(mapID, tileX, tileY))
-                    buildTile(mapID, tileX, tileY, navMesh);
-
-                ++m_totalTilesProcessed;
+                TileInfo tileInfo;
+                tileInfo.m_mapId = mapID;
+                tileInfo.m_tileX = tileX;
+                tileInfo.m_tileY = tileY;
+                memcpy(&tileInfo.m_navMeshParams, navMesh->getParams(), sizeof(dtNavMeshParams));
+                _queue.Push(tileInfo);
             }
 
             dtFreeNavMesh(navMesh);
         }
-
-        printf("[Map %03i] Complete!\n", mapID);
     }
 
     /**************************************************************************/
-    void MapBuilder::buildTile(uint32 mapID, uint32 tileX, uint32 tileY, dtNavMesh* navMesh)
+    void TileBuilder::buildTile(uint32 mapID, uint32 tileX, uint32 tileY, dtNavMesh* navMesh)
     {
-        printf("%u%% [Map %03i] Building tile [%02u,%02u]\n", percentageDone(m_totalTiles, m_totalTilesProcessed), mapID, tileX, tileY);
+        if(shouldSkipTile(mapID, tileX, tileY))
+        {
+            ++m_mapBuilder->m_totalTilesProcessed;
+            return;
+        }
+
+        printf("%u%% [Map %04i] Building tile [%02u,%02u]\n", m_mapBuilder->currentPercentageDone(), mapID, tileX, tileY);
 
         MeshData meshData;
 
@@ -424,7 +476,10 @@ namespace MMAP
 
         // if there is no data, give up now
         if (!meshData.solidVerts.size() && !meshData.liquidVerts.size())
+        {
+            ++m_mapBuilder->m_totalTilesProcessed;
             return;
+        }
 
         // remove unused vertices
         TerrainBuilder::cleanVertices(meshData.solidVerts, meshData.solidTris);
@@ -436,16 +491,21 @@ namespace MMAP
         allVerts.append(meshData.solidVerts);
 
         if (!allVerts.size())
+        {
+            ++m_mapBuilder->m_totalTilesProcessed;
             return;
+        }
 
         // get bounds of current tile
         float bmin[3], bmax[3];
-        getTileBounds(tileX, tileY, allVerts.getCArray(), allVerts.size() / 3, bmin, bmax);
+        m_mapBuilder->getTileBounds(tileX, tileY, allVerts.getCArray(), allVerts.size() / 3, bmin, bmax);
 
-        m_terrainBuilder->loadOffMeshConnections(mapID, tileX, tileY, meshData, m_offMeshFilePath);
+        m_terrainBuilder->loadOffMeshConnections(mapID, tileX, tileY, meshData, m_mapBuilder->m_offMeshFilePath);
 
         // build navmesh tile
         buildMoveMapTile(mapID, tileX, tileY, meshData, bmin, bmax, navMesh);
+
+        ++m_mapBuilder->m_totalTilesProcessed;
     }
 
     /**************************************************************************/
@@ -524,7 +584,7 @@ namespace MMAP
     }
 
     /**************************************************************************/
-    void MapBuilder::buildMoveMapTile(uint32 mapID, uint32 tileX, uint32 tileY,
+    void TileBuilder::buildMoveMapTile(uint32 mapID, uint32 tileX, uint32 tileY,
                                       MeshData& meshData, float bmin[3], float bmax[3],
                                       dtNavMesh* navMesh)
     {
@@ -549,7 +609,7 @@ namespace MMAP
         const TileConfig tileConfig = TileConfig(m_bigBaseUnit);
         int TILES_PER_MAP = tileConfig.TILES_PER_MAP;
         float BASE_UNIT_DIM = tileConfig.BASE_UNIT_DIM;
-        rcConfig config = GetMapSpecificConfig(mapID, bmin, bmax, tileConfig);
+        rcConfig config = m_mapBuilder->GetMapSpecificConfig(mapID, bmin, bmax, tileConfig);
 
         // this sets the dimensions of the heightfield - should maybe happen before border padding
         rcCalcGridSize(config.bmin, config.bmax, config.cs, &config.width, &config.height);
@@ -852,7 +912,7 @@ namespace MMAP
     }
 
     /**************************************************************************/
-    void MapBuilder::getTileBounds(uint32 tileX, uint32 tileY, float* verts, int vertCount, float* bmin, float* bmax)
+    void MapBuilder::getTileBounds(uint32 tileX, uint32 tileY, float* verts, int vertCount, float* bmin, float* bmax) const
     {
         // this is for elevation
         if (verts && vertCount)
@@ -871,7 +931,7 @@ namespace MMAP
     }
 
     /**************************************************************************/
-    bool MapBuilder::shouldSkipMap(uint32 mapID)
+    bool MapBuilder::shouldSkipMap(uint32 mapID) const
     {
         if (m_mapid >= 0)
             return static_cast<uint32>(m_mapid) != mapID;
@@ -927,7 +987,7 @@ namespace MMAP
     }
 
     /**************************************************************************/
-    bool MapBuilder::isTransportMap(uint32 mapID)
+    bool MapBuilder::isTransportMap(uint32 mapID) const
     {
         switch (mapID)
         {
@@ -967,7 +1027,7 @@ namespace MMAP
     }
 
     /**************************************************************************/
-    bool MapBuilder::shouldSkipTile(uint32 mapID, uint32 tileX, uint32 tileY)
+    bool TileBuilder::shouldSkipTile(uint32 mapID, uint32 tileX, uint32 tileY) const
     {
         char fileName[255];
         sprintf(fileName, "mmaps/%03u%02i%02i.mmtile", mapID, tileY, tileX);
@@ -990,7 +1050,7 @@ namespace MMAP
         return true;
     }
 
-    rcConfig MapBuilder::GetMapSpecificConfig(uint32 mapID, float bmin[3], float bmax[3], const TileConfig &tileConfig)
+    rcConfig MapBuilder::GetMapSpecificConfig(uint32 mapID, float bmin[3], float bmax[3], const TileConfig &tileConfig) const
     {
         rcConfig config;
         memset(&config, 0, sizeof(rcConfig));
@@ -1039,11 +1099,16 @@ namespace MMAP
     }
 
     /**************************************************************************/
-    uint32 MapBuilder::percentageDone(uint32 totalTiles, uint32 totalTilesBuilt)
+    uint32 MapBuilder::percentageDone(uint32 totalTiles, uint32 totalTilesBuilt) const
     {
         if (totalTiles)
             return totalTilesBuilt * 100 / totalTiles;
 
         return 0;
     }
+
+    uint32 MapBuilder::currentPercentageDone() const
+    {
+        return percentageDone(m_totalTiles, m_totalTilesProcessed);
+    }
 }
diff --git a/src/tools/mmaps_generator/MapBuilder.h b/src/tools/mmaps_generator/MapBuilder.h
index 239553891d..e36e1117fb 100644
--- a/src/tools/mmaps_generator/MapBuilder.h
+++ b/src/tools/mmaps_generator/MapBuilder.h
@@ -94,64 +94,102 @@ namespace MMAP
         int TILES_PER_MAP;
     };
 
+    struct TileInfo
+    {
+        TileInfo() : m_mapId(uint32(-1)), m_tileX(), m_tileY(), m_navMeshParams() {}
+
+        uint32 m_mapId;
+        uint32 m_tileX;
+        uint32 m_tileY;
+        dtNavMeshParams m_navMeshParams;
+    };
+
+    // ToDo: move this to its own file. For now it will stay here to keep the changes to a minimum, especially in the cpp file
+    class MapBuilder;
+    class TileBuilder
+    {
+    public:
+        TileBuilder(MapBuilder* mapBuilder,
+                    bool skipLiquid,
+                    bool bigBaseUnit,
+                    bool debugOutput);
+
+        TileBuilder(TileBuilder&&) = default;
+        ~TileBuilder();
+
+        void WorkerThread();
+        void WaitCompletion();
+
+        void buildTile(uint32 mapID, uint32 tileX, uint32 tileY, dtNavMesh* navMesh);
+        // move map building
+        void buildMoveMapTile(uint32 mapID,
+                              uint32 tileX,
+                              uint32 tileY,
+                              MeshData& meshData,
+                              float bmin[3],
+                              float bmax[3],
+                              dtNavMesh* navMesh);
+
+        bool shouldSkipTile(uint32 mapID, uint32 tileX, uint32 tileY) const;
+
+    private:
+        bool m_bigBaseUnit;
+        bool m_debugOutput;
+
+        MapBuilder* m_mapBuilder;
+        TerrainBuilder* m_terrainBuilder;
+        std::thread m_workerThread;
+        // build performance - not really used for now
+        rcContext* m_rcContext;
+    };
+
     class MapBuilder
     {
+        friend class TileBuilder;
     public:
         MapBuilder(Optional<float> maxWalkableAngle,
                    Optional<float> maxWalkableAngleNotSteep,
-                   bool skipLiquid          = false,
-                   bool skipContinents      = false,
-                   bool skipJunkMaps        = true,
-                   bool skipBattlegrounds   = false,
-                   bool debugOutput         = false,
-                   bool bigBaseUnit         = false,
-                   int mapid                = -1,
-                   const char* offMeshFilePath = nullptr);
+                   bool skipLiquid,
+                   bool skipContinents,
+                   bool skipJunkMaps,
+                   bool skipBattlegrounds,
+                   bool debugOutput,
+                   bool bigBaseUnit,
+                   int mapid,
+                   char const* offMeshFilePath,
+                   unsigned int threads);
 
         ~MapBuilder();
 
-        // builds all mmap tiles for the specified map id (ignores skip settings)
-        void buildMap(uint32 mapID);
         void buildMeshFromFile(char* name);
 
         // builds an mmap tile for the specified map and its mesh
         void buildSingleTile(uint32 mapID, uint32 tileX, uint32 tileY);
 
         // builds list of maps, then builds all of mmap tiles (based on the skip settings)
-        void buildAllMaps(unsigned int threads);
-
-        void WorkerThread();
+        void buildMaps(Optional<uint32> mapID);
 
     private:
+        // builds all mmap tiles for the specified map id (ignores skip settings)
+        void buildMap(uint32 mapID);
         // detect maps and tiles
         void discoverTiles();
         std::set<uint32>* getTileList(uint32 mapID);
 
         void buildNavMesh(uint32 mapID, dtNavMesh*& navMesh);
 
-        void buildTile(uint32 mapID, uint32 tileX, uint32 tileY, dtNavMesh* navMesh);
-
-        // move map building
-        void buildMoveMapTile(uint32 mapID,
-                              uint32 tileX,
-                              uint32 tileY,
-                              MeshData& meshData,
-                              float bmin[3],
-                              float bmax[3],
-                              dtNavMesh* navMesh);
-
         void getTileBounds(uint32 tileX, uint32 tileY,
                            float* verts, int vertCount,
-                           float* bmin, float* bmax);
+                           float* bmin, float* bmax) const;
         void getGridBounds(uint32 mapID, uint32& minX, uint32& minY, uint32& maxX, uint32& maxY) const;
 
-        bool shouldSkipMap(uint32 mapID);
-        bool isTransportMap(uint32 mapID);
-        bool shouldSkipTile(uint32 mapID, uint32 tileX, uint32 tileY);
+        bool shouldSkipMap(uint32 mapID) const;
+        bool isTransportMap(uint32 mapID) const;
 
-        rcConfig GetMapSpecificConfig(uint32 mapID, float bmin[3], float bmax[3], const TileConfig &tileConfig);
+        rcConfig GetMapSpecificConfig(uint32 mapID, float bmin[3], float bmax[3], const TileConfig &tileConfig) const;
 
-        uint32 percentageDone(uint32 totalTiles, uint32 totalTilesDone);
+        uint32 percentageDone(uint32 totalTiles, uint32 totalTilesDone) const;
+        uint32 currentPercentageDone() const;
 
         TerrainBuilder* m_terrainBuilder{nullptr};
         TileList m_tiles;
@@ -159,9 +197,11 @@ namespace MMAP
         bool m_debugOutput;
 
         const char* m_offMeshFilePath;
+        unsigned int m_threads;
         bool m_skipContinents;
         bool m_skipJunkMaps;
         bool m_skipBattlegrounds;
+        bool m_skipLiquid;
 
         Optional<float> m_maxWalkableAngle;
         Optional<float> m_maxWalkableAngleNotSteep;
@@ -174,8 +214,8 @@ namespace MMAP
         // build performance - not really used for now
         rcContext* m_rcContext{nullptr};
 
-        std::vector<std::thread> _workerThreads;
-        ProducerConsumerQueue<uint32> _queue;
+        std::vector<TileBuilder*> m_tileBuilders;
+        ProducerConsumerQueue<TileInfo> _queue;
         std::atomic<bool> _cancelationToken;
     };
 }
diff --git a/src/tools/mmaps_generator/PathGenerator.cpp b/src/tools/mmaps_generator/PathGenerator.cpp
index 18e070ae48..469ff79845 100644
--- a/src/tools/mmaps_generator/PathGenerator.cpp
+++ b/src/tools/mmaps_generator/PathGenerator.cpp
@@ -328,7 +328,7 @@ int main(int argc, char** argv)
     }
 
     MapBuilder builder(maxAngle, maxAngleNotSteep, skipLiquid, skipContinents, skipJunkMaps,
-                       skipBattlegrounds, debugOutput, bigBaseUnit, mapnum, offMeshInputPath);
+                       skipBattlegrounds, debugOutput, bigBaseUnit, mapnum, offMeshInputPath, threads);
 
     uint32 start = getMSTime();
     if (file)
@@ -336,9 +336,9 @@ int main(int argc, char** argv)
     else if (tileX > -1 && tileY > -1 && mapnum >= 0)
         builder.buildSingleTile(mapnum, tileX, tileY);
     else if (mapnum >= 0)
-        builder.buildMap(uint32(mapnum));
+        builder.buildMaps(uint32(mapnum));
     else
-        builder.buildAllMaps(threads);
+        builder.buildMaps({});
 
     if (!silent)
         printf("Finished. MMAPS were built in %u ms!\n", GetMSTimeDiffToNow(start));