001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.mmtk.utility;
014
015 import org.mmtk.utility.gcspy.drivers.AbstractDriver;
016
017 import org.mmtk.vm.Lock;
018 import org.mmtk.vm.VM;
019
020 import org.vmmagic.pragma.*;
021 import org.vmmagic.unboxed.*;
022
023 /**
024 * FIXME This class must be re-written as it makes the assumption that
025 * the implementation language (Java) and the language being
026 * implemented are the same. This is true in the case of Jikes RVM,
027 * but it is not true for any VM implementing a language other than
028 * Java.
029 *
030 *
031 * Each instance of this class is a doubly-linked list, in which
032 * each item or node is a piece of memory. The first two words of each node
033 * contains the forward and backward links. The third word contains
034 * the treadmill. The remaining portion is the payload.
035 *
036 * The treadmill object itself must not be moved.
037 *
038 * Access to the instances may be synchronized depending on the
039 * constructor argument.
040 */
041 @Uninterruptible public final class DoublyLinkedList implements Constants {
042
043 /****************************************************************************
044 *
045 * Class variables
046 */
047
048 /****************************************************************************
049 *
050 * Instance variables
051 */
052 private Address head;
053 private final Lock lock;
054 private final int logGranularity; // Each node on the treadmill is guaranteed to be a multiple of granularity.
055
056 /****************************************************************************
057 *
058 * Instance Methods
059 */
060
061 /**
062 * Constructor
063 */
064 public DoublyLinkedList(int logGranularity, boolean shared) {
065 head = Address.zero();
066 lock = shared ? VM.newLock("DoublyLinkedList") : null;
067 this.logGranularity = logGranularity;
068
069 // ensure that granularity is big enough for midPayloadToNode to work
070 Word tmp = Word.one().lsh(logGranularity);
071 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(tmp.and(nodeMask).EQ(tmp));
072 }
073
074 // Offsets are relative to the node (not the payload)
075 //
076 private static final Offset PREV_OFFSET = Offset.fromIntSignExtend(0 * BYTES_IN_ADDRESS);
077 private static Offset NEXT_OFFSET = Offset.fromIntSignExtend(1 * BYTES_IN_ADDRESS);
078 private static Offset HEADER_SIZE = Offset.fromIntSignExtend(2 * BYTES_IN_ADDRESS);
079
080 private static final Word nodeMask;
081 static {
082 Word mask = Word.one();
083 while (mask.LE(HEADER_SIZE.plus(MAX_BYTES_PADDING).toWord())) mask = mask.lsh(1);
084 nodeMask = mask.minus(Word.one()).not();
085 }
086
087 @Inline
088 public static int headerSize() {
089 return HEADER_SIZE.toInt();
090 }
091
092 public boolean isNode(Address node) {
093 return node.toWord().rshl(logGranularity).lsh(logGranularity).EQ(node.toWord());
094 }
095
096 @Inline
097 public static Address nodeToPayload(Address node) {
098 return node.plus(HEADER_SIZE);
099 }
100
101 @Inline
102 public static Address midPayloadToNode(Address payload) {
103 // This method words as long as you are less than MAX_BYTES_PADDING into the payload.
104 return payload.toWord().and(nodeMask).toAddress();
105 }
106
107 @Inline
108 public void add(Address node) {
109 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isNode(node));
110 if (lock != null) lock.acquire();
111 node.store(Address.zero(), PREV_OFFSET);
112 node.store(head, NEXT_OFFSET);
113 if (!head.isZero())
114 head.store(node, PREV_OFFSET);
115 head = node;
116 if (lock != null) lock.release();
117 }
118
119 @Inline
120 public void remove(Address node) {
121 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isNode(node));
122 if (lock != null) lock.acquire();
123 Address prev = node.loadAddress(PREV_OFFSET);
124 Address next = node.loadAddress(NEXT_OFFSET);
125 // Splice the node out of the list
126 if (!next.isZero())
127 next.store(prev, PREV_OFFSET);
128 if (prev.isZero())
129 head = next;
130 else
131 prev.store(next, NEXT_OFFSET);
132 // Null out node's reference to the list
133 node.store(Address.zero(), PREV_OFFSET);
134 node.store(Address.zero(), NEXT_OFFSET);
135 if (lock != null) lock.release();
136 }
137
138 @Inline
139 public Address getHead() {
140 return head;
141 }
142
143 @Inline
144 public Address getNext(Address node) {
145 return node.loadAddress(NEXT_OFFSET);
146 }
147
148 @Inline
149 public Address pop() {
150 Address first = head;
151 if (!first.isZero())
152 remove(first);
153 return first;
154 }
155
156 @Inline
157 public boolean isEmpty() {
158 return head.isZero();
159 }
160
161 /**
162 * Return true if a cell is on a given treadmill
163 *
164 * @param node The cell being searched for
165 * @return True if the cell is found on the treadmill
166 */
167 public boolean isMember(Address node) {
168 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isNode(node));
169 boolean result = false;
170 if (lock != null) lock.acquire();
171 Address cur = head;
172 while (!cur.isZero()) {
173 if (cur.EQ(node)) {
174 result = true;
175 break;
176 }
177 cur = cur.loadAddress(NEXT_OFFSET);
178 }
179 if (lock != null) lock.release();
180 return result;
181 }
182
183 public void show() {
184 if (lock != null) lock.acquire();
185 Address cur = head;
186 Log.write(cur);
187 while (!cur.isZero()) {
188 cur = cur.loadAddress(NEXT_OFFSET);
189 Log.write(" -> "); Log.write(cur);
190 }
191 Log.writeln();
192 if (lock != null) lock.release();
193 }
194
195
196 /**
197 * Gather data for GCSpy
198 * @param driver the GCSpy space driver
199 */
200 void gcspyGatherData(AbstractDriver driver) {
201 // GCSpy doesn't need a lock (in its stop the world config)
202 Address cur = head;
203 while (!cur.isZero()) {
204 driver.scan(cur);
205 cur = cur.loadAddress(NEXT_OFFSET);
206 }
207 }
208 }