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