port of STM

4 files changed, 309 insertions, 0 deletions

diff --git a/src/cli/runtime/TRef.cs b/src/cli/runtime/TRef.cs
new file mode 100644
index 00000000..e8edcc85
--- /dev/null
+++ b/src/cli/runtime/TRef.cs
@@ -0,0 +1,32 @@
+/**

+ *   Copyright (c) Rich Hickey. All rights reserved.

+ *   The use and distribution terms for this software are covered by the

+ *   Common Public License 1.0 (http://opensource.org/licenses/cpl.php)

+ *   which can be found in the file CPL.TXT at the root of this distribution.

+ *   By using this software in any fashion, you are agreeing to be bound by

+ * 	 the terms of this license.

+ *   You must not remove this notice, or any other, from this software.

+ **/

+

+/* rich May 30, 2006 */

+

+using System;

+using System.Threading;

+

+namespace org.clojure.runtime

+{

+

+public class TRef : TVal, IComparable{

+static int nextSeq = 0;

+

+readonly int lockSeq;

+

+public TRef() {

+	this.lockSeq = Interlocked.Increment(ref nextSeq);

+}

+

+public int CompareTo(Object o){

+	return lockSeq - ((TRef) o).lockSeq;

+}

+}

+}

diff --git a/src/cli/runtime/TVal.cs b/src/cli/runtime/TVal.cs
new file mode 100644
index 00000000..05b502e9
--- /dev/null
+++ b/src/cli/runtime/TVal.cs
@@ -0,0 +1,30 @@
+/**

+ *   Copyright (c) Rich Hickey. All rights reserved.

+ *   The use and distribution terms for this software are covered by the

+ *   Common Public License 1.0 (http://opensource.org/licenses/cpl.php)

+ *   which can be found in the file CPL.TXT at the root of this distribution.

+ *   By using this software in any fashion, you are agreeing to be bound by

+ * 	 the terms of this license.

+ *   You must not remove this notice, or any other, from this software.

+ **/

+

+/* rich May 30, 2006 */

+

+using System;

+

+namespace org.clojure.runtime

+{

+public class TVal{

+internal volatile Object val;

+internal volatile Transaction.Info tinfo;

+internal volatile TVal prior;

+

+internal void push(Object val,Transaction.Info tinfo) {

+	if(tinfo != null) //not newly created

+		this.prior = (TVal) this.MemberwiseClone();

+	this.tinfo = tinfo;

+	this.val = val;

+}

+

+}

+}

diff --git a/src/cli/runtime/ThreadLocalData.cs b/src/cli/runtime/ThreadLocalData.cs
index bb3f8896..3b57c632 100644
--- a/src/cli/runtime/ThreadLocalData.cs
+++ b/src/cli/runtime/ThreadLocalData.cs
@@ -23,6 +23,14 @@ public Object[] mvArray = new Object[MULTIPLE_VALUES_LIMIT];
 
 internal HybridDictionary dynamicBindings = new HybridDictionary();
 
+internal Transaction transaction;

+

+public Transaction getTransaction() {

+	if(transaction == null)

+		throw new Exception("No active transaction");

+	return transaction;

+}
+
 public ThreadLocalData(HybridDictionary dynamicBindings)
 	{
 	this.mvCount = 0;
diff --git a/src/cli/runtime/Transaction.cs b/src/cli/runtime/Transaction.cs
new file mode 100644
index 00000000..5a66bc38
--- /dev/null
+++ b/src/cli/runtime/Transaction.cs
@@ -0,0 +1,239 @@
+/**

+ *   Copyright (c) Rich Hickey. All rights reserved.

+ *   The use and distribution terms for this software are covered by the

+ *   Common Public License 1.0 (http://opensource.org/licenses/cpl.php)

+ *   which can be found in the file CPL.TXT at the root of this distribution.

+ *   By using this software in any fashion, you are agreeing to be bound by

+ * 	 the terms of this license.

+ *   You must not remove this notice, or any other, from this software.

+ **/

+

+/* rich May 30, 2006 */

+

+using System;

+using System.Threading;

+using System.Collections.Generic;

+

+namespace org.clojure.runtime

+{

+public class Transaction{

+

+public const int COMMITTED = 0;

+public const int WORKING = 1;

+static readonly Object lockObj = new Object();

+

+volatile static int nextSeq = 1;

+

+static int getNextSeq(){

+lock (lockObj)

+{

+		return nextSeq++;

+	}

+}

+

+public class Info{

+internal int seq;

+internal int status;

+

+

+internal Info(int seq,int status){

+	this.seq = seq;

+	this.status = status;

+}

+}

+

+

+Info info;

+int startSeq;

+

+Dictionary<TRef,Object> sets;

+Dictionary<TRef,Cons> commutates;

+

+

+static public Object runInTransaction(ThreadLocalData tld,IFn fn) {

+	if(tld.transaction != null)

+		return fn.invoke(tld);

+	tld.transaction = new Transaction();

+	try{

+		return tld.transaction.run(tld, fn);

+		}

+	finally{

+		tld.transaction = null;

+		}

+}

+

+static public TRef tref(ThreadLocalData tld, Object val) {

+	Transaction trans = tld.getTransaction();

+	TRef tref = new TRef();

+	trans.set(tref, val);

+	return tref;

+}

+

+static public Object get(ThreadLocalData tld, TRef tref) {

+	 return tld.getTransaction().get(tref);

+}

+

+static public Object set(ThreadLocalData tld, TRef tref, Object val) {

+	 return tld.getTransaction().set(tref,val);

+}

+

+static public void touch(ThreadLocalData tld, TRef tref) {

+	tld.getTransaction().touch(tref);

+}

+

+static public void commutate(ThreadLocalData tld, TRef tref, IFn fn) {

+	tld.getTransaction().commutate(tref, fn);

+}

+

+

+Object run(ThreadLocalData tld, IFn fn) {

+	bool done = false;

+	Object ret = null;

+	List<TRef> locks = null;

+	List<TRef> locked = null;

+

+	while(!done){

+		try

+			{

+			ret = fn.invoke(tld);

+			if(locks == null && (sets != null || commutates != null))

+				locks = new List<TRef>();

+			if(sets != null)

+				locks.AddRange(sets.Keys);

+			if(commutates != null)

+				locks.AddRange(commutates.Keys);

+			if(locks != null)

+				{

+				if(locked == null)

+					locked = new List<TRef>(locks.Count);

+				//lock in order, to avoid deadlocks

+				locks.Sort();

+				foreach(TRef tref in locks)

+					{

+					//will block here

+					Monitor.Enter(tref);

+					locked.Add(tref);

+					if(sets.ContainsKey(tref))

+						{

+						//try again if the thing we are trying to set has changed since we started

+						TVal curr = getCurrent(tref);

+						if(curr != null && curr.tinfo.seq > startSeq)

+							goto loop;

+						}

+					}

+				}

+

+			//at this point all write targets are locked

+			//turn commutates into sets

+			foreach(KeyValuePair<TRef, Cons> e in commutates)

+				{

+				TRef tref = e.Key;

+				//note this will npe if tref has never been set, as designed

+				Object val = getCurrent(tref).val;

+				for(Cons c = e.Value;c!=null;c = c.rest)

+					{

+					IFn f = (IFn) c.first;

+					val = f.invoke(tld, val);

+					}

+				sets[tref] =  val;

+				}

+

+			//set the new vals

+			foreach(KeyValuePair<TRef, Object> entry in sets)

+				{

+				TRef tref = entry.Key;

+				tref.push(entry.Value, info);

+				}

+

+			//atomic commit

+			lock(lockObj){

+				info.seq = getNextSeq();

+				info.status = COMMITTED;

+			}

+

+			done = true;

+			loop:

+			    ;

+			}

+		finally{

+			if(locked != null)

+				{

+				foreach(TRef tref in locked)

+					{

+					Monitor.Exit(tref);

+					}

+				locked.Clear();

+				}

+			reset();

+			if(locks != null)

+				locks.Clear();

+			}

+		}

+	return ret;

+}

+

+private void reset(){

+	if(sets != null)

+		sets.Clear();

+	if(commutates != null)

+		commutates.Clear();

+

+}

+

+

+Transaction(){

+	lock(lockObj){

+		int seq = getNextSeq();

+		this.info = new Info(seq, WORKING);

+		this.startSeq = seq;

+	}

+}

+

+Object get(TRef tref) {

+	if(sets != null && sets.ContainsKey(tref))

+		return sets[tref];

+

+    for(TVal ver = tref;ver != null;ver = ver.prior)

+	    {

+	    //note this will npe if tref has never been set, as designed

+	    if(ver.tinfo.status == COMMITTED && ver.tinfo.seq <= startSeq)

+		    return ver.val;

+	    }

+

+	throw new Exception("Version not found");

+}

+

+static TVal getCurrent(TRef tref) {

+    for(TVal ver = tref;ver != null;ver = ver.prior)

+	    {

+	    if(ver.tinfo != null && ver.tinfo.status == COMMITTED)

+		    return ver;

+	    }

+	//this return only if no value was ever successfully set

+	return null;

+}

+

+Object set(TRef tref, Object val) {

+	if(sets == null)

+		sets = new Dictionary<TRef,Object>();

+	if(commutates != null && commutates.ContainsKey(tref))

+		throw new Exception("Can't commutate and set a TRef in the same transaction");

+

+	sets[tref] =val;

+	return val;

+	}

+

+void touch(TRef tref) {

+	set(tref, get(tref));

+	}

+

+void commutate(TRef tref, IFn fn) {

+	if(commutates == null)

+		commutates = new Dictionary<TRef,Cons>();

+	if(sets != null && sets.ContainsKey(tref))

+		throw new Exception("Can't commutate and set a TRef in the same transaction");

+	commutates[tref] = RT.cons(fn, commutates[tref]);

+	}

+

+}

+}