1 /* Distributed under the OSI-approved BSD 3-Clause License. See accompanying
2 file Copyright.txt or https://cmake.org/licensing for details. */
3 #include "cmCTestBinPacker.h"
4
5 #include <algorithm>
6 #include <utility>
7
operator ==(const cmCTestBinPackerAllocation & other) const8 bool cmCTestBinPackerAllocation::operator==(
9 const cmCTestBinPackerAllocation& other) const
10 {
11 return this->ProcessIndex == other.ProcessIndex &&
12 this->SlotsNeeded == other.SlotsNeeded && this->Id == other.Id;
13 }
14
operator !=(const cmCTestBinPackerAllocation & other) const15 bool cmCTestBinPackerAllocation::operator!=(
16 const cmCTestBinPackerAllocation& other) const
17 {
18 return !(*this == other);
19 }
20
21 namespace {
22
23 /*
24 * The following algorithm is used to do two things:
25 *
26 * 1) Determine if a test's resource requirements can fit within the resources
27 * present on the system, and
28 * 2) Do the actual allocation
29 *
30 * This algorithm performs a recursive search, looking for a bin pack that will
31 * fit the specified requirements. It has a template to specify different
32 * optimization strategies. If it ever runs out of room, it backtracks as far
33 * down the stack as it needs to and tries a different combination until no
34 * more combinations can be tried.
35 */
36 template <typename AllocationStrategy>
AllocateCTestResources(const std::map<std::string,cmCTestResourceAllocator::Resource> & resources,const std::vector<std::string> & resourcesSorted,std::size_t currentIndex,std::vector<cmCTestBinPackerAllocation * > & allocations)37 static bool AllocateCTestResources(
38 const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
39 const std::vector<std::string>& resourcesSorted, std::size_t currentIndex,
40 std::vector<cmCTestBinPackerAllocation*>& allocations)
41 {
42 // Iterate through all large enough resources until we find a solution
43 std::size_t resourceIndex = 0;
44 while (resourceIndex < resourcesSorted.size()) {
45 auto const& resource = resources.at(resourcesSorted[resourceIndex]);
46 if (resource.Free() >=
47 static_cast<unsigned int>(allocations[currentIndex]->SlotsNeeded)) {
48 // Preemptively allocate the resource
49 allocations[currentIndex]->Id = resourcesSorted[resourceIndex];
50 if (currentIndex + 1 >= allocations.size()) {
51 // We have a solution
52 return true;
53 }
54
55 // Move the resource up the list until it is sorted again
56 auto resources2 = resources;
57 auto resourcesSorted2 = resourcesSorted;
58 resources2[resourcesSorted2[resourceIndex]].Locked +=
59 allocations[currentIndex]->SlotsNeeded;
60 AllocationStrategy::IncrementalSort(resources2, resourcesSorted2,
61 resourceIndex);
62
63 // Recurse one level deeper
64 if (AllocateCTestResources<AllocationStrategy>(
65 resources2, resourcesSorted2, currentIndex + 1, allocations)) {
66 return true;
67 }
68 }
69
70 // No solution found here, deallocate the resource and try the next one
71 allocations[currentIndex]->Id.clear();
72 auto freeSlots = resources.at(resourcesSorted.at(resourceIndex)).Free();
73 do {
74 ++resourceIndex;
75 } while (resourceIndex < resourcesSorted.size() &&
76 resources.at(resourcesSorted.at(resourceIndex)).Free() ==
77 freeSlots);
78 }
79
80 // No solution was found
81 return false;
82 }
83
84 template <typename AllocationStrategy>
AllocateCTestResources(const std::map<std::string,cmCTestResourceAllocator::Resource> & resources,std::vector<cmCTestBinPackerAllocation> & allocations)85 static bool AllocateCTestResources(
86 const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
87 std::vector<cmCTestBinPackerAllocation>& allocations)
88 {
89 // Sort the resource requirements in descending order by slots needed
90 std::vector<cmCTestBinPackerAllocation*> allocationsPtr;
91 allocationsPtr.reserve(allocations.size());
92 for (auto& allocation : allocations) {
93 allocationsPtr.push_back(&allocation);
94 }
95 std::stable_sort(
96 allocationsPtr.rbegin(), allocationsPtr.rend(),
97 [](cmCTestBinPackerAllocation* a1, cmCTestBinPackerAllocation* a2) {
98 return a1->SlotsNeeded < a2->SlotsNeeded;
99 });
100
101 // Sort the resources according to sort strategy
102 std::vector<std::string> resourcesSorted;
103 resourcesSorted.reserve(resources.size());
104 for (auto const& res : resources) {
105 resourcesSorted.push_back(res.first);
106 }
107 AllocationStrategy::InitialSort(resources, resourcesSorted);
108
109 // Do the actual allocation
110 return AllocateCTestResources<AllocationStrategy>(
111 resources, resourcesSorted, std::size_t(0), allocationsPtr);
112 }
113
114 class RoundRobinAllocationStrategy
115 {
116 public:
117 static void InitialSort(
118 const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
119 std::vector<std::string>& resourcesSorted);
120
121 static void IncrementalSort(
122 const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
123 std::vector<std::string>& resourcesSorted, std::size_t lastAllocatedIndex);
124 };
125
InitialSort(const std::map<std::string,cmCTestResourceAllocator::Resource> & resources,std::vector<std::string> & resourcesSorted)126 void RoundRobinAllocationStrategy::InitialSort(
127 const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
128 std::vector<std::string>& resourcesSorted)
129 {
130 std::stable_sort(
131 resourcesSorted.rbegin(), resourcesSorted.rend(),
132 [&resources](const std::string& id1, const std::string& id2) {
133 return resources.at(id1).Free() < resources.at(id2).Free();
134 });
135 }
136
IncrementalSort(const std::map<std::string,cmCTestResourceAllocator::Resource> & resources,std::vector<std::string> & resourcesSorted,std::size_t lastAllocatedIndex)137 void RoundRobinAllocationStrategy::IncrementalSort(
138 const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
139 std::vector<std::string>& resourcesSorted, std::size_t lastAllocatedIndex)
140 {
141 auto tmp = resourcesSorted[lastAllocatedIndex];
142 std::size_t i = lastAllocatedIndex;
143 while (i < resourcesSorted.size() - 1 &&
144 resources.at(resourcesSorted[i + 1]).Free() >
145 resources.at(tmp).Free()) {
146 resourcesSorted[i] = resourcesSorted[i + 1];
147 ++i;
148 }
149 resourcesSorted[i] = tmp;
150 }
151
152 class BlockAllocationStrategy
153 {
154 public:
155 static void InitialSort(
156 const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
157 std::vector<std::string>& resourcesSorted);
158
159 static void IncrementalSort(
160 const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
161 std::vector<std::string>& resourcesSorted, std::size_t lastAllocatedIndex);
162 };
163
InitialSort(const std::map<std::string,cmCTestResourceAllocator::Resource> & resources,std::vector<std::string> & resourcesSorted)164 void BlockAllocationStrategy::InitialSort(
165 const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
166 std::vector<std::string>& resourcesSorted)
167 {
168 std::stable_sort(
169 resourcesSorted.rbegin(), resourcesSorted.rend(),
170 [&resources](const std::string& id1, const std::string& id2) {
171 return resources.at(id1).Free() < resources.at(id2).Free();
172 });
173 }
174
IncrementalSort(const std::map<std::string,cmCTestResourceAllocator::Resource> &,std::vector<std::string> & resourcesSorted,std::size_t lastAllocatedIndex)175 void BlockAllocationStrategy::IncrementalSort(
176 const std::map<std::string, cmCTestResourceAllocator::Resource>&,
177 std::vector<std::string>& resourcesSorted, std::size_t lastAllocatedIndex)
178 {
179 auto tmp = resourcesSorted[lastAllocatedIndex];
180 std::size_t i = lastAllocatedIndex;
181 while (i > 0) {
182 resourcesSorted[i] = resourcesSorted[i - 1];
183 --i;
184 }
185 resourcesSorted[i] = tmp;
186 }
187 }
188
cmAllocateCTestResourcesRoundRobin(const std::map<std::string,cmCTestResourceAllocator::Resource> & resources,std::vector<cmCTestBinPackerAllocation> & allocations)189 bool cmAllocateCTestResourcesRoundRobin(
190 const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
191 std::vector<cmCTestBinPackerAllocation>& allocations)
192 {
193 return AllocateCTestResources<RoundRobinAllocationStrategy>(resources,
194 allocations);
195 }
196
cmAllocateCTestResourcesBlock(const std::map<std::string,cmCTestResourceAllocator::Resource> & resources,std::vector<cmCTestBinPackerAllocation> & allocations)197 bool cmAllocateCTestResourcesBlock(
198 const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
199 std::vector<cmCTestBinPackerAllocation>& allocations)
200 {
201 return AllocateCTestResources<BlockAllocationStrategy>(resources,
202 allocations);
203 }
204