throw_allocator.h

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

Generated on Thu Jul 23 21:16:28 2009 for libstdc++ by  doxygen 1.5.8