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;