libstdc++
|
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