1 // -*- C++ -*-
2
3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
20
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
29 // Public License.
30
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32
33 // Permission to use, copy, modify, sell, and distribute this software
34 // is hereby granted without fee, provided that the above copyright
35 // notice appears in all copies, and that both that copyright notice
36 // and this permission notice appear in supporting documentation. None
37 // of the above authors, nor IBM Haifa Research Laboratories, make any
38 // representation about the suitability of this software for any
39 // purpose. It is provided "as is" without express or implied
40 // warranty.
41
42 /** @file ext/vstring.h
43 * This file is a GNU extension to the Standard C++ Library.
44 *
45 * Contains an exception-throwing allocator, useful for testing
46 * exception safety. In addition, allocation addresses are stored and
47 * sanity checked.
48 */
49
50 /**
51 * @file throw_allocator.h
52 */
53
54 #ifndef _THROW_ALLOCATOR_H
55 #define _THROW_ALLOCATOR_H 1
56
57 #include <cmath>
58 #include <map>
59 #include <set>
60 #include <string>
61 #include <ostream>
62 #include <stdexcept>
63 #include <utility>
64 #include <tr1/random>
65 #include <bits/functexcept.h>
66
_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)67 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
68
69 class twister_rand_gen
70 {
71 public:
72 twister_rand_gen(unsigned int seed =
73 static_cast<unsigned int>(std::time(0)));
74
75 void
76 init(unsigned int);
77
78 double
79 get_prob();
80
81 private:
82 std::tr1::mt19937 _M_generator;
83 };
84
85 struct forced_exception_error : public std::exception
86 { };
87
88 // Substitute for concurrence_error object in the case of -fno-exceptions.
89 inline void
__throw_forced_exception_error()90 __throw_forced_exception_error()
91 {
92 #if __EXCEPTIONS
93 throw forced_exception_error();
94 #else
95 __builtin_abort();
96 #endif
97 }
98
99 class throw_allocator_base
100 {
101 public:
102 void
103 init(unsigned long seed);
104
105 static void
106 set_throw_prob(double throw_prob);
107
108 static double
109 get_throw_prob();
110
111 static void
112 set_label(size_t l);
113
114 static bool
115 empty();
116
117 struct group_throw_prob_adjustor
118 {
group_throw_prob_adjustorgroup_throw_prob_adjustor119 group_throw_prob_adjustor(size_t size)
120 : _M_throw_prob_orig(_S_throw_prob)
121 {
122 _S_throw_prob =
123 1 - ::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1)));
124 }
125
~group_throw_prob_adjustorgroup_throw_prob_adjustor126 ~group_throw_prob_adjustor()
127 { _S_throw_prob = _M_throw_prob_orig; }
128
129 private:
130 const double _M_throw_prob_orig;
131 };
132
133 struct zero_throw_prob_adjustor
134 {
zero_throw_prob_adjustorzero_throw_prob_adjustor135 zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob)
136 { _S_throw_prob = 0; }
137
~zero_throw_prob_adjustorzero_throw_prob_adjustor138 ~zero_throw_prob_adjustor()
139 { _S_throw_prob = _M_throw_prob_orig; }
140
141 private:
142 const double _M_throw_prob_orig;
143 };
144
145 protected:
146 static void
147 insert(void*, size_t);
148
149 static void
150 erase(void*, size_t);
151
152 static void
153 throw_conditionally();
154
155 // See if a particular address and size has been allocated by this
156 // allocator.
157 static void
158 check_allocated(void*, size_t);
159
160 // See if a given label has been allocated by this allocator.
161 static void
162 check_allocated(size_t);
163
164 private:
165 typedef std::pair<size_t, size_t> alloc_data_type;
166 typedef std::map<void*, alloc_data_type> map_type;
167 typedef map_type::value_type entry_type;
168 typedef map_type::const_iterator const_iterator;
169 typedef map_type::const_reference const_reference;
170
171 friend std::ostream&
172 operator<<(std::ostream&, const throw_allocator_base&);
173
174 static entry_type
175 make_entry(void*, size_t);
176
177 static void
178 print_to_string(std::string&);
179
180 static void
181 print_to_string(std::string&, const_reference);
182
183 static twister_rand_gen _S_g;
184 static map_type _S_map;
185 static double _S_throw_prob;
186 static size_t _S_label;
187 };
188
189
190 template<typename T>
191 class throw_allocator : public throw_allocator_base
192 {
193 public:
194 typedef size_t size_type;
195 typedef ptrdiff_t difference_type;
196 typedef T value_type;
197 typedef value_type* pointer;
198 typedef const value_type* const_pointer;
199 typedef value_type& reference;
200 typedef const value_type& const_reference;
201
202
203 template<typename U>
204 struct rebind
205 {
206 typedef throw_allocator<U> other;
207 };
208
throw()209 throw_allocator() throw() { }
210
throw()211 throw_allocator(const throw_allocator&) throw() { }
212
213 template<typename U>
throw_allocator(const throw_allocator<U> &)214 throw_allocator(const throw_allocator<U>&) throw() { }
215
throw()216 ~throw_allocator() throw() { }
217
218 size_type
max_size()219 max_size() const throw()
220 { return std::allocator<value_type>().max_size(); }
221
222 pointer
223 allocate(size_type num, std::allocator<void>::const_pointer hint = 0)
224 {
225 throw_conditionally();
226 value_type* const a = std::allocator<value_type>().allocate(num, hint);
227 insert(a, sizeof(value_type) * num);
228 return a;
229 }
230
231 void
construct(pointer p,const T & val)232 construct(pointer p, const T& val)
233 { return std::allocator<value_type>().construct(p, val); }
234
235 void
destroy(pointer p)236 destroy(pointer p)
237 { std::allocator<value_type>().destroy(p); }
238
239 void
deallocate(pointer p,size_type num)240 deallocate(pointer p, size_type num)
241 {
242 erase(p, sizeof(value_type) * num);
243 std::allocator<value_type>().deallocate(p, num);
244 }
245
246 void
check_allocated(pointer p,size_type num)247 check_allocated(pointer p, size_type num)
248 { throw_allocator_base::check_allocated(p, sizeof(value_type) * num); }
249
250 void
check_allocated(size_type label)251 check_allocated(size_type label)
252 { throw_allocator_base::check_allocated(label); }
253 };
254
255 template<typename T>
256 inline bool
257 operator==(const throw_allocator<T>&, const throw_allocator<T>&)
258 { return true; }
259
260 template<typename T>
261 inline bool
262 operator!=(const throw_allocator<T>&, const throw_allocator<T>&)
263 { return false; }
264
265 std::ostream&
266 operator<<(std::ostream& os, const throw_allocator_base& alloc)
267 {
268 std::string error;
269 throw_allocator_base::print_to_string(error);
270 os << error;
271 return os;
272 }
273
274 // XXX Should be in .cc.
275 twister_rand_gen::
twister_rand_gen(unsigned int seed)276 twister_rand_gen(unsigned int seed) : _M_generator(seed) { }
277
278 void
279 twister_rand_gen::
init(unsigned int seed)280 init(unsigned int seed)
281 { _M_generator.seed(seed); }
282
283 double
284 twister_rand_gen::
get_prob()285 get_prob()
286 {
287 const double eng_min = _M_generator.min();
288 const double eng_range =
289 static_cast<const double>(_M_generator.max() - eng_min);
290
291 const double eng_res =
292 static_cast<const double>(_M_generator() - eng_min);
293
294 const double ret = eng_res / eng_range;
295 _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1);
296 return ret;
297 }
298
299 twister_rand_gen throw_allocator_base::_S_g;
300
301 throw_allocator_base::map_type
302 throw_allocator_base::_S_map;
303
304 double throw_allocator_base::_S_throw_prob;
305
306 size_t throw_allocator_base::_S_label = 0;
307
308 throw_allocator_base::entry_type
make_entry(void * p,size_t size)309 throw_allocator_base::make_entry(void* p, size_t size)
310 { return std::make_pair(p, alloc_data_type(_S_label, size)); }
311
312 void
init(unsigned long seed)313 throw_allocator_base::init(unsigned long seed)
314 { _S_g.init(seed); }
315
316 void
set_throw_prob(double throw_prob)317 throw_allocator_base::set_throw_prob(double throw_prob)
318 { _S_throw_prob = throw_prob; }
319
320 double
get_throw_prob()321 throw_allocator_base::get_throw_prob()
322 { return _S_throw_prob; }
323
324 void
set_label(size_t l)325 throw_allocator_base::set_label(size_t l)
326 { _S_label = l; }
327
328 void
insert(void * p,size_t size)329 throw_allocator_base::insert(void* p, size_t size)
330 {
331 const_iterator found_it = _S_map.find(p);
332 if (found_it != _S_map.end())
333 {
334 std::string error("throw_allocator_base::insert");
335 error += "double insert!";
336 error += '\n';
337 print_to_string(error, make_entry(p, size));
338 print_to_string(error, *found_it);
339 std::__throw_logic_error(error.c_str());
340 }
341 _S_map.insert(make_entry(p, size));
342 }
343
344 bool
empty()345 throw_allocator_base::empty()
346 { return _S_map.empty(); }
347
348 void
erase(void * p,size_t size)349 throw_allocator_base::erase(void* p, size_t size)
350 {
351 check_allocated(p, size);
352 _S_map.erase(p);
353 }
354
355 void
check_allocated(void * p,size_t size)356 throw_allocator_base::check_allocated(void* p, size_t size)
357 {
358 const_iterator found_it = _S_map.find(p);
359 if (found_it == _S_map.end())
360 {
361 std::string error("throw_allocator_base::check_allocated by value ");
362 error += "null erase!";
363 error += '\n';
364 print_to_string(error, make_entry(p, size));
365 std::__throw_logic_error(error.c_str());
366 }
367
368 if (found_it->second.second != size)
369 {
370 std::string error("throw_allocator_base::check_allocated by value ");
371 error += "wrong-size erase!";
372 error += '\n';
373 print_to_string(error, make_entry(p, size));
374 print_to_string(error, *found_it);
375 std::__throw_logic_error(error.c_str());
376 }
377 }
378
379 void
check_allocated(size_t label)380 throw_allocator_base::check_allocated(size_t label)
381 {
382 std::string found;
383 const_iterator it = _S_map.begin();
384 while (it != _S_map.end())
385 {
386 if (it->second.first == label)
387 print_to_string(found, *it);
388 ++it;
389 }
390
391 if (!found.empty())
392 {
393 std::string error("throw_allocator_base::check_allocated by label ");
394 error += '\n';
395 error += found;
396 std::__throw_logic_error(error.c_str());
397 }
398 }
399
400 void
throw_conditionally()401 throw_allocator_base::throw_conditionally()
402 {
403 if (_S_g.get_prob() < _S_throw_prob)
404 __throw_forced_exception_error();
405 }
406
407 void
print_to_string(std::string & s)408 throw_allocator_base::print_to_string(std::string& s)
409 {
410 const_iterator begin = throw_allocator_base::_S_map.begin();
411 const_iterator end = throw_allocator_base::_S_map.end();
412 for (; begin != end; ++begin)
413 print_to_string(s, *begin);
414 }
415
416 void
print_to_string(std::string & s,const_reference ref)417 throw_allocator_base::print_to_string(std::string& s, const_reference ref)
418 {
419 char buf[40];
420 const char tab('\t');
421 s += "address: ";
422 snprintf(buf, sizeof buf, "%p", ref.first);
423 s += buf;
424 s += tab;
425 s += "label: ";
426 snprintf(buf, sizeof buf, "%u", ref.second.first);
427 s += buf;
428 s += tab;
429 s += "size: ";
430 snprintf(buf, sizeof buf, "%u", ref.second.second);
431 s += buf;
432 s += '\n';
433 }
434
435 _GLIBCXX_END_NAMESPACE
436
437 #endif
438