From patchwork Wed Oct 9 15:08:32 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 833968 Delivered-To: patch@linaro.org Received: by 2002:adf:a1de:0:b0:37d:45d0:187 with SMTP id v30csp160470wrv; Wed, 9 Oct 2024 08:09:13 -0700 (PDT) X-Forwarded-Encrypted: i=2; AJvYcCXj5z6t7KKmjIpLo2IdpjnrcCr/S0wLhdmoLIFvaz+jCFPMsG84bTJ9QeDpxU4gTBUQOtpx/Q==@linaro.org X-Google-Smtp-Source: AGHT+IEivgT5iwCtmc1anFbylh53qBbSIMTeaIMGsRe5/rQrNxXndCy0RQbVln77YRUlDHlWf6Ak X-Received: by 2002:a05:6214:2a81:b0:6cb:42f6:674a with SMTP id 6a1803df08f44-6cbba980856mr126786346d6.18.1728486552833; Wed, 09 Oct 2024 08:09:12 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1728486552; cv=none; d=google.com; s=arc-20240605; b=gtqB1c72b8e/DKOLZHR5wvqF2NDjPvrxaC+YEQijYgkUAFq6gUfsRFeAn+4zYhIRPN eNGlkNsxar6qsUCcfWXOrbibzjxffOve7JO3xVPcSwZ+y2NHvRAj5I16SoiLsfcc/jxI +j5mAxeFaIt3rzXv4lXRedNt2ZAcSmVMPpBEIhH65V0w5BDbBpt4Syt21vhYO1Ngxg5x zXGBlIAJASG3aktYKIBv5xGJA8FyU6yx6no1PNDAXh9ifn8RPlE6MgFcsSGHV1aJCkhH 4b3gRrs2LwRmIRt+Px0q4vOFgSGq+HPEvDvL8U+Wrk/cO4oxe/AO19Ce8lhRhUTeMYwY Z8vg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:message-id:date:subject:to:from:dkim-signature; bh=FzZm7uKCk7b4BByU9zV10eNVb7kQGJkY/vOPQhrdAhc=; fh=PnYt+qEB9tAfMKoqBm2xjKOFpYyFFGPudh5cVIoieJM=; b=bra4KCI3RDkiqJEGu1Ry4syMA5PEf+J/Ic4vzsJXlD1zNVN+MsX2S+amecLrr0eMYb YisSDdg/hu10MxEKs1MdllzKbAmrXN+AWjAAU/sEZ3YKINrvVwls0ctLvAU+Gxte7Xm/ UWAaZF+iXd3d9DePGoSbG8vifr5teIZongfhz55SsfWOTLQ7AOvhF7Ik5JKYTCb4m6tL LQN0wZ19PSlwQU7/uCrDi48W8jklKJfEzVNZ1ayg4maz6Ty6C1KiYnQd5yaTXlVN8iSU QL1g6baZJLc0i8HH64UVNqDfqKP07Y6jFyIso9pslQ8sW34I7BqkD60RZzDqxyj/hwgZ caRg==; dara=google.com ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=zMLwaiIF; 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; dara=neutral header.i=@linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [209.51.188.17]) by mx.google.com with ESMTPS id 6a1803df08f44-6cba47a7832si108940816d6.586.2024.10.09.08.09.12 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 09 Oct 2024 08:09: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=zMLwaiIF; 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; dara=neutral header.i=@linaro.org Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1syYJG-0001Ju-26; Wed, 09 Oct 2024 11:09:06 -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 1syYJC-0001JF-MM for qemu-devel@nongnu.org; Wed, 09 Oct 2024 11:09:02 -0400 Received: from mail-pf1-x42f.google.com ([2607:f8b0:4864:20::42f]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1syYJ8-0007vz-Pk for qemu-devel@nongnu.org; Wed, 09 Oct 2024 11:09:00 -0400 Received: by mail-pf1-x42f.google.com with SMTP id d2e1a72fcca58-71dfc1124cdso849338b3a.1 for ; Wed, 09 Oct 2024 08:08:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1728486537; x=1729091337; darn=nongnu.org; h=content-transfer-encoding:mime-version:message-id:date:subject:to :from:from:to:cc:subject:date:message-id:reply-to; bh=FzZm7uKCk7b4BByU9zV10eNVb7kQGJkY/vOPQhrdAhc=; b=zMLwaiIFUdVHhc9uWJV1FrRiHULTdVdUYbYYU0djEhuOB3DgrX1+18j8RreEGkLvgz d6GbFgD79Bz1JISlSyfOpUfPfnoGA1TtE/RRH4++U+vDIBoA0BdofJAqplxjX8QgBEjJ Gk9boSG/gDmGDHkrYzG4n6Qmk45sMpquqbJUQ1l9hzoB2qBHzHe7IjhBE8IHr2nzye8h FR/J50mw1I2DaZ65F2808sPukj8mB602BjF7DVgwKZF/oOV5QaXPNmVqV1goZm2cQdHT YM5YAkTHPbymV16BivLbLu/1kk6hzz18OdgtLLmAoC/5U9QJ/2IYqb7vaAv/KaPkMjgS wGQQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728486537; x=1729091337; h=content-transfer-encoding:mime-version:message-id:date:subject:to :from:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=FzZm7uKCk7b4BByU9zV10eNVb7kQGJkY/vOPQhrdAhc=; b=lIuayJgT8p3fomr6gM0cFr2P51CPVmRkFLuXUfLdw314Quazy6h9Ryqhh3ZG+8xPUQ 1FNuhW+Rbff5oKjHWx18mnr5DqoFKy6UcmsusV1SHW1QcymRJHkAsXWwl3K7sBNcGcS6 b+B5fS21nz3TZac9MI5Qx6li4NErJHX0pRSvyZPXYeDnn9zCCwiAZXUk0UBVDDS2y9oD qbOcd7ME0o82eux0eKILZWsj1aQaImkxA2Y82feXz/bPnop5+Cz+xXRfqeuVlzovVrBn Td+mgWzC6RN2K3JAcI5HDQe0DTCZUHdDF/dlMbW6f0rVT6353pMbdZJHqtgHpyj1hiHl 5org== X-Gm-Message-State: AOJu0Yy50pwP2meTrmDgbOF8R/FpnPynq+ejnbtKCUW/6rqK0aIBz7KH ORhjfIJK/HNYk3WbJfSWUDHV6l5rwLFkv8Q5WGghr+FIOr8UR5bl6+sbX3J9W/gyzMHtazKFKFw c X-Received: by 2002:a05:6a00:2191:b0:71e:21c:bf08 with SMTP id d2e1a72fcca58-71e1d352956mr4849004b3a.1.1728486537109; Wed, 09 Oct 2024 08:08:57 -0700 (PDT) Received: from stoup.. (174-21-81-121.tukw.qwest.net. [174.21.81.121]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-71df0d65278sm7881094b3a.160.2024.10.09.08.08.56 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 09 Oct 2024 08:08:56 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Subject: [RFC PATCH 00/23] accel/tcg: Convert victim tlb to IntervalTree Date: Wed, 9 Oct 2024 08:08:32 -0700 Message-ID: <20241009150855.804605-1-richard.henderson@linaro.org> X-Mailer: git-send-email 2.43.0 MIME-Version: 1.0 Received-SPF: pass client-ip=2607:f8b0:4864:20::42f; envelope-from=richard.henderson@linaro.org; helo=mail-pf1-x42f.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 Based-on: 20241009000453.315652-1-richard.henderson@linaro.org ("[PATCH v3 00/20] accel/tcg: Introduce tlb_fill_align hook") The initial idea was: how much can we do with an intelligent data structure for the same cost as a linear search through an array? This is an initial installment along these lines. This is about as far as I can go without first converting all targets to the new tlb_fill_align hook. Indeed, the final two patches will not compile with all targets enabled, but hint at the direction of the next steps. I do not expect large perf changes with this patch set. I will be happy if performance comes out even. r~ Richard Henderson (23): util/interval-tree: Introduce interval_tree_free_nodes accel/tcg: Split out tlbfast_flush_locked accel/tcg: Split out tlbfast_{index,entry} accel/tcg: Split out tlbfast_flush_range_locked accel/tcg: Fix flags usage in mmu_lookup1, atomic_mmu_lookup accel/tcg: Early exit for zero length in tlb_flush_range_by_mmuidx* accel/tcg: Flush entire tlb when a masked range wraps accel/tcg: Add IntervalTreeRoot to CPUTLBDesc accel/tcg: Populate IntervalTree in tlb_set_page_full accel/tcg: Remove IntervalTree entry in tlb_flush_page_locked accel/tcg: Remove IntervalTree entries in tlb_flush_range_locked accel/tcg: Process IntervalTree entries in tlb_reset_dirty accel/tcg: Process IntervalTree entries in tlb_set_dirty accel/tcg: Replace victim_tlb_hit with tlbtree_hit accel/tcg: Remove the victim tlb include/exec/tlb-common: Move CPUTLBEntryFull from hw/core/cpu.h accel/tcg: Delay plugin adjustment in probe_access_internal accel/tcg: Call cpu_ld*_code_mmu from cpu_ld*_code accel/tcg: Always use IntervalTree for code lookups accel/tcg: Link CPUTLBEntry to CPUTLBEntryTree accel/tcg: Remove CPUTLBDesc.fulltlb accel/tcg: Drop TCGCPUOps.tlb_fill -- NOTYET accel/tcg: Unexport tlb_set_page* include/exec/cpu-all.h | 3 + include/exec/exec-all.h | 57 ---- include/exec/tlb-common.h | 68 +++- include/hw/core/cpu.h | 75 +---- include/hw/core/tcg-cpu-ops.h | 10 - include/qemu/interval-tree.h | 11 + accel/tcg/cputlb.c | 599 +++++++++++++++++++--------------- util/interval-tree.c | 20 ++ util/selfmap.c | 13 +- 9 files changed, 431 insertions(+), 425 deletions(-)