util/interval-tree: Check root for null in interval_tree_iter_first

Fix a crash in qemu-user when running

cat /proc/self/maps

in a chroot, where /proc isn't mounted.

The problem was introduce

util/interval-tree: Check root for null in interval_tree_iter_first

Fix a crash in qemu-user when running

cat /proc/self/maps

in a chroot, where /proc isn't mounted.

The problem was introduced by commit 3ce3dd8ca965 ("util/selfmap:
Rewrite using qemu/interval-tree.h") where in open_self_maps_1() the
function read_self_maps() is called and which returns NULL if it can't
read the hosts /proc/self/maps file. Afterwards that NULL is fed into
interval_tree_iter_first() which doesn't check if the root node is NULL.

Fix it by adding a check if root is NULL and return NULL in that case.

Signed-off-by: Helge Deller <deller@gmx.de>
Fixes: 3ce3dd8ca965 ("util/selfmap: Rewrite using qemu/interval-tree.h")
Message-Id: <ZNOsq6Z7t/eyIG/9@p100>
Reviewed-by: Richard Henderson <richard.henderson@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>

show more ...

util/interval-tree: Use qatomic_read/set for rb_parent_color

While less susceptible to optimization problems than left and right,
interval_tree_iter_next also reads rb_parent(), so make sure that
st

util/interval-tree: Use qatomic_read/set for rb_parent_color

While less susceptible to optimization problems than left and right,
interval_tree_iter_next also reads rb_parent(), so make sure that
stores and loads are atomic.

This goes further than technically required, changing all loads to
be atomic, rather than simply the ones in the iteration side. But
it doesn't really affect the code generation on the rebalance side
and is cleaner to handle everything the same.

Reviewed-by: Peter Maydell <peter.maydell@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>

show more ...

util/interval-tree: Introduce pc_parent

Reviewed-by: Peter Maydell <peter.maydell@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>

util/interval-tree: Use qatomic_set_mb in rb_link_node

Ensure that the stores to rb_left and rb_right are complete before
inserting the new node into the tree. Otherwise a concurrent reader
could s

util/interval-tree: Use qatomic_set_mb in rb_link_node

Ensure that the stores to rb_left and rb_right are complete before
inserting the new node into the tree. Otherwise a concurrent reader
could see garbage in the new leaf.

Cc: qemu-stable@nongnu.org
Reviewed-by: Peter Maydell <peter.maydell@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>

show more ...

util/interval-tree: Use qatomic_read for left/right while searching

Fixes a race condition (generally without optimization) in which
the subtree is re-read after the protecting if condition.

Cc: qe

util/interval-tree: Use qatomic_read for left/right while searching

Fixes a race condition (generally without optimization) in which
the subtree is re-read after the protecting if condition.

Cc: qemu-stable@nongnu.org
Reviewed-by: Peter Maydell <peter.maydell@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>

show more ...

util: Add interval-tree.c

Copy and simplify the Linux kernel's interval_tree_generic.h,
instantiating for uint64_t.

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Signed-off-by: Richard Henderso

util: Add interval-tree.c

Copy and simplify the Linux kernel's interval_tree_generic.h,
instantiating for uint64_t.

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>

show more ...