/*

 * Copyright (c) 2016-2017  Moddable Tech, Inc.

 *

 *   This file is part of the Moddable SDK Runtime.

 * 

 *   The Moddable SDK Runtime is free software: you can redistribute it and/or modify

 *   it under the terms of the GNU Lesser General Public License as published by

 *   the Free Software Foundation, either version 3 of the License, or

 *   (at your option) any later version.

 * 

 *   The Moddable SDK Runtime is distributed in the hope that it will be useful,

 *   but WITHOUT ANY WARRANTY; without even the implied warranty of

 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 *   GNU Lesser General Public License for more details.

 * 

 *   You should have received a copy of the GNU Lesser General Public License

 *   along with the Moddable SDK Runtime.  If not, see <http://www.gnu.org/licenses/>.

 *

 * This file incorporates work covered by the following copyright and  

 * permission notice:  

 *

 *       Copyright (C) 2010-2016 Marvell International Ltd.

 *       Copyright (C) 2002-2010 Kinoma, Inc.

 *

 *       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 "xsAll.h"

#ifndef mxReport

#define mxReport 0

#endif

#ifndef mxStress

#define mxStress 0

#endif

#ifndef mxNoChunks

#define mxNoChunks 0

#endif

#ifndef mxPoisonSlots

#define mxPoisonSlots 0

#endif

#if mxPoisonSlots

#include <sanitizer/asan_interface.h>

#endif

#if mxStress

int gxStress = 0;

static int fxShouldStress()

{

  if (!gxStress)

    return 0;

  if (gxStress > 0)

    return 1;

  gxStress += 1;

  return 0 == gxStress;

}

#endif

#if mxNoChunks

  #if FUZZING

    extern void *fxMemMalloc_noforcefail(size_t size);

    #define c_malloc_noforcefail(size) fxMemMalloc_noforcefail(size)

  #else

    #define c_malloc_noforcefail c_malloc

  #endif

#endif

#define mxChunkFlag 0x80000000

static txSize fxAdjustChunkSize(txMachine* the, txSize size);

static void* fxCheckChunk(txMachine* the, txChunk* chunk, txSize size, txSize offset);

static void* fxFindChunk(txMachine* the, txSize size, txBoolean *once);

static void* fxGrowChunk(txMachine* the, txSize size);

static void* fxGrowChunks(txMachine* the, txSize theSize); 

/* static */ void fxGrowSlots(txMachine* the, txSize theCount); 

static void fxMark(txMachine* the, void (*theMarker)(txMachine*, txSlot*));

#if mxKeysGarbageCollection

static void fxMarkID(txMachine* the, txID id);

#endif

static void fxMarkFinalizationRegistry(txMachine* the, txSlot* registry);

static void fxMarkInstance(txMachine* the, txSlot* theCurrent, void (*theMarker)(txMachine*, txSlot*));

static void fxMarkReference(txMachine* the, txSlot* theSlot);

static void fxMarkValue(txMachine* the, txSlot* theSlot);

static void fxMarkWeakStuff(txMachine* the);

static void fxSweep(txMachine* the);

static void fxSweepValue(txMachine* the, txSlot* theSlot);

#ifdef mxNever

typedef struct sxSample txSample;

struct sxSample {

  struct timespec time;

  txNumber duration;

  long count;

  char* label;

};

void reportTime(txSample* theSample) 

{

  fprintf(stderr, " %s %ld %f", theSample->label, theSample->count, theSample->duration); 

}

void startTime(txSample* theSample) 

{

  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &(theSample->time));

}

void stopTime(txSample* theSample) 

{

  struct timespec time;

  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time);

  theSample->duration += ((double)(time.tv_sec) - (double)(theSample->time.tv_sec))

      + (((double)(time.tv_nsec) - (double)(theSample->time.tv_nsec)) / 1000000000.0);

  theSample->count++;

}

txSample gxLifeTime = { { 0, 0 }, 0, 0, "life" };

txSample gxMarkTime = { { 0, 0 }, 0, 0, "mark" };

txSample gxSweepChunkTime = { { 0, 0 }, 0, 0, "sweep chunk" };

txSample gxSweepSlotTime = { { 0, 0 }, 0, 0, "sweep slot" };

txSample gxCompactChunkTime = { { 0, 0 }, 0, 0, "compact" };

txSample gxChunksGarbageCollectionTime = { { 0, 0 }, 0, 0, "chunks" };

txSample gxKeysGarbageCollectionTime = { { 0, 0 }, 0, 0, "keys" };

txSample gxSlotsGarbageCollectionTime = { { 0, 0 }, 0, 0, "slots" };

txSample gxForcedGarbageCollectionTime = { { 0, 0 }, 0, 0, "forced" };

#endif

txSize fxAddChunkSizes(txMachine* the, txSize a, txSize b)

{

  txSize c;

#if __has_builtin(__builtin_add_overflow)

  if (__builtin_add_overflow(a, b, &c)) {

#else

  c = a + b;

  if (((a ^ c) & (b ^ c)) < 0) {

#endif

    fxAbort(the, XS_NOT_ENOUGH_MEMORY_EXIT);

  }

  return c;

}

txSize fxAdjustChunkSize(txMachine* the, txSize size)

{

  txSize adjust = sizeof(txChunk);

  txSize modulo = size & (sizeof(size_t) - 1);

  if (modulo)

    adjust += sizeof(size_t) - modulo;

  return fxAddChunkSizes(the, size, adjust);

}

void fxAllocate(txMachine* the, txCreation* theCreation)

{

#ifdef mxNever

  startTime(&gxLifeTime);

#endif

#if mxStress

  gxStress = 0;

#endif

  the->currentChunksSize = 0;

  the->peakChunksSize = 0;

  the->maximumChunksSize = 0;

  the->minimumChunksSize = theCreation->incrementalChunkSize;

  the->currentHeapCount = 0;

  the->peakHeapCount = 0;

  the->maximumHeapCount = 0;

  the->minimumHeapCount = theCreation->incrementalHeapCount;

  the->firstBlock = C_NULL;

  the->firstHeap = C_NULL;

#if mxNoChunks

  the->maximumChunksSize = theCreation->initialChunkSize;

#else

  fxGrowChunks(the, theCreation->initialChunkSize);

#endif

  the->stackBottom = fxAllocateSlots(the, theCreation->stackCount);

  the->stackTop = the->stackBottom + theCreation->stackCount;

  the->stackIntrinsics = the->stackTop;

  the->stackPrototypes = the->stackTop - XS_INTRINSICS_COUNT;

  the->stack = the->stackTop;

#ifdef mxInstrument

  the->stackPeak = the->stackTop;

#endif

  fxGrowSlots(the, theCreation->initialHeapCount);

  the->keyCount = (txID)theCreation->initialKeyCount;

  the->keyDelta = (txID)theCreation->incrementalKeyCount;

  the->keyIndex = 0;

  the->keyArray = (txSlot **)c_malloc_uint32(theCreation->initialKeyCount * sizeof(txSlot*));

  if (!the->keyArray)

    fxAbort(the, XS_NOT_ENOUGH_MEMORY_EXIT);   

  the->nameModulo = theCreation->nameModulo;

  the->nameTable = (txSlot **)c_malloc_uint32(theCreation->nameModulo * sizeof(txSlot*));

  if (!the->nameTable)

    fxAbort(the, XS_NOT_ENOUGH_MEMORY_EXIT);

  the->symbolModulo = theCreation->symbolModulo;

  the->symbolTable = (txSlot **)c_malloc_uint32(theCreation->symbolModulo * sizeof(txSlot*));

  if (!the->symbolTable)

    fxAbort(the, XS_NOT_ENOUGH_MEMORY_EXIT);

  fxAllocateStringInfoCache(the);

  the->stackLimit = fxCStackLimit();

  the->cRoot = C_NULL;

  the->parserBufferSize = theCreation->parserBufferSize;

  the->parserTableModulo = theCreation->parserTableModulo;

#ifdef mxDebug

  the->pathCount = 256;

  the->pathValue = c_malloc(the->pathCount);

  if (!the->pathValue)

    fxAbort(the, XS_NOT_ENOUGH_MEMORY_EXIT);

#endif

}

void* fxCheckChunk(txMachine* the, txChunk* chunk, txSize size, txSize offset)

{

  if (chunk) {

    txByte* data = (txByte*)chunk;

#if mxNoChunks

    chunk->size = size;

    the->currentChunksSize += size;

#else

    txSize capacity = (txSize)(chunk->temporary - data);

  #ifdef mxSnapshot

    #if INTPTR_MAX == INT64_MAX

      chunk->dummy = 0;

    #endif

  #ifdef mxSnapshotRandomInit

    arc4random_buf(data + sizeof(txChunk), offset);

  #endif    

  #endif

    offset += sizeof(txChunk);

    c_memset(data + offset, 0, capacity - offset);

    chunk->size = size;

    the->currentChunksSize += capacity;

#endif

    if (the->peakChunksSize < the->currentChunksSize)

      the->peakChunksSize = the->currentChunksSize;

    return data + sizeof(txChunk);

  }

  fxReport(the, "# Chunk allocation: failed for %ld bytes\n", (long)size);

  fxAbort(the, XS_NOT_ENOUGH_MEMORY_EXIT);

  return C_NULL;

}

#if defined(__clang__) || defined (__GNUC__)

  __attribute__((no_sanitize_address))

#endif

void fxCheckCStack(txMachine* the)

{

    char x;

    char *stack = &x;

  if (stack <= the->stackLimit) {

    fxAbort(the, XS_NATIVE_STACK_OVERFLOW_EXIT);

  }

}

void fxCollect(txMachine* the, txFlag theFlag)

{

  txSize aCount;

  txSlot* freeSlot;

  txSlot* aSlot;

  txSlot* bSlot;

  txSlot* cSlot;

  if ((the->collectFlag & XS_COLLECTING_FLAG) == 0) {

    the->collectFlag |= XS_SKIPPED_COLLECT_FLAG;

    return;

  }

  the->collectFlag |= theFlag & (XS_COLLECT_KEYS_FLAG | XS_ORGANIC_FLAG);

#ifdef mxNever

  if (theFlag & XS_ORGANIC_FLAG) {

    if (theFlag & XS_COMPACT_FLAG)

      startTime(&gxChunksGarbageCollectionTime);

    else if (theFlag & XS_COLLECT_KEYS_FLAG)

      startTime(&gxKeysGarbageCollectionTime);

    else

      startTime(&gxSlotsGarbageCollectionTime);

  }

  else

    startTime(&gxForcedGarbageCollectionTime);

  startTime(&gxMarkTime);

#endif

  if (theFlag & XS_COMPACT_FLAG) {

    fxInvalidateStringInfoCache(the);

    fxMark(the, fxMarkValue);

    fxMarkWeakStuff(the);

  #ifdef mxNever

    stopTime(&gxMarkTime);

  #endif

    fxSweep(the);

  }

  else {

    fxMark(the, fxMarkReference);

    fxMarkWeakStuff(the);

  #ifdef mxNever

    stopTime(&gxMarkTime);

    startTime(&gxSweepSlotTime);

  #endif

    aCount = 0;

    freeSlot = C_NULL;

    aSlot = the->firstHeap;

    while (aSlot) {

      bSlot = aSlot + 1;

      cSlot = aSlot->value.reference;

      while (bSlot < cSlot) {

        if (bSlot->flag & XS_MARK_FLAG) {

          bSlot->flag &= ~XS_MARK_FLAG; 

          if (bSlot->kind == XS_REFERENCE_KIND) {

            mxCheck(the, bSlot->value.reference->kind == XS_INSTANCE_KIND);

          }

          aCount++;

        }

        else {

          if (bSlot->kind == XS_HOST_KIND) {

            if (bSlot->flag & XS_HOST_HOOKS_FLAG) {

              if (bSlot->value.host.variant.hooks->destructor)

                (*(bSlot->value.host.variant.hooks->destructor))(bSlot->value.host.data);

            }

            else if (bSlot->value.host.variant.destructor)

              (*(bSlot->value.host.variant.destructor))(bSlot->value.host.data);

          }

        #if mxInstrument

          if ((bSlot->kind == XS_MODULE_KIND) && (bSlot->ID == XS_MODULE_BEHAVIOR))

            the->loadedModulesCount--;

        #endif

          bSlot->kind = XS_UNDEFINED_KIND;

          bSlot->next = freeSlot;

        #if mxPoisonSlots

          ASAN_POISON_MEMORY_REGION(&bSlot->value, sizeof(bSlot->value));

        #endif

          freeSlot = bSlot;

        }

        bSlot++;

      }

      aSlot = aSlot->next;

    }

    the->currentHeapCount = aCount;

    the->freeHeap = freeSlot;

  #ifdef mxNever

    stopTime(&gxSweepSlotTime);

  #endif

  }

  aSlot = the->stack;

  while (aSlot < the->stackTop) {

    aSlot->flag &= ~XS_MARK_FLAG; 

    aSlot++;

  }

  the->collectFlag &= ~(XS_COLLECT_KEYS_FLAG | XS_ORGANIC_FLAG);

  if (theFlag & XS_COMPACT_FLAG) {

    if ((the->maximumChunksSize - the->currentChunksSize) < the->minimumChunksSize)

      the->collectFlag |= XS_TRASHING_CHUNKS_FLAG;

    else

      the->collectFlag &= ~XS_TRASHING_CHUNKS_FLAG;

  }

  if ((the->maximumHeapCount - the->currentHeapCount) < the->minimumHeapCount)

    the->collectFlag |= XS_TRASHING_SLOTS_FLAG;

  else

    the->collectFlag &= ~XS_TRASHING_SLOTS_FLAG;

#ifdef mxNever

  if (theFlag & XS_ORGANIC_FLAG) {

    if (theFlag & XS_COMPACT_FLAG)

      stopTime(&gxChunksGarbageCollectionTime);

    else if (theFlag & XS_COLLECT_KEYS_FLAG)

      stopTime(&gxKeysGarbageCollectionTime);

    else

      stopTime(&gxSlotsGarbageCollectionTime);

  }

  else

    stopTime(&gxForcedGarbageCollectionTime);

#endif

#if mxReport

  if (theFlag)

    fxReport(the, "# Chunk collection: reserved %ld used %ld peak %ld bytes\n", 

      (long)the->maximumChunksSize, (long)the->currentChunksSize, (long)the->peakChunksSize);

  aCount = 0;

  aSlot = the->firstHeap;

  while (aSlot) {

    aCount++;

    aSlot = aSlot->next;

  }

  fxReport(the, "# Slot collection: reserved %ld used %ld peak %ld bytes %d\n",

    (long)((the->maximumHeapCount - aCount) * sizeof(txSlot)),

    (long)(the->currentHeapCount * sizeof(txSlot)),

    (long)(the->peakHeapCount * sizeof(txSlot)),

    the->collectFlag & XS_TRASHING_SLOTS_FLAG);

#endif

#ifdef mxInstrument

  the->garbageCollectionCount++;

#endif

#if defined(mxInstrument) || defined(mxProfile)

  fxCheckProfiler(the, C_NULL);

#endif

}

txSlot* fxDuplicateSlot(txMachine* the, txSlot* theSlot)

{

  txSlot* result;

  result = fxNewSlot(the);

  result->ID = theSlot->ID;

  result->kind = theSlot->kind;

  result->flag = theSlot->flag & ~XS_MARK_FLAG;

  result->value = theSlot->value;

  return result;

}

void* fxFindChunk(txMachine* the, txSize size, txBoolean *once)

{

  txBlock* block;

  txChunk* chunk;

#if mxStress

  if (fxShouldStress()) {

    if (*once) {

      fxCollect(the, XS_COMPACT_FLAG | XS_ORGANIC_FLAG);

      *once = 0;

    }

  }

#endif

#if mxNoChunks

  if ((the->currentChunksSize + size > the->maximumChunksSize)) {

    fxCollect(the, XS_COMPACT_FLAG | XS_ORGANIC_FLAG);

    if (the->collectFlag & XS_TRASHING_CHUNKS_FLAG)

      the->maximumChunksSize += the->minimumChunksSize;

  }

  chunk = c_malloc_noforcefail(size);

  if (!chunk)

    fxAbort(the, XS_NOT_ENOUGH_MEMORY_EXIT);

  chunk->size = size;

  chunk->temporary = (txByte*)the->firstBlock;

  the->firstBlock = (txBlock*)chunk;

  return chunk;

#endif

again:

  block = the->firstBlock;

  while (block) {

    if ((block->current + size) <= block->limit) {

      chunk = (txChunk*)(block->current);

      block->current += size;

      chunk->temporary = block->current;

      return chunk;

    }

    block = block->nextBlock;

  }

  if (*once) {

    txBoolean wasThrashing = ((the->collectFlag & XS_TRASHING_CHUNKS_FLAG) != 0), isThrashing;

    fxCollect(the, XS_COMPACT_FLAG | XS_ORGANIC_FLAG);

    isThrashing = ((the->collectFlag & XS_TRASHING_CHUNKS_FLAG) != 0);

    *once = 0;

    if (wasThrashing && isThrashing)

      return C_NULL;

    goto again;

  }

  return C_NULL;

}

txSlot* fxFindKey(txMachine* the)

{

#if mxKeysGarbageCollection

  txBoolean once = 1;

#endif

  txID id;

  txSlot* result;

more:

  id = the->keyIndex;

  if (id < the->keyCount) {

    result = fxNewSlot(the);

    result->ID = id;

    the->keyArray[id - the->keyOffset] = result;

    the->keyIndex++;

    return result;

  }

#if mxKeysGarbageCollection

again:

  result = the->keyholeList;

  if (result) {

    the->keyholeCount--;

    the->keyholeList = result->next;

    result->next = C_NULL;

    return result;

  }

  if (once) {

    fxCollect(the, XS_COLLECT_KEYS_FLAG | XS_ORGANIC_FLAG);

    once = 0;

    goto again;

  }

#endif

  else {

    fxGrowKeys(the, 1);

    goto more;

  }

  return C_NULL;

}

void fxFree(txMachine* the) 

{

  txSlot* aHeap;

#if mxAliasInstance

  if (the->aliasArray)

    c_free_uint32(the->aliasArray);

  the->aliasArray = C_NULL;

#endif

  fxFreeStringInfoCache(the);

  if (the->symbolTable)

    c_free_uint32(the->symbolTable);

  the->symbolTable = C_NULL;

  if (the->nameTable)

    c_free_uint32(the->nameTable);

  the->nameTable = C_NULL;

  if (the->keyArray)

    c_free_uint32(the->keyArray);

  the->keyArray = C_NULL;

  while (the->firstHeap) {

    aHeap = the->firstHeap;

    the->firstHeap = aHeap->next;

    fxFreeSlots(the, aHeap);

  }

  the->firstHeap = C_NULL;

  if (the->stackBottom)

    fxFreeSlots(the, the->stackBottom);

  the->stackBottom = C_NULL;

  the->stackTop = C_NULL;

  the->stackIntrinsics = C_NULL;

  the->stackPrototypes = C_NULL;

  the->stack = C_NULL;

#if mxNoChunks

  {

    txChunk** address;

    txChunk* chunk;

    address = (txChunk**)&(the->firstBlock);

    while ((chunk = *address)) {

      *address = (txChunk*)(chunk->temporary);

      c_free(chunk);

    }

  }

#else

  {

    txBlock* aBlock;

    while (the->firstBlock) {

      aBlock = the->firstBlock;

      the->firstBlock = aBlock->nextBlock;

      fxFreeChunks(the, aBlock);

    }

    the->firstBlock = C_NULL;

  }

#endif

#ifdef mxDebug

  if (the->pathValue)

    c_free(the->pathValue);

  the->pathValue = C_NULL;

#endif

#ifdef mxNever

  stopTime(&gxLifeTime);

//  fprintf(stderr, "###");

//  reportTime(&gxLifeTime);

//  reportTime(&gxForcedGarbageCollectionTime);

//  reportTime(&gxChunksGarbageCollectionTime);

//  reportTime(&gxKeysGarbageCollectionTime);

//  reportTime(&gxSlotsGarbageCollectionTime);

//  reportTime(&gxMarkTime);

//  reportTime(&gxSweepChunkTime);

//  reportTime(&gxSweepSlotTime);

//  reportTime(&gxCompactChunkTime);

//  fprintf(stderr, "\n");

#endif

}

void* fxGrowChunk(txMachine* the, txSize size) 

{

  txBlock* block = fxGrowChunks(the, size);

  txChunk* chunk = C_NULL;

  if (block) {

    chunk = (txChunk*)(block->current);

    block->current += size;

    chunk->temporary = block->current;

  }

  return chunk;

}

void* fxGrowChunks(txMachine* the, txSize size) 

{

  txByte* buffer;

  txBlock* block = C_NULL;

  if (!the->minimumChunksSize && the->firstBlock) {

    fxReport(the, "# Chunk allocation: %d bytes failed in fixed size heap\n", size);

    fxAbort(the, XS_NOT_ENOUGH_MEMORY_EXIT);

  }

  if ((the->firstBlock != C_NULL) && (!(the->collectFlag & XS_SKIPPED_COLLECT_FLAG))) {

    txSize modulo = size % (the->minimumChunksSize ? the->minimumChunksSize : 16);

    if (modulo)

      size = fxAddChunkSizes(the, size, the->minimumChunksSize - modulo);

  }

  size = fxAddChunkSizes(the, size, sizeof(txBlock));

  buffer = fxAllocateChunks(the, size);

  if (buffer) {

  #ifdef mxSnapshot

    c_memset(buffer, 0, size);

  #endif

    if ((the->firstBlock != C_NULL) && (the->firstBlock->limit == buffer)) {

      the->firstBlock->limit += size;

      block = the->firstBlock;

    }

    else {

      block = (txBlock*)buffer;

      block->nextBlock = the->firstBlock;

      block->current = buffer + sizeof(txBlock);

      block->limit = buffer + size;

      block->temporary = C_NULL;

      the->firstBlock = block;

      size -= sizeof(txBlock);

    }

    the->maximumChunksSize = fxAddChunkSizes(the, the->maximumChunksSize, size);

  #if mxReport

    fxReport(the, "# Chunk allocation: reserved %ld used %ld peak %ld bytes\n", 

      (long)the->maximumChunksSize, (long)the->currentChunksSize, (long)the->peakChunksSize);

  #endif

  }

  the->collectFlag &= ~XS_TRASHING_CHUNKS_FLAG;

  return block;

}

void fxGrowKeys(txMachine* the, txID theCount) 

{

  if (the->keyDelta > 0) {

    txID keyDelta = (theCount > the->keyDelta) ? theCount : the->keyDelta;

    txID keyCount = (the->keyCount + keyDelta) - the->keyOffset;

    txSlot** keyArray = c_realloc(the->keyArray, keyCount * sizeof(txSlot*));

    if (keyArray == C_NULL)

      fxAbort(the, XS_NOT_ENOUGH_MEMORY_EXIT);

    the->keyArray = keyArray;

    the->keyCount = keyCount + the->keyOffset;

  }

  else 

    fxAbort(the, XS_NO_MORE_KEYS_EXIT);

}

void fxGrowSlots(txMachine* the, txSize theCount) 

{

  txSlot* aHeap;

  txSlot* aSlot;

  aHeap = fxAllocateSlots(the, theCount);

  if (!aHeap) {

    fxReport(the, "# Slot allocation: failed for %ld bytes\n", theCount * sizeof(txSlot));

    fxAbort(the, XS_NOT_ENOUGH_MEMORY_EXIT);

  }

  if ((void *)-1 == aHeap)

    return;

  if (the->firstHeap && the->growHeapDirection) {

    if (the->growHeapDirection > 0) {

      the->firstHeap->value.reference = aHeap + theCount;

      the->maximumHeapCount += theCount;    

      theCount -= 1;

      aSlot = aHeap;

    }

    else {

      *aHeap = *(the->firstHeap);

      the->maximumHeapCount += theCount;

      theCount -= 1;

      the->firstHeap = aHeap;

      aSlot = aHeap + 1;

    }

  }

  else {

    the->maximumHeapCount += theCount - 1;

    aHeap->next = the->firstHeap;

    aHeap->ID = 0;

    aHeap->flag = 0;

    aHeap->kind = 0;

    aHeap->value.reference = aHeap + theCount;

    theCount -= 2;

    the->firstHeap = aHeap;

    aSlot = aHeap + 1;

  }

    while (theCount--) {

    txSlot* next = aSlot + 1;

    aSlot->next = next;

    aSlot->flag = XS_NO_FLAG;

    aSlot->kind = XS_UNDEFINED_KIND;

  #if mxPoisonSlots

    ASAN_POISON_MEMORY_REGION(&aSlot->value, sizeof(aSlot->value));

  #endif

        aSlot = next;

    }

  aSlot->next = the->freeHeap;

  aSlot->flag = XS_NO_FLAG;

  aSlot->kind = XS_UNDEFINED_KIND;

#if mxPoisonSlots

  ASAN_POISON_MEMORY_REGION(&aSlot->value, sizeof(aSlot->value));

#endif

  the->freeHeap = aHeap + 1;

  the->collectFlag &= ~XS_TRASHING_SLOTS_FLAG;

#if mxReport

  fxReport(the, "# Slot allocation: reserved %ld used %ld peak %ld bytes\n", 

    (long)(the->maximumHeapCount * sizeof(txSlot)),

    (long)(the->currentHeapCount * sizeof(txSlot)),

    (long)(the->peakHeapCount * sizeof(txSlot)));

#endif

}

void fxMark(txMachine* the, void (*theMarker)(txMachine*, txSlot*))

{

  txSlot** p;

  txSlot** q;

  txSlot* slot;

#if mxAliasInstance

  p = the->aliasArray;

  q = p + the->aliasCount;

  while (p < q) {

    if ((slot = *p)) {

      (*theMarker)(the, slot);

      slot->flag |= XS_MARK_FLAG;

    }

    p++;

  }

#endif

  slot = the->stackTop;

  while (slot > the->stack) {

        slot--;

    (*theMarker)(the, slot);

  }

  slot = the->cRoot;

  while (slot) {

    (*theMarker)(the, slot);

    slot = slot->next;

  }

#if mxKeysGarbageCollection

  if (the->collectFlag & XS_COLLECT_KEYS_FLAG) {

    txInteger deletions = 0;

    p = the->keyArray;

    q = p + the->keyIndex - the->keyOffset;

    while (p < q) {

      slot = *p++;

      if (!(slot->flag & XS_MARK_FLAG)) {

        if (slot->flag & XS_DONT_DELETE_FLAG)

          slot->flag |= XS_MARK_FLAG;

        else if (slot->flag & XS_DONT_ENUM_FLAG)

          deletions++;

      }

    }

  //  fprintf(stderr, "\n### KEYS GC %d", deletions);

    p = the->nameTable;

    q = the->nameTable + the->nameModulo;

    while ((p < q) && deletions) {

      txSlot** address = p;

      while (((slot = *address)) && deletions) {

        if (slot->flag & XS_MARK_FLAG)

          address = &(slot->next);

        else {

          *address = slot->next;

          deletions--;

        }

      }

      p++;

    }

  //  fprintf(stderr, " => %d", deletions);

    the->keyholeCount = 0;

    the->keyholeList = C_NULL;

    p = the->keyArray;

    q = p + the->keyIndex - the->keyOffset;

    while (p < q) {

      slot = *p;

      if (slot->flag & XS_MARK_FLAG)

        (*theMarker)(the, slot);

      else {

  //      if (slot->kind != XS_UNDEFINED_KIND) {  

  //        fxIDToString(the, slot->ID, the->nameBuffer, sizeof(the->nameBuffer));

  //        fprintf(stderr, "\n%p %d %s", slot, slot->ID, the->nameBuffer);

  //      }

        slot->flag = XS_INTERNAL_FLAG | XS_MARK_FLAG;

        slot->next = the->keyholeList;

        slot->kind = XS_UNDEFINED_KIND;

        the->keyholeCount++;

        the->keyholeList = slot;

      }

      p++;

    }

  //  fprintf(stderr, "\n");

  }

  else

#endif

  {

    p = the->keyArray;

    q = p + the->keyIndex - the->keyOffset;

    while (p < q) {

      slot = *p++;

      slot->flag |= XS_MARK_FLAG;

      (*theMarker)(the, slot);

    }

  }

}

#if mxKeysGarbageCollection

void fxMarkID(txMachine* the, txID id)

{

  txSlot* slot;

  if (id == XS_NO_ID)

    return;

  if (id < the->keyOffset)

    return;

  id -= the->keyOffset;

  slot = the->keyArray[id];

  slot->flag |= XS_MARK_FLAG;

}

#endif

void fxMarkFinalizationRegistry(txMachine* the, txSlot* registry) 

{

  txSlot* slot = registry->value.finalizationRegistry.callback->next;

  txSlot* instance;

  while (slot) {

    slot = slot->next;

    if (slot) {

      instance = slot->value.finalizationCell.target;

      if (instance && !(instance->flag & XS_MARK_FLAG)) {

        slot->value.finalizationCell.target = C_NULL;

        registry->value.finalizationRegistry.flags |= XS_FINALIZATION_REGISTRY_CHANGED;

      }

      instance = slot->value.finalizationCell.token;

      if (instance && !(instance->flag & XS_MARK_FLAG))

        slot->value.finalizationCell.token = C_NULL;

      slot = slot->next;

    }

  }

}

void fxMarkInstance(txMachine* the, txSlot* theCurrent, void (*theMarker)(txMachine*, txSlot*))

{

  txSlot* aProperty;

  txSlot* aTemporary;

  mxCheck(the, theCurrent->kind == XS_INSTANCE_KIND);

  aProperty = theCurrent;

  theCurrent->value.instance.garbage = C_NULL;

  for (;;) {

    if (aProperty) {

      if (!(aProperty->flag & XS_MARK_FLAG)) {

        aProperty->flag |= XS_MARK_FLAG;

        switch (aProperty->kind) {

        case XS_INSTANCE_KIND:

          aTemporary = aProperty->value.instance.prototype;

          if (aTemporary && !(aTemporary->flag & XS_MARK_FLAG)) {

            aProperty->value.instance.prototype = theCurrent;

            theCurrent = aTemporary;

            theCurrent->value.instance.garbage = aProperty;

            aProperty = theCurrent;

          }

          else

            aProperty = aProperty->next;

          break;

        case XS_REFERENCE_KIND:

        #if mxKeysGarbageCollection

          if (the->collectFlag & XS_COLLECT_KEYS_FLAG) {

            if (!(aProperty->flag & XS_INTERNAL_FLAG))

              fxMarkID(the, aProperty->ID);

          }

        #endif

          aTemporary = aProperty->value.reference;

          if (!(aTemporary->flag & XS_MARK_FLAG)) {

            aProperty->value.reference = theCurrent;

            theCurrent = aTemporary;

            theCurrent->value.instance.garbage = aProperty;

            aProperty = theCurrent;

          }

          else

            aProperty = aProperty->next;

          break;

        case XS_PROXY_KIND:

          aTemporary = aProperty->value.proxy.handler;

          if (aTemporary && !(aTemporary->flag & XS_MARK_FLAG)) {

            aProperty->flag |= XS_INSPECTOR_FLAG;

            aProperty->value.proxy.handler = theCurrent;

            theCurrent = aTemporary;

            theCurrent->value.instance.garbage = aProperty;

            aProperty = theCurrent;

          }

          else {

            aTemporary = aProperty->value.proxy.target;

            if (aTemporary && !(aTemporary->flag & XS_MARK_FLAG)) {

              aProperty->value.proxy.target = theCurrent;

              theCurrent = aTemporary;

              theCurrent->value.instance.garbage = aProperty;

              aProperty = theCurrent;

            }

            else

              aProperty = aProperty->next;

          }

          break;

        case XS_CLOSURE_KIND:

        #if mxKeysGarbageCollection

          if (the->collectFlag & XS_COLLECT_KEYS_FLAG) {

            if (!(aProperty->flag & XS_INTERNAL_FLAG))

              fxMarkID(the, aProperty->ID);

          }

        #endif

          aTemporary = aProperty->value.closure;

          if (aTemporary && !(aTemporary->flag & XS_MARK_FLAG)) {

            aTemporary->flag |= XS_MARK_FLAG; 

            if (aTemporary->kind == XS_REFERENCE_KIND) {

              aTemporary = aTemporary->value.reference;

              if (!(aTemporary->flag & XS_MARK_FLAG)) {

                aProperty->value.closure->value.reference = theCurrent;

                theCurrent = aTemporary;

                theCurrent->value.instance.garbage = aProperty;

                aProperty = theCurrent;

              }

            }

            else {

              (*theMarker)(the, aTemporary);

              aProperty = aProperty->next;

            }

          }

          else

            aProperty = aProperty->next;

          break;

        case XS_CALLBACK_KIND:

        case XS_CODE_KIND:

        #if mxKeysGarbageCollection

          if (the->collectFlag & XS_COLLECT_KEYS_FLAG)

            fxMarkID(the, aProperty->ID);

        #endif

          (*theMarker)(the, aProperty);

          aProperty = aProperty->next;

          break;  

        default:

        #if mxKeysGarbageCollection

          if (the->collectFlag & XS_COLLECT_KEYS_FLAG) {

            if (!(aProperty->flag & XS_INTERNAL_FLAG))

              fxMarkID(the, aProperty->ID);

          }

        #endif

          (*theMarker)(the, aProperty);

          aProperty = aProperty->next;

          break; 

        }

      }

      else

        aProperty = aProperty->next;

    }

    else if (theCurrent->value.instance.garbage) {

      aProperty = theCurrent->value.instance.garbage;

      theCurrent->value.instance.garbage = C_NULL;

      switch (aProperty->kind) {

      case XS_INSTANCE_KIND:

        aTemporary = aProperty->value.instance.prototype;

        aProperty->value.instance.prototype = theCurrent;

        theCurrent = aTemporary;

        aProperty = aProperty->next;

        break;

      case XS_REFERENCE_KIND:

        aTemporary = aProperty->value.reference;

        aProperty->value.reference = theCurrent;

        theCurrent = aTemporary;

        aProperty = aProperty->next;

        break;

      case XS_PROXY_KIND:

        if (aProperty->flag & XS_INSPECTOR_FLAG) {

          aProperty->flag &= ~XS_INSPECTOR_FLAG;

          aTemporary = aProperty->value.proxy.handler;

          aProperty->value.proxy.handler = theCurrent;

          theCurrent = aTemporary;

          aTemporary = aProperty->value.proxy.target;

          if (aTemporary && !(aTemporary->flag & XS_MARK_FLAG)) {

            aProperty->value.proxy.target = theCurrent;

            theCurrent = aTemporary;

            theCurrent->value.instance.garbage = aProperty;

            aProperty = theCurrent;

          }

          else {

            aProperty = aProperty->next;

          }

        }

        else {

          aTemporary = aProperty->value.proxy.target;

          aProperty->value.proxy.target = theCurrent;

          theCurrent = aTemporary;

          aProperty = aProperty->next;

        }

        break;

      case XS_CLOSURE_KIND:

        aTemporary = aProperty->value.closure->value.reference;

        aProperty->value.closure->value.reference = theCurrent;

        theCurrent = aTemporary;

        aProperty = aProperty->next;