1 // Written in the D programming language.
2 /**
3 Allocator that collects useful statistics about allocations, both global and per
4 calling point. The statistics collected can be configured statically by choosing
5 combinations of `Options` appropriately.
6 
7 Source: $(PHOBOSSRC std/experimental/allocator/building_blocks/stats_collector.d)
8 */
9 module std.experimental.allocator.building_blocks.stats_collector;
10 
11 ///
12 @safe unittest
13 {
14     import std.experimental.allocator.gc_allocator : GCAllocator;
15     import std.experimental.allocator.building_blocks.free_list : FreeList;
16     alias Allocator = StatsCollector!(GCAllocator, Options.bytesUsed);
17 }
18 
19 import std.experimental.allocator.common;
20 
21 /**
22 _Options for `StatsCollector` defined below. Each enables during
23 compilation one specific counter, statistic, or other piece of information.
24 */
25 enum Options : ulong
26 {
27     /**
28     Counts the number of calls to `owns`.
29     */
30     numOwns = 1u << 0,
31     /**
32     Counts the number of calls to `allocate`. All calls are counted,
33     including requests for zero bytes or failed requests.
34     */
35     numAllocate = 1u << 1,
36     /**
37     Counts the number of calls to `allocate` that succeeded, i.e. they
38     returned a block as large as requested. (N.B. requests for zero bytes count
39     as successful.)
40     */
41     numAllocateOK = 1u << 2,
42     /**
43     Counts the number of calls to `expand`, regardless of arguments or
44     result.
45     */
46     numExpand = 1u << 3,
47     /**
48     Counts the number of calls to `expand` that resulted in a successful
49     expansion.
50     */
51     numExpandOK = 1u << 4,
52     /**
53     Counts the number of calls to `reallocate`, regardless of arguments or
54     result.
55     */
56     numReallocate = 1u << 5,
57     /**
58     Counts the number of calls to `reallocate` that succeeded.
59     (Reallocations to zero bytes count as successful.)
60     */
61     numReallocateOK = 1u << 6,
62     /**
63     Counts the number of calls to `reallocate` that resulted in an in-place
64     reallocation (no memory moved). If this number is close to the total number
65     of reallocations, that indicates the allocator finds room at the current
66     block's end in a large fraction of the cases, but also that internal
67     fragmentation may be high (the size of the unit of allocation is large
68     compared to the typical allocation size of the application).
69     */
70     numReallocateInPlace = 1u << 7,
71     /**
72     Counts the number of calls to `deallocate`.
73     */
74     numDeallocate = 1u << 8,
75     /**
76     Counts the number of calls to `deallocateAll`.
77     */
78     numDeallocateAll = 1u << 9,
79     /**
80     Counts the number of calls to `alignedAllocate`. All calls are counted,
81     including requests for zero bytes or failed requests.
82     */
83     numAlignedAllocate = 1u << 10,
84     /**
85     Counts the number of calls to `alignedAllocate` that succeeded, i.e. they
86     returned a block as large as requested. (N.B. requests for zero bytes count
87     as successful.)
88     */
89     numAlignedAllocateOk = 1u << 11,
90     /**
91     Chooses all `numXxx` flags.
92     */
93     numAll = (1u << 12) - 1,
94     /**
95     Tracks bytes currently allocated by this allocator. This number goes up
96     and down as memory is allocated and deallocated, and is zero if the
97     allocator currently has no active allocation.
98     */
99     bytesUsed = 1u << 12,
100     /**
101     Tracks total cumulative bytes allocated by means of `allocate`,
102     `expand`, and `reallocate` (when resulting in an expansion). This
103     number always grows and indicates allocation traffic. To compute bytes
104     deallocated cumulatively, subtract `bytesUsed` from `bytesAllocated`.
105     */
106     bytesAllocated = 1u << 13,
107     /**
108     Tracks the sum of all `delta` values in calls of the form
109     $(D expand(b, delta)) that succeed (return `true`).
110     */
111     bytesExpanded = 1u << 14,
112     /**
113     Tracks the sum of all $(D b.length - s) with $(D b.length > s) in calls of
114     the form $(D realloc(b, s)) that succeed (return `true`). In per-call
115     statistics, also unambiguously counts the bytes deallocated with
116     `deallocate`.
117     */
118     bytesContracted = 1u << 15,
119     /**
120     Tracks the sum of all bytes moved as a result of calls to `realloc` that
121     were unable to reallocate in place. A large number (relative to $(D
122     bytesAllocated)) indicates that the application should use larger
123     preallocations.
124     */
125     bytesMoved = 1u << 16,
126     /**
127     Tracks the sum of all bytes NOT moved as result of calls to `realloc`
128     that managed to reallocate in place. A large number (relative to $(D
129     bytesAllocated)) indicates that the application is expansion-intensive and
130     is saving a good amount of moves. However, if this number is relatively
131     small and `bytesSlack` is high, it means the application is
132     overallocating for little benefit.
133     */
134     bytesNotMoved = 1u << 17,
135     /**
136     Measures the sum of extra bytes allocated beyond the bytes requested, i.e.
137     the $(HTTPS en.wikipedia.org/wiki/Fragmentation_(computing)#Internal_fragmentation, internal fragmentation). This is the current
138     effective number of slack bytes, and it goes up and down with time.
139     */
140     bytesSlack = 1u << 18,
141     /**
142     Measures the maximum bytes allocated over the time. This is useful for
143     dimensioning allocators.
144     */
145     bytesHighTide = 1u << 19,
146     /**
147     Chooses all `byteXxx` flags.
148     */
149     bytesAll = ((1u << 20) - 1) & ~numAll,
150     /**
151     Combines all flags above.
152     */
153     all = (1u << 20) - 1
154 }
155 
156 /**
157 
158 Allocator that collects extra data about allocations. Since each piece of
159 information adds size and time overhead, statistics can be individually enabled
160 or disabled through compile-time `flags`.
161 
162 All stats of the form `numXxx` record counts of events occurring, such as
163 calls to functions and specific results. The stats of the form `bytesXxx`
164 collect cumulative sizes.
165 
166 In addition, the data `callerSize`, `callerModule`, `callerFile`, $(D
167 callerLine), and `callerTime` is associated with each specific allocation.
168 This data prefixes each allocation.
169 
170 */
171 struct StatsCollector(Allocator, ulong flags = Options.all,
172     ulong perCallFlags = 0)
173 {
174 private:
175     import std.traits : hasMember, Signed;
176     import std.typecons : Ternary;
177 
178     static string define(string type, string[] names...)
179     {
180         string result;
181         foreach (v; names)
182             result ~= "static if (flags & Options."~v~") {"
183                 ~ "private "~type~" _"~v~";"
184                 ~ "public const("~type~") "~v~"() const { return _"~v~"; }"
185                 ~ "}";
186         return result;
187     }
188 
189     void add(string counter)(Signed!size_t n)
190     {
191         mixin("static if (flags & Options." ~ counter
192             ~ ") _" ~ counter ~ " += n;");
193         static if (counter == "bytesUsed" && (flags & Options.bytesHighTide))
194         {
195             if (bytesHighTide < bytesUsed ) _bytesHighTide = bytesUsed;
196         }
197     }
198 
199     void up(string counter)() { add!counter(1); }
200     void down(string counter)() { add!counter(-1); }
201 
202     version (StdDdoc)
203     {
204         /**
205         Read-only properties enabled by the homonym `flags` chosen by the
206         user.
207 
208         Example:
209         ----
210         StatsCollector!(Mallocator,
211             Options.bytesUsed | Options.bytesAllocated) a;
212         auto d1 = a.allocate(10);
213         auto d2 = a.allocate(11);
214         a.deallocate(d1);
215         assert(a.bytesAllocated == 21);
216         assert(a.bytesUsed == 11);
217         a.deallocate(d2);
218         assert(a.bytesAllocated == 21);
219         assert(a.bytesUsed == 0);
220         ----
221         */
222         @property ulong numOwns() const;
223         /// Ditto
224         @property ulong numAllocate() const;
225         /// Ditto
226         @property ulong numAllocateOK() const;
227         /// Ditto
228         @property ulong numExpand() const;
229         /// Ditto
230         @property ulong numExpandOK() const;
231         /// Ditto
232         @property ulong numReallocate() const;
233         /// Ditto
234         @property ulong numReallocateOK() const;
235         /// Ditto
236         @property ulong numReallocateInPlace() const;
237         /// Ditto
238         @property ulong numDeallocate() const;
239         /// Ditto
240         @property ulong numDeallocateAll() const;
241         /// Ditto
242         @property ulong numAlignedAllocate() const;
243         /// Ditto
244         @property ulong numAlignedAllocateOk() const;
245         /// Ditto
246         @property ulong bytesUsed() const;
247         /// Ditto
248         @property ulong bytesAllocated() const;
249         /// Ditto
250         @property ulong bytesExpanded() const;
251         /// Ditto
252         @property ulong bytesContracted() const;
253         /// Ditto
254         @property ulong bytesMoved() const;
255         /// Ditto
256         @property ulong bytesNotMoved() const;
257         /// Ditto
258         @property ulong bytesSlack() const;
259         /// Ditto
260         @property ulong bytesHighTide() const;
261     }
262 
263 public:
264     /**
265     The parent allocator is publicly accessible either as a direct member if it
266     holds state, or as an alias to `Allocator.instance` otherwise. One may use
267     it for making calls that won't count toward statistics collection.
268     */
269     static if (stateSize!Allocator) Allocator parent;
270     else alias parent = Allocator.instance;
271 
272 private:
273     // Per-allocator state
274     mixin(define("ulong",
275         "numOwns",
276         "numAllocate",
277         "numAllocateOK",
278         "numExpand",
279         "numExpandOK",
280         "numReallocate",
281         "numReallocateOK",
282         "numReallocateInPlace",
283         "numDeallocate",
284         "numDeallocateAll",
285         "numAlignedAllocate",
286         "numAlignedAllocateOk",
287         "bytesUsed",
288         "bytesAllocated",
289         "bytesExpanded",
290         "bytesContracted",
291         "bytesMoved",
292         "bytesNotMoved",
293         "bytesSlack",
294         "bytesHighTide",
295     ));
296 
297 public:
298 
299     /// Alignment offered is equal to `Allocator.alignment`.
300     alias alignment = Allocator.alignment;
301 
302     /**
303     Increments `numOwns` (per instance and and per call) and forwards to $(D
304     parent.owns(b)).
305     */
306     static if (hasMember!(Allocator, "owns"))
307     {
308         static if ((perCallFlags & Options.numOwns) == 0)
309         Ternary owns(void[] b)
310         { return ownsImpl(b); }
311         else
312         Ternary owns(string f = __FILE__, uint n = __LINE__)(void[] b)
313         { return ownsImpl!(f, n)(b); }
314     }
315 
316     private Ternary ownsImpl(string f = null, uint n = 0)(void[] b)
317     {
318         up!"numOwns";
319         addPerCall!(f, n, "numOwns")(1);
320         return parent.owns(b);
321     }
322 
323     /**
324     Forwards to `parent.allocate`. Affects per instance: `numAllocate`,
325     `bytesUsed`, `bytesAllocated`, `bytesSlack`, `numAllocateOK`,
326     and `bytesHighTide`. Affects per call: `numAllocate`, $(D
327     numAllocateOK), and `bytesAllocated`.
328     */
329     static if (!(perCallFlags
330         & (Options.numAllocate | Options.numAllocateOK
331             | Options.bytesAllocated)))
332     {
333         void[] allocate(size_t n)
334         { return allocateImpl(n); }
335     }
336     else
337     {
338         void[] allocate(string f = __FILE__, ulong n = __LINE__)
339             (size_t bytes)
340         { return allocateImpl!(f, n)(bytes); }
341     }
342 
343     // Common code currently shared between allocateImpl and allocateZeroedImpl.
344     private enum _updateStatsForAllocateResult =
345     q{
346         add!"bytesUsed"(result.length);
347         add!"bytesAllocated"(result.length);
348         immutable slack = this.goodAllocSize(result.length) - result.length;
349         add!"bytesSlack"(slack);
350         up!"numAllocate";
351         add!"numAllocateOK"(result.length == bytes); // allocating 0 bytes is OK
352         addPerCall!(f, n, "numAllocate", "numAllocateOK", "bytesAllocated")
353             (1, result.length == bytes, result.length);
354     };
355 
356     private void[] allocateImpl(string f = null, ulong n = 0)(size_t bytes)
357     {
358         auto result = parent.allocate(bytes);
359         mixin(_updateStatsForAllocateResult);
360         return result;
361     }
362 
363     static if (hasMember!(Allocator, "allocateZeroed"))
364     {
365         static if (!(perCallFlags
366             & (Options.numAllocate | Options.numAllocateOK
367                 | Options.bytesAllocated)))
368         {
369             package(std) void[] allocateZeroed()(size_t n)
370             { return allocateZeroedImpl(n); }
371         }
372         else
373         {
374             package(std) void[] allocateZeroed(string f = __FILE__, ulong n = __LINE__)
375                 (size_t bytes)
376             { return allocateZeroedImpl!(f, n)(bytes); }
377         }
378 
379         private void[] allocateZeroedImpl(string f = null, ulong n = 0)(size_t bytes)
380         {
381             auto result = parent.allocateZeroed(bytes);
382             // Note: calls to `allocateZeroed` are counted for statistical purposes
383             // as if they were calls to `allocate`. If/when `allocateZeroed` is made
384             // public it might be of interest to count such calls separately.
385             mixin(_updateStatsForAllocateResult);
386             return result;
387         }
388     }
389 
390     /**
391     Forwards to `parent.alignedAllocate`. Affects per instance: `numAlignedAllocate`,
392     `bytesUsed`, `bytesAllocated`, `bytesSlack`, `numAlignedAllocateOk`,
393     and `bytesHighTide`. Affects per call: `numAlignedAllocate`, `numAlignedAllocateOk`,
394     and `bytesAllocated`.
395     */
396     static if (!(perCallFlags
397         & (Options.numAlignedAllocate | Options.numAlignedAllocateOk
398             | Options.bytesAllocated)))
399     {
400         void[] alignedAllocate(size_t n, uint a)
401         { return alignedAllocateImpl(n, a); }
402     }
403     else
404     {
405         void[] alignedAllocate(string f = __FILE__, ulong n = __LINE__)
406             (size_t bytes, uint a)
407         { return alignedAllocateImpl!(f, n)(bytes, a); }
408     }
409 
410     private void[] alignedAllocateImpl(string f = null, ulong n = 0)(size_t bytes, uint a)
411     {
412         up!"numAlignedAllocate";
413         static if (!hasMember!(Allocator, "alignedAllocate"))
414         {
415             if (bytes == 0)
416                 up!"numAlignedAllocateOk";
417             void[] result = null;
418         }
419         else
420         {
421             auto result = parent.alignedAllocate(bytes, a);
422             add!"bytesUsed"(result.length);
423             add!"bytesAllocated"(result.length);
424             immutable slack = this.goodAllocSize(result.length) - result.length;
425             add!"bytesSlack"(slack);
426             add!"numAlignedAllocateOk"(result.length == bytes); // allocating 0 bytes is OK
427         }
428         addPerCall!(f, n, "numAlignedAllocate", "numAlignedAllocateOk", "bytesAllocated")
429             (1, result.length == bytes, result.length);
430 
431         return result;
432     }
433 
434     /**
435     Defined whether or not `Allocator.expand` is defined. Affects
436     per instance: `numExpand`, `numExpandOK`, `bytesExpanded`,
437     `bytesSlack`, `bytesAllocated`, and `bytesUsed`. Affects per call:
438     `numExpand`, `numExpandOK`, `bytesExpanded`, and
439     `bytesAllocated`.
440     */
441     static if (!(perCallFlags
442         & (Options.numExpand | Options.numExpandOK | Options.bytesExpanded)))
443     {
444         bool expand(ref void[] b, size_t delta)
445         { return expandImpl(b, delta); }
446     }
447     else
448     {
449         bool expand(string f = __FILE__, uint n = __LINE__)
450             (ref void[] b, size_t delta)
451         { return expandImpl!(f, n)(b, delta); }
452     }
453 
454     private bool expandImpl(string f = null, uint n = 0)(ref void[] b, size_t s)
455     {
456         up!"numExpand";
457         Signed!size_t slack = 0;
458         static if (!hasMember!(Allocator, "expand"))
459         {
460             auto result = s == 0;
461         }
462         else
463         {
464             immutable bytesSlackB4 = this.goodAllocSize(b.length) - b.length;
465             auto result = parent.expand(b, s);
466             if (result)
467             {
468                 up!"numExpandOK";
469                 add!"bytesUsed"(s);
470                 add!"bytesAllocated"(s);
471                 add!"bytesExpanded"(s);
472                 slack = Signed!size_t(this.goodAllocSize(b.length) - b.length
473                     - bytesSlackB4);
474                 add!"bytesSlack"(slack);
475             }
476         }
477         immutable xtra = result ? s : 0;
478         addPerCall!(f, n, "numExpand", "numExpandOK", "bytesExpanded",
479             "bytesAllocated")
480             (1, result, xtra, xtra);
481         return result;
482     }
483 
484     /**
485     Defined whether or not `Allocator.reallocate` is defined. Affects
486     per instance: `numReallocate`, `numReallocateOK`, $(D
487     numReallocateInPlace), `bytesNotMoved`, `bytesAllocated`, $(D
488     bytesSlack), `bytesExpanded`, and `bytesContracted`. Affects per call:
489     `numReallocate`, `numReallocateOK`, `numReallocateInPlace`,
490     `bytesNotMoved`, `bytesExpanded`, `bytesContracted`, and
491     `bytesMoved`.
492     */
493     static if (!(perCallFlags
494         & (Options.numReallocate | Options.numReallocateOK
495             | Options.numReallocateInPlace | Options.bytesNotMoved
496             | Options.bytesExpanded | Options.bytesContracted
497             | Options.bytesMoved)))
498     {
499         bool reallocate(ref void[] b, size_t s)
500         { return reallocateImpl(b, s); }
501     }
502     else
503     {
504         bool reallocate(string f = __FILE__, ulong n = __LINE__)
505             (ref void[] b, size_t s)
506         { return reallocateImpl!(f, n)(b, s); }
507     }
508 
509     private bool reallocateImpl(string f = null, uint n = 0)
510         (ref void[] b, size_t s)
511     {
512         up!"numReallocate";
513         const bytesSlackB4 = this.goodAllocSize(b.length) - b.length;
514         const oldB = b.ptr;
515         const oldLength = b.length;
516 
517         const result = parent.reallocate(b, s);
518 
519         Signed!size_t slack = 0;
520         bool wasInPlace = false;
521         Signed!size_t delta = 0;
522 
523         if (result)
524         {
525             up!"numReallocateOK";
526             slack = (this.goodAllocSize(b.length) - b.length) - bytesSlackB4;
527             add!"bytesSlack"(slack);
528             add!"bytesUsed"(Signed!size_t(b.length - oldLength));
529             if (oldB == b.ptr)
530             {
531                 // This was an in-place reallocation, yay
532                 wasInPlace = true;
533                 up!"numReallocateInPlace";
534                 add!"bytesNotMoved"(oldLength);
535                 delta = b.length - oldLength;
536                 if (delta >= 0)
537                 {
538                     // Expansion
539                     add!"bytesAllocated"(delta);
540                     add!"bytesExpanded"(delta);
541                 }
542                 else
543                 {
544                     // Contraction
545                     add!"bytesContracted"(-delta);
546                 }
547             }
548             else
549             {
550                 // This was a allocate-move-deallocate cycle
551                 add!"bytesAllocated"(b.length);
552                 add!"bytesMoved"(oldLength);
553             }
554         }
555         addPerCall!(f, n, "numReallocate", "numReallocateOK",
556             "numReallocateInPlace", "bytesNotMoved",
557             "bytesExpanded", "bytesContracted", "bytesMoved")
558             (1, result, wasInPlace, wasInPlace ? oldLength : 0,
559                 delta >= 0 ? delta : 0, delta < 0 ? -delta : 0,
560                 wasInPlace ? 0 : oldLength);
561         return result;
562     }
563 
564     /**
565     Defined whether or not `Allocator.deallocate` is defined. Affects
566     per instance: `numDeallocate`, `bytesUsed`, and `bytesSlack`.
567     Affects per call: `numDeallocate` and `bytesContracted`.
568     */
569     static if (!(perCallFlags &
570             (Options.numDeallocate | Options.bytesContracted)))
571         bool deallocate(void[] b)
572         { return deallocateImpl(b); }
573     else
574         bool deallocate(string f = __FILE__, uint n = __LINE__)(void[] b)
575         { return deallocateImpl!(f, n)(b); }
576 
577     private bool deallocateImpl(string f = null, uint n = 0)(void[] b)
578     {
579         up!"numDeallocate";
580         add!"bytesUsed"(-Signed!size_t(b.length));
581         add!"bytesSlack"(-(this.goodAllocSize(b.length) - b.length));
582         addPerCall!(f, n, "numDeallocate", "bytesContracted")(1, b.length);
583         static if (hasMember!(Allocator, "deallocate"))
584             return parent.deallocate(b);
585         else
586             return false;
587     }
588 
589     static if (hasMember!(Allocator, "deallocateAll"))
590     {
591         /**
592         Defined only if `Allocator.deallocateAll` is defined. Affects
593         per instance and per call `numDeallocateAll`.
594         */
595         static if (!(perCallFlags & Options.numDeallocateAll))
596             bool deallocateAll()
597             { return deallocateAllImpl(); }
598         else
599             bool deallocateAll(string f = __FILE__, uint n = __LINE__)()
600             { return deallocateAllImpl!(f, n)(); }
601 
602         private bool deallocateAllImpl(string f = null, uint n = 0)()
603         {
604             up!"numDeallocateAll";
605             addPerCall!(f, n, "numDeallocateAll")(1);
606             static if ((flags & Options.bytesUsed))
607                 _bytesUsed = 0;
608             return parent.deallocateAll();
609         }
610     }
611 
612     /**
613     Defined only if `Options.bytesUsed` is defined. Returns $(D bytesUsed ==
614     0).
615     */
616     static if (flags & Options.bytesUsed)
617     pure nothrow @safe @nogc
618     Ternary empty()
619     {
620         return Ternary(_bytesUsed == 0);
621     }
622 
623     /**
624     Reports per instance statistics to `output` (e.g. `stdout`). The
625     format is simple: one kind and value per line, separated by a colon, e.g.
626     `bytesAllocated:7395404`
627     */
628     void reportStatistics(R)(auto ref R output)
629     {
630         import std.conv : to;
631         import std.traits : EnumMembers;
632         foreach (e; EnumMembers!Options)
633         {
634             static if ((flags & e) && e != Options.numAll
635                     && e != Options.bytesAll && e != Options.all)
636                 output.write(e.to!string, ":", mixin(e.to!string), '\n');
637         }
638     }
639 
640     static if (perCallFlags)
641     {
642         /**
643         Defined if `perCallFlags` is nonzero.
644         */
645         struct PerCallStatistics
646         {
647             /// The file and line of the call.
648             string file;
649             /// Ditto
650             uint line;
651             /// The options corresponding to the statistics collected.
652             Options[] opts;
653             /// The values of the statistics. Has the same length as `opts`.
654             ulong[] values;
655             // Next in the chain.
656             private PerCallStatistics* next;
657 
658             /**
659             Format to a string such as:
660             $(D mymodule.d(655): [numAllocate:21, numAllocateOK:21, bytesAllocated:324202]).
661             */
662             string toString() const
663             {
664                 import std.conv : text, to;
665                 auto result = text(file, "(", line, "): [");
666                 foreach (i, opt; opts)
667                 {
668                     if (i) result ~= ", ";
669                     result ~= opt.to!string;
670                     result ~= ':';
671                     result ~= values[i].to!string;
672                 }
673                 return result ~= "]";
674             }
675         }
676         private static PerCallStatistics* root;
677 
678         /**
679         Defined if `perCallFlags` is nonzero. Iterates all monitored
680         file/line instances. The order of iteration is not meaningful (items
681         are inserted at the front of a list upon the first call), so
682         preprocessing the statistics after collection might be appropriate.
683         */
684         static auto byFileLine()
685         {
686             static struct Voldemort
687             {
688                 PerCallStatistics* current;
689                 bool empty() { return !current; }
690                 ref PerCallStatistics front() { return *current; }
691                 void popFront() { current = current.next; }
692                 auto save() { return this; }
693             }
694             return Voldemort(root);
695         }
696 
697         /**
698         Defined if `perCallFlags` is nonzero. Outputs (e.g. to a `File`)
699         a simple report of the collected per-call statistics.
700         */
701         static void reportPerCallStatistics(R)(auto ref R output)
702         {
703             output.write("Stats for: ", StatsCollector.stringof, '\n');
704             foreach (ref stat; byFileLine)
705             {
706                 output.write(stat, '\n');
707             }
708         }
709 
710         private PerCallStatistics* statsAt(string f, uint n, opts...)()
711         {
712             import std.array : array;
713             import std.range : repeat;
714 
715             static PerCallStatistics s = { f, n, [ opts ],
716                 repeat(0UL, opts.length).array };
717             static bool inserted;
718 
719             if (!inserted)
720             {
721                 // Insert as root
722                 s.next = root;
723                 root = &s;
724                 inserted = true;
725             }
726             return &s;
727         }
728 
729         private void addPerCall(string f, uint n, names...)(ulong[] values...)
730         {
731             import std.array : join;
732             enum ulong mask = mixin("Options."~[names].join("|Options."));
733             static if (perCallFlags & mask)
734             {
735                 // Per allocation info
736                 auto ps = mixin("statsAt!(f, n,"
737                     ~ "Options."~[names].join(", Options.")
738                 ~")");
739                 foreach (i; 0 .. names.length)
740                 {
741                     ps.values[i] += values[i];
742                 }
743             }
744         }
745     }
746     else
747     {
748         private void addPerCall(string f, uint n, names...)(ulong[]...)
749         {
750         }
751     }
752 }
753 
754 ///
755 @system unittest
756 {
757     import std.experimental.allocator.building_blocks.free_list : FreeList;
758     import std.experimental.allocator.gc_allocator : GCAllocator;
759     alias Allocator = StatsCollector!(GCAllocator, Options.all, Options.all);
760 
761     Allocator alloc;
762     auto b = alloc.allocate(10);
763     alloc.reallocate(b, 20);
764     alloc.deallocate(b);
765 
766     import std.file : deleteme, remove;
767     import std.range : walkLength;
768     import std.stdio : File;
769 
770     auto f = deleteme ~ "-dlang.std.experimental.allocator.stats_collector.txt";
771     scope(exit) remove(f);
772     Allocator.reportPerCallStatistics(File(f, "w"));
773     alloc.reportStatistics(File(f, "a"));
774     assert(File(f).byLine.walkLength == 24);
775 }
776 
777 @system unittest
778 {
779     void test(Allocator)()
780     {
781         import std.range : walkLength;
782         import std.typecons : Ternary;
783 
784         Allocator a;
785         assert((() pure nothrow @safe @nogc => a.empty)() == Ternary.yes);
786         auto b1 = a.allocate(100);
787         assert(a.numAllocate == 1);
788         assert((() nothrow @safe => a.expand(b1, 0))());
789         assert(a.reallocate(b1, b1.length + 1));
790         auto b2 = a.allocate(101);
791         assert(a.numAllocate == 2);
792         assert(a.bytesAllocated == 202);
793         assert(a.bytesUsed == 202);
794         auto b3 = a.allocate(202);
795         assert(a.numAllocate == 3);
796         assert(a.bytesAllocated == 404);
797         assert((() pure nothrow @safe @nogc => a.empty)() == Ternary.no);
798 
799         () nothrow @nogc { a.deallocate(b2); }();
800         assert(a.numDeallocate == 1);
801         () nothrow @nogc { a.deallocate(b1); }();
802         assert(a.numDeallocate == 2);
803         () nothrow @nogc { a.deallocate(b3); }();
804         assert(a.numDeallocate == 3);
805         assert(a.numAllocate == a.numDeallocate);
806         assert(a.bytesUsed == 0);
807      }
808 
809     import std.experimental.allocator.building_blocks.free_list : FreeList;
810     import std.experimental.allocator.gc_allocator : GCAllocator;
811     test!(StatsCollector!(GCAllocator, Options.all, Options.all));
812     test!(StatsCollector!(FreeList!(GCAllocator, 128), Options.all,
813         Options.all));
814 }
815 
816 @system unittest
817 {
818     void test(Allocator)()
819     {
820         import std.range : walkLength;
821         Allocator a;
822         auto b1 = a.allocate(100);
823         assert((() nothrow @safe => a.expand(b1, 0))());
824         assert(a.reallocate(b1, b1.length + 1));
825         auto b2 = a.allocate(101);
826         auto b3 = a.allocate(202);
827 
828         () nothrow @nogc { a.deallocate(b2); }();
829         () nothrow @nogc { a.deallocate(b1); }();
830         () nothrow @nogc { a.deallocate(b3); }();
831     }
832     import std.experimental.allocator.building_blocks.free_list : FreeList;
833     import std.experimental.allocator.gc_allocator : GCAllocator;
834     test!(StatsCollector!(GCAllocator, 0, 0));
835 }
836 
837 @system unittest
838 {
839     import std.experimental.allocator.gc_allocator : GCAllocator;
840     StatsCollector!(GCAllocator, 0, 0) a;
841 
842     // calls std.experimental.allocator.common.goodAllocSize
843     assert((() pure nothrow @safe @nogc => a.goodAllocSize(1))());
844 }
845 
846 @system unittest
847 {
848     import std.experimental.allocator.building_blocks.region : BorrowedRegion;
849 
850     auto a = StatsCollector!(BorrowedRegion!(), Options.all, Options.all)(BorrowedRegion!()(new ubyte[1024 * 64]));
851     auto b = a.allocate(42);
852     assert(b.length == 42);
853     // Test that reallocate infers from parent
854     assert((() nothrow @nogc => a.reallocate(b, 100))());
855     assert(b.length == 100);
856     // Test that deallocateAll infers from parent
857     assert((() nothrow @nogc => a.deallocateAll())());
858 }
859 
860 @system unittest
861 {
862     import std.experimental.allocator.building_blocks.region : BorrowedRegion;
863 
864     auto a = StatsCollector!(BorrowedRegion!(), Options.all)(BorrowedRegion!()(new ubyte[1024 * 64]));
865     auto b = a.alignedAllocate(42, 128);
866     assert(b.length == 42);
867     assert(b.ptr.alignedAt(128));
868     assert(a.numAlignedAllocate == 1);
869     assert(a.numAlignedAllocateOk == 1);
870     assert(a.bytesUsed == 42);
871 
872     b = a.alignedAllocate(23, 256);
873     assert(b.length == 23);
874     assert(b.ptr.alignedAt(256));
875     assert(a.numAlignedAllocate == 2);
876     assert(a.numAlignedAllocateOk == 2);
877     assert(a.bytesUsed == 65);
878 
879     b = a.alignedAllocate(0, 512);
880     assert(b.length == 0);
881     assert(a.numAlignedAllocate == 3);
882     assert(a.numAlignedAllocateOk == 3);
883     assert(a.bytesUsed == 65);
884 
885     b = a.alignedAllocate(1024 * 1024, 512);
886     assert(b is null);
887     assert(a.numAlignedAllocate == 4);
888     assert(a.numAlignedAllocateOk == 3);
889     assert(a.bytesUsed == 65);
890 }