"Unable to find any free processors for remaining blocks" (compute_block_grid_mapping error)

[vasdommes]

Exception

On one of the machines (MacBook M1 Air), the following exception happened in unit tests (not reproduced on other machines):

compute_block_grid_mapping
 Random
-------------------------------------------------------------------------------
../test/src/unit_tests/cases/block_mapping.test.cxx:49
...............................................................................

../test/src/unit_tests/cases/block_mapping.test.cxx:53: FAILED:
due to unexpected exception with messages:
 num_nodes := 2
 procs_per_node := 10
 num_blocks := 1001 (0x3e9)
 in compute_block_grid_mapping() at ../src/sdpb_util/block_mapping/
 compute_block_grid_mapping.hxx:169: 
 Unable to find any free processors for remaining blocks
 Stacktrace:
 0# compute_block_grid_mapping(unsigned long const&, unsigned long const&,
 std::__1::vector<Block_Cost, std::__1::allocator<Block_Cost>>) in /Users/
 thomas.pochart/sdpb/build/unit_tests
 1# CATCH2_INTERNAL_TEST_28() in /Users/thomas.pochart/sdpb/build/unit_tests

The error is thrown by the following piece of code:

sdpb/src/sdpb_util/block_mapping/compute_block_grid_mapping.hxx

Lines 166 to 170 in 32afe5d

	if(min_block == available_block_maps.at(0).end())
	{
	LOGIC_ERROR(
	"Unable to find any free processors for remaining blocks");
	}

Explanation

The problem is that initially we set the iterator min_block = available_block_maps.at(0).end()), assuming that end() is semantically equivalent to nullptr. Then we set min_block to some real iterator pointing to the one of the available Block_Map's:

sdpb/src/sdpb_util/block_mapping/compute_block_grid_mapping.hxx

Lines 152 to 161 in 32afe5d

	auto min_block(available_block_maps.at(0).end());
	for(size_t node(0); node < num_nodes; ++node)
	{
	if(!available_block_maps[node].empty())
	{
	auto block = std::min_element(available_block_maps[node].begin(),
	available_block_maps[node].end());
	if(block->cost < min_cost)
	{
	min_block = block;

Now, if min_block is an iterator e.g. from available_block_maps[1], comparing it to an iterator from available_block_maps.at[0] leads to undefined behaviour.

In this specific case, min_block was set to available_block_maps.at(1).begin(), and then comparison available_block_maps.at(0).end() == available_block_maps.at(1).begin()) returned true, leading to the exception shown above.

Why did it return true? This makes sense if we imagine that all data for available_block_maps is stored in a contiguous memory region, and iterator comparison is implemented via raw pointer comparison. In that case, the end() of the first vector coincides with the begin() of the next one.