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