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

   1 /*
   2  *  Copyright (C) 2006  Shawn Pearce <spearce@spearce.org>
   3  *
   4  *  This library is free software; you can redistribute it and/or
   5  *  modify it under the terms of the GNU General Public
   6  *  License, version 2, as published by the Free Software Foundation.
   7  *
   8  *  This library is distributed in the hope that it will be useful,
   9  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  *  General Public License for more details.
  12  *
  13  *  You should have received a copy of the GNU General Public
  14  *  License along with this library; if not, write to the Free Software
  15  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301
  16  */
  17 package org.spearce.jgit.lib;
  18
  19 import java.io.IOException;
  20 import java.lang.ref.ReferenceQueue;
  21 import java.util.zip.Inflater;
  22
  23 /**
  24  * The WindowCache manages reusable <code>Windows</code> and inflaters used by
  25  * the other windowed file access classes.
  26  */
  27 public class WindowCache {
  28         private static final int KB = 1024;
  29
  30         private static final int MB = 1024 * KB;
  31
  32         private static final int bits(int newSize) {
  33                 if (newSize < 4096)
  34                         throw new IllegalArgumentException("Invalid window size");
  35                 if (Integer.bitCount(newSize) != 1)
  36                         throw new IllegalArgumentException("Window size must be power of 2");
  37                 return Integer.numberOfTrailingZeros(newSize);
  38         }
  39
  40         private static final Inflater[] inflaterCache;
  41
  42         private static final int maxByteCount;
  43
  44         static final int sz;
  45
  46         static final int szb;
  47
  48         static final int szm;
  49
  50         static final boolean mmap;
  51
  52         static final ReferenceQueue<?> clearedWindowQueue;
  53
  54         private static final ByteWindow[] windows;
  55
  56         private static int openWindowCount;
  57
  58         private static int openByteCount;
  59
  60         private static int openInflaterCount;
  61
  62         private static int accessClock;
  63
  64         static {
  65                 maxByteCount = 10 * MB;
  66                 szb = bits(8 * KB);
  67                 sz = 1 << szb;
  68                 szm = (1 << szb) - 1;
  69                 mmap = false;
  70                 windows = new ByteWindow[maxByteCount / sz];
  71                 inflaterCache = new Inflater[4];
  72                 clearedWindowQueue = new ReferenceQueue<Object>();
  73         }
  74
  75         /**
  76          * Modify the configuration of the window cache.
  77          * <p>
  78          * The new configuration is applied immediately. If the new limits are
  79          * smaller than what what is currently cached, older entries will be purged
  80          * as soon as possible to allow the cache to meet the new limit.
  81          *
  82          * @param packedGitLimit
  83          *            maximum number of bytes to hold within this instance.
  84          * @param packedGitWindowSize
  85          *            number of bytes per window within the cache.
  86          * @param packedGitMMAP
  87          *            true to enable use of mmap when creating windows.
  88          * @param deltaBaseCacheLimit
  89          *            number of bytes to hold in the delta base cache.
  90          */
  91         public static void reconfigure(final int packedGitLimit,
  92                         final int packedGitWindowSize, final boolean packedGitMMAP,
  93                         final int deltaBaseCacheLimit) {
  94                 // fix me
  95                 UnpackedObjectCache.reconfigure(deltaBaseCacheLimit);
  96         }
  97
  98         synchronized static Inflater borrowInflater() {
  99                 if (openInflaterCount > 0) {
 100                         final Inflater r = inflaterCache[--openInflaterCount];
 101                         inflaterCache[openInflaterCount] = null;
 102                         return r;
 103                 }
 104                 return new Inflater(false);
 105         }
 106
 107         synchronized static void returnInflater(final Inflater i) {
 108                 if (openInflaterCount == inflaterCache.length)
 109                         i.end();
 110                 else
 111                         inflaterCache[openInflaterCount++] = i;
 112         }
 113
 114         /**
 115          * Get a specific window.
 116          *
 117          * @param curs
 118          *            an active cursor object to maintain the window reference while
 119          *            the caller needs it.
 120          * @param wp
 121          *            the provider of the window. If the window is not currently in
 122          *            the cache then the provider will be asked to load it.
 123          * @param id
 124          *            the id, unique only within the scope of the specific provider
 125          *            <code>wp</code>. Typically this id is the byte offset
 126          *            within the file divided by the window size, but its meaning is
 127          *            left open to the provider.
 128          * @throws IOException
 129          *             the window was not found in the cache and the given provider
 130          *             was unable to load the window on demand.
 131          */
 132         public static synchronized final void get(final WindowCursor curs,
 133                         final WindowedFile wp, final int id) throws IOException {
 134                 int idx = binarySearch(wp, id);
 135                 if (0 <= idx) {
 136                         final ByteWindow<?> w = windows[idx];
 137                         if ((curs.handle = w.get()) != null) {
 138                                 w.lastAccessed = ++accessClock;
 139                                 curs.window = w;
 140                                 return;
 141                         }
 142                 }
 143
 144                 if (++wp.openCount == 1) {
 145                         try {
 146                                 wp.cacheOpen();
 147                         } catch (IOException ioe) {
 148                                 wp.openCount = 0;
 149                                 throw ioe;
 150                         } catch (RuntimeException ioe) {
 151                                 wp.openCount = 0;
 152                                 throw ioe;
 153                         } catch (Error ioe) {
 154                                 wp.openCount = 0;
 155                                 throw ioe;
 156                         }
 157
 158                         // The cacheOpen may have mapped the window we are trying to
 159                         // map ourselves. Retrying the search ensures that does not
 160                         // happen to us.
 161                         //
 162                         idx = binarySearch(wp, id);
 163                         if (0 <= idx) {
 164                                 final ByteWindow<?> w = windows[idx];
 165                                 if ((curs.handle = w.get()) != null) {
 166                                         w.lastAccessed = ++accessClock;
 167                                         curs.window = w;
 168                                         return;
 169                                 }
 170                         }
 171                 }
 172
 173                 idx = -(idx + 1);
 174                 for (;;) {
 175                         final ByteWindow<?> w = (ByteWindow<?>) clearedWindowQueue.poll();
 176                         if (w == null)
 177                                 break;
 178                         final int oldest = binarySearch(w.provider, w.id);
 179                         if (oldest < 0 || windows[oldest] != w)
 180                                 continue; // Must have been evicted by our other controls.
 181
 182                         final WindowedFile p = w.provider;
 183                         if (--p.openCount == 0 && p != wp)
 184                                 p.cacheClose();
 185
 186                         openByteCount -= w.size;
 187                         final int toMove = openWindowCount - oldest - 1;
 188                         if (toMove > 0)
 189                                 System.arraycopy(windows, oldest + 1, windows, oldest, toMove);
 190                         windows[--openWindowCount] = null;
 191                         if (oldest < idx)
 192                                 idx--;
 193                 }
 194
 195                 final int wSz = wp.getWindowSize(id);
 196                 while (openWindowCount == windows.length
 197                                 || (openWindowCount > 0 && openByteCount + wSz > maxByteCount)) {
 198                         int oldest = 0;
 199                         for (int k = openWindowCount - 1; k > 0; k--) {
 200                                 if (windows[k].lastAccessed < windows[oldest].lastAccessed)
 201                                         oldest = k;
 202                         }
 203
 204                         final ByteWindow w = windows[oldest];
 205                         final WindowedFile p = w.provider;
 206                         if (--p.openCount == 0 && p != wp)
 207                                 p.cacheClose();
 208
 209                         openByteCount -= w.size;
 210                         final int toMove = openWindowCount - oldest - 1;
 211                         if (toMove > 0)
 212                                 System.arraycopy(windows, oldest + 1, windows, oldest, toMove);
 213                         windows[--openWindowCount] = null;
 214                         w.enqueue();
 215                         if (oldest < idx)
 216                                 idx--;
 217                 }
 218
 219                 if (idx < 0)
 220                         idx = 0;
 221                 final int toMove = openWindowCount - idx;
 222                 if (toMove > 0)
 223                         System.arraycopy(windows, idx, windows, idx + 1, toMove);
 224                 wp.loadWindow(curs, id);
 225                 windows[idx] = curs.window;
 226                 openWindowCount++;
 227                 openByteCount += curs.window.size;
 228         }
 229
 230         private static final int binarySearch(final WindowedFile sprov,
 231                         final int sid) {
 232                 if (openWindowCount == 0)
 233                         return -1;
 234                 final int shc = sprov.hash;
 235                 int high = openWindowCount;
 236                 int low = 0;
 237                 do {
 238                         final int mid = (low + high) / 2;
 239                         final ByteWindow mw = windows[mid];
 240                         if (mw.provider == sprov && mw.id == sid)
 241                                 return mid;
 242                         final int mhc = mw.provider.hash;
 243                         if (mhc < shc || (shc == mhc && mw.id < sid))
 244                                 low = mid + 1;
 245                         else
 246                                 high = mid;
 247                 } while (low < high);
 248                 return -(low + 1);
 249         }
 250
 251         /**
 252          * Remove all windows associated with a specific provider.
 253          * <p>
 254          * Providers should invoke this method as part of their cleanup/close
 255          * routines, ensuring that the window cache releases all windows that cannot
 256          * ever be requested again.
 257          * </p>
 258          *
 259          * @param wp
 260          *            the window provider whose windows should be removed from the
 261          *            cache.
 262          */
 263         public static synchronized final void purge(final WindowedFile wp) {
 264                 int d = 0;
 265                 for (int s = 0; s < openWindowCount; s++) {
 266                         final ByteWindow win = windows[s];
 267                         if (win.provider != wp)
 268                                 windows[d++] = win;
 269                         else
 270                                 openByteCount -= win.size;
 271                 }
 272                 openWindowCount = d;
 273
 274                 if (wp.openCount > 0) {
 275                         wp.openCount = 0;
 276                         wp.cacheClose();
 277                 }
 278         }
 279
 280         private WindowCache() {
 281                 throw new UnsupportedOperationException();
 282         }
 283 }