std::string底层实现之COW(Copy-On-Write)

你好,我是雨乐!

在开始正文之前,先看一段代码,如下:

 std::string s("str");
 std::string s1 = s;
 char *p = const_cast<char*>(s1.data());
 p[2] = '\0';

 std::cout << s << std::endl;
 std::cout << s1 << std::endl;

可能会有部分人认为上面代码的输出结果是:

st
st

也有部分人认为上述代码输出结果是:

str
st

其实,上述两种结果都是正确的,第一种正确的前提是基于gcc5.1之前的版本,第二种正确的前提是基于gcc5.1(包含)以后的版本。

而第一种之所以正确,这是基于std::string的另外一个特性:COW(Copy On Write)。

COW

COW是Copy On Write的缩写,是一种很常见且很重要的优化方式。核心思想是对多个实体的资源请求进行延时处理,如果不存在资源更改行为,则多个实体共享该块资源,直到有实体需要对资源进行修改时,才真正为该实体分配私有的资源。

COW技术的一个经典应用在于Linux内核在进程fork时对进程地址空间的处理。由于fork产生的子进程需要一份和父进程内容相同但完全独立的地址空间,一种做法是将父进程的地址空间完全复制一份,另一种做法是将父进程地址空间中的页面标记为共享的(引用计数+1),使子进程与父进程共享地址空间,但当有一方需要对内存中某个页面进行修改时,重新分配一个新的页面(拷贝原内容),并使修改进程的虚拟地址重定向到新的页面上。

COW技术有哪些优点呢?

  1. 减少了分配(和复制)大量资源带来的瞬间延迟(注意仅仅是latency,但实际上该延迟被分摊到后续的操作中,其累积耗时很可能比一次统一处理的延迟要高,造成throughput下降是有可能的)
  2. 另一方面减少不必要的资源分配。(例如在fork的例子中,并不是所有的页面都需要复制,比如父进程的代码段(.code)和只读数据(.rodata)段,由于不允许修改,根本就无需复制。而如果fork后面紧跟exec的话,之前的地址空间都会废弃,花大力气的分配和复制只是徒劳无功。)

COW的思想在资源管理上被广泛使用,本文中分析的string中也用到了COW思想~~。

实现

为了分析COW在string中的实现机制,我们对上述代码进行分析。下面源码版本为4.6.0(在线地址为:string源码)。

在上节内容中,我们提到一般实现COW的策略,都用了引用计数,std::string也不例外,使用如下结构:

struct _Rep_base
       {
     size_type       _M_length;
     size_type       _M_capacity;
     _Atomic_word        _M_refcount;
       };

 struct _Rep : _Rep_base
       {
     // Types:
     typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;

         bool
     _M_is_leaked() const
         { return this->_M_refcount < 0; }

         bool
     _M_is_shared() const
         { return this->_M_refcount > 0; }

         void
     _M_set_leaked()
         { this->_M_refcount = -1; }

         void
     _M_set_sharable()
         { this->_M_refcount = 0; }

     void
     _M_set_length_and_sharable(size_type __n)
     {
 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
       if (__builtin_expect(this != &_S_empty_rep(), false))
 #endif
         {
           this->_M_set_sharable();  // One reference.
           this->_M_length = __n;
           traits_type::assign(this->_M_refdata()[__n], _S_terminal);
           // grrr. (per 21.3.4)
           // You cannot leave those LWG people alone for a second.
         }
     }

     _CharT*
     _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);
     }

     // Create & Destroy
     static _Rep*
     _S_create(size_type, size_type, const _Alloc&);

     void
     _M_dispose(const _Alloc& __a)
     {
 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
       if (__builtin_expect(this != &_S_empty_rep(), false))
 #endif
         {
           // Be race-detector-friendly.  For more info see bits/c++config.
           _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&this->_M_refcount);
           if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,
                              -1) <= 0)
         {
           _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this->_M_refcount);
           _M_destroy(__a);
         }
         }
     }  // XXX MT

     void
     _M_destroy(const _Alloc&) throw();

     _CharT*
     _M_refcopy() throw()
     {
 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
       if (__builtin_expect(this != &_S_empty_rep(), false))
 #endif
             __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
       return _M_refdata();
     }  // XXX MT

     _CharT*
     _M_clone(const _Alloc&, size_type __res = 0);
       };

在上述结构中,有一个变量_M_refcount,用来记录当前引用该string的对象个数。在string的COW实现中,当新建一个string或者为其分配内存时,会额外创建一个_Rep_base对象用来存放引用对象的个数,当发生拷贝或者赋值的时候,这个引用计数就会+1。而在内容修改时,string类为查看这个引用计数是否为0,如果不为零,表示有人在共享这块内存,那么自己需要先做一份拷贝,然后把引用计数-1,再把数据拷贝过来。_Rep的各种成员函数,则是用来对引用计数进行操作。

构造函数

在代码std::string s("str");构建一个string对象,我们看下其具体实现,代码如下:

 template<typename _CharT, typename _Traits, typename _Alloc>
     basic_string<_CharT, _Traits, _Alloc>::
     basic_string(const _CharT* __s, const _Alloc& __a)
     : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
                    __s + npos, __a), __a)
     { }

在该实现中,调用了_M_dataplus()函数,其实际上是某个对象的构造函数,有两个参数,一个为_S_construct生成的char*指针,另一个则为分配器。

_M_dataplus的定义如下:

struct _Alloc_hider : _Alloc
       {
     _Alloc_hider(_CharT* __dat, const _Alloc& __a)
     : _Alloc(__a), _M_p(__dat) { }

     _CharT* _M_p; // The actual data.
       };
mutable _Alloc_hider  _M_dataplus;

_M_dataplus中有个成员变量_M_p指向实际的字符串地址,而该地址是由_S_construct生成,代码如下:

template<typename _CharT, typename _Traits, typename _Alloc>
     template<typename _InIterator>
       _CharT*
       basic_string<_CharT, _Traits, _Alloc>::
       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
            input_iterator_tag)
       {
 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
     if (__beg == __end && __a == _Alloc())
       return _S_empty_rep()._M_refdata();
 #endif
     // Avoid reallocation for common case.
     _CharT __buf[128];
     size_type __len = 0;
     while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
       {
         __buf[__len++] = *__beg;
         ++__beg;
       }
     _Rep* __r = _Rep::_S_create(__len, size_type(0), __a); // 创建Rep*对象,即包含有引用计数的
     _M_copy(__r->_M_refdata(), __buf, __len);
     __try
       {
         while (__beg != __end)
           {
         if (__len == __r->_M_capacity)
           {
             // Allocate more space.
             _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
             _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
             __r->_M_destroy(__a);
             __r = __another;
           }
         __r->_M_refdata()[__len++] = *__beg;
         ++__beg;
          }
       }
     __catch(...)
       {
         __r->_M_destroy(__a);
         __throw_exception_again;
       }
     __r->_M_set_length_and_sharable(__len);
     return __r->_M_refdata();
       }

上述代码还是比较简单易理解的,无非就是将字符串拷贝到内存,生成COW所需要的对象~~

这块需要注意的是,在string定义中,并没有一个单独的_Rep对象,即并没有为了实现COW的引用计数功能而单独定义一个对象,而是为了节省内存,该_Rep对象均是通过指针偏移来实现。在前面内容中,有提到,_M_dataplus._M_p用来指向真正的存储数据的地址。

下面是string的数据成员:

template<typename _CharT, typename _Traits, typename _Alloc>
  class basic_string {
    // **********
    static const size_type    npos = static_cast<size_type>(-1);
    mutable _Alloc_hider  _M_dataplus;
  }

下面继续分析_S_construct代码,在该函数中,比较重要的一行

_Rep* __r = _Rep::_S_create(__len, size_type(0), __a);

该行中主要负责分配内存,由分配器__a进行分配(string中的分配方式与vector类似,都采用了预分配方式,以提升性能),其如图所示:

![image-20221010110814876](/Users/lijun/Library/Application Support/typora-user-images/image-20221010110814876.png)

这块设计非常巧妙,在_Rep::_S_create源码实现中,通过分配器分配一块内存,然后通过placement new构建_Rep对象,如下:

void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
       _Rep *__p = new (__place) _Rep;
       __p->_M_capacity = __capacity;

那么有个疑问,string如何获取到存储实际数据的指针,以及又如何对引用计数进行操作的呢?

相信我们经常都会用到string::c_str()操作,这个函数的作用就是返回实际的存储数据的地址,实现如下:

const _CharT*
       c_str() const
       { return _M_data(); }

_CharT*
       _M_data() const
       { return  _M_dataplus._M_p; }

通过如上代码,进一步证明_M_dataplus._M_p指向实际存储数据的地址。而_M_p则是在构造函数_M_dataplus()中由_S_construct()生成,在_S_construct函数的最后一行为return __r->_M_refdata();,其返回的是实际存储数据地址,但__r类型为_Rep,又是如何返回的呢,不妨看下函数实现:

_CharT*
     _M_refdata() throw()
     { return reinterpret_cast<_CharT*>(this + 1); }

结合上图,通过this + 1,移动指针,自然就到了可存储数据部分。那么string又是如何进行引用计数操作的呢?通过_M_dataplus._M_p指针反向操作,自然可以得到_Rep对象。

_Rep*
       _M_rep() const
       { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }

拷贝构造

在本文例子中,同样一块代码,在不同版本中的运行结果不一致,其根源就在于std::string s1 = s;,这句代码调用了拷贝构造函数,所以,不妨从其构造函数入手,来研究其实现😁。

template<typename _CharT, typename _Traits, typename _Alloc>
     basic_string<_CharT, _Traits, _Alloc>::
     basic_string(const basic_string& __str)
     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
                       __str.get_allocator()),
           __str.get_allocator())
     { }

显然,该函数实现简单,只调用了_M_dataplus函数,其定义如下:

struct _Alloc_hider : _Alloc
       {
     _Alloc_hider(_CharT* __dat, const _Alloc& __a)
     : _Alloc(__a), _M_p(__dat) { }

     _CharT* _M_p; // The actual data.
       };

mutable _Alloc_hider  _M_dataplus;

通过上述定义,可以看出,_M_dataplus是一个对象,在其构造函数中有两个参数,一个为char类型的实际数据,另外一个为分配器(分配器不在本文讨论范围内),所以重点就在于char数据了,通过函数调用发现,char*是通过_M_grab来获取的。也就是说,string的拷贝构造函数仅仅对_M_dataplus对象进行构造,看来重点在`__str._M_rep()->_M_grab这块了,源码如下:

_CharT*
     _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
     {
       return (!_M_is_leaked() && __alloc1 == __alloc2)
               ? _M_refcopy() : _M_clone(__alloc1);
     }

在_M_grab函数中,如果字符串可共享,进行引用拷贝(即引用计数+1,返回源数据地址),否则进行深度拷贝。那么判断字符串共享的条件是什么?显然!M_is_leaked() && alloc1 == alloc2,正常情况下,字符串都可被共享(使用不同分配器这种情况忽略哈),只有个别情况下不可共享,比如这个字符串正在被写入时就不可被共享(比如调用了insert函数等)。

引用拷贝是通过_M_refcopy()函数来实现的,其定义如下:

_CharT*
     _M_refcopy() throw()
     {
 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
       if (__builtin_expect(this != &_S_empty_rep(), false))
 #endif
             __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
       return _M_refdata();
     }  // XXX MT

在引用拷贝的方法实现_M_refcopy中,对字符串的引用计数+1,然后直接返回源字符串的字符串地址。

必须说明的该函数只有在basic_string的copy ctor和assignment中才可能被调用,也就是说只有在新的字符串按copy或者赋值创建的时候才考虑使用引用计数。
进行refcopy或者clone的关键标识是:首先没有内存泄漏标志(关于这个标志主要是禁止string再次被共享),然后就是两个string对象的分配相同。

结语

COW的核心思想就是lazy-copy,是一种常见的优化手段,通常发生在拷贝、赋值等操作上,但是如果使用不当,则会导致预期之外的结果,虽然COW在gcc的高版本实现中已经去掉了,但是,因为种种原因,仍然有许多开发人员使用的老版本gcc,那么这个优化导致的问题就不得不引起关注,正所谓知己知彼,方能百战不殆

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/1201

转载文章受原作者版权保护。转载请注明原作者出处!

(2)
上一篇 2022年9月6日 下午5:00
下一篇 2022年10月26日 下午10:08

相关推荐