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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2007, 2008 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 terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 2, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /** @file ext/throw_allocator.h
  43  *  This file is a GNU extension to the Standard C++ Library.
  44  *
  45  *  Contains an exception-throwing allocator, useful for testing
  46  *  exception safety. In addition, allocation addresses are stored and
  47  *  sanity checked.
  48  */
  49
  50 #ifndef _THROW_ALLOCATOR_H
  51 #define _THROW_ALLOCATOR_H 1
  52
  53 #include <cmath>
  54 #include <ctime>
  55 #include <map>
  56 #include <set>
  57 #include <string>
  58 #include <ostream>
  59 #include <stdexcept>
  60 #include <utility>
  61 #include <tr1/random>
  62 #include <bits/functexcept.h>
  63 #include <bits/move.h>
  64
  65 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
  66
  67   class twister_rand_gen
  68   {
  69   private:
  70     std::tr1::mt19937 _M_generator;
  71
  72   public:
  73     twister_rand_gen(unsigned int s = static_cast<unsigned int>(std::time(0)));
  74
  75     void
  76     init(unsigned int);
  77
  78     double
  79     get_prob();
  80   };
  81
  82   /// Thown by throw_allocator.
  83   struct forced_exception_error : public std::exception
  84   { };
  85
  86   // Substitute for concurrence_error object in the case of -fno-exceptions.
  87   inline void
  88   __throw_forced_exception_error()
  89   {
  90 #if __EXCEPTIONS
  91     throw forced_exception_error();
  92 #else
  93     __builtin_abort();
  94 #endif
  95   }
  96
  97   /// Base class.
  98   class throw_allocator_base
  99   {
 100   public:
 101     void
 102     init(unsigned long seed);
 103
 104     static void
 105     set_throw_prob(double throw_prob);
 106
 107     static double
 108     get_throw_prob();
 109
 110     static void
 111     set_label(size_t l);
 112
 113     static bool
 114     empty();
 115
 116     struct group_throw_prob_adjustor
 117     {
 118       group_throw_prob_adjustor(size_t size) : _M_throw_prob_orig(_S_throw_prob)
 119       {
 120         _S_throw_prob =
 121           1 - std::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1)));
 122       }
 123
 124       ~group_throw_prob_adjustor()
 125       { _S_throw_prob = _M_throw_prob_orig; }
 126
 127     private:
 128       const double _M_throw_prob_orig;
 129     };
 130
 131     struct zero_throw_prob_adjustor
 132     {
 133       zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob)
 134       { _S_throw_prob = 0; }
 135
 136       ~zero_throw_prob_adjustor()
 137       { _S_throw_prob = _M_throw_prob_orig; }
 138
 139     private:
 140       const double _M_throw_prob_orig;
 141     };
 142
 143   protected:
 144     static void
 145     insert(void*, size_t);
 146
 147     static void
 148     erase(void*, size_t);
 149
 150     static void
 151     throw_conditionally();
 152
 153     // See if a particular address and size has been allocated by this
 154     // allocator.
 155     static void
 156     check_allocated(void*, size_t);
 157
 158     // See if a given label has been allocated by this allocator.
 159     static void
 160     check_allocated(size_t);
 161
 162   private:
 163     typedef std::pair<size_t, size_t>           alloc_data_type;
 164     typedef std::map<void*, alloc_data_type>    map_type;
 165     typedef map_type::value_type                entry_type;
 166     typedef map_type::const_iterator            const_iterator;
 167     typedef map_type::const_reference           const_reference;
 168
 169     friend std::ostream&
 170     operator<<(std::ostream&, const throw_allocator_base&);
 171
 172     static entry_type
 173     make_entry(void*, size_t);
 174
 175     static void
 176     print_to_string(std::string&);
 177
 178     static void
 179     print_to_string(std::string&, const_reference);
 180
 181     static twister_rand_gen     _S_g;
 182     static map_type             _S_map;
 183     static double               _S_throw_prob;
 184     static size_t               _S_label;
 185   };
 186
 187   /// Allocator class with logging and exception control.
 188   template<typename T>
 189     class throw_allocator : public throw_allocator_base
 190     {
 191     public:
 192       typedef size_t                            size_type;
 193       typedef ptrdiff_t                         difference_type;
 194       typedef T                                 value_type;
 195       typedef value_type*                       pointer;
 196       typedef const value_type*                 const_pointer;
 197       typedef value_type&                       reference;
 198       typedef const value_type&                 const_reference;
 199
 200
 201       template<typename U>
 202       struct rebind
 203       {
 204         typedef throw_allocator<U> other;
 205       };
 206
 207       throw_allocator() throw() { }
 208
 209       throw_allocator(const throw_allocator&) throw() { }
 210
 211       template<typename U>
 212       throw_allocator(const throw_allocator<U>&) throw() { }
 213
 214       ~throw_allocator() throw() { }
 215
 216       size_type
 217       max_size() const throw()
 218       { return std::allocator<value_type>().max_size(); }
 219
 220       pointer
 221       allocate(size_type __n, std::allocator<void>::const_pointer hint = 0)
 222       {
 223         if (__builtin_expect(__n > this->max_size(), false))
 224           std::__throw_bad_alloc();
 225
 226         throw_conditionally();
 227         value_type* const a = std::allocator<value_type>().allocate(__n, hint);
 228         insert(a, sizeof(value_type) * __n);
 229         return a;
 230       }
 231
 232       void
 233       construct(pointer __p, const T& val)
 234       { return std::allocator<value_type>().construct(__p, val); }
 235
 236 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 237       template<typename... _Args>
 238         void
 239         construct(pointer __p, _Args&&... __args)
 240         {
 241           return std::allocator<value_type>().
 242             construct(__p, std::forward<_Args>(__args)...);
 243         }
 244 #endif
 245
 246       void
 247       destroy(pointer __p)
 248       { std::allocator<value_type>().destroy(__p); }
 249
 250       void
 251       deallocate(pointer __p, size_type __n)
 252       {
 253         erase(__p, sizeof(value_type) * __n);
 254         std::allocator<value_type>().deallocate(__p, __n);
 255       }
 256
 257       void
 258       check_allocated(pointer __p, size_type __n)
 259       { throw_allocator_base::check_allocated(__p, sizeof(value_type) * __n); }
 260
 261       void
 262       check_allocated(size_type label)
 263       { throw_allocator_base::check_allocated(label); }
 264     };
 265
 266   template<typename T>
 267     inline bool
 268     operator==(const throw_allocator<T>&, const throw_allocator<T>&)
 269     { return true; }
 270
 271   template<typename T>
 272     inline bool
 273     operator!=(const throw_allocator<T>&, const throw_allocator<T>&)
 274     { return false; }
 275
 276   std::ostream&
 277   operator<<(std::ostream& os, const throw_allocator_base& alloc)
 278   {
 279     std::string error;
 280     throw_allocator_base::print_to_string(error);
 281     os << error;
 282     return os;
 283   }
 284
 285   // XXX Should be in .cc.
 286   twister_rand_gen::
 287   twister_rand_gen(unsigned int seed) : _M_generator(seed)  { }
 288
 289   void
 290   twister_rand_gen::
 291   init(unsigned int seed)
 292   { _M_generator.seed(seed); }
 293
 294   double
 295   twister_rand_gen::
 296   get_prob()
 297   {
 298     const double min = _M_generator.min();
 299     const double res = static_cast<const double>(_M_generator() - min);
 300     const double range = static_cast<const double>(_M_generator.max() - min);
 301     const double ret = res / range;
 302     _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1);
 303     return ret;
 304   }
 305
 306   twister_rand_gen throw_allocator_base::_S_g;
 307
 308   throw_allocator_base::map_type
 309   throw_allocator_base::_S_map;
 310
 311   double throw_allocator_base::_S_throw_prob;
 312
 313   size_t throw_allocator_base::_S_label = 0;
 314
 315   throw_allocator_base::entry_type
 316   throw_allocator_base::make_entry(void* p, size_t size)
 317   { return std::make_pair(p, alloc_data_type(_S_label, size)); }
 318
 319   void
 320   throw_allocator_base::init(unsigned long seed)
 321   { _S_g.init(seed); }
 322
 323   void
 324   throw_allocator_base::set_throw_prob(double throw_prob)
 325   { _S_throw_prob = throw_prob; }
 326
 327   double
 328   throw_allocator_base::get_throw_prob()
 329   { return _S_throw_prob; }
 330
 331   void
 332   throw_allocator_base::set_label(size_t l)
 333   { _S_label = l; }
 334
 335   void
 336   throw_allocator_base::insert(void* p, size_t size)
 337   {
 338     const_iterator found_it = _S_map.find(p);
 339     if (found_it != _S_map.end())
 340       {
 341         std::string error("throw_allocator_base::insert");
 342         error += "double insert!";
 343         error += '\n';
 344         print_to_string(error, make_entry(p, size));
 345         print_to_string(error, *found_it);
 346         std::__throw_logic_error(error.c_str());
 347       }
 348     _S_map.insert(make_entry(p, size));
 349   }
 350
 351   bool
 352   throw_allocator_base::empty()
 353   { return _S_map.empty(); }
 354
 355   void
 356   throw_allocator_base::erase(void* p, size_t size)
 357   {
 358     check_allocated(p, size);
 359     _S_map.erase(p);
 360   }
 361
 362   void
 363   throw_allocator_base::check_allocated(void* p, size_t size)
 364   {
 365     const_iterator found_it = _S_map.find(p);
 366     if (found_it == _S_map.end())
 367       {
 368         std::string error("throw_allocator_base::check_allocated by value ");
 369         error += "null erase!";
 370         error += '\n';
 371         print_to_string(error, make_entry(p, size));
 372         std::__throw_logic_error(error.c_str());
 373       }
 374
 375     if (found_it->second.second != size)
 376       {
 377         std::string error("throw_allocator_base::check_allocated by value ");
 378         error += "wrong-size erase!";
 379         error += '\n';
 380         print_to_string(error, make_entry(p, size));
 381         print_to_string(error, *found_it);
 382         std::__throw_logic_error(error.c_str());
 383       }
 384   }
 385
 386   void
 387   throw_allocator_base::check_allocated(size_t label)
 388   {
 389     std::string found;
 390     const_iterator it = _S_map.begin();
 391     while (it != _S_map.end())
 392       {
 393         if (it->second.first == label)
 394           {
 395             print_to_string(found, *it);
 396           }
 397         ++it;
 398       }
 399
 400     if (!found.empty())
 401       {
 402         std::string error("throw_allocator_base::check_allocated by label ");
 403         error += '\n';
 404         error += found;
 405         std::__throw_logic_error(error.c_str());
 406       }
 407   }
 408
 409   void
 410   throw_allocator_base::throw_conditionally()
 411   {
 412     if (_S_g.get_prob() < _S_throw_prob)
 413       __throw_forced_exception_error();
 414   }
 415
 416   void
 417   throw_allocator_base::print_to_string(std::string& s)
 418   {
 419     const_iterator begin = throw_allocator_base::_S_map.begin();
 420     const_iterator end = throw_allocator_base::_S_map.end();
 421     for (; begin != end; ++begin)
 422       print_to_string(s, *begin);
 423   }
 424
 425   void
 426   throw_allocator_base::print_to_string(std::string& s, const_reference ref)
 427   {
 428     char buf[40];
 429     const char tab('\t');
 430     s += "address: ";
 431     __builtin_sprintf(buf, "%p", ref.first);
 432     s += buf;
 433     s += tab;
 434     s += "label: ";
 435     unsigned long l = static_cast<unsigned long>(ref.second.first);
 436     __builtin_sprintf(buf, "%lu", l);
 437     s += buf;
 438     s += tab;
 439     s += "size: ";
 440     l = static_cast<unsigned long>(ref.second.second);
 441     __builtin_sprintf(buf, "%lu", l);
 442     s += buf;
 443     s += '\n';
 444   }
 445
 446 _GLIBCXX_END_NAMESPACE
 447
 448 #endif