001    /*
002     * CDDL HEADER START
003     *
004     * The contents of this file are subject to the terms of the
005     * Common Development and Distribution License, Version 1.0 only
006     * (the "License").  You may not use this file except in compliance
007     * with the License.
008     *
009     * You can obtain a copy of the license at
010     * trunk/opends/resource/legal-notices/OpenDS.LICENSE
011     * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
012     * See the License for the specific language governing permissions
013     * and limitations under the License.
014     *
015     * When distributing Covered Code, include this CDDL HEADER in each
016     * file and include the License file at
017     * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
018     * add the following below this CDDL HEADER, with the fields enclosed
019     * by brackets "[]" replaced with your own identifying information:
020     *      Portions Copyright [yyyy] [name of copyright owner]
021     *
022     * CDDL HEADER END
023     *
024     *
025     *      Copyright 2006-2008 Sun Microsystems, Inc.
026     */
027    package org.opends.server.types;
028    
029    
030    
031    import java.util.concurrent.ConcurrentHashMap;
032    import java.util.concurrent.TimeUnit;
033    import java.util.concurrent.locks.Lock;
034    import java.util.concurrent.locks.ReentrantReadWriteLock;
035    
036    import org.opends.server.core.DirectoryServer;
037    import org.opends.server.loggers.debug.DebugTracer;
038    
039    import static org.opends.server.loggers.debug.DebugLogger.*;
040    import static org.opends.server.util.ServerConstants.*;
041    import static org.opends.server.util.StaticUtils.*;
042    
043    
044    
045    /**
046     * This class defines a Directory Server component that can keep track
047     * of all locks needed throughout the Directory Server.  It is
048     * intended primarily for entry locking but support for other types of
049     * objects might be added in the future.
050     */
051    @org.opends.server.types.PublicAPI(
052         stability=org.opends.server.types.StabilityLevel.UNCOMMITTED,
053         mayInstantiate=false,
054         mayExtend=false,
055         mayInvoke=true)
056    public final class LockManager
057    {
058      /**
059       * The tracer object for the debug logger.
060       */
061      private static final DebugTracer TRACER = getTracer();
062    
063      /**
064       * The default setting for the use of fair ordering locks.
065       */
066      public static final boolean DEFAULT_FAIR_ORDERING = true;
067    
068      /**
069       * The default initial size to use for the lock table.
070       */
071      public static final int DEFAULT_INITIAL_TABLE_SIZE = 64;
072    
073    
074    
075      /**
076       * The default concurrency level to use for the lock table.
077       */
078      public static final int DEFAULT_CONCURRENCY_LEVEL = 32;
079    
080    
081    
082      /**
083       * The default load factor to use for the lock table.
084       */
085      public static final float DEFAULT_LOAD_FACTOR = 0.75F;
086    
087    
088    
089      /**
090       * The default length of time in milliseconds to wait while
091       * attempting to acquire a read or write lock.
092       */
093      public static final long DEFAULT_TIMEOUT = 3000;
094    
095    
096    
097      // The set of entry locks that the server knows about.
098      private static
099           ConcurrentHashMap<DN,ReentrantReadWriteLock> lockTable;
100    
101      // Whether fair ordering should be used on the locks.
102      private static boolean fair;
103    
104    
105    
106      // Initialize the lock table.
107      static
108      {
109        DirectoryEnvironmentConfig environmentConfig =
110             DirectoryServer.getEnvironmentConfig();
111        lockTable = new ConcurrentHashMap<DN,ReentrantReadWriteLock>(
112             environmentConfig.getLockManagerTableSize(),
113             DEFAULT_LOAD_FACTOR,
114             environmentConfig.getLockManagerConcurrencyLevel());
115        fair = environmentConfig.getLockManagerFairOrdering();
116      }
117    
118    
119    
120      /**
121       * Recreates the lock table.  This should be called only in the
122       * case that the Directory Server is in the process of an in-core
123       * restart because it will destroy the existing lock table.
124       */
125      public synchronized static void reinitializeLockTable()
126      {
127        ConcurrentHashMap<DN,ReentrantReadWriteLock> oldTable = lockTable;
128    
129        DirectoryEnvironmentConfig environmentConfig =
130             DirectoryServer.getEnvironmentConfig();
131        lockTable = new ConcurrentHashMap<DN,ReentrantReadWriteLock>(
132             environmentConfig.getLockManagerTableSize(),
133             DEFAULT_LOAD_FACTOR,
134             environmentConfig.getLockManagerConcurrencyLevel());
135    
136        if  (! oldTable.isEmpty())
137        {
138          for (DN dn : oldTable.keySet())
139          {
140            try
141            {
142              ReentrantReadWriteLock lock = oldTable.get(dn);
143              if (lock.isWriteLocked())
144              {
145                TRACER.debugWarning("Found stale write lock on " +
146                                    dn.toString());
147              }
148              else if (lock.getReadLockCount() > 0)
149              {
150                TRACER.debugWarning("Found stale read lock on " +
151                                    dn.toString());
152              }
153              else
154              {
155                TRACER.debugWarning("Found stale unheld lock on " +
156                                    dn.toString());
157              }
158            }
159            catch (Exception e)
160            {
161              if (debugEnabled())
162              {
163                TRACER.debugCaught(DebugLogLevel.ERROR, e);
164              }
165            }
166          }
167    
168          oldTable.clear();
169        }
170    
171        fair = environmentConfig.getLockManagerFairOrdering();
172      }
173    
174    
175    
176      /**
177       * Attempts to acquire a read lock on the specified entry.  It will
178       * succeed only if the write lock is not already held.  If any
179       * blocking is required, then this call will fail rather than block.
180       *
181       * @param  entryDN  The DN of the entry for which to obtain the read
182       *                  lock.
183       *
184       * @return  The read lock that was acquired, or {@code null} if it
185       *          was not possible to obtain a read lock for some reason.
186       */
187      public static Lock tryLockRead(DN entryDN)
188      {
189        ReentrantReadWriteLock entryLock =
190            new ReentrantReadWriteLock(fair);
191        Lock readLock = entryLock.readLock();
192        readLock.lock();
193    
194        ReentrantReadWriteLock existingLock =
195             lockTable.putIfAbsent(entryDN, entryLock);
196        if (existingLock == null)
197        {
198          return readLock;
199        }
200        else
201        {
202          // There's a lock in the table, but it could potentially be
203          // unheld.  We'll do an unsafe check to see whether it might be
204          // held and if so then fail to acquire the lock.
205          if (existingLock.isWriteLocked())
206          {
207            readLock.unlock();
208            return null;
209          }
210    
211          // We will never remove a lock from the table without holding
212          // its monitor.  Since there's already a lock in the table, then
213          // get its monitor and try to acquire the lock.  This should
214          // prevent the owner from releasing the lock and removing it
215          // from the table before it can be acquired by another thread.
216          synchronized (existingLock)
217          {
218            ReentrantReadWriteLock existingLock2 =
219                 lockTable.putIfAbsent(entryDN, entryLock);
220            if (existingLock2 == null)
221            {
222              return readLock;
223            }
224            else if (existingLock == existingLock2)
225            {
226              // We were able to synchronize on the lock's monitor while
227              // the lock was still in the table.  Try to acquire it now
228              // (which will succeed if the lock isn't held by anything)
229              // and either return it or return null.
230              readLock.unlock();
231              readLock = existingLock.readLock();
232    
233              try
234              {
235                if (readLock.tryLock(0, TimeUnit.SECONDS))
236                {
237                  return readLock;
238                }
239                else
240                {
241                  return null;
242                }
243              }
244              catch(InterruptedException ie)
245              {
246                // This should never happen. Just return null
247                return null;
248              }
249            }
250            else
251            {
252              // If this happens, then it means that while we were waiting
253              // the existing lock was unlocked and removed from the table
254              // and a new one was created and added to the table.  This
255              // is more trouble than it's worth, so return null.
256              readLock.unlock();
257              return null;
258            }
259          }
260        }
261      }
262    
263    
264    
265      /**
266       * Attempts to acquire a read lock for the specified entry.
267       * Multiple threads can hold the read lock concurrently for an entry
268       * as long as the write lock is held.  If the write lock is held,
269       * then no other read or write locks will be allowed for that entry
270       * until the write lock is released.  A default timeout will be used
271       * for the lock.
272       *
273       * @param  entryDN  The DN of the entry for which to obtain the read
274       *                  lock.
275       *
276       * @return  The read lock that was acquired, or {@code null} if it
277       *          was not possible to obtain a read lock for some reason.
278       */
279      public static Lock lockRead(DN entryDN)
280      {
281        return lockRead(entryDN, DEFAULT_TIMEOUT);
282      }
283    
284    
285    
286      /**
287       * Attempts to acquire a read lock for the specified entry.
288       * Multiple threads can hold the read lock concurrently for an entry
289       * as long as the write lock is not held.  If the write lock is
290       * held, then no other read or write locks will be allowed for that
291       * entry until the write lock is released.
292       *
293       * @param  entryDN  The DN of the entry for which to obtain the read
294       *                  lock.
295       * @param  timeout  The maximum length of time in milliseconds to
296       *                  wait for the lock before timing out.
297       *
298       * @return  The read lock that was acquired, or <CODE>null</CODE> if
299       *          it was not possible to obtain a read lock for some
300       *          reason.
301       */
302      public static Lock lockRead(DN entryDN, long timeout)
303      {
304        // First, try to get the lock without blocking.
305        Lock readLock = tryLockRead(entryDN);
306        if (readLock != null)
307        {
308          return readLock;
309        }
310    
311        ReentrantReadWriteLock entryLock =
312            new ReentrantReadWriteLock(fair);
313        readLock = entryLock.readLock();
314        readLock.lock();
315    
316        ReentrantReadWriteLock existingLock =
317             lockTable.putIfAbsent(entryDN, entryLock);
318        if (existingLock == null)
319        {
320          return readLock;
321        }
322    
323        long surrenderTime = System.currentTimeMillis() + timeout;
324        readLock.unlock();
325        readLock = existingLock.readLock();
326    
327        while (true)
328        {
329          try
330          {
331            // See if we can acquire the lock while it's still in the
332            // table within the given timeout.
333            if (readLock.tryLock(timeout, TimeUnit.MILLISECONDS))
334            {
335              synchronized (existingLock)
336              {
337                if (lockTable.get(entryDN) == existingLock)
338                {
339                  // We acquired the lock within the timeout and it's
340                  // still in the lock table, so we're good to go.
341                  return readLock;
342                }
343                else
344                {
345                  ReentrantReadWriteLock existingLock2 =
346                       lockTable.putIfAbsent(entryDN, existingLock);
347                  if (existingLock2 == null)
348                  {
349                    // The lock had already been removed from the table,
350                    // but nothing had replaced it before we put it back,
351                    // so we're good to go.
352                    return readLock;
353                  }
354                  else
355                  {
356                    readLock.unlock();
357                    existingLock = existingLock2;
358                    readLock     = existingLock.readLock();
359                  }
360                }
361              }
362            }
363            else
364            {
365              // We couldn't acquire the lock before the timeout occurred,
366              // so we have to fail.
367              return null;
368            }
369          } catch (InterruptedException ie) {}
370    
371    
372          // There are only two reasons we should be here:
373          // - If the attempt to acquire the lock was interrupted.
374          // - If we acquired the lock but it had already been removed
375          //   from the table and another one had replaced it before we
376          //   could put it back.
377          // Our only recourse is to try again, but we need to reduce the
378          // timeout to account for the time we've already waited.
379          timeout = surrenderTime - System.currentTimeMillis();
380          if (timeout <= 0)
381          {
382            return null;
383          }
384        }
385      }
386    
387    
388    
389      /**
390       * Attempts to acquire a write lock on the specified entry.  It will
391       * succeed only if the lock is not already held.  If any blocking is
392       * required, then this call will fail rather than block.
393       *
394       * @param  entryDN  The DN of the entry for which to obtain the
395       *                  write lock.
396       *
397       * @return  The write lock that was acquired, or <CODE>null</CODE>
398       *          if it was not possible to obtain a write lock for some
399       *          reason.
400       */
401      public static Lock tryLockWrite(DN entryDN)
402      {
403        ReentrantReadWriteLock entryLock =
404            new ReentrantReadWriteLock(fair);
405        Lock writeLock = entryLock.writeLock();
406        writeLock.lock();
407    
408        ReentrantReadWriteLock existingLock =
409             lockTable.putIfAbsent(entryDN, entryLock);
410        if (existingLock == null)
411        {
412          return writeLock;
413        }
414        else
415        {
416          // There's a lock in the table, but it could potentially be
417          // unheld.  We'll do an unsafe check to see whether it might be
418          // held and if so then fail to acquire the lock.
419          if ((existingLock.getReadLockCount() > 0) ||
420              (existingLock.isWriteLocked()))
421          {
422            writeLock.unlock();
423            return null;
424          }
425    
426          // We will never remove a lock from the table without holding
427          // its monitor.  Since there's already a lock in the table, then
428          // get its monitor and try to acquire the lock.  This should
429          // prevent the owner from releasing the lock and removing it
430          // from the table before it can be acquired by another thread.
431          synchronized (existingLock)
432          {
433            ReentrantReadWriteLock existingLock2 =
434                 lockTable.putIfAbsent(entryDN, entryLock);
435            if (existingLock2 == null)
436            {
437              return writeLock;
438            }
439            else if (existingLock == existingLock2)
440            {
441              // We were able to synchronize on the lock's monitor while
442              // the lock was still in the table.  Try to acquire it now
443              // (which will succeed if the lock isn't held by anything)
444              // and either return it or return null.
445              writeLock.unlock();
446              writeLock = existingLock.writeLock();
447              try
448              {
449                if (writeLock.tryLock(0, TimeUnit.SECONDS))
450                {
451                  return writeLock;
452                }
453                else
454                {
455                  return null;
456                }
457              }
458              catch(InterruptedException ie)
459              {
460                // This should never happen. Just return null
461                return null;
462              }
463            }
464            else
465            {
466              // If this happens, then it means that while we were waiting
467              // the existing lock was unlocked and removed from the table
468              // and a new one was created and added to the table.  This
469              // is more trouble than it's worth, so return null.
470              writeLock.unlock();
471              return null;
472            }
473          }
474        }
475      }
476    
477    
478    
479      /**
480       * Attempts to acquire the write lock for the specified entry.  Only
481       * a single thread may hold the write lock for an entry at any given
482       * time, and during that time no read locks may be held for it.  A
483       * default timeout will be used for the lock.
484       *
485       * @param  entryDN  The DN of the entry for which to obtain the
486       *                  write lock.
487       *
488       * @return  The write lock that was acquired, or <CODE>null</CODE>
489       *          if it was not possible to obtain a write lock for some
490       *          reason.
491       */
492      public static Lock lockWrite(DN entryDN)
493      {
494        return lockWrite(entryDN, DEFAULT_TIMEOUT);
495      }
496    
497    
498    
499      /**
500       * Attempts to acquire the write lock for the specified entry.  Only
501       * a single thread may hold the write lock for an entry at any given
502       * time, and during that time no read locks may be held for it.
503       *
504       * @param  entryDN  The DN of the entry for which to obtain the
505       *                  write lock.
506       * @param  timeout  The maximum length of time in milliseconds to
507       *                  wait for the lock before timing out.
508       *
509       * @return  The write lock that was acquired, or <CODE>null</CODE>
510       *          if it was not possible to obtain a read lock for some
511       *          reason.
512       */
513      public static Lock lockWrite(DN entryDN, long timeout)
514      {
515        // First, try to get the lock without blocking.
516        Lock writeLock = tryLockWrite(entryDN);
517        if (writeLock != null)
518        {
519          return writeLock;
520        }
521    
522        ReentrantReadWriteLock entryLock =
523            new ReentrantReadWriteLock(fair);
524        writeLock = entryLock.writeLock();
525        writeLock.lock();
526    
527        ReentrantReadWriteLock existingLock =
528             lockTable.putIfAbsent(entryDN, entryLock);
529        if (existingLock == null)
530        {
531          return writeLock;
532        }
533    
534        long surrenderTime = System.currentTimeMillis() + timeout;
535        writeLock.unlock();
536        writeLock = existingLock.writeLock();
537    
538        while (true)
539        {
540          try
541          {
542            // See if we can acquire the lock while it's still in the
543            // table within the given timeout.
544            if (writeLock.tryLock(timeout, TimeUnit.MILLISECONDS))
545            {
546              synchronized (existingLock)
547              {
548                if (lockTable.get(entryDN) == existingLock)
549                {
550                  // We acquired the lock within the timeout and it's
551                  // still in the lock table, so we're good to go.
552                  return writeLock;
553                }
554                else
555                {
556                  ReentrantReadWriteLock existingLock2 =
557                       lockTable.putIfAbsent(entryDN, existingLock);
558                  if (existingLock2 == null)
559                  {
560                    // The lock had already been removed from the table,
561                    // but nothing had replaced it before we put it back,
562                    // so we're good to go.
563                    return writeLock;
564                  }
565                  else
566                  {
567                    writeLock.unlock();
568                    existingLock  = existingLock2;
569                    writeLock     = existingLock.writeLock();
570                  }
571                }
572              }
573            }
574            else
575            {
576              // We couldn't acquire the lock before the timeout occurred,
577              // so we have to fail.
578              return null;
579            }
580          } catch (InterruptedException ie) {}
581    
582    
583          // There are only two reasons we should be here:
584          // - If the attempt to acquire the lock was interrupted.
585          // - If we acquired the lock but it had already been removed
586          //   from the table and another one had replaced it before we
587          //   could put it back.
588          // Our only recourse is to try again, but we need to reduce the
589          // timeout to account for the time we've already waited.
590          timeout = surrenderTime - System.currentTimeMillis();
591          if (timeout <= 0)
592          {
593            return null;
594          }
595        }
596      }
597    
598    
599    
600      /**
601       * Releases a read or write lock held on the specified entry.
602       *
603       * @param  entryDN  The DN of the entry for which to release the
604       *                  lock.
605       * @param  lock     The read or write lock held for the entry.
606       */
607      public static void unlock(DN entryDN, Lock lock)
608      {
609        // Get the corresponding read-write lock from the lock table.
610        ReentrantReadWriteLock existingLock = lockTable.get(entryDN);
611        if (existingLock == null)
612        {
613          // This shouldn't happen, but if it does then all we can do is
614          // release the lock and return.
615          lock.unlock();
616          return;
617        }
618    
619        // See if there's anything waiting on the lock.  If so, then we
620        // can't remove it from the table when we unlock it.
621        if (existingLock.hasQueuedThreads() ||
622            (existingLock.getReadLockCount() > 1))
623        {
624          lock.unlock();
625          return;
626        }
627        else
628        {
629          lock.unlock();
630          synchronized (existingLock)
631          {
632            if ((! existingLock.isWriteLocked()) &&
633                (existingLock.getReadLockCount() == 0))
634            {
635              lockTable.remove(entryDN, existingLock);
636            }
637          }
638          return;
639        }
640      }
641    
642    
643    
644      /**
645       * Removes any reference to the specified entry from the lock table.
646       * This may be helpful if there is a case where a lock has been
647       * orphaned somehow and must be removed before other threads may
648       * acquire it.
649       *
650       * @param  entryDN  The DN of the entry for which to remove the lock
651       *                  from the table.
652       *
653       * @return  The read write lock that was removed from the table, or
654       *          {@code null} if nothing was in the table for the
655       *          specified entry.  If a lock object is returned, it may
656       *          be possible to get information about who was holding it.
657       */
658      public static ReentrantReadWriteLock destroyLock(DN entryDN)
659      {
660        return lockTable.remove(entryDN);
661      }
662    
663    
664    
665      /**
666       * Retrieves the number of entries currently held in the lock table.
667       * Note that this may be an expensive operation.
668       *
669       * @return  The number of entries currently held in the lock table.
670       */
671      public static int lockTableSize()
672      {
673        return lockTable.size();
674      }
675    }
676