1 //===-- hwasan_allocator.cpp ------------------------ ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file is a part of HWAddressSanitizer.
10 //
11 // HWAddressSanitizer allocator.
12 //===----------------------------------------------------------------------===//
13 
14 #include "sanitizer_common/sanitizer_atomic.h"
15 #include "sanitizer_common/sanitizer_errno.h"
16 #include "sanitizer_common/sanitizer_stackdepot.h"
17 #include "hwasan.h"
18 #include "hwasan_allocator.h"
19 #include "hwasan_mapping.h"
20 #include "hwasan_malloc_bisect.h"
21 #include "hwasan_thread.h"
22 #include "hwasan_report.h"
23 
24 #if HWASAN_WITH_INTERCEPTORS
25 DEFINE_REAL(void *, realloc, void *ptr, uptr size)
26 DEFINE_REAL(void, free, void *ptr)
27 #endif
28 
29 namespace __hwasan {
30 
31 static Allocator allocator;
32 static AllocatorCache fallback_allocator_cache;
33 static SpinMutex fallback_mutex;
34 static atomic_uint8_t hwasan_allocator_tagging_enabled;
35 
36 static const tag_t kFallbackAllocTag = 0xBB;
37 static const tag_t kFallbackFreeTag = 0xBC;
38 
39 enum RightAlignMode {
40   kRightAlignNever,
41   kRightAlignSometimes,
42   kRightAlignAlways
43 };
44 
45 // These two variables are initialized from flags()->malloc_align_right
46 // in HwasanAllocatorInit and are never changed afterwards.
47 static RightAlignMode right_align_mode = kRightAlignNever;
48 static bool right_align_8 = false;
49 
50 // Initialized in HwasanAllocatorInit, an never changed.
51 static ALIGNED(16) u8 tail_magic[kShadowAlignment];
52 
53 bool HwasanChunkView::IsAllocated() const {
54   return metadata_ && metadata_->alloc_context_id && metadata_->requested_size;
55 }
56 
57 // Aligns the 'addr' right to the granule boundary.
58 static uptr AlignRight(uptr addr, uptr requested_size) {
59   uptr tail_size = requested_size % kShadowAlignment;
60   if (!tail_size) return addr;
61   if (right_align_8)
62     return tail_size > 8 ? addr : addr + 8;
63   return addr + kShadowAlignment - tail_size;
64 }
65 
66 uptr HwasanChunkView::Beg() const {
67   if (metadata_ && metadata_->right_aligned)
68     return AlignRight(block_, metadata_->requested_size);
69   return block_;
70 }
71 uptr HwasanChunkView::End() const {
72   return Beg() + UsedSize();
73 }
74 uptr HwasanChunkView::UsedSize() const {
75   return metadata_->requested_size;
76 }
77 u32 HwasanChunkView::GetAllocStackId() const {
78   return metadata_->alloc_context_id;
79 }
80 
81 uptr HwasanChunkView::ActualSize() const {
82   return allocator.GetActuallyAllocatedSize(reinterpret_cast<void *>(block_));
83 }
84 
85 bool HwasanChunkView::FromSmallHeap() const {
86   return allocator.FromPrimary(reinterpret_cast<void *>(block_));
87 }
88 
89 void GetAllocatorStats(AllocatorStatCounters s) {
90   allocator.GetStats(s);
91 }
92 
93 void HwasanAllocatorInit() {
94   atomic_store_relaxed(&hwasan_allocator_tagging_enabled,
95                        !flags()->disable_allocator_tagging);
96   SetAllocatorMayReturnNull(common_flags()->allocator_may_return_null);
97   allocator.Init(common_flags()->allocator_release_to_os_interval_ms);
98   switch (flags()->malloc_align_right) {
99     case 0: break;
100     case 1:
101       right_align_mode = kRightAlignSometimes;
102       right_align_8 = false;
103       break;
104     case 2:
105       right_align_mode = kRightAlignAlways;
106       right_align_8 = false;
107       break;
108     case 8:
109       right_align_mode = kRightAlignSometimes;
110       right_align_8 = true;
111       break;
112     case 9:
113       right_align_mode = kRightAlignAlways;
114       right_align_8 = true;
115       break;
116     default:
117       Report("ERROR: unsupported value of malloc_align_right flag: %d\n",
118              flags()->malloc_align_right);
119       Die();
120   }
121   for (uptr i = 0; i < kShadowAlignment; i++)
122     tail_magic[i] = GetCurrentThread()->GenerateRandomTag();
123 }
124 
125 void AllocatorSwallowThreadLocalCache(AllocatorCache *cache) {
126   allocator.SwallowCache(cache);
127 }
128 
129 static uptr TaggedSize(uptr size) {
130   if (!size) size = 1;
131   uptr new_size = RoundUpTo(size, kShadowAlignment);
132   CHECK_GE(new_size, size);
133   return new_size;
134 }
135 
136 static void *HwasanAllocate(StackTrace *stack, uptr orig_size, uptr alignment,
137                             bool zeroise) {
138   if (orig_size > kMaxAllowedMallocSize) {
139     if (AllocatorMayReturnNull()) {
140       Report("WARNING: HWAddressSanitizer failed to allocate 0x%zx bytes\n",
141              orig_size);
142       return nullptr;
143     }
144     ReportAllocationSizeTooBig(orig_size, kMaxAllowedMallocSize, stack);
145   }
146 
147   alignment = Max(alignment, kShadowAlignment);
148   uptr size = TaggedSize(orig_size);
149   Thread *t = GetCurrentThread();
150   void *allocated;
151   if (t) {
152     allocated = allocator.Allocate(t->allocator_cache(), size, alignment);
153   } else {
154     SpinMutexLock l(&fallback_mutex);
155     AllocatorCache *cache = &fallback_allocator_cache;
156     allocated = allocator.Allocate(cache, size, alignment);
157   }
158   if (UNLIKELY(!allocated)) {
159     SetAllocatorOutOfMemory();
160     if (AllocatorMayReturnNull())
161       return nullptr;
162     ReportOutOfMemory(size, stack);
163   }
164   Metadata *meta =
165       reinterpret_cast<Metadata *>(allocator.GetMetaData(allocated));
166   meta->requested_size = static_cast<u32>(orig_size);
167   meta->alloc_context_id = StackDepotPut(*stack);
168   meta->right_aligned = false;
169   if (zeroise) {
170     internal_memset(allocated, 0, size);
171   } else if (flags()->max_malloc_fill_size > 0) {
172     uptr fill_size = Min(size, (uptr)flags()->max_malloc_fill_size);
173     internal_memset(allocated, flags()->malloc_fill_byte, fill_size);
174   }
175   if (!right_align_mode)
176     internal_memcpy(reinterpret_cast<u8 *>(allocated) + orig_size, tail_magic,
177                     size - orig_size);
178 
179   void *user_ptr = allocated;
180   // Tagging can only be skipped when both tag_in_malloc and tag_in_free are
181   // false. When tag_in_malloc = false and tag_in_free = true malloc needs to
182   // retag to 0.
183   if ((flags()->tag_in_malloc || flags()->tag_in_free) &&
184       atomic_load_relaxed(&hwasan_allocator_tagging_enabled)) {
185     tag_t tag = flags()->tag_in_malloc && malloc_bisect(stack, orig_size)
186                     ? (t ? t->GenerateRandomTag() : kFallbackAllocTag)
187                     : 0;
188     user_ptr = (void *)TagMemoryAligned((uptr)user_ptr, size, tag);
189   }
190 
191   if ((orig_size % kShadowAlignment) && (alignment <= kShadowAlignment) &&
192       right_align_mode) {
193     uptr as_uptr = reinterpret_cast<uptr>(user_ptr);
194     if (right_align_mode == kRightAlignAlways ||
195         GetTagFromPointer(as_uptr) & 1) {  // use a tag bit as a random bit.
196       user_ptr = reinterpret_cast<void *>(AlignRight(as_uptr, orig_size));
197       meta->right_aligned = 1;
198     }
199   }
200 
201   HWASAN_MALLOC_HOOK(user_ptr, size);
202   return user_ptr;
203 }
204 
205 static bool PointerAndMemoryTagsMatch(void *tagged_ptr) {
206   CHECK(tagged_ptr);
207   tag_t ptr_tag = GetTagFromPointer(reinterpret_cast<uptr>(tagged_ptr));
208   tag_t mem_tag = *reinterpret_cast<tag_t *>(
209       MemToShadow(reinterpret_cast<uptr>(UntagPtr(tagged_ptr))));
210   return ptr_tag == mem_tag;
211 }
212 
213 static void HwasanDeallocate(StackTrace *stack, void *tagged_ptr) {
214   CHECK(tagged_ptr);
215   HWASAN_FREE_HOOK(tagged_ptr);
216 
217   if (!PointerAndMemoryTagsMatch(tagged_ptr))
218     ReportInvalidFree(stack, reinterpret_cast<uptr>(tagged_ptr));
219 
220   void *untagged_ptr = UntagPtr(tagged_ptr);
221   void *aligned_ptr = reinterpret_cast<void *>(
222       RoundDownTo(reinterpret_cast<uptr>(untagged_ptr), kShadowAlignment));
223   Metadata *meta =
224       reinterpret_cast<Metadata *>(allocator.GetMetaData(aligned_ptr));
225   uptr orig_size = meta->requested_size;
226   u32 free_context_id = StackDepotPut(*stack);
227   u32 alloc_context_id = meta->alloc_context_id;
228 
229   // Check tail magic.
230   uptr tagged_size = TaggedSize(orig_size);
231   if (flags()->free_checks_tail_magic && !right_align_mode && orig_size) {
232     uptr tail_size = tagged_size - orig_size;
233     CHECK_LT(tail_size, kShadowAlignment);
234     void *tail_beg = reinterpret_cast<void *>(
235         reinterpret_cast<uptr>(aligned_ptr) + orig_size);
236     if (tail_size && internal_memcmp(tail_beg, tail_magic, tail_size))
237       ReportTailOverwritten(stack, reinterpret_cast<uptr>(tagged_ptr),
238                             orig_size, tail_size, tail_magic);
239   }
240 
241   meta->requested_size = 0;
242   meta->alloc_context_id = 0;
243   // This memory will not be reused by anyone else, so we are free to keep it
244   // poisoned.
245   Thread *t = GetCurrentThread();
246   if (flags()->max_free_fill_size > 0) {
247     uptr fill_size =
248         Min(TaggedSize(orig_size), (uptr)flags()->max_free_fill_size);
249     internal_memset(aligned_ptr, flags()->free_fill_byte, fill_size);
250   }
251   if (flags()->tag_in_free && malloc_bisect(stack, 0) &&
252       atomic_load_relaxed(&hwasan_allocator_tagging_enabled))
253     TagMemoryAligned(reinterpret_cast<uptr>(aligned_ptr), TaggedSize(orig_size),
254                      t ? t->GenerateRandomTag() : kFallbackFreeTag);
255   if (t) {
256     allocator.Deallocate(t->allocator_cache(), aligned_ptr);
257     if (auto *ha = t->heap_allocations())
258       ha->push({reinterpret_cast<uptr>(tagged_ptr), alloc_context_id,
259                 free_context_id, static_cast<u32>(orig_size)});
260   } else {
261     SpinMutexLock l(&fallback_mutex);
262     AllocatorCache *cache = &fallback_allocator_cache;
263     allocator.Deallocate(cache, aligned_ptr);
264   }
265 }
266 
267 static void *HwasanReallocate(StackTrace *stack, void *tagged_ptr_old,
268                               uptr new_size, uptr alignment) {
269   if (!PointerAndMemoryTagsMatch(tagged_ptr_old))
270     ReportInvalidFree(stack, reinterpret_cast<uptr>(tagged_ptr_old));
271 
272   void *tagged_ptr_new =
273       HwasanAllocate(stack, new_size, alignment, false /*zeroise*/);
274   if (tagged_ptr_old && tagged_ptr_new) {
275     void *untagged_ptr_old =  UntagPtr(tagged_ptr_old);
276     Metadata *meta =
277         reinterpret_cast<Metadata *>(allocator.GetMetaData(untagged_ptr_old));
278     internal_memcpy(UntagPtr(tagged_ptr_new), untagged_ptr_old,
279                     Min(new_size, static_cast<uptr>(meta->requested_size)));
280     HwasanDeallocate(stack, tagged_ptr_old);
281   }
282   return tagged_ptr_new;
283 }
284 
285 static void *HwasanCalloc(StackTrace *stack, uptr nmemb, uptr size) {
286   if (UNLIKELY(CheckForCallocOverflow(size, nmemb))) {
287     if (AllocatorMayReturnNull())
288       return nullptr;
289     ReportCallocOverflow(nmemb, size, stack);
290   }
291   return HwasanAllocate(stack, nmemb * size, sizeof(u64), true);
292 }
293 
294 HwasanChunkView FindHeapChunkByAddress(uptr address) {
295   void *block = allocator.GetBlockBegin(reinterpret_cast<void*>(address));
296   if (!block)
297     return HwasanChunkView();
298   Metadata *metadata =
299       reinterpret_cast<Metadata*>(allocator.GetMetaData(block));
300   return HwasanChunkView(reinterpret_cast<uptr>(block), metadata);
301 }
302 
303 static uptr AllocationSize(const void *tagged_ptr) {
304   const void *untagged_ptr = UntagPtr(tagged_ptr);
305   if (!untagged_ptr) return 0;
306   const void *beg = allocator.GetBlockBegin(untagged_ptr);
307   Metadata *b = (Metadata *)allocator.GetMetaData(untagged_ptr);
308   if (b->right_aligned) {
309     if (beg != reinterpret_cast<void *>(RoundDownTo(
310                    reinterpret_cast<uptr>(untagged_ptr), kShadowAlignment)))
311       return 0;
312   } else {
313     if (beg != untagged_ptr) return 0;
314   }
315   return b->requested_size;
316 }
317 
318 void *hwasan_malloc(uptr size, StackTrace *stack) {
319   return SetErrnoOnNull(HwasanAllocate(stack, size, sizeof(u64), false));
320 }
321 
322 void *hwasan_calloc(uptr nmemb, uptr size, StackTrace *stack) {
323   return SetErrnoOnNull(HwasanCalloc(stack, nmemb, size));
324 }
325 
326 void *hwasan_realloc(void *ptr, uptr size, StackTrace *stack) {
327   if (!ptr)
328     return SetErrnoOnNull(HwasanAllocate(stack, size, sizeof(u64), false));
329 
330 #if HWASAN_WITH_INTERCEPTORS
331   // A tag of 0 means that this is a system allocator allocation, so we must use
332   // the system allocator to realloc it.
333   if (!flags()->disable_allocator_tagging && GetTagFromPointer((uptr)ptr) == 0)
334     return REAL(realloc)(ptr, size);
335 #endif
336 
337   if (size == 0) {
338     HwasanDeallocate(stack, ptr);
339     return nullptr;
340   }
341   return SetErrnoOnNull(HwasanReallocate(stack, ptr, size, sizeof(u64)));
342 }
343 
344 void *hwasan_valloc(uptr size, StackTrace *stack) {
345   return SetErrnoOnNull(
346       HwasanAllocate(stack, size, GetPageSizeCached(), false));
347 }
348 
349 void *hwasan_pvalloc(uptr size, StackTrace *stack) {
350   uptr PageSize = GetPageSizeCached();
351   if (UNLIKELY(CheckForPvallocOverflow(size, PageSize))) {
352     errno = errno_ENOMEM;
353     if (AllocatorMayReturnNull())
354       return nullptr;
355     ReportPvallocOverflow(size, stack);
356   }
357   // pvalloc(0) should allocate one page.
358   size = size ? RoundUpTo(size, PageSize) : PageSize;
359   return SetErrnoOnNull(HwasanAllocate(stack, size, PageSize, false));
360 }
361 
362 void *hwasan_aligned_alloc(uptr alignment, uptr size, StackTrace *stack) {
363   if (UNLIKELY(!CheckAlignedAllocAlignmentAndSize(alignment, size))) {
364     errno = errno_EINVAL;
365     if (AllocatorMayReturnNull())
366       return nullptr;
367     ReportInvalidAlignedAllocAlignment(size, alignment, stack);
368   }
369   return SetErrnoOnNull(HwasanAllocate(stack, size, alignment, false));
370 }
371 
372 void *hwasan_memalign(uptr alignment, uptr size, StackTrace *stack) {
373   if (UNLIKELY(!IsPowerOfTwo(alignment))) {
374     errno = errno_EINVAL;
375     if (AllocatorMayReturnNull())
376       return nullptr;
377     ReportInvalidAllocationAlignment(alignment, stack);
378   }
379   return SetErrnoOnNull(HwasanAllocate(stack, size, alignment, false));
380 }
381 
382 int hwasan_posix_memalign(void **memptr, uptr alignment, uptr size,
383                         StackTrace *stack) {
384   if (UNLIKELY(!CheckPosixMemalignAlignment(alignment))) {
385     if (AllocatorMayReturnNull())
386       return errno_EINVAL;
387     ReportInvalidPosixMemalignAlignment(alignment, stack);
388   }
389   void *ptr = HwasanAllocate(stack, size, alignment, false);
390   if (UNLIKELY(!ptr))
391     // OOM error is already taken care of by HwasanAllocate.
392     return errno_ENOMEM;
393   CHECK(IsAligned((uptr)ptr, alignment));
394   *memptr = ptr;
395   return 0;
396 }
397 
398 void hwasan_free(void *ptr, StackTrace *stack) {
399 #if HWASAN_WITH_INTERCEPTORS
400   // A tag of 0 means that this is a system allocator allocation, so we must use
401   // the system allocator to free it.
402   if (!flags()->disable_allocator_tagging && GetTagFromPointer((uptr)ptr) == 0)
403     return REAL(free)(ptr);
404 #endif
405 
406   return HwasanDeallocate(stack, ptr);
407 }
408 
409 }  // namespace __hwasan
410 
411 using namespace __hwasan;
412 
413 void __hwasan_enable_allocator_tagging() {
414   atomic_store_relaxed(&hwasan_allocator_tagging_enabled, 1);
415 }
416 
417 void __hwasan_disable_allocator_tagging() {
418 #if HWASAN_WITH_INTERCEPTORS
419   // Allocator tagging must be enabled for the system allocator fallback to work
420   // correctly. This means that we can't disable it at runtime if it was enabled
421   // at startup since that might result in our deallocations going to the system
422   // allocator. If tagging was disabled at startup we avoid this problem by
423   // disabling the fallback altogether.
424   CHECK(flags()->disable_allocator_tagging);
425 #endif
426 
427   atomic_store_relaxed(&hwasan_allocator_tagging_enabled, 0);
428 }
429 
430 uptr __sanitizer_get_current_allocated_bytes() {
431   uptr stats[AllocatorStatCount];
432   allocator.GetStats(stats);
433   return stats[AllocatorStatAllocated];
434 }
435 
436 uptr __sanitizer_get_heap_size() {
437   uptr stats[AllocatorStatCount];
438   allocator.GetStats(stats);
439   return stats[AllocatorStatMapped];
440 }
441 
442 uptr __sanitizer_get_free_bytes() { return 1; }
443 
444 uptr __sanitizer_get_unmapped_bytes() { return 1; }
445 
446 uptr __sanitizer_get_estimated_allocated_size(uptr size) { return size; }
447 
448 int __sanitizer_get_ownership(const void *p) { return AllocationSize(p) != 0; }
449 
450 uptr __sanitizer_get_allocated_size(const void *p) { return AllocationSize(p); }
451