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

   1 // MT-optimized allocator -*- C++ -*-
   2
   3 // Copyright (C) 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 /** @file ext/mt_allocator.h
  31  *  This file is a GNU extension to the Standard C++ Library.
  32  *  You should only include this header if you are using GCC 3 or later.
  33  */
  34
  35 #ifndef _MT_ALLOCATOR_H
  36 #define _MT_ALLOCATOR_H 1
  37
  38 #include <new>
  39 #include <cstdlib>
  40 #include <bits/functexcept.h>
  41 #include <bits/gthr.h>
  42 #include <bits/atomicity.h>
  43
  44 namespace __gnu_cxx
  45 {
  46   /**
  47    *  This is a fixed size (power of 2) allocator which - when
  48    *  compiled with thread support - will maintain one freelist per
  49    *  size per thread plus a "global" one. Steps are taken to limit
  50    *  the per thread freelist sizes (by returning excess back to
  51    *  "global").
  52    *
  53    *  Usage examples:
  54    *  @code
  55    *    vector<int, __gnu_cxx::__mt_alloc<int> > v1;
  56    *
  57    *    typedef __gnu_cxx::__mt_alloc<char> > string_allocator;
  58    *    std::basic_string<char, std::char_traits<char>, string_allocator> s1;
  59    *  @endcode
  60    */
  61   template<typename _Tp>
  62     class __mt_alloc
  63     {
  64     public:
  65       typedef size_t     size_type;
  66       typedef ptrdiff_t  difference_type;
  67       typedef _Tp*       pointer;
  68       typedef const _Tp* const_pointer;
  69       typedef _Tp&       reference;
  70       typedef const _Tp& const_reference;
  71       typedef _Tp        value_type;
  72
  73       template<typename _Tp1>
  74         struct rebind
  75         { typedef __mt_alloc<_Tp1> other; };
  76
  77       __mt_alloc() throw()
  78       {
  79         // XXX
  80       }
  81
  82       __mt_alloc(const __mt_alloc&) throw()
  83       {
  84         // XXX
  85       }
  86
  87       template<typename _Tp1>
  88         __mt_alloc(const __mt_alloc<_Tp1>&) throw()
  89         {
  90           // XXX
  91         }
  92
  93       ~__mt_alloc() throw() { }
  94
  95       pointer
  96       address(reference __x) const { return &__x; }
  97
  98       const_pointer
  99       address(const_reference __x) const { return &__x; }
 100
 101       size_type
 102       max_size() const throw()
 103       { return size_t(-1) / sizeof(_Tp); }
 104
 105       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 106       // 402. wrong new expression in [some_] allocator::construct
 107       void
 108       construct(pointer __p, const _Tp& __val)
 109       { ::new(__p) _Tp(__val); }
 110
 111       void
 112       destroy(pointer __p) { __p->~_Tp(); }
 113
 114     private:
 115       /*
 116        * We need to create the initial lists and set up some variables
 117        * before we can answer to the first request for memory.
 118        * The initialization of these variables is done at file scope
 119        * below class declaration.
 120        */
 121 #ifdef __GTHREADS
 122       static __gthread_once_t _S_once_mt;
 123 #endif
 124       static bool volatile _S_initialized;
 125
 126       /*
 127        * If the env var GLIBCXX_FORCE_NEW is set during _S_init()
 128        * we set this var to true which causes all allocations to use new()
 129        */
 130       static bool _S_force_new;
 131
 132       /*
 133        * Using short int as type for the binmap implies we are never caching
 134        * blocks larger than 65535 with this allocator
 135        */
 136       typedef unsigned short int binmap_type;
 137       static binmap_type* _S_binmap;
 138
 139       static void _S_init();
 140
 141       /*
 142        * Variables used to "tune" the behavior of the allocator, assigned
 143        * and explained in detail below.
 144        */
 145       static size_t _S_max_bytes;
 146       static size_t _S_chunk_size;
 147       static size_t _S_max_threads;
 148       static size_t _S_no_of_bins;
 149       static size_t _S_freelist_headroom;
 150
 151       /*
 152        * Each requesting thread is assigned an id ranging from 1 to
 153        * _S_max_threads. Thread id 0 is used as a global memory pool.
 154        * In order to get constant performance on the thread assignment
 155        * routine, we keep a list of free ids. When a thread first requests
 156        * memory we remove the first record in this list and stores the address
 157        * in a __gthread_key. When initializing the __gthread_key
 158        * we specify a destructor. When this destructor (i.e. the thread dies)
 159        * is called, we return the thread id to the front of this list.
 160        */
 161 #ifdef __GTHREADS
 162       struct thread_record
 163       {
 164         /*
 165          * Points to next free thread id record. NULL if last record in list.
 166          */
 167         thread_record* volatile next;
 168
 169         /*
 170          * Thread id ranging from 1 to _S_max_threads.
 171          */
 172         size_t id;
 173       };
 174
 175       static thread_record* volatile _S_thread_freelist_first;
 176       static __gthread_mutex_t _S_thread_freelist_mutex;
 177       static void _S_thread_key_destr(void* freelist_pos);
 178       static __gthread_key_t _S_thread_key;
 179       static size_t _S_get_thread_id();
 180 #endif
 181
 182       struct block_record
 183       {
 184         /*
 185          * Points to the next block_record for its thread_id.
 186          */
 187         block_record* volatile next;
 188
 189         /*
 190          * The thread id of the thread which has requested this block.
 191          */
 192 #ifdef __GTHREADS
 193         size_t thread_id;
 194 #endif
 195       };
 196
 197       struct bin_record
 198       {
 199         /*
 200          * An "array" of pointers to the first/last free block for each
 201          * thread id. Memory to these "arrays" is allocated in _S_init()
 202          * for _S_max_threads + global pool 0.
 203          */
 204         block_record** volatile first;
 205         block_record** volatile last;
 206
 207         /*
 208          * An "array" of counters used to keep track of the amount of blocks
 209          * that are on the freelist/used for each thread id.
 210          * Memory to these "arrays" is allocated in _S_init()
 211          * for _S_max_threads + global pool 0.
 212          */
 213         size_t* volatile free;
 214         size_t* volatile used;
 215
 216         /*
 217          * Each bin has its own mutex which is used to ensure data integrity
 218          * while changing "ownership" on a block.
 219          * The mutex is initialized in _S_init().
 220          */
 221 #ifdef __GTHREADS
 222         __gthread_mutex_t* mutex;
 223 #endif
 224       };
 225
 226       /*
 227        * An "array" of bin_records each of which represents a specific
 228        * power of 2 size. Memory to this "array" is allocated in _S_init().
 229        */
 230       static bin_record* volatile _S_bin;
 231
 232     public:
 233       pointer
 234       allocate(size_t __n, const void* = 0)
 235       {
 236         /*
 237          * Although the test in __gthread_once() would suffice, we
 238          * wrap test of the once condition in our own unlocked
 239          * check. This saves one function call to pthread_once()
 240          * (which itself only tests for the once value unlocked anyway
 241          * and immediately returns if set)
 242          */
 243         if (!_S_initialized)
 244           {
 245 #ifdef __GTHREADS
 246             if (__gthread_active_p())
 247               __gthread_once(&_S_once_mt, _S_init);
 248             else
 249 #endif
 250               {
 251                 _S_max_threads = 0;
 252                 _S_init();
 253               }
 254           }
 255
 256         /*
 257          * Requests larger than _S_max_bytes are handled by
 258          * new/delete directly
 259          */
 260         if (__n * sizeof(_Tp) > _S_max_bytes || _S_force_new)
 261           {
 262             void* __ret = ::operator new(__n * sizeof(_Tp));
 263             if (!__ret)
 264               std::__throw_bad_alloc();
 265             return static_cast<_Tp*>(__ret);
 266           }
 267
 268         /*
 269          * Round up to power of 2 and figure out which bin to use
 270          */
 271         size_t bin = _S_binmap[__n * sizeof(_Tp)];
 272
 273 #ifdef __GTHREADS
 274         size_t thread_id = _S_get_thread_id();
 275 #else
 276         size_t thread_id = 0;
 277 #endif
 278
 279         block_record* block = NULL;
 280
 281         /*
 282          * Find out if we have blocks on our freelist.
 283          * If so, go ahead and use them directly without
 284          * having to lock anything.
 285          */
 286         if (_S_bin[bin].first[thread_id] == NULL)
 287           {
 288             /*
 289              * Are we using threads?
 290              * - Yes, check if there are free blocks on the global
 291              *   list. If so, grab up to block_count blocks in one
 292              *   lock and change ownership. If the global list is
 293              *   empty, we allocate a new chunk and add those blocks
 294              *   directly to our own freelist (with us as owner).
 295              * - No, all operations are made directly to global pool 0
 296              *   no need to lock or change ownership but check for free
 297              *   blocks on global list (and if not add new ones) and
 298              *   get the first one.
 299              */
 300 #ifdef __GTHREADS
 301             if (__gthread_active_p())
 302               {
 303                 size_t bin_t = 1 << bin;
 304                 size_t block_count =
 305                   _S_chunk_size /(bin_t + sizeof(block_record));
 306
 307                 __gthread_mutex_lock(_S_bin[bin].mutex);
 308
 309                 if (_S_bin[bin].first[0] == NULL)
 310                   {
 311                     /*
 312                      * No need to hold the lock when we are adding a
 313                      * whole chunk to our own list
 314                      */
 315                     __gthread_mutex_unlock(_S_bin[bin].mutex);
 316
 317                     _S_bin[bin].first[thread_id] =
 318                      static_cast<block_record*>(::operator new(_S_chunk_size));
 319
 320                     if (!_S_bin[bin].first[thread_id])
 321                       std::__throw_bad_alloc();
 322
 323                     _S_bin[bin].free[thread_id] = block_count;
 324
 325                     block_count--;
 326                     block = _S_bin[bin].first[thread_id];
 327
 328                     while (block_count > 0)
 329                       {
 330                         block->next = (block_record*)((char*)block +
 331                                       (bin_t + sizeof(block_record)));
 332                         block->thread_id = thread_id;
 333                         block = block->next;
 334                         block_count--;
 335                       }
 336
 337                     block->next = NULL;
 338                     block->thread_id = thread_id;
 339                     _S_bin[bin].last[thread_id] = block;
 340                   }
 341                 else
 342                   {
 343                     size_t global_count = 0;
 344
 345                     while( _S_bin[bin].first[0] != NULL &&
 346                            global_count < block_count )
 347                       {
 348                         block = _S_bin[bin].first[0];
 349
 350                         if (_S_bin[bin].first[thread_id] == NULL)
 351                           _S_bin[bin].first[thread_id] = block;
 352                         else
 353                           _S_bin[bin].last[thread_id]->next = block;
 354
 355                         _S_bin[bin].last[thread_id] = block;
 356
 357                         block->thread_id = thread_id;
 358
 359                         _S_bin[bin].free[thread_id]++;
 360
 361                         _S_bin[bin].first[0] = _S_bin[bin].first[0]->next;
 362
 363                         global_count++;
 364                       }
 365
 366                     block->next = NULL;
 367
 368                     __gthread_mutex_unlock(_S_bin[bin].mutex);
 369                   }
 370
 371                 /*
 372                  * Return the first newly added block in our list and
 373                  * update the counters
 374                  */
 375                 block = _S_bin[bin].first[thread_id];
 376                 _S_bin[bin].first[thread_id] =
 377                   _S_bin[bin].first[thread_id]->next;
 378
 379                 _S_bin[bin].free[thread_id]--;
 380                 _S_bin[bin].used[thread_id]++;
 381               }
 382             else
 383 #endif
 384               {
 385                 _S_bin[bin].first[0] =
 386                   static_cast<block_record*>(::operator new(_S_chunk_size));
 387
 388                 if (!_S_bin[bin].first[0])
 389                   std::__throw_bad_alloc();
 390
 391                 size_t bin_t = 1 << bin;
 392                 size_t block_count =
 393                   _S_chunk_size / (bin_t + sizeof(block_record));
 394
 395                 block_count--;
 396                 block = _S_bin[bin].first[0];
 397
 398                 while (block_count > 0)
 399                   {
 400                     block->next = (block_record*)((char*)block +
 401                                   (bin_t + sizeof(block_record)));
 402                     block = block->next;
 403                     block_count--;
 404                   }
 405
 406                 block->next = NULL;
 407                 _S_bin[bin].last[0] = block;
 408
 409                 block = _S_bin[bin].first[0];
 410
 411                 /*
 412                  * Remove from list
 413                  */
 414                 _S_bin[bin].first[0] = _S_bin[bin].first[0]->next;
 415               }
 416           }
 417         else
 418           {
 419             /*
 420              * "Default" operation - we have blocks on our own freelist
 421              * grab the first record and update the counters.
 422              */
 423             block = _S_bin[bin].first[thread_id];
 424
 425             _S_bin[bin].first[thread_id] = _S_bin[bin].first[thread_id]->next;
 426
 427 #ifdef __GTHREADS
 428             if (__gthread_active_p())
 429               {
 430                 _S_bin[bin].free[thread_id]--;
 431                 _S_bin[bin].used[thread_id]++;
 432               }
 433 #endif
 434           }
 435
 436         return static_cast<_Tp*>(static_cast<void*>((char*)block +
 437                                                     sizeof(block_record)));
 438       }
 439
 440       void
 441       deallocate(pointer __p, size_type __n)
 442       {
 443         /*
 444          * Requests larger than _S_max_bytes are handled by
 445          * operators new/delete directly
 446          */
 447         if (__n * sizeof(_Tp) > _S_max_bytes || _S_force_new)
 448           {
 449             ::operator delete(__p);
 450             return;
 451           }
 452
 453         /*
 454          * Round up to power of 2 and figure out which bin to use
 455          */
 456         size_t bin = _S_binmap[__n * sizeof(_Tp)];
 457
 458 #ifdef __GTHREADS
 459         size_t thread_id = _S_get_thread_id();
 460 #else
 461         size_t thread_id = 0;
 462 #endif
 463
 464         block_record* block = (block_record*)((char*)__p
 465                                              - sizeof(block_record));
 466
 467         /*
 468          * This block will always be at the back of a list and thus
 469          * we set its next pointer to NULL.
 470          */
 471         block->next = NULL;
 472
 473 #ifdef __GTHREADS
 474         if (__gthread_active_p())
 475           {
 476             /*
 477              * Calculate the number of records to remove from our freelist
 478              */
 479             int remove = _S_bin[bin].free[thread_id] -
 480                          (_S_bin[bin].used[thread_id] / _S_freelist_headroom);
 481
 482             /*
 483              * The calculation above will almost always tell us to
 484              * remove one or two records at a time, but this creates
 485              * too much contention when locking and therefore we
 486              * wait until the number of records is "high enough".
 487              */
 488             if (remove > (int)(100 * (_S_no_of_bins - bin)) &&
 489                 remove > (int)(_S_bin[bin].free[thread_id] /
 490                                _S_freelist_headroom))
 491               {
 492                 __gthread_mutex_lock(_S_bin[bin].mutex);
 493
 494                 while (remove > 0)
 495                   {
 496                     if (_S_bin[bin].first[0] == NULL)
 497                       _S_bin[bin].first[0] = _S_bin[bin].first[thread_id];
 498                     else
 499                       _S_bin[bin].last[0]->next = _S_bin[bin].first[thread_id];
 500
 501                     _S_bin[bin].last[0] = _S_bin[bin].first[thread_id];
 502
 503                     _S_bin[bin].first[thread_id] =
 504                       _S_bin[bin].first[thread_id]->next;
 505
 506                     _S_bin[bin].free[thread_id]--;
 507
 508                     remove--;
 509                   }
 510
 511                 _S_bin[bin].last[0]->next = NULL;
 512
 513                 __gthread_mutex_unlock(_S_bin[bin].mutex);
 514               }
 515
 516             /*
 517              * Return this block to our list and update
 518              * counters and owner id as needed
 519              */
 520             if (_S_bin[bin].first[thread_id] == NULL)
 521               _S_bin[bin].first[thread_id] = block;
 522             else
 523               _S_bin[bin].last[thread_id]->next = block;
 524
 525             _S_bin[bin].last[thread_id] = block;
 526
 527             _S_bin[bin].free[thread_id]++;
 528
 529             if (thread_id == block->thread_id)
 530               _S_bin[bin].used[thread_id]--;
 531             else
 532               {
 533                 _S_bin[bin].used[block->thread_id]--;
 534                 block->thread_id = thread_id;
 535               }
 536           }
 537         else
 538 #endif
 539           {
 540             /*
 541              * Single threaded application - return to global pool
 542              */
 543             if (_S_bin[bin].first[0] == NULL)
 544               _S_bin[bin].first[0] = block;
 545             else
 546               _S_bin[bin].last[0]->next = block;
 547
 548             _S_bin[bin].last[0] = block;
 549           }
 550       }
 551     };
 552
 553   template<typename _Tp>
 554     void
 555     __mt_alloc<_Tp>::
 556     _S_init()
 557     {
 558       if (getenv("GLIBCXX_FORCE_NEW"))
 559         {
 560           _S_force_new = true;
 561           _S_initialized = true;
 562
 563           /*
 564            * Since none of the code in allocate/deallocate ever will be
 565            * executed due to that the GLIBCXX_FORCE_NEW flag is set
 566            * there is no need to create the internal structures either.
 567            */
 568           return;
 569         }
 570
 571       /*
 572        * Calculate the number of bins required based on _S_max_bytes,
 573        * _S_no_of_bins is initialized to 1 below.
 574        */
 575       {
 576         size_t bin_t = 1;
 577         while (_S_max_bytes > bin_t)
 578           {
 579             bin_t = bin_t << 1;
 580             _S_no_of_bins++;
 581           }
 582       }
 583
 584       /*
 585        * Setup the bin map for quick lookup of the relevant bin
 586        */
 587       _S_binmap = (binmap_type*)
 588         ::operator new ((_S_max_bytes + 1) * sizeof(binmap_type));
 589
 590       if (!_S_binmap)
 591         std::__throw_bad_alloc();
 592
 593       binmap_type* bp_t = _S_binmap;
 594       binmap_type bin_max_t = 1;
 595       binmap_type bin_t = 0;
 596       for (binmap_type ct = 0; ct <= _S_max_bytes; ct++)
 597         {
 598           if (ct > bin_max_t)
 599             {
 600               bin_max_t <<= 1;
 601               bin_t++;
 602             }
 603           *bp_t++ = bin_t;
 604         }
 605
 606       /*
 607        * If __gthread_active_p() create and initialize the list of
 608        * free thread ids. Single threaded applications use thread id 0
 609        * directly and have no need for this.
 610        */
 611 #ifdef __GTHREADS
 612       if (__gthread_active_p())
 613         {
 614           _S_thread_freelist_first =
 615             static_cast<thread_record*>(::operator
 616               new(sizeof(thread_record) * _S_max_threads));
 617
 618           if (!_S_thread_freelist_first)
 619             std::__throw_bad_alloc();
 620
 621           /*
 622            * NOTE! The first assignable thread id is 1 since the global
 623            * pool uses id 0
 624            */
 625           size_t i;
 626           for (i = 1; i < _S_max_threads; i++)
 627             {
 628               _S_thread_freelist_first[i - 1].next =
 629                 &_S_thread_freelist_first[i];
 630
 631               _S_thread_freelist_first[i - 1].id = i;
 632             }
 633
 634           /*
 635            * Set last record
 636            */
 637           _S_thread_freelist_first[i - 1].next = NULL;
 638           _S_thread_freelist_first[i - 1].id = i;
 639
 640           /*
 641            * Initialize per thread key to hold pointer to
 642            * _S_thread_freelist
 643            */
 644           __gthread_key_create(&_S_thread_key, _S_thread_key_destr);
 645         }
 646 #endif
 647
 648       /*
 649        * Initialize _S_bin and its members
 650        */
 651       _S_bin = static_cast<bin_record*>(::operator
 652         new(sizeof(bin_record) * _S_no_of_bins));
 653
 654       if (!_S_bin)
 655         std::__throw_bad_alloc();
 656
 657       std::size_t __n = 1;
 658
 659 #ifdef __GTHREADS
 660       if (__gthread_active_p())
 661         __n = _S_max_threads + 1;
 662 #endif
 663
 664       for (size_t bin = 0; bin < _S_no_of_bins; bin++)
 665         {
 666           _S_bin[bin].first = static_cast<block_record**>(::operator
 667             new(sizeof(block_record*) * __n));
 668
 669           if (!_S_bin[bin].first)
 670             std::__throw_bad_alloc();
 671
 672           _S_bin[bin].last = static_cast<block_record**>(::operator
 673             new(sizeof(block_record*) * __n));
 674
 675           if (!_S_bin[bin].last)
 676             std::__throw_bad_alloc();
 677
 678 #ifdef __GTHREADS
 679           if (__gthread_active_p())
 680             {
 681               _S_bin[bin].free = static_cast<size_t*>(::operator
 682                 new(sizeof(size_t) * __n));
 683
 684               if (!_S_bin[bin].free)
 685                 std::__throw_bad_alloc();
 686
 687               _S_bin[bin].used = static_cast<size_t*>(::operator
 688                 new(sizeof(size_t) * __n));
 689
 690               if (!_S_bin[bin].used)
 691                 std::__throw_bad_alloc();
 692
 693               _S_bin[bin].mutex = static_cast<__gthread_mutex_t*>(::operator
 694                 new(sizeof(__gthread_mutex_t)));
 695
 696 #ifdef __GTHREAD_MUTEX_INIT
 697               {
 698                 // Do not copy a POSIX/gthr mutex once in use.
 699                 __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT;
 700                 *_S_bin[bin].mutex = __tmp;
 701               }
 702 #else
 703               { __GTHREAD_MUTEX_INIT_FUNCTION (_S_bin[bin].mutex); }
 704 #endif
 705             }
 706 #endif
 707
 708           for (size_t thread = 0; thread < __n; thread++)
 709             {
 710               _S_bin[bin].first[thread] = NULL;
 711               _S_bin[bin].last[thread] = NULL;
 712 #ifdef __GTHREADS
 713               if (__gthread_active_p())
 714                 {
 715                   _S_bin[bin].free[thread] = 0;
 716                   _S_bin[bin].used[thread] = 0;
 717                 }
 718 #endif
 719             }
 720         }
 721
 722       _S_initialized = true;
 723     }
 724
 725 #ifdef __GTHREADS
 726   template<typename _Tp>
 727     void
 728     __mt_alloc<_Tp>::
 729     _S_thread_key_destr(void* freelist_pos)
 730     {
 731       /*
 732        * Return this thread id record to front of thread_freelist
 733        */
 734       __gthread_mutex_lock(&_S_thread_freelist_mutex);
 735       ((thread_record*)freelist_pos)->next = _S_thread_freelist_first;
 736       _S_thread_freelist_first = (thread_record*)freelist_pos;
 737       __gthread_mutex_unlock(&_S_thread_freelist_mutex);
 738     }
 739
 740   template<typename _Tp>
 741     size_t
 742     __mt_alloc<_Tp>::
 743     _S_get_thread_id()
 744     {
 745       /*
 746        * If we have thread support and it's active we check the thread
 747        * key value and return it's id or if it's not set we take the
 748        * first record from _S_thread_freelist and sets the key and
 749        * returns it's id.
 750        */
 751       if (__gthread_active_p())
 752         {
 753           thread_record* freelist_pos;
 754
 755           if ((freelist_pos =
 756               (thread_record*)__gthread_getspecific(_S_thread_key)) == NULL)
 757             {
 758               /*
 759                * Since _S_max_threads must be larger than the
 760                * theoretical max number of threads of the OS the list
 761                * can never be empty.
 762                */
 763               __gthread_mutex_lock(&_S_thread_freelist_mutex);
 764               freelist_pos = _S_thread_freelist_first;
 765               _S_thread_freelist_first = _S_thread_freelist_first->next;
 766               __gthread_mutex_unlock(&_S_thread_freelist_mutex);
 767
 768               __gthread_setspecific(_S_thread_key, (void*)freelist_pos);
 769             }
 770
 771           return freelist_pos->id;
 772         }
 773
 774       /*
 775        * Otherwise (no thread support or inactive) all requests are
 776        * served from the global pool 0.
 777        */
 778       return 0;
 779     }
 780
 781   template<typename _Tp> __gthread_once_t
 782   __mt_alloc<_Tp>::_S_once_mt = __GTHREAD_ONCE_INIT;
 783 #endif
 784
 785   template<typename _Tp>
 786   bool volatile __mt_alloc<_Tp>::_S_initialized = false;
 787
 788   template<typename _Tp> bool
 789   __mt_alloc<_Tp>::_S_force_new = false;
 790
 791   template<typename _Tp> typename __mt_alloc<_Tp>::binmap_type*
 792   __mt_alloc<_Tp>::_S_binmap = NULL;
 793
 794   /*
 795    * Allocation requests (after round-up to power of 2) below this
 796    * value will be handled by the allocator. A raw new/ call
 797    * will be used for requests larger than this value.
 798    */
 799   template<typename _Tp> size_t
 800   __mt_alloc<_Tp>::_S_max_bytes = 128;
 801
 802   /*
 803    * In order to avoid fragmenting and minimize the number of new()
 804    * calls we always request new memory using this value. Based on
 805    * previous discussions on the libstdc++ mailing list we have
 806    * choosen the value below. See
 807    * http://gcc.gnu.org/ml/libstdc++/2001-07/msg00077.html
 808    */
 809   template<typename _Tp> size_t
 810   __mt_alloc<_Tp>::_S_chunk_size = 4096 - 4 * sizeof(void*);
 811
 812   /*
 813    * The maximum number of supported threads. Our Linux 2.4.18 reports
 814    * 4070 in /proc/sys/kernel/threads-max
 815    */
 816   template<typename _Tp> size_t
 817   __mt_alloc<_Tp>::_S_max_threads = 4096;
 818
 819   /*
 820    * Actual value calculated in _S_init()
 821    */
 822   template<typename _Tp> size_t
 823   __mt_alloc<_Tp>::_S_no_of_bins = 1;
 824
 825   /*
 826    * Each time a deallocation occurs in a threaded application we make
 827    * sure that there are no more than _S_freelist_headroom % of used
 828    * memory on the freelist. If the number of additional records is
 829    * more than _S_freelist_headroom % of the freelist, we move these
 830    * records back to the global pool.
 831    */
 832   template<typename _Tp> size_t
 833   __mt_alloc<_Tp>::_S_freelist_headroom = 10;
 834
 835   /*
 836    * Actual initialization in _S_init()
 837    */
 838 #ifdef __GTHREADS
 839   template<typename _Tp> typename __mt_alloc<_Tp>::thread_record*
 840   volatile __mt_alloc<_Tp>::_S_thread_freelist_first = NULL;
 841
 842   template<typename _Tp> __gthread_mutex_t
 843 #ifdef __GTHREAD_MUTEX_INIT
 844   __mt_alloc<_Tp>::_S_thread_freelist_mutex = __GTHREAD_MUTEX_INIT;
 845 #else
 846   // XXX
 847   __mt_alloc<_Tp>::_S_thread_freelist_mutex;
 848 #endif
 849
 850   /*
 851    * Actual initialization in _S_init()
 852    */
 853   template<typename _Tp> __gthread_key_t
 854   __mt_alloc<_Tp>::_S_thread_key;
 855 #endif
 856
 857   template<typename _Tp> typename __mt_alloc<_Tp>::bin_record*
 858   volatile __mt_alloc<_Tp>::_S_bin = NULL;
 859
 860   template<typename _Tp>
 861     inline bool
 862     operator==(const __mt_alloc<_Tp>&, const __mt_alloc<_Tp>&)
 863     { return true; }
 864
 865   template<typename _Tp>
 866     inline bool
 867     operator!=(const __mt_alloc<_Tp>&, const __mt_alloc<_Tp>&)
 868     { return false; }
 869 } // namespace __gnu_cxx
 870
 871 #endif