1 /**
2  * D Documentation Generator
3  * Copyright: © 2014 Economic Modeling Specialists, Intl., © 2015 Ferdinand Majerech
4  * Authors: Brian Schott, Ferdinand Majerech
5  * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt Boost License 1.0)
6  */
7 
8 /// std.allocator-compatible memory allocator.
9 module allocator;
10 
11 public import std.experimental.allocator;
12 public import std.experimental.allocator.building_blocks.fallback_allocator;
13 public import std.experimental.allocator.gc_allocator;
14 public import std.experimental.allocator.mallocator;
15 import std.stdio;
16 import std.exception: assumeWontThrow;
17 import std.typecons: Ternary;
18 
19 
20 /** Allocator used by hmod (block allocator with a GC fallback for allcs bigger than block size)
21  */
22 public alias Allocator = FallbackAllocator!(
23 	HmodBlockAllocator!(32 * 1024), 
24 	GCAllocator);
25 
26 
27 /** A somewhat incomplete (no dealloc) std.allocator implementation - passed to
28  * libdparse.
29  *
30  * All data is deallocated in destructor.
31  *
32  * Allocates memory in fixed-size blocks and tries to place allocations into
33  * those blocks. Allocations larger than a block fail.
34  *
35  * Based on BlockAllocator from Brian Schott's containers library
36  */
37 struct HmodBlockAllocator(size_t blockSize)
38 {
39 	union
40 	{
41 		private size_t bytesAllocated_;
42 		/// Number of bytes allocated over time.
43 		const size_t bytesAllocated;
44 	}
45 	// Since we don't support deallocation (right now), these two are the same
46 	/// The highest number of bytes allocated at any given moment.
47 	alias bytesHighTide = bytesAllocated;
48 	union 
49 	{
50 		private size_t bytesWithSlack_;
51 		/// Number of bytes allocated at the moment, including slack (wasted space)
52 		const size_t bytesWithSlack;
53 	}
54 	union 
55 	{
56 		private size_t bytesGivenUp_;
57 		/// Total size of allocations that failed (bigger than block size).
58 		const size_t bytesGivenUp;
59 	}
60 	union 
61 	{
62 		private size_t allocsGivenUp_;
63 		/// Number of allocations that failed.
64 		const size_t allocsGivenUp;
65 	}
66 	union 
67 	{
68 		private size_t bytesAttemptedToDeallocate_;
69 		/// Number of bytes the user has attempted to deallocate.
70 		const size_t bytesAttemptedToDeallocate;
71 	}
72 	/**
73 	 * Copy construction disabled because this struct clears its memory with a
74 	 * destructor.
75 	 */
76 	@disable this(this);
77 
78 	/**
79 	 * Frees all memory allocated by this allocator
80 	 */
81 	~this() /*pure nothrow*/ @trusted
82 	{
83 		Node* current = root;
84 		Node* previous = void;
85 		while (current !is null)
86 		{
87 			previous = current;
88 			current = current.next;
89 			assert (previous == previous.memory.ptr);
90 			Mallocator.instance.deallocate(previous.memory);
91 		}
92 		root = null;
93 	}
94 
95 	/**
96 	 * Standard allocator operation.
97 	 *
98 	 * Returns null if bytes > blockSize.
99 	 */
100 	void[] allocate(size_t bytes) /*pure*/ nothrow @trusted
101 	out (result)
102 	{
103 		import std.format : format;
104 		assert (!result.length || result.length == bytes,
105 			format("Allocated %d bytes when %d bytes were requested.",
106 				   result.length, bytes));
107 	}
108 	body
109 	{
110 		void updateStats(void[] result)
111 		{
112 			if (!result.length)
113 			{
114 				++allocsGivenUp_;
115 				bytesGivenUp_ += bytes;
116 				return;
117 			}
118 			bytesAllocated_ += result.length;
119 		}
120 		if (bytes > maxAllocationSize)
121 		{
122 			debug
123 			{
124 				import std.exception : assumeWontThrow;
125 				writeln("Big alloc: ", bytes).assumeWontThrow;
126 			}
127 			updateStats(null);
128 			return null; 
129 		}
130 
131 		// Allocate from the beginning of the list. Filled blocks go later in
132 		// the list.
133 		// Give up after three blocks. We don't want to do a full linear scan.
134 		size_t i;
135 		for (Node* current = root; current !is null && i < 3; current = current.next)
136 		{
137 			void[] mem = allocateInNode(current, bytes);
138 			if (mem !is null)
139 			{
140 				updateStats(mem);
141 				return mem;
142 			}
143 			i++;
144 		}
145 		Node* n = allocateNewNode();
146 		bytesWithSlack_ += n.memory.length;
147 		void[] mem = allocateInNode(n, bytes);
148 		n.next = root;
149 		root = n;
150 		updateStats(mem);
151 		return mem;
152 	}
153 
154 	//TODO implement deallocate if/when libdparse uses it (needs allocator design changes)
155 	/// Dummy deallocation function, to keep track of how much the user tried to deallocate.
156 	bool deallocate(void[] b) pure nothrow @trusted
157 	{
158 		bytesAttemptedToDeallocate_ += b.length;
159 		return false;
160 	}
161 
162 	/// Was the given buffer allocated with this allocator?
163 	Ternary owns(void[] b) const pure nothrow @trusted
164 	{
165 		for (const(Node)* current = root; current !is null; current = current.next)
166 		{
167 			if (b.ptr >= current.memory.ptr && b.ptr + b.length <= current.memory.ptr + current.used)
168 				return Ternary.yes;
169 		}
170 		return Ternary.no;
171 	}
172 	/**
173 	 * The maximum number of bytes that can be allocated at a time with this
174 	 * allocator. This is smaller than blockSize because of some internal
175 	 * bookkeeping information.
176 	 */
177 	enum maxAllocationSize = blockSize - Node.sizeof;
178 
179 	/**
180 	 * Allocator's memory alignment
181 	 */
182 	enum alignment = platformAlignment;
183 
184 	/// Write allocation statistics to standard output.
185 	void writeStats()
186 	{
187 		writefln("allocated: %.2fMiB\n" ~
188 				 "deallocate attempts: %.2fMiB\n" ~
189 				 "high tide: %.2f\n" ~
190 				 "allocated + slack: %.2f\n" ~
191 				 "given up (bytes): %.2f\n"  ~
192 				 "given up (allocs): %s\n",
193 				 bytesAllocated / 1000_000.0,
194 				 bytesAttemptedToDeallocate_ / 1000_000.0,
195 				 bytesHighTide / 1000_000.0,
196 				 bytesWithSlack / 1000_000.0,
197 				 bytesGivenUp / 1000_000.0,
198 				 allocsGivenUp);
199 	}
200 private:
201 
202 	/**
203 	 * Allocates a new node along with its memory
204 	 */
205 	Node* allocateNewNode() /*pure*/ nothrow const @trusted
206 	{
207 		void[] memory = Mallocator.instance.allocate(blockSize).assumeWontThrow;
208 		Node* n = cast(Node*) memory.ptr;
209 		n.used = roundUpToMultipleOf(Node.sizeof, platformAlignment);
210 		n.memory = memory;
211 		n.next = null;
212 		return n;
213 	}
214 
215 	/**
216 	 * Allocates memory from the given node
217 	 */
218 	void[] allocateInNode(Node* node, size_t bytes) pure nothrow const @safe
219 	in
220 	{
221 		assert (node !is null);
222 	}
223 	body
224 	{
225 		if (node.used + bytes > node.memory.length)
226 			return null;
227 		immutable prev = node.used;
228 		node.used = roundUpToMultipleOf(node.used + bytes, platformAlignment);
229 		return node.memory[prev .. prev + bytes];
230 	}
231 
232 	/**
233 	 * Single linked list of allocated blocks
234 	 */
235 	static struct Node
236 	{
237 		void[] memory;
238 		size_t used;
239 		Node* next;
240 	}
241 
242 	/**
243 	 * Pointer to the first item in the node list
244 	 */
245 	Node* root;
246 
247 	/**
248 	 * Returns s rounded up to a multiple of base.
249 	 */
250 	static size_t roundUpToMultipleOf(size_t s, uint base) pure nothrow @safe
251 	{
252 		assert(base);
253 		auto rem = s % base;
254 		return rem ? s + base - rem : s;
255 	}
256 }