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.pool2.impl;
018
019import java.util.ArrayList;
020import java.util.Deque;
021import java.util.HashMap;
022import java.util.Iterator;
023import java.util.List;
024import java.util.Map;
025import java.util.Map.Entry;
026import java.util.NoSuchElementException;
027import java.util.TreeMap;
028import java.util.concurrent.ConcurrentHashMap;
029import java.util.concurrent.TimeUnit;
030import java.util.concurrent.atomic.AtomicInteger;
031import java.util.concurrent.atomic.AtomicLong;
032import java.util.concurrent.locks.Lock;
033import java.util.concurrent.locks.ReadWriteLock;
034import java.util.concurrent.locks.ReentrantReadWriteLock;
035
036import org.apache.commons.pool2.KeyedObjectPool;
037import org.apache.commons.pool2.KeyedPooledObjectFactory;
038import org.apache.commons.pool2.PoolUtils;
039import org.apache.commons.pool2.PooledObject;
040import org.apache.commons.pool2.PooledObjectState;
041import org.apache.commons.pool2.SwallowedExceptionListener;
042
043/**
044 * A configurable <code>KeyedObjectPool</code> implementation.
045 * <p>
046 * When coupled with the appropriate {@link KeyedPooledObjectFactory},
047 * <code>GenericKeyedObjectPool</code> provides robust pooling functionality for
048 * keyed objects. A <code>GenericKeyedObjectPool</code> can be viewed as a map
049 * of sub-pools, keyed on the (unique) key values provided to the
050 * {@link #preparePool preparePool}, {@link #addObject addObject} or
051 * {@link #borrowObject borrowObject} methods. Each time a new key value is
052 * provided to one of these methods, a sub-new pool is created under the given
053 * key to be managed by the containing <code>GenericKeyedObjectPool.</code>
054 * </p>
055 * <p>
056 * Note that the current implementation uses a ConcurrentHashMap which uses
057 * equals() to compare keys.
058 * This means that distinct instance keys must be distinguishable using equals.
059 * </p>
060 * <p>
061 * Optionally, one may configure the pool to examine and possibly evict objects
062 * as they sit idle in the pool and to ensure that a minimum number of idle
063 * objects is maintained for each key. This is performed by an "idle object
064 * eviction" thread, which runs asynchronously. Caution should be used when
065 * configuring this optional feature. Eviction runs contend with client threads
066 * for access to objects in the pool, so if they run too frequently performance
067 * issues may result.
068 * </p>
069 * <p>
070 * Implementation note: To prevent possible deadlocks, care has been taken to
071 * ensure that no call to a factory method will occur within a synchronization
072 * block. See POOL-125 and DBCP-44 for more information.
073 * </p>
074 * <p>
075 * This class is intended to be thread-safe.
076 * </p>
077 *
078 * @see GenericObjectPool
079 *
080 * @param <K> The type of keys maintained by this pool.
081 * @param <T> Type of element pooled in this pool.
082 *
083 * @since 2.0
084 */
085public class GenericKeyedObjectPool<K, T> extends BaseGenericObjectPool<T>
086        implements KeyedObjectPool<K, T>, GenericKeyedObjectPoolMXBean<K> {
087
088    /**
089     * Create a new <code>GenericKeyedObjectPool</code> using defaults from
090     * {@link GenericKeyedObjectPoolConfig}.
091     * @param factory the factory to be used to create entries
092     */
093    public GenericKeyedObjectPool(final KeyedPooledObjectFactory<K, T> factory) {
094        this(factory, new GenericKeyedObjectPoolConfig<T>());
095    }
096
097    /**
098     * Create a new <code>GenericKeyedObjectPool</code> using a specific
099     * configuration.
100     *
101     * @param factory the factory to be used to create entries
102     * @param config    The configuration to use for this pool instance. The
103     *                  configuration is used by value. Subsequent changes to
104     *                  the configuration object will not be reflected in the
105     *                  pool.
106     */
107    public GenericKeyedObjectPool(final KeyedPooledObjectFactory<K, T> factory,
108            final GenericKeyedObjectPoolConfig<T> config) {
109
110        super(config, ONAME_BASE, config.getJmxNamePrefix());
111
112        if (factory == null) {
113            jmxUnregister(); // tidy up
114            throw new IllegalArgumentException("factory may not be null");
115        }
116        this.factory = factory;
117        this.fairness = config.getFairness();
118
119        setConfig(config);
120    }
121
122    /**
123     * Returns the limit on the number of object instances allocated by the pool
124     * (checked out or idle), per key. When the limit is reached, the sub-pool
125     * is said to be exhausted. A negative value indicates no limit.
126     *
127     * @return the limit on the number of active instances per key
128     *
129     * @see #setMaxTotalPerKey
130     */
131    @Override
132    public int getMaxTotalPerKey() {
133        return maxTotalPerKey;
134    }
135
136    /**
137     * Sets the limit on the number of object instances allocated by the pool
138     * (checked out or idle), per key. When the limit is reached, the sub-pool
139     * is said to be exhausted. A negative value indicates no limit.
140     *
141     * @param maxTotalPerKey the limit on the number of active instances per key
142     *
143     * @see #getMaxTotalPerKey
144     */
145    public void setMaxTotalPerKey(final int maxTotalPerKey) {
146        this.maxTotalPerKey = maxTotalPerKey;
147    }
148
149
150    /**
151     * Returns the cap on the number of "idle" instances per key in the pool.
152     * If maxIdlePerKey is set too low on heavily loaded systems it is possible
153     * you will see objects being destroyed and almost immediately new objects
154     * being created. This is a result of the active threads momentarily
155     * returning objects faster than they are requesting them, causing the
156     * number of idle objects to rise above maxIdlePerKey. The best value for
157     * maxIdlePerKey for heavily loaded system will vary but the default is a
158     * good starting point.
159     *
160     * @return the maximum number of "idle" instances that can be held in a
161     *         given keyed sub-pool or a negative value if there is no limit
162     *
163     * @see #setMaxIdlePerKey
164     */
165    @Override
166    public int getMaxIdlePerKey() {
167        return maxIdlePerKey;
168    }
169
170    /**
171     * Sets the cap on the number of "idle" instances per key in the pool.
172     * If maxIdlePerKey is set too low on heavily loaded systems it is possible
173     * you will see objects being destroyed and almost immediately new objects
174     * being created. This is a result of the active threads momentarily
175     * returning objects faster than they are requesting them, causing the
176     * number of idle objects to rise above maxIdlePerKey. The best value for
177     * maxIdlePerKey for heavily loaded system will vary but the default is a
178     * good starting point.
179     *
180     * @param maxIdlePerKey the maximum number of "idle" instances that can be
181     *                      held in a given keyed sub-pool. Use a negative value
182     *                      for no limit
183     *
184     * @see #getMaxIdlePerKey
185     */
186    public void setMaxIdlePerKey(final int maxIdlePerKey) {
187        this.maxIdlePerKey = maxIdlePerKey;
188    }
189
190    /**
191     * Sets the target for the minimum number of idle objects to maintain in
192     * each of the keyed sub-pools. This setting only has an effect if it is
193     * positive and {@link #getTimeBetweenEvictionRunsMillis()} is greater than
194     * zero. If this is the case, an attempt is made to ensure that each
195     * sub-pool has the required minimum number of instances during idle object
196     * eviction runs.
197     * <p>
198     * If the configured value of minIdlePerKey is greater than the configured
199     * value for maxIdlePerKey then the value of maxIdlePerKey will be used
200     * instead.
201     *
202     * @param minIdlePerKey The minimum size of the each keyed pool
203     *
204     * @see #getMinIdlePerKey
205     * @see #getMaxIdlePerKey()
206     * @see #setTimeBetweenEvictionRunsMillis
207     */
208    public void setMinIdlePerKey(final int minIdlePerKey) {
209        this.minIdlePerKey = minIdlePerKey;
210    }
211
212    /**
213     * Returns the target for the minimum number of idle objects to maintain in
214     * each of the keyed sub-pools. This setting only has an effect if it is
215     * positive and {@link #getTimeBetweenEvictionRunsMillis()} is greater than
216     * zero. If this is the case, an attempt is made to ensure that each
217     * sub-pool has the required minimum number of instances during idle object
218     * eviction runs.
219     * <p>
220     * If the configured value of minIdlePerKey is greater than the configured
221     * value for maxIdlePerKey then the value of maxIdlePerKey will be used
222     * instead.
223     *
224     * @return minimum size of the each keyed pool
225     *
226     * @see #setTimeBetweenEvictionRunsMillis
227     */
228    @Override
229    public int getMinIdlePerKey() {
230        final int maxIdlePerKeySave = getMaxIdlePerKey();
231        if (this.minIdlePerKey > maxIdlePerKeySave) {
232            return maxIdlePerKeySave;
233        }
234        return minIdlePerKey;
235    }
236
237    /**
238     * Sets the configuration.
239     *
240     * @param conf the new configuration to use. This is used by value.
241     *
242     * @see GenericKeyedObjectPoolConfig
243     */
244    public void setConfig(final GenericKeyedObjectPoolConfig<T> conf) {
245        super.setConfig(conf);
246        setMaxIdlePerKey(conf.getMaxIdlePerKey());
247        setMaxTotalPerKey(conf.getMaxTotalPerKey());
248        setMaxTotal(conf.getMaxTotal());
249        setMinIdlePerKey(conf.getMinIdlePerKey());
250    }
251
252    /**
253     * Obtain a reference to the factory used to create, destroy and validate
254     * the objects used by this pool.
255     *
256     * @return the factory
257     */
258    public KeyedPooledObjectFactory<K, T> getFactory() {
259        return factory;
260    }
261
262    /**
263     * Equivalent to <code>{@link #borrowObject(Object, long) borrowObject}(key,
264     * {@link #getMaxWaitMillis()})</code>.
265     * <p>
266     * {@inheritDoc}
267     */
268    @Override
269    public T borrowObject(final K key) throws Exception {
270        return borrowObject(key, getMaxWaitMillis());
271    }
272
273    /**
274     * Borrows an object from the sub-pool associated with the given key using
275     * the specified waiting time which only applies if
276     * {@link #getBlockWhenExhausted()} is true.
277     * <p>
278     * If there is one or more idle instances available in the sub-pool
279     * associated with the given key, then an idle instance will be selected
280     * based on the value of {@link #getLifo()}, activated and returned.  If
281     * activation fails, or {@link #getTestOnBorrow() testOnBorrow} is set to
282     * <code>true</code> and validation fails, the instance is destroyed and the
283     * next available instance is examined.  This continues until either a valid
284     * instance is returned or there are no more idle instances available.
285     * <p>
286     * If there are no idle instances available in the sub-pool associated with
287     * the given key, behavior depends on the {@link #getMaxTotalPerKey()
288     * maxTotalPerKey}, {@link #getMaxTotal() maxTotal}, and (if applicable)
289     * {@link #getBlockWhenExhausted()} and the value passed in to the
290     * <code>borrowMaxWaitMillis</code> parameter. If the number of instances checked
291     * out from the sub-pool under the given key is less than
292     * <code>maxTotalPerKey</code> and the total number of instances in
293     * circulation (under all keys) is less than <code>maxTotal</code>, a new
294     * instance is created, activated and (if applicable) validated and returned
295     * to the caller. If validation fails, a <code>NoSuchElementException</code>
296     * will be thrown.
297     * <p>
298     * If the associated sub-pool is exhausted (no available idle instances and
299     * no capacity to create new ones), this method will either block
300     * ({@link #getBlockWhenExhausted()} is true) or throw a
301     * <code>NoSuchElementException</code>
302     * ({@link #getBlockWhenExhausted()} is false).
303     * The length of time that this method will block when
304     * {@link #getBlockWhenExhausted()} is true is determined by the value
305     * passed in to the <code>borrowMaxWait</code> parameter.
306     * <p>
307     * When <code>maxTotal</code> is set to a positive value and this method is
308     * invoked when at the limit with no idle instances available under the requested
309     * key, an attempt is made to create room by clearing the oldest 15% of the
310     * elements from the keyed sub-pools.
311     * <p>
312     * When the pool is exhausted, multiple calling threads may be
313     * simultaneously blocked waiting for instances to become available. A
314     * "fairness" algorithm has been implemented to ensure that threads receive
315     * available instances in request arrival order.
316     *
317     * @param key pool key
318     * @param borrowMaxWaitMillis The time to wait in milliseconds for an object
319     *                            to become available
320     *
321     * @return object instance from the keyed pool
322     *
323     * @throws NoSuchElementException if a keyed object instance cannot be
324     *                                returned because the pool is exhausted.
325     *
326     * @throws Exception if a keyed object instance cannot be returned due to an
327     *                   error
328     */
329    public T borrowObject(final K key, final long borrowMaxWaitMillis) throws Exception {
330        assertOpen();
331
332        PooledObject<T> p = null;
333
334        // Get local copy of current config so it is consistent for entire
335        // method execution
336        final boolean blockWhenExhausted = getBlockWhenExhausted();
337
338        boolean create;
339        final long waitTime = System.currentTimeMillis();
340        final ObjectDeque<T> objectDeque = register(key);
341
342        try {
343            while (p == null) {
344                create = false;
345                p = objectDeque.getIdleObjects().pollFirst();
346                if (p == null) {
347                    p = create(key);
348                    if (p != null) {
349                        create = true;
350                    }
351                }
352                if (blockWhenExhausted) {
353                    if (p == null) {
354                        if (borrowMaxWaitMillis < 0) {
355                            p = objectDeque.getIdleObjects().takeFirst();
356                        } else {
357                            p = objectDeque.getIdleObjects().pollFirst(
358                                    borrowMaxWaitMillis, TimeUnit.MILLISECONDS);
359                        }
360                    }
361                    if (p == null) {
362                        throw new NoSuchElementException(
363                                "Timeout waiting for idle object");
364                    }
365                } else {
366                    if (p == null) {
367                        throw new NoSuchElementException("Pool exhausted");
368                    }
369                }
370                if (!p.allocate()) {
371                    p = null;
372                }
373
374                if (p != null) {
375                    try {
376                        factory.activateObject(key, p);
377                    } catch (final Exception e) {
378                        try {
379                            destroy(key, p, true);
380                        } catch (final Exception e1) {
381                            // Ignore - activation failure is more important
382                        }
383                        p = null;
384                        if (create) {
385                            final NoSuchElementException nsee = new NoSuchElementException(
386                                    "Unable to activate object");
387                            nsee.initCause(e);
388                            throw nsee;
389                        }
390                    }
391                    if (p != null && getTestOnBorrow()) {
392                        boolean validate = false;
393                        Throwable validationThrowable = null;
394                        try {
395                            validate = factory.validateObject(key, p);
396                        } catch (final Throwable t) {
397                            PoolUtils.checkRethrow(t);
398                            validationThrowable = t;
399                        }
400                        if (!validate) {
401                            try {
402                                destroy(key, p, true);
403                                destroyedByBorrowValidationCount.incrementAndGet();
404                            } catch (final Exception e) {
405                                // Ignore - validation failure is more important
406                            }
407                            p = null;
408                            if (create) {
409                                final NoSuchElementException nsee = new NoSuchElementException(
410                                        "Unable to validate object");
411                                nsee.initCause(validationThrowable);
412                                throw nsee;
413                            }
414                        }
415                    }
416                }
417            }
418        } finally {
419            deregister(key);
420        }
421
422        updateStatsBorrow(p, System.currentTimeMillis() - waitTime);
423
424        return p.getObject();
425    }
426
427
428    /**
429     * Returns an object to a keyed sub-pool.
430     * <p>
431     * If {@link #getMaxIdlePerKey() maxIdle} is set to a positive value and the
432     * number of idle instances under the given key has reached this value, the
433     * returning instance is destroyed.
434     * <p>
435     * If {@link #getTestOnReturn() testOnReturn} == true, the returning
436     * instance is validated before being returned to the idle instance sub-pool
437     * under the given key. In this case, if validation fails, the instance is
438     * destroyed.
439     * <p>
440     * Exceptions encountered destroying objects for any reason are swallowed
441     * but notified via a {@link SwallowedExceptionListener}.
442     *
443     * @param key pool key
444     * @param obj instance to return to the keyed pool
445     *
446     * @throws IllegalStateException if an object is returned to the pool that
447     *                               was not borrowed from it or if an object is
448     *                               returned to the pool multiple times
449     */
450    @Override
451    public void returnObject(final K key, final T obj) {
452
453        final ObjectDeque<T> objectDeque = poolMap.get(key);
454
455        if (objectDeque == null) {
456            throw new IllegalStateException(
457                    "No keyed pool found under the given key.");
458        }
459
460        final PooledObject<T> p = objectDeque.getAllObjects().get(new IdentityWrapper<>(obj));
461
462        if (p == null) {
463            throw new IllegalStateException(
464                    "Returned object not currently part of this pool");
465        }
466
467        markReturningState(p);
468
469        final long activeTime = p.getActiveTimeMillis();
470
471        try {
472            if (getTestOnReturn() && !factory.validateObject(key, p)) {
473                try {
474                    destroy(key, p, true);
475                } catch (final Exception e) {
476                    swallowException(e);
477                }
478                whenWaitersAddObject(key, objectDeque.idleObjects);
479                return;
480            }
481
482            try {
483                factory.passivateObject(key, p);
484            } catch (final Exception e1) {
485                swallowException(e1);
486                try {
487                    destroy(key, p, true);
488                } catch (final Exception e) {
489                    swallowException(e);
490                }
491                whenWaitersAddObject(key, objectDeque.idleObjects);
492                return;
493            }
494
495            if (!p.deallocate()) {
496                throw new IllegalStateException(
497                        "Object has already been returned to this pool");
498            }
499
500            final int maxIdle = getMaxIdlePerKey();
501            final LinkedBlockingDeque<PooledObject<T>> idleObjects =
502                    objectDeque.getIdleObjects();
503
504            if (isClosed() || maxIdle > -1 && maxIdle <= idleObjects.size()) {
505                try {
506                    destroy(key, p, true);
507                } catch (final Exception e) {
508                    swallowException(e);
509                }
510            } else {
511                if (getLifo()) {
512                    idleObjects.addFirst(p);
513                } else {
514                    idleObjects.addLast(p);
515                }
516                if (isClosed()) {
517                    // Pool closed while object was being added to idle objects.
518                    // Make sure the returned object is destroyed rather than left
519                    // in the idle object pool (which would effectively be a leak)
520                    clear(key);
521                }
522            }
523        } finally {
524            if (hasBorrowWaiters()) {
525                reuseCapacity();
526            }
527            updateStatsReturn(activeTime);
528        }
529    }
530
531    /**
532     * Whether there is at least one thread waiting on this deque, add an pool object.
533     * @param key pool key.
534     * @param idleObjects list of idle pool objects.
535     */
536    private void whenWaitersAddObject(final K key, final LinkedBlockingDeque<PooledObject<T>> idleObjects) {
537        if (idleObjects.hasTakeWaiters()) {
538            try {
539                addObject(key);
540            } catch (final Exception e) {
541                swallowException(e);
542            }
543        }
544    }
545
546    /**
547     * {@inheritDoc}
548     * <p>
549     * Activation of this method decrements the active count associated with
550     * the given keyed pool and attempts to destroy <code>obj.</code>
551     *
552     * @param key pool key
553     * @param obj instance to invalidate
554     *
555     * @throws Exception             if an exception occurs destroying the
556     *                               object
557     * @throws IllegalStateException if obj does not belong to the pool
558     *                               under the given key
559     */
560    @Override
561    public void invalidateObject(final K key, final T obj) throws Exception {
562
563        final ObjectDeque<T> objectDeque = poolMap.get(key);
564
565        final PooledObject<T> p = objectDeque.getAllObjects().get(new IdentityWrapper<>(obj));
566        if (p == null) {
567            throw new IllegalStateException(
568                    "Object not currently part of this pool");
569        }
570        synchronized (p) {
571            if (p.getState() != PooledObjectState.INVALID) {
572                destroy(key, p, true);
573            }
574        }
575        if (objectDeque.idleObjects.hasTakeWaiters()) {
576            addObject(key);
577        }
578    }
579
580
581    /**
582     * Clears any objects sitting idle in the pool by removing them from the
583     * idle instance sub-pools and then invoking the configured
584     * PoolableObjectFactory's
585     * {@link KeyedPooledObjectFactory#destroyObject(Object, PooledObject)}
586     * method on each idle instance.
587     * <p>
588     * Implementation notes:
589     * <ul>
590     * <li>This method does not destroy or effect in any way instances that are
591     * checked out when it is invoked.</li>
592     * <li>Invoking this method does not prevent objects being returned to the
593     * idle instance pool, even during its execution. Additional instances may
594     * be returned while removed items are being destroyed.</li>
595     * <li>Exceptions encountered destroying idle instances are swallowed
596     * but notified via a {@link SwallowedExceptionListener}.</li>
597     * </ul>
598     */
599    @Override
600    public void clear() {
601        final Iterator<K> iter = poolMap.keySet().iterator();
602
603        while (iter.hasNext()) {
604            clear(iter.next());
605        }
606    }
607
608
609    /**
610     * Clears the specified sub-pool, removing all pooled instances
611     * corresponding to the given <code>key</code>. Exceptions encountered
612     * destroying idle instances are swallowed but notified via a
613     * {@link SwallowedExceptionListener}.
614     *
615     * @param key the key to clear
616     */
617    @Override
618    public void clear(final K key) {
619
620        final ObjectDeque<T> objectDeque = register(key);
621
622        try {
623            final LinkedBlockingDeque<PooledObject<T>> idleObjects =
624                    objectDeque.getIdleObjects();
625
626            PooledObject<T> p = idleObjects.poll();
627
628            while (p != null) {
629                try {
630                    destroy(key, p, true);
631                } catch (final Exception e) {
632                    swallowException(e);
633                }
634                p = idleObjects.poll();
635            }
636        } finally {
637            deregister(key);
638        }
639    }
640
641
642    @Override
643    public int getNumActive() {
644        return numTotal.get() - getNumIdle();
645    }
646
647
648    @Override
649    public int getNumIdle() {
650        final Iterator<ObjectDeque<T>> iter = poolMap.values().iterator();
651        int result = 0;
652
653        while (iter.hasNext()) {
654            result += iter.next().getIdleObjects().size();
655        }
656
657        return result;
658    }
659
660
661    @Override
662    public int getNumActive(final K key) {
663        final ObjectDeque<T> objectDeque = poolMap.get(key);
664        if (objectDeque != null) {
665            return objectDeque.getAllObjects().size() -
666                    objectDeque.getIdleObjects().size();
667        }
668        return 0;
669    }
670
671
672    @Override
673    public int getNumIdle(final K key) {
674        final ObjectDeque<T> objectDeque = poolMap.get(key);
675        return objectDeque != null ? objectDeque.getIdleObjects().size() : 0;
676    }
677
678
679    /**
680     * Closes the keyed object pool. Once the pool is closed,
681     * {@link #borrowObject(Object)} will fail with IllegalStateException, but
682     * {@link #returnObject(Object, Object)} and
683     * {@link #invalidateObject(Object, Object)} will continue to work, with
684     * returned objects destroyed on return.
685     * <p>
686     * Destroys idle instances in the pool by invoking {@link #clear()}.
687     */
688    @Override
689    public void close() {
690        if (isClosed()) {
691            return;
692        }
693
694        synchronized (closeLock) {
695            if (isClosed()) {
696                return;
697            }
698
699            // Stop the evictor before the pool is closed since evict() calls
700            // assertOpen()
701            stopEvictor();
702
703            closed = true;
704            // This clear removes any idle objects
705            clear();
706
707            jmxUnregister();
708
709            // Release any threads that were waiting for an object
710            final Iterator<ObjectDeque<T>> iter = poolMap.values().iterator();
711            while (iter.hasNext()) {
712                iter.next().getIdleObjects().interuptTakeWaiters();
713            }
714            // This clear cleans up the keys now any waiting threads have been
715            // interrupted
716            clear();
717        }
718    }
719
720
721    /**
722     * Clears oldest 15% of objects in pool.  The method sorts the objects into
723     * a TreeMap and then iterates the first 15% for removal.
724     */
725    public void clearOldest() {
726
727        // build sorted map of idle objects
728        final Map<PooledObject<T>, K> map = new TreeMap<>();
729
730        for (final Map.Entry<K, ObjectDeque<T>> entry : poolMap.entrySet()) {
731            final K k = entry.getKey();
732            final ObjectDeque<T> deque = entry.getValue();
733            // Protect against possible NPE if key has been removed in another
734            // thread. Not worth locking the keys while this loop completes.
735            if (deque != null) {
736                final LinkedBlockingDeque<PooledObject<T>> idleObjects =
737                        deque.getIdleObjects();
738                for (final PooledObject<T> p : idleObjects) {
739                    // each item into the map using the PooledObject object as the
740                    // key. It then gets sorted based on the idle time
741                    map.put(p, k);
742                }
743            }
744        }
745
746        // Now iterate created map and kill the first 15% plus one to account
747        // for zero
748        int itemsToRemove = ((int) (map.size() * 0.15)) + 1;
749        final Iterator<Map.Entry<PooledObject<T>, K>> iter =
750                map.entrySet().iterator();
751
752        while (iter.hasNext() && itemsToRemove > 0) {
753            final Map.Entry<PooledObject<T>, K> entry = iter.next();
754            // kind of backwards on naming.  In the map, each key is the
755            // PooledObject because it has the ordering with the timestamp
756            // value.  Each value that the key references is the key of the
757            // list it belongs to.
758            final K key = entry.getValue();
759            final PooledObject<T> p = entry.getKey();
760            // Assume the destruction succeeds
761            boolean destroyed = true;
762            try {
763                destroyed = destroy(key, p, false);
764            } catch (final Exception e) {
765                swallowException(e);
766            }
767            if (destroyed) {
768                itemsToRemove--;
769            }
770        }
771    }
772
773    /**
774     * Attempt to create one new instance to serve from the most heavily
775     * loaded pool that can add a new instance.
776     *
777     * This method exists to ensure liveness in the pool when threads are
778     * parked waiting and capacity to create instances under the requested keys
779     * subsequently becomes available.
780     *
781     * This method is not guaranteed to create an instance and its selection
782     * of the most loaded pool that can create an instance may not always be
783     * correct, since it does not lock the pool and instances may be created,
784     * borrowed, returned or destroyed by other threads while it is executing.
785     */
786    private void reuseCapacity() {
787        final int maxTotalPerKeySave = getMaxTotalPerKey();
788
789        // Find the most loaded pool that could take a new instance
790        int maxQueueLength = 0;
791        LinkedBlockingDeque<PooledObject<T>> mostLoaded = null;
792        K loadedKey = null;
793        for (final Map.Entry<K, ObjectDeque<T>> entry : poolMap.entrySet()) {
794            final K k = entry.getKey();
795            final ObjectDeque<T> deque = entry.getValue();
796            if (deque != null) {
797                final LinkedBlockingDeque<PooledObject<T>> pool = deque.getIdleObjects();
798                final int queueLength = pool.getTakeQueueLength();
799                if (getNumActive(k) < maxTotalPerKeySave && queueLength > maxQueueLength) {
800                    maxQueueLength = queueLength;
801                    mostLoaded = pool;
802                    loadedKey = k;
803                }
804            }
805        }
806
807        // Attempt to add an instance to the most loaded pool
808        if (mostLoaded != null) {
809            register(loadedKey);
810            try {
811                final PooledObject<T> p = create(loadedKey);
812                if (p != null) {
813                    addIdleObject(loadedKey, p);
814                }
815            } catch (final Exception e) {
816                swallowException(e);
817            } finally {
818                deregister(loadedKey);
819            }
820        }
821    }
822
823    /**
824     * Checks to see if there are any threads currently waiting to borrow
825     * objects but are blocked waiting for more objects to become available.
826     *
827     * @return {@code true} if there is at least one thread waiting otherwise
828     *         {@code false}
829     */
830    private boolean hasBorrowWaiters() {
831        for (final Map.Entry<K, ObjectDeque<T>> entry : poolMap.entrySet()) {
832            final ObjectDeque<T> deque = entry.getValue();
833            if (deque != null) {
834                final LinkedBlockingDeque<PooledObject<T>> pool =
835                        deque.getIdleObjects();
836                if(pool.hasTakeWaiters()) {
837                    return true;
838                }
839            }
840        }
841        return false;
842    }
843
844
845    /**
846     * {@inheritDoc}
847     * <p>
848     * Successive activations of this method examine objects in keyed sub-pools
849     * in sequence, cycling through the keys and examining objects in
850     * oldest-to-youngest order within the keyed sub-pools.
851     */
852    @Override
853    public void evict() throws Exception {
854        assertOpen();
855
856        if (getNumIdle() == 0) {
857            return;
858        }
859
860        PooledObject<T> underTest = null;
861        final EvictionPolicy<T> evictionPolicy = getEvictionPolicy();
862
863        synchronized (evictionLock) {
864            final EvictionConfig evictionConfig = new EvictionConfig(
865                    getMinEvictableIdleTimeMillis(),
866                    getSoftMinEvictableIdleTimeMillis(),
867                    getMinIdlePerKey());
868
869            final boolean testWhileIdle = getTestWhileIdle();
870
871            for (int i = 0, m = getNumTests(); i < m; i++) {
872                if(evictionIterator == null || !evictionIterator.hasNext()) {
873                    if (evictionKeyIterator == null ||
874                            !evictionKeyIterator.hasNext()) {
875                        final List<K> keyCopy = new ArrayList<>();
876                        final Lock readLock = keyLock.readLock();
877                        readLock.lock();
878                        try {
879                            keyCopy.addAll(poolKeyList);
880                        } finally {
881                            readLock.unlock();
882                        }
883                        evictionKeyIterator = keyCopy.iterator();
884                    }
885                    while (evictionKeyIterator.hasNext()) {
886                        evictionKey = evictionKeyIterator.next();
887                        final ObjectDeque<T> objectDeque = poolMap.get(evictionKey);
888                        if (objectDeque == null) {
889                            continue;
890                        }
891
892                        final Deque<PooledObject<T>> idleObjects = objectDeque.getIdleObjects();
893                        evictionIterator = new EvictionIterator(idleObjects);
894                        if (evictionIterator.hasNext()) {
895                            break;
896                        }
897                        evictionIterator = null;
898                    }
899                }
900                if (evictionIterator == null) {
901                    // Pools exhausted
902                    return;
903                }
904                final Deque<PooledObject<T>> idleObjects;
905                try {
906                    underTest = evictionIterator.next();
907                    idleObjects = evictionIterator.getIdleObjects();
908                } catch (final NoSuchElementException nsee) {
909                    // Object was borrowed in another thread
910                    // Don't count this as an eviction test so reduce i;
911                    i--;
912                    evictionIterator = null;
913                    continue;
914                }
915
916                if (!underTest.startEvictionTest()) {
917                    // Object was borrowed in another thread
918                    // Don't count this as an eviction test so reduce i;
919                    i--;
920                    continue;
921                }
922
923                // User provided eviction policy could throw all sorts of
924                // crazy exceptions. Protect against such an exception
925                // killing the eviction thread.
926                boolean evict;
927                try {
928                    evict = evictionPolicy.evict(evictionConfig, underTest,
929                            poolMap.get(evictionKey).getIdleObjects().size());
930                } catch (final Throwable t) {
931                    // Slightly convoluted as SwallowedExceptionListener
932                    // uses Exception rather than Throwable
933                    PoolUtils.checkRethrow(t);
934                    swallowException(new Exception(t));
935                    // Don't evict on error conditions
936                    evict = false;
937                }
938
939                if (evict) {
940                    destroy(evictionKey, underTest, true);
941                    destroyedByEvictorCount.incrementAndGet();
942                } else {
943                    if (testWhileIdle) {
944                        boolean active = false;
945                        try {
946                            factory.activateObject(evictionKey, underTest);
947                            active = true;
948                        } catch (final Exception e) {
949                            destroy(evictionKey, underTest, true);
950                            destroyedByEvictorCount.incrementAndGet();
951                        }
952                        if (active) {
953                            if (!factory.validateObject(evictionKey, underTest)) {
954                                destroy(evictionKey, underTest, true);
955                                destroyedByEvictorCount.incrementAndGet();
956                            } else {
957                                try {
958                                    factory.passivateObject(evictionKey, underTest);
959                                } catch (final Exception e) {
960                                    destroy(evictionKey, underTest, true);
961                                    destroyedByEvictorCount.incrementAndGet();
962                                }
963                            }
964                        }
965                    }
966                    if (!underTest.endEvictionTest(idleObjects)) {
967                        // TODO - May need to add code here once additional
968                        // states are used
969                    }
970                }
971            }
972        }
973    }
974
975    /**
976     * Create a new pooled object.
977     *
978     * @param key Key associated with new pooled object
979     *
980     * @return The new, wrapped pooled object
981     *
982     * @throws Exception If the objection creation fails
983     */
984    private PooledObject<T> create(final K key) throws Exception {
985        int maxTotalPerKeySave = getMaxTotalPerKey(); // Per key
986        if (maxTotalPerKeySave < 0) {
987            maxTotalPerKeySave = Integer.MAX_VALUE;
988        }
989        final int maxTotal = getMaxTotal();   // All keys
990
991        final ObjectDeque<T> objectDeque = poolMap.get(key);
992
993        // Check against the overall limit
994        boolean loop = true;
995
996        while (loop) {
997            final int newNumTotal = numTotal.incrementAndGet();
998            if (maxTotal > -1 && newNumTotal > maxTotal) {
999                numTotal.decrementAndGet();
1000                if (getNumIdle() == 0) {
1001                    return null;
1002                }
1003                clearOldest();
1004            } else {
1005                loop = false;
1006            }
1007        }
1008
1009        // Flag that indicates if create should:
1010        // - TRUE:  call the factory to create an object
1011        // - FALSE: return null
1012        // - null:  loop and re-test the condition that determines whether to
1013        //          call the factory
1014        Boolean create = null;
1015        while (create == null) {
1016            synchronized (objectDeque.makeObjectCountLock) {
1017                final long newCreateCount = objectDeque.getCreateCount().incrementAndGet();
1018                // Check against the per key limit
1019                if (newCreateCount > maxTotalPerKeySave) {
1020                    // The key is currently at capacity or in the process of
1021                    // making enough new objects to take it to capacity.
1022                    objectDeque.getCreateCount().decrementAndGet();
1023                    if (objectDeque.makeObjectCount == 0) {
1024                        // There are no makeObject() calls in progress for this
1025                        // key so the key is at capacity. Do not attempt to
1026                        // create a new object. Return and wait for an object to
1027                        // be returned.
1028                        create = Boolean.FALSE;
1029                    } else {
1030                        // There are makeObject() calls in progress that might
1031                        // bring the pool to capacity. Those calls might also
1032                        // fail so wait until they complete and then re-test if
1033                        // the pool is at capacity or not.
1034                        objectDeque.makeObjectCountLock.wait();
1035                    }
1036                } else {
1037                    // The pool is not at capacity. Create a new object.
1038                    objectDeque.makeObjectCount++;
1039                    create = Boolean.TRUE;
1040                }
1041            }
1042        }
1043
1044        if (!create.booleanValue()) {
1045            numTotal.decrementAndGet();
1046            return null;
1047        }
1048
1049        PooledObject<T> p = null;
1050        try {
1051            p = factory.makeObject(key);
1052            if (getTestOnCreate() && !factory.validateObject(key, p)) {
1053                numTotal.decrementAndGet();
1054                objectDeque.getCreateCount().decrementAndGet();
1055                return null;
1056            }
1057        } catch (final Exception e) {
1058            numTotal.decrementAndGet();
1059            objectDeque.getCreateCount().decrementAndGet();
1060            throw e;
1061        } finally {
1062            synchronized (objectDeque.makeObjectCountLock) {
1063                objectDeque.makeObjectCount--;
1064                objectDeque.makeObjectCountLock.notifyAll();
1065            }
1066        }
1067
1068        createdCount.incrementAndGet();
1069        objectDeque.getAllObjects().put(new IdentityWrapper<>(p.getObject()), p);
1070        return p;
1071    }
1072
1073    /**
1074     * Destroy the wrapped, pooled object.
1075     *
1076     * @param key The key associated with the object to destroy.
1077     * @param toDestroy The wrapped object to be destroyed
1078     * @param always Should the object be destroyed even if it is not currently
1079     *               in the set of idle objects for the given key
1080     * @return {@code true} if the object was destroyed, otherwise {@code false}
1081     * @throws Exception If the object destruction failed
1082     */
1083    private boolean destroy(final K key, final PooledObject<T> toDestroy, final boolean always)
1084            throws Exception {
1085
1086        final ObjectDeque<T> objectDeque = register(key);
1087
1088        try {
1089            boolean isIdle;
1090            synchronized(toDestroy) {
1091                // Check idle state directly
1092                isIdle = toDestroy.getState().equals(PooledObjectState.IDLE);
1093                // If idle, not under eviction test, or always is true, remove instance,
1094                // updating isIdle if instance is found in idle objects
1095                if (isIdle || always) {
1096                    isIdle = objectDeque.getIdleObjects().remove(toDestroy);
1097                }
1098            }
1099            if (isIdle || always) {
1100                objectDeque.getAllObjects().remove(new IdentityWrapper<>(toDestroy.getObject()));
1101                toDestroy.invalidate();
1102
1103                try {
1104                    factory.destroyObject(key, toDestroy);
1105                } finally {
1106                    objectDeque.getCreateCount().decrementAndGet();
1107                    destroyedCount.incrementAndGet();
1108                    numTotal.decrementAndGet();
1109                }
1110                return true;
1111            }
1112            return false;
1113        } finally {
1114            deregister(key);
1115        }
1116    }
1117
1118
1119    /**
1120     * Register the use of a key by an object.
1121     * <p>
1122     * register() and deregister() must always be used as a pair.
1123     *
1124     * @param k The key to register
1125     *
1126     * @return The objects currently associated with the given key. If this
1127     *         method returns without throwing an exception then it will never
1128     *         return null.
1129     */
1130    private ObjectDeque<T> register(final K k) {
1131        Lock lock = keyLock.readLock();
1132        ObjectDeque<T> objectDeque = null;
1133        try {
1134            lock.lock();
1135            objectDeque = poolMap.get(k);
1136            if (objectDeque == null) {
1137                // Upgrade to write lock
1138                lock.unlock();
1139                lock = keyLock.writeLock();
1140                lock.lock();
1141                objectDeque = poolMap.get(k);
1142                if (objectDeque == null) {
1143                    objectDeque = new ObjectDeque<>(fairness);
1144                    objectDeque.getNumInterested().incrementAndGet();
1145                    // NOTE: Keys must always be added to both poolMap and
1146                    //       poolKeyList at the same time while protected by
1147                    //       keyLock.writeLock()
1148                    poolMap.put(k, objectDeque);
1149                    poolKeyList.add(k);
1150                } else {
1151                    objectDeque.getNumInterested().incrementAndGet();
1152                }
1153            } else {
1154                objectDeque.getNumInterested().incrementAndGet();
1155            }
1156        } finally {
1157            lock.unlock();
1158        }
1159        return objectDeque;
1160    }
1161
1162    /**
1163     * De-register the use of a key by an object.
1164     * <p>
1165     * register() and deregister() must always be used as a pair.
1166     *
1167     * @param k The key to de-register
1168     */
1169    private void deregister(final K k) {
1170        Lock lock = keyLock.readLock();
1171        try {
1172            lock.lock();
1173            final ObjectDeque<T> objectDeque = poolMap.get(k);
1174            final long numInterested = objectDeque.getNumInterested().decrementAndGet();
1175            if (numInterested == 0 && objectDeque.getCreateCount().get() == 0) {
1176                // Potential to remove key
1177                // Upgrade to write lock
1178                lock.unlock();
1179                lock = keyLock.writeLock();
1180                lock.lock();
1181                if (objectDeque.getCreateCount().get() == 0 && objectDeque.getNumInterested().get() == 0) {
1182                    // NOTE: Keys must always be removed from both poolMap and
1183                    //       poolKeyList at the same time while protected by
1184                    //       keyLock.writeLock()
1185                    poolMap.remove(k);
1186                    poolKeyList.remove(k);
1187                }
1188            }
1189        } finally {
1190            lock.unlock();
1191        }
1192    }
1193
1194    @Override
1195    void ensureMinIdle() throws Exception {
1196        final int minIdlePerKeySave = getMinIdlePerKey();
1197        if (minIdlePerKeySave < 1) {
1198            return;
1199        }
1200
1201        for (final K k : poolMap.keySet()) {
1202            ensureMinIdle(k);
1203        }
1204    }
1205
1206    /**
1207     * Ensure that the configured number of minimum idle objects is available in
1208     * the pool for the given key.
1209     *
1210     * @param key The key to check for idle objects
1211     *
1212     * @throws Exception If a new object is required and cannot be created
1213     */
1214    private void ensureMinIdle(final K key) throws Exception {
1215        // Calculate current pool objects
1216        ObjectDeque<T> objectDeque = poolMap.get(key);
1217
1218        // objectDeque == null is OK here. It is handled correctly by both
1219        // methods called below.
1220
1221        // this method isn't synchronized so the
1222        // calculateDeficit is done at the beginning
1223        // as a loop limit and a second time inside the loop
1224        // to stop when another thread already returned the
1225        // needed objects
1226        final int deficit = calculateDeficit(objectDeque);
1227
1228        for (int i = 0; i < deficit && calculateDeficit(objectDeque) > 0; i++) {
1229            addObject(key);
1230            // If objectDeque was null, it won't be any more. Obtain a reference
1231            // to it so the deficit can be correctly calculated. It needs to
1232            // take account of objects created in other threads.
1233            if (objectDeque == null) {
1234                objectDeque = poolMap.get(key);
1235            }
1236        }
1237    }
1238
1239    /**
1240     * Create an object using the {@link KeyedPooledObjectFactory#makeObject
1241     * factory}, passivate it, and then place it in the idle object pool.
1242     * <code>addObject</code> is useful for "pre-loading" a pool with idle
1243     * objects.
1244     *
1245     * @param key the key a new instance should be added to
1246     *
1247     * @throws Exception when {@link KeyedPooledObjectFactory#makeObject}
1248     *                   fails.
1249     */
1250    @Override
1251    public void addObject(final K key) throws Exception {
1252        assertOpen();
1253        register(key);
1254        try {
1255            final PooledObject<T> p = create(key);
1256            addIdleObject(key, p);
1257        } finally {
1258            deregister(key);
1259        }
1260    }
1261
1262    /**
1263     * Add an object to the set of idle objects for a given key.
1264     *
1265     * @param key The key to associate with the idle object
1266     * @param p The wrapped object to add.
1267     *
1268     * @throws Exception If the associated factory fails to passivate the object
1269     */
1270    private void addIdleObject(final K key, final PooledObject<T> p) throws Exception {
1271
1272        if (p != null) {
1273            factory.passivateObject(key, p);
1274            final LinkedBlockingDeque<PooledObject<T>> idleObjects =
1275                    poolMap.get(key).getIdleObjects();
1276            if (getLifo()) {
1277                idleObjects.addFirst(p);
1278            } else {
1279                idleObjects.addLast(p);
1280            }
1281        }
1282    }
1283
1284    /**
1285     * Registers a key for pool control and ensures that
1286     * {@link #getMinIdlePerKey()} idle instances are created.
1287     *
1288     * @param key - The key to register for pool control.
1289     *
1290     * @throws Exception If the associated factory throws an exception
1291     */
1292    public void preparePool(final K key) throws Exception {
1293        final int minIdlePerKeySave = getMinIdlePerKey();
1294        if (minIdlePerKeySave < 1) {
1295            return;
1296        }
1297        ensureMinIdle(key);
1298    }
1299
1300    /**
1301     * Calculate the number of objects to test in a run of the idle object
1302     * evictor.
1303     *
1304     * @return The number of objects to test for validity
1305     */
1306    private int getNumTests() {
1307        final int totalIdle = getNumIdle();
1308        final int numTests = getNumTestsPerEvictionRun();
1309        if (numTests >= 0) {
1310            return Math.min(numTests, totalIdle);
1311        }
1312        return(int)(Math.ceil(totalIdle/Math.abs((double)numTests)));
1313    }
1314
1315    /**
1316     * Calculate the number of objects that need to be created to attempt to
1317     * maintain the minimum number of idle objects while not exceeded the limits
1318     * on the maximum number of objects either per key or totally.
1319     *
1320     * @param objectDeque   The set of objects to check
1321     *
1322     * @return The number of new objects to create
1323     */
1324    private int calculateDeficit(final ObjectDeque<T> objectDeque) {
1325
1326        if (objectDeque == null) {
1327            return getMinIdlePerKey();
1328        }
1329
1330        // Used more than once so keep a local copy so the value is consistent
1331        final int maxTotal = getMaxTotal();
1332        final int maxTotalPerKeySave = getMaxTotalPerKey();
1333
1334        int objectDefecit = 0;
1335
1336        // Calculate no of objects needed to be created, in order to have
1337        // the number of pooled objects < maxTotalPerKey();
1338        objectDefecit = getMinIdlePerKey() - objectDeque.getIdleObjects().size();
1339        if (maxTotalPerKeySave > 0) {
1340            final int growLimit = Math.max(0,
1341                    maxTotalPerKeySave - objectDeque.getIdleObjects().size());
1342            objectDefecit = Math.min(objectDefecit, growLimit);
1343        }
1344
1345        // Take the maxTotal limit into account
1346        if (maxTotal > 0) {
1347            final int growLimit = Math.max(0, maxTotal - getNumActive() - getNumIdle());
1348            objectDefecit = Math.min(objectDefecit, growLimit);
1349        }
1350
1351        return objectDefecit;
1352    }
1353
1354
1355    //--- JMX support ----------------------------------------------------------
1356
1357    @Override
1358    public Map<String,Integer> getNumActivePerKey() {
1359        final HashMap<String,Integer> result = new HashMap<>();
1360
1361        final Iterator<Entry<K,ObjectDeque<T>>> iter = poolMap.entrySet().iterator();
1362        while (iter.hasNext()) {
1363            final Entry<K,ObjectDeque<T>> entry = iter.next();
1364            if (entry != null) {
1365                final K key = entry.getKey();
1366                final ObjectDeque<T> objectDequeue = entry.getValue();
1367                if (key != null && objectDequeue != null) {
1368                    result.put(key.toString(), Integer.valueOf(
1369                            objectDequeue.getAllObjects().size() -
1370                            objectDequeue.getIdleObjects().size()));
1371                }
1372            }
1373        }
1374        return result;
1375    }
1376
1377    /**
1378     * Return an estimate of the number of threads currently blocked waiting for
1379     * an object from the pool. This is intended for monitoring only, not for
1380     * synchronization control.
1381     *
1382     * @return The estimate of the number of threads currently blocked waiting
1383     *         for an object from the pool
1384     */
1385    @Override
1386    public int getNumWaiters() {
1387        int result = 0;
1388
1389        if (getBlockWhenExhausted()) {
1390            final Iterator<ObjectDeque<T>> iter = poolMap.values().iterator();
1391
1392            while (iter.hasNext()) {
1393                // Assume no overflow
1394                result += iter.next().getIdleObjects().getTakeQueueLength();
1395            }
1396        }
1397
1398        return result;
1399    }
1400
1401    /**
1402     * Return an estimate of the number of threads currently blocked waiting for
1403     * an object from the pool for each key. This is intended for
1404     * monitoring only, not for synchronization control.
1405     *
1406     * @return The estimate of the number of threads currently blocked waiting
1407     *         for an object from the pool for each key
1408     */
1409    @Override
1410    public Map<String,Integer> getNumWaitersByKey() {
1411        final Map<String,Integer> result = new HashMap<>();
1412
1413        for (final Map.Entry<K, ObjectDeque<T>> entry : poolMap.entrySet()) {
1414            final K k = entry.getKey();
1415            final ObjectDeque<T> deque = entry.getValue();
1416            if (deque != null) {
1417                if (getBlockWhenExhausted()) {
1418                    result.put(k.toString(), Integer.valueOf(
1419                            deque.getIdleObjects().getTakeQueueLength()));
1420                } else {
1421                    result.put(k.toString(), Integer.valueOf(0));
1422                }
1423            }
1424        }
1425        return result;
1426    }
1427
1428    /**
1429     * Provides information on all the objects in the pool, both idle (waiting
1430     * to be borrowed) and active (currently borrowed).
1431     * <p>
1432     * Note: This is named listAllObjects so it is presented as an operation via
1433     * JMX. That means it won't be invoked unless the explicitly requested
1434     * whereas all attributes will be automatically requested when viewing the
1435     * attributes for an object in a tool like JConsole.
1436     *
1437     * @return Information grouped by key on all the objects in the pool
1438     */
1439    @Override
1440    public Map<String,List<DefaultPooledObjectInfo>> listAllObjects() {
1441        final Map<String,List<DefaultPooledObjectInfo>> result =
1442                new HashMap<>();
1443
1444        for (final Map.Entry<K, ObjectDeque<T>> entry : poolMap.entrySet()) {
1445            final K k = entry.getKey();
1446            final ObjectDeque<T> deque = entry.getValue();
1447            if (deque != null) {
1448                final List<DefaultPooledObjectInfo> list =
1449                        new ArrayList<>();
1450                result.put(k.toString(), list);
1451                for (final PooledObject<T> p : deque.getAllObjects().values()) {
1452                    list.add(new DefaultPooledObjectInfo(p));
1453                }
1454            }
1455        }
1456        return result;
1457    }
1458
1459
1460    //--- inner classes ----------------------------------------------
1461
1462    /**
1463     * Maintains information on the per key queue for a given key.
1464     *
1465     * @param <S> type of objects in the pool
1466     */
1467    private class ObjectDeque<S> {
1468
1469        private final LinkedBlockingDeque<PooledObject<S>> idleObjects;
1470
1471        /*
1472         * Number of instances created - number destroyed.
1473         * Invariant: createCount <= maxTotalPerKey
1474         */
1475        private final AtomicInteger createCount = new AtomicInteger(0);
1476
1477        private long makeObjectCount = 0;
1478        private final Object makeObjectCountLock = new Object();
1479
1480        /*
1481         * The map is keyed on pooled instances, wrapped to ensure that
1482         * they work properly as keys.
1483         */
1484        private final Map<IdentityWrapper<S>, PooledObject<S>> allObjects =
1485                new ConcurrentHashMap<>();
1486
1487        /*
1488         * Number of threads with registered interest in this key.
1489         * register(K) increments this counter and deRegister(K) decrements it.
1490         * Invariant: empty keyed pool will not be dropped unless numInterested
1491         *            is 0.
1492         */
1493        private final AtomicLong numInterested = new AtomicLong(0);
1494
1495        /**
1496         * Create a new ObjecDeque with the given fairness policy.
1497         * @param fairness true means client threads waiting to borrow / return instances
1498         * will be served as if waiting in a FIFO queue.
1499         */
1500        public ObjectDeque(final boolean fairness) {
1501            idleObjects = new LinkedBlockingDeque<>(fairness);
1502        }
1503
1504        /**
1505         * Obtain the idle objects for the current key.
1506         *
1507         * @return The idle objects
1508         */
1509        public LinkedBlockingDeque<PooledObject<S>> getIdleObjects() {
1510            return idleObjects;
1511        }
1512
1513        /**
1514         * Obtain the count of the number of objects created for the current
1515         * key.
1516         *
1517         * @return The number of objects created for this key
1518         */
1519        public AtomicInteger getCreateCount() {
1520            return createCount;
1521        }
1522
1523        /**
1524         * Obtain the number of threads with an interest registered in this key.
1525         *
1526         * @return The number of threads with a registered interest in this key
1527         */
1528        public AtomicLong getNumInterested() {
1529            return numInterested;
1530        }
1531
1532        /**
1533         * Obtain all the objects for the current key.
1534         *
1535         * @return All the objects
1536         */
1537        public Map<IdentityWrapper<S>, PooledObject<S>> getAllObjects() {
1538            return allObjects;
1539        }
1540
1541        @Override
1542        public String toString() {
1543            final StringBuilder builder = new StringBuilder();
1544            builder.append("ObjectDeque [idleObjects=");
1545            builder.append(idleObjects);
1546            builder.append(", createCount=");
1547            builder.append(createCount);
1548            builder.append(", allObjects=");
1549            builder.append(allObjects);
1550            builder.append(", numInterested=");
1551            builder.append(numInterested);
1552            builder.append("]");
1553            return builder.toString();
1554        }
1555
1556    }
1557
1558    //--- configuration attributes ---------------------------------------------
1559    private volatile int maxIdlePerKey =
1560            GenericKeyedObjectPoolConfig.DEFAULT_MAX_IDLE_PER_KEY;
1561    private volatile int minIdlePerKey =
1562            GenericKeyedObjectPoolConfig.DEFAULT_MIN_IDLE_PER_KEY;
1563    private volatile int maxTotalPerKey =
1564            GenericKeyedObjectPoolConfig.DEFAULT_MAX_TOTAL_PER_KEY;
1565    private final KeyedPooledObjectFactory<K, T> factory;
1566    private final boolean fairness;
1567
1568
1569    //--- internal attributes --------------------------------------------------
1570
1571    /*
1572     * My hash of sub-pools (ObjectQueue). The list of keys <b>must</b> be kept
1573     * in step with {@link #poolKeyList} using {@link #keyLock} to ensure any
1574     * changes to the list of current keys is made in a thread-safe manner.
1575     */
1576    private final Map<K, ObjectDeque<T>> poolMap =
1577            new ConcurrentHashMap<>(); // @GuardedBy("keyLock") for write access (and some read access)
1578    /*
1579     * List of pool keys - used to control eviction order. The list of keys
1580     * <b>must</b> be kept in step with {@link #poolMap} using {@link #keyLock}
1581     * to ensure any changes to the list of current keys is made in a
1582     * thread-safe manner.
1583     */
1584    private final List<K> poolKeyList = new ArrayList<>(); // @GuardedBy("keyLock")
1585    private final ReadWriteLock keyLock = new ReentrantReadWriteLock(true);
1586    /*
1587     * The combined count of the currently active objects for all keys and those
1588     * in the process of being created. Under load, it may exceed
1589     * {@link #maxTotal} but there will never be more than {@link #maxTotal}
1590     * created at any one time.
1591     */
1592    private final AtomicInteger numTotal = new AtomicInteger(0);
1593    private Iterator<K> evictionKeyIterator = null; // @GuardedBy("evictionLock")
1594    private K evictionKey = null; // @GuardedBy("evictionLock")
1595
1596    // JMX specific attributes
1597    private static final String ONAME_BASE =
1598            "org.apache.commons.pool2:type=GenericKeyedObjectPool,name=";
1599
1600    @Override
1601    protected void toStringAppendFields(final StringBuilder builder) {
1602        super.toStringAppendFields(builder);
1603        builder.append(", maxIdlePerKey=");
1604        builder.append(maxIdlePerKey);
1605        builder.append(", minIdlePerKey=");
1606        builder.append(minIdlePerKey);
1607        builder.append(", maxTotalPerKey=");
1608        builder.append(maxTotalPerKey);
1609        builder.append(", factory=");
1610        builder.append(factory);
1611        builder.append(", fairness=");
1612        builder.append(fairness);
1613        builder.append(", poolMap=");
1614        builder.append(poolMap);
1615        builder.append(", poolKeyList=");
1616        builder.append(poolKeyList);
1617        builder.append(", keyLock=");
1618        builder.append(keyLock);
1619        builder.append(", numTotal=");
1620        builder.append(numTotal);
1621        builder.append(", evictionKeyIterator=");
1622        builder.append(evictionKeyIterator);
1623        builder.append(", evictionKey=");
1624        builder.append(evictionKey);
1625    }
1626}