Coverage Report

Created: 2020-09-22 08:39

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