51488
|
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 _T>
|
|
397 struct _Alloc_traits<_T, gc_alloc >
|
|
398 {
|
|
399 static const bool _S_instanceless = true;
|
|
400 typedef simple_alloc<_T, gc_alloc > _Alloc_type;
|
|
401 typedef __allocator<_T, 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 _T>
|
|
417 struct _Alloc_traits<_T, single_client_gc_alloc >
|
|
418 {
|
|
419 static const bool _S_instanceless = true;
|
|
420 typedef simple_alloc<_T, single_client_gc_alloc > _Alloc_type;
|
|
421 typedef __allocator<_T, 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 _T>
|
|
437 struct _Alloc_traits<_T, traceable_alloc >
|
|
438 {
|
|
439 static const bool _S_instanceless = true;
|
|
440 typedef simple_alloc<_T, traceable_alloc > _Alloc_type;
|
|
441 typedef __allocator<_T, 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 _T>
|
|
457 struct _Alloc_traits<_T, single_client_traceable_alloc >
|
|
458 {
|
|
459 static const bool _S_instanceless = true;
|
|
460 typedef simple_alloc<_T, single_client_traceable_alloc > _Alloc_type;
|
|
461 typedef __allocator<_T, 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 */
|