-
-
Notifications
You must be signed in to change notification settings - Fork 701
/
free_list.d
1296 lines (1151 loc) · 39.3 KB
/
free_list.d
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
// Written in the D programming language.
/**
Source: $(PHOBOSSRC std/experimental/allocator/building_blocks/free_list.d)
*/
module std.experimental.allocator.building_blocks.free_list;
import std.experimental.allocator.common;
import std.typecons : Flag, Yes, No;
/**
$(HTTP en.wikipedia.org/wiki/Free_list, Free list allocator), stackable on top of
another allocator. Allocation requests between `min` and `max` bytes are
rounded up to `max` and served from a singly-linked list of buffers
deallocated in the past. All other allocations are directed to $(D
ParentAllocator). Due to the simplicity of free list management, allocations
from the free list are fast. If `adaptive` is set to `Yes.adaptive`,
the free list gradually reduces its size if allocations tend to use the parent
allocator much more than the lists' available nodes.
One instantiation is of particular interest: $(D FreeList!(0, unbounded)) puts
every deallocation in the freelist, and subsequently serves any allocation from
the freelist (if not empty). There is no checking of size matching, which would
be incorrect for a freestanding allocator but is both correct and fast when an
owning allocator on top of the free list allocator (such as `Segregator`) is
already in charge of handling size checking.
The following methods are defined if `ParentAllocator` defines them, and
forward to it: `expand`, `owns`, `reallocate`.
*/
struct FreeList(ParentAllocator,
size_t minSize, size_t maxSize = minSize,
Flag!"adaptive" adaptive = No.adaptive)
{
import std.conv : text;
import std.exception : enforce;
import std.traits : hasMember;
import std.typecons : Ternary;
import std.experimental.allocator.building_blocks.null_allocator : NullAllocator;
static assert(minSize != unbounded, "Use minSize = 0 for no low bound.");
static assert(maxSize >= (void*).sizeof,
"Maximum size must accommodate a pointer.");
private enum unchecked = minSize == 0 && maxSize == unbounded;
private enum hasTolerance = !unchecked && (minSize != maxSize
|| maxSize == chooseAtRuntime);
static if (minSize == chooseAtRuntime)
{
/**
Returns the smallest allocation size eligible for allocation from the
freelist. (If $(D minSize != chooseAtRuntime), this is simply an alias
for `minSize`.)
*/
@property size_t min() const
{
assert(_min != chooseAtRuntime);
return _min;
}
/**
If `FreeList` has been instantiated with $(D minSize ==
chooseAtRuntime), then the `min` property is writable. Setting it
must precede any allocation.
Params:
low = new value for `min`
Precondition: $(D low <= max), or $(D maxSize == chooseAtRuntime) and
`max` has not yet been initialized. Also, no allocation has been
yet done with this allocator.
Postcondition: $(D min == low)
*/
@property void min(size_t low)
{
assert(low <= max || max == chooseAtRuntime);
minimize;
_min = low;
}
}
else
{
alias min = minSize;
}
static if (maxSize == chooseAtRuntime)
{
/**
Returns the largest allocation size eligible for allocation from the
freelist. (If $(D maxSize != chooseAtRuntime), this is simply an alias
for `maxSize`.) All allocation requests for sizes greater than or
equal to `min` and less than or equal to `max` are rounded to $(D
max) and forwarded to the parent allocator. When the block fitting the
same constraint gets deallocated, it is put in the freelist with the
allocated size assumed to be `max`.
*/
@property size_t max() const { return _max; }
/**
If `FreeList` has been instantiated with $(D maxSize ==
chooseAtRuntime), then the `max` property is writable. Setting it
must precede any allocation.
Params:
high = new value for `max`
Precondition: $(D high >= min), or $(D minSize == chooseAtRuntime) and
`min` has not yet been initialized. Also $(D high >= (void*).sizeof). Also, no allocation has been yet done with this allocator.
Postcondition: $(D max == high)
*/
@property void max(size_t high)
{
assert((high >= min || min == chooseAtRuntime)
&& high >= (void*).sizeof);
minimize;
_max = high;
}
@system unittest
{
import std.experimental.allocator.common : chooseAtRuntime;
import std.experimental.allocator.mallocator : Mallocator;
FreeList!(Mallocator, chooseAtRuntime, chooseAtRuntime) a;
a.min = 64;
a.max = 128;
assert(a.min == 64);
assert(a.max == 128);
}
}
else
{
alias max = maxSize;
}
private bool tooSmall(size_t n) const
{
static if (minSize == 0) return false;
else return n < min;
}
private bool tooLarge(size_t n) const
{
static if (maxSize == unbounded) return false;
else return n > max;
}
private bool freeListEligible(size_t n) const
{
static if (unchecked)
{
return true;
}
else
{
static if (minSize == 0)
{
if (!n) return false;
}
static if (minSize == maxSize && minSize != chooseAtRuntime)
return n == maxSize;
else
return !tooSmall(n) && !tooLarge(n);
}
}
static if (!unchecked)
private void[] blockFor(Node* p)
{
assert(p);
return (cast(void*) p)[0 .. max];
}
// statistics
static if (adaptive == Yes.adaptive)
{
private enum double windowLength = 1000.0;
private enum double tooFewMisses = 0.01;
private double probMiss = 1.0; // start with a high miss probability
private uint accumSamples, accumMisses;
void updateStats()
{
assert(accumSamples >= accumMisses);
/*
Given that for the past windowLength samples we saw misses with
estimated probability probMiss, and assuming the new sample wasMiss or
not, what's the new estimated probMiss?
*/
probMiss = (probMiss * windowLength + accumMisses)
/ (windowLength + accumSamples);
assert(probMiss <= 1.0);
accumSamples = 0;
accumMisses = 0;
// If probability to miss is under x%, yank one off the freelist
static if (!unchecked)
{
if (probMiss < tooFewMisses && _root)
{
auto b = blockFor(_root);
_root = _root.next;
parent.deallocate(b);
}
}
}
}
private struct Node { Node* next; }
static assert(ParentAllocator.alignment >= Node.alignof);
// state
/**
The parent allocator. Depending on whether `ParentAllocator` holds state
or not, this is a member variable or an alias for
`ParentAllocator.instance`.
*/
static if (stateSize!ParentAllocator) ParentAllocator parent;
else alias parent = ParentAllocator.instance;
private Node* root;
static if (minSize == chooseAtRuntime) private size_t _min = chooseAtRuntime;
static if (maxSize == chooseAtRuntime) private size_t _max = chooseAtRuntime;
/**
Alignment offered.
*/
alias alignment = ParentAllocator.alignment;
/**
If $(D maxSize == unbounded), returns `parent.goodAllocSize(bytes)`.
Otherwise, returns `max` for sizes in the interval $(D [min, max]), and
`parent.goodAllocSize(bytes)` otherwise.
Precondition:
If set at runtime, `min` and/or `max` must be initialized
appropriately.
Postcondition:
$(D result >= bytes)
*/
size_t goodAllocSize(size_t bytes)
{
assert(minSize != chooseAtRuntime && maxSize != chooseAtRuntime);
static if (maxSize != unbounded)
{
if (freeListEligible(bytes))
{
assert(parent.goodAllocSize(max) == max,
text("Wrongly configured freelist: maximum should be ",
parent.goodAllocSize(max), " instead of ", max));
return max;
}
}
return parent.goodAllocSize(bytes);
}
private void[] allocateEligible(size_t bytes)
{
assert(bytes);
if (root)
{
// faster
auto result = (cast(ubyte*) root)[0 .. bytes];
root = root.next;
return result;
}
// slower
static if (hasTolerance)
{
immutable toAllocate = max;
}
else
{
alias toAllocate = bytes;
}
assert(toAllocate == max || max == unbounded);
auto result = parent.allocate(toAllocate);
static if (hasTolerance)
{
if (result) result = result.ptr[0 .. bytes];
}
static if (adaptive == Yes.adaptive)
{
++accumMisses;
updateStats;
}
return result;
}
/**
Allocates memory either off of the free list or from the parent allocator.
If `n` is within $(D [min, max]) or if the free list is unchecked
($(D minSize == 0 && maxSize == size_t.max)), then the free list is
consulted first. If not empty (hit), the block at the front of the free
list is removed from the list and returned. Otherwise (miss), a new block
of `max` bytes is allocated, truncated to `n` bytes, and returned.
Params:
n = number of bytes to allocate
Returns:
The allocated block, or `null`.
Precondition:
If set at runtime, `min` and/or `max` must be initialized
appropriately.
Postcondition: $(D result.length == bytes || result is null)
*/
void[] allocate(size_t n)
{
static if (adaptive == Yes.adaptive) ++accumSamples;
assert(n < size_t.max / 2);
// fast path
if (freeListEligible(n))
{
return allocateEligible(n);
}
// slower
static if (adaptive == Yes.adaptive)
{
updateStats;
}
return parent.allocate(n);
}
// Forwarding methods
mixin(forwardToMember("parent",
"expand", "owns", "reallocate"));
/**
If `block.length` is within $(D [min, max]) or if the free list is
unchecked ($(D minSize == 0 && maxSize == size_t.max)), then inserts the
block at the front of the free list. For all others, forwards to $(D
parent.deallocate) if `Parent.deallocate` is defined.
Params:
block = Block to deallocate.
Precondition:
If set at runtime, `min` and/or `max` must be initialized
appropriately. The block must have been allocated with this
freelist, and no dynamic changing of `min` or `max` is allowed to
occur between allocation and deallocation.
*/
bool deallocate(void[] block)
{
if (freeListEligible(block.length))
{
if (min == 0)
{
// In this case a null pointer might have made it this far.
if (block is null) return true;
}
auto t = root;
root = cast(Node*) block.ptr;
root.next = t;
return true;
}
static if (hasMember!(ParentAllocator, "deallocate"))
return parent.deallocate(block);
else
return false;
}
/**
Defined only if `ParentAllocator` defines `deallocateAll`. If so,
forwards to it and resets the freelist.
*/
static if (hasMember!(ParentAllocator, "deallocateAll"))
bool deallocateAll()
{
root = null;
return parent.deallocateAll();
}
/**
Nonstandard function that minimizes the memory usage of the freelist by
freeing each element in turn. Defined only if `ParentAllocator` defines
`deallocate`. $(D FreeList!(0, unbounded)) does not have this function.
*/
static if (hasMember!(ParentAllocator, "deallocate") && !unchecked)
void minimize()
{
while (root)
{
auto nuke = blockFor(root);
root = root.next;
parent.deallocate(nuke);
}
}
/**
If `ParentAllocator` defines `deallocate`, the list frees all nodes
on destruction. $(D FreeList!(0, unbounded)) does not deallocate the memory
on destruction.
*/
static if (!is(ParentAllocator == NullAllocator) &&
hasMember!(ParentAllocator, "deallocate") && !unchecked)
~this()
{
minimize();
}
}
@system unittest
{
import std.experimental.allocator.mallocator : Mallocator;
import std.experimental.allocator.building_blocks.stats_collector
: StatsCollector, Options;
struct StatsCollectorWrapper {
~this()
{
// buf2 should still be around and buf1 deallocated
assert(parent.numDeallocate == 1);
assert(parent.bytesUsed == 16);
}
static StatsCollector!(Mallocator, Options.all) parent;
alias parent this;
}
FreeList!(StatsCollectorWrapper, 16, 16) fl;
auto buf1 = fl.allocate(16);
auto buf2 = fl.allocate(16);
assert(fl.parent.bytesUsed == 32);
// After this, the list has 1 node, so no actual deallocation by Mallocator
fl.deallocate(buf1);
assert(fl.parent.bytesUsed == 32);
// Destruction should only deallocate the node
destroy(fl);
}
@system unittest
{
import std.experimental.allocator.gc_allocator : GCAllocator;
FreeList!(GCAllocator, 0, 8) fl;
assert(fl.root is null);
auto b1 = fl.allocate(7);
fl.allocate(8);
assert(fl.root is null);
// Ensure deallocate inherits from parent
() nothrow @nogc { fl.deallocate(b1); }();
assert(fl.root !is null);
fl.allocate(8);
assert(fl.root is null);
}
@system unittest
{
import std.experimental.allocator.gc_allocator : GCAllocator;
FreeList!(GCAllocator, 0, 16) fl;
// Not @nogc because of std.conv.text
assert((() nothrow @safe /*@nogc*/ => fl.goodAllocSize(1))() == 16);
}
// Test that deallocateAll infers from parent
@system unittest
{
import std.experimental.allocator.building_blocks.region : Region;
auto fl = FreeList!(Region!(), 0, 16)(Region!()(new ubyte[1024 * 64]));
auto b = fl.allocate(42);
assert(b.length == 42);
assert((() pure nothrow @safe @nogc => fl.expand(b, 48))());
assert(b.length == 90);
assert((() nothrow @nogc => fl.reallocate(b, 100))());
assert(b.length == 100);
assert((() nothrow @nogc => fl.deallocateAll())());
}
/**
Free list built on top of exactly one contiguous block of memory. The block is
assumed to have been allocated with `ParentAllocator`, and is released in
`ContiguousFreeList`'s destructor (unless `ParentAllocator` is $(D
NullAllocator)).
`ContiguousFreeList` has most advantages of `FreeList` but fewer
disadvantages. It has better cache locality because items are closer to one
another. It imposes less fragmentation on its parent allocator.
The disadvantages of `ContiguousFreeList` over `FreeList` are its pay
upfront model (as opposed to `FreeList`'s pay-as-you-go approach), and a
hard limit on the number of nodes in the list. Thus, a large number of long-
lived objects may occupy the entire block, making it unavailable for serving
allocations from the free list. However, an absolute cap on the free list size
may be beneficial.
The options $(D minSize == unbounded) and $(D maxSize == unbounded) are not
available for `ContiguousFreeList`.
*/
struct ContiguousFreeList(ParentAllocator,
size_t minSize, size_t maxSize = minSize)
{
import std.experimental.allocator.building_blocks.null_allocator
: NullAllocator;
import std.experimental.allocator.building_blocks.stats_collector
: StatsCollector, Options;
import std.traits : hasMember;
import std.typecons : Ternary;
alias Impl = FreeList!(NullAllocator, minSize, maxSize);
enum unchecked = minSize == 0 && maxSize == unbounded;
alias Node = Impl.Node;
alias SParent = StatsCollector!(ParentAllocator, Options.bytesUsed);
// state
/**
The parent allocator. Depending on whether `ParentAllocator` holds state
or not, this is a member variable or an alias for
`ParentAllocator.instance`.
*/
SParent parent;
FreeList!(NullAllocator, minSize, maxSize) fl;
void[] support;
size_t allocated;
/// Alignment offered.
enum uint alignment = (void*).alignof;
private void initialize(ubyte[] buffer, size_t itemSize = fl.max)
{
assert(itemSize != unbounded && itemSize != chooseAtRuntime);
assert(buffer.ptr.alignedAt(alignment));
immutable available = buffer.length / itemSize;
if (available == 0) return;
support = buffer;
fl.root = cast(Node*) buffer.ptr;
auto past = cast(Node*) (buffer.ptr + available * itemSize);
for (auto n = fl.root; ; )
{
auto next = cast(Node*) (cast(ubyte*) n + itemSize);
if (next == past)
{
n.next = null;
break;
}
assert(next < past);
assert(n < next);
n.next = next;
n = next;
}
}
/**
Constructors setting up the memory structured as a free list.
Params:
buffer = Buffer to structure as a free list. If `ParentAllocator` is not
`NullAllocator`, the buffer is assumed to be allocated by `parent`
and will be freed in the destructor.
parent = Parent allocator. For construction from stateless allocators, use
their `instance` static member.
bytes = Bytes (not items) to be allocated for the free list. Memory will be
allocated during construction and deallocated in the destructor.
max = Maximum size eligible for freelisting. Construction with this
parameter is defined only if $(D maxSize == chooseAtRuntime) or $(D maxSize
== unbounded).
min = Minimum size eligible for freelisting. Construction with this
parameter is defined only if $(D minSize == chooseAtRuntime). If this
condition is met and no `min` parameter is present, `min` is
initialized with `max`.
*/
static if (!stateSize!ParentAllocator)
this(ubyte[] buffer)
{
initialize(buffer);
}
/// ditto
static if (stateSize!ParentAllocator)
this(ParentAllocator parent, ubyte[] buffer)
{
initialize(buffer);
this.parent = SParent(parent);
}
/// ditto
static if (!stateSize!ParentAllocator)
this(size_t bytes)
{
initialize(cast(ubyte[])(ParentAllocator.instance.allocate(bytes)));
}
/// ditto
static if (stateSize!ParentAllocator)
this(ParentAllocator parent, size_t bytes)
{
initialize(cast(ubyte[])(parent.allocate(bytes)));
this.parent = SParent(parent);
}
/// ditto
static if (!stateSize!ParentAllocator
&& (maxSize == chooseAtRuntime || maxSize == unbounded))
this(size_t bytes, size_t max)
{
static if (maxSize == chooseAtRuntime) fl.max = max;
static if (minSize == chooseAtRuntime) fl.min = max;
initialize(cast(ubyte[])(parent.allocate(bytes)), max);
}
/// ditto
static if (stateSize!ParentAllocator
&& (maxSize == chooseAtRuntime || maxSize == unbounded))
this(ParentAllocator parent, size_t bytes, size_t max)
{
static if (maxSize == chooseAtRuntime) fl.max = max;
static if (minSize == chooseAtRuntime) fl.min = max;
initialize(cast(ubyte[])(parent.allocate(bytes)), max);
this.parent = SParent(parent);
}
/// ditto
static if (!stateSize!ParentAllocator
&& (maxSize == chooseAtRuntime || maxSize == unbounded)
&& minSize == chooseAtRuntime)
this(size_t bytes, size_t min, size_t max)
{
static if (maxSize == chooseAtRuntime) fl.max = max;
fl.min = min;
initialize(cast(ubyte[])(parent.allocate(bytes)), max);
static if (stateSize!ParentAllocator)
this.parent = SParent(parent);
}
/// ditto
static if (stateSize!ParentAllocator
&& (maxSize == chooseAtRuntime || maxSize == unbounded)
&& minSize == chooseAtRuntime)
this(ParentAllocator parent, size_t bytes, size_t min, size_t max)
{
static if (maxSize == chooseAtRuntime) fl.max = max;
fl.min = min;
initialize(cast(ubyte[])(parent.allocate(bytes)), max);
static if (stateSize!ParentAllocator)
this.parent = SParent(parent);
}
/**
If `n` is eligible for freelisting, returns `max`. Otherwise, returns
`parent.goodAllocSize(n)`.
Precondition:
If set at runtime, `min` and/or `max` must be initialized
appropriately.
Postcondition:
$(D result >= bytes)
*/
size_t goodAllocSize(size_t n)
{
if (fl.freeListEligible(n)) return fl.max;
return parent.goodAllocSize(n);
}
/**
Allocate `n` bytes of memory. If `n` is eligible for freelist and the
freelist is not empty, pops the memory off the free list. In all other
cases, uses the parent allocator.
*/
void[] allocate(size_t n)
{
auto result = fl.allocate(n);
if (result)
{
// Only case we care about: eligible sizes allocated from us
++allocated;
return result;
}
// All others, allocate from parent
return parent.allocate(n);
}
/**
Defined if `ParentAllocator` defines it. Checks whether the block
belongs to this allocator.
*/
static if (hasMember!(SParent, "owns") || unchecked)
// Ternary owns(const void[] b) const ?
Ternary owns(void[] b)
{
if ((() @trusted => support && b
&& (&support[0] <= &b[0])
&& (&b[0] < &support[0] + support.length)
)())
return Ternary.yes;
static if (unchecked)
return Ternary.no;
else
return parent.owns(b);
}
/**
Deallocates `b`. If it's of eligible size, it's put on the free list.
Otherwise, it's returned to `parent`.
Precondition: `b` has been allocated with this allocator, or is $(D
null).
*/
bool deallocate(void[] b)
{
if (support.ptr <= b.ptr && b.ptr < support.ptr + support.length)
{
// we own this guy
assert(fl.freeListEligible(b.length));
assert(allocated);
--allocated;
// Put manually in the freelist
auto t = fl.root;
fl.root = cast(Node*) b.ptr;
fl.root.next = t;
return true;
}
return parent.deallocate(b);
}
/**
Deallocates everything from the parent.
*/
static if (hasMember!(ParentAllocator, "deallocateAll")
&& stateSize!ParentAllocator)
bool deallocateAll()
{
bool result = fl.deallocateAll && parent.deallocateAll;
allocated = 0;
return result;
}
/**
Returns `Ternary.yes` if no memory is currently allocated with this
allocator, `Ternary.no` otherwise. This method never returns
`Ternary.unknown`.
*/
Ternary empty()
{
return Ternary(allocated == 0 && parent.bytesUsed == 0);
}
}
///
@safe unittest
{
import std.experimental.allocator.building_blocks.allocator_list
: AllocatorList;
import std.experimental.allocator.gc_allocator : GCAllocator;
import std.experimental.allocator.common : unbounded;
alias ScalableFreeList = AllocatorList!((n) =>
ContiguousFreeList!(GCAllocator, 0, unbounded)(4096)
);
}
@system unittest
{
import std.experimental.allocator.building_blocks.null_allocator
: NullAllocator;
import std.typecons : Ternary;
alias A = ContiguousFreeList!(NullAllocator, 0, 64);
auto a = A(new ubyte[1024]);
assert((() nothrow @safe @nogc => a.empty)() == Ternary.yes);
assert((() pure nothrow @safe @nogc => a.goodAllocSize(15))() == 64);
assert((() pure nothrow @safe @nogc => a.goodAllocSize(65))()
== (() nothrow @safe @nogc => NullAllocator.instance.goodAllocSize(65))());
auto b = a.allocate(100);
assert((() nothrow @safe @nogc => a.empty)() == Ternary.yes);
assert(b.length == 0);
// Ensure deallocate inherits from parent
() nothrow @nogc { a.deallocate(b); }();
b = a.allocate(64);
assert((() nothrow @safe @nogc => a.empty)() == Ternary.no);
assert(b.length == 64);
assert((() nothrow @safe @nogc => a.owns(b))() == Ternary.yes);
assert((() nothrow @safe @nogc => a.owns(null))() == Ternary.no);
() nothrow @nogc { a.deallocate(b); }();
}
@system unittest
{
import std.experimental.allocator.building_blocks.region : Region;
import std.experimental.allocator.gc_allocator : GCAllocator;
import std.typecons : Ternary;
alias A = ContiguousFreeList!(Region!GCAllocator, 0, 64);
auto a = A(Region!GCAllocator(1024 * 4), 1024);
assert((() nothrow @safe @nogc => a.empty)() == Ternary.yes);
assert((() pure nothrow @safe @nogc => a.goodAllocSize(15))() == 64);
assert((() pure nothrow @safe @nogc => a.goodAllocSize(65))()
== (() pure nothrow @safe @nogc => a.parent.goodAllocSize(65))());
auto b = a.allocate(100);
assert((() nothrow @safe @nogc => a.empty)() == Ternary.no);
assert(a.allocated == 0);
assert(b.length == 100);
// Ensure deallocate inherits from parent
assert((() nothrow @nogc => a.deallocate(b))());
assert((() nothrow @safe @nogc => a.empty)() == Ternary.yes);
b = a.allocate(64);
assert((() nothrow @safe @nogc => a.empty)() == Ternary.no);
assert(b.length == 64);
assert(a.reallocate(b, 100));
assert(b.length == 100);
assert((() nothrow @safe @nogc => a.owns(b))() == Ternary.yes);
assert((() nothrow @safe @nogc => a.owns(null))() == Ternary.no);
// Test deallocate infers from parent
assert((() nothrow @nogc => a.deallocate(b))());
assert((() nothrow @nogc => a.deallocateAll())());
}
@system unittest
{
import std.experimental.allocator.gc_allocator : GCAllocator;
alias A = ContiguousFreeList!(GCAllocator, 64, 64);
auto a = A(1024);
const b = a.allocate(100);
assert(b.length == 100);
}
/**
FreeList shared across threads. Allocation and deallocation are lock-free. The
parameters have the same semantics as for `FreeList`.
`expand` is defined to forward to `ParentAllocator.expand`
(it must be also `shared`).
*/
struct SharedFreeList(ParentAllocator,
size_t minSize, size_t maxSize = minSize, size_t approxMaxNodes = unbounded)
{
import std.conv : text;
import std.exception : enforce;
import std.traits : hasMember;
static if (hasMember!(ParentAllocator, "owns"))
{
import std.typecons : Ternary;
}
static assert(approxMaxNodes, "approxMaxNodes must not be null.");
static assert(minSize != unbounded, "Use minSize = 0 for no low bound.");
static assert(maxSize >= (void*).sizeof,
"Maximum size must accommodate a pointer.");
import core.atomic : atomicOp, cas;
import core.internal.spinlock : SpinLock;
private enum unchecked = minSize == 0 && maxSize == unbounded;
static if (minSize != chooseAtRuntime)
{
alias min = minSize;
}
else
{
private shared size_t _min = chooseAtRuntime;
@property size_t min() const shared
{
assert(_min != chooseAtRuntime);
return _min;
}
@property void min(size_t x) shared
{
enforce(x <= max);
enforce(cas(&_min, chooseAtRuntime, x),
"SharedFreeList.min must be initialized exactly once.");
}
static if (maxSize == chooseAtRuntime)
{
// Both bounds can be set, provide one function for setting both in
// one shot.
void setBounds(size_t low, size_t high) shared
{
enforce(low <= high && high >= (void*).sizeof);
enforce(cas(&_min, chooseAtRuntime, low),
"SharedFreeList.min must be initialized exactly once.");
enforce(cas(&_max, chooseAtRuntime, high),
"SharedFreeList.max must be initialized exactly once.");
}
}
}
private bool tooSmall(size_t n) const shared
{
static if (minSize == 0) return false;
else static if (minSize == chooseAtRuntime) return n < _min;
else return n < minSize;
}
static if (maxSize != chooseAtRuntime)
{
alias max = maxSize;
}
else
{
private shared size_t _max = chooseAtRuntime;
@property size_t max() const shared { return _max; }
@property void max(size_t x) shared
{
enforce(x >= min && x >= (void*).sizeof);
enforce(cas(&_max, chooseAtRuntime, x),
"SharedFreeList.max must be initialized exactly once.");
}
}
private bool tooLarge(size_t n) const shared
{
static if (maxSize == unbounded) return false;
else static if (maxSize == chooseAtRuntime) return n > _max;
else return n > maxSize;
}
private bool freeListEligible(size_t n) const shared
{
static if (minSize == maxSize && minSize != chooseAtRuntime)
return n == maxSize;
else return !tooSmall(n) && !tooLarge(n);
}
static if (approxMaxNodes != chooseAtRuntime)
{
alias approxMaxLength = approxMaxNodes;
}
else
{
private shared size_t _approxMaxLength = chooseAtRuntime;
@property size_t approxMaxLength() const shared { return _approxMaxLength; }
@property void approxMaxLength(size_t x) shared { _approxMaxLength = enforce(x); }
}
static if (approxMaxNodes != unbounded)
{
private shared size_t nodes;
private void incNodes() shared
{
atomicOp!("+=")(nodes, 1);
}
private void decNodes() shared
{
assert(nodes);
atomicOp!("-=")(nodes, 1);
}
private void resetNodes() shared
{
nodes = 0;
}
private bool nodesFull() shared
{
return nodes >= approxMaxLength;
}
}
else
{
private static void incNodes() { }
private static void decNodes() { }
private static void resetNodes() { }
private enum bool nodesFull = false;
}
version (StdDdoc)
{
/**
Properties for getting (and possibly setting) the bounds. Setting bounds
is allowed only once , and before any allocation takes place. Otherwise,
the primitives have the same semantics as those of `FreeList`.
*/
@property size_t min();
/// Ditto
@property void min(size_t newMinSize);
/// Ditto
@property size_t max();
/// Ditto
@property void max(size_t newMaxSize);
/// Ditto
void setBounds(size_t newMin, size_t newMax);
/**
Properties for getting (and possibly setting) the approximate maximum length of a shared freelist.
*/
@property size_t approxMaxLength() const shared;
/// ditto
@property void approxMaxLength(size_t x) shared;
}
/**
The parent allocator. Depending on whether `ParentAllocator` holds state
or not, this is a member variable or an alias for
`ParentAllocator.instance`.
*/
static if (stateSize!ParentAllocator) shared ParentAllocator parent;
else alias parent = ParentAllocator.instance;