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
  68 #define GC_ALLOC_H
  69
  70 #include <stddef.h>
  71 #include <string.h>
  72
  73 // The following need to match collector data structures.
  74 // We can't include gc_priv.h, since that pulls in way too much stuff.
  75 // This should eventually be factored out into another include file.
  76
  77 extern "C" {
  78     extern void ** const GC_objfreelist_ptr;
  79     extern void ** const GC_aobjfreelist_ptr;
  80     extern void ** const GC_uobjfreelist_ptr;
  81     extern void ** const GC_auobjfreelist_ptr;
  82
  83     extern void GC_incr_words_allocd(size_t words);
  84     extern void GC_incr_mem_freed(size_t words);
  85
  86     extern char * GC_generic_malloc_words_small(size_t word, int kind);
  87 }
  88
  89 // Object kinds; must match PTRFREE, NORMAL, UNCOLLECTABLE, and
  90 // AUNCOLLECTABLE in gc_priv.h.
  91
  92 enum { GC_PTRFREE = 0, GC_NORMAL = 1, GC_UNCOLLECTABLE = 2,
  93        GC_AUNCOLLECTABLE = 3 };
  94
  95 enum { GC_max_fast_bytes = 255 };
  96
  97 enum { GC_bytes_per_word = sizeof(char *) };
  98
  99 enum { GC_byte_alignment = 8 };
 100
 101 enum { GC_word_alignment = GC_byte_alignment/GC_bytes_per_word };
 102
 103 inline void * &GC_obj_link(void * p)
 104 {   return *(void **)p;  }
 105
 106 // Compute a number of words >= n+1 bytes.
 107 // The +1 allows for pointers one past the end.
 108 inline size_t GC_round_up(size_t n)
 109 {
 110     return ((n + GC_byte_alignment)/GC_byte_alignment)*GC_word_alignment;
 111 }
 112
 113 // The same but don't allow for extra byte.
 114 inline size_t GC_round_up_uncollectable(size_t n)
 115 {
 116     return ((n + GC_byte_alignment - 1)/GC_byte_alignment)*GC_word_alignment;
 117 }
 118
 119 template <int dummy>
 120 class GC_aux_template {
 121 public:
 122   // File local count of allocated words.  Occasionally this is
 123   // added into the global count.  A separate count is necessary since the
 124   // real one must be updated with a procedure call.
 125   static size_t GC_words_recently_allocd;
 126
 127   // Same for uncollectable mmory.  Not yet reflected in either
 128   // GC_words_recently_allocd or GC_non_gc_bytes.
 129   static size_t GC_uncollectable_words_recently_allocd;
 130
 131   // Similar counter for explicitly deallocated memory.
 132   static size_t GC_mem_recently_freed;
 133
 134   // Again for uncollectable memory.
 135   static size_t GC_uncollectable_mem_recently_freed;
 136
 137   static void * GC_out_of_line_malloc(size_t nwords, int kind);
 138 };
 139
 140 template <int dummy>
 141 size_t GC_aux_template<dummy>::GC_words_recently_allocd = 0;
 142
 143 template <int dummy>
 144 size_t GC_aux_template<dummy>::GC_uncollectable_words_recently_allocd = 0;
 145
 146 template <int dummy>
 147 size_t GC_aux_template<dummy>::GC_mem_recently_freed = 0;
 148
 149 template <int dummy>
 150 size_t GC_aux_template<dummy>::GC_uncollectable_mem_recently_freed = 0;
 151
 152 template <int dummy>
 153 void * GC_aux_template<dummy>::GC_out_of_line_malloc(size_t nwords, int kind)
 154 {
 155     GC_words_recently_allocd += GC_uncollectable_words_recently_allocd;
 156     GC_non_gc_bytes +=
 157                 GC_bytes_per_word * GC_uncollectable_words_recently_allocd;
 158     GC_uncollectable_words_recently_allocd = 0;
 159
 160     GC_mem_recently_freed += GC_uncollectable_mem_recently_freed;
 161     GC_non_gc_bytes -=
 162                 GC_bytes_per_word * GC_uncollectable_mem_recently_freed;
 163     GC_uncollectable_mem_recently_freed = 0;
 164
 165     GC_incr_words_allocd(GC_words_recently_allocd);
 166     GC_words_recently_allocd = 0;
 167
 168     GC_incr_mem_freed(GC_mem_recently_freed);
 169     GC_mem_recently_freed = 0;
 170
 171     return GC_generic_malloc_words_small(nwords, kind);
 172 }
 173
 174 typedef GC_aux_template<0> GC_aux;
 175
 176 // A fast, single-threaded, garbage-collected allocator
 177 // We assume the first word will be immediately overwritten.
 178 // In this version, deallocation is not a noop, and explicit
 179 // deallocation is likely to help performance.
 180 template <int dummy>
 181 class single_client_gc_alloc_template {
 182     public:
 183         static void * allocate(size_t n)
 184         {
 185             size_t nwords = GC_round_up(n);
 186             void ** flh;
 187             void * op;
 188
 189             if (n > GC_max_fast_bytes) return GC_malloc(n);
 190             flh = GC_objfreelist_ptr + nwords;
 191             if (0 == (op = *flh)) {
 192                 return GC_aux::GC_out_of_line_malloc(nwords, GC_NORMAL);
 193             }
 194             *flh = GC_obj_link(op);
 195             GC_aux::GC_words_recently_allocd += nwords;
 196             return op;
 197         }
 198         static void * ptr_free_allocate(size_t n)
 199         {
 200             size_t nwords = GC_round_up(n);
 201             void ** flh;
 202             void * op;
 203
 204             if (n > GC_max_fast_bytes) return GC_malloc_atomic(n);
 205             flh = GC_aobjfreelist_ptr + nwords;
 206             if (0 == (op = *flh)) {
 207                 return GC_aux::GC_out_of_line_malloc(nwords, GC_PTRFREE);
 208             }
 209             *flh = GC_obj_link(op);
 210             GC_aux::GC_words_recently_allocd += nwords;
 211             return op;
 212         }
 213         static void deallocate(void *p, size_t n)
 214         {
 215             size_t nwords = GC_round_up(n);
 216             void ** flh;
 217
 218             if (n > GC_max_fast_bytes)  {
 219                 GC_free(p);
 220             } else {
 221                 flh = GC_objfreelist_ptr + nwords;
 222                 GC_obj_link(p) = *flh;
 223                 memset((char *)p + GC_bytes_per_word, 0,
 224                        GC_bytes_per_word * (nwords - 1));
 225                 *flh = p;
 226                 GC_aux::GC_mem_recently_freed += nwords;
 227             }
 228         }
 229         static void ptr_free_deallocate(void *p, size_t n)
 230         {
 231             size_t nwords = GC_round_up(n);
 232             void ** flh;
 233
 234             if (n > GC_max_fast_bytes) {
 235                 GC_free(p);
 236             } else {
 237                 flh = GC_aobjfreelist_ptr + nwords;
 238                 GC_obj_link(p) = *flh;
 239                 *flh = p;
 240                 GC_aux::GC_mem_recently_freed += nwords;
 241             }
 242         }
 243 };
 244
 245 typedef single_client_gc_alloc_template<0> single_client_gc_alloc;
 246
 247 // Once more, for uncollectable objects.
 248 template <int dummy>
 249 class single_client_traceable_alloc_template {
 250     public:
 251         static void * allocate(size_t n)
 252         {
 253             size_t nwords = GC_round_up_uncollectable(n);
 254             void ** flh;
 255             void * op;
 256
 257             if (n > GC_max_fast_bytes) return GC_malloc_uncollectable(n);
 258             flh = GC_uobjfreelist_ptr + nwords;
 259             if (0 == (op = *flh)) {
 260                 return GC_aux::GC_out_of_line_malloc(nwords, GC_UNCOLLECTABLE);
 261             }
 262             *flh = GC_obj_link(op);
 263             GC_aux::GC_uncollectable_words_recently_allocd += nwords;
 264             return op;
 265         }
 266         static void * ptr_free_allocate(size_t n)
 267         {
 268             size_t nwords = GC_round_up_uncollectable(n);
 269             void ** flh;
 270             void * op;
 271
 272             if (n > GC_max_fast_bytes) return GC_malloc_atomic_uncollectable(n);
 273             flh = GC_auobjfreelist_ptr + nwords;
 274             if (0 == (op = *flh)) {
 275                 return GC_aux::GC_out_of_line_malloc(nwords, GC_AUNCOLLECTABLE);
 276             }
 277             *flh = GC_obj_link(op);
 278             GC_aux::GC_uncollectable_words_recently_allocd += nwords;
 279             return op;
 280         }
 281         static void deallocate(void *p, size_t n)
 282         {
 283             size_t nwords = GC_round_up_uncollectable(n);
 284             void ** flh;
 285
 286             if (n > GC_max_fast_bytes)  {
 287                 GC_free(p);
 288             } else {
 289                 flh = GC_uobjfreelist_ptr + nwords;
 290                 GC_obj_link(p) = *flh;
 291                 *flh = p;
 292                 GC_aux::GC_uncollectable_mem_recently_freed += nwords;
 293             }
 294         }
 295         static void ptr_free_deallocate(void *p, size_t n)
 296         {
 297             size_t nwords = GC_round_up_uncollectable(n);
 298             void ** flh;
 299
 300             if (n > GC_max_fast_bytes) {
 301                 GC_free(p);
 302             } else {
 303                 flh = GC_auobjfreelist_ptr + nwords;
 304                 GC_obj_link(p) = *flh;
 305                 *flh = p;
 306                 GC_aux::GC_uncollectable_mem_recently_freed += nwords;
 307             }
 308         }
 309 };
 310
 311 typedef single_client_traceable_alloc_template<0> single_client_traceable_alloc;
 312
 313 template < int dummy >
 314 class gc_alloc_template {
 315     public:
 316         static void * allocate(size_t n) { return GC_malloc(n); }
 317         static void * ptr_free_allocate(size_t n)
 318                 { return GC_malloc_atomic(n); }
 319         static void deallocate(void *, size_t) { }
 320         static void ptr_free_deallocate(void *, size_t) { }
 321 };
 322
 323 typedef gc_alloc_template < 0 > gc_alloc;
 324
 325 template < int dummy >
 326 class traceable_alloc_template {
 327     public:
 328         static void * allocate(size_t n) { return GC_malloc_uncollectable(n); }
 329         static void * ptr_free_allocate(size_t n)
 330                 { return GC_malloc_atomic_uncollectable(n); }
 331         static void deallocate(void *p, size_t) { GC_free(p); }
 332         static void ptr_free_deallocate(void *p, size_t) { GC_free(p); }
 333 };
 334
 335 typedef traceable_alloc_template < 0 > traceable_alloc;
 336
 337 // We want to specialize simple_alloc so that it does the right thing
 338 // for all pointerfree types.  At the moment there is no portable way to
 339 // even approximate that.  The following approximation should work for
 340 // SGI compilers, and recent versions of g++.
 341
 342 # define __GC_SPECIALIZE(T,alloc) \
 343 class simple_alloc<T, alloc> { \
 344 public: \
 345     static T *allocate(size_t n) \
 346         { return 0 == n? 0 : \
 347                          (T*) alloc::ptr_free_allocate(n * sizeof (T)); } \
 348     static T *allocate(void) \
 349         { return (T*) alloc::ptr_free_allocate(sizeof (T)); } \
 350     static void deallocate(T *p, size_t n) \
 351         { if (0 != n) alloc::ptr_free_deallocate(p, n * sizeof (T)); } \
 352     static void deallocate(T *p) \
 353         { alloc::ptr_free_deallocate(p, sizeof (T)); } \
 354 };
 355
 356 __STL_BEGIN_NAMESPACE
 357
 358 __GC_SPECIALIZE(char, gc_alloc)
 359 __GC_SPECIALIZE(int, gc_alloc)
 360 __GC_SPECIALIZE(unsigned, gc_alloc)
 361 __GC_SPECIALIZE(float, gc_alloc)
 362 __GC_SPECIALIZE(double, gc_alloc)
 363
 364 __GC_SPECIALIZE(char, traceable_alloc)
 365 __GC_SPECIALIZE(int, traceable_alloc)
 366 __GC_SPECIALIZE(unsigned, traceable_alloc)
 367 __GC_SPECIALIZE(float, traceable_alloc)
 368 __GC_SPECIALIZE(double, traceable_alloc)
 369
 370 __GC_SPECIALIZE(char, single_client_gc_alloc)
 371 __GC_SPECIALIZE(int, single_client_gc_alloc)
 372 __GC_SPECIALIZE(unsigned, single_client_gc_alloc)
 373 __GC_SPECIALIZE(float, single_client_gc_alloc)
 374 __GC_SPECIALIZE(double, single_client_gc_alloc)
 375
 376 __GC_SPECIALIZE(char, single_client_traceable_alloc)
 377 __GC_SPECIALIZE(int, single_client_traceable_alloc)
 378 __GC_SPECIALIZE(unsigned, single_client_traceable_alloc)
 379 __GC_SPECIALIZE(float, single_client_traceable_alloc)
 380 __GC_SPECIALIZE(double, single_client_traceable_alloc)
 381
 382 __STL_END_NAMESPACE
 383
 384 #ifdef __STL_USE_STD_ALLOCATORS
 385
 386 __STL_BEGIN_NAMESPACE
 387
 388 template <class _T>
 389 struct _Alloc_traits<_T, gc_alloc >
 390 {
 391   static const bool _S_instanceless = true;
 392   typedef simple_alloc<_T, gc_alloc > _Alloc_type;
 393   typedef __allocator<_T, gc_alloc > allocator_type;
 394 };
 395
 396 inline bool operator==(const gc_alloc&,
 397                        const gc_alloc&)
 398 {
 399   return true;
 400 }
 401
 402 inline bool operator!=(const gc_alloc&,
 403                        const gc_alloc&)
 404 {
 405   return false;
 406 }
 407
 408 template <class _T>
 409 struct _Alloc_traits<_T, single_client_gc_alloc >
 410 {
 411   static const bool _S_instanceless = true;
 412   typedef simple_alloc<_T, single_client_gc_alloc > _Alloc_type;
 413   typedef __allocator<_T, single_client_gc_alloc > allocator_type;
 414 };
 415
 416 inline bool operator==(const single_client_gc_alloc&,
 417                        const single_client_gc_alloc&)
 418 {
 419   return true;
 420 }
 421
 422 inline bool operator!=(const single_client_gc_alloc&,
 423                        const single_client_gc_alloc&)
 424 {
 425   return false;
 426 }
 427
 428 template <class _T>
 429 struct _Alloc_traits<_T, traceable_alloc >
 430 {
 431   static const bool _S_instanceless = true;
 432   typedef simple_alloc<_T, traceable_alloc > _Alloc_type;
 433   typedef __allocator<_T, traceable_alloc > allocator_type;
 434 };
 435
 436 inline bool operator==(const traceable_alloc&,
 437                        const traceable_alloc&)
 438 {
 439   return true;
 440 }
 441
 442 inline bool operator!=(const traceable_alloc&,
 443                        const traceable_alloc&)
 444 {
 445   return false;
 446 }
 447
 448 template <class _T>
 449 struct _Alloc_traits<_T, single_client_traceable_alloc >
 450 {
 451   static const bool _S_instanceless = true;
 452   typedef simple_alloc<_T, single_client_traceable_alloc > _Alloc_type;
 453   typedef __allocator<_T, single_client_traceable_alloc > allocator_type;
 454 };
 455
 456 inline bool operator==(const single_client_traceable_alloc&,
 457                        const single_client_traceable_alloc&)
 458 {
 459   return true;
 460 }
 461
 462 inline bool operator!=(const single_client_traceable_alloc&,
 463                        const single_client_traceable_alloc&)
 464 {
 465   return false;
 466 }
 467
 468 __STL_END_NAMESPACE
 469
 470 #endif /* __STL_USE_STD_ALLOCATORS */
 471
 472 #endif /* GC_ALLOC_H */