001 /*
002 Galois, a framework to exploit amorphous data-parallelism in irregular
003 programs.
004
005 Copyright (C) 2010, The University of Texas at Austin. All rights reserved.
006 UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS SOFTWARE
007 AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR ANY
008 PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF PERFORMANCE, AND ANY
009 WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF DEALING OR USAGE OF TRADE.
010 NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH RESPECT TO THE USE OF THE
011 SOFTWARE OR DOCUMENTATION. Under no circumstances shall University be liable
012 for incidental, special, indirect, direct or consequential damages or loss of
013 profits, interruption of business, or related expenses which may arise from use
014 of Software or Documentation, including but not limited to those resulting from
015 defects in Software and/or Documentation, or loss or inaccuracy of data of any
016 kind.
017
018
019 */
020
021 package galois.runtime;
022
023 import galois.objects.Lockable;
024 import galois.objects.MethodFlag;
025
026 import java.util.ArrayDeque;
027 import java.util.ArrayList;
028 import java.util.Deque;
029 import java.util.List;
030 import java.util.concurrent.atomic.AtomicReference;
031
032 /**
033 * Represents data accessed during an iteration.
034 */
035 public class Iteration {
036 private static ThreadLocal<Iteration> iteration = new ThreadLocal<Iteration>();
037 /**
038 * A list of any commit actions
039 */
040 private final Deque<Callback> commitActions;
041 private final List<ReleaseCallback> releaseActions;
042
043 /**
044 * A stack of callbacks to undo any actions the iteration has done
045 */
046 private final Deque<Callback> undoActions;
047
048 /**
049 * locked objects
050 */
051 private final List<Lockable> locked;
052
053 /**
054 * id of the iteration assigned on creation
055 */
056 private final int id;
057
058 public Iteration(int id) {
059 this.id = id;
060 this.undoActions = new ArrayDeque<Callback>();
061 this.releaseActions = new ArrayList<ReleaseCallback>();
062 this.commitActions = new ArrayDeque<Callback>();
063 this.locked = new ArrayList<Lockable>();
064 }
065
066 protected void reset() {
067 // Clear logs should have taken care of everything
068 }
069
070 /**
071 * Returns the currently executing iteration or null if no iteration is currently being
072 * executed.
073 *
074 * @return the current iteration
075 */
076 public static Iteration getCurrentIteration() {
077 return iteration.get();
078 }
079
080 /**
081 * Hack to set the current iteration being executed by a thread.
082 *
083 * @param it the current iteration
084 */
085 static void setCurrentIteration(Iteration it) {
086 iteration.set(it);
087 }
088
089 /**
090 * Acquires an <i> abstract lock</i> on the given object if <code>flags</code>
091 * contains {@link MethodFlag#CHECK_CONFLICT}. Returns the current iteration if
092 * <code>flags</code> contains {@link MethodFlag#CHECK_CONFLICT}.
093 *
094 * @param lockable the object to lock
095 * @param flags method flags
096 * @return the current iteration if <code>flags</code> contains {@link MethodFlag#CHECK_CONFLICT}
097 * @see #acquire(Lockable)
098 */
099 public static Iteration acquire(Lockable lockable, byte flags) {
100 Iteration it = null;
101 if (GaloisRuntime.needMethodFlag(flags, MethodFlag.CHECK_CONFLICT)) {
102 it = Iteration.getCurrentIteration();
103 it.acquire(lockable);
104 }
105 return it;
106 }
107
108 /**
109 * Acquires an <i>abstract lock</i> on the given object.
110 *
111 * @param lockable object to acquire an abstract lock on
112 */
113 public void acquire(Lockable lockable) {
114 AtomicReference<Iteration> owner = lockable.getOwner();
115
116 if (owner.get() == this) {
117 return;
118 }
119
120 while (!owner.compareAndSet(null, this)) {
121 GaloisRuntime.getRuntime().raiseConflict(this, owner.get());
122 }
123
124 locked.add(lockable);
125 }
126
127 void addCommitAction(Callback c) {
128 commitActions.addLast(c);
129 }
130
131 void addUndoAction(Callback c) {
132 undoActions.addFirst(c);
133 }
134
135 /**
136 * Add a new conflict log to the iteration (i.e. the iteration has made
137 * calls listed in this CL)
138 *
139 * @param cm
140 */
141 void addReleaseAction(ReleaseCallback callback) {
142 releaseActions.add(callback);
143 }
144
145 /**
146 * Clears undo logs, commit logs, conflict logs
147 */
148 protected int clearLogs(boolean releaseLocks) {
149 undoActions.clear();
150 commitActions.clear();
151
152 if (releaseLocks)
153 return releaseLocks();
154 else
155 return 0;
156 }
157
158 private int releaseLocks() {
159 int total = 0;
160 for (int i = 0; i < releaseActions.size(); i++) {
161 total += releaseActions.get(i).release(this);
162 }
163 releaseActions.clear();
164
165 for (int i = 0; i < locked.size(); i++) {
166 locked.get(i).getOwner().set(null);
167 total++;
168 }
169 locked.clear();
170 return total;
171 }
172
173 /**
174 * Called to abort an iteration. This unwinds the undo log, clears conflict
175 * logs and releases all held partitions
176 */
177 int performAbort() {
178 Callback c;
179 while ((c = undoActions.poll()) != null) {
180 c.call();
181 }
182
183 return clearLogs(true);
184 }
185
186 /**
187 * Commit iteration. This clears the conflict logs and releases any held
188 * partitions, and performs any commit actions
189 */
190 int performCommit(boolean releaseLocks) {
191 Callback c;
192 while ((c = commitActions.poll()) != null) {
193 c.call();
194 }
195
196 return clearLogs(releaseLocks);
197 }
198
199 /**
200 * Create a new iteration that reuses as much storage from this finished
201 * iteration as it can to reduce the need for garbage collection. Returns
202 * the new Iteration
203 */
204 Iteration recycle() {
205 reset();
206 return this;
207 }
208
209 public int getId() {
210 return id;
211 }
212 }