3 // Copyright (C) 2004 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Librarbooly. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
34 #include <bits/c++config.h>
35 #include <ext/mt_allocator.h>
36 #include <bits/concurrence.h>
38 namespace __gnu_internal
40 __glibcxx_mutex_define_initialized(freelist_mutex
);
43 __gthread_key_t freelist_key
;
51 __pool
<true>::_M_reclaim_memory(char* __p
, size_t __bytes
)
53 // Round up to power of 2 and figure out which bin to use.
54 const size_t __which
= _M_binmap
[__bytes
];
55 const _Bin_record
& __bin
= _M_bin
[__which
];
56 const _Tune
& __options
= _M_get_options();
58 char* __c
= __p
- __options
._M_align
;
59 _Block_record
* __block
= reinterpret_cast<_Block_record
*>(__c
);
61 if (__gthread_active_p())
63 // Calculate the number of records to remove from our freelist:
64 // in order to avoid too much contention we wait until the
65 // number of records is "high enough".
66 const size_t __thread_id
= _M_get_thread_id();
68 long __remove
= ((__bin
._M_free
[__thread_id
]
69 * __options
._M_freelist_headroom
)
70 - __bin
._M_used
[__thread_id
]);
71 if (__remove
> static_cast<long>(100 * (_M_bin_size
- __which
)
72 * __options
._M_freelist_headroom
)
73 && __remove
> static_cast<long>(__bin
._M_free
[__thread_id
]))
75 _Block_record
* __tmp
= __bin
._M_first
[__thread_id
];
76 _Block_record
* __first
= __tmp
;
77 __remove
/= __options
._M_freelist_headroom
;
78 const long __removed
= __remove
;
80 while (__remove
-- > 0)
81 __tmp
= __tmp
->_M_next
;
82 __bin
._M_first
[__thread_id
] = __tmp
->_M_next
;
83 __bin
._M_free
[__thread_id
] -= __removed
;
85 __gthread_mutex_lock(__bin
._M_mutex
);
86 __tmp
->_M_next
= __bin
._M_first
[0];
87 __bin
._M_first
[0] = __first
;
88 __bin
._M_free
[0] += __removed
;
89 __gthread_mutex_unlock(__bin
._M_mutex
);
92 // Return this block to our list and update counters and
93 // owner id as needed.
94 --__bin
._M_used
[__block
->_M_thread_id
];
96 __block
->_M_next
= __bin
._M_first
[__thread_id
];
97 __bin
._M_first
[__thread_id
] = __block
;
99 ++__bin
._M_free
[__thread_id
];
103 // Not using threads, so single threaded application - return
105 __block
->_M_next
= __bin
._M_first
[0];
106 __bin
._M_first
[0] = __block
;
112 __pool
<false>::_M_reclaim_memory(char* __p
, size_t __bytes
)
114 // Round up to power of 2 and figure out which bin to use.
115 const size_t __which
= _M_binmap
[__bytes
];
116 const _Bin_record
& __bin
= _M_bin
[__which
];
117 const _Tune
& __options
= _M_get_options();
119 char* __c
= __p
- __options
._M_align
;
120 _Block_record
* __block
= reinterpret_cast<_Block_record
*>(__c
);
122 // Single threaded application - return to global pool.
123 __block
->_M_next
= __bin
._M_first
[0];
124 __bin
._M_first
[0] = __block
;
129 __pool
<true>::_M_reserve_memory(size_t __bytes
, const size_t __thread_id
)
131 // Round up to power of 2 and figure out which bin to use.
132 const size_t __which
= _M_binmap
[__bytes
];
134 // If here, there are no blocks on our freelist.
135 const _Tune
& __options
= _M_get_options();
136 _Block_record
* __block
= NULL
;
137 const _Bin_record
& __bin
= _M_bin
[__which
];
139 // NB: For alignment reasons, we can't use the first _M_align
140 // bytes, even when sizeof(_Block_record) < _M_align.
141 const size_t __bin_size
= ((__options
._M_min_bin
<< __which
)
142 + __options
._M_align
);
143 size_t __block_count
= __options
._M_chunk_size
/ __bin_size
;
145 // Are we using threads?
146 // - Yes, check if there are free blocks on the global
147 // list. If so, grab up to __block_count blocks in one
148 // lock and change ownership. If the global list is
149 // empty, we allocate a new chunk and add those blocks
150 // directly to our own freelist (with us as owner).
151 // - No, all operations are made directly to global pool 0
152 // no need to lock or change ownership but check for free
153 // blocks on global list (and if not add new ones) and
154 // get the first one.
155 if (__gthread_active_p())
157 __gthread_mutex_lock(__bin
._M_mutex
);
158 if (__bin
._M_first
[0] == NULL
)
160 // No need to hold the lock when we are adding a
161 // whole chunk to our own list.
162 __gthread_mutex_unlock(__bin
._M_mutex
);
164 void* __v
= ::operator new(__options
._M_chunk_size
);
165 __bin
._M_first
[__thread_id
] = static_cast<_Block_record
*>(__v
);
166 __bin
._M_free
[__thread_id
] = __block_count
;
169 __block
= __bin
._M_first
[__thread_id
];
170 while (__block_count
-- > 0)
172 char* __c
= reinterpret_cast<char*>(__block
) + __bin_size
;
173 __block
->_M_next
= reinterpret_cast<_Block_record
*>(__c
);
174 __block
= __block
->_M_next
;
176 __block
->_M_next
= NULL
;
180 // Is the number of required blocks greater than or
181 // equal to the number that can be provided by the
183 __bin
._M_first
[__thread_id
] = __bin
._M_first
[0];
184 if (__block_count
>= __bin
._M_free
[0])
186 __bin
._M_free
[__thread_id
] = __bin
._M_free
[0];
187 __bin
._M_free
[0] = 0;
188 __bin
._M_first
[0] = NULL
;
192 __bin
._M_free
[__thread_id
] = __block_count
;
193 __bin
._M_free
[0] -= __block_count
;
195 __block
= __bin
._M_first
[0];
196 while (__block_count
-- > 0)
197 __block
= __block
->_M_next
;
198 __bin
._M_first
[0] = __block
->_M_next
;
199 __block
->_M_next
= NULL
;
201 __gthread_mutex_unlock(__bin
._M_mutex
);
206 void* __v
= ::operator new(__options
._M_chunk_size
);
207 __bin
._M_first
[0] = static_cast<_Block_record
*>(__v
);
210 __block
= __bin
._M_first
[0];
211 while (__block_count
-- > 0)
213 char* __c
= reinterpret_cast<char*>(__block
) + __bin_size
;
214 __block
->_M_next
= reinterpret_cast<_Block_record
*>(__c
);
215 __block
= __block
->_M_next
;
217 __block
->_M_next
= NULL
;
220 __block
= __bin
._M_first
[__thread_id
];
221 __bin
._M_first
[__thread_id
] = __bin
._M_first
[__thread_id
]->_M_next
;
223 if (__gthread_active_p())
225 __block
->_M_thread_id
= __thread_id
;
226 --__bin
._M_free
[__thread_id
];
227 ++__bin
._M_used
[__thread_id
];
229 return reinterpret_cast<char*>(__block
) + __options
._M_align
;
234 __pool
<false>::_M_reserve_memory(size_t __bytes
, const size_t __thread_id
)
236 // Round up to power of 2 and figure out which bin to use.
237 const size_t __which
= _M_binmap
[__bytes
];
239 // If here, there are no blocks on our freelist.
240 const _Tune
& __options
= _M_get_options();
241 _Block_record
* __block
= NULL
;
242 const _Bin_record
& __bin
= _M_bin
[__which
];
244 // NB: For alignment reasons, we can't use the first _M_align
245 // bytes, even when sizeof(_Block_record) < _M_align.
246 const size_t __bin_size
= ((__options
._M_min_bin
<< __which
)
247 + __options
._M_align
);
248 size_t __block_count
= __options
._M_chunk_size
/ __bin_size
;
250 // Not using threads.
251 void* __v
= ::operator new(__options
._M_chunk_size
);
252 __bin
._M_first
[0] = static_cast<_Block_record
*>(__v
);
255 __block
= __bin
._M_first
[0];
256 while (__block_count
-- > 0)
258 char* __c
= reinterpret_cast<char*>(__block
) + __bin_size
;
259 __block
->_M_next
= reinterpret_cast<_Block_record
*>(__c
);
260 __block
= __block
->_M_next
;
262 __block
->_M_next
= NULL
;
264 __block
= __bin
._M_first
[__thread_id
];
265 __bin
._M_first
[__thread_id
] = __bin
._M_first
[__thread_id
]->_M_next
;
266 return reinterpret_cast<char*>(__block
) + __options
._M_align
;
271 __pool
<true>::_M_initialize(__destroy_handler __d
)
273 // This method is called on the first allocation (when _M_init
274 // is still false) to create the bins.
276 // _M_force_new must not change after the first allocate(),
277 // which in turn calls this method, so if it's false, it's false
278 // forever and we don't need to return here ever again.
279 if (_M_options
._M_force_new
)
285 // Calculate the number of bins required based on _M_max_bytes.
286 // _M_bin_size is statically-initialized to one.
287 size_t __bin_size
= _M_options
._M_min_bin
;
288 while (_M_options
._M_max_bytes
> __bin_size
)
294 // Setup the bin map for quick lookup of the relevant bin.
295 const size_t __j
= (_M_options
._M_max_bytes
+ 1) * sizeof(_Binmap_type
);
296 _M_binmap
= static_cast<_Binmap_type
*>(::operator new(__j
));
298 _Binmap_type
* __bp
= _M_binmap
;
299 _Binmap_type __bin_max
= _M_options
._M_min_bin
;
300 _Binmap_type __bint
= 0;
301 for (_Binmap_type __ct
= 0; __ct
<= _M_options
._M_max_bytes
; ++__ct
)
303 if (__ct
> __bin_max
)
311 // Initialize _M_bin and its members.
312 void* __v
= ::operator new(sizeof(_Bin_record
) * _M_bin_size
);
313 _M_bin
= static_cast<_Bin_record
*>(__v
);
315 // If __gthread_active_p() create and initialize the list of
316 // free thread ids. Single threaded applications use thread id 0
317 // directly and have no need for this.
318 if (__gthread_active_p())
320 const size_t __k
= sizeof(_Thread_record
) * _M_options
._M_max_threads
;
321 __v
= ::operator new(__k
);
322 _M_thread_freelist
= static_cast<_Thread_record
*>(__v
);
324 // NOTE! The first assignable thread id is 1 since the
325 // global pool uses id 0
327 for (__i
= 1; __i
< _M_options
._M_max_threads
; ++__i
)
329 _Thread_record
& __tr
= _M_thread_freelist
[__i
- 1];
330 __tr
._M_next
= &_M_thread_freelist
[__i
];
335 _M_thread_freelist
[__i
- 1]._M_next
= NULL
;
336 _M_thread_freelist
[__i
- 1]._M_id
= __i
;
338 // Initialize per thread key to hold pointer to
339 // _M_thread_freelist.
340 __gthread_key_create(&__gnu_internal::freelist_key
, __d
);
342 const size_t __max_threads
= _M_options
._M_max_threads
+ 1;
343 for (size_t __n
= 0; __n
< _M_bin_size
; ++__n
)
345 _Bin_record
& __bin
= _M_bin
[__n
];
346 __v
= ::operator new(sizeof(_Block_record
*) * __max_threads
);
347 __bin
._M_first
= static_cast<_Block_record
**>(__v
);
349 __v
= ::operator new(sizeof(size_t) * __max_threads
);
350 __bin
._M_free
= static_cast<size_t*>(__v
);
352 __v
= ::operator new(sizeof(size_t) * __max_threads
);
353 __bin
._M_used
= static_cast<size_t*>(__v
);
355 __v
= ::operator new(sizeof(__gthread_mutex_t
));
356 __bin
._M_mutex
= static_cast<__gthread_mutex_t
*>(__v
);
358 #ifdef __GTHREAD_MUTEX_INIT
360 // Do not copy a POSIX/gthr mutex once in use.
361 __gthread_mutex_t __tmp
= __GTHREAD_MUTEX_INIT
;
362 *__bin
._M_mutex
= __tmp
;
365 { __GTHREAD_MUTEX_INIT_FUNCTION(__bin
._M_mutex
); }
368 for (size_t __threadn
= 0; __threadn
< __max_threads
;
371 __bin
._M_first
[__threadn
] = NULL
;
372 __bin
._M_free
[__threadn
] = 0;
373 __bin
._M_used
[__threadn
] = 0;
378 for (size_t __n
= 0; __n
< _M_bin_size
; ++__n
)
380 _Bin_record
& __bin
= _M_bin
[__n
];
381 __v
= ::operator new(sizeof(_Block_record
*));
382 __bin
._M_first
= static_cast<_Block_record
**>(__v
);
383 __bin
._M_first
[0] = NULL
;
390 __pool
<false>::_M_initialize()
392 // This method is called on the first allocation (when _M_init
393 // is still false) to create the bins.
395 // _M_force_new must not change after the first allocate(),
396 // which in turn calls this method, so if it's false, it's false
397 // forever and we don't need to return here ever again.
398 if (_M_options
._M_force_new
)
404 // Calculate the number of bins required based on _M_max_bytes.
405 // _M_bin_size is statically-initialized to one.
406 size_t __bin_size
= _M_options
._M_min_bin
;
407 while (_M_options
._M_max_bytes
> __bin_size
)
413 // Setup the bin map for quick lookup of the relevant bin.
414 const size_t __j
= (_M_options
._M_max_bytes
+ 1) * sizeof(_Binmap_type
);
415 _M_binmap
= static_cast<_Binmap_type
*>(::operator new(__j
));
417 _Binmap_type
* __bp
= _M_binmap
;
418 _Binmap_type __bin_max
= _M_options
._M_min_bin
;
419 _Binmap_type __bint
= 0;
420 for (_Binmap_type __ct
= 0; __ct
<= _M_options
._M_max_bytes
; ++__ct
)
422 if (__ct
> __bin_max
)
430 // Initialize _M_bin and its members.
431 void* __v
= ::operator new(sizeof(_Bin_record
) * _M_bin_size
);
432 _M_bin
= static_cast<_Bin_record
*>(__v
);
434 for (size_t __n
= 0; __n
< _M_bin_size
; ++__n
)
436 _Bin_record
& __bin
= _M_bin
[__n
];
437 __v
= ::operator new(sizeof(_Block_record
*));
438 __bin
._M_first
= static_cast<_Block_record
**>(__v
);
439 __bin
._M_first
[0] = NULL
;
446 __pool
<true>::_M_get_thread_id()
448 // If we have thread support and it's active we check the thread
449 // key value and return its id or if it's not set we take the
450 // first record from _M_thread_freelist and sets the key and
452 if (__gthread_active_p())
454 void* v
= __gthread_getspecific(__gnu_internal::freelist_key
);
455 _Thread_record
* __freelist_pos
= static_cast<_Thread_record
*>(v
);
456 if (__freelist_pos
== NULL
)
458 // Since _M_options._M_max_threads must be larger than
459 // the theoretical max number of threads of the OS the
460 // list can never be empty.
462 __gnu_cxx::lock
sentry(__gnu_internal::freelist_mutex
);
463 __freelist_pos
= _M_thread_freelist
;
464 _M_thread_freelist
= _M_thread_freelist
->_M_next
;
467 __gthread_setspecific(__gnu_internal::freelist_key
,
468 static_cast<void*>(__freelist_pos
));
470 return __freelist_pos
->_M_id
;
473 // Otherwise (no thread support or inactive) all requests are
474 // served from the global pool 0.
479 __pool
<true>::_M_destroy_thread_key(void* __freelist_pos
)
481 // Return this thread id record to front of thread_freelist.
482 __gnu_cxx::lock
sentry(__gnu_internal::freelist_mutex
);
483 _Thread_record
* __tr
= static_cast<_Thread_record
*>(__freelist_pos
);
484 __tr
->_M_next
= _M_thread_freelist
;
485 _M_thread_freelist
= __tr
;
489 // Definitions for non-exported bits of __common_pool.
492 __common_pool_policy
<true>::_S_data
= __pool
<true>();
495 __common_pool_policy
<true>::_S_get_pool() { return _S_data
; }
500 __common_pool_policy
<false>::_S_data
= __pool
<false>();
504 __common_pool_policy
<false>::_S_get_pool() { return _S_data
; }
507 template class __mt_alloc
<char>;
508 template class __mt_alloc
<wchar_t>;
509 } // namespace __gnu_cxx