strcache.c

   1 /* Constant string caching for GNU Make.
   2 Copyright (C) 2006-2013 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 "makeint.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 __attribute__((no_sanitize_undefined))
  76 static const char *
  77 add_string (const char *str, unsigned int len)
  78 {
  79   char *res;
  80   struct strcache *sp;
  81   struct strcache **spp = &strcache;
  82   /* We need space for the nul char.  */
  83   unsigned int sz = len + 1;
  84
  85   /* If the string we want is too large to fit into a single buffer, then
  86      no existing cache is large enough.  Change the maximum size.  */
  87   if (sz > bufsize)
  88     bufsize = CACHE_BUFFER_SIZE ((((sz + 1) / CACHE_BUFFER_BASE) + 1)
  89                                  * CACHE_BUFFER_BASE);
  90   else
  91     /* Find the first cache with enough free space.  */
  92     for (; *spp != NULL; spp = &(*spp)->next)
  93       if ((*spp)->bytesfree > sz)
  94         break;
  95
  96   /* If nothing is big enough, make a new cache.  */
  97   sp = *spp;
  98   if (sp == NULL)
  99     {
 100       sp = new_cache ();
 101       spp = &sp;
 102     }
 103
 104   /* Add the string to this cache.  */
 105   res = &sp->buffer[sp->end];
 106   memmove (res, str, len);
 107   res[len] = '\0';
 108   sp->end += sz;
 109   sp->bytesfree -= sz;
 110   ++sp->count;
 111
 112   /* If the amount free in this cache is less than the average string size,
 113      consider it full and move it to the full list.  */
 114   ++total_strings;
 115   total_size += sz;
 116
 117   if (sp->bytesfree < (total_size / total_strings) + 1)
 118     {
 119       *spp = (*spp)->next;
 120       sp->next = fullcache;
 121       fullcache = sp;
 122     }
 123
 124   return res;
 125 }
 126
 127
 128 /* Hash table of strings in the cache.  */
 129
 130 static unsigned long
 131 str_hash_1 (const void *key)
 132 {
 133   return_ISTRING_HASH_1 ((const char *) key);
 134 }
 135
 136 static unsigned long
 137 str_hash_2 (const void *key)
 138 {
 139   return_ISTRING_HASH_2 ((const char *) key);
 140 }
 141
 142 static int
 143 str_hash_cmp (const void *x, const void *y)
 144 {
 145   return_ISTRING_COMPARE ((const char *) x, (const char *) y);
 146 }
 147
 148 static struct hash_table strings;
 149 static unsigned long total_adds = 0;
 150
 151 static const char *
 152 add_hash (const char *str, int len)
 153 {
 154   /* Look up the string in the hash.  If it's there, return it.  */
 155   char *const *slot = (char *const *) hash_find_slot (&strings, str);
 156   const char *key = *slot;
 157
 158   /* Count the total number of add operations we performed.  */
 159   ++total_adds;
 160
 161   if (!HASH_VACANT (key))
 162     return key;
 163
 164   /* Not there yet so add it to a buffer, then into the hash table.  */
 165   key = add_string (str, len);
 166   hash_insert_at (&strings, key, slot);
 167   return key;
 168 }
 169
 170 /* Returns true if the string is in the cache; false if not.  */
 171 int
 172 strcache_iscached (const char *str)
 173 {
 174   struct strcache *sp;
 175
 176   for (sp = strcache; sp != 0; sp = sp->next)
 177     if (str >= sp->buffer && str < sp->buffer + sp->end)
 178       return 1;
 179   for (sp = fullcache; sp != 0; sp = sp->next)
 180     if (str >= sp->buffer && str < sp->buffer + sp->end)
 181       return 1;
 182
 183   return 0;
 184 }
 185
 186 /* If the string is already in the cache, return a pointer to the cached
 187    version.  If not, add it then return a pointer to the cached version.
 188    Note we do NOT take control of the string passed in.  */
 189 const char *
 190 strcache_add (const char *str)
 191 {
 192   return add_hash (str, strlen (str));
 193 }
 194
 195 const char *
 196 strcache_add_len (const char *str, unsigned int len)
 197 {
 198   /* If we're not given a nul-terminated string we have to create one, because
 199      the hashing functions expect it.  */
 200   if (str[len] != '\0')
 201     {
 202       char *key = alloca (len + 1);
 203       memcpy (key, str, len);
 204       key[len] = '\0';
 205       str = key;
 206     }
 207
 208   return add_hash (str, len);
 209 }
 210
 211 int
 212 strcache_setbufsize (unsigned int size)
 213 {
 214   if (size > bufsize)
 215     bufsize = size;
 216   return bufsize;
 217 }
 218
 219 void
 220 strcache_init (void)
 221 {
 222   hash_init (&strings, 8000, str_hash_1, str_hash_2, str_hash_cmp);
 223 }
 224
 225
 226 /* Generate some stats output.  */
 227
 228 void
 229 strcache_print_stats (const char *prefix)
 230 {
 231   const struct strcache *sp;
 232   unsigned long numbuffs = 0, fullbuffs = 0;
 233   unsigned long totfree = 0, maxfree = 0, minfree = bufsize;
 234
 235   if (! strcache)
 236     {
 237       printf (_("\n%s No strcache buffers\n"), prefix);
 238       return;
 239     }
 240
 241   /* Count the first buffer separately since it's not full.  */
 242   for (sp = strcache->next; sp != NULL; sp = sp->next)
 243     {
 244       sc_buflen_t bf = sp->bytesfree;
 245
 246       totfree += bf;
 247       maxfree = (bf > maxfree ? bf : maxfree);
 248       minfree = (bf < minfree ? bf : minfree);
 249
 250       ++numbuffs;
 251     }
 252   for (sp = fullcache; sp != NULL; sp = sp->next)
 253     {
 254       sc_buflen_t bf = sp->bytesfree;
 255
 256       totfree += bf;
 257       maxfree = (bf > maxfree ? bf : maxfree);
 258       minfree = (bf < minfree ? bf : minfree);
 259
 260       ++numbuffs;
 261       ++fullbuffs;
 262     }
 263
 264   /* Make sure we didn't lose any buffers.  */
 265   assert (total_buffers == numbuffs + 1);
 266
 267   printf (_("\n%s strcache buffers: %lu (%lu) / strings = %lu / storage = %lu B / avg = %lu B\n"),
 268           prefix, numbuffs + 1, fullbuffs, total_strings, total_size,
 269           (total_size / total_strings));
 270
 271   printf (_("%s current buf: size = %hu B / used = %hu B / count = %hu / avg = %hu B\n"),
 272           prefix, bufsize, strcache->end, strcache->count,
 273           (strcache->end / strcache->count));
 274
 275   if (numbuffs)
 276     {
 277       unsigned long sz = total_size - bufsize;
 278       unsigned long cnt = total_strings - strcache->count;
 279       sc_buflen_t avgfree = totfree / numbuffs;
 280
 281       printf (_("%s other used: total = %lu B / count = %lu / avg = %lu B\n"),
 282               prefix, sz, cnt, sz / cnt);
 283
 284       printf (_("%s other free: total = %lu B / max = %lu B / min = %lu B / avg = %hu B\n"),
 285               prefix, totfree, maxfree, minfree, avgfree);
 286     }
 287
 288   printf (_("\n%s strcache performance: lookups = %lu / hit rate = %lu%%\n"),
 289           prefix, total_adds, (long unsigned)(100.0 * (total_adds - total_strings) / total_adds));
 290   fputs (_("# hash-table stats:\n# "), stdout);
 291   hash_print_stats (&strings, stdout);
 292 }