--- /dev/null
+/*
+ *
+ * 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>
+//# define _STLP_MALLOC_USABLE_SIZE(__buf) malloc_usable_size(__buf)
+#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 malloc 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 void* __stlp_chunk_malloc(size_t __bytes) { _STLP_CHECK_NULL_ALLOC(_malloc_dbg(__bytes, _CRT_BLOCK, __FILE__, __LINE__)); }
+inline void __stlp_chunck_free(void* __p) { _free_dbg(__p, _CRT_BLOCK); }
+#else // !_DEBUG
+# ifdef _STLP_NODE_ALLOC_USE_MALLOC
+# include <cstdlib>
+inline void* __stlp_chunk_malloc(size_t __bytes) { _STLP_CHECK_NULL_ALLOC(_STLP_VENDOR_CSTD::malloc(__bytes)); }
+inline void __stlp_chunck_free(void* __p) { _STLP_VENDOR_CSTD::free(__p); }
+# else
+inline void* __stlp_chunk_malloc(size_t __bytes) { return _STLP_STD::__stl_new(__bytes); }
+inline void __stlp_chunck_free(void* __p) { _STLP_STD::__stl_delete(__p); }
+# endif
+#endif // !_DEBUG
+
+#define _S_FREELIST_INDEX(__bytes) ((__bytes - size_t(1)) >> (int)_ALIGN_SHIFT)
+
+_STLP_BEGIN_NAMESPACE
+
+class __malloc_alloc_impl {
+private:
+ static void* _S_oom_malloc(size_t __n) {
+ __oom_handler_type __my_malloc_handler;
+ void * __result;
+
+ for (;;) {
+ __my_malloc_handler = __oom_handler;
+ if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
+ (*__my_malloc_handler)();
+ __result = malloc(__n);
+ if (__result) return(__result);
+ }
+#if defined (_STLP_NEED_UNREACHABLE_RETURN)
+ return 0;
+#endif
+ }
+ static __oom_handler_type __oom_handler;
+public:
+ // this one is needed for proper simple_alloc wrapping
+ typedef char value_type;
+ static void* allocate(size_t& __n) {
+ void* __result = malloc(__n);
+ if (0 == __result) {
+ __result = _S_oom_malloc(__n);
+ }
+#if defined (_STLP_MALLOC_USABLE_SIZE)
+ else {
+ size_t __new_n = _STLP_MALLOC_USABLE_SIZE(__result);
+ /*
+ if (__n != __new_n) {
+ printf("requested size %d, usable %d\n", __n, __new_n);
+ }
+ */
+ __n = __new_n;
+ }
+#endif
+ return __result;
+ }
+ static void deallocate(void* __p, size_t /* __n */) { free((char*)__p); }
+ static __oom_handler_type set_malloc_handler(__oom_handler_type __f) {
+ __oom_handler_type __old = __oom_handler;
+ __oom_handler = __f;
+ return __old;
+ }
+};
+
+// malloc_alloc out-of-memory handling
+__oom_handler_type __malloc_alloc_impl::__oom_handler = __STATIC_CAST(__oom_handler_type, 0);
+
+void* _STLP_CALL __malloc_alloc::allocate(size_t& __n)
+{ return __malloc_alloc_impl::allocate(__n); }
+__oom_handler_type _STLP_CALL __malloc_alloc::set_malloc_handler(__oom_handler_type __f)
+{ return __malloc_alloc_impl::set_malloc_handler(__f); }
+
+// *******************************************************
+// 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 {
+public:
+ _Node_Alloc_Lock() {
+# if defined (_STLP_SGI_THREADS)
+ if (__us_rsthread_malloc)
+# endif
+ _S_lock._M_acquire_lock();
+ }
+
+ ~_Node_Alloc_Lock() {
+# if defined (_STLP_SGI_THREADS)
+ if (__us_rsthread_malloc)
+# endif
+ _S_lock._M_release_lock();
+ }
+
+ static _STLP_STATIC_MUTEX _S_lock;
+};
+
+_STLP_STATIC_MUTEX _Node_Alloc_Lock::_S_lock _STLP_MUTEX_INITIALIZER;
+# 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 {
+_STLP_PRIVATE:
+ 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 __stl_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
+}
+
+/* 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);
+ }
+
+ size_t __bytes_to_get =
+ 2 * __total_bytes + _S_round_up(_S_heap_size >> 4)
+# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
+ + sizeof(_Obj)
+# endif
+ ;
+
+ _S_start_free = __STATIC_CAST(char*, __stlp_chunk_malloc(__bytes_to_get));
+ if (0 == _S_start_free) {
+ _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.
+ }
+ }
+ _S_end_free = 0; // In case of exception.
+ _S_start_free = __STATIC_CAST(char*, __stlp_chunk_malloc(__bytes_to_get));
+ /*
+ (char*)malloc_alloc::allocate(__bytes_to_get);
+ */
+
+ // This should either throw an
+ // exception or remedy the situation. Thus we assume it
+ // succeeded.
+ }
+
+ _S_heap_size += __bytes_to_get;
+# 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;
+# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
+ _S_start_free += sizeof(_Obj);
+# endif
+ 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_chunck_free(__pcur);
+ __pcur = __pnext;
+ }
+ _S_chunks = 0;
+ _S_start_free = _S_end_free = 0;
+ _S_heap_size = 0;
+ memset(__REINTERPRET_CAST(char*, &_S_free_list[0]), 0, _STLP_NFREELISTS * sizeof(_Obj*));
+}
+# endif /* _STLP_DO_CLEAN_NODE_ALLOC */
+
+#else /* !defined(_STLP_USE_LOCK_FREE_IMPLEMENTATION) */
+
+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;
+}
+
+/* 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;
+ __stl_atomic_t __total_bytes = __STATIC_CAST(__stl_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);
+ __stl_atomic_t __bytes_left = __block->_M_end - __buf_start;
+
+ if ((__bytes_left < __total_bytes) && (__bytes_left >= __STATIC_CAST(__stl_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(__stl_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 >= 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.
+ __stl_atomic_t __bytes_to_get = 2 * __total_bytes + __STATIC_CAST(__stl_atomic_t, _S_round_up(_S_heap_size >> 4))
+# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
+ + _ALIGN
+# endif
+ ;
+
+ __result = __STATIC_CAST(char*, __stlp_chunk_malloc(__bytes_to_get));
+ // Alignment check
+ _STLP_VERBOSE_ASSERT(((__REINTERPRET_CAST(size_t, __result) & __STATIC_CAST(size_t, _ALIGN - 1)) == 0), _StlMsg_DBA_DELETED_TWICE)
+
+ if (0 == __result) {
+ // 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(__stl_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
+# if defined (_STLP_DO_CLEAN_NODE_ALLOC)
+ + _ALIGN
+# endif
+ ;
+ __result = __STATIC_CAST(char*, __stlp_chunk_malloc(__bytes_to_get));
+ // Alignment check
+ _STLP_VERBOSE_ASSERT(((__REINTERPRET_CAST(size_t, __result) & __STATIC_CAST(size_t, _ALIGN - 1)) == 0), _StlMsg_DBA_DELETED_TWICE)
+
+ // This should either throw an exception or remedy the situation.
+ // Thus we assume it succeeded.
+ }
+
+ _STLP_ATOMIC_ADD(&_S_heap_size, __bytes_to_get);
+
+# 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_chunck_free(__chunk);
+ __chunk = __next;
+ }
+}
+# endif /* _STLP_DO_CLEAN_NODE_ALLOC */
+
+#endif /* !defined(_STLP_USE_LOCK_FREE_IMPLEMENTATION) */
+
+#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 __stl_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 _STLP_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)) {
+ __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) {
+ __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 >> 4);
+ // 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;
+ _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
projects / polintos / scott / priv.git / blobdiff