CR-6653 OPENDJ-1878: re-implemented LockManager to support sub-tree write l...

Matthew Swift

16.49.2015 a5789e69cf5ecfff3234af5b81dfd5fc3de6d1e3

 opendj-server-legacy/src/main/java/org/opends/server/backends/LDIFBackend.java

@@ -102,14 +102,9 @@
   */
  public LDIFBackend()
  {
    super();

    entryMap = new LinkedHashMap<DN,Entry>();
    childDNs = new HashMap<DN, Set<DN>>();

    boolean useFairLocking =
         DirectoryServer.getEnvironmentConfig().getLockManagerFairOrdering();
    backendLock = new ReentrantReadWriteLock(useFairLocking);
    backendLock = new ReentrantReadWriteLock();
  }

  /** {@inheritDoc} */

 opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryContainer.java

@@ -1887,8 +1887,7 @@
  /**
   * Fetch an entry by DN, trying the entry cache first, then the database.
   * Retrieves the requested entry, trying the entry cache first,
   * then the database.  Note that the caller must hold a read or write lock
   * on the specified DN.
   * then the database.
   *
   * @param entryDN The distinguished name of the entry to retrieve.
   * @return The requested entry, or <CODE>null</CODE> if the entry does not

 opendj-server-legacy/src/main/java/org/opends/server/backends/task/Task.java

@@ -36,7 +36,6 @@
import java.util.List;
import java.util.TimeZone;
import java.util.UUID;
import java.util.concurrent.locks.Lock;

import javax.mail.MessagingException;

@@ -47,6 +46,7 @@
import org.opends.messages.Severity;
import org.opends.server.core.DirectoryServer;
import org.opends.server.types.*;
import org.opends.server.types.LockManager.DNLock;
import org.opends.server.util.EMailMessage;
import org.opends.server.util.StaticUtils;
import org.opends.server.util.TimeThread;
@@ -583,13 +583,11 @@
  {
    // We only need to grab the entry-level lock if we don't already hold the
    // broader scheduler lock.
    boolean needLock = (! taskScheduler.holdsSchedulerLock());
    Lock lock = null;
    if (needLock)
    DNLock lock = null;
    if (!taskScheduler.holdsSchedulerLock())
    {
      lock = taskScheduler.writeLockEntry(taskEntryDN);
    }

    try
    {
      this.taskState = taskState;
@@ -601,9 +599,9 @@
    }
    finally
    {
      if (needLock)
      if (lock != null)
      {
        taskScheduler.unlockEntry(taskEntryDN, lock);
        lock.unlock();
      }
    }
  }
@@ -675,13 +673,11 @@
  {
    // We only need to grab the entry-level lock if we don't already hold the
    // broader scheduler lock.
    boolean needLock = (! taskScheduler.holdsSchedulerLock());
    Lock lock = null;
    if (needLock)
    DNLock lock = null;
    if (!taskScheduler.holdsSchedulerLock())
    {
      lock = taskScheduler.writeLockEntry(taskEntryDN);
    }

    try
    {
      Entry taskEntry = getTaskEntry();
@@ -694,9 +690,9 @@
    }
    finally
    {
      if (needLock)
      if (lock != null)
      {
        taskScheduler.unlockEntry(taskEntryDN, lock);
        lock.unlock();
      }
    }
  }
@@ -744,13 +740,11 @@
  {
    // We only need to grab the entry-level lock if we don't already hold the
    // broader scheduler lock.
    boolean needLock = (! taskScheduler.holdsSchedulerLock());
    Lock lock = null;
    if (needLock)
    DNLock lock = null;
    if (!taskScheduler.holdsSchedulerLock())
    {
      lock = taskScheduler.writeLockEntry(taskEntryDN);
    }

    try
    {
      this.actualStartTime = actualStartTime;
@@ -764,9 +758,9 @@
    }
    finally
    {
      if (needLock)
      if (lock != null)
      {
        taskScheduler.unlockEntry(taskEntryDN, lock);
        lock.unlock();
      }
    }
  }
@@ -800,13 +794,11 @@
  {
    // We only need to grab the entry-level lock if we don't already hold the
    // broader scheduler lock.
    boolean needLock = (! taskScheduler.holdsSchedulerLock());
    Lock lock = null;
    if (needLock)
    DNLock lock = null;
    if (!taskScheduler.holdsSchedulerLock())
    {
      lock = taskScheduler.writeLockEntry(taskEntryDN);
    }

    try
    {
      this.completionTime = completionTime;
@@ -822,9 +814,9 @@
    }
    finally
    {
      if (needLock)
      if (lock != null)
      {
        taskScheduler.unlockEntry(taskEntryDN, lock);
        lock.unlock();
      }
    }
  }
@@ -946,13 +938,11 @@

    // We only need to grab the entry-level lock if we don't already hold the
    // broader scheduler lock.
    boolean needLock = (! taskScheduler.holdsSchedulerLock());
    Lock lock = null;
    if (needLock)
    DNLock lock = null;
    if (!taskScheduler.holdsSchedulerLock())
    {
      lock = taskScheduler.writeLockEntry(taskEntryDN);
    }

    try
    {
      StringBuilder buffer = new StringBuilder();
@@ -1008,9 +998,9 @@
    }
    finally
    {
      if (needLock)
      if (lock != null)
      {
        taskScheduler.unlockEntry(taskEntryDN, lock);
        lock.unlock();
      }
    }
  }

 opendj-server-legacy/src/main/java/org/opends/server/backends/task/TaskBackend.java

@@ -35,7 +35,6 @@
import java.net.InetAddress;
import java.security.MessageDigest;
import java.util.*;
import java.util.concurrent.locks.Lock;
import java.util.zip.Deflater;
import java.util.zip.ZipEntry;
import java.util.zip.ZipInputStream;
@@ -59,6 +58,7 @@
import org.opends.server.config.ConfigEntry;
import org.opends.server.core.*;
import org.opends.server.types.*;
import org.opends.server.types.LockManager.DNLock;
import org.opends.server.util.DynamicConstants;
import org.opends.server.util.LDIFException;
import org.opends.server.util.LDIFReader;
@@ -413,8 +413,7 @@
      return null;
    }

    Lock lock = taskScheduler.readLockEntry(entryDN);

    DNLock lock = taskScheduler.readLockEntry(entryDN);
    try
    {
      if (entryDN.equals(taskRootDN))
@@ -453,7 +452,7 @@
    }
    finally
    {
      taskScheduler.unlockEntry(entryDN, lock);
      lock.unlock();
    }
  }

@@ -584,11 +583,10 @@
      ModifyOperation modifyOperation) throws DirectoryException
  {
    DN entryDN = newEntry.getName();

    Lock entryLock = null;
    DNLock entryLock = null;
    if (! taskScheduler.holdsSchedulerLock())
    {
      entryLock = LockManager.lockWrite(entryDN);
      entryLock = DirectoryServer.getLockManager().tryWriteLockEntry(entryDN);
      if (entryLock == null)
      {
        throw new DirectoryException(ResultCode.BUSY,
@@ -707,7 +705,7 @@
    {
      if (entryLock != null)
      {
        LockManager.unlock(entryDN, entryLock);
        entryLock.unlock();
      }
    }
  }
@@ -868,8 +866,7 @@
      }
      else if (parentDN.equals(scheduledTaskParentDN))
      {
        Lock lock = taskScheduler.readLockEntry(baseDN);

        DNLock lock = taskScheduler.readLockEntry(baseDN);
        try
        {
          Entry e = taskScheduler.getScheduledTaskEntry(baseDN);
@@ -890,13 +887,12 @@
        }
        finally
        {
          taskScheduler.unlockEntry(baseDN, lock);
          lock.unlock();
        }
      }
      else if (parentDN.equals(recurringTaskParentDN))
      {
        Lock lock = taskScheduler.readLockEntry(baseDN);

        DNLock lock = taskScheduler.readLockEntry(baseDN);
        try
        {
          Entry e = taskScheduler.getRecurringTaskEntry(baseDN);
@@ -917,7 +913,7 @@
        }
        finally
        {
          taskScheduler.unlockEntry(baseDN, lock);
          lock.unlock();
        }
      }
      else

 opendj-server-legacy/src/main/java/org/opends/server/backends/task/TaskScheduler.java

@@ -35,7 +35,6 @@
import java.io.IOException;
import java.util.*;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

import org.forgerock.i18n.LocalizableMessage;
@@ -45,6 +44,7 @@
import org.opends.server.core.SearchOperation;
import org.forgerock.i18n.slf4j.LocalizedLogger;
import org.opends.server.types.*;
import org.opends.server.types.LockManager.DNLock;
import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.ResultCode;
import org.opends.server.util.LDIFException;
@@ -1553,22 +1553,20 @@
   *
   * @return  The write lock that has been acquired for the entry.
   */
  Lock writeLockEntry(DN entryDN)
  DNLock writeLockEntry(DN entryDN)
  {
    Lock lock = LockManager.lockWrite(entryDN);
    DNLock lock = null;
    while (lock == null)
    {
      lock = LockManager.lockWrite(entryDN);
      lock = DirectoryServer.getLockManager().tryWriteLockEntry(entryDN);
    }

    return lock;
  }



  /**
   * Attempts to acquire a read lock on the specified entry, trying up to five
   * times before failing.
   * Attempts to acquire a read lock on the specified entry.
   *
   * @param  entryDN  The DN of the entry for which to acquire the read lock.
   *
@@ -1576,32 +1574,14 @@
   *
   * @throws  DirectoryException  If the read lock cannot be acquired.
   */
  Lock readLockEntry(DN entryDN)
       throws DirectoryException
  DNLock readLockEntry(DN entryDN) throws DirectoryException
  {
    final Lock lock = LockManager.lockRead(entryDN);
    if (lock == null)
    {
      throw new DirectoryException(ResultCode.BUSY,
          ERR_BACKEND_CANNOT_LOCK_ENTRY.get(entryDN));
    }
    else
    final DNLock lock = DirectoryServer.getLockManager().tryReadLockEntry(entryDN);
    if (lock != null)
    {
      return lock;
    }
  }



  /**
   * Releases the lock held on the specified entry.
   *
   * @param  entryDN  The DN of the entry for which the lock is held.
   * @param  lock     The lock held on the entry.
   */
  void unlockEntry(DN entryDN, Lock lock)
  {
    LockManager.unlock(entryDN, lock);
    throw new DirectoryException(ResultCode.BUSY, ERR_BACKEND_CANNOT_LOCK_ENTRY.get(entryDN));
  }


@@ -1670,8 +1650,7 @@
      for (Task t : tasks.values())
      {
        DN taskEntryDN = t.getTaskEntryDN();
        Lock lock = readLockEntry(taskEntryDN);

        DNLock lock = readLockEntry(taskEntryDN);
        try
        {
          Entry e = t.getTaskEntry().duplicate(true);
@@ -1682,7 +1661,7 @@
        }
        finally
        {
          unlockEntry(taskEntryDN, lock);
          lock.unlock();
        }
      }

@@ -1818,8 +1797,7 @@
      for (RecurringTask rt : recurringTasks.values())
      {
        DN recurringTaskEntryDN = rt.getRecurringTaskEntryDN();
        Lock lock = readLockEntry(recurringTaskEntryDN);

        DNLock lock = readLockEntry(recurringTaskEntryDN);
        try
        {
          Entry e = rt.getRecurringTaskEntry().duplicate(true);
@@ -1830,7 +1808,7 @@
        }
        finally
        {
          unlockEntry(recurringTaskEntryDN, lock);
          lock.unlock();
        }
      }


 opendj-server-legacy/src/main/java/org/opends/server/core/DirectoryServer.java

@@ -801,6 +801,9 @@
  /** The Disk Space Monitor */
  private DiskSpaceMonitor diskSpaceMonitor;

  /** The lock manager which will be used for coordinating access to LDAP entries */
  private final LockManager lockManager = new LockManager();

  /**
   * The maximum size that internal buffers will be allowed to grow to until
   * they are trimmed.
@@ -7208,7 +7211,6 @@
    TimeThread.start();

    getNewInstance(config);
    LockManager.reinitializeLockTable();
    directoryServer.bootstrapServer();
    directoryServer.initializeConfiguration();
    return directoryServer;
@@ -8491,5 +8493,15 @@
    return directoryServer.maxInternalBufferSize;
  }

  /**
   * Returns the lock manager which will be used for coordinating access to LDAP entries.
   *
   * @return the lock manager which will be used for coordinating access to LDAP entries.
   */
  public static LockManager getLockManager()
  {
    return directoryServer.lockManager;
  }

}


 opendj-server-legacy/src/main/java/org/opends/server/extensions/FIFOEntryCache.java

@@ -49,7 +49,6 @@
import org.opends.server.types.DN;
import org.opends.server.types.Entry;
import org.opends.server.types.InitializationException;
import org.opends.server.types.LockManager;
import org.opends.server.types.SearchFilter;
import org.opends.server.util.ServerConstants;

@@ -117,7 +116,7 @@
  private FIFOEntryCacheCfg registeredConfiguration;

  /** The maximum length of time to try to obtain a lock before giving up. */
  private long lockTimeout = LockManager.DEFAULT_TIMEOUT;
  private long lockTimeout = 2000;

  /** Creates a new instance of this FIFO entry cache. */
  public FIFOEntryCache()
@@ -850,7 +849,7 @@
   * @return  <CODE>true</CODE> if configuration is acceptable,
   *          or <CODE>false</CODE> otherwise.
   */
  public boolean processEntryCacheConfig(
  private boolean processEntryCacheConfig(
      FIFOEntryCacheCfg                   configuration,
      boolean                             applyChanges,
      EntryCacheCommon.ConfigErrorHandler errorHandler

 opendj-server-legacy/src/main/java/org/opends/server/extensions/PasswordModifyExtendedOperation.java

@@ -36,7 +36,6 @@

import java.io.IOException;
import java.util.*;
import java.util.concurrent.locks.Lock;

import org.forgerock.i18n.LocalizableMessage;
import org.forgerock.i18n.LocalizableMessageBuilder;
@@ -65,6 +64,7 @@
import org.opends.server.schema.AuthPasswordSyntax;
import org.opends.server.schema.UserPasswordSyntax;
import org.opends.server.types.*;
import org.opends.server.types.LockManager.DNLock;

/**
 * This class implements the password modify extended operation defined in RFC
@@ -253,10 +253,9 @@

    // See if a user identity was provided.  If so, then try to resolve it to
    // an actual user.
    DN    userDN    = null;
    DN userDN = null;
    Entry userEntry = null;
    Lock  userLock  = null;

    DNLock userLock = null;
    try
    {
      if (userIdentity == null)
@@ -272,16 +271,7 @@
          return;
        }

        // Retrieve a write lock on that user's entry.
        userDN = requestorEntry.getName();
        userLock = LockManager.lockWrite(userDN);
        if (userLock == null)
        {
          operation.setResultCode(ResultCode.BUSY);
          operation.appendErrorMessage(ERR_EXTOP_PASSMOD_CANNOT_LOCK_USER_ENTRY.get(userDN));
          return;
        }

        userEntry = requestorEntry;
      }
      else
@@ -341,11 +331,13 @@
            return;
          }
        }
        // the userIdentity provided does not follow Authorization Identity form. RFC3062 declaration "may or may
        // not be an LDAPDN" allows for pretty much anything in that field. we gonna try to parse it as DN first
        // then if that fails as user ID.
        else
        {
          /*
           * the userIdentity provided does not follow Authorization Identity form. RFC3062
           * declaration "may or may not be an LDAPDN" allows for pretty much anything in that
           * field. we gonna try to parse it as DN first then if that fails as user ID.
           */
          try
          {
            userDN = DN.valueOf(authzIDStr);
@@ -384,6 +376,14 @@
        }
      }

      userLock = DirectoryServer.getLockManager().tryWriteLockEntry(userDN);
      if (userLock == null)
      {
        operation.setResultCode(ResultCode.BUSY);
        operation.appendErrorMessage(ERR_EXTOP_PASSMOD_CANNOT_LOCK_USER_ENTRY.get(userDN));
        return;
      }

      // At this point, we should have the user entry.  Get the associated password policy.
      PasswordPolicyState pwPolicyState;
      try
@@ -908,7 +908,7 @@
    {
      if (userLock != null)
      {
        LockManager.unlock(userDN, userLock);
        userLock.unlock();
      }
    }
  }

 opendj-server-legacy/src/main/java/org/opends/server/tasks/AddSchemaFileTask.java

@@ -30,7 +30,6 @@
import java.util.LinkedList;
import java.util.List;
import java.util.TreeSet;
import java.util.concurrent.locks.Lock;

import org.forgerock.i18n.LocalizableMessage;
import org.opends.server.admin.std.server.SynchronizationProviderCfg;
@@ -43,10 +42,13 @@
import org.opends.server.core.SchemaConfigManager;
import org.forgerock.i18n.slf4j.LocalizedLogger;
import org.opends.server.types.*;
import org.opends.server.types.LockManager.DNLock;
import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.ResultCode;

import static org.opends.messages.TaskMessages.*;
import static org.opends.server.config.ConfigConstants.*;
import static org.opends.server.core.DirectoryServer.getSchemaDN;
import static org.opends.server.util.ServerConstants.*;
import static org.opends.server.util.StaticUtils.*;

@@ -179,11 +181,10 @@
  {
    // Obtain a write lock on the server schema so that we can be sure nothing
    // else tries to write to it at the same time.
    DN schemaDN = DirectoryServer.getSchemaDN();
    final Lock schemaLock = LockManager.lockWrite(schemaDN);
    final DNLock schemaLock = DirectoryServer.getLockManager().tryWriteLockEntry(getSchemaDN());
    if (schemaLock == null)
    {
      logger.error(ERR_TASK_ADDSCHEMAFILE_CANNOT_LOCK_SCHEMA, schemaDN);
      logger.error(ERR_TASK_ADDSCHEMAFILE_CANNOT_LOCK_SCHEMA, getSchemaDN());
      return TaskState.STOPPED_BY_ERROR;
    }

@@ -267,7 +268,7 @@
    }
    finally
    {
      LockManager.unlock(schemaDN, schemaLock);
      schemaLock.unlock();
    }
  }
}

 opendj-server-legacy/src/main/java/org/opends/server/types/DirectoryEnvironmentConfig.java

@@ -1117,158 +1117,6 @@



  /**
   * Retrieves the concurrency level for the Directory Server lock
   * table.
   *
   * @return  The concurrency level for the Directory Server lock
   *          table.
   */
  public int getLockManagerConcurrencyLevel()
  {
    String levelStr =
         getProperty(PROPERTY_LOCK_MANAGER_CONCURRENCY_LEVEL);
    if (levelStr == null)
    {
      return LockManager.DEFAULT_CONCURRENCY_LEVEL;
    }

    int concurrencyLevel;
    try
    {
      concurrencyLevel = Integer.parseInt(levelStr);
    }
    catch (Exception e)
    {
      return LockManager.DEFAULT_CONCURRENCY_LEVEL;
    }

    if (concurrencyLevel <= 0)
    {
      return LockManager.DEFAULT_CONCURRENCY_LEVEL;
    }
    else
    {
      return concurrencyLevel;
    }
  }



  /**
   * Specifies the concurrency level for the Directory Server lock
   * table.  This should be set to the maximum number of threads that
   * could attempt to interact with the lock table at any given time.
   *
   * @param  concurrencyLevel  The concurrency level for the Directory
   *                           Server lock manager.
   *
   * @return  The previously-configured concurrency level.  If there
   *          was no previously-configured value, then the default
   *          concurrency level will be returned.
   *
   * @throws  InitializationException  If the Directory Server is
   *                                   already running or there is a
   *                                   problem with the provided
   *                                   concurrency level value.
   */
  public int setLockManagerConcurrencyLevel(int concurrencyLevel)
         throws InitializationException
  {
    checkServerIsRunning();

    if (concurrencyLevel <= 0)
    {
        throw new InitializationException(
                ERR_DIRCFG_INVALID_CONCURRENCY_LEVEL.get(
                        concurrencyLevel));
    }

    String concurrencyStr =
         setProperty(PROPERTY_LOCK_MANAGER_CONCURRENCY_LEVEL,
                     String.valueOf(concurrencyLevel));
    if (concurrencyStr == null)
    {
      return LockManager.DEFAULT_CONCURRENCY_LEVEL;
    }
    else
    {
      try
      {
        return Integer.parseInt(concurrencyStr);
      }
      catch (Exception e)
      {
        return LockManager.DEFAULT_CONCURRENCY_LEVEL;
      }
    }
  }

  /**
   * Retrieves whether a fair ordering should be used for the lock
   * manager.
   *
   * @return True if fair orderin should be used or false otherwise
   */
  public boolean getLockManagerFairOrdering()
  {
    String sizeStr = getProperty(PROPERTY_LOCK_MANAGER_FAIR_ORDERING);
    if (sizeStr == null)
    {
      return LockManager.DEFAULT_FAIR_ORDERING;
    }
    else
    {
      try
      {
        return Boolean.parseBoolean(sizeStr);
      }
      catch (Exception e)
      {
        return LockManager.DEFAULT_FAIR_ORDERING;
      }
    }
  }

  /**
   * Specifies whether a fair ordering should be used for the lock
   * manager.
   *
   * @param  fairOrdering  {@code true} if fair ordering should be
   *                       used, or {@code false} if not.
   *
   * @return  The previously-configured setting for fair ordering.  If
   *          there was no previously-configured value, then the
   *          default initial setting will be returned.
   *
   * @throws  InitializationException  If the Directory Server is
   *                                   already running.
   */
  public boolean setLockManagerFairOrdering(boolean fairOrdering)
         throws InitializationException
  {
    checkServerIsRunning();

    String fairOrderingStr =
         setProperty(PROPERTY_LOCK_MANAGER_FAIR_ORDERING,
                     String.valueOf(fairOrdering));
    if (fairOrderingStr == null)
    {
      return LockManager.DEFAULT_FAIR_ORDERING;
    }
    else
    {
      try
      {
        return Boolean.parseBoolean(fairOrderingStr);
      }
      catch (Exception e)
      {
        return LockManager.DEFAULT_FAIR_ORDERING;
      }
    }
  }

  /** Throws an exception if server is running and it is not allowed. */
  private void checkServerIsRunning() throws InitializationException
  {
@@ -1278,84 +1126,4 @@
              ERR_DIRCFG_SERVER_ALREADY_RUNNING.get());
    }
  }

  /**
   * Retrieves the initial table size for the server lock table.  This
   * can be used to ensure that the lock table has the appropriate
   * size for the expected number of locks that will be held at any
   * given time.
   *
   * @return  The initial table size for the server lock table.
   */
  public int getLockManagerTableSize()
  {
    String sizeStr = getProperty(PROPERTY_LOCK_MANAGER_TABLE_SIZE);
    if (sizeStr == null)
    {
      return LockManager.DEFAULT_INITIAL_TABLE_SIZE;
    }
    else
    {
      try
      {
        return Integer.parseInt(sizeStr);
      }
      catch (Exception e)
      {
        return LockManager.DEFAULT_INITIAL_TABLE_SIZE;
      }
    }
  }



  /**
   * Specifies the initial table size for the server lock table.  This
   * can be used to ensure taht the lock table has the appropriate
   * size for the expected number of locks that will be held at any
   * given time.
   *
   * @param  lockTableSize  The initial table size for the server lock
   *                        table.
   *
   * @return  The previously-configured initial lock table size.  If
   *          there was no previously-configured value, then the
   *          default initial table size will be returned.
   *
   * @throws  InitializationException  If the Directory Server is
   *                                   already running or there is a
   *                                   problem with the provided
   *                                   initial table size.
   */
  public int setLockManagerTableSize(int lockTableSize)
         throws InitializationException
  {
    checkServerIsRunning();

    if (lockTableSize <= 0)
    {
        throw new InitializationException(
                ERR_DIRCFG_INVALID_LOCK_TABLE_SIZE.get(
                        lockTableSize));
    }

    String tableSizeStr =
         setProperty(PROPERTY_LOCK_MANAGER_TABLE_SIZE,
                     String.valueOf(lockTableSize));
    if (tableSizeStr == null)
    {
      return LockManager.DEFAULT_INITIAL_TABLE_SIZE;
    }
    else
    {
      try
      {
        return Integer.parseInt(tableSizeStr);
      }
      catch (Exception e)
      {
        return LockManager.DEFAULT_INITIAL_TABLE_SIZE;
      }
    }
  }
}

 opendj-server-legacy/src/main/java/org/opends/server/types/LockManager.java

@@ -21,629 +21,517 @@
 * CDDL HEADER END
 *
 *
 *      Copyright 2006-2008 Sun Microsystems, Inc.
 *      Portions Copyright 2013-2015 ForgeRock AS.
 *      Copyright 2015 ForgeRock AS.
 */
package org.opends.server.types;

import java.util.concurrent.ConcurrentHashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

import org.opends.server.core.DirectoryServer;
import org.forgerock.i18n.slf4j.LocalizedLogger;
import org.forgerock.util.Reject;

/**
 * This class defines a Directory Server component that can keep track
 * of all locks needed throughout the Directory Server.  It is
 * intended primarily for entry locking but support for other types of
 * objects might be added in the future.
 * A lock manager coordinates directory update operations so that the DIT structure remains in a
 * consistent state, as well as providing repeatable read isolation. When accessing entries
 * components need to ensure that they have the appropriate lock:
 * <ul>
 * <li>repeatable reads: repeatable read isolation is rarely needed in practice, since all backend
 * reads are guaranteed to be performed with read-committed isolation, which is normally sufficient.
 * Specifically, read-only operations such as compare and search do not require any additional
 * locking. If repeatable read isolation is required then lock the entry using
 * {@link #tryReadLockEntry(DN)}
 * <li>modifying an entry: acquire an entry write-lock for the target entry using
 * {@link #tryWriteLockEntry(DN)}. Updates are typically performed using a read-modify-write cycle,
 * so the write lock should be acquired before performing the initial read in order to ensure
 * consistency
 * <li>adding an entry: client code must acquire an entry write-lock for the target entry using
 * {@link #tryWriteLockEntry(DN)}. The parent entry will automatically be protected from deletion by
 * an implicit subtree read lock on the parent
 * <li>deleting an entry: client code must acquire a subtree write lock for the target entry using
 * {@link #tryWriteLockSubtree(DN)}
 * <li>renaming an entry: client code must acquire a subtree write lock for the old entry, and a
 * subtree write lock for the new entry using {@link #tryWriteLockSubtree(DN)}. Care should be taken
 * to avoid deadlocks, e.g. by locking the DN which sorts first.
 * </ul>
 * In addition, backend implementations may choose to use their own lock manager for enforcing
 * atomicity and isolation. This is typically the case for backends which cannot take advantage of
 * atomicity guarantees provided by an underlying DB (the task backend is one such example).
 * <p>
 * <b>Implementation Notes</b>
 * <p>
 * The lock table is conceptually a cache of locks keyed on DN, i.e. a {@code Map<DN, DNLock>}.
 * Locks must be kept in the cache while they are locked, but may be removed once they are no longer
 * locked by any threads. Locks are represented using a pair of read-write locks: the first lock is
 * the "subtree" lock and the second is the "entry" lock.
 * <p>
 * In order to lock an entry for read or write a <b>subtree</b> read lock is first acquired on each
 * of the parent entries from the root DN down to the immediate parent of the entry to be locked.
 * Then the appropriate read or write <b>entry</b> lock is acquired for the target entry. Subtree
 * write locking is performed by acquiring a <b>subtree</b> read lock on each of the parent entries
 * from the root DN down to the immediate parent of the subtree to be locked. Then a <b>subtree</b>
 * write lock is acquired for the target subtree.
 * <p>
 * The lock table itself is not represented using a {@code ConcurrentHashMap} because the JDK6/7
 * APIs do not provide the ability to atomically add-and-lock or unlock-and-remove locks (this
 * capability is provided in JDK8). Instead, we provide our own implementation comprising of a fixed
 * number of buckets, a bucket being a {@code LinkedList} of {@code DNLock}s. In addition, it is
 * important to be able to efficiently iterate up and down a chain of hierarchically related locks,
 * so each lock maintains a reference to its parent lock. Modern directories tend to have a flat
 * structure so it is also important to avoid contention on "hot" parent DNs. Typically, a lock
 * attempt against a DN will involve a cache miss for the target DN and a cache hit for the parent,
 * but the parent will be the same parent for all lock requests, resulting in a lot of contention on
 * the same lock bucket. To avoid this the lock manager maintains a small-thread local cache of
 * locks, so that parent locks can be acquired using a lock-free algorithm.
 * <p>
 * Since the thread local cache may reference locks which are not actively locked by anyone, a
 * reference counting mechanism is used in order to prevent cached locks from being removed from the
 * underlying lock table. The reference counting mechanism is also used for references between a
 * lock and its parent lock. To summarize, locking a DN involves the following steps:
 * <ul>
 * <li>get the lock from the thread local cache. If the lock was not in the thread local cache then
 * try fetching it from the lock table:
 * <ul>
 * <li><i>found</i> - store it in the thread local cache and bump the reference count
 * <li><i>not found</i> - create a new lock. First fetch the parent lock using the same process,
 * i.e. looking in the thread local cache, etc. Then create a new lock referencing the parent lock
 * (bumps the reference count for the parent lock), and store it in the lock table and the thread
 * local cache with a reference count of 1.
 * </ul>
 * <li>return the lock to the application and increment its reference count since the application
 * now also has a reference to the lock.
 * </ul>
 * Locks are dereferenced when they are unlocked, when they are evicted from a thread local cache,
 * and when a child lock's reference count reaches zero. A lock is completely removed from the lock
 * table once its reference count reaches zero.
 */
@org.opends.server.types.PublicAPI(
     stability=org.opends.server.types.StabilityLevel.UNCOMMITTED,
     mayInstantiate=false,
     mayExtend=false,
     mayInvoke=true)
@org.opends.server.types.PublicAPI(stability = org.opends.server.types.StabilityLevel.UNCOMMITTED,
    mayInstantiate = false, mayExtend = false, mayInvoke = true)
public final class LockManager
{
  private static final LocalizedLogger logger = LocalizedLogger.getLoggerForThisClass();

  /**
   * The default setting for the use of fair ordering locks.
   * A lock on an entry or subtree. A lock can only be unlocked once.
   */
  public static final boolean DEFAULT_FAIR_ORDERING = true;

  /**
   * The default initial size to use for the lock table.
   */
  public static final int DEFAULT_INITIAL_TABLE_SIZE = 64;



  /**
   * The default concurrency level to use for the lock table.
   */
  public static final int DEFAULT_CONCURRENCY_LEVEL = 32;



  /**
   * The default load factor to use for the lock table.
   */
  public static final float DEFAULT_LOAD_FACTOR = 0.75F;



  /**
   * The default length of time in milliseconds to wait while
   * attempting to acquire a read or write lock.
   */
  public static final long DEFAULT_TIMEOUT = 9000;



  /** The set of entry locks that the server knows about. */
  private static
       ConcurrentHashMap<DN,ReentrantReadWriteLock> lockTable;

  /** Whether fair ordering should be used on the locks. */
  private static boolean fair;



  /** Initialize the lock table. */
  static
  public final class DNLock
  {
    DirectoryEnvironmentConfig environmentConfig =
         DirectoryServer.getEnvironmentConfig();
    lockTable = new ConcurrentHashMap<DN,ReentrantReadWriteLock>(
         environmentConfig.getLockManagerTableSize(),
         DEFAULT_LOAD_FACTOR,
         environmentConfig.getLockManagerConcurrencyLevel());
    fair = environmentConfig.getLockManagerFairOrdering();
  }
    private final DNLockHolder lock;
    private final Lock subtreeLock;
    private final Lock entryLock;
    private boolean isLocked = true;



  /**
   * Recreates the lock table.  This should be called only in the
   * case that the Directory Server is in the process of an in-core
   * restart because it will destroy the existing lock table.
   */
  public static synchronized void reinitializeLockTable()
  {
    ConcurrentHashMap<DN,ReentrantReadWriteLock> oldTable = lockTable;

    DirectoryEnvironmentConfig environmentConfig =
         DirectoryServer.getEnvironmentConfig();
    lockTable = new ConcurrentHashMap<DN,ReentrantReadWriteLock>(
         environmentConfig.getLockManagerTableSize(),
         DEFAULT_LOAD_FACTOR,
         environmentConfig.getLockManagerConcurrencyLevel());

    if  (! oldTable.isEmpty())
    private DNLock(final DNLockHolder lock, final Lock subtreeLock, final Lock entryLock)
    {
      for (DN dn : oldTable.keySet())
      {
        try
        {
          ReentrantReadWriteLock lock = oldTable.get(dn);
          if (lock.isWriteLocked())
          {
            logger.trace("Found stale write lock on %s", dn);
          }
          else if (lock.getReadLockCount() > 0)
          {
            logger.trace("Found stale read lock on %s", dn);
          }
          else
          {
            logger.trace("Found stale unheld lock on %s", dn);
          }
        }
        catch (Exception e)
        {
          logger.traceException(e);
        }
      }

      oldTable.clear();
      this.lock = lock;
      this.subtreeLock = subtreeLock;
      this.entryLock = entryLock;
    }

    fair = environmentConfig.getLockManagerFairOrdering();
    @Override
    public String toString()
    {
      return lock.toString();
    }

    /**
     * Unlocks this lock and releases any blocked threads.
     *
     * @throws IllegalStateException
     *           If this lock has already been unlocked.
     */
    public void unlock()
    {
      if (!isLocked)
      {
        throw new IllegalStateException("Already unlocked");
      }
      lock.releaseParentSubtreeReadLock();
      subtreeLock.unlock();
      entryLock.unlock();
      dereference(lock);
      isLocked = false;
    }

    // For unit testing.
    int refCount()
    {
      return lock.refCount.get();
    }
  }



  /**
   * Attempts to acquire a read lock on the specified entry.  It will
   * succeed only if the write lock is not already held.  If any
   * blocking is required, then this call will fail rather than block.
   *
   * @param  entryDN  The DN of the entry for which to obtain the read
   *                  lock.
   *
   * @return  The read lock that was acquired, or {@code null} if it
   *          was not possible to obtain a read lock for some reason.
   * Lock implementation
   */
  private static Lock tryLockRead(DN entryDN)
  private final class DNLockHolder
  {
    ReentrantReadWriteLock entryLock =
        new ReentrantReadWriteLock(fair);
    Lock readLock = entryLock.readLock();
    readLock.lock();
    private final AtomicInteger refCount = new AtomicInteger();
    private final DNLockHolder parent;
    private final DN dn;
    private final int dnHashCode;
    private final ReentrantReadWriteLock subtreeLock = new ReentrantReadWriteLock();
    private final ReentrantReadWriteLock entryLock = new ReentrantReadWriteLock();

    ReentrantReadWriteLock existingLock =
         lockTable.putIfAbsent(entryDN, entryLock);
    if (existingLock == null)
    DNLockHolder(final DNLockHolder parent, final DN dn, final int dnHashCode)
    {
      return readLock;
      this.parent = parent;
      this.dn = dn;
      this.dnHashCode = dnHashCode;
    }
    else

    @Override
    public String toString()
    {
      // There's a lock in the table, but it could potentially be
      // unheld.  We'll do an unsafe check to see whether it might be
      // held and if so then fail to acquire the lock.
      if (existingLock.isWriteLocked())
      {
        readLock.unlock();
        return null;
      }
      return "\"" + dn + "\" : " + refCount;
    }

      // We will never remove a lock from the table without holding
      // its monitor.  Since there's already a lock in the table, then
      // get its monitor and try to acquire the lock.  This should
      // prevent the owner from releasing the lock and removing it
      // from the table before it can be acquired by another thread.
      synchronized (existingLock)
    /**
     * Unlocks the subtree read lock from the parent of this lock up to the root.
     */
    void releaseParentSubtreeReadLock()
    {
      for (DNLockHolder lock = parent; lock != null; lock = lock.parent)
      {
        ReentrantReadWriteLock existingLock2 =
             lockTable.putIfAbsent(entryDN, entryLock);
        if (existingLock2 == null)
        {
          return readLock;
        }
        else if (existingLock == existingLock2)
        {
          // We were able to synchronize on the lock's monitor while
          // the lock was still in the table.  Try to acquire it now
          // (which will succeed if the lock isn't held by anything)
          // and either return it or return null.
          readLock.unlock();
          readLock = existingLock.readLock();

          try
          {
            if (readLock.tryLock(0, TimeUnit.SECONDS))
            {
              return readLock;
            }
            else
            {
              return null;
            }
          }
          catch(InterruptedException ie)
          {
            // This should never happen. Just return null
            return null;
          }
        }
        else
        {
          // If this happens, then it means that while we were waiting
          // the existing lock was unlocked and removed from the table
          // and a new one was created and added to the table.  This
          // is more trouble than it's worth, so return null.
          readLock.unlock();
          return null;
        }
        lock.subtreeLock.readLock().unlock();
      }
    }
  }



  /**
   * Attempts to acquire a read lock for the specified entry.
   * Multiple threads can hold the read lock concurrently for an entry
   * as long as the write lock is held.  If the write lock is held,
   * then no other read or write locks will be allowed for that entry
   * until the write lock is released.  A default timeout will be used
   * for the lock.
   *
   * @param  entryDN  The DN of the entry for which to obtain the read
   *                  lock.
   *
   * @return  The read lock that was acquired, or {@code null} if it
   *          was not possible to obtain a read lock for some reason.
   */
  public static Lock lockRead(DN entryDN)
  {
    return lockRead(entryDN, DEFAULT_TIMEOUT);
  }



  /**
   * Attempts to acquire a read lock for the specified entry.
   * Multiple threads can hold the read lock concurrently for an entry
   * as long as the write lock is not held.  If the write lock is
   * held, then no other read or write locks will be allowed for that
   * entry until the write lock is released.
   *
   * @param  entryDN  The DN of the entry for which to obtain the read
   *                  lock.
   * @param  timeout  The maximum length of time in milliseconds to
   *                  wait for the lock before timing out.
   *
   * @return  The read lock that was acquired, or <CODE>null</CODE> if
   *          it was not possible to obtain a read lock for some
   *          reason.
   */
  private static Lock lockRead(DN entryDN, long timeout)
  {
    // First, try to get the lock without blocking.
    Lock readLock = tryLockRead(entryDN);
    if (readLock != null)
    DNLock tryReadLockEntry()
    {
      return readLock;
      return tryLock(subtreeLock.readLock(), entryLock.readLock());
    }

    ReentrantReadWriteLock entryLock =
        new ReentrantReadWriteLock(fair);
    readLock = entryLock.readLock();
    readLock.lock();

    ReentrantReadWriteLock existingLock =
         lockTable.putIfAbsent(entryDN, entryLock);
    if (existingLock == null)
    DNLock tryWriteLockEntry()
    {
      return readLock;
      return tryLock(subtreeLock.readLock(), entryLock.writeLock());
    }

    long surrenderTime = System.currentTimeMillis() + timeout;
    readLock.unlock();
    readLock = existingLock.readLock();
    DNLock tryWriteLockSubtree()
    {
      return tryLock(subtreeLock.writeLock(), entryLock.writeLock());
    }

    while (true)
    /**
     * Locks the subtree read lock from the root down to the parent of this lock.
     */
    private boolean tryAcquireParentSubtreeReadLock()
    {
      // First lock the parents of the parent.
      if (parent == null)
      {
        return true;
      }

      if (!parent.tryAcquireParentSubtreeReadLock())
      {
        return false;
      }

      // Then lock the parent of this lock
      if (tryLockWithTimeout(parent.subtreeLock.readLock()))
      {
        return true;
      }

      // Failed to grab the parent lock within the timeout, so roll-back the other locks.
      releaseParentSubtreeReadLock();
      return false;
    }

    private DNLock tryLock(final Lock subtreeLock, final Lock entryLock)
    {
      if (tryAcquireParentSubtreeReadLock())
      {
        if (tryLockWithTimeout(subtreeLock))
        {
          if (tryLockWithTimeout(entryLock))
          {
            return new DNLock(this, subtreeLock, entryLock);
          }
          subtreeLock.unlock();
        }
        releaseParentSubtreeReadLock();
      }
      // Failed to acquire all the necessary locks within the time out.
      dereference(this);
      return null;
    }

    private boolean tryLockWithTimeout(final Lock lock)
    {
      try
      {
        // See if we can acquire the lock while it's still in the
        // table within the given timeout.
        if (readLock.tryLock(timeout, TimeUnit.MILLISECONDS))
        return lock.tryLock(lockTimeout, lockTimeoutUnits);
      }
      catch (final InterruptedException e)
      {
        // Unable to handle interrupts here.
        Thread.currentThread().interrupt();
        return false;
      }
    }
  }

  private static final long DEFAULT_LOCK_TIMEOUT = 9;
  private static final TimeUnit DEFAULT_LOCK_TIMEOUT_UNITS = TimeUnit.SECONDS;
  private static final int MINIMUM_NUMBER_OF_BUCKETS = 64;
  private static final int THREAD_LOCAL_CACHE_SIZE = 8;

  private final int numberOfBuckets;
  private final LinkedList<DNLockHolder>[] lockTable;
  private final long lockTimeout;
  private final TimeUnit lockTimeoutUnits;

  // Avoid sub-classing in order to workaround class leaks in app servers.
  private final ThreadLocal<LinkedList<DNLockHolder>> threadLocalCache = new ThreadLocal<LinkedList<DNLockHolder>>();

  /**
   * Creates a new lock manager with a lock timeout of 9 seconds and an automatically chosen number
   * of lock table buckets based on the number of processors.
   */
  public LockManager()
  {
    this(DEFAULT_LOCK_TIMEOUT, DEFAULT_LOCK_TIMEOUT_UNITS);
  }

  /**
   * Creates a new lock manager with the specified lock timeout and an automatically chosen number
   * of lock table buckets based on the number of processors.
   *
   * @param lockTimeout
   *          The lock timeout.
   * @param lockTimeoutUnit
   *          The lock timeout units.
   */
  public LockManager(final long lockTimeout, final TimeUnit lockTimeoutUnit)
  {
    this(lockTimeout, lockTimeoutUnit, Runtime.getRuntime().availableProcessors() * 8);
  }

  /**
   * Creates a new lock manager with the provided configuration.
   *
   * @param lockTimeout
   *          The lock timeout.
   * @param lockTimeoutUnit
   *          The lock timeout units.
   * @param numberOfBuckets
   *          The number of buckets to use in the lock table. The minimum number of buckets is 64.
   */
  @SuppressWarnings("unchecked")
  public LockManager(final long lockTimeout, final TimeUnit lockTimeoutUnit, final int numberOfBuckets)
  {
    Reject.ifFalse(lockTimeout >= 0, "lockTimeout must be a non-negative integer");
    Reject.ifNull(lockTimeoutUnit, "lockTimeoutUnit must be non-null");
    Reject.ifFalse(numberOfBuckets > 0, "numberOfBuckets must be a positive integer");

    this.lockTimeout = lockTimeout;
    this.lockTimeoutUnits = lockTimeoutUnit;
    this.numberOfBuckets = getNumberOfBuckets(numberOfBuckets);
    this.lockTable = new LinkedList[this.numberOfBuckets];
    for (int i = 0; i < this.numberOfBuckets; i++)
    {
      this.lockTable[i] = new LinkedList<DNLockHolder>();
    }
  }

  @Override
  public String toString()
  {
    final StringBuilder builder = new StringBuilder();
    for (int i = 0; i < numberOfBuckets; i++)
    {
      final LinkedList<DNLockHolder> bucket = lockTable[i];
      synchronized (bucket)
      {
        for (final DNLockHolder lock : bucket)
        {
          synchronized (existingLock)
          builder.append(lock);
          builder.append('\n');
        }
      }
    }
    return builder.toString();
  }

  /**
   * Acquires the read lock for the specified entry. This method will block if the entry is already
   * write locked or if the entry, or any of its parents, have the subtree write lock taken.
   *
   * @param entry
   *          The entry whose read lock is required.
   * @return The lock, or {@code null} if the lock attempt timed out.
   */
  public DNLock tryReadLockEntry(final DN entry)
  {
    return acquireLockFromCache(entry).tryReadLockEntry();
  }

  /**
   * Acquires the write lock for the specified entry. This method will block if the entry is already
   * read or write locked or if the entry, or any of its parents, have the subtree write lock taken.
   *
   * @param entry
   *          The entry whose write lock is required.
   * @return The lock, or {@code null} if the lock attempt timed out.
   */
  public DNLock tryWriteLockEntry(final DN entry)
  {
    return acquireLockFromCache(entry).tryWriteLockEntry();
  }

  /**
   * Acquires the write lock for the specified subtree. This method will block if any entry or
   * subtree within the subtree is already read or write locked or if any of the parent entries of
   * the subtree have the subtree write lock taken.
   *
   * @param subtree
   *          The subtree whose write lock is required.
   * @return The lock, or {@code null} if the lock attempt timed out.
   */
  public DNLock tryWriteLockSubtree(final DN subtree)
  {
    return acquireLockFromCache(subtree).tryWriteLockSubtree();
  }

  // For unit testing.
  int getLockTableRefCountFor(final DN dn)
  {
    final int dnHashCode = dn.hashCode();
    final LinkedList<DNLockHolder> bucket = getBucket(dnHashCode);
    synchronized (bucket)
    {
      for (final DNLockHolder lock : bucket)
      {
        if (lock.dnHashCode == dnHashCode && lock.dn.equals(dn))
        {
          return lock.refCount.get();
        }
      }
      return -1;
    }
  }

  //For unit testing.
  int getThreadLocalCacheRefCountFor(final DN dn)
  {
    final LinkedList<DNLockHolder> cache = threadLocalCache.get();
    if (cache == null)
    {
      return -1;
    }
    final int dnHashCode = dn.hashCode();
    for (final DNLockHolder lock : cache)
    {
      if (lock.dnHashCode == dnHashCode && lock.dn.equals(dn))
      {
        return lock.refCount.get();
      }
    }
    return -1;
  }

  private DNLockHolder acquireLockFromCache(final DN dn)
  {
    LinkedList<DNLockHolder> cache = threadLocalCache.get();
    if (cache == null)
    {
      cache = new LinkedList<DNLockHolder>();
      threadLocalCache.set(cache);
    }
    return acquireLockFromCache0(dn, cache);
  }

  private DNLockHolder acquireLockFromCache0(final DN dn, final LinkedList<DNLockHolder> cache)
  {
    final int dnHashCode = dn.hashCode();
    DNLockHolder lock = removeLock(cache, dn, dnHashCode);
    if (lock == null)
    {
      lock = acquireLockFromLockTable(dn, dnHashCode, cache);
      if (cache.size() >= THREAD_LOCAL_CACHE_SIZE)
      {
        // Cache too big: evict oldest entry.
        dereference(cache.removeLast());
      }
    }
    cache.addFirst(lock); // optimize for LRU
    lock.refCount.incrementAndGet();
    return lock;
  }

  private DNLockHolder acquireLockFromLockTable(final DN dn, final int dnHashCode, final LinkedList<DNLockHolder> cache)
  {
    final LinkedList<DNLockHolder> bucket = getBucket(dnHashCode);
    synchronized (bucket)
    {
      DNLockHolder lock = removeLock(bucket, dn, dnHashCode);
      if (lock == null)
      {
        final DN parentDN = dn.parent();
        final DNLockHolder parentLock = parentDN != null ? acquireLockFromCache0(parentDN, cache) : null;
        lock = new DNLockHolder(parentLock, dn, dnHashCode);
      }
      bucket.addFirst(lock); // optimize for LRU
      lock.refCount.incrementAndGet();
      return lock;
    }
  }

  private void dereference(final DNLockHolder lock)
  {
    if (lock.refCount.decrementAndGet() <= 0)
    {
      final LinkedList<DNLockHolder> bucket = getBucket(lock.dnHashCode);
      synchronized (bucket)
      {
        // Double check: another thread could have acquired the lock since we decremented it to zero.
        if (lock.refCount.get() <= 0)
        {
          removeLock(bucket, lock.dn, lock.dnHashCode);
          if (lock.parent != null)
          {
            if (lockTable.get(entryDN) == existingLock)
            {
              // We acquired the lock within the timeout and it's
              // still in the lock table, so we're good to go.
              return readLock;
            }
            else
            {
              ReentrantReadWriteLock existingLock2 =
                   lockTable.putIfAbsent(entryDN, existingLock);
              if (existingLock2 == null)
              {
                // The lock had already been removed from the table,
                // but nothing had replaced it before we put it back,
                // so we're good to go.
                return readLock;
              }
              else
              {
                readLock.unlock();
                existingLock = existingLock2;
                readLock     = existingLock.readLock();
              }
            }
            dereference(lock.parent);
          }
        }
        else
        {
          // We couldn't acquire the lock before the timeout occurred,
          // so we have to fail.
          return null;
        }
      } catch (InterruptedException ie) {}


      // There are only two reasons we should be here:
      // - If the attempt to acquire the lock was interrupted.
      // - If we acquired the lock but it had already been removed
      //   from the table and another one had replaced it before we
      //   could put it back.
      // Our only recourse is to try again, but we need to reduce the
      // timeout to account for the time we've already waited.
      timeout = surrenderTime - System.currentTimeMillis();
      if (timeout <= 0)
      {
        return null;
      }
    }
  }



  /**
   * Attempts to acquire a write lock on the specified entry.  It will
   * succeed only if the lock is not already held.  If any blocking is
   * required, then this call will fail rather than block.
   *
   * @param  entryDN  The DN of the entry for which to obtain the
   *                  write lock.
   *
   * @return  The write lock that was acquired, or <CODE>null</CODE>
   *          if it was not possible to obtain a write lock for some
   *          reason.
   */
  private static Lock tryLockWrite(DN entryDN)
  private LinkedList<DNLockHolder> getBucket(final int dnHashCode)
  {
    ReentrantReadWriteLock entryLock =
        new ReentrantReadWriteLock(fair);
    Lock writeLock = entryLock.writeLock();
    writeLock.lock();
    return lockTable[dnHashCode & numberOfBuckets - 1];
  }

    ReentrantReadWriteLock existingLock =
         lockTable.putIfAbsent(entryDN, entryLock);
    if (existingLock == null)
  /*
   * Ensure that the number of buckets is a power of 2 in order to make it easier to map hash codes
   * to bucket indexes.
   */
  private int getNumberOfBuckets(final int buckets)
  {
    final int roundedNumberOfBuckets = Math.min(buckets, MINIMUM_NUMBER_OF_BUCKETS);
    int powerOf2 = 1;
    while (powerOf2 < roundedNumberOfBuckets)
    {
      return writeLock;
      powerOf2 <<= 1;
    }
    else
    {
      // There's a lock in the table, but it could potentially be
      // unheld.  We'll do an unsafe check to see whether it might be
      // held and if so then fail to acquire the lock.
      if ((existingLock.getReadLockCount() > 0) ||
          (existingLock.isWriteLocked()))
      {
        writeLock.unlock();
        return null;
      }
    return powerOf2;
  }

      // We will never remove a lock from the table without holding
      // its monitor.  Since there's already a lock in the table, then
      // get its monitor and try to acquire the lock.  This should
      // prevent the owner from releasing the lock and removing it
      // from the table before it can be acquired by another thread.
      synchronized (existingLock)
  private DNLockHolder removeLock(final LinkedList<DNLockHolder> lockList, final DN dn, final int dnHashCode)
  {
    final Iterator<DNLockHolder> iterator = lockList.iterator();
    while (iterator.hasNext())
    {
      final DNLockHolder lock = iterator.next();
      if (lock.dnHashCode == dnHashCode && lock.dn.equals(dn))
      {
        ReentrantReadWriteLock existingLock2 =
             lockTable.putIfAbsent(entryDN, entryLock);
        if (existingLock2 == null)
        {
          return writeLock;
        }
        else if (existingLock == existingLock2)
        {
          // We were able to synchronize on the lock's monitor while
          // the lock was still in the table.  Try to acquire it now
          // (which will succeed if the lock isn't held by anything)
          // and either return it or return null.
          writeLock.unlock();
          writeLock = existingLock.writeLock();
          try
          {
            if (writeLock.tryLock(0, TimeUnit.SECONDS))
            {
              return writeLock;
            }
            else
            {
              return null;
            }
          }
          catch(InterruptedException ie)
          {
            // This should never happen. Just return null
            return null;
          }
        }
        else
        {
          // If this happens, then it means that while we were waiting
          // the existing lock was unlocked and removed from the table
          // and a new one was created and added to the table.  This
          // is more trouble than it's worth, so return null.
          writeLock.unlock();
          return null;
        }
        // Found: remove the lock because it will be moved to the front of the list.
        iterator.remove();
        return lock;
      }
    }
  }



  /**
   * Attempts to acquire the write lock for the specified entry.  Only
   * a single thread may hold the write lock for an entry at any given
   * time, and during that time no read locks may be held for it.  A
   * default timeout will be used for the lock.
   *
   * @param  entryDN  The DN of the entry for which to obtain the
   *                  write lock.
   *
   * @return  The write lock that was acquired, or <CODE>null</CODE>
   *          if it was not possible to obtain a write lock for some
   *          reason.
   */
  public static Lock lockWrite(DN entryDN)
  {
    return lockWrite(entryDN, DEFAULT_TIMEOUT);
  }



  /**
   * Attempts to acquire the write lock for the specified entry.  Only
   * a single thread may hold the write lock for an entry at any given
   * time, and during that time no read locks may be held for it.
   *
   * @param  entryDN  The DN of the entry for which to obtain the
   *                  write lock.
   * @param  timeout  The maximum length of time in milliseconds to
   *                  wait for the lock before timing out.
   *
   * @return  The write lock that was acquired, or <CODE>null</CODE>
   *          if it was not possible to obtain a read lock for some
   *          reason.
   */
  private static Lock lockWrite(DN entryDN, long timeout)
  {
    // First, try to get the lock without blocking.
    Lock writeLock = tryLockWrite(entryDN);
    if (writeLock != null)
    {
      return writeLock;
    }

    ReentrantReadWriteLock entryLock =
        new ReentrantReadWriteLock(fair);
    writeLock = entryLock.writeLock();
    writeLock.lock();

    ReentrantReadWriteLock existingLock =
         lockTable.putIfAbsent(entryDN, entryLock);
    if (existingLock == null)
    {
      return writeLock;
    }

    long surrenderTime = System.currentTimeMillis() + timeout;
    writeLock.unlock();
    writeLock = existingLock.writeLock();

    while (true)
    {
      try
      {
        // See if we can acquire the lock while it's still in the
        // table within the given timeout.
        if (writeLock.tryLock(timeout, TimeUnit.MILLISECONDS))
        {
          synchronized (existingLock)
          {
            if (lockTable.get(entryDN) == existingLock)
            {
              // We acquired the lock within the timeout and it's
              // still in the lock table, so we're good to go.
              return writeLock;
            }
            else
            {
              ReentrantReadWriteLock existingLock2 =
                   lockTable.putIfAbsent(entryDN, existingLock);
              if (existingLock2 == null)
              {
                // The lock had already been removed from the table,
                // but nothing had replaced it before we put it back,
                // so we're good to go.
                return writeLock;
              }
              else
              {
                writeLock.unlock();
                existingLock  = existingLock2;
                writeLock     = existingLock.writeLock();
              }
            }
          }
        }
        else
        {
          // We couldn't acquire the lock before the timeout occurred,
          // so we have to fail.
          return null;
        }
      } catch (InterruptedException ie) {}


      // There are only two reasons we should be here:
      // - If the attempt to acquire the lock was interrupted.
      // - If we acquired the lock but it had already been removed
      //   from the table and another one had replaced it before we
      //   could put it back.
      // Our only recourse is to try again, but we need to reduce the
      // timeout to account for the time we've already waited.
      timeout = surrenderTime - System.currentTimeMillis();
      if (timeout <= 0)
      {
        return null;
      }
    }
  }



  /**
   * Releases a read or write lock held on the specified entry.
   *
   * @param  entryDN  The DN of the entry for which to release the
   *                  lock.
   * @param  lock     The read or write lock held for the entry.
   */
  public static void unlock(DN entryDN, Lock lock)
  {
    // Get the corresponding read-write lock from the lock table.
    ReentrantReadWriteLock existingLock = lockTable.get(entryDN);

    // it should never be null, if it is is then all we can do is
    // release the lock and return.
    lock.unlock();
    if (existingLock != null
        && !existingLock.hasQueuedThreads()
        && existingLock.getReadLockCount() <= 1)
    {
      synchronized (existingLock)
      {
        if (!existingLock.isWriteLocked()
            && existingLock.getReadLockCount() == 0)
        {
          // If there's nothing waiting on the lock,
          // then we can remove it from the table when we unlock it.
          lockTable.remove(entryDN, existingLock);
        }
      }
    }
  }



  /**
   * Removes any reference to the specified entry from the lock table.
   * This may be helpful if there is a case where a lock has been
   * orphaned somehow and must be removed before other threads may
   * acquire it.
   *
   * @param  entryDN  The DN of the entry for which to remove the lock
   *                  from the table.
   *
   * @return  The read write lock that was removed from the table, or
   *          {@code null} if nothing was in the table for the
   *          specified entry.  If a lock object is returned, it may
   *          be possible to get information about who was holding it.
   */
  public static ReentrantReadWriteLock destroyLock(DN entryDN)
  {
    return lockTable.remove(entryDN);
  }



  /**
   * Retrieves the number of entries currently held in the lock table.
   * Note that this may be an expensive operation.
   *
   * @return  The number of entries currently held in the lock table.
   */
  public static int lockTableSize()
  {
    return lockTable.size();
    return null;
  }
}


 opendj-server-legacy/src/main/java/org/opends/server/workflowelement/localbackend/LocalBackendAddOperation.java

@@ -22,7 +22,7 @@
 *
 *
 *      Copyright 2008-2010 Sun Microsystems, Inc.
 *      Portions Copyright 2011-2014 ForgeRock AS
 *      Portions Copyright 2011-2015 ForgeRock AS
 */
package org.opends.server.workflowelement.localbackend;

@@ -31,7 +31,6 @@
import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.locks.Lock;

import org.forgerock.i18n.LocalizableMessage;
import org.forgerock.i18n.LocalizableMessageBuilder;
@@ -71,7 +70,7 @@
import org.opends.server.types.DN;
import org.opends.server.types.DirectoryException;
import org.opends.server.types.Entry;
import org.opends.server.types.LockManager;
import org.opends.server.types.LockManager.DNLock;
import org.opends.server.types.ObjectClass;
import org.opends.server.types.Privilege;
import org.opends.server.types.RDN;
@@ -240,28 +239,14 @@
    // Check for a request to cancel this operation.
    checkIfCanceled(false);

    // Grab a read lock on the parent entry, if there is one. We need to do
    // this to ensure that the parent is not deleted or renamed while this add
    // is in progress, and we could also need it to check the entry against
    // a DIT structure rule.
    Lock entryLock = null;
    Lock parentLock = null;
    DN parentDN = null;

    // Grab a write lock on the target entry. We'll need to do this
    // eventually anyway, and we want to make sure that the two locks are
    // always released when exiting this method, no matter what. Since
    // the entry shouldn't exist yet, locking earlier than necessary
    // shouldn't cause a problem.
    final DNLock entryLock = DirectoryServer.getLockManager().tryWriteLockEntry(entryDN);
    try
    {
      parentDN = entryDN.getParentDNInSuffix();
      parentLock = lockParent(parentDN);

      // Check for a request to cancel this operation.
      checkIfCanceled(false);

      // Grab a write lock on the target entry. We'll need to do this
      // eventually anyway, and we want to make sure that the two locks are
      // always released when exiting this method, no matter what. Since
      // the entry shouldn't exist yet, locking earlier than necessary
      // shouldn't cause a problem.
      entryLock = LockManager.lockWrite(entryDN);
      if (entryLock == null)
      {
        setResultCode(ResultCode.BUSY);
@@ -269,6 +254,26 @@
        return;
      }

      DN parentDN = entryDN.getParentDNInSuffix();
      if (parentDN == null && !DirectoryServer.isNamingContext(entryDN))
      {
        if (entryDN.isRootDN())
        {
          // This is not fine.  The root DSE cannot be added.
          throw new DirectoryException(ResultCode.UNWILLING_TO_PERFORM, ERR_ADD_CANNOT_ADD_ROOT_DSE.get());
        }
        else
        {
          // The entry doesn't have a parent but isn't a suffix.  This is not
          // allowed.
          throw new DirectoryException(ResultCode.NO_SUCH_OBJECT, ERR_ADD_ENTRY_NOT_SUFFIX.get(entryDN));
        }
      }

      // Check for a request to cancel this operation.
      checkIfCanceled(false);


      // Invoke any conflict resolution processing that might be needed by the
      // synchronization provider.
      for (SynchronizationProvider<?> provider : DirectoryServer
@@ -520,32 +525,31 @@
    }
    finally
    {
      for (SynchronizationProvider<?> provider : DirectoryServer
          .getSynchronizationProviders())
      {
        try
        {
          provider.doPostOperation(this);
        }
        catch (DirectoryException de)
        {
          logger.traceException(de);

          logger.error(ERR_ADD_SYNCH_POSTOP_FAILED, getConnectionID(),
              getOperationID(), getExceptionMessage(de));
          setResponseData(de);
          break;
        }
      }

      if (entryLock != null)
      {
        LockManager.unlock(entryDN, entryLock);
        entryLock.unlock();
      }
      processSynchPostOperationPlugins();
    }
  }

      if (parentLock != null)


  private void processSynchPostOperationPlugins()
  {
    for (SynchronizationProvider<?> provider : DirectoryServer.getSynchronizationProviders())
    {
      try
      {
        LockManager.unlock(parentDN, parentLock);
        provider.doPostOperation(this);
      }
      catch (DirectoryException de)
      {
        logger.traceException(de);
        logger.error(ERR_ADD_SYNCH_POSTOP_FAILED, getConnectionID(),
            getOperationID(), getExceptionMessage(de));
        setResponseData(de);
        break;
      }
    }
  }
@@ -607,48 +611,6 @@
        ERR_ADD_AUTHZ_INSUFFICIENT_ACCESS_RIGHTS.get(entryDN));
  }

  /**
   * Acquire a read lock on the parent of the entry to add.
   *
   * @return  The acquired read lock.
   *
   * @throws  DirectoryException  If a problem occurs while attempting to
   *                              acquire the lock.
   */
  private Lock lockParent(DN parentDN) throws DirectoryException
  {
    if (parentDN != null)
    {
      final Lock parentLock = LockManager.lockRead(parentDN);
      if (parentLock == null)
      {
        throw newDirectoryException(parentDN, ResultCode.BUSY,
            ERR_ADD_CANNOT_LOCK_PARENT.get(entryDN, parentDN));
      }
      return parentLock;
    }

    // Either this entry is a suffix or doesn't belong in the directory.
    if (DirectoryServer.isNamingContext(entryDN))
    {
      // This is fine.  This entry is one of the configured suffixes.
      return null;
    }
    else if (entryDN.isRootDN())
    {
      // This is not fine.  The root DSE cannot be added.
      throw new DirectoryException(ResultCode.UNWILLING_TO_PERFORM,
          ERR_ADD_CANNOT_ADD_ROOT_DSE.get());
    }
    else
    {
      // The entry doesn't have a parent but isn't a suffix.  This is not
      // allowed.
      throw new DirectoryException(ResultCode.NO_SUCH_OBJECT,
          ERR_ADD_ENTRY_NOT_SUFFIX.get(entryDN));
    }
  }



  /**

 opendj-server-legacy/src/main/java/org/opends/server/workflowelement/localbackend/LocalBackendDeleteOperation.java

@@ -22,13 +22,12 @@
 *
 *
 *      Copyright 2008-2009 Sun Microsystems, Inc.
 *      Portions Copyright 2011-2014 ForgeRock AS
 *      Portions Copyright 2011-2015 ForgeRock AS
 */
package org.opends.server.workflowelement.localbackend;

import java.util.List;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.locks.Lock;

import org.forgerock.i18n.LocalizableMessage;
import org.forgerock.i18n.slf4j.LocalizedLogger;
@@ -53,10 +52,10 @@
import org.opends.server.types.DN;
import org.opends.server.types.DirectoryException;
import org.opends.server.types.Entry;
import org.opends.server.types.LockManager;
import org.opends.server.types.Privilege;
import org.opends.server.types.SearchFilter;
import org.opends.server.types.SynchronizationProviderResult;
import org.opends.server.types.LockManager.DNLock;
import org.opends.server.types.operation.PostOperationDeleteOperation;
import org.opends.server.types.operation.PostResponseDeleteOperation;
import org.opends.server.types.operation.PostSynchronizationDeleteOperation;
@@ -207,12 +206,14 @@
      return;
    }

    // Grab a write lock on the entry.
    final Lock entryLock = LockManager.lockWrite(entryDN);

    /*
     * Grab a write lock on the entry and its subtree in order to prevent concurrent updates to
     * subordinate entries.
     */
    final DNLock subtreeLock = DirectoryServer.getLockManager().tryWriteLockSubtree(entryDN);
    try
    {
      if (entryLock == null)
      if (subtreeLock == null)
      {
        setResultCode(ResultCode.BUSY);
        appendErrorMessage(ERR_DELETE_CANNOT_LOCK_ENTRY.get(entryDN));
@@ -348,9 +349,9 @@
    }
    finally
    {
      if (entryLock != null)
      if (subtreeLock != null)
      {
        LockManager.unlock(entryDN, entryLock);
        subtreeLock.unlock();
      }
      processSynchPostOperationPlugins();
    }

 opendj-server-legacy/src/main/java/org/opends/server/workflowelement/localbackend/LocalBackendModifyDNOperation.java

@@ -30,7 +30,6 @@
import java.util.List;
import java.util.ListIterator;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.locks.Lock;

import org.forgerock.i18n.LocalizableMessage;
import org.forgerock.i18n.LocalizableMessageBuilder;
@@ -62,12 +61,12 @@
import org.opends.server.types.DN;
import org.opends.server.types.DirectoryException;
import org.opends.server.types.Entry;
import org.opends.server.types.LockManager;
import org.opends.server.types.Modification;
import org.opends.server.types.Privilege;
import org.opends.server.types.RDN;
import org.opends.server.types.SearchFilter;
import org.opends.server.types.SynchronizationProviderResult;
import org.opends.server.types.LockManager.DNLock;
import org.opends.server.types.operation.PostOperationModifyDNOperation;
import org.opends.server.types.operation.PostResponseModifyDNOperation;
import org.opends.server.types.operation.PostSynchronizationModifyDNOperation;
@@ -309,17 +308,24 @@
    checkIfCanceled(false);

    /*
     * FIXME: we lock the target DN and the renamed target DN, but not the parent of the target DN,
     * which seems inconsistent with the add operation implementation. Specifically, this
     * implementation does not defend against concurrent deletes of the parent of the renamed entry.
     * Acquire subtree write locks for the current and new DN. Be careful to avoid deadlocks by
     * taking the locks in a well defined order.
     */

    // Acquire write locks for the current and new DN.
    final Lock currentLock = LockManager.lockWrite(entryDN);
    Lock newLock = null;

    DNLock currentLock = null;
    DNLock newLock = null;
    try
    {
      if (entryDN.compareTo(newDN) < 0)
      {
        currentLock = DirectoryServer.getLockManager().tryWriteLockSubtree(entryDN);
        newLock = DirectoryServer.getLockManager().tryWriteLockSubtree(newDN);
      }
      else
      {
        newLock = DirectoryServer.getLockManager().tryWriteLockSubtree(newDN);
        currentLock = DirectoryServer.getLockManager().tryWriteLockSubtree(entryDN);
      }

      if (currentLock == null)
      {
        setResultCode(ResultCode.BUSY);
@@ -327,23 +333,10 @@
        return;
      }

      try
      if (newLock == null)
      {
        newLock = LockManager.lockWrite(newDN);
        if (newLock == null)
        {
          setResultCode(ResultCode.BUSY);
          appendErrorMessage(ERR_MODDN_CANNOT_LOCK_NEW_DN.get(entryDN, newDN));
          return;
        }
      }
      catch (Exception e)
      {
        logger.traceException(e);

        setResultCodeAndMessageNoInfoDisclosure(null, newDN,
            DirectoryServer.getServerErrorResultCode(),
            ERR_MODDN_EXCEPTION_LOCKING_NEW_DN.get(entryDN, newDN, getExceptionMessage(e)));
        setResultCode(ResultCode.BUSY);
        appendErrorMessage(ERR_MODDN_CANNOT_LOCK_NEW_DN.get(entryDN, newDN));
        return;
      }

@@ -495,11 +488,11 @@
    {
      if (currentLock != null)
      {
        LockManager.unlock(entryDN, currentLock);
        currentLock.unlock();
      }
      if (newLock != null)
      {
        LockManager.unlock(newDN, newLock);
        newLock.unlock();
      }
      processSynchPostOperationPlugins();
    }

 opendj-server-legacy/src/main/java/org/opends/server/workflowelement/localbackend/LocalBackendModifyOperation.java

@@ -31,7 +31,6 @@
import java.util.List;
import java.util.ListIterator;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.locks.Lock;

import org.forgerock.i18n.LocalizableMessage;
import org.forgerock.i18n.LocalizableMessageBuilder;
@@ -79,13 +78,13 @@
import org.opends.server.types.DN;
import org.opends.server.types.DirectoryException;
import org.opends.server.types.Entry;
import org.opends.server.types.LockManager;
import org.opends.server.types.Modification;
import org.opends.server.types.ObjectClass;
import org.opends.server.types.Privilege;
import org.opends.server.types.RDN;
import org.opends.server.types.SearchFilter;
import org.opends.server.types.SynchronizationProviderResult;
import org.opends.server.types.LockManager.DNLock;
import org.opends.server.types.operation.PostOperationModifyOperation;
import org.opends.server.types.operation.PostResponseModifyOperation;
import org.opends.server.types.operation.PostSynchronizationModifyOperation;
@@ -394,8 +393,7 @@
    checkIfCanceled(false);

    // Acquire a write lock on the target entry.
    final Lock entryLock = LockManager.lockWrite(entryDN);

    final DNLock entryLock = DirectoryServer.getLockManager().tryWriteLockEntry(entryDN);
    try
    {
      if (entryLock == null)
@@ -605,7 +603,7 @@
    {
      if (entryLock != null)
      {
        LockManager.unlock(entryDN, entryLock);
        entryLock.unlock();
      }
      processSynchPostOperationPlugins();
    }

 opendj-server-legacy/src/test/java/org/opends/server/core/AddOperationTestCase.java

@@ -22,7 +22,7 @@
 *
 *
 *      Copyright 2006-2008 Sun Microsystems, Inc.
 *      Portions Copyright 2011-2014 ForgeRock AS.
 *      Portions Copyright 2011-2015 ForgeRock AS.
 */
package org.opends.server.core;

@@ -32,7 +32,6 @@
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.concurrent.locks.Lock;

import org.forgerock.i18n.LocalizableMessage;
import org.forgerock.opendj.ldap.ByteString;
@@ -60,11 +59,11 @@
import org.opends.server.types.DN;
import org.opends.server.types.DirectoryException;
import org.opends.server.types.Entry;
import org.opends.server.types.LockManager;
import org.opends.server.types.ObjectClass;
import org.opends.server.types.Operation;
import org.opends.server.types.RawAttribute;
import org.opends.server.types.WritabilityMode;
import org.opends.server.types.LockManager.DNLock;
import org.opends.server.util.StaticUtils;
import org.testng.annotations.AfterMethod;
import org.testng.annotations.DataProvider;
@@ -1582,8 +1581,7 @@
  {
    TestCaseUtils.initializeTestBackend(true);

    Lock entryLock = LockManager.lockRead(DN.valueOf("ou=People,o=test"));

    final DNLock entryLock = DirectoryServer.getLockManager().tryReadLockEntry(DN.valueOf("ou=People,o=test"));
    try
    {
      Entry entry = TestCaseUtils.makeEntry(
@@ -1597,7 +1595,7 @@
    }
    finally
    {
      LockManager.unlock(DN.valueOf("ou=People,o=test"), entryLock);
      entryLock.unlock();
    }
  }


 opendj-server-legacy/src/test/java/org/opends/server/core/CompareOperationTestCase.java

@@ -22,15 +22,13 @@
 *
 *
 *      Copyright 2006-2008 Sun Microsystems, Inc.
 *      Portions Copyright 2011-2014 ForgeRock AS.
 *      Portions Copyright 2011-2015 ForgeRock AS.
 */

package org.opends.server.core;

import java.net.Socket;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.Lock;

import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.ResultCode;
@@ -41,7 +39,6 @@
import org.opends.server.plugins.InvocationCounterPlugin;
import org.opends.server.protocols.internal.InternalClientConnection;
import org.opends.server.protocols.ldap.*;
import org.opends.server.tools.LDAPWriter;
import org.opends.server.types.*;
import org.opends.server.util.ServerConstants;
import org.testng.annotations.BeforeClass;
@@ -639,80 +636,4 @@
    examineIncompleteOperation(compareOperation);
  }

  @Test(groups = "slow")
  public void testCompareWriteLock() throws Exception
  {
    // We need the operation to be run in a separate thread because we are going
    // to write lock the entry in the test case thread and check that the
    // compare operation does not proceed.

    // Establish a connection to the server.
    Socket s = new Socket("127.0.0.1", TestCaseUtils.getServerLdapPort());
    try
    {
      org.opends.server.tools.LDAPReader r =
          new org.opends.server.tools.LDAPReader(s);
      LDAPWriter w = new LDAPWriter(s);
      TestCaseUtils.configureSocket(s);

      BindRequestProtocolOp bindRequest =
           new BindRequestProtocolOp(
                ByteString.valueOf("cn=Directory Manager"),
                3, ByteString.valueOf("password"));
      LDAPMessage message = new LDAPMessage(1, bindRequest);
      w.writeMessage(message);

      message = r.readMessage();
      BindResponseProtocolOp bindResponse = message.getBindResponseProtocolOp();
      assertEquals(bindResponse.getResultCode(), LDAPResultCode.SUCCESS);

      // Since we are going to be watching the post-response count, we need to
      // wait for the server to become idle before kicking off the next request
      // to ensure that any remaining post-response processing from the previous
      // operation has completed.
      TestCaseUtils.quiesceServer();

      Lock writeLock = LockManager.lockWrite(entry.getName());
      assertNotNull(writeLock);

      try
      {
        InvocationCounterPlugin.resetAllCounters();

        long compareRequests  = ldapStatistics.getCompareRequests();
        long compareResponses = ldapStatistics.getCompareResponses();

        CompareRequestProtocolOp compareRequest =
          new CompareRequestProtocolOp(
               ByteString.valueOf(entry.getName().toString()),
               "uid", ByteString.valueOf("rogasawara"));
        message = new LDAPMessage(2, compareRequest);
        w.writeMessage(message);

        message = r.readMessage();
        CompareResponseProtocolOp compareResponse =
             message.getCompareResponseProtocolOp();

        assertEquals(compareResponse.getResultCode(), LDAPResultCode.BUSY);

//        assertEquals(InvocationCounterPlugin.getPreParseCount(), 1);
//        assertEquals(InvocationCounterPlugin.getPreOperationCount(), 0);
//        assertEquals(InvocationCounterPlugin.getPostOperationCount(), 0);

        // The post response might not have been called yet.
        assertEquals(InvocationCounterPlugin.waitForPostResponse(), 1);

        assertEquals(ldapStatistics.getCompareRequests(), compareRequests+1);
        assertEquals(ldapStatistics.getCompareResponses(), compareResponses+1);
      } finally
      {
        LockManager.unlock(entry.getName(), writeLock);
      }
    } finally
    {
      s.close();
    }

  }

}

 opendj-server-legacy/src/test/java/org/opends/server/core/DeleteOperationTestCase.java

@@ -22,14 +22,13 @@
 *
 *
 *      Copyright 2006-2008 Sun Microsystems, Inc.
 *      Portions Copyright 2011-2014 ForgeRock AS.
 *      Portions Copyright 2011-2015 ForgeRock AS.
 */
package org.opends.server.core;

import java.net.Socket;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.Lock;

import org.forgerock.i18n.LocalizableMessage;
import org.forgerock.opendj.ldap.ByteString;
@@ -45,6 +44,7 @@
import org.opends.server.tools.LDAPDelete;
import org.opends.server.tools.LDAPWriter;
import org.opends.server.types.*;
import org.opends.server.types.LockManager.DNLock;
import org.opends.server.util.StaticUtils;
import org.opends.server.workflowelement.localbackend.LocalBackendDeleteOperation;
import org.testng.annotations.AfterMethod;
@@ -207,8 +207,9 @@
    DeleteOperation deleteOperation = processDeleteRaw("o=test");
    assertEquals(deleteOperation.getResultCode(), ResultCode.SUCCESS);
    retrieveCompletedOperationElements(deleteOperation);
    @SuppressWarnings("unchecked")
    List<LocalBackendDeleteOperation> localOps =
      (List) deleteOperation.getAttachment(Operation.LOCALBACKENDOPERATIONS);
        (List<LocalBackendDeleteOperation>) deleteOperation.getAttachment(Operation.LOCALBACKENDOPERATIONS);
    assertNotNull(localOps);
    for (LocalBackendDeleteOperation curOp : localOps)
    {
@@ -239,8 +240,9 @@

    DeleteOperation deleteOperation = processDeleteRaw("ou=People,o=test");
    assertFalse(deleteOperation.getResultCode() == ResultCode.SUCCESS);
    @SuppressWarnings("unchecked")
    List<LocalBackendDeleteOperation> localOps =
      (List) deleteOperation.getAttachment(Operation.LOCALBACKENDOPERATIONS);
        (List<LocalBackendDeleteOperation>) deleteOperation.getAttachment(Operation.LOCALBACKENDOPERATIONS);
    assertNotNull(localOps);
    for (LocalBackendDeleteOperation curOp : localOps)
    {
@@ -694,8 +696,7 @@
  {
    TestCaseUtils.initializeTestBackend(true);

    Lock entryLock = LockManager.lockRead(DN.valueOf("o=test"));

    final DNLock entryLock = DirectoryServer.getLockManager().tryReadLockEntry(DN.valueOf("o=test"));
    try
    {
      DeleteOperation deleteOperation = processDeleteRaw("o=test");
@@ -703,7 +704,7 @@
    }
    finally
    {
      LockManager.unlock(DN.valueOf("o=test"), entryLock);
      entryLock.unlock();
    }
  }


 opendj-server-legacy/src/test/java/org/opends/server/core/ModifyOperationTestCase.java

@@ -22,7 +22,7 @@
 *
 *
 *      Copyright 2006-2011 Sun Microsystems, Inc.
 *      Portions Copyright 2011-2014 ForgeRock AS
 *      Portions Copyright 2011-2015 ForgeRock AS
 */
package org.opends.server.core;

@@ -30,7 +30,6 @@
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.locks.Lock;

import org.forgerock.i18n.LocalizableMessage;
import org.forgerock.opendj.ldap.ByteString;
@@ -63,11 +62,11 @@
import org.opends.server.types.DN;
import org.opends.server.types.DirectoryException;
import org.opends.server.types.Entry;
import org.opends.server.types.LockManager;
import org.opends.server.types.Modification;
import org.opends.server.types.Operation;
import org.opends.server.types.RawModification;
import org.opends.server.types.WritabilityMode;
import org.opends.server.types.LockManager.DNLock;
import org.opends.server.util.Base64;
import org.opends.server.util.ServerConstants;
import org.opends.server.util.StaticUtils;
@@ -399,8 +398,9 @@
               modifyOperation.getProcessingStartTime());
    assertTrue(modifyOperation.getProcessingTime() >= 0);

    @SuppressWarnings("unchecked")
    List<LocalBackendModifyOperation> localOps =
      (List) modifyOperation.getAttachment(Operation.LOCALBACKENDOPERATIONS);
        (List<LocalBackendModifyOperation>) modifyOperation.getAttachment(Operation.LOCALBACKENDOPERATIONS);
    assertNotNull(localOps);
    for (LocalBackendModifyOperation curOp : localOps)
    {
@@ -2789,8 +2789,7 @@
  public void testCannotLockEntry(String baseDN)
         throws Exception
  {
    Lock entryLock = LockManager.lockRead(DN.valueOf(baseDN));

    final DNLock entryLock = DirectoryServer.getLockManager().tryReadLockEntry(DN.valueOf(baseDN));
    try
    {
      LDAPAttribute attr = newLDAPAttribute("description", "foo");
@@ -2799,7 +2798,7 @@
    }
    finally
    {
      LockManager.unlock(DN.valueOf(baseDN), entryLock);
      entryLock.unlock();
    }
  }


 opendj-server-legacy/src/test/java/org/opends/server/core/TestModifyDNOperation.java

@@ -31,7 +31,6 @@
import java.util.Collections;
import java.util.Hashtable;
import java.util.List;
import java.util.concurrent.locks.Lock;

import javax.naming.Context;
import javax.naming.InvalidNameException;
@@ -52,6 +51,7 @@
import org.opends.server.tools.LDAPModify;
import org.opends.server.tools.LDAPWriter;
import org.opends.server.types.*;
import org.opends.server.types.LockManager.DNLock;
import org.opends.server.util.ServerConstants;
import org.opends.server.util.StaticUtils;
import org.testng.annotations.BeforeClass;
@@ -1042,7 +1042,7 @@
      assertTrue(DirectoryServer.getWorkQueue().waitUntilIdle(10000));


      Lock writeLock = LockManager.lockWrite(entry.getName());
      final DNLock writeLock = DirectoryServer.getLockManager().tryWriteLockEntry(entry.getName());
      assertNotNull(writeLock);

      try
@@ -1076,7 +1076,7 @@
//                     modifyDNResponses+1);
      } finally
      {
        LockManager.unlock(entry.getName(), writeLock);
        writeLock.unlock();
      }
    } finally
    {

 opendj-server-legacy/src/test/java/org/opends/server/types/LockManagerTest.java

New file
@@ -0,0 +1,320 @@
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt
 * or http://forgerock.org/license/CDDLv1.0.html.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at legal-notices/CDDLv1_0.txt.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Copyright 2015 ForgeRock AS
 */
package org.opends.server.types;

import static org.assertj.core.api.Assertions.assertThat;

import java.util.LinkedList;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.TimeoutException;

import org.opends.server.TestCaseUtils;
import org.opends.server.types.LockManager.DNLock;
import org.testng.annotations.BeforeClass;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

@Test(timeOut = 20000, sequential = true)
@SuppressWarnings("javadoc")
public class LockManagerTest extends TypesTestCase
{
  private enum LockType
  {
    READ_ENTRY
    {
      @Override
      DNLock lock(final LockManager lockManager, final DN dn)
      {
        return lockManager.tryReadLockEntry(dn);
      }
    },
    WRITE_ENTRY
    {
      @Override
      DNLock lock(final LockManager lockManager, final DN dn)
      {
        return lockManager.tryWriteLockEntry(dn);
      }
    },
    WRITE_SUBTREE
    {
      @Override
      DNLock lock(final LockManager lockManager, final DN dn)
      {
        return lockManager.tryWriteLockSubtree(dn);
      }
    };

    abstract DNLock lock(LockManager lockManager, DN dn);
  }

  private DN dnA;
  private DN dnAB;

  private DN dnABC;
  private DN dnABD;
  private final ExecutorService thread1 = Executors.newSingleThreadExecutor();
  private final ExecutorService thread2 = Executors.newSingleThreadExecutor();

  @BeforeClass
  private void setup() throws Exception
  {
    TestCaseUtils.startServer();
    dnA = DN.valueOf("dc=a");
    dnAB = DN.valueOf("dc=b,dc=a");
    dnABC = DN.valueOf("dc=c,dc=b,dc=a");
    dnABD = DN.valueOf("dc=d,dc=b,dc=a");
  }

  @Test
  public void testLockTimeout() throws Exception
  {
    final LockManager lockManager = new LockManager(100, TimeUnit.MILLISECONDS);
    DNLock lock1 = lockUsingThread(thread1, lockManager, LockType.WRITE_ENTRY, dnABC).get();
    DNLock lock2 = lockUsingThread(thread2, lockManager, LockType.WRITE_ENTRY, dnABC).get();
    assertThat(lock1).isNotNull();
    assertThat(lock2).isNull(); // Timed out.
    unlockUsingThread(thread1, lock1);
  }

  @DataProvider
  private Object[][] multiThreadedLockCombinationsWhichShouldBlock()
  {
    // @formatter:off
    return new Object[][] {
      { LockType.READ_ENTRY,    dnA,    LockType.WRITE_ENTRY,   dnA },
      { LockType.WRITE_ENTRY,   dnA,    LockType.READ_ENTRY,    dnA },
      { LockType.WRITE_ENTRY,   dnA,    LockType.WRITE_ENTRY,   dnA },

      { LockType.WRITE_SUBTREE, dnA,    LockType.READ_ENTRY,    dnA },
      { LockType.READ_ENTRY,    dnA,    LockType.WRITE_SUBTREE, dnA },
      { LockType.WRITE_SUBTREE, dnA,    LockType.WRITE_ENTRY,   dnA },
      { LockType.WRITE_ENTRY,   dnA,    LockType.WRITE_SUBTREE, dnA },
      { LockType.WRITE_SUBTREE, dnA,    LockType.WRITE_SUBTREE, dnA },

      { LockType.WRITE_SUBTREE, dnA,    LockType.READ_ENTRY,    dnAB },
      { LockType.READ_ENTRY,    dnAB,   LockType.WRITE_SUBTREE, dnA },
      { LockType.WRITE_SUBTREE, dnA,    LockType.WRITE_ENTRY,   dnAB },
      { LockType.WRITE_ENTRY,   dnAB,   LockType.WRITE_SUBTREE, dnA },
      { LockType.WRITE_SUBTREE, dnA,    LockType.WRITE_SUBTREE, dnAB },
      { LockType.WRITE_SUBTREE, dnAB,   LockType.WRITE_SUBTREE, dnA },
    };
    // @formatter:on
  }

  @Test(dataProvider = "multiThreadedLockCombinationsWhichShouldBlock")
  public void testMultiThreadedLockCombinationsWhichShouldBlock(final LockType lock1Type, final DN dn1,
      final LockType lock2Type, final DN dn2) throws Exception
  {
    final LockManager lockManager = new LockManager();
    final DNLock lock1 = lockUsingThread(thread1, lockManager, lock1Type, dn1).get();
    final Future<DNLock> lock2Future = lockUsingThread(thread2, lockManager, lock2Type, dn2);

    try
    {
      lock2Future.get(10, TimeUnit.MILLISECONDS);
    }
    catch (final TimeoutException e)
    {
      // Ignore: we'll check the state of the future instead.
    }
    assertThat(lock2Future.isDone()).isFalse();
    unlockUsingThread(thread1, lock1);
    final DNLock lock2 = lock2Future.get();
    unlockUsingThread(thread2, lock2);

    assertThat(getThreadLocalLockRefCountFor(thread1, lockManager, dn1)).isGreaterThan(0);
    assertThat(getThreadLocalLockRefCountFor(thread2, lockManager, dn2)).isGreaterThan(0);
    assertThat(lockManager.getLockTableRefCountFor(dn1)).isGreaterThan(0);
    assertThat(lockManager.getLockTableRefCountFor(dn2)).isGreaterThan(0);
  }

  @DataProvider
  private Object[][] multiThreadedLockCombinationsWhichShouldNotBlock()
  {
    // @formatter:off
    return new Object[][] {
      { LockType.READ_ENTRY,    dnA,    LockType.READ_ENTRY,    dnA },

      { LockType.READ_ENTRY,    dnA,    LockType.WRITE_ENTRY,   dnAB },
      { LockType.WRITE_ENTRY,   dnAB,   LockType.READ_ENTRY,    dnA },
      { LockType.WRITE_ENTRY,   dnA,    LockType.WRITE_ENTRY,   dnAB },
      { LockType.WRITE_ENTRY,   dnAB,   LockType.WRITE_ENTRY,   dnA },

      { LockType.READ_ENTRY,    dnA,    LockType.WRITE_SUBTREE, dnAB },
      { LockType.WRITE_SUBTREE, dnAB,   LockType.READ_ENTRY,    dnA },

      { LockType.WRITE_ENTRY,   dnA,    LockType.WRITE_SUBTREE, dnAB },
      { LockType.WRITE_SUBTREE, dnAB,   LockType.WRITE_ENTRY,   dnA },

      { LockType.WRITE_SUBTREE, dnABC,  LockType.WRITE_SUBTREE, dnABD },
    };
    // @formatter:on
  }

  @Test(dataProvider = "multiThreadedLockCombinationsWhichShouldNotBlock")
  public void testMultiThreadedLockCombinationsWhichShouldNotBlock(final LockType lock1Type, final DN dn1,
      final LockType lock2Type, final DN dn2) throws Exception
  {
    final LockManager lockManager = new LockManager();
    final DNLock lock1 = lockUsingThread(thread1, lockManager, lock1Type, dn1).get();
    final DNLock lock2 = lockUsingThread(thread2, lockManager, lock2Type, dn2).get();

    assertThat(lock1).isNotSameAs(lock2);
    unlockUsingThread(thread1, lock1);
    unlockUsingThread(thread2, lock2);

    assertThat(getThreadLocalLockRefCountFor(thread1, lockManager, dn1)).isGreaterThan(0);
    assertThat(getThreadLocalLockRefCountFor(thread2, lockManager, dn2)).isGreaterThan(0);
    assertThat(lockManager.getLockTableRefCountFor(dn1)).isGreaterThan(0);
    assertThat(lockManager.getLockTableRefCountFor(dn2)).isGreaterThan(0);
  }

  @DataProvider
  private LockType[][] reentrantLockCombinationsWhichShouldNotBlock()
  {
    // @formatter:off
    return new LockType[][] {
      { LockType.READ_ENTRY,    LockType.READ_ENTRY },

      { LockType.WRITE_ENTRY,   LockType.READ_ENTRY },
      { LockType.WRITE_ENTRY,   LockType.WRITE_ENTRY },

      { LockType.WRITE_SUBTREE, LockType.READ_ENTRY },
      { LockType.WRITE_SUBTREE, LockType.WRITE_ENTRY },
      { LockType.WRITE_SUBTREE, LockType.WRITE_SUBTREE },
    };
    // @formatter:on
  }

  @Test(dataProvider = "reentrantLockCombinationsWhichShouldNotBlock")
  public void testReentrantLockCombinationsWhichShouldNotBlock(final LockType lock1Type, final LockType lock2Type)
  {
    final LockManager lockManager = new LockManager();
    final DNLock lock1 = lock1Type.lock(lockManager, dnA);
    final DNLock lock2 = lock2Type.lock(lockManager, dnA);

    assertThat(lock1).isNotSameAs(lock2);
    assertThat(lock1.refCount()).isEqualTo(3); // +1 for thread local cache
    assertThat(lock2.refCount()).isEqualTo(3);

    lock1.unlock();
    assertThat(lock1.refCount()).isEqualTo(2);
    assertThat(lock2.refCount()).isEqualTo(2);

    lock2.unlock();
    assertThat(lock1.refCount()).isEqualTo(1);
    assertThat(lock2.refCount()).isEqualTo(1);

    assertThat(lockManager.getThreadLocalCacheRefCountFor(dnA)).isGreaterThan(0);
    assertThat(lockManager.getLockTableRefCountFor(dnA)).isGreaterThan(0);
  }

  @Test
  public void testThreadLocalCacheEviction() throws Exception
  {
    final LockManager lockManager = new LockManager();

    // Acquire 100 different locks. The first few locks should be evicted from the cache.
    final LinkedList<DNLock> locks = new LinkedList<DNLock>();
    for (int i = 0; i < 100; i++)
    {
      locks.add(lockManager.tryWriteLockEntry(dn(i)));
    }

    // The first lock should have been evicted from the cache, but still in the lock table because it is locked.
    assertThat(locks.getFirst().refCount()).isEqualTo(1);
    assertThat(lockManager.getThreadLocalCacheRefCountFor(dn(0))).isLessThan(0);
    assertThat(lockManager.getLockTableRefCountFor(dn(0))).isGreaterThan(0);

    // The last lock should still be in the cache and the lock table.
    assertThat(locks.getLast().refCount()).isEqualTo(2);
    assertThat(lockManager.getThreadLocalCacheRefCountFor(dn(99))).isGreaterThan(0);
    assertThat(lockManager.getLockTableRefCountFor(dn(99))).isGreaterThan(0);

    for (final DNLock lock : locks)
    {
      lock.unlock();
    }

    // The first lock should not be in the cache or the lock table.
    assertThat(locks.getFirst().refCount()).isEqualTo(0);
    assertThat(lockManager.getThreadLocalCacheRefCountFor(dn(0))).isLessThan(0);
    assertThat(lockManager.getLockTableRefCountFor(dn(0))).isLessThan(0);

    // The last lock should still be in the cache and the lock table.
    assertThat(locks.getLast().refCount()).isEqualTo(1);
    assertThat(lockManager.getThreadLocalCacheRefCountFor(dn(99))).isGreaterThan(0);
    assertThat(lockManager.getLockTableRefCountFor(dn(99))).isGreaterThan(0);
  }

  private DN dn(final int i) throws DirectoryException
  {
    return DN.valueOf(String.format("uid=user.%d,ou=people,dc=example,dc=com", i));
  }

  private Future<DNLock> lockUsingThread(final ExecutorService thread, final LockManager lockManager,
      final LockType lockType, final DN dn) throws Exception
  {
    return thread.submit(new Callable<DNLock>()
    {
      @Override
      public DNLock call() throws Exception
      {
        return lockType.lock(lockManager, dn);
      }
    });
  }

  private int getThreadLocalLockRefCountFor(final ExecutorService thread, final LockManager lockManager,
      final DN dn) throws Exception
  {
    return thread.submit(new Callable<Integer>()
    {
      @Override
      public Integer call() throws Exception
      {
        return lockManager.getThreadLocalCacheRefCountFor(dn);
      }
    }).get();
  }

  private void unlockUsingThread(final ExecutorService thread, final DNLock lock) throws Exception
  {
    thread.submit(new Runnable()
    {
      @Override
      public void run()
      {
        lock.unlock();
      }
    }).get();
  }
}