/* Distributed under the OSI-approved BSD 3-Clause License. See accompanying file Copyright.txt or https://cmake.org/licensing for details. */ #include "cmCTestBinPacker.h" #include <algorithm> #include <utility> bool cmCTestBinPackerAllocation::operator==( const cmCTestBinPackerAllocation& other) const { return this->ProcessIndex == other.ProcessIndex && this->SlotsNeeded == other.SlotsNeeded && this->Id == other.Id; } bool cmCTestBinPackerAllocation::operator!=( const cmCTestBinPackerAllocation& other) const { return !(*this == other); } namespace { /* * The following algorithm is used to do two things: * * 1) Determine if a test's resource requirements can fit within the resources * present on the system, and * 2) Do the actual allocation * * This algorithm performs a recursive search, looking for a bin pack that will * fit the specified requirements. It has a template to specify different * optimization strategies. If it ever runs out of room, it backtracks as far * down the stack as it needs to and tries a different combination until no * more combinations can be tried. */ template <typename AllocationStrategy> static bool AllocateCTestResources( const std::map<std::string, cmCTestResourceAllocator::Resource>& resources, const std::vector<std::string>& resourcesSorted, std::size_t currentIndex, std::vector<cmCTestBinPackerAllocation*>& allocations) { // Iterate through all large enough resources until we find a solution std::size_t resourceIndex = 0; while (resourceIndex < resourcesSorted.size()) { auto const& resource = resources.at(resourcesSorted[resourceIndex]); if (resource.Free() >= static_cast<unsigned int>(allocations[currentIndex]->SlotsNeeded)) { // Preemptively allocate the resource allocations[currentIndex]->Id = resourcesSorted[resourceIndex]; if (currentIndex + 1 >= allocations.size()) { // We have a solution return true; } // Move the resource up the list until it is sorted again auto resources2 = resources; auto resourcesSorted2 = resourcesSorted; resources2[resourcesSorted2[resourceIndex]].Locked += allocations[currentIndex]->SlotsNeeded; AllocationStrategy::IncrementalSort(resources2, resourcesSorted2, resourceIndex); // Recurse one level deeper if (AllocateCTestResources<AllocationStrategy>( resources2, resourcesSorted2, currentIndex + 1, allocations)) { return true; } } // No solution found here, deallocate the resource and try the next one allocations[currentIndex]->Id.clear(); auto freeSlots = resources.at(resourcesSorted.at(resourceIndex)).Free(); do { ++resourceIndex; } while (resourceIndex < resourcesSorted.size() && resources.at(resourcesSorted.at(resourceIndex)).Free() == freeSlots); } // No solution was found return false; } template <typename AllocationStrategy> static bool AllocateCTestResources( const std::map<std::string, cmCTestResourceAllocator::Resource>& resources, std::vector<cmCTestBinPackerAllocation>& allocations) { // Sort the resource requirements in descending order by slots needed std::vector<cmCTestBinPackerAllocation*> allocationsPtr; allocationsPtr.reserve(allocations.size()); for (auto& allocation : allocations) { allocationsPtr.push_back(&allocation); } std::stable_sort( allocationsPtr.rbegin(), allocationsPtr.rend(), [](cmCTestBinPackerAllocation* a1, cmCTestBinPackerAllocation* a2) { return a1->SlotsNeeded < a2->SlotsNeeded; }); // Sort the resources according to sort strategy std::vector<std::string> resourcesSorted; resourcesSorted.reserve(resources.size()); for (auto const& res : resources) { resourcesSorted.push_back(res.first); } AllocationStrategy::InitialSort(resources, resourcesSorted); // Do the actual allocation return AllocateCTestResources<AllocationStrategy>( resources, resourcesSorted, std::size_t(0), allocationsPtr); } class RoundRobinAllocationStrategy { public: static void InitialSort( const std::map<std::string, cmCTestResourceAllocator::Resource>& resources, std::vector<std::string>& resourcesSorted); static void IncrementalSort( const std::map<std::string, cmCTestResourceAllocator::Resource>& resources, std::vector<std::string>& resourcesSorted, std::size_t lastAllocatedIndex); }; void RoundRobinAllocationStrategy::InitialSort( const std::map<std::string, cmCTestResourceAllocator::Resource>& resources, std::vector<std::string>& resourcesSorted) { std::stable_sort( resourcesSorted.rbegin(), resourcesSorted.rend(), [&resources](const std::string& id1, const std::string& id2) { return resources.at(id1).Free() < resources.at(id2).Free(); }); } void RoundRobinAllocationStrategy::IncrementalSort( const std::map<std::string, cmCTestResourceAllocator::Resource>& resources, std::vector<std::string>& resourcesSorted, std::size_t lastAllocatedIndex) { auto tmp = resourcesSorted[lastAllocatedIndex]; std::size_t i = lastAllocatedIndex; while (i < resourcesSorted.size() - 1 && resources.at(resourcesSorted[i + 1]).Free() > resources.at(tmp).Free()) { resourcesSorted[i] = resourcesSorted[i + 1]; ++i; } resourcesSorted[i] = tmp; } class BlockAllocationStrategy { public: static void InitialSort( const std::map<std::string, cmCTestResourceAllocator::Resource>& resources, std::vector<std::string>& resourcesSorted); static void IncrementalSort( const std::map<std::string, cmCTestResourceAllocator::Resource>& resources, std::vector<std::string>& resourcesSorted, std::size_t lastAllocatedIndex); }; void BlockAllocationStrategy::InitialSort( const std::map<std::string, cmCTestResourceAllocator::Resource>& resources, std::vector<std::string>& resourcesSorted) { std::stable_sort( resourcesSorted.rbegin(), resourcesSorted.rend(), [&resources](const std::string& id1, const std::string& id2) { return resources.at(id1).Free() < resources.at(id2).Free(); }); } void BlockAllocationStrategy::IncrementalSort( const std::map<std::string, cmCTestResourceAllocator::Resource>&, std::vector<std::string>& resourcesSorted, std::size_t lastAllocatedIndex) { auto tmp = resourcesSorted[lastAllocatedIndex]; std::size_t i = lastAllocatedIndex; while (i > 0) { resourcesSorted[i] = resourcesSorted[i - 1]; --i; } resourcesSorted[i] = tmp; } } bool cmAllocateCTestResourcesRoundRobin( const std::map<std::string, cmCTestResourceAllocator::Resource>& resources, std::vector<cmCTestBinPackerAllocation>& allocations) { return AllocateCTestResources<RoundRobinAllocationStrategy>(resources, allocations); } bool cmAllocateCTestResourcesBlock( const std::map<std::string, cmCTestResourceAllocator::Resource>& resources, std::vector<cmCTestBinPackerAllocation>& allocations) { return AllocateCTestResources<BlockAllocationStrategy>(resources, allocations); }