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