1/* UndefinedBehaviorSanitizer, undefined behavior detector.
2   Copyright (C) 2013-2015 Free Software Foundation, Inc.
3   Contributed by Marek Polacek <polacek@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3.  If not see
19<http://www.gnu.org/licenses/>.  */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "hash-set.h"
25#include "machmode.h"
26#include "vec.h"
27#include "double-int.h"
28#include "input.h"
29#include "alias.h"
30#include "symtab.h"
31#include "options.h"
32#include "wide-int.h"
33#include "inchash.h"
34#include "tree.h"
35#include "alloc-pool.h"
36#include "hash-map.h"
37#include "is-a.h"
38#include "plugin-api.h"
39#include "vec.h"
40#include "hashtab.h"
41#include "hash-set.h"
42#include "machmode.h"
43#include "tm.h"
44#include "hard-reg-set.h"
45#include "input.h"
46#include "function.h"
47#include "ipa-ref.h"
48#include "cgraph.h"
49#include "output.h"
50#include "toplev.h"
51#include "ubsan.h"
52#include "c-family/c-common.h"
53#include "c-family/c-ubsan.h"
54#include "asan.h"
55#include "internal-fn.h"
56#include "stor-layout.h"
57#include "builtins.h"
58#include "gimplify.h"
59
60/* Instrument division by zero and INT_MIN / -1.  If not instrumenting,
61   return NULL_TREE.  */
62
63tree
64ubsan_instrument_division (location_t loc, tree op0, tree op1)
65{
66  tree t, tt;
67  tree type = TREE_TYPE (op0);
68
69  /* At this point both operands should have the same type,
70     because they are already converted to RESULT_TYPE.
71     Use TYPE_MAIN_VARIANT since typedefs can confuse us.  */
72  gcc_assert (TYPE_MAIN_VARIANT (TREE_TYPE (op0))
73	      == TYPE_MAIN_VARIANT (TREE_TYPE (op1)));
74
75  op0 = unshare_expr (op0);
76  op1 = unshare_expr (op1);
77
78  if (TREE_CODE (type) == INTEGER_TYPE
79      && (flag_sanitize & SANITIZE_DIVIDE))
80    t = fold_build2 (EQ_EXPR, boolean_type_node,
81		     op1, build_int_cst (type, 0));
82  else if (TREE_CODE (type) == REAL_TYPE
83	   && (flag_sanitize & SANITIZE_FLOAT_DIVIDE))
84    t = fold_build2 (EQ_EXPR, boolean_type_node,
85		     op1, build_real (type, dconst0));
86  else
87    return NULL_TREE;
88
89  /* We check INT_MIN / -1 only for signed types.  */
90  if (TREE_CODE (type) == INTEGER_TYPE
91      && (flag_sanitize & SANITIZE_DIVIDE)
92      && !TYPE_UNSIGNED (type))
93    {
94      tree x;
95      tt = fold_build2 (EQ_EXPR, boolean_type_node, op1,
96			build_int_cst (type, -1));
97      x = fold_build2 (EQ_EXPR, boolean_type_node, op0,
98		       TYPE_MIN_VALUE (type));
99      x = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, x, tt);
100      t = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, t, x);
101    }
102
103  /* If the condition was folded to 0, no need to instrument
104     this expression.  */
105  if (integer_zerop (t))
106    return NULL_TREE;
107
108  /* In case we have a SAVE_EXPR in a conditional context, we need to
109     make sure it gets evaluated before the condition.  If the OP0 is
110     an instrumented array reference, mark it as having side effects so
111     it's not folded away.  */
112  if (flag_sanitize & SANITIZE_BOUNDS)
113    {
114      tree xop0 = op0;
115      while (CONVERT_EXPR_P (xop0))
116	xop0 = TREE_OPERAND (xop0, 0);
117      if (TREE_CODE (xop0) == ARRAY_REF)
118	{
119	  TREE_SIDE_EFFECTS (xop0) = 1;
120	  TREE_SIDE_EFFECTS (op0) = 1;
121	}
122    }
123  t = fold_build2 (COMPOUND_EXPR, TREE_TYPE (t), op0, t);
124  t = fold_build2 (COMPOUND_EXPR, TREE_TYPE (t), op1, t);
125  if (flag_sanitize_undefined_trap_on_error)
126    tt = build_call_expr_loc (loc, builtin_decl_explicit (BUILT_IN_TRAP), 0);
127  else
128    {
129      tree data = ubsan_create_data ("__ubsan_overflow_data", 1, &loc,
130				     ubsan_type_descriptor (type), NULL_TREE,
131				     NULL_TREE);
132      data = build_fold_addr_expr_loc (loc, data);
133      enum built_in_function bcode
134	= (flag_sanitize_recover & SANITIZE_DIVIDE)
135	  ? BUILT_IN_UBSAN_HANDLE_DIVREM_OVERFLOW
136	  : BUILT_IN_UBSAN_HANDLE_DIVREM_OVERFLOW_ABORT;
137      tt = builtin_decl_explicit (bcode);
138      tt = build_call_expr_loc (loc, tt, 3, data, ubsan_encode_value (op0),
139				ubsan_encode_value (op1));
140    }
141  t = fold_build3 (COND_EXPR, void_type_node, t, tt, void_node);
142
143  return t;
144}
145
146/* Instrument left and right shifts.  */
147
148tree
149ubsan_instrument_shift (location_t loc, enum tree_code code,
150			tree op0, tree op1)
151{
152  tree t, tt = NULL_TREE;
153  tree type0 = TREE_TYPE (op0);
154  tree type1 = TREE_TYPE (op1);
155  tree op1_utype = unsigned_type_for (type1);
156  HOST_WIDE_INT op0_prec = TYPE_PRECISION (type0);
157  tree uprecm1 = build_int_cst (op1_utype, op0_prec - 1);
158
159  op0 = unshare_expr (op0);
160  op1 = unshare_expr (op1);
161
162  t = fold_convert_loc (loc, op1_utype, op1);
163  t = fold_build2 (GT_EXPR, boolean_type_node, t, uprecm1);
164
165  /* For signed x << y, in C99/C11, the following:
166     (unsigned) x >> (uprecm1 - y)
167     if non-zero, is undefined.  */
168  if (code == LSHIFT_EXPR
169      && !TYPE_UNSIGNED (type0)
170      && flag_isoc99)
171    {
172      tree x = fold_build2 (MINUS_EXPR, op1_utype, uprecm1,
173			    fold_convert (op1_utype, op1));
174      tt = fold_convert_loc (loc, unsigned_type_for (type0), op0);
175      tt = fold_build2 (RSHIFT_EXPR, TREE_TYPE (tt), tt, x);
176      tt = fold_build2 (NE_EXPR, boolean_type_node, tt,
177			build_int_cst (TREE_TYPE (tt), 0));
178    }
179
180  /* For signed x << y, in C++11 and later, the following:
181     x < 0 || ((unsigned) x >> (uprecm1 - y))
182     if > 1, is undefined.  */
183  if (code == LSHIFT_EXPR
184      && !TYPE_UNSIGNED (TREE_TYPE (op0))
185      && (cxx_dialect >= cxx11))
186    {
187      tree x = fold_build2 (MINUS_EXPR, op1_utype, uprecm1,
188			    fold_convert (op1_utype, op1));
189      tt = fold_convert_loc (loc, unsigned_type_for (type0), op0);
190      tt = fold_build2 (RSHIFT_EXPR, TREE_TYPE (tt), tt, x);
191      tt = fold_build2 (GT_EXPR, boolean_type_node, tt,
192			build_int_cst (TREE_TYPE (tt), 1));
193      x = fold_build2 (LT_EXPR, boolean_type_node, op0,
194		       build_int_cst (type0, 0));
195      tt = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, x, tt);
196    }
197
198  /* If the condition was folded to 0, no need to instrument
199     this expression.  */
200  if (integer_zerop (t) && (tt == NULL_TREE || integer_zerop (tt)))
201    return NULL_TREE;
202
203  /* In case we have a SAVE_EXPR in a conditional context, we need to
204     make sure it gets evaluated before the condition.  If the OP0 is
205     an instrumented array reference, mark it as having side effects so
206     it's not folded away.  */
207  if (flag_sanitize & SANITIZE_BOUNDS)
208    {
209      tree xop0 = op0;
210      while (CONVERT_EXPR_P (xop0))
211	xop0 = TREE_OPERAND (xop0, 0);
212      if (TREE_CODE (xop0) == ARRAY_REF)
213	{
214	  TREE_SIDE_EFFECTS (xop0) = 1;
215	  TREE_SIDE_EFFECTS (op0) = 1;
216	}
217    }
218  t = fold_build2 (COMPOUND_EXPR, TREE_TYPE (t), op0, t);
219  t = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, t,
220		   tt ? tt : integer_zero_node);
221
222  if (flag_sanitize_undefined_trap_on_error)
223    tt = build_call_expr_loc (loc, builtin_decl_explicit (BUILT_IN_TRAP), 0);
224  else
225    {
226      tree data = ubsan_create_data ("__ubsan_shift_data", 1, &loc,
227				     ubsan_type_descriptor (type0),
228				     ubsan_type_descriptor (type1), NULL_TREE,
229				     NULL_TREE);
230      data = build_fold_addr_expr_loc (loc, data);
231
232      enum built_in_function bcode
233	= (flag_sanitize_recover & SANITIZE_SHIFT)
234	  ? BUILT_IN_UBSAN_HANDLE_SHIFT_OUT_OF_BOUNDS
235	  : BUILT_IN_UBSAN_HANDLE_SHIFT_OUT_OF_BOUNDS_ABORT;
236      tt = builtin_decl_explicit (bcode);
237      tt = build_call_expr_loc (loc, tt, 3, data, ubsan_encode_value (op0),
238				ubsan_encode_value (op1));
239    }
240  t = fold_build3 (COND_EXPR, void_type_node, t, tt, void_node);
241
242  return t;
243}
244
245/* Instrument variable length array bound.  */
246
247tree
248ubsan_instrument_vla (location_t loc, tree size)
249{
250  tree type = TREE_TYPE (size);
251  tree t, tt;
252
253  t = fold_build2 (LE_EXPR, boolean_type_node, size, build_int_cst (type, 0));
254  if (flag_sanitize_undefined_trap_on_error)
255    tt = build_call_expr_loc (loc, builtin_decl_explicit (BUILT_IN_TRAP), 0);
256  else
257    {
258      tree data = ubsan_create_data ("__ubsan_vla_data", 1, &loc,
259				     ubsan_type_descriptor (type), NULL_TREE,
260				     NULL_TREE);
261      data = build_fold_addr_expr_loc (loc, data);
262      enum built_in_function bcode
263	= (flag_sanitize_recover & SANITIZE_VLA)
264	  ? BUILT_IN_UBSAN_HANDLE_VLA_BOUND_NOT_POSITIVE
265	  : BUILT_IN_UBSAN_HANDLE_VLA_BOUND_NOT_POSITIVE_ABORT;
266      tt = builtin_decl_explicit (bcode);
267      tt = build_call_expr_loc (loc, tt, 2, data, ubsan_encode_value (size));
268    }
269  t = fold_build3 (COND_EXPR, void_type_node, t, tt, void_node);
270
271  return t;
272}
273
274/* Instrument missing return in C++ functions returning non-void.  */
275
276tree
277ubsan_instrument_return (location_t loc)
278{
279  if (flag_sanitize_undefined_trap_on_error)
280    return build_call_expr_loc (loc, builtin_decl_explicit (BUILT_IN_TRAP), 0);
281  /* It is possible that PCH zapped table with definitions of sanitizer
282     builtins.  Reinitialize them if needed.  */
283  initialize_sanitizer_builtins ();
284
285  tree data = ubsan_create_data ("__ubsan_missing_return_data", 1, &loc,
286				 NULL_TREE, NULL_TREE);
287  tree t = builtin_decl_explicit (BUILT_IN_UBSAN_HANDLE_MISSING_RETURN);
288  return build_call_expr_loc (loc, t, 1, build_fold_addr_expr_loc (loc, data));
289}
290
291/* Instrument array bounds for ARRAY_REFs.  We create special builtin,
292   that gets expanded in the sanopt pass, and make an array dimension
293   of it.  ARRAY is the array, *INDEX is an index to the array.
294   Return NULL_TREE if no instrumentation is emitted.
295   IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR.  */
296
297tree
298ubsan_instrument_bounds (location_t loc, tree array, tree *index,
299			 bool ignore_off_by_one)
300{
301  tree type = TREE_TYPE (array);
302  tree domain = TYPE_DOMAIN (type);
303
304  if (domain == NULL_TREE || TYPE_MAX_VALUE (domain) == NULL_TREE)
305    return NULL_TREE;
306
307  tree bound = TYPE_MAX_VALUE (domain);
308  if (ignore_off_by_one)
309    bound = fold_build2 (PLUS_EXPR, TREE_TYPE (bound), bound,
310			 build_int_cst (TREE_TYPE (bound), 1));
311
312  /* Detect flexible array members and suchlike.  */
313  tree base = get_base_address (array);
314  if (TREE_CODE (array) == COMPONENT_REF
315      && base && (TREE_CODE (base) == INDIRECT_REF
316		  || TREE_CODE (base) == MEM_REF))
317    {
318      tree next = NULL_TREE;
319      tree cref = array;
320
321      /* Walk all structs/unions.  */
322      while (TREE_CODE (cref) == COMPONENT_REF)
323	{
324	  if (TREE_CODE (TREE_TYPE (TREE_OPERAND (cref, 0))) == RECORD_TYPE)
325	    for (next = DECL_CHAIN (TREE_OPERAND (cref, 1));
326		 next && TREE_CODE (next) != FIELD_DECL;
327		 next = DECL_CHAIN (next))
328	      ;
329	  if (next)
330	    /* Not a last element.  Instrument it.  */
331	    break;
332	  /* Ok, this is the last field of the structure/union.  But the
333	     aggregate containing the field must be the last field too,
334	     recursively.  */
335	  cref = TREE_OPERAND (cref, 0);
336	}
337      if (!next)
338	/* Don't instrument this flexible array member-like array in non-strict
339	   -fsanitize=bounds mode.  */
340        return NULL_TREE;
341    }
342
343  /* Don't emit instrumentation in the most common cases.  */
344  tree idx = NULL_TREE;
345  if (TREE_CODE (*index) == INTEGER_CST)
346    idx = *index;
347  else if (TREE_CODE (*index) == BIT_AND_EXPR
348	   && TREE_CODE (TREE_OPERAND (*index, 1)) == INTEGER_CST)
349    idx = TREE_OPERAND (*index, 1);
350  if (idx
351      && TREE_CODE (bound) == INTEGER_CST
352      && tree_int_cst_sgn (idx) >= 0
353      && tree_int_cst_le (idx, bound))
354    return NULL_TREE;
355
356  *index = save_expr (*index);
357  /* Create a "(T *) 0" tree node to describe the array type.  */
358  tree zero_with_type = build_int_cst (build_pointer_type (type), 0);
359  return build_call_expr_internal_loc (loc, IFN_UBSAN_BOUNDS,
360				       void_type_node, 3, zero_with_type,
361				       *index, bound);
362}
363
364/* Return true iff T is an array that was instrumented by SANITIZE_BOUNDS.  */
365
366bool
367ubsan_array_ref_instrumented_p (const_tree t)
368{
369  if (TREE_CODE (t) != ARRAY_REF)
370    return false;
371
372  tree op1 = TREE_OPERAND (t, 1);
373  return TREE_CODE (op1) == COMPOUND_EXPR
374	 && TREE_CODE (TREE_OPERAND (op1, 0)) == CALL_EXPR
375	 && CALL_EXPR_FN (TREE_OPERAND (op1, 0)) == NULL_TREE
376	 && CALL_EXPR_IFN (TREE_OPERAND (op1, 0)) == IFN_UBSAN_BOUNDS;
377}
378
379/* Instrument an ARRAY_REF, if it hasn't already been instrumented.
380   IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR.  */
381
382void
383ubsan_maybe_instrument_array_ref (tree *expr_p, bool ignore_off_by_one)
384{
385  if (!ubsan_array_ref_instrumented_p (*expr_p)
386      && do_ubsan_in_current_function ())
387    {
388      tree op0 = TREE_OPERAND (*expr_p, 0);
389      tree op1 = TREE_OPERAND (*expr_p, 1);
390      tree e = ubsan_instrument_bounds (EXPR_LOCATION (*expr_p), op0, &op1,
391					ignore_off_by_one);
392      if (e != NULL_TREE)
393	{
394	  tree t = copy_node (*expr_p);
395	  TREE_OPERAND (t, 1) = build2 (COMPOUND_EXPR, TREE_TYPE (op1),
396					e, op1);
397	  *expr_p = t;
398	}
399    }
400}
401
402static tree
403ubsan_maybe_instrument_reference_or_call (location_t loc, tree op, tree ptype,
404					  enum ubsan_null_ckind ckind)
405{
406  if (!do_ubsan_in_current_function ())
407    return NULL_TREE;
408
409  tree type = TREE_TYPE (ptype);
410  tree orig_op = op;
411  bool instrument = false;
412  unsigned int mina = 0;
413
414  if (flag_sanitize & SANITIZE_ALIGNMENT)
415    {
416      mina = min_align_of_type (type);
417      if (mina <= 1)
418	mina = 0;
419    }
420  while ((TREE_CODE (op) == NOP_EXPR
421	  || TREE_CODE (op) == NON_LVALUE_EXPR)
422	 && TREE_CODE (TREE_TYPE (op)) == POINTER_TYPE)
423    op = TREE_OPERAND (op, 0);
424  if (TREE_CODE (op) == NOP_EXPR
425      && TREE_CODE (TREE_TYPE (op)) == REFERENCE_TYPE)
426    {
427      if (mina && mina > min_align_of_type (TREE_TYPE (TREE_TYPE (op))))
428	instrument = true;
429    }
430  else
431    {
432      if ((flag_sanitize & SANITIZE_NULL) && TREE_CODE (op) == ADDR_EXPR)
433	{
434	  bool strict_overflow_p = false;
435	  /* tree_single_nonzero_warnv_p will not return true for non-weak
436	     non-automatic decls with -fno-delete-null-pointer-checks,
437	     which is disabled during -fsanitize=null.  We don't want to
438	     instrument those, just weak vars though.  */
439	  int save_flag_delete_null_pointer_checks
440	    = flag_delete_null_pointer_checks;
441	  flag_delete_null_pointer_checks = 1;
442	  if (!tree_single_nonzero_warnv_p (op, &strict_overflow_p)
443	      || strict_overflow_p)
444	    instrument = true;
445	  flag_delete_null_pointer_checks
446	    = save_flag_delete_null_pointer_checks;
447	}
448      else if (flag_sanitize & SANITIZE_NULL)
449	instrument = true;
450      if (mina && mina > 1)
451	{
452	  if (!POINTER_TYPE_P (TREE_TYPE (op))
453	      || mina > get_pointer_alignment (op) / BITS_PER_UNIT)
454	    instrument = true;
455	}
456    }
457  if (!instrument)
458    return NULL_TREE;
459  op = save_expr (orig_op);
460  gcc_assert (POINTER_TYPE_P (ptype));
461  if (TREE_CODE (ptype) == REFERENCE_TYPE)
462    ptype = build_pointer_type (TREE_TYPE (ptype));
463  tree kind = build_int_cst (ptype, ckind);
464  tree align = build_int_cst (pointer_sized_int_node, mina);
465  tree call
466    = build_call_expr_internal_loc (loc, IFN_UBSAN_NULL, void_type_node,
467				    3, op, kind, align);
468  TREE_SIDE_EFFECTS (call) = 1;
469  return fold_build2 (COMPOUND_EXPR, TREE_TYPE (op), call, op);
470}
471
472/* Instrument a NOP_EXPR to REFERENCE_TYPE if needed.  */
473
474void
475ubsan_maybe_instrument_reference (tree stmt)
476{
477  tree op = TREE_OPERAND (stmt, 0);
478  op = ubsan_maybe_instrument_reference_or_call (EXPR_LOCATION (stmt), op,
479						 TREE_TYPE (stmt),
480						 UBSAN_REF_BINDING);
481  if (op)
482    TREE_OPERAND (stmt, 0) = op;
483}
484
485/* Instrument a CALL_EXPR to a method if needed.  */
486
487void
488ubsan_maybe_instrument_member_call (tree stmt, bool is_ctor)
489{
490  if (call_expr_nargs (stmt) == 0)
491    return;
492  tree op = CALL_EXPR_ARG (stmt, 0);
493  if (op == error_mark_node
494      || !POINTER_TYPE_P (TREE_TYPE (op)))
495    return;
496  op = ubsan_maybe_instrument_reference_or_call (EXPR_LOCATION (stmt), op,
497						 TREE_TYPE (op),
498						 is_ctor ? UBSAN_CTOR_CALL
499						 : UBSAN_MEMBER_CALL);
500  if (op)
501    CALL_EXPR_ARG (stmt, 0) = op;
502}
503