1 | /** |
2 | * Copyright (c) Glow Contributors. See CONTRIBUTORS file. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | #include "glow/CodeGen/MemoryAllocator.h" |
18 | #include "glow/Support/Debug.h" |
19 | |
20 | #include "llvm/ADT/SmallVector.h" |
21 | #include "llvm/Support/Casting.h" |
22 | #include "llvm/Support/Debug.h" |
23 | #include "llvm/Support/raw_ostream.h" |
24 | |
25 | #define DEBUG_TYPE "memory-allocator" |
26 | |
27 | using namespace glow; |
28 | |
29 | namespace glow { |
30 | class Value; |
31 | } |
32 | |
33 | /// The type of the address returned by MemoryAllocator::allocate should be at |
34 | /// least 64-bit wide. |
35 | static_assert(sizeof(decltype(MemoryAllocator::npos)) >= 8, |
36 | "Allocated addresses should be at least 64-bit wide" ); |
37 | |
38 | /// The type of the address returned by MemoryAllocator::allocate should be |
39 | /// unsigned |
40 | static_assert(std::is_unsigned<decltype(MemoryAllocator::npos)>{}, |
41 | "Allocated addresses should be unsigned integers" ); |
42 | |
43 | const uint64_t MemoryAllocator::npos = -1; |
44 | |
45 | float MemoryAllocator::getAllocationEfficiency() const { |
46 | if (maxUsedSize_ != 0) { |
47 | return static_cast<float>(maxLiveSize_) / static_cast<float>(maxUsedSize_); |
48 | } else { |
49 | return 0; |
50 | } |
51 | }; |
52 | |
53 | uint64_t MemoryAllocator::getEffectiveSize(uint64_t size) const { |
54 | return alignedSize(size, alignment_); |
55 | } |
56 | |
57 | uint64_t MemoryAllocator::allocate(uint64_t size, Handle handle) { |
58 | // Always allocate buffers properly aligned to hold values of any type. |
59 | // Zero is a valid size and shows up in some shape computations and |
60 | // tests. To associate a Handle with the returned ptr, we |
61 | // need to allocate a segment. |
62 | uint64_t segmentSize = getEffectiveSize(std::max<uint64_t>(1, size)); |
63 | uint64_t prev = 0; |
64 | for (auto it = segments_.begin(), e = segments_.end(); it != e; it++) { |
65 | if (it->begin - prev >= segmentSize) { |
66 | segments_.emplace(it, prev, prev + segmentSize); |
67 | maxUsedSize_ = std::max(maxUsedSize_, prev + segmentSize); |
68 | liveSize_ += segmentSize; |
69 | maxLiveSize_ = std::max(maxLiveSize_, liveSize_); |
70 | setHandle(prev, size, handle); |
71 | return prev; |
72 | } |
73 | prev = it->end; |
74 | } |
75 | // Could not find a place for the new buffer in the middle of the list. Push |
76 | // the new allocation to the end of the stack. |
77 | |
78 | // Check that we are not allocating memory beyond the pool size. |
79 | if (memorySize_ && (prev + segmentSize) > memorySize_) { |
80 | return npos; |
81 | } |
82 | |
83 | segments_.emplace_back(prev, prev + segmentSize); |
84 | maxUsedSize_ = std::max(maxUsedSize_, prev + segmentSize); |
85 | liveSize_ += segmentSize; |
86 | maxLiveSize_ = std::max(maxLiveSize_, liveSize_); |
87 | setHandle(prev, size, handle); |
88 | return prev; |
89 | } |
90 | |
91 | void MemoryAllocator::evictFirstFit(uint64_t size, |
92 | const std::set<Handle> &mustNotEvict, |
93 | std::vector<Handle> &evicted) { |
94 | // Use the first fit strategy to evict allocated blocks. |
95 | size = getEffectiveSize(size); |
96 | bool hasSeenNonEvicted{false}; |
97 | uint64_t startAddress = 0; |
98 | uint64_t begin = 0; |
99 | llvm::SmallVector<std::pair<Segment, Handle>, 16> evictionCandidates; |
100 | for (auto it = segments_.begin(), e = segments_.end(); it != e; it++) { |
101 | // Skip any allocations below the start address. |
102 | if (it->begin < startAddress) { |
103 | continue; |
104 | } |
105 | auto curHandle = getHandle(it->begin); |
106 | if (mustNotEvict.count(curHandle)) { |
107 | DEBUG_GLOW(llvm::dbgs() |
108 | << "Cannot evict a buffer from '" << name_ << "' : " |
109 | << "address: " << it->begin << " size: " << size << "\n" ); |
110 | // The block cannot be evicted. Start looking after it. |
111 | begin = it->end; |
112 | evictionCandidates.clear(); |
113 | hasSeenNonEvicted = true; |
114 | continue; |
115 | } |
116 | // Remember current block as a candidate. |
117 | evictionCandidates.emplace_back(std::make_pair(*it, curHandle)); |
118 | // If the total to be evicted size is enough, no need to look any further. |
119 | if (it->end - begin >= size) { |
120 | break; |
121 | } |
122 | } |
123 | |
124 | if ((!evictionCandidates.empty() && |
125 | evictionCandidates.back().first.end - begin >= size) || |
126 | (!hasSeenNonEvicted && memorySize_ >= size)) { |
127 | // Now evict all eviction candidates. |
128 | for (auto &candidate : evictionCandidates) { |
129 | auto &curHandle = candidate.second; |
130 | auto &segment = candidate.first; |
131 | (void)segment; |
132 | DEBUG_GLOW(llvm::dbgs() << "Evict a buffer from the '" << name_ << "': " |
133 | << "address: " << segment.begin |
134 | << " size: " << segment.size() << "\n" ); |
135 | deallocate(curHandle); |
136 | evicted.emplace_back(curHandle); |
137 | } |
138 | } |
139 | } |
140 | |
141 | uint64_t MemoryAllocator::allocate(uint64_t size, Handle handle, |
142 | const std::set<Handle> &mustNotEvict, |
143 | std::vector<Handle> &evicted) { |
144 | // Try the usual allocation first. |
145 | auto ptr = allocate(size, handle); |
146 | // If it was possible to allocate the requested block, just return it. |
147 | if (ptr != npos) { |
148 | return ptr; |
149 | } |
150 | // Allocation was not possible, try to evict something. |
151 | // Use the first fit strategy to evict allocated blocks. |
152 | evictFirstFit(size, mustNotEvict, evicted); |
153 | // Try again to allocate the space. This time it should succeed. |
154 | ptr = allocate(size, handle); |
155 | return ptr; |
156 | } |
157 | |
158 | void MemoryAllocator::deallocate(Handle handle) { |
159 | auto ptr = getAddress(handle); |
160 | for (auto it = segments_.begin(), e = segments_.end(); it != e; it++) { |
161 | if (it->begin == ptr) { |
162 | liveSize_ -= it->size(); |
163 | maxLiveSize_ = std::max(maxLiveSize_, liveSize_); |
164 | segments_.erase(it); |
165 | addrToHandleMap_.erase(ptr); |
166 | handleToSegmentMap_.erase(handle); |
167 | return; |
168 | } |
169 | } |
170 | llvm_unreachable("Unknown buffer to deallocate" ); |
171 | } |
172 | |
173 | bool MemoryAllocator::hasHandle(uint64_t address) const { |
174 | auto it = addrToHandleMap_.find(address); |
175 | return it != addrToHandleMap_.end(); |
176 | } |
177 | |
178 | MemoryAllocator::Handle MemoryAllocator::getHandle(uint64_t address) const { |
179 | auto it = addrToHandleMap_.find(address); |
180 | assert(it != addrToHandleMap_.end() && "Unknown address" ); |
181 | return it->second; |
182 | } |
183 | |
184 | bool MemoryAllocator::hasAddress(Handle handle) const { |
185 | auto it = handleToSegmentMap_.find(handle); |
186 | return it != handleToSegmentMap_.end(); |
187 | } |
188 | |
189 | const Segment &MemoryAllocator::getSegment(Handle handle) const { |
190 | auto it = handleToSegmentMap_.find(handle); |
191 | assert(it != handleToSegmentMap_.end() && "Unknown handle" ); |
192 | return it->second; |
193 | } |
194 | |
195 | uint64_t MemoryAllocator::getAddress(Handle handle) const { |
196 | return getSegment(handle).begin; |
197 | } |
198 | |
199 | uint64_t MemoryAllocator::getSize(Handle handle) const { |
200 | return getSegment(handle).size(); |
201 | } |
202 | |
203 | void MemoryAllocator::setHandle(uint64_t ptr, uint64_t size, Handle handle) { |
204 | // TODO: Check that ptr is an allocated address. |
205 | assert(contains(ptr) && "The address is not allocated" ); |
206 | assert(!hasHandle(ptr) && "The address has an associated handle already" ); |
207 | addrToHandleMap_[ptr] = handle; |
208 | handleToSegmentMap_.insert(std::make_pair(handle, Segment(ptr, ptr + size))); |
209 | } |
210 | |
211 | bool MemoryAllocator::verifyAllocations( |
212 | const std::list<Allocation> &allocList) const { |
213 | // Allocations length must be even. |
214 | if (allocList.size() % 2) { |
215 | return false; |
216 | } |
217 | // Number of ALLOC must be equal to number of FREE. |
218 | size_t numAlloc = 0; |
219 | for (const auto &alloc : allocList) { |
220 | if (alloc.alloc) { |
221 | numAlloc++; |
222 | } |
223 | } |
224 | if (numAlloc != (allocList.size() / 2)) { |
225 | return false; |
226 | } |
227 | // Verify each ALLOC has an associated FREE following it. |
228 | // Verify each ALLOC has a unique handle. |
229 | std::list<Handle> allocHandleList; |
230 | for (auto allocIt = allocList.begin(); allocIt != allocList.end(); |
231 | ++allocIt) { |
232 | if (!allocIt->alloc) { |
233 | continue; |
234 | } |
235 | // Find a FREE instruction associated to this ALLOC. |
236 | auto allocHandle = allocIt->handle; |
237 | bool freeFound = false; |
238 | for (auto it = allocIt; it != allocList.end(); ++it) { |
239 | if ((!it->alloc) && (it->handle == allocHandle)) { |
240 | freeFound = true; |
241 | break; |
242 | } |
243 | } |
244 | if (!freeFound) { |
245 | return false; |
246 | } |
247 | // Verify ALLOC handle is unique. |
248 | auto handleIt = |
249 | std::find(allocHandleList.begin(), allocHandleList.end(), allocHandle); |
250 | if (handleIt != allocHandleList.end()) { |
251 | return false; |
252 | } |
253 | allocHandleList.emplace_back(allocHandle); |
254 | } |
255 | return true; |
256 | } |
257 | |
258 | bool MemoryAllocator::verifySegments( |
259 | const std::list<Allocation> &allocList) const { |
260 | // Segments handles should match allocation handles. |
261 | // Segments sizes should match allocation sizes. |
262 | // Segments begin addresses must be aligned. |
263 | // Segments end addresses must not surpass the memory size. |
264 | for (const auto &alloc : allocList) { |
265 | if (!alloc.alloc) { |
266 | continue; |
267 | } |
268 | auto it = handleToSegmentMap_.find(alloc.handle); |
269 | if (it == handleToSegmentMap_.end()) { |
270 | return false; |
271 | } |
272 | Segment seg = it->second; |
273 | if (seg.size() != alloc.size) { |
274 | return false; |
275 | } |
276 | if (seg.begin % alignment_) { |
277 | return false; |
278 | } |
279 | if (memorySize_ && seg.end > memorySize_) { |
280 | return false; |
281 | } |
282 | } |
283 | // Allocations which are simultaneously alive must be assigned non-overlapping |
284 | // segments. |
285 | std::list<Handle> liveHandleList; |
286 | for (const auto &alloc : allocList) { |
287 | auto allocHandle = alloc.handle; |
288 | if (alloc.alloc) { |
289 | // Verify current segment is not overlapping with the other live segments. |
290 | auto it = handleToSegmentMap_.find(alloc.handle); |
291 | Segment seg = it->second; |
292 | for (const auto &liveHandle : liveHandleList) { |
293 | auto liveIt = handleToSegmentMap_.find(liveHandle); |
294 | Segment liveSeg = liveIt->second; |
295 | bool segOverlap = |
296 | intervalsOverlap(seg.begin, seg.end, liveSeg.begin, liveSeg.end); |
297 | if (segOverlap) { |
298 | return false; |
299 | } |
300 | } |
301 | // Add handle to live handles. |
302 | liveHandleList.emplace_back(allocHandle); |
303 | } else { |
304 | // Remove handle from live handles. |
305 | auto it = |
306 | std::find(liveHandleList.begin(), liveHandleList.end(), allocHandle); |
307 | assert(it != liveHandleList.end() && "Handle not found for removal!" ); |
308 | liveHandleList.erase(it); |
309 | } |
310 | } |
311 | assert(liveHandleList.empty() && "Inconsistent allocations!" ); |
312 | return true; |
313 | } |
314 | |
315 | /// Buffer information structure. |
316 | struct BuffInfo { |
317 | // Allocation size in bytes (requested size without alignment). |
318 | uint64_t allocSize; |
319 | // Buffer size in bytes (effective size with alignment). |
320 | uint64_t size; |
321 | // Allocation start time (inclusive) for this buffer. |
322 | uint64_t timeStart; |
323 | // Allocation stop time (inclusive) for this buffer. |
324 | uint64_t timeStop; |
325 | }; |
326 | |
327 | /// Liveness information structure for a given point in time. |
328 | struct LiveInfo { |
329 | // Total size for all the live buffers at this point in time. |
330 | uint64_t size; |
331 | // List of IDs of all the live buffers at this point in time. |
332 | std::list<uint64_t> idList; |
333 | }; |
334 | |
335 | /// Type definition for the function which defines the order used to allocate |
336 | /// the segments. Such a strategy is provided with the current buffer index |
337 | /// \p buffIdx, the buffer information \p buffInfoArray and liveness information |
338 | /// \p liveInfoArray. \returns the ID of the segment chosen for allocation. |
339 | using MemAllocStrategy = std::function<uint64_t( |
340 | size_t buffIdx, const std::vector<BuffInfo> &buffInfoArray, |
341 | const std::vector<LiveInfo> &liveInfoArray)>; |
342 | |
343 | /// Utility function to retrieve the list of IDs of all the buffers within the |
344 | /// live allocation with maximum size. We must take into account the corner case |
345 | /// when all the live allocations contain buffers with size 0. |
346 | const std::list<uint64_t> & |
347 | getMaxLiveSizeBuffIdList(const std::vector<LiveInfo> &liveInfoArray) { |
348 | size_t liveSizeMaxIdx = 0; |
349 | uint64_t liveSizeMax = 0; |
350 | for (size_t idx = 0, end = liveInfoArray.size(); idx < end; ++idx) { |
351 | const auto &liveInfo = liveInfoArray[idx]; |
352 | // Skip empty live allocations. |
353 | if (liveInfo.idList.empty()) { |
354 | continue; |
355 | } |
356 | // Find maximum live allocation size. If the maximum was not updated |
357 | // we update it regardless in case we have allocations of size 0. |
358 | if (liveInfo.size > liveSizeMax || liveSizeMax == 0) { |
359 | liveSizeMax = liveInfo.size; |
360 | liveSizeMaxIdx = idx; |
361 | } |
362 | } |
363 | return liveInfoArray[liveSizeMaxIdx].idList; |
364 | } |
365 | |
366 | /// Memory allocation strategy based on the following logic: |
367 | /// 1. Find maximum live size. |
368 | /// 2. Find buffer with maximum size. |
369 | /// 3. If multiple buffers with same size, find maximum live interval. |
370 | static uint64_t |
371 | MaxLiveSizeMaxBuffSize(size_t buffIdx, |
372 | const std::vector<BuffInfo> &buffInfoArray, |
373 | const std::vector<LiveInfo> &liveInfoArray) { |
374 | // Find maximum total live allocation. |
375 | const auto &liveBuffIdList = getMaxLiveSizeBuffIdList(liveInfoArray); |
376 | // Find buffer with maximum size within the maximum allocation. |
377 | assert(liveBuffIdList.size() && "Live buffer ID list is empty!" ); |
378 | uint64_t buffIdMax = liveBuffIdList.front(); |
379 | uint64_t buffSizeMax = buffInfoArray[buffIdMax].size; |
380 | for (auto buffIdIter : liveBuffIdList) { |
381 | auto buffSizeIter = buffInfoArray[buffIdIter].size; |
382 | // Choose buffer with maximum size. |
383 | if (buffSizeIter > buffSizeMax) { |
384 | buffSizeMax = buffSizeIter; |
385 | buffIdMax = buffIdIter; |
386 | } |
387 | // If size is the same choose buffer with maximum live interval. |
388 | if (buffSizeIter == buffSizeMax) { |
389 | auto currTime = buffInfoArray[buffIdMax].timeStop - |
390 | buffInfoArray[buffIdMax].timeStart; |
391 | auto iterTime = buffInfoArray[buffIdIter].timeStop - |
392 | buffInfoArray[buffIdIter].timeStart; |
393 | if (iterTime > currTime) { |
394 | buffIdMax = buffIdIter; |
395 | } |
396 | } |
397 | } |
398 | return buffIdMax; |
399 | } |
400 | |
401 | /// Memory allocation strategy based on the following logic: |
402 | /// 1. Find maximum live size. |
403 | /// 2. Find buffer with maximum live interval. |
404 | /// 3. If multiple buffers with same live interval, find maximum size. |
405 | static uint64_t |
406 | MaxLiveSizeMaxBuffTime(size_t buffIdx, |
407 | const std::vector<BuffInfo> &buffInfoArray, |
408 | const std::vector<LiveInfo> &liveInfoArray) { |
409 | // Find maximum total live allocation. |
410 | const auto &liveBuffIdList = getMaxLiveSizeBuffIdList(liveInfoArray); |
411 | // Find buffer with maximum live interval within the maximum allocation. |
412 | assert(liveBuffIdList.size() && "Live buffer ID list is empty!" ); |
413 | uint64_t buffIdMax = 0; |
414 | uint64_t buffTimeMax = 0; |
415 | for (auto buffIdIter : liveBuffIdList) { |
416 | auto buffTimeIter = buffInfoArray[buffIdIter].timeStop - |
417 | buffInfoArray[buffIdIter].timeStart; |
418 | // Choose buffer with maximum live interval. |
419 | if (buffTimeIter > buffTimeMax) { |
420 | buffTimeMax = buffTimeIter; |
421 | buffIdMax = buffIdIter; |
422 | } |
423 | // If live interval is the same choose buffer with maximum size. |
424 | if (buffTimeIter == buffTimeMax) { |
425 | auto currSize = buffInfoArray[buffIdMax].size; |
426 | auto iterSize = buffInfoArray[buffIdIter].size; |
427 | if (iterSize > currSize) { |
428 | buffIdMax = buffIdIter; |
429 | } |
430 | } |
431 | } |
432 | return buffIdMax; |
433 | } |
434 | |
435 | /// Memory allocation strategy which allocates the segments in the same order as |
436 | /// requested. |
437 | static uint64_t SameOrder(size_t buffIdx, |
438 | const std::vector<BuffInfo> &buffInfoArray, |
439 | const std::vector<LiveInfo> &liveInfoArray) { |
440 | return buffIdx; |
441 | } |
442 | |
443 | /// Array of available memory allocation strategies listed in the decreasing |
444 | /// order of the likelihood of getting the best allocation efficiency. All these |
445 | /// strategies are used one after the other in the exact order as listed here. |
446 | /// In case one such strategy provides the maximum efficiency (best theoretical |
447 | /// result) then the following ones (if any) are not used anymore. |
448 | static std::vector<MemAllocStrategy> memAllocStrategies = { |
449 | MaxLiveSizeMaxBuffSize, MaxLiveSizeMaxBuffTime, SameOrder}; |
450 | |
451 | /// Utility function to allocate all the segments at once using the given |
452 | /// \p strategy and the memory size \p memorySize. The buffer information |
453 | /// is incapsulated in the array \p buffInfoArray and the buffer liveness |
454 | /// information before the allocation is incapsulated in the input array |
455 | /// \p liveInfoArrayInit. At the end of the allocation the segments are |
456 | /// written in \p idSegMap which is a map between the allocation handles |
457 | /// and the associated segments. |
458 | static uint64_t allocateAllWithStrategy( |
459 | uint64_t memorySize, const std::vector<BuffInfo> &buffInfoArray, |
460 | const std::vector<LiveInfo> &liveInfoArrayInit, |
461 | std::unordered_map<size_t, Segment> &idSegMap, MemAllocStrategy strategy) { |
462 | |
463 | // Make local copy of the liveness information which is modified during |
464 | // the allocation algorithm. |
465 | auto liveInfoArray = liveInfoArrayInit; |
466 | |
467 | // The maximum total memory used for segment allocation. |
468 | uint64_t usedSizeMax = 0; |
469 | |
470 | // Allocate all buffers. |
471 | for (size_t buffIdx = 0; buffIdx < buffInfoArray.size(); buffIdx++) { |
472 | |
473 | // Choose buffer/segment to allocate based on strategy. |
474 | uint64_t currSegId = strategy(buffIdx, buffInfoArray, liveInfoArray); |
475 | |
476 | // Check that this segment was not previously allocated. |
477 | assert(idSegMap.find(currSegId) == idSegMap.end() && |
478 | "Segment previously allocated!" ); |
479 | |
480 | // ------------------------------------------------------------------------- |
481 | // Find previously allocated segments which overlap with the current segment |
482 | // in time, that is segments which are alive at the same time with the |
483 | // current segment. We keep only those segments and store them in buffers. |
484 | // We also sort the found segments in increasing order of the stop address. |
485 | // Note: The number of previous segments is usually small. |
486 | // ------------------------------------------------------------------------- |
487 | typedef std::pair<uint64_t, uint64_t> AddressPair; |
488 | |
489 | // We initialize the "previous segments" buffers with a virtual segment of |
490 | // size 0 since this will simplify the logic used in the following section. |
491 | std::vector<AddressPair> prevSegAddr = {AddressPair(0, 0)}; |
492 | for (const auto &idSeg : idSegMap) { |
493 | |
494 | // Previously allocated segment. |
495 | auto prevSegId = idSeg.first; |
496 | auto prevSeg = idSeg.second; |
497 | |
498 | // Verify if the previous segment overlaps with current segment in time. |
499 | bool overlap = intervalsOverlap(buffInfoArray[currSegId].timeStart, |
500 | buffInfoArray[currSegId].timeStop, |
501 | buffInfoArray[prevSegId].timeStart, |
502 | buffInfoArray[prevSegId].timeStop); |
503 | |
504 | // If segment overlaps with previous then store the previous segment. |
505 | if (overlap) { |
506 | prevSegAddr.emplace_back(prevSeg.begin, prevSeg.end); |
507 | } |
508 | } |
509 | |
510 | // Order segments in the increasing order of the stop address. |
511 | std::sort(prevSegAddr.begin(), prevSegAddr.end(), |
512 | [](const AddressPair &a, const AddressPair &b) { |
513 | return a.second < b.second; |
514 | }); |
515 | |
516 | // ------------------------------------------------------------------------- |
517 | // Find a position for the current segment by trying to allocate at the |
518 | // end of all the previously allocated segments which were previously |
519 | // found. Since the previous segments are ordered by their stop address |
520 | // in ascending order this procedure is guaranteed to find a place at |
521 | // least at the end of the last segment. |
522 | // ------------------------------------------------------------------------- |
523 | uint64_t currSegAddrStart = 0; |
524 | uint64_t currSegAddrStop = 0; |
525 | for (size_t prevSegIdx = 0; prevSegIdx < prevSegAddr.size(); prevSegIdx++) { |
526 | |
527 | // Try to place current segment after this previously allocated segment. |
528 | currSegAddrStart = prevSegAddr[prevSegIdx].second; |
529 | currSegAddrStop = currSegAddrStart + buffInfoArray[currSegId].size; |
530 | |
531 | // Verify if this placement overlaps with all the other segments. |
532 | // Note that this verification with all the previous segments is required |
533 | // because the previous segments can overlap between themselves. |
534 | bool overlap = false; |
535 | for (size_t ovrSegIdx = 0; ovrSegIdx < prevSegAddr.size(); ovrSegIdx++) { |
536 | // Check overlap. |
537 | overlap = overlap || intervalsOverlap(currSegAddrStart, currSegAddrStop, |
538 | prevSegAddr[ovrSegIdx].first, |
539 | prevSegAddr[ovrSegIdx].second); |
540 | // Early break if overlaps. |
541 | if (overlap) { |
542 | break; |
543 | } |
544 | } |
545 | |
546 | // If no overlap than we found the solution for the placement. |
547 | if (!overlap) { |
548 | break; |
549 | } |
550 | } |
551 | |
552 | // Update maximum used size. |
553 | usedSizeMax = std::max(usedSizeMax, currSegAddrStop); |
554 | |
555 | // If max available memory is surpassed with the new segment then we stop |
556 | // the allocation and return early. |
557 | if (usedSizeMax > memorySize) { |
558 | return MemoryAllocator::npos; |
559 | } |
560 | |
561 | // Allocate current segment. |
562 | Segment currSeg(currSegAddrStart, currSegAddrStop); |
563 | idSegMap.insert(std::make_pair(currSegId, currSeg)); |
564 | |
565 | // Update buffer liveness information. |
566 | for (size_t allocIdx = buffInfoArray[currSegId].timeStart; |
567 | allocIdx < buffInfoArray[currSegId].timeStop; allocIdx++) { |
568 | // Update total live size. |
569 | liveInfoArray[allocIdx].size -= buffInfoArray[currSegId].size; |
570 | // Update total live IDs. |
571 | auto &allocIds = liveInfoArray[allocIdx].idList; |
572 | auto it = std::find(allocIds.begin(), allocIds.end(), currSegId); |
573 | assert(it != allocIds.end() && "Buffer ID not found for removal!" ); |
574 | allocIds.erase(it); |
575 | } |
576 | } |
577 | |
578 | // Verify again that all the buffers were allocated. |
579 | for (size_t allocIdx = 0; allocIdx < liveInfoArray.size(); allocIdx++) { |
580 | assert(liveInfoArray[allocIdx].size == 0 && |
581 | "Not all buffers were allocated!" ); |
582 | assert(liveInfoArray[allocIdx].idList.empty() && |
583 | "Not all buffers were allocated!" ); |
584 | } |
585 | |
586 | return usedSizeMax; |
587 | } |
588 | |
589 | void MemoryAllocator::mapHandlesToIds( |
590 | const std::list<Allocation> &allocList, |
591 | std::unordered_map<Handle, size_t> &handleToIdMap, |
592 | std::vector<Handle> &idToHandleMap) { |
593 | size_t buffNum = allocList.size() / 2; |
594 | handleToIdMap.clear(); |
595 | idToHandleMap = std::vector<Handle>(buffNum); |
596 | size_t id = 0; |
597 | for (const auto &alloc : allocList) { |
598 | // We only map the Handles of ALLOCs. |
599 | if (alloc.alloc) { |
600 | handleToIdMap[alloc.handle] = id; |
601 | idToHandleMap[id] = alloc.handle; |
602 | id++; |
603 | } |
604 | } |
605 | assert(id == buffNum && "Inconsistent Handle to ID mapping!" ); |
606 | } |
607 | |
608 | uint64_t MemoryAllocator::allocateAll(const std::list<Allocation> &allocList, |
609 | bool reuseMemory) { |
610 | |
611 | // Verify allocations. |
612 | assert(verifyAllocations(allocList) && "Allocations are invalid!" ); |
613 | |
614 | // If allocation list is empty then return early. |
615 | size_t allocNum = allocList.size(); |
616 | if (allocNum == 0) { |
617 | return 0; |
618 | } |
619 | |
620 | // Number of buffers/segments to allocate. |
621 | assert((allocNum % 2 == 0) && |
622 | "The allocation list must have an even number of entries!" ); |
623 | size_t buffNum = allocNum / 2; |
624 | |
625 | // Effective memory size remaining for allocation taking into account the |
626 | // previously allocated segments. For this parameter a value of 0 means no |
627 | // remaining space while an infinite value is encoded as max(uint64). |
628 | uint64_t effectiveMemorySize = |
629 | memorySize_ ? memorySize_ : std::numeric_limits<uint64_t>::max(); |
630 | if (!reuseMemory) { |
631 | assert(effectiveMemorySize >= maxUsedSize_ && "Memory size invalid!" ); |
632 | effectiveMemorySize -= maxUsedSize_; |
633 | } |
634 | |
635 | // Map Handles to consecutive unique IDs between 0 and numBuff - 1 since this |
636 | // makes the algorithm implementation easier/faster by using IDs as vector |
637 | // indices. |
638 | std::unordered_map<Handle, size_t> handleToIdMap; |
639 | std::vector<Handle> idToHandleMap; |
640 | mapHandlesToIds(allocList, handleToIdMap, idToHandleMap); |
641 | |
642 | // ----------------------------------------------------------------------- |
643 | // Get overall information about all the buffers. |
644 | // ----------------------------------------------------------------------- |
645 | // Buffer information. |
646 | std::vector<BuffInfo> buffInfoArray(buffNum); |
647 | |
648 | // The maximum total required memory of all the live buffers reached during |
649 | // all allocation time steps. Note that this is the best size any allocation |
650 | // algorithm can hope for and is used to compute the allocation efficiency. |
651 | uint64_t liveSizeMax = 0; |
652 | |
653 | // Liveness information for each allocation time step. |
654 | std::vector<LiveInfo> liveInfoArray(allocNum); |
655 | |
656 | // Gather information. |
657 | { |
658 | uint64_t allocIdx = 0; |
659 | uint64_t liveBuffSize = 0; |
660 | std::list<uint64_t> liveBuffIdList; |
661 | for (const auto &alloc : allocList) { |
662 | |
663 | // Current buffer handle and mapped ID. |
664 | auto buffHandle = alloc.handle; |
665 | auto buffId = handleToIdMap[buffHandle]; |
666 | |
667 | // Current buffer size. We only use the buffer size of an ALLOC request. |
668 | // For a FREE request we use the buffer size of the associated ALLOC. |
669 | // We round the requested buffer size using the alignment. |
670 | uint64_t buffSize; |
671 | if (alloc.alloc) { |
672 | buffSize = getEffectiveSize(alloc.size); |
673 | } else { |
674 | buffSize = buffInfoArray[buffId].size; |
675 | } |
676 | |
677 | // Update buffer information. |
678 | if (alloc.alloc) { |
679 | buffInfoArray[buffId].allocSize = alloc.size; |
680 | buffInfoArray[buffId].size = buffSize; |
681 | buffInfoArray[buffId].timeStart = allocIdx; |
682 | } else { |
683 | buffInfoArray[buffId].timeStop = allocIdx; |
684 | } |
685 | |
686 | // Update liveness information. |
687 | if (alloc.alloc) { |
688 | liveBuffSize = liveBuffSize + buffSize; |
689 | liveBuffIdList.emplace_back(buffId); |
690 | } else { |
691 | liveBuffSize = liveBuffSize - buffSize; |
692 | auto it = |
693 | std::find(liveBuffIdList.begin(), liveBuffIdList.end(), buffId); |
694 | assert(it != liveBuffIdList.end() && |
695 | "Buffer ID not found for removal!" ); |
696 | liveBuffIdList.erase(it); |
697 | } |
698 | liveSizeMax = std::max(liveSizeMax, liveBuffSize); |
699 | liveInfoArray[allocIdx].size = liveBuffSize; |
700 | liveInfoArray[allocIdx].idList = liveBuffIdList; |
701 | allocIdx++; |
702 | } |
703 | assert(liveBuffSize == 0 && |
704 | "Mismatch between total allocated and deallocated size!" ); |
705 | assert(liveBuffIdList.empty() && |
706 | "Mismatch between total allocated and deallocated buffers!" ); |
707 | } |
708 | |
709 | // If the theoretical required memory is larger than the available memory size |
710 | // then we return early. |
711 | if (liveSizeMax > effectiveMemorySize) { |
712 | return MemoryAllocator::npos; |
713 | } |
714 | |
715 | // --------------------------------------------------------------------------- |
716 | // Allocate all the buffers using all the available strategies. |
717 | // --------------------------------------------------------------------------- |
718 | // Map between allocated IDs and segments for optimal strategy. |
719 | std::unordered_map<size_t, Segment> idSegMap; |
720 | |
721 | // The maximum total memory used for segment allocation for optimal strategy. |
722 | uint64_t usedSizeMax = std::numeric_limits<uint64_t>::max(); |
723 | |
724 | // Iterate all the available strategies and pick the optimal one. |
725 | size_t strategyNum = memAllocStrategies.size(); |
726 | for (size_t strategyIdx = 0; strategyIdx < strategyNum; strategyIdx++) { |
727 | |
728 | // Allocate segments using current strategy. |
729 | std::unordered_map<size_t, Segment> idSegMapTemp; |
730 | auto strategy = memAllocStrategies[strategyIdx]; |
731 | uint64_t usedSize = |
732 | allocateAllWithStrategy(effectiveMemorySize, buffInfoArray, |
733 | liveInfoArray, idSegMapTemp, strategy); |
734 | |
735 | // If available memory is exceeded then we return early. |
736 | if (usedSize == MemoryAllocator::npos) { |
737 | return MemoryAllocator::npos; |
738 | } |
739 | |
740 | // If maximum efficiency is reached we update and break early. |
741 | if (usedSize == liveSizeMax) { |
742 | usedSizeMax = usedSize; |
743 | idSegMap = idSegMapTemp; |
744 | break; |
745 | } |
746 | |
747 | // If new optimal is obtained we update. |
748 | if (usedSize < usedSizeMax) { |
749 | usedSizeMax = usedSize; |
750 | idSegMap = idSegMapTemp; |
751 | } |
752 | } |
753 | |
754 | // Update the segments, handles and the max used/live memory. |
755 | assert(idSegMap.size() == (allocList.size() / 2) && "Segments are invalid!" ); |
756 | for (const auto &idSeg : idSegMap) { |
757 | size_t id = idSeg.first; |
758 | Segment segment = idSeg.second; |
759 | // Since the segment allocation was done using the aligned size, we restore |
760 | // the segment size to the value of the original allocation size. |
761 | segment.end = segment.begin + buffInfoArray[id].allocSize; |
762 | // When memory is not reused we adjust the segment position based on the |
763 | // previous memory usage. |
764 | if (!reuseMemory) { |
765 | segment.begin += maxUsedSize_; |
766 | segment.end += maxUsedSize_; |
767 | } |
768 | Handle handle = idToHandleMap[id]; |
769 | segments_.emplace_back(segment); |
770 | handleToSegmentMap_.insert(std::make_pair(handle, segment)); |
771 | addrToHandleMap_[segment.begin] = handle; |
772 | } |
773 | if (reuseMemory) { |
774 | maxUsedSize_ = std::max(maxUsedSize_, usedSizeMax); |
775 | maxLiveSize_ = std::max(maxLiveSize_, liveSizeMax); |
776 | } else { |
777 | maxUsedSize_ = maxUsedSize_ + usedSizeMax; |
778 | maxLiveSize_ = maxLiveSize_ + liveSizeMax; |
779 | } |
780 | liveSize_ = 0; |
781 | |
782 | // Verify segments. |
783 | assert(verifySegments(allocList) && "Segments are invalid!" ); |
784 | |
785 | return maxUsedSize_; |
786 | } |
787 | |