Return-Path: X-Original-To: apmail-directory-commits-archive@www.apache.org Delivered-To: apmail-directory-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 1A0949ABB for ; Thu, 27 Oct 2011 14:11:26 +0000 (UTC) Received: (qmail 35753 invoked by uid 500); 27 Oct 2011 14:11:26 -0000 Delivered-To: apmail-directory-commits-archive@directory.apache.org Received: (qmail 35710 invoked by uid 500); 27 Oct 2011 14:11:25 -0000 Mailing-List: contact commits-help@directory.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@directory.apache.org Delivered-To: mailing list commits@directory.apache.org Received: (qmail 35703 invoked by uid 99); 27 Oct 2011 14:11:25 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 27 Oct 2011 14:11:25 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 27 Oct 2011 14:11:23 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id 75B0E23889E3 for ; Thu, 27 Oct 2011 14:11:03 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1189768 - in /directory/apacheds/branches/apacheds-txns: core-api/src/main/java/org/apache/directory/server/core/txn/ core/src/main/java/org/apache/directory/server/core/txn/ Date: Thu, 27 Oct 2011 14:11:03 -0000 To: commits@directory.apache.org From: saya@apache.org X-Mailer: svnmailer-1.0.8-patched Message-Id: <20111027141103.75B0E23889E3@eris.apache.org> Author: saya Date: Thu Oct 27 14:11:02 2011 New Revision: 1189768 URL: http://svn.apache.org/viewvc?rev=1189768&view=rev Log: Changes to add conflict detection service to the txn manager. DnSet: keeps track of the base dn and the scope a read depends on or a write afffects. For a txn, readset is always a superset of writeset. When txn tries to commit, its read set is checked against the writeset of the txns that committed after it started. If conflict is found, a txnconflict exception is thrown. Added: directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnConflictException.java directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DnSet.java Modified: directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnLogManager.java directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnManager.java directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnLogManager.java directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnManager.java directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/ReadWriteTxn.java Added: directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnConflictException.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnConflictException.java?rev=1189768&view=auto ============================================================================== --- directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnConflictException.java (added) +++ directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnConflictException.java Thu Oct 27 14:11:02 2011 @@ -0,0 +1,51 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + * + */ +package org.apache.directory.server.core.txn; + +/** + * An exception used when the txn conflict is detected. + * + * @author Apache Directory Project + */ +public class TxnConflictException extends Exception +{ + public TxnConflictException() + { + } + + + public TxnConflictException( String s ) + { + super( s ); + } + + + public TxnConflictException( Throwable cause ) + { + super( cause ); + } + + + public TxnConflictException( String s, Throwable cause ) + { + super( s, cause ); + } + +} \ No newline at end of file Modified: directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnLogManager.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnLogManager.java?rev=1189768&r1=1189767&r2=1189768&view=diff ============================================================================== --- directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnLogManager.java (original) +++ directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnLogManager.java Thu Oct 27 14:11:02 2011 @@ -27,6 +27,8 @@ import org.apache.directory.server.core. import org.apache.directory.shared.ldap.model.entry.Entry; import org.apache.directory.shared.ldap.model.name.Dn; +import org.apache.directory.shared.ldap.model.message.SearchScope; + import java.io.IOException; /** @@ -42,4 +44,8 @@ public interface TxnLogManager Entry mergeUpdates(Dn partitionDN, ID entryID, Entry entry ); IndexCursor wrap( Dn partitionDn, IndexCursor wrappedCursor, IndexComparator comparator, String attributeOid, boolean forwardIndex, Object onlyValueKey, ID onlyIDKey ) throws Exception; + + void addRead( Dn baseDn, SearchScope scope ); + + void addWrite( Dn baseDn, SearchScope scope ); } Modified: directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnManager.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnManager.java?rev=1189768&r1=1189767&r2=1189768&view=diff ============================================================================== --- directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnManager.java (original) +++ directory/apacheds/branches/apacheds-txns/core-api/src/main/java/org/apache/directory/server/core/txn/TxnManager.java Thu Oct 27 14:11:02 2011 @@ -31,7 +31,7 @@ public interface TxnManager { void beginTransaction( boolean readOnly ) throws IOException; - void commitTransaction() throws IOException; + void commitTransaction() throws IOException, TxnConflictException; void abortTransaction() throws IOException; Modified: directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnLogManager.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnLogManager.java?rev=1189768&r1=1189767&r2=1189768&view=diff ============================================================================== --- directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnLogManager.java (original) +++ directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnLogManager.java Thu Oct 27 14:11:02 2011 @@ -30,6 +30,7 @@ import org.apache.directory.server.core. import org.apache.directory.server.core.api.partition.index.IndexComparator; import org.apache.directory.shared.ldap.model.entry.Entry; +import org.apache.directory.shared.ldap.model.message.SearchScope; import org.apache.directory.shared.ldap.model.name.Dn; import org.apache.directory.server.core.txn.logedit.LogEdit; @@ -148,4 +149,53 @@ public class DefaultTxnLogManager im { return new IndexCursorWrapper( partitionDn, wrappedCursor, comparator, attributeOid, forwardIndex, onlyValueKey, onlyIDKey ); } + + + /** + * {@inheritDoc} + */ + public void addRead( Dn baseDn, SearchScope scope ) + { + addDnSet( baseDn, scope, true ); + } + + + /** + * {@inheritDoc} + */ + public void addWrite( Dn baseDn, SearchScope scope ) + { + addDnSet( baseDn, scope, true ); + } + + + private void addDnSet( Dn baseDn, SearchScope scope, boolean read ) + { + Transaction curTxn = txnManager.getCurTxn(); + + if ( ( curTxn == null ) ) + { + throw new IllegalStateException( "Trying to add dn set wihout txn" ); + } + + // No need to do anything for read only txns + if ( !( curTxn instanceof ReadWriteTxn ) ) + { + + return; + + } + + DnSet dnSet = new DnSet( baseDn, scope ); + ReadWriteTxn txn = ( ReadWriteTxn ) curTxn; + + if ( read ) + { + txn.addRead( dnSet ); + } + else + { + txn.addWrite( dnSet ); + } + } } \ No newline at end of file Modified: directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnManager.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnManager.java?rev=1189768&r1=1189767&r2=1189768&view=diff ============================================================================== --- directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnManager.java (original) +++ directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DefaultTxnManager.java Thu Oct 27 14:11:02 2011 @@ -146,7 +146,7 @@ public class DefaultTxnManager imple /** * {@inheritDoc} */ - public void commitTransaction() throws IOException + public void commitTransaction() throws IOException, TxnConflictException { Transaction txn = getCurTxn(); @@ -375,7 +375,7 @@ public class DefaultTxnManager imple } - private void commitReadWriteTxn( ReadWriteTxn txn ) throws IOException + private void commitReadWriteTxn( ReadWriteTxn txn ) throws IOException, TxnConflictException { UserLogRecord logRecord = txn.getUserLogRecord(); @@ -410,7 +410,27 @@ public class DefaultTxnManager imple verifyLock.lock(); - // TODO verify txn here throw conflict exception if necessary + //Verify txn and throw conflict exception if necessary + Iterator> it = committedQueue.iterator(); + ReadWriteTxn toCheckTxn; + long startTime = txn.getStartTime(); + + while ( it.hasNext() ) + { + toCheckTxn = it.next(); + + // Check txns that committed after we started + if ( toCheckTxn.getCommitTime() < startTime ) + { + continue; + } + + if ( txn.hasConflict( toCheckTxn ) ) + { + verifyLock.unlock(); + throw new TxnConflictException(); + } + } writeTxnsLock.lock(); @@ -421,6 +441,7 @@ public class DefaultTxnManager imple txn.commitTxn( logRecord.getLogAnchor().getLogLSN() ); latestVerifiedTxn.set( txn ); + committedQueue.offer( txn ); // TODO when sync is done outside the locks, advance latest commit outside the locks latestCommittedTxn.set( txn ); Added: directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DnSet.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DnSet.java?rev=1189768&view=auto ============================================================================== --- directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DnSet.java (added) +++ directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/DnSet.java Thu Oct 27 14:11:02 2011 @@ -0,0 +1,59 @@ + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + * + */ + +package org.apache.directory.server.core.txn; + +import org.apache.directory.shared.ldap.model.name.Dn; +import org.apache.directory.shared.ldap.model.message.SearchScope; + +/** + * A class representing the set of Dns a read operation depends or the set of Dns a write + * operation affects. + * + * @author Apache Directory Project + */ +public class DnSet +{ + /** Base Dn */ + private Dn baseDn; + + /** Scope of the set */ + SearchScope dnScope; + + + public DnSet( Dn base, SearchScope scope ) + { + baseDn = base; + dnScope = scope; + } + + + public Dn getBaseDn() + { + return baseDn; + } + + + public SearchScope getScope() + { + return dnScope; + } +} Modified: directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/ReadWriteTxn.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/ReadWriteTxn.java?rev=1189768&r1=1189767&r2=1189768&view=diff ============================================================================== --- directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/ReadWriteTxn.java (original) +++ directory/apacheds/branches/apacheds-txns/core/src/main/java/org/apache/directory/server/core/txn/ReadWriteTxn.java Thu Oct 27 14:11:02 2011 @@ -52,6 +52,8 @@ import org.apache.directory.shared.ldap. import org.apache.directory.shared.ldap.model.constants.SchemaConstants; +import org.apache.directory.shared.ldap.model.message.SearchScope; + /** * * @author Apache Directory Project @@ -73,14 +75,25 @@ class ReadWriteTxn extends AbstractT /** User record used to communicate data with log manager */ private UserLogRecord logRecord = new UserLogRecord(); + /** A summary of forward index adds */ private Map >>> forwardIndexAdds = new HashMap >>>(); + /** A summary of reverse index adds */ private Map >>> reverseIndexAdds = new HashMap >>>(); + /** A summary of index deletes */ private Map >>> indexDeletes = new HashMap >>>(); + + + /** List of Dn sets this txn depends */ + private List readDns = new LinkedList(); + + /** List of Dn sets affected by the write operations of this txn */ + private List writeDns = new LinkedList(); + public AtomicInteger getRefCount() { @@ -350,4 +363,93 @@ class ReadWriteTxn extends AbstractT return txnIndexCursor; } + + public void addRead( DnSet readSet ) + { + readDns.add( readSet ); + } + + public void addWrite( DnSet writeSet ) + { + writeDns.add( writeSet ); + + // Changing a dn means also read dependency + readDns.add( writeSet ); + } + + public List getWriteSet() + { + return writeDns; + } + + public boolean hasConflict( ReadWriteTxn txn ) + { + boolean result = false; + + + List txnWriteDns = txn.getWriteSet(); + Iterator writeIt = txnWriteDns.iterator(); + Iterator readIt = readDns.iterator(); + + DnSet readDnSet; + SearchScope readScope; + DnSet writeDnSet; + SearchScope writeScope; + + while ( readIt.hasNext() ) + { + readDnSet = readIt.next(); + readScope = readDnSet.getScope(); + + while ( writeIt.hasNext() ) + { + writeDnSet = writeIt.next(); + writeScope = writeDnSet.getScope(); + + if ( readScope.equals( SearchScope.OBJECT ) ) + { + if ( writeScope.equals( SearchScope.OBJECT ) ) + { + if ( readDnSet.getBaseDn().equals( writeDnSet.getBaseDn() ) ) + { + result = true; + break; + } + } + else //one level or subtree scope for the write. + { + // Even if one level scope, conservatively check the whole subtree + if ( readDnSet.getBaseDn().isDescendantOf( writeDnSet.getBaseDn() ) ) + { + result = true; + break; + } + } + } + else //one level or subtree scope for the read. + { + if ( writeScope.equals( SearchScope.OBJECT ) ) + { + if ( readDnSet.getBaseDn().isAncestorOf( writeDnSet.getBaseDn() ) ) + { + result = true; + break; + } + } + else //one level or subtree scope for the write. + { + // Even if one level scope, conservatively check if any basedn is descendent of the other + if ( ( readDnSet.getBaseDn().isDescendantOf( writeDnSet.getBaseDn() ) ) || + ( readDnSet.getBaseDn().isAncestorOf( writeDnSet.getBaseDn() ) ) ) + { + result = true; + break; + } + } + } + } // end of inner while loop + } // end of outer while loop + + return result; + } }