From 815e6239a529ed1ba367b0647c7f971bae282109 Mon Sep 17 00:00:00 2001 From: David Crocker Date: Wed, 5 May 2021 16:43:21 +0100 Subject: Added stack check to some recursive functions --- src/GCodes/GCodeBuffer/ExpressionParser.cpp | 56 +++++++++++++++++++++++++++-- 1 file changed, 53 insertions(+), 3 deletions(-) (limited to 'src/GCodes/GCodeBuffer/ExpressionParser.cpp') diff --git a/src/GCodes/GCodeBuffer/ExpressionParser.cpp b/src/GCodes/GCodeBuffer/ExpressionParser.cpp index 2279ca2e..6b9101ea 100644 --- a/src/GCodes/GCodeBuffer/ExpressionParser.cpp +++ b/src/GCodes/GCodeBuffer/ExpressionParser.cpp @@ -12,6 +12,7 @@ #include #include #include +#include #include @@ -21,6 +22,14 @@ constexpr size_t MaxStringExpressionLength = StringLength100; +namespace StackUsage +{ + // The following values are obtained from file ExpressionParser.su generated by the compiler + constexpr uint32_t ParseInternal = 72; + constexpr uint32_t ParseIdentifierExpression = 256; + constexpr uint32_t GetObjectValue_withTable = 48; +} + // These can't be declared locally inside ParseIdentifierExpression because NamedEnum includes static data NamedEnum(NamedConstant, unsigned int, _false, iterations, line, _null, pi, _result, _true); NamedEnum(Function, unsigned int, abs, acos, asin, atan, atan2, cos, degrees, exists, floor, isnan, max, min, mod, radians, random, sin, sqrt, tan); @@ -35,6 +44,7 @@ ExpressionParser::ExpressionParser(const GCodeBuffer& p_gb, const char *text, co // Evaluate a bracketed expression void ExpressionParser::ParseExpectKet(ExpressionValue& rslt, bool evaluate, char closingBracket) THROWS(GCodeException) { + CheckStack(StackUsage::ParseInternal); ParseInternal(rslt, evaluate, 0); if (CurrentCharacter() != closingBracket) { @@ -43,7 +53,7 @@ void ExpressionParser::ParseExpectKet(ExpressionValue& rslt, bool evaluate, char AdvancePointer(); } -// Evaluate an expression +// Evaluate an expression. Do not call this one recursively! ExpressionValue ExpressionParser::Parse(bool evaluate) THROWS(GCodeException) { obsoleteField.Clear(); @@ -77,6 +87,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_ case '-': AdvancePointer(); + CheckStack(StackUsage::ParseInternal); ParseInternal(val, evaluate, UnaryPriority); switch (val.GetType()) { @@ -95,6 +106,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_ case '+': AdvancePointer(); + CheckStack(StackUsage::ParseInternal); ParseInternal(val, evaluate, UnaryPriority); switch (val.GetType()) { @@ -119,10 +131,12 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_ if (isalpha(CurrentCharacter())) { // Probably applying # to an object model array, so optimise by asking the OM for just the length + CheckStack(StackUsage::ParseIdentifierExpression); ParseIdentifierExpression(val, evaluate, true, false); } else { + CheckStack(StackUsage::ParseInternal); ParseInternal(val, evaluate, UnaryPriority); if (val.GetType() == TypeCode::CString) { @@ -151,6 +165,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_ case '!': AdvancePointer(); + CheckStack(StackUsage::ParseInternal); ParseInternal(val, evaluate, UnaryPriority); ConvertToBool(val, evaluate); val.bVal = !val.bVal; @@ -163,6 +178,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_ } else if (isalpha(c)) // looks like a variable name { + CheckStack(StackUsage::ParseIdentifierExpression); ParseIdentifierExpression(val, evaluate, false, false); } else @@ -228,6 +244,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_ ConvertToBool(val, evaluate); { ExpressionValue val2; + CheckStack(StackUsage::ParseInternal); ParseInternal(val2, evaluate && val.bVal, opPrio); // get the next operand if (val.bVal) { @@ -241,6 +258,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_ ConvertToBool(val, evaluate); { ExpressionValue val2; + CheckStack(StackUsage::ParseInternal); ParseInternal(val2, evaluate && !val.bVal, opPrio); // get the next operand if (!val.bVal) { @@ -255,12 +273,14 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_ { const bool b = val.bVal; ExpressionValue val2; + CheckStack(StackUsage::ParseInternal); ParseInternal(((b) ? val : val2), evaluate && b, opPrio); // get the second operand if (CurrentCharacter() != ':') { ThrowParseException("expected ':'"); } AdvancePointer(); + // We recently checked the stack for a call to ParseInternal, no need to do it again ParseInternal(((b) ? val2 : val), evaluate && !b, opPrio - 1); // get the third operand, which may be a further conditional expression return; } @@ -269,6 +289,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_ // Handle binary operators that always evaluate both operands { ExpressionValue val2; + CheckStack(StackUsage::ParseInternal); ParseInternal(val2, evaluate, opPrio); // get the next operand switch(opChar) { @@ -655,7 +676,7 @@ void ExpressionParser::ConvertToBool(ExpressionValue& val, bool evaluate) const } } -void ExpressionParser::ConvertToString(ExpressionValue& val, bool evaluate) THROWS(GCodeException) +void ExpressionParser::ConvertToString(ExpressionValue& val, bool evaluate) noexcept { if (!val.IsStringType()) { @@ -729,6 +750,7 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva if (c == '[') { ExpressionValue index; + CheckStack(StackUsage::ParseInternal); ParseInternal(index, evaluate, 0); if (CurrentCharacter() != ']') { @@ -836,10 +858,12 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva AdvancePointer(); if (func == Function::exists) { + CheckStack(StackUsage::ParseIdentifierExpression); ParseIdentifierExpression(rslt, evaluate, false, true); } else { + CheckStack(StackUsage::ParseInternal); ParseInternal(rslt, evaluate, 0); // evaluate the first operand switch (func.RawValue()) @@ -911,6 +935,7 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva AdvancePointer(); SkipWhiteSpace(); ExpressionValue nextOperand; + // We recently checked the stack for a call to ParseInternal, no need to do it again ParseInternal(nextOperand, evaluate, 0); ConvertToFloat(nextOperand, evaluate); rslt.fVal = atan2f(rslt.fVal, nextOperand.fVal); @@ -968,6 +993,7 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva AdvancePointer(); SkipWhiteSpace(); ExpressionValue nextOperand; + // We recently checked the stack for a call to ParseInternal, no need to do it again ParseInternal(nextOperand, evaluate, 0); BalanceNumericTypes(rslt, nextOperand, evaluate); if (rslt.GetType() == TypeCode::Float) @@ -996,6 +1022,7 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva AdvancePointer(); SkipWhiteSpace(); ExpressionValue nextOperand; + // We recently checked the stack for a call to ParseInternal, no need to do it again ParseInternal(nextOperand, evaluate, 0); BalanceNumericTypes(rslt, nextOperand, evaluate); if (rslt.GetType() == TypeCode::Float) @@ -1021,6 +1048,7 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva AdvancePointer(); SkipWhiteSpace(); ExpressionValue nextOperand; + // We recently checked the stack for a call to ParseInternal, no need to do it again ParseInternal(nextOperand, evaluate, 0); BalanceNumericTypes(rslt, nextOperand, evaluate); if (rslt.GetType() == TypeCode::Float) @@ -1100,7 +1128,8 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva } // Else assume an object model value - rslt = reprap.GetObjectValue(context, nullptr, id.c_str()); + CheckStack(StackUsage::GetObjectValue_withTable); + rslt = reprap.GetObjectValue(context, nullptr, id.c_str(), 0); if (context.ObsoleteFieldQueried() && obsoleteField.IsEmpty()) { obsoleteField.copy(id.c_str()); @@ -1200,4 +1229,25 @@ void ExpressionParser::ThrowParseException(const char *str, uint32_t param) cons throw GCodeException(gb.GetLineNumber(), GetColumn(), str, param); } +// Call this before making a recursive call, or before calling a function that needs a lot of stack from a recursive function +void ExpressionParser::CheckStack(uint32_t calledFunctionStackUsage) const THROWS(GCodeException) +{ + register const char * stackPtr asm ("sp"); + const char *stackLimit = (const char*)TaskBase::GetCallerTaskHandle() + sizeof(TaskBase); + debugPrintf("Margin: %u\n", stackPtr - stackLimit); + if (stackLimit + calledFunctionStackUsage + (StackUsage::Throw + StackUsage::Margin) <= stackPtr) + { + return; + } + + // The stack is in danger of overflowing. Throw an exception if we have enough stack to do so (ideally, this should always be the case) + if (stackLimit + StackUsage::Throw <= stackPtr) + { + throw GCodeException(gb.GetLineNumber(), GetColumn(), "Expression nesting too deep"); + } + + // Not enough stack left to throw an exception + SoftwareReset(SoftwareResetReason::stackOverflow, (const uint32_t *)stackPtr); +} + // End -- cgit v1.2.3