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