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 66 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 67 68 class twister_rand_gen 69 { 70 public: 71 twister_rand_gen(unsigned int seed = 72 static_cast<unsigned int>(std::time(0))); 73 74 void 75 init(unsigned int); 76 77 double 78 get_prob(); 79 80 private: 81 std::tr1::mt19937 _M_generator; 82 }; 83 84 85 struct forced_exception_error : public std::exception 86 { }; 87 88 class throw_allocator_base 89 { 90 public: 91 void 92 init(unsigned long seed); 93 94 static void 95 set_throw_prob(double throw_prob); 96 97 static double 98 get_throw_prob(); 99 100 static void 101 set_label(size_t l); 102 103 static bool 104 empty(); 105 106 struct group_throw_prob_adjustor 107 { 108 group_throw_prob_adjustor(size_t size) 109 : _M_throw_prob_orig(_S_throw_prob) 110 { 111 _S_throw_prob = 112 1 - ::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1))); 113 } 114 115 ~group_throw_prob_adjustor() 116 { _S_throw_prob = _M_throw_prob_orig; } 117 118 private: 119 const double _M_throw_prob_orig; 120 }; 121 122 struct zero_throw_prob_adjustor 123 { 124 zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob) 125 { _S_throw_prob = 0; } 126 127 ~zero_throw_prob_adjustor() 128 { _S_throw_prob = _M_throw_prob_orig; } 129 130 private: 131 const double _M_throw_prob_orig; 132 }; 133 134 protected: 135 static void 136 insert(void*, size_t); 137 138 static void 139 erase(void*, size_t); 140 141 static void 142 throw_conditionally(); 143 144 // See if a particular address and size has been allocated by this 145 // allocator. 146 static void 147 check_allocated(void*, size_t); 148 149 // See if a given label has been allocated by this allocator. 150 static void 151 check_allocated(size_t); 152 153 private: 154 typedef std::pair<size_t, size_t> alloc_data_type; 155 typedef std::map<void*, alloc_data_type> map_type; 156 typedef map_type::value_type entry_type; 157 typedef map_type::const_iterator const_iterator; 158 typedef map_type::const_reference const_reference; 159 160 friend std::ostream& 161 operator<<(std::ostream&, const throw_allocator_base&); 162 163 static entry_type 164 make_entry(void*, size_t); 165 166 static void 167 print_to_string(std::string&); 168 169 static void 170 print_to_string(std::string&, const_reference); 171 172 static twister_rand_gen _S_g; 173 static map_type _S_map; 174 static double _S_throw_prob; 175 static size_t _S_label; 176 }; 177 178 179 template<typename T> 180 class throw_allocator : public throw_allocator_base 181 { 182 public: 183 typedef size_t size_type; 184 typedef ptrdiff_t difference_type; 185 typedef T value_type; 186 typedef value_type* pointer; 187 typedef const value_type* const_pointer; 188 typedef value_type& reference; 189 typedef const value_type& const_reference; 190 191 192 template<typename U> 193 struct rebind 194 { 195 typedef throw_allocator<U> other; 196 }; 197 198 throw_allocator() throw() { } 199 200 throw_allocator(const throw_allocator&) throw() { } 201 202 template<typename U> 203 throw_allocator(const throw_allocator<U>&) throw() { } 204 205 ~throw_allocator() throw() { } 206 207 size_type 208 max_size() const throw() 209 { return std::allocator<value_type>().max_size(); } 210 211 pointer 212 allocate(size_type num, std::allocator<void>::const_pointer hint = 0) 213 { 214 throw_conditionally(); 215 value_type* const a = std::allocator<value_type>().allocate(num, hint); 216 insert(a, sizeof(value_type) * num); 217 return a; 218 } 219 220 void 221 construct(pointer p, const T& val) 222 { return std::allocator<value_type>().construct(p, val); } 223 224 void 225 destroy(pointer p) 226 { std::allocator<value_type>().destroy(p); } 227 228 void 229 deallocate(pointer p, size_type num) 230 { 231 erase(p, sizeof(value_type) * num); 232 std::allocator<value_type>().deallocate(p, num); 233 } 234 235 void 236 check_allocated(pointer p, size_type num) 237 { throw_allocator_base::check_allocated(p, sizeof(value_type) * num); } 238 239 void 240 check_allocated(size_type label) 241 { throw_allocator_base::check_allocated(label); } 242 }; 243 244 template<typename T> 245 inline bool 246 operator==(const throw_allocator<T>&, const throw_allocator<T>&) 247 { return true; } 248 249 template<typename T> 250 inline bool 251 operator!=(const throw_allocator<T>&, const throw_allocator<T>&) 252 { return false; } 253 254 std::ostream& 255 operator<<(std::ostream& os, const throw_allocator_base& alloc) 256 { 257 std::string error; 258 throw_allocator_base::print_to_string(error); 259 os << error; 260 return os; 261 } 262 263 // XXX Should be in .cc. 264 twister_rand_gen:: 265 twister_rand_gen(unsigned int seed) : _M_generator(seed) { } 266 267 void 268 twister_rand_gen:: 269 init(unsigned int seed) 270 { _M_generator.seed(seed); } 271 272 double 273 twister_rand_gen:: 274 get_prob() 275 { 276 const double eng_min = _M_generator.min(); 277 const double eng_range = 278 static_cast<const double>(_M_generator.max() - eng_min); 279 280 const double eng_res = 281 static_cast<const double>(_M_generator() - eng_min); 282 283 const double ret = eng_res / eng_range; 284 _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1); 285 return ret; 286 } 287 288 twister_rand_gen throw_allocator_base::_S_g; 289 290 throw_allocator_base::map_type 291 throw_allocator_base::_S_map; 292 293 double throw_allocator_base::_S_throw_prob; 294 295 size_t throw_allocator_base::_S_label = 0; 296 297 throw_allocator_base::entry_type 298 throw_allocator_base::make_entry(void* p, size_t size) 299 { return std::make_pair(p, alloc_data_type(_S_label, size)); } 300 301 void 302 throw_allocator_base::init(unsigned long seed) 303 { _S_g.init(seed); } 304 305 void 306 throw_allocator_base::set_throw_prob(double throw_prob) 307 { _S_throw_prob = throw_prob; } 308 309 double 310 throw_allocator_base::get_throw_prob() 311 { return _S_throw_prob; } 312 313 void 314 throw_allocator_base::set_label(size_t l) 315 { _S_label = l; } 316 317 void 318 throw_allocator_base::insert(void* p, size_t size) 319 { 320 const_iterator found_it = _S_map.find(p); 321 if (found_it != _S_map.end()) 322 { 323 std::string error("throw_allocator_base::insert"); 324 error += "double insert!"; 325 error += '\n'; 326 print_to_string(error, make_entry(p, size)); 327 print_to_string(error, *found_it); 328 throw std::logic_error(error); 329 } 330 _S_map.insert(make_entry(p, size)); 331 } 332 333 bool 334 throw_allocator_base::empty() 335 { return _S_map.empty(); } 336 337 void 338 throw_allocator_base::erase(void* p, size_t size) 339 { 340 check_allocated(p, size); 341 _S_map.erase(p); 342 } 343 344 void 345 throw_allocator_base::check_allocated(void* p, size_t size) 346 { 347 const_iterator found_it = _S_map.find(p); 348 if (found_it == _S_map.end()) 349 { 350 std::string error("throw_allocator_base::check_allocated by value "); 351 error += "null erase!"; 352 error += '\n'; 353 print_to_string(error, make_entry(p, size)); 354 throw std::logic_error(error); 355 } 356 357 if (found_it->second.second != size) 358 { 359 std::string error("throw_allocator_base::check_allocated by value "); 360 error += "wrong-size erase!"; 361 error += '\n'; 362 print_to_string(error, make_entry(p, size)); 363 print_to_string(error, *found_it); 364 throw std::logic_error(error); 365 } 366 } 367 368 void 369 throw_allocator_base::check_allocated(size_t label) 370 { 371 std::string found; 372 const_iterator it = _S_map.begin(); 373 while (it != _S_map.end()) 374 { 375 if (it->second.first == label) 376 print_to_string(found, *it); 377 ++it; 378 } 379 380 if (!found.empty()) 381 { 382 std::string error("throw_allocator_base::check_allocated by label "); 383 error += '\n'; 384 error += found; 385 throw std::logic_error(error); 386 } 387 } 388 389 void 390 throw_allocator_base::throw_conditionally() 391 { 392 if (_S_g.get_prob() < _S_throw_prob) 393 throw forced_exception_error(); 394 } 395 396 void 397 throw_allocator_base::print_to_string(std::string& s) 398 { 399 const_iterator begin = throw_allocator_base::_S_map.begin(); 400 const_iterator end = throw_allocator_base::_S_map.end(); 401 for (; begin != end; ++begin) 402 print_to_string(s, *begin); 403 } 404 405 void 406 throw_allocator_base::print_to_string(std::string& s, const_reference ref) 407 { 408 char buf[40]; 409 const char tab('\t'); 410 s += "address: "; 411 sprintf(buf, "%p", ref.first); 412 s += buf; 413 s += tab; 414 s += "label: "; 415 sprintf(buf, "%u", ref.second.first); 416 s += buf; 417 s += tab; 418 s += "size: "; 419 sprintf(buf, "%u", ref.second.second); 420 s += buf; 421 s += '\n'; 422 } 423 424 _GLIBCXX_END_NAMESPACE 425 426 #endif 427