/*
 *  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.utility.alloc;

import org.mmtk.policy.Space;
import org.mmtk.utility.*;

import org.mmtk.vm.VM;

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

/**
 * This class implements "block" data structures of various sizes.<p>
 *
 * Blocks are a non-shared (thread-local) coarse-grained unit of
 * storage. Blocks are available in power-of-two sizes.
 *
 * Virtual memory space is taken from a VM resource, and pages
 * consumed by blocks are accounted for by a memory resource.
 */
@Uninterruptible
public final class BlockAllocator implements Constants {
  /****************************************************************************
   *
   * Class variables
   */

  // block freelist
  public static final int LOG_MIN_BLOCK = 12; // 4K bytes
  public static final int LOG_MAX_BLOCK = 15; // 32K bytes
  public static final byte MAX_BLOCK_SIZE_CLASS = LOG_MAX_BLOCK - LOG_MIN_BLOCK;
  public static final int BLOCK_SIZE_CLASSES = MAX_BLOCK_SIZE_CLASS + 1;

  // metadata
  private static final Offset NEXT_OFFSET = Offset.zero();
  private static final Offset BMD_OFFSET = NEXT_OFFSET.plus(BYTES_IN_ADDRESS);
  private static final Offset CSC_OFFSET = BMD_OFFSET.plus(1);
  private static final Offset IU_OFFSET = CSC_OFFSET.plus(1);
  private static final Offset FL_META_OFFSET = IU_OFFSET.plus(BYTES_IN_SHORT);
  private static final byte BLOCK_SC_MASK = 0xf;             // lower 4 bits
  private static final int BLOCK_PAGE_OFFSET_SHIFT = 4;      // higher 4 bits
  private static final int MAX_BLOCK_PAGE_OFFSET = (1<<4)-1; // 4 bits
  private static final int LOG_BYTES_IN_BLOCK_META = LOG_BYTES_IN_ADDRESS + 2;
  private static final int LOG_BYTE_COVERAGE = LOG_MIN_BLOCK - LOG_BYTES_IN_BLOCK_META;

  public static final int META_DATA_BYTES_PER_REGION = 1 << (EmbeddedMetaData.LOG_BYTES_IN_REGION - LOG_BYTE_COVERAGE);
  public static final Extent META_DATA_EXTENT = Extent.fromIntSignExtend(META_DATA_BYTES_PER_REGION);

  /****************************************************************************
   *
   * Allocation & freeing
   */

  /**
   * Allocate a block, returning the address of the first usable byte
   * in the block.
   *
   * @param blockSizeClass The size class for the block to be allocated.
   * @return The address of the first usable byte in the block, or
   * zero on failure.
   */
  public static Address alloc(Space space, int blockSizeClass) {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((blockSizeClass >= 0) && (blockSizeClass <= MAX_BLOCK_SIZE_CLASS));
    int pages = pagesForSizeClass(blockSizeClass);
    Address result = space.acquire(pages);
    if (!result.isZero()) {
      setBlkSizeMetaData(result, (byte) blockSizeClass);
    }
    return result;
  }

  /**
   * Free a block.  If the block is a sub-page block and the page is
   * not completely free, then the block is added to the free list.
   * Otherwise the block is returned to the virtual memory resource.
   *
   * @param block The address of the block to be freed
   */
  public static void free(Space space, Address block) {
    space.release(block);
  }

  /**
   * Return the size in bytes of a block of a given size class
   *
   * @param blockSizeClass The size class in question
   * @return The size in bytes of a block of this size class
   */
  @Inline
  public static int blockSize(int blockSizeClass) {
    return 1 << (LOG_MIN_BLOCK + blockSizeClass);
  }

  /**
   * Return the number of pages required when allocating space for
   *         this size class.
   *
   * @param blockSizeClass The size class in question
   * @return The number of pages required when allocating a block (or
   * blocks) of this size class.
   */
  @Inline
  private static int pagesForSizeClass(int blockSizeClass) {
    return 1 << (LOG_MIN_BLOCK + blockSizeClass - LOG_BYTES_IN_PAGE);
  }

  /****************************************************************************
   *
   * Block meta-data manipulation
   */

  /**
   * Set the <i>block size class</i> meta data field for a given
   * address (all blocks on a given page are homogeneous with respect
   * to block size class).
   *
   * @param block The address of interest
   * @param sc The value to which this field is to be set
   */
  @Inline
  private static void setBlkSizeMetaData(Address block, byte sc) {
    if (VM.VERIFY_ASSERTIONS) {
      VM.assertions._assert(block.EQ(Conversions.pageAlign(block)));
      VM.assertions._assert(pagesForSizeClass(sc) - 1  <= MAX_BLOCK_PAGE_OFFSET);
    }
    Address address = block;
    for (int i = 0; i < pagesForSizeClass(sc); i++) {
      byte value = (byte) ((i << BLOCK_PAGE_OFFSET_SHIFT) | sc);
      getMetaAddress(address).store(value, BMD_OFFSET);
      if (VM.VERIFY_ASSERTIONS) {
        VM.assertions._assert(getBlkStart(address).EQ(block));
        VM.assertions._assert(getBlkSizeClass(address) == sc);
      }
      address = address.plus(1<<VM.LOG_BYTES_IN_PAGE);
    }
  }

  /**
   * Get the <i>block size class</i> meta data field for a given page
   * (all blocks on a given page are homogeneous with respect to block
   * size class).
   *
   * @param address The address of interest
   * @return The size class field for the block containing the given address
   */
  @Inline
  private static byte getBlkSizeClass(Address address) {
    address = Conversions.pageAlign(address);
    byte rtn = (byte) (getMetaAddress(address).loadByte(BMD_OFFSET) & BLOCK_SC_MASK);
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(rtn >= 0 && rtn <= MAX_BLOCK_SIZE_CLASS);
    return rtn;
  }

  /**
   * Get the <i>address of the start of a block size class</i> a given page
   * within the block.
   *
   * @param address The address of interest
   * @return The address of the block containing the address
   */
  @Inline
  public static Address getBlkStart(Address address) {
    address = Conversions.pageAlign(address);
    byte offset = (byte) (getMetaAddress(address).loadByte(BMD_OFFSET) >>> BLOCK_PAGE_OFFSET_SHIFT);
    return address.minus(offset<<LOG_BYTES_IN_PAGE);
  }

  /**
   * Set the <i>client size class</i> meta data field for a given
   * address (all blocks on a given page are homogeneous with respect
   * to block size class).
   *
   * @param block The address of interest
   * @param sc The value to which this field is to be set
   */
  @Inline
  public static void setAllClientSizeClass(Address block, int blocksc, byte sc) {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(block.EQ(Conversions.pageAlign(block)));
    Address address = block;
    for (int i = 0; i < pagesForSizeClass(blocksc); i++) {
      getMetaAddress(address).store(sc, CSC_OFFSET);
      address = address.plus(1<<VM.LOG_BYTES_IN_PAGE);
    }
  }

  /**
   * Get the <i>client size class</i> meta data field for a given page
   * (all blocks on a given page are homogeneous with respect to block
   * size class).
   *
   * @param address The address of interest
   * @return The size class field for the block containing the given address
   */
  @Inline
  public static byte getClientSizeClass(Address address) {
    address = Conversions.pageAlign(address);
    byte rtn = getMetaAddress(address).loadByte(CSC_OFFSET);
    return rtn;
  }

  /**
   * Set the free list meta data field for a given address (this is
   * per-block meta data that is stored along with the block metadata
   * but not used by the block allocator).
   *
   * @param address The address of interest
   * @param value The value to which this field is to be set
   */
  @Inline
  public static void setFreeListMeta(Address address, Address value) {
    getMetaAddress(address).plus(FL_META_OFFSET).store(value);
  }

  /**
   * Get the free list meta data field for a given address (this is
   * per-block meta data that is stored along with the block metadata
   * but not used by the block allocator).
   *
   * @param address The address of interest
   * @return The free list meta data field for the block containing
   * the given address
   */
  @Inline
  public static Address getFreeListMeta(Address address) {
    return getMetaAddress(address).plus(FL_META_OFFSET).loadAddress();
  }

  /**
   * Set the <i>prev</i> meta data field for a given address
   *
   * @param address The address of interest
   * @param prev The value to which this field is to be set
   */
  @Inline
  public static void setNext(Address address, Address prev) {
    getMetaAddress(address, NEXT_OFFSET).store(prev);
  }

  /**
   * Get the <i>prev</i> meta data field for a given address
   *
   * @param address The address of interest
   * @return The prev field for the block containing the given address
   */
  @Inline
  public static Address getNext(Address address) {
    return getMetaAddress(address, NEXT_OFFSET).loadAddress();
  }

  /**
   * Get the address of some metadata given the address for which the
   * metadata is required and the offset into the metadata that is of
   * interest.
   *
   * @param address The address for which the metadata is required
   * @return The address of the specified meta data
   */
  @Inline
  private static Address getMetaAddress(Address address) {
    return getMetaAddress(address, Offset.zero());
  }

  /**
   * Get the address of some metadata given the address for which the
   * metadata is required and the offset into the metadata that is of
   * interest.
   *
   * @param address The address for which the metadata is required
   * @param offset The offset (in bytes) into the metadata block (eg
   * for the prev pointer, or next pointer)
   * @return The address of the specified meta data
   */
  @Inline
  private static Address getMetaAddress(Address address, Offset offset) {
    return EmbeddedMetaData.getMetaDataBase(address).plus(
           EmbeddedMetaData.getMetaDataOffset(address, LOG_BYTE_COVERAGE, LOG_BYTES_IN_BLOCK_META)).plus(offset);
  }

  /****************************************************************************
   *
   * Block marking
   */

  /**
   * Mark the metadata for this block.
   *
   * @param ref
   */
  @Inline
  public static void markBlockMeta(ObjectReference ref) {
    getMetaAddress(VM.objectModel.refToAddress(ref)).plus(FL_META_OFFSET).store(Word.one());
  }

  /**
   * Mark the metadata for this block.
   *
   * @param block The block address
   */
  @Inline
  public static void markBlockMeta(Address block) {
    getMetaAddress(block).plus(FL_META_OFFSET).store(Word.one());
  }

  /**
   * Return true if the metadata for this block was set.
   *
   * @param block The block address
   * @return value of the meta data.
   */
  @Inline
  public static boolean checkBlockMeta(Address block) {
    return getMetaAddress(block).plus(FL_META_OFFSET).loadWord().EQ(Word.one());
  }

  /**
   * Clear the metadata for this block
   *
   * @param block The block address
   */
  @Inline
  public static void clearBlockMeta(Address block) {
    getMetaAddress(block).plus(FL_META_OFFSET).store(Word.zero());
  }
}