edgechasing.java

Java的面向对象数据库系统的源代码

// You can redistribute this software and/or modify it under the terms of
// the Ozone Core License version 1 published by ozone-db.org.
//
// The original code and portions created by SMB are
// Copyright (C) 1997-@year@ by SMB GmbH. All rights reserved.
//
// $Id: EdgeChasing.java,v 1.5 2002/12/29 11:15:57 per_nyfelt Exp $

package org.ozoneDB.core.dr;

import java.util.HashSet;

import org.ozoneDB.DxLib.*;
import org.ozoneDB.core.*;
import org.ozoneDB.util.*;

/**
 * @author <a href="http://www.softwarebuero.de/">SMB</a>
 * @version $Revision: 1.5 $Date: 2002/12/29 11:15:57 $
 */
public final class EdgeChasing extends DeadlockRecognition {

    protected Env env;


    public EdgeChasing( Env _env ) {
        this.env = _env;
    }


    public Locker detectDeadlock( Locker locker ) {
//      env.logWriter.newEntry( this, "*** detectDeadlock(): " + locker, LogWriter.DEBUG );
//      return sendLockMessage( locker, locker, true ) ? locker : null;
        return sendLockMessage( locker, locker, true );
    }


    /**
     * Recursive deadlock recognition.
     * @return True, if this transaction is blocked by root (?)
     */
    public Locker sendLockMessage( Locker root, Locker locker, boolean firstLevel ) {
        HashSet visitingLockers = new HashSet(); // The lockers we are currently already visiting

        return sendLockMessage(root,locker,firstLevel,visitingLockers);
    }

    /**
     * Recursive deadlock recognition.
     * @return True, if this transaction is blocked by root (?)
     */
    public Locker sendLockMessage(Locker root,Locker locker,boolean firstLevel,HashSet visitingLockers) {
        if (!locker.isDeadlocked()) {
            if (visitingLockers.add(locker)) {
                try {
                    env.logWriter.newEntry( this, "*** sendLockMessage(): " + locker+", visitingLockers="+visitingLockers+".", LogWriter.DEBUG );
                    Lockable blocker = locker.blockedBy();

                    if (blocker == null) {
                        return null;
                    }

                    try {
                        if (!firstLevel) {
                            if (root == locker) {
                                return null;
                            }

                            if (blocker == null) {
                                return null;
                            }
                        }

                        //bin selbst beim warten auf blocker blockiert; wenn ich
                        //lese-lock setzen moechte, muss ich die ta mit schreib-lock
                        //auf blocker kontrollieren; wenn schreib-lock alle ta mit
                        //lese-lock auf blocker - diese werden genau von allLockers()
                        //geliefert

                        //alle ta, die mich behindern; entweder ein schreibende oder
                        //viele lesende transaktionen
                        DxCollection lockers = blocker.allLockers();
                        Locker       deadLockingLocker = null;

                        if (lockers != null) {
                            DxIterator it = lockers.iterator();

                            while (it.next() != null) {
                                Locker nextLocker = (Locker)it.object();
                                if (nextLocker != locker) {
                                    if (visitingLockers.contains(nextLocker)) {
                                        deadLockingLocker =   nextLocker;
                                        /*
                                            We know we already are deadlocking. But let's traverse deeper if possible.
                                            In this case, we could find a second deadlock ring which the first depends
                                            on.

                                            What if we find a deadLockingLocker, it is the only one, but a locker which this
                                            locker depends on still has some locker free? If we still get deadlock-livelocks
                                            (deadlocks are resolved but they happen again and again in the same way), we
                                            have to consider this.

                                            Oh, these livelocks just happened..
                                        */
                                        nextLocker.setDeadlocked(true);
                                    } else {
    //                                  deadLockingLocker =   null;
                                    }
                                    //we are done if we have detected the first circle;
                                    //go on with next candidate otherwise

                                    Locker deadlocker = sendLockMessage(root,nextLocker,false,visitingLockers);

                                    // We continue our traversal until we reached every potential deadlocker (we have to do this due to deadlock-loops)
                                    if (deadlocker!=null) {
                                        if (false) {
                                            return deadlocker;
                                        } else {
                                            deadLockingLocker = deadlocker;
                                        }
                                    }
                                }
                            }
                        }

                        return deadLockingLocker;
                    } finally {
                        blocker.unpin();
                    }
                } finally {
                    visitingLockers.remove(locker);
                }
            } else {
                if (!locker.isDeadlocked()) {
                    locker.setDeadlocked(true);
                    env.logWriter.newEntry(this,"sendLockMessage(): We are about to visit "+locker+" twice (visitingLockers="+visitingLockers+"). This must not be because we would loop.",LogWriter.ERROR);
                } else {
                    env.logWriter.newEntry(this,"sendLockMessage(): We were about to visit "+locker+" twice (visitingLockers="+visitingLockers+"), but locker is already deadlocked.",LogWriter.ERROR);
                }
                return locker;
            }
        } else {
//          env.logWriter.newEntry(this,"sendLockMessage(): "+locker+" is deadlocked.",LogWriter.DEBUG2);
            return locker;
        }
    }

}