Template and Meta in shared_ptr

Structure

The classes

Classes

The Idea

The inheritance arrow in this figure is in fact a plain arrow, means “add”. It is just for convenience of my UML editor

Idea

In general, the shared_ptr is combined by components of counter, pointer reference, pointer access. These contributor work in policy pattern and implemented in meta programming to provide flexibility in compile time.

Components

bad_weak_ptr

It is an exception to be thrown when the __weak_ptr is invalid.

Why there is a bad weak ptr exception, no bad shared ptr exception
This exception is thrown when ref_count = 0, why? The counters are initialized as 1 when a shared pointer is created. If the count == 0, the wrapped pointer and the ptr object should have been destructed.

Sp_counted_base

Meta Classes

The _Sp_counted_base is the base of counter class. It combines the counter for both shared pointer and weak pointer. It provides sub-classes for different lock policies.

  template<_Lock_policy _Lp = __default_lock_policy>
    class _Sp_counted_base
    : public _Mutex_base<_Lp>

_Sp_counted_base is a class template of lock policy. It provides default value for template argument Lock_policy. The default value is the default policy value of OS.

The class inherited the Mutex_base class.

  // Empty helper class except when the template argument is _S_mutex.
  template<_Lock_policy _Lp>
    class _Mutex_base
    {
    protected:
      // The atomic policy uses fully-fenced builtins, single doesn't care.
      enum { _S_need_barriers = 0 };
    };

The meta class of Mutex_base defined barriers as false. And a specialized template for mutex policy defined barriers as true

  template<>
    class _Mutex_base<_S_mutex>
    : public __gnu_cxx::__mutex
    {
    protected:
      // This policy is used when atomic builtins are not available.
      // The replacement atomic operations might not have the necessary
      // memory barriers.
      enum { _S_need_barriers = 1 };
    };

Concurrency in Release

The treatments that make this function thread safe

_GLIBCXX_SYNCHRONIZATION_HAPPENS__*

      void
      _M_release() noexcept
      {
        // Be race-detector-friendly.  For more info see bits/c++config.
        //POSITION_1
        _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_use_count);
	if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1) == 1)
	  {
	    //POSITION_2
            _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_use_count);
	    _M_dispose();

The _GLIBCXX_SYNCHRONIZATION_HAPPENS_XXX ensures that instructions before POSITION_1 would be executed before instructions in POSITION_2. Then

iff M_use_count == 0 makes thread reach _POSITION_2
the __exchange_and_add_dispatch function is synchronized

Only one thread would call _M_dispose
When _M_use_count > 0, it does not race with thread read _M_use_count == 0

Conclusion:

The function __exchange_and_add_dispatch alone is able to provide synchronization mentioned
The _GLIBCXX_SYNCHRONIZATION_HAPPENS_XXX is just a race-detector-friendly trick

Ref:

Fence

	    if (_Mutex_base<_Lp>::_S_need_barriers)
	      {
		__atomic_thread_fence (__ATOMIC_ACQ_REL);
	      }

The __atomic_thread_fence is introduced to ensure that the effect of _M_dispose is known to _M_destroy as the destroy may also be invoked by other threads that manipulate weak_ptr

Ref:

Questions:

Which level of these tricks, compiler or runtime?
Atomic memory access sequence system

Single Policy

The release function was optimized for single case as there is no race condition:

  template<>
    inline void
    _Sp_counted_base<_S_single>::_M_release() noexcept
    {
      if (--_M_use_count == 0)
        {
          _M_dispose();
          if (--_M_weak_count == 0)
            _M_destroy();
        }
    }

Implement classes

_Sp_counted_ptr

This is the simple and default implementation without deleter and allocator assigned This class just has the inner pointer involved.

The _M_destroy defined as

      virtual void
      _M_destroy() noexcept
      { delete this; }

This function delete itself as:

The newed object requires a way to be deleted
The clean up operations, including counter manipulation and memory management, should be executed in a destructor
The function that implemented clean up functions are virtual functions, they can not be called in a destructor
Therefore, the clean up functions are encapsulated in release()
Then release() function is invoked in destructor of __shared_count
As the pointer of count_base is encapsulated in __shared_count, the pointer is inaccessible after release
So, the object kills itself and it is safe

Ref:

Calling virtual function from destructor

Is it legal (and moral) for a member function to say delete this?

_Sp_counted_deleter

This class has deleter and allocator involved.

std::move

There is a inner class _Impl defined. This class is inherited from _Sp_ebo_helper, and to provide the real type for deleter/allocator according to their EBO property.

This class has a constructor like this:

      _Sp_counted_deleter(_Ptr __p, _Deleter __d, const _Alloc& __a) noexcept
      : _M_impl(__p, std::move(__d), __a) { }

This shows the general way of using std::move(). The Deleter object is copied into the constructor. As this object is merely for _M_impl object, the Deleter object is moved into the _M_impl constructor. And then moves into _M_impl object:

      explicit _Sp_ebo_helper(_Tp&& __tp) : _Tp(std::move(__tp)) { }

But the Alloc argument is not moved as it is not recommended to move a const object:

      explicit _Sp_ebo_helper(const _Tp& __tp) : _Tp(__tp) { }

Ref:

_M_destroy()

As mentioned in _Sp_counted_ptr, _M_destroy takes responsibility of killing self. In _Sp_counted_deleter, the function defined as:

      virtual void
      _M_destroy() noexcept
      {
	__allocator_type __a(_M_impl._M_alloc());
	__allocated_ptr<__allocator_type> __guard_ptr{ __a, this };
	this->~_Sp_counted_deleter();
      }

As this version of counter ptr has customized allocator defined, a _guard_ptr is generated to ensure that the customized allocator would release the memory in guard object’s destructor after destruction of _Sp_counted_deleter called as this->~_Sp_counted_deleter()

The allocator type was defined as:

      using __allocator_type = __alloc_rebind<_Alloc, _Sp_counted_deleter>;

So we are using template argument _Alloc for _Sp_counted_deleter’s memory manipulation.

Therefore, the argument _Alloc is for _Sp_counted_deleter, and the argument _Deleter is for inner pointer ptr

The _M_get_deleter to be parsed

Ref:

Why is allocator::rebind necessary when we have template template parameters?
_Sp_counted_ptr_inplace

This class is similar to __Sp_counted_deleter. But instead of pointer, it holds the real memory for the pointer.

This is supposed to work as helper for make_shared_ptr function as this class is only used in __shared_count when _Sp_make_shared_tag was set.

The memory is allocated once and wrapped in counter class once the _Sp_counted_ptr_inplace object created:

      class _Impl : _Sp_ebo_helper<0, _Alloc>
      {
	typedef _Sp_ebo_helper<0, _Alloc>	_A_base;

      public:
	explicit _Impl(_Alloc __a) noexcept : _A_base(__a) { }

	_Alloc& _M_alloc() noexcept { return _A_base::_S_get(*this); }

	__gnu_cxx::__aligned_buffer<_Tp> _M_storage;
      };

The constructor of typename _Tp invoked with constructor arguments forwarded:

      template<typename... _Args>
	_Sp_counted_ptr_inplace(_Alloc __a, _Args&&... __args)
	: _M_impl(__a)
	{
	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
	  // 2070.  allocate_shared should use allocator_traits<A>::construct
	  allocator_traits<_Alloc>::construct(__a, _M_ptr(),
	      std::forward<_Args>(__args)...); // might throw
	}

The release of the inner pointer and outer object are similar to that in _Sp_counted_deleter

__shared_count

Constructor

The class __shared_count holds a pointer of _Sp_counted_base. This pointer is initialized into different sub-classes in according to constructor arguments.

Default

A default constructor with nothing initialized

      constexpr __shared_count() noexcept : _M_pi(0)
      { }

__Sp_counted_ptr

When a inner pointer provided, the __Sp_counted_ptr used

      template<typename _Ptr>
        explicit
	__shared_count(_Ptr __p) : _M_pi(0)
	{
	  __try
	    {
	      _M_pi = new _Sp_counted_ptr<_Ptr, _Lp>(__p);
	    }
	  __catch(...)
	    {
	      delete __p;
	      __throw_exception_again;
	    }
	}

__Sp_counted_deleter

When a deleter provided, the __Sp_counted_deleter used

      template<typename _Ptr, typename _Deleter, typename _Alloc>
	__shared_count(_Ptr __p, _Deleter __d, _Alloc __a) : _M_pi(0)
	{
	  typedef _Sp_counted_deleter<_Ptr, _Deleter, _Alloc, _Lp> _Sp_cd_type;
      // ...
    }

Memory allocated in guard object:

	      typename _Sp_cd_type::__allocator_type __a2(__a);
	      auto __guard = std::__allocate_guarded(__a2);
	      _Sp_cd_type* __mem = __guard.get();

Construct the _Sp_counted_deleter pointer

	      ::new (__mem) _Sp_cd_type(__p, std::move(__d), std::move(__a));
	      _M_pi = __mem;

Set the guard as null to avoid destructor, so as no delete on __mem While if anything wrong happened before this, the guard destructor works to delete the memory allocated for _M_pi

	      __guard = nullptr;

__Sp_counted_ptr_inplace

If _Sp_make_shared_tag set, make use of _Sp_counted_ptr_inplace to create pointer of typename __Tp

      template<typename _Tp, typename _Alloc, typename... _Args>
	__shared_count(_Sp_make_shared_tag, _Tp*, const _Alloc& __a,
		       _Args&&... __args)
	: _M_pi(0)
	{
	  typedef _Sp_counted_ptr_inplace<_Tp, _Alloc, _Lp> _Sp_cp_type;
      //...
	}

Copy constructor

For copy constructor, the _M_pi is shared, so that the counter and the inner pointer bound

      __shared_count(const __shared_count& __r) noexcept
      : _M_pi(__r._M_pi)
      {
	if (_M_pi != 0)
	  _M_pi->_M_add_ref_copy();
      }

And the counter operations are implemented in copy constructor, copy assignment and destructor

For unique_ptr

A version for unique ptr

      // Special case for unique_ptr<_Tp,_Del> to provide the strong guarantee.
      template<typename _Tp, typename _Del>
        explicit
	__shared_count(std::unique_ptr<_Tp, _Del>&& __r) : _M_pi(0)
	{
	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
	  // 2415. Inconsistency between unique_ptr and shared_ptr
	  if (__r.get() == nullptr) //cuased by user
	    return;

      //Get inner pointer type
	  using _Ptr = typename unique_ptr<_Tp, _Del>::pointer;
	  //Meta, get deleter type
	  using _Del2 = typename conditional<is_reference<_Del>::value,
	      reference_wrapper<typename remove_reference<_Del>::type>,
	      _Del>::type;

	  //Same way as previous constructor implementation
	  using _Sp_cd_type
	    = _Sp_counted_deleter<_Ptr, _Del2, allocator<void>, _Lp>;
	  using _Alloc = allocator<_Sp_cd_type>;
	  using _Alloc_traits = allocator_traits<_Alloc>;
	  _Alloc __a;
	  _Sp_cd_type* __mem = _Alloc_traits::allocate(__a, 1);
	  //Suppose no throw as it succeeded in unique_ptr construction
	  _Alloc_traits::construct(__a, __mem, __r.release(),
				   __r.get_deleter());  // non-throwing
	  _M_pi = __mem;
	}

From __weak_count

  // Now that __weak_count is defined we can define this constructor:
  template<_Lock_policy _Lp>
    inline
    __shared_count<_Lp>::__shared_count(const __weak_count<_Lp>& __r)
    : _M_pi(__r._M_pi)
    {
      if (_M_pi != nullptr)
	_M_pi->_M_add_ref_lock();
      else
	__throw_bad_weak_ptr();
    }

The count base object has both ref_count and weak_count contained. weak_count manipulates merely weak_ref, share_count manipulates merely share_ref. So the counter pointer _M_pi could be shared between shared_count and weak_count, and therefore has shared_count, weak_count and pinter bound.

Destructor

      ~__shared_count() noexcept
      {
	if (_M_pi != nullptr)
	  _M_pi->_M_release();
      }

Destructor -> release -> dispose -> delete inner pointer -> destroy -> delete counter pointer

__shared_ptr

The __shared_ptr combines shared ptr, weak ptr and unique ptr to some degree. And it provides conversion of inner pointer.

Accessories

Compatible

__sp_compatible_with is based on is_convertible

  /// is_convertible
  template<typename _From, typename _To>
    struct is_convertible
    : public __is_convertible_helper<_From, _To>::type
    { };

The type of this template is false_type/true_type asserted by __test(int). The input argument is just a dummy to distinguish all these test() functions

  template<typename _From, typename _To>
    class __is_convertible_helper<_From, _To, false>
    {
    //...
    public:
      typedef decltype(__test<_From, _To>(0)) type;
    };

The default value is false_type

      template<typename, typename>
	static false_type
	__test(...);

An auxiliary function defined to assert if an input type is _To1

       template<typename _To1>
	static void __test_aux(_To1);

The real job to assert if type _From could be converted into _To

      template<typename _From1, typename _To1,
	       typename = decltype(__test_aux<_To1>(std::declval<_From1>()))>
	static true_type
	__test(int);

std::declval<_From1>() get type of _From1, then put it into specialized test_aux<_To1>_ to assert if the template that expects a __To1_ type accepts type of __From1_. If sentence ___test_aux<_To1>(std::declval<_From1>()) compiled, the decltype then gets type, then __test(int) return true_type. Else, the compiler turns back to default version to return false_type

To be noted that the types are _From* and _To* instead of plain types.

And a special true_type case for array:

  template<typename _Up, size_t _Nm>
    struct __sp_compatible_with<_Up(*)[_Nm], _Up(*)[]>
    : true_type
    { };

Constructable

It is in fact pointer version of compatible:

  // otherwise, Y* shall be convertible to T*.
  template<typename _Tp, typename _Yp>
    struct __sp_is_constructible
    : is_convertible<_Yp*, _Tp*>::type
    { };

Assignable

Defined as

      // Constraint for assignment from shared_ptr and weak_ptr:
      template<typename _Yp>
	using _Assignable = _Compatible<_Yp, __shared_ptr&>;

As compatibility depends on implicit converter, but the only constructor of __shared_ptr receives raw pointer is defined as explicit, the assignable _Yp is in fact one of __share_ptr, __weak_ptr and unique_ptr.

weak_ptr

weak_ptr is similar to WeakReference in Java.

weak_ptr is a read-only access to shared_ptr. That is, weak_ptr depends on shared_ptr. There is no way to construct a weak_ptr from a raw pointer. The root of a weak_ptr is always a shared_ptr. And there is no way to touch the inner pointer from a weak_ptr. Whenever accessing to the inner pointer, a corresponding shared_ptr generated from the weak_ptr.

On the one hand, user of weak_ptr does not expect that the inner pointer is always valid. Of course it provides function to assert if the inner pointer is valid. If user want to write to inner pointer, the weak_ptr would transferred into a shared_ptr automatically. And manipulation of weak_ptr does not interference to memory management of the inner pointer in corresponding _shared_ptr.

On the other hand, the corresponding shared_ptr can go its own way without consideration of related weak_ptr

weak_ptr often works in cache: When is std::weak_ptr useful?

And to prevent cyclic reference of shared_ptr:

shared_ptr的原理与应用

Notes on std::shared_ptr and std::weak_ptr

enable_shared_from_this

enable_shared_from_this provides a method to get shared_ptr from inner pointer to avoid multiple independent shared_ptr over a same inner pointer.

__enable_shared_from_this is the super class to provide this function, by function of shared_from_this. The sub-classes implement this super class to inherit this function.

The _enable_shared_from_this class defines only protected constructor, so the object of the class would only be created in sub-class’s constructor by default.

    protected:
      constexpr __enable_shared_from_this() noexcept { }

      __enable_shared_from_this(const __enable_shared_from_this&) noexcept { }

      __enable_shared_from_this&
      operator=(const __enable_shared_from_this&) noexcept
      { return *this; }

      ~__enable_shared_from_this() { }

It holds an object of __weak_ptr, to avoid the case that the inner pointer holds a strong reference of itself.

      mutable __weak_ptr<_Tp, _Lp>  _M_weak_this;

The constructor of __shared_ptr tries to create the associated object automatically:

      template<typename _Yp, typename _Deleter, typename = _SafeConv<_Yp>>
	__shared_ptr(_Yp* __p, _Deleter __d)
	: _M_ptr(__p), _M_refcount(__p, std::move(__d))
	{
	  static_assert(__is_invocable<_Deleter&, _Yp*&>::value,
	      "deleter expression d(p) is well-formed");
	  _M_enable_shared_from_this_with(__p);
	}

The definition of __M_enable_shared_from_this():

      template<typename _Yp, typename _Yp2 = typename remove_cv<_Yp>::type>
	typename enable_if<__has_esft_base<_Yp2>::value>::type
	_M_enable_shared_from_this_with(_Yp* __p) noexcept
	{
	  if (auto __base = __enable_shared_from_this_base(_M_refcount, __p))
	    __base->_M_weak_assign(const_cast<_Yp2*>(__p), _M_refcount);
	}

It gets the plain type of _Yp by remove_cv, and decides if the type _Yp has __enable_shared_from_this inherited.

If _Yp is a sub-class,

      friend const __enable_shared_from_this*
      __enable_shared_from_this_base(const __shared_count<_Lp>&,
				     const __enable_shared_from_this* __p)
      { return __p; }

The pointer __p converts to pointer of base type __enable_shared_from_this, and return this pointer to caller.

    private:
      template<typename _Tp1>
	void
	_M_weak_assign(_Tp1* __p, const __shared_count<_Lp>& __n) const noexcept
	{ _M_weak_this._M_assign(__p, __n); }

Then the __weak_ptr binds the counter and the pointer.

Therefore, the __weak_ptr is created by default in construction of the __shared_ptr when the inner pointer was wrapped in very beginning.

If the type of inner pointer has no intention to implement this function, nothing happened.

      template<typename _Yp, typename _Yp2 = typename remove_cv<_Yp>::type>
	typename enable_if<!__has_esft_base<_Yp2>::value>::type
	_M_enable_shared_from_this_with(_Yp*) noexcept
	{ }

shared_ptr

make_shared

The function provides an easy way to create a share_ptr from inner pointer type. It is also a function wrapper of shared_ptr creation to prevent exception thrown in new ref. Ref: shared_ptr

nullptr

shared_ptr implements special treatment for nullptr.

without deleter

      constexpr shared_ptr(nullptr_t) noexcept : shared_ptr() { }
      constexpr shared_ptr() noexcept : __shared_ptr<_Tp>() { }

      constexpr __shared_ptr() noexcept
      : _M_ptr(0), _M_refcount()
      { }

      constexpr __shared_count() noexcept : _M_pi(0)
      { }

with deleter

      template<typename _Deleter>
	shared_ptr(nullptr_t __p, _Deleter __d)
        : __shared_ptr<_Tp>(__p, std::move(__d)) { }

      template<typename _Deleter>
	__shared_ptr(nullptr_t __p, _Deleter __d)
	: _M_ptr(0), _M_refcount(__p, std::move(__d))
	{ }

Don’t know why there is no special treatment for __shared_count, maybe the library suppose the user knows what is going on with deleter assigned. ```c++ template<typename _Ptr, typename _Deleter, typename _Alloc> __shared_count(_Ptr __p, _Deleter __d, _Alloc __a) : _M_pi(0) { typedef _Sp_counted_deleter<_Ptr, _Deleter, _Alloc, _Lp> _Sp_cd_type; __try { typename _Sp_cd_type::__allocator_type __a2(__a); auto __guard = std::__allocate_guarded(__a2); _Sp_cd_type* __mem = __guard.get(); ::new (__mem) _Sp_cd_type(__p, std::move(__d), std::move(__a)); _M_pi = __mem; __guard = nullptr; } __catch(…) { __d(__p); // Call _Deleter on __p. __throw_exception_again; } }

And validation in ___shared_ptr_access_
```c++
      element_type&
      operator*() const noexcept
      {
	__glibcxx_assert(_M_get() != nullptr);
	return *_M_get();
      }