/* 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 mappings in the guest system.
 */

#include "memcheck_mmrange_map.h"
#include "memcheck_logging.h"

/* Memory range descriptor stored in the map. */
typedef struct MMRangeMapEntry {
    /* R-B tree entry. */
    RB_ENTRY(MMRangeMapEntry)   rb_entry;

    /* Memory range descriptor for this entry. */
    MMRangeDesc                 desc;
} MMRangeMapEntry;

// =============================================================================
// R-B Tree implementation
// =============================================================================

/* Compare routine for the 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(MMRangeMapEntry* d1, MMRangeMapEntry* d2)
{
    const target_ulong start1 = d1->desc.map_start;
    const target_ulong start2 = d2->desc.map_start;

    if (start1 < start2) {
        return (d1->desc.map_end - 1) < start2 ? -1 : 0;
    }
    return (d2->desc.map_end - 1) < start1 ? 1 : 0;
}

/* Expands RB macros here. */
RB_GENERATE(MMRangeMap, MMRangeMapEntry, rb_entry, cmp_rb);

// =============================================================================
// Static routines
// =============================================================================

/* Inserts new (or replaces existing) entry into the map.
 * See comments on mmrangemap_insert routine in the header file for details
 * about this routine.
 */
static RBTMapResult
mmrangemap_insert_desc(MMRangeMap* map,
                       MMRangeMapEntry* rdesc,
                       MMRangeDesc* replaced)
{
    MMRangeMapEntry* existing = MMRangeMap_RB_INSERT(map, rdesc);
    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(MMRangeDesc));
    MMRangeMap_RB_REMOVE(map, existing);
    g_free(existing);
    MMRangeMap_RB_INSERT(map, rdesc);
    return RBT_MAP_RESULT_ENTRY_REPLACED;
}

/* Finds an entry in the map that matches the given address range.
 * Param:
 *  map - Map where to search for an entry.
 *  start - Starting address of a mapping range.
 *  end - Ending address of a mapping range.
 * Return:
 *  Address of a map entry that matches the given range, or NULL if no
 *  such entry has been found.
 */
static inline MMRangeMapEntry*
mmrangemap_find_entry(const MMRangeMap* map,
                      target_ulong start,
                      target_ulong end)
{
    MMRangeMapEntry rdesc;
    rdesc.desc.map_start = start;
    rdesc.desc.map_end = end;
    return MMRangeMap_RB_FIND((MMRangeMap*)map, &rdesc);
}

// =============================================================================
// Map API
// =============================================================================

void
mmrangemap_init(MMRangeMap* map)
{
    RB_INIT(map);
}

RBTMapResult
mmrangemap_insert(MMRangeMap* map,
                  const MMRangeDesc* desc,
                  MMRangeDesc* replaced)
{
    RBTMapResult ret;

    // Allocate and initialize new map entry.
    MMRangeMapEntry* rdesc = g_malloc(sizeof(MMRangeMapEntry));
    if (rdesc == NULL) {
        ME("memcheck: Unable to allocate new MMRangeMapEntry on insert.");
        return RBT_MAP_RESULT_ERROR;
    }
    memcpy(&rdesc->desc, desc, sizeof(MMRangeDesc));

    // Insert new entry into the map.
    ret = mmrangemap_insert_desc(map, rdesc, 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 free new descriptor, as it wasn't inserted. */
        g_free(rdesc);
    }
    return ret;
}

MMRangeDesc*
mmrangemap_find(const MMRangeMap* map, target_ulong start, target_ulong end)
{
    MMRangeMapEntry* rdesc = mmrangemap_find_entry(map, start, end);
    return rdesc != NULL ? &rdesc->desc : NULL;
}

int
mmrangemap_pull(MMRangeMap* map,
                target_ulong start,
                target_ulong end,
                MMRangeDesc* pulled)
{
    MMRangeMapEntry* rdesc = mmrangemap_find_entry(map, start, end);
    if (rdesc != NULL) {
        memcpy(pulled, &rdesc->desc, sizeof(MMRangeDesc));
        MMRangeMap_RB_REMOVE(map, rdesc);
        g_free(rdesc);
        return 0;
    } else {
        return -1;
    }
}

int
mmrangemap_pull_first(MMRangeMap* map, MMRangeDesc* pulled)
{
    MMRangeMapEntry* first = RB_MIN(MMRangeMap, map);
    if (first != NULL) {
        memcpy(pulled, &first->desc, sizeof(MMRangeDesc));
        MMRangeMap_RB_REMOVE(map, first);
        g_free(first);
        return 0;
    } else {
        return -1;
    }
}

int
mmrangemap_copy(MMRangeMap* to, const MMRangeMap* from)
{
    MMRangeMapEntry* entry;
    RB_FOREACH(entry, MMRangeMap, (MMRangeMap*)from) {
        RBTMapResult ins_res;
        MMRangeMapEntry* new_entry =
                (MMRangeMapEntry*)g_malloc(sizeof(MMRangeMapEntry));
        if (new_entry == NULL) {
            ME("memcheck: Unable to allocate new MMRangeMapEntry on copy.");
            return -1;
        }
        memcpy(new_entry, entry, sizeof(MMRangeMapEntry));
        new_entry->desc.path = g_malloc(strlen(entry->desc.path) + 1);
        if (new_entry->desc.path == NULL) {
            ME("memcheck: Unable to allocate new path for MMRangeMapEntry on copy.");
            g_free(new_entry);
            return -1;
        }
        strcpy(new_entry->desc.path, entry->desc.path);
        ins_res = mmrangemap_insert_desc(to, new_entry, NULL);
        if (ins_res != RBT_MAP_RESULT_ENTRY_INSERTED) {
            ME("memcheck: Unable to insert new range map entry on copy. Insert returned %u",
               ins_res);
            g_free(new_entry->desc.path);
            g_free(new_entry);
            return -1;
        }
    }

    return 0;
}

int
mmrangemap_empty(MMRangeMap* map)
{
    MMRangeDesc pulled;
    int removed = 0;

    while (!mmrangemap_pull_first(map, &pulled)) {
        g_free(pulled.path);
        removed++;
    }

    return removed;
}