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