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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2007 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/vstring.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 /**
  51  * @file throw_allocator.h
  52  */
  53
  54 #ifndef _THROW_ALLOCATOR_H
  55 #define _THROW_ALLOCATOR_H 1
  56
  57 #include <cmath>
  58 #include <ctime>
  59 #include <map>
  60 #include <set>
  61 #include <string>
  62 #include <ostream>
  63 #include <stdexcept>
  64 #include <utility>
  65 #include <tr1/random>
  66
  67 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
  68
  69   class twister_rand_gen
  70   {
  71   public:
  72     twister_rand_gen(unsigned int seed =
  73                      static_cast<unsigned int>(std::time(0)));
  74
  75     void
  76     init(unsigned int);
  77
  78     double
  79     get_prob();
  80
  81   private:
  82     std::tr1::mt19937 _M_generator;
  83   };
  84
  85
  86   struct forced_exception_error : public std::exception
  87   { };
  88
  89   class throw_allocator_base
  90   {
  91   public:
  92     void
  93     init(unsigned long seed);
  94
  95     static void
  96     set_throw_prob(double throw_prob);
  97
  98     static double
  99     get_throw_prob();
 100
 101     static void
 102     set_label(size_t l);
 103
 104     static bool
 105     empty();
 106
 107     struct group_throw_prob_adjustor
 108     {
 109       group_throw_prob_adjustor(size_t size)
 110       : _M_throw_prob_orig(_S_throw_prob)
 111       {
 112         _S_throw_prob =
 113           1 - std::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1)));
 114       }
 115
 116       ~group_throw_prob_adjustor()
 117       { _S_throw_prob = _M_throw_prob_orig; }
 118
 119     private:
 120       const double _M_throw_prob_orig;
 121     };
 122
 123     struct zero_throw_prob_adjustor
 124     {
 125       zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob)
 126       { _S_throw_prob = 0; }
 127
 128       ~zero_throw_prob_adjustor()
 129       { _S_throw_prob = _M_throw_prob_orig; }
 130
 131     private:
 132       const double _M_throw_prob_orig;
 133     };
 134
 135   protected:
 136     static void
 137     insert(void*, size_t);
 138
 139     static void
 140     erase(void*, size_t);
 141
 142     static void
 143     throw_conditionally();
 144
 145     // See if a particular address and size has been allocated by this
 146     // allocator.
 147     static void
 148     check_allocated(void*, size_t);
 149
 150     // See if a given label has been allocated by this allocator.
 151     static void
 152     check_allocated(size_t);
 153
 154   private:
 155     typedef std::pair<size_t, size_t>           alloc_data_type;
 156     typedef std::map<void*, alloc_data_type>    map_type;
 157     typedef map_type::value_type                entry_type;
 158     typedef map_type::const_iterator            const_iterator;
 159     typedef map_type::const_reference           const_reference;
 160
 161     friend std::ostream&
 162     operator<<(std::ostream&, const throw_allocator_base&);
 163
 164     static entry_type
 165     make_entry(void*, size_t);
 166
 167     static void
 168     print_to_string(std::string&);
 169
 170     static void
 171     print_to_string(std::string&, const_reference);
 172
 173     static twister_rand_gen     _S_g;
 174     static map_type             _S_map;
 175     static double               _S_throw_prob;
 176     static size_t               _S_label;
 177   };
 178
 179
 180   template<typename T>
 181     class throw_allocator : public throw_allocator_base
 182     {
 183     public:
 184       typedef size_t                            size_type;
 185       typedef ptrdiff_t                         difference_type;
 186       typedef T                                 value_type;
 187       typedef value_type*                       pointer;
 188       typedef const value_type*                 const_pointer;
 189       typedef value_type&                       reference;
 190       typedef const value_type&                 const_reference;
 191
 192
 193       template<typename U>
 194       struct rebind
 195       {
 196         typedef throw_allocator<U> other;
 197       };
 198
 199       throw_allocator() throw() { }
 200
 201       throw_allocator(const throw_allocator&) throw() { }
 202
 203       template<typename U>
 204       throw_allocator(const throw_allocator<U>&) throw() { }
 205
 206       ~throw_allocator() throw() { }
 207
 208       size_type
 209       max_size() const throw()
 210       { return std::allocator<value_type>().max_size(); }
 211
 212       pointer
 213       allocate(size_type __n, std::allocator<void>::const_pointer hint = 0)
 214       {
 215         if (__builtin_expect(__n > this->max_size(), false))
 216           std::__throw_bad_alloc();
 217
 218         throw_conditionally();
 219         value_type* const a = std::allocator<value_type>().allocate(__n, hint);
 220         insert(a, sizeof(value_type) * __n);
 221         return a;
 222       }
 223
 224       void
 225       construct(pointer __p, const T& val)
 226       { return std::allocator<value_type>().construct(__p, val); }
 227
 228       void
 229       destroy(pointer __p)
 230       { std::allocator<value_type>().destroy(__p); }
 231
 232       void
 233       deallocate(pointer __p, size_type __n)
 234       {
 235         erase(__p, sizeof(value_type) * __n);
 236         std::allocator<value_type>().deallocate(__p, __n);
 237       }
 238
 239       void
 240       check_allocated(pointer __p, size_type __n)
 241       { throw_allocator_base::check_allocated(__p, sizeof(value_type) * __n); }
 242
 243       void
 244       check_allocated(size_type label)
 245       { throw_allocator_base::check_allocated(label); }
 246     };
 247
 248   template<typename T>
 249     inline bool
 250     operator==(const throw_allocator<T>&, const throw_allocator<T>&)
 251     { return true; }
 252
 253   template<typename T>
 254     inline bool
 255     operator!=(const throw_allocator<T>&, const throw_allocator<T>&)
 256     { return false; }
 257
 258   std::ostream&
 259   operator<<(std::ostream& os, const throw_allocator_base& alloc)
 260   {
 261     std::string error;
 262     throw_allocator_base::print_to_string(error);
 263     os << error;
 264     return os;
 265   }
 266
 267   // XXX Should be in .cc.
 268   twister_rand_gen::
 269   twister_rand_gen(unsigned int seed) : _M_generator(seed)  { }
 270
 271   void
 272   twister_rand_gen::
 273   init(unsigned int seed)
 274   { _M_generator.seed(seed); }
 275
 276   double
 277   twister_rand_gen::
 278   get_prob()
 279   {
 280     const double eng_min = _M_generator.min();
 281     const double eng_range =
 282       static_cast<const double>(_M_generator.max() - eng_min);
 283
 284     const double eng_res =
 285       static_cast<const double>(_M_generator() - eng_min);
 286
 287     const double ret = eng_res / eng_range;
 288     _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1);
 289     return ret;
 290   }
 291
 292   twister_rand_gen throw_allocator_base::_S_g;
 293
 294   throw_allocator_base::map_type
 295   throw_allocator_base::_S_map;
 296
 297   double throw_allocator_base::_S_throw_prob;
 298
 299   size_t throw_allocator_base::_S_label = 0;
 300
 301   throw_allocator_base::entry_type
 302   throw_allocator_base::make_entry(void* p, size_t size)
 303   { return std::make_pair(p, alloc_data_type(_S_label, size)); }
 304
 305   void
 306   throw_allocator_base::init(unsigned long seed)
 307   { _S_g.init(seed); }
 308
 309   void
 310   throw_allocator_base::set_throw_prob(double throw_prob)
 311   { _S_throw_prob = throw_prob; }
 312
 313   double
 314   throw_allocator_base::get_throw_prob()
 315   { return _S_throw_prob; }
 316
 317   void
 318   throw_allocator_base::set_label(size_t l)
 319   { _S_label = l; }
 320
 321   void
 322   throw_allocator_base::insert(void* p, size_t size)
 323   {
 324     const_iterator found_it = _S_map.find(p);
 325     if (found_it != _S_map.end())
 326       {
 327         std::string error("throw_allocator_base::insert");
 328         error += "double insert!";
 329         error += '\n';
 330         print_to_string(error, make_entry(p, size));
 331         print_to_string(error, *found_it);
 332         throw std::logic_error(error);
 333       }
 334     _S_map.insert(make_entry(p, size));
 335   }
 336
 337   bool
 338   throw_allocator_base::empty()
 339   { return _S_map.empty(); }
 340
 341   void
 342   throw_allocator_base::erase(void* p, size_t size)
 343   {
 344     check_allocated(p, size);
 345     _S_map.erase(p);
 346   }
 347
 348   void
 349   throw_allocator_base::check_allocated(void* p, size_t size)
 350   {
 351     const_iterator found_it = _S_map.find(p);
 352     if (found_it == _S_map.end())
 353       {
 354         std::string error("throw_allocator_base::check_allocated by value ");
 355         error += "null erase!";
 356         error += '\n';
 357         print_to_string(error, make_entry(p, size));
 358         throw std::logic_error(error);
 359       }
 360
 361     if (found_it->second.second != size)
 362       {
 363         std::string error("throw_allocator_base::check_allocated by value ");
 364         error += "wrong-size erase!";
 365         error += '\n';
 366         print_to_string(error, make_entry(p, size));
 367         print_to_string(error, *found_it);
 368         throw std::logic_error(error);
 369       }
 370   }
 371
 372   void
 373   throw_allocator_base::check_allocated(size_t label)
 374   {
 375     std::string found;
 376     const_iterator it = _S_map.begin();
 377     while (it != _S_map.end())
 378       {
 379         if (it->second.first == label)
 380           print_to_string(found, *it);
 381         ++it;
 382       }
 383
 384     if (!found.empty())
 385       {
 386         std::string error("throw_allocator_base::check_allocated by label ");
 387         error += '\n';
 388         error += found;
 389         throw std::logic_error(error);
 390       }
 391   }
 392
 393   void
 394   throw_allocator_base::throw_conditionally()
 395   {
 396     if (_S_g.get_prob() < _S_throw_prob)
 397       throw forced_exception_error();
 398   }
 399
 400   void
 401   throw_allocator_base::print_to_string(std::string& s)
 402   {
 403     const_iterator begin = throw_allocator_base::_S_map.begin();
 404     const_iterator end = throw_allocator_base::_S_map.end();
 405     for (; begin != end; ++begin)
 406       print_to_string(s, *begin);
 407   }
 408
 409   void
 410   throw_allocator_base::print_to_string(std::string& s, const_reference ref)
 411   {
 412     char buf[40];
 413     const char tab('\t');
 414     s += "address: ";
 415     sprintf(buf, "%p", ref.first);
 416     s += buf;
 417     s += tab;
 418     s += "label: ";
 419     sprintf(buf, "%u", ref.second.first);
 420     s += buf;
 421     s += tab;
 422     s += "size: ";
 423     sprintf(buf, "%u", ref.second.second);
 424     s += buf;
 425     s += '\n';
 426   }
 427
 428 _GLIBCXX_END_NAMESPACE
 429
 430 #endif