Hazard Pointer:

- fixed a bug actual for intrusive containers
- optimized scan() function

diff --git a/cds/gc/details/hp.h b/cds/gc/details/hp.h
index fde65fddbdb09148a4d8bb7d69e86d4991521d3a..abc435ef0b76befbbcedde050490bf71025abe9f 100644 (file)
--- a/cds/gc/details/hp.h
+++ b/cds/gc/details/hp.h
@@ -290,12 +290,6 @@ namespace cds {
             */
             void                DeleteHPRec( hplist_node * pNode );
 
             */
             void                DeleteHPRec( hplist_node * pNode );
 

-            /// Permanently deletes retired pointer \p p
-            /**
-                Caveat: for performance reason this function is defined as inline and cannot be called directly
-            */
-            void                DeletePtr( details::retired_ptr& p );
-

             void detachAllThread();
 
         public:
             void detachAllThread();
 
         public:

diff --git a/src/hp_gc.cpp b/src/hp_gc.cpp
index 05b5f748f50750b7dd537c920ae5083da90fdc00..dec6e245665949b693153d65123dd713bc1225ed 100644 (file)
--- a/src/hp_gc.cpp
+++ b/src/hp_gc.cpp
@@ -74,7 +74,7 @@ namespace cds { namespace gc {
                 details::retired_vector::iterator itRetired = vect.begin();
                 details::retired_vector::iterator itRetiredEnd = vect.end();
                 while ( itRetired != itRetiredEnd ) {
                 details::retired_vector::iterator itRetired = vect.begin();
                 details::retired_vector::iterator itRetiredEnd = vect.end();
                 while ( itRetired != itRetiredEnd ) {

-                    DeletePtr( *itRetired );
+                    itRetired->free();

                     ++itRetired;
                 }
                 vect.clear();
                     ++itRetired;
                 }
                 vect.clear();


@@ -86,26 +86,20 @@ namespace cds { namespace gc {
 
         inline GarbageCollector::hplist_node * GarbageCollector::NewHPRec()
         {
 
         inline GarbageCollector::hplist_node * GarbageCollector::NewHPRec()
         {

-            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_AllocNewHPRec );
+            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_AllocNewHPRec )

             return new hplist_node( *this );
         }
 
         inline void GarbageCollector::DeleteHPRec( hplist_node * pNode )
         {
             return new hplist_node( *this );
         }
 
         inline void GarbageCollector::DeleteHPRec( hplist_node * pNode )
         {

-            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_DeleteHPRec );
+            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_DeleteHPRec )

             assert( pNode->m_arrRetired.size() == 0 );
             delete pNode;
         }
 
             assert( pNode->m_arrRetired.size() == 0 );
             delete pNode;
         }
 

-        inline void GarbageCollector::DeletePtr( details::retired_ptr& p )
-        {
-            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_DeletedNode );
-            p.free();
-        }
-

         details::hp_record * GarbageCollector::alloc_hp_record()
         {
         details::hp_record * GarbageCollector::alloc_hp_record()
         {

-            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_AllocHPRec );
+            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_AllocHPRec )

 
             hplist_node * hprec;
             const cds::OS::ThreadId nullThreadId = cds::OS::c_NullThreadId;
 
             hplist_node * hprec;
             const cds::OS::ThreadId nullThreadId = cds::OS::c_NullThreadId;


@@ -139,10 +133,11 @@ namespace cds { namespace gc {
         void GarbageCollector::free_hp_record( details::hp_record * pRec )
         {
             assert( pRec != nullptr );
         void GarbageCollector::free_hp_record( details::hp_record * pRec )
         {
             assert( pRec != nullptr );

-            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_RetireHPRec );
+            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_RetireHPRec )

 
             pRec->clear();
             Scan( pRec );
 
             pRec->clear();
             Scan( pRec );

+            HelpScan( pRec );

             hplist_node * pNode = static_cast<hplist_node *>( pRec );
             pNode->m_idOwner.store( cds::OS::c_NullThreadId, atomics::memory_order_release );
         }
             hplist_node * pNode = static_cast<hplist_node *>( pRec );
             pNode->m_idOwner.store( cds::OS::c_NullThreadId, atomics::memory_order_release );
         }


@@ -161,7 +156,7 @@ namespace cds { namespace gc {
 
         void GarbageCollector::classic_scan( details::hp_record * pRec )
         {
 
         void GarbageCollector::classic_scan( details::hp_record * pRec )
         {

-            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_ScanCallCount );
+            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_ScanCallCount )

 
             std::vector< void * >   plist;
             plist.reserve( m_nMaxThreadCount * m_nHazardPointerCount );
 
             std::vector< void * >   plist;
             plist.reserve( m_nMaxThreadCount * m_nHazardPointerCount );


@@ -192,22 +187,27 @@ namespace cds { namespace gc {
             // clear() is just set up item counter to 0, the items is not destroyed
             arrRetired.clear();
 
             // clear() is just set up item counter to 0, the items is not destroyed
             arrRetired.clear();
 

-            std::vector< void * >::iterator itBegin = plist.begin();
-            std::vector< void * >::iterator itEnd = plist.end();
-            while ( itRetired != itRetiredEnd ) {
-                if ( std::binary_search( itBegin, itEnd, itRetired->m_p) ) {
-                    CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_DeferredNode );
-                    arrRetired.push( *itRetired );
+            {
+                std::vector< void * >::iterator itBegin = plist.begin();
+                std::vector< void * >::iterator itEnd = plist.end();
+                size_t nDeferredCount = 0;
+                while ( itRetired != itRetiredEnd ) {
+                    if ( std::binary_search( itBegin, itEnd, itRetired->m_p ) ) {
+                        arrRetired.push( *itRetired );
+                        ++nDeferredCount;
+                    }
+                    else
+                        itRetired->free();
+                    ++itRetired;

                 }
                 }

-                else
-                    DeletePtr( *itRetired );
-                ++itRetired;
+                CDS_HAZARDPTR_STATISTIC( m_Stat.m_DeferredNode += nDeferredCount )
+                CDS_HAZARDPTR_STATISTIC( m_Stat.m_DeletedNode += (itRetiredEnd - arrRetired.begin()) - nDeferredCount )

             }
         }
 
         void GarbageCollector::inplace_scan( details::hp_record * pRec )
         {
             }
         }
 
         void GarbageCollector::inplace_scan( details::hp_record * pRec )
         {

-            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_ScanCallCount );
+            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_ScanCallCount )

 
             // In-place scan algo uses LSB of retired ptr as a mark for internal purposes.
             // It is correct if all retired pointers are ar least 2-byte aligned (LSB is zero).
 
             // In-place scan algo uses LSB of retired ptr as a mark for internal purposes.
             // It is correct if all retired pointers are ar least 2-byte aligned (LSB is zero).


@@ -228,20 +228,35 @@ namespace cds { namespace gc {
             // Sort retired pointer array
             std::sort( itRetired, itRetiredEnd, cds::gc::details::retired_ptr::less );
 
             // Sort retired pointer array
             std::sort( itRetired, itRetiredEnd, cds::gc::details::retired_ptr::less );
 

+            // Check double free
+            /*
+            {
+                auto it = itRetired;
+                auto itPrev = it;
+                while ( ++it != itRetiredEnd ) {
+                    if ( it->m_p == itPrev->m_p )
+                        throw std::runtime_error( "Double free" );
+                    itPrev = it;
+                }
+            }
+            */
+

             // Search guarded pointers in retired array
             hplist_node * pNode = m_pListHead.load( atomics::memory_order_acquire );
 
             {
                 details::retired_ptr dummyRetired;
                 while ( pNode ) {
             // Search guarded pointers in retired array
             hplist_node * pNode = m_pListHead.load( atomics::memory_order_acquire );
 
             {
                 details::retired_ptr dummyRetired;
                 while ( pNode ) {

-                    for ( size_t i = 0; i < m_nHazardPointerCount; ++i ) {
-                        void * hptr = pNode->m_hzp[i];
-                        if ( hptr ) {
-                            dummyRetired.m_p = hptr;
-                            details::retired_vector::iterator it = std::lower_bound( itRetired, itRetiredEnd, dummyRetired, cds::gc::details::retired_ptr::less );
-                            if ( it != itRetiredEnd && it->m_p == hptr ) {
-                                // Mark retired pointer as guarded
-                                it->m_n |= 1;
+                    if ( !pNode->m_bFree.load( atomics::memory_order_acquire ) ) {
+                        for ( size_t i = 0; i < m_nHazardPointerCount; ++i ) {
+                            void * hptr = pNode->m_hzp[i];
+                            if ( hptr ) {
+                                dummyRetired.m_p = hptr;
+                                details::retired_vector::iterator it = std::lower_bound( itRetired, itRetiredEnd, dummyRetired, cds::gc::details::retired_ptr::less );
+                                if ( it != itRetiredEnd && it->m_p == hptr ) {
+                                    // Mark retired pointer as guarded
+                                    it->m_n |= 1;
+                                }

                             }
                         }
                     }
                             }
                         }
                     }


@@ -258,20 +273,22 @@ namespace cds { namespace gc {
                         if ( itInsert != it )
                             *itInsert = *it;
                         ++itInsert;
                         if ( itInsert != it )
                             *itInsert = *it;
                         ++itInsert;

-                        CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_DeferredNode );

                     }
                     else {
                         // Retired pointer may be freed
                     }
                     else {
                         // Retired pointer may be freed

-                        DeletePtr( *it );
+                        it->free();

                     }
                 }
                     }
                 }

-                pRec->m_arrRetired.size( itInsert - itRetired );
+                const size_t nDeferred = itInsert - itRetired;
+                pRec->m_arrRetired.size( nDeferred );
+                CDS_HAZARDPTR_STATISTIC( m_Stat.m_DeferredNode += nDeferred )
+                CDS_HAZARDPTR_STATISTIC( m_Stat.m_DeletedNode += (itRetiredEnd - itRetired) - nDeferred )

             }
         }
 
         void GarbageCollector::HelpScan( details::hp_record * pThis )
         {
             }
         }
 
         void GarbageCollector::HelpScan( details::hp_record * pThis )
         {

-            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_HelpScanCallCount );
+            CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_HelpScanCallCount )

 
             assert( static_cast<hplist_node *>(pThis)->m_idOwner.load(atomics::memory_order_relaxed) == cds::OS::getCurrentThreadId() );
 
 
             assert( static_cast<hplist_node *>(pThis)->m_idOwner.load(atomics::memory_order_relaxed) == cds::OS::getCurrentThreadId() );
 


@@ -308,7 +325,7 @@ namespace cds { namespace gc {
                 while ( itRetired != itRetiredEnd ) {
                     dest.push( *itRetired );
                     if ( dest.isFull()) {
                 while ( itRetired != itRetiredEnd ) {
                     dest.push( *itRetired );
                     if ( dest.isFull()) {

-                        CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_CallScanFromHelpScan );
+                        CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_CallScanFromHelpScan )

                         Scan( pThis );
                     }
                     ++itRetired;
                         Scan( pThis );
                     }
                     ++itRetired;


@@ -317,6 +334,8 @@ namespace cds { namespace gc {
 
                 hprec->m_bFree.store(true, atomics::memory_order_release);
                 hprec->m_idOwner.store( nullThreadId, atomics::memory_order_release );
 
                 hprec->m_bFree.store(true, atomics::memory_order_release);
                 hprec->m_idOwner.store( nullThreadId, atomics::memory_order_release );

+
+                Scan( pThis );

             }
         }
 
             }
         }
 

diff --git a/tests/unit/queue/intrusive_queue_reader_writer.cpp b/tests/unit/queue/intrusive_queue_reader_writer.cpp
index 7a0c718ee1755c7fa5418db2c35c07b63406542b..b5ad38c48f5e01b86e3f1dca14ad25c5f3ac1438 100644 (file)
--- a/tests/unit/queue/intrusive_queue_reader_writer.cpp
+++ b/tests/unit/queue/intrusive_queue_reader_writer.cpp
@@ -361,10 +361,12 @@ namespace queue {
         {
             value_array<typename Queue::value_type> arrValue( s_nQueueSize );
             {
         {
             value_array<typename Queue::value_type> arrValue( s_nQueueSize );
             {

-                Queue q;
-                test_with(q, arrValue, 0, 0);
+                {
+                    Queue q;
+                    test_with( q, arrValue, 0, 0 );
+                }
+                Queue::gc::force_dispose();

             }
             }

-            Queue::gc::force_dispose();

         }
 
         template <typename Queue>
         }
 
         template <typename Queue>

diff --git a/tests/unit/queue/queue_reader_writer.cpp b/tests/unit/queue/queue_reader_writer.cpp
index 6a4cfe3de22fb2b222ed2b7191ae4209d13b0715..74f90c8c97ce8f9ccd68287ee8f4deeed24497a8 100644 (file)
--- a/tests/unit/queue/queue_reader_writer.cpp
+++ b/tests/unit/queue/queue_reader_writer.cpp
@@ -182,7 +182,7 @@ namespace queue {
 
     protected:
         template <class Queue>
 
     protected:
         template <class Queue>

-        void analyze( CppUnitMini::ThreadPool& pool, Queue& testQueue, size_t nLeftOffset = 0, size_t nRightOffset = 0  )
+        void analyze( CppUnitMini::ThreadPool& pool, Queue& testQueue, size_t /*nLeftOffset*/ = 0, size_t nRightOffset = 0  )

         {
             typedef ReaderThread<Queue> Reader;
             typedef WriterThread<Queue> Writer;
         {
             typedef ReaderThread<Queue> Reader;
             typedef WriterThread<Queue> Writer;