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