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_trKillNodeRtn. 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.4 1999/09/22 03:42:24 crh 95 * Fixed a minor typo. 96 * 97 * Revision 0.3 1998/06/03 18:00:15 crh 98 * Further fiddling with sys_include.h, which is no longer explicitly 99 * included by this module since it is inherited from ubi_BinTree.h. 100 * 101 * Revision 0.2 1998/06/02 01:36:18 crh 102 * Changed include name from ubi_null.h to sys_include.h to make it 103 * more generic. 104 * 105 * Revision 0.1 1998/05/20 04:36:02 crh 106 * The C file now includes ubi_null.h. See ubi_null.h for more info. 107 * 108 * Revision 0.0 1997/12/18 06:24:33 crh 109 * Initial Revision. 110 * 111 * ========================================================================== ** 112 */ 113 114#include "ubi_Cache.h" /* Header for *this* module. */ 115 116/* -------------------------------------------------------------------------- ** 117 * Static data... 118 */ 119 120/* commented out until I make use of it... 121static char ModuleID[] = 122"ubi_Cache\n\ 123\tRevision: 0.4 \n\ 124\tDate: 1999/09/22 03:42:24 \n\ 125\tAuthor: crh \n"; 126*/ 127 128/* -------------------------------------------------------------------------- ** 129 * Internal functions... 130 */ 131 132static void free_entry( ubi_cacheRootPtr CachePtr, ubi_cacheEntryPtr EntryPtr ) 133 /* ------------------------------------------------------------------------ ** 134 * Free a ubi_cacheEntry, and adjust the mem_used counter accordingly. 135 * 136 * Input: CachePtr - A pointer to the cache from which the entry has 137 * been removed. 138 * EntryPtr - A pointer to the already removed entry. 139 * 140 * Output: none. 141 * 142 * Notes: The entry must be removed from the cache *before* this function 143 * is called!!!! 144 * ------------------------------------------------------------------------ ** 145 */ 146 { 147 CachePtr->mem_used -= EntryPtr->entry_size; 148 (*CachePtr->free_func)( (void *)EntryPtr ); 149 } /* free_entry */ 150 151static void cachetrim( ubi_cacheRootPtr crptr ) 152 /* ------------------------------------------------------------------------ ** 153 * Remove entries from the cache until the number of entries and the amount 154 * of memory used are *both* below or at the maximum. 155 * 156 * Input: crptr - pointer to the cache to be trimmed. 157 * 158 * Output: None. 159 * 160 * ------------------------------------------------------------------------ ** 161 */ 162 { 163 while( ( crptr->max_entries && (crptr->max_entries < crptr->root.count) ) 164 || ( crptr->max_memory && (crptr->max_memory < crptr->mem_used) ) ) 165 { 166 if( !ubi_cacheReduce( crptr, 1 ) ) 167 return; 168 } 169 } /* cachetrim */ 170 171 172/* -------------------------------------------------------------------------- ** 173 * Exported functions... 174 */ 175 176ubi_cacheRootPtr ubi_cacheInit( ubi_cacheRootPtr CachePtr, 177 ubi_trCompFunc CompFunc, 178 ubi_trKillNodeRtn FreeFunc, 179 unsigned long MaxEntries, 180 unsigned long MaxMemory ) 181 /* ------------------------------------------------------------------------ ** 182 * Initialize a cache header structure. 183 * 184 * Input: CachePtr - A pointer to a ubi_cacheRoot structure that is 185 * to be initialized. 186 * CompFunc - A pointer to the function that will be called 187 * to compare two cache values. See the module 188 * comments, above, for more information. 189 * FreeFunc - A pointer to a function that will be called 190 * to free a cache entry. If you allocated 191 * the cache entry using malloc(), then this 192 * will likely be free(). If you are allocating 193 * cache entries from a free list, then this will 194 * likely be a function that returns memory to the 195 * free list, etc. 196 * MaxEntries - The maximum number of entries that will be 197 * allowed to exist in the cache. If this limit 198 * is exceeded, then existing entries will be 199 * removed from the cache. A value of zero 200 * indicates that there is no limit on the number 201 * of cache entries. See ubi_cachePut(). 202 * MaxMemory - The maximum amount of memory, in bytes, to be 203 * allocated to the cache (excluding the cache 204 * header). If this is exceeded, existing entries 205 * in the cache will be removed until enough memory 206 * has been freed to meet the condition. See 207 * ubi_cachePut(). 208 * 209 * Output: A pointer to the initialized cache (i.e., the same as CachePtr). 210 * 211 * Notes: Both MaxEntries and MaxMemory may be changed after the cache 212 * has been created. See 213 * ubi_cacheSetMaxEntries() 214 * ubi_cacheSetMaxMemory() 215 * ubi_cacheGetMaxEntries() 216 * ubi_cacheGetMaxMemory() (the latter two are macros). 217 * 218 * - Memory is allocated in multiples of the word size. The 219 * return value of the strlen() function does not reflect 220 * this; it will allways be less than or equal to the amount 221 * of memory actually allocated. Keep this in mind when 222 * choosing a value for MaxMemory. 223 * 224 * ------------------------------------------------------------------------ ** 225 */ 226 { 227 if( CachePtr ) 228 { 229 (void)ubi_trInitTree( CachePtr, CompFunc, ubi_trOVERWRITE ); 230 CachePtr->free_func = FreeFunc; 231 CachePtr->max_entries = MaxEntries; 232 CachePtr->max_memory = MaxMemory; 233 CachePtr->mem_used = 0; 234 CachePtr->cache_hits = 0; 235 CachePtr->cache_trys = 0; 236 } 237 return( CachePtr ); 238 } /* ubi_cacheInit */ 239 240ubi_cacheRootPtr ubi_cacheClear( ubi_cacheRootPtr CachePtr ) 241 /* ------------------------------------------------------------------------ ** 242 * Remove and free all entries in an existing cache. 243 * 244 * Input: CachePtr - A pointer to the cache that is to be cleared. 245 * 246 * Output: A pointer to the cache header (i.e., the same as CachePtr). 247 * This function re-initializes the cache header. 248 * 249 * ------------------------------------------------------------------------ ** 250 */ 251 { 252 if( CachePtr ) 253 { 254 (void)ubi_trKillTree( CachePtr, CachePtr->free_func ); 255 CachePtr->mem_used = 0; 256 CachePtr->cache_hits = 0; 257 CachePtr->cache_trys = 0; 258 } 259 return( CachePtr ); 260 } /* ubi_cacheClear */ 261 262void ubi_cachePut( ubi_cacheRootPtr CachePtr, 263 unsigned long EntrySize, 264 ubi_cacheEntryPtr EntryPtr, 265 ubi_trItemPtr Key ) 266 /* ------------------------------------------------------------------------ ** 267 * Add an entry to the cache. 268 * 269 * Input: CachePtr - A pointer to the cache into which the entry 270 * will be added. 271 * EntrySize - The size, in bytes, of the memory block indicated 272 * by EntryPtr. This will be copied into the 273 * EntryPtr->entry_size field. 274 * EntryPtr - A pointer to a memory block that begins with a 275 * ubi_cacheEntry structure. The entry structure 276 * should be followed immediately by the data to be 277 * cached (even if that is a pointer to yet more data). 278 * Key - Pointer used to identify the lookup key within the 279 * Entry. 280 * 281 * Output: None. 282 * 283 * Notes: After adding the new node, the cache is "trimmed". This 284 * removes extra nodes if the tree has exceeded it's memory or 285 * entry count limits. It is unlikely that the newly added node 286 * will be purged from the cache (assuming a reasonably large 287 * cache), since new nodes in a splay tree (which is what this 288 * module was designed to use) are moved to the top of the tree 289 * and the cache purge process removes nodes from the bottom of 290 * the tree. 291 * - The underlying splay tree is opened in OVERWRITE mode. If 292 * the input key matches an existing key, the existing entry will 293 * be politely removed from the tree and freed. 294 * - Memory is allocated in multiples of the word size. The 295 * return value of the strlen() function does not reflect 296 * this; it will allways be less than or equal to the amount 297 * of memory actually allocated. 298 * 299 * ------------------------------------------------------------------------ ** 300 */ 301 { 302 ubi_trNodePtr OldNode; 303 304 EntryPtr->entry_size = EntrySize; 305 CachePtr->mem_used += EntrySize; 306 (void)ubi_trInsert( CachePtr, EntryPtr, Key, &OldNode ); 307 if( OldNode ) 308 free_entry( CachePtr, (ubi_cacheEntryPtr)OldNode ); 309 310 cachetrim( CachePtr ); 311 } /* ubi_cachePut */ 312 313ubi_cacheEntryPtr ubi_cacheGet( ubi_cacheRootPtr CachePtr, 314 ubi_trItemPtr FindMe ) 315 /* ------------------------------------------------------------------------ ** 316 * Attempt to retrieve an entry from the cache. 317 * 318 * Input: CachePtr - A ponter to the cache that is to be searched. 319 * FindMe - A ubi_trItemPtr that indicates the key for which 320 * to search. 321 * 322 * Output: A pointer to the cache entry that was found, or NULL if no 323 * matching entry was found. 324 * 325 * Notes: This function also updates the hit ratio counters. 326 * The counters are unsigned short. If the number of cache tries 327 * reaches 32768, then both the number of tries and the number of 328 * hits are divided by two. This prevents the counters from 329 * overflowing. See the comments in ubi_cacheHitRatio() for 330 * additional notes. 331 * 332 * ------------------------------------------------------------------------ ** 333 */ 334 { 335 ubi_trNodePtr FoundPtr; 336 337 FoundPtr = ubi_trFind( CachePtr, FindMe ); 338 339 if( FoundPtr ) 340 CachePtr->cache_hits++; 341 CachePtr->cache_trys++; 342 343 if( CachePtr->cache_trys & 0x8000 ) 344 { 345 CachePtr->cache_hits = CachePtr->cache_hits / 2; 346 CachePtr->cache_trys = CachePtr->cache_trys / 2; 347 } 348 349 return( (ubi_cacheEntryPtr)FoundPtr ); 350 } /* ubi_cacheGet */ 351 352ubi_trBool ubi_cacheDelete( ubi_cacheRootPtr CachePtr, ubi_trItemPtr DeleteMe ) 353 /* ------------------------------------------------------------------------ ** 354 * Find and delete the specified cache entry. 355 * 356 * Input: CachePtr - A pointer to the cache. 357 * DeleteMe - The key of the entry to be deleted. 358 * 359 * Output: TRUE if the entry was found & freed, else FALSE. 360 * 361 * ------------------------------------------------------------------------ ** 362 */ 363 { 364 ubi_trNodePtr FoundPtr; 365 366 FoundPtr = ubi_trFind( CachePtr, DeleteMe ); 367 if( FoundPtr ) 368 { 369 (void)ubi_trRemove( CachePtr, FoundPtr ); 370 free_entry( CachePtr, (ubi_cacheEntryPtr)FoundPtr ); 371 return( ubi_trTRUE ); 372 } 373 return( ubi_trFALSE ); 374 } /* ubi_cacheDelete */ 375 376ubi_trBool ubi_cacheReduce( ubi_cacheRootPtr CachePtr, unsigned long count ) 377 /* ------------------------------------------------------------------------ ** 378 * Remove <count> entries from the bottom of the cache. 379 * 380 * Input: CachePtr - A pointer to the cache which is to be reduced in 381 * size. 382 * count - The number of entries to remove. 383 * 384 * Output: The function will return TRUE if <count> entries were removed, 385 * else FALSE. A return value of FALSE should indicate that 386 * there were less than <count> entries in the cache, and that the 387 * cache is now empty. 388 * 389 * Notes: This function forces a reduction in the number of cache entries 390 * without requiring that the MaxMemory or MaxEntries values be 391 * changed. 392 * 393 * ------------------------------------------------------------------------ ** 394 */ 395 { 396 ubi_trNodePtr NodePtr; 397 398 while( count ) 399 { 400 NodePtr = ubi_trLeafNode( CachePtr->root.root ); 401 if( NULL == NodePtr ) 402 return( ubi_trFALSE ); 403 else 404 { 405 (void)ubi_trRemove( CachePtr, NodePtr ); 406 free_entry( CachePtr, (ubi_cacheEntryPtr)NodePtr ); 407 } 408 count--; 409 } 410 return( ubi_trTRUE ); 411 } /* ubi_cacheReduce */ 412 413unsigned long ubi_cacheSetMaxEntries( ubi_cacheRootPtr CachePtr, 414 unsigned long NewSize ) 415 /* ------------------------------------------------------------------------ ** 416 * Change the maximum number of entries allowed to exist in the cache. 417 * 418 * Input: CachePtr - A pointer to the cache to be modified. 419 * NewSize - The new maximum number of cache entries. 420 * 421 * Output: The maximum number of entries previously allowed to exist in 422 * the cache. 423 * 424 * Notes: If the new size is less than the old size, this function will 425 * trim the cache (remove excess entries). 426 * - A value of zero indicates an unlimited number of entries. 427 * 428 * ------------------------------------------------------------------------ ** 429 */ 430 { 431 unsigned long oldsize = CachePtr->max_entries; /* Save the old value. */ 432 433 CachePtr->max_entries = NewSize; /* Apply the new value. */ 434 if( (NewSize < oldsize) || (NewSize && !oldsize) ) /* If size is smaller, */ 435 cachetrim( CachePtr ); /* remove excess. */ 436 return( oldsize ); 437 } /* ubi_cacheSetMaxEntries */ 438 439unsigned long ubi_cacheSetMaxMemory( ubi_cacheRootPtr CachePtr, 440 unsigned long NewSize ) 441 /* ------------------------------------------------------------------------ ** 442 * Change the maximum amount of memory to be used for storing cache 443 * entries. 444 * 445 * Input: CachePtr - A pointer to the cache to be modified. 446 * NewSize - The new cache memory size. 447 * 448 * Output: The previous maximum memory size. 449 * 450 * Notes: If the new size is less than the old size, this function will 451 * trim the cache (remove excess entries). 452 * - A value of zero indicates that the cache has no memory limit. 453 * 454 * ------------------------------------------------------------------------ ** 455 */ 456 { 457 unsigned long oldsize = CachePtr->max_memory; /* Save the old value. */ 458 459 CachePtr->max_memory = NewSize; /* Apply the new value. */ 460 if( (NewSize < oldsize) || (NewSize && !oldsize) ) /* If size is smaller, */ 461 cachetrim( CachePtr ); /* remove excess. */ 462 return( oldsize ); 463 } /* ubi_cacheSetMaxMemory */ 464 465int ubi_cacheHitRatio( ubi_cacheRootPtr CachePtr ) 466 /* ------------------------------------------------------------------------ ** 467 * Returns a value that is 10,000 times the slightly weighted average hit 468 * ratio for the cache. 469 * 470 * Input: CachePtr - Pointer to the cache to be queried. 471 * 472 * Output: An integer that is 10,000 times the number of successful 473 * cache hits divided by the number of cache lookups, or: 474 * (10000 * hits) / trys 475 * You can easily convert this to a float, or do something 476 * like this (where i is the return value of this function): 477 * 478 * printf( "Hit rate : %d.%02d%%\n", (i/100), (i%100) ); 479 * 480 * Notes: I say "slightly-weighted", because the numerator and 481 * denominator are both accumulated in locations of type 482 * 'unsigned short'. If the number of cache trys becomes 483 * large enough, both are divided by two. (See function 484 * ubi_cacheGet().) 485 * Dividing both numerator and denominator by two does not 486 * change the ratio (much...it is an integer divide), but it 487 * does mean that subsequent increments to either counter will 488 * have twice as much significance as previous ones. 489 * 490 * - The value returned by this function will be in the range 491 * [0..10000] because ( 0 <= cache_hits <= cache_trys ) will 492 * always be true. 493 * 494 * ------------------------------------------------------------------------ ** 495 */ 496 { 497 int tmp = 0; 498 499 if( CachePtr->cache_trys ) 500 tmp = (int)( (10000 * (long)(CachePtr->cache_hits) ) 501 / (long)(CachePtr->cache_trys) ); 502 return( tmp ); 503 } /* ubi_cacheHitRatio */ 504 505/* -------------------------------------------------------------------------- */ 506