mt_allocator.h

来自「Mac OS X 10.4.9 for x86 Source Code gcc」· C头文件 代码 · 共 764 行 · 第 1/2 页

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

// Copyright (C) 2003, 2004, 2005 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 2, 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.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @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 <new>
#include <cstdlib>
#include <bits/functexcept.h>
#include <bits/gthr.h>
#include <bits/atomicity.h>

namespace __gnu_cxx
{
  typedef void (*__destroy_handler)(void*);
  typedef void (*__create_handler)(void);

  /// @brief  Base class for pool object.
  struct __pool_base
  {
    // Using short int as type for the binmap implies we are never
    // caching blocks larger than 65535 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.
      size_t	_M_max_bytes; 
      
      // Size in bytes of the smallest bin.
      // NB: Must be a power of 2 and >= _M_align.
      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 choosen the value below.
      // See http://gcc.gnu.org/ml/libstdc++/2001-07/msg00077.html
      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(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]; }

    const size_t
    _M_get_align()
    { return _M_options._M_align; }

    explicit 
    __pool_base() 
    : _M_options(_Tune()), _M_binmap(NULL), _M_init(false) { }

    explicit 
    __pool_base(const _Tune& __options)
    : _M_options(__options), _M_binmap(NULL), _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<bool _Thread>
    class __pool;

  template<>
    class __pool<true>;

  template<>
    class __pool<false>;

  /// Specialization for single thread.
  template<>
    class __pool<false> : public __pool_base
    {
    public:
      union _Block_record
      {
	// Points to the block_record of the next free block.
	_Block_record* volatile         _M_next;
      };

      struct _Bin_record
      {
	// An "array" of pointers to the first free block.
	_Block_record** volatile        _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);
    
      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(NULL), _M_bin_size(1) { }

      explicit __pool(const __pool_base::_Tune& __tune) 
      : __pool_base(__tune), _M_bin(NULL), _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* volatile	_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<true> : 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* volatile        _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* volatile         _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** volatile        _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.
	// Memory to these "arrays" is allocated in _S_initialize() for
	// _S_max_threads + global pool 0.
	size_t* volatile                _M_free;
	size_t* volatile                _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;
      };
      
      void
      _M_initialize(__destroy_handler __d);

      void
      _M_initialize_once(__create_handler __c)
      {
	// Although the test in __gthread_once() would suffice, we
	// wrap test of the once condition in our own unlocked
	// check. This saves one function call to pthread_once()
	// (which itself only tests for the once value unlocked anyway
	// and immediately returns if set)
	if (__builtin_expect(_M_init == false, false))
	  {
	    if (__gthread_active_p())
	      __gthread_once(&_M_once, __c);
	    if (!_M_init)
	      __c();
	  }
      }

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

      void 
      _M_destroy_thread_key(void* __freelist_pos);

      size_t 
      _M_get_thread_id();

      explicit __pool() 
      : _M_bin(NULL), _M_bin_size(1), _M_thread_freelist(NULL) 
      {
	// On some platforms, __gthread_once_t is an aggregate.
	__gthread_once_t __tmp = __GTHREAD_ONCE_INIT;
	_M_once = __tmp;
      }

      explicit __pool(const __pool_base::_Tune& __tune) 
      : __pool_base(__tune), _M_bin(NULL), _M_bin_size(1), 
      _M_thread_freelist(NULL) 
      {
	// On some platforms, __gthread_once_t is an aggregate.
	__gthread_once_t __tmp = __GTHREAD_ONCE_INIT;
	_M_once = __tmp;
      }