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