vmkit/mmtk/java/src/org/mmtk/utility/GenericFreeList.java

/*
 *  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;

import org.mmtk.plan.Plan;
import org.mmtk.vm.VM;

import org.vmmagic.pragma.*;

/**
 * This is a very simple, generic malloc-free allocator.  It works
 * abstractly, in "units", which the user may associate with some
 * other allocatable resource (e.g. heap blocks).  The user issues
 * requests for N units and the allocator returns the index of the
 * first of a contiguous set of N units or fails, returning -1.  The
 * user frees the block of N units by calling <code>free()</code> with
 * the index of the first unit as the argument.<p>
 *
 * Properties/Constraints:<ul>
 *   <li> The allocator consumes one word per allocatable unit (plus
 *   a fixed overhead of about 128 words).</li>
 *   <li> The allocator can only deal with MAX_UNITS units (see below for
 *   the value).</li>
 * </ul>
 *
 * The basic data structure used by the algorithm is a large table,
 * with one word per allocatable unit.  Each word is used in a
 * number of different ways, some combination of "undefined" (32),
 * "free/used" (1), "multi/single" (1), "prev" (15), "next" (15) &
 * "size" (15) where field sizes in bits are in parenthesis.
 * <pre>
 *                       +-+-+-----------+-----------+
 *                       |f|m|    prev   | next/size |
 *                       +-+-+-----------+-----------+
 *
 *   - single free unit: "free", "single", "prev", "next"
 *   - single used unit: "used", "single"
 *    - contiguous free units
 *     . first unit: "free", "multi", "prev", "next"
 *     . second unit: "free", "multi", "size"
 *     . last unit: "free", "multi", "size"
 *    - contiguous used units
 *     . first unit: "used", "multi", "prev", "next"
 *     . second unit: "used", "multi", "size"
 *     . last unit: "used", "multi", "size"
 *    - any other unit: undefined
 *
 *                       +-+-+-----------+-----------+
 *   top sentinel        |0|0|    tail   |   head    |  [-1]
 *                       +-+-+-----------+-----------+
 *                                     ....
 *            /--------  +-+-+-----------+-----------+
 *            |          |1|1|   prev    |   next    |  [j]
 *            |          +-+-+-----------+-----------+
 *            |          |1|1|           |   size    |  [j+1]
 *         free multi    +-+-+-----------+-----------+
 *         unit block    |              ...          |  ...
 *            |          +-+-+-----------+-----------+
 *            |          |1|1|           |   size    |
 *           >--------  +-+-+-----------+-----------+
 *   single free unit    |1|0|   prev    |   next    |
 *           >--------  +-+-+-----------+-----------+
 *   single used unit    |0|0|                       |
 *           >--------  +-+-+-----------------------+
 *            |          |0|1|                       |
 *            |          +-+-+-----------+-----------+
 *            |          |0|1|           |   size    |
 *         used multi    +-+-+-----------+-----------+
 *         unit block    |              ...          |
 *            |          +-+-+-----------+-----------+
 *            |          |0|1|           |   size    |
 *            \--------  +-+-+-----------+-----------+
 *                                     ....
 *                       +-+-+-----------------------+
 *   bottom sentinel     |0|0|                       |  [N]
 *                       +-+-+-----------------------+
 * </pre>
 * The sentinels serve as guards against out of range coalescing
 * because they both appear as "used" blocks and so will never
 * coalesce.  The top sentinel also serves as the head and tail of
 * the doubly linked list of free blocks.
 */
@Uninterruptible
public final class GenericFreeList extends BaseGenericFreeList implements Constants {

  /****************************************************************************
   *
   * Public instance methods
   */

  /**
   * Constructor
   *
   * @param units The number of allocatable units for this free list
   */
  public GenericFreeList(int units) {
    this(units, units);
  }

  /**
   * Constructor
   *
   * @param units The number of allocatable units for this free list
   * @param grain Units are allocated such that they will never cross this granularity boundary
   */
  public GenericFreeList(int units, int grain) {
    this(units, grain, 1);
  }

  /**
   * Constructor
   *
   * @param units The number of allocatable units for this free list
   * @param grain Units are allocated such that they will never cross this granularity boundary
   * @param heads The number of free lists which will share this instance
   */
  public GenericFreeList(int units, int grain, int heads) {
    this.parent = null;
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(units <= MAX_UNITS && heads <= MAX_HEADS);
    this.heads = heads;
    head = -1;

    // allocate the data structure, including space for top & bottom sentinels
    table = new int[(units + 1 + heads) << 1];
    initializeHeap(units, grain);
  }

  /**
   * Resize the free list for a parent free list.
   * This must not be called dynamically (ie not after bootstrap).
   *
   * @param units The number of allocatable units for this free list
   * @param grain Units are allocated such that they will never cross this granularity boundary
   */
  @Interruptible
  public void resizeFreeList(int units, int grain) {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(parent == null && !Plan.isInitialized());
    table = new int[(units + 1 + heads) << 1];
    initializeHeap(units, grain);
  }

  /**
   * Resize the free list for a child free list.
   * This must not be called dynamically (ie not after bootstrap).
   */
  @Interruptible
  public void resizeFreeList() {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(parent != null && !Plan.isInitialized());
    table = parent.getTable();
  }

  /**
   * Constructor
   *
   * @param parent The parent, owning the data structures this instance will share
   * @param ordinal The ordinal number of this child
   */
  public GenericFreeList(GenericFreeList parent, int ordinal) {
    this.parent = parent;
    this.table = parent.getTable();
    this.heads = parent.getHeads();
    this.head = -(1 + ordinal);
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(-this.head <= this.heads);
  }

  /** Getter */
  int[] getTable() { return table; }
  int getHeads() { return heads; }

  /**
   * Initialize a unit as a sentinel
   *
   * @param unit The unit to be initialized
   */
  protected void setSentinel(int unit) {
    setLoEntry(unit, NEXT_MASK & unit);
    setHiEntry(unit, PREV_MASK & unit);
  }

  /**
   * Get the size of a lump of units
   *
   * @param unit The first unit in the lump of units
   * @return The size of the lump of units
   */
  protected int getSize(int unit) {
    if ((getHiEntry(unit) & MULTI_MASK) == MULTI_MASK)
      return (getHiEntry(unit + 1) & SIZE_MASK);
    else
      return 1;
  }

  /**
   * Set the size of lump of units
   *
   * @param unit The first unit in the lump of units
   * @param size The size of the lump of units
   */
  protected void setSize(int unit, int size) {
    if (size > 1) {
      setHiEntry(unit, getHiEntry(unit) | MULTI_MASK);
      setHiEntry(unit + 1, MULTI_MASK | size);
      setHiEntry(unit + size - 1, MULTI_MASK | size);
    } else
      setHiEntry(unit, getHiEntry(unit) & ~MULTI_MASK);
  }

  /**
   * Establish whether a lump of units is free
   *
   * @param unit The first or last unit in the lump
   * @return True if the lump is free
   */
  protected boolean getFree(int unit) {
    return ((getLoEntry(unit) & FREE_MASK) == FREE_MASK);
  }

  /**
   * Set the "free" flag for a lump of units (both the first and last
   * units in the lump are set.
   *
   * @param unit The first unit in the lump
   * @param isFree True if the lump is to be marked as free
   */
  protected void setFree(int unit, boolean isFree) {
    int size;
    if (isFree) {
      setLoEntry(unit, getLoEntry(unit) | FREE_MASK);
      if ((size = getSize(unit)) > 1)
        setLoEntry(unit + size - 1, getLoEntry(unit + size - 1) | FREE_MASK);
    } else {
      setLoEntry(unit, getLoEntry(unit) & ~FREE_MASK);
      if ((size = getSize(unit)) > 1)
        setLoEntry(unit + size - 1, getLoEntry(unit + size - 1) & ~FREE_MASK);
    }
  }

  /**
   * Get the next lump in the doubly linked free list
   *
   * @param unit The index of the first unit in the current lump
   * @return The index of the first unit of the next lump of units in the list
   */
  protected int getNext(int unit) {
    int next = getHiEntry(unit) & NEXT_MASK;
    return (next <= MAX_UNITS) ? next : head;
  }

  /**
   * Set the next lump in the doubly linked free list
   *
   * @param unit The index of the first unit in the lump to be set
   * @param next The value to be set.
   */
  protected void setNext(int unit, int next) {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((next >= -heads) && (next <= MAX_UNITS));
    int oldValue = getHiEntry(unit);
    int newValue = (oldValue & ~NEXT_MASK) | (next & NEXT_MASK);
    setHiEntry(unit, newValue);
  }

  /**
   * Get the previous lump in the doubly linked free list
   *
   * @param unit The index of the first unit in the current lump
   * @return The index of the first unit of the previous lump of units
   * in the list
   */
  protected int getPrev(int unit) {
    int prev = getLoEntry(unit) & PREV_MASK;
    return (prev <= MAX_UNITS) ? prev : head;
  }

  /**
   * Set the previous lump in the doubly linked free list
   *
   * @param unit The index of the first unit in the lump to be set
   * @param prev The value to be set.
   */
  protected void setPrev(int unit, int prev) {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((prev >= -heads) && (prev <= MAX_UNITS));
    int oldValue = getLoEntry(unit);
    int newValue = (oldValue & ~PREV_MASK) | (prev & PREV_MASK);
    setLoEntry(unit, newValue);
  }

  /**
   * Set the uncoalescable bit associated with this unit.
   * This ensures this unit cannot be coalesced with units below
   * it.
   *
   * @param unit The unit whose uncoalescable bit is to be set
   */
  public void setUncoalescable(int unit) {
    setLoEntry(unit, getLoEntry(unit) | COALESC_MASK);
  }

  /**
   * Clear the uncoalescable bit associated with this unit.
   * This allows this unit to be coalesced with units below
   * it.
   *
   * @param unit The unit whose uncoalescable bit is to be cleared
   */
  public void clearUncoalescable(int unit) {
    setLoEntry(unit, getLoEntry(unit) & ~COALESC_MASK);
  }

  /**
   * Return true if this unit may be coalesced with the unit below it.
   *
   * @param unit The unit in question
   * @return True if this unit may be coalesced with the unit below it.
   */
  @Override
  public boolean isCoalescable(int unit) {
    return (getLoEntry(unit) & COALESC_MASK) == 0;
  }

 /**
   * Get the lump to the "left" of the current lump (i.e. "above" it)
   *
   * @param unit The index of the first unit in the lump in question
   * @return The index of the first unit in the lump to the
   * "left"/"above" the lump in question.
   */
  protected int getLeft(int unit) {
    if ((getHiEntry(unit - 1) & MULTI_MASK) == MULTI_MASK)
      return unit - (getHiEntry(unit - 1) & SIZE_MASK);
    else
      return unit - 1;
  }


  /**
   * Get the contents of an entry
   *
   * @param unit The index of the unit
   * @return The contents of the unit
   */
  private int getLoEntry(int unit) {
    return table[(unit + heads) << 1];
  }
  private int getHiEntry(int unit) {
    return table[((unit + heads) << 1) + 1];
  }

  /**
   * Set the contents of an entry
   *
   * @param unit The index of the unit
   * @param value The contents of the unit
   */
  private void setLoEntry(int unit, int value) {
    table[(unit + heads) << 1] = value;
  }
  private void setHiEntry(int unit, int value) {
    table[((unit + heads) << 1) + 1] = value;
  }

  private static final int TOTAL_BITS = 32;
  private static final int UNIT_BITS = (TOTAL_BITS - 2);
  public static final int MAX_UNITS = (int) (((((long) 1) << UNIT_BITS) - 1) - MAX_HEADS - 1);
  private static final int NEXT_MASK = (int) ((((long) 1) << UNIT_BITS) - 1);
  private static final int PREV_MASK = (int) ((((long) 1) << UNIT_BITS) - 1);
  private static final int FREE_MASK = 1 << (TOTAL_BITS - 1);
  private static final int MULTI_MASK = 1 << (TOTAL_BITS - 1);
  private static final int COALESC_MASK = 1 << (TOTAL_BITS - 2);
  private static final int SIZE_MASK = (int) ((((long) 1) << UNIT_BITS) - 1);

  private int[] table;
  private final GenericFreeList parent;
}