libstdc++
throw_allocator.h
Go to the documentation of this file.
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  */
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.
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:
163  typedef map_type::const_iterator const_iterator;
164  typedef map_type::const_reference const_reference;
165 
166  friend std::ostream&
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>
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  {
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