Subversion Repositories Kolibri OS

/*

 * Copyright (c) 1996

 * Silicon Graphics Computer Systems, Inc.

 *

 * Permission to use, copy, modify, distribute and sell this software

 * and its documentation for any purpose is hereby granted without fee,

 * provided that the above copyright notice appear in all copies and

 * that both that copyright notice and this permission notice appear

 * in supporting documentation.  Silicon Graphics makes no

 * representations about the suitability of this software for any

 * purpose.  It is provided "as is" without express or implied warranty.

 */

#ifndef _CPP_BITS_PTHREAD_ALLOCIMPL_H

#define _CPP_BITS_PTHREAD_ALLOCIMPL_H 1

// Pthread-specific node allocator.

// This is similar to the default allocator, except that free-list

// information is kept separately for each thread, avoiding locking.

// This should be reasonably fast even in the presence of threads.

// The down side is that storage may not be well-utilized.

// It is not an error to allocate memory in thread A and deallocate

// it in thread B.  But this effectively transfers ownership of the memory,

// so that it can only be reallocated by thread B.  Thus this can effectively

// result in a storage leak if it's done on a regular basis.

// It can also result in frequent sharing of

// cache lines among processors, with potentially serious performance

// consequences.

#include 

#include 

#include 

#ifndef __RESTRICT

#  define __RESTRICT

#endif

#include 

namespace std

{

#define __STL_DATA_ALIGNMENT 8

union _Pthread_alloc_obj {

    union _Pthread_alloc_obj * __free_list_link;

    char __client_data[__STL_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<_Max_size>.

template

struct _Pthread_alloc_per_thread_state {

  typedef _Pthread_alloc_obj __obj;

  enum { _S_NFREELISTS = _Max_size/__STL_DATA_ALIGNMENT };

  _Pthread_alloc_obj* volatile __free_list[_S_NFREELISTS];

  _Pthread_alloc_per_thread_state<_Max_size> * __next;

	// 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 *)__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-specific allocator.

// The argument specifies the largest object size allocated from per-thread

// free lists.  Larger objects are allocated using malloc_alloc.

// Max_size must be a power of 2.

template 

class _Pthread_alloc_template {

public: // but only for internal use:

  typedef _Pthread_alloc_obj __obj;

  // 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, int &__nobjs);

  enum {_S_ALIGN = __STL_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 pthread_mutex_t _S_chunk_allocator_lock;

  static char *_S_start_free;

  static char *_S_end_free;

  static size_t _S_heap_size;

  static _Pthread_alloc_per_thread_state<_Max_size>* _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 _Pthread_alloc_per_thread_state<_Max_size> *_S_new_per_thread_state();

        // Return a recycled or new per thread state.

  static _Pthread_alloc_per_thread_state<_Max_size> *_S_get_per_thread_state();

        // ensure that the current thread has an associated

        // per thread state.

  class _M_lock;

  friend class _M_lock;

  class _M_lock {

      public:

        _M_lock () { pthread_mutex_lock(&_S_chunk_allocator_lock); }

        ~_M_lock () { pthread_mutex_unlock(&_S_chunk_allocator_lock); }

  };

public:

  /* n must be > 0      */

  static void * allocate(size_t __n)

  {

    __obj * volatile * __my_free_list;

    __obj * __RESTRICT __result;

    _Pthread_alloc_per_thread_state<_Max_size>* __a;

    if (__n > _Max_size) {

        return(malloc_alloc::allocate(__n));

    }

    if (!_S_key_initialized ||

        !(__a = (_Pthread_alloc_per_thread_state<_Max_size>*)

                                 pthread_getspecific(_S_key))) {

        __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(_S_round_up(__n));

        return __r;

    }

    *__my_free_list = __result -> __free_list_link;

    return (__result);

  };

  /* p may not be 0 */

  static void deallocate(void *__p, size_t __n)

  {

    __obj *__q = (__obj *)__p;

    __obj * volatile * __my_free_list;

    _Pthread_alloc_per_thread_state<_Max_size>* __a;

    if (__n > _Max_size) {

        malloc_alloc::deallocate(__p, __n);

        return;

    }

    if (!_S_key_initialized ||

        !(__a = (_Pthread_alloc_per_thread_state<_Max_size> *)

                pthread_getspecific(_S_key))) {

        __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;

  }

  static void * reallocate(void *__p, size_t __old_sz, size_t __new_sz);

} ;

typedef _Pthread_alloc_template<> pthread_alloc;

template 

void _Pthread_alloc_template<_Max_size>::_S_destructor(void * __instance)

{

    _M_lock __lock_instance;	// Need to acquire lock here.

    _Pthread_alloc_per_thread_state<_Max_size>* __s =

        (_Pthread_alloc_per_thread_state<_Max_size> *)__instance;

    __s -> __next = _S_free_per_thread_states;

    _S_free_per_thread_states = __s;

}

template 

_Pthread_alloc_per_thread_state<_Max_size> *

_Pthread_alloc_template<_Max_size>::_S_new_per_thread_state()

{

    /* lock already held here.	*/

    if (0 != _S_free_per_thread_states) {

        _Pthread_alloc_per_thread_state<_Max_size> *__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<_Max_size>;

    }

}

template 

_Pthread_alloc_per_thread_state<_Max_size> *

_Pthread_alloc_template<_Max_size>::_S_get_per_thread_state()

{

    /*REFERENCED*/

    _M_lock __lock_instance;	// Need to acquire lock here.

    int __ret_code;

    _Pthread_alloc_per_thread_state<_Max_size> * __result;

    if (!_S_key_initialized) {

        if (pthread_key_create(&_S_key, _S_destructor)) {

	    std::__throw_bad_alloc();  // defined in funcexcept.h

        }

        _S_key_initialized = true;

    }

    __result = _S_new_per_thread_state();

    __ret_code = pthread_setspecific(_S_key, __result);

    if (__ret_code) {

      if (__ret_code == ENOMEM) {

	std::__throw_bad_alloc();

      } else {

	// EINVAL

	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.                             */

template 

char *_Pthread_alloc_template<_Max_size>

::_S_chunk_alloc(size_t __size, int &__nobjs)

{

  {

    char * __result;

    size_t __total_bytes;

    size_t __bytes_left;

    /*REFERENCED*/

    _M_lock __lock_instance;         // Acquire lock for this routine

    __total_bytes = __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 >= __size) {

        __nobjs = __bytes_left/__size;

        __total_bytes = __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) {

            _Pthread_alloc_per_thread_state<_Max_size>* __a =

                (_Pthread_alloc_per_thread_state<_Max_size>*)

			pthread_getspecific(_S_key);

            __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(__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.                                         */

template 

void *_Pthread_alloc_per_thread_state<_Max_size>

::_M_refill(size_t __n)

{

    int __nobjs = 128;

    char * __chunk =

	_Pthread_alloc_template<_Max_size>::_S_chunk_alloc(__n, __nobjs);

    __obj * volatile * __my_free_list;

    __obj * __result;

    __obj * __current_obj, * __next_obj;

    int __i;

    if (1 == __nobjs)  {

        return(__chunk);

    }

    __my_free_list = __free_list

		 + _Pthread_alloc_template<_Max_size>::_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);

}

template 

void *_Pthread_alloc_template<_Max_size>

::reallocate(void *__p, size_t __old_sz, size_t __new_sz)

{

    void * __result;

    size_t __copy_sz;

    if (__old_sz > _Max_size

	&& __new_sz > _Max_size) {

        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);

}

template 

_Pthread_alloc_per_thread_state<_Max_size> *

_Pthread_alloc_template<_Max_size>::_S_free_per_thread_states = 0;

template 

pthread_key_t _Pthread_alloc_template<_Max_size>::_S_key;

template 

bool _Pthread_alloc_template<_Max_size>::_S_key_initialized = false;

template 

pthread_mutex_t _Pthread_alloc_template<_Max_size>::_S_chunk_allocator_lock

= PTHREAD_MUTEX_INITIALIZER;

template 

char *_Pthread_alloc_template<_Max_size>

::_S_start_free = 0;

template 

char *_Pthread_alloc_template<_Max_size>

::_S_end_free = 0;

template 

size_t _Pthread_alloc_template<_Max_size>

::_S_heap_size = 0;

template 

class pthread_allocator {

  typedef pthread_alloc _S_Alloc;          // The underlying allocator.

public:

  typedef size_t     size_type;

  typedef ptrdiff_t  difference_type;

  typedef _Tp*       pointer;

  typedef const _Tp* const_pointer;

  typedef _Tp&       reference;

  typedef const _Tp& const_reference;

  typedef _Tp        value_type;

  template  struct rebind {

    typedef pthread_allocator<_NewType> other;

  };

  pthread_allocator() __STL_NOTHROW {}

  pthread_allocator(const pthread_allocator& a) __STL_NOTHROW {}

  template 

	pthread_allocator(const pthread_allocator<_OtherType>&)

		__STL_NOTHROW {}

  ~pthread_allocator() __STL_NOTHROW {}

  pointer address(reference __x) const { return &__x; }

  const_pointer address(const_reference __x) const { return &__x; }

  // __n is permitted to be 0.  The C++ standard says nothing about what

  // the return value is when __n == 0.

  _Tp* allocate(size_type __n, const void* = 0) {

    return __n != 0 ? static_cast<_Tp*>(_S_Alloc::allocate(__n * sizeof(_Tp)))

                    : 0;

  }

  // p is not permitted to be a null pointer.

  void deallocate(pointer __p, size_type __n)

    { _S_Alloc::deallocate(__p, __n * sizeof(_Tp)); }

  size_type max_size() const __STL_NOTHROW

    { return size_t(-1) / sizeof(_Tp); }

  void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }

  void destroy(pointer _p) { _p->~_Tp(); }

};

template<>

class pthread_allocator {

public:

  typedef size_t      size_type;

  typedef ptrdiff_t   difference_type;

  typedef void*       pointer;

  typedef const void* const_pointer;

  typedef void        value_type;

  template  struct rebind {

    typedef pthread_allocator<_NewType> other;

  };

};

template 

inline bool operator==(const _Pthread_alloc_template<_Max_size>&,

                       const _Pthread_alloc_template<_Max_size>&)

{

  return true;

}

template 

inline bool operator==(const pthread_allocator<_T1>&,

                       const pthread_allocator<_T2>& a2)

{

  return true;

}

template 

inline bool operator!=(const pthread_allocator<_T1>&,

                       const pthread_allocator<_T2>&)

{

  return false;

}

template 

struct _Alloc_traits<_Tp, _Pthread_alloc_template<_Max_size> >

{

  static const bool _S_instanceless = true;

  typedef simple_alloc<_Tp, _Pthread_alloc_template<_Max_size> > _Alloc_type;

  typedef __allocator<_Tp, _Pthread_alloc_template<_Max_size> >

          allocator_type;

};

template 

struct _Alloc_traits<_Tp, __allocator<_Atype, _Pthread_alloc_template<_Max> > >

{

  static const bool _S_instanceless = true;

  typedef simple_alloc<_Tp, _Pthread_alloc_template<_Max> > _Alloc_type;

  typedef __allocator<_Tp, _Pthread_alloc_template<_Max> > allocator_type;

};

template 

struct _Alloc_traits<_Tp, pthread_allocator<_Atype> >

{

  static const bool _S_instanceless = true;

  typedef simple_alloc<_Tp, _Pthread_alloc_template<> > _Alloc_type;

  typedef pthread_allocator<_Tp> allocator_type;

};

} // namespace std

#endif /* _CPP_BITS_PTHREAD_ALLOCIMPL_H */

// Local Variables:

// mode:C++

// End: