--- /dev/null
+package dstm2;
+
+/*
+ * AtomicArray.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+
+
+import TransactionalIO.exceptions.AbortedException;
+import TransactionalIO.exceptions.PanicException;
+import dstm2.factory.ofree.ReadSet;
+import java.lang.reflect.Array;
+
+/**
+ * @author mph
+ */
+@atomic public class AtomicArray<T> {
+
+ private final T[] array;
+ private final T[] shadow;
+ private Transaction writer;
+ private ReadSet readers;
+ long version;
+ private final String FORMAT = "Unexpected transaction state: %s";
+
+ /** Creates a new instance of AtomicArray */
+ public AtomicArray(Class _class, int capacity) {
+ array = (T[]) Array.newInstance(_class, capacity);
+ shadow = (T[]) Array.newInstance(_class, capacity);
+ writer = Transaction.COMMITTED;
+ readers = new ReadSet();
+ version = 0;
+ }
+
+ public T get(int i) {
+ Transaction me = Thread.getTransaction();
+ Transaction other = null;
+ ContentionManager manager = Thread.getContentionManager();
+ while (true) {
+ synchronized (this) {
+ other = openRead(me);
+ if (other == null) {
+ return array[i];
+ }
+ }
+ manager.resolveConflict(me, other);
+ }
+ }
+
+ public void set(int i, T value) {
+ Transaction me = Thread.getTransaction();
+ Transaction other = null;
+ ContentionManager manager = Thread.getContentionManager();
+ while (true) {
+ synchronized (this) {
+ other = openWrite(me);
+ if (other == null) {
+ array[i] = value;
+ return;
+ }
+ }
+ manager.resolveConflict(me, other);
+ }
+ }
+ /**
+ * Tries to open object for reading. Returns reference to conflictin transaction, if one exists
+ **/
+ private Transaction openRead(Transaction me) {
+ // not in a transaction
+ if (me == null) { // restore object if latest writer aborted
+ if (writer.isAborted()) {
+ restore();
+ version++;
+ writer = Transaction.COMMITTED;
+ }
+ return null;
+ }
+ // Am I still active?
+ if (!me.isActive()) {
+ throw new AbortedException();
+ }
+ // Have I already opened this object?
+ if (writer == me) {
+ return null;
+ }
+ switch (writer.getStatus()) {
+ case ACTIVE:
+ return writer;
+ case COMMITTED:
+ break;
+ case ABORTED:
+ restore();
+ version++;
+ break;
+ default:
+ throw new PanicException(FORMAT, writer.getStatus());
+ }
+ writer = Transaction.COMMITTED;
+ readers.add(me);
+ return null;
+ }
+
+ /**
+ * Tries to open object for reading. Returns reference to conflicting transaction, if one exists
+ **/
+ public Transaction openWrite(Transaction me) {
+ // not in a transaction
+ if (me == null) { // restore object if latest writer aborted
+ if (writer.isAborted()) {
+ restore();
+ version++;
+ writer = Transaction.COMMITTED;
+ }
+ return null;
+ }
+ if (!me.validate()) {
+ throw new AbortedException();
+ }
+ if (me == writer) {
+ return null;
+ }
+ for (Transaction reader : readers) {
+ if (reader.isActive() && reader != me) {
+ return reader;
+ }
+ }
+ readers.clear();
+ switch (writer.getStatus()) {
+ case ACTIVE:
+ return writer;
+ case COMMITTED:
+ backup();
+ version++;
+ break;
+ case ABORTED:
+ restore();
+ version++;
+ break;
+ default:
+ throw new PanicException(FORMAT, writer.getStatus());
+ }
+ writer = me;
+ return null;
+ }
+
+ private void restore() {
+ System.arraycopy(shadow, 0, array, 0, array.length);
+ }
+ private void backup() {
+ System.arraycopy(array, 0, shadow, 0, array.length);
+ }
+
+}
--- /dev/null
+/*
+ * ContentionManager.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2;
+
+import dstm2.*;
+import java.util.Collection;
+/**
+ * Interface satisfied by all contention managers
+ */
+public interface ContentionManager {
+ /**
+ * Either give the writer a chance to finish it, abort it, or both.
+ * @param me Calling transaction.
+ * @param other Transaction that's in my way.
+ */
+ void resolveConflict(Transaction me, Transaction other);
+
+ /**
+ * Either give the writer a chance to finish it, abort it, or both.
+ * @param me Calling transaction.
+ * @param other set of transactions in my way
+ */
+ void resolveConflict(Transaction me, Collection<Transaction> other);
+
+ /**
+ * Assign a priority to caller. Not all managers assign meaningful priorities.
+ * @return Priority of conflicting transaction.
+ */
+ long getPriority();
+
+ /**
+ * Change this manager's priority.
+ * @param value new priority value
+ */
+ void setPriority(long value);
+
+ /**
+ * Notify manager that object was opened.
+ */
+ void openSucceeded();
+
+ /**
+ * Notify manager that transaction committed.
+ */
+ void committed();
+
+};
--- /dev/null
+/*
+ * Defaults.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2;
+
+/**
+ *
+ * @author Maurice Herlihy
+ */
+public class Defaults {
+ /**
+ * how many threads
+ **/
+ public static final int THREADS = 5;
+ /**
+ * benchmark duration in milliseconds
+ **/
+ public static final int TIME = 10000;
+ /**
+ * uninterpreted arg passed to benchmark
+ **/
+ public static final int EXPERIMENT = 100;
+ /**
+ * fully-qualified contention manager name
+ **/
+ public static final String MANAGER = "dstm2.manager.BackoffManager";
+ /**
+ * fully-qualified factory name
+ **/
+ public static final String FACTORY = "dstm2.factory.shadow.Factory";
+ /**
+ * fully-qualified adapter name
+ **/
+ public static final String ADAPTER = "dstm2.factory.shadow.Adapter";;
+
+}
--- /dev/null
+/*
+ * Main.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2;
+import static dstm2.Defaults.*;
+import dstm2.benchmark.Benchmark;
+import TransactionalIO.exceptions.PanicException;
+import dstm2.factory.Factory;
+
+public class Main {
+
+ /**
+ * @param args the command line arguments
+ * usage: dstm.benchmark.Main -b <benchmarkclass> [-m <managerclass>] [-t <#threads>] [-n <#time-in-ms>] [-e <experiment#>] [-f <factory>"
+ */
+ public static void main(String args[]) {
+ int numThreads = 20;//THREADS;
+ int numMillis = TIME;
+ int experiment = EXPERIMENT;
+ String managerClassName = MANAGER;
+ Class managerClass = null;
+ String benchmarkClassName = null;
+ Class benchmarkClass = null;
+
+ String adapterClassName = Defaults.ADAPTER;
+
+ // discard statistics from previous runs
+ Thread.clear();
+ // Parse and check the args
+ int argc = 0;
+ try {
+ while (argc < args.length) {
+ String option = args[argc++];
+ if (option.equals("-m"))
+ managerClassName = args[argc];
+ else if (option.equals("-b"))
+ benchmarkClassName = args[argc];
+ else if (option.equals("-t"))
+ numThreads = Integer.parseInt(args[argc]);
+ else if (option.equals("-n"))
+ numMillis = Integer.parseInt(args[argc]);
+ else if (option.equals("-e"))
+ experiment = Integer.parseInt(args[argc]);
+ else if (option.equals("-a"))
+ adapterClassName = args[argc];
+ else
+ reportUsageErrorAndDie();
+ argc++;
+ }
+ } catch (NumberFormatException e) {
+ System.out.println("Expected a number: " + args[argc]);
+ System.exit(0);
+ } catch (Exception e) {
+ reportUsageErrorAndDie();
+ }
+
+ // Initialize contention manager.
+ try {
+ managerClass = Class.forName(MANAGER);
+ Thread.setContentionManagerClass(managerClass);
+ } catch (ClassNotFoundException ex) {
+ reportUsageErrorAndDie();
+ }
+
+ // Initialize adapter class
+ Thread.setAdapterClass(adapterClassName);
+
+ // initialize benchmark
+ Benchmark benchmark = null;
+ try {
+ benchmarkClass = Class.forName(benchmarkClassName);
+ benchmark = (Benchmark) benchmarkClass.newInstance();
+ } catch (InstantiationException e) {
+ System.out.format("%s does not implement dstm.benchmark.Benchmark: %s\n", benchmarkClass, e);
+ System.exit(0);
+ } catch (ClassCastException e) {
+ System.out.format("Exception when creating class %s: %s\n", benchmarkClass, e);
+ System.exit(0);
+ } catch (Exception e) {
+ e.printStackTrace(System.out);
+ System.exit(0);
+ }
+
+ // Set up the benchmark
+ long startTime = 0;
+
+ Thread[] thread = new Thread[numThreads];
+ System.out.println("Benchmark: " + benchmarkClass);
+ System.out.println("Adapter: " + adapterClassName);
+ System.out.println("Contention manager: " + managerClassName);
+ System.out.println("Threads: " + numThreads);
+ System.out.println("Mix: " + experiment + "% updates");
+
+
+ TransactionalIO.benchmarks.benchmark.init();
+
+ System.out.println((char)97);
+ int j = 97;
+ try {
+ for (int i = 0; i < numThreads; i++){
+ System.out.println((char)j);
+ thread[i] = benchmark.createThread(experiment, (char)j);
+ j++;
+ }
+
+ startTime = System.currentTimeMillis();
+ for (int i = 0; i < numThreads; i++)
+ thread[i].start();
+ Thread.sleep(numMillis);
+ Thread.stop = true; // notify threads to stop
+ for (int i = 0; i < numThreads; i++) {
+ thread[i].join();
+ }
+ } catch (Exception e) {
+ e.printStackTrace(System.out);
+ System.exit(0);
+ }
+ long stopTime = System.currentTimeMillis();
+
+ double elapsed = (double)(stopTime - startTime) / 1000.0;
+
+ // Run the sanity check for this benchmark
+ try {
+ benchmark.sanityCheck();
+ } catch (Exception e) {
+ e.printStackTrace(System.out);
+ }
+
+ long committed = Thread.totalCommitted;
+ long total = Thread.totalTotal;
+ if (total > 0) {
+ System.out.printf("Committed: %d\nTotal: %d\nPercent committed: (%d%%)\n",
+ committed,
+ total,
+ (100 * committed) / total);
+ } else {
+ System.out.println("No transactions executed!");
+ }
+ benchmark.report();
+ System.out.println("Elapsed time: " + elapsed + " seconds.");
+ System.out.println("----------------------------------------");
+ }
+
+ private static void reportUsageErrorAndDie() {
+ System.out.println("usage: dstm2.Main -b <benchmarkclass> [-m <managerclass>] [-t <#threads>] [-n <#time-in-ms>] [-e <experiment#>] [-a <adapter>]");
+ System.exit(0);
+ }
+
+}
+
--- /dev/null
+package dstm2;
+
+/*
+ * Thread.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+//package dstm2;
+
+
+import TransactionalIO.exceptions.AbortedException;
+import TransactionalIO.exceptions.GracefulException;
+import TransactionalIO.exceptions.PanicException;
+
+import dstm2.factory.AtomicFactory;
+import dstm2.factory.Factory;
+import TransactionalIO.benchmarks.benchmark;
+import TransactionalIO.core.TransactionalFile;
+import TransactionalIO.core.Wrapper;
+import java.lang.reflect.Constructor;
+import java.lang.reflect.InvocationTargetException;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.Callable;
+import static dstm2.Defaults.*;
+/**
+ * The basic unit of computation for the transactional memory. This
+ * class extends <code>java.lang.Thread</code> by providing methods to
+ * begin, commit and abort transactions.
+ *
+ * Every <code>Thread</code> has a contention manager, created when
+ * the thread is created. Before creating any <code>Thread</code>s,
+ * you must call <code>Thread.setContentionManager</code> to set the
+ * class of the contention manager that will be created. The
+ * contention manager of a thread is notified (by invoking its
+ * notification methods) of the results of any methods involving the
+ * thread. It is also consulted on whether a transaction should be
+ * begun.
+ *
+ * @see dstm2.ContentionManager
+ */
+public class Thread extends java.lang.Thread {
+ /**
+ * Contention manager class.
+ */
+ protected static Class contentionManagerClass;
+
+ /**
+ * Adapter class.
+ */
+ protected static Class<dstm2.factory.Adapter> adapterClass;
+
+ /**
+ * Set to true when benchmark runs out of time.
+ **/
+ public static volatile boolean stop = false;
+ /**
+ * number of committed transactions for all threads
+ */
+ public static long totalCommitted = 0;
+ /**
+ * total number of transactions for all threads
+ */
+ public static long totalTotal = 0;
+ /**
+ * number of committed memory references for all threads
+ */
+ public static long totalCommittedMemRefs = 0;
+ /**
+ * total number of memory references for all threads
+ */
+ public static long totalTotalMemRefs = 0;
+
+ static ThreadLocal<ThreadState> _threadState = new ThreadLocal<ThreadState>() {
+ protected synchronized ThreadState initialValue() {
+ return new ThreadState();
+ }
+ };
+ static ThreadLocal<Thread> _thread = new ThreadLocal<Thread>() {
+ protected synchronized Thread initialValue() {
+ return null;
+ }
+ };
+
+ private static int MAX_NESTING_DEPTH = 1;
+
+ private static Object lock = new Object();
+
+ // Memo-ize factories so we don't have to recreate them.
+ private static Map<Class,Factory> factoryTable
+ = Collections.synchronizedMap(new HashMap<Class,Factory>());
+
+ /**
+ * Create thread to run a method.
+ * @param target execute this object's <CODE>run()</CODE> method
+ */
+ public Thread(final Runnable target) {
+ super(new Runnable() {
+ public void run() {
+ ThreadState threadState = _threadState.get();
+ threadState.reset();
+ target.run();
+ // collect statistics
+ synchronized (lock){
+ totalCommitted += threadState.committed;
+ totalTotal += threadState.total;
+ totalCommittedMemRefs += threadState.committedMemRefs;
+ totalTotalMemRefs += threadState.totalMemRefs;
+ }
+ }
+ });
+ }
+ /**
+ * no-arg constructor
+ */
+ public Thread() {
+ super();
+ }
+
+ /**
+ * Establishes a contention manager. You must call this method
+ * before creating any <code>Thread</code>.
+ *
+ * @see dstm2.ContentionManager
+ * @param theClass class of desired contention manager.
+ */
+ public static void setContentionManagerClass(Class theClass) {
+ Class cm;
+ try {
+ cm = Class.forName("dstm2.ContentionManager");
+ } catch (ClassNotFoundException e) {
+ throw new PanicException(e);
+ }
+ try {
+ contentionManagerClass = theClass;
+ } catch (Exception e) {
+ throw new PanicException("The class " + theClass
+ + " does not implement dstm2.ContentionManager");
+ }
+ }
+
+ /**
+ * set Adapter class for this thread
+ * @param adapterClassName adapter class as string
+ */
+ public static void setAdapterClass(String adapterClassName) {
+ try {
+ adapterClass = (Class<dstm2.factory.Adapter>)Class.forName(adapterClassName);
+ } catch (ClassNotFoundException ex) {
+ throw new PanicException("Adapter class not found: %s\n", adapterClassName);
+ }
+ }
+
+ /**
+ * Tests whether the current transaction can still commit. Does not
+ * actually end the transaction (either <code>commitTransaction</code> or
+ * <code>abortTransaction</code> must still be called). The contention
+ * manager of the invoking thread is notified if the onValidate fails
+ * because a <code>TMObject</code> opened for reading was invalidated.
+ *
+ * @return whether the current transaction may commit successfully.
+ */
+ static public boolean validate() {
+ ThreadState threadState = _threadState.get();
+ return threadState.validate();
+ }
+
+ /**
+ * Gets the current transaction, if any, of the invoking <code>Thread</code>.
+ *
+ * @return the current thread's current transaction; <code>null</code> if
+ * there is no current transaction.
+ */
+ static public Transaction getTransaction() {
+ return _threadState.get().transaction;
+ }
+
+ /**
+ * Gets the contention manager of the invoking <code>Thread</code>.
+ *
+ * @return the invoking thread's contention manager
+ */
+ static public ContentionManager getContentionManager() {
+ return _threadState.get().manager;
+ }
+
+ /**
+ * Create a new factory instance.
+ * @param _class class to implement
+ * @return new factory
+ */
+ static public <T> Factory<T> makeFactory(Class<T> _class) {
+ try {
+ Factory<T> factory = (Factory<T>) factoryTable.get(_class);
+
+ if (factory == null) {
+ factory = new AtomicFactory<T>(_class, adapterClass);
+ factoryTable.put(_class, factory);
+ }
+ return factory;
+ } catch (Exception e) {
+ throw new PanicException(e);
+ }
+ }
+
+ /**
+ * Execute a transaction
+ * @param xaction execute this object's <CODE>call()</CODE> method.
+ * @return result of <CODE>call()</CODE> method
+ */
+ public static <T> T doIt(Callable<T> xaction) {
+ ThreadState threadState = _threadState.get();
+ ContentionManager manager = threadState.manager;
+ T result = null;
+ boolean flag = false;
+ try {
+ while (true) {
+ threadState.beginTransaction();
+
+ /////For Integrating with IO//////////
+ Wrapper.Initialize(Thread.getTransaction());
+ //////////////////////////////////////
+ try {
+ result = xaction.call();
+
+ // } catch (AbortedException d) {
+ /* synchronized(benchmark.lock){
+ System.out.println(Thread.currentThread() + " aborted in committing");
+ }*/
+
+ // } //catch (SnapshotException s) {
+ //threadState.abortTransaction();
+ //}
+ // catch (Exception e) {
+ // e.printStackTrace();
+ // throw new PanicException("Unhandled exception " + e);
+ // }
+ threadState.totalMemRefs += threadState.transaction.memRefs;
+ threadState.transaction.attempts++;
+ /*synchronized(benchmark.lock){
+ System.out.println(Thread.currentThread() + " ghabl az try");
+ }*/
+ // try{
+
+
+ // if (!flag)
+ Wrapper.prepareIOCommit();
+ /* synchronized(benchmark.lock){
+ System.out.println(Thread.currentThread() + " to try");
+ }*/
+ ///////////////////////////////
+
+ if (threadState.commitTransaction()) {
+ threadState.committedMemRefs += threadState.transaction.memRefs;
+
+ Wrapper.commitIO();
+ flag = true;
+ }
+ }
+ catch(AbortedException ex){
+ threadState.depth--;
+ /// synchronized(benchmark.lock){
+ // System.out.println(Thread.currentThread() + " aborted in committing");
+ //}
+
+ }
+ catch (Exception e) {
+ e.printStackTrace();
+ throw new PanicException("Unhandled exception " + e);
+ }
+ finally{
+
+ Wrapper.getTransaction().unlockAllLocks();
+ if (flag == true)
+ break;
+ }
+
+ // transaction aborted
+ }
+ if (threadState.transaction != null) {
+ threadState.abortTransaction();
+ }
+ } finally {
+ threadState.transaction = null;
+ Wrapper.setTransaction(null);
+ }
+ // collect statistics
+ synchronized (lock){
+ totalTotalMemRefs = threadState.totalMemRefs;
+ totalCommittedMemRefs = threadState.committedMemRefs;
+ totalCommitted += threadState.committed;
+ totalTotal += threadState.total;
+ threadState.reset(); // set up for next iteration
+ }
+ throw new GracefulException();
+ }
+ /**
+ * Execute transaction
+ * @param xaction call this object's <CODE>run()</CODE> method
+ */
+ public static void doIt(final Runnable xaction) {
+ doIt(new Callable<Boolean>() {
+ public Boolean call() {
+ xaction.run();
+ return false;
+ };
+ });
+ }
+
+ /**
+ * number of transactions committed by this thread
+ * @return number of transactions committed by this thread
+ */
+ public static long getCommitted() {
+ return totalCommitted;
+ }
+
+ /**
+ * umber of transactions aborted by this thread
+ * @return number of aborted transactions
+ */
+ public static long getAborted() {
+ return totalTotal - totalCommitted;
+ }
+
+ /**
+ * number of transactions executed by this thread
+ * @return number of transactions
+ */
+ public static long getTotal() {
+ return totalTotal;
+ }
+
+ /**
+ * Register a method to be called every time this thread validates any transaction.
+ * @param c abort if this object's <CODE>call()</CODE> method returns false
+ */
+ public static void onValidate(Callable<Boolean> c) {
+ _threadState.get().onValidate.add(c);
+ }
+ /**
+ * Register a method to be called every time the current transaction is validated.
+ * @param c abort if this object's <CODE>call()</CODE> method returns false
+ */
+ public static void onValidateOnce(Callable<Boolean> c) {
+ _threadState.get().onValidateOnce.add(c);
+ }
+ /**
+ * Register a method to be called every time this thread commits a transaction.
+ * @param r call this object's <CODE>run()</CODE> method
+ */
+ public static void onCommit(Runnable r) {
+ _threadState.get().onCommit.add(r);
+ }
+ /**
+ * Register a method to be called once if the current transaction commits.
+ * @param r call this object's <CODE>run()</CODE> method
+ */
+ public static void onCommitOnce(Runnable r) {
+ _threadState.get().onCommitOnce.add(r);
+ }
+ /**
+ * Register a method to be called every time this thread aborts a transaction.
+ * @param r call this objec't <CODE>run()</CODE> method
+ */
+ public static void onAbort(Runnable r) {
+ _threadState.get().onAbort.add(r);
+ }
+ /**
+ * Register a method to be called once if the current transaction aborts.
+ * @param r call this object's <CODE>run()</CODE> method
+ */
+ public static void onAbortOnce(Runnable r) {
+ _threadState.get().onAbortOnce.add(r);
+ }
+ /**
+ * get thread ID for debugging
+ * @return unique id
+ */
+ public static int getID() {
+ return _threadState.get().hashCode();
+ }
+
+ /**
+ * reset thread statistics
+ */
+ public static void clear() {
+ totalTotal = 0;
+ totalCommitted = 0;
+ totalCommittedMemRefs = 0;
+ totalTotalMemRefs = 0;
+ stop = false;
+ }
+
+ /**
+ * Class that holds thread's actual state
+ */
+ public static class ThreadState {
+
+ int depth = 0;
+ ContentionManager manager;
+
+ private long committed = 0; // number of committed transactions
+ private long total = 0; // total number of transactions
+ private long committedMemRefs = 0; // number of committed reads and writes
+ private long totalMemRefs = 0; // total number of reads and writes
+
+ Set<Callable<Boolean>> onValidate = new HashSet<Callable<Boolean>>();
+ Set<Runnable> onCommit = new HashSet<Runnable>();
+ Set<Runnable> onAbort = new HashSet<Runnable>();
+ Set<Callable<Boolean>> onValidateOnce = new HashSet<Callable<Boolean>>();
+ Set<Runnable> onCommitOnce = new HashSet<Runnable>();
+ Set<Runnable> onAbortOnce = new HashSet<Runnable>();
+
+ Transaction transaction = null;
+
+ /**
+ * Creates new ThreadState
+ */
+ public ThreadState() {
+ try {
+ manager = (ContentionManager)Thread.contentionManagerClass.newInstance();
+ } catch (NullPointerException e) {
+ throw new PanicException("No default contention manager class set.");
+ } catch (Exception e) { // Some problem with instantiation
+ throw new PanicException(e);
+ }
+ }
+
+ /**
+ * Resets any metering information (commits/aborts, etc).
+ */
+ public void reset() {
+ committed = 0; // number of committed transactions
+ total = 0; // total number of transactions
+ committedMemRefs = 0; // number of committed reads and writes
+ totalMemRefs = 0; // total number of reads and writes
+ }
+
+ /**
+ * used for debugging
+ * @return string representation of thread state
+ */
+ public String toString() {
+ return
+ "Thread" + hashCode() + "["+
+ "committed: " + committed + "," +
+ "aborted: " + ( total - committed) +
+ "]";
+ }
+
+ /**
+ * Can this transaction still commit?
+ * This method may be called at any time, not just at transaction end,
+ * so we do not clear the onValidateOnce table.
+ * @return true iff transaction might still commit
+ */
+ public boolean validate() {
+ try {
+ // permanent
+ for (Callable<Boolean> v : onValidate) {
+ if (!v.call()) {
+ return false;
+ }
+ }
+ // temporary
+ for (Callable<Boolean> v : onValidateOnce) {
+ if (!v.call()) {
+ return false;
+ }
+ }
+ return transaction.validate();
+ } catch (Exception ex) {
+ return false;
+ }
+ }
+
+ /**
+ * Call methods registered to be called on commit.
+ */
+ public void runCommitHandlers() {
+ try {
+ // permanent
+ for (Runnable r: onCommit) {
+ r.run();
+ }
+ // temporary
+ for (Runnable r: onCommitOnce) {
+ r.run();
+ }
+ onCommitOnce.clear();
+ onValidateOnce.clear();
+ } catch (Exception ex) {
+ throw new PanicException(ex);
+ }
+ }
+
+ /**
+ * Starts a new transaction. Cannot nest transactions deeper than
+ * <code>Thread.MAX_NESTING_DEPTH.</code> The contention manager of the
+ * invoking thread is notified when a transaction is begun.
+ */
+ public void beginTransaction() {
+ transaction = new Transaction();
+ if (depth == 0) {
+ total++;
+ }
+ // first thing to fix if we allow nested transactions
+ if (depth >= 1) {
+ throw new PanicException("beginTransaction: attempting to nest transactions too deeply.");
+ }
+ depth++;
+ }
+
+ /**
+ * Attempts to commit the current transaction of the invoking
+ * <code>Thread</code>. Always succeeds for nested
+ * transactions. The contention manager of the invoking thread is
+ * notified of the result. If the transaction does not commit
+ * because a <code>TMObject</code> opened for reading was
+ * invalidated, the contention manager is also notified of the
+ * inonValidate.
+ *
+ *
+ * @return whether commit succeeded.
+ */
+ public boolean commitTransaction() {
+ depth--;
+ if (depth < 0) {
+ throw new PanicException("commitTransaction invoked when no transaction active.");
+ }
+ if (depth > 0) {
+ throw new PanicException("commitTransaction invoked on nested transaction.");
+ }
+ if (depth == 0) {
+ if (validate() && transaction.commit()) {
+ committed++;
+ runCommitHandlers();
+ return true;
+ }
+ abortTransaction();
+ return false;
+ } else {
+ return true;
+ }
+ }
+
+ /**
+ * Aborts the current transaction of the invoking <code>Thread</code>.
+ * Does not end transaction, but ensures it will never commit.
+ */
+ public void abortTransaction() {
+ runAbortHandlers();
+ transaction.abort();
+ }
+
+ /**
+ * Call methods registered to be called on commit.
+ */
+ public void runAbortHandlers() {
+ try {
+ // permanent
+ for (Runnable r: onAbort) {
+ r.run();
+ }
+ // temporary
+ for (Runnable r: onAbortOnce) {
+ r.run();
+ }
+ onAbortOnce.clear();
+ onValidateOnce.clear();
+ } catch (Exception ex) {
+ throw new PanicException(ex);
+ }
+ }
+ }
+}
--- /dev/null
+/*
+ * Transaction.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2;
+
+import TransactionalIO.exceptions.PanicException;
+import TransactionalIO.benchmarks.benchmark;
+import TransactionalIO.interfaces.TransactionStatu;
+import java.util.concurrent.atomic.AtomicReference;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+/**
+ * Transaction.java
+ * Keeps a transaction's status and contention manager.
+ */
+
+public class Transaction implements TransactionStatu{
+
+ private TransactionStatu othersystem;
+ private boolean flag = true;
+ /**
+ * Possible transaction status
+ **/
+ public enum Status {ABORTED, ACTIVE, COMMITTED};
+
+ /**
+ * Predefined committed transaction
+ */
+ public static Transaction COMMITTED = new Transaction(Status.COMMITTED);
+ /**
+ * Predefined orted transaction
+ */
+ public static Transaction ABORTED = new Transaction(Status.ABORTED);
+
+ /**
+ * Is transaction waiting for another?
+ */
+ public boolean waiting = false;
+
+ /**
+ * Number of times this transaction tried
+ */
+ public int attempts = 0;
+
+ /**
+ * Number of unique memory references so far.
+ */
+ public int memRefs = 0;
+
+ /**
+ * Time in nanos when transaction started
+ */
+ public long startTime = 0;
+ /**
+ * Time in nanos when transaction committed or aborted
+ */
+ public long stopTime = 0;
+
+ // generate unique ids
+ private static AtomicInteger unique = new AtomicInteger(100);
+
+ /** Updater for status */
+ private static final
+ AtomicReferenceFieldUpdater<Transaction, Status>
+ statusUpdater = AtomicReferenceFieldUpdater.newUpdater
+ (Transaction.class, Status.class, "status");
+
+ private volatile Status status;
+
+ private long id;
+
+ private ContentionManager manager;
+
+ /**
+ * Creates a new, active transaction.
+ */
+ public Transaction() {
+ this.status = Status.ACTIVE;
+ this.id = this.startTime = System.nanoTime();
+ this.manager = Thread.getContentionManager();
+ }
+
+ /**
+ * Creates a new transaction with given status.
+ * @param myStatus active, committed, or aborted
+ */
+ private Transaction(Transaction.Status myStatus) {
+ this.status = myStatus;
+ this.startTime = 0;
+ }
+
+ /**
+ * Access the transaction's current status.
+ * @return current transaction status
+ */
+ public Status getStatus() {
+ return status;
+ }
+
+ /**
+ * Tests whether transaction is active.
+ * @return whether transaction is active
+ */
+ public boolean isActive() {
+ return this.getStatus() == Status.ACTIVE;
+ }
+
+ /**
+ * Tests whether transaction is aborted.
+ * @return whether transaction is aborted
+ */
+ public boolean isAborted() {
+
+ return this.getStatus() == Status.ABORTED;
+ }
+
+ /**
+ * Tests whether transaction is committed.
+ * @return whether transaction is committed
+ */
+ public boolean isCommitted() {
+ return (this.getStatus() == Status.COMMITTED);
+ }
+
+ /**
+ * Tests whether transaction is committed or active.
+ * @return whether transaction is committed or active
+ */
+ public boolean validate() {
+ Status status = this.getStatus();
+ switch (status) {
+ case COMMITTED:
+ throw new PanicException("committed transaction still running");
+ case ACTIVE:
+ return true;
+ case ABORTED:
+ return false;
+ default:
+ throw new PanicException("unexpected transaction state: " + status);
+ }
+ }
+
+ /**
+ * Tries to commit transaction
+ * @return whether transaction was committed
+ */
+ public boolean commit() {
+ try {
+ while (this.getStatus() == Status.ACTIVE) {
+ if (statusUpdater.compareAndSet(this,
+ Status.ACTIVE,
+ Status.COMMITTED)) {
+ return true;
+ }
+ }
+ return false;
+ } finally {
+ wakeUp();
+ }
+ }
+
+ /**
+ * Tries to abort transaction
+ * @return whether transaction was aborted (not necessarily by this call)
+ */
+ public boolean abort() {
+ try {
+ boolean flag = false;
+ while (this.getStatus() == Status.ACTIVE) {
+ if (statusUpdater.compareAndSet(this, Status.ACTIVE, Status.ABORTED)) {
+ flag = true;
+ // System.out.println(Thread.currentThread() +" tamam " + this.getStatus());
+ }
+ }
+ if (flag)
+ if (getOtherSystem() != null && !(getOtherSystem().isAborted())){
+ /* synchronized(benchmark.lock){
+ System.out.println(Thread.currentThread() +" beeeeee gade sag raftim 1");
+ } */
+ getOtherSystem().abortThisSystem();
+ /* synchronized(benchmark.lock){
+ System.out.println(Thread.currentThread() +" beeeeeeeee gade sag raftim 2");
+ } */
+ }
+
+
+
+ return this.getStatus() == Status.ABORTED;
+ } finally {
+
+ wakeUp();
+ }
+ }
+
+ /**
+ * Returns a string representation of this transaction
+ * @return the string representcodes[ation
+ */
+ public String toString() {
+ switch (this.status) {
+ case COMMITTED:
+ return "Transaction" + this.startTime + "[committed]";
+ case ABORTED:
+ return "Transaction" + this.startTime + "[aborted]";
+ case ACTIVE:
+ return "Transaction" + this.startTime + "[active]";
+ default:
+ return "Transaction" + this.startTime + "[???]";
+ }
+ }
+
+ /**
+ * Block caller while transaction is active.
+ */
+ public synchronized void waitWhileActive() {
+ while (this.getStatus() == Status.ACTIVE) {
+ try {
+ wait();
+ } catch (InterruptedException ex) {}
+ }
+ }
+ /**
+ * Block caller while transaction is active.
+ */
+ public synchronized void waitWhileActiveNotWaiting() {
+ while (getStatus() == Status.ACTIVE && !waiting) {
+ try {
+ wait();
+ } catch (InterruptedException ex) {}
+ }
+ }
+
+ /**
+ * Wake up any transactions waiting for this one to finish.
+ */
+ public synchronized void wakeUp() {
+ notifyAll();
+ }
+
+ /**
+ * This transaction's contention manager
+ * @return the manager
+ */
+ public ContentionManager getContentionManager() {
+ return manager;
+ }
+
+
+
+ public TransactionStatu getOtherSystem() {
+ return othersystem;
+ }
+
+ public void setOtherSystem(TransactionStatu othersystem) {
+ this.othersystem = othersystem;
+ }
+
+ public void abortThisSystem() {
+ abort();
+ }
+}
--- /dev/null
+/*
+ * atomic.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2;
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+
+/**
+ * Annotation indicating that class is atomic (can be shared among transactions).
+ * @author Maurice Herlihy
+ */
+@Retention(RetentionPolicy.RUNTIME)
+@Target(ElementType.TYPE)
+public @interface atomic {
+
+}
--- /dev/null
+/*
+ * To change this template, choose Tools | Templates
+ * and open the template in the editor.
+ */
+
+package dstm2.benchmark;
+
+import dstm2.Thread;
+import dstm2.atomic;
+import dstm2.factory.Factory;
+import java.util.Iterator;
+
+/**
+ *
+ * @author navid
+ */
+public class AVLTree extends IntSetBenchmark{
+
+ static Factory<AvlNode> factory = Thread.makeFactory(AvlNode.class);
+
+ protected AvlNode root;
+
+ @atomic public interface AvlNode
+ {
+ AvlNode getLeft();
+ void setLeft(AvlNode value);
+
+ AvlNode getRight();
+ void setRight(AvlNode value);
+
+ int getHeight();
+ void setHeight(int value);
+
+ int getElement();
+ void setElement(int value);
+
+ }
+
+
+
+ public boolean insert( int x )
+ {
+ // System.out.println(Thread.currentThread() + " null? " +root);
+ AVLTree.this.root = insert( x, AVLTree.this.root );
+ return true;
+ }
+
+
+
+
+ /* public Comparable find( Comparable x )
+ {
+ return elementAt( find( x, root ) );
+ }*/
+
+ public boolean isEmpty( )
+ {
+ return this.root == null;
+ }
+
+
+ public void printTree( )
+ {
+ if( isEmpty( ) )
+ System.out.println( "Empty tree" );
+ else
+ printTree( this.root );
+ }
+
+ private Comparable elementAt( AvlNode t )
+ {
+ return t == null ? null : t.getElement();
+ }
+
+
+ private AvlNode insert( int x, AvlNode t )
+ {
+ // if (root != null)
+ // System.out.println(Thread.currentThread() + " gozo" + root.getElement());
+
+ if( t == null ){
+ // if (t==root)
+ // System.out.println(Thread.currentThread() + " root? " +root);
+ // System.out.println(Thread.currentThread() + " ff " +t);
+ t = factory.create();
+ // System.out.println(Thread.currentThread() + " gg " +t);
+ t.setElement(x);
+ t.setLeft(null);
+ t.setRight(null);
+ }
+
+ else if( x < t.getElement() )
+ {
+ t.setLeft(insert( x, t.getLeft() ));
+ if( height( t.getLeft() ) - height( t.getRight() ) == 2 )
+ if( x < t.getLeft().getElement() )
+ t = leftRoate( t );
+ else
+ t = doubleLeftRotae( t );
+ }
+ else if( x > t.getElement())
+ {
+ t.setRight(insert( x, t.getRight() ));
+ if( height( t.getRight() ) - height( t.getLeft() ) == 2 )
+ if( x > t.getRight().getElement() )
+ t = rightRotate( t );
+ else
+ t = doubleRightRotate( t );
+ }
+ else;
+
+ t.setHeight(max( height( t.getLeft() ), height( t.getRight() ) ) + 1);
+ return t;
+ }
+
+
+ public void makeEmpty( )
+ {
+ this.root = null;
+ }
+
+ /* private AvlNode find( Comparable x, AvlNode t )
+ {
+ while( t != null )
+ if( x.compareTo( t.getElement() ) < 0 )
+ t = t.getLeft();
+ else if( x.compareTo( t.getElement() ) > 0 )
+ t = t.getRight();
+ else
+ return t; // Match
+
+ return null; // No match
+ }*/
+
+
+ private void printTree( AvlNode t )
+ {
+ if( t != null )
+ {
+ printTree( t.getLeft() );
+ System.out.println( t.getElement());
+ printTree( t.getRight() );
+ }
+ }
+
+
+ private static int height( AvlNode t )
+ {
+ return t == null ? -1 : t.getHeight();
+ }
+
+
+ private static int max( int lhs, int rhs )
+ {
+ return lhs > rhs ? lhs : rhs;
+ }
+
+ private static AvlNode leftRoate( AvlNode k2 )
+ {
+
+ AvlNode k1 = k2.getLeft();
+ k2.setLeft(k1.getRight());
+ k1.setRight(k2);
+ k2.setHeight(max( height( k2.getLeft()), height( k2.getRight() ) ) + 1);
+ k1.setHeight(max( height( k1.getLeft() ), k2.getHeight()) + 1);
+ return k1;
+ }
+
+
+ private static AvlNode rightRotate( AvlNode k1 )
+ {
+
+ AvlNode k2 = k1.getRight();
+ k1.setRight(k2.getLeft());
+ k2.setLeft(k1);
+ k1.setHeight(max( height(k1.getLeft()), height( k1.getRight())) + 1);
+
+ k2.setHeight(max( height(k2.getRight()),k1.getHeight()) + 1);
+
+ return k2;
+ }
+
+ private static AvlNode doubleLeftRotae( AvlNode k3 )
+ {
+ k3.setLeft(rightRotate( k3.getLeft() ));
+ return leftRoate( k3 );
+ }
+
+ private static AvlNode doubleRightRotate( AvlNode k1 )
+ {
+ k1.setRight(leftRoate( k1.getRight()));
+ return rightRotate( k1 );
+ }
+
+
+ protected void init() {
+ // this.root = factory.create();
+
+ }
+
+ public Thread createThread(int which) {
+ throw new UnsupportedOperationException("Not supported yet.");
+ }
+
+
+
+
+
+ @Override
+ public Iterator<Integer> iterator() {
+ throw new UnsupportedOperationException("Not supported yet.");
+
+ }
+
+ @Override
+ public boolean contains(int v) {
+ throw new UnsupportedOperationException("Not supported yet.");
+ }
+
+ @Override
+ public boolean remove(int v) {
+ throw new UnsupportedOperationException("Not supported yet.");
+ }
+
+ public Thread createThread(int which, char sample, int start) {
+ throw new UnsupportedOperationException("Not supported yet.");
+ }
+
+
+
+}
--- /dev/null
+/*
+ * Benchmark.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.benchmark;
+import dstm2.Thread;
+
+
+/**
+ * A simple interface to set up uniform benchmarks for the DSTM system
+ **/
+public interface Benchmark
+{
+ /**
+ * Creates a thread to run the benchmark.
+ *
+ * @param which <code>int</code> which test to run
+ * @return Thread the thread to run the benchmark
+ */
+ public Thread createThread(int which);
+ public Thread createThread(int which, char sample);
+
+
+ /**
+ * Checks that after running the benchmark, the resulting data
+ * structure meets a specified "sanity check". Prints messages to
+ * <code>System.out</code> if problems are found, or confirmation
+ * that no problems were found.
+ * @param stats how big should the object be?
+ */
+ public void sanityCheck();
+
+ /**
+ * Reports statistics.
+ */
+ public void report();
+}
+
--- /dev/null
+/*
+ * To change this template, choose Tools | Templates
+ * and open the template in the editor.
+ */
+
+package dstm2.benchmark;
+
+import dstm2.Thread;
+import dstm2.atomic;
+import dstm2.factory.Factory;
+import TransactionalIO.benchmarks.benchmark;
+import TransactionalIO.core.TransactionalFile;
+import dstm2.util.Random;
+import java.io.IOException;
+import java.util.Iterator;
+import java.util.Vector;
+import java.util.concurrent.locks.ReentrantLock;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+/**
+ *
+ * @author navid
+ */
+public class Counter extends CustomBenchmark {
+
+ private static Factory<CountKeeper> factory = Thread.makeFactory(CountKeeper.class);
+ private CountKeeper word1_occurence;
+ private CountKeeper word2_occurence;
+ private CountKeeper word3_occurence;
+ private CountKeeper word4_occurence;
+ private CountKeeper word5_occurence;
+ private CountKeeper word6_occurence;
+ private CountKeeper word7_occurence;
+ private CountKeeper word8_occurence;
+ private CountKeeper word9_occurence;
+ private CountKeeper word10_occurence;
+
+
+
+
+ public void init() {
+ // for (int i = 0; i< 10; i++)
+
+
+ word1_occurence = factory.create();
+ word1_occurence.setOccurence(0);
+
+ word2_occurence = factory.create();
+ word2_occurence.setOccurence(0);
+
+ word3_occurence = factory.create();
+ word3_occurence.setOccurence(0);
+
+ word4_occurence = factory.create();
+ word4_occurence.setOccurence(0);
+
+ word5_occurence = factory.create();
+ word5_occurence.setOccurence(0);
+
+ word6_occurence = factory.create();
+ word6_occurence.setOccurence(0);
+
+ word7_occurence = factory.create();
+ word7_occurence.setOccurence(0);
+
+ word8_occurence = factory.create();
+ word8_occurence.setOccurence(0);
+
+ word9_occurence = factory.create();
+ word9_occurence.setOccurence(0);
+
+ word10_occurence = factory.create();
+ word10_occurence.setOccurence(0);
+
+ }
+
+ public void execute(){
+ TransactionalFile f1 = (TransactionalFile)benchmark.m.get("2");
+ byte[] data = new byte[1];
+ char[] holder = new char[10000];
+ char[] word = new char[20];
+ boolean flag = false;
+ long toseek = Integer.valueOf(Thread.currentThread().getName().substring(7)) * 21169;
+ f1.seek(toseek);
+
+ data[0] ='a';
+ if (toseek != 0) //////////////// skipt the first word since its been read already
+ while (data[0] != '\n'){
+ int res;
+ res = f1.read(data);
+ if (res == -1){
+ flag =true;
+ break;
+ }
+ }
+
+ boolean completeword = false;
+
+ int counter = 0;
+ while (f1.getFilePointer() < toseek +21169)
+ {
+ if (flag)
+ break;
+ data[0] = 'a';
+ int i = 0;
+ int res;
+ //if (completeparag)
+ while ((data[0] != '\n' || completeword)){
+
+ if (completeword){
+ completeword = false;
+ int tmp = processInput(String.valueOf(word,0,counter-1));
+ if (tmp != -1){
+ switch(tmp){
+ case 0:
+ word1_occurence.setOccurence(word1_occurence.getOccurence() + 1);
+ break;
+ case 1:
+ word2_occurence.setOccurence(word2_occurence.getOccurence() + 1);
+ break;
+ case 2:
+ word3_occurence.setOccurence(word3_occurence.getOccurence() + 1);
+ break;
+ case 3:
+ word4_occurence.setOccurence(word4_occurence.getOccurence() + 1);
+ break;
+ case 4:
+ word5_occurence.setOccurence(word5_occurence.getOccurence() + 1);
+ break;
+ case 5:
+ word6_occurence.setOccurence(word6_occurence.getOccurence() + 1);
+ break;
+ case 6:
+ word7_occurence.setOccurence(word7_occurence.getOccurence() + 1);
+ break;
+ case 7:
+ word8_occurence.setOccurence(word8_occurence.getOccurence() + 1);
+ break;
+ case 8:
+ word9_occurence.setOccurence(word9_occurence.getOccurence() + 1);
+ break;
+ case 9:
+ word10_occurence.setOccurence(word10_occurence.getOccurence() + 1);
+ break;
+
+ }
+ //update data structure
+ String tolog = new String();
+
+ tolog = "-----------------------------------------------------------------";
+ tolog += "Found Word: " + String.valueOf(word,0,counter-1) + "\nAt Offset: ";
+ tolog += f1.getFilePointer() - counter;
+ tolog += "\n";
+
+ //byte[] towrite0 = new byte[title.length()];
+ //towrite0 = title.getBytes();
+
+ tolog += String.valueOf(holder,0,i);
+ tolog += "\n";
+ tolog += "-----------------------------------------------------------------";
+ tolog += "\n";
+
+ byte[] towrite = new byte[tolog.length()];
+ towrite = tolog.getBytes();
+ //towrite = tmpstr.getBytes();
+
+
+ try {
+ // System.out.println("dddddd");
+
+ ((TransactionalFile) (benchmark.m.get("3"))).write(towrite);
+ //((TransactionalFile) (benchmark.m.get("3"))).write();
+
+ } catch (IOException ex) {
+ Logger.getLogger(Counter.class.getName()).log(Level.SEVERE, null, ex);
+ }
+
+ }
+ }
+
+ if (flag)
+ break;
+
+ if (completeword){
+ //synchronized(benchmark.lock){
+ // if (!(Character.isWhitespace(word[counter])))
+ // System.out.println(String.valueOf(word,0,counter-1));
+ //}
+ holder[i] = (char)data[0];
+ i++;
+
+ }
+ counter = 0;
+ completeword= false;
+ data[0] = 'a';
+ while(Character.isLetter((char)data[0]))
+ {
+
+ res = f1.read(data);
+ if (res == -1){
+ flag = true;
+ break;
+ }
+ word[counter] = (char)data[0];
+ counter++;
+ if (counter > 1)
+ completeword = true;
+ holder[i] = (char)data[0];
+ i++;
+ }
+ }
+ }
+ //return true;
+ }
+ protected void execute(String towrite, int indiex_of_object){
+ switch(indiex_of_object){
+ case 0:
+ word1_occurence.setOccurence(word1_occurence.getOccurence() + 1);
+ break;
+ case 1:
+ word2_occurence.setOccurence(word2_occurence.getOccurence() + 1);
+ break;
+ case 2:
+ word3_occurence.setOccurence(word3_occurence.getOccurence() + 1);
+ break;
+ case 3:
+ word4_occurence.setOccurence(word4_occurence.getOccurence() + 1);
+ break;
+ case 4:
+ word5_occurence.setOccurence(word5_occurence.getOccurence() + 1);
+ break;
+ case 5:
+ word6_occurence.setOccurence(word6_occurence.getOccurence() + 1);
+ break;
+ case 6:
+ word7_occurence.setOccurence(word7_occurence.getOccurence() + 1);
+ break;
+ case 7:
+ word8_occurence.setOccurence(word8_occurence.getOccurence() + 1);
+ break;
+ case 8:
+ word9_occurence.setOccurence(word9_occurence.getOccurence() + 1);
+ break;
+ case 9:
+ word10_occurence.setOccurence(word10_occurence.getOccurence() + 1);
+ break;
+ }
+
+
+ try {
+ ((TransactionalFile) (benchmark.m.get("3"))).write(towrite.getBytes());
+
+ } catch (IOException ex) {
+ Logger.getLogger(Counter.class.getName()).log(Level.SEVERE, null, ex);
+ }
+
+ }
+
+
+
+ @atomic public interface CountKeeper{
+ int getOccurence();
+ void setOccurence(int value);;
+ }
+
+ private int processInput(String str){
+
+ Iterator it = benchmark.m2.keySet().iterator();
+ while (it.hasNext()){
+ Integer index = (Integer) it.next();
+ String pattern = (String)benchmark.m2.get(index);
+ if (str.equalsIgnoreCase(pattern)){
+ return index;
+ }
+ }
+ return -1;
+ }
+
+ public void printResults() {
+ for (int i =0; i<10; i++)
+ switch(i){
+ case 0:
+ System.out.println((String)benchmark.m2.get(Integer.valueOf(i)) + " " + word1_occurence.getOccurence());
+ break;
+ case 1:
+ System.out.println((String)benchmark.m2.get(Integer.valueOf(i)) + " " + word2_occurence.getOccurence());
+ break;
+ case 2:
+ System.out.println((String)benchmark.m2.get(Integer.valueOf(i)) + " " + word3_occurence.getOccurence());
+ break;
+ case 3:
+ System.out.println((String)benchmark.m2.get(Integer.valueOf(i)) + " " + word4_occurence.getOccurence());
+ break;
+ case 4:
+ System.out.println((String)benchmark.m2.get(Integer.valueOf(i)) + " " + word5_occurence.getOccurence());
+ break;
+ case 5:
+ System.out.println((String)benchmark.m2.get(Integer.valueOf(i)) + " " + word6_occurence.getOccurence());
+ break;
+ case 6:
+ System.out.println((String)benchmark.m2.get(Integer.valueOf(i)) + " " + word7_occurence.getOccurence());
+ break;
+ case 7:
+ System.out.println((String)benchmark.m2.get(Integer.valueOf(i)) + " " + word8_occurence.getOccurence());
+ break;
+ case 8:
+ System.out.println((String)benchmark.m2.get(Integer.valueOf(i)) + " " + word9_occurence.getOccurence());
+ break;
+ case 9:
+ System.out.println((String)benchmark.m2.get(Integer.valueOf(i)) + " " + word10_occurence.getOccurence());
+ break;
+ }
+
+ }
+
+ @Override
+ protected void execute(Vector arguments) {
+ String towrite = (String)arguments.get(0);
+ Integer i = (Integer)arguments.get(1);
+ int indiex_of_object = i.intValue();
+ switch(indiex_of_object){
+ case 0:
+ word1_occurence.setOccurence(word1_occurence.getOccurence() + 1);
+ break;
+ case 1:
+ word2_occurence.setOccurence(word2_occurence.getOccurence() + 1);
+ break;
+ case 2:
+ word3_occurence.setOccurence(word3_occurence.getOccurence() + 1);
+ break;
+ case 3:
+ word4_occurence.setOccurence(word4_occurence.getOccurence() + 1);
+ break;
+ case 4:
+ word5_occurence.setOccurence(word5_occurence.getOccurence() + 1);
+ break;
+ case 5:
+ word6_occurence.setOccurence(word6_occurence.getOccurence() + 1);
+ break;
+ case 6:
+ word7_occurence.setOccurence(word7_occurence.getOccurence() + 1);
+ break;
+ case 7:
+ word8_occurence.setOccurence(word8_occurence.getOccurence() + 1);
+ break;
+ case 8:
+ word9_occurence.setOccurence(word9_occurence.getOccurence() + 1);
+ break;
+ case 9:
+ word10_occurence.setOccurence(word10_occurence.getOccurence() + 1);
+ break;
+ }
+
+
+ try {
+ System.out.println(Thread.currentThread());
+ ((TransactionalFile) (benchmark.m.get("3"))).write(towrite.getBytes());
+
+ } catch (IOException ex) {
+ Logger.getLogger(Counter.class.getName()).log(Level.SEVERE, null, ex);
+ }
+
+ }
+
+
+
+}
+
+
+
+
--- /dev/null
+/*
+ * To change this template, choose Tools | Templates
+ * and open the template in the editor.
+ */
+
+package dstm2.benchmark;
+
+import TransactionalIO.benchmarks.benchmark;
+import TransactionalIO.core.TransactionalFile;
+import TransactionalIO.exceptions.GracefulException;
+import dstm2.atomic;
+import dstm2.benchmark.Counter.CountKeeper;
+import dstm2.factory.Factory;
+import dstm2.Thread;
+import dstm2.util.Random;
+import java.util.Vector;
+import java.util.concurrent.Callable;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ *
+ * @author navid
+ */
+public abstract class CustomBenchmark{
+
+ public ReentrantLock programlock = new ReentrantLock();
+
+ public static final Object lock = new Object();
+ /**
+ * local variable
+ */
+ int element;
+ /**
+ * local variable
+ */
+ int value;
+
+ /**
+ * Number of calls to insert()
+ */
+ int insertCalls = 0;
+ /**
+ * number of calls to contains()
+ */
+ int containsCalls = 0;
+ /**
+ * number of calls to remove()
+ */
+ int removeCalls = 0;
+ /**
+ * amount by which the set size has changed
+ */
+ int delta = 0;
+
+ protected abstract void init();
+
+ protected abstract void execute(Vector arguments);
+
+ protected abstract void printResults();
+
+ public CustomBenchmark() {
+ init();
+ }
+ // public static Vector hotwords;
+
+
+
+ /**
+ * Prints an error message to <code>System.out</code>, including a
+ * standard header to identify the message as an error message.
+ * @param s String describing error
+ */
+ protected static void reportError(String s) {
+ System.out.println(" ERROR: " + s);
+ System.out.flush();
+ }
+
+ public void report() {
+ System.out.println("Insert/Remove calls:\t" + (insertCalls + removeCalls));
+ System.out.println("Contains calls:\t" + containsCalls);
+ }
+
+
+
+
+ public void sanityCheck() {
+ long expected = delta;
+ int length = 1;
+
+ int prevValue = Integer.MIN_VALUE;
+ /* for (int value : this) {
+ length++;
+ if (value < prevValue) {
+ System.out.println("ERROR: set not sorted");
+ System.exit(0);
+ }
+ if (value == prevValue) {
+ System.out.println("ERROR: set has duplicates!");
+ System.exit(0);
+ }
+ if (length == expected) {
+ System.out.println("ERROR: set has bad length!");
+ System.exit(0);
+ }
+
+ }*/
+ System.out.println("Integer Set OK");
+ }
+
+
+
+
+ }
--- /dev/null
+/*
+ * To change this template, choose Tools | Templates
+ * and open the template in the editor.
+ */
+
+package dstm2.benchmark;
+
+import TransactionalIO.benchmarks.benchmark;
+import TransactionalIO.core.TransactionalFile;
+import TransactionalIO.exceptions.GracefulException;
+import java.io.FileNotFoundException;
+import java.io.IOException;
+import java.util.Iterator;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+import dstm2.Thread;
+import dstm2.atomic;
+import dstm2.factory.Factory;
+import java.io.RandomAccessFile;
+import java.util.Vector;
+import java.util.concurrent.Callable;
+
+/**
+ *
+ * @author navid
+ */
+public class CustomThread implements Runnable{
+
+ private Thread thread;
+ private CustomBenchmark mybenchmark;
+
+ static final Object lock = new Object();
+
+ int insertCalls = 0;
+ /**
+ * number of calls to contains()
+ */
+ int containsCalls = 0;
+ /**
+ * number of calls to remove()
+ */
+ int removeCalls = 0;
+ /**
+ * amount by which the set size has changed
+ */
+ int delta = 0;
+
+ public CustomThread(CustomBenchmark benchmark) {
+ mybenchmark = benchmark;
+ thread = new Thread(this);
+
+ }
+
+ public void start(){
+ thread.start();
+ }
+
+ public void join(){
+ try {
+ thread.join();
+ } catch (InterruptedException ex) {
+ Logger.getLogger(CustomThread.class.getName()).log(Level.SEVERE, null, ex);
+ }
+ }
+
+ public void run(){
+ if (mybenchmark instanceof Counter)
+ counterBenchmark();
+ else if (mybenchmark instanceof FinancialTransaction)
+ financialBenchmark();
+
+ }
+
+ public void financialBenchmark(){
+ try {
+ // try {
+ // try {
+ // TransactionalFile f1 = new TransactionalFile("/home/navid/financialtransaction.text", "rw");
+ //TransactionalFile f1 = (TransactionalFile)benchmark.m.get("4");
+ // TransactionalFile f1
+ // RandomAccessFile f1 = new RandomAccessFile("/home/navid/iliad.text", "rw");
+ RandomAccessFile f1 = new RandomAccessFile("/home/navid/financialtransaction.text", "rw");
+ byte[] data = new byte[1];
+ char[] holder = new char[10000];
+ char[] word = new char[20];
+ char[] word2 = new char[20];
+ char[] tradenumber = new char[20];
+ boolean flag = false;
+ int counter = 0;
+ long toseek = (Integer.valueOf(Thread.currentThread().getName().substring(7))) * 266914;//;// 53417;266914;//// ;
+ f1.seek(toseek);
+
+ data[0] = 'a';
+ if (toseek != 0) {
+ //////////////// skipt the first word since its been read already
+ while (data[0] != '\n') {
+ int res;
+ res = f1.read(data);
+ if (res == -1) {
+ flag = true;
+ break;
+ }
+ }
+ }
+
+
+ while (f1.getFilePointer() < toseek + 266914/* 53417/*/) {
+ if (flag) {
+ break;
+ }
+ final Vector arguments = new Vector();
+ try {
+ counter = 0;
+ data[0] = 'a';
+ while (data[0] != ' ') {
+ int res = f1.read(data);
+ if (res == -1) {
+ flag = true;
+ // System.out.println("sadsadsasadssadsafdsffffffff");
+ // System.out.println(Thread.currentThread());
+ break;
+ }
+ word[counter] = (char) data[0];
+ counter++;
+ }
+
+ if (flag) {
+ return;
+ }
+ arguments.add(String.copyValueOf(word, 0, counter - 1));
+ // synchronized(benchmark.lock){
+ // System.out.println(Thread.currentThread() + " string " + String.copyValueOf(word, 0, counter-1));
+ // }
+ counter = 0;
+ data[0] = 'a';
+ while (data[0] != ' ') {
+ int res = f1.read(data);
+ if (res == -1) {
+ flag = true;
+ // System.out.println("sadsadsasadssadsafdsffffffff");
+ break;
+ }
+ word[counter] = (char) data[0];
+ counter++;
+ }
+ // synchronized(benchmark.lock){
+ // System.out.println(Thread.currentThread() + " integer " +Integer.parseInt(String.valueOf(word, 0, counter - 1)));
+ // }
+ if (flag) {
+ return;
+ }
+ arguments.add(Integer.parseInt(String.valueOf(word, 0, counter - 1)));
+
+ counter = 0;
+ data[0] = 'a';
+
+ while (data[0] != ' ') {
+ // System.out.println("gaaaaaaaaaidi");
+ int res = f1.read(data);
+ if (res == -1) {
+ flag = true;
+ // System.out.println("sadsadsasadssadsafdsffffffff");
+ // System.out.println(Thread.currentThread());
+ break;
+ }
+ word[counter] = (char) data[0];
+ counter++;
+ }
+
+ if (flag) {
+ return;
+
+ }
+ arguments.add(String.copyValueOf(word, 0, counter - 1));
+
+
+ counter = 0;
+ data[0] = 'a';
+
+ while (data[0] != '\n') {
+ // System.out.println("gaaaaaaaaaidi");
+ int res = f1.read(data);
+ if (res == -1) {
+ flag = true;
+ // System.out.println("sadsadsasadssadsafdsffffffff");
+ // System.out.println(Thread.currentThread());
+ break;
+ }
+
+ word[counter] = (char) data[0];
+ counter++;
+ }
+ if (flag)
+ return;
+
+ arguments.add(String.copyValueOf(word, 0, counter - 1));
+ // iteration = 0;
+ /*while (data[0] != '\n'){
+ iteration++;
+ counter = 0;
+ data[0] = 'a';
+ boolean first = true;
+ while (data[0] != ' ' && data[0] != '\n'){
+ int res = f1.read(data);
+ if (res == -1) {
+ flag = true;
+ System.out.println("sadsadsasadssadsafdsffffffff");
+ break;
+ }
+ word[counter] = (char) data[0];
+ if (first){
+ if (Character.isDigit(data[0]))
+ iteration =2;
+ else
+ iteration = 0;
+ first = false;
+ }
+ counter++;
+ }
+ if (iteration != 2){
+ arguments.add(String.copyValueOf(word, 0, counter-1));
+ synchronized(benchmark.lock){
+ // System.out.println(Thread.currentThread() + " string " + String.copyValueOf(word, 0, counter-1));
+ }
+ }
+ else{
+ arguments.add(Integer.parseInt(String.valueOf(word, 0, counter - 1)));
+ synchronized(benchmark.lock){
+ // System.out.println(Thread.currentThread() + " integer " + String.valueOf(word, 0, counter - 1));
+ }
+ }
+ // System.out.println(arguments);
+ }*/
+
+ boolean result = Thread.doIt(new Callable<Boolean>() {
+
+ public Boolean call() {
+ // mybenchmark.programlock.lock();
+ // mybenchmark.execute(topass, tmp);
+ try {
+
+ mybenchmark.execute(arguments);
+ } catch (java.lang.ArrayIndexOutOfBoundsException e) {
+ e.printStackTrace();
+ }
+ // mybenchmark.programlock.unlock();
+ return true;
+ }
+ });
+ arguments.clear();
+ } catch (GracefulException g) {
+ // synchronized (lock) {
+ // mybenchmark.printResults();
+ /*insertCalls += myInsertCalls;
+ removeCalls += myRemoveCalls;
+ containsCalls += myContainsCalls;
+ delta += myDelta;*/
+ // }
+ }
+ }
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+ // } catch (IOException ex) {
+ // Logger.getLogger(CustomThread.class.getName()).log(Level.SEVERE, null, ex);
+ // }
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+// } catch (IOException ex) {
+ // Logger.getLogger(CustomThread.class.getName()).log(Level.SEVERE, null, ex);
+ // }
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+ // } catch (IOException ex) {
+ // Logger.getLogger(CustomThread.class.getName()).log(Level.SEVERE, null, ex);
+ // }
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+ } catch (IOException ex) {
+ Logger.getLogger(CustomThread.class.getName()).log(Level.SEVERE, null, ex);
+ }
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+ // } catch (IOException ex) {
+ // Logger.getLogger(CustomThread.class.getName()).log(Level.SEVERE, null, ex);
+ // }
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+// } catch (IOException ex) {
+ // Logger.getLogger(CustomThread.class.getName()).log(Level.SEVERE, null, ex);
+ // }
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+ // } catch (IOException ex) {
+ // Logger.getLogger(CustomThread.class.getName()).log(Level.SEVERE, null, ex);
+ // }
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+ /* synchronized (lock) {
+ mybenchmark.printResults();
+ }*/
+
+
+ }
+
+ public void counterBenchmark(){
+
+
+ TransactionalFile f1 = new TransactionalFile("/home/navid/iliad.text", "rw");
+ //RandomAccessFile f1 = new RandomAccessFile("/home/navid/iliad.text", "rw");
+ byte[] data = new byte[1];
+ char[] holder = new char[10000];
+ char[] word = new char[20];
+ boolean flag = false;
+ long toseek = Integer.valueOf(Thread.currentThread().getName().substring(7)) * 42337;
+ f1.seek(toseek);
+
+ data[0] = 'a';
+ if (toseek != 0) {
+ //////////////// skipt the first word since its been read already
+ while (data[0] != '\n') {
+ int res;
+ res = f1.read(data);
+ if (res == -1) {
+ flag = true;
+ break;
+ }
+ }
+ }
+ boolean completeword = false;
+
+ int counter = 0;
+
+ while (f1.getFilePointer() < toseek + 42337) {
+ try {
+ if (flag) {
+ break;
+ }
+ data[0] = 'a';
+ int i = 0;
+ int res;
+ //if (completeparag)
+ while (data[0] != '\n' || completeword) {
+
+ if (completeword) {
+ completeword = false;
+ final int tmp = processInput(String.valueOf(word, 0, counter - 1));
+ if (tmp != -1) {
+ final String topass = execute(holder, word, counter, i, f1.getFilePointer());
+ boolean result;
+ final Vector arguments = new Vector();
+ arguments.add(topass);
+ arguments.add(Integer.valueOf(tmp));
+ result = Thread.doIt(new Callable<Boolean>() {
+ public Boolean call() {
+ // mybenchmark.lock.lock();
+ //mybenchmark.execute(topass, tmp);
+ mybenchmark.execute(arguments);
+ // mybenchmark.lock.unlock();
+ return true;
+ }
+ });
+ arguments.clear();
+ }
+ }
+
+ if (flag) {
+ break;
+ }
+ if (completeword) {
+ //synchronized(benchmark.lock){
+ // if (!(Character.isWhitespace(word[counter])))
+ // System.out.println(String.valueOf(word,0,counter-1));
+ //}
+ holder[i] = (char) data[0];
+ i++;
+ }
+ counter = 0;
+ completeword = false;
+ data[0] = 'a';
+ while (Character.isLetter((char) data[0])) {
+
+ res = f1.read(data);
+ if (res == -1) {
+ flag = true;
+ break;
+ }
+ word[counter] = (char) data[0];
+ counter++;
+ if (counter > 1) {
+ completeword = true;
+ }
+ holder[i] = (char) data[0];
+ i++;
+ }
+ }
+ } catch (GracefulException g) {
+ // update statistics
+ synchronized (lock) {
+ mybenchmark.printResults();
+ /*insertCalls += myInsertCalls;
+ removeCalls += myRemoveCalls;
+ containsCalls += myContainsCalls;
+ delta += myDelta;*/
+ }
+ // return;
+ }
+ }
+ //return true;
+
+ //return true;
+ }
+
+ private int processInput(String str){
+
+ Iterator it = benchmark.m2.keySet().iterator();
+ while (it.hasNext()){
+ Integer index = (Integer) it.next();
+ String pattern = (String)benchmark.m2.get(index);
+ if (str.equalsIgnoreCase(pattern)){
+ return index;
+ }
+ }
+ return -1;
+ }
+
+
+ private String execute(char[] holder, char[] word, int counter, int i, long offset){
+ String tolog = new String();
+
+ tolog = "-----------------------------------------------------------------";
+ tolog += "Found Word: " + String.valueOf(word,0,counter-1) + "\nAt Offset: ";
+ tolog += offset - counter;
+ tolog += "\n";
+
+ //byte[] towrite0 = new byte[title.length()];
+ //towrite0 = title.getBytes();
+
+ tolog += String.valueOf(holder,0,i);
+ tolog += "\n";
+ tolog += "-----------------------------------------------------------------";
+ tolog += "\n";
+
+ byte[] towrite = new byte[tolog.length()];
+ towrite = tolog.getBytes();
+ //towrite = tmpstr.getBytes();
+
+ return tolog;
+ /*try {
+ // System.out.println("dddddd");
+
+ ((TransactionalFile) (benchmark.m.get("3"))).write(towrite);
+ //((TransactionalFile) (benchmark.m.get("3"))).write();
+
+ } catch (IOException ex) {
+ Logger.getLogger(CustomThread.class.getName()).log(Level.SEVERE, null, ex);
+ }*/
+ }
+
+
+
+
+
+}
--- /dev/null
+/*
+ * To change this template, choose Tools | Templates
+ * and open the template in the editor.
+ */
+
+package dstm2.benchmark;
+
+import TransactionalIO.benchmarks.benchmark;
+import TransactionalIO.core.Defaults;
+import TransactionalIO.core.TransactionalFile;
+import dstm2.AtomicArray;
+import dstm2.atomic;
+import dstm2.Thread;
+import dstm2.factory.Factory;
+import java.io.IOException;
+import java.io.RandomAccessFile;
+import java.util.Vector;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+
+/**
+ *
+ * @author navid
+ */
+public class FinancialTransaction extends CustomBenchmark{
+ private static Factory<FinancialTransactionDS> factory = Thread.makeFactory(FinancialTransactionDS.class);
+ private static Factory<RootHolder> factory2 = Thread.makeFactory(RootHolder.class);
+ private static Factory<FTrHolder> factory3 = Thread.makeFactory(FTrHolder.class);
+
+ LockedFTrHolder[] hlm;
+
+
+
+
+ /* String buyer1 = new String();
+ int soldshare1 = 0;
+ String seller1 = new String();
+
+ String buyer2 = new String();
+ int soldshare2 = 0;
+ String seller2 = new String();
+
+ String buyer3 = new String();
+ int soldshare3 = 0;
+ String seller3 = new String();
+
+ String buyer4 = new String();
+ int soldshare4 = 0;
+ String seller4 = new String();
+
+ String buyer5 = new String();
+ int soldshare5 = 0;
+ String seller5 = new String();
+
+ int lockedcounter = 1;*/
+ AtomicArray<FTrHolder> financialTransactionKeeper;
+
+ protected void init() {
+ /* hlm = new LockedFTrHolder[20];
+ for (int i=0; i<20; i++){
+ hlm[i] = new LockedFTrHolder();
+ hlm[i].counter =1;
+ hlm[i].lk = new LockedFinancialTransactionDS[5];
+ for (int j=0; j<5; j++){
+ hlm[i].lk[j] = new LockedFinancialTransactionDS();
+ hlm[i].lk[j].buyer = "";
+ hlm[i].lk[j].seller = "";
+ hlm[i].lk[j].soldshare = 0;
+ }
+
+ }*/
+
+
+
+
+ RootHolder ck = factory2.create();
+ ck.setFinancialTransactionKeeper(new AtomicArray<FTrHolder>(FTrHolder.class, 20));
+
+
+ financialTransactionKeeper = ck.getFinancialTransactionKeeper();
+ for (int i=0; i<20; i++){
+
+ FTrHolder f1 = factory3.create();
+ f1.setCounter(1);
+ f1.setFinancialTransactionKeeper(new AtomicArray<FinancialTransactionDS>(FinancialTransactionDS.class, 5));
+ for (int j=0; j<5; j++)
+ {
+ FinancialTransactionDS ftk = factory.create();
+ ftk.setBuyer("");
+ ftk.setSeller("");
+ ftk.setSoldShare(0);
+ AtomicArray<FinancialTransactionDS> tmp = f1.getFinancialTransactionKeeper();
+ tmp.set(j, ftk);
+ }
+
+
+ financialTransactionKeeper.set(i, f1);
+ }
+
+ }
+
+
+ protected void execute(Vector arguments) {
+ try {
+
+ TransactionalFile file = (TransactionalFile) benchmark.m.get("5");
+// RandomAccessFile file = (RandomAccessFile) benchmark.m.get("7");
+ String oldowner = (String) arguments.get(0);
+ Integer stocktrade = (Integer) arguments.get(1);
+ String newowner = (String) arguments.get(2);
+ String nameofstock = (String) arguments.get(3);
+ Integer offset1 = (Integer) benchmark.m4.get(oldowner);
+ Integer offset2 = (Integer) benchmark.m4.get(newowner);
+
+
+ file.seek(offset1 * Defaults.FILEFRAGMENTSIZE);
+ Vector v = computeandupdate(true, stocktrade, nameofstock);
+ String st = (String)(v.get(1));
+ long offset1towrite = ((Long)(v.get(0))).longValue();
+
+ file.seek(offset2 * Defaults.FILEFRAGMENTSIZE);
+ v = computeandupdate(false, stocktrade, nameofstock);
+ String st2 = (String)(v.get(1));
+ long offset2towrite = ((Long)(v.get(0))).longValue();
+
+
+ file.seek(offset1towrite);
+ file.write(st.getBytes());
+ file.seek(offset2towrite);
+ file.write(st2.getBytes());
+
+ // RandomAccessFile file2 = (RandomAccessFile) benchmark.m.get("8");
+ TransactionalFile file2 = (TransactionalFile) benchmark.m.get("6");
+
+ String towrite = oldowner + " " + stocktrade.toString() + " " + newowner + " processed\n";
+ file2.write(towrite.getBytes());
+ /*switch(lockedcounter){
+ case 1:
+ seller1 = oldowner;
+ soldshare1 = stocktrade.intValue();
+ buyer1 = newowner;
+ lockedcounter = 2;
+ break;
+ case 2:
+ seller2 = oldowner;
+ soldshare2 = stocktrade.intValue();
+ buyer2 = newowner;
+ lockedcounter = 3;
+ break;
+ case 3:
+ seller3 = oldowner;
+ soldshare3 = stocktrade.intValue();
+ buyer3 = newowner;
+ lockedcounter = 4;
+ break;
+ case 4:
+ seller4 = oldowner;
+ soldshare4 = stocktrade.intValue();
+ buyer4 = newowner;
+ lockedcounter = 5;
+ break;
+ case 5:
+ seller5 = oldowner;
+ soldshare5 = stocktrade.intValue();
+ buyer5 = newowner;
+ lockedcounter = 1;
+ break;
+ }*/
+ int i;
+ for (i=0;i<benchmark.stocks.length; i++){
+ if (benchmark.stocks[i].equalsIgnoreCase(nameofstock))
+ break;
+ }
+
+ /* switch(financialTransactionKeeper.get(i).getCounter()){
+ case 1:
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(0).setSeller(oldowner);
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(0).setSoldShare(stocktrade.intValue());
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(0).setBuyer(newowner);
+ financialTransactionKeeper.get(i).setCounter(2);
+ break;
+ case 2:
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(1).setSeller(oldowner);
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(1).setSoldShare(stocktrade.intValue());
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(1).setBuyer(newowner);
+ financialTransactionKeeper.get(i).setCounter(3);
+ break;
+ case 3:
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(2).setSeller(oldowner);
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(2).setSoldShare(stocktrade.intValue());
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(2).setBuyer(newowner);
+ financialTransactionKeeper.get(i).setCounter(4);
+ break;
+ case 4:
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(3).setSeller(oldowner);
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(3).setSoldShare(stocktrade.intValue());
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(3).setBuyer(newowner);
+ financialTransactionKeeper.get(i).setCounter(5);
+ break;
+ case 5:
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(4).setSeller(oldowner);
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(4).setSoldShare(stocktrade.intValue());
+ financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(4).setBuyer(newowner);
+ financialTransactionKeeper.get(i).setCounter(1);
+ break;
+
+ }*/
+
+ /* switch(hlm[i].counter){
+ case 1:
+ hlm[i].lk[0].seller = oldowner;
+ hlm[i].lk[0].soldshare = stocktrade.intValue();
+ hlm[i].lk[0].buyer = newowner;
+ hlm[i].counter = 2;
+ break;
+ case 2:
+ hlm[i].lk[1].seller = oldowner;
+ hlm[i].lk[1].soldshare = stocktrade.intValue();
+ hlm[i].lk[1].buyer = newowner;
+ hlm[i].counter = 3;
+ break;
+ case 3:
+ hlm[i].lk[2].seller = oldowner;
+ hlm[i].lk[2].soldshare = stocktrade.intValue();
+ hlm[i].lk[2].buyer = newowner;
+ hlm[i].counter = 4;
+ break;
+ case 4:
+ hlm[i].lk[3].seller = oldowner;
+ hlm[i].lk[3].soldshare = stocktrade.intValue();
+ hlm[i].lk[3].buyer = newowner;
+ hlm[i].counter = 5;
+ break;
+ case 5:
+ hlm[i].lk[4].seller = oldowner;
+ hlm[i].lk[4].soldshare = stocktrade.intValue();
+ hlm[i].lk[4].buyer = newowner;
+ hlm[i].counter = 1;
+ break;
+ }*/
+
+ } catch (IOException ex) {
+ Logger.getLogger(FinancialTransaction.class.getName()).log(Level.SEVERE, null, ex);
+ }
+ }
+ /*catch (NullPointerException e){
+ System.out.println("file?? " + file);
+ System.out.println("offset?? " + offset1);
+ System.out.println(oldowner);
+ System.out.println(Thread.currentThread());
+ e.printStackTrace();
+ }*/
+ /* int oldbalance = getOldBalance();
+ int newnumber = oldbalance - stocktrade.intValue();
+ updateFile(newnumber);
+ // System.out.println("offset: " + offset1 + " for: " + oldowner + " old balance: "+ oldbalance);
+
+ if (oldowner.equals("Smith")){
+ System.out.println("offset: " + offset1 + " for: " + oldowner + " old balance: "+ oldbalance);
+ System.out.println("trade money: " + stocktrade);
+ }
+ // System.out.println("old number: " + oldbalance);
+
+
+ oldbalance = getOldBalance();
+ newnumber = oldbalance + stocktrade.intValue();
+ updateFile(newnumber);*/
+ /* if (newowner.equals("Smith")){
+ System.out.println("offset: " + offset2 + " for: " + newowner + " old balance: "+ oldbalance);
+ System.out.println("trade money: " + stocktrade);
+ }*/
+
+
+
+ // }
+
+ // }
+
+ private Vector computeandupdate(boolean type, Integer stocktrade, String origstockname ){
+ // try{
+ // RandomAccessFile file = (RandomAccessFile) benchmark.m.get("7");
+ TransactionalFile file = (TransactionalFile)benchmark.m.get("5");
+ Vector v = new Vector();
+ byte[] data = new byte[1];
+ char[] balance = new char[20];
+
+ // int counter =0;
+ boolean flag = false;
+ data[0] = 'a';
+ int counter = 0;
+ while (data[0] != '\n') {
+ int res;
+ res = file.read(data);
+ if (res == -1) {
+ flag = true;
+ break;
+ }
+ }
+
+ while(true){
+ char[] stname = new char[10];
+ data[0] = 'a';
+ int ol=0;
+ while (data[0] != ' ') {
+ int res;
+ res = file.read(data);
+ if (res == -1) {
+ flag = true;
+ break;
+ }
+ stname[ol] = (char)data[0];
+ ol++;
+ }
+ String stockname = String.copyValueOf(stname, 0, ol-1);
+ if (stockname.equalsIgnoreCase(origstockname)) {
+ break;
+ }
+ else while (data[0] != '\n')
+ file.read(data);
+ }
+
+
+
+
+ data[0] = 'a';
+ while ((char) data[0] != ':') {
+ int res;
+ res = file.read(data);
+ if (res == -1) {
+ flag = true;
+ break;
+ }
+ }
+ int res = file.read(data);
+ long offsetofnumber = file.getFilePointer();
+ do {
+ res = file.read(data);
+ if (res == -1) {
+ flag = true;
+ break;
+ }
+ balance[counter] = (char) data[0];
+ counter++;
+ } while (Character.isDigit((char) data[0]) || (char)data[0] == '-');
+
+ int oldbalance = Integer.parseInt(String.valueOf(balance, 0, counter - 1));
+
+ // return oldnumber;
+
+
+ int newnumber;
+ if (type){
+ newnumber = oldbalance - stocktrade.intValue();
+ }
+ else
+ newnumber = oldbalance + stocktrade.intValue();
+
+
+ ////// file.seek(offsetofnumber);
+
+
+ String st = new String();
+ st = String.valueOf(newnumber);
+ if (String.valueOf(newnumber).length() < counter - 1){
+
+ for (int i=0; i<counter-String.valueOf(newnumber).length(); i++){
+ st += (new String(" "));
+ //file.write((new String(" ")).getBytes());
+ }
+ }
+ // st += new String("\n");
+ //file.write((new String("\n")).getBytes());
+ v.add(Long.valueOf(offsetofnumber));
+ v.add(st);
+ return v;
+/* } catch (IOException ex) {
+
+ Logger.getLogger(FinancialTransaction.class.getName()).log(Level.SEVERE, null, ex);
+ return null;
+ }*/
+ }
+
+ protected void printResults() {
+
+ for (int i=0; i<20; i++){
+ System.out.println("----------------------------------------------");
+ System.out.println(benchmark.stocks[i]);
+ for (int j=0; j<5; j++)
+ {
+ System.out.print(financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(j).getSeller() + " ");
+ System.out.print(financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(j).getBuyer() + " ");
+ System.out.println(financialTransactionKeeper.get(i).getFinancialTransactionKeeper().get(j).getSoldShare());
+ }
+ System.out.println("----------------------------------------------");
+ }
+ /* for (int i=0; i<20; i++){
+ System.out.println("----------------------------------------------");
+ System.out.println(benchmark.stocks[i]);
+ for (int j=0; j<5; j++)
+ {
+
+ System.out.print(hlm[i].lk[j].seller + " ");
+ System.out.print(hlm[i].lk[j].buyer + " ");
+ System.out.println(hlm[i].lk[j].soldshare);
+ }
+ System.out.println("----------------------------------------------");
+ }*/
+
+ /* System.out.print(finance1.getSeller() + " ");
+ System.out.print(finance1.getBuyer() + " ");
+ System.out.println(finance1.getSoldShare());
+
+ System.out.print(finance2.getSeller() + " ");
+ System.out.print(finance2.getBuyer()+ " ");
+ System.out.println(finance2.getSoldShare());
+
+ System.out.print(finance3.getSeller() + " ");
+ System.out.print(finance3.getBuyer()+ " ");
+ System.out.println(finance3.getSoldShare());
+
+ System.out.print(finance4.getSeller() + " ");
+ System.out.print(finance4.getBuyer()+ " ");
+ System.out.println(finance4.getSoldShare());
+
+ System.out.print(finance5.getSeller() + " ");
+ System.out.print(finance5.getBuyer()+ " ");
+ System.out.println(finance5.getSoldShare());*/
+
+ /*System.out.print(buyer1 + " ");
+ System.out.print(soldshare1 + " ");
+ System.out.println(seller1);
+
+ System.out.print(buyer2 + " ");
+ System.out.print(soldshare2 + " ");
+ System.out.println(seller2);
+
+ System.out.print(buyer3 + " ");
+ System.out.print(soldshare3 + " ");
+ System.out.println(seller3);
+
+ System.out.print(buyer4 + " ");
+ System.out.print(soldshare4 + " ");
+ System.out.println(seller4);
+
+ System.out.print(buyer5 + " ");
+ System.out.print(soldshare5 + " ");
+ System.out.println(seller5);*/
+
+ //System.out.println("----------------------------------------------");
+ }
+
+
+
+
+ @atomic public interface FinancialTransactionDS{
+ String getSeller();
+ void setSeller(String value);
+ int getSoldShare();
+ void setSoldShare(int value);
+ String getBuyer();
+ void setBuyer(String value);
+ }
+
+ @atomic public interface FTrHolder{
+ AtomicArray<FinancialTransactionDS> getFinancialTransactionKeeper();
+ void setFinancialTransactionKeeper(AtomicArray<FinancialTransactionDS> arr);
+ int getCounter();
+ void setCounter(int value);
+ }
+
+ @atomic public interface RootHolder{
+ AtomicArray<FTrHolder> getFinancialTransactionKeeper();
+ void setFinancialTransactionKeeper(AtomicArray<FTrHolder> arr);
+ // int getCounter();
+ // void setCounter(int value);
+ }
+
+ class LockedFinancialTransactionDS{
+ public String seller;
+ public String buyer;
+ public int soldshare;
+ }
+
+ class LockedFTrHolder{
+ public LockedFinancialTransactionDS[] lk = new LockedFinancialTransactionDS[5];
+ public int counter;
+ }
+
+
+
+
+ /* private int getOldBalance(){
+
+ byte[] data = new byte[1];
+ char[] balance = new char[20];
+
+ // int counter =0;
+ boolean flag = false;
+ data[0] = 'a';
+ counter = 0;
+ while (data[0] != '\n') {
+ int res;
+ res = file.read(data);
+ if (res == -1) {
+ flag = true;
+ break;
+ }
+ }
+ while ((char) data[0] != ':') {
+ int res;
+ res = file.read(data);
+ if (res == -1) {
+ flag = true;
+ break;
+ }
+ }
+ int res = file.read(data);
+ offsetofnumber = file.getFilePointer();
+ do {
+ res = file.read(data);
+ if (res == -1) {
+ flag = true;
+ break;
+ }
+ balance[counter] = (char) data[0];
+ counter++;
+ } while (Character.isDigit((char) data[0]) || (char)data[0] == '-');
+ // System.out.println((char)data[0]);
+ int oldnumber = Integer.parseInt(String.valueOf(balance, 0, counter - 1));
+ // System.out.println(oldnumber);
+ return oldnumber;
+
+
+ }
+
+ private void updateFile(int newnumber){
+ try {
+
+ file.seek(offsetofnumber);
+ // System.out.println(String.valueOf(newnumber));
+ file.write(String.valueOf(newnumber).getBytes());
+ if (String.valueOf(newnumber).length() < counter - 1){
+
+ for (int i=0; i<counter-String.valueOf(newnumber).length(); i++){
+
+ file.write((new String(" ")).getBytes());
+ }
+ }
+ file.write((new String("\n")).getBytes());
+
+ } catch (IOException ex) {
+ Logger.getLogger(FinancialTransaction.class.getName()).log(Level.SEVERE, null, ex);
+ }
+ }*/
+
+}
--- /dev/null
+/*
+ * IntSetBenchmark.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.benchmark;
+
+import TransactionalIO.exceptions.AbortedException;
+import TransactionalIO.exceptions.GracefulException;
+import TransactionalIO.exceptions.PanicException;
+import dstm2.Thread;
+
+import TransactionalIO.benchmarks.benchmark;
+import TransactionalIO.core.TransactionalFile;
+import dstm2.util.Random;
+import java.io.IOException;
+import java.util.Iterator;
+import java.util.concurrent.Callable;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+/**
+ * This abstract class is the superclass for the integer set benchmarks.
+ * @author Maurice Herlihy
+ * @date April 2004
+ */
+public abstract class IntSetBenchmark implements Benchmark, Iterable<Integer> {
+
+ /**
+ * How large to initialize the integer set.
+ */
+ protected final int INITIAL_SIZE = 8;
+
+ /**
+ * After the run is over, synchronize merging statistics with other threads.
+ */
+ static final Object lock = new Object();
+ /**
+ * local variable
+ */
+ int element;
+ /**
+ * local variable
+ */
+ int value;
+
+ /**
+ * Number of calls to insert()
+ */
+ int insertCalls = 0;
+ /**
+ * number of calls to contains()
+ */
+ int containsCalls = 0;
+ /**
+ * number of calls to remove()
+ */
+ int removeCalls = 0;
+ /**
+ * amount by which the set size has changed
+ */
+ int delta = 0;
+
+ /**
+ * Give subclass a chance to intialize private fields.
+ */
+ protected abstract void init();
+
+ /**
+ * Iterate through set. Not necessarily thread-safe.
+ */
+ public abstract Iterator<Integer> iterator();
+
+ /**
+ * Add an element to the integer set, if it is not already there.
+ * @param v the integer value to add from the set
+ * @return true iff value was added.
+ */
+ public abstract boolean insert(int v);
+
+ /**
+ * Tests wheter a value is in an the integer set.
+ * @param v the integer value to insert into the set
+ * @return true iff presence was confirmed.
+ */
+ public abstract boolean contains(int v);
+
+ /**
+ * Removes an element from the integer set, if it is there.
+ * @param v the integer value to delete from the set
+ * @return true iff v was removed
+ */
+ public abstract boolean remove(int v);
+
+ /**
+ * Creates a new test thread.
+ * @param percent Mix of mutators and observers.
+ * @return Thread to run.
+ */
+ public Thread createThread(int percent, char sample) {
+ try {
+ TestThread testThread = new TestThread(this, percent, sample);
+ return testThread;
+ } catch (Exception e) {
+ e.printStackTrace(System.out);
+ return null;
+ }
+ }
+
+ /**
+ * Prints an error message to <code>System.out</code>, including a
+ * standard header to identify the message as an error message.
+ * @param s String describing error
+ */
+ protected static void reportError(String s) {
+ System.out.println(" ERROR: " + s);
+ System.out.flush();
+ }
+
+ public void report() {
+ System.out.println("Insert/Remove calls:\t" + (insertCalls + removeCalls));
+ System.out.println("Contains calls:\t" + containsCalls);
+ }
+
+ private class TestThread extends Thread {
+ IntSetBenchmark intSet;
+ /**
+ * Thread-local statistic.
+ */
+ int myInsertCalls = 0;
+ /**
+ * Thread-local statistic.
+ */
+ int myRemoveCalls = 0;
+ /**
+ * Thread-local statistic.
+ */
+ int myContainsCalls = 0;
+ /**
+ * Thread-local statistic.
+ */
+ int myDelta = 0; // net change
+ public int percent = 0; // percent inserts
+ char sample;
+ AVLTree tree;
+
+ TestThread(IntSetBenchmark intSet, int percent, char sample) {
+ this.intSet = intSet;
+ this.percent = percent;
+ this.sample = sample;
+ }
+
+
+
+ public void run() {
+ Random random = new Random(this.hashCode());
+ random.setSeed(System.currentTimeMillis()); // comment out for determinstic
+
+ boolean toggle = true;
+ final TransactionalFile f1 = (TransactionalFile)benchmark.TransactionalFiles.get("0");
+ try {
+ while (true) {
+ boolean result = true;
+ element = random.nextInt();
+ if (Math.abs(element) % 100 < percent) {
+ if (toggle) { // insert on even turns
+ value = element / 100;
+ result = Thread.doIt(new Callable<Boolean>() {
+ public Boolean call() {
+ //////////////////////////////////////////benchmark 1////////////////////////////
+ /* TransactionalFile f1 = (TransactionalFile)benchmark.m.get("2");
+ byte[] data = new byte[1];
+ char[] holder = new char[10000];
+ char[] word = new char[20];
+ boolean flag = false;
+ long toseek = Integer.valueOf(Thread.currentThread().getName().substring(7)) * 21169;
+ f1.seek(toseek);
+
+ data[0] ='a';
+ if (toseek != 0) //////////////// skipt the first word since its been read already
+ while (data[0] != '\n'){
+ int res;
+ res = f1.read(data);
+ if (res == -1){
+ flag =true;
+ break;
+ }
+ }
+
+ boolean completeword = false;
+ int counter = 0;
+ while (f1.getFilePointer() < toseek +21169)
+ {
+ if (flag)
+ break;
+ data[0] = 'a';
+ int i = 0;
+ int res;
+ while ((data[0] != '\n' || completeword)){
+
+ //if (completeword){
+ // String str = Mixedbecnhmark.processInput(String.valueOf(word,0,counter-1));
+ //if (str != null){
+ // update data structure
+ // byte[] towrite = new byte[String.valueOf(holder,0,i).length()];
+ // towrite = String.valueOf(holder,0,i).getBytes();
+ // try {
+ // ((TransactionalFile) (benchmark.m.get("3"))).write(towrite);
+
+ // } catch (IOException ex) {
+ // Logger.getLogger(TestThread.class.getName()).log(Level.SEVERE, null, ex);
+ // }
+ //}
+ //}
+
+ if (flag)
+ break;
+
+ if (completeword){
+ synchronized(benchmark.lock){
+ // if (!(Character.isWhitespace(word[counter])))
+ // System.out.println(String.valueOf(word,0,counter-1));
+ }
+ holder[i] = (char)data[0];
+ i++;
+
+ }
+ counter = 0;
+ completeword= false;
+ data[0] = 'a';
+ while(Character.isLetter((char)data[0]))
+ {
+
+ res = f1.read(data);
+ if (res == -1){
+ flag = true;
+ break;
+ }
+ word[counter] = (char)data[0];
+ counter++;
+ if (counter > 1)
+ completeword = true;
+ holder[i] = (char)data[0];
+ i++;
+ }
+ }
+
+ }
+
+ myInsertCalls++;
+ return intSet.insert(464);*/
+ ////////////////////////benchmark 2///////////////////
+
+ TransactionalFile f1 = (TransactionalFile)benchmark.m.get("0");
+ byte[] data = new byte[1];
+ char[] holder = new char[10000];
+ char[] word = new char[20];
+ boolean flag = false;
+ long toseek = Integer.valueOf(Thread.currentThread().getName().substring(7)) * 20448;
+ f1.seek(toseek);
+
+ data[0] ='a';
+ if (toseek != 0) //////////////// skipt the first word since its been read already
+ while (data[0] != '\n'){
+ int res;
+ res = f1.read(data);
+ if (res == -1){
+ flag =true;
+ break;
+ }
+ }
+
+
+ while (f1.getFilePointer() < toseek +20448)
+ {
+ if (flag == true)
+ break;
+ data[0] = 'a';
+ int i = 0;
+ int res;
+ while (data[0] != '\n'){
+ res = f1.read(data);
+ if (res == -1){
+ flag = true;
+ break;
+ }
+
+ holder[i] = (char)data[0];
+ i++;
+ }
+
+
+ byte[] towrite = new byte[String.valueOf(holder,0,i).length()];
+ towrite = String.valueOf(holder,0,i).getBytes();
+ // System.out.println(String.valueOf(holder,0,i).toLowerCase().substring(0, 1));
+
+ try {
+ ((TransactionalFile) (benchmark.m.get(String.valueOf(holder,0,i).toLowerCase().substring(0, 1)))).write(towrite);
+ //update the memory //}
+ } catch (IOException ex) {
+ Logger.getLogger(TestThread.class.getName()).log(Level.SEVERE, null, ex);
+ }
+ }
+
+
+
+ return true;
+
+ }
+ });
+ if (result)
+ myDelta++;
+ }
+ else {
+ // remove on odd turns
+
+ result = Thread.doIt(new Callable<Boolean>() {
+ public Boolean call() {
+ return intSet.remove(value);
+ }
+ });
+ myRemoveCalls++;
+ if (result)
+ this.myDelta--;
+ }
+ toggle = !toggle;
+ } else {
+ Thread.doIt(new Callable<Void>() {
+ public Void call() {
+ // return null;
+ intSet.contains(element / 100);
+ return null;
+ }
+ });
+ myContainsCalls++;
+ }
+ }
+ } catch (GracefulException g) {
+ // update statistics
+ synchronized (lock) {
+
+ insertCalls += myInsertCalls;
+ removeCalls += myRemoveCalls;
+ containsCalls += myContainsCalls;
+ delta += myDelta;
+ }
+ return;
+ }
+ }
+ }
+
+ public void sanityCheck() {
+ long expected = INITIAL_SIZE + delta;
+ int length = 1;
+
+ int prevValue = Integer.MIN_VALUE;
+ for (int value : this) {
+ length++;
+ if (value < prevValue) {
+ System.out.println("ERROR: set not sorted");
+ System.exit(0);
+ }
+ if (value == prevValue) {
+ System.out.println("ERROR: set has duplicates!");
+ System.exit(0);
+ }
+ if (length == expected) {
+ System.out.println("ERROR: set has bad length!");
+ System.exit(0);
+ }
+
+ }
+ System.out.println("Integer Set OK");
+ }
+
+ /**
+ * Creates a new IntSetBenchmark
+ */
+ public IntSetBenchmark() {
+ int size = 2;
+ init();
+ Random random = new Random(this.hashCode());
+ while (size < INITIAL_SIZE) {
+ if (insert(random.nextInt())) {
+ size++;
+ }
+ }
+ }
+
+ public void printTree(){};
+
+}
--- /dev/null
+/*
+ * List.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.benchmark;
+
+import dstm2.atomic;
+import dstm2.factory.Factory;
+import dstm2.Thread;
+import java.util.Iterator;
+
+/**
+ * @author Maurice Herlihy
+ */
+public class List extends IntSetBenchmark {
+
+ static Factory<INode> factory = Thread.makeFactory(INode.class);
+
+ protected INode first;
+
+ protected void init() {
+ INode firstList = factory.create();
+ firstList.setValue(Integer.MIN_VALUE);
+ this.first = firstList;
+ INode firstNext = factory.create();
+ firstNext.setValue(Integer.MAX_VALUE);
+ firstList.setNext(firstNext);
+ }
+
+ /**
+ * This method does all the work. It returns a
+ * <code>dstm.benchmark.IntSetBenchmark.Neighborhood</code> object containing
+ * the transactional node with maximal value strictly less than v, and the
+ * non-transactional TestFactory element containing v (or null, if none exists).
+ * @param v value sought
+ * @return neighborhood of value
+ */
+ protected Neighborhood find(int v) {
+ INode prevNode = this.first;
+ INode currNode = prevNode.getNext();
+ while (currNode.getValue() < v) {
+ prevNode = currNode;
+ currNode = prevNode.getNext();
+ }
+ if (currNode.getValue() == v)
+ return new Neighborhood(prevNode, currNode);
+ else
+ return new Neighborhood(prevNode);
+ }
+
+ /**
+ * Add an element to the integer set, if it is not already there.
+ * @param v the integer value to add from the set
+ * @return true iff value was added.
+ */
+ public boolean insert(int v) {
+ INode newNode = factory.create();
+ newNode.setValue(v);
+ Neighborhood hood = find(v);
+ if (hood.currNode != null) {
+ return false;
+ } else {
+ INode prevNode = hood.prevNode;
+ newNode.setNext(prevNode.getNext());
+ prevNode.setNext(newNode);
+ return true;
+ }
+ }
+
+ /**
+ * Tests wheter a value is in an the integer set.
+ * @param v the integer value to insert into the set
+ * @return true iff presence was confirmed.
+ */
+ public boolean contains(int v) {
+ Neighborhood hood = find(v);
+ return hood.currNode != null;
+ }
+
+ /**
+ * Removes an element from the integer set, if it is there.
+ * @param v the integer value to delete from the set
+ * @return true iff v was removed
+ */
+ public boolean remove(int v) {
+ INode newNode = factory.create();
+ newNode.setValue(v);
+ Neighborhood hood = find(v);
+ if (hood.currNode == null) {
+ return false;
+ } else {
+ INode prevNode = hood.prevNode;
+ prevNode.setNext(hood.currNode.getNext());
+ return true;
+ }
+ }
+
+ @atomic public interface INode {
+ int getValue();
+ void setValue(int value);
+ INode getNext();
+ void setNext(INode value);
+ }
+
+ public Iterator<Integer> iterator() {
+ return new Iterator<Integer>() {
+ INode cursor = List.this.first.getNext();
+ public boolean hasNext() {
+ return cursor.getNext().getValue() != Integer.MAX_VALUE;
+ }
+ public Integer next() {
+ INode node = cursor;
+ cursor = cursor.getNext();
+ return node.getValue();
+ }
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+ };
+ }
+ protected class Neighborhood {
+ public INode prevNode;
+ public INode currNode;
+ public Neighborhood(INode prevNode, INode currNode) {
+ this.prevNode = prevNode;
+ this.currNode = currNode;
+ }
+ public Neighborhood(INode prevNode) {
+ this.prevNode = prevNode;
+ }
+ }
+
+ public Thread createThread(int which) {
+ throw new UnsupportedOperationException("Not supported yet.");
+ }
+
+
+
+
+
+}
--- /dev/null
+/*
+ * ListRelease.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.benchmark;
+
+import dstm2.atomic;
+import dstm2.factory.Factory;
+import dstm2.Thread;
+import dstm2.factory.Releasable;
+import java.lang.reflect.Method;
+import java.util.Iterator;
+
+/**
+ * @author Maurice Herlihy
+ */
+public class ListRelease extends IntSetBenchmark {
+
+ static Factory<INode> factory = Thread.makeFactory(INode.class);
+
+ protected INode first;
+
+ protected void init() {
+ INode firstList = factory.create();
+ firstList.setValue(Integer.MIN_VALUE);
+ this.first = firstList;
+ INode firstNext = factory.create();
+ firstNext.setValue(Integer.MAX_VALUE);
+ firstList.setNext(firstNext);
+ }
+
+ /**
+ * This method does all the work. It returns a
+ * <code>dstm.benchmark.IntSetBenchmark.Neighborhood</code> object containing
+ * the transactional node with maximal value strictly less than v, and the
+ * non-transactional TestFactory element containing v (or null, if none exists).
+ * @param v value sought
+ * @return neighborhood of value
+ */
+ protected Neighborhood find(int v) {
+ INode last = null;
+ INode prev = this.first;
+ INode curr = prev.getNext();
+ while (curr.getValue() < v) {
+ if (last != null) {
+ ((Releasable)last).release();
+ }
+ prev = curr;
+ curr = prev.getNext();
+ }
+ if (curr.getValue() == v)
+ return new Neighborhood(prev, curr);
+ else
+ return new Neighborhood(prev);
+ }
+
+ /**
+ * Add an element to the integer set, if it is not already there.
+ * @param v the integer value to add from the set
+ * @return true iff value was added.
+ */
+ public boolean insert(int v) {
+ INode newNode = factory.create();
+ newNode.setValue(v);
+ Neighborhood hood = find(v);
+ if (hood.curr != null) {
+ return false;
+ } else {
+ INode prev = hood.prev;
+ newNode.setNext(prev.getNext());
+ prev.setNext(newNode);
+ return true;
+ }
+ }
+
+ /**
+ * Tests wheter a value is in an the integer set.
+ * @param v the integer value to insert into the set
+ * @return true iff presence was confirmed.
+ */
+ public boolean contains(int v) {
+ Neighborhood hood = find(v);
+ return hood.curr != null;
+ }
+
+ /**
+ * Removes an element from the integer set, if it is there.
+ * @param v the integer value to delete from the set
+ * @return true iff v was removed
+ */
+ public boolean remove(int v) {
+ INode newNode = factory.create();
+ newNode.setValue(v);
+ Neighborhood hood = find(v);
+ if (hood.curr == null) {
+ return false;
+ } else {
+ INode prev = hood.prev;
+ prev.setNext(hood.curr.getNext());
+ return true;
+ }
+ }
+
+ @atomic public interface INode {
+ int getValue();
+ void setValue(int value);
+ INode getNext();
+ void setNext(INode value);
+ }
+
+ public Iterator<Integer> iterator() {
+ return new Iterator<Integer>() {
+ INode cursor = ListRelease.this.first.getNext();
+ public boolean hasNext() {
+ return cursor.getNext().getValue() != Integer.MAX_VALUE;
+ }
+ public Integer next() {
+ INode node = cursor;
+ cursor = cursor.getNext();
+ return node.getValue();
+ }
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+ };
+ }
+ protected class Neighborhood {
+ public INode prev;
+ public INode curr;
+ public Neighborhood(INode prev, INode curr) {
+ this.prev = prev;
+ this.curr = curr;
+ }
+ public Neighborhood(INode prev) {
+ this.prev = prev;
+ }
+ }
+
+ public Thread createThread(int which) {
+ throw new UnsupportedOperationException("Not supported yet.");
+ }
+}
--- /dev/null
+/*
+ * ListSnap.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.benchmark;
+//import TransactionalIO.exceptions.AbortedException;
+import TransactionalIO.exceptions.*;//GracefulException;
+import dstm2.atomic;
+import dstm2.benchmark.IntSetBenchmark;
+import dstm2.Thread;
+import dstm2.factory.Factory;
+import dstm2.factory.Snapable;
+import java.lang.reflect.Method;
+import java.util.Iterator;
+import java.util.concurrent.Callable;
+
+/**
+ * @author Maurice Herlihy
+ */
+public class ListSnap extends IntSetBenchmark {
+
+ static Factory<INode> factory = Thread.makeFactory(INode.class);
+
+ protected INode first;
+
+ protected void init() {
+ INode firstList = factory.create();
+ firstList.setValue(Integer.MIN_VALUE);
+ this.first = firstList;
+ INode firstNext = factory.create();
+ firstNext.setValue(Integer.MAX_VALUE);
+ firstList.setNext(firstNext);
+ }
+
+ /**
+ * Tests wheter a value is in an the integer set.
+ * @param v the integer value to insert into the set
+ * @return true iff presence was confirmed.
+ */
+ public boolean contains(int v) {
+ INode last = null;
+ INode lastSnap = null;
+ INode prev = this.first;
+ INode prevSnap = ((Snapable<INode>)prev).snapshot();
+ INode curr = prevSnap.getNext();
+ INode currSnap = ((Snapable<INode>)curr).snapshot();
+ while (currSnap.getValue()< v) {
+ if (last != null) {
+ ((Snapable<INode>)last).validate(lastSnap);
+ }
+ last = prev;
+ lastSnap = prevSnap;
+ prev = curr;
+ prevSnap = currSnap;
+ curr = prevSnap.getNext();
+ currSnap = ((Snapable<INode>)curr).snapshot();
+ }
+ if (lastSnap != null) {
+ ((Snapable<INode>)last).upgrade(lastSnap);
+ }
+ ((Snapable<INode>)prev).upgrade(prevSnap);
+ ((Snapable<INode>)curr).upgrade(currSnap);
+ return (curr.getValue()== v);
+ }
+
+ /**
+ * Removes an element from the integer set, if it is there.
+ * @param v the integer value to delete from the set
+ * @return true iff v was removed
+ */
+ public boolean remove(int v) {
+ INode last = null;
+ INode lastSnap = null;
+ INode prev = this.first;
+ INode prevSnap = ((Snapable<INode>)prev).snapshot();
+ INode curr = prevSnap.getNext();
+ INode currSnap = ((Snapable<INode>)curr).snapshot();
+ while (currSnap.getValue()< v) {
+ if (last != null) {
+ ((Snapable<INode>)last).validate(lastSnap);
+ }
+ last = prev;
+ lastSnap = prevSnap;
+ prev = curr;
+ prevSnap = currSnap;
+ curr = prevSnap.getNext();
+ currSnap = ((Snapable<INode>)curr).snapshot();
+ }
+ if (lastSnap != null) {
+ ((Snapable<INode>)last).upgrade(lastSnap);
+ }
+ ((Snapable<INode>)prev).upgrade(prevSnap);
+ ((Snapable<INode>)curr).upgrade(currSnap);
+ if (curr.getValue()!= v) {
+ return false;
+ } else {
+ prev.setNext(curr.getNext());
+ return true;
+ }
+ }
+
+ public boolean insert(int v) {
+ INode last = null;
+ INode lastSnap = null;
+ INode prev = this.first;
+ Snapable<INode> prevS = (Snapable<INode>)prev;
+ INode prevSnap = prevS.snapshot();
+ INode curr = prevSnap.getNext();
+ INode currSnap = ((Snapable<INode>)curr).snapshot();
+ INode newNode = factory.create();
+ while (currSnap.getValue()< v) {
+ if (last != null) {
+ ((Snapable<INode>)last).validate(lastSnap);
+ }
+ last = prev;
+ lastSnap = prevSnap;
+ prev = curr;
+ prevSnap = currSnap;
+ curr = prevSnap.getNext();
+ currSnap = ((Snapable<INode>)curr).snapshot();
+ }
+ if (lastSnap != null) {
+ ((Snapable<INode>)last).upgrade(lastSnap);
+ }
+ ((Snapable<INode>)prev).upgrade(prevSnap);
+ ((Snapable<INode>)curr).upgrade(currSnap);
+ if (currSnap.getValue()== v) {
+ return false;
+ } else {
+ newNode.setNext(curr);
+ prev.setNext(newNode);
+ return true;
+ }
+ }
+
+ public Iterator<Integer> iterator() {
+ return new Iterator<Integer>() {
+ INode cursor = ListSnap.this.first.getNext();
+ public boolean hasNext() {
+ return cursor.getNext().getValue() == Integer.MAX_VALUE;
+ }
+ public Integer next() {
+ INode node = cursor;
+ cursor = cursor.getNext();
+ return node.getValue();
+ }
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+ };
+ }
+ protected class Neighborhood {
+ public INode prev;
+ public INode curr;
+ public Neighborhood(INode prev, INode curr) {
+ this.prev = prev;
+ this.curr = curr;
+ }
+ public Neighborhood(INode prev) {
+ this.prev = prev;
+ }
+ }
+
+ @atomic public interface INode {
+ int getValue();
+ void setValue(int value);
+ INode getNext();
+ void setNext(INode value);
+ }
+
+ public Thread createThread(int which) {
+ throw new UnsupportedOperationException("Not supported yet.");
+ }
+}
+
--- /dev/null
+/*
+ * To change this template, choose Tools | Templates
+ * and open the template in the editor.
+ */
+package dstm2.benchmark;
+
+import java.io.BufferedReader;
+import java.io.BufferedWriter;
+import java.io.FileReader;
+import java.io.FileWriter;
+import java.io.IOException;
+import java.util.logging.Level;
+import dstm2.Thread;
+import dstm2.Defaults;
+import java.io.File;
+
+
+/**
+ *
+ * @author navid
+ */
+public class Main {
+
+ /**
+ * @param args the command line arguments
+ * The first args is the name of the output file args[0]
+ * The second args is the name of the randomwords input file args[1]
+ * The third args is the name of the sequential words input file args[2]
+ */
+ public static void main(String[] args) {
+
+ // Code For Inserting Words From Random File to The Binary Tree
+
+ int numThreads = 20;//THREADS;
+ int numMillis = Defaults.TIME;
+ int experiment = Defaults.EXPERIMENT;
+ String managerClassName = Defaults.MANAGER;
+ Class managerClass = null;
+ String benchmarkClassName = null;
+ Class benchmarkClass = null;
+ double ii = (double)new File("/home/navid/iliad.text").length() / (double)20;
+
+ System.out.println(Math.ceil(ii));
+ String adapterClassName = Defaults.ADAPTER;
+
+ // discard statistics from previous runs
+ Thread.clear();
+ // Parse and check the args
+ int argc = 0;
+ try {
+ while (argc < args.length) {
+ String option = args[argc++];
+ if (option.equals("-m"))
+ managerClassName = args[argc];
+ else if (option.equals("-b"))
+ benchmarkClassName = args[argc];
+ else if (option.equals("-t"))
+ numThreads = Integer.parseInt(args[argc]);
+ else if (option.equals("-n"))
+ numMillis = Integer.parseInt(args[argc]);
+ else if (option.equals("-e"))
+ experiment = Integer.parseInt(args[argc]);
+ else if (option.equals("-a"))
+ adapterClassName = args[argc];
+ else
+ reportUsageErrorAndDie();
+ argc++;
+ }
+ } catch (NumberFormatException e) {
+ System.out.println("Expected a number: " + args[argc]);
+ System.exit(0);
+ } catch (Exception e) {
+ reportUsageErrorAndDie();
+ }
+
+ // Initialize contention manager.
+ try {
+ managerClass = Class.forName(Defaults.MANAGER);
+ Thread.setContentionManagerClass(managerClass);
+ } catch (ClassNotFoundException ex) {
+ reportUsageErrorAndDie();
+ }
+
+ // Initialize adapter class
+ Thread.setAdapterClass(adapterClassName);
+
+ // initialize benchmark
+ Benchmark benchmark = null;
+ try {
+ benchmarkClass = Class.forName(benchmarkClassName);
+ benchmark = (Benchmark) benchmarkClass.newInstance();
+
+ } catch (InstantiationException e) {
+ System.out.format("%s does not implement dstm.benchmark.Benchmark: %s\n", benchmarkClass, e);
+ System.exit(0);
+ } catch (ClassCastException e) {
+ System.out.format("Exception when creating class %s: %s\n", benchmarkClass, e);
+ System.exit(0);
+ } catch (Exception e) {
+ e.printStackTrace(System.out);
+ System.exit(0);
+ }
+
+ // Set up the benchmark
+ long startTime = 0;
+
+ Thread[] thread = new Thread[numThreads];
+ System.out.println("Benchmark: " + benchmarkClass);
+ System.out.println("Adapter: " + adapterClassName);
+ System.out.println("Contention manager: " + managerClassName);
+ System.out.println("Threads: " + numThreads);
+ System.out.println("Mix: " + experiment + "% updates");
+
+
+ TransactionalIO.benchmarks.benchmark.init();
+
+ // System.out.println((char)97);
+ int j = 97;
+ try {
+ for (int i = 0; i < numThreads; i++){
+
+ //thread[i] = benchmark.createThread(experiment, (char)j);
+ thread[i] = benchmark.createThread(experiment, (char)j);
+ j++;
+ }
+
+ startTime = System.currentTimeMillis();
+ for (int i = 0; i < numThreads; i++)
+ thread[i].start();
+ // Thread.sleep(numMillis);
+ // Thread.stop = true; // notify threads to stop
+ for (int i = 0; i < numThreads; i++) {
+ thread[i].join();
+ }
+ } catch (Exception e) {
+ e.printStackTrace(System.out);
+ System.exit(0);
+ }
+ long stopTime = System.currentTimeMillis();
+
+ double elapsed = (double)(stopTime - startTime) / 1000.0;
+
+ // Run the sanity check for this benchmark
+ try {
+ benchmark.sanityCheck();
+ } catch (Exception e) {
+ e.printStackTrace(System.out);
+ }
+
+ long committed = Thread.totalCommitted;
+ long total = Thread.totalTotal;
+ if (total > 0) {
+ System.out.printf("Committed: %d\nTotal: %d\nPercent committed: (%d%%)\n",
+ committed,
+ total,
+ (100 * committed) / total);
+ } else {
+ System.out.println("No transactions executed!");
+ }
+ benchmark.report();
+ System.out.println("Elapsed time: " + elapsed + " seconds.");
+ System.out.println("------------------------------------------");
+
+
+
+
+ }
+ private static void reportUsageErrorAndDie() {
+ System.out.println("usage: dstm2.Main -b <benchmarkclass> [-m <managerclass>] [-t <#threads>] [-n <#time-in-ms>] [-e <experiment#>] [-a <adapter>]");
+ System.exit(0);
+ }
+
+}
--- /dev/null
+/*
+ * To change this template, choose Tools | Templates
+ * and open the template in the editor.
+ */
+
+package dstm2.benchmark;
+
+import dstm2.Defaults;
+import dstm2.Thread;
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.util.Vector;
+import javax.swing.KeyStroke;
+
+/**
+ *
+ * @author navid
+ */
+public class Main_for_Book_BenchMArk {
+ public static void main(String args[]){
+ // Code For Inserting Words From Random File to The Binary Tree
+ int numThreads = 2;//THREADS;
+ int numMillis = Defaults.TIME;
+ int experiment = Defaults.EXPERIMENT;
+ String managerClassName = Defaults.MANAGER;
+ Class managerClass = null;
+ String benchmarkClassName = null;
+ Class benchmarkClass = null;
+
+
+
+ String adapterClassName = Defaults.ADAPTER;
+
+ // discard statistics from previous runs
+ Thread.clear();
+ // Parse and check the args
+ int argc = 0;
+ try {
+ while (argc < args.length) {
+ String option = args[argc++];
+ if (option.equals("-m"))
+ managerClassName = args[argc];
+ else if (option.equals("-b"))
+ benchmarkClassName = args[argc];
+ else if (option.equals("-t"))
+ numThreads = Integer.parseInt(args[argc]);
+ else if (option.equals("-n"))
+ numMillis = Integer.parseInt(args[argc]);
+ else if (option.equals("-e"))
+ experiment = Integer.parseInt(args[argc]);
+ else if (option.equals("-a"))
+ adapterClassName = args[argc];
+ else
+ reportUsageErrorAndDie();
+ argc++;
+ }
+ } catch (NumberFormatException e) {
+ System.out.println("Expected a number: " + args[argc]);
+ System.exit(0);
+ } catch (Exception e) {
+ reportUsageErrorAndDie();
+ }
+
+ // Initialize contention manager.
+ try {
+ managerClass = Class.forName(Defaults.MANAGER);
+ Thread.setContentionManagerClass(managerClass);
+ } catch (ClassNotFoundException ex) {
+ reportUsageErrorAndDie();
+ }
+
+ // Initialize adapter class
+ Thread.setAdapterClass(adapterClassName);
+
+ // initialize benchmark
+ CustomBenchmark benchmark = null;
+ try {
+ benchmarkClass = Class.forName(benchmarkClassName);
+ benchmark = (CustomBenchmark) benchmarkClass.newInstance();
+
+ } catch (InstantiationException e) {
+ System.out.format("%s does not implement dstm.benchmark.Benchmark: %s\n", benchmarkClass, e);
+ System.exit(0);
+ } catch (ClassCastException e) {
+ System.out.format("Exception when creating class %s: %s\n", benchmarkClass, e);
+ System.exit(0);
+ } catch (Exception e) {
+ e.printStackTrace(System.out);
+ System.exit(0);
+ }
+
+ // Set up the benchmark
+ long startTime = 0;
+
+ CustomThread[] thread = new CustomThread[numThreads];
+ System.out.println("Benchmark: " + benchmarkClass);
+ System.out.println("Adapter: " + adapterClassName);
+ System.out.println("Contention manager: " + managerClassName);
+ System.out.println("Threads: " + numThreads);
+ System.out.println("Mix: " + experiment + "% updates");
+ TransactionalIO.benchmarks.benchmark.init();
+
+
+ // for(int k=0 ; k<400; k++){
+
+
+ // System.out.println((char)97);
+ int j = 97;
+ try {
+ for (int i = 0; i < numThreads; i++){
+
+ //thread[i] = benchmark.createThread(experiment, (char)j);
+
+ thread[i] = new CustomThread(benchmark);
+ j++;
+ }
+
+ startTime = System.currentTimeMillis();
+ for (int i = 0; i < numThreads; i++)
+ thread[i].start();
+ // Thread.sleep(numMillis);
+ // Thread.stop = true; // notify threads to stop
+ for (int i = 0; i < numThreads; i++) {
+ thread[i].join();
+ }
+
+ } catch (Exception e) {
+ e.printStackTrace(System.out);
+ System.exit(0);
+ }
+ long stopTime = System.currentTimeMillis();
+
+ double elapsed = (double)(stopTime - startTime) / 1000.0;
+
+ // Run the sanity check for this benchmark
+ try {
+ benchmark.sanityCheck();
+ } catch (Exception e) {
+ e.printStackTrace(System.out);
+ }
+
+ long committed = Thread.totalCommitted;
+ long total = Thread.totalTotal;
+ if (total > 0) {
+ System.out.printf("Committed: %d\nTotal: %d\nPercent committed: (%d%%)\n",
+ committed,
+ total,
+ (100 * committed) / total);
+ } else {
+ System.out.println("No transactions executed!");
+ }
+ benchmark.report();
+ System.out.println("Elapsed time: " + elapsed + " seconds.");
+ System.out.println("------------------------------------------");
+
+ /* BufferedReader dataIn = new BufferedReader(new
+ InputStreamReader( System.in) );
+
+ String name = "";
+ try{
+ name = dataIn.readLine();
+ }catch( IOException e ){
+ System.out.println("Error!");
+ }*/
+ // }
+ // benchmark.printResults();
+
+ }
+ private static void reportUsageErrorAndDie() {
+ System.out.println("usage: dstm2.Main -b <benchmarkclass> [-m <managerclass>] [-t <#threads>] [-n <#time-in-ms>] [-e <experiment#>] [-a <adapter>]");
+ System.exit(0);
+ }
+
+}
--- /dev/null
+/*
+ * To change this template, choose Tools | Templates
+ * and open the template in the editor.
+ */
+
+package dstm2.benchmark;
+
+import TransactionalIO.benchmarks.benchmark;
+import TransactionalIO.core.TransactionalFile;
+import java.io.IOException;
+import java.io.RandomAccessFile;
+import java.util.Vector;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+/**
+ *
+ * @author navid
+ */
+public class PureIO extends CustomBenchmark{
+
+ @Override
+ protected void init() {
+
+ }
+
+
+ protected void execute() {
+ try {
+ TransactionalFile f1 = (TransactionalFile)benchmark.m.get("0");
+ // RandomAccessFile f1 = ((TransactionalFile) benchmark.m.get("0")).file;
+ byte[] data = new byte[1];
+ char[] holder = new char[10000];
+ char[] word = new char[20];
+ boolean flag = false;
+ long toseek = Integer.valueOf(Thread.currentThread().getName().substring(7)) * 20448;
+
+ // benchmark.filelock.lock();
+ f1.seek(toseek);
+
+ data[0] = 'a';
+ if (toseek != 0) {
+ //////////////// skipt the first word since its been read already
+ while (data[0] != '\n') {
+ int res;
+ res = f1.read(data);
+ if (res == -1) {
+ flag = true;
+ break;
+ }
+ }
+ }
+ while (f1.getFilePointer() < toseek + 20448) {
+ if (flag == true) {
+ break;
+ }
+ data[0] = 'a';
+ int i = 0;
+ int res;
+ while (data[0] != '\n') {
+ res = f1.read(data);
+ if (res == -1) {
+ flag = true;
+ break;
+ }
+
+ holder[i] = (char) data[0];
+ i++;
+ }
+
+
+ byte[] towrite = new byte[String.valueOf(holder, 0, i).length()];
+ towrite = String.valueOf(holder, 0, i).getBytes();
+
+
+
+ // System.out.println(String.valueOf(holder,0,i).toLowerCase().substring(0, 1));
+ //((TransactionalFile) (benchmark.m.get(String.valueOf(holder,0,i).toLowerCase().substring(0, 1)))).file.write(towrite);
+ ((TransactionalFile) (benchmark.m.get(String.valueOf(holder,0,i).toLowerCase().substring(0, 1)))).write(towrite);
+ //update the memory //}
+ }
+ // benchmark.filelock.unlock();
+ } catch (IOException ex) {
+ Logger.getLogger(PureIO.class.getName()).log(Level.SEVERE, null, ex);
+ } catch (NullPointerException e) {
+ e.printStackTrace();
+ }
+ }
+
+ @Override
+ protected void printResults() {
+ throw new UnsupportedOperationException("Not supported yet.");
+ }
+
+ @Override
+ protected void execute(Vector arguments) {
+ throw new UnsupportedOperationException("Not supported yet.");
+ }
+
+}
--- /dev/null
+/*
+ * RBTree.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.benchmark;
+
+import dstm2.atomic;
+import dstm2.benchmark.Benchmark;
+import dstm2.factory.Factory;
+import dstm2.Thread;
+import java.util.EmptyStackException;
+import java.util.Iterator;
+import java.util.Stack;
+
+/**
+ * Red-Black tree benchmark.
+ * Adapted from {@link http://www.codeproject.com/csharp/RedBlackCS.asp
+ * }
+ * @author Maurice Herlihy
+ */
+public class RBTree extends IntSetBenchmark {
+ /**
+ * Transactional RBNode factory.
+ */
+ static Factory<RBNode> factory = Thread.makeFactory(RBNode.class);
+ /**
+ * Each node has one of two colors.
+ */
+ public enum Color {BLACK, RED};
+
+ /**
+ * Left hand of darkness: the actual root of the tree is the left-hand
+ * child of this node. Indirection needed to make changes to the root
+ * transactional.
+ */
+ private RBNode root;
+ /**
+ * Used in place of null pointer.
+ */
+ public static RBNode sentinelNode;
+ /**
+ * Initializes the tree shared by all the threads.
+ **/
+ public void init() {
+ sentinelNode = factory.create();
+ sentinelNode.setLeft(null);
+ sentinelNode.setRight(null);
+ sentinelNode.setParent(null);
+ sentinelNode.setColor(Color.BLACK);
+ root = factory.create();
+ root.setLeft(sentinelNode);
+ this.root.setValue(Integer.MIN_VALUE);
+ this.root.setColor(Color.BLACK);
+ int size = 0;
+ }
+
+ protected RBNode getRoot() {
+ return root.getLeft();
+ }
+
+ protected void setRoot(RBNode value) {
+ root.setLeft(value);
+ }
+
+ /**
+ * Inserts an element into the tree, if it is not already present.
+ * @param key element to insert
+ * @return true iff item was not there already
+ */
+ public boolean insert(int key) {
+ // traverse tree - find where node belongs
+ RBNode node = factory.create();
+ RBNode temp = getRoot();
+
+ while(temp != sentinelNode) { // find Parent
+ node.setParent(temp);
+ if ( key == temp.getValue()) {
+ return false;
+ } else if (key > temp.getValue()) {
+ temp = temp.getRight();
+ } else {
+ temp = temp.getLeft();
+ }
+ }
+
+ // setup node
+ node.setValue(key);
+ node.setLeft(sentinelNode);
+ node.setRight(sentinelNode);
+
+ // insert node into tree starting at parent's location
+ if(node.getParent() != null) {
+ if (node.getValue() > node.getParent().getValue()) {
+ node.getParent().setRight(node);
+ } else
+ node.getParent().setLeft(node);
+ } else
+ setRoot(node); // first node added
+
+ restoreAfterInsert(node); // restore red-black properities
+ return true;
+ }
+
+ /**
+ * Tests whether item is present.
+ * @return whether the item was present</returns>
+ * @param key item to search for
+ */
+ public boolean contains(int key) {
+
+ RBNode node = getRoot(); // begin at root
+
+ // traverse tree until node is found
+ while(node != sentinelNode) {
+ if (key == node.getValue()) {
+ return true;
+ } else if (key < node.getValue()) {
+ node = node.getLeft();
+ } else {
+ node = node.getRight();
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Remove item if present.
+ * @return whether the item was removed</returns>
+ * @param key item to remove
+ */
+ public boolean remove(int key) {
+
+ // find node
+ RBNode node;
+
+ node = getRoot();
+ while(node != sentinelNode) {
+ if (key == node.getValue()) {
+ break;
+ } else if (key < node.getValue()) {
+ node = node.getLeft();
+ } else {
+ node = node.getRight();
+ }
+ }
+
+ if(node == sentinelNode)
+ return false; // key not found
+
+ delete(node);
+ return true;
+ }
+
+ /**
+ * Delete a node.
+ * A node to be deleted will be:
+ * 1. a leaf with no children
+ * 2. have one child
+ * 3. have two children
+ * If the deleted node is red, the red black properties still hold.
+ * If the deleted node is black, the tree needs rebalancing
+ * @param z start at this node
+ */
+ private void delete(RBNode z) {
+
+ RBNode x = factory.create(); // work node to contain the replacement node
+ RBNode y; // work node
+
+ // find the replacement node (the successor to x) - the node one with
+ // at *most* one child.
+ if(z.getLeft() == sentinelNode || z.getRight() == sentinelNode)
+ y = z; // node has sentinel as a child
+ else {
+ // z has two children, find replacement node which will
+ // be the leftmost node greater than z
+ y = z.getRight(); // traverse right subtree
+ while(y.getLeft() != sentinelNode) // to find next node in sequence
+ y = y.getLeft();
+ }
+
+ // at this point, y contains the replacement node. it's content will be copied
+ // to the valules in the node to be deleted
+
+ // x (y's only child) is the node that will be linked to y's old parent.
+ if(y.getLeft() != sentinelNode)
+ x = y.getLeft();
+ else
+ x = y.getRight();
+
+ // replace x's parent with y's parent and
+ // link x to proper subtree in parent
+ // this removes y from the chain
+ x.setParent(y.getParent());
+ if(y.getParent() != null)
+ if(y == y.getParent().getLeft())
+ y.getParent().setLeft(x);
+ else
+ y.getParent().setRight(x);
+ else
+ setRoot(x); // make x the root node
+
+ // copy the values from y (the replacement node) to the node being deleted.
+ // note: this effectively deletes the node.
+ if(y != z) {
+ z.setValue(y.getValue());
+ }
+
+ if(y.getColor() == Color.BLACK)
+ restoreAfterDelete(x);
+ }
+
+ /**
+ * restoreAfterDelete
+ * Deletions from red-black trees may destroy the red-black
+ * properties. Examine the tree and restore. Rotations are normally
+ * required to restore it
+ * @param x start here
+ */
+ private void restoreAfterDelete(RBNode x) {
+ // maintain Red-Black tree balance after deleting node
+
+ RBNode y;
+
+ while(x != getRoot() && x.getColor() == Color.BLACK) {
+ if(x == x.getParent().getLeft()) // determine sub tree from parent
+ {
+ y = x.getParent().getRight(); // y is x's sibling
+ if(y.getColor() == Color.RED) { // x is black, y is red - make both black and rotate
+ y.setColor(Color.BLACK);
+ x.getParent().setColor(Color.RED);
+ rotateLeft(x.getParent());
+ y = x.getParent().getRight();
+ }
+ if(y.getLeft().getColor() == Color.BLACK &&
+ y.getRight().getColor() == Color.BLACK) { // children are both black
+ y.setColor(Color.RED); // change parent to red
+ x = x.getParent(); // move up the tree
+ } else {
+ if(y.getRight().getColor() == Color.BLACK) {
+ y.getLeft().setColor(Color.BLACK);
+ y.setColor(Color.RED);
+ rotateRight(y);
+ y = x.getParent().getRight();
+ }
+ y.setColor(x.getParent().getColor());
+ x.getParent().setColor(Color.BLACK);
+ y.getRight().setColor(Color.BLACK);
+ rotateLeft(x.getParent());
+ setRoot(x);
+ }
+ } else { // right subtree - same as code above with right and left swapped
+ y = x.getParent().getLeft();
+ if(y.getColor() == Color.RED) {
+ y.setColor(Color.BLACK);
+ x.getParent().setColor(Color.RED);
+ rotateRight(x.getParent());
+ y = x.getParent().getLeft();
+ }
+ if(y.getRight().getColor() == Color.BLACK &&
+ y.getLeft().getColor() == Color.BLACK) {
+ y.setColor(Color.RED);
+ x = x.getParent();
+ } else {
+ if(y.getLeft().getColor() == Color.BLACK) {
+ y.getRight().setColor(Color.BLACK);
+ y.setColor(Color.RED);
+ rotateLeft(y);
+ y = x.getParent().getLeft();
+ }
+ y.setColor(x.getParent().getColor());
+ x.getParent().setColor(Color.BLACK);
+ y.getLeft().setColor(Color.BLACK);
+ rotateRight(x.getParent());
+ setRoot(x);
+ }
+ }
+ }
+ x.setColor(Color.BLACK);
+ }
+
+ /**
+ * Insertions may destroy the red-black properties. Examine the tree
+ * and rotate as needed to restore the property.
+ * @param x start here
+ */
+ private void restoreAfterInsert(RBNode x) {
+ RBNode y;
+
+ // maintain red-black tree properties after adding x
+ while(x != getRoot() && x.getParent().getColor() == Color.RED) {
+ // Parent node is .Colored red;
+ if(x.getParent() == x.getParent().getParent().getLeft()) // determine traversal path
+ { // is it on the Left or Right subtree?
+ y = x.getParent().getParent().getRight(); // get uncle
+ if(y!= null && y.getColor() == Color.RED) { // uncle is red; change x's Parent and uncle to black
+ x.getParent().setColor(Color.BLACK);
+ y.setColor(Color.BLACK);
+ // grandparent must be red. Why? Every red node that is not
+ // a leaf has only black children
+ x.getParent().getParent().setColor(Color.RED);
+ x = x.getParent().getParent(); // continue loop with grandparent
+ } else {
+ // uncle is black; determine if x is greater than Parent
+ if(x == x.getParent().getRight()) { // yes, x is greater than Parent; rotate Left
+ // make x a Left child
+ x = x.getParent();
+ rotateLeft(x);
+ }
+ // no, x is less than Parent
+ x.getParent().setColor(Color.BLACK); // make Parent black
+ x.getParent().getParent().setColor(Color.RED); // make grandparent black
+ rotateRight(x.getParent().getParent()); // rotate right
+ }
+ } else { // x's Parent is on the Right subtree
+ // this code is the same as above with "Left" and "Right" swapped
+ y = x.getParent().getParent().getLeft();
+ if(y!= null && y.getColor() == Color.RED) {
+ x.getParent().setColor(Color.BLACK);
+ y.setColor(Color.BLACK);
+ x.getParent().getParent().setColor(Color.RED);
+ x = x.getParent().getParent();
+ } else {
+ if(x == x.getParent().getLeft()) {
+ x = x.getParent();
+ rotateRight(x);
+ }
+ x.getParent().setColor(Color.BLACK);
+ x.getParent().getParent().setColor(Color.RED);
+ rotateLeft(x.getParent().getParent());
+ }
+ }
+ }
+ getRoot().setColor(Color.BLACK); // root should always be black
+ }
+
+ /**
+ * rotateLeft
+ * Rebalance the tree by rotating the nodes to the left
+ * @param x start here
+ */
+ public void rotateLeft(RBNode x) {
+ // pushing node x down and to the Left to balance the tree. x's Right child (y)
+ // replaces x (since y > x), and y's Left child becomes x's Right child
+ // (since it's < y but > x).
+
+ RBNode y = x.getRight(); // get x's Right node, this becomes y
+
+ // set x's Right link
+ x.setRight(y.getLeft()); // y's Left child's becomes x's Right child
+
+ // modify parents
+ if(y.getLeft() != sentinelNode)
+ y.getLeft().setParent(x); // sets y's Left Parent to x
+
+ if(y != sentinelNode)
+ y.setParent(x.getParent()); // set y's Parent to x's Parent
+
+ if(x.getParent() != null) { // determine which side of it's Parent x was on
+ if(x == x.getParent().getLeft())
+ x.getParent().setLeft(y); // set Left Parent to y
+ else
+ x.getParent().setRight(y); // set Right Parent to y
+ } else
+ setRoot(y); // at root, set it to y
+
+ // link x and y
+ y.setLeft(x); // put x on y's Left
+ if(x != sentinelNode) // set y as x's Parent
+ x.setParent(y);
+ }
+
+ /**
+ * rotateRight
+ * Rebalance the tree by rotating the nodes to the right
+ * @param x start here
+ */
+ public void rotateRight(RBNode x) {
+ // pushing node x down and to the Right to balance the tree. x's Left child (y)
+ // replaces x (since x < y), and y's Right child becomes x's Left child
+ // (since it's < x but > y).
+
+ RBNode y = x.getLeft(); // get x's Left node, this becomes y
+
+ // set x's Right link
+ x.setLeft(y.getRight()); // y's Right child becomes x's Left child
+
+ // modify parents
+ if(y.getRight() != sentinelNode)
+ y.getRight().setParent(x); // sets y's Right Parent to x
+
+ if(y != sentinelNode)
+ y.setParent(x.getParent()); // set y's Parent to x's Parent
+
+ if(x.getParent() != null) // null=root, could also have used root
+ { // determine which side of its Parent x was on
+ if(x == x.getParent().getRight())
+ x.getParent().setRight(y); // set Right Parent to y
+ else
+ x.getParent().setLeft(y); // set Left Parent to y
+ } else
+ setRoot(y); // at root, set it to y
+
+ // link x and y
+ y.setRight(x); // put x on y's Right
+ if(x != sentinelNode) // set y as x's Parent
+ x.setParent(y);
+ }
+
+ /**
+ * returns number of black nodes akibg root to leaf path
+ * @param root tree root
+ * @return number of black nodes in left-most path
+ */
+ private int countBlackNodes(RBNode root) {
+ if (sentinelNode == root)
+ return 0;
+ int me = (root.getColor() == Color.BLACK) ? 1 : 0;
+ RBNode left = (sentinelNode == root.getLeft())
+ ? sentinelNode
+ : root.getLeft();
+ return me + countBlackNodes(left);
+ }
+
+ /**
+ * counts nodes in tree
+ * @param root tree root
+ * @return number of nodes in tree
+ */
+ private int count(RBNode root) {
+ if (root == sentinelNode)
+ return 0;
+ return 1 + count(root.getLeft()) + count(root.getRight());
+ }
+
+ /**
+ * Checks internal consistency.
+ * @param root tree root
+ * @param blackNodes number of black nodes expected in leaf-to-root path
+ * @param soFar number of black nodes seen in path so far
+ */
+ private void recursiveValidate(RBNode root, int blackNodes, int soFar) {
+ // Empty sub-tree is vacuously OK
+ if (sentinelNode == root)
+ return;
+
+ Color rootcolor = root.getColor();
+ soFar += ((Color.BLACK == rootcolor) ? 1 : 0);
+ root.setMarked(true);
+
+ // Check left side
+ RBNode left = root.getLeft();
+ if (sentinelNode != left) {
+ if (left.getColor() != Color.RED || rootcolor != Color.RED) {
+ System.out.println("Error: Two consecutive red nodes!");
+ }
+ if (left.getValue() < root.getValue()) {
+ System.out.println(" Error; Tree values out of order!");
+ }
+ if (!left.isMarked()) {
+ System.out.println("Error; Cycle in tree structure!");
+ }
+ recursiveValidate(left, blackNodes, soFar);
+ }
+
+ // Check right side
+ RBNode right = root.getRight();
+ if (sentinelNode != right) {
+ if (right.getColor() != Color.RED || rootcolor != Color.RED) {
+ System.out.println("Error: Two consecutive red nodes!");
+ }
+ if (right.getValue() > root.getValue()) {
+ System.out.println("Error: Tree values out of order!");
+ }
+ if (!right.isMarked()) {
+ System.out.println("Error: Cycle in tree structure!");
+ }
+ recursiveValidate(right, blackNodes, soFar);
+ }
+
+ // Check black node count
+ if (sentinelNode == root.getLeft() || sentinelNode == root.getRight()) {
+ if (soFar != blackNodes) {
+ System.out.println("Error: Variable number of black nodes to leaves!");
+ return;
+ }
+ }
+ // Everything checks out if we get this far.
+ return;
+ }
+
+ public Iterator<Integer> iterator() {
+ return new MyIterator();
+ }
+
+ /**
+ * Tree node definition. Implemented by transactional factory.
+ */
+ @atomic public interface RBNode {
+
+ /**
+ * Reads node value.
+ * @return node value
+ */
+ public int getValue();
+
+ /**
+ * sets node value
+ * @param newValue new value for node
+ */
+ public void setValue(int newValue);
+
+ /**
+ * is node marked?
+ * @return whether node is marked
+ */
+ public boolean isMarked();
+
+ /**
+ * mark or unmark node
+ * @param newMarked new value for marked flag
+ */
+ public void setMarked(boolean newMarked);
+
+ /**
+ * examine node color
+ * @return node color
+ */
+ public Color getColor();
+
+ /**
+ * change node's color
+ * @param newColor new color
+ */
+ public void setColor(Color newColor);
+
+ /**
+ * examine node's parent
+ * @return node's parent
+ */
+ public RBNode getParent();
+
+ /**
+ * change node's parent
+ * @param newParent new parent
+ */
+ public void setParent(RBNode newParent);
+
+ /**
+ * examine node's left child
+ * @return node's left child
+ */
+ public RBNode getLeft();
+
+ /**
+ * change node's right child
+ * @param newLeft new left child
+ */
+ public void setLeft(RBNode newLeft);
+
+ /**
+ * examine node's right child
+ * @return node's right child
+ */
+ public RBNode getRight();
+
+ /**
+ * change node's left child
+ * @param newRight new right child
+ */
+ public void setRight(RBNode newRight);
+
+ }
+
+ private class MyIterator implements Iterator<Integer> {
+ RBNode node = getRoot();
+ RBNode prev = node;
+ RBNode next = node;
+ Stack<RBNode> stack = new Stack<RBNode>();
+ MyIterator() {
+ while (node != sentinelNode) {
+ stack.push(node);
+ node = node.getLeft();
+ }
+ next = prev = stack.peek();
+ }
+ public boolean hasNext() {
+ return !stack.empty();
+ }
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ public Integer next() {
+ prev = next;
+ node = stack.peek();
+ // If I have a right child, move there and descend left
+ if (node.getRight() != sentinelNode) {
+ node = node.getRight();
+ while (node != sentinelNode) {
+ stack.push(node);
+ node = node.getLeft();
+ }
+ } else {
+ RBNode seen = sentinelNode;
+ while (node.getRight() == seen) {
+ seen = stack.pop();
+ if (stack.empty()) {
+ next = null;
+ break;
+ } else {
+ next = node = stack.peek();
+ }
+ }
+ }
+ return prev.getValue();
+ }
+ }
+
+ public Thread createThread(int which) {
+ throw new UnsupportedOperationException("Not supported yet.");
+ }
+}
--- /dev/null
+/*
+ * SkipList.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.benchmark;
+
+import dstm2.AtomicArray;
+import dstm2.atomic;
+import dstm2.factory.Factory;
+import dstm2.Thread;
+import dstm2.util.Random;
+import java.util.Iterator;
+
+/**
+ * @author Maurice Herlihy
+ */
+public class SkipList extends IntSetBenchmark {
+ /**
+ * Transactional Node factory.
+ */
+ static Factory<Node> factory = Thread.makeFactory(Node.class);
+
+ // Maximum level any node in a skip list can have
+ private final int MaxLevel = 32;
+
+ // Probability factor used to determine the node level
+ private final double Probability = 0.5;
+
+ // The skip list header. It also serves as the NIL node.
+ private Node header;
+
+ // Random number generator for generating random node levels.
+ private Random random;
+
+ // Current maximum list level.
+ private int listLevel;
+
+ protected void init() {
+ int size = 0;
+ header = factory.create();
+ random = new Random();
+ initNode(header, MaxLevel);
+ listLevel = 1;
+ AtomicArray<Node> forward = header.getForward();
+ for (int i = 0; i < MaxLevel; i++) {
+ forward.set(i, header);
+ }
+ }
+
+ public java.util.Iterator<Integer> iterator() {
+ return new MyIterator();
+ }
+
+ public boolean insert(int key) {
+ Node[] update = new Node[MaxLevel];
+ Node curr = search(key, update);
+ // If key does not already exist in the skip list.
+ if(curr.getKey() != key) {
+ insert(key, update);
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ public boolean contains(int key) {
+ Node[] dummy = new Node[MaxLevel];
+ Node curr = search(key, dummy);
+ return curr.getKey() == key;
+ }
+
+ public boolean remove(int key) {
+ Node[] update = new Node[MaxLevel];
+ Node curr = search(key, update);
+ if(curr.getKey() == key) {
+ // Redirect references to victim node to successors.
+ for (int i = 0; i < listLevel && update[i].getForward().get(i) == curr; i++) {
+ update[i].getForward().set(i, curr.getForward().get(i));
+ }
+ return true;
+ }
+ return false;
+ }
+
+ private class MyIterator implements Iterator<Integer> {
+ Node node = header.getForward().get(0);
+ public boolean hasNext() {
+ return node != header;
+ }
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ public Integer next() {
+ node = node.getForward().get(0);
+ return node.getKey();
+ }
+ }
+ /**
+ * Initializes an instant of a Node with its node level.
+ **/
+ public void initNode(Node node, int level) {
+ node.setForward(new AtomicArray<Node>(Node.class, level));
+ }
+
+ /**
+ * Initializes an instant of a Node with its node level and
+ * key/value pair.
+ **/
+ public void initNode(Node node, int level, int key) {
+ node.setForward(new AtomicArray<Node>(Node.class, level));
+ node.setKey(key);
+ }
+
+ /// <summary>
+ /// Returns a level value for a new SkipList node.
+ /// <returns>
+ /// The level value for a new SkipList node.
+ /// </returns>
+ /// </summary>
+ private int getNewLevel() {
+ int level = 1;
+ while(random.nextDouble() < Probability && level < MaxLevel && level <= listLevel) {
+ level++;
+ }
+ return level;
+ }
+
+ /// <summary>
+ /// Inserts a keykey into the SkipList.
+ /// <param name="key">
+ /// The key to insert into the SkipList.
+ /// </param>
+ /// <param name="update">
+ /// An array of nodes holding references to places in the SkipList in
+ /// which the search for the place to insert the new key/value pair
+ /// dropped down one level.
+ /// </param>
+ /// </summary>
+ private void insert(int key, Node[] update) {
+ // Get the level for the new node.
+ int newLevel = getNewLevel();
+ // If new node level greater than skip list level.
+ if (newLevel > listLevel) {
+ // Make sure our update references above the current skip list
+ // level point to the header.
+ for (int i = listLevel; i < newLevel; i++) {
+ update[i] = header;
+ }
+ // The current skip list level is now the new node level.
+ listLevel++;
+ }
+ // Create the new node.
+ Node newNode = factory.create();
+ initNode(newNode, newLevel, key);
+ // Insert the new node into the skip list.
+ for (int i = 0; i < newLevel; i++) {
+ // Initialize new node forward references to update forward references
+ newNode.getForward().set(i, update[i].getForward().get(i));
+ // Set update forward references to new node.
+ update[i].getForward().set(i, newNode);
+ }
+ }
+
+ /// <summary>
+ /// Search for the specified key.
+ /// <param name="_key">
+ /// The key to search for.
+ /// </param>
+ /// <param name="curr">
+ /// A SkipList node to hold the results of the search.
+ /// </param>
+ /// <param name="update">
+ /// An array of nodes holding references to the places in the SkipList
+ /// search in which the search dropped down one level.
+ /// </param>
+ /// <returns>
+ /// Returns node with least key greater than or equal to search key.
+ /// </returns>
+ /// </summary>
+ private Node search(int key, Node[] update) {
+ int comp;
+ // Begin at the start of the skip list.
+ Node curr = header;
+ // Work our way down from the top of the skip list to the bottom.
+ for(int i = listLevel - 1; i >= 0; i--) {
+ comp = curr.getForward().get(i).getKey();
+ // While we haven't reached the end of the skip list and the
+ // current key is less than the search key.
+ while(curr.getForward().get(i) != header && comp < key) {
+ // Move forward in the skip list.
+ curr = curr.getForward().get(i);
+ // Get the current key.
+ comp = curr.getForward().get(i).getKey();
+ }
+ // Keep track of each node where we move down a level. Used later to rearrange
+ // node references when inserting a new element.
+ update[i] = curr;
+ }
+ // Move ahead in the skip list. If the key isn't there, we end up at a node with a
+ // key greater key, and otherwise at a node with the same key.
+ curr = curr.getForward().get(0);
+ return curr;
+ }
+
+ @atomic public interface Node {
+ /**
+ * Get array of nodes further along in the skip list.
+ **/
+ public AtomicArray<Node> getForward();
+ /**
+ * Set array of nodes further along in the skip list.
+ **/
+ public void setForward(AtomicArray<Node> value);
+
+ /**
+ * Get node value.
+ **/
+ public int getKey();
+ /**
+ * Set node value.
+ **/
+ public void setKey(int value);
+ }
+
+ public Thread createThread(int which) {
+ throw new UnsupportedOperationException("Not supported yet.");
+ }
+}
--- /dev/null
+/*
+ * GracefulException.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.exceptions;
+
+/**
+ * Thrown by the BaseContentionManager when the benchmark time has elapsed.
+ **/
+public class GracefulException extends java.lang.RuntimeException {
+ static final long serialVersionUID = 6572490566353395650L;
+
+ /**
+ * Creates a new <code>GracefulException</code> instance with no detail message.
+ */
+ public GracefulException() {
+ super();
+ }
+
+}
--- /dev/null
+/*
+ * AbortedException.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.exceptions;
+/**
+ * Thrown by an attempt to open a <code>TMObject</code> to indicate
+ * that the current transaction cannot commit.
+ **/
+public class MemoryAbortedException extends java.lang.RuntimeException {
+ static final long serialVersionUID = 6572490566353395650L;
+
+ /**
+ * Creates a new <code>DeniedException</code> instance with no detail message.
+ */
+ public MemoryAbortedException() {
+ super();
+ }
+
+
+ /**
+ * Creates a new <code>Denied</code> instance with the specified detail message.
+ * @param msg the detail message.
+ */
+ public MemoryAbortedException(String msg) {
+ super(msg);
+ }
+}
--- /dev/null
+/*
+ * PanicException.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.exceptions;
+
+/**
+ * Thrown to indicate an error in the use of the transactional memory;
+ * that is, a violation of the assumptions of use.
+ */
+public class PanicException extends java.lang.RuntimeException {
+
+ /**
+ * Creates new <code>PanicException</code> with no detail message.
+ */
+ public PanicException() {
+ }
+
+ public PanicException(String format, Object ... args) {
+ super(String.format(format, args));
+ }
+
+ /**
+ * Creates a new <code>PanicException</code> with the specified detail message.
+ *
+ * @param msg the detail message.
+ */
+ public PanicException(String msg) {
+ super(msg);
+ }
+
+ /**
+ * Creates an <code>PanicException</code> with the specified cause.
+ *
+ * @param cause Throwable that caused PanicException to be thrown
+ */
+ public PanicException(Throwable cause) {
+ super(cause);
+ }
+}
+
--- /dev/null
+/*
+ * SnapshotException.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.exceptions;
+
+/**
+ * Thrown if shapshot validation fails. Will abort transaction if not
+ * caught by the application.
+ *
+ * @author Maurice Herlihy
+ */
+public class SnapshotException extends java.lang.RuntimeException {
+
+ /**
+ * Creates a new <code>SnapshotException</code> instance with no detail message.
+ */
+ public SnapshotException() {
+ super();
+ }
+
+
+ /**
+ * Creates a new <code>SnapshotException</code> instance with the specified detail message.
+ * @param msg the detail message.
+ */
+ public SnapshotException(String msg) {
+ super(msg);
+ }
+}
--- /dev/null
+/*
+ * Adapter.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.factory;
+
+/**
+ * User-defined factories use this adapter interface.
+ * @author Maurice Herlihy
+ */
+public interface Adapter<T> {
+ /**
+ * A Setter<V> object represents <code>void setMumble(V value)</code> method.
+ **/
+ public interface Setter<V> {
+ /**
+ * Call setter.
+ */
+ public void call(V x);
+ }
+
+ /**
+ * A Getter<V> object represents <code>V getMumble()</code> method.
+ **/
+ public interface Getter<V> {
+ /**
+ * Call getter.
+ */
+ public V call();
+ }
+
+ /**
+ * creates a Setter<V>
+ * @param methodName Name of setter, e.g., "setValue"
+ * @param _class field class, e.g., <code>int.TYPE</code>
+ * @return <code>Setter<V></code> object to call.
+ */
+ public <V> Setter<V> makeSetter(String methodName, Class<V> _class);
+
+ /**
+ * creates a Getter<V>
+ * @param methodName Name of getter, e.g., "getValue"
+ * @param _class field class, e.g., <code>int.TYPE</code>
+ * @return <code>Getter<V></code> object to call.
+ */
+ public <V> Getter<V> makeGetter(String methodName, Class<V> _class);
+
+
+}
--- /dev/null
+/*
+ * AtomicFactory.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.factory;
+/*
+ * AtomicFactory.java
+ *
+ * Created on November 16, 2005, 1:25 PM
+ *
+ * Copyright 2005 Sun Microsystems, Inc. All Rights Reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to technology embodied in the product that is described in this document. In particular, and without limitation, these intellectual property rights may include one or more of the U.S. patents listed at http://www.sun.com/patents and one or more additional patents or pending patent applications in the U.S. and in other countries.
+ * U.S. Government Rights - Commercial software. Government users are subject to the Sun Microsystems, Inc. standard license agreement and applicable provisions of the FAR and its supplements. Use is subject to license terms.
+ * Sun, Sun Microsystems, the Sun logo and Java are trademarks or registered trademarks of Sun Microsystems, Inc. in the U.S. and other countries.
+ */
+import dstm2.ContentionManager;
+import TransactionalIO.exceptions.AbortedException;
+import TransactionalIO.exceptions.PanicException;
+import dstm2.Transaction;
+import dstm2.Transaction.Status;
+import dstm2.factory.BaseFactory;
+import dstm2.factory.ClassLoader;
+import dstm2.factory.Copyable;
+import dstm2.factory.Property;
+import dstm2.factory.Releasable;
+import dstm2.factory.Snapable;
+import java.lang.reflect.Constructor;
+import java.lang.reflect.InvocationTargetException;
+import org.apache.bcel.Constants;
+import org.apache.bcel.classfile.JavaClass;
+import org.apache.bcel.classfile.Method;
+import org.apache.bcel.generic.*;
+import org.apache.bcel.Repository;
+
+import static org.apache.bcel.Constants.*;
+/**
+ * Factory for constructing atomic objects.
+ * User provides an Adapter class.
+ * @author Maurice Herlihy
+ */
+public class AtomicFactory<T> extends dstm2.factory.BaseFactory<T> {
+
+ Class adapterClass;
+
+ public AtomicFactory(Class<T> _class, Class<? extends dstm2.factory.Adapter> adapterClass) {
+ super(_class);
+ synchronized (lock) { // BCEL is not thread-safe!
+
+ interfaceName = _class.getName();
+ this.adapterClass = adapterClass;
+ className = _class.getName() + "$";
+ Class[] interfaces = adapterClass.getInterfaces();
+ String[] myInterfaces = new String[interfaces.length];
+ myInterfaces[0] = _class.getName();
+ int i = 1;
+ for (Class c : interfaces) {
+ if (!c.equals(dstm2.factory.Adapter.class)) {
+ myInterfaces[i++] = c.getName();
+ }
+ }
+
+ _cg = new ClassGen(className,
+ "java.lang.Object",
+ "Factory.java",
+ ACC_PUBLIC | ACC_SUPER,
+ myInterfaces);
+ _cp = _cg.getConstantPool();
+ _factory = new InstructionFactory(_cg, _cp);
+
+ createFields();
+
+ createCtor();
+
+ for (Property p : properties) {
+ createGetMethod(p);
+ createSetMethod(p);
+ }
+ for (Class c : interfaces) {
+ if (!c.equals(dstm2.factory.Adapter.class)) {
+ JavaClass jc = null;
+ try {
+ jc = Repository.lookupClass(c);
+
+ } catch (java.lang.ClassNotFoundException ex) {
+ throw new PanicException("Class not found: " + _class);
+ }
+ for (Method m : jc.getMethods()) {
+ passThrough(c, m);
+ }
+ }
+ }
+ createStatic();
+ seal();
+ }
+ }
+
+ public T create() {
+ try {
+ synchronized(lock) { // not sure this is needed ...
+ return theClass.newInstance();
+ }
+ } catch (InstantiationException ex) {
+ throw new PanicException(ex);
+ } catch (IllegalAccessException ex) {
+ throw new PanicException(ex);
+ }
+ }
+
+ private String getFieldName(Property p) {
+ return p.getMethod.getName() + "$$";
+ }
+ private String setFieldName(Property p) {
+ return p.setMethod.getName() + "$$";
+ }
+
+ private void createFields() {
+ FieldGen field;
+ // static Class _class;
+ field = new FieldGen(ACC_STATIC, new ObjectType("java.lang.Class"), "_class", _cp);
+ _cg.addField(field.getField());
+ // Adapter adapter;
+ field = new FieldGen(0, new ObjectType(adapterClass.getName()), "adapter", _cp);
+ _cg.addField(field.getField());
+ // getter and setter fields for each property
+ for (Property p : properties) {
+ field = new FieldGen(0, new ObjectType("dstm2.factory.Adapter$Getter"), getFieldName(p), _cp);
+ _cg.addField(field.getField());
+
+ field = new FieldGen(0, new ObjectType("dstm2.factory.Adapter$Setter"), setFieldName(p), _cp);
+ _cg.addField(field.getField());
+ }
+ }
+
+ private void initRegularField(Property p, InstructionList il, MethodGen method) {
+
+ InstructionHandle ih_0 = il.append(new PUSH(_cp, p._class.getName()));
+ il.append(_factory.createStore(Type.OBJECT, 1));
+ il.append(_factory.createLoad(Type.OBJECT, 1));
+ il.append(_factory.createInvoke("java.lang.Class", "forName", new ObjectType("java.lang.Class"), new Type[] { Type.STRING }, Constants.INVOKESTATIC));
+ il.append(_factory.createStore(Type.OBJECT, 2));
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createFieldAccess(className, "adapter", new ObjectType(adapterClass.getName()), Constants.GETFIELD));
+ il.append(new PUSH(_cp, p.getMethod.getName()));
+ il.append(_factory.createLoad(Type.OBJECT, 2));
+ il.append(_factory.createInvoke(adapterClass.getName(), "makeGetter", new ObjectType("dstm2.factory.Adapter$Getter"), new Type[] { Type.STRING, new ObjectType("java.lang.Class") }, Constants.INVOKEVIRTUAL));
+ il.append(_factory.createFieldAccess(className, getFieldName(p), new ObjectType("dstm2.factory.Adapter$Getter"), Constants.PUTFIELD));
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createFieldAccess(className, "adapter", new ObjectType(adapterClass.getName()), Constants.GETFIELD));
+ il.append(new PUSH(_cp, p.setMethod.getName()));
+ il.append(_factory.createLoad(Type.OBJECT, 2));
+ il.append(_factory.createInvoke(adapterClass.getName(), "makeSetter", new ObjectType("dstm2.factory.Adapter$Setter"), new Type[] { Type.STRING, new ObjectType("java.lang.Class") }, Constants.INVOKEVIRTUAL));
+ InstructionHandle ih_33 = il.append(_factory.createFieldAccess(className, setFieldName(p), new ObjectType("dstm2.factory.Adapter$Setter"), Constants.PUTFIELD));
+ InstructionHandle ih_36;
+ BranchInstruction goto_36 = _factory.createBranchInstruction(Constants.GOTO, null);
+ ih_36 = il.append(goto_36);
+ InstructionHandle ih_39 = il.append(_factory.createStore(Type.OBJECT, 1));
+ il.append(_factory.createNew("dstm2.exceptions.PanicException"));
+ il.append(InstructionConstants.DUP);
+ il.append(_factory.createLoad(Type.OBJECT, 1));
+ il.append(_factory.createInvoke("dstm2.exceptions.PanicException", "<init>", Type.VOID, new Type[] { new ObjectType("java.lang.Throwable") }, Constants.INVOKESPECIAL));
+ il.append(InstructionConstants.ATHROW);
+ InstructionHandle ih_49 = il.append(InstructionConstants.NOP);
+ goto_36.setTarget(ih_49);
+ method.addExceptionHandler(ih_0, ih_33, ih_39, new ObjectType("java.lang.ClassNotFoundException"));
+ }
+
+ private void initPrimitiveField(Property p, InstructionList il, MethodGen method) {
+ InstructionHandle ih_0 = il.append(new PUSH(_cp, p._class.getName()));
+ il.append(_factory.createStore(Type.OBJECT, 1));
+ il.append(_factory.createLoad(Type.OBJECT, 1));
+ pushPrimitiveClass(il, p._class);
+ il.append(_factory.createStore(Type.OBJECT, 2));
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createFieldAccess(className, "adapter", new ObjectType(adapterClass.getName()), Constants.GETFIELD));
+ il.append(new PUSH(_cp, p.getMethod.getName()));
+ il.append(_factory.createLoad(Type.OBJECT, 2));
+ il.append(_factory.createInvoke(adapterClass.getName(), "makeGetter", new ObjectType("dstm2.factory.Adapter$Getter"), new Type[] { Type.STRING, new ObjectType("java.lang.Class") }, Constants.INVOKEVIRTUAL));
+ il.append(_factory.createFieldAccess(className, getFieldName(p), new ObjectType("dstm2.factory.Adapter$Getter"), Constants.PUTFIELD));
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createFieldAccess(className, "adapter", new ObjectType(adapterClass.getName()), Constants.GETFIELD));
+ il.append(new PUSH(_cp, p.setMethod.getName()));
+ il.append(_factory.createLoad(Type.OBJECT, 2));
+ il.append(_factory.createInvoke(adapterClass.getName(), "makeSetter", new ObjectType("dstm2.factory.Adapter$Setter"), new Type[] { Type.STRING, new ObjectType("java.lang.Class") }, Constants.INVOKEVIRTUAL));
+ InstructionHandle ih_33 = il.append(_factory.createFieldAccess(className, setFieldName(p), new ObjectType("dstm2.factory.Adapter$Setter"), Constants.PUTFIELD));
+ InstructionHandle ih_36;
+ BranchInstruction goto_36 = _factory.createBranchInstruction(Constants.GOTO, null);
+ ih_36 = il.append(goto_36);
+ InstructionHandle ih_39 = il.append(_factory.createStore(Type.OBJECT, 1));
+ il.append(_factory.createNew("dstm2.exceptions.PanicException"));
+ il.append(InstructionConstants.DUP);
+ il.append(_factory.createLoad(Type.OBJECT, 1));
+ il.append(_factory.createInvoke("dstm2.exceptions.PanicException", "<init>", Type.VOID, new Type[] { new ObjectType("java.lang.Throwable") }, Constants.INVOKESPECIAL));
+ il.append(InstructionConstants.ATHROW);
+ InstructionHandle ih_49 = il.append(InstructionConstants.NOP);
+ goto_36.setTarget(ih_49);
+ method.addExceptionHandler(ih_0, ih_33, ih_39, new ObjectType("java.lang.ClassNotFoundException"));
+ }
+ // Create constructor
+ private void createCtor() {
+ InstructionList il = new InstructionList();
+ MethodGen method = new MethodGen(ACC_PUBLIC, Type.VOID, Type.NO_ARGS, new String[] { }, "<init>", className, il, _cp);
+
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createInvoke("java.lang.Object", "<init>", Type.VOID, Type.NO_ARGS, Constants.INVOKESPECIAL));
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createNew(adapterClass.getName()));
+ il.append(InstructionConstants.DUP);
+ il.append(_factory.createFieldAccess(className, "_class", new ObjectType("java.lang.Class"), Constants.GETSTATIC));
+ il.append(_factory.createInvoke(adapterClass.getName(), "<init>", Type.VOID, new Type[] { new ObjectType("java.lang.Class") }, Constants.INVOKESPECIAL));
+ il.append(_factory.createFieldAccess(className, "adapter", new ObjectType(adapterClass.getName()), Constants.PUTFIELD));
+
+ for (Property p : properties) {
+ if (p._class.isPrimitive()) {
+ initPrimitiveField(p, il, method);
+ } else {
+ initRegularField(p, il, method);
+ }
+ }
+ il.append(_factory.createReturn(Type.VOID));
+ method.setMaxStack();
+ method.setMaxLocals();
+ _cg.addMethod(method.getMethod());
+ il.dispose();
+ }
+
+ private void createGetMethod(Property p) {
+ if (p._class.isPrimitive()) {
+ createPrimitiveGetMethod(p);
+ } else {
+ createRegularGetMethod(p);
+ }
+ }
+ private void createSetMethod(Property p) {
+ if (p._class.isPrimitive()) {
+ createPrimitiveSetMethod(p);
+ } else {
+ createRegularSetMethod(p);
+ }
+ }
+
+ private void createStatic() {
+ InstructionList il = new InstructionList();
+ MethodGen method = new MethodGen(ACC_STATIC, Type.VOID, Type.NO_ARGS, new String[] { }, "<clinit>", className, il, _cp);
+
+ InstructionHandle ih_0 = il.append(new PUSH(_cp, interfaceName));
+ il.append(_factory.createInvoke("java.lang.Class", "forName", new ObjectType("java.lang.Class"), new Type[] { Type.STRING }, Constants.INVOKESTATIC));
+ InstructionHandle ih_5 = il.append(_factory.createFieldAccess(className, "_class", new ObjectType("java.lang.Class"), Constants.PUTSTATIC));
+ InstructionHandle ih_8;
+ BranchInstruction goto_8 = _factory.createBranchInstruction(Constants.GOTO, null);
+ ih_8 = il.append(goto_8);
+ InstructionHandle ih_11 = il.append(_factory.createStore(Type.OBJECT, 0));
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createInvoke("java.lang.ClassNotFoundException", "printStackTrace", Type.VOID, Type.NO_ARGS, Constants.INVOKEVIRTUAL));
+ InstructionHandle ih_16 = il.append(_factory.createReturn(Type.VOID));
+ goto_8.setTarget(ih_16);
+ method.addExceptionHandler(ih_0, ih_5, ih_11, new ObjectType("java.lang.ClassNotFoundException"));
+ method.setMaxStack();
+ method.setMaxLocals();
+ _cg.addMethod(method.getMethod());
+ il.dispose();
+ }
+
+ private void pushPrimitiveClass(InstructionList il, Class _class) {
+ il.append(_factory.createFieldAccess(unboxedClass(_class), "TYPE", new ObjectType("java.lang.Class"), Constants.GETSTATIC));
+ }
+
+ private String unboxedClass(Class _class) {
+ if (_class.equals(Boolean.TYPE)) {
+ return "java.lang.Boolean";
+ } else if (_class.equals(Character.TYPE)) {
+ return "java.lang.Character";
+ } else if (_class.equals(Byte.TYPE)) {
+ return "java.lang.Byte";
+ } else if (_class.equals(Short.TYPE)) {
+ return "java.lang.Short";
+ } else if (_class.equals(Integer.TYPE)) {
+ return "java.lang.Integer";
+ } else if (_class.equals(Long.TYPE)) {
+ return "java.lang.Long";
+ } else if (_class.equals(Float.TYPE)) {
+ return "java.lang.Float";
+ } else if (_class.equals(Double.TYPE)) {
+ return "java.lang.Double";
+ } else {
+ throw new PanicException("Unrecognized primitive type: " + _class);
+ }
+ }
+
+ private void createPrimitiveGetMethod(Property p) {
+ InstructionList il = new InstructionList();
+ MethodGen method = new MethodGen(ACC_PUBLIC, p.type, Type.NO_ARGS, new String[] { }, p.getMethod.getName(), className, il, _cp);
+
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createFieldAccess(className, getFieldName(p), new ObjectType("dstm2.factory.Adapter$Getter"), Constants.GETFIELD));
+ il.append(_factory.createInvoke("dstm2.factory.Adapter$Getter", "call", Type.OBJECT, Type.NO_ARGS, Constants.INVOKEINTERFACE));
+ il.append(_factory.createCheckCast(new ObjectType(unboxedClass(p._class))));
+ il.append(_factory.createInvoke(unboxedClass(p._class), p._class.getName() + "Value", p.type, Type.NO_ARGS, Constants.INVOKEVIRTUAL));
+ il.append(_factory.createReturn(Type.INT));
+ method.setMaxStack();
+ method.setMaxLocals();
+ _cg.addMethod(method.getMethod());
+ il.dispose();
+ }
+
+ private void createPrimitiveSetMethod(Property p) {
+ InstructionList il = new InstructionList();
+ MethodGen method = new MethodGen(ACC_PUBLIC, Type.VOID, new Type[] { p.type }, new String[] { "arg0" }, p.setMethod.getName(), className, il, _cp);
+
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createFieldAccess(className, setFieldName(p), new ObjectType("dstm2.factory.Adapter$Setter"), Constants.GETFIELD));
+ il.append(_factory.createLoad(Type.INT, 1));
+ il.append(_factory.createInvoke(unboxedClass(p._class), "valueOf", new ObjectType(unboxedClass(p._class)), new Type[] { p.type }, Constants.INVOKESTATIC));
+ il.append(_factory.createInvoke("dstm2.factory.Adapter$Setter", "call", Type.VOID, new Type[] { Type.OBJECT }, Constants.INVOKEINTERFACE));
+ il.append(_factory.createReturn(Type.VOID));
+ method.setMaxStack();
+ method.setMaxLocals();
+ _cg.addMethod(method.getMethod());
+ il.dispose();
+ }
+
+ private void createRegularGetMethod(Property p) {
+ InstructionList il = new InstructionList();
+ MethodGen method = new MethodGen(ACC_PUBLIC, p.type, Type.NO_ARGS, new String[] { }, p.getMethod.getName(), className, il, _cp);
+
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createFieldAccess(className, getFieldName(p), new ObjectType("dstm2.factory.Adapter$Getter"), Constants.GETFIELD));
+ il.append(_factory.createInvoke("dstm2.factory.Adapter$Getter", "call", Type.OBJECT, Type.NO_ARGS, Constants.INVOKEINTERFACE));
+ il.append(_factory.createCheckCast(new ObjectType(p._class.getName())));
+ il.append(_factory.createReturn(Type.OBJECT));
+ method.setMaxStack();
+ method.setMaxLocals();
+ _cg.addMethod(method.getMethod());
+ il.dispose();
+
+ }
+ private void createRegularSetMethod(Property p) {
+ InstructionList il = new InstructionList();
+ MethodGen method = new MethodGen(ACC_PUBLIC, Type.VOID, new Type[] { p.type }, new String[] { "arg0" }, p.setMethod.getName(), className, il, _cp);
+
+ il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createFieldAccess(className, setFieldName(p), new ObjectType("dstm2.factory.Adapter$Setter"), Constants.GETFIELD));
+ il.append(_factory.createLoad(Type.OBJECT, 1));
+ il.append(_factory.createInvoke("dstm2.factory.Adapter$Setter", "call", Type.VOID, new Type[] { Type.OBJECT }, Constants.INVOKEINTERFACE));
+ il.append(_factory.createReturn(Type.VOID));
+ method.setMaxStack();
+ method.setMaxLocals();
+ _cg.addMethod(method.getMethod());
+ il.dispose();
+ }
+
+ private void passThrough(Class c, Method m) {
+ InstructionList il = new InstructionList();
+ Type[] argTypes = m.getArgumentTypes();
+ String[] argNames = new String[m.getArgumentTypes().length];
+ int argCount = argTypes.length;
+ for (int i = 0; i < argCount; i++) {
+ argNames[i] = "arg" + i;
+ }
+ MethodGen method = new MethodGen(Constants.ACC_PUBLIC,
+ m.getReturnType(),
+ argTypes, argNames,
+ m.getName(), className, il, _cp);
+
+ InstructionHandle ih_0 = il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createFieldAccess(className, "adapter", new ObjectType("dstm2.factory.Adapter"), Constants.GETFIELD));
+ il.append(_factory.createCheckCast(new ObjectType(c.getName())));
+ il.append(_factory.createStore(Type.OBJECT, argCount + 1));
+
+ il.append(_factory.createLoad(Type.OBJECT, argCount + 1));
+ for (int i = 0; i < argCount; i++) {
+ il.append(_factory.createLoad(argTypes[i], i + 1));
+ }
+ il.append(_factory.createInvoke(c.getName(),
+ m.getName(),
+ m.getReturnType(),
+ m.getArgumentTypes(),
+ Constants.INVOKEINTERFACE));
+ il.append(_factory.createReturn(m.getReturnType()));
+ method.setMaxStack();
+ method.setMaxLocals();
+ _cg.addMethod(method.getMethod());
+ il.dispose();
+ }
+}
--- /dev/null
+/*
+ * BaseFactory.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.factory;
+
+import dstm2.atomic;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.HashMap;
+import java.util.Set;
+import java.util.HashSet;
+import java.io.IOException;
+import java.io.ByteArrayOutputStream;
+
+import dstm2.Transaction;
+import TransactionalIO.exceptions.PanicException;
+
+import org.apache.bcel.classfile.*;
+import org.apache.bcel.generic.*;
+import org.apache.bcel.util.*;
+import org.apache.bcel.Constants;
+import org.apache.bcel.Repository;
+import org.apache.bcel.classfile.Method;
+
+/**
+ * Provides utility methods for factories.
+ * @author Maurice Herlihy
+ */
+public abstract class BaseFactory<T> implements Factory<T> {
+ /**
+ * BCEL is not thread-safe
+ **/
+ protected static Object lock = new Object();
+ /**
+ * BCEL instruction factory.
+ */
+ protected InstructionFactory _factory;
+ /**
+ * Constant pool for created class.
+ */
+ protected ConstantPoolGen _cp;
+ /**
+ * Used to generate the class.
+ */
+ protected ClassGen _cg;
+ /**
+ * The actual class we are building.
+ */
+ protected Class<T> theClass;
+ /**
+ * The name of the class we are building.
+ */
+ protected String className;
+ /**
+ * Interface exported by created class.
+ */
+ protected String interfaceName;
+
+ /**
+ * Set of properties.
+ **/
+ protected Set<Property> properties = new HashSet<Property>();
+ /**
+ * Set of other methods.
+ **/
+ protected Set<Method> methods = new HashSet<Method>();
+
+ /**
+ * set of interfaces satisfied by this class
+ */
+ protected Set<Class> interfaces = new HashSet<Class>();
+
+ /**
+ * This constructor separates methods into properties and miscellaneous
+ * methods. For properties, it deduces type and name of properties, and
+ * stores them in the <CODE>properties</CODE> set. Other methods go into
+ * the <CODE>methods</CODE> field.
+ * @param interfaces additional interfaces satisfied by this class and understood by this factory.
+ * @param _class interface class
+ */
+ public BaseFactory(Class<T> _class) {
+ if (!_class.isInterface()) {
+ throw new PanicException("%s is not an interface", _class);
+ }
+ parseProperties(_class);
+ }
+
+ /**
+ * Once methods and fields have been defined, this method turns the
+ * byte code into a Java class.
+ */
+ protected void seal() {
+ ByteArrayOutputStream out = new ByteArrayOutputStream();
+ try {
+ _cg.getJavaClass().dump(out);
+ } catch (IOException ex) {
+ throw new PanicException(ex);
+ }
+ byte[] bytes = out.toByteArray();
+ ClassLoader<T> classLoader = new ClassLoader<T>(bytes);
+ theClass = classLoader.make();
+ }
+
+ /**
+ * Create a new field.
+ * @param type BCEL type of field.
+ * @param name field name
+ */
+ protected void createField(Type type, String name) {
+ FieldGen field = new FieldGen(0, type, name, _cp);
+ _cg.addField(field.getField());
+ }
+
+ /**
+ * Extracts properties from interface definition. Does rudimentary type
+ * and sanity checking
+ * @param _class class to inspect.
+ */
+ private void parseProperties(Class _class) {
+ // Make sure implied field types are scalar or atomic.
+ // Enough to check return type of getField() methods.
+ for (java.lang.reflect.Method method : _class.getMethods()) {
+ if (method.getName().substring(0,3).equals("get")) {
+ if (!isAtomicOrScalar(method.getReturnType())) {
+ throw new PanicException("Method %s return type %s not scalar or atomic.",
+ method.getName(), method.getReturnType().getName());
+ }
+ }
+ }
+ JavaClass jc = null;
+ try {
+ jc = Repository.lookupClass(_class);
+ } catch (java.lang.ClassNotFoundException ex) {
+ throw new PanicException("Class not found: " + _class);
+ }
+ properties = new HashSet<Property>();
+ methods = new HashSet<Method>();
+ Map<String,Property> fieldMap = new HashMap<String,Property>();
+ for (Method m : jc.getMethods()) {
+ String methodName = m.getName();
+ Class returnClass = null; // need both class & type
+ try {
+ returnClass = _class.getMethod(methodName).getReturnType();
+ } catch (NoSuchMethodException e) {};
+ Type[] parameterTypes = m.getArgumentTypes();
+ // for get and set methods
+ String fieldName = unCapitalize(methodName.substring(3));
+ // for boolean is method
+ String fieldNameBool = unCapitalize(methodName.substring(2));
+ // get method?
+ if (methodName.substring(0,3).equals("get")) {
+ Property record = fieldMap.get(fieldName);
+ if (parameterTypes.length != 0) {
+ throw new PanicException("Class %s: method %s\n has bad signature\n",
+ jc.getClassName(), methodName);
+ }
+ Type returnType = m.getReturnType();
+ // first time?
+ if (record == null) {
+ Property newRecord = new Property(returnClass, returnType, fieldName);
+ properties.add(newRecord);
+ newRecord.getMethod = m;
+ fieldMap.put(fieldName, newRecord);
+ } else { // not first time
+ if (!record.type.equals(returnType)) {
+ throw new PanicException("Class %s: inconsistent definitions for field type %s: %s vs %s\n",
+ jc.getClassName(), fieldName, record.type, returnType);
+ } else if (record.getMethod != null) {
+ throw new PanicException("Class %s: multiple definitions for %s\n",
+ jc.getClassName(), methodName);
+ }
+ record.getMethod = m;
+ }
+ // is method
+ } else if (methodName.substring(0,2).equals("is")) {
+ Property record = fieldMap.get(fieldNameBool);
+ if (parameterTypes.length != 0) {
+ throw new PanicException("Class %s: method %s\n has bad signature\n",
+ jc.getClassName(), methodName);
+ }
+ Type returnType = m.getReturnType();
+ if (!returnType.equals(Type.BOOLEAN)) {
+ throw new PanicException("Class %s: method %s\n must have Boolean argument\n",
+ jc.getClassName(), methodName);
+ }
+ // first time?
+ if (record == null) {
+ Property newRecord = new Property(returnClass, returnType, fieldNameBool);
+ properties.add(newRecord);
+ newRecord.getMethod = m;
+ fieldMap.put(fieldNameBool, newRecord);
+ } else { // not first time
+ if (!record.type.equals(returnType)) {
+ throw new PanicException("Class %s: inconsistent definitions for field type %s: %s vs %s\n",
+ jc.getClassName(), fieldNameBool, record.type, returnType);
+ } else if (record.getMethod != null) {
+ throw new PanicException("Class %s: multiple definitions for %s\n",
+ jc.getClassName(), methodName);
+ }
+ record.getMethod = m;
+ }
+ } else if (methodName.substring(0,3).equals("set")) {
+ Property record = fieldMap.get(fieldName);
+ if (parameterTypes.length != 1) {
+ throw new PanicException("Class %s: method %s has bad signature\n",
+ jc.getClassName(), methodName);
+ }
+ Type argType = parameterTypes[0];
+ // first time?
+ if (record == null) {
+ Property newRecord = new Property(returnClass, argType, fieldName);
+ properties.add(newRecord);
+ newRecord.setMethod = m;
+ fieldMap.put(fieldName, newRecord);
+ } else { // not first time
+ if (!record.type.equals(argType)) {
+ throw new PanicException("Class %s: inconsistent definitions for field arg type %s: %s vs %s\n",
+ jc.getClassName(), fieldName, record.type, argType);
+ } else if (record.setMethod != null) {
+ throw new PanicException("Class %s: multiple definitions for %s\n",
+ jc.getClassName(), methodName);
+ }
+ record.setMethod = m;
+ }
+ } else {
+ throw new PanicException("%s: not a get/set method\n", m.getName());
+ }
+ }
+ for (Entry<String, Property> entry : fieldMap.entrySet()) {
+ if (entry.getValue().getMethod == null) {
+ throw new PanicException("Class %s: method get%s not defined\n",
+ jc.getClassName(), entry.getKey());
+ } else if (entry.getValue().setMethod == null) {
+ throw new PanicException("Class %s: method set%s not defined\n",
+ jc.getClassName(), entry.getKey());
+ }
+ }
+ }
+
+ /**
+ * Did caller declare a <CODE>void release()</CODE> method?
+ * @return whether to provide a release() implementation.
+ */
+ protected boolean releaseDefined() {
+ for (Method m : methods) {
+ if (m.getName().equals("release") &&
+ m.getReturnType() == Type.NULL &&
+ m.getArgumentTypes().length == 0) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Checks whether a field type is scalar or declared atomic.
+ * @param _class class to check
+ * @return whether field is legit type for an atomic object
+ */
+ public boolean isAtomicOrScalar(Class _class) {
+ return _class.isPrimitive() ||
+ _class.isEnum() ||
+ _class.isAnnotationPresent(atomic.class) ||
+ _class.equals(Boolean.class) ||
+ _class.equals(Character.class) ||
+ _class.equals(Byte.class) ||
+ _class.equals(Short.class) ||
+ _class.equals(Integer.class) ||
+ _class.equals(Long.class) ||
+ _class.equals(Float.class) ||
+ _class.equals(Double.class) ||
+ _class.equals(String.class);
+ }
+
+ String unCapitalize(String s) {
+ StringBuffer sb = new StringBuffer(s);
+ sb.setCharAt(0, Character.toLowerCase(sb.charAt(0)));
+ return sb.toString();
+ }
+}
--- /dev/null
+/*
+ * ClassLoader.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.factory;
+/**
+ * Simple classloader used to turn BCEL-generated classes into Java classes.
+ * @author Maurice Herlihy
+ */
+ public class ClassLoader<T> extends java.lang.ClassLoader {
+ /**
+ * Holds actual bytes.
+ */
+ byte[] stream;
+ /**
+ * Create instance of class loader.
+ * @param bytes
+ */
+ public ClassLoader(byte[] bytes) {
+ stream = bytes;
+ }
+ /**
+ * Transform byte code into a Java <CODE>class</CODE>.
+ */
+ public Class<T> make() {
+ return (Class<T>)defineClass(null, stream, 0, stream.length);
+ }
+ }
--- /dev/null
+/*
+ * Copyable.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.factory;
+
+/**
+ * @author Maurice Herlihy
+ * Class provides a copyFrom(...) method.
+ */
+public interface Copyable extends CopyableDef<Copyable>{
+
+}
--- /dev/null
+/*
+ * CopyableDef.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.factory;
+/**
+ * Fool the generics machinery into allowing a copyFrom(T) method.
+ * @author Maurice Herlihy
+ */
+public interface CopyableDef<T> {
+ void copyFrom(T other);
+}
--- /dev/null
+/*
+ * Factory.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.factory;
+import dstm2.Transaction;
+
+/**
+ * Interface for all Factory classes.
+ * @author Maurice Herlihy
+ */
+public interface Factory<T> {
+ /**
+ * Creates a new object via no-arg constructor. Return type may satisfy
+ * other, factory-specific interfaces.
+ * @return new object.
+ */
+ T create();
+
+}
--- /dev/null
+/*
+ * Property.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.factory;
+import TransactionalIO.exceptions.PanicException;
+import dstm2.atomic;
+import java.lang.annotation.Annotation;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map.Entry;
+import java.util.Map;
+import java.util.Set;
+import org.apache.bcel.Repository;
+import org.apache.bcel.classfile.Attribute;
+import org.apache.bcel.classfile.JavaClass;
+import org.apache.bcel.classfile.Method;
+import org.apache.bcel.generic.BasicType;
+import org.apache.bcel.generic.Type;
+
+/**
+ * A property is a private or protected field <CODE>prop</CODE> of type
+ * T with <CODE>T getProp()</CODE> and <CODE>void setProp(T)</CODE> methods.
+ * If T is Boolean, getter can be <CODE>boolean isProp()</CODE>.
+ */
+public class Property {
+ /**
+ * Java class of property
+ */
+ public Class _class;
+ /**
+ * BCEL type of property
+ */
+ public Type type;
+ /**
+ * Method that reads property value.
+ */
+ public Method getMethod;
+ /**
+ * Method that sets property value.
+ */
+ public Method setMethod;
+ /**
+ * Name of field associated with property.
+ */
+ public String name;
+ /**
+ * Create a property
+ * @param _type property type
+ * @param _name property name
+ */
+ Property(Class _class, Type _type, String _name) {
+ this._class = _class;
+ this.type = _type;
+ this.name = _name;
+ }
+
+
+ /**
+ * for debugging
+ * @return property description
+ */
+ public String toString() {
+ return String.format("Property[%s %s]", type, name);
+ }
+
+}
--- /dev/null
+/*
+ * Releasable.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.factory;
+
+/**
+ * The <CODE>void release()</CODE> method forgets that the
+ * transaction ever read or modified this object. Use with care.
+ * @author Maurice Herlihy
+ */
+public interface Releasable {
+ /**
+ * Forget that the calling transaction ever saw this object.
+ */
+ void release();
+}
--- /dev/null
+/*
+ * SequentialFactory.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.factory;
+import TransactionalIO.exceptions.PanicException;
+import dstm2.Transaction;
+import dstm2.factory.BaseFactory;
+import dstm2.factory.ClassLoader;
+import dstm2.factory.Property;
+import java.lang.reflect.Constructor;
+import java.lang.reflect.InvocationTargetException;
+import org.apache.bcel.Constants;
+import org.apache.bcel.classfile.Method;
+import org.apache.bcel.generic.*;
+
+/**
+ * Simple factory that implements properties declared in an interface.
+ * Ignores all non-property methods.
+ * @author Maurice Herlihy
+ */
+public class SequentialFactory<T> extends BaseFactory<T> {
+
+ /**
+ * Creates a new instance of SequentialFactory
+ * @param _class Run-time class of interface being implemented.
+ */
+ public SequentialFactory(Class<T> _class) {
+ super(_class);
+ synchronized(lock) {
+ className = _class.getName() + "$";
+ int constants = Constants.ACC_PUBLIC | Constants.ACC_SUPER;
+ String[] interfaces = new String[] {_class.getName()};
+ _cg = new ClassGen(className, "java.lang.Object", null, constants, interfaces);
+ _cp = _cg.getConstantPool();
+ _factory = new InstructionFactory(_cg, _cp);
+ createCtor();
+ for (Property p : properties) {
+ createField(p.type, p.name);
+ createGetMethod(p);
+ createSetMethod(p);
+ }
+ seal();
+ }
+ }
+
+ /**
+ * Create an object.
+ * @return the object.
+ */
+ public T create() {
+ try {
+ synchronized (lock) {
+ return theClass.newInstance();
+ }
+ } catch (Exception ex) {
+ throw new PanicException(ex);
+ }
+ }
+
+ /**
+ * Create constructor for new class.
+ */
+ private void createCtor() {
+ InstructionList il = new InstructionList();
+ MethodGen method = new MethodGen(Constants.ACC_PUBLIC, Type.VOID, Type.NO_ARGS, new String[] { }, "<init>", className, il, _cp);
+
+ InstructionHandle ih_0 = il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createInvoke("java.lang.Object", "<init>", Type.VOID, Type.NO_ARGS, Constants.INVOKESPECIAL));
+ InstructionHandle ih_4 = il.append(_factory.createReturn(Type.VOID));
+ method.setMaxStack();
+ method.setMaxLocals();
+ _cg.addMethod(method.getMethod());
+ il.dispose();
+ }
+
+ /**
+ * Create getter for property.
+ * @param p Property to implement.
+ */
+ private void createGetMethod(Property p) {
+ InstructionList il = new InstructionList();
+ MethodGen method = new MethodGen(Constants.ACC_PUBLIC, p.type, Type.NO_ARGS, new String[] { }, p.getMethod.getName(), className, il, _cp);
+
+ InstructionHandle ih_0 = il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createFieldAccess(className, p.name, p.type, Constants.GETFIELD));
+ InstructionHandle ih_4 = il.append(_factory.createReturn(p.type));
+ method.setMaxStack();
+ method.setMaxLocals();
+ _cg.addMethod(method.getMethod());
+ il.dispose();
+ }
+
+ /**
+ * create setter for new class
+ * @param p Property to implement
+ */
+ private void createSetMethod(Property p) {
+ InstructionList il = new InstructionList();
+ MethodGen method = new MethodGen(Constants.ACC_PUBLIC, Type.VOID, new Type[] { p.type }, new String[] { "value" }, p.setMethod.getName(), className, il, _cp);
+
+ InstructionHandle ih_0 = il.append(_factory.createLoad(Type.OBJECT, 0));
+ il.append(_factory.createLoad(p.type, 1));
+ il.append(_factory.createFieldAccess(className, p.name, p.type, Constants.PUTFIELD));
+ InstructionHandle ih_5 = il.append(_factory.createReturn(Type.VOID));
+ method.setMaxStack();
+ method.setMaxLocals();
+ _cg.addMethod(method.getMethod());
+ il.dispose();
+ }
+
+}
--- /dev/null
+/*
+ * Snapable.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.factory;
+import TransactionalIO.exceptions.SnapshotException;
+
+/**
+ * Interface for objects that support snapshots. {@link http://www.cs.brown.edu/people/mph/ColeH05/herlihy-snapshot-final.pdf }
+ * @author Maurice Herlihy
+ */
+public interface Snapable<T> {
+ /**
+ * Return version that would have been returned by a read open.
+ * @return current version
+ */
+ T snapshot();
+ /**
+ * Check that version is still current.
+ * @param snap Earlier snapshot.
+ * @throws <code>SnapshotException</code> if snapshot not current.
+ */
+ void validate(T snap) throws SnapshotException;
+ /**
+ * If snapshot is current, convert to write access.
+ * @param snap prior snapshot
+ * @throws <code>SnapshotException</code> if snapshot not current.
+ */
+ void upgrade(T snap) throws SnapshotException;
+}
--- /dev/null
+/*
+ * AggressiveManager.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.manager;
+
+import dstm2.util.Random;
+import dstm2.ContentionManager;
+import dstm2.Transaction;
+
+/**
+ * The Chuck Norris contention manager: always abort other transaction.
+ * @author Maurice Herlihy
+ */
+public class AggressiveManager extends BaseManager {
+
+ public AggressiveManager() {
+ }
+ public void resolveConflict(Transaction me, Transaction other) {
+ other.abort();
+ }
+
+ public long getPriority() {
+ throw new UnsupportedOperationException();
+ }
+
+ public void setPriority(long value) {
+ throw new UnsupportedOperationException();
+ }
+}
--- /dev/null
+/*
+ * BackoffManager.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.manager;
+
+import dstm2.util.Random;
+import dstm2.ContentionManager;
+import dstm2.Transaction;
+import java.util.Collection;
+
+/**
+ * Contention manager employing simple exponential backoff.
+ * @author Maurice Herlihy
+ */
+public class BackoffManager extends BaseManager {
+ static final int MIN_LOG_BACKOFF = 4;
+ static final int MAX_LOG_BACKOFF = 26;
+ static final int MAX_RETRIES = 22;
+
+ Random random;
+
+ int currentAttempt = 0;
+
+ public BackoffManager() {
+ random = new Random();
+ }
+ public void openSucceeded() {
+ super.openSucceeded();
+ currentAttempt = 0;
+ }
+ public void resolveConflict(Transaction me, Transaction other) {
+ if (currentAttempt <= MAX_RETRIES) {
+ if (!other.isActive()) {
+ return;
+ }
+ int logBackoff = currentAttempt - 2 + MIN_LOG_BACKOFF;
+ if (logBackoff > MAX_LOG_BACKOFF) {
+ logBackoff = MAX_LOG_BACKOFF;
+ }
+ int sleep = random.nextInt(1 << logBackoff);
+ try {
+ Thread.sleep(sleep/1000000, sleep % 1000000);
+ } catch (InterruptedException ex) {
+ }
+ currentAttempt++;
+ } else {
+ other.abort();
+ currentAttempt = 0;
+ }
+ }
+ public void resolveConflict(Transaction me, Collection<Transaction> others) {
+ if (currentAttempt <= MAX_RETRIES) {
+ int logBackoff = currentAttempt - 2 + MIN_LOG_BACKOFF;
+ if (logBackoff > MAX_LOG_BACKOFF) {
+ logBackoff = MAX_LOG_BACKOFF;
+ }
+ int sleep = random.nextInt(1 << logBackoff);
+ try {
+ Thread.sleep(sleep/1000000, sleep % 1000000);
+ } catch (InterruptedException ex) {
+ }
+ currentAttempt++;
+ } else {
+ for (Transaction other : others) {
+ if (other.isActive() && other != me) {
+ other.abort();
+ }
+ }
+ currentAttempt = 0;
+ }
+ }
+}
--- /dev/null
+/*
+ * BaseManager.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.manager;
+import dstm2.ContentionManager;
+import dstm2.Transaction;
+import java.util.Collection;
+
+/**
+ *
+ * @author mph
+ */
+public class BaseManager implements ContentionManager {
+ long priority;
+
+ /** Creates a new instance of BaseManager */
+ public BaseManager() {
+ priority = 0;
+ }
+
+ public void resolveConflict(Transaction me, Transaction other) {
+ }
+
+ public void resolveConflict(Transaction me, Collection<Transaction> other) {
+ }
+
+ public long getPriority() {
+ return priority;
+ }
+
+ public void setPriority(long value) {
+ priority = value;
+ }
+
+ public void openSucceeded() {
+ }
+
+ /**
+ * Local-spin sleep method -- more accurate than Thread.sleep()
+ * Difference discovered by V. Marathe.
+ */
+ protected void sleep(int ns) {
+ long startTime = System.nanoTime();
+ long stopTime = 0;
+ do {
+ stopTime = System.nanoTime();
+ } while((stopTime - startTime) < ns);
+ }
+
+ public void committed() {
+ }
+
+
+}
--- /dev/null
+/*
+ * EruptionManager.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.manager;
+
+import dstm2.ContentionManager;
+import dstm2.Transaction;
+
+/**
+ * Resolves conflicts by increasing pressure on the transactions that
+ * a blocked transaction is waiting on, eventually causing them to
+ * erupt through to completion. The way this works is that each time a
+ * block is successfully opened, the transaction gains one point of
+ * "momentum". When a transaction finds itself blocked by another of
+ * higher priority, it adds its momentum (priority) to the other
+ * transaction and then waits for the other transaction to complete.
+ * Like the Karma manager, Eruption will only wait around so long
+ * before clobbering the other transaction and going on anyway; the
+ * maximum wait is proportional to the square of the difference in
+ * priorities between the two transactions. Of course, at contention
+ * time, if the other transaction has a lower priority, we just erupt
+ * past it.
+ *
+ * The reasoning behind this management scheme is that if a particular
+ * transaction is blocking resources critical to many other
+ * transactions, it will gain all of their priority in addition to its
+ * own and thus be much more likely to finish quickly and get out of
+ * the way of all the others.
+ *
+ * Note that while a transaction is blocked, other transactions can
+ * pile up behind it and increase its priority enough to outweigh the
+ * transaction it's blocked behind.
+ *
+ * @author Bill Scherer
+ *
+ **/
+
+public class EruptionManager extends BaseManager {
+ static final int SLEEP_PERIOD = 1000;
+
+ /** Creates a new instance of EruptionManager */
+ public EruptionManager() {
+ priority = 0;
+ }
+
+ public void resolveConflict(Transaction me, Transaction other) {
+ long transferred = 0;
+ ContentionManager otherManager = other.getContentionManager();
+ for (int attempts = 0; ; attempts++) {
+ long otherPriority = otherManager.getPriority();
+ long delta = otherPriority - priority;
+ if (delta < 0 || attempts > delta * delta) {
+ transferred = 0;
+ other.abort();
+ return;
+ }
+ // Unsafe increment, but too expensive to synchronize.
+ if (priority > transferred) {
+ otherManager.setPriority(otherPriority + priority - transferred);
+ transferred = priority;
+ }
+ if (attempts < delta) {
+ sleep(SLEEP_PERIOD);
+ }
+ }
+ }
+
+ public void openSucceeded() {
+ priority++;
+ }
+
+}
--- /dev/null
+/*
+ * GreedyManager.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.manager;
+
+import dstm2.Transaction;
+
+/**
+ * Tries to keep a maximal independent set running.
+ * If prior transaction is
+ * waiting or lower priority, then abort it.
+ * otherwise, wait for it to commit, abort, or wait
+ * Complete description in
+ * Rachid Guerraoui, Maurice Herlihy, and Sebastian Pochon, Toward a Theory of Transactional Contention Management,
+ * Proceedings of the Twenty-Fourth Annual Symposium on Principles of Distributed Computing (PODC).
+ * Las Vegas, NV July 2005.
+ * @author Maurice Herlihy
+ */
+public class GreedyManager extends BaseManager {
+ public void resolveConflict(Transaction me, Transaction other) {
+ if (other.waiting || other.startTime < me.startTime) {
+ other.abort();
+ } else {
+ me.waiting = true; // I'm waiting
+ other.waitWhileActiveNotWaiting();
+ me.waiting = false; // I'm no longer waiting
+ }
+ }
+ /**
+ * Reset priority only on commit. On abort, restart with previous priority.
+ **/
+ public void committed() {
+ setPriority(0);
+ }
+
+ public void openSucceeded() {
+ setPriority(getPriority() + 1);
+ }
+}
--- /dev/null
+/*
+ * KarmaManager.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.manager;
+import dstm2.Transaction;
+import dstm2.ContentionManager;
+
+/**
+ * Uses "karmic debt management" to resolve conflicts. Roughly, a
+ * thread gains "karma" for every object it successfully opens, and
+ * threads with greater karma can abort transactions of other threads.
+ * A thread's karma is reset every time it successfully commits a
+ * transaction, but not when it is aborted (hence the name).
+ *
+ * When conflict occurs between two transactions, the one with the
+ * greater accumulated karma wins. If the other transaction holds a
+ * block, it gets aborted immediately. Otherwise, the "lesser"
+ * transaction backs off for a fixed interval and up to the square of
+ * the difference in karma bethere the two.
+ *
+ * The key idea behind this policy is that it allows long transactions
+ * to eventually finish even if mixed with lots of competing shorter
+ * transactions. This happens because the longer transaction will
+ * accumulate more and more karma each time it gets aborted, so it
+ * will eventually reach "critical mass" and be able to bulldoze its
+ * way through to get its work done.
+ *
+ * @author Bill Scherer
+ **/
+
+public class KarmaManager extends BaseManager {
+ static final int SLEEP_PERIOD = 1000;
+
+ public void resolveConflict(Transaction me, Transaction other) {
+ ContentionManager otherManager = other.getContentionManager();
+ for (int attempts = 0; ; attempts++) {
+ long delta = otherManager.getPriority() - priority;
+ if (attempts > delta) {
+ other.abort();
+ }
+ }
+ }
+
+ /**
+ * Reset priority only on commit. On abort, restart with previous priority.
+ * "Cosmic debt"?. More like cosmic credit.
+ **/
+ public void committed() {
+ setPriority(0);
+ }
+
+ public void openSucceeded() {
+ setPriority(getPriority() + 1);
+ }
+}
--- /dev/null
+/*
+ * KindergartenManager.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.manager;
+
+import dstm2.Transaction;
+import dstm2.ContentionManager;
+import dstm2.util.Random;
+import java.util.TreeSet;
+
+/**
+ * Transactions take turns playing with blocks.
+ *
+ * @author Bill Scherer
+ */
+public class KindergartenManager extends BaseManager {
+ static final int SLEEP_PERIOD = 1000; // was 100
+ static final int MAX_RETRIES = 100; // was 10
+ TreeSet<KindergartenManager> otherChildren;
+ Random random;
+
+ /** Creates new <code>Kindergarten</code> manager */
+ public KindergartenManager() {
+ super();
+ otherChildren = new TreeSet<KindergartenManager>();
+ otherChildren.add(this);
+ random = new Random();
+ }
+
+ public void resolveConflict(Transaction me, Transaction other) {
+ try {
+ KindergartenManager otherManager =
+ (KindergartenManager) other.getContentionManager();
+ // first, check sharing records.
+ if (otherChildren.contains(otherManager)) {
+ otherChildren.remove(otherManager);
+ other.abort(); // My turn! My turn!
+ return;
+ }
+ for (int i = 0; i < MAX_RETRIES; i++) {
+ this.sleep(SLEEP_PERIOD);
+ if (!other.isActive()) {
+ return;
+ }
+ }
+ me.abort(); // give up
+ return;
+ } catch (ClassCastException e) {
+ other.abort(); // Oh, other not a Kindergartener. Kill it.
+ return;
+ }
+ }
+}
--- /dev/null
+/*
+ * PriorityManager.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.manager;
+
+import dstm2.ContentionManager;
+import dstm2.Transaction;
+
+/**
+ * Older transaction always wins.
+ * @author Maurice Herlihy
+ */
+public class PriorityManager extends BaseManager {
+
+ public PriorityManager() {
+ }
+ public void resolveConflict(Transaction me, Transaction other) {
+ if (me.startTime <= other.startTime) {
+ other.abort();
+ } else {
+ other.waitWhileActive();
+ }
+ }
+
+ public long getPriority() {
+ throw new UnsupportedOperationException();
+ }
+
+ public void setPriority(long value) {
+ throw new UnsupportedOperationException();
+ }
+}
--- /dev/null
+/*
+ * Random.java
+ *
+ * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
+ * Clara, California 95054, U.S.A. All rights reserved.
+ *
+ * Sun Microsystems, Inc. has intellectual property rights relating to
+ * technology embodied in the product that is described in this
+ * document. In particular, and without limitation, these
+ * intellectual property rights may include one or more of the
+ * U.S. patents listed at http://www.sun.com/patents and one or more
+ * additional patents or pending patent applications in the U.S. and
+ * in other countries.
+ *
+ * U.S. Government Rights - Commercial software.
+ * Government users are subject to the Sun Microsystems, Inc. standard
+ * license agreement and applicable provisions of the FAR and its
+ * supplements. Use is subject to license terms. Sun, Sun
+ * Microsystems, the Sun logo and Java are trademarks or registered
+ * trademarks of Sun Microsystems, Inc. in the U.S. and other
+ * countries.
+ *
+ * This product is covered and controlled by U.S. Export Control laws
+ * and may be subject to the export or import laws in other countries.
+ * Nuclear, missile, chemical biological weapons or nuclear maritime
+ * end uses or end users, whether direct or indirect, are strictly
+ * prohibited. Export or reexport to countries subject to
+ * U.S. embargo or to entities identified on U.S. export exclusion
+ * lists, including, but not limited to, the denied persons and
+ * specially designated nationals lists is strictly prohibited.
+ */
+
+package dstm2.util;
+
+import java.io.*;
+import java.util.concurrent.atomic.AtomicLong;
+
+/**
+ * Lightweight random number generator. <I>Not thread-safe.</I> Synchronization in the
+ * <CODE>java.util.Randome</CODE> can distort the performance of multithreaded benchmarks.
+ */
+public class Random extends java.util.Random {
+
+ /** use serialVersionUID from JDK 1.1 for interoperability */
+ static final long serialVersionUID = 3905348978240129619L;
+
+ private long seed;
+
+ private final static long multiplier = 0x5DEECE66DL;
+ private final static long addend = 0xBL;
+ private final static long mask = (1L << 48) - 1;
+
+ /**
+ * Creates a new random number generator. This constructor sets
+ * the seed of the random number generator to a value very likely
+ * to be distinct from any other invocation of this constructor.
+ */
+ public Random() { this(++seedUniquifier + System.nanoTime()); }
+ private static volatile long seedUniquifier = 8682522807148012L;
+
+ /**
+ * Creates a new random number generator using a single
+ * <code>long</code> seed:
+ * <blockquote><pre>
+ * public Random(long seed) { setSeed(seed); }</pre></blockquote>
+ * Used by method <tt>next</tt> to hold
+ * the state of the pseudorandom number generator.
+ *
+ * @param seed the initial seed.
+ * @see java.util.Random#setSeed(long)
+ */
+ public Random(long seed) {
+ this.seed = 0L;
+ setSeed(seed);
+ }
+
+ /**
+ * Sets the seed of this random number generator using a single
+ * <code>long</code> seed. The general contract of <tt>setSeed</tt>
+ * is that it alters the state of this random number generator
+ * object so as to be in exactly the same state as if it had just
+ * been created with the argument <tt>seed</tt> as a seed. The method
+ * <tt>setSeed</tt> is implemented by class Random as follows:
+ * <blockquote><pre>
+ * synchronized public void setSeed(long seed) {
+ * this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
+ * haveNextNextGaussian = false;
+ * }</pre></blockquote>
+ * The implementation of <tt>setSeed</tt> by class <tt>Random</tt>
+ * happens to use only 48 bits of the given seed. In general, however,
+ * an overriding method may use all 64 bits of the long argument
+ * as a seed value.
+ *
+ * Note: Although the seed value is an AtomicLong, this method
+ * must still be synchronized to ensure correct semantics
+ * of haveNextNextGaussian.
+ *
+ * @param seed the initial seed.
+ */
+ public void setSeed(long seed) {
+ seed = (seed ^ multiplier) & mask;
+ this.seed = seed;
+ haveNextNextGaussian = false;
+ }
+
+ /**
+ * Generates the next pseudorandom number. Subclass should
+ * override this, as this is used by all other methods.<p>
+ * The general contract of <tt>next</tt> is that it returns an
+ * <tt>int</tt> value and if the argument bits is between <tt>1</tt>
+ * and <tt>32</tt> (inclusive), then that many low-order bits of the
+ * returned value will be (approximately) independently chosen bit
+ * values, each of which is (approximately) equally likely to be
+ * <tt>0</tt> or <tt>1</tt>. The method <tt>next</tt> is implemented
+ * by class <tt>Random</tt> as follows:
+ * <blockquote><pre>
+ * synchronized protected int next(int bits) {
+ * seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
+ * return (int)(seed >>> (48 - bits));
+ * }</pre></blockquote>
+ * This is a linear congruential pseudorandom number generator, as
+ * defined by D. H. Lehmer and described by Donald E. Knuth in <i>The
+ * Art of Computer Programming,</i> Volume 2: <i>Seminumerical
+ * Algorithms</i>, section 3.2.1.
+ *
+ * @param bits random bits
+ * @return the next pseudorandom value from this random number generator's sequence.
+ * @since JDK1.1
+ */
+ protected int next(int bits) {
+ seed = (seed * multiplier + addend) & mask;
+ return (int)(seed >>> (48 - bits));
+ }
+
+ private static final int BITS_PER_BYTE = 8;
+ private static final int BYTES_PER_INT = 4;
+
+ private double nextNextGaussian;
+ private boolean haveNextNextGaussian = false;
+
+ /**
+ * Returns the next pseudorandom, Gaussian ("normally") distributed
+ * <code>double</code> value with mean <code>0.0</code> and standard
+ * deviation <code>1.0</code> from this random number generator's sequence.
+ * <p>
+ * The general contract of <tt>nextGaussian</tt> is that one
+ * <tt>double</tt> value, chosen from (approximately) the usual
+ * normal distribution with mean <tt>0.0</tt> and standard deviation
+ * <tt>1.0</tt>, is pseudorandomly generated and returned. The method
+ * <tt>nextGaussian</tt> is implemented by class <tt>Random</tt> as follows:
+ * <blockquote><pre>
+ * synchronized public double nextGaussian() {
+ * if (haveNextNextGaussian) {
+ * haveNextNextGaussian = false;
+ * return nextNextGaussian;
+ * } else {
+ * double v1, v2, s;
+ * do {
+ * v1 = 2 * nextDouble() - 1; // between -1.0 and 1.0
+ * v2 = 2 * nextDouble() - 1; // between -1.0 and 1.0
+ * s = v1 * v1 + v2 * v2;
+ * } while (s >= 1 || s == 0);
+ * double multiplier = Math.sqrt(-2 * Math.log(s)/s);
+ * nextNextGaussian = v2 * multiplier;
+ * haveNextNextGaussian = true;
+ * return v1 * multiplier;
+ * }
+ * }</pre></blockquote>
+ * This uses the <i>polar method</i> of G. E. P. Box, M. E. Muller, and
+ * G. Marsaglia, as described by Donald E. Knuth in <i>The Art of
+ * Computer Programming</i>, Volume 2: <i>Seminumerical Algorithms</i>,
+ * section 3.4.1, subsection C, algorithm P. Note that it generates two
+ * independent values at the cost of only one call to <tt>Math.log</tt>
+ * and one call to <tt>Math.sqrt</tt>.
+ *
+ * @return the next pseudorandom, Gaussian ("normally") distributed
+ * <code>double</code> value with mean <code>0.0</code> and
+ * standard deviation <code>1.0</code> from this random number
+ * generator's sequence.
+ */
+ public double nextGaussian() {
+ // See Knuth, ACP, Section 3.4.1 Algorithm C.
+ if (haveNextNextGaussian) {
+ haveNextNextGaussian = false;
+ return nextNextGaussian;
+ } else {
+ double v1, v2, s;
+ do {
+ v1 = 2 * nextDouble() - 1; // between -1 and 1
+ v2 = 2 * nextDouble() - 1; // between -1 and 1
+ s = v1 * v1 + v2 * v2;
+ } while (s >= 1 || s == 0);
+ double multiplier = Math.sqrt(-2 * Math.log(s)/s);
+ nextNextGaussian = v2 * multiplier;
+ haveNextNextGaussian = true;
+ return v1 * multiplier;
+ }
+ }
+
+ /**
+ * Serializable fields for Random.
+ *
+ * @serialField seed long;
+ * seed for random computations
+ * @serialField nextNextGaussian double;
+ * next Gaussian to be returned
+ * @serialField haveNextNextGaussian boolean
+ * nextNextGaussian is valid
+ */
+ private static final ObjectStreamField[] serialPersistentFields = {
+ new ObjectStreamField("seed", Long.TYPE),
+ new ObjectStreamField("nextNextGaussian", Double.TYPE),
+ new ObjectStreamField("haveNextNextGaussian", Boolean.TYPE)
+ };
+
+ /**
+ * Reconstitute the <tt>Random</tt> instance from a stream (that is,
+ * deserialize it). The seed is read in as long for
+ * historical reasons, but it is converted to an AtomicLong.
+ */
+ private void readObject(java.io.ObjectInputStream s)
+ throws java.io.IOException, ClassNotFoundException {
+
+ ObjectInputStream.GetField fields = s.readFields();
+ long seedVal;
+
+ seedVal = (long) fields.get("seed", -1L);
+ if (seedVal < 0)
+ throw new java.io.StreamCorruptedException(
+ "Random: invalid seed");
+ seed = seedVal;
+ nextNextGaussian = fields.get("nextNextGaussian", 0.0);
+ haveNextNextGaussian = fields.get("haveNextNextGaussian", false);
+ }
+
+
+ /**
+ * Save the <tt>Random</tt> instance to a stream.
+ * The seed of a Random is serialized as a long for
+ * historical reasons.
+ *
+ */
+ synchronized private void writeObject(ObjectOutputStream s) throws IOException {
+ // set the values of the Serializable fields
+ ObjectOutputStream.PutField fields = s.putFields();
+ fields.put("seed", seed);
+ fields.put("nextNextGaussian", nextNextGaussian);
+ fields.put("haveNextNextGaussian", haveNextNextGaussian);
+
+ // save them
+ s.writeFields();
+
+ }
+
+}
projects / IRC.git / commitdiff