boot-132.tar.gz

[apple/boot.git] / i386 / libsaio / cache.c

diff --git a/i386/libsaio/cache.c b/i386/libsaio/cache.c
index 6ead4d65b2e050c37e5256f3538e4dfb4f5aeaad..8b79dbc91930c2d0eca7cd0b6042ed31fd654b2f 100644 (file)
--- a/i386/libsaio/cache.c
+++ b/i386/libsaio/cache.c
@@ -1,94 +1,170 @@
 /*
 /*

- * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2003 Apple Computer, Inc. All rights reserved.

  *
  * @APPLE_LICENSE_HEADER_START@
  * 
  *
  * @APPLE_LICENSE_HEADER_START@
  * 

- * Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
- * Reserved.  This file contains Original Code and/or Modifications of
- * Original Code as defined in and that are subject to the Apple Public
- * Source License Version 1.1 (the "License").  You may not use this file
- * except in compliance with the License.  Please obtain a copy of the
- * License at http://www.apple.com/publicsource and read it before using
- * this file.
+ * The contents of this file constitute Original Code as defined in and
+ * are subject to the Apple Public Source License Version 2.0 (the
+ * "License").  You may not use this file except in compliance with the
+ * License.  Please obtain a copy of the License at
+ * http://www.apple.com/publicsource and read it before using this file.

  * 
  * 

- * The Original Code and all software distributed under the License are
+ * This Original Code and all software distributed under the License are

  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,

- * FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT.  Please see the
+ * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the

  * License for the specific language governing rights and limitations
  * under the License.
  * 
  * @APPLE_LICENSE_HEADER_END@
  */
  * License for the specific language governing rights and limitations
  * under the License.
  * 
  * @APPLE_LICENSE_HEADER_END@
  */

-/* cache */
+/*
+ *  cache.c - A simple cache for file systems meta-data.
+ *
+ *  Copyright (c) 2000 Apple Computer, Inc.
+ *
+ *  DRI: Josh de Cesare
+ */

 
 

-#include "cache.h"
-#include "libsa.h"
+#include <sl.h>
+// #include <fs.h>

 
 

-cache_t *cacheInit(
-    int nitems,
-    int item_size
-)
-{
-    cache_t *cp;
-    item_size += sizeof(item_t);
-    cp = (cache_t *)malloc(sizeof(cache_t) + nitems * item_size);
-    cp->nitems = nitems;
-    cp->item_size = item_size;
-    return cp;
-}
+struct CacheEntry {
+  CICell    ih;
+  long      time;
+  long long offset;
+};
+typedef struct CacheEntry CacheEntry;

 
 

-/*
- * Either find an item in the cache, or find where it should go.
- * Returns 1 if found, 0 if not found.
- * This function assumes that if you find an empty slot, you will use it;
- * therefore, empty slots returned are marked valid.
- */
-int cacheFind(
-    cache_t *cp,
-    int key1,
-    int key2,
-    char **ip
-)
+#define kCacheSize            (0x100000)
+#define kCacheMinBlockSize    (0x200)
+#define kCacheMaxBlockSize    (0x4000)
+#define kCacheMaxEntries      (kCacheSize / kCacheMinBlockSize)
+
+static CICell     gCacheIH;
+static long       gCacheBlockSize;
+static long       gCacheNumEntries;
+static long       gCacheTime;
+
+#ifdef __i386__
+static CacheEntry *gCacheEntries;
+static char       *gCacheBuffer;
+#else
+static CacheEntry gCacheEntries[kCacheMaxEntries];
+static char       gCacheBuffer[kCacheSize];
+#endif
+
+#if CACHE_STATS
+unsigned long     gCacheHits;
+unsigned long     gCacheMisses;
+unsigned long     gCacheEvicts;
+#endif
+
+void CacheInit( CICell ih, long blockSize )

 {
 {

-    item_t *iip, *min_p;
-    int i,j;
+#ifdef __i386__
+    if ((ih == gCacheIH) && (blockSize == gCacheBlockSize))
+        return;
+#endif
+
+    if ((blockSize  < kCacheMinBlockSize) ||
+        (blockSize >= kCacheMaxBlockSize))
+        return;
+
+    gCacheBlockSize = blockSize;
+    gCacheNumEntries = kCacheSize / gCacheBlockSize;
+    gCacheTime = 0;

     
     

-    for(i=j=0, iip = min_p = (item_t *)cp->storage; i < cp->nitems; i++) {
-       if (iip->referenced && (iip->key1 == key1) && (iip->key2 == key2)) {
-           *ip = iip->storage;
-           if (iip->referenced < 65535)
-               iip->referenced++;
-           return 1;
-       }
-       if (iip->referenced < min_p->referenced) {
-           min_p = iip;
-           j = i;
-       }
-       iip = (item_t *)((char *)iip + cp->item_size);
+#if CACHE_STATS
+    gCacheHits = 0;
+    gCacheMisses = 0;
+    gCacheEvicts = 0;
+#endif
+
+    gCacheIH = ih;
+
+#ifdef __i386__
+    if (!gCacheBuffer) gCacheBuffer = (char *) malloc(kCacheSize);
+    if (!gCacheEntries) gCacheEntries = (CacheEntry *) malloc(kCacheMaxEntries * sizeof(CacheEntry));
+    if ( !gCacheBuffer || !gCacheEntries )
+    {
+        gCacheIH = 0;  // invalidate cache
+        return;

     }
     }

-    *ip = min_p->storage;
-    min_p->referenced = 1;
-    min_p->key1 = key1;
-    min_p->key2 = key2;
-    return 0;
+#endif
+
+    bzero(gCacheEntries, kCacheMaxEntries * sizeof(CacheEntry));

 }
 
 }
 

-/*
- * Flush the cache.
- */
-void cacheFlush(
-    cache_t *cp
-)
+long CacheRead( CICell ih, char * buffer, long long offset,
+                   long length, long cache )

 {
 {

-    int i;
-    item_t *ip;
-    
-    if (cp == 0)
-       return;
-    for(i=0, ip = (item_t *)cp->storage; i < cp->nitems; i++) {
-       ip->referenced = 0;
-       ip = (item_t *)((char *)ip + cp->item_size);
+    long       cnt, oldestEntry = 0, oldestTime, loadCache = 0;
+    CacheEntry *entry;
+
+    // See if the data can be cached.
+    if (cache && (gCacheIH == ih) && (length == gCacheBlockSize)) {
+        // Look for the data in the cache.
+        for (cnt = 0; cnt < gCacheNumEntries; cnt++) {
+            entry = &gCacheEntries[cnt];
+            if ((entry->ih == ih) && (entry->offset == offset)) {
+                entry->time = ++gCacheTime;
+                break;
+            }
+        }
+
+        // If the data was found copy it to the caller.
+        if (cnt != gCacheNumEntries) {
+            bcopy(gCacheBuffer + cnt * gCacheBlockSize, buffer, gCacheBlockSize);
+#if CACHE_STATS
+            gCacheHits++;
+#endif
+            return gCacheBlockSize;
+        }
+
+        // Could not find the data in the cache.
+        loadCache = 1;

     }
     }

+
+    // Read the data from the disk.
+    Seek(ih, offset);
+    Read(ih, (long)buffer, length);
+#if CACHE_STATS
+    if (cache) gCacheMisses++;
+#endif
+
+    // Put the data from the disk in the cache if needed.
+    if (loadCache) {
+        // Find a free entry.
+        oldestTime = gCacheTime;
+        for (cnt = 0; cnt < gCacheNumEntries; cnt++) {
+            entry = &gCacheEntries[cnt];
+
+            // Found a free entry.
+            if (entry->ih == 0) break;
+        
+            if (entry->time < oldestTime) {
+                oldestTime = entry->time;
+                oldestEntry = cnt;
+            }
+        }
+
+        // If no free entry was found, use the oldest.
+        if (cnt == gCacheNumEntries) {
+            cnt = oldestEntry;
+#if CACHE_STATS
+            gCacheEvicts++;
+#endif
+        }
+
+        // Copy the data from disk to the new entry.
+        entry = &gCacheEntries[cnt];
+        entry->ih = ih;
+        entry->time = ++gCacheTime;
+        entry->offset = offset;
+        bcopy(buffer, gCacheBuffer + cnt * gCacheBlockSize, gCacheBlockSize);
+    }
+
+    return length;

 }
 }