From 4fb79b54f28791292d7bab029d13cf5f89da5106 Mon Sep 17 00:00:00 2001 From: Ehsan Nasiri Date: Sun, 4 Dec 2016 10:48:26 -0500 Subject: [PATCH] Validation for struct nesting depth. According to sectin 2.17 in SPIR-V Spec, the structure nesting depth may not be larger than 255. This is interpreted as structures nested in structures. The code does not look into arrays or follow pointers to see if it reaches a structure downstream. Use memoization to avoid exponential runtime. --- source/val/validation_state.cpp | 1 + source/val/validation_state.h | 13 +++++++++++++ source/validate_instruction.cpp | 34 +++++++++++++++++++++++++++++++++- test/val/val_limits_test.cpp | 33 +++++++++++++++++++++++++++++++++ 4 files changed, 80 insertions(+), 1 deletion(-) diff --git a/source/val/validation_state.cpp b/source/val/validation_state.cpp index b11e6fc..de692f8 100644 --- a/source/val/validation_state.cpp +++ b/source/val/validation_state.cpp @@ -194,6 +194,7 @@ ValidationState_t::ValidationState_t(const spv_const_context ctx) all_definitions_(), num_global_vars_(0), num_local_vars_(0), + struct_nesting_depth_(), grammar_(ctx), addressing_model_(SpvAddressingModelLogical), memory_model_(SpvMemoryModelSimple), diff --git a/source/val/validation_state.h b/source/val/validation_state.h index ad90ef9..5abf9c3 100644 --- a/source/val/validation_state.h +++ b/source/val/validation_state.h @@ -205,6 +205,16 @@ class ValidationState_t { /// Increments the number of Local Variables void incrementNumLocalVars() { ++num_local_vars_; } + /// Sets the struct nesting depth for a given struct ID + void set_struct_nesting_depth(uint32_t id, uint32_t depth) { + struct_nesting_depth_[id] = depth; + } + + /// Returns the nesting depth of a given structure ID + uint32_t struct_nesting_depth(uint32_t id) { + return struct_nesting_depth_[id]; + } + private: ValidationState_t(const ValidationState_t&); @@ -254,6 +264,9 @@ class ValidationState_t { /// Number of Local Variables ('Function' Storage Class) uint32_t num_local_vars_; + /// Structure Nesting Depth + std::unordered_map struct_nesting_depth_; + AssemblyGrammar grammar_; SpvAddressingModel addressing_model_; diff --git a/source/validate_instruction.cpp b/source/validate_instruction.cpp index 0b3d0c0..507d073 100644 --- a/source/validate_instruction.cpp +++ b/source/validate_instruction.cpp @@ -16,6 +16,7 @@ #include "validate.h" +#include #include #include @@ -145,14 +146,45 @@ spv_result_t LimitCheckIdBound(ValidationState_t& _, // Checks that the number of OpTypeStruct members is within the limit. spv_result_t LimitCheckStruct(ValidationState_t& _, const spv_parsed_instruction_t* inst) { + if (SpvOpTypeStruct != inst->opcode) { + return SPV_SUCCESS; + } + // Number of members is the number of operands of the instruction minus 1. // One operand is the result ID. const uint16_t limit = 0x3fff; - if (SpvOpTypeStruct == inst->opcode && inst->num_operands - 1 > limit) { + if (inst->num_operands - 1 > limit) { return _.diag(SPV_ERROR_INVALID_BINARY) << "Number of OpTypeStruct members (" << inst->num_operands - 1 << ") has exceeded the limit (" << limit << ")."; } + + // Section 2.17 of SPIRV Spec specifies that the "Structure Nesting Depth" + // must be less than or equal to 255. + // This is interpreted as structures including other structures as members. + // The code does not follow pointers or look into arrays to see if we reach a + // structure downstream. + // The nesting depth of a struct is 1+(largest depth of any member). + // Scalars are at depth 0. + uint32_t max_member_depth = 0; + // Struct members start at word 2 of OpTypeStruct instruction. + for (size_t word_i = 2; word_i < inst->num_words; ++word_i) { + auto member = inst->words[word_i]; + auto memberTypeInstr = _.FindDef(member); + if (memberTypeInstr && SpvOpTypeStruct == memberTypeInstr->opcode()) { + max_member_depth = std::max( + max_member_depth, _.struct_nesting_depth(memberTypeInstr->id())); + } + } + + const uint32_t depth_limit = 255; + const uint32_t cur_depth = 1 + max_member_depth; + _.set_struct_nesting_depth(inst->result_id, cur_depth); + if (cur_depth > depth_limit) { + return _.diag(SPV_ERROR_INVALID_BINARY) + << "Structure Nesting Depth may not be larger than " << depth_limit + << ". Found " << cur_depth << "."; + } return SPV_SUCCESS; } diff --git a/test/val/val_limits_test.cpp b/test/val/val_limits_test.cpp index 3774afe..f6f2945 100644 --- a/test/val/val_limits_test.cpp +++ b/test/val/val_limits_test.cpp @@ -287,3 +287,36 @@ TEST_F(ValidateLimits, NumLocalVarsBad) { "exceeded the valid limit (524287).")); } +// Valid: Structure nesting depth of 255. +TEST_F(ValidateLimits, StructNestingDepthGood) { + std::ostringstream spirv; + spirv << header << R"( + %int = OpTypeInt 32 0 + %s_depth_1 = OpTypeStruct %int + )"; + for(auto i=2; i<=255; ++i) { + spirv << "%s_depth_" << i << " = OpTypeStruct %int %s_depth_" << i-1; + spirv << "\n"; + } + CompileSuccessfully(spirv.str()); + EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()); +} + +// Invalid: Structure nesting depth of 256. +TEST_F(ValidateLimits, StructNestingDepthBad) { + std::ostringstream spirv; + spirv << header << R"( + %int = OpTypeInt 32 0 + %s_depth_1 = OpTypeStruct %int + )"; + for(auto i=2; i<=256; ++i) { + spirv << "%s_depth_" << i << " = OpTypeStruct %int %s_depth_" << i-1; + spirv << "\n"; + } + CompileSuccessfully(spirv.str()); + EXPECT_EQ(SPV_ERROR_INVALID_BINARY, ValidateInstructions()); + EXPECT_THAT( + getDiagnosticString(), + HasSubstr( + "Structure Nesting Depth may not be larger than 255. Found 256.")); +} -- 2.7.4