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

   1 /*
   2  * Copyright (C) 2008, Google Inc.
   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 bits(int newSize) {
  50                 if (newSize < 4096)
  51                         throw new IllegalArgumentException("Invalid window size");
  52                 if (Integer.bitCount(newSize) != 1)
  53                         throw new IllegalArgumentException("Window size must be power of 2");
  54                 return Integer.numberOfTrailingZeros(newSize);
  55         }
  56
  57         private static int maxFileCount;
  58
  59         private static int maxByteCount;
  60
  61         private static int windowSize;
  62
  63         private static int windowSizeShift;
  64
  65         static boolean mmap;
  66
  67         static final ReferenceQueue<?> clearedWindowQueue;
  68
  69         private static ByteWindow[] cache;
  70
  71         private static ByteWindow lruHead;
  72
  73         private static ByteWindow lruTail;
  74
  75         private static int openFileCount;
  76
  77         private static int openByteCount;
  78
  79         static {
  80                 final WindowCacheConfig c = new WindowCacheConfig();
  81                 maxFileCount = c.getPackedGitOpenFiles();
  82                 maxByteCount = c.getPackedGitLimit();
  83                 windowSizeShift = bits(c.getPackedGitWindowSize());
  84                 windowSize = 1 << windowSizeShift;
  85                 mmap = c.isPackedGitMMAP();
  86                 cache = new ByteWindow[cacheTableSize()];
  87                 clearedWindowQueue = new ReferenceQueue<Object>();
  88         }
  89
  90         private static int cacheTableSize() {
  91                 return 5 * (maxByteCount / windowSize) / 2;
  92         }
  93
  94         /**
  95          * Modify the configuration of the window cache.
  96          * <p>
  97          * The new configuration is applied immediately. If the new limits are
  98          * smaller than what what is currently cached, older entries will be purged
  99          * as soon as possible to allow the cache to meet the new limit.
 100          *
 101          * @param packedGitLimit
 102          *            maximum number of bytes to hold within this instance.
 103          * @param packedGitWindowSize
 104          *            number of bytes per window within the cache.
 105          * @param packedGitMMAP
 106          *            true to enable use of mmap when creating windows.
 107          * @param deltaBaseCacheLimit
 108          *            number of bytes to hold in the delta base cache.
 109          * @deprecated Use {@link WindowCacheConfig} instead.
 110          */
 111         public static void reconfigure(final int packedGitLimit,
 112                         final int packedGitWindowSize, final boolean packedGitMMAP,
 113                         final int deltaBaseCacheLimit) {
 114                 final WindowCacheConfig c = new WindowCacheConfig();
 115                 c.setPackedGitLimit(packedGitLimit);
 116                 c.setPackedGitWindowSize(packedGitWindowSize);
 117                 c.setPackedGitMMAP(packedGitMMAP);
 118                 c.setDeltaBaseCacheLimit(deltaBaseCacheLimit);
 119                 reconfigure(c);
 120         }
 121
 122         /**
 123          * Modify the configuration of the window cache.
 124          * <p>
 125          * The new configuration is applied immediately. If the new limits are
 126          * smaller than what what is currently cached, older entries will be purged
 127          * as soon as possible to allow the cache to meet the new limit.
 128          *
 129          * @param cfg
 130          *            the new window cache configuration.
 131          */
 132         public static void reconfigure(final WindowCacheConfig cfg) {
 133                 reconfigureImpl(cfg);
 134                 UnpackedObjectCache.reconfigure(cfg);
 135         }
 136
 137         private static synchronized void reconfigureImpl(final WindowCacheConfig cfg) {
 138                 boolean prune = false;
 139                 boolean evictAll = false;
 140
 141                 if (maxFileCount < cfg.getPackedGitOpenFiles())
 142                         maxFileCount = cfg.getPackedGitOpenFiles();
 143                 else if (maxFileCount > cfg.getPackedGitOpenFiles()) {
 144                         maxFileCount = cfg.getPackedGitOpenFiles();
 145                         prune = true;
 146                 }
 147
 148                 if (maxByteCount < cfg.getPackedGitLimit()) {
 149                         maxByteCount = cfg.getPackedGitLimit();
 150                 } else if (maxByteCount > cfg.getPackedGitLimit()) {
 151                         maxByteCount = cfg.getPackedGitLimit();
 152                         prune = true;
 153                 }
 154
 155                 if (bits(cfg.getPackedGitWindowSize()) != windowSizeShift) {
 156                         windowSizeShift = bits(cfg.getPackedGitWindowSize());
 157                         windowSize = 1 << windowSizeShift;
 158                         evictAll = true;
 159                 }
 160
 161                 if (mmap != cfg.isPackedGitMMAP()) {
 162                         mmap = cfg.isPackedGitMMAP();
 163                         evictAll = true;
 164                 }
 165
 166                 if (evictAll) {
 167                         // We have to throw away every window we have. None
 168                         // of them are suitable for the new configuration.
 169                         //
 170                         for (ByteWindow<?> e : cache) {
 171                                 for (; e != null; e = e.chainNext)
 172                                         clear(e);
 173                         }
 174                         runClearedWindowQueue();
 175                         cache = new ByteWindow[cacheTableSize()];
 176
 177                 } else {
 178                         if (prune) {
 179                                 // We should decrease our memory usage.
 180                                 //
 181                                 releaseMemory();
 182                                 runClearedWindowQueue();
 183                         }
 184
 185                         if (cache.length != cacheTableSize()) {
 186                                 // The cache table should be resized.
 187                                 // Rehash every entry.
 188                                 //
 189                                 final ByteWindow[] priorTable = cache;
 190
 191                                 cache = new ByteWindow[cacheTableSize()];
 192                                 for (ByteWindow<?> e : priorTable) {
 193                                         for (ByteWindow<?> n; e != null; e = n) {
 194                                                 n = e.chainNext;
 195                                                 final int idx = hash(e.provider, e.id);
 196                                                 e.chainNext = cache[idx];
 197                                                 cache[idx] = e;
 198                                         }
 199                                 }
 200                         }
 201                 }
 202         }
 203
 204         /**
 205          * Get a specific window.
 206          *
 207          * @param curs
 208          *            an active cursor object to maintain the window reference while
 209          *            the caller needs it.
 210          * @param wp
 211          *            the provider of the window. If the window is not currently in
 212          *            the cache then the provider will be asked to load it.
 213          * @param position
 214          *            offset (in bytes) within the file that the caller needs access
 215          *            to.
 216          * @throws IOException
 217          *             the window was not found in the cache and the given provider
 218          *             was unable to load the window on demand.
 219          */
 220         public static final void get(final WindowCursor curs, final PackFile wp,
 221                         final long position) throws IOException {
 222                 getImpl(curs, wp, position);
 223                 curs.window.ensureLoaded(curs.handle);
 224         }
 225
 226         static synchronized final void pin(final PackFile wp) throws IOException {
 227                 if (++wp.openCount == 1) {
 228                         openFile(wp);
 229                 }
 230         }
 231
 232         static synchronized final void unpin(final PackFile wp) {
 233                 if (--wp.openCount == 0) {
 234                         openFileCount--;
 235                         wp.cacheClose();
 236                 }
 237         }
 238
 239         private static synchronized final void getImpl(final WindowCursor curs,
 240                         final PackFile wp, final long position) throws IOException {
 241                 final int id = (int) (position >> windowSizeShift);
 242                 final int idx = hash(wp, id);
 243                 for (ByteWindow<?> e = cache[idx]; e != null; e = e.chainNext) {
 244                         if (e.provider == wp && e.id == id) {
 245                                 if ((curs.handle = e.get()) != null) {
 246                                         curs.window = e;
 247                                         makeMostRecent(e);
 248                                         return;
 249                                 }
 250
 251                                 clear(e);
 252                                 break;
 253                         }
 254                 }
 255
 256                 if (wp.openCount == 0) {
 257                         openFile(wp);
 258
 259                         // The cacheOpen may have mapped the window we are trying to
 260                         // map ourselves. Retrying the search ensures that does not
 261                         // happen to us.
 262                         //
 263                         for (ByteWindow<?> e = cache[idx]; e != null; e = e.chainNext) {
 264                                 if (e.provider == wp && e.id == id) {
 265                                         if ((curs.handle = e.get()) != null) {
 266                                                 curs.window = e;
 267                                                 makeMostRecent(e);
 268                                                 return;
 269                                         }
 270
 271                                         clear(e);
 272                                         break;
 273                                 }
 274                         }
 275                 }
 276
 277                 final int wsz = windowSize(wp, id);
 278                 wp.openCount++;
 279                 openByteCount += wsz;
 280                 releaseMemory();
 281                 runClearedWindowQueue();
 282
 283                 wp.allocWindow(curs, id, (position >>> windowSizeShift) << windowSizeShift, wsz);
 284                 final ByteWindow<?> e = curs.window;
 285                 e.chainNext = cache[idx];
 286                 cache[idx] = e;
 287                 insertLRU(e);
 288         }
 289
 290         private static void openFile(final PackFile wp) throws IOException {
 291                 try {
 292                         openFileCount++;
 293                         releaseMemory();
 294                         runClearedWindowQueue();
 295                         wp.openCount = 1;
 296                         wp.cacheOpen();
 297                 } catch (IOException ioe) {
 298                         openFileCount--;
 299                         wp.openCount = 0;
 300                         throw ioe;
 301                 } catch (RuntimeException ioe) {
 302                         openFileCount--;
 303                         wp.openCount = 0;
 304                         throw ioe;
 305                 } catch (Error ioe) {
 306                         openFileCount--;
 307                         wp.openCount = 0;
 308                         throw ioe;
 309                 } finally {
 310                         wp.openCount--;
 311                 }
 312         }
 313
 314         static synchronized void markLoaded(final ByteWindow w) {
 315                 if (--w.provider.openCount == 0) {
 316                         openFileCount--;
 317                         w.provider.cacheClose();
 318                 }
 319         }
 320
 321         private static void makeMostRecent(ByteWindow<?> e) {
 322                 if (lruHead != e) {
 323                         unlinkLRU(e);
 324                         insertLRU(e);
 325                 }
 326         }
 327
 328         private static void releaseMemory() {
 329                 ByteWindow<?> e = lruTail;
 330                 while (isOverLimit() && e != null) {
 331                         final ByteWindow<?> p = e.lruPrev;
 332                         clear(e);
 333                         e = p;
 334                 }
 335         }
 336
 337         private static boolean isOverLimit() {
 338                 return openByteCount > maxByteCount || openFileCount > maxFileCount;
 339         }
 340
 341         /**
 342          * Remove all windows associated with a specific provider.
 343          * <p>
 344          * Providers should invoke this method as part of their cleanup/close
 345          * routines, ensuring that the window cache releases all windows that cannot
 346          * ever be requested again.
 347          * </p>
 348          *
 349          * @param wp
 350          *            the window provider whose windows should be removed from the
 351          *            cache.
 352          */
 353         public static synchronized final void purge(final PackFile wp) {
 354                 for (ByteWindow e : cache) {
 355                         for (; e != null; e = e.chainNext) {
 356                                 if (e.provider == wp)
 357                                         clear(e);
 358                         }
 359                 }
 360                 runClearedWindowQueue();
 361         }
 362
 363         private static void runClearedWindowQueue() {
 364                 ByteWindow<?> e;
 365                 while ((e = (ByteWindow) clearedWindowQueue.poll()) != null) {
 366                         unlinkSize(e);
 367                         unlinkLRU(e);
 368                         unlinkCache(e);
 369                         e.chainNext = null;
 370                         e.lruNext = null;
 371                         e.lruPrev = null;
 372                 }
 373         }
 374
 375         private static void clear(final ByteWindow<?> e) {
 376                 unlinkSize(e);
 377                 e.clear();
 378                 e.enqueue();
 379         }
 380
 381         private static void unlinkSize(final ByteWindow<?> e) {
 382                 if (e.sizeActive) {
 383                         if (--e.provider.openCount == 0) {
 384                                 openFileCount--;
 385                                 e.provider.cacheClose();
 386                         }
 387                         openByteCount -= e.size;
 388                         e.sizeActive = false;
 389                 }
 390         }
 391
 392         private static void unlinkCache(final ByteWindow dead) {
 393                 final int idx = hash(dead.provider, dead.id);
 394                 ByteWindow<?> e = cache[idx], p = null, n;
 395                 for (; e != null; p = e, e = n) {
 396                         n = e.chainNext;
 397                         if (e == dead) {
 398                                 if (p == null)
 399                                         cache[idx] = n;
 400                                 else
 401                                         p.chainNext = n;
 402                                 break;
 403                         }
 404                 }
 405         }
 406
 407         private static void unlinkLRU(final ByteWindow e) {
 408                 final ByteWindow<?> prev = e.lruPrev;
 409                 final ByteWindow<?> next = e.lruNext;
 410
 411                 if (prev != null)
 412                         prev.lruNext = next;
 413                 else
 414                         lruHead = next;
 415
 416                 if (next != null)
 417                         next.lruPrev = prev;
 418                 else
 419                         lruTail = prev;
 420         }
 421
 422         private static void insertLRU(final ByteWindow<?> e) {
 423                 final ByteWindow h = lruHead;
 424                 e.lruPrev = null;
 425                 e.lruNext = h;
 426                 if (h != null)
 427                         h.lruPrev = e;
 428                 else
 429                         lruTail = e;
 430                 lruHead = e;
 431         }
 432
 433         private static int hash(final PackFile wp, final int id) {
 434                 // wp.hash was already "stirred up" a bit by * 31 when
 435                 // it was created. Its reasonable to just add here.
 436                 //
 437                 return ((wp.hash + id) >>> 1) % cache.length;
 438         }
 439
 440         private static int windowSize(final PackFile file, final int id) {
 441                 final long len = file.length;
 442                 final long pos = id << windowSizeShift;
 443                 return len < pos + windowSize ? (int) (len - pos) : windowSize;
 444         }
 445
 446         private WindowCache() {
 447                 throw new UnsupportedOperationException();
 448         }
 449 }