bsd/hfs/hfscommon/Misc/GenericMRUCache.c

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * The contents of this file constitute Original Code as defined in and
   7  * are subject to the Apple Public Source License Version 1.1 (the
   8  * "License").  You may not use this file except in compliance with the
   9  * License.  Please obtain a copy of the License at
  10  * http://www.apple.com/publicsource and read it before using this file.
  11  *
  12  * This Original Code and all software distributed under the License are
  13  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  17  * License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22 /*
  23         File:           GenericMRUCache.c
  24
  25         Contains:       Contains cache accessor routines based on MRU / LRU ordering.
  26
  27         Version:        HFS+ 1.0
  28
  29         Copyright:      © 1997-1998 by Apple Computer, Inc., all rights reserved.
  30
  31         File Ownership:
  32
  33                 DRI:                            Deric Horn
  34
  35                 Other Contact:          Don Brady
  36
  37                 Technology:                     HFS+
  38
  39         Writers:
  40
  41                 (DSH)   Deric Horn
  42
  43         Change History (most recent first):
  44
  45            <CS2>         1/29/98        DSH             Add TrashMRUCache for TrashAllFSCaches API support.
  46            <CS1>         7/25/97        DSH             first checked in
  47 */
  48
  49 #include "../../hfs_macos_defs.h"
  50 #include "../headers/FileMgrInternal.h"
  51
  52 enum {
  53         //      error codes
  54         errNotInCache                   = -123,
  55         errInvalidKey                   = -124
  56 };
  57
  58
  59 struct CacheBlock {
  60         struct CacheBlock               *nextMRU;                                       //      next node in MRU order
  61         struct CacheBlock               *nextLRU;                                       //      next node in LRU order
  62         UInt32                                  flags;                                          //      status flags
  63         UInt32                                  key;                                            //      comparrison Key
  64         char                                    buffer[1];                                      //      user defineable data
  65 };
  66 typedef struct CacheBlock CacheBlock;
  67
  68 struct CacheGlobals {
  69         UInt32                                  cacheBlockSize;                         //      Size of CacheBlock structure including the buffer
  70         UInt32                                  cacheBufferSize;                        //      Size of cache buffer
  71         UInt32                                  numCacheBlocks;                         //      Number of blocks in cache
  72         CacheBlock                              *mru;
  73         CacheBlock                              *lru;
  74 };
  75 typedef struct CacheGlobals CacheGlobals;
  76
  77
  78 //
  79 //      Internal routines
  80 //
  81 static void InsertAsMRU ( CacheGlobals *cacheGlobals, CacheBlock *cacheBlock );
  82 static void InsertAsLRU ( CacheGlobals *cacheGlobals, CacheBlock *cacheBlock );
  83
  84
  85 //
  86 //      Diagram of Cache structures
  87 //
  88 //      _______        ________        ________            ________
  89 //      |data |        | buff |        | buff |            | buff |
  90 //      | mru |----->  | nMRU |----->  | nMRU |--> °°° --->| nMRU |-->\80
  91 //      | lru |-\   \80<-| nLRU |  <-----| nLRU |<-- °°° <---| nLRU |
  92 //      -------  \     --------        --------            --------
  93 //            \                                           |
  94 //                 \-----------------------------------------/
  95 //      CacheGlobals                                    CacheBlock's
  96
  97
  98
  99
 100 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
 101 //      Routine:        InitMRUCache
 102 //
 103 //      Function:       Allocates cache, and initializes all the cache structures.
 104 //
 105 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
 106 OSErr   InitMRUCache( UInt32 bufferSize, UInt32 numCacheBlocks, Ptr *cachePtr )
 107 {
 108         OSErr                   err;
 109         short                   i, lastBuffer;
 110         CacheBlock              *cacheBlock;
 111         CacheGlobals    *cacheGlobals;
 112         UInt32                  cacheBlockSize  = offsetof( CacheBlock, buffer ) + bufferSize;
 113
 114         cacheGlobals    = (CacheGlobals *) NewPtrSysClear( sizeof( CacheGlobals ) +  ( numCacheBlocks * cacheBlockSize ) );
 115         err = MemError();
 116
 117         if ( err == noErr )
 118         {
 119                 cacheGlobals->cacheBlockSize    = cacheBlockSize;
 120                 cacheGlobals->cacheBufferSize   = bufferSize;
 121                 cacheGlobals->numCacheBlocks    = numCacheBlocks;
 122
 123                 lastBuffer = numCacheBlocks - 1;                                                        //      last buffer number, since they start at 0
 124
 125                 //      Initialize the LRU order for the cache
 126                 cacheGlobals->lru = (CacheBlock *)((Ptr)cacheGlobals + sizeof( CacheGlobals ) + (lastBuffer * cacheBlockSize));
 127                 cacheGlobals->lru->nextMRU = nil;
 128
 129                 //      Initialize the MRU order for the cache
 130                 cacheGlobals->mru = (CacheBlock *)( (Ptr)cacheGlobals + sizeof( CacheGlobals ) );       //      points to 1st cache block
 131                 cacheGlobals->mru->nextLRU = nil;
 132
 133                 //      Traverse nodes, setting initial mru, lru, and default values
 134                 for ( i=0, cacheBlock=cacheGlobals->mru; i<lastBuffer ; i++ )
 135                 {
 136                         cacheBlock->key         = kInvalidMRUCacheKey;                          //      initialize key to illegal while we're at it
 137                         cacheBlock->flags       = 0;
 138                         cacheBlock->nextMRU     = (CacheBlock *) ( (Ptr)cacheBlock + cacheBlockSize );
 139                         cacheBlock                      = cacheBlock->nextMRU;
 140                 }
 141                 //      And the last Block
 142                 cacheGlobals->lru->key  = kInvalidMRUCacheKey;
 143                 cacheBlock->flags               = 0;
 144
 145                 for ( i=0, cacheBlock=cacheGlobals->lru; i<lastBuffer ; i++ )
 146                 {
 147                         cacheBlock->nextLRU = (CacheBlock *) ( (Ptr)cacheBlock - cacheBlockSize );
 148                         cacheBlock = cacheBlock->nextLRU;
 149                 }
 150
 151                 *cachePtr       = (Ptr) cacheGlobals;                                                   //      return cacheGlobals to user
 152         }
 153         else
 154         {
 155                 *cachePtr       = nil;
 156         }
 157
 158         return( err );
 159 }
 160
 161
 162 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
 163 //      Routine:        DisposeMRUCache
 164 //
 165 //      Function:       Dispose of all memory allocated by the cache
 166 //
 167 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
 168 OSErr   DisposeMRUCache( Ptr cachePtr )
 169 {
 170         OSErr           err;
 171
 172         DisposePtr( cachePtr );
 173         err = MemError();
 174
 175         return( err );
 176 }
 177
 178
 179 //ÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑ
 180 //      Routine:        TrashMRUCache
 181 //
 182 //      Function:       Invalidates all entries in the MRU cache pointed to by cachePtr.
 183 //
 184 //ÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑ
 185 void    TrashMRUCache( Ptr cachePtr )
 186 {
 187         CacheGlobals    *cacheGlobals   = (CacheGlobals *) cachePtr;
 188         CacheBlock              *cacheBlock;
 189
 190         for ( cacheBlock = cacheGlobals->mru ; cacheBlock != nil ; cacheBlock = cacheBlock->nextMRU )
 191         {
 192                 cacheBlock->flags       = 0;                                    //      Clear the flags
 193                 cacheBlock->key         = kInvalidMRUCacheKey;  //      Make it an illegal value
 194         }
 195 }
 196
 197
 198 //ÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑ
 199 //      Routine:        GetMRUCacheBlock
 200 //
 201 //      Function:       Return buffer associated with the passed in key.
 202 //                              Search the cache in MRU order
 203 //                              \80 We can insert the found cache block at the head of mru automatically
 204 //
 205 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
 206 OSErr   GetMRUCacheBlock( UInt32 key, Ptr cachePtr, Ptr *buffer )
 207 {
 208         CacheBlock              *cacheBlock;
 209         CacheGlobals    *cacheGlobals   = (CacheGlobals *) cachePtr;
 210
 211 //      if ( key == kInvalidMRUCacheKey )               //      removed for performance
 212 //              return( errInvalidKey );
 213
 214         for ( cacheBlock = cacheGlobals->mru ; (cacheBlock != nil) && (cacheBlock->key != kInvalidMRUCacheKey) ; cacheBlock = cacheBlock->nextMRU )
 215         {
 216                 if ( cacheBlock->key == key )
 217                 {
 218                         InsertAsMRU( cacheGlobals, cacheBlock );
 219                         *buffer = (Ptr) cacheBlock->buffer;
 220                         return( noErr );
 221                 }
 222         }
 223
 224         return( errNotInCache );
 225 }
 226
 227
 228
 229 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
 230 //      Routine:        InvalidateMRUCacheBlock
 231 //
 232 //      Function:       Place the cache block at the head of the lru queue and mark it invalid
 233 //
 234 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
 235 void    InvalidateMRUCacheBlock( Ptr cachePtr, Ptr buffer )
 236 {
 237         CacheGlobals    *cacheGlobals   = (CacheGlobals *) cachePtr;
 238         CacheBlock              *cacheBlock;
 239
 240         cacheBlock = (CacheBlock *) (buffer - offsetof( CacheBlock, buffer ));
 241         cacheBlock->flags       = 0;                                    //      Clear the flags
 242         cacheBlock->key         = kInvalidMRUCacheKey;  //      Make it an illegal value
 243         InsertAsLRU( cacheGlobals, cacheBlock );
 244 }
 245
 246
 247 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
 248 //      Routine:        InsertMRUCacheBlock
 249 //
 250 //      Function:       Place the CacheBlock associated with the passed in key at the
 251 //                              head of the mru queue and replace the buffer with the passed in buffer
 252 //
 253 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
 254 void    InsertMRUCacheBlock( Ptr cachePtr, UInt32 key, Ptr buffer )
 255 {
 256         CacheBlock              *cacheBlock = NULL;
 257         Ptr                             cacheBuffer;
 258         OSErr                   err;
 259         CacheGlobals    *cacheGlobals   = (CacheGlobals *) cachePtr;
 260         UInt32                  cacheBufferSize;
 261
 262         err = GetMRUCacheBlock( key, cachePtr, &cacheBuffer );
 263         if ( err == errNotInCache )
 264             cacheBlock = cacheGlobals->lru;
 265         else if ( err == noErr )
 266                 cacheBlock = (CacheBlock *) (cacheBuffer - offsetof( CacheBlock, buffer ));
 267
 268         cacheBufferSize = cacheGlobals->cacheBufferSize;
 269         if ( cacheBufferSize == sizeof(UInt32) )
 270                 *(UInt32*)cacheBlock->buffer = *(UInt32*)buffer;
 271         else
 272                 BlockMoveData( buffer, cacheBlock->buffer, cacheBufferSize );
 273         InsertAsMRU( cacheGlobals, cacheBlock );
 274
 275         cacheBlock->flags       = 0;
 276         cacheBlock->key         = key;
 277 }
 278
 279
 280
 281
 282 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
 283 //      Routine:        InsertMRUCacheBlock
 284 //
 285 //      Function:       Moves cache block to head of mru order in double linked list of cached blocks
 286 //
 287 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
 288 static void     InsertAsMRU     ( CacheGlobals *cacheGlobals, CacheBlock *cacheBlock )
 289 {
 290         CacheBlock      *swapBlock;
 291
 292         if ( cacheGlobals->mru != cacheBlock )                                  //      if it's not already the mru cacheBlock
 293         {
 294                 swapBlock = cacheGlobals->mru;                                          //      put it in the front of the double queue
 295                 cacheGlobals->mru = cacheBlock;
 296                 cacheBlock->nextLRU->nextMRU = cacheBlock->nextMRU;
 297                 if ( cacheBlock->nextMRU != nil )
 298                         cacheBlock->nextMRU->nextLRU = cacheBlock->nextLRU;
 299                 else
 300                         cacheGlobals->lru= cacheBlock->nextLRU;
 301                 cacheBlock->nextMRU     = swapBlock;
 302                 cacheBlock->nextLRU     = nil;
 303                 swapBlock->nextLRU      = cacheBlock;
 304         }
 305 }
 306
 307
 308 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
 309 //      Routine:        InsertMRUCacheBlock
 310 //
 311 //      Function:       Moves cache block to head of lru order in double linked list of cached blocks
 312 //
 313 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
 314 static void InsertAsLRU ( CacheGlobals *cacheGlobals, CacheBlock *cacheBlock )
 315 {
 316         CacheBlock      *swapBlock;
 317
 318         if ( cacheGlobals->lru != cacheBlock )
 319         {
 320                 swapBlock = cacheGlobals->lru;
 321                 cacheGlobals->lru = cacheBlock;
 322                 cacheBlock->nextMRU->nextLRU = cacheBlock->nextLRU;
 323                 if ( cacheBlock->nextLRU != nil )
 324                         cacheBlock->nextLRU->nextMRU = cacheBlock->nextMRU;
 325                 else
 326                         cacheGlobals->mru= cacheBlock->nextMRU;
 327                 cacheBlock->nextLRU     = swapBlock;
 328                 cacheBlock->nextMRU     = nil;
 329                 swapBlock->nextMRU      = cacheBlock;
 330         }
 331 }
 332
 333