diff options
Diffstat (limited to 'org.eclipse.jgit')
| -rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/lib/OffsetCache.java | 539 | ||||
| -rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/lib/WindowCache.java | 396 |
2 files changed, 377 insertions, 558 deletions
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/OffsetCache.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/OffsetCache.java deleted file mode 100644 index 747f6f122e..0000000000 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/OffsetCache.java +++ /dev/null @@ -1,539 +0,0 @@ -/* - * Copyright (C) 2009, Google Inc. - * and other copyright owners as documented in the project's IP log. - * - * This program and the accompanying materials are made available - * under the terms of the Eclipse Distribution License v1.0 which - * accompanies this distribution, is reproduced below, and is - * available at http://www.eclipse.org/org/documents/edl-v10.php - * - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or - * without modification, are permitted provided that the following - * conditions are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * - Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following - * disclaimer in the documentation and/or other materials provided - * with the distribution. - * - * - Neither the name of the Eclipse Foundation, Inc. nor the - * names of its contributors may be used to endorse or promote - * products derived from this software without specific prior - * written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND - * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, - * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR - * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER - * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, - * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF - * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -package org.eclipse.jgit.lib; - -import java.io.IOException; -import java.lang.ref.ReferenceQueue; -import java.lang.ref.SoftReference; -import java.util.Random; -import java.util.concurrent.atomic.AtomicLong; -import java.util.concurrent.atomic.AtomicReferenceArray; -import java.util.concurrent.locks.ReentrantLock; - -/** - * Least frequently used cache for objects specified by PackFile positions. - * <p> - * This cache maps a <code>({@link PackFile},position)</code> tuple to an Object. - * <p> - * This cache is suitable for objects that are "relative expensive" to compute - * from the underlying PackFile, given some known position in that file. - * <p> - * Whenever a cache miss occurs, {@link #load(PackFile, long)} is invoked by - * exactly one thread for the given <code>(PackFile,position)</code> key tuple. - * This is ensured by an array of locks, with the tuple hashed to a lock - * instance. - * <p> - * During a miss, older entries are evicted from the cache so long as - * {@link #isFull()} returns true. - * <p> - * Its too expensive during object access to be 100% accurate with a least - * recently used (LRU) algorithm. Strictly ordering every read is a lot of - * overhead that typically doesn't yield a corresponding benefit to the - * application. - * <p> - * This cache implements a loose LRU policy by randomly picking a window - * comprised of roughly 10% of the cache, and evicting the oldest accessed entry - * within that window. - * <p> - * Entities created by the cache are held under SoftReferences, permitting the - * Java runtime's garbage collector to evict entries when heap memory gets low. - * Most JREs implement a loose least recently used algorithm for this eviction. - * <p> - * The internal hash table does not expand at runtime, instead it is fixed in - * size at cache creation time. The internal lock table used to gate load - * invocations is also fixed in size. - * <p> - * The key tuple is passed through to methods as a pair of parameters rather - * than as a single Object, thus reducing the transient memory allocations of - * callers. It is more efficient to avoid the allocation, as we can't be 100% - * sure that a JIT would be able to stack-allocate a key tuple. - * <p> - * This cache has an implementation rule such that: - * <ul> - * <li>{@link #load(PackFile, long)} is invoked by at most one thread at a time - * for a given <code>(PackFile,position)</code> tuple.</li> - * <li>For every <code>load()</code> invocation there is exactly one - * {@link #createRef(PackFile, long, Object)} invocation to wrap a SoftReference - * around the cached entity.</li> - * <li>For every Reference created by <code>createRef()</code> there will be - * exactly one call to {@link #clear(Ref)} to cleanup any resources associated - * with the (now expired) cached entity.</li> - * </ul> - * <p> - * Therefore, it is safe to perform resource accounting increments during the - * {@link #load(PackFile, long)} or {@link #createRef(PackFile, long, Object)} - * methods, and matching decrements during {@link #clear(Ref)}. Implementors may - * need to override {@link #createRef(PackFile, long, Object)} in order to embed - * additional accounting information into an implementation specific - * {@link OffsetCache.Ref} subclass, as the cached entity may have already been - * evicted by the JRE's garbage collector. - * <p> - * To maintain higher concurrency workloads, during eviction only one thread - * performs the eviction work, while other threads can continue to insert new - * objects in parallel. This means that the cache can be temporarily over limit, - * especially if the nominated eviction thread is being starved relative to the - * other threads. - * - * @param <V> - * type of value stored in the cache. - * @param <R> - * type of {@link OffsetCache.Ref} subclass used by the cache. - */ -abstract class OffsetCache<V, R extends OffsetCache.Ref<V>> { - private static final Random rng = new Random(); - - /** ReferenceQueue that {@link #createRef(PackFile, long, Object)} must use. */ - protected final ReferenceQueue<V> queue; - - /** Number of entries in {@link #table}. */ - private final int tableSize; - - /** Access clock for loose LRU. */ - private final AtomicLong clock; - - /** Hash bucket directory; entries are chained below. */ - private final AtomicReferenceArray<Entry<V>> table; - - /** Locks to prevent concurrent loads for same (PackFile,position). */ - private final Lock[] locks; - - /** Lock to elect the eviction thread after a load occurs. */ - private final ReentrantLock evictLock; - - /** Number of {@link #table} buckets to scan for an eviction window. */ - private final int evictBatch; - - /** - * Create a new cache with a fixed size entry table and lock table. - * - * @param tSize - * number of entries in the entry hash table. - * @param lockCount - * number of entries in the lock table. This is the maximum - * concurrency rate for creation of new objects through - * {@link #load(PackFile, long)} invocations. - */ - OffsetCache(final int tSize, final int lockCount) { - if (tSize < 1) - throw new IllegalArgumentException("tSize must be >= 1"); - if (lockCount < 1) - throw new IllegalArgumentException("lockCount must be >= 1"); - - queue = new ReferenceQueue<V>(); - tableSize = tSize; - clock = new AtomicLong(1); - table = new AtomicReferenceArray<Entry<V>>(tableSize); - locks = new Lock[lockCount]; - for (int i = 0; i < locks.length; i++) - locks[i] = new Lock(); - evictLock = new ReentrantLock(); - - int eb = (int) (tableSize * .1); - if (64 < eb) - eb = 64; - else if (eb < 4) - eb = 4; - if (tableSize < eb) - eb = tableSize; - evictBatch = eb; - } - - /** - * Lookup a cached object, creating and loading it if it doesn't exist. - * - * @param pack - * the pack that "contains" the cached object. - * @param position - * offset within <code>pack</code> of the object. - * @return the object reference. - * @throws IOException - * the object reference was not in the cache and could not be - * obtained by {@link #load(PackFile, long)}. - */ - V getOrLoad(final PackFile pack, final long position) throws IOException { - final int slot = slot(pack, position); - final Entry<V> e1 = table.get(slot); - V v = scan(e1, pack, position); - if (v != null) - return v; - - synchronized (lock(pack, position)) { - Entry<V> e2 = table.get(slot); - if (e2 != e1) { - v = scan(e2, pack, position); - if (v != null) - return v; - } - - v = load(pack, position); - final Ref<V> ref = createRef(pack, position, v); - hit(ref); - for (;;) { - final Entry<V> n = new Entry<V>(clean(e2), ref); - if (table.compareAndSet(slot, e2, n)) - break; - e2 = table.get(slot); - } - } - - if (evictLock.tryLock()) { - try { - gc(); - evict(); - } finally { - evictLock.unlock(); - } - } - - return v; - } - - private V scan(Entry<V> n, final PackFile pack, final long position) { - for (; n != null; n = n.next) { - final Ref<V> r = n.ref; - if (r.pack == pack && r.position == position) { - final V v = r.get(); - if (v != null) { - hit(r); - return v; - } - n.kill(); - break; - } - } - return null; - } - - private void hit(final Ref<V> r) { - // We don't need to be 100% accurate here. Its sufficient that at least - // one thread performs the increment. Any other concurrent access at - // exactly the same time can simply use the same clock value. - // - // Consequently we attempt the set, but we don't try to recover should - // it fail. This is why we don't use getAndIncrement() here. - // - final long c = clock.get(); - clock.compareAndSet(c, c + 1); - r.lastAccess = c; - } - - private void evict() { - while (isFull()) { - int ptr = rng.nextInt(tableSize); - Entry<V> old = null; - int slot = 0; - for (int b = evictBatch - 1; b >= 0; b--, ptr++) { - if (tableSize <= ptr) - ptr = 0; - for (Entry<V> e = table.get(ptr); e != null; e = e.next) { - if (e.dead) - continue; - if (old == null || e.ref.lastAccess < old.ref.lastAccess) { - old = e; - slot = ptr; - } - } - } - if (old != null) { - old.kill(); - gc(); - final Entry<V> e1 = table.get(slot); - table.compareAndSet(slot, e1, clean(e1)); - } - } - } - - /** - * Clear every entry from the cache. - *<p> - * This is a last-ditch effort to clear out the cache, such as before it - * gets replaced by another cache that is configured differently. This - * method tries to force every cached entry through {@link #clear(Ref)} to - * ensure that resources are correctly accounted for and cleaned up by the - * subclass. A concurrent reader loading entries while this method is - * running may cause resource accounting failures. - */ - void removeAll() { - for (int s = 0; s < tableSize; s++) { - Entry<V> e1; - do { - e1 = table.get(s); - for (Entry<V> e = e1; e != null; e = e.next) - e.kill(); - } while (!table.compareAndSet(s, e1, null)); - } - gc(); - } - - /** - * Clear all entries related to a single file. - * <p> - * Typically this method is invoked during {@link PackFile#close()}, when we - * know the pack is never going to be useful to us again (for example, it no - * longer exists on disk). A concurrent reader loading an entry from this - * same pack may cause the pack to become stuck in the cache anyway. - * - * @param pack - * the file to purge all entries of. - */ - void removeAll(final PackFile pack) { - for (int s = 0; s < tableSize; s++) { - final Entry<V> e1 = table.get(s); - boolean hasDead = false; - for (Entry<V> e = e1; e != null; e = e.next) { - if (e.ref.pack == pack) { - e.kill(); - hasDead = true; - } else if (e.dead) - hasDead = true; - } - if (hasDead) - table.compareAndSet(s, e1, clean(e1)); - } - gc(); - } - - /** - * Materialize an object that doesn't yet exist in the cache. - * <p> - * This method is invoked by {@link #getOrLoad(PackFile, long)} when the - * specified entity does not yet exist in the cache. Internal locking - * ensures that at most one thread can call this method for each unique - * <code>(pack,position)</code>, but multiple threads can call this method - * concurrently for different <code>(pack,position)</code> tuples. - * - * @param pack - * the file to materialize the entry from. - * @param position - * offset within the file of the entry. - * @return the materialized object. Must never be null. - * @throws IOException - * the method was unable to materialize the object for this - * input pair. The usual reasons would be file corruption, file - * not found, out of file descriptors, etc. - */ - protected abstract V load(PackFile pack, long position) throws IOException; - - /** - * Construct a Ref (SoftReference) around a cached entity. - * <p> - * Implementing this is only necessary if the subclass is performing - * resource accounting during {@link #load(PackFile, long)} and - * {@link #clear(Ref)} requires some information to update the accounting. - * <p> - * Implementors <b>MUST</b> ensure that the returned reference uses the - * {@link #queue} ReferenceQueue, otherwise {@link #clear(Ref)} will not be - * invoked at the proper time. - * - * @param pack - * the file to materialize the entry from. - * @param position - * offset within the file of the entry. - * @param v - * the object returned by {@link #load(PackFile, long)}. - * @return a soft reference subclass wrapped around <code>v</code>. - */ - @SuppressWarnings("unchecked") - protected R createRef(final PackFile pack, final long position, final V v) { - return (R) new Ref<V>(pack, position, v, queue); - } - - /** - * Update accounting information now that an object has left the cache. - * <p> - * This method is invoked exactly once for the combined - * {@link #load(PackFile, long)} and - * {@link #createRef(PackFile, long, Object)} invocation pair that was used - * to construct and insert an object into the cache. - * - * @param ref - * the reference wrapped around the object. Implementations must - * be prepared for <code>ref.get()</code> to return null. - */ - protected void clear(final R ref) { - // Do nothing by default. - } - - /** - * Determine if the cache is full and requires eviction of entries. - * <p> - * By default this method returns false. Implementors may override to - * consult with the accounting updated by {@link #load(PackFile, long)}, - * {@link #createRef(PackFile, long, Object)} and {@link #clear(Ref)}. - * - * @return true if the cache is still over-limit and requires eviction of - * more entries. - */ - protected boolean isFull() { - return false; - } - - @SuppressWarnings("unchecked") - private void gc() { - R r; - while ((r = (R) queue.poll()) != null) { - // Sun's Java 5 and 6 implementation have a bug where a Reference - // can be enqueued and dequeued twice on the same reference queue - // due to a race condition within ReferenceQueue.enqueue(Reference). - // - // http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6837858 - // - // We CANNOT permit a Reference to come through us twice, as it will - // skew the resource counters we maintain. Our canClear() check here - // provides a way to skip the redundant dequeues, if any. - // - if (r.canClear()) { - clear(r); - - boolean found = false; - final int s = slot(r.pack, r.position); - final Entry<V> e1 = table.get(s); - for (Entry<V> n = e1; n != null; n = n.next) { - if (n.ref == r) { - n.dead = true; - found = true; - break; - } - } - if (found) - table.compareAndSet(s, e1, clean(e1)); - } - } - } - - /** - * Compute the hash code value for a <code>(PackFile,position)</code> tuple. - * <p> - * For example, <code>return packHash + (int) (position >>> 4)</code>. - * Implementors must override with a suitable hash (for example, a different - * right shift on the position). - * - * @param packHash - * hash code for the file being accessed. - * @param position - * position within the file being accessed. - * @return a reasonable hash code mixing the two values. - */ - protected abstract int hash(int packHash, long position); - - private int slot(final PackFile pack, final long position) { - return (hash(pack.hash, position) >>> 1) % tableSize; - } - - private Lock lock(final PackFile pack, final long position) { - return locks[(hash(pack.hash, position) >>> 1) % locks.length]; - } - - private static <V> Entry<V> clean(Entry<V> top) { - while (top != null && top.dead) { - top.ref.enqueue(); - top = top.next; - } - if (top == null) - return null; - final Entry<V> n = clean(top.next); - return n == top.next ? top : new Entry<V>(n, top.ref); - } - - private static class Entry<V> { - /** Next entry in the hash table's chain list. */ - final Entry<V> next; - - /** The referenced object. */ - final Ref<V> ref; - - /** - * Marked true when ref.get() returns null and the ref is dead. - * <p> - * A true here indicates that the ref is no longer accessible, and that - * we therefore need to eventually purge this Entry object out of the - * bucket's chain. - */ - volatile boolean dead; - - Entry(final Entry<V> n, final Ref<V> r) { - next = n; - ref = r; - } - - final void kill() { - dead = true; - ref.enqueue(); - } - } - - /** - * A soft reference wrapped around a cached object. - * - * @param <V> - * type of the cached object. - */ - protected static class Ref<V> extends SoftReference<V> { - final PackFile pack; - - final long position; - - long lastAccess; - - private boolean cleared; - - protected Ref(final PackFile pack, final long position, final V v, - final ReferenceQueue<V> queue) { - super(v, queue); - this.pack = pack; - this.position = position; - } - - final synchronized boolean canClear() { - if (cleared) - return false; - cleared = true; - return true; - } - } - - private static final class Lock { - // Used only for its implicit monitor. - } -} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/WindowCache.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/WindowCache.java index 9c8f99dbc9..b2c79c1089 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/WindowCache.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/WindowCache.java @@ -46,8 +46,12 @@ package org.eclipse.jgit.lib; import java.io.IOException; import java.lang.ref.ReferenceQueue; +import java.lang.ref.SoftReference; +import java.util.Random; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicLong; +import java.util.concurrent.atomic.AtomicReferenceArray; +import java.util.concurrent.locks.ReentrantLock; /** * Caches slices of a {@link PackFile} in memory for faster read access. @@ -56,8 +60,65 @@ import java.util.concurrent.atomic.AtomicLong; * PackFile into the JVM heap prior to use. As JGit often wants to do reads of * only tiny slices of a file, the WindowCache tries to smooth out these tiny * reads into larger block-sized IO operations. + * <p> + * Whenever a cache miss occurs, {@link #load(PackFile, long)} is invoked by + * exactly one thread for the given <code>(PackFile,position)</code> key tuple. + * This is ensured by an array of locks, with the tuple hashed to a lock + * instance. + * <p> + * During a miss, older entries are evicted from the cache so long as + * {@link #isFull()} returns true. + * <p> + * Its too expensive during object access to be 100% accurate with a least + * recently used (LRU) algorithm. Strictly ordering every read is a lot of + * overhead that typically doesn't yield a corresponding benefit to the + * application. + * <p> + * This cache implements a loose LRU policy by randomly picking a window + * comprised of roughly 10% of the cache, and evicting the oldest accessed entry + * within that window. + * <p> + * Entities created by the cache are held under SoftReferences, permitting the + * Java runtime's garbage collector to evict entries when heap memory gets low. + * Most JREs implement a loose least recently used algorithm for this eviction. + * <p> + * The internal hash table does not expand at runtime, instead it is fixed in + * size at cache creation time. The internal lock table used to gate load + * invocations is also fixed in size. + * <p> + * The key tuple is passed through to methods as a pair of parameters rather + * than as a single Object, thus reducing the transient memory allocations of + * callers. It is more efficient to avoid the allocation, as we can't be 100% + * sure that a JIT would be able to stack-allocate a key tuple. + * <p> + * This cache has an implementation rule such that: + * <ul> + * <li>{@link #load(PackFile, long)} is invoked by at most one thread at a time + * for a given <code>(PackFile,position)</code> tuple.</li> + * <li>For every <code>load()</code> invocation there is exactly one + * {@link #createRef(PackFile, long, ByteWindow)} invocation to wrap a + * SoftReference around the cached entity.</li> + * <li>For every Reference created by <code>createRef()</code> there will be + * exactly one call to {@link #clear(Ref)} to cleanup any resources associated + * with the (now expired) cached entity.</li> + * </ul> + * <p> + * Therefore, it is safe to perform resource accounting increments during the + * {@link #load(PackFile, long)} or + * {@link #createRef(PackFile, long, ByteWindow)} methods, and matching + * decrements during {@link #clear(Ref)}. Implementors may need to override + * {@link #createRef(PackFile, long, ByteWindow)} in order to embed additional + * accounting information into an implementation specific {@link Ref} subclass, + * as the cached entity may have already been evicted by the JRE's garbage + * collector. + * <p> + * To maintain higher concurrency workloads, during eviction only one thread + * performs the eviction work, while other threads can continue to insert new + * objects in parallel. This means that the cache can be temporarily over limit, + * especially if the nominated eviction thread is being starved relative to the + * other threads. */ -public class WindowCache extends OffsetCache<ByteWindow, WindowCache.WindowRef> { +public class WindowCache { private static final int bits(int newSize) { if (newSize < 4096) throw new IllegalArgumentException("Invalid window size"); @@ -66,6 +127,8 @@ public class WindowCache extends OffsetCache<ByteWindow, WindowCache.WindowRef> return Integer.numberOfTrailingZeros(newSize); } + private static final Random rng = new Random(); + private static volatile WindowCache cache; static { @@ -145,6 +208,27 @@ public class WindowCache extends OffsetCache<ByteWindow, WindowCache.WindowRef> cache.removeAll(pack); } + /** ReferenceQueue to cleanup released and garbage collected windows. */ + private final ReferenceQueue<ByteWindow> queue; + + /** Number of entries in {@link #table}. */ + private final int tableSize; + + /** Access clock for loose LRU. */ + private final AtomicLong clock; + + /** Hash bucket directory; entries are chained below. */ + private final AtomicReferenceArray<Entry> table; + + /** Locks to prevent concurrent loads for same (PackFile,position). */ + private final Lock[] locks; + + /** Lock to elect the eviction thread after a load occurs. */ + private final ReentrantLock evictLock; + + /** Number of {@link #table} buckets to scan for an eviction window. */ + private final int evictBatch; + private final int maxFiles; private final long maxBytes; @@ -160,7 +244,30 @@ public class WindowCache extends OffsetCache<ByteWindow, WindowCache.WindowRef> private final AtomicLong openBytes; private WindowCache(final WindowCacheConfig cfg) { - super(tableSize(cfg), lockCount(cfg)); + tableSize = tableSize(cfg); + final int lockCount = lockCount(cfg); + if (tableSize < 1) + throw new IllegalArgumentException("tSize must be >= 1"); + if (lockCount < 1) + throw new IllegalArgumentException("lockCount must be >= 1"); + + queue = new ReferenceQueue<ByteWindow>(); + clock = new AtomicLong(1); + table = new AtomicReferenceArray<Entry>(tableSize); + locks = new Lock[lockCount]; + for (int i = 0; i < locks.length; i++) + locks[i] = new Lock(); + evictLock = new ReentrantLock(); + + int eb = (int) (tableSize * .1); + if (64 < eb) + eb = 64; + else if (eb < 4) + eb = 4; + if (tableSize < eb) + eb = tableSize; + evictBatch = eb; + maxFiles = cfg.getPackedGitOpenFiles(); maxBytes = cfg.getPackedGitLimit(); mmap = cfg.isPackedGitMMAP(); @@ -184,13 +291,11 @@ public class WindowCache extends OffsetCache<ByteWindow, WindowCache.WindowRef> return openBytes.get(); } - @Override - protected int hash(final int packHash, final long off) { + private int hash(final int packHash, final long off) { return packHash + (int) (off >>> windowSizeShift); } - @Override - protected ByteWindow load(final PackFile pack, final long offset) + private ByteWindow load(final PackFile pack, final long offset) throws IOException { if (pack.beginWindowCache()) openFiles.incrementAndGet(); @@ -210,16 +315,13 @@ public class WindowCache extends OffsetCache<ByteWindow, WindowCache.WindowRef> } } - @Override - protected WindowRef createRef(final PackFile p, final long o, - final ByteWindow v) { - final WindowRef ref = new WindowRef(p, o, v, queue); + private Ref createRef(final PackFile p, final long o, final ByteWindow v) { + final Ref ref = new Ref(p, o, v, queue); openBytes.addAndGet(ref.size); return ref; } - @Override - protected void clear(final WindowRef ref) { + private void clear(final Ref ref) { openBytes.addAndGet(-ref.size); close(ref.pack); } @@ -229,8 +331,7 @@ public class WindowCache extends OffsetCache<ByteWindow, WindowCache.WindowRef> openFiles.decrementAndGet(); } - @Override - protected boolean isFull() { + private boolean isFull() { return maxFiles < openFiles.get() || maxBytes < openBytes.get(); } @@ -252,13 +353,270 @@ public class WindowCache extends OffsetCache<ByteWindow, WindowCache.WindowRef> return Math.max(cfg.getPackedGitOpenFiles(), 32); } - static class WindowRef extends OffsetCache.Ref<ByteWindow> { + /** + * Lookup a cached object, creating and loading it if it doesn't exist. + * + * @param pack + * the pack that "contains" the cached object. + * @param position + * offset within <code>pack</code> of the object. + * @return the object reference. + * @throws IOException + * the object reference was not in the cache and could not be + * obtained by {@link #load(PackFile, long)}. + */ + private ByteWindow getOrLoad(final PackFile pack, final long position) + throws IOException { + final int slot = slot(pack, position); + final Entry e1 = table.get(slot); + ByteWindow v = scan(e1, pack, position); + if (v != null) + return v; + + synchronized (lock(pack, position)) { + Entry e2 = table.get(slot); + if (e2 != e1) { + v = scan(e2, pack, position); + if (v != null) + return v; + } + + v = load(pack, position); + final Ref ref = createRef(pack, position, v); + hit(ref); + for (;;) { + final Entry n = new Entry(clean(e2), ref); + if (table.compareAndSet(slot, e2, n)) + break; + e2 = table.get(slot); + } + } + + if (evictLock.tryLock()) { + try { + gc(); + evict(); + } finally { + evictLock.unlock(); + } + } + + return v; + } + + private ByteWindow scan(Entry n, final PackFile pack, final long position) { + for (; n != null; n = n.next) { + final Ref r = n.ref; + if (r.pack == pack && r.position == position) { + final ByteWindow v = r.get(); + if (v != null) { + hit(r); + return v; + } + n.kill(); + break; + } + } + return null; + } + + private void hit(final Ref r) { + // We don't need to be 100% accurate here. Its sufficient that at least + // one thread performs the increment. Any other concurrent access at + // exactly the same time can simply use the same clock value. + // + // Consequently we attempt the set, but we don't try to recover should + // it fail. This is why we don't use getAndIncrement() here. + // + final long c = clock.get(); + clock.compareAndSet(c, c + 1); + r.lastAccess = c; + } + + private void evict() { + while (isFull()) { + int ptr = rng.nextInt(tableSize); + Entry old = null; + int slot = 0; + for (int b = evictBatch - 1; b >= 0; b--, ptr++) { + if (tableSize <= ptr) + ptr = 0; + for (Entry e = table.get(ptr); e != null; e = e.next) { + if (e.dead) + continue; + if (old == null || e.ref.lastAccess < old.ref.lastAccess) { + old = e; + slot = ptr; + } + } + } + if (old != null) { + old.kill(); + gc(); + final Entry e1 = table.get(slot); + table.compareAndSet(slot, e1, clean(e1)); + } + } + } + + /** + * Clear every entry from the cache. + * <p> + * This is a last-ditch effort to clear out the cache, such as before it + * gets replaced by another cache that is configured differently. This + * method tries to force every cached entry through {@link #clear(Ref)} to + * ensure that resources are correctly accounted for and cleaned up by the + * subclass. A concurrent reader loading entries while this method is + * running may cause resource accounting failures. + */ + private void removeAll() { + for (int s = 0; s < tableSize; s++) { + Entry e1; + do { + e1 = table.get(s); + for (Entry e = e1; e != null; e = e.next) + e.kill(); + } while (!table.compareAndSet(s, e1, null)); + } + gc(); + } + + /** + * Clear all entries related to a single file. + * <p> + * Typically this method is invoked during {@link PackFile#close()}, when we + * know the pack is never going to be useful to us again (for example, it no + * longer exists on disk). A concurrent reader loading an entry from this + * same pack may cause the pack to become stuck in the cache anyway. + * + * @param pack + * the file to purge all entries of. + */ + private void removeAll(final PackFile pack) { + for (int s = 0; s < tableSize; s++) { + final Entry e1 = table.get(s); + boolean hasDead = false; + for (Entry e = e1; e != null; e = e.next) { + if (e.ref.pack == pack) { + e.kill(); + hasDead = true; + } else if (e.dead) + hasDead = true; + } + if (hasDead) + table.compareAndSet(s, e1, clean(e1)); + } + gc(); + } + + @SuppressWarnings("unchecked") + private void gc() { + Ref r; + while ((r = (Ref) queue.poll()) != null) { + // Sun's Java 5 and 6 implementation have a bug where a Reference + // can be enqueued and dequeued twice on the same reference queue + // due to a race condition within ReferenceQueue.enqueue(Reference). + // + // http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6837858 + // + // We CANNOT permit a Reference to come through us twice, as it will + // skew the resource counters we maintain. Our canClear() check here + // provides a way to skip the redundant dequeues, if any. + // + if (r.canClear()) { + clear(r); + + boolean found = false; + final int s = slot(r.pack, r.position); + final Entry e1 = table.get(s); + for (Entry n = e1; n != null; n = n.next) { + if (n.ref == r) { + n.dead = true; + found = true; + break; + } + } + if (found) + table.compareAndSet(s, e1, clean(e1)); + } + } + } + + private int slot(final PackFile pack, final long position) { + return (hash(pack.hash, position) >>> 1) % tableSize; + } + + private Lock lock(final PackFile pack, final long position) { + return locks[(hash(pack.hash, position) >>> 1) % locks.length]; + } + + private static Entry clean(Entry top) { + while (top != null && top.dead) { + top.ref.enqueue(); + top = top.next; + } + if (top == null) + return null; + final Entry n = clean(top.next); + return n == top.next ? top : new Entry(n, top.ref); + } + + private static class Entry { + /** Next entry in the hash table's chain list. */ + final Entry next; + + /** The referenced object. */ + final Ref ref; + + /** + * Marked true when ref.get() returns null and the ref is dead. + * <p> + * A true here indicates that the ref is no longer accessible, and that + * we therefore need to eventually purge this Entry object out of the + * bucket's chain. + */ + volatile boolean dead; + + Entry(final Entry n, final Ref r) { + next = n; + ref = r; + } + + final void kill() { + dead = true; + ref.enqueue(); + } + } + + /** A soft reference wrapped around a cached object. */ + private static class Ref extends SoftReference<ByteWindow> { + final PackFile pack; + + final long position; + final int size; - WindowRef(final PackFile pack, final long position, final ByteWindow v, - final ReferenceQueue<ByteWindow> queue) { - super(pack, position, v, queue); - size = v.size(); + long lastAccess; + + private boolean cleared; + + protected Ref(final PackFile pack, final long position, + final ByteWindow v, final ReferenceQueue<ByteWindow> queue) { + super(v, queue); + this.pack = pack; + this.position = position; + this.size = v.size(); } + + final synchronized boolean canClear() { + if (cleared) + return false; + cleared = true; + return true; + } + } + + private static final class Lock { + // Used only for its implicit monitor. } } |