Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Memory Leaks #11

Closed
sivetic opened this issue Sep 29, 2011 · 4 comments
Closed

Memory Leaks #11

sivetic opened this issue Sep 29, 2011 · 4 comments
Assignees
@DennisOSRM
Milestone
0.3

Comments

@sivetic
Copy link
Contributor

sivetic commented Sep 29, 2011

I've been struggling to find a memory leak in extractor that causes the process to eat up excessive amounts of memory on Windows and eventually crash. I've only run into the problem when processing a large file (I'm trying a North America extract, which is just shy of 5GB). I've spent a few hours trying to track the leak down with little success. The leak isn't specific to Windows, as I can see data lost when running extractor through valgrind (I've attached the output). I have not managed to parse the entire 5GB file when running through valgrind (last attempt was over 24 hours and running, had to kill the process), so I've used a smaller PBF file, which is only 3MB.

Note: valgrind run was done with the unmodified version (before my Windows commit) of OSRM to eliminate any issues that may have been introduced with my Windows changes. Both extractor runs were done on the same pbf file (3MB).

Relevant output from valgrind:

==25520==
==25520== HEAP SUMMARY:
==25520==     in use at exit: 174,255 bytes in 4,015 blocks
==25520==   total heap usage: 1,750,355 allocs, 1,746,340 frees, 667,610,759 bytes allocated
==25520==
==25520== Thread 1:
==25520== 60 bytes in 1 blocks are still reachable in loss record 1 of 6
==25520==    at 0x4026864: malloc (vg_replace_malloc.c:236)
==25520==    by 0x4419B41: ??? (in /usr/lib/i386-linux-gnu/libgomp.so.1.0.0)
==25520==    by 0x441FA82: ??? (in /usr/lib/i386-linux-gnu/libgomp.so.1.0.0)
==25520==    by 0x441AB3C: omp_set_num_threads (in /usr/lib/i386-linux-gnu/libgomp.so.1.0.0)
==25520==    by 0x8079BED: main (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==
==25520== 140 bytes in 1 blocks are indirectly lost in loss record 2 of 6
==25520==    at 0x402641D: operator new(unsigned int) (vg_replace_malloc.c:255)
==25520==    by 0x43929F7: std::string::_Rep::_S_create(unsigned int, unsigned int, std::allocator<char> const&) (in /usr/lib/i386-linux-gnu/libstdc++.so.6.0.14)
==25520==    by 0x4394C33: char* std::string::_S_construct<char const*>(char const*, char const*, std::allocator<char> const&, std::forward_iterator_tag) (in /usr/lib/i386-linux-gnu/libstdc++.so.6.0.14)
==25520==    by 0x43953C4: std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(char const*, std::allocator<char> const&) (in /usr/lib/i386-linux-gnu/libstdc++.so.6.0.14)
==25520==    by 0x8065CAB: GetRandomString() (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==    by 0x8079811: main (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==
==25520== 192 bytes in 1 blocks are still reachable in loss record 3 of 6
==25520==    at 0x4026864: malloc (vg_replace_malloc.c:236)
==25520==    by 0x4419B41: ??? (in /usr/lib/i386-linux-gnu/libgomp.so.1.0.0)
==25520==    by 0x441F7DE: ??? (in /usr/lib/i386-linux-gnu/libgomp.so.1.0.0)
==25520==    by 0x441E21D: GOMP_parallel_start (in /usr/lib/i386-linux-gnu/libgomp.so.1.0.0)
==25520==    by 0x80B2E07: PBFParser::Parse() (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==    by 0x8079C80: main (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==
==25520== 65,536 bytes in 1 blocks are indirectly lost in loss record 4 of 6
==25520==    at 0x4026864: malloc (vg_replace_malloc.c:236)
==25520==    by 0x808E6F3: google::dense_hashtable<std::pair<std::string const, unsigned int>, std::string, std::tr1::hash<std::string>, google::dense_hash_map<std::string, unsigned int, std::tr1::hash<std::string>, std::equal_to<std::string>, std::allocator<unsigned int> >::SelectKey, google::dense_hash_map<std::string, unsigned int, std::tr1::hash<std::string>, std::equal_to<std::string>, std::allocator<unsigned int> >::SetKey, std::equal_to<std::string>, std::allocator<unsigned int> >::copy_from(google::dense_hashtable<std::pair<std::string const, unsigned int>, std::string, std::tr1::hash<std::string>, google::dense_hash_map<std::string, unsigned int, std::tr1::hash<std::string>, std::equal_to<std::string>, std::allocator<unsigned int> >::SelectKey, google::dense_hash_map<std::string, unsigned int, std::tr1::hash<std::string>, std::equal_to<std::string>, std::allocator<unsigned int> >::SetKey, std::equal_to<std::string>, std::allocator<unsigned int> > const&, unsigned int) (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==    by 0x80A51F2: ExtractorCallbacks::wayFunction(_Way&) (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==    by 0x8077CC9: wayFunction(_Way) (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==    by 0x8098270: PBFParser::parseWay(PBFParser::_ThreadData*) (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==    by 0x807842B: _ZN9PBFParser5ParseEv.omp_fn.0 (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==    by 0x80B2E0F: PBFParser::Parse() (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==    by 0x8079C80: main (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==
==25520== 108,267 bytes in 4,010 blocks are indirectly lost in loss record 5 of 6
==25520==    at 0x402641D: operator new(unsigned int) (vg_replace_malloc.c:255)
==25520==    by 0x43929F7: std::string::_Rep::_S_create(unsigned int, unsigned int, std::allocator<char> const&) (in /usr/lib/i386-linux-gnu/libstdc++.so.6.0.14)
==25520==    by 0x4393C77: std::string::_Rep::_M_clone(std::allocator<char> const&, unsigned int) (in /usr/lib/i386-linux-gnu/libstdc++.so.6.0.14)
==25520==    by 0x439459E: std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::string const&) (in /usr/lib/i386-linux-gnu/libstdc++.so.6.0.14)
==25520==    by 0x8097F46: PBFParser::parseWay(PBFParser::_ThreadData*) (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==    by 0x807842B: _ZN9PBFParser5ParseEv.omp_fn.0 (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==    by 0x80B2E0F: PBFParser::Parse() (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==    by 0x8079C80: main (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==
==25520== 174,003 (60 direct, 173,943 indirect) bytes in 1 blocks are definitely lost in loss record 6 of 6
==25520==    at 0x402641D: operator new(unsigned int) (vg_replace_malloc.c:255)
==25520==    by 0x8079410: main (in /home/mioadmin/osrm_svn/osrm/extractor)
==25520==
==25520== LEAK SUMMARY:
==25520==    definitely lost: 60 bytes in 1 blocks
==25520==    indirectly lost: 173,943 bytes in 4,012 blocks
==25520==      possibly lost: 0 bytes in 0 blocks
==25520==    still reachable: 252 bytes in 2 blocks
==25520==         suppressed: 0 bytes in 0 blocks

Three different stack traces for leaked memory allocations from Visual Studio:

msvcr90d.dll!_heap_alloc_dbg_impl(unsigned int nSize=448, int nBlockUse=1, const char * szFileName=0x00000000, int nLine=0, int * errno_tmp=0x0166e4b0)  Line 387   C++
    msvcr90d.dll!_nh_malloc_dbg_impl(unsigned int nSize=448, int nhFlag=0, int nBlockUse=1, const char * szFileName=0x00000000, int nLine=0, int * errno_tmp=0x0166e4b0)  Line 239 + 0x19 bytes C++
    msvcr90d.dll!_nh_malloc_dbg(unsigned int nSize=448, int nhFlag=0, int nBlockUse=1, const char * szFileName=0x00000000, int nLine=0)  Line 296 + 0x1d bytes  C++
    msvcr90d.dll!malloc(unsigned int nSize=448)  Line 56 + 0x15 bytes   C++
    msvcr90d.dll!operator new(unsigned int size=448)  Line 59 + 0x9 bytes   C++
    extractor.exe!std::_Allocate<std::basic_string<char,std::char_traits<char>,std::allocator<char> > >(unsigned int _Count=14, std::basic_string<char,std::char_traits<char>,std::allocator<char> > * __formal=0x00000000)  Line 43 + 0xc bytes    C++
    extractor.exe!std::allocator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > >::allocate(unsigned int _Count=14)  Line 145 + 0xb bytes C++
    extractor.exe!std::vector<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::allocator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > > >::_Insert<std::basic_string<char,std::char_traits<char>,std::allocator<char> > *>(std::_Vector_const_iterator<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::allocator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > > > _Where={_Bx={...} _Mysize=??? _Myres=??? }, std::basic_string<char,std::char_traits<char>,std::allocator<char> > * _First="motorway", std::basic_string<char,std::char_traits<char>,std::allocator<char> > * _Last="X ™�˜i™�", std::forward_iterator_tag __formal={...})  Line 950 + 0xf bytes    C++
    extractor.exe!std::vector<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::allocator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > > >::insert<std::basic_string<char,std::char_traits<char>,std::allocator<char> > *>(std::_Vector_const_iterator<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::allocator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > > > _Where={_Bx={...} _Mysize=??? _Myres=??? }, std::basic_string<char,std::char_traits<char>,std::allocator<char> > * _First="motorway", std::basic_string<char,std::char_traits<char>,std::allocator<char> > * _Last="X ™�˜i™�")  Line 890   C++
    extractor.exe!main(int argc=2, char * * argv=0x01992350)  Line 121 + 0x5a bytes C++
    extractor.exe!__tmainCRTStartup()  Line 586 + 0x19 bytes    C
    extractor.exe!mainCRTStartup()  Line 403    C
    kernel32.dll!7711339a()     
    [Frames below may be incorrect and/or missing, no symbols loaded for kernel32.dll]  
    ntdll.dll!776c9ed2()    
    ntdll.dll!776c9ea5()    

msvcr90d.dll!_heap_alloc_dbg_impl(unsigned int nSize=4, int nBlockUse=1, const char * szFileName=0x00000000, int nLine=0, int * errno_tmp=0x0166d854)  Line 387 C++
    msvcr90d.dll!_nh_malloc_dbg_impl(unsigned int nSize=4, int nhFlag=0, int nBlockUse=1, const char * szFileName=0x00000000, int nLine=0, int * errno_tmp=0x0166d854)  Line 239 + 0x19 bytes   C++
    msvcr90d.dll!_nh_malloc_dbg(unsigned int nSize=4, int nhFlag=0, int nBlockUse=1, const char * szFileName=0x00000000, int nLine=0)  Line 296 + 0x1d bytes    C++
    msvcr90d.dll!malloc(unsigned int nSize=4)  Line 56 + 0x15 bytes C++
    msvcr90d.dll!operator new(unsigned int size=4)  Line 59 + 0x9 bytes C++
    extractor.exe!std::_Allocate<char const *>(unsigned int _Count=1, const char * * __formal=0x00000000)  Line 43 + 0xc bytes  C++
    extractor.exe!std::allocator<char const *>::allocate(unsigned int _Count=1)  Line 145 + 0xb bytes   C++
    extractor.exe!std::vector<void (__cdecl*)(void),std::allocator<void (__cdecl*)(void)> >::_Insert_n(std::_Vector_const_iterator<void (__cdecl*)(void),std::allocator<void (__cdecl*)(void)> > _Where=..., unsigned int _Count=1, void (void)* const & _Val=0xffffffff)  Line 1173 + 0xf bytes    C++
    extractor.exe!std::vector<int,std::allocator<int> >::resize(unsigned int _Newsize=1, int _Val=-1)  Line 719 + 0x5f bytes    C++
    extractor.exe!stxxl::vector<_Node,4,stxxl::lru_pager<8>,2097152,stxxl::RC,unsigned __int64>::reserve(unsigned __int64 n=1)  Line 887    C++
    extractor.exe!stxxl::vector<_Node,4,stxxl::lru_pager<8>,2097152,stxxl::RC,unsigned __int64>::_resize(unsigned __int64 n=1)  Line 924    C++
    extractor.exe!stxxl::vector<_Node,4,stxxl::lru_pager<8>,2097152,stxxl::RC,unsigned __int64>::resize(unsigned __int64 n=1)  Line 910 C++
    extractor.exe!stxxl::vector<_Node,4,stxxl::lru_pager<8>,2097152,stxxl::RC,unsigned __int64>::push_back(const _Node & obj={...})  Line 989   C++
    extractor.exe!ExtractorCallbacks::nodeFunction(_Node & n={...})  Line 87    C++
    extractor.exe!nodeFunction(_Node n={...})  Line 447 C++
    extractor.exe!PBFParser::parseDenseNode(PBFParser::_ThreadData * threadData=0x0199a908)  Line 225 + 0x29 bytes  C++
    extractor.exe!PBFParser::Parse$omp$1()  Line 176    C++
    vcomp90d.dll!_vcomp::fork_helper(void (<no type>)* funclet=0x00405b90, int arg_count=1, char * argptr=0x0166e858)  Line 333 C++
    vcomp90d.dll!_vcomp::ParallelRegion::HandlerThreadFunc(void * context=0x00312808, unsigned long index=0)  Line 293 + 0x1a bytes C++
    vcomp90d.dll!InvokeThreadTeam(_THREAD_TEAM * ptm=0x726d4028, void (void *, unsigned long)* pfn=0x726c2fb0, void * pvContext=0x00312808)  Line 563   C++
    vcomp90d.dll!_vcomp_fork(int if_test=1, int arg_count=1, void (<no type>)* funclet=0x00405b90, ...)  Line 186   C++
    extractor.exe!PBFParser::Parse()  Line 142 + 0x35 bytes C++
    extractor.exe!main(int argc=2, char * * argv=0x01992350)  Line 138 + 0x15 bytes C++
    extractor.exe!__tmainCRTStartup()  Line 586 + 0x19 bytes    C
    extractor.exe!mainCRTStartup()  Line 403    C
    kernel32.dll!7711339a()     
    [Frames below may be incorrect and/or missing, no symbols loaded for kernel32.dll]  
    ntdll.dll!776c9ed2()    
    ntdll.dll!776c9ea5()    

msvcr90d.dll!_heap_alloc_dbg_impl(unsigned int nSize=32, int nBlockUse=1, const char * szFileName=0x00000000, int nLine=0, int * errno_tmp=0x0166da94)  Line 387    C++
    msvcr90d.dll!_nh_malloc_dbg_impl(unsigned int nSize=32, int nhFlag=0, int nBlockUse=1, const char * szFileName=0x00000000, int nLine=0, int * errno_tmp=0x0166da94)  Line 239 + 0x19 bytes  C++
    msvcr90d.dll!_nh_malloc_dbg(unsigned int nSize=32, int nhFlag=0, int nBlockUse=1, const char * szFileName=0x00000000, int nLine=0)  Line 296 + 0x1d bytes   C++
    msvcr90d.dll!malloc(unsigned int nSize=32)  Line 56 + 0x15 bytes    C++
    msvcr90d.dll!operator new(unsigned int size=32)  Line 59 + 0x9 bytes    C++
    msvcp90d.dll!std::_Allocate<char>(unsigned int _Count=32, char * __formal=0x00000000)  Line 43 + 0x9 bytes  C++
    msvcp90d.dll!std::allocator<char>::allocate(unsigned int _Count=32)  Line 151 + 0xb bytes   C++
    msvcp90d.dll!std::basic_string<char,std::char_traits<char>,std::allocator<char> >::_Copy(unsigned int _Newsize=20, unsigned int _Oldlen=0)  Line 2103 + 0x12 bytes  C++
    msvcp90d.dll!std::basic_string<char,std::char_traits<char>,std::allocator<char> >::_Grow(unsigned int _Newsize=20, bool _Trim=false)  Line 2133 + 0x13 bytes    C++
    msvcp90d.dll!std::basic_string<char,std::char_traits<char>,std::allocator<char> >::assign(const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & _Right="Wolseley Avenue West", unsigned int _Roff=0, unsigned int _Count=4294967295)  Line 1065 + 0xe bytes  C++
    msvcp90d.dll!std::basic_string<char,std::char_traits<char>,std::allocator<char> >::assign(const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & _Right="Wolseley Avenue West")  Line 1052    C++
    msvcp90d.dll!std::basic_string<char,std::char_traits<char>,std::allocator<char> >::operator=(const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & _Right="Wolseley Avenue West")  Line 927  C++
>   extractor.exe!stxxl::vector<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,4,stxxl::lru_pager<8>,2097152,stxxl::RC,unsigned __int64>::push_back(const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & obj="Wolseley Avenue West")  Line 989 + 0x1e bytes   C++
    extractor.exe!ExtractorCallbacks::wayFunction(_Way & w={...})  Line 190 C++
    extractor.exe!wayFunction(_Way w={...})  Line 462   C++
    extractor.exe!PBFParser::parseWay(PBFParser::_ThreadData * threadData=0x0191a908)  Line 336 + 0x28 bytes    C++
    extractor.exe!PBFParser::Parse$omp$1()  Line 164    C++
    vcomp90d.dll!_vcomp::fork_helper(void (<no type>)* funclet=0x00405b90, int arg_count=1, char * argptr=0x0166e858)  Line 333 C++
    vcomp90d.dll!_vcomp::ParallelRegion::HandlerThreadFunc(void * context=0x001b2808, unsigned long index=0)  Line 293 + 0x1a bytes C++
    vcomp90d.dll!InvokeThreadTeam(_THREAD_TEAM * ptm=0x5afe4028, void (void *, unsigned long)* pfn=0x5afd2fb0, void * pvContext=0x001b2808)  Line 563   C++
    vcomp90d.dll!_vcomp_fork(int if_test=1, int arg_count=1, void (<no type>)* funclet=0x00405b90, ...)  Line 186   C++
    extractor.exe!PBFParser::Parse()  Line 142 + 0x35 bytes C++
    extractor.exe!main(int argc=2, char * * argv=0x01912350)  Line 138 + 0x15 bytes C++
    extractor.exe!__tmainCRTStartup()  Line 586 + 0x19 bytes    C
    extractor.exe!mainCRTStartup()  Line 403    C
    kernel32.dll!7711339a()     
    [Frames below may be incorrect and/or missing, no symbols loaded for kernel32.dll]  
    ntdll.dll!776c9ed2()    
    ntdll.dll!776c9ea5()
@DennisOSRM
Copy link
Collaborator

Thanks for the traces. Will have a look at why the vector of strings is leaking.

@ghost ghost assigned DennisOSRM Sep 30, 2011
@DennisOSRM
Copy link
Collaborator

There is a leak indeed, but that the problem is just a matter of cleaning up at the end of extraction. This bug will be fixed.

Each street name is recorded exactly once and identified a (unique) id. A hash table is used to check if a streetname is already known. During the extraction, the hash table grows. Generally, the table is rather small, but may grow out of memory bounds on large data sets. Doing hash tables in external memory may not be feasible here, so I need to look for a different approach.

How much RAM does your machine have?

@DennisOSRM
Copy link
Collaborator

Proper cleanup fixes the leak.

==14119== LEAK SUMMARY:
==14119== definitely lost: 0 bytes in 0 blocks
==14119== indirectly lost: 0 bytes in 0 blocks
==14119== possibly lost: 0 bytes in 0 blocks
==14119== still reachable: 296 bytes in 2 blocks
==14119== suppressed: 0 bytes in 0 blocks
==14119== Rerun with --leak-check=full to see details of leaked memory

Will push the commit soon.

DennisOSRM pushed a commit that referenced this issue Oct 4, 2011
Boost Property Tree provides the speed profile from an ini file
109279d 
Memory leak fixed, issue #11, thanks sivetic
Typo fixed
for loop replaced by boost's FOREACH
@DennisOSRM
Copy link
Collaborator

Pushed the changes to master. Closing this bug for now and opening a new issue to store the hash table with strings in a more efficient way.

This was referenced Nov 25, 2011
Closed
Closed
@emiltin emiltin mentioned this issue Mar 22, 2012
Closed
@mrueegg mrueegg mentioned this issue Sep 17, 2012
Closed
@banek13 banek13 mentioned this issue Sep 27, 2012
Closed
@drieks drieks mentioned this issue Jul 2, 2013
Closed
@mitchless mitchless mentioned this issue Mar 10, 2014
Closed
@mafin mafin mentioned this issue May 20, 2014
Closed
@escurzo escurzo mentioned this issue Jun 16, 2014
Closed
@frodrigo frodrigo mentioned this issue Oct 21, 2014
Closed
@GhOsTMZ GhOsTMZ mentioned this issue Jul 3, 2015
Closed
@baststar baststar mentioned this issue Aug 27, 2016
Closed
This was referenced Sep 17, 2017
Closed
Closed
Closed
@pbeyssac pbeyssac mentioned this issue May 17, 2021
Closed
@RZR-UA RZR-UA mentioned this issue Sep 13, 2021
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@DennisOSRM DennisOSRM

Labels
None yet
Projects
None yet
Milestone
0.3
Development

No branches or pull requests
2 participants
@DennisOSRM @sivetic