xref: /openbsd/gnu/llvm/libcxx/src/debug.cpp (revision a0747c9f) 
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 #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
579