home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 February / PCWK0296.iso / sharewar / dos / program / gs300sr1 / gs300sr1.exe / IALLOC.C < prev    next >
C/C++ Source or Header  |  1994-07-27  |  30KB  |  949 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. /* ialloc.c */
  20. /* Memory allocator for Ghostscript interpreter */
  21. #include "gx.h"
  22. #include "memory_.h"
  23. #include "errors.h"
  24. #include "gsstruct.h"
  25. #include "gxarith.h"            /* for small_exact_log2 */
  26. #include "iref.h"            /* must precede iastate.h */
  27. #include "iastate.h"
  28. #include "store.h"
  29.  
  30. /* The structure descriptor for allocators.  Even though allocators */
  31. /* are allocated outside GC space, they reference objects within it. */
  32. /* The procedures are exported for the alloc_save_t subclass. */
  33. private_st_ref_memory();
  34. #define mptr ((gs_ref_memory_t *)vptr)
  35. ENUM_PTRS_BEGIN(ref_memory_enum_ptrs) return 0;
  36.     ENUM_PTR(0, gs_ref_memory_t, changes);
  37.     ENUM_PTR(1, gs_ref_memory_t, saved);
  38. ENUM_PTRS_END
  39. RELOC_PTRS_BEGIN(ref_memory_reloc_ptrs) {
  40.     RELOC_PTR(gs_ref_memory_t, changes);
  41.     /* Don't relocate the pointer now -- see igc.c for details. */
  42.     mptr->reloc_saved = gs_reloc_struct_ptr(mptr->saved, gcst);
  43. } RELOC_PTRS_END
  44.  
  45. /* Import the debugging variables from gsmemory.c. */
  46. extern byte gs_alloc_fill_alloc;
  47. extern byte gs_alloc_fill_free;
  48.  
  49. /* Forward references */
  50. private gs_ref_memory_t *ialloc_alloc_state(P2(gs_memory_t *, uint));
  51. private obj_header_t *alloc_obj(P4(gs_ref_memory_t *, ulong, gs_memory_type_ptr_t, client_name_t));
  52. private chunk_t *alloc_add_chunk(P4(gs_ref_memory_t *, ulong, bool, client_name_t));
  53. void alloc_close_chunk(P1(gs_ref_memory_t *));
  54. private void alloc_close_refs(P1(chunk_t *));
  55.  
  56. /* Define the quantum of allocation for strings. */
  57. #define string_data_quantum 32
  58. #define string_block_quantum (string_data_quantum + (string_data_quantum / 8) + sizeof(ushort))
  59.  
  60. /*
  61.  * Define the standard implementation (for the interpreter)
  62.  * of Ghostscript's memory manager interface.
  63.  */
  64. private gs_memory_proc_alloc_bytes(i_alloc_bytes);
  65. private gs_memory_proc_alloc_struct(i_alloc_struct);
  66. private gs_memory_proc_alloc_byte_array(i_alloc_byte_array);
  67. private gs_memory_proc_alloc_struct_array(i_alloc_struct_array);
  68. private gs_memory_proc_object_size(i_object_size);
  69. private gs_memory_proc_object_type(i_object_type);
  70. private gs_memory_proc_free_object(i_free_object);
  71. private gs_memory_proc_alloc_string(i_alloc_string);
  72. private gs_memory_proc_resize_string(i_resize_string);
  73. private gs_memory_proc_free_string(i_free_string);
  74. private gs_memory_proc_register_root(i_register_root);
  75. private gs_memory_proc_unregister_root(i_unregister_root);
  76. private gs_memory_proc_status(i_status);
  77. private const gs_memory_procs_t imemory_procs = {
  78.     i_alloc_bytes,
  79.     i_alloc_struct,
  80.     i_alloc_byte_array,
  81.     i_alloc_struct_array,
  82.     i_object_size,
  83.     i_object_type,
  84.     i_free_object,
  85.     i_alloc_string,
  86.     i_resize_string,
  87.     i_free_string,
  88.     i_register_root,
  89.     i_unregister_root,
  90.     i_status
  91. };
  92. /*
  93.  * Define global and local instances.
  94.  */
  95. gs_dual_memory_t gs_imemory;
  96.  
  97. #define imem ((gs_ref_memory_t *)mem)
  98.  
  99. /* Initialize the allocator */
  100. void
  101. ialloc_init(gs_memory_t *mem, uint chunk_size, bool level2)
  102. {    gs_ref_memory_t *ilmem = gs_imemory.local =
  103.         ialloc_alloc_state(mem, chunk_size);
  104.     gs_ref_memory_t *igmem = gs_imemory.global =
  105.         (level2 ?
  106.          ialloc_alloc_state(mem, chunk_size) :
  107.          ilmem);
  108.     gs_ref_memory_t *ismem = gs_imemory.system =
  109.         ialloc_alloc_state(mem, chunk_size);
  110.     gs_imemory.reclaim = 0;
  111.     ilmem->local_attr = a_local;
  112.     igmem->global = ilmem->global = igmem;
  113.     igmem->local_attr = 0;
  114.     ismem->local_attr = 0;
  115.     ialloc_set_local(&gs_imemory, false);
  116. }
  117. /* Allocate the state of an allocator (system, global, or local). */
  118. /* Does not initialize global, local_attr. */
  119. private gs_ref_memory_t *
  120. ialloc_alloc_state(gs_memory_t *parent, uint chunk_size)
  121. {    /* We can't assume that the parent uses the same object header */
  122.     /* that we do, but the GC requires that allocators have */
  123.     /* such a header.  Therefore, we prepend one explicitly. */
  124.     typedef struct _rmo {
  125.       obj_header_t header;
  126.       gs_ref_memory_t memory;
  127.     } gs_ref_memory_object;
  128.     gs_ref_memory_object *memo =
  129.       (gs_ref_memory_object *)
  130.         gs_alloc_bytes(parent, sizeof(gs_ref_memory_object),
  131.                "ialloc_alloc_state");
  132.     gs_ref_memory_t *iimem;
  133.     if ( memo == 0 )
  134.         return 0;
  135.     /* Construct the object header "by hand". */
  136.     memo->header.o_large = 0;
  137.     memo->header.o_size = sizeof(gs_ref_memory_t);
  138.     memo->header.o_type = &st_ref_memory;
  139.     iimem = &memo->memory;
  140.     iimem->procs = imemory_procs;
  141.     iimem->parent = parent;
  142.     iimem->chunk_size = chunk_size;
  143.     iimem->large_size = ((chunk_size / 4) & -obj_align_mod) + 1;
  144.     iimem->gc_status.vm_threshold = chunk_size * 3L;
  145.     iimem->gc_status.max_vm = max_long;
  146.     iimem->gc_status.psignal = NULL;
  147.     iimem->gc_status.enabled = false;
  148.     iimem->previous_status.allocated = 0;
  149.     iimem->previous_status.used = 0;
  150.     ialloc_reset(iimem);
  151.     ialloc_set_limit(iimem);
  152.     iimem->cc.cbot = iimem->cc.ctop = 0;
  153.     iimem->pcc = 0;
  154.     iimem->roots = 0;
  155.     iimem->num_contexts = 1;
  156.     iimem->saved = 0;
  157.     return iimem;
  158. }
  159. /* Initialize after a save. */
  160. void
  161. ialloc_reset(gs_ref_memory_t *mem)
  162. {    mem->cfirst = 0;
  163.     mem->clast = 0;
  164.     mem->cc.rcur = 0;
  165.     mem->cc.rtop = 0;
  166.     mem->cc.has_refs = false;
  167.     mem->allocated = 0;
  168.     mem->changes = 0;
  169.     ialloc_reset_free(mem);
  170. }
  171. /* Initialize after a save or GC. */
  172. void
  173. ialloc_reset_free(gs_ref_memory_t *mem)
  174. {    int i;
  175.     obj_header_t **p;
  176.     mem->freed_lost = 0;
  177.     mem->cfreed.cp = 0;
  178.     for ( i = 0, p = &mem->freelists[0]; i < num_freelists; i++, p++ )
  179.       *p = 0;
  180. }
  181. /* Set the allocation limit after a change in one or more of */
  182. /* vm_threshold, max_vm, or enabled, or after a GC. */
  183. void
  184. ialloc_set_limit(register gs_ref_memory_t *mem)
  185. {    /*
  186.      * The following code is intended to set the limit so that
  187.      * we stop allocating when allocated + previous_status.allocated
  188.      * exceeds the lesser of max_vm or (if GC is enabled)
  189.      * gc_allocated + vm_threshold.
  190.      */
  191.     ulong max_allocated =
  192.       (mem->gc_status.max_vm > mem->previous_status.allocated ?
  193.        mem->gc_status.max_vm - mem->previous_status.allocated :
  194.        0);
  195.     if ( mem->gc_status.enabled )
  196.       {    ulong limit = mem->gc_allocated + mem->gc_status.vm_threshold;
  197.         if ( limit < mem->previous_status.allocated )
  198.           mem->limit = 0;
  199.         else
  200.           {    limit -= mem->previous_status.allocated;
  201.             mem->limit = min(limit, max_allocated);
  202.           }
  203.       }
  204.     else
  205.       mem->limit = max_allocated;
  206. }
  207.  
  208. /* ================ Accessors ================ */
  209.  
  210. /* Get the size of an object from the header. */
  211. private uint
  212. i_object_size(gs_memory_t *mem, const void /*obj_header_t*/ *obj)
  213. {    return pre_obj_contents_size((obj_header_t *)obj - 1);
  214. }
  215.  
  216. /* Get the type of a structure from the header. */
  217. private gs_memory_type_ptr_t
  218. i_object_type(gs_memory_t *mem, const void /*obj_header_t*/ *obj)
  219. {    return ((obj_header_t *)obj - 1)->o_type;
  220. }
  221.  
  222. /* Get the GC status of a memory. */
  223. void
  224. gs_memory_gc_status(const gs_ref_memory_t *mem, gs_memory_gc_status_t *pstat)
  225. {    *pstat = mem->gc_status;
  226. }
  227.  
  228. /* Set the GC status of a memory. */
  229. void
  230. gs_memory_set_gc_status(gs_ref_memory_t *mem, const gs_memory_gc_status_t *pstat)
  231. {    mem->gc_status = *pstat;
  232.     ialloc_set_limit(mem);
  233. }
  234.  
  235. /* ================ Objects ================ */
  236.  
  237. /* Allocate a small object fast if possible. */
  238. /* The size must be substantially less than max_uint. */
  239. /* ptr must be declared as obj_header_t *. */
  240. /* pfl must be declared as obj_header_t **. */
  241. #define if_not_alloc_small(ptr, imem, size, pstype, pfl)\
  242.     if ( size <= max_freelist_size &&\
  243.          *(pfl = &imem->freelists[(size + obj_align_mask) >> log2_obj_align_mod]) != 0\
  244.        )\
  245.     {    ptr = *pfl;\
  246.         *pfl = *(obj_header_t **)ptr;\
  247.         ptr[-1].o_size = size;\
  248.         ptr[-1].o_type = pstype;\
  249.         if ( gs_alloc_debug )\
  250.           { /* Clear the block in an attempt to track down */\
  251.             /* uninitialized data errors. */\
  252.             memset(ptr, gs_alloc_fill_alloc, size);\
  253.           }\
  254.     }\
  255.     else if ( (imem->cc.ctop - (byte *)(ptr = (obj_header_t *)imem->cc.cbot))\
  256.         >= size + (obj_align_mod + sizeof(obj_header_t) * 2) &&\
  257.          size < imem->large_size\
  258.        )\
  259.     {    imem->cc.cbot = (byte *)ptr + obj_size_round(size);\
  260.         ptr->o_large = 0;\
  261.         ptr->o_size = size;\
  262.         ptr->o_type = pstype;\
  263.         ptr++;\
  264.         if ( gs_alloc_debug )\
  265.           { /* Clear the block in an attempt to track down */\
  266.             /* uninitialized data errors. */\
  267.             memset(ptr, gs_alloc_fill_alloc, size);\
  268.           }\
  269.     }\
  270.     else
  271.  
  272. private byte *
  273. i_alloc_bytes(gs_memory_t *mem, uint size, client_name_t cname)
  274. {    obj_header_t *obj;
  275.     obj_header_t **pfl;
  276.     if_not_alloc_small(obj, imem, size, &st_bytes, pfl)
  277.     {    obj = alloc_obj(imem, size, &st_bytes, cname);
  278.         if ( obj == 0 )
  279.             return 0;
  280.     }
  281.     if_debug3('A', "[a:#< ]%s -bytes-(%u) = 0x%lx\n",
  282.           client_name_string(cname), size, (ulong)obj);
  283.     return (byte *)obj;
  284. }
  285. private void *
  286. i_alloc_struct(gs_memory_t *mem, gs_memory_type_ptr_t pstype,
  287.   client_name_t cname)
  288. {    uint size = pstype->ssize;
  289.     obj_header_t *obj;
  290.     obj_header_t **pfl;
  291.     if_not_alloc_small(obj, imem, size, pstype, pfl)
  292.     {    obj = alloc_obj(imem, size, pstype, cname);
  293.         if ( obj == 0 )
  294.             return 0;
  295.     }
  296.     if_debug4('A', "[a:+< ]%s %s(%u) = 0x%lx\n",
  297.           client_name_string(cname), struct_type_name_string(pstype),
  298.           size, (ulong)obj);
  299.     return (char *)obj;
  300. }
  301. private byte *
  302. i_alloc_byte_array(gs_memory_t *mem, uint num_elements, uint elt_size,
  303.   client_name_t cname)
  304. {    obj_header_t *obj = alloc_obj(imem, (ulong)num_elements * elt_size,
  305.                       &st_bytes, cname);
  306.     if_debug5('A', "[a:#< ]%s -bytes-*(%lu=%u*%u) = 0x%lx\n",
  307.           client_name_string(cname),
  308.           (ulong)num_elements * elt_size,
  309.           num_elements, elt_size, (ulong)obj);
  310.     return (byte *)obj;
  311. }
  312. private void *
  313. i_alloc_struct_array(gs_memory_t *mem, uint num_elements,
  314.   gs_memory_type_ptr_t pstype, client_name_t cname)
  315. {    obj_header_t *obj = alloc_obj(imem,
  316.                 (ulong)num_elements * pstype->ssize,
  317.                 pstype, cname);
  318.     if_debug6('A', "[a:+< ]%s %s*(%lu=%u*%u) = 0x%lx\n",
  319.           client_name_string(cname), struct_type_name_string(pstype),
  320.           (ulong)num_elements * pstype->ssize,
  321.           num_elements, pstype->ssize, (ulong)obj);
  322.     return (char *)obj;
  323. }
  324. private void
  325. i_free_object(gs_memory_t *mem, void *ptr, client_name_t cname)
  326. {    obj_header_t *pp;
  327.     struct_proc_finalize((*finalize));
  328.     uint size;
  329.     if ( ptr == 0 )
  330.         return;
  331.     pp = (obj_header_t *)ptr - 1;
  332.     size = pre_obj_contents_size(pp);
  333.     finalize = pp->o_type->finalize;
  334.     if ( finalize != 0 )
  335.         (*finalize)(ptr);
  336.     if ( gs_alloc_debug )
  337.         memset(ptr, gs_alloc_fill_free, size);
  338.     if ( (byte *)ptr + obj_align_round(size) == imem->cc.cbot )
  339.     {    if_debug3('A', "[a:-< ]%s(%u) 0x%lx\n",
  340.               client_name_string(cname), size, (ulong)pp);
  341.         imem->cc.cbot = (byte *)pp;
  342.         return;
  343.     }
  344.     if ( pp->o_large )
  345.     {    /* We gave this object its own chunk. */
  346.         /* Free the entire chunk. */
  347.         chunk_locator_t cl;
  348.         if_debug3('a', "[a:-<L]%s(%u) 0x%lx\n",
  349.               client_name_string(cname), size, (ulong)pp);
  350.         cl.memory = imem;
  351.         cl.cp = 0;
  352.         if ( !chunk_locate_ptr(ptr, &cl) )
  353.         {    /* Something is very wrong! */
  354.             lprintf2("%s: free large 0x%lx chunk not found\n",
  355.                  client_name_string(cname), (ulong)ptr);
  356.             return;
  357.         }
  358.         alloc_free_chunk(cl.cp, imem);
  359.         return;
  360.     }
  361.     if ( size <= max_freelist_size &&
  362.          size >= sizeof(obj_header_t *)
  363.        )
  364.       {    /* Put it on a freelist, unless it belongs to */
  365.         /* an older save level, in which case we mustn't */
  366.         /* overwrite it. */
  367.         imem->cfreed.memory = imem;
  368.         if ( chunk_locate(ptr, &imem->cfreed) )
  369.           {    obj_header_t **pfl =
  370.               &imem->freelists[(size + obj_align_mask) >>
  371.                        log2_obj_align_mod];
  372.             pp->o_type = &st_bytes;    /* don't confuse GC */
  373.             *(obj_header_t **)ptr = *pfl;
  374.             *pfl = (obj_header_t *)ptr;
  375.             if_debug3('A', "[a:F< ]%s(%u) 0x%lx\n",
  376.                   client_name_string(cname),
  377.                   size, (ulong)pp);
  378.             return;
  379.           }
  380.       }
  381.     if_debug3('A', "[a:~< ]%s(%u) 0x%lx\n",
  382.           client_name_string(cname), size, (ulong)pp);
  383.     imem->freed_lost += obj_size_round(size);
  384. }
  385. private byte *
  386. i_alloc_string(gs_memory_t *mem, uint nbytes, client_name_t cname)
  387. {    byte *str;
  388. top:    if ( imem->cc.ctop - imem->cc.cbot > nbytes )
  389.     {    if_debug3('A', "[a:+> ]%s(%u) = 0x%lx\n",
  390.               client_name_string(cname), nbytes,
  391.               (ulong)(imem->cc.ctop - nbytes));
  392.         return (imem->cc.ctop -= nbytes);
  393.     }
  394.     if ( nbytes > max_uint - (obj_align_mod - 1) )
  395.     {    /* Can't represent the size in a uint! */
  396.         return 0;
  397.     }
  398.     if ( nbytes >= imem->large_size )
  399.     {    /* Give it a chunk all its own. */
  400.         uint asize = (nbytes + (string_data_quantum - 1)) /
  401.           string_data_quantum * string_block_quantum +
  402.             sizeof(chunk_head_t);
  403.         chunk_t *cp =
  404.           alloc_add_chunk(imem, (ulong)asize, true,
  405.                   "large string chunk");
  406.         if ( cp == 0 )
  407.             return 0;
  408.         str = cp->ctop = cp->climit - nbytes;
  409.         if_debug3('a', "[a:+>L]%s(%u) = 0x%lx\n",
  410.               client_name_string(cname), nbytes, (ulong)str);
  411.     }
  412.     else
  413.     {    /* Add another chunk. */
  414.         chunk_t *cp =
  415.           alloc_add_chunk(imem, (ulong)imem->chunk_size, true,
  416.                   "chunk");
  417.         if ( cp == 0 )
  418.             return 0;
  419.         alloc_close_chunk(imem);
  420.         imem->pcc = cp;
  421.         imem->cc = *imem->pcc;
  422.         goto top;
  423.     }
  424.     if ( gs_alloc_debug )
  425.       { /* Clear the block in an attempt to track down */
  426.         /* uninitialized data errors. */
  427.         memset(str, gs_alloc_fill_alloc, nbytes);
  428.       }
  429.     return str;
  430. }
  431. private byte *
  432. i_resize_string(gs_memory_t *mem, byte *data, uint old_num, uint new_num,
  433.   client_name_t cname)
  434. {    byte *ptr;
  435.     if ( data == imem->cc.ctop &&
  436.            (new_num < old_num ||
  437.         imem->cc.ctop - imem->cc.cbot > new_num - old_num)
  438.        )
  439.     {    /* Resize in place. */
  440.         register uint i;
  441.         ptr = data + old_num - new_num;
  442.         if_debug5('A', "[a:%c> ]%s(%u->%u) 0x%lx\n",
  443.               (new_num > old_num ? '>' : '<'),
  444.               client_name_string(cname), old_num, new_num,
  445.               (ulong)ptr);
  446.         imem->cc.ctop = ptr;
  447.         if ( new_num < old_num )
  448.           for ( i = new_num; i > 0; ) --i, ptr[i] = data[i];
  449.         else
  450.           for ( i = 0; i < old_num; ) ptr[i] = data[i], i++;
  451.     }
  452.     else
  453.     {    /* Punt. */
  454.         ptr = gs_alloc_string(mem, new_num, cname);
  455.         if ( ptr == 0 )
  456.           return 0;
  457.         memcpy(ptr, data, min(old_num, new_num));
  458.         gs_free_string(mem, data, old_num, cname);
  459.     }
  460.     return ptr;
  461. }
  462. private void
  463. i_free_string(gs_memory_t *mem, byte *data, uint nbytes,
  464.   client_name_t cname)
  465. {    if ( data == imem->cc.ctop )
  466.     {    if_debug3('A', "[a:-> ]%s(%u) 0x%lx\n",
  467.               client_name_string(cname), nbytes, (ulong)data);
  468.         imem->cc.ctop += nbytes;
  469.     }
  470.     else
  471.     {    if_debug3('A', "[a:~> ]%s(%u) 0x%lx\n",
  472.               client_name_string(cname), nbytes, (ulong)data);
  473.         imem->freed_lost += nbytes;
  474.     }
  475. }
  476. private void
  477. i_status(gs_memory_t *mem, gs_memory_status_t *pstat)
  478. {    ulong unused = 0;
  479.     chunk_t *cp = imem->cfirst;
  480.     alloc_close_chunk(imem);
  481.     while ( cp != 0 )
  482.     {    unused += cp->ctop - cp->cbot;
  483.         cp = cp->cnext;
  484.     }
  485.     pstat->used = imem->allocated - unused - imem->freed_lost +
  486.       imem->previous_status.used;
  487.     pstat->allocated = imem->allocated +
  488.       imem->previous_status.allocated;
  489. }
  490.  
  491. /* ------ Internal procedures ------ */
  492.  
  493. /* Allocate an object.  This handles all but the fastest, simplest case. */
  494. private obj_header_t *
  495. alloc_obj(gs_ref_memory_t *mem, ulong lsize, gs_memory_type_ptr_t pstype,
  496.   client_name_t cname)
  497. {    obj_header_t *ptr;
  498.     if ( lsize >= mem->large_size )
  499.     {    ulong asize =
  500.           ((lsize + obj_align_mask) & -obj_align_mod) +
  501.             sizeof(obj_header_t);
  502.         /* Give it a chunk all its own. */
  503.         chunk_t *cp =
  504.           alloc_add_chunk(mem, asize + sizeof(chunk_head_t), false,
  505.                   "large object chunk");
  506.         if ( cp == 0 )
  507.             return 0;
  508.         ptr = (obj_header_t *)cp->cbot;
  509.         cp->cbot += asize;
  510.         if_debug3('a', "[a:+<L]%s(%lu) = 0x%lx\n",
  511.               client_name_string(cname), lsize, (ulong)ptr);
  512.         ptr->o_large = 1;
  513.         pre_obj_set_large_size(ptr, lsize);
  514.         if ( pstype == &st_refs )
  515.           cp->has_refs = true;
  516.     }
  517.     else
  518.     {    uint asize = obj_size_round((uint)lsize);
  519.         while ( mem->cc.ctop -
  520.              (byte *)(ptr = (obj_header_t *)mem->cc.cbot)
  521.               <= asize + sizeof(obj_header_t) )
  522.         {    /* Add another chunk. */
  523.             chunk_t *cp =
  524.               alloc_add_chunk(mem, (ulong)mem->chunk_size,
  525.                       true, "chunk");
  526.             if ( cp == 0 )
  527.                 return 0;
  528.             alloc_close_chunk(mem);
  529.             mem->pcc = cp;
  530.             mem->cc = *mem->pcc;
  531.         }
  532.         mem->cc.cbot = (byte *)ptr + asize;
  533.         ptr->o_large = 0;
  534.         ptr->o_size = (uint)lsize;
  535.     }
  536.     ptr->o_type = pstype;
  537.     ptr++;
  538.     if ( gs_alloc_debug )
  539.       { /* Clear the block in an attempt to track down */
  540.         /* uninitialized data errors. */
  541.         /* Note that the block may be too large for a single memset. */
  542.         ulong msize = lsize;
  543.         char *p = (char *)ptr;
  544.         int isize;
  545.         for ( ; msize; msize -= isize, p += isize )
  546.           { isize = min(msize, max_int);
  547.         memset(p, gs_alloc_fill_alloc, isize);
  548.           }
  549.       }
  550.     return ptr;
  551. }
  552.  
  553. /* ================ Roots ================ */
  554.  
  555. /* Register a root. */
  556. private void
  557. i_register_root(gs_memory_t *mem, gs_gc_root_t *rp, gs_ptr_type_t ptype,
  558.   void **up, client_name_t cname)
  559. {    if_debug3('8', "[8]register root(%s) 0x%lx -> 0x%lx\n",
  560.          client_name_string(cname), (ulong)rp, (ulong)up);
  561.     rp->ptype = ptype, rp->p = up;
  562.     rp->next = imem->roots, imem->roots = rp;
  563. }
  564.  
  565. /* Unregister a root. */
  566. private void
  567. i_unregister_root(gs_memory_t *mem, gs_gc_root_t *rp, client_name_t cname)
  568. {    gs_gc_root_t **rpp = &imem->roots;
  569.     if_debug2('8', "[8]unregister root(%s) 0x%lx\n",
  570.         client_name_string(cname), (ulong)rp);
  571.     while ( *rpp != rp ) rpp = &(*rpp)->next;
  572.     *rpp = (*rpp)->next;
  573. }
  574.  
  575. /* ================ Local/global VM ================ */
  576.  
  577. /* Get the local/global attribute of an allocator */
  578. uint
  579. imemory_local_attr(gs_ref_memory_t *iimem)
  580. {    return iimem->local_attr;
  581. }
  582.  
  583. /* Select the current local or global allocator. */
  584. void
  585. ialloc_set_local(gs_dual_memory_t *dmem, bool local)
  586. {    gs_ref_memory_t *mem = (local ? dmem->local : dmem->global);
  587.     dmem->current = mem;
  588.     dmem->local_mask = mem->local_attr;
  589. }
  590.  
  591. /* Reset the requests. */
  592. void
  593. ialloc_reset_requested(gs_dual_memory_t *dmem)
  594. {    dmem->global->gc_status.requested = 0;
  595.     dmem->local->gc_status.requested = 0;
  596. }
  597.  
  598. /* ================ Refs ================ */
  599.  
  600. /*
  601.  * As noted in iastate.h, every run of refs has an extra ref at the end
  602.  * to hold relocation information for the garbage collector;
  603.  * since sizeof(ref) % obj_align_mod == 0, we never need to
  604.  * allocate any additional padding space at the end of the block.
  605.  */
  606.         
  607. /* Allocate an array of refs. */
  608. int
  609. gs_alloc_ref_array(gs_ref_memory_t *mem, ref *parr, uint attrs,
  610.   uint num_refs, client_name_t cname)
  611. {    ref *obj;
  612.     /* If we're allocating a run of refs already, use it. */
  613.     if ( mem->cc.rtop == mem->cc.cbot &&
  614.          num_refs < (mem->cc.ctop - mem->cc.cbot) / sizeof(ref)
  615.        )
  616.       {    obj = (ref *)mem->cc.rtop - 1;    /* back up over last ref */
  617.         if_debug3('A', "[a:+$ ]%s(%u) = 0x%lx\n",
  618.               client_name_string(cname), num_refs, (ulong)obj);
  619.         mem->cc.rtop = mem->cc.cbot += num_refs * sizeof(ref);
  620.       }
  621.     else
  622.       {    /* Use a new run.  We have to be careful, because */
  623.         /* the new run might stay in the same chunk, create a new */
  624.         /* current chunk, or allocate a separate large chunk. */
  625.         byte *top = mem->cc.cbot;
  626.         chunk_t *pcc = mem->pcc;
  627.         obj = gs_alloc_struct_array((gs_memory_t *)mem, num_refs + 1,
  628.                         ref, &st_refs, cname);
  629.         if ( obj == 0 )
  630.           return_error(e_VMerror);
  631.         if ( mem->cc.cbot == top )
  632.           {    /* We allocated a separate large chunk. */
  633.             /* Set the terminating ref now. */
  634.             /* alloc_obj made a special check to set has_refs. */
  635.             ref *end = (ref *)obj + num_refs;
  636.             make_mark(end);
  637.           }
  638.         else
  639.           {    if ( mem->pcc == pcc )
  640.                 alloc_close_refs(&mem->cc);
  641.             else if ( pcc != 0 )
  642.                 alloc_close_refs(pcc);
  643.             mem->cc.rcur = (obj_header_t *)obj;
  644.             mem->cc.rtop = mem->cc.cbot;
  645.             mem->cc.has_refs = true;
  646.           }
  647.       }
  648.     make_array(parr, attrs | mem->local_attr, num_refs, obj);
  649.     return 0;
  650. }
  651.  
  652. /* Resize an array of refs.  Currently this is only implemented */
  653. /* for shrinking, not for growing. */
  654. int
  655. gs_resize_ref_array(gs_ref_memory_t *mem, ref *parr,
  656.   uint new_num_refs, client_name_t cname)
  657. {    uint old_num_refs = r_size(parr);
  658.     uint diff;
  659.     ref *obj = parr->value.refs;
  660.     if ( new_num_refs > old_num_refs || !r_has_type(parr, t_array) )
  661.       return_error(e_Fatal);
  662.     diff = old_num_refs - new_num_refs;
  663.     /* Check for LIFO.  See gs_free_ref_array for more details. */
  664.     if ( mem->cc.rtop == mem->cc.cbot &&
  665.          (byte *)(obj + (old_num_refs + 1)) == mem->cc.rtop
  666.        )
  667.       {    /* Shorten the refs object. */
  668.         if_debug3('A', "[a:-/ ]%s(%u) 0x%lx\n",
  669.               client_name_string(cname), diff, (ulong)obj);
  670.         mem->cc.cbot = mem->cc.rtop -= diff * sizeof(ref);
  671.       }
  672.     else
  673.       {    /* Punt. */
  674.         if_debug3('A', "[a:~/ ]%s(%u) 0x%lx\n",
  675.               client_name_string(cname), diff, (ulong)obj);
  676.         imem->freed_lost += diff * sizeof(ref);
  677.       }
  678.     r_set_size(parr, new_num_refs);
  679.     return 0;
  680. }
  681.  
  682. /* Deallocate an array of refs.  Only do this if LIFO. */
  683. void
  684. gs_free_ref_array(gs_ref_memory_t *mem, ref *parr, client_name_t cname)
  685. {    uint num_refs = r_size(parr);
  686.     ref *obj = parr->value.refs;
  687.     /*
  688.      * Compute the storage size of the array, and check for LIFO
  689.      * freeing.  Note that the array might be packed;
  690.      * for the moment, if it's anything but a t_array, punt.
  691.      * The +1s are for the extra ref for the GC.
  692.      */
  693.     if ( r_has_type(parr, t_array) &&
  694.           mem->cc.rtop == mem->cc.cbot &&
  695.           (byte *)(obj + (num_refs + 1)) == mem->cc.rtop
  696.        )
  697.       {    if ( (obj_header_t *)obj == mem->cc.rcur )
  698.           {    /* Deallocate the entire refs object. */
  699.             gs_free_object((gs_memory_t *)mem, obj, cname);
  700.             mem->cc.rcur = 0;
  701.             mem->cc.rtop = 0;
  702.           }
  703.         else
  704.           {    /* Deallocate it at the end of the refs object. */
  705.             if_debug3('A', "[a:-$ ]%s(%u) 0x%lx\n",
  706.                   client_name_string(cname), num_refs,
  707.                   (ulong)obj);
  708.             mem->cc.rtop = mem->cc.cbot = (byte *)(obj + 1);
  709.           }
  710.       }
  711.     else
  712.       {    /* Punt. */
  713.         if_debug3('A', "[a:~$ ]%s(%u) 0x%lx\n",
  714.               client_name_string(cname), num_refs, (ulong)obj);
  715.         imem->freed_lost += num_refs * sizeof(ref);
  716.       }
  717. }
  718.  
  719. /* Allocate a string ref. */
  720. int
  721. gs_alloc_string_ref(gs_ref_memory_t *mem, ref *psref,
  722.   uint attrs, uint nbytes, client_name_t cname)
  723. {    byte *str = gs_alloc_string((gs_memory_t *)mem, nbytes, cname);
  724.     if ( str == 0 )
  725.       return_error(e_VMerror);
  726.     make_string(psref, attrs | mem->local_attr, nbytes, str);
  727.     return 0;
  728. }
  729.  
  730. /* ================ Chunks ================ */
  731.  
  732. public_st_chunk();
  733.  
  734. /* Insert a chunk in the chain.  This is exported for the GC. */
  735. void
  736. alloc_link_chunk(chunk_t *cp, gs_ref_memory_t *mem)
  737. {    byte *cdata = cp->cbase;
  738.     chunk_t *icp;
  739.     chunk_t *prev;
  740.     for ( icp = mem->cfirst; icp != 0 && ptr_ge(cdata, icp->ctop);
  741.           icp = icp->cnext
  742.         )
  743.         ;
  744.     cp->cnext = icp;
  745.     if ( icp == 0 )            /* add at end of chain */
  746.     {    prev = imem->clast;
  747.         imem->clast = cp;
  748.     }
  749.     else                /* insert before icp */
  750.     {    prev = icp->cprev;
  751.         icp->cprev = cp;
  752.     }
  753.     cp->cprev = prev;
  754.     if ( prev == 0 )
  755.         imem->cfirst = cp;
  756.     else
  757.         prev->cnext= cp;
  758.     if ( imem->pcc != 0 )
  759.     {    imem->cc.cnext = imem->pcc->cnext;
  760.         imem->cc.cprev = imem->pcc->cprev;
  761.     }
  762. }
  763.  
  764. /* Allocate a chunk.  If we would exceed MaxLocalVM (if relevant), */
  765. /* or if we would exceed the VMThreshold and psignal is NULL, */
  766. /* return 0; if we would exceed the VMThreshold but psignal is valid, */
  767. /* just set the signal and return successfully. */
  768. private chunk_t *
  769. alloc_add_chunk(gs_ref_memory_t *mem, ulong csize, bool has_strings,
  770.   client_name_t cname)
  771. {    gs_memory_t *parent = mem->parent;
  772.     chunk_t *cp = gs_alloc_struct(parent, chunk_t, &st_chunk, cname);
  773.     byte *cdata;
  774.     /* If csize is larger than max_uint, */
  775.     /* we have to fake it using gs_alloc_byte_array. */
  776.     ulong elt_size = csize;
  777.     uint num_elts = 1;
  778.     if ( mem->allocated >= mem->limit )
  779.       {    mem->gc_status.requested += csize;
  780.         if ( mem->limit >= mem->gc_status.max_vm ||
  781.              mem->gc_status.psignal == 0
  782.            )
  783.             return 0;
  784.         *mem->gc_status.psignal = mem->gc_status.signal_value;
  785.       }
  786.     while ( (uint)elt_size != elt_size )
  787.       elt_size = (elt_size + 1) >> 1,
  788.       num_elts <<= 1;
  789.     cdata = gs_alloc_byte_array(parent, num_elts, elt_size, cname);
  790.     if ( cp == 0 || cdata == 0 )
  791.     {    gs_free_object(parent, cdata, cname);
  792.         gs_free_object(parent, cp, cname);
  793.         mem->gc_status.requested = csize;
  794.         return 0;
  795.     }
  796.     alloc_init_chunk(cp, cdata, cdata + csize, has_strings, (chunk_t *)0);
  797.     alloc_link_chunk(cp, mem);
  798.     mem->allocated += gs_object_size(parent, cdata) + sizeof(chunk_t);
  799.     return cp;
  800. }
  801.  
  802. /* Initialize the pointers in a chunk.  This is exported for save/restore. */
  803. /* The bottom pointer must be aligned,  but the top pointer need not */
  804. /* be aligned. */
  805. void
  806. alloc_init_chunk(chunk_t *cp, byte *bot, byte *top, bool has_strings,
  807.   chunk_t *outer)
  808. {    byte *cdata = bot;
  809.     if ( outer != 0 )
  810.       outer->inner_count++;
  811.     cp->chead = (chunk_head_t *)cdata;
  812.     cdata += sizeof(chunk_head_t);
  813.     cp->cbot = cp->cbase = cdata;
  814.     cp->cend = top;
  815.     cp->rcur = 0;
  816.     cp->rtop = 0;
  817.     cp->outer = outer;
  818.     cp->inner_count = 0;
  819.     cp->has_refs = false;
  820.     cp->sbase = cdata;
  821.     if ( has_strings && top - cdata >= string_block_quantum )
  822.     {    /* We allocate a large enough string marking and reloc table */
  823.         /* to cover the entire chunk. */
  824.         /* We require that the size of allocatable string space */
  825.         /* be a multiple of string_data_quantum. */
  826.         uint nblocks = (top - cdata) / string_block_quantum;
  827.         cp->climit = cdata + nblocks * string_data_quantum;
  828.         cp->smark = cp->climit;
  829.         cp->smark_size = nblocks * (string_data_quantum / 8);
  830.         cp->sreloc = (ushort *)(cp->smark + cp->smark_size);
  831.     }
  832.     else
  833.     {    /* No strings, don't need the string GC tables. */
  834.         cp->climit = cp->cend;
  835.         cp->smark = 0;
  836.         cp->smark_size = 0;
  837.         cp->sreloc = 0;
  838.     }
  839.     cp->ctop = cp->climit;
  840. }
  841.  
  842. /* Close up the current chunk. */
  843. /* This is exported for save/restore and the GC. */
  844. void
  845. alloc_close_chunk(gs_ref_memory_t *mem)
  846. {    alloc_close_refs(&mem->cc);
  847.     if ( mem->pcc != 0 )
  848.     {    *mem->pcc = mem->cc;
  849.         if_debug_chunk('a', "[a]closing chunk", mem->pcc);
  850.     }
  851. }
  852.  
  853. /* Reopen the current chunk after a GC or restore. */
  854. void
  855. alloc_open_chunk(gs_ref_memory_t *mem)
  856. {    if ( mem->pcc != 0 )
  857.     {    mem->cc = *mem->pcc;
  858.         if_debug_chunk('a', "[a]opening chunk", mem->pcc);
  859.     }
  860. }
  861.  
  862. /* Remove a chunk from the chain.  This is exported for the GC. */
  863. void
  864. alloc_unlink_chunk(chunk_t *cp, gs_ref_memory_t *mem)
  865. {    if ( cp->cprev == 0 )
  866.         mem->cfirst = cp->cnext;
  867.     else
  868.         cp->cprev->cnext = cp->cnext;
  869.     if ( cp->cnext == 0 )
  870.         mem->clast = cp->cprev;
  871.     else
  872.         cp->cnext->cprev = cp->cprev;
  873.     if ( mem->pcc != 0 )
  874.     {    mem->cc.cnext = mem->pcc->cnext;
  875.         mem->cc.cprev = mem->pcc->cprev;
  876.         if ( mem->pcc == cp )
  877.         {    mem->pcc = 0;
  878.             mem->cc.cbot = mem->cc.ctop = 0;
  879.         }
  880.     }
  881. }
  882.  
  883. /* Free a chunk.  This is exported for save/restore and for the GC. */
  884. void
  885. alloc_free_chunk(chunk_t *cp, gs_ref_memory_t *mem)
  886. {    gs_memory_t *parent = mem->parent;
  887.     alloc_unlink_chunk(cp, mem);
  888.     if ( cp->outer == 0 )
  889.       {    byte *cdata = (byte *)cp->chead;
  890.         mem->allocated -= gs_object_size(parent, cdata);
  891.         gs_free_object(parent, cdata, "alloc_free_chunk(data)");
  892.       }
  893.     else
  894.       cp->outer->inner_count--;
  895.     mem->allocated -= gs_object_size(parent, cp);
  896.     gs_free_object(parent, cp, "alloc_free_chunk(chunk struct)");
  897. }
  898.  
  899. /* Close the refs object of a chunk. */
  900. private void
  901. alloc_close_refs(chunk_t *cp)
  902. {    obj_header_t *rcur = cp->rcur;
  903.     if_debug3('a', "[a]closing refs 0x%lx: 0x%lx - 0x%lx\n",
  904.           (ulong)cp, (ulong)rcur, (ulong)cp->rtop);
  905.     if ( rcur != 0 )
  906.     {    rcur[-1].o_size = cp->rtop - (byte *)rcur;
  907.         /* Create the final ref, reserved for the GC. */
  908.         make_mark((ref *)cp->rtop - 1);
  909.     }
  910. }
  911.  
  912. /* Find the chunk for a pointer. */
  913. /* Note that this only searches the current save level. */
  914. /* Since a given save level can't contain both a chunk and an inner chunk */
  915. /* of that chunk, we can stop when is_within_chunk succeeds, and just test */
  916. /* is_in_inner_chunk then. */
  917. bool
  918. chunk_locate_ptr(const void *vptr, chunk_locator_t *clp)
  919. {    register chunk_t *cp = clp->cp;
  920.     if ( cp == 0 )
  921.     {    cp = clp->memory->cfirst;
  922.         if ( cp == 0 )
  923.             return false;
  924.     }
  925. #define ptr (const byte *)vptr
  926.     if ( ptr_lt(ptr, cp->cbase) )
  927.     {    do
  928.         {    cp = cp->cprev;
  929.             if ( cp == 0 )
  930.                 return false;
  931.         }
  932.         while ( ptr_lt(ptr, cp->cbase) );
  933.         if ( ptr_ge(ptr, cp->cend) )
  934.           return false;
  935.     }
  936.     else
  937.     {    while ( ptr_ge(ptr, cp->cend) )
  938.         {    cp = cp->cnext;
  939.             if ( cp == 0 )
  940.                 return false;
  941.         }
  942.         if ( ptr_lt(ptr, cp->cbase) )
  943.           return false;
  944.     }
  945.     clp->cp = cp;
  946.     return !ptr_is_in_inner_chunk(ptr, cp);
  947. #undef ptr
  948. }
  949.