1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.google.common.util.concurrent;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20
21 import com.google.common.annotations.Beta;
22 import com.google.common.annotations.VisibleForTesting;
23 import com.google.common.base.MoreObjects;
24 import com.google.common.base.Preconditions;
25 import com.google.common.collect.ImmutableSet;
26 import com.google.common.collect.Lists;
27 import com.google.common.collect.MapMaker;
28 import com.google.common.collect.Maps;
29 import com.google.common.collect.Sets;
30
31 import java.util.ArrayList;
32 import java.util.Arrays;
33 import java.util.Collections;
34 import java.util.EnumMap;
35 import java.util.List;
36 import java.util.Map;
37 import java.util.Set;
38 import java.util.concurrent.ConcurrentMap;
39 import java.util.concurrent.TimeUnit;
40 import java.util.concurrent.locks.ReentrantLock;
41 import java.util.concurrent.locks.ReentrantReadWriteLock;
42 import java.util.logging.Level;
43 import java.util.logging.Logger;
44
45 import javax.annotation.Nullable;
46 import javax.annotation.concurrent.ThreadSafe;
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164 @Beta
165 @ThreadSafe
166 public class CycleDetectingLockFactory {
167
168
169
170
171
172
173
174
175 @Beta
176 @ThreadSafe
177 public interface Policy {
178
179
180
181
182
183
184
185
186
187
188
189 void handlePotentialDeadlock(PotentialDeadlockException exception);
190 }
191
192
193
194
195
196
197 @Beta
198 public enum Policies implements Policy {
199
200
201
202
203
204
205 THROW {
206 @Override
207 public void handlePotentialDeadlock(PotentialDeadlockException e) {
208 throw e;
209 }
210 },
211
212
213
214
215
216
217
218 WARN {
219 @Override
220 public void handlePotentialDeadlock(PotentialDeadlockException e) {
221 logger.log(Level.SEVERE, "Detected potential deadlock", e);
222 }
223 },
224
225
226
227
228
229
230
231
232
233
234
235 DISABLED {
236 @Override
237 public void handlePotentialDeadlock(PotentialDeadlockException e) {
238 }
239 };
240 }
241
242
243
244
245 public static CycleDetectingLockFactory newInstance(Policy policy) {
246 return new CycleDetectingLockFactory(policy);
247 }
248
249
250
251
252 public ReentrantLock newReentrantLock(String lockName) {
253 return newReentrantLock(lockName, false);
254 }
255
256
257
258
259
260
261 public ReentrantLock newReentrantLock(String lockName, boolean fair) {
262 return policy == Policies.DISABLED ? new ReentrantLock(fair)
263 : new CycleDetectingReentrantLock(
264 new LockGraphNode(lockName), fair);
265 }
266
267
268
269
270 public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName) {
271 return newReentrantReadWriteLock(lockName, false);
272 }
273
274
275
276
277
278
279 public ReentrantReadWriteLock newReentrantReadWriteLock(
280 String lockName, boolean fair) {
281 return policy == Policies.DISABLED ? new ReentrantReadWriteLock(fair)
282 : new CycleDetectingReentrantReadWriteLock(
283 new LockGraphNode(lockName), fair);
284 }
285
286
287 private static final ConcurrentMap<Class<? extends Enum>,
288 Map<? extends Enum, LockGraphNode>> lockGraphNodesPerType =
289 new MapMaker().weakKeys().makeMap();
290
291
292
293
294 public static <E extends Enum<E>> WithExplicitOrdering<E>
295 newInstanceWithExplicitOrdering(Class<E> enumClass, Policy policy) {
296
297
298 checkNotNull(enumClass);
299 checkNotNull(policy);
300 @SuppressWarnings("unchecked")
301 Map<E, LockGraphNode> lockGraphNodes =
302 (Map<E, LockGraphNode>) getOrCreateNodes(enumClass);
303 return new WithExplicitOrdering<E>(policy, lockGraphNodes);
304 }
305
306 private static Map<? extends Enum, LockGraphNode> getOrCreateNodes(
307 Class<? extends Enum> clazz) {
308 Map<? extends Enum, LockGraphNode> existing =
309 lockGraphNodesPerType.get(clazz);
310 if (existing != null) {
311 return existing;
312 }
313 Map<? extends Enum, LockGraphNode> created = createNodes(clazz);
314 existing = lockGraphNodesPerType.putIfAbsent(clazz, created);
315 return MoreObjects.firstNonNull(existing, created);
316 }
317
318
319
320
321
322
323
324 @VisibleForTesting
325 static <E extends Enum<E>> Map<E, LockGraphNode> createNodes(Class<E> clazz) {
326 EnumMap<E, LockGraphNode> map = Maps.newEnumMap(clazz);
327 E[] keys = clazz.getEnumConstants();
328 final int numKeys = keys.length;
329 ArrayList<LockGraphNode> nodes =
330 Lists.newArrayListWithCapacity(numKeys);
331
332 for (E key : keys) {
333 LockGraphNode node = new LockGraphNode(getLockName(key));
334 nodes.add(node);
335 map.put(key, node);
336 }
337
338 for (int i = 1; i < numKeys; i++) {
339 nodes.get(i).checkAcquiredLocks(Policies.THROW, nodes.subList(0, i));
340 }
341
342 for (int i = 0; i < numKeys - 1; i++) {
343 nodes.get(i).checkAcquiredLocks(
344 Policies.DISABLED, nodes.subList(i + 1, numKeys));
345 }
346 return Collections.unmodifiableMap(map);
347 }
348
349
350
351
352
353
354 private static String getLockName(Enum<?> rank) {
355 return rank.getDeclaringClass().getSimpleName() + "." + rank.name();
356 }
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419 @Beta
420 public static final class WithExplicitOrdering<E extends Enum<E>>
421 extends CycleDetectingLockFactory {
422
423 private final Map<E, LockGraphNode> lockGraphNodes;
424
425 @VisibleForTesting
426 WithExplicitOrdering(
427 Policy policy, Map<E, LockGraphNode> lockGraphNodes) {
428 super(policy);
429 this.lockGraphNodes = lockGraphNodes;
430 }
431
432
433
434
435 public ReentrantLock newReentrantLock(E rank) {
436 return newReentrantLock(rank, false);
437 }
438
439
440
441
442
443
444
445
446
447
448 public ReentrantLock newReentrantLock(E rank, boolean fair) {
449 return policy == Policies.DISABLED ? new ReentrantLock(fair)
450 : new CycleDetectingReentrantLock(lockGraphNodes.get(rank), fair);
451 }
452
453
454
455
456 public ReentrantReadWriteLock newReentrantReadWriteLock(E rank) {
457 return newReentrantReadWriteLock(rank, false);
458 }
459
460
461
462
463
464
465
466
467
468
469 public ReentrantReadWriteLock newReentrantReadWriteLock(
470 E rank, boolean fair) {
471 return policy == Policies.DISABLED ? new ReentrantReadWriteLock(fair)
472 : new CycleDetectingReentrantReadWriteLock(
473 lockGraphNodes.get(rank), fair);
474 }
475 }
476
477
478
479 private static final Logger logger = Logger.getLogger(
480 CycleDetectingLockFactory.class.getName());
481
482 final Policy policy;
483
484 private CycleDetectingLockFactory(Policy policy) {
485 this.policy = checkNotNull(policy);
486 }
487
488
489
490
491
492
493
494
495 private static final ThreadLocal<ArrayList<LockGraphNode>>
496 acquiredLocks = new ThreadLocal<ArrayList<LockGraphNode>>() {
497 @Override
498 protected ArrayList<LockGraphNode> initialValue() {
499 return Lists.<LockGraphNode>newArrayListWithCapacity(3);
500 }
501 };
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517 private static class ExampleStackTrace extends IllegalStateException {
518
519 static final StackTraceElement[] EMPTY_STACK_TRACE =
520 new StackTraceElement[0];
521
522 static Set<String> EXCLUDED_CLASS_NAMES = ImmutableSet.of(
523 CycleDetectingLockFactory.class.getName(),
524 ExampleStackTrace.class.getName(),
525 LockGraphNode.class.getName());
526
527 ExampleStackTrace(LockGraphNode node1, LockGraphNode node2) {
528 super(node1.getLockName() + " -> " + node2.getLockName());
529 StackTraceElement[] origStackTrace = getStackTrace();
530 for (int i = 0, n = origStackTrace.length; i < n; i++) {
531 if (WithExplicitOrdering.class.getName().equals(
532 origStackTrace[i].getClassName())) {
533
534 setStackTrace(EMPTY_STACK_TRACE);
535 break;
536 }
537 if (!EXCLUDED_CLASS_NAMES.contains(origStackTrace[i].getClassName())) {
538 setStackTrace(Arrays.copyOfRange(origStackTrace, i, n));
539 break;
540 }
541 }
542 }
543 }
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567 @Beta
568 public static final class PotentialDeadlockException
569 extends ExampleStackTrace {
570
571 private final ExampleStackTrace conflictingStackTrace;
572
573 private PotentialDeadlockException(
574 LockGraphNode node1,
575 LockGraphNode node2,
576 ExampleStackTrace conflictingStackTrace) {
577 super(node1, node2);
578 this.conflictingStackTrace = conflictingStackTrace;
579 initCause(conflictingStackTrace);
580 }
581
582 public ExampleStackTrace getConflictingStackTrace() {
583 return conflictingStackTrace;
584 }
585
586
587
588
589
590 @Override
591 public String getMessage() {
592 StringBuilder message = new StringBuilder(super.getMessage());
593 for (Throwable t = conflictingStackTrace; t != null; t = t.getCause()) {
594 message.append(", ").append(t.getMessage());
595 }
596 return message.toString();
597 }
598 }
599
600
601
602
603
604
605 private interface CycleDetectingLock {
606
607
608 LockGraphNode getLockGraphNode();
609
610
611 boolean isAcquiredByCurrentThread();
612 }
613
614
615
616
617
618 private static class LockGraphNode {
619
620
621
622
623
624
625 final Map<LockGraphNode, ExampleStackTrace> allowedPriorLocks =
626 new MapMaker().weakKeys().makeMap();
627
628
629
630
631
632 final Map<LockGraphNode, PotentialDeadlockException>
633 disallowedPriorLocks = new MapMaker().weakKeys().makeMap();
634
635 final String lockName;
636
637 LockGraphNode(String lockName) {
638 this.lockName = Preconditions.checkNotNull(lockName);
639 }
640
641 String getLockName() {
642 return lockName;
643 }
644
645 void checkAcquiredLocks(
646 Policy policy, List<LockGraphNode> acquiredLocks) {
647 for (int i = 0, size = acquiredLocks.size(); i < size; i++) {
648 checkAcquiredLock(policy, acquiredLocks.get(i));
649 }
650 }
651
652
653
654
655
656
657
658
659
660
661 void checkAcquiredLock(Policy policy, LockGraphNode acquiredLock) {
662
663
664
665
666
667
668 Preconditions.checkState(
669 this != acquiredLock,
670 "Attempted to acquire multiple locks with the same rank " +
671 acquiredLock.getLockName());
672
673 if (allowedPriorLocks.containsKey(acquiredLock)) {
674
675
676
677 return;
678 }
679 PotentialDeadlockException previousDeadlockException =
680 disallowedPriorLocks.get(acquiredLock);
681 if (previousDeadlockException != null) {
682
683
684
685 PotentialDeadlockException exception = new PotentialDeadlockException(
686 acquiredLock, this,
687 previousDeadlockException.getConflictingStackTrace());
688 policy.handlePotentialDeadlock(exception);
689 return;
690 }
691
692
693 Set<LockGraphNode> seen = Sets.newIdentityHashSet();
694 ExampleStackTrace path = acquiredLock.findPathTo(this, seen);
695
696 if (path == null) {
697
698
699
700
701
702
703
704
705 allowedPriorLocks.put(
706 acquiredLock, new ExampleStackTrace(acquiredLock, this));
707 } else {
708
709
710 PotentialDeadlockException exception =
711 new PotentialDeadlockException(acquiredLock, this, path);
712 disallowedPriorLocks.put(acquiredLock, exception);
713 policy.handlePotentialDeadlock(exception);
714 }
715 }
716
717
718
719
720
721
722
723
724
725
726 @Nullable
727 private ExampleStackTrace findPathTo(
728 LockGraphNode node, Set<LockGraphNode> seen) {
729 if (!seen.add(this)) {
730 return null;
731 }
732 ExampleStackTrace found = allowedPriorLocks.get(node);
733 if (found != null) {
734 return found;
735 }
736
737 for (Map.Entry<LockGraphNode, ExampleStackTrace> entry :
738 allowedPriorLocks.entrySet()) {
739 LockGraphNode preAcquiredLock = entry.getKey();
740 found = preAcquiredLock.findPathTo(node, seen);
741 if (found != null) {
742
743
744
745 ExampleStackTrace path =
746 new ExampleStackTrace(preAcquiredLock, this);
747 path.setStackTrace(entry.getValue().getStackTrace());
748 path.initCause(found);
749 return path;
750 }
751 }
752 return null;
753 }
754 }
755
756
757
758
759
760 private void aboutToAcquire(CycleDetectingLock lock) {
761 if (!lock.isAcquiredByCurrentThread()) {
762 ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get();
763 LockGraphNode node = lock.getLockGraphNode();
764 node.checkAcquiredLocks(policy, acquiredLockList);
765 acquiredLockList.add(node);
766 }
767 }
768
769
770
771
772
773
774
775 private void lockStateChanged(CycleDetectingLock lock) {
776 if (!lock.isAcquiredByCurrentThread()) {
777 ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get();
778 LockGraphNode node = lock.getLockGraphNode();
779
780
781 for (int i = acquiredLockList.size() - 1; i >=0; i--) {
782 if (acquiredLockList.get(i) == node) {
783 acquiredLockList.remove(i);
784 break;
785 }
786 }
787 }
788 }
789
790 final class CycleDetectingReentrantLock
791 extends ReentrantLock implements CycleDetectingLock {
792
793 private final LockGraphNode lockGraphNode;
794
795 private CycleDetectingReentrantLock(
796 LockGraphNode lockGraphNode, boolean fair) {
797 super(fair);
798 this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode);
799 }
800
801
802
803 @Override
804 public LockGraphNode getLockGraphNode() {
805 return lockGraphNode;
806 }
807
808 @Override
809 public boolean isAcquiredByCurrentThread() {
810 return isHeldByCurrentThread();
811 }
812
813
814
815 @Override
816 public void lock() {
817 aboutToAcquire(this);
818 try {
819 super.lock();
820 } finally {
821 lockStateChanged(this);
822 }
823 }
824
825 @Override
826 public void lockInterruptibly() throws InterruptedException {
827 aboutToAcquire(this);
828 try {
829 super.lockInterruptibly();
830 } finally {
831 lockStateChanged(this);
832 }
833 }
834
835 @Override
836 public boolean tryLock() {
837 aboutToAcquire(this);
838 try {
839 return super.tryLock();
840 } finally {
841 lockStateChanged(this);
842 }
843 }
844
845 @Override
846 public boolean tryLock(long timeout, TimeUnit unit)
847 throws InterruptedException {
848 aboutToAcquire(this);
849 try {
850 return super.tryLock(timeout, unit);
851 } finally {
852 lockStateChanged(this);
853 }
854 }
855
856 @Override
857 public void unlock() {
858 try {
859 super.unlock();
860 } finally {
861 lockStateChanged(this);
862 }
863 }
864 }
865
866 final class CycleDetectingReentrantReadWriteLock
867 extends ReentrantReadWriteLock implements CycleDetectingLock {
868
869
870
871
872
873 private final CycleDetectingReentrantReadLock readLock;
874 private final CycleDetectingReentrantWriteLock writeLock;
875
876 private final LockGraphNode lockGraphNode;
877
878 private CycleDetectingReentrantReadWriteLock(
879 LockGraphNode lockGraphNode, boolean fair) {
880 super(fair);
881 this.readLock = new CycleDetectingReentrantReadLock(this);
882 this.writeLock = new CycleDetectingReentrantWriteLock(this);
883 this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode);
884 }
885
886
887
888 @Override
889 public ReadLock readLock() {
890 return readLock;
891 }
892
893 @Override
894 public WriteLock writeLock() {
895 return writeLock;
896 }
897
898
899
900 @Override
901 public LockGraphNode getLockGraphNode() {
902 return lockGraphNode;
903 }
904
905 @Override
906 public boolean isAcquiredByCurrentThread() {
907 return isWriteLockedByCurrentThread() || getReadHoldCount() > 0;
908 }
909 }
910
911 private class CycleDetectingReentrantReadLock
912 extends ReentrantReadWriteLock.ReadLock {
913
914 final CycleDetectingReentrantReadWriteLock readWriteLock;
915
916 CycleDetectingReentrantReadLock(
917 CycleDetectingReentrantReadWriteLock readWriteLock) {
918 super(readWriteLock);
919 this.readWriteLock = readWriteLock;
920 }
921
922 @Override
923 public void lock() {
924 aboutToAcquire(readWriteLock);
925 try {
926 super.lock();
927 } finally {
928 lockStateChanged(readWriteLock);
929 }
930 }
931
932 @Override
933 public void lockInterruptibly() throws InterruptedException {
934 aboutToAcquire(readWriteLock);
935 try {
936 super.lockInterruptibly();
937 } finally {
938 lockStateChanged(readWriteLock);
939 }
940 }
941
942 @Override
943 public boolean tryLock() {
944 aboutToAcquire(readWriteLock);
945 try {
946 return super.tryLock();
947 } finally {
948 lockStateChanged(readWriteLock);
949 }
950 }
951
952 @Override
953 public boolean tryLock(long timeout, TimeUnit unit)
954 throws InterruptedException {
955 aboutToAcquire(readWriteLock);
956 try {
957 return super.tryLock(timeout, unit);
958 } finally {
959 lockStateChanged(readWriteLock);
960 }
961 }
962
963 @Override
964 public void unlock() {
965 try {
966 super.unlock();
967 } finally {
968 lockStateChanged(readWriteLock);
969 }
970 }
971 }
972
973 private class CycleDetectingReentrantWriteLock
974 extends ReentrantReadWriteLock.WriteLock {
975
976 final CycleDetectingReentrantReadWriteLock readWriteLock;
977
978 CycleDetectingReentrantWriteLock(
979 CycleDetectingReentrantReadWriteLock readWriteLock) {
980 super(readWriteLock);
981 this.readWriteLock = readWriteLock;
982 }
983
984 @Override
985 public void lock() {
986 aboutToAcquire(readWriteLock);
987 try {
988 super.lock();
989 } finally {
990 lockStateChanged(readWriteLock);
991 }
992 }
993
994 @Override
995 public void lockInterruptibly() throws InterruptedException {
996 aboutToAcquire(readWriteLock);
997 try {
998 super.lockInterruptibly();
999 } finally {
1000 lockStateChanged(readWriteLock);
1001 }
1002 }
1003
1004 @Override
1005 public boolean tryLock() {
1006 aboutToAcquire(readWriteLock);
1007 try {
1008 return super.tryLock();
1009 } finally {
1010 lockStateChanged(readWriteLock);
1011 }
1012 }
1013
1014 @Override
1015 public boolean tryLock(long timeout, TimeUnit unit)
1016 throws InterruptedException {
1017 aboutToAcquire(readWriteLock);
1018 try {
1019 return super.tryLock(timeout, unit);
1020 } finally {
1021 lockStateChanged(readWriteLock);
1022 }
1023 }
1024
1025 @Override
1026 public void unlock() {
1027 try {
1028 super.unlock();
1029 } finally {
1030 lockStateChanged(readWriteLock);
1031 }
1032 }
1033 }
1034 }