strcache.c

   1 /* Constant string caching for GNU Make.
   2 Copyright (C) 2006, 2007, 2008, 2009, 2010 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
  19 #include <stddef.h>
  20 #include <assert.h>
  21
  22 #include "hash.h"
  23
  24 /* A string cached here will never be freed, so we don't need to worry about
  25    reference counting.  We just store the string, and then remember it in a
  26    hash so it can be looked up again. */
  27
  28 typedef unsigned short int sc_buflen_t;
  29
  30 struct strcache {
  31   struct strcache *next;    /* The next block of strings.  Must be first!  */
  32   sc_buflen_t end;          /* Offset to the beginning of free space.  */
  33   sc_buflen_t bytesfree;    /* Free space left in this buffer.  */
  34   sc_buflen_t count;        /* # of strings in this buffer (for stats).  */
  35   char buffer[1];           /* The buffer comes after this.  */
  36 };
  37
  38 /* The size (in bytes) of each cache buffer.
  39    Try to pick something that will map well into the heap.
  40    This must be able to be represented by a short int (<=65535).  */
  41 #define CACHE_BUFFER_BASE       (8192)
  42 #define CACHE_BUFFER_ALLOC(_s)  ((_s) - (2 * sizeof (size_t)))
  43 #define CACHE_BUFFER_OFFSET     (offsetof (struct strcache, buffer))
  44 #define CACHE_BUFFER_SIZE(_s)   (CACHE_BUFFER_ALLOC(_s) - CACHE_BUFFER_OFFSET)
  45
  46 static sc_buflen_t bufsize = CACHE_BUFFER_SIZE (CACHE_BUFFER_BASE);
  47 static struct strcache *strcache = NULL;
  48 static struct strcache *fullcache = NULL;
  49
  50 static unsigned long total_buffers = 0;
  51 static unsigned long total_strings = 0;
  52 static unsigned long total_size = 0;
  53
  54 /* Add a new buffer to the cache.  Add it at the front to reduce search time.
  55    This can also increase the overhead, since it's less likely that older
  56    buffers will be filled in.  However, GNU make has so many smaller strings
  57    that this doesn't seem to be much of an issue in practice.
  58  */
  59 static struct strcache *
  60 new_cache()
  61 {
  62   struct strcache *new;
  63   new = xmalloc (bufsize + CACHE_BUFFER_OFFSET);
  64   new->end = 0;
  65   new->count = 0;
  66   new->bytesfree = bufsize;
  67
  68   new->next = strcache;
  69   strcache = new;
  70
  71   ++total_buffers;
  72   return new;
  73 }
  74
  75 static const char *
  76 add_string (const char *str, unsigned int len)
  77 {
  78   char *res;
  79   struct strcache *sp;
  80   struct strcache **spp = &strcache;
  81   /* We need space for the nul char.  */
  82   unsigned int sz = len + 1;
  83
  84   /* If the string we want is too large to fit into a single buffer, then
  85      no existing cache is large enough.  Change the maximum size.  */
  86   if (sz > bufsize)
  87     bufsize = CACHE_BUFFER_SIZE ((((sz + 1) / CACHE_BUFFER_BASE) + 1)
  88                                  * CACHE_BUFFER_BASE);
  89   else
  90     /* Find the first cache with enough free space.  */
  91     for (; *spp != NULL; spp = &(*spp)->next)
  92       if ((*spp)->bytesfree > sz)
  93         break;
  94
  95   /* If nothing is big enough, make a new cache.  */
  96   sp = *spp;
  97   if (sp == NULL)
  98     {
  99       sp = new_cache ();
 100       spp = &sp;
 101     }
 102
 103   /* Add the string to this cache.  */
 104   res = &sp->buffer[sp->end];
 105   memmove (res, str, len);
 106   res[len] = '\0';
 107   sp->end += sz;
 108   sp->bytesfree -= sz;
 109   ++sp->count;
 110
 111   /* If the amount free in this cache is less than the average string size,
 112      consider it full and move it to the full list.  */
 113   ++total_strings;
 114   total_size += sz;
 115
 116   if (sp->bytesfree < (total_size / total_strings) + 1)
 117     {
 118       *spp = (*spp)->next;
 119       sp->next = fullcache;
 120       fullcache = sp;
 121     }
 122
 123   return res;
 124 }
 125
 126
 127 /* Hash table of strings in the cache.  */
 128
 129 static unsigned long
 130 str_hash_1 (const void *key)
 131 {
 132   return_ISTRING_HASH_1 ((const char *) key);
 133 }
 134
 135 static unsigned long
 136 str_hash_2 (const void *key)
 137 {
 138   return_ISTRING_HASH_2 ((const char *) key);
 139 }
 140
 141 static int
 142 str_hash_cmp (const void *x, const void *y)
 143 {
 144   return_ISTRING_COMPARE ((const char *) x, (const char *) y);
 145 }
 146
 147 static struct hash_table strings;
 148 static unsigned long total_adds = 0;
 149
 150 static const char *
 151 add_hash (const char *str, int len)
 152 {
 153   /* Look up the string in the hash.  If it's there, return it.  */
 154   char *const *slot = (char *const *) hash_find_slot (&strings, str);
 155   const char *key = *slot;
 156
 157   /* Count the total number of add operations we performed.  */
 158   ++total_adds;
 159
 160   if (!HASH_VACANT (key))
 161     return key;
 162
 163   /* Not there yet so add it to a buffer, then into the hash table.  */
 164   key = add_string (str, len);
 165   hash_insert_at (&strings, key, slot);
 166   return key;
 167 }
 168
 169 /* Returns true if the string is in the cache; false if not.  */
 170 int
 171 strcache_iscached (const char *str)
 172 {
 173   struct strcache *sp;
 174
 175   for (sp = strcache; sp != 0; sp = sp->next)
 176     if (str >= sp->buffer && str < sp->buffer + sp->end)
 177       return 1;
 178   for (sp = fullcache; sp != 0; sp = sp->next)
 179     if (str >= sp->buffer && str < sp->buffer + sp->end)
 180       return 1;
 181
 182   return 0;
 183 }
 184
 185 /* If the string is already in the cache, return a pointer to the cached
 186    version.  If not, add it then return a pointer to the cached version.
 187    Note we do NOT take control of the string passed in.  */
 188 const char *
 189 strcache_add (const char *str)
 190 {
 191   return add_hash (str, strlen (str));
 192 }
 193
 194 const char *
 195 strcache_add_len (const char *str, unsigned int len)
 196 {
 197   /* If we're not given a nul-terminated string we have to create one, because
 198      the hashing functions expect it.  */
 199   if (str[len] != '\0')
 200     {
 201       char *key = alloca (len + 1);
 202       memcpy (key, str, len);
 203       key[len] = '\0';
 204       str = key;
 205     }
 206
 207   return add_hash (str, len);
 208 }
 209
 210 int
 211 strcache_setbufsize(unsigned int size)
 212 {
 213   if (size > bufsize)
 214     bufsize = size;
 215   return bufsize;
 216 }
 217
 218 void
 219 strcache_init (void)
 220 {
 221   hash_init (&strings, 8000, str_hash_1, str_hash_2, str_hash_cmp);
 222 }
 223
 224
 225 /* Generate some stats output.  */
 226
 227 void
 228 strcache_print_stats (const char *prefix)
 229 {
 230   const struct strcache *sp;
 231   unsigned long numbuffs = 0, fullbuffs = 0;
 232   unsigned long totfree = 0, maxfree = 0, minfree = bufsize;
 233
 234   if (! strcache)
 235     {
 236       printf(_("\n%s No strcache buffers\n"), prefix);
 237       return;
 238     }
 239
 240   /* Count the first buffer separately since it's not full.  */
 241   for (sp = strcache->next; sp != NULL; sp = sp->next)
 242     {
 243       sc_buflen_t bf = sp->bytesfree;
 244
 245       totfree += bf;
 246       maxfree = (bf > maxfree ? bf : maxfree);
 247       minfree = (bf < minfree ? bf : minfree);
 248
 249       ++numbuffs;
 250     }
 251   for (sp = fullcache; sp != NULL; sp = sp->next)
 252     {
 253       sc_buflen_t bf = sp->bytesfree;
 254
 255       totfree += bf;
 256       maxfree = (bf > maxfree ? bf : maxfree);
 257       minfree = (bf < minfree ? bf : minfree);
 258
 259       ++numbuffs;
 260       ++fullbuffs;
 261     }
 262
 263   /* Make sure we didn't lose any buffers.  */
 264   assert (total_buffers == numbuffs + 1);
 265
 266   printf (_("\n%s strcache buffers: %lu (%lu) / strings = %lu / storage = %lu B / avg = %lu B\n"),
 267           prefix, numbuffs + 1, fullbuffs, total_strings, total_size,
 268           (total_size / total_strings));
 269
 270   printf (_("%s current buf: size = %hu B / used = %hu B / count = %hu / avg = %hu B\n"),
 271           prefix, bufsize, strcache->end, strcache->count,
 272           (strcache->end / strcache->count));
 273
 274   if (numbuffs)
 275     {
 276       unsigned long sz = total_size - bufsize;
 277       unsigned long cnt = total_strings - strcache->count;
 278       sc_buflen_t avgfree = totfree / numbuffs;
 279
 280       printf (_("%s other used: total = %lu B / count = %lu / avg = %lu B\n"),
 281               prefix, sz, cnt, sz / cnt);
 282
 283       printf (_("%s other free: total = %lu B / max = %lu B / min = %lu B / avg = %hu B\n"),
 284               prefix, totfree, maxfree, minfree, avgfree);
 285     }
 286
 287   printf (_("\n%s strcache performance: lookups = %lu / hit rate = %lu%%\n"),
 288           prefix, total_adds, (long unsigned)(100.0 * (total_adds - total_strings) / total_adds));
 289   fputs (_("# hash-table stats:\n# "), stdout);
 290   hash_print_stats (&strings, stdout);
 291 }