Instrumented local variables and implemented runtime.

runtime/szrt_asan.c

Index: runtime/szrt_asan.c
diff --git a/runtime/szrt_asan.c b/runtime/szrt_asan.c
index 9f62e28ef474015e8843a38cea631e0f364396ac..6ae92deb7a61f4454f0bfdbea4be8e1f4b7793d7 100644
--- a/runtime/szrt_asan.c
+++ b/runtime/szrt_asan.c
@@ -16,48 +16,123 @@
 //===----------------------------------------------------------------------===//
 
 #include <assert.h>
+#include <limits.h>
+#include <stdbool.h>
 #include <stddef.h>
+#include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <sys/mman.h>
 
-static __thread int behind_malloc = 0;
+#define RZ_SIZE (32)
+#define MEM2SHADOW(p) (((uintptr_t)(p) >> 3) + shadow_offset)

[Karl, 2016/06/23 21:55:52]

Create a symbolic name for 3 (like kByteLog2). Then replace corresponding uses.

[tlively, 2016/06/24 05:39:21]

Done.

+#define SHADOW2MEM(p) ((uintptr_t)((char *)(p)-shadow_offset) << 3)
+
+// greater than zero iff malloc is in the call stack
+static char *shadow_offset = NULL;
+static __thread bool behind_malloc = false;
+
+void __asan_init(void);
+void __asan_check(char *, int);
+void *__asan_malloc(size_t);
+void __asan_free(char *);
+void __asan_poison(char *, int);
+void __asan_unpoison(char *, int);
 
-// TODO(tlively): Define and implement this library
 void __asan_init(void) {

[Karl, 2016/06/23 21:55:51]

Since __asan_malloc assumes that

   RS_SIZE >= sizeof(void*)

and 

   RS_SIZE >= sizeof(size_t)

Why not add an assert check (with appropriate comment) to verify assumptions?

[tlively, 2016/06/24 05:39:21]

Done.

-  if (behind_malloc == 0)
-    printf("set up shadow memory here\n");
+  assert(shadow_offset == NULL);
+  size_t length = (sizeof(void *) == 4) ? 1 << 29 : 0x0000100000000000;

[Karl, 2016/06/23 21:55:51]

Again, create a symbolic name for 29?
Also, you may want to write the then and else parts as:

       ? size_t(1) << kShadowBoundary32 : size_t(1) << kShadowBoundary64

[tlively, 2016/06/24 05:39:21]

Done.

+  int prot = PROT_READ | PROT_WRITE;
+  int flags = MAP_PRIVATE | MAP_ANONYMOUS;
+  int fd = -1;
+  off_t offset = 0;
+  shadow_offset = mmap((void *)length, length, prot, flags, fd, offset);
+  if (shadow_offset == NULL)
+    fprintf(stderr, "Unable to allocate shadow memory\n");
+  else
+    printf("set up shadow memory at %p\n", shadow_offset);
+  if (mprotect(MEM2SHADOW(shadow_offset), length >> 3, PROT_NONE))
+    fprintf(stderr, "could not protect bad region\n");
+  else
+    printf("protected bad region\n");
 }
 
-void __asan_check(void *addr, int size) {
-  if (behind_malloc == 0)
-    printf("check %d bytes at %p\n", size, addr);
+void __asan_check(char *ptr, int size) {
+  if (behind_malloc)
+    return;
+  printf("check %d bytes at %p\n", size, ptr);
+  char *end = ptr + size;
+  for (; ptr < end; ++ptr) {
+    char shadow = *(char *)MEM2SHADOW(ptr);
+    printf("checking %p with shadow %d\n", ptr, shadow);
+    assert(shadow == 0 || (shadow >= 0 && (uintptr_t)ptr % 8 <= shadow));
+  }
 }
 
 void *__asan_malloc(size_t size) {
-  if (behind_malloc == 0)
-    printf("malloc() called with size %d\n", size);
-  ++behind_malloc;
-  void *ret = malloc(size);
-  --behind_malloc;
-  assert(behind_malloc >= 0);
+  if (behind_malloc)
+    return malloc(size);
+  printf("malloc() called with size %d\n", size);
+  size_t padding = (size % CHAR_BIT == 0) ? 0 : CHAR_BIT - size % CHAR_BIT;
+  size_t rz_left_size = RZ_SIZE;
+  size_t rz_right_size = RZ_SIZE + padding;
+  behind_malloc = true;
+  char *rz_left = malloc(rz_left_size + size + rz_right_size);
+  behind_malloc = false;
+  void *ret = rz_left + rz_left_size;
+  void *rz_right = ret + size;
+  __asan_poison(rz_left, rz_left_size);
+  __asan_poison(rz_right, rz_right_size);
+  // record size and location data so we can find it again
+  *(void **)rz_left = rz_right;

[Karl, 2016/06/23 21:55:52]

Since types like

    (void **)
and
    (size_t *)

occurs multiple times, why not typedef then and given them symbolic names?

[tlively, 2016/06/24 05:39:21]

What sort of names might be appropriate for these types?

+  *(size_t *)rz_right = rz_right_size;
+  assert((uintptr_t)ret % 8 == 0);
   return ret;
 }
 
-void __asan_free(void *ptr) {
-  if (behind_malloc == 0)
-    printf("free() called on %p\n", ptr);
-  ++behind_malloc;
-  free(ptr);
-  --behind_malloc;
-  assert(behind_malloc >= 0);
+void __asan_free(char *ptr) {
+  if (behind_malloc) {
+    free(ptr);
+    return;
+  }
+  printf("free() called on %p\n", ptr);
+  void *rz_left = ptr - RZ_SIZE;
+  void *rz_right = *(void **)rz_left;
+  size_t rz_right_size = *(size_t *)rz_right;
+  __asan_unpoison(rz_left, RZ_SIZE);
+  __asan_unpoison(rz_right, rz_right_size);
+  free(rz_left);
 }
 
-void __asan_alloca(void *ptr, int size) {
-  if (behind_malloc == 0)
-    printf("alloca of %d bytes at %p\n", size, ptr);
+void __asan_poison(char *ptr, int size) {
+  char *end = ptr + size;
+  assert((uintptr_t)end % 8 == 0);

[Karl, 2016/06/23 21:55:52]

CHAR_BIT instead of 8?

Also, consider defining a macro for this (byte-aligned) test, so that it it more
readable?

Maybe IS_BYTE_ALIGNED?

[tlively, 2016/06/24 05:39:22]

Done.

+  assert(size < 64);

[Karl, 2016/06/23 21:55:52]

Why the magic number 64?

[tlively, 2016/06/24 05:39:21]

Done.

+  if (behind_malloc)
+    return;
+  printf("poison %d bytes at %p: %p - %p\n", size, ptr, MEM2SHADOW(ptr),
+         MEM2SHADOW(end));
+  size_t offset = (uintptr_t)ptr % 8;
+  *(char *)MEM2SHADOW(ptr) = (offset) == 0 ? -1 : offset;
+  ptr += size % 8;

[Karl, 2016/06/23 21:55:52]

How about defining a macro for cases of (X % 8) and use it everywhere it occurs?

[tlively, 2016/06/24 05:39:22]

Done.

+  assert((uintptr_t)ptr % 8 == 0);
+  for (; ptr != end; ptr += 8) {
+    *(char *)MEM2SHADOW(ptr) = -1;
+  }
 }
 
-void __asan_unalloca(void *ptr, int size) {
-  if (behind_malloc == 0)
-    printf("unalloca of %d bytes as %p\n", size, ptr);
+void __asan_unpoison(char *ptr, int size) {
+  char *end = ptr + size;
+  assert((uintptr_t)end % 8 == 0);
+  assert(size < 64);
+  if (behind_malloc)
+    return;
+  printf("unpoison %d bytes at %p: %p - %p\n", size, ptr, MEM2SHADOW(ptr),
+         MEM2SHADOW(end));
+  *(char *)MEM2SHADOW(ptr) = 0;
+  ptr += size % 8;
+  assert((uintptr_t)ptr % 8 == 0);
+  for (; ptr != end; ptr += 8) {
+    *(char *)MEM2SHADOW(ptr) = 0;
+  }
 }

[Karl, 2016/06/23 21:55:51]

In general, this code looks right. However, it is hard to read because it has
lots of low-level calculations and casts. Try to clean this up
by adding macros that capture common usages, so that it is easier to read.

[tlively, 2016/06/24 05:39:21]

Done, and with the changes I briefly tested changing the scale and redzone size
and that worked well.