# throw_allocator.h

Go to the documentation of this file.

    00001 // -*- C++ -*-
    00002
    00003 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
    00004 //
    00005 // This file is part of the GNU ISO C++ Library.  This library is free
    00006 // software; you can redistribute it and/or modify it under the terms
    00007 // of the GNU General Public License as published by the Free Software
    00008 // Foundation; either version 2, or (at your option) any later
    00009 // version.
    00010
    00011 // This library is distributed in the hope that it will be useful, but
    00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
    00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    00014 // General Public License for more details.
    00015
    00016 // You should have received a copy of the GNU General Public License
    00017 // along with this library; see the file COPYING.  If not, write to
    00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
    00019 // MA 02111-1307, USA.
    00020
    00021 // As a special exception, you may use this file as part of a free
    00022 // software library without restriction.  Specifically, if other files
    00023 // instantiate templates or use macros or inline functions from this
    00024 // file, or you compile this file and link it with other files to
    00025 // produce an executable, this file does not by itself cause the
    00026 // resulting executable to be covered by the GNU General Public
    00027 // License.  This exception does not however invalidate any other
    00028 // reasons why the executable file might be covered by the GNU General
    00029 // Public License.
    00030
    00031 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
    00032
    00033 // Permission to use, copy, modify, sell, and distribute this software
    00034 // is hereby granted without fee, provided that the above copyright
    00035 // notice appears in all copies, and that both that copyright notice
    00036 // and this permission notice appear in supporting documentation. None
    00037 // of the above authors, nor IBM Haifa Research Laboratories, make any
    00038 // representation about the suitability of this software for any
    00039 // purpose. It is provided "as is" without express or implied
    00040 // warranty.
    00041
    00042 /** @file ext/vstring.h
    00043  *  This file is a GNU extension to the Standard C++ Library.
    00044  *
    00045  *  Contains an exception-throwing allocator, useful for testing
    00046  *  exception safety. In addition, allocation addresses are stored and
    00047  *  sanity checked.
    00048  */
    00049
    00050 /**
    00051  * @file throw_allocator.h
    00052  */
    00053
    00054 #ifndef _THROW_ALLOCATOR_H
    00055 #define _THROW_ALLOCATOR_H 1
    00056
    00057 #include <cmath>
    00058 #include <map>
    00059 #include <set>
    00060 #include <string>
    00061 #include <ostream>
    00062 #include <stdexcept>
    00063 #include <utility>
    00064 #include <tr1/random>
    00065 #include <bits/functexcept.h>
    00066
    00067 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
    00068
    00069   class twister_rand_gen
    00070   {
    00071   public:
    00072     twister_rand_gen(unsigned int seed =
    00073              static_cast<unsigned int>(std::time(0)));
    00074
    00075     void
    00076     init(unsigned int);
    00077
    00078     double
    00079     get_prob();
    00080
    00081   private:
    00082     std::tr1::mt19937 _M_generator;
    00083   };
    00084
    00085   struct forced_exception_error : public std::exception
    00086   { };
    00087
    00088   // Substitute for concurrence_error object in the case of -fno-exceptions.
    00089   inline void
    00090   __throw_forced_exception_error()
    00091   {
    00092 #if __EXCEPTIONS
    00093     throw forced_exception_error();
    00094 #else
    00095     __builtin_abort();
    00096 #endif
    00097   }
    00098
    00099   class throw_allocator_base
    00100   {
    00101   public:
    00102     void
    00103     init(unsigned long seed);
    00104
    00105     static void
    00106     set_throw_prob(double throw_prob);
    00107
    00108     static double
    00109     get_throw_prob();
    00110
    00111     static void
    00112     set_label(size_t l);
    00113
    00114     static bool
    00115     empty();
    00116
    00117     struct group_throw_prob_adjustor
    00118     {
    00119       group_throw_prob_adjustor(size_t size)
    00120       : _M_throw_prob_orig(_S_throw_prob)
    00121       {
    00122     _S_throw_prob =
    00123       1 - ::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1)));
    00124       }
    00125
    00126       ~group_throw_prob_adjustor()
    00127       { _S_throw_prob = _M_throw_prob_orig; }
    00128
    00129     private:
    00130       const double _M_throw_prob_orig;
    00131     };
    00132
    00133     struct zero_throw_prob_adjustor
    00134     {
    00135       zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob)
    00136       { _S_throw_prob = 0; }
    00137
    00138       ~zero_throw_prob_adjustor()
    00139       { _S_throw_prob = _M_throw_prob_orig; }
    00140
    00141     private:
    00142       const double _M_throw_prob_orig;
    00143     };
    00144
    00145   protected:
    00146     static void
    00147     insert(void*, size_t);
    00148
    00149     static void
    00150     erase(void*, size_t);
    00151
    00152     static void
    00153     throw_conditionally();
    00154
    00155     // See if a particular address and size has been allocated by this
    00156     // allocator.
    00157     static void
    00158     check_allocated(void*, size_t);
    00159
    00160     // See if a given label has been allocated by this allocator.
    00161     static void
    00162     check_allocated(size_t);
    00163
    00164   private:
    00165     typedef std::pair<size_t, size_t>       alloc_data_type;
    00166     typedef std::map<void*, alloc_data_type>    map_type;
    00167     typedef map_type::value_type        entry_type;
    00168     typedef map_type::const_iterator        const_iterator;
    00169     typedef map_type::const_reference       const_reference;
    00170
    00171     friend std::ostream&
    00172     operator<<(std::ostream&, const throw_allocator_base&);
    00173
    00174     static entry_type
    00175     make_entry(void*, size_t);
    00176
    00177     static void
    00178     print_to_string(std::string&);
    00179
    00180     static void
    00181     print_to_string(std::string&, const_reference);
    00182
    00183     static twister_rand_gen     _S_g;
    00184     static map_type         _S_map;
    00185     static double       _S_throw_prob;
    00186     static size_t       _S_label;
    00187   };
    00188
    00189
    00190   template<typename T>
    00191     class throw_allocator : public throw_allocator_base
    00192     {
    00193     public:
    00194       typedef size_t                size_type;
    00195       typedef ptrdiff_t             difference_type;
    00196       typedef T                 value_type;
    00197       typedef value_type*           pointer;
    00198       typedef const value_type*         const_pointer;
    00199       typedef value_type&           reference;
    00200       typedef const value_type&         const_reference;
    00201
    00202
    00203       template<typename U>
    00204       struct rebind
    00205       {
    00206         typedef throw_allocator<U> other;
    00207       };
    00208
    00209       throw_allocator() throw() { }
    00210
    00211       throw_allocator(const throw_allocator&) throw() { }
    00212
    00213       template<typename U>
    00214       throw_allocator(const throw_allocator<U>&) throw() { }
    00215
    00216       ~throw_allocator() throw() { }
    00217
    00218       size_type
    00219       max_size() const throw()
    00220       { return std::allocator<value_type>().max_size(); }
    00221
    00222       pointer
    00223       allocate(size_type num, std::allocator<void>::const_pointer hint = 0)
    00224       {
    00225     throw_conditionally();
    00226     value_type* const a = std::allocator<value_type>().allocate(num, hint);
    00227     insert(a, sizeof(value_type) * num);
    00228     return a;
    00229       }
    00230
    00231       void
    00232       construct(pointer p, const T& val)
    00233       { return std::allocator<value_type>().construct(p, val); }
    00234
    00235       void
    00236       destroy(pointer p)
    00237       { std::allocator<value_type>().destroy(p); }
    00238
    00239       void
    00240       deallocate(pointer p, size_type num)
    00241       {
    00242     erase(p, sizeof(value_type) * num);
    00243     std::allocator<value_type>().deallocate(p, num);
    00244       }
    00245
    00246       void
    00247       check_allocated(pointer p, size_type num)
    00248       { throw_allocator_base::check_allocated(p, sizeof(value_type) * num); }
    00249
    00250       void
    00251       check_allocated(size_type label)
    00252       { throw_allocator_base::check_allocated(label); }
    00253     };
    00254
    00255   template<typename T>
    00256     inline bool
    00257     operator==(const throw_allocator<T>&, const throw_allocator<T>&)
    00258     { return true; }
    00259
    00260   template<typename T>
    00261     inline bool
    00262     operator!=(const throw_allocator<T>&, const throw_allocator<T>&)
    00263     { return false; }
    00264
    00265   std::ostream&
    00266   operator<<(std::ostream& os, const throw_allocator_base& alloc)
    00267   {
    00268     std::string error;
    00269     throw_allocator_base::print_to_string(error);
    00270     os << error;
    00271     return os;
    00272   }
    00273
    00274   // XXX Should be in .cc.
    00275   twister_rand_gen::
    00276   twister_rand_gen(unsigned int seed) : _M_generator(seed)  { }
    00277
    00278   void
    00279   twister_rand_gen::
    00280   init(unsigned int seed)
    00281   { _M_generator.seed(seed); }
    00282
    00283   double
    00284   twister_rand_gen::
    00285   get_prob()
    00286   {
    00287     const double eng_min = _M_generator.min();
    00288     const double eng_range =
    00289       static_cast<const double>(_M_generator.max() - eng_min);
    00290
    00291     const double eng_res =
    00292       static_cast<const double>(_M_generator() - eng_min);
    00293
    00294     const double ret = eng_res / eng_range;
    00295     _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1);
    00296     return ret;
    00297   }
    00298
    00299   twister_rand_gen throw_allocator_base::_S_g;
    00300
    00301   throw_allocator_base::map_type
    00302   throw_allocator_base::_S_map;
    00303
    00304   double throw_allocator_base::_S_throw_prob;
    00305
    00306   size_t throw_allocator_base::_S_label = 0;
    00307
    00308   throw_allocator_base::entry_type
    00309   throw_allocator_base::make_entry(void* p, size_t size)
    00310   { return std::make_pair(p, alloc_data_type(_S_label, size)); }
    00311
    00312   void
    00313   throw_allocator_base::init(unsigned long seed)
    00314   { _S_g.init(seed); }
    00315
    00316   void
    00317   throw_allocator_base::set_throw_prob(double throw_prob)
    00318   { _S_throw_prob = throw_prob; }
    00319
    00320   double
    00321   throw_allocator_base::get_throw_prob()
    00322   { return _S_throw_prob; }
    00323
    00324   void
    00325   throw_allocator_base::set_label(size_t l)
    00326   { _S_label = l; }
    00327
    00328   void
    00329   throw_allocator_base::insert(void* p, size_t size)
    00330   {
    00331     const_iterator found_it = _S_map.find(p);
    00332     if (found_it != _S_map.end())
    00333       {
    00334     std::string error("throw_allocator_base::insert");
    00335     error += "double insert!";
    00336     error += '\n';
    00337     print_to_string(error, make_entry(p, size));
    00338     print_to_string(error, *found_it);
    00339     std::__throw_logic_error(error.c_str());
    00340       }
    00341     _S_map.insert(make_entry(p, size));
    00342   }
    00343
    00344   bool
    00345   throw_allocator_base::empty()
    00346   { return _S_map.empty(); }
    00347
    00348   void
    00349   throw_allocator_base::erase(void* p, size_t size)
    00350   {
    00351     check_allocated(p, size);
    00352     _S_map.erase(p);
    00353   }
    00354
    00355   void
    00356   throw_allocator_base::check_allocated(void* p, size_t size)
    00357   {
    00358     const_iterator found_it = _S_map.find(p);
    00359     if (found_it == _S_map.end())
    00360       {
    00361     std::string error("throw_allocator_base::check_allocated by value ");
    00362     error += "null erase!";
    00363     error += '\n';
    00364     print_to_string(error, make_entry(p, size));
    00365     std::__throw_logic_error(error.c_str());
    00366       }
    00367
    00368     if (found_it->second.second != size)
    00369       {
    00370     std::string error("throw_allocator_base::check_allocated by value ");
    00371     error += "wrong-size erase!";
    00372     error += '\n';
    00373     print_to_string(error, make_entry(p, size));
    00374     print_to_string(error, *found_it);
    00375     std::__throw_logic_error(error.c_str());
    00376       }
    00377   }
    00378
    00379   void
    00380   throw_allocator_base::check_allocated(size_t label)
    00381   {
    00382     std::string found;
    00383     const_iterator it = _S_map.begin();
    00384     while (it != _S_map.end())
    00385       {
    00386     if (it->second.first == label)
    00387       print_to_string(found, *it);
    00388     ++it;
    00389       }
    00390
    00391     if (!found.empty())
    00392       {
    00393     std::string error("throw_allocator_base::check_allocated by label ");
    00394     error += '\n';
    00395     error += found;
    00396     std::__throw_logic_error(error.c_str());
    00397       }
    00398   }
    00399
    00400   void
    00401   throw_allocator_base::throw_conditionally()
    00402   {
    00403     if (_S_g.get_prob() < _S_throw_prob)
    00404       __throw_forced_exception_error();
    00405   }
    00406
    00407   void
    00408   throw_allocator_base::print_to_string(std::string& s)
    00409   {
    00410     const_iterator begin = throw_allocator_base::_S_map.begin();
    00411     const_iterator end = throw_allocator_base::_S_map.end();
    00412     for (; begin != end; ++begin)
    00413       print_to_string(s, *begin);
    00414   }
    00415
    00416   void
    00417   throw_allocator_base::print_to_string(std::string& s, const_reference ref)
    00418   {
    00419     char buf[40];
    00420     const char tab('\t');
    00421     s += "address: ";
    00422     sprintf(buf, "%p", ref.first);
    00423     s += buf;
    00424     s += tab;
    00425     s += "label: ";
    00426     sprintf(buf, "%u", ref.second.first);
    00427     s += buf;
    00428     s += tab;
    00429     s += "size: ";
    00430     sprintf(buf, "%u", ref.second.second);
    00431     s += buf;
    00432     s += '\n';
    00433   }
    00434
    00435 _GLIBCXX_END_NAMESPACE
    00436
    00437 #endif