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