src/strcache.c

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