[libc++] Fix use-after-free when building with _LIBCPP_DEBUG=1

[thomasanderson]

Summary

The issue is the following code:

__cn1->__add(*__ip);
(*__ip)->__c_ = __cn1;

__ip points into the array of iterators for container __cn2. This code adds
the iterator to the array of iterators for __cn1, and updates the iterator to
point to the new container.

This code works fine, except when __cn1 and __cn2 are the same container.
__cn1->__add() might need to grow the array of iterators, and when it does,
__ip becomes invalid, so the second line becomes a use-after-free error.

Simply swapping the order of the above two lines is not sufficient, because of
the memmove() below. The easiest and most performant solution is just to skip
touching any iterators if the containers are the same.

[EricWF]

Can you add a test in test/libcxx/debug/containers/db_sequence_container_iterators.pass.cpp?

[thomasanderson]

Added test: crashes before change, passes after

libcxx/include/list

#endif
     {
         __link_pointer __f = __c.__end_.__next_;
         __link_pointer __l = __c.__end_.__prev_;
         base::__unlink_nodes(__f, __l);
         __link_nodes(__p.__ptr_, __f, __l);
         base::__sz() += __c.__sz();
         __c.__sz() = 0;
 #if _LIBCPP_DEBUG_LEVEL >= 2
+        if (&__c != this) {
             __libcpp_db* __db = __get_db();
             __c_node* __cn1 = __db->__find_c_and_lock(this);
             __c_node* __cn2 = __db->__find_c(&__c);
             for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
             {
                 --__ip;
                 iterator* __i = static_cast<iterator*>((*__ip)->__i_);
                 if (__i->__ptr_ != __c.__end_as_link())
                 {
                     __cn1->__add(*__ip);
                     (*__ip)->__c_ = __cn1;
                     if (--__cn2->end_ != __ip)
                         memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
                 }
             }
             __db->unlock();
+        }
 #endif
     }
 }
 
 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i)
 {
#endif
     if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
     {
         __link_pointer __f = __i.__ptr_;
         base::__unlink_nodes(__f, __f);
         __link_nodes(__p.__ptr_, __f, __f);
         --__c.__sz();
         ++base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
+        if (&__c != this) {
             __libcpp_db* __db = __get_db();
             __c_node* __cn1 = __db->__find_c_and_lock(this);
             __c_node* __cn2 = __db->__find_c(&__c);
             for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
             {
                 --__ip;
                 iterator* __j = static_cast<iterator*>((*__ip)->__i_);
                 if (__j->__ptr_ == __f)
                 {
                     __cn1->__add(*__ip);
                     (*__ip)->__c_ = __cn1;
                     if (--__cn2->end_ != __ip)
                         memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
                 }
             }
             __db->unlock();
+        }
 #endif
     }
 }
 
 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l)
 {
if (__f != __l)
         {
             size_type __s = _VSTD::distance(__f, __l) + 1;
             __c.__sz() -= __s;
             base::__sz() += __s;
         }
         base::__unlink_nodes(__first, __last);
         __link_nodes(__p.__ptr_, __first, __last);
 #if _LIBCPP_DEBUG_LEVEL >= 2
+        if (&__c != this) {
             __libcpp_db* __db = __get_db();
             __c_node* __cn1 = __db->__find_c_and_lock(this);
             __c_node* __cn2 = __db->__find_c(&__c);
             for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
             {
                 --__ip;
                 iterator* __j = static_cast<iterator*>((*__ip)->__i_);
                 for (__link_pointer __k = __f.__ptr_;
                                               __k != __l.__ptr_; __k = __k->__next_)
                 {
                     if (__j->__ptr_ == __k)
                     {
                         __cn1->__add(*__ip);
                         (*__ip)->__c_ = __cn1;
                         if (--__cn2->end_ != __ip)
                             memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
                     }
                 }
             }
             __db->unlock();
+        }
 #endif
     }
 }
 
 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::remove(const value_type& __x)
 {

libcxx/test/libcxx/debug/containers/db_sequence_container_iterators.pass.cpp

try {
       if constexpr (CT == CT_List || CT == CT_Deque) {
         PopFront(); // FIXME: Run with forward list as well
       }
       if constexpr (CT == CT_List || CT == CT_ForwardList) {
         RemoveFirstElem();
       }
       if constexpr (CT == CT_List) {
         SpliceFirstElem();
+        SpliceSameContainer();
       }
     } catch (...) {
       assert(false && "uncaught debug exception");
     }
   }
 
 private:
   static void SanityTest() {
static void SpliceFirstElem() {
     }
     {
       Container C = makeContainer(1);
       Container C2;
       C2.splice(C2.end(), C, C.begin());
     }
   }
 
+  static void SpliceSameContainer() {
+    CHECKPOINT("splice(<same-container>)");
+    Container C = {1, 1};
+    C.splice(C.end(), C, C.begin());
+  }
 
   static void SpliceFirstElemAfter() {
     // See llvm.org/PR35564
     CHECKPOINT("splice(<first-elem>)");
     {
       Container C = makeContainer(1);
       Container C2;
       C2.splice_after(C2.begin(), C, C.begin(), ++C.begin());