xref: /llvm-project-15.0.7/libcxx/src/debug.cpp (revision 2e1479e2) 
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 void
207 __libcpp_db::__insert_c(void* __c, __libcpp_db::_InsertConstruct *__fn)
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     void *buf = malloc(sizeof(__c_node));
238     if (buf == nullptr)
239       __throw_bad_alloc();
240     __cbeg_[hc] = __fn(buf, __c, p);
241 
242     ++__csz_;
243 }
244 
245 void
246 __libcpp_db::__erase_i(void* __i)
247 {
248 #ifndef _LIBCPP_HAS_NO_THREADS
249     WLock _(mut());
250 #endif
251     if (__ibeg_ != __iend_)
252     {
253         size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
254         __i_node* p = __ibeg_[hi];
255         if (p != nullptr)
256         {
257             __i_node* q = nullptr;
258             while (p->__i_ != __i)
259             {
260                 q = p;
261                 p = p->__next_;
262                 if (p == nullptr)
263                     return;
264             }
265             if (q == nullptr)
266                 __ibeg_[hi] = p->__next_;
267             else
268                 q->__next_ = p->__next_;
269             __c_node* c = p->__c_;
270             --__isz_;
271             if (c != nullptr)
272                 c->__remove(p);
273             free(p);
274         }
275     }
276 }
277 
278 void
279 __libcpp_db::__invalidate_all(void* __c)
280 {
281 #ifndef _LIBCPP_HAS_NO_THREADS
282     WLock _(mut());
283 #endif
284     if (__cend_ != __cbeg_)
285     {
286         size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
287         __c_node* p = __cbeg_[hc];
288         if (p == nullptr)
289             return;
290         while (p->__c_ != __c)
291         {
292             p = p->__next_;
293             if (p == nullptr)
294                 return;
295         }
296         while (p->end_ != p->beg_)
297         {
298             --p->end_;
299             (*p->end_)->__c_ = nullptr;
300         }
301     }
302 }
303 
304 __c_node*
305 __libcpp_db::__find_c_and_lock(void* __c) const
306 {
307 #ifndef _LIBCPP_HAS_NO_THREADS
308     mut().lock();
309 #endif
310     if (__cend_ == __cbeg_)
311     {
312 #ifndef _LIBCPP_HAS_NO_THREADS
313         mut().unlock();
314 #endif
315         return nullptr;
316     }
317     size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
318     __c_node* p = __cbeg_[hc];
319     if (p == nullptr)
320     {
321 #ifndef _LIBCPP_HAS_NO_THREADS
322         mut().unlock();
323 #endif
324         return nullptr;
325     }
326     while (p->__c_ != __c)
327     {
328         p = p->__next_;
329         if (p == nullptr)
330         {
331 #ifndef _LIBCPP_HAS_NO_THREADS
332             mut().unlock();
333 #endif
334             return nullptr;
335         }
336     }
337     return p;
338 }
339 
340 __c_node*
341 __libcpp_db::__find_c(void* __c) const
342 {
343     size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
344     __c_node* p = __cbeg_[hc];
345     _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A");
346     while (p->__c_ != __c)
347     {
348         p = p->__next_;
349         _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B");
350     }
351     return p;
352 }
353 
354 void
355 __libcpp_db::unlock() const
356 {
357 #ifndef _LIBCPP_HAS_NO_THREADS
358     mut().unlock();
359 #endif
360 }
361 
362 void
363 __libcpp_db::__erase_c(void* __c)
364 {
365 #ifndef _LIBCPP_HAS_NO_THREADS
366     WLock _(mut());
367 #endif
368     if (__cend_ != __cbeg_)
369     {
370         size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
371         __c_node* p = __cbeg_[hc];
372         if (p == nullptr)
373             return;
374         __c_node* q = nullptr;
375         _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A");
376         while (p->__c_ != __c)
377         {
378             q = p;
379             p = p->__next_;
380             if (p == nullptr)
381                 return;
382             _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B");
383         }
384         if (q == nullptr)
385             __cbeg_[hc] = p->__next_;
386         else
387             q->__next_ = p->__next_;
388         while (p->end_ != p->beg_)
389         {
390             --p->end_;
391             (*p->end_)->__c_ = nullptr;
392         }
393         free(p->beg_);
394         free(p);
395         --__csz_;
396     }
397 }
398 
399 void
400 __libcpp_db::__iterator_copy(void* __i, const void* __i0)
401 {
402 #ifndef _LIBCPP_HAS_NO_THREADS
403     WLock _(mut());
404 #endif
405     __i_node* i = __find_iterator(__i);
406     __i_node* i0 = __find_iterator(__i0);
407     __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr;
408     if (i == nullptr && i0 != nullptr)
409         i = __insert_iterator(__i);
410     __c_node* c = i != nullptr ? i->__c_ : nullptr;
411     if (c != c0)
412     {
413         if (c != nullptr)
414             c->__remove(i);
415         if (i != nullptr)
416         {
417             i->__c_ = nullptr;
418             if (c0 != nullptr)
419             {
420                 i->__c_ = c0;
421                 i->__c_->__add(i);
422             }
423         }
424     }
425 }
426 
427 bool
428 __libcpp_db::__dereferenceable(const void* __i) const
429 {
430 #ifndef _LIBCPP_HAS_NO_THREADS
431     RLock _(mut());
432 #endif
433     __i_node* i = __find_iterator(__i);
434     return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i);
435 }
436 
437 bool
438 __libcpp_db::__decrementable(const void* __i) const
439 {
440 #ifndef _LIBCPP_HAS_NO_THREADS
441     RLock _(mut());
442 #endif
443     __i_node* i = __find_iterator(__i);
444     return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i);
445 }
446 
447 bool
448 __libcpp_db::__addable(const void* __i, ptrdiff_t __n) const
449 {
450 #ifndef _LIBCPP_HAS_NO_THREADS
451     RLock _(mut());
452 #endif
453     __i_node* i = __find_iterator(__i);
454     return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n);
455 }
456 
457 bool
458 __libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const
459 {
460 #ifndef _LIBCPP_HAS_NO_THREADS
461     RLock _(mut());
462 #endif
463     __i_node* i = __find_iterator(__i);
464     return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n);
465 }
466 
467 bool
468 __libcpp_db::__less_than_comparable(const void* __i, const void* __j) const
469 {
470 #ifndef _LIBCPP_HAS_NO_THREADS
471     RLock _(mut());
472 #endif
473     __i_node* i = __find_iterator(__i);
474     __i_node* j = __find_iterator(__j);
475     __c_node* ci = i != nullptr ? i->__c_ : nullptr;
476     __c_node* cj = j != nullptr ? j->__c_ : nullptr;
477     return ci != nullptr && ci == cj;
478 }
479 
480 void
481 __libcpp_db::swap(void* c1, void* c2)
482 {
483 #ifndef _LIBCPP_HAS_NO_THREADS
484     WLock _(mut());
485 #endif
486     size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_);
487     __c_node* p1 = __cbeg_[hc];
488     _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A");
489     while (p1->__c_ != c1)
490     {
491         p1 = p1->__next_;
492         _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B");
493     }
494     hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_);
495     __c_node* p2 = __cbeg_[hc];
496     _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C");
497     while (p2->__c_ != c2)
498     {
499         p2 = p2->__next_;
500         _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D");
501     }
502     std::swap(p1->beg_, p2->beg_);
503     std::swap(p1->end_, p2->end_);
504     std::swap(p1->cap_, p2->cap_);
505     for (__i_node** p = p1->beg_; p != p1->end_; ++p)
506         (*p)->__c_ = p1;
507     for (__i_node** p = p2->beg_; p != p2->end_; ++p)
508         (*p)->__c_ = p2;
509 }
510 
511 void
512 __libcpp_db::__insert_i(void* __i)
513 {
514 #ifndef _LIBCPP_HAS_NO_THREADS
515     WLock _(mut());
516 #endif
517     __insert_iterator(__i);
518 }
519 
520 void
521 __c_node::__add(__i_node* i)
522 {
523     if (end_ == cap_)
524     {
525         size_t nc = 2*static_cast<size_t>(cap_ - beg_);
526         if (nc == 0)
527             nc = 1;
528         __i_node** beg =
529            static_cast<__i_node**>(malloc(nc * sizeof(__i_node*)));
530         if (beg == nullptr)
531             __throw_bad_alloc();
532 
533         if (nc > 1)
534             memcpy(beg, beg_, nc/2*sizeof(__i_node*));
535         free(beg_);
536         beg_ = beg;
537         end_ = beg_ + nc/2;
538         cap_ = beg_ + nc;
539     }
540     *end_++ = i;
541 }
542 
543 // private api
544 
545 _LIBCPP_HIDDEN
546 __i_node*
547 __libcpp_db::__insert_iterator(void* __i)
548 {
549     if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_))
550     {
551         size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1);
552         __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(void*)));
553         if (ibeg == nullptr)
554             __throw_bad_alloc();
555 
556         for (__i_node** p = __ibeg_; p != __iend_; ++p)
557         {
558             __i_node* q = *p;
559             while (q != nullptr)
560             {
561                 size_t h = hash<void*>()(q->__i_) % nc;
562                 __i_node* r = q->__next_;
563                 q->__next_ = ibeg[h];
564                 ibeg[h] = q;
565                 q = r;
566             }
567         }
568         free(__ibeg_);
569         __ibeg_ = ibeg;
570         __iend_ = __ibeg_ + nc;
571     }
572     size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
573     __i_node* p = __ibeg_[hi];
574     __i_node* r = __ibeg_[hi] =
575       static_cast<__i_node*>(malloc(sizeof(__i_node)));
576     if (r == nullptr)
577         __throw_bad_alloc();
578 
579     ::new(r) __i_node(__i, p, nullptr);
580     ++__isz_;
581     return r;
582 }
583 
584 _LIBCPP_HIDDEN
585 __i_node*
586 __libcpp_db::__find_iterator(const void* __i) const
587 {
588     __i_node* r = nullptr;
589     if (__ibeg_ != __iend_)
590     {
591         size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
592         for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_)
593         {
594             if (nd->__i_ == __i)
595             {
596                 r = nd;
597                 break;
598             }
599         }
600     }
601     return r;
602 }
603 
604 _LIBCPP_HIDDEN
605 void
606 __c_node::__remove(__i_node* p)
607 {
608     __i_node** r = find(beg_, end_, p);
609     _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove");
610     if (--end_ != r)
611         memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*));
612 }
613 
614 _LIBCPP_END_NAMESPACE_STD
615