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 */
017package org.apache.commons.transaction.locking;
018
019import java.util.ArrayList;
020import java.util.Collection;
021import java.util.Collections;
022import java.util.HashMap;
023import java.util.HashSet;
024import java.util.Iterator;
025import java.util.Map;
026import java.util.Set;
027
028import 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 */
040public 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}