bootx.tproj/fs.subproj/cache.c

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25 /*
  26  *  cache.c - A simple cache for file systems meta-data.
  27  *
  28  *  Copyright (c) 2000 - 2003 Apple Computer, Inc.
  29  *
  30  *  DRI: Josh de Cesare
  31  */
  32
  33 #include <sl.h>
  34 #include <fs.h>
  35
  36 struct CacheEntry {
  37   CICell    ih;
  38   long      time;
  39   long long offset;
  40 };
  41 typedef struct CacheEntry CacheEntry;
  42
  43 #define kCacheSize            (kFSCacheSize)
  44 #define kCacheMinBlockSize    (0x200)
  45 #define kCacheMaxBlockSize    (0x4000)
  46 #define kCacheMaxEntries      (kCacheSize / kCacheMinBlockSize)
  47
  48 static CICell     gCacheIH;
  49 static long       gCacheBlockSize;
  50 static long       gCacheNumEntries;
  51 static long       gCacheTime;
  52 static CacheEntry gCacheEntries[kCacheMaxEntries];
  53 static char       *gCacheBuffer = (char *)kFSCacheAddr;
  54
  55 unsigned long     gCacheHits;
  56 unsigned long     gCacheMisses;
  57 unsigned long     gCacheEvicts;
  58
  59 void CacheInit(CICell ih, long blockSize)
  60 {
  61   if ((blockSize < kCacheMinBlockSize) ||
  62       (blockSize >= kCacheMaxBlockSize))
  63     return;
  64
  65   gCacheBlockSize = blockSize;
  66   gCacheNumEntries = kCacheSize / gCacheBlockSize;
  67   gCacheTime = 0;
  68
  69   gCacheHits = 0;
  70   gCacheMisses = 0;
  71   gCacheEvicts = 0;
  72
  73   bzero(gCacheEntries, sizeof(gCacheEntries));
  74
  75   gCacheIH = ih;
  76 }
  77
  78
  79 long CacheRead(CICell ih, char *buffer, long long offset,
  80                long length, long cache)
  81 {
  82   long       cnt, oldestEntry, oldestTime, loadCache = 0;
  83   CacheEntry *entry;
  84
  85   // See if the data can be cached.
  86   if (cache && (gCacheIH == ih) && (length == gCacheBlockSize)) {
  87     // Look for the data in the cache.
  88     for (cnt = 0; cnt < gCacheNumEntries; cnt++) {
  89       entry = &gCacheEntries[cnt];
  90       if ((entry->ih == ih) && (entry->offset == offset)) {
  91         entry->time = ++gCacheTime;
  92         break;
  93       }
  94     }
  95
  96     // If the data was found copy it to the caller.
  97     if (cnt != gCacheNumEntries) {
  98       bcopy(gCacheBuffer + cnt * gCacheBlockSize, buffer, gCacheBlockSize);
  99       gCacheHits++;
 100       return gCacheBlockSize;
 101     }
 102
 103     // Could not find the data in the cache.
 104     loadCache = 1;
 105   }
 106
 107   // Read the data from the disk.
 108   Seek(ih, offset);
 109   Read(ih, (CICell)buffer, length);
 110   if (cache) gCacheMisses++;
 111
 112   // Put the data from the disk in the cache if needed.
 113   if (loadCache) {
 114     // Find a free entry.
 115     oldestTime = gCacheTime;
 116     for (cnt = 0; cnt < gCacheNumEntries; cnt++) {
 117       entry = &gCacheEntries[cnt];
 118
 119       // Found a free entry.
 120       if (entry->ih == 0) break;
 121
 122       if (entry->time < oldestTime) {
 123         oldestTime = entry->time;
 124         oldestEntry = cnt;
 125       }
 126     }
 127
 128     // If no free entry was found, use the oldest.
 129     if (cnt == gCacheNumEntries) {
 130       cnt = oldestEntry;
 131       gCacheEvicts++;
 132     }
 133
 134     // Copy the data from disk to the new entry.
 135     entry = &gCacheEntries[cnt];
 136     entry->ih = ih;
 137     entry->time = ++gCacheTime;
 138     entry->offset = offset;
 139     bcopy(buffer, gCacheBuffer + cnt * gCacheBlockSize, gCacheBlockSize);
 140   }
 141
 142   return length;
 143 }