Quadcap Embeddable Database

com/quadcap/sql/lock/LockManager.java

Go to the documentation of this file.

package com.quadcap.sql.lock;

/* Copyright 1999 - 2003 Quadcap Software.  All rights reserved.
 *
 * This software is distributed under the Quadcap Free Software License.
 * This software may be used or modified for any purpose, personal or
 * commercial.  Open Source redistributions are permitted.  Commercial
 * redistribution of larger works derived from, or works which bundle
 * this software requires a "Commercial Redistribution License"; see
 * http://www.quadcap.com/purchase.
 *
 * Redistributions qualify as "Open Source" under  one of the following terms:
 *   
 *    Redistributions are made at no charge beyond the reasonable cost of
 *    materials and delivery.
 *
 *    Redistributions are accompanied by a copy of the Source Code or by an
 *    irrevocable offer to provide a copy of the Source Code for up to three
 *    years at the cost of materials and delivery.  Such redistributions
 *    must allow further use, modification, and redistribution of the Source
 *    Code under substantially the same terms as this license.
 *
 * Redistributions of source code must retain the copyright notices as they
 * appear in each source code file, these license terms, and the
 * disclaimer/limitation of liability set forth as paragraph 6 below.
 *
 * Redistributions in binary form must reproduce this Copyright Notice,
 * these license terms, and the disclaimer/limitation of liability set
 * forth as paragraph 6 below, in the documentation and/or other materials
 * provided with the distribution.
 *
 * The Software is provided on an "AS IS" basis.  No warranty is
 * provided that the Software is free of defects, or fit for a
 * particular purpose.  
 *
 * Limitation of Liability. Quadcap Software shall not be liable
 * for any damages suffered by the Licensee or any third party resulting
 * from use of the Software.
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;

import java.util.Comparator;

import java.sql.SQLException;

import javax.concurrent.Sync;

import com.quadcap.util.Debug;
import com.quadcap.util.Util;

import com.quadcap.util.ConfigNumber;


/**
 * Manage a hierarchical set of read/write/intention locks.
 *
 * @author Stan Bailes
 */
public class LockManager {
    //#ifdef TRACE
    /*{com.quadcap.qed.Trace-vars.xml-1064}
     * <config-var>
     *   <config-name>qed.trace.locks</config-name>
     *   <config-dflt>0</config-dflt>
     *   <config-desc>
     *   <pre>
     *     bit 0: verbose lock tracing
     *     bit 1: lock tracing
     *     bit 2: really verbose lock tracing
     *     bit 3: transactions
     *     bit 4: dump locktable every 30 seconds
     *    </pre>
     *    </config-desc>
     * </config-var>
     */
    protected static final
    ConfigNumber trace = ConfigNumber.find("qed.trace.locks", "0");
    //#endif

    protected static final
    ConfigNumber lockTimeout = ConfigNumber.find("qed.lock.Timeout", "60");

    private long                        transCount      = 1;

    final Object                        locksLock       = new Object();

    /** Pool of lock objects */
    LockPool                            locks           = new LockPool();

    /** Pool of 'held' locks */
    HeldLockPool                        held            = new HeldLockPool();

    /** Temp held lock object used for searching */
    HeldLock                            tmpHeld         = null;

    /** Pool of transaction objects. */
    TransactionPool                     transactions    =new TransactionPool();

    /** held locks sorted by transaction */
    SortedArray                         byTrans;
    SortedArrayIterator                 byTransIter;
    
    /**
     * Constructor
     */
    public LockManager() {
        Comparator compare = new Comparator() {
            public int compare(Object a, Object b) {
                return HeldLock.compare((HeldLock)a, (HeldLock)b);
            }
        };
        byTrans = new SortedArray(compare);
        byTransIter = new SortedArrayIterator(byTrans);
        tmpHeld = held.get(null, null, LockMode.IX);
        final LockManager lockMgr = this;

        //#ifdef DEBUG
        if (trace.bit(4)) {
            Thread t = new Thread() {
                public void run() {
                    setName("LockManager Debug");
                    Debug.println("Lock dump thread running");
                    while (lockMgr != null) {
                        try {
                            Thread.sleep(10000);
                            synchronized (lockMgr.locksLock) {
                                if (lockMgr.byTrans.size() > 0) {
                                    Debug.println("DUMP: " +
                                                  lockMgr.toString());
                                }
                            }
                        } catch (Throwable e) {
                            Debug.print(e);
                        }
                    }
                }
                };
            t.setDaemon(true);
            t.start(); 
        }
        //#endif
    }
    
    /**
     * Allocate a new Transaction.  All lock operations are performed
     * on behalf of a Transaction.
     */
    public final Transaction getTransaction(long transId) {
        synchronized (locksLock) {
            Transaction t = (Transaction)transactions.get(transId);
            //#ifdef DEBUG
            if (trace.bit(3)) {
                Debug.println("getTransaction() = " + t);
                if (trace.bit(2)) {
                    Debug.println("this = " + this);
                }
            }
            //#endif
            return t;
        }
    }

    /**
     * Find an existing transaction.  Return null if the specified
     * transaction doesn't exist.
     */
    public Transaction findTransaction(long transId) {
        return transactions.find(transId);
    }

    /**
     * End a transaction, releasing all of its locks
     */
    public void releaseTransaction(Transaction t) {
        //#ifdef DEBUG
        if (trace.bit(3)) {
            Debug.println("releaseTransaction(" + t + ")");
            if (trace.bit(2)) {
                Debug.println("this = " + this);
            }
        }
        //#endif
        synchronized (locksLock) {
            try {
                // for each lock held by the transaction
                Iterator tlocks = locksForTransaction(t);
                //#ifdef TRACE
                if (trace.bit(1)) {
                    Debug.println("releaseTransaction(" + t + ") [1]");
                }
                //#endif
                //Debug.println("releaseTransaction(" + t + "), held locks = " + byTrans);
                while (tlocks.hasNext()) {
                    HeldLock h = (HeldLock)tlocks.next();
                    boolean saveMe = false;
                    if (h.trans.getTransactionId() < t.getTransactionId()) continue;
                    if (h.trans.getTransactionId() > t.getTransactionId()) break;
                    //Debug.println("  Releasing: " + h);
                    Lock lock = h.lock;
                    int mode = h.mode;
                    tlocks.remove();
                    if (h.mode == LockMode.NL) continue;
                    //#ifdef TRACE
                    if (trace.bit(1)) {
                        Debug.println("[release] lock(" + t + ", " + lock + " in " +
                            LockMode.toString(mode));
                    }
                    //#endif
                    lock.decrHeldCount(mode);
                    Transaction w = lock.headWaitQueue();
                    while (w != null && w.getWaitMode() == LockMode.NL) {
                        lock.popWaitQueue();
                        w = lock.headWaitQueue();
                    }
                    if (w != null && !w.equals(t)) {
                        if (lock.couldLock(w.getWaitMode())) {
                            lock.popWaitQueue();
                            HeldLock wl = w.getWait();
                            //#ifdef TRACE
                            if (trace.bit(1)) {
                                Debug.println("" + t + " releasing " + lock +
                                              ", waking " + wl);
                            }
                            //#endif
                            
                            wl.mode = wl.waitMode;                            
                            acquireLock(wl);
                            w.clearWait();
                            try {
                            } catch (InterruptedException ex) {
                            }
                        }
                    }
                    held.release(h);
                }
            } finally {
                transactions.release(t);
            }
            //#ifdef TRACE
            if (trace.bit(1)) {
                Debug.println("releaseTransaction(" + t + ") done");
                if (trace.bit(2)) {
                    Debug.println("this = " + this);
                }
            }
            //#endif
        }
    }

    /**
     * Return an iterator over all active transactions
     */
    public Iterator transactions() {
        return transactions.iterator();
    }

    /**
     * Return an Iterator over the held locks positioned at the first
     * lock owned by transaction 't'.
     */
    final Iterator locksForTransaction(Transaction t) {
        tmpHeld.trans = t;
        tmpHeld.lock = null;
        byTransIter.position(tmpHeld);
        return byTransIter;
    }

    final HeldLock getLockForTransaction(Transaction t, Lock lock) {
        tmpHeld.trans = t;
        tmpHeld.lock = lock;
        tmpHeld.mode = LockMode.NL;
        byTransIter.position(tmpHeld);
        while (byTransIter.hasNext()) {
            HeldLock h = (HeldLock)byTransIter.next();
            if (t.getTransactionId() > h.trans.getTransactionId()) {
                return null;
            }
            if (t.getTransactionId() == h.trans.getTransactionId() &&
                lock.hashCode() == h.lock.hashCode()) {
                return h;
            }
        }
        return null;
    }
    
    /**
     * Instantiate the specified lock on behalf of transaction 't',
     * which may or may not already have this lock.
     */
    public final Lock getLock(Transaction t, Lock parent, String name,
                              int mode)
        throws SQLException
    {
        HeldLock h = null;
        boolean newLock = false;
        //#ifdef TRACE
        if (trace.bit(1)) {
            Debug.println("---- getLock(" + t + ", " + parent + ", " +
                          name + ", " + LockMode.toString(mode) + ")");
        }
        //#endif
        try {
            synchronized (locksLock) {
                Lock lock = locks.get(parent, name);
                checkParentsLockMode(t, lock, mode);

                h = getLockForTransaction(t, lock);
                if (h != null) {
                    //Debug.println("  holding: " + h);
                    // 't' already has 'lock'; check the mode.
                    if (LockMode.implies(h.mode, mode)) {
                        //Debug.println("  Already have: " + h);
                        return h.lock;
                    }
                    if (LockMode.implies(mode, h.mode)) {
                        if (lock.couldPromote(h.mode, mode)) {
                            promoteLock(h, mode);
                            //Debug.println("  Promoted: " + h);
                            return h.lock;
                        } else {
                            //Debug.println("  Can't promote: " + h + ": " + lock.dump());
                        }
                    } else {
                        throw new RuntimeException("Transaction " + t +
                                                   " has lock " + lock +
                                                   " in mode " +
                                                   LockMode.toString(h.mode) +
                                                   ", trying to lock now in mode "+
                                                   LockMode.toString(mode));
                    }
                } else {
                    newLock = true;
                    //Debug.println("  Don't have it yet");
                    // 't' does not have 'lock' in any way
                    h = held.get(t, lock, mode);
                    if (lock.couldLock(mode) && !lock.hasWaiters()) {
                        acquireLock(h);
                        //Debug.println("  Got lock: " + h);
                        return h.lock;
                    }
                }
                h.setWaitMode(mode);
                try {
                    s = waitForLock(h);
                } catch (InterruptedException ex) {
                    throw new SQLException("Interrupted trying to get lock: " +
                                           name);
                }
                    
            }
            //#ifdef DEBUG
            if (trace.bit(0)) {
                Debug.println("  Waiting for: " + h);
                if (trace.bit(2)) {
                    Debug.println(byTrans.toString());
                }
            }
            //#endif
            boolean got = false;
            try {
            } catch (InterruptedException ex) { }
            if (!got) {
                Debug.println("Lock timed out: " + name + " after " +
                              lockTimeout.longValue() + 
                              " seconds");
                Debug.println("LockManager: " + this);
//                  try {
//                      got = s.attempt(lockTimeout.longValue() * 1000);
//                  } catch (InterruptedException ex) {}
                if (!got) {
                    t.setWait(null);
                    if (newLock) {
                        held.release(h);
                        newLock = false;
                    }
                    throw new SQLException("Timed out trying to get lock: " +
                                           name + " for [T:" + t + "]");
                }
            }
            //#ifdef DEBUG
            if (trace.bit(0)) {
                Debug.println("  Wait done for: " + h);
            }
            //#endif
            return h.lock;
        } finally {
            //#ifdef TRACE
            if (trace.bit(1)) {
                Debug.println("getLock(" + name + ") done");
            }
            //#endif
        }
    }
        
    /**
     * We're in the critical section still
     */
        final Transaction t = h.trans;
        //#ifdef PARANOID
//-     if (t.getWait() != null)
//-         throw new RuntimeException("Transaction already waiting");
        //#endif
        h.lock.addWaitQueue(t);
        t.setWait(h);
        return t.getSync();
    }

    /**
     * Ensure that the lock's parent(s) are properly locked, to enable
     * locking <code>lock</code> in the specified mode.
     */
    final void checkParentsLockMode(Transaction t, Lock lock, int mode) {
        Lock p = lock.getParent();
        if (p != null) {
            HeldLock h = getLockForTransaction(t, p);
            if (h == null) {
                //#ifdef DEBUG
                Debug.println("Held: " + byTrans + ", lock = " + lock);
                Debug.println("LockManager: " + this);
                //#endif
                throw new RuntimeException("no lock on parent " + p);
            }
            if (!couldLockWithParentMode(h.mode, mode)) {
                //#ifdef DEBUG
                Debug.println("lock = " + lock + ", p = " + p + ", h = " + h);
                Debug.println("LockManager: " + this);
                //#endif
                throw new RuntimeException("parent not properly locked: " + h);
            }
            checkParentsLockMode(t, p, mode);
        }
    }

    final boolean couldLockWithParentMode(int pmode, int mode) {
        switch (mode) {
        case LockMode.S:
        case LockMode.IS:
            return pmode == LockMode.X || pmode == LockMode.S
                || pmode == LockMode.IX || pmode == LockMode.IS;
        case LockMode.X:
        case LockMode.IX:
        case LockMode.SIX:
            return pmode == LockMode.X
                || pmode == LockMode.IX || pmode == LockMode.SIX;
        default:
            throw new RuntimeException("bad lock mode: " +
                                       LockMode.toString(mode));
        }
    }

    void promoteLock(HeldLock h, int mode) {
        h.lock.decrHeldCount(h.mode);
        h.lock.incrHeldCount(mode);
        h.mode = mode;
    }

    void acquireLock(HeldLock h) {
        h.lock.incrHeldCount(h.mode);
        byTrans.add(h);
    }

    //#ifdef DEBUG
    public String toString() {
        synchronized (locksLock) {
            StringBuffer sb = new StringBuffer();
            sb.append("\nTransactions:\n------------\n");
            sb.append(transactions);
            sb.append("\nHeld:\n----\n");
            sb.append(byTrans);
            sb.append("\nLocks:\n-----\n");
            sb.append(locks);
            sb.append("\n");
            return sb.toString();   
        }
    }
    //#endif
}