1 /* Copyright (C) 1996, 2000 Aladdin Enterprises. All rights reserved.
2
3 This software is provided AS-IS with no warranty, either express or
4 implied.
5
6 This software is distributed under license and may not be copied,
7 modified or distributed except as expressly authorized under the terms
8 of the license contained in the file LICENSE in this distribution.
9
10 For more information about licensing, please refer to
11 http://www.ghostscript.com/licensing/. For information on
12 commercial licensing, go to http://www.artifex.com/licensing/ or
13 contact Artifex Software, Inc., 101 Lucas Valley Road #110,
14 San Rafael, CA 94903, U.S.A., +1(415)492-9861.
15 */
16
17 /* $Id: gsnogc.c,v 1.10 2002/06/16 05:48:55 lpd Exp $ */
18 /* String freelist implementation and ersatz garbage collector */
19 #include "gx.h"
20 #include "gsmdebug.h"
21 #include "gsnogc.h"
22 #include "gsstruct.h"
23 #include "gxalloc.h"
24
25 /*
26 * We implement string freelists here, because they are only useful
27 * in non-garbage-collected environments.
28 */
29
30 /*
31 * Get and put unaligned 32-bit values. NOTE: these procedures must match
32 * the value of SFREE_NB defined in gxalloc.h.
33 */
34 #define NB SFREE_NB
35 #if NB == 4
36 private uint
get_uu32(const byte * ptr)37 get_uu32(const byte *ptr)
38 {
39 return (ptr[0] << 24) + (ptr[1] << 16) + (ptr[2] << 8) + ptr[3];
40 }
41 private void
put_uu32(byte * ptr,uint val)42 put_uu32(byte *ptr, uint val)
43 {
44 ptr[0] = val >> 24;
45 ptr[1] = (byte)(val >> 16);
46 ptr[2] = (byte)(val >> 8);
47 ptr[3] = (byte)val;
48 }
49 #endif /* otherwise, undefined procedures will give an error */
50
51 /* Allocate a string. */
52 /* Scan the current chunk's free list if the request is large enough. */
53 /* Currently we require an exact match of the block size. */
54 private byte *
sf_alloc_string(gs_memory_t * mem,uint nbytes,client_name_t cname)55 sf_alloc_string(gs_memory_t * mem, uint nbytes, client_name_t cname)
56 {
57 gs_ref_memory_t * const imem = (gs_ref_memory_t *)mem;
58
59 if (nbytes >= 40 && nbytes < imem->large_size) {
60 byte *base = csbase(&imem->cc);
61 byte *prev = 0;
62 uint offset = imem->cc.sfree;
63 uint next;
64 byte *ptr;
65
66 for (; offset != 0; prev = ptr, offset = next) {
67 ptr = base + offset;
68 next = get_uu32(ptr + NB);
69 if (get_uu32(ptr) != nbytes)
70 continue;
71 /* Take this block. */
72 if (prev == 0)
73 imem->cc.sfree = next;
74 else
75 put_uu32(prev + NB, next);
76 if_debug4('A', "[a%d:+>F]%s(%u) = 0x%lx\n", imem->space,
77 client_name_string(cname), nbytes, (ulong) ptr);
78 gs_alloc_fill(ptr, gs_alloc_fill_alloc, nbytes);
79 imem->lost.strings -= nbytes;
80 return ptr;
81 }
82 }
83 return (*gs_ref_memory_procs.alloc_string) (mem, nbytes, cname);
84 }
85
86 /* Free a string. */
87 private void
sf_free_string(gs_memory_t * mem,byte * str,uint size,client_name_t cname)88 sf_free_string(gs_memory_t * mem, byte * str, uint size, client_name_t cname)
89 {
90 gs_ref_memory_t * const imem = (gs_ref_memory_t *)mem;
91 chunk_t *cp;
92 uint str_offset;
93
94 if (str == imem->cc.ctop) {
95 if_debug4('A', "[a%d:-> ]%s(%u) 0x%lx\n", imem->space,
96 client_name_string(cname), size, (ulong) str);
97 imem->cc.ctop += size;
98 gs_alloc_fill(str, gs_alloc_fill_free, size);
99 return;
100 }
101 if_debug4('A', "[a%d:->#]%s(%u) 0x%lx\n", imem->space,
102 client_name_string(cname), size, (ulong) str);
103 imem->lost.strings += size;
104 if (ptr_is_in_chunk(str, &imem->cc)) {
105 cp = &imem->cc;
106 /* We already tested for the string being at ctop. */
107 } else {
108 chunk_locator_t loc;
109
110 loc.memory = imem;
111 loc.cp = imem->clast;
112 if (!chunk_locate_ptr(str, &loc))
113 return; /* something is probably wrong.... */
114 cp = loc.cp;
115 if (str == cp->ctop) {
116 cp->ctop += size;
117 return;
118 }
119 }
120 str_offset = str - csbase(cp);
121 if (size >= 2 * NB) {
122 byte *prev;
123 uint next;
124
125 put_uu32(str, size);
126 if (cp->sfree == 0 || str_offset < cp->sfree) {
127 /* Put the string at the head of the free list. */
128 put_uu32(str + NB, cp->sfree);
129 cp->sfree = str_offset;
130 return;
131 }
132 /* Insert the new string in address order. */
133 prev = csbase(cp) + cp->sfree;
134 #ifdef DEBUG
135 if (gs_debug_c('?')) {
136 if (prev < str + size && prev + get_uu32(prev) > str) {
137 lprintf4("freeing string 0x%lx(%u), overlaps 0x%lx(%u)!\n",
138 (ulong) str, size, (ulong) prev, get_uu32(prev));
139 return;
140 }
141 }
142 #endif
143 for (;;) {
144 next = get_uu32(prev + NB);
145 #ifdef DEBUG
146 if (gs_debug_c('?') && next != 0) {
147 byte *pnext = csbase(cp) + next;
148
149 if (pnext < str + size && pnext + get_uu32(pnext) > str) {
150 lprintf4("freeing string 0x%lx(%u), overlaps 0x%lx(%u)!\n",
151 (ulong) str, size, (ulong) pnext, get_uu32(pnext));
152 return;
153 }
154 }
155 #endif
156 if (next >= str_offset || next == 0)
157 break;
158 prev = csbase(cp) + next;
159 }
160 put_uu32(str + NB, next);
161 put_uu32(prev + NB, str_offset);
162 gs_alloc_fill(str + 2 * NB, gs_alloc_fill_free, size - 2 * NB);
163 } else {
164 /*
165 * Insert the string in the 1-byte free list(s). Note that
166 * if it straddles a 256-byte block, we need to do this twice.
167 */
168 uint *pfree1 = &cp->sfree1[str_offset >> 8];
169 uint count = size;
170 byte *prev;
171 byte *ptr;
172
173 if (*pfree1 == 0) {
174 *str = 0;
175 *pfree1 = str_offset;
176 if (!--count)
177 return;
178 prev = str;
179 ptr = str + 1;
180 } else if (str_offset < *pfree1) {
181 *str = *pfree1 - str_offset;
182 *pfree1 = str_offset;
183 if (!--count)
184 return;
185 prev = str;
186 ptr = str + 1;
187 } else {
188 uint next;
189
190 prev = csbase(cp) + *pfree1;
191 while ((next = *prev) != 0 && prev + next < str)
192 prev += next;
193 ptr = str;
194 }
195 for (;;) {
196 /*
197 * Invariants:
198 * ptr == str + size - count
199 * prev < sfbase + str_offset
200 * *prev == 0 || prev + *prev > sfbase + str_offset
201 */
202 *ptr = (*prev == 0 ? 0 : prev + *prev - ptr);
203 *prev = ptr - prev;
204 if (!--count)
205 break;
206 prev = ptr++;
207 if (!(++str_offset & 255)) {
208 /* Move to the next block of 256 bytes. */
209 ++pfree1;
210 *ptr = (byte) * pfree1;
211 *pfree1 = str_offset;
212 if (!--count)
213 break;
214 prev = ptr++;
215 ++str_offset;
216 }
217 }
218 }
219 }
220
221 /* Enable or disable freeing. */
222 private void
sf_enable_free(gs_memory_t * mem,bool enable)223 sf_enable_free(gs_memory_t * mem, bool enable)
224 {
225 (*gs_ref_memory_procs.enable_free) (mem, enable);
226 if (enable)
227 mem->procs.free_string = sf_free_string;
228 }
229
230 /* Merge free strings at the bottom of a chunk's string storage. */
231 private void
sf_merge_strings(chunk_t * cp)232 sf_merge_strings(chunk_t * cp)
233 {
234 for (;;) {
235 byte *ctop = cp->ctop;
236 uint top_offset = ctop - csbase(cp);
237 uint *pfree1;
238
239 if (cp->sfree == top_offset) { /* Merge a large free block. */
240 cp->sfree = get_uu32(ctop + NB);
241 cp->ctop += get_uu32(ctop);
242 continue;
243 }
244 if (!cp->sfree1)
245 break;
246 pfree1 = &cp->sfree1[top_offset >> 8];
247 if (*pfree1 != top_offset)
248 break;
249 /* Merge a small (1-byte) free block. */
250 *pfree1 = (*ctop ? *pfree1 + *ctop : 0);
251 cp->ctop++;
252 }
253 }
254
255 /* Consolidate free space. */
256 private void
sf_consolidate_free(gs_memory_t * mem)257 sf_consolidate_free(gs_memory_t *mem)
258 {
259 gs_ref_memory_t *imem = (gs_ref_memory_t *)mem;
260 chunk_t *cp;
261
262 alloc_close_chunk(imem);
263 for (cp = imem->clast; cp != 0; cp = cp->cprev) {
264 byte *top = cp->ctop;
265
266 sf_merge_strings(cp);
267 imem->lost.strings -= cp->ctop - top;
268 if (cp->ctop == cp->climit && cp->smark_size != 0) {
269 /*
270 * No string space is being used. Since we are not using the
271 * 'string marking table' for GC, we can recover its space by
272 * deleting the smark area, setting smark_size = 0, and sliding
273 * up ctop and climit. We also need to recompute the size of
274 * the string freelist area (it will be larger, since the
275 * space potentially allocated to strings is larger).
276 */
277 cp->smark_size = 0;
278 cp->smark = 0;
279 /*
280 * Reserve enough space for the string freelist all the way to
281 * cend even though the climit will be moved to before the
282 * freelist area. This recovers most of the space.
283 */
284 cp->climit = cp->cend;
285 cp->climit -= STRING_FREELIST_SPACE(cp);
286 cp->ctop = cp->climit;
287 alloc_init_free_strings(cp);
288 }
289 }
290 alloc_open_chunk(imem);
291
292 /* Merge free objects, detecting entirely free chunks. */
293 ialloc_consolidate_free(imem);
294 }
295
296 /*
297 * This procedure has the same API as the garbage collector used by the
298 * PostScript interpreter, but it is designed to be used in environments
299 * that don't need garbage collection and don't use save/restore. All it
300 * does is coalesce free blocks at the high end of the object area of each
301 * chunk, and free strings at the low end of the string area, and then if
302 * not 'controlled' memory, free completely empty chunks.
303 *
304 * Note that any string marking area will be added to the free space
305 * within the chunk if possible.
306 */
307
308 private void use_string_freelists(gs_ref_memory_t *mem);
309 void
gs_nogc_reclaim(vm_spaces * pspaces,bool global)310 gs_nogc_reclaim(vm_spaces * pspaces, bool global)
311 {
312 int space;
313 gs_ref_memory_t *mem_prev = 0;
314
315 for (space = 0; space < countof(pspaces->memories.indexed); ++space) {
316 gs_ref_memory_t *mem = pspaces->memories.indexed[space];
317
318 if (mem == 0 || mem == mem_prev)
319 continue;
320 mem_prev = mem;
321 use_string_freelists(mem);
322 if (mem->stable_memory != (gs_memory_t *)mem &&
323 mem->stable_memory != 0
324 )
325 use_string_freelists((gs_ref_memory_t *)mem->stable_memory);
326 }
327 }
328 #ifdef VMS
329 #pragma optimize ansi_alias=off
330 #endif
331 private void
use_string_freelists(gs_ref_memory_t * rmem)332 use_string_freelists(gs_ref_memory_t *rmem)
333 {
334 /*
335 * ANSI made an incompatible change to the C language standard that
336 * caused the following to generate aliasing warnings:
337 gs_memory_t *mem = (gs_memory_t *)rmem;
338 * Consequently, we now use rmem rather than mem in the assignments
339 * below, even though this degrades code readability by obscuring the
340 * fact that they are only manipulating fields of the more abstract
341 * superclass.
342 * For OpenVMS this still gets us a warning so we switch the warning
343 * message off.
344 */
345 #ifdef VMS
346 #pragma message disable BADANSIALIAS
347 #endif
348
349 /* Change the allocator to use string freelists in the future. */
350 rmem->procs.alloc_string = sf_alloc_string;
351 if (rmem->procs.free_string != gs_ignore_free_string)
352 rmem->procs.free_string = sf_free_string;
353 rmem->procs.enable_free = sf_enable_free;
354 rmem->procs.consolidate_free = sf_consolidate_free;
355
356 /* Merge free objects, detecting entirely free chunks. */
357 gs_consolidate_free((gs_memory_t *)rmem);
358 }
359