home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / sa104os2.zip / SATHR104.ZIP / SATHER / SYSTEM / GC / MALLOC.C < prev    next >
C/C++ Source or Header  |  1994-09-19  |  15KB  |  583 lines
  1. /* 
  2.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  3.  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
  4.  *
  5.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  6.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  7.  *
  8.  * Permission is hereby granted to use or copy this program
  9.  * for any purpose,  provided the above notices are retained on all copies.
  10.  * Permission to modify the code and to distribute modified code is granted,
  11.  * provided the above notices are retained, and a notice that the code was
  12.  * modified is included with the above copyright notice.
  13.  */
  14. /* Boehm, September 19, 1994 4:18 pm PDT */
  15.  
  16. #include <stdio.h>
  17. #include "gc_priv.h"
  18.  
  19. extern ptr_t GC_clear_stack();    /* in misc.c, behaves like identity */
  20. void GC_extend_size_map();    /* in misc.c. */
  21.  
  22. /* Allocate reclaim list for kind:    */
  23. /* Return TRUE on success        */
  24. bool GC_alloc_reclaim_list(kind)
  25. register struct obj_kind * kind;
  26. {
  27.     struct hblk ** result = (struct hblk **)
  28.             GC_scratch_alloc((MAXOBJSZ+1) * sizeof(struct hblk *));
  29.     if (result == 0) return(FALSE);
  30.     BZERO(result, (MAXOBJSZ+1)*sizeof(struct hblk *));
  31.     kind -> ok_reclaim_list = result;
  32.     return(TRUE);
  33. }
  34.  
  35. /* allocate lb bytes for an object of kind.    */
  36. /* Should not be used to directly to allocate    */
  37. /* objects such as STUBBORN objects that    */
  38. /* require special handling on allocation.    */
  39. /* First a version that assumes we already    */
  40. /* hold lock:                    */
  41. ptr_t GC_generic_malloc_inner(lb, k)
  42. register word lb;
  43. register int k;
  44. {
  45. register word lw;
  46. register ptr_t op;
  47. register ptr_t *opp;
  48.  
  49.     if( SMALL_OBJ(lb) ) {
  50.         register struct obj_kind * kind = GC_obj_kinds + k;
  51. #       ifdef MERGE_SIZES
  52.       lw = GC_size_map[lb];
  53. #    else
  54.       lw = ALIGNED_WORDS(lb);
  55.       if (lw == 0) lw = 1;
  56. #       endif
  57.     opp = &(kind -> ok_freelist[lw]);
  58.         if( (op = *opp) == 0 ) {
  59. #        ifdef MERGE_SIZES
  60.           if (GC_size_map[lb] == 0) {
  61.             if (!GC_is_initialized)  GC_init_inner();
  62.             if (GC_size_map[lb] == 0) GC_extend_size_map(lb);
  63.             return(GC_generic_malloc_inner(lb, k));
  64.           }
  65. #        else
  66.           if (!GC_is_initialized) {
  67.             GC_init_inner();
  68.             return(GC_generic_malloc_inner(lb, k));
  69.           }
  70. #        endif
  71.         if (kind -> ok_reclaim_list == 0) {
  72.             if (!GC_alloc_reclaim_list(kind)) goto out;
  73.         }
  74.         op = GC_allocobj(lw, k);
  75.         if (op == 0) goto out;
  76.         }
  77.         /* Here everything is in a consistent state.    */
  78.         /* We assume the following assignment is    */
  79.         /* atomic.  If we get aborted            */
  80.         /* after the assignment, we lose an object,    */
  81.         /* but that's benign.                */
  82.         /* Volatile declarations may need to be added    */
  83.         /* to prevent the compiler from breaking things.*/
  84.         *opp = obj_link(op);
  85.         obj_link(op) = 0;
  86.     } else {
  87.     register struct hblk * h;
  88.     register word n_blocks = divHBLKSZ(ADD_SLOP(lb)
  89.                        + HDR_BYTES + HBLKSIZE-1);
  90.     
  91.     if (!GC_is_initialized) GC_init_inner();
  92.     /* Do our share of marking work */
  93.           if(GC_incremental && !GC_dont_gc)
  94.         GC_collect_a_little_inner((int)n_blocks);
  95.     lw = ROUNDED_UP_WORDS(lb);
  96.     while ((h = GC_allochblk(lw, k, 0)) == 0
  97.         && GC_collect_or_expand(n_blocks));
  98.     if (h == 0) {
  99.         op = 0;
  100.     } else {
  101.         op = (ptr_t) (h -> hb_body);
  102.         GC_words_wasted += BYTES_TO_WORDS(n_blocks * HBLKSIZE) - lw;
  103.     }
  104.     }
  105.     GC_words_allocd += lw;
  106.     
  107. out:
  108.     return((ptr_t)op);
  109. }
  110.  
  111. /* Allocate a composite object of size n bytes.  The caller guarantees    */
  112. /* that pointers past the first page are not relevant.  Caller holds    */
  113. /* allocation lock.                            */
  114. ptr_t GC_generic_malloc_inner_ignore_off_page(lb, k)
  115. register size_t lb;
  116. register int k;
  117. {
  118. # ifdef ALL_INTERIOR_POINTERS
  119.     register struct hblk * h;
  120.     register word n_blocks;
  121.     register word lw;
  122.     register ptr_t op;
  123.  
  124.     if (lb <= HBLKSIZE)
  125.         return(GC_generic_malloc_inner((word)lb, k));
  126.     n_blocks = divHBLKSZ(ADD_SLOP(lb) + HDR_BYTES + HBLKSIZE-1);
  127.     if (!GC_is_initialized) GC_init_inner();
  128.     /* Do our share of marking work */
  129.     if(GC_incremental && !GC_dont_gc)
  130.     GC_collect_a_little_inner((int)n_blocks);
  131.     lw = ROUNDED_UP_WORDS(lb);
  132.     while ((h = GC_allochblk(lw, k, IGNORE_OFF_PAGE)) == 0
  133.        && GC_collect_or_expand(n_blocks));
  134.     if (h == 0) {
  135.     op = 0;
  136.     } else {
  137.     op = (ptr_t) (h -> hb_body);
  138.     GC_words_wasted += BYTES_TO_WORDS(n_blocks * HBLKSIZE) - lw;
  139.     }
  140.     GC_words_allocd += lw;
  141.     return((ptr_t)op);
  142. # else
  143.     return(GC_generic_malloc_inner((word)lb, k));
  144. # endif
  145. }
  146.  
  147. ptr_t GC_generic_malloc_ignore_off_page(lb, k)
  148. register size_t lb;
  149. register int k;
  150. {
  151.     register ptr_t result;
  152.     DCL_LOCK_STATE;
  153.     
  154.     GC_invoke_finalizers();
  155.     DISABLE_SIGNALS();
  156.     LOCK();
  157.     result = GC_generic_malloc_inner_ignore_off_page(lb,k);
  158.     UNLOCK();
  159.     ENABLE_SIGNALS();
  160.     return(result);
  161. }
  162.  
  163. # if defined(__STDC__) || defined(__cplusplus)
  164.   void * GC_malloc_ignore_off_page(size_t lb)
  165. # else
  166.   char * GC_malloc_ignore_off_page(lb)
  167.   register size_t lb;
  168. # endif
  169. {
  170.     return((extern_ptr_t)GC_generic_malloc_ignore_off_page(lb, NORMAL));
  171. }
  172.  
  173. # if defined(__STDC__) || defined(__cplusplus)
  174.   void * GC_malloc_atomic_ignore_off_page(size_t lb)
  175. # else
  176.   char * GC_malloc_atomic_ignore_off_page(lb)
  177.   register size_t lb;
  178. # endif
  179. {
  180.     return((extern_ptr_t)GC_generic_malloc_ignore_off_page(lb, PTRFREE));
  181. }
  182.  
  183. ptr_t GC_generic_malloc(lb, k)
  184. register word lb;
  185. register int k;
  186. {
  187.     ptr_t result;
  188.     DCL_LOCK_STATE;
  189.  
  190.     GC_invoke_finalizers();
  191.     DISABLE_SIGNALS();
  192.     LOCK();
  193.     result = GC_generic_malloc_inner(lb, k);
  194.     UNLOCK();
  195.     ENABLE_SIGNALS();
  196.     return(result);
  197. }   
  198.  
  199.  
  200. /* Analogous to the above, but assumes a small object size, and     */
  201. /* bypasses MERGE_SIZES mechanism.  Used by gc_inline.h.        */
  202. ptr_t GC_generic_malloc_words_small(lw, k)
  203. register word lw;
  204. register int k;
  205. {
  206. register ptr_t op;
  207. register ptr_t *opp;
  208. register struct obj_kind * kind = GC_obj_kinds + k;
  209. DCL_LOCK_STATE;
  210.  
  211.     GC_invoke_finalizers();
  212.     DISABLE_SIGNALS();
  213.     LOCK();
  214.     opp = &(kind -> ok_freelist[lw]);
  215.     if( (op = *opp) == 0 ) {
  216.         if (!GC_is_initialized) {
  217.             GC_init_inner();
  218.         }
  219.     if (kind -> ok_reclaim_list == 0) {
  220.         if (!GC_alloc_reclaim_list(kind)) goto out;
  221.     }
  222.     op = GC_clear_stack(GC_allocobj(lw, k));
  223.     if (op == 0) goto out;
  224.     }
  225.     *opp = obj_link(op);
  226.     obj_link(op) = 0;
  227.     GC_words_allocd += lw;
  228.     
  229. out:
  230.     UNLOCK();
  231.     ENABLE_SIGNALS();
  232.     return((ptr_t)op);
  233. }
  234.  
  235. #if defined(THREADS) && !defined(SRC_M3)
  236. /* Return a list of 1 or more objects of the indicated size, linked    */
  237. /* through the first word in the object.  This has the advantage that    */
  238. /* it acquires the allocation lock only once, and may greatly reduce    */
  239. /* time wasted contending for the allocation lock.  Typical usage would */
  240. /* be in a thread that requires many items of the same size.  It would    */
  241. /* keep its own free list in thread-local storage, and call        */
  242. /* GC_malloc_many or friends to replenish it.  (We do not round up    */
  243. /* object sizes, since a call indicates the intention to consume many    */
  244. /* objects of exactly this size.)                    */
  245. /* Note that the client should usually clear the link field.        */
  246. ptr_t GC_generic_malloc_many(lb, k)
  247. register word lb;
  248. register int k;
  249. {
  250. ptr_t op;
  251. register ptr_t p;
  252. ptr_t *opp;
  253. word lw;
  254. register word my_words_allocd;
  255. DCL_LOCK_STATE;
  256.  
  257.     if (!SMALL_OBJ(lb)) {
  258.         op = GC_generic_malloc(lb, k);
  259.         obj_link(op) = 0;
  260.         return(op);
  261.     }
  262.     lw = ALIGNED_WORDS(lb);
  263.     GC_invoke_finalizers();
  264.     DISABLE_SIGNALS();
  265.     LOCK();
  266.     opp = &(GC_obj_kinds[k].ok_freelist[lw]);
  267.     if( (op = *opp) == 0 ) {
  268.         if (!GC_is_initialized) {
  269.             GC_init_inner();
  270.         }
  271.     op = GC_clear_stack(GC_allocobj(lw, k));
  272.     if (op == 0) goto out;
  273.     }
  274.     *opp = 0;
  275.     my_words_allocd = 0;
  276.     for (p = op; p != 0; p = obj_link(p)) {
  277.         my_words_allocd += lw;
  278.         if (my_words_allocd >= BODY_SZ) {
  279.             *opp = obj_link(p);
  280.             obj_link(p) = 0;
  281.             break;
  282.         }
  283.     }
  284.     GC_words_allocd += my_words_allocd;
  285.     
  286. out:
  287.     UNLOCK();
  288.     ENABLE_SIGNALS();
  289.     return(op);
  290.  
  291. }
  292.  
  293. void * GC_malloc_many(size_t lb)
  294. {
  295.     return(GC_generic_malloc_many(lb, NORMAL));
  296. }
  297.  
  298. /* Note that the "atomic" version of this would be unsafe, since the    */
  299. /* links would not be seen by the collector.                */
  300. # endif
  301.  
  302. #define GENERAL_MALLOC(lb,k) \
  303.     (extern_ptr_t)GC_clear_stack(GC_generic_malloc((word)lb, k))
  304. /* We make the GC_clear_stack_call a tail call, hoping to get more of    */
  305. /* the stack.                                */
  306.  
  307. /* Allocate lb bytes of atomic (pointerfree) data */
  308. # ifdef __STDC__
  309.     extern_ptr_t GC_malloc_atomic(size_t lb)
  310. # else
  311.     extern_ptr_t GC_malloc_atomic(lb)
  312.     size_t lb;
  313. # endif
  314. {
  315. register ptr_t op;
  316. register ptr_t * opp;
  317. register word lw;
  318. DCL_LOCK_STATE;
  319.  
  320.     if( SMALL_OBJ(lb) ) {
  321. #       ifdef MERGE_SIZES
  322.       lw = GC_size_map[lb];
  323. #    else
  324.       lw = ALIGNED_WORDS(lb);
  325. #       endif
  326.     opp = &(GC_aobjfreelist[lw]);
  327.     FASTLOCK();
  328.         if( !FASTLOCK_SUCCEEDED() || (op = *opp) == 0 ) {
  329.             FASTUNLOCK();
  330.             return(GENERAL_MALLOC((word)lb, PTRFREE));
  331.         }
  332.         /* See above comment on signals.    */
  333.         *opp = obj_link(op);
  334.         GC_words_allocd += lw;
  335.         FASTUNLOCK();
  336.         return((extern_ptr_t) op);
  337.    } else {
  338.        return(GENERAL_MALLOC((word)lb, PTRFREE));
  339.    }
  340. }
  341.  
  342. /* Allocate lb bytes of composite (pointerful) data */
  343. # ifdef __STDC__
  344.     extern_ptr_t GC_malloc(size_t lb)
  345. # else
  346.     extern_ptr_t GC_malloc(lb)
  347.     size_t lb;
  348. # endif
  349. {
  350. register ptr_t op;
  351. register ptr_t *opp;
  352. register word lw;
  353. DCL_LOCK_STATE;
  354.  
  355.     if( SMALL_OBJ(lb) ) {
  356. #       ifdef MERGE_SIZES
  357.       lw = GC_size_map[lb];
  358. #    else
  359.       lw = ALIGNED_WORDS(lb);
  360. #       endif
  361.     opp = &(GC_objfreelist[lw]);
  362.     FASTLOCK();
  363.         if( !FASTLOCK_SUCCEEDED() || (op = *opp) == 0 ) {
  364.             FASTUNLOCK();
  365.             return(GENERAL_MALLOC((word)lb, NORMAL));
  366.         }
  367.         /* See above comment on signals.    */
  368.         *opp = obj_link(op);
  369.         obj_link(op) = 0;
  370.         GC_words_allocd += lw;
  371.         FASTUNLOCK();
  372.         return((extern_ptr_t) op);
  373.    } else {
  374.        return(GENERAL_MALLOC((word)lb, NORMAL));
  375.    }
  376. }
  377.  
  378. /* Allocate lb bytes of pointerful, traced, but not collectable data */
  379. # ifdef __STDC__
  380.     extern_ptr_t GC_malloc_uncollectable(size_t lb)
  381. # else
  382.     extern_ptr_t GC_malloc_uncollectable(lb)
  383.     size_t lb;
  384. # endif
  385. {
  386. register ptr_t op;
  387. register ptr_t *opp;
  388. register word lw;
  389. DCL_LOCK_STATE;
  390.  
  391.     if( SMALL_OBJ(lb) ) {
  392. #       ifdef MERGE_SIZES
  393. #      ifdef ADD_BYTE_AT_END
  394.         lb--; /* We don't need the extra byte, since this won't be    */
  395.               /* collected anyway.                    */
  396. #      endif
  397.       lw = GC_size_map[lb];
  398. #    else
  399.       lw = ALIGNED_WORDS(lb);
  400. #       endif
  401.     opp = &(GC_uobjfreelist[lw]);
  402.     FASTLOCK();
  403.         if( FASTLOCK_SUCCEEDED() && (op = *opp) != 0 ) {
  404.             /* See above comment on signals.    */
  405.             *opp = obj_link(op);
  406.             obj_link(op) = 0;
  407.             GC_words_allocd += lw;
  408.             GC_set_mark_bit(op);
  409.             GC_non_gc_bytes += WORDS_TO_BYTES(lw);
  410.             FASTUNLOCK();
  411.             return((extern_ptr_t) op);
  412.         }
  413.         FASTUNLOCK();
  414.         op = (ptr_t)GC_generic_malloc((word)lb, UNCOLLECTABLE);
  415.     } else {
  416.     op = (ptr_t)GC_generic_malloc((word)lb, UNCOLLECTABLE);
  417.     }
  418.     /* We don't need the lock here, since we have an undisguised     */
  419.     /* pointer.  We do need to hold the lock while we adjust        */
  420.     /* mark bits.                            */
  421.     {
  422.     register struct hblk * h;
  423.     
  424.     h = HBLKPTR(op);
  425.     lw = HDR(h) -> hb_sz;
  426.     
  427.     DISABLE_SIGNALS();
  428.     LOCK();
  429.     GC_set_mark_bit(op);
  430.     GC_non_gc_bytes += WORDS_TO_BYTES(lw);
  431.     UNLOCK();
  432.     ENABLE_SIGNALS();
  433.     return((extern_ptr_t) op);
  434.     }
  435. }
  436.  
  437. extern_ptr_t GC_generic_or_special_malloc(lb,knd)
  438. word lb;
  439. int knd;
  440. {
  441.     switch(knd) {
  442. #     ifdef STUBBORN_ALLOC
  443.     case STUBBORN:
  444.         return(GC_malloc_stubborn((size_t)lb));
  445. #     endif
  446.     case PTRFREE:
  447.         return(GC_malloc_atomic((size_t)lb));
  448.     case NORMAL:
  449.         return(GC_malloc((size_t)lb));
  450.     case UNCOLLECTABLE:
  451.         return(GC_malloc_uncollectable((size_t)lb));
  452.     default:
  453.         return(GC_generic_malloc(lb,knd));
  454.     }
  455. }
  456.  
  457.  
  458. /* Change the size of the block pointed to by p to contain at least   */
  459. /* lb bytes.  The object may be (and quite likely will be) moved.     */
  460. /* The kind (e.g. atomic) is the same as that of the old.          */
  461. /* Shrinking of large blocks is not implemented well.                 */
  462. # ifdef __STDC__
  463.     extern_ptr_t GC_realloc(extern_ptr_t p, size_t lb)
  464. # else
  465.     extern_ptr_t GC_realloc(p,lb)
  466.     extern_ptr_t p;
  467.     size_t lb;
  468. # endif
  469. {
  470. register struct hblk * h;
  471. register hdr * hhdr;
  472. register word sz;     /* Current size in bytes    */
  473. register word orig_sz;     /* Original sz in bytes    */
  474. int obj_kind;
  475.  
  476.     if (p == 0) return(GC_malloc(lb));    /* Required by ANSI */
  477.     h = HBLKPTR(p);
  478.     hhdr = HDR(h);
  479.     sz = hhdr -> hb_sz;
  480.     obj_kind = hhdr -> hb_obj_kind;
  481.     sz = WORDS_TO_BYTES(sz);
  482.     orig_sz = sz;
  483.  
  484.     if (sz > WORDS_TO_BYTES(MAXOBJSZ)) {
  485.     /* Round it up to the next whole heap block */
  486.       
  487.       sz = (sz+HDR_BYTES+HBLKSIZE-1)
  488.         & (~HBLKMASK);
  489.       sz -= HDR_BYTES;
  490.       hhdr -> hb_sz = BYTES_TO_WORDS(sz);
  491.       if (obj_kind == UNCOLLECTABLE) GC_non_gc_bytes += (sz - orig_sz);
  492.       /* Extra area is already cleared by allochblk. */
  493.     }
  494.     if (ADD_SLOP(lb) <= sz) {
  495.     if (lb >= (sz >> 1)) {
  496. #        ifdef STUBBORN_ALLOC
  497.             if (obj_kind == STUBBORN) GC_change_stubborn(p);
  498. #        endif
  499.         if (orig_sz > lb) {
  500.           /* Clear unneeded part of object to avoid bogus pointer */
  501.           /* tracing.                          */
  502.           /* Safe for stubborn objects.                  */
  503.             BZERO(((ptr_t)p) + lb, orig_sz - lb);
  504.         }
  505.         return(p);
  506.     } else {
  507.         /* shrink */
  508.           extern_ptr_t result =
  509.                   GC_generic_or_special_malloc((word)lb, obj_kind);
  510.  
  511.           if (result == 0) return(0);
  512.               /* Could also return original object.  But this     */
  513.               /* gives the client warning of imminent disaster.    */
  514.           BCOPY(p, result, lb);
  515.           GC_free(p);
  516.           return(result);
  517.     }
  518.     } else {
  519.     /* grow */
  520.       extern_ptr_t result =
  521.           GC_generic_or_special_malloc((word)lb, obj_kind);
  522.  
  523.       if (result == 0) return(0);
  524.       BCOPY(p, result, sz);
  525.       GC_free(p);
  526.       return(result);
  527.     }
  528. }
  529.  
  530. /* Explicitly deallocate an object p.                */
  531. # ifdef __STDC__
  532.     void GC_free(extern_ptr_t p)
  533. # else
  534.     void GC_free(p)
  535.     extern_ptr_t p;
  536. # endif
  537. {
  538.     register struct hblk *h;
  539.     register hdr *hhdr;
  540.     register signed_word sz;
  541.     register ptr_t * flh;
  542.     register int knd;
  543.     register struct obj_kind * ok;
  544.     DCL_LOCK_STATE;
  545.  
  546.     if (p == 0) return;
  547.         /* Required by ANSI.  It's not my fault ...    */
  548.     h = HBLKPTR(p);
  549.     hhdr = HDR(h);
  550.     knd = hhdr -> hb_obj_kind;
  551.     sz = hhdr -> hb_sz;
  552.     ok = &GC_obj_kinds[knd];
  553.     if (sz <= MAXOBJSZ) {
  554. #    ifdef THREADS
  555.         DISABLE_SIGNALS();
  556.         LOCK();
  557. #    endif
  558.     GC_mem_freed += sz;
  559.     /* A signal here can make GC_mem_freed and GC_non_gc_bytes    */
  560.     /* inconsistent.  We claim this is benign.            */
  561.     if (knd == UNCOLLECTABLE) GC_non_gc_bytes -= sz;
  562.     if (ok -> ok_init) {
  563.         BZERO((word *)p + 1, WORDS_TO_BYTES(sz-1));
  564.     }
  565.     flh = &(ok -> ok_freelist[sz]);
  566.     obj_link(p) = *flh;
  567.     *flh = (ptr_t)p;
  568. #    ifdef THREADS
  569.         UNLOCK();
  570.         ENABLE_SIGNALS();
  571. #    endif
  572.     } else {
  573.         DISABLE_SIGNALS();
  574.         LOCK();
  575.         GC_mem_freed += sz;
  576.     if (knd == UNCOLLECTABLE) GC_non_gc_bytes -= sz;
  577.         GC_freehblk(h);
  578.         UNLOCK();
  579.         ENABLE_SIGNALS();
  580.     }
  581. }
  582.  
  583.