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.List;
026    import java.util.Map;
027    import java.util.Set;
028    
029    import org.apache.commons.transaction.util.LoggerFacade;
030    
031    /**
032     * A generic implementain of a simple multi level lock.
033     * 
034     * <p>
035     * The idea is to have an ascending number of lock levels ranging from
036     * <code>0</code> to <code>maxLockLevel</code> as specified in
037     * {@link #GenericLock(Object, int, LoggerFacade)}: the higher the lock level
038     * the stronger and more restrictive the lock. To determine which lock may
039     * coexist with other locks you have to imagine matching pairs of lock levels.
040     * For each pair both parts allow for all lock levels less than or equal to the
041     * matching other part. Pairs are composed by the lowest and highest level not
042     * yet part of a pair and successively applying this method until no lock level
043     * is left. For an even amount of levels each level is part of exactly one pair.
044     * For an odd amount the middle level is paired with itself. The highst lock
045     * level may coexist with the lowest one (<code>0</code>) which by
046     * definition means <code>NO LOCK</code>. This implies that you will have to
047     * specify at least one other lock level and thus set <code>maxLockLevel</code>
048     * to at least <code>1</code>.
049     * </p>
050     * 
051     * <p>
052     * Although this may sound complicated, in practice this is quite simple. Let us
053     * imagine you have three lock levels:
054     * <ul>
055     * <li><code>0</code>:<code>NO LOCK</code> (always needed by the
056     * implementation of this lock)
057     * <li><code>1</code>:<code>SHARED</code>
058     * <li><code>2</code>:<code>EXCLUSIVE</code>
059     * </ul>
060     * Accordingly, you will have to set <code>maxLockLevel</code> to
061     * <code>2</code>. Now, there are two pairs of levels
062     * <ul>
063     * <li><code>NO LOCK</code> with <code>EXCLUSIVE</code>
064     * <li><code>SHARED</code> with <code>SHARED</code>
065     * </ul>
066     * This means when the current highest lock level is <code>NO LOCK</code>
067     * everything less or equal to <code>EXCLUSIVE</code> is allowed - which means
068     * every other lock level. On the other side <code>EXCLUSIVE</code> allows
069     * exacly for <code>NO LOCK</code>- which means nothing else. In conclusion,
070     * <code>SHARED</code> allows for <code>SHARED</code> or <code>NO
071     * LOCK</code>,
072     * but not for <code>EXCLUSIVE</code>. To make this very clear have a look at
073     * this table, where <code>o</code> means compatible or can coexist and
074     * <code>x</code> means incompatible or can not coexist:
075     * </p>
076     * <table><tbody>
077     * <tr>
078     * <td align="center"></td>
079     * <td align="center">NO LOCK</td>
080     * <td align="center">SHARED</td>
081     * <td align="center">EXCLUSIVE</td>
082     * </tr>
083     * <tr>
084     * <td align="center">NO LOCK</td>
085     * <td align="center">o</td>
086     * <td align="center">o</td>
087     * <td align="center">o</td>
088     * </tr>
089     * <tr>
090     * <td align="center">SHARED</td>
091     * <td align="center">o</td>
092     * <td align="center">o</td>
093     * <td align="center">x</td>
094     * </tr>
095     * <tr>
096     * <td align="center">EXCLUSIVE</td>
097     * <td align="center" align="center">o</td>
098     * <td align="center">x</td>
099     * <td align="center">x</td>
100     * </tr>
101     * </tbody> </table>
102     * 
103     * </p>
104     * <p>
105     * Additionally, there are preferences for specific locks you can pass to
106     * {@link #acquire(Object, int, boolean, int, boolean, long)}. 
107     * This means whenever more thanone party
108     * waits for a lock you can specify which one is to be preferred. This gives you
109     * every freedom you might need to specifcy e.g. 
110     * <ul>
111     * <li>priority to parties either applying for higher or lower lock levels
112     * <li>priority not only to higher or lower locks, but to a specific level
113     * <li>completely random preferences
114     * </ul>
115     * </p>
116     * 
117     * @version $Id: GenericLock.java 493628 2007-01-07 01:42:48Z joerg $
118     */
119    public class GenericLock implements MultiLevelLock2 {
120    
121        protected Object resourceId;
122        // XXX needs to be synchronized to allow for unsynchronized access for deadlock detection
123        // in getConflictingOwners to avoid deadlocks between lock to acquire and lock to check for
124        // deadlocks
125        protected Map owners = Collections.synchronizedMap(new HashMap());
126        // XXX needs to be synchronized to allow for unsynchronized access for deadlock detection
127        // in getConflictingWaiters to avoid deadlocks between lock to acquire and lock to check for
128        // deadlocks
129        // Note: having this as a list allows for fair mechanisms in sub classes
130        protected List waitingOwners = Collections.synchronizedList(new ArrayList());
131        private int maxLockLevel;
132        protected LoggerFacade logger;
133        protected int waiters = 0;
134        
135        /**
136         * Creates a new lock.
137         * 
138         * @param resourceId identifier for the resource associated to this lock
139         * @param maxLockLevel highest allowed lock level as described in class intro 
140         * @param logger generic logger used for all kind of debug logging
141         */
142        public GenericLock(Object resourceId, int maxLockLevel, LoggerFacade logger) {
143            if (maxLockLevel < 1)
144                throw new IllegalArgumentException(
145                    "The maximum lock level must be at least 1 (" + maxLockLevel + " was specified)");
146            this.resourceId = resourceId;
147            this.maxLockLevel = maxLockLevel;
148            this.logger = logger;
149        }
150    
151        public boolean equals(Object o) {
152            if (o instanceof GenericLock) {
153                return ((GenericLock)o).resourceId.equals(resourceId);
154            }
155            return false;
156        }
157    
158        public int hashCode() {
159            return resourceId.hashCode();
160        }
161    
162        /**
163         * @see MultiLevelLock2#test(Object, int, int)
164         */
165        public boolean test(Object ownerId, int targetLockLevel, int compatibility) {
166            boolean success = tryLock(ownerId, targetLockLevel, compatibility, false, true);
167            return success;
168        }
169        
170        /**
171         * @see MultiLevelLock2#has(Object, int)
172         */
173        public boolean has(Object ownerId, int lockLevel) {
174            int level = getLockLevel(ownerId);
175            return (lockLevel <= level);
176        }
177        
178        /**
179         * @see org.apache.commons.transaction.locking.MultiLevelLock#acquire(java.lang.Object,
180         *      int, boolean, boolean, long)
181         */
182        public synchronized boolean acquire(Object ownerId, int targetLockLevel, boolean wait,
183                boolean reentrant, long timeoutMSecs) throws InterruptedException {
184            return acquire(ownerId, targetLockLevel, wait, reentrant ? COMPATIBILITY_REENTRANT
185                    : COMPATIBILITY_NONE, timeoutMSecs);
186        }
187    
188        /**
189         * @see #acquire(Object, int, boolean, int, boolean, long)
190         */
191        public synchronized boolean acquire(Object ownerId, int targetLockLevel, boolean wait,
192                int compatibility, long timeoutMSecs) throws InterruptedException {
193            return acquire(ownerId, targetLockLevel, wait, compatibility, false, timeoutMSecs);
194        }
195        
196        /**
197         * Tries to blockingly acquire a lock which can be preferred.
198         * 
199         * @see #acquire(Object, int, boolean, int, boolean, long) 
200         * @since 1.1 
201         */
202        public synchronized boolean acquire(Object ownerId, int targetLockLevel, boolean preferred,
203                long timeoutMSecs) throws InterruptedException {
204            return acquire(ownerId, targetLockLevel, true, COMPATIBILITY_REENTRANT, preferred,
205                    timeoutMSecs);
206        }
207        
208        /**
209         * @see org.apache.commons.transaction.locking.MultiLevelLock2#acquire(Object,
210         *      int, boolean, int, boolean, long)
211         * @since 1.1 
212         */
213        public synchronized boolean acquire(
214            Object ownerId,
215            int targetLockLevel,
216            boolean wait,
217            int compatibility,
218            boolean preferred,
219            long timeoutMSecs)
220            throws InterruptedException {
221    
222            if (logger.isFinerEnabled()) {
223                    logger.logFiner(
224                        ownerId.toString()
225                            + " trying to acquire lock for "
226                            + resourceId.toString()
227                            + " at level "
228                            + targetLockLevel
229                            + " at "
230                            + System.currentTimeMillis());
231            }
232    
233            if (tryLock(ownerId, targetLockLevel, compatibility, preferred)) {
234                
235                if (logger.isFinerEnabled()) {
236                        logger.logFiner(
237                            ownerId.toString()
238                                + " actually acquired lock for "
239                                + resourceId.toString()
240                                + " at "
241                                + System.currentTimeMillis());
242                }
243    
244                return true;
245            } else {
246                if (!wait) {
247                    return false;
248                } else {
249                    long started = System.currentTimeMillis();
250                    for (long remaining = timeoutMSecs;
251                        remaining > 0;
252                        remaining = timeoutMSecs - (System.currentTimeMillis() - started)) {
253    
254                        if (logger.isFinerEnabled()) {
255                                logger.logFiner(
256                                    ownerId.toString()
257                                        + " waiting on "
258                                        + resourceId.toString()
259                                        + " for msecs "
260                                        + timeoutMSecs
261                                        + " at "
262                                        + System.currentTimeMillis());
263                        }
264    
265                        LockOwner waitingOwner = new LockOwner(ownerId, targetLockLevel, compatibility,
266                                preferred);
267                        try {
268                            registerWaiter(waitingOwner);
269                            if (preferred) {
270                                // while waiting we already make our claim we are next
271                                LockOwner oldLock = null;
272                                try {
273                                    // we need to remember it to restore it after waiting
274                                    oldLock = (LockOwner) owners.get(ownerId);
275                                    // this creates a new owner, so we do not need to
276                                    // copy the old one
277                                    setLockLevel(ownerId, null, targetLockLevel, compatibility,
278                                            preferred);
279        
280                                    // finally wait
281                                    wait(remaining);
282                                    
283                                } finally {
284                                    // we need to restore the old lock in order not to
285                                    // interfere with the intention lock in the
286                                    // following check
287                                    // and not to have it in case of success either
288                                    // as there will be an ordinary lock then
289                                    if (oldLock != null) {
290                                        owners.put(ownerId, oldLock);
291                                    } else {
292                                        owners.remove(ownerId);
293                                    }
294                                }
295        
296                            } else {
297                                wait(remaining);
298                            }
299                        } finally {
300                            unregisterWaiter(waitingOwner);
301                        }
302                        
303                        if (tryLock(ownerId, targetLockLevel, compatibility, preferred)) {
304    
305                            if (logger.isFinerEnabled()) {
306                                    logger.logFiner(
307                                        ownerId.toString()
308                                            + " waiting on "
309                                            + resourceId.toString()
310                                            + " eventually got the lock at "
311                                            + System.currentTimeMillis());
312                            }
313    
314                            return true;
315                        }
316                    }
317                    return false;
318                }
319            }
320        }
321    
322        protected void registerWaiter(LockOwner waitingOwner) {
323            synchronized (waitingOwners) {
324                unregisterWaiter(waitingOwner);
325                waiters++;
326                waitingOwners.add(waitingOwner);
327            }
328        }
329    
330        protected void unregisterWaiter(LockOwner waitingOwner) {
331            synchronized (waitingOwners) {
332                if (waitingOwners.remove(waitingOwner))
333                    waiters--;
334            }
335        }
336        
337        /**
338         * @see org.apache.commons.transaction.locking.MultiLevelLock#release(Object)
339         */
340        public synchronized boolean release(Object ownerId) {
341            if (owners.remove(ownerId) != null) {
342                if (logger.isFinerEnabled()) {
343                        logger.logFiner(
344                            ownerId.toString()
345                                + " releasing lock for "
346                                + resourceId.toString()
347                                + " at "
348                                + System.currentTimeMillis());
349                }
350                notifyAll();
351                return true;
352            }
353            return false;
354        }
355    
356        /**
357         * @see org.apache.commons.transaction.locking.MultiLevelLock#getLockLevel(Object)
358         */
359        public int getLockLevel(Object ownerId) {
360            LockOwner owner = (LockOwner) owners.get(ownerId);
361            if (owner == null) {
362                return 0;
363            } else {
364                return owner.lockLevel;
365            }
366        }
367    
368        /**
369         * Gets the resource assotiated to this lock. 
370         * 
371         * @return identifier for the resource associated to this lock 
372         */
373        public Object getResourceId() {
374            return resourceId;
375        }
376    
377        /**
378         * Gets the lowest lock level possible.
379         * 
380         * @return minimum lock level
381         */
382        public int getLevelMinLock() {
383            return 0;
384        }
385    
386        /**
387         * Gets the highst lock level possible.
388         * 
389         * @return maximum lock level
390         */
391        public int getLevelMaxLock() {
392            return maxLockLevel;
393        }
394    
395        public Object getOwner() {
396            LockOwner owner = getMaxLevelOwner();
397            if (owner == null)
398                return null;
399            return owner.ownerId;
400        }
401    
402        public synchronized String toString() {
403            StringBuffer buf = new StringBuffer();
404            buf.append(resourceId.toString()).append(":\n");
405    
406            for (Iterator it = owners.values().iterator(); it.hasNext();) {
407                LockOwner owner = (LockOwner) it.next();
408                buf.append("- ").append(owner.toString()).append("\n");
409            }
410    
411            if (waiters != 0) {
412                buf.append(waiters).append(" waiting:\n");
413                for (Iterator it = waitingOwners.iterator(); it.hasNext();) {
414                    LockOwner owner = (LockOwner) it.next();
415                    buf.append("- ").append(owner.toString()).append("\n");
416                }
417            }
418            
419            return buf.toString();
420        }
421    
422        protected synchronized LockOwner getMaxLevelOwner() {
423            return getMaxLevelOwner(null, -1, false);
424        }
425    
426        protected synchronized LockOwner getMaxLevelOwner(LockOwner reentrantOwner, boolean preferred) {
427            return getMaxLevelOwner(reentrantOwner, -1, preferred);
428        }
429    
430        protected synchronized LockOwner getMaxLevelOwner(int supportLockLevel, boolean preferred) {
431            return getMaxLevelOwner(null, supportLockLevel, preferred);
432        }
433    
434        protected synchronized LockOwner getMaxLevelOwner(LockOwner reentrantOwner,
435                int supportLockLevel, boolean preferred) {
436            LockOwner maxOwner = null;
437            for (Iterator it = owners.values().iterator(); it.hasNext();) {
438                LockOwner owner = (LockOwner) it.next();
439                if (owner.lockLevel != supportLockLevel && !owner.equals(reentrantOwner)
440                        && (maxOwner == null || maxOwner.lockLevel < owner.lockLevel)
441                        // if we are a preferred lock we must not interfere with other intention
442                        // locks as we otherwise might mututally lock without resolvation
443                        && !(preferred && owner.intention)) {
444                    maxOwner = owner;
445                }
446            }
447            return maxOwner;
448        }
449        
450        protected synchronized void setLockLevel(Object ownerId, LockOwner lock, int targetLockLevel,
451                int compatibility, boolean intention) {
452            // be sure there exists at most one lock per owner
453            if (lock != null) {
454                if (logger.isFinestEnabled()) {
455                        logger.logFinest(
456                            ownerId.toString()
457                                + " upgrading lock for "
458                                + resourceId.toString()
459                                + " to level "
460                                + targetLockLevel
461                                + " at "
462                                + System.currentTimeMillis());
463                }
464            } else {
465                if (logger.isFinestEnabled()) {
466                        logger.logFinest(
467                            ownerId.toString()
468                                + " getting new lock for "
469                                + resourceId.toString()
470                                + " at level "
471                                + targetLockLevel
472                                + " at "
473                                + System.currentTimeMillis());
474                }
475            }
476            owners.put(ownerId, new LockOwner(ownerId, targetLockLevel, compatibility, intention));
477        }
478    
479        protected boolean tryLock(Object ownerId, int targetLockLevel, int compatibility,
480                boolean preferred) {
481            return tryLock(ownerId, targetLockLevel, compatibility, preferred, false);
482        }
483    
484        protected synchronized boolean tryLock(Object ownerId, int targetLockLevel, int compatibility,
485                boolean preferred, boolean tryOnly) {
486    
487            LockOwner myLock = (LockOwner) owners.get(ownerId);
488    
489            // determine highest owner        
490            LockOwner highestOwner;
491            if (compatibility == COMPATIBILITY_REENTRANT) {
492                if (myLock != null && targetLockLevel <= myLock.lockLevel) {
493                    // we already have it
494                    return true;
495                } else {
496                    // our own lock will not be compromised by ourself
497                    highestOwner = getMaxLevelOwner(myLock, preferred);
498                }
499            } else if (compatibility == COMPATIBILITY_SUPPORT) {
500                // we are compatible with any other lock owner holding
501                // the same lock level
502                highestOwner = getMaxLevelOwner(targetLockLevel, preferred);
503    
504            } else if (compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT) {
505                if (myLock != null && targetLockLevel <= myLock.lockLevel) {
506                    // we already have it
507                    return true;
508                } else {
509                    // our own lock will not be compromised by ourself and same lock level 
510                    highestOwner = getMaxLevelOwner(myLock, targetLockLevel, preferred);
511                }
512            } else {
513                highestOwner = getMaxLevelOwner();
514            }
515    
516            int i;
517            // what is our current lock level?
518            int currentLockLevel;
519            if (highestOwner != null) {
520                currentLockLevel = highestOwner.lockLevel;
521            } else {
522                currentLockLevel = getLevelMinLock();
523            }
524    
525            // we are only allowed to acquire our locks if we do not compromise locks of any other lock owner
526            if (isCompatible(targetLockLevel, currentLockLevel)) {
527                if (!tryOnly) {
528                    // if we really have the lock, it no longer is an intention
529                    setLockLevel(ownerId, myLock, targetLockLevel, compatibility, false);
530                }
531                return true;
532            } else {
533                return false;
534            }
535        }
536    
537        protected boolean isCompatible(int targetLockLevel, int currentLockLevel) {
538            return (targetLockLevel <= getLevelMaxLock() - currentLockLevel);
539        }
540        
541        protected Set getConflictingOwners(Object ownerId, int targetLockLevel, int compatibility) {
542    
543            LockOwner myLock = (LockOwner) owners.get(ownerId);
544            if (myLock != null && targetLockLevel <= myLock.lockLevel) {
545                // shortcut as we already have the lock
546                return null;
547            }
548            
549            LockOwner testLock = new LockOwner(ownerId, targetLockLevel, compatibility, false);
550            List ownersCopy;
551            synchronized (owners) {
552                ownersCopy = new ArrayList(owners.values());
553            }
554            return getConflictingOwners(testLock, ownersCopy);
555            
556        }
557    
558        protected Collection getConflictingWaiters(Object ownerId) {
559            LockOwner owner = (LockOwner) owners.get(ownerId);
560            if (owner != null) {
561                List waiterCopy;
562                synchronized (waitingOwners) {
563                    waiterCopy = new ArrayList(waitingOwners);
564                }
565                Collection conflicts = getConflictingOwners(owner, waiterCopy);
566                return conflicts;
567            }
568            return null;
569        }
570        
571        protected Set getConflictingOwners(LockOwner myOwner, Collection ownersToTest) {
572    
573            if (myOwner == null) return null;
574            
575            Set conflicts = new HashSet();
576    
577            // check if any locks conflict with ours
578            for (Iterator it = ownersToTest.iterator(); it.hasNext();) {
579                LockOwner owner = (LockOwner) it.next();
580                
581                // we do not interfere with ourselves, except when explicitely said so
582                if ((myOwner.compatibility == COMPATIBILITY_REENTRANT || myOwner.compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT)
583                        && owner.ownerId.equals(myOwner.ownerId))
584                    continue;
585                
586                // otherwise find out the lock level of the owner and see if we conflict with it
587                int onwerLockLevel = owner.lockLevel;
588               
589                if (myOwner.compatibility == COMPATIBILITY_SUPPORT
590                        || myOwner.compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT
591                        && myOwner.lockLevel == onwerLockLevel)
592                    continue;
593                
594                if (!isCompatible(myOwner.lockLevel, onwerLockLevel)) {
595                    conflicts.add(owner.ownerId);
596                }
597            }
598            return (conflicts.isEmpty() ? null : conflicts);
599        }
600    
601        protected static class LockOwner {
602            public final Object ownerId;
603            public final int lockLevel;
604            public final boolean intention;
605            public final int compatibility;
606    
607            public LockOwner(Object ownerId, int lockLevel, int compatibility, boolean intention) {
608                this.ownerId = ownerId;
609                this.lockLevel = lockLevel;
610                this.intention = intention;
611                this.compatibility = compatibility;
612            }
613    
614            public String toString() {
615                StringBuffer buf = new StringBuffer();
616                buf.append(ownerId.toString()).append(": level ").append(lockLevel).append(", complevel ")
617                        .append(compatibility).append(intention ? ", intention/preferred" : "");
618                return buf.toString();
619            }
620            
621            public boolean equals(Object o) {
622                if (o instanceof LockOwner) {
623                    return ((LockOwner)o).ownerId.equals(ownerId);
624                }
625                return false;
626            }
627            
628            public int hashCode() {
629                return ownerId.hashCode();
630            }
631        }
632    
633    }