org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java

   1 /*
   2  * Copyright (C) 2007, Robin Rosenberg <robin.rosenberg@dewire.com>
   3  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
   4  *
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or
   8  * without modification, are permitted provided that the following
   9  * conditions are met:
  10  *
  11  * - Redistributions of source code must retain the above copyright
  12  *   notice, this list of conditions and the following disclaimer.
  13  *
  14  * - Redistributions in binary form must reproduce the above
  15  *   copyright notice, this list of conditions and the following
  16  *   disclaimer in the documentation and/or other materials provided
  17  *   with the distribution.
  18  *
  19  * - Neither the name of the Git Development Community nor the
  20  *   names of its contributors may be used to endorse or promote
  21  *   products derived from this software without specific prior
  22  *   written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  25  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  26  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  27  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  28  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  29  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  31  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  32  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  33  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  34  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  35  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  36  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  37  */
  38
  39 package org.spearce.jgit.lib;
  40
  41 import java.io.IOException;
  42 import java.lang.ref.ReferenceQueue;
  43
  44 /**
  45  * The WindowCache manages reusable <code>Windows</code> and inflaters used by
  46  * the other windowed file access classes.
  47  */
  48 public class WindowCache {
  49         private static final int KB = 1024;
  50
  51         private static final int MB = 1024 * KB;
  52
  53         private static final int bits(int newSize) {
  54                 if (newSize < 4096)
  55                         throw new IllegalArgumentException("Invalid window size");
  56                 if (Integer.bitCount(newSize) != 1)
  57                         throw new IllegalArgumentException("Window size must be power of 2");
  58                 return Integer.numberOfTrailingZeros(newSize);
  59         }
  60
  61         private static int maxByteCount;
  62
  63         private static int windowSize;
  64
  65         private static int windowSizeShift;
  66
  67         static boolean mmap;
  68
  69         static final ReferenceQueue<?> clearedWindowQueue;
  70
  71         private static ByteWindow[] windows;
  72
  73         private static int openWindowCount;
  74
  75         private static int openByteCount;
  76
  77         private static int accessClock;
  78
  79         static {
  80                 maxByteCount = 10 * MB;
  81                 windowSizeShift = bits(8 * KB);
  82                 windowSize = 1 << windowSizeShift;
  83                 mmap = false;
  84                 windows = new ByteWindow[maxByteCount / windowSize];
  85                 clearedWindowQueue = new ReferenceQueue<Object>();
  86         }
  87
  88         /**
  89          * Modify the configuration of the window cache.
  90          * <p>
  91          * The new configuration is applied immediately. If the new limits are
  92          * smaller than what what is currently cached, older entries will be purged
  93          * as soon as possible to allow the cache to meet the new limit.
  94          *
  95          * @param packedGitLimit
  96          *            maximum number of bytes to hold within this instance.
  97          * @param packedGitWindowSize
  98          *            number of bytes per window within the cache.
  99          * @param packedGitMMAP
 100          *            true to enable use of mmap when creating windows.
 101          * @param deltaBaseCacheLimit
 102          *            number of bytes to hold in the delta base cache.
 103          */
 104         public static void reconfigure(final int packedGitLimit,
 105                         final int packedGitWindowSize, final boolean packedGitMMAP,
 106                         final int deltaBaseCacheLimit) {
 107                 reconfigureImpl(packedGitLimit, packedGitWindowSize, packedGitMMAP);
 108                 UnpackedObjectCache.reconfigure(deltaBaseCacheLimit);
 109         }
 110
 111         private static synchronized void reconfigureImpl(final int packedGitLimit,
 112                         final int packedGitWindowSize, final boolean packedGitMMAP) {
 113                 boolean prune = false;
 114                 boolean evictAll = false;
 115
 116                 if (maxByteCount < packedGitLimit) {
 117                         maxByteCount = packedGitLimit;
 118                 } else if (maxByteCount > packedGitLimit) {
 119                         maxByteCount = packedGitLimit;
 120                         prune = true;
 121                 }
 122
 123                 if (bits(packedGitWindowSize) != windowSizeShift) {
 124                         windowSizeShift = bits(packedGitWindowSize);
 125                         windowSize = 1 << windowSizeShift;
 126                         evictAll = true;
 127                 }
 128
 129                 if (mmap != packedGitMMAP) {
 130                         mmap = packedGitMMAP;
 131                         evictAll = true;
 132                 }
 133
 134                 if (evictAll) {
 135                         // We have to throw away every window we have. None
 136                         // of them are suitable for the new configuration.
 137                         //
 138                         for (int i = 0; i < openWindowCount; i++) {
 139                                 final ByteWindow win = windows[i];
 140                                 if (--win.provider.openCount == 0)
 141                                         win.provider.cacheClose();
 142                                 windows[i] = null;
 143                         }
 144                         windows = new ByteWindow[maxByteCount / windowSize];
 145                         openWindowCount = 0;
 146                         openByteCount = 0;
 147                 } else if (prune) {
 148                         // Our memory limit was decreased so we should try
 149                         // to drop windows to ensure we meet the new lower
 150                         // limit we were just given.
 151                         //
 152                         final int wincnt = maxByteCount / windowSize;
 153                         releaseMemory(wincnt, null, 0, 0);
 154
 155                         if (wincnt != windows.length) {
 156                                 final ByteWindow[] n = new ByteWindow[wincnt];
 157                                 System.arraycopy(windows, 0, n, 0, openWindowCount);
 158                                 windows = n;
 159                         }
 160                 }
 161         }
 162
 163         /**
 164          * Get a specific window.
 165          *
 166          * @param curs
 167          *            an active cursor object to maintain the window reference while
 168          *            the caller needs it.
 169          * @param wp
 170          *            the provider of the window. If the window is not currently in
 171          *            the cache then the provider will be asked to load it.
 172          * @param position
 173          *            offset (in bytes) within the file that the caller needs access
 174          *            to.
 175          * @throws IOException
 176          *             the window was not found in the cache and the given provider
 177          *             was unable to load the window on demand.
 178          */
 179         public static synchronized final void get(final WindowCursor curs,
 180                         final WindowedFile wp, final long position) throws IOException {
 181                 final int id = (int) (position >> windowSizeShift);
 182                 int idx = binarySearch(wp, id);
 183                 if (0 <= idx) {
 184                         final ByteWindow<?> w = windows[idx];
 185                         if ((curs.handle = w.get()) != null) {
 186                                 w.lastAccessed = ++accessClock;
 187                                 curs.window = w;
 188                                 return;
 189                         }
 190                 }
 191
 192                 if (++wp.openCount == 1) {
 193                         try {
 194                                 wp.cacheOpen();
 195                         } catch (IOException ioe) {
 196                                 wp.openCount = 0;
 197                                 throw ioe;
 198                         } catch (RuntimeException ioe) {
 199                                 wp.openCount = 0;
 200                                 throw ioe;
 201                         } catch (Error ioe) {
 202                                 wp.openCount = 0;
 203                                 throw ioe;
 204                         }
 205
 206                         // The cacheOpen may have mapped the window we are trying to
 207                         // map ourselves. Retrying the search ensures that does not
 208                         // happen to us.
 209                         //
 210                         idx = binarySearch(wp, id);
 211                         if (0 <= idx) {
 212                                 final ByteWindow<?> w = windows[idx];
 213                                 if ((curs.handle = w.get()) != null) {
 214                                         w.lastAccessed = ++accessClock;
 215                                         curs.window = w;
 216                                         return;
 217                                 }
 218                         }
 219                 }
 220
 221                 idx = -(idx + 1);
 222                 final int wSz = windowSize(wp, id);
 223                 idx = releaseMemory(windows.length, wp, idx, wSz);
 224
 225                 if (idx < 0)
 226                         idx = 0;
 227                 final int toMove = openWindowCount - idx;
 228                 if (toMove > 0)
 229                         System.arraycopy(windows, idx, windows, idx + 1, toMove);
 230                 wp.loadWindow(curs, id, id << windowSizeShift, wSz);
 231                 windows[idx] = curs.window;
 232                 openWindowCount++;
 233                 openByteCount += curs.window.size;
 234         }
 235
 236         private static int releaseMemory(final int maxWindowCount,
 237                         final WindowedFile willRead, int insertionIndex, final int willAdd) {
 238                 for (;;) {
 239                         final ByteWindow<?> w = (ByteWindow<?>) clearedWindowQueue.poll();
 240                         if (w == null)
 241                                 break;
 242                         final int oldest = binarySearch(w.provider, w.id);
 243                         if (oldest < 0 || windows[oldest] != w)
 244                                 continue; // Must have been evicted by our other controls.
 245
 246                         final WindowedFile p = w.provider;
 247                         if (--p.openCount == 0 && p != willRead)
 248                                 p.cacheClose();
 249
 250                         openByteCount -= w.size;
 251                         final int toMove = openWindowCount - oldest - 1;
 252                         if (toMove > 0)
 253                                 System.arraycopy(windows, oldest + 1, windows, oldest, toMove);
 254                         windows[--openWindowCount] = null;
 255                         if (oldest < insertionIndex)
 256                                 insertionIndex--;
 257                 }
 258
 259                 while (openWindowCount >= maxWindowCount
 260                                 || (openWindowCount > 0 && openByteCount + willAdd > maxByteCount)) {
 261                         int oldest = 0;
 262                         for (int k = openWindowCount - 1; k > 0; k--) {
 263                                 if (windows[k].lastAccessed < windows[oldest].lastAccessed)
 264                                         oldest = k;
 265                         }
 266
 267                         final ByteWindow w = windows[oldest];
 268                         final WindowedFile p = w.provider;
 269                         if (--p.openCount == 0 && p != willRead)
 270                                 p.cacheClose();
 271
 272                         openByteCount -= w.size;
 273                         final int toMove = openWindowCount - oldest - 1;
 274                         if (toMove > 0)
 275                                 System.arraycopy(windows, oldest + 1, windows, oldest, toMove);
 276                         windows[--openWindowCount] = null;
 277                         w.enqueue();
 278                         if (oldest < insertionIndex)
 279                                 insertionIndex--;
 280                 }
 281
 282                 return insertionIndex;
 283         }
 284
 285         private static final int binarySearch(final WindowedFile sprov,
 286                         final int sid) {
 287                 if (openWindowCount == 0)
 288                         return -1;
 289                 final int shc = sprov.hash;
 290                 int high = openWindowCount;
 291                 int low = 0;
 292                 do {
 293                         final int mid = (low + high) / 2;
 294                         final ByteWindow mw = windows[mid];
 295                         if (mw.provider == sprov && mw.id == sid)
 296                                 return mid;
 297                         final int mhc = mw.provider.hash;
 298                         if (mhc < shc || (shc == mhc && mw.id < sid))
 299                                 low = mid + 1;
 300                         else
 301                                 high = mid;
 302                 } while (low < high);
 303                 return -(low + 1);
 304         }
 305
 306         /**
 307          * Remove all windows associated with a specific provider.
 308          * <p>
 309          * Providers should invoke this method as part of their cleanup/close
 310          * routines, ensuring that the window cache releases all windows that cannot
 311          * ever be requested again.
 312          * </p>
 313          *
 314          * @param wp
 315          *            the window provider whose windows should be removed from the
 316          *            cache.
 317          */
 318         public static synchronized final void purge(final WindowedFile wp) {
 319                 int d = 0;
 320                 for (int s = 0; s < openWindowCount; s++) {
 321                         final ByteWindow win = windows[s];
 322                         if (win.provider != wp)
 323                                 windows[d++] = win;
 324                         else
 325                                 openByteCount -= win.size;
 326                 }
 327                 openWindowCount = d;
 328
 329                 if (wp.openCount > 0) {
 330                         wp.openCount = 0;
 331                         wp.cacheClose();
 332                 }
 333         }
 334
 335         private static int windowSize(final WindowedFile file, final int id) {
 336                 final long len = file.length();
 337                 final long pos = id << windowSizeShift;
 338                 return len < pos + windowSize ? (int) (len - pos) : windowSize;
 339         }
 340
 341         private WindowCache() {
 342                 throw new UnsupportedOperationException();
 343         }
 344 }