Merge memory checking from sandbox
Change-id: Ibce845d0
diff --git a/memcheck/memcheck_mmrange_map.c b/memcheck/memcheck_mmrange_map.c
new file mode 100644
index 0000000..f2609df
--- /dev/null
+++ b/memcheck/memcheck_mmrange_map.c
@@ -0,0 +1,236 @@
+/* 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.
+ */
+
+/* This file should compile iff qemu is built with memory checking
+ * configuration turned on. */
+#ifndef CONFIG_MEMCHECK
+#error CONFIG_MEMCHECK is not defined.
+#endif // CONFIG_MEMCHECK
+
+#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);
+ qemu_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 = qemu_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. */
+ qemu_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);
+ qemu_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);
+ qemu_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*)qemu_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 = qemu_malloc(strlen(entry->desc.path) + 1);
+ if (new_entry->desc.path == NULL) {
+ ME("memcheck: Unable to allocate new path for MMRangeMapEntry on copy.");
+ qemu_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);
+ qemu_free(new_entry->desc.path);
+ qemu_free(new_entry);
+ return -1;
+ }
+ }
+
+ return 0;
+}
+
+int
+mmrangemap_empty(MMRangeMap* map)
+{
+ MMRangeDesc pulled;
+ int removed = 0;
+
+ while (!mmrangemap_pull_first(map, &pulled)) {
+ qemu_free(pulled.path);
+ removed++;
+ }
+
+ return removed;
+}