]>
Commit | Line | Data |
---|---|---|
37d6f666 | 1 | /* AddressSanitizer, a fast memory error detector. |
dfe06d3e | 2 | Copyright (C) 2012 Free Software Foundation, Inc. |
37d6f666 WM |
3 | Contributed by Kostya Serebryany <kcc@google.com> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it under | |
8 | the terms of the GNU General Public License as published by the Free | |
9 | Software Foundation; either version 3, or (at your option) any later | |
10 | version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GCC; see the file COPYING3. If not see | |
19 | <http://www.gnu.org/licenses/>. */ | |
20 | ||
21 | ||
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
37d6f666 WM |
25 | #include "gimple.h" |
26 | #include "tree-iterator.h" | |
27 | #include "tree-flow.h" | |
37d6f666 | 28 | #include "tree-pass.h" |
37d6f666 WM |
29 | #include "asan.h" |
30 | #include "gimple-pretty-print.h" | |
dfe06d3e | 31 | #include "target.h" |
37d6f666 WM |
32 | |
33 | /* | |
34 | AddressSanitizer finds out-of-bounds and use-after-free bugs | |
35 | with <2x slowdown on average. | |
36 | ||
37 | The tool consists of two parts: | |
38 | instrumentation module (this file) and a run-time library. | |
39 | The instrumentation module adds a run-time check before every memory insn. | |
40 | For a 8- or 16- byte load accessing address X: | |
41 | ShadowAddr = (X >> 3) + Offset | |
42 | ShadowValue = *(char*)ShadowAddr; // *(short*) for 16-byte access. | |
43 | if (ShadowValue) | |
44 | __asan_report_load8(X); | |
45 | For a load of N bytes (N=1, 2 or 4) from address X: | |
46 | ShadowAddr = (X >> 3) + Offset | |
47 | ShadowValue = *(char*)ShadowAddr; | |
48 | if (ShadowValue) | |
49 | if ((X & 7) + N - 1 > ShadowValue) | |
50 | __asan_report_loadN(X); | |
51 | Stores are instrumented similarly, but using __asan_report_storeN functions. | |
52 | A call too __asan_init() is inserted to the list of module CTORs. | |
53 | ||
54 | The run-time library redefines malloc (so that redzone are inserted around | |
55 | the allocated memory) and free (so that reuse of free-ed memory is delayed), | |
56 | provides __asan_report* and __asan_init functions. | |
57 | ||
58 | Read more: | |
59 | http://code.google.com/p/address-sanitizer/wiki/AddressSanitizerAlgorithm | |
60 | ||
61 | Future work: | |
62 | The current implementation supports only detection of out-of-bounds and | |
63 | use-after-free bugs in heap. | |
64 | In order to support out-of-bounds for stack and globals we will need | |
65 | to create redzones for stack and global object and poison them. | |
66 | */ | |
67 | ||
f6d98484 JJ |
68 | /* Pointer types to 1 resp. 2 byte integers in shadow memory. A separate |
69 | alias set is used for all shadow memory accesses. */ | |
70 | static GTY(()) tree shadow_ptr_types[2]; | |
71 | ||
37d6f666 WM |
72 | /* Construct a function tree for __asan_report_{load,store}{1,2,4,8,16}. |
73 | IS_STORE is either 1 (for a store) or 0 (for a load). | |
74 | SIZE_IN_BYTES is one of 1, 2, 4, 8, 16. */ | |
75 | ||
76 | static tree | |
f6d98484 | 77 | report_error_func (bool is_store, int size_in_bytes) |
37d6f666 WM |
78 | { |
79 | tree fn_type; | |
80 | tree def; | |
81 | char name[100]; | |
82 | ||
f6d98484 | 83 | sprintf (name, "__asan_report_%s%d", |
37d6f666 WM |
84 | is_store ? "store" : "load", size_in_bytes); |
85 | fn_type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE); | |
86 | def = build_fn_decl (name, fn_type); | |
87 | TREE_NOTHROW (def) = 1; | |
88 | TREE_THIS_VOLATILE (def) = 1; /* Attribute noreturn. Surprise! */ | |
89 | DECL_ATTRIBUTES (def) = tree_cons (get_identifier ("leaf"), | |
90 | NULL, DECL_ATTRIBUTES (def)); | |
91 | DECL_ASSEMBLER_NAME (def); | |
92 | return def; | |
93 | } | |
94 | ||
95 | /* Construct a function tree for __asan_init(). */ | |
96 | ||
97 | static tree | |
98 | asan_init_func (void) | |
99 | { | |
100 | tree fn_type; | |
101 | tree def; | |
102 | ||
103 | fn_type = build_function_type_list (void_type_node, NULL_TREE); | |
104 | def = build_fn_decl ("__asan_init", fn_type); | |
105 | TREE_NOTHROW (def) = 1; | |
106 | DECL_ASSEMBLER_NAME (def); | |
107 | return def; | |
108 | } | |
109 | ||
110 | ||
f6d98484 JJ |
111 | #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 2000 - 1) |
112 | #define PROB_ALWAYS (REG_BR_PROB_BASE) | |
113 | ||
37d6f666 WM |
114 | /* Instrument the memory access instruction BASE. |
115 | Insert new statements before ITER. | |
116 | LOCATION is source code location. | |
117 | IS_STORE is either 1 (for a store) or 0 (for a load). | |
118 | SIZE_IN_BYTES is one of 1, 2, 4, 8, 16. */ | |
119 | ||
120 | static void | |
121 | build_check_stmt (tree base, | |
122 | gimple_stmt_iterator *iter, | |
f6d98484 | 123 | location_t location, bool is_store, int size_in_bytes) |
37d6f666 WM |
124 | { |
125 | gimple_stmt_iterator gsi; | |
dfb9e332 | 126 | basic_block cond_bb, then_bb, else_bb; |
37d6f666 | 127 | edge e; |
f6d98484 | 128 | tree t, base_addr, shadow; |
37d6f666 | 129 | gimple g; |
f6d98484 JJ |
130 | tree shadow_ptr_type = shadow_ptr_types[size_in_bytes == 16 ? 1 : 0]; |
131 | tree shadow_type = TREE_TYPE (shadow_ptr_type); | |
132 | tree uintptr_type | |
133 | = build_nonstandard_integer_type (TYPE_PRECISION (TREE_TYPE (base)), 1); | |
37d6f666 WM |
134 | |
135 | /* We first need to split the current basic block, and start altering | |
136 | the CFG. This allows us to insert the statements we're about to | |
137 | construct into the right basic blocks. */ | |
138 | ||
139 | cond_bb = gimple_bb (gsi_stmt (*iter)); | |
140 | gsi = *iter; | |
141 | gsi_prev (&gsi); | |
142 | if (!gsi_end_p (gsi)) | |
143 | e = split_block (cond_bb, gsi_stmt (gsi)); | |
144 | else | |
145 | e = split_block_after_labels (cond_bb); | |
146 | cond_bb = e->src; | |
dfb9e332 | 147 | else_bb = e->dest; |
37d6f666 | 148 | |
dfb9e332 | 149 | /* A recap at this point: else_bb is the basic block at whose head |
37d6f666 WM |
150 | is the gimple statement for which this check expression is being |
151 | built. cond_bb is the (possibly new, synthetic) basic block the | |
152 | end of which will contain the cache-lookup code, and a | |
153 | conditional that jumps to the cache-miss code or, much more | |
dfb9e332 | 154 | likely, over to else_bb. */ |
37d6f666 WM |
155 | |
156 | /* Create the bb that contains the crash block. */ | |
157 | then_bb = create_empty_bb (cond_bb); | |
f6d98484 JJ |
158 | e = make_edge (cond_bb, then_bb, EDGE_TRUE_VALUE); |
159 | e->probability = PROB_VERY_UNLIKELY; | |
dfb9e332 | 160 | make_single_succ_edge (then_bb, else_bb, EDGE_FALLTHRU); |
37d6f666 | 161 | |
dfb9e332 JJ |
162 | /* Mark the pseudo-fallthrough edge from cond_bb to else_bb. */ |
163 | e = find_edge (cond_bb, else_bb); | |
37d6f666 WM |
164 | e->flags = EDGE_FALSE_VALUE; |
165 | e->count = cond_bb->count; | |
f6d98484 | 166 | e->probability = PROB_ALWAYS - PROB_VERY_UNLIKELY; |
37d6f666 WM |
167 | |
168 | /* Update dominance info. Note that bb_join's data was | |
169 | updated by split_block. */ | |
170 | if (dom_info_available_p (CDI_DOMINATORS)) | |
171 | { | |
172 | set_immediate_dominator (CDI_DOMINATORS, then_bb, cond_bb); | |
dfb9e332 | 173 | set_immediate_dominator (CDI_DOMINATORS, else_bb, cond_bb); |
37d6f666 WM |
174 | } |
175 | ||
f6d98484 | 176 | base = unshare_expr (base); |
37d6f666 | 177 | |
f6d98484 JJ |
178 | gsi = gsi_last_bb (cond_bb); |
179 | g = gimple_build_assign_with_ops (TREE_CODE (base), | |
180 | make_ssa_name (TREE_TYPE (base), NULL), | |
181 | base, NULL_TREE); | |
37d6f666 | 182 | gimple_set_location (g, location); |
f6d98484 | 183 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); |
37d6f666 | 184 | |
f6d98484 JJ |
185 | g = gimple_build_assign_with_ops (NOP_EXPR, |
186 | make_ssa_name (uintptr_type, NULL), | |
187 | gimple_assign_lhs (g), NULL_TREE); | |
37d6f666 | 188 | gimple_set_location (g, location); |
f6d98484 JJ |
189 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); |
190 | base_addr = gimple_assign_lhs (g); | |
37d6f666 | 191 | |
f6d98484 JJ |
192 | /* Build |
193 | (base_addr >> ASAN_SHADOW_SHIFT) + targetm.asan_shadow_offset (). */ | |
37d6f666 | 194 | |
f6d98484 JJ |
195 | t = build_int_cst (uintptr_type, ASAN_SHADOW_SHIFT); |
196 | g = gimple_build_assign_with_ops (RSHIFT_EXPR, | |
197 | make_ssa_name (uintptr_type, NULL), | |
198 | base_addr, t); | |
37d6f666 | 199 | gimple_set_location (g, location); |
f6d98484 JJ |
200 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); |
201 | ||
202 | t = build_int_cst (uintptr_type, targetm.asan_shadow_offset ()); | |
203 | g = gimple_build_assign_with_ops (PLUS_EXPR, | |
204 | make_ssa_name (uintptr_type, NULL), | |
205 | gimple_assign_lhs (g), t); | |
37d6f666 | 206 | gimple_set_location (g, location); |
f6d98484 | 207 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); |
37d6f666 | 208 | |
f6d98484 JJ |
209 | g = gimple_build_assign_with_ops (NOP_EXPR, |
210 | make_ssa_name (shadow_ptr_type, NULL), | |
211 | gimple_assign_lhs (g), NULL_TREE); | |
212 | gimple_set_location (g, location); | |
213 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); | |
37d6f666 | 214 | |
f6d98484 JJ |
215 | t = build2 (MEM_REF, shadow_type, gimple_assign_lhs (g), |
216 | build_int_cst (shadow_ptr_type, 0)); | |
217 | g = gimple_build_assign_with_ops (MEM_REF, | |
218 | make_ssa_name (shadow_type, NULL), | |
219 | t, NULL_TREE); | |
220 | gimple_set_location (g, location); | |
221 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); | |
222 | shadow = gimple_assign_lhs (g); | |
223 | ||
224 | if (size_in_bytes < 8) | |
225 | { | |
226 | /* Slow path for 1, 2 and 4 byte accesses. | |
227 | Test (shadow != 0) | |
228 | & ((base_addr & 7) + (size_in_bytes - 1)) >= shadow). */ | |
229 | g = gimple_build_assign_with_ops (NE_EXPR, | |
230 | make_ssa_name (boolean_type_node, | |
231 | NULL), | |
232 | shadow, | |
233 | build_int_cst (shadow_type, 0)); | |
234 | gimple_set_location (g, location); | |
235 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); | |
236 | t = gimple_assign_lhs (g); | |
237 | ||
238 | g = gimple_build_assign_with_ops (BIT_AND_EXPR, | |
239 | make_ssa_name (uintptr_type, | |
240 | NULL), | |
241 | base_addr, | |
242 | build_int_cst (uintptr_type, 7)); | |
243 | gimple_set_location (g, location); | |
244 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); | |
245 | ||
246 | g = gimple_build_assign_with_ops (NOP_EXPR, | |
247 | make_ssa_name (shadow_type, | |
248 | NULL), | |
249 | gimple_assign_lhs (g), NULL_TREE); | |
250 | gimple_set_location (g, location); | |
251 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); | |
252 | ||
253 | if (size_in_bytes > 1) | |
254 | { | |
255 | g = gimple_build_assign_with_ops (PLUS_EXPR, | |
256 | make_ssa_name (shadow_type, | |
257 | NULL), | |
258 | gimple_assign_lhs (g), | |
259 | build_int_cst (shadow_type, | |
260 | size_in_bytes - 1)); | |
261 | gimple_set_location (g, location); | |
262 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); | |
263 | } | |
264 | ||
265 | g = gimple_build_assign_with_ops (GE_EXPR, | |
266 | make_ssa_name (boolean_type_node, | |
267 | NULL), | |
268 | gimple_assign_lhs (g), | |
269 | shadow); | |
270 | gimple_set_location (g, location); | |
271 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); | |
272 | ||
273 | g = gimple_build_assign_with_ops (BIT_AND_EXPR, | |
274 | make_ssa_name (boolean_type_node, | |
275 | NULL), | |
276 | t, gimple_assign_lhs (g)); | |
277 | gimple_set_location (g, location); | |
278 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); | |
279 | t = gimple_assign_lhs (g); | |
280 | } | |
281 | else | |
282 | t = shadow; | |
37d6f666 | 283 | |
f6d98484 JJ |
284 | g = gimple_build_cond (NE_EXPR, t, build_int_cst (TREE_TYPE (t), 0), |
285 | NULL_TREE, NULL_TREE); | |
286 | gimple_set_location (g, location); | |
287 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); | |
37d6f666 | 288 | |
f6d98484 | 289 | /* Generate call to the run-time library (e.g. __asan_report_load8). */ |
37d6f666 | 290 | gsi = gsi_start_bb (then_bb); |
f6d98484 JJ |
291 | g = gimple_build_call (report_error_func (is_store, size_in_bytes), |
292 | 1, base_addr); | |
293 | gimple_set_location (g, location); | |
294 | gsi_insert_after (&gsi, g, GSI_NEW_STMT); | |
37d6f666 | 295 | |
dfb9e332 | 296 | *iter = gsi_start_bb (else_bb); |
37d6f666 WM |
297 | } |
298 | ||
299 | /* If T represents a memory access, add instrumentation code before ITER. | |
300 | LOCATION is source code location. | |
301 | IS_STORE is either 1 (for a store) or 0 (for a load). */ | |
302 | ||
303 | static void | |
304 | instrument_derefs (gimple_stmt_iterator *iter, tree t, | |
f6d98484 | 305 | location_t location, bool is_store) |
37d6f666 WM |
306 | { |
307 | tree type, base; | |
f6d98484 | 308 | HOST_WIDE_INT size_in_bytes; |
37d6f666 WM |
309 | |
310 | type = TREE_TYPE (t); | |
37d6f666 WM |
311 | switch (TREE_CODE (t)) |
312 | { | |
313 | case ARRAY_REF: | |
314 | case COMPONENT_REF: | |
315 | case INDIRECT_REF: | |
316 | case MEM_REF: | |
317 | break; | |
318 | default: | |
319 | return; | |
320 | } | |
f6d98484 JJ |
321 | |
322 | size_in_bytes = int_size_in_bytes (type); | |
323 | if ((size_in_bytes & (size_in_bytes - 1)) != 0 | |
324 | || (unsigned HOST_WIDE_INT) size_in_bytes - 1 >= 16) | |
325 | return; | |
326 | ||
327 | /* For now just avoid instrumenting bit field acceses. | |
37d6f666 WM |
328 | Fixing it is doable, but expected to be messy. */ |
329 | ||
f6d98484 JJ |
330 | HOST_WIDE_INT bitsize, bitpos; |
331 | tree offset; | |
332 | enum machine_mode mode; | |
333 | int volatilep = 0, unsignedp = 0; | |
334 | get_inner_reference (t, &bitsize, &bitpos, &offset, | |
335 | &mode, &unsignedp, &volatilep, false); | |
336 | if (bitpos != 0 || bitsize != size_in_bytes * BITS_PER_UNIT) | |
337 | return; | |
338 | ||
339 | base = build_fold_addr_expr (t); | |
37d6f666 WM |
340 | build_check_stmt (base, iter, location, is_store, size_in_bytes); |
341 | } | |
342 | ||
343 | /* asan: this looks too complex. Can this be done simpler? */ | |
344 | /* Transform | |
345 | 1) Memory references. | |
346 | 2) BUILTIN_ALLOCA calls. | |
347 | */ | |
348 | ||
349 | static void | |
350 | transform_statements (void) | |
351 | { | |
352 | basic_block bb; | |
353 | gimple_stmt_iterator i; | |
354 | int saved_last_basic_block = last_basic_block; | |
37d6f666 WM |
355 | |
356 | FOR_EACH_BB (bb) | |
357 | { | |
358 | if (bb->index >= saved_last_basic_block) continue; | |
359 | for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i)) | |
360 | { | |
361 | gimple s = gsi_stmt (i); | |
f6d98484 JJ |
362 | if (!gimple_assign_single_p (s)) |
363 | continue; | |
37d6f666 | 364 | instrument_derefs (&i, gimple_assign_lhs (s), |
f6d98484 | 365 | gimple_location (s), true); |
37d6f666 | 366 | instrument_derefs (&i, gimple_assign_rhs1 (s), |
f6d98484 | 367 | gimple_location (s), false); |
37d6f666 WM |
368 | } |
369 | } | |
370 | } | |
371 | ||
372 | /* Module-level instrumentation. | |
373 | - Insert __asan_init() into the list of CTORs. | |
374 | - TODO: insert redzones around globals. | |
375 | */ | |
376 | ||
377 | void | |
378 | asan_finish_file (void) | |
379 | { | |
380 | tree ctor_statements = NULL_TREE; | |
381 | append_to_statement_list (build_call_expr (asan_init_func (), 0), | |
382 | &ctor_statements); | |
383 | cgraph_build_static_cdtor ('I', ctor_statements, | |
384 | MAX_RESERVED_INIT_PRIORITY - 1); | |
385 | } | |
386 | ||
f6d98484 JJ |
387 | /* Initialize shadow_ptr_types array. */ |
388 | ||
389 | static void | |
390 | asan_init_shadow_ptr_types (void) | |
391 | { | |
392 | alias_set_type set = new_alias_set (); | |
393 | shadow_ptr_types[0] = build_distinct_type_copy (signed_char_type_node); | |
394 | TYPE_ALIAS_SET (shadow_ptr_types[0]) = set; | |
395 | shadow_ptr_types[0] = build_pointer_type (shadow_ptr_types[0]); | |
396 | shadow_ptr_types[1] = build_distinct_type_copy (short_integer_type_node); | |
397 | TYPE_ALIAS_SET (shadow_ptr_types[1]) = set; | |
398 | shadow_ptr_types[1] = build_pointer_type (shadow_ptr_types[1]); | |
399 | } | |
400 | ||
37d6f666 WM |
401 | /* Instrument the current function. */ |
402 | ||
403 | static unsigned int | |
404 | asan_instrument (void) | |
405 | { | |
f6d98484 JJ |
406 | if (shadow_ptr_types[0] == NULL_TREE) |
407 | asan_init_shadow_ptr_types (); | |
37d6f666 | 408 | transform_statements (); |
37d6f666 WM |
409 | return 0; |
410 | } | |
411 | ||
412 | static bool | |
413 | gate_asan (void) | |
414 | { | |
415 | return flag_asan != 0; | |
416 | } | |
417 | ||
418 | struct gimple_opt_pass pass_asan = | |
419 | { | |
420 | { | |
421 | GIMPLE_PASS, | |
422 | "asan", /* name */ | |
423 | OPTGROUP_NONE, /* optinfo_flags */ | |
424 | gate_asan, /* gate */ | |
425 | asan_instrument, /* execute */ | |
426 | NULL, /* sub */ | |
427 | NULL, /* next */ | |
428 | 0, /* static_pass_number */ | |
429 | TV_NONE, /* tv_id */ | |
430 | PROP_ssa | PROP_cfg | PROP_gimple_leh,/* properties_required */ | |
431 | 0, /* properties_provided */ | |
432 | 0, /* properties_destroyed */ | |
433 | 0, /* todo_flags_start */ | |
434 | TODO_verify_flow | TODO_verify_stmts | |
f6d98484 | 435 | | TODO_update_ssa /* todo_flags_finish */ |
37d6f666 WM |
436 | } |
437 | }; | |
f6d98484 | 438 | |
dfb9e332 JJ |
439 | static bool |
440 | gate_asan_O0 (void) | |
441 | { | |
442 | return flag_asan != 0 && !optimize; | |
443 | } | |
444 | ||
445 | struct gimple_opt_pass pass_asan_O0 = | |
446 | { | |
447 | { | |
448 | GIMPLE_PASS, | |
449 | "asan0", /* name */ | |
450 | OPTGROUP_NONE, /* optinfo_flags */ | |
451 | gate_asan_O0, /* gate */ | |
452 | asan_instrument, /* execute */ | |
453 | NULL, /* sub */ | |
454 | NULL, /* next */ | |
455 | 0, /* static_pass_number */ | |
456 | TV_NONE, /* tv_id */ | |
457 | PROP_ssa | PROP_cfg | PROP_gimple_leh,/* properties_required */ | |
458 | 0, /* properties_provided */ | |
459 | 0, /* properties_destroyed */ | |
460 | 0, /* todo_flags_start */ | |
461 | TODO_verify_flow | TODO_verify_stmts | |
462 | | TODO_update_ssa /* todo_flags_finish */ | |
463 | } | |
464 | }; | |
465 | ||
f6d98484 | 466 | #include "gt-asan.h" |