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
66namespace __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
784namespace 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