0%

shared_ptr是线程安全的吗?

Boost官网:shared_ptr_thread_safety

shared_ptr与内建类型(比如int, char;std::string不是内建类型)具有相同的线程安全等级:

  • 同一个shared_ptr可以被并发读;
  • 不同的shared_ptr可以被并发写(析构也是写)。
  • 其他并发访问是未定义的。

Examples:

1
shared_ptr<int> p(new int(42));

Code Example 4. Reading a shared_ptr from two threads

1
2
3
4
5
// thread A
shared_ptr<int> p2(p); // reads p

// thread B
shared_ptr<int> p3(p); // OK, multiple reads are safe

读取同一个shared_ptr是线程安全的。
同时增加引用计数,安全。

Code Example 5. Writing different shared_ptr instances from two threads

1
2
3
4
5
// thread A
p.reset(new int(1912)); // writes p

// thread B
p2.reset(); // OK, writes p2

写不同的shared_ptr实例是线程安全的。
不同的实例各自更新自己的引用计数控制块指针,安全。
对共同掌管的资源的引用计数原子减1,安全。

Code Example 6. Reading and writing a shared_ptr from two threads

1
2
3
4
5
// thread A
p = p3; // reads p3, writes p

// thread B
p3.reset(); // writes p3; undefined, simultaneous read/write

同时读写同一个shared_ptr实例,是线程不安全的。
同时对引用计数进行增减,如果先看到减到0,那么可能资源已经被释放。

Code Example 7. Reading and destroying a shared_ptr from two threads

1
2
3
4
5
// thread A
p3 = p2; // reads p2, writes p3

// thread B
// p2 goes out of scope: undefined, the destructor is considered a "write access"

同时读写(析构也是写)同一个shared_ptr实例,是线程不安全的。

Code Example 8. Writing a shared_ptr from two threads

1
2
3
4
5
// thread A
p3.reset(new int(1));

// thread B
p3.reset(new int(2)); // undefined, multiple writes

同时写同一个shared_ptr,可能对引用计数操作多次(应该只能操作一次),线程不安全。

测试:模拟潜在竞态条件:

最后一个引用即将销毁时,另一个线程试图复制

示例1:复制构造和reset()竞争
race1.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <chrono>
#include <iostream>
#include <memory>
#include <thread>

struct Test {
Test() { std::cout << "Test constructed\n"; }
~Test() { std::cout << "Test destroyed\n"; }
};

void thread_copy(std::shared_ptr<Test>& ptr) {
// 模拟延迟,试图在主线程销毁后复制
std::this_thread::sleep_for(std::chrono::milliseconds(100));
std::cout << "Thread attempting to copy shared_ptr\n";
std::shared_ptr<Test> local_copy = ptr; // 资源可能已经释放
if (local_copy) { // shared_ptr 还存在,所以可以用来检查资源是否有效
std::cout << "Thread copied shared_ptr\n";
} else {
std::cout << "Thread failed to copy shared_ptr\n";
}
}

int main() {
std::shared_ptr<Test> ptr = std::make_shared<Test>();

std::thread t(thread_copy, std::ref(ptr));

// 主线程销毁 shared_ptr
std::this_thread::sleep_for(std::chrono::milliseconds(50));
ptr.reset(); // 引用计数降为 0,销毁对象

t.join();
return 0;
}

总结: reset() 与复制构造需要加锁保护。

示例2:复制构造和析构竞争
race2.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <chrono>
#include <iostream>
#include <memory>
#include <thread>

struct Test {
Test() { std::cout << "Test constructed\n"; }
~Test() { std::cout << "Test destroyed\n"; }
};

void thread_copy(std::shared_ptr<Test>& ptr) {
// 模拟延迟,试图在主线程销毁后复制
std::this_thread::sleep_for(std::chrono::milliseconds(100));
std::cout << "Thread attempting to copy shared_ptr\n";
std::shared_ptr<Test> local_copy = ptr; // 如果 ptr 已经销毁,这里是未定义行为
if (local_copy) { // 可能“成功”复制一个已经销毁的 shared_ptr
std::cout << "Thread copied shared_ptr\n";
std::cout << "Use count in thread: "
<< local_copy.use_count() << "\n"; // 引用计数控制块是一个野指针
} else {
std::cout << "Thread failed to copy shared_ptr\n";
}
}

int main() {
std::thread t;

{
std::shared_ptr<Test> ptr = std::make_shared<Test>();

t = std::thread(thread_copy, std::ref(ptr));

// 主线程销毁 shared_ptr
std::this_thread::sleep_for(std::chrono::milliseconds(50));

// 析构,引用计数降为 0,销毁对象
}

t.join();
return 0;
}

总结:

  • 不能以左值引用来复制构造shared_ptr,否则会存在竞争。
  • 可以使用const引用,因为可以延续shared_ptr的生命期,析构被推迟,间接消除了竞态。
  • 程序中shared_ptr读写操作同时存在时,需要加锁。
  • 要防止shared_ptr析构:在shared_ptr副本的整个作用域内加锁同样可以保护这种情况。
  • C++20 开始支持 atomic<shared_ptr<T>>,可以安全地在多个线程之间共享和更新 shared_ptr。
  • 如果 thread A 只是想观察 p2 是否还存在,可以使用 std::weak_ptr 来观察。

shared_ptr为什么要隐式自持一个weak count?

每个 shared_ptr 和 weak_ptr 都指向一个 控制块(control block),这个控制块通常包含:

名称 作用
strong count 当前活跃的 shared_ptr 数量
weak count 当前活跃的 weak_ptr 数量 + 当前活跃的 shared_ptr 数量
指向对象的指针 被管理的资源

控制块的生命周期由 weak count 决定,只要还有 weak_ptr 或 shared_ptr 存在,控制块就不能被销毁。

  • weak_ptr和shared_ptr可能存在只有两者之一的情况,所以他们都必须要维护控制块的生命周期。
  • 如果只有weak_ptr对weak count进行计数,那么可能出现shared_ptr和weak_ptr共同看到weak count为0的情况:
    • weak_ptr析构将weak count降低为0,准备释放控制块;
    • shared_ptr析构或reset,检测到weak count为0,准备释放控制块;
    • 这样就释放了两次,因为他们都持有指针,且没有设置相互通知的机制。
  • 但是,如果weak_ptr和shared_ptr都对weak count进行计数,那么就不可能同时观察到weak count为0的情况。

动手实现一个shared_ptr

SimpleSharedPtr
SimpleSharedPtr.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
#include <iostream>
#include <atomic>
#include <functional>
#include <stdexcept>

template<typename T>
class SimpleSharedPtr; // 先声明

template<typename T>
class SimpleWeakPtr;

template<typename T>
class ControlBlock {
public:
std::atomic<int> shared_count;
std::atomic<int> weak_count;
T* ptr;
std::function<void(T*)> deleter;

// 每个shared_ptr自持一个weak count
ControlBlock(T* p, std::function<void(T*)> d)
: shared_count(1), weak_count(1), ptr(p), deleter(d ? d : [](T* p){ delete p; }) {}

~ControlBlock() = default;
};

template<typename T>
class SimpleSharedPtr {
private:
ControlBlock<T>* ctrl;

void release() {
if (ctrl) {
// 减shared_count
if (ctrl->shared_count.fetch_sub(1, std::memory_order_acq_rel) == 1) {
// 最后一个shared_ptr,释放资源
try {
ctrl->deleter(ctrl->ptr);
} catch (...) {
std::cerr << "Exception in deleter\n";
}
ctrl->ptr = nullptr;

// 再减少weak_count,自己占有一个weak计数,减少它
if (ctrl->weak_count.fetch_sub(1, std::memory_order_acq_rel) == 1) {
delete ctrl;
}
}
ctrl = nullptr;
}
}

public:
explicit SimpleSharedPtr(T* p = nullptr, std::function<void(T*)> d = nullptr) {
if (p) {
ctrl = new ControlBlock<T>(p, d);
// shared_count=1, weak_count=0
} else {
ctrl = nullptr;
}
}

// 拷贝构造
SimpleSharedPtr(const SimpleSharedPtr& other) : ctrl(other.ctrl) {
if (ctrl) {
ctrl->shared_count.fetch_add(1, std::memory_order_relaxed);
}
}

// 移动构造
SimpleSharedPtr(SimpleSharedPtr&& other) noexcept : ctrl(other.ctrl) {
other.ctrl = nullptr;
}

// 析构
~SimpleSharedPtr() {
release();
}

// 拷贝赋值
SimpleSharedPtr& operator=(const SimpleSharedPtr& other) {
if (this != &other) {
release();
ctrl = other.ctrl;
if (ctrl) {
ctrl->shared_count.fetch_add(1, std::memory_order_relaxed);
}
}
return *this;
}

// 移动赋值
SimpleSharedPtr& operator=(SimpleSharedPtr&& other) noexcept {
if (this != &other) {
release();
ctrl = other.ctrl;
other.ctrl = nullptr;
}
return *this;
}

T* get() const {
return ctrl ? ctrl->ptr : nullptr;
}

T& operator*() const {
if (!get()) throw std::runtime_error("Dereferencing null pointer");
return *(ctrl->ptr);
}

T* operator->() const {
return get();
}

int use_count() const {
return ctrl ? ctrl->shared_count.load(std::memory_order_relaxed) : 0;
}

bool unique() const {
return use_count() == 1;
}

explicit operator bool() const {
return get() != nullptr;
}

void reset(T* p = nullptr, std::function<void(T*)> d = nullptr) {
release();
if (p) {
ctrl = new ControlBlock<T>(p, d);
} else {
ctrl = nullptr;
}
}

// 给 SimpleWeakPtr 访问 ControlBlock 指针权限
friend class SimpleWeakPtr<T>;

private:
// SimpleSharedPtr增加一个私有构造,能从控制块构造shared_ptr(配合weak_ptr的lock)
SimpleSharedPtr(ControlBlock<T>* c) : ctrl(c) {}
};

template<typename T>
class SimpleWeakPtr {
private:
ControlBlock<T>* ctrl;

void release() {
if (ctrl) {
if (ctrl->weak_count.fetch_sub(1, std::memory_order_acq_rel) == 1) {
// 只有弱引用且没有shared_ptr存在时,销毁控制块
if (ctrl->shared_count.load(std::memory_order_acquire) == 0) {
delete ctrl;
}
}
ctrl = nullptr;
}
}

public:
SimpleWeakPtr() : ctrl(nullptr) {}

// 从 shared_ptr 构造 weak_ptr
SimpleWeakPtr(const SimpleSharedPtr<T>& shared) : ctrl(shared.ctrl) {
if (ctrl) {
ctrl->weak_count.fetch_add(1, std::memory_order_relaxed);
}
}

// 拷贝构造
SimpleWeakPtr(const SimpleWeakPtr& other) : ctrl(other.ctrl) {
if (ctrl) {
ctrl->weak_count.fetch_add(1, std::memory_order_relaxed);
}
}

// 移动构造
SimpleWeakPtr(SimpleWeakPtr&& other) noexcept : ctrl(other.ctrl) {
other.ctrl = nullptr;
}

~SimpleWeakPtr() {
release();
}

// 拷贝赋值
SimpleWeakPtr& operator=(const SimpleWeakPtr& other) {
if (this != &other) {
release();
ctrl = other.ctrl;
if (ctrl) {
ctrl->weak_count.fetch_add(1, std::memory_order_relaxed);
}
}
return *this;
}

// 移动赋值
SimpleWeakPtr& operator=(SimpleWeakPtr&& other) noexcept {
if (this != &other) {
release();
ctrl = other.ctrl;
other.ctrl = nullptr;
}
return *this;
}

int use_count() const {
return ctrl ? ctrl->shared_count.load(std::memory_order_relaxed) : 0;
}

bool expired() const {
return use_count() == 0;
}

// 尝试获取shared_ptr,资源已被销毁则返回空shared_ptr
SimpleSharedPtr<T> lock() const {
if (expired()) {
return SimpleSharedPtr<T>();
} else {
// 尝试增加shared_count
int old_count = ctrl->shared_count.load(std::memory_order_relaxed);
while (old_count != 0) {
if (ctrl->shared_count.compare_exchange_weak(old_count, old_count + 1,
std::memory_order_acq_rel, std::memory_order_relaxed)) {
// 成功增加shared_count
return SimpleSharedPtr<T>(ctrl);
}
// old_count 已被更新,继续循环
}
return SimpleSharedPtr<T>();
}
}

private:
// 让 SimpleSharedPtr 可以通过控制块构造 shared_ptr
friend class SimpleSharedPtr<T>;

explicit SimpleWeakPtr(ControlBlock<T>* c) : ctrl(c) {}
};


int main() {
SimpleSharedPtr<int> sp1(new int(42));
SimpleWeakPtr<int> wp1 = sp1;

std::cout << "use_count: " << sp1.use_count() << "\n"; // 1
std::cout << "expired: " << wp1.expired() << "\n"; // 0

if (auto sp2 = wp1.lock()) {
std::cout << "locked value: " << *sp2 << "\n"; // 42
std::cout << "use_count after lock: " << sp2.use_count() << "\n"; // 2
}

sp1.reset();

std::cout << "expired after reset: " << wp1.expired() << "\n"; // 1

if (auto sp3 = wp1.lock()) {
std::cout << "Should not print\n";
} else {
std::cout << "lock failed, resource expired\n";
}

return 0;
}

附录:shared_ptr源码

https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/index.html

  • /usr/include/c++/11/bits/shared_ptr.h
  • /usr/include/c++/11/bits/shared_ptr_base.h
  • /usr/include/c++/11/bits/shared_ptr_atomic.h
shared_ptr.h
shared_ptr.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
// shared_ptr and weak_ptr implementation -*- C++ -*-

// Copyright (C) 2007-2021 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.

// GCC Note: Based on files from version 1.32.0 of the Boost library.

// shared_count.hpp
// Copyright (c) 2001, 2002, 2003 Peter Dimov and Multi Media Ltd.

// shared_ptr.hpp
// Copyright (C) 1998, 1999 Greg Colvin and Beman Dawes.
// Copyright (C) 2001, 2002, 2003 Peter Dimov

// weak_ptr.hpp
// Copyright (C) 2001, 2002, 2003 Peter Dimov

// enable_shared_from_this.hpp
// Copyright (C) 2002 Peter Dimov

// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

/** @file
* This is an internal header file, included by other library headers.
* Do not attempt to use it directly. @headername{memory}
*/

#ifndef _SHARED_PTR_H
#define _SHARED_PTR_H 1

#include <iosfwd> // std::basic_ostream
#include <bits/shared_ptr_base.h>

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

/**
* @addtogroup pointer_abstractions
* @{
*/

// 20.7.2.2.11 shared_ptr I/O

/// Write the stored pointer to an ostream.
/// @relates shared_ptr
template<typename _Ch, typename _Tr, typename _Tp, _Lock_policy _Lp>
inline std::basic_ostream<_Ch, _Tr>&
operator<<(std::basic_ostream<_Ch, _Tr>& __os,
const __shared_ptr<_Tp, _Lp>& __p)
{
__os << __p.get();
return __os;
}

template<typename _Del, typename _Tp, _Lock_policy _Lp>
inline _Del*
get_deleter(const __shared_ptr<_Tp, _Lp>& __p) noexcept
{
#if __cpp_rtti
return static_cast<_Del*>(__p._M_get_deleter(typeid(_Del)));
#else
return 0;
#endif
}

/// 20.7.2.2.10 shared_ptr get_deleter

/// If `__p` has a deleter of type `_Del`, return a pointer to it.
/// @relates shared_ptr
template<typename _Del, typename _Tp>
inline _Del*
get_deleter(const shared_ptr<_Tp>& __p) noexcept
{
#if __cpp_rtti
return static_cast<_Del*>(__p._M_get_deleter(typeid(_Del)));
#else
return 0;
#endif
}

/**
* @brief A smart pointer with reference-counted copy semantics.
*
* A `shared_ptr` object is either empty or _owns_ a pointer passed
* to the constructor. Copies of a `shared_ptr` share ownership of
* the same pointer. When the last `shared_ptr` that owns the pointer
* is destroyed or reset, the owned pointer is freed (either by `delete`
* or by invoking a custom deleter that was passed to the constructor).
*
* A `shared_ptr` also stores another pointer, which is usually
* (but not always) the same pointer as it owns. The stored pointer
* can be retrieved by calling the `get()` member function.
*
* The equality and relational operators for `shared_ptr` only compare
* the stored pointer returned by `get()`, not the owned pointer.
* To test whether two `shared_ptr` objects share ownership of the same
* pointer see `std::shared_ptr::owner_before` and `std::owner_less`.
*/
template<typename _Tp>
class shared_ptr : public __shared_ptr<_Tp>
{
template<typename... _Args>
using _Constructible = typename enable_if<
is_constructible<__shared_ptr<_Tp>, _Args...>::value
>::type;

template<typename _Arg>
using _Assignable = typename enable_if<
is_assignable<__shared_ptr<_Tp>&, _Arg>::value, shared_ptr&
>::type;

public:

/// The type pointed to by the stored pointer, remove_extent_t<_Tp>
using element_type = typename __shared_ptr<_Tp>::element_type;

#if __cplusplus >= 201703L
# define __cpp_lib_shared_ptr_weak_type 201606
/// The corresponding weak_ptr type for this shared_ptr
using weak_type = weak_ptr<_Tp>;
#endif
/**
* @brief Construct an empty %shared_ptr.
* @post use_count()==0 && get()==0
*/
constexpr shared_ptr() noexcept : __shared_ptr<_Tp>() { }

shared_ptr(const shared_ptr&) noexcept = default; ///< Copy constructor

/**
* @brief Construct a %shared_ptr that owns the pointer @a __p.
* @param __p A pointer that is convertible to element_type*.
* @post use_count() == 1 && get() == __p
* @throw std::bad_alloc, in which case @c delete @a __p is called.
*/
template<typename _Yp, typename = _Constructible<_Yp*>>
explicit
shared_ptr(_Yp* __p) : __shared_ptr<_Tp>(__p) { }

/**
* @brief Construct a %shared_ptr that owns the pointer @a __p
* and the deleter @a __d.
* @param __p A pointer.
* @param __d A deleter.
* @post use_count() == 1 && get() == __p
* @throw std::bad_alloc, in which case @a __d(__p) is called.
*
* Requirements: _Deleter's copy constructor and destructor must
* not throw
*
* __shared_ptr will release __p by calling __d(__p)
*/
template<typename _Yp, typename _Deleter,
typename = _Constructible<_Yp*, _Deleter>>
shared_ptr(_Yp* __p, _Deleter __d)
: __shared_ptr<_Tp>(__p, std::move(__d)) { }

/**
* @brief Construct a %shared_ptr that owns a null pointer
* and the deleter @a __d.
* @param __p A null pointer constant.
* @param __d A deleter.
* @post use_count() == 1 && get() == __p
* @throw std::bad_alloc, in which case @a __d(__p) is called.
*
* Requirements: _Deleter's copy constructor and destructor must
* not throw
*
* The last owner will call __d(__p)
*/
template<typename _Deleter>
shared_ptr(nullptr_t __p, _Deleter __d)
: __shared_ptr<_Tp>(__p, std::move(__d)) { }

/**
* @brief Construct a %shared_ptr that owns the pointer @a __p
* and the deleter @a __d.
* @param __p A pointer.
* @param __d A deleter.
* @param __a An allocator.
* @post use_count() == 1 && get() == __p
* @throw std::bad_alloc, in which case @a __d(__p) is called.
*
* Requirements: _Deleter's copy constructor and destructor must
* not throw _Alloc's copy constructor and destructor must not
* throw.
*
* __shared_ptr will release __p by calling __d(__p)
*/
template<typename _Yp, typename _Deleter, typename _Alloc,
typename = _Constructible<_Yp*, _Deleter, _Alloc>>
shared_ptr(_Yp* __p, _Deleter __d, _Alloc __a)
: __shared_ptr<_Tp>(__p, std::move(__d), std::move(__a)) { }

/**
* @brief Construct a %shared_ptr that owns a null pointer
* and the deleter @a __d.
* @param __p A null pointer constant.
* @param __d A deleter.
* @param __a An allocator.
* @post use_count() == 1 && get() == __p
* @throw std::bad_alloc, in which case @a __d(__p) is called.
*
* Requirements: _Deleter's copy constructor and destructor must
* not throw _Alloc's copy constructor and destructor must not
* throw.
*
* The last owner will call __d(__p)
*/
template<typename _Deleter, typename _Alloc>
shared_ptr(nullptr_t __p, _Deleter __d, _Alloc __a)
: __shared_ptr<_Tp>(__p, std::move(__d), std::move(__a)) { }

// Aliasing constructor

/**
* @brief Constructs a `shared_ptr` instance that stores `__p`
* and shares ownership with `__r`.
* @param __r A `shared_ptr`.
* @param __p A pointer that will remain valid while `*__r` is valid.
* @post `get() == __p && use_count() == __r.use_count()`
*
* This can be used to construct a `shared_ptr` to a sub-object
* of an object managed by an existing `shared_ptr`. The complete
* object will remain valid while any `shared_ptr` owns it, even
* if they don't store a pointer to the complete object.
*
* @code
* shared_ptr<pair<int,int>> pii(new pair<int,int>());
* shared_ptr<int> pi(pii, &pii->first);
* assert(pii.use_count() == 2);
* @endcode
*/
template<typename _Yp>
shared_ptr(const shared_ptr<_Yp>& __r, element_type* __p) noexcept
: __shared_ptr<_Tp>(__r, __p) { }

#if __cplusplus > 201703L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2996. Missing rvalue overloads for shared_ptr operations
/**
* @brief Constructs a `shared_ptr` instance that stores `__p`
* and shares ownership with `__r`.
* @param __r A `shared_ptr`.
* @param __p A pointer that will remain valid while `*__r` is valid.
* @post `get() == __p && !__r.use_count() && !__r.get()`
*
* This can be used to construct a `shared_ptr` to a sub-object
* of an object managed by an existing `shared_ptr`. The complete
* object will remain valid while any `shared_ptr` owns it, even
* if they don't store a pointer to the complete object.
*
* @code
* shared_ptr<pair<int,int>> pii(new pair<int,int>());
* shared_ptr<int> pi1(pii, &pii->first);
* assert(pii.use_count() == 2);
* shared_ptr<int> pi2(std::move(pii), &pii->second);
* assert(pii.use_count() == 0);
* @endcode
*/
template<typename _Yp>
shared_ptr(shared_ptr<_Yp>&& __r, element_type* __p) noexcept
: __shared_ptr<_Tp>(std::move(__r), __p) { }
#endif
/**
* @brief If @a __r is empty, constructs an empty %shared_ptr;
* otherwise construct a %shared_ptr that shares ownership
* with @a __r.
* @param __r A %shared_ptr.
* @post get() == __r.get() && use_count() == __r.use_count()
*/
template<typename _Yp,
typename = _Constructible<const shared_ptr<_Yp>&>>
shared_ptr(const shared_ptr<_Yp>& __r) noexcept
: __shared_ptr<_Tp>(__r) { }

/**
* @brief Move-constructs a %shared_ptr instance from @a __r.
* @param __r A %shared_ptr rvalue.
* @post *this contains the old value of @a __r, @a __r is empty.
*/
shared_ptr(shared_ptr&& __r) noexcept
: __shared_ptr<_Tp>(std::move(__r)) { }

/**
* @brief Move-constructs a %shared_ptr instance from @a __r.
* @param __r A %shared_ptr rvalue.
* @post *this contains the old value of @a __r, @a __r is empty.
*/
template<typename _Yp, typename = _Constructible<shared_ptr<_Yp>>>
shared_ptr(shared_ptr<_Yp>&& __r) noexcept
: __shared_ptr<_Tp>(std::move(__r)) { }

/**
* @brief Constructs a %shared_ptr that shares ownership with @a __r
* and stores a copy of the pointer stored in @a __r.
* @param __r A weak_ptr.
* @post use_count() == __r.use_count()
* @throw bad_weak_ptr when __r.expired(),
* in which case the constructor has no effect.
*/
template<typename _Yp, typename = _Constructible<const weak_ptr<_Yp>&>>
explicit shared_ptr(const weak_ptr<_Yp>& __r)
: __shared_ptr<_Tp>(__r) { }

#if _GLIBCXX_USE_DEPRECATED
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
template<typename _Yp, typename = _Constructible<auto_ptr<_Yp>>>
shared_ptr(auto_ptr<_Yp>&& __r);
#pragma GCC diagnostic pop
#endif

// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2399. shared_ptr's constructor from unique_ptr should be constrained
template<typename _Yp, typename _Del,
typename = _Constructible<unique_ptr<_Yp, _Del>>>
shared_ptr(unique_ptr<_Yp, _Del>&& __r)
: __shared_ptr<_Tp>(std::move(__r)) { }

#if __cplusplus <= 201402L && _GLIBCXX_USE_DEPRECATED
// This non-standard constructor exists to support conversions that
// were possible in C++11 and C++14 but are ill-formed in C++17.
// If an exception is thrown this constructor has no effect.
template<typename _Yp, typename _Del,
_Constructible<unique_ptr<_Yp, _Del>, __sp_array_delete>* = 0>
shared_ptr(unique_ptr<_Yp, _Del>&& __r)
: __shared_ptr<_Tp>(std::move(__r), __sp_array_delete()) { }
#endif

/**
* @brief Construct an empty %shared_ptr.
* @post use_count() == 0 && get() == nullptr
*/
constexpr shared_ptr(nullptr_t) noexcept : shared_ptr() { }

shared_ptr& operator=(const shared_ptr&) noexcept = default;

template<typename _Yp>
_Assignable<const shared_ptr<_Yp>&>
operator=(const shared_ptr<_Yp>& __r) noexcept
{
this->__shared_ptr<_Tp>::operator=(__r);
return *this;
}

#if _GLIBCXX_USE_DEPRECATED
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
template<typename _Yp>
_Assignable<auto_ptr<_Yp>>
operator=(auto_ptr<_Yp>&& __r)
{
this->__shared_ptr<_Tp>::operator=(std::move(__r));
return *this;
}
#pragma GCC diagnostic pop
#endif

shared_ptr&
operator=(shared_ptr&& __r) noexcept
{
this->__shared_ptr<_Tp>::operator=(std::move(__r));
return *this;
}

template<class _Yp>
_Assignable<shared_ptr<_Yp>>
operator=(shared_ptr<_Yp>&& __r) noexcept
{
this->__shared_ptr<_Tp>::operator=(std::move(__r));
return *this;
}

template<typename _Yp, typename _Del>
_Assignable<unique_ptr<_Yp, _Del>>
operator=(unique_ptr<_Yp, _Del>&& __r)
{
this->__shared_ptr<_Tp>::operator=(std::move(__r));
return *this;
}

private:
// This constructor is non-standard, it is used by allocate_shared.
template<typename _Alloc, typename... _Args>
shared_ptr(_Sp_alloc_shared_tag<_Alloc> __tag, _Args&&... __args)
: __shared_ptr<_Tp>(__tag, std::forward<_Args>(__args)...)
{ }

template<typename _Yp, typename _Alloc, typename... _Args>
friend shared_ptr<_Yp>
allocate_shared(const _Alloc& __a, _Args&&... __args);

// This constructor is non-standard, it is used by weak_ptr::lock().
shared_ptr(const weak_ptr<_Tp>& __r, std::nothrow_t) noexcept
: __shared_ptr<_Tp>(__r, std::nothrow) { }

friend class weak_ptr<_Tp>;
};

#if __cpp_deduction_guides >= 201606
template<typename _Tp>
shared_ptr(weak_ptr<_Tp>) -> shared_ptr<_Tp>;
template<typename _Tp, typename _Del>
shared_ptr(unique_ptr<_Tp, _Del>) -> shared_ptr<_Tp>;
#endif

// 20.7.2.2.7 shared_ptr comparisons

/// @relates shared_ptr @{

/// Equality operator for shared_ptr objects, compares the stored pointers
template<typename _Tp, typename _Up>
_GLIBCXX_NODISCARD inline bool
operator==(const shared_ptr<_Tp>& __a, const shared_ptr<_Up>& __b) noexcept
{ return __a.get() == __b.get(); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
_GLIBCXX_NODISCARD inline bool
operator==(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
{ return !__a; }

#ifdef __cpp_lib_three_way_comparison
template<typename _Tp, typename _Up>
inline strong_ordering
operator<=>(const shared_ptr<_Tp>& __a,
const shared_ptr<_Up>& __b) noexcept
{ return compare_three_way()(__a.get(), __b.get()); }

template<typename _Tp>
inline strong_ordering
operator<=>(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
{
using pointer = typename shared_ptr<_Tp>::element_type*;
return compare_three_way()(__a.get(), static_cast<pointer>(nullptr));
}
#else
/// shared_ptr comparison with nullptr
template<typename _Tp>
_GLIBCXX_NODISCARD inline bool
operator==(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
{ return !__a; }

/// Inequality operator for shared_ptr objects, compares the stored pointers
template<typename _Tp, typename _Up>
_GLIBCXX_NODISCARD inline bool
operator!=(const shared_ptr<_Tp>& __a, const shared_ptr<_Up>& __b) noexcept
{ return __a.get() != __b.get(); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
_GLIBCXX_NODISCARD inline bool
operator!=(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
{ return (bool)__a; }

/// shared_ptr comparison with nullptr
template<typename _Tp>
_GLIBCXX_NODISCARD inline bool
operator!=(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
{ return (bool)__a; }

/// Relational operator for shared_ptr objects, compares the stored pointers
template<typename _Tp, typename _Up>
_GLIBCXX_NODISCARD inline bool
operator<(const shared_ptr<_Tp>& __a, const shared_ptr<_Up>& __b) noexcept
{
using _Tp_elt = typename shared_ptr<_Tp>::element_type;
using _Up_elt = typename shared_ptr<_Up>::element_type;
using _Vp = typename common_type<_Tp_elt*, _Up_elt*>::type;
return less<_Vp>()(__a.get(), __b.get());
}

/// shared_ptr comparison with nullptr
template<typename _Tp>
_GLIBCXX_NODISCARD inline bool
operator<(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
{
using _Tp_elt = typename shared_ptr<_Tp>::element_type;
return less<_Tp_elt*>()(__a.get(), nullptr);
}

/// shared_ptr comparison with nullptr
template<typename _Tp>
_GLIBCXX_NODISCARD inline bool
operator<(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
{
using _Tp_elt = typename shared_ptr<_Tp>::element_type;
return less<_Tp_elt*>()(nullptr, __a.get());
}

/// Relational operator for shared_ptr objects, compares the stored pointers
template<typename _Tp, typename _Up>
_GLIBCXX_NODISCARD inline bool
operator<=(const shared_ptr<_Tp>& __a, const shared_ptr<_Up>& __b) noexcept
{ return !(__b < __a); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
_GLIBCXX_NODISCARD inline bool
operator<=(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
{ return !(nullptr < __a); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
_GLIBCXX_NODISCARD inline bool
operator<=(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
{ return !(__a < nullptr); }

/// Relational operator for shared_ptr objects, compares the stored pointers
template<typename _Tp, typename _Up>
_GLIBCXX_NODISCARD inline bool
operator>(const shared_ptr<_Tp>& __a, const shared_ptr<_Up>& __b) noexcept
{ return (__b < __a); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
_GLIBCXX_NODISCARD inline bool
operator>(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
{ return nullptr < __a; }

/// shared_ptr comparison with nullptr
template<typename _Tp>
_GLIBCXX_NODISCARD inline bool
operator>(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
{ return __a < nullptr; }

/// Relational operator for shared_ptr objects, compares the stored pointers
template<typename _Tp, typename _Up>
_GLIBCXX_NODISCARD inline bool
operator>=(const shared_ptr<_Tp>& __a, const shared_ptr<_Up>& __b) noexcept
{ return !(__a < __b); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
_GLIBCXX_NODISCARD inline bool
operator>=(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
{ return !(__a < nullptr); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
_GLIBCXX_NODISCARD inline bool
operator>=(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
{ return !(nullptr < __a); }
#endif

// 20.7.2.2.8 shared_ptr specialized algorithms.

/// Swap overload for shared_ptr
template<typename _Tp>
inline void
swap(shared_ptr<_Tp>& __a, shared_ptr<_Tp>& __b) noexcept
{ __a.swap(__b); }

// 20.7.2.2.9 shared_ptr casts.

/// Convert type of `shared_ptr`, via `static_cast`
template<typename _Tp, typename _Up>
inline shared_ptr<_Tp>
static_pointer_cast(const shared_ptr<_Up>& __r) noexcept
{
using _Sp = shared_ptr<_Tp>;
return _Sp(__r, static_cast<typename _Sp::element_type*>(__r.get()));
}

/// Convert type of `shared_ptr`, via `const_cast`
template<typename _Tp, typename _Up>
inline shared_ptr<_Tp>
const_pointer_cast(const shared_ptr<_Up>& __r) noexcept
{
using _Sp = shared_ptr<_Tp>;
return _Sp(__r, const_cast<typename _Sp::element_type*>(__r.get()));
}

/// Convert type of `shared_ptr`, via `dynamic_cast`
template<typename _Tp, typename _Up>
inline shared_ptr<_Tp>
dynamic_pointer_cast(const shared_ptr<_Up>& __r) noexcept
{
using _Sp = shared_ptr<_Tp>;
if (auto* __p = dynamic_cast<typename _Sp::element_type*>(__r.get()))
return _Sp(__r, __p);
return _Sp();
}

#if __cplusplus >= 201703L
/// Convert type of `shared_ptr`, via `reinterpret_cast`
template<typename _Tp, typename _Up>
inline shared_ptr<_Tp>
reinterpret_pointer_cast(const shared_ptr<_Up>& __r) noexcept
{
using _Sp = shared_ptr<_Tp>;
return _Sp(__r, reinterpret_cast<typename _Sp::element_type*>(__r.get()));
}

#if __cplusplus > 201703L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2996. Missing rvalue overloads for shared_ptr operations

/// Convert type of `shared_ptr` rvalue, via `static_cast`
template<typename _Tp, typename _Up>
inline shared_ptr<_Tp>
static_pointer_cast(shared_ptr<_Up>&& __r) noexcept
{
using _Sp = shared_ptr<_Tp>;
return _Sp(std::move(__r),
static_cast<typename _Sp::element_type*>(__r.get()));
}

/// Convert type of `shared_ptr` rvalue, via `const_cast`
template<typename _Tp, typename _Up>
inline shared_ptr<_Tp>
const_pointer_cast(shared_ptr<_Up>&& __r) noexcept
{
using _Sp = shared_ptr<_Tp>;
return _Sp(std::move(__r),
const_cast<typename _Sp::element_type*>(__r.get()));
}

/// Convert type of `shared_ptr` rvalue, via `dynamic_cast`
template<typename _Tp, typename _Up>
inline shared_ptr<_Tp>
dynamic_pointer_cast(shared_ptr<_Up>&& __r) noexcept
{
using _Sp = shared_ptr<_Tp>;
if (auto* __p = dynamic_cast<typename _Sp::element_type*>(__r.get()))
return _Sp(std::move(__r), __p);
return _Sp();
}

/// Convert type of `shared_ptr` rvalue, via `reinterpret_cast`
template<typename _Tp, typename _Up>
inline shared_ptr<_Tp>
reinterpret_pointer_cast(shared_ptr<_Up>&& __r) noexcept
{
using _Sp = shared_ptr<_Tp>;
return _Sp(std::move(__r),
reinterpret_cast<typename _Sp::element_type*>(__r.get()));
}
#endif // C++20
#endif // C++17

/// @}

/**
* @brief A non-owning observer for a pointer owned by a shared_ptr
*
* A weak_ptr provides a safe alternative to a raw pointer when you want
* a non-owning reference to an object that is managed by a shared_ptr.
*
* Unlike a raw pointer, a weak_ptr can be converted to a new shared_ptr
* that shares ownership with every other shared_ptr that already owns
* the pointer. In other words you can upgrade from a non-owning "weak"
* reference to an owning shared_ptr, without having access to any of
* the existing shared_ptr objects.
*
* Also unlike a raw pointer, a weak_ptr does not become "dangling" after
* the object it points to has been destroyed. Instead, a weak_ptr
* becomes _expired_ and can no longer be converted to a shared_ptr that
* owns the freed pointer, so you cannot accidentally access the pointed-to
* object after it has been destroyed.
*/
template<typename _Tp>
class weak_ptr : public __weak_ptr<_Tp>
{
template<typename _Arg>
using _Constructible = typename enable_if<
is_constructible<__weak_ptr<_Tp>, _Arg>::value
>::type;

template<typename _Arg>
using _Assignable = typename enable_if<
is_assignable<__weak_ptr<_Tp>&, _Arg>::value, weak_ptr&
>::type;

public:
constexpr weak_ptr() noexcept = default;

template<typename _Yp,
typename = _Constructible<const shared_ptr<_Yp>&>>
weak_ptr(const shared_ptr<_Yp>& __r) noexcept
: __weak_ptr<_Tp>(__r) { }

weak_ptr(const weak_ptr&) noexcept = default;

template<typename _Yp, typename = _Constructible<const weak_ptr<_Yp>&>>
weak_ptr(const weak_ptr<_Yp>& __r) noexcept
: __weak_ptr<_Tp>(__r) { }

weak_ptr(weak_ptr&&) noexcept = default;

template<typename _Yp, typename = _Constructible<weak_ptr<_Yp>>>
weak_ptr(weak_ptr<_Yp>&& __r) noexcept
: __weak_ptr<_Tp>(std::move(__r)) { }

weak_ptr&
operator=(const weak_ptr& __r) noexcept = default;

template<typename _Yp>
_Assignable<const weak_ptr<_Yp>&>
operator=(const weak_ptr<_Yp>& __r) noexcept
{
this->__weak_ptr<_Tp>::operator=(__r);
return *this;
}

template<typename _Yp>
_Assignable<const shared_ptr<_Yp>&>
operator=(const shared_ptr<_Yp>& __r) noexcept
{
this->__weak_ptr<_Tp>::operator=(__r);
return *this;
}

weak_ptr&
operator=(weak_ptr&& __r) noexcept = default;

template<typename _Yp>
_Assignable<weak_ptr<_Yp>>
operator=(weak_ptr<_Yp>&& __r) noexcept
{
this->__weak_ptr<_Tp>::operator=(std::move(__r));
return *this;
}

shared_ptr<_Tp>
lock() const noexcept
{ return shared_ptr<_Tp>(*this, std::nothrow); }
};

#if __cpp_deduction_guides >= 201606
template<typename _Tp>
weak_ptr(shared_ptr<_Tp>) -> weak_ptr<_Tp>;
#endif

// 20.7.2.3.6 weak_ptr specialized algorithms.
/// Swap overload for weak_ptr
/// @relates weak_ptr
template<typename _Tp>
inline void
swap(weak_ptr<_Tp>& __a, weak_ptr<_Tp>& __b) noexcept
{ __a.swap(__b); }


/// Primary template owner_less
template<typename _Tp = void>
struct owner_less;

/// Void specialization of owner_less compares either shared_ptr or weak_ptr
template<>
struct owner_less<void> : _Sp_owner_less<void, void>
{ };

/// Partial specialization of owner_less for shared_ptr.
template<typename _Tp>
struct owner_less<shared_ptr<_Tp>>
: public _Sp_owner_less<shared_ptr<_Tp>, weak_ptr<_Tp>>
{ };

/// Partial specialization of owner_less for weak_ptr.
template<typename _Tp>
struct owner_less<weak_ptr<_Tp>>
: public _Sp_owner_less<weak_ptr<_Tp>, shared_ptr<_Tp>>
{ };

/**
* @brief Base class allowing use of member function shared_from_this.
*/
template<typename _Tp>
class enable_shared_from_this
{
protected:
constexpr enable_shared_from_this() noexcept { }

enable_shared_from_this(const enable_shared_from_this&) noexcept { }

enable_shared_from_this&
operator=(const enable_shared_from_this&) noexcept
{ return *this; }

~enable_shared_from_this() { }

public:
shared_ptr<_Tp>
shared_from_this()
{ return shared_ptr<_Tp>(this->_M_weak_this); }

shared_ptr<const _Tp>
shared_from_this() const
{ return shared_ptr<const _Tp>(this->_M_weak_this); }

#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
#define __cpp_lib_enable_shared_from_this 201603
weak_ptr<_Tp>
weak_from_this() noexcept
{ return this->_M_weak_this; }

weak_ptr<const _Tp>
weak_from_this() const noexcept
{ return this->_M_weak_this; }
#endif

private:
template<typename _Tp1>
void
_M_weak_assign(_Tp1* __p, const __shared_count<>& __n) const noexcept
{ _M_weak_this._M_assign(__p, __n); }

// Found by ADL when this is an associated class.
friend const enable_shared_from_this*
__enable_shared_from_this_base(const __shared_count<>&,
const enable_shared_from_this* __p)
{ return __p; }

template<typename, _Lock_policy>
friend class __shared_ptr;

mutable weak_ptr<_Tp> _M_weak_this;
};

/// @relates shared_ptr @{

/**
* @brief Create an object that is owned by a shared_ptr.
* @param __a An allocator.
* @param __args Arguments for the @a _Tp object's constructor.
* @return A shared_ptr that owns the newly created object.
* @throw An exception thrown from @a _Alloc::allocate or from the
* constructor of @a _Tp.
*
* A copy of @a __a will be used to allocate memory for the shared_ptr
* and the new object.
*/
template<typename _Tp, typename _Alloc, typename... _Args>
inline shared_ptr<_Tp>
allocate_shared(const _Alloc& __a, _Args&&... __args)
{
static_assert(!is_array<_Tp>::value, "make_shared<T[]> not supported");

return shared_ptr<_Tp>(_Sp_alloc_shared_tag<_Alloc>{__a},
std::forward<_Args>(__args)...);
}

/**
* @brief Create an object that is owned by a shared_ptr.
* @param __args Arguments for the @a _Tp object's constructor.
* @return A shared_ptr that owns the newly created object.
* @throw std::bad_alloc, or an exception thrown from the
* constructor of @a _Tp.
*/
template<typename _Tp, typename... _Args>
inline shared_ptr<_Tp>
make_shared(_Args&&... __args)
{
typedef typename std::remove_cv<_Tp>::type _Tp_nc;
return std::allocate_shared<_Tp>(std::allocator<_Tp_nc>(),
std::forward<_Args>(__args)...);
}

/// std::hash specialization for shared_ptr.
template<typename _Tp>
struct hash<shared_ptr<_Tp>>
: public __hash_base<size_t, shared_ptr<_Tp>>
{
size_t
operator()(const shared_ptr<_Tp>& __s) const noexcept
{
return std::hash<typename shared_ptr<_Tp>::element_type*>()(__s.get());
}
};

/// @} relates shared_ptr
/// @} group pointer_abstractions

#if __cplusplus >= 201703L
namespace __detail::__variant
{
template<typename> struct _Never_valueless_alt; // see <variant>

// Provide the strong exception-safety guarantee when emplacing a
// shared_ptr into a variant.
template<typename _Tp>
struct _Never_valueless_alt<std::shared_ptr<_Tp>>
: std::true_type
{ };

// Provide the strong exception-safety guarantee when emplacing a
// weak_ptr into a variant.
template<typename _Tp>
struct _Never_valueless_alt<std::weak_ptr<_Tp>>
: std::true_type
{ };
} // namespace __detail::__variant
#endif // C++17

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace

#endif // _SHARED_PTR_H
shared_ptr_base.h
shared_ptr_base.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
// shared_ptr and weak_ptr implementation details -*- C++ -*-

// Copyright (C) 2007-2021 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.

// GCC Note: Based on files from version 1.32.0 of the Boost library.

// shared_count.hpp
// Copyright (c) 2001, 2002, 2003 Peter Dimov and Multi Media Ltd.

// shared_ptr.hpp
// Copyright (C) 1998, 1999 Greg Colvin and Beman Dawes.
// Copyright (C) 2001, 2002, 2003 Peter Dimov

// weak_ptr.hpp
// Copyright (C) 2001, 2002, 2003 Peter Dimov

// enable_shared_from_this.hpp
// Copyright (C) 2002 Peter Dimov

// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

/** @file bits/shared_ptr_base.h
* This is an internal header file, included by other library headers.
* Do not attempt to use it directly. @headername{memory}
*/

#ifndef _SHARED_PTR_BASE_H
#define _SHARED_PTR_BASE_H 1

#include <typeinfo>
#include <bits/allocated_ptr.h>
#include <bits/allocator.h>
#include <bits/exception_defines.h>
#include <bits/functional_hash.h>
#include <bits/refwrap.h>
#include <bits/stl_function.h> // std::less
#include <bits/unique_ptr.h>
#include <ext/aligned_buffer.h>
#include <ext/atomicity.h>
#include <ext/concurrence.h>
#if __cplusplus > 201703L
# include <compare>
#endif

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

#if _GLIBCXX_USE_DEPRECATED
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
template<typename> class auto_ptr;
#pragma GCC diagnostic pop
#endif

/**
* @brief Exception possibly thrown by @c shared_ptr.
* @ingroup exceptions
*/
class bad_weak_ptr : public std::exception
{
public:
virtual char const* what() const noexcept;

virtual ~bad_weak_ptr() noexcept;
};

// Substitute for bad_weak_ptr object in the case of -fno-exceptions.
inline void
__throw_bad_weak_ptr()
{ _GLIBCXX_THROW_OR_ABORT(bad_weak_ptr()); }

using __gnu_cxx::_Lock_policy;
using __gnu_cxx::__default_lock_policy;
using __gnu_cxx::_S_single;
using __gnu_cxx::_S_mutex;
using __gnu_cxx::_S_atomic;

// Empty helper class except when the template argument is _S_mutex.
template<_Lock_policy _Lp>
class _Mutex_base
{
protected:
// The atomic policy uses fully-fenced builtins, single doesn't care.
enum { _S_need_barriers = 0 };
};

template<>
class _Mutex_base<_S_mutex>
: public __gnu_cxx::__mutex
{
protected:
// This policy is used when atomic builtins are not available.
// The replacement atomic operations might not have the necessary
// memory barriers.
enum { _S_need_barriers = 1 };
};

template<_Lock_policy _Lp = __default_lock_policy>
class _Sp_counted_base
: public _Mutex_base<_Lp>
{
public:
_Sp_counted_base() noexcept
: _M_use_count(1), _M_weak_count(1) { }

virtual
~_Sp_counted_base() noexcept
{ }

// Called when _M_use_count drops to zero, to release the resources
// managed by *this.
virtual void
_M_dispose() noexcept = 0;

// Called when _M_weak_count drops to zero.
virtual void
_M_destroy() noexcept
{ delete this; }

virtual void*
_M_get_deleter(const std::type_info&) noexcept = 0;

void
_M_add_ref_copy()
{ __gnu_cxx::__atomic_add_dispatch(&_M_use_count, 1); }

void
_M_add_ref_lock()
{
if (!_M_add_ref_lock_nothrow())
__throw_bad_weak_ptr();
}

bool
_M_add_ref_lock_nothrow() noexcept;

void
_M_release() noexcept
{
// Be race-detector-friendly. For more info see bits/c++config.
_GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_use_count);
if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1) == 1)
{
_GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_use_count);
_M_dispose();
// There must be a memory barrier between dispose() and destroy()
// to ensure that the effects of dispose() are observed in the
// thread that runs destroy().
// See http://gcc.gnu.org/ml/libstdc++/2005-11/msg00136.html
if (_Mutex_base<_Lp>::_S_need_barriers)
{
__atomic_thread_fence (__ATOMIC_ACQ_REL);
}

// Be race-detector-friendly. For more info see bits/c++config.
_GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_weak_count);
if (__gnu_cxx::__exchange_and_add_dispatch(&_M_weak_count,
-1) == 1)
{
_GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_weak_count);
_M_destroy();
}
}
}

void
_M_weak_add_ref() noexcept
{ __gnu_cxx::__atomic_add_dispatch(&_M_weak_count, 1); }

void
_M_weak_release() noexcept
{
// Be race-detector-friendly. For more info see bits/c++config.
_GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_weak_count);
if (__gnu_cxx::__exchange_and_add_dispatch(&_M_weak_count, -1) == 1)
{
_GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_weak_count);
if (_Mutex_base<_Lp>::_S_need_barriers)
{
// See _M_release(),
// destroy() must observe results of dispose()
__atomic_thread_fence (__ATOMIC_ACQ_REL);
}
_M_destroy();
}
}

long
_M_get_use_count() const noexcept
{
// No memory barrier is used here so there is no synchronization
// with other threads.
return __atomic_load_n(&_M_use_count, __ATOMIC_RELAXED);
}

private:
_Sp_counted_base(_Sp_counted_base const&) = delete;
_Sp_counted_base& operator=(_Sp_counted_base const&) = delete;

_Atomic_word _M_use_count; // #shared
_Atomic_word _M_weak_count; // #weak + (#shared != 0)
};

template<>
inline bool
_Sp_counted_base<_S_single>::
_M_add_ref_lock_nothrow() noexcept
{
if (_M_use_count == 0)
return false;
++_M_use_count;
return true;
}

template<>
inline bool
_Sp_counted_base<_S_mutex>::
_M_add_ref_lock_nothrow() noexcept
{
__gnu_cxx::__scoped_lock sentry(*this);
if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, 1) == 0)
{
_M_use_count = 0;
return false;
}
return true;
}

template<>
inline bool
_Sp_counted_base<_S_atomic>::
_M_add_ref_lock_nothrow() noexcept
{
// Perform lock-free add-if-not-zero operation.
_Atomic_word __count = _M_get_use_count();
do
{
if (__count == 0)
return false;
// Replace the current counter value with the old value + 1, as
// long as it's not changed meanwhile.
}
while (!__atomic_compare_exchange_n(&_M_use_count, &__count, __count + 1,
true, __ATOMIC_ACQ_REL,
__ATOMIC_RELAXED));
return true;
}

template<>
inline void
_Sp_counted_base<_S_single>::_M_add_ref_copy()
{ ++_M_use_count; }

template<>
inline void
_Sp_counted_base<_S_single>::_M_release() noexcept
{
if (--_M_use_count == 0)
{
_M_dispose();
if (--_M_weak_count == 0)
_M_destroy();
}
}

template<>
inline void
_Sp_counted_base<_S_single>::_M_weak_add_ref() noexcept
{ ++_M_weak_count; }

template<>
inline void
_Sp_counted_base<_S_single>::_M_weak_release() noexcept
{
if (--_M_weak_count == 0)
_M_destroy();
}

template<>
inline long
_Sp_counted_base<_S_single>::_M_get_use_count() const noexcept
{ return _M_use_count; }


// Forward declarations.
template<typename _Tp, _Lock_policy _Lp = __default_lock_policy>
class __shared_ptr;

template<typename _Tp, _Lock_policy _Lp = __default_lock_policy>
class __weak_ptr;

template<typename _Tp, _Lock_policy _Lp = __default_lock_policy>
class __enable_shared_from_this;

template<typename _Tp>
class shared_ptr;

template<typename _Tp>
class weak_ptr;

template<typename _Tp>
struct owner_less;

template<typename _Tp>
class enable_shared_from_this;

template<_Lock_policy _Lp = __default_lock_policy>
class __weak_count;

template<_Lock_policy _Lp = __default_lock_policy>
class __shared_count;


// Counted ptr with no deleter or allocator support
template<typename _Ptr, _Lock_policy _Lp>
class _Sp_counted_ptr final : public _Sp_counted_base<_Lp>
{
public:
explicit
_Sp_counted_ptr(_Ptr __p) noexcept
: _M_ptr(__p) { }

virtual void
_M_dispose() noexcept
{ delete _M_ptr; }

virtual void
_M_destroy() noexcept
{ delete this; }

virtual void*
_M_get_deleter(const std::type_info&) noexcept
{ return nullptr; }

_Sp_counted_ptr(const _Sp_counted_ptr&) = delete;
_Sp_counted_ptr& operator=(const _Sp_counted_ptr&) = delete;

private:
_Ptr _M_ptr;
};

template<>
inline void
_Sp_counted_ptr<nullptr_t, _S_single>::_M_dispose() noexcept { }

template<>
inline void
_Sp_counted_ptr<nullptr_t, _S_mutex>::_M_dispose() noexcept { }

template<>
inline void
_Sp_counted_ptr<nullptr_t, _S_atomic>::_M_dispose() noexcept { }

template<int _Nm, typename _Tp,
bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
struct _Sp_ebo_helper;

/// Specialization using EBO.
template<int _Nm, typename _Tp>
struct _Sp_ebo_helper<_Nm, _Tp, true> : private _Tp
{
explicit _Sp_ebo_helper(const _Tp& __tp) : _Tp(__tp) { }
explicit _Sp_ebo_helper(_Tp&& __tp) : _Tp(std::move(__tp)) { }

static _Tp&
_S_get(_Sp_ebo_helper& __eboh) { return static_cast<_Tp&>(__eboh); }
};

/// Specialization not using EBO.
template<int _Nm, typename _Tp>
struct _Sp_ebo_helper<_Nm, _Tp, false>
{
explicit _Sp_ebo_helper(const _Tp& __tp) : _M_tp(__tp) { }
explicit _Sp_ebo_helper(_Tp&& __tp) : _M_tp(std::move(__tp)) { }

static _Tp&
_S_get(_Sp_ebo_helper& __eboh)
{ return __eboh._M_tp; }

private:
_Tp _M_tp;
};

// Support for custom deleter and/or allocator
template<typename _Ptr, typename _Deleter, typename _Alloc, _Lock_policy _Lp>
class _Sp_counted_deleter final : public _Sp_counted_base<_Lp>
{
class _Impl : _Sp_ebo_helper<0, _Deleter>, _Sp_ebo_helper<1, _Alloc>
{
typedef _Sp_ebo_helper<0, _Deleter> _Del_base;
typedef _Sp_ebo_helper<1, _Alloc> _Alloc_base;

public:
_Impl(_Ptr __p, _Deleter __d, const _Alloc& __a) noexcept
: _Del_base(std::move(__d)), _Alloc_base(__a), _M_ptr(__p)
{ }

_Deleter& _M_del() noexcept { return _Del_base::_S_get(*this); }
_Alloc& _M_alloc() noexcept { return _Alloc_base::_S_get(*this); }

_Ptr _M_ptr;
};

public:
using __allocator_type = __alloc_rebind<_Alloc, _Sp_counted_deleter>;

// __d(__p) must not throw.
_Sp_counted_deleter(_Ptr __p, _Deleter __d) noexcept
: _M_impl(__p, std::move(__d), _Alloc()) { }

// __d(__p) must not throw.
_Sp_counted_deleter(_Ptr __p, _Deleter __d, const _Alloc& __a) noexcept
: _M_impl(__p, std::move(__d), __a) { }

~_Sp_counted_deleter() noexcept { }

virtual void
_M_dispose() noexcept
{ _M_impl._M_del()(_M_impl._M_ptr); }

virtual void
_M_destroy() noexcept
{
__allocator_type __a(_M_impl._M_alloc());
__allocated_ptr<__allocator_type> __guard_ptr{ __a, this };
this->~_Sp_counted_deleter();
}

virtual void*
_M_get_deleter(const type_info& __ti [[__gnu__::__unused__]]) noexcept
{
#if __cpp_rtti
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2400. shared_ptr's get_deleter() should use addressof()
return __ti == typeid(_Deleter)
? std::__addressof(_M_impl._M_del())
: nullptr;
#else
return nullptr;
#endif
}

private:
_Impl _M_impl;
};

// helpers for make_shared / allocate_shared

struct _Sp_make_shared_tag
{
private:
template<typename _Tp, typename _Alloc, _Lock_policy _Lp>
friend class _Sp_counted_ptr_inplace;

static const type_info&
_S_ti() noexcept _GLIBCXX_VISIBILITY(default)
{
alignas(type_info) static constexpr char __tag[sizeof(type_info)] = { };
return reinterpret_cast<const type_info&>(__tag);
}

static bool _S_eq(const type_info&) noexcept;
};

template<typename _Alloc>
struct _Sp_alloc_shared_tag
{
const _Alloc& _M_a;
};

template<typename _Tp, typename _Alloc, _Lock_policy _Lp>
class _Sp_counted_ptr_inplace final : public _Sp_counted_base<_Lp>
{
class _Impl : _Sp_ebo_helper<0, _Alloc>
{
typedef _Sp_ebo_helper<0, _Alloc> _A_base;

public:
explicit _Impl(_Alloc __a) noexcept : _A_base(__a) { }

_Alloc& _M_alloc() noexcept { return _A_base::_S_get(*this); }

__gnu_cxx::__aligned_buffer<_Tp> _M_storage;
};

public:
using __allocator_type = __alloc_rebind<_Alloc, _Sp_counted_ptr_inplace>;

// Alloc parameter is not a reference so doesn't alias anything in __args
template<typename... _Args>
_Sp_counted_ptr_inplace(_Alloc __a, _Args&&... __args)
: _M_impl(__a)
{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2070. allocate_shared should use allocator_traits<A>::construct
allocator_traits<_Alloc>::construct(__a, _M_ptr(),
std::forward<_Args>(__args)...); // might throw
}

~_Sp_counted_ptr_inplace() noexcept { }

virtual void
_M_dispose() noexcept
{
allocator_traits<_Alloc>::destroy(_M_impl._M_alloc(), _M_ptr());
}

// Override because the allocator needs to know the dynamic type
virtual void
_M_destroy() noexcept
{
__allocator_type __a(_M_impl._M_alloc());
__allocated_ptr<__allocator_type> __guard_ptr{ __a, this };
this->~_Sp_counted_ptr_inplace();
}

private:
friend class __shared_count<_Lp>; // To be able to call _M_ptr().

// No longer used, but code compiled against old libstdc++ headers
// might still call it from __shared_ptr ctor to get the pointer out.
virtual void*
_M_get_deleter(const std::type_info& __ti) noexcept override
{
auto __ptr = const_cast<typename remove_cv<_Tp>::type*>(_M_ptr());
// Check for the fake type_info first, so we don't try to access it
// as a real type_info object. Otherwise, check if it's the real
// type_info for this class. With RTTI enabled we can check directly,
// or call a library function to do it.
if (&__ti == &_Sp_make_shared_tag::_S_ti()
||
#if __cpp_rtti
__ti == typeid(_Sp_make_shared_tag)
#else
_Sp_make_shared_tag::_S_eq(__ti)
#endif
)
return __ptr;
return nullptr;
}

_Tp* _M_ptr() noexcept { return _M_impl._M_storage._M_ptr(); }

_Impl _M_impl;
};

// The default deleter for shared_ptr<T[]> and shared_ptr<T[N]>.
struct __sp_array_delete
{
template<typename _Yp>
void operator()(_Yp* __p) const { delete[] __p; }
};

template<_Lock_policy _Lp>
class __shared_count
{
template<typename _Tp>
struct __not_alloc_shared_tag { using type = void; };

template<typename _Tp>
struct __not_alloc_shared_tag<_Sp_alloc_shared_tag<_Tp>> { };

public:
constexpr __shared_count() noexcept : _M_pi(0)
{ }

template<typename _Ptr>
explicit
__shared_count(_Ptr __p) : _M_pi(0)
{
__try
{
_M_pi = new _Sp_counted_ptr<_Ptr, _Lp>(__p);
}
__catch(...)
{
delete __p;
__throw_exception_again;
}
}

template<typename _Ptr>
__shared_count(_Ptr __p, /* is_array = */ false_type)
: __shared_count(__p)
{ }

template<typename _Ptr>
__shared_count(_Ptr __p, /* is_array = */ true_type)
: __shared_count(__p, __sp_array_delete{}, allocator<void>())
{ }

template<typename _Ptr, typename _Deleter,
typename = typename __not_alloc_shared_tag<_Deleter>::type>
__shared_count(_Ptr __p, _Deleter __d)
: __shared_count(__p, std::move(__d), allocator<void>())
{ }

template<typename _Ptr, typename _Deleter, typename _Alloc,
typename = typename __not_alloc_shared_tag<_Deleter>::type>
__shared_count(_Ptr __p, _Deleter __d, _Alloc __a) : _M_pi(0)
{
typedef _Sp_counted_deleter<_Ptr, _Deleter, _Alloc, _Lp> _Sp_cd_type;
__try
{
typename _Sp_cd_type::__allocator_type __a2(__a);
auto __guard = std::__allocate_guarded(__a2);
_Sp_cd_type* __mem = __guard.get();
::new (__mem) _Sp_cd_type(__p, std::move(__d), std::move(__a));
_M_pi = __mem;
__guard = nullptr;
}
__catch(...)
{
__d(__p); // Call _Deleter on __p.
__throw_exception_again;
}
}

template<typename _Tp, typename _Alloc, typename... _Args>
__shared_count(_Tp*& __p, _Sp_alloc_shared_tag<_Alloc> __a,
_Args&&... __args)
{
typedef _Sp_counted_ptr_inplace<_Tp, _Alloc, _Lp> _Sp_cp_type;
typename _Sp_cp_type::__allocator_type __a2(__a._M_a);
auto __guard = std::__allocate_guarded(__a2);
_Sp_cp_type* __mem = __guard.get();
auto __pi = ::new (__mem)
_Sp_cp_type(__a._M_a, std::forward<_Args>(__args)...);
__guard = nullptr;
_M_pi = __pi;
__p = __pi->_M_ptr();
}

#if _GLIBCXX_USE_DEPRECATED
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
// Special case for auto_ptr<_Tp> to provide the strong guarantee.
template<typename _Tp>
explicit
__shared_count(std::auto_ptr<_Tp>&& __r);
#pragma GCC diagnostic pop
#endif

// Special case for unique_ptr<_Tp,_Del> to provide the strong guarantee.
template<typename _Tp, typename _Del>
explicit
__shared_count(std::unique_ptr<_Tp, _Del>&& __r) : _M_pi(0)
{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2415. Inconsistency between unique_ptr and shared_ptr
if (__r.get() == nullptr)
return;

using _Ptr = typename unique_ptr<_Tp, _Del>::pointer;
using _Del2 = typename conditional<is_reference<_Del>::value,
reference_wrapper<typename remove_reference<_Del>::type>,
_Del>::type;
using _Sp_cd_type
= _Sp_counted_deleter<_Ptr, _Del2, allocator<void>, _Lp>;
using _Alloc = allocator<_Sp_cd_type>;
using _Alloc_traits = allocator_traits<_Alloc>;
_Alloc __a;
_Sp_cd_type* __mem = _Alloc_traits::allocate(__a, 1);
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 3548. shared_ptr construction from unique_ptr should move
// (not copy) the deleter
_Alloc_traits::construct(__a, __mem, __r.release(),
std::forward<_Del>(__r.get_deleter()));
_M_pi = __mem;
}

// Throw bad_weak_ptr when __r._M_get_use_count() == 0.
explicit __shared_count(const __weak_count<_Lp>& __r);

// Does not throw if __r._M_get_use_count() == 0, caller must check.
explicit
__shared_count(const __weak_count<_Lp>& __r, std::nothrow_t) noexcept;

~__shared_count() noexcept
{
if (_M_pi != nullptr)
_M_pi->_M_release();
}

__shared_count(const __shared_count& __r) noexcept
: _M_pi(__r._M_pi)
{
if (_M_pi != nullptr)
_M_pi->_M_add_ref_copy();
}

__shared_count&
operator=(const __shared_count& __r) noexcept
{
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
if (__tmp != _M_pi)
{
if (__tmp != nullptr)
__tmp->_M_add_ref_copy();
if (_M_pi != nullptr)
_M_pi->_M_release();
_M_pi = __tmp;
}
return *this;
}

void
_M_swap(__shared_count& __r) noexcept
{
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
__r._M_pi = _M_pi;
_M_pi = __tmp;
}

long
_M_get_use_count() const noexcept
{ return _M_pi ? _M_pi->_M_get_use_count() : 0; }

bool
_M_unique() const noexcept
{ return this->_M_get_use_count() == 1; }

void*
_M_get_deleter(const std::type_info& __ti) const noexcept
{ return _M_pi ? _M_pi->_M_get_deleter(__ti) : nullptr; }

bool
_M_less(const __shared_count& __rhs) const noexcept
{ return std::less<_Sp_counted_base<_Lp>*>()(this->_M_pi, __rhs._M_pi); }

bool
_M_less(const __weak_count<_Lp>& __rhs) const noexcept
{ return std::less<_Sp_counted_base<_Lp>*>()(this->_M_pi, __rhs._M_pi); }

// Friend function injected into enclosing namespace and found by ADL
friend inline bool
operator==(const __shared_count& __a, const __shared_count& __b) noexcept
{ return __a._M_pi == __b._M_pi; }

private:
friend class __weak_count<_Lp>;

_Sp_counted_base<_Lp>* _M_pi;
};


template<_Lock_policy _Lp>
class __weak_count
{
public:
constexpr __weak_count() noexcept : _M_pi(nullptr)
{ }

__weak_count(const __shared_count<_Lp>& __r) noexcept
: _M_pi(__r._M_pi)
{
if (_M_pi != nullptr)
_M_pi->_M_weak_add_ref();
}

__weak_count(const __weak_count& __r) noexcept
: _M_pi(__r._M_pi)
{
if (_M_pi != nullptr)
_M_pi->_M_weak_add_ref();
}

__weak_count(__weak_count&& __r) noexcept
: _M_pi(__r._M_pi)
{ __r._M_pi = nullptr; }

~__weak_count() noexcept
{
if (_M_pi != nullptr)
_M_pi->_M_weak_release();
}

__weak_count&
operator=(const __shared_count<_Lp>& __r) noexcept
{
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
if (__tmp != nullptr)
__tmp->_M_weak_add_ref();
if (_M_pi != nullptr)
_M_pi->_M_weak_release();
_M_pi = __tmp;
return *this;
}

__weak_count&
operator=(const __weak_count& __r) noexcept
{
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
if (__tmp != nullptr)
__tmp->_M_weak_add_ref();
if (_M_pi != nullptr)
_M_pi->_M_weak_release();
_M_pi = __tmp;
return *this;
}

__weak_count&
operator=(__weak_count&& __r) noexcept
{
if (_M_pi != nullptr)
_M_pi->_M_weak_release();
_M_pi = __r._M_pi;
__r._M_pi = nullptr;
return *this;
}

void
_M_swap(__weak_count& __r) noexcept
{
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
__r._M_pi = _M_pi;
_M_pi = __tmp;
}

long
_M_get_use_count() const noexcept
{ return _M_pi != nullptr ? _M_pi->_M_get_use_count() : 0; }

bool
_M_less(const __weak_count& __rhs) const noexcept
{ return std::less<_Sp_counted_base<_Lp>*>()(this->_M_pi, __rhs._M_pi); }

bool
_M_less(const __shared_count<_Lp>& __rhs) const noexcept
{ return std::less<_Sp_counted_base<_Lp>*>()(this->_M_pi, __rhs._M_pi); }

// Friend function injected into enclosing namespace and found by ADL
friend inline bool
operator==(const __weak_count& __a, const __weak_count& __b) noexcept
{ return __a._M_pi == __b._M_pi; }

private:
friend class __shared_count<_Lp>;

_Sp_counted_base<_Lp>* _M_pi;
};

// Now that __weak_count is defined we can define this constructor:
template<_Lock_policy _Lp>
inline
__shared_count<_Lp>::__shared_count(const __weak_count<_Lp>& __r)
: _M_pi(__r._M_pi)
{
if (_M_pi == nullptr || !_M_pi->_M_add_ref_lock_nothrow())
__throw_bad_weak_ptr();
}

// Now that __weak_count is defined we can define this constructor:
template<_Lock_policy _Lp>
inline
__shared_count<_Lp>::
__shared_count(const __weak_count<_Lp>& __r, std::nothrow_t) noexcept
: _M_pi(__r._M_pi)
{
if (_M_pi && !_M_pi->_M_add_ref_lock_nothrow())
_M_pi = nullptr;
}

#define __cpp_lib_shared_ptr_arrays 201611L

// Helper traits for shared_ptr of array:

// A pointer type Y* is said to be compatible with a pointer type T* when
// either Y* is convertible to T* or Y is U[N] and T is U cv [].
template<typename _Yp_ptr, typename _Tp_ptr>
struct __sp_compatible_with
: false_type
{ };

template<typename _Yp, typename _Tp>
struct __sp_compatible_with<_Yp*, _Tp*>
: is_convertible<_Yp*, _Tp*>::type
{ };

template<typename _Up, size_t _Nm>
struct __sp_compatible_with<_Up(*)[_Nm], _Up(*)[]>
: true_type
{ };

template<typename _Up, size_t _Nm>
struct __sp_compatible_with<_Up(*)[_Nm], const _Up(*)[]>
: true_type
{ };

template<typename _Up, size_t _Nm>
struct __sp_compatible_with<_Up(*)[_Nm], volatile _Up(*)[]>
: true_type
{ };

template<typename _Up, size_t _Nm>
struct __sp_compatible_with<_Up(*)[_Nm], const volatile _Up(*)[]>
: true_type
{ };

// Test conversion from Y(*)[N] to U(*)[N] without forming invalid type Y[N].
template<typename _Up, size_t _Nm, typename _Yp, typename = void>
struct __sp_is_constructible_arrN
: false_type
{ };

template<typename _Up, size_t _Nm, typename _Yp>
struct __sp_is_constructible_arrN<_Up, _Nm, _Yp, __void_t<_Yp[_Nm]>>
: is_convertible<_Yp(*)[_Nm], _Up(*)[_Nm]>::type
{ };

// Test conversion from Y(*)[] to U(*)[] without forming invalid type Y[].
template<typename _Up, typename _Yp, typename = void>
struct __sp_is_constructible_arr
: false_type
{ };

template<typename _Up, typename _Yp>
struct __sp_is_constructible_arr<_Up, _Yp, __void_t<_Yp[]>>
: is_convertible<_Yp(*)[], _Up(*)[]>::type
{ };

// Trait to check if shared_ptr<T> can be constructed from Y*.
template<typename _Tp, typename _Yp>
struct __sp_is_constructible;

// When T is U[N], Y(*)[N] shall be convertible to T*;
template<typename _Up, size_t _Nm, typename _Yp>
struct __sp_is_constructible<_Up[_Nm], _Yp>
: __sp_is_constructible_arrN<_Up, _Nm, _Yp>::type
{ };

// when T is U[], Y(*)[] shall be convertible to T*;
template<typename _Up, typename _Yp>
struct __sp_is_constructible<_Up[], _Yp>
: __sp_is_constructible_arr<_Up, _Yp>::type
{ };

// otherwise, Y* shall be convertible to T*.
template<typename _Tp, typename _Yp>
struct __sp_is_constructible
: is_convertible<_Yp*, _Tp*>::type
{ };


// Define operator* and operator-> for shared_ptr<T>.
template<typename _Tp, _Lock_policy _Lp,
bool = is_array<_Tp>::value, bool = is_void<_Tp>::value>
class __shared_ptr_access
{
public:
using element_type = _Tp;

element_type&
operator*() const noexcept
{
__glibcxx_assert(_M_get() != nullptr);
return *_M_get();
}

element_type*
operator->() const noexcept
{
_GLIBCXX_DEBUG_PEDASSERT(_M_get() != nullptr);
return _M_get();
}

private:
element_type*
_M_get() const noexcept
{ return static_cast<const __shared_ptr<_Tp, _Lp>*>(this)->get(); }
};

// Define operator-> for shared_ptr<cv void>.
template<typename _Tp, _Lock_policy _Lp>
class __shared_ptr_access<_Tp, _Lp, false, true>
{
public:
using element_type = _Tp;

element_type*
operator->() const noexcept
{
auto __ptr = static_cast<const __shared_ptr<_Tp, _Lp>*>(this)->get();
_GLIBCXX_DEBUG_PEDASSERT(__ptr != nullptr);
return __ptr;
}
};

// Define operator[] for shared_ptr<T[]> and shared_ptr<T[N]>.
template<typename _Tp, _Lock_policy _Lp>
class __shared_ptr_access<_Tp, _Lp, true, false>
{
public:
using element_type = typename remove_extent<_Tp>::type;

#if __cplusplus <= 201402L
[[__deprecated__("shared_ptr<T[]>::operator* is absent from C++17")]]
element_type&
operator*() const noexcept
{
__glibcxx_assert(_M_get() != nullptr);
return *_M_get();
}

[[__deprecated__("shared_ptr<T[]>::operator-> is absent from C++17")]]
element_type*
operator->() const noexcept
{
_GLIBCXX_DEBUG_PEDASSERT(_M_get() != nullptr);
return _M_get();
}
#endif

element_type&
operator[](ptrdiff_t __i) const
{
__glibcxx_assert(_M_get() != nullptr);
__glibcxx_assert(!extent<_Tp>::value || __i < extent<_Tp>::value);
return _M_get()[__i];
}

private:
element_type*
_M_get() const noexcept
{ return static_cast<const __shared_ptr<_Tp, _Lp>*>(this)->get(); }
};

template<typename _Tp, _Lock_policy _Lp>
class __shared_ptr
: public __shared_ptr_access<_Tp, _Lp>
{
public:
using element_type = typename remove_extent<_Tp>::type;

private:
// Constraint for taking ownership of a pointer of type _Yp*:
template<typename _Yp>
using _SafeConv
= typename enable_if<__sp_is_constructible<_Tp, _Yp>::value>::type;

// Constraint for construction from shared_ptr and weak_ptr:
template<typename _Yp, typename _Res = void>
using _Compatible = typename
enable_if<__sp_compatible_with<_Yp*, _Tp*>::value, _Res>::type;

// Constraint for assignment from shared_ptr and weak_ptr:
template<typename _Yp>
using _Assignable = _Compatible<_Yp, __shared_ptr&>;

// Constraint for construction from unique_ptr:
template<typename _Yp, typename _Del, typename _Res = void,
typename _Ptr = typename unique_ptr<_Yp, _Del>::pointer>
using _UniqCompatible = __enable_if_t<__and_<
__sp_compatible_with<_Yp*, _Tp*>,
is_convertible<_Ptr, element_type*>,
is_move_constructible<_Del>
>::value, _Res>;

// Constraint for assignment from unique_ptr:
template<typename _Yp, typename _Del>
using _UniqAssignable = _UniqCompatible<_Yp, _Del, __shared_ptr&>;

public:

#if __cplusplus > 201402L
using weak_type = __weak_ptr<_Tp, _Lp>;
#endif

constexpr __shared_ptr() noexcept
: _M_ptr(0), _M_refcount()
{ }

template<typename _Yp, typename = _SafeConv<_Yp>>
explicit
__shared_ptr(_Yp* __p)
: _M_ptr(__p), _M_refcount(__p, typename is_array<_Tp>::type())
{
static_assert( !is_void<_Yp>::value, "incomplete type" );
static_assert( sizeof(_Yp) > 0, "incomplete type" );
_M_enable_shared_from_this_with(__p);
}

template<typename _Yp, typename _Deleter, typename = _SafeConv<_Yp>>
__shared_ptr(_Yp* __p, _Deleter __d)
: _M_ptr(__p), _M_refcount(__p, std::move(__d))
{
static_assert(__is_invocable<_Deleter&, _Yp*&>::value,
"deleter expression d(p) is well-formed");
_M_enable_shared_from_this_with(__p);
}

template<typename _Yp, typename _Deleter, typename _Alloc,
typename = _SafeConv<_Yp>>
__shared_ptr(_Yp* __p, _Deleter __d, _Alloc __a)
: _M_ptr(__p), _M_refcount(__p, std::move(__d), std::move(__a))
{
static_assert(__is_invocable<_Deleter&, _Yp*&>::value,
"deleter expression d(p) is well-formed");
_M_enable_shared_from_this_with(__p);
}

template<typename _Deleter>
__shared_ptr(nullptr_t __p, _Deleter __d)
: _M_ptr(0), _M_refcount(__p, std::move(__d))
{ }

template<typename _Deleter, typename _Alloc>
__shared_ptr(nullptr_t __p, _Deleter __d, _Alloc __a)
: _M_ptr(0), _M_refcount(__p, std::move(__d), std::move(__a))
{ }

// Aliasing constructor
template<typename _Yp>
__shared_ptr(const __shared_ptr<_Yp, _Lp>& __r,
element_type* __p) noexcept
: _M_ptr(__p), _M_refcount(__r._M_refcount) // never throws
{ }

// Aliasing constructor
template<typename _Yp>
__shared_ptr(__shared_ptr<_Yp, _Lp>&& __r,
element_type* __p) noexcept
: _M_ptr(__p), _M_refcount()
{
_M_refcount._M_swap(__r._M_refcount);
__r._M_ptr = nullptr;
}

__shared_ptr(const __shared_ptr&) noexcept = default;
__shared_ptr& operator=(const __shared_ptr&) noexcept = default;
~__shared_ptr() = default;

template<typename _Yp, typename = _Compatible<_Yp>>
__shared_ptr(const __shared_ptr<_Yp, _Lp>& __r) noexcept
: _M_ptr(__r._M_ptr), _M_refcount(__r._M_refcount)
{ }

__shared_ptr(__shared_ptr&& __r) noexcept
: _M_ptr(__r._M_ptr), _M_refcount()
{
_M_refcount._M_swap(__r._M_refcount);
__r._M_ptr = nullptr;
}

template<typename _Yp, typename = _Compatible<_Yp>>
__shared_ptr(__shared_ptr<_Yp, _Lp>&& __r) noexcept
: _M_ptr(__r._M_ptr), _M_refcount()
{
_M_refcount._M_swap(__r._M_refcount);
__r._M_ptr = nullptr;
}

template<typename _Yp, typename = _Compatible<_Yp>>
explicit __shared_ptr(const __weak_ptr<_Yp, _Lp>& __r)
: _M_refcount(__r._M_refcount) // may throw
{
// It is now safe to copy __r._M_ptr, as
// _M_refcount(__r._M_refcount) did not throw.
_M_ptr = __r._M_ptr;
}

// If an exception is thrown this constructor has no effect.
template<typename _Yp, typename _Del,
typename = _UniqCompatible<_Yp, _Del>>
__shared_ptr(unique_ptr<_Yp, _Del>&& __r)
: _M_ptr(__r.get()), _M_refcount()
{
auto __raw = __to_address(__r.get());
_M_refcount = __shared_count<_Lp>(std::move(__r));
_M_enable_shared_from_this_with(__raw);
}

#if __cplusplus <= 201402L && _GLIBCXX_USE_DEPRECATED
protected:
// If an exception is thrown this constructor has no effect.
template<typename _Tp1, typename _Del,
typename enable_if<__and_<
__not_<is_array<_Tp>>, is_array<_Tp1>,
is_convertible<typename unique_ptr<_Tp1, _Del>::pointer, _Tp*>
>::value, bool>::type = true>
__shared_ptr(unique_ptr<_Tp1, _Del>&& __r, __sp_array_delete)
: _M_ptr(__r.get()), _M_refcount()
{
auto __raw = __to_address(__r.get());
_M_refcount = __shared_count<_Lp>(std::move(__r));
_M_enable_shared_from_this_with(__raw);
}
public:
#endif

#if _GLIBCXX_USE_DEPRECATED
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
// Postcondition: use_count() == 1 and __r.get() == 0
template<typename _Yp, typename = _Compatible<_Yp>>
__shared_ptr(auto_ptr<_Yp>&& __r);
#pragma GCC diagnostic pop
#endif

constexpr __shared_ptr(nullptr_t) noexcept : __shared_ptr() { }

template<typename _Yp>
_Assignable<_Yp>
operator=(const __shared_ptr<_Yp, _Lp>& __r) noexcept
{
_M_ptr = __r._M_ptr;
_M_refcount = __r._M_refcount; // __shared_count::op= doesn't throw
return *this;
}

#if _GLIBCXX_USE_DEPRECATED
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
template<typename _Yp>
_Assignable<_Yp>
operator=(auto_ptr<_Yp>&& __r)
{
__shared_ptr(std::move(__r)).swap(*this);
return *this;
}
#pragma GCC diagnostic pop
#endif

__shared_ptr&
operator=(__shared_ptr&& __r) noexcept
{
__shared_ptr(std::move(__r)).swap(*this);
return *this;
}

template<class _Yp>
_Assignable<_Yp>
operator=(__shared_ptr<_Yp, _Lp>&& __r) noexcept
{
__shared_ptr(std::move(__r)).swap(*this);
return *this;
}

template<typename _Yp, typename _Del>
_UniqAssignable<_Yp, _Del>
operator=(unique_ptr<_Yp, _Del>&& __r)
{
__shared_ptr(std::move(__r)).swap(*this);
return *this;
}

void
reset() noexcept
{ __shared_ptr().swap(*this); }

template<typename _Yp>
_SafeConv<_Yp>
reset(_Yp* __p) // _Yp must be complete.
{
// Catch self-reset errors.
__glibcxx_assert(__p == nullptr || __p != _M_ptr);
__shared_ptr(__p).swap(*this);
}

template<typename _Yp, typename _Deleter>
_SafeConv<_Yp>
reset(_Yp* __p, _Deleter __d)
{ __shared_ptr(__p, std::move(__d)).swap(*this); }

template<typename _Yp, typename _Deleter, typename _Alloc>
_SafeConv<_Yp>
reset(_Yp* __p, _Deleter __d, _Alloc __a)
{ __shared_ptr(__p, std::move(__d), std::move(__a)).swap(*this); }

/// Return the stored pointer.
element_type*
get() const noexcept
{ return _M_ptr; }

/// Return true if the stored pointer is not null.
explicit operator bool() const noexcept
{ return _M_ptr != nullptr; }

/// Return true if use_count() == 1.
bool
unique() const noexcept
{ return _M_refcount._M_unique(); }

/// If *this owns a pointer, return the number of owners, otherwise zero.
long
use_count() const noexcept
{ return _M_refcount._M_get_use_count(); }

/// Exchange both the owned pointer and the stored pointer.
void
swap(__shared_ptr<_Tp, _Lp>& __other) noexcept
{
std::swap(_M_ptr, __other._M_ptr);
_M_refcount._M_swap(__other._M_refcount);
}

/** @brief Define an ordering based on ownership.
*
* This function defines a strict weak ordering between two shared_ptr
* or weak_ptr objects, such that one object is less than the other
* unless they share ownership of the same pointer, or are both empty.
* @{
*/
template<typename _Tp1>
bool
owner_before(__shared_ptr<_Tp1, _Lp> const& __rhs) const noexcept
{ return _M_refcount._M_less(__rhs._M_refcount); }

template<typename _Tp1>
bool
owner_before(__weak_ptr<_Tp1, _Lp> const& __rhs) const noexcept
{ return _M_refcount._M_less(__rhs._M_refcount); }
/// @}

protected:
// This constructor is non-standard, it is used by allocate_shared.
template<typename _Alloc, typename... _Args>
__shared_ptr(_Sp_alloc_shared_tag<_Alloc> __tag, _Args&&... __args)
: _M_ptr(), _M_refcount(_M_ptr, __tag, std::forward<_Args>(__args)...)
{ _M_enable_shared_from_this_with(_M_ptr); }

template<typename _Tp1, _Lock_policy _Lp1, typename _Alloc,
typename... _Args>
friend __shared_ptr<_Tp1, _Lp1>
__allocate_shared(const _Alloc& __a, _Args&&... __args);

// This constructor is used by __weak_ptr::lock() and
// shared_ptr::shared_ptr(const weak_ptr&, std::nothrow_t).
__shared_ptr(const __weak_ptr<_Tp, _Lp>& __r, std::nothrow_t) noexcept
: _M_refcount(__r._M_refcount, std::nothrow)
{
_M_ptr = _M_refcount._M_get_use_count() ? __r._M_ptr : nullptr;
}

friend class __weak_ptr<_Tp, _Lp>;

private:

template<typename _Yp>
using __esft_base_t = decltype(__enable_shared_from_this_base(
std::declval<const __shared_count<_Lp>&>(),
std::declval<_Yp*>()));

// Detect an accessible and unambiguous enable_shared_from_this base.
template<typename _Yp, typename = void>
struct __has_esft_base
: false_type { };

template<typename _Yp>
struct __has_esft_base<_Yp, __void_t<__esft_base_t<_Yp>>>
: __not_<is_array<_Tp>> { }; // No enable shared_from_this for arrays

template<typename _Yp, typename _Yp2 = typename remove_cv<_Yp>::type>
typename enable_if<__has_esft_base<_Yp2>::value>::type
_M_enable_shared_from_this_with(_Yp* __p) noexcept
{
if (auto __base = __enable_shared_from_this_base(_M_refcount, __p))
__base->_M_weak_assign(const_cast<_Yp2*>(__p), _M_refcount);
}

template<typename _Yp, typename _Yp2 = typename remove_cv<_Yp>::type>
typename enable_if<!__has_esft_base<_Yp2>::value>::type
_M_enable_shared_from_this_with(_Yp*) noexcept
{ }

void*
_M_get_deleter(const std::type_info& __ti) const noexcept
{ return _M_refcount._M_get_deleter(__ti); }

template<typename _Tp1, _Lock_policy _Lp1> friend class __shared_ptr;
template<typename _Tp1, _Lock_policy _Lp1> friend class __weak_ptr;

template<typename _Del, typename _Tp1, _Lock_policy _Lp1>
friend _Del* get_deleter(const __shared_ptr<_Tp1, _Lp1>&) noexcept;

template<typename _Del, typename _Tp1>
friend _Del* get_deleter(const shared_ptr<_Tp1>&) noexcept;

element_type* _M_ptr; // Contained pointer.
__shared_count<_Lp> _M_refcount; // Reference counter.
};


// 20.7.2.2.7 shared_ptr comparisons
template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
inline bool
operator==(const __shared_ptr<_Tp1, _Lp>& __a,
const __shared_ptr<_Tp2, _Lp>& __b) noexcept
{ return __a.get() == __b.get(); }

template<typename _Tp, _Lock_policy _Lp>
inline bool
operator==(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
{ return !__a; }

#ifdef __cpp_lib_three_way_comparison
template<typename _Tp, typename _Up, _Lock_policy _Lp>
inline strong_ordering
operator<=>(const __shared_ptr<_Tp, _Lp>& __a,
const __shared_ptr<_Up, _Lp>& __b) noexcept
{ return compare_three_way()(__a.get(), __b.get()); }

template<typename _Tp, _Lock_policy _Lp>
inline strong_ordering
operator<=>(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
{
using pointer = typename __shared_ptr<_Tp, _Lp>::element_type*;
return compare_three_way()(__a.get(), static_cast<pointer>(nullptr));
}
#else
template<typename _Tp, _Lock_policy _Lp>
inline bool
operator==(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
{ return !__a; }

template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
inline bool
operator!=(const __shared_ptr<_Tp1, _Lp>& __a,
const __shared_ptr<_Tp2, _Lp>& __b) noexcept
{ return __a.get() != __b.get(); }

template<typename _Tp, _Lock_policy _Lp>
inline bool
operator!=(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
{ return (bool)__a; }

template<typename _Tp, _Lock_policy _Lp>
inline bool
operator!=(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
{ return (bool)__a; }

template<typename _Tp, typename _Up, _Lock_policy _Lp>
inline bool
operator<(const __shared_ptr<_Tp, _Lp>& __a,
const __shared_ptr<_Up, _Lp>& __b) noexcept
{
using _Tp_elt = typename __shared_ptr<_Tp, _Lp>::element_type;
using _Up_elt = typename __shared_ptr<_Up, _Lp>::element_type;
using _Vp = typename common_type<_Tp_elt*, _Up_elt*>::type;
return less<_Vp>()(__a.get(), __b.get());
}

template<typename _Tp, _Lock_policy _Lp>
inline bool
operator<(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
{
using _Tp_elt = typename __shared_ptr<_Tp, _Lp>::element_type;
return less<_Tp_elt*>()(__a.get(), nullptr);
}

template<typename _Tp, _Lock_policy _Lp>
inline bool
operator<(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
{
using _Tp_elt = typename __shared_ptr<_Tp, _Lp>::element_type;
return less<_Tp_elt*>()(nullptr, __a.get());
}

template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
inline bool
operator<=(const __shared_ptr<_Tp1, _Lp>& __a,
const __shared_ptr<_Tp2, _Lp>& __b) noexcept
{ return !(__b < __a); }

template<typename _Tp, _Lock_policy _Lp>
inline bool
operator<=(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
{ return !(nullptr < __a); }

template<typename _Tp, _Lock_policy _Lp>
inline bool
operator<=(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
{ return !(__a < nullptr); }

template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
inline bool
operator>(const __shared_ptr<_Tp1, _Lp>& __a,
const __shared_ptr<_Tp2, _Lp>& __b) noexcept
{ return (__b < __a); }

template<typename _Tp, _Lock_policy _Lp>
inline bool
operator>(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
{ return nullptr < __a; }

template<typename _Tp, _Lock_policy _Lp>
inline bool
operator>(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
{ return __a < nullptr; }

template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
inline bool
operator>=(const __shared_ptr<_Tp1, _Lp>& __a,
const __shared_ptr<_Tp2, _Lp>& __b) noexcept
{ return !(__a < __b); }

template<typename _Tp, _Lock_policy _Lp>
inline bool
operator>=(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
{ return !(__a < nullptr); }

template<typename _Tp, _Lock_policy _Lp>
inline bool
operator>=(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
{ return !(nullptr < __a); }
#endif // three-way comparison

// 20.7.2.2.8 shared_ptr specialized algorithms.
template<typename _Tp, _Lock_policy _Lp>
inline void
swap(__shared_ptr<_Tp, _Lp>& __a, __shared_ptr<_Tp, _Lp>& __b) noexcept
{ __a.swap(__b); }

// 20.7.2.2.9 shared_ptr casts

// The seemingly equivalent code:
// shared_ptr<_Tp, _Lp>(static_cast<_Tp*>(__r.get()))
// will eventually result in undefined behaviour, attempting to
// delete the same object twice.
/// static_pointer_cast
template<typename _Tp, typename _Tp1, _Lock_policy _Lp>
inline __shared_ptr<_Tp, _Lp>
static_pointer_cast(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
{
using _Sp = __shared_ptr<_Tp, _Lp>;
return _Sp(__r, static_cast<typename _Sp::element_type*>(__r.get()));
}

// The seemingly equivalent code:
// shared_ptr<_Tp, _Lp>(const_cast<_Tp*>(__r.get()))
// will eventually result in undefined behaviour, attempting to
// delete the same object twice.
/// const_pointer_cast
template<typename _Tp, typename _Tp1, _Lock_policy _Lp>
inline __shared_ptr<_Tp, _Lp>
const_pointer_cast(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
{
using _Sp = __shared_ptr<_Tp, _Lp>;
return _Sp(__r, const_cast<typename _Sp::element_type*>(__r.get()));
}

// The seemingly equivalent code:
// shared_ptr<_Tp, _Lp>(dynamic_cast<_Tp*>(__r.get()))
// will eventually result in undefined behaviour, attempting to
// delete the same object twice.
/// dynamic_pointer_cast
template<typename _Tp, typename _Tp1, _Lock_policy _Lp>
inline __shared_ptr<_Tp, _Lp>
dynamic_pointer_cast(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
{
using _Sp = __shared_ptr<_Tp, _Lp>;
if (auto* __p = dynamic_cast<typename _Sp::element_type*>(__r.get()))
return _Sp(__r, __p);
return _Sp();
}

#if __cplusplus > 201402L
template<typename _Tp, typename _Tp1, _Lock_policy _Lp>
inline __shared_ptr<_Tp, _Lp>
reinterpret_pointer_cast(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
{
using _Sp = __shared_ptr<_Tp, _Lp>;
return _Sp(__r, reinterpret_cast<typename _Sp::element_type*>(__r.get()));
}
#endif

template<typename _Tp, _Lock_policy _Lp>
class __weak_ptr
{
template<typename _Yp, typename _Res = void>
using _Compatible = typename
enable_if<__sp_compatible_with<_Yp*, _Tp*>::value, _Res>::type;

// Constraint for assignment from shared_ptr and weak_ptr:
template<typename _Yp>
using _Assignable = _Compatible<_Yp, __weak_ptr&>;

public:
using element_type = typename remove_extent<_Tp>::type;

constexpr __weak_ptr() noexcept
: _M_ptr(nullptr), _M_refcount()
{ }

__weak_ptr(const __weak_ptr&) noexcept = default;

~__weak_ptr() = default;

// The "obvious" converting constructor implementation:
//
// template<typename _Tp1>
// __weak_ptr(const __weak_ptr<_Tp1, _Lp>& __r)
// : _M_ptr(__r._M_ptr), _M_refcount(__r._M_refcount) // never throws
// { }
//
// has a serious problem.
//
// __r._M_ptr may already have been invalidated. The _M_ptr(__r._M_ptr)
// conversion may require access to *__r._M_ptr (virtual inheritance).
//
// It is not possible to avoid spurious access violations since
// in multithreaded programs __r._M_ptr may be invalidated at any point.
template<typename _Yp, typename = _Compatible<_Yp>>
__weak_ptr(const __weak_ptr<_Yp, _Lp>& __r) noexcept
: _M_refcount(__r._M_refcount)
{ _M_ptr = __r.lock().get(); }

template<typename _Yp, typename = _Compatible<_Yp>>
__weak_ptr(const __shared_ptr<_Yp, _Lp>& __r) noexcept
: _M_ptr(__r._M_ptr), _M_refcount(__r._M_refcount)
{ }

__weak_ptr(__weak_ptr&& __r) noexcept
: _M_ptr(__r._M_ptr), _M_refcount(std::move(__r._M_refcount))
{ __r._M_ptr = nullptr; }

template<typename _Yp, typename = _Compatible<_Yp>>
__weak_ptr(__weak_ptr<_Yp, _Lp>&& __r) noexcept
: _M_ptr(__r.lock().get()), _M_refcount(std::move(__r._M_refcount))
{ __r._M_ptr = nullptr; }

__weak_ptr&
operator=(const __weak_ptr& __r) noexcept = default;

template<typename _Yp>
_Assignable<_Yp>
operator=(const __weak_ptr<_Yp, _Lp>& __r) noexcept
{
_M_ptr = __r.lock().get();
_M_refcount = __r._M_refcount;
return *this;
}

template<typename _Yp>
_Assignable<_Yp>
operator=(const __shared_ptr<_Yp, _Lp>& __r) noexcept
{
_M_ptr = __r._M_ptr;
_M_refcount = __r._M_refcount;
return *this;
}

__weak_ptr&
operator=(__weak_ptr&& __r) noexcept
{
__weak_ptr(std::move(__r)).swap(*this);
return *this;
}

template<typename _Yp>
_Assignable<_Yp>
operator=(__weak_ptr<_Yp, _Lp>&& __r) noexcept
{
_M_ptr = __r.lock().get();
_M_refcount = std::move(__r._M_refcount);
__r._M_ptr = nullptr;
return *this;
}

__shared_ptr<_Tp, _Lp>
lock() const noexcept
{ return __shared_ptr<element_type, _Lp>(*this, std::nothrow); }

long
use_count() const noexcept
{ return _M_refcount._M_get_use_count(); }

bool
expired() const noexcept
{ return _M_refcount._M_get_use_count() == 0; }

template<typename _Tp1>
bool
owner_before(const __shared_ptr<_Tp1, _Lp>& __rhs) const noexcept
{ return _M_refcount._M_less(__rhs._M_refcount); }

template<typename _Tp1>
bool
owner_before(const __weak_ptr<_Tp1, _Lp>& __rhs) const noexcept
{ return _M_refcount._M_less(__rhs._M_refcount); }

void
reset() noexcept
{ __weak_ptr().swap(*this); }

void
swap(__weak_ptr& __s) noexcept
{
std::swap(_M_ptr, __s._M_ptr);
_M_refcount._M_swap(__s._M_refcount);
}

private:
// Used by __enable_shared_from_this.
void
_M_assign(_Tp* __ptr, const __shared_count<_Lp>& __refcount) noexcept
{
if (use_count() == 0)
{
_M_ptr = __ptr;
_M_refcount = __refcount;
}
}

template<typename _Tp1, _Lock_policy _Lp1> friend class __shared_ptr;
template<typename _Tp1, _Lock_policy _Lp1> friend class __weak_ptr;
friend class __enable_shared_from_this<_Tp, _Lp>;
friend class enable_shared_from_this<_Tp>;

element_type* _M_ptr; // Contained pointer.
__weak_count<_Lp> _M_refcount; // Reference counter.
};

// 20.7.2.3.6 weak_ptr specialized algorithms.
template<typename _Tp, _Lock_policy _Lp>
inline void
swap(__weak_ptr<_Tp, _Lp>& __a, __weak_ptr<_Tp, _Lp>& __b) noexcept
{ __a.swap(__b); }

template<typename _Tp, typename _Tp1>
struct _Sp_owner_less : public binary_function<_Tp, _Tp, bool>
{
bool
operator()(const _Tp& __lhs, const _Tp& __rhs) const noexcept
{ return __lhs.owner_before(__rhs); }

bool
operator()(const _Tp& __lhs, const _Tp1& __rhs) const noexcept
{ return __lhs.owner_before(__rhs); }

bool
operator()(const _Tp1& __lhs, const _Tp& __rhs) const noexcept
{ return __lhs.owner_before(__rhs); }
};

template<>
struct _Sp_owner_less<void, void>
{
template<typename _Tp, typename _Up>
auto
operator()(const _Tp& __lhs, const _Up& __rhs) const noexcept
-> decltype(__lhs.owner_before(__rhs))
{ return __lhs.owner_before(__rhs); }

using is_transparent = void;
};

template<typename _Tp, _Lock_policy _Lp>
struct owner_less<__shared_ptr<_Tp, _Lp>>
: public _Sp_owner_less<__shared_ptr<_Tp, _Lp>, __weak_ptr<_Tp, _Lp>>
{ };

template<typename _Tp, _Lock_policy _Lp>
struct owner_less<__weak_ptr<_Tp, _Lp>>
: public _Sp_owner_less<__weak_ptr<_Tp, _Lp>, __shared_ptr<_Tp, _Lp>>
{ };


template<typename _Tp, _Lock_policy _Lp>
class __enable_shared_from_this
{
protected:
constexpr __enable_shared_from_this() noexcept { }

__enable_shared_from_this(const __enable_shared_from_this&) noexcept { }

__enable_shared_from_this&
operator=(const __enable_shared_from_this&) noexcept
{ return *this; }

~__enable_shared_from_this() { }

public:
__shared_ptr<_Tp, _Lp>
shared_from_this()
{ return __shared_ptr<_Tp, _Lp>(this->_M_weak_this); }

__shared_ptr<const _Tp, _Lp>
shared_from_this() const
{ return __shared_ptr<const _Tp, _Lp>(this->_M_weak_this); }

#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
__weak_ptr<_Tp, _Lp>
weak_from_this() noexcept
{ return this->_M_weak_this; }

__weak_ptr<const _Tp, _Lp>
weak_from_this() const noexcept
{ return this->_M_weak_this; }
#endif

private:
template<typename _Tp1>
void
_M_weak_assign(_Tp1* __p, const __shared_count<_Lp>& __n) const noexcept
{ _M_weak_this._M_assign(__p, __n); }

friend const __enable_shared_from_this*
__enable_shared_from_this_base(const __shared_count<_Lp>&,
const __enable_shared_from_this* __p)
{ return __p; }

template<typename, _Lock_policy>
friend class __shared_ptr;

mutable __weak_ptr<_Tp, _Lp> _M_weak_this;
};

template<typename _Tp, _Lock_policy _Lp = __default_lock_policy,
typename _Alloc, typename... _Args>
inline __shared_ptr<_Tp, _Lp>
__allocate_shared(const _Alloc& __a, _Args&&... __args)
{
static_assert(!is_array<_Tp>::value, "make_shared<T[]> not supported");

return __shared_ptr<_Tp, _Lp>(_Sp_alloc_shared_tag<_Alloc>{__a},
std::forward<_Args>(__args)...);
}

template<typename _Tp, _Lock_policy _Lp = __default_lock_policy,
typename... _Args>
inline __shared_ptr<_Tp, _Lp>
__make_shared(_Args&&... __args)
{
typedef typename std::remove_const<_Tp>::type _Tp_nc;
return std::__allocate_shared<_Tp, _Lp>(std::allocator<_Tp_nc>(),
std::forward<_Args>(__args)...);
}

/// std::hash specialization for __shared_ptr.
template<typename _Tp, _Lock_policy _Lp>
struct hash<__shared_ptr<_Tp, _Lp>>
: public __hash_base<size_t, __shared_ptr<_Tp, _Lp>>
{
size_t
operator()(const __shared_ptr<_Tp, _Lp>& __s) const noexcept
{
return hash<typename __shared_ptr<_Tp, _Lp>::element_type*>()(
__s.get());
}
};

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace

#endif // _SHARED_PTR_BASE_H
shared_ptr_atomic.h
shared_ptr_atomic.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
// shared_ptr atomic access -*- C++ -*-

// Copyright (C) 2014-2021 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.

/** @file bits/shared_ptr_atomic.h
* This is an internal header file, included by other library headers.
* Do not attempt to use it directly. @headername{memory}
*/

#ifndef _SHARED_PTR_ATOMIC_H
#define _SHARED_PTR_ATOMIC_H 1

#include <bits/atomic_base.h>

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

/**
* @addtogroup pointer_abstractions
* @{
*/
/// @relates shared_ptr @{

/// @cond undocumented

struct _Sp_locker
{
_Sp_locker(const _Sp_locker&) = delete;
_Sp_locker& operator=(const _Sp_locker&) = delete;

#ifdef __GTHREADS
explicit
_Sp_locker(const void*) noexcept;
_Sp_locker(const void*, const void*) noexcept;
~_Sp_locker();

private:
unsigned char _M_key1;
unsigned char _M_key2;
#else
explicit _Sp_locker(const void*, const void* = nullptr) { }
#endif
};

/// @endcond

/**
* @brief Report whether shared_ptr atomic operations are lock-free.
* @param __p A non-null pointer to a shared_ptr object.
* @return True if atomic access to @c *__p is lock-free, false otherwise.
* @{
*/
template<typename _Tp, _Lock_policy _Lp>
inline bool
atomic_is_lock_free(const __shared_ptr<_Tp, _Lp>* __p)
{
#ifdef __GTHREADS
return __gthread_active_p() == 0;
#else
return true;
#endif
}

template<typename _Tp>
inline bool
atomic_is_lock_free(const shared_ptr<_Tp>* __p)
{ return std::atomic_is_lock_free<_Tp, __default_lock_policy>(__p); }

/// @}

/**
* @brief Atomic load for shared_ptr objects.
* @param __p A non-null pointer to a shared_ptr object.
* @return @c *__p
*
* The memory order shall not be @c memory_order_release or
* @c memory_order_acq_rel.
* @{
*/
template<typename _Tp>
inline shared_ptr<_Tp>
atomic_load_explicit(const shared_ptr<_Tp>* __p, memory_order)
{
_Sp_locker __lock{__p};
return *__p;
}

template<typename _Tp>
inline shared_ptr<_Tp>
atomic_load(const shared_ptr<_Tp>* __p)
{ return std::atomic_load_explicit(__p, memory_order_seq_cst); }

template<typename _Tp, _Lock_policy _Lp>
inline __shared_ptr<_Tp, _Lp>
atomic_load_explicit(const __shared_ptr<_Tp, _Lp>* __p, memory_order)
{
_Sp_locker __lock{__p};
return *__p;
}

template<typename _Tp, _Lock_policy _Lp>
inline __shared_ptr<_Tp, _Lp>
atomic_load(const __shared_ptr<_Tp, _Lp>* __p)
{ return std::atomic_load_explicit(__p, memory_order_seq_cst); }
/// @}

/**
* @brief Atomic store for shared_ptr objects.
* @param __p A non-null pointer to a shared_ptr object.
* @param __r The value to store.
*
* The memory order shall not be @c memory_order_acquire or
* @c memory_order_acq_rel.
* @{
*/
template<typename _Tp>
inline void
atomic_store_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r,
memory_order)
{
_Sp_locker __lock{__p};
__p->swap(__r); // use swap so that **__p not destroyed while lock held
}

template<typename _Tp>
inline void
atomic_store(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r)
{ std::atomic_store_explicit(__p, std::move(__r), memory_order_seq_cst); }

template<typename _Tp, _Lock_policy _Lp>
inline void
atomic_store_explicit(__shared_ptr<_Tp, _Lp>* __p,
__shared_ptr<_Tp, _Lp> __r,
memory_order)
{
_Sp_locker __lock{__p};
__p->swap(__r); // use swap so that **__p not destroyed while lock held
}

template<typename _Tp, _Lock_policy _Lp>
inline void
atomic_store(__shared_ptr<_Tp, _Lp>* __p, __shared_ptr<_Tp, _Lp> __r)
{ std::atomic_store_explicit(__p, std::move(__r), memory_order_seq_cst); }
/// @}

/**
* @brief Atomic exchange for shared_ptr objects.
* @param __p A non-null pointer to a shared_ptr object.
* @param __r New value to store in @c *__p.
* @return The original value of @c *__p
* @{
*/
template<typename _Tp>
inline shared_ptr<_Tp>
atomic_exchange_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r,
memory_order)
{
_Sp_locker __lock{__p};
__p->swap(__r);
return __r;
}

template<typename _Tp>
inline shared_ptr<_Tp>
atomic_exchange(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r)
{
return std::atomic_exchange_explicit(__p, std::move(__r),
memory_order_seq_cst);
}

template<typename _Tp, _Lock_policy _Lp>
inline __shared_ptr<_Tp, _Lp>
atomic_exchange_explicit(__shared_ptr<_Tp, _Lp>* __p,
__shared_ptr<_Tp, _Lp> __r,
memory_order)
{
_Sp_locker __lock{__p};
__p->swap(__r);
return __r;
}

template<typename _Tp, _Lock_policy _Lp>
inline __shared_ptr<_Tp, _Lp>
atomic_exchange(__shared_ptr<_Tp, _Lp>* __p, __shared_ptr<_Tp, _Lp> __r)
{
return std::atomic_exchange_explicit(__p, std::move(__r),
memory_order_seq_cst);
}
/// @}

/**
* @brief Atomic compare-and-swap for shared_ptr objects.
* @param __p A non-null pointer to a shared_ptr object.
* @param __v A non-null pointer to a shared_ptr object.
* @param __w A non-null pointer to a shared_ptr object.
* @return True if @c *__p was equivalent to @c *__v, false otherwise.
*
* The memory order for failure shall not be @c memory_order_release or
* @c memory_order_acq_rel, or stronger than the memory order for success.
* @{
*/
template<typename _Tp>
bool
atomic_compare_exchange_strong_explicit(shared_ptr<_Tp>* __p,
shared_ptr<_Tp>* __v,
shared_ptr<_Tp> __w,
memory_order,
memory_order)
{
shared_ptr<_Tp> __x; // goes out of scope after __lock
_Sp_locker __lock{__p, __v};
owner_less<shared_ptr<_Tp>> __less;
if (*__p == *__v && !__less(*__p, *__v) && !__less(*__v, *__p))
{
__x = std::move(*__p);
*__p = std::move(__w);
return true;
}
__x = std::move(*__v);
*__v = *__p;
return false;
}

template<typename _Tp>
inline bool
atomic_compare_exchange_strong(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v,
shared_ptr<_Tp> __w)
{
return std::atomic_compare_exchange_strong_explicit(__p, __v,
std::move(__w), memory_order_seq_cst, memory_order_seq_cst);
}

template<typename _Tp>
inline bool
atomic_compare_exchange_weak_explicit(shared_ptr<_Tp>* __p,
shared_ptr<_Tp>* __v,
shared_ptr<_Tp> __w,
memory_order __success,
memory_order __failure)
{
return std::atomic_compare_exchange_strong_explicit(__p, __v,
std::move(__w), __success, __failure);
}

template<typename _Tp>
inline bool
atomic_compare_exchange_weak(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v,
shared_ptr<_Tp> __w)
{
return std::atomic_compare_exchange_weak_explicit(__p, __v,
std::move(__w), memory_order_seq_cst, memory_order_seq_cst);
}

template<typename _Tp, _Lock_policy _Lp>
bool
atomic_compare_exchange_strong_explicit(__shared_ptr<_Tp, _Lp>* __p,
__shared_ptr<_Tp, _Lp>* __v,
__shared_ptr<_Tp, _Lp> __w,
memory_order,
memory_order)
{
__shared_ptr<_Tp, _Lp> __x; // goes out of scope after __lock
_Sp_locker __lock{__p, __v};
owner_less<__shared_ptr<_Tp, _Lp>> __less;
if (*__p == *__v && !__less(*__p, *__v) && !__less(*__v, *__p))
{
__x = std::move(*__p);
*__p = std::move(__w);
return true;
}
__x = std::move(*__v);
*__v = *__p;
return false;
}

template<typename _Tp, _Lock_policy _Lp>
inline bool
atomic_compare_exchange_strong(__shared_ptr<_Tp, _Lp>* __p,
__shared_ptr<_Tp, _Lp>* __v,
__shared_ptr<_Tp, _Lp> __w)
{
return std::atomic_compare_exchange_strong_explicit(__p, __v,
std::move(__w), memory_order_seq_cst, memory_order_seq_cst);
}

template<typename _Tp, _Lock_policy _Lp>
inline bool
atomic_compare_exchange_weak_explicit(__shared_ptr<_Tp, _Lp>* __p,
__shared_ptr<_Tp, _Lp>* __v,
__shared_ptr<_Tp, _Lp> __w,
memory_order __success,
memory_order __failure)
{
return std::atomic_compare_exchange_strong_explicit(__p, __v,
std::move(__w), __success, __failure);
}

template<typename _Tp, _Lock_policy _Lp>
inline bool
atomic_compare_exchange_weak(__shared_ptr<_Tp, _Lp>* __p,
__shared_ptr<_Tp, _Lp>* __v,
__shared_ptr<_Tp, _Lp> __w)
{
return std::atomic_compare_exchange_weak_explicit(__p, __v,
std::move(__w), memory_order_seq_cst, memory_order_seq_cst);
}
/// @}

/// @} relates shared_ptr
/// @} group pointer_abstractions

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace

#endif // _SHARED_PTR_ATOMIC_H

内存模型的定义

内存模型(Memory Model)是定义数据一致性执行顺序规则的一组规范。

备忘录

  • 编程语言保证单线程的“程序顺序一致性”,比如为了防止CPU乱序执行,甚至主动对有依赖关系的变量插入内存屏障。

多核缓存

分层:

  • 寄存器:最快,由重命名机制管理
  • L1/L2/L3 Cache:核心本地缓存,按缓存行一致性(MESI)维护共享状态
  • 主内存(DRAM):CPU访问需经总线或内存控制器
缓存级别 位置 速度(快) 容量(小) 每核私有/共享 说明
L1 Cache CPU核心内部 ✅最快 ❌最小 每核私有 通常分为指令缓存(L1I)和数据缓存(L1D)
L2 Cache 核心内部或旁边 较快 较小 每核私有或共享 有助于减缓L1未命中后的访问压力
L3 Cache 核心集群共享 慢一些 更大 多核共享 减少跨核访问主存的延迟,常位于芯片中心
L4 Cache 一些高端CPU或封装外DRAM 最慢 最大 多芯片共享 非常少见(例如Intel的eDRAM)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[CPU Core] 
├── [Load Buffer] ← 处理 load 指令
├── [Store Buffer] ← 处理 store 指令
├── [L1 Cache]
└── [Execution Unit]

⬇️

[Shared L2 Cache] / [L3 Cache]

⬇️

[Memory Bus] ↔ [Main Memory (DRAM)]



[Other CPU Cores]

Store/Load Buffer

  • Load Buffer:

    • 位置:在 CPU 核心内部,靠近 Load/Store Unit。
    • 功能:暂存“load”(读取)指令的结果,等待内存或缓存返回数据。
    • 使用场景:比如你访问一个变量 x,如果还没拿到内存值,它就被放在 load buffer 等待。
  • Store Buffer:保存尚未提交的 store 写操作(延迟写回),可被后续 load 查询(store-to-load forwarding)。内存屏障(memory fence)可强制“写入完成后再继续”。

    • 位置:同样在 CPU 核心内部,紧挨 Load Buffer。
    • 功能:当执行 x = 5 这样的写操作时,并不会立刻写入内存,而是先写入 store buffer。
    • 延迟写回:写操作会被延后,在合适时机批量提交到缓存或主存中。
    • 注意:这就是为什么需要内存屏障(memory fence)来强制“写入完成后再继续”。

Store/Load Buffer是一个具备调度逻辑的指令队列,不是为了“缓存数据”。
之所以叫”Buffer”而不是”Queue”,是强调其“乱序 + 并发调度能力”。

与普通队列的对比:

对比项 普通队列 Load Buffer
数据结构 FIFO 队列 类似 CAM(Content Addressable Memory)或乱序数组
访问方式 一次 pop 一个 任意条目都能被访问、发射、取消
顺序 严格顺序 支持乱序发射、乱序完成、乱序提交
功能 暂存数据 追踪地址、状态、与 Store Buffer 比较、rollback 等

Intel 和 ARM 的实际叫法

  • Intel 官方架构手册:

    • 用词是 Load Buffer / Store Buffer
    • 有时叫 “Memory Ordering Buffer”
  • ARM 架构(如 Cortex-A76)

    • 常叫:Load-Store Queue(LSQ)
    • 还会细分为:
      • Load Queue(LQ)
      • Store Queue(SQ)

但即使叫“Queue”,也不一定是严格的队列行为,而是调度窗口结构。

缓存行(Cache Line)

  • 位置:在 CPU 的缓存(L1/L2/L3)中,缓存是以行(line)为单位存储的。
  • 功能:每行通常是 64 字节,它是 CPU 和内存之间最小的同步单位。
  • 状态(MESI 协议):
    • M(Modified): 修改过,主存未同步
    • E(Exclusive): 独占但未修改
    • S(Shared): 可共享读取
    • I(Invalid): 已失效

总线(Memory Bus / Interconnect)

  • 位置:连接多个 CPU 核心、缓存、主存的通信通道。
  • 功能:
    • 数据在 CPU 和内存之间传输
    • 执行原子操作时用于发送 LOCK# 或缓存一致性请求

🔗 示例:Intel 使用 Ring Bus、AMD 使用 Infinity Fabric。

主内存(Main Memory / DRAM)

  • 位置:通常是系统主板上的 DRAM 芯片。
  • 功能:存储所有不在 cache 中的数据,访问速度比 cache 慢很多。

🕓 延迟:访问主存通常需要 100ns ~ 几百ns,而访问 L1 Cache 只需几个 cycle。

内存控制器通道与总线的区别

维度 总线(Bus) 内存控制器通道(Memory Channel)
硬件层级 CPU、缓存、内存之间的共享通信总线 内存控制器内部的通路,直接连接 DRAM 芯片
作用范围 跨多核、跨缓存,整个系统范围 只负责访问主内存的某一部分,细粒度数据路径
连接对象 CPU核心、缓存、内存控制器等 内存控制器与物理内存条之间的接口
作用 传递内存访问请求,实现缓存一致性协议 调度内存读写,执行具体内存命令
原子操作锁定对象 锁定总线,阻止其他核访问内存 锁定内存通道,防止同通道冲突访问

乱序执行

现代 CPU 采用乱序执行(Out-of-Order Execution, OoO)优化性能:

  • 发射顺序有序(程序顺序)
  • 执行顺序无序(根据数据/资源依赖动态调度)
  • 提交顺序有序(借助 ROB 保证提交的程序语义)

核心机制:

  • 指令乱序执行:由调度器和执行单元动态决定执行顺序。
  • 寄存器重命名:使用临时物理寄存器消除写后写、写后读冲突。
  • Load/Store Buffer:用于暂存尚未提交的读写操作。
  • ROB(Reorder Buffer):按程序顺序提交指令(写入寄存器/内存),确保最终结果可预测。

程序顺序一致性(program-order consistency):

  • 在本线程中观察到的顺序要“看起来像顺序执行”。
  • 注意:多线程中可能出现乱序提交。
1
2
3
4
5
6
7
1. Fetch         <-- ✅ 顺序取指,从指令缓存中取出下一条指令
2. Decode <-- 顺序解码,分析操作数和目的寄存器
3. Rename <-- 寄存器重命名
4. Dispatch <-- 投递到调度窗口,等待执行条件满足
5. Execute <-- ✅ 乱序执行(由调度器决定),实际在执行单元上运行指令
6. Writeback <-- 写结果到 ROB
7. Commit <-- ✅ 按程序顺序提交(retire),更新寄存器状态或进行内存写入

TODO: 内存控制器

扩展:寄存器重命名(Register Renaming)

现代 CPU 为了支持乱序执行(Out-of-Order Execution)和指令级并行(ILP),会引入比架构寄存器更多的物理寄存器,来存储中间值。

寄存器重命名:CPU 用一张 寄存器映射表(Register Alias Table, RAT) 来将架构寄存器映射到物理寄存器。

  • 架构寄存器:由 ISA 定义,固定不变。x86-64 是 16 个通用寄存器。
  • 物理寄存器:由具体 CPU 实现,通常远多于架构寄存器。例如:
    • Intel 的 Skylake 有 180 个左右物理寄存器(整数+浮点)
    • ARM 的 Cortex-A 系列也有几百个物理寄存器(实际数量通常保密)
类型 说明
物理寄存器(Physical Register) CPU 内部实际使用的、很多个
架构寄存器(Architectural Register) 程序看到的,例如 RAX、RBX 等,一般只有 16~32 个

举例:

1
2
3
MOV RAX, 1
MOV RAX, 2
ADD RAX, 3

执行流程:

指令 分配的物理寄存器 对应动作
1 RAX → P1 P1 ← 1
2 RAX → P2 P2 ← 2(与1可并行执行)
3 用 P2 + 3 写入 P3,RAX → P3

注意:

  • 三条指令都写的是 RAX,但实际上写的是 不同的物理寄存器(P1、P2、P3)
  • 只有最后提交阶段才把 RAX 映射为最终结果的寄存器(P3)

内存屏障

屏障类型 会阻止 作用说明
SFENCE Store → Store 重排序 前面的写必须完成再执行后面的写
LFENCE Load → Load 重排序 后面的读必须等前面的读完成
MFENCE 所有内存访问 保证前面的 load/store 全部完成
问题 答案
内存屏障是运行时插入的吗? ❌ 插入时机是编译期,但运行时会执行它
屏障如何阻止后面指令提前? ✅ 屏障执行时会强制刷新缓冲区、阻止乱序执行

缓存一致性协议(MESI)

MESI 协议的核心操作:

  • 读(load):如果某核 cache 没有,就从主内存或其他核拉一份。
  • 写(store):必须先让其他核的对应 cache line 失效(invalidate),否则就可能出现数据竞争。

atomic(哪怕是 relaxed)为什么会触发 invalidate?

当你写入一个 std::atomic(哪怕是 relaxed):

1
x.store(123, std::memory_order_relaxed);
  • 这个 store 会编译为一条特殊的汇编指令(如 MOV 带 lock 前缀,或 STLR, STR 等)
  • CPU 会发出总线事务(bus transaction)或利用缓存一致性协议 广播这个写入:
    • 让其他核心中缓存这个变量所在 cache line 的副本 全部失效(Invalidate)
  • 所有核心必须从这个核心或主内存读取最新的值(下一次 load)

内存序

内存序 = 程序中读写内存操作的可见顺序。

在理想世界(顺序一致的架构)中,你写的代码顺序就是 CPU 执行和其他线程观察到的顺序。但现实中:

  • CPU 会乱序执行(out-of-order)
  • 编译器会重排指令
  • 缓存系统和 store/load buffer 会拖延内存访问
  • 多核之间访问的是缓存,而不是主内存

👉 所以,需要有一套规则来定义:“内存操作到底是何时、如何被其他线程看见的”,这就是内存序的目标。

概念 ^1 ^2

  • load: 从内存变量的值到CPU:内存 ➝ CPU。

  • store: 把一个值从 CPU 的寄存器或处理单元中,到内存中的某个地址(变量):CPU ➝ 内存。

  • relaxed: 对其他线程的读写没有同步或顺序约束,仅仅保证本操作的原子性。

  • acquire: 对 load 操作的内存序语义约束。

    • 当前线程中的任何读写都不能重排序到此 load 之前;
    • 在其他线程中 release 同一原子变量的所有写入在当前线程中可见。
  • release: 对 store 操作的内存序语义约束。

    • 当前线程中的任何读写都不能重排序到此 store 之后;
    • 当前线程的写入对 acquire 同一原子变量的其他线程可见。
  • acquire-release: 对 read-modify-write 操作的内存序语义约束。

    • 当前线程中的任何读写不能重排序到此 load 之前,也不能重排序到此 store 之后。
    • 其他线程 release 同一原子变量的写操作,对该 modification 可见;
    • modificationacquire 同一原子变量的其他线程可见。
  • sequentially-consistent:

    • load 操作遵循 acquire 语义;
    • store 操作遵循 release 语义;
    • read-modify-write 操作同时遵循 acquirerelease 语义;
    • 存在一个全序,其中所有线程都以相同的顺序观察所有修改。
内存序 插入屏障 特点
relaxed ❌ 无 只保证原子性,不保证顺序
acquire ✅ 读屏障 阻止后续操作提前
release ✅ 写屏障 阻止前面操作延后
acquire-release ✅ 两者都有 双向有序
seq_cst ✅ 全屏障 全局顺序一致性
步骤 普通变量 atomic(relaxed)
1 编译器可优化 编译器必须保留这个操作
2 CPU 可能重排 CPU 仍可能重排(因为是 relaxed)
3 缓存写入 可能停在本核 cache 中,不通知他人
4 不触发 invalidate ✅ 会触发 cache line invalidate
5 其他线程可见性低 ✅ 其他线程可读取到最新的值(但时序不保证)

私注:

  • acquire: 当本线程读取后,本线程之后的操作都可以依赖这次读取(“后面的读写不得提前”);
  • release: 当本线程允许写后,本线程之前的读写都完成了,即之后的操作都可以依赖此前的写入(“前面的读写不得滞后”)。

和普通变量相比,atomic(即使是 relaxed)做了哪些额外工作?

atomic(即使使用 memory_order_relaxed)和普通变量相比,最核心的区别是:原子变量保证原子性(atomicity)和可见性,而普通变量不能。

  • 保证操作的原子性

    所谓“原子性”,是指某个操作(如 load、store、CAS)要么全部完成、要么完全不做,不会出现中间状态。

    • atomic x;

      1
      x.store(42, std::memory_order_relaxed);

      这个 store 是原子的:不会被打断、不会被分拆。

    • 普通变量可能被编译器或 CPU 拆成多条指令(比如低 4 字节和高 4 字节分开发),多线程下可能看到“半成品”状态。

  • 触发 CPU 的 cache coherence 协议(MESI等)

    原子变量的访问会参与硬件层的缓存一致性协议,以保证多核 CPU 看到一致的值。

    • 即使是 relaxed,store 也会触发对应 cache line 的写入通知(invalidate);
    • 普通变量(非 volatile、非 atomic)的访问,编译器会缓存到寄存器中,不一定会回写。
  • 禁止编译器优化(只针对原子变量本身)

    编译器不能将多个 atomic store 合并,也不能删去它(不会当作“死代码”)。

    • x.store(42, relaxed) 每次都必须发出一条指令;

    • 对普通变量:

      1
      2
      x = 42;
      x = 43;

      可能直接编译为 x = 43;,前一条被优化掉。

atomic<T, relaxed> 不做的事:

功能 atomic(relaxed) 普通变量
保证原子性 ✅ 是 ❌ 否
保证可见性(跨线程) ✅ 是(通过 cache 协议) ❌ 否
禁止指令重排(保证顺序) ❌ 否(只 relaxed) ❌ 否

屏障为什么要设置两种?

性能优化 + 最小化开销 + 精确控制重排序方向。

屏障的本质是“控制指令重排序”
但它并不一刀切地“全部阻止”,而是:

屏障类型 阻止的方向(简化理解)
读屏障 阻止 读-after-读 重排序(即前面的读取不能晚于后面的读取)
写屏障 阻止 写-after-写 重排序(即前面的写不能晚于后面的写)
全屏障 阻止 读/写 与 所有后续指令的重排序

为什么分开这么细?(硬件视角)

现代 CPU 架构(如 x86, ARM)中:

  • 读和写通路是分离的

    • 读用 load buffer
    • 写用 store buffer
  • 两者乱序的模式、处理机制、性能代价都不同!

所以,硬件支持你只加读屏障(LFENCE)或写屏障(SFENCE),能以更小代价完成你想要的顺序语义。

举例:

操作 屏障类型 效果 例子
flag==1 后再读取 data 读屏障 禁止 data = ? 提前执行 load-acquire fence
data=42 后,才写 flag=1 写屏障 禁止 flag=1 提前写出 store-release fence
多线程通信中,强一致顺序 全屏障 所有读写顺序完全禁止重排 x86 MFENCE
  • 你可以只阻止读乱序 → 读屏障
  • 你可以只阻止写乱序 → 写屏障
  • 你可以全部阻止 → 全屏障

原子操作

层次 机制 说明
指令层 原子指令(如 lock cmpxchgxaddldrex/strex 提供不可中断的执行
缓存层 MESI 协议 保证多个CPU缓存数据一致
总线层 总线锁定(旧方式) 强制所有核等待该操作完成
内存层 内存屏障 保证内存操作顺序正确可见

CPU的原子指令如何实现的?

CPU 的原子指令是在硬件微架构层面通过微操作(micro-ops)调度、缓存控制、总线协议协调等机制联合实现的。我们可以从以下几个层面来详细剖析:

微架构层面:锁住特定资源

当执行原子指令时,CPU 内部会采取 锁定机制,确保该操作的所有子步骤在执行时不会被打断。

  • 对于访问内存的原子操作,CPU 会尝试锁定:
    • 缓存行(现代 CPU)
    • 或内存总线(旧 CPU)

以 x86 的 LOCK CMPXCHG 为例,它内部其实是:

1
2
3
4
5
6
7
if (mem == eax) {
mem = reg;
ZF = 1;
} else {
eax = mem;
ZF = 0;
}

这个流程在硬件中不是三条指令,而是一个专门的微操作指令组合包,称为“fused micro-op”,由 CPU 保证“执行期间中断关闭、禁止抢占”。

缓存一致性协议(MESI)保障原子性

原子指令通常访问共享变量,这就需要解决缓存一致性问题。

举例:两个 CPU 都缓存了某个共享变量的值
当 CPU1 执行原子写入(例如 lock xadd)时:

CPU1 会尝试将该缓存行从 Shared → Modified 状态

MESI 协议要求其他 CPU(如 CPU2)将该缓存行标记为 Invalid

一旦独占,CPU1 就能安全完成读-改-写过程

这种方式实现了 原子访问缓存行。

总线或互联互锁(bus lock / interconnect lock)

对于不在缓存中的内存地址(如非一致内存访问 NUMA、I/O 内存等),现代 CPU 仍可能退回到:

  • 总线锁定(Bus Lock)
  • 内存控制器互锁(memory interconnect lock)

比如 x86 的 lock 前缀会让 CPU 发出 LOCK# 信号,告诉其他核暂时禁止访问这段地址。

这是一种慢但可靠的 fallback 机制,避免跨节点访问带来的竞态。

禁止乱序与流水线干预

现代 CPU 为了性能采用乱序执行(Out-of-Order Execution)和流水线(Pipelining)机制。但原子操作必须:

  • 执行期间不得乱序
  • 禁止乱序缓存访问(如 Store Buffer 提前写入)
  • 强制所有早于它的读写完成,之后的读写等待

这依赖于:

  • 微指令插入内存屏障(memory fence)
  • 暂停 load/store buffer 的重排
  • Flush pipeline / reorder buffer

这就是为什么原子操作通常比普通操作要慢的原因之一。

例子:lock cmpxchg 的硬件执行流程

假设 CPU1 执行 lock cmpxchg [X], eax,大致流程如下:

  • CPU1 发出 LOCK# 信号或锁住缓存行 X(取决于地址是否在 cache)
  • 向 MESI 控制器发请求,抢占地址 X 的 cache line 独占权限
  • 在其他核心收到 invalidation 后,CPU1 获得修改权限
  • CPU1 比较 X 与 eax 的值,如果相等则更新为新值
  • 完成后通知 MESI controller,X 的状态设为 Modified
  • 操作结束,缓存一致性仍然维护

整个过程是由硬件控制单元(Load/Store Queue、Execution Unit、Bus Interface Unit)协调完成的。

小结:CPU 实现原子操作的关键机制

机制 功能
原子指令(如 lock cmpxchg, ldrex/strex 提供原子读-改-写
微操作调度锁定资源 保证在流水线中不可拆分
MESI 协议 多核共享缓存一致性
总线锁或互联锁 防止跨核心或I/O地址出现竞态
内存屏障 & 禁止乱序 防止指令与缓存失序访问

线程状态

  • New(新建):线程对象刚创建,还未开始执行。
  • Ready(就绪):线程准备好运行,等待调度器分配 CPU。
  • Running(运行):线程正在使用 CPU 执行指令。
  • Blocked(阻塞):线程在等待某个事件(如 I/O、锁、条件变量等),不能运行。
  • Terminated(终止):线程执行完毕或被强制结束。
  • Sleeping(休眠):线程主动暂停一段时间(如 sleep()),不能被调度。

线程状态转换图

当前状态 触发条件 转换后状态 说明
New 调用 start() 或 std::thread 构造函数 Ready 线程被创建,等待调度
Ready 被调度器选中 Running 获得 CPU,开始执行
Running 时间片耗尽 / yield() Ready 主动或被动让出 CPU,重新排队
Running 调用 sleep() / wait() / 等待锁 Blocked / Sleeping 线程不能继续执行,等待事件或时间
Blocked / Sleeping 条件满足 / 时间到 Ready 线程重新具备运行条件,等待调度
Running 执行结束或异常 Terminated 线程生命周期结束

性能指标

CPU时间

函数调用的 CPU 时间:

  • Inclusive time: total cpu time, include all functions it calls.
  • Exclusive time: only the time used by the function itself, exclusive all its children.

Refer to here.

  1. Wall time: total time the process used, containing IO time.

  2. CPU usage (CPU利用率) = CPU time / Wall time.

  3. real/user/system time

    • Real is wall clock time - time from start to finish of the call. This is all elapsed time including time slices used by other processes and time the process spends blocked (for example if it is waiting for I/O to complete).
    • User is the amount of CPU time spent in user-mode code (outside the kernel) within the process. This is only actual CPU time used in executing the process. Other processes and time the process spends blocked do not count towards this figure.
    • Sys is the amount of CPU time spent in the kernel within the process. This means executing CPU time spent in system calls within the kernel, as opposed to library code, which is still running in user-space. Like ‘user’, this is only CPU time used by the process. See below for a brief description of kernel mode (also known as ‘supervisor’ mode) and the system call mechanism.

    Refer to here.

  4. CPU 时间可能大于墙上时间:

    这是因为 CPU 时间是所有 CPU 核的运行时间的累加和,墙上时间则是实际的时间。此时 CPU 利用率大于 100%. (这是自己的理解)

  5. TODO: Is CPU time in flame graph sum of all the CPU time? Or is it the wall time when CPU works?

计时工具:timer

1
$ /usr/bin/time -p ls

Or,

1
$ time ls

其中(参考链接),

1
2
3
$ type -a time
time is a shell keyword
time is /usr/bin/time

分析工具

  • Performance Analyzer
  • Thread Analyzer
  • gprof
  • DDT/gdb

Performance Analyzer

Oracle Developer Studio 提供了多种工具:Performance Analyzer、Thread Analyzer。

Performance Analyzer 官方文档

1. 收集数据

使用 collect 命令收集数据(官方文档)。

1
collect collect-options program program-arguments

2. 开始性能分析

使用 analyzer 命令进行性能分析(官方文档)。

1
analyzer [control-options] [experiment | experiment-list]

例如:

1
analyzer -c test.1.er test.4.er

Thread Analyzer

Thread Analyzer 官方文档

gprof

gprof(GNU profiler)是GNU binutils工具集中的一个工具,linux系统当中会自带这个工具。它可以分析程序的性能,能给出函数调用时间、调用次数和调用关系,找出程序的瓶颈所在。在编译和链接选项中都加入-pg之后,gcc会在每个函数中插入代码片段,用于记录函数间的调用关系和调用次数,并采集函数的调用时间。

DDT

DDT

简介

“Hybrid Build”(混合构建)是指一种 兼顾调试能力与运行性能 的构建方式,常用于需要在 Release 环境中进行问题分析,但又不能完全使用 Debug 构建的场景。

🧩 Hybrid Build 的核心特征

特性 描述
优化等级 使用 -O2 或 -O3,保持接近 Release 的性能
调试信息 保留 -g,生成 DWARF 调试符号,便于分析 core dump 或使用 gdb
符号表 可选开启 -fno-omit-frame-pointer,便于栈回溯
日志/保护机制 可嵌入轻量级日志、ASAN-lite、canary 等机制,增强可观测性
部署策略 仅在内部或特定客户环境中使用,避免暴露完整源码结构或调试符号

✅ 编译示例(GCC/Clang)

1
g++ -O2 -g -fno-omit-frame-pointer -DNDEBUG -o your_program main.cpp
  • -O2:优化代码,接近 Release 性能
  • -g:保留调试信息
  • -fno-omit-frame-pointer:保留帧指针,便于栈追踪
  • -DNDEBUG:关闭断言(assert)

🎯 使用场景

场景 是否推荐使用 Hybrid Build 原因说明
客户现场复现崩溃 可通过 core dump + 符号表快速定位问题
内部性能测试 保持优化效果,同时可调试
正式发布给客户(大规模部署) 不建议,可能暴露符号信息,体积较大
与 ASAN/TSAN 联合使用 ⚠️(需关闭优化) ASAN/TSAN 更适合 Debug 构建,Hybrid 会影响检测精度

🛠️ 实践建议

  • 符号分离:使用 objcopy --only-keep-debug 分离调试符号,避免暴露给客户。
  • 符号服务器:内部维护符号服务器,支持通过 core 文件自动符号化。
  • 结合日志框架:Hybrid Build 可与轻量级日志框架结合,增强问题定位能力。

符号分离(Split Debug Info)

✅ 为什么要分离?

  • Release 版本:体积小,性能高,但缺少调试信息
  • 调试符号文件:保留完整符号信息,用于内部分析 core dump

🛠️ 分离流程(以 GCC/Clang 为例)

1
2
3
4
5
6
7
8
9
10
11
# 编译时保留调试信息
g++ -O2 -g -o your_program main.cpp

# 分离调试符号
objcopy --only-keep-debug your_program your_program.debug

# 去除主程序中的调试信息
strip --strip-debug --strip-unneeded your_program

# 添加调试符号关联信息
objcopy --add-gnu-debuglink=your_program.debug your_program

或者:

1
2
3
4
5
6
7
8
9
10
11
# 编译 Debug 版本(带调试信息)
gcc -g -O2 -o myapp_debug myapp.c

# 提取调试信息
objcopy --only-keep-debug myapp_debug myapp.debug

# 编译 Release 版本(去除调试信息)
strip --strip-debug myapp_debug -o myapp_release

# 使用 GDB 加载 Release + 调试符号
gdb --exec=myapp_release --symbols=myapp.debug

这样你就可以像调试 Debug 版本一样使用 GDB,但运行的是 Release 版本。

如果你有 Debug 和 Release 两个版本:

1
gdb --exec=myapp_release --symbols=myapp_debug

这会让 GDB 使用 Debug 版本的符号信息来调试 Release 程序。

✅ 最终产物:

  • your_program:可交付给客户的 Release 可执行文件
  • your_program.debug:内部使用的调试符号文件

core dump 分析

1. 客户侧设置 core dump

1
ulimit -c unlimited

2. 客户运行程序并生成 core 文件

1
2
./your_program crash_input.txt
# 程序崩溃后生成 core 文件,如 core.12345

3. 客户提供 core 文件 + 可执行文件

  • core.12345
  • your_program(Release 版本)

4. 你在内部分析 core 文件

1
2
3
4
gdb your_program core.12345
# 加载调试符号
(gdb) symbol-file your_program.debug
(gdb) bt # 查看调用栈

栈指针寄存器

TODO:

  • rsp

  • rbp

  • 压栈和出栈的过程

  • 使用 rsp 可以节省指令和寄存器

工具

valgrind 是一个强大的内存调试和性能分析工具,它的不同子工具用于不同的分析目的。--memcheck--massif 是其中两个常用的工具。

ASAN(AddressSanitizer) 和 TSAN(ThreadSanitizer) 都是由现代编译器(如 Clang 和 GCC)提供的 运行时检测工具,用于帮助开发者在开发阶段发现内存错误和线程问题。

  • Clang:全面支持 ASAN 和 TSAN
  • GCC:也支持,但 TSAN 的支持略逊于 Clang

博客:How to get a core dump for a segfault on Linux

Memcheck:内存错误检查工具

官方文档:4. Memcheck: a memory error detector

  • 用途:检测内存相关的错误,如内存泄漏、越界访问、未初始化内存读取等。
  • 适用场景:调试程序中的内存错误,确保程序的内存使用是安全的。
  • 输出内容:
    • 哪些内存没有释放(内存泄漏)
    • 哪些内存被非法访问(越界、未初始化等)
    • 哪些内存访问是未定义行为
  • 常用命令:
1
valgrind --tool=memcheck ./your_program

Massif:堆内存使用分析工具

官方文档:9. Massif: a heap profiler

  • 用途:分析程序在运行过程中堆内存的使用情况,帮助优化内存占用。
  • 适用场景:性能分析,找出内存占用高的代码路径或数据结构。
  • 输出内容:
    • 堆内存使用随时间的变化(快照):需用 ms_printPostScript Viewer 查看
    • 哪些函数或调用路径分配了最多的内存
    • 常用命令:
1
2
valgrind --tool=massif ./your_program
ms_print massif.out.<pid>

🆚 Memcheck vs Massif 对比总结

特性 --memcheck --massif
工具类型 内存错误检查工具 堆内存使用分析工具
主要用途 检查内存泄漏、越界访问、未初始化读取等 分析堆内存使用趋势和峰值
检测内存泄漏 ❌(不直接检测)
分析内存增长趋势
输出格式 错误报告(文本) 内存快照(需用 ms_print 查看)
性能开销 高(运行速度变慢) 中等

ThreadSanitizer(TSAN)

  • 用途:检测多线程程序中的 数据竞争(data race) 和其他线程同步问题。
  • 适用场景:并发程序调试,尤其是当多个线程访问共享变量时。
  • 检测内容:
    • 数据竞争(两个线程同时访问同一变量,且至少一个是写操作)
    • 锁使用错误(死锁、双重解锁等)
  • 启用方式(Clang/GCC):
1
clang -fsanitize=thread -g your_program.c -o your_program

AddressSanitizer(ASAN)

AddressSanitizer 文档

  • 用途:检测内存访问错误。
  • 适用场景:单线程或多线程程序中调试内存问题。
  • 检测内容:
    • 越界访问(stack/heap/global)
    • use-after-free(释放后使用)
    • 内存泄漏(可选)
    • use-after-scope(作用域结束后使用局部变量)
  • 启用方式:
1
clang -fsanitize=address -g your_program.c -o your_program

🆚 TSAN vs ASAN 对比总结

特性 TSAN(ThreadSanitizer) ASAN(AddressSanitizer)
检测目标 多线程数据竞争 内存访问错误
是否支持多线程 ✅(专为多线程设计) ✅(支持,但不检测数据竞争)
性能开销 较高(10x~40x) 中等(2x~3x)
内存开销 中等 较高(增加约2倍内存使用)
是否检测内存泄漏 ❌(不检测) ✅(可选开启)
是否检测数据竞争

🆚 Memcheck vs Massif vs TSAN vs ASAN 对比总结

工具名称 类型 主要用途 检测内容 是否支持多线程 性能开销 内存开销 是否检测内存泄漏 是否检测数据竞争
Memcheck Valgrind 工具 内存错误检测 内存泄漏、越界访问、未初始化读取、非法释放等 ✅(有限支持) 高(10x+)
Massif Valgrind 工具 堆内存使用分析 堆内存分配趋势、内存峰值、调用路径分析 中等 中等
ASAN 编译器工具 内存访问错误检测 越界访问、use-after-free、use-after-scope、内存泄漏(可选) 中等(2x~3x) 高(约2倍) ✅(可选)
TSAN 编译器工具 多线程数据竞争检测 数据竞争、死锁、错误的锁使用等 ✅(强支持) 高(5x~40x) 中等

UBSan (Unifined Behavior Sanitizer)

Sanitizer 检测内容 Google 贡献
ASAN 内存访问错误 ✅ 是
UBSan 未定义行为 ✅ 是
TSAN 数据竞争 ✅ 是
MSAN 未初始化内存使用 ✅ 是

__attribute__((__visibility__("default")))

__attribute__((__visibility__("default"))) 是 GCC 编译器的一个属性,用于控制符号的可见性。它指定了一个符号(如函数或变量)在共享库中的可见性。

含义:

  • default 可见性
    • 符号可以被其他共享库或可执行文件访问。
    • 符号会被导出到共享库的符号表中。

用途:

  • 用于显式导出符号,使其在动态链接时可被其他模块使用。

  • 在共享库中,默认情况下符号是 default 可见的,但使用 -fvisibility=hidden 编译选项时,所有符号会被隐藏,只有显式标记为 default 的符号才会导出。

  • 编译器优化的影响:即使没有 -fvisibility=hidden,某些编译器优化(如 -flto)可能会影响符号的导出。
    显式使用 __attribute__((__visibility__("default"))) 可以避免这些问题。

示例:

1
2
3
4
__attribute__((__visibility__("default")))
void myFunc() {
// Function implementation
}

可以通过以下步骤确认 myFunc 是否在被链接时可见:

方法 1: 使用 nm 工具检查符号

nm 是一个工具,可以列出目标文件或共享库中的符号表。

  1. 检查 libchip.so 中是否导出了 myFunc

    1
    nm -D libchip.so | grep myFunc
    • 如果 myFunc 出现在输出中,说明它被导出并且可见。
    • 如果没有出现,可能是符号被隐藏(例如使用了 -fvisibility=hidden)。
  2. 如果 myFunc 没有导出:

    • 确认是否在代码中使用了 __attribute__((__visibility__("default")))
    • 确认编译时是否启用了 -fvisibility=hidden

方法 2: 使用 readelf 检查动态符号

readelf 可以显示共享库的动态符号表。

  1. 检查 libchip.so 的动态符号表:
    1
    readelf -Ws libchip.so | grep myFunc
    • 如果 myFunc 出现在输出中,说明它是动态可见的。
    • 如果没有出现,说明符号被隐藏。

方法 3: 检查链接依赖关系

  1. 检查 libdbg.so 是否声明了对 libchip.so 的依赖:

    1
    readelf -d libdbg.so | grep NEEDED
    • 如果 libchip.so 出现在 NEEDED 列表中,说明 libdbg.so依赖 libchip.so
  2. 如果 libchip.so 在依赖列表中,但链接时仍然报错:

    • 确认 myFunc 是否在 libchip.so 中导出(使用 nmreadelf 检查)。

方法 4: 检查链接器错误

如果链接器报错 undefined reference to myFunc

  • 确认链接命令是否显式包含 libchip.so
    1
    g++ -o executable main.o -L/path/to/libs -ldbg -lchip
  • 如果没有显式链接 libchip.so,动态链接器可能无法解析 myFunc

总结:

  • 使用 nmreadelf 检查 libchip.so 是否导出了 myFunc
  • 如果符号未导出,确保代码中使用了 __attribute__((__visibility__("default"))) 并检查编译选项。

📝 现象描述

当你运行一个 ELF 可执行文件(比如一个 32-bit 的程序),而它依赖的 loader 或共享库找不到 时,Shell 会提示:

1
bash: ./a.out: No such file or directory

但其实,这个“文件”确实存在,问题出在它 依赖的 loader 文件或库文件找不到,进而导致 execve() 系统调用失败。

我们从 内核执行路径 角度来解析这背后的原理。

🧠Linux 内部逻辑解析

  1. Shell 运行程序的过程
1
./my_app

Shell 实际做的是调用 execve() 系统调用:

1
execve("./my_app", argv, envp);

这是 Linux 加载并运行一个程序的唯一入口。

  1. execve() 做了什么?

内核执行 execve() 时,它会:

🔹 Step 1: 打开并读取 ELF 头(文件的前几个字节)
从而判断这是一个 ELF 可执行文件、脚本,还是其他格式。

🔹 Step 2: 检查 ELF 的架构位数、ABI、动态链接需求
对于动态链接程序,它会在 ELF 头中读取如下字段:

  • e_ident[EI_CLASS]: 32-bit 或 64-bit
  • e_interpreter: 这是最关键的!
  1. e_interpreter 是什么?

这是 ELF 文件里定义的 “程序解释器路径”(interpreter path)。即这个程序运行时,系统需要先加载谁来帮它加载剩下的动态库。

可以通过 readelf -l my_app 查看:

1
2
3
$ readelf -l ./my_app | grep interpreter

[Requesting program interpreter: /lib/ld-linux.so.2]

比如:/lib/ld-linux.so.2 是 32-bit 程序使用的 loader。

  1. 如果这个 loader 不存在,会发生什么?
  • execve() 尝试打开 ELF 指定的解释器(/lib/ld-linux.so.2)
  • 如果该文件不存在,open() 失败
  • 整个 execve() 调用失败
  • 错误代码是 ENOENT(2),代表:

“No such file or directory”

但这并不是说 你运行的那个文件 ./my_app 不存在,而是 它依赖的解释器不在系统中,导致整个执行失败。

🤯 为什么这么误导?

因为 shell(bash/zsh)调用 execve() 失败后,只看到了 errno = ENOENT,它默认解释为:

“你指定的那个文件路径不存在”

而不是更深层次的:

“文件存在,但它需要的 loader 不存在”

这是 shell 的 历史遗留行为,没有细分 errno 背后语义。

🧪 举个实际例子

1
2
3
4
5
6
7
8
9
10
11
$ file ./a.out
./a.out: ELF 32-bit LSB executable, Intel 80386, ...

$ readelf -l ./a.out | grep interpreter
[Requesting program interpreter: /lib/ld-linux.so.2]

$ ls /lib/ld-linux.so.2
ls: cannot access '/lib/ld-linux.so.2': No such file or directory

$ ./a.out
bash: ./a.out: No such file or directory ❌

实际上是 缺少解释器 /lib/ld-linux.so.2,而不是 a.out 本身。

✅ 总结

层级 行为
用户 输入 ./prog
Shell 调用 execve("./prog", ...)
内核 解析 ELF,发现 interpreter/lib/ld-linux.so.2
内核 找不到解释器,返回 ENOENT
Shell No such file or directory ❌(误导性)

🛠️ Bonus:编译 32-bit 程序

  1. 编写一个简单的 C 程序
1
2
3
4
5
6
7
// hello.c
#include <stdio.h>

int main() {
printf("Hello from 32-bit program!\n");
return 0;
}
  1. 编译成 32 bit 程序

需要先安装 32-bit 编译支持:

1
2
sudo apt update
sudo apt install gcc-multilib

然后编译:

1
gcc -m32 hello.c -o hello32
  1. 验证是否是 32-bit ELF 可执行文件
1
file hello32

输出应类似:

1
hello32: ELF 32-bit LSB executable, Intel 80386, ...

Makefileview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
CXX = g++
CXXFLAGS = -fPIC -Wall -Wextra
LDFLAGS = -shared

all: main libhello.so

main: main.cpp
$(CXX) main.cpp -o main -ldl

libhello.so: hello.cpp
$(CXX) $(CXXFLAGS) $(LDFLAGS) hello.cpp -o libhello.so

clean:
rm -f main libhello.
main.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <dlfcn.h>

#include <iostream>

typedef void (*HelloFunc)();

int main() {
// 打开共享库
void* handle = dlopen("./libhello.so", RTLD_LAZY);
if (!handle) {
std::cerr << "dlopen failed: " << dlerror() << std::endl;
return 1;
}

// 清除之前的错误
dlerror();

// 获取函数指针
HelloFunc hello = (HelloFunc)dlsym(handle, "hello");
const char* dlsym_error = dlerror();
if (dlsym_error) {
std::cerr << "dlsym failed: " << dlsym_error << std::endl;
dlclose(handle);
return 1;
}

// 打印函数地址
std::cout << "Address of hello function: " << reinterpret_cast<void*>(hello) << std::endl;

// 调用函数
hello();

// 关闭共享库
dlclose(handle);
return 0;
}

定义

当两个线程同时修改原子变量时,以下操作会发生:

原子性:原子变量的修改是原子的,即每次修改都是一个不可分割的操作。这意味着在任何时刻,只有一个线程能够成功地修改原子变量,而不会出现竞争条件。

同步机制:原子变量使用硬件级别的同步机制(如锁、比较并交换操作等)来确保修改的原子性。这些机制确保线程在修改原子变量时不会干扰其他线程的操作。

内存可见性:原子变量的修改会确保内存可见性,即一个线程对原子变量的修改会立即对其他线程可见。这意味着其他线程可以看到最新的修改结果,而不会读取到过时的数据。

举个例子,假设我们有一个原子变量 std::atomic<int> counter,两个线程同时执行 counter++ 操作:

atomic1.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <atomic>
#include <thread>
#include <iostream>

std::atomic<int> counter(0);

void increment() {
for (int i = 0; i < 1000; ++i) {
counter++;
}
}

int main() {
std::thread t1(increment);
std::thread t2(increment);

t1.join();
t2.join();

std::cout << "Final counter value: " << counter << std::endl;
return 0;
}

在这个例子中:

两个线程 t1 和 t2 同时执行 increment 函数,尝试修改原子变量 counter。
原子性 确保每次 counter++ 操作都是不可分割的,避免竞争条件。
同步机制 确保两个线程不会同时修改 counter,而是一个线程成功修改后,另一个线程才能继续修改。
内存可见性 确保 counter 的最新值对两个线程都是可见的。

实现机制

让我们深入探讨一下两个线程同时修改原子变量时的底层机制。

  1. 原子操作的硬件支持
    原子操作通常由硬件指令支持,这些指令确保操作的原子性。例如,x86架构提供了 LOCK 前缀,用于确保指令在多处理器环境中的原子性。常见的原子指令包括 LOCK XADD(原子加法)和 LOCK CMPXCHG(原子比较并交换)。

  2. 缓存一致性协议
    多核处理器使用缓存一致性协议(如MESI协议)来确保各个处理器缓存中的数据一致性。当一个处理器修改原子变量时,缓存一致性协议会确保其他处理器的缓存中对应的数据无效或更新。

  3. 内存屏障
    内存屏障(Memory Barrier)是一种指令,用于防止编译器和处理器对内存操作进行重排序。原子操作通常会使用内存屏障来确保操作的顺序性和可见性。例如,std::atomic 在实现时会使用内存屏障来确保操作的正确性。

  4. 比较并交换(CAS)
    比较并交换(Compare-And-Swap, CAS)是一种常用的原子操作,它通过比较变量的当前值和预期值,如果相等则更新变量的值。CAS操作是无锁编程的基础,用于实现许多并发数据结构。

  5. 伪代码示例
    以下是一个伪代码示例,展示了CAS操作的工作原理:

cas_mock.cppview raw
1
2
3
4
5
6
7
bool compare_and_swap(int* ptr, int old_value, int new_value) {
if (*ptr == old_value) {
*ptr = new_value;
return true;
}
return false;
}

在多线程环境中,CAS操作可以确保只有一个线程成功修改变量的值,而其他线程会失败并重试。

  1. 实际应用
    在实际应用中,原子变量的操作可能如下所示:
atomic2.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <atomic>
#include <thread>
#include <iostream>

std::atomic<int> counter(0);

void increment() {
for (int i = 0; i < 1000; ++i) {
int expected = counter.load();
while (!counter.compare_exchange_weak(expected, expected + 1)) {
// 重试,直到成功
}
}
}

int main() {
std::thread t1(increment);
std::thread t2(increment);

t1.join();
t2.join();

std::cout << "Final counter value: " << counter << std::endl;
return 0;
}

在这个例子中,compare_exchange_weak 使用CAS操作来确保 counter 的原子性修改。每次修改失败时,线程会重试,直到成功。

缓存一致性协议

缓存一致性协议是确保多核处理器中各个缓存之间数据一致性的机制。最常见的缓存一致性协议是MESI协议。让我们详细解释一下。

MESI协议

MESI协议是由四种状态组成的缓存一致性协议,每个缓存行(Cache Line)可以处于以下四种状态之一:

  • Modified(修改):缓存行中的数据已被修改,与主内存中的数据不一致,且该数据仅存在于当前缓存中。
  • Exclusive(独占):缓存行中的数据与主内存中的数据一致,且该数据仅存在于当前缓存中。
  • Shared(共享):缓存行中的数据与主内存中的数据一致,且该数据可能存在于多个缓存中。
  • Invalid(无效):缓存行中的数据无效。

状态转换

缓存行的状态会根据不同的操作进行转换。以下是一些常见的状态转换:

从主内存读取数据:如果一个缓存行处于Invalid状态,当一个处理器读取该数据时,缓存行会变为Shared或Exclusive状态。
修改数据:如果一个缓存行处于Shared或Exclusive状态,当一个处理器修改该数据时,缓存行会变为Modified状态,并通知其他缓存将该缓存行置为Invalid状态。
写回数据:如果一个缓存行处于Modified状态,当该缓存行被替换时,数据会被写回主内存,缓存行变为Invalid状态。

工作原理

假设有三个处理器A、B和C,它们各自有自己的缓存。主内存中有一个变量x,初始值为0。

读取数据:

处理器A从主内存读取x,缓存行状态变为Exclusive。
处理器B从主内存读取x,处理器A检测到冲突,将缓存行状态变为Shared,处理器B的缓存行状态也变为Shared。
修改数据:

处理器A修改x,缓存行状态变为Modified,并通知处理器B将其缓存行状态变为Invalid。
处理器B尝试读取x时,检测到缓存行无效,从主内存重新读取数据。

写回数据:

处理器A将修改后的数据写回主内存,缓存行状态变为Invalid。

优化和问题

缓存一致性协议通过总线嗅探(Bus Snooping)和状态机机制来实现数据的一致性,但也会引入一些性能问题,如总线带宽压力和处理器等待时间。为了解决这些问题,现代处理器引入了存储缓冲区(Store Buffer)和写回策略(Write Back)等优化技术。

CAS

比较并交换(Compare-And-Swap, CAS)操作在并发编程中有许多好处:

  1. 无锁编程
    CAS操作是无锁编程的基础,它允许多个线程在不使用锁的情况下安全地修改共享数据。无锁编程可以减少锁的开销,避免死锁,提高系统的并发性能。

  2. 原子性
    CAS操作是原子的,即它确保比较和交换操作在硬件级别上是不可分割的。这意味着在任何时刻,只有一个线程能够成功地修改变量的值,避免竞争条件。

  3. 高效性
    CAS操作通常由硬件指令支持(如x86架构中的 LOCK CMPXCHG 指令),这些指令非常高效,能够快速完成比较和交换操作。相比于使用锁,CAS操作的开销更低。

  4. 可扩展性
    CAS操作允许多个线程同时尝试修改变量,而不会阻塞其他线程。这种特性使得CAS操作在高并发环境中具有良好的可扩展性,能够处理大量线程的并发访问。

  5. 实现复杂的并发数据结构
    CAS操作可以用于实现复杂的并发数据结构,如无锁队列、无锁栈等。这些数据结构能够在高并发环境中提供高效的操作,而不会引入锁的开销。

以下是一个使用CAS操作实现无锁计数器的示例:

cas_counter.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <atomic>
#include <thread>
#include <iostream>

std::atomic<int> counter(0);

void increment() {
for (int i = 0; i < 1000; ++i) {
int expected = counter.load();
while (!counter.compare_exchange_weak(expected, expected + 1)) {
// 重试,直到成功
}
}
}

int main() {
std::thread t1(increment);
std::thread t2(increment);

t1.join();
t2.join();

std::cout << "Final counter value: " << counter << std::endl;
return 0;
}

在这个例子中,compare_exchange_weak 使用CAS操作来确保 counter 的原子性修改。每次修改失败时,线程会重试,直到成功。

compare_exchange_weak 和 fetch_add

compare_exchange_weak 和 fetch_add 是两种不同的原子操作,它们在功能和使用场景上有明显的区别。让我们详细解释一下它们的区别以及如何选择。

compare_exchange_weak

功能:

compare_exchange_weak 是一种CAS(Compare-And-Swap)操作,用于比较原子变量的当前值与预期值,如果相等,则将新值存储到变量中,并返回 true;如果不相等,则返回 false 并更新预期值。
该操作允许偶尔的失败(即使当前值与预期值相等,也可能返回 false),这在一些循环算法中是可以接受的。

使用场景:

适用于需要在循环中反复尝试更新变量的场景,例如实现无锁数据结构(如无锁队列、栈等)。
在高并发环境中,compare_exchange_weak 通常比 compare_exchange_strong 性能更高,因为它允许偶尔的失败,从而减少了总线锁定的开销.

fetch_add

功能:

fetch_add 是一种原子加法操作,它将给定的值加到原子变量的当前值中,并返回变量的旧值。
该操作是原子的,确保在多线程环境中不会出现竞争条件。

使用场景:

适用于简单的计数器或累加器场景,例如统计访问次数、累加总和等。
在需要对变量进行简单的加法操作时,fetch_add 是一个高效的选择2.

如何选择

选择 compare_exchange_weak 还是 fetch_add 取决于具体的使用场景和需求:

如果需要实现复杂的无锁数据结构(如无锁队列、栈等),并且需要反复尝试更新变量,选择 compare_exchange_weak。
如果需要对变量进行简单的加法操作(如计数器、累加器),选择 fetch_add。
示例代码
以下是使用 compare_exchange_weak 和 fetch_add 的示例代码:

compare_exchange_weak 示例:

compare_exchange_weak_eg.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <atomic>
#include <thread>
#include <iostream>

std::atomic<int> counter(0);

void increment() {
for (int i = 0; i < 1000; ++i) {
int expected = counter.load();
while (!counter.compare_exchange_weak(expected, expected + 1)) {
// 重试,直到成功
}
}
}

int main() {
std::thread t1(increment);
std::thread t2(increment);

t1.join();
t2.join();

std::cout << "Final counter value: " << counter << std::endl;
return 0;
}

fetch_add 示例:

fetch_add_eg.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <atomic>
#include <thread>
#include <iostream>

std::atomic<int> counter(0);

void increment() {
for (int i = 0; i < 1000; ++i) {
counter.fetch_add(1);
}
}

int main() {
std::thread t1(increment);
std::thread t2(increment);

t1.join();
t2.join();

std::cout << "Final counter value: " << counter << std::endl;
return 0;
}

如果我们只需要简单地递增计数器,并且没有其他条件限制,fetch_add 确实是一个更直接和高效的选择。fetch_add 能够确保每次递增操作都是原子的,避免了竞争条件。

然而,在某些特定场景下,compare_exchange_weak 可能更为合适。例如,当我们需要基于特定条件进行更新时,compare_exchange_weak 可以确保只有在满足条件时才进行更新操作。

示例:基于条件的更新
假设我们有一个计数器,需要在满足特定条件时进行递增操作:

cas_case.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <atomic>
#include <thread>
#include <iostream>

std::atomic<int> counter(0);

void conditional_increment() {
for (int i = 0; i < 1000; ++i) {
int expected = counter.load();
while (expected < 500 && !counter.compare_exchange_weak(expected, expected + 1)) {
// 重试,直到成功或条件不满足
}
}
}

int main() {
std::thread t1(conditional_increment);
std::thread t2(conditional_increment);

t1.join();
t2.join();

std::cout << "Final counter value: " << counter << std::endl;
return 0;
}

在这个例子中,只有当 counter 的值小于500时,才会进行递增操作。compare_exchange_weak 确保条件更新的原子性和安全性。

使用 fetch_add 的场景
如果我们不需要基于条件进行更新,只是简单地递增计数器,那么 fetch_add 是一个更好的选择:

fetch_add_case.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <atomic>
#include <thread>
#include <iostream>

std::atomic<int> counter(0);

void increment() {
for (int i = 0; i < 1000; ++i) {
counter.fetch_add(1);
}
}

int main() {
std::thread t1(increment);
std::thread t2(increment);

t1.join();
t2.join();

std::cout << "Final counter value: " << counter << std::endl;
return 0;
}

在这个例子中,fetch_add 确保每次递增操作都是原子的,避免了竞争条件。

总结来说,如果你的操作只是简单的递增,fetch_add 是更高效的选择;如果需要基于条件进行更新,compare_exchange_weak 则更为合适。

ABA

ABA问题在并发编程中是一个常见的问题,尤其是在使用CAS(Compare-And-Swap)操作时。ABA问题的本质是一个变量的值在两次比较之间发生了变化,但最终值又回到了原始值,导致CAS操作无法检测到这种变化。为了避免ABA问题,可以使用带有版本号或标记的原子引用,例如 AtomicStampedReference。

示例:使用 AtomicStampedReference 避免ABA问题
以下是一个使用 AtomicStampedReference 避免ABA问题的示例:

atomic_stamped_reference.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <atomic>
#include <iostream>
#include <thread>
#include <vector>

std::atomic<int> counter(0);
std::atomic<int> stamp(0);

void conditional_increment() {
for (int i = 0; i < 1000; ++i) {
int expected = counter.load();
int expected_stamp = stamp.load();
// FIXME: 这种方式不可行,因为可能发生:expecited 更新了,但 expected_stamp
// 没有更新
while (expected < 500 &&
!counter.compare_exchange_weak(expected, expected + 1) &&
!stamp.compare_exchange_weak(expected_stamp, expected_stamp + 1)) {
// 重试,直到成功或条件不满足
}
}
}

int main() {
std::thread t1(conditional_increment);
std::thread t2(conditional_increment);

t1.join();
t2.join();

std::cout << "Final counter value: " << counter << std::endl;
std::cout << "Final stamp value: " << stamp << std::endl;
return 0;
}

在这个例子中,我们使用了一个额外的 stamp 变量来记录每次更新的版本号。每次更新 counter 时,同时更新 stamp。这样,即使 counter 的值回到了原始值,stamp 的值也会不同,从而避免了ABA问题。

解释
版本号:每次更新 counter 时,同时更新 stamp,确保每次更新都有一个唯一的版本号。
CAS操作:使用 compare_exchange_weak 确保 counter 和 stamp 的更新是原子的。
重试机制:如果CAS操作失败,线程会重试,直到成功或条件不满足。
这种方法通过引入版本号或标记,确保即使变量的值回到了原始值,版本号也会不同,从而避免了ABA问题。

ABA问题不仅存在于CAS操作中,还可能在其他并发编程场景中出现。以下是一些可能出现ABA问题的情景:

  1. 双重检查锁定(Double-Checked Locking)
    在双重检查锁定模式中,ABA问题可能会导致错误的判断。例如,在初始化单例对象时,如果两个线程同时检查对象是否为空,并且一个线程在检查后立即创建对象,而另一个线程在检查后发现对象已经被创建并且再次检查时发现对象为空,这可能会导致错误的初始化。

  2. 无锁队列和栈
    在无锁队列和栈的实现中,ABA问题可能会导致节点的插入和删除操作出现错误。例如,一个线程在删除节点时,另一个线程可能会插入和删除相同的节点,导致第一个线程无法正确判断节点的状态。

  3. 版本控制
    在版本控制系统中,ABA问题可能会导致错误的版本判断。例如,一个线程在检查版本号时,另一个线程可能会更新版本号并且再次更新回原始版本号,导致第一个线程无法正确判断版本是否被修改。

解决方案
为了避免ABA问题,可以使用以下解决方案:

版本号或标记:使用版本号或标记来记录每次更新的状态。例如,使用 AtomicStampedReference 来确保每次更新都有一个唯一的版本号。
时间戳:使用时间戳来记录每次更新的时间,确保每次更新都有一个唯一的时间标记。
逻辑时钟:使用逻辑时钟来记录每次更新的顺序,确保每次更新都有一个唯一的顺序标记。
示例:使用 AtomicStampedReference 避免ABA问题
以下是一个使用 AtomicStampedReference 避免ABA问题的示例:

atomic_stamped_reference.javaview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.concurrent.atomic.AtomicStampedReference;

public class ABAExample {
private static AtomicStampedReference<Integer> atomicStampedRef = new AtomicStampedReference<>(0, 0);

public static void main(String[] args) {
Thread t1 = new Thread(() -> {
int stamp = atomicStampedRef.getStamp();
Integer value = atomicStampedRef.getReference();
System.out.println("Thread 1 initial value: " + value + ", stamp: " + stamp);
atomicStampedRef.compareAndSet(value, value + 1, stamp, stamp + 1);
System.out.println("Thread 1 updated value: " + atomicStampedRef.getReference() + ", stamp: " + atomicStampedRef.getStamp());
});

Thread t2 = new Thread(() -> {
int stamp = atomicStampedRef.getStamp();
Integer value = atomicStampedRef.getReference();
System.out.println("Thread 2 initial value: " + value + ", stamp: " + stamp);
atomicStampedRef.compareAndSet(value, value + 1, stamp, stamp + 1);
System.out.println("Thread 2 updated value: " + atomicStampedRef.getReference() + ", stamp: " + atomicStampedRef.getStamp());
});

t1.start();
t2.start();
}
}

在这个例子中,AtomicStampedReference 使用版本号来避免ABA问题,确保每次更新都有一个唯一的版本号。

C++ 标准库中没有直接等同于 Java 的 AtomicStampedReference 的类,但你可以通过组合 std::atomic 和自定义结构体来实现类似的功能。以下是一个示例,展示如何在 C++ 中实现带有版本号的原子引用,以避免 ABA 问题:

示例:实现带有版本号的原子引用

cas_with_version.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <atomic>
#include <iostream>
#include <thread>

struct StampedValue {
int value;
int stamp;
};

std::atomic<StampedValue> atomicStampedValue{StampedValue{0, 0}};

void increment() {
for (int i = 0; i < 1000; ++i) {
StampedValue expected = atomicStampedValue.load();
StampedValue newValue;
do {
newValue = {expected.value + 1, expected.stamp + 1};
} while (!atomicStampedValue.compare_exchange_weak(expected, newValue));
}
}

int main() {
std::thread t1(increment);
std::thread t2(increment);

t1.join();
t2.join();

StampedValue finalValue = atomicStampedValue.load();
std::cout << "Final value: " << finalValue.value << ", Final stamp: " << finalValue.stamp << std::endl;
return 0;
}

解释
StampedValue 结构体:包含一个值和一个版本号(或时间戳)。
std::atomic:使用 std::atomic 包装 StampedValue 结构体,以确保原子性操作。
compare_exchange_weak:在更新值和版本号时使用 CAS 操作,确保操作的原子性和避免 ABA 问题。
使用场景
这种方法适用于需要避免 ABA 问题的场景,例如无锁队列、无锁栈等复杂并发数据结构。

compare_exchange_weak 和 compare_exchange_strong

区别
可靠性:

compare_exchange_weak:允许偶尔失败,即使当前值与期望值相等,也可能返回 false。这种设计是为了提高性能,适用于循环中的自旋锁等场景。
compare_exchange_strong:保证操作成功,如果当前值与期望值相等,则一定返回 true。适用于需要确保操作成功的场景。
性能:

compare_exchange_weak:通常比 compare_exchange_strong 性能更高,因为它允许偶尔失败。
compare_exchange_strong:在某些平台上性能可能较低,因为它需要确保操作成功。
适用场景
compare_exchange_weak:

  • 适用于循环中的自旋锁。
  • 适用于高性能要求的场景。

compare_exchange_strong:

  • 适用于需要确保操作成功的场景。
  • 适用于线程同步。

compare_exchange_weak 允许虚假失败的底层实现基于 CAS(Compare-And-Swap) 操作和硬件指令的特性。以下是详细解释:

CAS操作
CAS 操作有三个参数:内存地址、预期值和新值。其基本原理是:

比较内存地址中的值是否与预期值相等。
如果相等,则将内存地址中的值更新为新值。
如果不相等,则不做任何操作,并返回当前内存地址中的值。
虚假失败的原因
compare_exchange_weak 允许虚假失败,即使当前值与预期值相等,也可能返回 false。这种情况通常发生在以下几种情况:

缓存一致性问题:

在多核处理器中,缓存一致性协议可能导致 CAS 操作失败,即使内存中的值没有改变。例如,在 ARM 架构中,使用 LDXR/STXR 指令时,其他线程对同一缓存行的访问可能导致 CAS 操作失败1。
硬件指令的实现:

在某些平台上,CAS 操作可能被实现为单次 LL/SC(Load-Linked/Store-Conditional)尝试。这种实现允许 CAS 操作偶尔失败,以提高性能

为什么compare_exchange_strong不被用于实现自旋锁?
Copilot said:
Copilot
compare_exchange_strong 通常不用于实现自旋锁,主要原因在于其性能和设计目的:

性能
compare_exchange_strong 保证操作成功,如果当前值与预期值相等,则一定返回 true1。这种保证需要更多的硬件资源和时间来完成操作,可能导致性能下降1。
compare_exchange_weak 允许偶尔失败,即使当前值与预期值相等,也可能返回 false1。这种设计减少了硬件资源的消耗,提高了性能1。
设计目的
自旋锁 的设计目的是在短时间内频繁尝试获取锁,而不是长时间等待。因此,自旋锁更适合使用 compare_exchange_weak,因为它可以在失败时快速重试1。
compare_exchange_strong 更适合需要确保操作成功的场景,如线程同步1。在这些场景中,操作的成功率比性能更重要。
代码示例
以下是一个使用 compare_exchange_weak 实现自旋锁的示例:

cas_spin_lock.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class SpinLock {
private:
std::atomic<bool> flag = {false};
public:
void lock() {
bool expected = false;
while (!flag.compare_exchange_weak(expected, true, std::memory_order_acquire)) {
expected = false;
}
}
void unlock() {
flag.store(false, std::memory_order_release);
}
};

在这个示例中,compare_exchange_weak 被用来实现自旋锁,因为它在失败时可以快速重试,从而提高性能

内存屏障

内存屏障(Memory Barrier),也被称为内存栅栏(Memory Fence)或内存围栏(Memory Fence),是一种硬件或软件的同步机制,用于在并发系统中保持内存操作的顺序性。这是多核和多线程环境中至关重要的,因为现代处理器会对指令进行重排序以提高执行效率。

内存屏障的作用

  • 防止指令重排序:

    编译器和处理器可能会对指令进行重排序,以优化性能。内存屏障确保特定的内存操作在屏障之前完成,而不会被重排序到屏障之后。

  • 保证内存可见性:

    在多线程环境中,一个线程对内存的修改必须对其他线程可见。内存屏障确保在屏障之前的所有写操作对其他线程可见。

类型

  • 加载屏障(Load Barrier):

    确保在屏障之前的所有加载操作完成后,才开始执行屏障之后的加载操作。

  • 存储屏障(Store Barrier):

    确保在屏障之前的所有存储操作完成后,才开始执行屏障之后的存储操作。

  • 全屏障(Full Barrier):

    结合了加载屏障和存储屏障的功能,确保在屏障之前的所有加载和存储操作完成后,才开始执行屏障之后的加载和存储操作。

代码示例

以下是一个简单的代码示例,展示了如何使用内存屏障:

memory_barrier.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <atomic>

std::atomic<int> a{0};
std::atomic<int> b{0};

void thread1() {
a.store(1, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_seq_cst); // 全屏障
b.store(1, std::memory_order_relaxed);
}

void thread2() {
while (b.load(std::memory_order_relaxed) == 0);
std::atomic_thread_fence(std::memory_order_seq_cst); // 全屏障
assert(a.load(std::memory_order_relaxed) == 1);
}

在这个示例中,std::atomic_thread_fence 用于插入内存屏障,确保在屏障之前的存储操作完成后,才开始执行屏障之后的存储操作

内存序

内存序(Memory Order)描述了在多线程环境中,内存操作的顺序和可见性。它决定了一个线程对内存的修改何时以及如何对其他线程可见。C++11 引入了六种内存序,以便程序员在并发编程中根据需求选择合适的同步机制。

六种内存序

  • memory_order_relaxed:

    只保证当前操作的原子性,不考虑线程间的同步。适用于不需要同步的场景,如计数器的增加。

  • memory_order_consume:

    确保当前操作依赖的所有写操作在此操作之前完成。主要用于依赖关系较强的场景。

  • memory_order_acquire:

    确保在此操作之后的所有读写操作不会被重排序到此操作之前。常用于获取锁的操作。

  • memory_order_release:

    确保在此操作之前的所有读写操作不会被重排序到此操作之后。常用于释放锁的操作。

  • memory_order_acq_rel:

    结合了 acquire 和 release 的语义,确保在此操作之前的写操作不会被重排序到此操作之后,同时在此操作之后的读操作不会被重排序到此操作之前。适用于读-修改-写操作。

  • memory_order_seq_cst:

    顺序一致性,确保所有线程看到的内存操作顺序一致。这是最严格的内存序,适用于需要强一致性的场景。

代码示例

以下是一个简单的代码示例,展示了如何使用不同的内存序:

memory_order.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <atomic>
#include <thread>
#include <cassert>

std::atomic<int> data{0};
std::atomic<bool> ready{false};

void producer() {
data.store(42, std::memory_order_relaxed);
ready.store(true, std::memory_order_release);
}

void consumer() {
while (!ready.load(std::memory_order_acquire));
assert(data.load(std::memory_order_relaxed) == 42);
}

int main() {
std::thread t1(producer);
std::thread t2(consumer);
t1.join();
t2.join();
return 0;
}

在这个示例中,producer 线程使用 memory_order_release 来发布数据,而 consumer 线程使用 memory_order_acquire 来确保读取到的数据是最新的

TODO