MacHack 1998/MacHack 1998.toast/Papers/C++ Exceptions/µShell/Threads Support/Semaphores.cp

Text File | 1998-05-25 | 22.2 KB | 689 lines | [TEXT/CWIE]

#include "Semaphores.h"
#include "TimeUtils.h"
#include <AppleEvents.h>
#include <AERegistry.h>
#include <Errors.h>

//========================================================================================
// CLASS TThreadIDQueue
//========================================================================================

const short  kThreadQueueAllocSize = 4;

//----------------------------------------------------------------------------------------
// TThreadIDQueue::~TThreadIDQueue
//----------------------------------------------------------------------------------------
TThreadIDQueue::~TThreadIDQueue()
{
    if(fThreadQueue != nil)
    {
        DisposeHandle((Handle)fThreadQueue);
        fThreadQueue = nil;
    }
} // TThreadIDQueue::~TThreadIDQueue

//----------------------------------------------------------------------------------------
// TThreadIDQueue::Enqueue
//----------------------------------------------------------------------------------------
OSErr TThreadIDQueue::Enqueue(ThreadID threadToAdd)
{
    OSErr err = this->InsureThreadQueueHasFreeSpace();
    if(err == noErr)
    {
        (*fThreadQueue)[fThreadCount] = threadToAdd;
        ++fThreadCount;
    }
    return err;
} // TThreadIDQueue::Enqueue

//----------------------------------------------------------------------------------------
// TThreadIDQueue::Dequeue
//----------------------------------------------------------------------------------------
ThreadID TThreadIDQueue::Dequeue()
{
    ThreadID resultThreadID = kNoThreadID;

    if(fThreadCount > 0)
    {
        resultThreadID = (*fThreadQueue)[0];
        --fThreadCount;
        for(long i=0;i<fThreadCount;++i)
            (*fThreadQueue)[i] = (*fThreadQueue)[i + 1];
        (*fThreadQueue)[fThreadCount] = kNoThreadID;
    }

    return resultThreadID;
} // TThreadIDQueue::Dequeue

//----------------------------------------------------------------------------------------
// TThreadIDQueue::InsureThreadQueueHasFreeSpace
//----------------------------------------------------------------------------------------
OSErr TThreadIDQueue::InsureThreadQueueHasFreeSpace()
{
    OSErr err = noErr;

    if(fThreadQueue == nil)
    {
        if((fThreadCount > 0) || (fReservedSpace > 0))
            err = errAEEventFailed;
        else
        {
            fThreadQueue = (ThreadID**) NewHandle( sizeof(ThreadID) * kThreadQueueAllocSize );
            err = MemError();
            if(err == noErr)
                fReservedSpace = kThreadQueueAllocSize;
        }
    }
    else if(fThreadCount >= fReservedSpace)
    {
        if(fThreadCount > fReservedSpace)
            err = errAEEventFailed;
        else
        {
            SetHandleSize((Handle)fThreadQueue, sizeof(ThreadID) * (kThreadQueueAllocSize + fReservedSpace));
            err = MemError();
            if(err == noErr)
                fReservedSpace += kThreadQueueAllocSize;
        }
    }

    return err;
} // TThreadIDQueue::InsureThreadQueueHasFreeSpace

//========================================================================================
// CLASS TSemaphore
//========================================================================================

TSemaphore*        TSemaphore::fgFirstSemaphore            = nil;

long            TSemaphore::fgSemaphoreIDSequence        = kAnySemaphoreID + 1;
long            TSemaphore::fgSemaphoreDefaultTimeout    = kNeverTimeoutSemaphore;
long            TSemaphore::fgSemaphoreDefaultMaxWait    = kNeverTimeoutSemaphore;

unsigned long    TSemaphore::fgLastTimeoutTest            = 0;
unsigned long    TSemaphore::fgLastIdleTick                = 0;
unsigned long    TSemaphore::fgNextTimeoutTest            = 1;

//----------------------------------------------------------------------------------------
// TSemaphore::TSemaphore
//
// Add the semaphore to a global list so we can look up semaphores later by ID.
//----------------------------------------------------------------------------------------
TSemaphore::TSemaphore(long resourceCount /* = 1 */, long semaphoreID /* = kAnySemaphoreID*/)
{
    if (semaphoreID == kAnySemaphoreID)
        semaphoreID = TSemaphore::NewUniqueSemaphoreID();

    fResourceCount = resourceCount;
    fSemaphoreID = semaphoreID;

    //
    // We have one reference (the person who created the semaphore)
    // but no owner yet
    //
    fReferenceCount = 1;
    fOwnerThread = kNoThreadID;
    fOwnerCount = 0;
    fDisposed = false;
    fFailOnWakeup = noErr;

    fSemaphoreTimeoutValue = fgSemaphoreDefaultTimeout;
    fSemaphoreMaxWaitTime = fgSemaphoreDefaultMaxWait;
    fBlockStartTick = TickCount();
    this->ResetTimeoutTimer();

    fNextSemaphore = fgFirstSemaphore;
    fPreviousSemaphore = nil;
    if(fNextSemaphore != nil)
        fNextSemaphore->fPreviousSemaphore = this;
    fgFirstSemaphore = this;
}

//----------------------------------------------------------------------------------------
// TSemaphore::~TSemaphore:
//
// First, remove ourselves from the global linked list of all semaphores.  Then,
// wake up all threads that are still blocked on us before we go away so they won’t
// be stranded, asleep forever.
//----------------------------------------------------------------------------------------
TSemaphore::~TSemaphore()
{
    this->RemoveFromGlobalSemaphoreList();
}

//----------------------------------------------------------------------------------------
// TSemaphore::InitializeGlobals
//----------------------------------------------------------------------------------------
void TSemaphore::InitializeGlobals()
{
    fgFirstSemaphore            = nil;

    fgSemaphoreIDSequence        = kAnySemaphoreID + 1;
    fgSemaphoreDefaultTimeout    = kNeverTimeoutSemaphore;
    fgSemaphoreDefaultMaxWait    = kNeverTimeoutSemaphore;

    fgLastTimeoutTest            = 0;
    fgLastIdleTick                = 0;
    fgNextTimeoutTest            = 1;
}

//----------------------------------------------------------------------------------------
// TSemaphore::RemoveFromGlobalSemaphoreList
//----------------------------------------------------------------------------------------
void TSemaphore::RemoveFromGlobalSemaphoreList()
{
    if((fPreviousSemaphore != nil) || (fNextSemaphore != nil) || (fgFirstSemaphore == this))
    {
        //
        // Either gFirstSemaphore == this or fPreviousSemaphore != nil
        //
        if (fgFirstSemaphore == this)
            fgFirstSemaphore = fNextSemaphore;
        else if (fPreviousSemaphore != nil)
            fPreviousSemaphore->fNextSemaphore = fNextSemaphore;
        else
            DebugStr("\pRemoveFromGlobalSemaphoreList semaphore list corrupt");

        if (fNextSemaphore != nil)
            fNextSemaphore->fPreviousSemaphore = fPreviousSemaphore;

        fPreviousSemaphore = nil;
        fNextSemaphore = nil;
    }
}

//----------------------------------------------------------------------------------------
// TSemaphore::ReleaseReference
//
// Delete this semaphore iff there are no references to it.
// Usually, clients should call either 'Dispose' (the owner of the semaphore should
// dispose it) or 'Release' (any thread that grabs a semaphore should release it).
//----------------------------------------------------------------------------------------
void TSemaphore::ReleaseReference()
{
    --fReferenceCount;
    //
    // By the time our reference count goes to zero, fDisposed should
    // be true and we should no longer be in the global semaphore list.
    //
//    if(fReferenceCount == 0)
//        delete this;
} // TSemaphore::ReleaseReference

//----------------------------------------------------------------------------------------
// TSemaphore::Dispose
//
// Delete this semaphore iff there are no threads blocked on it.  If there are
// blocked threads, then wait until the threads all wake up before disposing this
// semaphore.
//----------------------------------------------------------------------------------------
void TSemaphore::Dispose()
{
    this->ReleaseAllThreads();
    this->RemoveFromGlobalSemaphoreList();
    fDisposed = true;
    this->ReleaseReference();
}

//----------------------------------------------------------------------------------------
// TSemaphore::NewUniqueSemaphoreID:
// A static method to generate a unique ID for a semaphore.  Unique IDs are generated
// simply by starting at zero and counting up.
//----------------------------------------------------------------------------------------
long TSemaphore::NewUniqueSemaphoreID()
{
    ++fgSemaphoreIDSequence;
    return fgSemaphoreIDSequence;
}


//----------------------------------------------------------------------------------------
// TSemaphore::FindSemaphore:
//----------------------------------------------------------------------------------------
TSemaphore*    TSemaphore::FindSemaphore(long semaphoreID, Boolean createIfNotFound /* = false */, long resourceCount /* = 1 */)
{
    TSemaphore* resultSemaphore = fgFirstSemaphore;

    if(fgFirstSemaphore != nil)
        if(fgFirstSemaphore->fPreviousSemaphore != nil)
            DebugStr("\pFirst semaphore in list corrupt!");

    while ((resultSemaphore != nil) && (resultSemaphore->fSemaphoreID != semaphoreID))
    {
        if(resultSemaphore->fNextSemaphore != nil)
            if(resultSemaphore->fNextSemaphore->fPreviousSemaphore != resultSemaphore)
                DebugStr("\pSemaphore linked list corrupt!");

        resultSemaphore = resultSemaphore->fNextSemaphore;
    }

    if((resultSemaphore == nil) && (createIfNotFound == true))
        resultSemaphore = new TSemaphore(resourceCount, semaphoreID);

    return resultSemaphore;
}


//----------------------------------------------------------------------------------------
// TSemaphore::Idle
//
// Call Periodicly to test for blocked semaphores whose time has expired
//----------------------------------------------------------------------------------------
void TSemaphore::Idle()
{
    unsigned long currentTime = TickCount();
    long semaphoreCount = 0;
    long gracePeriod = currentTime - fgLastIdleTick;

    //
    // If we have been away for a long time, then allow clients
    // a grace period; the idea being, that the user or some
    // selfish process probably locked up the machine for a long
    // time, so it's likely that no one (client or server) got
    // any work done.  Even if the server is on some other machine,
    // we still want to add in the grace period; it would be really
    // bad to time out after a long lock-out if the reply was sitting
    // in the AppleEvent manager's queue, waiting for some time to
    // be processed.
    //
    // If we weren't gone for at least half a second, though, then we'll
    // assume that the machine is running just fine.
    //
    if((gracePeriod < 30) || (fgLastIdleTick == 0))
        gracePeriod = 0;
    fgLastIdleTick = currentTime;

    //
    // Don't walk the semaphore list until it's time
    //
    if(TimeExpired(currentTime, fgLastTimeoutTest, fgNextTimeoutTest))
    {
        // DebugStr("\pTSemaphore::Idle decided to do work");

        //
        // Reset gLastTimeoutTest to currentTime to record that this
        // is the time that we did the last test.  Reset gNextTimeoutTest
        // to be one tick before that, the longest time we could
        // possably wait before doing another test (forever!).  In the
        // "forever" case, gNextTimeoutTest will be reset when new
        // semaphores are created.
        //
        fgLastTimeoutTest = currentTime;
        fgNextTimeoutTest = currentTime - 1;

        TSemaphore* semaphore = fgFirstSemaphore;

        while(semaphore != nil)
        {
            ++semaphoreCount;
            TSemaphore* nextSemaphore = semaphore->fNextSemaphore;

            //
            // If we've been away for a while, then allow the
            // semaphore to adjust itself.
            //
            if(gracePeriod)
                semaphore->AddGracePeriod(gracePeriod);

            if(semaphore->CheckIfTimerExpired(currentTime) == false)
            {
                // DebugStr("\pFound a semaphore that has not timed out");

                //
                // For next time through the loop:  test to see
                // if the timeout tick for this semaphore is going
                // to happen sooner than any other timeout value
                // we've calculated yet.  Doing this test now will
                // let us avoid walking the list of semaphores until
                // it's time for one of them to expire.  We don't
                // care if the next-in-line semaphore goes away
                // before we test again; this is just a best-case
                // estimate.
                //
                fgNextTimeoutTest = CloserTick(currentTime, fgNextTimeoutTest, semaphore->TimeoutTick());
            }
            else
            {
                //
                // If the semaphore's time has come, cancel the threads
                // that are blocked on it.
                //
                semaphore->SemaphoreTimedOut();
            }

            semaphore = nextSemaphore;
        }
    }
}

//----------------------------------------------------------------------------------------
// TSemaphore::ThreadDied
//
// If a thread is killed from some other thread, and the killed thread might
// be the owner of some semaphore, then the killer must call this routine so
// that the semaphore can be released.
//----------------------------------------------------------------------------------------
void TSemaphore::ThreadDied(ThreadID threadID)
{
    TSemaphore* semaphore = fgFirstSemaphore;
    while(semaphore != nil)
    {
        TSemaphore* nextSemaphore = semaphore->fNextSemaphore;

        //
        // Release this semaphore iff it was owned by the thread that died
        //
        semaphore->Release(threadID);
        semaphore = nextSemaphore;
    }
}

//----------------------------------------------------------------------------------------
// TSemaphore::Grab:
//
// If the specified thread does not already have ownership of this semaphore, enqueue it.
// If other threads are already waiting, put the thread to sleep (to be woken up when it
// gets to the head of the queue).  By default, the thread grabbing the semaphore is the
// current thread.
//----------------------------------------------------------------------------------------
OSErr TSemaphore::Grab(ThreadID grabbingThread /* = kCurrentThreadID */)
{
    OSErr err = noErr;

    //
    // Every call to 'Grab' should be balanced by a call to 'release'
    //
    ++fReferenceCount;

    //
    // This semaphore isn't good for much once it's been disposed.
    // Similarly, if a semaphore has timed out and is causing all
    // of its blocked threads to wake up (fFailOnWakeup != noErr),
    // then we shouldn't let new threads in either.
    //
    if(fFailOnWakeup != noErr)
        err = fFailOnWakeup;
    else if(fDisposed)
        err = errAEEventFailed;
    else
    {
        //
        // By default the current thread grabs the semaphore
        //
        if (grabbingThread == kCurrentThreadID)
            GetCurrentThread(&grabbingThread);

        //
        // Short-circuit if we already own the semaphore
        // (Note:  if the semaphore sontrolled multiple
        // resources, then it may be possible for one thread
        // to grab the same resource more than once.)
        //
        if (grabbingThread == fOwnerThread)
            return noErr;

        //
        // If the semaphore is available, then we'll let this thread
        // grab it.
        //
        if (fOwnerCount < fResourceCount)
        {
            //
            // There shouldn’t be an owner if we’re about to grab it;
            // set the owner, and mark the semaphore as being unavailable
            //
            // Assert(fOwnerThread == kNoThreadID);
            fOwnerThread = grabbingThread;
            ++fOwnerCount;
        }
        //
        // If the semaphore isn't available, then block the grabbing thread
        //
        else
        {
            //
            // Enqueue the thread, increment the count of threads blocked
            // on this semaphore (often different than the count of threads
            // queued, since at wake-up time threads will be dequeued and
            // woken up, but won't fall out of 'SetThreadState' until the
            // next time they're scheduled)
            //
            err = fBlockedThreads.Enqueue(grabbingThread);
            if(err == noErr)
                err = SetThreadState(grabbingThread, kStoppedThreadState, kNoThreadID);

            //
            // If someone has set our automatic-failure signal, then
            // make note of it; this error should take precedence over
            // any returned by 'SetThreadState'.
            //
            if(fFailOnWakeup != noErr)
            {
                err = fFailOnWakeup;
            }
        }
    }

    return err;
}

//----------------------------------------------------------------------------------------
// TSemaphore::Release:
//
// Remove the reference that this thread has to this semaphore
//----------------------------------------------------------------------------------------
void TSemaphore::Release(ThreadID threadID /* = kCurrentThreadID */)
{
    //
    // If no thread is specified, then assume that the current thread
    // is being released.
    //
    if (threadID == kCurrentThreadID)
        GetCurrentThread(&threadID);

    //
    // If we own this semaphore, then let someone else have it
    //
    // ••• We should require that the thread being released is
    // either the owner or in the list of blocked threads.  If
    // it is in the list of blocked threads, then we should wake
    // it up if possible.
    //
    if(fOwnerThread == threadID)
    {
        fOwnerThread = this->ReleaseOneThread();
    }

    //
    // Decrement our reference count
    //
    this->ReleaseReference();
}

//----------------------------------------------------------------------------------------
// TSemaphore::ReleaseOneThread:
//
// If the thread queue is non-empty, wake up the thread that is now at the head of the
// queue.  If the queue is empty, do nothing.
//----------------------------------------------------------------------------------------
ThreadID TSemaphore::ReleaseOneThread()
{
    ThreadID releasedThread = kNoThreadID;

    //
    // Probably not necessary, but let's make sure that this
    // semaphore is never deleted while we're working with it.
    //
    ++fReferenceCount;

    //
    // Keep working until we find a thread to wake up,
    // or we run out of threads that are blocked on us
    //
    while(fBlockedThreads.QueuedThreads() > 0)
    {
        //
        // Take the first thread waiting in line and wake it up
        //
        releasedThread = fBlockedThreads.Dequeue();

        //
        // If we have a thread, try to wake it up.  Stop working
        // if we can; if we can't wake it up (maybe someone killed
        // it already), then try to pop off the next thread in the list.
        //
        if (releasedThread != kNoThreadID)
        {
            //
            // If the thread can't be woken up, then it will never
            // fall out from TSemaphore::Grab; in that case, decrement
            // the count of blocked threads.
            //
            if(SetThreadState(releasedThread, kReadyThreadState, kNoThreadID) == noErr)
                break;
            else
                this->ReleaseReference();
        }
    }

    //
    // Release the reference we grabbed
    //
    this->ReleaseReference();

    return releasedThread;
}

//----------------------------------------------------------------------------------------
// TSemaphore::ReleaseAllThreads:
// Release everyone who’s blocked on us by simply releasing threads until no one is left.
//----------------------------------------------------------------------------------------
void TSemaphore::ReleaseAllThreads()
{
    //
    // Probably not necessary, but let's make sure that this
    // semaphore is never deleted while we're working with it.
    //
    ++fReferenceCount;
//    while (fBlockedThreads.QueuedThreads() > 0)
        this->ReleaseOneThread();

    //
    // Release the reference we grabbed
    //
    this->ReleaseReference();
}

//----------------------------------------------------------------------------------------
// TSemaphore::CheckIfTimerExpired
//
// CurrentTime is just 'TickCount', but since this routine is always called from a
// loop, I didn't think there was any point in calling it over and over again.
//
// If the timer has expired, then set fFailOnWakeup to errAETimeout and wake up
// all of the blocked threads.
//----------------------------------------------------------------------------------------
Boolean TSemaphore::CheckIfTimerExpired(unsigned long currentTime)
{
    //
    // In order for our timer to run out, one of fSemaphoreTimeoutValue
    // or fSemaphoreMaxWaitTime must be something other than kNeverTimeoutSemaphore,
    // AND the time must have expired for this semaphore.
    //
    return (    ((fSemaphoreTimeoutValue != kNeverTimeoutSemaphore) || (fSemaphoreMaxWaitTime != kNeverTimeoutSemaphore))
                && TimeExpired(fBlockStartTick, fTimeoutTick, currentTime)    );
}

//----------------------------------------------------------------------------------------
// TSemaphore::SemaphoreTimedOut
//
// If the timer expired, deal with it.
//----------------------------------------------------------------------------------------
void TSemaphore::SemaphoreTimedOut()
{
    // DebugStr("\pSemaphore timed out!  Wake up blocked threads");

    fFailOnWakeup = errAETimeout;
    this->ReleaseAllThreads();
}

//----------------------------------------------------------------------------------------
// TSemaphore::AddGracePeriod
//
// Acount for the fact that the machine may have been locked up for a while by
// user actions or what-have-you.
//----------------------------------------------------------------------------------------
void TSemaphore::AddGracePeriod(long gracePeriod)
{
    //
    // Pretend that our timer was reset 'gracePeriod' ticks
    // later than it actually was.
    //
    fTimeoutTick += gracePeriod;
} // TSemaphore::AddGracePeriod

//----------------------------------------------------------------------------------------
// TSemaphore::ResetTimeoutTimer
//
// Reset the timer, but don't allow it to go past 'maxTimoutValue'.
//----------------------------------------------------------------------------------------
void TSemaphore::ResetTimeoutTimer()
{
    unsigned long currentTime = TickCount();
    unsigned long newTimeoutValue = fSemaphoreTimeoutValue;

    //
    // Pin the timeout value rather than the timeout tick,
    // so we don't get messed up by overflow problems.
    //
    // Note that if we have passed '(fBlockStartTick + fSemaphoreMaxWaitTime)',
    // then maxTimeoutValue will be negative.  This is what we
    // want:  the semaphore should time out on the next call to
    // 'CheckIfTimerExpired'.
    //
    if(fSemaphoreMaxWaitTime != kNeverTimeoutSemaphore)
    {
        unsigned long maxTimeoutValue = (fBlockStartTick + fSemaphoreMaxWaitTime) - currentTime;
        if(newTimeoutValue > maxTimeoutValue)
            newTimeoutValue = maxTimeoutValue;
    }

    fTimeoutTick = currentTime + newTimeoutValue;

    //
    // Recalculate the next time that we're going to test
    // for Semaphore timeouts (just in case gNextTimeoutTest
    // is off on the 'forever' side of gLastTimeoutTest).
    //
    fgNextTimeoutTest = CloserTick(currentTime, fgNextTimeoutTest, fTimeoutTick);
}

//----------------------------------------------------------------------------------------
// TSemaphore::SetSemaphoreTimoutValue
//
// Specify some timeout value other than the default for this semaphore.
//
// Don't call 'SetSemaphoreTimoutValue' at arbitrary times, because it also resets the
// timeout timer.
//----------------------------------------------------------------------------------------
void TSemaphore::SetSemaphoreTimoutValue(long timeoutValue)
{
    fSemaphoreTimeoutValue = timeoutValue;
    this->ResetTimeoutTimer();
}

//----------------------------------------------------------------------------------------
// TSemaphore::SetSemaphoreMaxWaitTime
//
// Specify some maximum wait time other than the default for this semaphore.
//
// Don't call 'SetSemaphoreMaxWaitTime' at arbitrary times, because it also resets the
// timeout timer.
//----------------------------------------------------------------------------------------
void TSemaphore::SetSemaphoreMaxWaitTime(long timeoutValue)
{
    fSemaphoreMaxWaitTime = timeoutValue;
    this->ResetTimeoutTimer();
}