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 C++ header file that is intended to replace the SGI STL
16 // alloc.h. This assumes SGI STL version < 3.0.
17 //
18 // This assumes the collector has been compiled with -DATOMIC_UNCOLLECTABLE
19 // and -DALL_INTERIOR_POINTERS. We also recommend
20 // -DREDIRECT_MALLOC=GC_uncollectable_malloc.
21 //
22 // Some of this could be faster in the explicit deallocation case. In particular,
23 // we spend too much time clearing objects on the free lists. That could be avoided.
24 //
25 // This uses template classes with static members, and hence does not work
26 // with g++ 2.7.2 and earlier.
27 //
28 // This code assumes that the collector itself has been compiled with a
29 // compiler that defines __STDC__ .
30 //
31
32 #include "gc.h"
33
34 #ifndef GC_ALLOC_H
35
36 #define GC_ALLOC_H
37 #define __ALLOC_H // Prevent inclusion of the default version. Ugly.
38 #define __SGI_STL_ALLOC_H
39 #define __SGI_STL_INTERNAL_ALLOC_H
40
41 #ifndef __ALLOC
42 # define __ALLOC alloc
43 #endif
44
45 #include <stddef.h>
46 #include <string.h>
47
48 // The following is just replicated from the conventional SGI alloc.h:
49
50 template<class T, class alloc>
51 class simple_alloc {
52
53 public:
allocate(size_t n)54 static T *allocate(size_t n)
55 { return 0 == n? 0 : (T*) alloc::allocate(n * sizeof (T)); }
allocate(void)56 static T *allocate(void)
57 { return (T*) alloc::allocate(sizeof (T)); }
deallocate(T * p,size_t n)58 static void deallocate(T *p, size_t n)
59 { if (0 != n) alloc::deallocate(p, n * sizeof (T)); }
deallocate(T * p)60 static void deallocate(T *p)
61 { alloc::deallocate(p, sizeof (T)); }
62 };
63
64 #include "gc.h"
65
66 // The following need to match collector data structures.
67 // We can't include gc_priv.h, since that pulls in way too much stuff.
68 // This should eventually be factored out into another include file.
69
70 extern "C" {
71 extern void ** const GC_objfreelist_ptr;
72 extern void ** const GC_aobjfreelist_ptr;
73 extern void ** const GC_uobjfreelist_ptr;
74 extern void ** const GC_auobjfreelist_ptr;
75
76 extern void GC_incr_words_allocd(size_t words);
77 extern void GC_incr_mem_freed(size_t words);
78
79 extern char * GC_generic_malloc_words_small(size_t word, int kind);
80 }
81
82 // Object kinds; must match PTRFREE, NORMAL, UNCOLLECTABLE, and
83 // AUNCOLLECTABLE in gc_priv.h.
84
85 enum { GC_PTRFREE = 0, GC_NORMAL = 1, GC_UNCOLLECTABLE = 2,
86 GC_AUNCOLLECTABLE = 3 };
87
88 enum { GC_max_fast_bytes = 255 };
89
90 enum { GC_bytes_per_word = sizeof(char *) };
91
92 enum { GC_byte_alignment = 8 };
93
94 enum { GC_word_alignment = GC_byte_alignment/GC_bytes_per_word };
95
GC_obj_link(void * p)96 inline void * &GC_obj_link(void * p)
97 { return *(void **)p; }
98
99 // Compute a number of words >= n+1 bytes.
100 // The +1 allows for pointers one past the end.
GC_round_up(size_t n)101 inline size_t GC_round_up(size_t n)
102 {
103 return ((n + GC_byte_alignment)/GC_byte_alignment)*GC_word_alignment;
104 }
105
106 // The same but don't allow for extra byte.
GC_round_up_uncollectable(size_t n)107 inline size_t GC_round_up_uncollectable(size_t n)
108 {
109 return ((n + GC_byte_alignment - 1)/GC_byte_alignment)*GC_word_alignment;
110 }
111
112 template <int dummy>
113 class GC_aux_template {
114 public:
115 // File local count of allocated words. Occasionally this is
116 // added into the global count. A separate count is necessary since the
117 // real one must be updated with a procedure call.
118 static size_t GC_words_recently_allocd;
119
120 // Same for uncollectable mmory. Not yet reflected in either
121 // GC_words_recently_allocd or GC_non_gc_bytes.
122 static size_t GC_uncollectable_words_recently_allocd;
123
124 // Similar counter for explicitly deallocated memory.
125 static size_t GC_mem_recently_freed;
126
127 // Again for uncollectable memory.
128 static size_t GC_uncollectable_mem_recently_freed;
129
130 static void * GC_out_of_line_malloc(size_t nwords, int kind);
131 };
132
133 template <int dummy>
134 size_t GC_aux_template<dummy>::GC_words_recently_allocd = 0;
135
136 template <int dummy>
137 size_t GC_aux_template<dummy>::GC_uncollectable_words_recently_allocd = 0;
138
139 template <int dummy>
140 size_t GC_aux_template<dummy>::GC_mem_recently_freed = 0;
141
142 template <int dummy>
143 size_t GC_aux_template<dummy>::GC_uncollectable_mem_recently_freed = 0;
144
145 template <int dummy>
GC_out_of_line_malloc(size_t nwords,int kind)146 void * GC_aux_template<dummy>::GC_out_of_line_malloc(size_t nwords, int kind)
147 {
148 GC_words_recently_allocd += GC_uncollectable_words_recently_allocd;
149 GC_non_gc_bytes +=
150 GC_bytes_per_word * GC_uncollectable_words_recently_allocd;
151 GC_uncollectable_words_recently_allocd = 0;
152
153 GC_mem_recently_freed += GC_uncollectable_mem_recently_freed;
154 GC_non_gc_bytes -=
155 GC_bytes_per_word * GC_uncollectable_mem_recently_freed;
156 GC_uncollectable_mem_recently_freed = 0;
157
158 GC_incr_words_allocd(GC_words_recently_allocd);
159 GC_words_recently_allocd = 0;
160
161 GC_incr_mem_freed(GC_mem_recently_freed);
162 GC_mem_recently_freed = 0;
163
164 return GC_generic_malloc_words_small(nwords, kind);
165 }
166
167 typedef GC_aux_template<0> GC_aux;
168
169 // A fast, single-threaded, garbage-collected allocator
170 // We assume the first word will be immediately overwritten.
171 // In this version, deallocation is not a noop, and explicit
172 // deallocation is likely to help performance.
173 template <int dummy>
174 class single_client_gc_alloc_template {
175 public:
allocate(size_t n)176 static void * allocate(size_t n)
177 {
178 size_t nwords = GC_round_up(n);
179 void ** flh;
180 void * op;
181
182 if (n > GC_max_fast_bytes) return GC_malloc(n);
183 flh = GC_objfreelist_ptr + nwords;
184 if (0 == (op = *flh)) {
185 return GC_aux::GC_out_of_line_malloc(nwords, GC_NORMAL);
186 }
187 *flh = GC_obj_link(op);
188 GC_aux::GC_words_recently_allocd += nwords;
189 return op;
190 }
ptr_free_allocate(size_t n)191 static void * ptr_free_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_atomic(n);
198 flh = GC_aobjfreelist_ptr + nwords;
199 if (0 == (op = *flh)) {
200 return GC_aux::GC_out_of_line_malloc(nwords, GC_PTRFREE);
201 }
202 *flh = GC_obj_link(op);
203 GC_aux::GC_words_recently_allocd += nwords;
204 return op;
205 }
deallocate(void * p,size_t n)206 static void deallocate(void *p, size_t n)
207 {
208 size_t nwords = GC_round_up(n);
209 void ** flh;
210
211 if (n > GC_max_fast_bytes) {
212 GC_free(p);
213 } else {
214 flh = GC_objfreelist_ptr + nwords;
215 GC_obj_link(p) = *flh;
216 memset((char *)p + GC_bytes_per_word, 0,
217 GC_bytes_per_word * (nwords - 1));
218 *flh = p;
219 GC_aux::GC_mem_recently_freed += nwords;
220 }
221 }
ptr_free_deallocate(void * p,size_t n)222 static void ptr_free_deallocate(void *p, size_t n)
223 {
224 size_t nwords = GC_round_up(n);
225 void ** flh;
226
227 if (n > GC_max_fast_bytes) {
228 GC_free(p);
229 } else {
230 flh = GC_aobjfreelist_ptr + nwords;
231 GC_obj_link(p) = *flh;
232 *flh = p;
233 GC_aux::GC_mem_recently_freed += nwords;
234 }
235 }
236 };
237
238 typedef single_client_gc_alloc_template<0> single_client_gc_alloc;
239
240 // Once more, for uncollectable objects.
241 template <int dummy>
242 class single_client_alloc_template {
243 public:
allocate(size_t n)244 static void * allocate(size_t n)
245 {
246 size_t nwords = GC_round_up_uncollectable(n);
247 void ** flh;
248 void * op;
249
250 if (n > GC_max_fast_bytes) return GC_malloc_uncollectable(n);
251 flh = GC_uobjfreelist_ptr + nwords;
252 if (0 == (op = *flh)) {
253 return GC_aux::GC_out_of_line_malloc(nwords, GC_UNCOLLECTABLE);
254 }
255 *flh = GC_obj_link(op);
256 GC_aux::GC_uncollectable_words_recently_allocd += nwords;
257 return op;
258 }
ptr_free_allocate(size_t n)259 static void * ptr_free_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_atomic_uncollectable(n);
266 flh = GC_auobjfreelist_ptr + nwords;
267 if (0 == (op = *flh)) {
268 return GC_aux::GC_out_of_line_malloc(nwords, GC_AUNCOLLECTABLE);
269 }
270 *flh = GC_obj_link(op);
271 GC_aux::GC_uncollectable_words_recently_allocd += nwords;
272 return op;
273 }
deallocate(void * p,size_t n)274 static void deallocate(void *p, size_t n)
275 {
276 size_t nwords = GC_round_up_uncollectable(n);
277 void ** flh;
278
279 if (n > GC_max_fast_bytes) {
280 GC_free(p);
281 } else {
282 flh = GC_uobjfreelist_ptr + nwords;
283 GC_obj_link(p) = *flh;
284 *flh = p;
285 GC_aux::GC_uncollectable_mem_recently_freed += nwords;
286 }
287 }
ptr_free_deallocate(void * p,size_t n)288 static void ptr_free_deallocate(void *p, size_t n)
289 {
290 size_t nwords = GC_round_up_uncollectable(n);
291 void ** flh;
292
293 if (n > GC_max_fast_bytes) {
294 GC_free(p);
295 } else {
296 flh = GC_auobjfreelist_ptr + nwords;
297 GC_obj_link(p) = *flh;
298 *flh = p;
299 GC_aux::GC_uncollectable_mem_recently_freed += nwords;
300 }
301 }
302 };
303
304 typedef single_client_alloc_template<0> single_client_alloc;
305
306 template < int dummy >
307 class gc_alloc_template {
308 public:
allocate(size_t n)309 static void * allocate(size_t n) { return GC_malloc(n); }
ptr_free_allocate(size_t n)310 static void * ptr_free_allocate(size_t n)
311 { return GC_malloc_atomic(n); }
deallocate(void *,size_t)312 static void deallocate(void *, size_t) { }
ptr_free_deallocate(void *,size_t)313 static void ptr_free_deallocate(void *, size_t) { }
314 };
315
316 typedef gc_alloc_template < 0 > gc_alloc;
317
318 template < int dummy >
319 class alloc_template {
320 public:
allocate(size_t n)321 static void * allocate(size_t n) { return GC_malloc_uncollectable(n); }
ptr_free_allocate(size_t n)322 static void * ptr_free_allocate(size_t n)
323 { return GC_malloc_atomic_uncollectable(n); }
deallocate(void * p,size_t)324 static void deallocate(void *p, size_t) { GC_free(p); }
ptr_free_deallocate(void * p,size_t)325 static void ptr_free_deallocate(void *p, size_t) { GC_free(p); }
326 };
327
328 typedef alloc_template < 0 > alloc;
329
330 #ifdef _SGI_SOURCE
331
332 // We want to specialize simple_alloc so that it does the right thing
333 // for all pointerfree types. At the moment there is no portable way to
334 // even approximate that. The following approximation should work for
335 // SGI compilers, and perhaps some others.
336
337 # define __GC_SPECIALIZE(T,alloc) \
338 class simple_alloc<T, alloc> { \
339 public: \
340 static T *allocate(size_t n) \
341 { return 0 == n? 0 : \
342 (T*) alloc::ptr_free_allocate(n * sizeof (T)); } \
343 static T *allocate(void) \
344 { return (T*) alloc::ptr_free_allocate(sizeof (T)); } \
345 static void deallocate(T *p, size_t n) \
346 { if (0 != n) alloc::ptr_free_deallocate(p, n * sizeof (T)); } \
347 static void deallocate(T *p) \
348 { alloc::ptr_free_deallocate(p, sizeof (T)); } \
349 };
350
351 __GC_SPECIALIZE(char, gc_alloc)
352 __GC_SPECIALIZE(int, gc_alloc)
353 __GC_SPECIALIZE(unsigned, gc_alloc)
354 __GC_SPECIALIZE(float, gc_alloc)
355 __GC_SPECIALIZE(double, gc_alloc)
356
357 __GC_SPECIALIZE(char, alloc)
358 __GC_SPECIALIZE(int, alloc)
359 __GC_SPECIALIZE(unsigned, alloc)
360 __GC_SPECIALIZE(float, alloc)
361 __GC_SPECIALIZE(double, alloc)
362
363 __GC_SPECIALIZE(char, single_client_gc_alloc)
364 __GC_SPECIALIZE(int, single_client_gc_alloc)
365 __GC_SPECIALIZE(unsigned, single_client_gc_alloc)
366 __GC_SPECIALIZE(float, single_client_gc_alloc)
367 __GC_SPECIALIZE(double, single_client_gc_alloc)
368
369 __GC_SPECIALIZE(char, single_client_alloc)
370 __GC_SPECIALIZE(int, single_client_alloc)
371 __GC_SPECIALIZE(unsigned, single_client_alloc)
372 __GC_SPECIALIZE(float, single_client_alloc)
373 __GC_SPECIALIZE(double, single_client_alloc)
374
375 #ifdef __STL_USE_STD_ALLOCATORS
376
377 ???copy stuff from stl_alloc.h or remove it to a different file ???
378
379 #endif /* __STL_USE_STD_ALLOCATORS */
380
381 #endif /* _SGI_SOURCE */
382
383 #endif /* GC_ALLOC_H */
384