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 | http://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 "php.h"
20 #include "zend_compile.h"
21 #include "zend_extensions.h"
22 #include "Optimizer/zend_optimizer.h"
23 #include "zend_optimizer_internal.h"
24 #include "zend_inference.h"
25 #include "zend_call_graph.h"
26 #include "zend_func_info.h"
27 #include "zend_inference.h"
28 #include "zend_call_graph.h"
29
30 typedef int (*zend_op_array_func_t)(zend_call_graph *call_graph, zend_op_array *op_array);
31
zend_op_array_calc(zend_call_graph * call_graph,zend_op_array * op_array)32 static int zend_op_array_calc(zend_call_graph *call_graph, zend_op_array *op_array)
33 {
34 (void) op_array;
35
36 call_graph->op_arrays_count++;
37 return SUCCESS;
38 }
39
zend_op_array_collect(zend_call_graph * call_graph,zend_op_array * op_array)40 static int zend_op_array_collect(zend_call_graph *call_graph, zend_op_array *op_array)
41 {
42 zend_func_info *func_info = call_graph->func_infos + call_graph->op_arrays_count;
43
44 ZEND_SET_FUNC_INFO(op_array, func_info);
45 call_graph->op_arrays[call_graph->op_arrays_count] = op_array;
46 func_info->num = call_graph->op_arrays_count;
47 func_info->num_args = -1;
48 func_info->return_value_used = -1;
49 call_graph->op_arrays_count++;
50 return SUCCESS;
51 }
52
zend_foreach_op_array(zend_call_graph * call_graph,zend_script * script,zend_op_array_func_t func)53 static int zend_foreach_op_array(zend_call_graph *call_graph, zend_script *script, zend_op_array_func_t func)
54 {
55 zend_class_entry *ce;
56 zend_string *key;
57 zend_op_array *op_array;
58
59 if (func(call_graph, &script->main_op_array) != SUCCESS) {
60 return FAILURE;
61 }
62
63 ZEND_HASH_FOREACH_PTR(&script->function_table, op_array) {
64 if (func(call_graph, op_array) != SUCCESS) {
65 return FAILURE;
66 }
67 } ZEND_HASH_FOREACH_END();
68
69 ZEND_HASH_FOREACH_STR_KEY_PTR(&script->class_table, key, ce) {
70 if (ce->refcount > 1 && !zend_string_equals_ci(key, ce->name)) {
71 continue;
72 }
73 ZEND_HASH_FOREACH_PTR(&ce->function_table, op_array) {
74 if (op_array->scope == ce
75 && op_array->type == ZEND_USER_FUNCTION
76 && !(op_array->fn_flags & ZEND_ACC_TRAIT_CLONE)) {
77 if (func(call_graph, op_array) != SUCCESS) {
78 return FAILURE;
79 }
80 }
81 } ZEND_HASH_FOREACH_END();
82 } ZEND_HASH_FOREACH_END();
83
84 return SUCCESS;
85 }
86
zend_analyze_calls(zend_arena ** arena,zend_script * script,uint32_t build_flags,zend_op_array * op_array,zend_func_info * func_info)87 int zend_analyze_calls(zend_arena **arena, zend_script *script, uint32_t build_flags, zend_op_array *op_array, zend_func_info *func_info)
88 {
89 zend_op *opline = op_array->opcodes;
90 zend_op *end = opline + op_array->last;
91 zend_function *func;
92 zend_call_info *call_info;
93 int call = 0;
94 zend_call_info **call_stack;
95 ALLOCA_FLAG(use_heap);
96
97 call_stack = do_alloca((op_array->last / 2) * sizeof(zend_call_info*), use_heap);
98 call_info = NULL;
99 while (opline != end) {
100 switch (opline->opcode) {
101 case ZEND_INIT_FCALL:
102 case ZEND_INIT_METHOD_CALL:
103 case ZEND_INIT_STATIC_METHOD_CALL:
104 call_stack[call] = call_info;
105 func = zend_optimizer_get_called_func(
106 script, op_array, opline, (build_flags & ZEND_RT_CONSTANTS) != 0);
107 if (func) {
108 call_info = zend_arena_calloc(arena, 1, sizeof(zend_call_info) + (sizeof(zend_send_arg_info) * ((int)opline->extended_value - 1)));
109 call_info->caller_op_array = op_array;
110 call_info->caller_init_opline = opline;
111 call_info->caller_call_opline = NULL;
112 call_info->callee_func = func;
113 call_info->num_args = opline->extended_value;
114 call_info->next_callee = func_info->callee_info;
115 func_info->callee_info = call_info;
116
117 if (build_flags & ZEND_CALL_TREE) {
118 call_info->next_caller = NULL;
119 } else if (func->type == ZEND_INTERNAL_FUNCTION) {
120 call_info->next_caller = NULL;
121 } else {
122 zend_func_info *callee_func_info = ZEND_FUNC_INFO(&func->op_array);
123 if (callee_func_info) {
124 call_info->next_caller = callee_func_info->caller_info;
125 callee_func_info->caller_info = call_info;
126 } else {
127 call_info->next_caller = NULL;
128 }
129 }
130 } else {
131 call_info = NULL;
132 }
133 call++;
134 break;
135 case ZEND_INIT_FCALL_BY_NAME:
136 case ZEND_INIT_NS_FCALL_BY_NAME:
137 case ZEND_INIT_DYNAMIC_CALL:
138 case ZEND_NEW:
139 case ZEND_INIT_USER_CALL:
140 call_stack[call] = call_info;
141 call_info = NULL;
142 call++;
143 break;
144 case ZEND_DO_FCALL:
145 case ZEND_DO_ICALL:
146 case ZEND_DO_UCALL:
147 case ZEND_DO_FCALL_BY_NAME:
148 func_info->flags |= ZEND_FUNC_HAS_CALLS;
149 if (call_info) {
150 call_info->caller_call_opline = opline;
151 }
152 call--;
153 call_info = call_stack[call];
154 break;
155 case ZEND_SEND_VAL:
156 case ZEND_SEND_VAR:
157 case ZEND_SEND_VAL_EX:
158 case ZEND_SEND_VAR_EX:
159 case ZEND_SEND_FUNC_ARG:
160 case ZEND_SEND_REF:
161 case ZEND_SEND_VAR_NO_REF:
162 case ZEND_SEND_VAR_NO_REF_EX:
163 case ZEND_SEND_USER:
164 if (call_info) {
165 uint32_t num = opline->op2.num;
166
167 if (num > 0) {
168 num--;
169 }
170 call_info->arg_info[num].opline = opline;
171 }
172 break;
173 case ZEND_SEND_ARRAY:
174 case ZEND_SEND_UNPACK:
175 /* TODO: set info about var_arg call ??? */
176 if (call_info) {
177 call_info->num_args = -1;
178 }
179 break;
180 case ZEND_EXIT:
181 /* In this case the DO_CALL opcode may have been dropped
182 * and caller_call_opline will be NULL. */
183 break;
184 }
185 opline++;
186 }
187 free_alloca(call_stack, use_heap);
188 return SUCCESS;
189 }
190
zend_is_indirectly_recursive(zend_op_array * root,zend_op_array * op_array,zend_bitset visited)191 static int zend_is_indirectly_recursive(zend_op_array *root, zend_op_array *op_array, zend_bitset visited)
192 {
193 zend_func_info *func_info;
194 zend_call_info *call_info;
195 int ret = 0;
196
197 if (op_array == root) {
198 return 1;
199 }
200
201 func_info = ZEND_FUNC_INFO(op_array);
202 if (zend_bitset_in(visited, func_info->num)) {
203 return 0;
204 }
205 zend_bitset_incl(visited, func_info->num);
206 call_info = func_info->caller_info;
207 while (call_info) {
208 if (zend_is_indirectly_recursive(root, call_info->caller_op_array, visited)) {
209 call_info->recursive = 1;
210 ret = 1;
211 }
212 call_info = call_info->next_caller;
213 }
214 return ret;
215 }
216
zend_analyze_recursion(zend_call_graph * call_graph)217 static void zend_analyze_recursion(zend_call_graph *call_graph)
218 {
219 zend_op_array *op_array;
220 zend_func_info *func_info;
221 zend_call_info *call_info;
222 int i;
223 int set_len = zend_bitset_len(call_graph->op_arrays_count);
224 zend_bitset visited;
225 ALLOCA_FLAG(use_heap);
226
227 visited = ZEND_BITSET_ALLOCA(set_len, use_heap);
228 for (i = 0; i < call_graph->op_arrays_count; i++) {
229 op_array = call_graph->op_arrays[i];
230 func_info = call_graph->func_infos + i;
231 call_info = func_info->caller_info;
232 while (call_info) {
233 if (call_info->caller_op_array == op_array) {
234 call_info->recursive = 1;
235 func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_DIRECTLY;
236 } else {
237 memset(visited, 0, sizeof(zend_ulong) * set_len);
238 if (zend_is_indirectly_recursive(op_array, call_info->caller_op_array, visited)) {
239 call_info->recursive = 1;
240 func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_INDIRECTLY;
241 }
242 }
243 call_info = call_info->next_caller;
244 }
245 }
246
247 free_alloca(visited, use_heap);
248 }
249
zend_sort_op_arrays(zend_call_graph * call_graph)250 static void zend_sort_op_arrays(zend_call_graph *call_graph)
251 {
252 (void) call_graph;
253
254 // TODO: perform topological sort of cyclic call graph
255 }
256
zend_build_call_graph(zend_arena ** arena,zend_script * script,uint32_t build_flags,zend_call_graph * call_graph)257 int zend_build_call_graph(zend_arena **arena, zend_script *script, uint32_t build_flags, zend_call_graph *call_graph) /* {{{ */
258 {
259 int i;
260
261 call_graph->op_arrays_count = 0;
262 if (zend_foreach_op_array(call_graph, script, zend_op_array_calc) != SUCCESS) {
263 return FAILURE;
264 }
265 call_graph->op_arrays = (zend_op_array**)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_op_array*));
266 call_graph->func_infos = (zend_func_info*)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_func_info));
267 call_graph->op_arrays_count = 0;
268 if (zend_foreach_op_array(call_graph, script, zend_op_array_collect) != SUCCESS) {
269 return FAILURE;
270 }
271 for (i = 0; i < call_graph->op_arrays_count; i++) {
272 zend_analyze_calls(arena, script, build_flags, call_graph->op_arrays[i], call_graph->func_infos + i);
273 }
274 zend_analyze_recursion(call_graph);
275 zend_sort_op_arrays(call_graph);
276
277 return SUCCESS;
278 }
279 /* }}} */
280
zend_build_call_map(zend_arena ** arena,zend_func_info * info,zend_op_array * op_array)281 zend_call_info **zend_build_call_map(zend_arena **arena, zend_func_info *info, zend_op_array *op_array) /* {{{ */
282 {
283 zend_call_info **map, *call;
284 if (!info->callee_info) {
285 /* Don't build call map if function contains no calls */
286 return NULL;
287 }
288
289 map = zend_arena_calloc(arena, sizeof(zend_call_info *), op_array->last);
290 for (call = info->callee_info; call; call = call->next_callee) {
291 int i;
292 map[call->caller_init_opline - op_array->opcodes] = call;
293 if (call->caller_call_opline) {
294 map[call->caller_call_opline - op_array->opcodes] = call;
295 }
296 for (i = 0; i < call->num_args; i++) {
297 if (call->arg_info[i].opline) {
298 map[call->arg_info[i].opline - op_array->opcodes] = call;
299 }
300 }
301 }
302 return map;
303 }
304 /* }}} */
305
