1 // Written in the D programming language.
2 /**
3 $(H2 Assembling Your Own Allocator)
4 
5 This package also implements
6 untyped composable memory allocators. They are $(I untyped) because they deal
7 exclusively in `void[]` and have no notion of what type the memory allocated
8 would be destined for. They are $(I composable) because the included allocators
9 are building blocks that can be assembled in complex nontrivial allocators.
10 
11 $(P Unlike the allocators for the C and C++ programming languages, which manage
12 the allocated size internally, these allocators require that the client
13 maintains (or knows $(I a priori)) the allocation size for each piece of memory
14 allocated. Put simply, the client must pass the allocated size upon
15 deallocation. Storing the size in the _allocator has significant negative
16 performance implications, and is virtually always redundant because client code
17 needs knowledge of the allocated size in order to avoid buffer overruns. (See
18 more discussion in a $(HTTP open-
19 std.org/JTC1/SC22/WG21/docs/papers/2013/n3536.html, proposal) for sized
20 deallocation in C++.) For this reason, allocators herein traffic in `void[]`
21 as opposed to `void*`.)
22 
23 $(P In order to be usable as an _allocator, a type should implement the
24 following methods with their respective semantics. Only `alignment` and  $(D
25 allocate) are required. If any of the other methods is missing, the _allocator
26 is assumed to not have that capability (for example some allocators do not offer
27 manual deallocation of memory). Allocators should NOT implement
28 unsupported methods to always fail. For example, an allocator that lacks the
29 capability to implement `alignedAllocate` should not define it at all (as
30 opposed to defining it to always return `null` or throw an exception). The
31 missing implementation statically informs other components about the
32 allocator's capabilities and allows them to make design decisions accordingly.)
33 
34 $(BOOKTABLE ,
35 $(TR $(TH Method name) $(TH Semantics))
36 
37 $(TR $(TDC uint alignment;, $(POST $(RES) > 0)) $(TD Returns the minimum
38 alignment of all data returned by the allocator. An allocator may implement $(D
39 alignment) as a statically-known `enum` value only. Applications that need
40 dynamically-chosen alignment values should use the `alignedAllocate` and $(D
41 alignedReallocate) APIs.))
42 
43 $(TR $(TDC size_t goodAllocSize(size_t n);, $(POST $(RES) >= n)) $(TD Allocators
44 customarily allocate memory in discretely-sized chunks. Therefore, a request for
45 `n` bytes may result in a larger allocation. The extra memory allocated goes
46 unused and adds to the so-called $(HTTPS en.wikipedia.org/wiki/Fragmentation_(computing)#Internal_fragmentation,internal fragmentation).
47 The function `goodAllocSize(n)` returns the actual number of bytes that would
48 be allocated upon a request for `n` bytes. This module defines a default
49 implementation that returns `n` rounded up to a multiple of the allocator's
50 alignment.))
51 
52 $(TR $(TDC void[] allocate(size_t s);, $(POST $(RES) is null || $(RES).length ==
53 s)) $(TD If $(D s == 0), the call may return any empty slice (including $(D
54 null)). Otherwise, the call allocates `s` bytes of memory and returns the
55 allocated block, or `null` if the request could not be satisfied.))
56 
57 $(TR $(TDC void[] alignedAllocate(size_t s, uint a);, $(POST $(RES) is null ||
58 $(RES).length == s)) $(TD Similar to `allocate`, with the additional
59 guarantee that the memory returned is aligned to at least `a` bytes. `a`
60 must be a power of 2.))
61 
62 $(TR $(TDC void[] allocateAll();) $(TD Offers all of allocator's memory to the
63 caller, so it's usually defined by fixed-size allocators. If the allocator is
64 currently NOT managing any memory, then `allocateAll()` shall allocate and
65 return all memory available to the allocator, and subsequent calls to all
66 allocation primitives should not succeed (e.g. `allocate` shall return $(D
67 null) etc). Otherwise, `allocateAll` only works on a best-effort basis, and
68 the allocator is allowed to return `null` even if does have available memory.
69 Memory allocated with `allocateAll` is not otherwise special (e.g. can be
70 reallocated or deallocated with the usual primitives, if defined).))
71 
72 $(TR $(TDC bool expand(ref void[] b, size_t delta);, $(POST !$(RES) || b.length
73 == $(I old)(b).length + delta)) $(TD Expands `b` by `delta` bytes. If $(D
74 delta == 0), succeeds without changing `b`. If $(D b is null), returns
75 `false` (the null pointer cannot be expanded in place). Otherwise, $(D
76 b) must be a buffer previously allocated with the same allocator. If expansion
77 was successful, `expand` changes `b`'s length to $(D b.length + delta) and
78 returns `true`. Upon failure, the call effects no change upon the allocator
79 object, leaves `b` unchanged, and returns `false`.))
80 
81 $(TR $(TDC bool reallocate(ref void[] b, size_t s);, $(POST !$(RES) || b.length
82 == s)) $(TD Reallocates `b` to size `s`, possibly moving memory around.
83 `b` must be `null` or a buffer allocated with the same allocator. If
84 reallocation was successful, `reallocate` changes `b` appropriately and
85 returns `true`. Upon failure, the call effects no change upon the allocator
86 object, leaves `b` unchanged, and returns `false`. An allocator should
87 implement `reallocate` if it can derive some advantage from doing so;
88 otherwise, this module defines a `reallocate` free function implemented in
89 terms of `expand`, `allocate`, and `deallocate`.))
90 
91 $(TR $(TDC bool alignedReallocate(ref void[] b,$(BR) size_t s, uint a);, $(POST
92 !$(RES) || b.length == s)) $(TD Similar to `reallocate`, but guarantees the
93 reallocated memory is aligned at `a` bytes. The buffer must have been
94 originated with a call to `alignedAllocate`. `a` must be a power of 2
95 greater than `(void*).sizeof`. An allocator should implement $(D
96 alignedReallocate) if it can derive some advantage from doing so; otherwise,
97 this module defines a `alignedReallocate` free function implemented in terms
98 of `expand`, `alignedAllocate`, and `deallocate`.))
99 
100 $(TR $(TDC Ternary owns(void[] b);) $(TD Returns `Ternary.yes` if `b` has been
101 allocated with this allocator. An allocator should define this method only if it
102 can decide on ownership precisely and fast (in constant time, logarithmic time,
103 or linear time with a low multiplication factor). Traditional allocators such as
104 the C heap do not define such functionality. If $(D b is null), the allocator
105 shall return `Ternary.no`, i.e. no allocator owns the `null` slice.))
106 
107 $(TR $(TDC Ternary resolveInternalPointer(void* p, ref void[] result);) $(TD If
108 `p` is a pointer somewhere inside a block allocated with this allocator,
109 `result` holds a pointer to the beginning of the allocated block and returns
110 `Ternary.yes`. Otherwise, `result` holds `null` and returns `Ternary.no`.
111 If the pointer points immediately after an allocated block, the result is
112 implementation defined.))
113 
114 $(TR $(TDC bool deallocate(void[] b);) $(TD If $(D b is null), does
115 nothing and returns `true`. Otherwise, deallocates memory previously allocated
116 with this allocator and returns `true` if successful, `false` otherwise. An
117 implementation that would not support deallocation (i.e. would always return
118 `false` should not define this primitive at all.)))
119 
120 $(TR $(TDC bool deallocateAll();, $(POST empty)) $(TD Deallocates all memory
121 allocated with this allocator. If an allocator implements this method, it must
122 specify whether its destructor calls it, too.))
123 
124 $(TR $(TDC Ternary empty();) $(TD Returns `Ternary.yes` if and only if the
125 allocator holds no memory (i.e. no allocation has occurred, or all allocations
126 have been deallocated).))
127 
128 $(TR $(TDC static Allocator instance;, $(POST instance $(I is a valid)
129 Allocator $(I object))) $(TD Some allocators are $(I monostate), i.e. have only
130 an instance and hold only global state. (Notable examples are C's own
131 `malloc`-based allocator and D's garbage-collected heap.) Such allocators must
132 define a static `instance` instance that serves as the symbolic placeholder
133 for the global instance of the allocator. An allocator should not hold state
134 and define `instance` simultaneously. Depending on whether the allocator is
135 thread-safe or not, this instance may be `shared`.))
136 )
137 
138 $(H2 Sample Assembly)
139 
140 The example below features an _allocator modeled after $(HTTP jemalloc.net/,
141 jemalloc), which uses a battery of free-list allocators spaced so as to keep
142 internal fragmentation to a minimum. The `FList` definitions specify no
143 bounds for the freelist because the `Segregator` does all size selection in
144 advance.
145 
146 Sizes through 3584 bytes are handled via freelists of staggered sizes. Sizes
147 from 3585 bytes through 4072 KB are handled by a `BitmappedBlock` with a
148 block size of 4 KB. Sizes above that are passed direct to the `GCAllocator`.
149 
150 $(RUNNABLE_EXAMPLE
151     ----
152     import std.experimental.allocator;
153     import std.algorithm.comparison : max;
154 
155     alias FList = FreeList!(GCAllocator, 0, unbounded);
156     alias A = Segregator!(
157         8, FreeList!(GCAllocator, 0, 8),
158         128, Bucketizer!(FList, 1, 128, 16),
159         256, Bucketizer!(FList, 129, 256, 32),
160         512, Bucketizer!(FList, 257, 512, 64),
161         1024, Bucketizer!(FList, 513, 1024, 128),
162         2048, Bucketizer!(FList, 1025, 2048, 256),
163         3584, Bucketizer!(FList, 2049, 3584, 512),
164         4072 * 1024, AllocatorList!(n => Region!GCAllocator(max(n, 1024 * 4096))),
165         GCAllocator
166     );
167     A tuMalloc;
168     auto b = tuMalloc.allocate(500);
169     assert(b.length == 500);
170     auto c = tuMalloc.allocate(113);
171     assert(c.length == 113);
172     assert(tuMalloc.expand(c, 14));
173     tuMalloc.deallocate(b);
174     tuMalloc.deallocate(c);
175     ----
176 )
177 
178 $(H2 Allocating memory for sharing across threads)
179 
180 One allocation pattern used in multithreaded applications is to share memory
181 across threads, and to deallocate blocks in a different thread than the one that
182 allocated it.
183 
184 All allocators in this module accept and return `void[]` (as opposed to
185 $(D shared void[])). This is because at the time of allocation, deallocation, or
186 reallocation, the memory is effectively not `shared` (if it were, it would
187 reveal a bug at the application level).
188 
189 The issue remains of calling `a.deallocate(b)` from a different thread than
190 the one that allocated `b`. It follows that both threads must have access to
191 the same instance `a` of the respective allocator type. By definition of D,
192 this is possible only if `a` has the `shared` qualifier. It follows that
193 the allocator type must implement `allocate` and `deallocate` as $(D
194 shared) methods. That way, the allocator commits to allowing usable `shared`
195 instances.
196 
197 Conversely, allocating memory with one non-`shared` allocator, passing it
198 across threads (by casting the obtained buffer to `shared`), and later
199 deallocating it in a different thread (either with a different allocator object
200 or with the same allocator object after casting it to `shared`) is illegal.
201 
202 $(H2 Building Blocks)
203 
204 $(P The table below gives a synopsis of predefined allocator building blocks,
205 with their respective modules. Either `import` the needed modules individually,
206 or `import` `std.experimental.building_blocks`, which imports them all
207 `public`ly. The building blocks can be assembled in unbounded ways and also
208 combined with your own. For a collection of typical and useful preassembled
209 allocators and for inspiration in defining more such assemblies, refer to
210 $(MREF std,experimental,allocator,showcase).)
211 
212 $(BOOKTABLE,
213 $(TR $(TH Allocator$(BR)) $(TH Description))
214 
215 $(TR $(TDC2 NullAllocator, null_allocator) $(TD Very good at doing absolutely nothing. A good
216 starting point for defining other allocators or for studying the API.))
217 
218 $(TR $(TDC3 GCAllocator, gc_allocator) $(TD The system-provided garbage-collector allocator.
219 This should be the default fallback allocator tapping into system memory. It
220 offers manual `free` and dutifully collects litter.))
221 
222 $(TR $(TDC3 Mallocator, mallocator) $(TD The C heap _allocator, a.k.a. $(D
223 malloc)/`realloc`/`free`. Use sparingly and only for code that is unlikely
224 to leak.))
225 
226 $(TR $(TDC3 AlignedMallocator, mallocator) $(TD Interface to OS-specific _allocators that
227 support specifying alignment:
228 $(HTTP man7.org/linux/man-pages/man3/posix_memalign.3.html, `posix_memalign`)
229 on Posix and $(HTTP msdn.microsoft.com/en-us/library/fs9stz4e(v=vs.80).aspx,
230 `__aligned_xxx`) on Windows.))
231 
232 $(TR $(TDC2 AlignedBlockList, aligned_block_list) $(TD A wrapper around a list of allocators
233 which allow for very fast deallocations.))
234 
235 $(TR $(TDC2 AffixAllocator, affix_allocator) $(TD Allocator that allows and manages allocating
236 extra prefix and/or a suffix bytes for each block allocated.))
237 
238 $(TR $(TDC2 BitmappedBlock, bitmapped_block) $(TD Organizes one contiguous chunk of memory in
239 equal-size blocks and tracks allocation status at the cost of one bit per
240 block.))
241 
242 $(TR $(TDC2 FallbackAllocator, fallback_allocator) $(TD Allocator that combines two other
243  allocators - primary and fallback. Allocation requests are first tried with primary, and
244  upon failure are passed to the fallback. Useful for small and fast allocators
245  fronting general-purpose ones.))
246 
247 $(TR $(TDC2 FreeList, free_list) $(TD Allocator that implements a $(HTTP
248 wikipedia.org/wiki/Free_list, free list) on top of any other allocator. The
249 preferred size, tolerance, and maximum elements are configurable at compile- and
250 run time.))
251 
252 $(TR $(TDC2 SharedFreeList, free_list) $(TD Same features as `FreeList`, but packaged as
253 a `shared` structure that is accessible to several threads.))
254 
255 $(TR $(TDC2 FreeTree, free_tree) $(TD Allocator similar to `FreeList` that uses a
256 binary search tree to adaptively store not one, but many free lists.))
257 
258 $(TR $(TDC2 Region, region) $(TD Region allocator organizes a chunk of memory as a
259 simple bump-the-pointer allocator.))
260 
261 $(TR $(TDC2 InSituRegion, region) $(TD Region holding its own allocation, most often on
262 the stack. Has statically-determined size.))
263 
264 $(TR $(TDC2 SbrkRegion, region) $(TD Region using $(D $(LINK2 https://en.wikipedia.org/wiki/Sbrk,
265 sbrk)) for allocating memory.))
266 
267 $(TR $(TDC3 MmapAllocator, mmap_allocator) $(TD Allocator using
268             $(D $(LINK2 https://en.wikipedia.org/wiki/Mmap, mmap)) directly.))
269 
270 $(TR $(TDC2 StatsCollector, stats_collector) $(TD Collect statistics about any other
271 allocator.))
272 
273 $(TR $(TDC2 Quantizer, quantizer) $(TD Allocates in coarse-grained quantas, thus
274 improving performance of reallocations by often reallocating in place. The drawback is higher memory consumption because of allocated and unused memory.))
275 
276 $(TR $(TDC2 AllocatorList, allocator_list) $(TD Given an allocator factory, lazily creates as
277 many allocators as needed to satisfy allocation requests. The allocators are
278 stored in a linked list. Requests for allocation are satisfied by searching the
279 list in a linear manner.))
280 
281 $(TR $(TDC2 Segregator, segregator) $(TD Segregates allocation requests by size
282 and dispatches them to distinct allocators.))
283 
284 $(TR $(TDC2 Bucketizer, bucketizer) $(TD Divides allocation sizes in discrete buckets and
285 uses an array of allocators, one per bucket, to satisfy requests.))
286 
287 $(TR $(TDC2 AscendingPageAllocator, ascending_page_allocator) $(TD A memory safe allocator
288 where sizes are rounded to a multiple of the page size and allocations are satisfied at increasing addresses.))
289 
290 $(COMMENT $(TR $(TDC2 InternalPointersTree) $(TD Adds support for resolving internal
291 pointers on top of another allocator.)))
292 )
293 
294 Source: $(PHOBOSSRC std/experimental/allocator/building_blocks/package.d)
295 
296 Macros:
297 MYREF2 = $(REF_SHORT $1, std,experimental,allocator,building_blocks,$2)
298 MYREF3 = $(REF_SHORT $1, std,experimental,allocator,$2)
299 TDC = $(TDNW `$1`$+)
300 TDC2 = $(TDNW $(D $(MYREF2 $1,$+))$(BR)$(SMALL
301 `std.experimental.allocator.building_blocks.$2`))
302 TDC3 = $(TDNW $(D $(MYREF3 $1,$+))$(BR)$(SMALL
303 `std.experimental.allocator.$2`))
304 RES = $(I result)
305 POST = $(BR)$(SMALL $(I Post:) $(BLUE `$0`))
306 */
307 
308 module std.experimental.allocator.building_blocks;
309 
310 public import
311     std.experimental.allocator.building_blocks.affix_allocator,
312     std.experimental.allocator.building_blocks.aligned_block_list,
313     std.experimental.allocator.building_blocks.allocator_list,
314     std.experimental.allocator.building_blocks.ascending_page_allocator,
315     std.experimental.allocator.building_blocks.bucketizer,
316     std.experimental.allocator.building_blocks.fallback_allocator,
317     std.experimental.allocator.building_blocks.free_list,
318     std.experimental.allocator.building_blocks.free_tree,
319     std.experimental.allocator.gc_allocator,
320     std.experimental.allocator.building_blocks.bitmapped_block,
321     std.experimental.allocator.building_blocks.kernighan_ritchie,
322     std.experimental.allocator.mallocator,
323     std.experimental.allocator.mmap_allocator,
324     std.experimental.allocator.building_blocks.null_allocator,
325     std.experimental.allocator.building_blocks.quantizer,
326     std.experimental.allocator.building_blocks.region,
327     std.experimental.allocator.building_blocks.segregator,
328     std.experimental.allocator.building_blocks.stats_collector;