From ea0c6724dc992a5358d6da3d50d9f60472d66d64 Mon Sep 17 00:00:00 2001 From: Martin Nowack Date: Tue, 22 Mar 2016 17:16:38 +0100 Subject: Handle aligned varargs allignment correctly For vararg handling, arguments of size bigger than 64 bit need to be handled 128bit aligned according to AMD calling conventions AMD64-ABI 3.5.7p5. To handle that case correctly, we do: 1) make sure that every argument is aligned correctly in an allocation for function arguments 2) the allocation itself is aligned correctly --- lib/Core/MemoryManager.cpp | 22 +++++++++++++++++----- 1 file changed, 17 insertions(+), 5 deletions(-) (limited to 'lib/Core/MemoryManager.cpp') diff --git a/lib/Core/MemoryManager.cpp b/lib/Core/MemoryManager.cpp index 7c76d480..02bbe678 100644 --- a/lib/Core/MemoryManager.cpp +++ b/lib/Core/MemoryManager.cpp @@ -32,13 +32,25 @@ MemoryManager::~MemoryManager() { } } -MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, +MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, bool isGlobal, - const llvm::Value *allocSite) { + const llvm::Value *allocSite, + size_t alignment) { if (size>10*1024*1024) - klee_warning_once(0, "Large alloc: %u bytes. KLEE may run out of memory.", (unsigned) size); - - uint64_t address = (uint64_t) (unsigned long) malloc((unsigned) size); + klee_warning_once(0, "Large alloc: %lu bytes. KLEE may run out of memory.", + size); + + uint64_t address = 0; + // Use malloc for the standard case + if (alignment <= 8) + address = (uint64_t)malloc(size); + else { + int res = posix_memalign((void **)&address, alignment, size); + if (res < 0) { + klee_warning("Allocating aligned memory failed."); + address = 0; + } + } if (!address) return 0; -- cgit v1.2.3 From d06a14dc2ff22da34dbf566a2ad4626c88b0be17 Mon Sep 17 00:00:00 2001 From: Martin Nowack Date: Tue, 22 Mar 2016 17:50:28 +0100 Subject: Add deterministic allocation of memory Deterministic allocation provides an internal allocator which mmaps memory to a fixed static address. This way, same allocation is assured across different KLEE runs for the same application assuming a deterministic searcher. In addition, this patch provides following options: -allocate-determ: switch on/off deterministic allocation -allocate-determ-size: adjust preallocated memory -null-on-zero-malloc: returns null pointer in case a malloc of size 0 was requested. According to standard, also a non-null pointer can be returned (which happens with the default glibc malloc implementation) -allocation-space: space between allocations can be adjusted. KLEE is not able to detect out-of-bound accesses which are inside another but wrong object. Due the implementation of typical allocators adjacent mallocs have space in between for management purposes. This spaces helped KLEE to detect off-by-1/2 accesses. For higher numbers, the allocation space has to be increased. -allocate-determ-start-address: adjust deterministic start address. The addres has to be page aligned. KLEE fails if it cannot acquire this address --- lib/Core/MemoryManager.cpp | 100 +++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 96 insertions(+), 4 deletions(-) (limited to 'lib/Core/MemoryManager.cpp') diff --git a/lib/Core/MemoryManager.cpp b/lib/Core/MemoryManager.cpp index 02bbe678..560bb6f6 100644 --- a/lib/Core/MemoryManager.cpp +++ b/lib/Core/MemoryManager.cpp @@ -11,25 +11,84 @@ #include "Memory.h" #include "MemoryManager.h" -#include "klee/ExecutionState.h" #include "klee/Expr.h" -#include "klee/Solver.h" #include "klee/Internal/Support/ErrorHandling.h" #include "llvm/Support/CommandLine.h" +#include "llvm/Support/MathExtras.h" +#include using namespace klee; +namespace { +llvm::cl::opt DeterministicAllocation( + "allocate-determ", + llvm::cl::desc("Allocate memory deterministically(default=off)"), + llvm::cl::init(false)); + +llvm::cl::opt DeterministicAllocationSize( + "allocate-determ-size", + llvm::cl::desc( + "Preallocated memory for deterministic allocation in MB (default=100)"), + llvm::cl::init(100)); + +llvm::cl::opt + NullOnZeroMalloc("return-null-on-zero-malloc", + llvm::cl::desc("Returns NULL in case malloc(size) was " + "called with size 0 (default=off)."), + llvm::cl::init(false)); + +llvm::cl::opt RedZoneSpace( + "red-zone-space", + llvm::cl::desc("Set the amount of free space between allocations. This is " + "important to detect out-of-bound accesses (default=10)."), + llvm::cl::init(10)); + +llvm::cl::opt DeterministicStartAddress( + "allocate-determ-start-address", + llvm::cl::desc("Start address for deterministic allocation. Has to be page " + "aligned (default=0x7ff30000000)."), + llvm::cl::init(0x7ff30000000)); +} + /***/ +MemoryManager::MemoryManager(ArrayCache *_arrayCache) + : arrayCache(_arrayCache), deterministicSpace(0), + nextFreeSlot(0), + spaceSize(DeterministicAllocationSize.getValue() * 1024 * 1024) { + if (DeterministicAllocation) { + // Page boundary + void *expectedAddress = (void *)DeterministicStartAddress.getValue(); + + char *newSpace = + (char *)mmap(expectedAddress, spaceSize, PROT_READ | PROT_WRITE, + MAP_ANONYMOUS | MAP_PRIVATE, -1, 0); + + if (newSpace == MAP_FAILED) { + klee_error("Couldn't mmap() memory for deterministic allocations"); + } + if (expectedAddress != newSpace) { + klee_error("Could not allocate memory deterministically"); + } + + klee_message("Deterministic memory allocation starting from %p", + expectedAddress); + deterministicSpace = newSpace; + nextFreeSlot = newSpace; + } +} MemoryManager::~MemoryManager() { while (!objects.empty()) { MemoryObject *mo = *objects.begin(); - if (!mo->isFixed) + if (!mo->isFixed && !DeterministicAllocation) free((void *)mo->address); objects.erase(mo); delete mo; } + + if (DeterministicAllocation) + munmap(deterministicSpace, spaceSize); } MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, @@ -40,7 +99,34 @@ MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, klee_warning_once(0, "Large alloc: %lu bytes. KLEE may run out of memory.", size); + // Return NULL if size is zero, this is equal to error during allocation + if (NullOnZeroMalloc && size == 0) + return 0; + + if (!llvm::isPowerOf2_64(alignment)) { + klee_warning("Only alignment of power of two is supported"); + return 0; + } + uint64_t address = 0; + if (DeterministicAllocation) { + + address = llvm::RoundUpToAlignment((uint64_t)nextFreeSlot + alignment - 1, + alignment); + + // Handle the case of 0-sized allocations as 1-byte allocations. + // This way, we make sure we have this allocation between its own red zones + size_t alloc_size = std::max(size, (uint64_t)1); + if ((char *)address + alloc_size < deterministicSpace + spaceSize) { + nextFreeSlot = (char *)address + alloc_size + RedZoneSpace; + } else { + klee_warning_once( + 0, + "Couldn't allocate %lu bytes. Not enough deterministic space left.", + size); + address = 0; + } + } else { // Use malloc for the standard case if (alignment <= 8) address = (uint64_t)malloc(size); @@ -51,6 +137,8 @@ MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, address = 0; } } + } + if (!address) return 0; @@ -86,8 +174,12 @@ void MemoryManager::deallocate(const MemoryObject *mo) { void MemoryManager::markFreed(MemoryObject *mo) { if (objects.find(mo) != objects.end()) { - if (!mo->isFixed) + if (!mo->isFixed && !DeterministicAllocation) free((void *)mo->address); objects.erase(mo); } } + +size_t MemoryManager::getUsedDeterministicSize() { + return nextFreeSlot - deterministicSpace; +} -- cgit v1.2.3 From 05a0962a50fede85aae254667d5dac1586744eb3 Mon Sep 17 00:00:00 2001 From: Martin Nowack Date: Tue, 24 May 2016 15:13:31 +0200 Subject: Clang-formated MemoryManager --- lib/Core/MemoryManager.cpp | 26 +++++++++++--------------- 1 file changed, 11 insertions(+), 15 deletions(-) (limited to 'lib/Core/MemoryManager.cpp') diff --git a/lib/Core/MemoryManager.cpp b/lib/Core/MemoryManager.cpp index 560bb6f6..004ce090 100644 --- a/lib/Core/MemoryManager.cpp +++ b/lib/Core/MemoryManager.cpp @@ -53,8 +53,7 @@ llvm::cl::opt DeterministicStartAddress( /***/ MemoryManager::MemoryManager(ArrayCache *_arrayCache) - : arrayCache(_arrayCache), deterministicSpace(0), - nextFreeSlot(0), + : arrayCache(_arrayCache), deterministicSpace(0), nextFreeSlot(0), spaceSize(DeterministicAllocationSize.getValue() * 1024 * 1024) { if (DeterministicAllocation) { // Page boundary @@ -78,7 +77,7 @@ MemoryManager::MemoryManager(ArrayCache *_arrayCache) } } -MemoryManager::~MemoryManager() { +MemoryManager::~MemoryManager() { while (!objects.empty()) { MemoryObject *mo = *objects.begin(); if (!mo->isFixed && !DeterministicAllocation) @@ -95,7 +94,7 @@ MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, bool isGlobal, const llvm::Value *allocSite, size_t alignment) { - if (size>10*1024*1024) + if (size > 10 * 1024 * 1024) klee_warning_once(0, "Large alloc: %lu bytes. KLEE may run out of memory.", size); @@ -141,7 +140,7 @@ MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, if (!address) return 0; - + ++stats::allocations; MemoryObject *res = new MemoryObject(address, size, isLocal, isGlobal, false, allocSite, this); @@ -152,28 +151,25 @@ MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, MemoryObject *MemoryManager::allocateFixed(uint64_t address, uint64_t size, const llvm::Value *allocSite) { #ifndef NDEBUG - for (objects_ty::iterator it = objects.begin(), ie = objects.end(); - it != ie; ++it) { + for (objects_ty::iterator it = objects.begin(), ie = objects.end(); it != ie; + ++it) { MemoryObject *mo = *it; - if (address+size > mo->address && address < mo->address+mo->size) + if (address + size > mo->address && address < mo->address + mo->size) klee_error("Trying to allocate an overlapping object"); } #endif ++stats::allocations; - MemoryObject *res = new MemoryObject(address, size, false, true, true, - allocSite, this); + MemoryObject *res = + new MemoryObject(address, size, false, true, true, allocSite, this); objects.insert(res); return res; } -void MemoryManager::deallocate(const MemoryObject *mo) { - assert(0); -} +void MemoryManager::deallocate(const MemoryObject *mo) { assert(0); } void MemoryManager::markFreed(MemoryObject *mo) { - if (objects.find(mo) != objects.end()) - { + if (objects.find(mo) != objects.end()) { if (!mo->isFixed && !DeterministicAllocation) free((void *)mo->address); objects.erase(mo); -- cgit v1.2.3