vmkit/mmtk/java/src/org/mmtk/utility/BaseGenericFreeList.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.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 abstract class BaseGenericFreeList implements Constants {

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

  /**
   * Allocate <code>size</code> units. Return the unit ID
   *
   * @param size  The number of units to be allocated
   * @return The index of the first of the <code>size</code>
   * contiguous units, or -1 if the request can't be satisfied
   */
  public final int alloc(int size) {
    // Note: -1 is both the default return value *and* the start sentinel index
    int unit = head; // HEAD = -1
    int s = 0;
    while (((unit = getNext(unit)) != head) && ((s = getSize(unit)) < size));

    return (unit == head) ? FAILURE : alloc(size, unit, s);
  }

  /**
   * Would an allocation of <code>size</code> units succeed?
   *
   * @param size The number of units to test for
   * @return True if such a request could be satisfied.
   */
  public final boolean couldAlloc(int size) {
    // Note: -1 is both the default return value *and* the start sentinel index
    int unit = head; // HEAD = -1
    while (((unit = getNext(unit)) != head) && (getSize(unit) < size));

    return (unit != head);
  }

  /**
   * Allocate <code>size</code> units. Return the unit ID
   *
   * @param size  The number of units to be allocated
   * @return The index of the first of the <code>size</code>
   * contiguous units, or -1 if the request can't be satisfied
   */
  public final int alloc(int size, int unit) {
    int s = 0;

    if (getFree(unit) && (s = getSize(unit)) >= size)
      return alloc(size, unit, s);
    else
      return FAILURE;
  }

  /**
   * Allocate <code>size</code> units. Return the unit ID
   *
   * @param size  The number of units to be allocated
   * @return The index of the first of the <code>size</code>
   * contiguous units, or -1 if the request can't be satisfied
   */
  private int alloc(int size, int unit, int unitSize) {
    if (unitSize >= size) {
      if (unitSize > size)
        split(unit, size);
      removeFromFree(unit);
      setFree(unit, false);
    }

    if (DEBUG) dbgPrintFree();

    return unit;
  }

  /**
   * Free a previously allocated contiguous lump of units.
   *
   * @param unit The index of the first unit.
   * @return return the size of the unit which was freed.
   */
  public final int free(int unit) {
    return free(unit, false);
  }

  /**
   * Free a previously allocated contiguous lump of units.
   *
   * @param unit The index of the first unit.
   * @param returnCoalescedSize if true, return the coalesced size
   * @return The number of units freed. if returnCoalescedSize is
   *  false, return the size of the unit which was freed.  Otherwise
   *   return the size of the unit now available (the coalesced size)
   */
  public final int free(int unit, boolean returnCoalescedSize) {
    int freed = getSize(unit);
    int left = getLeft(unit);
    int start = isCoalescable(unit) && getFree(left) ? left : unit;
    int right = getRight(unit);
    int end = isCoalescable(right) && getFree(right) ? right : unit;
    if (start != end)
      coalesce(start, end);

    if (returnCoalescedSize)
      freed = getSize(start);
    addToFree(start);

    if (DEBUG) dbgPrintFree();
    return freed;
  }

  /**
   * Return the size of the specified lump of units
   *
   * @param unit The index of the first unit in the lump.
   * @return The size of the lump, in units.
   */
  public final int size(int unit) {
    return getSize(unit);
  }

  /****************************************************************************
   *
   * Private fields and methods
   */

  /**
   * Initialize a new heap.  Fabricate a free list entry containing
   * everything
   *
   * @param units The number of units in the heap
   */
  protected final void initializeHeap(int units) {
    initializeHeap(units, units);
  }

  /**
   * Initialize a new heap.  Fabricate a free list entry containing
   * everything
   *
   * @param units The number of units in the heap
   */
  protected final void initializeHeap(int units, int grain) {
    // Initialize the sentinels
    for (int i = 1; i <= heads; i++)
      setSentinel(-i);
    setSentinel(units);

    // create the free list item
    int offset = units % grain;
    int cursor = units - offset;
    if (offset > 0) {
      setSize(cursor, offset);
      addToFree(cursor);
    }
    cursor -= grain;
    while (cursor >= 0) {
      setSize(cursor, grain);
      addToFree(cursor);
      cursor -= grain;
    }
    if (DEBUG) dbgPrintFree();
  }

  /**
   * Reduce a lump of units to size, freeing any excess.
   *
   * @param unit The index of the first unit
   * @param size The size of the first part
   */
  private void split(int unit, int size) {
    int basesize = getSize(unit);
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(basesize > size);
    setSize(unit, size);
    setSize(unit + size, basesize - size);
    addToFree(unit + size);
    if (DEBUG) dbgPrintFree();
  }

  /**
   * Coalesce two or three contiguous lumps of units, removing start
   * and end lumps from the free list as necessary.
   * @param start The index of the start of the first lump
   * @param end The index of the start of the last lump
   */
  private void coalesce(int start, int end) {
    if (getFree(end))
      removeFromFree(end);
    if (getFree(start))
      removeFromFree(start);

    setSize(start, end - start + getSize(end));
  }

  /**
   * Add a lump of units to the free list
   *
   * @param unit The first unit in the lump of units to be added
   */
  private void addToFree(int unit) {
    setFree(unit, true);
    int next = getNext(head);
    setNext(unit, next);
    setNext(head, unit);
    setPrev(unit, head);
    setPrev(next, unit);
  }

  /**
   * Remove a lump of units from the free list
   *
   * @param unit The first unit in the lump of units to be removed
   */
  private void removeFromFree(int unit) {
    int next = getNext(unit);
    int prev = getPrev(unit);
    setNext(prev, next);
    setPrev(next, prev);
    if (DEBUG) dbgPrintFree();
  }

  /**
   * Get the lump to the "right" of the current lump (i.e. "below" 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
   * "right"/"below" the lump in question.
   */
  private int getRight(int unit) {
    return unit + getSize(unit);
  }


  /**
   * Print the free list (for debugging purposes)
   */
  void dbgPrintFree() {
    if (DEBUG) {
      Log.write("FL[");
      int i = head;
      while ((i = getNext(i)) != head) {
        boolean f = getFree(i);
        int s = getSize(i);
        if (!f)
          Log.write("->");
        Log.write(i);
        if (!f)
          Log.write("<-");
        Log.write("(");
        Log.write(s);
        Log.write(")");
        Log.write(" ");
        Log.flush();
      }
      Log.writeln("]FL");
    }
  }

  abstract void setSentinel(int unit);
  abstract int getSize(int unit);
  abstract void setSize(int unit, int size);
  abstract boolean getFree(int unit);
  abstract void setFree(int unit, boolean isFree);
  abstract int getNext(int unit);
  abstract void setNext(int unit, int next);
  abstract int getPrev(int unit);
  abstract void setPrev(int unit, int prev);
  abstract int getLeft(int unit);
  abstract boolean isCoalescable(int unit);

  protected static final boolean DEBUG = false;
  public static final int FAILURE = -1;
  protected static final int MAX_HEADS = 128; // somewhat arbitrary

  protected int heads = 1;
  protected int head = -heads;
}