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 }