home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 February / PCWK0296.iso / sharewar / dos / program / gs300sr1 / gs300sr1.exe / IGC.C < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-27  |  29.9 KB  |  1,037 lines
  1. /* Copyright (C) 1993, 1994 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* igc.c */
  20. /* Garbage collector for Ghostscript */
  21. #include "memory_.h"
  22. #include "ghost.h"
  23. #include "errors.h"
  24. #include "gsstruct.h"
  25. #include "gsutil.h"
  26. #include "iastate.h"
  27. #include "isave.h"
  28. #include "isstate.h"
  29. #include "idict.h"
  30. #include "ipacked.h"
  31. #include "istruct.h"
  32. #include "igc.h"
  33. #include "iname.h"
  34. #include "dstack.h"            /* for dsbot, dsp, dict_set_top */
  35. #include "estack.h"            /* for esbot, esp */
  36. #include "ostack.h"            /* for osbot, osp */
  37. #include "opdef.h"            /* for marking oparray names */
  38. #include "store.h"            /* for make_array */
  39.  
  40. /* Import the debugging variables from gsmemory.c. */
  41. extern byte gs_alloc_fill_collected;
  42.  
  43. /* Import the static interpreter refs from interp.c. */
  44. extern ref ref_static_stacks;
  45. extern ref ref_ref_stacks[3];
  46.  
  47. /* Import a cleanup routine from iname.c. */
  48. extern void name_gc_cleanup(P1(gc_state_t *));
  49.  
  50. /* Forward references */
  51. private void gs_vmreclaim(P2(gs_dual_memory_t *, bool));
  52. private void gc_top_level(P2(gs_dual_memory_t *, bool));
  53. private void gc_objects_clear_marks(P1(chunk_t *));
  54. private void gc_unmark_names(P0());
  55. private int gc_trace(P2(gs_gc_root_t *, gc_state_t *));
  56. private int gc_trace_chunk(P2(chunk_t *, gc_state_t *));
  57. private bool gc_trace_finish(P1(gc_state_t *));
  58. private void gc_clear_reloc(P1(chunk_t *));
  59. private void gc_objects_set_reloc(P1(chunk_t *));
  60. private void gc_do_reloc(P3(chunk_t *, gs_ref_memory_t *, gc_state_t *));
  61. private void gc_objects_compact(P2(chunk_t *, gc_state_t *));
  62. private void gc_free_empty_chunks(P1(gs_ref_memory_t *));
  63.  
  64. /* Forward references for pointer types */
  65. private ptr_proc_unmark(ptr_struct_unmark);
  66. private ptr_proc_mark(ptr_struct_mark);
  67. private ptr_proc_unmark(ptr_string_unmark);
  68. private ptr_proc_mark(ptr_string_mark);
  69. /*ptr_proc_unmark(ptr_ref_unmark);*/    /* in igc.h */
  70. /*ptr_proc_mark(ptr_ref_mark);*/    /* in igc.h */
  71. /*ptr_proc_reloc(gs_reloc_struct_ptr, void);*/    /* in gsstruct.h */
  72. /*ptr_proc_reloc(gs_reloc_string_ptr, byte);*/    /* in gsstruct.h */
  73. /*ptr_proc_reloc(gs_reloc_const_string_ptr, const byte);*/ /* in gsstruct.h */
  74. /*ptr_proc_reloc(gs_reloc_ref_ptr, ref_packed);*/    /* in istruct.h */
  75.  
  76. /* Pointer type descriptors. */
  77. /* Note that the trace/mark routine has special knowledge of ptr_ref_type */
  78. /* and ptr_struct_type, assuming that no other types have embedded */
  79. /* pointers. */
  80. typedef ptr_proc_reloc((*ptr_proc_reloc_t), void);
  81. const gs_ptr_procs_t ptr_struct_procs =
  82.  { ptr_struct_unmark, ptr_struct_mark, (ptr_proc_reloc_t)gs_reloc_struct_ptr };
  83. const gs_ptr_procs_t ptr_string_procs =
  84.  { ptr_string_unmark, ptr_string_mark, (ptr_proc_reloc_t)gs_reloc_string_ptr };
  85. const gs_ptr_procs_t ptr_const_string_procs =
  86.  { ptr_string_unmark, ptr_string_mark, (ptr_proc_reloc_t)gs_reloc_string_ptr };
  87. const gs_ptr_procs_t ptr_ref_procs =
  88.  { ptr_ref_unmark, ptr_ref_mark, (ptr_proc_reloc_t)gs_reloc_ref_ptr };
  89.  
  90. /* ------ Main program ------ */
  91.  
  92. /* Initialize the GC hook in the allocator. */
  93. private int ireclaim(P2(gs_dual_memory_t *, int));
  94. private void
  95. igc_init(void)
  96. {    gs_imemory.reclaim = ireclaim;
  97. }
  98.  
  99. /* GC hook called when the allocator returns a VMerror (which = -1), */
  100. /* or for vmreclaim (which = 0 for local, 1 for global). */
  101. private int
  102. ireclaim(gs_dual_memory_t *dmem, int which)
  103. {    bool global;
  104.     gs_ref_memory_t *mem;
  105.     if ( which < 0 )
  106.       {    /* Determine which allocator got the VMerror. */
  107.         gs_memory_status_t stats;
  108.         global = dmem->global->gc_status.requested > 0;
  109.         mem = (global ? dmem->global : dmem->local);
  110.         gs_memory_status((gs_memory_t *)mem, &stats);
  111.         if ( stats.allocated >= mem->gc_status.max_vm )
  112.           {    /* We can't satisfy this request within max_vm. */
  113.             return_error(e_VMerror);
  114.           }
  115.       }
  116.     else
  117.       {    global = which > 0;
  118.         mem = (global ? dmem->global : dmem->local);
  119.       }
  120. /****************/
  121. global = true;
  122. /****************/
  123.     gs_vmreclaim(dmem, global);
  124.     ialloc_set_limit(mem);
  125.     return 0;
  126. }
  127.  
  128. /* Interpreter entry to garbage collector. */
  129. /* This registers the stacks before calling the main GC. */
  130. private void near set_ref_chunk(P4(chunk_t *, ref *, ref *, gs_ref_memory_t *));
  131. private void
  132. gs_vmreclaim(gs_dual_memory_t *dmem, bool global)
  133. {    /*
  134.      * Create pseudo-chunks to hold the interpreter roots:
  135.      * copies of the ref_stacks, and, if necessary,
  136.      * the statically allocated stack bodies.
  137.      */
  138.     gs_ref_memory_t *mem = dmem->local;
  139.     gs_ref_memory_t *gmem = dmem->global;
  140.     gs_ref_memory_t *smem = dmem->system;
  141.     struct ir_ {
  142.         chunk_head_t head;
  143.         obj_header_t prefix;
  144.         ref refs[5+1];        /* +1 for extra relocation ref */
  145.     } iroot_refs;
  146.     chunk_t cir, css;
  147.     void *piroot = &iroot_refs.refs[0];
  148.     gs_gc_root_t iroot;
  149.  
  150.     alloc_close_chunk(mem);
  151.     if ( gmem != mem )
  152.       alloc_close_chunk(gmem);
  153.     alloc_close_chunk(smem);
  154.  
  155.     /* Copy the ref_stacks into the heap, so we can trace and */
  156.     /* relocate them. */
  157. #define get_stack(i, stk)\
  158.   ref_stack_cleanup(&stk);\
  159.   iroot_refs.refs[i+2] = ref_ref_stacks[i],\
  160.   *r_ptr(&iroot_refs.refs[i+2], ref_stack) = stk
  161.     get_stack(0, d_stack);
  162.     get_stack(1, e_stack);
  163.     get_stack(2, o_stack);
  164. #undef get_stack
  165.  
  166.     /* Make the root chunk. */
  167.     iroot_refs.refs[1] = ref_static_stacks;
  168.     make_array(&iroot_refs.refs[0], 0, 4, &iroot_refs.refs[1]);
  169.     set_ref_chunk(&cir, &iroot_refs.refs[0], &iroot_refs.refs[5], mem);
  170.     gs_register_ref_root((gs_memory_t *)mem, &iroot, &piroot, "gs_gc_main");
  171.  
  172.     /* If necessary, make the static stack chunk. */
  173. #define css_array iroot_refs.refs[1]
  174. #define css_base css_array.value.refs
  175.     if ( css_base != NULL )
  176.       set_ref_chunk(&css, css_base, css_base + r_size(&css_array), mem);
  177.  
  178.     gc_top_level(dmem, global);
  179.  
  180.     /* Remove the temporary chunks. */
  181.     if ( css_base != NULL )
  182.       alloc_unlink_chunk(&css, mem);
  183.     gs_unregister_root((gs_memory_t *)mem, &iroot, "gs_gc_main");
  184.     alloc_unlink_chunk(&cir, mem);
  185. #undef css_array
  186. #undef css_base
  187.  
  188.     /* Update the static copies of the ref_stacks. */
  189. #define put_stack(i, stk)\
  190.   ref_ref_stacks[i].value.pstruct = iroot_refs.refs[i+2].value.pstruct,\
  191.   stk = *r_ptr(&iroot_refs.refs[i+2], ref_stack)
  192.     put_stack(0, d_stack);
  193.     put_stack(1, e_stack);
  194.     put_stack(2, o_stack);
  195. #undef put_stack
  196.  
  197.     alloc_open_chunk(smem);
  198.     if ( gmem != mem )
  199.       alloc_open_chunk(gmem);
  200.     alloc_open_chunk(mem);
  201.  
  202.     /* Update caches */
  203.  
  204.     { uint dcount = ref_stack_count(&d_stack);
  205.       ref_systemdict = *ref_stack_index(&d_stack, dcount - 1);
  206.     }
  207.     dict_set_top();
  208. }
  209. private void near
  210. set_ref_chunk(chunk_t *cp, ref *bot, ref *top, gs_ref_memory_t *mem)
  211. {    obj_header_t *pre = (obj_header_t *)bot - 1;
  212.     chunk_head_t *head = (chunk_head_t *)pre - 1;
  213.     pre->o_large = 1;        /* not relocatable */
  214.     pre->o_lsize = 0;
  215.     pre->o_lmark = o_l_unmarked;
  216.     pre->o_size = (byte *)(top + 1) - (byte *)bot;
  217.     pre->o_type = &st_refs;
  218.     alloc_init_chunk(cp, (byte *)head, (byte *)(top + 1), false, NULL);    /* +1 for extra reloc ref */
  219.     cp->cbot = cp->ctop;
  220.     alloc_link_chunk(cp, mem);
  221.     make_int(top, 0);        /* relocation ref */
  222. }
  223.  
  224. /* Top level of garbage collector. */
  225. #ifdef DEBUG
  226. private void
  227. end_phase(const char _ds *str)
  228. {    if_debug1('6', "[6]---------------- end %s ----------------\n",
  229.           (const char *)str);
  230. }
  231. #else
  232. #  define end_phase(str) DO_NOTHING
  233. #endif
  234. private void
  235. gc_top_level(gs_dual_memory_t *dmem, bool global)
  236. {
  237. #define nspaces 3
  238.     gs_ref_memory_t *spaces[nspaces];
  239.     gs_gc_root_t space_roots[nspaces];
  240.     int ntrace, ncollect, ispace;
  241.     gs_ref_memory_t *mem;
  242.     chunk_t *cp;
  243.     gs_gc_root_t *rp;
  244.     gc_state_t state;
  245.  
  246.     /* Determine how many spaces we are collecting. */
  247.     
  248.     spaces[0] = dmem->local;
  249.     spaces[1] = dmem->system;
  250.     spaces[2] = dmem->global;
  251.     if ( dmem->global != dmem->local )
  252.         ntrace = 3;
  253.     else
  254.         ntrace = 2;
  255.     ncollect = (global ? ntrace : 1);
  256.  
  257. #define for_spaces(i, n)\
  258.   for ( i = 0; i < n; i++ )
  259. #define for_space_mems(i, mem)\
  260.   for ( mem = spaces[i]; mem != 0; mem = &mem->saved->state )
  261. #define for_mem_chunks(mem, cp)\
  262.   for ( cp = (mem)->cfirst; cp != 0; cp = cp->cnext )
  263. #define for_space_chunks(i, mem, cp)\
  264.   for_space_mems(i, mem) for_mem_chunks(mem, cp)
  265. #define for_chunks(n, mem, cp)\
  266.   for_spaces(ispace, n) for_space_chunks(ispace, mem, cp)
  267. #define for_roots(n, ap, rp)\
  268.   for_spaces(ispace, n)\
  269.     for ( mem = spaces[ispace], rp = mem->roots; rp != 0; rp = rp->next )
  270.  
  271.     /* Initialize the state. */
  272.     state.loc.memory = spaces[0];    /* either one will do */
  273.     state.loc.cp = 0;
  274.     state.local = spaces[0];
  275.     state.system = spaces[1];
  276.     state.global = spaces[2];
  277.  
  278.     /* Register the allocators themselves as roots, */
  279.     /* so we mark and relocate the change and save lists properly. */
  280.  
  281.     for_spaces(ispace, ntrace)
  282.       gs_register_struct_root((gs_memory_t *)spaces[ispace],
  283.                   &space_roots[ispace],
  284.                   (void **)&spaces[ispace],
  285.                   "gc_top_level");
  286.  
  287.     end_phase("register space roots");
  288.  
  289.     /* Clear marks in spaces to be collected; set them, */
  290.     /* and clear relocation, in spaces that are only being traced. */
  291.  
  292.     for_chunks(ncollect, mem, cp)
  293.       {    gc_objects_clear_marks(cp);
  294.         gc_strings_set_marks(cp, false);
  295.       }
  296.     for ( ispace = ncollect; ispace < ntrace; ispace++ )
  297.       for_space_chunks(ispace, mem, cp)
  298.         gc_clear_reloc(cp);
  299.  
  300.     end_phase("clear chunk marks");
  301.  
  302.     /* Clear the marks of roots.  We must do this explicitly, */
  303.     /* since some roots are not in any chunk. */
  304.  
  305.     for_roots(ntrace, mem, rp)
  306.       {    void *vptr = *rp->p;
  307.         if_debug_root('6', "[6]unmarking root", rp);
  308.         (*rp->ptype->unmark)(vptr, &state);
  309.       }
  310.  
  311.     end_phase("clear root marks");
  312.  
  313.     gc_unmark_names();
  314.  
  315.     /* Mark from roots. */
  316.  
  317.     {    int more = 0;
  318.         for_roots(ntrace, mem, rp)
  319.         {    if_debug_root('6', "[6]marking root", rp);
  320.             more |= gc_trace(rp, &state);
  321.         }
  322.  
  323.         end_phase("mark");
  324.  
  325.         while ( more < 0 )        /* stack overflowed */
  326.         {    more = 0;
  327.             for_chunks(ntrace, mem, cp)
  328.                 more |= gc_trace_chunk(cp, &state);
  329.         };
  330.  
  331.         end_phase("mark overflow");
  332.     }
  333.  
  334.     gc_trace_finish(&state);
  335.  
  336.     end_phase("finish trace");
  337.  
  338.     /* Set the relocation of roots outside any chunk to o_untraced, */
  339.     /* so we won't try to relocate pointers to them. */
  340.     /* (Currently, this is only the allocators.) */
  341.  
  342.     for_spaces(ispace, ntrace)
  343.       o_set_untraced(((obj_header_t *)spaces[ispace] - 1));
  344.  
  345.     /* Compute relocation based on marks, in the spaces */
  346.     /* we are going to compact. */
  347.  
  348.     for_chunks(ncollect, mem, cp)
  349.     {    gc_objects_set_reloc(cp);
  350.         gc_strings_set_reloc(cp);
  351.     }
  352.  
  353.     end_phase("set reloc");
  354.  
  355.     /* Remove unmarked names, and relocate name string pointers. */
  356.  
  357.     name_gc_cleanup(&state);
  358.  
  359.     end_phase("clean up names");
  360.  
  361.     /* Relocate pointers. */
  362.  
  363.     for_chunks(ntrace, mem, cp)
  364.         gc_do_reloc(cp, mem, &state);
  365.  
  366.     end_phase("relocate chunks");
  367.  
  368.     for_roots(ntrace, mem, rp)
  369.     {    if_debug3('6', "[6]relocating root 0x%lx: 0x%lx -> 0x%lx\n",
  370.               (ulong)rp, (ulong)rp->p, (ulong)*rp->p);
  371.         if ( rp->ptype == ptr_ref_type )
  372.         {    ref *pref = (ref *)*rp->p;
  373.             gs_reloc_refs((ref_packed *)pref,
  374.                       (ref_packed *)(pref + 1),
  375.                       &state);
  376.         }
  377.         else
  378.             *rp->p = (*rp->ptype->reloc)(*rp->p, &state);
  379.     }
  380.     /* The allocators themselves aren't in any chunk, */
  381.     /* so we have to relocate their references specially. */
  382.     for_spaces(ispace, ntrace)
  383.       { mem = spaces[ispace];
  384.         ref_memory_reloc_ptrs(mem, sizeof(gs_ref_memory_t), &state);
  385.       }
  386.  
  387.     end_phase("relocate roots");
  388.  
  389.     /* Compact data.  We only do this for spaces we are collecting. */
  390.  
  391.     for_spaces(ispace, ncollect)
  392.       { for_space_mems(ispace, mem)
  393.           { for_mem_chunks(mem, cp)
  394.           { if_debug_chunk('6', "[6]compacting chunk", cp);
  395.             gc_objects_compact(cp, &state);
  396.             gc_strings_compact(cp);
  397.             if_debug_chunk('6', "[6]after compaction:", cp);
  398.             if ( mem->pcc == cp )
  399.               mem->cc = *cp;
  400.           }
  401.         mem->saved = mem->reloc_saved;
  402.         ialloc_reset_free(mem);
  403.           }
  404.       }
  405.  
  406.     end_phase("compact");
  407.  
  408.     /* Free empty chunks. */
  409.  
  410.     for_spaces(ispace, ncollect)
  411.       for_space_mems(ispace, mem)
  412.         gc_free_empty_chunks(mem);
  413.  
  414.     end_phase("free empty chunks");
  415.  
  416.     /* Update previous_status.  We must do this by working back-to-front */
  417.     /* along the save chain, using pointer reversal. */
  418.  
  419.     for_spaces(ispace, ncollect)
  420.       {    /* Reverse the pointers. */
  421.         alloc_save_t *curr;
  422.         alloc_save_t *prev = 0;
  423.         alloc_save_t *next;
  424.         gs_memory_status_t total;
  425.         for ( curr = spaces[ispace]->saved; curr != 0;
  426.               prev = curr, curr = next
  427.             )
  428.           { next = curr->state.saved;
  429.             curr->state.saved = prev;
  430.           }
  431.         /* Now work the other way, accumulating the values. */
  432.         total.allocated = 0, total.used = 0;
  433.         for ( curr = prev, prev = 0; curr != 0;
  434.               prev = curr, curr = next
  435.             )
  436.           { mem = &curr->state;
  437.             next = mem->saved;
  438.             mem->saved = prev;
  439.             mem->previous_status = total;
  440.             if_debug3('6',
  441.                   "[6]0x%lx previous allocated=%lu, used=%lu\n",
  442.                   (ulong)mem, total.allocated, total.used);
  443.             gs_memory_status((gs_memory_t *)mem, &total);
  444.             mem->gc_allocated = mem->allocated + total.allocated;
  445.           }
  446.         mem = spaces[ispace];
  447.         mem->previous_status = total;
  448.         mem->gc_allocated = mem->allocated + total.allocated;
  449.         if_debug3('6', "[6]0x%lx previous allocated=%lu, used=%lu\n",
  450.               (ulong)mem, total.allocated, total.used);
  451.       }
  452.  
  453.     end_phase("update stats");
  454.  
  455.     /* Clear marks in spaces we didn't compact. */
  456.  
  457.     for ( ispace = ncollect; ispace < ntrace; ispace++ )
  458.       for_space_chunks(ispace, mem, cp)
  459.         gc_objects_clear_marks(cp);
  460.  
  461.     end_phase("post-clear marks");
  462.  
  463.     /* Unregister the allocator roots. */
  464.  
  465.     for_spaces(ispace, ntrace)
  466.       gs_unregister_root((gs_memory_t *)spaces[ispace],
  467.                  &space_roots[ispace], "gc_top_level");
  468.  
  469.     end_phase("unregister space roots");
  470.  
  471. }
  472.  
  473. /* ------ Debugging utilities ------ */
  474.  
  475. #ifdef DEBUG
  476. /* Validate a pointer to an object header. */
  477. private void
  478. debug_check_object(const obj_header_t *pre, const chunk_t *cp)
  479. {    ulong size = pre_obj_contents_size(pre);
  480.     gs_memory_type_ptr_t otype = pre->o_type;
  481.     const char *oname = struct_type_name_string(otype);
  482.     if ( *oname < 33 || *oname > 126 ||
  483.          size % otype->ssize != 0 ||
  484.          (cp != 0 &&
  485.           !(pre->o_large ? (byte *)pre == cp->cbase :
  486.         size <= cp->ctop - (byte *)(pre + 1)))
  487.        )
  488.     {    lprintf3("Bad size %lu at 0x%lx in chunk 0x%lx!\n",
  489.              (ulong)size, (ulong)pre, (ulong)cp);
  490.         exit(1);
  491.     }
  492. }
  493. #else
  494. #  define debug_check_object(pre, cp) DO_NOTHING
  495. #endif
  496.  
  497. /* ------ Unmarking phase ------ */
  498.  
  499. /* Unmark a single struct. */
  500. private void
  501. ptr_struct_unmark(void *vptr, gc_state_t *ignored)
  502. {    if ( vptr != 0 )
  503.       o_set_unmarked(((obj_header_t *)vptr - 1));
  504. }
  505.  
  506. /* Unmark a single string. */
  507. private void
  508. ptr_string_unmark(void *vptr, gc_state_t *gcst)
  509. {    (void) gc_string_mark(((gs_string *)vptr)->data,
  510.                   ((gs_string *)vptr)->size,
  511.                   false, gcst);
  512. }
  513.  
  514. /* Unmark the objects in a chunk. */
  515. private void
  516. gc_objects_clear_marks(chunk_t *cp)
  517. {    if_debug_chunk('6', "[6]unmarking chunk", cp);
  518.     SCAN_CHUNK_OBJECTS(cp)
  519.       DO_ALL
  520.         struct_proc_clear_marks((*proc)) =
  521.             pre->o_type->clear_marks;
  522.         debug_check_object(pre, cp);
  523.         if_debug3('7', " [7](un)marking %s(%lu) 0x%lx\n",
  524.               struct_type_name_string(pre->o_type),
  525.               (ulong)size, (ulong)pre);
  526.         o_set_unmarked(pre);
  527.         if ( proc != 0 )
  528.             (*proc)(pre + 1, size);
  529.     END_OBJECTS_SCAN
  530. }
  531.  
  532. /* Mark 0- and 1-character names, and those referenced from the */
  533. /* op_array_nx_table, and unmark all the rest. */
  534. private void
  535. gc_unmark_names()
  536. {    uint count = name_count();
  537.     register uint i;
  538.     for ( i = 0; i < count; i++ )
  539.     {    name *pname = name_index_ptr(i);
  540.         if ( pname->string_size <= 1 )
  541.           pname->mark = 1;
  542.         else
  543.           pname->mark = 0;
  544.     }
  545.     for ( i = 0; i < op_array_count; i++ )
  546.     {    uint nidx = op_array_nx_table[i];
  547.         name_index_ptr(nidx)->mark = 1;
  548.     }
  549. }
  550.  
  551. /* ------ Marking phase ------ */
  552.  
  553. /* Mark starting from all marked objects in a chunk. */
  554. private int
  555. gc_trace_chunk(chunk_t *cp, gc_state_t *pstate)
  556. {    gs_gc_root_t root;
  557.     void *comp;
  558.     int more = 0;
  559.     root.p = ∁
  560.     if_debug_chunk('6', "[6]marking from chunk", cp);
  561.     SCAN_CHUNK_OBJECTS(cp)
  562.       DO_ALL
  563.         if_debug2('7', " [7]scanning/marking 0x%lx(%lu)\n",
  564.               (ulong)pre, (ulong)size);
  565.         if ( pre->o_type == &st_refs )
  566.           {    ref_packed *rp = (ref_packed *)(pre + 1);
  567.             char *end = (char *)rp + size;
  568.             root.ptype = ptr_ref_type;
  569.             while ( (char *)rp < end )
  570.             {    comp = rp;
  571.                 if ( r_is_packed(rp) )
  572.                   { if ( r_has_pmark(rp) )
  573.                       { r_clear_pmark(rp);
  574.                     more |= gc_trace(&root, pstate);
  575.                       }
  576.                     rp++;
  577.                   }
  578.                 else
  579.                   { if ( r_has_attr((ref *)rp, l_mark) )
  580.                       { r_clear_attrs((ref *)rp, l_mark);
  581.                     more |= gc_trace(&root, pstate);
  582.                       }
  583.                     rp += packed_per_ref;
  584.                   }
  585.             }
  586.           }
  587.         else if ( !o_is_unmarked(pre) )
  588.           {    struct_proc_clear_marks((*proc)) =
  589.               pre->o_type->clear_marks;
  590.             root.ptype = ptr_struct_type;
  591.             comp = pre + 1;
  592.             if ( !o_is_untraced(pre) )
  593.               o_set_unmarked(pre);
  594.             if ( proc != 0 )
  595.               (*proc)(comp, size);
  596.             more |= gc_trace(&root, pstate);
  597.           }
  598.     END_OBJECTS_SCAN
  599.     return more;
  600. }
  601.  
  602. /* Recursively mark from a (root) pointer. */
  603. /* Return -1 if we overflowed the mark stack, */
  604. /* 0 if we completed successfully. */
  605. private int
  606. gc_trace(gs_gc_root_t *rp, gc_state_t *pstate)
  607. {    typedef struct { void *ptr; uint index; bool is_refs; } ms_entry;
  608.     /*
  609.      * We should look for the largest free block to use as a stack
  610.      * (at least on machines with flat addressing), but for now....
  611.      */
  612. #define ms_size 100
  613.     ms_entry mark_stack[ms_size + 1];
  614.     ms_entry _ss *sp = mark_stack;
  615.     ms_entry _ss *stop = mark_stack + ms_size - 1;
  616.     bool ok = true;
  617.     void *nptr = *rp->p;
  618. #define mark_name(i)\
  619.   { name *pname = name_index_ptr(i);\
  620.     if ( !pname->mark )\
  621.      {  pname->mark = 1;\
  622.     if_debug2('8', "  [8]marked name 0x%lx(%u)\n", (ulong)pname, i);\
  623.      }\
  624.   }
  625.  
  626.     /* Initialize the stack */
  627.     sp->ptr = nptr;
  628.     if ( rp->ptype == ptr_ref_type )
  629.         sp->index = 1, sp->is_refs = true;
  630.     else
  631.     {    sp->index = 0, sp->is_refs = false;
  632.         (*rp->ptype->mark)(nptr, pstate);
  633.     }
  634.     while ( sp >= mark_stack )
  635.     {    gs_ptr_type_t ptp;
  636. #ifdef DEBUG
  637.         static const char *dots = "..........";
  638. #define depth_dots\
  639.   (sp >= &mark_stack[10] ? dots : dots + 10 - (sp - mark_stack))
  640. #endif
  641.         if ( !sp->is_refs )    /* struct */
  642.         {    obj_header_t *ptr = sp->ptr;
  643.             ulong osize = pre_obj_contents_size(ptr - 1);
  644.             struct_proc_enum_ptrs((*mproc));
  645.             debug_check_object(ptr - 1, NULL);
  646.             if_debug4('7', " [7]%smarking %s 0x%lx[%u]",
  647.                   depth_dots,
  648.                   struct_type_name_string(ptr[-1].o_type),
  649.                   (ulong)ptr, sp->index);
  650.             mproc = ptr[-1].o_type->enum_ptrs;
  651.             ptp = (mproc == 0 ? (gs_ptr_type_t)0 :
  652.                 (*mproc)(ptr, osize, sp->index++, &nptr));
  653.             if ( ptp == NULL )    /* done with structure */
  654.             {    if_debug0('7', " - done\n");
  655.                 sp--;
  656.                 continue;
  657.             }
  658.             if_debug1('7', " = 0x%lx\n", (ulong)nptr);
  659.             sp[1].index = (ptp == ptr_ref_type ? 1 : 0);
  660.         }
  661.         else            /* refs */
  662.         {    ref_packed *pptr = sp->ptr;
  663.             if_debug3('8', "  [8]%smarking refs 0x%lx[%u]\n",
  664.                   depth_dots, (ulong)pptr, sp->index - 1);
  665. #define rptr ((ref *)pptr)
  666.             if ( r_is_packed(rptr) )
  667.             {    if ( !--(sp->index) ) sp--;
  668.                 else sp->ptr = pptr + 1;
  669.                 if ( r_has_pmark(pptr) )
  670.                     continue;
  671.                 r_set_pmark(pptr);
  672.                 if ( r_packed_is_name(pptr) )
  673.                 {    uint nidx = packed_name_index(pptr);
  674.                     mark_name(nidx);
  675.                 }
  676.                 continue;
  677.             }
  678.             if ( !--(sp->index) ) sp--;
  679.             else sp->ptr = rptr + 1;
  680.             if ( r_has_attr(rptr, l_mark) )
  681.                 continue;
  682.             r_set_attrs(rptr, l_mark);
  683.             switch ( r_type(rptr) )
  684.                {
  685.             /* Struct cases */
  686.             case t_file:
  687.                 nptr = rptr->value.pfile;
  688. rs:                if ( r_has_attr(rptr, a_foreign) )
  689.                     continue;
  690.                 ptp = ptr_struct_type;
  691.                 sp[1].index = 0;
  692.                 break;
  693.             case t_device:
  694.                 nptr = rptr->value.pdevice; goto rs;
  695.             case t_fontID:
  696.             case t_struct:
  697.             case t_astruct:
  698.                 nptr = rptr->value.pstruct; goto rs;
  699.             /* Non-trivial non-struct cases */
  700.             case t_dictionary:
  701.                 nptr = rptr->value.pdict;
  702.                 sp[1].index = sizeof(dict) / sizeof(ref);
  703.                 goto rrp;
  704.             case t_array:
  705.                 nptr = rptr->value.refs;
  706. rr:                if ( (sp[1].index = r_size(rptr)) == 0 )
  707.                 {    /* Set the base pointer to 0, */
  708.                     /* so we never try to relocate it. */
  709.                     rptr->value.refs = 0;
  710.                     continue;
  711.                 }
  712. rrp:                if ( r_has_attr(rptr, a_foreign) )
  713.                     continue;
  714.                 if ( sp == stop )    /* stack overflow */
  715.                 {    ok = false;
  716.                     if_debug0('6', "[6]mark stack overflow\n");
  717.                     continue;
  718.                 }
  719.                 (++sp)->ptr = nptr;
  720.                 sp->is_refs = true;
  721.                 continue;
  722.             case t_mixedarray: case t_shortarray:
  723.                 nptr = (void *)rptr->value.packed; /* discard const */
  724.                 goto rr;
  725.             case t_name:
  726.                 mark_name(name_index(rptr));
  727.                 continue;
  728.             case t_string:
  729.                 if ( r_has_attr(rptr, a_foreign) )
  730.                     continue;
  731.                 gc_string_mark(rptr->value.bytes, r_size(rptr), true, pstate);
  732.                 continue;
  733.             default:        /* includes packed refs */
  734.                 continue;
  735.                }
  736. #undef rptr
  737.         }
  738.         /* Descend into nptr, whose pointer type is ptp. */
  739.         if ( ptp == ptr_ref_type )
  740.             sp[1].is_refs = 1;
  741.         else
  742.         {    if ( !(*ptp->mark)(nptr, pstate) )
  743.                 continue;
  744.             if ( ptp != ptr_struct_type )
  745.               {    /* We assume this is some non-pointer- */
  746.                 /* containing type. */
  747.                 continue;
  748.               }
  749.             sp[1].is_refs = 0;
  750.         }
  751.         if ( sp == stop )
  752.         {    ok = false;
  753.             continue;
  754.         }
  755.         (++sp)->ptr = nptr;
  756.         /* index and is_refs are already set */
  757.     }
  758.     return (!ok ? -1 : 0);
  759. #undef ms_size
  760. }
  761.  
  762. /* Mark a struct.  Return true if new mark. */
  763. private bool
  764. ptr_struct_mark(void *vptr, gc_state_t *ignored)
  765. {    obj_header_t *ptr = vptr;
  766.     if ( vptr == 0 )
  767.         return false;
  768.     ptr--;            /* point to header */
  769.     if ( !o_is_unmarked(ptr) )
  770.         return false;
  771.     o_mark(ptr);
  772.     return true;
  773. }
  774.  
  775. /* Mark a string.  Return true if new mark. */
  776. private bool
  777. ptr_string_mark(void *vptr, gc_state_t *gcst)
  778. {    return gc_string_mark(((gs_string *)vptr)->data,
  779.                   ((gs_string *)vptr)->size,
  780.                   true, gcst);
  781. }
  782.  
  783. /* Finish tracing by marking names. */
  784. private bool
  785. gc_trace_finish(gc_state_t *pstate)
  786. {    uint count = name_count();
  787.     bool marked = false;
  788.     register uint c;
  789.     for ( c = 0; c < count; c++ )
  790.     {    uint i = name_count_to_index(c);
  791.         name *pname = name_index_ptr(i);
  792.         if ( pname->mark )
  793.         {    if ( !pname->foreign_string && gc_string_mark(pname->string_bytes, pname->string_size, true, pstate) )
  794.                 marked = true;
  795.             marked |= ptr_struct_mark(name_index_ptr_sub_table(i, pname), pstate);
  796.         }
  797.     }
  798.     return marked;
  799. }
  800.  
  801. /* ------ Relocation planning phase ------ */
  802.  
  803. /* Initialize the relocation information in the chunk header. */
  804. private void
  805. gc_init_reloc(chunk_t *cp)
  806. {    chunk_head_t *chead = cp->chead;
  807.     chead->dest = cp->cbase;
  808.     chead->free.o_back =
  809.       offset_of(chunk_head_t, free) >> obj_back_shift;
  810.     chead->free.o_size = sizeof(obj_header_t);
  811.     chead->free.o_nreloc = 0;
  812. }
  813.  
  814. /* Set marks and clear relocation for chunks that won't be compacted. */
  815. private void
  816. gc_clear_reloc(chunk_t *cp)
  817. {    gc_init_reloc(cp);
  818.     SCAN_CHUNK_OBJECTS(cp)
  819.       DO_ALL
  820.         const struct_shared_procs_t _ds *procs =
  821.             pre->o_type->shared;
  822.         if ( procs != 0 )
  823.           (*procs->clear_reloc)(pre, size);
  824.         o_set_untraced(pre);
  825.     END_OBJECTS_SCAN
  826.     gc_strings_set_marks(cp, true);
  827.     gc_strings_clear_reloc(cp);
  828. }
  829.  
  830. /* Set the relocation for the objects in a chunk. */
  831. /* This will never be called for a chunk with any o_untraced objects. */
  832. private void
  833. gc_objects_set_reloc(chunk_t *cp)
  834. {    uint reloc = 0;
  835.     chunk_head_t *chead = cp->chead;
  836.     byte *pfree = (byte *)&chead->free;    /* most recent free object */
  837.     if_debug_chunk('6', "[6]setting reloc for chunk", cp);
  838.     gc_init_reloc(cp);
  839.     SCAN_CHUNK_OBJECTS(cp)
  840.       DO_ALL
  841.         struct_proc_finalize((*finalize));
  842.         const struct_shared_procs_t _ds *procs =
  843.           pre->o_type->shared;
  844.         if ( (procs == 0 ? o_is_unmarked(pre) :
  845.               !(*procs->set_reloc)(pre, reloc, size))
  846.            )
  847.           {    /* Free object */
  848.             reloc += sizeof(obj_header_t) + obj_align_round(size);
  849.             if ( (finalize = pre->o_type->finalize) != 0 )
  850.               (*finalize)(pre + 1);
  851.             if ( pre->o_large )
  852.               {    /* We should chop this up into small */
  853.                 /* free blocks, but there's no value */
  854.                 /* in doing this right now. */
  855.                 o_set_unmarked_large(pre);
  856.               }
  857.             else
  858.               {    pfree = (byte *)pre;
  859.                 pre->o_back =
  860.                   (pfree - (byte *)chead) >> obj_back_shift;
  861.                 pre->o_nreloc = reloc;
  862.               }
  863.             if_debug3('7', " [7]at 0x%lx, unmarked %lu, new reloc = %u\n",
  864.                   (ulong)pre, (ulong)size, reloc);
  865.           }
  866.         else
  867.           {    /* Useful object */
  868.             debug_check_object(pre, cp);
  869.             if ( pre->o_large )
  870.               {    if ( o_is_unmarked_large(pre) )
  871.                   o_mark_large(pre);
  872.               }
  873.             else
  874.               pre->o_back =
  875.                 ((byte *)pre - pfree) >> obj_back_shift;
  876.           }
  877.     END_OBJECTS_SCAN
  878. #ifdef DEBUG
  879.     if ( reloc != 0 )
  880.     { if_debug1('6', "[6]freed %u", reloc);
  881.       if_debug_chunk('6', " in", cp);
  882.     }
  883. #endif
  884. }
  885.  
  886. /* ------ Relocation phase ------ */
  887.  
  888. /* Relocate the pointers in all the objects in a chunk. */
  889. private void
  890. gc_do_reloc(chunk_t *cp, gs_ref_memory_t *mem, gc_state_t *pstate)
  891. {    chunk_head_t *chead = cp->chead;
  892.     if_debug_chunk('6', "[6]relocating in chunk", cp);
  893.     SCAN_CHUNK_OBJECTS(cp)
  894.       DO_ALL
  895.         /* We need to relocate the pointers in an object iff */
  896.         /* it is o_untraced, or it is a useful object. */
  897.         /* An object is free iff its back pointer points to */
  898.         /* the chunk_head structure. */
  899.         if ( o_is_untraced(pre) ||
  900.              (pre->o_large ? !o_is_unmarked(pre) :
  901.               pre->o_back << obj_back_shift !=
  902.                 (byte *)pre - (byte *)chead)
  903.            )
  904.           {    struct_proc_reloc_ptrs((*proc)) =
  905.                 pre->o_type->reloc_ptrs;
  906.             if_debug3('7',
  907.                   " [7]relocating ptrs in %s(%lu) 0x%lx\n",
  908.                   struct_type_name_string(pre->o_type),
  909.                   (ulong)size, (ulong)pre);
  910.             if ( proc != 0 )
  911.                 (*proc)(pre + 1, size, pstate);
  912.           }
  913.     END_OBJECTS_SCAN
  914. }
  915.  
  916. /* Print pointer relocation if debugging. */
  917. #ifdef DEBUG
  918. void *
  919. print_reloc_proc(void *obj, const char *cname, void *robj)
  920. {    if_debug3('9', "  [9]relocate %s * 0x%lx to 0x%lx\n",
  921.           cname, (ulong)obj, (ulong)robj);
  922.     return robj;
  923. }
  924. #endif
  925.  
  926. /* Relocate a pointer to an (aligned) object. */
  927. void * /* obj_header_t * */
  928. gs_reloc_struct_ptr(void * /* obj_header_t * */ obj, gc_state_t *gcst)
  929. {    void *robj;
  930.     if ( obj == 0 )
  931.       return print_reloc(obj, "NULL", 0);
  932. #define optr ((obj_header_t *)obj)
  933.     debug_check_object(optr - 1, NULL);
  934.     /* The following should be a conditional expression, */
  935.     /* but Sun's cc compiler can't handle it. */
  936.     if ( optr[-1].o_large )
  937.       robj = obj;
  938.     else
  939.       {    uint back = optr[-1].o_back;
  940.         if ( back == o_untraced )
  941.           robj = obj;
  942.         else
  943.           {    obj_header_t *pfree = (obj_header_t *)
  944.               ((char *)(optr - 1) - (back << obj_back_shift));
  945.             chunk_head_t *chead = (chunk_head_t *)
  946.               ((char *)pfree - (pfree->o_back << obj_back_shift));
  947.             robj = chead->dest +
  948.               ((char *)obj - (char *)(chead + 1) - pfree->o_nreloc);
  949. #ifdef DEBUG
  950.             /* Do some sanity checking. */
  951.             if ( back > gcst->local->chunk_size >> obj_back_shift )
  952.               {    lprintf2("Invalid back pointer %u at 0x%lx!\n",
  953.                      back, (ulong)obj);
  954.                 exit(1);
  955.               }
  956. #endif
  957.           }
  958.       }
  959.     return print_reloc(obj,
  960.                struct_type_name_string(optr[-1].o_type),
  961.                robj);
  962. #undef optr
  963. }
  964.  
  965. /* ------ Compaction phase ------ */
  966.  
  967. /* Compact the objects in a chunk. */
  968. /* This will never be called for a chunk with any o_untraced objects. */
  969. private void
  970. gc_objects_compact(chunk_t *cp, gc_state_t *gcst)
  971. {    chunk_head_t *chead = cp->chead;
  972.     obj_header_t *dpre = (obj_header_t *)chead->dest;
  973.     SCAN_CHUNK_OBJECTS(cp)
  974.       DO_ALL
  975.         /* An object is free iff its back pointer points to */
  976.         /* the chunk_head structure. */
  977.         if ( (pre->o_large ? !o_is_unmarked(pre) :
  978.               pre->o_back << obj_back_shift !=
  979.                 (byte *)pre - (byte *)chead)
  980.            )
  981.           {    const struct_shared_procs_t _ds *procs =
  982.               pre->o_type->shared;
  983.             debug_check_object(pre, cp);
  984.             if_debug4('7',
  985.                   " [7]compacting %s 0x%lx(%lu) to 0x%lx\n",
  986.                   struct_type_name_string(pre->o_type),
  987.                   (ulong)pre, (ulong)size, (ulong)dpre);
  988.             if ( procs == 0 )
  989.               { if ( dpre != pre )
  990.                   memmove(dpre, pre,
  991.                       sizeof(obj_header_t) + size);
  992.               }
  993.             else
  994.               (*procs->compact)(pre, dpre, size);
  995.             dpre = (obj_header_t *)
  996.               ((byte *)dpre + obj_size_round(size));
  997.           }
  998.     END_OBJECTS_SCAN
  999.     if ( cp->outer == 0 && chead->dest != cp->cbase )
  1000.       dpre = (obj_header_t *)cp->cbase; /* compacted this chunk into another */
  1001.     if ( gs_alloc_debug )
  1002.       memset(dpre, gs_alloc_fill_collected, cp->cbot - (byte *)dpre);
  1003.     cp->cbot = (byte *)dpre;
  1004.     cp->rcur = 0;
  1005.     cp->rtop = 0;        /* just to be sure */
  1006. }
  1007.  
  1008. /* ------ Cleanup ------ */
  1009.  
  1010. /* Free empty chunks. */
  1011. private void
  1012. gc_free_empty_chunks(gs_ref_memory_t *mem)
  1013. {    chunk_t *cp;
  1014.     chunk_t *csucc;
  1015.     /* Free the chunks in reverse order, */
  1016.     /* to encourage LIFO behavior. */
  1017.     for ( cp = mem->clast; cp != 0; cp = csucc )
  1018.     {    /* Make sure this isn't an inner chunk, */
  1019.         /* or a chunk that has inner chunks. */
  1020.         csucc = cp->cprev;     /* save before freeing */
  1021.         if ( cp->cbot == cp->cbase && cp->ctop == cp->climit &&
  1022.              cp->outer == 0 && cp->inner_count == 0
  1023.            )
  1024.           {    alloc_free_chunk(cp, mem);
  1025.             if ( mem->pcc == cp )
  1026.               mem->pcc = 0;
  1027.           }
  1028.     }
  1029. }
  1030.  
  1031. /* ------ Initialization procedure ------ */
  1032.  
  1033. op_def igc_l2_op_defs[] = {
  1034.         op_def_begin_level2(),
  1035.     op_def_end(igc_init)
  1036. };
  1037.