From: Kevin Lewis
Date: April 3 2009 4:34am
Subject: Mini-Cycle Manager vs a Global Cycle Manager
List-Archive: http://lists.mysql.com/falcon/666
Message-Id: <49D591D5.6030603@sun.com>
MIME-Version: 1.0
Content-Type: text/plain; format=flowed; charset=ISO-8859-1
Content-Transfer-Encoding: 7BIT

At the meeting in Athens,  Kelly Long and I worked out a localized
version of cycle locking that would allow Record and RecordVersions to
be deleted with the assurance that no other thread has a dangling
temporary stack based pointer.  The following is an description of this 
Mini-Cycle Manager followed by a description of the Global Cycle Manager 
that Jim implemented last week.

Mini-Cycle manager
======================

* Each RecordLeaf contains a Cycle object with 4 syncObjects.
* This is intended to replace both RecordLeaf::syncObject and
Table::syncPriorVersions
* Before collecting a local stack based pointer to a Record object, each
thread would get a shared lock on the the currentCycle.
	currentCycle = RecordLeaf::cycle.share();
* That cycle must be remembered so it can be unlocked when the local
stack based pointer is no longer needed.

* Any thread that needs to change make a change in the linked list of
RecordVersion objects, from RelordLeaf::records[n] through each
RecordVersion::priorVersion, must follow the following procedure
   1) 'Pedal' the cycle - This involves changing the current cycle
number  so that any new reader thread following this chain of pointers
will get a shared lock on the next cycle. Since this can be done by
multiple threads at once, it is the most critical part of the mini-cycle
process.
     1. nextCycle = INTERLOCKED_INCREMENT(currentCycleCount);
        Two simultaneous threads pedaling the cycle at the same
        time will get successive nextCycle values.
     2. syncObjects[nextCycle & 3].lock(NULL, Exclusive);
        These two threads will exclusively lock their own 'next'
        cycle to prevent readers from reading on that cycle until
        the change to the linkage is completed.
     3. syncObjects[(nextCycle - 1) & 3].lock(NULL, Shared);
        Keep this cycle active until you need to 'pump' it.
        In the case where two threads are pedaling at the same
        time, the thread with the higher nextCycle will wait for
        this shared lock.  (Note: there may be a race condition where;
           Thread 1 pedals step 1,
           Thread 2 pedals step 1,
           Thread 2 pedals step 2,
           Thread 2 pedals step 3,
           Thread 1 pedals step 2,
           Thread 1 pedals step 3
        If this happens, thread 2 will come out of the pedal step
        while thread 1 is waiting for it.  This is discussed in
        step 3 below.
   2) Change the linkage - This can be done with a single atomic
operation, COMPARE_EXCHANGE_POINTER(). Since the linkage is always
followed in one direction, any thread following the chain will either 
see this leaving RecordVersion or not. It does not matter if it is 
missed. If a thread has a pointer to it, that pointer should be reliable 
until that thread's shared lock is given up.
   3) Pump the current cycle. - This means getting an exclusive lock on
the current cycle, waiting, if necessary, for all threads to release
their shared locks.  It means that no threads have pointers to what was
detached after the current cycle was pedaled.
     1. syncObjects[nextCycle & 3].downGrade(Shared);
     2. syncObjects[(nextCycle - 1) & 3].unlock();
     3. syncObjects[(nextCycle - 1) & 3].lock(NULL, Exclusive);
     4. syncObjects[(nextCycle - 1) & 3].unlock();
     Note, In the case described above where Thread 2 gets to pump first,
     it will downgrade the cycle ahead of Thread 1, unlock the shared
     lock that Thread 1 is waiting on,  and then wait on Thread 1 in
     Pump.step3.  Then thread 1 will wake up and complete all 4 steps of
     its own pump cycle.  So both threads will be able to pump the cycle
     even if their pedal steps race and crossed paths.

* While a Record version is detached, and before the pump completes, it
must be treated as if other threads are looking at it.  You cannot
change things in this object that will cause a race condition or 
assertion by any other thread which may be looking at it.

================================================================
Global Cycle Manager.

The global Cycle Manager is a much simpler design.  It has the advantage 
that only one thread, the CycleManager thread, ever 'pumps' the cycle. 
Another characteristic (which may be a advantage or an disadvantage) is 
that the doomed objects hang around longer.  Threads which add objects 
to a CycleManager's 'purgatory' list cannot wait for the pump.  If a 
thread needs to do anything to a doomed object after all other pointers 
are gone, then this solution does not work.  Fortunately, there is 
nothing that needs to be done to a doomed record version object while 
other threads still may have pointers to it. (*** This conclusion or 
assumption must be considered whenever working with the record tree)

The CycleManager Thread has a loop in which it sleeps for (currently) 1 
second.  When it wakes up, it does this;
   1) Collect/Separate the doomed list of Record and RecordVersion 
objects that are currently in purgatory.
   2) Make the SyncObject *currentCycle point to the other lock.  Unlike 
the Mini-Cycle Manager described above, this design only needs two 
syncObjects since only one thread pumps at a time.  From this point on, 
any threads that may accrss a record chain will put a shared lock on the 
next cycle.  What about threads that lock the old cycle after step 1 and 
before step 2?  If one of these threads collects a pointer to a record 
that is detached and added to the current purgatory list, there will not 
be a problem.  This thread will just get pumped on an earlier cycle.
   3) Pump the Cycle by getting an exclusive lock on the SyncObject that 
currentCycle is no longer pointing to.  When this lock is achieved, it 
is immediately unlocked.
   4) Step through each doomed record and call record->release().  No 
other thread is pointing to these.

The thread that detaches records from a record chain must have a shared 
lock on the currentCycle itself.  It detaches the record from either the 
RecordLeaf or the record higher up the chain.  Then it calls 
garbageCollect on this record, knowing that some other thread may still 
have a pointer to it.  Finally, where it uesed to call 
Record::release(), it now calls Record::queueForDelete()

Each thread that may access one or more Record or RecordVersion objects 
on a priorRecord chain needs to lock the syncObject on the current 
Cycle.  This is done easily by instantiating a CycleLock object on the 
stack.  Its constructor locks the current cycle and its destructor 
releases it.  The CycleLock registers itself with the Thread object. In 
order to catch all possible thread stacks that may need to instantiate a 
CycleLock, I added temporary code into RecordVersion::getPriorVersion() 
that checks the Thread for a current CycleLock.  If a thread stack 
happens to instantiate two CycleLocks, the second will not lock again. 
It will just set a pointer to the first so that the status of the lock 
can be determined.

If a thread needs to wait for another Transaction to complete, the 
CycleLock which was instantiated higher up the stack is used to unlock 
the cycle.  After the wait, the current cycle is locked.  This means 
that any temporary stack based pointers higher up the stack cannot be 
trusted anymore.
========================================================

I hope this helps to explain why we chose the Global Cycle Manager and 
how it works.

Kevin