We will want to be able to search the set of mappings.
For this patch, the two users iterate the tree in order.
Signed-off-by: Richard Henderson <richard.hender...@linaro.org>
---
include/qemu/selfmap.h | 22 ++++----
linux-user/elfload.c | 14 +++--
linux-user/syscall.c | 15 +++---
util/selfmap.c | 114 +++++++++++++++++++++++++----------------
4 files changed, 97 insertions(+), 68 deletions(-)
diff --git a/include/qemu/selfmap.h b/include/qemu/selfmap.h
index 3479a2a618..7d938945cb 100644
--- a/include/qemu/selfmap.h
+++ b/include/qemu/selfmap.h
@@ -9,9 +9,10 @@
#ifndef SELFMAP_H
#define SELFMAP_H
+#include "qemu/interval-tree.h"
+
typedef struct {
- unsigned long start;
- unsigned long end;
+ IntervalTreeNode itree;
/* flags */
bool is_read;
@@ -19,26 +20,25 @@ typedef struct {
bool is_exec;
bool is_priv;
- unsigned long offset;
- gchar *dev;
+ uint64_t offset;
uint64_t inode;
- gchar *path;
+ const char *path;
+ char dev[];
} MapInfo;
-
/**
* read_self_maps:
*
- * Read /proc/self/maps and return a list of MapInfo structures.
+ * Read /proc/self/maps and return a tree of MapInfo structures.
*/
-GSList *read_self_maps(void);
+IntervalTreeRoot *read_self_maps(void);
/**
* free_self_maps:
- * @info: a GSlist
+ * @info: an interval tree
*
- * Free a list of MapInfo structures.
+ * Free a tree of MapInfo structures.
*/
-void free_self_maps(GSList *info);
+void free_self_maps(IntervalTreeRoot *root);
#endif /* SELFMAP_H */
diff --git a/linux-user/elfload.c b/linux-user/elfload.c
index e72497c4b4..fb137345f6 100644
--- a/linux-user/elfload.c
+++ b/linux-user/elfload.c
@@ -2620,7 +2620,8 @@ static uintptr_t pgd_find_hole_fallback(uintptr_t
guest_size, uintptr_t brk,
static uintptr_t pgb_find_hole(uintptr_t guest_loaddr, uintptr_t guest_size,
long align, uintptr_t offset)
{
- GSList *maps, *iter;
+ IntervalTreeRoot *maps;
+ IntervalTreeNode *iter;
uintptr_t this_start, this_end, next_start, brk;
intptr_t ret = -1;
@@ -2638,12 +2639,15 @@ static uintptr_t pgb_find_hole(uintptr_t guest_loaddr,
uintptr_t guest_size,
/* The first hole is before the first map entry. */
this_start = mmap_min_addr;
- for (iter = maps; iter;
- this_start = next_start, iter = g_slist_next(iter)) {
+ for (iter = interval_tree_iter_first(maps, 0, -1);
+ iter;
+ this_start = next_start,
+ iter = interval_tree_iter_next(iter, 0, -1)) {
+ MapInfo *info = container_of(iter, MapInfo, itree);
uintptr_t align_start, hole_size;
- this_end = ((MapInfo *)iter->data)->start;
- next_start = ((MapInfo *)iter->data)->end;
+ this_end = info->itree.start;
+ next_start = info->itree.last + 1;
align_start = ROUND_UP(this_start + offset, align);
/* Skip holes that are too small. */
diff --git a/linux-user/syscall.c b/linux-user/syscall.c
index 7c2c2f6e2f..a15bce2be2 100644
--- a/linux-user/syscall.c
+++ b/linux-user/syscall.c
@@ -8070,16 +8070,17 @@ static int open_self_maps_1(CPUArchState *cpu_env, int
fd, bool smaps)
{
CPUState *cpu = env_cpu(cpu_env);
TaskState *ts = cpu->opaque;
- GSList *map_info = read_self_maps();
- GSList *s;
+ IntervalTreeRoot *map_info = read_self_maps();
+ IntervalTreeNode *s;
int count;
- for (s = map_info; s; s = g_slist_next(s)) {
- MapInfo *e = (MapInfo *) s->data;
+ for (s = interval_tree_iter_first(map_info, 0, -1); s;
+ s = interval_tree_iter_next(s, 0, -1)) {
+ MapInfo *e = container_of(s, MapInfo, itree);
- if (h2g_valid(e->start)) {
- unsigned long min = e->start;
- unsigned long max = e->end;
+ if (h2g_valid(e->itree.start)) {
+ unsigned long min = e->itree.start;
+ unsigned long max = e->itree.last + 1;
int flags = page_get_flags(h2g(min));
const char *path;
diff --git a/util/selfmap.c b/util/selfmap.c
index 2c14f019ce..4db5b42651 100644
--- a/util/selfmap.c
+++ b/util/selfmap.c
@@ -10,74 +10,98 @@
#include "qemu/cutils.h"
#include "qemu/selfmap.h"
-GSList *read_self_maps(void)
+IntervalTreeRoot *read_self_maps(void)
{
- gchar *maps;
- GSList *map_info = NULL;
+ IntervalTreeRoot *root;
+ gchar *maps, **lines;
+ guint i, nlines;
- if (g_file_get_contents("/proc/self/maps", &maps, NULL, NULL)) {
- gchar **lines = g_strsplit(maps, "\n", 0);
- int i, entries = g_strv_length(lines);
+ if (!g_file_get_contents("/proc/self/maps", &maps, NULL, NULL)) {
+ return NULL;
+ }
- for (i = 0; i < entries; i++) {
- gchar **fields = g_strsplit(lines[i], " ", 6);
- if (g_strv_length(fields) > 4) {
- MapInfo *e = g_new0(MapInfo, 1);
- int errors = 0;
- const char *end;
+ root = g_new0(IntervalTreeRoot, 1);
+ lines = g_strsplit(maps, "\n", 0);
+ nlines = g_strv_length(lines);
- errors |= qemu_strtoul(fields[0], &end, 16, &e->start);
- errors |= qemu_strtoul(end + 1, NULL, 16, &e->end);
+ for (i = 0; i < nlines; i++) {
+ gchar **fields = g_strsplit(lines[i], " ", 6);
+ guint nfields = g_strv_length(fields);
+
+ if (nfields > 4) {
+ uint64_t start, end, offset, inode;
+ int errors = 0;
+ const char *p;
+
+ errors |= qemu_strtou64(fields[0], &p, 16, &start);
+ errors |= qemu_strtou64(p + 1, NULL, 16, &end);
+ errors |= qemu_strtou64(fields[2], NULL, 16, &offset);
+ errors |= qemu_strtou64(fields[4], NULL, 10, &inode);
+
+ if (!errors) {
+ size_t dev_len, path_len;
+ MapInfo *e;
+
+ dev_len = strlen(fields[3]) + 1;
+ if (nfields == 6) {
+ p = fields[5];
+ p += strspn(p, " ");
+ path_len = strlen(p) + 1;
+ } else {
+ p = NULL;
+ path_len = 0;
+ }
+
+ e = g_malloc0(sizeof(*e) + dev_len + path_len);
+
+ e->itree.start = start;
+ e->itree.last = end - 1;
+ e->offset = offset;
+ e->inode = inode;
e->is_read = fields[1][0] == 'r';
e->is_write = fields[1][1] == 'w';
e->is_exec = fields[1][2] == 'x';
e->is_priv = fields[1][3] == 'p';
- errors |= qemu_strtoul(fields[2], NULL, 16, &e->offset);
- e->dev = g_strdup(fields[3]);
- errors |= qemu_strtou64(fields[4], NULL, 10, &e->inode);
-
- if (!errors) {
- /*
- * The last field may have leading spaces which we
- * need to strip.
- */
- if (g_strv_length(fields) == 6) {
- e->path = g_strdup(g_strchug(fields[5]));
- }
- map_info = g_slist_prepend(map_info, e);
- } else {
- g_free(e->dev);
- g_free(e);
+ memcpy(e->dev, fields[3], dev_len);
+ if (path_len) {
+ e->path = memcpy(e->dev + dev_len, p, path_len);
}
+
+ interval_tree_insert(&e->itree, root);
}
-
- g_strfreev(fields);
}
- g_strfreev(lines);
- g_free(maps);
+ g_strfreev(fields);
}
+ g_strfreev(lines);
+ g_free(maps);
- /* ensure the map data is in the same order we collected it */
- return g_slist_reverse(map_info);
+ return root;
}
/**
* free_self_maps:
- * @info: a GSlist
+ * @root: an interval tree
*
- * Free a list of MapInfo structures.
+ * Free a tree of MapInfo structures.
+ * Since we allocated each MapInfo in one chunk, we need not consider the
+ * contents and can simply free each RBNode.
*/
-static void free_info(gpointer data)
+
+static void free_rbnode(RBNode *n)
{
- MapInfo *e = (MapInfo *) data;
- g_free(e->dev);
- g_free(e->path);
- g_free(e);
+ if (n) {
+ free_rbnode(n->rb_left);
+ free_rbnode(n->rb_right);
+ g_free(n);
+ }
}
-void free_self_maps(GSList *info)
+void free_self_maps(IntervalTreeRoot *root)
{
- g_slist_free_full(info, &free_info);
+ if (root) {
+ free_rbnode(root->rb_root.rb_node);
+ g_free(root);
+ }
}
--
2.34.1
