Subversion Repositories Kolibri OS

// MT-optimized allocator -*- C++ -*-

// Copyright (C) 2003-2013 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 3, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// .

/** @file ext/mt_allocator.h

 *  This file is a GNU extension to the Standard C++ Library.

 */

#ifndef _MT_ALLOCATOR_H

#define _MT_ALLOCATOR_H 1

#include 

#include 

#include 

#include 

#include 

#if __cplusplus >= 201103L

#include 

#endif

namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)

{

_GLIBCXX_BEGIN_NAMESPACE_VERSION

  using std::size_t;

  using std::ptrdiff_t;

  typedef void (*__destroy_handler)(void*);

  /// Base class for pool object.

  struct __pool_base

  {

    // Using short int as type for the binmap implies we are never

    // caching blocks larger than 32768 with this allocator.

    typedef unsigned short int _Binmap_type;

    // Variables used to configure the behavior of the allocator,

    // assigned and explained in detail below.

    struct _Tune

     {

      // Compile time constants for the default _Tune values.

      enum { _S_align = 8 };

      enum { _S_max_bytes = 128 };

      enum { _S_min_bin = 8 };

      enum { _S_chunk_size = 4096 - 4 * sizeof(void*) };

      enum { _S_max_threads = 4096 };

      enum { _S_freelist_headroom = 10 };

      // Alignment needed.

      // NB: In any case must be >= sizeof(_Block_record), that

      // is 4 on 32 bit machines and 8 on 64 bit machines.

      size_t	_M_align;

      // Allocation requests (after round-up to power of 2) below

      // this value will be handled by the allocator. A raw new/

      // call will be used for requests larger than this value.

      // NB: Must be much smaller than _M_chunk_size and in any

      // case <= 32768.

      size_t	_M_max_bytes;

      // Size in bytes of the smallest bin.

      // NB: Must be a power of 2 and >= _M_align (and of course

      // much smaller than _M_max_bytes).

      size_t	_M_min_bin;

      // In order to avoid fragmenting and minimize the number of

      // new() calls we always request new memory using this

      // value. Based on previous discussions on the libstdc++

      // mailing list we have chosen the value below.

      // See http://gcc.gnu.org/ml/libstdc++/2001-07/msg00077.html

      // NB: At least one order of magnitude > _M_max_bytes.

      size_t	_M_chunk_size;

      // The maximum number of supported threads. For

      // single-threaded operation, use one. Maximum values will

      // vary depending on details of the underlying system. (For

      // instance, Linux 2.4.18 reports 4070 in

      // /proc/sys/kernel/threads-max, while Linux 2.6.6 reports

      // 65534)

      size_t 	_M_max_threads;

      // Each time a deallocation occurs in a threaded application

      // we make sure that there are no more than

      // _M_freelist_headroom % of used memory on the freelist. If

      // the number of additional records is more than

      // _M_freelist_headroom % of the freelist, we move these

      // records back to the global pool.

      size_t 	_M_freelist_headroom;

      // Set to true forces all allocations to use new().

      bool 	_M_force_new;

      explicit

      _Tune()

      : _M_align(_S_align), _M_max_bytes(_S_max_bytes), _M_min_bin(_S_min_bin),

      _M_chunk_size(_S_chunk_size), _M_max_threads(_S_max_threads),

      _M_freelist_headroom(_S_freelist_headroom),

      _M_force_new(std::getenv("GLIBCXX_FORCE_NEW") ? true : false)

      { }

      explicit

      _Tune(size_t __align, size_t __maxb, size_t __minbin, size_t __chunk,

	    size_t __maxthreads, size_t __headroom, bool __force)

      : _M_align(__align), _M_max_bytes(__maxb), _M_min_bin(__minbin),

      _M_chunk_size(__chunk), _M_max_threads(__maxthreads),

      _M_freelist_headroom(__headroom), _M_force_new(__force)

      { }

    };

    struct _Block_address

    {

      void* 			_M_initial;

      _Block_address* 		_M_next;

    };

    const _Tune&

    _M_get_options() const

    { return _M_options; }

    void

    _M_set_options(_Tune __t)

    {

      if (!_M_init)

	_M_options = __t;

    }

    bool

    _M_check_threshold(size_t __bytes)

    { return __bytes > _M_options._M_max_bytes || _M_options._M_force_new; }

    size_t

    _M_get_binmap(size_t __bytes)

    { return _M_binmap[__bytes]; }

    size_t

    _M_get_align()

    { return _M_options._M_align; }

    explicit

    __pool_base()

    : _M_options(_Tune()), _M_binmap(0), _M_init(false) { }

    explicit

    __pool_base(const _Tune& __options)

    : _M_options(__options), _M_binmap(0), _M_init(false) { }

  private:

    explicit

    __pool_base(const __pool_base&);

    __pool_base&

    operator=(const __pool_base&);

  protected:

    // Configuration options.

    _Tune 	       		_M_options;

    _Binmap_type* 		_M_binmap;

    // Configuration of the pool object via _M_options can happen

    // after construction but before initialization. After

    // initialization is complete, this variable is set to true.

    bool 			_M_init;

  };

  /**

   *  @brief  Data describing the underlying memory pool, parameterized on

   *  threading support.

   */

  template

    class __pool;

  /// Specialization for single thread.

  template<>

    class __pool : public __pool_base

    {

    public:

      union _Block_record

      {

	// Points to the block_record of the next free block.

	_Block_record* 			_M_next;

      };

      struct _Bin_record

      {

	// An "array" of pointers to the first free block.

	_Block_record**			_M_first;

	// A list of the initial addresses of all allocated blocks.

	_Block_address*		     	_M_address;

      };

      void

      _M_initialize_once()

      {

	if (__builtin_expect(_M_init == false, false))

	  _M_initialize();

      }

      void

      _M_destroy() throw();

      char*

      _M_reserve_block(size_t __bytes, const size_t __thread_id);

      void

      _M_reclaim_block(char* __p, size_t __bytes) throw ();

      size_t

      _M_get_thread_id() { return 0; }

      const _Bin_record&

      _M_get_bin(size_t __which)

      { return _M_bin[__which]; }

      void

      _M_adjust_freelist(const _Bin_record&, _Block_record*, size_t)

      { }

      explicit __pool()

      : _M_bin(0), _M_bin_size(1) { }

      explicit __pool(const __pool_base::_Tune& __tune)

      : __pool_base(__tune), _M_bin(0), _M_bin_size(1) { }

    private:

      // An "array" of bin_records each of which represents a specific

      // power of 2 size. Memory to this "array" is allocated in

      // _M_initialize().

      _Bin_record*		 _M_bin;

      // Actual value calculated in _M_initialize().

      size_t 	       	     	_M_bin_size;

      void

      _M_initialize();

  };

#ifdef __GTHREADS

  /// Specialization for thread enabled, via gthreads.h.

  template<>

    class __pool : public __pool_base

    {

    public:

      // Each requesting thread is assigned an id ranging from 1 to

      // _S_max_threads. Thread id 0 is used as a global memory pool.

      // In order to get constant performance on the thread assignment

      // routine, we keep a list of free ids. When a thread first

      // requests memory we remove the first record in this list and

      // stores the address in a __gthread_key. When initializing the

      // __gthread_key we specify a destructor. When this destructor

      // (i.e. the thread dies) is called, we return the thread id to

      // the front of this list.

      struct _Thread_record

      {

	// Points to next free thread id record. NULL if last record in list.

	_Thread_record*			_M_next;

	// Thread id ranging from 1 to _S_max_threads.

	size_t                          _M_id;

      };

      union _Block_record

      {

	// Points to the block_record of the next free block.

	_Block_record*			_M_next;

	// The thread id of the thread which has requested this block.

	size_t                          _M_thread_id;

      };

      struct _Bin_record

      {

	// An "array" of pointers to the first free block for each

	// thread id. Memory to this "array" is allocated in

	// _S_initialize() for _S_max_threads + global pool 0.

	_Block_record**			_M_first;

	// A list of the initial addresses of all allocated blocks.

	_Block_address*		     	_M_address;

	// An "array" of counters used to keep track of the amount of

	// blocks that are on the freelist/used for each thread id.

	// - Note that the second part of the allocated _M_used "array"

	//   actually hosts (atomic) counters of reclaimed blocks:  in

	//   _M_reserve_block and in _M_reclaim_block those numbers are

	//   subtracted from the first ones to obtain the actual size

	//   of the "working set" of the given thread.

	// - Memory to these "arrays" is allocated in _S_initialize()

	//   for _S_max_threads + global pool 0.

	size_t*				_M_free;

	size_t*			        _M_used;

	// Each bin has its own mutex which is used to ensure data

	// integrity while changing "ownership" on a block.  The mutex

	// is initialized in _S_initialize().

	__gthread_mutex_t*              _M_mutex;

      };

      // XXX GLIBCXX_ABI Deprecated

      void

      _M_initialize(__destroy_handler);

      void

      _M_initialize_once()

      {

	if (__builtin_expect(_M_init == false, false))

	  _M_initialize();

      }

      void

      _M_destroy() throw();

      char*

      _M_reserve_block(size_t __bytes, const size_t __thread_id);

      void

      _M_reclaim_block(char* __p, size_t __bytes) throw ();

      const _Bin_record&

      _M_get_bin(size_t __which)

      { return _M_bin[__which]; }

      void

      _M_adjust_freelist(const _Bin_record& __bin, _Block_record* __block,

			 size_t __thread_id)

      {

	if (__gthread_active_p())

	  {

	    __block->_M_thread_id = __thread_id;

	    --__bin._M_free[__thread_id];

	    ++__bin._M_used[__thread_id];

	  }

      }

      // XXX GLIBCXX_ABI Deprecated

      _GLIBCXX_CONST void

      _M_destroy_thread_key(void*) throw ();

      size_t

      _M_get_thread_id();

      explicit __pool()

      : _M_bin(0), _M_bin_size(1), _M_thread_freelist(0)

      { }

      explicit __pool(const __pool_base::_Tune& __tune)

      : __pool_base(__tune), _M_bin(0), _M_bin_size(1),

	_M_thread_freelist(0)

      { }

    private:

      // An "array" of bin_records each of which represents a specific

      // power of 2 size. Memory to this "array" is allocated in

      // _M_initialize().

      _Bin_record*		_M_bin;

      // Actual value calculated in _M_initialize().

      size_t 	       	     	_M_bin_size;

      _Thread_record* 		_M_thread_freelist;

      void*			_M_thread_freelist_initial;

      void

      _M_initialize();

    };

#endif

  template