source/ubiqx/ubi_Cache.c

   1 /* ========================================================================== **
   2  *                                 ubi_Cache.c
   3  *
   4  *  Copyright (C) 1997 by Christopher R. Hertel
   5  *
   6  *  Email: crh@ubiqx.mn.org
   7  * -------------------------------------------------------------------------- **
   8  *
   9  *  This module implements a generic cache.
  10  *
  11  * -------------------------------------------------------------------------- **
  12  *
  13  *  This library is free software; you can redistribute it and/or
  14  *  modify it under the terms of the GNU Library General Public
  15  *  License as published by the Free Software Foundation; either
  16  *  version 2 of the License, or (at your option) any later version.
  17  *
  18  *  This library is distributed in the hope that it will be useful,
  19  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21  *  Library General Public License for more details.
  22  *
  23  *  You should have received a copy of the GNU Library General Public
  24  *  License along with this library; if not, write to the Free
  25  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  26  *
  27  * -------------------------------------------------------------------------- **
  28  *
  29  *  This module uses a splay tree to implement a simple cache.  The cache
  30  *  module adds a thin layer of functionality to the splay tree.  In
  31  *  particular:
  32  *
  33  *    - The tree (cache) may be limited in size by the number of
  34  *      entries permitted or the amount of memory used.  When either
  35  *      limit is exceeded cache entries are removed until the cache
  36  *      conforms.
  37  *    - Some statistical information is kept so that an approximate
  38  *      "hit ratio" can be calculated.
  39  *    - There are several functions available that provide access to
  40  *      and management of cache size limits, hit ratio, and tree
  41  *      trimming.
  42  *
  43  *  The splay tree is used because recently accessed items tend toward the
  44  *  top of the tree and less recently accessed items tend toward the bottom.
  45  *  This makes it easy to purge less recently used items should the cache
  46  *  exceed its limits.
  47  *
  48  *  To use this module, you will need to supply a comparison function of
  49  *  type ubi_trCompFunc and a node-freeing function of type
  50  *  ubi_trKillNodeTrn.  See ubi_BinTree.h for more information on
  51  *  these.  (This is all basic ubiqx tree management stuff.)
  52  *
  53  *  Notes:
  54  *
  55  *  - Cache performance will start to suffer dramatically if the
  56  *    cache becomes large enough to force the OS to start swapping
  57  *    memory to disk.  This is because the nodes of the underlying tree
  58  *    will be scattered across memory in an order that is completely
  59  *    unrelated to their traversal order.  As more and more of the
  60  *    cache is placed into swap space, more and more swaps will be
  61  *    required for a simple traversal (...and then there's the splay
  62  *    operation).
  63  *
  64  *    In one simple test under Linux, the load and dump of a cache of
  65  *    400,000 entries took only 1min, 40sec of real time.  The same
  66  *    test with 450,000 records took 2 *hours* and eight minutes.
  67  *
  68  *  - In an effort to save memory, I considered using an unsigned
  69  *    short to save the per-entry entry size.  I would have tucked this
  70  *    value into some unused space in the tree node structure.  On
  71  *    32-bit word aligned systems this would have saved an additional
  72  *    four bytes per entry.  I may revisit this issue, but for now I've
  73  *    decided against it.
  74  *
  75  *    Using an unsigned short would limit the size of an entry to 64K
  76  *    bytes.  That's probably more than enough for most applications.
  77  *    The key word in that last sentence, however, is "probably".  I
  78  *    really dislike imposing such limits on things.
  79  *
  80  *  - Each entry keeps track of the amount of memory it used and the
  81  *    cache header keeps the total.  This information is provided via
  82  *    the EntrySize parameter in ubi_cachePut(), so it is up to you to
  83  *    make sure that the numbers are accurate.  (The numbers don't even
  84  *    have to represent bytes used.)
  85  *
  86  *    As you consider this, note that the strdup() function--as an
  87  *    example--will call malloc().  The latter generally allocates a
  88  *    multiple of the system word size, which may be more than the
  89  *    number of bytes needed to store the string.
  90  *
  91  * -------------------------------------------------------------------------- **
  92  *
  93  *  Log: ubi_Cache.c,v
  94  *  Revision 0.3  1998/06/03 18:00:15  crh
  95  *  Further fiddling with sys_include.h, which is no longer explicitly
  96  *  included by this module since it is inherited from ubi_BinTree.h.
  97  *
  98  *  Revision 0.2  1998/06/02 01:36:18  crh
  99  *  Changed include name from ubi_null.h to sys_include.h to make it
 100  *  more generic.
 101  *
 102  *  Revision 0.1  1998/05/20 04:36:02  crh
 103  *  The C file now includes ubi_null.h.  See ubi_null.h for more info.
 104  *
 105  *  Revision 0.0  1997/12/18 06:24:33  crh
 106  *  Initial Revision.
 107  *
 108  * ========================================================================== **
 109  */
 110
 111 #include "ubi_Cache.h"    /* Header for *this* module. */
 112
 113 /* -------------------------------------------------------------------------- **
 114  * Static data...
 115  */
 116
 117 /*  commented out until I make use of it...
 118 static char ModuleID[] =
 119 "ubi_Cache\n\
 120 \tRevision: 0.3 \n\
 121 \tDate: 1998/06/03 18:00:15 \n\
 122 \tAuthor: crh \n";
 123 */
 124
 125 /* -------------------------------------------------------------------------- **
 126  * Internal functions...
 127  */
 128
 129 static void free_entry( ubi_cacheRootPtr CachePtr, ubi_cacheEntryPtr EntryPtr )
 130   /* ------------------------------------------------------------------------ **
 131    * Free a ubi_cacheEntry, and adjust the mem_used counter accordingly.
 132    *
 133    *  Input:  CachePtr  - A pointer to the cache from which the entry has
 134    *                      been removed.
 135    *          EntryPtr  - A pointer to the already removed entry.
 136    *
 137    *  Output: none.
 138    *
 139    *  Notes:  The entry must be removed from the cache *before* this function
 140    *          is called!!!!
 141    * ------------------------------------------------------------------------ **
 142    */
 143   {
 144   CachePtr->mem_used -= EntryPtr->entry_size;
 145   (*CachePtr->free_func)( (void *)EntryPtr );
 146   } /* free_entry */
 147
 148 static void cachetrim( ubi_cacheRootPtr crptr )
 149   /* ------------------------------------------------------------------------ **
 150    * Remove entries from the cache until the number of entries and the amount
 151    * of memory used are *both* below or at the maximum.
 152    *
 153    *  Input:  crptr - pointer to the cache to be trimmed.
 154    *
 155    *  Output: None.
 156    *
 157    * ------------------------------------------------------------------------ **
 158    */
 159   {
 160   while( ( crptr->max_entries && (crptr->max_entries < crptr->root.count) )
 161       || ( crptr->max_memory  && (crptr->max_memory  < crptr->mem_used)   ) )
 162     {
 163     if( !ubi_cacheReduce( crptr, 1 ) )
 164       return;
 165     }
 166   } /* cachetrim */
 167
 168
 169 /* -------------------------------------------------------------------------- **
 170  * Exported functions...
 171  */
 172
 173 ubi_cacheRootPtr ubi_cacheInit( ubi_cacheRootPtr  CachePtr,
 174                                 ubi_trCompFunc    CompFunc,
 175                                 ubi_trKillNodeRtn FreeFunc,
 176                                 unsigned long     MaxEntries,
 177                                 unsigned long     MaxMemory )
 178   /* ------------------------------------------------------------------------ **
 179    * Initialize a cache header structure.
 180    *
 181    *  Input:  CachePtr    - A pointer to a ubi_cacheRoot structure that is
 182    *                        to be initialized.
 183    *          CompFunc    - A pointer to the function that will be called
 184    *                        to compare two cache values.  See the module
 185    *                        comments, above, for more information.
 186    *          FreeFunc    - A pointer to a function that will be called
 187    *                        to free a cache entry.  If you allocated
 188    *                        the cache entry using malloc(), then this
 189    *                        will likely be free().  If you are allocating
 190    *                        cache entries from a free list, then this will
 191    *                        likely be a function that returns memory to the
 192    *                        free list, etc.
 193    *          MaxEntries  - The maximum number of entries that will be
 194    *                        allowed to exist in the cache.  If this limit
 195    *                        is exceeded, then existing entries will be
 196    *                        removed from the cache.  A value of zero
 197    *                        indicates that there is no limit on the number
 198    *                        of cache entries.  See ubi_cachePut().
 199    *          MaxMemory   - The maximum amount of memory, in bytes, to be
 200    *                        allocated to the cache (excluding the cache
 201    *                        header).  If this is exceeded, existing entries
 202    *                        in the cache will be removed until enough memory
 203    *                        has been freed to meet the condition.  See
 204    *                        ubi_cachePut().
 205    *
 206    *  Output: A pointer to the initialized cache (i.e., the same as CachePtr).
 207    *
 208    *  Notes:  Both MaxEntries and MaxMemory may be changed after the cache
 209    *          has been created.  See
 210    *            ubi_cacheSetMaxEntries()
 211    *            ubi_cacheSetMaxMemory()
 212    *            ubi_cacheGetMaxEntries()
 213    *            ubi_cacheGetMaxMemory()    (the latter two are macros).
 214    *
 215    *        - Memory is allocated in multiples of the word size.  The
 216    *          return value of the strlen() function does not reflect
 217    *          this; it will allways be less than or equal to the amount
 218    *          of memory actually allocated.  Keep this in mind when
 219    *          choosing a value for MaxMemory.
 220    *
 221    * ------------------------------------------------------------------------ **
 222    */
 223   {
 224   if( CachePtr )
 225     {
 226     (void)ubi_trInitTree( CachePtr, CompFunc, ubi_trOVERWRITE );
 227     CachePtr->free_func   = FreeFunc;
 228     CachePtr->max_entries = MaxEntries;
 229     CachePtr->max_memory  = MaxMemory;
 230     CachePtr->mem_used    = 0;
 231     CachePtr->cache_hits  = 0;
 232     CachePtr->cache_trys  = 0;
 233     }
 234   return( CachePtr );
 235   } /* ubi_cacheInit */
 236
 237 ubi_cacheRootPtr ubi_cacheClear( ubi_cacheRootPtr CachePtr )
 238   /* ------------------------------------------------------------------------ **
 239    * Remove and free all entries in an existing cache.
 240    *
 241    *  Input:  CachePtr  - A pointer to the cache that is to be cleared.
 242    *
 243    *  Output: A pointer to the cache header (i.e., the same as CachePtr).
 244    *          This function re-initializes the cache header.
 245    *
 246    * ------------------------------------------------------------------------ **
 247    */
 248   {
 249   if( CachePtr )
 250     {
 251     (void)ubi_trKillTree( CachePtr, CachePtr->free_func );
 252     CachePtr->mem_used    = 0;
 253     CachePtr->cache_hits  = 0;
 254     CachePtr->cache_trys  = 0;
 255     }
 256   return( CachePtr );
 257   } /* ubi_cacheClear */
 258
 259 void ubi_cachePut( ubi_cacheRootPtr  CachePtr,
 260                    unsigned long     EntrySize,
 261                    ubi_cacheEntryPtr EntryPtr,
 262                    ubi_trItemPtr     Key )
 263   /* ------------------------------------------------------------------------ **
 264    * Add an entry to the cache.
 265    *
 266    *  Input:  CachePtr  - A pointer to the cache into which the entry
 267    *                      will be added.
 268    *          EntrySize - The size, in bytes, of the memory block indicated
 269    *                      by EntryPtr.  This will be copied into the
 270    *                      EntryPtr->entry_size field.
 271    *          EntryPtr  - A pointer to a memory block that begins with a
 272    *                      ubi_cacheEntry structure.  The entry structure
 273    *                      should be followed immediately by the data to be
 274    *                      cached (even if that is a pointer to yet more data).
 275    *          Key       - Pointer used to identify the lookup key within the
 276    *                      Entry.
 277    *
 278    *  Output: None.
 279    *
 280    *  Notes:  After adding the new node, the cache is "trimmed".  This
 281    *          removes extra nodes if the tree has exceeded it's memory or
 282    *          entry count limits.  It is unlikely that the newly added node
 283    *          will be purged from the cache (assuming a reasonably large
 284    *          cache), since new nodes in a splay tree (which is what this
 285    *          module was designed to use) are moved to the top of the tree
 286    *          and the cache purge process removes nodes from the bottom of
 287    *          the tree.
 288    *        - The underlying splay tree is opened in OVERWRITE mode.  If
 289    *          the input key matches an existing key, the existing entry will
 290    *          be politely removed from the tree and freed.
 291    *        - Memory is allocated in multiples of the word size.  The
 292    *          return value of the strlen() function does not reflect
 293    *          this; it will allways be less than or equal to the amount
 294    *          of memory actually allocated.
 295    *
 296    * ------------------------------------------------------------------------ **
 297    */
 298   {
 299   ubi_trNodePtr OldNode;
 300
 301   EntryPtr->entry_size = EntrySize;
 302   CachePtr->mem_used  += EntrySize;
 303   (void)ubi_trInsert( CachePtr, EntryPtr, Key, &OldNode );
 304   if( OldNode )
 305     free_entry( CachePtr, (ubi_cacheEntryPtr)OldNode );
 306
 307   cachetrim( CachePtr );
 308   } /* ubi_cachePut */
 309
 310 ubi_cacheEntryPtr ubi_cacheGet( ubi_cacheRootPtr CachePtr,
 311                                 ubi_trItemPtr    FindMe )
 312   /* ------------------------------------------------------------------------ **
 313    * Attempt to retrieve an entry from the cache.
 314    *
 315    *  Input:  CachePtr  - A ponter to the cache that is to be searched.
 316    *          FindMe    - A ubi_trItemPtr that indicates the key for which
 317    *                      to search.
 318    *
 319    *  Output: A pointer to the cache entry that was found, or NULL if no
 320    *          matching entry was found.
 321    *
 322    *  Notes:  This function also updates the hit ratio counters.
 323    *          The counters are unsigned short.  If the number of cache tries
 324    *          reaches 32768, then both the number of tries and the number of
 325    *          hits are divided by two.  This prevents the counters from
 326    *          overflowing.  See the comments in ubi_cacheHitRatio() for
 327    *          additional notes.
 328    *
 329    * ------------------------------------------------------------------------ **
 330    */
 331   {
 332   ubi_trNodePtr FoundPtr;
 333
 334   FoundPtr = ubi_trFind( CachePtr, FindMe );
 335
 336   if( FoundPtr )
 337     CachePtr->cache_hits++;
 338   CachePtr->cache_trys++;
 339
 340   if( CachePtr->cache_trys & 0x8000 )
 341     {
 342     CachePtr->cache_hits = CachePtr->cache_hits / 2;
 343     CachePtr->cache_trys = CachePtr->cache_trys / 2;
 344     }
 345
 346   return( (ubi_cacheEntryPtr)FoundPtr );
 347   } /* ubi_cacheGet */
 348
 349 ubi_trBool ubi_cacheDelete( ubi_cacheRootPtr CachePtr, ubi_trItemPtr DeleteMe )
 350   /* ------------------------------------------------------------------------ **
 351    * Find and delete the specified cache entry.
 352    *
 353    *  Input:  CachePtr  - A pointer to the cache.
 354    *          DeleteMe  - The key of the entry to be deleted.
 355    *
 356    *  Output: TRUE if the entry was found & freed, else FALSE.
 357    *
 358    * ------------------------------------------------------------------------ **
 359    */
 360   {
 361   ubi_trNodePtr FoundPtr;
 362
 363   FoundPtr = ubi_trFind( CachePtr, DeleteMe );
 364   if( FoundPtr )
 365     {
 366     (void)ubi_trRemove( CachePtr, FoundPtr );
 367     free_entry( CachePtr, (ubi_cacheEntryPtr)FoundPtr );
 368     return( ubi_trTRUE );
 369     }
 370   return( ubi_trFALSE );
 371   } /* ubi_cacheDelete */
 372
 373 ubi_trBool ubi_cacheReduce( ubi_cacheRootPtr CachePtr, unsigned long count )
 374   /* ------------------------------------------------------------------------ **
 375    * Remove <count> entries from the bottom of the cache.
 376    *
 377    *  Input:  CachePtr  - A pointer to the cache which is to be reduced in
 378    *                      size.
 379    *          count     - The number of entries to remove.
 380    *
 381    *  Output: The function will return TRUE if <count> entries were removed,
 382    *          else FALSE.  A return value of FALSE should indicate that
 383    *          there were less than <count> entries in the cache, and that the
 384    *          cache is now empty.
 385    *
 386    *  Notes:  This function forces a reduction in the number of cache entries
 387    *          without requiring that the MaxMemory or MaxEntries values be
 388    *          changed.
 389    *
 390    * ------------------------------------------------------------------------ **
 391    */
 392   {
 393   ubi_trNodePtr NodePtr;
 394
 395   while( count )
 396     {
 397     NodePtr = ubi_trLeafNode( CachePtr->root.root );
 398     if( NULL == NodePtr )
 399       return( ubi_trFALSE );
 400     else
 401       {
 402       (void)ubi_trRemove( CachePtr, NodePtr );
 403       free_entry( CachePtr, (ubi_cacheEntryPtr)NodePtr );
 404       }
 405     count--;
 406     }
 407   return( ubi_trTRUE );
 408   } /* ubi_cacheReduce */
 409
 410 unsigned long ubi_cacheSetMaxEntries( ubi_cacheRootPtr CachePtr,
 411                                       unsigned long    NewSize )
 412   /* ------------------------------------------------------------------------ **
 413    * Change the maximum number of entries allowed to exist in the cache.
 414    *
 415    *  Input:  CachePtr  - A pointer to the cache to be modified.
 416    *          NewSize   - The new maximum number of cache entries.
 417    *
 418    *  Output: The maximum number of entries previously allowed to exist in
 419    *          the cache.
 420    *
 421    *  Notes:  If the new size is less than the old size, this function will
 422    *          trim the cache (remove excess entries).
 423    *        - A value of zero indicates an unlimited number of entries.
 424    *
 425    * ------------------------------------------------------------------------ **
 426    */
 427   {
 428   unsigned long oldsize = CachePtr->max_entries;      /* Save the old value.  */
 429
 430   CachePtr->max_entries = NewSize;                    /* Apply the new value. */
 431   if( (NewSize < oldsize) || (NewSize && !oldsize) )  /* If size is smaller,  */
 432     cachetrim( CachePtr );                            /*   remove excess.     */
 433   return( oldsize );
 434   } /* ubi_cacheSetMaxEntries */
 435
 436 unsigned long ubi_cacheSetMaxMemory( ubi_cacheRootPtr CachePtr,
 437                                      unsigned long    NewSize )
 438   /* ------------------------------------------------------------------------ **
 439    * Change the maximum amount of memory to be used for storing cache
 440    * entries.
 441    *
 442    *  Input:  CachePtr  - A pointer to the cache to be modified.
 443    *          NewSize   - The new cache memory size.
 444    *
 445    *  Output: The previous maximum memory size.
 446    *
 447    *  Notes:  If the new size is less than the old size, this function will
 448    *          trim the cache (remove excess entries).
 449    *        - A value of zero indicates that the cache has no memory limit.
 450    *
 451    * ------------------------------------------------------------------------ **
 452    */
 453   {
 454   unsigned long oldsize = CachePtr->max_memory;       /* Save the old value.  */
 455
 456   CachePtr->max_memory = NewSize;                     /* Apply the new value. */
 457   if( (NewSize < oldsize) || (NewSize && !oldsize) )  /* If size is smaller,  */
 458     cachetrim( CachePtr );                            /*   remove excess.     */
 459   return( oldsize );
 460   } /* ubi_cacheSetMaxMemory */
 461
 462 int ubi_cacheHitRatio( ubi_cacheRootPtr CachePtr )
 463   /* ------------------------------------------------------------------------ **
 464    * Returns a value that is 10,000 times the slightly weighted average hit
 465    * ratio for the cache.
 466    *
 467    *  Input:  CachePtr  - Pointer to the cache to be queried.
 468    *
 469    *  Output: An integer that is 10,000 times the number of successful
 470    *          cache hits divided by the number of cache lookups, or:
 471    *            (10000 * hits) / trys
 472    *          You can easily convert this to a float, or do something
 473    *          like this (where i is the return value of this function):
 474    *
 475    *            printf( "Hit rate   : %d.%02d%%\n", (i/100), (i%100) );
 476    *
 477    *  Notes:  I say "slightly-weighted", because the numerator and
 478    *          denominator are both accumulated in locations of type
 479    *          'unsigned short'.  If the number of cache trys becomes
 480    *          large enough, both are divided  by two.  (See function
 481    *          ubi_cacheGet().)
 482    *          Dividing both numerator and denominator by two does not
 483    *          change the ratio (much...it is an integer divide), but it
 484    *          does mean that subsequent increments to either counter will
 485    *          have twice as much significance as previous ones.
 486    *
 487    *        - The value returned by this function will be in the range
 488    *          [0..10000] because ( 0 <= cache_hits <= cache_trys ) will
 489    *          always be true.
 490    *
 491    * ------------------------------------------------------------------------ **
 492    */
 493   {
 494   int tmp = 0;
 495
 496   if( CachePtr->cache_trys )
 497     tmp = (int)( (10000 * (long)(CachePtr->cache_hits) )
 498                         / (long)(CachePtr->cache_trys) );
 499   return( tmp );
 500   } /* ubi_cacheHitRatio */
 501
 502 /* -------------------------------------------------------------------------- */