/* 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 declarations of structures, routines, etc. that are commonly used
 * in memechecker framework.
 */

#ifndef QEMU_MEMCHECK_MEMCHECK_COMMON_H
#define QEMU_MEMCHECK_MEMCHECK_COMMON_H

#include "qemu-common.h"
#include "cpu.h"

#ifdef __cplusplus
extern "C" {
#endif

// =============================================================================
// Events generated by the guest system.
// =============================================================================

/* Notifies the emulator that libc has been initialized for a process.
 * Event's value parameter is PID for the process in context of which libc has
 * been initialized.
 */
#define TRACE_DEV_REG_LIBC_INIT             1536

/* Notifies the emulator about new memory block being allocated.
 * Event's value parameter points to MallocDesc instance in the guest's address
 * space that contains allocated block information. Note that 'libc_pid' field
 * of the descriptor is used by emulator to report failure in handling this
 * event. In case of failure emulator will zero that filed before completing
 * this event.
 */
#define TRACE_DEV_REG_MALLOC                1537

/* Notifies the emulator about memory block being freed.
 * Event's value parameter points to MallocFree descriptor instance in the
 * guest's address space that contains information about block that's being
 * freed. Note that 'libc_pid' field of the descriptor is used by emulator to
 * report failure in handling this event. In case of failure emulator will zero
 * that filed before completing this event.
 */
#define TRACE_DEV_REG_FREE_PTR              1538

/* Queries the emulator about memory block information.
 * Event's value parameter points to MallocDescQuery descriptor instance in the
 * guest's address space that contains query parameters. Note that 'libc_pid'
 * field of the descriptor is used by emulator to report failure in handling
 * this event. In case of failure emulator will zero that filed before
 * completing this event.
 */
#define TRACE_DEV_REG_QUERY_MALLOC          1539

/* Queries the emulator to print a string to its stdout.
 * Event's value parameter points to zero-terminated string to be printed. Note
 * that this string is located in the guest's address space.
 */
#define TRACE_DEV_REG_PRINT_USER_STR        1540

// =============================================================================
// Communication structures
// =============================================================================

/* Describes memory block allocated from the heap. This structure is passed
 * along with TRACE_DEV_REG_MALLOC event. This descriptor is used to inform
 * the emulator about new memory block being allocated from the heap. The entire
 * structure is initialized by the guest system before event is fired up. It is
 * important to remember that same structure (an exact copy) is also declared
 * in the libc's sources. So, every time a change is made to any of these
 * two declaration, another one must be also updated accordingly. */
typedef struct MallocDesc {
    /* Poniter to the memory block actually allocated from the heap. Note that
     * this is not the pointer that is returned to the malloc's caller. Pointer
     * returned to the caller is calculated by adding value stored in this field
     * to the value stored in prefix_size field of this structure.
     */
    target_ulong    ptr;

    /* Nuber of bytes requested by the malloc's caller. */
    uint32_t        requested_bytes;

    /* Byte size of the prefix data. Actual pointer returned to the malloc's
     * caller is calculated by adding value stored in this field to the value
     * stored in in the ptr field of this structure.
     */
    uint32_t        prefix_size;

    /* Byte size of the suffix data. */
    uint32_t        suffix_size;

    /* Id of the process that initialized libc instance, in which allocation
     * has occurred. This field is used by the emulator to report errors in
     * the course of TRACE_DEV_REG_MALLOC event handling. In case of an error,
     * emulator sets this field to zero (invalid value for a process ID).
     */
    uint32_t        libc_pid;

    /* Id of the process in context of which allocation has occurred.
     * Value in this field may differ from libc_pid value, if process that
     * is doing allocation has been forked from the process that initialized
     * libc instance.
     */
    uint32_t        allocator_pid;

    /* Number of access violations detected on this allocation. */
    uint32_t        av_count;
} MallocDesc;
/* Helpers for addressing field in MallocDesc structure, using which emulator
 * reports an error back to the guest.
 */
#define ALLOC_RES_OFFSET        ((uint32_t)(ptrdiff_t)&(((MallocDesc*)0)->libc_pid))
#define ALLOC_RES_ADDRESS(p)    (p + ALLOC_RES_OFFSET)

/* Describes memory block info queried from emulator. This structure is passed
 * along with TRACE_DEV_REG_QUERY_MALLOC event. When handling free and realloc
 * calls, it is required that we have information about memory blocks that were
 * actually allocated in previous calls to malloc, memalign, or realloc. Since
 * we don't keep this information directlry in the allocated block, but rather
 * we keep it in the emulator, we need to query emulator for that information
 * with TRACE_DEV_REG_QUERY_MALLOC query. The entire structure is initialized
 * by the guest system before event is fired up It is important to remember that
 * same structure (an exact copy) is also declared in the libc's sources. So,
 * every time a change is made to any of these two declaration, another one
 * must be also updated accordingly.
 */
typedef struct MallocDescQuery {
    /* Pointer for which information is queried. Note that this pointer doesn't
     * have to be exact pointer returned to malloc's caller, but can point
     * anywhere inside an allocated block, including guarding areas. Emulator
     * will respond with information about allocated block that contains this
     * pointer.
     */
    target_ulong    ptr;

    /* Id of the process that initialized libc instance, in which this query
     * is called. This field is used by the emulator to report errors in
     * the course of TRACE_DEV_REG_QUERY_MALLOC event handling. In case of an
     * error, emulator sets this field to zero (invalid value for a process ID).
     */
    uint32_t        libc_pid;

    /* Process ID in context of which query is made. */
    uint32_t        query_pid;

    /* Code of the allocation routine, in context of which query has been made:
     *  1 - free
     *  2 - realloc
     */
    uint32_t        routine;

    /* Address in guest's virtual space of memory allocation descriptor for the
     * queried pointer. Descriptor, addressed by this field is initialized by
     * the emulator in response to the query.
     */
    target_ulong    desc;
} MallocDescQuery;
/* Helpers for addressing field in MallocDescQuery structure using which
 * emulator reports an error back to the guest.
 */
#define QUERY_RES_OFFSET        ((uint32_t)(ptrdiff_t)&(((MallocDescQuery*)0)->libc_pid))
#define QUERY_RES_ADDRESS(p)    (p + QUERY_RES_OFFSET)

/* Describes memory block that is being freed back to the heap. This structure
 * is passed along with TRACE_DEV_REG_FREE_PTR event. The entire structure is
 * initialized by the guest system before event is fired up. It is important to
 * remember that same structure (an exact copy) is also declared in the libc's
 * sources. So, every time a change is made to any of these two declaration,
 * another one must be also updated accordingly.
 */
typedef struct MallocFree {
    /* Pointer to be freed. */
    uint32_t    ptr;

    /* Id of the process that initialized libc instance, in which this free
     * is called. This field is used by the emulator to report errors in
     * the course of TRACE_DEV_REG_FREE_PTR event handling. In case of an
     * error, emulator sets this field to zero (invalid value for a process ID).
     */
    uint32_t    libc_pid;

    /* Process ID in context of which memory is being freed. */
    uint32_t    free_pid;
} MallocFree;
/* Helpers for addressing field in MallocFree structure, using which emulator
 * reports an error back to the guest.
 */
#define FREE_RES_OFFSET         ((uint32_t)(ptrdiff_t)&(((MallocFree*)0)->libc_pid))
#define FREE_RES_ADDRESS(p)     (p + FREE_RES_OFFSET)

/* Extends MallocDesc structure with additional information, used by memchecker.
 */
typedef struct MallocDescEx {
    /* Allocation descriptor this structure extends. */
    MallocDesc      malloc_desc;

    /* Call stack that lead to memory allocation. The array is arranged in
     * accending order, where entry at index 0 corresponds to the routine
     * that allocated memory. */
    target_ulong*   call_stack;

    /* Number of entries in call_stack array. */
    uint32_t        call_stack_count;

    /* Set of misc. flags. See MDESC_FLAG_XXX bellow. */
    uint32_t        flags;
} MallocDescEx;

/* Indicates that memory has been allocated before process started execution.
 * After a process has been forked, but before it actually starts executing,
 * allocations can be made in context of that process PID. This flag marks such
 * allocations in the process' allocation descriptors map.
 */
#define MDESC_FLAG_TRANSITION_ENTRY         0x00000001

/* Indicates that memory block has been inherited from the parent process.
 * When a process is forked from its parent process, the forked process inherits
 * a copy of the parent process' heap. Thus, all allocations that were recorded
 * for the parent process must be also recorded for the forked process. This
 * flag marks entries in the forked process' allocation descriptors map that
 * were copied over from the parent process' allocation descriptors map.
 */
#define MDESC_FLAG_INHERITED_ON_FORK        0x00000002

/* Describes a memory mapping of an execution module in the guest system. */
typedef struct MMRangeDesc {
    /* Starting address of mmapping of a module in the guest's address space. */
    target_ulong            map_start;

    /* Ending address of mmapping of a module in the guest's address space. */
    target_ulong            map_end;

    /* Mmapping's execution offset. */
    target_ulong            exec_offset;

    /* Image path of the module that has been mapped with this mmapping. */
    char*                   path;
} MMRangeDesc;

/* Enumerates returned values for insert routines implemeted for red-black
 * tree maps.
 */
typedef enum {
    /* New entry has been inserted into the map. */
    RBT_MAP_RESULT_ENTRY_INSERTED = 0,

    /* An entry, matching the new one already exists in the map. */
    RBT_MAP_RESULT_ENTRY_ALREADY_EXISTS,

    /* An existing entry, matching the new one has been replaced
    * with the new entry.
    */
    RBT_MAP_RESULT_ENTRY_REPLACED,

    /* An error has occurred when inserting entry into the map. */
    RBT_MAP_RESULT_ERROR = -1,
} RBTMapResult;

/* Encapsulates an array of guest addresses, sorted in accending order. */
typedef struct AddrArray {
    /* Array of addresses. */
    target_ulong*   addr;

    /* Number of elements in the array. */
    int             num;
} AddrArray;

// =============================================================================
// Inlines
// =============================================================================

/* Gets pointer returned to malloc caller for the given allocation decriptor.
 * Param:
 *  desc - Allocation descriptor.
 * Return:
 *  Pointer to the allocated memory returned to the malloc caller.
 */
static inline target_ulong
mallocdesc_get_user_ptr(const MallocDesc* desc)
{
    return desc->ptr + desc->prefix_size;
}

/* Gets total size of the allocated block for the given descriptor.
 * Param:
 *  desc - Descriptor for the memory block, allocated in malloc handler.
 * Return:
 *  Total size of memory block allocated in malloc handler.
 */
static inline uint32_t
mallocdesc_get_alloc_size(const MallocDesc* desc)
{
    return desc->prefix_size + desc->requested_bytes + desc->suffix_size;
}

/* Gets the end of the allocated block for the given descriptor.
 * Param:
 *  desc - Descriptor for the memory block, allocated in malloc handler.
 * Return:
 *  Pointer to the end of the allocated block (next byte past the block).
 */
static inline target_ulong
mallocdesc_get_alloc_end(const MallocDesc* desc)
{
    return desc->ptr + mallocdesc_get_alloc_size(desc);
}

/* Gets the end of the allocated block available to the user for the given
 * descriptor.
 * Param:
 *  desc - Descriptor for the memory block, allocated in malloc handler.
 * Return:
 *  Pointer to the end of the allocated block available to the user (next byte
 *  past the block - suffix guarding area).
 */
static inline target_ulong
mallocdesc_get_user_alloc_end(const MallocDesc* desc)
{
    return mallocdesc_get_user_ptr(desc) + desc->requested_bytes;
}

/* Checks if allocation has been made before process started execution.
 * Param:
 *  desc - Allocation descriptor to check.
 * Return:
 *  boolean: 1 if allocation has been made before process started execution,
 *  or 0 if allocation has been made after process started execution.
 */
static inline int
mallocdescex_is_transition_entry(const MallocDescEx* desc)
{
    return (desc->flags & MDESC_FLAG_TRANSITION_ENTRY) != 0;
}

/* Checks if allocation block has been inherited on fork.
 * Param:
 *  desc - Allocation descriptor to check.
 * Return:
 *  boolean: 1 if allocation has been inherited on fork, or 0 if allocation
 *  has been made by this process..
 */
static inline int
mallocdescex_is_inherited_on_fork(const MallocDescEx* desc)
{
    return (desc->flags & MDESC_FLAG_INHERITED_ON_FORK) != 0;
}

/* Gets offset for the given address inside a mapped module.
 * Param:
 *  address - Address to get offset for.
 * Return:
 *  Offset of the given address inside a mapped module, represented with the
 *  given mmaping range descriptor.
 */
static inline target_ulong
mmrangedesc_get_module_offset(const MMRangeDesc* rdesc, target_ulong address)
{
    return address - rdesc->map_start + rdesc->exec_offset;
}

/* Checks if given address is contained in the given address array.
 * Return:
 *  boolean: 1 if address is contained in the array, or zero if it's not.
 */
static inline int
addrarray_check(const AddrArray* addr_array, target_ulong addr)
{
    if (addr_array->num != 0) {
        int m_min = 0;
        int m_max = addr_array->num - 1;

        /* May be odd for THUMB mode. */
        addr &= ~1;
        /* Since array is sorted we can do binary search here. */
        while (m_min <= m_max) {
            const int m = (m_min + m_max) >> 1;
            const target_ulong saved = addr_array->addr[m];
            if (addr == saved) {
                return 1;
            }
            if (addr < saved) {
                m_max = m - 1;
            } else {
                m_min = m + 1;
            }
        }
    }
    return 0;
}

/* Adds an address to the address array.
 * Return:
 *  1  - Address has been added to the array.
 *  -1 - Address already exists in the array.
 *  0  - Unable to expand the array.
 */
static inline int
addrarray_add(AddrArray* addr_array, target_ulong addr)
{
    target_ulong* new_arr;
    int m_min;
    int m_max;

    /* May be odd for THUMB mode. */
    addr &= ~1;
    if (addr_array->num == 0) {
        /* First element. */
        addr_array->addr = qemu_malloc(sizeof(target_ulong));
        assert(addr_array->addr != NULL);
        if (addr_array->addr == NULL) {
            return 0;
        }
        *addr_array->addr = addr;
        addr_array->num++;
        return 1;
    }

    /* Using binary search find the place where to insert new address. */
    m_min = 0;
    m_max = addr_array->num - 1;
    while (m_min <= m_max) {
        const int m = (m_min + m_max) >> 1;
        const target_ulong saved = addr_array->addr[m];
        if (addr == saved) {
            return -1;
        }
        if (addr < saved) {
            m_max = m - 1;
        } else {
            m_min = m + 1;
        }
    }
    if (m_max < 0) {
        m_max = 0;
    }
    /* Expand the array. */
    new_arr = qemu_malloc(sizeof(target_ulong) * (addr_array->num + 1));
    assert(new_arr != NULL);
    if (new_arr == NULL) {
        return 0;
    }
    /* Copy preceding elements to the new array. */
    if (m_max != 0) {
        memcpy(new_arr, addr_array->addr, m_max * sizeof(target_ulong));
    }
    if (addr > addr_array->addr[m_max]) {
        new_arr[m_max] = addr_array->addr[m_max];
        m_max++;
    }
    /* Insert new address. */
    new_arr[m_max] = addr;
    /* Copy remaining elements to the new array. */
    if (m_max < addr_array->num) {
        memcpy(new_arr + m_max + 1, addr_array->addr + m_max,
               (addr_array->num - m_max) * sizeof(target_ulong));
    }
    /* Swap arrays. */
    qemu_free(addr_array->addr);
    addr_array->addr = new_arr;
    addr_array->num++;
    return 1;
}

#ifdef __cplusplus
};  /* end of extern "C" */
#endif

#endif  // QEMU_MEMCHECK_MEMCHECK_COMMON_H