001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *     http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    package org.apache.commons.transaction.locking;
018    
019    import java.util.ArrayList;
020    import java.util.Collection;
021    import java.util.Collections;
022    import java.util.HashMap;
023    import java.util.HashSet;
024    import java.util.Iterator;
025    import java.util.Map;
026    import java.util.Set;
027    
028    import org.apache.commons.transaction.util.LoggerFacade;
029    
030    /**
031     * Manager for {@link GenericLock}s on resources. This implementation includes 
032     * <ul>
033     * <li>deadlock detection, which is configurable to come into effect after an initial short waiting
034     * lock request; this is useful as it is somewhat expensive
035     * <li>global transaction timeouts that actively revoke granted rights from transactions
036     * </ul>
037     * 
038     * @version $Id: GenericLockManager.java 545634 2007-06-08 21:36:59Z ozeigermann $
039     */
040    public class GenericLockManager implements LockManager, LockManager2 {
041    
042        public static final long DEFAULT_TIMEOUT = 30000;
043        public static final long DEFAULT_CHECK_THRESHHOLD = 500;
044        
045        /** Maps onwerId to locks it (partially) owns. */
046        protected Map globalOwners = Collections.synchronizedMap(new HashMap());
047    
048        /** Maps resourceId to lock. */
049        protected Map globalLocks = new HashMap();
050        
051        /** Maps onwerId to global effective time outs (i.e. the time the lock will time out). */
052        protected Map effectiveGlobalTimeouts = Collections.synchronizedMap(new HashMap());
053    
054        protected Set timedOutOwners = Collections.synchronizedSet(new HashSet());
055        
056        protected int maxLockLevel = -1;
057        protected LoggerFacade logger;
058        protected long globalTimeoutMSecs;
059        protected long checkThreshhold;
060        
061        /**
062         * Creates a new generic lock manager.
063         * 
064         * @param maxLockLevel
065         *            highest allowed lock level as described in {@link GenericLock}
066         *            's class intro
067         * @param logger
068         *            generic logger used for all kind of debug logging
069         * @param timeoutMSecs
070         *            specifies the maximum time to wait for a lock in milliseconds
071         * @param checkThreshholdMSecs
072         *            specifies a special wait threshhold before deadlock and
073         *            timeout detection come into play or <code>-1</code> switch
074         *            it off and check for directly
075         * @throws IllegalArgumentException
076         *             if maxLockLevel is less than 1
077         * 
078         * @since 1.1
079         */
080        public GenericLockManager(int maxLockLevel, LoggerFacade logger, long timeoutMSecs,
081                long checkThreshholdMSecs) throws IllegalArgumentException {
082            if (maxLockLevel < 1)
083                throw new IllegalArgumentException("The maximum lock level must be at least 1 ("
084                        + maxLockLevel + " was specified)");
085            this.maxLockLevel = maxLockLevel;
086            this.logger = logger.createLogger("Locking");
087            this.globalTimeoutMSecs = timeoutMSecs;
088            this.checkThreshhold = checkThreshholdMSecs;
089        }
090    
091        public GenericLockManager(int maxLockLevel, LoggerFacade logger, long timeoutMSecs)
092                throws IllegalArgumentException {
093            this(maxLockLevel, logger, timeoutMSecs, DEFAULT_CHECK_THRESHHOLD);
094        }
095    
096        public GenericLockManager(int maxLockLevel, LoggerFacade logger)
097                throws IllegalArgumentException {
098            this(maxLockLevel, logger, DEFAULT_TIMEOUT);
099        }
100    
101        /**
102         * @see LockManager2#startGlobalTimeout(Object, long)
103         * @since 1.1
104         */
105        public void startGlobalTimeout(Object ownerId, long timeoutMSecs) {
106            long now = System.currentTimeMillis();
107            long timeout = now + timeoutMSecs;
108            effectiveGlobalTimeouts.put(ownerId, new Long(timeout));
109        }
110        
111        /**
112         * @see LockManager2#tryLock(Object, Object, int, boolean)
113         * @since 1.1
114         */
115        public boolean tryLock(Object ownerId, Object resourceId, int targetLockLevel, boolean reentrant) {
116            timeoutCheck(ownerId);
117    
118            GenericLock lock = (GenericLock) atomicGetOrCreateLock(resourceId);
119            boolean acquired = lock.tryLock(ownerId, targetLockLevel,
120                    reentrant ? GenericLock.COMPATIBILITY_REENTRANT : GenericLock.COMPATIBILITY_NONE,
121                    false);
122            
123            if (acquired) {
124                addOwner(ownerId, lock);
125            }
126            return acquired;
127        }
128    
129        /**
130         * @see LockManager2#checkLock(Object, Object, int, boolean)
131         * @since 1.1
132         */
133        public boolean checkLock(Object ownerId, Object resourceId, int targetLockLevel, boolean reentrant) {
134            timeoutCheck(ownerId);
135            boolean possible = true;
136    
137            GenericLock lock = (GenericLock) getLock(resourceId);
138            if (lock != null) {
139                possible = lock.test(ownerId, targetLockLevel,
140                        reentrant ? GenericLock.COMPATIBILITY_REENTRANT
141                                : GenericLock.COMPATIBILITY_NONE);
142            }
143            return possible;
144        }
145    
146        /**
147         * @see LockManager2#hasLock(Object, Object, int)
148         * @since 1.1
149         */
150        public boolean hasLock(Object ownerId, Object resourceId, int lockLevel) {
151            timeoutCheck(ownerId);
152            boolean owned = false;
153    
154            GenericLock lock = (GenericLock) getLock(resourceId);
155            if (lock != null) {
156                owned = lock.has(ownerId, lockLevel);
157            }
158            return owned;
159        }
160    
161        /**
162         * @see LockManager2#lock(Object, Object, int, boolean)
163         * @since 1.1
164         */
165        public void lock(Object ownerId, Object resourceId, int targetLockLevel, boolean reentrant)
166                throws LockException {
167            lock(ownerId, resourceId, targetLockLevel, reentrant, globalTimeoutMSecs);
168        }
169    
170        /**
171         * @see LockManager2#lock(Object, Object, int, boolean, long)
172         * @since 1.1
173         */
174        public void lock(Object ownerId, Object resourceId, int targetLockLevel, boolean reentrant,
175                long timeoutMSecs) throws LockException {
176            lock(ownerId, resourceId, targetLockLevel, reentrant ? GenericLock.COMPATIBILITY_REENTRANT
177                    : GenericLock.COMPATIBILITY_NONE, false, timeoutMSecs);
178        }
179    
180        /**
181         * @see LockManager2#lock(Object, Object, int, int, boolean, long)
182         * @since 1.1
183         */
184        public void lock(Object ownerId, Object resourceId, int targetLockLevel, int compatibility,
185                boolean preferred, long timeoutMSecs) throws LockException {
186            timeoutCheck(ownerId);
187            GenericLock lock = (GenericLock) atomicGetOrCreateLock(resourceId);
188            doLock(lock, ownerId, resourceId, targetLockLevel, compatibility, preferred, timeoutMSecs);
189        }
190    
191        protected void doLock(GenericLock lock, Object ownerId, Object resourceId, int targetLockLevel,
192                              int compatibility, boolean preferred, long timeoutMSecs)
193        {
194            long now = System.currentTimeMillis();
195            long waitEnd = now + timeoutMSecs;
196    
197            timeoutCheck(ownerId);
198            
199            GenericLock.LockOwner lockWaiter = new GenericLock.LockOwner(ownerId, targetLockLevel,
200                    compatibility, preferred);
201            
202            boolean acquired = false;
203            try {
204                
205                // detection for deadlocks and time outs is rather expensive, 
206                // so we wait for the lock for a  
207                // short time (<5 seconds) to see if we get it without checking;
208                // if not we still can check what the reason for this is
209                if (checkThreshhold != -1 && timeoutMSecs > checkThreshhold) {
210                    acquired = lock
211                            .acquire(ownerId, targetLockLevel, true, compatibility,
212                                    preferred, checkThreshhold);
213                    timeoutMSecs -= checkThreshhold;
214                } else {
215                    acquired = lock
216                    .acquire(ownerId, targetLockLevel, false, compatibility,
217                            preferred, checkThreshhold);
218                    
219                }
220                if (acquired) {
221                    addOwner(ownerId, lock);
222                    return;
223                }
224            } catch (InterruptedException e) {
225                throw new LockException("Interrupted", LockException.CODE_INTERRUPTED, resourceId);
226            }
227            try {
228                lock.registerWaiter(lockWaiter);
229                
230                boolean deadlock = wouldDeadlock(ownerId, new HashSet());
231                if (deadlock) {
232                    throw new LockException("Lock would cause deadlock",
233                            LockException.CODE_DEADLOCK_VICTIM, resourceId);
234                }
235    
236                now = System.currentTimeMillis();
237                while (!acquired && waitEnd > now) {
238                
239                    // first be sure all locks are stolen from owners that have already timed out
240                    releaseTimedOutOwners();
241    
242                    // if there are owners we conflict with lets see if one of them globally times
243                    // out earlier than this lock, if so we will wake up then to check again
244                    Set conflicts = lock.getConflictingOwners(ownerId, targetLockLevel, compatibility);
245                    long nextConflictTimeout = getNextGlobalConflictTimeout(conflicts);
246                    if (nextConflictTimeout != -1 && nextConflictTimeout < waitEnd) {
247                        timeoutMSecs = nextConflictTimeout - now;
248                        // XXX add 10% to ensure the lock really is timed out
249                        timeoutMSecs += timeoutMSecs / 10;
250                    } else {
251                        timeoutMSecs = waitEnd - now;
252                    }
253    
254                    // XXX acquire will remove us as a waiter, but it is important to remain us such
255                    // to constantly indicate it to other owners, otherwise there might be undetected
256                    // deadlocks
257                    synchronized (lock) {
258                        acquired = lock.acquire(ownerId, targetLockLevel, true, compatibility,
259                                preferred, timeoutMSecs);
260                        lock.registerWaiter(lockWaiter);
261                    }
262                    now = System.currentTimeMillis();
263                }
264                if (!acquired) {
265                    throw new LockException("Lock wait timed out", LockException.CODE_TIMED_OUT,
266                            resourceId);
267                } else {
268                    addOwner(ownerId, lock);
269                }
270            } catch (InterruptedException e) {
271                throw new LockException("Interrupted", LockException.CODE_INTERRUPTED, resourceId);
272            } finally {
273                lock.unregisterWaiter(lockWaiter);
274            }
275        }
276    
277        /**
278         * @see LockManager2#getLevel(Object, Object)
279         * @since 1.1
280         */
281        public int getLevel(Object ownerId, Object resourceId) {
282            timeoutCheck(ownerId);
283            GenericLock lock = (GenericLock) getLock(resourceId);
284            if (lock != null) {
285                return lock.getLockLevel(ownerId);
286            } else {
287                return 0;
288            }
289        }
290    
291        /**
292         * @see LockManager2#release(Object, Object)
293         * @since 1.1
294         */
295        public boolean release(Object ownerId, Object resourceId) {
296            timeoutCheck(ownerId);
297            boolean released = false;
298    
299            GenericLock lock = (GenericLock) getLock(resourceId);
300            if (lock != null) {
301                released = lock.release(ownerId);
302                removeOwner(ownerId, lock);
303            }
304            return released;
305        }
306    
307        /**
308         * @see LockManager2#releaseAll(Object)
309         * @since 1.1
310         */
311        public void releaseAll(Object ownerId) {
312            releaseAllNoTimeOutReset(ownerId);
313            // reset time out status for this owner
314            timedOutOwners.remove(ownerId);
315            effectiveGlobalTimeouts.remove(ownerId);
316        }
317    
318        protected void releaseAllNoTimeOutReset(Object ownerId) {
319            Set locks = (Set) globalOwners.get(ownerId);
320            if (locks != null) {
321                Collection locksCopy;
322                // need to copy in order not to interfere with wouldDeadlock
323                // possibly called by
324                // other threads
325                synchronized (locks) {
326                    locksCopy = new ArrayList(locks);
327                }
328                for (Iterator it = locksCopy.iterator(); it.hasNext();) {
329                    GenericLock lock = (GenericLock) it.next();
330                    lock.release(ownerId);
331                    locks.remove(lock);
332                }
333            }
334            removeOwnerWithoutLocks(ownerId);
335        }
336        
337        /**
338         * @see LockManager2#getAll(Object)
339         * @since 1.1
340         */
341        public Set getAll(Object ownerId) {
342            Set locks = (Set) globalOwners.get(ownerId);
343            if (locks == null) {
344                return new HashSet();
345            } else {
346                return locks;
347            }
348        }
349    
350        protected void addOwner(Object ownerId, GenericLock lock) {
351            synchronized (globalOwners) {
352                Set locks = (Set) globalOwners.get(ownerId);
353                if (locks == null) {
354                    locks = Collections.synchronizedSet(new HashSet());
355                    globalOwners.put(ownerId, locks);
356                }
357                locks.add(lock);
358            }
359        }
360    
361        protected void removeOwner(Object ownerId, GenericLock lock) {
362            Set locks = (Set) globalOwners.get(ownerId);
363            if (locks != null) {
364                locks.remove(lock);
365            }
366            removeOwnerWithoutLocks(ownerId);
367        }
368    
369        /**
370         * Checks if an owner is deadlocked. <br>
371         * <br>
372         * We traverse the tree recursively formed by owners, locks held by them and
373         * then again owners waiting for the locks. If there is a cycle in one of
374         * the paths from the root to a leaf we have a deadlock. <br>
375         * <br>
376         * A more detailed discussion on deadlocks and definitions and how to detect
377         * them can be found in <a
378         * href="http://www.onjava.com/pub/a/onjava/2004/10/20/threads2.html?page=1">this
379         * nice article </a>. <br>
380         * <em>Caution:</em> This computation can be very expensive with many
381         * owners and locks. Worst (unlikely) case is exponential.
382         * 
383         * @param ownerId
384         *            the owner to check for being deadlocked
385         * @param path
386         *            initially should be called with an empty set
387         * @return <code>true</code> if the owner is deadlocked,
388         *         <code>false</code> otherwise
389         */
390        protected boolean wouldDeadlock(Object ownerId, Set path) {
391            path.add(ownerId);
392            // these are our locks
393            Set locks = (Set) globalOwners.get(ownerId);
394            if (locks != null) {
395                Collection locksCopy;
396                // need to copy in order not to interfere with releaseAll possibly called by
397                // other threads
398                synchronized (locks) {
399                    locksCopy = new ArrayList(locks);
400                }
401                for (Iterator i = locksCopy.iterator(); i.hasNext();) {
402                    GenericLock mylock = (GenericLock) i.next();
403                    // these are the ones waiting for one of our locks
404                    Collection conflicts = mylock.getConflictingWaiters(ownerId);
405                    if (conflicts != null) {
406                        for (Iterator j = conflicts.iterator(); j.hasNext();) {
407                            Object waitingOwnerId = j.next();
408                            if (path.contains(waitingOwnerId)) {
409                                return true;
410                            } else if (wouldDeadlock(waitingOwnerId, path)) {
411                                return true;
412                            }
413                        }
414                    }
415                }
416            }
417            path.remove(ownerId);
418            return false;
419        }
420    
421        protected boolean releaseTimedOutOwners() {
422            boolean released = false;
423            synchronized (effectiveGlobalTimeouts) {
424                for (Iterator it = effectiveGlobalTimeouts.entrySet().iterator(); it.hasNext();) {
425                    Map.Entry entry = (Map.Entry) it.next();
426                    Object ownerId = entry.getKey();
427                    long timeout = ((Long) entry.getValue()).longValue();
428                    long now = System.currentTimeMillis();
429                    if (timeout < now) {
430                        releaseAllNoTimeOutReset(ownerId);
431                        timedOutOwners.add(ownerId);
432                        released = true;
433                    }
434                }
435            }
436            return released;
437        }
438        
439        protected boolean timeOut(Object ownerId) {
440            Long timeout = (Long)effectiveGlobalTimeouts.get(ownerId);
441            long now = System.currentTimeMillis();
442            if (timeout != null && timeout.longValue() < now) {
443                releaseAll(ownerId);
444                timedOutOwners.add(ownerId);
445                return true;
446            } else {
447                return false;
448            }
449        }
450        
451        protected long getNextGlobalConflictTimeout(Set conflicts) {
452            long minTimeout = -1;
453            long now = System.currentTimeMillis();
454            if (conflicts != null) {
455                synchronized (effectiveGlobalTimeouts) {
456                    for (Iterator it = effectiveGlobalTimeouts.entrySet().iterator(); it.hasNext();) {
457                        Map.Entry entry = (Map.Entry) it.next();
458                        Object ownerId = entry.getKey();
459                        if (conflicts.contains(ownerId)) {
460                            long timeout = ((Long) entry.getValue()).longValue();
461                            if (minTimeout == -1 || timeout < minTimeout) {
462                                minTimeout = timeout;
463                            }
464                        }
465                    }
466                }
467            }
468            return minTimeout;
469        }
470        
471        public MultiLevelLock getLock(Object resourceId) {
472            synchronized (globalLocks) {
473                return (MultiLevelLock) globalLocks.get(resourceId);
474            }
475        }
476    
477        public MultiLevelLock atomicGetOrCreateLock(Object resourceId) {
478            synchronized (globalLocks) {
479                MultiLevelLock lock = getLock(resourceId);
480                if (lock == null) {
481                    lock = createLock(resourceId);
482                }
483                return lock;
484            }
485        }
486    
487        public void removeLock(MultiLevelLock lock) {
488            synchronized (globalLocks) {
489                globalLocks.remove(lock);
490            }
491        }
492        
493        /**
494         * Gets all locks as orignials, <em>no copies</em>.
495         * 
496         * @return collection holding all locks.
497         */
498        public Collection getLocks() {
499            synchronized (globalLocks) {
500               return globalLocks.values();
501            }
502        }
503    
504        public synchronized String toString() {
505            StringBuffer buf = new StringBuffer(1000);
506            for (Iterator it = globalLocks.values().iterator(); it.hasNext();) {
507                GenericLock lock = (GenericLock) it.next();
508                buf.append(lock.toString()).append('\n');
509            }
510            return buf.toString();
511        }
512    
513        protected GenericLock createLock(Object resourceId) {
514            synchronized (globalLocks) {
515                GenericLock lock = new GenericLock(resourceId, maxLockLevel, logger);
516                globalLocks.put(resourceId, lock);
517                return lock;
518            }
519        }
520        
521        protected void timeoutCheck(Object ownerId) throws LockException {
522            timeOut(ownerId);
523            if (timedOutOwners.contains(ownerId)) {
524                throw new LockException(
525                        "All locks of owner "
526                                + ownerId
527                                + " have globally timed out."
528                                + " You will not be able to to continue with this owner until you call releaseAll.",
529                        LockException.CODE_TIMED_OUT, null);
530            }
531        }
532    
533        protected void removeOwnerWithoutLocks(Object ownerId) {
534            synchronized (globalOwners) {
535                Set locks = (Set) globalOwners.get(ownerId);
536                if (locks == null || locks.isEmpty()) {
537                    globalOwners.remove(ownerId);
538                }
539            }
540        }
541    }