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