1 /* ========================================================================== **
4 * Copyright (C) 1997 by Christopher R. Hertel
6 * Email: crh@ubiqx.mn.org
7 * -------------------------------------------------------------------------- **
9 * This module implements a generic cache.
11 * -------------------------------------------------------------------------- **
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.
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.
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.
27 * -------------------------------------------------------------------------- **
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
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
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
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
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.)
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
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.
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
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.
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.)
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.
91 * -------------------------------------------------------------------------- **
94 * Revision 0.0 1997/12/18 06:24:33 crh
97 * ========================================================================== **
100 #include <stdlib.h> /* Defines NULL. */
101 #include "ubi_Cache.h" /* Header for *this* module. */
103 /* -------------------------------------------------------------------------- **
107 /* -------------------------------------------------------------------------- **
108 * Internal functions...
111 static void free_entry( ubi_cacheRootPtr CachePtr, ubi_cacheEntryPtr EntryPtr )
112 /* ------------------------------------------------------------------------ **
113 * Free a ubi_cacheEntry, and adjust the mem_used counter accordingly.
115 * Input: CachePtr - A pointer to the cache from which the entry has
117 * EntryPtr - A pointer to the already removed entry.
121 * Notes: The entry must be removed from the cache *before* this function
123 * ------------------------------------------------------------------------ **
126 CachePtr->mem_used -= EntryPtr->entry_size;
127 (*CachePtr->free_func)( (void *)EntryPtr );
130 static void cachetrim( ubi_cacheRootPtr crptr )
131 /* ------------------------------------------------------------------------ **
132 * Remove entries from the cache until the number of entries and the amount
133 * of memory used are *both* below or at the maximum.
135 * Input: crptr - pointer to the cache to be trimmed.
139 * ------------------------------------------------------------------------ **
142 while( ( crptr->max_entries && (crptr->max_entries < crptr->root.count) )
143 || ( crptr->max_memory && (crptr->max_memory < crptr->mem_used) ) )
145 if( !ubi_cacheReduce( crptr, 1 ) )
151 /* -------------------------------------------------------------------------- **
152 * Exported functions...
155 ubi_cacheRootPtr ubi_cacheInit( ubi_cacheRootPtr CachePtr,
156 ubi_trCompFunc CompFunc,
157 ubi_trKillNodeRtn FreeFunc,
158 unsigned long MaxEntries,
159 unsigned long MaxMemory )
160 /* ------------------------------------------------------------------------ **
161 * Initialize a cache header structure.
163 * Input: CachePtr - A pointer to a ubi_cacheRoot structure that is
165 * CompFunc - A pointer to the function that will be called
166 * to compare two cache values. See the module
167 * comments, above, for more information.
168 * FreeFunc - A pointer to a function that will be called
169 * to free a cache entry. If you allocated
170 * the cache entry using malloc(), then this
171 * will likely be free(). If you are allocating
172 * cache entries from a free list, then this will
173 * likely be a function that returns memory to the
175 * MaxEntries - The maximum number of entries that will be
176 * allowed to exist in the cache. If this limit
177 * is exceeded, then existing entries will be
178 * removed from the cache. A value of zero
179 * indicates that there is no limit on the number
180 * of cache entries. See ubi_cachePut().
181 * MaxMemory - The maximum amount of memory, in bytes, to be
182 * allocated to the cache (excluding the cache
183 * header). If this is exceeded, existing entries
184 * in the cache will be removed until enough memory
185 * has been freed to meet the condition. See
188 * Output: A pointer to the initialized cache (i.e., the same as CachePtr).
190 * Notes: Both MaxEntries and MaxMemory may be changed after the cache
191 * has been created. See
192 * ubi_cacheSetMaxEntries()
193 * ubi_cacheSetMaxMemory()
194 * ubi_cacheGetMaxEntries()
195 * ubi_cacheGetMaxMemory() (the latter two are macros).
197 * - Memory is allocated in multiples of the word size. The
198 * return value of the strlen() function does not reflect
199 * this; it will allways be less than or equal to the amount
200 * of memory actually allocated. Keep this in mind when
201 * choosing a value for MaxMemory.
203 * ------------------------------------------------------------------------ **
208 (void)ubi_trInitTree( CachePtr, CompFunc, ubi_trOVERWRITE );
209 CachePtr->free_func = FreeFunc;
210 CachePtr->max_entries = MaxEntries;
211 CachePtr->max_memory = MaxMemory;
212 CachePtr->mem_used = 0;
213 CachePtr->cache_hits = 0;
214 CachePtr->cache_trys = 0;
217 } /* ubi_cacheInit */
219 ubi_cacheRootPtr ubi_cacheClear( ubi_cacheRootPtr CachePtr )
220 /* ------------------------------------------------------------------------ **
221 * Remove and free all entries in an existing cache.
223 * Input: CachePtr - A pointer to the cache that is to be cleared.
225 * Output: A pointer to the cache header (i.e., the same as CachePtr).
226 * This function re-initializes the cache header.
228 * ------------------------------------------------------------------------ **
233 (void)ubi_trKillTree( CachePtr, CachePtr->free_func );
234 CachePtr->mem_used = 0;
235 CachePtr->cache_hits = 0;
236 CachePtr->cache_trys = 0;
239 } /* ubi_cacheClear */
241 void ubi_cachePut( ubi_cacheRootPtr CachePtr,
242 unsigned long EntrySize,
243 ubi_cacheEntryPtr EntryPtr,
245 /* ------------------------------------------------------------------------ **
246 * Add an entry to the cache.
248 * Input: CachePtr - A pointer to the cache into which the entry
250 * EntrySize - The size, in bytes, of the memory block indicated
251 * by EntryPtr. This will be copied into the
252 * EntryPtr->entry_size field.
253 * EntryPtr - A pointer to a memory block that begins with a
254 * ubi_cacheEntry structure. The entry structure
255 * should be followed immediately by the data to be
256 * cached (even if that is a pointer to yet more data).
257 * Key - Pointer used to identify the lookup key within the
262 * Notes: After adding the new node, the cache is "trimmed". This
263 * removes extra nodes if the tree has exceeded it's memory or
264 * entry count limits. It is unlikely that the newly added node
265 * will be purged from the cache (assuming a reasonably large
266 * cache), since new nodes in a splay tree (which is what this
267 * module was designed to use) are moved to the top of the tree
268 * and the cache purge process removes nodes from the bottom of
270 * - The underlying splay tree is opened in OVERWRITE mode. If
271 * the input key matches an existing key, the existing entry will
272 * be politely removed from the tree and freed.
273 * - Memory is allocated in multiples of the word size. The
274 * return value of the strlen() function does not reflect
275 * this; it will allways be less than or equal to the amount
276 * of memory actually allocated.
278 * ------------------------------------------------------------------------ **
281 ubi_trNodePtr OldNode;
283 EntryPtr->entry_size = EntrySize;
284 CachePtr->mem_used += EntrySize;
285 (void)ubi_trInsert( CachePtr, EntryPtr, Key, &OldNode );
287 free_entry( CachePtr, (ubi_cacheEntryPtr)OldNode );
289 cachetrim( CachePtr );
292 ubi_cacheEntryPtr ubi_cacheGet( ubi_cacheRootPtr CachePtr,
293 ubi_trItemPtr FindMe )
294 /* ------------------------------------------------------------------------ **
295 * Attempt to retrieve an entry from the cache.
297 * Input: CachePtr - A ponter to the cache that is to be searched.
298 * FindMe - A ubi_trItemPtr that indicates the key for which
301 * Output: A pointer to the cache entry that was found, or NULL if no
302 * matching entry was found.
304 * Notes: This function also updates the hit ratio counters.
305 * The counters are unsigned short. If the number of cache tries
306 * reaches 32768, then both the number of tries and the number of
307 * hits are divided by two. This prevents the counters from
308 * overflowing. See the comments in ubi_cacheHitRatio() for
311 * ------------------------------------------------------------------------ **
314 ubi_trNodePtr FoundPtr;
316 FoundPtr = ubi_trFind( CachePtr, FindMe );
319 CachePtr->cache_hits++;
320 CachePtr->cache_trys++;
322 if( CachePtr->cache_trys & 0x8000 )
324 CachePtr->cache_hits = CachePtr->cache_hits / 2;
325 CachePtr->cache_trys = CachePtr->cache_trys / 2;
328 return( (ubi_cacheEntryPtr)FoundPtr );
331 ubi_trBool ubi_cacheDelete( ubi_cacheRootPtr CachePtr, ubi_trItemPtr DeleteMe )
332 /* ------------------------------------------------------------------------ **
333 * Find and delete the specified cache entry.
335 * Input: CachePtr - A pointer to the cache.
336 * DeleteMe - The key of the entry to be deleted.
338 * Output: TRUE if the entry was found & freed, else FALSE.
340 * ------------------------------------------------------------------------ **
343 ubi_trNodePtr FoundPtr;
345 FoundPtr = ubi_trFind( CachePtr, DeleteMe );
348 (void)ubi_trRemove( CachePtr, FoundPtr );
349 free_entry( CachePtr, (ubi_cacheEntryPtr)FoundPtr );
350 return( ubi_trTRUE );
352 return( ubi_trFALSE );
353 } /* ubi_cacheDelete */
355 ubi_trBool ubi_cacheReduce( ubi_cacheRootPtr CachePtr, unsigned long count )
356 /* ------------------------------------------------------------------------ **
357 * Remove <count> entries from the bottom of the cache.
359 * Input: CachePtr - A pointer to the cache which is to be reduced in
361 * count - The number of entries to remove.
363 * Output: The function will return TRUE if <count> entries were removed,
364 * else FALSE. A return value of FALSE should indicate that
365 * there were less than <count> entries in the cache, and that the
366 * cache is now empty.
368 * Notes: This function forces a reduction in the number of cache entries
369 * without requiring that the MaxMemory or MaxEntries values be
372 * ------------------------------------------------------------------------ **
375 ubi_trNodePtr NodePtr;
379 NodePtr = ubi_trLeafNode( CachePtr->root.root );
380 if( NULL == NodePtr )
381 return( ubi_trFALSE );
384 (void)ubi_trRemove( CachePtr, NodePtr );
385 free_entry( CachePtr, (ubi_cacheEntryPtr)NodePtr );
389 return( ubi_trTRUE );
390 } /* ubi_cacheReduce */
392 unsigned long ubi_cacheSetMaxEntries( ubi_cacheRootPtr CachePtr,
393 unsigned long NewSize )
394 /* ------------------------------------------------------------------------ **
395 * Change the maximum number of entries allowed to exist in the cache.
397 * Input: CachePtr - A pointer to the cache to be modified.
398 * NewSize - The new maximum number of cache entries.
400 * Output: The maximum number of entries previously allowed to exist in
403 * Notes: If the new size is less than the old size, this function will
404 * trim the cache (remove excess entries).
405 * - A value of zero indicates an unlimited number of entries.
407 * ------------------------------------------------------------------------ **
410 unsigned long oldsize = CachePtr->max_entries; /* Save the old value. */
412 CachePtr->max_entries = NewSize; /* Apply the new value. */
413 if( (NewSize < oldsize) || (NewSize && !oldsize) ) /* If size is smaller, */
414 cachetrim( CachePtr ); /* remove excess. */
416 } /* ubi_cacheSetMaxEntries */
418 unsigned long ubi_cacheSetMaxMemory( ubi_cacheRootPtr CachePtr,
419 unsigned long NewSize )
420 /* ------------------------------------------------------------------------ **
421 * Change the maximum amount of memory to be used for storing cache
424 * Input: CachePtr - A pointer to the cache to be modified.
425 * NewSize - The new cache memory size.
427 * Output: The previous maximum memory size.
429 * Notes: If the new size is less than the old size, this function will
430 * trim the cache (remove excess entries).
431 * - A value of zero indicates that the cache has no memory limit.
433 * ------------------------------------------------------------------------ **
436 unsigned long oldsize = CachePtr->max_memory; /* Save the old value. */
438 CachePtr->max_memory = NewSize; /* Apply the new value. */
439 if( (NewSize < oldsize) || (NewSize && !oldsize) ) /* If size is smaller, */
440 cachetrim( CachePtr ); /* remove excess. */
442 } /* ubi_cacheSetMaxMemory */
444 int ubi_cacheHitRatio( ubi_cacheRootPtr CachePtr )
445 /* ------------------------------------------------------------------------ **
446 * Returns a value that is 10,000 times the slightly weighted average hit
447 * ratio for the cache.
449 * Input: CachePtr - Pointer to the cache to be queried.
451 * Output: An integer that is 10,000 times the number of successful
452 * cache hits divided by the number of cache lookups, or:
453 * (10000 * hits) / trys
454 * You can easily convert this to a float, or do something
455 * like this (where i is the return value of this function):
457 * printf( "Hit rate : %d.%02d%%\n", (i/100), (i%100) );
459 * Notes: I say "slightly-weighted", because the numerator and
460 * denominator are both accumulated in locations of type
461 * 'unsigned short'. If the number of cache trys becomes
462 * large enough, both are divided by two. (See function
464 * Dividing both numerator and denominator by two does not
465 * change the ratio (much...it is an integer divide), but it
466 * does mean that subsequent increments to either counter will
467 * have twice as much significance as previous ones.
469 * - The value returned by this function will be in the range
470 * [0..10000] because ( 0 <= cache_hits <= cache_trys ) will
473 * ------------------------------------------------------------------------ **
478 if( CachePtr->cache_trys )
479 tmp = (int)( (10000 * (long)(CachePtr->cache_hits) )
480 / (long)(CachePtr->cache_trys) );
482 } /* ubi_cacheHitRatio */
484 /* -------------------------------------------------------------------------- */