/*
 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
 *
 *  This file is licensed to You under the Eclipse Public License (EPL);
 *  You may not use this file except in compliance with the License. You
 *  may obtain a copy of the License at
 *
 *      http://www.opensource.org/licenses/eclipse-1.0.php
 *
 *  See the COPYRIGHT.txt file distributed with this work for information
 *  regarding copyright ownership.
 */
package org.mmtk.policy;

import org.mmtk.utility.alloc.BlockAllocator;
import org.mmtk.utility.alloc.EmbeddedMetaData;
import org.mmtk.utility.heap.FreeListPageResource;
import org.mmtk.utility.heap.VMRequest;
import org.mmtk.utility.Constants;
import org.mmtk.utility.Conversions;
import org.mmtk.utility.Memory;

import org.mmtk.vm.Lock;
import org.mmtk.vm.VM;

import org.vmmagic.pragma.*;
import org.vmmagic.unboxed.*;

/**
 * Each instance of this class corresponds to one mark-sweep *space*.
 * Each of the instance methods of this class may be called by any
 * thread (i.e. synchronization must be explicit in any instance or
 * class method).  This contrasts with the MarkSweepLocal, where
 * instances correspond to *plan* instances and therefore to kernel
 * threads.  Thus unlike this class, synchronization is not necessary
 * in the instance methods of MarkSweepLocal.
 */
@Uninterruptible
public abstract class SegregatedFreeListSpace extends Space implements Constants {

  /****************************************************************************
  *
  * Class variables
  */
  protected static final boolean LAZY_SWEEP = true;
  private static final boolean COMPACT_SIZE_CLASSES = false;
  protected static final int MIN_CELLS = 6;
  protected static final int MAX_CELLS = 99; // (1<<(INUSE_BITS-1))-1;
  protected static final int MAX_CELL_SIZE = 8<<10;
  public static final int MAX_FREELIST_OBJECT_BYTES = MAX_CELL_SIZE;

  // live bits etc
  private static final int OBJECT_LIVE_SHIFT = LOG_MIN_ALIGNMENT; // 4 byte resolution
  private static final int LOG_BIT_COVERAGE = OBJECT_LIVE_SHIFT;
  private static final int LOG_LIVE_COVERAGE = LOG_BIT_COVERAGE + LOG_BITS_IN_BYTE;
  private static final int LIVE_BYTES_PER_REGION = 1 << (EmbeddedMetaData.LOG_BYTES_IN_REGION - LOG_LIVE_COVERAGE);
  private static final Word WORD_SHIFT_MASK = Word.one().lsh(LOG_BITS_IN_WORD).minus(Extent.one());
  private static final int LOG_LIVE_WORD_STRIDE = LOG_LIVE_COVERAGE + LOG_BYTES_IN_WORD;
  private static final Extent LIVE_WORD_STRIDE = Extent.fromIntSignExtend(1<<LOG_LIVE_WORD_STRIDE);
  private static final Word LIVE_WORD_STRIDE_MASK = LIVE_WORD_STRIDE.minus(1).toWord().not();
  private static final int NET_META_DATA_BYTES_PER_REGION = BlockAllocator.META_DATA_BYTES_PER_REGION + LIVE_BYTES_PER_REGION;
  protected static final int META_DATA_PAGES_PER_REGION_WITH_BITMAP = Conversions.bytesToPages(Extent.fromIntSignExtend(NET_META_DATA_BYTES_PER_REGION));
  protected static final int META_DATA_PAGES_PER_REGION_NO_BITMAP = Conversions.bytesToPages(Extent.fromIntSignExtend(BlockAllocator.META_DATA_BYTES_PER_REGION));
  private static final Extent META_DATA_OFFSET = BlockAllocator.META_DATA_EXTENT;


  // calculate worst case fragmentation very conservatively
  private static final int NEW_SIZECLASS_OVERHEAD = sizeClassCount();  // one page wasted per size class
  private static final int METADATA_OVERHEAD = META_DATA_PAGES_PER_REGION_WITH_BITMAP; // worst case scenario
  public static final float WORST_CASE_FRAGMENTATION = 1 + ((NEW_SIZECLASS_OVERHEAD + METADATA_OVERHEAD)/(float) EmbeddedMetaData.BYTES_IN_REGION);

  /****************************************************************************
   *
   * Instance variables
   */
  protected final Lock lock = VM.newLock("SegregatedFreeListGlobal");
  protected final AddressArray consumedBlockHead = AddressArray.create(sizeClassCount());
  protected final AddressArray flushedBlockHead = AddressArray.create(sizeClassCount());
  protected final AddressArray availableBlockHead = AddressArray.create(sizeClassCount());

  private final int[] cellSize = new int[sizeClassCount()];
  private final byte[] blockSizeClass = new byte[sizeClassCount()];
  private final int[] blockHeaderSize = new int[sizeClassCount()];

  /**
   * The caller specifies the region of virtual memory to be used for
   * this space.  If this region conflicts with an existing space,
   * then the constructor will fail.
   *
   * @param name The name of this space (used when printing error messages etc)
   * @param pageBudget The number of pages this space may consume before consulting the plan
   * @param additionalMetadata The number of meta data bytes per region for the subclass.
   * @param vmRequest An object describing the virtual memory requested.
   */
  public SegregatedFreeListSpace(String name, int pageBudget, int additionalMetadata, VMRequest vmRequest) {
    super(name, false, false, vmRequest);
    initSizeClasses();
    int totalMetadata = additionalMetadata;
    if (maintainSideBitmap()) {
      totalMetadata += META_DATA_PAGES_PER_REGION_WITH_BITMAP;
    } else {
      totalMetadata += META_DATA_PAGES_PER_REGION_NO_BITMAP;
    }
    if (vmRequest.isDiscontiguous()) {
      pr = new FreeListPageResource(pageBudget, this, totalMetadata);
    } else {
      pr = new FreeListPageResource(pageBudget, this, start, extent, totalMetadata);
    }
  }

  /**
   * Should SegregatedFreeListSpace manage a side bitmap to keep track of live objects?
   */
  protected abstract boolean maintainSideBitmap();

  /**
   * Do we need to preserve free lists as we move blocks around.
   */
  protected abstract boolean preserveFreeList();

  /****************************************************************************
   *
   * Allocation
   */

  /**
   * Return a block to the global pool.
   *
   * @param block The block to return
   * @param sizeClass The size class
   */
  public void returnConsumedBlock(Address block, int sizeClass) {
    returnBlock(block, sizeClass, Address.zero());
  }

  /**
   * Return a block to the global pool.
   *
   * @param block The block to return
   * @param sizeClass The size class
   * @param freeCell The first free cell in the block.
   */
  public void returnBlock(Address block, int sizeClass, Address freeCell) {
    if (VM.VERIFY_ASSERTIONS) {
      VM.assertions._assert(BlockAllocator.getNext(block).isZero());
    }
    if (preserveFreeList()) {
      setFreeList(block, freeCell);
    }
    lock.acquire();
    BlockAllocator.setNext(block, consumedBlockHead.get(sizeClass));
    consumedBlockHead.set(sizeClass, block);
    lock.release();
  }

  /**
   * Acquire a new block from the global pool to allocate into. This method
   * with either return a non-empty free list, or zero when allocation
   * fails.
   *
   * This method will populate the passed in free list for the given size
   * class and return the address of the block.
   *
   * @param sizeClass The size class to allocate into
   * @param freeList The free list to populate
   * @return The address of the block
   */
  public Address getAllocationBlock(int sizeClass, AddressArray freeList) {
    lock.acquire();
    Address block;
    while(!(block = availableBlockHead.get(sizeClass)).isZero()) {
      availableBlockHead.set(sizeClass, BlockAllocator.getNext(block));
      lock.release();

      /* This block is no longer on any list */
      BlockAllocator.setNext(block, Address.zero());

      /* Can we allocate into this block? */
      Address cell = advanceToBlock(block, sizeClass);
      if (!cell.isZero()) {
        freeList.set(sizeClass, cell);
        return block;
      }

      /* Block was full */
      lock.acquire();
      BlockAllocator.setNext(block, consumedBlockHead.get(sizeClass));
      consumedBlockHead.set(sizeClass, block);
    }
    lock.release();
    return expandSizeClass(sizeClass, freeList);
  }

  /**
   * Expand a particular size class, allocating a new block, breaking
   * the block into cells and placing those cells on a free list for
   * that block.  The block becomes the current head for this size
   * class and the address of the first available cell is returned.<p>
   *
   * <b>This is guaranteed to return pre-zeroed cells</b>
   *
   * @param sizeClass The size class to be expanded
   * @param freeList The free list to populate.
   * @return The block that was just allocated.
   */
  @Inline
  private Address expandSizeClass(int sizeClass, AddressArray freeList) {
    Address block = BlockAllocator.alloc(this, blockSizeClass[sizeClass]);

    if (block.isZero()) {
      return Address.zero();
    }

    BlockAllocator.setNext(block, Address.zero());
    BlockAllocator.setAllClientSizeClass(block, blockSizeClass[sizeClass], (byte) sizeClass);

    notifyNewBlock(block, sizeClass);

    int cellExtent = cellSize[sizeClass];
    int blockSize = BlockAllocator.blockSize(blockSizeClass[sizeClass]);
    int useableBlockSize = blockSize - blockHeaderSize[sizeClass];
    Address firstCell = block.plus(blockHeaderSize[sizeClass]);
    Address sentinel = block.plus(blockSize);

    /* pre-zero the block */
    VM.memory.zero(firstCell, Extent.fromIntZeroExtend(useableBlockSize));

    /* construct the free list */
    Address nextCell;
    Address cell = firstCell;
    while ((nextCell = cell.plus(cellExtent)).LT(sentinel)) {
      cell.store(nextCell);
      cell = nextCell;
    }

    /* Populate the free list */
    freeList.set(sizeClass, firstCell);
    return block;
  }

  /****************************************************************************
   *
   * Block management
   */

  /**
   * Initialize the size class data structures.
   */
  private void initSizeClasses() {
    for (int sc = 0; sc < sizeClassCount(); sc++) {
      cellSize[sc] = getBaseCellSize(sc);
      for (byte blk = 0; blk < BlockAllocator.BLOCK_SIZE_CLASSES; blk++) {
        int usableBytes = BlockAllocator.blockSize(blk);
        int cells = usableBytes / cellSize[sc];
        blockSizeClass[sc] = blk;
        /* cells must start at multiple of MIN_ALIGNMENT because
           cellSize is also supposed to be multiple, this should do
           the trick: */
        blockHeaderSize[sc] = BlockAllocator.blockSize(blk) - cells * cellSize[sc];
        if (((usableBytes < BYTES_IN_PAGE) && (cells*2 > MAX_CELLS)) ||
            ((usableBytes > (BYTES_IN_PAGE>>1)) && (cells > MIN_CELLS)))
          break;
      }
    }
  }

  /**
   * Get the size class for a given number of bytes.
   *
   * We use size classes based on a worst case internal fragmentation
   * loss target of 1/8.  In fact, across sizes from 8 bytes to 512
   * the average worst case loss is 13.3%, giving an expected loss
   * (assuming uniform distribution) of about 7%.  We avoid using the
   * Lea class sizes because they were so numerous and therefore
   * liable to lead to excessive inter-class-size fragmentation.<p>
   *
   * This method may segregate arrays and scalars (currently it does
   * not).<p>
   *
   * This method should be more intelligent and take alignment requests
   * into consideration. The issue with this is that the block header
   * which can be varied by subclasses can change the alignment of the
   * cells.<p>
   *
   * @param bytes The number of bytes required to accommodate the object
   * to be allocated.
   * @return The size class capable of accommodating the allocation request.
   */
  @Inline
  public final int getSizeClass(int bytes) {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((bytes > 0) && (bytes <= MAX_CELL_SIZE));

    int sz1 = bytes - 1;

    if (BYTES_IN_ADDRESS == 4) { // 32-bit
      if (COMPACT_SIZE_CLASSES)
        return (
            (sz1 <=  31) ?      (sz1 >>  2) : //    4 bytes apart
            (sz1 <=  63) ?  4 + (sz1 >>  3) : //    8 bytes apart
            (sz1 <=  95) ?  8 + (sz1 >>  4) : //   16 bytes apart
            (sz1 <= 223) ? 14 + (sz1 >>  6) : //   64 bytes apart
            (sz1 <= 734) ? 17 + (sz1 >>  8) : //  256 bytes apart
                           20 + (sz1 >> 10)); // 1024 bytes apart
      else
        return (
            (sz1 <=   63) ?      (sz1 >>  2) : //    4 bytes apart
            (sz1 <=  127) ? 12 + (sz1 >>  4) : //   16 bytes apart
            (sz1 <=  255) ? 16 + (sz1 >>  5) : //   32 bytes apart
            (sz1 <=  511) ? 20 + (sz1 >>  6) : //   64 bytes apart
            (sz1 <= 2047) ? 26 + (sz1 >>  8) : //  256 bytes apart
                            32 + (sz1 >> 10)); // 1024 bytes apart
    } else { // 64-bit
      if (COMPACT_SIZE_CLASSES)
        return (
            (sz1 <=   95) ?      (sz1 >>  3) : //    8 bytes apart
            (sz1 <=  127) ?  6 + (sz1 >>  4) : //   16 bytes apart
            (sz1 <=  191) ? 10 + (sz1 >>  5) : //   32 bytes apart
            (sz1 <=  383) ? 13 + (sz1 >>  6) : //   64 bytes apart
            (sz1 <=  511) ? 16 + (sz1 >>  7) : //  128 bytes apart
            (sz1 <= 1023) ? 19 + (sz1 >>  9) : //  512 bytes apart
                            20 + (sz1 >> 10)); // 1024 bytes apart
      else
        return (
            (sz1 <=  111) ?      (sz1 >>  3) : //    8 bytes apart
            (sz1 <=  223) ?  7 + (sz1 >>  4) : //   16 bytes apart
            (sz1 <=  319) ? 14 + (sz1 >>  5) : //   32 bytes apart
            (sz1 <=  575) ? 19 + (sz1 >>  6) : //   64 bytes apart
            (sz1 <= 2047) ? 26 + (sz1 >>  8) : //  256 bytes apart
                            32 + (sz1 >> 10)); // 1024 bytes apart
    }
  }

  /**
   * Return the size of a basic cell (i.e. not including any cell
   * header) for a given size class.
   *
   * @param sc The size class in question
   * @return The size of a basic cell (i.e. not including any cell
   * header).
   */
  @Inline
  public final int getBaseCellSize(int sc) {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((sc >= 0) && (sc < sizeClassCount()));

    if (BYTES_IN_ADDRESS == 4) { // 32-bit
      if (COMPACT_SIZE_CLASSES)
        return ((sc <  8) ? (sc +  1) <<  2:
                (sc < 12) ? (sc -  3) <<  3:
                (sc < 16) ? (sc -  7) <<  4:
                (sc < 18) ? (sc - 13) <<  6:
                (sc < 21) ? (sc - 16) <<  8:
                            (sc - 19) << 10);
      else
        return ((sc < 16) ? (sc +  1) <<  2:
                (sc < 20) ? (sc - 11) <<  4:
                (sc < 24) ? (sc - 15) <<  5:
                (sc < 28) ? (sc - 19) <<  6:
                (sc < 34) ? (sc - 25) <<  8:
                            (sc - 31) << 10);
    } else { // 64-bit
      if (COMPACT_SIZE_CLASSES)
        return ((sc < 12) ? (sc +  1) <<  3:
                (sc < 14) ? (sc -  5) <<  4:
                (sc < 16) ? (sc -  9) <<  5:
                (sc < 19) ? (sc - 12) <<  6:
                (sc < 20) ? (sc - 15) <<  7:
                (sc < 21) ? (sc - 18) <<  9:
                            (sc - 19) << 10);
      else
        return ((sc < 14) ? (sc +  1) <<  3:
                (sc < 21) ? (sc -  6) <<  4:
                (sc < 24) ? (sc - 13) <<  5:
                (sc < 28) ? (sc - 18) <<  6:
                (sc < 34) ? (sc - 25) <<  8:
                            (sc - 31) << 10);
    }
  }

  /**
   * The number of distinct size classes.
   */
  @Inline
  public static int sizeClassCount() {
    return (COMPACT_SIZE_CLASSES) ? 28 : 40;
  }

  /****************************************************************************
   *
   * Preserving (saving & restoring) free lists
   */

  /**
   * Prepare a block for allocation, returning a free list into the block.
   *
   * @param block The new block
   * @param sizeClass The block's sizeclass.
   */
  protected abstract Address advanceToBlock(Address block, int sizeClass);

  /**
   * Notify that a new block has been installed.
   *
   * @param block The new block
   * @param sizeClass The block's sizeclass.
   */
  protected void notifyNewBlock(Address block, int sizeClass) {}

  /**
   * Should the sweep reclaim the cell containing this object. Is this object
   * live. This is only used when maintainSideBitmap is false.
   *
   * @param object The object to query
   * @return True if the cell should be reclaimed
   */
  protected boolean reclaimCellForObject(ObjectReference object) {
    VM.assertions.fail("Must implement reclaimCellForObject if not maintaining side bitmap");
    return false;
  }

  /****************************************************************************
   *
   * Metadata manipulation
   */

  /**
   * In the case where free lists associated with each block are
   * preserved, get the free list for a given block.
   *
   * @param block The block whose free list is to be found
   * @return The free list for this block
   */
  @Inline
  protected final Address getFreeList(Address block) {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(preserveFreeList());
    return BlockAllocator.getFreeListMeta(block);
  }

  /**
   * In the case where free lists associated with each block are
   * preserved, set the free list for a given block.
   *
   * @param block The block whose free list is to be found
   * @param cell The head of the free list (i.e. the first cell in the
   * free list).
   */
  @Inline
  protected final void setFreeList(Address block, Address cell) {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(preserveFreeList());
    BlockAllocator.setFreeListMeta(block, cell);
  }

  /****************************************************************************
   *
   * Collection
   */

  /**
   * Clear all block marks for this space.  This method is important when
   * it is desirable to do partial collections, which man mean that block
   * marks need to be explicitly cleared when necessary.
   */
  protected final void clearAllBlockMarks() {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!maintainSideBitmap());
    for (int sizeClass = 0; sizeClass < sizeClassCount(); sizeClass++) {
      Extent blockSize = Extent.fromIntSignExtend(BlockAllocator.blockSize(blockSizeClass[sizeClass]));
      /* Flushed blocks */
      Address block = flushedBlockHead.get(sizeClass);
      while (!block.isZero()) {
        Address next = BlockAllocator.getNext(block);
        clearBlockMark(block, blockSize);
        block = next;
      }
      /* Available blocks */
      block = consumedBlockHead.get(sizeClass);
      while (!block.isZero()) {
        Address next = BlockAllocator.getNext(block);
        clearBlockMark(block, blockSize);
        block = next;
      }
    }
  }

  /**
   * Sweep all blocks for free objects.
   *
   * @param clearMarks should we clear block mark bits as we process.
   */
  protected final void sweepConsumedBlocks(boolean clearMarks) {
    for (int sizeClass = 0; sizeClass < sizeClassCount(); sizeClass++) {
      Extent blockSize = Extent.fromIntSignExtend(BlockAllocator.blockSize(blockSizeClass[sizeClass]));
      Address availableHead = Address.zero();
      /* Flushed blocks */
      Address block = flushedBlockHead.get(sizeClass);
      flushedBlockHead.set(sizeClass, Address.zero());
      while (!block.isZero()) {
        Address next = BlockAllocator.getNext(block);
        availableHead = sweepBlock(block, sizeClass, blockSize, availableHead, clearMarks);
        block = next;
      }
      /* Consumed blocks */
      block = consumedBlockHead.get(sizeClass);
      consumedBlockHead.set(sizeClass, Address.zero());
      while (!block.isZero()) {
        Address next = BlockAllocator.getNext(block);
        availableHead = sweepBlock(block, sizeClass, blockSize, availableHead, clearMarks);
        block = next;
      }
      /* Make blocks available */
      availableBlockHead.set(sizeClass, availableHead);
    }
  }

  /**
   * Sweep a block, freeing it and adding to the list given by availableHead
   * if it contains no free objects.
   *
   * @param clearMarks should we clear block mark bits as we process.
   */
  protected final Address sweepBlock(Address block, int sizeClass, Extent blockSize, Address availableHead, boolean clearMarks) {
    boolean liveBlock = containsLiveCell(block, blockSize, clearMarks);
    if (!liveBlock) {
      BlockAllocator.setNext(block, Address.zero());
      BlockAllocator.free(this, block);
    } else {
      BlockAllocator.setNext(block, availableHead);
      availableHead = block;
      if (!LAZY_SWEEP) {
        setFreeList(block, makeFreeList(block, sizeClass));
      }
    }
    return availableHead;
  }

  /**
   * Eagerly consume all remaining blocks.
   */
  protected final void consumeBlocks() {
    for (int sizeClass = 0; sizeClass < sizeClassCount(); sizeClass++) {
      while (!getAllocationBlock(sizeClass, null).isZero());
    }
  }

  /**
   * Flush all the allocation blocks to the consumed list.
   */
  protected final void flushAvailableBlocks() {
    for (int sizeClass = 0; sizeClass < sizeClassCount(); sizeClass++) {
      flushedBlockHead.set(sizeClass, availableBlockHead.get(sizeClass));
      availableBlockHead.set(sizeClass, Address.zero());
    }
  }

  /**
   * Does this block contain any live cells.
   *
   * @param block The block
   * @param blockSize The size of the block
   * @param clearMarks should we clear block mark bits as we process.
   * @return True if any cells in the block are live
   */
  @Inline
  protected boolean containsLiveCell(Address block, Extent blockSize, boolean clearMarks) {
    if (maintainSideBitmap()) {
      if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(alignToLiveStride(block).EQ(block));
      Address cursor = getLiveWordAddress(block);
      Address sentinel = getLiveWordAddress(block.plus(blockSize.minus(1)));
      while (cursor.LE(sentinel)) {
        Word live = cursor.loadWord();
        if (!live.isZero()) {
          return true;
        }
        cursor = cursor.plus(BYTES_IN_WORD);
      }
      return false;
    } else {
      boolean live = false;
      Address cursor = block;
      while(cursor.LT(block.plus(blockSize))) {
        live |= BlockAllocator.checkBlockMeta(cursor);
        if (clearMarks)
          BlockAllocator.clearBlockMeta(cursor);
        cursor = cursor.plus(1 << BlockAllocator.LOG_MIN_BLOCK);
      }
      return live;
    }
  }


  /**
   * Clear block marks for a block
   *
   * @param block The block
   * @param blockSize The size of the block
   */
  @Inline
  protected void clearBlockMark(Address block, Extent blockSize) {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!maintainSideBitmap());
    Address cursor = block;
    while(cursor.LT(block.plus(blockSize))) {
      BlockAllocator.clearBlockMeta(cursor);
      cursor = cursor.plus(1 << BlockAllocator.LOG_MIN_BLOCK);
    }
  }

  /**
   * In the cell containing this object live?
   *
   * @param object The object
   * @return True if the cell is live
   */
  @Inline
  protected boolean isCellLive(ObjectReference object) {
    /* Must override if not using the side bitmap */
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(maintainSideBitmap());
    return liveBitSet(object);
  }

  /**
   * Use the live bits for a block to infer free cells and thus
   * construct a free list for the block.
   *
   * @param block The block to be processed
   * @param sizeClass The size class for the block
   * @return The head of the new free list
   */
  @Inline
  protected final Address makeFreeList(Address block, int sizeClass) {
    Extent blockSize = Extent.fromIntSignExtend(BlockAllocator.blockSize(blockSizeClass[sizeClass]));
    Address cursor = block.plus(blockHeaderSize[sizeClass]);
    Address lastFree = Address.zero();
    Address firstFree = Address.zero();
    Address end = block.plus(blockSize);
    Extent cellExtent = Extent.fromIntSignExtend(cellSize[sizeClass]);
    while (cursor.LT(end)) {
      ObjectReference current = VM.objectModel.getObjectFromStartAddress(cursor);
      boolean free = true;
      if (!current.isNull()) {
        free = !isCellLive(current);
      }
      if (free) {
        if (firstFree.isZero()) {
          firstFree = cursor;
        } else {
          lastFree.store(cursor);
        }
        Memory.zeroSmall(cursor, cellExtent);
        lastFree = cursor;
      }
      cursor = cursor.plus(cellExtent);
    }
    return firstFree;
  }

  /**
   * Sweep all blocks for free objects.
   */
  public void sweepCells(Sweeper sweeper) {
    for (int sizeClass = 0; sizeClass < sizeClassCount(); sizeClass++) {
      Address availableHead = Address.zero();
      /* Flushed blocks */
      Address block = flushedBlockHead.get(sizeClass);
      flushedBlockHead.set(sizeClass, Address.zero());
      while (!block.isZero()) {
        Address next = BlockAllocator.getNext(block);
        availableHead = sweepCells(sweeper, block, sizeClass, availableHead);
        block = next;
      }
      /* Consumed blocks */
      block = consumedBlockHead.get(sizeClass);
      consumedBlockHead.set(sizeClass, Address.zero());
      while (!block.isZero()) {
        Address next = BlockAllocator.getNext(block);
        availableHead = sweepCells(sweeper, block, sizeClass, availableHead);
        block = next;
      }
      /* Make blocks available */
      availableBlockHead.set(sizeClass, availableHead);
    }
  }

  /**
   * Sweep a block, freeing it and adding to the list given by availableHead
   * if it contains no free objects.
   */
  private Address sweepCells(Sweeper sweeper, Address block, int sizeClass, Address availableHead) {
    boolean liveBlock = sweepCells(sweeper, block, sizeClass);
    if (!liveBlock) {
      BlockAllocator.setNext(block, Address.zero());
      BlockAllocator.free(this, block);
    } else {
      BlockAllocator.setNext(block, availableHead);
      availableHead = block;
    }
    return availableHead;
  }

  /**
   * Sweep a block, freeing it and making it available if any live cells were found.
   * if it contains no free objects.
   *
   * This is designed to be called in parallel by multiple collector threads.
   */
  public void parallelSweepCells(Sweeper sweeper) {
    for (int sizeClass = 0; sizeClass < sizeClassCount(); sizeClass++) {
      Address block;
      while(!(block = getSweepBlock(sizeClass)).isZero()) {
        boolean liveBlock = sweepCells(sweeper, block, sizeClass);
        if (!liveBlock) {
          BlockAllocator.setNext(block, Address.zero());
          BlockAllocator.free(this, block);
        } else {
          lock.acquire();
          BlockAllocator.setNext(block, availableBlockHead.get(sizeClass));
          availableBlockHead.set(sizeClass, block);
          lock.release();
        }
      }
    }
  }

  /**
   * Get a block for a parallel sweep.
   *
   * @param sizeClass The size class of the block to sweep.
   * @return The block or zero if no blocks remain to be swept.
   */
  private Address getSweepBlock(int sizeClass) {
    lock.acquire();
    Address block;

    /* Flushed blocks */
    block = flushedBlockHead.get(sizeClass);
    if (!block.isZero()) {
      flushedBlockHead.set(sizeClass, BlockAllocator.getNext(block));
      lock.release();
      BlockAllocator.setNext(block, Address.zero());
      return block;
    }

    /* Consumed blocks */
    block = consumedBlockHead.get(sizeClass);
    if (!block.isZero()) {
      flushedBlockHead.set(sizeClass, BlockAllocator.getNext(block));
      lock.release();
      BlockAllocator.setNext(block, Address.zero());
      return block;
    }

    /* All swept! */
    lock.release();
    return Address.zero();
  }

  /**
   * Does this block contain any live cells?
   */
  @Inline
  public boolean sweepCells(Sweeper sweeper, Address block, int sizeClass) {
    Extent blockSize = Extent.fromIntSignExtend(BlockAllocator.blockSize(blockSizeClass[sizeClass]));
    Address cursor = block.plus(blockHeaderSize[sizeClass]);
    Address end = block.plus(blockSize);
    Extent cellExtent = Extent.fromIntSignExtend(cellSize[sizeClass]);
    boolean containsLive = false;
    while (cursor.LT(end)) {
      ObjectReference current = VM.objectModel.getObjectFromStartAddress(cursor);
      boolean free = true;
      if (!current.isNull()) {
        free = !liveBitSet(current);
        if (!free) {
          free = sweeper.sweepCell(current);
          if (free) unsyncClearLiveBit(current);
        }
      }
      if (!free) {
        containsLive = true;
      }
      cursor = cursor.plus(cellExtent);
    }
    return containsLive;
  }

  /**
   * A callback used to perform sweeping of a free list space.
   */
  @Uninterruptible
  public abstract static class Sweeper {
    public abstract boolean sweepCell(ObjectReference object);
  }

  /****************************************************************************
   *
   * Live bit manipulation
   */

  /**
   * Atomically set the live bit for a given object
   *
   * @param object The object whose live bit is to be set.
   * @return True if the bit was changed to true.
   */
  @Inline
  public static boolean testAndSetLiveBit(ObjectReference object) {
    return updateLiveBit(VM.objectModel.objectStartRef(object), true, true);
  }

  /**
   * Set the live bit for the block containing the given object
   *
   * @param object The object whose blocks liveness is to be set.
   */
  @Inline
  protected static void markBlock(ObjectReference object) {
    BlockAllocator.markBlockMeta(object);
  }

  /**
   * Set the live bit for the given block.
   *
   * @param block The block whose liveness is to be set.
   */
  @Inline
  protected static void markBlock(Address block) {
    BlockAllocator.markBlockMeta(block);
  }

  /**
   * Set the live bit for a given object, without using
   * synchronization primitives---must only be used when contention
   * for live bit is strictly not possible
   *
   * @param object The object whose live bit is to be set.
   */
  @Inline
  public static boolean unsyncSetLiveBit(ObjectReference object) {
    return updateLiveBit(VM.objectModel.refToAddress(object), true, false);
  }

  /**
   * Set the live bit for a given address
   *
   * @param address The address whose live bit is to be set.
   * @param set True if the bit is to be set, as opposed to cleared
   * @param atomic True if we want to perform this operation atomically
   */
  @Inline
  private static boolean updateLiveBit(Address address, boolean set, boolean atomic) {
    Word oldValue, newValue;
    Address liveWord = getLiveWordAddress(address);
    Word mask = getMask(address, true);
    if (atomic) {
      do {
        oldValue = liveWord.prepareWord();
        newValue = (set) ? oldValue.or(mask) : oldValue.and(mask.not());
      } while (!liveWord.attempt(oldValue, newValue));
    } else {
      oldValue = liveWord.loadWord();
      liveWord.store(set ? oldValue.or(mask) : oldValue.and(mask.not()));
    }
    return oldValue.and(mask).NE(mask);
  }

  /**
   * Test the live bit for a given object
   *
   * @param object The object whose live bit is to be set.
   */
  @Inline
  protected static boolean liveBitSet(ObjectReference object) {
    return liveBitSet(VM.objectModel.refToAddress(object));
  }

  /**
   * Set the live bit for a given address
   *
   * @param address The address whose live bit is to be set.
   * @return true if this operation changed the state of the live bit.
   */
  @Inline
  protected static boolean liveBitSet(Address address) {
    Address liveWord = getLiveWordAddress(address);
    Word mask = getMask(address, true);
    Word value = liveWord.loadWord();
    return value.and(mask).EQ(mask);
  }

  /**
   * Clear the live bit for a given object
   *
   * @param object The object whose live bit is to be cleared.
   */
  @Inline
  protected static void clearLiveBit(ObjectReference object) {
    clearLiveBit(VM.objectModel.refToAddress(object));
  }

  /**
   * Clear the live bit for a given address
   *
   * @param address The address whose live bit is to be cleared.
   */
  @Inline
  protected static void clearLiveBit(Address address) {
    updateLiveBit(address, false, true);
  }

  /**
   * Clear the live bit for a given object
   *
   * @param object The object whose live bit is to be cleared.
   */
  @Inline
  protected static void unsyncClearLiveBit(ObjectReference object) {
    unsyncClearLiveBit(VM.objectModel.refToAddress(object));
  }

  /**
   * Clear the live bit for a given address
   *
   * @param address The address whose live bit is to be cleared.
   */
  @Inline
  protected static void unsyncClearLiveBit(Address address) {
    updateLiveBit(address, false, false);
  }

  /**
   * Clear all live bits for a block
   */
  protected void clearLiveBits(Address block, int sizeClass) {
    int blockSize = BlockAllocator.blockSize(blockSizeClass[sizeClass]);
    Address cursor = getLiveWordAddress(block);
    Address sentinel = getLiveWordAddress(block.plus(blockSize - 1));
    while (cursor.LE(sentinel)) {
      cursor.store(Word.zero());
      cursor = cursor.plus(BYTES_IN_WORD);
    }
  }

  /**
   * Clear all live bits
   */
  protected static void zeroLiveBits(Address start, Address end) {
    Extent bytes = Extent.fromIntSignExtend(EmbeddedMetaData.BYTES_IN_REGION>>LOG_LIVE_COVERAGE);
    while (start.LT(end)) {
      Address metadata = EmbeddedMetaData.getMetaDataBase(start).plus(META_DATA_OFFSET);
      VM.memory.zero(metadata, bytes);
      start = start.plus(EmbeddedMetaData.BYTES_IN_REGION);
    }
  }

  /**
   * Align an address so that it corresponds to a live word boundary.
   * In other words, if the live bit for the given address is not the
   * zeroth bit of a live word, round the address down such that it
   * does.
   *
   * @param address The address to be aligned to a live word
   * @return The given address, aligned down so that it corresponds to
   * an address on a live word boundary.
   */
  private static Address alignToLiveStride(Address address) {
    return address.toWord().and(LIVE_WORD_STRIDE_MASK).toAddress();
  }

  /**
   * Given an address, produce a bit mask for the live table
   *
   * @param address The address whose live bit mask is to be established
   * @param set True if we want the mask for <i>setting</i> the bit,
   * false if we want the mask for <i>clearing</i> the bit.
   * @return The appropriate bit mask for object for the live table for.
   */
  @Inline
  private static Word getMask(Address address, boolean set) {
    int shift = address.toWord().rshl(OBJECT_LIVE_SHIFT).and(WORD_SHIFT_MASK).toInt();
    Word rtn = Word.one().lsh(shift);
    return (set) ? rtn : rtn.not();
  }

  /**
   * Given an address, return the address of the live word for
   * that address.
   *
   * @param address The address whose live word address is to be returned
   * @return The address of the live word for this object
   */
  @Inline
  private static Address getLiveWordAddress(Address address) {
    Address rtn = EmbeddedMetaData.getMetaDataBase(address);
    return rtn.plus(META_DATA_OFFSET).plus(EmbeddedMetaData.getMetaDataOffset(address, LOG_LIVE_COVERAGE, LOG_BYTES_IN_WORD));
  }
}