1 //===- subzero/runtime/szrt_asan.c - AddressSanitizer Runtime -----*- C -*-===//
2 //
3 // The Subzero Code Generator
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief Provides the AddressSanitizer runtime.
12 ///
13 /// Exposes functions for initializing the shadow memory region and managing it
14 /// on loads, stores, and allocations.
15 ///
16 //===----------------------------------------------------------------------===//
17
18 #include <assert.h>
19 #include <errno.h>
20 #include <limits.h>
21 #include <sched.h>
22 #include <stdbool.h>
23 #include <stddef.h>
24 #include <stdint.h>
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include <string.h>
28 #include <sys/mman.h>
29
30 #if _POSIX_THREADS
31
32 #include <pthread.h>
33 typedef pthread_mutex_t mutex_t;
34 #define MUTEX_INITIALIZER (PTHREAD_MUTEX_INITIALIZER)
35 #define MUTEX_LOCK(mutex) (pthread_mutex_lock(&(mutex)))
36 #define MUTEX_UNLOCK(mutex) (pthread_mutex_unlock(&(mutex)))
37
38 #else // !_POSIX_THREADS
39
40 typedef uint32_t mutex_t;
41 #define MUTEX_INITIALIZER (0)
42 #define MUTEX_LOCK(mutex) \
43 while (__sync_swap((mutex), 1) != 0) { \
44 sched_yield(); \
45 }
46 #define MUTEX_UNLOCK(mutex) (__sync_swap((mutex), 0))
47
48 #endif // _POSIX_THREADS
49
50 #define RZ_SIZE (32)
51 #define SHADOW_SCALE_LOG2 (3)
52 #define SHADOW_SCALE ((size_t)1 << SHADOW_SCALE_LOG2)
53 #define DEBUG (0)
54
55 // Assuming 48 bit address space on 64 bit systems
56 #define SHADOW_LENGTH_64 (1u << (48 - SHADOW_SCALE_LOG2))
57 #define SHADOW_LENGTH_32 (1u << (32 - SHADOW_SCALE_LOG2))
58 #define WORD_SIZE (sizeof(uint32_t))
59 #define IS_32_BIT (sizeof(void *) == WORD_SIZE)
60
61 #define SHADOW_OFFSET(p) ((uintptr_t)(p) % SHADOW_SCALE)
62 #define IS_SHADOW_ALIGNED(p) (SHADOW_OFFSET(p) == 0)
63
64 #define MEM2SHADOW(p) (((uintptr_t)(p) >> SHADOW_SCALE_LOG2) + shadow_offset)
65 #define SHADOW2MEM(p) \
66 ((uintptr_t)((char *)(p)-shadow_offset) << SHADOW_SCALE_LOG2)
67
68 #define QUARANTINE_MAX_SIZE ((size_t)1 << 28) // 256 MB
69
70 #define STACK_POISON_VAL ((char)-1)
71 #define HEAP_POISON_VAL ((char)-2)
72 #define GLOBAL_POISON_VAL ((char)-3)
73 #define FREED_POISON_VAL ((char)-4)
74 #define MEMTYPE_INDEX(x) (-1 - (x))
75 static const char *memtype_names[] = {"stack", "heap", "global", "freed"};
76
77 #define ACCESS_LOAD (0)
78 #define ACCESS_STORE (1)
79 static const char *access_names[] = {"load from", "store to"};
80
81 #if DEBUG
82 #define DUMP(args...) \
83 do { \
84 printf(args); \
85 } while (false);
86 #else // !DEBUG
87 #define DUMP(args...)
88 #endif // DEBUG
89
90 static char *shadow_offset = NULL;
91
92 static bool __asan_check(char *, int);
93 static void __asan_error(char *, int, int, void *);
94 static void __asan_get_redzones(char *, char **, char **);
95
96 void __asan_init(int, void **, int *);
97 void __asan_check_load(char *, int);
98 void __asan_check_store(char *, int);
99 void *__asan_malloc(size_t);
100 void *__asan_calloc(size_t, size_t);
101 void *__asan_realloc(char *, size_t);
102 void __asan_free(char *);
103 void __asan_poison(char *, int, char);
104 void __asan_unpoison(char *, int);
105
106 struct quarantine_entry {
107 struct quarantine_entry *next;
108 size_t size;
109 };
110
111 mutex_t quarantine_lock = MUTEX_INITIALIZER;
112 uint64_t quarantine_size = 0;
113 struct quarantine_entry *quarantine_head = NULL;
114 struct quarantine_entry *quarantine_tail = NULL;
115
__asan_error(char * ptr,int size,int access,void * ret_addr)116 static void __asan_error(char *ptr, int size, int access, void *ret_addr) {
117 char *shadow_addr = MEM2SHADOW(ptr);
118 char shadow_val = *shadow_addr;
119 if (shadow_val > 0)
120 shadow_val = *(shadow_addr + 1);
121 assert(access == ACCESS_LOAD || access == ACCESS_STORE);
122 const char *access_name = access_names[access];
123 assert(shadow_val == STACK_POISON_VAL || shadow_val == HEAP_POISON_VAL ||
124 shadow_val == GLOBAL_POISON_VAL || shadow_val == FREED_POISON_VAL);
125 const char *memtype = memtype_names[MEMTYPE_INDEX(shadow_val)];
126 fprintf(stderr, "%p: Illegal %d byte %s %s object at %p\n", ret_addr, size,
127 access_name, memtype, ptr);
128 fprintf(stderr, "(address of __asan_error symbol is %p)\n", __asan_error);
129 abort();
130 }
131
132 // check only the first byte of each word unless strict
__asan_check(char * ptr,int size)133 static bool __asan_check(char *ptr, int size) {
134 assert(size == 1 || size == 2 || size == 4 || size == 8);
135 char *shadow_addr = (char *)MEM2SHADOW(ptr);
136 char shadow_val = *shadow_addr;
137 DUMP("check %d bytes at %p: %p + %d (%d)\n", size, ptr, shadow_addr,
138 (uintptr_t)ptr % SHADOW_SCALE, shadow_val);
139 if (size == SHADOW_SCALE) {
140 return shadow_val == 0;
141 }
142 return shadow_val == 0 || (char)SHADOW_OFFSET(ptr) + size <= shadow_val;
143 }
144
__asan_get_redzones(char * ptr,char ** left,char ** right)145 static void __asan_get_redzones(char *ptr, char **left, char **right) {
146 char *rz_left = ptr - RZ_SIZE;
147 char *rz_right = *(char **)rz_left;
148 if (left != NULL)
149 *left = rz_left;
150 if (right != NULL)
151 *right = rz_right;
152 }
153
__asan_check_load(char * ptr,int size)154 void __asan_check_load(char *ptr, int size) {
155 // aligned single word accesses may be widened single byte accesses, but for
156 // all else use strict check
157 int check_size =
158 (size == WORD_SIZE && (uintptr_t)ptr % WORD_SIZE == 0) ? 1 : size;
159 if (!__asan_check(ptr, check_size))
160 __asan_error(ptr, size, ACCESS_LOAD, __builtin_return_address(0));
161 }
162
__asan_check_store(char * ptr,int size)163 void __asan_check_store(char *ptr, int size) {
164 // stores may never be partially out of bounds so use strict check
165 if (!__asan_check(ptr, size))
166 __asan_error(ptr, size, ACCESS_STORE, __builtin_return_address(0));
167 }
168
__asan_init(int n_rzs,void ** rzs,int * rz_sizes)169 void __asan_init(int n_rzs, void **rzs, int *rz_sizes) {
170 // ensure the redzones are large enough to hold metadata
171 assert(RZ_SIZE >= sizeof(void *) && RZ_SIZE >= sizeof(size_t));
172 assert(shadow_offset == NULL);
173 size_t length = (IS_32_BIT) ? SHADOW_LENGTH_32 : SHADOW_LENGTH_64;
174 int prot = PROT_READ | PROT_WRITE;
175 int flags = MAP_PRIVATE | MAP_ANONYMOUS;
176 int fd = -1;
177 off_t offset = 0;
178 shadow_offset = mmap((void *)length, length, prot, flags, fd, offset);
179 if (shadow_offset == NULL)
180 fprintf(stderr, "unable to allocate shadow memory\n");
181 else
182 DUMP("set up shadow memory at %p\n", shadow_offset);
183 if (mprotect(MEM2SHADOW(shadow_offset), length >> SHADOW_SCALE_LOG2,
184 PROT_NONE))
185 fprintf(stderr, "could not protect bad region\n");
186 else
187 DUMP("protected bad region\n");
188
189 // poison global redzones
190 DUMP("poisioning %d global redzones\n", n_rzs);
191 for (int i = 0; i < n_rzs; i++) {
192 DUMP("(%d) poisoning redzone of size %d at %p\n", i, rz_sizes[i], rzs[i]);
193 __asan_poison(rzs[i], rz_sizes[i], GLOBAL_POISON_VAL);
194 }
195 }
196
__asan_malloc(size_t size)197 void *__asan_malloc(size_t size) {
198 DUMP("malloc() called with size %d\n", size);
199 size_t padding =
200 (IS_SHADOW_ALIGNED(size)) ? 0 : SHADOW_SCALE - SHADOW_OFFSET(size);
201 size_t rz_left_size = RZ_SIZE;
202 size_t rz_right_size = RZ_SIZE + padding;
203 void *rz_left;
204 int err = posix_memalign(&rz_left, SHADOW_SCALE,
205 rz_left_size + size + rz_right_size);
206 if (err != 0) {
207 assert(err == ENOMEM);
208 return NULL;
209 }
210 void *ret = rz_left + rz_left_size;
211 void *rz_right = ret + size;
212 __asan_poison(rz_left, rz_left_size, HEAP_POISON_VAL);
213 __asan_poison(rz_right, rz_right_size, HEAP_POISON_VAL);
214 // record size and location data so we can find it again
215 *(void **)rz_left = rz_right;
216 *(size_t *)rz_right = rz_right_size;
217 assert((uintptr_t)ret % 8 == 0);
218 return ret;
219 }
220
__asan_calloc(size_t nmemb,size_t size)221 void *__asan_calloc(size_t nmemb, size_t size) {
222 size_t alloc_size = nmemb * size;
223 void *ret = __asan_malloc(alloc_size);
224 memset(ret, 0, alloc_size);
225 return ret;
226 }
227
__asan_realloc(char * ptr,size_t size)228 void *__asan_realloc(char *ptr, size_t size) {
229 if (ptr == NULL)
230 return __asan_malloc(size);
231 if (size == 0) {
232 __asan_free(ptr);
233 return NULL;
234 }
235 char *rz_right;
236 __asan_get_redzones(ptr, NULL, &rz_right);
237 size_t old_size = rz_right - ptr;
238 if (size == old_size)
239 return ptr;
240 char *new_alloc = __asan_malloc(size);
241 if (new_alloc == NULL)
242 return NULL;
243 size_t copyable = (size < old_size) ? size : old_size;
244 memcpy(new_alloc, ptr, copyable);
245 __asan_free(ptr);
246 return new_alloc;
247 }
248
__asan_free(char * ptr)249 void __asan_free(char *ptr) {
250 DUMP("free() called on %p\n", ptr);
251 if (ptr == NULL)
252 return;
253 if (*(char *)MEM2SHADOW(ptr) == FREED_POISON_VAL) {
254 fprintf(stderr, "%p: Double free of object at %p\n",
255 __builtin_return_address(0), ptr);
256 fprintf(stderr, "(address of __asan_error symbol is %p)\n", __asan_error);
257 abort();
258 }
259 char *rz_left, *rz_right;
260 __asan_get_redzones(ptr, &rz_left, &rz_right);
261 size_t rz_right_size = *(size_t *)rz_right;
262 size_t total_size = rz_right_size + (rz_right - rz_left);
263 __asan_poison(rz_left, total_size, FREED_POISON_VAL);
264
265 // place allocation in quarantine
266 struct quarantine_entry *entry = (struct quarantine_entry *)rz_left;
267 assert(entry != NULL);
268 entry->next = NULL;
269 entry->size = total_size;
270
271 DUMP("Placing %d bytes at %p in quarantine\n", entry->size, entry);
272 MUTEX_LOCK(&quarantine_lock);
273 if (quarantine_tail != NULL)
274 quarantine_tail->next = entry;
275 quarantine_tail = entry;
276 if (quarantine_head == NULL)
277 quarantine_head = entry;
278 quarantine_size += total_size;
279 DUMP("Quarantine size is %llu\n", quarantine_size);
280
281 // free old objects as necessary
282 while (quarantine_size > QUARANTINE_MAX_SIZE) {
283 struct quarantine_entry *freed = quarantine_head;
284 assert(freed != NULL);
285 __asan_unpoison((char *)freed, freed->size);
286 quarantine_size -= freed->size;
287 quarantine_head = freed->next;
288 DUMP("Releasing %d bytes at %p from quarantine\n", freed->size, freed);
289 DUMP("Quarantine size is %llu\n", quarantine_size);
290 free(freed);
291 }
292 MUTEX_UNLOCK(&quarantine_lock);
293 }
294
__asan_poison(char * ptr,int size,char poison_val)295 void __asan_poison(char *ptr, int size, char poison_val) {
296 char *end = ptr + size;
297 assert(IS_SHADOW_ALIGNED(end));
298 DUMP("poison %d bytes at %p: %p - %p\n", size, ptr, MEM2SHADOW(ptr),
299 MEM2SHADOW(end));
300 size_t offset = SHADOW_OFFSET(ptr);
301 *(char *)MEM2SHADOW(ptr) = (offset == 0) ? poison_val : offset;
302 ptr += SHADOW_OFFSET(size);
303 assert(IS_SHADOW_ALIGNED(ptr));
304 int len = (end - ptr) >> SHADOW_SCALE_LOG2;
305 memset(MEM2SHADOW(ptr), poison_val, len);
306 }
307
__asan_unpoison(char * ptr,int size)308 void __asan_unpoison(char *ptr, int size) {
309 char *end = ptr + size;
310 assert(IS_SHADOW_ALIGNED(end));
311 DUMP("unpoison %d bytes at %p: %p - %p\n", size, ptr, MEM2SHADOW(ptr),
312 MEM2SHADOW(end));
313 *(char *)MEM2SHADOW(ptr) = 0;
314 ptr += SHADOW_OFFSET(size);
315 assert(IS_SHADOW_ALIGNED(ptr));
316 memset(MEM2SHADOW(ptr), 0, (end - ptr) >> SHADOW_SCALE_LOG2);
317 }
318