开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > 系统编程 > 查看源码
runtime.h
资源名称：mem_collector.tar.z　[点击查看]
上传用户：nthfjj
上传日期：2007-01-07
资源大小：37k
文件大小：20k
源码类别：

系统编程

开发平台：

Unix_Linux

runtime.h：源码内容
  1. /* Copyright 1988,1989 Hans-J. Boehm, Alan J. Demers */
  3. /*********************************/
  4. /*                               */
  5. /* Definitions for conservative  */
  6. /* collector                     */
  7. /*                               */
  8. /*********************************/
  10. /*********************************/
  11. /*                               */
  12. /* Easily changeable parameters  */
  13. /*                               */
  14. /*********************************/
  16. # if defined(sun) && defined(mc68000)
  17. #    define M68K
  18. #    define mach_type_known
  19. # endif
  20. # if defined(vax)
  21. #    define VAX
  22. #    define mach_type_known
  23. # endif
  24. # if defined(mips)
  25. #    define MIPS
  26. #    define mach_type_known
  27. # endif
  28. # if defined(sequent) && defined(i386)
  29. #    define I386
  30. #    define mach_type_known
  31. # endif
  32. # if defined(ibm032)
  33. #   define RT
  34. #   define mach_type_known
  35. # endif
  36. # if defined(sun) && defined(sparc)
  37. #   define SPARC
  38. #   define mach_type_known
  39. # endif
  42. /* Feel free to add more clauses here */
  44. /* Or manually define the machine type here: */
  45. # ifndef mach_type_known
  46. #   define M68K     /* This is a Motorola 68000, as opposed to a SPARC, VAX, */
  47.     /* RT, I386, MIPS, or NS32K.                             */
  48.     /* We assume:  M68K ==> Sun3, I386 ==> Sequent Symmetry */
  49.     /* NS32K ==> Encore Multimax, MIPS ==> R2000 or R3000   */
  50. # endif
  52. #define PRINTSTATS  /* Print garbage collection statistics                  */
  53.     /* For less verbose output, undefine in reclaim.c      */
  56. #define PRINTTIMES  /* Print the amount of time consumed by each garbage   */
  57.     /* collection.                                         */
  60. #define PRINTBLOCKS /* Print object sizes associated with heap blocks,     */
  61.     /* whether the objects are atomic or composite, and    */
  62.     /* whether or not the block was found to be empty      */
  63.     /* duing the reclaim phase.  Typically generates       */
  64.     /* about one screenful per garbage collection.         */
  65. #undef PRINTBLOCKS
  67. #define HBLK_MAP    /* Maintain a map of all potential heap blocks        */
  68.     /* starting at heapstart.                             */
  69.     /* Normally, this performs about as well as the       */
  70.     /* standard stack of chunk pointers that is used      */
  71.     /* otherwise.  It loses if a small section of the     */
  72.     /* heap consists of garbage collected objects.        */
  73.     /* It is ESSENTIAL if pointers to object interiors    */
  74.     /* are considered valid, i.e. if INTERIOR_POINTERS    */
  75.     /* is defined.                                        */
  76. #undef HBLK_MAP
  78. #define MAP_SIZE 8192  /* total data size < MAP_SIZE * HBLKSIZE = 32 Meg  */
  79. #define MAXHBLKS 4096  /* Maximum number of chunks which can be           */
  80.        /* allocated                                       */
  81. #define INTERIOR_POINTERS
  82.     /* Follow pointers to the interior of an object.      */
  83.     /* Substantially increases the probability of         */
  84.     /* unnnecessary space retention.  May be necessary    */
  85.     /* with gcc -O or other C compilers that may clobber  */
  86.     /* values of dead variables prematurely.  Pcc         */
  87.     /* derived compilers appear to pose no such problems. */
  88.     /* Empirical evidence suggests that this is probably  */
  89.     /* still OK for most purposes, so long as pointers    */
  90.     /* are known to be 32 bit aligned.  The combination   */
  91.     /* of INTERIOR_POINTERS and UNALIGNED (e.g. on a      */
  92.     /* Sun 3 with the standard compiler) causes easily    */
  93.     /* observable spurious retention and performance      */
  94.     /* degradation.                                       */
  95. #undef INTERIOR_POINTERS
  97. #if defined(INTERIOR_POINTERS) && !defined(HBLK_MAP)
  98.     --> check for interior pointers requires a heap block map
  99. #endif
  101. #define MERGE_SIZES /* Round up some object sizes, so that fewer distinct */
  102.     /* free lists are actually maintained.  This applies  */
  103.     /* only to the top level routines in misc.c, not to   */
  104.     /* user generated code that calls allocobj and        */
  105.     /* allocaobj directly.                                */
  106.     /* Slows down average programs slightly.  May however */
  107.     /* substantially reduce fragmentation if allocation   */
  108.     /* request sizes are widely scattered.                */
  109. #undef MERGE_SIZES
  112. #ifdef M68K
  113. #  define UNALIGNED       /* Pointers are not longword aligned         */
  114. #  define ALIGNMENT   2   /* Pointers are aligned on 2 byte boundaries */
  115.   /* by the Sun C compiler.                    */
  116. #else
  117. #  ifdef VAX
  118. #    undef UNALIGNED      /* Pointers are longword aligned by 4.2 C compiler */
  119. #    define ALIGNMENT 4
  120. #  else
  121. #    ifdef RT
  122. #      undef UNALIGNED
  123. #      define ALIGNMENT 4
  124. #    else
  125. #      ifdef SPARC
  126. #        undef UNALIGNED
  127. #        define ALIGNMENT 4
  128. #      else
  129. #        ifdef I386
  130. #           undef UNALIGNED         /* Sequent compiler aligns pointers */
  131. #           define ALIGNMENT 4
  132. #        else
  133. #          ifdef NS32K
  134. #            undef UNALIGNED        /* Pointers are aligned on NS32K */
  135. #            define ALIGNMENT 4
  136. #          else
  137. #            ifdef MIPS
  138. #              undef UNALIGNED      /* MIPS hardware requires pointer */
  139.     /* alignment                      */
  140. #              define ALIGNMENT 4
  141. #            else
  142.  --> specify alignment <--
  143. #            endif
  144. #          endif
  145. #        endif
  146. #      endif
  147. #    endif
  148. #  endif
  149. # endif
  151. # ifdef M68K
  152. #   define STACKTOP ((char *)0xf000000) /* Beginning of stack on a Sun 3 */
  153. /* Sun 2 value is 0x1000000      */
  154. # else
  155. #   ifdef VAX
  156. #     define STACKTOP ((char *)0x80000000) /* Beginning of stack under 4.n BSD */
  157. #   else
  158. #     ifdef RT
  159. #       define STACKTOP ((char *) 0x1fffd800)
  160. #     else
  161. #       ifdef SPARC
  162. #         define STACKTOP ((char *) 0xf8000000)
  163. #       else
  164. #         ifdef I386
  165. #           define STACKTOP ((char *) 0x3ffff000)  /* For Sequent */
  166. #         else
  167. #           ifdef NS32K
  168. #             define STACKTOP ((char *) 0xfffff000) /* for Encore */
  169. #           else
  170. #             ifdef MIPS
  171. #               define STACKTOP ((char *) 0x7ffff000)
  172.       /* Could probably be slightly lower since  */
  173.       /* startup code allocates lots of junk     */
  174. #             else
  175. --> specify
  176. #             endif
  177. #           endif
  178. #         endif
  179. #       endif
  180. #     endif
  181. #   endif
  182. # endif
  184. /* Start of data segment for each of the above systems.  Note that the */
  185. /* default case works only for contiguous text and data, such as on a  */
  186. /* Vax.                                                                */
  187. # ifdef M68K
  188. #   define DATASTART ((char *)((((long) (&etext)) + 0x1ffff) & ~0x1ffff))
  189. # else
  190. #   ifdef RT
  191. #     define DATASTART ((char *) 0x10000000)
  192. #   else
  193. #     ifdef I386
  194. #       define DATASTART ((char *)((((long) (&etext)) + 0xfff) & ~0xfff))
  195. #     else
  196. #       ifdef NS32K
  197.   extern char **environ;
  198. #         define DATASTART ((char *)(&environ))
  199.       /* hideous kludge: environ is the first   */
  200.       /* word in crt0.o, and delimits the start */
  201.       /* of the data segment, no matter which   */
  202.       /* ld options were passed through.        */
  203. #       else
  204. #         ifdef MIPS
  205. #           define DATASTART 0x10000000
  206.       /* Could probably be slightly higher since */
  207.       /* startup code allocates lots of junk     */
  208. #         else
  209. #           define DATASTART (&etext)
  210. #         endif
  211. #       endif
  212. #     endif
  213. #   endif
  214. # endif
  216. # define HINCR 16          /* Initial heap increment, in blocks of 4K        */
  217. # define HINCR_MULT 3      /* After each new allocation, hincr is multiplied */
  218. # define HINCR_DIV 2       /* by HINCR_MULT/HINCR_DIV                        */
  219. # define GC_MULT 3         /* Don't collect if the fraction of   */
  220.    /* non-collectable memory in the heap */
  221.    /* exceeds GC_MUL/GC_DIV              */
  222. # define GC_DIV  4
  224. # define NON_GC_HINCR 8    /* Heap increment if most of heap if collection */
  225.    /* was suppressed because most of heap is not   */
  226.    /* collectable                                  */
  228. /*  heap address bounds.  These are extreme bounds used for sanity checks. */
  229. /*  HEAPLIM may have to be increased for machines with incredibly large    */
  230. /*  amounts of memory.                                                     */
  232. #ifdef RT
  233. #   define HEAPSTART 0x10000000
  234. #   define HEAPLIM   0x1fff0000
  235. #else
  236. # ifdef M68K
  237. #   define HEAPSTART 0x00010000
  238. #   define HEAPLIM   0x04000000
  239. # else
  240. #   ifdef SPARC
  241. #       define HEAPSTART 0x00010000
  242. #       define HEAPLIM   0x10000000
  243. #   else
  244. #     ifdef VAX
  245. #       define HEAPSTART 0x400
  246. #       define HEAPLIM   0x10000000
  247. #     else
  248. #       ifdef I386
  249. #         define HEAPSTART 0x1000
  250. #         define HEAPLIM 0x10000000
  251. #       else
  252. #         ifdef NS32K
  253. #           define HEAPSTART 0x2000
  254. #           define HEAPLIM   0x10000000
  255. #         else
  256. #           ifdef MIPS
  257. #             define HEAPSTART 0x10000000
  258. #             define HEAPLIM 0x20000000
  259. #           else
  260.        --> values unknown <--
  261. #           endif
  262. #         endif
  263. #       endif
  264. #     endif
  265. #   endif
  266. # endif
  267. #endif
  269. /*********************************/
  270. /*                               */
  271. /* Machine-dependent defines     */
  272. /*                               */
  273. /*********************************/
  275. #define WORDS_TO_BYTES(x)   ((x)<<2)
  276. #define BYTES_TO_WORDS(x)   ((x)>>2)
  278. #define WORDSZ              32
  279. #define LOGWL               5    /* log[2] of above */
  280. #define BYTES_PER_WORD      (sizeof (word))
  281. #define NREGS               16
  282. #define ONES                0xffffffff
  283. #define MSBYTE              0xff000000
  284. #define SIGNB               0x80000000
  285. #define MAXSHORT            0x7fff
  286. #define modHALFWORDSZ(n) ((n) & 0xf)    /* mod n by size of half word    */
  287. #define divHALFWORDSZ(n) ((n) >> 4) /* divide n by size of half word */
  288. #define modWORDSZ(n) ((n) & 0x1f)       /* mod n by size of word         */
  289. #define divWORDSZ(n) ((n) >> 5)         /* divide n by size of word      */
  290. #define twice(n) ((n) << 1)             /* double n                      */
  292. typedef unsigned long word;
  294. #define TRUE  1
  295. #define FALSE 0
  297. /*********************/
  298. /*                   */
  299. /*  Size Parameters  */
  300. /*                   */
  301. /*********************/
  303. /*  heap block size, bytes */
  304. /* for RT see comment below */
  306. #define HBLKSIZE   0x1000
  309. /*  max size objects supported by freelist (larger objects may be   */
  310. /*  allocated, but less efficiently)                                */
  311. /*      asm(".set MAXOBJSZ,0x200")      if HBLKSIZE/2 == 0x200          */
  313. #define MAXOBJSZ    (HBLKSIZE/8)
  314. /* Should be BYTES_TO_WORDS(HBLKSIZE/2), but a cpp */
  315. /* misfeature prevents that.                       */
  316. #define MAXAOBJSZ   (HBLKSIZE/8)
  318. # define divHBLKSZ(n) ((n) >> 12)
  319.  
  320. # define modHBLKSZ(n) ((n) & 0xfff)
  321.  
  322. # define HBLKPTR(objptr) ((struct hblk *)(((long) (objptr)) & ~0xfff))
  326. /********************************************/
  327. /*                                          */
  328. /*    H e a p   B l o c k s                 */
  329. /*                                          */
  330. /********************************************/
  332. /*  heap block header */
  333. #define HBLKMASK   (HBLKSIZE-1)
  335. #define BITS_PER_HBLK (HBLKSIZE * 8)
  337. #define MARK_BITS_PER_HBLK (BITS_PER_HBLK/WORDSZ)
  338.    /* upper bound                                    */
  339.    /* We allocate 1 bit/word.  Only the first word   */
  340.    /* in each object is actually marked.             */
  342. # define MARK_BITS_SZ ((MARK_BITS_PER_HBLK + WORDSZ - 1)/WORDSZ)
  343.    /* Upper bound on number of mark words per heap block  */
  345. struct hblkhdr {
  346.     long hbh_sz;    /* sz > 0 ==> objects are sz-tuples of poss. pointers */
  347.     /* sz < 0 ==> objects are sz-tuples not pointers      */
  348.     /* if free, the size in bytes of the whole block      */
  349.     /* Misc.c knows that hbh_sz comes first.              */
  350. # ifndef HBLK_MAP
  351.     struct hblk ** hbh_index;   /* Pointer to heap block list entry   */
  352. /* for this block                     */
  353. # endif
  354.     struct hblk * hbh_next; /* Link field for hblk free list */
  355.     long hbh_mask;      /* If hbh_mask >= 0 then:                          */
  356. /*   x % (4 * hbh_sz) == x & hbh_mask              */
  357. /*   sz is a power of 2 and < the size of a heap   */
  358. /*     block.                                      */
  359. /* A hack to speed up pointer validity check on    */
  360. /* machines with slow division.                    */
  361.     long hbh_marks[MARK_BITS_SZ];
  362.     /* Bits 2i and 2i+1 in the array refer to the   */
  363.     /* object starting at the ith word (header      */
  364.     /* INCLUDED) in the heap block.                 */
  365.     /* For free blocks, hbh_marks[0] = 1, indicates */
  366.     /* block is uninitialized.                      */
  367. };
  369. /*  heap block body */
  371. # define BODY_SZ ((HBLKSIZE-sizeof(struct hblkhdr))/sizeof(word))
  373. struct hblk {
  374.     struct hblkhdr hb_hdr;
  375.     word hb_body[BODY_SZ];
  376. };
  378. # define hb_sz hb_hdr.hbh_sz
  379. # ifndef HBLK_MAP
  380. #   define hb_index hb_hdr.hbh_index
  381. # endif
  382. # define hb_marks hb_hdr.hbh_marks
  383. # define hb_next hb_hdr.hbh_next
  384. # define hb_uninit hb_hdr.hbh_marks[0]
  385. # define hb_mask hb_hdr.hbh_mask
  387. /*  lists of all heap blocks and free lists  */
  388. /* Object declaration is in alloc.c          */
  389. /* These are grouped together in a struct    */
  390. /* so that they can be easily skipped by the */
  391. /* mark routine.                             */
  392. /* misc.c knows about their relative order.  */
  394. struct __gc_arrays {
  395.   struct obj * _aobjfreelist[MAXAOBJSZ+1];         /* free list for atomic objs*/
  396.   struct obj * _objfreelist[MAXOBJSZ+1];           /* free list for objects */
  397. # ifdef HBLK_MAP
  398.     char _hblkmap[MAP_SIZE];
  399. #   define HBLK_INVALID 0    /* Not administered by collector   */
  400. #   define HBLK_VALID 0x7f   /* Beginning of a valid heap block */
  401.     /* A value n, 0 < n < 0x7f denotes the continuation of a valid heap    */
  402.     /* block which starts at the current address - n * HBLKSIZE or earlier */
  403. # else
  404.     struct hblk * _hblklist[MAXHBLKS];
  405. # endif
  406. };
  408. extern struct __gc_arrays _gc_arrays; 
  410. # define objfreelist _gc_arrays._objfreelist
  411. # define aobjfreelist _gc_arrays._aobjfreelist
  412. # ifdef HBLK_MAP
  413. #   define hblkmap _gc_arrays._hblkmap
  414. # else
  415. #   define hblklist _gc_arrays._hblklist
  416. # endif
  418. # define begin_gc_arrays ((char *)(&_gc_arrays))
  419. # define end_gc_arrays (((char *)(&_gc_arrays)) + (sizeof _gc_arrays))
  421. struct hblk ** last_hblk;  /* Pointer to one past the real end of hblklist */
  423. struct hblk * hblkfreelist;
  425. extern long heapsize;       /* Heap size in bytes */
  427. # define HINCR 16          /* Initial heap increment, in blocks              */
  428. long hincr;                /* current heap increment, in blocks              */
  430. /* Operations */
  431. # define update_hincr  hincr = (hincr * HINCR_MULT)/HINCR_DIV
  432. # define HB_SIZE(p) abs((p) -> hb_sz)
  433. # define abs(x)  ((x) < 0? (-(x)) : (x))
  435. /*  procedures */
  437. extern void
  438. freehblk();
  440. extern struct hblk *
  441. allochblk();
  443. /****************************/
  444. /*                          */
  445. /*   Objects                */
  446. /*                          */
  447. /****************************/
  449. /*  object structure */
  451. struct obj {
  452.     union {
  453. struct obj *oun_link;   /* --> next object in freelist */
  454. #         define obj_link       obj_un.oun_link
  455. word oun_component[1];  /* treats obj as list of words */
  456. #         define obj_component  obj_un.oun_component
  457.     } obj_un;
  458. };
  460. /*  Test whether something points to a legitimate heap object */
  463. extern char end;
  465. # ifdef HBLK_MAP
  466.   char * heapstart; /* A lower bound on all heap addresses */
  467.     /* Known to be HBLKSIZE aligned.       */
  468. # endif
  470. char * heaplim;   /* 1 + last address in heap */
  472. char * startup_sfp; /* Frame pointer for Russell startup routine */
  474. /* Check whether the given HBLKSIZE aligned hblk pointer refers to the   */
  475. /* beginning of a legitimate chunk.                                      */
  476. /* Assumes that *p is addressable                                        */
  477. # ifdef HBLK_MAP
  478. #   define is_hblk(p)  (hblkmap[divHBLKSZ(((long)p) - ((long)heapstart))] 
  479. == HBLK_VALID)
  480. # else
  481. #   define is_hblk(p) ( (p) -> hb_index >= hblklist 
  482. && (p) -> hb_index < last_hblk 
  483. && *((p)->hb_index) == (p))
  484. # endif
  485. # ifdef INTERIOR_POINTERS
  486.     /* Return the hblk_map entry for the pointer p */
  487. #     define get_map(p)  (hblkmap[divHBLKSZ(((long)p) - ((long)heapstart))])
  488. # endif
  490. # ifdef INTERIOR_POINTERS
  491.   /* Return the word displacement of the beginning of the object to       */
  492.   /* which q points.  q is an address inside hblk p for objects of size s */
  493.   /* with mask m corresponding to s.                                      */
  494. #  define get_word_no(q,p,s,m) 
  495.     (((long)(m)) >= 0 ? 
  496. (((((long)q) - ((long)p) - (sizeof (struct hblkhdr))) & ~(m)) 
  497.  + (sizeof (struct hblkhdr)) >> 2) 
  498. : ((((long)q) - ((long)p) - (sizeof (struct hblkhdr)) >> 2) 
  499.    / (s)) * (s) 
  500.    + ((sizeof (struct hblkhdr)) >> 2))
  501. # else
  502.   /* Check whether q points to an object inside hblk p for objects of size s */
  503.   /* with mask m corresponding to s.                                         */
  504. #  define is_proper_obj(q,p,s,m) 
  505.     (((long)(m)) >= 0 ? 
  506. (((((long)(q)) - (sizeof (struct hblkhdr))) & (m)) == 0) 
  507. : (((long) (q)) - ((long)(p)) - (sizeof (struct hblkhdr))) 
  508.    % ((s) << 2) == 0)
  509. #  endif
  511. /* The following is a quick test whether something is an object pointer */
  512. /* It may err in the direction of identifying bogus pointers            */
  513. /* Assumes heap + text + data + bss < 64 Meg.                           */
  514. #ifdef M68K
  515. #   define TMP_POINTER_MASK 0xfc000003  /* pointer & POINTER_MASK should be 0 */
  516. #else
  517. # ifdef RT
  518. #   define TMP_POINTER_MASK 0xc0000003
  519. # else
  520. #   ifdef VAX
  521. #     define TMP_POINTER_MASK 0xfc000003
  522. #   else
  523. #     ifdef SPARC
  524. #       define TMP_POINTER_MASK 0xfc000003
  525. #     else
  526. #       ifdef I386
  527. #         define TMP_POINTER_MASK 0xfc000003
  528. #       else
  529. #         ifdef NS32K
  530. #           define TMP_POINTER_MASK 0xfc000003
  531. #         else
  532. #           ifdef MIPS
  533. #             define TMP_POINTER_MASK 0xc0000003
  534. #           else
  535.       --> dont know <--
  536. #           endif
  537. #         endif
  538. #       endif
  539. #     endif
  540. #   endif
  541. # endif
  542. #endif
  544. #ifdef INTERIOR_POINTERS
  545. #   define POINTER_MASK (TMP_POINTER_MASK & 0xfffffff8)
  546. /* Don't pay attention to whether address is properly aligned */
  547. #else
  548. #   define POINTER_MASK TMP_POINTER_MASK
  549. #endif
  551. #ifdef HBLK_MAP
  552. #  define quicktest(p) (((long)(p)) > ((long)(heapstart)) 
  553. && !(((unsigned long)(p)) & POINTER_MASK))
  554. #else
  555. # ifdef UNALIGNED
  556. #  define quicktest(p) (((long)(p)) > ((long)(&end)) 
  557.                         && !(((unsigned long)(p)) & POINTER_MASK) 
  558.                         && (((long)(p)) & HBLKMASK))
  559. /* The last test throws out pointers to the beginning of heap */
  560.         /* blocks.  Small integers shifted by 16 bits tend to look    */
  561.         /* like these.                                                */
  562. # else
  563. #  define quicktest(p) (((long)(p)) > ((long)(&end)) 
  564. && !(((unsigned long)(p)) & POINTER_MASK))
  565. # endif
  566. #endif
  569. /*  Marks are in a reserved area in                          */
  570. /*  each heap block.  Each word has one mark bits associated */
  571. /*  with it. Only those corresponding to the beginning of an */
  572. /*  object are used.                                         */
  575. /* Operations */
  577. /*
  578.  * Retrieve, set, clear the mark bit corresponding
  579.  * to the nth word in a given heap block.
  580.  * Note that retrieval will work, so long as *hblk is addressable.
  581.  * In particular, the check whether hblk is a legitimate heap block
  582.  * can be postponed until after the mark bit is examined.
  583.  *
  584.  * (Recall that bit n corresponds to object beginning at word n)
  585.  */
  587. # define mark_bit(hblk,n) (((hblk)->hb_marks[divWORDSZ(n)] 
  588.     >> (modWORDSZ(n))) & 1)
  590. /* The following assume the mark bit in question is either initially */
  591. /* cleared or it already has its final value                         */
  592. # define set_mark_bit(hblk,n) (hblk)->hb_marks[divWORDSZ(n)] 
  593. |= 1 << modWORDSZ(n)
  595. # define clear_mark_bit(hblk,n) (hblk)->hb_marks[divWORDSZ(n)] 
  596. &= ~(1 << modWORDSZ(n))
  598. /*  procedures */
  600. /* Small object allocation routines */
  601. extern struct obj * allocobj();
  602. extern struct obj * allocaobj();
  604. /* general purpose allocation routines */
  605. extern struct obj * gc_malloc();
  607. extern struct obj * gc_malloc_comp();