1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010 4// Free Software Foundation, Inc. 5// 6// This file is part of the GNU ISO C++ Library. This library is free 7// software; you can redistribute it and/or modify it under the terms 8// of the GNU General Public License as published by the Free Software 9// Foundation; either version 3, or (at your option) any later 10// version. 11 12// This library is distributed in the hope that it will be useful, but 13// WITHOUT ANY WARRANTY; without even the implied warranty of 14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15// General Public License for more details. 16 17// Under Section 7 of GPL version 3, you are granted additional 18// permissions described in the GCC Runtime Library Exception, version 19// 3.1, as published by the Free Software Foundation. 20 21// You should have received a copy of the GNU General Public License and 22// a copy of the GCC Runtime Library Exception along with this program; 23// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24// <http://www.gnu.org/licenses/>. 25 26// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 27 28// Permission to use, copy, modify, sell, and distribute this software 29// is hereby granted without fee, provided that the above copyright 30// notice appears in all copies, and that both that copyright notice 31// and this permission notice appear in supporting documentation. None 32// of the above authors, nor IBM Haifa Research Laboratories, make any 33// representation about the suitability of this software for any 34// purpose. It is provided "as is" without express or implied 35// warranty. 36 37/** @file ext/throw_allocator.h 38 * This file is a GNU extension to the Standard C++ Library. 39 * 40 * Contains two exception-generating types (throw_value, throw_allocator) 41 * intended to be used as value and allocator types while testing 42 * exception safety in templatized containers and algorithms. The 43 * allocator has additional log and debug features. The exception 44 * generated is of type forced_exception_error. 45 */ 46 47#ifndef _THROW_ALLOCATOR_H 48#define _THROW_ALLOCATOR_H 1 49 50#include <cmath> 51#include <ctime> 52#include <map> 53#include <string> 54#include <ostream> 55#include <stdexcept> 56#include <utility> 57#include <bits/functexcept.h> 58#include <bits/move.h> 59#ifdef __GXX_EXPERIMENTAL_CXX0X__ 60# include <functional> 61# include <random> 62#else 63# include <tr1/functional> 64# include <tr1/random> 65#endif 66 67_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 68 69 /** 70 * @brief Thown by exception safety machinery. 71 * @ingroup exceptions 72 */ 73 struct forced_error : public std::exception 74 { }; 75 76 // Substitute for forced_error object when -fno-exceptions. 77 inline void 78 __throw_forced_error() 79 { 80#if __EXCEPTIONS 81 throw forced_error(); 82#else 83 __builtin_abort(); 84#endif 85 } 86 87 88 /** 89 * @brief Base class for checking address and label information 90 * about allocations. Create a std::map between the allocated 91 * address (void*) and a datum for annotations, which are a pair of 92 * numbers corresponding to label and allocated size. 93 */ 94 struct annotate_base 95 { 96 annotate_base() 97 { 98 label(); 99 map(); 100 } 101 102 static void 103 set_label(size_t l) 104 { label() = l; } 105 106 static size_t 107 get_label() 108 { return label(); } 109 110 void 111 insert(void* p, size_t size) 112 { 113 if (p == NULL) 114 { 115 std::string error("annotate_base::insert null insert!\n"); 116 log_to_string(error, make_entry(p, size)); 117 std::__throw_logic_error(error.c_str()); 118 } 119 120 const_iterator found = map().find(p); 121 if (found != map().end()) 122 { 123 std::string error("annotate_base::insert double insert!\n"); 124 log_to_string(error, make_entry(p, size)); 125 log_to_string(error, *found); 126 std::__throw_logic_error(error.c_str()); 127 } 128 129 map().insert(make_entry(p, size)); 130 } 131 132 void 133 erase(void* p, size_t size) 134 { 135 check_allocated(p, size); 136 map().erase(p); 137 } 138 139 // See if a particular address and allocation size has been saved. 140 inline void 141 check_allocated(void* p, size_t size) 142 { 143 const_iterator found = map().find(p); 144 if (found == map().end()) 145 { 146 std::string error("annotate_base::check_allocated by value " 147 "null erase!\n"); 148 log_to_string(error, make_entry(p, size)); 149 std::__throw_logic_error(error.c_str()); 150 } 151 152 if (found->second.second != size) 153 { 154 std::string error("annotate_base::check_allocated by value " 155 "wrong-size erase!\n"); 156 log_to_string(error, make_entry(p, size)); 157 log_to_string(error, *found); 158 std::__throw_logic_error(error.c_str()); 159 } 160 } 161 162 // See if a given label has been allocated. 163 inline void 164 check_allocated(size_t label) 165 { 166 const_iterator beg = map().begin(); 167 const_iterator end = map().end(); 168 std::string found; 169 while (beg != end) 170 { 171 if (beg->second.first == label) 172 log_to_string(found, *beg); 173 ++beg; 174 } 175 176 if (!found.empty()) 177 { 178 std::string error("annotate_base::check_allocated by label\n"); 179 error += found; 180 std::__throw_logic_error(error.c_str()); 181 } 182 } 183 184 private: 185 typedef std::pair<size_t, size_t> data_type; 186 typedef std::map<void*, data_type> map_type; 187 typedef map_type::value_type entry_type; 188 typedef map_type::const_iterator const_iterator; 189 typedef map_type::const_reference const_reference; 190 191 friend std::ostream& 192 operator<<(std::ostream&, const annotate_base&); 193 194 entry_type 195 make_entry(void* p, size_t size) 196 { return std::make_pair(p, data_type(get_label(), size)); } 197 198 void 199 log_to_string(std::string& s, const_reference ref) const 200 { 201 char buf[40]; 202 const char tab('\t'); 203 s += "label: "; 204 unsigned long l = static_cast<unsigned long>(ref.second.first); 205 __builtin_sprintf(buf, "%lu", l); 206 s += buf; 207 s += tab; 208 s += "size: "; 209 l = static_cast<unsigned long>(ref.second.second); 210 __builtin_sprintf(buf, "%lu", l); 211 s += buf; 212 s += tab; 213 s += "address: "; 214 __builtin_sprintf(buf, "%p", ref.first); 215 s += buf; 216 s += '\n'; 217 } 218 219 static size_t& 220 label() 221 { 222 static size_t _S_label(std::numeric_limits<size_t>::max()); 223 return _S_label; 224 } 225 226 static map_type& 227 map() 228 { 229 static map_type _S_map; 230 return _S_map; 231 } 232 }; 233 234 inline std::ostream& 235 operator<<(std::ostream& os, const annotate_base& __b) 236 { 237 std::string error; 238 typedef annotate_base base_type; 239 base_type::const_iterator beg = __b.map().begin(); 240 base_type::const_iterator end = __b.map().end(); 241 for (; beg != end; ++beg) 242 __b.log_to_string(error, *beg); 243 return os << error; 244 } 245 246 247 /** 248 * @brief Base struct for condition policy. 249 * 250 * Requires a public member function with the signature 251 * void throw_conditionally() 252 */ 253 struct condition_base 254 { 255 virtual ~condition_base() { }; 256 }; 257 258 259 /** 260 * @brief Base class for incremental control and throw. 261 */ 262 struct limit_condition : public condition_base 263 { 264 // Scope-level adjustor objects: set limit for throw at the 265 // beginning of a scope block, and restores to previous limit when 266 // object is destroyed on exiting the block. 267 struct adjustor_base 268 { 269 private: 270 const size_t _M_orig; 271 272 public: 273 adjustor_base() : _M_orig(limit()) { } 274 275 virtual 276 ~adjustor_base() { set_limit(_M_orig); } 277 }; 278 279 /// Never enter the condition. 280 struct never_adjustor : public adjustor_base 281 { 282 never_adjustor() { set_limit(std::numeric_limits<size_t>::max()); } 283 }; 284 285 /// Always enter the condition. 286 struct always_adjustor : public adjustor_base 287 { 288 always_adjustor() { set_limit(count()); } 289 }; 290 291 /// Enter the nth condition. 292 struct limit_adjustor : public adjustor_base 293 { 294 limit_adjustor(const size_t __l) { set_limit(__l); } 295 }; 296 297 // Increment _S_count every time called. 298 // If _S_count matches the limit count, throw. 299 static void 300 throw_conditionally() 301 { 302 if (count() == limit()) 303 __throw_forced_error(); 304 ++count(); 305 } 306 307 static size_t& 308 count() 309 { 310 static size_t _S_count(0); 311 return _S_count; 312 } 313 314 static size_t& 315 limit() 316 { 317 static size_t _S_limit(std::numeric_limits<size_t>::max()); 318 return _S_limit; 319 } 320 321 // Zero the throw counter, set limit to argument. 322 static void 323 set_limit(const size_t __l) 324 { 325 limit() = __l; 326 count() = 0; 327 } 328 }; 329 330 331 /** 332 * @brief Base class for random probability control and throw. 333 */ 334 struct random_condition : public condition_base 335 { 336 // Scope-level adjustor objects: set probability for throw at the 337 // beginning of a scope block, and restores to previous 338 // probability when object is destroyed on exiting the block. 339 struct adjustor_base 340 { 341 private: 342 const double _M_orig; 343 344 public: 345 adjustor_base() : _M_orig(probability()) { } 346 347 virtual ~adjustor_base() 348 { set_probability(_M_orig); } 349 }; 350 351 /// Group condition. 352 struct group_adjustor : public adjustor_base 353 { 354 group_adjustor(size_t size) 355 { set_probability(1 - std::pow(double(1 - probability()), 356 double(0.5 / (size + 1)))); 357 } 358 }; 359 360 /// Never enter the condition. 361 struct never_adjustor : public adjustor_base 362 { 363 never_adjustor() { set_probability(0); } 364 }; 365 366 /// Always enter the condition. 367 struct always_adjustor : public adjustor_base 368 { 369 always_adjustor() { set_probability(1); } 370 }; 371 372 random_condition() 373 { 374 probability(); 375 engine(); 376 } 377 378 static void 379 set_probability(double __p) 380 { probability() = __p; } 381 382 static void 383 throw_conditionally() 384 { 385 if (generate() < probability()) 386 __throw_forced_error(); 387 } 388 389 void 390 seed(unsigned long __s) 391 { engine().seed(__s); } 392 393 private: 394#ifdef __GXX_EXPERIMENTAL_CXX0X__ 395 typedef std::uniform_real_distribution<double> distribution_type; 396 typedef std::mt19937 engine_type; 397#else 398 typedef std::tr1::uniform_real<double> distribution_type; 399 typedef std::tr1::mt19937 engine_type; 400#endif 401 402 static double 403 generate() 404 { 405#ifdef __GXX_EXPERIMENTAL_CXX0X__ 406 const distribution_type distribution(0, 1); 407 static auto generator = std::bind(distribution, engine()); 408#else 409 // Use variate_generator to get normalized results. 410 typedef std::tr1::variate_generator<engine_type, distribution_type> gen_t; 411 distribution_type distribution(0, 1); 412 static gen_t generator(engine(), distribution); 413#endif 414 415 double random = generator(); 416 if (random < distribution.min() || random > distribution.max()) 417 { 418 std::string __s("random_condition::generate"); 419 __s += "\n"; 420 __s += "random number generated is: "; 421 char buf[40]; 422 __builtin_sprintf(buf, "%f", random); 423 __s += buf; 424 std::__throw_out_of_range(__s.c_str()); 425 } 426 427 return random; 428 } 429 430 static double& 431 probability() 432 { 433 static double _S_p; 434 return _S_p; 435 } 436 437 static engine_type& 438 engine() 439 { 440 static engine_type _S_e; 441 return _S_e; 442 } 443 }; 444 445 446 /** 447 * @brief Class with exception generation control. Intended to be 448 * used as a value_type in templatized code. 449 * 450 * Note: Destructor not allowed to throw. 451 */ 452 template<typename _Cond> 453 struct throw_value_base : public _Cond 454 { 455 typedef _Cond condition_type; 456 457 using condition_type::throw_conditionally; 458 459 std::size_t _M_i; 460 461#ifndef _GLIBCXX_IS_AGGREGATE 462 throw_value_base() : _M_i(0) 463 { throw_conditionally(); } 464 465 throw_value_base(const throw_value_base& __v) : _M_i(__v._M_i) 466 { throw_conditionally(); } 467 468 explicit throw_value_base(const std::size_t __i) : _M_i(__i) 469 { throw_conditionally(); } 470#endif 471 472 throw_value_base& 473 operator=(const throw_value_base& __v) 474 { 475 throw_conditionally(); 476 _M_i = __v._M_i; 477 return *this; 478 } 479 480 throw_value_base& 481 operator++() 482 { 483 throw_conditionally(); 484 ++_M_i; 485 return *this; 486 } 487 }; 488 489 template<typename _Cond> 490 inline void 491 swap(throw_value_base<_Cond>& __a, throw_value_base<_Cond>& __b) 492 { 493 typedef throw_value_base<_Cond> throw_value; 494 throw_value::throw_conditionally(); 495 throw_value orig(__a); 496 __a = __b; 497 __b = orig; 498 } 499 500 // General instantiable types requirements. 501 template<typename _Cond> 502 inline bool 503 operator==(const throw_value_base<_Cond>& __a, 504 const throw_value_base<_Cond>& __b) 505 { 506 typedef throw_value_base<_Cond> throw_value; 507 throw_value::throw_conditionally(); 508 bool __ret = __a._M_i == __b._M_i; 509 return __ret; 510 } 511 512 template<typename _Cond> 513 inline bool 514 operator<(const throw_value_base<_Cond>& __a, 515 const throw_value_base<_Cond>& __b) 516 { 517 typedef throw_value_base<_Cond> throw_value; 518 throw_value::throw_conditionally(); 519 bool __ret = __a._M_i < __b._M_i; 520 return __ret; 521 } 522 523 // Numeric algorithms instantiable types requirements. 524 template<typename _Cond> 525 inline throw_value_base<_Cond> 526 operator+(const throw_value_base<_Cond>& __a, 527 const throw_value_base<_Cond>& __b) 528 { 529 typedef throw_value_base<_Cond> throw_value; 530 throw_value::throw_conditionally(); 531 throw_value __ret(__a._M_i + __b._M_i); 532 return __ret; 533 } 534 535 template<typename _Cond> 536 inline throw_value_base<_Cond> 537 operator-(const throw_value_base<_Cond>& __a, 538 const throw_value_base<_Cond>& __b) 539 { 540 typedef throw_value_base<_Cond> throw_value; 541 throw_value::throw_conditionally(); 542 throw_value __ret(__a._M_i - __b._M_i); 543 return __ret; 544 } 545 546 template<typename _Cond> 547 inline throw_value_base<_Cond> 548 operator*(const throw_value_base<_Cond>& __a, 549 const throw_value_base<_Cond>& __b) 550 { 551 typedef throw_value_base<_Cond> throw_value; 552 throw_value::throw_conditionally(); 553 throw_value __ret(__a._M_i * __b._M_i); 554 return __ret; 555 } 556 557 558 /// Type throwing via limit condition. 559 struct throw_value_limit : public throw_value_base<limit_condition> 560 { 561 typedef throw_value_base<limit_condition> base_type; 562 563#ifndef _GLIBCXX_IS_AGGREGATE 564 throw_value_limit() { } 565 566 throw_value_limit(const throw_value_limit& __other) 567 : base_type(__other._M_i) { } 568 569 explicit throw_value_limit(const std::size_t __i) : base_type(__i) { } 570#endif 571 }; 572 573 /// Type throwing via random condition. 574 struct throw_value_random : public throw_value_base<random_condition> 575 { 576 typedef throw_value_base<random_condition> base_type; 577 578#ifndef _GLIBCXX_IS_AGGREGATE 579 throw_value_random() { } 580 581 throw_value_random(const throw_value_random& __other) 582 : base_type(__other._M_i) { } 583 584 585 explicit throw_value_random(const std::size_t __i) : base_type(__i) { } 586#endif 587 }; 588 589 590 /** 591 * @brief Allocator class with logging and exception generation control. 592 * Intended to be used as an allocator_type in templatized code. 593 * @ingroup allocators 594 * 595 * Note: Deallocate not allowed to throw. 596 */ 597 template<typename _Tp, typename _Cond> 598 class throw_allocator_base 599 : public annotate_base, public _Cond 600 { 601 public: 602 typedef size_t size_type; 603 typedef ptrdiff_t difference_type; 604 typedef _Tp value_type; 605 typedef value_type* pointer; 606 typedef const value_type* const_pointer; 607 typedef value_type& reference; 608 typedef const value_type& const_reference; 609 610 private: 611 typedef _Cond condition_type; 612 613 std::allocator<value_type> _M_allocator; 614 615 using condition_type::throw_conditionally; 616 617 public: 618 size_type 619 max_size() const throw() 620 { return _M_allocator.max_size(); } 621 622 pointer 623 allocate(size_type __n, std::allocator<void>::const_pointer hint = 0) 624 { 625 if (__n > this->max_size()) 626 std::__throw_bad_alloc(); 627 628 throw_conditionally(); 629 pointer const a = _M_allocator.allocate(__n, hint); 630 insert(a, sizeof(value_type) * __n); 631 return a; 632 } 633 634 void 635 construct(pointer __p, const value_type& val) 636 { return _M_allocator.construct(__p, val); } 637 638#ifdef __GXX_EXPERIMENTAL_CXX0X__ 639 template<typename... _Args> 640 void 641 construct(pointer __p, _Args&&... __args) 642 { return _M_allocator.construct(__p, std::forward<_Args>(__args)...); } 643#endif 644 645 void 646 destroy(pointer __p) 647 { _M_allocator.destroy(__p); } 648 649 void 650 deallocate(pointer __p, size_type __n) 651 { 652 erase(__p, sizeof(value_type) * __n); 653 _M_allocator.deallocate(__p, __n); 654 } 655 656 void 657 check_allocated(pointer __p, size_type __n) 658 { 659 size_type __t = sizeof(value_type) * __n; 660 annotate_base::check_allocated(__p, __t); 661 } 662 663 void 664 check_allocated(size_type __n) 665 { annotate_base::check_allocated(__n); } 666 }; 667 668 template<typename _Tp, typename _Cond> 669 inline bool 670 operator==(const throw_allocator_base<_Tp, _Cond>&, 671 const throw_allocator_base<_Tp, _Cond>&) 672 { return true; } 673 674 template<typename _Tp, typename _Cond> 675 inline bool 676 operator!=(const throw_allocator_base<_Tp, _Cond>&, 677 const throw_allocator_base<_Tp, _Cond>&) 678 { return false; } 679 680 /// Allocator throwing via limit condition. 681 template<typename _Tp> 682 struct throw_allocator_limit 683 : public throw_allocator_base<_Tp, limit_condition> 684 { 685 template<typename _Tp1> 686 struct rebind 687 { typedef throw_allocator_limit<_Tp1> other; }; 688 689 throw_allocator_limit() throw() { } 690 691 throw_allocator_limit(const throw_allocator_limit&) throw() { } 692 693 template<typename _Tp1> 694 throw_allocator_limit(const throw_allocator_limit<_Tp1>&) throw() { } 695 696 ~throw_allocator_limit() throw() { } 697 }; 698 699 /// Allocator throwing via random condition. 700 template<typename _Tp> 701 struct throw_allocator_random 702 : public throw_allocator_base<_Tp, random_condition> 703 { 704 template<typename _Tp1> 705 struct rebind 706 { typedef throw_allocator_random<_Tp1> other; }; 707 708 throw_allocator_random() throw() { } 709 710 throw_allocator_random(const throw_allocator_random&) throw() { } 711 712 template<typename _Tp1> 713 throw_allocator_random(const throw_allocator_random<_Tp1>&) throw() { } 714 715 ~throw_allocator_random() throw() { } 716 }; 717 718_GLIBCXX_END_NAMESPACE 719 720#ifdef __GXX_EXPERIMENTAL_CXX0X__ 721 722# include <bits/functional_hash.h> 723 724namespace std 725{ 726 /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit. 727 template<> 728 struct hash<__gnu_cxx::throw_value_limit> 729 : public std::unary_function<__gnu_cxx::throw_value_limit, size_t> 730 { 731 size_t 732 operator()(const __gnu_cxx::throw_value_limit& __val) const 733 { 734 std::hash<std::size_t> h; 735 size_t __result = h(__val._M_i); 736 return __result; 737 } 738 }; 739 740 /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit. 741 template<> 742 struct hash<__gnu_cxx::throw_value_random> 743 : public std::unary_function<__gnu_cxx::throw_value_random, size_t> 744 { 745 size_t 746 operator()(const __gnu_cxx::throw_value_random& __val) const 747 { 748 std::hash<std::size_t> h; 749 size_t __result = h(__val._M_i); 750 return __result; 751 } 752 }; 753} // end namespace std 754#endif 755 756#endif 757