123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356 |
- /* Copyright (C) 1993, 1996, 1997, 1998, 1999 Aladdin Enterprises. All rights reserved.
-
- This software is provided AS-IS with no warranty, either express or
- implied.
-
- This software is distributed under license and may not be copied,
- modified or distributed except as expressly authorized under the terms
- of the license contained in the file LICENSE in this distribution.
-
- For more information about licensing, please refer to
- http://www.ghostscript.com/licensing/. For information on
- commercial licensing, go to http://www.artifex.com/licensing/ or
- contact Artifex Software, Inc., 101 Lucas Valley Road #110,
- San Rafael, CA 94903, U.S.A., +1(415)492-9861.
- */
- /* $Id: igc.c,v 1.15 2005/09/05 13:58:55 leonardo Exp $ */
- /* Garbage collector for Ghostscript */
- #include "memory_.h"
- #include "ghost.h"
- #include "ierrors.h"
- #include "gsexit.h"
- #include "gsmdebug.h"
- #include "gsstruct.h"
- #include "gsutil.h"
- #include "iastate.h"
- #include "isave.h"
- #include "isstate.h"
- #include "idict.h"
- #include "ipacked.h"
- #include "istruct.h"
- #include "igc.h"
- #include "igcstr.h"
- #include "inamedef.h"
- #include "opdef.h" /* for marking oparray names */
- /* Define whether to force all garbage collections to be global. */
- private const bool I_FORCE_GLOBAL_GC = false;
- /* Define whether to bypass the collector entirely. */
- private const bool I_BYPASS_GC = false;
- /* Define an entry on the mark stack. */
- typedef struct {
- void *ptr;
- uint index;
- bool is_refs;
- } ms_entry;
- /* Define (a segment of) the mark stack. */
- /* entries[0] has ptr = 0 to indicate the bottom of the stack. */
- /* count additional entries follow this structure. */
- typedef struct gc_mark_stack_s gc_mark_stack;
- struct gc_mark_stack_s {
- gc_mark_stack *prev;
- gc_mark_stack *next;
- uint count;
- bool on_heap; /* if true, allocated during GC */
- ms_entry entries[1];
- };
- /* Define the mark stack sizing parameters. */
- #define ms_size_default 100 /* default, allocated on C stack */
- /* This should probably be defined as a parameter somewhere.... */
- #define ms_size_desired /* for additional allocation */\
- ((max_ushort - sizeof(gc_mark_stack)) / sizeof(ms_entry) - 10)
- #define ms_size_min 50 /* min size for segment in free block */
- /* Forward references */
- private void gc_init_mark_stack(gc_mark_stack *, uint);
- private void gc_objects_clear_marks(const gs_memory_t *mem, chunk_t *);
- private void gc_unmark_names(name_table *);
- private int gc_trace(gs_gc_root_t *, gc_state_t *, gc_mark_stack *);
- private int gc_rescan_chunk(chunk_t *, gc_state_t *, gc_mark_stack *);
- private int gc_trace_chunk(const gs_memory_t *mem, chunk_t *, gc_state_t *, gc_mark_stack *);
- private bool gc_trace_finish(gc_state_t *);
- private void gc_clear_reloc(chunk_t *);
- private void gc_objects_set_reloc(chunk_t *);
- private void gc_do_reloc(chunk_t *, gs_ref_memory_t *, gc_state_t *);
- private void gc_objects_compact(chunk_t *, gc_state_t *);
- private void gc_free_empty_chunks(gs_ref_memory_t *);
- /* Forward references for pointer types */
- private ptr_proc_unmark(ptr_struct_unmark);
- private ptr_proc_mark(ptr_struct_mark);
- private ptr_proc_unmark(ptr_string_unmark);
- private ptr_proc_mark(ptr_string_mark);
- /*ptr_proc_unmark(ptr_ref_unmark); *//* in igc.h */
- /*ptr_proc_mark(ptr_ref_mark); *//* in igc.h */
- private ptr_proc_reloc(igc_reloc_struct_ptr, void);
- ptr_proc_reloc(igc_reloc_ref_ptr, ref_packed); /* in igcref.c */
- refs_proc_reloc(igc_reloc_refs); /* in igcref.c */
- /* Define this GC's procedure vector. */
- private const gc_procs_with_refs_t igc_procs = {
- igc_reloc_struct_ptr, igc_reloc_string, igc_reloc_const_string,
- igc_reloc_param_string, igc_reloc_ref_ptr, igc_reloc_refs
- };
- /* Pointer type descriptors. */
- /* Note that the trace/mark routine has special knowledge of ptr_ref_type */
- /* and ptr_struct_type -- it assumes that no other types have embedded */
- /* pointers. Note also that the reloc procedures for string and ref */
- /* pointers are never called. */
- typedef ptr_proc_reloc((*ptr_proc_reloc_t), void);
- const gs_ptr_procs_t ptr_struct_procs =
- {ptr_struct_unmark, ptr_struct_mark, (ptr_proc_reloc_t) igc_reloc_struct_ptr};
- const gs_ptr_procs_t ptr_string_procs =
- {ptr_string_unmark, ptr_string_mark, NULL};
- const gs_ptr_procs_t ptr_const_string_procs =
- {ptr_string_unmark, ptr_string_mark, NULL};
- const gs_ptr_procs_t ptr_ref_procs =
- {ptr_ref_unmark, ptr_ref_mark, NULL};
- /* ------ Main program ------ */
- /* Top level of garbage collector. */
- #ifdef DEBUG
- private void
- end_phase(const char *str)
- {
- if (gs_debug_c('6')) {
- dlprintf1("[6]---------------- end %s ----------------\n",
- (const char *)str);
- dflush();
- }
- }
- static const char *const depth_dots_string = "..........";
- private const char *
- depth_dots(const ms_entry * sp, const gc_mark_stack * pms)
- {
- int depth = sp - pms->entries - 1;
- const gc_mark_stack *pss = pms;
- while ((pss = pss->prev) != 0)
- depth += pss->count - 1;
- return depth_dots_string + (depth >= 10 ? 0 : 10 - depth);
- }
- private void
- gc_validate_spaces(gs_ref_memory_t **spaces, int max_space, gc_state_t *gcst)
- {
- int i;
- gs_ref_memory_t *mem;
- for (i = 1; i <= max_space; ++i)
- if ((mem = spaces[i]) != 0)
- ialloc_validate_memory(mem, gcst);
- }
- #else /* !DEBUG */
- # define end_phase(str) DO_NOTHING
- #endif /* DEBUG */
- void
- gs_gc_reclaim(vm_spaces * pspaces, bool global)
- {
- #define nspaces ((i_vm_max + 1) * 2) /* * 2 for stable allocators */
- vm_spaces spaces;
- gs_ref_memory_t *space_memories[nspaces];
- gs_gc_root_t space_roots[nspaces];
- int max_trace; /* max space_ to trace */
- int min_collect; /* min space_ to collect */
- int min_collect_vm_space; /* min VM space to collect */
- int ispace;
- gs_ref_memory_t *mem;
- chunk_t *cp;
- gs_gc_root_t *rp;
- gc_state_t state;
- struct _msd {
- gc_mark_stack stack;
- ms_entry body[ms_size_default];
- } ms_default;
- gc_mark_stack *mark_stack = &ms_default.stack;
- const gs_memory_t *cmem;
- /* Optionally force global GC for debugging. */
- if (I_FORCE_GLOBAL_GC)
- global = true;
- /* Determine which spaces we are tracing and collecting. */
- spaces = *pspaces;
- cmem = space_system->stable_memory;
- space_memories[1] = space_system;
- space_memories[2] = space_global;
- min_collect = max_trace = 2;
- min_collect_vm_space = i_vm_global;
- if (space_global->stable_memory != (gs_memory_t *)space_global)
- space_memories[++max_trace] =
- (gs_ref_memory_t *)space_global->stable_memory;
- if (space_global != space_local) {
- space_memories[++max_trace] = space_local;
- min_collect = max_trace;
- min_collect_vm_space = i_vm_local;
- if (space_local->stable_memory != (gs_memory_t *)space_local)
- space_memories[++max_trace] =
- (gs_ref_memory_t *)space_local->stable_memory;
- }
- if (global)
- min_collect = min_collect_vm_space = 1;
- #define for_spaces(i, n)\
- for (i = 1; i <= n; ++i)
- #define for_collected_spaces(i)\
- for (i = min_collect; i <= max_trace; ++i)
- #define for_space_mems(i, mem)\
- for (mem = space_memories[i]; mem != 0; mem = &mem->saved->state)
- #define for_mem_chunks(mem, cp)\
- for (cp = (mem)->cfirst; cp != 0; cp = cp->cnext)
- #define for_space_chunks(i, mem, cp)\
- for_space_mems(i, mem) for_mem_chunks(mem, cp)
- #define for_chunks(n, mem, cp)\
- for_spaces(ispace, n) for_space_chunks(ispace, mem, cp)
- #define for_collected_chunks(mem, cp)\
- for_collected_spaces(ispace) for_space_chunks(ispace, mem, cp)
- #define for_roots(n, mem, rp)\
- for_spaces(ispace, n)\
- for (mem = space_memories[ispace], rp = mem->roots; rp != 0; rp = rp->next)
- /* Initialize the state. */
- state.procs = &igc_procs;
- state.loc.memory = space_global; /* any one will do */
- state.loc.cp = 0;
- state.spaces = spaces;
- state.min_collect = min_collect_vm_space << r_space_shift;
- state.relocating_untraced = false;
- state.heap = state.loc.memory->non_gc_memory;
- state.ntable = state.heap->gs_lib_ctx->gs_name_table;
- /* Register the allocators themselves as roots, */
- /* so we mark and relocate the change and save lists properly. */
- for_spaces(ispace, max_trace)
- gs_register_struct_root((gs_memory_t *)space_memories[ispace],
- &space_roots[ispace],
- (void **)&space_memories[ispace],
- "gc_top_level");
- end_phase("register space roots");
- #ifdef DEBUG
- /* Pre-validate the state. This shouldn't be necessary.... */
- gc_validate_spaces(space_memories, max_trace, &state);
- end_phase("pre-validate pointers");
- #endif
- if (I_BYPASS_GC) { /* Don't collect at all. */
- goto no_collect;
- }
- /* Clear marks in spaces to be collected. */
- for_collected_spaces(ispace)
- for_space_chunks(ispace, mem, cp) {
- gc_objects_clear_marks((const gs_memory_t *)mem, cp);
- gc_strings_set_marks(cp, false);
- }
- end_phase("clear chunk marks");
- /* Clear the marks of roots. We must do this explicitly, */
- /* since some roots are not in any chunk. */
- for_roots(max_trace, mem, rp) {
- enum_ptr_t eptr;
- eptr.ptr = *rp->p;
- if_debug_root('6', "[6]unmarking root", rp);
- (*rp->ptype->unmark)(&eptr, &state);
- }
- end_phase("clear root marks");
- if (global)
- gc_unmark_names(state.ntable);
- /* Initialize the (default) mark stack. */
- gc_init_mark_stack(&ms_default.stack, ms_size_default);
- ms_default.stack.prev = 0;
- ms_default.stack.on_heap = false;
- /* Add all large-enough free blocks to the mark stack. */
- /* Also initialize the rescan pointers. */
- {
- gc_mark_stack *end = mark_stack;
- for_chunks(max_trace, mem, cp) {
- uint avail = cp->ctop - cp->cbot;
- if (avail >= sizeof(gc_mark_stack) + sizeof(ms_entry) *
- ms_size_min &&
- !cp->inner_count
- ) {
- gc_mark_stack *pms = (gc_mark_stack *) cp->cbot;
- gc_init_mark_stack(pms, (avail - sizeof(gc_mark_stack)) /
- sizeof(ms_entry));
- end->next = pms;
- pms->prev = end;
- pms->on_heap = false;
- if_debug2('6', "[6]adding free 0x%lx(%u) to mark stack\n",
- (ulong) pms, pms->count);
- }
- cp->rescan_bot = cp->cend;
- cp->rescan_top = cp->cbase;
- }
- }
- /* Mark reachable objects. */
- {
- int more = 0;
- /* Mark from roots. */
- for_roots(max_trace, mem, rp) {
- if_debug_root('6', "[6]marking root", rp);
- more |= gc_trace(rp, &state, mark_stack);
- }
- end_phase("mark");
- /* If this is a local GC, mark from non-local chunks. */
- if (!global)
- for_chunks(min_collect - 1, mem, cp)
- more |= gc_trace_chunk((const gs_memory_t *)mem, cp, &state, mark_stack);
- /* Handle mark stack overflow. */
- while (more < 0) { /* stack overflowed */
- more = 0;
- for_chunks(max_trace, mem, cp)
- more |= gc_rescan_chunk(cp, &state, mark_stack);
- }
- end_phase("mark overflow");
- }
- /* Free the mark stack. */
- {
- gc_mark_stack *pms = mark_stack;
- while (pms->next)
- pms = pms->next;
- while (pms) {
- gc_mark_stack *prev = pms->prev;
- if (pms->on_heap)
- gs_free_object(state.heap, pms, "gc mark stack");
- else
- gs_alloc_fill(pms, gs_alloc_fill_free,
- sizeof(*pms) + sizeof(ms_entry) * pms->count);
- pms = prev;
- }
- }
- end_phase("free mark stack");
- if (global) {
- gc_trace_finish(&state);
- names_trace_finish(state.ntable, &state);
- end_phase("finish trace");
- }
- /* Clear marks and relocation in spaces that are only being traced. */
- /* We have to clear the marks first, because we want the */
- /* relocation to wind up as o_untraced, not o_unmarked. */
- for_chunks(min_collect - 1, mem, cp)
- gc_objects_clear_marks((const gs_memory_t *)mem, cp);
- end_phase("post-clear marks");
- for_chunks(min_collect - 1, mem, cp)
- gc_clear_reloc(cp);
- end_phase("clear reloc");
- /* Set the relocation of roots outside any chunk to o_untraced, */
- /* so we won't try to relocate pointers to them. */
- /* (Currently, there aren't any.) */
- /* Disable freeing in the allocators of the spaces we are */
- /* collecting, so finalization procedures won't cause problems. */
- {
- int i;
- for_collected_spaces(i)
- gs_enable_free((gs_memory_t *)space_memories[i], false);
- }
- /* Compute relocation based on marks, in the spaces */
- /* we are going to compact. Also finalize freed objects. */
- for_collected_chunks(mem, cp) {
- gc_objects_set_reloc(cp);
- gc_strings_set_reloc(cp);
- }
- /* Re-enable freeing. */
- {
- int i;
- for_collected_spaces(i)
- gs_enable_free((gs_memory_t *)space_memories[i], true);
- }
- end_phase("set reloc");
- /* Relocate pointers. */
- state.relocating_untraced = true;
- for_chunks(min_collect - 1, mem, cp)
- gc_do_reloc(cp, mem, &state);
- state.relocating_untraced = false;
- for_collected_chunks(mem, cp)
- gc_do_reloc(cp, mem, &state);
- end_phase("relocate chunks");
- for_roots(max_trace, mem, rp) {
- if_debug3('6', "[6]relocating root 0x%lx: 0x%lx -> 0x%lx\n",
- (ulong) rp, (ulong) rp->p, (ulong) * rp->p);
- if (rp->ptype == ptr_ref_type) {
- ref *pref = (ref *) * rp->p;
- igc_reloc_refs((ref_packed *) pref,
- (ref_packed *) (pref + 1),
- &state);
- } else
- *rp->p = (*rp->ptype->reloc) (*rp->p, &state);
- if_debug3('6', "[6]relocated root 0x%lx: 0x%lx -> 0x%lx\n",
- (ulong) rp, (ulong) rp->p, (ulong) * rp->p);
- }
- end_phase("relocate roots");
- /* Compact data. We only do this for spaces we are collecting. */
- for_collected_spaces(ispace) {
- for_space_mems(ispace, mem) {
- for_mem_chunks(mem, cp) {
- if_debug_chunk('6', "[6]compacting chunk", cp);
- gc_objects_compact(cp, &state);
- gc_strings_compact(cp);
- if_debug_chunk('6', "[6]after compaction:", cp);
- if (mem->pcc == cp)
- mem->cc = *cp;
- }
- mem->saved = mem->reloc_saved;
- ialloc_reset_free(mem);
- }
- }
- end_phase("compact");
- /* Free empty chunks. */
- for_collected_spaces(ispace) {
- for_space_mems(ispace, mem) {
- gc_free_empty_chunks(mem);
- }
- }
- end_phase("free empty chunks");
- /*
- * Update previous_status to reflect any freed chunks,
- * and set inherited to the negative of allocated,
- * so it has no effect. We must update previous_status by
- * working back-to-front along the save chain, using pointer reversal.
- * (We could update inherited in any order, since it only uses
- * information local to the individual save level.)
- */
- for_collected_spaces(ispace) { /* Reverse the pointers. */
- alloc_save_t *curr;
- alloc_save_t *prev = 0;
- alloc_save_t *next;
- gs_memory_status_t total;
- for (curr = space_memories[ispace]->saved; curr != 0;
- prev = curr, curr = next
- ) {
- next = curr->state.saved;
- curr->state.saved = prev;
- }
- /* Now work the other way, accumulating the values. */
- total.allocated = 0, total.used = 0;
- for (curr = prev, prev = 0; curr != 0;
- prev = curr, curr = next
- ) {
- mem = &curr->state;
- next = mem->saved;
- mem->saved = prev;
- mem->previous_status = total;
- if_debug3('6',
- "[6]0x%lx previous allocated=%lu, used=%lu\n",
- (ulong) mem, total.allocated, total.used);
- gs_memory_status((gs_memory_t *) mem, &total);
- mem->gc_allocated = mem->allocated + total.allocated;
- mem->inherited = -(int)mem->allocated;
- }
- mem = space_memories[ispace];
- mem->previous_status = total;
- mem->gc_allocated = mem->allocated + total.allocated;
- if_debug3('6', "[6]0x%lx previous allocated=%lu, used=%lu\n",
- (ulong) mem, total.allocated, total.used);
- }
- end_phase("update stats");
- no_collect:
- /* Unregister the allocator roots. */
- for_spaces(ispace, max_trace)
- gs_unregister_root((gs_memory_t *)space_memories[ispace],
- &space_roots[ispace], "gc_top_level");
- end_phase("unregister space roots");
- #ifdef DEBUG
- /* Validate the state. This shouldn't be necessary.... */
- gc_validate_spaces(space_memories, max_trace, &state);
- end_phase("validate pointers");
- #endif
- }
- /* ------ Debugging utilities ------ */
- /* Validate a pointer to an object header. */
- #ifdef DEBUG
- # define debug_check_object(pre, cp, gcst)\
- ialloc_validate_object((pre) + 1, cp, gcst)
- #else
- # define debug_check_object(pre, cp, gcst) DO_NOTHING
- #endif
- /* ------ Unmarking phase ------ */
- /* Unmark a single struct. */
- private void
- ptr_struct_unmark(enum_ptr_t *pep, gc_state_t * ignored)
- {
- void *const vptr = (void *)pep->ptr; /* break const */
- if (vptr != 0)
- o_set_unmarked(((obj_header_t *) vptr - 1));
- }
- /* Unmark a single string. */
- private void
- ptr_string_unmark(enum_ptr_t *pep, gc_state_t * gcst)
- {
- discard(gc_string_mark(pep->ptr, pep->size, false, gcst));
- }
- /* Unmark the objects in a chunk. */
- private void
- gc_objects_clear_marks(const gs_memory_t *mem, chunk_t * cp)
- {
- if_debug_chunk('6', "[6]unmarking chunk", cp);
- SCAN_CHUNK_OBJECTS(cp)
- DO_ALL
- struct_proc_clear_marks((*proc)) =
- pre->o_type->clear_marks;
- #ifdef DEBUG
- if (pre->o_type != &st_free)
- debug_check_object(pre, cp, NULL);
- #endif
- if_debug3('7', " [7](un)marking %s(%lu) 0x%lx\n",
- struct_type_name_string(pre->o_type),
- (ulong) size, (ulong) pre);
- o_set_unmarked(pre);
- if (proc != 0)
- (*proc) (mem, pre + 1, size, pre->o_type);
- END_OBJECTS_SCAN
- }
- /* Mark 0- and 1-character names, and those referenced from the */
- /* op_array_nx_table, and unmark all the rest. */
- private void
- gc_unmark_names(name_table * nt)
- {
- uint i;
- names_unmark_all(nt);
- for (i = 0; i < op_array_table_global.count; i++) {
- name_index_t nidx = op_array_table_global.nx_table[i];
- names_mark_index(nt, nidx);
- }
- for (i = 0; i < op_array_table_local.count; i++) {
- name_index_t nidx = op_array_table_local.nx_table[i];
- names_mark_index(nt, nidx);
- }
- }
- /* ------ Marking phase ------ */
- /* Initialize (a segment of) the mark stack. */
- private void
- gc_init_mark_stack(gc_mark_stack * pms, uint count)
- {
- pms->next = 0;
- pms->count = count;
- pms->entries[0].ptr = 0;
- pms->entries[0].index = 0;
- pms->entries[0].is_refs = false;
- }
- /* Mark starting from all marked objects in the interval of a chunk */
- /* needing rescanning. */
- private int
- gc_rescan_chunk(chunk_t * cp, gc_state_t * pstate, gc_mark_stack * pmstack)
- {
- byte *sbot = cp->rescan_bot;
- byte *stop = cp->rescan_top;
- gs_gc_root_t root;
- void *comp;
- int more = 0;
- const gs_memory_t *mem = gcst_get_memory_ptr( pstate );
- if (sbot > stop)
- return 0;
- root.p = ∁
- if_debug_chunk('6', "[6]rescanning chunk", cp);
- cp->rescan_bot = cp->cend;
- cp->rescan_top = cp->cbase;
- SCAN_CHUNK_OBJECTS(cp)
- DO_ALL
- if ((byte *) (pre + 1) + size < sbot);
- else if ((byte *) (pre + 1) > stop)
- return more; /* 'break' won't work here */
- else {
- if_debug2('7', " [7]scanning/marking 0x%lx(%lu)\n",
- (ulong) pre, (ulong) size);
- if (pre->o_type == &st_refs) {
- ref_packed *rp = (ref_packed *) (pre + 1);
- char *end = (char *)rp + size;
- root.ptype = ptr_ref_type;
- while ((char *)rp < end) {
- comp = rp;
- if (r_is_packed(rp)) {
- if (r_has_pmark(rp)) {
- r_clear_pmark(rp);
- more |= gc_trace(&root, pstate,
- pmstack);
- }
- rp++;
- } else {
- ref *const pref = (ref *)rp;
- if (r_has_attr(pref, l_mark)) {
- r_clear_attrs(pref, l_mark);
- more |= gc_trace(&root, pstate, pmstack);
- }
- rp += packed_per_ref;
- }
- }
- } else if (!o_is_unmarked(pre)) {
- struct_proc_clear_marks((*proc)) =
- pre->o_type->clear_marks;
- root.ptype = ptr_struct_type;
- comp = pre + 1;
- if (!o_is_untraced(pre))
- o_set_unmarked(pre);
- if (proc != 0)
- (*proc) (mem, comp, size, pre->o_type);
- more |= gc_trace(&root, pstate, pmstack);
- }
- }
- END_OBJECTS_SCAN
- return more;
- }
- /* Mark starting from all the objects in a chunk. */
- /* We assume that pstate->min_collect > avm_system, */
- /* so we don't have to trace names. */
- private int
- gc_trace_chunk(const gs_memory_t *mem, chunk_t * cp, gc_state_t * pstate, gc_mark_stack * pmstack)
- {
- gs_gc_root_t root;
- void *comp;
- int more = 0;
- int min_trace = pstate->min_collect;
- root.p = ∁
- if_debug_chunk('6', "[6]marking from chunk", cp);
- SCAN_CHUNK_OBJECTS(cp)
- DO_ALL
- {
- if_debug2('7', " [7]scanning/marking 0x%lx(%lu)\n",
- (ulong) pre, (ulong) size);
- if (pre->o_type == &st_refs) {
- ref_packed *rp = (ref_packed *) (pre + 1);
- char *end = (char *)rp + size;
- root.ptype = ptr_ref_type;
- while ((char *)rp < end) {
- comp = rp;
- if (r_is_packed(rp)) { /* No packed refs need tracing. */
- rp++;
- } else {
- ref *const pref = (ref *)rp;
- if (r_space(pref) >= min_trace) {
- r_clear_attrs(pref, l_mark);
- more |= gc_trace(&root, pstate, pmstack);
- }
- rp += packed_per_ref;
- }
- }
- } else if (!o_is_unmarked(pre)) {
- if (!o_is_untraced(pre))
- o_set_unmarked(pre);
- if (pre->o_type != &st_free) {
- struct_proc_clear_marks((*proc)) =
- pre->o_type->clear_marks;
- root.ptype = ptr_struct_type;
- comp = pre + 1;
- if (proc != 0)
- (*proc) (mem, comp, size, pre->o_type);
- more |= gc_trace(&root, pstate, pmstack);
- }
- }
- }
- END_OBJECTS_SCAN
- return more;
- }
- /* Recursively mark from a (root) pointer. */
- /* Return -1 if we overflowed the mark stack, */
- /* 0 if we completed successfully without marking any new objects, */
- /* 1 if we completed and marked some new objects. */
- private int gc_extend_stack(gc_mark_stack *, gc_state_t *);
- private int
- gc_trace(gs_gc_root_t * rp, gc_state_t * pstate, gc_mark_stack * pmstack)
- {
- int min_trace = pstate->min_collect;
- gc_mark_stack *pms = pmstack;
- ms_entry *sp = pms->entries + 1;
- /* We stop the mark stack 1 entry early, because we store into */
- /* the entry beyond the top. */
- ms_entry *stop = sp + pms->count - 2;
- int new = 0;
- enum_ptr_t nep;
- void *nptr;
- name_table *nt = pstate->ntable;
- #define mark_name(nidx)\
- BEGIN\
- if (names_mark_index(nt, nidx)) {\
- new |= 1;\
- if_debug2('8', " [8]marked name 0x%lx(%u)\n",\
- (ulong)names_index_ptr(nt, nidx), nidx);\
- }\
- END
- nptr = *rp->p;
- if (nptr == 0)
- return 0;
- /* Initialize the stack */
- sp->ptr = nptr;
- if (rp->ptype == ptr_ref_type)
- sp->index = 1, sp->is_refs = true;
- else {
- sp->index = 0, sp->is_refs = false;
- nep.ptr = nptr;
- if ((*rp->ptype->mark) (&nep, pstate))
- new |= 1;
- }
- for (;;) {
- gs_ptr_type_t ptp;
- /*
- * The following should really be an if..else, but that
- * would force unnecessary is_refs tests.
- */
- if (sp->is_refs)
- goto do_refs;
- /* ---------------- Structure ---------------- */
- do_struct:
- {
- obj_header_t *ptr = sp->ptr;
- struct_proc_enum_ptrs((*mproc));
- if (ptr == 0) { /* We've reached the bottom of a stack segment. */
- pms = pms->prev;
- if (pms == 0)
- break; /* all done */
- stop = pms->entries + pms->count - 1;
- sp = stop;
- continue;
- }
- debug_check_object(ptr - 1, NULL, NULL);
- ts:if_debug4('7', " [7]%smarking %s 0x%lx[%u]",
- depth_dots(sp, pms),
- struct_type_name_string(ptr[-1].o_type),
- (ulong) ptr, sp->index);
- mproc = ptr[-1].o_type->enum_ptrs;
- if (mproc == gs_no_struct_enum_ptrs ||
- (ptp = (*mproc)
- (gcst_get_memory_ptr(pstate), ptr, pre_obj_contents_size(ptr - 1),
- sp->index, &nep, ptr[-1].o_type, pstate)) == 0
- ) {
- if_debug0('7', " - done\n");
- sp--;
- continue;
- }
- /* The cast in the following statement is the one */
- /* place we need to break 'const' to make the */
- /* template for pointer enumeration work. */
- nptr = (void *)nep.ptr;
- sp->index++;
- if_debug1('7', " = 0x%lx\n", (ulong) nptr);
- /* Descend into nep.ptr, whose pointer type is ptp. */
- if (ptp == ptr_struct_type) {
- sp[1].index = 0;
- sp[1].is_refs = false;
- if (sp == stop)
- goto push;
- if (!ptr_struct_mark(&nep, pstate))
- goto ts;
- new |= 1;
- (++sp)->ptr = nptr;
- goto do_struct;
- } else if (ptp == ptr_ref_type) {
- sp[1].index = 1;
- sp[1].is_refs = true;
- if (sp == stop)
- goto push;
- new |= 1;
- (++sp)->ptr = nptr;
- goto do_refs;
- } else { /* We assume this is some non-pointer- */
- /* containing type. */
- if ((*ptp->mark) (&nep, pstate))
- new |= 1;
- goto ts;
- }
- }
- /* ---------------- Refs ---------------- */
- do_refs:
- {
- ref_packed *pptr = sp->ptr;
- ref *rptr;
- tr:if (!sp->index) {
- --sp;
- continue;
- }
- --(sp->index);
- if_debug3('8', " [8]%smarking refs 0x%lx[%u]\n",
- depth_dots(sp, pms), (ulong) pptr, sp->index);
- if (r_is_packed(pptr)) {
- if (!r_has_pmark(pptr)) {
- r_set_pmark(pptr);
- new |= 1;
- if (r_packed_is_name(pptr)) {
- name_index_t nidx = packed_name_index(pptr);
- mark_name(nidx);
- }
- }
- ++pptr;
- goto tr;
- }
- rptr = (ref *) pptr; /* * const beyond here */
- if (r_has_attr(rptr, l_mark)) {
- pptr = (ref_packed *)(rptr + 1);
- goto tr;
- }
- r_set_attrs(rptr, l_mark);
- new |= 1;
- if (r_space(rptr) < min_trace) { /* Note that this always picks up all scalars. */
- pptr = (ref_packed *) (rptr + 1);
- goto tr;
- }
- sp->ptr = rptr + 1;
- switch (r_type(rptr)) {
- /* Struct cases */
- case t_file:
- nptr = rptr->value.pfile;
- rs:sp[1].is_refs = false;
- sp[1].index = 0;
- if (sp == stop) {
- ptp = ptr_struct_type;
- break;
- }
- nep.ptr = nptr;
- if (!ptr_struct_mark(&nep, pstate))
- goto nr;
- new |= 1;
- (++sp)->ptr = nptr;
- goto do_struct;
- case t_device:
- nptr = rptr->value.pdevice;
- goto rs;
- case t_fontID:
- case t_struct:
- case t_astruct:
- nptr = rptr->value.pstruct;
- goto rs;
- /* Non-trivial non-struct cases */
- case t_dictionary:
- nptr = rptr->value.pdict;
- sp[1].index = sizeof(dict) / sizeof(ref);
- goto rrp;
- case t_array:
- nptr = rptr->value.refs;
- rr:if ((sp[1].index = r_size(rptr)) == 0) { /* Set the base pointer to 0, */
- /* so we never try to relocate it. */
- rptr->value.refs = 0;
- goto nr;
- }
- rrp:
- rrc:sp[1].is_refs = true;
- if (sp == stop) {
- /*
- * The following initialization is unnecessary:
- * ptp will not be used if sp[1].is_refs = true.
- * We put this here solely to get rid of bogus
- * "possibly uninitialized variable" warnings
- * from certain compilers.
- */
- ptp = ptr_ref_type;
- break;
- }
- new |= 1;
- (++sp)->ptr = nptr;
- goto do_refs;
- case t_mixedarray:
- case t_shortarray:
- nptr = rptr->value.writable_packed;
- goto rr;
- case t_name:
- mark_name(names_index(nt, rptr));
- nr:pptr = (ref_packed *) (rptr + 1);
- goto tr;
- case t_string:
- if (gc_string_mark(rptr->value.bytes, r_size(rptr), true, pstate))
- new |= 1;
- goto nr;
- case t_oparray:
- nptr = rptr->value.refs; /* discard const */
- sp[1].index = 1;
- goto rrc;
- default:
- goto nr;
- }
- }
- /* ---------------- Recursion ---------------- */
- push:
- if (sp == stop) { /* The current segment is full. */
- int new_added = gc_extend_stack(pms, pstate);
- if (new_added) {
- new |= new_added;
- continue;
- }
- pms = pms->next;
- stop = pms->entries + pms->count - 1;
- pms->entries[1] = sp[1];
- sp = pms->entries;
- }
- /* index and is_refs are already set */
- if (!sp[1].is_refs) {
- nep.ptr = nptr;
- if (!(*ptp->mark) (&nep, pstate))
- continue;
- new |= 1;
- }
- (++sp)->ptr = nptr;
- }
- return new;
- }
- /* Link to, attempting to allocate if necessary, */
- /* another chunk of mark stack. */
- private int
- gc_extend_stack(gc_mark_stack * pms, gc_state_t * pstate)
- {
- if (pms->next == 0) { /* Try to allocate another segment. */
- uint count;
- for (count = ms_size_desired; count >= ms_size_min; count >>= 1) {
- pms->next = (gc_mark_stack *)
- gs_alloc_bytes_immovable(pstate->heap,
- sizeof(gc_mark_stack) +
- sizeof(ms_entry) * count,
- "gc mark stack");
- if (pms->next != 0)
- break;
- }
- if (pms->next == 0) { /* The mark stack overflowed. */
- ms_entry *sp = pms->entries + pms->count - 1;
- byte *cptr = sp->ptr; /* container */
- chunk_t *cp = gc_locate(cptr, pstate);
- int new = 1;
- if (cp == 0) { /* We were tracing outside collectible */
- /* storage. This can't happen. */
- lprintf1("mark stack overflowed while outside collectible space at 0x%lx!\n",
- (ulong) cptr);
- gs_abort(pstate->heap);
- }
- if (cptr < cp->rescan_bot)
- cp->rescan_bot = cptr, new = -1;
- if (cptr > cp->rescan_top)
- cp->rescan_top = cptr, new = -1;
- return new;
- }
- gc_init_mark_stack(pms->next, count);
- pms->next->prev = pms;
- pms->next->on_heap = true;
- }
- return 0;
- }
- /* Mark a struct. Return true if new mark. */
- private bool
- ptr_struct_mark(enum_ptr_t *pep, gc_state_t * ignored)
- {
- obj_header_t *ptr = (obj_header_t *)pep->ptr;
- if (ptr == 0)
- return false;
- ptr--; /* point to header */
- if (!o_is_unmarked(ptr))
- return false;
- o_mark(ptr);
- return true;
- }
- /* Mark a string. Return true if new mark. */
- private bool
- ptr_string_mark(enum_ptr_t *pep, gc_state_t * gcst)
- {
- return gc_string_mark(pep->ptr, pep->size, true, gcst);
- }
- /* Finish tracing by marking names. */
- private bool
- gc_trace_finish(gc_state_t * pstate)
- {
- name_table *nt = pstate->ntable;
- name_index_t nidx = 0;
- bool marked = false;
- while ((nidx = names_next_valid_index(nt, nidx)) != 0) {
- name_string_t *pnstr = names_index_string_inline(nt, nidx);
- if (pnstr->mark) {
- enum_ptr_t enst, ensst;
- if (!pnstr->foreign_string &&
- gc_string_mark(pnstr->string_bytes, pnstr->string_size,
- true, pstate)
- )
- marked = true;
- enst.ptr = names_index_sub_table(nt, nidx);
- ensst.ptr = names_index_string_sub_table(nt, nidx);
- marked |=
- ptr_struct_mark(&enst, pstate) |
- ptr_struct_mark(&ensst, pstate);
- }
- }
- return marked;
- }
- /* ------ Relocation planning phase ------ */
- /* Initialize the relocation information in the chunk header. */
- private void
- gc_init_reloc(chunk_t * cp)
- {
- chunk_head_t *chead = cp->chead;
- chead->dest = cp->cbase;
- chead->free.o_back =
- offset_of(chunk_head_t, free) >> obj_back_shift;
- chead->free.o_size = sizeof(obj_header_t);
- chead->free.o_nreloc = 0;
- }
- /* Set marks and clear relocation for chunks that won't be compacted. */
- private void
- gc_clear_reloc(chunk_t * cp)
- {
- byte *pfree = (byte *) & cp->chead->free;
- gc_init_reloc(cp);
- SCAN_CHUNK_OBJECTS(cp)
- DO_ALL
- const struct_shared_procs_t *procs =
- pre->o_type->shared;
- if (procs != 0)
- (*procs->clear_reloc) (pre, size);
- o_set_untraced(pre);
- pre->o_back = ((byte *) pre - pfree) >> obj_back_shift;
- END_OBJECTS_SCAN
- gc_strings_set_marks(cp, true);
- gc_strings_clear_reloc(cp);
- }
- /* Set the relocation for the objects in a chunk. */
- /* This will never be called for a chunk with any o_untraced objects. */
- private void
- gc_objects_set_reloc(chunk_t * cp)
- {
- uint reloc = 0;
- chunk_head_t *chead = cp->chead;
- byte *pfree = (byte *) & chead->free; /* most recent free object */
- if_debug_chunk('6', "[6]setting reloc for chunk", cp);
- gc_init_reloc(cp);
- SCAN_CHUNK_OBJECTS(cp)
- DO_ALL
- struct_proc_finalize((*finalize));
- const struct_shared_procs_t *procs =
- pre->o_type->shared;
- if ((procs == 0 ? o_is_unmarked(pre) :
- !(*procs->set_reloc) (pre, reloc, size))
- ) { /* Free object */
- reloc += sizeof(obj_header_t) + obj_align_round(size);
- if ((finalize = pre->o_type->finalize) != 0) {
- if_debug2('u', "[u]GC finalizing %s 0x%lx\n",
- struct_type_name_string(pre->o_type),
- (ulong) (pre + 1));
- (*finalize) (pre + 1);
- }
- pfree = (byte *) pre;
- pre->o_back = (pfree - (byte *) chead) >> obj_back_shift;
- pre->o_nreloc = reloc;
- if_debug3('7', " [7]at 0x%lx, unmarked %lu, new reloc = %u\n",
- (ulong) pre, (ulong) size, reloc);
- } else { /* Useful object */
- debug_check_object(pre, cp, NULL);
- pre->o_back = ((byte *) pre - pfree) >> obj_back_shift;
- }
- END_OBJECTS_SCAN
- #ifdef DEBUG
- if (reloc != 0) {
- if_debug1('6', "[6]freed %u", reloc);
- if_debug_chunk('6', " in", cp);
- }
- #endif
- }
- /* ------ Relocation phase ------ */
- /* Relocate the pointers in all the objects in a chunk. */
- private void
- gc_do_reloc(chunk_t * cp, gs_ref_memory_t * mem, gc_state_t * pstate)
- {
- chunk_head_t *chead = cp->chead;
- if_debug_chunk('6', "[6]relocating in chunk", cp);
- SCAN_CHUNK_OBJECTS(cp)
- DO_ALL
- #ifdef DEBUG
- pstate->container = cp;
- #endif
- /* We need to relocate the pointers in an object iff */
- /* it is o_untraced, or it is a useful object. */
- /* An object is free iff its back pointer points to */
- /* the chunk_head structure. */
- if (o_is_untraced(pre) ||
- pre->o_back << obj_back_shift != (byte *) pre - (byte *) chead
- ) {
- struct_proc_reloc_ptrs((*proc)) =
- pre->o_type->reloc_ptrs;
- if_debug3('7',
- " [7]relocating ptrs in %s(%lu) 0x%lx\n",
- struct_type_name_string(pre->o_type),
- (ulong) size, (ulong) pre);
- if (proc != 0)
- (*proc) (pre + 1, size, pre->o_type, pstate);
- }
- #ifdef DEBUG
- pstate->container = 0;
- #endif
- END_OBJECTS_SCAN
- }
- /* Print pointer relocation if debugging. */
- /* We have to provide this procedure even if DEBUG is not defined, */
- /* in case one of the other GC modules was compiled with DEBUG. */
- const void *
- print_reloc_proc(const void *obj, const char *cname, const void *robj)
- {
- if_debug3('9', " [9]relocate %s * 0x%lx to 0x%lx\n",
- cname, (ulong)obj, (ulong)robj);
- return robj;
- }
- /* Relocate a pointer to an (aligned) object. */
- /* See gsmemory.h for why the argument is const and the result is not. */
- private void /*obj_header_t */ *
- igc_reloc_struct_ptr(const void /*obj_header_t */ *obj, gc_state_t * gcst)
- {
- const obj_header_t *const optr = (const obj_header_t *)obj;
- const void *robj;
- if (obj == 0) {
- discard(print_reloc(obj, "NULL", 0));
- return 0;
- }
- debug_check_object(optr - 1, NULL, gcst);
- {
- uint back = optr[-1].o_back;
- if (back == o_untraced)
- robj = obj;
- else {
- #ifdef DEBUG
- /* Do some sanity checking. */
- chunk_t *cp = gcst->container;
- if (cp != 0 && cp->cbase <= (byte *)obj && (byte *)obj <cp->ctop) {
- if (back > (cp->ctop - cp->cbase) >> obj_back_shift) {
- lprintf2("Invalid back pointer %u at 0x%lx!\n",
- back, (ulong) obj);
- gs_abort(NULL);
- }
- } else {
- /* Pointed to unknown chunk. Can't check it, sorry. */
- }
- #endif
- {
- const obj_header_t *pfree = (const obj_header_t *)
- ((const char *)(optr - 1) -
- (back << obj_back_shift));
- const chunk_head_t *chead = (const chunk_head_t *)
- ((const char *)pfree -
- (pfree->o_back << obj_back_shift));
- robj = chead->dest +
- ((const char *)obj - (const char *)(chead + 1) -
- pfree->o_nreloc);
- }
- }
- }
- /* Use a severely deprecated pun to remove the const property. */
- {
- union { const void *r; void *w; } u;
- u.r = print_reloc(obj, struct_type_name_string(optr[-1].o_type), robj);
- return u.w;
- }
- }
- /* ------ Compaction phase ------ */
- /* Compact the objects in a chunk. */
- /* This will never be called for a chunk with any o_untraced objects. */
- private void
- gc_objects_compact(chunk_t * cp, gc_state_t * gcst)
- {
- chunk_head_t *chead = cp->chead;
- obj_header_t *dpre = (obj_header_t *) chead->dest;
- const gs_memory_t *cmem = gcst->spaces.memories.named.system->stable_memory;
- SCAN_CHUNK_OBJECTS(cp)
- DO_ALL
- /* An object is free iff its back pointer points to */
- /* the chunk_head structure. */
- if (pre->o_back << obj_back_shift != (byte *) pre - (byte *) chead) {
- const struct_shared_procs_t *procs = pre->o_type->shared;
- debug_check_object(pre, cp, gcst);
- if_debug4('7',
- " [7]compacting %s 0x%lx(%lu) to 0x%lx\n",
- struct_type_name_string(pre->o_type),
- (ulong) pre, (ulong) size, (ulong) dpre);
- if (procs == 0) {
- if (dpre != pre)
- memmove(dpre, pre,
- sizeof(obj_header_t) + size);
- } else
- (*procs->compact) (cmem, pre, dpre, size);
- dpre = (obj_header_t *)
- ((byte *) dpre + obj_size_round(size));
- }
- END_OBJECTS_SCAN
- if (cp->outer == 0 && chead->dest != cp->cbase)
- dpre = (obj_header_t *) cp->cbase; /* compacted this chunk into another */
- gs_alloc_fill(dpre, gs_alloc_fill_collected, cp->cbot - (byte *) dpre);
- cp->cbot = (byte *) dpre;
- cp->rcur = 0;
- cp->rtop = 0; /* just to be sure */
- }
- /* ------ Cleanup ------ */
- /* Free empty chunks. */
- private void
- gc_free_empty_chunks(gs_ref_memory_t * mem)
- {
- chunk_t *cp;
- chunk_t *csucc;
- /* Free the chunks in reverse order, */
- /* to encourage LIFO behavior. */
- for (cp = mem->clast; cp != 0; cp = csucc) { /* Make sure this isn't an inner chunk, */
- /* or a chunk that has inner chunks. */
- csucc = cp->cprev; /* save before freeing */
- if (cp->cbot == cp->cbase && cp->ctop == cp->climit &&
- cp->outer == 0 && cp->inner_count == 0
- ) {
- alloc_free_chunk(cp, mem);
- if (mem->pcc == cp)
- mem->pcc = 0;
- }
- }
- }
- const gs_memory_t * gcst_get_memory_ptr(gc_state_t *gcst)
- {
- vm_spaces spaces = gcst->spaces;
- const gs_memory_t *cmem = space_system->stable_memory;
- return cmem;
- }
|