summaryrefslogtreecommitdiff
path: root/strcache.c
blob: ff6a2d1fd4be414509ebad399d2390b089db41fc (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
/* Constant string caching for GNU Make.
Copyright (C) 2006-2013 Free Software Foundation, Inc.
This file is part of GNU Make.

GNU Make is free software; you can redistribute it and/or modify it under the
terms of the GNU General Public License as published by the Free Software
Foundation; either version 3 of the License, or (at your option) any later
version.

GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
A PARTICULAR PURPOSE.  See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with
this program.  If not, see <http://www.gnu.org/licenses/>.  */

#include "makeint.h"

#include <stddef.h>
#include <assert.h>

#include "hash.h"

/* A string cached here will never be freed, so we don't need to worry about
   reference counting.  We just store the string, and then remember it in a
   hash so it can be looked up again. */

typedef unsigned short int sc_buflen_t;

struct strcache {
  struct strcache *next;    /* The next block of strings.  Must be first!  */
  sc_buflen_t end;          /* Offset to the beginning of free space.  */
  sc_buflen_t bytesfree;    /* Free space left in this buffer.  */
  sc_buflen_t count;        /* # of strings in this buffer (for stats).  */
  char buffer[1];           /* The buffer comes after this.  */
};

/* The size (in bytes) of each cache buffer.
   Try to pick something that will map well into the heap.
   This must be able to be represented by a short int (<=65535).  */
#define CACHE_BUFFER_BASE       (8192)
#define CACHE_BUFFER_ALLOC(_s)  ((_s) - (2 * sizeof (size_t)))
#define CACHE_BUFFER_OFFSET     (offsetof (struct strcache, buffer))
#define CACHE_BUFFER_SIZE(_s)   (CACHE_BUFFER_ALLOC(_s) - CACHE_BUFFER_OFFSET)

static sc_buflen_t bufsize = CACHE_BUFFER_SIZE (CACHE_BUFFER_BASE);
static struct strcache *strcache = NULL;
static struct strcache *fullcache = NULL;

static unsigned long total_buffers = 0;
static unsigned long total_strings = 0;
static unsigned long total_size = 0;

/* Add a new buffer to the cache.  Add it at the front to reduce search time.
   This can also increase the overhead, since it's less likely that older
   buffers will be filled in.  However, GNU make has so many smaller strings
   that this doesn't seem to be much of an issue in practice.
 */
static struct strcache *
new_cache ()
{
  struct strcache *new;
  new = xmalloc (bufsize + CACHE_BUFFER_OFFSET);
  new->end = 0;
  new->count = 0;
  new->bytesfree = bufsize;

  new->next = strcache;
  strcache = new;

  ++total_buffers;
  return new;
}

static const char *
add_string (const char *str, unsigned int len)
{
  char *res;
  struct strcache *sp;
  struct strcache **spp = &strcache;
  /* We need space for the nul char.  */
  unsigned int sz = len + 1;

  /* If the string we want is too large to fit into a single buffer, then
     no existing cache is large enough.  Change the maximum size.  */
  if (sz > bufsize)
    bufsize = CACHE_BUFFER_SIZE ((((sz + 1) / CACHE_BUFFER_BASE) + 1)
                                 * CACHE_BUFFER_BASE);
  else
    /* Find the first cache with enough free space.  */
    for (; *spp != NULL; spp = &(*spp)->next)
      if ((*spp)->bytesfree > sz)
        break;

  /* If nothing is big enough, make a new cache.  */
  sp = *spp;
  if (sp == NULL)
    {
      sp = new_cache ();
      spp = &sp;
    }

  /* Add the string to this cache.  */
  res = &sp->buffer[sp->end];
  memmove (res, str, len);
  res[len] = '\0';
  sp->end += sz;
  sp->bytesfree -= sz;
  ++sp->count;

  /* If the amount free in this cache is less than the average string size,
     consider it full and move it to the full list.  */
  ++total_strings;
  total_size += sz;

  if (sp->bytesfree < (total_size / total_strings) + 1)
    {
      *spp = (*spp)->next;
      sp->next = fullcache;
      fullcache = sp;
    }

  return res;
}


/* Hash table of strings in the cache.  */

static unsigned long
str_hash_1 (const void *key)
{
  return_ISTRING_HASH_1 ((const char *) key);
}

static unsigned long
str_hash_2 (const void *key)
{
  return_ISTRING_HASH_2 ((const char *) key);
}

static int
str_hash_cmp (const void *x, const void *y)
{
  return_ISTRING_COMPARE ((const char *) x, (const char *) y);
}

static struct hash_table strings;
static unsigned long total_adds = 0;

static const char *
add_hash (const char *str, int len)
{
  /* Look up the string in the hash.  If it's there, return it.  */
  char *const *slot = (char *const *) hash_find_slot (&strings, str);
  const char *key = *slot;

  /* Count the total number of add operations we performed.  */
  ++total_adds;

  if (!HASH_VACANT (key))
    return key;

  /* Not there yet so add it to a buffer, then into the hash table.  */
  key = add_string (str, len);
  hash_insert_at (&strings, key, slot);
  return key;
}

/* Returns true if the string is in the cache; false if not.  */
int
strcache_iscached (const char *str)
{
  struct strcache *sp;

  for (sp = strcache; sp != 0; sp = sp->next)
    if (str >= sp->buffer && str < sp->buffer + sp->end)
      return 1;
  for (sp = fullcache; sp != 0; sp = sp->next)
    if (str >= sp->buffer && str < sp->buffer + sp->end)
      return 1;

  return 0;
}

/* If the string is already in the cache, return a pointer to the cached
   version.  If not, add it then return a pointer to the cached version.
   Note we do NOT take control of the string passed in.  */
const char *
strcache_add (const char *str)
{
  return add_hash (str, strlen (str));
}

const char *
strcache_add_len (const char *str, unsigned int len)
{
  /* If we're not given a nul-terminated string we have to create one, because
     the hashing functions expect it.  */
  if (str[len] != '\0')
    {
      char *key = alloca (len + 1);
      memcpy (key, str, len);
      key[len] = '\0';
      str = key;
    }

  return add_hash (str, len);
}

int
strcache_setbufsize (unsigned int size)
{
  if (size > bufsize)
    bufsize = size;
  return bufsize;
}

void
strcache_init (void)
{
  hash_init (&strings, 8000, str_hash_1, str_hash_2, str_hash_cmp);
}


/* Generate some stats output.  */

void
strcache_print_stats (const char *prefix)
{
  const struct strcache *sp;
  unsigned long numbuffs = 0, fullbuffs = 0;
  unsigned long totfree = 0, maxfree = 0, minfree = bufsize;

  if (! strcache)
    {
      printf (_("\n%s No strcache buffers\n"), prefix);
      return;
    }

  /* Count the first buffer separately since it's not full.  */
  for (sp = strcache->next; sp != NULL; sp = sp->next)
    {
      sc_buflen_t bf = sp->bytesfree;

      totfree += bf;
      maxfree = (bf > maxfree ? bf : maxfree);
      minfree = (bf < minfree ? bf : minfree);

      ++numbuffs;
    }
  for (sp = fullcache; sp != NULL; sp = sp->next)
    {
      sc_buflen_t bf = sp->bytesfree;

      totfree += bf;
      maxfree = (bf > maxfree ? bf : maxfree);
      minfree = (bf < minfree ? bf : minfree);

      ++numbuffs;
      ++fullbuffs;
    }

  /* Make sure we didn't lose any buffers.  */
  assert (total_buffers == numbuffs + 1);

  printf (_("\n%s strcache buffers: %lu (%lu) / strings = %lu / storage = %lu B / avg = %lu B\n"),
          prefix, numbuffs + 1, fullbuffs, total_strings, total_size,
          (total_size / total_strings));

  printf (_("%s current buf: size = %hu B / used = %hu B / count = %hu / avg = %hu B\n"),
          prefix, bufsize, strcache->end, strcache->count,
          (strcache->end / strcache->count));

  if (numbuffs)
    {
      unsigned long sz = total_size - bufsize;
      unsigned long cnt = total_strings - strcache->count;
      sc_buflen_t avgfree = totfree / numbuffs;

      printf (_("%s other used: total = %lu B / count = %lu / avg = %lu B\n"),
              prefix, sz, cnt, sz / cnt);

      printf (_("%s other free: total = %lu B / max = %lu B / min = %lu B / avg = %hu B\n"),
              prefix, totfree, maxfree, minfree, avgfree);
    }

  printf (_("\n%s strcache performance: lookups = %lu / hit rate = %lu%%\n"),
          prefix, total_adds, (long unsigned)(100.0 * (total_adds - total_strings) / total_adds));
  fputs (_("# hash-table stats:\n# "), stdout);
  hash_print_stats (&strings, stdout);
}