163d1a8abSmrg // Allocator details. 263d1a8abSmrg 3*ec02198aSmrg // Copyright (C) 2004-2020 Free Software Foundation, Inc. 463d1a8abSmrg // 563d1a8abSmrg // This file is part of the GNU ISO C++ Library. This library is free 663d1a8abSmrg // software; you can redistribute it and/or modify it under the 763d1a8abSmrg // terms of the GNU General Public License as published by the 863d1a8abSmrg // Free Software Foundation; either version 3, or (at your option) 963d1a8abSmrg // any later version. 1063d1a8abSmrg 1163d1a8abSmrg // This library is distributed in the hope that it will be useful, 1263d1a8abSmrg // but WITHOUT ANY WARRANTY; without even the implied warranty of 1363d1a8abSmrg // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1463d1a8abSmrg // GNU General Public License for more details. 1563d1a8abSmrg 1663d1a8abSmrg // Under Section 7 of GPL version 3, you are granted additional 1763d1a8abSmrg // permissions described in the GCC Runtime Library Exception, version 1863d1a8abSmrg // 3.1, as published by the Free Software Foundation. 1963d1a8abSmrg 2063d1a8abSmrg // You should have received a copy of the GNU General Public License and 2163d1a8abSmrg // a copy of the GCC Runtime Library Exception along with this program; 2263d1a8abSmrg // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2363d1a8abSmrg // <http://www.gnu.org/licenses/>. 2463d1a8abSmrg 2563d1a8abSmrg // 2663d1a8abSmrg // ISO C++ 14882: 2763d1a8abSmrg // 2863d1a8abSmrg 2963d1a8abSmrg #include <bits/c++config.h> 3063d1a8abSmrg #include <ext/concurrence.h> 3163d1a8abSmrg #include <ext/mt_allocator.h> 3263d1a8abSmrg #include <cstring> 3363d1a8abSmrg 3463d1a8abSmrg // The include file is needed for uintptr_t. If this file does not compile, 3563d1a8abSmrg // check to make sure the target has <stdint.h> and that it provides 3663d1a8abSmrg // uintptr_t. 3763d1a8abSmrg #include <stdint.h> 3863d1a8abSmrg 3963d1a8abSmrg namespace 4063d1a8abSmrg { 4163d1a8abSmrg #ifdef __GTHREADS 4263d1a8abSmrg struct __freelist 4363d1a8abSmrg { 4463d1a8abSmrg typedef __gnu_cxx::__pool<true>::_Thread_record _Thread_record; 4563d1a8abSmrg _Thread_record* _M_thread_freelist; 4663d1a8abSmrg _Thread_record* _M_thread_freelist_array; 4763d1a8abSmrg size_t _M_max_threads; 4863d1a8abSmrg __gthread_key_t _M_key; 4963d1a8abSmrg ~__freelist__anoncaf632960111::__freelist5063d1a8abSmrg ~__freelist() 5163d1a8abSmrg { 5263d1a8abSmrg if (_M_thread_freelist_array) 5363d1a8abSmrg { 5463d1a8abSmrg __gthread_key_delete(_M_key); 5563d1a8abSmrg ::operator delete(static_cast<void*>(_M_thread_freelist_array)); 5663d1a8abSmrg _M_thread_freelist = 0; 5763d1a8abSmrg } 5863d1a8abSmrg } 5963d1a8abSmrg }; 6063d1a8abSmrg 6163d1a8abSmrg __freelist& get_freelist()6263d1a8abSmrg get_freelist() 6363d1a8abSmrg { 6463d1a8abSmrg static __freelist freelist; 6563d1a8abSmrg return freelist; 6663d1a8abSmrg } 6763d1a8abSmrg 6863d1a8abSmrg __gnu_cxx::__mutex& get_freelist_mutex()6963d1a8abSmrg get_freelist_mutex() 7063d1a8abSmrg { 7163d1a8abSmrg static __gnu_cxx::__mutex freelist_mutex; 7263d1a8abSmrg return freelist_mutex; 7363d1a8abSmrg } 7463d1a8abSmrg 7563d1a8abSmrg static void _M_destroy_thread_key(void * __id)7663d1a8abSmrg _M_destroy_thread_key(void* __id) 7763d1a8abSmrg { 7863d1a8abSmrg // Return this thread id record to the front of thread_freelist. 7963d1a8abSmrg __freelist& freelist = get_freelist(); 8063d1a8abSmrg { 8163d1a8abSmrg __gnu_cxx::__scoped_lock sentry(get_freelist_mutex()); 8263d1a8abSmrg uintptr_t _M_id = reinterpret_cast<uintptr_t>(__id); 8363d1a8abSmrg 8463d1a8abSmrg typedef __gnu_cxx::__pool<true>::_Thread_record _Thread_record; 8563d1a8abSmrg _Thread_record* __tr = &freelist._M_thread_freelist_array[_M_id - 1]; 8663d1a8abSmrg __tr->_M_next = freelist._M_thread_freelist; 8763d1a8abSmrg freelist._M_thread_freelist = __tr; 8863d1a8abSmrg } 8963d1a8abSmrg } 9063d1a8abSmrg #endif 9163d1a8abSmrg } // anonymous namespace 9263d1a8abSmrg 9363d1a8abSmrg namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 9463d1a8abSmrg { 9563d1a8abSmrg _GLIBCXX_BEGIN_NAMESPACE_VERSION 9663d1a8abSmrg 9763d1a8abSmrg void _M_destroy()9863d1a8abSmrg __pool<false>::_M_destroy() throw() 9963d1a8abSmrg { 10063d1a8abSmrg if (_M_init && !_M_options._M_force_new) 10163d1a8abSmrg { 10263d1a8abSmrg for (size_t __n = 0; __n < _M_bin_size; ++__n) 10363d1a8abSmrg { 10463d1a8abSmrg _Bin_record& __bin = _M_bin[__n]; 10563d1a8abSmrg while (__bin._M_address) 10663d1a8abSmrg { 10763d1a8abSmrg _Block_address* __tmp = __bin._M_address->_M_next; 10863d1a8abSmrg ::operator delete(__bin._M_address->_M_initial); 10963d1a8abSmrg __bin._M_address = __tmp; 11063d1a8abSmrg } 11163d1a8abSmrg ::operator delete(__bin._M_first); 11263d1a8abSmrg } 11363d1a8abSmrg ::operator delete(_M_bin); 11463d1a8abSmrg ::operator delete(_M_binmap); 11563d1a8abSmrg } 11663d1a8abSmrg } 11763d1a8abSmrg 11863d1a8abSmrg void _M_reclaim_block(char * __p,size_t __bytes)11963d1a8abSmrg __pool<false>::_M_reclaim_block(char* __p, size_t __bytes) throw () 12063d1a8abSmrg { 12163d1a8abSmrg // Round up to power of 2 and figure out which bin to use. 12263d1a8abSmrg const size_t __which = _M_binmap[__bytes]; 12363d1a8abSmrg _Bin_record& __bin = _M_bin[__which]; 12463d1a8abSmrg 12563d1a8abSmrg char* __c = __p - _M_get_align(); 12663d1a8abSmrg _Block_record* __block = reinterpret_cast<_Block_record*>(__c); 12763d1a8abSmrg 12863d1a8abSmrg // Single threaded application - return to global pool. 12963d1a8abSmrg __block->_M_next = __bin._M_first[0]; 13063d1a8abSmrg __bin._M_first[0] = __block; 13163d1a8abSmrg } 13263d1a8abSmrg 13363d1a8abSmrg char* _M_reserve_block(size_t __bytes,const size_t __thread_id)13463d1a8abSmrg __pool<false>::_M_reserve_block(size_t __bytes, const size_t __thread_id) 13563d1a8abSmrg { 13663d1a8abSmrg // Round up to power of 2 and figure out which bin to use. 13763d1a8abSmrg const size_t __which = _M_binmap[__bytes]; 13863d1a8abSmrg _Bin_record& __bin = _M_bin[__which]; 13963d1a8abSmrg const _Tune& __options = _M_get_options(); 14063d1a8abSmrg const size_t __bin_size = (__options._M_min_bin << __which) 14163d1a8abSmrg + __options._M_align; 14263d1a8abSmrg size_t __block_count = __options._M_chunk_size - sizeof(_Block_address); 14363d1a8abSmrg __block_count /= __bin_size; 14463d1a8abSmrg 14563d1a8abSmrg // Get a new block dynamically, set it up for use. 14663d1a8abSmrg void* __v = ::operator new(__options._M_chunk_size); 14763d1a8abSmrg _Block_address* __address = static_cast<_Block_address*>(__v); 14863d1a8abSmrg __address->_M_initial = __v; 14963d1a8abSmrg __address->_M_next = __bin._M_address; 15063d1a8abSmrg __bin._M_address = __address; 15163d1a8abSmrg 15263d1a8abSmrg char* __c = static_cast<char*>(__v) + sizeof(_Block_address); 15363d1a8abSmrg _Block_record* __block = reinterpret_cast<_Block_record*>(__c); 15463d1a8abSmrg __bin._M_first[__thread_id] = __block; 15563d1a8abSmrg while (--__block_count > 0) 15663d1a8abSmrg { 15763d1a8abSmrg __c += __bin_size; 15863d1a8abSmrg __block->_M_next = reinterpret_cast<_Block_record*>(__c); 15963d1a8abSmrg __block = __block->_M_next; 16063d1a8abSmrg } 16163d1a8abSmrg __block->_M_next = 0; 16263d1a8abSmrg 16363d1a8abSmrg __block = __bin._M_first[__thread_id]; 16463d1a8abSmrg __bin._M_first[__thread_id] = __block->_M_next; 16563d1a8abSmrg 16663d1a8abSmrg // NB: For alignment reasons, we can't use the first _M_align 16763d1a8abSmrg // bytes, even when sizeof(_Block_record) < _M_align. 16863d1a8abSmrg return reinterpret_cast<char*>(__block) + __options._M_align; 16963d1a8abSmrg } 17063d1a8abSmrg 17163d1a8abSmrg void _M_initialize()17263d1a8abSmrg __pool<false>::_M_initialize() 17363d1a8abSmrg { 17463d1a8abSmrg // _M_force_new must not change after the first allocate(), which 17563d1a8abSmrg // in turn calls this method, so if it's false, it's false forever 17663d1a8abSmrg // and we don't need to return here ever again. 17763d1a8abSmrg if (_M_options._M_force_new) 17863d1a8abSmrg { 17963d1a8abSmrg _M_init = true; 18063d1a8abSmrg return; 18163d1a8abSmrg } 18263d1a8abSmrg 18363d1a8abSmrg // Create the bins. 18463d1a8abSmrg // Calculate the number of bins required based on _M_max_bytes. 18563d1a8abSmrg // _M_bin_size is statically-initialized to one. 18663d1a8abSmrg size_t __bin_size = _M_options._M_min_bin; 18763d1a8abSmrg while (_M_options._M_max_bytes > __bin_size) 18863d1a8abSmrg { 18963d1a8abSmrg __bin_size <<= 1; 19063d1a8abSmrg ++_M_bin_size; 19163d1a8abSmrg } 19263d1a8abSmrg 19363d1a8abSmrg // Setup the bin map for quick lookup of the relevant bin. 19463d1a8abSmrg const size_t __j = (_M_options._M_max_bytes + 1) * sizeof(_Binmap_type); 19563d1a8abSmrg _M_binmap = static_cast<_Binmap_type*>(::operator new(__j)); 19663d1a8abSmrg _Binmap_type* __bp = _M_binmap; 19763d1a8abSmrg _Binmap_type __bin_max = _M_options._M_min_bin; 19863d1a8abSmrg _Binmap_type __bint = 0; 19963d1a8abSmrg for (_Binmap_type __ct = 0; __ct <= _M_options._M_max_bytes; ++__ct) 20063d1a8abSmrg { 20163d1a8abSmrg if (__ct > __bin_max) 20263d1a8abSmrg { 20363d1a8abSmrg __bin_max <<= 1; 20463d1a8abSmrg ++__bint; 20563d1a8abSmrg } 20663d1a8abSmrg *__bp++ = __bint; 20763d1a8abSmrg } 20863d1a8abSmrg 20963d1a8abSmrg // Initialize _M_bin and its members. 21063d1a8abSmrg void* __v = ::operator new(sizeof(_Bin_record) * _M_bin_size); 21163d1a8abSmrg _M_bin = static_cast<_Bin_record*>(__v); 21263d1a8abSmrg for (size_t __n = 0; __n < _M_bin_size; ++__n) 21363d1a8abSmrg { 21463d1a8abSmrg _Bin_record& __bin = _M_bin[__n]; 21563d1a8abSmrg __v = ::operator new(sizeof(_Block_record*)); 21663d1a8abSmrg __bin._M_first = static_cast<_Block_record**>(__v); 21763d1a8abSmrg __bin._M_first[0] = 0; 21863d1a8abSmrg __bin._M_address = 0; 21963d1a8abSmrg } 22063d1a8abSmrg _M_init = true; 22163d1a8abSmrg } 22263d1a8abSmrg 22363d1a8abSmrg 22463d1a8abSmrg #ifdef __GTHREADS 22563d1a8abSmrg void _M_destroy()22663d1a8abSmrg __pool<true>::_M_destroy() throw() 22763d1a8abSmrg { 22863d1a8abSmrg if (_M_init && !_M_options._M_force_new) 22963d1a8abSmrg { 23063d1a8abSmrg if (__gthread_active_p()) 23163d1a8abSmrg { 23263d1a8abSmrg for (size_t __n = 0; __n < _M_bin_size; ++__n) 23363d1a8abSmrg { 23463d1a8abSmrg _Bin_record& __bin = _M_bin[__n]; 23563d1a8abSmrg while (__bin._M_address) 23663d1a8abSmrg { 23763d1a8abSmrg _Block_address* __tmp = __bin._M_address->_M_next; 23863d1a8abSmrg ::operator delete(__bin._M_address->_M_initial); 23963d1a8abSmrg __bin._M_address = __tmp; 24063d1a8abSmrg } 24163d1a8abSmrg ::operator delete(__bin._M_first); 24263d1a8abSmrg ::operator delete(__bin._M_free); 24363d1a8abSmrg ::operator delete(__bin._M_used); 24463d1a8abSmrg ::operator delete(__bin._M_mutex); 24563d1a8abSmrg } 24663d1a8abSmrg } 24763d1a8abSmrg else 24863d1a8abSmrg { 24963d1a8abSmrg for (size_t __n = 0; __n < _M_bin_size; ++__n) 25063d1a8abSmrg { 25163d1a8abSmrg _Bin_record& __bin = _M_bin[__n]; 25263d1a8abSmrg while (__bin._M_address) 25363d1a8abSmrg { 25463d1a8abSmrg _Block_address* __tmp = __bin._M_address->_M_next; 25563d1a8abSmrg ::operator delete(__bin._M_address->_M_initial); 25663d1a8abSmrg __bin._M_address = __tmp; 25763d1a8abSmrg } 25863d1a8abSmrg ::operator delete(__bin._M_first); 25963d1a8abSmrg } 26063d1a8abSmrg } 26163d1a8abSmrg ::operator delete(_M_bin); 26263d1a8abSmrg ::operator delete(_M_binmap); 26363d1a8abSmrg } 26463d1a8abSmrg } 26563d1a8abSmrg 26663d1a8abSmrg void _M_reclaim_block(char * __p,size_t __bytes)26763d1a8abSmrg __pool<true>::_M_reclaim_block(char* __p, size_t __bytes) throw () 26863d1a8abSmrg { 26963d1a8abSmrg // Round up to power of 2 and figure out which bin to use. 27063d1a8abSmrg const size_t __which = _M_binmap[__bytes]; 27163d1a8abSmrg const _Bin_record& __bin = _M_bin[__which]; 27263d1a8abSmrg 27363d1a8abSmrg // Know __p not null, assume valid block. 27463d1a8abSmrg char* __c = __p - _M_get_align(); 27563d1a8abSmrg _Block_record* __block = reinterpret_cast<_Block_record*>(__c); 27663d1a8abSmrg if (__gthread_active_p()) 27763d1a8abSmrg { 27863d1a8abSmrg // Calculate the number of records to remove from our freelist: 27963d1a8abSmrg // in order to avoid too much contention we wait until the 28063d1a8abSmrg // number of records is "high enough". 28163d1a8abSmrg const size_t __thread_id = _M_get_thread_id(); 28263d1a8abSmrg const _Tune& __options = _M_get_options(); 28363d1a8abSmrg const size_t __limit = (100 * (_M_bin_size - __which) 28463d1a8abSmrg * __options._M_freelist_headroom); 28563d1a8abSmrg 28663d1a8abSmrg size_t __remove = __bin._M_free[__thread_id]; 28763d1a8abSmrg __remove *= __options._M_freelist_headroom; 28863d1a8abSmrg 28963d1a8abSmrg // NB: We assume that reads of _Atomic_words are atomic. 29063d1a8abSmrg const size_t __max_threads = __options._M_max_threads + 1; 29163d1a8abSmrg _Atomic_word* const __reclaimed_base = 29263d1a8abSmrg reinterpret_cast<_Atomic_word*>(__bin._M_used + __max_threads); 29363d1a8abSmrg const _Atomic_word __reclaimed = __reclaimed_base[__thread_id]; 29463d1a8abSmrg const size_t __net_used = __bin._M_used[__thread_id] - __reclaimed; 29563d1a8abSmrg 29663d1a8abSmrg // NB: For performance sake we don't resync every time, in order 29763d1a8abSmrg // to spare atomic ops. Note that if __reclaimed increased by, 29863d1a8abSmrg // say, 1024, since the last sync, it means that the other 29963d1a8abSmrg // threads executed the atomic in the else below at least the 30063d1a8abSmrg // same number of times (at least, because _M_reserve_block may 30163d1a8abSmrg // have decreased the counter), therefore one more cannot hurt. 30263d1a8abSmrg if (__reclaimed > 1024) 30363d1a8abSmrg { 30463d1a8abSmrg __bin._M_used[__thread_id] -= __reclaimed; 30563d1a8abSmrg __atomic_add(&__reclaimed_base[__thread_id], -__reclaimed); 30663d1a8abSmrg } 30763d1a8abSmrg 30863d1a8abSmrg if (__remove >= __net_used) 30963d1a8abSmrg __remove -= __net_used; 31063d1a8abSmrg else 31163d1a8abSmrg __remove = 0; 31263d1a8abSmrg if (__remove > __limit && __remove > __bin._M_free[__thread_id]) 31363d1a8abSmrg { 31463d1a8abSmrg _Block_record* __first = __bin._M_first[__thread_id]; 31563d1a8abSmrg _Block_record* __tmp = __first; 31663d1a8abSmrg __remove /= __options._M_freelist_headroom; 31763d1a8abSmrg const size_t __removed = __remove; 31863d1a8abSmrg while (--__remove > 0) 31963d1a8abSmrg __tmp = __tmp->_M_next; 32063d1a8abSmrg __bin._M_first[__thread_id] = __tmp->_M_next; 32163d1a8abSmrg __bin._M_free[__thread_id] -= __removed; 32263d1a8abSmrg 32363d1a8abSmrg __gthread_mutex_lock(__bin._M_mutex); 32463d1a8abSmrg __tmp->_M_next = __bin._M_first[0]; 32563d1a8abSmrg __bin._M_first[0] = __first; 32663d1a8abSmrg __bin._M_free[0] += __removed; 32763d1a8abSmrg __gthread_mutex_unlock(__bin._M_mutex); 32863d1a8abSmrg } 32963d1a8abSmrg 33063d1a8abSmrg // Return this block to our list and update counters and 33163d1a8abSmrg // owner id as needed. 33263d1a8abSmrg if (__block->_M_thread_id == __thread_id) 33363d1a8abSmrg --__bin._M_used[__thread_id]; 33463d1a8abSmrg else 33563d1a8abSmrg __atomic_add(&__reclaimed_base[__block->_M_thread_id], 1); 33663d1a8abSmrg 33763d1a8abSmrg __block->_M_next = __bin._M_first[__thread_id]; 33863d1a8abSmrg __bin._M_first[__thread_id] = __block; 33963d1a8abSmrg 34063d1a8abSmrg ++__bin._M_free[__thread_id]; 34163d1a8abSmrg } 34263d1a8abSmrg else 34363d1a8abSmrg { 34463d1a8abSmrg // Not using threads, so single threaded application - return 34563d1a8abSmrg // to global pool. 34663d1a8abSmrg __block->_M_next = __bin._M_first[0]; 34763d1a8abSmrg __bin._M_first[0] = __block; 34863d1a8abSmrg } 34963d1a8abSmrg } 35063d1a8abSmrg 35163d1a8abSmrg char* _M_reserve_block(size_t __bytes,const size_t __thread_id)35263d1a8abSmrg __pool<true>::_M_reserve_block(size_t __bytes, const size_t __thread_id) 35363d1a8abSmrg { 35463d1a8abSmrg // Round up to power of 2 and figure out which bin to use. 35563d1a8abSmrg const size_t __which = _M_binmap[__bytes]; 35663d1a8abSmrg const _Tune& __options = _M_get_options(); 35763d1a8abSmrg const size_t __bin_size = ((__options._M_min_bin << __which) 35863d1a8abSmrg + __options._M_align); 35963d1a8abSmrg size_t __block_count = __options._M_chunk_size - sizeof(_Block_address); 36063d1a8abSmrg __block_count /= __bin_size; 36163d1a8abSmrg 36263d1a8abSmrg // Are we using threads? 36363d1a8abSmrg // - Yes, check if there are free blocks on the global 36463d1a8abSmrg // list. If so, grab up to __block_count blocks in one 36563d1a8abSmrg // lock and change ownership. If the global list is 36663d1a8abSmrg // empty, we allocate a new chunk and add those blocks 36763d1a8abSmrg // directly to our own freelist (with us as owner). 36863d1a8abSmrg // - No, all operations are made directly to global pool 0 36963d1a8abSmrg // no need to lock or change ownership but check for free 37063d1a8abSmrg // blocks on global list (and if not add new ones) and 37163d1a8abSmrg // get the first one. 37263d1a8abSmrg _Bin_record& __bin = _M_bin[__which]; 37363d1a8abSmrg _Block_record* __block = 0; 37463d1a8abSmrg if (__gthread_active_p()) 37563d1a8abSmrg { 37663d1a8abSmrg // Resync the _M_used counters. 37763d1a8abSmrg const size_t __max_threads = __options._M_max_threads + 1; 37863d1a8abSmrg _Atomic_word* const __reclaimed_base = 37963d1a8abSmrg reinterpret_cast<_Atomic_word*>(__bin._M_used + __max_threads); 38063d1a8abSmrg const _Atomic_word __reclaimed = __reclaimed_base[__thread_id]; 38163d1a8abSmrg __bin._M_used[__thread_id] -= __reclaimed; 38263d1a8abSmrg __atomic_add(&__reclaimed_base[__thread_id], -__reclaimed); 38363d1a8abSmrg 38463d1a8abSmrg __gthread_mutex_lock(__bin._M_mutex); 38563d1a8abSmrg if (__bin._M_first[0] == 0) 38663d1a8abSmrg { 38763d1a8abSmrg void* __v = ::operator new(__options._M_chunk_size); 38863d1a8abSmrg _Block_address* __address = static_cast<_Block_address*>(__v); 38963d1a8abSmrg __address->_M_initial = __v; 39063d1a8abSmrg __address->_M_next = __bin._M_address; 39163d1a8abSmrg __bin._M_address = __address; 39263d1a8abSmrg __gthread_mutex_unlock(__bin._M_mutex); 39363d1a8abSmrg 39463d1a8abSmrg // No need to hold the lock when we are adding a whole 39563d1a8abSmrg // chunk to our own list. 39663d1a8abSmrg char* __c = static_cast<char*>(__v) + sizeof(_Block_address); 39763d1a8abSmrg __block = reinterpret_cast<_Block_record*>(__c); 39863d1a8abSmrg __bin._M_free[__thread_id] = __block_count; 39963d1a8abSmrg __bin._M_first[__thread_id] = __block; 40063d1a8abSmrg while (--__block_count > 0) 40163d1a8abSmrg { 40263d1a8abSmrg __c += __bin_size; 40363d1a8abSmrg __block->_M_next = reinterpret_cast<_Block_record*>(__c); 40463d1a8abSmrg __block = __block->_M_next; 40563d1a8abSmrg } 40663d1a8abSmrg __block->_M_next = 0; 40763d1a8abSmrg } 40863d1a8abSmrg else 40963d1a8abSmrg { 41063d1a8abSmrg // Is the number of required blocks greater than or equal 41163d1a8abSmrg // to the number that can be provided by the global free 41263d1a8abSmrg // list? 41363d1a8abSmrg __bin._M_first[__thread_id] = __bin._M_first[0]; 41463d1a8abSmrg if (__block_count >= __bin._M_free[0]) 41563d1a8abSmrg { 41663d1a8abSmrg __bin._M_free[__thread_id] = __bin._M_free[0]; 41763d1a8abSmrg __bin._M_free[0] = 0; 41863d1a8abSmrg __bin._M_first[0] = 0; 41963d1a8abSmrg } 42063d1a8abSmrg else 42163d1a8abSmrg { 42263d1a8abSmrg __bin._M_free[__thread_id] = __block_count; 42363d1a8abSmrg __bin._M_free[0] -= __block_count; 42463d1a8abSmrg __block = __bin._M_first[0]; 42563d1a8abSmrg while (--__block_count > 0) 42663d1a8abSmrg __block = __block->_M_next; 42763d1a8abSmrg __bin._M_first[0] = __block->_M_next; 42863d1a8abSmrg __block->_M_next = 0; 42963d1a8abSmrg } 43063d1a8abSmrg __gthread_mutex_unlock(__bin._M_mutex); 43163d1a8abSmrg } 43263d1a8abSmrg } 43363d1a8abSmrg else 43463d1a8abSmrg { 43563d1a8abSmrg void* __v = ::operator new(__options._M_chunk_size); 43663d1a8abSmrg _Block_address* __address = static_cast<_Block_address*>(__v); 43763d1a8abSmrg __address->_M_initial = __v; 43863d1a8abSmrg __address->_M_next = __bin._M_address; 43963d1a8abSmrg __bin._M_address = __address; 44063d1a8abSmrg 44163d1a8abSmrg char* __c = static_cast<char*>(__v) + sizeof(_Block_address); 44263d1a8abSmrg __block = reinterpret_cast<_Block_record*>(__c); 44363d1a8abSmrg __bin._M_first[0] = __block; 44463d1a8abSmrg while (--__block_count > 0) 44563d1a8abSmrg { 44663d1a8abSmrg __c += __bin_size; 44763d1a8abSmrg __block->_M_next = reinterpret_cast<_Block_record*>(__c); 44863d1a8abSmrg __block = __block->_M_next; 44963d1a8abSmrg } 45063d1a8abSmrg __block->_M_next = 0; 45163d1a8abSmrg } 45263d1a8abSmrg 45363d1a8abSmrg __block = __bin._M_first[__thread_id]; 45463d1a8abSmrg __bin._M_first[__thread_id] = __block->_M_next; 45563d1a8abSmrg 45663d1a8abSmrg if (__gthread_active_p()) 45763d1a8abSmrg { 45863d1a8abSmrg __block->_M_thread_id = __thread_id; 45963d1a8abSmrg --__bin._M_free[__thread_id]; 46063d1a8abSmrg ++__bin._M_used[__thread_id]; 46163d1a8abSmrg } 46263d1a8abSmrg 46363d1a8abSmrg // NB: For alignment reasons, we can't use the first _M_align 46463d1a8abSmrg // bytes, even when sizeof(_Block_record) < _M_align. 46563d1a8abSmrg return reinterpret_cast<char*>(__block) + __options._M_align; 46663d1a8abSmrg } 46763d1a8abSmrg 46863d1a8abSmrg void _M_initialize()46963d1a8abSmrg __pool<true>::_M_initialize() 47063d1a8abSmrg { 47163d1a8abSmrg // _M_force_new must not change after the first allocate(), 47263d1a8abSmrg // which in turn calls this method, so if it's false, it's false 47363d1a8abSmrg // forever and we don't need to return here ever again. 47463d1a8abSmrg if (_M_options._M_force_new) 47563d1a8abSmrg { 47663d1a8abSmrg _M_init = true; 47763d1a8abSmrg return; 47863d1a8abSmrg } 47963d1a8abSmrg 48063d1a8abSmrg // Create the bins. 48163d1a8abSmrg // Calculate the number of bins required based on _M_max_bytes. 48263d1a8abSmrg // _M_bin_size is statically-initialized to one. 48363d1a8abSmrg size_t __bin_size = _M_options._M_min_bin; 48463d1a8abSmrg while (_M_options._M_max_bytes > __bin_size) 48563d1a8abSmrg { 48663d1a8abSmrg __bin_size <<= 1; 48763d1a8abSmrg ++_M_bin_size; 48863d1a8abSmrg } 48963d1a8abSmrg 49063d1a8abSmrg // Setup the bin map for quick lookup of the relevant bin. 49163d1a8abSmrg const size_t __j = (_M_options._M_max_bytes + 1) * sizeof(_Binmap_type); 49263d1a8abSmrg _M_binmap = static_cast<_Binmap_type*>(::operator new(__j)); 49363d1a8abSmrg _Binmap_type* __bp = _M_binmap; 49463d1a8abSmrg _Binmap_type __bin_max = _M_options._M_min_bin; 49563d1a8abSmrg _Binmap_type __bint = 0; 49663d1a8abSmrg for (_Binmap_type __ct = 0; __ct <= _M_options._M_max_bytes; ++__ct) 49763d1a8abSmrg { 49863d1a8abSmrg if (__ct > __bin_max) 49963d1a8abSmrg { 50063d1a8abSmrg __bin_max <<= 1; 50163d1a8abSmrg ++__bint; 50263d1a8abSmrg } 50363d1a8abSmrg *__bp++ = __bint; 50463d1a8abSmrg } 50563d1a8abSmrg 50663d1a8abSmrg // Initialize _M_bin and its members. 50763d1a8abSmrg void* __v = ::operator new(sizeof(_Bin_record) * _M_bin_size); 50863d1a8abSmrg _M_bin = static_cast<_Bin_record*>(__v); 50963d1a8abSmrg 51063d1a8abSmrg // If __gthread_active_p() create and initialize the list of 51163d1a8abSmrg // free thread ids. Single threaded applications use thread id 0 51263d1a8abSmrg // directly and have no need for this. 51363d1a8abSmrg if (__gthread_active_p()) 51463d1a8abSmrg { 51563d1a8abSmrg __freelist& freelist = get_freelist(); 51663d1a8abSmrg { 51763d1a8abSmrg __gnu_cxx::__scoped_lock sentry(get_freelist_mutex()); 51863d1a8abSmrg 51963d1a8abSmrg if (!freelist._M_thread_freelist_array 52063d1a8abSmrg || freelist._M_max_threads < _M_options._M_max_threads) 52163d1a8abSmrg { 52263d1a8abSmrg const size_t __k = sizeof(_Thread_record) 52363d1a8abSmrg * _M_options._M_max_threads; 52463d1a8abSmrg __v = ::operator new(__k); 52563d1a8abSmrg _M_thread_freelist = static_cast<_Thread_record*>(__v); 52663d1a8abSmrg 52763d1a8abSmrg // NOTE! The first assignable thread id is 1 since the 52863d1a8abSmrg // global pool uses id 0 52963d1a8abSmrg size_t __i; 53063d1a8abSmrg for (__i = 1; __i < _M_options._M_max_threads; ++__i) 53163d1a8abSmrg { 53263d1a8abSmrg _Thread_record& __tr = _M_thread_freelist[__i - 1]; 53363d1a8abSmrg __tr._M_next = &_M_thread_freelist[__i]; 53463d1a8abSmrg __tr._M_id = __i; 53563d1a8abSmrg } 53663d1a8abSmrg 53763d1a8abSmrg // Set last record. 53863d1a8abSmrg _M_thread_freelist[__i - 1]._M_next = 0; 53963d1a8abSmrg _M_thread_freelist[__i - 1]._M_id = __i; 54063d1a8abSmrg 54163d1a8abSmrg if (!freelist._M_thread_freelist_array) 54263d1a8abSmrg { 54363d1a8abSmrg // Initialize per thread key to hold pointer to 54463d1a8abSmrg // _M_thread_freelist. 54563d1a8abSmrg __gthread_key_create(&freelist._M_key, 54663d1a8abSmrg ::_M_destroy_thread_key); 54763d1a8abSmrg freelist._M_thread_freelist = _M_thread_freelist; 54863d1a8abSmrg } 54963d1a8abSmrg else 55063d1a8abSmrg { 55163d1a8abSmrg _Thread_record* _M_old_freelist 55263d1a8abSmrg = freelist._M_thread_freelist; 55363d1a8abSmrg _Thread_record* _M_old_array 55463d1a8abSmrg = freelist._M_thread_freelist_array; 55563d1a8abSmrg freelist._M_thread_freelist 55663d1a8abSmrg = &_M_thread_freelist[_M_old_freelist - _M_old_array]; 55763d1a8abSmrg while (_M_old_freelist) 55863d1a8abSmrg { 55963d1a8abSmrg size_t next_id; 56063d1a8abSmrg if (_M_old_freelist->_M_next) 56163d1a8abSmrg next_id = _M_old_freelist->_M_next - _M_old_array; 56263d1a8abSmrg else 56363d1a8abSmrg next_id = freelist._M_max_threads; 56463d1a8abSmrg _M_thread_freelist[_M_old_freelist->_M_id - 1]._M_next 56563d1a8abSmrg = &_M_thread_freelist[next_id]; 56663d1a8abSmrg _M_old_freelist = _M_old_freelist->_M_next; 56763d1a8abSmrg } 56863d1a8abSmrg ::operator delete(static_cast<void*>(_M_old_array)); 56963d1a8abSmrg } 57063d1a8abSmrg freelist._M_thread_freelist_array = _M_thread_freelist; 57163d1a8abSmrg freelist._M_max_threads = _M_options._M_max_threads; 57263d1a8abSmrg } 57363d1a8abSmrg } 57463d1a8abSmrg 57563d1a8abSmrg const size_t __max_threads = _M_options._M_max_threads + 1; 57663d1a8abSmrg for (size_t __n = 0; __n < _M_bin_size; ++__n) 57763d1a8abSmrg { 57863d1a8abSmrg _Bin_record& __bin = _M_bin[__n]; 57963d1a8abSmrg __v = ::operator new(sizeof(_Block_record*) * __max_threads); 58063d1a8abSmrg std::memset(__v, 0, sizeof(_Block_record*) * __max_threads); 58163d1a8abSmrg __bin._M_first = static_cast<_Block_record**>(__v); 58263d1a8abSmrg 58363d1a8abSmrg __bin._M_address = 0; 58463d1a8abSmrg 58563d1a8abSmrg __v = ::operator new(sizeof(size_t) * __max_threads); 58663d1a8abSmrg std::memset(__v, 0, sizeof(size_t) * __max_threads); 58763d1a8abSmrg 58863d1a8abSmrg __bin._M_free = static_cast<size_t*>(__v); 58963d1a8abSmrg 59063d1a8abSmrg __v = ::operator new(sizeof(size_t) * __max_threads 59163d1a8abSmrg + sizeof(_Atomic_word) * __max_threads); 59263d1a8abSmrg std::memset(__v, 0, (sizeof(size_t) * __max_threads 59363d1a8abSmrg + sizeof(_Atomic_word) * __max_threads)); 59463d1a8abSmrg __bin._M_used = static_cast<size_t*>(__v); 59563d1a8abSmrg 59663d1a8abSmrg __v = ::operator new(sizeof(__gthread_mutex_t)); 59763d1a8abSmrg __bin._M_mutex = static_cast<__gthread_mutex_t*>(__v); 59863d1a8abSmrg 59963d1a8abSmrg #ifdef __GTHREAD_MUTEX_INIT 60063d1a8abSmrg { 60163d1a8abSmrg // Do not copy a POSIX/gthr mutex once in use. 60263d1a8abSmrg __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT; 60363d1a8abSmrg *__bin._M_mutex = __tmp; 60463d1a8abSmrg } 60563d1a8abSmrg #else 60663d1a8abSmrg { __GTHREAD_MUTEX_INIT_FUNCTION(__bin._M_mutex); } 60763d1a8abSmrg #endif 60863d1a8abSmrg } 60963d1a8abSmrg } 61063d1a8abSmrg else 61163d1a8abSmrg { 61263d1a8abSmrg for (size_t __n = 0; __n < _M_bin_size; ++__n) 61363d1a8abSmrg { 61463d1a8abSmrg _Bin_record& __bin = _M_bin[__n]; 61563d1a8abSmrg __v = ::operator new(sizeof(_Block_record*)); 61663d1a8abSmrg __bin._M_first = static_cast<_Block_record**>(__v); 61763d1a8abSmrg __bin._M_first[0] = 0; 61863d1a8abSmrg __bin._M_address = 0; 61963d1a8abSmrg } 62063d1a8abSmrg } 62163d1a8abSmrg _M_init = true; 62263d1a8abSmrg } 62363d1a8abSmrg 62463d1a8abSmrg size_t _M_get_thread_id()62563d1a8abSmrg __pool<true>::_M_get_thread_id() 62663d1a8abSmrg { 62763d1a8abSmrg // If we have thread support and it's active we check the thread 62863d1a8abSmrg // key value and return its id or if it's not set we take the 62963d1a8abSmrg // first record from _M_thread_freelist and sets the key and 63063d1a8abSmrg // returns its id. 63163d1a8abSmrg if (__gthread_active_p()) 63263d1a8abSmrg { 63363d1a8abSmrg __freelist& freelist = get_freelist(); 63463d1a8abSmrg void* v = __gthread_getspecific(freelist._M_key); 63563d1a8abSmrg uintptr_t _M_id = (uintptr_t)v; 63663d1a8abSmrg if (_M_id == 0) 63763d1a8abSmrg { 63863d1a8abSmrg { 63963d1a8abSmrg __gnu_cxx::__scoped_lock sentry(get_freelist_mutex()); 64063d1a8abSmrg if (freelist._M_thread_freelist) 64163d1a8abSmrg { 64263d1a8abSmrg _M_id = freelist._M_thread_freelist->_M_id; 64363d1a8abSmrg freelist._M_thread_freelist 64463d1a8abSmrg = freelist._M_thread_freelist->_M_next; 64563d1a8abSmrg } 64663d1a8abSmrg } 64763d1a8abSmrg 64863d1a8abSmrg __gthread_setspecific(freelist._M_key, (void*)_M_id); 64963d1a8abSmrg } 65063d1a8abSmrg return _M_id >= _M_options._M_max_threads ? 0 : _M_id; 65163d1a8abSmrg } 65263d1a8abSmrg 65363d1a8abSmrg // Otherwise (no thread support or inactive) all requests are 65463d1a8abSmrg // served from the global pool 0. 65563d1a8abSmrg return 0; 65663d1a8abSmrg } 65763d1a8abSmrg 65863d1a8abSmrg // XXX GLIBCXX_ABI Deprecated 65963d1a8abSmrg void _M_destroy_thread_key(void *)66063d1a8abSmrg __pool<true>::_M_destroy_thread_key(void*) throw () { } 66163d1a8abSmrg 66263d1a8abSmrg // XXX GLIBCXX_ABI Deprecated 66363d1a8abSmrg void _M_initialize(__destroy_handler)66463d1a8abSmrg __pool<true>::_M_initialize(__destroy_handler) 66563d1a8abSmrg { 66663d1a8abSmrg // _M_force_new must not change after the first allocate(), 66763d1a8abSmrg // which in turn calls this method, so if it's false, it's false 66863d1a8abSmrg // forever and we don't need to return here ever again. 66963d1a8abSmrg if (_M_options._M_force_new) 67063d1a8abSmrg { 67163d1a8abSmrg _M_init = true; 67263d1a8abSmrg return; 67363d1a8abSmrg } 67463d1a8abSmrg 67563d1a8abSmrg // Create the bins. 67663d1a8abSmrg // Calculate the number of bins required based on _M_max_bytes. 67763d1a8abSmrg // _M_bin_size is statically-initialized to one. 67863d1a8abSmrg size_t __bin_size = _M_options._M_min_bin; 67963d1a8abSmrg while (_M_options._M_max_bytes > __bin_size) 68063d1a8abSmrg { 68163d1a8abSmrg __bin_size <<= 1; 68263d1a8abSmrg ++_M_bin_size; 68363d1a8abSmrg } 68463d1a8abSmrg 68563d1a8abSmrg // Setup the bin map for quick lookup of the relevant bin. 68663d1a8abSmrg const size_t __j = (_M_options._M_max_bytes + 1) * sizeof(_Binmap_type); 68763d1a8abSmrg _M_binmap = static_cast<_Binmap_type*>(::operator new(__j)); 68863d1a8abSmrg _Binmap_type* __bp = _M_binmap; 68963d1a8abSmrg _Binmap_type __bin_max = _M_options._M_min_bin; 69063d1a8abSmrg _Binmap_type __bint = 0; 69163d1a8abSmrg for (_Binmap_type __ct = 0; __ct <= _M_options._M_max_bytes; ++__ct) 69263d1a8abSmrg { 69363d1a8abSmrg if (__ct > __bin_max) 69463d1a8abSmrg { 69563d1a8abSmrg __bin_max <<= 1; 69663d1a8abSmrg ++__bint; 69763d1a8abSmrg } 69863d1a8abSmrg *__bp++ = __bint; 69963d1a8abSmrg } 70063d1a8abSmrg 70163d1a8abSmrg // Initialize _M_bin and its members. 70263d1a8abSmrg void* __v = ::operator new(sizeof(_Bin_record) * _M_bin_size); 70363d1a8abSmrg _M_bin = static_cast<_Bin_record*>(__v); 70463d1a8abSmrg 70563d1a8abSmrg // If __gthread_active_p() create and initialize the list of 70663d1a8abSmrg // free thread ids. Single threaded applications use thread id 0 70763d1a8abSmrg // directly and have no need for this. 70863d1a8abSmrg if (__gthread_active_p()) 70963d1a8abSmrg { 71063d1a8abSmrg __freelist& freelist = get_freelist(); 71163d1a8abSmrg { 71263d1a8abSmrg __gnu_cxx::__scoped_lock sentry(get_freelist_mutex()); 71363d1a8abSmrg 71463d1a8abSmrg if (!freelist._M_thread_freelist_array 71563d1a8abSmrg || freelist._M_max_threads < _M_options._M_max_threads) 71663d1a8abSmrg { 71763d1a8abSmrg const size_t __k = sizeof(_Thread_record) 71863d1a8abSmrg * _M_options._M_max_threads; 71963d1a8abSmrg __v = ::operator new(__k); 72063d1a8abSmrg _M_thread_freelist = static_cast<_Thread_record*>(__v); 72163d1a8abSmrg 72263d1a8abSmrg // NOTE! The first assignable thread id is 1 since the 72363d1a8abSmrg // global pool uses id 0 72463d1a8abSmrg size_t __i; 72563d1a8abSmrg for (__i = 1; __i < _M_options._M_max_threads; ++__i) 72663d1a8abSmrg { 72763d1a8abSmrg _Thread_record& __tr = _M_thread_freelist[__i - 1]; 72863d1a8abSmrg __tr._M_next = &_M_thread_freelist[__i]; 72963d1a8abSmrg __tr._M_id = __i; 73063d1a8abSmrg } 73163d1a8abSmrg 73263d1a8abSmrg // Set last record. 73363d1a8abSmrg _M_thread_freelist[__i - 1]._M_next = 0; 73463d1a8abSmrg _M_thread_freelist[__i - 1]._M_id = __i; 73563d1a8abSmrg 73663d1a8abSmrg if (!freelist._M_thread_freelist_array) 73763d1a8abSmrg { 73863d1a8abSmrg // Initialize per thread key to hold pointer to 73963d1a8abSmrg // _M_thread_freelist. 74063d1a8abSmrg __gthread_key_create(&freelist._M_key, 74163d1a8abSmrg ::_M_destroy_thread_key); 74263d1a8abSmrg freelist._M_thread_freelist = _M_thread_freelist; 74363d1a8abSmrg } 74463d1a8abSmrg else 74563d1a8abSmrg { 74663d1a8abSmrg _Thread_record* _M_old_freelist 74763d1a8abSmrg = freelist._M_thread_freelist; 74863d1a8abSmrg _Thread_record* _M_old_array 74963d1a8abSmrg = freelist._M_thread_freelist_array; 75063d1a8abSmrg freelist._M_thread_freelist 75163d1a8abSmrg = &_M_thread_freelist[_M_old_freelist - _M_old_array]; 75263d1a8abSmrg while (_M_old_freelist) 75363d1a8abSmrg { 75463d1a8abSmrg size_t next_id; 75563d1a8abSmrg if (_M_old_freelist->_M_next) 75663d1a8abSmrg next_id = _M_old_freelist->_M_next - _M_old_array; 75763d1a8abSmrg else 75863d1a8abSmrg next_id = freelist._M_max_threads; 75963d1a8abSmrg _M_thread_freelist[_M_old_freelist->_M_id - 1]._M_next 76063d1a8abSmrg = &_M_thread_freelist[next_id]; 76163d1a8abSmrg _M_old_freelist = _M_old_freelist->_M_next; 76263d1a8abSmrg } 76363d1a8abSmrg ::operator delete(static_cast<void*>(_M_old_array)); 76463d1a8abSmrg } 76563d1a8abSmrg freelist._M_thread_freelist_array = _M_thread_freelist; 76663d1a8abSmrg freelist._M_max_threads = _M_options._M_max_threads; 76763d1a8abSmrg } 76863d1a8abSmrg } 76963d1a8abSmrg 77063d1a8abSmrg const size_t __max_threads = _M_options._M_max_threads + 1; 77163d1a8abSmrg for (size_t __n = 0; __n < _M_bin_size; ++__n) 77263d1a8abSmrg { 77363d1a8abSmrg _Bin_record& __bin = _M_bin[__n]; 77463d1a8abSmrg __v = ::operator new(sizeof(_Block_record*) * __max_threads); 77563d1a8abSmrg std::memset(__v, 0, sizeof(_Block_record*) * __max_threads); 77663d1a8abSmrg __bin._M_first = static_cast<_Block_record**>(__v); 77763d1a8abSmrg 77863d1a8abSmrg __bin._M_address = 0; 77963d1a8abSmrg 78063d1a8abSmrg __v = ::operator new(sizeof(size_t) * __max_threads); 78163d1a8abSmrg std::memset(__v, 0, sizeof(size_t) * __max_threads); 78263d1a8abSmrg __bin._M_free = static_cast<size_t*>(__v); 78363d1a8abSmrg 78463d1a8abSmrg __v = ::operator new(sizeof(size_t) * __max_threads + 78563d1a8abSmrg sizeof(_Atomic_word) * __max_threads); 78663d1a8abSmrg std::memset(__v, 0, (sizeof(size_t) * __max_threads 78763d1a8abSmrg + sizeof(_Atomic_word) * __max_threads)); 78863d1a8abSmrg __bin._M_used = static_cast<size_t*>(__v); 78963d1a8abSmrg 79063d1a8abSmrg __v = ::operator new(sizeof(__gthread_mutex_t)); 79163d1a8abSmrg __bin._M_mutex = static_cast<__gthread_mutex_t*>(__v); 79263d1a8abSmrg 79363d1a8abSmrg #ifdef __GTHREAD_MUTEX_INIT 79463d1a8abSmrg { 79563d1a8abSmrg // Do not copy a POSIX/gthr mutex once in use. 79663d1a8abSmrg __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT; 79763d1a8abSmrg *__bin._M_mutex = __tmp; 79863d1a8abSmrg } 79963d1a8abSmrg #else 80063d1a8abSmrg { __GTHREAD_MUTEX_INIT_FUNCTION(__bin._M_mutex); } 80163d1a8abSmrg #endif 80263d1a8abSmrg } 80363d1a8abSmrg } 80463d1a8abSmrg else 80563d1a8abSmrg { 80663d1a8abSmrg for (size_t __n = 0; __n < _M_bin_size; ++__n) 80763d1a8abSmrg { 80863d1a8abSmrg _Bin_record& __bin = _M_bin[__n]; 80963d1a8abSmrg __v = ::operator new(sizeof(_Block_record*)); 81063d1a8abSmrg __bin._M_first = static_cast<_Block_record**>(__v); 81163d1a8abSmrg __bin._M_first[0] = 0; 81263d1a8abSmrg __bin._M_address = 0; 81363d1a8abSmrg } 81463d1a8abSmrg } 81563d1a8abSmrg _M_init = true; 81663d1a8abSmrg } 81763d1a8abSmrg #endif 81863d1a8abSmrg 81963d1a8abSmrg // Instantiations. 82063d1a8abSmrg template class __mt_alloc<char>; 82163d1a8abSmrg template class __mt_alloc<wchar_t>; 82263d1a8abSmrg 82363d1a8abSmrg _GLIBCXX_END_NAMESPACE_VERSION 82463d1a8abSmrg } // namespace 825