diff options
| -rw-r--r-- | Source/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | Source/CTest/cmCTestBinPacker.cxx | 201 | ||||
| -rw-r--r-- | Source/CTest/cmCTestBinPacker.h | 31 | ||||
| -rw-r--r-- | Tests/CMakeLib/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | Tests/CMakeLib/testCTestBinPacker.cxx | 300 |
5 files changed, 534 insertions, 0 deletions
diff --git a/Source/CMakeLists.txt b/Source/CMakeLists.txt index 57229db..63e08de 100644 --- a/Source/CMakeLists.txt +++ b/Source/CMakeLists.txt @@ -899,6 +899,7 @@ include_directories( # set(CTEST_SRCS cmCTest.cxx CTest/cmProcess.cxx + CTest/cmCTestBinPacker.cxx CTest/cmCTestBuildAndTestHandler.cxx CTest/cmCTestBuildCommand.cxx CTest/cmCTestBuildHandler.cxx diff --git a/Source/CTest/cmCTestBinPacker.cxx b/Source/CTest/cmCTestBinPacker.cxx new file mode 100644 index 0000000..e9e3bee --- /dev/null +++ b/Source/CTest/cmCTestBinPacker.cxx @@ -0,0 +1,201 @@ +/* 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 hardware requirements can fit within the hardware + * 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 AllocateCTestHardware( + const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware, + const std::vector<std::string>& hardwareSorted, std::size_t currentIndex, + std::vector<cmCTestBinPackerAllocation*>& allocations) +{ + // Iterate through all large enough resources until we find a solution + std::size_t hardwareIndex = 0; + while (hardwareIndex < hardwareSorted.size()) { + auto const& resource = hardware.at(hardwareSorted[hardwareIndex]); + if (resource.Free() >= + static_cast<unsigned int>(allocations[currentIndex]->SlotsNeeded)) { + // Preemptively allocate the resource + allocations[currentIndex]->Id = hardwareSorted[hardwareIndex]; + if (currentIndex + 1 >= allocations.size()) { + // We have a solution + return true; + } + + // Move the resource up the list until it is sorted again + auto hardware2 = hardware; + auto hardwareSorted2 = hardwareSorted; + hardware2[hardwareSorted2[hardwareIndex]].Locked += + allocations[currentIndex]->SlotsNeeded; + AllocationStrategy::IncrementalSort(hardware2, hardwareSorted2, + hardwareIndex); + + // Recurse one level deeper + if (AllocateCTestHardware<AllocationStrategy>( + hardware2, hardwareSorted2, currentIndex + 1, allocations)) { + return true; + } + } + + // No solution found here, deallocate the resource and try the next one + allocations[currentIndex]->Id.clear(); + auto freeSlots = hardware.at(hardwareSorted.at(hardwareIndex)).Free(); + do { + ++hardwareIndex; + } while (hardwareIndex < hardwareSorted.size() && + hardware.at(hardwareSorted.at(hardwareIndex)).Free() == + freeSlots); + } + + // No solution was found + return false; +} + +template <typename AllocationStrategy> +static bool AllocateCTestHardware( + const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware, + 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> hardwareSorted; + hardwareSorted.reserve(hardware.size()); + for (auto const& hw : hardware) { + hardwareSorted.push_back(hw.first); + } + AllocationStrategy::InitialSort(hardware, hardwareSorted); + + // Do the actual allocation + return AllocateCTestHardware<AllocationStrategy>( + hardware, hardwareSorted, std::size_t(0), allocationsPtr); +} + +class RoundRobinAllocationStrategy +{ +public: + static void InitialSort( + const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware, + std::vector<std::string>& hardwareSorted); + + static void IncrementalSort( + const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware, + std::vector<std::string>& hardwareSorted, std::size_t lastAllocatedIndex); +}; + +void RoundRobinAllocationStrategy::InitialSort( + const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware, + std::vector<std::string>& hardwareSorted) +{ + std::stable_sort( + hardwareSorted.rbegin(), hardwareSorted.rend(), + [&hardware](const std::string& id1, const std::string& id2) { + return hardware.at(id1).Free() < hardware.at(id2).Free(); + }); +} + +void RoundRobinAllocationStrategy::IncrementalSort( + const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware, + std::vector<std::string>& hardwareSorted, std::size_t lastAllocatedIndex) +{ + auto tmp = hardwareSorted[lastAllocatedIndex]; + std::size_t i = lastAllocatedIndex; + while (i < hardwareSorted.size() - 1 && + hardware.at(hardwareSorted[i + 1]).Free() > hardware.at(tmp).Free()) { + hardwareSorted[i] = hardwareSorted[i + 1]; + ++i; + } + hardwareSorted[i] = tmp; +} + +class BlockAllocationStrategy +{ +public: + static void InitialSort( + const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware, + std::vector<std::string>& hardwareSorted); + + static void IncrementalSort( + const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware, + std::vector<std::string>& hardwareSorted, std::size_t lastAllocatedIndex); +}; + +void BlockAllocationStrategy::InitialSort( + const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware, + std::vector<std::string>& hardwareSorted) +{ + std::stable_sort( + hardwareSorted.rbegin(), hardwareSorted.rend(), + [&hardware](const std::string& id1, const std::string& id2) { + return hardware.at(id1).Free() < hardware.at(id2).Free(); + }); +} + +void BlockAllocationStrategy::IncrementalSort( + const std::map<std::string, cmCTestHardwareAllocator::Resource>&, + std::vector<std::string>& hardwareSorted, std::size_t lastAllocatedIndex) +{ + auto tmp = hardwareSorted[lastAllocatedIndex]; + std::size_t i = lastAllocatedIndex; + while (i > 0) { + hardwareSorted[i] = hardwareSorted[i - 1]; + --i; + } + hardwareSorted[i] = tmp; +} +} + +bool cmAllocateCTestHardwareRoundRobin( + const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware, + std::vector<cmCTestBinPackerAllocation>& allocations) +{ + return AllocateCTestHardware<RoundRobinAllocationStrategy>(hardware, + allocations); +} + +bool cmAllocateCTestHardwareBlock( + const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware, + std::vector<cmCTestBinPackerAllocation>& allocations) +{ + return AllocateCTestHardware<BlockAllocationStrategy>(hardware, allocations); +} diff --git a/Source/CTest/cmCTestBinPacker.h b/Source/CTest/cmCTestBinPacker.h new file mode 100644 index 0000000..54f03d7 --- /dev/null +++ b/Source/CTest/cmCTestBinPacker.h @@ -0,0 +1,31 @@ +/* Distributed under the OSI-approved BSD 3-Clause License. See accompanying + file Copyright.txt or https://cmake.org/licensing for details. */ +#ifndef cmCTestBinPacker_h +#define cmCTestBinPacker_h + +#include <cstddef> +#include <map> +#include <string> +#include <vector> + +#include "cmCTestHardwareAllocator.h" + +struct cmCTestBinPackerAllocation +{ + std::size_t ProcessIndex; + int SlotsNeeded; + std::string Id; + + bool operator==(const cmCTestBinPackerAllocation& other) const; + bool operator!=(const cmCTestBinPackerAllocation& other) const; +}; + +bool cmAllocateCTestHardwareRoundRobin( + const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware, + std::vector<cmCTestBinPackerAllocation>& allocations); + +bool cmAllocateCTestHardwareBlock( + const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware, + std::vector<cmCTestBinPackerAllocation>& allocations); + +#endif diff --git a/Tests/CMakeLib/CMakeLists.txt b/Tests/CMakeLib/CMakeLists.txt index c24b64c..bc2079f 100644 --- a/Tests/CMakeLib/CMakeLists.txt +++ b/Tests/CMakeLib/CMakeLists.txt @@ -7,6 +7,7 @@ include_directories( set(CMakeLib_TESTS testArgumentParser.cxx + testCTestBinPacker.cxx testCTestProcesses.cxx testCTestHardwareAllocator.cxx testCTestHardwareSpec.cxx diff --git a/Tests/CMakeLib/testCTestBinPacker.cxx b/Tests/CMakeLib/testCTestBinPacker.cxx new file mode 100644 index 0000000..62ea55b --- /dev/null +++ b/Tests/CMakeLib/testCTestBinPacker.cxx @@ -0,0 +1,300 @@ +#include <cstddef> +#include <iostream> +#include <map> +#include <string> +#include <vector> + +#include "cmCTestBinPacker.h" +#include "cmCTestHardwareAllocator.h" + +struct ExpectedPackResult +{ + std::vector<int> SlotsNeeded; + std::map<std::string, cmCTestHardwareAllocator::Resource> Hardware; + bool ExpectedReturnValue; + std::vector<cmCTestBinPackerAllocation> ExpectedRoundRobinAllocations; + std::vector<cmCTestBinPackerAllocation> ExpectedBlockAllocations; +}; + +static const std::vector<ExpectedPackResult> expectedResults +{ + /* clang-format off */ + { + { 2, 2, 2, 2 }, + { { "0", { 4, 0 } }, { "1", { 4, 0 } }, { "2", { 4, 0 } }, + { "3", { 4, 0 } } }, + true, + { + { 0, 2, "0" }, + { 1, 2, "1" }, + { 2, 2, "2" }, + { 3, 2, "3" }, + }, + { + { 0, 2, "0" }, + { 1, 2, "0" }, + { 2, 2, "1" }, + { 3, 2, "1" }, + }, + }, + { + { 2, 3, 2 }, + { { "0", { 5, 0 } }, { "1", { 2, 0 } } }, + true, + { + { 0, 2, "0" }, + { 1, 3, "0" }, + { 2, 2, "1" }, + }, + { + { 0, 2, "0" }, + { 1, 3, "0" }, + { 2, 2, "1" }, + }, + }, + { + { 1, 2, 3 }, + { { "0", { 1, 0 } }, { "1", { 2, 0 } }, { "2", { 2, 0 } } }, + false, + { }, + { }, + }, + { + { 48, 21, 31, 10, 40 }, + { { "0", { 81, 0 } }, { "1", { 68, 0 } }, { "2", { 20, 0 } }, + { "3", { 13, 0 } } }, + true, + { + { 0, 48, "0" }, + { 1, 21, "1" }, + { 2, 31, "0" }, + { 3, 10, "2" }, + { 4, 40, "1" }, + }, + { + { 0, 48, "0" }, + { 1, 21, "1" }, + { 2, 31, "0" }, + { 3, 10, "2" }, + { 4, 40, "1" }, + }, + }, + { + { 30, 31, 39, 67 }, + { { "0", { 16, 0 } }, { "1", { 81, 0 } }, { "2", { 97, 0 } } }, + true, + { + { 0, 30, "2" }, + { 1, 31, "1" }, + { 2, 39, "1" }, + { 3, 67, "2" }, + }, + { + { 0, 30, "2" }, + { 1, 31, "1" }, + { 2, 39, "1" }, + { 3, 67, "2" }, + }, + }, + { + { 63, 47, 1, 9 }, + { { "0", { 18, 0 } }, { "1", { 29, 0 } }, { "2", { 9, 0 } }, + { "3", { 52, 0 } } }, + false, + { }, + { }, + }, + { + { 22, 29, 46, 85 }, + { { "0", { 65, 0 } }, { "1", { 85, 0 } }, { "2", { 65, 0 } }, + { "3", { 78, 0 } } }, + true, + { + { 0, 22, "2" }, + { 1, 29, "0" }, + { 2, 46, "3" }, + { 3, 85, "1" }, + }, + { + { 0, 22, "0" }, + { 1, 29, "3" }, + { 2, 46, "3" }, + { 3, 85, "1" }, + }, + }, + { + { 66, 11, 34, 21 }, + { { "0", { 24, 0 } }, { "1", { 57, 0 } }, { "2", { 61, 0 } }, + { "3", { 51, 0 } } }, + false, + { }, + { }, + }, + { + { 72, 65, 67, 45 }, + { { "0", { 29, 0 } }, { "1", { 77, 0 } }, { "2", { 98, 0 } }, + { "3", { 58, 0 } } }, + false, + { }, + { }, + }, + /* + * The following is a contrived attack on the bin-packing algorithm that + * causes it to execute with n! complexity, where n is the number of + * resources. This case is very unrepresentative of real-world usage, and + * has been documented but disabled. The bin-packing problem is NP-hard, and + * we may not be able to fix this case at all. + */ +#if 0 + { + { 1000, 999, 998, 997, 996, 995, 994, 993, 992, 991, 19 }, + { { "0", { 1000, 0 } }, { "1", { 1001, 0 } }, { "2", { 1002, 0 } }, + { "3", { 1003, 0 } }, { "4", { 1004, 0 } }, { "5", { 1005, 0 } }, + { "6", { 1006, 0 } }, { "7", { 1007, 0 } }, { "8", { 1008, 0 } }, + { "9", { 1009, 0 } } }, + false, + { }, + { }, + }, +#endif + /* + * These cases are more representative of real-world usage (the resource + * sizes are all the same.) + */ + { + { 1000, 999, 998, 997, 996, 995, 994, 993, 992, 991, 10 }, + { { "0", { 1000, 0 } }, { "1", { 1000, 0 } }, { "2", { 1000, 0 } }, + { "3", { 1000, 0 } }, { "4", { 1000, 0 } }, { "5", { 1000, 0 } }, + { "6", { 1000, 0 } }, { "7", { 1000, 0 } }, { "8", { 1000, 0 } }, + { "9", { 1000, 0 } } }, + false, + { }, + { }, + }, + { + { 1000, 999, 998, 997, 996, 995, 994, 993, 992, 991, 9 }, + { { "0", { 1000, 0 } }, { "1", { 1000, 0 } }, { "2", { 1000, 0 } }, + { "3", { 1000, 0 } }, { "4", { 1000, 0 } }, { "5", { 1000, 0 } }, + { "6", { 1000, 0 } }, { "7", { 1000, 0 } }, { "8", { 1000, 0 } }, + { "9", { 1000, 0 } } }, + true, + { + { 0, 1000, "0" }, + { 1, 999, "1" }, + { 2, 998, "2" }, + { 3, 997, "3" }, + { 4, 996, "4" }, + { 5, 995, "5" }, + { 6, 994, "6" }, + { 7, 993, "7" }, + { 8, 992, "8" }, + { 9, 991, "9" }, + { 10, 9, "9" }, + }, + { + { 0, 1000, "0" }, + { 1, 999, "1" }, + { 2, 998, "2" }, + { 3, 997, "3" }, + { 4, 996, "4" }, + { 5, 995, "5" }, + { 6, 994, "6" }, + { 7, 993, "7" }, + { 8, 992, "8" }, + { 9, 991, "9" }, + { 10, 9, "9" }, + }, + }, + /* clang-format on */ +}; + +struct AllocationComparison +{ + cmCTestBinPackerAllocation First; + cmCTestBinPackerAllocation Second; + bool Equal; +}; + +static const std::vector<AllocationComparison> comparisons{ + /* clang-format off */ + { { 0, 1, "0" }, { 0, 1, "0" }, true }, + { { 0, 1, "0" }, { 1, 1, "0" }, false }, + { { 0, 1, "0" }, { 0, 2, "0" }, false }, + { { 0, 1, "0" }, { 0, 1, "1" }, false }, + /* clang-format on */ +}; + +bool TestExpectedPackResult(const ExpectedPackResult& expected) +{ + std::vector<cmCTestBinPackerAllocation> roundRobinAllocations; + roundRobinAllocations.reserve(expected.SlotsNeeded.size()); + std::size_t index = 0; + for (auto const& n : expected.SlotsNeeded) { + roundRobinAllocations.push_back({ index++, n, "" }); + } + + bool roundRobinResult = cmAllocateCTestHardwareRoundRobin( + expected.Hardware, roundRobinAllocations); + if (roundRobinResult != expected.ExpectedReturnValue) { + std::cout + << "cmAllocateCTestHardwareRoundRobin did not return expected value" + << std::endl; + return false; + } + + if (roundRobinResult && + roundRobinAllocations != expected.ExpectedRoundRobinAllocations) { + std::cout << "cmAllocateCTestHardwareRoundRobin did not return expected " + "allocations" + << std::endl; + return false; + } + + std::vector<cmCTestBinPackerAllocation> blockAllocations; + blockAllocations.reserve(expected.SlotsNeeded.size()); + index = 0; + for (auto const& n : expected.SlotsNeeded) { + blockAllocations.push_back({ index++, n, "" }); + } + + bool blockResult = + cmAllocateCTestHardwareBlock(expected.Hardware, blockAllocations); + if (blockResult != expected.ExpectedReturnValue) { + std::cout << "cmAllocateCTestHardwareBlock did not return expected value" + << std::endl; + return false; + } + + if (blockResult && blockAllocations != expected.ExpectedBlockAllocations) { + std::cout << "cmAllocateCTestHardwareBlock did not return expected" + " allocations" + << std::endl; + return false; + } + + return true; +} + +int testCTestBinPacker(int /*unused*/, char* /*unused*/ []) +{ + int retval = 0; + + for (auto const& comparison : comparisons) { + if ((comparison.First == comparison.Second) != comparison.Equal) { + std::cout << "Comparison did not match expected" << std::endl; + retval = 1; + } + if ((comparison.First != comparison.Second) == comparison.Equal) { + std::cout << "Comparison did not match expected" << std::endl; + retval = 1; + } + } + + for (auto const& expected : expectedResults) { + if (!TestExpectedPackResult(expected)) { + retval = 1; + } + } + + return retval; +} |