Menu
▾
▴
[rvm-commits] SF.net SVN: jikesrvm: [13518] rvmroot/trunk/MMTk/src/org/mmtk/utility
|
From: <ste...@us...> - 2007-09-08 03:29:55
|
Revision: 13518
http://jikesrvm.svn.sourceforge.net/jikesrvm/?rev=13518&view=rev
Author: steveb-oss
Date: 2007-09-07 20:29:51 -0700 (Fri, 07 Sep 2007)
Log Message:
-----------
Clean up and generalize generic free list
Modified Paths:
--------------
rvmroot/trunk/MMTk/src/org/mmtk/utility/BaseGenericFreeList.java
rvmroot/trunk/MMTk/src/org/mmtk/utility/GenericFreeList.java
Removed Paths:
-------------
rvmroot/trunk/MMTk/src/org/mmtk/utility/SmallGenericFreeList.java
Modified: rvmroot/trunk/MMTk/src/org/mmtk/utility/BaseGenericFreeList.java
===================================================================
--- rvmroot/trunk/MMTk/src/org/mmtk/utility/BaseGenericFreeList.java 2007-09-07 12:37:17 UTC (rev 13517)
+++ rvmroot/trunk/MMTk/src/org/mmtk/utility/BaseGenericFreeList.java 2007-09-08 03:29:51 UTC (rev 13518)
@@ -105,11 +105,11 @@
*/
public final int alloc(int size) {
// Note: -1 is both the default return value *and* the start sentinel index
- int rtn = HEAD; // HEAD = -1
+ int unit = head; // HEAD = -1
int s = 0;
- while (((rtn = getNext(rtn)) != HEAD) && ((s = getSize(rtn)) < size));
+ while (((unit = getNext(unit)) != head) && ((s = getSize(unit)) < size));
- return alloc(size, rtn, s);
+ return alloc(size, unit, s);
}
/**
@@ -120,10 +120,10 @@
*/
public final boolean couldAlloc(int size) {
// Note: -1 is both the default return value *and* the start sentinel index
- int rtn = HEAD; // HEAD = -1
- while (((rtn = getNext(rtn)) != HEAD) && (getSize(rtn) < size));
+ int unit = head; // HEAD = -1
+ while (((unit = getNext(unit)) != head) && (getSize(unit) < size));
- return (rtn != -1);
+ return (unit != head);
}
/**
@@ -139,7 +139,7 @@
if (getFree(unit) && (s = getSize(unit)) >= size)
return alloc(size, unit, s);
else
- return HEAD;
+ return FAILURE;
}
/**
@@ -158,6 +158,7 @@
}
if (DEBUG) dbgPrintFree();
+
return unit;
}
@@ -165,6 +166,7 @@
* Free a previously allocated contiguous lump of units.
*
* @param unit The index of the first unit.
+ * @param returnCoalescedSize TODO
* @return The number of units freed.
*/
public final int free(int unit) {
@@ -173,9 +175,9 @@
int end = getFree(getRight(unit)) ? getRight(unit) : unit;
if (start != end)
coalesce(start, end);
+
addToFree(start);
if (DEBUG) dbgPrintFree();
-
return freed;
}
@@ -211,8 +213,9 @@
* @param units The number of units in the heap
*/
protected final void initializeHeap(int units, int grain) {
- // Initialize the sentiels
- setSentinel(-1);
+ // Initialize the sentinels
+ for (int i = 1; i <= heads; i++)
+ setSentinel(-i);
setSentinel(units);
// create the free list item
@@ -243,6 +246,7 @@
setSize(unit, size);
setSize(unit + size, basesize - size);
addToFree(unit + size);
+ if (DEBUG) dbgPrintFree();
}
/**
@@ -267,10 +271,10 @@
*/
private void addToFree(int unit) {
setFree(unit, true);
- int next = getNext(HEAD);
+ int next = getNext(head);
setNext(unit, next);
- setNext(HEAD, unit);
- setPrev(unit, HEAD);
+ setNext(head, unit);
+ setPrev(unit, head);
setPrev(next, unit);
}
@@ -284,6 +288,7 @@
int prev = getPrev(unit);
setNext(prev, next);
setPrev(next, prev);
+ if (DEBUG) dbgPrintFree();
}
/**
@@ -304,8 +309,8 @@
void dbgPrintFree() {
if (DEBUG) {
Log.write("FL[");
- int i = HEAD;
- while ((i = getNext(i)) != HEAD) {
+ int i = head;
+ while ((i = getNext(i)) != head) {
boolean f = getFree(i);
int s = getSize(i);
if (!f)
@@ -313,9 +318,9 @@
Log.write(i);
if (!f)
Log.write("<-");
- Log.write("[");
+ Log.write("(");
Log.write(s);
- Log.write("]");
+ Log.write(")");
Log.write(" ");
Log.flush();
}
@@ -335,5 +340,8 @@
abstract int getLeft(int unit);
protected static final boolean DEBUG = false;
- protected static final int HEAD = -1;
+ protected static final int FAILURE = -1;
+
+ protected int heads = 1;
+ protected int head = -heads;
}
Modified: rvmroot/trunk/MMTk/src/org/mmtk/utility/GenericFreeList.java
===================================================================
--- rvmroot/trunk/MMTk/src/org/mmtk/utility/GenericFreeList.java 2007-09-07 12:37:17 UTC (rev 13517)
+++ rvmroot/trunk/MMTk/src/org/mmtk/utility/GenericFreeList.java 2007-09-08 03:29:51 UTC (rev 13518)
@@ -98,26 +98,65 @@
/**
* 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) {
if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(units <= MAX_UNITS);
+ this.heads = heads;
+ head = -1;
// allocate the data structure, including space for top & bottom sentinels
- table = new int[(units + 2) << 1];
+ table = new int[(units + 1 + heads) << 1];
initializeHeap(units, grain);
}
/**
+ * 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.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 initilized
+ * @param unit The unit to be initialized
*/
protected void setSentinel(int unit) {
- setLoEntry(unit, SENTINEL_LO_INIT);
- setHiEntry(unit, SENTINEL_HI_INIT);
+ setLoEntry(unit, NEXT_MASK & unit);
+ setHiEntry(unit, PREV_MASK & unit);
}
/**
@@ -186,7 +225,7 @@
*/
protected int getNext(int unit) {
int next = getHiEntry(unit) & NEXT_MASK;
- return (next <= MAX_UNITS) ? next : HEAD;
+ return (next <= MAX_UNITS) ? next : head;
}
/**
@@ -196,9 +235,9 @@
* @param next The value to be set.
*/
protected void setNext(int unit, int next) {
- if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((next >= HEAD) && (next <= MAX_UNITS));
+ if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((next >= -heads) && (next <= MAX_UNITS));
int oldValue = getHiEntry(unit);
- int newValue = (next == HEAD) ? (oldValue | NEXT_MASK) : ((oldValue & ~NEXT_MASK) | next);
+ int newValue = (oldValue & ~NEXT_MASK) | (next & NEXT_MASK);
setHiEntry(unit, newValue);
}
@@ -211,7 +250,7 @@
*/
protected int getPrev(int unit) {
int prev = getLoEntry(unit) & PREV_MASK;
- return (prev <= MAX_UNITS) ? prev : HEAD;
+ return (prev <= MAX_UNITS) ? prev : head;
}
/**
@@ -221,11 +260,10 @@
* @param prev The value to be set.
*/
protected void setPrev(int unit, int prev) {
- if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((prev >= HEAD) && (prev <= MAX_UNITS));
- if (prev == HEAD)
- setLoEntry(unit, (getLoEntry(unit) | PREV_MASK));
- else
- setLoEntry(unit, (getLoEntry(unit) & ~PREV_MASK) | 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);
}
/**
@@ -249,10 +287,10 @@
* @return The contents of the unit
*/
private int getLoEntry(int unit) {
- return table[(unit + 1) << 1];
+ return table[(unit + heads) << 1];
}
private int getHiEntry(int unit) {
- return table[((unit + 1) << 1) + 1];
+ return table[((unit + heads) << 1) + 1];
}
/**
@@ -262,10 +300,10 @@
* @param value The contents of the unit
*/
private void setLoEntry(int unit, int value) {
- table[(unit + 1) << 1] = value;
+ table[(unit + heads) << 1] = value;
}
private void setHiEntry(int unit, int value) {
- table[((unit + 1) << 1) + 1] = value;
+ table[((unit + heads) << 1) + 1] = value;
}
private static final int TOTAL_BITS = 32;
@@ -277,10 +315,5 @@
private static final int MULTI_MASK = 1 << (TOTAL_BITS - 1);
private static final int SIZE_MASK = (int) ((((long) 1) << UNIT_BITS) - 1);
- // want the sentinels to be "used" & "single", and want first
- // sentinel to initially point to itself.
- private static final int SENTINEL_LO_INIT = PREV_MASK;
- private static final int SENTINEL_HI_INIT = NEXT_MASK;
-
private int[] table;
}
Deleted: rvmroot/trunk/MMTk/src/org/mmtk/utility/SmallGenericFreeList.java
===================================================================
--- rvmroot/trunk/MMTk/src/org/mmtk/utility/SmallGenericFreeList.java 2007-09-07 12:37:17 UTC (rev 13517)
+++ rvmroot/trunk/MMTk/src/org/mmtk/utility/SmallGenericFreeList.java 2007-09-08 03:29:51 UTC (rev 13518)
@@ -1,278 +0,0 @@
-/*
- * This file is part of the Jikes RVM project (http://jikesrvm.org).
- *
- * This file is licensed to You under the Common Public License (CPL);
- * 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/cpl1.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.Uninterruptible;
-
-/**
- * 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 final class SmallGenericFreeList extends BaseGenericFreeList implements Constants {
-
- /****************************************************************************
- *
- * Public instance methods
- */
-
- /**
- * Constructor
- */
- SmallGenericFreeList(int units) {
- if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(units <= MAX_UNITS);
-
- // allocate the data structure, including space for top & bottom sentinels
- table = new int[units + 2];
-
- initializeHeap(units);
- }
-
- /**
- * Initialize a unit as a sentinel
- *
- * @param unit The unit to be initilized
- */
- protected void setSentinel(int unit) {
- setEntry(unit, SENTINEL_INIT);
- }
-
- /**
- * 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 ((getEntry(unit) & MULTI_MASK) == MULTI_MASK)
- return (getEntry(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) {
- setEntry(unit, getEntry(unit) | MULTI_MASK);
- setEntry(unit + 1, MULTI_MASK | size);
- setEntry(unit + size - 1, MULTI_MASK | size);
- } else
- setEntry(unit, getEntry(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 ((getEntry(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) {
- setEntry(unit, getEntry(unit) | FREE_MASK);
- if ((size = getSize(unit)) > 1)
- setEntry(unit + size - 1, getEntry(unit + size - 1) | FREE_MASK);
- } else {
- setEntry(unit, getEntry(unit) & ~FREE_MASK);
- if ((size = getSize(unit)) > 1)
- setEntry(unit + size - 1, getEntry(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 = getEntry(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 >= HEAD) && (next <= MAX_UNITS));
- if (next == HEAD)
- setEntry(unit, (getEntry(unit) | NEXT_MASK));
- else
- setEntry(unit, (getEntry(unit) & ~NEXT_MASK) | next);
- }
-
- /**
- * 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 = (getEntry(unit) & PREV_MASK) >> PREV_SHIFT;
- 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 >= HEAD) && (prev <= MAX_UNITS));
- if (prev == HEAD)
- setEntry(unit, (getEntry(unit) | PREV_MASK));
- else
- setEntry(unit, (getEntry(unit) & ~PREV_MASK) | (prev << PREV_SHIFT));
- }
-
- /**
- * 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 ((getEntry(unit - 1) & MULTI_MASK) == MULTI_MASK)
- return unit - (getEntry(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 getEntry(int unit) {
- return table[unit + 1];
- }
-
- /**
- * Set the contents of an entry
- *
- * @param unit The index of the unit
- * @param value The contents of the unit
- */
- private void setEntry(int unit, int value) {
- table[unit + 1] = value;
- }
-
- private static final int TOTAL_BITS = 32;
- private static final int UNIT_BITS = (TOTAL_BITS - 2) >> 1;
- private static final int MAX_UNITS = ((1 << UNIT_BITS) - 1) - 1;
- private static final int NEXT_MASK = (1 << UNIT_BITS) - 1;
- private static final int PREV_SHIFT = UNIT_BITS;
- private static final int PREV_MASK = ((1 << UNIT_BITS) - 1) << PREV_SHIFT;
- private static final int FREE_MASK = 1 << (TOTAL_BITS - 1);
- private static final int MULTI_MASK = 1 << (TOTAL_BITS - 2);
- private static final int SIZE_MASK = (1 << UNIT_BITS) - 1;
-
- // want the sentinels to be "used" & "single", and want first
- // sentinel to initially point to itself.
- private static final int SENTINEL_INIT = NEXT_MASK | PREV_MASK;
-
- private int[] table;
-}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|