src/kmk/strcache.c

   1 /* Constant string caching for GNU Make.
   2 Copyright (C) 2006, 2007 Free Software Foundation, Inc.
   3 This file is part of GNU Make.
   4
   5 GNU Make is free software; you can redistribute it and/or modify it under the
   6 terms of the GNU General Public License as published by the Free Software
   7 Foundation; either version 3 of the License, or (at your option) any later
   8 version.
   9
  10 GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
  11 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  12 A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License along with
  15 this program.  If not, see <http://www.gnu.org/licenses/>.  */
  16
  17 #include "make.h"
  18 #ifndef CONFIG_WITH_STRCACHE2
  19
  20 #include <assert.h>
  21
  22 #include "hash.h"
  23
  24 /* The size (in bytes) of each cache buffer.
  25    Try to pick something that will map well into the heap.  */
  26 #define CACHE_BUFFER_SIZE   (8192 - 16)
  27
  28
  29 /* A string cached here will never be freed, so we don't need to worry about
  30    reference counting.  We just store the string, and then remember it in a
  31    hash so it can be looked up again. */
  32
  33 struct strcache {
  34   struct strcache *next;    /* The next block of strings.  */
  35   char *end;                /* Pointer to the beginning of the free space.  */
  36   int count;                /* # of strings in this buffer (for stats).  */
  37   int bytesfree;            /* The amount of the buffer that is free.  */
  38   char buffer[1];           /* The buffer comes after this.  */
  39 };
  40
  41 static int bufsize = CACHE_BUFFER_SIZE;
  42 static struct strcache *strcache = NULL;
  43
  44 /* Add a new buffer to the cache.  Add it at the front to reduce search time.
  45    This can also increase the overhead, since it's less likely that older
  46    buffers will be filled in.  However, GNU make has so many smaller strings
  47    that this doesn't seem to be much of an issue in practice.
  48  */
  49 static struct strcache *
  50 new_cache()
  51 {
  52   struct strcache *new;
  53   new = xmalloc (sizeof (*new) + bufsize);
  54   new->end = new->buffer;
  55   new->count = 0;
  56   new->bytesfree = bufsize;
  57
  58   new->next = strcache;
  59   strcache = new;
  60
  61   return new;
  62 }
  63
  64 static const char *
  65 add_string(const char *str, int len)
  66 {
  67   struct strcache *best = NULL;
  68   struct strcache *sp;
  69   const char *res;
  70
  71   /* If the string we want is too large to fit into a single buffer, then
  72      we're screwed; nothing will ever fit!  Change the maximum size of the
  73      cache to be big enough.  */
  74   if (len > bufsize)
  75     bufsize = len * 2;
  76
  77   /* First, find a cache with enough free space.  We always look through all
  78      the blocks and choose the one with the best fit (the one that leaves the
  79      least amount of space free).  */
  80   for (sp = strcache; sp != NULL; sp = sp->next)
  81     if (sp->bytesfree > len && (!best || best->bytesfree > sp->bytesfree))
  82       best = sp;
  83
  84   /* If nothing is big enough, make a new cache.  */
  85   if (!best)
  86     best = new_cache();
  87
  88   assert (best->bytesfree > len);
  89
  90   /* Add the string to the best cache.  */
  91   res = best->end;
  92   memcpy (best->end, str, len);
  93   best->end += len;
  94   *(best->end++) = '\0';
  95   best->bytesfree -= len + 1;
  96   ++best->count;
  97
  98   return res;
  99 }
 100
 101
 102 /* Hash table of strings in the cache.  */
 103
 104 static unsigned long
 105 str_hash_1 (const void *key)
 106 {
 107   return_ISTRING_HASH_1 ((const char *) key);
 108 }
 109
 110 static unsigned long
 111 str_hash_2 (const void *key)
 112 {
 113   return_ISTRING_HASH_2 ((const char *) key);
 114 }
 115
 116 static int
 117 str_hash_cmp (const void *x, const void *y)
 118 {
 119   return_ISTRING_COMPARE ((const char *) x, (const char *) y);
 120 }
 121
 122 static struct hash_table strings;
 123 static unsigned long total_adds = 0;
 124
 125 static const char *
 126 add_hash (const char *str, int len)
 127 {
 128   /* Look up the string in the hash.  If it's there, return it.  */
 129   char *const *slot = (char *const *) hash_find_slot (&strings, str);
 130   const char *key = *slot;
 131
 132   /* Count the total number of adds we performed.  */
 133   ++total_adds;
 134
 135   if (!HASH_VACANT (key))
 136     return key;
 137
 138   /* Not there yet so add it to a buffer, then into the hash table.  */
 139   key = add_string (str, len);
 140   hash_insert_at (&strings, key, slot);
 141   return key;
 142 }
 143
 144 /* Returns true if the string is in the cache; false if not.  */
 145 int
 146 strcache_iscached (const char *str)
 147 {
 148   struct strcache *sp;
 149
 150   for (sp = strcache; sp != 0; sp = sp->next)
 151     if (str >= sp->buffer && str < sp->end)
 152       return 1;
 153
 154   return 0;
 155 }
 156
 157 /* If the string is already in the cache, return a pointer to the cached
 158    version.  If not, add it then return a pointer to the cached version.
 159    Note we do NOT take control of the string passed in.  */
 160 const char *
 161 strcache_add (const char *str)
 162 {
 163   return add_hash (str, strlen (str));
 164 }
 165
 166 const char *
 167 strcache_add_len (const char *str, int len)
 168 {
 169   /* If we're not given a nul-terminated string we have to create one, because
 170      the hashing functions expect it.  */
 171   if (str[len] != '\0')
 172     {
 173       char *key = alloca (len + 1);
 174       memcpy (key, str, len);
 175       key[len] = '\0';
 176       str = key;
 177     }
 178
 179   return add_hash (str, len);
 180 }
 181
 182 int
 183 strcache_setbufsize(int size)
 184 {
 185   if (size > bufsize)
 186     bufsize = size;
 187   return bufsize;
 188 }
 189
 190 void
 191 strcache_init (void)
 192 {
 193   hash_init (&strings, 8000, str_hash_1, str_hash_2, str_hash_cmp);
 194 }
 195
 196
 197 /* Generate some stats output.  */
 198
 199 void
 200 strcache_print_stats (const char *prefix)
 201 {
 202   int numbuffs = 0, numstrs = 0;
 203   int totsize = 0, avgsize, maxsize = 0, minsize = bufsize;
 204   int totfree = 0, avgfree, maxfree = 0, minfree = bufsize;
 205   int lastused = 0, lastfree = 0;
 206
 207   if (strcache)
 208     {
 209       const struct strcache *sp;
 210
 211       /* Count the first buffer separately since it's not full.  */
 212       lastused = strcache->end - strcache->buffer;
 213       lastfree = strcache->bytesfree;
 214
 215       for (sp = strcache->next; sp != NULL; sp = sp->next)
 216         {
 217           int bf = sp->bytesfree;
 218           int sz = sp->end - sp->buffer;
 219
 220           ++numbuffs;
 221           numstrs += sp->count;
 222
 223           totsize += sz;
 224           maxsize = (sz > maxsize ? sz : maxsize);
 225           minsize = (sz < minsize ? sz : minsize);
 226
 227           totfree += bf;
 228           maxfree = (bf > maxfree ? bf : maxfree);
 229           minfree = (bf < minfree ? bf : minfree);
 230         }
 231     }
 232
 233   avgsize = numbuffs ? (int)(totsize / numbuffs) : 0;
 234   avgfree = numbuffs ? (int)(totfree / numbuffs) : 0;
 235
 236   printf (_("\n%s # of strings in strcache: %d / lookups = %lu / hits = %lu\n"),
 237           prefix, numstrs, total_adds, (total_adds - numstrs));
 238   printf (_("%s # of strcache buffers: %d (* %d B/buffer = %d B)\n"),
 239           prefix, (numbuffs + 1), bufsize, ((numbuffs + 1) * bufsize));
 240   printf (_("%s strcache used: total = %d (%d) / max = %d / min = %d / avg = %d\n"),
 241           prefix, totsize, lastused, maxsize, minsize, avgsize);
 242   printf (_("%s strcache free: total = %d (%d) / max = %d / min = %d / avg = %d\n"),
 243           prefix, totfree, lastfree, maxfree, minfree, avgfree);
 244
 245   fputs (_("\n# strcache hash-table stats:\n# "), stdout);
 246   hash_print_stats (&strings, stdout);
 247 }
 248
 249 #else /* CONFIG_WITH_STRCACHE2 */
 250
 251 #include "strcache2.h"
 252
 253 const char *suffixes_strcached;
 254
 255 /* The file string cache. */
 256 struct strcache2 file_strcache;
 257
 258 void strcache_init (void)
 259 {
 260   strcache2_init(&file_strcache,
 261                  "file",        /* name */
 262                  65536,         /* hash size */
 263                  0,             /* default segment size*/
 264 #ifdef HAVE_CASE_INSENSITIVE_FS
 265                  1,             /* case insensitive */
 266 #else
 267                  0,             /* case insensitive */
 268 #endif
 269                  0);            /* thread safe */
 270
 271   /* .SUFFIXES is referenced in several loops, keep the added pointer in a
 272      global var so these can be optimized. */
 273
 274   suffixes_strcached = strcache_add_len (".SUFFIXES", sizeof (".SUFFIXES")-1);
 275 }
 276
 277 void
 278 strcache_print_stats (const char *prefix)
 279 {
 280   strcache2_print_stats (&file_strcache, prefix);
 281 }
 282
 283 #endif /* CONFIG_WITH_STRCACHE2 */
 284