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 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 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 { 119 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 126 ~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 { 135 zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob) 136 { _S_throw_prob = 0; } 137 138 ~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 209 throw_allocator() throw() { } 210 211 throw_allocator(const throw_allocator&) throw() { } 212 213 template<typename U> 214 throw_allocator(const throw_allocator<U>&) throw() { } 215 216 ~throw_allocator() throw() { } 217 218 size_type 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 232 construct(pointer p, const T& val) 233 { return std::allocator<value_type>().construct(p, val); } 234 235 void 236 destroy(pointer p) 237 { std::allocator<value_type>().destroy(p); } 238 239 void 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 247 check_allocated(pointer p, size_type num) 248 { throw_allocator_base::check_allocated(p, sizeof(value_type) * num); } 249 250 void 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:: 276 twister_rand_gen(unsigned int seed) : _M_generator(seed) { } 277 278 void 279 twister_rand_gen:: 280 init(unsigned int seed) 281 { _M_generator.seed(seed); } 282 283 double 284 twister_rand_gen:: 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 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 313 throw_allocator_base::init(unsigned long seed) 314 { _S_g.init(seed); } 315 316 void 317 throw_allocator_base::set_throw_prob(double throw_prob) 318 { _S_throw_prob = throw_prob; } 319 320 double 321 throw_allocator_base::get_throw_prob() 322 { return _S_throw_prob; } 323 324 void 325 throw_allocator_base::set_label(size_t l) 326 { _S_label = l; } 327 328 void 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 345 throw_allocator_base::empty() 346 { return _S_map.empty(); } 347 348 void 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 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 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 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 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 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 sprintf(buf, "%p", ref.first); 423 s += buf; 424 s += tab; 425 s += "label: "; 426 sprintf(buf, "%lu", ref.second.first); 427 s += buf; 428 s += tab; 429 s += "size: "; 430 sprintf(buf, "%lu", ref.second.second); 431 s += buf; 432 s += '\n'; 433 } 434 435_GLIBCXX_END_NAMESPACE 436 437#endif 438