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