libstdc++-v3/include/ext/pool_allocator.h

   1 // Allocators -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  * Copyright (c) 1996-1997
  32  * Silicon Graphics Computer Systems, Inc.
  33  *
  34  * Permission to use, copy, modify, distribute and sell this software
  35  * and its documentation for any purpose is hereby granted without fee,
  36  * provided that the above copyright notice appear in all copies and
  37  * that both that copyright notice and this permission notice appear
  38  * in supporting documentation.  Silicon Graphics makes no
  39  * representations about the suitability of this software for any
  40  * purpose.  It is provided "as is" without express or implied warranty.
  41  */
  42
  43 /** @file ext/pool_allocator.h
  44  *  This file is a GNU extension to the Standard C++ Library.
  45  *  You should only include this header if you are using GCC 3 or later.
  46  */
  47 #ifndef _POOL_ALLOCATOR_H
  48 #define _POOL_ALLOCATOR_H 1
  49
  50 #include <bits/c++config.h>
  51 #include <new>
  52 #include <bits/functexcept.h>
  53 #include <bits/stl_threads.h>
  54 #include <bits/atomicity.h>
  55
  56 namespace __gnu_cxx
  57 {
  58   using std::__throw_bad_alloc;
  59
  60   /**
  61    *  @if maint
  62    *  Default node allocator.  "SGI" style.  Uses various allocators to
  63    *  fulfill underlying requests (and makes as few requests as possible
  64    *  when in default high-speed pool mode).
  65    *
  66    *  Important implementation properties:
  67    *  0. If globally mandated, then allocate objects from new
  68    *  1. If the clients request an object of size > _S_max_bytes, the resulting
  69    *     object will be obtained directly from new
  70    *  2. In all other cases, we allocate an object of size exactly
  71    *     _S_round_up(requested_size).  Thus the client has enough size
  72    *     information that we can return the object to the proper free list
  73    *     without permanently losing part of the object.
  74    *
  75    *  The first template parameter specifies whether more than one thread may
  76    *  use this allocator.  It is safe to allocate an object from one instance
  77    *  of a default_alloc and deallocate it with another one.  This effectively
  78    *  transfers its ownership to the second one.  This may have undesirable
  79    *  effects on reference locality.
  80    *
  81    *  The second parameter is unused and serves only to allow the
  82    *  creation of multiple default_alloc instances.  Note that
  83    *  containers built on different allocator instances have different
  84    *  types, limiting the utility of this approach.  If you do not
  85    *  wish to share the free lists with the main default_alloc
  86    *  instance, instantiate this with a non-zero __inst.
  87    *
  88    *  @endif
  89    *  (See @link Allocators allocators info @endlink for more.)
  90    */
  91   template<bool __threads, int __inst>
  92     class __pool_alloc
  93     {
  94     private:
  95       enum {_S_align = 8};
  96       enum {_S_max_bytes = 128};
  97       enum {_S_freelists = _S_max_bytes / _S_align};
  98
  99       union _Obj
 100       {
 101         union _Obj* _M_free_list_link;
 102         char        _M_client_data[1];    // The client sees this.
 103       };
 104
 105       static _Obj* volatile         _S_free_list[_S_freelists];
 106
 107       // Chunk allocation state.
 108       static char*                  _S_start_free;
 109       static char*                  _S_end_free;
 110       static size_t                 _S_heap_size;
 111
 112       static _STL_mutex_lock        _S_lock;
 113       static _Atomic_word           _S_force_new;
 114
 115       static size_t
 116       _S_round_up(size_t __bytes)
 117       { return ((__bytes + (size_t)_S_align - 1) & ~((size_t)_S_align - 1)); }
 118
 119       static size_t
 120       _S_freelist_index(size_t __bytes)
 121       { return ((__bytes + (size_t)_S_align - 1)/(size_t)_S_align - 1); }
 122
 123       // Returns an object of size __n, and optionally adds to size __n
 124       // free list.
 125       static void*
 126       _S_refill(size_t __n);
 127
 128       // Allocates a chunk for nobjs of size size.  nobjs may be reduced
 129       // if it is inconvenient to allocate the requested number.
 130       static char*
 131       _S_chunk_alloc(size_t __n, int& __nobjs);
 132
 133       // It would be nice to use _STL_auto_lock here.  But we need a
 134       // test whether threads are in use.
 135       struct _Lock
 136       {
 137         _Lock() { if (__threads) _S_lock._M_acquire_lock(); }
 138         ~_Lock() { if (__threads) _S_lock._M_release_lock(); }
 139       } __attribute__ ((__unused__));
 140       friend struct _Lock;
 141
 142     public:
 143       // __n must be > 0
 144       static void*
 145       allocate(size_t __n);
 146
 147       // __p may not be 0
 148       static void
 149       deallocate(void* __p, size_t __n);
 150     };
 151
 152   template<bool __threads, int __inst>
 153     inline bool
 154     operator==(const __pool_alloc<__threads,__inst>&,
 155                const __pool_alloc<__threads,__inst>&)
 156     { return true; }
 157
 158   template<bool __threads, int __inst>
 159     inline bool
 160     operator!=(const __pool_alloc<__threads,__inst>&,
 161                const __pool_alloc<__threads,__inst>&)
 162     { return false; }
 163
 164
 165   // Allocate memory in large chunks in order to avoid fragmenting the
 166   // heap too much.  Assume that __n is properly aligned.  We hold
 167   // the allocation lock.
 168   template<bool __threads, int __inst>
 169     char*
 170     __pool_alloc<__threads, __inst>::_S_chunk_alloc(size_t __n, int& __nobjs)
 171     {
 172       char* __result;
 173       size_t __total_bytes = __n * __nobjs;
 174       size_t __bytes_left = _S_end_free - _S_start_free;
 175
 176       if (__bytes_left >= __total_bytes)
 177         {
 178           __result = _S_start_free;
 179           _S_start_free += __total_bytes;
 180           return __result ;
 181         }
 182       else if (__bytes_left >= __n)
 183         {
 184           __nobjs = (int)(__bytes_left/__n);
 185           __total_bytes = __n * __nobjs;
 186           __result = _S_start_free;
 187           _S_start_free += __total_bytes;
 188           return __result;
 189         }
 190       else
 191         {
 192           size_t __bytes_to_get =
 193             2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
 194           // Try to make use of the left-over piece.
 195           if (__bytes_left > 0)
 196             {
 197               _Obj* volatile* __free_list =
 198                 _S_free_list + _S_freelist_index(__bytes_left);
 199
 200               ((_Obj*)(void*)_S_start_free)->_M_free_list_link = *__free_list;
 201               *__free_list = (_Obj*)(void*)_S_start_free;
 202             }
 203           _S_start_free = static_cast<char*>(::operator new(__bytes_to_get));
 204           if (_S_start_free == 0)
 205             {
 206               size_t __i;
 207               _Obj* volatile* __free_list;
 208               _Obj* __p;
 209               // Try to make do with what we have.  That can't hurt.  We
 210               // do not try smaller requests, since that tends to result
 211               // in disaster on multi-process machines.
 212               __i = __n;
 213               for (; __i <= (size_t) _S_max_bytes; __i += (size_t) _S_align)
 214                 {
 215                   __free_list = _S_free_list + _S_freelist_index(__i);
 216                   __p = *__free_list;
 217                   if (__p != 0)
 218                     {
 219                       *__free_list = __p -> _M_free_list_link;
 220                       _S_start_free = (char*)__p;
 221                       _S_end_free = _S_start_free + __i;
 222                       return _S_chunk_alloc(__n, __nobjs);
 223                       // Any leftover piece will eventually make it to the
 224                       // right free list.
 225                     }
 226                 }
 227               _S_end_free = 0;        // In case of exception.
 228               _S_start_free = static_cast<char*>(::operator new(__bytes_to_get));
 229               // This should either throw an exception or remedy the situation.
 230               // Thus we assume it succeeded.
 231             }
 232           _S_heap_size += __bytes_to_get;
 233           _S_end_free = _S_start_free + __bytes_to_get;
 234           return _S_chunk_alloc(__n, __nobjs);
 235         }
 236     }
 237
 238   // Returns an object of size __n, and optionally adds to "size
 239   // __n"'s free list.  We assume that __n is properly aligned.  We
 240   // hold the allocation lock.
 241   template<bool __threads, int __inst>
 242     void*
 243     __pool_alloc<__threads, __inst>::_S_refill(size_t __n)
 244     {
 245       int __nobjs = 20;
 246       char* __chunk = _S_chunk_alloc(__n, __nobjs);
 247       _Obj* volatile* __free_list;
 248       _Obj* __result;
 249       _Obj* __current_obj;
 250       _Obj* __next_obj;
 251       int __i;
 252
 253       if (1 == __nobjs)
 254         return __chunk;
 255       __free_list = _S_free_list + _S_freelist_index(__n);
 256
 257       // Build free list in chunk.
 258       __result = (_Obj*)(void*)__chunk;
 259       *__free_list = __next_obj = (_Obj*)(void*)(__chunk + __n);
 260       for (__i = 1; ; __i++)
 261         {
 262           __current_obj = __next_obj;
 263           __next_obj = (_Obj*)(void*)((char*)__next_obj + __n);
 264           if (__nobjs - 1 == __i)
 265             {
 266               __current_obj -> _M_free_list_link = 0;
 267               break;
 268             }
 269           else
 270             __current_obj -> _M_free_list_link = __next_obj;
 271         }
 272       return __result;
 273     }
 274
 275   template<bool __threads, int __inst>
 276     void*
 277     __pool_alloc<__threads, __inst>::allocate(size_t __n)
 278     {
 279       void* __ret = 0;
 280
 281       // If there is a race through here, assume answer from getenv
 282       // will resolve in same direction.  Inspired by techniques
 283       // to efficiently support threading found in basic_string.h.
 284       if (_S_force_new == 0)
 285         {
 286           if (getenv("GLIBCXX_FORCE_NEW"))
 287             __atomic_add(&_S_force_new, 1);
 288           else
 289             __atomic_add(&_S_force_new, -1);
 290         }
 291
 292       if ((__n > (size_t) _S_max_bytes) || (_S_force_new > 0))
 293         __ret = ::operator new(__n);
 294       else
 295         {
 296           _Obj* volatile* __free_list = _S_free_list + _S_freelist_index(__n);
 297           // Acquire the lock here with a constructor call.  This
 298           // ensures that it is released in exit or during stack
 299           // unwinding.
 300           _Lock __lock_instance;
 301           _Obj* __restrict__ __result = *__free_list;
 302           if (__builtin_expect(__result == 0, 0))
 303             __ret = _S_refill(_S_round_up(__n));
 304           else
 305             {
 306               *__free_list = __result -> _M_free_list_link;
 307               __ret = __result;
 308             }
 309           if (__builtin_expect(__ret == 0, 0))
 310             __throw_bad_alloc();
 311         }
 312       return __ret;
 313     }
 314
 315   template<bool __threads, int __inst>
 316     void
 317     __pool_alloc<__threads, __inst>::deallocate(void* __p, size_t __n)
 318     {
 319       if ((__n > (size_t) _S_max_bytes) || (_S_force_new > 0))
 320         ::operator delete(__p);
 321       else
 322         {
 323           _Obj* volatile* __free_list = _S_free_list + _S_freelist_index(__n);
 324           _Obj* __q = (_Obj*)__p;
 325
 326           // Acquire the lock here with a constructor call.  This
 327           // ensures that it is released in exit or during stack
 328           // unwinding.
 329           _Lock __lock_instance;
 330           __q -> _M_free_list_link = *__free_list;
 331           *__free_list = __q;
 332         }
 333     }
 334
 335   template<bool __threads, int __inst>
 336     typename __pool_alloc<__threads, __inst>::_Obj* volatile
 337     __pool_alloc<__threads, __inst>::_S_free_list[_S_freelists];
 338
 339   template<bool __threads, int __inst>
 340     char* __pool_alloc<__threads, __inst>::_S_start_free = 0;
 341
 342   template<bool __threads, int __inst>
 343     char* __pool_alloc<__threads, __inst>::_S_end_free = 0;
 344
 345   template<bool __threads, int __inst>
 346     size_t __pool_alloc<__threads, __inst>::_S_heap_size = 0;
 347
 348   template<bool __threads, int __inst>
 349     _STL_mutex_lock
 350     __pool_alloc<__threads, __inst>::_S_lock __STL_MUTEX_INITIALIZER;
 351
 352   template<bool __threads, int __inst> _Atomic_word
 353   __pool_alloc<__threads, __inst>::_S_force_new = 0;
 354
 355   // Inhibit implicit instantiations for required instantiations,
 356   // which are defined via explicit instantiations elsewhere.
 357   // NB: This syntax is a GNU extension.
 358 #if _GLIBCXX_EXTERN_TEMPLATE
 359   extern template class __pool_alloc<true, 0>;
 360 #endif
 361 } // namespace __gnu_cxx
 362
 363 #endif