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
|
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head><title>Memory</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"/><meta name="keywords" content=" ISO C++ , library "/><meta name="keywords" content=" ISO C++ , runtime , library "/><link rel="home" href="../index.html" title="The GNU C++ Library"/><link rel="up" href="utilities.html" title="Chapter 6. Utilities"/><link rel="prev" href="pairs.html" title="Pairs"/><link rel="next" href="traits.html" title="Traits"/></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Memory</th></tr><tr><td align="left"><a accesskey="p" href="pairs.html">Prev</a> </td><th width="60%" align="center">Chapter 6.
Utilities
</th><td align="right"> <a accesskey="n" href="traits.html">Next</a></td></tr></table><hr/></div><div class="section" title="Memory"><div class="titlepage"><div><div><h2 class="title"><a id="std.util.memory"/>Memory</h2></div></div></div><p>
Memory contains three general areas. First, function and operator
calls via <code class="function">new</code> and <code class="function">delete</code>
operator or member function calls. Second, allocation via
<code class="classname">allocator</code>. And finally, smart pointer and
intelligent pointer abstractions.
</p><div class="section" title="Allocators"><div class="titlepage"><div><div><h3 class="title"><a id="std.util.memory.allocator"/>Allocators</h3></div></div></div><p>
Memory management for Standard Library entities is encapsulated in a
class template called <code class="classname">allocator</code>. The
<code class="classname">allocator</code> abstraction is used throughout the
library in <code class="classname">string</code>, container classes,
algorithms, and parts of iostreams. This class, and base classes of
it, are the superset of available free store (<span class="quote">“<span class="quote">heap</span>”</span>)
management classes.
</p><div class="section" title="Requirements"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.req"/>Requirements</h4></div></div></div><p>
The C++ standard only gives a few directives in this area:
</p><div class="itemizedlist"><ul class="itemizedlist"><li class="listitem"><p>
When you add elements to a container, and the container must
allocate more memory to hold them, the container makes the
request via its <span class="type">Allocator</span> template
parameter, which is usually aliased to
<span class="type">allocator_type</span>. This includes adding chars
to the string class, which acts as a regular STL container in
this respect.
</p></li><li class="listitem"><p>
The default <span class="type">Allocator</span> argument of every
container-of-T is <code class="classname">allocator<T></code>.
</p></li><li class="listitem"><p>
The interface of the <code class="classname">allocator<T></code> class is
extremely simple. It has about 20 public declarations (nested
typedefs, member functions, etc), but the two which concern us most
are:
</p><pre class="programlisting">
T* allocate (size_type n, const void* hint = 0);
void deallocate (T* p, size_type n);
</pre><p>
The <code class="varname">n</code> arguments in both those
functions is a <span class="emphasis"><em>count</em></span> of the number of
<span class="type">T</span>'s to allocate space for, <span class="emphasis"><em>not their
total size</em></span>.
(This is a simplification; the real signatures use nested typedefs.)
</p></li><li class="listitem"><p>
The storage is obtained by calling <code class="function">::operator
new</code>, but it is unspecified when or how
often this function is called. The use of the
<code class="varname">hint</code> is unspecified, but intended as an
aid to locality if an implementation so
desires. <code class="constant">[20.4.1.1]/6</code>
</p></li></ul></div><p>
Complete details can be found in the C++ standard, look in
<code class="constant">[20.4 Memory]</code>.
</p></div><div class="section" title="Design Issues"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.design_issues"/>Design Issues</h4></div></div></div><p>
The easiest way of fulfilling the requirements is to call
<code class="function">operator new</code> each time a container needs
memory, and to call <code class="function">operator delete</code> each time
the container releases memory. This method may be <a class="link" href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00105.html">slower</a>
than caching the allocations and re-using previously-allocated
memory, but has the advantage of working correctly across a wide
variety of hardware and operating systems, including large
clusters. The <code class="classname">__gnu_cxx::new_allocator</code>
implements the simple operator new and operator delete semantics,
while <code class="classname">__gnu_cxx::malloc_allocator</code>
implements much the same thing, only with the C language functions
<code class="function">std::malloc</code> and <code class="function">free</code>.
</p><p>
Another approach is to use intelligence within the allocator
class to cache allocations. This extra machinery can take a variety
of forms: a bitmap index, an index into an exponentially increasing
power-of-two-sized buckets, or simpler fixed-size pooling cache.
The cache is shared among all the containers in the program: when
your program's <code class="classname">std::vector<int></code> gets
cut in half and frees a bunch of its storage, that memory can be
reused by the private
<code class="classname">std::list<WonkyWidget></code> brought in from
a KDE library that you linked against. And operators
<code class="function">new</code> and <code class="function">delete</code> are not
always called to pass the memory on, either, which is a speed
bonus. Examples of allocators that use these techniques are
<code class="classname">__gnu_cxx::bitmap_allocator</code>,
<code class="classname">__gnu_cxx::pool_allocator</code>, and
<code class="classname">__gnu_cxx::__mt_alloc</code>.
</p><p>
Depending on the implementation techniques used, the underlying
operating system, and compilation environment, scaling caching
allocators can be tricky. In particular, order-of-destruction and
order-of-creation for memory pools may be difficult to pin down
with certainty, which may create problems when used with plugins
or loading and unloading shared objects in memory. As such, using
caching allocators on systems that do not support
<code class="function">abi::__cxa_atexit</code> is not recommended.
</p></div><div class="section" title="Implementation"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.impl"/>Implementation</h4></div></div></div><div class="section" title="Interface Design"><div class="titlepage"><div><div><h5 class="title"><a id="id633362"/>Interface Design</h5></div></div></div><p>
The only allocator interface that
is supported is the standard C++ interface. As such, all STL
containers have been adjusted, and all external allocators have
been modified to support this change.
</p><p>
The class <code class="classname">allocator</code> just has typedef,
constructor, and rebind members. It inherits from one of the
high-speed extension allocators, covered below. Thus, all
allocation and deallocation depends on the base class.
</p><p>
The base class that <code class="classname">allocator</code> is derived from
may not be user-configurable.
</p></div><div class="section" title="Selecting Default Allocation Policy"><div class="titlepage"><div><div><h5 class="title"><a id="id633392"/>Selecting Default Allocation Policy</h5></div></div></div><p>
It's difficult to pick an allocation strategy that will provide
maximum utility, without excessively penalizing some behavior. In
fact, it's difficult just deciding which typical actions to measure
for speed.
</p><p>
Three synthetic benchmarks have been created that provide data
that is used to compare different C++ allocators. These tests are:
</p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>
Insertion.
</p><p>
Over multiple iterations, various STL container
objects have elements inserted to some maximum amount. A variety
of allocators are tested.
Test source for <a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert/sequence.cc?view=markup">sequence</a>
and <a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert/associative.cc?view=markup">associative</a>
containers.
</p></li><li class="listitem"><p>
Insertion and erasure in a multi-threaded environment.
</p><p>
This test shows the ability of the allocator to reclaim memory
on a per-thread basis, as well as measuring thread contention
for memory resources.
Test source
<a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert_erase/associative.cc?view=markup">here</a>.
</p></li><li class="listitem"><p>
A threaded producer/consumer model.
</p><p>
Test source for
<a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc++-v3/testsuite/performance/23_containers/producer_consumer/sequence.cc?view=markup">sequence</a>
and
<a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc++-v3/testsuite/performance/23_containers/producer_consumer/associative.cc?view=markup">associative</a>
containers.
</p></li></ol></div><p>
The current default choice for
<code class="classname">allocator</code> is
<code class="classname">__gnu_cxx::new_allocator</code>.
</p></div><div class="section" title="Disabling Memory Caching"><div class="titlepage"><div><div><h5 class="title"><a id="id633502"/>Disabling Memory Caching</h5></div></div></div><p>
In use, <code class="classname">allocator</code> may allocate and
deallocate using implementation-specified strategies and
heuristics. Because of this, every call to an allocator object's
<code class="function">allocate</code> member function may not actually
call the global operator new. This situation is also duplicated
for calls to the <code class="function">deallocate</code> member
function.
</p><p>
This can be confusing.
</p><p>
In particular, this can make debugging memory errors more
difficult, especially when using third party tools like valgrind or
debug versions of <code class="function">new</code>.
</p><p>
There are various ways to solve this problem. One would be to use
a custom allocator that just called operators
<code class="function">new</code> and <code class="function">delete</code>
directly, for every allocation. (See
<code class="filename">include/ext/new_allocator.h</code>, for instance.)
However, that option would involve changing source code to use
a non-default allocator. Another option is to force the
default allocator to remove caching and pools, and to directly
allocate with every call of <code class="function">allocate</code> and
directly deallocate with every call of
<code class="function">deallocate</code>, regardless of efficiency. As it
turns out, this last option is also available.
</p><p>
To globally disable memory caching within the library for the
default allocator, merely set
<code class="constant">GLIBCXX_FORCE_NEW</code> (with any value) in the
system's environment before running the program. If your program
crashes with <code class="constant">GLIBCXX_FORCE_NEW</code> in the
environment, it likely means that you linked against objects
built against the older library (objects which might still using the
cached allocations...).
</p></div></div><div class="section" title="Using a Specific Allocator"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.using"/>Using a Specific Allocator</h4></div></div></div><p>
You can specify different memory management schemes on a
per-container basis, by overriding the default
<span class="type">Allocator</span> template parameter. For example, an easy
(but non-portable) method of specifying that only <code class="function">malloc</code> or <code class="function">free</code>
should be used instead of the default node allocator is:
</p><pre class="programlisting">
std::list <int, __gnu_cxx::malloc_allocator<int> > malloc_list;</pre><p>
Likewise, a debugging form of whichever allocator is currently in use:
</p><pre class="programlisting">
std::deque <int, __gnu_cxx::debug_allocator<std::allocator<int> > > debug_deque;
</pre></div><div class="section" title="Custom Allocators"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.custom"/>Custom Allocators</h4></div></div></div><p>
Writing a portable C++ allocator would dictate that the interface
would look much like the one specified for
<code class="classname">allocator</code>. Additional member functions, but
not subtractions, would be permissible.
</p><p>
Probably the best place to start would be to copy one of the
extension allocators: say a simple one like
<code class="classname">new_allocator</code>.
</p></div><div class="section" title="Extension Allocators"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.ext"/>Extension Allocators</h4></div></div></div><p>
Several other allocators are provided as part of this
implementation. The location of the extension allocators and their
names have changed, but in all cases, functionality is
equivalent. Starting with gcc-3.4, all extension allocators are
standard style. Before this point, SGI style was the norm. Because of
this, the number of template arguments also changed. Here's a simple
chart to track the changes.
</p><p>
More details on each of these extension allocators follows.
</p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>
<code class="classname">new_allocator</code>
</p><p>
Simply wraps <code class="function">::operator new</code>
and <code class="function">::operator delete</code>.
</p></li><li class="listitem"><p>
<code class="classname">malloc_allocator</code>
</p><p>
Simply wraps <code class="function">malloc</code> and
<code class="function">free</code>. There is also a hook for an
out-of-memory handler (for
<code class="function">new</code>/<code class="function">delete</code> this is
taken care of elsewhere).
</p></li><li class="listitem"><p>
<code class="classname">array_allocator</code>
</p><p>
Allows allocations of known and fixed sizes using existing
global or external storage allocated via construction of
<code class="classname">std::tr1::array</code> objects. By using this
allocator, fixed size containers (including
<code class="classname">std::string</code>) can be used without
instances calling <code class="function">::operator new</code> and
<code class="function">::operator delete</code>. This capability
allows the use of STL abstractions without runtime
complications or overhead, even in situations such as program
startup. For usage examples, please consult the testsuite.
</p></li><li class="listitem"><p>
<code class="classname">debug_allocator</code>
</p><p>
A wrapper around an arbitrary allocator A. It passes on
slightly increased size requests to A, and uses the extra
memory to store size information. When a pointer is passed
to <code class="function">deallocate()</code>, the stored size is
checked, and <code class="function">assert()</code> is used to
guarantee they match.
</p></li><li class="listitem"><p>
<code class="classname">throw_allocator</code>
</p><p>
Includes memory tracking and marking abilities as well as hooks for
throwing exceptions at configurable intervals (including random,
all, none).
</p></li><li class="listitem"><p>
<code class="classname">__pool_alloc</code>
</p><p>
A high-performance, single pool allocator. The reusable
memory is shared among identical instantiations of this type.
It calls through <code class="function">::operator new</code> to
obtain new memory when its lists run out. If a client
container requests a block larger than a certain threshold
size, then the pool is bypassed, and the allocate/deallocate
request is passed to <code class="function">::operator new</code>
directly.
</p><p>
Older versions of this class take a boolean template
parameter, called <code class="varname">thr</code>, and an integer template
parameter, called <code class="varname">inst</code>.
</p><p>
The <code class="varname">inst</code> number is used to track additional memory
pools. The point of the number is to allow multiple
instantiations of the classes without changing the semantics at
all. All three of
</p><pre class="programlisting">
typedef __pool_alloc<true,0> normal;
typedef __pool_alloc<true,1> private;
typedef __pool_alloc<true,42> also_private;
</pre><p>
behave exactly the same way. However, the memory pool for each type
(and remember that different instantiations result in different types)
remains separate.
</p><p>
The library uses <span class="emphasis"><em>0</em></span> in all its instantiations. If you
wish to keep separate free lists for a particular purpose, use a
different number.
</p><p>The <code class="varname">thr</code> boolean determines whether the
pool should be manipulated atomically or not. When
<code class="varname">thr</code> = <code class="constant">true</code>, the allocator
is thread-safe, while <code class="varname">thr</code> =
<code class="constant">false</code>, is slightly faster but unsafe for
multiple threads.
</p><p>
For thread-enabled configurations, the pool is locked with a
single big lock. In some situations, this implementation detail
may result in severe performance degradation.
</p><p>
(Note that the GCC thread abstraction layer allows us to provide
safe zero-overhead stubs for the threading routines, if threads
were disabled at configuration time.)
</p></li><li class="listitem"><p>
<code class="classname">__mt_alloc</code>
</p><p>
A high-performance fixed-size allocator with
exponentially-increasing allocations. It has its own
documentation, found <a class="link" href="mt_allocator.html" title="Chapter 20. The mt_allocator">here</a>.
</p></li><li class="listitem"><p>
<code class="classname">bitmap_allocator</code>
</p><p>
A high-performance allocator that uses a bit-map to keep track
of the used and unused memory locations. It has its own
documentation, found <a class="link" href="bitmap_allocator.html" title="Chapter 21. The bitmap_allocator">here</a>.
</p></li></ol></div></div><div class="bibliography" title="Bibliography"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.biblio"/>Bibliography</h4></div></div></div><div class="biblioentry"><a id="id633953"/><p><span class="citetitle"><em class="citetitle">
ISO/IEC 14882:1998 Programming languages - C++
</em>. </span>
isoc++_1998
<span class="pagenums">20.4 Memory. </span></p></div><div class="biblioentry" title="The Standard Librarian: What Are Allocators Good For?"><a id="id633968"/><p><span class="title"><em>
<a class="link" href="http://www.drdobbs.com/cpp/184403759">
The Standard Librarian: What Are Allocators Good For?
</a>
</em>. </span><span class="author"><span class="firstname">Matt</span> <span class="surname">Austern</span>. </span><span class="publisher"><span class="publishername">
C/C++ Users Journal
. </span></span></p></div><div class="biblioentry" title="The Hoard Memory Allocator"><a id="id633999"/><p><span class="title"><em>
<a class="link" href="http://www.cs.umass.edu/~emery/hoard">
The Hoard Memory Allocator
</a>
</em>. </span><span class="author"><span class="firstname">Emery</span> <span class="surname">Berger</span>. </span></p></div><div class="biblioentry" title="Reconsidering Custom Memory Allocation"><a id="id634022"/><p><span class="title"><em>
<a class="link" href="http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf">
Reconsidering Custom Memory Allocation
</a>
</em>. </span><span class="author"><span class="firstname">Emery</span> <span class="surname">Berger</span>. </span><span class="author"><span class="firstname">Ben</span> <span class="surname">Zorn</span>. </span><span class="author"><span class="firstname">Kathryn</span> <span class="surname">McKinley</span>. </span><span class="copyright">Copyright © 2002 OOPSLA. </span></p></div><div class="biblioentry" title="Allocator Types"><a id="id634074"/><p><span class="title"><em>
<a class="link" href="http://www.angelikalanger.com/Articles/C++Report/Allocators/Allocators.html">
Allocator Types
</a>
</em>. </span><span class="author"><span class="firstname">Klaus</span> <span class="surname">Kreft</span>. </span><span class="author"><span class="firstname">Angelika</span> <span class="surname">Langer</span>. </span><span class="publisher"><span class="publishername">
C/C++ Users Journal
. </span></span></p></div><div class="biblioentry"><a id="id634113"/><p><span class="citetitle"><em class="citetitle">The C++ Programming Language</em>. </span><span class="author"><span class="firstname">Bjarne</span> <span class="surname">Stroustrup</span>. </span><span class="copyright">Copyright © 2000 . </span><span class="pagenums">19.4 Allocators. </span><span class="publisher"><span class="publishername">
Addison Wesley
. </span></span></p></div><div class="biblioentry"><a id="id634150"/><p><span class="citetitle"><em class="citetitle">Yalloc: A Recycling C++ Allocator</em>. </span><span class="author"><span class="firstname">Felix</span> <span class="surname">Yen</span>. </span></p></div></div></div><div class="section" title="auto_ptr"><div class="titlepage"><div><div><h3 class="title"><a id="std.util.memory.auto_ptr"/>auto_ptr</h3></div></div></div><div class="section" title="Limitations"><div class="titlepage"><div><div><h4 class="title"><a id="auto_ptr.limitations"/>Limitations</h4></div></div></div><p>Explaining all of the fun and delicious things that can
happen with misuse of the <code class="classname">auto_ptr</code> class
template (called <acronym class="acronym">AP</acronym> here) would take some
time. Suffice it to say that the use of <acronym class="acronym">AP</acronym>
safely in the presence of copying has some subtleties.
</p><p>
The AP class is a really
nifty idea for a smart pointer, but it is one of the dumbest of
all the smart pointers -- and that's fine.
</p><p>
AP is not meant to be a supersmart solution to all resource
leaks everywhere. Neither is it meant to be an effective form
of garbage collection (although it can help, a little bit).
And it can <span class="emphasis"><em>not</em></span>be used for arrays!
</p><p>
<acronym class="acronym">AP</acronym> is meant to prevent nasty leaks in the
presence of exceptions. That's <span class="emphasis"><em>all</em></span>. This
code is AP-friendly:
</p><pre class="programlisting">
// Not a recommend naming scheme, but good for web-based FAQs.
typedef std::auto_ptr<MyClass> APMC;
extern function_taking_MyClass_pointer (MyClass*);
extern some_throwable_function ();
void func (int data)
{
APMC ap (new MyClass(data));
some_throwable_function(); // this will throw an exception
function_taking_MyClass_pointer (ap.get());
}
</pre><p>When an exception gets thrown, the instance of MyClass that's
been created on the heap will be <code class="function">delete</code>'d as the stack is
unwound past <code class="function">func()</code>.
</p><p>Changing that code as follows is not <acronym class="acronym">AP</acronym>-friendly:
</p><pre class="programlisting">
APMC ap (new MyClass[22]);
</pre><p>You will get the same problems as you would without the use
of <acronym class="acronym">AP</acronym>:
</p><pre class="programlisting">
char* array = new char[10]; // array new...
...
delete array; // ...but single-object delete
</pre><p>
AP cannot tell whether the pointer you've passed at creation points
to one or many things. If it points to many things, you are about
to die. AP is trivial to write, however, so you could write your
own <code class="code">auto_array_ptr</code> for that situation (in fact, this has
been done many times; check the mailing lists, Usenet, Boost, etc).
</p></div><div class="section" title="Use in Containers"><div class="titlepage"><div><div><h4 class="title"><a id="auto_ptr.using"/>Use in Containers</h4></div></div></div><p>
</p><p>All of the <a class="link" href="containers.html" title="Chapter 9. Containers">containers</a>
described in the standard library require their contained types
to have, among other things, a copy constructor like this:
</p><pre class="programlisting">
struct My_Type
{
My_Type (My_Type const&);
};
</pre><p>
Note the const keyword; the object being copied shouldn't change.
The template class <code class="code">auto_ptr</code> (called AP here) does not
meet this requirement. Creating a new AP by copying an existing
one transfers ownership of the pointed-to object, which means that
the AP being copied must change, which in turn means that the
copy ctors of AP do not take const objects.
</p><p>
The resulting rule is simple: <span class="emphasis"><em>Never ever use a
container of auto_ptr objects</em></span>. The standard says that
<span class="quote">“<span class="quote">undefined</span>”</span> behavior is the result, but it is
guaranteed to be messy.
</p><p>
To prevent you from doing this to yourself, the
<a class="link" href="ext_compile_checks.html" title="Chapter 16. Compile Time Checks">concept checks</a> built
in to this implementation will issue an error if you try to
compile code like this:
</p><pre class="programlisting">
#include <vector>
#include <memory>
void f()
{
std::vector< std::auto_ptr<int> > vec_ap_int;
}
</pre><p>
Should you try this with the checks enabled, you will see an error.
</p></div></div><div class="section" title="shared_ptr"><div class="titlepage"><div><div><h3 class="title"><a id="std.util.memory.shared_ptr"/>shared_ptr</h3></div></div></div><p>
The shared_ptr class template stores a pointer, usually obtained via new,
and implements shared ownership semantics.
</p><div class="section" title="Requirements"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.req"/>Requirements</h4></div></div></div><p>
</p><p>
The standard deliberately doesn't require a reference-counted
implementation, allowing other techniques such as a
circular-linked-list.
</p><p>
At the time of writing the C++0x working paper doesn't mention how
threads affect shared_ptr, but it is likely to follow the existing
practice set by <code class="classname">boost::shared_ptr</code>. The
shared_ptr in libstdc++ is derived from Boost's, so the same rules
apply.
</p><p>
</p></div><div class="section" title="Design Issues"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.design_issues"/>Design Issues</h4></div></div></div><p>
The <code class="classname">shared_ptr</code> code is kindly donated to GCC by the Boost
project and the original authors of the code. The basic design and
algorithms are from Boost, the notes below describe details specific to
the GCC implementation. Names have been uglified in this implementation,
but the design should be recognisable to anyone familiar with the Boost
1.32 shared_ptr.
</p><p>
The basic design is an abstract base class, <code class="code">_Sp_counted_base</code> that
does the reference-counting and calls virtual functions when the count
drops to zero.
Derived classes override those functions to destroy resources in a context
where the correct dynamic type is known. This is an application of the
technique known as type erasure.
</p></div><div class="section" title="Implementation"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.impl"/>Implementation</h4></div></div></div><div class="section" title="Class Hierarchy"><div class="titlepage"><div><div><h5 class="title"><a id="id634511"/>Class Hierarchy</h5></div></div></div><p>
A <code class="classname">shared_ptr<T></code> contains a pointer of
type <span class="type">T*</span> and an object of type
<code class="classname">__shared_count</code>. The shared_count contains a
pointer of type <span class="type">_Sp_counted_base*</span> which points to the
object that maintains the reference-counts and destroys the managed
resource.
</p><div class="variablelist"><dl><dt><span class="term"><code class="classname">_Sp_counted_base<Lp></code></span></dt><dd><p>
The base of the hierarchy is parameterized on the lock policy (see below.)
_Sp_counted_base doesn't depend on the type of pointer being managed,
it only maintains the reference counts and calls virtual functions when
the counts drop to zero. The managed object is destroyed when the last
strong reference is dropped, but the _Sp_counted_base itself must exist
until the last weak reference is dropped.
</p></dd><dt><span class="term"><code class="classname">_Sp_counted_base_impl<Ptr, Deleter, Lp></code></span></dt><dd><p>
Inherits from _Sp_counted_base and stores a pointer of type <span class="type">Ptr</span>
and a deleter of type <code class="code">Deleter</code>. <code class="code">_Sp_deleter</code> is
used when the user doesn't supply a custom deleter. Unlike Boost's, this
default deleter is not "checked" because GCC already issues a warning if
<code class="function">delete</code> is used with an incomplete type.
This is the only derived type used by <code class="classname">shared_ptr<Ptr></code>
and it is never used by <code class="classname">shared_ptr</code>, which uses one of
the following types, depending on how the shared_ptr is constructed.
</p></dd><dt><span class="term"><code class="classname">_Sp_counted_ptr<Ptr, Lp></code></span></dt><dd><p>
Inherits from _Sp_counted_base and stores a pointer of type <span class="type">Ptr</span>,
which is passed to <code class="function">delete</code> when the last reference is dropped.
This is the simplest form and is used when there is no custom deleter or
allocator.
</p></dd><dt><span class="term"><code class="classname">_Sp_counted_deleter<Ptr, Deleter, Alloc></code></span></dt><dd><p>
Inherits from _Sp_counted_ptr and adds support for custom deleter and
allocator. Empty Base Optimization is used for the allocator. This class
is used even when the user only provides a custom deleter, in which case
<code class="classname">allocator</code> is used as the allocator.
</p></dd><dt><span class="term"><code class="classname">_Sp_counted_ptr_inplace<Tp, Alloc, Lp></code></span></dt><dd><p>
Used by <code class="code">allocate_shared</code> and <code class="code">make_shared</code>.
Contains aligned storage to hold an object of type <span class="type">Tp</span>,
which is constructed in-place with placement <code class="function">new</code>.
Has a variadic template constructor allowing any number of arguments to
be forwarded to <span class="type">Tp</span>'s constructor.
Unlike the other <code class="classname">_Sp_counted_*</code> classes, this one is parameterized on the
type of object, not the type of pointer; this is purely a convenience
that simplifies the implementation slightly.
</p></dd></dl></div></div><div class="section" title="Thread Safety"><div class="titlepage"><div><div><h5 class="title"><a id="id634689"/>Thread Safety</h5></div></div></div><p>
C++0x-only features are: rvalue-ref/move support, allocator support,
aliasing constructor, make_shared & allocate_shared. Additionally,
the constructors taking <code class="classname">auto_ptr</code> parameters are
deprecated in C++0x mode.
</p><p>
The
<a class="link" href="http://boost.org/libs/smart_ptr/shared_ptr.htm#ThreadSafety">Thread
Safety</a> section of the Boost shared_ptr documentation says "shared_ptr
objects offer the same level of thread safety as built-in types."
The implementation must ensure that concurrent updates to separate shared_ptr
instances are correct even when those instances share a reference count e.g.
</p><pre class="programlisting">
shared_ptr<A> a(new A);
shared_ptr<A> b(a);
// Thread 1 // Thread 2
a.reset(); b.reset();
</pre><p>
The dynamically-allocated object must be destroyed by exactly one of the
threads. Weak references make things even more interesting.
The shared state used to implement shared_ptr must be transparent to the
user and invariants must be preserved at all times.
The key pieces of shared state are the strong and weak reference counts.
Updates to these need to be atomic and visible to all threads to ensure
correct cleanup of the managed resource (which is, after all, shared_ptr's
job!)
On multi-processor systems memory synchronisation may be needed so that
reference-count updates and the destruction of the managed resource are
race-free.
</p><p>
The function <code class="function">_Sp_counted_base::_M_add_ref_lock()</code>, called when
obtaining a shared_ptr from a weak_ptr, has to test if the managed
resource still exists and either increment the reference count or throw
<code class="classname">bad_weak_ptr</code>.
In a multi-threaded program there is a potential race condition if the last
reference is dropped (and the managed resource destroyed) between testing
the reference count and incrementing it, which could result in a shared_ptr
pointing to invalid memory.
</p><p>
The Boost shared_ptr (as used in GCC) features a clever lock-free
algorithm to avoid the race condition, but this relies on the
processor supporting an atomic <span class="emphasis"><em>Compare-And-Swap</em></span>
instruction. For other platforms there are fall-backs using mutex
locks. Boost (as of version 1.35) includes several different
implementations and the preprocessor selects one based on the
compiler, standard library, platform etc. For the version of
shared_ptr in libstdc++ the compiler and library are fixed, which
makes things much simpler: we have an atomic CAS or we don't, see Lock
Policy below for details.
</p></div><div class="section" title="Selecting Lock Policy"><div class="titlepage"><div><div><h5 class="title"><a id="id634759"/>Selecting Lock Policy</h5></div></div></div><p>
</p><p>
There is a single <code class="classname">_Sp_counted_base</code> class,
which is a template parameterized on the enum
<span class="type">__gnu_cxx::_Lock_policy</span>. The entire family of classes is
parameterized on the lock policy, right up to
<code class="classname">__shared_ptr</code>, <code class="classname">__weak_ptr</code> and
<code class="classname">__enable_shared_from_this</code>. The actual
<code class="classname">std::shared_ptr</code> class inherits from
<code class="classname">__shared_ptr</code> with the lock policy parameter
selected automatically based on the thread model and platform that
libstdc++ is configured for, so that the best available template
specialization will be used. This design is necessary because it would
not be conforming for <code class="classname">shared_ptr</code> to have an
extra template parameter, even if it had a default value. The
available policies are:
</p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>
<span class="type">_S_Atomic</span>
</p><p>
Selected when GCC supports a builtin atomic compare-and-swap operation
on the target processor (see <a class="link" href="http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html">Atomic
Builtins</a>.) The reference counts are maintained using a lock-free
algorithm and GCC's atomic builtins, which provide the required memory
synchronisation.
</p></li><li class="listitem"><p>
<span class="type">_S_Mutex</span>
</p><p>
The _Sp_counted_base specialization for this policy contains a mutex,
which is locked in add_ref_lock(). This policy is used when GCC's atomic
builtins aren't available so explicit memory barriers are needed in places.
</p></li><li class="listitem"><p>
<span class="type">_S_Single</span>
</p><p>
This policy uses a non-reentrant add_ref_lock() with no locking. It is
used when libstdc++ is built without <code class="literal">--enable-threads</code>.
</p></li></ol></div><p>
For all three policies, reference count increments and
decrements are done via the functions in
<code class="filename">ext/atomicity.h</code>, which detect if the program
is multi-threaded. If only one thread of execution exists in
the program then less expensive non-atomic operations are used.
</p></div><div class="section" title="Dual C++0x and TR1 Implementation"><div class="titlepage"><div><div><h5 class="title"><a id="id634881"/>Dual C++0x and TR1 Implementation</h5></div></div></div><p>
The interface of <code class="classname">tr1::shared_ptr</code> was extended for C++0x
with support for rvalue-references and the other features from N2351.
The <code class="classname">_Sp_counted_base</code> base class is implemented in
<code class="filename">tr1/boost_sp_shared_count.h</code> and is common to the TR1
and C++0x versions of <code class="classname">shared_ptr</code>.
</p><p>
The classes derived from <code class="classname">_Sp_counted_base</code> (see Class Hierarchy
above) and <code class="classname">__shared_count</code> are implemented separately for C++0x
and TR1, in <code class="filename">bits/shared_ptr.h</code> and
<code class="filename">tr1/shared_ptr.h</code> respectively.
</p><p>
The TR1 implementation is considered relatively stable, so is unlikely to
change unless bug fixes require it. If the code that is common to both
C++0x and TR1 modes needs to diverge further then it might be necessary to
duplicate <code class="classname">_Sp_counted_base</code> and only make changes to
the C++0x version.
</p></div><div class="section" title="Related functions and classes"><div class="titlepage"><div><div><h5 class="title"><a id="id634937"/>Related functions and classes</h5></div></div></div><div class="variablelist"><dl><dt><span class="term"><code class="code">dynamic_pointer_cast</code>, <code class="code">static_pointer_cast</code>,
<code class="code">const_pointer_cast</code></span></dt><dd><p>
As noted in N2351, these functions can be implemented non-intrusively using
the alias constructor. However the aliasing constructor is only available
in C++0x mode, so in TR1 mode these casts rely on three non-standard
constructors in shared_ptr and __shared_ptr.
In C++0x mode these constructors and the related tag types are not needed.
</p></dd><dt><span class="term"><code class="code">enable_shared_from_this</code></span></dt><dd><p>
The clever overload to detect a base class of type
<code class="code">enable_shared_from_this</code> comes straight from Boost.
There is an extra overload for <code class="code">__enable_shared_from_this</code> to
work smoothly with <code class="code">__shared_ptr<Tp, Lp></code> using any lock
policy.
</p></dd><dt><span class="term"><code class="code">make_shared</code>, <code class="code">allocate_shared</code></span></dt><dd><p>
<code class="code">make_shared</code> simply forwards to <code class="code">allocate_shared</code>
with <code class="code">std::allocator</code> as the allocator.
Although these functions can be implemented non-intrusively using the
alias constructor, if they have access to the implementation then it is
possible to save storage and reduce the number of heap allocations. The
newly constructed object and the _Sp_counted_* can be allocated in a single
block and the standard says implementations are "encouraged, but not required,"
to do so. This implementation provides additional non-standard constructors
(selected with the type <code class="code">_Sp_make_shared_tag</code>) which create an
object of type <code class="code">_Sp_counted_ptr_inplace</code> to hold the new object.
The returned <code class="code">shared_ptr<A></code> needs to know the address of the
new <code class="code">A</code> object embedded in the <code class="code">_Sp_counted_ptr_inplace</code>,
but it has no way to access it.
This implementation uses a "covert channel" to return the address of the
embedded object when <code class="code">get_deleter<_Sp_make_shared_tag>()</code>
is called. Users should not try to use this.
As well as the extra constructors, this implementation also needs some
members of _Sp_counted_deleter to be protected where they could otherwise
be private.
</p></dd></dl></div></div></div><div class="section" title="Use"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.using"/>Use</h4></div></div></div><div class="section" title="Examples"><div class="titlepage"><div><div><h5 class="title"><a id="id635086"/>Examples</h5></div></div></div><p>
Examples of use can be found in the testsuite, under
<code class="filename">testsuite/tr1/2_general_utilities/shared_ptr</code>,
<code class="filename">testsuite/20_util/shared_ptr</code>
and
<code class="filename">testsuite/20_util/weak_ptr</code>.
</p></div><div class="section" title="Unresolved Issues"><div class="titlepage"><div><div><h5 class="title"><a id="id635116"/>Unresolved Issues</h5></div></div></div><p>
The <span class="emphasis"><em><code class="classname">shared_ptr</code> atomic access</em></span>
clause in the C++0x working draft is not implemented in GCC.
</p><p>
The <span class="type">_S_single</span> policy uses atomics when used in MT
code, because it uses the same dispatcher functions that check
<code class="function">__gthread_active_p()</code>. This could be
addressed by providing template specialisations for some members
of <code class="classname">_Sp_counted_base<_S_single></code>.
</p><p>
Unlike Boost, this implementation does not use separate classes
for the pointer+deleter and pointer+deleter+allocator cases in
C++0x mode, combining both into _Sp_counted_deleter and using
<code class="classname">allocator</code> when the user doesn't specify
an allocator. If it was found to be beneficial an additional
class could easily be added. With the current implementation,
the _Sp_counted_deleter and __shared_count constructors taking a
custom deleter but no allocator are technically redundant and
could be removed, changing callers to always specify an
allocator. If a separate pointer+deleter class was added the
__shared_count constructor would be needed, so it has been kept
for now.
</p><p>
The hack used to get the address of the managed object from
<code class="function">_Sp_counted_ptr_inplace::_M_get_deleter()</code>
is accessible to users. This could be prevented if
<code class="function">get_deleter<_Sp_make_shared_tag>()</code>
always returned NULL, since the hack only needs to work at a
lower level, not in the public API. This wouldn't be difficult,
but hasn't been done since there is no danger of accidental
misuse: users already know they are relying on unsupported
features if they refer to implementation details such as
_Sp_make_shared_tag.
</p><p>
tr1::_Sp_deleter could be a private member of tr1::__shared_count but it
would alter the ABI.
</p></div></div><div class="section" title="Acknowledgments"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.ack"/>Acknowledgments</h4></div></div></div><p>
The original authors of the Boost shared_ptr, which is really nice
code to work with, Peter Dimov in particular for his help and
invaluable advice on thread safety. Phillip Jordan and Paolo
Carlini for the lock policy implementation.
</p></div><div class="bibliography" title="Bibliography"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.biblio"/>Bibliography</h4></div></div></div><div class="biblioentry" title="Improving shared_ptr for C++0x, Revision 2"><a id="id635209"/><p><span class="title"><em>
<a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2351.htm">
Improving shared_ptr for C++0x, Revision 2
</a>
</em>. </span><span class="subtitle">
N2351
. </span></p></div><div class="biblioentry" title="C++ Standard Library Active Issues List"><a id="id635228"/><p><span class="title"><em>
<a class="link" href="http://open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2456.html">
C++ Standard Library Active Issues List
</a>
</em>. </span><span class="subtitle">
N2456
. </span></p></div><div class="biblioentry" title="Working Draft, Standard for Programming Language C++"><a id="id635248"/><p><span class="title"><em>
<a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2461.pdf">
Working Draft, Standard for Programming Language C++
</a>
</em>. </span><span class="subtitle">
N2461
. </span></p></div><div class="biblioentry" title="Boost C++ Libraries documentation, shared_ptr"><a id="id635267"/><p><span class="title"><em>
<a class="link" href="http://boost.org/libs/smart_ptr/shared_ptr.htm">
Boost C++ Libraries documentation, shared_ptr
</a>
</em>. </span><span class="subtitle">
N2461
. </span></p></div></div></div></div><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td align="left"><a accesskey="p" href="pairs.html">Prev</a> </td><td align="center"><a accesskey="u" href="utilities.html">Up</a></td><td align="right"> <a accesskey="n" href="traits.html">Next</a></td></tr><tr><td align="left" valign="top">Pairs </td><td align="center"><a accesskey="h" href="../index.html">Home</a></td><td align="right" valign="top"> Traits</td></tr></table></div></body></html>
|
