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.deque;
014
015 import org.mmtk.policy.RawPageSpace;
016
017 import org.mmtk.vm.VM;
018
019 import org.vmmagic.pragma.*;
020 import org.vmmagic.unboxed.*;
021
022 /**
023 * This supports <i>unsynchronized</i> enqueuing and dequeuing of buffers
024 * for shared use. The data can be added to and removed from either end
025 * of the deque. This class is based upon the SharedQueue class. The sorting
026 * routines were modified from code written by Narendran Sachindran and
027 * Matthew Hertz for GCTk.
028 */
029 @Uninterruptible public abstract class SortSharedDeque extends SharedDeque {
030
031
032 private static final int BYTES_PUSHED = BYTES_IN_ADDRESS * 5;
033 private static final int MAX_STACK_SIZE = BYTES_PUSHED * 64;
034 private static final Offset INSERTION_SORT_LIMIT = Offset.fromIntSignExtend(80);
035
036 /***********************************************************************
037 *
038 * Class variables
039 */
040
041 /**
042 * Constructor
043 *
044 * @param rps The space from which the instance should obtain buffers.
045 */
046 public SortSharedDeque(String name, RawPageSpace rps, int arity) {
047 super(name, rps, arity);
048 stackBase = AddressArray.create(MAX_STACK_SIZE);
049 stackLoc = 0;
050 }
051
052 /***********************************************************************
053 *
054 * Sorting methods, utilities, and instance variables
055 */
056
057
058 /**
059 * Return the sorting key for the object passed as a parameter.
060 *
061 * @param obj The address of the object whose key is wanted
062 * @return The value of the sorting key for this object
063 */
064 protected abstract Word getKey(Address obj);
065
066 private static final Word mask16 = Word.fromIntZeroExtend(0xffff0000);
067 private static final Word mask8 = Word.fromIntZeroExtend(0x0000ff00);
068 private static final Word mask4 = Word.fromIntZeroExtend(0x000000f0);
069 private static final Word mask2 = Word.fromIntZeroExtend(0x0000000c);
070 private static final Word mask1 = Word.fromIntZeroExtend(0x00000002);
071
072 /**
073 * Find the highest bit that is set in a longword and return a mask
074 * with only that bit set.
075 *
076 * @param addr Value for which the mask needs to be found
077 * @return The highest bit set in the parameter
078 */
079 private static Word getBitMask(Word addr) {
080 int shift = 0;
081 if (!addr.and(mask16).isZero()) {
082 addr = addr.rshl(16);
083 shift += 16;
084 }
085 if (!addr.and(mask8).isZero()) {
086 addr = addr.rshl(8);
087 shift += 8;
088 }
089 if (!addr.and(mask4).isZero()) {
090 addr = addr.rshl(4);
091 shift += 4;
092 }
093 if (!addr.and(mask2).isZero()) {
094 addr = addr.rshl(2);
095 shift += 2;
096 }
097 if (!addr.and(mask1).isZero()) {
098 shift += 1;
099 }
100 return (Word.one().lsh(shift));
101 }
102
103 /**
104 * Perform insertion sort within an intra-block address range.
105 *
106 * @param begin Start address of the range to be sorted
107 * @param end End address of the range to be sorted
108 */
109 private void insertionSort(Address begin, Address end) {
110 Address rPtr = begin.minus(BYTES_IN_ADDRESS);
111 Address lPtr;
112
113 while (rPtr.GE(end)) {
114 Address rSlot = rPtr.loadAddress();
115 Word rKey = getKey(rSlot);
116 lPtr = rPtr.plus(BYTES_IN_ADDRESS);
117 while (lPtr.LE(begin)) {
118 Address lSlot = lPtr.loadAddress();
119 Word lKey = getKey(lSlot);
120 if (lKey.GT(rKey)) {
121 lPtr.minus(BYTES_IN_ADDRESS).store(lSlot);
122 lPtr = lPtr.plus(BYTES_IN_ADDRESS);
123 } else {
124 break;
125 }
126 }
127 lPtr.minus(BYTES_IN_ADDRESS).store(rSlot);
128 rPtr = rPtr.minus(BYTES_IN_ADDRESS);
129 }
130 }
131
132 /**
133 * Sort objects using radix exchange sort. An explicit stack is
134 * maintained to avoid using recursion.
135 */
136 public void sort() {
137 Address startPtr, startLink, endPtr, endLink;
138 Word bitMask;
139 if (!head.EQ(HEAD_INITIAL_VALUE)) {
140 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(tail.NE(TAIL_INITIAL_VALUE));
141 /* Obtain the bitmask for the first iteration and save the start &
142 end pointers and the bitmask on the stack */
143 initStack();
144 startPtr = popStack();
145 while (!startPtr.isZero()) {
146 startLink = popStack();
147 endPtr = popStack();
148 endLink = popStack();
149 bitMask = (popStack()).toWord();
150 if (startLink.NE(endLink)) {
151 partition(startPtr, startLink, endPtr, endLink, bitMask);
152 } else if (startPtr.GT(endPtr)) {
153 /* Use insertionSort for a limited number of objects within
154 a single block */
155 if (startPtr.diff(endPtr).sLT(INSERTION_SORT_LIMIT)) {
156 insertionSort(startPtr, endPtr);
157 } else {
158 partition(startPtr, startLink, endPtr, endLink, bitMask);
159 }
160 }
161 // Get the next set of data to sort
162 startPtr = popStack();
163 }
164 }
165 checkIfSorted();
166 }
167
168 /**
169 * Partition the slots in an address range based on the value in
170 * a particular bit. Place the start & end addresses of the two
171 * partitions & a bitmask per partition (which indicates the highest
172 * bit position at which the max & min of a partition differ) on the
173 * stack. This works just like the partition in quick sort, except
174 * that a bit value is being compared here
175 *
176 * @param startAddr The start address of the range to be sorted
177 * @param startLinkAddr The address where the start block has its next field
178 * @param endAddr The end address of the range to be sorted
179 * @param endLinkAddr The address where the end block has its next field
180 * @param bitMask The mask in which the bit to be commpared is set
181 */
182 private void partition(Address startAddr, Address startLinkAddr,
183 Address endAddr, Address endLinkAddr,
184 Word bitMask) {
185 Address travPtr = endAddr;
186 Address travLink = endLinkAddr;
187 Address stopPtr = startAddr;
188 Address stopLink = startLinkAddr;
189 Address travSlot, stopSlot;
190 Word travKey, stopKey;
191 Word lmax = Word.zero(), rmax = Word.zero();
192 Word lmin = Word.max(), rmin = Word.max();
193
194 while (true) {
195 /* Compute the address range within the current block to compute. */
196 Address endOfBlock = travLink;
197
198 /* Move the left pointer until the right pointer is reached
199 or an address with a 0 value in the bit position is found. */
200 while (true) {
201 travSlot = travPtr.loadAddress();
202 travKey = getKey(travSlot);
203
204 /* If we reach the end. */
205 if (travPtr.EQ(stopPtr))
206 break;
207 /* If we found a 0 in bit position, break. */
208 if (travKey.and(bitMask).isZero())
209 break;
210 if (travKey.GT(rmax))
211 rmax = travKey;
212 if (travKey.LT(rmin))
213 rmin = travKey;
214 /* Move to the next entry. */
215 travPtr = travPtr.plus(BYTES_IN_ADDRESS);
216 /* If at end of remset block, move to next block */
217 if (travPtr.EQ(endOfBlock)) {
218 travLink = getPrev(travPtr);
219 endOfBlock = travLink;
220 travPtr = bufferStart(endOfBlock);
221 }
222 }
223
224 /* Store the end of the block. */
225 endOfBlock = bufferStart(stopPtr);
226 /* Move the right pointer until the left pointer is reached
227 or an address with a 1 value in the bit position is found. */
228 while (true) {
229 stopSlot = stopPtr.loadAddress();
230 stopKey = getKey(stopSlot);
231 /* Found a 1 in bit position, break. */
232 if (!stopKey.and(bitMask).isZero())
233 break;
234 if (stopKey.GT(lmax))
235 lmax = stopKey;
236 if (stopKey.LT(lmin))
237 lmin = stopKey;
238 if (stopPtr.EQ(travPtr))
239 break;
240 /* Move to the next entry, which may be in the next block. */
241 if (stopPtr.EQ(endOfBlock)) {
242 stopLink = getNext(stopLink);
243 stopPtr = stopLink;
244 endOfBlock = bufferStart(stopPtr);
245 }
246 stopPtr = stopPtr.minus(BYTES_IN_ADDRESS);
247 }
248 if (stopPtr.EQ(travPtr))
249 break;
250 /* interchange the values pointed to by the left and right pointers */
251 travPtr.store(stopSlot);
252 stopPtr.store(travSlot);
253 }
254
255 /* If max value is not equal to the min value in the right partition,
256 (not all slots are identical) push the right partition on to the stack */
257 if (rmax.GT(rmin)) {
258 if (travPtr.EQ(bufferStart(travPtr))) {
259 stopLink = getNext(travLink);
260 stopPtr = stopLink;
261 } else {
262 stopLink = travLink;
263 stopPtr = travPtr;
264 }
265 pushOnStack(getBitMask(rmax.xor(rmin)).toAddress());
266 pushOnStack(endLinkAddr);
267 pushOnStack(endAddr);
268 pushOnStack(stopLink);
269 pushOnStack(stopPtr.minus(BYTES_IN_ADDRESS));
270 }
271 /* if max value is not equal to the min value in the left partition,
272 (not all slots are identical) push the left partition on to the stack */
273 if (lmax.GT(lmin)) {
274 pushOnStack(getBitMask(lmax.xor(lmin)).toAddress());
275 pushOnStack(travLink);
276 pushOnStack(travPtr);
277 pushOnStack(startLinkAddr);
278 pushOnStack(startAddr);
279 }
280 }
281
282 /*************************************************************************
283 *
284 * Sorting Stack management routines
285 */
286
287 /**
288 *
289 */
290 private int stackLoc;
291 private AddressArray stackBase;
292
293 /*
294 * Allocate memory for the stack and initialize it with the first range
295 * to partition
296 */
297 private void initStack() {
298 stackLoc = 0;
299
300 Address endOfBlock = tail;
301 Address startPtr = bufferStart(endOfBlock);
302 Word min = Word.max();
303 Word max = Word.zero();
304 // Find the max. and min addresses in the object buffer
305 while (endOfBlock.NE(HEAD_INITIAL_VALUE)) {
306 startPtr = bufferStart(endOfBlock);
307 while (startPtr.LT(endOfBlock)) {
308 Address startSlot = startPtr.loadAddress();
309 Word startKey = getKey(startSlot);
310 if (startKey.GT(max))
311 max = startKey;
312 if (startKey.LT(min))
313 min = startKey;
314 startPtr = startPtr.plus(BYTES_IN_ADDRESS);
315 }
316 endOfBlock = getPrev(startPtr);
317 }
318
319 // If max and min are different (not all elements are equal), push the
320 // start, end and bitmask values on the stack
321 if (max.GT(min)) {
322 pushOnStack(getBitMask(max.xor(min)).toAddress());
323 pushOnStack(tail);
324 pushOnStack(bufferStart(tail));
325 pushOnStack(startPtr);
326 pushOnStack(startPtr.minus(BYTES_IN_ADDRESS));
327 }
328 }
329
330 /**
331 * Push an address on to the stack
332 *
333 * @param val The address to be pushed
334 */
335 private void pushOnStack(Address val) {
336 stackBase.set(stackLoc, val);
337 stackLoc++;
338 }
339
340 /**
341 * Pop an address from the stack
342 *
343 * @return The address at the top of the stack, or 0 if stack is empty
344 */
345 private Address popStack() {
346 if (stackLoc == 0)
347 return Address.zero();
348 stackLoc--;
349 return stackBase.get(stackLoc);
350 }
351
352 /**
353 * Debug routine, used to check if the object buffer is sorted correctly in
354 * decreasing final reference deletion time
355 */
356 private void checkIfSorted() {
357 if (VM.VERIFY_ASSERTIONS) {
358 Address buf, end;
359 Word prevKey = Word.max();
360 end = tail;
361 buf = bufferStart(end);
362 while (buf.NE(HEAD_INITIAL_VALUE)) {
363 // iterate through the block
364 while (buf.LT(end)) {
365 Address slot = buf.loadAddress();
366 Word key = getKey(slot);
367 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(key.LE(prevKey));
368 prevKey = key;
369 buf = buf.plus(BYTES_IN_ADDRESS);
370 }
371 end = getPrev(end);
372 buf = bufferStart(end);
373 }
374 }
375 }
376 }