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