src/mm/boehm-gc/include/new_gc_alloc.h

   1 /*
   2  * Copyright (c) 1996-1998 by Silicon Graphics.  All rights reserved.
   3  *
   4  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   5  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   6  *
   7  * Permission is hereby granted to use or copy this program
   8  * for any purpose,  provided the above notices are retained on all copies.
   9  * Permission to modify the code and to distribute modified code is granted,
  10  * provided the above notices are retained, and a notice that the code was
  11  * modified is included with the above copyright notice.
  12  */
  13
  14 //
  15 // This is a revision of gc_alloc.h for SGI STL versions > 3.0
  16 // Unlike earlier versions, it supplements the standard "alloc.h"
  17 // instead of replacing it.
  18 //
  19 // This is sloppy about variable names used in header files.
  20 // It also doesn't yet understand the new header file names or
  21 // namespaces.
  22 //
  23 // This assumes the collector has been compiled with -DATOMIC_UNCOLLECTABLE.
  24 // The user should also consider -DREDIRECT_MALLOC=GC_uncollectable_malloc,
  25 // to ensure that object allocated through malloc are traced.
  26 //
  27 // Some of this could be faster in the explicit deallocation case.
  28 // In particular, we spend too much time clearing objects on the
  29 // free lists.  That could be avoided.
  30 //
  31 // This uses template classes with static members, and hence does not work
  32 // with g++ 2.7.2 and earlier.
  33 //
  34 // Unlike its predecessor, this one simply defines
  35 //      gc_alloc
  36 //      single_client_gc_alloc
  37 //      traceable_alloc
  38 //      single_client_traceable_alloc
  39 //
  40 // It does not redefine alloc.  Nor does it change the default allocator,
  41 // though the user may wish to do so.  (The argument against changing
  42 // the default allocator is that it may introduce subtle link compatibility
  43 // problems.  The argument for changing it is that the usual default
  44 // allocator is usually a very bad choice for a garbage collected environment.)
  45 //
  46 // This code assumes that the collector itself has been compiled with a
  47 // compiler that defines __STDC__ .
  48 //
  49
  50 #ifndef GC_ALLOC_H
  51
  52 #include "gc.h"
  53
  54 #if (__GNUC__ < 3)
  55 # include <stack>  // A more portable way to get stl_alloc.h .
  56 #else
  57 # include <bits/stl_alloc.h>
  58 # ifndef __STL_BEGIN_NAMESPACE
  59 # define __STL_BEGIN_NAMESPACE namespace std {
  60 # define __STL_END_NAMESPACE };
  61 # endif
  62 #ifndef __STL_USE_STD_ALLOCATORS
  63 #define __STL_USE_STD_ALLOCATORS
  64 #endif
  65 #endif
  66
  67 /* A hack to deal with gcc 3.1.  If you are using gcc3.1 and later,     */
  68 /* you should probably really use gc_allocator.h instead.               */
  69 #if defined (__GNUC__) && \
  70     (__GNUC__ > 3 || (__GNUC__ == 3 && (__GNUC_MINOR__ >= 1)))
  71 # define simple_alloc __simple_alloc
  72 #endif
  73
  74
  75
  76 #define GC_ALLOC_H
  77
  78 #include <stddef.h>
  79 #include <string.h>
  80
  81 // The following need to match collector data structures.
  82 // We can't include gc_priv.h, since that pulls in way too much stuff.
  83 // This should eventually be factored out into another include file.
  84
  85 extern "C" {
  86     extern void ** const GC_objfreelist_ptr;
  87     extern void ** const GC_aobjfreelist_ptr;
  88     extern void ** const GC_uobjfreelist_ptr;
  89     extern void ** const GC_auobjfreelist_ptr;
  90
  91     extern void GC_incr_bytes_allocd(size_t bytes);
  92     extern void GC_incr_mem_freed(size_t words); /* FIXME: use bytes */
  93
  94     extern char * GC_generic_malloc_words_small(size_t word, int kind);
  95                 /* FIXME: Doesn't exist anymore.        */
  96 }
  97
  98 // Object kinds; must match PTRFREE, NORMAL, UNCOLLECTABLE, and
  99 // AUNCOLLECTABLE in gc_priv.h.
 100
 101 enum { GC_PTRFREE = 0, GC_NORMAL = 1, GC_UNCOLLECTABLE = 2,
 102        GC_AUNCOLLECTABLE = 3 };
 103
 104 enum { GC_max_fast_bytes = 255 };
 105
 106 enum { GC_bytes_per_word = sizeof(char *) };
 107
 108 enum { GC_byte_alignment = 8 };
 109
 110 enum { GC_word_alignment = GC_byte_alignment/GC_bytes_per_word };
 111
 112 inline void * &GC_obj_link(void * p)
 113 {   return *reinterpret_cast<void **>(p);  }
 114
 115 // Compute a number of words >= n+1 bytes.
 116 // The +1 allows for pointers one past the end.
 117 inline size_t GC_round_up(size_t n)
 118 {
 119     return ((n + GC_byte_alignment)/GC_byte_alignment)*GC_word_alignment;
 120 }
 121
 122 // The same but don't allow for extra byte.
 123 inline size_t GC_round_up_uncollectable(size_t n)
 124 {
 125     return ((n + GC_byte_alignment - 1)/GC_byte_alignment)*GC_word_alignment;
 126 }
 127
 128 template <int dummy>
 129 class GC_aux_template {
 130 public:
 131   // File local count of allocated words.  Occasionally this is
 132   // added into the global count.  A separate count is necessary since the
 133   // real one must be updated with a procedure call.
 134   static size_t GC_bytes_recently_allocd;
 135
 136   // Same for uncollectable memory.  Not yet reflected in either
 137   // GC_bytes_recently_allocd or GC_non_gc_bytes.
 138   static size_t GC_uncollectable_bytes_recently_allocd;
 139
 140   // Similar counter for explicitly deallocated memory.
 141   static size_t GC_bytes_recently_freed;
 142
 143   // Again for uncollectable memory.
 144   static size_t GC_uncollectable_bytes_recently_freed;
 145
 146   static void * GC_out_of_line_malloc(size_t nwords, int kind);
 147 };
 148
 149 template <int dummy>
 150 size_t GC_aux_template<dummy>::GC_bytes_recently_allocd = 0;
 151
 152 template <int dummy>
 153 size_t GC_aux_template<dummy>::GC_uncollectable_bytes_recently_allocd = 0;
 154
 155 template <int dummy>
 156 size_t GC_aux_template<dummy>::GC_bytes_recently_freed = 0;
 157
 158 template <int dummy>
 159 size_t GC_aux_template<dummy>::GC_uncollectable_bytes_recently_freed = 0;
 160
 161 template <int dummy>
 162 void * GC_aux_template<dummy>::GC_out_of_line_malloc(size_t nwords, int kind)
 163 {
 164     GC_bytes_recently_allocd += GC_uncollectable_bytes_recently_allocd;
 165     GC_non_gc_bytes +=
 166                 GC_uncollectable_bytes_recently_allocd;
 167     GC_uncollectable_bytes_recently_allocd = 0;
 168
 169     GC_bytes_recently_freed += GC_uncollectable_bytes_recently_freed;
 170     GC_non_gc_bytes -= GC_uncollectable_bytes_recently_freed;
 171     GC_uncollectable_bytes_recently_freed = 0;
 172
 173     GC_incr_bytes_allocd(GC_bytes_recently_allocd);
 174     GC_bytes_recently_allocd = 0;
 175
 176     GC_incr_mem_freed(GC_bytes_per_word(GC_bytes_recently_freed));
 177     GC_bytes_recently_freed = 0;
 178
 179     return GC_generic_malloc_words_small(nwords, kind);
 180 }
 181
 182 typedef GC_aux_template<0> GC_aux;
 183
 184 // A fast, single-threaded, garbage-collected allocator
 185 // We assume the first word will be immediately overwritten.
 186 // In this version, deallocation is not a no-op, and explicit
 187 // deallocation is likely to help performance.
 188 template <int dummy>
 189 class single_client_gc_alloc_template {
 190     public:
 191         static void * allocate(size_t n)
 192         {
 193             size_t nwords = GC_round_up(n);
 194             void ** flh;
 195             void * op;
 196
 197             if (n > GC_max_fast_bytes) return GC_malloc(n);
 198             flh = GC_objfreelist_ptr + nwords;
 199             if (0 == (op = *flh)) {
 200                 return GC_aux::GC_out_of_line_malloc(nwords, GC_NORMAL);
 201             }
 202             *flh = GC_obj_link(op);
 203             GC_aux::GC_bytes_recently_allocd += nwords * GC_bytes_per_word;
 204             return op;
 205         }
 206         static void * ptr_free_allocate(size_t n)
 207         {
 208             size_t nwords = GC_round_up(n);
 209             void ** flh;
 210             void * op;
 211
 212             if (n > GC_max_fast_bytes) return GC_malloc_atomic(n);
 213             flh = GC_aobjfreelist_ptr + nwords;
 214             if (0 == (op = *flh)) {
 215                 return GC_aux::GC_out_of_line_malloc(nwords, GC_PTRFREE);
 216             }
 217             *flh = GC_obj_link(op);
 218             GC_aux::GC_bytes_recently_allocd += nwords * GC_bytes_per_word;
 219             return op;
 220         }
 221         static void deallocate(void *p, size_t n)
 222         {
 223             size_t nwords = GC_round_up(n);
 224             void ** flh;
 225
 226             if (n > GC_max_fast_bytes)  {
 227                 GC_free(p);
 228             } else {
 229                 flh = GC_objfreelist_ptr + nwords;
 230                 GC_obj_link(p) = *flh;
 231                 memset(reinterpret_cast<char *>(p) + GC_bytes_per_word, 0,
 232                        GC_bytes_per_word * (nwords - 1));
 233                 *flh = p;
 234                 GC_aux::GC_bytes_recently_freed += nwords * GC_bytes_per_word;
 235             }
 236         }
 237         static void ptr_free_deallocate(void *p, size_t n)
 238         {
 239             size_t nwords = GC_round_up(n);
 240             void ** flh;
 241
 242             if (n > GC_max_fast_bytes) {
 243                 GC_free(p);
 244             } else {
 245                 flh = GC_aobjfreelist_ptr + nwords;
 246                 GC_obj_link(p) = *flh;
 247                 *flh = p;
 248                 GC_aux::GC_bytes_recently_freed += nwords * GC_bytes_per_word;
 249             }
 250         }
 251 };
 252
 253 typedef single_client_gc_alloc_template<0> single_client_gc_alloc;
 254
 255 // Once more, for uncollectable objects.
 256 template <int dummy>
 257 class single_client_traceable_alloc_template {
 258     public:
 259         static void * allocate(size_t n)
 260         {
 261             size_t nwords = GC_round_up_uncollectable(n);
 262             void ** flh;
 263             void * op;
 264
 265             if (n > GC_max_fast_bytes) return GC_malloc_uncollectable(n);
 266             flh = GC_uobjfreelist_ptr + nwords;
 267             if (0 == (op = *flh)) {
 268                 return GC_aux::GC_out_of_line_malloc(nwords, GC_UNCOLLECTABLE);
 269             }
 270             *flh = GC_obj_link(op);
 271             GC_aux::GC_uncollectable_bytes_recently_allocd +=
 272                                         nwords * GC_bytes_per_word;
 273             return op;
 274         }
 275         static void * ptr_free_allocate(size_t n)
 276         {
 277             size_t nwords = GC_round_up_uncollectable(n);
 278             void ** flh;
 279             void * op;
 280
 281             if (n > GC_max_fast_bytes) return GC_malloc_atomic_uncollectable(n);
 282             flh = GC_auobjfreelist_ptr + nwords;
 283             if (0 == (op = *flh)) {
 284                 return GC_aux::GC_out_of_line_malloc(nwords, GC_AUNCOLLECTABLE);
 285             }
 286             *flh = GC_obj_link(op);
 287             GC_aux::GC_uncollectable_bytes_recently_allocd +=
 288                                         nwords * GC_bytes_per_word;
 289             return op;
 290         }
 291         static void deallocate(void *p, size_t n)
 292         {
 293             size_t nwords = GC_round_up_uncollectable(n);
 294             void ** flh;
 295
 296             if (n > GC_max_fast_bytes)  {
 297                 GC_free(p);
 298             } else {
 299                 flh = GC_uobjfreelist_ptr + nwords;
 300                 GC_obj_link(p) = *flh;
 301                 *flh = p;
 302                 GC_aux::GC_uncollectable_bytes_recently_freed +=
 303                                 nwords * GC_bytes_per_word;
 304             }
 305         }
 306         static void ptr_free_deallocate(void *p, size_t n)
 307         {
 308             size_t nwords = GC_round_up_uncollectable(n);
 309             void ** flh;
 310
 311             if (n > GC_max_fast_bytes) {
 312                 GC_free(p);
 313             } else {
 314                 flh = GC_auobjfreelist_ptr + nwords;
 315                 GC_obj_link(p) = *flh;
 316                 *flh = p;
 317                 GC_aux::GC_uncollectable_bytes_recently_freed +=
 318                                 nwords * GC_bytes_per_word;
 319             }
 320         }
 321 };
 322
 323 typedef single_client_traceable_alloc_template<0> single_client_traceable_alloc;
 324
 325 template < int dummy >
 326 class gc_alloc_template {
 327     public:
 328         static void * allocate(size_t n) { return GC_malloc(n); }
 329         static void * ptr_free_allocate(size_t n)
 330                 { return GC_malloc_atomic(n); }
 331         static void deallocate(void *, size_t) { }
 332         static void ptr_free_deallocate(void *, size_t) { }
 333 };
 334
 335 typedef gc_alloc_template < 0 > gc_alloc;
 336
 337 template < int dummy >
 338 class traceable_alloc_template {
 339     public:
 340         static void * allocate(size_t n) { return GC_malloc_uncollectable(n); }
 341         static void * ptr_free_allocate(size_t n)
 342                 { return GC_malloc_atomic_uncollectable(n); }
 343         static void deallocate(void *p, size_t) { GC_free(p); }
 344         static void ptr_free_deallocate(void *p, size_t) { GC_free(p); }
 345 };
 346
 347 typedef traceable_alloc_template < 0 > traceable_alloc;
 348
 349 // We want to specialize simple_alloc so that it does the right thing
 350 // for all pointer-free types.  At the moment there is no portable way to
 351 // even approximate that.  The following approximation should work for
 352 // SGI compilers, and recent versions of g++.
 353
 354 # define __GC_SPECIALIZE(T,alloc) \
 355 class simple_alloc<T, alloc> { \
 356 public: \
 357     static T *allocate(size_t n) \
 358         { return 0 == n? 0 : \
 359                          reinterpret_cast<T*>(alloc::ptr_free_allocate(n * sizeof (T))); } \
 360     static T *allocate(void) \
 361         { return reinterpret_cast<T*>(alloc::ptr_free_allocate(sizeof (T))); } \
 362     static void deallocate(T *p, size_t n) \
 363         { if (0 != n) alloc::ptr_free_deallocate(p, n * sizeof (T)); } \
 364     static void deallocate(T *p) \
 365         { alloc::ptr_free_deallocate(p, sizeof (T)); } \
 366 };
 367
 368 __STL_BEGIN_NAMESPACE
 369
 370 __GC_SPECIALIZE(char, gc_alloc)
 371 __GC_SPECIALIZE(int, gc_alloc)
 372 __GC_SPECIALIZE(unsigned, gc_alloc)
 373 __GC_SPECIALIZE(float, gc_alloc)
 374 __GC_SPECIALIZE(double, gc_alloc)
 375
 376 __GC_SPECIALIZE(char, traceable_alloc)
 377 __GC_SPECIALIZE(int, traceable_alloc)
 378 __GC_SPECIALIZE(unsigned, traceable_alloc)
 379 __GC_SPECIALIZE(float, traceable_alloc)
 380 __GC_SPECIALIZE(double, traceable_alloc)
 381
 382 __GC_SPECIALIZE(char, single_client_gc_alloc)
 383 __GC_SPECIALIZE(int, single_client_gc_alloc)
 384 __GC_SPECIALIZE(unsigned, single_client_gc_alloc)
 385 __GC_SPECIALIZE(float, single_client_gc_alloc)
 386 __GC_SPECIALIZE(double, single_client_gc_alloc)
 387
 388 __GC_SPECIALIZE(char, single_client_traceable_alloc)
 389 __GC_SPECIALIZE(int, single_client_traceable_alloc)
 390 __GC_SPECIALIZE(unsigned, single_client_traceable_alloc)
 391 __GC_SPECIALIZE(float, single_client_traceable_alloc)
 392 __GC_SPECIALIZE(double, single_client_traceable_alloc)
 393
 394 __STL_END_NAMESPACE
 395
 396 #ifdef __STL_USE_STD_ALLOCATORS
 397
 398 __STL_BEGIN_NAMESPACE
 399
 400 template <class _Tp>
 401 struct _Alloc_traits<_Tp, gc_alloc >
 402 {
 403   static const bool _S_instanceless = true;
 404   typedef simple_alloc<_Tp, gc_alloc > _Alloc_type;
 405   typedef __allocator<_Tp, gc_alloc > allocator_type;
 406 };
 407
 408 inline bool operator==(const gc_alloc&,
 409                        const gc_alloc&)
 410 {
 411   return true;
 412 }
 413
 414 inline bool operator!=(const gc_alloc&,
 415                        const gc_alloc&)
 416 {
 417   return false;
 418 }
 419
 420 template <class _Tp>
 421 struct _Alloc_traits<_Tp, single_client_gc_alloc >
 422 {
 423   static const bool _S_instanceless = true;
 424   typedef simple_alloc<_Tp, single_client_gc_alloc > _Alloc_type;
 425   typedef __allocator<_Tp, single_client_gc_alloc > allocator_type;
 426 };
 427
 428 inline bool operator==(const single_client_gc_alloc&,
 429                        const single_client_gc_alloc&)
 430 {
 431   return true;
 432 }
 433
 434 inline bool operator!=(const single_client_gc_alloc&,
 435                        const single_client_gc_alloc&)
 436 {
 437   return false;
 438 }
 439
 440 template <class _Tp>
 441 struct _Alloc_traits<_Tp, traceable_alloc >
 442 {
 443   static const bool _S_instanceless = true;
 444   typedef simple_alloc<_Tp, traceable_alloc > _Alloc_type;
 445   typedef __allocator<_Tp, traceable_alloc > allocator_type;
 446 };
 447
 448 inline bool operator==(const traceable_alloc&,
 449                        const traceable_alloc&)
 450 {
 451   return true;
 452 }
 453
 454 inline bool operator!=(const traceable_alloc&,
 455                        const traceable_alloc&)
 456 {
 457   return false;
 458 }
 459
 460 template <class _Tp>
 461 struct _Alloc_traits<_Tp, single_client_traceable_alloc >
 462 {
 463   static const bool _S_instanceless = true;
 464   typedef simple_alloc<_Tp, single_client_traceable_alloc > _Alloc_type;
 465   typedef __allocator<_Tp, single_client_traceable_alloc > allocator_type;
 466 };
 467
 468 inline bool operator==(const single_client_traceable_alloc&,
 469                        const single_client_traceable_alloc&)
 470 {
 471   return true;
 472 }
 473
 474 inline bool operator!=(const single_client_traceable_alloc&,
 475                        const single_client_traceable_alloc&)
 476 {
 477   return false;
 478 }
 479
 480 __STL_END_NAMESPACE
 481
 482 #endif /* __STL_USE_STD_ALLOCATORS */
 483
 484 #endif /* GC_ALLOC_H */