blob: 93d1832c0f683a6fe04faf7e9ba740d29e24dc28 [file] [log] [blame]
/*
* Copyright 2017, Data61, CSIRO (ABN 41 687 119 230)
*
* SPDX-License-Identifier: BSD-2-Clause
*/
/* This file contains functionality for debugging heap corruption issues. It is
* styled after Electric Fence [0], but we can't check as thoroughly as eFence
* can because we don't have support for mapping/unmapping/mprotecting regions.
* The basic concept is that we stick a 'canary' value before and after
* allocated memory. During free, we check that these canaries haven't been
* overwritten, which would imply buffer underflow or overflow. This checking
* is limited in that we don't catch heap corruption until memory is actually
* freed.
*
* Essentially any allocated region actually looks like this:
* p q r
* ↓ ↓ ↓
* |canary|size|memory...|canary|
*
* Internally we deal in 'unboxed' pointers, like p. Externally the caller is
* given 'boxed' pointers, like q. We effectively play the same tricks malloc
* does to store some book keeping information surrounding the malloced memory.
* The 'size' stored is the size the user requested, not the size including
* the canaries etc. We need to track this in order to calculate the pointer r
* on free.
*
* In addition to checking for corruption within the heap, this functionality
* also tracks pointers that have been allocated. If you try and free (or
* realloc) a pointer that was never allocated, it will be detected.
*
* To use this, you will need to instruct the linker to wrap your calls to
* allocation functions. You will need to append something like the following
* to your LD_FALGS:
* -Wl,--wrap=malloc -Wl,--wrap=free -Wl,--wrap=realloc -Wl,--wrap=calloc
*
* Ensure you do not call any functions that malloc or free memory within this
* file or you will infinitely recurse.
*/
#include <assert.h>
#include <autoconf.h>
#include <sel4debug/gen_config.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h> /* for size_t */
#include <string.h>
/* Maximum alignment of a data type. The malloc spec requires that returned
* pointers are aligned to this.
*/
#define MAX_ALIGNMENT (sizeof(void*) * 2) /* bytes */
/* Random bits to OR into the pre- and post-canary values so we're not storing
* an exact pointer value. Note that these should be less than MAX_ALIGNMENT so
* that we're ORing into known 0 bits. Preserving the pointer is not actually
* necessary so nothing will break if you change these values to any random
* word-sized value.
*/
#define PRE_EXTRA_BITS 0x7
#define POST_EXTRA_BITS 0x3
/* Algorithms for calculating a canary value to use before and after the
* allocated region. The actual algorithm used here is more or less irrelevant
* as long as it is deterministic.
*/
static uintptr_t pre_canary(void *ptr)
{
return ((uintptr_t)ptr) | PRE_EXTRA_BITS;
}
static uintptr_t post_canary(void *ptr)
{
return ((uintptr_t)ptr) | POST_EXTRA_BITS;
}
typedef struct {
uintptr_t canary;
size_t size;
} __attribute__((aligned(MAX_ALIGNMENT))) metadata_t;
/* A `uintptr_t` that is not naturally aligned. It is necessary to explicitly
* tag unaligned pointers because, e.g., on ARM the compiler is free to
* transform `memcpy` calls into a variant that assumes its inputs are aligned
* and performs word-sized accesses. See the following for more information:
* http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.faqs/4972.html
*/
typedef uintptr_t unaligned_uintptr_t __attribute__((aligned(1)));
/* Whether we've already encountered heap corruption. See uses of this below,
* where we abandon all instrumentation if we've hit an error. The reasoning
* behind this is that error reporting functions may call malloc.
*/
static int err = 0;
/* Adjust a size that is about to be passed to the real allocation functions in
* order to account for our instrumentation.
*/
static size_t adjust_size(size_t size)
{
return size + sizeof(metadata_t) + sizeof(uintptr_t);
}
/* Wrap a (just-allocated) region with canary values. */
static void *box(void *ptr, size_t size)
{
if (ptr == NULL) {
return ptr;
}
metadata_t *pre = (metadata_t *)ptr;
ptr += sizeof(*pre);
unaligned_uintptr_t *post = ptr + size;
/* Write the leading canary. */
pre->canary = pre_canary(ptr);
pre->size = size;
/* Use memcpy for the trailing canary so we don't need to care about
* alignment.
*/
uintptr_t canary = post_canary(ptr);
memcpy(post, &canary, sizeof(canary));
return ptr;
}
/* Throw an error resulting from a bad user invocation. */
#define error(args...) do { \
assert(!err); /* We should not already be handling an error. */ \
err = 1; \
fprintf(stderr, args); \
abort(); \
} while (0)
/* Unwrap a canary-endowed region into the original allocated pointer. */
static void *unbox(void *ptr, void *ret_addr)
{
if (ptr == NULL) {
return ptr;
}
metadata_t *pre = (metadata_t *)(ptr - sizeof(*pre));
unaligned_uintptr_t *post = ptr + pre->size;
/* Check the leading canary (underflow). */
if (pre->canary != pre_canary(ptr)) {
error("Leading corruption in heap memory pointed to by %p (called "
"prior to %p)\n", ptr, ret_addr);
}
/* Check the trailing canary with memcmp so we don't need to care about
* alignment. If the memcmp VM faults here, it's likely that you underran
* your buffer and overwrote the 'size' metadata, causing this function to
* derive an incorrect 'post' pointer.
*/
uintptr_t canary = post_canary(ptr);
if (memcmp(post, &canary, sizeof(canary)) != 0) {
error("Buffer overflow in heap memory pointed to by %p (called prior "
"to %p)\n", ptr, ret_addr);
}
return (void *)pre;
}
/* Buffer for tracking currently live heap pointers. This is used to detect
* when the user attempts to free an invalid pointer. Note that we always track
* *boxed* pointers as these are the ones seen by the user.
*/
#ifndef CONFIG_LIBSEL4DEBUG_ALLOC_BUFFER_ENTRIES
#define CONFIG_LIBSEL4DEBUG_ALLOC_BUFFER_ENTRIES 128
#endif
static uintptr_t alloced[CONFIG_LIBSEL4DEBUG_ALLOC_BUFFER_ENTRIES];
/* Track the given heap pointer as currently live. */
static void track(void *ptr)
{
if (sizeof(alloced) == 0 || ptr == NULL) {
/* Disable tracking if we have no buffer and never track NULL. */
return;
}
for (unsigned int i = 0; i < sizeof(alloced) / sizeof(uintptr_t); i++) {
if (alloced[i] == 0) {
/* Found a free slot. */
alloced[i] = (uintptr_t)ptr;
return;
}
}
/* Failed to find a free slot. */
error("Exhausted pointer tracking buffer; try increasing "
"CONFIG_LIBSEL4DEBUG_ALLOC_BUFFER_ENTRIES value\n");
}
/* Stop tracking the given pointer (mark it as dead). */
static void untrack(void *ptr, void *ret_addr)
{
if (sizeof(alloced) == 0 || ptr == NULL) {
/* Ignore tracking if we have no buffer or are freeing NULL. */
return;
}
for (unsigned int i = 0; i < sizeof(alloced) / sizeof(uintptr_t); i++) {
if (alloced[i] == (uintptr_t)ptr) {
/* Found it. */
alloced[i] = 0;
return;
}
}
/* Failed to find it. */
error("Attempt to free pointer %p that was never malloced (called prior "
"to %p)\n", ptr, ret_addr);
}
/* Wrapped functions that will be exported to us from libmuslc. */
void *__real_malloc(size_t size);
void __real_free(void *ptr);
void *__real_calloc(size_t num, size_t size);
void *__real_realloc(void *ptr, size_t size);
/* Actual allocation wrappers follow. */
void *__wrap_malloc(size_t size)
{
if (err) {
return __real_malloc(size);
}
size_t new_size = adjust_size(size);
void *ptr = __real_malloc(new_size);
ptr = box(ptr, size);
track(ptr);
return ptr;
}
void __wrap_free(void *ptr)
{
if (err) {
__real_free(ptr);
return;
}
void *ret = __builtin_extract_return_addr(__builtin_return_address(0));
untrack(ptr, ret);
/* Write garbage all over the region we were handed back to try to expose
* use-after-free bugs. If we fault while doing this, it probably means the
* user underran their buffer and overwrote the 'size' metadata.
*/
metadata_t *pre = (metadata_t *)(ptr - sizeof(*pre));
for (unsigned int i = 0; i < pre->size; i++) {
((char *)ptr)[i] ^= (char)~i;
}
ptr = unbox(ptr, ret);
__real_free(ptr);
}
void *__wrap_calloc(size_t num, size_t size)
{
if (err) {
return __real_calloc(num, size);
}
size_t sz = adjust_size(num * size);
size_t new_num = sz / size;
if (sz % size != 0) {
new_num++;
}
void *ptr = __real_calloc(new_num, size);
ptr = box(ptr, num * size);
track(ptr);
return ptr;
}
void *__wrap_realloc(void *ptr, size_t size)
{
if (err) {
return __real_realloc(ptr, size);
}
void *ret = __builtin_extract_return_addr(__builtin_return_address(0));
untrack(ptr, ret);
ptr = unbox(ptr, ret);
size_t new_size = adjust_size(size);
ptr = __real_realloc(ptr, new_size);
ptr = box(ptr, size);
track(ptr);
return ptr;
}