1 /*
2 * Copyright 2021 Google LLC
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "include/core/SkTypes.h"
9 #include "include/private/SkSLIRNode.h"
10 #include "include/private/SkSLProgramElement.h"
11 #include "include/private/SkSLStatement.h"
12 #include "include/sksl/SkSLErrorReporter.h"
13 #include "include/sksl/SkSLPosition.h"
14 #include "src/base/SkSafeMath.h"
15 #include "src/core/SkTHash.h"
16 #include "src/sksl/SkSLAnalysis.h"
17 #include "src/sksl/SkSLContext.h"
18 #include "src/sksl/analysis/SkSLProgramVisitor.h"
19 #include "src/sksl/ir/SkSLExpression.h"
20 #include "src/sksl/ir/SkSLForStatement.h"
21 #include "src/sksl/ir/SkSLFunctionCall.h"
22 #include "src/sksl/ir/SkSLFunctionDeclaration.h"
23 #include "src/sksl/ir/SkSLFunctionDefinition.h"
24 #include "src/sksl/ir/SkSLProgram.h"
25
26 #include <cstddef>
27 #include <memory>
28 #include <string>
29 #include <utility>
30 #include <vector>
31
32 namespace SkSL {
33
CheckProgramStructure(const Program & program,bool enforceSizeLimit)34 bool Analysis::CheckProgramStructure(const Program& program, bool enforceSizeLimit) {
35 // We check the size of strict-ES2 programs; since SkVM will completely unroll them, it's
36 // important to know how large the result will be. For non-ES2 code, we compute an approximate
37 // lower bound by assuming all non-unrollable loops will execute one time only.
38 const Context& context = *program.fContext;
39
40 // If we decide that expressions are cheaper than statements, or that certain statements are
41 // more expensive than others, etc., we can always tweak these ratios as needed. A very rough
42 // ballpark estimate is currently good enough for our purposes.
43 static constexpr size_t kExpressionCost = 1;
44 static constexpr size_t kStatementCost = 1;
45 static constexpr size_t kUnknownCost = -1;
46 static constexpr size_t kProgramSizeLimit = 100000;
47 static constexpr size_t kProgramStackDepthLimit = 50;
48
49 class ProgramSizeVisitor : public ProgramVisitor {
50 public:
51 ProgramSizeVisitor(const Context& c) : fContext(c) {}
52
53 using ProgramVisitor::visitProgramElement;
54
55 size_t functionSize() const {
56 return fFunctionSize;
57 }
58
59 bool visitProgramElement(const ProgramElement& pe) override {
60 if (pe.is<FunctionDefinition>()) {
61 // Check the function-size cache map first. We don't need to visit this function if
62 // we already processed it before.
63 const FunctionDeclaration* decl = &pe.as<FunctionDefinition>().declaration();
64 if (size_t *cachedCost = fFunctionCostMap.find(decl)) {
65 // We already have this function in our map. We don't need to check it again.
66 if (*cachedCost == kUnknownCost) {
67 // If the function is present in the map with an unknown cost, we're
68 // recursively processing it--in other words, we found a cycle in the code.
69 // Unwind our stack into a string.
70 std::string msg = "\n\t" + decl->description();
71 for (auto unwind = fStack.rbegin(); unwind != fStack.rend(); ++unwind) {
72 msg = "\n\t" + (*unwind)->description() + msg;
73 if (*unwind == decl) {
74 break;
75 }
76 }
77 msg = "potential recursion (function call cycle) not allowed:" + msg;
78 fContext.fErrors->error(pe.fPosition, std::move(msg));
79 fFunctionSize = 0;
80 *cachedCost = 0;
81 return true;
82 }
83 // Set the size to its known value.
84 fFunctionSize = *cachedCost;
85 return false;
86 }
87
88 // If the function-call stack has gotten too deep, stop the analysis.
89 if (fStack.size() >= kProgramStackDepthLimit) {
90 std::string msg = "exceeded max function call depth:";
91 for (auto unwind = fStack.begin(); unwind != fStack.end(); ++unwind) {
92 msg += "\n\t" + (*unwind)->description();
93 }
94 msg += "\n\t" + decl->description();
95 fContext.fErrors->error(pe.fPosition, std::move(msg));
96 fFunctionSize = 0;
97 fFunctionCostMap.set(decl, 0);
98 return true;
99 }
100
101 // Calculate the function cost and store it in our cache.
102 fFunctionCostMap.set(decl, kUnknownCost);
103 fStack.push_back(decl);
104 fFunctionSize = 0;
105 bool result = INHERITED::visitProgramElement(pe);
106 fFunctionCostMap.set(decl, fFunctionSize);
107 fStack.pop_back();
108
109 return result;
110 }
111
112 return INHERITED::visitProgramElement(pe);
113 }
114
115 bool visitStatement(const Statement& stmt) override {
116 switch (stmt.kind()) {
117 case Statement::Kind::kFor: {
118 // We count a for-loop's unrolled size here. We expect that the init statement
119 // will be emitted once, and the test-expr, next-expr and statement will be
120 // repeated in the output for every iteration of the loop.
121 bool earlyExit = false;
122 const ForStatement& forStmt = stmt.as<ForStatement>();
123 if (forStmt.initializer() && this->visitStatement(*forStmt.initializer())) {
124 earlyExit = true;
125 }
126
127 size_t originalFunctionSize = fFunctionSize;
128 fFunctionSize = 0;
129
130 if (forStmt.next() && this->visitExpression(*forStmt.next())) {
131 earlyExit = true;
132 }
133 if (forStmt.test() && this->visitExpression(*forStmt.test())) {
134 earlyExit = true;
135 }
136 if (this->visitStatement(*forStmt.statement())) {
137 earlyExit = true;
138 }
139
140 // ES2 programs always have a known unroll count. Non-ES2 programs don't enforce
141 // a maximum program size, so it's fine to treat the loop as executing once.
142 if (const LoopUnrollInfo* unrollInfo = forStmt.unrollInfo()) {
143 fFunctionSize = SkSafeMath::Mul(fFunctionSize, unrollInfo->fCount);
144 }
145 fFunctionSize = SkSafeMath::Add(fFunctionSize, originalFunctionSize);
146 return earlyExit;
147 }
148
149 case Statement::Kind::kExpression:
150 // The cost of an expression-statement is counted in visitExpression. It would
151 // be double-dipping to count it here too.
152 break;
153
154 case Statement::Kind::kNop:
155 case Statement::Kind::kVarDeclaration:
156 // These statements don't directly consume any space in a compiled program.
157 break;
158
159 default:
160 // Note that we don't make any attempt to estimate the number of iterations of
161 // do-while loops here. Those aren't an ES2 construct so we aren't enforcing
162 // program size on them.
163 fFunctionSize = SkSafeMath::Add(fFunctionSize, kStatementCost);
164 break;
165 }
166
167 return INHERITED::visitStatement(stmt);
168 }
169
170 bool visitExpression(const Expression& expr) override {
171 // Other than function calls, all expressions are assumed to have a fixed unit cost.
172 bool earlyExit = false;
173 size_t expressionCost = kExpressionCost;
174
175 if (expr.is<FunctionCall>()) {
176 // Visit this function call to calculate its size. If we've already sized it, this
177 // will retrieve the size from our cache.
178 const FunctionCall& call = expr.as<FunctionCall>();
179 const FunctionDeclaration* decl = &call.function();
180 if (decl->definition() && !decl->isIntrinsic()) {
181 size_t originalFunctionSize = fFunctionSize;
182 fFunctionSize = 0;
183
184 earlyExit = this->visitProgramElement(*decl->definition());
185 expressionCost = fFunctionSize;
186
187 fFunctionSize = originalFunctionSize;
188 }
189 }
190
191 fFunctionSize = SkSafeMath::Add(fFunctionSize, expressionCost);
192 return earlyExit || INHERITED::visitExpression(expr);
193 }
194
195 private:
196 using INHERITED = ProgramVisitor;
197
198 const Context& fContext;
199 size_t fFunctionSize = 0;
200 SkTHashMap<const FunctionDeclaration*, size_t> fFunctionCostMap;
201 std::vector<const FunctionDeclaration*> fStack;
202 };
203
204 // Process every function in our program.
205 ProgramSizeVisitor visitor{context};
206 for (const std::unique_ptr<ProgramElement>& element : program.fOwnedElements) {
207 if (element->is<FunctionDefinition>()) {
208 // Visit every function--we want to detect static recursion and report it as an error,
209 // even in unreferenced functions.
210 visitor.visitProgramElement(*element);
211 // Report an error when main()'s flattened size is larger than our program limit.
212 if (enforceSizeLimit &&
213 visitor.functionSize() > kProgramSizeLimit &&
214 element->as<FunctionDefinition>().declaration().isMain()) {
215 context.fErrors->error(Position(), "program is too large");
216 }
217 }
218 }
219
220 return true;
221 }
222
223 } // namespace SkSL
224