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
27using namespace glow;
28
29namespace glow {
30class Value;
31}
32
33/// The type of the address returned by MemoryAllocator::allocate should be at
34/// least 64-bit wide.
35static_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
40static_assert(std::is_unsigned<decltype(MemoryAllocator::npos)>{},
41 "Allocated addresses should be unsigned integers");
42
43const uint64_t MemoryAllocator::npos = -1;
44
45float 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
53uint64_t MemoryAllocator::getEffectiveSize(uint64_t size) const {
54 return alignedSize(size, alignment_);
55}
56
57uint64_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
91void 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
141uint64_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
158void 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
173bool MemoryAllocator::hasHandle(uint64_t address) const {
174 auto it = addrToHandleMap_.find(address);
175 return it != addrToHandleMap_.end();
176}
177
178MemoryAllocator::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
184bool MemoryAllocator::hasAddress(Handle handle) const {
185 auto it = handleToSegmentMap_.find(handle);
186 return it != handleToSegmentMap_.end();
187}
188
189const 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
195uint64_t MemoryAllocator::getAddress(Handle handle) const {
196 return getSegment(handle).begin;
197}
198
199uint64_t MemoryAllocator::getSize(Handle handle) const {
200 return getSegment(handle).size();
201}
202
203void 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
211bool 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
258bool 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.
316struct 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.
328struct 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.
339using 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.
346const std::list<uint64_t> &
347getMaxLiveSizeBuffIdList(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.
370static uint64_t
371MaxLiveSizeMaxBuffSize(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.
405static uint64_t
406MaxLiveSizeMaxBuffTime(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.
437static 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.
448static 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.
458static 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
589void 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
608uint64_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