storage/tradindexed/tdx-cache.c

   1 /*  $Id: tdx-cache.c 5394 2002-04-04 22:55:24Z rra $
   2 **
   3 **  Cache functions for open overview data files.
   4 **
   5 **  This code maintains a cache of open overview data files to avoid some of
   6 **  the overhead involved in closing and reopening files.  All opens and
   7 **  closes should go through this code, and the hit ratio is tracked to check
   8 **  cache effectiveness.
   9 */
  10
  11 #include "config.h"
  12 #include "clibrary.h"
  13 #include <time.h>
  14
  15 #include "inn/hashtab.h"
  16 #include "inn/messages.h"
  17 #include "libinn.h"
  18 #include "storage.h"
  19 #include "tdx-private.h"
  20
  21 /* Returned to callers as an opaque data type, this struct holds all of the
  22    information about the cache. */
  23 struct cache {
  24     struct hash *hashtable;
  25     unsigned int count;
  26     unsigned int max;
  27     unsigned long queries;
  28     unsigned long hits;
  29 };
  30
  31 /* A cache entry, holding a group_data struct and some additional information
  32    used to do cache lookups and to choose what to drop from the cache. */
  33 struct cache_entry {
  34     struct group_data *data;
  35     HASH hash;
  36     time_t lastused;
  37 };
  38
  39
  40 /*
  41 **  The hash function for a cache_entry.  Just return as much of the group
  42 **  hash as can fit in an unsigned long.
  43 */
  44 static unsigned long
  45 entry_hash(const void *key)
  46 {
  47     const HASH *hash = key;
  48     unsigned long bucket;
  49
  50     memcpy(&bucket, hash, sizeof(bucket));
  51     return bucket;
  52 }
  53
  54
  55 /*
  56 **  Given a cache_entry, return its key.
  57 */
  58 static const void *
  59 entry_key(const void *data)
  60 {
  61     const struct cache_entry *entry = (const struct cache_entry *) data;
  62
  63     return &entry->hash;
  64 }
  65
  66
  67 /*
  68 **  Check to see if two entries are equal.
  69 */
  70 static bool
  71 entry_equal(const void *key, const void *data)
  72 {
  73     const HASH *hash = (const HASH *) key;
  74     const struct cache_entry *entry = (const struct cache_entry *) data;
  75
  76     return (memcmp(hash, &entry->hash, sizeof(HASH)) == 0);
  77 }
  78
  79
  80 /*
  81 **  Free a cache entry.
  82 */
  83 static void
  84 entry_delete(void *data)
  85 {
  86     struct cache_entry *entry = (struct cache_entry *) data;
  87
  88     entry->data->refcount--;
  89     if (entry->data->refcount == 0)
  90         tdx_data_close(entry->data);
  91     free(entry);
  92 }
  93
  94
  95 /*
  96 **  Called by hash_traverse, this function finds the oldest entry with the
  97 **  smallest refcount and stores it in the provided pointer so that it can be
  98 **  freed.  This is used when the cache is full to drop the least useful
  99 **  entry.
 100 */
 101 static void
 102 entry_find_oldest(void *data, void *cookie)
 103 {
 104     struct cache_entry *entry = (struct cache_entry *) data;
 105     struct cache_entry **oldest = (struct cache_entry **) cookie;
 106
 107     if (*oldest == NULL) {
 108         *oldest = entry;
 109         return;
 110     }
 111     if (entry->data->refcount > (*oldest)->data->refcount)
 112         return;
 113     if (entry->lastused > (*oldest)->lastused)
 114         return;
 115     *oldest = data;
 116 }
 117
 118
 119 /*
 120 **  Create a new cache with the given size.
 121 */
 122 struct cache *
 123 tdx_cache_create(unsigned int size)
 124 {
 125     struct cache *cache;
 126
 127     cache = xmalloc(sizeof(struct cache));
 128     cache->count = 0;
 129     cache->max = size;
 130     cache->queries = 0;
 131     cache->hits = 0;
 132     cache->hashtable = hash_create(size * 4 / 3, entry_hash, entry_key,
 133                                    entry_equal, entry_delete);
 134     return cache;
 135 }
 136
 137
 138 /*
 139 **  Look up a particular entry and return it.
 140 */
 141 struct group_data *
 142 tdx_cache_lookup(struct cache *cache, HASH hash)
 143 {
 144     struct cache_entry *entry;
 145
 146     cache->queries++;
 147     entry = hash_lookup(cache->hashtable, &hash);
 148     if (entry != NULL) {
 149         cache->hits++;
 150         entry->lastused = time(NULL);
 151     }
 152     return (entry == NULL) ? NULL : entry->data;
 153 }
 154
 155
 156 /*
 157 **  Insert a new entry, clearing out the oldest entry if the cache is
 158 **  currently full.
 159 */
 160 void
 161 tdx_cache_insert(struct cache *cache, HASH hash, struct group_data *data)
 162 {
 163     struct cache_entry *entry;
 164
 165     if (cache->count == cache->max) {
 166         struct cache_entry *oldest = NULL;
 167
 168         hash_traverse(cache->hashtable, entry_find_oldest, &oldest);
 169         if (oldest == NULL) {
 170             warn("tradindexed: unable to find oldest cache entry");
 171             return;
 172         } else {
 173             if (!hash_delete(cache->hashtable, &oldest->hash)) {
 174                 warn("tradindexed: cannot delete oldest cache entry");
 175                 return;
 176             }
 177         }
 178         cache->count--;
 179     }
 180     entry = xmalloc(sizeof(struct cache_entry));
 181     entry->data = data;
 182     entry->hash = hash;
 183     entry->lastused = time(NULL);
 184     if (!hash_insert(cache->hashtable, &entry->hash, entry)) {
 185         warn("tradindexed: duplicate cache entry for %s", HashToText(hash));
 186         free(entry);
 187     } else {
 188         entry->data->refcount++;
 189         cache->count++;
 190     }
 191 }
 192
 193
 194 /*
 195 **  Delete an entry from the cache.
 196 */
 197 void
 198 tdx_cache_delete(struct cache *cache, HASH hash)
 199 {
 200     if (!hash_delete(cache->hashtable, &hash))
 201         warn("tradindexed: unable to remove cache entry for %s",
 202              HashToText(hash));
 203 }
 204
 205
 206 /*
 207 **  Delete the cache and all of the resources that it's holding open.
 208 */
 209 void
 210 tdx_cache_free(struct cache *cache)
 211 {
 212     hash_free(cache->hashtable);
 213     free(cache);
 214 }