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