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