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

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