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