1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine, Call Graph |
4 +----------------------------------------------------------------------+
5 | Copyright (c) The PHP Group |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | https://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
15 | Authors: Dmitry Stogov <dmitry@php.net> |
16 +----------------------------------------------------------------------+
17 */
18
19 #include "zend_compile.h"
20 #include "zend_extensions.h"
21 #include "Optimizer/zend_optimizer.h"
22 #include "zend_optimizer_internal.h"
23 #include "zend_inference.h"
24 #include "zend_call_graph.h"
25 #include "zend_func_info.h"
26 #include "zend_inference.h"
27 #include "zend_call_graph.h"
28
zend_op_array_calc(zend_op_array * op_array,void * context)29 static void zend_op_array_calc(zend_op_array *op_array, void *context)
30 {
31 zend_call_graph *call_graph = context;
32 call_graph->op_arrays_count++;
33 }
34
zend_op_array_collect(zend_op_array * op_array,void * context)35 static void zend_op_array_collect(zend_op_array *op_array, void *context)
36 {
37 zend_call_graph *call_graph = context;
38 zend_func_info *func_info = call_graph->func_infos + call_graph->op_arrays_count;
39
40 ZEND_SET_FUNC_INFO(op_array, func_info);
41 call_graph->op_arrays[call_graph->op_arrays_count] = op_array;
42 func_info->num = call_graph->op_arrays_count;
43 call_graph->op_arrays_count++;
44 }
45
zend_analyze_calls(zend_arena ** arena,zend_script * script,uint32_t build_flags,zend_op_array * op_array,zend_func_info * func_info)46 ZEND_API void zend_analyze_calls(zend_arena **arena, zend_script *script, uint32_t build_flags, zend_op_array *op_array, zend_func_info *func_info)
47 {
48 zend_op *opline = op_array->opcodes;
49 zend_op *end = opline + op_array->last;
50 zend_function *func;
51 zend_call_info *call_info;
52 int call = 0;
53 zend_call_info **call_stack;
54 ALLOCA_FLAG(use_heap);
55 bool is_prototype;
56
57 call_stack = do_alloca((op_array->last / 2) * sizeof(zend_call_info*), use_heap);
58 call_info = NULL;
59 while (opline != end) {
60 switch (opline->opcode) {
61 case ZEND_INIT_FCALL:
62 case ZEND_INIT_METHOD_CALL:
63 case ZEND_INIT_STATIC_METHOD_CALL:
64 case ZEND_INIT_PARENT_PROPERTY_HOOK_CALL:
65 call_stack[call] = call_info;
66 func = zend_optimizer_get_called_func(
67 script, op_array, opline, &is_prototype);
68 if (func) {
69 call_info = zend_arena_calloc(arena, 1, sizeof(zend_call_info) + (sizeof(zend_send_arg_info) * ((int)opline->extended_value - 1)));
70 call_info->caller_op_array = op_array;
71 call_info->caller_init_opline = opline;
72 call_info->caller_call_opline = NULL;
73 call_info->callee_func = func;
74 call_info->num_args = opline->extended_value;
75 call_info->next_callee = func_info->callee_info;
76 call_info->is_prototype = is_prototype;
77 call_info->is_frameless = false;
78 func_info->callee_info = call_info;
79
80 if (build_flags & ZEND_CALL_TREE) {
81 call_info->next_caller = NULL;
82 } else if (func->type == ZEND_INTERNAL_FUNCTION
83 || func->op_array.filename != script->filename) {
84 call_info->next_caller = NULL;
85 } else {
86 zend_func_info *callee_func_info = ZEND_FUNC_INFO(&func->op_array);
87 if (callee_func_info) {
88 call_info->next_caller = callee_func_info->caller_info;
89 callee_func_info->caller_info = call_info;
90 } else {
91 call_info->next_caller = NULL;
92 }
93 }
94 } else {
95 call_info = NULL;
96 }
97 call++;
98 break;
99 case ZEND_INIT_FCALL_BY_NAME:
100 case ZEND_INIT_NS_FCALL_BY_NAME:
101 case ZEND_INIT_DYNAMIC_CALL:
102 case ZEND_NEW:
103 case ZEND_INIT_USER_CALL:
104 call_stack[call] = call_info;
105 call_info = NULL;
106 call++;
107 break;
108 case ZEND_FRAMELESS_ICALL_0:
109 case ZEND_FRAMELESS_ICALL_1:
110 case ZEND_FRAMELESS_ICALL_2:
111 case ZEND_FRAMELESS_ICALL_3: {
112 func = ZEND_FLF_FUNC(opline);
113 zend_call_info *call_info = zend_arena_calloc(arena, 1, sizeof(zend_call_info));
114 call_info->caller_op_array = op_array;
115 call_info->caller_init_opline = opline;
116 call_info->caller_call_opline = NULL;
117 call_info->callee_func = func;
118 call_info->num_args = ZEND_FLF_NUM_ARGS(opline->opcode);
119 call_info->next_callee = func_info->callee_info;
120 call_info->is_prototype = false;
121 call_info->is_frameless = true;
122 call_info->next_caller = NULL;
123 func_info->callee_info = call_info;
124 break;
125 }
126 case ZEND_DO_FCALL:
127 case ZEND_DO_ICALL:
128 case ZEND_DO_UCALL:
129 case ZEND_DO_FCALL_BY_NAME:
130 case ZEND_CALLABLE_CONVERT:
131 func_info->flags |= ZEND_FUNC_HAS_CALLS;
132 if (call_info) {
133 call_info->caller_call_opline = opline;
134 }
135 call--;
136 call_info = call_stack[call];
137 break;
138 case ZEND_SEND_VAL:
139 case ZEND_SEND_VAR:
140 case ZEND_SEND_VAL_EX:
141 case ZEND_SEND_VAR_EX:
142 case ZEND_SEND_FUNC_ARG:
143 case ZEND_SEND_REF:
144 case ZEND_SEND_VAR_NO_REF:
145 case ZEND_SEND_VAR_NO_REF_EX:
146 case ZEND_SEND_USER:
147 if (call_info) {
148 if (opline->op2_type == IS_CONST) {
149 call_info->named_args = 1;
150 break;
151 }
152
153 uint32_t num = opline->op2.num;
154 if (num > 0) {
155 num--;
156 }
157 call_info->arg_info[num].opline = opline;
158 }
159 break;
160 case ZEND_SEND_ARRAY:
161 case ZEND_SEND_UNPACK:
162 if (call_info) {
163 call_info->send_unpack = 1;
164 }
165 break;
166 }
167 opline++;
168 }
169 free_alloca(call_stack, use_heap);
170 }
171
zend_is_indirectly_recursive(zend_op_array * root,zend_op_array * op_array,zend_bitset visited)172 static bool zend_is_indirectly_recursive(zend_op_array *root, zend_op_array *op_array, zend_bitset visited)
173 {
174 zend_func_info *func_info;
175 zend_call_info *call_info;
176 bool ret = 0;
177
178 if (op_array == root) {
179 return 1;
180 }
181
182 func_info = ZEND_FUNC_INFO(op_array);
183 if (zend_bitset_in(visited, func_info->num)) {
184 return 0;
185 }
186 zend_bitset_incl(visited, func_info->num);
187 call_info = func_info->caller_info;
188 while (call_info) {
189 if (zend_is_indirectly_recursive(root, call_info->caller_op_array, visited)) {
190 call_info->recursive = 1;
191 ret = 1;
192 }
193 call_info = call_info->next_caller;
194 }
195 return ret;
196 }
197
zend_analyze_recursion(zend_call_graph * call_graph)198 static void zend_analyze_recursion(zend_call_graph *call_graph)
199 {
200 zend_op_array *op_array;
201 zend_func_info *func_info;
202 zend_call_info *call_info;
203 int i;
204 int set_len = zend_bitset_len(call_graph->op_arrays_count);
205 zend_bitset visited;
206 ALLOCA_FLAG(use_heap);
207
208 visited = ZEND_BITSET_ALLOCA(set_len, use_heap);
209 for (i = 0; i < call_graph->op_arrays_count; i++) {
210 op_array = call_graph->op_arrays[i];
211 func_info = call_graph->func_infos + i;
212 call_info = func_info->caller_info;
213 for (; call_info; call_info = call_info->next_caller) {
214 if (call_info->is_prototype) {
215 /* Might be calling an overridden child method and not actually recursive. */
216 continue;
217 }
218 if (call_info->caller_op_array == op_array) {
219 call_info->recursive = 1;
220 func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_DIRECTLY;
221 } else {
222 memset(visited, 0, sizeof(zend_ulong) * set_len);
223 if (zend_is_indirectly_recursive(op_array, call_info->caller_op_array, visited)) {
224 call_info->recursive = 1;
225 func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_INDIRECTLY;
226 }
227 }
228 }
229 }
230
231 free_alloca(visited, use_heap);
232 }
233
zend_sort_op_arrays(zend_call_graph * call_graph)234 static void zend_sort_op_arrays(zend_call_graph *call_graph)
235 {
236 (void) call_graph;
237
238 // TODO: perform topological sort of cyclic call graph
239 }
240
zend_build_call_graph(zend_arena ** arena,zend_script * script,zend_call_graph * call_graph)241 ZEND_API void zend_build_call_graph(zend_arena **arena, zend_script *script, zend_call_graph *call_graph) /* {{{ */
242 {
243 call_graph->op_arrays_count = 0;
244 zend_foreach_op_array(script, zend_op_array_calc, call_graph);
245
246 call_graph->op_arrays = (zend_op_array**)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_op_array*));
247 call_graph->func_infos = (zend_func_info*)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_func_info));
248 call_graph->op_arrays_count = 0;
249 zend_foreach_op_array(script, zend_op_array_collect, call_graph);
250 }
251 /* }}} */
252
zend_analyze_call_graph(zend_arena ** arena,zend_script * script,zend_call_graph * call_graph)253 ZEND_API void zend_analyze_call_graph(zend_arena **arena, zend_script *script, zend_call_graph *call_graph) /* {{{ */
254 {
255 int i;
256
257 for (i = 0; i < call_graph->op_arrays_count; i++) {
258 zend_analyze_calls(arena, script, 0, call_graph->op_arrays[i], call_graph->func_infos + i);
259 }
260 zend_analyze_recursion(call_graph);
261 zend_sort_op_arrays(call_graph);
262 }
263 /* }}} */
264
zend_build_call_map(zend_arena ** arena,zend_func_info * info,const zend_op_array * op_array)265 ZEND_API zend_call_info **zend_build_call_map(zend_arena **arena, zend_func_info *info, const zend_op_array *op_array) /* {{{ */
266 {
267 zend_call_info **map, *call;
268 if (!info->callee_info) {
269 /* Don't build call map if function contains no calls */
270 return NULL;
271 }
272
273 map = zend_arena_calloc(arena, sizeof(zend_call_info *), op_array->last);
274 for (call = info->callee_info; call; call = call->next_callee) {
275 int i;
276 map[call->caller_init_opline - op_array->opcodes] = call;
277 if (call->caller_call_opline) {
278 map[call->caller_call_opline - op_array->opcodes] = call;
279 }
280 if (!call->is_frameless) {
281 for (i = 0; i < call->num_args; i++) {
282 if (call->arg_info[i].opline) {
283 map[call->arg_info[i].opline - op_array->opcodes] = call;
284 }
285 }
286 }
287 }
288 return map;
289 }
290 /* }}} */
291
