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