2008-12-02 Marek Habersack <mhabersack@novell.com>

[mono.git] / mcs / class / System.Core / System.Threading / ReaderWriterLockSlim.cs

//
// System.Threading.ReaderWriterLockSlim.cs
//
// Authors:
//   Miguel de Icaza (miguel@novell.com) 
//   Dick Porter (dick@ximian.com)
//   Jackson Harper (jackson@ximian.com)
//   Lluis Sanchez Gual (lluis@ximian.com)
//
// Copyright 2004-2008 Novell, Inc (http://www.novell.com)
// Copyright 2003, Ximian, Inc.
//
// NoRecursion code based on the blog post from Vance Morrison:
//   http://blogs.msdn.com/vancem/archive/2006/03/28/563180.aspx
//
// Recursion code based on Mono's implementation of ReaderWriterLock.
// 
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
// 
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//

using System;
using System.Collections;
using System.Collections.Generic;
using System.Security.Permissions;
using System.Diagnostics;
using System.Threading;

namespace System.Threading {

        //
        // This implementation is based on the light-weight
        // Reader/Writer lock sample from Vance Morrison's blog:
        //
        // http://blogs.msdn.com/vancem/archive/2006/03/28/563180.aspx
        //
        // And in Mono's ReaderWriterLock
        //
        [HostProtectionAttribute(SecurityAction.LinkDemand, MayLeakOnAbort = true)]
        [HostProtectionAttribute(SecurityAction.LinkDemand, Synchronization = true, ExternalThreading = true)]
        public class ReaderWriterLockSlim : IDisposable {
                // Are we on a multiprocessor?
                static bool smp;
                
                // Lock specifiation for myLock:  This lock protects exactly the local fields associted
                // instance of MyReaderWriterLock.  It does NOT protect the memory associted with the
                // the events that hang off this lock (eg writeEvent, readEvent upgradeEvent).
                int myLock;

                // Who owns the lock owners > 0 => readers
                // owners = -1 means there is one writer, Owners must be >= -1.  
                internal int owners;
                Thread upgradable_thread;
                
                // These variables allow use to avoid Setting events (which is expensive) if we don't have to. 
                uint numWriteWaiters;        // maximum number of threads that can be doing a WaitOne on the writeEvent 
                uint numReadWaiters;         // maximum number of threads that can be doing a WaitOne on the readEvent
                uint numUpgradeWaiters;      // maximum number of threads that can be doing a WaitOne on the upgradeEvent (at most 1). 
                
                // conditions we wait on. 
                EventWaitHandle writeEvent;    // threads waiting to aquire a write lock go here.
                EventWaitHandle readEvent;     // threads waiting to aquire a read lock go here (will be released in bulk)
                EventWaitHandle upgradeEvent;  // thread waiting to upgrade a read lock to a write lock go here (at most one)

                int lock_owner;

                // Only set if we are a recursive lock
                Dictionary<int,int> reader_locks;
                
                static ReaderWriterLockSlim ()
                {
                        smp = Environment.ProcessorCount > 1;
                }
                
                public ReaderWriterLockSlim () : this (LockRecursionPolicy.NoRecursion)
                {
                }

                public ReaderWriterLockSlim (LockRecursionPolicy recursionPolicy)
                {
                        if (recursionPolicy != LockRecursionPolicy.NoRecursion){
                                reader_locks = new Dictionary<int,int> ();
                                throw new NotImplementedException ("recursionPolicy != NoRecursion not currently implemented");
                        }
                }

                public void EnterReadLock ()
                {
                        TryEnterReadLock (-1);
                }

                public bool TryEnterReadLock (int millisecondsTimeout)
                {
                        EnterMyLock ();
                        
                        while (true){
                                // Easy case, no contention
                                // owners >= 0 means there might be readers (but no writer)
                                if (owners >= 0 && numWriteWaiters == 0){
                                        owners++;
                                        break;
                                }
                                
                                // If the request is to probe.
                                if (millisecondsTimeout == 0){
                                        ExitMyLock ();
                                        return false;
                                }

                                // We need to wait.  Mark that we have waiters and wait.  
                                if (readEvent == null) {
                                        LazyCreateEvent (ref readEvent, false);
                                        // since we left the lock, start over. 
                                        continue;
                                }

                                if (!WaitOnEvent (readEvent, ref numReadWaiters, millisecondsTimeout))
                                        return false;
                        }
                        ExitMyLock ();
                        
                        return true;
                }

                public bool TryEnterReadLock (TimeSpan timeout)
                {
                        int ms = CheckTimeout (timeout);
                        return TryEnterReadLock (ms);
                }

                //
                // TODO: What to do if we are releasing a ReadLock and we do not own it?
                //
                public void ExitReadLock ()
                {
                        EnterMyLock ();
                        Debug.Assert(owners > 0, "ReleasingReaderLock: releasing lock and no read lock taken");
                        --owners;
                        ExitAndWakeUpAppropriateWaiters ();
                }

                public void EnterWriteLock ()
                {
                        TryEnterWriteLock (-1);
                }
                
                public bool TryEnterWriteLock (int millisecondsTimeout)
                {
                        EnterMyLock ();

                        while (true){
                                // There is no contention, we are done
                                if (owners == 0){
                                        // Indicate that we have a writer
                                        owners = -1;
                                        break;
                                }

                                // If we are the thread that took the Upgradable read lock
                                if (owners == 1 && upgradable_thread == Thread.CurrentThread){
                                        owners = -1;
                                        break;
                                }

                                // If the request is to probe.
                                if (millisecondsTimeout == 0){
                                        ExitMyLock ();
                                        return false;
                                }

                                // We need to wait, figure out what kind of waiting.
                                
                                if (upgradable_thread == Thread.CurrentThread){
                                        // We are the upgradable thread, register our interest.
                                        
                                        if (upgradeEvent == null){
                                                LazyCreateEvent (ref upgradeEvent, false);

                                                // since we left the lock, start over.
                                                continue;
                                        }

                                        if (numUpgradeWaiters > 0){
                                                ExitMyLock ();
                                                throw new ApplicationException ("Upgrading lock to writer lock already in process, deadlock");
                                        }
                                        
                                        if (!WaitOnEvent (upgradeEvent, ref numUpgradeWaiters, millisecondsTimeout))
                                                return false;
                                } else {
                                        if (writeEvent == null){
                                                LazyCreateEvent (ref writeEvent, true);

                                                // since we left the lock, retry
                                                continue;
                                        }
                                        if (!WaitOnEvent (writeEvent, ref numWriteWaiters, millisecondsTimeout))
                                                return false;
                                }
                        }

                        Debug.Assert (owners == -1, "Owners is not -1");
                        ExitMyLock ();
                        return true;
                }

                public bool TryEnterWriteLock (TimeSpan timeout)
                {
                        int ms = CheckTimeout (timeout);
                        return TryEnterWriteLock (ms);
                }

                public void ExitWriteLock ()
                {
                        EnterMyLock ();
                        Debug.Assert (owners == -1, "Calling ReleaseWriterLock when no write lock is held");
                        Debug.Assert (numUpgradeWaiters > 0);
                        upgradable_thread = null;
                        owners = 0;
                        ExitAndWakeUpAppropriateWaiters ();
                }

                public void EnterUpgradableReadLock ()
                {
                        TryEnterUpgradableReadLock (-1);
                }

                //
                // Taking the Upgradable read lock is like taking a read lock
                // but we limit it to a single upgradable at a time.
                //
                public bool TryEnterUpgradableReadLock (int millisecondsTimeout)
                {
                        EnterMyLock ();
                        while (true){
                                if (owners == 0 && numWriteWaiters == 0 && upgradable_thread == null){
                                        owners++;
                                        upgradable_thread = Thread.CurrentThread;
                                        break;
                                }

                                // If the request is to probe
                                if (millisecondsTimeout == 0){
                                        ExitMyLock ();
                                        return false;
                                }

                                if (readEvent == null){
                                        LazyCreateEvent (ref readEvent, false);
                                        // since we left the lock, start over.
                                        continue;
                                }

                                if (!WaitOnEvent (readEvent, ref numReadWaiters, millisecondsTimeout))
                                        return false;
                        }

                        ExitMyLock ();
                        return true;
                }

                public bool TryEnterUpgradableReadLock (TimeSpan timeout)
                {
                        int ms = CheckTimeout (timeout);
                        return TryEnterUpgradableReadLock (ms);
                }
               
                public void ExitUpgradeableReadLock ()
                {
                        EnterMyLock ();
                        Debug.Assert (owners > 0, "Releasing an upgradable lock, but there was no reader!");
                        --owners;
                        upgradable_thread = null;
                        ExitAndWakeUpAppropriateWaiters ();
                }

                public void Dispose ()
                {
                        throw new NotImplementedException ();
                }
                
#region Private methods
                void EnterMyLock ()
                {
                        if (Interlocked.CompareExchange(ref myLock, 1, 0) != 0)
                                EnterMyLockSpin ();
                }

                void EnterMyLockSpin ()
                {

                        for (int i = 0; ;i++) {
                                if (i < 3 && smp)
                                        Thread.SpinWait (20);    // Wait a few dozen instructions to let another processor release lock. 
                                else 
                                        Thread.Sleep (0);        // Give up my quantum.  

                                if (Interlocked.CompareExchange(ref myLock, 1, 0) == 0)
                                        return;
                        }
                }

                void ExitMyLock()
                {
                        Debug.Assert (myLock != 0, "Exiting spin lock that is not held");
                        myLock = 0;
                }

                bool MyLockHeld { get { return myLock != 0; } }

                /// <summary>
                /// Determines the appropriate events to set, leaves the locks, and sets the events. 
                /// </summary>
                private void ExitAndWakeUpAppropriateWaiters()
                {
                        Debug.Assert (MyLockHeld);

                        // First a writing thread waiting on being upgraded
                        if (owners == 1 && numUpgradeWaiters != 0){
                                // Exit before signaling to improve efficiency (wakee will need the lock)
                                ExitMyLock ();
                                // release all upgraders (however there can be at most one). 
                                upgradeEvent.Set ();
                                //
                                // TODO: What does the following comment mean?
                                // two threads upgrading is a guarenteed deadlock, so we throw in that case. 
                        } else if (owners == 0 && numWriteWaiters > 0) {
                                // Exit before signaling to improve efficiency (wakee will need the lock)
                                ExitMyLock ();
                                // release one writer. 
                                writeEvent.Set ();
                        }
                        else if (owners >= 0 && numReadWaiters != 0) {
                                // Exit before signaling to improve efficiency (wakee will need the lock)
                                ExitMyLock ();
                                // release all readers.
                                readEvent.Set();
                        } else
                                ExitMyLock();
                }

                /// <summary>
                /// A routine for lazily creating a event outside the lock (so if errors
                /// happen they are outside the lock and that we don't do much work
                /// while holding a spin lock).  If all goes well, reenter the lock and
                /// set 'waitEvent' 
                /// </summary>
                void LazyCreateEvent(ref EventWaitHandle waitEvent, bool makeAutoResetEvent)
                {
                        Debug.Assert (MyLockHeld);
                        Debug.Assert (waitEvent == null);
                        
                        ExitMyLock ();
                        EventWaitHandle newEvent;
                        if (makeAutoResetEvent) 
                                newEvent = new AutoResetEvent (false);
                        else 
                                newEvent = new ManualResetEvent (false);

                        EnterMyLock ();

                        // maybe someone snuck in. 
                        if (waitEvent == null)
                                waitEvent = newEvent;
                }

                /// <summary>
                /// Waits on 'waitEvent' with a timeout of 'millisceondsTimeout.  
                /// Before the wait 'numWaiters' is incremented and is restored before leaving this routine.
                /// </summary>
                bool WaitOnEvent (EventWaitHandle waitEvent, ref uint numWaiters, int millisecondsTimeout)
                {
                        Debug.Assert (MyLockHeld);

                        waitEvent.Reset ();
                        numWaiters++;

                        bool waitSuccessful = false;

                        // Do the wait outside of any lock 
                        ExitMyLock();      
                        try {
                                waitSuccessful = waitEvent.WaitOne (millisecondsTimeout, false);
                        } finally {
                                EnterMyLock ();
                                --numWaiters;
                                if (!waitSuccessful)
                                        ExitMyLock ();
                        }
                        return waitSuccessful;
                }
                
                int CheckTimeout (TimeSpan timeout)
                {
                        int ms = (int) timeout.TotalMilliseconds;

                        if (ms < -1)
                                throw new ArgumentOutOfRangeException ("timeout",
                                                "Number must be either non-negative or -1");
                        return ms;
                }
#endregion
        }
}