Prevent double free in basic_string

Prevent double free in basic_string

[tlknv]

[-- Attachment #1: Type: text/plain, Size: 1565 bytes --]

Hi All,
I would like to propose a patch to libstdc++-v3/include/bits/basic_string.h that solves the problem described in the bug 21334 ( http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21334 ).
Briefly:
Developers often use non constant methods begin(), end(), operator [], at() for constant operations.
Since developers don’t modify the string they don’t expect that these operations are considered as not constant/modifying operations and can lead to double free if not protected by some mutex/lock.
The problem is caused by a potential delay in _M_grab() between making a positive decision (!_M_is_leaked() && __alloc1 == __alloc2) and performing the corresponding action ( _M_refcopy() ). 
        _CharT*
        _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
        {
         return (!_M_is_leaked() && __alloc1 == __alloc2)
                 ? _M_refcopy() : _M_clone(__alloc1);
        }
Assume that there is std::string s1;
Some thread t2 creates a “copy” of s1: std::string s2(s1);
Copy constructor calls _M_grab. Since _M_refcount == 0 _M_grab decided to call _M_refcopy(). At this moment some other thread t1 calls some non-constant method on s1, e.g. s1.begin(). begin() calls _M_leak .. _M_leak_hard .. _M_set_leaked which sets _M_refcount to -1. Then _M_refcopy() in t2 is going to increment _M_refcount making it 0. Thus each of two basic_string objects think that it owns the object and will eventually free the memory allocated for the string. Which will cause double free and likely crash of the process.

Thanks,
Boris

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: basic_string_grab.h.diff --]
[-- Type: text/x-c++; name="basic_string_grab.h.diff", Size: 2057 bytes --]

--- old/libstdc++-v3/include/bits/basic_string.h	2012-05-30 17:03:15.974035000 -0400
+++ new/libstdc++-v3/include/bits/basic_string.h	2012-05-31 09:09:43.514414000 -0400
@@ -224,14 +224,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_refdata() throw()
 	{ return reinterpret_cast<_CharT*>(this + 1); }
 
 	_CharT*
 	_M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
 	{
-	  return (!_M_is_leaked() && __alloc1 == __alloc2)
-	          ? _M_refcopy() : _M_clone(__alloc1);
+          _CharT* res = (_CharT*)0;
+	  if(!_M_is_leaked() && __alloc1 == __alloc2) {
+            res = _M_refcopy();
+          }
+          if (res == (_CharT*)0) {
+            res = _M_clone(__alloc1);
+          }
+          return res;
 	}
 
 	// Create & Destroy
 	static _Rep*
 	_S_create(size_type, size_type, const _Alloc&);
 
@@ -259,13 +265,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_CharT*
 	_M_refcopy() throw()
 	{
 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
 	  if (__builtin_expect(this != &_S_empty_rep(), false))
 #endif
+          {
             __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
+            // Here we try to detect and compensate an unexpected decrement of
+            // _M_refcount from another thread. In the properly designed code
+            // this should not happen ever! If we do nothing about this
+            // condition then the string is going to be freed twice.
+            // Unfortunatelly, some cases that lead to this condition are not
+            // obvious for the developers, e.g. non-constant
+            // methods operator [], at(), begin, end, etc.
+            // In many of these cases the string is not going to be
+            // changed from another thread and it's actually safe to
+            // clone the string.
+            if (!this->_M_is_shared()) {
+              __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, -1);
+              return (_CharT*)0;
+            }
+          }
 	  return _M_refdata();
 	}  // XXX MT
 
 	_CharT*
 	_M_clone(const _Alloc&, size_type __res = 0);
       };

Re: Prevent double free in basic_string

[Marc Glisse]

On Thu, 31 May 2012, tlknv wrote:

> I would like to propose a patch to 
> libstdc++-v3/include/bits/basic_string.h that solves the problem 
> described in the bug 21334 ( 
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21334 ).

Hello,

correct me if I am wrong, but this patch doesn't aim to fix the issue, 
just paper over the most likely case to reduce the likelihood of a race, 
right?

-- 
Marc Glisse

Re: Prevent double free in basic_string

[tlknv]

[-- Attachment #1: Type: text/plain, Size: 57 bytes --]

Actually, for number of threads >=3 this patch is better:

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: basic_string_grab.h.diff --]
[-- Type: text/x-c++; name="basic_string_grab.h.diff", Size: 2101 bytes --]

--- old/libstdc++-v3/include/bits/basic_string.h	2012-05-30 17:03:15.974035000 -0400
+++ new/libstdc++-v3/include/bits/basic_string.h	2012-05-31 13:06:39.903442000 -0400
@@ -224,14 +224,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_refdata() throw()
 	{ return reinterpret_cast<_CharT*>(this + 1); }
 
 	_CharT*
 	_M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
 	{
-	  return (!_M_is_leaked() && __alloc1 == __alloc2)
-	          ? _M_refcopy() : _M_clone(__alloc1);
+          _CharT* res = (_CharT*)0;
+	  if(!_M_is_leaked() && __alloc1 == __alloc2) {
+            res = _M_refcopy();
+          }
+          if (res == (_CharT*)0) {
+            res = _M_clone(__alloc1);
+          }
+          return res;
 	}
 
 	// Create & Destroy
 	static _Rep*
 	_S_create(size_type, size_type, const _Alloc&);
 
@@ -259,13 +265,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_CharT*
 	_M_refcopy() throw()
 	{
 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
 	  if (__builtin_expect(this != &_S_empty_rep(), false))
 #endif
-            __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
+          {
+            // Here we try to detect and compensate an unexpected decrement of
+            // _M_refcount from another thread. In the properly designed code
+            // this should not happen ever! If we do nothing about this
+            // condition then the string is going to be freed twice.
+            // Unfortunatelly, some cases that lead to this condition are not
+            // obvious for the developers, e.g. non-constant
+            // methods operator [], at(), begin, end, etc.
+            // In many of these cases the string is not going to be
+            // changed from another thread and it's actually safe to
+            // clone the string.
+            if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount, 1) < 0) {
+              __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, -1);
+              return (_CharT*)0;
+            }
+          }
 	  return _M_refdata();
 	}  // XXX MT
 
 	_CharT*
 	_M_clone(const _Alloc&, size_type __res = 0);
       };