libgc/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_words_allocd(size_t words);
  92     extern void GC_incr_mem_freed(size_t words);
  93
  94     extern char * GC_generic_malloc_words_small(size_t word, int kind);
  95 }
  96
  97 // Object kinds; must match PTRFREE, NORMAL, UNCOLLECTABLE, and
  98 // AUNCOLLECTABLE in gc_priv.h.
  99
 100 enum { GC_PTRFREE = 0, GC_NORMAL = 1, GC_UNCOLLECTABLE = 2,
 101        GC_AUNCOLLECTABLE = 3 };
 102
 103 enum { GC_max_fast_bytes = 255 };
 104
 105 enum { GC_bytes_per_word = sizeof(char *) };
 106
 107 enum { GC_byte_alignment = 8 };
 108
 109 enum { GC_word_alignment = GC_byte_alignment/GC_bytes_per_word };
 110
 111 inline void * &GC_obj_link(void * p)
 112 {   return *(void **)p;  }
 113
 114 // Compute a number of words >= n+1 bytes.
 115 // The +1 allows for pointers one past the end.
 116 inline size_t GC_round_up(size_t n)
 117 {
 118     return ((n + GC_byte_alignment)/GC_byte_alignment)*GC_word_alignment;
 119 }
 120
 121 // The same but don't allow for extra byte.
 122 inline size_t GC_round_up_uncollectable(size_t n)
 123 {
 124     return ((n + GC_byte_alignment - 1)/GC_byte_alignment)*GC_word_alignment;
 125 }
 126
 127 template <int dummy>
 128 class GC_aux_template {
 129 public:
 130   // File local count of allocated words.  Occasionally this is
 131   // added into the global count.  A separate count is necessary since the
 132   // real one must be updated with a procedure call.
 133   static size_t GC_words_recently_allocd;
 134
 135   // Same for uncollectable mmory.  Not yet reflected in either
 136   // GC_words_recently_allocd or GC_non_gc_bytes.
 137   static size_t GC_uncollectable_words_recently_allocd;
 138
 139   // Similar counter for explicitly deallocated memory.
 140   static size_t GC_mem_recently_freed;
 141
 142   // Again for uncollectable memory.
 143   static size_t GC_uncollectable_mem_recently_freed;
 144
 145   static void * GC_out_of_line_malloc(size_t nwords, int kind);
 146 };
 147
 148 template <int dummy>
 149 size_t GC_aux_template<dummy>::GC_words_recently_allocd = 0;
 150
 151 template <int dummy>
 152 size_t GC_aux_template<dummy>::GC_uncollectable_words_recently_allocd = 0;
 153
 154 template <int dummy>
 155 size_t GC_aux_template<dummy>::GC_mem_recently_freed = 0;
 156
 157 template <int dummy>
 158 size_t GC_aux_template<dummy>::GC_uncollectable_mem_recently_freed = 0;
 159
 160 template <int dummy>
 161 void * GC_aux_template<dummy>::GC_out_of_line_malloc(size_t nwords, int kind)
 162 {
 163     GC_words_recently_allocd += GC_uncollectable_words_recently_allocd;
 164     GC_non_gc_bytes +=
 165                 GC_bytes_per_word * GC_uncollectable_words_recently_allocd;
 166     GC_uncollectable_words_recently_allocd = 0;
 167
 168     GC_mem_recently_freed += GC_uncollectable_mem_recently_freed;
 169     GC_non_gc_bytes -=
 170                 GC_bytes_per_word * GC_uncollectable_mem_recently_freed;
 171     GC_uncollectable_mem_recently_freed = 0;
 172
 173     GC_incr_words_allocd(GC_words_recently_allocd);
 174     GC_words_recently_allocd = 0;
 175
 176     GC_incr_mem_freed(GC_mem_recently_freed);
 177     GC_mem_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 noop, 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_words_recently_allocd += nwords;
 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_words_recently_allocd += nwords;
 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((char *)p + GC_bytes_per_word, 0,
 232                        GC_bytes_per_word * (nwords - 1));
 233                 *flh = p;
 234                 GC_aux::GC_mem_recently_freed += nwords;
 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_mem_recently_freed += nwords;
 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_words_recently_allocd += nwords;
 272             return op;
 273         }
 274         static void * ptr_free_allocate(size_t n)
 275         {
 276             size_t nwords = GC_round_up_uncollectable(n);
 277             void ** flh;
 278             void * op;
 279
 280             if (n > GC_max_fast_bytes) return GC_malloc_atomic_uncollectable(n);
 281             flh = GC_auobjfreelist_ptr + nwords;
 282             if (0 == (op = *flh)) {
 283                 return GC_aux::GC_out_of_line_malloc(nwords, GC_AUNCOLLECTABLE);
 284             }
 285             *flh = GC_obj_link(op);
 286             GC_aux::GC_uncollectable_words_recently_allocd += nwords;
 287             return op;
 288         }
 289         static void deallocate(void *p, size_t n)
 290         {
 291             size_t nwords = GC_round_up_uncollectable(n);
 292             void ** flh;
 293
 294             if (n > GC_max_fast_bytes)  {
 295                 GC_free(p);
 296             } else {
 297                 flh = GC_uobjfreelist_ptr + nwords;
 298                 GC_obj_link(p) = *flh;
 299                 *flh = p;
 300                 GC_aux::GC_uncollectable_mem_recently_freed += nwords;
 301             }
 302         }
 303         static void ptr_free_deallocate(void *p, size_t n)
 304         {
 305             size_t nwords = GC_round_up_uncollectable(n);
 306             void ** flh;
 307
 308             if (n > GC_max_fast_bytes) {
 309                 GC_free(p);
 310             } else {
 311                 flh = GC_auobjfreelist_ptr + nwords;
 312                 GC_obj_link(p) = *flh;
 313                 *flh = p;
 314                 GC_aux::GC_uncollectable_mem_recently_freed += nwords;
 315             }
 316         }
 317 };
 318
 319 typedef single_client_traceable_alloc_template<0> single_client_traceable_alloc;
 320
 321 template < int dummy >
 322 class gc_alloc_template {
 323     public:
 324         static void * allocate(size_t n) { return GC_malloc(n); }
 325         static void * ptr_free_allocate(size_t n)
 326                 { return GC_malloc_atomic(n); }
 327         static void deallocate(void *, size_t) { }
 328         static void ptr_free_deallocate(void *, size_t) { }
 329 };
 330
 331 typedef gc_alloc_template < 0 > gc_alloc;
 332
 333 template < int dummy >
 334 class traceable_alloc_template {
 335     public:
 336         static void * allocate(size_t n) { return GC_malloc_uncollectable(n); }
 337         static void * ptr_free_allocate(size_t n)
 338                 { return GC_malloc_atomic_uncollectable(n); }
 339         static void deallocate(void *p, size_t) { GC_free(p); }
 340         static void ptr_free_deallocate(void *p, size_t) { GC_free(p); }
 341 };
 342
 343 typedef traceable_alloc_template < 0 > traceable_alloc;
 344
 345 // We want to specialize simple_alloc so that it does the right thing
 346 // for all pointerfree types.  At the moment there is no portable way to
 347 // even approximate that.  The following approximation should work for
 348 // SGI compilers, and recent versions of g++.
 349
 350 # define __GC_SPECIALIZE(T,alloc) \
 351 class simple_alloc<T, alloc> { \
 352 public: \
 353     static T *allocate(size_t n) \
 354         { return 0 == n? 0 : \
 355                          (T*) alloc::ptr_free_allocate(n * sizeof (T)); } \
 356     static T *allocate(void) \
 357         { return (T*) alloc::ptr_free_allocate(sizeof (T)); } \
 358     static void deallocate(T *p, size_t n) \
 359         { if (0 != n) alloc::ptr_free_deallocate(p, n * sizeof (T)); } \
 360     static void deallocate(T *p) \
 361         { alloc::ptr_free_deallocate(p, sizeof (T)); } \
 362 };
 363
 364 __STL_BEGIN_NAMESPACE
 365
 366 __GC_SPECIALIZE(char, gc_alloc)
 367 __GC_SPECIALIZE(int, gc_alloc)
 368 __GC_SPECIALIZE(unsigned, gc_alloc)
 369 __GC_SPECIALIZE(float, gc_alloc)
 370 __GC_SPECIALIZE(double, gc_alloc)
 371
 372 __GC_SPECIALIZE(char, traceable_alloc)
 373 __GC_SPECIALIZE(int, traceable_alloc)
 374 __GC_SPECIALIZE(unsigned, traceable_alloc)
 375 __GC_SPECIALIZE(float, traceable_alloc)
 376 __GC_SPECIALIZE(double, traceable_alloc)
 377
 378 __GC_SPECIALIZE(char, single_client_gc_alloc)
 379 __GC_SPECIALIZE(int, single_client_gc_alloc)
 380 __GC_SPECIALIZE(unsigned, single_client_gc_alloc)
 381 __GC_SPECIALIZE(float, single_client_gc_alloc)
 382 __GC_SPECIALIZE(double, single_client_gc_alloc)
 383
 384 __GC_SPECIALIZE(char, single_client_traceable_alloc)
 385 __GC_SPECIALIZE(int, single_client_traceable_alloc)
 386 __GC_SPECIALIZE(unsigned, single_client_traceable_alloc)
 387 __GC_SPECIALIZE(float, single_client_traceable_alloc)
 388 __GC_SPECIALIZE(double, single_client_traceable_alloc)
 389
 390 __STL_END_NAMESPACE
 391
 392 #ifdef __STL_USE_STD_ALLOCATORS
 393
 394 __STL_BEGIN_NAMESPACE
 395
 396 template <class _Tp>
 397 struct _Alloc_traits<_Tp, gc_alloc >
 398 {
 399   static const bool _S_instanceless = true;
 400   typedef simple_alloc<_Tp, gc_alloc > _Alloc_type;
 401   typedef __allocator<_Tp, gc_alloc > allocator_type;
 402 };
 403
 404 inline bool operator==(const gc_alloc&,
 405                        const gc_alloc&)
 406 {
 407   return true;
 408 }
 409
 410 inline bool operator!=(const gc_alloc&,
 411                        const gc_alloc&)
 412 {
 413   return false;
 414 }
 415
 416 template <class _Tp>
 417 struct _Alloc_traits<_Tp, single_client_gc_alloc >
 418 {
 419   static const bool _S_instanceless = true;
 420   typedef simple_alloc<_Tp, single_client_gc_alloc > _Alloc_type;
 421   typedef __allocator<_Tp, single_client_gc_alloc > allocator_type;
 422 };
 423
 424 inline bool operator==(const single_client_gc_alloc&,
 425                        const single_client_gc_alloc&)
 426 {
 427   return true;
 428 }
 429
 430 inline bool operator!=(const single_client_gc_alloc&,
 431                        const single_client_gc_alloc&)
 432 {
 433   return false;
 434 }
 435
 436 template <class _Tp>
 437 struct _Alloc_traits<_Tp, traceable_alloc >
 438 {
 439   static const bool _S_instanceless = true;
 440   typedef simple_alloc<_Tp, traceable_alloc > _Alloc_type;
 441   typedef __allocator<_Tp, traceable_alloc > allocator_type;
 442 };
 443
 444 inline bool operator==(const traceable_alloc&,
 445                        const traceable_alloc&)
 446 {
 447   return true;
 448 }
 449
 450 inline bool operator!=(const traceable_alloc&,
 451                        const traceable_alloc&)
 452 {
 453   return false;
 454 }
 455
 456 template <class _Tp>
 457 struct _Alloc_traits<_Tp, single_client_traceable_alloc >
 458 {
 459   static const bool _S_instanceless = true;
 460   typedef simple_alloc<_Tp, single_client_traceable_alloc > _Alloc_type;
 461   typedef __allocator<_Tp, single_client_traceable_alloc > allocator_type;
 462 };
 463
 464 inline bool operator==(const single_client_traceable_alloc&,
 465                        const single_client_traceable_alloc&)
 466 {
 467   return true;
 468 }
 469
 470 inline bool operator!=(const single_client_traceable_alloc&,
 471                        const single_client_traceable_alloc&)
 472 {
 473   return false;
 474 }
 475
 476 __STL_END_NAMESPACE
 477
 478 #endif /* __STL_USE_STD_ALLOCATORS */
 479
 480 #endif /* GC_ALLOC_H */