1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2007, 2008, 2009 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27 // Permission to use, copy, modify, sell, and distribute this software 28 // is hereby granted without fee, provided that the above copyright 29 // notice appears in all copies, and that both that copyright notice 30 // and this permission notice appear in supporting documentation. None 31 // of the above authors, nor IBM Haifa Research Laboratories, make any 32 // representation about the suitability of this software for any 33 // purpose. It is provided "as is" without express or implied 34 // warranty. 35 36 /** @file ext/throw_allocator.h 37 * This file is a GNU extension to the Standard C++ Library. 38 * 39 * Contains an exception-throwing allocator, useful for testing 40 * exception safety. In addition, allocation addresses are stored and 41 * sanity checked. 42 */ 43 44 #ifndef _THROW_ALLOCATOR_H 45 #define _THROW_ALLOCATOR_H 1 46 47 #include <cmath> 48 #include <ctime> 49 #include <map> 50 #include <set> 51 #include <string> 52 #include <ostream> 53 #include <stdexcept> 54 #include <utility> 55 #include <tr1/random> 56 #include <bits/functexcept.h> 57 #include <bits/move.h> 58 59 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 60 61 class twister_rand_gen 62 { 63 private: 64 std::tr1::mt19937 _M_generator; 65 66 public: 67 twister_rand_gen(unsigned int s = static_cast<unsigned int>(std::time(0))); 68 69 void 70 init(unsigned int); 71 72 double 73 get_prob(); 74 }; 75 76 /** 77 * @brief Thown by throw_allocator. 78 * @ingroup exceptions 79 */ 80 struct forced_exception_error : public std::exception 81 { }; 82 83 // Substitute for concurrence_error object in the case of -fno-exceptions. 84 inline void 85 __throw_forced_exception_error() 86 { 87 #if __EXCEPTIONS 88 throw forced_exception_error(); 89 #else 90 __builtin_abort(); 91 #endif 92 } 93 94 /// Base class. 95 class throw_allocator_base 96 { 97 public: 98 void 99 init(unsigned long seed); 100 101 static void 102 set_throw_prob(double throw_prob); 103 104 static double 105 get_throw_prob(); 106 107 static void 108 set_label(size_t l); 109 110 static bool 111 empty(); 112 113 struct group_throw_prob_adjustor 114 { 115 group_throw_prob_adjustor(size_t size) : _M_throw_prob_orig(_S_throw_prob) 116 { 117 _S_throw_prob = 118 1 - std::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1))); 119 } 120 121 ~group_throw_prob_adjustor() 122 { _S_throw_prob = _M_throw_prob_orig; } 123 124 private: 125 const double _M_throw_prob_orig; 126 }; 127 128 struct zero_throw_prob_adjustor 129 { 130 zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob) 131 { _S_throw_prob = 0; } 132 133 ~zero_throw_prob_adjustor() 134 { _S_throw_prob = _M_throw_prob_orig; } 135 136 private: 137 const double _M_throw_prob_orig; 138 }; 139 140 protected: 141 static void 142 insert(void*, size_t); 143 144 static void 145 erase(void*, size_t); 146 147 static void 148 throw_conditionally(); 149 150 // See if a particular address and size has been allocated by this 151 // allocator. 152 static void 153 check_allocated(void*, size_t); 154 155 // See if a given label has been allocated by this allocator. 156 static void 157 check_allocated(size_t); 158 159 private: 160 typedef std::pair<size_t, size_t> alloc_data_type; 161 typedef std::map<void*, alloc_data_type> map_type; 162 typedef map_type::value_type entry_type; 163 typedef map_type::const_iterator const_iterator; 164 typedef map_type::const_reference const_reference; 165 166 friend std::ostream& 167 operator<<(std::ostream&, const throw_allocator_base&); 168 169 static entry_type 170 make_entry(void*, size_t); 171 172 static void 173 print_to_string(std::string&); 174 175 static void 176 print_to_string(std::string&, const_reference); 177 178 static twister_rand_gen _S_g; 179 static map_type _S_map; 180 static double _S_throw_prob; 181 static size_t _S_label; 182 }; 183 184 /** 185 * @brief Allocator class with logging and exception control. 186 * @ingroup allocators 187 */ 188 template<typename T> 189 class throw_allocator : public throw_allocator_base 190 { 191 public: 192 typedef size_t size_type; 193 typedef ptrdiff_t difference_type; 194 typedef T value_type; 195 typedef value_type* pointer; 196 typedef const value_type* const_pointer; 197 typedef value_type& reference; 198 typedef const value_type& const_reference; 199 200 201 template<typename U> 202 struct rebind 203 { 204 typedef throw_allocator<U> other; 205 }; 206 207 throw_allocator() throw() { } 208 209 throw_allocator(const throw_allocator&) throw() { } 210 211 template<typename U> 212 throw_allocator(const throw_allocator<U>&) throw() { } 213 214 ~throw_allocator() throw() { } 215 216 size_type 217 max_size() const throw() 218 { return std::allocator<value_type>().max_size(); } 219 220 pointer 221 allocate(size_type __n, std::allocator<void>::const_pointer hint = 0) 222 { 223 if (__builtin_expect(__n > this->max_size(), false)) 224 std::__throw_bad_alloc(); 225 226 throw_conditionally(); 227 value_type* const a = std::allocator<value_type>().allocate(__n, hint); 228 insert(a, sizeof(value_type) * __n); 229 return a; 230 } 231 232 void 233 construct(pointer __p, const T& val) 234 { return std::allocator<value_type>().construct(__p, val); } 235 236 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 237 template<typename... _Args> 238 void 239 construct(pointer __p, _Args&&... __args) 240 { 241 return std::allocator<value_type>(). 242 construct(__p, std::forward<_Args>(__args)...); 243 } 244 #endif 245 246 void 247 destroy(pointer __p) 248 { std::allocator<value_type>().destroy(__p); } 249 250 void 251 deallocate(pointer __p, size_type __n) 252 { 253 erase(__p, sizeof(value_type) * __n); 254 std::allocator<value_type>().deallocate(__p, __n); 255 } 256 257 void 258 check_allocated(pointer __p, size_type __n) 259 { throw_allocator_base::check_allocated(__p, sizeof(value_type) * __n); } 260 261 void 262 check_allocated(size_type label) 263 { throw_allocator_base::check_allocated(label); } 264 }; 265 266 template<typename T> 267 inline bool 268 operator==(const throw_allocator<T>&, const throw_allocator<T>&) 269 { return true; } 270 271 template<typename T> 272 inline bool 273 operator!=(const throw_allocator<T>&, const throw_allocator<T>&) 274 { return false; } 275 276 std::ostream& 277 operator<<(std::ostream& os, const throw_allocator_base& alloc) 278 { 279 std::string error; 280 throw_allocator_base::print_to_string(error); 281 os << error; 282 return os; 283 } 284 285 // XXX Should be in .cc. 286 twister_rand_gen:: 287 twister_rand_gen(unsigned int seed) : _M_generator(seed) { } 288 289 void 290 twister_rand_gen:: 291 init(unsigned int seed) 292 { _M_generator.seed(seed); } 293 294 double 295 twister_rand_gen:: 296 get_prob() 297 { 298 const double min = _M_generator.min(); 299 const double res = static_cast<const double>(_M_generator() - min); 300 const double range = static_cast<const double>(_M_generator.max() - min); 301 const double ret = res / range; 302 _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1); 303 return ret; 304 } 305 306 twister_rand_gen throw_allocator_base::_S_g; 307 308 throw_allocator_base::map_type 309 throw_allocator_base::_S_map; 310 311 double throw_allocator_base::_S_throw_prob; 312 313 size_t throw_allocator_base::_S_label = 0; 314 315 throw_allocator_base::entry_type 316 throw_allocator_base::make_entry(void* p, size_t size) 317 { return std::make_pair(p, alloc_data_type(_S_label, size)); } 318 319 void 320 throw_allocator_base::init(unsigned long seed) 321 { _S_g.init(seed); } 322 323 void 324 throw_allocator_base::set_throw_prob(double throw_prob) 325 { _S_throw_prob = throw_prob; } 326 327 double 328 throw_allocator_base::get_throw_prob() 329 { return _S_throw_prob; } 330 331 void 332 throw_allocator_base::set_label(size_t l) 333 { _S_label = l; } 334 335 void 336 throw_allocator_base::insert(void* p, size_t size) 337 { 338 const_iterator found_it = _S_map.find(p); 339 if (found_it != _S_map.end()) 340 { 341 std::string error("throw_allocator_base::insert"); 342 error += "double insert!"; 343 error += '\n'; 344 print_to_string(error, make_entry(p, size)); 345 print_to_string(error, *found_it); 346 std::__throw_logic_error(error.c_str()); 347 } 348 _S_map.insert(make_entry(p, size)); 349 } 350 351 bool 352 throw_allocator_base::empty() 353 { return _S_map.empty(); } 354 355 void 356 throw_allocator_base::erase(void* p, size_t size) 357 { 358 check_allocated(p, size); 359 _S_map.erase(p); 360 } 361 362 void 363 throw_allocator_base::check_allocated(void* p, size_t size) 364 { 365 const_iterator found_it = _S_map.find(p); 366 if (found_it == _S_map.end()) 367 { 368 std::string error("throw_allocator_base::check_allocated by value "); 369 error += "null erase!"; 370 error += '\n'; 371 print_to_string(error, make_entry(p, size)); 372 std::__throw_logic_error(error.c_str()); 373 } 374 375 if (found_it->second.second != size) 376 { 377 std::string error("throw_allocator_base::check_allocated by value "); 378 error += "wrong-size erase!"; 379 error += '\n'; 380 print_to_string(error, make_entry(p, size)); 381 print_to_string(error, *found_it); 382 std::__throw_logic_error(error.c_str()); 383 } 384 } 385 386 void 387 throw_allocator_base::check_allocated(size_t label) 388 { 389 std::string found; 390 const_iterator it = _S_map.begin(); 391 while (it != _S_map.end()) 392 { 393 if (it->second.first == label) 394 { 395 print_to_string(found, *it); 396 } 397 ++it; 398 } 399 400 if (!found.empty()) 401 { 402 std::string error("throw_allocator_base::check_allocated by label "); 403 error += '\n'; 404 error += found; 405 std::__throw_logic_error(error.c_str()); 406 } 407 } 408 409 void 410 throw_allocator_base::throw_conditionally() 411 { 412 if (_S_g.get_prob() < _S_throw_prob) 413 __throw_forced_exception_error(); 414 } 415 416 void 417 throw_allocator_base::print_to_string(std::string& s) 418 { 419 const_iterator begin = throw_allocator_base::_S_map.begin(); 420 const_iterator end = throw_allocator_base::_S_map.end(); 421 for (; begin != end; ++begin) 422 print_to_string(s, *begin); 423 } 424 425 void 426 throw_allocator_base::print_to_string(std::string& s, const_reference ref) 427 { 428 char buf[40]; 429 const char tab('\t'); 430 s += "address: "; 431 __builtin_sprintf(buf, "%p", ref.first); 432 s += buf; 433 s += tab; 434 s += "label: "; 435 unsigned long l = static_cast<unsigned long>(ref.second.first); 436 __builtin_sprintf(buf, "%lu", l); 437 s += buf; 438 s += tab; 439 s += "size: "; 440 l = static_cast<unsigned long>(ref.second.second); 441 __builtin_sprintf(buf, "%lu", l); 442 s += buf; 443 s += '\n'; 444 } 445 446 _GLIBCXX_END_NAMESPACE 447 448 #endif 449
