Detect large Jacobians and return failure instead of crashing. Detect when the number of non-zeros overflows when constructing BlockSparseMatrix and CompressedRowSparseMatrix and return with an error message instead of crashing. Change-Id: I45e102f7c0519eef441ce0586b7adf96e4a954a9
diff --git a/internal/ceres/block_jacobian_writer.cc b/internal/ceres/block_jacobian_writer.cc index b009e96..adeaf41 100644 --- a/internal/ceres/block_jacobian_writer.cc +++ b/internal/ceres/block_jacobian_writer.cc
@@ -63,7 +63,7 @@ // // TODO(keir): Consider if we should use a boolean for each parameter block // instead of num_eliminate_blocks. -void BuildJacobianLayout(const Program& program, +bool BuildJacobianLayout(const Program& program, int num_eliminate_blocks, std::vector<int*>* jacobian_layout, std::vector<int>* jacobian_layout_storage) { @@ -73,8 +73,8 @@ // Iterate over all the active residual blocks and determine how many E blocks // are there. This will determine where the F blocks start in the jacobian // matrix. Also compute the number of jacobian blocks. - int f_block_pos = 0; - int num_jacobian_blocks = 0; + unsigned int f_block_pos = 0; + unsigned int num_jacobian_blocks = 0; for (auto* residual_block : residual_blocks) { const int num_residuals = residual_block->NumResiduals(); const int num_parameter_blocks = residual_block->NumParameterBlocks(); @@ -90,6 +90,11 @@ } } } + if (num_jacobian_blocks > std::numeric_limits<int>::max()) { + LOG(ERROR) << "Overlow error. Too many blocks in the jacobian matrix : " + << num_jacobian_blocks; + return false; + } } // We now know that the E blocks are laid out starting at zero, and the F @@ -145,12 +150,18 @@ jacobian_pos[k] = e_block_pos; e_block_pos += jacobian_block_size; } else { - jacobian_pos[k] = f_block_pos; + jacobian_pos[k] = static_cast<int>(f_block_pos); f_block_pos += jacobian_block_size; + if (f_block_pos > std::numeric_limits<int>::max()) { + LOG(ERROR) + << "Overlow error. Too many entries in the Jacobian matrix."; + return false; + } } } jacobian_pos += active_parameter_blocks.size(); } + return true; } } // namespace @@ -161,10 +172,10 @@ CHECK_GE(options.num_eliminate_blocks, 0) << "num_eliminate_blocks must be greater than 0."; - BuildJacobianLayout(*program, - options.num_eliminate_blocks, - &jacobian_layout_, - &jacobian_layout_storage_); + jacobian_layout_is_valid_ = BuildJacobianLayout(*program, + options.num_eliminate_blocks, + &jacobian_layout_, + &jacobian_layout_storage_); } // Create evaluate prepareres that point directly into the final jacobian. This @@ -183,6 +194,12 @@ } std::unique_ptr<SparseMatrix> BlockJacobianWriter::CreateJacobian() const { + if (!jacobian_layout_is_valid_) { + LOG(ERROR) << "Unable to create Jacobian matrix. Too many entries in the " + "Jacobian matrix."; + return nullptr; + } + auto* bs = new CompressedRowBlockStructure; const std::vector<ParameterBlock*>& parameter_blocks =
diff --git a/internal/ceres/block_jacobian_writer.h b/internal/ceres/block_jacobian_writer.h index 30b5f02..627013c 100644 --- a/internal/ceres/block_jacobian_writer.h +++ b/internal/ceres/block_jacobian_writer.h
@@ -133,6 +133,12 @@ // The pointers in jacobian_layout_ point directly into this vector. std::vector<int> jacobian_layout_storage_; + + // The constructor computes the layout of the Jacobian, and this bool keeps + // track of whether the computation of the layout completed successfully or + // not, if it is false, then jacobian_layout and jacobian_layout_storage are + // both in an invalid state. + bool jacobian_layout_is_valid_ = false; }; } // namespace ceres::internal
diff --git a/internal/ceres/compressed_row_jacobian_writer.cc b/internal/ceres/compressed_row_jacobian_writer.cc index 14c5251..5533fcf 100644 --- a/internal/ceres/compressed_row_jacobian_writer.cc +++ b/internal/ceres/compressed_row_jacobian_writer.cc
@@ -94,7 +94,10 @@ const int total_num_effective_parameters = program_->NumEffectiveParameters(); // Count the number of jacobian nonzeros. - int num_jacobian_nonzeros = 0; + // + // We used an unsigned int here, so that we can compare it INT_MAX without + // triggering overflow behaviour. + unsigned int num_jacobian_nonzeros = total_num_effective_parameters; for (auto* residual_block : residual_blocks) { const int num_residuals = residual_block->NumResiduals(); const int num_parameter_blocks = residual_block->NumParameterBlocks(); @@ -102,6 +105,12 @@ auto parameter_block = residual_block->parameter_blocks()[j]; if (!parameter_block->IsConstant()) { num_jacobian_nonzeros += num_residuals * parameter_block->TangentSize(); + if (num_jacobian_nonzeros > std::numeric_limits<int>::max()) { + LOG(ERROR) << "Unable to create Jacobian matrix: Too many entries in " + "the Jacobian matrix. num_jacobian_nonzeros = " + << num_jacobian_nonzeros; + return nullptr; + } } } } @@ -113,7 +122,7 @@ auto jacobian = std::make_unique<CompressedRowSparseMatrix>( total_num_residuals, total_num_effective_parameters, - num_jacobian_nonzeros + total_num_effective_parameters); + static_cast<int>(num_jacobian_nonzeros)); // At this stage, the CompressedRowSparseMatrix is an invalid state. But // this seems to be the only way to construct it without doing a memory
diff --git a/internal/ceres/evaluator_test.cc b/internal/ceres/evaluator_test.cc index 34ec78c..773cbcd 100644 --- a/internal/ceres/evaluator_test.cc +++ b/internal/ceres/evaluator_test.cc
@@ -676,5 +676,51 @@ } } +class HugeCostFunction : public SizedCostFunction<46341, 46345> { + bool Evaluate(double const* const* parameters, + double* residuals, + double** jacobians) const override { + return true; + } +}; + +TEST(Evaluator, LargeProblemDoesNotCauseCrashBlockJacobianWriter) { + ProblemImpl problem; + std::vector<double> x(46345); + + problem.AddResidualBlock(new HugeCostFunction, nullptr, x.data()); + Evaluator::Options options; + options.linear_solver_type = SPARSE_NORMAL_CHOLESKY; + options.context = problem.context(); + options.num_eliminate_blocks = 0; + options.dynamic_sparsity = false; + std::string error; + auto program = problem.mutable_program(); + program->SetParameterOffsetsAndIndex(); + auto evaluator = Evaluator::Create(options, program, &error); + auto jacobian = evaluator->CreateJacobian(); + EXPECT_EQ(jacobian, nullptr); +} + +TEST(Evaluator, LargeProblemDoesNotCauseCrashCompressedRowJacobianWriter) { + ProblemImpl problem; + std::vector<double> x(46345); + + problem.AddResidualBlock(new HugeCostFunction, nullptr, x.data()); + Evaluator::Options options; + // CGNR on CUDA_SPARSE is the only combination that triggers a + // CompressedRowJacobianWriter. + options.linear_solver_type = CGNR; + options.sparse_linear_algebra_library_type = CUDA_SPARSE; + options.context = problem.context(); + options.num_eliminate_blocks = 0; + std::string error; + auto program = problem.mutable_program(); + program->SetParameterOffsetsAndIndex(); + auto evaluator = Evaluator::Create(options, program, &error); + auto jacobian = evaluator->CreateJacobian(); + EXPECT_EQ(jacobian, nullptr); +} + } // namespace internal } // namespace ceres
diff --git a/internal/ceres/trust_region_preprocessor.cc b/internal/ceres/trust_region_preprocessor.cc index 519f851..2b036a5 100644 --- a/internal/ceres/trust_region_preprocessor.cc +++ b/internal/ceres/trust_region_preprocessor.cc
@@ -336,13 +336,19 @@ } // Configure and create a TrustRegionMinimizer object. -void SetupMinimizerOptions(PreprocessedProblem* pp) { +bool SetupMinimizerOptions(PreprocessedProblem* pp) { const Solver::Options& options = pp->options; SetupCommonMinimizerOptions(pp); pp->minimizer_options.is_constrained = pp->reduced_program->IsBoundsConstrained(); pp->minimizer_options.jacobian = pp->evaluator->CreateJacobian(); + if (pp->minimizer_options.jacobian == nullptr) { + pp->error = + "Unable to create Jacobian matrix. Likely because it is too large."; + return false; + } + pp->minimizer_options.inner_iteration_minimizer = pp->inner_iteration_minimizer; @@ -360,6 +366,7 @@ pp->minimizer_options.trust_region_strategy = TrustRegionStrategy::Create(strategy_options); CHECK(pp->minimizer_options.trust_region_strategy != nullptr); + return true; } } // namespace @@ -395,8 +402,7 @@ return false; } - SetupMinimizerOptions(pp); - return true; + return SetupMinimizerOptions(pp); } } // namespace ceres::internal