Merge pull request #4255 from pgavlin/GcInfoArrayList

Refactor `StructArrayList` for the GC info encoder.

5 files changed, 112 insertions, 6 deletions

diff --git a/src/gcinfo/CMakeLists.txt b/src/gcinfo/CMakeLists.txt
index d8b91d11f0..53a1ad2591 100644
--- a/src/gcinfo/CMakeLists.txt
+++ b/src/gcinfo/CMakeLists.txt
@@ -1,6 +1,7 @@
 set(CMAKE_INCLUDE_CURRENT_DIR ON)
 
 set( GCINFO_SOURCES
+  arraylist.cpp
   gcinfoencoder.cpp
   dbggcinfoencoder.cpp
 )
diff --git a/src/gcinfo/arraylist.cpp b/src/gcinfo/arraylist.cpp
new file mode 100644
index 0000000000..566304c7ac
--- /dev/null
+++ b/src/gcinfo/arraylist.cpp
@@ -0,0 +1,104 @@
+// Licensed to the .NET Foundation under one or more agreements.
+// The .NET Foundation licenses this file to you under the MIT license.
+// See the LICENSE file in the project root for more information.
+
+#include <stdint.h>
+#include <windows.h>
+#include "debugmacros.h"
+#include "iallocator.h"
+#include "gcinfoarraylist.h"
+#include "safemath.h"
+
+inline size_t roundUp(size_t size, size_t alignment)
+{
+    // `alignment` must be a power of two
+    assert(alignment != 0);
+    assert((alignment & (alignment - 1)) == 0);
+
+    return (size + (alignment - 1)) & ~(alignment - 1);
+}
+
+GcInfoArrayListBase::GcInfoArrayListBase(IAllocator* allocator)
+    : m_allocator(allocator),
+      m_firstChunk(nullptr),
+      m_lastChunk(nullptr),
+      m_lastChunkCount(0),
+      m_lastChunkCapacity(0),
+      m_itemCount(0)
+{
+    assert(m_allocator != nullptr);
+}
+
+GcInfoArrayListBase::~GcInfoArrayListBase()
+{
+    for (ChunkBase* list = m_firstChunk, *chunk; list != nullptr; list = chunk)
+    {
+        chunk = list->m_next;
+        m_allocator->Free(list);
+    }
+}
+
+void GcInfoArrayListBase::AppendNewChunk(size_t firstChunkCapacity, size_t elementSize, size_t chunkAlignment)
+{
+    size_t chunkCapacity = (m_firstChunk == nullptr) ? firstChunkCapacity : (m_lastChunkCapacity * GrowthFactor);
+
+    S_SIZE_T chunkSize = S_SIZE_T(roundUp(sizeof(ChunkBase), chunkAlignment)) + (S_SIZE_T(elementSize) * S_SIZE_T(chunkCapacity));
+    assert(!chunkSize.IsOverflow());
+
+    ChunkBase* chunk = reinterpret_cast<ChunkBase*>(m_allocator->Alloc(chunkSize.Value()));
+    chunk->m_next = nullptr;
+
+    if (m_lastChunk != nullptr)
+    {
+        assert(m_firstChunk != nullptr);
+        m_lastChunk->m_next = chunk;
+    }
+    else
+    {
+        assert(m_lastChunk == nullptr);
+        m_firstChunk = chunk;
+    }
+
+    m_lastChunk = chunk;
+    m_lastChunkCount = 0;
+    m_lastChunkCapacity = chunkCapacity;
+}
+
+GcInfoArrayListBase::IteratorBase::IteratorBase(GcInfoArrayListBase* list, size_t firstChunkCapacity)
+    : m_list(list)
+{
+    assert(m_list != nullptr);
+
+    // Note: if the list is empty, m_list->firstChunk == nullptr == m_list->lastChunk and m_lastChunkCount == 0.
+    //       In that case, the next two lines will set m_currentChunk to nullptr and m_currentChunkCount to 0.
+    m_currentChunk = m_list->m_firstChunk;
+    m_currentChunkCount = (m_currentChunk == m_list->m_lastChunk) ? m_list->m_lastChunkCount : firstChunkCapacity;
+}
+
+GcInfoArrayListBase::ChunkBase* GcInfoArrayListBase::IteratorBase::GetNextChunk(size_t& elementCount)
+{
+    if (m_currentChunk == nullptr)
+    {
+        elementCount = 0;
+        return nullptr;
+    }
+
+    ChunkBase* chunk = m_currentChunk;
+    elementCount = m_currentChunkCount;
+
+    m_currentChunk = m_currentChunk->m_next;
+    if (m_currentChunk == nullptr)
+    {
+        m_currentChunkCount = 0;
+    }
+    else if (m_currentChunk == m_list->m_lastChunk)
+    {
+        m_currentChunkCount = m_list->m_lastChunkCount;
+    }
+    else
+    {
+        m_currentChunkCount *= GrowthFactor;
+    }
+
+    return chunk;
+}
diff --git a/src/gcinfo/dbggcinfoencoder.cpp b/src/gcinfo/dbggcinfoencoder.cpp
index eb18f69570..c41db2fe7e 100644
--- a/src/gcinfo/dbggcinfoencoder.cpp
+++ b/src/gcinfo/dbggcinfoencoder.cpp
@@ -74,7 +74,7 @@ GcInfoEncoder::GcInfoEncoder(
 #endif
 #endif
         m_FullyInterruptibleInfoWriter( pJitAllocator ),
-        m_LifetimeTransitions()
+        m_LifetimeTransitions( pJitAllocator )
 {
     _ASSERTE( pCorJitInfo != NULL );
     _ASSERTE( pMethodInfo != NULL );
@@ -354,7 +354,7 @@ void GcInfoEncoder::SetSlotState(
     transition.CodeOffset = instructionOffset;
     transition.BecomesLive = ( slotState == GC_SLOT_LIVE );
 
-    *( m_LifetimeTransitions.AppendThrowing() ) = transition;
+    *( m_LifetimeTransitions.Append() ) = transition;
 }
 
 
diff --git a/src/gcinfo/gcinfo.settings.targets b/src/gcinfo/gcinfo.settings.targets
index b20bca410d..f600e2a904 100644
--- a/src/gcinfo/gcinfo.settings.targets
+++ b/src/gcinfo/gcinfo.settings.targets
@@ -12,6 +12,7 @@
 
   <!-- Leaf Project Items -->
   <ItemGroup>
+    <CppCompile Include="..\ArrayList.cpp" />
     <CppCompile Include="..\GCInfoEncoder.cpp" />
     <CppCompile Include="..\DbgGCInfoEncoder.cpp" />
   </ItemGroup>
diff --git a/src/gcinfo/gcinfoencoder.cpp b/src/gcinfo/gcinfoencoder.cpp
index a013c4258a..95673a1677 100644
--- a/src/gcinfo/gcinfoencoder.cpp
+++ b/src/gcinfo/gcinfoencoder.cpp
@@ -438,8 +438,8 @@ GcInfoEncoder::GcInfoEncoder(
             )
     :   m_Info1( pJitAllocator ),
         m_Info2( pJitAllocator ),
-        m_InterruptibleRanges(),
-        m_LifetimeTransitions()
+        m_InterruptibleRanges( pJitAllocator ),
+        m_LifetimeTransitions( pJitAllocator )
 #ifdef VERIFY_GCINFO
         , m_DbgEncoder(pCorJitInfo, pMethodInfo, pJitAllocator)
 #endif    
@@ -647,7 +647,7 @@ void GcInfoEncoder::DefineInterruptibleRange( UINT32 startInstructionOffset, UIN
             InterruptibleRange range;
             range.NormStartOffset = normStartOffset;
             range.NormStopOffset = normStopOffset;
-            m_pLastInterruptibleRange = m_InterruptibleRanges.AppendThrowing();
+            m_pLastInterruptibleRange = m_InterruptibleRanges.Append();
             *m_pLastInterruptibleRange = range;
         }
     }
@@ -679,7 +679,7 @@ void GcInfoEncoder::SetSlotState(
     transition.BecomesLive = ( slotState == GC_SLOT_LIVE );
     transition.IsDeleted = FALSE;
 
-    *( m_LifetimeTransitions.AppendThrowing() ) = transition;
+    *( m_LifetimeTransitions.Append() ) = transition;
 
     LOG((LF_GCINFO, LL_INFO1000000, LOG_GCSLOTDESC_FMT " %s at %x\n", LOG_GCSLOTDESC_ARGS(&m_SlotTable[slotId]), slotState == GC_SLOT_LIVE ? "live" : "dead", instructionOffset));
 }