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