contrib/libc++/src/debug.cpp

   1 //===-------------------------- debug.cpp ---------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is dual licensed under the MIT and the University of Illinois Open
   6 // Source Licenses. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "__config"
  11 #include "__debug"
  12 #include "functional"
  13 #include "algorithm"
  14 #include "string"
  15 #include "cstdio"
  16 #include "__hash_table"
  17 #include "mutex"
  18
  19 _LIBCPP_BEGIN_NAMESPACE_STD
  20
  21 static std::string make_what_str(__libcpp_debug_info const& info) {
  22   string msg = info.__file_;
  23   msg += ":" + to_string(info.__line_) + ": _LIBCPP_ASSERT '";
  24   msg += info.__pred_;
  25   msg += "' failed. ";
  26   msg += info.__msg_;
  27   return msg;
  28 }
  29
  30 _LIBCPP_SAFE_STATIC __libcpp_debug_function_type
  31     __libcpp_debug_function = __libcpp_abort_debug_function;
  32
  33 bool __libcpp_set_debug_function(__libcpp_debug_function_type __func) {
  34   __libcpp_debug_function = __func;
  35   return true;
  36 }
  37
  38 _LIBCPP_NORETURN void __libcpp_abort_debug_function(__libcpp_debug_info const& info) {
  39   std::fprintf(stderr, "%s\n", make_what_str(info).c_str());
  40   std::abort();
  41 }
  42
  43 _LIBCPP_NORETURN void __libcpp_throw_debug_function(__libcpp_debug_info const& info) {
  44 #ifndef _LIBCPP_NO_EXCEPTIONS
  45   throw __libcpp_debug_exception(info);
  46 #else
  47   __libcpp_abort_debug_function(info);
  48 #endif
  49 }
  50
  51 struct __libcpp_debug_exception::__libcpp_debug_exception_imp {
  52   __libcpp_debug_info __info_;
  53   std::string __what_str_;
  54 };
  55
  56 __libcpp_debug_exception::__libcpp_debug_exception() _NOEXCEPT
  57     : __imp_(nullptr) {
  58 }
  59
  60 __libcpp_debug_exception::__libcpp_debug_exception(
  61     __libcpp_debug_info const& info) : __imp_(new __libcpp_debug_exception_imp)
  62 {
  63   __imp_->__info_ = info;
  64   __imp_->__what_str_ = make_what_str(info);
  65 }
  66 __libcpp_debug_exception::__libcpp_debug_exception(
  67     __libcpp_debug_exception const& other) : __imp_(nullptr) {
  68   if (other.__imp_)
  69     __imp_ = new __libcpp_debug_exception_imp(*other.__imp_);
  70 }
  71
  72 __libcpp_debug_exception::~__libcpp_debug_exception() _NOEXCEPT {
  73   if (__imp_)
  74     delete __imp_;
  75 }
  76
  77 const char* __libcpp_debug_exception::what() const _NOEXCEPT {
  78   if (__imp_)
  79     return __imp_->__what_str_.c_str();
  80   return "__libcpp_debug_exception";
  81 }
  82
  83 _LIBCPP_FUNC_VIS
  84 __libcpp_db*
  85 __get_db()
  86 {
  87     static __libcpp_db db;
  88     return &db;
  89 }
  90
  91 _LIBCPP_FUNC_VIS
  92 const __libcpp_db*
  93 __get_const_db()
  94 {
  95     return __get_db();
  96 }
  97
  98 namespace
  99 {
 100
 101 #ifndef _LIBCPP_HAS_NO_THREADS
 102 typedef mutex mutex_type;
 103 typedef lock_guard<mutex_type> WLock;
 104 typedef lock_guard<mutex_type> RLock;
 105
 106 mutex_type&
 107 mut()
 108 {
 109     static mutex_type m;
 110     return m;
 111 }
 112 #endif // !_LIBCPP_HAS_NO_THREADS
 113
 114 }  // unnamed namespace
 115
 116 __i_node::~__i_node()
 117 {
 118     if (__next_)
 119     {
 120         __next_->~__i_node();
 121         free(__next_);
 122     }
 123 }
 124
 125 __c_node::~__c_node()
 126 {
 127     free(beg_);
 128     if (__next_)
 129     {
 130         __next_->~__c_node();
 131         free(__next_);
 132     }
 133 }
 134
 135 __libcpp_db::__libcpp_db()
 136     : __cbeg_(nullptr),
 137       __cend_(nullptr),
 138       __csz_(0),
 139       __ibeg_(nullptr),
 140       __iend_(nullptr),
 141       __isz_(0)
 142 {
 143 }
 144
 145 __libcpp_db::~__libcpp_db()
 146 {
 147     if (__cbeg_)
 148     {
 149         for (__c_node** p = __cbeg_; p != __cend_; ++p)
 150         {
 151             if (*p != nullptr)
 152             {
 153                 (*p)->~__c_node();
 154                 free(*p);
 155             }
 156         }
 157         free(__cbeg_);
 158     }
 159     if (__ibeg_)
 160     {
 161         for (__i_node** p = __ibeg_; p != __iend_; ++p)
 162         {
 163             if (*p != nullptr)
 164             {
 165                 (*p)->~__i_node();
 166                 free(*p);
 167             }
 168         }
 169         free(__ibeg_);
 170     }
 171 }
 172
 173 void*
 174 __libcpp_db::__find_c_from_i(void* __i) const
 175 {
 176 #ifndef _LIBCPP_HAS_NO_THREADS
 177     RLock _(mut());
 178 #endif
 179     __i_node* i = __find_iterator(__i);
 180     _LIBCPP_ASSERT(i != nullptr, "iterator not found in debug database.");
 181     return i->__c_ != nullptr ? i->__c_->__c_ : nullptr;
 182 }
 183
 184 void
 185 __libcpp_db::__insert_ic(void* __i, const void* __c)
 186 {
 187 #ifndef _LIBCPP_HAS_NO_THREADS
 188     WLock _(mut());
 189 #endif
 190     if (__cbeg_ == __cend_)
 191         return;
 192     size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
 193     __c_node* c = __cbeg_[hc];
 194     if (c == nullptr)
 195         return;
 196     while (c->__c_ != __c)
 197     {
 198         c = c->__next_;
 199         if (c == nullptr)
 200             return;
 201     }
 202     __i_node* i = __insert_iterator(__i);
 203     c->__add(i);
 204     i->__c_ = c;
 205 }
 206
 207 __c_node*
 208 __libcpp_db::__insert_c(void* __c)
 209 {
 210 #ifndef _LIBCPP_HAS_NO_THREADS
 211     WLock _(mut());
 212 #endif
 213     if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_))
 214     {
 215         size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1);
 216         __c_node** cbeg = static_cast<__c_node**>(calloc(nc, sizeof(void*)));
 217         if (cbeg == nullptr)
 218             __throw_bad_alloc();
 219
 220         for (__c_node** p = __cbeg_; p != __cend_; ++p)
 221         {
 222             __c_node* q = *p;
 223             while (q != nullptr)
 224             {
 225                 size_t h = hash<void*>()(q->__c_) % nc;
 226                 __c_node* r = q->__next_;
 227                 q->__next_ = cbeg[h];
 228                 cbeg[h] = q;
 229                 q = r;
 230             }
 231         }
 232         free(__cbeg_);
 233         __cbeg_ = cbeg;
 234         __cend_ = __cbeg_ + nc;
 235     }
 236     size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
 237     __c_node* p = __cbeg_[hc];
 238     __c_node* r = __cbeg_[hc] =
 239       static_cast<__c_node*>(malloc(sizeof(__c_node)));
 240     if (__cbeg_[hc] == nullptr)
 241         __throw_bad_alloc();
 242
 243     r->__c_ = __c;
 244     r->__next_ = p;
 245     ++__csz_;
 246     return r;
 247 }
 248
 249 void
 250 __libcpp_db::__erase_i(void* __i)
 251 {
 252 #ifndef _LIBCPP_HAS_NO_THREADS
 253     WLock _(mut());
 254 #endif
 255     if (__ibeg_ != __iend_)
 256     {
 257         size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
 258         __i_node* p = __ibeg_[hi];
 259         if (p != nullptr)
 260         {
 261             __i_node* q = nullptr;
 262             while (p->__i_ != __i)
 263             {
 264                 q = p;
 265                 p = p->__next_;
 266                 if (p == nullptr)
 267                     return;
 268             }
 269             if (q == nullptr)
 270                 __ibeg_[hi] = p->__next_;
 271             else
 272                 q->__next_ = p->__next_;
 273             __c_node* c = p->__c_;
 274             --__isz_;
 275             if (c != nullptr)
 276                 c->__remove(p);
 277             free(p);
 278         }
 279     }
 280 }
 281
 282 void
 283 __libcpp_db::__invalidate_all(void* __c)
 284 {
 285 #ifndef _LIBCPP_HAS_NO_THREADS
 286     WLock _(mut());
 287 #endif
 288     if (__cend_ != __cbeg_)
 289     {
 290         size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
 291         __c_node* p = __cbeg_[hc];
 292         if (p == nullptr)
 293             return;
 294         while (p->__c_ != __c)
 295         {
 296             p = p->__next_;
 297             if (p == nullptr)
 298                 return;
 299         }
 300         while (p->end_ != p->beg_)
 301         {
 302             --p->end_;
 303             (*p->end_)->__c_ = nullptr;
 304         }
 305     }
 306 }
 307
 308 __c_node*
 309 __libcpp_db::__find_c_and_lock(void* __c) const
 310 {
 311 #ifndef _LIBCPP_HAS_NO_THREADS
 312     mut().lock();
 313 #endif
 314     if (__cend_ == __cbeg_)
 315     {
 316 #ifndef _LIBCPP_HAS_NO_THREADS
 317         mut().unlock();
 318 #endif
 319         return nullptr;
 320     }
 321     size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
 322     __c_node* p = __cbeg_[hc];
 323     if (p == nullptr)
 324     {
 325 #ifndef _LIBCPP_HAS_NO_THREADS
 326         mut().unlock();
 327 #endif
 328         return nullptr;
 329     }
 330     while (p->__c_ != __c)
 331     {
 332         p = p->__next_;
 333         if (p == nullptr)
 334         {
 335 #ifndef _LIBCPP_HAS_NO_THREADS
 336             mut().unlock();
 337 #endif
 338             return nullptr;
 339         }
 340     }
 341     return p;
 342 }
 343
 344 __c_node*
 345 __libcpp_db::__find_c(void* __c) const
 346 {
 347     size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
 348     __c_node* p = __cbeg_[hc];
 349     _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A");
 350     while (p->__c_ != __c)
 351     {
 352         p = p->__next_;
 353         _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B");
 354     }
 355     return p;
 356 }
 357
 358 void
 359 __libcpp_db::unlock() const
 360 {
 361 #ifndef _LIBCPP_HAS_NO_THREADS
 362     mut().unlock();
 363 #endif
 364 }
 365
 366 void
 367 __libcpp_db::__erase_c(void* __c)
 368 {
 369 #ifndef _LIBCPP_HAS_NO_THREADS
 370     WLock _(mut());
 371 #endif
 372     if (__cend_ != __cbeg_)
 373     {
 374         size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
 375         __c_node* p = __cbeg_[hc];
 376         if (p == nullptr)
 377             return;
 378         __c_node* q = nullptr;
 379         _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A");
 380         while (p->__c_ != __c)
 381         {
 382             q = p;
 383             p = p->__next_;
 384             if (p == nullptr)
 385                 return;
 386             _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B");
 387         }
 388         if (q == nullptr)
 389             __cbeg_[hc] = p->__next_;
 390         else
 391             q->__next_ = p->__next_;
 392         while (p->end_ != p->beg_)
 393         {
 394             --p->end_;
 395             (*p->end_)->__c_ = nullptr;
 396         }
 397         free(p->beg_);
 398         free(p);
 399         --__csz_;
 400     }
 401 }
 402
 403 void
 404 __libcpp_db::__iterator_copy(void* __i, const void* __i0)
 405 {
 406 #ifndef _LIBCPP_HAS_NO_THREADS
 407     WLock _(mut());
 408 #endif
 409     __i_node* i = __find_iterator(__i);
 410     __i_node* i0 = __find_iterator(__i0);
 411     __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr;
 412     if (i == nullptr && i0 != nullptr)
 413         i = __insert_iterator(__i);
 414     __c_node* c = i != nullptr ? i->__c_ : nullptr;
 415     if (c != c0)
 416     {
 417         if (c != nullptr)
 418             c->__remove(i);
 419         if (i != nullptr)
 420         {
 421             i->__c_ = nullptr;
 422             if (c0 != nullptr)
 423             {
 424                 i->__c_ = c0;
 425                 i->__c_->__add(i);
 426             }
 427         }
 428     }
 429 }
 430
 431 bool
 432 __libcpp_db::__dereferenceable(const void* __i) const
 433 {
 434 #ifndef _LIBCPP_HAS_NO_THREADS
 435     RLock _(mut());
 436 #endif
 437     __i_node* i = __find_iterator(__i);
 438     return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i);
 439 }
 440
 441 bool
 442 __libcpp_db::__decrementable(const void* __i) const
 443 {
 444 #ifndef _LIBCPP_HAS_NO_THREADS
 445     RLock _(mut());
 446 #endif
 447     __i_node* i = __find_iterator(__i);
 448     return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i);
 449 }
 450
 451 bool
 452 __libcpp_db::__addable(const void* __i, ptrdiff_t __n) const
 453 {
 454 #ifndef _LIBCPP_HAS_NO_THREADS
 455     RLock _(mut());
 456 #endif
 457     __i_node* i = __find_iterator(__i);
 458     return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n);
 459 }
 460
 461 bool
 462 __libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const
 463 {
 464 #ifndef _LIBCPP_HAS_NO_THREADS
 465     RLock _(mut());
 466 #endif
 467     __i_node* i = __find_iterator(__i);
 468     return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n);
 469 }
 470
 471 bool
 472 __libcpp_db::__less_than_comparable(const void* __i, const void* __j) const
 473 {
 474 #ifndef _LIBCPP_HAS_NO_THREADS
 475     RLock _(mut());
 476 #endif
 477     __i_node* i = __find_iterator(__i);
 478     __i_node* j = __find_iterator(__j);
 479     __c_node* ci = i != nullptr ? i->__c_ : nullptr;
 480     __c_node* cj = j != nullptr ? j->__c_ : nullptr;
 481     return ci != nullptr && ci == cj;
 482 }
 483
 484 void
 485 __libcpp_db::swap(void* c1, void* c2)
 486 {
 487 #ifndef _LIBCPP_HAS_NO_THREADS
 488     WLock _(mut());
 489 #endif
 490     size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_);
 491     __c_node* p1 = __cbeg_[hc];
 492     _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A");
 493     while (p1->__c_ != c1)
 494     {
 495         p1 = p1->__next_;
 496         _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B");
 497     }
 498     hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_);
 499     __c_node* p2 = __cbeg_[hc];
 500     _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C");
 501     while (p2->__c_ != c2)
 502     {
 503         p2 = p2->__next_;
 504         _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D");
 505     }
 506     std::swap(p1->beg_, p2->beg_);
 507     std::swap(p1->end_, p2->end_);
 508     std::swap(p1->cap_, p2->cap_);
 509     for (__i_node** p = p1->beg_; p != p1->end_; ++p)
 510         (*p)->__c_ = p1;
 511     for (__i_node** p = p2->beg_; p != p2->end_; ++p)
 512         (*p)->__c_ = p2;
 513 }
 514
 515 void
 516 __libcpp_db::__insert_i(void* __i)
 517 {
 518 #ifndef _LIBCPP_HAS_NO_THREADS
 519     WLock _(mut());
 520 #endif
 521     __insert_iterator(__i);
 522 }
 523
 524 void
 525 __c_node::__add(__i_node* i)
 526 {
 527     if (end_ == cap_)
 528     {
 529         size_t nc = 2*static_cast<size_t>(cap_ - beg_);
 530         if (nc == 0)
 531             nc = 1;
 532         __i_node** beg =
 533            static_cast<__i_node**>(malloc(nc * sizeof(__i_node*)));
 534         if (beg == nullptr)
 535             __throw_bad_alloc();
 536
 537         if (nc > 1)
 538             memcpy(beg, beg_, nc/2*sizeof(__i_node*));
 539         free(beg_);
 540         beg_ = beg;
 541         end_ = beg_ + nc/2;
 542         cap_ = beg_ + nc;
 543     }
 544     *end_++ = i;
 545 }
 546
 547 // private api
 548
 549 _LIBCPP_HIDDEN
 550 __i_node*
 551 __libcpp_db::__insert_iterator(void* __i)
 552 {
 553     if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_))
 554     {
 555         size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1);
 556         __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(void*)));
 557         if (ibeg == nullptr)
 558             __throw_bad_alloc();
 559
 560         for (__i_node** p = __ibeg_; p != __iend_; ++p)
 561         {
 562             __i_node* q = *p;
 563             while (q != nullptr)
 564             {
 565                 size_t h = hash<void*>()(q->__i_) % nc;
 566                 __i_node* r = q->__next_;
 567                 q->__next_ = ibeg[h];
 568                 ibeg[h] = q;
 569                 q = r;
 570             }
 571         }
 572         free(__ibeg_);
 573         __ibeg_ = ibeg;
 574         __iend_ = __ibeg_ + nc;
 575     }
 576     size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
 577     __i_node* p = __ibeg_[hi];
 578     __i_node* r = __ibeg_[hi] =
 579       static_cast<__i_node*>(malloc(sizeof(__i_node)));
 580     if (r == nullptr)
 581         __throw_bad_alloc();
 582
 583     ::new(r) __i_node(__i, p, nullptr);
 584     ++__isz_;
 585     return r;
 586 }
 587
 588 _LIBCPP_HIDDEN
 589 __i_node*
 590 __libcpp_db::__find_iterator(const void* __i) const
 591 {
 592     __i_node* r = nullptr;
 593     if (__ibeg_ != __iend_)
 594     {
 595         size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
 596         for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_)
 597         {
 598             if (nd->__i_ == __i)
 599             {
 600                 r = nd;
 601                 break;
 602             }
 603         }
 604     }
 605     return r;
 606 }
 607
 608 _LIBCPP_HIDDEN
 609 void
 610 __c_node::__remove(__i_node* p)
 611 {
 612     __i_node** r = find(beg_, end_, p);
 613     _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove");
 614     if (--end_ != r)
 615         memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*));
 616 }
 617
 618 _LIBCPP_END_NAMESPACE_STD