libcxx/src/debug.cpp

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