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