/*
*
* Copyright (c) 1996,1997
* Silicon Graphics Computer Systems, Inc.
*
* Copyright (c) 1997
* Moscow Center for SPARC Technology
*
* Copyright (c) 1999
* Boris Fomitchev
*
* This material is provided "as is", with absolutely no warranty expressed
* or implied. Any use is at your own risk.
*
* Permission to use or copy this software for any purpose is hereby granted
* without fee, provided the above notices are retained on all copies.
* Permission to modify the code and to distribute modified code is granted,
* provided the above notices are retained, and a notice that the code was
* modified is included with the above copyright notice.
*
*/
#include "stlport_prefix.h"
#include <memory>
#if defined (__GNUC__) && (defined (__CYGWIN__) || defined (__MINGW32__))
# include <malloc.h>
#endif
#if defined (_STLP_PTHREADS) && !defined (_STLP_NO_THREADS)
# include <pthread_alloc>
# include <cerrno>
#endif
#include <stl/_threads.h>
#include "lock_free_slist.h"
#if defined (__WATCOMC__)
# pragma warning 13 9
# pragma warning 367 9
# pragma warning 368 9
#endif
#if defined (_STLP_SGI_THREADS)
// We test whether threads are in use before locking.
// Perhaps this should be moved into stl_threads.h, but that
// probably makes it harder to avoid the procedure call when
// it isn't needed.
extern "C" {
extern int __us_rsthread_malloc;
}
#endif
// Specialised debug form of new operator which does not provide "false"
// memory leaks when run with debug CRT libraries.
#if defined (_STLP_MSVC) && (_STLP_MSVC >= 1020 && defined (_STLP_DEBUG_ALLOC)) && !defined (_STLP_WCE)
# include <crtdbg.h>
inline char* __stlp_new_chunk(size_t __bytes) {
void *__chunk = _STLP_CHECK_NULL_ALLOC(::operator new(__bytes, __FILE__, __LINE__));
return __STATIC_CAST(char*, __chunk);
}
inline void __stlp_delete_chunck(void* __p) { ::operator delete(__p, __FILE__, __LINE__); }
#else
# ifdef _STLP_NODE_ALLOC_USE_MALLOC
# include <cstdlib>
inline char* __stlp_new_chunk(size_t __bytes) {
// do not use _STLP_CHECK_NULL_ALLOC, this macro is dedicated to new operator.
void *__chunk = _STLP_VENDOR_CSTD::malloc(__bytes);
if (__chunk == 0) {
_STLP_THROW_BAD_ALLOC;
}
return __STATIC_CAST(char*, __chunk);
}
inline void __stlp_delete_chunck(void* __p) { _STLP_VENDOR_CSTD::free(__p); }
# else
inline char* __stlp_new_chunk(size_t __bytes)
{ return __STATIC_CAST(char*, _STLP_STD::__stl_new(__bytes)); }
inline void __stlp_delete_chunck(void* __p) { _STLP_STD::__stl_delete(__p); }
# endif
#endif
/* This is an additional atomic operations to the ones already defined in
* stl/_threads.h, platform should try to support it to improve performance.
* __add_atomic_t _STLP_ATOMIC_ADD(volatile __add_atomic_t* __target, __add_atomic_t __val) :
* does *__target = *__target + __val and returns the old *__target value */
typedef long __add_atomic_t;
typedef unsigned long __uadd_atomic_t;
#if defined (__GNUC__) && defined (__i386__)
inline long _STLP_atomic_add_gcc_x86(long volatile* p, long addend) {
long result;
__asm__ __volatile__
("lock; xaddl %1, %0;"
:"=m" (*p), "=r" (result)
:"m" (*p), "1" (addend)
:"cc");
return result + addend;
}
# define _STLP_ATOMIC_ADD(__dst, __val) _STLP_atomic_add_gcc_x86(__dst, __val)
#elif defined (_STLP_WIN32THREADS)
// The Win32 API function InterlockedExchangeAdd is not available on Windows 95.
# if !defined (_STLP_WIN95_LIKE)
# if defined (_STLP_NEW_PLATFORM_SDK)
# define _STLP_ATOMIC_ADD(__dst, __val) InterlockedExchangeAdd(__dst, __val)
# else
# define _STLP_ATOMIC_ADD(__dst, __val) InterlockedExchangeAdd(__CONST_CAST(__add_atomic_t*, __dst), __val)
# endif
# endif
#endif
#if defined (__OS400__)
// dums 02/05/2007: is it really necessary ?
enum { _ALIGN = 16, _ALIGN_SHIFT = 4 };
#else
enum { _ALIGN = 2 * sizeof(void*), _ALIGN_SHIFT = 2 + sizeof(void*) / 4 };
#endif
#define _S_FREELIST_INDEX(__bytes) ((__bytes - size_t(1)) >> (int)_ALIGN_SHIFT)
_STLP_BEGIN_NAMESPACE
// malloc_alloc out-of-memory handling
static __oom_handler_type __oom_handler = __STATIC_CAST(__oom_handler_type, 0);
#ifdef _STLP_THREADS
_STLP_mutex __oom_handler_lock;
#endif
void* _STLP_CALL __malloc_alloc::allocate(size_t __n)
{
void *__result = malloc(__n);
if ( 0 == __result ) {
__oom_handler_type __my_malloc_handler;
for (;;) {
{
#ifdef _STLP_THREADS
_STLP_auto_lock _l( __oom_handler_lock );
#endif
__my_malloc_handler = __oom_handler;
}
if ( 0 == __my_malloc_handler) {
_STLP_THROW_BAD_ALLOC;
}
(*__my_malloc_handler)();
__result = malloc(__n);
if ( __result )
return __result;
}
}
return __result;
}
__oom_handler_type _STLP_CALL __malloc_alloc::set_malloc_handler(__oom_handler_type __f)
{
#ifdef _STLP_THREADS
_STLP_auto_lock _l( __oom_handler_lock );
#endif
__oom_handler_type __old = __oom_handler;
__oom_handler = __f;
return __old;
}
// *******************************************************
// Default node allocator.
// With a reasonable compiler, this should be roughly as fast as the
// original STL class-specific allocators, but with less fragmentation.
//
// Important implementation properties:
// 1. If the client request an object of size > _MAX_BYTES, the resulting
// object will be obtained directly from malloc.
// 2. In all other cases, we allocate an object of size exactly
// _S_round_up(requested_size). Thus the client has enough size
// information that we can return the object to the proper free list
// without permanently losing part of the object.
//
#define _STLP_NFREELISTS 16
#if defined (_STLP_LEAKS_PEDANTIC) && defined (_STLP_USE_DYNAMIC_LIB)
/*
* We can only do cleanup of the node allocator memory pool if we are
* sure that the STLport library is used as a shared one as it guaranties
* the unicity of the node allocator instance. Without that guaranty node
* allocator instances might exchange memory blocks making the implementation
* of a cleaning process much more complicated.
*/
# define _STLP_DO_CLEAN_NODE_ALLOC
#endif
/* When STLport is used without multi threaded safety we use the node allocator
* implementation with locks as locks becomes no-op. The lock free implementation
* always use system specific atomic operations which are slower than 'normal'
* ones.
*/
#if defined (_STLP_THREADS) && \
defined (_STLP_HAS_ATOMIC_FREELIST) && defined (_STLP_ATOMIC_ADD)
/*
* We have an implementation of the atomic freelist (_STLP_atomic_freelist)
* for this architecture and compiler. That means we can use the non-blocking
* implementation of the node-allocation engine.*/
# define _STLP_USE_LOCK_FREE_IMPLEMENTATION
#endif
#if !defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)
# if defined (_STLP_THREADS)
class _Node_Alloc_Lock {
static _STLP_STATIC_MUTEX& _S_Mutex() {
static _STLP_STATIC_MUTEX mutex _STLP_MUTEX_INITIALIZER;
return mutex;
}
public:
_Node_Alloc_Lock() {
# if defined (_STLP_SGI_THREADS)
if (__us_rsthread_malloc)
# endif
_S_Mutex()._M_acquire_lock();
}
~_Node_Alloc_Lock() {
# if defined (_STLP_SGI_THREADS)
if (__us_rsthread_malloc)
# endif
_S_Mutex()._M_release_lock();
}
};
# else
class _Node_Alloc_Lock {
public:
_Node_Alloc_Lock() { }
~_Node_Alloc_Lock() { }
};
# endif
struct _Node_alloc_obj {
_Node_alloc_obj * _M_next;
};
#endif
class __node_alloc_impl {
static inline size_t _STLP_CALL _S_round_up(size_t __bytes)
{ return (((__bytes) + (size_t)_ALIGN-1) & ~((size_t)_ALIGN - 1)); }
#if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)
typedef _STLP_atomic_freelist::item _Obj;
typedef _STLP_atomic_freelist _Freelist;
typedef _STLP_atomic_freelist _ChunkList;
// Header of blocks of memory that have been allocated as part of
// a larger chunk but have not yet been chopped up into nodes.
struct _FreeBlockHeader : public _STLP_atomic_freelist::item {
char* _M_end; // pointer to end of free memory
};
#else
typedef _Node_alloc_obj _Obj;
typedef _Obj* _STLP_VOLATILE _Freelist;
typedef _Obj* _ChunkList;
#endif
private:
// Returns an object of size __n, and optionally adds to size __n free list.
static _Obj* _S_refill(size_t __n);
// Allocates a chunk for nobjs of size __p_size. nobjs may be reduced
// if it is inconvenient to allocate the requested number.
static char* _S_chunk_alloc(size_t __p_size, int& __nobjs);
// Chunk allocation state.
static _Freelist _S_free_list[_STLP_NFREELISTS];
// Amount of total allocated memory
#if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)
static _STLP_VOLATILE __add_atomic_t _S_heap_size;
#else
static size_t _S_heap_size;
#endif
#if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)
// List of blocks of free memory
static _STLP_atomic_freelist _S_free_mem_blocks;
#else
// Start of the current free memory buffer
static char* _S_start_free;
// End of the current free memory buffer
static char* _S_end_free;
#endif
#if defined (_STLP_DO_CLEAN_NODE_ALLOC)
public:
// Methods to report alloc/dealloc calls to the counter system.
# if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)
typedef _STLP_VOLATILE __stl_atomic_t _AllocCounter;
# else
typedef __stl_atomic_t _AllocCounter;
# endif
static _AllocCounter& _STLP_CALL _S_alloc_counter();
static void _S_alloc_call();
static void _S_dealloc_call();
private:
// Free all the allocated chuncks of memory
static void _S_chunk_dealloc();
// Beginning of the linked list of allocated chunks of memory
static _ChunkList _S_chunks;
#endif /* _STLP_DO_CLEAN_NODE_ALLOC */
public:
/* __n must be > 0 */
static void* _M_allocate(size_t& __n);
/* __p may not be 0 */
static void _M_deallocate(void *__p, size_t __n);
};
#if !defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)
void* __node_alloc_impl::_M_allocate(size_t& __n) {
__n = _S_round_up(__n);
_Obj * _STLP_VOLATILE * __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);
_Obj *__r;
// Acquire the lock here with a constructor call.
// This ensures that it is released in exit or during stack
// unwinding.
_Node_Alloc_Lock __lock_instance;
if ( (__r = *__my_free_list) != 0 ) {
*__my_free_list = __r->_M_next;
} else {
__r = _S_refill(__n);
}
# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
_S_alloc_call();
# endif
// lock is released here
return __r;
}
void __node_alloc_impl::_M_deallocate(void *__p, size_t __n) {
_Obj * _STLP_VOLATILE * __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);
_Obj * __pobj = __STATIC_CAST(_Obj*, __p);
// acquire lock
_Node_Alloc_Lock __lock_instance;
__pobj->_M_next = *__my_free_list;
*__my_free_list = __pobj;
# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
_S_dealloc_call();
# endif
// lock is released here
}
# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
# define _STLP_OFFSET sizeof(_Obj)
# else
# define _STLP_OFFSET 0
# endif
/* We allocate memory in large chunks in order to avoid fragmenting */
/* the malloc heap too much. */
/* We assume that size is properly aligned. */
/* We hold the allocation lock. */
char* __node_alloc_impl::_S_chunk_alloc(size_t _p_size, int& __nobjs) {
char* __result;
size_t __total_bytes = _p_size * __nobjs;
size_t __bytes_left = _S_end_free - _S_start_free;
if (__bytes_left > 0) {
if (__bytes_left >= __total_bytes) {
__result = _S_start_free;
_S_start_free += __total_bytes;
return __result;
}
if (__bytes_left >= _p_size) {
__nobjs = (int)(__bytes_left / _p_size);
__total_bytes = _p_size * __nobjs;
__result = _S_start_free;
_S_start_free += __total_bytes;
return __result;
}
// Try to make use of the left-over piece.
_Obj* _STLP_VOLATILE* __my_free_list = _S_free_list + _S_FREELIST_INDEX(__bytes_left);
__REINTERPRET_CAST(_Obj*, _S_start_free)->_M_next = *__my_free_list;
*__my_free_list = __REINTERPRET_CAST(_Obj*, _S_start_free);
_S_start_free = _S_end_free = 0;
}
size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size) + _STLP_OFFSET;
_STLP_TRY {
_S_start_free = __stlp_new_chunk(__bytes_to_get);
}
#if defined (_STLP_USE_EXCEPTIONS)
catch (const _STLP_STD::bad_alloc&) {
_Obj* _STLP_VOLATILE* __my_free_list;
_Obj* __p;
// Try to do with what we have. That can't hurt.
// We do not try smaller requests, since that tends
// to result in disaster on multi-process machines.
for (size_t __i = _p_size; __i <= (size_t)_MAX_BYTES; __i += (size_t)_ALIGN) {
__my_free_list = _S_free_list + _S_FREELIST_INDEX(__i);
__p = *__my_free_list;
if (0 != __p) {
*__my_free_list = __p -> _M_next;
_S_start_free = __REINTERPRET_CAST(char*, __p);
_S_end_free = _S_start_free + __i;
return _S_chunk_alloc(_p_size, __nobjs);
// Any leftover piece will eventually make it to the
// right free list.
}
}
__bytes_to_get = __total_bytes + _STLP_OFFSET;
_S_start_free = __stlp_new_chunk(__bytes_to_get);
}
#endif
_S_heap_size += __bytes_to_get >> 4;
# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
__REINTERPRET_CAST(_Obj*, _S_start_free)->_M_next = _S_chunks;
_S_chunks = __REINTERPRET_CAST(_Obj*, _S_start_free);
# endif
_S_end_free = _S_start_free + __bytes_to_get;
_S_start_free += _STLP_OFFSET;
return _S_chunk_alloc(_p_size, __nobjs);
}
/* Returns an object of size __n, and optionally adds to size __n free list.*/
/* We assume that __n is properly aligned. */
/* We hold the allocation lock. */
_Node_alloc_obj* __node_alloc_impl::_S_refill(size_t __n) {
int __nobjs = 20;
char* __chunk = _S_chunk_alloc(__n, __nobjs);
if (1 == __nobjs) return __REINTERPRET_CAST(_Obj*, __chunk);
_Obj* _STLP_VOLATILE* __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
/* Build free list in chunk */
__result = __REINTERPRET_CAST(_Obj*, __chunk);
*__my_free_list = __next_obj = __REINTERPRET_CAST(_Obj*, __chunk + __n);
for (--__nobjs; --__nobjs; ) {
__current_obj = __next_obj;
__next_obj = __REINTERPRET_CAST(_Obj*, __REINTERPRET_CAST(char*, __next_obj) + __n);
__current_obj->_M_next = __next_obj;
}
__next_obj->_M_next = 0;
return __result;
}
# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
void __node_alloc_impl::_S_alloc_call()
{ ++_S_alloc_counter(); }
void __node_alloc_impl::_S_dealloc_call() {
__stl_atomic_t &counter = _S_alloc_counter();
if (--counter == 0)
{ _S_chunk_dealloc(); }
}
/* We deallocate all the memory chunks */
void __node_alloc_impl::_S_chunk_dealloc() {
_Obj *__pcur = _S_chunks, *__pnext;
while (__pcur != 0) {
__pnext = __pcur->_M_next;
__stlp_delete_chunck(__pcur);
__pcur = __pnext;
}
_S_chunks = 0;
_S_start_free = _S_end_free = 0;
_S_heap_size = 0;
memset(__REINTERPRET_CAST(char*, __CONST_CAST(_Obj**, &_S_free_list[0])), 0, _STLP_NFREELISTS * sizeof(_Obj*));
}
# endif
#else
void* __node_alloc_impl::_M_allocate(size_t& __n) {
__n = _S_round_up(__n);
_Obj* __r = _S_free_list[_S_FREELIST_INDEX(__n)].pop();
if (__r == 0)
{ __r = _S_refill(__n); }
# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
_S_alloc_call();
# endif
return __r;
}
void __node_alloc_impl::_M_deallocate(void *__p, size_t __n) {
_S_free_list[_S_FREELIST_INDEX(__n)].push(__STATIC_CAST(_Obj*, __p));
# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
_S_dealloc_call();
# endif
}
/* Returns an object of size __n, and optionally adds additional ones to */
/* freelist of objects of size __n. */
/* We assume that __n is properly aligned. */
__node_alloc_impl::_Obj* __node_alloc_impl::_S_refill(size_t __n) {
int __nobjs = 20;
char* __chunk = _S_chunk_alloc(__n, __nobjs);
if (__nobjs <= 1)
return __REINTERPRET_CAST(_Obj*, __chunk);
// Push all new nodes (minus first one) onto freelist
_Obj* __result = __REINTERPRET_CAST(_Obj*, __chunk);
_Obj* __cur_item = __result;
_Freelist* __my_freelist = _S_free_list + _S_FREELIST_INDEX(__n);
for (--__nobjs; __nobjs != 0; --__nobjs) {
__cur_item = __REINTERPRET_CAST(_Obj*, __REINTERPRET_CAST(char*, __cur_item) + __n);
__my_freelist->push(__cur_item);
}
return __result;
}
# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
# define _STLP_OFFSET _ALIGN
# else
# define _STLP_OFFSET 0
# endif
/* We allocate memory in large chunks in order to avoid fragmenting */
/* the malloc heap too much. */
/* We assume that size is properly aligned. */
char* __node_alloc_impl::_S_chunk_alloc(size_t _p_size, int& __nobjs) {
# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
//We are going to add a small memory block to keep all the allocated blocks
//address, we need to do so respecting the memory alignment. The following
//static assert checks that the reserved block is big enough to store a pointer.
_STLP_STATIC_ASSERT(sizeof(_Obj) <= _ALIGN)
# endif
char* __result = 0;
__add_atomic_t __total_bytes = __STATIC_CAST(__add_atomic_t, _p_size) * __nobjs;
_FreeBlockHeader* __block = __STATIC_CAST(_FreeBlockHeader*, _S_free_mem_blocks.pop());
if (__block != 0) {
// We checked a block out and can now mess with it with impugnity.
// We'll put the remainder back into the list if we're done with it below.
char* __buf_start = __REINTERPRET_CAST(char*, __block);
__add_atomic_t __bytes_left = __block->_M_end - __buf_start;
if ((__bytes_left < __total_bytes) && (__bytes_left >= __STATIC_CAST(__add_atomic_t, _p_size))) {
// There's enough left for at least one object, but not as much as we wanted
__result = __buf_start;
__nobjs = (int)(__bytes_left/_p_size);
__total_bytes = __STATIC_CAST(__add_atomic_t, _p_size) * __nobjs;
__bytes_left -= __total_bytes;
__buf_start += __total_bytes;
}
else if (__bytes_left >= __total_bytes) {
// The block has enough left to satisfy all that was asked for
__result = __buf_start;
__bytes_left -= __total_bytes;
__buf_start += __total_bytes;
}
if (__bytes_left != 0) {
// There is still some memory left over in block after we satisfied our request.
if ((__result != 0) && (__bytes_left >= (__add_atomic_t)sizeof(_FreeBlockHeader))) {
// We were able to allocate at least one object and there is still enough
// left to put remainder back into list.
_FreeBlockHeader* __newblock = __REINTERPRET_CAST(_FreeBlockHeader*, __buf_start);
__newblock->_M_end = __block->_M_end;
_S_free_mem_blocks.push(__newblock);
}
else {
// We were not able to allocate enough for at least one object.
// Shove into freelist of nearest (rounded-down!) size.
size_t __rounded_down = _S_round_up(__bytes_left + 1) - (size_t)_ALIGN;
if (__rounded_down > 0)
_S_free_list[_S_FREELIST_INDEX(__rounded_down)].push((_Obj*)__buf_start);
}
}
if (__result != 0)
return __result;
}
// We couldn't satisfy it from the list of free blocks, get new memory.
__add_atomic_t __bytes_to_get = 2 * __total_bytes +
__STATIC_CAST(__add_atomic_t,
_S_round_up(__STATIC_CAST(__uadd_atomic_t, _STLP_ATOMIC_ADD(&_S_heap_size, 0)))) +
_STLP_OFFSET;
_STLP_TRY {
__result = __stlp_new_chunk(__bytes_to_get);
}
#if defined (_STLP_USE_EXCEPTIONS)
catch (const bad_alloc&) {
// Allocation failed; try to canibalize from freelist of a larger object size.
for (size_t __i = _p_size; __i <= (size_t)_MAX_BYTES; __i += (size_t)_ALIGN) {
_Obj* __p = _S_free_list[_S_FREELIST_INDEX(__i)].pop();
if (0 != __p) {
if (__i < sizeof(_FreeBlockHeader)) {
// Not enough to put into list of free blocks, divvy it up here.
// Use as much as possible for this request and shove remainder into freelist.
__nobjs = (int)(__i/_p_size);
__total_bytes = __nobjs * __STATIC_CAST(__add_atomic_t, _p_size);
size_t __bytes_left = __i - __total_bytes;
size_t __rounded_down = _S_round_up(__bytes_left+1) - (size_t)_ALIGN;
if (__rounded_down > 0) {
_S_free_list[_S_FREELIST_INDEX(__rounded_down)].push(__REINTERPRET_CAST(_Obj*, __REINTERPRET_CAST(char*, __p) + __total_bytes));
}
return __REINTERPRET_CAST(char*, __p);
}
else {
// Add node to list of available blocks and recursively allocate from it.
_FreeBlockHeader* __newblock = (_FreeBlockHeader*)__p;
__newblock->_M_end = __REINTERPRET_CAST(char*, __p) + __i;
_S_free_mem_blocks.push(__newblock);
return _S_chunk_alloc(_p_size, __nobjs);
}
}
}
// We were not able to find something in a freelist, try to allocate a smaller amount.
__bytes_to_get = __total_bytes + _STLP_OFFSET;
__result = __stlp_new_chunk(__bytes_to_get);
// This should either throw an exception or remedy the situation.
// Thus we assume it succeeded.
}
#endif
// Alignment check
_STLP_VERBOSE_ASSERT(((__REINTERPRET_CAST(size_t, __result) & __STATIC_CAST(size_t, _ALIGN - 1)) == 0),
_StlMsg_DBA_DELETED_TWICE)
_STLP_ATOMIC_ADD(&_S_heap_size, __bytes_to_get >> 4);
# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
// We have to track the allocated memory chunks for release on exit.
_S_chunks.push(__REINTERPRET_CAST(_Obj*, __result));
__result += _ALIGN;
__bytes_to_get -= _ALIGN;
# endif
if (__bytes_to_get > __total_bytes) {
// Push excess memory allocated in this chunk into list of free memory blocks
_FreeBlockHeader* __freeblock = __REINTERPRET_CAST(_FreeBlockHeader*, __result + __total_bytes);
__freeblock->_M_end = __result + __bytes_to_get;
_S_free_mem_blocks.push(__freeblock);
}
return __result;
}
# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
void __node_alloc_impl::_S_alloc_call()
{ _STLP_ATOMIC_INCREMENT(&_S_alloc_counter()); }
void __node_alloc_impl::_S_dealloc_call() {
_STLP_VOLATILE __stl_atomic_t *pcounter = &_S_alloc_counter();
if (_STLP_ATOMIC_DECREMENT(pcounter) == 0)
_S_chunk_dealloc();
}
/* We deallocate all the memory chunks */
void __node_alloc_impl::_S_chunk_dealloc() {
// Note: The _Node_alloc_helper class ensures that this function
// will only be called when the (shared) library is unloaded or the
// process is shutdown. It's thus not possible that another thread
// is currently trying to allocate a node (we're not thread-safe here).
//
// Clear the free blocks and all freelistst. This makes sure that if
// for some reason more memory is allocated again during shutdown
// (it'd also be really nasty to leave references to deallocated memory).
_S_free_mem_blocks.clear();
_S_heap_size = 0;
for (size_t __i = 0; __i < _STLP_NFREELISTS; ++__i) {
_S_free_list[__i].clear();
}
// Detach list of chunks and free them all
_Obj* __chunk = _S_chunks.clear();
while (__chunk != 0) {
_Obj* __next = __chunk->_M_next;
__stlp_delete_chunck(__chunk);
__chunk = __next;
}
}
# endif
#endif
#if defined (_STLP_DO_CLEAN_NODE_ALLOC)
struct __node_alloc_cleaner {
~__node_alloc_cleaner()
{ __node_alloc_impl::_S_dealloc_call(); }
};
# if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)
_STLP_VOLATILE __stl_atomic_t& _STLP_CALL
# else
__stl_atomic_t& _STLP_CALL
# endif
__node_alloc_impl::_S_alloc_counter() {
static _AllocCounter _S_counter = 1;
static __node_alloc_cleaner _S_node_alloc_cleaner;
return _S_counter;
}
#endif
#if !defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)
_Node_alloc_obj * _STLP_VOLATILE
__node_alloc_impl::_S_free_list[_STLP_NFREELISTS]
= {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
// The 16 zeros are necessary to make version 4.1 of the SunPro
// compiler happy. Otherwise it appears to allocate too little
// space for the array.
#else
_STLP_atomic_freelist __node_alloc_impl::_S_free_list[_STLP_NFREELISTS];
_STLP_atomic_freelist __node_alloc_impl::_S_free_mem_blocks;
#endif
#if !defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)
char *__node_alloc_impl::_S_start_free = 0;
char *__node_alloc_impl::_S_end_free = 0;
#endif
#if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)
_STLP_VOLATILE __add_atomic_t
#else
size_t
#endif
__node_alloc_impl::_S_heap_size = 0;
#if defined (_STLP_DO_CLEAN_NODE_ALLOC)
# if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)
_STLP_atomic_freelist __node_alloc_impl::_S_chunks;
# else
_Node_alloc_obj* __node_alloc_impl::_S_chunks = 0;
# endif
#endif
void * _STLP_CALL __node_alloc::_M_allocate(size_t& __n)
{ return __node_alloc_impl::_M_allocate(__n); }
void _STLP_CALL __node_alloc::_M_deallocate(void *__p, size_t __n)
{ __node_alloc_impl::_M_deallocate(__p, __n); }
#if defined (_STLP_PTHREADS) && !defined (_STLP_NO_THREADS)
# define _STLP_DATA_ALIGNMENT 8
_STLP_MOVE_TO_PRIV_NAMESPACE
// *******************************************************
// __perthread_alloc implementation
union _Pthread_alloc_obj {
union _Pthread_alloc_obj * __free_list_link;
char __client_data[_STLP_DATA_ALIGNMENT]; /* The client sees this. */
};
// Pthread allocators don't appear to the client to have meaningful
// instances. We do in fact need to associate some state with each
// thread. That state is represented by _Pthread_alloc_per_thread_state.
struct _Pthread_alloc_per_thread_state {
typedef _Pthread_alloc_obj __obj;
enum { _S_NFREELISTS = _MAX_BYTES / _STLP_DATA_ALIGNMENT };
// Free list link for list of available per thread structures.
// When one of these becomes available for reuse due to thread
// termination, any objects in its free list remain associated
// with it. The whole structure may then be used by a newly
// created thread.
_Pthread_alloc_per_thread_state() : __next(0)
{ memset((void *)__CONST_CAST(_Pthread_alloc_obj**, __free_list), 0, (size_t)_S_NFREELISTS * sizeof(__obj *)); }
// Returns an object of size __n, and possibly adds to size n free list.
void *_M_refill(size_t __n);
_Pthread_alloc_obj* volatile __free_list[_S_NFREELISTS];
_Pthread_alloc_per_thread_state *__next;
// this data member is only to be used by per_thread_allocator, which returns memory to the originating thread.
_STLP_mutex _M_lock;
};
// Pthread-specific allocator.
class _Pthread_alloc_impl {
public: // but only for internal use:
typedef _Pthread_alloc_per_thread_state __state_type;
typedef char value_type;
// Allocates a chunk for nobjs of size size. nobjs may be reduced
// if it is inconvenient to allocate the requested number.
static char *_S_chunk_alloc(size_t __size, size_t &__nobjs, __state_type*);
enum {_S_ALIGN = _STLP_DATA_ALIGNMENT};
static size_t _S_round_up(size_t __bytes)
{ return (((__bytes) + (int)_S_ALIGN - 1) & ~((int)_S_ALIGN - 1)); }
static size_t _S_freelist_index(size_t __bytes)
{ return (((__bytes) + (int)_S_ALIGN - 1) / (int)_S_ALIGN - 1); }
private:
// Chunk allocation state. And other shared state.
// Protected by _S_chunk_allocator_lock.
static _STLP_STATIC_MUTEX _S_chunk_allocator_lock;
static char *_S_start_free;
static char *_S_end_free;
static size_t _S_heap_size;
static __state_type *_S_free_per_thread_states;
static pthread_key_t _S_key;
static bool _S_key_initialized;
// Pthread key under which per thread state is stored.
// Allocator instances that are currently unclaimed by any thread.
static void _S_destructor(void *instance);
// Function to be called on thread exit to reclaim per thread
// state.
static __state_type *_S_new_per_thread_state();
public:
// Return a recycled or new per thread state.
static __state_type *_S_get_per_thread_state();
private:
// ensure that the current thread has an associated
// per thread state.
class _M_lock;
friend class _M_lock;
class _M_lock {
public:
_M_lock () { _S_chunk_allocator_lock._M_acquire_lock(); }
~_M_lock () { _S_chunk_allocator_lock._M_release_lock(); }
};
public:
/* n must be > 0 */
static void * allocate(size_t& __n);
/* p may not be 0 */
static void deallocate(void *__p, size_t __n);
// boris : versions for per_thread_allocator
/* n must be > 0 */
static void * allocate(size_t& __n, __state_type* __a);
/* p may not be 0 */
static void deallocate(void *__p, size_t __n, __state_type* __a);
static void * reallocate(void *__p, size_t __old_sz, size_t& __new_sz);
};
/* Returns an object of size n, and optionally adds to size n free list.*/
/* We assume that n is properly aligned. */
/* We hold the allocation lock. */
void *_Pthread_alloc_per_thread_state::_M_refill(size_t __n) {
typedef _Pthread_alloc_obj __obj;
size_t __nobjs = 128;
char * __chunk = _Pthread_alloc_impl::_S_chunk_alloc(__n, __nobjs, this);
__obj * volatile * __my_free_list;
__obj * __result;
__obj * __current_obj, * __next_obj;
size_t __i;
if (1 == __nobjs) {
return __chunk;
}
__my_free_list = __free_list + _Pthread_alloc_impl::_S_freelist_index(__n);
/* Build free list in chunk */
__result = (__obj *)__chunk;
*__my_free_list = __next_obj = (__obj *)(__chunk + __n);
for (__i = 1; ; ++__i) {
__current_obj = __next_obj;
__next_obj = (__obj *)((char *)__next_obj + __n);
if (__nobjs - 1 == __i) {
__current_obj -> __free_list_link = 0;
break;
} else {
__current_obj -> __free_list_link = __next_obj;
}
}
return __result;
}
void _Pthread_alloc_impl::_S_destructor(void *__instance) {
_M_lock __lock_instance; // Need to acquire lock here.
_Pthread_alloc_per_thread_state* __s = (_Pthread_alloc_per_thread_state*)__instance;
__s -> __next = _S_free_per_thread_states;
_S_free_per_thread_states = __s;
}
_Pthread_alloc_per_thread_state* _Pthread_alloc_impl::_S_new_per_thread_state() {
/* lock already held here. */
if (0 != _S_free_per_thread_states) {
_Pthread_alloc_per_thread_state *__result = _S_free_per_thread_states;
_S_free_per_thread_states = _S_free_per_thread_states -> __next;
return __result;
}
else {
return new _Pthread_alloc_per_thread_state;
}
}
_Pthread_alloc_per_thread_state* _Pthread_alloc_impl::_S_get_per_thread_state() {
int __ret_code;
__state_type* __result;
if (_S_key_initialized && (__result = (__state_type*) pthread_getspecific(_S_key)))
return __result;
/*REFERENCED*/
_M_lock __lock_instance; // Need to acquire lock here.
if (!_S_key_initialized) {
if (pthread_key_create(&_S_key, _S_destructor)) {
_STLP_THROW_BAD_ALLOC; // failed
}
_S_key_initialized = true;
}
__result = _S_new_per_thread_state();
__ret_code = pthread_setspecific(_S_key, __result);
if (__ret_code) {
if (__ret_code == ENOMEM) {
_STLP_THROW_BAD_ALLOC;
} else {
// EINVAL
_STLP_ABORT();
}
}
return __result;
}
/* We allocate memory in large chunks in order to avoid fragmenting */
/* the malloc heap too much. */
/* We assume that size is properly aligned. */
char *_Pthread_alloc_impl::_S_chunk_alloc(size_t __p_size, size_t &__nobjs, _Pthread_alloc_per_thread_state *__a) {
typedef _Pthread_alloc_obj __obj;
{
char * __result;
size_t __total_bytes;
size_t __bytes_left;
/*REFERENCED*/
_M_lock __lock_instance; // Acquire lock for this routine
__total_bytes = __p_size * __nobjs;
__bytes_left = _S_end_free - _S_start_free;
if (__bytes_left >= __total_bytes) {
__result = _S_start_free;
_S_start_free += __total_bytes;
return __result;
} else if (__bytes_left >= __p_size) {
__nobjs = __bytes_left/__p_size;
__total_bytes = __p_size * __nobjs;
__result = _S_start_free;
_S_start_free += __total_bytes;
return __result;
} else {
size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size);
// Try to make use of the left-over piece.
if (__bytes_left > 0) {
__obj * volatile * __my_free_list = __a->__free_list + _S_freelist_index(__bytes_left);
((__obj *)_S_start_free) -> __free_list_link = *__my_free_list;
*__my_free_list = (__obj *)_S_start_free;
}
# ifdef _SGI_SOURCE
// Try to get memory that's aligned on something like a
// cache line boundary, so as to avoid parceling out
// parts of the same line to different threads and thus
// possibly different processors.
{
const int __cache_line_size = 128; // probable upper bound
__bytes_to_get &= ~(__cache_line_size-1);
_S_start_free = (char *)memalign(__cache_line_size, __bytes_to_get);
if (0 == _S_start_free) {
_S_start_free = (char *)__malloc_alloc::allocate(__bytes_to_get);
}
}
# else /* !SGI_SOURCE */
_S_start_free = (char *)__malloc_alloc::allocate(__bytes_to_get);
# endif
_S_heap_size += __bytes_to_get >> 4;
_S_end_free = _S_start_free + __bytes_to_get;
}
}
// lock is released here
return _S_chunk_alloc(__p_size, __nobjs, __a);
}
/* n must be > 0 */
void *_Pthread_alloc_impl::allocate(size_t& __n) {
typedef _Pthread_alloc_obj __obj;
__obj * volatile * __my_free_list;
__obj * __result;
__state_type* __a;
if (__n > _MAX_BYTES) {
return __malloc_alloc::allocate(__n);
}
__n = _S_round_up(__n);
__a = _S_get_per_thread_state();
__my_free_list = __a->__free_list + _S_freelist_index(__n);
__result = *__my_free_list;
if (__result == 0) {
void *__r = __a->_M_refill(__n);
return __r;
}
*__my_free_list = __result->__free_list_link;
return __result;
};
/* p may not be 0 */
void _Pthread_alloc_impl::deallocate(void *__p, size_t __n) {
typedef _Pthread_alloc_obj __obj;
__obj *__q = (__obj *)__p;
__obj * volatile * __my_free_list;
__state_type* __a;
if (__n > _MAX_BYTES) {
__malloc_alloc::deallocate(__p, __n);
return;
}
__a = _S_get_per_thread_state();
__my_free_list = __a->__free_list + _S_freelist_index(__n);
__q -> __free_list_link = *__my_free_list;
*__my_free_list = __q;
}
// boris : versions for per_thread_allocator
/* n must be > 0 */
void *_Pthread_alloc_impl::allocate(size_t& __n, __state_type* __a) {
typedef _Pthread_alloc_obj __obj;
__obj * volatile * __my_free_list;
__obj * __result;
if (__n > _MAX_BYTES) {
return __malloc_alloc::allocate(__n);
}
__n = _S_round_up(__n);
// boris : here, we have to lock per thread state, as we may be getting memory from
// different thread pool.
_STLP_auto_lock __lock(__a->_M_lock);
__my_free_list = __a->__free_list + _S_freelist_index(__n);
__result = *__my_free_list;
if (__result == 0) {
void *__r = __a->_M_refill(__n);
return __r;
}
*__my_free_list = __result->__free_list_link;
return __result;
};
/* p may not be 0 */
void _Pthread_alloc_impl::deallocate(void *__p, size_t __n, __state_type* __a) {
typedef _Pthread_alloc_obj __obj;
__obj *__q = (__obj *)__p;
__obj * volatile * __my_free_list;
if (__n > _MAX_BYTES) {
__malloc_alloc::deallocate(__p, __n);
return;
}
// boris : here, we have to lock per thread state, as we may be returning memory from
// different thread.
_STLP_auto_lock __lock(__a->_M_lock);
__my_free_list = __a->__free_list + _S_freelist_index(__n);
__q -> __free_list_link = *__my_free_list;
*__my_free_list = __q;
}
void *_Pthread_alloc_impl::reallocate(void *__p, size_t __old_sz, size_t& __new_sz) {
void * __result;
size_t __copy_sz;
if (__old_sz > _MAX_BYTES && __new_sz > _MAX_BYTES) {
return realloc(__p, __new_sz);
}
if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return __p;
__result = allocate(__new_sz);
__copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
memcpy(__result, __p, __copy_sz);
deallocate(__p, __old_sz);
return __result;
}
_Pthread_alloc_per_thread_state* _Pthread_alloc_impl::_S_free_per_thread_states = 0;
pthread_key_t _Pthread_alloc_impl::_S_key = 0;
_STLP_STATIC_MUTEX _Pthread_alloc_impl::_S_chunk_allocator_lock _STLP_MUTEX_INITIALIZER;
bool _Pthread_alloc_impl::_S_key_initialized = false;
char *_Pthread_alloc_impl::_S_start_free = 0;
char *_Pthread_alloc_impl::_S_end_free = 0;
size_t _Pthread_alloc_impl::_S_heap_size = 0;
void * _STLP_CALL _Pthread_alloc::allocate(size_t& __n)
{ return _Pthread_alloc_impl::allocate(__n); }
void _STLP_CALL _Pthread_alloc::deallocate(void *__p, size_t __n)
{ _Pthread_alloc_impl::deallocate(__p, __n); }
void * _STLP_CALL _Pthread_alloc::allocate(size_t& __n, __state_type* __a)
{ return _Pthread_alloc_impl::allocate(__n, __a); }
void _STLP_CALL _Pthread_alloc::deallocate(void *__p, size_t __n, __state_type* __a)
{ _Pthread_alloc_impl::deallocate(__p, __n, __a); }
void * _STLP_CALL _Pthread_alloc::reallocate(void *__p, size_t __old_sz, size_t& __new_sz)
{ return _Pthread_alloc_impl::reallocate(__p, __old_sz, __new_sz); }
_Pthread_alloc_per_thread_state* _STLP_CALL _Pthread_alloc::_S_get_per_thread_state()
{ return _Pthread_alloc_impl::_S_get_per_thread_state(); }
_STLP_MOVE_TO_STD_NAMESPACE
#endif
_STLP_END_NAMESPACE
#undef _S_FREELIST_INDEX