From patchwork Tue Feb 13 09:32:50 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Oliver Upton X-Patchwork-Id: 200295 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7300:bc8a:b0:106:860b:bbdd with SMTP id dn10csp425070dyb; Tue, 13 Feb 2024 01:38:21 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCUCrLOT5CfQ7VODmjq8dgB88b/xEEm4s1Vh0C10gq3zB0R7g8oyYOt6zPT+hMjuua5JZgjbF5v4bR8L7dPpLkR4OxGggw== X-Google-Smtp-Source: AGHT+IEya+hG0Jb0Nxuh4W95uUuagp9P3BT+R1rp5wDe3dlIiQudgdKimFKSNxjy5HsEPZtQUPtm X-Received: by 2002:a17:906:e287:b0:a3c:8cf8:9383 with SMTP id gg7-20020a170906e28700b00a3c8cf89383mr4292165ejb.37.1707817101035; Tue, 13 Feb 2024 01:38:21 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707817101; cv=pass; d=google.com; s=arc-20160816; b=mgCByr0Igi6HinwQ4E9b4a9d8tIAv+K5ZpYsnNN4iOV5uot05K8YHM++KikRw9dt5L NS61Ut+go33FzRSawz4rsBre4W4Axs1PDXWpk+afVhqoI9F9o3UxzM3THMHaUL2q86km bxBlA5O//zJuB0NTtmPFJ1SOyWGV7p1ha4dNBxkkk4vUDTDmyaMcbPXT67JEJrTPjAZP 6cj5XbN1U19sr2wHw41xWAZuJqUaP7D4FDryNw9QN41BtiefGn6YHsT7QP+J51pD6oNY XQf3b68pEZO/F8opogGRxZ2IJ0FHqWqjDy7qHQzgB+ykqRWG0OW8ohJc25cHUEekKhLW iUxA== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:references:in-reply-to:message-id :date:subject:cc:to:from:dkim-signature; bh=BKECb1eTQQJ/f0GKxMxXWqmjCFHiATDCrLFETxE2qgY=; fh=PzNE90v4iM9Zvw5WFDr6s/X7fBoWF7du8zJvDHj7fqM=; b=hUXqE/VKOpYeaBswfZjU8LhdFcGx4742gjvlU08FIdfL8hVF6/dE2TulfEkepKIeWz +FPjaZQY3UmRAS1PgTjPq2dLw/AHCKGxlId0J+P6JtORw3LWvoD/saNzFAGpu7beG8Dm 2Xt7v3RvyzxlOi9PxXCD2pd5c7/wUo+Xq11r74Fjvy/XIHoFo2vlxsQTXfW5IqABRFNv BuA4TGqSu49dJwlBokqBdOIe7d36MXHgDq+pwMyUlUp/VQo8UdPpSTw6XwdzbFd39DnC aCTTRXpkES3e1rOxfV5lrV59bz85uTVZNeBxEJxaKtW5QXrfdpScQAbHARKgR4QfNEew VCYA==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@linux.dev header.s=key1 header.b=Kv8VMoYw; arc=pass (i=1 spf=pass spfdomain=linux.dev dkim=pass dkdomain=linux.dev dmarc=pass fromdomain=linux.dev); spf=pass (google.com: domain of linux-kernel+bounces-63218-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-63218-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linux.dev X-Forwarded-Encrypted: i=2; AJvYcCVYkIz9Cf9+GC3noeUmUvyrErbG0NitTahvmFRM1KhbroRIuQoJl+vCF7Ftl7AogQ7z1rnqEr2XYYUiswZX7BvZMJQtSg== Received: from am.mirrors.kernel.org (am.mirrors.kernel.org. [147.75.80.249]) by mx.google.com with ESMTPS id j15-20020a170906050f00b00a3d1bc0c9b6si40575eja.291.2024.02.13.01.38.20 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 13 Feb 2024 01:38:21 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-63218-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) client-ip=147.75.80.249; Authentication-Results: mx.google.com; dkim=pass header.i=@linux.dev header.s=key1 header.b=Kv8VMoYw; arc=pass (i=1 spf=pass spfdomain=linux.dev dkim=pass dkdomain=linux.dev dmarc=pass fromdomain=linux.dev); spf=pass (google.com: domain of linux-kernel+bounces-63218-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-63218-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linux.dev Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by am.mirrors.kernel.org (Postfix) with ESMTPS id 78B451F23649 for ; Tue, 13 Feb 2024 09:38:20 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 2297F51C5C; Tue, 13 Feb 2024 09:33:42 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=linux.dev header.i=@linux.dev header.b="Kv8VMoYw" Received: from out-175.mta1.migadu.com (out-175.mta1.migadu.com [95.215.58.175]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id E8955364DB for ; Tue, 13 Feb 2024 09:33:37 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=95.215.58.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707816819; cv=none; b=fATo7uoaTe19HtlBR5iiHFN2rXhwj3RfresGf8MwZbhwZVCJca+SKJCPwpbsvtM+Qx8hFptpul7Fh1H32A6M/Uf0HDD8piN4OggAjrvtnv9dB2dfusAqZlSGfZDHcNaDO9+UqHdsTLIcTUBmhEu5mtXL+J1EUv9xJeNJaLfYBMY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707816819; c=relaxed/simple; bh=Qi8rU6NjOkVcx9TX1/O9p73F+ULC5MIdl/I9CDfvIew=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=hsmiMYczPi3RM7gIZISGgDedbmy/i0i4dQEX8qHoeyRXAjNmDUuQZLyglgG1PTmoJmXYi3ngMEdvDN2gIuuBV7NY46/jiKrTNSGV00TpBwh6aIPM04mTrKZ6DRj2q1fxmHlO9+Alu8cXuSZx9RBwfbSFTWuGn/6x0N/1tteANxs= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linux.dev; spf=pass smtp.mailfrom=linux.dev; dkim=pass (1024-bit key) header.d=linux.dev header.i=@linux.dev header.b=Kv8VMoYw; arc=none smtp.client-ip=95.215.58.175 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linux.dev Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=linux.dev X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.dev; s=key1; t=1707816816; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=BKECb1eTQQJ/f0GKxMxXWqmjCFHiATDCrLFETxE2qgY=; b=Kv8VMoYwDOw5o/4ifDv6LsdWhzI+zrP+hXZ/dyggg6voxrWhMxjS3n2slHUN6XjTEoqdYA dQuL0Hu9I6PuXqEFLSppH2l3M8sTV/qJmjOHGnCDT3mXHmHde1DdJLi7H/mz2ONCtgqeki OIZDsSupblvzEtuDnC7WHJDgthL8+mY= From: Oliver Upton To: kvmarm@lists.linux.dev Cc: kvm@vger.kernel.org, Marc Zyngier , James Morse , Suzuki K Poulose , Zenghui Yu , linux-kernel@vger.kernel.org, Oliver Upton Subject: [PATCH v2 13/23] KVM: arm64: vgic-its: Pick cache victim based on usage count Date: Tue, 13 Feb 2024 09:32:50 +0000 Message-ID: <20240213093250.3960069-14-oliver.upton@linux.dev> In-Reply-To: <20240213093250.3960069-1-oliver.upton@linux.dev> References: <20240213093250.3960069-1-oliver.upton@linux.dev> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Migadu-Flow: FLOW_OUT X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1790776024824972848 X-GMAIL-MSGID: 1790776024824972848 To date the translation cache LRU policy relies on the ordering of the linked-list to pick the victim, as entries are moved to the head of the list on every cache hit. These sort of transformations are incompatible with an rculist, necessitating a different strategy for recording usage in-place. Count the number of cache hits since the last translation cache miss for every entry. The preferences for selecting a victim are as follows: - Invalid entries over valid entries - Valid entry with the lowest usage count - In the case of a tie, pick the entry closest to the tail (oldest) Signed-off-by: Oliver Upton --- arch/arm64/kvm/vgic/vgic-its.c | 46 ++++++++++++++++++++++++++-------- 1 file changed, 36 insertions(+), 10 deletions(-) diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c index a7ba20b57264..35926d5ae561 100644 --- a/arch/arm64/kvm/vgic/vgic-its.c +++ b/arch/arm64/kvm/vgic/vgic-its.c @@ -157,6 +157,7 @@ struct vgic_translation_cache_entry { u32 devid; u32 eventid; struct vgic_irq *irq; + atomic64_t usage_count; }; /** @@ -580,13 +581,7 @@ static struct vgic_irq *__vgic_its_check_cache(struct vgic_dist *dist, cte->eventid != eventid) continue; - /* - * Move this entry to the head, as it is the most - * recently used. - */ - if (!list_is_first(&cte->entry, &dist->lpi_translation_cache)) - list_move(&cte->entry, &dist->lpi_translation_cache); - + atomic64_inc(&cte->usage_count); return cte->irq; } @@ -619,6 +614,36 @@ static unsigned int vgic_its_max_cache_size(struct kvm *kvm) return atomic_read(&kvm->online_vcpus) * LPI_DEFAULT_PCPU_CACHE_SIZE; } +static struct vgic_translation_cache_entry *vgic_its_cache_victim(struct vgic_dist *dist, + s64 *max_usage) +{ + struct vgic_translation_cache_entry *cte, *victim = NULL; + s64 min, tmp, max = S64_MIN; + + /* + * Find the least used cache entry since the last cache miss, preferring + * older entries in the case of a tie. Return the max usage count seen + * during the scan to initialize the new cache entry. + */ + list_for_each_entry(cte, &dist->lpi_translation_cache, entry) { + tmp = atomic64_read(&cte->usage_count); + max = max(max, tmp); + + if (!cte->irq) { + victim = cte; + break; + } + + if (!victim || tmp <= min) { + victim = cte; + min = tmp; + } + } + + *max_usage = max; + return victim; +} + static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its, u32 devid, u32 eventid, struct vgic_irq *irq) @@ -627,6 +652,7 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its, struct vgic_dist *dist = &kvm->arch.vgic; unsigned long flags; phys_addr_t db; + s64 usage = 0; /* Do not cache a directly injected interrupt */ if (irq->hw) @@ -650,9 +676,8 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its, } if (dist->lpi_cache_count >= vgic_its_max_cache_size(kvm)) { - /* Always reuse the last entry (LRU policy) */ - victim = list_last_entry(&dist->lpi_translation_cache, - typeof(*cte), entry); + victim = vgic_its_cache_victim(dist, &usage); + list_del(&victim->entry); dist->lpi_cache_count--; } @@ -664,6 +689,7 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its, lockdep_assert_held(&its->its_lock); vgic_get_irq_kref(irq); + atomic64_set(&new->usage_count, usage); new->db = db; new->devid = devid; new->eventid = eventid;