throw_allocator.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2007 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/throw_allocator.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 #ifndef _THROW_ALLOCATOR_H
00051 #define _THROW_ALLOCATOR_H 1
00052 
00053 #include <cmath>
00054 #include <ctime>
00055 #include <map>
00056 #include <set>
00057 #include <string>
00058 #include <ostream>
00059 #include <stdexcept>
00060 #include <utility>
00061 #include <tr1/random>
00062 #include <bits/functexcept.h>
00063 #include <bits/stl_move.h>
00064 
00065 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00066 
00067   class twister_rand_gen
00068   {
00069   public:
00070     twister_rand_gen(unsigned int seed = 
00071              static_cast<unsigned int>(std::time(0)));
00072     
00073     void
00074     init(unsigned int);
00075     
00076     double
00077     get_prob();
00078     
00079   private:
00080     std::tr1::mt19937 _M_generator;
00081   };
00082 
00083   /// Thown by throw_allocator.
00084   struct forced_exception_error : public std::exception
00085   { };
00086 
00087   // Substitute for concurrence_error object in the case of -fno-exceptions.
00088   inline void
00089   __throw_forced_exception_error()
00090   {
00091 #if __EXCEPTIONS
00092     throw forced_exception_error();
00093 #else
00094     __builtin_abort();
00095 #endif
00096   }
00097 
00098   /// Base class.
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 - std::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   /// Allocator class with logging and exception control.
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 __n, std::allocator<void>::const_pointer hint = 0)
00224       {
00225     if (__builtin_expect(__n > this->max_size(), false))
00226       std::__throw_bad_alloc();
00227 
00228     throw_conditionally();
00229     value_type* const a = std::allocator<value_type>().allocate(__n, hint);
00230     insert(a, sizeof(value_type) * __n);
00231     return a;
00232       }
00233 
00234       void
00235       construct(pointer __p, const T& val)
00236       { return std::allocator<value_type>().construct(__p, val); }
00237 
00238 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00239       template<typename... _Args>
00240         void
00241         construct(pointer __p, _Args&&... __args)
00242     { 
00243       return std::allocator<value_type>().
00244         construct(__p, std::forward<_Args>(__args)...);
00245     }
00246 #endif
00247 
00248       void
00249       destroy(pointer __p)
00250       { std::allocator<value_type>().destroy(__p); }
00251 
00252       void
00253       deallocate(pointer __p, size_type __n)
00254       {
00255     erase(__p, sizeof(value_type) * __n);
00256     std::allocator<value_type>().deallocate(__p, __n);
00257       }
00258 
00259       void
00260       check_allocated(pointer __p, size_type __n)
00261       { throw_allocator_base::check_allocated(__p, sizeof(value_type) * __n); }
00262 
00263       void
00264       check_allocated(size_type label)
00265       { throw_allocator_base::check_allocated(label); }
00266     };
00267 
00268   template<typename T>
00269     inline bool
00270     operator==(const throw_allocator<T>&, const throw_allocator<T>&)
00271     { return true; }
00272 
00273   template<typename T>
00274     inline bool
00275     operator!=(const throw_allocator<T>&, const throw_allocator<T>&)
00276     { return false; }
00277 
00278   std::ostream& 
00279   operator<<(std::ostream& os, const throw_allocator_base& alloc)
00280   {
00281     std::string error;
00282     throw_allocator_base::print_to_string(error);
00283     os << error;
00284     return os;
00285   }
00286 
00287   // XXX Should be in .cc.
00288   twister_rand_gen::
00289   twister_rand_gen(unsigned int seed) : _M_generator(seed)  { }
00290 
00291   void
00292   twister_rand_gen::
00293   init(unsigned int seed)
00294   { _M_generator.seed(seed); }
00295 
00296   double
00297   twister_rand_gen::
00298   get_prob()
00299   {
00300     const double eng_min = _M_generator.min();
00301     const double eng_range =
00302       static_cast<const double>(_M_generator.max() - eng_min);
00303 
00304     const double eng_res =
00305       static_cast<const double>(_M_generator() - eng_min);
00306 
00307     const double ret = eng_res / eng_range;
00308     _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1);
00309     return ret;
00310   }
00311 
00312   twister_rand_gen throw_allocator_base::_S_g;
00313 
00314   throw_allocator_base::map_type 
00315   throw_allocator_base::_S_map;
00316 
00317   double throw_allocator_base::_S_throw_prob;
00318 
00319   size_t throw_allocator_base::_S_label = 0;
00320 
00321   throw_allocator_base::entry_type
00322   throw_allocator_base::make_entry(void* p, size_t size)
00323   { return std::make_pair(p, alloc_data_type(_S_label, size)); }
00324 
00325   void
00326   throw_allocator_base::init(unsigned long seed)
00327   { _S_g.init(seed); }
00328 
00329   void
00330   throw_allocator_base::set_throw_prob(double throw_prob)
00331   { _S_throw_prob = throw_prob; }
00332 
00333   double
00334   throw_allocator_base::get_throw_prob()
00335   { return _S_throw_prob; }
00336 
00337   void
00338   throw_allocator_base::set_label(size_t l)
00339   { _S_label = l; }
00340 
00341   void
00342   throw_allocator_base::insert(void* p, size_t size)
00343   {
00344     const_iterator found_it = _S_map.find(p);
00345     if (found_it != _S_map.end())
00346       {
00347     std::string error("throw_allocator_base::insert");
00348     error += "double insert!";
00349     error += '\n';
00350     print_to_string(error, make_entry(p, size));
00351     print_to_string(error, *found_it);
00352     std::__throw_logic_error(error.c_str());
00353       }
00354     _S_map.insert(make_entry(p, size));
00355   }
00356 
00357   bool
00358   throw_allocator_base::empty()
00359   { return _S_map.empty(); }
00360 
00361   void
00362   throw_allocator_base::erase(void* p, size_t size)
00363   {
00364     check_allocated(p, size);
00365     _S_map.erase(p);
00366   }
00367 
00368   void
00369   throw_allocator_base::check_allocated(void* p, size_t size)
00370   {
00371     const_iterator found_it = _S_map.find(p);
00372     if (found_it == _S_map.end())
00373       {
00374     std::string error("throw_allocator_base::check_allocated by value ");
00375     error += "null erase!";
00376     error += '\n';
00377     print_to_string(error, make_entry(p, size));
00378     std::__throw_logic_error(error.c_str());
00379       }
00380 
00381     if (found_it->second.second != size)
00382       {
00383     std::string error("throw_allocator_base::check_allocated by value ");
00384     error += "wrong-size erase!";
00385     error += '\n';
00386     print_to_string(error, make_entry(p, size));
00387     print_to_string(error, *found_it);
00388     std::__throw_logic_error(error.c_str());
00389       }
00390   }
00391 
00392   void
00393   throw_allocator_base::check_allocated(size_t label)
00394   {
00395     std::string found;
00396     const_iterator it = _S_map.begin();
00397     while (it != _S_map.end())
00398       {
00399     if (it->second.first == label)
00400       print_to_string(found, *it);
00401     ++it;
00402       }
00403 
00404     if (!found.empty())
00405       {
00406     std::string error("throw_allocator_base::check_allocated by label ");
00407     error += '\n';
00408     error += found;
00409     std::__throw_logic_error(error.c_str());
00410       } 
00411   }
00412 
00413   void
00414   throw_allocator_base::throw_conditionally()
00415   {
00416     if (_S_g.get_prob() < _S_throw_prob)
00417       __throw_forced_exception_error();
00418   }
00419 
00420   void
00421   throw_allocator_base::print_to_string(std::string& s)
00422   {
00423     const_iterator begin = throw_allocator_base::_S_map.begin();
00424     const_iterator end = throw_allocator_base::_S_map.end();
00425     for (; begin != end; ++begin)
00426       print_to_string(s, *begin);
00427   }
00428 
00429   void
00430   throw_allocator_base::print_to_string(std::string& s, const_reference ref)
00431   {
00432     char buf[40];
00433     const char tab('\t');
00434     s += "address: ";
00435     __builtin_sprintf(buf, "%p", ref.first);
00436     s += buf;
00437     s += tab;
00438     s += "label: ";
00439     unsigned long l = static_cast<unsigned long>(ref.second.first);
00440     __builtin_sprintf(buf, "%lu", l);
00441     s += buf;
00442     s += tab;
00443     s += "size: ";
00444     l = static_cast<unsigned long>(ref.second.second);
00445     __builtin_sprintf(buf, "%lu", l);
00446     s += buf;
00447     s += '\n';
00448   }
00449 
00450 _GLIBCXX_END_NAMESPACE
00451 
00452 #endif 

Generated on Sat Oct 25 05:09:17 2008 for libstdc++ by  doxygen 1.5.6