Implement protection of stack variables

This patch implements the protection of stack variables.

It lays out stack variables as well as the different red zones,
emits some prologue code to populate the shadow memory as to poison
(mark as non-accessible) the regions of the red zones and mark the
regions of stack variables as accessible, and emit some epilogue code
to un-poison (mark as accessible) the regions of red zones right
before the function exits.

	* Makefile.in (asan.o): Depend on $(EXPR_H) $(OPTABS_H).
	(cfgexpand.o): Depend on asan.h.
	* asan.c: Include expr.h and optabs.h.
	(asan_shadow_set): New variable.
	(asan_shadow_cst, asan_emit_stack_protection): New functions.
	(asan_init_shadow_ptr_types): Initialize also asan_shadow_set.
	* cfgexpand.c: Include asan.h.  Define HOST_WIDE_INT heap vector.
	(partition_stack_vars): If i is large alignment and j small
	alignment or vice versa, break out of the loop instead of continue,
	and put the test earlier.  If flag_asan, break out of the loop
	if for small alignment size is different.
	(struct stack_vars_data): New type.
	(expand_stack_vars): Add DATA argument.  Change PRED type to
	function taking size_t argument instead of tree.  Adjust pred
	calls.  Fill DATA in and add needed padding in between variables
	if -faddress-sanitizer.
	(defer_stack_allocation): Defer everything for flag_asan.
	(stack_protect_decl_phase_1, stack_protect_decl_phase_2): Take
	size_t index into stack_vars array instead of the decl directly.
	(asan_decl_phase_3): New function.
	(expand_used_vars): Return var destruction sequence.  Adjust
	expand_stack_vars calls, add another one for flag_asan.  Call
	asan_emit_stack_protection if expand_stack_vars added anything
	to the vectors.
	(expand_gimple_basic_block): Add disable_tail_calls argument.
	(gimple_expand_cfg): Pass true to it if expand_used_vars returned
	non-NULL.  Emit the sequence returned by expand_used_vars after
	return_label.
	* asan.h (asan_emit_stack_protection): New prototype.
	(asan_shadow_set): New decl.
	(ASAN_RED_ZONE_SIZE, ASAN_STACK_MAGIC_LEFT, ASAN_STACK_MAGIC_MIDDLE,
	ASAN_STACK_MAGIC_RIGHT, ASAN_STACK_FRAME_MAGIC): Define.
	(asan_protect_stack_decl): New inline.
	* toplev.c (process_options): Also disable -faddress-sanitizer on
	!FRAME_GROWS_DOWNWARDS targets.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@193436 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 297 insertions, 9 deletions

diff --git a/gcc/asan.c b/gcc/asan.c
index 398b83775e6..b9f27443f52 100644
--- a/gcc/asan.c
+++ b/gcc/asan.c
@@ -29,6 +29,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "asan.h"
 #include "gimple-pretty-print.h"
 #include "target.h"
+#include "expr.h"
+#include "optabs.h"
 
 /*
  AddressSanitizer finds out-of-bounds and use-after-free bugs 
@@ -58,17 +60,303 @@ along with GCC; see the file COPYING3.  If not see
  Read more:
  http://code.google.com/p/address-sanitizer/wiki/AddressSanitizerAlgorithm
 
- Future work:
- The current implementation supports only detection of out-of-bounds and
- use-after-free bugs in heap.
- In order to support out-of-bounds for stack and globals we will need
- to create redzones for stack and global object and poison them.
-*/
+ The current implementation supports detection of out-of-bounds and
+ use-after-free in the heap, on the stack and for global variables.
+
+ [Protection of stack variables]
+
+ To understand how detection of out-of-bounds and use-after-free works
+ for stack variables, lets look at this example on x86_64 where the
+ stack grows downward:
+
+     int
+     foo ()
+     {
+       char a[23] = {0};
+       int b[2] = {0};
+
+       a[5] = 1;
+       b[1] = 2;
+
+       return a[5] + b[1];
+     }
+
+ For this function, the stack protected by asan will be organized as
+ follows, from the top of the stack to the bottom:
+
+ Slot 1/ [red zone of 32 bytes called 'RIGHT RedZone']
+
+ Slot 2/ [8 bytes of red zone, that adds up to the space of 'a' to make
+	  the next slot be 32 bytes aligned; this one is called Partial
+	  Redzone; this 32 bytes alignment is an asan constraint]
+
+ Slot 3/ [24 bytes for variable 'a']
+
+ Slot 4/ [red zone of 32 bytes called 'Middle RedZone']
+
+ Slot 5/ [24 bytes of Partial Red Zone (similar to slot 2]
+
+ Slot 6/ [8 bytes for variable 'b']
+
+ Slot 7/ [32 bytes of Red Zone at the bottom of the stack, called 'LEFT
+	  RedZone']
+
+ The 32 bytes of LEFT red zone at the bottom of the stack can be
+ decomposed as such:
+
+     1/ The first 8 bytes contain a magical asan number that is always
+     0x41B58AB3.
+
+     2/ The following 8 bytes contains a pointer to a string (to be
+     parsed at runtime by the runtime asan library), which format is
+     the following:
+
+      "<function-name> <space> <num-of-variables-on-the-stack>
+      (<32-bytes-aligned-offset-in-bytes-of-variable> <space>
+      <length-of-var-in-bytes> ){n} "
+
+	where '(...){n}' means the content inside the parenthesis occurs 'n'
+	times, with 'n' being the number of variables on the stack.
+
+      3/ The following 16 bytes of the red zone have no particular
+      format.
+
+ The shadow memory for that stack layout is going to look like this:
+
+     - content of shadow memory 8 bytes for slot 7: 0xF1F1F1F1.
+       The F1 byte pattern is a magic number called
+       ASAN_STACK_MAGIC_LEFT and is a way for the runtime to know that
+       the memory for that shadow byte is part of a the LEFT red zone
+       intended to seat at the bottom of the variables on the stack.
+
+     - content of shadow memory 8 bytes for slots 6 and 5:
+       0xF4F4F400.  The F4 byte pattern is a magic number
+       called ASAN_STACK_MAGIC_PARTIAL.  It flags the fact that the
+       memory region for this shadow byte is a PARTIAL red zone
+       intended to pad a variable A, so that the slot following
+       {A,padding} is 32 bytes aligned.
+
+       Note that the fact that the least significant byte of this
+       shadow memory content is 00 means that 8 bytes of its
+       corresponding memory (which corresponds to the memory of
+       variable 'b') is addressable.
+
+     - content of shadow memory 8 bytes for slot 4: 0xF2F2F2F2.
+       The F2 byte pattern is a magic number called
+       ASAN_STACK_MAGIC_MIDDLE.  It flags the fact that the memory
+       region for this shadow byte is a MIDDLE red zone intended to
+       seat between two 32 aligned slots of {variable,padding}.
+
+     - content of shadow memory 8 bytes for slot 3 and 2:
+       0xFFFFFFFFF4000000.  This represents is the concatenation of
+       variable 'a' and the partial red zone following it, like what we
+       had for variable 'b'.  The least significant 3 bytes being 00
+       means that the 3 bytes of variable 'a' are addressable.
+
+     - content of shadow memory 8 bytes for slot 1: 0xFFFFFFFFF3F3F3F3.
+       The F3 byte pattern is a magic number called
+       ASAN_STACK_MAGIC_RIGHT.  It flags the fact that the memory
+       region for this shadow byte is a RIGHT red zone intended to seat
+       at the top of the variables of the stack.
+
+ Note that the real variable layout is done in expand_used_vars in
+ cfgexpand.c.  As far as Address Sanitizer is concerned, it lays out
+ stack variables as well as the different red zones, emits some
+ prologue code to populate the shadow memory as to poison (mark as
+ non-accessible) the regions of the red zones and mark the regions of
+ stack variables as accessible, and emit some epilogue code to
+ un-poison (mark as accessible) the regions of red zones right before
+ the function exits.  */
+
+alias_set_type asan_shadow_set = -1;
 
 /* Pointer types to 1 resp. 2 byte integers in shadow memory.  A separate
    alias set is used for all shadow memory accesses.  */
 static GTY(()) tree shadow_ptr_types[2];
 
+/* Return a CONST_INT representing 4 subsequent shadow memory bytes.  */
+
+static rtx
+asan_shadow_cst (unsigned char shadow_bytes[4])
+{
+  int i;
+  unsigned HOST_WIDE_INT val = 0;
+  gcc_assert (WORDS_BIG_ENDIAN == BYTES_BIG_ENDIAN);
+  for (i = 0; i < 4; i++)
+    val |= (unsigned HOST_WIDE_INT) shadow_bytes[BYTES_BIG_ENDIAN ? 3 - i : i]
+	   << (BITS_PER_UNIT * i);
+  return GEN_INT (trunc_int_for_mode (val, SImode));
+}
+
+/* Insert code to protect stack vars.  The prologue sequence should be emitted
+   directly, epilogue sequence returned.  BASE is the register holding the
+   stack base, against which OFFSETS array offsets are relative to, OFFSETS
+   array contains pairs of offsets in reverse order, always the end offset
+   of some gap that needs protection followed by starting offset,
+   and DECLS is an array of representative decls for each var partition.
+   LENGTH is the length of the OFFSETS array, DECLS array is LENGTH / 2 - 1
+   elements long (OFFSETS include gap before the first variable as well
+   as gaps after each stack variable).  */
+
+rtx
+asan_emit_stack_protection (rtx base, HOST_WIDE_INT *offsets, tree *decls,
+			    int length)
+{
+  rtx shadow_base, shadow_mem, ret, mem;
+  unsigned char shadow_bytes[4];
+  HOST_WIDE_INT base_offset = offsets[length - 1], offset, prev_offset;
+  HOST_WIDE_INT last_offset, last_size;
+  int l;
+  unsigned char cur_shadow_byte = ASAN_STACK_MAGIC_LEFT;
+  static pretty_printer pp;
+  static bool pp_initialized;
+  const char *buf;
+  size_t len;
+  tree str_cst;
+
+  /* First of all, prepare the description string.  */
+  if (!pp_initialized)
+    {
+      pp_construct (&pp, /* prefix */NULL, /* line-width */0);
+      pp_initialized = true;
+    }
+  pp_clear_output_area (&pp);
+  if (DECL_NAME (current_function_decl))
+    pp_base_tree_identifier (&pp, DECL_NAME (current_function_decl));
+  else
+    pp_string (&pp, "<unknown>");
+  pp_space (&pp);
+  pp_decimal_int (&pp, length / 2 - 1);
+  pp_space (&pp);
+  for (l = length - 2; l; l -= 2)
+    {
+      tree decl = decls[l / 2 - 1];
+      pp_wide_integer (&pp, offsets[l] - base_offset);
+      pp_space (&pp);
+      pp_wide_integer (&pp, offsets[l - 1] - offsets[l]);
+      pp_space (&pp);
+      if (DECL_P (decl) && DECL_NAME (decl))
+	{
+	  pp_decimal_int (&pp, IDENTIFIER_LENGTH (DECL_NAME (decl)));
+	  pp_space (&pp);
+	  pp_base_tree_identifier (&pp, DECL_NAME (decl));
+	}
+      else
+	pp_string (&pp, "9 <unknown>");
+      pp_space (&pp);
+    }
+  buf = pp_base_formatted_text (&pp);
+  len = strlen (buf);
+  str_cst = build_string (len + 1, buf);
+  TREE_TYPE (str_cst)
+    = build_array_type (char_type_node, build_index_type (size_int (len)));
+  TREE_READONLY (str_cst) = 1;
+  TREE_STATIC (str_cst) = 1;
+  str_cst = build1 (ADDR_EXPR, build_pointer_type (char_type_node), str_cst);
+
+  /* Emit the prologue sequence.  */
+  base = expand_binop (Pmode, add_optab, base, GEN_INT (base_offset),
+		       NULL_RTX, 1, OPTAB_DIRECT);
+  mem = gen_rtx_MEM (ptr_mode, base);
+  emit_move_insn (mem, GEN_INT (ASAN_STACK_FRAME_MAGIC));
+  mem = adjust_address (mem, VOIDmode, GET_MODE_SIZE (ptr_mode));
+  emit_move_insn (mem, expand_normal (str_cst));
+  shadow_base = expand_binop (Pmode, lshr_optab, base,
+			      GEN_INT (ASAN_SHADOW_SHIFT),
+			      NULL_RTX, 1, OPTAB_DIRECT);
+  shadow_base = expand_binop (Pmode, add_optab, shadow_base,
+			      GEN_INT (targetm.asan_shadow_offset ()),
+			      NULL_RTX, 1, OPTAB_DIRECT);
+  gcc_assert (asan_shadow_set != -1
+	      && (ASAN_RED_ZONE_SIZE >> ASAN_SHADOW_SHIFT) == 4);
+  shadow_mem = gen_rtx_MEM (SImode, shadow_base);
+  set_mem_alias_set (shadow_mem, asan_shadow_set);
+  prev_offset = base_offset;
+  for (l = length; l; l -= 2)
+    {
+      if (l == 2)
+	cur_shadow_byte = ASAN_STACK_MAGIC_RIGHT;
+      offset = offsets[l - 1];
+      if ((offset - base_offset) & (ASAN_RED_ZONE_SIZE - 1))
+	{
+	  int i;
+	  HOST_WIDE_INT aoff
+	    = base_offset + ((offset - base_offset)
+			     & ~(ASAN_RED_ZONE_SIZE - HOST_WIDE_INT_1));
+	  shadow_mem = adjust_address (shadow_mem, VOIDmode,
+				       (aoff - prev_offset)
+				       >> ASAN_SHADOW_SHIFT);
+	  prev_offset = aoff;
+	  for (i = 0; i < 4; i++, aoff += (1 << ASAN_SHADOW_SHIFT))
+	    if (aoff < offset)
+	      {
+		if (aoff < offset - (1 << ASAN_SHADOW_SHIFT) + 1)
+		  shadow_bytes[i] = 0;
+		else
+		  shadow_bytes[i] = offset - aoff;
+	      }
+	    else
+	      shadow_bytes[i] = ASAN_STACK_MAGIC_PARTIAL;
+	  emit_move_insn (shadow_mem, asan_shadow_cst (shadow_bytes));
+	  offset = aoff;
+	}
+      while (offset <= offsets[l - 2] - ASAN_RED_ZONE_SIZE)
+	{
+	  shadow_mem = adjust_address (shadow_mem, VOIDmode,
+				       (offset - prev_offset)
+				       >> ASAN_SHADOW_SHIFT);
+	  prev_offset = offset;
+	  memset (shadow_bytes, cur_shadow_byte, 4);
+	  emit_move_insn (shadow_mem, asan_shadow_cst (shadow_bytes));
+	  offset += ASAN_RED_ZONE_SIZE;
+	}
+      cur_shadow_byte = ASAN_STACK_MAGIC_MIDDLE;
+    }
+  do_pending_stack_adjust ();
+
+  /* Construct epilogue sequence.  */
+  start_sequence ();
+
+  shadow_mem = gen_rtx_MEM (BLKmode, shadow_base);
+  set_mem_alias_set (shadow_mem, asan_shadow_set);
+  prev_offset = base_offset;
+  last_offset = base_offset;
+  last_size = 0;
+  for (l = length; l; l -= 2)
+    {
+      offset = base_offset + ((offsets[l - 1] - base_offset)
+			     & ~(ASAN_RED_ZONE_SIZE - HOST_WIDE_INT_1));
+      if (last_offset + last_size != offset)
+	{
+	  shadow_mem = adjust_address (shadow_mem, VOIDmode,
+				       (last_offset - prev_offset)
+				       >> ASAN_SHADOW_SHIFT);
+	  prev_offset = last_offset;
+	  clear_storage (shadow_mem, GEN_INT (last_size >> ASAN_SHADOW_SHIFT),
+			 BLOCK_OP_NORMAL);
+	  last_offset = offset;
+	  last_size = 0;
+	}
+      last_size += base_offset + ((offsets[l - 2] - base_offset)
+				  & ~(ASAN_RED_ZONE_SIZE - HOST_WIDE_INT_1))
+		   - offset;
+    }
+  if (last_size)
+    {
+      shadow_mem = adjust_address (shadow_mem, VOIDmode,
+				   (last_offset - prev_offset)
+				   >> ASAN_SHADOW_SHIFT);
+      clear_storage (shadow_mem, GEN_INT (last_size >> ASAN_SHADOW_SHIFT),
+		     BLOCK_OP_NORMAL);
+    }
+
+  do_pending_stack_adjust ();
+
+  ret = get_insns ();
+  end_sequence ();
+  return ret;
+}
+
 /* Construct a function tree for __asan_report_{load,store}{1,2,4,8,16}.
    IS_STORE is either 1 (for a store) or 0 (for a load).
    SIZE_IN_BYTES is one of 1, 2, 4, 8, 16.  */
@@ -389,12 +677,12 @@ asan_finish_file (void)
 static void
 asan_init_shadow_ptr_types (void)
 {
-  alias_set_type set = new_alias_set ();
+  asan_shadow_set = new_alias_set ();
   shadow_ptr_types[0] = build_distinct_type_copy (signed_char_type_node);
-  TYPE_ALIAS_SET (shadow_ptr_types[0]) = set;
+  TYPE_ALIAS_SET (shadow_ptr_types[0]) = asan_shadow_set;
   shadow_ptr_types[0] = build_pointer_type (shadow_ptr_types[0]);
   shadow_ptr_types[1] = build_distinct_type_copy (short_integer_type_node);
-  TYPE_ALIAS_SET (shadow_ptr_types[1]) = set;
+  TYPE_ALIAS_SET (shadow_ptr_types[1]) = asan_shadow_set;
   shadow_ptr_types[1] = build_pointer_type (shadow_ptr_types[1]);
 }