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
  19 #include <assert.h>
  20
  21 #include "hash.h"
  22
  23 /* The size (in bytes) of each cache buffer.
  24    Try to pick something that will map well into the heap.  */
  25 #define CACHE_BUFFER_SIZE   (8192 - 16)
  26
  27
  28 /* A string cached here will never be freed, so we don't need to worry about
  29    reference counting.  We just store the string, and then remember it in a
  30    hash so it can be looked up again. */
  31
  32 struct strcache {
  33   struct strcache *next;    /* The next block of strings.  */
  34   char *end;                /* Pointer to the beginning of the free space.  */
  35   int count;                /* # of strings in this buffer (for stats).  */
  36   int bytesfree;            /* The amount of the buffer that is free.  */
  37   char buffer[1];           /* The buffer comes after this.  */
  38 };
  39
  40 static int bufsize = CACHE_BUFFER_SIZE;
  41 static struct strcache *strcache = NULL;
  42
  43 /* Add a new buffer to the cache.  Add it at the front to reduce search time.
  44    This can also increase the overhead, since it's less likely that older
  45    buffers will be filled in.  However, GNU make has so many smaller strings
  46    that this doesn't seem to be much of an issue in practice.
  47  */
  48 static struct strcache *
  49 new_cache()
  50 {
  51   struct strcache *new;
  52   new = xmalloc (sizeof (*new) + bufsize);
  53   new->end = new->buffer;
  54   new->count = 0;
  55   new->bytesfree = bufsize;
  56
  57   new->next = strcache;
  58   strcache = new;
  59
  60   return new;
  61 }
  62
  63 static const char *
  64 add_string(const char *str, int len)
  65 {
  66   struct strcache *best = NULL;
  67   struct strcache *sp;
  68   const char *res;
  69
  70   /* If the string we want is too large to fit into a single buffer, then
  71      we're screwed; nothing will ever fit!  Change the maximum size of the
  72      cache to be big enough.  */
  73   if (len > bufsize)
  74     bufsize = len * 2;
  75
  76   /* First, find a cache with enough free space.  We always look through all
  77      the blocks and choose the one with the best fit (the one that leaves the
  78      least amount of space free).  */
  79   for (sp = strcache; sp != NULL; sp = sp->next)
  80     if (sp->bytesfree > len && (!best || best->bytesfree > sp->bytesfree))
  81       best = sp;
  82
  83   /* If nothing is big enough, make a new cache.  */
  84   if (!best)
  85     best = new_cache();
  86
  87   assert (best->bytesfree > len);
  88
  89   /* Add the string to the best cache.  */
  90   res = best->end;
  91   memcpy (best->end, str, len);
  92   best->end += len;
  93   *(best->end++) = '\0';
  94   best->bytesfree -= len + 1;
  95   ++best->count;
  96
  97   return res;
  98 }
  99
 100
 101 /* Hash table of strings in the cache.  */
 102
 103 static unsigned long
 104 str_hash_1 (const void *key)
 105 {
 106   return_ISTRING_HASH_1 ((const char *) key);
 107 }
 108
 109 static unsigned long
 110 str_hash_2 (const void *key)
 111 {
 112   return_ISTRING_HASH_2 ((const char *) key);
 113 }
 114
 115 static int
 116 str_hash_cmp (const void *x, const void *y)
 117 {
 118   return_ISTRING_COMPARE ((const char *) x, (const char *) y);
 119 }
 120
 121 static struct hash_table strings;
 122 static unsigned long total_adds = 0;
 123
 124 static const char *
 125 add_hash (const char *str, int len)
 126 {
 127   /* Look up the string in the hash.  If it's there, return it.  */
 128   char *const *slot = (char *const *) hash_find_slot (&strings, str);
 129   const char *key = *slot;
 130
 131   /* Count the total number of adds we performed.  */
 132   ++total_adds;
 133
 134   if (!HASH_VACANT (key))
 135     return key;
 136
 137   /* Not there yet so add it to a buffer, then into the hash table.  */
 138   key = add_string (str, len);
 139   hash_insert_at (&strings, key, slot);
 140   return key;
 141 }
 142
 143 /* Returns true if the string is in the cache; false if not.  */
 144 int
 145 strcache_iscached (const char *str)
 146 {
 147   struct strcache *sp;
 148
 149   for (sp = strcache; sp != 0; sp = sp->next)
 150     if (str >= sp->buffer && str < sp->end)
 151       return 1;
 152
 153   return 0;
 154 }
 155
 156 /* If the string is already in the cache, return a pointer to the cached
 157    version.  If not, add it then return a pointer to the cached version.
 158    Note we do NOT take control of the string passed in.  */
 159 const char *
 160 strcache_add (const char *str)
 161 {
 162   return add_hash (str, strlen (str));
 163 }
 164
 165 const char *
 166 strcache_add_len (const char *str, int len)
 167 {
 168   /* If we're not given a nul-terminated string we have to create one, because
 169      the hashing functions expect it.  */
 170   if (str[len] != '\0')
 171     {
 172       char *key = alloca (len + 1);
 173       memcpy (key, str, len);
 174       key[len] = '\0';
 175       str = key;
 176     }
 177
 178   return add_hash (str, len);
 179 }
 180
 181 int
 182 strcache_setbufsize(int size)
 183 {
 184   if (size > bufsize)
 185     bufsize = size;
 186   return bufsize;
 187 }
 188
 189 void
 190 strcache_init (void)
 191 {
 192   hash_init (&strings, 8000, str_hash_1, str_hash_2, str_hash_cmp);
 193 }
 194
 195
 196 /* Generate some stats output.  */
 197
 198 void
 199 strcache_print_stats (const char *prefix)
 200 {
 201   int numbuffs = 0, numstrs = 0;
 202   int totsize = 0, avgsize, maxsize = 0, minsize = bufsize;
 203   int totfree = 0, avgfree, maxfree = 0, minfree = bufsize;
 204   int lastused = 0, lastfree = 0;
 205
 206   if (strcache)
 207     {
 208       const struct strcache *sp;
 209
 210       /* Count the first buffer separately since it's not full.  */
 211       lastused = strcache->end - strcache->buffer;
 212       lastfree = strcache->bytesfree;
 213
 214       for (sp = strcache->next; sp != NULL; sp = sp->next)
 215         {
 216           int bf = sp->bytesfree;
 217           int sz = sp->end - sp->buffer;
 218
 219           ++numbuffs;
 220           numstrs += sp->count;
 221
 222           totsize += sz;
 223           maxsize = (sz > maxsize ? sz : maxsize);
 224           minsize = (sz < minsize ? sz : minsize);
 225
 226           totfree += bf;
 227           maxfree = (bf > maxfree ? bf : maxfree);
 228           minfree = (bf < minfree ? bf : minfree);
 229         }
 230     }
 231
 232   avgsize = numbuffs ? (int)(totsize / numbuffs) : 0;
 233   avgfree = numbuffs ? (int)(totfree / numbuffs) : 0;
 234
 235   printf (_("\n%s # of strings in strcache: %d / lookups = %lu / hits = %lu\n"),
 236           prefix, numstrs, total_adds, (total_adds - numstrs));
 237   printf (_("%s # of strcache buffers: %d (* %d B/buffer = %d B)\n"),
 238           prefix, (numbuffs + 1), bufsize, ((numbuffs + 1) * bufsize));
 239   printf (_("%s strcache used: total = %d (%d) / max = %d / min = %d / avg = %d\n"),
 240           prefix, totsize, lastused, maxsize, minsize, avgsize);
 241   printf (_("%s strcache free: total = %d (%d) / max = %d / min = %d / avg = %d\n"),
 242           prefix, totfree, lastfree, maxfree, minfree, avgfree);
 243
 244   fputs (_("\n# strcache hash-table stats:\n# "), stdout);
 245   hash_print_stats (&strings, stdout);
 246 }