From patchwork Wed Mar 22 15:07:34 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 665907 Delivered-To: patch@linaro.org Received: by 2002:a5d:4d08:0:0:0:0:0 with SMTP id z8csp204170wrt; Wed, 22 Mar 2023 08:09:53 -0700 (PDT) X-Google-Smtp-Source: AK7set8/ERMX0GvROcEuit+pY11bIPTKrLYjTCeUpovZ5DIv4+PUoEoqaiagiNQweaNXpOtouURm X-Received: by 2002:ad4:5d6c:0:b0:5ac:daf1:1ac1 with SMTP id fn12-20020ad45d6c000000b005acdaf11ac1mr7121343qvb.27.1679497793736; Wed, 22 Mar 2023 08:09:53 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1679497793; cv=none; d=google.com; s=arc-20160816; b=KqHq1Kj59tRvoDLSQeWqrcsdY4u/8OQnOatr+H8CH7cg326DTPP+4OqxWxk1c3MnxM jFoVulMHi1IY1//stIs2rF0m6se2LiPszEuvQY8g7tcAP0e4r9e3x7z1NddSdASgWhpU mv6v/m+s9lwLDrUxhO2U0D3bPuKS17QgUcyGrH6o4+MzVaDg5S0oWWOFOk7Rq14BKSnE YolfPaspZxrZZQgxzi90il07U8mATblje6d4cIrQOpahhHN1rV7BAYecgdJSPtRmAoNH Spejprt8cBKvw9tEHb0u4DgYtlS8JDkfpDq+jEazi0pYh3AT74Ea1GQSrysZEwezmaV0 dTBw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=VljO4/V5RF5GdhSHEc7pp4EFkxkOTq4sQuAyZ0els/g=; b=lY89ed9WAML04Ka/9LaSRuRR9nM366z6QUx/ELGawA51SgO8cKvz5bdC8+0/IJa3DO tsPaQPtfOapWGr955ZPYbZLfUb6lz9bDfw9biDvaAiOFSYSdbpwHEWHoPAWCYOeBj359 Pak37PvyAygw7XXNdyWwTH5+Za1i7o1fPByVWPgtUwWomoiGjO9chnpa7I6YOgLM5rnz jfaYEaI9pbep6DulEn203XMc8k/cAnxIOXKteWuRS7HMZ8lUxEb5ly+Dj+BnrcRiUlA2 WEQkseQBfBB9wv+X1Dp9x1UPCFBgnqFcb6lgWN0MN/u8ObOFHEaEpeJ7xcyh683nwA+n yOaQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=VHEhAhO7; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [209.51.188.17]) by mx.google.com with ESMTPS id q7-20020ad44347000000b005a4a6987041si9890438qvs.117.2023.03.22.08.09.53 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 22 Mar 2023 08:09:53 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=VHEhAhO7; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pf04H-0002wC-BF; Wed, 22 Mar 2023 11:08:01 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pf04A-0002ib-Hm for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:07:54 -0400 Received: from mail-pl1-x62e.google.com ([2607:f8b0:4864:20::62e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pf045-0007FG-Hj for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:07:54 -0400 Received: by mail-pl1-x62e.google.com with SMTP id iw3so19555242plb.6 for ; Wed, 22 Mar 2023 08:07:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1679497668; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=VljO4/V5RF5GdhSHEc7pp4EFkxkOTq4sQuAyZ0els/g=; b=VHEhAhO7zROdVs/gyfzJ/v4L185K6dpoqT/L6fkRYMEiCIN5PZDUa5LcM0+snhXQ9q h7LEpAdy8hujgsHuuKxCeWsO+rzfP08v+UmTpB0Tia5npnCwJrK8NW34krs3mdtyQz3q 12kOhHhbYxMRHc+UteN983t0oKNlFBBFXNKB29n2dwT2tSEU+gMdePFBzJFBOg5bqHQn 35dmqpQKfycfEp7YqEK7ARepmULoU8rrSUGEHr03RMGkleLNVrXmqsJRlQYTmTIfuEg0 8g5BMc7CtyKz9niHkic7IZaObRYQWsmESLso8+Z++xP9DjkhUB2lmVbWox8rrY0uNsPi El4g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679497668; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=VljO4/V5RF5GdhSHEc7pp4EFkxkOTq4sQuAyZ0els/g=; b=7V7figW9NxuvLUfVsM4xYgmAtmZ1+CgHfZz4m3k35AjB+C1xwFMB9GNi8Dz/QSoNgV mxD/1Y6cY2XAjlnQJPihYEjFQ5H6Ga6WOChPGzMIjG5F1iQ9KodydwCR9/o1mdLgiF/E kMzgnBIwBXvexnVX8H/TfULYClEZ/r9j2LB+zN3FJg/S0AsLhwrFokoe2dn5alaLxp64 dJ/cHUsEq/WqxqPNIYdmwuRNIPTZ9UUlqg6Sdd1l+4pgZwAFuk/rWvtafVQmr8RPWZQa 5ELffN3r8ZwOqK/5YOxuQaArUyr9pkyrhoTR2j7RjQ13OWXGqjOgsX8gFuDvrOHo80Oh G4bw== X-Gm-Message-State: AO0yUKU7I8whTlWxJEeTKXvA1Iwil+cKAKm31Mq8xSY6o/mayd6g3Xfk N7TR930k7bizukDaaSD5ESMgLeukJRRXRVZKBH0= X-Received: by 2002:a17:902:db0f:b0:1a1:bff4:49e9 with SMTP id m15-20020a170902db0f00b001a1bff449e9mr3521586plx.23.1679497667376; Wed, 22 Mar 2023 08:07:47 -0700 (PDT) Received: from stoup.. (24-113-166-229.wavecable.com. [24.113.166.229]) by smtp.gmail.com with ESMTPSA id 17-20020a170902ee5100b0019339f3368asm10757555plo.3.2023.03.22.08.07.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Mar 2023 08:07:47 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: cota@braap.org, peter.maydell@linaro.org Subject: [PATCH for-8.0 01/11] util: import GTree as QTree Date: Wed, 22 Mar 2023 08:07:34 -0700 Message-Id: <20230322150744.175010-2-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230322150744.175010-1-richard.henderson@linaro.org> References: <20230322150744.175010-1-richard.henderson@linaro.org> MIME-Version: 1.0 Received-SPF: pass client-ip=2607:f8b0:4864:20::62e; envelope-from=richard.henderson@linaro.org; helo=mail-pl1-x62e.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: qemu-devel-bounces+patch=linaro.org@nongnu.org From: Emilio Cota The only reason to add this implementation is to control the memory allocator used. Some users (e.g. TCG) cannot work reliably in multi-threaded environments (e.g. forking in user-mode) with GTree's allocator, GSlice. See https://gitlab.com/qemu-project/qemu/-/issues/285 for details. Importing GTree is a temporary workaround until GTree migrates away from GSlice. This implementation is identical to that in glib v2.75.0, except that we don't import recent additions to the API nor deprecated API calls, none of which are used in QEMU. I've imported tests from glib and added a benchmark just to make sure that performance is similar. Note: it cannot be identical because (1) we are not using GSlice, (2) we use different compilation flags (e.g. -fPIC) and (3) we're linking statically. $ cat /proc/cpuinfo| grep 'model name' | head -1 model name : AMD Ryzen 7 PRO 5850U with Radeon Graphics $ echo '0' | sudo tee /sys/devices/system/cpu/cpufreq/boost $ tests/bench/qtree-bench Tree Op 32 1024 4096 131072 1048576 ------------------------------------------------------------------------------------------------ GTree Lookup 83.23 43.08 25.31 19.40 16.22 QTree Lookup 113.42 (1.36x) 53.83 (1.25x) 28.38 (1.12x) 17.64 (0.91x) 13.04 (0.80x) GTree Insert 44.23 29.37 25.83 19.49 17.03 QTree Insert 46.87 (1.06x) 25.62 (0.87x) 24.29 (0.94x) 16.83 (0.86x) 12.97 (0.76x) GTree Remove 53.27 35.15 31.43 24.64 16.70 QTree Remove 57.32 (1.08x) 41.76 (1.19x) 38.37 (1.22x) 29.30 (1.19x) 15.07 (0.90x) GTree RemoveAll 135.44 127.52 126.72 120.11 64.34 QTree RemoveAll 127.15 (0.94x) 110.37 (0.87x) 107.97 (0.85x) 97.13 (0.81x) 55.10 (0.86x) GTree Traverse 277.71 276.09 272.78 246.72 98.47 QTree Traverse 370.33 (1.33x) 411.97 (1.49x) 400.23 (1.47x) 262.82 (1.07x) 78.52 (0.80x) ------------------------------------------------------------------------------------------------ As a sanity check, the same benchmark when Glib's version is >= $glib_dropped_gslice_version (i.e. QTree == GTree): Tree Op 32 1024 4096 131072 1048576 ------------------------------------------------------------------------------------------------ GTree Lookup 82.72 43.09 24.18 19.73 16.09 QTree Lookup 81.82 (0.99x) 43.10 (1.00x) 24.20 (1.00x) 19.76 (1.00x) 16.26 (1.01x) GTree Insert 45.07 29.62 26.34 19.90 17.18 QTree Insert 45.72 (1.01x) 29.60 (1.00x) 26.38 (1.00x) 19.71 (0.99x) 17.20 (1.00x) GTree Remove 54.48 35.36 31.77 24.97 16.95 QTree Remove 54.46 (1.00x) 35.32 (1.00x) 31.77 (1.00x) 24.91 (1.00x) 17.15 (1.01x) GTree RemoveAll 140.68 127.36 125.43 121.45 68.20 QTree RemoveAll 140.65 (1.00x) 127.64 (1.00x) 125.01 (1.00x) 121.73 (1.00x) 67.06 (0.98x) GTree Traverse 278.68 276.05 266.75 251.65 104.93 QTree Traverse 278.31 (1.00x) 275.78 (1.00x) 266.42 (1.00x) 247.89 (0.99x) 104.58 (1.00x) ------------------------------------------------------------------------------------------------ Signed-off-by: Emilio Cota Message-Id: <20230205163758.416992-2-cota@braap.org> Signed-off-by: Richard Henderson --- configure | 15 + meson.build | 4 + include/qemu/qtree.h | 201 ++++++ tests/bench/qtree-bench.c | 286 ++++++++ tests/unit/test-qtree.c | 333 +++++++++ util/qtree.c | 1390 +++++++++++++++++++++++++++++++++++++ tests/bench/meson.build | 4 + tests/unit/meson.build | 1 + util/meson.build | 1 + 9 files changed, 2235 insertions(+) create mode 100644 include/qemu/qtree.h create mode 100644 tests/bench/qtree-bench.c create mode 100644 tests/unit/test-qtree.c create mode 100644 util/qtree.c diff --git a/configure b/configure index 05bed4f4a1..800b5850f4 100755 --- a/configure +++ b/configure @@ -231,6 +231,7 @@ safe_stack="" use_containers="yes" gdb_bin=$(command -v "gdb-multiarch" || command -v "gdb") gdb_arches="" +glib_has_gslice="no" if test -e "$source_path/.git" then @@ -1494,6 +1495,17 @@ for i in $glib_modules; do fi done +# Check whether glib has gslice, which we have to avoid for correctness. +# TODO: remove this check and the corresponding workaround (qtree) when +# the minimum supported glib is >= $glib_dropped_gslice_version. +glib_dropped_gslice_version=2.75.3 +for i in $glib_modules; do + if ! $pkg_config --atleast-version=$glib_dropped_gslice_version $i; then + glib_has_gslice="yes" + break + fi +done + glib_bindir="$($pkg_config --variable=bindir glib-2.0)" if test -z "$glib_bindir" ; then glib_bindir="$($pkg_config --variable=prefix glib-2.0)"/bin @@ -2420,6 +2432,9 @@ echo "GLIB_CFLAGS=$glib_cflags" >> $config_host_mak echo "GLIB_LIBS=$glib_libs" >> $config_host_mak echo "GLIB_BINDIR=$glib_bindir" >> $config_host_mak echo "GLIB_VERSION=$($pkg_config --modversion glib-2.0)" >> $config_host_mak +if test "$glib_has_gslice" = "yes" ; then + echo "HAVE_GLIB_WITH_SLICE_ALLOCATOR=y" >> $config_host_mak +fi echo "QEMU_LDFLAGS=$QEMU_LDFLAGS" >> $config_host_mak echo "EXESUF=$EXESUF" >> $config_host_mak diff --git a/meson.build b/meson.build index 29f8644d6d..c44d05a13f 100644 --- a/meson.build +++ b/meson.build @@ -508,6 +508,10 @@ glib = declare_dependency(compile_args: config_host['GLIB_CFLAGS'].split(), }) # override glib dep with the configure results (for subprojects) meson.override_dependency('glib-2.0', glib) +# pass down whether Glib has the slice allocator +if config_host.has_key('HAVE_GLIB_WITH_SLICE_ALLOCATOR') + config_host_data.set('HAVE_GLIB_WITH_SLICE_ALLOCATOR', true) +endif gio = not_found gdbus_codegen = not_found diff --git a/include/qemu/qtree.h b/include/qemu/qtree.h new file mode 100644 index 0000000000..69fe74b50d --- /dev/null +++ b/include/qemu/qtree.h @@ -0,0 +1,201 @@ +/* + * GLIB - Library of useful routines for C programming + * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald + * + * SPDX-License-Identifier: LGPL-2.1-or-later + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, see . + */ + +/* + * Modified by the GLib Team and others 1997-2000. See the AUTHORS + * file for a list of people on the GLib Team. See the ChangeLog + * files for a list of changes. These files are distributed with + * GLib at ftp://ftp.gtk.org/pub/gtk/. + */ + +/* + * QTree is a partial import of Glib's GTree. The parts excluded correspond + * to API calls either deprecated (e.g. g_tree_traverse) or recently added + * (e.g. g_tree_search_node, added in 2.68); neither have callers in QEMU. + * + * The reason for this import is to allow us to control the memory allocator + * used by the tree implementation. Until Glib 2.75.3, GTree uses Glib's + * slice allocator, which causes problems when forking in user-mode; + * see https://gitlab.com/qemu-project/qemu/-/issues/285 and glib's + * "45b5a6c1e gslice: Remove slice allocator and use malloc() instead". + * + * TODO: remove QTree when QEMU's minimum Glib version is >= 2.75.3. + */ + +#ifndef QEMU_QTREE_H +#define QEMU_QTREE_H + +#include "qemu/osdep.h" + +#ifdef HAVE_GLIB_WITH_SLICE_ALLOCATOR + +typedef struct _QTree QTree; + +typedef struct _QTreeNode QTreeNode; + +typedef gboolean (*QTraverseNodeFunc)(QTreeNode *node, + gpointer user_data); + +/* + * Balanced binary trees + */ +QTree *q_tree_new(GCompareFunc key_compare_func); +QTree *q_tree_new_with_data(GCompareDataFunc key_compare_func, + gpointer key_compare_data); +QTree *q_tree_new_full(GCompareDataFunc key_compare_func, + gpointer key_compare_data, + GDestroyNotify key_destroy_func, + GDestroyNotify value_destroy_func); +QTree *q_tree_ref(QTree *tree); +void q_tree_unref(QTree *tree); +void q_tree_destroy(QTree *tree); +void q_tree_insert(QTree *tree, + gpointer key, + gpointer value); +void q_tree_replace(QTree *tree, + gpointer key, + gpointer value); +gboolean q_tree_remove(QTree *tree, + gconstpointer key); +gboolean q_tree_steal(QTree *tree, + gconstpointer key); +gpointer q_tree_lookup(QTree *tree, + gconstpointer key); +gboolean q_tree_lookup_extended(QTree *tree, + gconstpointer lookup_key, + gpointer *orig_key, + gpointer *value); +void q_tree_foreach(QTree *tree, + GTraverseFunc func, + gpointer user_data); +gpointer q_tree_search(QTree *tree, + GCompareFunc search_func, + gconstpointer user_data); +gint q_tree_height(QTree *tree); +gint q_tree_nnodes(QTree *tree); + +#else /* !HAVE_GLIB_WITH_SLICE_ALLOCATOR */ + +typedef GTree QTree; +typedef GTreeNode QTreeNode; +typedef GTraverseNodeFunc QTraverseNodeFunc; + +static inline QTree *q_tree_new(GCompareFunc key_compare_func) +{ + return g_tree_new(key_compare_func); +} + +static inline QTree *q_tree_new_with_data(GCompareDataFunc key_compare_func, + gpointer key_compare_data) +{ + return g_tree_new_with_data(key_compare_func, key_compare_data); +} + +static inline QTree *q_tree_new_full(GCompareDataFunc key_compare_func, + gpointer key_compare_data, + GDestroyNotify key_destroy_func, + GDestroyNotify value_destroy_func) +{ + return g_tree_new_full(key_compare_func, key_compare_data, + key_destroy_func, value_destroy_func); +} + +static inline QTree *q_tree_ref(QTree *tree) +{ + return g_tree_ref(tree); +} + +static inline void q_tree_unref(QTree *tree) +{ + g_tree_unref(tree); +} + +static inline void q_tree_destroy(QTree *tree) +{ + g_tree_destroy(tree); +} + +static inline void q_tree_insert(QTree *tree, + gpointer key, + gpointer value) +{ + g_tree_insert(tree, key, value); +} + +static inline void q_tree_replace(QTree *tree, + gpointer key, + gpointer value) +{ + g_tree_replace(tree, key, value); +} + +static inline gboolean q_tree_remove(QTree *tree, + gconstpointer key) +{ + return g_tree_remove(tree, key); +} + +static inline gboolean q_tree_steal(QTree *tree, + gconstpointer key) +{ + return g_tree_steal(tree, key); +} + +static inline gpointer q_tree_lookup(QTree *tree, + gconstpointer key) +{ + return g_tree_lookup(tree, key); +} + +static inline gboolean q_tree_lookup_extended(QTree *tree, + gconstpointer lookup_key, + gpointer *orig_key, + gpointer *value) +{ + return g_tree_lookup_extended(tree, lookup_key, orig_key, value); +} + +static inline void q_tree_foreach(QTree *tree, + GTraverseFunc func, + gpointer user_data) +{ + return g_tree_foreach(tree, func, user_data); +} + +static inline gpointer q_tree_search(QTree *tree, + GCompareFunc search_func, + gconstpointer user_data) +{ + return g_tree_search(tree, search_func, user_data); +} + +static inline gint q_tree_height(QTree *tree) +{ + return g_tree_height(tree); +} + +static inline gint q_tree_nnodes(QTree *tree) +{ + return g_tree_nnodes(tree); +} + +#endif /* HAVE_GLIB_WITH_SLICE_ALLOCATOR */ + +#endif /* QEMU_QTREE_H */ diff --git a/tests/bench/qtree-bench.c b/tests/bench/qtree-bench.c new file mode 100644 index 0000000000..f3d7edc76d --- /dev/null +++ b/tests/bench/qtree-bench.c @@ -0,0 +1,286 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +#include "qemu/osdep.h" +#include "qemu/qtree.h" +#include "qemu/timer.h" + +enum tree_op { + OP_LOOKUP, + OP_INSERT, + OP_REMOVE, + OP_REMOVE_ALL, + OP_TRAVERSE, +}; + +struct benchmark { + const char * const name; + enum tree_op op; + bool fill_on_init; +}; + +enum impl_type { + IMPL_GTREE, + IMPL_QTREE, +}; + +struct tree_implementation { + const char * const name; + enum impl_type type; +}; + +static const struct benchmark benchmarks[] = { + { + .name = "Lookup", + .op = OP_LOOKUP, + .fill_on_init = true, + }, + { + .name = "Insert", + .op = OP_INSERT, + .fill_on_init = false, + }, + { + .name = "Remove", + .op = OP_REMOVE, + .fill_on_init = true, + }, + { + .name = "RemoveAll", + .op = OP_REMOVE_ALL, + .fill_on_init = true, + }, + { + .name = "Traverse", + .op = OP_TRAVERSE, + .fill_on_init = true, + }, +}; + +static const struct tree_implementation impls[] = { + { + .name = "GTree", + .type = IMPL_GTREE, + }, + { + .name = "QTree", + .type = IMPL_QTREE, + }, +}; + +static int compare_func(const void *ap, const void *bp) +{ + const size_t *a = ap; + const size_t *b = bp; + + return *a - *b; +} + +static void init_empty_tree_and_keys(enum impl_type impl, + void **ret_tree, size_t **ret_keys, + size_t n_elems) +{ + size_t *keys = g_malloc_n(n_elems, sizeof(*keys)); + for (size_t i = 0; i < n_elems; i++) { + keys[i] = i; + } + + void *tree; + switch (impl) { + case IMPL_GTREE: + tree = g_tree_new(compare_func); + break; + case IMPL_QTREE: + tree = q_tree_new(compare_func); + break; + default: + g_assert_not_reached(); + } + + *ret_tree = tree; + *ret_keys = keys; +} + +static gboolean traverse_func(gpointer key, gpointer value, gpointer data) +{ + return FALSE; +} + +static inline void remove_all(void *tree, enum impl_type impl) +{ + switch (impl) { + case IMPL_GTREE: + g_tree_destroy(tree); + break; + case IMPL_QTREE: + q_tree_destroy(tree); + break; + default: + g_assert_not_reached(); + } +} + +static int64_t run_benchmark(const struct benchmark *bench, + enum impl_type impl, + size_t n_elems) +{ + void *tree; + size_t *keys; + + init_empty_tree_and_keys(impl, &tree, &keys, n_elems); + if (bench->fill_on_init) { + for (size_t i = 0; i < n_elems; i++) { + switch (impl) { + case IMPL_GTREE: + g_tree_insert(tree, &keys[i], &keys[i]); + break; + case IMPL_QTREE: + q_tree_insert(tree, &keys[i], &keys[i]); + break; + default: + g_assert_not_reached(); + } + } + } + + int64_t start_ns = get_clock(); + switch (bench->op) { + case OP_LOOKUP: + for (size_t i = 0; i < n_elems; i++) { + void *value; + switch (impl) { + case IMPL_GTREE: + value = g_tree_lookup(tree, &keys[i]); + break; + case IMPL_QTREE: + value = q_tree_lookup(tree, &keys[i]); + break; + default: + g_assert_not_reached(); + } + (void)value; + } + break; + case OP_INSERT: + for (size_t i = 0; i < n_elems; i++) { + switch (impl) { + case IMPL_GTREE: + g_tree_insert(tree, &keys[i], &keys[i]); + break; + case IMPL_QTREE: + q_tree_insert(tree, &keys[i], &keys[i]); + break; + default: + g_assert_not_reached(); + } + } + break; + case OP_REMOVE: + for (size_t i = 0; i < n_elems; i++) { + switch (impl) { + case IMPL_GTREE: + g_tree_remove(tree, &keys[i]); + break; + case IMPL_QTREE: + q_tree_remove(tree, &keys[i]); + break; + default: + g_assert_not_reached(); + } + } + break; + case OP_REMOVE_ALL: + remove_all(tree, impl); + break; + case OP_TRAVERSE: + switch (impl) { + case IMPL_GTREE: + g_tree_foreach(tree, traverse_func, NULL); + break; + case IMPL_QTREE: + q_tree_foreach(tree, traverse_func, NULL); + break; + default: + g_assert_not_reached(); + } + break; + default: + g_assert_not_reached(); + } + int64_t ns = get_clock() - start_ns; + + if (bench->op != OP_REMOVE_ALL) { + remove_all(tree, impl); + } + g_free(keys); + + return ns; +} + +int main(int argc, char *argv[]) +{ + size_t sizes[] = { + 32, + 1024, + 1024 * 4, + 1024 * 128, + 1024 * 1024, + }; + + double res[ARRAY_SIZE(benchmarks)][ARRAY_SIZE(impls)][ARRAY_SIZE(sizes)]; + for (int i = 0; i < ARRAY_SIZE(sizes); i++) { + size_t size = sizes[i]; + for (int j = 0; j < ARRAY_SIZE(impls); j++) { + const struct tree_implementation *impl = &impls[j]; + for (int k = 0; k < ARRAY_SIZE(benchmarks); k++) { + const struct benchmark *bench = &benchmarks[k]; + + /* warm-up run */ + run_benchmark(bench, impl->type, size); + + int64_t total_ns = 0; + int64_t n_runs = 0; + while (total_ns < 2e8 || n_runs < 5) { + total_ns += run_benchmark(bench, impl->type, size); + n_runs++; + } + double ns_per_run = (double)total_ns / n_runs; + + /* Throughput, in Mops/s */ + res[k][j][i] = size / ns_per_run * 1e3; + } + } + } + + printf("# Results' breakdown: Tree, Op and #Elements. Units: Mops/s\n"); + printf("%5s %10s ", "Tree", "Op"); + for (int i = 0; i < ARRAY_SIZE(sizes); i++) { + printf("%7zu ", sizes[i]); + } + printf("\n"); + char separator[97]; + for (int i = 0; i < ARRAY_SIZE(separator) - 1; i++) { + separator[i] = '-'; + } + separator[ARRAY_SIZE(separator) - 1] = '\0'; + printf("%s\n", separator); + for (int i = 0; i < ARRAY_SIZE(benchmarks); i++) { + for (int j = 0; j < ARRAY_SIZE(impls); j++) { + printf("%5s %10s ", impls[j].name, benchmarks[i].name); + for (int k = 0; k < ARRAY_SIZE(sizes); k++) { + printf("%7.2f ", res[i][j][k]); + if (j == 0) { + printf(" "); + } else { + if (res[i][0][k] != 0) { + double speedup = res[i][j][k] / res[i][0][k]; + printf("(%4.2fx) ", speedup); + } else { + printf("( ) "); + } + } + } + printf("\n"); + } + } + printf("%s\n", separator); + return 0; +} diff --git a/tests/unit/test-qtree.c b/tests/unit/test-qtree.c new file mode 100644 index 0000000000..4d836d22c7 --- /dev/null +++ b/tests/unit/test-qtree.c @@ -0,0 +1,333 @@ +/* + * SPDX-License-Identifier: LGPL-2.1-or-later + * + * Tests for QTree. + * Original source: glib + * https://gitlab.gnome.org/GNOME/glib/-/blob/main/glib/tests/tree.c + * LGPL license. + * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald + */ + +#include "qemu/osdep.h" +#include "qemu/qtree.h" + +static gint my_compare(gconstpointer a, gconstpointer b) +{ + const char *cha = a; + const char *chb = b; + + return *cha - *chb; +} + +static gint my_compare_with_data(gconstpointer a, + gconstpointer b, + gpointer user_data) +{ + const char *cha = a; + const char *chb = b; + + /* just check that we got the right data */ + g_assert(GPOINTER_TO_INT(user_data) == 123); + + return *cha - *chb; +} + +static gint my_search(gconstpointer a, gconstpointer b) +{ + return my_compare(b, a); +} + +static gpointer destroyed_key; +static gpointer destroyed_value; +static guint destroyed_key_count; +static guint destroyed_value_count; + +static void my_key_destroy(gpointer key) +{ + destroyed_key = key; + destroyed_key_count++; +} + +static void my_value_destroy(gpointer value) +{ + destroyed_value = value; + destroyed_value_count++; +} + +static gint my_traverse(gpointer key, gpointer value, gpointer data) +{ + char *ch = key; + + g_assert((*ch) > 0); + + if (*ch == 'd') { + return TRUE; + } + + return FALSE; +} + +char chars[] = + "0123456789" + "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + "abcdefghijklmnopqrstuvwxyz"; + +char chars2[] = + "0123456789" + "abcdefghijklmnopqrstuvwxyz"; + +static gint check_order(gpointer key, gpointer value, gpointer data) +{ + char **p = data; + char *ch = key; + + g_assert(**p == *ch); + + (*p)++; + + return FALSE; +} + +static void test_tree_search(void) +{ + gint i; + QTree *tree; + gboolean removed; + gchar c; + gchar *p, *d; + + tree = q_tree_new_with_data(my_compare_with_data, GINT_TO_POINTER(123)); + + for (i = 0; chars[i]; i++) { + q_tree_insert(tree, &chars[i], &chars[i]); + } + + q_tree_foreach(tree, my_traverse, NULL); + + g_assert(q_tree_nnodes(tree) == strlen(chars)); + g_assert(q_tree_height(tree) == 6); + + p = chars; + q_tree_foreach(tree, check_order, &p); + + for (i = 0; i < 26; i++) { + removed = q_tree_remove(tree, &chars[i + 10]); + g_assert(removed); + } + + c = '\0'; + removed = q_tree_remove(tree, &c); + g_assert(!removed); + + q_tree_foreach(tree, my_traverse, NULL); + + g_assert(q_tree_nnodes(tree) == strlen(chars2)); + g_assert(q_tree_height(tree) == 6); + + p = chars2; + q_tree_foreach(tree, check_order, &p); + + for (i = 25; i >= 0; i--) { + q_tree_insert(tree, &chars[i + 10], &chars[i + 10]); + } + + p = chars; + q_tree_foreach(tree, check_order, &p); + + c = '0'; + p = q_tree_lookup(tree, &c); + g_assert(p && *p == c); + g_assert(q_tree_lookup_extended(tree, &c, (gpointer *)&d, (gpointer *)&p)); + g_assert(c == *d && c == *p); + + c = 'A'; + p = q_tree_lookup(tree, &c); + g_assert(p && *p == c); + + c = 'a'; + p = q_tree_lookup(tree, &c); + g_assert(p && *p == c); + + c = 'z'; + p = q_tree_lookup(tree, &c); + g_assert(p && *p == c); + + c = '!'; + p = q_tree_lookup(tree, &c); + g_assert(p == NULL); + + c = '='; + p = q_tree_lookup(tree, &c); + g_assert(p == NULL); + + c = '|'; + p = q_tree_lookup(tree, &c); + g_assert(p == NULL); + + c = '0'; + p = q_tree_search(tree, my_search, &c); + g_assert(p && *p == c); + + c = 'A'; + p = q_tree_search(tree, my_search, &c); + g_assert(p && *p == c); + + c = 'a'; + p = q_tree_search(tree, my_search, &c); + g_assert(p && *p == c); + + c = 'z'; + p = q_tree_search(tree, my_search, &c); + g_assert(p && *p == c); + + c = '!'; + p = q_tree_search(tree, my_search, &c); + g_assert(p == NULL); + + c = '='; + p = q_tree_search(tree, my_search, &c); + g_assert(p == NULL); + + c = '|'; + p = q_tree_search(tree, my_search, &c); + g_assert(p == NULL); + + q_tree_destroy(tree); +} + +static void test_tree_remove(void) +{ + QTree *tree; + char c, d; + gint i; + gboolean removed; + + tree = q_tree_new_full((GCompareDataFunc)my_compare, NULL, + my_key_destroy, + my_value_destroy); + + for (i = 0; chars[i]; i++) { + q_tree_insert(tree, &chars[i], &chars[i]); + } + + c = '0'; + q_tree_insert(tree, &c, &c); + g_assert(destroyed_key == &c); + g_assert(destroyed_value == &chars[0]); + destroyed_key = NULL; + destroyed_value = NULL; + + d = '1'; + q_tree_replace(tree, &d, &d); + g_assert(destroyed_key == &chars[1]); + g_assert(destroyed_value == &chars[1]); + destroyed_key = NULL; + destroyed_value = NULL; + + c = '2'; + removed = q_tree_remove(tree, &c); + g_assert(removed); + g_assert(destroyed_key == &chars[2]); + g_assert(destroyed_value == &chars[2]); + destroyed_key = NULL; + destroyed_value = NULL; + + c = '3'; + removed = q_tree_steal(tree, &c); + g_assert(removed); + g_assert(destroyed_key == NULL); + g_assert(destroyed_value == NULL); + + const gchar *remove = "omkjigfedba"; + for (i = 0; remove[i]; i++) { + removed = q_tree_remove(tree, &remove[i]); + g_assert(removed); + } + + q_tree_destroy(tree); +} + +static void test_tree_destroy(void) +{ + QTree *tree; + gint i; + + tree = q_tree_new(my_compare); + + for (i = 0; chars[i]; i++) { + q_tree_insert(tree, &chars[i], &chars[i]); + } + + g_assert(q_tree_nnodes(tree) == strlen(chars)); + + g_test_message("nnodes: %d", q_tree_nnodes(tree)); + q_tree_ref(tree); + q_tree_destroy(tree); + + g_test_message("nnodes: %d", q_tree_nnodes(tree)); + g_assert(q_tree_nnodes(tree) == 0); + + q_tree_unref(tree); +} + +static void test_tree_insert(void) +{ + QTree *tree; + gchar *p; + gint i; + gchar *scrambled; + + tree = q_tree_new(my_compare); + + for (i = 0; chars[i]; i++) { + q_tree_insert(tree, &chars[i], &chars[i]); + } + p = chars; + q_tree_foreach(tree, check_order, &p); + + q_tree_unref(tree); + tree = q_tree_new(my_compare); + + for (i = strlen(chars) - 1; i >= 0; i--) { + q_tree_insert(tree, &chars[i], &chars[i]); + } + p = chars; + q_tree_foreach(tree, check_order, &p); + + q_tree_unref(tree); + tree = q_tree_new(my_compare); + + scrambled = g_strdup(chars); + + for (i = 0; i < 30; i++) { + gchar tmp; + gint a, b; + + a = g_random_int_range(0, strlen(scrambled)); + b = g_random_int_range(0, strlen(scrambled)); + tmp = scrambled[a]; + scrambled[a] = scrambled[b]; + scrambled[b] = tmp; + } + + for (i = 0; scrambled[i]; i++) { + q_tree_insert(tree, &scrambled[i], &scrambled[i]); + } + p = chars; + q_tree_foreach(tree, check_order, &p); + + g_free(scrambled); + q_tree_unref(tree); +} + +int main(int argc, char *argv[]) +{ + g_test_init(&argc, &argv, NULL); + + g_test_add_func("/qtree/search", test_tree_search); + g_test_add_func("/qtree/remove", test_tree_remove); + g_test_add_func("/qtree/destroy", test_tree_destroy); + g_test_add_func("/qtree/insert", test_tree_insert); + + return g_test_run(); +} diff --git a/util/qtree.c b/util/qtree.c new file mode 100644 index 0000000000..deb46c187f --- /dev/null +++ b/util/qtree.c @@ -0,0 +1,1390 @@ +/* + * GLIB - Library of useful routines for C programming + * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald + * + * SPDX-License-Identifier: LGPL-2.1-or-later + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, see . + */ + +/* + * Modified by the GLib Team and others 1997-2000. See the AUTHORS + * file for a list of people on the GLib Team. See the ChangeLog + * files for a list of changes. These files are distributed with + * GLib at ftp://ftp.gtk.org/pub/gtk/. + */ + +/* + * MT safe + */ + +#include "qemu/osdep.h" +#include "qemu/qtree.h" + +/** + * SECTION:trees-binary + * @title: Balanced Binary Trees + * @short_description: a sorted collection of key/value pairs optimized + * for searching and traversing in order + * + * The #QTree structure and its associated functions provide a sorted + * collection of key/value pairs optimized for searching and traversing + * in order. This means that most of the operations (access, search, + * insertion, deletion, ...) on #QTree are O(log(n)) in average and O(n) + * in worst case for time complexity. But, note that maintaining a + * balanced sorted #QTree of n elements is done in time O(n log(n)). + * + * To create a new #QTree use q_tree_new(). + * + * To insert a key/value pair into a #QTree use q_tree_insert() + * (O(n log(n))). + * + * To remove a key/value pair use q_tree_remove() (O(n log(n))). + * + * To look up the value corresponding to a given key, use + * q_tree_lookup() and q_tree_lookup_extended(). + * + * To find out the number of nodes in a #QTree, use q_tree_nnodes(). To + * get the height of a #QTree, use q_tree_height(). + * + * To traverse a #QTree, calling a function for each node visited in + * the traversal, use q_tree_foreach(). + * + * To destroy a #QTree, use q_tree_destroy(). + **/ + +#define MAX_GTREE_HEIGHT 40 + +/** + * QTree: + * + * The QTree struct is an opaque data structure representing a + * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be + * accessed only by using the following functions. + */ +struct _QTree { + QTreeNode *root; + GCompareDataFunc key_compare; + GDestroyNotify key_destroy_func; + GDestroyNotify value_destroy_func; + gpointer key_compare_data; + guint nnodes; + gint ref_count; +}; + +struct _QTreeNode { + gpointer key; /* key for this node */ + gpointer value; /* value stored at this node */ + QTreeNode *left; /* left subtree */ + QTreeNode *right; /* right subtree */ + gint8 balance; /* height (right) - height (left) */ + guint8 left_child; + guint8 right_child; +}; + + +static QTreeNode *q_tree_node_new(gpointer key, + gpointer value); +static QTreeNode *q_tree_insert_internal(QTree *tree, + gpointer key, + gpointer value, + gboolean replace); +static gboolean q_tree_remove_internal(QTree *tree, + gconstpointer key, + gboolean steal); +static QTreeNode *q_tree_node_balance(QTreeNode *node); +static QTreeNode *q_tree_find_node(QTree *tree, + gconstpointer key); +static QTreeNode *q_tree_node_search(QTreeNode *node, + GCompareFunc search_func, + gconstpointer data); +static QTreeNode *q_tree_node_rotate_left(QTreeNode *node); +static QTreeNode *q_tree_node_rotate_right(QTreeNode *node); +#ifdef Q_TREE_DEBUG +static void q_tree_node_check(QTreeNode *node); +#endif + +static QTreeNode* +q_tree_node_new(gpointer key, + gpointer value) +{ + QTreeNode *node = g_new(QTreeNode, 1); + + node->balance = 0; + node->left = NULL; + node->right = NULL; + node->left_child = FALSE; + node->right_child = FALSE; + node->key = key; + node->value = value; + + return node; +} + +/** + * q_tree_new: + * @key_compare_func: the function used to order the nodes in the #QTree. + * It should return values similar to the standard strcmp() function - + * 0 if the two arguments are equal, a negative value if the first argument + * comes before the second, or a positive value if the first argument comes + * after the second. + * + * Creates a new #QTree. + * + * Returns: a newly allocated #QTree + */ +QTree * +q_tree_new(GCompareFunc key_compare_func) +{ + g_return_val_if_fail(key_compare_func != NULL, NULL); + + return q_tree_new_full((GCompareDataFunc) key_compare_func, NULL, + NULL, NULL); +} + +/** + * q_tree_new_with_data: + * @key_compare_func: qsort()-style comparison function + * @key_compare_data: data to pass to comparison function + * + * Creates a new #QTree with a comparison function that accepts user data. + * See q_tree_new() for more details. + * + * Returns: a newly allocated #QTree + */ +QTree * +q_tree_new_with_data(GCompareDataFunc key_compare_func, + gpointer key_compare_data) +{ + g_return_val_if_fail(key_compare_func != NULL, NULL); + + return q_tree_new_full(key_compare_func, key_compare_data, + NULL, NULL); +} + +/** + * q_tree_new_full: + * @key_compare_func: qsort()-style comparison function + * @key_compare_data: data to pass to comparison function + * @key_destroy_func: a function to free the memory allocated for the key + * used when removing the entry from the #QTree or %NULL if you don't + * want to supply such a function + * @value_destroy_func: a function to free the memory allocated for the + * value used when removing the entry from the #QTree or %NULL if you + * don't want to supply such a function + * + * Creates a new #QTree like q_tree_new() and allows to specify functions + * to free the memory allocated for the key and value that get called when + * removing the entry from the #QTree. + * + * Returns: a newly allocated #QTree + */ +QTree * +q_tree_new_full(GCompareDataFunc key_compare_func, + gpointer key_compare_data, + GDestroyNotify key_destroy_func, + GDestroyNotify value_destroy_func) +{ + QTree *tree; + + g_return_val_if_fail(key_compare_func != NULL, NULL); + + tree = g_new(QTree, 1); + tree->root = NULL; + tree->key_compare = key_compare_func; + tree->key_destroy_func = key_destroy_func; + tree->value_destroy_func = value_destroy_func; + tree->key_compare_data = key_compare_data; + tree->nnodes = 0; + tree->ref_count = 1; + + return tree; +} + +/** + * q_tree_node_first: + * @tree: a #QTree + * + * Returns the first in-order node of the tree, or %NULL + * for an empty tree. + * + * Returns: (nullable) (transfer none): the first node in the tree + * + * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. + */ +static QTreeNode * +q_tree_node_first(QTree *tree) +{ + QTreeNode *tmp; + + g_return_val_if_fail(tree != NULL, NULL); + + if (!tree->root) { + return NULL; + } + + tmp = tree->root; + + while (tmp->left_child) { + tmp = tmp->left; + } + + return tmp; +} + +/** + * q_tree_node_previous + * @node: a #QTree node + * + * Returns the previous in-order node of the tree, or %NULL + * if the passed node was already the first one. + * + * Returns: (nullable) (transfer none): the previous node in the tree + * + * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. + */ +static QTreeNode * +q_tree_node_previous(QTreeNode *node) +{ + QTreeNode *tmp; + + g_return_val_if_fail(node != NULL, NULL); + + tmp = node->left; + + if (node->left_child) { + while (tmp->right_child) { + tmp = tmp->right; + } + } + + return tmp; +} + +/** + * q_tree_node_next + * @node: a #QTree node + * + * Returns the next in-order node of the tree, or %NULL + * if the passed node was already the last one. + * + * Returns: (nullable) (transfer none): the next node in the tree + * + * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. + */ +static QTreeNode * +q_tree_node_next(QTreeNode *node) +{ + QTreeNode *tmp; + + g_return_val_if_fail(node != NULL, NULL); + + tmp = node->right; + + if (node->right_child) { + while (tmp->left_child) { + tmp = tmp->left; + } + } + + return tmp; +} + +/** + * q_tree_remove_all: + * @tree: a #QTree + * + * Removes all nodes from a #QTree and destroys their keys and values, + * then resets the #QTree’s root to %NULL. + * + * Since: 2.70 in GLib. Internal in Qtree, i.e. not in the public API. + */ +static void +q_tree_remove_all(QTree *tree) +{ + QTreeNode *node; + QTreeNode *next; + + g_return_if_fail(tree != NULL); + + node = q_tree_node_first(tree); + + while (node) { + next = q_tree_node_next(node); + + if (tree->key_destroy_func) { + tree->key_destroy_func(node->key); + } + if (tree->value_destroy_func) { + tree->value_destroy_func(node->value); + } + g_free(node); + +#ifdef Q_TREE_DEBUG + g_assert(tree->nnodes > 0); + tree->nnodes--; +#endif + + node = next; + } + +#ifdef Q_TREE_DEBUG + g_assert(tree->nnodes == 0); +#endif + + tree->root = NULL; +#ifndef Q_TREE_DEBUG + tree->nnodes = 0; +#endif +} + +/** + * q_tree_ref: + * @tree: a #QTree + * + * Increments the reference count of @tree by one. + * + * It is safe to call this function from any thread. + * + * Returns: the passed in #QTree + * + * Since: 2.22 + */ +QTree * +q_tree_ref(QTree *tree) +{ + g_return_val_if_fail(tree != NULL, NULL); + + g_atomic_int_inc(&tree->ref_count); + + return tree; +} + +/** + * q_tree_unref: + * @tree: a #QTree + * + * Decrements the reference count of @tree by one. + * If the reference count drops to 0, all keys and values will + * be destroyed (if destroy functions were specified) and all + * memory allocated by @tree will be released. + * + * It is safe to call this function from any thread. + * + * Since: 2.22 + */ +void +q_tree_unref(QTree *tree) +{ + g_return_if_fail(tree != NULL); + + if (g_atomic_int_dec_and_test(&tree->ref_count)) { + q_tree_remove_all(tree); + g_free(tree); + } +} + +/** + * q_tree_destroy: + * @tree: a #QTree + * + * Removes all keys and values from the #QTree and decreases its + * reference count by one. If keys and/or values are dynamically + * allocated, you should either free them first or create the #QTree + * using q_tree_new_full(). In the latter case the destroy functions + * you supplied will be called on all keys and values before destroying + * the #QTree. + */ +void +q_tree_destroy(QTree *tree) +{ + g_return_if_fail(tree != NULL); + + q_tree_remove_all(tree); + q_tree_unref(tree); +} + +/** + * q_tree_insert_node: + * @tree: a #QTree + * @key: the key to insert + * @value: the value corresponding to the key + * + * Inserts a key/value pair into a #QTree. + * + * If the given key already exists in the #QTree its corresponding value + * is set to the new value. If you supplied a @value_destroy_func when + * creating the #QTree, the old value is freed using that function. If + * you supplied a @key_destroy_func when creating the #QTree, the passed + * key is freed using that function. + * + * The tree is automatically 'balanced' as new key/value pairs are added, + * so that the distance from the root to every leaf is as small as possible. + * The cost of maintaining a balanced tree while inserting new key/value + * result in a O(n log(n)) operation where most of the other operations + * are O(log(n)). + * + * Returns: (transfer none): the inserted (or set) node. + * + * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. + */ +static QTreeNode * +q_tree_insert_node(QTree *tree, + gpointer key, + gpointer value) +{ + QTreeNode *node; + + g_return_val_if_fail(tree != NULL, NULL); + + node = q_tree_insert_internal(tree, key, value, FALSE); + +#ifdef Q_TREE_DEBUG + q_tree_node_check(tree->root); +#endif + + return node; +} + +/** + * q_tree_insert: + * @tree: a #QTree + * @key: the key to insert + * @value: the value corresponding to the key + * + * Inserts a key/value pair into a #QTree. + * + * Inserts a new key and value into a #QTree as q_tree_insert_node() does, + * only this function does not return the inserted or set node. + */ +void +q_tree_insert(QTree *tree, + gpointer key, + gpointer value) +{ + q_tree_insert_node(tree, key, value); +} + +/** + * q_tree_replace_node: + * @tree: a #QTree + * @key: the key to insert + * @value: the value corresponding to the key + * + * Inserts a new key and value into a #QTree similar to q_tree_insert_node(). + * The difference is that if the key already exists in the #QTree, it gets + * replaced by the new key. If you supplied a @value_destroy_func when + * creating the #QTree, the old value is freed using that function. If you + * supplied a @key_destroy_func when creating the #QTree, the old key is + * freed using that function. + * + * The tree is automatically 'balanced' as new key/value pairs are added, + * so that the distance from the root to every leaf is as small as possible. + * + * Returns: (transfer none): the inserted (or set) node. + * + * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. + */ +static QTreeNode * +q_tree_replace_node(QTree *tree, + gpointer key, + gpointer value) +{ + QTreeNode *node; + + g_return_val_if_fail(tree != NULL, NULL); + + node = q_tree_insert_internal(tree, key, value, TRUE); + +#ifdef Q_TREE_DEBUG + q_tree_node_check(tree->root); +#endif + + return node; +} + +/** + * q_tree_replace: + * @tree: a #QTree + * @key: the key to insert + * @value: the value corresponding to the key + * + * Inserts a new key and value into a #QTree as q_tree_replace_node() does, + * only this function does not return the inserted or set node. + */ +void +q_tree_replace(QTree *tree, + gpointer key, + gpointer value) +{ + q_tree_replace_node(tree, key, value); +} + +/* internal insert routine */ +static QTreeNode * +q_tree_insert_internal(QTree *tree, + gpointer key, + gpointer value, + gboolean replace) +{ + QTreeNode *node, *retnode; + QTreeNode *path[MAX_GTREE_HEIGHT]; + int idx; + + g_return_val_if_fail(tree != NULL, NULL); + + if (!tree->root) { + tree->root = q_tree_node_new(key, value); + tree->nnodes++; + return tree->root; + } + + idx = 0; + path[idx++] = NULL; + node = tree->root; + + while (1) { + int cmp = tree->key_compare(key, node->key, tree->key_compare_data); + + if (cmp == 0) { + if (tree->value_destroy_func) { + tree->value_destroy_func(node->value); + } + + node->value = value; + + if (replace) { + if (tree->key_destroy_func) { + tree->key_destroy_func(node->key); + } + + node->key = key; + } else { + /* free the passed key */ + if (tree->key_destroy_func) { + tree->key_destroy_func(key); + } + } + + return node; + } else if (cmp < 0) { + if (node->left_child) { + path[idx++] = node; + node = node->left; + } else { + QTreeNode *child = q_tree_node_new(key, value); + + child->left = node->left; + child->right = node; + node->left = child; + node->left_child = TRUE; + node->balance -= 1; + + tree->nnodes++; + + retnode = child; + break; + } + } else { + if (node->right_child) { + path[idx++] = node; + node = node->right; + } else { + QTreeNode *child = q_tree_node_new(key, value); + + child->right = node->right; + child->left = node; + node->right = child; + node->right_child = TRUE; + node->balance += 1; + + tree->nnodes++; + + retnode = child; + break; + } + } + } + + /* + * Restore balance. This is the goodness of a non-recursive + * implementation, when we are done with balancing we 'break' + * the loop and we are done. + */ + while (1) { + QTreeNode *bparent = path[--idx]; + gboolean left_node = (bparent && node == bparent->left); + g_assert(!bparent || bparent->left == node || bparent->right == node); + + if (node->balance < -1 || node->balance > 1) { + node = q_tree_node_balance(node); + if (bparent == NULL) { + tree->root = node; + } else if (left_node) { + bparent->left = node; + } else { + bparent->right = node; + } + } + + if (node->balance == 0 || bparent == NULL) { + break; + } + + if (left_node) { + bparent->balance -= 1; + } else { + bparent->balance += 1; + } + + node = bparent; + } + + return retnode; +} + +/** + * q_tree_remove: + * @tree: a #QTree + * @key: the key to remove + * + * Removes a key/value pair from a #QTree. + * + * If the #QTree was created using q_tree_new_full(), the key and value + * are freed using the supplied destroy functions, otherwise you have to + * make sure that any dynamically allocated values are freed yourself. + * If the key does not exist in the #QTree, the function does nothing. + * + * The cost of maintaining a balanced tree while removing a key/value + * result in a O(n log(n)) operation where most of the other operations + * are O(log(n)). + * + * Returns: %TRUE if the key was found (prior to 2.8, this function + * returned nothing) + */ +gboolean +q_tree_remove(QTree *tree, + gconstpointer key) +{ + gboolean removed; + + g_return_val_if_fail(tree != NULL, FALSE); + + removed = q_tree_remove_internal(tree, key, FALSE); + +#ifdef Q_TREE_DEBUG + q_tree_node_check(tree->root); +#endif + + return removed; +} + +/** + * q_tree_steal: + * @tree: a #QTree + * @key: the key to remove + * + * Removes a key and its associated value from a #QTree without calling + * the key and value destroy functions. + * + * If the key does not exist in the #QTree, the function does nothing. + * + * Returns: %TRUE if the key was found (prior to 2.8, this function + * returned nothing) + */ +gboolean +q_tree_steal(QTree *tree, + gconstpointer key) +{ + gboolean removed; + + g_return_val_if_fail(tree != NULL, FALSE); + + removed = q_tree_remove_internal(tree, key, TRUE); + +#ifdef Q_TREE_DEBUG + q_tree_node_check(tree->root); +#endif + + return removed; +} + +/* internal remove routine */ +static gboolean +q_tree_remove_internal(QTree *tree, + gconstpointer key, + gboolean steal) +{ + QTreeNode *node, *parent, *balance; + QTreeNode *path[MAX_GTREE_HEIGHT]; + int idx; + gboolean left_node; + + g_return_val_if_fail(tree != NULL, FALSE); + + if (!tree->root) { + return FALSE; + } + + idx = 0; + path[idx++] = NULL; + node = tree->root; + + while (1) { + int cmp = tree->key_compare(key, node->key, tree->key_compare_data); + + if (cmp == 0) { + break; + } else if (cmp < 0) { + if (!node->left_child) { + return FALSE; + } + + path[idx++] = node; + node = node->left; + } else { + if (!node->right_child) { + return FALSE; + } + + path[idx++] = node; + node = node->right; + } + } + + /* + * The following code is almost equal to q_tree_remove_node, + * except that we do not have to call q_tree_node_parent. + */ + balance = parent = path[--idx]; + g_assert(!parent || parent->left == node || parent->right == node); + left_node = (parent && node == parent->left); + + if (!node->left_child) { + if (!node->right_child) { + if (!parent) { + tree->root = NULL; + } else if (left_node) { + parent->left_child = FALSE; + parent->left = node->left; + parent->balance += 1; + } else { + parent->right_child = FALSE; + parent->right = node->right; + parent->balance -= 1; + } + } else { + /* node has a right child */ + QTreeNode *tmp = q_tree_node_next(node); + tmp->left = node->left; + + if (!parent) { + tree->root = node->right; + } else if (left_node) { + parent->left = node->right; + parent->balance += 1; + } else { + parent->right = node->right; + parent->balance -= 1; + } + } + } else { + /* node has a left child */ + if (!node->right_child) { + QTreeNode *tmp = q_tree_node_previous(node); + tmp->right = node->right; + + if (parent == NULL) { + tree->root = node->left; + } else if (left_node) { + parent->left = node->left; + parent->balance += 1; + } else { + parent->right = node->left; + parent->balance -= 1; + } + } else { + /* node has a both children (pant, pant!) */ + QTreeNode *prev = node->left; + QTreeNode *next = node->right; + QTreeNode *nextp = node; + int old_idx = idx + 1; + idx++; + + /* path[idx] == parent */ + /* find the immediately next node (and its parent) */ + while (next->left_child) { + path[++idx] = nextp = next; + next = next->left; + } + + path[old_idx] = next; + balance = path[idx]; + + /* remove 'next' from the tree */ + if (nextp != node) { + if (next->right_child) { + nextp->left = next->right; + } else { + nextp->left_child = FALSE; + } + nextp->balance += 1; + + next->right_child = TRUE; + next->right = node->right; + } else { + node->balance -= 1; + } + + /* set the prev to point to the right place */ + while (prev->right_child) { + prev = prev->right; + } + prev->right = next; + + /* prepare 'next' to replace 'node' */ + next->left_child = TRUE; + next->left = node->left; + next->balance = node->balance; + + if (!parent) { + tree->root = next; + } else if (left_node) { + parent->left = next; + } else { + parent->right = next; + } + } + } + + /* restore balance */ + if (balance) { + while (1) { + QTreeNode *bparent = path[--idx]; + g_assert(!bparent || + bparent->left == balance || + bparent->right == balance); + left_node = (bparent && balance == bparent->left); + + if (balance->balance < -1 || balance->balance > 1) { + balance = q_tree_node_balance(balance); + if (!bparent) { + tree->root = balance; + } else if (left_node) { + bparent->left = balance; + } else { + bparent->right = balance; + } + } + + if (balance->balance != 0 || !bparent) { + break; + } + + if (left_node) { + bparent->balance += 1; + } else { + bparent->balance -= 1; + } + + balance = bparent; + } + } + + if (!steal) { + if (tree->key_destroy_func) { + tree->key_destroy_func(node->key); + } + if (tree->value_destroy_func) { + tree->value_destroy_func(node->value); + } + } + + g_free(node); + + tree->nnodes--; + + return TRUE; +} + +/** + * q_tree_lookup_node: + * @tree: a #QTree + * @key: the key to look up + * + * Gets the tree node corresponding to the given key. Since a #QTree is + * automatically balanced as key/value pairs are added, key lookup + * is O(log n) (where n is the number of key/value pairs in the tree). + * + * Returns: (nullable) (transfer none): the tree node corresponding to + * the key, or %NULL if the key was not found + * + * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. + */ +static QTreeNode * +q_tree_lookup_node(QTree *tree, + gconstpointer key) +{ + g_return_val_if_fail(tree != NULL, NULL); + + return q_tree_find_node(tree, key); +} + +/** + * q_tree_lookup: + * @tree: a #QTree + * @key: the key to look up + * + * Gets the value corresponding to the given key. Since a #QTree is + * automatically balanced as key/value pairs are added, key lookup + * is O(log n) (where n is the number of key/value pairs in the tree). + * + * Returns: the value corresponding to the key, or %NULL + * if the key was not found + */ +gpointer +q_tree_lookup(QTree *tree, + gconstpointer key) +{ + QTreeNode *node; + + node = q_tree_lookup_node(tree, key); + + return node ? node->value : NULL; +} + +/** + * q_tree_lookup_extended: + * @tree: a #QTree + * @lookup_key: the key to look up + * @orig_key: (out) (optional) (nullable): returns the original key + * @value: (out) (optional) (nullable): returns the value associated with + * the key + * + * Looks up a key in the #QTree, returning the original key and the + * associated value. This is useful if you need to free the memory + * allocated for the original key, for example before calling + * q_tree_remove(). + * + * Returns: %TRUE if the key was found in the #QTree + */ +gboolean +q_tree_lookup_extended(QTree *tree, + gconstpointer lookup_key, + gpointer *orig_key, + gpointer *value) +{ + QTreeNode *node; + + g_return_val_if_fail(tree != NULL, FALSE); + + node = q_tree_find_node(tree, lookup_key); + + if (node) { + if (orig_key) { + *orig_key = node->key; + } + if (value) { + *value = node->value; + } + return TRUE; + } else { + return FALSE; + } +} + +/** + * q_tree_foreach: + * @tree: a #QTree + * @func: the function to call for each node visited. + * If this function returns %TRUE, the traversal is stopped. + * @user_data: user data to pass to the function + * + * Calls the given function for each of the key/value pairs in the #QTree. + * The function is passed the key and value of each pair, and the given + * @data parameter. The tree is traversed in sorted order. + * + * The tree may not be modified while iterating over it (you can't + * add/remove items). To remove all items matching a predicate, you need + * to add each item to a list in your #GTraverseFunc as you walk over + * the tree, then walk the list and remove each item. + */ +void +q_tree_foreach(QTree *tree, + GTraverseFunc func, + gpointer user_data) +{ + QTreeNode *node; + + g_return_if_fail(tree != NULL); + + if (!tree->root) { + return; + } + + node = q_tree_node_first(tree); + + while (node) { + if ((*func)(node->key, node->value, user_data)) { + break; + } + + node = q_tree_node_next(node); + } +} + +/** + * q_tree_search_node: + * @tree: a #QTree + * @search_func: a function used to search the #QTree + * @user_data: the data passed as the second argument to @search_func + * + * Searches a #QTree using @search_func. + * + * The @search_func is called with a pointer to the key of a key/value + * pair in the tree, and the passed in @user_data. If @search_func returns + * 0 for a key/value pair, then the corresponding node is returned as + * the result of q_tree_search(). If @search_func returns -1, searching + * will proceed among the key/value pairs that have a smaller key; if + * @search_func returns 1, searching will proceed among the key/value + * pairs that have a larger key. + * + * Returns: (nullable) (transfer none): the node corresponding to the + * found key, or %NULL if the key was not found + * + * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. + */ +static QTreeNode * +q_tree_search_node(QTree *tree, + GCompareFunc search_func, + gconstpointer user_data) +{ + g_return_val_if_fail(tree != NULL, NULL); + + if (!tree->root) { + return NULL; + } + + return q_tree_node_search(tree->root, search_func, user_data); +} + +/** + * q_tree_search: + * @tree: a #QTree + * @search_func: a function used to search the #QTree + * @user_data: the data passed as the second argument to @search_func + * + * Searches a #QTree using @search_func. + * + * The @search_func is called with a pointer to the key of a key/value + * pair in the tree, and the passed in @user_data. If @search_func returns + * 0 for a key/value pair, then the corresponding value is returned as + * the result of q_tree_search(). If @search_func returns -1, searching + * will proceed among the key/value pairs that have a smaller key; if + * @search_func returns 1, searching will proceed among the key/value + * pairs that have a larger key. + * + * Returns: the value corresponding to the found key, or %NULL + * if the key was not found + */ +gpointer +q_tree_search(QTree *tree, + GCompareFunc search_func, + gconstpointer user_data) +{ + QTreeNode *node; + + node = q_tree_search_node(tree, search_func, user_data); + + return node ? node->value : NULL; +} + +/** + * q_tree_height: + * @tree: a #QTree + * + * Gets the height of a #QTree. + * + * If the #QTree contains no nodes, the height is 0. + * If the #QTree contains only one root node the height is 1. + * If the root node has children the height is 2, etc. + * + * Returns: the height of @tree + */ +gint +q_tree_height(QTree *tree) +{ + QTreeNode *node; + gint height; + + g_return_val_if_fail(tree != NULL, 0); + + if (!tree->root) { + return 0; + } + + height = 0; + node = tree->root; + + while (1) { + height += 1 + MAX(node->balance, 0); + + if (!node->left_child) { + return height; + } + + node = node->left; + } +} + +/** + * q_tree_nnodes: + * @tree: a #QTree + * + * Gets the number of nodes in a #QTree. + * + * Returns: the number of nodes in @tree + */ +gint +q_tree_nnodes(QTree *tree) +{ + g_return_val_if_fail(tree != NULL, 0); + + return tree->nnodes; +} + +static QTreeNode * +q_tree_node_balance(QTreeNode *node) +{ + if (node->balance < -1) { + if (node->left->balance > 0) { + node->left = q_tree_node_rotate_left(node->left); + } + node = q_tree_node_rotate_right(node); + } else if (node->balance > 1) { + if (node->right->balance < 0) { + node->right = q_tree_node_rotate_right(node->right); + } + node = q_tree_node_rotate_left(node); + } + + return node; +} + +static QTreeNode * +q_tree_find_node(QTree *tree, + gconstpointer key) +{ + QTreeNode *node; + gint cmp; + + node = tree->root; + if (!node) { + return NULL; + } + + while (1) { + cmp = tree->key_compare(key, node->key, tree->key_compare_data); + if (cmp == 0) { + return node; + } else if (cmp < 0) { + if (!node->left_child) { + return NULL; + } + + node = node->left; + } else { + if (!node->right_child) { + return NULL; + } + + node = node->right; + } + } +} + +static QTreeNode * +q_tree_node_search(QTreeNode *node, + GCompareFunc search_func, + gconstpointer data) +{ + gint dir; + + if (!node) { + return NULL; + } + + while (1) { + dir = (*search_func)(node->key, data); + if (dir == 0) { + return node; + } else if (dir < 0) { + if (!node->left_child) { + return NULL; + } + + node = node->left; + } else { + if (!node->right_child) { + return NULL; + } + + node = node->right; + } + } +} + +static QTreeNode * +q_tree_node_rotate_left(QTreeNode *node) +{ + QTreeNode *right; + gint a_bal; + gint b_bal; + + right = node->right; + + if (right->left_child) { + node->right = right->left; + } else { + node->right_child = FALSE; + right->left_child = TRUE; + } + right->left = node; + + a_bal = node->balance; + b_bal = right->balance; + + if (b_bal <= 0) { + if (a_bal >= 1) { + right->balance = b_bal - 1; + } else { + right->balance = a_bal + b_bal - 2; + } + node->balance = a_bal - 1; + } else { + if (a_bal <= b_bal) { + right->balance = a_bal - 2; + } else { + right->balance = b_bal - 1; + } + node->balance = a_bal - b_bal - 1; + } + + return right; +} + +static QTreeNode * +q_tree_node_rotate_right(QTreeNode *node) +{ + QTreeNode *left; + gint a_bal; + gint b_bal; + + left = node->left; + + if (left->right_child) { + node->left = left->right; + } else { + node->left_child = FALSE; + left->right_child = TRUE; + } + left->right = node; + + a_bal = node->balance; + b_bal = left->balance; + + if (b_bal <= 0) { + if (b_bal > a_bal) { + left->balance = b_bal + 1; + } else { + left->balance = a_bal + 2; + } + node->balance = a_bal - b_bal + 1; + } else { + if (a_bal <= -1) { + left->balance = b_bal + 1; + } else { + left->balance = a_bal + b_bal + 2; + } + node->balance = a_bal + 1; + } + + return left; +} + +#ifdef Q_TREE_DEBUG +static gint +q_tree_node_height(QTreeNode *node) +{ + gint left_height; + gint right_height; + + if (node) { + left_height = 0; + right_height = 0; + + if (node->left_child) { + left_height = q_tree_node_height(node->left); + } + + if (node->right_child) { + right_height = q_tree_node_height(node->right); + } + + return MAX(left_height, right_height) + 1; + } + + return 0; +} + +static void q_tree_node_check(QTreeNode *node) +{ + gint left_height; + gint right_height; + gint balance; + QTreeNode *tmp; + + if (node) { + if (node->left_child) { + tmp = q_tree_node_previous(node); + g_assert(tmp->right == node); + } + + if (node->right_child) { + tmp = q_tree_node_next(node); + g_assert(tmp->left == node); + } + + left_height = 0; + right_height = 0; + + if (node->left_child) { + left_height = q_tree_node_height(node->left); + } + if (node->right_child) { + right_height = q_tree_node_height(node->right); + } + + balance = right_height - left_height; + g_assert(balance == node->balance); + + if (node->left_child) { + q_tree_node_check(node->left); + } + if (node->right_child) { + q_tree_node_check(node->right); + } + } +} +#endif diff --git a/tests/bench/meson.build b/tests/bench/meson.build index 7477a1f401..4e6b469066 100644 --- a/tests/bench/meson.build +++ b/tests/bench/meson.build @@ -9,6 +9,10 @@ xbzrle_bench = executable('xbzrle-bench', dependencies: [qemuutil,migration]) endif +qtree_bench = executable('qtree-bench', + sources: 'qtree-bench.c', + dependencies: [qemuutil]) + executable('atomic_add-bench', sources: files('atomic_add-bench.c'), dependencies: [qemuutil], diff --git a/tests/unit/meson.build b/tests/unit/meson.build index fa63cfe6ff..3bc78d8660 100644 --- a/tests/unit/meson.build +++ b/tests/unit/meson.build @@ -36,6 +36,7 @@ tests = { 'test-rcu-slist': [], 'test-qdist': [], 'test-qht': [], + 'test-qtree': [], 'test-bitops': [], 'test-bitcnt': [], 'test-qgraph': ['../qtest/libqos/qgraph.c'], diff --git a/util/meson.build b/util/meson.build index 26c73e586b..3c2cfc6ede 100644 --- a/util/meson.build +++ b/util/meson.build @@ -26,6 +26,7 @@ util_ss.add(when: 'CONFIG_WIN32', if_true: files('oslib-win32.c')) util_ss.add(when: 'CONFIG_WIN32', if_true: files('qemu-thread-win32.c')) util_ss.add(when: 'CONFIG_WIN32', if_true: winmm) util_ss.add(when: 'CONFIG_WIN32', if_true: pathcch) +util_ss.add(when: 'HAVE_GLIB_WITH_SLICE_ALLOCATOR', if_true: files('qtree.c')) util_ss.add(files('envlist.c', 'path.c', 'module.c')) util_ss.add(files('host-utils.c')) util_ss.add(files('bitmap.c', 'bitops.c')) From patchwork Wed Mar 22 15:07:35 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 665899 Delivered-To: patch@linaro.org Received: by 2002:a5d:4d08:0:0:0:0:0 with SMTP id z8csp203273wrt; Wed, 22 Mar 2023 08:08:30 -0700 (PDT) X-Google-Smtp-Source: AK7set/45qJEDfOY+iysddq7oT1SMuDeS6i35TmgWB1OdikRJkORXEYoqig8eMjvlJX4EmJ6vhPK X-Received: by 2002:a05:6214:508f:b0:5b4:1d9a:75e7 with SMTP id kk15-20020a056214508f00b005b41d9a75e7mr6476382qvb.13.1679497709982; Wed, 22 Mar 2023 08:08:29 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1679497709; cv=none; d=google.com; s=arc-20160816; b=VqdvmGrhfCtvIrhEWdwYvRbsp/k5iyHu2rwNXZmQnudeHpH29UsQBrMVJ84xuGtYnj tvpx1sATtQd9uYM9HYa5X6i6EOICvFFXfogPdUAJDGtrjmrXs/cnUqO5Jyt8ODRaTgyi H9LLE7CekxPvc52Nwp0HRML+qA642ixe10vmRQ1VNk+nXCIn3fqe4SMvKjpHPaNyPnu4 CxS9Mf5xrYmygia/g6kdr0jEGRNqmTnn7Hutb6GYBTSqnY8VjTlKrWu8skSUJhz6zHfG v0pKspOk/I/mwIeR2TcsLtfFzmHNRXo4Mi8h60RaCbATYrfNHzAwfI/z7zW8kPp3KBIO aDrg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=NMY/vAWySJgtF4AXv2RQlxqwdk/wExvFK2+RnIza0g8=; b=NvxNBJXgDnUoVmzVCMC0IXd0Wt6YR4rLt1j0g1E1cCLDek9vXNtfwSU9cmuFugj+HC M0f7p3vRs0AvI1CpOHu8k+8TWlmzrqizrct33aoM7SUBsuexW3rPEcj47YcZjdxXcfps EJeyfM/DZAGZzAPm0NL8hzgNiT6m1LlZ4wq9mxwXi7h/OupsNiRZycLs11S25YBZDQNJ zOwKZR86PoMbSsTkLBudk0Al5cf5XGcMzQIENcXXme0jN150IL7bD/a6Lq010uj/RZt5 Zr1qzyn6NvdYK/f1gmrAegTLjtvRt4YjA7EIQQTHuB0G5U0nAplX2Qjheq+GKKXk+Hk5 HgZg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=lnhhn9gp; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [209.51.188.17]) by mx.google.com with ESMTPS id i17-20020a0cf951000000b005abf1b68250si9848084qvo.547.2023.03.22.08.08.29 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 22 Mar 2023 08:08:29 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=lnhhn9gp; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pf049-0002hL-FP; Wed, 22 Mar 2023 11:07:53 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pf048-0002gP-0d for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:07:52 -0400 Received: from mail-pl1-x634.google.com ([2607:f8b0:4864:20::634]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pf046-0007Fk-0A for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:07:51 -0400 Received: by mail-pl1-x634.google.com with SMTP id w4so11476142plg.9 for ; Wed, 22 Mar 2023 08:07:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1679497669; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=NMY/vAWySJgtF4AXv2RQlxqwdk/wExvFK2+RnIza0g8=; b=lnhhn9gp2CzztoUq0/u5Gsck2jBo+71aCIXsHlR8OzvmCY4SjYHlHfCZwdXt254fBD ej2tclNAbLyoVmhoZbseQ0p+0/mGFgI3VzigzDtQ8q9C0opl12mGnEiaV3TpxsNYFs25 5HkpOYVjUGrcmrSJ0OPkb290ttwo1QaWL/XlbfyctbaVhOsvLVhMQBbUFUEtmibFxooJ 9rFyWDTmrajWP/LHP4uPdT+OM1j2tnsy9Un8Zh9hrffAFGj+crTQLI4D7q6UvXnkLt4s xy3ktFj5XoK35CjiXXUBrhJyZWq00qCQAnRIiRjsDUe/X6jbuZAwmo4JWswujH4REq/c xgvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679497669; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=NMY/vAWySJgtF4AXv2RQlxqwdk/wExvFK2+RnIza0g8=; b=wbgyYpyWVFt/jvdGH22YfrFYuXc9+wHvkCi/HJ4gmzu9FVNgioeAy+yk1dChkJRWkK Ynp2k2hXPOI7rnd5X6XyHgsmZighqo6sqQi5uPG2a4eFsMxoMfZdcthBzHBARcz4I1h+ S+2Wtypsp1uZYcQudZESaE56Z5ZzPdE3XMZHemHzJv5RNsnPN4HjS/gHMSOyxrkXpYRx +qoNR/FPLtKaiRNkcP/ERJwI9bZog90x3hXC1IhZUENpH0Ipw3f8sM/kN+XBTUKc7tvE it5obYkDEeGc6/RWgIF5y3DrHAczg6YRe/7N96Zd826e7wNK9TTMiF6gjxxiRz/+B/pQ nFiA== X-Gm-Message-State: AO0yUKV04rrzAnc0OC77ZQsCVCrm+BZGd4fxMa1MMRBqItrTBnEYLbtp j8lUxhYS0XRUKIO2nRsil3frBwkKCdBVgWqFoz0= X-Received: by 2002:a17:90b:3149:b0:23f:7dfb:7dc1 with SMTP id ip9-20020a17090b314900b0023f7dfb7dc1mr4139973pjb.33.1679497668696; Wed, 22 Mar 2023 08:07:48 -0700 (PDT) Received: from stoup.. (24-113-166-229.wavecable.com. [24.113.166.229]) by smtp.gmail.com with ESMTPSA id 17-20020a170902ee5100b0019339f3368asm10757555plo.3.2023.03.22.08.07.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Mar 2023 08:07:48 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: cota@braap.org, peter.maydell@linaro.org, Valentin David , =?utf-8?q?Philippe_Mathieu-Daud?= =?utf-8?q?=C3=A9?= Subject: [PATCH for-8.0 02/11] tcg: use QTree instead of GTree Date: Wed, 22 Mar 2023 08:07:35 -0700 Message-Id: <20230322150744.175010-3-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230322150744.175010-1-richard.henderson@linaro.org> References: <20230322150744.175010-1-richard.henderson@linaro.org> MIME-Version: 1.0 Received-SPF: pass client-ip=2607:f8b0:4864:20::634; envelope-from=richard.henderson@linaro.org; helo=mail-pl1-x634.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: qemu-devel-bounces+patch=linaro.org@nongnu.org From: Emilio Cota qemu-user can hang in a multi-threaded fork. One common reason is that when creating a TB, between fork and exec we manipulate a GTree whose memory allocator (GSlice) is not fork-safe. Although POSIX does not mandate it, the system's allocator (e.g. tcmalloc, libc malloc) is probably fork-safe. Fix some of these hangs by using QTree, which uses the system's allocator regardless of the Glib version that we used at configuration time. Tested with the test program in the original bug report, i.e.: ``` void garble() { int pid = fork(); if (pid == 0) { exit(0); } else { int wstatus; waitpid(pid, &wstatus, 0); } } void supragarble(unsigned depth) { if (depth == 0) return ; std::thread a(supragarble, depth-1); std::thread b(supragarble, depth-1); garble(); a.join(); b.join(); } int main() { supragarble(10); } ``` Resolves: https://gitlab.com/qemu-project/qemu/-/issues/285 Reported-by: Valentin David Reviewed-by: Philippe Mathieu-Daudé Signed-off-by: Emilio Cota Message-Id: <20230205163758.416992-3-cota@braap.org> [rth: Add QEMU_DISABLE_CFI for all callback using functions.] Signed-off-by: Richard Henderson --- accel/tcg/tb-maint.c | 17 +++++++++-------- tcg/region.c | 19 ++++++++++--------- util/qtree.c | 8 ++++---- 3 files changed, 23 insertions(+), 21 deletions(-) diff --git a/accel/tcg/tb-maint.c b/accel/tcg/tb-maint.c index 7246c1c46b..a173db17e6 100644 --- a/accel/tcg/tb-maint.c +++ b/accel/tcg/tb-maint.c @@ -19,6 +19,7 @@ #include "qemu/osdep.h" #include "qemu/interval-tree.h" +#include "qemu/qtree.h" #include "exec/cputlb.h" #include "exec/log.h" #include "exec/exec-all.h" @@ -314,7 +315,7 @@ struct page_entry { * See also: page_collection_lock(). */ struct page_collection { - GTree *tree; + QTree *tree; struct page_entry *max; }; @@ -467,7 +468,7 @@ static bool page_trylock_add(struct page_collection *set, tb_page_addr_t addr) struct page_entry *pe; PageDesc *pd; - pe = g_tree_lookup(set->tree, &index); + pe = q_tree_lookup(set->tree, &index); if (pe) { return false; } @@ -478,7 +479,7 @@ static bool page_trylock_add(struct page_collection *set, tb_page_addr_t addr) } pe = page_entry_new(pd, index); - g_tree_insert(set->tree, &pe->index, pe); + q_tree_insert(set->tree, &pe->index, pe); /* * If this is either (1) the first insertion or (2) a page whose index @@ -525,13 +526,13 @@ static struct page_collection *page_collection_lock(tb_page_addr_t start, end >>= TARGET_PAGE_BITS; g_assert(start <= end); - set->tree = g_tree_new_full(tb_page_addr_cmp, NULL, NULL, + set->tree = q_tree_new_full(tb_page_addr_cmp, NULL, NULL, page_entry_destroy); set->max = NULL; assert_no_pages_locked(); retry: - g_tree_foreach(set->tree, page_entry_lock, NULL); + q_tree_foreach(set->tree, page_entry_lock, NULL); for (index = start; index <= end; index++) { TranslationBlock *tb; @@ -542,7 +543,7 @@ static struct page_collection *page_collection_lock(tb_page_addr_t start, continue; } if (page_trylock_add(set, index << TARGET_PAGE_BITS)) { - g_tree_foreach(set->tree, page_entry_unlock, NULL); + q_tree_foreach(set->tree, page_entry_unlock, NULL); goto retry; } assert_page_locked(pd); @@ -551,7 +552,7 @@ static struct page_collection *page_collection_lock(tb_page_addr_t start, (tb_page_addr1(tb) != -1 && page_trylock_add(set, tb_page_addr1(tb)))) { /* drop all locks, and reacquire in order */ - g_tree_foreach(set->tree, page_entry_unlock, NULL); + q_tree_foreach(set->tree, page_entry_unlock, NULL); goto retry; } } @@ -562,7 +563,7 @@ static struct page_collection *page_collection_lock(tb_page_addr_t start, static void page_collection_unlock(struct page_collection *set) { /* entries are unlocked and freed via page_entry_destroy */ - g_tree_destroy(set->tree); + q_tree_destroy(set->tree); g_free(set); } diff --git a/tcg/region.c b/tcg/region.c index 88d6bb273f..bef4c4756f 100644 --- a/tcg/region.c +++ b/tcg/region.c @@ -28,6 +28,7 @@ #include "qemu/mprotect.h" #include "qemu/memalign.h" #include "qemu/cacheinfo.h" +#include "qemu/qtree.h" #include "qapi/error.h" #include "exec/exec-all.h" #include "tcg/tcg.h" @@ -36,7 +37,7 @@ struct tcg_region_tree { QemuMutex lock; - GTree *tree; + QTree *tree; /* padding to avoid false sharing is computed at run-time */ }; @@ -163,7 +164,7 @@ static void tcg_region_trees_init(void) struct tcg_region_tree *rt = region_trees + i * tree_size; qemu_mutex_init(&rt->lock); - rt->tree = g_tree_new_full(tb_tc_cmp, NULL, NULL, tb_destroy); + rt->tree = q_tree_new_full(tb_tc_cmp, NULL, NULL, tb_destroy); } } @@ -202,7 +203,7 @@ void tcg_tb_insert(TranslationBlock *tb) g_assert(rt != NULL); qemu_mutex_lock(&rt->lock); - g_tree_insert(rt->tree, &tb->tc, tb); + q_tree_insert(rt->tree, &tb->tc, tb); qemu_mutex_unlock(&rt->lock); } @@ -212,7 +213,7 @@ void tcg_tb_remove(TranslationBlock *tb) g_assert(rt != NULL); qemu_mutex_lock(&rt->lock); - g_tree_remove(rt->tree, &tb->tc); + q_tree_remove(rt->tree, &tb->tc); qemu_mutex_unlock(&rt->lock); } @@ -232,7 +233,7 @@ TranslationBlock *tcg_tb_lookup(uintptr_t tc_ptr) } qemu_mutex_lock(&rt->lock); - tb = g_tree_lookup(rt->tree, &s); + tb = q_tree_lookup(rt->tree, &s); qemu_mutex_unlock(&rt->lock); return tb; } @@ -267,7 +268,7 @@ void tcg_tb_foreach(GTraverseFunc func, gpointer user_data) for (i = 0; i < region.n; i++) { struct tcg_region_tree *rt = region_trees + i * tree_size; - g_tree_foreach(rt->tree, func, user_data); + q_tree_foreach(rt->tree, func, user_data); } tcg_region_tree_unlock_all(); } @@ -281,7 +282,7 @@ size_t tcg_nb_tbs(void) for (i = 0; i < region.n; i++) { struct tcg_region_tree *rt = region_trees + i * tree_size; - nb_tbs += g_tree_nnodes(rt->tree); + nb_tbs += q_tree_nnodes(rt->tree); } tcg_region_tree_unlock_all(); return nb_tbs; @@ -296,8 +297,8 @@ static void tcg_region_tree_reset_all(void) struct tcg_region_tree *rt = region_trees + i * tree_size; /* Increment the refcount first so that destroy acts as a reset */ - g_tree_ref(rt->tree); - g_tree_destroy(rt->tree); + q_tree_ref(rt->tree); + q_tree_destroy(rt->tree); } tcg_region_tree_unlock_all(); } diff --git a/util/qtree.c b/util/qtree.c index deb46c187f..31f0b46182 100644 --- a/util/qtree.c +++ b/util/qtree.c @@ -310,7 +310,7 @@ q_tree_node_next(QTreeNode *node) * * Since: 2.70 in GLib. Internal in Qtree, i.e. not in the public API. */ -static void +static void QEMU_DISABLE_CFI q_tree_remove_all(QTree *tree) { QTreeNode *node; @@ -532,7 +532,7 @@ q_tree_replace(QTree *tree, } /* internal insert routine */ -static QTreeNode * +static QTreeNode * QEMU_DISABLE_CFI q_tree_insert_internal(QTree *tree, gpointer key, gpointer value, @@ -721,7 +721,7 @@ q_tree_steal(QTree *tree, } /* internal remove routine */ -static gboolean +static gboolean QEMU_DISABLE_CFI q_tree_remove_internal(QTree *tree, gconstpointer key, gboolean steal) @@ -1182,7 +1182,7 @@ q_tree_node_balance(QTreeNode *node) return node; } -static QTreeNode * +static QTreeNode * QEMU_DISABLE_CFI q_tree_find_node(QTree *tree, gconstpointer key) { From patchwork Wed Mar 22 15:07:36 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 665898 Delivered-To: patch@linaro.org Received: by 2002:a5d:4d08:0:0:0:0:0 with SMTP id z8csp203271wrt; Wed, 22 Mar 2023 08:08:30 -0700 (PDT) X-Google-Smtp-Source: AK7set+Xai5UMFOaW3LR2auOWOd0dF+/elGBaMp7+Av0RDaZzf36uKJZoY3EXTHX6byGz9Lq/yrT X-Received: by 2002:ac8:5f0e:0:b0:3bf:c83d:5d4c with SMTP id x14-20020ac85f0e000000b003bfc83d5d4cmr6499200qta.64.1679497709960; Wed, 22 Mar 2023 08:08:29 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1679497709; cv=none; d=google.com; s=arc-20160816; b=LASzlNZCzTQbz8sjDpETIDm9FvZsHGxyRz+0oDDJmUjxv+b1Re8ftHtUhxdAwv0zaE Q8NJ+sO8NEfuL8VJAq0YnMXIiuXpTmvYmTxOdGRNeOnu2Qk1MXDj1U5D14GUqlxLuJs2 jECc407TNljK11QetjIa8INJEuVD0QKs8Qe8iVsVbbJh/kASdkP+SGRohE/PymthWjtG xm8iMNmvIdR2K4s0qkYoIBkSRC63CDpuXXxRLQmogd2qhqLeMmJva9Uhow3Nvh0Q8Ldm WJbmDzXROOEL+Tbnyx3yxTyix0BvR8oQRrDfsl660KZmyuM3vPsGS6lCob7aabj16yLi uhvQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=d+avOkff6EBvJ8K9x1TsSkw5p9567zBA1o+YX6GdDwE=; b=YuHqoYAxmDSylS1+aBBb6X9F9uiQKqv/aRj3Bx8MFztcaYgxSQdv9rZ0BzYMfa0maS qfUM+N5+bLUQxJrexD6qsHKagoiI7e++6V/kIJ3sdm904dLCqCA2o1jvzwtLpfW3JpAH 77L4/FhLks0Xm7Us/+NCCQNuY6LU/1Mx0TJekdgVCJbCDffReFZakaAGeS2s3j+f3TmM 27LaKZFd5xyTEMjHzU+feDGu+eoC/LBPGRCwE9zkpUcLqhAplQlV+aciwDpY1gaQmAa8 Kt/z8zoTg7QCb3iX0xa33pSP+VgbG26XwX3h9tXKTFYr/+PZsU7sMD30+glbiDuxMVfV pidg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=RIZOgz7M; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [209.51.188.17]) by mx.google.com with ESMTPS id h1-20020a05620a244100b007461b4f4666si10527564qkn.236.2023.03.22.08.08.29 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 22 Mar 2023 08:08:29 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=RIZOgz7M; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pf04C-0002nK-9v; Wed, 22 Mar 2023 11:07:56 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pf049-0002hJ-8q for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:07:53 -0400 Received: from mail-pj1-x1029.google.com ([2607:f8b0:4864:20::1029]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pf047-0007GP-50 for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:07:52 -0400 Received: by mail-pj1-x1029.google.com with SMTP id j13so18782030pjd.1 for ; Wed, 22 Mar 2023 08:07:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1679497670; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=d+avOkff6EBvJ8K9x1TsSkw5p9567zBA1o+YX6GdDwE=; b=RIZOgz7M6JeOVcnlBJHQ2Js8KewnfOHsGUanHxxJBrTWlfKPQEOd60UxU0+L7vrogk W5A7UJybTQNmD6f+XWo0+UjZHu1cv97g1l3IbWuBLS3Wcd1vTtI8vIoQhrrNMibp8bVZ 9eVZqszFEKl2alhEPHnFZDALER/Eb22Q+v5FLKPliVArDW0yiVAcwkjiI6eKStUBfw4H 5n9w7i3AyU52HjcqV9jWNbrDaGiCGheSvPt6fNJbwIZsFkH0xF90axPbKaOT/fbM1u+/ fL2ORZMgHGIdXDCID559SPMdmPNwGkv+7MsSQD5EjGEVGlxHuD7liqPeRuZsi8IcjzVg XYUg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679497670; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=d+avOkff6EBvJ8K9x1TsSkw5p9567zBA1o+YX6GdDwE=; b=dQDiJklKi723M1dTuhAY8CiMfeKRpsMSky6Cxuo40qWwAgA7GemcN1IO43nbRT8TwQ WKp8UO63EDxLAT7LXYiwiL5NdQaDnudqACnqcbxQpm9MmMk/31Ayg2Dn+jQsG5JQHG9K V+/1boHBu95rox2vmRqE98lmkuRWDMB8DSW5OqhourspJTs4e6X0+AxvopwhuW6lvNjB MtSfQwF17jJU/AJn/bFogrfMsyKVhckcMChu3tCzHYsMWqAe6nJyrWkHcqSQMMorUlnR Wry2bKgDLaTRxiSXQOIT+kPB5Heuuh8eaGVAB/Nzgd6w+y+KzMCsLXQ5TvkjGZVZu4rU pNRA== X-Gm-Message-State: AO0yUKWp5ccJ+e2ykLLk8kC/xscK6ZnNLu6Ep10c6o94XAzol+QntWQ0 TvIqbSKzsHvbHEauDY0k7F227CjMPnJSsrEXQJI= X-Received: by 2002:a17:903:183:b0:19c:cf89:b7ee with SMTP id z3-20020a170903018300b0019ccf89b7eemr2632109plg.69.1679497669899; Wed, 22 Mar 2023 08:07:49 -0700 (PDT) Received: from stoup.. (24-113-166-229.wavecable.com. [24.113.166.229]) by smtp.gmail.com with ESMTPSA id 17-20020a170902ee5100b0019339f3368asm10757555plo.3.2023.03.22.08.07.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Mar 2023 08:07:49 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: cota@braap.org, peter.maydell@linaro.org, =?utf-8?q?Philippe_Mathieu-Dau?= =?utf-8?q?d=C3=A9?= Subject: [PATCH for-8.0 03/11] linux-user: Diagnose misaligned -R size Date: Wed, 22 Mar 2023 08:07:36 -0700 Message-Id: <20230322150744.175010-4-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230322150744.175010-1-richard.henderson@linaro.org> References: <20230322150744.175010-1-richard.henderson@linaro.org> MIME-Version: 1.0 Received-SPF: pass client-ip=2607:f8b0:4864:20::1029; envelope-from=richard.henderson@linaro.org; helo=mail-pj1-x1029.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: qemu-devel-bounces+patch=linaro.org@nongnu.org We have been enforcing host page alignment for the non-R fallback of MAX_RESERVED_VA, but failing to enforce for -R. Reviewed-by: Philippe Mathieu-Daudé Signed-off-by: Richard Henderson --- linux-user/main.c | 6 ++++++ 1 file changed, 6 insertions(+) diff --git a/linux-user/main.c b/linux-user/main.c index 4b18461969..39d9bd4d7a 100644 --- a/linux-user/main.c +++ b/linux-user/main.c @@ -793,6 +793,12 @@ int main(int argc, char **argv, char **envp) */ max_reserved_va = MAX_RESERVED_VA(cpu); if (reserved_va != 0) { + if (reserved_va % qemu_host_page_size) { + char *s = size_to_str(qemu_host_page_size); + fprintf(stderr, "Reserved virtual address not aligned mod %s\n", s); + g_free(s); + exit(EXIT_FAILURE); + } if (max_reserved_va && reserved_va > max_reserved_va) { fprintf(stderr, "Reserved virtual address too big\n"); exit(EXIT_FAILURE); From patchwork Wed Mar 22 15:07:37 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 665905 Delivered-To: patch@linaro.org Received: by 2002:a5d:4d08:0:0:0:0:0 with SMTP id z8csp203872wrt; Wed, 22 Mar 2023 08:09:27 -0700 (PDT) X-Google-Smtp-Source: AK7set8P4Y2X2xQf9n3XBxCjJm4Uas1eb9/rsatHAeaBwbwLS9IWQjIVbmElg3ZbDWC9QLD8caj+ X-Received: by 2002:a05:6214:acd:b0:5cb:e2fb:dd4d with SMTP id g13-20020a0562140acd00b005cbe2fbdd4dmr6774233qvi.32.1679497767324; Wed, 22 Mar 2023 08:09:27 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1679497767; cv=none; d=google.com; s=arc-20160816; b=d799hOngoA7ltEErorVenuZlQXF69d8JivfW/E2aW1NVtKeTX8Elrm7MQ+fbl8jr7W /3ot+D4Ydolde4E46cw0hFVmITovRe4V3FBi37b2li1CMaXBLBeqKiOTIjY2GF9FeXsS V3RFQtvCv5OfaSS9ke0jaBh5CvMMPrtOfMMFgChL5JXJ85IciT3gWlRf096DpKklEW65 d7uyMVqeI6AWFO+vixIsNyVoZsY28wLR6taFcjB5X5ZQw7PJSEwqYollLhp2tq/nQpE0 y/ODI3DvPib2ncG3UIoLNZJ3WIPGrb/fEIs6P5TK5BBAfE9fvuIyXMAEvWRoC34iaF2t l88A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=Nl+O5kCXUOJVGVi2vwdOXVZym0o1Puo9UdIbwQgjClA=; b=jdAZyrC0/HANf/cR67tnvvVI94IkOUKr8l1VAQQwH0E82Ko4S3Lao+una/FfjS2MSm ZRdDVmFkxSrBRVCUYAL1E6ZdfJDeVQcGh5dUGSPzsxoH3J7Bk/YFVH+/ckXzNtYGjhjy C5OXbtt5Z5qWhOQbE1MfcwM2mr/5yktIlZBeVZ44LVuhZIdCN1lZUTb5LjwfmPkwpswk z+8GjxQ2aHAOEAFD3CdhpQGyxpUkBgumDdBhLdLgi+MyEff9S5ARI3Aynv/xR5LCZedY tPAeCuE1WZGmFO6yGTnhEsw2RFzqnH5dr/GZ5sDn4i/bTlp5JNIFsv2K8mBER0UYWERQ hLRA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=BnK482Fm; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [209.51.188.17]) by mx.google.com with ESMTPS id dn1-20020a056214094100b0056e98779ab7si9753461qvb.380.2023.03.22.08.09.27 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 22 Mar 2023 08:09:27 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=BnK482Fm; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pf04U-00033e-7h; Wed, 22 Mar 2023 11:08:15 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pf04B-0002mE-Cr for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:07:55 -0400 Received: from mail-pl1-x631.google.com ([2607:f8b0:4864:20::631]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pf049-0007HX-3a for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:07:55 -0400 Received: by mail-pl1-x631.google.com with SMTP id o2so12144636plg.4 for ; Wed, 22 Mar 2023 08:07:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1679497672; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Nl+O5kCXUOJVGVi2vwdOXVZym0o1Puo9UdIbwQgjClA=; b=BnK482Fm0ztxv5eg2gONNRDEI/vhCWqQUUZK9M8XdeGlsUrvMPweqCJyUEhZi6wilB 4xnMGWc6VowiOfJpS11yxogXeBgGnWCVAwhOE43K/skAn9B4jqNNPsRBa2rBNzBHcYzy O/kbPQROqVN4/9ZexkenqlQCN/+wEUAbDRSAN5pwn9fX1XIBzF2kCb5cZkFKd5WHFoCQ qVccIJYuIY4ijWzMMx4dFSufPuZYsiyhkudGt8iNPFaE8zWhl09T1MSPQnNGabut+Jqt FVYzarSrJeWXinfAJBbzReK4RjKW15T3pI+6xMlbmR5Ke1kkiY/LKuI6OBn0+UyB3T+M 9t0g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679497672; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Nl+O5kCXUOJVGVi2vwdOXVZym0o1Puo9UdIbwQgjClA=; b=OHqdkEcrCOk1Hld1oRxXDL94qYPMdFtk5weiIXvPRmZOycUos0nH18jqYjOVUHpFx7 GUOUzYeHEjJ5pWdcGe2k2kStxTpmzLuwQ0AXw/mMIBmHgXFkJbbGiyPqnnHAcg7MNDMX qLSPhBNcQIqiFjzPKc1Cp8Iv+voSGdLzWExx9WxkndSvlKMhsamCIU+5a5CgDqyDvlFi WjfHQdI/v6VXKzjJiyt/42JnUH9hZaA0Mp4W9Ej9x5P5Nh3TObMywo5VArvoNfJRHeKp D8mrsGqCpsWmNUrkJvTatFlE8evQPAep9xDM/O1xF82eBemxzPQ3OLbUWVPdK/3Gg07B NfBg== X-Gm-Message-State: AO0yUKW3Vq4mlIc+qJVZ32Jcm1eX2TqWy37W6cq0jOqge8DlvsM8xYLK 5uCGrL2RlVM9ok61VNTtUrE0YKcYijp91C0apzE= X-Received: by 2002:a17:902:f211:b0:19f:1c69:54b5 with SMTP id m17-20020a170902f21100b0019f1c6954b5mr2627411plc.12.1679497671725; Wed, 22 Mar 2023 08:07:51 -0700 (PDT) Received: from stoup.. (24-113-166-229.wavecable.com. [24.113.166.229]) by smtp.gmail.com with ESMTPSA id 17-20020a170902ee5100b0019339f3368asm10757555plo.3.2023.03.22.08.07.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Mar 2023 08:07:50 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: cota@braap.org, peter.maydell@linaro.org, =?utf-8?q?Philippe_Mathieu-Dau?= =?utf-8?q?d=C3=A9?= Subject: [PATCH for-8.0 04/11] include/exec: Change reserved_va semantics to last byte Date: Wed, 22 Mar 2023 08:07:37 -0700 Message-Id: <20230322150744.175010-5-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230322150744.175010-1-richard.henderson@linaro.org> References: <20230322150744.175010-1-richard.henderson@linaro.org> MIME-Version: 1.0 Received-SPF: pass client-ip=2607:f8b0:4864:20::631; envelope-from=richard.henderson@linaro.org; helo=mail-pl1-x631.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: qemu-devel-bounces+patch=linaro.org@nongnu.org Change the semantics to be the last byte of the guest va, rather than the following byte. This avoids some overflow conditions. Reviewed-by: Philippe Mathieu-Daudé Signed-off-by: Richard Henderson --- include/exec/cpu-all.h | 11 ++++++++++- linux-user/arm/target_cpu.h | 2 +- bsd-user/main.c | 10 +++------- bsd-user/mmap.c | 4 ++-- linux-user/elfload.c | 21 +++++++++++---------- linux-user/main.c | 27 +++++++++++++-------------- linux-user/mmap.c | 4 ++-- 7 files changed, 42 insertions(+), 37 deletions(-) diff --git a/include/exec/cpu-all.h b/include/exec/cpu-all.h index 548be9c8ea..456afd0e22 100644 --- a/include/exec/cpu-all.h +++ b/include/exec/cpu-all.h @@ -152,6 +152,15 @@ static inline void tswap64s(uint64_t *s) */ extern uintptr_t guest_base; extern bool have_guest_base; + +/* + * If non-zero, the guest virtual address space is a contiguous subset + * of the host virtual address space, i.e. '-R reserved_va' is in effect + * either from the command-line or by default. The value is the last + * byte of the guest address space e.g. UINT32_MAX. + * + * If zero, the host and guest virtual address spaces are intermingled. + */ extern unsigned long reserved_va; /* @@ -171,7 +180,7 @@ extern unsigned long reserved_va; #define GUEST_ADDR_MAX_ \ ((MIN_CONST(TARGET_VIRT_ADDR_SPACE_BITS, TARGET_ABI_BITS) <= 32) ? \ UINT32_MAX : ~0ul) -#define GUEST_ADDR_MAX (reserved_va ? reserved_va - 1 : GUEST_ADDR_MAX_) +#define GUEST_ADDR_MAX (reserved_va ? : GUEST_ADDR_MAX_) #else diff --git a/linux-user/arm/target_cpu.h b/linux-user/arm/target_cpu.h index 89ba274cfc..f6383a7cd1 100644 --- a/linux-user/arm/target_cpu.h +++ b/linux-user/arm/target_cpu.h @@ -30,7 +30,7 @@ static inline unsigned long arm_max_reserved_va(CPUState *cs) * the high addresses. Restrict linux-user to the * cached write-back RAM in the system map. */ - return 0x80000000ul; + return 0x7ffffffful; } else { /* * We need to be able to map the commpage. diff --git a/bsd-user/main.c b/bsd-user/main.c index 89f225dead..babc3b009b 100644 --- a/bsd-user/main.c +++ b/bsd-user/main.c @@ -68,13 +68,9 @@ bool have_guest_base; # if HOST_LONG_BITS > TARGET_VIRT_ADDR_SPACE_BITS # if TARGET_VIRT_ADDR_SPACE_BITS == 32 && \ (TARGET_LONG_BITS == 32 || defined(TARGET_ABI32)) -/* - * There are a number of places where we assign reserved_va to a variable - * of type abi_ulong and expect it to fit. Avoid the last page. - */ -# define MAX_RESERVED_VA (0xfffffffful & TARGET_PAGE_MASK) +# define MAX_RESERVED_VA 0xfffffffful # else -# define MAX_RESERVED_VA (1ul << TARGET_VIRT_ADDR_SPACE_BITS) +# define MAX_RESERVED_VA ((1ul << TARGET_VIRT_ADDR_SPACE_BITS) - 1) # endif # else # define MAX_RESERVED_VA 0 @@ -466,7 +462,7 @@ int main(int argc, char **argv) envlist_free(envlist); if (reserved_va) { - mmap_next_start = reserved_va; + mmap_next_start = reserved_va + 1; } { diff --git a/bsd-user/mmap.c b/bsd-user/mmap.c index d6c5a344c9..d35650e562 100644 --- a/bsd-user/mmap.c +++ b/bsd-user/mmap.c @@ -234,7 +234,7 @@ static abi_ulong mmap_find_vma_reserved(abi_ulong start, abi_ulong size, size = HOST_PAGE_ALIGN(size) + alignment; end_addr = start + size; if (end_addr > reserved_va) { - end_addr = reserved_va; + end_addr = reserved_va + 1; } addr = end_addr - qemu_host_page_size; @@ -243,7 +243,7 @@ static abi_ulong mmap_find_vma_reserved(abi_ulong start, abi_ulong size, if (looped) { return (abi_ulong)-1; } - end_addr = reserved_va; + end_addr = reserved_va + 1; addr = end_addr - qemu_host_page_size; looped = 1; continue; diff --git a/linux-user/elfload.c b/linux-user/elfload.c index 150d1d4503..bb2001bf30 100644 --- a/linux-user/elfload.c +++ b/linux-user/elfload.c @@ -207,7 +207,7 @@ static bool init_guest_commpage(void) * has specified -R reserved_va, which would trigger an assert(). */ if (reserved_va != 0 && - TARGET_VSYSCALL_PAGE + TARGET_PAGE_SIZE >= reserved_va) { + TARGET_VSYSCALL_PAGE + TARGET_PAGE_SIZE - 1 > reserved_va) { error_report("Cannot allocate vsyscall page"); exit(EXIT_FAILURE); } @@ -2499,10 +2499,11 @@ static void pgb_have_guest_base(const char *image_name, abi_ulong guest_loaddr, /* Sanity check the guest binary. */ if (reserved_va) { - if (guest_hiaddr > reserved_va) { + if (guest_hiaddr - 1 > reserved_va) { error_report("%s: requires more than reserved virtual " "address space (0x%" PRIx64 " > 0x%lx)", - image_name, (uint64_t)guest_hiaddr, reserved_va); + image_name, (uint64_t)guest_hiaddr - 1, + reserved_va); exit(EXIT_FAILURE); } } else { @@ -2523,7 +2524,7 @@ static void pgb_have_guest_base(const char *image_name, abi_ulong guest_loaddr, if (reserved_va) { guest_loaddr = (guest_base >= mmap_min_addr ? 0 : mmap_min_addr - guest_base); - guest_hiaddr = reserved_va; + guest_hiaddr = reserved_va + 1; } /* Reserve the address space for the binary, or reserved_va. */ @@ -2750,15 +2751,15 @@ static void pgb_reserved_va(const char *image_name, abi_ulong guest_loaddr, int flags = MAP_ANONYMOUS | MAP_PRIVATE | MAP_NORESERVE; void *addr, *test; - if (guest_hiaddr > reserved_va) { + if (guest_hiaddr - 1 > reserved_va) { error_report("%s: requires more than reserved virtual " "address space (0x%" PRIx64 " > 0x%lx)", - image_name, (uint64_t)guest_hiaddr, reserved_va); + image_name, (uint64_t)guest_hiaddr - 1, reserved_va); exit(EXIT_FAILURE); } /* Widen the "image" to the entire reserved address space. */ - pgb_static(image_name, 0, reserved_va, align); + pgb_static(image_name, 0, reserved_va + 1, align); /* osdep.h defines this as 0 if it's missing */ flags |= MAP_FIXED_NOREPLACE; @@ -2766,17 +2767,17 @@ static void pgb_reserved_va(const char *image_name, abi_ulong guest_loaddr, /* Reserve the memory on the host. */ assert(guest_base != 0); test = g2h_untagged(0); - addr = mmap(test, reserved_va, PROT_NONE, flags, -1, 0); + addr = mmap(test, reserved_va + 1, PROT_NONE, flags, -1, 0); if (addr == MAP_FAILED || addr != test) { error_report("Unable to reserve 0x%lx bytes of virtual address " "space at %p (%s) for use as guest address space (check your " "virtual memory ulimit setting, min_mmap_addr or reserve less " - "using -R option)", reserved_va, test, strerror(errno)); + "using -R option)", reserved_va + 1, test, strerror(errno)); exit(EXIT_FAILURE); } qemu_log_mask(CPU_LOG_PAGE, "%s: base @ %p for %lu bytes\n", - __func__, addr, reserved_va); + __func__, addr, reserved_va + 1); } void probe_guest_base(const char *image_name, abi_ulong guest_loaddr, diff --git a/linux-user/main.c b/linux-user/main.c index 39d9bd4d7a..fe03293516 100644 --- a/linux-user/main.c +++ b/linux-user/main.c @@ -109,11 +109,9 @@ static const char *last_log_filename; # if HOST_LONG_BITS > TARGET_VIRT_ADDR_SPACE_BITS # if TARGET_VIRT_ADDR_SPACE_BITS == 32 && \ (TARGET_LONG_BITS == 32 || defined(TARGET_ABI32)) -/* There are a number of places where we assign reserved_va to a variable - of type abi_ulong and expect it to fit. Avoid the last page. */ -# define MAX_RESERVED_VA(CPU) (0xfffffffful & TARGET_PAGE_MASK) +# define MAX_RESERVED_VA(CPU) 0xfffffffful # else -# define MAX_RESERVED_VA(CPU) (1ul << TARGET_VIRT_ADDR_SPACE_BITS) +# define MAX_RESERVED_VA(CPU) ((1ul << TARGET_VIRT_ADDR_SPACE_BITS) - 1) # endif # else # define MAX_RESERVED_VA(CPU) 0 @@ -379,7 +377,9 @@ static void handle_arg_reserved_va(const char *arg) { char *p; int shift = 0; - reserved_va = strtoul(arg, &p, 0); + unsigned long val; + + val = strtoul(arg, &p, 0); switch (*p) { case 'k': case 'K': @@ -393,10 +393,10 @@ static void handle_arg_reserved_va(const char *arg) break; } if (shift) { - unsigned long unshifted = reserved_va; + unsigned long unshifted = val; p++; - reserved_va <<= shift; - if (reserved_va >> shift != unshifted) { + val <<= shift; + if (val >> shift != unshifted) { fprintf(stderr, "Reserved virtual address too big\n"); exit(EXIT_FAILURE); } @@ -405,6 +405,8 @@ static void handle_arg_reserved_va(const char *arg) fprintf(stderr, "Unrecognised -R size suffix '%s'\n", p); exit(EXIT_FAILURE); } + /* The representation is size - 1, with 0 remaining "default". */ + reserved_va = val ? val - 1 : 0; } static void handle_arg_singlestep(const char *arg) @@ -793,7 +795,7 @@ int main(int argc, char **argv, char **envp) */ max_reserved_va = MAX_RESERVED_VA(cpu); if (reserved_va != 0) { - if (reserved_va % qemu_host_page_size) { + if ((reserved_va + 1) % qemu_host_page_size) { char *s = size_to_str(qemu_host_page_size); fprintf(stderr, "Reserved virtual address not aligned mod %s\n", s); g_free(s); @@ -804,11 +806,8 @@ int main(int argc, char **argv, char **envp) exit(EXIT_FAILURE); } } else if (HOST_LONG_BITS == 64 && TARGET_VIRT_ADDR_SPACE_BITS <= 32) { - /* - * reserved_va must be aligned with the host page size - * as it is used with mmap() - */ - reserved_va = max_reserved_va & qemu_host_page_mask; + /* MAX_RESERVED_VA + 1 is a large power of 2, so is aligned. */ + reserved_va = max_reserved_va; } { diff --git a/linux-user/mmap.c b/linux-user/mmap.c index 28135c9e6a..cf14930c30 100644 --- a/linux-user/mmap.c +++ b/linux-user/mmap.c @@ -283,7 +283,7 @@ static abi_ulong mmap_find_vma_reserved(abi_ulong start, abi_ulong size, end_addr = start + size; if (start > reserved_va - size) { /* Start at the top of the address space. */ - end_addr = ((reserved_va - size) & -align) + size; + end_addr = ((reserved_va + 1 - size) & -align) + size; looped = true; } @@ -297,7 +297,7 @@ static abi_ulong mmap_find_vma_reserved(abi_ulong start, abi_ulong size, return (abi_ulong)-1; } /* Re-start at the top of the address space. */ - addr = end_addr = ((reserved_va - size) & -align) + size; + addr = end_addr = ((reserved_va + 1 - size) & -align) + size; looped = true; } else { prot = page_get_flags(addr); From patchwork Wed Mar 22 15:07:38 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 665900 Delivered-To: patch@linaro.org Received: by 2002:a5d:4d08:0:0:0:0:0 with SMTP id z8csp203696wrt; Wed, 22 Mar 2023 08:09:11 -0700 (PDT) X-Google-Smtp-Source: AK7set+7eoxcvkgU5+qMZ/mQZNdB/WrN3xtr1jzDaTxTHZsb21x2s38D2wCb6CXS8T7hQg/CENq9 X-Received: by 2002:a05:6214:21e2:b0:579:5dbc:ab8c with SMTP id p2-20020a05621421e200b005795dbcab8cmr6591524qvj.30.1679497751245; Wed, 22 Mar 2023 08:09:11 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1679497751; cv=none; d=google.com; s=arc-20160816; b=o5xllovUtrYhEyaPaSyehWbi6hWDcB+ajEC0Hoc7znWsn9OI6e1AEMONM6cUtlVKxS nux0TZzu+sWkAOTQcmpbzNFLmEPZpWPDU24eW4vw4aTyuIE0r4rknlhH//PwWWT4S15h yvygVUzupIa0Q2jR8W8Ztj+sho65ThAanwxCvzpWQI5MsPCZsDK8Wy5tBcS3CIRWTQNO MZ7aoWILVNW9ZBs1iXkwNLI4fFiFmEyrD2pb2VBTeBq/kfSzmJWh1k4UJOtkCJctK0JR 2ui9S6v5vXxJtSlNsD+sMmuXeeYtpIgfnhr25pzxI9Lfybw/zgANZexZw4OKVt4m/CbZ 9B5g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=2kvritCIjGTiqdgRNHvpXtJsxXziMDXMFnO/TaSkgDA=; b=SHRE2lIm+7zsRWOBwQ50eKWTnptQec4yLg+BeBl5fiUyQUCbz90s+jSrYaOSy8jOiE c7M53GhYaA3+OJ5HoFiJkSovIrLE7AhQvfIWADLeh9Ic4Wly1nKCP+Xpzo8ZtBBHouXM peUq9AzvtlE9t5Irf9Ojpp0XFCUgylIOXx7I5AFZtpAQcRMASyzPbQmy+Lr3MCpvsYNn hfbofKkjbTDz4EjUP6+qZyOO5ndTKHbqA2kkI0ULtZ7MD8ogF1dNk/zbiWd59+93EDsh Bk/OtACUSJHfXRK8kkHX7uJc+hDKc8IZNWP8XGqFEpdFkvUVEQwOL6EDurs3Dsy1cBgU QOUQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=MigUZtuJ; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [209.51.188.17]) by mx.google.com with ESMTPS id df4-20020a056214080400b0056eb4187816si10020875qvb.221.2023.03.22.08.09.10 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 22 Mar 2023 08:09:11 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=MigUZtuJ; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pf04S-00031Y-TI; Wed, 22 Mar 2023 11:08:14 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pf04C-0002p5-Ls for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:07:56 -0400 Received: from mail-pj1-x1034.google.com ([2607:f8b0:4864:20::1034]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pf04A-0007IS-CR for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:07:56 -0400 Received: by mail-pj1-x1034.google.com with SMTP id o6-20020a17090a9f8600b0023f32869993so19967832pjp.1 for ; Wed, 22 Mar 2023 08:07:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1679497673; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=2kvritCIjGTiqdgRNHvpXtJsxXziMDXMFnO/TaSkgDA=; b=MigUZtuJQn7jYFc4dNJaVW0JCPRgKK6jXDGDq3p09hiPfg/duEEWJQhLQlNb/KgxQy eoTfNwQpfeOZhbRrCoFdcfLt7DEEVtIv/UZ4Ts1CBne5K0DEmBZ2YOQJrlgCkcIWiF+w hQhxqXywwwOZ39ppQkr94Sp6o+6I3uMS6OmOJGDOfjDbU+FmpBRUdN/YvjikiScni65r yOf8W4MQV4XNorF0yZizafW0mDUJaQv2+9HDdY7dnX02YRRMgIXjnuzV8lHl+jQb1vU4 7QELAs+hCLt5g+IDfXZNA23Qcx4l4oRl3Jgcrb7ypdWhvWAjtMbggqnTE9/8Ic5iyktV o+Eg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679497673; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=2kvritCIjGTiqdgRNHvpXtJsxXziMDXMFnO/TaSkgDA=; b=lOO+353018Rmbx8vVhMF20Tl+mcqBceCcYO2aByahtsX50KvtzdkrIB4wy5lxgPlnJ eYnJ9omhmuL0bJT5Gesa+0rpw1VGJCtqvjIPJfYS/9S3Rr4fEFK4a8mdc7bIqg8cxNUu E2FTmzhNxRXiSu0v8sPWuKr9rfEV5qYRzhGFXyjOgSCR/k/7tykajhWHmz8jDLDAgIRw eMCCN3wuLhnRVTuwj19raNsqMRBKYlVRCwBVtDNLGyZYcUcOZqE2H8FZsAiJV178sJrC UMu09No/6Ekc78g9YnEXEy3BCnF2hOsQy6lF0vDjq9fh2xNttD0RFao7FD5K/logvU1a g3og== X-Gm-Message-State: AO0yUKWxgcTT1H9M02TDQZQFmfpEYMgtbh8xT2Yi77oZrtGc527Gqrue lBzH3ctVpFuLHIyFatmVZ7/Lb/SmlbsxVxCoSSQ= X-Received: by 2002:a17:902:f691:b0:1a1:be45:9857 with SMTP id l17-20020a170902f69100b001a1be459857mr3795698plg.1.1679497672993; Wed, 22 Mar 2023 08:07:52 -0700 (PDT) Received: from stoup.. (24-113-166-229.wavecable.com. [24.113.166.229]) by smtp.gmail.com with ESMTPSA id 17-20020a170902ee5100b0019339f3368asm10757555plo.3.2023.03.22.08.07.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Mar 2023 08:07:52 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: cota@braap.org, peter.maydell@linaro.org, =?utf-8?q?Philippe_Mathieu-Dau?= =?utf-8?q?d=C3=A9?= Subject: [PATCH for-8.0 05/11] accel/tcg: Pass last not end to page_set_flags Date: Wed, 22 Mar 2023 08:07:38 -0700 Message-Id: <20230322150744.175010-6-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230322150744.175010-1-richard.henderson@linaro.org> References: <20230322150744.175010-1-richard.henderson@linaro.org> MIME-Version: 1.0 Received-SPF: pass client-ip=2607:f8b0:4864:20::1034; envelope-from=richard.henderson@linaro.org; helo=mail-pj1-x1034.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: qemu-devel-bounces+patch=linaro.org@nongnu.org Pass the address of the last byte to be changed, rather than the first address past the last byte. This avoids overflow when the last page of the address space is involved. Resolves: https://gitlab.com/qemu-project/qemu/-/issues/1528 Reviewed-by: Philippe Mathieu-Daudé Signed-off-by: Richard Henderson --- include/exec/cpu-all.h | 2 +- accel/tcg/user-exec.c | 16 +++++++--------- bsd-user/mmap.c | 6 +++--- linux-user/elfload.c | 11 ++++++----- linux-user/mmap.c | 16 ++++++++-------- linux-user/syscall.c | 4 ++-- 6 files changed, 27 insertions(+), 28 deletions(-) diff --git a/include/exec/cpu-all.h b/include/exec/cpu-all.h index 456afd0e22..be99cd3621 100644 --- a/include/exec/cpu-all.h +++ b/include/exec/cpu-all.h @@ -285,7 +285,7 @@ typedef int (*walk_memory_regions_fn)(void *, target_ulong, int walk_memory_regions(void *, walk_memory_regions_fn); int page_get_flags(target_ulong address); -void page_set_flags(target_ulong start, target_ulong end, int flags); +void page_set_flags(target_ulong start, target_ulong last, int flags); void page_reset_target_data(target_ulong start, target_ulong end); int page_check_range(target_ulong start, target_ulong len, int flags); diff --git a/accel/tcg/user-exec.c b/accel/tcg/user-exec.c index 7b37fd229e..035f8096b2 100644 --- a/accel/tcg/user-exec.c +++ b/accel/tcg/user-exec.c @@ -480,24 +480,22 @@ static bool pageflags_set_clear(target_ulong start, target_ulong last, * The flag PAGE_WRITE_ORG is positioned automatically depending * on PAGE_WRITE. The mmap_lock should already be held. */ -void page_set_flags(target_ulong start, target_ulong end, int flags) +void page_set_flags(target_ulong start, target_ulong last, int flags) { - target_ulong last; bool reset = false; bool inval_tb = false; /* This function should never be called with addresses outside the guest address space. If this assert fires, it probably indicates a missing call to h2g_valid. */ - assert(start < end); - assert(end - 1 <= GUEST_ADDR_MAX); + assert(start <= last); + assert(last <= GUEST_ADDR_MAX); /* Only set PAGE_ANON with new mappings. */ assert(!(flags & PAGE_ANON) || (flags & PAGE_RESET)); assert_memory_lock(); - start = start & TARGET_PAGE_MASK; - end = TARGET_PAGE_ALIGN(end); - last = end - 1; + start &= TARGET_PAGE_MASK; + last |= ~TARGET_PAGE_MASK; if (!(flags & PAGE_VALID)) { flags = 0; @@ -510,7 +508,7 @@ void page_set_flags(target_ulong start, target_ulong end, int flags) } if (!flags || reset) { - page_reset_target_data(start, end); + page_reset_target_data(start, last + 1); inval_tb |= pageflags_unset(start, last); } if (flags) { @@ -518,7 +516,7 @@ void page_set_flags(target_ulong start, target_ulong end, int flags) ~(reset ? 0 : PAGE_STICKY)); } if (inval_tb) { - tb_invalidate_phys_range(start, end); + tb_invalidate_phys_range(start, last + 1); } } diff --git a/bsd-user/mmap.c b/bsd-user/mmap.c index d35650e562..565b9f97ed 100644 --- a/bsd-user/mmap.c +++ b/bsd-user/mmap.c @@ -118,7 +118,7 @@ int target_mprotect(abi_ulong start, abi_ulong len, int prot) if (ret != 0) goto error; } - page_set_flags(start, start + len, prot | PAGE_VALID); + page_set_flags(start, start + len - 1, prot | PAGE_VALID); mmap_unlock(); return 0; error: @@ -656,7 +656,7 @@ abi_long target_mmap(abi_ulong start, abi_ulong len, int prot, } } the_end1: - page_set_flags(start, start + len, prot | PAGE_VALID); + page_set_flags(start, start + len - 1, prot | PAGE_VALID); the_end: #ifdef DEBUG_MMAP printf("ret=0x" TARGET_ABI_FMT_lx "\n", start); @@ -767,7 +767,7 @@ int target_munmap(abi_ulong start, abi_ulong len) } if (ret == 0) { - page_set_flags(start, start + len, 0); + page_set_flags(start, start + len - 1, 0); } mmap_unlock(); return ret; diff --git a/linux-user/elfload.c b/linux-user/elfload.c index bb2001bf30..b068676340 100644 --- a/linux-user/elfload.c +++ b/linux-user/elfload.c @@ -212,7 +212,7 @@ static bool init_guest_commpage(void) exit(EXIT_FAILURE); } page_set_flags(TARGET_VSYSCALL_PAGE, - TARGET_VSYSCALL_PAGE + TARGET_PAGE_SIZE, + TARGET_VSYSCALL_PAGE | ~TARGET_PAGE_MASK, PAGE_EXEC | PAGE_VALID); return true; } @@ -443,7 +443,7 @@ static bool init_guest_commpage(void) exit(EXIT_FAILURE); } - page_set_flags(commpage, commpage + qemu_host_page_size, + page_set_flags(commpage, commpage | ~qemu_host_page_mask, PAGE_READ | PAGE_EXEC | PAGE_VALID); return true; } @@ -1315,7 +1315,7 @@ static bool init_guest_commpage(void) exit(EXIT_FAILURE); } - page_set_flags(LO_COMMPAGE, LO_COMMPAGE + TARGET_PAGE_SIZE, + page_set_flags(LO_COMMPAGE, LO_COMMPAGE | ~TARGET_PAGE_MASK, PAGE_READ | PAGE_EXEC | PAGE_VALID); return true; } @@ -1727,7 +1727,7 @@ static bool init_guest_commpage(void) * and implement syscalls. Here, simply mark the page executable. * Special case the entry points during translation (see do_page_zero). */ - page_set_flags(LO_COMMPAGE, LO_COMMPAGE + TARGET_PAGE_SIZE, + page_set_flags(LO_COMMPAGE, LO_COMMPAGE | ~TARGET_PAGE_MASK, PAGE_EXEC | PAGE_VALID); return true; } @@ -2208,7 +2208,8 @@ static void zero_bss(abi_ulong elf_bss, abi_ulong last_bss, int prot) /* Ensure that the bss page(s) are valid */ if ((page_get_flags(last_bss-1) & prot) != prot) { - page_set_flags(elf_bss & TARGET_PAGE_MASK, last_bss, prot | PAGE_VALID); + page_set_flags(elf_bss & TARGET_PAGE_MASK, last_bss - 1, + prot | PAGE_VALID); } if (host_start < host_map_start) { diff --git a/linux-user/mmap.c b/linux-user/mmap.c index cf14930c30..9c70f51d97 100644 --- a/linux-user/mmap.c +++ b/linux-user/mmap.c @@ -181,7 +181,7 @@ int target_mprotect(abi_ulong start, abi_ulong len, int target_prot) } } - page_set_flags(start, start + len, page_flags); + page_set_flags(start, start + len - 1, page_flags); ret = 0; error: @@ -640,15 +640,15 @@ abi_long target_mmap(abi_ulong start, abi_ulong len, int target_prot, } page_flags |= PAGE_RESET; if (passthrough_start == passthrough_end) { - page_set_flags(start, start + len, page_flags); + page_set_flags(start, start + len - 1, page_flags); } else { if (start < passthrough_start) { - page_set_flags(start, passthrough_start, page_flags); + page_set_flags(start, passthrough_start - 1, page_flags); } - page_set_flags(passthrough_start, passthrough_end, + page_set_flags(passthrough_start, passthrough_end - 1, page_flags | PAGE_PASSTHROUGH); if (passthrough_end < start + len) { - page_set_flags(passthrough_end, start + len, page_flags); + page_set_flags(passthrough_end, start + len - 1, page_flags); } } the_end: @@ -763,7 +763,7 @@ int target_munmap(abi_ulong start, abi_ulong len) } if (ret == 0) { - page_set_flags(start, start + len, 0); + page_set_flags(start, start + len - 1, 0); } mmap_unlock(); return ret; @@ -849,8 +849,8 @@ abi_long target_mremap(abi_ulong old_addr, abi_ulong old_size, } else { new_addr = h2g(host_addr); prot = page_get_flags(old_addr); - page_set_flags(old_addr, old_addr + old_size, 0); - page_set_flags(new_addr, new_addr + new_size, + page_set_flags(old_addr, old_addr + old_size - 1, 0); + page_set_flags(new_addr, new_addr + new_size - 1, prot | PAGE_VALID | PAGE_RESET); } mmap_unlock(); diff --git a/linux-user/syscall.c b/linux-user/syscall.c index 24cea6fb6a..7fbc664e83 100644 --- a/linux-user/syscall.c +++ b/linux-user/syscall.c @@ -4594,7 +4594,7 @@ static inline abi_ulong do_shmat(CPUArchState *cpu_env, } raddr=h2g((unsigned long)host_raddr); - page_set_flags(raddr, raddr + shm_info.shm_segsz, + page_set_flags(raddr, raddr + shm_info.shm_segsz - 1, PAGE_VALID | PAGE_RESET | PAGE_READ | (shmflg & SHM_RDONLY ? 0 : PAGE_WRITE)); @@ -4624,7 +4624,7 @@ static inline abi_long do_shmdt(abi_ulong shmaddr) for (i = 0; i < N_SHM_REGIONS; ++i) { if (shm_regions[i].in_use && shm_regions[i].start == shmaddr) { shm_regions[i].in_use = false; - page_set_flags(shmaddr, shmaddr + shm_regions[i].size, 0); + page_set_flags(shmaddr, shmaddr + shm_regions[i].size - 1, 0); break; } } From patchwork Wed Mar 22 15:07:39 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 665902 Delivered-To: patch@linaro.org Received: by 2002:a5d:4d08:0:0:0:0:0 with SMTP id z8csp203775wrt; Wed, 22 Mar 2023 08:09:18 -0700 (PDT) X-Google-Smtp-Source: AK7set+Vowgb0TjwSNv4Zpe+zrz5hr6hFT5ilvg367nwWtcm6zS47+pMon8XAhksNPuHf8H4ZmMf X-Received: by 2002:a05:622a:1748:b0:3c0:1010:8d4a with SMTP id l8-20020a05622a174800b003c010108d4amr4763964qtk.1.1679497758117; Wed, 22 Mar 2023 08:09:18 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1679497758; cv=none; d=google.com; s=arc-20160816; b=DwJf0Vo+GdJ313G3rY99eJsOmRp2ALEAp/kx3aVUf+Hrt1IDQ72Oo5SdJLY+QVeGHS higeQPeGtwF3/HPruRXB05WFJ7HPK84nQn9MRfqBQihK0CPPlLZ6VK+L99P0wxb2HEEY T72CD9+hKbaImOp7gTFWZrt+YCvGI3p1SbrvGH3i5HyWs1iO49VGpeIIhU1nEcH5cCCs ZG9PXbd2t5Sb0N/YDyBi/v+QJVNhJcIqPa087534aBpP2GR8g0pTvxvXuJzEjdFZcoQP IlohsGtD7BoPjCRhPakWxRth03I/UC9dy0sPhha5u0fgiEsROOw9+PaBoj72LavvFAby y+Hw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=fml4Pm46/jWkyRSlZ3NNbqY5RtzmzqQcXM/tCMICWQU=; b=PhBsgRMSNKQskGC2DSzTP4dCwiAIo3Zy2zeJ68pXhQI/grSozp4BxBHBRU66nYcTVe is8uMDE9u9ZVItMxn/Usu/yXLpXmpt+MEFNMcdbZnxuneC2pXXKA7r0RDk2Y49S0lxZV eTCqcuNI/InpEnPoaBhvBTqY2RihHJynYs/OsvfU+92PqoAyqEErRqpXduSa8z50l/2R SIVbsOcYKPjdmbFS8vY7exOQWuJzL6QS9JSFGyjtJOlEPJYd7LbAc6x4Sr/ldcWpp4bV oirA11DvG2NrYQE1PBskd2NkFfq30w3BNz3R4hh7ih3hZnRphCuzsZ3KBONfjlvdXcL5 EDzA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=vUUrDkVh; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [209.51.188.17]) by mx.google.com with ESMTPS id v6-20020a05622a188600b003e38b50d3dbsi1282643qtc.277.2023.03.22.08.09.17 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 22 Mar 2023 08:09:18 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=vUUrDkVh; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pf04d-0003IG-A9; Wed, 22 Mar 2023 11:08:23 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pf04H-0002xt-Ls for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:08:02 -0400 Received: from mail-pl1-x634.google.com ([2607:f8b0:4864:20::634]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pf04B-0007JH-J3 for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:07:56 -0400 Received: by mail-pl1-x634.google.com with SMTP id c18so19536671ple.11 for ; Wed, 22 Mar 2023 08:07:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1679497674; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=fml4Pm46/jWkyRSlZ3NNbqY5RtzmzqQcXM/tCMICWQU=; b=vUUrDkVhbiDvd1uNkVlGrN+9kqArX90/d9k4NCt/q+/fGZAl5hRx69OVOflrDaHGrL oHxG2fJtoPwwzq//ghL03rFu7lW6INyNNp95AiLMnwZ4cUZw0xy01buGf5pjkJU1bde2 9UCzxGm+zYvr7smXozlrn7tq7VC1qIGeWpe/NoeiIDsjgMohLCjUILH+sR6zVtKBZy7i n6iBQAD87XiR+dd69/lNJlBcMAxdT2huoKNyEySmjOQ0ghGw3hJnrLYoFHBnCNgswyNu KpvDlbq/BQVss/OznQ5Mc3ZzmYrXvkou+AAExv486xkOYN+d2m4CHD6XZ67C0MnS8rox gwTQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679497674; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=fml4Pm46/jWkyRSlZ3NNbqY5RtzmzqQcXM/tCMICWQU=; b=Fu32AguO4hJM0rUhiYZDm3vyqLGSoA5sLd9rc7gr1ABdO+oW1lOj1wG1i5xI4zQJRl RGnId7kGmp5ewwdm+X7Dx1lfx+ywvgxj5ymq5tWO2htTuCoBWfcX7kSz32wyNjFQShgm OeY+81cWqUa48t6nN6IGlF6KfKyqFTich/HQdiSJ0ZCbxyMltYC1h9EmktFXdcOgKCf5 JMvFrM1efmZWVeB37ngj8PNgPO9bZbLdtX+knzXf3knGAhbwBKIvyVqlXlx0tKO7DG44 ltUMIhwXpwpHADQUXIeoj6KWqH1W/BEhs+1MOUkPL986CWoutUfTkJ1K6J2/VdkeKu9w qKEQ== X-Gm-Message-State: AAQBX9fVoHlZB4tXb1BFf/aH2GL9Bdcje48XiCX7EQ0vqnHQSY/ZcNpT pkWPygCi9Dq1cB42U6vkbP5b/M2E4GpZ6033Qy0= X-Received: by 2002:a17:903:2345:b0:19a:59d1:389e with SMTP id c5-20020a170903234500b0019a59d1389emr2718562plh.23.1679497674323; Wed, 22 Mar 2023 08:07:54 -0700 (PDT) Received: from stoup.. (24-113-166-229.wavecable.com. [24.113.166.229]) by smtp.gmail.com with ESMTPSA id 17-20020a170902ee5100b0019339f3368asm10757555plo.3.2023.03.22.08.07.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Mar 2023 08:07:53 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: cota@braap.org, peter.maydell@linaro.org, =?utf-8?q?Philippe_Mathieu-Dau?= =?utf-8?q?d=C3=A9?= Subject: [PATCH for-8.0 06/11] accel/tcg: Pass last not end to page_reset_target_data Date: Wed, 22 Mar 2023 08:07:39 -0700 Message-Id: <20230322150744.175010-7-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230322150744.175010-1-richard.henderson@linaro.org> References: <20230322150744.175010-1-richard.henderson@linaro.org> MIME-Version: 1.0 Received-SPF: pass client-ip=2607:f8b0:4864:20::634; envelope-from=richard.henderson@linaro.org; helo=mail-pl1-x634.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: qemu-devel-bounces+patch=linaro.org@nongnu.org Pass the address of the last byte to be changed, rather than the first address past the last byte. This avoids overflow when the last page of the address space is involved. Reviewed-by: Philippe Mathieu-Daudé Signed-off-by: Richard Henderson --- include/exec/cpu-all.h | 2 +- accel/tcg/user-exec.c | 11 +++++------ linux-user/mmap.c | 2 +- 3 files changed, 7 insertions(+), 8 deletions(-) diff --git a/include/exec/cpu-all.h b/include/exec/cpu-all.h index be99cd3621..090922e4a8 100644 --- a/include/exec/cpu-all.h +++ b/include/exec/cpu-all.h @@ -286,7 +286,7 @@ int walk_memory_regions(void *, walk_memory_regions_fn); int page_get_flags(target_ulong address); void page_set_flags(target_ulong start, target_ulong last, int flags); -void page_reset_target_data(target_ulong start, target_ulong end); +void page_reset_target_data(target_ulong start, target_ulong last); int page_check_range(target_ulong start, target_ulong len, int flags); /** diff --git a/accel/tcg/user-exec.c b/accel/tcg/user-exec.c index 035f8096b2..20b6fc2f6e 100644 --- a/accel/tcg/user-exec.c +++ b/accel/tcg/user-exec.c @@ -508,7 +508,7 @@ void page_set_flags(target_ulong start, target_ulong last, int flags) } if (!flags || reset) { - page_reset_target_data(start, last + 1); + page_reset_target_data(start, last); inval_tb |= pageflags_unset(start, last); } if (flags) { @@ -814,15 +814,14 @@ typedef struct TargetPageDataNode { static IntervalTreeRoot targetdata_root; -void page_reset_target_data(target_ulong start, target_ulong end) +void page_reset_target_data(target_ulong start, target_ulong last) { IntervalTreeNode *n, *next; - target_ulong last; assert_memory_lock(); - start = start & TARGET_PAGE_MASK; - last = TARGET_PAGE_ALIGN(end) - 1; + start &= TARGET_PAGE_MASK; + last |= ~TARGET_PAGE_MASK; for (n = interval_tree_iter_first(&targetdata_root, start, last), next = n ? interval_tree_iter_next(n, start, last) : NULL; @@ -885,7 +884,7 @@ void *page_get_target_data(target_ulong address) return t->data[(page - region) >> TARGET_PAGE_BITS]; } #else -void page_reset_target_data(target_ulong start, target_ulong end) { } +void page_reset_target_data(target_ulong start, target_ulong last) { } #endif /* TARGET_PAGE_DATA_SIZE */ /* The softmmu versions of these helpers are in cputlb.c. */ diff --git a/linux-user/mmap.c b/linux-user/mmap.c index 9c70f51d97..0aa8ae7356 100644 --- a/linux-user/mmap.c +++ b/linux-user/mmap.c @@ -946,7 +946,7 @@ abi_long target_madvise(abi_ulong start, abi_ulong len_in, int advice) if (can_passthrough_madvise(start, end)) { ret = get_errno(madvise(g2h_untagged(start), len, advice)); if ((advice == MADV_DONTNEED) && (ret == 0)) { - page_reset_target_data(start, start + len); + page_reset_target_data(start, start + len - 1); } } } From patchwork Wed Mar 22 15:07:40 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 665903 Delivered-To: patch@linaro.org Received: by 2002:a5d:4d08:0:0:0:0:0 with SMTP id z8csp203790wrt; Wed, 22 Mar 2023 08:09:20 -0700 (PDT) X-Google-Smtp-Source: AK7set9FtLGjhJHVN2yWYh6BclyzxjP0lN2wA3Dj2mBB6v4VVnpEOZZ1xxwv2YrKygE4H39Pi1yW X-Received: by 2002:ac8:7f10:0:b0:3ba:18c2:99e7 with SMTP id f16-20020ac87f10000000b003ba18c299e7mr6716515qtk.45.1679497760100; Wed, 22 Mar 2023 08:09:20 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1679497760; cv=none; d=google.com; s=arc-20160816; b=VRlozwlKwMw+S+fpsJgZvV/ZQpC0FlEYUFLDGlL+Hn5+GMBb+6hA9OSImaUhvm33+G JwrKlTJ4hFnoQ9QhOmoHAguP9wbdz3d3TfT6Igyy1PN2jeSBveYVwiMysfGp0t+18abD ROVOgnwGxFar86tmqlD/JRQX+PPQX14qk471F5wYhdywfkCNIUrKP4geAux/3yD0vtjb urkgeJLIn7yO9qAv0cmIeiQElyX8okP/80wJTZQR+rKW7AnxOwqvVMfexrPq9O6GA/Vf H+JyOtXy/kupuOOmIlY6jSQkR1/T7lyP9SAJ/l0w3qfSc2s25/pFzdtTC4RTbxpcHyPa cRnw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=s8SVCaZUmE/Km0+IIG6EiSCxwnpR9ibdQSVxm7qmuBg=; b=XdEzGzcRZ6P3hZG0jqCjDTlbRxmsidDen0E0DJXdpzNWC3NrgCi3Skl8oo29p/lycd HmjA/5UItzHFPyRhv8zTfOW1icND8sZ39YgQGCcqlaAorpiLb+dcLGhmy5BEd9Am+vb2 8kIaIqxz461V/7pVNd4HcjFTceQVxjBu3h5W9ab1x7j/lI2ziRKigkQOPZE2Y2zi6oLY nwLOHUdtgsEs8KREjbW7X3x9VMV+dLJLddwY1vWIZzhBV2sZLyFqKsnX/meiJpsT0thF /xCedNOJy+M6WHMtOy161+9ZhS43UgMW9agOcFukc9eLYqfkA/LIec9vwmbNBnf2MHc5 OKsQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b="xw/9c7dW"; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [209.51.188.17]) by mx.google.com with ESMTPS id e12-20020ac85dcc000000b003ba201d92b0si10737993qtx.285.2023.03.22.08.09.19 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 22 Mar 2023 08:09:20 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b="xw/9c7dW"; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pf04g-0003Up-MG; Wed, 22 Mar 2023 11:08:27 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pf04J-0002zq-3K for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:08:03 -0400 Received: from mail-pj1-x102c.google.com ([2607:f8b0:4864:20::102c]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pf04C-0007Jn-QR for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:08:02 -0400 Received: by mail-pj1-x102c.google.com with SMTP id gp15-20020a17090adf0f00b0023d1bbd9f9eso23930404pjb.0 for ; Wed, 22 Mar 2023 08:07:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1679497675; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=s8SVCaZUmE/Km0+IIG6EiSCxwnpR9ibdQSVxm7qmuBg=; b=xw/9c7dWnXZ+TSfBjuEjcmhtRO0cMDYz6vsXm2WrJYTeXcf6qlYIu1OEMXJ/KpOhZP k7p1ufqW4ls1CsQEXE/IUG8DtJ0NqJPaMnnKrRPNjLX9GPsJyTIZ4AUbiqOxBNNYO4xy qPdptXr5gzDtm1Q/rLc78A+Xf+sQuACdiT6TiGubAL5CHEH+tPwE1IidVXn3A1abEZsO RMfDOu71FjF9t37Lfao/lwcM7kGVrhcTmUG9KrZt15fYTbka5nA/euoqOtA1Z5s3OT/h 2pLPgH4woK0xzh5Jm4FI9ocPBtahdzwcgW77lGqXYJE955ynRWPt5+Y7ohR5+Rl3YfTJ Vjjg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679497675; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=s8SVCaZUmE/Km0+IIG6EiSCxwnpR9ibdQSVxm7qmuBg=; b=R5Iz4w4Zyr/48SnaSJMkmJpibbj27OzCjvhpTI/Wv85F4g4oqRJ3Q2qP6Y1loif2iK k2JI+WyBlXAnWhXmVLAlkcXaSk3ZNtm75JShomHJ391r/R5np/xMw2S9FH6k/A6humEh XUEHiQVxf9mbi8KOdCb6uLsNEGZMuj0pMCNi6DWXYWfeLsfDbe6lo4XbIcDqvCYwE2Pd 4a1mwfJKRob+qu6H4MwvR9phYYXfyX4BRR0kOQwkcqI3BZcCmjS4IIMHkN1SCcGFt/j4 K+b0CZNpLS9Kb9NMuOlSaGlrQJi5kez/m9pkBcqAMIv51TSMgGhj0mSZXEEK/eZsLIVD 5LMQ== X-Gm-Message-State: AO0yUKUymtc2J94dSDpNdEcB19AXr6NG4y1UI5QbEigr7aQaJgwp42j/ zFIJsSBKzcUI6YQtrqikNc0Sa2nnPq/KvzgPDOM= X-Received: by 2002:a17:902:7c11:b0:19e:872b:e844 with SMTP id x17-20020a1709027c1100b0019e872be844mr2574829pll.40.1679497675428; Wed, 22 Mar 2023 08:07:55 -0700 (PDT) Received: from stoup.. (24-113-166-229.wavecable.com. [24.113.166.229]) by smtp.gmail.com with ESMTPSA id 17-20020a170902ee5100b0019339f3368asm10757555plo.3.2023.03.22.08.07.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Mar 2023 08:07:55 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: cota@braap.org, peter.maydell@linaro.org, =?utf-8?q?Philippe_Mathieu-Dau?= =?utf-8?q?d=C3=A9?= Subject: [PATCH for-8.0 07/11] accel/tcg: Pass last not end to PAGE_FOR_EACH_TB Date: Wed, 22 Mar 2023 08:07:40 -0700 Message-Id: <20230322150744.175010-8-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230322150744.175010-1-richard.henderson@linaro.org> References: <20230322150744.175010-1-richard.henderson@linaro.org> MIME-Version: 1.0 Received-SPF: pass client-ip=2607:f8b0:4864:20::102c; envelope-from=richard.henderson@linaro.org; helo=mail-pj1-x102c.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: qemu-devel-bounces+patch=linaro.org@nongnu.org Pass the address of the last byte to be changed, rather than the first address past the last byte. This avoids overflow when the last page of the address space is involved. Reviewed-by: Philippe Mathieu-Daudé Signed-off-by: Richard Henderson --- accel/tcg/tb-maint.c | 28 ++++++++++++++++------------ 1 file changed, 16 insertions(+), 12 deletions(-) diff --git a/accel/tcg/tb-maint.c b/accel/tcg/tb-maint.c index a173db17e6..04d2751bb6 100644 --- a/accel/tcg/tb-maint.c +++ b/accel/tcg/tb-maint.c @@ -127,29 +127,29 @@ static void tb_remove(TranslationBlock *tb) } /* TODO: For now, still shared with translate-all.c for system mode. */ -#define PAGE_FOR_EACH_TB(start, end, pagedesc, T, N) \ - for (T = foreach_tb_first(start, end), \ - N = foreach_tb_next(T, start, end); \ +#define PAGE_FOR_EACH_TB(start, last, pagedesc, T, N) \ + for (T = foreach_tb_first(start, last), \ + N = foreach_tb_next(T, start, last); \ T != NULL; \ - T = N, N = foreach_tb_next(N, start, end)) + T = N, N = foreach_tb_next(N, start, last)) typedef TranslationBlock *PageForEachNext; static PageForEachNext foreach_tb_first(tb_page_addr_t start, - tb_page_addr_t end) + tb_page_addr_t last) { - IntervalTreeNode *n = interval_tree_iter_first(&tb_root, start, end - 1); + IntervalTreeNode *n = interval_tree_iter_first(&tb_root, start, last); return n ? container_of(n, TranslationBlock, itree) : NULL; } static PageForEachNext foreach_tb_next(PageForEachNext tb, tb_page_addr_t start, - tb_page_addr_t end) + tb_page_addr_t last) { IntervalTreeNode *n; if (tb) { - n = interval_tree_iter_next(&tb->itree, start, end - 1); + n = interval_tree_iter_next(&tb->itree, start, last); if (n) { return container_of(n, TranslationBlock, itree); } @@ -320,7 +320,7 @@ struct page_collection { }; typedef int PageForEachNext; -#define PAGE_FOR_EACH_TB(start, end, pagedesc, tb, n) \ +#define PAGE_FOR_EACH_TB(start, last, pagedesc, tb, n) \ TB_FOR_EACH_TAGGED((pagedesc)->first_tb, tb, n, page_next) #ifdef CONFIG_DEBUG_TCG @@ -995,10 +995,11 @@ void tb_invalidate_phys_range(tb_page_addr_t start, tb_page_addr_t end) { TranslationBlock *tb; PageForEachNext n; + tb_page_addr_t last = end - 1; assert_memory_lock(); - PAGE_FOR_EACH_TB(start, end, unused, tb, n) { + PAGE_FOR_EACH_TB(start, last, unused, tb, n) { tb_phys_invalidate__locked(tb); } } @@ -1030,6 +1031,7 @@ bool tb_invalidate_phys_page_unwind(tb_page_addr_t addr, uintptr_t pc) bool current_tb_modified; TranslationBlock *tb; PageForEachNext n; + tb_page_addr_t last; /* * Without precise smc semantics, or when outside of a TB, @@ -1046,10 +1048,11 @@ bool tb_invalidate_phys_page_unwind(tb_page_addr_t addr, uintptr_t pc) assert_memory_lock(); current_tb = tcg_tb_lookup(pc); + last = addr | ~TARGET_PAGE_MASK; addr &= TARGET_PAGE_MASK; current_tb_modified = false; - PAGE_FOR_EACH_TB(addr, addr + TARGET_PAGE_SIZE, unused, tb, n) { + PAGE_FOR_EACH_TB(addr, last, unused, tb, n) { if (current_tb == tb && (tb_cflags(current_tb) & CF_COUNT_MASK) != 1) { /* @@ -1091,12 +1094,13 @@ tb_invalidate_phys_page_range__locked(struct page_collection *pages, bool current_tb_modified = false; TranslationBlock *current_tb = retaddr ? tcg_tb_lookup(retaddr) : NULL; #endif /* TARGET_HAS_PRECISE_SMC */ + tb_page_addr_t last G_GNUC_UNUSED = end - 1; /* * We remove all the TBs in the range [start, end[. * XXX: see if in some cases it could be faster to invalidate all the code */ - PAGE_FOR_EACH_TB(start, end, p, tb, n) { + PAGE_FOR_EACH_TB(start, last, p, tb, n) { /* NOTE: this is subtle as a TB may span two physical pages */ if (n == 0) { /* NOTE: tb_end may be after the end of the page, but From patchwork Wed Mar 22 15:07:41 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 665906 Delivered-To: patch@linaro.org Received: by 2002:a5d:4d08:0:0:0:0:0 with SMTP id z8csp204126wrt; Wed, 22 Mar 2023 08:09:51 -0700 (PDT) X-Google-Smtp-Source: AK7set/MpZz24/FDprjUZW6uz8/sxYOI0uMC+R4ePoQYqyx5/v9dK8nodHXDs4+Y6VRhr5Kn+NS9 X-Received: by 2002:ad4:5dcd:0:b0:5a9:c0a1:d31a with SMTP id m13-20020ad45dcd000000b005a9c0a1d31amr6174209qvh.49.1679497790582; Wed, 22 Mar 2023 08:09:50 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1679497790; cv=none; d=google.com; s=arc-20160816; b=u8IdhLBndUlJocl5jecJv9yvo54KD5M9swy8pgoWSbyVZceBZhH2vMpNVgV019dJSz /PDlHqMENirZQsrpya1S0nUPCF+i85Qc7tjNPOT+giEt4AG9DzAs3xrPWq9TzWV07fg1 feNTvHhdxaMB1oQTrSiyxgRSsXP6Gk9+/Lsjvi3D8Ekoh46p/MwdGT/QisDj/VGCRVUV g1o48LtOBChY+U8LYqPQ0nOjLa8ZIzRmau9v7gTXr2/k2OE4jCa5GkhDwH0oB40vulhJ /9JSwk7Hv0s2HntR8E82mQOyUFbo/tPI9suN/UB1d6LvIA9UO6Qh4vPpWeXxVnNjXpQV C4PQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=OMK6G6BOZWlbHX4rg+TLkGN/x34xkpFqL8aYBw8SQ0w=; b=BymDp76KIhWGZibqErTPyBN7o/FrRKqbqif+L+PcY72pkXUG/I1T1xU0r2BBk21Ucw FOSrVJ0XPhix/lrfJ80hlp4Dhi4IwISmzNByjJDBAHlkTkjYUf3sui0oCdBLwDp7N25b YuuD7kJHQ6gfhP5ww9Pd7v3/VUbfajr+gf82NQrOeD1WN7KN2AtEYQttZCp8x1fUh0lK kzeiMvmW+rz65fD+CfAorMzfXzLLiaaXzZLxBl+PYrAcJ9uj+w3SMJWvVERvhLDROhNF 6+hBrxoQInDIvbG073PJ1qhYuJmK7xbr+8WsnReZwdKRqGb9ByNmCMGDjuNddbmnidCK 8Onw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=Hg75OGgV; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [209.51.188.17]) by mx.google.com with ESMTPS id kc8-20020a056214410800b005ca5decd352si6505483qvb.450.2023.03.22.08.09.50 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 22 Mar 2023 08:09:50 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=Hg75OGgV; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pf04k-0003Xg-Gz; Wed, 22 Mar 2023 11:08:30 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pf04L-00032l-GW for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:08:10 -0400 Received: from mail-pl1-x634.google.com ([2607:f8b0:4864:20::634]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pf04H-0007Kg-E7 for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:08:04 -0400 Received: by mail-pl1-x634.google.com with SMTP id ja10so19554264plb.5 for ; Wed, 22 Mar 2023 08:07:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1679497676; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=OMK6G6BOZWlbHX4rg+TLkGN/x34xkpFqL8aYBw8SQ0w=; b=Hg75OGgVVVqJ8K9jjUZa98ox2YwUFnU+TI+Tco112arWLwXN1dj9DgdoEeKzTE2Ps5 0N3Ap4z4swtXI8xu6gZwyiHNyZQaEk+TLJz+9dS0j5lOBk5vGeODZlRjD+FSjzq2NKOw Oca5CCwhUsBXuSSP/7ydGA1ucZqqrlijQPLl2w1cC5VQ9G2Fw9+qpwftfieYCeh2rt9F mveIzBAbe0tvxZETzhXLlorgcDYsX9WuhwdgB1EPKoPn/ff6NjMqi3svOPBuk01lLs3T ZfH9Prj26vMqUD8BfpEkEibwusUAqys9PlW+kJ+HGOKj3tJkFSminJENLbayXZvJAAaX 1yWA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679497676; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=OMK6G6BOZWlbHX4rg+TLkGN/x34xkpFqL8aYBw8SQ0w=; b=DyvbrPnpfvVLSNNaN42HF4K0ImLBPEIbC1PMMeVkyQYlvbTCakx41TmBfDn7MNd01u cV2ZTWHvkPOnsa/5chK8okEVksHLfNeVl8V2fvQITxX+aCmzc4RcjfjtPbYHcAqDyJdl fbMlCB+sJL1EJmhH2Vn5pRCVbadZZSbpGZsqky7tpIxnwTy05m2gEKlOU2MQ5dgjbXmf 4WfqcssSm7TAisjUMz47NfUxARF9h+5KsYhupbrkbOJqvk3La2hCc+VoZ4AQ7PUwKWuC qGBUuWSAxYyDB3UYBeXHAOKlWPn2aYzlcvzJzVNmF+MF8aerscIcTh1Uakktxi785e0i AWYQ== X-Gm-Message-State: AO0yUKUv7IAIlS7Kt1xbaiAqf+lFUDoawPOvoUSZcOpwic5Ktu574w2K HlBV+z3lR40ZTa9KQHQVbUC+F7yEwcLGqkPWcw0= X-Received: by 2002:a17:902:c944:b0:1a1:e14f:3750 with SMTP id i4-20020a170902c94400b001a1e14f3750mr3584388pla.1.1679497676383; Wed, 22 Mar 2023 08:07:56 -0700 (PDT) Received: from stoup.. (24-113-166-229.wavecable.com. [24.113.166.229]) by smtp.gmail.com with ESMTPSA id 17-20020a170902ee5100b0019339f3368asm10757555plo.3.2023.03.22.08.07.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Mar 2023 08:07:55 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: cota@braap.org, peter.maydell@linaro.org, =?utf-8?q?Philippe_Mathieu-Dau?= =?utf-8?q?d=C3=A9?= Subject: [PATCH for-8.0 08/11] accel/tcg: Pass last not end to page_collection_lock Date: Wed, 22 Mar 2023 08:07:41 -0700 Message-Id: <20230322150744.175010-9-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230322150744.175010-1-richard.henderson@linaro.org> References: <20230322150744.175010-1-richard.henderson@linaro.org> MIME-Version: 1.0 Received-SPF: pass client-ip=2607:f8b0:4864:20::634; envelope-from=richard.henderson@linaro.org; helo=mail-pl1-x634.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: qemu-devel-bounces+patch=linaro.org@nongnu.org Pass the address of the last byte to be changed, rather than the first address past the last byte. This avoids overflow when the last page of the address space is involved. Fixes a bug in the loop comparision where "<= end" would lock one more page than required. Reviewed-by: Philippe Mathieu-Daudé Signed-off-by: Richard Henderson --- accel/tcg/tb-maint.c | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) diff --git a/accel/tcg/tb-maint.c b/accel/tcg/tb-maint.c index 04d2751bb6..57da2feb2f 100644 --- a/accel/tcg/tb-maint.c +++ b/accel/tcg/tb-maint.c @@ -511,20 +511,20 @@ static gint tb_page_addr_cmp(gconstpointer ap, gconstpointer bp, gpointer udata) } /* - * Lock a range of pages ([@start,@end[) as well as the pages of all + * Lock a range of pages ([@start,@last]) as well as the pages of all * intersecting TBs. * Locking order: acquire locks in ascending order of page index. */ static struct page_collection *page_collection_lock(tb_page_addr_t start, - tb_page_addr_t end) + tb_page_addr_t last) { struct page_collection *set = g_malloc(sizeof(*set)); tb_page_addr_t index; PageDesc *pd; start >>= TARGET_PAGE_BITS; - end >>= TARGET_PAGE_BITS; - g_assert(start <= end); + last >>= TARGET_PAGE_BITS; + g_assert(start <= last); set->tree = q_tree_new_full(tb_page_addr_cmp, NULL, NULL, page_entry_destroy); @@ -534,7 +534,7 @@ static struct page_collection *page_collection_lock(tb_page_addr_t start, retry: q_tree_foreach(set->tree, page_entry_lock, NULL); - for (index = start; index <= end; index++) { + for (index = start; index <= last; index++) { TranslationBlock *tb; PageForEachNext n; @@ -1154,7 +1154,7 @@ tb_invalidate_phys_page_range__locked(struct page_collection *pages, void tb_invalidate_phys_page(tb_page_addr_t addr) { struct page_collection *pages; - tb_page_addr_t start, end; + tb_page_addr_t start, last; PageDesc *p; p = page_find(addr >> TARGET_PAGE_BITS); @@ -1163,9 +1163,9 @@ void tb_invalidate_phys_page(tb_page_addr_t addr) } start = addr & TARGET_PAGE_MASK; - end = start + TARGET_PAGE_SIZE; - pages = page_collection_lock(start, end); - tb_invalidate_phys_page_range__locked(pages, p, start, end, 0); + last = addr | ~TARGET_PAGE_MASK; + pages = page_collection_lock(start, last); + tb_invalidate_phys_page_range__locked(pages, p, start, last + 1, 0); page_collection_unlock(pages); } @@ -1181,7 +1181,7 @@ void tb_invalidate_phys_range(tb_page_addr_t start, tb_page_addr_t end) struct page_collection *pages; tb_page_addr_t next; - pages = page_collection_lock(start, end); + pages = page_collection_lock(start, end - 1); for (next = (start & TARGET_PAGE_MASK) + TARGET_PAGE_SIZE; start < end; start = next, next += TARGET_PAGE_SIZE) { @@ -1226,7 +1226,7 @@ void tb_invalidate_phys_range_fast(ram_addr_t ram_addr, { struct page_collection *pages; - pages = page_collection_lock(ram_addr, ram_addr + size); + pages = page_collection_lock(ram_addr, ram_addr + size - 1); tb_invalidate_phys_page_fast__locked(pages, ram_addr, size, retaddr); page_collection_unlock(pages); } From patchwork Wed Mar 22 15:07:42 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 665904 Delivered-To: patch@linaro.org Received: by 2002:a5d:4d08:0:0:0:0:0 with SMTP id z8csp203862wrt; Wed, 22 Mar 2023 08:09:26 -0700 (PDT) X-Google-Smtp-Source: AK7set83EjG9FnAkJWt2VahhXVAJKrW88iY8E222dMHN1wFlrkaVdMAo8wpZR9mTjcITYhMj69cY X-Received: by 2002:ac8:5d93:0:b0:3d6:d055:72af with SMTP id d19-20020ac85d93000000b003d6d05572afmr6476235qtx.53.1679497766038; Wed, 22 Mar 2023 08:09:26 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1679497766; cv=none; d=google.com; s=arc-20160816; b=u8NwQnfAs+/lr3dwn8FRWJrP+Iu5WcWvghkX0UELqUQDbfmkYMAUzx9Q+A/3BTRxj3 ASCITzEIOQaHRPRv3IwA3KRGc8jLK9gQp8UUrTAB9xAyY2w+pmHonN0xwjCoV4xqeg+1 ewVwxYkF+3xwkg17Y0MhZ0fulqw8teOE8SsIg3HQNfBpRME0tmW9uoDWRGzQHh62D9wB PmcS4+T3inE5nlMecYg1GdLuYy7bZRpOz1kgqu508jDMOOi1ZCUx1/YXBZMCzDNg3c3z a4nfyO+VLj6R4F4gjvPYNpanW46FH/FEvsoDCNQHN0cAdmvey/0UNlPGFqYeEXZ3HXdU zlOw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=7lQNHN36cq4JX4MpVuNitP2N8g4BnbyjtKLtJ8yHuJE=; b=Qpk7sP8BnmU74qqV0YLM7Z+/pZf6rbcpWO3kI00T2FyTyCmXMdU9bavlLWD7BOkkD6 ajCiGXVb6jjDMdNhs/c8xp8wuqWi1rT/882fTHsPDgGXvIXVGWith1gt4tB1hvuWALcz EY1qzbAOlY95OwioJ1FOi33Oy2wvm+zgmhq/XjGX9Fe68F3mYS9vbHLpqoxbLbUKyiuc n9Fno5ZxdjLT4hVpnJ/IkUgavfc9JAwWbGVlda9jSZtHk795YPGvd8210rZbWvT0mWv5 xAKMdA1VbMLws1ZataB3cdLqrbHfz1eF1HUNexHvQbtbTa1u2dhgJw282ndZrC2Jf2Y7 HroQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=MflxYJOx; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [209.51.188.17]) by mx.google.com with ESMTPS id h19-20020a05622a171300b003e38a96d78bsi1497923qtk.340.2023.03.22.08.09.25 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 22 Mar 2023 08:09:26 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=MflxYJOx; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pf04d-0003Ke-Ci; Wed, 22 Mar 2023 11:08:23 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pf04J-00031I-CR for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:08:03 -0400 Received: from mail-pj1-x1029.google.com ([2607:f8b0:4864:20::1029]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pf04H-0007LB-DU for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:08:03 -0400 Received: by mail-pj1-x1029.google.com with SMTP id l7so1731342pjg.5 for ; Wed, 22 Mar 2023 08:07:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1679497677; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=7lQNHN36cq4JX4MpVuNitP2N8g4BnbyjtKLtJ8yHuJE=; b=MflxYJOxIJIARWIPMDZRefRtzZfMoCmTzUISF2fxavT/eM0hXocv7oLPLRkk8FRsmh vmyLMPQZZu+InlCg9ZDKaYcBIYJTQ48/9WDYOoLkceIfX4Zc7itBZY3d+4gyMXt7xjfK coNR0h3LagNSgTd6tlr4xu0z9DDecj0aIW+Wm9Qc8KG/16WxxQUkNTZBogaWQfIluuwZ w6PlaNQ5D35K4WYInS/sOUNmRlLR88XkakXJK0bYMLwYqMiFXh3kceBP5S+MoO6M7dpT sqNzGa06PSS/nXLfisRRT/vaDa2uqQ122ZA90ISTDqZkkXo/lAW+wgAAEpyfPo5xw+wV LgHg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679497677; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=7lQNHN36cq4JX4MpVuNitP2N8g4BnbyjtKLtJ8yHuJE=; b=qJzIeYQewTR7P/G6grfO8iwkLB1mIodan+lQ2/6gpbfqif0qJfUI/YA9OP+SMs4gfa TimCSES72YY94az1Ywz2/6mn6Y7ivS1sCdVs0GJyhRx9MM2ZVstZyJ0V0cPDh+cH+1jl 2ty6uYf31dAnnDPnPTnA/7BwkYM1MHTJwzyXMenUcYNVJQ95WCoKjhePa/kDoroVAckX P8DSmR67RzO0N0nqCNnyfwXxiwYrgf8J8yEDMc/H2evYthdDulDMO8+rw95y7P0ndGuC X22KzRuWOngMpWi/pgOaOTSK5+Xt8z2FsOV2lNDT0AcNgBFF8VJSG8hiAFpYiEh8zCob EmVg== X-Gm-Message-State: AO0yUKUFp+vXYhvco2ocfNj4YWoo0PgbuQfvrHCZJAdiTcW8zLC5yTJY E9uppniUiYx6g2qP8ppHh1e6kxIWepwmjonEDj4= X-Received: by 2002:a17:902:c613:b0:1a1:e33e:2606 with SMTP id r19-20020a170902c61300b001a1e33e2606mr2456361plr.25.1679497677592; Wed, 22 Mar 2023 08:07:57 -0700 (PDT) Received: from stoup.. (24-113-166-229.wavecable.com. [24.113.166.229]) by smtp.gmail.com with ESMTPSA id 17-20020a170902ee5100b0019339f3368asm10757555plo.3.2023.03.22.08.07.56 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Mar 2023 08:07:57 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: cota@braap.org, peter.maydell@linaro.org, =?utf-8?q?Philippe_Mathieu-Dau?= =?utf-8?q?d=C3=A9?= Subject: [PATCH for-8.0 09/11] accel/tcg: Pass last not end to tb_invalidate_phys_page_range__locked Date: Wed, 22 Mar 2023 08:07:42 -0700 Message-Id: <20230322150744.175010-10-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230322150744.175010-1-richard.henderson@linaro.org> References: <20230322150744.175010-1-richard.henderson@linaro.org> MIME-Version: 1.0 Received-SPF: pass client-ip=2607:f8b0:4864:20::1029; envelope-from=richard.henderson@linaro.org; helo=mail-pj1-x1029.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: qemu-devel-bounces+patch=linaro.org@nongnu.org Pass the address of the last byte to be changed, rather than the first address past the last byte. This avoids overflow when the last page of the address space is involved. Properly truncate tb_last to the end of the page; the comment about tb_end being past the end of the page being ok is not correct, considering overflow. Reviewed-by: Philippe Mathieu-Daudé Signed-off-by: Richard Henderson --- accel/tcg/tb-maint.c | 26 ++++++++++++-------------- 1 file changed, 12 insertions(+), 14 deletions(-) diff --git a/accel/tcg/tb-maint.c b/accel/tcg/tb-maint.c index 57da2feb2f..74823ba464 100644 --- a/accel/tcg/tb-maint.c +++ b/accel/tcg/tb-maint.c @@ -1084,35 +1084,33 @@ bool tb_invalidate_phys_page_unwind(tb_page_addr_t addr, uintptr_t pc) static void tb_invalidate_phys_page_range__locked(struct page_collection *pages, PageDesc *p, tb_page_addr_t start, - tb_page_addr_t end, + tb_page_addr_t last, uintptr_t retaddr) { TranslationBlock *tb; - tb_page_addr_t tb_start, tb_end; PageForEachNext n; #ifdef TARGET_HAS_PRECISE_SMC bool current_tb_modified = false; TranslationBlock *current_tb = retaddr ? tcg_tb_lookup(retaddr) : NULL; #endif /* TARGET_HAS_PRECISE_SMC */ - tb_page_addr_t last G_GNUC_UNUSED = end - 1; /* - * We remove all the TBs in the range [start, end[. + * We remove all the TBs in the range [start, last]. * XXX: see if in some cases it could be faster to invalidate all the code */ PAGE_FOR_EACH_TB(start, last, p, tb, n) { + tb_page_addr_t tb_start, tb_last; + /* NOTE: this is subtle as a TB may span two physical pages */ + tb_start = tb_page_addr0(tb); + tb_last = tb_start + tb->size - 1; if (n == 0) { - /* NOTE: tb_end may be after the end of the page, but - it is not a problem */ - tb_start = tb_page_addr0(tb); - tb_end = tb_start + tb->size; + tb_last = MIN(tb_last, tb_start | ~TARGET_PAGE_MASK); } else { tb_start = tb_page_addr1(tb); - tb_end = tb_start + ((tb_page_addr0(tb) + tb->size) - & ~TARGET_PAGE_MASK); + tb_last = tb_start + (tb_last & ~TARGET_PAGE_MASK); } - if (!(tb_end <= start || tb_start >= end)) { + if (!(tb_last < start || tb_start > last)) { #ifdef TARGET_HAS_PRECISE_SMC if (current_tb == tb && (tb_cflags(current_tb) & CF_COUNT_MASK) != 1) { @@ -1165,7 +1163,7 @@ void tb_invalidate_phys_page(tb_page_addr_t addr) start = addr & TARGET_PAGE_MASK; last = addr | ~TARGET_PAGE_MASK; pages = page_collection_lock(start, last); - tb_invalidate_phys_page_range__locked(pages, p, start, last + 1, 0); + tb_invalidate_phys_page_range__locked(pages, p, start, last, 0); page_collection_unlock(pages); } @@ -1192,7 +1190,7 @@ void tb_invalidate_phys_range(tb_page_addr_t start, tb_page_addr_t end) continue; } assert_page_locked(pd); - tb_invalidate_phys_page_range__locked(pages, pd, start, bound, 0); + tb_invalidate_phys_page_range__locked(pages, pd, start, bound - 1, 0); } page_collection_unlock(pages); } @@ -1212,7 +1210,7 @@ static void tb_invalidate_phys_page_fast__locked(struct page_collection *pages, } assert_page_locked(p); - tb_invalidate_phys_page_range__locked(pages, p, start, start + len, ra); + tb_invalidate_phys_page_range__locked(pages, p, start, start + len - 1, ra); } /* From patchwork Wed Mar 22 15:07:43 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 665909 Delivered-To: patch@linaro.org Received: by 2002:a5d:4d08:0:0:0:0:0 with SMTP id z8csp204352wrt; Wed, 22 Mar 2023 08:10:12 -0700 (PDT) X-Google-Smtp-Source: AK7set/uiGdx2NioiyXx2ei5ZQPUEfWI2+rwkJ6J0JpExfuxbuEIA4xAQwmtFv8LAy5Olf0GJjhb X-Received: by 2002:a05:6214:b63:b0:5aa:43c0:9cdd with SMTP id ey3-20020a0562140b6300b005aa43c09cddmr8335511qvb.45.1679497812204; Wed, 22 Mar 2023 08:10:12 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1679497812; cv=none; d=google.com; s=arc-20160816; b=tUZTHwcSPlfhX62tpqfDMwKaGdfX08tXWBApWxyOb1xKFgJbHqs/f1ircNO7vEEY2w icOM8xaX2brq8R9tH25oV/vyAie+xmLglsTXx6jiN6X1KsOum1X+daU64zD6kxRb5ySI uLXGg7wkIr4wydekT9yWWik/Lzr+kQsthIAQe82Fm/x5lls5jUhTJzGsNYc2bzyU5Q2t ex9z/qavhW8K3WuwJRbvTRRZXJC2z2hoN0rJ3BdNxgvESYsbkrVSrH235bk6rPLZW/0G aF1Syw015pBgWuPodYL2grepHM1LFCOweap7hkEg6kml6kxVeWZhg39USu0xragcF7Nm Y7LQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=Kk3UquZ0rVIuilYEk4nV7wLaq1oBqNaW1wOekl52DrA=; b=yr9JOunFRynUDFRGRgk1abDdH61V1i6531yGfIrmPkC/DcA/5gFMLeGPdwozIXXfi3 yM2DhhyPT9xlw0aqNRabuLefQXH4oBK7539onuaqKJlZZjgKvT11v0X8lFaMI+wta5pQ I+oS3VDC2jY8v2TtD+ZxRa8JJSjHwFr3zPHQP4jrOWBePEaEBGcuN9aRknzHKYkDFG1y ifZpIakyDKAx6KJTYfFYnl+5brbfstbIVEBOTQb9oJc8OB6pwDe6CpEK5+nl6WMc9EB/ 8xp0tEkx6OwNaTWqwN1xjpNf8bCeHnmAvuR9/eirINyb992TRil80kQESFC9nmBGQHNZ TVOQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=WpRuZGnr; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [209.51.188.17]) by mx.google.com with ESMTPS id h3-20020a0ceec3000000b0056ee5ebb3c3si10764740qvs.566.2023.03.22.08.10.12 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 22 Mar 2023 08:10:12 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=WpRuZGnr; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pf04c-0003AF-8l; Wed, 22 Mar 2023 11:08:22 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pf04L-00032k-EZ for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:08:10 -0400 Received: from mail-pj1-x1031.google.com ([2607:f8b0:4864:20::1031]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pf04H-0007Lx-Eu for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:08:04 -0400 Received: by mail-pj1-x1031.google.com with SMTP id mp3-20020a17090b190300b0023fcc8ce113so8927189pjb.4 for ; Wed, 22 Mar 2023 08:07:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1679497678; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Kk3UquZ0rVIuilYEk4nV7wLaq1oBqNaW1wOekl52DrA=; b=WpRuZGnr8cUOVM+SKteXxwAss+Nz+mo8Fcq7LyWDVLJWdQM3lSqiHkd5aVTjKEPtX3 /VSwq6rASBTozh9/sNWDcj0dhzFiHclk84qqXSx6qKdZd4gl3Xygnk3umpZacsVbMHgx 8qMtYo5qCukmLB3jmn1QPvnX6yOctAT7eGqq7nQwomgXqOesUTHqV/3QT1no1GfVu6K2 xoNnK0omoNEUwkxFPn7hpuGC+tGrgVfEtNk2ILZWu++Yc8fT1fdVJXecV5GHJZqKjA7k TuvkPmLDbBTshPinRKCaAoBQxSpiU7t9tZPP02Ba1CttiSK3Hxdv/PJuyf6O3DQuQmdl Ptkw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679497678; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Kk3UquZ0rVIuilYEk4nV7wLaq1oBqNaW1wOekl52DrA=; b=FOJBVnSRCZfKggGHQG85bPUTJskex/0A4bAJEMbUmDvi7IeCzonOfGqe+KGoGvIVrA iYgzBpmFKqSRIyycbQ9HINDxKInx6fELYcdEjOs6V0P8fM4YKJcQtuJhoFugxXlGSOhm 6qzQHxAww8qHbpj9mktbKKEhFa2O2UzCOkXjMFYAB/uWNlD2WF2wZS0ajB0qgrn2TXIC eodcihvpWtasaqcwzB5tUeQnscVTiuinb3HVNrVymLDoovxcmN7x/SC/lHMmL58c6CZN +W5AKeUuhgj/XAm21bzVOodW3AuKLv4tkskcM9n3AoYJ31PQXqjNCo19RDd+A5j6yF17 si1A== X-Gm-Message-State: AO0yUKX/0/oFJPjrds1uDDDKaqVG1/JbeI2lxjJQftPz5S1lVLjkjIvf uBBJOgAIOkGbYlQRUwGeqpmUoRiEPApBA3llCl8= X-Received: by 2002:a17:902:d411:b0:19c:f8c5:d504 with SMTP id b17-20020a170902d41100b0019cf8c5d504mr2296628ple.59.1679497678546; Wed, 22 Mar 2023 08:07:58 -0700 (PDT) Received: from stoup.. (24-113-166-229.wavecable.com. [24.113.166.229]) by smtp.gmail.com with ESMTPSA id 17-20020a170902ee5100b0019339f3368asm10757555plo.3.2023.03.22.08.07.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Mar 2023 08:07:58 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: cota@braap.org, peter.maydell@linaro.org, =?utf-8?q?Philippe_Mathieu-Dau?= =?utf-8?q?d=C3=A9?= Subject: [PATCH for-8.0 10/11] accel/tcg: Pass last not end to tb_invalidate_phys_range Date: Wed, 22 Mar 2023 08:07:43 -0700 Message-Id: <20230322150744.175010-11-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230322150744.175010-1-richard.henderson@linaro.org> References: <20230322150744.175010-1-richard.henderson@linaro.org> MIME-Version: 1.0 Received-SPF: pass client-ip=2607:f8b0:4864:20::1031; envelope-from=richard.henderson@linaro.org; helo=mail-pj1-x1031.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: qemu-devel-bounces+patch=linaro.org@nongnu.org Pass the address of the last byte to be changed, rather than the first address past the last byte. This avoids overflow when the last page of the address space is involved. Reviewed-by: Philippe Mathieu-Daudé Signed-off-by: Richard Henderson --- include/exec/exec-all.h | 2 +- accel/tcg/tb-maint.c | 31 ++++++++++++++++--------------- accel/tcg/translate-all.c | 2 +- accel/tcg/user-exec.c | 2 +- softmmu/physmem.c | 2 +- 5 files changed, 20 insertions(+), 19 deletions(-) diff --git a/include/exec/exec-all.h b/include/exec/exec-all.h index ad9eb6067b..ecded1f112 100644 --- a/include/exec/exec-all.h +++ b/include/exec/exec-all.h @@ -678,7 +678,7 @@ void tb_invalidate_phys_addr(target_ulong addr); void tb_invalidate_phys_addr(AddressSpace *as, hwaddr addr, MemTxAttrs attrs); #endif void tb_phys_invalidate(TranslationBlock *tb, tb_page_addr_t page_addr); -void tb_invalidate_phys_range(tb_page_addr_t start, tb_page_addr_t end); +void tb_invalidate_phys_range(tb_page_addr_t start, tb_page_addr_t last); void tb_set_jmp_target(TranslationBlock *tb, int n, uintptr_t addr); /* GETPC is the true target of the return instruction that we'll execute. */ diff --git a/accel/tcg/tb-maint.c b/accel/tcg/tb-maint.c index 74823ba464..cb1f806f00 100644 --- a/accel/tcg/tb-maint.c +++ b/accel/tcg/tb-maint.c @@ -991,11 +991,10 @@ TranslationBlock *tb_link_page(TranslationBlock *tb, tb_page_addr_t phys_pc, * Called with mmap_lock held for user-mode emulation. * NOTE: this function must not be called while a TB is running. */ -void tb_invalidate_phys_range(tb_page_addr_t start, tb_page_addr_t end) +void tb_invalidate_phys_range(tb_page_addr_t start, tb_page_addr_t last) { TranslationBlock *tb; PageForEachNext n; - tb_page_addr_t last = end - 1; assert_memory_lock(); @@ -1011,11 +1010,11 @@ void tb_invalidate_phys_range(tb_page_addr_t start, tb_page_addr_t end) */ void tb_invalidate_phys_page(tb_page_addr_t addr) { - tb_page_addr_t start, end; + tb_page_addr_t start, last; start = addr & TARGET_PAGE_MASK; - end = start + TARGET_PAGE_SIZE; - tb_invalidate_phys_range(start, end); + last = addr | ~TARGET_PAGE_MASK; + tb_invalidate_phys_range(start, last); } /* @@ -1169,28 +1168,30 @@ void tb_invalidate_phys_page(tb_page_addr_t addr) /* * Invalidate all TBs which intersect with the target physical address range - * [start;end[. NOTE: start and end may refer to *different* physical pages. + * [start;last]. NOTE: start and end may refer to *different* physical pages. * 'is_cpu_write_access' should be true if called from a real cpu write * access: the virtual CPU will exit the current TB if code is modified inside * this TB. */ -void tb_invalidate_phys_range(tb_page_addr_t start, tb_page_addr_t end) +void tb_invalidate_phys_range(tb_page_addr_t start, tb_page_addr_t last) { struct page_collection *pages; - tb_page_addr_t next; + tb_page_addr_t index, index_last; - pages = page_collection_lock(start, end - 1); - for (next = (start & TARGET_PAGE_MASK) + TARGET_PAGE_SIZE; - start < end; - start = next, next += TARGET_PAGE_SIZE) { - PageDesc *pd = page_find(start >> TARGET_PAGE_BITS); - tb_page_addr_t bound = MIN(next, end); + pages = page_collection_lock(start, last); + + index_last = last >> TARGET_PAGE_BITS; + for (index = start >> TARGET_PAGE_BITS; index <= index_last; index++) { + PageDesc *pd = page_find(index); + tb_page_addr_t bound; if (pd == NULL) { continue; } assert_page_locked(pd); - tb_invalidate_phys_page_range__locked(pages, pd, start, bound - 1, 0); + bound = (index << TARGET_PAGE_BITS) | ~TARGET_PAGE_MASK; + bound = MIN(bound, last); + tb_invalidate_phys_page_range__locked(pages, pd, start, bound, 0); } page_collection_unlock(pages); } diff --git a/accel/tcg/translate-all.c b/accel/tcg/translate-all.c index 74deb18bd0..5b13281119 100644 --- a/accel/tcg/translate-all.c +++ b/accel/tcg/translate-all.c @@ -572,7 +572,7 @@ void tb_check_watchpoint(CPUState *cpu, uintptr_t retaddr) cpu_get_tb_cpu_state(env, &pc, &cs_base, &flags); addr = get_page_addr_code(env, pc); if (addr != -1) { - tb_invalidate_phys_range(addr, addr + 1); + tb_invalidate_phys_range(addr, addr); } } } diff --git a/accel/tcg/user-exec.c b/accel/tcg/user-exec.c index 20b6fc2f6e..a7e0c3e2f4 100644 --- a/accel/tcg/user-exec.c +++ b/accel/tcg/user-exec.c @@ -516,7 +516,7 @@ void page_set_flags(target_ulong start, target_ulong last, int flags) ~(reset ? 0 : PAGE_STICKY)); } if (inval_tb) { - tb_invalidate_phys_range(start, last + 1); + tb_invalidate_phys_range(start, last); } } diff --git a/softmmu/physmem.c b/softmmu/physmem.c index e35061bba4..0e0182d9f2 100644 --- a/softmmu/physmem.c +++ b/softmmu/physmem.c @@ -2527,7 +2527,7 @@ static void invalidate_and_set_dirty(MemoryRegion *mr, hwaddr addr, } if (dirty_log_mask & (1 << DIRTY_MEMORY_CODE)) { assert(tcg_enabled()); - tb_invalidate_phys_range(addr, addr + length); + tb_invalidate_phys_range(addr, addr + length - 1); dirty_log_mask &= ~(1 << DIRTY_MEMORY_CODE); } cpu_physical_memory_set_dirty_range(addr, length, dirty_log_mask); From patchwork Wed Mar 22 15:07:44 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 665908 Delivered-To: patch@linaro.org Received: by 2002:a5d:4d08:0:0:0:0:0 with SMTP id z8csp204295wrt; Wed, 22 Mar 2023 08:10:05 -0700 (PDT) X-Google-Smtp-Source: AK7set+hp83+jQGwh19tN/vPWuCjkV2g2OoFxQskuEI9xdvW+FlU2vwVpi/VmOqTGzxEsF0rrDqO X-Received: by 2002:ac8:5e53:0:b0:3bf:a3fc:c70a with SMTP id i19-20020ac85e53000000b003bfa3fcc70amr5580050qtx.28.1679497805388; Wed, 22 Mar 2023 08:10:05 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1679497805; cv=none; d=google.com; s=arc-20160816; b=bNx8cg7xs6ZgcKHc8k7j1WlQVWvoNQrgayuWGyP2EEuRT4sS9/iw8UdygVYBaik8iR LqytlxGjpERPjecI18/4SliMUP1Y9R2LxQiweImjuMzNTSXwZfC5EWwNq7yYDwXsOZp6 Zb6RtGo/dzFDjk5NC4svWDn6Sb89Noed+jMlTw1tqTAcNFbS27LWyDBYgqeiv9lGYj0B gXg5ZOtVyGSfnt7Oxuya1XJPpc+ZSFtvqKmJwgKqSGhwfF2bUtRzcwzHzYxqrabFEz9n 6zfJuwPNDMbYUhYV8BZc/SnHWSnFmdIU+j9j9OeGTdt/c4Wg59okui97HJ2eWNuJhObu nP4A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=fXNPlCQTG4Q+TjXBR7MVbKgvdvefxmvjapXjC24wVMI=; b=DAUGMw3MZ9ylF8LoHSbOHf19tZMbTMzC7DUrRt+YHJSBkEHD3csIEUytNzki9d2bNO tsQ28jWPVoUH19NZqKfo6UHEM6UHnJTR44EEOmm5O6P2mTdbYcLl31U7phzepCvKNjtD bpCWDlONbFSKL8Fr4Ekemqir3rC88DPUihewJ/kJ21t4HcZS69r0BCj8/FCACmsBZPCD pk/fTdpdTVqWjQNziG0IWOFbd3cu3ocULMHZknuKPNL9Piyb6sm2ILkM2ylszSIv2d0Y eBvYpRb4FbrmSSmu2IjlDiTCz4zvAIHag6d+C2shjURTIWkLY7rBdNyObuNSGq2kA9Wo pnBA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=T3dyVMMO; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [209.51.188.17]) by mx.google.com with ESMTPS id m64-20020a375843000000b0073ba400e4b5si9502492qkb.10.2023.03.22.08.10.05 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 22 Mar 2023 08:10:05 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=T3dyVMMO; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pf04l-0003fY-8W; Wed, 22 Mar 2023 11:08:31 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pf04K-00031y-E6 for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:08:07 -0400 Received: from mail-pl1-x634.google.com ([2607:f8b0:4864:20::634]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pf04H-0007Fk-Dw for qemu-devel@nongnu.org; Wed, 22 Mar 2023 11:08:04 -0400 Received: by mail-pl1-x634.google.com with SMTP id w4so11476669plg.9 for ; Wed, 22 Mar 2023 08:07:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1679497679; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=fXNPlCQTG4Q+TjXBR7MVbKgvdvefxmvjapXjC24wVMI=; b=T3dyVMMOzUItdSj38r3iKSVE/xo8/sV3BNryvESme5fdvW2qJKMTmncOlVJ3Sx1Hde qgUA3kXvYkMW7PP+ug+V6MrmTvvGrj4S3OhOsx+CTbhWUmlY+TkMcwMN6h01m223XpUX sA+SxVHHz9X2fX3DVeylD2ucV1PRcXWr0UyxzMVILaDczLAeI9zywN1khxk/frJqY3pr oq5NZLPCfOfRM09vFXAukLW86QGcx9Wi5SYOke2tGT6D4Z9ZeEUN3Y+jhynt6VRO4ZbA lGWRO3JFAnvELJyLMCbSolSZPXn46vFGEsIcAWf7fmWqrl6LtwBql4bQTa1aguISinu6 FQ6w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679497679; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=fXNPlCQTG4Q+TjXBR7MVbKgvdvefxmvjapXjC24wVMI=; b=tbo5msfYoLuxxF2TK0S+d8jjweHo3ib0gYXItSGeWyFcvwGc2/UA579SUHrc2M7aix tYv2i9ob5Z20o5z7PCzNe0NFJYVnj2IBURM2QjyIBm41SqPk1yBaBvA0m54jmMMm30BB swuUPt6Syoe0uoM3V/wrkvhNXlCvGjtqLHCkGLggURH7Quif0yA6C6pY8/4CF/xE3hwQ rtNeSoMWPdY0ypdu6BV7FNsdcWHfBPmAGpaKIrKUq/MNMURNF49BGnN6j4yHpe7J5EJr va4Qd6xiKtNuAAewQB/0rrZ/F3FeS1G3rnQCHUx3Cf8WvMx6iwRkCx0n7scsbWi5fFDv Wvhw== X-Gm-Message-State: AO0yUKWrQ7ta5GEczGZ/bL9XaFOe0YmFCblptsOL4QuIgQ1lo9HdcF91 j8qL5kOpBk2TGKrKLjZpB/SL9lKB89Ik5i9h0XU= X-Received: by 2002:a17:902:e8c3:b0:19f:3e9b:7527 with SMTP id v3-20020a170902e8c300b0019f3e9b7527mr2434439plg.61.1679497679477; Wed, 22 Mar 2023 08:07:59 -0700 (PDT) Received: from stoup.. (24-113-166-229.wavecable.com. [24.113.166.229]) by smtp.gmail.com with ESMTPSA id 17-20020a170902ee5100b0019339f3368asm10757555plo.3.2023.03.22.08.07.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Mar 2023 08:07:59 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: cota@braap.org, peter.maydell@linaro.org Subject: [PATCH for-8.0 11/11] linux-user/arm: Take more care allocating commpage Date: Wed, 22 Mar 2023 08:07:44 -0700 Message-Id: <20230322150744.175010-12-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230322150744.175010-1-richard.henderson@linaro.org> References: <20230322150744.175010-1-richard.henderson@linaro.org> MIME-Version: 1.0 Received-SPF: pass client-ip=2607:f8b0:4864:20::634; envelope-from=richard.henderson@linaro.org; helo=mail-pl1-x634.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: qemu-devel-bounces+patch=linaro.org@nongnu.org User setting of -R reserved_va can lead to an assertion failure in page_set_flags. Sanity check the value of reserved_va and print an error message instead. Do not allocate a commpage at all for m-profile cpus. Signed-off-by: Richard Henderson --- linux-user/elfload.c | 37 +++++++++++++++++++++++++++---------- 1 file changed, 27 insertions(+), 10 deletions(-) diff --git a/linux-user/elfload.c b/linux-user/elfload.c index b068676340..0529430b1d 100644 --- a/linux-user/elfload.c +++ b/linux-user/elfload.c @@ -422,12 +422,32 @@ enum { static bool init_guest_commpage(void) { - abi_ptr commpage = HI_COMMPAGE & -qemu_host_page_size; - void *want = g2h_untagged(commpage); - void *addr = mmap(want, qemu_host_page_size, PROT_READ | PROT_WRITE, - MAP_ANONYMOUS | MAP_PRIVATE | MAP_FIXED, -1, 0); + ARMCPU *cpu = ARM_CPU(thread_cpu); + abi_ptr want = HI_COMMPAGE & TARGET_PAGE_MASK; + abi_ptr addr; - if (addr == MAP_FAILED) { + /* + * M-profile allocates maximum of 2GB address space, so can never + * allocate the commpage. Skip it. + */ + if (arm_feature(&cpu->env, ARM_FEATURE_M)) { + return true; + } + + /* + * If reserved_va does not cover the commpage, we get an assert + * in page_set_flags. Produce an intelligent error instead. + */ + if (reserved_va != 0 && want + TARGET_PAGE_SIZE - 1 > reserved_va) { + error_report("Allocating guest commpage: -R 0x%" PRIx64 " too small", + (uint64_t)reserved_va + 1); + exit(EXIT_FAILURE); + } + + addr = target_mmap(want, TARGET_PAGE_SIZE, PROT_READ | PROT_WRITE, + MAP_ANONYMOUS | MAP_PRIVATE | MAP_FIXED, -1, 0); + + if (addr == -1) { perror("Allocating guest commpage"); exit(EXIT_FAILURE); } @@ -436,15 +456,12 @@ static bool init_guest_commpage(void) } /* Set kernel helper versions; rest of page is 0. */ - __put_user(5, (uint32_t *)g2h_untagged(0xffff0ffcu)); + put_user_u32(5, 0xffff0ffcu); - if (mprotect(addr, qemu_host_page_size, PROT_READ)) { + if (target_mprotect(addr, qemu_host_page_size, PROT_READ | PROT_EXEC)) { perror("Protecting guest commpage"); exit(EXIT_FAILURE); } - - page_set_flags(commpage, commpage | ~qemu_host_page_mask, - PAGE_READ | PAGE_EXEC | PAGE_VALID); return true; }