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.plan.Plan;
016 import org.mmtk.utility.Constants;
017
018 import org.mmtk.vm.VM;
019
020 import org.vmmagic.pragma.*;
021 import org.vmmagic.unboxed.*;
022
023 /**
024 * This class implements a local (<i>unsynchronized</i>) sequential
025 * store buffer. An SSB is strictly FIFO (although this class does
026 * not implement dequeuing).<p>
027 *
028 * Each instance stores word-sized values into a local buffer. When
029 * the buffer is full, or if the <code>flushLocal()</code> method is
030 * called, the buffer enqueued at the tail of a
031 * <code>SharedDeque</code>. This class provides no mechanism for
032 * dequeing.<p>
033 *
034 * The implementation is intended to be as efficient as possible, in
035 * time and space, as it is used in critical code such as the GC work
036 * queue and the write buffer used by many "remembering"
037 * collectors. Each instance has just two fields: a bump pointer and a
038 * pointer to the <code>SharedDeque</code><p>
039 *
040 * Preconditions: Buffers are always aligned on buffer-size address
041 * boundaries.<p>
042 *
043 * Invariants: Buffers are filled such that tuples (of the specified
044 * arity) are packed to the low end of the buffer. Thus buffer
045 * overflows on inserts and pops (underflow actually) will always arise
046 * when then cursor is buffer-size aligned.
047 */
048 @Uninterruptible class LocalSSB extends Deque implements Constants {
049
050 /****************************************************************************
051 *
052 * Public instance methods
053 */
054
055 /**
056 * Constructor
057 *
058 * @param queue The shared queue to which this local ssb will append
059 * its buffers (when full or flushed).
060 */
061 LocalSSB(SharedDeque queue) {
062 this.queue = queue;
063 resetLocal();
064 }
065
066 /**
067 * Flush the buffer and add it to the shared queue (this will
068 * make any entries in the buffer visible to any consumer associated
069 * with the shared queue).
070 */
071 public void flushLocal() {
072 if (tail.NE(Deque.TAIL_INITIAL_VALUE)) {
073 closeAndEnqueueTail(queue.getArity());
074 tail = Deque.TAIL_INITIAL_VALUE;
075 tailBufferEnd = Deque.TAIL_INITIAL_VALUE;
076 }
077 }
078
079 public void reset() {
080 resetLocal();
081 }
082
083 /****************************************************************************
084 *
085 * Protected instance methods and fields
086 */
087 @Entrypoint
088 protected Address tail; // the location in the buffer
089 protected Address tailBufferEnd; // the end of the buffer
090 protected final SharedDeque queue; // the shared queue
091
092 /**
093 * Reset the local buffer (throwing away any local entries).
094 */
095 public void resetLocal() {
096 tail = Deque.TAIL_INITIAL_VALUE;
097 tailBufferEnd = Deque.TAIL_INITIAL_VALUE;
098 }
099
100 /**
101 * Check whether there is space in the buffer for a pending insert.
102 * If there is not sufficient space, allocate a new buffer
103 * (dispatching the full buffer to the shared queue if not null).
104 *
105 * @param arity The arity of the values stored in this SSB: the
106 * buffer must contain enough space for this many words.
107 */
108 @Inline(value=Inline.When.AssertionsDisabled)
109 protected final void checkTailInsert(int arity) {
110 if (bufferOffset(tail).isZero())
111 tailOverflow(arity);
112 else if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(bufferOffset(tail).sGE(Word.fromIntZeroExtend(arity).lsh(LOG_BYTES_IN_ADDRESS).toOffset()));
113 }
114
115 /**
116 * Insert a value into the buffer. This is <i>unchecked</i>. The
117 * caller must first call <code>checkInsert()</code> to ensure the
118 * buffer can accommodate the insertion.
119 *
120 * @param value the value to be inserted.
121 */
122 @Inline(value=Inline.When.AssertionsDisabled)
123 protected final void uncheckedTailInsert(Address value) {
124 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(bufferOffset(tail).sGE(Offset.fromIntZeroExtend(BYTES_IN_ADDRESS)));
125 tail = tail.minus(BYTES_IN_ADDRESS);
126 tail.store(value);
127 // if (Interface.VerifyAssertions) enqueued++;
128 }
129
130 /**
131 * In the case where a buffer must be flushed before being
132 * filled (either to the queue or to the head), the entries must be
133 * slid to the base of the buffer in order to preserve the invariant
134 * that all non-tail buffers will have entries starting at the base
135 * (which allows a simple test against the base to be used when
136 * popping entries). This is <i>expensive</i>, so should be
137 * avoided.
138 *
139 * @param arity The arity of the buffer in question
140 * @return The last slot in the normalized buffer that contains an entry
141 */
142 protected final Address normalizeTail(int arity) {
143 Address src = tail;
144 Address tgt = bufferFirst(tail);
145 Address last = tgt.plus(bufferLastOffset(arity).minus(bufferOffset(tail)));
146 while (tgt.LE(last)) {
147 tgt.store(src.loadAddress());
148 src = src.plus(BYTES_IN_ADDRESS);
149 tgt = tgt.plus(BYTES_IN_ADDRESS);
150 }
151 return last;
152 }
153
154 /**
155 * Return the sentinel offset for a buffer of a given arity. This is used
156 * both to compute the address at the end of the buffer.
157 *
158 * @param arity The arity of this buffer
159 * @return The sentinel offset value for a buffer of the given arity.
160 */
161 @Inline
162 protected final Offset bufferSentinel(int arity) {
163 return bufferLastOffset(arity).plus(BYTES_IN_ADDRESS);
164 }
165
166 /****************************************************************************
167 *
168 * Private instance methods
169 */
170
171 /**
172 * Buffer space has been exhausted, allocate a new buffer and enqueue
173 * the existing buffer (if any).
174 *
175 * @param arity The arity of this buffer (used for sanity test only).
176 */
177 private void tailOverflow(int arity) {
178 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(arity == queue.getArity());
179 if (tail.NE(Deque.TAIL_INITIAL_VALUE)) {
180 closeAndEnqueueTail(arity);
181 }
182 tail = queue.alloc().plus(bufferSentinel(arity));
183 tailBufferEnd = tail;
184 Plan.checkForAsyncCollection(); // possible side-effect of alloc()
185 }
186
187 /**
188 * Close the tail buffer (normalizing if necessary), and enqueue it
189 * at the tail of the shared buffer queue.
190 *
191 * @param arity The arity of this buffer.
192 */
193 @NoInline
194 private void closeAndEnqueueTail(int arity) {
195 Address last;
196 if (!bufferOffset(tail).isZero()) {
197 // prematurely closed
198 last = normalizeTail(arity);
199 } else {
200 // a full tail buffer
201 last = tailBufferEnd.minus(BYTES_IN_ADDRESS);
202 }
203 queue.enqueue(last.plus(BYTES_IN_ADDRESS), arity, true);
204 }
205
206 /**
207 * Return true if this SSB is locally empty
208 *
209 * @return true if this SSB is locally empty
210 */
211 public final boolean isFlushed() {
212 return tail.EQ(Deque.TAIL_INITIAL_VALUE);
213 }
214 }