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 			case ZEND_SEND_USER:
159 				if (call_info) {
160 					uint32_t num = opline->op2.num;
161 
162 					if (num > 0) {
163 						num--;
164 					}
165 					call_info->arg_info[num].opline = opline;
166 				}
167 				break;
168 			case ZEND_SEND_ARRAY:
169 			case ZEND_SEND_UNPACK:
170 				/* TODO: set info about var_arg call ??? */
171 				if (call_info) {
172 					call_info->num_args = -1;
173 				}
174 				break;
175 		}
176 		opline++;
177 	}
178 	free_alloca(call_stack, use_heap);
179 	return SUCCESS;
180 }
181 
zend_is_indirectly_recursive(zend_op_array * root,zend_op_array * op_array,zend_bitset visited)182 static int zend_is_indirectly_recursive(zend_op_array *root, zend_op_array *op_array, zend_bitset visited)
183 {
184 	zend_func_info *func_info;
185 	zend_call_info *call_info;
186 	int ret = 0;
187 
188 	if (op_array == root) {
189 		return 1;
190 	}
191 
192 	func_info = ZEND_FUNC_INFO(op_array);
193 	if (zend_bitset_in(visited, func_info->num)) {
194 		return 0;
195 	}
196 	zend_bitset_incl(visited, func_info->num);
197 	call_info = func_info->caller_info;
198 	while (call_info) {
199 		if (zend_is_indirectly_recursive(root, call_info->caller_op_array, visited)) {
200 			call_info->recursive = 1;
201 			ret = 1;
202 		}
203 		call_info = call_info->next_caller;
204 	}
205 	return ret;
206 }
207 
zend_analyze_recursion(zend_call_graph * call_graph)208 static void zend_analyze_recursion(zend_call_graph *call_graph)
209 {
210 	zend_op_array *op_array;
211 	zend_func_info *func_info;
212 	zend_call_info *call_info;
213 	int i;
214 	int set_len = zend_bitset_len(call_graph->op_arrays_count);
215 	zend_bitset visited;
216 	ALLOCA_FLAG(use_heap);
217 
218 	visited = ZEND_BITSET_ALLOCA(set_len, use_heap);
219 	for (i = 0; i < call_graph->op_arrays_count; i++) {
220 		op_array = call_graph->op_arrays[i];
221 		func_info = call_graph->func_infos + i;
222 		call_info = func_info->caller_info;
223 		while (call_info) {
224 			if (call_info->caller_op_array == op_array) {
225 				call_info->recursive = 1;
226 				func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_DIRECTLY;
227 			} else {
228 				memset(visited, 0, sizeof(zend_ulong) * set_len);
229 				if (zend_is_indirectly_recursive(op_array, call_info->caller_op_array, visited)) {
230 					call_info->recursive = 1;
231 					func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_INDIRECTLY;
232 				}
233 			}
234 			call_info = call_info->next_caller;
235 		}
236 	}
237 
238 	free_alloca(visited, use_heap);
239 }
240 
zend_sort_op_arrays(zend_call_graph * call_graph)241 static void zend_sort_op_arrays(zend_call_graph *call_graph)
242 {
243 	(void) call_graph;
244 
245 	// TODO: perform topological sort of cyclic call graph
246 }
247 
zend_build_call_graph(zend_arena ** arena,zend_script * script,uint32_t build_flags,zend_call_graph * call_graph)248 int zend_build_call_graph(zend_arena **arena, zend_script *script, uint32_t build_flags, zend_call_graph *call_graph) /* {{{ */
249 {
250 	int i;
251 
252 	call_graph->op_arrays_count = 0;
253 	if (zend_foreach_op_array(call_graph, script, zend_op_array_calc) != SUCCESS) {
254 		return FAILURE;
255 	}
256 	call_graph->op_arrays = (zend_op_array**)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_op_array*));
257 	call_graph->func_infos = (zend_func_info*)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_func_info));
258 	call_graph->op_arrays_count = 0;
259 	if (zend_foreach_op_array(call_graph, script, zend_op_array_collect) != SUCCESS) {
260 		return FAILURE;
261 	}
262 	for (i = 0; i < call_graph->op_arrays_count; i++) {
263 		zend_analyze_calls(arena, script, build_flags, call_graph->op_arrays[i], call_graph->func_infos + i);
264 	}
265 	zend_analyze_recursion(call_graph);
266 	zend_sort_op_arrays(call_graph);
267 
268 	return SUCCESS;
269 }
270 /* }}} */
271 
zend_build_call_map(zend_arena ** arena,zend_func_info * info,zend_op_array * op_array)272 zend_call_info **zend_build_call_map(zend_arena **arena, zend_func_info *info, zend_op_array *op_array) /* {{{ */
273 {
274 	zend_call_info **map, *call;
275 	if (!info->callee_info) {
276 		/* Don't build call map if function contains no calls */
277 		return NULL;
278 	}
279 
280 	map = zend_arena_calloc(arena, sizeof(zend_call_info *), op_array->last);
281 	for (call = info->callee_info; call; call = call->next_callee) {
282 		int i;
283 		map[call->caller_init_opline - op_array->opcodes] = call;
284 		map[call->caller_call_opline - op_array->opcodes] = call;
285 		for (i = 0; i < call->num_args; i++) {
286 			if (call->arg_info[i].opline) {
287 				map[call->arg_info[i].opline - op_array->opcodes] = call;
288 			}
289 		}
290 	}
291 	return map;
292 }
293 /* }}} */
294 
295 /*
296  * Local variables:
297  * tab-width: 4
298  * c-basic-offset: 4
299  * indent-tabs-mode: t
300  * End:
301  */
302