1 /* Copyright (C) 1995, 1996, 1997, 1998, 1999, 2000 artofcode LLC. All rights reserved.
2
3 This program is free software; you can redistribute it and/or modify it
4 under the terms of the GNU General Public License as published by the
5 Free Software Foundation; either version 2 of the License, or (at your
6 option) any later version.
7
8 This program is distributed in the hope that it will be useful, but
9 WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 General Public License for more details.
12
13 You should have received a copy of the GNU General Public License along
14 with this program; if not, write to the Free Software Foundation, Inc.,
15 59 Temple Place, Suite 330, Boston, MA, 02111-1307.
16
17 */
18
19 /*$Id: ilocate.c,v 1.4.2.1.2.1 2003/01/17 00:49:04 giles Exp $ */
20 /* Object locating and validating for Ghostscript memory manager */
21 #include "ghost.h"
22 #include "memory_.h"
23 #include "errors.h"
24 #include "gsexit.h"
25 #include "gsstruct.h"
26 #include "iastate.h"
27 #include "idict.h"
28 #include "igc.h" /* for gc_state_t */
29 #include "igcstr.h" /* for prototype */
30 #include "iname.h"
31 #include "ipacked.h"
32 #include "isstate.h"
33 #include "iutil.h" /* for packed_get */
34 #include "ivmspace.h"
35 #include "store.h"
36
37 /* ================ Locating ================ */
38
39 /* Locate a pointer in the chunks of a space being collected. */
40 /* This is only used for string garbage collection and for debugging. */
41 chunk_t *
gc_locate(const void * ptr,gc_state_t * gcst)42 gc_locate(const void *ptr, gc_state_t * gcst)
43 {
44 const gs_ref_memory_t *mem;
45 const gs_ref_memory_t *other;
46
47 if (chunk_locate(ptr, &gcst->loc))
48 return gcst->loc.cp;
49 mem = gcst->loc.memory;
50
51 /*
52 * Try the stable allocator of this space, or, if the current memory
53 * is the stable one, the non-stable allocator of this space.
54 */
55
56 if ((other = (const gs_ref_memory_t *)mem->stable_memory) != mem ||
57 (other = gcst->spaces_indexed[mem->space >> r_space_shift]) != mem
58 ) {
59 gcst->loc.memory = other;
60 gcst->loc.cp = 0;
61 if (chunk_locate(ptr, &gcst->loc))
62 return gcst->loc.cp;
63 }
64
65 /*
66 * Try the other space, if there is one, including its stable allocator
67 * and all save levels. (If the original space is system space, try
68 * local space.)
69 */
70
71 if (gcst->space_local != gcst->space_global) {
72 gcst->loc.memory = other =
73 (mem->space == avm_local ? gcst->space_global : gcst->space_local);
74 gcst->loc.cp = 0;
75 if (chunk_locate(ptr, &gcst->loc))
76 return gcst->loc.cp;
77 /* Try its stable allocator. */
78 if (other->stable_memory != (const gs_memory_t *)other) {
79 gcst->loc.memory = (gs_ref_memory_t *)other->stable_memory;
80 gcst->loc.cp = 0;
81 if (chunk_locate(ptr, &gcst->loc))
82 return gcst->loc.cp;
83 gcst->loc.memory = other;
84 }
85 /* Try other save levels of this space. */
86 while (gcst->loc.memory->saved != 0) {
87 gcst->loc.memory = &gcst->loc.memory->saved->state;
88 gcst->loc.cp = 0;
89 if (chunk_locate(ptr, &gcst->loc))
90 return gcst->loc.cp;
91 }
92 }
93
94 /*
95 * Try system space. This is simpler because it isn't subject to
96 * save/restore and doesn't have a separate stable allocator.
97 */
98
99 if (mem != gcst->space_system) {
100 gcst->loc.memory = gcst->space_system;
101 gcst->loc.cp = 0;
102 if (chunk_locate(ptr, &gcst->loc))
103 return gcst->loc.cp;
104 }
105
106 /*
107 * Try other save levels of the initial space, or of global space if the
108 * original space was system space. In the latter case, try all
109 * levels, and its stable allocator.
110 */
111
112 switch (mem->space) {
113 default: /* system */
114 other = gcst->space_global;
115 if (other->stable_memory != (const gs_memory_t *)other) {
116 gcst->loc.memory = (gs_ref_memory_t *)other->stable_memory;
117 gcst->loc.cp = 0;
118 if (chunk_locate(ptr, &gcst->loc))
119 return gcst->loc.cp;
120 }
121 gcst->loc.memory = other;
122 break;
123 case avm_global:
124 gcst->loc.memory = gcst->space_global;
125 break;
126 case avm_local:
127 gcst->loc.memory = gcst->space_local;
128 break;
129 }
130 for (;;) {
131 if (gcst->loc.memory != mem) { /* don't do twice */
132 gcst->loc.cp = 0;
133 if (chunk_locate(ptr, &gcst->loc))
134 return gcst->loc.cp;
135 }
136 if (gcst->loc.memory->saved == 0)
137 break;
138 gcst->loc.memory = &gcst->loc.memory->saved->state;
139 }
140
141 /* Restore locator to a legal state and report failure. */
142
143 gcst->loc.memory = mem;
144 gcst->loc.cp = 0;
145 return 0;
146 }
147
148 /* ================ Debugging ================ */
149
150 #ifdef DEBUG
151
152 /* Define the structure for temporarily saving allocator state. */
153 typedef struct alloc_temp_save_s {
154 chunk_t cc;
155 uint rsize;
156 ref rlast;
157 } alloc_temp_save_t;
158 /* Temporarily save the state of an allocator. */
159 private void
alloc_temp_save(alloc_temp_save_t * pats,gs_ref_memory_t * mem)160 alloc_temp_save(alloc_temp_save_t *pats, gs_ref_memory_t *mem)
161 {
162 chunk_t *pcc = mem->pcc;
163 obj_header_t *rcur = mem->cc.rcur;
164
165 if (pcc != 0) {
166 pats->cc = *pcc;
167 *pcc = mem->cc;
168 }
169 if (rcur != 0) {
170 pats->rsize = rcur[-1].o_size;
171 rcur[-1].o_size = mem->cc.rtop - (byte *) rcur;
172 /* Create the final ref, reserved for the GC. */
173 pats->rlast = ((ref *) mem->cc.rtop)[-1];
174 make_mark((ref *) mem->cc.rtop - 1);
175 }
176 }
177 /* Restore the temporarily saved state. */
178 private void
alloc_temp_restore(alloc_temp_save_t * pats,gs_ref_memory_t * mem)179 alloc_temp_restore(alloc_temp_save_t *pats, gs_ref_memory_t *mem)
180 {
181 chunk_t *pcc = mem->pcc;
182 obj_header_t *rcur = mem->cc.rcur;
183
184 if (rcur != 0) {
185 rcur[-1].o_size = pats->rsize;
186 ((ref *) mem->cc.rtop)[-1] = pats->rlast;
187 }
188 if (pcc != 0)
189 *pcc = pats->cc;
190 }
191
192 /* Validate the contents of an allocator. */
193 void
ialloc_validate_spaces(const gs_dual_memory_t * dmem)194 ialloc_validate_spaces(const gs_dual_memory_t * dmem)
195 {
196 int i;
197 gc_state_t state;
198 alloc_temp_save_t
199 save[countof(dmem->spaces_indexed)],
200 save_stable[countof(dmem->spaces_indexed)];
201 gs_ref_memory_t *mem;
202
203 state.spaces = dmem->spaces;
204 state.loc.memory = state.space_local;
205 state.loc.cp = 0;
206
207 /* Save everything we need to reset temporarily. */
208
209 for (i = 0; i < countof(save); i++)
210 if ((mem = dmem->spaces_indexed[i]) != 0) {
211 alloc_temp_save(&save[i], mem);
212 if (mem->stable_memory != (gs_memory_t *)mem)
213 alloc_temp_save(&save_stable[i],
214 (gs_ref_memory_t *)mem->stable_memory);
215 }
216
217 /* Validate memory. */
218
219 for (i = 0; i < countof(save); i++)
220 if ((mem = dmem->spaces_indexed[i]) != 0) {
221 ialloc_validate_memory(mem, &state);
222 if (mem->stable_memory != (gs_memory_t *)mem)
223 ialloc_validate_memory((gs_ref_memory_t *)mem->stable_memory,
224 &state);
225 }
226
227 /* Undo temporary changes. */
228
229 for (i = 0; i < countof(save); i++)
230 if ((mem = dmem->spaces_indexed[i]) != 0) {
231 if (mem->stable_memory != (gs_memory_t *)mem)
232 alloc_temp_restore(&save_stable[i],
233 (gs_ref_memory_t *)mem->stable_memory);
234 alloc_temp_restore(&save[i], mem);
235 }
236 }
237 void
ialloc_validate_memory(const gs_ref_memory_t * mem,gc_state_t * gcst)238 ialloc_validate_memory(const gs_ref_memory_t * mem, gc_state_t * gcst)
239 {
240 const gs_ref_memory_t *smem;
241 int level;
242
243 for (smem = mem, level = 0; smem != 0;
244 smem = &smem->saved->state, --level
245 ) {
246 const chunk_t *cp;
247 int i;
248
249 if_debug3('6', "[6]validating memory 0x%lx, space %d, level %d\n",
250 (ulong) mem, mem->space, level);
251 /* Validate chunks. */
252 for (cp = smem->cfirst; cp != 0; cp = cp->cnext)
253 ialloc_validate_chunk(cp, gcst);
254 /* Validate freelists. */
255 for (i = 0; i < num_freelists; ++i) {
256 uint free_size = i << log2_obj_align_mod;
257 const obj_header_t *pfree;
258
259 for (pfree = mem->freelists[i]; pfree != 0;
260 pfree = *(const obj_header_t * const *)pfree
261 ) {
262 uint size = pfree[-1].o_size;
263
264 if (pfree[-1].o_type != &st_free) {
265 lprintf3("Non-free object 0x%lx(%u) on freelist %i!\n",
266 (ulong) pfree, size, i);
267 break;
268 }
269 if ((i == LARGE_FREELIST_INDEX && size < max_freelist_size) ||
270 (i != LARGE_FREELIST_INDEX &&
271 (size < free_size - obj_align_mask || size > free_size))) {
272 lprintf3("Object 0x%lx(%u) size wrong on freelist %i!\n",
273 (ulong) pfree, size, i);
274 break;
275 }
276 }
277 }
278 };
279 }
280
281 /* Check the validity of an object's size. */
282 inline private bool
object_size_valid(const obj_header_t * pre,uint size,const chunk_t * cp)283 object_size_valid(const obj_header_t * pre, uint size, const chunk_t * cp)
284 {
285 return (pre->o_alone ? (const byte *)pre == cp->cbase :
286 size <= cp->ctop - (const byte *)(pre + 1));
287 }
288
289 /* Validate all the objects in a chunk. */
290 private void ialloc_validate_ref(P2(const ref *, gc_state_t *));
291 private void ialloc_validate_ref_packed(P2(const ref_packed *, gc_state_t *));
292 void
ialloc_validate_chunk(const chunk_t * cp,gc_state_t * gcst)293 ialloc_validate_chunk(const chunk_t * cp, gc_state_t * gcst)
294 {
295 if_debug_chunk('6', "[6]validating chunk", cp);
296 SCAN_CHUNK_OBJECTS(cp);
297 DO_ALL
298 if (pre->o_type == &st_free) {
299 if (!object_size_valid(pre, size, cp))
300 lprintf3("Bad free object 0x%lx(%lu), in chunk 0x%lx!\n",
301 (ulong) (pre + 1), (ulong) size, (ulong) cp);
302 } else
303 ialloc_validate_object(pre + 1, cp, gcst);
304 if_debug3('7', " [7]validating %s(%lu) 0x%lx\n",
305 struct_type_name_string(pre->o_type),
306 (ulong) size, (ulong) pre);
307 if (pre->o_type == &st_refs) {
308 const ref_packed *rp = (const ref_packed *)(pre + 1);
309 const char *end = (const char *)rp + size;
310
311 while ((const char *)rp < end) {
312 ialloc_validate_ref_packed(rp, gcst);
313 rp = packed_next(rp);
314 }
315 } else {
316 struct_proc_enum_ptrs((*proc)) = pre->o_type->enum_ptrs;
317 uint index = 0;
318 enum_ptr_t eptr;
319 gs_ptr_type_t ptype;
320
321 if (proc != gs_no_struct_enum_ptrs)
322 for (; (ptype = (*proc) (pre + 1, size, index, &eptr, pre->o_type, NULL)) != 0; ++index)
323 if (eptr.ptr == 0)
324 DO_NOTHING;
325 else if (ptype == ptr_struct_type)
326 ialloc_validate_object(eptr.ptr, NULL, gcst);
327 else if (ptype == ptr_ref_type)
328 ialloc_validate_ref_packed(eptr.ptr, gcst);
329 }
330 END_OBJECTS_SCAN
331 }
332 /* Validate a ref. */
333 private void
ialloc_validate_ref_packed(const ref_packed * rp,gc_state_t * gcst)334 ialloc_validate_ref_packed(const ref_packed * rp, gc_state_t * gcst)
335 {
336 if (r_is_packed(rp)) {
337 ref unpacked;
338
339 packed_get(rp, &unpacked);
340 ialloc_validate_ref(&unpacked, gcst);
341 } else {
342 ialloc_validate_ref((const ref *)rp, gcst);
343 }
344 }
345 private void
ialloc_validate_ref(const ref * pref,gc_state_t * gcst)346 ialloc_validate_ref(const ref * pref, gc_state_t * gcst)
347 {
348 const void *optr;
349 const ref *rptr;
350 const char *tname;
351 uint size;
352
353 if (!gs_debug_c('?'))
354 return; /* no check */
355 if (r_space(pref) == avm_foreign)
356 return;
357 switch (r_type(pref)) {
358 case t_file:
359 optr = pref->value.pfile;
360 goto cks;
361 case t_device:
362 optr = pref->value.pdevice;
363 goto cks;
364 case t_fontID:
365 case t_struct:
366 case t_astruct:
367 optr = pref->value.pstruct;
368 cks: if (optr != 0)
369 ialloc_validate_object(optr, NULL, gcst);
370 break;
371 case t_name:
372 if (name_index_ptr(name_index(pref)) != pref->value.pname) {
373 lprintf3("At 0x%lx, bad name %u, pname = 0x%lx\n",
374 (ulong) pref, (uint)name_index(pref),
375 (ulong) pref->value.pname);
376 break;
377 } {
378 ref sref;
379
380 name_string_ref(pref, &sref);
381 if (r_space(&sref) != avm_foreign &&
382 !gc_locate(sref.value.const_bytes, gcst)
383 ) {
384 lprintf4("At 0x%lx, bad name %u, pname = 0x%lx, string 0x%lx not in any chunk\n",
385 (ulong) pref, (uint) r_size(pref),
386 (ulong) pref->value.pname,
387 (ulong) sref.value.const_bytes);
388 }
389 }
390 break;
391 case t_string:
392 if (r_size(pref) != 0 && !gc_locate(pref->value.bytes, gcst))
393 lprintf3("At 0x%lx, string ptr 0x%lx[%u] not in any chunk\n",
394 (ulong) pref, (ulong) pref->value.bytes,
395 (uint) r_size(pref));
396 break;
397 case t_array:
398 if (r_size(pref) == 0)
399 break;
400 rptr = pref->value.refs;
401 size = r_size(pref);
402 tname = "array";
403 cka: if (!gc_locate(rptr, gcst)) {
404 lprintf3("At 0x%lx, %s 0x%lx not in any chunk\n",
405 (ulong) pref, tname, (ulong) rptr);
406 break;
407 } {
408 uint i;
409
410 for (i = 0; i < size; ++i) {
411 const ref *elt = rptr + i;
412
413 if (r_is_packed(elt))
414 lprintf5("At 0x%lx, %s 0x%lx[%u] element %u is not a ref\n",
415 (ulong) pref, tname, (ulong) rptr, size, i);
416 }
417 }
418 break;
419 case t_shortarray:
420 case t_mixedarray:
421 if (r_size(pref) == 0)
422 break;
423 optr = pref->value.packed;
424 if (!gc_locate(optr, gcst))
425 lprintf2("At 0x%lx, packed array 0x%lx not in any chunk\n",
426 (ulong) pref, (ulong) optr);
427 break;
428 case t_dictionary:
429 {
430 const dict *pdict = pref->value.pdict;
431
432 if (!r_has_type(&pdict->values, t_array) ||
433 !r_is_array(&pdict->keys) ||
434 !r_has_type(&pdict->count, t_integer) ||
435 !r_has_type(&pdict->maxlength, t_integer)
436 )
437 lprintf2("At 0x%lx, invalid dict 0x%lx\n",
438 (ulong) pref, (ulong) pdict);
439 rptr = (const ref *)pdict;
440 }
441 size = sizeof(dict) / sizeof(ref);
442 tname = "dict";
443 goto cka;
444 }
445 }
446
447 /* Validate an object. */
448 void
ialloc_validate_object(const obj_header_t * ptr,const chunk_t * cp,gc_state_t * gcst)449 ialloc_validate_object(const obj_header_t * ptr, const chunk_t * cp,
450 gc_state_t * gcst)
451 {
452 const obj_header_t *pre = ptr - 1;
453 ulong size = pre_obj_contents_size(pre);
454 gs_memory_type_ptr_t otype = pre->o_type;
455 const char *oname;
456
457 if (!gs_debug_c('?'))
458 return; /* no check */
459 if (cp == 0 && gcst != 0) {
460 gc_state_t st;
461
462 st = *gcst; /* no side effects! */
463 if (!(cp = gc_locate(pre, &st))) {
464 lprintf1("Object 0x%lx not in any chunk!\n",
465 (ulong) ptr);
466 return; /*gs_abort(); */
467 }
468 }
469 if (otype == &st_free) {
470 lprintf3("Reference to free object 0x%lx(%lu), in chunk 0x%lx!\n",
471 (ulong) ptr, (ulong) size, (ulong) cp);
472 gs_abort();
473 }
474 if ((cp != 0 && !object_size_valid(pre, size, cp)) ||
475 otype->ssize == 0 ||
476 size % otype->ssize != 0 ||
477 (oname = struct_type_name_string(otype),
478 *oname < 33 || *oname > 126)
479 ) {
480 lprintf2("Bad object 0x%lx(%lu),\n",
481 (ulong) ptr, (ulong) size);
482 dprintf2(" ssize = %u, in chunk 0x%lx!\n",
483 otype->ssize, (ulong) cp);
484 gs_abort();
485 }
486 }
487
488 #else /* !DEBUG */
489
490 void
ialloc_validate_spaces(const gs_dual_memory_t * dmem)491 ialloc_validate_spaces(const gs_dual_memory_t * dmem)
492 {
493 }
494
495 void
ialloc_validate_memory(const gs_ref_memory_t * mem,gc_state_t * gcst)496 ialloc_validate_memory(const gs_ref_memory_t * mem, gc_state_t * gcst)
497 {
498 }
499
500 void
ialloc_validate_chunk(const chunk_t * cp,gc_state_t * gcst)501 ialloc_validate_chunk(const chunk_t * cp, gc_state_t * gcst)
502 {
503 }
504
505 void
ialloc_validate_object(const obj_header_t * ptr,const chunk_t * cp,gc_state_t * gcst)506 ialloc_validate_object(const obj_header_t * ptr, const chunk_t * cp,
507 gc_state_t * gcst)
508 {
509 }
510
511 #endif /* (!)DEBUG */
512