Subzero: Added ASan quarantine for recently freed objects

runtime/szrt_asan.c

 //===- subzero/runtime/szrt_asan.c - AddressSanitizer Runtime -----*- C -*-===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief Provides the AddressSanitizer runtime.
 ///
 /// Exposes functions for initializing the shadow memory region and managing it
 /// on loads, stores, and allocations.
 ///
 //===----------------------------------------------------------------------===//
 
 #include <assert.h>
 #include <errno.h>
 #include <limits.h>
+#include <sched.h>
 #include <stdbool.h>
 #include <stddef.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <sys/mman.h>
 
+#if _POSIX_THREADS
+
+#include <pthread.h>
+typedef pthread_mutex_t mutex_t;
+#define MUTEX_INITIALIZER (PTHREAD_MUTEX_INITIALIZER)
+#define MUTEX_LOCK(mutex) (pthread_mutex_lock(&(mutex)))
+#define MUTEX_UNLOCK(mutex) (pthread_mutex_unlock(&(mutex)))
+
+#else // !_POSIX_THREADS
+
+typedef uint32_t mutex_t;
+#define MUTEX_INITIALIZER (0)
+#define MUTEX_LOCK(mutex)                                                      \
+  while (__sync_swap((mutex), 1) != 0) {                                       \
+    sched_yield();                                                             \
+  }
+#define MUTEX_UNLOCK(mutex) (__sync_swap((mutex), 0))
+
+#endif // _POSIX_THREADS
+
 #define RZ_SIZE (32)
 #define SHADOW_SCALE_LOG2 (3)
 #define SHADOW_SCALE ((size_t)1 << SHADOW_SCALE_LOG2)
-#define DEBUG (0)
+#define DEBUG (1)
 
 // Assuming 48 bit address space on 64 bit systems
 #define SHADOW_LENGTH_64 (1u << (48 - SHADOW_SCALE_LOG2))
 #define SHADOW_LENGTH_32 (1u << (32 - SHADOW_SCALE_LOG2))
 #define WORD_SIZE (sizeof(uint32_t))
 #define IS_32_BIT (sizeof(void *) == WORD_SIZE)
 
 #define SHADOW_OFFSET(p) ((uintptr_t)(p) % SHADOW_SCALE)
 #define IS_SHADOW_ALIGNED(p) (SHADOW_OFFSET(p) == 0)
 
 #define MEM2SHADOW(p) (((uintptr_t)(p) >> SHADOW_SCALE_LOG2) + shadow_offset)
 #define SHADOW2MEM(p)                                                          \
   ((uintptr_t)((char *)(p)-shadow_offset) << SHADOW_SCALE_LOG2)
 
+#define QUARANTINE_MAX_SIZE ((size_t)1 << 28) // 256 MB
+
 #define STACK_POISON_VAL ((char)-1)
 #define HEAP_POISON_VAL ((char)-2)
 #define GLOBAL_POISON_VAL ((char)-3)
+#define FREED_POISON_VAL ((char)-4)
 #define MEMTYPE_INDEX(x) (-1 - (x))
-static const char *memtype_names[] = {"stack", "heap", "global"};
+static const char *memtype_names[] = {"stack", "heap", "global", "freed"};
 
 #define ACCESS_LOAD (0)
 #define ACCESS_STORE (1)
 static const char *access_names[] = {"load from", "store to"};
 
 #if DEBUG
 #define DUMP(args...)                                                          \
   do {                                                                         \
     printf(args);                                                              \
   } while (false);
@@ skipping 10 matching lines @@
 void __asan_init(int, void **, int *);
 void __asan_check_load(char *, int);
 void __asan_check_store(char *, int);
 void *__asan_malloc(size_t);
 void *__asan_calloc(size_t, size_t);
 void *__asan_realloc(char *, size_t);
 void __asan_free(char *);
 void __asan_poison(char *, int, char);
 void __asan_unpoison(char *, int);
 
+struct quarantine_entry {
+  struct quarantine_entry *next;
+  size_t size;
+};
+
+mutex_t quarantine_lock = MUTEX_INITIALIZER;
+uint64_t quarantine_size = 0;
+struct quarantine_entry *quarantine_head = NULL;
+struct quarantine_entry *quarantine_tail = NULL;
+
 static void __asan_error(char *ptr, int size, int access) {
   char *shadow_addr = MEM2SHADOW(ptr);
   char shadow_val = *shadow_addr;
   if (shadow_val > 0)
     shadow_val = *(shadow_addr + 1);
   assert(access == ACCESS_LOAD || access == ACCESS_STORE);
   const char *access_name = access_names[access];
   assert(shadow_val == STACK_POISON_VAL || shadow_val == HEAP_POISON_VAL ||
-         shadow_val == GLOBAL_POISON_VAL);
+         shadow_val == GLOBAL_POISON_VAL || shadow_val == FREED_POISON_VAL);
   const char *memtype = memtype_names[MEMTYPE_INDEX(shadow_val)];
   fprintf(stderr, "Illegal %d byte %s %s object at %p\n", size, access_name,
           memtype, ptr);
   abort();
 }
 
 // check only the first byte of each word unless strict
 static bool __asan_check(char *ptr, int size) {
   assert(size == 1 || size == 2 || size == 4 || size == 8);
   char *shadow_addr = (char *)MEM2SHADOW(ptr);
@@ skipping 105 matching lines @@
   if (new_alloc == NULL)
     return NULL;
   size_t copyable = (size < old_size) ? size : old_size;
   memcpy(new_alloc, ptr, copyable);
   __asan_free(ptr);
   return new_alloc;
 }
 
 void __asan_free(char *ptr) {
   DUMP("free() called on %p\n", ptr);
+  if (ptr == NULL)
+    return;
+  if (*(char *)MEM2SHADOW(ptr) == FREED_POISON_VAL) {
+    fprintf(stderr, "Double free of object at %p\n", ptr);
+    abort();
+  }
   char *rz_left, *rz_right;
   __asan_get_redzones(ptr, &rz_left, &rz_right);
   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);
+  size_t total_size = rz_right_size + (rz_right - rz_left);
+  __asan_poison(rz_left, total_size, FREED_POISON_VAL);
+
+  // place allocation in quarantine
+  struct quarantine_entry *entry = (struct quarantine_entry *)rz_left;
+  assert(entry != NULL);
+  entry->next = NULL;
+  entry->size = total_size;
+
+  DUMP("Placing %d bytes at %p in quarantine\n", entry->size, entry);
+  MUTEX_LOCK(&quarantine_lock);
+  if (quarantine_tail != NULL)
+    quarantine_tail->next = entry;
+  quarantine_tail = entry;
+  if (quarantine_head == NULL)
+    quarantine_head = entry;
+  quarantine_size += total_size;
+  DUMP("Quarantine size is %llu\n", quarantine_size);
+
+  // free old objects as necessary
+  while (quarantine_size > QUARANTINE_MAX_SIZE) {
+    struct quarantine_entry *freed = quarantine_head;
+    assert(freed != NULL);
+    __asan_unpoison((char *)freed, freed->size);
+    quarantine_size -= freed->size;
+    quarantine_head = freed->next;
+    DUMP("Releasing %d bytes at %p from quarantine\n", freed->size, freed);
+    DUMP("Quarantine size is %llu\n", quarantine_size);
+    free(freed);
+  }
+  MUTEX_UNLOCK(&quarantine_lock);
 }
 
 void __asan_poison(char *ptr, int size, char poison_val) {
   char *end = ptr + size;
   assert(IS_SHADOW_ALIGNED(end));
-  // redzones should be no greater than RZ_SIZE + RZ_SIZE-1 for alignment
-  assert(size < 2 * RZ_SIZE);
   DUMP("poison %d bytes at %p: %p - %p\n", size, ptr, MEM2SHADOW(ptr),
        MEM2SHADOW(end));
   size_t offset = SHADOW_OFFSET(ptr);
   *(char *)MEM2SHADOW(ptr) = (offset == 0) ? poison_val : offset;
   ptr += SHADOW_OFFSET(size);
   assert(IS_SHADOW_ALIGNED(ptr));
   int len = (end - ptr) >> SHADOW_SCALE_LOG2;
   memset(MEM2SHADOW(ptr), poison_val, len);
 }
 
 void __asan_unpoison(char *ptr, int size) {
   char *end = ptr + size;
   assert(IS_SHADOW_ALIGNED(end));
-  assert(size < 2 * RZ_SIZE);
   DUMP("unpoison %d bytes at %p: %p - %p\n", size, ptr, MEM2SHADOW(ptr),
        MEM2SHADOW(end));
   *(char *)MEM2SHADOW(ptr) = 0;
   ptr += SHADOW_OFFSET(size);
   assert(IS_SHADOW_ALIGNED(ptr));
   memset(MEM2SHADOW(ptr), 0, (end - ptr) >> SHADOW_SCALE_LOG2);
 }