/*
    * Copyright (C) 2008-2009, Google Inc.
    * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org> and others
    *
    * This program and the accompanying materials are made available under the
    * terms of the Eclipse Distribution License v. 1.0 which is available at
    * https://www.eclipse.org/org/documents/edl-v10.php.
    *
    * SPDX-License-Identifier: BSD-3-Clause
   */
  
  package org.eclipse.jgit.internal.storage.file;
  
  import java.io.IOException;
  import java.lang.ref.ReferenceQueue;
  import java.lang.ref.SoftReference;
  import java.util.Collections;
  import java.util.Map;
  import java.util.Random;
  import java.util.concurrent.ConcurrentHashMap;
  import java.util.concurrent.ConcurrentLinkedQueue;
  import java.util.concurrent.atomic.AtomicLong;
  import java.util.concurrent.atomic.AtomicReferenceArray;
  import java.util.concurrent.atomic.LongAdder;
  import java.util.concurrent.locks.ReentrantLock;
  import java.util.stream.Collectors;
  
  import org.eclipse.jgit.annotations.NonNull;
  import org.eclipse.jgit.internal.JGitText;
  import org.eclipse.jgit.storage.file.WindowCacheConfig;
  import org.eclipse.jgit.storage.file.WindowCacheStats;
  import org.eclipse.jgit.util.Monitoring;
  
  /**
   * Caches slices of a {@link org.eclipse.jgit.internal.storage.file.PackFile} in
   * memory for faster read access.
   * <p>
   * The WindowCache serves as a Java based "buffer cache", loading segments of a
   * 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 if option
   * {@code core.packedGitUseStrongRefs} is set to {@code false} in the git config
   * (this is the default) or by calling
   * {@link WindowCacheConfig#setPackedGitUseStrongRefs(boolean)}, 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.
   * When this option is set to {@code true} strong references are used which
   * means that Java gc cannot evict the WindowCache to reclaim memory. On the
   * other hand this provides more predictable performance since the cache isn't
   * flushed when used heap comes close to the maximum heap size.
   * <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 or a StrongReference around the cached entity.</li>
   * <li>For every Reference created by <code>createRef()</code> there will be
   * exactly one call to {@link #clear(PageRef)} 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(PageRef)}. Implementors may need to override
   * {@link #createRef(PackFile, long, ByteWindow)} in order to embed additional
   * accounting information into an implementation specific
   * {@link org.eclipse.jgit.internal.storage.file.WindowCache.PageRef} 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 {
 
 	/**
 	 * Record statistics for a cache
 	 */
 	static interface StatsRecorder {
 		/**
 		 * Record cache hits. Called when cache returns a cached entry.
 		 *
 		 * @param count
 		 *            number of cache hits to record
 		 */
 		void recordHits(int count);
 
 		/**
 		 * Record cache misses. Called when the cache returns an entry which had
 		 * to be loaded.
 		 *
 		 * @param count
 		 *            number of cache misses to record
 		 */
 		void recordMisses(int count);
 
 		/**
 		 * Record a successful load of a cache entry
 		 *
 		 * @param loadTimeNanos
 		 *            time to load a cache entry
 		 */
 		void recordLoadSuccess(long loadTimeNanos);
 
 		/**
 		 * Record a failed load of a cache entry
 		 *
 		 * @param loadTimeNanos
 		 *            time used trying to load a cache entry
 		 */
 		void recordLoadFailure(long loadTimeNanos);
 
 		/**
 		 * Record cache evictions due to the cache evictions strategy
 		 *
 		 * @param count
 		 *            number of evictions to record
 		 */
 		void recordEvictions(int count);
 
 		/**
 		 * Record files opened by cache
 		 *
 		 * @param delta
 		 *            delta of number of files opened by cache
 		 */
 		void recordOpenFiles(int delta);
 
 		/**
 		 * Record cached bytes
 		 *
 		 * @param pack
 		 *            pack file the bytes are read from
 		 *
 		 * @param delta
 		 *            delta of cached bytes
 		 */
 		void recordOpenBytes(PackFile pack, int delta);
 
 		/**
 		 * Returns a snapshot of this recorder's stats. Note that this may be an
 		 * inconsistent view, as it may be interleaved with update operations.
 		 *
 		 * @return a snapshot of this recorder's stats
 		 */
 		@NonNull
 		WindowCacheStats getStats();
 	}
 
 	static class StatsRecorderImpl
 			implements StatsRecorder, WindowCacheStats {
 		private final LongAdder hitCount;
 		private final LongAdder missCount;
 		private final LongAdder loadSuccessCount;
 		private final LongAdder loadFailureCount;
 		private final LongAdder totalLoadTime;
 		private final LongAdder evictionCount;
 		private final LongAdder openFileCount;
 		private final LongAdder openByteCount;
 		private final Map<String, LongAdder> openByteCountPerRepository;
 
 		/**
 		 * Constructs an instance with all counts initialized to zero.
 		 */
 		public StatsRecorderImpl() {
 			hitCount = new LongAdder();
 			missCount = new LongAdder();
 			loadSuccessCount = new LongAdder();
 			loadFailureCount = new LongAdder();
 			totalLoadTime = new LongAdder();
 			evictionCount = new LongAdder();
 			openFileCount = new LongAdder();
 			openByteCount = new LongAdder();
 			openByteCountPerRepository = new ConcurrentHashMap<>();
 		}
 
 		@Override
 		public void recordHits(int count) {
 			hitCount.add(count);
 		}
 
 		@Override
 		public void recordMisses(int count) {
 			missCount.add(count);
 		}
 
 		@Override
 		public void recordLoadSuccess(long loadTimeNanos) {
 			loadSuccessCount.increment();
 			totalLoadTime.add(loadTimeNanos);
 		}
 
 		@Override
 		public void recordLoadFailure(long loadTimeNanos) {
 			loadFailureCount.increment();
 			totalLoadTime.add(loadTimeNanos);
 		}
 
 		@Override
 		public void recordEvictions(int count) {
 			evictionCount.add(count);
 		}
 
 		@Override
 		public void recordOpenFiles(int delta) {
 			openFileCount.add(delta);
 		}
 
 		@Override
 		public void recordOpenBytes(PackFile pack, int delta) {
 			openByteCount.add(delta);
 			String repositoryId = repositoryId(pack);
 			LongAdder la = openByteCountPerRepository
 					.computeIfAbsent(repositoryId, k -> new LongAdder());
 			la.add(delta);
 			if (delta < 0) {
 				openByteCountPerRepository.computeIfPresent(repositoryId,
 						(k, v) -> v.longValue() == 0 ? null : v);
 			}
 		}
 
 		private static String repositoryId(PackFile pack) {
 			// use repository's gitdir since packfile doesn't know its
 			// repository
 			return pack.getPackFile().getParentFile().getParentFile()
 					.getParent();
 		}
 
 		@Override
 		public WindowCacheStats getStats() {
 			return this;
 		}
 
 		@Override
 		public long getHitCount() {
 			return hitCount.sum();
 		}
 
 		@Override
 		public long getMissCount() {
 			return missCount.sum();
 		}
 
 		@Override
 		public long getLoadSuccessCount() {
 			return loadSuccessCount.sum();
 		}
 
 		@Override
 		public long getLoadFailureCount() {
 			return loadFailureCount.sum();
 		}
 
 		@Override
 		public long getEvictionCount() {
 			return evictionCount.sum();
 		}
 
 		@Override
 		public long getTotalLoadTime() {
 			return totalLoadTime.sum();
 		}
 
 		@Override
 		public long getOpenFileCount() {
 			return openFileCount.sum();
 		}
 
 		@Override
 		public long getOpenByteCount() {
 			return openByteCount.sum();
 		}
 
 		@Override
 		public void resetCounters() {
 			hitCount.reset();
 			missCount.reset();
 			loadSuccessCount.reset();
 			loadFailureCount.reset();
 			totalLoadTime.reset();
 			evictionCount.reset();
 		}
 
 		@Override
 		public Map<String, Long> getOpenByteCountPerRepository() {
 			return Collections.unmodifiableMap(
 					openByteCountPerRepository.entrySet().stream()
 							.collect(Collectors.toMap(Map.Entry::getKey,
 									e -> Long.valueOf(e.getValue().sum()),
 									(u, v) -> v)));
 		}
 	}
 
 	private static final int bits(int newSize) {
 		if (newSize < 4096)
 			throw new IllegalArgumentException(JGitText.get().invalidWindowSize);
 		if (Integer.bitCount(newSize) != 1)
 			throw new IllegalArgumentException(JGitText.get().windowSizeMustBePowerOf2);
 		return Integer.numberOfTrailingZeros(newSize);
 	}
 
 	private static final Random rng = new Random();
 
 	private static volatile WindowCache cache;
 
 	private static volatile int streamFileThreshold;
 
 	static {
 		reconfigure(new WindowCacheConfig());
 	}
 
 	/**
 	 * Modify the configuration of the window cache.
 	 * <p>
 	 * The new configuration is applied immediately. If the new limits are
 	 * smaller than what is currently cached, older entries will be purged
 	 * as soon as possible to allow the cache to meet the new limit.
 	 *
 	 * @deprecated use {@code cfg.install()} to avoid internal reference.
 	 * @param cfg
 	 *            the new window cache configuration.
 	 * @throws java.lang.IllegalArgumentException
 	 *             the cache configuration contains one or more invalid
 	 *             settings, usually too low of a limit.
 	 */
 	@Deprecated
 	public static void reconfigure(WindowCacheConfig cfg) {
 		final WindowCacheal/storage/file/WindowCache.html#WindowCache">WindowCache nc = new WindowCache(cfg);
 		final WindowCache oc = cache;
 		if (oc != null)
 			oc.removeAll();
 		cache = nc;
 		streamFileThreshold = cfg.getStreamFileThreshold();
 		DeltaBaseCache.reconfigure(cfg);
 	}
 
 	static int getStreamFileThreshold() {
 		return streamFileThreshold;
 	}
 
 	/**
 	 * @return the cached instance.
 	 */
 	public static WindowCache getInstance() {
 		return cache;
 	}
 
 	static final ByteWindow get(PackFile pack, long offset)
 			throws IOException {
 		final WindowCache c = cache;
 		final ByteWindow r = c.getOrLoad(pack, c.toStart(offset));
 		if (c != cache) {
 			// The cache was reconfigured while we were using the old one
 			// to load this window. The window is still valid, but our
 			// cache may think its still live. Ensure the window is removed
 			// from the old cache so resources can be released.
 			//
 			c.removeAll();
 		}
 		return r;
 	}
 
 	static final void purge(PackFile pack) {
 		cache.removeAll(pack);
 	}
 
 	/** cleanup released and/or garbage collected windows. */
 	private final CleanupQueue 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;
 
 	private final boolean mmap;
 
 	private final int windowSizeShift;
 
 	private final int windowSize;
 
 	private final StatsRecorder statsRecorder;
 
 	private final StatsRecorderImpl mbean;
 
 	private boolean useStrongRefs;
 
 	private WindowCache(WindowCacheConfig cfg) {
 		tableSize = tableSize(cfg);
 		final int lockCount = lockCount(cfg);
 		if (tableSize < 1)
 			throw new IllegalArgumentException(JGitText.get().tSizeMustBeGreaterOrEqual1);
 		if (lockCount < 1)
 			throw new IllegalArgumentException(JGitText.get().lockCountMustBeGreaterOrEqual1);
 
 		clock = new AtomicLong(1);
 		table = new AtomicReferenceArray<>(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();
 		windowSizeShift = bits(cfg.getPackedGitWindowSize());
 		windowSize = 1 << windowSizeShift;
 		useStrongRefs = cfg.isPackedGitUseStrongRefs();
 		queue = useStrongRefs ? new StrongCleanupQueue(this)
 				: new SoftCleanupQueue(this);
 
 		mbean = new StatsRecorderImpl();
 		statsRecorder = mbean;
 		if (cfg.getExposeStatsViaJmx()) {
 			Monitoring.registerMBean(mbean, "block_cache"); //$NON-NLS-1$
 		}
 
 		if (maxFiles < 1)
 			throw new IllegalArgumentException(JGitText.get().openFilesMustBeAtLeast1);
 		if (maxBytes < windowSize)
 			throw new IllegalArgumentException(JGitText.get().windowSizeMustBeLesserThanLimit);
 	}
 
 	/**
 	 * @return cache statistics for the WindowCache
 	 */
 	public WindowCacheStats getStats() {
 		return statsRecorder.getStats();
 	}
 
 	/**
 	 * Reset stats. Does not reset open bytes and open files stats.
 	 */
 	public void resetStats() {
 		mbean.resetCounters();
 	}
 
 	private int hash(int packHash, long off) {
 		return packHash + (int) (off >>> windowSizeShift);
 	}
 
 	private ByteWindow load(PackFile pack, long offset) throws IOException {
 		long startTime = System.nanoTime();
 		if (pack.beginWindowCache())
 			statsRecorder.recordOpenFiles(1);
 		try {
 			if (mmap)
 				return pack.mmap(offset, windowSize);
 			ByteArrayWindow w = pack.read(offset, windowSize);
 			statsRecorder.recordLoadSuccess(System.nanoTime() - startTime);
 			return w;
 		} catch (IOException | RuntimeException | Error e) {
 			close(pack);
 			statsRecorder.recordLoadFailure(System.nanoTime() - startTime);
 			throw e;
 		} finally {
 			statsRecorder.recordMisses(1);
 		}
 	}
 
 	private PageRef<ByteWindow> createRef(PackFile p, long o, ByteWindow v) {
 		final PageRef<ByteWindow> ref = useStrongRefs
 				? new StrongRef(p, o, v, queue)
 				: new SoftRef(p, o, v, (SoftCleanupQueue) queue);
 		statsRecorder.recordOpenBytes(ref.getPack(), ref.getSize());
 		return ref;
 	}
 
 	private void clear(PageRef<ByteWindow> ref) {
 		statsRecorder.recordOpenBytes(ref.getPack(), -ref.getSize());
 		statsRecorder.recordEvictions(1);
 		close(ref.getPack());
 	}
 
 	private void close(PackFile pack) {
 		if (pack.endWindowCache()) {
 			statsRecorder.recordOpenFiles(-1);
 		}
 	}
 
 	private boolean isFull() {
 		return maxFiles < mbean.getOpenFileCount()
 				|| maxBytes < mbean.getOpenByteCount();
 	}
 
 	private long toStart(long offset) {
 		return (offset >>> windowSizeShift) << windowSizeShift;
 	}
 
 	private static int tableSize(WindowCacheConfig cfg) {
 		final int wsz = cfg.getPackedGitWindowSize();
 		final long limit = cfg.getPackedGitLimit();
 		if (wsz <= 0)
 			throw new IllegalArgumentException(JGitText.get().invalidWindowSize);
 		if (limit < wsz)
 			throw new IllegalArgumentException(JGitText.get().windowSizeMustBeLesserThanLimit);
 		return (int) Math.min(5 * (limit / wsz) / 2, 2000000000);
 	}
 
 	private static int lockCount(WindowCacheConfig cfg) {
 		return Math.max(cfg.getPackedGitOpenFiles(), 32);
 	}
 
 	/**
 	 * 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(PackFile pack, 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) {
 			statsRecorder.recordHits(1);
 			return v;
 		}
 
 		synchronized (lock(pack, position)) {
 			Entry e2 = table.get(slot);
 			if (e2 != e1) {
 				v = scan(e2, pack, position);
 				if (v != null) {
 					statsRecorder.recordHits(1);
 					return v;
 				}
 			}
 
 			v = load(pack, position);
 			final PageRef<ByteWindow> 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, PackFile pack, long position) {
 		for (; n != null; n = n.next) {
 			final PageRef<ByteWindow> r = n.ref;
 			if (r.getPack() == pack && r.getPosition() == position) {
 				final ByteWindow v = r.get();
 				if (v != null) {
 					hit(r);
 					return v;
 				}
 				n.kill();
 				break;
 			}
 		}
 		return null;
 	}
 
 	private void hit(PageRef 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.setLastAccess(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.getLastAccess() < old.ref
 							.getLastAccess()) {
 						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(PageRef)} 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(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.getPack() == pack) {
 					e.kill();
 					hasDead = true;
 				} else if (e.dead)
 					hasDead = true;
 			}
 			if (hasDead)
 				table.compareAndSet(s, e1, clean(e1));
 		}
 		gc();
 	}
 
 	private void gc() {
 		queue.gc();
 	}
 
 	private int slot(PackFile pack, long position) {
 		return (hash(pack.hash, position) >>> 1) % tableSize;
 	}
 
 	private Lock lock(PackFile pack, long position) {
 		return locks[(hash(pack.hash, position) >>> 1) % locks.length];
 	}
 
 	private static Entry clean(Entry top) {
 		while (top != null && top.dead) {
 			top.ref.kill();
 			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 PageRef<ByteWindow> 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(Entry n, PageRef<ByteWindow> r) {
 			next = n;
 			ref = r;
 		}
 
 		final void kill() {
 			dead = true;
 			ref.kill();
 		}
 	}
 
 	private static interface PageRef<T> {
 		/**
 		 * Returns this reference object's referent. If this reference object
 		 * has been cleared, either by the program or by the garbage collector,
 		 * then this method returns <code>null</code>.
 		 *
 		 * @return The object to which this reference refers, or
 		 *         <code>null</code> if this reference object has been cleared
 		 */
 		T get();
 
 	    /**
 		 * Kill this ref
 		 *
 		 * @return <code>true</code> if this reference object was successfully
 		 *         killed; <code>false</code> if it was already killed
 		 */
 		boolean kill();
 
 		/**
 		 * Get the packfile the referenced cache page is allocated for
 		 *
 		 * @return the packfile the referenced cache page is allocated for
 		 */
 		PackFile getPack();
 
 		/**
 		 * Get the position of the referenced cache page in the packfile
 		 *
 		 * @return the position of the referenced cache page in the packfile
 		 */
 		long getPosition();
 
 		/**
 		 * Get size of cache page
 		 *
 		 * @return size of cache page
 		 */
 		int getSize();
 
 		/**
 		 * Get pseudo time of last access to this cache page
 		 *
 		 * @return pseudo time of last access to this cache page
 		 */
 		long getLastAccess();
 
 		/**
 		 * Set pseudo time of last access to this cache page
 		 *
 		 * @param time
 		 *            pseudo time of last access to this cache page
 		 */
 		void setLastAccess(long time);
 
 		/**
 		 * Whether this is a strong reference.
 		 * @return {@code true} if this is a strong reference
 		 */
 		boolean isStrongRef();
 	}
 
 	/** A soft reference wrapped around a cached object. */
 	private static class SoftRef extends SoftReference<ByteWindow>
 			implements PageRef<ByteWindow> {
 		private final PackFile pack;
 
 		private final long position;
 
 		private final int size;
 
 		private long lastAccess;
 
 		protected SoftRef(final PackFile pack, final long position,
 				final ByteWindow v, final SoftCleanupQueue queue) {
 			super(v, queue);
 			this.pack = pack;
 			this.position = position;
 			this.size = v.size();
 		}
 
 		@Override
 		public PackFile getPack() {
 			return pack;
 		}
 
 		@Override
 		public long getPosition() {
 			return position;
 		}
 
 		@Override
 		public int getSize() {
 			return size;
 		}
 
 		@Override
 		public long getLastAccess() {
 			return lastAccess;
 		}
 
 		@Override
 		public void setLastAccess(long time) {
 			this.lastAccess = time;
 		}
 
 		@Override
 		public boolean kill() {
 			return enqueue();
 		}
 
 		@Override
 		public boolean isStrongRef() {
 			return false;
 		}
 	}
 
 	/** A strong reference wrapped around a cached object. */
 	private static class StrongRef implements PageRef<ByteWindow> {
 		private ByteWindow referent;
 
 		private final PackFile pack;
 
 		private final long position;
 
 		private final int size;
 
 		private long lastAccess;
 
 		private CleanupQueue queue;
 
 		protected StrongRef(final PackFile pack, final long position,
 				final ByteWindow v, final CleanupQueue queue) {
 			this.pack = pack;
 			this.position = position;
 			this.referent = v;
 			this.size = v.size();
 			this.queue = queue;
 		}
 
 		@Override
 		public PackFile getPack() {
 			return pack;
 		}
 
 		@Override
 		public long getPosition() {
 			return position;
 		}
 
 		@Override
 		public int getSize() {
 			return size;
 		}
 
 		@Override
 		public long getLastAccess() {
 			return lastAccess;
 		}
 
 		@Override
 		public void setLastAccess(long time) {
 			this.lastAccess = time;
 		}
 
 		@Override
 		public ByteWindow get() {
 			return referent;
 		}
 
 		@Override
 		public boolean kill() {
 			if (referent == null) {
 				return false;
 			}
 			referent = null;
 			return queue.enqueue(this);
 		}
 
 		@Override
 		public boolean isStrongRef() {
 			return true;
 		}
 	}
 
 	private static interface CleanupQueue {
 		boolean enqueue(PageRef<ByteWindow> r);
 		void gc();
 	}
 
 	private static class SoftCleanupQueue extends ReferenceQueue<ByteWindow>
 			implements CleanupQueue {
 		private final WindowCache wc;
 
 		SoftCleanupQueue(WindowCache cache) {
 			this.wc = cache;
 		}
 
 		@Override
 		public boolean enqueue(PageRef<ByteWindow> r) {
 			// no need to explicitly add soft references which are enqueued by
 			// the JVM
 			return false;
 		}
 
 		@Override
 		public void gc() {
 			SoftRef r;
 			while ((r = (SoftRef) poll()) != null) {
 				wc.clear(r);
 
 				final int s = wc.slot(r.getPack(), r.getPosition());
 				final Entry e1 = wc.table.get(s);
 				for (Entry n = e1; n != null; n = n.next) {
 					if (n.ref == r) {
 						n.dead = true;
 						wc.table.compareAndSet(s, e1, clean(e1));
 						break;
 					}
 				}
 			}
 		}
 	}
 
 	private static class StrongCleanupQueue implements CleanupQueue {
 		private final WindowCache wc;
 
 		private final ConcurrentLinkedQueue<PageRef<ByteWindow>> queue = new ConcurrentLinkedQueue<>();
 
 		StrongCleanupQueue(WindowCache wc) {
 			this.wc = wc;
 		}
 
 		@Override
 		public boolean enqueue(PageRef<ByteWindow> r) {
 			if (queue.contains(r)) {
 				return false;
 			}
 			return queue.add(r);
 		}
 
 		@Override
 		public void gc() {
 			PageRef<ByteWindow> r;
 			while ((r = queue.poll()) != null) {
 				wc.clear(r);
 
 				final int s = wc.slot(r.getPack(), r.getPosition());
 				final Entry e1 = wc.table.get(s);
 				for (Entry n = e1; n != null; n = n.next) {
 					if (n.ref == r) {
 						n.dead = true;
 						wc.table.compareAndSet(s, e1, clean(e1));
 						break;
 					}
 				}
 			}
 		}
 	}
 
 	private static final class Lock {
 		// Used only for its implicit monitor.
 	}
 }