/* Copyright (C) 2007-2010 The Android Open Source Project
**
** This software is licensed under the terms of the GNU General Public
** License version 2, as published by the Free Software Foundation, and
** may be copied, distributed, and modified under those terms.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU General Public License for more details.
*/
/*
* Contains implementation of routines that implement a red-black tree of
* memory blocks allocated by the guest system.
*/
#include "memcheck_malloc_map.h"
#include "memcheck_util.h"
#include "memcheck_logging.h"
/* Global flag, indicating whether or not __ld/__stx_mmu should be instrumented
* for checking for access violations. If read / write access violation check.
* Defined in memcheck.c
*/
extern int memcheck_instrument_mmu;
/* Allocation descriptor stored in the map. */
typedef struct AllocMapEntry {
/* R-B tree entry. */
RB_ENTRY(AllocMapEntry) rb_entry;
/* Allocation descriptor for this entry. */
MallocDescEx desc;
} AllocMapEntry;
// =============================================================================
// Inlines
// =============================================================================
/* Gets address of the beginning of an allocation block for the given entry in
* the map.
* Param:
* adesc - Entry in the allocation descriptors map.
* Return:
* Address of the beginning of an allocation block for the given entry in the
* map.
*/
static inline target_ulong
allocmapentry_alloc_begins(const AllocMapEntry* adesc)
{
return adesc->desc.malloc_desc.ptr;
}
/* Gets address of the end of an allocation block for the given entry in
* the map.
* Param:
* adesc - Entry in the allocation descriptors map.
* Return:
* Address of the end of an allocation block for the given entry in the map.
*/
static inline target_ulong
allocmapentry_alloc_ends(const AllocMapEntry* adesc)
{
return mallocdesc_get_alloc_end(&adesc->desc.malloc_desc);
}
// =============================================================================
// R-B Tree implementation
// =============================================================================
/* Compare routine for the allocation descriptors map.
* Param:
* d1 - First map entry to compare.
* d2 - Second map entry to compare.
* Return:
* 0 - Descriptors are equal. Note that descriptors are considered to be
* equal iff memory blocks they describe intersect in any part.
* 1 - d1 is greater than d2
* -1 - d1 is less than d2.
*/
static inline int
cmp_rb(AllocMapEntry* d1, AllocMapEntry* d2)
{
const target_ulong start1 = allocmapentry_alloc_begins(d1);
const target_ulong start2 = allocmapentry_alloc_begins(d2);
if (start1 < start2) {
return (allocmapentry_alloc_ends(d1) - 1) < start2 ? -1 : 0;
}
return (allocmapentry_alloc_ends(d2) - 1) < start1 ? 1 : 0;
}
/* Expands RB macros here. */
RB_GENERATE(AllocMap, AllocMapEntry, rb_entry, cmp_rb);
// =============================================================================
// Static routines
// =============================================================================
/* Inserts new (or replaces existing) entry into allocation descriptors map.
* See comments on allocmap_insert routine in the header file for details
* about this routine.
*/
static RBTMapResult
allocmap_insert_desc(AllocMap* map,
AllocMapEntry* adesc,
MallocDescEx* replaced)
{
AllocMapEntry* existing = AllocMap_RB_INSERT(map, adesc);
if (existing == NULL) {
return RBT_MAP_RESULT_ENTRY_INSERTED;
}
// Matching entry exists. Lets see if we need to replace it.
if (replaced == NULL) {
return RBT_MAP_RESULT_ENTRY_ALREADY_EXISTS;
}
/* Copy existing entry to the provided buffer and replace it
* with the new one. */
memcpy(replaced, &existing->desc, sizeof(MallocDescEx));
AllocMap_RB_REMOVE(map, existing);
g_free(existing);
AllocMap_RB_INSERT(map, adesc);
return RBT_MAP_RESULT_ENTRY_REPLACED;
}
/* Finds an entry in the allocation descriptors map that matches the given
* address range.
* Param:
* map - Allocation descriptors map where to search for an entry.
* address - Virtual address in the guest's user space to find matching
* entry for.
* Return:
* Address of an allocation descriptors map entry that matches the given
* address, or NULL if no such entry has been found.
*/
static inline AllocMapEntry*
allocmap_find_entry(const AllocMap* map,
target_ulong address,
uint32_t block_size)
{
AllocMapEntry adesc;
adesc.desc.malloc_desc.ptr = address;
adesc.desc.malloc_desc.requested_bytes = block_size;
adesc.desc.malloc_desc.prefix_size = 0;
adesc.desc.malloc_desc.suffix_size = 0;
return AllocMap_RB_FIND((AllocMap*)map, &adesc);
}
// =============================================================================
// Map API
// =============================================================================
void
allocmap_init(AllocMap* map)
{
RB_INIT(map);
}
RBTMapResult
allocmap_insert(AllocMap* map, const MallocDescEx* desc, MallocDescEx* replaced)
{
RBTMapResult ret;
// Allocate and initialize new map entry.
AllocMapEntry* adesc = g_malloc(sizeof(AllocMapEntry));
if (adesc == NULL) {
ME("memcheck: Unable to allocate new AllocMapEntry on insert.");
return RBT_MAP_RESULT_ERROR;
}
memcpy(&adesc->desc, desc, sizeof(MallocDescEx));
// Insert new entry into the map.
ret = allocmap_insert_desc(map, adesc, replaced);
if (ret == RBT_MAP_RESULT_ENTRY_ALREADY_EXISTS ||
ret == RBT_MAP_RESULT_ERROR) {
/* Another descriptor already exists for this block, or an error
* occurred. We have to tree new descriptor, as it wasn't inserted. */
g_free(adesc);
}
return ret;
}
MallocDescEx*
allocmap_find(const AllocMap* map, target_ulong address, uint32_t block_size)
{
AllocMapEntry* adesc = allocmap_find_entry(map, address, block_size);
return adesc != NULL ? &adesc->desc : NULL;
}
int
allocmap_pull(AllocMap* map, target_ulong address, MallocDescEx* pulled)
{
AllocMapEntry* adesc = allocmap_find_entry(map, address, 1);
if (adesc != NULL) {
memcpy(pulled, &adesc->desc, sizeof(MallocDescEx));
AllocMap_RB_REMOVE(map, adesc);
g_free(adesc);
return 0;
} else {
return -1;
}
}
int
allocmap_pull_first(AllocMap* map, MallocDescEx* pulled)
{
AllocMapEntry* first = RB_MIN(AllocMap, map);
if (first != NULL) {
memcpy(pulled, &first->desc, sizeof(MallocDescEx));
AllocMap_RB_REMOVE(map, first);
g_free(first);
return 0;
} else {
return -1;
}
}
int
allocmap_copy(AllocMap* to,
const AllocMap* from,
uint32_t set_flags,
uint32_t clear_flags)
{
AllocMapEntry* entry;
RB_FOREACH(entry, AllocMap, (AllocMap*)from) {
RBTMapResult ins_res;
AllocMapEntry* new_entry =
(AllocMapEntry*)g_malloc(sizeof(AllocMapEntry));
if (new_entry == NULL) {
ME("memcheck: Unable to allocate new AllocMapEntry on copy.");
return -1;
}
memcpy(new_entry, entry, sizeof(AllocMapEntry));
new_entry->desc.flags &= ~clear_flags;
new_entry->desc.flags |= set_flags;
if (entry->desc.call_stack_count) {
new_entry->desc.call_stack =
g_malloc(entry->desc.call_stack_count * sizeof(target_ulong));
memcpy(new_entry->desc.call_stack, entry->desc.call_stack,
entry->desc.call_stack_count * sizeof(target_ulong));
} else {
new_entry->desc.call_stack = NULL;
}
new_entry->desc.call_stack_count = entry->desc.call_stack_count;
ins_res = allocmap_insert_desc(to, new_entry, NULL);
if (ins_res == RBT_MAP_RESULT_ENTRY_INSERTED) {
if (memcheck_instrument_mmu) {
// Invalidate TLB cache for inserted entry.
invalidate_tlb_cache(new_entry->desc.malloc_desc.ptr,
mallocdesc_get_alloc_end(&new_entry->desc.malloc_desc));
}
} else {
ME("memcheck: Unable to insert new map entry on copy. Insert returned %u",
ins_res);
if (new_entry->desc.call_stack != NULL) {
g_free(new_entry->desc.call_stack);
}
g_free(new_entry);
return -1;
}
}
return 0;
}
int
allocmap_empty(AllocMap* map)
{
MallocDescEx pulled;
int removed = 0;
while (!allocmap_pull_first(map, &pulled)) {
removed++;
if (pulled.call_stack != NULL) {
g_free(pulled.call_stack);
}
}
return removed;
}