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