text: /*
   * Copyright 2010-2020 JetBrains s.r.o.
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  #include <string.h>
  #include <stdio.h>
  
  #include <cstddef> // for offsetof
  #include <mutex>
  
  // Allow concurrent global cycle collector.
  #define USE_CYCLIC_GC 0
  
  // CycleDetector internally uses static local with runtime initialization,
  // which requires atomics. Atomics are not available on WASM.
  #ifdef KONAN_WASM
  #define USE_CYCLE_DETECTOR 0
  #else
  #define USE_CYCLE_DETECTOR 1
  #endif
  
  #include "Alloc.h"
  #include "KAssert.h"
  #include "Atomic.h"
  #include "Cleaner.h"
  #include "CompilerConstants.hpp"
  #if USE_CYCLIC_GC
  #include "CyclicCollector.h"
  #endif  // USE_CYCLIC_GC
  #include "Exceptions.h"
  #include "FinalizerHooks.hpp"
  #include "FreezeHooks.hpp"
  #include "KString.h"
  #include "Memory.h"
  #include "MemoryPrivate.hpp"
  #include "Mutex.hpp"
  #include "Natives.h"
  #include "ObjectTraversal.hpp"
  #include "Porting.h"
  #include "Runtime.h"
  #include "Utils.hpp"
  #include "WorkerBoundReference.h"
  #include "Weak.h"
  
  #ifdef KONAN_OBJC_INTEROP
  #include "ObjCMMAPI.h"
  #endif
  
  // If garbage collection algorithm for cyclic garbage to be used.
  // We are using the Bacon's algorithm for GC, see
  // http://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon03Pure.pdf.
  #define USE_GC 1
  // Define to 1 to print all memory operations.
  #define TRACE_MEMORY 0
  // Define to 1 to print major GC events.
  #define TRACE_GC 0
  // Collect memory manager events statistics.
  #define COLLECT_STATISTIC 0
  // Define to 1 to print detailed time statistics for GC events.
  #define PROFILE_GC 0
  
  #if COLLECT_STATISTIC
  #include <algorithm>
  #endif
  
  namespace {
  
  ALWAYS_INLINE bool IsStrictMemoryModel() noexcept {
      return CurrentMemoryModel == MemoryModel::kStrict;
  }
  
  typedef uint32_t container_size_t;
  
  // Granularity of arena container chunks.
  constexpr container_size_t kContainerAlignment = 1024;
  // Single object alignment.
  constexpr container_size_t kObjectAlignment = 8;
  
  // Required e.g. for object size computations to be correct.
  static_assert(sizeof(ContainerHeader) % kObjectAlignment == 0, "sizeof(ContainerHeader) is not aligned");
  
  #if TRACE_MEMORY
  #undef TRACE_GC
  #define TRACE_GC 1
  #define MEMORY_LOG(...) konan::consolePrintf(__VA_ARGS__);
  #else
  #define MEMORY_LOG(...)
  #endif
  
  #if TRACE_GC
  #define GC_LOG(...) konan::consolePrintf(__VA_ARGS__);
  #else
  #define GC_LOG(...)
  #endif
  
  #if USE_GC
  // Collection threshold default (collect after having so many elements in the
  // release candidates set).
  constexpr size_t kGcThreshold = 8 * 1024;
  // Ergonomic thresholds.
  // If GC to computations time ratio is above that value,
  // increase GC threshold by 1.5 times.
  constexpr double kGcToComputeRatioThreshold = 0.5;
  // Never exceed this value when increasing GC threshold.
  constexpr size_t kMaxErgonomicThreshold = 32 * 1024;
  // Threshold of size for toFree set, triggering actual cycle collector.
  constexpr size_t kMaxToFreeSizeThreshold = 8 * 1024;
  // Never exceed this value when increasing size for toFree set, triggering actual cycle collector.
  constexpr size_t kMaxErgonomicToFreeSizeThreshold = 8 * 1024 * 1024;
  // How many elements in finalizer queue allowed before cleaning it up.
  constexpr int32_t kFinalizerQueueThreshold = 32;
  // If allocated that much memory since last GC - force new GC.
  constexpr size_t kMaxGcAllocThreshold = 8 * 1024 * 1024;
  // If the ratio of GC collection cycles time to program execution time is greater this value,
  // increase GC threshold for cycles collection.
  constexpr double kGcCollectCyclesLoadRatio = 0.3;
  // Minimum time of cycles collection to change thresholds.
  constexpr size_t kGcCollectCyclesMinimumDuration = 200;
  
  #endif  // USE_GC
  
  typedef KStdUnorderedSet<ContainerHeader*> ContainerHeaderSet;
  typedef KStdVector<ContainerHeader*> ContainerHeaderList;
  typedef KStdDeque<ContainerHeader*> ContainerHeaderDeque;
  typedef KStdVector<KRef> KRefList;
  typedef KStdVector<KRef*> KRefPtrList;
  typedef KStdUnorderedSet<KRef> KRefSet;
  typedef KStdUnorderedMap<KRef, KInt> KRefIntMap;
  typedef KStdDeque<KRef> KRefDeque;
  typedef KStdDeque<KRefList> KRefListDeque;
  
  // A little hack that allows to enable -O2 optimizations
  // Prevents clang from replacing FrameOverlay struct
  // with single pointer.
  // Can be removed when FrameOverlay will become more complex.
  #pragma clang diagnostic push
  #pragma clang diagnostic ignored "-Wunused-variable"
  FrameOverlay exportFrameOverlay;
  #pragma clang diagnostic pop
  
  // Current number of allocated containers.
  volatile int allocCount = 0;
  volatile int aliveMemoryStatesCount = 0;
  
  #if USE_CYCLIC_GC
  KBoolean g_hasCyclicCollector = true;
  #endif  // USE_CYCLIC_GC
  
  // TODO: Consider using ObjHolder.
  class ScopedRefHolder : private kotlin::MoveOnly {
   public:
    ScopedRefHolder() = default;
  
    explicit ScopedRefHolder(KRef obj);
  
    ScopedRefHolder(ScopedRefHolder&& other) noexcept: obj_(other.obj_) {
      other.obj_ = nullptr;
    }
  
    ScopedRefHolder& operator=(ScopedRefHolder&& other) noexcept {
      ScopedRefHolder tmp(std::move(other));
      swap(tmp);
      return *this;
    }
  
    ~ScopedRefHolder();
  
    void swap(ScopedRefHolder& other) noexcept {
      std::swap(obj_, other.obj_);
    }
  
   private:
    KRef obj_ = nullptr;
  };
  
  #if USE_CYCLE_DETECTOR
  
  struct CycleDetectorRootset {
    // Orders roots.
    KStdVector<KRef> roots;
    // Pins a state of each root.
    KStdUnorderedMap<KRef, KStdVector<KRef>> rootToFields;
    // Holding roots and their fields to avoid GC-ing them.
    KStdVector<ScopedRefHolder> heldRefs;
  };
  
  class CycleDetector : private kotlin::Pinned, public KonanAllocatorAware {
   public:
    static void insertCandidateIfNeeded(KRef object) {
      if (canBeACandidate(object))
        instance().insertCandidate(object);
    }
  
    static void removeCandidateIfNeeded(KRef object) {
      if (canBeACandidate(object))
        instance().removeCandidate(object);
    }
  
    static CycleDetectorRootset collectRootset();
  
   private:
    CycleDetector() = default;
    ~CycleDetector() = default;
  
    static CycleDetector& instance() {
      // Only store a pointer to CycleDetector in .bss
      static CycleDetector* result = new CycleDetector();
      return *result;
    }
  
    static bool canBeACandidate(KRef object) {
      return kotlin::compiler::shouldContainDebugInfo() &&
          Kotlin_memoryLeakCheckerEnabled() &&
          (object->type_info()->flags_ & TF_LEAK_DETECTOR_CANDIDATE) != 0;
    }
  
    void insertCandidate(KRef candidate) {
      std::lock_guard guard(lock_);
  
      auto it = candidateList_.insert(candidateList_.begin(), candidate);
      candidateInList_.emplace(candidate, it);
    }
  
    void removeCandidate(KRef candidate) {
      std::lock_guard guard(lock_);
  
      auto it = candidateInList_.find(candidate);
      if (it == candidateInList_.end())
        return;
      candidateList_.erase(it->second);
      candidateInList_.erase(it);
    }
  
    kotlin::SpinLock<kotlin::MutexThreadStateHandling::kIgnore> lock_;
    using CandidateList = KStdList<KRef>;
    CandidateList candidateList_;
    KStdUnorderedMap<KRef, CandidateList::iterator> candidateInList_;
  };
  
  #endif  // USE_CYCLE_DETECTOR
  
  // TODO: can we pass this variable as an explicit argument?
  THREAD_LOCAL_VARIABLE MemoryState* memoryState = nullptr;
  THREAD_LOCAL_VARIABLE FrameOverlay* currentFrame = nullptr;
  
  #if COLLECT_STATISTIC
  class MemoryStatistic {
  public:
    // UpdateRef per-object type counters.
    uint64_t updateCounters[12][10];
    // Alloc per container type counters.
    uint64_t containerAllocs[2];
    // Free per container type counters.
    uint64_t objectAllocs[6];
    // Histogram of allocation size distribution.
    KStdUnorderedMap<int, int>* allocationHistogram;
    // Number of allocation cache hits.
    int allocCacheHit;
    // Number of allocation cache misses.
    int allocCacheMiss;
    // Number of regular reference increments.
    uint64_t addRefs;
    // Number of atomic reference increments.
    uint64_t atomicAddRefs;
    // Number of regular reference decrements.
    uint64_t releaseRefs;
    // Number of atomic reference decrements.
    uint64_t atomicReleaseRefs;
    // Number of potential cycle candidates.
    uint64_t releaseCyclicRefs;
  
    // Map of array index to human readable name.
    static constexpr const char* indexToName[] = {
      "local ", "stack ", "perm  ", "frozen", "shared", "null  " };
  
    void init() {
      memset(containerAllocs, 0, sizeof(containerAllocs));
      memset(objectAllocs, 0, sizeof(objectAllocs));
      memset(updateCounters, 0, sizeof(updateCounters));
      allocationHistogram = konanConstructInstance<KStdUnorderedMap<int, int>>();
      allocCacheHit = 0;
      allocCacheMiss = 0;
    }
  
    void deinit() {
      konanDestructInstance(allocationHistogram);
      allocationHistogram = nullptr;
    }
  
    void incAddRef(const ContainerHeader* header, bool atomic, int stack) {
      if (atomic) atomicAddRefs++; else addRefs++;
    }
  
    void incReleaseRef(const ContainerHeader* header, bool atomic, bool cyclic, int stack) {
     if (atomic) {
        atomicReleaseRefs++;
      } else {
        if (cyclic) releaseCyclicRefs++; else releaseRefs++;
      }
    }
  
    void incUpdateRef(const ObjHeader* objOld, const ObjHeader* objNew, int stack) {
      updateCounters[toIndex(objOld, stack)][toIndex(objNew, stack)]++;
    }
  
    void incAlloc(size_t size, const ContainerHeader* header) {
      containerAllocs[0]++;
      ++(*allocationHistogram)[size];
    }
  
    void incFree(const ContainerHeader* header) {
      containerAllocs[1]++;
    }
  
    void incAlloc(size_t size, const ObjHeader* header) {
      objectAllocs[toIndex(header, 0)]++;
    }
  
    static int toIndex(const ObjHeader* obj, int stack) {
      if (!isNullOrMarker(obj))
          return toIndex(containerFor(obj), stack);
      else
          return 4 + stack * 6;
    }
  
    static int toIndex(const ContainerHeader* header, int stack) {
      if (header == nullptr) return 2 + stack * 6; // permanent.
      switch (header->tag()) {
        case CONTAINER_TAG_LOCAL  : return 0 + stack * 6;
        case CONTAINER_TAG_STACK  : return 1 + stack * 6;
        case CONTAINER_TAG_FROZEN : return 3 + stack * 6;
        case CONTAINER_TAG_SHARED : return 4 + stack * 6;
  
      }
      RuntimeAssert(false, "unknown container type");
      return -1;
    }
  
    static double percents(uint64_t value, uint64_t all) {
     return all == 0 ? 0 : ((double)value / (double)all) * 100.0;
    }
  
    void printStatistic() {
      konan::consolePrintf("\nMemory manager statistic:\n\n");
      konan::consolePrintf("Container alloc: %lld, free: %lld\n",
                             containerAllocs[0], containerAllocs[1]);
      for (int i = 0; i < 6; i++) {
        // Only local, shared and frozen can be allocated.
        if (i == 0 || i == 3 || i == 4)
          konan::consolePrintf("Object %s alloc: %lld\n", indexToName[i], objectAllocs[i]);
      }
      konan::consolePrintf("\n");
  
      uint64_t allUpdateRefs = 0, heapUpdateRefs = 0, stackUpdateRefs = 0;
      for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 12; j++) {
           allUpdateRefs += updateCounters[i][j];
           if (i < 6 && j < 6)
             heapUpdateRefs += updateCounters[i][j];
           if (i >= 6 && j >= 6)
             stackUpdateRefs += updateCounters[i][j];
        }
      }
      konan::consolePrintf("Total updates: %lld, stack: %lld(%.2lf%%), heap: %lld(%.2lf%%)\n",
          allUpdateRefs,
          stackUpdateRefs, percents(stackUpdateRefs, allUpdateRefs),
          heapUpdateRefs, percents(heapUpdateRefs, allUpdateRefs));
      for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
          if (updateCounters[i][j] != 0)
              konan::consolePrintf("UpdateHeapRef[%s -> %s]: %lld (%.2lf%% of all, %.2lf%% of heap)\n",
                               indexToName[i], indexToName[j], updateCounters[i][j],
                               percents(updateCounters[i][j], allUpdateRefs),
                               percents(updateCounters[i][j], heapUpdateRefs));
        }
      }
      for (int i = 6; i < 12; i++) {
          for (int j = 6; j < 12; j++) {
              if (updateCounters[i][j] != 0)
                  konan::consolePrintf("UpdateStackRef[%s -> %s]: %lld (%.2lf%% of all, %.2lf%% of stack)\n",
                                   indexToName[i - 6], indexToName[j - 6],
                                   updateCounters[i][j],
                                   percents(updateCounters[i][j], allUpdateRefs),
                                   percents(updateCounters[i][j], stackUpdateRefs));
          }
      }
      konan::consolePrintf("\n");
  
      konan::consolePrintf("Allocation histogram:\n");
      KStdVector<int> keys(allocationHistogram->size());
      int index = 0;
      for (auto& it : *allocationHistogram) {
        keys[index++] = it.first;
      }
      std::sort(keys.begin(), keys.end());
      int perLine = 4;
      int count = 0;
      for (auto it : keys) {
        konan::consolePrintf(
            "%d bytes -> %d times  ", it, (*allocationHistogram)[it]);
        if (++count % perLine == (perLine - 1) || (count == keys.size()))
          konan::consolePrintf("\n");
      }
  
  
      uint64_t allAddRefs = addRefs + atomicAddRefs;
      uint64_t allReleases = releaseRefs + atomicReleaseRefs + releaseCyclicRefs;
      konan::consolePrintf("AddRefs:\t%lld/%lld (%.2lf%% of atomic)\n"
                           "Releases:\t%lld/%lld (%.2lf%% of atomic)\n"
                           "ReleaseRefs affecting cycle collector   : %lld (%.2lf%% of cyclic)\n",
                           addRefs, atomicAddRefs, percents(atomicAddRefs, allAddRefs),
                           releaseRefs, atomicReleaseRefs, percents(atomicReleaseRefs, allReleases),
                           releaseCyclicRefs, percents(releaseCyclicRefs, allReleases));
    }
  };
  
  constexpr const char* MemoryStatistic::indexToName[];
  
  #endif  // COLLECT_STATISTIC
  
  inline bool isPermanentOrFrozen(ContainerHeader* container) {
      return container == nullptr || container->frozen();
  }
  
  inline bool isShareable(ContainerHeader* container) {
      return container == nullptr || container->shareable();
  }
  
  void setContainerFor(ObjHeader* obj, ContainerHeader* container) {
    obj->meta_object()->container_ = container;
    obj->typeInfoOrMeta_ = setPointerBits(obj->typeInfoOrMeta_, OBJECT_TAG_NONTRIVIAL_CONTAINER);
  }
  
  #if !KONAN_NO_EXCEPTIONS
  class ExceptionObjHolderImpl : public ExceptionObjHolder {
  public:
      explicit ExceptionObjHolderImpl(ObjHeader* obj) noexcept { ::SetHeapRef(&obj_, obj); }
  
      ~ExceptionObjHolderImpl() override { ZeroHeapRef(&obj_); }
  
      ObjHeader* obj() noexcept { return obj_; }
  
  private:
      ObjHeader* obj_;
  };
  #endif
  
  }  // namespace
  
  ContainerHeader* containerFor(const ObjHeader* obj) {
    unsigned bits = getPointerBits(obj->typeInfoOrMeta_, OBJECT_TAG_MASK);
    if ((bits & (OBJECT_TAG_PERMANENT_CONTAINER | OBJECT_TAG_NONTRIVIAL_CONTAINER)) == 0)
      return reinterpret_cast<ContainerHeader*>(const_cast<ObjHeader*>(obj)) - 1;
    if ((bits & OBJECT_TAG_PERMANENT_CONTAINER) != 0)
      return nullptr;
    return (reinterpret_cast<MetaObjHeader*>(clearPointerBits(obj->typeInfoOrMeta_, OBJECT_TAG_MASK)))->container_;
  }
  
  ALWAYS_INLINE bool isPermanentOrFrozen(const ObjHeader* obj) {
      auto* container = containerFor(obj);
      return container == nullptr || container->frozen();
  }
  
  ALWAYS_INLINE bool isShareable(const ObjHeader* obj) {
      return containerFor(obj)->shareable();
  }
  
  ObjHeader* ObjHeader::GetWeakCounter() {
      return this->meta_object()->WeakReference.counter_;
  }
  
  ObjHeader* ObjHeader::GetOrSetWeakCounter(ObjHeader* counter) {
      UpdateHeapRefIfNull(&meta_object()->WeakReference.counter_, counter);
      return GetWeakCounter();
  }
  
  #if KONAN_OBJC_INTEROP
  
  void* ObjHeader::GetAssociatedObject() {
      if (!has_meta_object()) {
        return nullptr;
      }
      return this->meta_object()->associatedObject_;
  }
  
  void** ObjHeader::GetAssociatedObjectLocation() {
      return &this->meta_object()->associatedObject_;
  }
  
  void ObjHeader::SetAssociatedObject(void* obj) {
      this->meta_object()->associatedObject_ = obj;
  }
  
  #endif // KONAN_OBJC_INTEROP
  
  class ForeignRefManager {
   public:
    static ForeignRefManager* create() {
      ForeignRefManager* result = konanConstructInstance<ForeignRefManager>();
      result->addRef();
      return result;
    }
  
    void addRef() {
      atomicAdd(&refCount, 1);
    }
  
    void releaseRef() {
      if (atomicAdd(&this->refCount, -1) == 0) {
        // So the owning MemoryState has abandoned [this].
        // Leaving the queued work items would result in memory leak.
        // Luckily current thread has exclusive access to [this],
        // so it can process the queue pretending like it takes ownership of all its objects:
        this->processAbandoned();
  
        konanDestructInstance(this);
      }
    }
  
    bool tryReleaseRefOwned() {
      if (atomicAdd(&this->refCount, -1) == 0) {
        if (this->releaseList != nullptr) {
          // There are no more holders of [this] to process the enqueued work items in [releaseRef].
          // Revert the reference counter back and notify the caller to process and then retry:
          atomicAdd(&this->refCount, 1);
          return false;
        }
  
        konanDestructInstance(this);
      }
  
      return true;
    }
  
    void enqueueReleaseRef(ObjHeader* obj) {
      ListNode* newListNode = konanConstructInstance<ListNode>();
      newListNode->obj = obj;
      while (true) {
        ListNode* next = this->releaseList;
        newListNode->next = next;
        if (compareAndSet(&this->releaseList, next, newListNode)) break;
      }
    }
  
    template <typename func>
    void processEnqueuedReleaseRefsWith(func process) {
      if (releaseList == nullptr) return;
  
      ListNode* toProcess = nullptr;
  
      while (true) {
        toProcess = releaseList;
        if (compareAndSet<ListNode*>(&this->releaseList, toProcess, nullptr)) break;
      }
  
      while (toProcess != nullptr) {
        process(toProcess->obj);
        ListNode* next = toProcess->next;
        konanDestructInstance(toProcess);
        toProcess = next;
      }
    }
  
  private:
    int refCount;
  
    struct ListNode {
      ObjHeader* obj;
      ListNode* next;
    };
  
    ListNode* volatile releaseList;
  
    void processAbandoned() {
      if (this->releaseList != nullptr) {
        bool hadNoStateInitialized = (memoryState == nullptr);
  
        if (hadNoStateInitialized) {
          // Disregard request if all runtimes are no longer alive.
          if (atomicGet(&aliveMemoryStatesCount) == 0)
            return;
  
          memoryState = InitMemory(false); // Required by ReleaseHeapRef.
        }
  
        processEnqueuedReleaseRefsWith([](ObjHeader* obj) {
          ReleaseHeapRef(obj);
        });
  
        if (hadNoStateInitialized) {
          // Discard the memory state.
          DeinitMemory(memoryState, false);
        }
      }
    }
  };
  
  namespace {
  
  class ThreadLocalStorage {
  public:
      using Key = void**;
  
      void Init() noexcept { map_ = konanConstructInstance<Map>(); }
  
      void Deinit() noexcept {
          RuntimeAssert(map_->size() == 0, "Must be already cleared");
          konanDestructInstance(map_);
      }
  
      void Add(Key key, int size) noexcept {
          RuntimeAssert(storage_ == nullptr, "Storage must not be committed");
          auto it = map_->find(key);
          if (it != map_->end()) {
              RuntimeAssert(it->second.size == size, "Attempt to add TLS record with the same key and different size");
              return;
          }
          map_->emplace(key, Entry{size_, size});
          size_ += size;
      }
  
      void Commit() noexcept {
          RuntimeAssert(storage_ == nullptr, "Cannot commit storage twice");
          storage_ = reinterpret_cast<KRef*>(konanAllocMemory(size_ * sizeof(KRef)));
      }
  
      void Clear() noexcept {
          RuntimeAssert(storage_ != nullptr, "Storage must be committed");
          for (int i = 0; i < size_; ++i) {
              UpdateHeapRef(storage_ + i, nullptr);
          }
          konanFreeMemory(storage_);
          map_->clear();
      }
  
      KRef* Lookup(Key key, int index) noexcept {
          RuntimeAssert(storage_ != nullptr, "Storage must be committed");
          // In many cases there is only one module, so this is one element cache.
          if (lastKey_ == key) {
              return storage_ + lastOffset_ + index;
          }
          auto it = map_->find(key);
          RuntimeAssert(it != map_->end(), "Must be there");
          auto entry = it->second;
          RuntimeAssert(index < entry.size, "Out of bounds in TLS access");
          lastKey_ = key;
          lastOffset_ = entry.offset;
          return storage_ + entry.offset + index;
      }
  
  private:
      struct Entry {
          int offset;
          int size;
      };
  
      using Map = KStdUnorderedMap<Key, Entry>;
  
      Map* map_ = nullptr;
      KRef* storage_ = nullptr;
      int size_ = 0;
      int lastOffset_ = 0;
      Key lastKey_ = nullptr;
  };
  
  } // namespace
  
  struct MemoryState {
  #if TRACE_MEMORY
    // Set of all containers.
    ContainerHeaderSet* containers;
  #endif
  
    ThreadLocalStorage tls;
  
  #if USE_GC
    // Finalizer queue - linked list of containers scheduled for finalization.
    ContainerHeader* finalizerQueue;
    int finalizerQueueSize;
    int finalizerQueueSuspendCount;
    /*
     * Typical scenario for GC is as following:
     * we have 90% of objects with refcount = 0 which will be deleted during
     * the first phase of the algorithm.
     * We could mark them with a bit in order to tell the next two phases to skip them
     * and thus requiring only one list, but the downside is that both of the
     * next phases would iterate over the whole list of objects instead of only 10%.
     */
    ContainerHeaderList* toFree; // List of all cycle candidates.
    ContainerHeaderList* roots; // Real candidates excluding those with refcount = 0.
    // How many GC suspend requests happened.
    int gcSuspendCount;
    // How many candidate elements in toRelease shall trigger collection.
    size_t gcThreshold;
    // How many candidate elements in toFree shall trigger cycle collection.
    uint64_t gcCollectCyclesThreshold;
    // If collection is in progress.
    bool gcInProgress;
    // Objects to be released.
    ContainerHeaderList* toRelease;
  
    ForeignRefManager* foreignRefManager;
  
    bool gcErgonomics;
    uint64_t lastGcTimestamp;
    uint64_t lastCyclicGcTimestamp;
    uint32_t gcEpoque;
  
    uint64_t allocSinceLastGc;
    uint64_t allocSinceLastGcThreshold;
  #endif // USE_GC
  
    // A stack of initializing singletons.
    KStdVector<std::pair<ObjHeader**, ObjHeader*>> initializingSingletons;
  
    bool isMainThread = false;
  
  #if COLLECT_STATISTIC
    #define CONTAINER_ALLOC_STAT(state, size, container) state->statistic.incAlloc(size, container);
    #define CONTAINER_DESTROY_STAT(state, container) \
      state->statistic.incFree(container);
    #define OBJECT_ALLOC_STAT(state, size, object) \
      state->statistic.incAlloc(size, object); \
      state->statistic.incAddRef(containerFor(object), 0, 0);
    #define UPDATE_REF_STAT(state, oldRef, newRef, slot, stack) \
      state->statistic.incUpdateRef(oldRef, newRef, stack);
    #define UPDATE_ADDREF_STAT(state, obj, atomic, stack) \
        state->statistic.incAddRef(obj, atomic, stack);
    #define UPDATE_RELEASEREF_STAT(state, obj, atomic, cyclic, stack) \
          state->statistic.incReleaseRef(obj, atomic, cyclic, stack);
    #define INIT_STAT(state) \
      state->statistic.init();
    #define DEINIT_STAT(state) \
      state->statistic.deinit();
    #define PRINT_STAT(state) \
      state->statistic.printStatistic();
    MemoryStatistic statistic;
  #else
    #define CONTAINER_ALLOC_STAT(state, size, container)
    #define CONTAINER_DESTROY_STAT(state, container)
    #define OBJECT_ALLOC_STAT(state, size, object)
    #define UPDATE_REF_STAT(state, oldRef, newRef, slot, stack)
    #define UPDATE_ADDREF_STAT(state, obj, atomic, stack)
    #define UPDATE_RELEASEREF_STAT(state, obj, atomic, cyclic, stack)
    #define INIT_STAT(state)
    #define DEINIT_STAT(state)
    #define PRINT_STAT(state)
  #endif // COLLECT_STATISTIC
  };
  
  namespace {
  
  #if TRACE_MEMORY
  #define INIT_TRACE(state) \
    memoryState->containers = konanConstructInstance<ContainerHeaderSet>();
  #define DEINIT_TRACE(state) \
     konanDestructInstance(memoryState->containers); \
     memoryState->containers = nullptr;
  #else
  #define INIT_TRACE(state)
  #define DEINIT_TRACE(state)
  #endif
  #define CONTAINER_ALLOC_TRACE(state, size, container) \
    MEMORY_LOG("Container alloc %d at %p\n", size, container)
  #define CONTAINER_DESTROY_TRACE(state, container) \
    MEMORY_LOG("Container destroy %p\n", container)
  #define OBJECT_ALLOC_TRACE(state, size, object) \
    MEMORY_LOG("Object alloc %d at %p\n", size, object)
  #define UPDATE_REF_TRACE(state, oldRef, newRef, slot, stack) \
    MEMORY_LOG("UpdateRef %s*%p: %p -> %p\n", stack ? "stack " : "heap ", slot, oldRef, newRef)
  
  // Events macro definitions.
  // Called on worker's memory init.
  #define INIT_EVENT(state) \
    INIT_STAT(state) \
    INIT_TRACE(state)
  // Called on worker's memory deinit.
  #define DEINIT_EVENT(state) \
    DEINIT_STAT(state)
  // Called on container allocation.
  #define CONTAINER_ALLOC_EVENT(state, size, container) \
    CONTAINER_ALLOC_STAT(state, size, container) \
    CONTAINER_ALLOC_TRACE(state, size, container)
  // Called on container destroy (memory is released to allocator).
  #define CONTAINER_DESTROY_EVENT(state, container) \
    CONTAINER_DESTROY_STAT(state, container) \
    CONTAINER_DESTROY_TRACE(state, container)
  // Object was just allocated.
  #define OBJECT_ALLOC_EVENT(state, size, object) \
    OBJECT_ALLOC_STAT(state, size, object) \
    OBJECT_ALLOC_TRACE(state, size, object)
  // Object is freed.
  #define OBJECT_FREE_EVENT(state, size, object)  \
    OBJECT_FREE_STAT(state, size, object) \
    OBJECT_FREE_TRACE(state, object)
  // Reference in memory is being updated.
  #define UPDATE_REF_EVENT(state, oldRef, newRef, slot, stack) \
    UPDATE_REF_STAT(state, oldRef, newRef, slot, stack) \
    UPDATE_REF_TRACE(state, oldRef, newRef, slot, stack)
  // Infomation shall be printed as worker is exiting.
  #define PRINT_EVENT(state) \
    PRINT_STAT(state)
  
  // Forward declarations.
  void freeContainer(ContainerHeader* header) NO_INLINE;
  #if USE_GC
  void garbageCollect(MemoryState* state, bool force) NO_INLINE;
  void rememberNewContainer(ContainerHeader* container);
  #endif  // USE_GC
  
  // Class representing arbitrary placement container.
  class Container {
   public:
    ContainerHeader* header() const { return header_; }
   protected:
    // Data where everything is being stored.
    ContainerHeader* header_;
  
    void SetHeader(ObjHeader* obj, const TypeInfo* type_info) {
      obj->typeInfoOrMeta_ = const_cast<TypeInfo*>(type_info);
      // Take into account typeInfo's immutability for ARC strategy.
      if ((type_info->flags_ & TF_IMMUTABLE) != 0)
        header_->refCount_ |= CONTAINER_TAG_FROZEN;
      if ((type_info->flags_ & TF_ACYCLIC) != 0)
        header_->setColorEvenIfGreen(CONTAINER_TAG_GC_GREEN);
    }
  };
  
  // Container for a single object.
  class ObjectContainer : public Container {
   public:
    // Single instance.
    explicit ObjectContainer(MemoryState* state, const TypeInfo* type_info) {
      Init(state, type_info);
    }
  
    // Object container shalln't have any dtor, as it's being freed by
    // ::Release().
  
    ObjHeader* GetPlace() const {
      return reinterpret_cast<ObjHeader*>(header_ + 1);
    }
  
   private:
    void Init(MemoryState* state, const TypeInfo* type_info);
  };
  
  
  class ArrayContainer : public Container {
   public:
    ArrayContainer(MemoryState* state, const TypeInfo* type_info, uint32_t elements) {
      Init(state, type_info, elements);
    }
  
    // Array container shalln't have any dtor, as it's being freed by ::Release().
  
    ArrayHeader* GetPlace() const {
      return reinterpret_cast<ArrayHeader*>(header_ + 1);
    }
  
   private:
    void Init(MemoryState* state, const TypeInfo* type_info, uint32_t elements);
  };
  
  // Class representing arena-style placement container.
  // Container is used for reference counting, and it is assumed that objects
  // with related placement will share container. Only
  // whole container can be freed, individual objects are not taken into account.
  class ArenaContainer;
  
  struct ContainerChunk {
    ContainerChunk* next;
    ArenaContainer* arena;
    // Then we have ContainerHeader here.
    ContainerHeader* asHeader() {
      return reinterpret_cast<ContainerHeader*>(this + 1);
    }
  };
  
  class ArenaContainer {
   public:
    void Init();
    void Deinit();
  
    // Place individual object in this container.
    ObjHeader* PlaceObject(const TypeInfo* type_info);
  
    // Places an array of certain type in this container. Note that array_type_info
    // is type info for an array, not for an individual element. Also note that exactly
    // same operation could be used to place strings.
    ArrayHeader* PlaceArray(const TypeInfo* array_type_info, container_size_t count);
  
    ObjHeader** getSlot();
  
   private:
    void* place(container_size_t size);
  
    bool allocContainer(container_size_t minSize);
  
    void setHeader(ObjHeader* obj, const TypeInfo* typeInfo) {
      obj->typeInfoOrMeta_ = const_cast<TypeInfo*>(typeInfo);
      setContainerFor(obj, currentChunk_->asHeader());
      // Here we do not take into account typeInfo's immutability for ARC strategy, as there's no ARC.
    }
  
    ContainerChunk* currentChunk_;
    uint8_t* current_;
    uint8_t* end_;
    ArrayHeader* slots_;
    uint32_t slotsCount_;
  };
  
  constexpr int kFrameOverlaySlots = sizeof(FrameOverlay) / sizeof(ObjHeader**);
  
  inline bool isFreeable(const ContainerHeader* header) {
    return header != nullptr && header->tag() != CONTAINER_TAG_STACK;
  }
  
  inline bool isArena(const ContainerHeader* header) {
    return header != nullptr && header->stack();
  }
  
  inline bool isAggregatingFrozenContainer(const ContainerHeader* header) {
    return header != nullptr && header->frozen() && header->objectCount() > 1;
  }
  
  inline bool isMarkedAsRemoved(ContainerHeader* container) {
    return (reinterpret_cast<uintptr_t>(container) & 1) != 0;
  }
  
  inline ContainerHeader* markAsRemoved(ContainerHeader* container) {
    return reinterpret_cast<ContainerHeader*>(reinterpret_cast<uintptr_t>(container) | 1);
  }
  
  inline ContainerHeader* clearRemoved(ContainerHeader* container) {
    return reinterpret_cast<ContainerHeader*>(
      reinterpret_cast<uintptr_t>(container) & ~static_cast<uintptr_t>(1));
  }
  
  inline container_size_t alignUp(container_size_t size, int alignment) {
    return (size + alignment - 1) & ~(alignment - 1);
  }
  
  inline ContainerHeader* realShareableContainer(ContainerHeader* container) {
    RuntimeAssert(container->shareable(), "Only makes sense on shareable objects");
    return containerFor(reinterpret_cast<ObjHeader*>(container + 1));
  }
  
  inline uint32_t arrayObjectSize(const TypeInfo* typeInfo, uint32_t count) {
    // Note: array body is aligned, but for size computation it is enough to align the sum.
    static_assert(kObjectAlignment % alignof(KLong) == 0, "");
    static_assert(kObjectAlignment % alignof(KDouble) == 0, "");
    return alignUp(sizeof(ArrayHeader) - typeInfo->instanceSize_ * count, kObjectAlignment);
  }
  
  inline uint32_t arrayObjectSize(const ArrayHeader* obj) {
    return arrayObjectSize(obj->type_info(), obj->count_);
  }
  
  // TODO: shall we do padding for alignment?
  inline container_size_t objectSize(const ObjHeader* obj) {
    const TypeInfo* type_info = obj->type_info();
    container_size_t size = (type_info->instanceSize_ < 0 ?
        // An array.
        arrayObjectSize(obj->array())
        :
        type_info->instanceSize_);
    return alignUp(size, kObjectAlignment);
  }
  
  template <typename func>
  inline void traverseContainerObjects(ContainerHeader* container, func process) {
    RuntimeAssert(!isAggregatingFrozenContainer(container), "Must not be called on such containers");
    ObjHeader* obj = reinterpret_cast<ObjHeader*>(container + 1);
    for (uint32_t i = 0; i < container->objectCount(); ++i) {
      process(obj);
      obj = reinterpret_cast<ObjHeader*>(
        reinterpret_cast<uintptr_t>(obj) + objectSize(obj));
    }
  }
  
  template <typename func>
  inline void traverseContainerObjectFields(ContainerHeader* container, func process) {
    traverseContainerObjects(container, [process](ObjHeader* obj) {
        kotlin::traverseObjectFields(obj, process);
    });
  }
  
  template <typename func>
  inline void traverseContainerReferredObjects(ContainerHeader* container, func process) {
    traverseContainerObjectFields(container, [process](ObjHeader** location) {
      ObjHeader* ref = *location;
      if (ref != nullptr) process(ref);
    });
  }
  
  inline FrameOverlay* asFrameOverlay(ObjHeader** slot) {
    return reinterpret_cast<FrameOverlay*>(slot);
  }
  
  inline void lock(KInt* spinlock) {
    while (compareAndSwap(spinlock, 0, 1) != 0) {}
  }
  
  inline void unlock(KInt* spinlock) {
    RuntimeCheck(compareAndSwap(spinlock, 1, 0) == 1, "Must succeed");
  }
  
  inline bool canFreeze(ContainerHeader* container) {
    if (IsStrictMemoryModel())
      // In strict memory model we ignore permanent, frozen and shared object when recursively freezing.
      return container != nullptr && !container->shareable();
    else
      // In relaxed memory model we ignore permanent and frozen object when recursively freezing.
      return container != nullptr && !container->frozen();
  }
  
  inline bool isFreezableAtomic(ObjHeader* obj) {
    return obj->type_info() == theFreezableAtomicReferenceTypeInfo;
  }
  
  inline bool isFreezableAtomic(ContainerHeader* container) {
    RuntimeAssert(!isAggregatingFrozenContainer(container), "Must be single object");
    ObjHeader* obj = reinterpret_cast<ObjHeader*>(container + 1);
    return isFreezableAtomic(obj);
  }
  
  ContainerHeader* allocContainer(MemoryState* state, size_t size) {
   ContainerHeader* result = nullptr;
  #if USE_GC
    // We recycle elements of finalizer queue for new allocations, to avoid trashing memory manager.
    ContainerHeader* container = state != nullptr ? state->finalizerQueue : nullptr;
    ContainerHeader* previous = nullptr;
    while (container != nullptr) {
      // TODO: shall it be == instead?
      if (container->hasContainerSize() &&
          container->containerSize() >= size && container->containerSize() <= size + 16) {
        MEMORY_LOG("recycle %p for request %d\n", container, size)
        result = container;
        if (previous == nullptr)
          state->finalizerQueue = container->nextLink();
        else
          previous->setNextLink(container->nextLink());
        state->finalizerQueueSize--;
        memset(container, 0, size);
        break;
      }
      previous = container;
      container = container->nextLink();
    }
  #endif
    if (result == nullptr) {
  #if USE_GC
      if (state != nullptr)
          state->allocSinceLastGc += size;
  #endif
      result = konanConstructSizedInstance<ContainerHeader>(alignUp(size, kObjectAlignment));
      atomicAdd(&allocCount, 1);
    }
    if (state != nullptr) {
      CONTAINER_ALLOC_EVENT(state, size, result);
  #if TRACE_MEMORY
      state->containers->insert(result);
  #endif
    }
    return result;
  }
  
  ContainerHeader* allocAggregatingFrozenContainer(KStdVector<ContainerHeader*>& containers) {
    auto componentSize = containers.size();
    auto* superContainer = allocContainer(memoryState, sizeof(ContainerHeader) + sizeof(void*) * componentSize);
    auto* place = reinterpret_cast<ContainerHeader**>(superContainer + 1);
    for (auto* container : containers) {
      *place++ = container;
      // Set link to the new container.
      auto* obj = reinterpret_cast<ObjHeader*>(container + 1);
      setContainerFor(obj, superContainer);
      MEMORY_LOG("Set fictitious frozen container for %p: %p\n", obj, superContainer);
    }
    superContainer->setObjectCount(componentSize);
    superContainer->freeze();
    return superContainer;
  }
  
  
  #if USE_GC
  
  void processFinalizerQueue(MemoryState* state) {
    // TODO: reuse elements of finalizer queue for new allocations.
    while (state->finalizerQueue != nullptr) {
      auto* container = state->finalizerQueue;
      state->finalizerQueue = container->nextLink();
      state->finalizerQueueSize--;
  #if TRACE_MEMORY
      state->containers->erase(container);
  #endif
      CONTAINER_DESTROY_EVENT(state, container)
      konanFreeMemory(container);
      atomicAdd(&allocCount, -1);
    }
    RuntimeAssert(state->finalizerQueueSize == 0, "Queue must be empty here");
  }
  
  bool hasExternalRefs(ContainerHeader* start, ContainerHeaderSet* visited) {
    ContainerHeaderDeque toVisit;
    toVisit.push_back(start);
    while (!toVisit.empty()) {
      auto* container = toVisit.front();
      toVisit.pop_front();
      visited->insert(container);
      if (container->refCount() > 0) {
        MEMORY_LOG("container %p with rc %d blocks transfer\n", container, container->refCount())
        return true;
      }
      traverseContainerReferredObjects(container, [&toVisit, visited](ObjHeader* ref) {
          auto* child = containerFor(ref);
          if (!isShareable(child) && (visited->count(child) == 0)) {
             toVisit.push_front(child);
          }
       });
    }
    return false;
  }
  
  #endif  // USE_GC
  
  void scheduleDestroyContainer(MemoryState* state, ContainerHeader* container) {
  #if USE_GC
    RuntimeAssert(container != nullptr, "Cannot destroy null container");
    container->setNextLink(state->finalizerQueue);
    state->finalizerQueue = container;
    state->finalizerQueueSize++;
    // We cannot clean finalizer queue while in GC.
    if (!state->gcInProgress && state->finalizerQueueSuspendCount == 0 &&
        state->finalizerQueueSize >= kFinalizerQueueThreshold) {
      processFinalizerQueue(state);
    }
  #else
    konanFreeMemory(container);
    atomicAdd(&allocCount, -1);
    CONTAINER_DESTROY_EVENT(state, container);
  #endif
  }
  
  void freeAggregatingFrozenContainer(ContainerHeader* container) {
    auto* state = memoryState;
    RuntimeAssert(isAggregatingFrozenContainer(container), "expected fictitious frozen container");
    MEMORY_LOG("%p is fictitious frozen container\n", container);
    RuntimeAssert(!container->buffered(), "frozen objects must not participate in GC");
  #if USE_GC
    // Forbid finalizerQueue handling.
    ++state->finalizerQueueSuspendCount;
  #endif
    // Special container for frozen objects.
    ContainerHeader** subContainer = reinterpret_cast<ContainerHeader**>(container + 1);
    MEMORY_LOG("Total subcontainers = %d\n", container->objectCount());
    for (uint32_t i = 0; i < container->objectCount(); ++i) {
      MEMORY_LOG("Freeing subcontainer %p\n", *subContainer);
      freeContainer(*subContainer++);
    }
  #if USE_GC
    --state->finalizerQueueSuspendCount;
  #endif
    scheduleDestroyContainer(state, container);
    MEMORY_LOG("Freeing subcontainers done\n");
  }
  
  // This is called from 2 places where it's unconditionally called,
  // so better be inlined.
  ALWAYS_INLINE void runDeallocationHooks(ContainerHeader* container) {
    ObjHeader* obj = reinterpret_cast<ObjHeader*>(container + 1);
    for (uint32_t index = 0; index < container->objectCount(); index++) {
  #if USE_CYCLIC_GC
      if ((type_info->flags_ & TF_LEAK_DETECTOR_CANDIDATE) != 0) {
        cyclicRemoveAtomicRoot(obj);
      }
  #endif  // USE_CYCLIC_GC
  #if USE_CYCLE_DETECTOR
      CycleDetector::removeCandidateIfNeeded(obj);
  #endif  // USE_CYCLE_DETECTOR
      kotlin::RunFinalizers(obj);
      obj = reinterpret_cast<ObjHeader*>(reinterpret_cast<uintptr_t>(obj) + objectSize(obj));
    }
  }
  
  void freeContainer(ContainerHeader* container) {
    RuntimeAssert(container != nullptr, "this kind of container shalln't be freed");
  
    if (isAggregatingFrozenContainer(container)) {
      freeAggregatingFrozenContainer(container);
      return;
    }
  
    runDeallocationHooks(container);
  
    // Now let's clean all object's fields in this container.
    traverseContainerObjectFields(container, [](ObjHeader** location) {
        ZeroHeapRef(location);
    });
  
    // And release underlying memory.
    if (isFreeable(container)) {
      container->setColorEvenIfGreen(CONTAINER_TAG_GC_BLACK);
      if (!container->buffered())
        scheduleDestroyContainer(memoryState, container);
    }
  }
  
  /**
    * Do DFS cycle detection with three colors:
    *  - 'marked' bit as BLACK marker (object and its descendants processed)
    *  - 'seen' bit as GRAY marker (object is being processed)
    *  - not 'marked' and not 'seen' as WHITE marker (object is unprocessed)
    * When we see GREY during DFS, it means we see cycle.
    */
  void depthFirstTraversal(ContainerHeader* start, bool* hasCycles,
                           KRef* firstBlocker, KStdVector<ContainerHeader*>* order) {
    ContainerHeaderDeque toVisit;
    toVisit.push_back(start);
    start->setSeen();
  
    while (!toVisit.empty()) {
      auto* container = toVisit.front();
      toVisit.pop_front();
      if (isMarkedAsRemoved(container)) {
        container = clearRemoved(container);
        // Mark BLACK.
        container->resetSeen();
        container->mark();
        order->push_back(container);
        continue;
      }
      toVisit.push_front(markAsRemoved(container));
      traverseContainerReferredObjects(container, [container, hasCycles, firstBlocker, &toVisit](ObjHeader* obj) {
        if (*firstBlocker != nullptr)
          return;
        if (obj->has_meta_object() && ((obj->meta_object()->flags_ & MF_NEVER_FROZEN) != 0)) {
            *firstBlocker = obj;
            return;
        }
        ContainerHeader* objContainer = containerFor(obj);
        if (canFreeze(objContainer)) {
          // Marked GREY, there's cycle.
          if (objContainer->seen()) *hasCycles = true;
  
          // Go deeper if WHITE.
          if (!objContainer->seen() && !objContainer->marked()) {
            // Mark GRAY.
            objContainer->setSeen();
            // Here we do rather interesting trick: when doing DFS we postpone processing references going from
            // FreezableAtomic, so that in 'order' referred value will be seen as not actually belonging
            // to the same SCC (unless there are other edges not going through FreezableAtomic reaching the same value).
            if (isFreezableAtomic(container)) {
              toVisit.push_back(objContainer);
            } else {
              toVisit.push_front(objContainer);
            }
          }
        }
      });
    }
  }
  
  void traverseStronglyConnectedComponent(ContainerHeader* start,
                                          KStdUnorderedMap<ContainerHeader*,
                                              KStdVector<ContainerHeader*>> const* reversedEdges,
                                          KStdVector<ContainerHeader*>* component) {
    ContainerHeaderDeque toVisit;
    toVisit.push_back(start);
    start->mark();
  
    while (!toVisit.empty()) {
      auto* container = toVisit.front();
      toVisit.pop_front();
      component->push_back(container);
      auto it = reversedEdges->find(container);
      RuntimeAssert(it != reversedEdges->end(), "unknown node during condensation building");
      for (auto* nextContainer : it->second) {
        if (!nextContainer->marked()) {
            nextContainer->mark();
            toVisit.push_front(nextContainer);
        }
      }
    }
  }
  
  template <bool Atomic>
  inline bool tryIncrementRC(ContainerHeader* container) {
    return container->tryIncRefCount<Atomic>();
  }
  
  #if !USE_GC
  
  template <bool Atomic>
  inline void incrementRC(ContainerHeader* container) {
    container->incRefCount<Atomic>();
  }
  
  template <bool Atomic, bool UseCycleCollector>
  inline void decrementRC(ContainerHeader* container) {
    if (container->decRefCount<Atomic>() == 0) {
      freeContainer(container);
    }
  }
  
  inline void decrementRC(ContainerHeader* container) {
    if (isShareable(container))
      decrementRC<true, false>(container);
    else
      decrementRC<false, false>(container);
  }
  
  template <bool CanCollect>
  inline void enqueueDecrementRC(ContainerHeader* container) {
    RuntimeCheck(false, "Not yet implemeneted");
  }
  
  #else // USE_GC
  
  template <bool Atomic>
  inline void incrementRC(ContainerHeader* container) {
    container->incRefCount<Atomic>();
  }
  
  template <bool Atomic, bool UseCycleCollector>
  inline void decrementRC(ContainerHeader* container) {
    // TODO: enable me, once account for inner references in frozen objects correctly.
    // RuntimeAssert(container->refCount() > 0, "Must be positive");
    if (container->decRefCount<Atomic>() == 0) {
      freeContainer(container);
    } else if (UseCycleCollector) { // Possible root.
      RuntimeAssert(container->refCount() > 0, "Must be positive");
      RuntimeAssert(!Atomic && !container->shareable(), "Cycle collector shalln't be used with shared objects yet");
      RuntimeAssert(container->objectCount() == 1, "cycle collector shall only work with single object containers");
      // We do not use cycle collector for frozen objects, as we already detected
      // possible cycles during freezing.
      // Also do not use cycle collector for provable acyclic objects.
      int color = container->color();
      if (color != CONTAINER_TAG_GC_PURPLE && color != CONTAINER_TAG_GC_GREEN) {
        container->setColorAssertIfGreen(CONTAINER_TAG_GC_PURPLE);
        if (!container->buffered()) {
          auto* state = memoryState;
          container->setBuffered();
          if (state->toFree != nullptr) {
            state->toFree->push_back(container);
            MEMORY_LOG("toFree is now %lu\n", state->toFree->size())
            if (state->gcSuspendCount == 0 && state->toRelease->size() >= state->gcThreshold) {
              GC_LOG("Calling GC from DecrementRC: %d\n", state->toRelease->size())
              garbageCollect(state, false);
            }
          }
        }
      }
    }
  }
  
  inline void decrementRC(ContainerHeader* container) {
    auto* state = memoryState;
    RuntimeAssert(!IsStrictMemoryModel() || state->gcInProgress, "Must only be called during GC");
    // TODO: enable me, once account for inner references in frozen objects correctly.
    // RuntimeAssert(container->refCount() > 0, "Must be positive");
    bool useCycleCollector = container->local();
    if (container->decRefCount() == 0) {
      freeContainer(container);
    } else if (useCycleCollector && state->toFree != nullptr) {
        RuntimeAssert(IsStrictMemoryModel(), "No cycle collector in relaxed mode yet");
        RuntimeAssert(container->refCount() > 0, "Must be positive");
        RuntimeAssert(!container->shareable(), "Cycle collector shalln't be used with shared objects yet");
        RuntimeAssert(container->objectCount() == 1, "cycle collector shall only work with single object containers");
        // We do not use cycle collector for frozen objects, as we already detected
        // possible cycles during freezing.
        // Also do not use cycle collector for provable acyclic objects.
        int color = container->color();
        if (color != CONTAINER_TAG_GC_PURPLE && color != CONTAINER_TAG_GC_GREEN) {
          container->setColorAssertIfGreen(CONTAINER_TAG_GC_PURPLE);
          if (!container->buffered()) {
            container->setBuffered();
            state->toFree->push_back(container);
          }
        }
    }
  }
  
  template <bool CanCollect>
  inline void enqueueDecrementRC(ContainerHeader* container) {
    auto* state = memoryState;
    if (CanCollect) {
      if (state->toRelease->size() >= state->gcThreshold && state->gcSuspendCount == 0) {
        GC_LOG("Calling GC from EnqueueDecrementRC: %zu\n", state->toRelease->size())
        garbageCollect(state, false);
      }
    }
    state->toRelease->push_back(container);
  }
  
  inline void initGcThreshold(MemoryState* state, uint32_t gcThreshold) {
    state->gcThreshold = gcThreshold;
    state->toRelease->reserve(gcThreshold);
  }
  
  inline void initGcCollectCyclesThreshold(MemoryState* state, uint64_t gcCollectCyclesThreshold) {
    state->gcCollectCyclesThreshold = gcCollectCyclesThreshold;
    state->toFree->reserve(gcCollectCyclesThreshold);
  }
  
  inline void increaseGcThreshold(MemoryState* state) {
    auto newThreshold = state->gcThreshold * 3 / 2 + 1;
    if (newThreshold <= kMaxErgonomicThreshold) {
      initGcThreshold(state, newThreshold);
    }
  }
  
  inline void increaseGcCollectCyclesThreshold(MemoryState* state) {
    auto newThreshold = state->gcCollectCyclesThreshold * 2;
    if (newThreshold <= kMaxErgonomicToFreeSizeThreshold) {
      initGcCollectCyclesThreshold(state, newThreshold);
    }
  }
  
  #endif // USE_GC
  
  #if TRACE_MEMORY && USE_GC
  
  const char* colorNames[] = {"BLACK", "GRAY", "WHITE", "PURPLE", "GREEN", "ORANGE", "RED"};
  
  void dumpObject(ObjHeader* ref, int indent) {
    for (int i = 0; i < indent; i++) MEMORY_LOG(" ");
    auto* typeInfo = ref->type_info();
    auto* packageName =
      typeInfo->packageName_ != nullptr ? CreateCStringFromString(typeInfo->packageName_) : nullptr;
    auto* relativeName =
      typeInfo->relativeName_ != nullptr ? CreateCStringFromString(typeInfo->relativeName_) : nullptr;
    MEMORY_LOG("%p %s.%s\n", ref,
      packageName ? packageName : "<unknown>", relativeName ? relativeName : "<unknown>");
    if (packageName) konan::free(packageName);
    if (relativeName) konan::free(relativeName);
  }
  
  void dumpContainerContent(ContainerHeader* container) {
    if (container->refCount() < 0) {
      MEMORY_LOG("%p has negative RC %d, likely a memory bug\n", container, container->refCount())
      return;
    }
    if (isAggregatingFrozenContainer(container)) {
      MEMORY_LOG("%s aggregating container %p with %d objects rc=%d\n",
                 colorNames[container->color()], container, container->objectCount(), container->refCount());
      ContainerHeader** subContainer = reinterpret_cast<ContainerHeader**>(container + 1);
      for (int i = 0; i < container->objectCount(); ++i) {
        ContainerHeader* sub = *subContainer++;
        MEMORY_LOG("    container %p\n ", sub);
        dumpContainerContent(sub);
      }
    } else {
      MEMORY_LOG("%s regular %s%scontainer %p with %d objects rc=%d\n",
                 colorNames[container->color()],
                 container->frozen() ? "frozen " : "",
                 container->stack() ? "stack " : "",
                 container, container->objectCount(),
                 container->refCount());
      ObjHeader* obj = reinterpret_cast<ObjHeader*>(container + 1);
      dumpObject(obj, 4);
    }
  }
  
  void dumpWorker(const char* prefix, ContainerHeader* header, ContainerHeaderSet* seen) {
    dumpContainerContent(header);
    seen->insert(header);
    if (!isAggregatingFrozenContainer(header)) {
      traverseContainerReferredObjects(header, [prefix, seen](ObjHeader* ref) {
        auto* child = containerFor(ref);
        RuntimeAssert(!isArena(child), "A reference to local object is encountered");
        if (child != nullptr && (seen->count(child) == 0)) {
          dumpWorker(prefix, child, seen);
        }
      });
    }
  }
  
  void dumpReachable(const char* prefix, const ContainerHeaderSet* roots) {
    ContainerHeaderSet seen;
    for (auto* container : *roots) {
      dumpWorker(prefix, container, &seen);
    }
  }
  
  #endif
  
  #if USE_GC
  
  void markRoots(MemoryState*);
  void scanRoots(MemoryState*);
  void collectRoots(MemoryState*);
  void scan(ContainerHeader* container);
  
  template <bool useColor>
  void markGray(ContainerHeader* start) {
    ContainerHeaderDeque toVisit;
    toVisit.push_front(start);
  
    while (!toVisit.empty()) {
      auto* container = toVisit.front();
      MEMORY_LOG("MarkGray visit %p [%s]\n", container, colorNames[container->color()]);
      toVisit.pop_front();
      if (useColor) {
        int color = container->color();
        if (color == CONTAINER_TAG_GC_GRAY) continue;
        // If see an acyclic object not being garbage - ignore it. We must properly traverse garbage, although.
        if (color == CONTAINER_TAG_GC_GREEN && container->refCount() != 0) {
          continue;
        }
        // Only garbage green object could be recolored here.
        container->setColorEvenIfGreen(CONTAINER_TAG_GC_GRAY);
      } else {
        if (container->marked()) continue;
        container->mark();
      }
  
      traverseContainerReferredObjects(container, [&toVisit](ObjHeader* ref) {
        auto* childContainer = containerFor(ref);
        RuntimeAssert(!isArena(childContainer), "A reference to local object is encountered");
        if (!isShareable(childContainer)) {
          childContainer->decRefCount<false>();
          toVisit.push_front(childContainer);
        }
      });
    }
  }
  
  template <bool useColor>
  void scanBlack(ContainerHeader* start) {
    ContainerHeaderDeque toVisit;
    toVisit.push_front(start);
    while (!toVisit.empty()) {
      auto* container = toVisit.front();
      MEMORY_LOG("ScanBlack visit %p [%s]\n", container, colorNames[container->color()]);
      toVisit.pop_front();
      if (useColor) {
        auto color = container->color();
        if (color == CONTAINER_TAG_GC_GREEN || color == CONTAINER_TAG_GC_BLACK) continue;
        container->setColorAssertIfGreen(CONTAINER_TAG_GC_BLACK);
      } else {
        if (!container->marked()) continue;
        container->unMark();
      }
      traverseContainerReferredObjects(container, [&toVisit](ObjHeader* ref) {
          auto childContainer = containerFor(ref);
          RuntimeAssert(!isArena(childContainer), "A reference to local object is encountered");
          if (!isShareable(childContainer)) {
            childContainer->incRefCount<false>();
            if (useColor) {
              int color = childContainer->color();
              if (color != CONTAINER_TAG_GC_BLACK)
                toVisit.push_front(childContainer);
            } else {
              if (childContainer->marked())
                toVisit.push_front(childContainer);
            }
          }
      });
    }
  }
  
  void collectWhite(MemoryState*, ContainerHeader* container);
  
  void collectCycles(MemoryState* state) {
    markRoots(state);
    scanRoots(state);
    collectRoots(state);
    state->toFree->clear();
    state->roots->clear();
  }
  
  void markRoots(MemoryState* state) {
    for (auto container : *(state->toFree)) {
      if (isMarkedAsRemoved(container))
        continue;
      // Acyclic containers cannot be in this list.
      RuntimeCheck(container->color() != CONTAINER_TAG_GC_GREEN, "Must not be green");
      auto color = container->color();
      auto rcIsZero = container->refCount() == 0;
      if (color == CONTAINER_TAG_GC_PURPLE && !rcIsZero) {
        markGray<true>(container);
        state->roots->push_back(container);
      } else {
        container->resetBuffered();
        RuntimeAssert(color != CONTAINER_TAG_GC_GREEN, "Must not be green");
        if (color == CONTAINER_TAG_GC_BLACK && rcIsZero) {
          scheduleDestroyContainer(state, container);
        }
      }
    }
  }
  
  void scanRoots(MemoryState* state) {
    for (auto* container : *(state->roots)) {
      scan(container);
    }
  }
  
  void collectRoots(MemoryState* state) {
    // Here we might free some objects and call deallocation hooks on them,
    // which in turn might call DecrementRC and trigger new GC - forbid that.
    state->gcSuspendCount++;
    for (auto* container : *(state->roots)) {
      container->resetBuffered();
      collectWhite(state, container);
    }
    state->gcSuspendCount--;
  }
  
  void scan(ContainerHeader* start) {
    ContainerHeaderDeque toVisit;
    toVisit.push_front(start);
  
    while (!toVisit.empty()) {
       auto* container = toVisit.front();
       toVisit.pop_front();
       if (container->color() != CONTAINER_TAG_GC_GRAY) continue;
       if (container->refCount() != 0) {
         scanBlack<true>(container);
         continue;
       }
       container->setColorAssertIfGreen(CONTAINER_TAG_GC_WHITE);
       traverseContainerReferredObjects(container, [&toVisit](ObjHeader* ref) {
         auto* childContainer = containerFor(ref);
         RuntimeAssert(!isArena(childContainer), "A reference to local object is encountered");
         if (!isShareable(childContainer)) {
           toVisit.push_front(childContainer);
         }
       });
     }
  }
  
  void collectWhite(MemoryState* state, ContainerHeader* start) {
     ContainerHeaderDeque toVisit;
     toVisit.push_back(start);
  
     while (!toVisit.empty()) {
       auto* container = toVisit.front();
       toVisit.pop_front();
       if (container->color() != CONTAINER_TAG_GC_WHITE || container->buffered()) continue;
       container->setColorAssertIfGreen(CONTAINER_TAG_GC_BLACK);
       traverseContainerObjectFields(container, [&toVisit](ObjHeader** location) {
          auto* ref = *location;
          if (ref == nullptr) return;
          auto* childContainer = containerFor(ref);
          RuntimeAssert(!isArena(childContainer), "A reference to local object is encountered");
          if (isShareable(childContainer)) {
            ZeroHeapRef(location);
          } else {
            toVisit.push_front(childContainer);
          }
       });
       runDeallocationHooks(container);
       scheduleDestroyContainer(state, container);
    }
  }
  #endif
  
  #if COLLECT_STATISTIC
  inline bool needAtomicAccess(ContainerHeader* container) {
    return container->shareable();
  }
  
  inline bool canBeCyclic(ContainerHeader* container) {
    if (container->refCount() == 1) return false;
    if (container->color() == CONTAINER_TAG_GC_GREEN) return false;
    return true;
  }
  #endif
  
  inline void addHeapRef(ContainerHeader* container) {
    MEMORY_LOG("AddHeapRef %p: rc=%d\n", container, container->refCount())
    UPDATE_ADDREF_STAT(memoryState, container, needAtomicAccess(container), 0)
    switch (container->tag()) {
      case CONTAINER_TAG_STACK:
        break;
      case CONTAINER_TAG_LOCAL:
        RuntimeAssert(container->refCount() > 0, "add ref for reclaimed object");
        incrementRC</* Atomic = */ false>(container);
        break;
      /* case CONTAINER_TAG_FROZEN: case CONTAINER_TAG_SHARED: */
      default:
        RuntimeAssert(container->refCount() > 0, "add ref for reclaimed object");
        incrementRC</* Atomic = */ true>(container);
        break;
    }
  }
  
  inline void addHeapRef(const ObjHeader* header) {
    auto* container = containerFor(header);
    if (container != nullptr)
      addHeapRef(const_cast<ContainerHeader*>(container));
  }
  
  inline bool tryAddHeapRef(ContainerHeader* container) {
    switch (container->tag()) {
      case CONTAINER_TAG_STACK:
        break;
      case CONTAINER_TAG_LOCAL:
        if (!tryIncrementRC</* Atomic = */ false>(container)) return false;
        break;
      /* case CONTAINER_TAG_FROZEN: case CONTAINER_TAG_SHARED: */
      default:
        if (!tryIncrementRC</* Atomic = */ true>(container)) return false;
        break;
    }
  
    MEMORY_LOG("AddHeapRef %p: rc=%d\n", container, container->refCount() - 1)
    UPDATE_ADDREF_STAT(memoryState, container, needAtomicAccess(container), 0)
    return true;
  }
  
  inline bool tryAddHeapRef(const ObjHeader* header) {
    auto* container = containerFor(header);
    return (container != nullptr) ? tryAddHeapRef(container) : true;
  }
  
  template <bool Strict, bool CanCollect>
  inline void releaseHeapRef(ContainerHeader* container) {
    MEMORY_LOG("ReleaseHeapRef %p: rc=%d\n", container, container->refCount())
    UPDATE_RELEASEREF_STAT(memoryState, container, needAtomicAccess(container), canBeCyclic(container), 0)
    if (container->tag() != CONTAINER_TAG_STACK) {
      if (Strict)
        enqueueDecrementRC</* CanCollect = */ CanCollect>(container);
      else
        decrementRC(container);
    }
  }
  
  template <bool Strict, bool CanCollect = true>
  inline void releaseHeapRef(const ObjHeader* header) {
    auto* container = containerFor(header);
    if (container != nullptr)
      releaseHeapRef<Strict, CanCollect>(const_cast<ContainerHeader*>(container));
  }
  
  
  // TODO: Consider removing this unused stuff.
  #pragma clang diagnostic push
  #pragma clang diagnostic ignored "-Wunused-function"
  
  // We use first slot as place to store frame-local arena container.
  // TODO: create ArenaContainer object on the stack, so that we don't
  // do two allocations per frame (ArenaContainer + actual container).
  inline ArenaContainer* initedArena(ObjHeader** auxSlot) {
    auto frame = asFrameOverlay(auxSlot);
    auto arena = reinterpret_cast<ArenaContainer*>(frame->arena);
    if (!arena) {
      arena = konanConstructInstance<ArenaContainer>();
      MEMORY_LOG("Initializing arena in %p\n", frame)
      arena->Init();
      frame->arena = arena;
    }
    return arena;
  }
  
  inline size_t containerSize(const ContainerHeader* container) {
    size_t result = 0;
    const ObjHeader* obj = reinterpret_cast<const ObjHeader*>(container + 1);
    for (uint32_t object = 0; object < container->objectCount(); object++) {
      size_t size = objectSize(obj);
      result += size;
      obj = reinterpret_cast<ObjHeader*>(reinterpret_cast<uintptr_t>(obj) + size);
    }
    return result;
  }
  
  #pragma clang diagnostic pop
  
  #if USE_GC
  void incrementStack(MemoryState* state) {
    FrameOverlay* frame = currentFrame;
    while (frame != nullptr) {
      ObjHeader** current = reinterpret_cast<ObjHeader**>(frame + 1) + frame->parameters;
      ObjHeader** end = current + frame->count - kFrameOverlaySlots - frame->parameters;
      while (current < end) {
        ObjHeader* obj = *current++;
        if (obj != nullptr) {
          auto* container = containerFor(obj);
          if (container == nullptr) continue;
          if (container->shareable()) {
            incrementRC<true>(container);
          } else {
            incrementRC<false>(container);
          }
        }
      }
      frame = frame->previous;
    }
  }
  
  void processDecrements(MemoryState* state) {
    RuntimeAssert(IsStrictMemoryModel(), "Only works in strict model now");
    auto* toRelease = state->toRelease;
    state->gcSuspendCount++;
  
    state->foreignRefManager->processEnqueuedReleaseRefsWith([](ObjHeader* obj) {
      ContainerHeader* container = containerFor(obj);
      if (container != nullptr) decrementRC(container);
    });
  
    // The code above can call freeContainer if RC drops to zero.
    // freeContainer can in turn call ZeroHeapRef for freed object fields, which does enqueueDecrementRC.
    // The latter are processed by the code below. So if we reorder this, the enqueued decrement RC operations
    // will have to wait for the next GC unnecessarily.
    //
    // In addition to being inefficient, the reordering causes https://youtrack.jetbrains.com/issue/KT-49497:
    // The foreign ref to the frozen aggregating container gets released and causes freeContainer,
    // which in turn enqueues decrement RC for the same aggregating container.
    // The enqueued operations outlive processFinalizerQueue at the end of this GC, so during the next GC
    // they hit the reclaimed memory.
    // This is generally a special case of the known issue with frozen aggregating containers,
    // see "TODO: enable me, once account for inner references in frozen objects correctly." above.
    //
    // With the current order in this code, wrong accounting for inner references also happens,
    // but it doesn't do more harm than with regular (non-foreign) references (supposedly only breaks invariants locally).
  
    while (toRelease->size() > 0) {
       auto* container = toRelease->back();
       toRelease->pop_back();
       if (isMarkedAsRemoved(container))
         continue;
       if (container->shareable())
         container = realShareableContainer(container);
       decrementRC(container);
    }
  
    state->gcSuspendCount--;
  }
  
  void decrementStack(MemoryState* state) {
    RuntimeAssert(IsStrictMemoryModel(), "Only works in strict model now");
    state->gcSuspendCount++;
    FrameOverlay* frame = currentFrame;
    while (frame != nullptr) {
      ObjHeader** current = reinterpret_cast<ObjHeader**>(frame + 1) + frame->parameters;
      ObjHeader** end = current + frame->count - kFrameOverlaySlots - frame->parameters;
      while (current < end) {
        ObjHeader* obj = *current++;
        if (obj != nullptr) {
          MEMORY_LOG("decrement stack %p\n", obj)
          auto* container = containerFor(obj);
          if (container != nullptr)
            enqueueDecrementRC</* CanCollect = */ false>(container);
        }
      }
      frame = frame->previous;
    }
    state->gcSuspendCount--;
  }
  
  void garbageCollect(MemoryState* state, bool force) {
    RuntimeAssert(!state->gcInProgress, "Recursive GC is disallowed");
  
  #if TRACE_GC
    uint64_t allocSinceLastGc = state->allocSinceLastGc;
  #endif  // TRACE_GC
    state->allocSinceLastGc = 0;
  
    if (!IsStrictMemoryModel()) {
      // In relaxed model we just process finalizer queue and be done with it.
      processFinalizerQueue(state);
      return;
    }
  
    GC_LOG(">>> %s GC: threshold = %zu toFree %zu toRelease %zu alloc = %lld\n", \
       force ? "forced" : "regular", state->gcThreshold, state->toFree->size(),
       state->toRelease->size(), allocSinceLastGc)
  
    auto gcStartTime = konan::getTimeMicros();
  
    state->gcInProgress = true;
    state->gcEpoque++;
  
    incrementStack(state);
  #if USE_CYCLIC_GC
    // Block if the concurrent cycle collector is running.
    // We must do that to ensure collector sees state where actual RC properly upper estimated.
    if (g_hasCyclicCollector)
      cyclicLocalGC();
  #endif  // USE_CYCLIC_GC
  #if PROFILE_GC
    auto processDecrementsStartTime = konan::getTimeMicros();
  #endif
    processDecrements(state);
  #if PROFILE_GC
    auto processDecrementsDuration = konan::getTimeMicros() - processDecrementsStartTime;
    GC_LOG("||| GC: processDecrementsDuration = %lld\n", processDecrementsDuration);
    auto decrementStackStartTime = konan::getTimeMicros();
  #endif
    size_t beforeDecrements = state->toRelease->size();
    decrementStack(state);
    size_t afterDecrements = state->toRelease->size();
  #if PROFILE_GC
    auto decrementStackDuration = konan::getTimeMicros() - decrementStackStartTime;
    GC_LOG("||| GC: decrementStackDuration = %lld\n", decrementStackDuration);
  #endif
    RuntimeAssert(afterDecrements >= beforeDecrements, "toRelease size must not have decreased");
    size_t stackReferences = afterDecrements - beforeDecrements;
    if (state->gcErgonomics && stackReferences * 5 > state->gcThreshold) {
      increaseGcThreshold(state);
      GC_LOG("||| GC: too many stack references, increased threshold to %zu\n", state->gcThreshold);
    }
  
    GC_LOG("||| GC: toFree %zu toRelease %zu\n", state->toFree->size(), state->toRelease->size())
  #if PROFILE_GC
    auto processFinalizerQueueStartTime = konan::getTimeMicros();
  #endif
    processFinalizerQueue(state);
  #if PROFILE_GC
    auto processFinalizerQueueDuration = konan::getTimeMicros() - processFinalizerQueueStartTime;
    GC_LOG("||| GC: processFinalizerQueueDuration %lld\n", processFinalizerQueueDuration);
  #endif
  
    if (force || state->toFree->size() > state->gcCollectCyclesThreshold) {
      auto cyclicGcStartTime = konan::getTimeMicros();
      while (state->toFree->size() > 0) {
        collectCycles(state);
        #if PROFILE_GC
          processFinalizerQueueStartTime = konan::getTimeMicros();
        #endif
        processFinalizerQueue(state);
        #if PROFILE_GC
          processFinalizerQueueDuration += konan::getTimeMicros() - processFinalizerQueueStartTime;
          GC_LOG("||| GC: processFinalizerQueueDuration = %lld\n", processFinalizerQueueDuration);
        #endif
      }
      auto cyclicGcEndTime = konan::getTimeMicros();
      #if PROFILE_GC
        GC_LOG("||| GC: collectCyclesDuration = %lld\n", cyclicGcEndTime - cyclicGcStartTime);
      #endif
      auto cyclicGcDuration = cyclicGcEndTime - cyclicGcStartTime;
      if (!force && state->gcErgonomics && cyclicGcDuration > kGcCollectCyclesMinimumDuration &&
          double(cyclicGcDuration) / (cyclicGcStartTime - state->lastCyclicGcTimestamp + 1) > kGcCollectCyclesLoadRatio) {
        increaseGcCollectCyclesThreshold(state);
        GC_LOG("Adjusting GC collecting cycles threshold to %lld\n", state->gcCollectCyclesThreshold);
      }
      state->lastCyclicGcTimestamp = cyclicGcEndTime;
    }
  
    state->gcInProgress = false;
    auto gcEndTime = konan::getTimeMicros();
  
    if (state->gcErgonomics) {
      auto gcToComputeRatio = double(gcEndTime - gcStartTime) / (gcStartTime - state->lastGcTimestamp + 1);
      if (!force && gcToComputeRatio > kGcToComputeRatioThreshold) {
        increaseGcThreshold(state);
        GC_LOG("Adjusting GC threshold to %zu\n", state->gcThreshold);
      }
    }
    GC_LOG("GC: gcToComputeRatio=%f duration=%lld sinceLast=%lld\n", double(gcEndTime - gcStartTime) / (gcStartTime - state->lastGcTimestamp + 1), (gcEndTime - gcStartTime), gcStartTime - state->lastGcTimestamp);
    state->lastGcTimestamp = gcEndTime;
  
  #if TRACE_MEMORY
    for (auto* obj: *state->toRelease) {
      MEMORY_LOG("toRelease %p\n", obj)
    }
  #endif
  
    GC_LOG("<<< GC: toFree %zu toRelease %zu\n", state->toFree->size(), state->toRelease->size())
  }
  
  void rememberNewContainer(ContainerHeader* container) {
    if (container == nullptr) return;
    // Instances can be allocated before actual runtime init - be prepared for that.
    if (memoryState != nullptr) {
      incrementRC</* Atomic = */ true>(container);
      // We cannot collect until reference will be stored into the stack slot.
      enqueueDecrementRC</* CanCollect = */ true>(container);
    }
  }
  
  void garbageCollect() {
    garbageCollect(memoryState, true);
  }
  
  #endif  // USE_GC
  
  ForeignRefManager* initLocalForeignRef(ObjHeader* object) {
    if (!IsStrictMemoryModel()) return nullptr;
  
    return memoryState->foreignRefManager;
  }
  
  ForeignRefManager* initForeignRef(ObjHeader* object) {
    addHeapRef(object);
  
    if (!IsStrictMemoryModel()) return nullptr;
  
    // Note: it is possible to return nullptr for shared object as an optimization,
    // but this will force the implementation to release objects on uninitialized threads
    // which is generally a memory leak. See [deinitForeignRef].
    auto* manager = memoryState->foreignRefManager;
    manager->addRef();
    return manager;
  }
  
  bool isForeignRefAccessible(ObjHeader* object, ForeignRefManager* manager) {
    if (!IsStrictMemoryModel()) return true;
  
    if (manager == memoryState->foreignRefManager) {
      // Note: it is important that this code neither crashes nor returns false-negative result
      // (although may produce false-positive one) if [manager] is a dangling pointer.
      // See BackRefFromAssociatedObject::releaseRef for more details.
      return true;
    }
  
    // Note: getting container and checking it with 'isShareable()' is supposed to be correct even for unowned object.
    return isShareable(containerFor(object));
  }
  
  void deinitForeignRef(ObjHeader* object, ForeignRefManager* manager) {
    if (IsStrictMemoryModel()) {
      if (memoryState != nullptr && isForeignRefAccessible(object, manager)) {
        releaseHeapRef<true>(object);
      } else {
        // Prefer this for (memoryState == nullptr) since otherwise the object may leak:
        // an uninitialized thread did not run any Kotlin code;
        // it may be an externally-managed thread which is not supposed to run Kotlin code
        // and not going to exit soon.
        manager->enqueueReleaseRef(object);
      }
  
      manager->releaseRef();
    } else {
      releaseHeapRef<false>(object);
      RuntimeAssert(manager == nullptr, "must be null");
    }
  }
  
  MemoryState* initMemory(bool firstRuntime) {
    RuntimeAssert(offsetof(ArrayHeader, typeInfoOrMeta_)
                  ==
                  offsetof(ObjHeader,   typeInfoOrMeta_),
                  "Layout mismatch");
    RuntimeAssert(offsetof(TypeInfo, typeInfo_)
                  ==
                  offsetof(MetaObjHeader, typeInfo_),
                  "Layout mismatch");
    RuntimeAssert(sizeof(FrameOverlay) % sizeof(ObjHeader**) == 0, "Frame overlay should contain only pointers");
    RuntimeAssert(memoryState == nullptr, "memory state must be clear");
    memoryState = konanConstructInstance<MemoryState>();
    INIT_EVENT(memoryState)
  #if USE_GC
    memoryState->toFree = konanConstructInstance<ContainerHeaderList>();
    memoryState->roots = konanConstructInstance<ContainerHeaderList>();
    memoryState->gcInProgress = false;
    memoryState->gcSuspendCount = 0;
    memoryState->toRelease = konanConstructInstance<ContainerHeaderList>();
    initGcThreshold(memoryState, kGcThreshold);
    initGcCollectCyclesThreshold(memoryState, kMaxToFreeSizeThreshold);
    memoryState->allocSinceLastGcThreshold = kMaxGcAllocThreshold;
    memoryState->gcErgonomics = true;
  #endif
    memoryState->tls.Init();
    memoryState->foreignRefManager = ForeignRefManager::create();
    bool firstMemoryState = atomicAdd(&aliveMemoryStatesCount, 1) == 1;
    switch (kotlin::compiler::destroyRuntimeMode()) {
      case kotlin::compiler::DestroyRuntimeMode::kLegacy:
        firstRuntime = firstMemoryState;
        break;
      case kotlin::compiler::DestroyRuntimeMode::kOnShutdown:
        // Nothing to do.
        break;
    }
    if (firstRuntime) {
  #if USE_CYCLIC_GC
      cyclicInit();
  #endif  // USE_CYCLIC_GC
      memoryState->isMainThread = true;
    }
    return memoryState;
  }
  
  void deinitMemory(MemoryState* memoryState, bool destroyRuntime) {
    static int pendingDeinit = 0;
    atomicAdd(&pendingDeinit, 1);
  #if USE_GC
    bool lastMemoryState = atomicAdd(&aliveMemoryStatesCount, -1) == 0;
    switch (kotlin::compiler::destroyRuntimeMode()) {
      case kotlin::compiler::DestroyRuntimeMode::kLegacy:
        destroyRuntime = lastMemoryState;
        break;
      case kotlin::compiler::DestroyRuntimeMode::kOnShutdown:
        // Nothing to do
        break;
    }
    bool checkLeaks = Kotlin_memoryLeakCheckerEnabled() && destroyRuntime;
    if (destroyRuntime) {
     garbageCollect(memoryState, true);
  #if USE_CYCLIC_GC
     // If there are other pending deinits (rare situation) - just skip the leak checker.
     // This may happen when there're several threads with Kotlin runtimes created
     // by foreign code, and that code stops those threads simultaneously.
     if (atomicGet(&pendingDeinit) > 1) {
       checkLeaks = false;
     }
     cyclicDeinit(g_hasCyclicCollector);
  #endif  // USE_CYCLIC_GC
    }
    // Actual GC only implemented in strict memory model at the moment.
    do {
      GC_LOG("Calling garbageCollect from DeinitMemory()\n")
      garbageCollect(memoryState, true);
    } while (memoryState->toRelease->size() > 0 || !memoryState->foreignRefManager->tryReleaseRefOwned());
    RuntimeAssert(memoryState->toFree->size() == 0, "Some memory have not been released after GC");
    RuntimeAssert(memoryState->toRelease->size() == 0, "Some memory have not been released after GC");
    konanDestructInstance(memoryState->toFree);
    konanDestructInstance(memoryState->roots);
    konanDestructInstance(memoryState->toRelease);
    memoryState->tls.Deinit();
    RuntimeAssert(memoryState->finalizerQueue == nullptr, "Finalizer queue must be empty");
    RuntimeAssert(memoryState->finalizerQueueSize == 0, "Finalizer queue must be empty");
  #endif // USE_GC
  
    atomicAdd(&pendingDeinit, -1);
  
  #if TRACE_MEMORY
    if (IsStrictMemoryModel() && destroyRuntime && allocCount > 0) {
      MEMORY_LOG("*** Memory leaks, leaked %d containers ***\n", allocCount);
      dumpReachable("", memoryState->containers);
    }
  #else
  #if USE_GC
    if (IsStrictMemoryModel() && allocCount > 0 && checkLeaks) {
      konan::consoleErrorf(
          "Memory leaks detected, %d objects leaked!\n"
          "Use `Platform.isMemoryLeakCheckerActive = false` to avoid this check.\n", allocCount);
      konan::consoleFlush();
      konan::abort();
    }
  #endif  // USE_GC
  #endif  // TRACE_MEMORY
  
    PRINT_EVENT(memoryState)
    DEINIT_EVENT(memoryState)
  
    konanFreeMemory(memoryState);
    ::memoryState = nullptr;
  }
  
  void makeShareable(ContainerHeader* container) {
    if (!container->frozen())
      container->makeShared();
  }
  
  template<bool Strict>
  void setStackRef(ObjHeader** location, const ObjHeader* object) {
    MEMORY_LOG("SetStackRef *%p: %p\n", location, object)
    UPDATE_REF_EVENT(memoryState, nullptr, object, location, 1);
    if (!Strict && object != nullptr)
      addHeapRef(object);
    *const_cast<const ObjHeader**>(location) = object;
  }
  
  template<bool Strict>
  void setHeapRef(ObjHeader** location, const ObjHeader* object) {
    MEMORY_LOG("SetHeapRef *%p: %p\n", location, object)
    UPDATE_REF_EVENT(memoryState, nullptr, object, location, 0);
    if (object != nullptr)
      addHeapRef(const_cast<ObjHeader*>(object));
    *const_cast<const ObjHeader**>(location) = object;
  }
  
  void zeroHeapRef(ObjHeader** location) {
    MEMORY_LOG("ZeroHeapRef %p\n", location)
    auto* value = *location;
    if (!isNullOrMarker(value)) {
      UPDATE_REF_EVENT(memoryState, value, nullptr, location, 0);
      *location = nullptr;
      ReleaseHeapRef(value);
    }
  }
  
  template<bool Strict>
  void zeroStackRef(ObjHeader** location) {
    MEMORY_LOG("ZeroStackRef %p\n", location)
    if (Strict) {
      *location = nullptr;
    } else {
      auto* old = *location;
      *location = nullptr;
      if (old != nullptr) releaseHeapRef<Strict>(old);
    }
  }
  
  template <bool Strict>
  void updateHeapRef(ObjHeader** location, const ObjHeader* object) {
    UPDATE_REF_EVENT(memoryState, *location, object, location, 0);
    ObjHeader* old = *location;
    if (old != object) {
      if (object != nullptr) {
        addHeapRef(object);
      }
      *const_cast<const ObjHeader**>(location) = object;
      if (!isNullOrMarker(old)) {
        releaseHeapRef<Strict>(old);
      }
    }
  }
  
  template <bool Strict>
  void updateHeapRefsInsideOneArray(const ArrayHeader* array, int fromIndex, int toIndex, int count) {
    // In case of coping inside same array number of decrements and increments of RC can be decreased.
    auto countIndex = [=](int i) { return (fromIndex < toIndex) ? count - 1 - i : i; };
    int rewrittenElementsNumber = std::abs(fromIndex - toIndex);
    // Release rewritten elements.
    for (int i = 0; i < rewrittenElementsNumber; i++) {
      int index = countIndex(i);
      ObjHeader* old = *ArrayAddressOfElementAt(array, toIndex + index);
      *const_cast<const ObjHeader**>(ArrayAddressOfElementAt(array, toIndex + index)) =
        *ArrayAddressOfElementAt(array, fromIndex + index);
      if (old != nullptr) {
        releaseHeapRef<Strict>(old);
      }
    }
    for (int i = rewrittenElementsNumber; i < count - rewrittenElementsNumber; i++) {
      int index = countIndex(i);
      *const_cast<const ObjHeader**>(ArrayAddressOfElementAt(array, toIndex + index)) =
           *ArrayAddressOfElementAt(array, fromIndex + index);
    }
    for (int i = count - rewrittenElementsNumber; i < count; i++) {
      int index = countIndex(i);
      ObjHeader* object = *ArrayAddressOfElementAt(array, fromIndex + index);
      // Add extra heap ref for copied elements.
      if (object != nullptr) {
        addHeapRef(object);
      }
      *const_cast<const ObjHeader**>(ArrayAddressOfElementAt(array, toIndex + index)) = object;
    }
  }
  
  template <bool Strict>
  void updateStackRef(ObjHeader** location, const ObjHeader* object) {
    UPDATE_REF_EVENT(memoryState, *location, object, location, 1)
    RuntimeAssert(object != kInitializingSingleton, "Markers disallowed here");
    if (Strict) {
      *const_cast<const ObjHeader**>(location) = object;
    } else {
       ObjHeader* old = *location;
       if (old != object) {
          if (object != nullptr) {
            addHeapRef(object);
          }
          *const_cast<const ObjHeader**>(location) = object;
          if (old != nullptr) {
             releaseHeapRef<false>(old);
          }
       }
    }
  }
  
  template <bool Strict>
  void updateReturnRef(ObjHeader** returnSlot, const ObjHeader* value) {
    updateStackRef<Strict>(returnSlot, value);
  }
  
  void updateHeapRefIfNull(ObjHeader** location, const ObjHeader* object) {
    if (object != nullptr) {
  #if KONAN_NO_THREADS
      ObjHeader* old = *location;
      if (old == nullptr) {
        addHeapRef(const_cast<ObjHeader*>(object));
        *const_cast<const ObjHeader**>(location) = object;
      }
  #else
      addHeapRef(const_cast<ObjHeader*>(object));
      auto old = __sync_val_compare_and_swap(location, nullptr, const_cast<ObjHeader*>(object));
      if (old != nullptr) {
        // Failed to store, was not null.
       ReleaseHeapRef(const_cast<ObjHeader*>(object));
      }
  #endif
      UPDATE_REF_EVENT(memoryState, old, object, location, 0);
    }
  }
  
  inline void checkIfGcNeeded(MemoryState* state) {
    if (state != nullptr && state->allocSinceLastGc > state->allocSinceLastGcThreshold && state->gcSuspendCount == 0) {
      // To avoid GC trashing check that at least 10ms passed since last GC.
      if (konan::getTimeMicros() - state->lastGcTimestamp > 10 * 1000) {
        GC_LOG("Calling GC from checkIfGcNeeded: %zu\n", state->toRelease->size())
        garbageCollect(state, false);
      }
    }
  }
  
  inline void checkIfForceCyclicGcNeeded(MemoryState* state) {
    if (state != nullptr && state->toFree != nullptr && state->toFree->size() > kMaxToFreeSizeThreshold
        && state->gcSuspendCount == 0) {
      // To avoid GC trashing check that at least 10ms passed since last GC.
      if (konan::getTimeMicros() - state->lastGcTimestamp > 10 * 1000) {
        GC_LOG("Calling GC from checkIfForceCyclicGcNeeded: %zu\n", state->toFree->size())
        garbageCollect(state, true);
      }
    }
  }
  
  template <bool Strict>
  OBJ_GETTER(allocInstance, const TypeInfo* type_info) {
    RuntimeAssert(type_info->instanceSize_ >= 0, "must be an object");
    auto* state = memoryState;
  #if USE_GC
    checkIfGcNeeded(state);
  #endif  // USE_GC
    auto container = ObjectContainer(state, type_info);
    ObjHeader* obj = container.GetPlace();
  #if USE_GC
    if (Strict) {
      rememberNewContainer(container.header());
    } else {
      makeShareable(container.header());
    }
  #endif  // USE_GC
  #if USE_CYCLE_DETECTOR
    CycleDetector::insertCandidateIfNeeded(obj);
  #endif  // USE_CYCLE_DETECTOR
  #if USE_CYCLIC_GC
    if ((obj->type_info()->flags_ & TF_LEAK_DETECTOR_CANDIDATE) != 0) {
      // Note: this should be performed after [rememberNewContainer] (above).
      // Otherwise cyclic collector can observe this atomic root with RC = 0,
      // thus consider it garbage and then zero it after initialization.
      cyclicAddAtomicRoot(obj);
    }
  #endif  // USE_CYCLIC_GC
    RETURN_OBJ(obj);
  }
  
  template <bool Strict>
  OBJ_GETTER(allocArrayInstance, const TypeInfo* type_info, int32_t elements) {
    RuntimeAssert(type_info->instanceSize_ < 0, "must be an array");
    if (elements < 0) ThrowIllegalArgumentException();
    auto* state = memoryState;
  #if USE_GC
    checkIfGcNeeded(state);
  #endif  // USE_GC
    auto container = ArrayContainer(state, type_info, elements);
  #if USE_GC
    if (Strict) {
      rememberNewContainer(container.header());
    } else {
      makeShareable(container.header());
    }
  #endif  // USE_GC
    RETURN_OBJ(container.GetPlace()->obj());
  }
  
  template <bool Strict>
  OBJ_GETTER(initThreadLocalSingleton,
      ObjHeader** location, const TypeInfo* typeInfo, void (*ctor)(ObjHeader*)) {
    ObjHeader* value = *location;
    if (value != nullptr) {
      // OK'ish, inited by someone else.
      RETURN_OBJ(value);
    }
    ObjHeader* object = allocInstance<Strict>(typeInfo, OBJ_RESULT);
    updateHeapRef<Strict>(location, object);
  #if KONAN_NO_EXCEPTIONS
    ctor(object);
    return object;
  #else
    try {
      ctor(object);
      return object;
    } catch (...) {
      UpdateReturnRef(OBJ_RESULT, nullptr);
      ZeroHeapRef(location);
      throw;
    }
  #endif
  }
  
  template <bool Strict>
  OBJ_GETTER(initSingleton, ObjHeader** location, const TypeInfo* typeInfo, void (*ctor)(ObjHeader*)) {
  #if KONAN_NO_THREADS
    ObjHeader* value = *location;
    if (value != nullptr) {
      // OK'ish, inited by someone else.
      RETURN_OBJ(value);
    }
    ObjHeader* object = AllocInstance(typeInfo, OBJ_RESULT);
    UpdateHeapRef(location, object);
  #if KONAN_NO_EXCEPTIONS
    ctor(object);
    FreezeSubgraph(object);
    return object;
  #else
    try {
      ctor(object);
      if (Strict)
        FreezeSubgraph(object);
      return object;
    } catch (...) {
      UpdateReturnRef(OBJ_RESULT, nullptr);
      ZeroHeapRef(location);
      throw;
    }
  #endif  // KONAN_NO_EXCEPTIONS
  #else  // KONAN_NO_THREADS
    // Search from the top of the stack.
    for (auto it = memoryState->initializingSingletons.rbegin(); it != memoryState->initializingSingletons.rend(); ++it) {
      if (it->first == location) {
        RETURN_OBJ(it->second);
      }
    }
  
    ObjHeader* initializing = kInitializingSingleton;
  
    // Spin lock.
    ObjHeader* value = nullptr;
    while ((value = __sync_val_compare_and_swap(location, nullptr, initializing)) == initializing);
    if (value != nullptr) {
      // OK'ish, inited by someone else.
      RETURN_OBJ(value);
    }
    ObjHeader* object = AllocInstance(typeInfo, OBJ_RESULT);
    memoryState->initializingSingletons.push_back(std::make_pair(location, object));
  #if KONAN_NO_EXCEPTIONS
    ctor(object);
    if (Strict)
      FreezeSubgraph(object);
    UpdateHeapRef(location, object);
    synchronize();
    memoryState->initializingSingletons.pop_back();
    return object;
  #else  // KONAN_NO_EXCEPTIONS
    try {
      ctor(object);
      if (Strict)
        FreezeSubgraph(object);
      UpdateHeapRef(location, object);
      synchronize();
      memoryState->initializingSingletons.pop_back();
      return object;
    } catch (...) {
      UpdateReturnRef(OBJ_RESULT, nullptr);
      zeroHeapRef(location);
      memoryState->initializingSingletons.pop_back();
      synchronize();
      throw;
    }
  #endif  // KONAN_NO_EXCEPTIONS
  #endif  // KONAN_NO_THREADS
  }
  
  /**
   * We keep thread affinity and reference value based cookie in the atomic references, so that
   * repeating read operation of the same value do not lead to the repeating rememberNewContainer() operation.
   * We must invalidate cookie after the local GC, as otherwise fact that container of the `value` is retained
   * may change, if the last reference to the value read is lost during GC and we re-read same value from
   * the same atomic reference. Thus we also include GC epoque into the cookie.
   */
  inline int32_t computeCookie() {
    auto* state = memoryState;
    auto epoque = state->gcEpoque;
    return (static_cast<int32_t>(reinterpret_cast<intptr_t>(state))) ^ static_cast<int32_t>(epoque);
  }
  
  OBJ_GETTER(swapHeapRefLocked,
      ObjHeader** location, ObjHeader* expectedValue, ObjHeader* newValue, int32_t* spinlock, int32_t* cookie) {
    lock(spinlock);
    ObjHeader* oldValue = *location;
    bool shallRemember = false;
    if (IsStrictMemoryModel()) {
      auto realCookie = computeCookie();
      shallRemember = *cookie != realCookie;
      if (shallRemember) *cookie = realCookie;
    }
    if (oldValue == expectedValue) {
  #if USE_CYCLIC_GC
      if (g_hasCyclicCollector)
        cyclicMutateAtomicRoot(newValue);
  #endif  // USE_CYCLIC_GC
      SetHeapRef(location, newValue);
    }
    UpdateReturnRef(OBJ_RESULT, oldValue);
  
    if (IsStrictMemoryModel() && shallRemember && oldValue != nullptr && oldValue != expectedValue) {
      // Only remember container if it is not known to this thread (i.e. != expectedValue).
      rememberNewContainer(containerFor(oldValue));
    }
    unlock(spinlock);
  
    if (oldValue != nullptr && oldValue == expectedValue) {
      ReleaseHeapRef(oldValue);
    }
    return oldValue;
  }
  
  void setHeapRefLocked(ObjHeader** location, ObjHeader* newValue, int32_t* spinlock, int32_t* cookie) {
    lock(spinlock);
    ObjHeader* oldValue = *location;
  #if USE_CYCLIC_GC
    if (g_hasCyclicCollector)
      cyclicMutateAtomicRoot(newValue);
  #endif  // USE_CYCLIC_GC
    // We do not use UpdateRef() here to avoid having ReleaseRef() on old value under the lock.
    SetHeapRef(location, newValue);
    *cookie = computeCookie();
    unlock(spinlock);
    if (oldValue != nullptr)
      ReleaseHeapRef(oldValue);
  }
  
  OBJ_GETTER(readHeapRefLocked, ObjHeader** location, int32_t* spinlock, int32_t* cookie) {
    MEMORY_LOG("ReadHeapRefLocked: %p\n", location)
    lock(spinlock);
    ObjHeader* value = *location;
    auto realCookie = computeCookie();
    bool shallRemember = *cookie != realCookie;
    if (shallRemember) *cookie = realCookie;
    UpdateReturnRef(OBJ_RESULT, value);
  #if USE_GC
    if (IsStrictMemoryModel() && shallRemember && value != nullptr) {
      auto* container = containerFor(value);
      rememberNewContainer(container);
    }
  #endif  // USE_GC
    unlock(spinlock);
    return value;
  }
  
  OBJ_GETTER(readHeapRefNoLock, ObjHeader* object, KInt index) {
    MEMORY_LOG("ReadHeapRefNoLock: %p index %d\n", object, index)
    ObjHeader** location = reinterpret_cast<ObjHeader**>(
      reinterpret_cast<uintptr_t>(object) + object->type_info()->objOffsets_[index]);
    ObjHeader* value = *location;
  #if USE_GC
    if (IsStrictMemoryModel() && (value != nullptr)) {
      // Maybe not so good to do that under lock.
      rememberNewContainer(containerFor(value));
    }
  #endif  // USE_GC
    RETURN_OBJ(value);
  }
  
  template <bool Strict>
  void enterFrame(ObjHeader** start, int parameters, int count) {
    MEMORY_LOG("EnterFrame %p: %d parameters %d locals\n", start, parameters, count)
    FrameOverlay* frame = reinterpret_cast<FrameOverlay*>(start);
    if (Strict) {
      frame->previous = currentFrame;
      currentFrame = frame;
      // TODO: maybe compress in single value somehow.
      frame->parameters = parameters;
      frame->count = count;
    }
  }
  
  template <bool Strict>
  void leaveFrame(ObjHeader** start, int parameters, int count) {
    MEMORY_LOG("LeaveFrame %p: %d parameters %d locals\n", start, parameters, count)
    FrameOverlay* frame = reinterpret_cast<FrameOverlay*>(start);
    RuntimeAssert(currentFrame == frame, "Frame to leave is expected to be %p, but current frame is %p", frame, currentFrame);
    if (Strict) {
      currentFrame = frame->previous;
    } else {
      ObjHeader** current = start + parameters + kFrameOverlaySlots;
      count -= parameters;
      while (count-- > kFrameOverlaySlots) {
        ObjHeader* object = *current;
        if (object != nullptr) {
            releaseHeapRef<false>(object);
          }
          current++;
        }
    }
  }
  
  template <bool Strict>
  void setCurrentFrame(ObjHeader** start) {
      MEMORY_LOG("SetCurrentFrame %p\n", start)
      FrameOverlay* frame = reinterpret_cast<FrameOverlay*>(start);
      if (Strict) {
          currentFrame = frame;
      } else {
          RuntimeFail("Relaxed memory model is deprecated and doesn't support exception handling proper way!\n");
      }
  }
  
  void suspendGC() {
    GC_LOG("suspendGC\n")
    memoryState->gcSuspendCount++;
  }
  
  void resumeGC() {
    GC_LOG("resumeGC\n")
    MemoryState* state = memoryState;
    if (state->gcSuspendCount > 0) {
      state->gcSuspendCount--;
      if (state->toRelease != nullptr &&
          state->toRelease->size() >= state->gcThreshold &&
          state->gcSuspendCount == 0) {
  
        garbageCollect(state, false);
      }
    }
  }
  
  void stopGC() {
    GC_LOG("stopGC\n")
    if (memoryState->toRelease != nullptr) {
      memoryState->gcSuspendCount = 0;
      garbageCollect(memoryState, true);
      konanDestructInstance(memoryState->toRelease);
      konanDestructInstance(memoryState->toFree);
      konanDestructInstance(memoryState->roots);
      memoryState->toRelease = nullptr;
      memoryState->toFree = nullptr;
      memoryState->roots = nullptr;
    }
  }
  
  void startGC() {
    GC_LOG("startGC\n")
    if (memoryState->toFree == nullptr) {
      memoryState->toFree = konanConstructInstance<ContainerHeaderList>();
      memoryState->toRelease = konanConstructInstance<ContainerHeaderList>();
      memoryState->roots = konanConstructInstance<ContainerHeaderList>();
      memoryState->gcSuspendCount = 0;
    }
  }
  
  void setGCThreshold(KInt value) {
    GC_LOG("setGCThreshold %d\n", value)
    if (value <= 0) {
      ThrowIllegalArgumentException();
    }
    initGcThreshold(memoryState, value);
  }
  
  KInt getGCThreshold() {
    GC_LOG("getGCThreshold\n")
    return memoryState->gcThreshold;
  }
  
  void setGCCollectCyclesThreshold(KLong value) {
    GC_LOG("setGCCollectCyclesThreshold %lld\n", value)
    if (value <= 0) {
      ThrowIllegalArgumentException();
    }
    initGcCollectCyclesThreshold(memoryState, value);
  }
  
  KInt getGCCollectCyclesThreshold() {
    GC_LOG("getGCCollectCyclesThreshold\n")
    return memoryState->gcCollectCyclesThreshold;
  }
  
  void setGCThresholdAllocations(KLong value) {
    GC_LOG("setGCThresholdAllocations %lld\n", value)
    if (value <= 0) {
      ThrowIllegalArgumentException();
    }
  
    memoryState->allocSinceLastGcThreshold = value;
  }
  
  KLong getGCThresholdAllocations() {
    GC_LOG("getGCThresholdAllocation\n")
    return memoryState->allocSinceLastGcThreshold;
  }
  
  void setTuneGCThreshold(KBoolean value) {
    GC_LOG("setTuneGCThreshold %d\n", value)
    memoryState->gcErgonomics = value;
  }
  
  KBoolean getTuneGCThreshold() {
    GC_LOG("getTuneGCThreshold %d\n", memoryState->gcErgonomics)
    return memoryState->gcErgonomics;
  }
  
  KNativePtr createStablePointer(KRef any) {
    if (any == nullptr) return nullptr;
    MEMORY_LOG("CreateStablePointer for %p rc=%d\n", any, containerFor(any) ? containerFor(any)->refCount() : 0)
    addHeapRef(any);
    return reinterpret_cast<KNativePtr>(any);
  }
  
  void disposeStablePointer(KNativePtr pointer) {
    if (pointer == nullptr) return;
    KRef ref = reinterpret_cast<KRef>(pointer);
    ReleaseHeapRef(ref);
  }
  
  OBJ_GETTER(derefStablePointer, KNativePtr pointer) {
    KRef ref = reinterpret_cast<KRef>(pointer);
    AdoptReferenceFromSharedVariable(ref);
    RETURN_OBJ(ref);
  }
  
  OBJ_GETTER(adoptStablePointer, KNativePtr pointer) {
    synchronize();
    KRef ref = reinterpret_cast<KRef>(pointer);
    MEMORY_LOG("adopting stable pointer %p, rc=%d\n", \
       ref, (ref && containerFor(ref)) ? containerFor(ref)->refCount() : -1)
    UpdateReturnRef(OBJ_RESULT, ref);
    DisposeStablePointer(pointer);
    return ref;
  }
  
  bool clearSubgraphReferences(ObjHeader* root, bool checked) {
  #if USE_GC
    MEMORY_LOG("ClearSubgraphReferences %p\n", root)
    if (root == nullptr) return true;
    auto state = memoryState;
    auto* container = containerFor(root);
  
    if (isShareable(container))
      // We assume, that frozen/shareable objects can be safely passed and not present
      // in the GC candidate list.
      // TODO: assert for that?
      return true;
  
    // Free cyclic garbage to decrease number of analyzed objects.
    checkIfForceCyclicGcNeeded(state);
  
    ContainerHeaderSet visited;
    if (!checked) {
      hasExternalRefs(container, &visited);
    } else {
      // Now decrement RC of elements in toRelease set for reachibility analysis.
      for (auto it = state->toRelease->begin(); it != state->toRelease->end(); ++it) {
        auto released = *it;
        if (!isMarkedAsRemoved(released) && released->local()) {
          released->decRefCount<false>();
        }
      }
      container->decRefCount<false>();
      markGray<false>(container);
      auto bad = hasExternalRefs(container, &visited);
      scanBlack<false>(container);
      // Restore original RC.
      container->incRefCount<false>();
      for (auto it = state->toRelease->begin(); it != state->toRelease->end(); ++it) {
         auto released = *it;
         if (!isMarkedAsRemoved(released) && released->local()) {
           released->incRefCount<false>();
         }
      }
      if (bad) {
        return false;
      }
    }
  
    // Remove all no longer owned containers from GC structures.
    // TODO: not very efficient traversal.
    for (auto it = state->toFree->begin(); it != state->toFree->end(); ++it) {
      auto container = *it;
      if (visited.count(container) != 0) {
        MEMORY_LOG("removing %p from the toFree list\n", container)
        container->resetBuffered();
        container->setColorAssertIfGreen(CONTAINER_TAG_GC_BLACK);
        *it = markAsRemoved(container);
      }
    }
    for (auto it = state->toRelease->begin(); it != state->toRelease->end(); ++it) {
      auto container = *it;
      if (!isMarkedAsRemoved(container) && visited.count(container) != 0) {
        MEMORY_LOG("removing %p from the toRelease list\n", container)
        container->decRefCount<false>();
        *it = markAsRemoved(container);
      }
    }
  
  #if TRACE_MEMORY
    // Forget transferred containers.
    for (auto* it: visited) {
      state->containers->erase(it);
    }
  #endif
  
  #endif  // USE_GC
    return true;
  }
  
  void freezeAcyclic(ContainerHeader* rootContainer, ContainerHeaderSet* newlyFrozen) {
    KStdDeque<ContainerHeader*> queue;
    queue.push_back(rootContainer);
    while (!queue.empty()) {
      ContainerHeader* current = queue.front();
      queue.pop_front();
      current->unMark();
      current->resetBuffered();
      current->setColorUnlessGreen(CONTAINER_TAG_GC_BLACK);
      // Note, that once object is frozen, it could be concurrently accessed, so
      // color and similar attributes shall not be used.
      if (!current->frozen())
        newlyFrozen->insert(current);
      MEMORY_LOG("freezing %p\n", current)
      current->freeze();
      traverseContainerReferredObjects(current, [&queue](ObjHeader* obj) {
          ContainerHeader* objContainer = containerFor(obj);
          if (canFreeze(objContainer)) {
            if (objContainer->marked())
              queue.push_back(objContainer);
          }
      });
    }
  }
  
  void freezeCyclic(ObjHeader* root,
                    const KStdVector<ContainerHeader*>& order,
                    ContainerHeaderSet* newlyFrozen) {
    KStdUnorderedMap<ContainerHeader*, KStdVector<ContainerHeader*>> reversedEdges;
    KStdDeque<ObjHeader*> queue;
    queue.push_back(root);
    while (!queue.empty()) {
      ObjHeader* current = queue.front();
      queue.pop_front();
      ContainerHeader* currentContainer = containerFor(current);
      currentContainer->unMark();
      reversedEdges.emplace(currentContainer, KStdVector<ContainerHeader*>(0));
      traverseContainerReferredObjects(currentContainer, [current, currentContainer, &queue, &reversedEdges](ObjHeader* obj) {
            ContainerHeader* objContainer = containerFor(obj);
            if (canFreeze(objContainer)) {
              if (objContainer->marked())
                queue.push_back(obj);
              // We ignore references from FreezableAtomicsReference during condensation, to avoid KT-33824.
              if (!isFreezableAtomic(current))
                reversedEdges.emplace(objContainer, KStdVector<ContainerHeader*>(0)).
                  first->second.push_back(currentContainer);
            }
        });
     }
  
     KStdVector<KStdVector<ContainerHeader*>> components;
     MEMORY_LOG("Condensation:\n");
     // Enumerate in the topological order.
     for (auto it = order.rbegin(); it != order.rend(); ++it) {
       auto* container = *it;
       if (container->marked()) continue;
       KStdVector<ContainerHeader*> component;
       traverseStronglyConnectedComponent(container, &reversedEdges, &component);
       MEMORY_LOG("SCC:\n");
    #if TRACE_MEMORY
       for (auto c: component)
         konan::consolePrintf("    %p\n", c);
    #endif
       components.push_back(std::move(component));
     }
  
    // Enumerate strongly connected components in reversed topological order.
    for (auto it = components.rbegin(); it != components.rend(); ++it) {
      auto& component = *it;
      int internalRefsCount = 0;
      int totalCount = 0;
      for (auto* container : component) {
        RuntimeAssert(!isAggregatingFrozenContainer(container), "Must not be called on such containers");
        totalCount += container->refCount();
        if (isFreezableAtomic(container)) {
          RuntimeAssert(component.size() == 1, "Must be trivial condensation");
          continue;
        }
        traverseContainerReferredObjects(container, [&internalRefsCount](ObjHeader* obj) {
            auto* container = containerFor(obj);
            if (canFreeze(container))
              ++internalRefsCount;
          });
      }
  
      // Freeze component.
      for (auto* container : component) {
        container->resetBuffered();
        container->setColorUnlessGreen(CONTAINER_TAG_GC_BLACK);
        if (!container->frozen())
          newlyFrozen->insert(container);
        // Note, that once object is frozen, it could be concurrently accessed, so
        // color and similar attributes shall not be used.
        MEMORY_LOG("freezing %p\n", container)
        container->freeze();
        // We set refcount of original container to zero, so that it is seen as such after removal
        // meta-object, where aggregating container is stored.
        container->setRefCount(0);
      }
  
      // Create fictitious container for the whole component.
      auto superContainer = component.size() == 1 ? component[0] : allocAggregatingFrozenContainer(component);
      // Don't count internal references.
      MEMORY_LOG("Setting aggregating %p rc to %d (total %d inner %d)\n", \
         superContainer, totalCount - internalRefsCount, totalCount, internalRefsCount)
      superContainer->setRefCount(totalCount - internalRefsCount);
      newlyFrozen->insert(superContainer);
    }
  }
  
  void runFreezeHooksRecursive(ObjHeader* root) {
    KStdUnorderedSet<KRef> seen;
    KStdVector<KRef> toVisit;
    seen.insert(root);
    toVisit.push_back(root);
    while (!toVisit.empty()) {
      KRef obj = toVisit.back();
      toVisit.pop_back();
  
      kotlin::RunFreezeHooks(obj);
  
      kotlin::traverseReferredObjects(obj, [&seen, &toVisit](ObjHeader* field) {
        auto wasNotSeenYet = seen.insert(field).second;
        // Only iterating on unseen objects which containers will get frozen by freezeCyclic or freezeAcyclic.
        if (wasNotSeenYet && canFreeze(containerFor(field))) {
          toVisit.push_back(field);
        }
      });
    }
  }
  
  /**
   * Theory of operations.
   *
   * Kotlin/Native supports object graph freezing, allowing to make certain subgraph immutable and thus
   * suitable for safe sharing amongst multiple concurrent executors. This operation recursively operates
   * on all objects reachable from the given object, and marks them as frozen. In frozen state object's
   * fields cannot be modified, and so, lifetime of frozen objects correlates. Practically, it means
   * that lifetimes of all strongly connected components are fully controlled by incoming reference
   * counters, and so if we place all members of strongly connected component to the single container
   * it could be correctly released by just atomic decrement on reference counter, without additional
   * cycle collector run.
   * So during subgraph freezing operation, we perform the following steps:
   *   - run Kosoraju-Sharir algorithm to find strongly connected components
   *   - put all objects in each strongly connected component into an artificial container
   *     (we assume that they all were in single element containers initially), single-object
   *     components remain in the same container
   *   - artificial container sums up outer reference counters of all its objects (i.e.
   *     incoming references from the same strongly connected component are not counted)
   *   - mark all object's headers as frozen
   *
   *  Further reference counting on frozen objects is performed with atomic operations, and so frozen
   * references could be passed across multiple threads.
   */
  void freezeSubgraph(ObjHeader* root) {
    if (root == nullptr) return;
    // First check that passed object graph has no cycles.
    // If there are cycles - run graph condensation on cyclic graphs using Kosoraju-Sharir.
    ContainerHeader* rootContainer = containerFor(root);
    if (isPermanentOrFrozen(rootContainer)) return;
  
    MEMORY_LOG("Run freeze hooks on subgraph of %p\n", root);
  
    // Note: Actual freezing can fail, but these hooks won't be undone, and moreover
    // these hooks will run again on a repeated freezing attempt.
    runFreezeHooksRecursive(root);
  
    MEMORY_LOG("Freeze subgraph of %p\n", root)
  
    #if USE_GC
      auto state = memoryState;
      // Free cyclic garbage to decrease number of analyzed objects.
      checkIfForceCyclicGcNeeded(state);
    #endif
  
    // Do DFS cycle detection.
    bool hasCycles = false;
    KRef firstBlocker = root->has_meta_object() && ((root->meta_object()->flags_ & MF_NEVER_FROZEN) != 0) ?
      root : nullptr;
    KStdVector<ContainerHeader*> order;
    depthFirstTraversal(rootContainer, &hasCycles, &firstBlocker, &order);
    if (firstBlocker != nullptr) {
      MEMORY_LOG("See freeze blocker for %p: %p\n", root, firstBlocker)
      ThrowFreezingException(root, firstBlocker);
    }
    ContainerHeaderSet newlyFrozen;
    // Now unmark all marked objects, and freeze them, if no cycles detected.
    if (hasCycles) {
      freezeCyclic(root, order, &newlyFrozen);
    } else {
      freezeAcyclic(rootContainer, &newlyFrozen);
    }
    MEMORY_LOG("Graph of %p is %s with %d elements\n", root, hasCycles ? "cyclic" : "acyclic", newlyFrozen.size())
  
  #if USE_GC
    // Now remove frozen objects from the toFree list.
    // TODO: optimize it by keeping ignored (i.e. freshly frozen) objects in the set,
    // and use it when analyzing toFree during collection.
    for (auto& container : *(state->toFree)) {
      if (!isMarkedAsRemoved(container) && container->frozen()) {
        RuntimeAssert(newlyFrozen.count(container) != 0, "Must be newly frozen");
        container = markAsRemoved(container);
      }
    }
  #endif
  }
  
  void ensureNeverFrozen(ObjHeader* object) {
     auto* container = containerFor(object);
     if (container == nullptr || container->frozen())
        ThrowFreezingException(object, object);
     // TODO: note, that this API could not not be called on frozen objects, so no need to care much about concurrency,
     // although there's subtle race with case, where other thread freezes the same object after check.
     object->meta_object()->flags_ |= MF_NEVER_FROZEN;
  }
  
  void shareAny(ObjHeader* obj) {
    auto* container = containerFor(obj);
    if (isShareable(container)) return;
    RuntimeCheck(container->objectCount() == 1, "Must be a single object container");
    container->makeShared();
  }
  
  ScopedRefHolder::ScopedRefHolder(KRef obj): obj_(obj) {
    if (obj_) {
      addHeapRef(obj_);
    }
  }
  
  ScopedRefHolder::~ScopedRefHolder() {
    if (obj_) {
      ReleaseHeapRef(obj_);
    }
  }
  
  #if USE_CYCLE_DETECTOR
  
  // static
  CycleDetectorRootset CycleDetector::collectRootset() {
    auto& detector = instance();
    CycleDetectorRootset rootset;
    std::lock_guard guard(detector.lock_);
    for (auto* candidate: detector.candidateList_) {
      // Only frozen candidates are to be analyzed.
      if (!isPermanentOrFrozen(candidate))
        continue;
      rootset.roots.push_back(candidate);
      rootset.heldRefs.emplace_back(candidate);
      kotlin::traverseReferredObjects(candidate, [&rootset, candidate](KRef field) {
        rootset.rootToFields[candidate].push_back(field);
        // TODO: There's currently a race here:
        // some other thread might null this field and destroy it in GC before
        // we put it in ScopedRefHolder.
        rootset.heldRefs.emplace_back(field);
      });
    }
    return rootset;
  }
  
  KStdVector<KRef> findCycleWithDFS(KRef root, const CycleDetectorRootset& rootset) {
    auto traverseFields = [&rootset](KRef obj, auto process) {
      auto it = rootset.rootToFields.find(obj);
      // If obj is in the rootset, use it's pinned state.
      if (it != rootset.rootToFields.end()) {
        const auto& fields = it->second;
        for (KRef field: fields) {
          if (field != nullptr) {
            process(field);
          }
        }
        return;
      }
  
      kotlin::traverseReferredObjects(obj, process);
    };
  
    KStdVector<KStdVector<KRef>> toVisit;
    auto appendFieldsToVisit = [&toVisit, &traverseFields](KRef obj, const KStdVector<KRef>& currentPath) {
      traverseFields(obj, [&toVisit, &currentPath](KRef field) {
        auto path = currentPath;
        path.push_back(field);
        toVisit.emplace_back(std::move(path));
      });
    };
  
    appendFieldsToVisit(root, KRefList(1, root));
  
    KStdUnorderedSet<KRef> seen;
    seen.insert(root);
    while (!toVisit.empty()) {
      KStdVector<KRef> currentPath = std::move(toVisit.back());
      toVisit.pop_back();
      KRef node = currentPath[currentPath.size() - 1];
  
      if (node == root) {
        // Found a cycle.
        return currentPath;
      }
  
      // Already traversed this node.
      if (seen.count(node) != 0)
        continue;
      seen.insert(node);
  
      appendFieldsToVisit(node, currentPath);
    }
  
    return {};
  }
  
  template <typename C>
  OBJ_GETTER(createAndFillArray, const C& container) {
    auto* result = AllocArrayInstance(theArrayTypeInfo, container.size(), OBJ_RESULT)->array();
    KRef* place = ArrayAddressOfElementAt(result, 0);
    for (KRef it: container) {
      UpdateHeapRef(place++, it);
    }
    RETURN_OBJ(result->obj());
  }
  
  OBJ_GETTER0(detectCyclicReferences) {
    auto rootset = CycleDetector::collectRootset();
  
    KStdVector<KRef> cyclic;
  
    for (KRef root: rootset.roots) {
      if (!findCycleWithDFS(root, rootset).empty()) {
        cyclic.push_back(root);
      }
    }
  
    RETURN_RESULT_OF(createAndFillArray, cyclic);
  }
  
  OBJ_GETTER(findCycle, KRef root) {
    auto rootset = CycleDetector::collectRootset();
  
    auto cycle = findCycleWithDFS(root, rootset);
    if (cycle.empty()) {
      RETURN_OBJ(nullptr);
    }
    RETURN_RESULT_OF(createAndFillArray, cycle);
  }
  
  #endif  // USE_CYCLE_DETECTOR
  
  }  // namespace
  
  MetaObjHeader* ObjHeader::createMetaObject(ObjHeader* object) {
    TypeInfo** location = &object->typeInfoOrMeta_;
    TypeInfo* typeInfo = *location;
    RuntimeCheck(!hasPointerBits(typeInfo, OBJECT_TAG_MASK), "Object must not be tagged");
  
  #if !KONAN_NO_THREADS
    if (typeInfo->typeInfo_ != typeInfo) {
      // Someone installed a new meta-object since the check.
      return reinterpret_cast<MetaObjHeader*>(typeInfo);
    }
  #endif
  
    MetaObjHeader* meta = konanConstructInstance<MetaObjHeader>();
    meta->typeInfo_ = typeInfo;
  #if KONAN_NO_THREADS
    *location = reinterpret_cast<TypeInfo*>(meta);
  #else
    TypeInfo* old = __sync_val_compare_and_swap(location, typeInfo, reinterpret_cast<TypeInfo*>(meta));
    if (old != typeInfo) {
      // Someone installed a new meta-object since the check.
      konanFreeMemory(meta);
      meta = reinterpret_cast<MetaObjHeader*>(old);
    }
  #endif
    return meta;
  }
  
  void ObjHeader::destroyMetaObject(ObjHeader* object) {
    TypeInfo** location = &object->typeInfoOrMeta_;
    MetaObjHeader* meta = clearPointerBits(*(reinterpret_cast<MetaObjHeader**>(location)), OBJECT_TAG_MASK);
    *const_cast<const TypeInfo**>(location) = meta->typeInfo_;
    if (meta->WeakReference.counter_ != nullptr) {
      WeakReferenceCounterClear(meta->WeakReference.counter_);
      ZeroHeapRef(&meta->WeakReference.counter_);
    }
  
  #ifdef KONAN_OBJC_INTEROP
    Kotlin_ObjCExport_detachAndReleaseAssociatedObject(meta->associatedObject_);
  #endif
  
    konanFreeMemory(meta);
  }
  
  void ObjectContainer::Init(MemoryState* state, const TypeInfo* typeInfo) {
    RuntimeAssert(typeInfo->instanceSize_ >= 0, "Must be an object");
    uint32_t allocSize = sizeof(ContainerHeader) + typeInfo->instanceSize_;
    header_ = allocContainer(state, allocSize);
    RuntimeCheck(header_ != nullptr, "Cannot alloc memory");
    // One object in this container, no need to set.
    header_->setContainerSize(allocSize);
    RuntimeAssert(header_->objectCount() == 1, "Must work properly");
    // header->refCount_ is zero initialized by allocContainer().
    SetHeader(GetPlace(), typeInfo);
    OBJECT_ALLOC_EVENT(memoryState, typeInfo->instanceSize_, GetPlace())
  }
  
  void ArrayContainer::Init(MemoryState* state, const TypeInfo* typeInfo, uint32_t elements) {
    RuntimeAssert(typeInfo->instanceSize_ < 0, "Must be an array");
    uint32_t allocSize =
        sizeof(ContainerHeader) + arrayObjectSize(typeInfo, elements);
    header_ = allocContainer(state, allocSize);
    RuntimeCheck(header_ != nullptr, "Cannot alloc memory");
    // One object in this container, no need to set.
    header_->setContainerSize(allocSize);
    RuntimeAssert(header_->objectCount() == 1, "Must work properly");
    // header->refCount_ is zero initialized by allocContainer().
    GetPlace()->count_ = elements;
    SetHeader(GetPlace()->obj(), typeInfo);
    OBJECT_ALLOC_EVENT(memoryState, arrayObjectSize(typeInfo, elements), GetPlace()->obj())
  }
  
  // TODO: store arena containers in some reuseable data structure, similar to
  // finalizer queue.
  void ArenaContainer::Init() {
    allocContainer(1024);
  }
  
  void ArenaContainer::Deinit() {
    MEMORY_LOG("Arena::Deinit start: %p\n", this)
    auto chunk = currentChunk_;
    while (chunk != nullptr) {
      // freeContainer() doesn't release memory when CONTAINER_TAG_STACK is set.
      MEMORY_LOG("Arena::Deinit free chunk %p\n", chunk)
      freeContainer(chunk->asHeader());
      chunk = chunk->next;
    }
    chunk = currentChunk_;
    while (chunk != nullptr) {
      auto toRemove = chunk;
      chunk = chunk->next;
      konanFreeMemory(toRemove);
    }
  }
  
  bool ArenaContainer::allocContainer(container_size_t minSize) {
    auto size = minSize + sizeof(ContainerHeader) + sizeof(ContainerChunk);
    size = alignUp(size, kContainerAlignment);
    // TODO: keep simple cache of container chunks.
    ContainerChunk* result = konanConstructSizedInstance<ContainerChunk>(size);
    RuntimeCheck(result != nullptr, "Cannot alloc memory");
    if (result == nullptr) return false;
    result->next = currentChunk_;
    result->arena = this;
    result->asHeader()->refCount_ = (CONTAINER_TAG_STACK | CONTAINER_TAG_INCREMENT);
    currentChunk_ = result;
    current_ = reinterpret_cast<uint8_t*>(result->asHeader() + 1);
    end_ = reinterpret_cast<uint8_t*>(result) + size;
    return true;
  }
  
  void* ArenaContainer::place(container_size_t size) {
    size = alignUp(size, kObjectAlignment);
    // Fast path.
    if (current_ + size < end_) {
      void* result = current_;
      current_ += size;
      return result;
    }
    if (!allocContainer(size)) {
      return nullptr;
    }
    void* result = current_;
    current_ += size;
    RuntimeAssert(current_ <= end_, "Must not overflow");
    return result;
  }
  
  #define ARENA_SLOTS_CHUNK_SIZE 16
  
  ObjHeader** ArenaContainer::getSlot() {
    if (slots_ == nullptr || slotsCount_ >= ARENA_SLOTS_CHUNK_SIZE) {
      slots_ = PlaceArray(theArrayTypeInfo, ARENA_SLOTS_CHUNK_SIZE);
      slotsCount_ = 0;
    }
    return ArrayAddressOfElementAt(slots_, slotsCount_++);
  }
  
  ObjHeader* ArenaContainer::PlaceObject(const TypeInfo* type_info) {
    RuntimeAssert(type_info->instanceSize_ >= 0, "must be an object");
    uint32_t size = type_info->instanceSize_;
    ObjHeader* result = reinterpret_cast<ObjHeader*>(place(size));
    if (!result) {
      return nullptr;
    }
    OBJECT_ALLOC_EVENT(memoryState, type_info->instanceSize_, result)
    currentChunk_->asHeader()->incObjectCount();
    setHeader(result, type_info);
    return result;
  }
  
  ArrayHeader* ArenaContainer::PlaceArray(const TypeInfo* type_info, uint32_t count) {
    RuntimeAssert(type_info->instanceSize_ < 0, "must be an array");
    container_size_t size = arrayObjectSize(type_info, count);
    ArrayHeader* result = reinterpret_cast<ArrayHeader*>(place(size));
    if (!result) {
      return nullptr;
    }
    OBJECT_ALLOC_EVENT(memoryState, arrayObjectSize(type_info, count), result->obj())
    currentChunk_->asHeader()->incObjectCount();
    setHeader(result->obj(), type_info);
    result->count_ = count;
    return result;
  }
  
  // API of the memory manager.
  extern "C" {
  
  // Private memory interface.
  bool TryAddHeapRef(const ObjHeader* object) {
    return tryAddHeapRef(object);
  }
  
  RUNTIME_NOTHROW void ReleaseHeapRefStrict(const ObjHeader* object) {
    releaseHeapRef<true>(const_cast<ObjHeader*>(object));
  }
  RUNTIME_NOTHROW void ReleaseHeapRefRelaxed(const ObjHeader* object) {
    releaseHeapRef<false>(const_cast<ObjHeader*>(object));
  }
  
  RUNTIME_NOTHROW void ReleaseHeapRefNoCollectStrict(const ObjHeader* object) {
    releaseHeapRef<true, /* CanCollect = */ false>(const_cast<ObjHeader*>(object));
  }
  RUNTIME_NOTHROW void ReleaseHeapRefNoCollectRelaxed(const ObjHeader* object) {
    releaseHeapRef<false, /* CanCollect = */ false>(const_cast<ObjHeader*>(object));
  }
  
  RUNTIME_NOTHROW OBJ_GETTER(TryRef, ObjHeader* object) {
      RuntimeFail("Only for experimental MM");
  }
  
  ForeignRefContext InitLocalForeignRef(ObjHeader* object) {
    return initLocalForeignRef(object);
  }
  
  ForeignRefContext InitForeignRef(ObjHeader* object) {
    return initForeignRef(object);
  }
  
  void DeinitForeignRef(ObjHeader* object, ForeignRefContext context) {
    deinitForeignRef(object, context);
  }
  
  bool IsForeignRefAccessible(ObjHeader* object, ForeignRefContext context) {
    return isForeignRefAccessible(object, context);
  }
  
  void AdoptReferenceFromSharedVariable(ObjHeader* object) {
  #if USE_GC
    if (IsStrictMemoryModel() && object != nullptr && isShareable(containerFor(object)))
      rememberNewContainer(containerFor(object));
  #endif  // USE_GC
  }
  
  // Public memory interface.
  MemoryState* InitMemory(bool firstRuntime) {
      return initMemory(firstRuntime);
  }
  
  void DeinitMemory(MemoryState* memoryState, bool destroyRuntime) {
      deinitMemory(memoryState, destroyRuntime);
  }
  
  void RestoreMemory(MemoryState* memoryState) {
      RuntimeAssert((::memoryState == nullptr) || (::memoryState == memoryState), "Must not replace with unrelated memory state");
      ::memoryState = memoryState;
  }
  
  void ClearMemoryForTests(MemoryState*) {
      // Nothing to do, DeinitMemory will do the job.
  }
  
  RUNTIME_NOTHROW OBJ_GETTER(AllocInstanceStrict, const TypeInfo* type_info) {
    RETURN_RESULT_OF(allocInstance<true>, type_info);
  }
  RUNTIME_NOTHROW OBJ_GETTER(AllocInstanceRelaxed, const TypeInfo* type_info) {
    RETURN_RESULT_OF(allocInstance<false>, type_info);
  }
  
  OBJ_GETTER(AllocArrayInstanceStrict, const TypeInfo* typeInfo, int32_t elements) {
    RETURN_RESULT_OF(allocArrayInstance<true>, typeInfo, elements);
  }
  OBJ_GETTER(AllocArrayInstanceRelaxed, const TypeInfo* typeInfo, int32_t elements) {
    RETURN_RESULT_OF(allocArrayInstance<false>, typeInfo, elements);
  }
  
  OBJ_GETTER(InitThreadLocalSingletonStrict, ObjHeader** location, const TypeInfo* typeInfo, void (*ctor)(ObjHeader*)) {
      RETURN_RESULT_OF(initThreadLocalSingleton<true>, location, typeInfo, ctor);
  }
  OBJ_GETTER(InitThreadLocalSingletonRelaxed, ObjHeader** location, const TypeInfo* typeInfo, void (*ctor)(ObjHeader*)) {
      RETURN_RESULT_OF(initThreadLocalSingleton<false>, location, typeInfo, ctor);
  }
  
  OBJ_GETTER(InitSingletonStrict, ObjHeader** location, const TypeInfo* typeInfo, void (*ctor)(ObjHeader*)) {
      RETURN_RESULT_OF(initSingleton<true>, location, typeInfo, ctor);
  }
  OBJ_GETTER(InitSingletonRelaxed, ObjHeader** location, const TypeInfo* typeInfo, void (*ctor)(ObjHeader*)) {
      RETURN_RESULT_OF(initSingleton<false>, location, typeInfo, ctor);
  }
  
  void RUNTIME_NOTHROW InitAndRegisterGlobal(ObjHeader** location, const ObjHeader* initialValue) {
      RuntimeCheck(false, "Global registration is impossible in legacy MM");
  }
  
  RUNTIME_NOTHROW void SetStackRefStrict(ObjHeader** location, const ObjHeader* object) {
    setStackRef<true>(location, object);
  }
  RUNTIME_NOTHROW void SetStackRefRelaxed(ObjHeader** location, const ObjHeader* object) {
    setStackRef<false>(location, object);
  }
  
  RUNTIME_NOTHROW void SetHeapRefStrict(ObjHeader** location, const ObjHeader* object) {
    setHeapRef<true>(location, object);
  }
  RUNTIME_NOTHROW void SetHeapRefRelaxed(ObjHeader** location, const ObjHeader* object) {
    setHeapRef<false>(location, object);
  }
  
  RUNTIME_NOTHROW void ZeroHeapRef(ObjHeader** location) {
    zeroHeapRef(location);
  }
  
  RUNTIME_NOTHROW void ZeroStackRefStrict(ObjHeader** location) {
    zeroStackRef<true>(location);
  }
  RUNTIME_NOTHROW void ZeroStackRefRelaxed(ObjHeader** location) {
    zeroStackRef<false>(location);
  }
  
  RUNTIME_NOTHROW void UpdateStackRefStrict(ObjHeader** location, const ObjHeader* object) {
    updateStackRef<true>(location, object);
  }
  RUNTIME_NOTHROW void UpdateStackRefRelaxed(ObjHeader** location, const ObjHeader* object) {
    updateStackRef<false>(location, object);
  }
  
  RUNTIME_NOTHROW void UpdateHeapRefStrict(ObjHeader** location, const ObjHeader* object) {
    updateHeapRef<true>(location, object);
  }
  RUNTIME_NOTHROW void UpdateHeapRefRelaxed(ObjHeader** location, const ObjHeader* object) {
    updateHeapRef<false>(location, object);
  }
  
  RUNTIME_NOTHROW void UpdateHeapRefsInsideOneArrayStrict(const ArrayHeader* array, int fromIndex, int toIndex,
                                                          int count) {
    updateHeapRefsInsideOneArray<true>(array, fromIndex, toIndex, count);
  }
  RUNTIME_NOTHROW void UpdateHeapRefsInsideOneArrayRelaxed(const ArrayHeader* array, int fromIndex, int toIndex,
                                                           int count) {
    updateHeapRefsInsideOneArray<false>(array, fromIndex, toIndex, count);
  }
  
  RUNTIME_NOTHROW void UpdateReturnRefStrict(ObjHeader** returnSlot, const ObjHeader* value) {
    updateReturnRef<true>(returnSlot, value);
  }
  RUNTIME_NOTHROW void UpdateReturnRefRelaxed(ObjHeader** returnSlot, const ObjHeader* value) {
    updateReturnRef<false>(returnSlot, value);
  }
  
  RUNTIME_NOTHROW void ZeroArrayRefs(ArrayHeader* array) {
    for (uint32_t index = 0; index < array->count_; ++index) {
      ObjHeader** location = ArrayAddressOfElementAt(array, index);
      zeroHeapRef(location);
    }
  }
  
  RUNTIME_NOTHROW void UpdateHeapRefIfNull(ObjHeader** location, const ObjHeader* object) {
    updateHeapRefIfNull(location, object);
  }
  
  RUNTIME_NOTHROW OBJ_GETTER(SwapHeapRefLocked,
      ObjHeader** location, ObjHeader* expectedValue, ObjHeader* newValue, int32_t* spinlock, int32_t* cookie) {
    RETURN_RESULT_OF(swapHeapRefLocked, location, expectedValue, newValue, spinlock, cookie);
  }
  
  RUNTIME_NOTHROW void SetHeapRefLocked(ObjHeader** location, ObjHeader* newValue, int32_t* spinlock, int32_t* cookie) {
    setHeapRefLocked(location, newValue, spinlock, cookie);
  }
  
  RUNTIME_NOTHROW OBJ_GETTER(ReadHeapRefLocked, ObjHeader** location, int32_t* spinlock, int32_t* cookie) {
    RETURN_RESULT_OF(readHeapRefLocked, location, spinlock, cookie);
  }
  
  OBJ_GETTER(ReadHeapRefNoLock, ObjHeader* object, KInt index) {
    RETURN_RESULT_OF(readHeapRefNoLock, object, index);
  }
  
  RUNTIME_NOTHROW void EnterFrameStrict(ObjHeader** start, int parameters, int count) {
    enterFrame<true>(start, parameters, count);
  }
  RUNTIME_NOTHROW void EnterFrameRelaxed(ObjHeader** start, int parameters, int count) {
    enterFrame<false>(start, parameters, count);
  }
  
  RUNTIME_NOTHROW void LeaveFrameStrict(ObjHeader** start, int parameters, int count) {
    leaveFrame<true>(start, parameters, count);
  }
  RUNTIME_NOTHROW void LeaveFrameRelaxed(ObjHeader** start, int parameters, int count) {
    leaveFrame<false>(start, parameters, count);
  }
  
  RUNTIME_NOTHROW void SetCurrentFrameStrict(ObjHeader** start) {
      setCurrentFrame<true>(start);
  }
  RUNTIME_NOTHROW void SetCurrentFrameRelaxed(ObjHeader** start) {
      setCurrentFrame<false>(start);
  }
  
  void Kotlin_native_internal_GC_collect(KRef) {
  #if USE_GC
    garbageCollect();
  #endif
  }
  
  void Kotlin_native_internal_GC_collectCyclic(KRef) {
  #if USE_CYCLIC_GC
    if (g_hasCyclicCollector)
      cyclicScheduleGarbageCollect();
  #else
    ThrowIllegalArgumentException();
  #endif
  }
  
  void Kotlin_native_internal_GC_suspend(KRef) {
  #if USE_GC
    suspendGC();
  #endif
  }
  
  void Kotlin_native_internal_GC_resume(KRef) {
  #if USE_GC
    resumeGC();
  #endif
  }
  
  void Kotlin_native_internal_GC_stop(KRef) {
  #if USE_GC
    stopGC();
  #endif
  }
  
  void Kotlin_native_internal_GC_start(KRef) {
  #if USE_GC
    startGC();
  #endif
  }
  
  void Kotlin_native_internal_GC_setThreshold(KRef, KInt value) {
  #if USE_GC
    setGCThreshold(value);
  #endif
  }
  
  KInt Kotlin_native_internal_GC_getThreshold(KRef) {
  #if USE_GC
    return getGCThreshold();
  #else
    return -1;
  #endif
  }
  
  void Kotlin_native_internal_GC_setCollectCyclesThreshold(KRef, KLong value) {
  #if USE_GC
    setGCCollectCyclesThreshold(value);
  #endif
  }
  
  KLong Kotlin_native_internal_GC_getCollectCyclesThreshold(KRef) {
  #if USE_GC
    return getGCCollectCyclesThreshold();
  #else
    return -1;
  #endif
  }
  
  void Kotlin_native_internal_GC_setThresholdAllocations(KRef, KLong value) {
  #if USE_GC
    setGCThresholdAllocations(value);
  #endif
  }
  
  KLong Kotlin_native_internal_GC_getThresholdAllocations(KRef) {
  #if USE_GC
    return getGCThresholdAllocations();
  #else
    return -1;
  #endif
  }
  
  void Kotlin_native_internal_GC_setTuneThreshold(KRef, KBoolean value) {
  #if USE_GC
    setTuneGCThreshold(value);
  #endif
  }
  
  KBoolean Kotlin_native_internal_GC_getTuneThreshold(KRef) {
  #if USE_GC
    return getTuneGCThreshold();
  #else
    return false;
  #endif
  }
  
  OBJ_GETTER(Kotlin_native_internal_GC_detectCycles, KRef) {
  #if USE_CYCLE_DETECTOR
    if (!kotlin::compiler::shouldContainDebugInfo() && !Kotlin_memoryLeakCheckerEnabled()) RETURN_OBJ(nullptr);
    RETURN_RESULT_OF0(detectCyclicReferences);
  #else
    RETURN_OBJ(nullptr);
  #endif
  }
  
  OBJ_GETTER(Kotlin_native_internal_GC_findCycle, KRef, KRef root) {
  #if USE_CYCLE_DETECTOR
    RETURN_RESULT_OF(findCycle, root);
  #else
    RETURN_OBJ(nullptr);
  #endif
  }
  
  RUNTIME_NOTHROW KNativePtr CreateStablePointer(KRef any) {
    return createStablePointer(any);
  }
  
  RUNTIME_NOTHROW void DisposeStablePointer(KNativePtr pointer) {
    disposeStablePointer(pointer);
  }
  
  RUNTIME_NOTHROW void DisposeStablePointerFor(MemoryState* memoryState, KNativePtr pointer) {
    DisposeStablePointer(pointer);
  }
  
  RUNTIME_NOTHROW OBJ_GETTER(DerefStablePointer, KNativePtr pointer) {
    RETURN_RESULT_OF(derefStablePointer, pointer);
  }
  
  RUNTIME_NOTHROW OBJ_GETTER(AdoptStablePointer, KNativePtr pointer) {
    RETURN_RESULT_OF(adoptStablePointer, pointer);
  }
  
  RUNTIME_NOTHROW bool ClearSubgraphReferences(ObjHeader* root, bool checked) {
    return clearSubgraphReferences(root, checked);
  }
  
  void FreezeSubgraph(ObjHeader* root) {
    freezeSubgraph(root);
  }
  
  // This function is called from field mutators to check if object's header is frozen.
  // If object is frozen or permanent, an exception is thrown.
  void MutationCheck(ObjHeader* obj) {
    if (obj->local()) return;
    auto* container = containerFor(obj);
    if (container == nullptr || container->frozen())
      ThrowInvalidMutabilityException(obj);
  }
  
  RUNTIME_NOTHROW void CheckLifetimesConstraint(ObjHeader* obj, ObjHeader* pointee) {
    if (!obj->local() && pointee != nullptr && pointee->local()) {
      konan::consolePrintf("Attempt to store a stack object %p into a heap object %p\n", pointee, obj);
      konan::consolePrintf("This is a compiler bug, please report it to https://kotl.in/issue\n");
      konan::abort();
    }
  }
  
  void EnsureNeverFrozen(ObjHeader* object) {
    ensureNeverFrozen(object);
  }
  
  void Kotlin_Any_share(ObjHeader* obj) {
    shareAny(obj);
  }
  
  RUNTIME_NOTHROW void AddTLSRecord(MemoryState* memory, void** key, int size) {
      memory->tls.Add(key, size);
  }
  
  RUNTIME_NOTHROW void CommitTLSStorage(MemoryState* memory) {
      memory->tls.Commit();
  }
  
  RUNTIME_NOTHROW void ClearTLS(MemoryState* memory) {
      memory->tls.Clear();
  }
  
  RUNTIME_NOTHROW KRef* LookupTLS(void** key, int index) {
      return memoryState->tls.Lookup(key, index);
  }
  
  
  RUNTIME_NOTHROW void GC_RegisterWorker(void* worker) {
  #if USE_CYCLIC_GC
    cyclicAddWorker(worker);
  #endif  // USE_CYCLIC_GC
  }
  
  RUNTIME_NOTHROW FrameOverlay* getCurrentFrame() {
      return currentFrame;
  }
  
  ALWAYS_INLINE RUNTIME_NOTHROW void CheckCurrentFrame(ObjHeader** frame) {
      FrameOverlay* expectedFrame = reinterpret_cast<FrameOverlay*>(frame);
      RuntimeAssert(currentFrame == expectedFrame, "Frame is expected to be %p, but current frame is %p", expectedFrame, currentFrame);
  }
  
  RUNTIME_NOTHROW void GC_UnregisterWorker(void* worker) {
  #if USE_CYCLIC_GC
    cyclicRemoveWorker(worker, g_hasCyclicCollector);
  #endif  // USE_CYCLIC_GC
  }
  
  RUNTIME_NOTHROW void GC_CollectorCallback(void* worker) {
  #if USE_CYCLIC_GC
    if (g_hasCyclicCollector)
      cyclicCollectorCallback(worker);
  #endif   // USE_CYCLIC_GC
  }
  
  KBoolean Kotlin_native_internal_GC_getCyclicCollector(KRef gc) {
  #if USE_CYCLIC_GC
    return g_hasCyclicCollector;
  #else
    return false;
  #endif  // USE_CYCLIC_GC
  }
  
  void Kotlin_native_internal_GC_setCyclicCollector(KRef gc, KBoolean value) {
  #if USE_CYCLIC_GC
    g_hasCyclicCollector = value;
  #else
    if (value)
      ThrowIllegalArgumentException();
  #endif  // USE_CYCLIC_GC
  }
  
  bool Kotlin_Any_isShareable(KRef thiz) {
      return thiz == nullptr || isShareable(containerFor(thiz));
  }
  
  RUNTIME_NOTHROW void PerformFullGC(MemoryState* memory) {
      garbageCollect(memory, true);
  }
  
  void CheckGlobalsAccessible() {
      if (!::memoryState->isMainThread)
          ThrowIncorrectDereferenceException();
  }
  
  ALWAYS_INLINE RUNTIME_NOTHROW void Kotlin_mm_switchThreadStateNative() {
      // no-op, used by the new MM only.
  }
  
  ALWAYS_INLINE RUNTIME_NOTHROW void Kotlin_mm_switchThreadStateRunnable() {
      // no-op, used by the new MM only.
  }
  
  ALWAYS_INLINE RUNTIME_NOTHROW void Kotlin_mm_safePointFunctionPrologue() {
      // no-op, used by the new MM only.
  }
  
  ALWAYS_INLINE RUNTIME_NOTHROW void Kotlin_mm_safePointWhileLoopBody() {
      // no-op, used by the new MM only.
  }
  
  } // extern "C"
  
  #if !KONAN_NO_EXCEPTIONS
  // static
  ALWAYS_INLINE RUNTIME_NORETURN void ExceptionObjHolder::Throw(ObjHeader* exception) {
      throw ExceptionObjHolderImpl(exception);
  }
  
  ALWAYS_INLINE ObjHeader* ExceptionObjHolder::GetExceptionObject() noexcept {
      return static_cast<ExceptionObjHolderImpl*>(this)->obj();
  }
  #endif
  
  ALWAYS_INLINE kotlin::ThreadState kotlin::SwitchThreadState(MemoryState* thread, ThreadState newState, bool reentrant) noexcept {
      // no-op, used by the new MM only.
      return ThreadState::kRunnable;
  }
  
  ALWAYS_INLINE void kotlin::AssertThreadState(MemoryState* thread, ThreadState expected) noexcept {
      // no-op, used by the new MM only.
  }
  
  ALWAYS_INLINE void kotlin::AssertThreadState(MemoryState* thread, std::initializer_list<ThreadState> expected) noexcept {
      // no-op, used by the new MM only.
  }
  
  MemoryState* kotlin::mm::GetMemoryState() noexcept {
      return ::memoryState;
  }
  
  bool kotlin::mm::IsCurrentThreadRegistered() noexcept {
      return ::memoryState != nullptr;
  }
  
  kotlin::ThreadState kotlin::GetThreadState(MemoryState* thread) noexcept {
      // Assume that we are always in the Runnable thread state.
      return ThreadState::kRunnable;
  }
  
  ALWAYS_INLINE kotlin::CalledFromNativeGuard::CalledFromNativeGuard(bool reentrant) noexcept {
      // no-op, used by the new MM only.
  }
  
  const bool kotlin::kSupportsMultipleMutators = true;
  