Deadlocked when allocating an std::string

I have an application with several threads running. I have 2 threads that seem deadlocked when trying to allocate an std::string. Inspecting the backtrace of both threads suggest that at some point one has tried to allocate an std::string, and got a bad_alloc exception. In its catch block, another string is created in an attempt to write a call stack to some log file. At the same time, the other thread is also trying to allocate an std::string and then the whole process gets stuck.

Here are the relevant parts of the 2 deadlocked threads:

#0  0x004cf7a2 in _dl_sysinfo_int80 () from /lib/ld-linux.so.2
#1  0x034ba3de in __lll_mutex_lock_wait () from /lib/tls/libpthread.so.0
#2  0x034b700b in _L_mutex_lock_35 () from /lib/tls/libpthread.so.0
#3  0x004e5fd4 in ?? () from /lib/ld-linux.so.2
#4  0x07c9f9bc in ?? () from /.../libstdc++.so.5
#5  0x00000037 in ?? ()
#6  0x07ca1714 in std::__default_alloc_template<true, 0>::_S_free_list () from /.../libstdc++.so.5
#7  0x9b2223a8 in ?? ()
#8  0x07c6ab7e in std::__default_alloc_template<true, 0>::allocate () from /.../libstdc++.so.5
#9  0x07c6ab7e in std::__default_alloc_template<true, 0>::allocate () from /.../libstdc++.so.5
#10 0x07c70b68 in std::string::_Rep::_S_create () from /.../libstdc++.so.5
#11 0x081c5ec0 in std::string::_S_construct<char*> ()
#12 0x081c33a2 in std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string<char*> ()
#13 0x081c296e in std::basic_stringbuf<char, std::char_traits<char>, std::allocator<char> >::str ()
#14 0x02af7d7a in os::bad_allocation_t::bad_allocation_t () from /.../libmylib.so 
#15 0x02af84a9 in operator new () from /.../libmylib.so 
#16 0x07c6b0f1 in std::__default_alloc_template<true, 0>::_S_chunk_alloc () from /.../libstdc++.so.5
#17 0x07c6affd in std::__default_alloc_template<true, 0>::_S_refill () from /.../libstdc++.so.5
#18 0x07c6ab6c in std::__default_alloc_template<true, 0>::allocate () from /.../libstdc++.so.5
#19 0x07c78b2f in std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_create () from /.../libstdc++.so.5
#20 0x07c78c59 in std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_M_clone () from /.../libstdc++.so.5
#21 0x07c76996 in std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::reserve () from /.../libstdc++.so.5
#22 0x07c76cff in std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::append () from /.../libstdc++.so.5

At #14 you see bad_alloc wrapped in my own exception class being caught and then another string being created.
At #15 you see my own operator new which simply calls std::malloc, checks its return and throws bad_allocation_t when NULL

And the other thread:

#0  0x004cf7a2 in _dl_sysinfo_int80 () from /lib/ld-linux.so.2
#1  0x034ba3de in __lll_mutex_lock_wait () from /lib/tls/libpthread.so.0
#2  0x034b700b in _L_mutex_lock_35 () from /lib/tls/libpthread.so.0
#3  0x18f54584 in ?? ()
#4  0x07c9f9bc in ?? () from /.../libstdc++.so.5
#5  0x00000033 in ?? ()
#6  0x07ca1714 in std::__default_alloc_template<true, 0>::_S_free_list () from /.../libstdc++.so.5
#7  0x9b4236c8 in ?? ()
#8  0x07c6ab7e in std::__default_alloc_template<true, 0>::allocate () from /.../libstdc++.so.5
#9  0x07c6ab7e in std::__default_alloc_template<true, 0>::allocate () from /.../libstdc++.so.5
#10 0x07c78b2f in std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_create () from /.../libstdc++.so.5
#11 0x07c78c59 in std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_M_clone () from /.../libstdc++.so.5
#12 0x07c76996 in std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::reserve () from /.../libstdc++.so.5
#13 0x07c76cff in std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::append () from /.../libstdc++.so.5

Can anyone provide any more insight than what I've gathered so far?

Trying to create a dynamically allocated string from within your new operator is probably a very bad idea (particularly after you were unable to allocate memory).

I guess what's happening is that std::__default_alloc_template is not safe to be used recursively - most likely because it has locked some data structure in frames 16-18 (with a non-recursive mutex) and tries to reacquire that same mutex in frame 6 (which deadlocks because it's not a recursive mutex).